151 static inline struct sfq_head *sfq_dep_head(struct sfq_sched_data *q, sfq_index val)  in sfq_dep_head()  argument
154 		return &q->slots[val].dep;  in sfq_dep_head()
155 	return &q->dep[val - SFQ_MAX_FLOWS];  in sfq_dep_head()
158 static unsigned int sfq_hash(const struct sfq_sched_data *q,  in sfq_hash()  argument
161 	return skb_get_hash_perturb(skb, q->perturbation) & (q->divisor - 1);  in sfq_hash()
167 	struct sfq_sched_data *q = qdisc_priv(sch);  in sfq_classify()  local
174 	    TC_H_MIN(skb->priority) <= q->divisor)  in sfq_classify()
177 	fl = rcu_dereference_bh(q->filter_list);  in sfq_classify()
179 		return sfq_hash(q, skb) + 1;  in sfq_classify()
193 		if (TC_H_MIN(res.classid) <= q->divisor)  in sfq_classify()
202 static inline void sfq_link(struct sfq_sched_data *q, sfq_index x)  in sfq_link()  argument
205 	struct sfq_slot *slot = &q->slots[x];  in sfq_link()
209 	n = q->dep[qlen].next;  in sfq_link()
214 	q->dep[qlen].next = x;		/* sfq_dep_head(q, p)->next = x */  in sfq_link()
215 	sfq_dep_head(q, n)->prev = x;  in sfq_link()
218 #define sfq_unlink(q, x, n, p)			\  argument
220 		n = q->slots[x].dep.next;	\
221 		p = q->slots[x].dep.prev;	\
222 		sfq_dep_head(q, p)->next = n;	\
223 		sfq_dep_head(q, n)->prev = p;	\
227 static inline void sfq_dec(struct sfq_sched_data *q, sfq_index x)  in sfq_dec()  argument
232 	sfq_unlink(q, x, n, p);  in sfq_dec()
234 	d = q->slots[x].qlen--;  in sfq_dec()
235 	if (n == p && q->cur_depth == d)  in sfq_dec()
236 		q->cur_depth--;  in sfq_dec()
237 	sfq_link(q, x);  in sfq_dec()
240 static inline void sfq_inc(struct sfq_sched_data *q, sfq_index x)  in sfq_inc()  argument
245 	sfq_unlink(q, x, n, p);  in sfq_inc()
247 	d = ++q->slots[x].qlen;  in sfq_inc()
248 	if (q->cur_depth < d)  in sfq_inc()
249 		q->cur_depth = d;  in sfq_inc()
250 	sfq_link(q, x);  in sfq_inc()
294 	struct sfq_sched_data *q = qdisc_priv(sch);  in sfq_drop()  local
295 	sfq_index x, d = q->cur_depth;  in sfq_drop()
302 		x = q->dep[d].next;  in sfq_drop()
303 		slot = &q->slots[x];  in sfq_drop()
305 		skb = q->headdrop ? slot_dequeue_head(slot) : slot_dequeue_tail(slot);  in sfq_drop()
308 		sfq_dec(q, x);  in sfq_drop()
309 		sch->q.qlen--;  in sfq_drop()
318 		x = q->tail->next;  in sfq_drop()
319 		slot = &q->slots[x];  in sfq_drop()
320 		q->tail->next = slot->next;  in sfq_drop()
321 		q->ht[slot->hash] = SFQ_EMPTY_SLOT;  in sfq_drop()
329 static int sfq_prob_mark(const struct sfq_sched_data *q)  in sfq_prob_mark()  argument
331 	return q->flags & TC_RED_ECN;  in sfq_prob_mark()
335 static int sfq_hard_mark(const struct sfq_sched_data *q)  in sfq_hard_mark()  argument
337 	return (q->flags & (TC_RED_ECN | TC_RED_HARDDROP)) == TC_RED_ECN;  in sfq_hard_mark()
340 static int sfq_headdrop(const struct sfq_sched_data *q)  in sfq_headdrop()  argument
342 	return q->headdrop;  in sfq_headdrop()
348 	struct sfq_sched_data *q = qdisc_priv(sch);  in sfq_enqueue()  local
365 	x = q->ht[hash];  in sfq_enqueue()
366 	slot = &q->slots[x];  in sfq_enqueue()
368 		x = q->dep[0].next; /* get a free slot */  in sfq_enqueue()
371 		q->ht[hash] = x;  in sfq_enqueue()
372 		slot = &q->slots[x];  in sfq_enqueue()
378 	if (q->red_parms) {  in sfq_enqueue()
379 		slot->vars.qavg = red_calc_qavg_no_idle_time(q->red_parms,  in sfq_enqueue()
382 		switch (red_action(q->red_parms,  in sfq_enqueue()
390 			if (sfq_prob_mark(q)) {  in sfq_enqueue()
392 				if (sfq_headdrop(q) &&  in sfq_enqueue()
394 					q->stats.prob_mark_head++;  in sfq_enqueue()
398 					q->stats.prob_mark++;  in sfq_enqueue()
402 			q->stats.prob_drop++;  in sfq_enqueue()
407 			if (sfq_hard_mark(q)) {  in sfq_enqueue()
409 				if (sfq_headdrop(q) &&  in sfq_enqueue()
411 					q->stats.forced_mark_head++;  in sfq_enqueue()
415 					q->stats.forced_mark++;  in sfq_enqueue()
419 			q->stats.forced_drop++;  in sfq_enqueue()
424 	if (slot->qlen >= q->maxdepth) {  in sfq_enqueue()
426 		if (!sfq_headdrop(q))  in sfq_enqueue()
444 	sfq_inc(q, x);  in sfq_enqueue()
446 		if (q->tail == NULL) {	/* It is the first flow */  in sfq_enqueue()
449 			slot->next = q->tail->next;  in sfq_enqueue()
450 			q->tail->next = x;  in sfq_enqueue()
456 		q->tail = slot;  in sfq_enqueue()
458 		slot->allot = q->scaled_quantum;  in sfq_enqueue()
460 	if (++sch->q.qlen <= q->limit)  in sfq_enqueue()
479 	struct sfq_sched_data *q = qdisc_priv(sch);  in sfq_dequeue()  local
485 	if (q->tail == NULL)  in sfq_dequeue()
489 	a = q->tail->next;  in sfq_dequeue()
490 	slot = &q->slots[a];  in sfq_dequeue()
492 		q->tail = slot;  in sfq_dequeue()
493 		slot->allot += q->scaled_quantum;  in sfq_dequeue()
497 	sfq_dec(q, a);  in sfq_dequeue()
499 	sch->q.qlen--;  in sfq_dequeue()
504 		q->ht[slot->hash] = SFQ_EMPTY_SLOT;  in sfq_dequeue()
507 			q->tail = NULL; /* no more active slots */  in sfq_dequeue()
510 		q->tail->next = next_a;  in sfq_dequeue()
534 	struct sfq_sched_data *q = qdisc_priv(sch);  in sfq_rehash()  local
544 	for (i = 0; i < q->maxflows; i++) {  in sfq_rehash()
545 		slot = &q->slots[i];  in sfq_rehash()
550 			sfq_dec(q, i);  in sfq_rehash()
555 		q->ht[slot->hash] = SFQ_EMPTY_SLOT;  in sfq_rehash()
557 	q->tail = NULL;  in sfq_rehash()
560 		unsigned int hash = sfq_hash(q, skb);  in sfq_rehash()
561 		sfq_index x = q->ht[hash];  in sfq_rehash()
563 		slot = &q->slots[x];  in sfq_rehash()
565 			x = q->dep[0].next; /* get a free slot */  in sfq_rehash()
574 			q->ht[hash] = x;  in sfq_rehash()
575 			slot = &q->slots[x];  in sfq_rehash()
578 		if (slot->qlen >= q->maxdepth)  in sfq_rehash()
581 		if (q->red_parms)  in sfq_rehash()
582 			slot->vars.qavg = red_calc_qavg(q->red_parms,  in sfq_rehash()
586 		sfq_inc(q, x);  in sfq_rehash()
588 			if (q->tail == NULL) {	/* It is the first flow */  in sfq_rehash()
591 				slot->next = q->tail->next;  in sfq_rehash()
592 				q->tail->next = x;  in sfq_rehash()
594 			q->tail = slot;  in sfq_rehash()
595 			slot->allot = q->scaled_quantum;  in sfq_rehash()
598 	sch->q.qlen -= dropped;  in sfq_rehash()
605 	struct sfq_sched_data *q = qdisc_priv(sch);  in sfq_perturbation()  local
609 	q->perturbation = prandom_u32();  in sfq_perturbation()
610 	if (!q->filter_list && q->tail)  in sfq_perturbation()
614 	if (q->perturb_period)  in sfq_perturbation()
615 		mod_timer(&q->perturb_timer, jiffies + q->perturb_period);  in sfq_perturbation()
620 	struct sfq_sched_data *q = qdisc_priv(sch);  in sfq_change()  local
640 		q->quantum = ctl->quantum;  in sfq_change()
641 		q->scaled_quantum = SFQ_ALLOT_SIZE(q->quantum);  in sfq_change()
643 	q->perturb_period = ctl->perturb_period * HZ;  in sfq_change()
645 		q->maxflows = min_t(u32, ctl->flows, SFQ_MAX_FLOWS);  in sfq_change()
647 		q->divisor = ctl->divisor;  in sfq_change()
648 		q->maxflows = min_t(u32, q->maxflows, q->divisor);  in sfq_change()
652 			q->maxdepth = min_t(u32, ctl_v1->depth, SFQ_MAX_DEPTH);  in sfq_change()
654 			swap(q->red_parms, p);  in sfq_change()
655 			red_set_parms(q->red_parms,  in sfq_change()
662 		q->flags = ctl_v1->flags;  in sfq_change()
663 		q->headdrop = ctl_v1->headdrop;  in sfq_change()
666 		q->limit = min_t(u32, ctl->limit, q->maxdepth * q->maxflows);  in sfq_change()
667 		q->maxflows = min_t(u32, q->maxflows, q->limit);  in sfq_change()
670 	qlen = sch->q.qlen;  in sfq_change()
671 	while (sch->q.qlen > q->limit)  in sfq_change()
673 	qdisc_tree_reduce_backlog(sch, qlen - sch->q.qlen, dropped);  in sfq_change()
675 	del_timer(&q->perturb_timer);  in sfq_change()
676 	if (q->perturb_period) {  in sfq_change()
677 		mod_timer(&q->perturb_timer, jiffies + q->perturb_period);  in sfq_change()
678 		q->perturbation = prandom_u32();  in sfq_change()
701 	struct sfq_sched_data *q = qdisc_priv(sch);  in sfq_destroy()  local
703 	tcf_destroy_chain(&q->filter_list);  in sfq_destroy()
704 	q->perturb_period = 0;  in sfq_destroy()
705 	del_timer_sync(&q->perturb_timer);  in sfq_destroy()
706 	sfq_free(q->ht);  in sfq_destroy()
707 	sfq_free(q->slots);  in sfq_destroy()
708 	kfree(q->red_parms);  in sfq_destroy()
713 	struct sfq_sched_data *q = qdisc_priv(sch);  in sfq_init()  local
716 	q->perturb_timer.function = sfq_perturbation;  in sfq_init()
717 	q->perturb_timer.data = (unsigned long)sch;  in sfq_init()
718 	init_timer_deferrable(&q->perturb_timer);  in sfq_init()
721 		q->dep[i].next = i + SFQ_MAX_FLOWS;  in sfq_init()
722 		q->dep[i].prev = i + SFQ_MAX_FLOWS;  in sfq_init()
725 	q->limit = SFQ_MAX_DEPTH;  in sfq_init()
726 	q->maxdepth = SFQ_MAX_DEPTH;  in sfq_init()
727 	q->cur_depth = 0;  in sfq_init()
728 	q->tail = NULL;  in sfq_init()
729 	q->divisor = SFQ_DEFAULT_HASH_DIVISOR;  in sfq_init()
730 	q->maxflows = SFQ_DEFAULT_FLOWS;  in sfq_init()
731 	q->quantum = psched_mtu(qdisc_dev(sch));  in sfq_init()
732 	q->scaled_quantum = SFQ_ALLOT_SIZE(q->quantum);  in sfq_init()
733 	q->perturb_period = 0;  in sfq_init()
734 	q->perturbation = prandom_u32();  in sfq_init()
742 	q->ht = sfq_alloc(sizeof(q->ht[0]) * q->divisor);  in sfq_init()
743 	q->slots = sfq_alloc(sizeof(q->slots[0]) * q->maxflows);  in sfq_init()
744 	if (!q->ht || !q->slots) {  in sfq_init()
748 	for (i = 0; i < q->divisor; i++)  in sfq_init()
749 		q->ht[i] = SFQ_EMPTY_SLOT;  in sfq_init()
751 	for (i = 0; i < q->maxflows; i++) {  in sfq_init()
752 		slot_queue_init(&q->slots[i]);  in sfq_init()
753 		sfq_link(q, i);  in sfq_init()
755 	if (q->limit >= 1)  in sfq_init()
764 	struct sfq_sched_data *q = qdisc_priv(sch);  in sfq_dump()  local
767 	struct red_parms *p = q->red_parms;  in sfq_dump()
770 	opt.v0.quantum	= q->quantum;  in sfq_dump()
771 	opt.v0.perturb_period = q->perturb_period / HZ;  in sfq_dump()
772 	opt.v0.limit	= q->limit;  in sfq_dump()
773 	opt.v0.divisor	= q->divisor;  in sfq_dump()
774 	opt.v0.flows	= q->maxflows;  in sfq_dump()
775 	opt.depth	= q->maxdepth;  in sfq_dump()
776 	opt.headdrop	= q->headdrop;  in sfq_dump()
786 	memcpy(&opt.stats, &q->stats, sizeof(opt.stats));  in sfq_dump()
787 	opt.flags	= q->flags;  in sfq_dump()
817 static void sfq_put(struct Qdisc *q, unsigned long cl)  in sfq_put()  argument
824 	struct sfq_sched_data *q = qdisc_priv(sch);  in sfq_find_tcf()  local
828 	return &q->filter_list;  in sfq_find_tcf()
841 	struct sfq_sched_data *q = qdisc_priv(sch);  in sfq_dump_class_stats()  local
842 	sfq_index idx = q->ht[cl - 1];  in sfq_dump_class_stats()
847 		const struct sfq_slot *slot = &q->slots[idx];  in sfq_dump_class_stats()
860 	struct sfq_sched_data *q = qdisc_priv(sch);  in sfq_walk()  local
866 	for (i = 0; i < q->divisor; i++) {  in sfq_walk()
867 		if (q->ht[i] == SFQ_EMPTY_SLOT ||  in sfq_walk()