Lines Matching +full:group +full:- +full:index +full:- +full:shift
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()
434 return -EINVAL; in qfq_change_class()
442 lmax == cl->agg->lmax && in qfq_change_class()
443 weight == cl->agg->class_weight) in qfq_change_class()
446 delta_w = weight - (cl ? cl->agg->class_weight : 0); in qfq_change_class()
448 if (q->wsum + delta_w > QFQ_MAX_WSUM) { in qfq_change_class()
451 delta_w, q->wsum); in qfq_change_class()
452 return -EINVAL; in qfq_change_class()
457 err = gen_replace_estimator(&cl->bstats, NULL, in qfq_change_class()
458 &cl->rate_est, in qfq_change_class()
472 return -ENOBUFS; in qfq_change_class()
474 gnet_stats_basic_sync_init(&cl->bstats); in qfq_change_class()
475 cl->common.classid = classid; in qfq_change_class()
476 cl->deficit = lmax; in qfq_change_class()
478 cl->qdisc = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops, in qfq_change_class()
480 if (cl->qdisc == NULL) in qfq_change_class()
481 cl->qdisc = &noop_qdisc; in qfq_change_class()
484 err = gen_new_estimator(&cl->bstats, NULL, in qfq_change_class()
485 &cl->rate_est, in qfq_change_class()
493 if (cl->qdisc != &noop_qdisc) in qfq_change_class()
494 qdisc_hash_add(cl->qdisc, true); in qfq_change_class()
503 err = -ENOBUFS; in qfq_change_class()
504 gen_kill_estimator(&cl->rate_est); in qfq_change_class()
513 qdisc_class_hash_insert(&q->clhash, &cl->common); in qfq_change_class()
516 qdisc_class_hash_grow(sch, &q->clhash); in qfq_change_class()
522 qdisc_put(cl->qdisc); in qfq_change_class()
532 gen_kill_estimator(&cl->rate_est); in qfq_destroy_class()
533 qdisc_put(cl->qdisc); in qfq_destroy_class()
543 if (qdisc_class_in_use(&cl->common)) { in qfq_delete_class()
545 return -EBUSY; in qfq_delete_class()
550 qdisc_purge_queue(cl->qdisc); in qfq_delete_class()
551 qdisc_class_hash_remove(&q->clhash, &cl->common); in qfq_delete_class()
572 return q->block; in qfq_tcf_block()
581 qdisc_class_get(&cl->common); in qfq_bind_tcf()
590 qdisc_class_put(&cl->common); in qfq_unbind_tcf()
600 new = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops, in qfq_graft_class()
601 cl->common.classid, NULL); in qfq_graft_class()
606 *old = qdisc_replace(sch, new, &cl->qdisc); in qfq_graft_class()
614 return cl->qdisc; in qfq_class_leaf()
623 tcm->tcm_parent = TC_H_ROOT; in qfq_dump_class()
624 tcm->tcm_handle = cl->common.classid; in qfq_dump_class()
625 tcm->tcm_info = cl->qdisc->handle; in qfq_dump_class()
630 if (nla_put_u32(skb, TCA_QFQ_WEIGHT, cl->agg->class_weight) || in qfq_dump_class()
631 nla_put_u32(skb, TCA_QFQ_LMAX, cl->agg->lmax)) in qfq_dump_class()
637 return -EMSGSIZE; in qfq_dump_class()
648 xstats.weight = cl->agg->class_weight; in qfq_dump_class_stats()
649 xstats.lmax = cl->agg->lmax; in qfq_dump_class_stats()
651 if (gnet_stats_copy_basic(d, NULL, &cl->bstats, true) < 0 || in qfq_dump_class_stats()
652 gnet_stats_copy_rate_est(d, &cl->rate_est) < 0 || in qfq_dump_class_stats()
653 qdisc_qstats_copy(d, cl->qdisc) < 0) in qfq_dump_class_stats()
654 return -1; in qfq_dump_class_stats()
665 if (arg->stop) in qfq_walk()
668 for (i = 0; i < q->clhash.hashsize; i++) { in qfq_walk()
669 hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) { in qfq_walk()
685 if (TC_H_MAJ(skb->priority ^ sch->handle) == 0) { in qfq_classify()
686 pr_debug("qfq_classify: found %d\n", skb->priority); in qfq_classify()
687 cl = qfq_find_class(sch, skb->priority); in qfq_classify()
693 fl = rcu_dereference_bh(q->filter_list); in qfq_classify()
719 return (s64)(a - b) > 0; in qfq_gt()
723 static inline u64 qfq_round_down(u64 ts, unsigned int shift) in qfq_round_down() argument
725 return ts & ~((1ULL << shift) - 1); in qfq_round_down()
728 /* return the pointer to the group with lowest index in the bitmap */
732 int index = __ffs(bitmap); in qfq_ffs() local
733 return &q->groups[index]; in qfq_ffs()
738 return bitmap & ~((1UL << from) - 1); in mask_from()
743 * First compute eligibility comparing grp->S, q->V,
749 unsigned int state = qfq_gt(grp->S, q->V); in qfq_calc_state()
750 unsigned long mask = mask_from(q->bitmaps[ER], grp->index); in qfq_calc_state()
755 if (qfq_gt(grp->F, next->F)) in qfq_calc_state()
765 * q->bitmaps[dst] |= q->bitmaps[src] & mask;
766 * q->bitmaps[src] &= ~mask;
772 q->bitmaps[dst] |= q->bitmaps[src] & mask; in qfq_move_groups()
773 q->bitmaps[src] &= ~mask; in qfq_move_groups()
776 static void qfq_unblock_groups(struct qfq_sched *q, int index, u64 old_F) in qfq_unblock_groups() argument
778 unsigned long mask = mask_from(q->bitmaps[ER], index + 1); in qfq_unblock_groups()
783 if (!qfq_gt(next->F, old_F)) in qfq_unblock_groups()
787 mask = (1UL << index) - 1; in qfq_unblock_groups()
795 old_V ^= q->V;
796 old_V >>= q->min_slot_shift;
804 unsigned long vslot = q->V >> q->min_slot_shift; in qfq_make_eligible()
805 unsigned long old_vslot = q->oldV >> q->min_slot_shift; in qfq_make_eligible()
814 mask = (1UL << last_flip_pos) - 1; in qfq_make_eligible()
822 * The index of the slot in which the input aggregate agg is to be
823 * inserted must not be higher than QFQ_MAX_SLOTS-2. There is a '-2'
824 * and not a '-1' because the start time of the group may be moved
826 * this would cause non-empty slots to be right-shifted by one
829 * QFQ+ fully satisfies this bound to the slot index if the parameters
835 * the timestamps of agg are low enough that the slot index is never
840 * As for the first event, i.e., an out-of-order service, the
841 * upper bound to the slot index guaranteed by QFQ+ grows to
846 * The following function deals with this problem by backward-shifting
848 * index is never higher than QFQ_MAX_SLOTS-2. This backward-shift may
850 * worst-case guarantees of these aggregates are not violated. In
851 * fact, in case of no out-of-order service, the timestamps of agg
852 * would have been even lower than they are after the backward shift,
854 * the slot index, and 2 < QFQ_MAX_SLOTS-2. Hence the aggregates whose
855 * service is postponed because of the backward-shift would have
858 * The other event that may cause the slot index to be higher than 2
868 * may cause the above bound to the slot index to be violated for some
872 * quite complex, the above-discussed capping of the slot index is
879 u64 slot = (roundedS - grp->S) >> grp->slot_shift; in qfq_slot_insert()
880 unsigned int i; /* slot index in the bucket list */ in qfq_slot_insert()
882 if (unlikely(slot > QFQ_MAX_SLOTS - 2)) { in qfq_slot_insert()
883 u64 deltaS = roundedS - grp->S - in qfq_slot_insert()
884 ((u64)(QFQ_MAX_SLOTS - 2)<<grp->slot_shift); in qfq_slot_insert()
885 agg->S -= deltaS; in qfq_slot_insert()
886 agg->F -= deltaS; in qfq_slot_insert()
887 slot = QFQ_MAX_SLOTS - 2; in qfq_slot_insert()
890 i = (grp->front + slot) % QFQ_MAX_SLOTS; in qfq_slot_insert()
892 hlist_add_head(&agg->next, &grp->slots[i]); in qfq_slot_insert()
893 __set_bit(slot, &grp->full_slots); in qfq_slot_insert()
899 return hlist_entry(grp->slots[grp->front].first, in qfq_slot_head()
911 hlist_del(&agg->next); in qfq_front_slot_remove()
912 if (hlist_empty(&grp->slots[grp->front])) in qfq_front_slot_remove()
913 __clear_bit(0, &grp->full_slots); in qfq_front_slot_remove()
917 * Returns the first aggregate in the first non-empty bucket of the
918 * group. As a side effect, adjusts the bucket list so the first
919 * non-empty bucket is at position 0 in full_slots.
926 grp->index, grp->full_slots); in qfq_slot_scan()
928 if (grp->full_slots == 0) in qfq_slot_scan()
931 i = __ffs(grp->full_slots); /* zero based */ in qfq_slot_scan()
933 grp->front = (grp->front + i) % QFQ_MAX_SLOTS; in qfq_slot_scan()
934 grp->full_slots >>= i; in qfq_slot_scan()
941 * adjust the bucket list. When the start time of a group decreases,
942 * we move the index down (modulo QFQ_MAX_SLOTS) so we don't need to
944 * because we use ffs() to find the first non-empty slot.
945 * This covers decreases in the group's start time, but what about
951 unsigned int i = (grp->S - roundedS) >> grp->slot_shift; in qfq_slot_rotate()
953 grp->full_slots <<= i; in qfq_slot_rotate()
954 grp->front = (grp->front - i) % QFQ_MAX_SLOTS; in qfq_slot_rotate()
962 ineligible = q->bitmaps[IR] | q->bitmaps[IB]; in qfq_update_eligible()
964 if (!q->bitmaps[ER]) { in qfq_update_eligible()
966 if (qfq_gt(grp->S, q->V)) in qfq_update_eligible()
967 q->V = grp->S; in qfq_update_eligible()
977 struct sk_buff *skb = qdisc_dequeue_peeked(cl->qdisc); in agg_dequeue()
982 cl->deficit -= (int) len; in agg_dequeue()
984 if (cl->qdisc->q.qlen == 0) /* no more packets, remove from list */ in agg_dequeue()
985 list_del(&cl->alist); in agg_dequeue()
986 else if (cl->deficit < qdisc_pkt_len(cl->qdisc->ops->peek(cl->qdisc))) { in agg_dequeue()
987 cl->deficit += agg->lmax; in agg_dequeue()
988 list_move_tail(&cl->alist, &agg->active); in agg_dequeue()
1000 *cl = list_first_entry(&agg->active, struct qfq_class, alist); in qfq_peek_skb()
1001 skb = (*cl)->qdisc->ops->peek((*cl)->qdisc); in qfq_peek_skb()
1003 qdisc_warn_nonwc("qfq_dequeue", (*cl)->qdisc); in qfq_peek_skb()
1016 * agg->initial_budget - agg->budget > agg->bugdetmax in charge_actual_service()
1018 u32 service_received = min(agg->budgetmax, in charge_actual_service()
1019 agg->initial_budget - agg->budget); in charge_actual_service()
1021 agg->F = agg->S + (u64)service_received * agg->inv_w; in charge_actual_service()
1024 /* Assign a reasonable start time for a new aggregate in group i.
1032 * set S to the F_j of the first group j which would be blocking us.
1034 * otherwise our group i would still be blocked.
1040 int slot_shift = agg->grp->slot_shift; in qfq_update_start()
1042 roundedF = qfq_round_down(agg->F, slot_shift); in qfq_update_start()
1043 limit = qfq_round_down(q->V, slot_shift) + (1ULL << slot_shift); in qfq_update_start()
1045 if (!qfq_gt(agg->F, q->V) || qfq_gt(roundedF, limit)) { in qfq_update_start()
1047 mask = mask_from(q->bitmaps[ER], agg->grp->index); in qfq_update_start()
1050 if (qfq_gt(roundedF, next->F)) { in qfq_update_start()
1051 if (qfq_gt(limit, next->F)) in qfq_update_start()
1052 agg->S = next->F; in qfq_update_start()
1054 agg->S = limit; in qfq_update_start()
1058 agg->S = q->V; in qfq_update_start()
1060 agg->S = agg->F; in qfq_update_start()
1064 * service. In particular, assign to agg->F its maximum possible
1075 agg->S = agg->F; in qfq_update_agg_ts()
1077 agg->F = agg->S + (u64)agg->budgetmax * agg->inv_w; in qfq_update_agg_ts()
1085 struct qfq_aggregate *in_serv_agg = q->in_serv_agg; in qfq_dequeue()
1088 /* next-packet len, 0 means no more active classes in in-service agg */ in qfq_dequeue()
1094 if (!list_empty(&in_serv_agg->active)) in qfq_dequeue()
1098 * If there are no active classes in the in-service aggregate, in qfq_dequeue()
1102 if (len == 0 || in_serv_agg->budget < len) { in qfq_dequeue()
1106 in_serv_agg->initial_budget = in_serv_agg->budget = in qfq_dequeue()
1107 in_serv_agg->budgetmax; in qfq_dequeue()
1109 if (!list_empty(&in_serv_agg->active)) { in qfq_dequeue()
1115 * just keep it as the in-service one. This in qfq_dequeue()
1122 } else if (sch->q.qlen == 0) { /* no aggregate to serve */ in qfq_dequeue()
1123 q->in_serv_agg = NULL; in qfq_dequeue()
1131 in_serv_agg = q->in_serv_agg = qfq_choose_next_agg(q); in qfq_dequeue()
1137 sch->q.qlen--; in qfq_dequeue()
1142 sch->q.qlen++; in qfq_dequeue()
1153 if (unlikely(in_serv_agg->budget < len)) in qfq_dequeue()
1154 in_serv_agg->budget = 0; in qfq_dequeue()
1156 in_serv_agg->budget -= len; in qfq_dequeue()
1158 q->V += (u64)len * q->iwsum; in qfq_dequeue()
1160 len, (unsigned long long) in_serv_agg->F, in qfq_dequeue()
1161 (unsigned long long) q->V); in qfq_dequeue()
1173 q->oldV = q->V; in qfq_choose_next_agg()
1175 if (!q->bitmaps[ER]) in qfq_choose_next_agg()
1178 grp = qfq_ffs(q, q->bitmaps[ER]); in qfq_choose_next_agg()
1179 old_F = grp->F; in qfq_choose_next_agg()
1188 if (new_front_agg == NULL) /* group is now inactive, remove from ER */ in qfq_choose_next_agg()
1189 __clear_bit(grp->index, &q->bitmaps[ER]); in qfq_choose_next_agg()
1191 u64 roundedS = qfq_round_down(new_front_agg->S, in qfq_choose_next_agg()
1192 grp->slot_shift); in qfq_choose_next_agg()
1195 if (grp->S == roundedS) in qfq_choose_next_agg()
1197 grp->S = roundedS; in qfq_choose_next_agg()
1198 grp->F = roundedS + (2ULL << grp->slot_shift); in qfq_choose_next_agg()
1199 __clear_bit(grp->index, &q->bitmaps[ER]); in qfq_choose_next_agg()
1201 __set_bit(grp->index, &q->bitmaps[s]); in qfq_choose_next_agg()
1204 qfq_unblock_groups(q, grp->index, old_F); in qfq_choose_next_agg()
1226 pr_debug("qfq_enqueue: cl = %x\n", cl->common.classid); in qfq_enqueue()
1228 if (unlikely(cl->agg->lmax < len)) { in qfq_enqueue()
1230 cl->agg->lmax, len, cl->common.classid); in qfq_enqueue()
1231 err = qfq_change_agg(sch, cl, cl->agg->class_weight, len); in qfq_enqueue()
1233 cl->qstats.drops++; in qfq_enqueue()
1238 gso_segs = skb_is_gso(skb) ? skb_shinfo(skb)->gso_segs : 1; in qfq_enqueue()
1239 first = !cl->qdisc->q.qlen; in qfq_enqueue()
1240 err = qdisc_enqueue(skb, cl->qdisc, to_free); in qfq_enqueue()
1244 cl->qstats.drops++; in qfq_enqueue()
1250 _bstats_update(&cl->bstats, len, gso_segs); in qfq_enqueue()
1251 sch->qstats.backlog += len; in qfq_enqueue()
1252 ++sch->q.qlen; in qfq_enqueue()
1254 agg = cl->agg; in qfq_enqueue()
1257 if (unlikely(skb == cl->qdisc->ops->peek(cl->qdisc)) && in qfq_enqueue()
1258 list_first_entry(&agg->active, struct qfq_class, alist) in qfq_enqueue()
1259 == cl && cl->deficit < len) in qfq_enqueue()
1260 list_move_tail(&cl->alist, &agg->active); in qfq_enqueue()
1266 cl->deficit = agg->lmax; in qfq_enqueue()
1267 list_add_tail(&cl->alist, &agg->active); in qfq_enqueue()
1269 if (list_first_entry(&agg->active, struct qfq_class, alist) != cl || in qfq_enqueue()
1270 q->in_serv_agg == agg) in qfq_enqueue()
1271 return err; /* non-empty or in service, nothing else to do */ in qfq_enqueue()
1283 struct qfq_group *grp = agg->grp; in qfq_schedule_agg()
1287 roundedS = qfq_round_down(agg->S, grp->slot_shift); in qfq_schedule_agg()
1291 * If agg->S >= grp->S we don't need to adjust the in qfq_schedule_agg()
1293 * Otherwise grp->S is decreasing, we must make room in qfq_schedule_agg()
1294 * in the bucket list, and also recompute the group state. in qfq_schedule_agg()
1295 * Finally, if there were no flows in this group and nobody in qfq_schedule_agg()
1298 if (grp->full_slots) { in qfq_schedule_agg()
1299 if (!qfq_gt(grp->S, agg->S)) in qfq_schedule_agg()
1302 /* create a slot for this agg->S */ in qfq_schedule_agg()
1304 /* group was surely ineligible, remove */ in qfq_schedule_agg()
1305 __clear_bit(grp->index, &q->bitmaps[IR]); in qfq_schedule_agg()
1306 __clear_bit(grp->index, &q->bitmaps[IB]); in qfq_schedule_agg()
1307 } else if (!q->bitmaps[ER] && qfq_gt(roundedS, q->V) && in qfq_schedule_agg()
1308 q->in_serv_agg == NULL) in qfq_schedule_agg()
1309 q->V = roundedS; in qfq_schedule_agg()
1311 grp->S = roundedS; in qfq_schedule_agg()
1312 grp->F = roundedS + (2ULL << grp->slot_shift); in qfq_schedule_agg()
1314 __set_bit(grp->index, &q->bitmaps[s]); in qfq_schedule_agg()
1317 s, q->bitmaps[s], in qfq_schedule_agg()
1318 (unsigned long long) agg->S, in qfq_schedule_agg()
1319 (unsigned long long) agg->F, in qfq_schedule_agg()
1320 (unsigned long long) q->V); in qfq_schedule_agg()
1331 agg->initial_budget = agg->budget = agg->budgetmax; /* recharge budg. */ in qfq_activate_agg()
1334 if (q->in_serv_agg == NULL) { /* no aggr. in service or scheduled */ in qfq_activate_agg()
1335 q->in_serv_agg = agg; /* start serving this aggregate */ in qfq_activate_agg()
1337 q->oldV = q->V = agg->S; in qfq_activate_agg()
1338 } else if (agg != q->in_serv_agg) in qfq_activate_agg()
1348 roundedS = qfq_round_down(agg->S, grp->slot_shift); in qfq_slot_remove()
1349 offset = (roundedS - grp->S) >> grp->slot_shift; in qfq_slot_remove()
1351 i = (grp->front + offset) % QFQ_MAX_SLOTS; in qfq_slot_remove()
1353 hlist_del(&agg->next); in qfq_slot_remove()
1354 if (hlist_empty(&grp->slots[i])) in qfq_slot_remove()
1355 __clear_bit(offset, &grp->full_slots); in qfq_slot_remove()
1367 struct qfq_group *grp = agg->grp; in qfq_deactivate_agg()
1372 if (agg == q->in_serv_agg) { in qfq_deactivate_agg()
1374 q->in_serv_agg = qfq_choose_next_agg(q); in qfq_deactivate_agg()
1378 agg->F = agg->S; in qfq_deactivate_agg()
1381 if (!grp->full_slots) { in qfq_deactivate_agg()
1382 __clear_bit(grp->index, &q->bitmaps[IR]); in qfq_deactivate_agg()
1383 __clear_bit(grp->index, &q->bitmaps[EB]); in qfq_deactivate_agg()
1384 __clear_bit(grp->index, &q->bitmaps[IB]); in qfq_deactivate_agg()
1386 if (test_bit(grp->index, &q->bitmaps[ER]) && in qfq_deactivate_agg()
1387 !(q->bitmaps[ER] & ~((1UL << grp->index) - 1))) { in qfq_deactivate_agg()
1388 mask = q->bitmaps[ER] & ((1UL << grp->index) - 1); in qfq_deactivate_agg()
1390 mask = ~((1UL << __fls(mask)) - 1); in qfq_deactivate_agg()
1396 __clear_bit(grp->index, &q->bitmaps[ER]); in qfq_deactivate_agg()
1397 } else if (hlist_empty(&grp->slots[grp->front])) { in qfq_deactivate_agg()
1399 roundedS = qfq_round_down(agg->S, grp->slot_shift); in qfq_deactivate_agg()
1400 if (grp->S != roundedS) { in qfq_deactivate_agg()
1401 __clear_bit(grp->index, &q->bitmaps[ER]); in qfq_deactivate_agg()
1402 __clear_bit(grp->index, &q->bitmaps[IR]); in qfq_deactivate_agg()
1403 __clear_bit(grp->index, &q->bitmaps[EB]); in qfq_deactivate_agg()
1404 __clear_bit(grp->index, &q->bitmaps[IB]); in qfq_deactivate_agg()
1405 grp->S = roundedS; in qfq_deactivate_agg()
1406 grp->F = roundedS + (2ULL << grp->slot_shift); in qfq_deactivate_agg()
1408 __set_bit(grp->index, &q->bitmaps[s]); in qfq_deactivate_agg()
1429 err = tcf_block_get(&q->block, &q->filter_list, sch, extack); in qfq_init_qdisc()
1433 err = qdisc_class_hash_init(&q->clhash); in qfq_init_qdisc()
1437 max_classes = min_t(u64, (u64)qdisc_dev(sch)->tx_queue_len + 1, in qfq_init_qdisc()
1441 q->max_agg_classes = 1<<max_cl_shift; in qfq_init_qdisc()
1445 q->min_slot_shift = FRAC_BITS + maxbudg_shift - QFQ_MAX_INDEX; in qfq_init_qdisc()
1448 grp = &q->groups[i]; in qfq_init_qdisc()
1449 grp->index = i; in qfq_init_qdisc()
1450 grp->slot_shift = q->min_slot_shift + i; in qfq_init_qdisc()
1452 INIT_HLIST_HEAD(&grp->slots[j]); in qfq_init_qdisc()
1455 INIT_HLIST_HEAD(&q->nonfull_aggs); in qfq_init_qdisc()
1466 for (i = 0; i < q->clhash.hashsize; i++) { in qfq_reset_qdisc()
1467 hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) { in qfq_reset_qdisc()
1468 if (cl->qdisc->q.qlen > 0) in qfq_reset_qdisc()
1471 qdisc_reset(cl->qdisc); in qfq_reset_qdisc()
1483 tcf_block_put(q->block); in qfq_destroy_qdisc()
1485 for (i = 0; i < q->clhash.hashsize; i++) { in qfq_destroy_qdisc()
1486 hlist_for_each_entry_safe(cl, next, &q->clhash.hash[i], in qfq_destroy_qdisc()
1491 qdisc_class_hash_destroy(&q->clhash); in qfq_destroy_qdisc()