150 static inline struct sfq_head *sfq_dep_head(struct sfq_sched_data *q, sfq_index val)  in sfq_dep_head()  argument
153 		return &q->slots[val].dep;  in sfq_dep_head()
154 	return &q->dep[val - SFQ_MAX_FLOWS];  in sfq_dep_head()
157 static unsigned int sfq_hash(const struct sfq_sched_data *q,  in sfq_hash()  argument
160 	return skb_get_hash_perturb(skb, &q->perturbation) & (q->divisor - 1);  in sfq_hash()
166 	struct sfq_sched_data *q = qdisc_priv(sch);  in sfq_classify()  local
173 	    TC_H_MIN(skb->priority) <= q->divisor)  in sfq_classify()
176 	fl = rcu_dereference_bh(q->filter_list);  in sfq_classify()
178 		return sfq_hash(q, skb) + 1;  in sfq_classify()
194 		if (TC_H_MIN(res.classid) <= q->divisor)  in sfq_classify()
203 static inline void sfq_link(struct sfq_sched_data *q, sfq_index x)  in sfq_link()  argument
206 	struct sfq_slot *slot = &q->slots[x];  in sfq_link()
210 	n = q->dep[qlen].next;  in sfq_link()
215 	q->dep[qlen].next = x;		/* sfq_dep_head(q, p)->next = x */  in sfq_link()
216 	sfq_dep_head(q, n)->prev = x;  in sfq_link()
219 #define sfq_unlink(q, x, n, p)			\  argument
221 		n = q->slots[x].dep.next;	\
222 		p = q->slots[x].dep.prev;	\
223 		sfq_dep_head(q, p)->next = n;	\
224 		sfq_dep_head(q, n)->prev = p;	\
228 static inline void sfq_dec(struct sfq_sched_data *q, sfq_index x)  in sfq_dec()  argument
233 	sfq_unlink(q, x, n, p);  in sfq_dec()
235 	d = q->slots[x].qlen--;  in sfq_dec()
236 	if (n == p && q->cur_depth == d)  in sfq_dec()
237 		q->cur_depth--;  in sfq_dec()
238 	sfq_link(q, x);  in sfq_dec()
241 static inline void sfq_inc(struct sfq_sched_data *q, sfq_index x)  in sfq_inc()  argument
246 	sfq_unlink(q, x, n, p);  in sfq_inc()
248 	d = ++q->slots[x].qlen;  in sfq_inc()
249 	if (q->cur_depth < d)  in sfq_inc()
250 		q->cur_depth = d;  in sfq_inc()
251 	sfq_link(q, x);  in sfq_inc()
295 	struct sfq_sched_data *q = qdisc_priv(sch);  in sfq_drop()  local
296 	sfq_index x, d = q->cur_depth;  in sfq_drop()
303 		x = q->dep[d].next;  in sfq_drop()
304 		slot = &q->slots[x];  in sfq_drop()
306 		skb = q->headdrop ? slot_dequeue_head(slot) : slot_dequeue_tail(slot);  in sfq_drop()
309 		sfq_dec(q, x);  in sfq_drop()
310 		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()
445 	sfq_inc(q, x);  in sfq_enqueue()
447 		if (q->tail == NULL) {	/* It is the first flow */  in sfq_enqueue()
450 			slot->next = q->tail->next;  in sfq_enqueue()
451 			q->tail->next = x;  in sfq_enqueue()
457 		q->tail = slot;  in sfq_enqueue()
459 		slot->allot = q->scaled_quantum;  in sfq_enqueue()
461 	if (++sch->q.qlen <= q->limit)  in sfq_enqueue()
482 	struct sfq_sched_data *q = qdisc_priv(sch);  in sfq_dequeue()  local
488 	if (q->tail == NULL)  in sfq_dequeue()
492 	a = q->tail->next;  in sfq_dequeue()
493 	slot = &q->slots[a];  in sfq_dequeue()
495 		q->tail = slot;  in sfq_dequeue()
496 		slot->allot += q->scaled_quantum;  in sfq_dequeue()
500 	sfq_dec(q, a);  in sfq_dequeue()
502 	sch->q.qlen--;  in sfq_dequeue()
507 		q->ht[slot->hash] = SFQ_EMPTY_SLOT;  in sfq_dequeue()
510 			q->tail = NULL; /* no more active slots */  in sfq_dequeue()
513 		q->tail->next = next_a;  in sfq_dequeue()
537 	struct sfq_sched_data *q = qdisc_priv(sch);  in sfq_rehash()  local
547 	for (i = 0; i < q->maxflows; i++) {  in sfq_rehash()
548 		slot = &q->slots[i];  in sfq_rehash()
553 			sfq_dec(q, i);  in sfq_rehash()
558 		q->ht[slot->hash] = SFQ_EMPTY_SLOT;  in sfq_rehash()
560 	q->tail = NULL;  in sfq_rehash()
563 		unsigned int hash = sfq_hash(q, skb);  in sfq_rehash()
564 		sfq_index x = q->ht[hash];  in sfq_rehash()
566 		slot = &q->slots[x];  in sfq_rehash()
568 			x = q->dep[0].next; /* get a free slot */  in sfq_rehash()
577 			q->ht[hash] = x;  in sfq_rehash()
578 			slot = &q->slots[x];  in sfq_rehash()
581 		if (slot->qlen >= q->maxdepth)  in sfq_rehash()
584 		if (q->red_parms)  in sfq_rehash()
585 			slot->vars.qavg = red_calc_qavg(q->red_parms,  in sfq_rehash()
589 		sfq_inc(q, x);  in sfq_rehash()
591 			if (q->tail == NULL) {	/* It is the first flow */  in sfq_rehash()
594 				slot->next = q->tail->next;  in sfq_rehash()
595 				q->tail->next = x;  in sfq_rehash()
597 			q->tail = slot;  in sfq_rehash()
598 			slot->allot = q->scaled_quantum;  in sfq_rehash()
601 	sch->q.qlen -= dropped;  in sfq_rehash()
607 	struct sfq_sched_data *q = from_timer(q, t, perturb_timer);  in sfq_perturbation()  local
608 	struct Qdisc *sch = q->sch;  in sfq_perturbation()
616 	q->perturbation = nkey;  in sfq_perturbation()
617 	if (!q->filter_list && q->tail)  in sfq_perturbation()
621 	if (q->perturb_period)  in sfq_perturbation()
622 		mod_timer(&q->perturb_timer, jiffies + q->perturb_period);  in sfq_perturbation()
628 	struct sfq_sched_data *q = qdisc_priv(sch);  in sfq_change()  local
662 		q->quantum = ctl->quantum;  in sfq_change()
663 		q->scaled_quantum = SFQ_ALLOT_SIZE(q->quantum);  in sfq_change()
665 	q->perturb_period = ctl->perturb_period * HZ;  in sfq_change()
667 		q->maxflows = min_t(u32, ctl->flows, SFQ_MAX_FLOWS);  in sfq_change()
669 		q->divisor = ctl->divisor;  in sfq_change()
670 		q->maxflows = min_t(u32, q->maxflows, q->divisor);  in sfq_change()
674 			q->maxdepth = min_t(u32, ctl_v1->depth, SFQ_MAX_DEPTH);  in sfq_change()
676 			swap(q->red_parms, p);  in sfq_change()
677 			red_set_parms(q->red_parms,  in sfq_change()
684 		q->flags = ctl_v1->flags;  in sfq_change()
685 		q->headdrop = ctl_v1->headdrop;  in sfq_change()
688 		q->limit = min_t(u32, ctl->limit, q->maxdepth * q->maxflows);  in sfq_change()
689 		q->maxflows = min_t(u32, q->maxflows, q->limit);  in sfq_change()
692 	qlen = sch->q.qlen;  in sfq_change()
693 	while (sch->q.qlen > q->limit) {  in sfq_change()
700 	qdisc_tree_reduce_backlog(sch, qlen - sch->q.qlen, dropped);  in sfq_change()
702 	del_timer(&q->perturb_timer);  in sfq_change()
703 	if (q->perturb_period) {  in sfq_change()
704 		mod_timer(&q->perturb_timer, jiffies + q->perturb_period);  in sfq_change()
705 		get_random_bytes(&q->perturbation, sizeof(q->perturbation));  in sfq_change()
724 	struct sfq_sched_data *q = qdisc_priv(sch);  in sfq_destroy()  local
726 	tcf_block_put(q->block);  in sfq_destroy()
727 	q->perturb_period = 0;  in sfq_destroy()
728 	del_timer_sync(&q->perturb_timer);  in sfq_destroy()
729 	sfq_free(q->ht);  in sfq_destroy()
730 	sfq_free(q->slots);  in sfq_destroy()
731 	kfree(q->red_parms);  in sfq_destroy()
737 	struct sfq_sched_data *q = qdisc_priv(sch);  in sfq_init()  local
741 	q->sch = sch;  in sfq_init()
742 	timer_setup(&q->perturb_timer, sfq_perturbation, TIMER_DEFERRABLE);  in sfq_init()
744 	err = tcf_block_get(&q->block, &q->filter_list, sch, extack);  in sfq_init()
749 		q->dep[i].next = i + SFQ_MAX_FLOWS;  in sfq_init()
750 		q->dep[i].prev = i + SFQ_MAX_FLOWS;  in sfq_init()
753 	q->limit = SFQ_MAX_DEPTH;  in sfq_init()
754 	q->maxdepth = SFQ_MAX_DEPTH;  in sfq_init()
755 	q->cur_depth = 0;  in sfq_init()
756 	q->tail = NULL;  in sfq_init()
757 	q->divisor = SFQ_DEFAULT_HASH_DIVISOR;  in sfq_init()
758 	q->maxflows = SFQ_DEFAULT_FLOWS;  in sfq_init()
759 	q->quantum = psched_mtu(qdisc_dev(sch));  in sfq_init()
760 	q->scaled_quantum = SFQ_ALLOT_SIZE(q->quantum);  in sfq_init()
761 	q->perturb_period = 0;  in sfq_init()
762 	get_random_bytes(&q->perturbation, sizeof(q->perturbation));  in sfq_init()
770 	q->ht = sfq_alloc(sizeof(q->ht[0]) * q->divisor);  in sfq_init()
771 	q->slots = sfq_alloc(sizeof(q->slots[0]) * q->maxflows);  in sfq_init()
772 	if (!q->ht || !q->slots) {  in sfq_init()
777 	for (i = 0; i < q->divisor; i++)  in sfq_init()
778 		q->ht[i] = SFQ_EMPTY_SLOT;  in sfq_init()
780 	for (i = 0; i < q->maxflows; i++) {  in sfq_init()
781 		slot_queue_init(&q->slots[i]);  in sfq_init()
782 		sfq_link(q, i);  in sfq_init()
784 	if (q->limit >= 1)  in sfq_init()
793 	struct sfq_sched_data *q = qdisc_priv(sch);  in sfq_dump()  local
796 	struct red_parms *p = q->red_parms;  in sfq_dump()
799 	opt.v0.quantum	= q->quantum;  in sfq_dump()
800 	opt.v0.perturb_period = q->perturb_period / HZ;  in sfq_dump()
801 	opt.v0.limit	= q->limit;  in sfq_dump()
802 	opt.v0.divisor	= q->divisor;  in sfq_dump()
803 	opt.v0.flows	= q->maxflows;  in sfq_dump()
804 	opt.depth	= q->maxdepth;  in sfq_dump()
805 	opt.headdrop	= q->headdrop;  in sfq_dump()
815 	memcpy(&opt.stats, &q->stats, sizeof(opt.stats));  in sfq_dump()
816 	opt.flags	= q->flags;  in sfq_dump()
844 static void sfq_unbind(struct Qdisc *q, unsigned long cl)  in sfq_unbind()  argument
851 	struct sfq_sched_data *q = qdisc_priv(sch);  in sfq_tcf_block()  local
855 	return q->block;  in sfq_tcf_block()
868 	struct sfq_sched_data *q = qdisc_priv(sch);  in sfq_dump_class_stats()  local
869 	sfq_index idx = q->ht[cl - 1];  in sfq_dump_class_stats()
874 		const struct sfq_slot *slot = &q->slots[idx];  in sfq_dump_class_stats()
887 	struct sfq_sched_data *q = qdisc_priv(sch);  in sfq_walk()  local
893 	for (i = 0; i < q->divisor; i++) {  in sfq_walk()
894 		if (q->ht[i] == SFQ_EMPTY_SLOT) {  in sfq_walk()