Lines Matching +full:group +full:- +full:index +full:- +full:shift
1 /*-
2 * SPDX-License-Identifier: BSD-2-Clause
73 * We use the base-0 version __fls() to match the description in
89 return fls(word) - 1; in __fls()
98 D("bad index %d", ix); in test_bit()
104 D("bad index %d", ix); in __set_bit()
110 D("bad index %d", ix); in __clear_bit()
125 /*-------------------------------------------*/
133 QFQ_MAX_INDEX is the maximum index allowed for a group. We need
134 one bit per index.
140 ^.__grp->index = 0
141 *.__grp->slot_shift
145 The max group index corresponds to Lmax/w_min, where
148 we can derive the shift corresponding to each group.
158 The per-scheduler-instance data contain all the data structures
164 * inside a group. This is approx lmax/lmin + 5.
169 * Shifts used for class<->group mapping. Class weights are
171 * group with the smallest index that can support the L_i / r_i
174 * grp->index is the index of the group; and grp->slot_shift
175 * is the shift for the corresponding (scaled) sigma_i.
177 * When computing the group index, we do (len<<FP_SHIFT)/weight,
192 #define QFQ_MIN_SLOT_SHIFT (FRAC_BITS + QFQ_MTU_SHIFT - QFQ_MAX_INDEX)
195 * Possible group states, also indexes for the bitmaps array in
211 /* group we belong to. In principle we would need the index,
213 * directly, only the group.
222 /* Group descriptor, see the paper for details.
226 uint64_t S, F; /* group timestamps (approx). */
227 unsigned int slot_shift; /* Slot shift. */
228 unsigned int index; /* Group index. */ member
229 unsigned int front; /* Index of the front slot. */
230 bitmap full_slots; /* non-empty slots */
244 bitmap bitmaps[QFQ_MAX_STATE]; /* Group bitmaps. */
248 /*---- support functions ----------------------------*/
253 return (int64_t)(a - b) > 0; in qfq_gt()
257 static inline uint64_t qfq_round_down(uint64_t ts, unsigned int shift) in qfq_round_down() argument
259 return ts & ~((1ULL << shift) - 1); in qfq_round_down()
262 /* return the pointer to the group with lowest index in the bitmap */
266 int index = ffs(bitmap) - 1; // zero-based in qfq_ffs() local
267 return &q->groups[index]; in qfq_ffs()
271 * Calculate a flow index, given its weight and maximum packet length.
272 * index = log_2(maxlen/weight) but we need to apply the scaling.
279 int index = 0; in qfq_calc_index() local
285 index = __fls(size_map) + 1; // basically a log_2() in qfq_calc_index()
286 index -= !(slot_size - (1ULL << (index + QFQ_MIN_SLOT_SHIFT - 1))); in qfq_calc_index()
288 if (index < 0) in qfq_calc_index()
289 index = 0; in qfq_calc_index()
292 ND("W = %d, L = %d, I = %d\n", ONE_FP/inv_w, maxlen, index); in qfq_calc_index()
293 return index; in qfq_calc_index()
295 /*---- end support functions ----*/
297 /*-------- API calls --------------------------------*/
304 struct qfq_sched *q = (struct qfq_sched *)(_q->_si + 1); in qfq_new_queue()
312 w = _q->fs->fs.par[0]; in qfq_new_queue()
313 cl->lmax = _q->fs->fs.par[1]; in qfq_new_queue()
318 cl->inv_w = ONE_FP/w; in qfq_new_queue()
319 w = ONE_FP/cl->inv_w; in qfq_new_queue()
320 if (q->wsum + w > QFQ_MAX_WSUM) in qfq_new_queue()
323 i = qfq_calc_index(cl->inv_w, cl->lmax); in qfq_new_queue()
324 cl->grp = &q->groups[i]; in qfq_new_queue()
325 q->wsum += w; in qfq_new_queue()
326 q->iwsum = ONE_FP / q->wsum; /* XXX note theory */ in qfq_new_queue()
327 // XXX cl->S = q->V; ? in qfq_new_queue()
335 struct qfq_sched *q = (struct qfq_sched *)(_q->_si + 1); in qfq_free_queue()
337 if (cl->inv_w) { in qfq_free_queue()
338 q->wsum -= ONE_FP/cl->inv_w; in qfq_free_queue()
339 if (q->wsum != 0) in qfq_free_queue()
340 q->iwsum = ONE_FP / q->wsum; in qfq_free_queue()
341 cl->inv_w = 0; /* reset weight to avoid run twice */ in qfq_free_queue()
350 return bitmap & ~((1UL << from) - 1); in mask_from()
355 * First compute eligibility comparing grp->S, q->V,
362 unsigned int state = qfq_gt(grp->S, q->V); in qfq_calc_state()
363 unsigned long mask = mask_from(q->bitmaps[ER], grp->index); in qfq_calc_state()
368 if (qfq_gt(grp->F, next->F)) in qfq_calc_state()
377 * q->bitmaps[dst] |= q->bitmaps[src] & mask;
378 * q->bitmaps[src] &= ~mask;
384 q->bitmaps[dst] |= q->bitmaps[src] & mask; in qfq_move_groups()
385 q->bitmaps[src] &= ~mask; in qfq_move_groups()
389 qfq_unblock_groups(struct qfq_sched *q, int index, uint64_t old_finish) in qfq_unblock_groups() argument
391 unsigned long mask = mask_from(q->bitmaps[ER], index + 1); in qfq_unblock_groups()
396 if (!qfq_gt(next->F, old_finish)) in qfq_unblock_groups()
400 mask = (1UL << index) - 1; in qfq_unblock_groups()
408 old_V ^= q->V;
420 vslot = q->V >> QFQ_MIN_SLOT_SHIFT; in qfq_make_eligible()
424 /* must be 2ULL, see ToN QFQ article fig.5, we use base-0 fls */ in qfq_make_eligible()
425 mask = (2ULL << (__fls(vslot ^ old_vslot))) - 1; in qfq_make_eligible()
434 * roundedS is always cl->S rounded on grp->slot_shift bits.
439 uint64_t slot = (roundedS - grp->S) >> grp->slot_shift; in qfq_slot_insert()
440 unsigned int i = (grp->front + slot) % QFQ_MAX_SLOTS; in qfq_slot_insert()
442 cl->next = grp->slots[i]; in qfq_slot_insert()
443 grp->slots[i] = cl; in qfq_slot_insert()
444 __set_bit(slot, &grp->full_slots); in qfq_slot_insert()
453 struct qfq_class **h = &grp->slots[grp->front]; in qfq_front_slot_remove()
455 *h = (*h)->next; in qfq_front_slot_remove()
457 __clear_bit(0, &grp->full_slots); in qfq_front_slot_remove()
461 * Returns the first full queue in a group. As a side effect,
462 * adjust the bucket list so the first non-empty bucket is at
470 ND("grp %d full %x", grp->index, grp->full_slots); in qfq_slot_scan()
471 if (!grp->full_slots) in qfq_slot_scan()
474 i = ffs(grp->full_slots) - 1; // zero-based in qfq_slot_scan()
476 grp->front = (grp->front + i) % QFQ_MAX_SLOTS; in qfq_slot_scan()
477 grp->full_slots >>= i; in qfq_slot_scan()
480 return grp->slots[grp->front]; in qfq_slot_scan()
484 * adjust the bucket list. When the start time of a group decreases,
485 * we move the index down (modulo QFQ_MAX_SLOTS) so we don't need to
487 * because we use ffs() to find the first non-empty slot.
488 * This covers decreases in the group's start time, but what about
495 unsigned int i = (grp->S - roundedS) >> grp->slot_shift; in qfq_slot_rotate()
498 grp->full_slots <<= i; in qfq_slot_rotate()
499 grp->front = (grp->front - i) % QFQ_MAX_SLOTS; in qfq_slot_rotate()
507 ineligible = q->bitmaps[IR] | q->bitmaps[IB]; in qfq_update_eligible()
509 if (!q->bitmaps[ER]) { in qfq_update_eligible()
512 if (qfq_gt(grp->S, q->V)) in qfq_update_eligible()
513 q->V = grp->S; in qfq_update_eligible()
520 * Updates the class, returns true if also the group needs to be updated.
528 cl->S = cl->F; in qfq_update_class()
529 if (cl->_q.mq.head == NULL) { in qfq_update_class()
535 len = cl->_q.mq.head->m_pkthdr.len; in qfq_update_class()
536 cl->F = cl->S + (uint64_t)len * cl->inv_w; in qfq_update_class()
537 roundedS = qfq_round_down(cl->S, grp->slot_shift); in qfq_update_class()
538 if (roundedS == grp->S) in qfq_update_class()
556 NO(q->loops++;) in qfq_dequeue()
557 if (!q->bitmaps[ER]) { in qfq_dequeue()
558 NO(if (q->queued) in qfq_dequeue()
563 grp = qfq_ffs(q, q->bitmaps[ER]); in qfq_dequeue()
565 cl = grp->slots[grp->front]; in qfq_dequeue()
567 m = dn_dequeue(&cl->_q); in qfq_dequeue()
570 D("BUG/* non-workconserving leaf */"); in qfq_dequeue()
573 NO(q->queued--;) in qfq_dequeue()
574 old_V = q->V; in qfq_dequeue()
575 q->V += (uint64_t)m->m_pkthdr.len * q->iwsum; in qfq_dequeue()
576 ND("m is %p F 0x%llx V now 0x%llx", m, cl->F, q->V); in qfq_dequeue()
579 uint64_t old_F = grp->F; in qfq_dequeue()
581 if (!cl) { /* group gone, remove from ER */ in qfq_dequeue()
582 __clear_bit(grp->index, &q->bitmaps[ER]); in qfq_dequeue()
583 // grp->S = grp->F + 1; // XXX debugging only in qfq_dequeue()
585 uint64_t roundedS = qfq_round_down(cl->S, grp->slot_shift); in qfq_dequeue()
588 if (grp->S == roundedS) in qfq_dequeue()
590 grp->S = roundedS; in qfq_dequeue()
591 grp->F = roundedS + (2ULL << grp->slot_shift); in qfq_dequeue()
593 __clear_bit(grp->index, &q->bitmaps[ER]); in qfq_dequeue()
595 __set_bit(grp->index, &q->bitmaps[s]); in qfq_dequeue()
597 /* we need to unblock even if the group has gone away */ in qfq_dequeue()
598 qfq_unblock_groups(q, grp->index, old_F); in qfq_dequeue()
603 NO(if (!q->bitmaps[ER] && q->queued) in qfq_dequeue()
610 * Assign a reasonable start time for a new flow k in group i.
618 * the F_j of the first group j which would be blocking us.
620 * otherwise our group i would still be blocked.
627 int slot_shift = cl->grp->slot_shift; in qfq_update_start()
629 roundedF = qfq_round_down(cl->F, slot_shift); in qfq_update_start()
630 limit = qfq_round_down(q->V, slot_shift) + (1ULL << slot_shift); in qfq_update_start()
632 if (!qfq_gt(cl->F, q->V) || qfq_gt(roundedF, limit)) { in qfq_update_start()
634 mask = mask_from(q->bitmaps[ER], cl->grp->index); in qfq_update_start()
637 if (qfq_gt(roundedF, next->F)) { in qfq_update_start()
639 if (qfq_gt(limit, next->F)) in qfq_update_start()
640 cl->S = next->F; in qfq_update_start()
642 cl->S = limit; in qfq_update_start()
646 cl->S = q->V; in qfq_update_start()
648 cl->S = cl->F; in qfq_update_start()
661 NO(q->loops++;) in qfq_enqueue()
662 DX(4, "len %d flow %p inv_w 0x%x grp %d", m->m_pkthdr.len, in qfq_enqueue()
663 _q, cl->inv_w, cl->grp->index); in qfq_enqueue()
665 if (m != _q->mq.head) { in qfq_enqueue()
668 NO(q->queued++;) in qfq_enqueue()
669 if (m != _q->mq.head) in qfq_enqueue()
673 grp = cl->grp; in qfq_enqueue()
676 cl->F = cl->S + (uint64_t)(m->m_pkthdr.len) * cl->inv_w; in qfq_enqueue()
677 roundedS = qfq_round_down(cl->S, grp->slot_shift); in qfq_enqueue()
681 * If cl->S >= grp->S we don't need to adjust the in qfq_enqueue()
683 * Otherwise grp->S is decreasing, we must make room in qfq_enqueue()
684 * in the bucket list, and also recompute the group state. in qfq_enqueue()
685 * Finally, if there were no flows in this group and nobody in qfq_enqueue()
688 if (grp->full_slots) { in qfq_enqueue()
689 if (!qfq_gt(grp->S, cl->S)) in qfq_enqueue()
691 /* create a slot for this cl->S */ in qfq_enqueue()
693 /* group was surely ineligible, remove */ in qfq_enqueue()
694 __clear_bit(grp->index, &q->bitmaps[IR]); in qfq_enqueue()
695 __clear_bit(grp->index, &q->bitmaps[IB]); in qfq_enqueue()
696 } else if (!q->bitmaps[ER] && qfq_gt(roundedS, q->V)) in qfq_enqueue()
697 q->V = roundedS; in qfq_enqueue()
699 grp->S = roundedS; in qfq_enqueue()
700 grp->F = roundedS + (2ULL << grp->slot_shift); // i.e. 2\sigma_i in qfq_enqueue()
702 __set_bit(grp->index, &q->bitmaps[s]); in qfq_enqueue()
703 ND("new state %d 0x%x", s, q->bitmaps[s]); in qfq_enqueue()
704 ND("S %llx F %llx V %llx", cl->S, cl->F, q->V); in qfq_enqueue()
719 roundedS = qfq_round_down(cl->S, grp->slot_shift);
720 offset = (roundedS - grp->S) >> grp->slot_shift;
721 i = (grp->front + offset) % QFQ_MAX_SLOTS;
725 pprev = &grp->slots[i];
727 pprev = &(*pprev)->next;
731 *pprev = cl->next;
732 if (!grp->slots[i])
733 __clear_bit(offset, &grp->full_slots);
748 struct qfq_group *grp = &q->groups[cl->index];
753 cl->F = cl->S; // not needed if the class goes away.
756 if (!grp->full_slots) {
757 /* nothing left in the group, remove from all sets.
761 __clear_bit(grp->index, &q->bitmaps[IR]);
762 __clear_bit(grp->index, &q->bitmaps[EB]);
763 __clear_bit(grp->index, &q->bitmaps[IB]);
765 if (test_bit(grp->index, &q->bitmaps[ER]) &&
766 !(q->bitmaps[ER] & ~((1UL << grp->index) - 1))) {
767 mask = q->bitmaps[ER] & ((1UL << grp->index) - 1);
769 mask = ~((1UL << __fls(mask)) - 1);
775 __clear_bit(grp->index, &q->bitmaps[ER]);
776 } else if (!grp->slots[grp->front]) {
778 roundedS = qfq_round_down(cl->S, grp->slot_shift);
779 if (grp->S != roundedS) {
780 __clear_bit(grp->index, &q->bitmaps[ER]);
781 __clear_bit(grp->index, &q->bitmaps[IR]);
782 __clear_bit(grp->index, &q->bitmaps[EB]);
783 __clear_bit(grp->index, &q->bitmaps[IB]);
784 grp->S = roundedS;
785 grp->F = roundedS + (2ULL << grp->slot_shift);
787 __set_bit(grp->index, &q->bitmaps[s]);
790 qfq_update_eligible(q, q->V);
797 ipdn_bound_var(&f->fs.par[0], 1, 1, QFQ_MAX_WEIGHT, "qfq weight"); in qfq_new_fsk()
798 ipdn_bound_var(&f->fs.par[1], 1500, 1, 2000, "qfq maxlen"); in qfq_new_fsk()
799 ND("weight %d len %d\n", f->fs.par[0], f->fs.par[1]); in qfq_new_fsk()
814 grp = &q->groups[i]; in qfq_new_sched()
815 grp->index = i; in qfq_new_sched()
816 grp->slot_shift = QFQ_MTU_SHIFT + FRAC_BITS - in qfq_new_sched()
817 (QFQ_MAX_INDEX - i); in qfq_new_sched()
832 _SI( .q_datalen = ) sizeof(struct qfq_class) - sizeof(struct dn_queue),
859 struct qfq_group *g = &q->groups[i]; in dump_groups()
864 if (g->slots[j]) in dump_groups()
865 D(" bucket %d %p", j, g->slots[j]); in dump_groups()
867 D("full_slots 0x%llx", (_P64)g->full_slots); in dump_groups()
869 (_P64)g->S, (_P64)g->F, in dump_groups()
877 D("--- in %s: ---", msg); in dump_sched()
878 D("loops %d queued %d V 0x%llx", q->loops, q->queued, (_P64)q->V); in dump_sched()
879 D(" ER 0x%08x", (unsigned)q->bitmaps[ER]); in dump_sched()
880 D(" EB 0x%08x", (unsigned)q->bitmaps[EB]); in dump_sched()
881 D(" IR 0x%08x", (unsigned)q->bitmaps[IR]); in dump_sched()
882 D(" IB 0x%08x", (unsigned)q->bitmaps[IB]); in dump_sched()