net/pktsched/pktsched_qfq.c

271 		struct qfq_group *grp = qif->qif_groups[i];
273 		if (grp != NULL) {
274 			VERIFY(grp->qfg_slots != NULL);
275 			_FREE(grp->qfg_slots, M_DEVBUF);
276 			grp->qfg_slots = NULL;
277 			_FREE(grp, M_DEVBUF);
422 	struct qfq_group *grp;
524 	grp = qif->qif_groups[i];
525 	if (grp == NULL) {
526 		grp = _MALLOC(sizeof (*grp), M_DEVBUF, M_WAITOK|M_ZERO);
527 		if (grp != NULL) {
528 			grp->qfg_index = i;
529 			grp->qfg_slot_shift =
531 			grp->qfg_slots = _MALLOC(sizeof (struct qfq_class *) *
533 			if (grp->qfg_slots == NULL) {
543 		if (grp == NULL || grp->qfg_slots == NULL) {
545 			if (grp != NULL)
546 				_FREE(grp, M_DEVBUF);
550 			qif->qif_groups[i] = grp;
553 	cl->cl_grp = grp;
636 		log(LOG_DEBUG, "%s: %s created qid=%d grp=%d weight=%d "
725  * First compute eligibility comparing grp->qfg_S, qif->qif_V,
729 qfq_calc_state(struct qfq_if *qif, struct qfq_group *grp)
732 	u_int32_t state = qfq_gt(grp->qfg_S, qif->qif_V);
734 	    grp->qfg_index);
739 		if (qfq_gt(grp->qfg_F, next->qfg_F))
803  * roundedS is always cl->qfg_S rounded on grp->qfg_slot_shift bits.
806 qfq_slot_insert(struct qfq_if *qif, struct qfq_group *grp,
809 	u_int64_t slot = (roundedS - grp->qfg_S) >> grp->qfg_slot_shift;
810 	u_int32_t i = (grp->qfg_front + slot) % qif->qif_maxslots;
812 	cl->cl_next = grp->qfg_slots[i];
813 	grp->qfg_slots[i] = cl;
814 	pktsched_bit_set(slot, &grp->qfg_full_slots);
821 qfq_front_slot_remove(struct qfq_group *grp)
823 	struct qfq_class **h = &grp->qfg_slots[grp->qfg_front];
827 		pktsched_bit_clr(0, &grp->qfg_full_slots);
836 qfq_slot_scan(struct qfq_if *qif, struct qfq_group *grp)
841 		log(LOG_DEBUG, "%s: %s grp=%d full_slots=0x%x\n",
842 		    if_name(QFQIF_IFP(qif)), qfq_style(qif), grp->qfg_index,
843 		    grp->qfg_full_slots);
846 	if (grp->qfg_full_slots == 0)
849 	i = pktsched_ffs(grp->qfg_full_slots) - 1; /* zero-based */
851 		grp->qfg_front = (grp->qfg_front + i) % qif->qif_maxslots;
852 		grp->qfg_full_slots >>= i;
855 	return (grp->qfg_slots[grp->qfg_front]);
868 qfq_slot_rotate(struct qfq_if *qif, struct qfq_group *grp, u_int64_t roundedS)
871 	u_int32_t i = (grp->qfg_S - roundedS) >> grp->qfg_slot_shift;
873 	grp->qfg_full_slots <<= i;
874 	grp->qfg_front = (grp->qfg_front - i) % qif->qif_maxslots;
885 			struct qfq_group *grp;
886 			grp = qfq_ffs(qif, ineligible);
887 			if (qfq_gt(grp->qfg_S, qif->qif_V))
888 				qif->qif_V = grp->qfg_S;
898 qfq_update_class(struct qfq_if *qif, struct qfq_group *grp,
904 		qfq_front_slot_remove(grp);
911 		roundedS = qfq_round_down(cl->cl_S, grp->qfg_slot_shift);
912 		if (roundedS == grp->qfg_S)
915 		qfq_front_slot_remove(grp);
916 		qfq_slot_insert(qif, grp, cl, roundedS);
932 	struct qfq_group *grp;
949 		grp = qfq_ffs(qif, er_bits);
951 		if (grp->qfg_full_slots != 0)
953 		pktsched_bit_clr(grp->qfg_index, &er_bits);
960 	cl = grp->qfg_slots[grp->qfg_front];
989 	if (qfq_update_class(qif, grp, cl)) {
990 		u_int64_t old_F = grp->qfg_F;
992 		cl = qfq_slot_scan(qif, grp);
994 			pktsched_bit_clr(grp->qfg_index, &qif->qif_bitmaps[ER]);
998 			    qfq_round_down(cl->cl_S, grp->qfg_slot_shift);
1000 			if (grp->qfg_S == roundedS)
1003 			grp->qfg_S = roundedS;
1004 			grp->qfg_F = roundedS + (2ULL << grp->qfg_slot_shift);
1007 			pktsched_bit_clr(grp->qfg_index, &qif->qif_bitmaps[ER]);
1008 			s = qfq_calc_state(qif, grp);
1009 			pktsched_bit_set(grp->qfg_index, &qif->qif_bitmaps[s]);
1012 		qfq_unblock_groups(qif, grp->qfg_index, old_F);
1070 	struct qfq_group *grp;
1125 	grp = cl->cl_grp;
1130 	roundedS = qfq_round_down(cl->cl_S, grp->qfg_slot_shift);
1135 	 * If cl->cl_S >= grp->qfg_S we don't need to adjust the bucket list
1136 	 * and simply go to the insertion phase.  Otherwise grp->qfg_S is
1141 	if (grp->qfg_full_slots != 0) {
1142 		if (!qfq_gt(grp->qfg_S, cl->cl_S))
1146 		qfq_slot_rotate(qif, grp, roundedS);
1149 		pktsched_bit_clr(grp->qfg_index, &qif->qif_bitmaps[IR]);
1150 		pktsched_bit_clr(grp->qfg_index, &qif->qif_bitmaps[IB]);
1155 	grp->qfg_S = roundedS;
1156 	grp->qfg_F =
1157 	    roundedS + (2ULL << grp->qfg_slot_shift); /* i.e. 2 sigma_i */
1158 	s = qfq_calc_state(qif, grp);
1159 	pktsched_bit_set(grp->qfg_index, &qif->qif_bitmaps[s]);
1169 	qfq_slot_insert(qif, grp, cl, roundedS);
1177 qfq_slot_remove(struct qfq_if *qif, struct qfq_group *grp,
1185 	roundedS = qfq_round_down(cl->cl_S, grp->qfg_slot_shift);
1186 	offset = (roundedS - grp->qfg_S) >> grp->qfg_slot_shift;
1187 	i = (grp->qfg_front + offset) % qif->qif_maxslots;
1189 	pprev = &grp->qfg_slots[i];
1194 	if (!grp->qfg_slots[i])
1195 		pktsched_bit_clr(offset, &grp->qfg_full_slots);
1209 	struct qfq_group *grp = cl->cl_grp;
1215 		log(LOG_DEBUG, "%s: %s deactivate qid=%d grp=%d "
1219 		    cl->cl_handle, grp->qfg_index, grp->qfg_full_slots,
1220 		    grp->qfg_front, qif->qif_bitmaps[ER], qif->qif_bitmaps[EB],
1229 	qfq_slot_remove(qif, grp, cl);
1231 	if (grp->qfg_full_slots == 0) {
1237 		pktsched_bit_clr(grp->qfg_index, &qif->qif_bitmaps[IR]);
1238 		pktsched_bit_clr(grp->qfg_index, &qif->qif_bitmaps[EB]);
1239 		pktsched_bit_clr(grp->qfg_index, &qif->qif_bitmaps[IB]);
1241 		if (pktsched_bit_tst(grp->qfg_index, &qif->qif_bitmaps[ER]) &&
1242 		    !(qif->qif_bitmaps[ER] & ~((1UL << grp->qfg_index) - 1))) {
1244 			    ((1UL << grp->qfg_index) - 1);
1252 		pktsched_bit_clr(grp->qfg_index, &qif->qif_bitmaps[ER]);
1253 	} else if (!grp->qfg_slots[grp->qfg_front]) {
1254 		cl = qfq_slot_scan(qif, grp);
1255 		roundedS = qfq_round_down(cl->cl_S, grp->qfg_slot_shift);
1256 		if (grp->qfg_S != roundedS) {
1257 			pktsched_bit_clr(grp->qfg_index, &qif->qif_bitmaps[ER]);
1258 			pktsched_bit_clr(grp->qfg_index, &qif->qif_bitmaps[IR]);
1259 			pktsched_bit_clr(grp->qfg_index, &qif->qif_bitmaps[EB]);
1260 			pktsched_bit_clr(grp->qfg_index, &qif->qif_bitmaps[IB]);
1261 			grp->qfg_S = roundedS;
1262 			grp->qfg_F = roundedS + (2ULL << grp->qfg_slot_shift);
1263 			s = qfq_calc_state(qif, grp);
1264 			pktsched_bit_set(grp->qfg_index, &qif->qif_bitmaps[s]);
1340 				    "failed for qid=%d grp=%d, falling back "
1626 		log(LOG_DEBUG, "%s: %s qid=%d grp=%d W=%u, L=%u, I=%d\n",