netpfil/ipfw/dn_sched_qfq.c

162  * grp->index is the index of the group; and grp->slot_shift
205 	struct qfq_group *grp;
313 	cl->grp = &q->groups[i];
342  * First compute eligibility comparing grp->S, q->V,
346 qfq_calc_state(struct qfq_sched *q, struct qfq_group *grp)
349 	unsigned int state = qfq_gt(grp->S, q->V);
350 	unsigned long mask = mask_from(q->bitmaps[ER], grp->index);
355 		if (qfq_gt(grp->F, next->F))
420  * roundedS is always cl->S rounded on grp->slot_shift bits.
423 qfq_slot_insert(struct qfq_group *grp, struct qfq_class *cl, uint64_t roundedS)
425 	uint64_t slot = (roundedS - grp->S) >> grp->slot_shift;
426 	unsigned int i = (grp->front + slot) % QFQ_MAX_SLOTS;
428 	cl->next = grp->slots[i];
429 	grp->slots[i] = cl;
430 	__set_bit(slot, &grp->full_slots);
437 qfq_front_slot_remove(struct qfq_group *grp)
439 	struct qfq_class **h = &grp->slots[grp->front];
443 		__clear_bit(0, &grp->full_slots);
452 qfq_slot_scan(struct qfq_group *grp)
456 	ND("grp %d full %x", grp->index, grp->full_slots);
457 	if (!grp->full_slots)
460 	i = ffs(grp->full_slots) - 1; // zero-based
462 		grp->front = (grp->front + i) % QFQ_MAX_SLOTS;
463 		grp->full_slots >>= i;
466 	return grp->slots[grp->front];
479 qfq_slot_rotate(struct qfq_sched *q, struct qfq_group *grp, uint64_t roundedS)
481 	unsigned int i = (grp->S - roundedS) >> grp->slot_shift;
483 	grp->full_slots <<= i;
484 	grp->front = (grp->front - i) % QFQ_MAX_SLOTS;
496 			struct qfq_group *grp;
497 			grp = qfq_ffs(q, ineligible);
498 			if (qfq_gt(grp->S, q->V))
499 				q->V = grp->S;
509 qfq_update_class(struct qfq_sched *q, struct qfq_group *grp,
515 		qfq_front_slot_remove(grp);
522 		roundedS = qfq_round_down(cl->S, grp->slot_shift);
523 		if (roundedS == grp->S)
526 		qfq_front_slot_remove(grp);
527 		qfq_slot_insert(grp, cl, roundedS);
536 	struct qfq_group *grp;
548 	grp = qfq_ffs(q, q->bitmaps[ER]);
550 	cl = grp->slots[grp->front];
563 	if (qfq_update_class(q, grp, cl)) {
564 		uint64_t old_F = grp->F;
565 		cl = qfq_slot_scan(grp);
567 			__clear_bit(grp->index, &q->bitmaps[ER]);
568 			// grp->S = grp->F + 1; // XXX debugging only
570 			uint64_t roundedS = qfq_round_down(cl->S, grp->slot_shift);
573 			if (grp->S == roundedS)
575 			grp->S = roundedS;
576 			grp->F = roundedS + (2ULL << grp->slot_shift);
578 			__clear_bit(grp->index, &q->bitmaps[ER]);
579 			s = qfq_calc_state(q, grp);
580 			__set_bit(grp->index, &q->bitmaps[s]);
583 		qfq_unblock_groups(q, grp->index, old_F);
612 	int slot_shift = cl->grp->slot_shift;
619 		mask = mask_from(q->bitmaps[ER], cl->grp->index);
637 	struct qfq_group *grp;
643 	DX(4, "len %d flow %p inv_w 0x%x grp %d", m->m_pkthdr.len,
644 		_q, cl->inv_w, cl->grp->index);
654 	grp = cl->grp;
658 	roundedS = qfq_round_down(cl->S, grp->slot_shift);
662 	 * If cl->S >= grp->S we don't need to adjust the
664 	 * Otherwise grp->S is decreasing, we must make room
669 	if (grp->full_slots) {
670 		if (!qfq_gt(grp->S, cl->S))
673 		qfq_slot_rotate(q, grp, roundedS);
675 		__clear_bit(grp->index, &q->bitmaps[IR]);
676 		__clear_bit(grp->index, &q->bitmaps[IB]);
680 	grp->S = roundedS;
681 	grp->F = roundedS + (2ULL << grp->slot_shift); // i.e. 2\sigma_i
682 	s = qfq_calc_state(q, grp);
683 	__set_bit(grp->index, &q->bitmaps[s]);
687 	qfq_slot_insert(grp, cl, roundedS);
695 qfq_slot_remove(struct qfq_sched *q, struct qfq_group *grp,
701 	roundedS = qfq_round_down(cl->S, grp->slot_shift);
702 	offset = (roundedS - grp->S) >> grp->slot_shift;
703 	i = (grp->front + offset) % QFQ_MAX_SLOTS;
707 		pprev = &grp->slots[i];
714 	if (!grp->slots[i])
715 		__clear_bit(offset, &grp->full_slots);
730 	struct qfq_group *grp = &q->groups[cl->index];
736 	qfq_slot_remove(q, grp, cl, pprev);
738 	if (!grp->full_slots) {
743 		__clear_bit(grp->index, &q->bitmaps[IR]);
744 		__clear_bit(grp->index, &q->bitmaps[EB]);
745 		__clear_bit(grp->index, &q->bitmaps[IB]);
747 		if (test_bit(grp->index, &q->bitmaps[ER]) &&
748 		    !(q->bitmaps[ER] & ~((1UL << grp->index) - 1))) {
749 			mask = q->bitmaps[ER] & ((1UL << grp->index) - 1);
757 		__clear_bit(grp->index, &q->bitmaps[ER]);
758 	} else if (!grp->slots[grp->front]) {
759 		cl = qfq_slot_scan(grp);
760 		roundedS = qfq_round_down(cl->S, grp->slot_shift);
761 		if (grp->S != roundedS) {
762 			__clear_bit(grp->index, &q->bitmaps[ER]);
763 			__clear_bit(grp->index, &q->bitmaps[IR]);
764 			__clear_bit(grp->index, &q->bitmaps[EB]);
765 			__clear_bit(grp->index, &q->bitmaps[IB]);
766 			grp->S = roundedS;
767 			grp->F = roundedS + (2ULL << grp->slot_shift);
768 			s = qfq_calc_state(q, grp);
769 			__set_bit(grp->index, &q->bitmaps[s]);
792 	struct qfq_group *grp;
796 		grp = &q->groups[i];
797 		grp->index = i;
798 		grp->slot_shift = QFQ_MTU_SHIFT + FRAC_BITS -