1 // SPDX-License-Identifier: GPL-2.0-only
26     "Reducing the Execution Time of Fair-Queueing Schedulers."
27     http://algo.ing.unimo.it/people/paolo/agg-sched/agg-sched.pdf
48   number of groups. Which group a class belongs to depends on the
59   QFQ_MAX_INDEX is the maximum index allowed for a group. We need
60 	one bit per index.
67 				 ^.__grp->index = 0
68 				 *.__grp->slot_shift
72   The max group index corresponds to Lmax/w_min, where
75   we can derive the shift corresponding to each group.
85   The per-scheduler-instance data contain all the data structures
92  * inside a group.
97  * Shifts used for aggregate<->group mapping.  We allow class weights that are
99  * group with the smallest index that can support the L_i / r_i configured
102  * grp->index is the index of the group; and grp->slot_shift
103  * is the shift for the corresponding (scaled) sigma_i.
121  * Possible group states.  These values are used as indexes for the bitmaps
137 	struct list_head alist;		/* Link for active-classes list. */
146 	/* group we belong to. In principle we would need the index,
148 	 * directly, only the group.
168 	u64 S, F;			/* group timestamps (approx). */
169 	unsigned int slot_shift;	/* Slot shift. */
170 	unsigned int index;		/* Group index. */  member
171 	unsigned int front;		/* Index of the front slot. */
172 	unsigned long full_slots;	/* non-empty slots */
188 	unsigned long bitmaps[QFQ_MAX_STATE];	    /* Group bitmaps. */
190 	u32 min_slot_shift;	/* Index of the group-0 bit in the bitmaps. */
210 	clc = qdisc_class_find(&q->clhash, classid);  in qfq_find_class()
227  * Calculate a flow index, given its weight and maximum packet length.
228  * index = log_2(maxlen/weight) but we need to apply the scaling.
235 	int index = 0;  in qfq_calc_index()  local
241 	index = __fls(size_map) + 1;	/* basically a log_2 */  in qfq_calc_index()
242 	index -= !(slot_size - (1ULL << (index + min_slot_shift - 1)));  in qfq_calc_index()
244 	if (index < 0)  in qfq_calc_index()
245 		index = 0;  in qfq_calc_index()
248 		 (unsigned long) ONE_FP/inv_w, maxlen, index);  in qfq_calc_index()
250 	return index;  in qfq_calc_index()
260 	INIT_LIST_HEAD(&agg->active);  in qfq_init_agg()
261 	hlist_add_head(&agg->nonfull_next, &q->nonfull_aggs);  in qfq_init_agg()
263 	agg->lmax = lmax;  in qfq_init_agg()
264 	agg->class_weight = weight;  in qfq_init_agg()
272 	hlist_for_each_entry(agg, &q->nonfull_aggs, nonfull_next)  in qfq_find_agg()
273 		if (agg->lmax == lmax && agg->class_weight == weight)  in qfq_find_agg()
286 	if (new_num_classes == q->max_agg_classes)  in qfq_update_agg()
287 		hlist_del_init(&agg->nonfull_next);  in qfq_update_agg()
289 	if (agg->num_classes > new_num_classes &&  in qfq_update_agg()
290 	    new_num_classes == q->max_agg_classes - 1) /* agg no more full */  in qfq_update_agg()
291 		hlist_add_head(&agg->nonfull_next, &q->nonfull_aggs);  in qfq_update_agg()
294 	 * agg->initial_budget > agg->budgetmax  in qfq_update_agg()
297 	agg->budgetmax = new_num_classes * agg->lmax;  in qfq_update_agg()
298 	new_agg_weight = agg->class_weight * new_num_classes;  in qfq_update_agg()
299 	agg->inv_w = ONE_FP/new_agg_weight;  in qfq_update_agg()
301 	if (agg->grp == NULL) {  in qfq_update_agg()
302 		int i = qfq_calc_index(agg->inv_w, agg->budgetmax,  in qfq_update_agg()
303 				       q->min_slot_shift);  in qfq_update_agg()
304 		agg->grp = &q->groups[i];  in qfq_update_agg()
307 	q->wsum +=  in qfq_update_agg()
308 		(int) agg->class_weight * (new_num_classes - agg->num_classes);  in qfq_update_agg()
309 	q->iwsum = ONE_FP / q->wsum;  in qfq_update_agg()
311 	agg->num_classes = new_num_classes;  in qfq_update_agg()
319 	cl->agg = agg;  in qfq_add_to_agg()
321 	qfq_update_agg(q, agg, agg->num_classes+1);  in qfq_add_to_agg()
322 	if (cl->qdisc->q.qlen > 0) { /* adding an active class */  in qfq_add_to_agg()
323 		list_add_tail(&cl->alist, &agg->active);  in qfq_add_to_agg()
324 		if (list_first_entry(&agg->active, struct qfq_class, alist) ==  in qfq_add_to_agg()
325 		    cl && q->in_serv_agg != agg) /* agg was inactive */  in qfq_add_to_agg()
334 	hlist_del_init(&agg->nonfull_next);  in qfq_destroy_agg()
335 	q->wsum -= agg->class_weight;  in qfq_destroy_agg()
336 	if (q->wsum != 0)  in qfq_destroy_agg()
337 		q->iwsum = ONE_FP / q->wsum;  in qfq_destroy_agg()
339 	if (q->in_serv_agg == agg)  in qfq_destroy_agg()
340 		q->in_serv_agg = qfq_choose_next_agg(q);  in qfq_destroy_agg()
347 	struct qfq_aggregate *agg = cl->agg;  in qfq_deactivate_class()
350 	list_del(&cl->alist); /* remove from RR queue of the aggregate */  in qfq_deactivate_class()
351 	if (list_empty(&agg->active)) /* agg is now inactive */  in qfq_deactivate_class()
358 	struct qfq_aggregate *agg = cl->agg;  in qfq_rm_from_agg()
360 	cl->agg = NULL;  in qfq_rm_from_agg()
361 	if (agg->num_classes == 1) { /* agg being emptied, destroy it */  in qfq_rm_from_agg()
365 	qfq_update_agg(q, agg, agg->num_classes-1);  in qfq_rm_from_agg()
371 	if (cl->qdisc->q.qlen > 0) /* class is active */  in qfq_deact_rm_from_agg()
386 		return -EINVAL;  in qfq_change_agg()
392 			return -ENOBUFS;  in qfq_change_agg()
416 		return -EINVAL;  in qfq_change_class()
437 			return -EINVAL;  in qfq_change_class()
445 	    lmax == cl->agg->lmax &&  in qfq_change_class()
446 	    weight == cl->agg->class_weight)  in qfq_change_class()
449 	delta_w = weight - (cl ? cl->agg->class_weight : 0);  in qfq_change_class()
451 	if (q->wsum + delta_w > QFQ_MAX_WSUM) {  in qfq_change_class()
454 				       delta_w, q->wsum);  in qfq_change_class()
455 		return -EINVAL;  in qfq_change_class()
460 			err = gen_replace_estimator(&cl->bstats, NULL,  in qfq_change_class()
461 						    &cl->rate_est,  in qfq_change_class()
475 		return -ENOBUFS;  in qfq_change_class()
477 	gnet_stats_basic_sync_init(&cl->bstats);  in qfq_change_class()
478 	cl->common.classid = classid;  in qfq_change_class()
479 	cl->deficit = lmax;  in qfq_change_class()
481 	cl->qdisc = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,  in qfq_change_class()
483 	if (cl->qdisc == NULL)  in qfq_change_class()
484 		cl->qdisc = &noop_qdisc;  in qfq_change_class()
487 		err = gen_new_estimator(&cl->bstats, NULL,  in qfq_change_class()
488 					&cl->rate_est,  in qfq_change_class()
496 	if (cl->qdisc != &noop_qdisc)  in qfq_change_class()
497 		qdisc_hash_add(cl->qdisc, true);  in qfq_change_class()
506 			err = -ENOBUFS;  in qfq_change_class()
507 			gen_kill_estimator(&cl->rate_est);  in qfq_change_class()
516 		qdisc_class_hash_insert(&q->clhash, &cl->common);  in qfq_change_class()
519 	qdisc_class_hash_grow(sch, &q->clhash);  in qfq_change_class()
525 	qdisc_put(cl->qdisc);  in qfq_change_class()
535 	gen_kill_estimator(&cl->rate_est);  in qfq_destroy_class()
536 	qdisc_put(cl->qdisc);  in qfq_destroy_class()
546 	if (qdisc_class_in_use(&cl->common)) {  in qfq_delete_class()
548 		return -EBUSY;  in qfq_delete_class()
553 	qdisc_purge_queue(cl->qdisc);  in qfq_delete_class()
554 	qdisc_class_hash_remove(&q->clhash, &cl->common);  in qfq_delete_class()
575 	return q->block;  in qfq_tcf_block()
584 		qdisc_class_get(&cl->common);  in qfq_bind_tcf()
593 	qdisc_class_put(&cl->common);  in qfq_unbind_tcf()
603 		new = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,  in qfq_graft_class()
604 					cl->common.classid, NULL);  in qfq_graft_class()
609 	*old = qdisc_replace(sch, new, &cl->qdisc);  in qfq_graft_class()
617 	return cl->qdisc;  in qfq_class_leaf()
626 	tcm->tcm_parent	= TC_H_ROOT;  in qfq_dump_class()
627 	tcm->tcm_handle	= cl->common.classid;  in qfq_dump_class()
628 	tcm->tcm_info	= cl->qdisc->handle;  in qfq_dump_class()
633 	if (nla_put_u32(skb, TCA_QFQ_WEIGHT, cl->agg->class_weight) ||  in qfq_dump_class()
634 	    nla_put_u32(skb, TCA_QFQ_LMAX, cl->agg->lmax))  in qfq_dump_class()
640 	return -EMSGSIZE;  in qfq_dump_class()
651 	xstats.weight = cl->agg->class_weight;  in qfq_dump_class_stats()
652 	xstats.lmax = cl->agg->lmax;  in qfq_dump_class_stats()
654 	if (gnet_stats_copy_basic(d, NULL, &cl->bstats, true) < 0 ||  in qfq_dump_class_stats()
655 	    gnet_stats_copy_rate_est(d, &cl->rate_est) < 0 ||  in qfq_dump_class_stats()
656 	    qdisc_qstats_copy(d, cl->qdisc) < 0)  in qfq_dump_class_stats()
657 		return -1;  in qfq_dump_class_stats()
668 	if (arg->stop)  in qfq_walk()
671 	for (i = 0; i < q->clhash.hashsize; i++) {  in qfq_walk()
672 		hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) {  in qfq_walk()
688 	if (TC_H_MAJ(skb->priority ^ sch->handle) == 0) {  in qfq_classify()
689 		pr_debug("qfq_classify: found %d\n", skb->priority);  in qfq_classify()
690 		cl = qfq_find_class(sch, skb->priority);  in qfq_classify()
696 	fl = rcu_dereference_bh(q->filter_list);  in qfq_classify()
722 	return (s64)(a - b) > 0;  in qfq_gt()
726 static inline u64 qfq_round_down(u64 ts, unsigned int shift)  in qfq_round_down()  argument
728 	return ts & ~((1ULL << shift) - 1);  in qfq_round_down()
731 /* return the pointer to the group with lowest index in the bitmap */
735 	int index = __ffs(bitmap);  in qfq_ffs()  local
736 	return &q->groups[index];  in qfq_ffs()
741 	return bitmap & ~((1UL << from) - 1);  in mask_from()
746  * First compute eligibility comparing grp->S, q->V,
752 	unsigned int state = qfq_gt(grp->S, q->V);  in qfq_calc_state()
753 	unsigned long mask = mask_from(q->bitmaps[ER], grp->index);  in qfq_calc_state()
758 		if (qfq_gt(grp->F, next->F))  in qfq_calc_state()
768  *	q->bitmaps[dst] |= q->bitmaps[src] & mask;
769  *	q->bitmaps[src] &= ~mask;
775 	q->bitmaps[dst] |= q->bitmaps[src] & mask;  in qfq_move_groups()
776 	q->bitmaps[src] &= ~mask;  in qfq_move_groups()
779 static void qfq_unblock_groups(struct qfq_sched *q, int index, u64 old_F)  in qfq_unblock_groups()  argument
781 	unsigned long mask = mask_from(q->bitmaps[ER], index + 1);  in qfq_unblock_groups()
786 		if (!qfq_gt(next->F, old_F))  in qfq_unblock_groups()
790 	mask = (1UL << index) - 1;  in qfq_unblock_groups()
798 	old_V ^= q->V;
799 	old_V >>= q->min_slot_shift;
807 	unsigned long vslot = q->V >> q->min_slot_shift;  in qfq_make_eligible()
808 	unsigned long old_vslot = q->oldV >> q->min_slot_shift;  in qfq_make_eligible()
817 			mask = (1UL << last_flip_pos) - 1;  in qfq_make_eligible()
825  * The index of the slot in which the input aggregate agg is to be
826  * inserted must not be higher than QFQ_MAX_SLOTS-2. There is a '-2'
827  * and not a '-1' because the start time of the group may be moved
829  * this would cause non-empty slots to be right-shifted by one
832  * QFQ+ fully satisfies this bound to the slot index if the parameters
838  * the timestamps of agg are low enough that the slot index is never
843  * As for the first event, i.e., an out-of-order service, the
844  * upper bound to the slot index guaranteed by QFQ+ grows to
849  * The following function deals with this problem by backward-shifting
851  * index is never higher than QFQ_MAX_SLOTS-2. This backward-shift may
853  * worst-case guarantees of these aggregates are not violated.  In
854  * fact, in case of no out-of-order service, the timestamps of agg
855  * would have been even lower than they are after the backward shift,
857  * the slot index, and 2 < QFQ_MAX_SLOTS-2. Hence the aggregates whose
858  * service is postponed because of the backward-shift would have
861  * The other event that may cause the slot index to be higher than 2
871  * may cause the above bound to the slot index to be violated for some
875  * quite complex, the above-discussed capping of the slot index is
882 	u64 slot = (roundedS - grp->S) >> grp->slot_shift;  in qfq_slot_insert()
883 	unsigned int i; /* slot index in the bucket list */  in qfq_slot_insert()
885 	if (unlikely(slot > QFQ_MAX_SLOTS - 2)) {  in qfq_slot_insert()
886 		u64 deltaS = roundedS - grp->S -  in qfq_slot_insert()
887 			((u64)(QFQ_MAX_SLOTS - 2)<<grp->slot_shift);  in qfq_slot_insert()
888 		agg->S -= deltaS;  in qfq_slot_insert()
889 		agg->F -= deltaS;  in qfq_slot_insert()
890 		slot = QFQ_MAX_SLOTS - 2;  in qfq_slot_insert()
893 	i = (grp->front + slot) % QFQ_MAX_SLOTS;  in qfq_slot_insert()
895 	hlist_add_head(&agg->next, &grp->slots[i]);  in qfq_slot_insert()
896 	__set_bit(slot, &grp->full_slots);  in qfq_slot_insert()
902 	return hlist_entry(grp->slots[grp->front].first,  in qfq_slot_head()
914 	hlist_del(&agg->next);  in qfq_front_slot_remove()
915 	if (hlist_empty(&grp->slots[grp->front]))  in qfq_front_slot_remove()
916 		__clear_bit(0, &grp->full_slots);  in qfq_front_slot_remove()
920  * Returns the first aggregate in the first non-empty bucket of the
921  * group. As a side effect, adjusts the bucket list so the first
922  * non-empty bucket is at position 0 in full_slots.
929 		 grp->index, grp->full_slots);  in qfq_slot_scan()
931 	if (grp->full_slots == 0)  in qfq_slot_scan()
934 	i = __ffs(grp->full_slots);  /* zero based */  in qfq_slot_scan()
936 		grp->front = (grp->front + i) % QFQ_MAX_SLOTS;  in qfq_slot_scan()
937 		grp->full_slots >>= i;  in qfq_slot_scan()
944  * adjust the bucket list. When the start time of a group decreases,
945  * we move the index down (modulo QFQ_MAX_SLOTS) so we don't need to
947  * because we use ffs() to find the first non-empty slot.
948  * This covers decreases in the group's start time, but what about
954 	unsigned int i = (grp->S - roundedS) >> grp->slot_shift;  in qfq_slot_rotate()
956 	grp->full_slots <<= i;  in qfq_slot_rotate()
957 	grp->front = (grp->front - i) % QFQ_MAX_SLOTS;  in qfq_slot_rotate()
965 	ineligible = q->bitmaps[IR] | q->bitmaps[IB];  in qfq_update_eligible()
967 		if (!q->bitmaps[ER]) {  in qfq_update_eligible()
969 			if (qfq_gt(grp->S, q->V))  in qfq_update_eligible()
970 				q->V = grp->S;  in qfq_update_eligible()
980 	struct sk_buff *skb = qdisc_dequeue_peeked(cl->qdisc);  in agg_dequeue()
985 	cl->deficit -= (int) len;  in agg_dequeue()
987 	if (cl->qdisc->q.qlen == 0) /* no more packets, remove from list */  in agg_dequeue()
988 		list_del(&cl->alist);  in agg_dequeue()
989 	else if (cl->deficit < qdisc_pkt_len(cl->qdisc->ops->peek(cl->qdisc))) {  in agg_dequeue()
990 		cl->deficit += agg->lmax;  in agg_dequeue()
991 		list_move_tail(&cl->alist, &agg->active);  in agg_dequeue()
1003 	*cl = list_first_entry(&agg->active, struct qfq_class, alist);  in qfq_peek_skb()
1004 	skb = (*cl)->qdisc->ops->peek((*cl)->qdisc);  in qfq_peek_skb()
1006 		qdisc_warn_nonwc("qfq_dequeue", (*cl)->qdisc);  in qfq_peek_skb()
1019 	 * agg->initial_budget - agg->budget > agg->bugdetmax  in charge_actual_service()
1021 	u32 service_received = min(agg->budgetmax,  in charge_actual_service()
1022 				   agg->initial_budget - agg->budget);  in charge_actual_service()
1024 	agg->F = agg->S + (u64)service_received * agg->inv_w;  in charge_actual_service()
1027 /* Assign a reasonable start time for a new aggregate in group i.
1035  * set S to the F_j of the first group j which would be blocking us.
1037  * otherwise our group i would still be blocked.
1043 	int slot_shift = agg->grp->slot_shift;  in qfq_update_start()
1045 	roundedF = qfq_round_down(agg->F, slot_shift);  in qfq_update_start()
1046 	limit = qfq_round_down(q->V, slot_shift) + (1ULL << slot_shift);  in qfq_update_start()
1048 	if (!qfq_gt(agg->F, q->V) || qfq_gt(roundedF, limit)) {  in qfq_update_start()
1050 		mask = mask_from(q->bitmaps[ER], agg->grp->index);  in qfq_update_start()
1053 			if (qfq_gt(roundedF, next->F)) {  in qfq_update_start()
1054 				if (qfq_gt(limit, next->F))  in qfq_update_start()
1055 					agg->S = next->F;  in qfq_update_start()
1057 					agg->S = limit;  in qfq_update_start()
1061 		agg->S = q->V;  in qfq_update_start()
1063 		agg->S = agg->F;  in qfq_update_start()
1067  * service.  In particular, assign to agg->F its maximum possible
1078 		agg->S = agg->F;  in qfq_update_agg_ts()
1080 	agg->F = agg->S + (u64)agg->budgetmax * agg->inv_w;  in qfq_update_agg_ts()
1088 	struct qfq_aggregate *in_serv_agg = q->in_serv_agg;  in qfq_dequeue()
1091 	/* next-packet len, 0 means no more active classes in in-service agg */  in qfq_dequeue()
1097 	if (!list_empty(&in_serv_agg->active))  in qfq_dequeue()
1101 	 * If there are no active classes in the in-service aggregate,  in qfq_dequeue()
1105 	if (len == 0 || in_serv_agg->budget < len) {  in qfq_dequeue()
1109 		in_serv_agg->initial_budget = in_serv_agg->budget =  in qfq_dequeue()
1110 			in_serv_agg->budgetmax;  in qfq_dequeue()
1112 		if (!list_empty(&in_serv_agg->active)) {  in qfq_dequeue()
1118 			 * just keep it as the in-service one. This  in qfq_dequeue()
1125 		} else if (sch->q.qlen == 0) { /* no aggregate to serve */  in qfq_dequeue()
1126 			q->in_serv_agg = NULL;  in qfq_dequeue()
1134 		in_serv_agg = q->in_serv_agg = qfq_choose_next_agg(q);  in qfq_dequeue()
1140 	sch->q.qlen--;  in qfq_dequeue()
1145 		sch->q.qlen++;  in qfq_dequeue()
1156 	if (unlikely(in_serv_agg->budget < len))  in qfq_dequeue()
1157 		in_serv_agg->budget = 0;  in qfq_dequeue()
1159 		in_serv_agg->budget -= len;  in qfq_dequeue()
1161 	q->V += (u64)len * q->iwsum;  in qfq_dequeue()
1163 		 len, (unsigned long long) in_serv_agg->F,  in qfq_dequeue()
1164 		 (unsigned long long) q->V);  in qfq_dequeue()
1176 	q->oldV = q->V;  in qfq_choose_next_agg()
1178 	if (!q->bitmaps[ER])  in qfq_choose_next_agg()
1181 	grp = qfq_ffs(q, q->bitmaps[ER]);  in qfq_choose_next_agg()
1182 	old_F = grp->F;  in qfq_choose_next_agg()
1191 	if (new_front_agg == NULL) /* group is now inactive, remove from ER */  in qfq_choose_next_agg()
1192 		__clear_bit(grp->index, &q->bitmaps[ER]);  in qfq_choose_next_agg()
1194 		u64 roundedS = qfq_round_down(new_front_agg->S,  in qfq_choose_next_agg()
1195 					      grp->slot_shift);  in qfq_choose_next_agg()
1198 		if (grp->S == roundedS)  in qfq_choose_next_agg()
1200 		grp->S = roundedS;  in qfq_choose_next_agg()
1201 		grp->F = roundedS + (2ULL << grp->slot_shift);  in qfq_choose_next_agg()
1202 		__clear_bit(grp->index, &q->bitmaps[ER]);  in qfq_choose_next_agg()
1204 		__set_bit(grp->index, &q->bitmaps[s]);  in qfq_choose_next_agg()
1207 	qfq_unblock_groups(q, grp->index, old_F);  in qfq_choose_next_agg()
1229 	pr_debug("qfq_enqueue: cl = %x\n", cl->common.classid);  in qfq_enqueue()
1231 	if (unlikely(cl->agg->lmax < len)) {  in qfq_enqueue()
1233 			 cl->agg->lmax, len, cl->common.classid);  in qfq_enqueue()
1234 		err = qfq_change_agg(sch, cl, cl->agg->class_weight, len);  in qfq_enqueue()
1236 			cl->qstats.drops++;  in qfq_enqueue()
1241 	gso_segs = skb_is_gso(skb) ? skb_shinfo(skb)->gso_segs : 1;  in qfq_enqueue()
1242 	first = !cl->qdisc->q.qlen;  in qfq_enqueue()
1243 	err = qdisc_enqueue(skb, cl->qdisc, to_free);  in qfq_enqueue()
1247 			cl->qstats.drops++;  in qfq_enqueue()
1253 	_bstats_update(&cl->bstats, len, gso_segs);  in qfq_enqueue()
1254 	sch->qstats.backlog += len;  in qfq_enqueue()
1255 	++sch->q.qlen;  in qfq_enqueue()
1257 	agg = cl->agg;  in qfq_enqueue()
1260 		if (unlikely(skb == cl->qdisc->ops->peek(cl->qdisc)) &&  in qfq_enqueue()
1261 		    list_first_entry(&agg->active, struct qfq_class, alist)  in qfq_enqueue()
1262 		    == cl && cl->deficit < len)  in qfq_enqueue()
1263 			list_move_tail(&cl->alist, &agg->active);  in qfq_enqueue()
1269 	cl->deficit = agg->lmax;  in qfq_enqueue()
1270 	list_add_tail(&cl->alist, &agg->active);  in qfq_enqueue()
1272 	if (list_first_entry(&agg->active, struct qfq_class, alist) != cl ||  in qfq_enqueue()
1273 	    q->in_serv_agg == agg)  in qfq_enqueue()
1274 		return err; /* non-empty or in service, nothing else to do */  in qfq_enqueue()
1286 	struct qfq_group *grp = agg->grp;  in qfq_schedule_agg()
1290 	roundedS = qfq_round_down(agg->S, grp->slot_shift);  in qfq_schedule_agg()
1294 	 * If agg->S >= grp->S we don't need to adjust the  in qfq_schedule_agg()
1296 	 * Otherwise grp->S is decreasing, we must make room  in qfq_schedule_agg()
1297 	 * in the bucket list, and also recompute the group state.  in qfq_schedule_agg()
1298 	 * Finally, if there were no flows in this group and nobody  in qfq_schedule_agg()
1301 	if (grp->full_slots) {  in qfq_schedule_agg()
1302 		if (!qfq_gt(grp->S, agg->S))  in qfq_schedule_agg()
1305 		/* create a slot for this agg->S */  in qfq_schedule_agg()
1307 		/* group was surely ineligible, remove */  in qfq_schedule_agg()
1308 		__clear_bit(grp->index, &q->bitmaps[IR]);  in qfq_schedule_agg()
1309 		__clear_bit(grp->index, &q->bitmaps[IB]);  in qfq_schedule_agg()
1310 	} else if (!q->bitmaps[ER] && qfq_gt(roundedS, q->V) &&  in qfq_schedule_agg()
1311 		   q->in_serv_agg == NULL)  in qfq_schedule_agg()
1312 		q->V = roundedS;  in qfq_schedule_agg()
1314 	grp->S = roundedS;  in qfq_schedule_agg()
1315 	grp->F = roundedS + (2ULL << grp->slot_shift);  in qfq_schedule_agg()
1317 	__set_bit(grp->index, &q->bitmaps[s]);  in qfq_schedule_agg()
1320 		 s, q->bitmaps[s],  in qfq_schedule_agg()
1321 		 (unsigned long long) agg->S,  in qfq_schedule_agg()
1322 		 (unsigned long long) agg->F,  in qfq_schedule_agg()
1323 		 (unsigned long long) q->V);  in qfq_schedule_agg()
1334 	agg->initial_budget = agg->budget = agg->budgetmax; /* recharge budg. */  in qfq_activate_agg()
1337 	if (q->in_serv_agg == NULL) { /* no aggr. in service or scheduled */  in qfq_activate_agg()
1338 		q->in_serv_agg = agg; /* start serving this aggregate */  in qfq_activate_agg()
1340 		q->oldV = q->V = agg->S;  in qfq_activate_agg()
1341 	} else if (agg != q->in_serv_agg)  in qfq_activate_agg()
1351 	roundedS = qfq_round_down(agg->S, grp->slot_shift);  in qfq_slot_remove()
1352 	offset = (roundedS - grp->S) >> grp->slot_shift;  in qfq_slot_remove()
1354 	i = (grp->front + offset) % QFQ_MAX_SLOTS;  in qfq_slot_remove()
1356 	hlist_del(&agg->next);  in qfq_slot_remove()
1357 	if (hlist_empty(&grp->slots[i]))  in qfq_slot_remove()
1358 		__clear_bit(offset, &grp->full_slots);  in qfq_slot_remove()
1370 	struct qfq_group *grp = agg->grp;  in qfq_deactivate_agg()
1375 	if (agg == q->in_serv_agg) {  in qfq_deactivate_agg()
1377 		q->in_serv_agg = qfq_choose_next_agg(q);  in qfq_deactivate_agg()
1381 	agg->F = agg->S;  in qfq_deactivate_agg()
1384 	if (!grp->full_slots) {  in qfq_deactivate_agg()
1385 		__clear_bit(grp->index, &q->bitmaps[IR]);  in qfq_deactivate_agg()
1386 		__clear_bit(grp->index, &q->bitmaps[EB]);  in qfq_deactivate_agg()
1387 		__clear_bit(grp->index, &q->bitmaps[IB]);  in qfq_deactivate_agg()
1389 		if (test_bit(grp->index, &q->bitmaps[ER]) &&  in qfq_deactivate_agg()
1390 		    !(q->bitmaps[ER] & ~((1UL << grp->index) - 1))) {  in qfq_deactivate_agg()
1391 			mask = q->bitmaps[ER] & ((1UL << grp->index) - 1);  in qfq_deactivate_agg()
1393 				mask = ~((1UL << __fls(mask)) - 1);  in qfq_deactivate_agg()
1399 		__clear_bit(grp->index, &q->bitmaps[ER]);  in qfq_deactivate_agg()
1400 	} else if (hlist_empty(&grp->slots[grp->front])) {  in qfq_deactivate_agg()
1402 		roundedS = qfq_round_down(agg->S, grp->slot_shift);  in qfq_deactivate_agg()
1403 		if (grp->S != roundedS) {  in qfq_deactivate_agg()
1404 			__clear_bit(grp->index, &q->bitmaps[ER]);  in qfq_deactivate_agg()
1405 			__clear_bit(grp->index, &q->bitmaps[IR]);  in qfq_deactivate_agg()
1406 			__clear_bit(grp->index, &q->bitmaps[EB]);  in qfq_deactivate_agg()
1407 			__clear_bit(grp->index, &q->bitmaps[IB]);  in qfq_deactivate_agg()
1408 			grp->S = roundedS;  in qfq_deactivate_agg()
1409 			grp->F = roundedS + (2ULL << grp->slot_shift);  in qfq_deactivate_agg()
1411 			__set_bit(grp->index, &q->bitmaps[s]);  in qfq_deactivate_agg()
1432 	err = tcf_block_get(&q->block, &q->filter_list, sch, extack);  in qfq_init_qdisc()
1436 	err = qdisc_class_hash_init(&q->clhash);  in qfq_init_qdisc()
1440 	max_classes = min_t(u64, (u64)qdisc_dev(sch)->tx_queue_len + 1,  in qfq_init_qdisc()
1444 	q->max_agg_classes = 1<<max_cl_shift;  in qfq_init_qdisc()
1448 	q->min_slot_shift = FRAC_BITS + maxbudg_shift - QFQ_MAX_INDEX;  in qfq_init_qdisc()
1451 		grp = &q->groups[i];  in qfq_init_qdisc()
1452 		grp->index = i;  in qfq_init_qdisc()
1453 		grp->slot_shift = q->min_slot_shift + i;  in qfq_init_qdisc()
1455 			INIT_HLIST_HEAD(&grp->slots[j]);  in qfq_init_qdisc()
1458 	INIT_HLIST_HEAD(&q->nonfull_aggs);  in qfq_init_qdisc()
1469 	for (i = 0; i < q->clhash.hashsize; i++) {  in qfq_reset_qdisc()
1470 		hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) {  in qfq_reset_qdisc()
1471 			if (cl->qdisc->q.qlen > 0)  in qfq_reset_qdisc()
1474 			qdisc_reset(cl->qdisc);  in qfq_reset_qdisc()
1486 	tcf_block_put(q->block);  in qfq_destroy_qdisc()
1488 	for (i = 0; i < q->clhash.hashsize; i++) {  in qfq_destroy_qdisc()
1489 		hlist_for_each_entry_safe(cl, next, &q->clhash.hash[i],  in qfq_destroy_qdisc()
1494 	qdisc_class_hash_destroy(&q->clhash);  in qfq_destroy_qdisc()