net/pktsched/pktsched_qfq.c

183 	struct qfq_if	*qif;
185 	qif = (how == M_WAITOK) ? zalloc(qfq_zone) : zalloc_noblock(qfq_zone);
186 	if (qif == NULL)
189 	bzero(qif, qfq_size);
190 	qif->qif_ifq = &ifp->if_snd;
192 		qif->qif_maxclasses = QFQ_MAX_CLASSES;
193 		qif->qif_maxslots = QFQ_MAX_SLOTS;
194 		qif->qif_flags |= QFQIFF_ALTQ;
196 		qif->qif_maxclasses = IFCQ_SC_MAX;
203 		 *	qif->qif_maxslots = IFCQ_SC_MAX;
205 		qif->qif_maxslots = QFQ_MAX_SLOTS;
208 	if ((qif->qif_class_tbl = _MALLOC(sizeof (struct qfq_class *) *
209 	    qif->qif_maxclasses, M_DEVBUF, M_WAITOK|M_ZERO)) == NULL) {
211 		    if_name(ifp), qfq_style(qif));
215 	if ((qif->qif_groups = _MALLOC(sizeof (struct qfq_group *) *
218 		    if_name(ifp), qfq_style(qif));
224 		    if_name(ifp), qfq_style(qif));
227 	return (qif);
230 	if (qif->qif_class_tbl != NULL) {
231 		_FREE(qif->qif_class_tbl, M_DEVBUF);
232 		qif->qif_class_tbl = NULL;
234 	if (qif->qif_groups != NULL) {
235 		_FREE(qif->qif_groups, M_DEVBUF);
236 		qif->qif_groups = NULL;
238 	zfree(qfq_zone, qif);
244 qfq_destroy(struct qfq_if *qif)
246 	struct ifclassq *ifq = qif->qif_ifq;
250 	err = qfq_destroy_locked(qif);
257 qfq_destroy_locked(struct qfq_if *qif)
261 	IFCQ_LOCK_ASSERT_HELD(qif->qif_ifq);
263 	(void) qfq_clear_interface(qif);
265 	VERIFY(qif->qif_class_tbl != NULL);
266 	_FREE(qif->qif_class_tbl, M_DEVBUF);
267 	qif->qif_class_tbl = NULL;
269 	VERIFY(qif->qif_groups != NULL);
271 		struct qfq_group *grp = qif->qif_groups[i];
278 			qif->qif_groups[i] = NULL;
281 	_FREE(qif->qif_groups, M_DEVBUF);
282 	qif->qif_groups = NULL;
286 		    if_name(QFQIF_IFP(qif)), qfq_style(qif));
289 	zfree(qfq_zone, qif);
299 qfq_clear_interface(struct qfq_if *qif)
304 	IFCQ_LOCK_ASSERT_HELD(qif->qif_ifq);
307 	for (i = 0; i < qif->qif_maxclasses; i++)
308 		if ((cl = qif->qif_class_tbl[i]) != NULL)
309 			qfq_class_destroy(qif, cl);
316 qfq_purge(struct qfq_if *qif)
321 	IFCQ_LOCK_ASSERT_HELD(qif->qif_ifq);
323 	for (i = 0; i < qif->qif_maxclasses; i++) {
324 		if ((cl = qif->qif_class_tbl[i]) != NULL)
325 			qfq_purgeq(qif, cl, 0, NULL, NULL);
334 	VERIFY(IFCQ_LEN(qif->qif_ifq) == 0);
339 qfq_purge_sc(struct qfq_if *qif, cqrq_purge_sc_t *pr)
341 	struct ifclassq *ifq = qif->qif_ifq;
353 		qfq_purgeq(qif, ifq->ifcq_disc_slots[i].cl,
362 			qfq_purgeq(qif, ifq->ifcq_disc_slots[i].cl,
371 qfq_event(struct qfq_if *qif, cqev_t ev)
376 	IFCQ_LOCK_ASSERT_HELD(qif->qif_ifq);
378 	for (i = 0; i < qif->qif_maxclasses; i++)
379 		if ((cl = qif->qif_class_tbl[i]) != NULL)
380 			qfq_updateq(qif, cl, ev);
384 qfq_add_queue(struct qfq_if *qif, u_int32_t qlimit, u_int32_t weight,
390 	IFCQ_LOCK_ASSERT_HELD(qif->qif_ifq);
392 	if (qfq_clh_to_clp(qif, qid) != NULL)
400 	if (qif->qif_wsum + w > QFQ_MAX_WSUM)
406 	cl = qfq_class_create(qif, weight, qlimit, flags, maxsz, qid);
417 qfq_class_create(struct qfq_if *qif, u_int32_t weight, u_int32_t qlimit,
427 	IFCQ_LOCK_ASSERT_HELD(qif->qif_ifq);
430 	if (qif->qif_flags & QFQIFF_ALTQ)
433 	if (qif->qif_classes >= qif->qif_maxclasses) {
435 		    if_name(QFQIF_IFP(qif)), qfq_style(qif),
436 		    qif->qif_maxclasses);
443 		    if_name(QFQIF_IFP(qif)), qfq_style(qif));
451 		    if_name(QFQIF_IFP(qif)), qfq_style(qif));
459 		    if_name(QFQIF_IFP(qif)), qfq_style(qif));
471 		    if_name(QFQIF_IFP(qif)), qfq_style(qif));
475 	ifq = qif->qif_ifq;
476 	ifp = QFQIF_IFP(qif);
490 	cl->cl_qif = qif;
499 	i = qid % qif->qif_maxclasses;
500 	if (qif->qif_class_tbl[i] == NULL) {
501 		qif->qif_class_tbl[i] = cl;
503 		for (i = 0; i < qif->qif_maxclasses; i++) {
504 			if (qif->qif_class_tbl[i] == NULL) {
505 				qif->qif_class_tbl[i] = cl;
509 		if (i == qif->qif_maxclasses) {
520 	VERIFY(qif->qif_wsum + w <= QFQ_MAX_WSUM);
524 	grp = qif->qif_groups[i];
532 			    qif->qif_maxslots, M_DEVBUF, M_WAITOK|M_ZERO);
536 				    qfq_style(qif), i);
540 			    "qid=%d\n", if_name(ifp), qfq_style(qif),
544 			qif->qif_class_tbl[qid % qif->qif_maxclasses] = NULL;
550 			qif->qif_groups[i] = grp;
554 	qif->qif_wsum += w;
555 	/* XXX cl->cl_S = qif->qif_V; ? */
556 	/* XXX compute qif->qif_i_wsum */
558 	qif->qif_classes++;
561 		qif->qif_default = cl;
637 		    "qlimit=%d flags=%b\n", if_name(ifp), qfq_style(qif),
646 qfq_remove_queue(struct qfq_if *qif, u_int32_t qid)
650 	IFCQ_LOCK_ASSERT_HELD(qif->qif_ifq);
652 	if ((cl = qfq_clh_to_clp(qif, qid)) == NULL)
655 	return (qfq_class_destroy(qif, cl));
659 qfq_class_destroy(struct qfq_if *qif, struct qfq_class *cl)
661 	struct ifclassq *ifq = qif->qif_ifq;
666 	qfq_purgeq(qif, cl, 0, NULL, NULL);
669 		qif->qif_wsum -= (QFQ_ONE_FP / cl->cl_inv_w);
673 	for (i = 0; i < qif->qif_maxclasses; i++) {
674 		if (qif->qif_class_tbl[i] == cl) {
675 			qif->qif_class_tbl[i] = NULL;
679 	qif->qif_classes--;
701 	if (qif->qif_default == cl)
702 		qif->qif_default = NULL;
706 		    if_name(QFQIF_IFP(qif)), qfq_style(qif), cl->cl_handle);
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);
733 	pktsched_bitmap_t mask = mask_from(qif->qif_bitmaps[ER],
738 		next = qfq_ffs(qif, mask);
748  *	qif->qif_bitmaps[dst] |= qif->qif_bitmaps[src] & mask;
749  *	qif->qif_bitmaps[src] &= ~mask;
753 qfq_move_groups(struct qfq_if *qif, pktsched_bitmap_t mask, int src, int dst)
755 	qif->qif_bitmaps[dst] |= qif->qif_bitmaps[src] & mask;
756 	qif->qif_bitmaps[src] &= ~mask;
760 qfq_unblock_groups(struct qfq_if *qif, int index, u_int64_t old_finish)
762 	pktsched_bitmap_t mask = mask_from(qif->qif_bitmaps[ER], index + 1);
766 		next = qfq_ffs(qif, mask);
772 	qfq_move_groups(qif, mask, EB, ER);
773 	qfq_move_groups(qif, mask, IB, IR);
779  *	old_V ^= qif->qif_V;
786 qfq_make_eligible(struct qfq_if *qif, u_int64_t old_V)
790 	vslot = qif->qif_V >> QFQ_MIN_SLOT_SHIFT;
795 		qfq_move_groups(qif, mask, IR, ER);
796 		qfq_move_groups(qif, mask, IB, EB);
806 qfq_slot_insert(struct qfq_if *qif, struct qfq_group *grp,
810 	u_int32_t i = (grp->qfg_front + slot) % qif->qif_maxslots;
836 qfq_slot_scan(struct qfq_if *qif, struct qfq_group *grp)
842 		    if_name(QFQIF_IFP(qif)), qfq_style(qif), grp->qfg_index,
851 		grp->qfg_front = (grp->qfg_front + i) % qif->qif_maxslots;
860  * we move the index down (modulo qif->qif_maxslots) so we don't need to
868 qfq_slot_rotate(struct qfq_if *qif, struct qfq_group *grp, u_int64_t roundedS)
870 #pragma unused(qif)
874 	grp->qfg_front = (grp->qfg_front - i) % qif->qif_maxslots;
878 qfq_update_eligible(struct qfq_if *qif, u_int64_t old_V)
882 	ineligible = qif->qif_bitmaps[IR] | qif->qif_bitmaps[IB];
884 		if (!qif->qif_bitmaps[ER]) {
886 			grp = qfq_ffs(qif, ineligible);
887 			if (qfq_gt(grp->qfg_S, qif->qif_V))
888 				qif->qif_V = grp->qfg_S;
890 		qfq_make_eligible(qif, old_V);
898 qfq_update_class(struct qfq_if *qif, struct qfq_group *grp,
901 #pragma unused(qif)
916 		qfq_slot_insert(qif, grp, cl, roundedS);
928 qfq_dequeue(struct qfq_if *qif, cqdq_op_t op)
930 	pktsched_bitmap_t er_bits = qif->qif_bitmaps[ER];
931 	struct ifclassq *ifq = qif->qif_ifq;
943 			if (qif->qif_queued && pktsched_verbose > 1)
944 				qfq_dump_sched(qif, "start dequeue");
949 		grp = qfq_ffs(qif, er_bits);
955 		qif->qif_emptygrp++;
971 	qif->qif_queued--;
980 	old_V = qif->qif_V;
981 	qif->qif_V += (u_int64_t)len * QFQ_IWSUM;
985 		    if_name(QFQIF_IFP(qif)), qfq_style(qif), cl->cl_handle,
986 		    m, cl->cl_F, qif->qif_V);
989 	if (qfq_update_class(qif, grp, cl)) {
992 		cl = qfq_slot_scan(qif, grp);
994 			pktsched_bit_clr(grp->qfg_index, &qif->qif_bitmaps[ER]);
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);
1016 	qfq_update_eligible(qif, old_V);
1019 	if (!qif->qif_bitmaps[ER] && qif->qif_queued && pktsched_verbose > 1)
1020 		qfq_dump_sched(qif, "end dequeue");
1040 qfq_update_start(struct qfq_if *qif, struct qfq_class *cl)
1047 	limit = qfq_round_down(qif->qif_V, slot_shift) + (1UL << slot_shift);
1049 	if (!qfq_gt(cl->cl_F, qif->qif_V) || qfq_gt(roundedF, limit)) {
1051 		mask = mask_from(qif->qif_bitmaps[ER], cl->cl_grp->qfg_index);
1053 			struct qfq_group *next = qfq_ffs(qif, mask);
1059 		cl->cl_S = qif->qif_V;
1066 qfq_enqueue(struct qfq_if *qif, struct qfq_class *cl, struct mbuf *m,
1069 	struct ifclassq *ifq = qif->qif_ifq;
1075 	VERIFY(cl == NULL || cl->cl_qif == qif);
1078 		cl = qfq_clh_to_clp(qif, t->pftag_qid);
1080 			cl = qif->qif_default;
1117 	qif->qif_queued++;
1126 	qfq_update_start(qif, cl);	/* adjust start time */
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]);
1151 	} else if (!qif->qif_bitmaps[ER] && qfq_gt(roundedS, qif->qif_V)) {
1152 		qif->qif_V = roundedS;
1158 	s = qfq_calc_state(qif, grp);
1159 	pktsched_bit_set(grp->qfg_index, &qif->qif_bitmaps[s]);
1163 		    "S=0x%llx F=0x%llx V=0x%llx\n", if_name(QFQIF_IFP(qif)),
1164 		    qfq_style(qif), cl->cl_handle, m, qfq_state2str(s),
1165 		    qif->qif_bitmaps[s], cl->cl_S, cl->cl_F, qif->qif_V);
1169 	qfq_slot_insert(qif, grp, cl, roundedS);
1177 qfq_slot_remove(struct qfq_if *qif, struct qfq_group *grp,
1180 #pragma unused(qif)
1187 	i = (grp->qfg_front + offset) % qif->qif_maxslots;
1207 qfq_deactivate_class(struct qfq_if *qif, struct qfq_class *cl)
1220 		    grp->qfg_front, qif->qif_bitmaps[ER], qif->qif_bitmaps[EB],
1221 		    qif->qif_bitmaps[IR], qif->qif_bitmaps[IB]);
1224 			qfq_dump_sched(qif, "start deactivate");
1229 	qfq_slot_remove(qif, grp, cl);
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))) {
1243 			mask = qif->qif_bitmaps[ER] &
1249 			qfq_move_groups(qif, mask, EB, ER);
1250 			qfq_move_groups(qif, mask, IB, IR);
1252 		pktsched_bit_clr(grp->qfg_index, &qif->qif_bitmaps[ER]);
1254 		cl = qfq_slot_scan(qif, grp);
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]);
1263 			s = qfq_calc_state(qif, grp);
1264 			pktsched_bit_set(grp->qfg_index, &qif->qif_bitmaps[s]);
1267 	qfq_update_eligible(qif, qif->qif_V);
1271 		qfq_dump_sched(qif, "end deactivate");
1303 	struct qfq_if	*qif = cl->cl_qif;
1304 	struct ifclassq *ifq = qif->qif_ifq;
1325 			struct ifnet *ifp = QFQIF_IFP(qif);
1342 				    qfq_style(qif), cl->cl_handle,
1344 			} else if (qif->qif_throttle != IFNET_THROTTLE_OFF) {
1346 				cqrq_throttle_t tr = { 1, qif->qif_throttle };
1347 				int err = qfq_throttle(qif, &tr);
1353 					(void) qfq_throttle(qif, &tr);
1408 qfq_purgeq(struct qfq_if *qif, struct qfq_class *cl, u_int32_t flow,
1411 	struct ifclassq *ifq = qif->qif_ifq;
1445 		VERIFY(qif->qif_queued >= cnt);
1446 		qif->qif_queued -= cnt;
1456 			qfq_deactivate_class(qif, cl);
1461 			    if_name(QFQIF_IFP(qif)),
1462 			    qfq_style(qif), cl->cl_handle,
1475 qfq_updateq(struct qfq_if *qif, struct qfq_class *cl, cqev_t ev)
1477 	IFCQ_LOCK_ASSERT_HELD(qif->qif_ifq);
1481 		    if_name(QFQIF_IFP(qif)), qfq_style(qif),
1503 qfq_get_class_stats(struct qfq_if *qif, u_int32_t qid,
1508 	IFCQ_LOCK_ASSERT_HELD(qif->qif_ifq);
1510 	if ((cl = qfq_clh_to_clp(qif, qid)) == NULL)
1545 qfq_clh_to_clp(struct qfq_if *qif, u_int32_t chandle)
1550 	IFCQ_LOCK_ASSERT_HELD(qif->qif_ifq);
1556 	i = chandle % qif->qif_maxclasses;
1557 	if ((cl = qif->qif_class_tbl[i]) != NULL && cl->cl_handle == chandle)
1559 	for (i = 0; i < qif->qif_maxclasses; i++)
1560 		if ((cl = qif->qif_class_tbl[i]) != NULL &&
1568 qfq_style(struct qfq_if *qif)
1570 	return ((qif->qif_flags & QFQIFF_ALTQ) ? "ALTQ_QFQ" : "QFQ");
1595 qfq_ffs(struct qfq_if *qif, pktsched_bitmap_t bitmap)
1599 	    qif->qif_groups[index] != NULL);
1600 	return (qif->qif_groups[index]);
1636 qfq_dump_groups(struct qfq_if *qif, u_int32_t mask)
1641 		struct qfq_group *g = qif->qif_groups[i];
1649 		    if_name(QFQIF_IFP(qif)), qfq_style(qif), i,
1652 		    if_name(QFQIF_IFP(qif)), qfq_style(qif),
1655 		for (j = 0; j < qif->qif_maxslots; j++) {
1658 				    "qid %d\n", if_name(QFQIF_IFP(qif)),
1659 				    qfq_style(qif), j, g->qfg_slots[j],
1667 qfq_dump_sched(struct qfq_if *qif, const char *msg)
1670 	    if_name(QFQIF_IFP(qif)), qfq_style(qif), msg);
1672 	    if_name(QFQIF_IFP(qif)), qfq_style(qif), qif->qif_emptygrp,
1673 	    qif->qif_queued, qif->qif_V);
1675 	    if_name(QFQIF_IFP(qif)), qfq_style(qif), qif->qif_bitmaps[ER]);
1677 	    if_name(QFQIF_IFP(qif)), qfq_style(qif), qif->qif_bitmaps[EB]);
1679 	    if_name(QFQIF_IFP(qif)), qfq_style(qif), qif->qif_bitmaps[IR]);
1681 	    if_name(QFQIF_IFP(qif)), qfq_style(qif), qif->qif_bitmaps[IB]);
1682 	qfq_dump_groups(qif, 0xffffffff);
1731 	struct qfq_if *qif = (struct qfq_if *)ifq->ifcq_disc;
1738 		qfq_purge(qif);
1742 		qfq_purge_sc(qif, (cqrq_purge_sc_t *)arg);
1746 		qfq_event(qif, (cqev_t)arg);
1750 		err = qfq_throttle(qif, (cqrq_throttle_t *)arg);
1762 	struct qfq_if *qif;
1783 	qif = qfq_alloc(ifp, M_WAITOK, FALSE);
1784 	if (qif == NULL)
1790 	if ((err = qfq_add_queue(qif, maxlen, 300, 1200,
1794 	if ((err = qfq_add_queue(qif, maxlen, 600, 1400,
1798 	if ((err = qfq_add_queue(qif, maxlen, 2400, 600,
1802 	if ((err = qfq_add_queue(qif, maxlen, 2700, 600,
1806 	if ((err = qfq_add_queue(qif, maxlen, 3000, 400,
1810 	if ((err = qfq_add_queue(qif, maxlen, 8000, 1000,
1814 	if ((err = qfq_add_queue(qif, maxlen, 15000, 1200,
1818 	if ((err = qfq_add_queue(qif, maxlen, 20000, 1400,
1822 	if ((err = qfq_add_queue(qif, maxlen, 23000, 200,
1826 	if ((err = qfq_add_queue(qif, maxlen, 25000, 200,
1830 	err = ifclassq_attach(ifq, PKTSCHEDT_QFQ, qif,
1869 		(void) qfq_destroy_locked(qif);
1877 	struct qfq_if *qif = ifq->ifcq_disc;
1881 	VERIFY(qif != NULL && ifq->ifcq_type == PKTSCHEDT_QFQ);
1883 	(void) qfq_destroy_locked(qif);
1898 	struct qfq_if *qif = ifq->ifcq_disc;
1906 	return (qfq_get_class_stats(qif, ifq->ifcq_disc_slots[slot].qid,
1911 qfq_throttle(struct qfq_if *qif, cqrq_throttle_t *tr)
1913 	struct ifclassq *ifq = qif->qif_ifq;
1918 	VERIFY(!(qif->qif_flags & QFQIFF_ALTQ));
1921 		tr->level = qif->qif_throttle;
1925 	if (tr->level == qif->qif_throttle)
1933 		err = qfq_resumeq(qif, cl);
1937 		err = qfq_suspendq(qif, cl);
1948 			    if_name(QFQIF_IFP(qif)), qfq_style(qif),
1949 			    (err == 0) ? "" : "lazy ", qif->qif_throttle,
1952 		qif->qif_throttle = tr->level;
1956 			qfq_purgeq(qif, cl, 0, NULL, NULL);
1959 		    "%d->%d [error=%d]\n", if_name(QFQIF_IFP(qif)),
1960 		    qfq_style(qif), qif->qif_throttle, tr->level, err);
1967 qfq_resumeq(struct qfq_if *qif, struct qfq_class *cl)
1969 	struct ifclassq *ifq = qif->qif_ifq;
1999 qfq_suspendq(struct qfq_if *qif, struct qfq_class *cl)
2001 	struct ifclassq *ifq = qif->qif_ifq;