1*de6d88d5Schristos /* $NetBSD: altq_hfsc.c,v 1.30 2021/09/21 14:30:15 christos Exp $ */
2dd191f37Speter /* $KAME: altq_hfsc.c,v 1.26 2005/04/13 03:44:24 suz Exp $ */
368de460fSthorpej
468de460fSthorpej /*
568de460fSthorpej * Copyright (c) 1997-1999 Carnegie Mellon University. All Rights Reserved.
668de460fSthorpej *
768de460fSthorpej * Permission to use, copy, modify, and distribute this software and
868de460fSthorpej * its documentation is hereby granted (including for commercial or
968de460fSthorpej * for-profit use), provided that both the copyright notice and this
1068de460fSthorpej * permission notice appear in all copies of the software, derivative
11dd191f37Speter * works, or modified versions, and any portions thereof.
1268de460fSthorpej *
1368de460fSthorpej * THIS SOFTWARE IS EXPERIMENTAL AND IS KNOWN TO HAVE BUGS, SOME OF
1468de460fSthorpej * WHICH MAY HAVE SERIOUS CONSEQUENCES. CARNEGIE MELLON PROVIDES THIS
1568de460fSthorpej * SOFTWARE IN ITS ``AS IS'' CONDITION, AND ANY EXPRESS OR IMPLIED
1668de460fSthorpej * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
1768de460fSthorpej * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
1868de460fSthorpej * DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY BE LIABLE
1968de460fSthorpej * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
2068de460fSthorpej * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
2168de460fSthorpej * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
2268de460fSthorpej * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
2368de460fSthorpej * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2468de460fSthorpej * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
2568de460fSthorpej * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
2668de460fSthorpej * DAMAGE.
2768de460fSthorpej *
2868de460fSthorpej * Carnegie Mellon encourages (but does not require) users of this
2968de460fSthorpej * software to return any improvements or extensions that they make,
3068de460fSthorpej * and to grant Carnegie Mellon the rights to redistribute these
3168de460fSthorpej * changes without encumbrance.
3268de460fSthorpej */
3368de460fSthorpej /*
3468de460fSthorpej * H-FSC is described in Proceedings of SIGCOMM'97,
3568de460fSthorpej * "A Hierarchical Fair Service Curve Algorithm for Link-Sharing,
3668de460fSthorpej * Real-Time and Priority Service"
3768de460fSthorpej * by Ion Stoica, Hui Zhang, and T. S. Eugene Ng.
38dd191f37Speter *
39dd191f37Speter * Oleg Cherevko <olwi@aq.ml.com.ua> added the upperlimit for link-sharing.
40dd191f37Speter * when a class has an upperlimit, the fit-time is computed from the
41dd191f37Speter * upperlimit service curve. the link-sharing scheduler does not schedule
42dd191f37Speter * a class whose fit-time exceeds the current time.
4368de460fSthorpej */
4468de460fSthorpej
45a13b5687Slukem #include <sys/cdefs.h>
46*de6d88d5Schristos __KERNEL_RCSID(0, "$NetBSD: altq_hfsc.c,v 1.30 2021/09/21 14:30:15 christos Exp $");
47a13b5687Slukem
48dd191f37Speter #ifdef _KERNEL_OPT
4968de460fSthorpej #include "opt_altq.h"
5068de460fSthorpej #include "opt_inet.h"
51463fbff4Speter #include "pf.h"
5268de460fSthorpej #endif
5368de460fSthorpej
5468de460fSthorpej #ifdef ALTQ_HFSC /* hfsc is enabled by ALTQ_HFSC option in opt_altq.h */
5568de460fSthorpej
5668de460fSthorpej #include <sys/param.h>
5768de460fSthorpej #include <sys/malloc.h>
5868de460fSthorpej #include <sys/mbuf.h>
5968de460fSthorpej #include <sys/socket.h>
6068de460fSthorpej #include <sys/systm.h>
6168de460fSthorpej #include <sys/errno.h>
6268de460fSthorpej #include <sys/queue.h>
63dd191f37Speter #if 1 /* ALTQ3_COMPAT */
64dd191f37Speter #include <sys/sockio.h>
65dd191f37Speter #include <sys/proc.h>
66dd191f37Speter #include <sys/kernel.h>
67dd191f37Speter #endif /* ALTQ3_COMPAT */
68fc6d984bSchristos #include <sys/kauth.h>
6968de460fSthorpej
7068de460fSthorpej #include <net/if.h>
71dd191f37Speter #include <netinet/in.h>
7268de460fSthorpej
73463fbff4Speter #if NPF > 0
74dd191f37Speter #include <net/pfvar.h>
75463fbff4Speter #endif
7668de460fSthorpej #include <altq/altq.h>
7768de460fSthorpej #include <altq/altq_hfsc.h>
78dd191f37Speter #ifdef ALTQ3_COMPAT
79dd191f37Speter #include <altq/altq_conf.h>
80dd191f37Speter #endif
8168de460fSthorpej
8268de460fSthorpej /*
8368de460fSthorpej * function prototypes
8468de460fSthorpej */
85dd191f37Speter static int hfsc_clear_interface(struct hfsc_if *);
86dd191f37Speter static int hfsc_request(struct ifaltq *, int, void *);
87dd191f37Speter static void hfsc_purge(struct hfsc_if *);
88dd191f37Speter static struct hfsc_class *hfsc_class_create(struct hfsc_if *,
89dd191f37Speter struct service_curve *, struct service_curve *, struct service_curve *,
90dd191f37Speter struct hfsc_class *, int, int, int);
91dd191f37Speter static int hfsc_class_destroy(struct hfsc_class *);
92dd191f37Speter static struct hfsc_class *hfsc_nextclass(struct hfsc_class *);
9325937c0dSknakahara static int hfsc_enqueue(struct ifaltq *, struct mbuf *);
94dd191f37Speter static struct mbuf *hfsc_dequeue(struct ifaltq *, int);
9568de460fSthorpej
96dd191f37Speter static int hfsc_addq(struct hfsc_class *, struct mbuf *);
97dd191f37Speter static struct mbuf *hfsc_getq(struct hfsc_class *);
98dd191f37Speter static struct mbuf *hfsc_pollq(struct hfsc_class *);
99dd191f37Speter static void hfsc_purgeq(struct hfsc_class *);
10068de460fSthorpej
101dd191f37Speter static void update_cfmin(struct hfsc_class *);
102dd191f37Speter static void set_active(struct hfsc_class *, int);
103dd191f37Speter static void set_passive(struct hfsc_class *);
10468de460fSthorpej
105dd191f37Speter static void init_ed(struct hfsc_class *, int);
106dd191f37Speter static void update_ed(struct hfsc_class *, int);
107dd191f37Speter static void update_d(struct hfsc_class *, int);
108dd191f37Speter static void init_vf(struct hfsc_class *, int);
109dd191f37Speter static void update_vf(struct hfsc_class *, int, u_int64_t);
110dd191f37Speter static ellist_t *ellist_alloc(void);
111dd191f37Speter static void ellist_destroy(ellist_t *);
112dd191f37Speter static void ellist_insert(struct hfsc_class *);
113dd191f37Speter static void ellist_remove(struct hfsc_class *);
114dd191f37Speter static void ellist_update(struct hfsc_class *);
115dd191f37Speter struct hfsc_class *ellist_get_mindl(ellist_t *, u_int64_t);
116dd191f37Speter static actlist_t *actlist_alloc(void);
117dd191f37Speter static void actlist_destroy(actlist_t *);
118dd191f37Speter static void actlist_insert(struct hfsc_class *);
119dd191f37Speter static void actlist_remove(struct hfsc_class *);
120dd191f37Speter static void actlist_update(struct hfsc_class *);
12168de460fSthorpej
122dd191f37Speter static struct hfsc_class *actlist_firstfit(struct hfsc_class *,
123dd191f37Speter u_int64_t);
12468de460fSthorpej
125dd191f37Speter static inline u_int64_t seg_x2y(u_int64_t, u_int64_t);
126dd191f37Speter static inline u_int64_t seg_y2x(u_int64_t, u_int64_t);
127dd191f37Speter static inline u_int64_t m2sm(u_int);
128dd191f37Speter static inline u_int64_t m2ism(u_int);
129dd191f37Speter static inline u_int64_t d2dx(u_int);
130dd191f37Speter static u_int sm2m(u_int64_t);
131dd191f37Speter static u_int dx2d(u_int64_t);
13268de460fSthorpej
133dd191f37Speter static void sc2isc(struct service_curve *, struct internal_sc *);
134dd191f37Speter static void rtsc_init(struct runtime_sc *, struct internal_sc *,
135dd191f37Speter u_int64_t, u_int64_t);
136dd191f37Speter static u_int64_t rtsc_y2x(struct runtime_sc *, u_int64_t);
137dd191f37Speter static u_int64_t rtsc_x2y(struct runtime_sc *, u_int64_t);
138dd191f37Speter static void rtsc_min(struct runtime_sc *, struct internal_sc *,
139dd191f37Speter u_int64_t, u_int64_t);
14068de460fSthorpej
141dd191f37Speter static void get_class_stats(struct hfsc_classstats *,
142dd191f37Speter struct hfsc_class *);
143dd191f37Speter static struct hfsc_class *clh_to_clp(struct hfsc_if *, u_int32_t);
144dd191f37Speter
145dd191f37Speter
146dd191f37Speter #ifdef ALTQ3_COMPAT
147dd191f37Speter static struct hfsc_if *hfsc_attach(struct ifaltq *, u_int);
148ec004aeaSchristos static void hfsc_detach(struct hfsc_if *);
149dd191f37Speter static int hfsc_class_modify(struct hfsc_class *, struct service_curve *,
150dd191f37Speter struct service_curve *, struct service_curve *);
151dd191f37Speter
152dd191f37Speter static int hfsccmd_if_attach(struct hfsc_attach *);
153dd191f37Speter static int hfsccmd_if_detach(struct hfsc_interface *);
154dd191f37Speter static int hfsccmd_add_class(struct hfsc_add_class *);
155dd191f37Speter static int hfsccmd_delete_class(struct hfsc_delete_class *);
156dd191f37Speter static int hfsccmd_modify_class(struct hfsc_modify_class *);
157dd191f37Speter static int hfsccmd_add_filter(struct hfsc_add_filter *);
158dd191f37Speter static int hfsccmd_delete_filter(struct hfsc_delete_filter *);
159dd191f37Speter static int hfsccmd_class_stats(struct hfsc_class_stats *);
160dd191f37Speter
161dd191f37Speter altqdev_decl(hfsc);
162dd191f37Speter #endif /* ALTQ3_COMPAT */
16368de460fSthorpej
16468de460fSthorpej /*
16568de460fSthorpej * macros
16668de460fSthorpej */
16768de460fSthorpej #define is_a_parent_class(cl) ((cl)->cl_children != NULL)
16868de460fSthorpej
169dd191f37Speter #define HT_INFINITY 0xffffffffffffffffLL /* infinite time value */
170dd191f37Speter
171dd191f37Speter #ifdef ALTQ3_COMPAT
17268de460fSthorpej /* hif_list keeps all hfsc_if's allocated. */
17368de460fSthorpej static struct hfsc_if *hif_list = NULL;
174dd191f37Speter #endif /* ALTQ3_COMPAT */
17568de460fSthorpej
176463fbff4Speter #if NPF > 0
177dd191f37Speter int
hfsc_pfattach(struct pf_altq * a)178dd191f37Speter hfsc_pfattach(struct pf_altq *a)
179dd191f37Speter {
180dd191f37Speter struct ifnet *ifp;
181dd191f37Speter int s, error;
182dd191f37Speter
183dd191f37Speter if ((ifp = ifunit(a->ifname)) == NULL || a->altq_disc == NULL)
184dd191f37Speter return (EINVAL);
185dd191f37Speter s = splnet();
186dd191f37Speter error = altq_attach(&ifp->if_snd, ALTQT_HFSC, a->altq_disc,
187dd191f37Speter hfsc_enqueue, hfsc_dequeue, hfsc_request, NULL, NULL);
188dd191f37Speter splx(s);
189dd191f37Speter return (error);
190dd191f37Speter }
191dd191f37Speter
192dd191f37Speter int
hfsc_add_altq(struct pf_altq * a)193dd191f37Speter hfsc_add_altq(struct pf_altq *a)
19468de460fSthorpej {
19568de460fSthorpej struct hfsc_if *hif;
196dd191f37Speter struct ifnet *ifp;
197dd191f37Speter
198dd191f37Speter if ((ifp = ifunit(a->ifname)) == NULL)
199dd191f37Speter return (EINVAL);
200dd191f37Speter if (!ALTQ_IS_READY(&ifp->if_snd))
201dd191f37Speter return (ENODEV);
20268de460fSthorpej
203d53df8e8Schristos hif = malloc(sizeof(struct hfsc_if), M_DEVBUF, M_WAITOK|M_ZERO);
20468de460fSthorpej if (hif == NULL)
205dd191f37Speter return (ENOMEM);
20668de460fSthorpej
20768de460fSthorpej hif->hif_eligible = ellist_alloc();
20868de460fSthorpej if (hif->hif_eligible == NULL) {
209d53df8e8Schristos free(hif, M_DEVBUF);
210dd191f37Speter return (ENOMEM);
21168de460fSthorpej }
21268de460fSthorpej
213dd191f37Speter hif->hif_ifq = &ifp->if_snd;
21468de460fSthorpej
215dd191f37Speter /* keep the state in pf_altq */
216dd191f37Speter a->altq_disc = hif;
217dd191f37Speter
218dd191f37Speter return (0);
21968de460fSthorpej }
22068de460fSthorpej
221dd191f37Speter int
hfsc_remove_altq(struct pf_altq * a)222dd191f37Speter hfsc_remove_altq(struct pf_altq *a)
22368de460fSthorpej {
224dd191f37Speter struct hfsc_if *hif;
225dd191f37Speter
226dd191f37Speter if ((hif = a->altq_disc) == NULL)
227dd191f37Speter return (EINVAL);
228dd191f37Speter a->altq_disc = NULL;
229dd191f37Speter
23068de460fSthorpej (void)hfsc_clear_interface(hif);
23168de460fSthorpej (void)hfsc_class_destroy(hif->hif_rootclass);
23268de460fSthorpej
23368de460fSthorpej ellist_destroy(hif->hif_eligible);
23468de460fSthorpej
235d53df8e8Schristos free(hif, M_DEVBUF);
23668de460fSthorpej
23768de460fSthorpej return (0);
23868de460fSthorpej }
23968de460fSthorpej
240dd191f37Speter int
hfsc_add_queue(struct pf_altq * a)241dd191f37Speter hfsc_add_queue(struct pf_altq *a)
242dd191f37Speter {
243dd191f37Speter struct hfsc_if *hif;
244dd191f37Speter struct hfsc_class *cl, *parent;
245dd191f37Speter struct hfsc_opts *opts;
246dd191f37Speter struct service_curve rtsc, lssc, ulsc;
247dd191f37Speter
248dd191f37Speter if ((hif = a->altq_disc) == NULL)
249dd191f37Speter return (EINVAL);
250dd191f37Speter
251dd191f37Speter opts = &a->pq_u.hfsc_opts;
252dd191f37Speter
253dd191f37Speter if (a->parent_qid == HFSC_NULLCLASS_HANDLE &&
254dd191f37Speter hif->hif_rootclass == NULL)
255dd191f37Speter parent = NULL;
256dd191f37Speter else if ((parent = clh_to_clp(hif, a->parent_qid)) == NULL)
257dd191f37Speter return (EINVAL);
258dd191f37Speter
259dd191f37Speter if (a->qid == 0)
260dd191f37Speter return (EINVAL);
261dd191f37Speter
262dd191f37Speter if (clh_to_clp(hif, a->qid) != NULL)
263dd191f37Speter return (EBUSY);
264dd191f37Speter
265dd191f37Speter rtsc.m1 = opts->rtsc_m1;
266dd191f37Speter rtsc.d = opts->rtsc_d;
267dd191f37Speter rtsc.m2 = opts->rtsc_m2;
268dd191f37Speter lssc.m1 = opts->lssc_m1;
269dd191f37Speter lssc.d = opts->lssc_d;
270dd191f37Speter lssc.m2 = opts->lssc_m2;
271dd191f37Speter ulsc.m1 = opts->ulsc_m1;
272dd191f37Speter ulsc.d = opts->ulsc_d;
273dd191f37Speter ulsc.m2 = opts->ulsc_m2;
274dd191f37Speter
275dd191f37Speter cl = hfsc_class_create(hif, &rtsc, &lssc, &ulsc,
276dd191f37Speter parent, a->qlimit, opts->flags, a->qid);
277dd191f37Speter if (cl == NULL)
278dd191f37Speter return (ENOMEM);
279dd191f37Speter
280dd191f37Speter return (0);
281dd191f37Speter }
282dd191f37Speter
283dd191f37Speter int
hfsc_remove_queue(struct pf_altq * a)284dd191f37Speter hfsc_remove_queue(struct pf_altq *a)
285dd191f37Speter {
286dd191f37Speter struct hfsc_if *hif;
287dd191f37Speter struct hfsc_class *cl;
288dd191f37Speter
289dd191f37Speter if ((hif = a->altq_disc) == NULL)
290dd191f37Speter return (EINVAL);
291dd191f37Speter
292dd191f37Speter if ((cl = clh_to_clp(hif, a->qid)) == NULL)
293dd191f37Speter return (EINVAL);
294dd191f37Speter
295dd191f37Speter return (hfsc_class_destroy(cl));
296dd191f37Speter }
297dd191f37Speter
298dd191f37Speter int
hfsc_getqstats(struct pf_altq * a,void * ubuf,int * nbytes)299dd191f37Speter hfsc_getqstats(struct pf_altq *a, void *ubuf, int *nbytes)
300dd191f37Speter {
301dd191f37Speter struct hfsc_if *hif;
302dd191f37Speter struct hfsc_class *cl;
303dd191f37Speter struct hfsc_classstats stats;
304dd191f37Speter int error = 0;
305dd191f37Speter
306dd191f37Speter if ((hif = altq_lookup(a->ifname, ALTQT_HFSC)) == NULL)
307dd191f37Speter return (EBADF);
308dd191f37Speter
309dd191f37Speter if ((cl = clh_to_clp(hif, a->qid)) == NULL)
310dd191f37Speter return (EINVAL);
311dd191f37Speter
312dd191f37Speter if (*nbytes < sizeof(stats))
313dd191f37Speter return (EINVAL);
314dd191f37Speter
315b9305616Sriastradh memset(&stats, 0, sizeof(stats));
316dd191f37Speter get_class_stats(&stats, cl);
317dd191f37Speter
31853524e44Schristos if ((error = copyout((void *)&stats, ubuf, sizeof(stats))) != 0)
319dd191f37Speter return (error);
320dd191f37Speter *nbytes = sizeof(stats);
321dd191f37Speter return (0);
322dd191f37Speter }
323463fbff4Speter #endif /* NPF > 0 */
324dd191f37Speter
32568de460fSthorpej /*
32668de460fSthorpej * bring the interface back to the initial state by discarding
32768de460fSthorpej * all the filters and classes except the root class.
32868de460fSthorpej */
32968de460fSthorpej static int
hfsc_clear_interface(struct hfsc_if * hif)330dd191f37Speter hfsc_clear_interface(struct hfsc_if *hif)
33168de460fSthorpej {
33268de460fSthorpej struct hfsc_class *cl;
33368de460fSthorpej
334dd191f37Speter #ifdef ALTQ3_COMPAT
33568de460fSthorpej /* free the filters for this interface */
33668de460fSthorpej acc_discard_filters(&hif->hif_classifier, NULL, 1);
337dd191f37Speter #endif
33868de460fSthorpej
33968de460fSthorpej /* clear out the classes */
340dd191f37Speter while (hif->hif_rootclass != NULL &&
341dd191f37Speter (cl = hif->hif_rootclass->cl_children) != NULL) {
34268de460fSthorpej /*
34368de460fSthorpej * remove the first leaf class found in the hierarchy
34468de460fSthorpej * then start over
34568de460fSthorpej */
34668de460fSthorpej for (; cl != NULL; cl = hfsc_nextclass(cl)) {
34768de460fSthorpej if (!is_a_parent_class(cl)) {
34868de460fSthorpej (void)hfsc_class_destroy(cl);
34968de460fSthorpej break;
35068de460fSthorpej }
35168de460fSthorpej }
35268de460fSthorpej }
35368de460fSthorpej
35468de460fSthorpej return (0);
35568de460fSthorpej }
35668de460fSthorpej
35768de460fSthorpej static int
hfsc_request(struct ifaltq * ifq,int req,void * arg)358168cd830Schristos hfsc_request(struct ifaltq *ifq, int req, void *arg)
35968de460fSthorpej {
36068de460fSthorpej struct hfsc_if *hif = (struct hfsc_if *)ifq->altq_disc;
36168de460fSthorpej
36268de460fSthorpej switch (req) {
36368de460fSthorpej case ALTRQ_PURGE:
36468de460fSthorpej hfsc_purge(hif);
36568de460fSthorpej break;
36668de460fSthorpej }
36768de460fSthorpej return (0);
36868de460fSthorpej }
36968de460fSthorpej
37068de460fSthorpej /* discard all the queued packets on the interface */
37168de460fSthorpej static void
hfsc_purge(struct hfsc_if * hif)372dd191f37Speter hfsc_purge(struct hfsc_if *hif)
37368de460fSthorpej {
37468de460fSthorpej struct hfsc_class *cl;
37568de460fSthorpej
37668de460fSthorpej for (cl = hif->hif_rootclass; cl != NULL; cl = hfsc_nextclass(cl))
37768de460fSthorpej if (!qempty(cl->cl_q))
37868de460fSthorpej hfsc_purgeq(cl);
37968de460fSthorpej if (ALTQ_IS_ENABLED(hif->hif_ifq))
38068de460fSthorpej hif->hif_ifq->ifq_len = 0;
38168de460fSthorpej }
38268de460fSthorpej
38368de460fSthorpej struct hfsc_class *
hfsc_class_create(struct hfsc_if * hif,struct service_curve * rsc,struct service_curve * fsc,struct service_curve * usc,struct hfsc_class * parent,int qlimit,int flags,int qid)384dd191f37Speter hfsc_class_create(struct hfsc_if *hif, struct service_curve *rsc,
385dd191f37Speter struct service_curve *fsc, struct service_curve *usc,
386dd191f37Speter struct hfsc_class *parent, int qlimit, int flags, int qid)
38768de460fSthorpej {
38868de460fSthorpej struct hfsc_class *cl, *p;
389dd191f37Speter int i, s;
390dd191f37Speter
391dd191f37Speter if (hif->hif_classes >= HFSC_MAX_CLASSES)
392dd191f37Speter return (NULL);
39368de460fSthorpej
39468de460fSthorpej #ifndef ALTQ_RED
39568de460fSthorpej if (flags & HFCF_RED) {
396dd191f37Speter #ifdef ALTQ_DEBUG
39768de460fSthorpej printf("hfsc_class_create: RED not configured for HFSC!\n");
398dd191f37Speter #endif
39968de460fSthorpej return (NULL);
40068de460fSthorpej }
40168de460fSthorpej #endif
40268de460fSthorpej
403d53df8e8Schristos cl = malloc(sizeof(struct hfsc_class), M_DEVBUF, M_WAITOK|M_ZERO);
40468de460fSthorpej if (cl == NULL)
40568de460fSthorpej return (NULL);
40668de460fSthorpej
407d53df8e8Schristos cl->cl_q = malloc(sizeof(class_queue_t), M_DEVBUF, M_WAITOK|M_ZERO);
40868de460fSthorpej if (cl->cl_q == NULL)
40968de460fSthorpej goto err_ret;
41068de460fSthorpej
41168de460fSthorpej cl->cl_actc = actlist_alloc();
41268de460fSthorpej if (cl->cl_actc == NULL)
41368de460fSthorpej goto err_ret;
41468de460fSthorpej
41568de460fSthorpej if (qlimit == 0)
41668de460fSthorpej qlimit = 50; /* use default */
41768de460fSthorpej qlimit(cl->cl_q) = qlimit;
41868de460fSthorpej qtype(cl->cl_q) = Q_DROPTAIL;
41968de460fSthorpej qlen(cl->cl_q) = 0;
42068de460fSthorpej cl->cl_flags = flags;
42168de460fSthorpej #ifdef ALTQ_RED
42268de460fSthorpej if (flags & (HFCF_RED|HFCF_RIO)) {
42368de460fSthorpej int red_flags, red_pkttime;
424dd191f37Speter u_int m2;
425dd191f37Speter
426dd191f37Speter m2 = 0;
427dd191f37Speter if (rsc != NULL && rsc->m2 > m2)
428dd191f37Speter m2 = rsc->m2;
429dd191f37Speter if (fsc != NULL && fsc->m2 > m2)
430dd191f37Speter m2 = fsc->m2;
431dd191f37Speter if (usc != NULL && usc->m2 > m2)
432dd191f37Speter m2 = usc->m2;
43368de460fSthorpej
43468de460fSthorpej red_flags = 0;
43568de460fSthorpej if (flags & HFCF_ECN)
43668de460fSthorpej red_flags |= REDF_ECN;
43768de460fSthorpej #ifdef ALTQ_RIO
43868de460fSthorpej if (flags & HFCF_CLEARDSCP)
43968de460fSthorpej red_flags |= RIOF_CLEARDSCP;
44068de460fSthorpej #endif
441dd191f37Speter if (m2 < 8)
44268de460fSthorpej red_pkttime = 1000 * 1000 * 1000; /* 1 sec */
44368de460fSthorpej else
44468de460fSthorpej red_pkttime = (int64_t)hif->hif_ifq->altq_ifp->if_mtu
445dd191f37Speter * 1000 * 1000 * 1000 / (m2 / 8);
44668de460fSthorpej if (flags & HFCF_RED) {
447dd191f37Speter cl->cl_red = red_alloc(0, 0,
448dd191f37Speter qlimit(cl->cl_q) * 10/100,
449dd191f37Speter qlimit(cl->cl_q) * 30/100,
45068de460fSthorpej red_flags, red_pkttime);
45168de460fSthorpej if (cl->cl_red != NULL)
45268de460fSthorpej qtype(cl->cl_q) = Q_RED;
45368de460fSthorpej }
45468de460fSthorpej #ifdef ALTQ_RIO
45568de460fSthorpej else {
45668de460fSthorpej cl->cl_red = (red_t *)rio_alloc(0, NULL,
45768de460fSthorpej red_flags, red_pkttime);
45868de460fSthorpej if (cl->cl_red != NULL)
45968de460fSthorpej qtype(cl->cl_q) = Q_RIO;
46068de460fSthorpej }
46168de460fSthorpej #endif
46268de460fSthorpej }
46368de460fSthorpej #endif /* ALTQ_RED */
46468de460fSthorpej
465dd191f37Speter if (rsc != NULL && (rsc->m1 != 0 || rsc->m2 != 0)) {
466d53df8e8Schristos cl->cl_rsc = malloc(sizeof(struct internal_sc), M_DEVBUF,
467d53df8e8Schristos M_WAITOK|M_ZERO);
46868de460fSthorpej if (cl->cl_rsc == NULL)
46968de460fSthorpej goto err_ret;
470dd191f37Speter sc2isc(rsc, cl->cl_rsc);
47168de460fSthorpej rtsc_init(&cl->cl_deadline, cl->cl_rsc, 0, 0);
47268de460fSthorpej rtsc_init(&cl->cl_eligible, cl->cl_rsc, 0, 0);
473dd191f37Speter }
474dd191f37Speter if (fsc != NULL && (fsc->m1 != 0 || fsc->m2 != 0)) {
475d53df8e8Schristos cl->cl_fsc = malloc(sizeof(struct internal_sc), M_DEVBUF,
476d53df8e8Schristos M_WAITOK|M_ZERO);
47768de460fSthorpej if (cl->cl_fsc == NULL)
47868de460fSthorpej goto err_ret;
479dd191f37Speter sc2isc(fsc, cl->cl_fsc);
48068de460fSthorpej rtsc_init(&cl->cl_virtual, cl->cl_fsc, 0, 0);
48168de460fSthorpej }
482dd191f37Speter if (usc != NULL && (usc->m1 != 0 || usc->m2 != 0)) {
483dd191f37Speter cl->cl_usc = malloc(sizeof(struct internal_sc), M_DEVBUF,
484dd191f37Speter M_WAITOK|M_ZERO);
485dd191f37Speter if (cl->cl_usc == NULL)
486dd191f37Speter goto err_ret;
487dd191f37Speter sc2isc(usc, cl->cl_usc);
488dd191f37Speter rtsc_init(&cl->cl_ulimit, cl->cl_usc, 0, 0);
489dd191f37Speter }
49068de460fSthorpej
49168de460fSthorpej cl->cl_id = hif->hif_classid++;
492dd191f37Speter cl->cl_handle = qid;
49368de460fSthorpej cl->cl_hif = hif;
49468de460fSthorpej cl->cl_parent = parent;
49568de460fSthorpej
496bf2dcec4Sthorpej s = splnet();
49768de460fSthorpej hif->hif_classes++;
498dd191f37Speter
499dd191f37Speter /*
500dd191f37Speter * find a free slot in the class table. if the slot matching
501dd191f37Speter * the lower bits of qid is free, use this slot. otherwise,
502dd191f37Speter * use the first free slot.
503dd191f37Speter */
504dd191f37Speter i = qid % HFSC_MAX_CLASSES;
505dd191f37Speter if (hif->hif_class_tbl[i] == NULL)
506dd191f37Speter hif->hif_class_tbl[i] = cl;
507dd191f37Speter else {
508dd191f37Speter for (i = 0; i < HFSC_MAX_CLASSES; i++)
509dd191f37Speter if (hif->hif_class_tbl[i] == NULL) {
510dd191f37Speter hif->hif_class_tbl[i] = cl;
511dd191f37Speter break;
512dd191f37Speter }
513dd191f37Speter if (i == HFSC_MAX_CLASSES) {
514dd191f37Speter splx(s);
515dd191f37Speter goto err_ret;
516dd191f37Speter }
517dd191f37Speter }
518dd191f37Speter
51968de460fSthorpej if (flags & HFCF_DEFAULTCLASS)
52068de460fSthorpej hif->hif_defaultclass = cl;
52168de460fSthorpej
52268de460fSthorpej if (parent == NULL) {
52368de460fSthorpej /* this is root class */
524dd191f37Speter hif->hif_rootclass = cl;
525dd191f37Speter } else {
526dd191f37Speter /* add this class to the children list of the parent */
527dd191f37Speter if ((p = parent->cl_children) == NULL)
52868de460fSthorpej parent->cl_children = cl;
52968de460fSthorpej else {
53068de460fSthorpej while (p->cl_siblings != NULL)
53168de460fSthorpej p = p->cl_siblings;
53268de460fSthorpej p->cl_siblings = cl;
53368de460fSthorpej }
534dd191f37Speter }
53568de460fSthorpej splx(s);
53668de460fSthorpej
53768de460fSthorpej return (cl);
53868de460fSthorpej
53968de460fSthorpej err_ret:
54068de460fSthorpej if (cl->cl_actc != NULL)
54168de460fSthorpej actlist_destroy(cl->cl_actc);
54268de460fSthorpej if (cl->cl_red != NULL) {
54368de460fSthorpej #ifdef ALTQ_RIO
54468de460fSthorpej if (q_is_rio(cl->cl_q))
54568de460fSthorpej rio_destroy((rio_t *)cl->cl_red);
54668de460fSthorpej #endif
54768de460fSthorpej #ifdef ALTQ_RED
54868de460fSthorpej if (q_is_red(cl->cl_q))
54968de460fSthorpej red_destroy(cl->cl_red);
55068de460fSthorpej #endif
55168de460fSthorpej }
55268de460fSthorpej if (cl->cl_fsc != NULL)
553d53df8e8Schristos free(cl->cl_fsc, M_DEVBUF);
55468de460fSthorpej if (cl->cl_rsc != NULL)
555d53df8e8Schristos free(cl->cl_rsc, M_DEVBUF);
556dd191f37Speter if (cl->cl_usc != NULL)
557dd191f37Speter free(cl->cl_usc, M_DEVBUF);
55868de460fSthorpej if (cl->cl_q != NULL)
559d53df8e8Schristos free(cl->cl_q, M_DEVBUF);
560d53df8e8Schristos free(cl, M_DEVBUF);
56168de460fSthorpej return (NULL);
56268de460fSthorpej }
56368de460fSthorpej
56468de460fSthorpej static int
hfsc_class_destroy(struct hfsc_class * cl)565dd191f37Speter hfsc_class_destroy(struct hfsc_class *cl)
56668de460fSthorpej {
567dd191f37Speter int i, s;
568dd191f37Speter
569dd191f37Speter if (cl == NULL)
570dd191f37Speter return (0);
57168de460fSthorpej
57268de460fSthorpej if (is_a_parent_class(cl))
57368de460fSthorpej return (EBUSY);
57468de460fSthorpej
575bf2dcec4Sthorpej s = splnet();
57668de460fSthorpej
577dd191f37Speter #ifdef ALTQ3_COMPAT
57868de460fSthorpej /* delete filters referencing to this class */
57968de460fSthorpej acc_discard_filters(&cl->cl_hif->hif_classifier, cl, 0);
580dd191f37Speter #endif /* ALTQ3_COMPAT */
58168de460fSthorpej
58268de460fSthorpej if (!qempty(cl->cl_q))
58368de460fSthorpej hfsc_purgeq(cl);
58468de460fSthorpej
58568de460fSthorpej if (cl->cl_parent == NULL) {
58668de460fSthorpej /* this is root class */
58768de460fSthorpej } else {
58868de460fSthorpej struct hfsc_class *p = cl->cl_parent->cl_children;
58968de460fSthorpej
59068de460fSthorpej if (p == cl)
59168de460fSthorpej cl->cl_parent->cl_children = cl->cl_siblings;
59268de460fSthorpej else do {
59368de460fSthorpej if (p->cl_siblings == cl) {
59468de460fSthorpej p->cl_siblings = cl->cl_siblings;
59568de460fSthorpej break;
59668de460fSthorpej }
59768de460fSthorpej } while ((p = p->cl_siblings) != NULL);
59868de460fSthorpej ASSERT(p != NULL);
59968de460fSthorpej }
600dd191f37Speter
601dd191f37Speter for (i = 0; i < HFSC_MAX_CLASSES; i++)
602dd191f37Speter if (cl->cl_hif->hif_class_tbl[i] == cl) {
603dd191f37Speter cl->cl_hif->hif_class_tbl[i] = NULL;
604dd191f37Speter break;
605dd191f37Speter }
606dd191f37Speter
60768de460fSthorpej cl->cl_hif->hif_classes--;
60868de460fSthorpej splx(s);
60968de460fSthorpej
61068de460fSthorpej actlist_destroy(cl->cl_actc);
61168de460fSthorpej
61268de460fSthorpej if (cl->cl_red != NULL) {
61368de460fSthorpej #ifdef ALTQ_RIO
61468de460fSthorpej if (q_is_rio(cl->cl_q))
61568de460fSthorpej rio_destroy((rio_t *)cl->cl_red);
61668de460fSthorpej #endif
61768de460fSthorpej #ifdef ALTQ_RED
61868de460fSthorpej if (q_is_red(cl->cl_q))
61968de460fSthorpej red_destroy(cl->cl_red);
62068de460fSthorpej #endif
62168de460fSthorpej }
622dd191f37Speter
623dd191f37Speter if (cl == cl->cl_hif->hif_rootclass)
624dd191f37Speter cl->cl_hif->hif_rootclass = NULL;
625dd191f37Speter if (cl == cl->cl_hif->hif_defaultclass)
626dd191f37Speter cl->cl_hif->hif_defaultclass = NULL;
627dd191f37Speter
628dd191f37Speter if (cl->cl_usc != NULL)
629dd191f37Speter free(cl->cl_usc, M_DEVBUF);
63068de460fSthorpej if (cl->cl_fsc != NULL)
631d53df8e8Schristos free(cl->cl_fsc, M_DEVBUF);
63268de460fSthorpej if (cl->cl_rsc != NULL)
633d53df8e8Schristos free(cl->cl_rsc, M_DEVBUF);
634d53df8e8Schristos free(cl->cl_q, M_DEVBUF);
635d53df8e8Schristos free(cl, M_DEVBUF);
63668de460fSthorpej
63768de460fSthorpej return (0);
63868de460fSthorpej }
63968de460fSthorpej
64068de460fSthorpej /*
64168de460fSthorpej * hfsc_nextclass returns the next class in the tree.
64268de460fSthorpej * usage:
64368de460fSthorpej * for (cl = hif->hif_rootclass; cl != NULL; cl = hfsc_nextclass(cl))
64468de460fSthorpej * do_something;
64568de460fSthorpej */
64668de460fSthorpej static struct hfsc_class *
hfsc_nextclass(struct hfsc_class * cl)647dd191f37Speter hfsc_nextclass(struct hfsc_class *cl)
64868de460fSthorpej {
64968de460fSthorpej if (cl->cl_children != NULL)
65068de460fSthorpej cl = cl->cl_children;
65168de460fSthorpej else if (cl->cl_siblings != NULL)
65268de460fSthorpej cl = cl->cl_siblings;
65368de460fSthorpej else {
65468de460fSthorpej while ((cl = cl->cl_parent) != NULL)
65568de460fSthorpej if (cl->cl_siblings) {
65668de460fSthorpej cl = cl->cl_siblings;
65768de460fSthorpej break;
65868de460fSthorpej }
65968de460fSthorpej }
66068de460fSthorpej
66168de460fSthorpej return (cl);
66268de460fSthorpej }
66368de460fSthorpej
66468de460fSthorpej /*
66568de460fSthorpej * hfsc_enqueue is an enqueue function to be registered to
66668de460fSthorpej * (*altq_enqueue) in struct ifaltq.
66768de460fSthorpej */
66868de460fSthorpej static int
hfsc_enqueue(struct ifaltq * ifq,struct mbuf * m)66925937c0dSknakahara hfsc_enqueue(struct ifaltq *ifq, struct mbuf *m)
67068de460fSthorpej {
67125937c0dSknakahara struct altq_pktattr pktattr;
67268de460fSthorpej struct hfsc_if *hif = (struct hfsc_if *)ifq->altq_disc;
67368de460fSthorpej struct hfsc_class *cl;
674dd191f37Speter struct m_tag *t;
67568de460fSthorpej int len;
67668de460fSthorpej
67768de460fSthorpej /* grab class set by classifier */
678dd191f37Speter if ((m->m_flags & M_PKTHDR) == 0) {
679dd191f37Speter /* should not happen */
680dd191f37Speter printf("altq: packet for %s does not have pkthdr\n",
681dd191f37Speter ifq->altq_ifp->if_xname);
682dd191f37Speter m_freem(m);
683dd191f37Speter return (ENOBUFS);
684dd191f37Speter }
685dd191f37Speter cl = NULL;
68625d59b3bSmaxv if ((t = m_tag_find(m, PACKET_TAG_ALTQ_QID)) != NULL)
687dd191f37Speter cl = clh_to_clp(hif, ((struct altq_tag *)(t+1))->qid);
688dd191f37Speter #ifdef ALTQ3_COMPAT
68925937c0dSknakahara else if ((ifq->altq_flags & ALTQF_CLASSIFY))
69025937c0dSknakahara cl = m->m_pkthdr.pattr_class;
691dd191f37Speter #endif
692dd191f37Speter if (cl == NULL || is_a_parent_class(cl)) {
69368de460fSthorpej cl = hif->hif_defaultclass;
694dd191f37Speter if (cl == NULL) {
695dd191f37Speter m_freem(m);
696dd191f37Speter return (ENOBUFS);
697dd191f37Speter }
698dd191f37Speter }
699dd191f37Speter #ifdef ALTQ3_COMPAT
70025937c0dSknakahara if (m->m_pkthdr.pattr_af != AF_UNSPEC) {
70125937c0dSknakahara pktattr.pattr_class = m->m_pkthdr.pattr_class;
70225937c0dSknakahara pktattr.pattr_af = m->m_pkthdr.pattr_af;
70325937c0dSknakahara pktattr.pattr_hdr = m->m_pkthdr.pattr_hdr;
70425937c0dSknakahara
70525937c0dSknakahara cl->cl_pktattr = &pktattr; /* save proto hdr used by ECN */
70625937c0dSknakahara } else
707dd191f37Speter #endif
708dd191f37Speter cl->cl_pktattr = NULL;
70968de460fSthorpej len = m_pktlen(m);
71068de460fSthorpej if (hfsc_addq(cl, m) != 0) {
71168de460fSthorpej /* drop occurred. mbuf was freed in hfsc_addq. */
71268de460fSthorpej PKTCNTR_ADD(&cl->cl_stats.drop_cnt, len);
71368de460fSthorpej return (ENOBUFS);
71468de460fSthorpej }
71568de460fSthorpej IFQ_INC_LEN(ifq);
71668de460fSthorpej cl->cl_hif->hif_packets++;
71768de460fSthorpej
71868de460fSthorpej /* successfully queued. */
71968de460fSthorpej if (qlen(cl->cl_q) == 1)
72068de460fSthorpej set_active(cl, m_pktlen(m));
72168de460fSthorpej
72268de460fSthorpej return (0);
72368de460fSthorpej }
72468de460fSthorpej
72568de460fSthorpej /*
72668de460fSthorpej * hfsc_dequeue is a dequeue function to be registered to
72768de460fSthorpej * (*altq_dequeue) in struct ifaltq.
72868de460fSthorpej *
72968de460fSthorpej * note: ALTDQ_POLL returns the next packet without removing the packet
73068de460fSthorpej * from the queue. ALTDQ_REMOVE is a normal dequeue operation.
73168de460fSthorpej * ALTDQ_REMOVE must return the same packet if called immediately
73268de460fSthorpej * after ALTDQ_POLL.
73368de460fSthorpej */
73468de460fSthorpej static struct mbuf *
hfsc_dequeue(struct ifaltq * ifq,int op)735dd191f37Speter hfsc_dequeue(struct ifaltq *ifq, int op)
73668de460fSthorpej {
73768de460fSthorpej struct hfsc_if *hif = (struct hfsc_if *)ifq->altq_disc;
73868de460fSthorpej struct hfsc_class *cl;
73968de460fSthorpej struct mbuf *m;
74068de460fSthorpej int len, next_len;
74168de460fSthorpej int realtime = 0;
742dd191f37Speter u_int64_t cur_time;
74368de460fSthorpej
74468de460fSthorpej if (hif->hif_packets == 0)
74568de460fSthorpej /* no packet in the tree */
74668de460fSthorpej return (NULL);
74768de460fSthorpej
748dd191f37Speter cur_time = read_machclk();
749dd191f37Speter
75068de460fSthorpej if (op == ALTDQ_REMOVE && hif->hif_pollcache != NULL) {
75168de460fSthorpej
75268de460fSthorpej cl = hif->hif_pollcache;
75368de460fSthorpej hif->hif_pollcache = NULL;
75468de460fSthorpej /* check if the class was scheduled by real-time criteria */
755dd191f37Speter if (cl->cl_rsc != NULL)
75668de460fSthorpej realtime = (cl->cl_e <= cur_time);
75768de460fSthorpej } else {
75868de460fSthorpej /*
75968de460fSthorpej * if there are eligible classes, use real-time criteria.
76068de460fSthorpej * find the class with the minimum deadline among
76168de460fSthorpej * the eligible classes.
76268de460fSthorpej */
763dd191f37Speter if ((cl = ellist_get_mindl(hif->hif_eligible, cur_time))
764dd191f37Speter != NULL) {
76568de460fSthorpej realtime = 1;
76668de460fSthorpej } else {
767dd191f37Speter #ifdef ALTQ_DEBUG
768dd191f37Speter int fits = 0;
769dd191f37Speter #endif
77068de460fSthorpej /*
77168de460fSthorpej * use link-sharing criteria
77268de460fSthorpej * get the class with the minimum vt in the hierarchy
77368de460fSthorpej */
77468de460fSthorpej cl = hif->hif_rootclass;
77568de460fSthorpej while (is_a_parent_class(cl)) {
776dd191f37Speter
777dd191f37Speter cl = actlist_firstfit(cl, cur_time);
778dd191f37Speter if (cl == NULL) {
779dd191f37Speter #ifdef ALTQ_DEBUG
780dd191f37Speter if (fits > 0)
781dd191f37Speter printf("%d fit but none found\n",fits);
782dd191f37Speter #endif
78368de460fSthorpej return (NULL);
78468de460fSthorpej }
785dd191f37Speter /*
786dd191f37Speter * update parent's cl_cvtmin.
787dd191f37Speter * don't update if the new vt is smaller.
788dd191f37Speter */
789dd191f37Speter if (cl->cl_parent->cl_cvtmin < cl->cl_vt)
790dd191f37Speter cl->cl_parent->cl_cvtmin = cl->cl_vt;
791dd191f37Speter #ifdef ALTQ_DEBUG
792dd191f37Speter fits++;
793dd191f37Speter #endif
794dd191f37Speter }
79568de460fSthorpej }
79668de460fSthorpej
79768de460fSthorpej if (op == ALTDQ_POLL) {
79868de460fSthorpej hif->hif_pollcache = cl;
79968de460fSthorpej m = hfsc_pollq(cl);
80068de460fSthorpej return (m);
80168de460fSthorpej }
80268de460fSthorpej }
80368de460fSthorpej
80468de460fSthorpej m = hfsc_getq(cl);
805dd191f37Speter if (m == NULL)
806dd191f37Speter panic("hfsc_dequeue:");
80768de460fSthorpej len = m_pktlen(m);
80868de460fSthorpej cl->cl_hif->hif_packets--;
80968de460fSthorpej IFQ_DEC_LEN(ifq);
81068de460fSthorpej PKTCNTR_ADD(&cl->cl_stats.xmit_cnt, len);
81168de460fSthorpej
812dd191f37Speter update_vf(cl, len, cur_time);
81368de460fSthorpej if (realtime)
81468de460fSthorpej cl->cl_cumul += len;
81568de460fSthorpej
81668de460fSthorpej if (!qempty(cl->cl_q)) {
81768de460fSthorpej if (cl->cl_rsc != NULL) {
81868de460fSthorpej /* update ed */
81968de460fSthorpej next_len = m_pktlen(qhead(cl->cl_q));
82068de460fSthorpej
82168de460fSthorpej if (realtime)
82268de460fSthorpej update_ed(cl, next_len);
82368de460fSthorpej else
82468de460fSthorpej update_d(cl, next_len);
82568de460fSthorpej }
82668de460fSthorpej } else {
82768de460fSthorpej /* the class becomes passive */
82868de460fSthorpej set_passive(cl);
82968de460fSthorpej }
83068de460fSthorpej
83168de460fSthorpej return (m);
83268de460fSthorpej }
83368de460fSthorpej
83468de460fSthorpej static int
hfsc_addq(struct hfsc_class * cl,struct mbuf * m)835dd191f37Speter hfsc_addq(struct hfsc_class *cl, struct mbuf *m)
83668de460fSthorpej {
83768de460fSthorpej
83868de460fSthorpej #ifdef ALTQ_RIO
83968de460fSthorpej if (q_is_rio(cl->cl_q))
84068de460fSthorpej return rio_addq((rio_t *)cl->cl_red, cl->cl_q,
84168de460fSthorpej m, cl->cl_pktattr);
84268de460fSthorpej #endif
84368de460fSthorpej #ifdef ALTQ_RED
84468de460fSthorpej if (q_is_red(cl->cl_q))
84568de460fSthorpej return red_addq(cl->cl_red, cl->cl_q, m, cl->cl_pktattr);
84668de460fSthorpej #endif
84768de460fSthorpej if (qlen(cl->cl_q) >= qlimit(cl->cl_q)) {
84868de460fSthorpej m_freem(m);
84968de460fSthorpej return (-1);
85068de460fSthorpej }
85168de460fSthorpej
85268de460fSthorpej if (cl->cl_flags & HFCF_CLEARDSCP)
85368de460fSthorpej write_dsfield(m, cl->cl_pktattr, 0);
85468de460fSthorpej
85568de460fSthorpej _addq(cl->cl_q, m);
85668de460fSthorpej
85768de460fSthorpej return (0);
85868de460fSthorpej }
85968de460fSthorpej
86068de460fSthorpej static struct mbuf *
hfsc_getq(struct hfsc_class * cl)861dd191f37Speter hfsc_getq(struct hfsc_class *cl)
86268de460fSthorpej {
86368de460fSthorpej #ifdef ALTQ_RIO
86468de460fSthorpej if (q_is_rio(cl->cl_q))
86568de460fSthorpej return rio_getq((rio_t *)cl->cl_red, cl->cl_q);
86668de460fSthorpej #endif
86768de460fSthorpej #ifdef ALTQ_RED
86868de460fSthorpej if (q_is_red(cl->cl_q))
86968de460fSthorpej return red_getq(cl->cl_red, cl->cl_q);
87068de460fSthorpej #endif
87168de460fSthorpej return _getq(cl->cl_q);
87268de460fSthorpej }
87368de460fSthorpej
87468de460fSthorpej static struct mbuf *
hfsc_pollq(struct hfsc_class * cl)875dd191f37Speter hfsc_pollq(struct hfsc_class *cl)
87668de460fSthorpej {
87768de460fSthorpej return qhead(cl->cl_q);
87868de460fSthorpej }
87968de460fSthorpej
88068de460fSthorpej static void
hfsc_purgeq(struct hfsc_class * cl)881dd191f37Speter hfsc_purgeq(struct hfsc_class *cl)
88268de460fSthorpej {
88368de460fSthorpej struct mbuf *m;
88468de460fSthorpej
88568de460fSthorpej if (qempty(cl->cl_q))
88668de460fSthorpej return;
88768de460fSthorpej
88868de460fSthorpej while ((m = _getq(cl->cl_q)) != NULL) {
88968de460fSthorpej PKTCNTR_ADD(&cl->cl_stats.drop_cnt, m_pktlen(m));
89068de460fSthorpej m_freem(m);
891dd191f37Speter cl->cl_hif->hif_packets--;
892dd191f37Speter IFQ_DEC_LEN(cl->cl_hif->hif_ifq);
89368de460fSthorpej }
89468de460fSthorpej ASSERT(qlen(cl->cl_q) == 0);
89568de460fSthorpej
896dd191f37Speter update_vf(cl, 0, 0); /* remove cl from the actlist */
89768de460fSthorpej set_passive(cl);
89868de460fSthorpej }
89968de460fSthorpej
90068de460fSthorpej static void
set_active(struct hfsc_class * cl,int len)901dd191f37Speter set_active(struct hfsc_class *cl, int len)
90268de460fSthorpej {
90368de460fSthorpej if (cl->cl_rsc != NULL)
90468de460fSthorpej init_ed(cl, len);
90568de460fSthorpej if (cl->cl_fsc != NULL)
906dd191f37Speter init_vf(cl, len);
90768de460fSthorpej
90868de460fSthorpej cl->cl_stats.period++;
90968de460fSthorpej }
91068de460fSthorpej
91168de460fSthorpej static void
set_passive(struct hfsc_class * cl)912dd191f37Speter set_passive(struct hfsc_class *cl)
91368de460fSthorpej {
91468de460fSthorpej if (cl->cl_rsc != NULL)
91568de460fSthorpej ellist_remove(cl);
91668de460fSthorpej
917dd191f37Speter /*
918dd191f37Speter * actlist is now handled in update_vf() so that update_vf(cl, 0, 0)
919dd191f37Speter * needs to be called explicitly to remove a class from actlist
920dd191f37Speter */
92168de460fSthorpej }
92268de460fSthorpej
92368de460fSthorpej static void
init_ed(struct hfsc_class * cl,int next_len)924dd191f37Speter init_ed(struct hfsc_class *cl, int next_len)
92568de460fSthorpej {
92668de460fSthorpej u_int64_t cur_time;
92768de460fSthorpej
92868de460fSthorpej cur_time = read_machclk();
92968de460fSthorpej
93068de460fSthorpej /* update the deadline curve */
93168de460fSthorpej rtsc_min(&cl->cl_deadline, cl->cl_rsc, cur_time, cl->cl_cumul);
93268de460fSthorpej
93368de460fSthorpej /*
93468de460fSthorpej * update the eligible curve.
93568de460fSthorpej * for concave, it is equal to the deadline curve.
93668de460fSthorpej * for convex, it is a linear curve with slope m2.
93768de460fSthorpej */
93868de460fSthorpej cl->cl_eligible = cl->cl_deadline;
93968de460fSthorpej if (cl->cl_rsc->sm1 <= cl->cl_rsc->sm2) {
94068de460fSthorpej cl->cl_eligible.dx = 0;
94168de460fSthorpej cl->cl_eligible.dy = 0;
94268de460fSthorpej }
94368de460fSthorpej
94468de460fSthorpej /* compute e and d */
94568de460fSthorpej cl->cl_e = rtsc_y2x(&cl->cl_eligible, cl->cl_cumul);
94668de460fSthorpej cl->cl_d = rtsc_y2x(&cl->cl_deadline, cl->cl_cumul + next_len);
94768de460fSthorpej
94868de460fSthorpej ellist_insert(cl);
94968de460fSthorpej }
95068de460fSthorpej
95168de460fSthorpej static void
update_ed(struct hfsc_class * cl,int next_len)952dd191f37Speter update_ed(struct hfsc_class *cl, int next_len)
95368de460fSthorpej {
95468de460fSthorpej cl->cl_e = rtsc_y2x(&cl->cl_eligible, cl->cl_cumul);
95568de460fSthorpej cl->cl_d = rtsc_y2x(&cl->cl_deadline, cl->cl_cumul + next_len);
95668de460fSthorpej
95768de460fSthorpej ellist_update(cl);
95868de460fSthorpej }
95968de460fSthorpej
96068de460fSthorpej static void
update_d(struct hfsc_class * cl,int next_len)961dd191f37Speter update_d(struct hfsc_class *cl, int next_len)
96268de460fSthorpej {
96368de460fSthorpej cl->cl_d = rtsc_y2x(&cl->cl_deadline, cl->cl_cumul + next_len);
96468de460fSthorpej }
96568de460fSthorpej
96668de460fSthorpej static void
init_vf(struct hfsc_class * cl,int len)967168cd830Schristos init_vf(struct hfsc_class *cl, int len)
96868de460fSthorpej {
969dd191f37Speter struct hfsc_class *max_cl, *p;
970dd191f37Speter u_int64_t vt, f, cur_time;
971dd191f37Speter int go_active;
97268de460fSthorpej
973dd191f37Speter cur_time = 0;
974dd191f37Speter go_active = 1;
975dd191f37Speter for ( ; cl->cl_parent != NULL; cl = cl->cl_parent) {
97668de460fSthorpej
977dd191f37Speter if (go_active && cl->cl_nactive++ == 0)
978dd191f37Speter go_active = 1;
979dd191f37Speter else
980dd191f37Speter go_active = 0;
98168de460fSthorpej
982dd191f37Speter if (go_active) {
98368de460fSthorpej max_cl = actlist_last(cl->cl_parent->cl_actc);
984dd191f37Speter if (max_cl != NULL) {
985dd191f37Speter /*
986dd191f37Speter * set vt to the average of the min and max
987dd191f37Speter * classes. if the parent's period didn't
988dd191f37Speter * change, don't decrease vt of the class.
989dd191f37Speter */
990dd191f37Speter vt = max_cl->cl_vt;
991dd191f37Speter if (cl->cl_parent->cl_cvtmin != 0)
992dd191f37Speter vt = (cl->cl_parent->cl_cvtmin + vt)/2;
993dd191f37Speter
994dd191f37Speter if (cl->cl_parent->cl_vtperiod !=
995dd191f37Speter cl->cl_parentperiod || vt > cl->cl_vt)
99668de460fSthorpej cl->cl_vt = vt;
997dd191f37Speter } else {
998dd191f37Speter /*
999dd191f37Speter * first child for a new parent backlog period.
1000dd191f37Speter * add parent's cvtmax to vtoff of children
1001dd191f37Speter * to make a new vt (vtoff + vt) larger than
1002dd191f37Speter * the vt in the last period for all children.
1003dd191f37Speter */
1004dd191f37Speter vt = cl->cl_parent->cl_cvtmax;
1005dd191f37Speter for (p = cl->cl_parent->cl_children; p != NULL;
1006dd191f37Speter p = p->cl_siblings)
1007dd191f37Speter p->cl_vtoff += vt;
1008dd191f37Speter cl->cl_vt = 0;
1009dd191f37Speter cl->cl_parent->cl_cvtmax = 0;
1010dd191f37Speter cl->cl_parent->cl_cvtmin = 0;
101168de460fSthorpej }
1012dd191f37Speter cl->cl_initvt = cl->cl_vt;
101368de460fSthorpej
101468de460fSthorpej /* update the virtual curve */
1015dd191f37Speter vt = cl->cl_vt + cl->cl_vtoff;
1016dd191f37Speter rtsc_min(&cl->cl_virtual, cl->cl_fsc, vt, cl->cl_total);
1017dd191f37Speter if (cl->cl_virtual.x == vt) {
1018dd191f37Speter cl->cl_virtual.x -= cl->cl_vtoff;
1019dd191f37Speter cl->cl_vtoff = 0;
1020dd191f37Speter }
1021dd191f37Speter cl->cl_vtadj = 0;
102268de460fSthorpej
102368de460fSthorpej cl->cl_vtperiod++; /* increment vt period */
102468de460fSthorpej cl->cl_parentperiod = cl->cl_parent->cl_vtperiod;
102568de460fSthorpej if (cl->cl_parent->cl_nactive == 0)
102668de460fSthorpej cl->cl_parentperiod++;
1027dd191f37Speter cl->cl_f = 0;
102868de460fSthorpej
102968de460fSthorpej actlist_insert(cl);
103068de460fSthorpej
1031dd191f37Speter if (cl->cl_usc != NULL) {
1032dd191f37Speter /* class has upper limit curve */
1033dd191f37Speter if (cur_time == 0)
1034dd191f37Speter cur_time = read_machclk();
1035dd191f37Speter
1036dd191f37Speter /* update the ulimit curve */
1037dd191f37Speter rtsc_min(&cl->cl_ulimit, cl->cl_usc, cur_time,
1038dd191f37Speter cl->cl_total);
1039dd191f37Speter /* compute myf */
1040dd191f37Speter cl->cl_myf = rtsc_y2x(&cl->cl_ulimit,
1041dd191f37Speter cl->cl_total);
1042dd191f37Speter cl->cl_myfadj = 0;
1043dd191f37Speter }
1044dd191f37Speter }
1045dd191f37Speter
1046dd191f37Speter if (cl->cl_myf > cl->cl_cfmin)
1047dd191f37Speter f = cl->cl_myf;
1048dd191f37Speter else
1049dd191f37Speter f = cl->cl_cfmin;
1050dd191f37Speter if (f != cl->cl_f) {
1051dd191f37Speter cl->cl_f = f;
1052dd191f37Speter update_cfmin(cl->cl_parent);
1053dd191f37Speter }
105468de460fSthorpej }
105568de460fSthorpej }
105668de460fSthorpej
105768de460fSthorpej static void
update_vf(struct hfsc_class * cl,int len,u_int64_t cur_time)1058dd191f37Speter update_vf(struct hfsc_class *cl, int len, u_int64_t cur_time)
105968de460fSthorpej {
1060dd191f37Speter u_int64_t f, myf_bound, delta;
1061dd191f37Speter int go_passive;
1062dd191f37Speter
1063dd191f37Speter go_passive = qempty(cl->cl_q);
1064dd191f37Speter
1065dd191f37Speter for (; cl->cl_parent != NULL; cl = cl->cl_parent) {
106668de460fSthorpej
106768de460fSthorpej cl->cl_total += len;
106868de460fSthorpej
1069dd191f37Speter if (cl->cl_fsc == NULL || cl->cl_nactive == 0)
1070dd191f37Speter continue;
1071dd191f37Speter
1072dd191f37Speter if (go_passive && --cl->cl_nactive == 0)
1073dd191f37Speter go_passive = 1;
1074dd191f37Speter else
1075dd191f37Speter go_passive = 0;
1076dd191f37Speter
1077dd191f37Speter if (go_passive) {
1078dd191f37Speter /* no more active child, going passive */
1079dd191f37Speter
1080dd191f37Speter /* update cvtmax of the parent class */
1081dd191f37Speter if (cl->cl_vt > cl->cl_parent->cl_cvtmax)
1082dd191f37Speter cl->cl_parent->cl_cvtmax = cl->cl_vt;
1083dd191f37Speter
1084dd191f37Speter /* remove this class from the vt list */
1085dd191f37Speter actlist_remove(cl);
1086dd191f37Speter
1087dd191f37Speter update_cfmin(cl->cl_parent);
1088dd191f37Speter
1089dd191f37Speter continue;
1090dd191f37Speter }
1091dd191f37Speter
1092dd191f37Speter /*
1093dd191f37Speter * update vt and f
1094dd191f37Speter */
1095dd191f37Speter cl->cl_vt = rtsc_y2x(&cl->cl_virtual, cl->cl_total)
1096dd191f37Speter - cl->cl_vtoff + cl->cl_vtadj;
1097dd191f37Speter
1098dd191f37Speter /*
1099dd191f37Speter * if vt of the class is smaller than cvtmin,
1100dd191f37Speter * the class was skipped in the past due to non-fit.
1101dd191f37Speter * if so, we need to adjust vtadj.
1102dd191f37Speter */
1103dd191f37Speter if (cl->cl_vt < cl->cl_parent->cl_cvtmin) {
1104dd191f37Speter cl->cl_vtadj += cl->cl_parent->cl_cvtmin - cl->cl_vt;
1105dd191f37Speter cl->cl_vt = cl->cl_parent->cl_cvtmin;
1106dd191f37Speter }
110768de460fSthorpej
110868de460fSthorpej /* update the vt list */
110968de460fSthorpej actlist_update(cl);
1110dd191f37Speter
1111dd191f37Speter if (cl->cl_usc != NULL) {
1112dd191f37Speter cl->cl_myf = cl->cl_myfadj
1113dd191f37Speter + rtsc_y2x(&cl->cl_ulimit, cl->cl_total);
1114dd191f37Speter
1115dd191f37Speter /*
1116dd191f37Speter * if myf lags behind by more than one clock tick
1117dd191f37Speter * from the current time, adjust myfadj to prevent
1118dd191f37Speter * a rate-limited class from going greedy.
1119dd191f37Speter * in a steady state under rate-limiting, myf
1120dd191f37Speter * fluctuates within one clock tick.
1121dd191f37Speter */
1122dd191f37Speter myf_bound = cur_time - machclk_per_tick;
1123dd191f37Speter if (cl->cl_myf < myf_bound) {
1124dd191f37Speter delta = cur_time - cl->cl_myf;
1125dd191f37Speter cl->cl_myfadj += delta;
1126dd191f37Speter cl->cl_myf += delta;
1127dd191f37Speter }
112868de460fSthorpej }
112968de460fSthorpej
1130dd191f37Speter /* cl_f is max(cl_myf, cl_cfmin) */
1131dd191f37Speter if (cl->cl_myf > cl->cl_cfmin)
1132dd191f37Speter f = cl->cl_myf;
1133dd191f37Speter else
1134dd191f37Speter f = cl->cl_cfmin;
1135dd191f37Speter if (f != cl->cl_f) {
1136dd191f37Speter cl->cl_f = f;
1137dd191f37Speter update_cfmin(cl->cl_parent);
113868de460fSthorpej }
113968de460fSthorpej }
1140dd191f37Speter }
1141dd191f37Speter
1142dd191f37Speter static void
update_cfmin(struct hfsc_class * cl)1143dd191f37Speter update_cfmin(struct hfsc_class *cl)
1144dd191f37Speter {
1145dd191f37Speter struct hfsc_class *p;
1146dd191f37Speter u_int64_t cfmin;
1147dd191f37Speter
1148dd191f37Speter if (TAILQ_EMPTY(cl->cl_actc)) {
1149dd191f37Speter cl->cl_cfmin = 0;
1150dd191f37Speter return;
1151dd191f37Speter }
1152dd191f37Speter cfmin = HT_INFINITY;
1153dd191f37Speter TAILQ_FOREACH(p, cl->cl_actc, cl_actlist) {
1154dd191f37Speter if (p->cl_f == 0) {
1155dd191f37Speter cl->cl_cfmin = 0;
1156dd191f37Speter return;
1157dd191f37Speter }
1158dd191f37Speter if (p->cl_f < cfmin)
1159dd191f37Speter cfmin = p->cl_f;
1160dd191f37Speter }
1161dd191f37Speter cl->cl_cfmin = cfmin;
1162dd191f37Speter }
116368de460fSthorpej
116468de460fSthorpej /*
116568de460fSthorpej * TAILQ based ellist and actlist implementation
116668de460fSthorpej * (ion wanted to make a calendar queue based implementation)
116768de460fSthorpej */
116868de460fSthorpej /*
116968de460fSthorpej * eligible list holds backlogged classes being sorted by their eligible times.
117068de460fSthorpej * there is one eligible list per interface.
117168de460fSthorpej */
117268de460fSthorpej
117368de460fSthorpej static ellist_t *
ellist_alloc(void)1174dd191f37Speter ellist_alloc(void)
117568de460fSthorpej {
117668de460fSthorpej ellist_t *head;
117768de460fSthorpej
1178d53df8e8Schristos head = malloc(sizeof(ellist_t), M_DEVBUF, M_WAITOK);
117968de460fSthorpej TAILQ_INIT(head);
118068de460fSthorpej return (head);
118168de460fSthorpej }
118268de460fSthorpej
118368de460fSthorpej static void
ellist_destroy(ellist_t * head)1184dd191f37Speter ellist_destroy(ellist_t *head)
118568de460fSthorpej {
1186d53df8e8Schristos free(head, M_DEVBUF);
118768de460fSthorpej }
118868de460fSthorpej
118968de460fSthorpej static void
ellist_insert(struct hfsc_class * cl)1190dd191f37Speter ellist_insert(struct hfsc_class *cl)
119168de460fSthorpej {
119268de460fSthorpej struct hfsc_if *hif = cl->cl_hif;
119368de460fSthorpej struct hfsc_class *p;
119468de460fSthorpej
119568de460fSthorpej /* check the last entry first */
119668de460fSthorpej if ((p = TAILQ_LAST(hif->hif_eligible, _eligible)) == NULL ||
119768de460fSthorpej p->cl_e <= cl->cl_e) {
119868de460fSthorpej TAILQ_INSERT_TAIL(hif->hif_eligible, cl, cl_ellist);
119968de460fSthorpej return;
120068de460fSthorpej }
120168de460fSthorpej
120268de460fSthorpej TAILQ_FOREACH(p, hif->hif_eligible, cl_ellist) {
120368de460fSthorpej if (cl->cl_e < p->cl_e) {
120468de460fSthorpej TAILQ_INSERT_BEFORE(p, cl, cl_ellist);
120568de460fSthorpej return;
120668de460fSthorpej }
120768de460fSthorpej }
120868de460fSthorpej ASSERT(0); /* should not reach here */
120968de460fSthorpej }
121068de460fSthorpej
121168de460fSthorpej static void
ellist_remove(struct hfsc_class * cl)1212dd191f37Speter ellist_remove(struct hfsc_class *cl)
121368de460fSthorpej {
121468de460fSthorpej struct hfsc_if *hif = cl->cl_hif;
121568de460fSthorpej
121668de460fSthorpej TAILQ_REMOVE(hif->hif_eligible, cl, cl_ellist);
121768de460fSthorpej }
121868de460fSthorpej
121968de460fSthorpej static void
ellist_update(struct hfsc_class * cl)1220dd191f37Speter ellist_update(struct hfsc_class *cl)
122168de460fSthorpej {
122268de460fSthorpej struct hfsc_if *hif = cl->cl_hif;
122368de460fSthorpej struct hfsc_class *p, *last;
122468de460fSthorpej
122568de460fSthorpej /*
122668de460fSthorpej * the eligible time of a class increases monotonically.
122768de460fSthorpej * if the next entry has a larger eligible time, nothing to do.
122868de460fSthorpej */
122968de460fSthorpej p = TAILQ_NEXT(cl, cl_ellist);
123068de460fSthorpej if (p == NULL || cl->cl_e <= p->cl_e)
123168de460fSthorpej return;
123268de460fSthorpej
123368de460fSthorpej /* check the last entry */
123468de460fSthorpej last = TAILQ_LAST(hif->hif_eligible, _eligible);
123568de460fSthorpej ASSERT(last != NULL);
123668de460fSthorpej if (last->cl_e <= cl->cl_e) {
123768de460fSthorpej TAILQ_REMOVE(hif->hif_eligible, cl, cl_ellist);
123868de460fSthorpej TAILQ_INSERT_TAIL(hif->hif_eligible, cl, cl_ellist);
123968de460fSthorpej return;
124068de460fSthorpej }
124168de460fSthorpej
124268de460fSthorpej /*
124368de460fSthorpej * the new position must be between the next entry
124468de460fSthorpej * and the last entry
124568de460fSthorpej */
124668de460fSthorpej while ((p = TAILQ_NEXT(p, cl_ellist)) != NULL) {
124768de460fSthorpej if (cl->cl_e < p->cl_e) {
124868de460fSthorpej TAILQ_REMOVE(hif->hif_eligible, cl, cl_ellist);
124968de460fSthorpej TAILQ_INSERT_BEFORE(p, cl, cl_ellist);
125068de460fSthorpej return;
125168de460fSthorpej }
125268de460fSthorpej }
125368de460fSthorpej ASSERT(0); /* should not reach here */
125468de460fSthorpej }
125568de460fSthorpej
125668de460fSthorpej /* find the class with the minimum deadline among the eligible classes */
125768de460fSthorpej struct hfsc_class *
ellist_get_mindl(ellist_t * head,u_int64_t cur_time)1258dd191f37Speter ellist_get_mindl(ellist_t *head, u_int64_t cur_time)
125968de460fSthorpej {
126068de460fSthorpej struct hfsc_class *p, *cl = NULL;
126168de460fSthorpej
126268de460fSthorpej TAILQ_FOREACH(p, head, cl_ellist) {
126368de460fSthorpej if (p->cl_e > cur_time)
126468de460fSthorpej break;
126568de460fSthorpej if (cl == NULL || p->cl_d < cl->cl_d)
126668de460fSthorpej cl = p;
126768de460fSthorpej }
126868de460fSthorpej return (cl);
126968de460fSthorpej }
127068de460fSthorpej
127168de460fSthorpej /*
127268de460fSthorpej * active children list holds backlogged child classes being sorted
127368de460fSthorpej * by their virtual time.
127468de460fSthorpej * each intermediate class has one active children list.
127568de460fSthorpej */
127668de460fSthorpej static actlist_t *
actlist_alloc(void)1277dd191f37Speter actlist_alloc(void)
127868de460fSthorpej {
127968de460fSthorpej actlist_t *head;
128068de460fSthorpej
1281d53df8e8Schristos head = malloc(sizeof(actlist_t), M_DEVBUF, M_WAITOK);
128268de460fSthorpej TAILQ_INIT(head);
128368de460fSthorpej return (head);
128468de460fSthorpej }
128568de460fSthorpej
128668de460fSthorpej static void
actlist_destroy(actlist_t * head)1287dd191f37Speter actlist_destroy(actlist_t *head)
128868de460fSthorpej {
1289d53df8e8Schristos free(head, M_DEVBUF);
129068de460fSthorpej }
129168de460fSthorpej static void
actlist_insert(struct hfsc_class * cl)1292dd191f37Speter actlist_insert(struct hfsc_class *cl)
129368de460fSthorpej {
129468de460fSthorpej struct hfsc_class *p;
129568de460fSthorpej
129668de460fSthorpej /* check the last entry first */
129768de460fSthorpej if ((p = TAILQ_LAST(cl->cl_parent->cl_actc, _active)) == NULL
129868de460fSthorpej || p->cl_vt <= cl->cl_vt) {
129968de460fSthorpej TAILQ_INSERT_TAIL(cl->cl_parent->cl_actc, cl, cl_actlist);
130068de460fSthorpej return;
130168de460fSthorpej }
130268de460fSthorpej
130368de460fSthorpej TAILQ_FOREACH(p, cl->cl_parent->cl_actc, cl_actlist) {
130468de460fSthorpej if (cl->cl_vt < p->cl_vt) {
130568de460fSthorpej TAILQ_INSERT_BEFORE(p, cl, cl_actlist);
130668de460fSthorpej return;
130768de460fSthorpej }
130868de460fSthorpej }
130968de460fSthorpej ASSERT(0); /* should not reach here */
131068de460fSthorpej }
131168de460fSthorpej
131268de460fSthorpej static void
actlist_remove(struct hfsc_class * cl)1313dd191f37Speter actlist_remove(struct hfsc_class *cl)
131468de460fSthorpej {
131568de460fSthorpej TAILQ_REMOVE(cl->cl_parent->cl_actc, cl, cl_actlist);
131668de460fSthorpej }
131768de460fSthorpej
131868de460fSthorpej static void
actlist_update(struct hfsc_class * cl)1319dd191f37Speter actlist_update(struct hfsc_class *cl)
132068de460fSthorpej {
132168de460fSthorpej struct hfsc_class *p, *last;
132268de460fSthorpej
132368de460fSthorpej /*
132468de460fSthorpej * the virtual time of a class increases monotonically during its
132568de460fSthorpej * backlogged period.
132668de460fSthorpej * if the next entry has a larger virtual time, nothing to do.
132768de460fSthorpej */
132868de460fSthorpej p = TAILQ_NEXT(cl, cl_actlist);
1329dd191f37Speter if (p == NULL || cl->cl_vt < p->cl_vt)
133068de460fSthorpej return;
133168de460fSthorpej
133268de460fSthorpej /* check the last entry */
133368de460fSthorpej last = TAILQ_LAST(cl->cl_parent->cl_actc, _active);
133468de460fSthorpej ASSERT(last != NULL);
133568de460fSthorpej if (last->cl_vt <= cl->cl_vt) {
133668de460fSthorpej TAILQ_REMOVE(cl->cl_parent->cl_actc, cl, cl_actlist);
133768de460fSthorpej TAILQ_INSERT_TAIL(cl->cl_parent->cl_actc, cl, cl_actlist);
133868de460fSthorpej return;
133968de460fSthorpej }
134068de460fSthorpej
134168de460fSthorpej /*
134268de460fSthorpej * the new position must be between the next entry
134368de460fSthorpej * and the last entry
134468de460fSthorpej */
134568de460fSthorpej while ((p = TAILQ_NEXT(p, cl_actlist)) != NULL) {
134668de460fSthorpej if (cl->cl_vt < p->cl_vt) {
134768de460fSthorpej TAILQ_REMOVE(cl->cl_parent->cl_actc, cl, cl_actlist);
134868de460fSthorpej TAILQ_INSERT_BEFORE(p, cl, cl_actlist);
134968de460fSthorpej return;
135068de460fSthorpej }
135168de460fSthorpej }
135268de460fSthorpej ASSERT(0); /* should not reach here */
135368de460fSthorpej }
135468de460fSthorpej
1355dd191f37Speter static struct hfsc_class *
actlist_firstfit(struct hfsc_class * cl,u_int64_t cur_time)1356dd191f37Speter actlist_firstfit(struct hfsc_class *cl, u_int64_t cur_time)
1357dd191f37Speter {
1358dd191f37Speter struct hfsc_class *p;
1359dd191f37Speter
1360dd191f37Speter TAILQ_FOREACH(p, cl->cl_actc, cl_actlist) {
1361dd191f37Speter if (p->cl_f <= cur_time)
1362dd191f37Speter return (p);
1363dd191f37Speter }
1364dd191f37Speter return (NULL);
1365dd191f37Speter }
1366dd191f37Speter
136768de460fSthorpej /*
136868de460fSthorpej * service curve support functions
136968de460fSthorpej *
137068de460fSthorpej * external service curve parameters
137168de460fSthorpej * m: bits/sec
137268de460fSthorpej * d: msec
137368de460fSthorpej * internal service curve parameters
137468de460fSthorpej * sm: (bytes/tsc_interval) << SM_SHIFT
137568de460fSthorpej * ism: (tsc_count/byte) << ISM_SHIFT
137668de460fSthorpej * dx: tsc_count
137768de460fSthorpej *
137868de460fSthorpej * SM_SHIFT and ISM_SHIFT are scaled in order to keep effective digits.
137968de460fSthorpej * we should be able to handle 100K-1Gbps linkspeed with 200Hz-1GHz CPU
138068de460fSthorpej * speed. SM_SHIFT and ISM_SHIFT are selected to have at least 3 effective
138168de460fSthorpej * digits in decimal using the following table.
138268de460fSthorpej *
1383dd191f37Speter * bits/sec 100Kbps 1Mbps 10Mbps 100Mbps 1Gbps
138468de460fSthorpej * ----------+-------------------------------------------------------
138568de460fSthorpej * bytes/nsec 12.5e-6 125e-6 1250e-6 12500e-6 125000e-6
138668de460fSthorpej * sm(500MHz) 25.0e-6 250e-6 2500e-6 25000e-6 250000e-6
138768de460fSthorpej * sm(200MHz) 62.5e-6 625e-6 6250e-6 62500e-6 625000e-6
138868de460fSthorpej *
138968de460fSthorpej * nsec/byte 80000 8000 800 80 8
139068de460fSthorpej * ism(500MHz) 40000 4000 400 40 4
139168de460fSthorpej * ism(200MHz) 16000 1600 160 16 1.6
139268de460fSthorpej */
139368de460fSthorpej #define SM_SHIFT 24
139468de460fSthorpej #define ISM_SHIFT 10
139568de460fSthorpej
1396dd191f37Speter #define SM_MASK ((1LL << SM_SHIFT) - 1)
1397dd191f37Speter #define ISM_MASK ((1LL << ISM_SHIFT) - 1)
139868de460fSthorpej
13995f1c88d7Sperry static inline u_int64_t
seg_x2y(u_int64_t x,u_int64_t sm)1400dd191f37Speter seg_x2y(u_int64_t x, u_int64_t sm)
140168de460fSthorpej {
140268de460fSthorpej u_int64_t y;
140368de460fSthorpej
1404dd191f37Speter /*
1405dd191f37Speter * compute
1406dd191f37Speter * y = x * sm >> SM_SHIFT
1407dd191f37Speter * but divide it for the upper and lower bits to avoid overflow
1408dd191f37Speter */
1409dd191f37Speter y = (x >> SM_SHIFT) * sm + (((x & SM_MASK) * sm) >> SM_SHIFT);
141068de460fSthorpej return (y);
141168de460fSthorpej }
141268de460fSthorpej
14135f1c88d7Sperry static inline u_int64_t
seg_y2x(u_int64_t y,u_int64_t ism)1414dd191f37Speter seg_y2x(u_int64_t y, u_int64_t ism)
141568de460fSthorpej {
141668de460fSthorpej u_int64_t x;
141768de460fSthorpej
141868de460fSthorpej if (y == 0)
141968de460fSthorpej x = 0;
1420dd191f37Speter else if (ism == HT_INFINITY)
1421dd191f37Speter x = HT_INFINITY;
1422dd191f37Speter else {
1423dd191f37Speter x = (y >> ISM_SHIFT) * ism
1424dd191f37Speter + (((y & ISM_MASK) * ism) >> ISM_SHIFT);
1425dd191f37Speter }
142668de460fSthorpej return (x);
142768de460fSthorpej }
142868de460fSthorpej
14295f1c88d7Sperry static inline u_int64_t
m2sm(u_int m)1430dd191f37Speter m2sm(u_int m)
143168de460fSthorpej {
143268de460fSthorpej u_int64_t sm;
143368de460fSthorpej
143468de460fSthorpej sm = ((u_int64_t)m << SM_SHIFT) / 8 / machclk_freq;
143568de460fSthorpej return (sm);
143668de460fSthorpej }
143768de460fSthorpej
14385f1c88d7Sperry static inline u_int64_t
m2ism(u_int m)1439dd191f37Speter m2ism(u_int m)
144068de460fSthorpej {
144168de460fSthorpej u_int64_t ism;
144268de460fSthorpej
144368de460fSthorpej if (m == 0)
1444dd191f37Speter ism = HT_INFINITY;
144568de460fSthorpej else
144668de460fSthorpej ism = ((u_int64_t)machclk_freq << ISM_SHIFT) * 8 / m;
144768de460fSthorpej return (ism);
144868de460fSthorpej }
144968de460fSthorpej
14505f1c88d7Sperry static inline u_int64_t
d2dx(u_int d)1451dd191f37Speter d2dx(u_int d)
145268de460fSthorpej {
145368de460fSthorpej u_int64_t dx;
145468de460fSthorpej
145568de460fSthorpej dx = ((u_int64_t)d * machclk_freq) / 1000;
145668de460fSthorpej return (dx);
145768de460fSthorpej }
145868de460fSthorpej
145968de460fSthorpej static u_int
sm2m(u_int64_t sm)1460dd191f37Speter sm2m(u_int64_t sm)
146168de460fSthorpej {
146268de460fSthorpej u_int64_t m;
146368de460fSthorpej
146468de460fSthorpej m = (sm * 8 * machclk_freq) >> SM_SHIFT;
146568de460fSthorpej return ((u_int)m);
146668de460fSthorpej }
146768de460fSthorpej
146868de460fSthorpej static u_int
dx2d(u_int64_t dx)1469dd191f37Speter dx2d(u_int64_t dx)
147068de460fSthorpej {
147168de460fSthorpej u_int64_t d;
147268de460fSthorpej
147368de460fSthorpej d = dx * 1000 / machclk_freq;
147468de460fSthorpej return ((u_int)d);
147568de460fSthorpej }
147668de460fSthorpej
147768de460fSthorpej static void
sc2isc(struct service_curve * sc,struct internal_sc * isc)1478dd191f37Speter sc2isc(struct service_curve *sc, struct internal_sc *isc)
147968de460fSthorpej {
148068de460fSthorpej isc->sm1 = m2sm(sc->m1);
148168de460fSthorpej isc->ism1 = m2ism(sc->m1);
148268de460fSthorpej isc->dx = d2dx(sc->d);
148368de460fSthorpej isc->dy = seg_x2y(isc->dx, isc->sm1);
148468de460fSthorpej isc->sm2 = m2sm(sc->m2);
148568de460fSthorpej isc->ism2 = m2ism(sc->m2);
148668de460fSthorpej }
148768de460fSthorpej
148868de460fSthorpej /*
148968de460fSthorpej * initialize the runtime service curve with the given internal
149068de460fSthorpej * service curve starting at (x, y).
149168de460fSthorpej */
149268de460fSthorpej static void
rtsc_init(struct runtime_sc * rtsc,struct internal_sc * isc,u_int64_t x,u_int64_t y)1493dd191f37Speter rtsc_init(struct runtime_sc *rtsc, struct internal_sc * isc, u_int64_t x,
1494dd191f37Speter u_int64_t y)
149568de460fSthorpej {
149668de460fSthorpej rtsc->x = x;
149768de460fSthorpej rtsc->y = y;
149868de460fSthorpej rtsc->sm1 = isc->sm1;
149968de460fSthorpej rtsc->ism1 = isc->ism1;
150068de460fSthorpej rtsc->dx = isc->dx;
150168de460fSthorpej rtsc->dy = isc->dy;
150268de460fSthorpej rtsc->sm2 = isc->sm2;
150368de460fSthorpej rtsc->ism2 = isc->ism2;
150468de460fSthorpej }
150568de460fSthorpej
150668de460fSthorpej /*
150768de460fSthorpej * calculate the y-projection of the runtime service curve by the
150868de460fSthorpej * given x-projection value
150968de460fSthorpej */
151068de460fSthorpej static u_int64_t
rtsc_y2x(struct runtime_sc * rtsc,u_int64_t y)1511dd191f37Speter rtsc_y2x(struct runtime_sc *rtsc, u_int64_t y)
151268de460fSthorpej {
151368de460fSthorpej u_int64_t x;
151468de460fSthorpej
151568de460fSthorpej if (y < rtsc->y)
151668de460fSthorpej x = rtsc->x;
151768de460fSthorpej else if (y <= rtsc->y + rtsc->dy) {
151868de460fSthorpej /* x belongs to the 1st segment */
151968de460fSthorpej if (rtsc->dy == 0)
152068de460fSthorpej x = rtsc->x + rtsc->dx;
152168de460fSthorpej else
152268de460fSthorpej x = rtsc->x + seg_y2x(y - rtsc->y, rtsc->ism1);
152368de460fSthorpej } else {
152468de460fSthorpej /* x belongs to the 2nd segment */
152568de460fSthorpej x = rtsc->x + rtsc->dx
152668de460fSthorpej + seg_y2x(y - rtsc->y - rtsc->dy, rtsc->ism2);
152768de460fSthorpej }
152868de460fSthorpej return (x);
152968de460fSthorpej }
153068de460fSthorpej
153168de460fSthorpej static u_int64_t
rtsc_x2y(struct runtime_sc * rtsc,u_int64_t x)1532dd191f37Speter rtsc_x2y(struct runtime_sc *rtsc, u_int64_t x)
153368de460fSthorpej {
153468de460fSthorpej u_int64_t y;
153568de460fSthorpej
153668de460fSthorpej if (x <= rtsc->x)
153768de460fSthorpej y = rtsc->y;
153868de460fSthorpej else if (x <= rtsc->x + rtsc->dx)
153968de460fSthorpej /* y belongs to the 1st segment */
154068de460fSthorpej y = rtsc->y + seg_x2y(x - rtsc->x, rtsc->sm1);
154168de460fSthorpej else
154268de460fSthorpej /* y belongs to the 2nd segment */
154368de460fSthorpej y = rtsc->y + rtsc->dy
154468de460fSthorpej + seg_x2y(x - rtsc->x - rtsc->dx, rtsc->sm2);
154568de460fSthorpej return (y);
154668de460fSthorpej }
154768de460fSthorpej
154868de460fSthorpej /*
154968de460fSthorpej * update the runtime service curve by taking the minimum of the current
155068de460fSthorpej * runtime service curve and the service curve starting at (x, y).
155168de460fSthorpej */
155268de460fSthorpej static void
rtsc_min(struct runtime_sc * rtsc,struct internal_sc * isc,u_int64_t x,u_int64_t y)1553dd191f37Speter rtsc_min(struct runtime_sc *rtsc, struct internal_sc *isc, u_int64_t x,
1554dd191f37Speter u_int64_t y)
155568de460fSthorpej {
155668de460fSthorpej u_int64_t y1, y2, dx, dy;
155768de460fSthorpej
155868de460fSthorpej if (isc->sm1 <= isc->sm2) {
155968de460fSthorpej /* service curve is convex */
156068de460fSthorpej y1 = rtsc_x2y(rtsc, x);
156168de460fSthorpej if (y1 < y)
156268de460fSthorpej /* the current rtsc is smaller */
156368de460fSthorpej return;
156468de460fSthorpej rtsc->x = x;
156568de460fSthorpej rtsc->y = y;
156668de460fSthorpej return;
156768de460fSthorpej }
156868de460fSthorpej
156968de460fSthorpej /*
157068de460fSthorpej * service curve is concave
157168de460fSthorpej * compute the two y values of the current rtsc
157268de460fSthorpej * y1: at x
157368de460fSthorpej * y2: at (x + dx)
157468de460fSthorpej */
157568de460fSthorpej y1 = rtsc_x2y(rtsc, x);
157668de460fSthorpej if (y1 <= y) {
157768de460fSthorpej /* rtsc is below isc, no change to rtsc */
157868de460fSthorpej return;
157968de460fSthorpej }
158068de460fSthorpej
158168de460fSthorpej y2 = rtsc_x2y(rtsc, x + isc->dx);
158268de460fSthorpej if (y2 >= y + isc->dy) {
158368de460fSthorpej /* rtsc is above isc, replace rtsc by isc */
158468de460fSthorpej rtsc->x = x;
158568de460fSthorpej rtsc->y = y;
158668de460fSthorpej rtsc->dx = isc->dx;
158768de460fSthorpej rtsc->dy = isc->dy;
158868de460fSthorpej return;
158968de460fSthorpej }
159068de460fSthorpej
159168de460fSthorpej /*
159268de460fSthorpej * the two curves intersect
159368de460fSthorpej * compute the offsets (dx, dy) using the reverse
159468de460fSthorpej * function of seg_x2y()
159568de460fSthorpej * seg_x2y(dx, sm1) == seg_x2y(dx, sm2) + (y1 - y)
159668de460fSthorpej */
159768de460fSthorpej dx = ((y1 - y) << SM_SHIFT) / (isc->sm1 - isc->sm2);
159868de460fSthorpej /*
159968de460fSthorpej * check if (x, y1) belongs to the 1st segment of rtsc.
160068de460fSthorpej * if so, add the offset.
160168de460fSthorpej */
160268de460fSthorpej if (rtsc->x + rtsc->dx > x)
160368de460fSthorpej dx += rtsc->x + rtsc->dx - x;
160468de460fSthorpej dy = seg_x2y(dx, isc->sm1);
160568de460fSthorpej
160668de460fSthorpej rtsc->x = x;
160768de460fSthorpej rtsc->y = y;
160868de460fSthorpej rtsc->dx = dx;
160968de460fSthorpej rtsc->dy = dy;
161068de460fSthorpej return;
161168de460fSthorpej }
161268de460fSthorpej
1613dd191f37Speter static void
get_class_stats(struct hfsc_classstats * sp,struct hfsc_class * cl)1614dd191f37Speter get_class_stats(struct hfsc_classstats *sp, struct hfsc_class *cl)
1615dd191f37Speter {
1616dd191f37Speter sp->class_id = cl->cl_id;
1617dd191f37Speter sp->class_handle = cl->cl_handle;
1618dd191f37Speter
1619dd191f37Speter if (cl->cl_rsc != NULL) {
1620dd191f37Speter sp->rsc.m1 = sm2m(cl->cl_rsc->sm1);
1621dd191f37Speter sp->rsc.d = dx2d(cl->cl_rsc->dx);
1622dd191f37Speter sp->rsc.m2 = sm2m(cl->cl_rsc->sm2);
1623dd191f37Speter } else {
1624dd191f37Speter sp->rsc.m1 = 0;
1625dd191f37Speter sp->rsc.d = 0;
1626dd191f37Speter sp->rsc.m2 = 0;
1627dd191f37Speter }
1628dd191f37Speter if (cl->cl_fsc != NULL) {
1629dd191f37Speter sp->fsc.m1 = sm2m(cl->cl_fsc->sm1);
1630dd191f37Speter sp->fsc.d = dx2d(cl->cl_fsc->dx);
1631dd191f37Speter sp->fsc.m2 = sm2m(cl->cl_fsc->sm2);
1632dd191f37Speter } else {
1633dd191f37Speter sp->fsc.m1 = 0;
1634dd191f37Speter sp->fsc.d = 0;
1635dd191f37Speter sp->fsc.m2 = 0;
1636dd191f37Speter }
1637dd191f37Speter if (cl->cl_usc != NULL) {
1638dd191f37Speter sp->usc.m1 = sm2m(cl->cl_usc->sm1);
1639dd191f37Speter sp->usc.d = dx2d(cl->cl_usc->dx);
1640dd191f37Speter sp->usc.m2 = sm2m(cl->cl_usc->sm2);
1641dd191f37Speter } else {
1642dd191f37Speter sp->usc.m1 = 0;
1643dd191f37Speter sp->usc.d = 0;
1644dd191f37Speter sp->usc.m2 = 0;
1645dd191f37Speter }
1646dd191f37Speter
1647dd191f37Speter sp->total = cl->cl_total;
1648dd191f37Speter sp->cumul = cl->cl_cumul;
1649dd191f37Speter
1650dd191f37Speter sp->d = cl->cl_d;
1651dd191f37Speter sp->e = cl->cl_e;
1652dd191f37Speter sp->vt = cl->cl_vt;
1653dd191f37Speter sp->f = cl->cl_f;
1654dd191f37Speter
1655dd191f37Speter sp->initvt = cl->cl_initvt;
1656dd191f37Speter sp->vtperiod = cl->cl_vtperiod;
1657dd191f37Speter sp->parentperiod = cl->cl_parentperiod;
1658dd191f37Speter sp->nactive = cl->cl_nactive;
1659dd191f37Speter sp->vtoff = cl->cl_vtoff;
1660dd191f37Speter sp->cvtmax = cl->cl_cvtmax;
1661dd191f37Speter sp->myf = cl->cl_myf;
1662dd191f37Speter sp->cfmin = cl->cl_cfmin;
1663dd191f37Speter sp->cvtmin = cl->cl_cvtmin;
1664dd191f37Speter sp->myfadj = cl->cl_myfadj;
1665dd191f37Speter sp->vtadj = cl->cl_vtadj;
1666dd191f37Speter
1667dd191f37Speter sp->cur_time = read_machclk();
1668dd191f37Speter sp->machclk_freq = machclk_freq;
1669dd191f37Speter
1670dd191f37Speter sp->qlength = qlen(cl->cl_q);
1671dd191f37Speter sp->qlimit = qlimit(cl->cl_q);
1672dd191f37Speter sp->xmit_cnt = cl->cl_stats.xmit_cnt;
1673dd191f37Speter sp->drop_cnt = cl->cl_stats.drop_cnt;
1674dd191f37Speter sp->period = cl->cl_stats.period;
1675dd191f37Speter
1676dd191f37Speter sp->qtype = qtype(cl->cl_q);
1677dd191f37Speter #ifdef ALTQ_RED
1678dd191f37Speter if (q_is_red(cl->cl_q))
1679dd191f37Speter red_getstats(cl->cl_red, &sp->red[0]);
1680dd191f37Speter #endif
1681dd191f37Speter #ifdef ALTQ_RIO
1682dd191f37Speter if (q_is_rio(cl->cl_q))
1683dd191f37Speter rio_getstats((rio_t *)cl->cl_red, &sp->red[0]);
1684dd191f37Speter #endif
1685dd191f37Speter }
1686dd191f37Speter
1687dd191f37Speter /* convert a class handle to the corresponding class pointer */
1688dd191f37Speter static struct hfsc_class *
clh_to_clp(struct hfsc_if * hif,u_int32_t chandle)1689dd191f37Speter clh_to_clp(struct hfsc_if *hif, u_int32_t chandle)
1690dd191f37Speter {
1691dd191f37Speter int i;
1692dd191f37Speter struct hfsc_class *cl;
1693dd191f37Speter
1694dd191f37Speter if (chandle == 0)
1695dd191f37Speter return (NULL);
1696dd191f37Speter /*
1697dd191f37Speter * first, try optimistically the slot matching the lower bits of
1698dd191f37Speter * the handle. if it fails, do the linear table search.
1699dd191f37Speter */
1700dd191f37Speter i = chandle % HFSC_MAX_CLASSES;
1701dd191f37Speter if ((cl = hif->hif_class_tbl[i]) != NULL && cl->cl_handle == chandle)
1702dd191f37Speter return (cl);
1703dd191f37Speter for (i = 0; i < HFSC_MAX_CLASSES; i++)
1704dd191f37Speter if ((cl = hif->hif_class_tbl[i]) != NULL &&
1705dd191f37Speter cl->cl_handle == chandle)
1706dd191f37Speter return (cl);
1707dd191f37Speter return (NULL);
1708dd191f37Speter }
1709dd191f37Speter
1710dd191f37Speter #ifdef ALTQ3_COMPAT
1711dd191f37Speter static struct hfsc_if *
hfsc_attach(struct ifaltq * ifq,u_int bandwidth)1712168cd830Schristos hfsc_attach(struct ifaltq *ifq, u_int bandwidth)
1713dd191f37Speter {
1714dd191f37Speter struct hfsc_if *hif;
1715dd191f37Speter
1716dd191f37Speter hif = malloc(sizeof(struct hfsc_if), M_DEVBUF, M_WAITOK|M_ZERO);
1717dd191f37Speter if (hif == NULL)
1718dd191f37Speter return (NULL);
1719dd191f37Speter
1720dd191f37Speter hif->hif_eligible = ellist_alloc();
1721dd191f37Speter if (hif->hif_eligible == NULL) {
1722dd191f37Speter free(hif, M_DEVBUF);
1723dd191f37Speter return NULL;
1724dd191f37Speter }
1725dd191f37Speter
1726dd191f37Speter hif->hif_ifq = ifq;
1727dd191f37Speter
1728dd191f37Speter /* add this state to the hfsc list */
1729dd191f37Speter hif->hif_next = hif_list;
1730dd191f37Speter hif_list = hif;
1731dd191f37Speter
1732dd191f37Speter return (hif);
1733dd191f37Speter }
1734dd191f37Speter
1735ec004aeaSchristos static void
hfsc_detach(struct hfsc_if * hif)1736dd191f37Speter hfsc_detach(struct hfsc_if *hif)
1737dd191f37Speter {
1738dd191f37Speter (void)hfsc_clear_interface(hif);
1739dd191f37Speter (void)hfsc_class_destroy(hif->hif_rootclass);
1740dd191f37Speter
1741dd191f37Speter /* remove this interface from the hif list */
1742dd191f37Speter if (hif_list == hif)
1743dd191f37Speter hif_list = hif->hif_next;
1744dd191f37Speter else {
1745dd191f37Speter struct hfsc_if *h;
1746dd191f37Speter
1747dd191f37Speter for (h = hif_list; h != NULL; h = h->hif_next)
1748dd191f37Speter if (h->hif_next == hif) {
1749dd191f37Speter h->hif_next = hif->hif_next;
1750dd191f37Speter break;
1751dd191f37Speter }
1752dd191f37Speter ASSERT(h != NULL);
1753dd191f37Speter }
1754dd191f37Speter
1755dd191f37Speter ellist_destroy(hif->hif_eligible);
1756dd191f37Speter
1757dd191f37Speter free(hif, M_DEVBUF);
1758dd191f37Speter }
1759dd191f37Speter
1760dd191f37Speter static int
hfsc_class_modify(struct hfsc_class * cl,struct service_curve * rsc,struct service_curve * fsc,struct service_curve * usc)1761dd191f37Speter hfsc_class_modify(struct hfsc_class *cl, struct service_curve *rsc,
1762dd191f37Speter struct service_curve *fsc, struct service_curve *usc)
1763dd191f37Speter {
1764dd191f37Speter struct internal_sc *rsc_tmp, *fsc_tmp, *usc_tmp;
1765dd191f37Speter u_int64_t cur_time;
1766dd191f37Speter int s;
1767dd191f37Speter
1768dd191f37Speter rsc_tmp = fsc_tmp = usc_tmp = NULL;
1769dd191f37Speter if (rsc != NULL && (rsc->m1 != 0 || rsc->m2 != 0) &&
1770dd191f37Speter cl->cl_rsc == NULL) {
1771dd191f37Speter rsc_tmp = malloc(sizeof(struct internal_sc), M_DEVBUF,
1772dd191f37Speter M_WAITOK);
1773dd191f37Speter if (rsc_tmp == NULL)
1774dd191f37Speter return (ENOMEM);
1775dd191f37Speter }
1776dd191f37Speter if (fsc != NULL && (fsc->m1 != 0 || fsc->m2 != 0) &&
1777dd191f37Speter cl->cl_fsc == NULL) {
1778dd191f37Speter fsc_tmp = malloc(sizeof(struct internal_sc), M_DEVBUF,
1779dd191f37Speter M_WAITOK);
1780dd191f37Speter if (fsc_tmp == NULL)
1781dd191f37Speter return (ENOMEM);
1782dd191f37Speter }
1783dd191f37Speter if (usc != NULL && (usc->m1 != 0 || usc->m2 != 0) &&
1784dd191f37Speter cl->cl_usc == NULL) {
1785dd191f37Speter usc_tmp = malloc(sizeof(struct internal_sc), M_DEVBUF,
1786dd191f37Speter M_WAITOK);
1787dd191f37Speter if (usc_tmp == NULL)
1788dd191f37Speter return (ENOMEM);
1789dd191f37Speter }
1790dd191f37Speter
1791dd191f37Speter cur_time = read_machclk();
1792dd191f37Speter s = splnet();
1793dd191f37Speter
1794dd191f37Speter if (rsc != NULL) {
1795dd191f37Speter if (rsc->m1 == 0 && rsc->m2 == 0) {
1796dd191f37Speter if (cl->cl_rsc != NULL) {
1797dd191f37Speter if (!qempty(cl->cl_q))
1798dd191f37Speter hfsc_purgeq(cl);
1799dd191f37Speter free(cl->cl_rsc, M_DEVBUF);
1800dd191f37Speter cl->cl_rsc = NULL;
1801dd191f37Speter }
1802dd191f37Speter } else {
1803dd191f37Speter if (cl->cl_rsc == NULL)
1804dd191f37Speter cl->cl_rsc = rsc_tmp;
1805dd191f37Speter sc2isc(rsc, cl->cl_rsc);
1806dd191f37Speter rtsc_init(&cl->cl_deadline, cl->cl_rsc, cur_time,
1807dd191f37Speter cl->cl_cumul);
1808dd191f37Speter cl->cl_eligible = cl->cl_deadline;
1809dd191f37Speter if (cl->cl_rsc->sm1 <= cl->cl_rsc->sm2) {
1810dd191f37Speter cl->cl_eligible.dx = 0;
1811dd191f37Speter cl->cl_eligible.dy = 0;
1812dd191f37Speter }
1813dd191f37Speter }
1814dd191f37Speter }
1815dd191f37Speter
1816dd191f37Speter if (fsc != NULL) {
1817dd191f37Speter if (fsc->m1 == 0 && fsc->m2 == 0) {
1818dd191f37Speter if (cl->cl_fsc != NULL) {
1819dd191f37Speter if (!qempty(cl->cl_q))
1820dd191f37Speter hfsc_purgeq(cl);
1821dd191f37Speter free(cl->cl_fsc, M_DEVBUF);
1822dd191f37Speter cl->cl_fsc = NULL;
1823dd191f37Speter }
1824dd191f37Speter } else {
1825dd191f37Speter if (cl->cl_fsc == NULL)
1826dd191f37Speter cl->cl_fsc = fsc_tmp;
1827dd191f37Speter sc2isc(fsc, cl->cl_fsc);
1828dd191f37Speter rtsc_init(&cl->cl_virtual, cl->cl_fsc, cl->cl_vt,
1829dd191f37Speter cl->cl_total);
1830dd191f37Speter }
1831dd191f37Speter }
1832dd191f37Speter
1833dd191f37Speter if (usc != NULL) {
1834dd191f37Speter if (usc->m1 == 0 && usc->m2 == 0) {
1835dd191f37Speter if (cl->cl_usc != NULL) {
1836dd191f37Speter free(cl->cl_usc, M_DEVBUF);
1837dd191f37Speter cl->cl_usc = NULL;
1838dd191f37Speter cl->cl_myf = 0;
1839dd191f37Speter }
1840dd191f37Speter } else {
1841dd191f37Speter if (cl->cl_usc == NULL)
1842dd191f37Speter cl->cl_usc = usc_tmp;
1843dd191f37Speter sc2isc(usc, cl->cl_usc);
1844dd191f37Speter rtsc_init(&cl->cl_ulimit, cl->cl_usc, cur_time,
1845dd191f37Speter cl->cl_total);
1846dd191f37Speter }
1847dd191f37Speter }
1848dd191f37Speter
1849dd191f37Speter if (!qempty(cl->cl_q)) {
1850dd191f37Speter if (cl->cl_rsc != NULL)
1851dd191f37Speter update_ed(cl, m_pktlen(qhead(cl->cl_q)));
1852dd191f37Speter if (cl->cl_fsc != NULL)
1853dd191f37Speter update_vf(cl, 0, cur_time);
1854dd191f37Speter /* is this enough? */
1855dd191f37Speter }
1856dd191f37Speter
1857dd191f37Speter splx(s);
1858dd191f37Speter
1859dd191f37Speter return (0);
1860dd191f37Speter }
1861dd191f37Speter
186268de460fSthorpej /*
186368de460fSthorpej * hfsc device interface
186468de460fSthorpej */
186568de460fSthorpej int
hfscopen(dev_t dev,int flag,int fmt,struct lwp * l)1866168cd830Schristos hfscopen(dev_t dev, int flag, int fmt,
1867168cd830Schristos struct lwp *l)
186868de460fSthorpej {
186968de460fSthorpej if (machclk_freq == 0)
187068de460fSthorpej init_machclk();
187168de460fSthorpej
187268de460fSthorpej if (machclk_freq == 0) {
1873d20841bbSwiz printf("hfsc: no CPU clock available!\n");
187468de460fSthorpej return (ENXIO);
187568de460fSthorpej }
187668de460fSthorpej
187768de460fSthorpej /* everything will be done when the queueing scheme is attached. */
187868de460fSthorpej return 0;
187968de460fSthorpej }
188068de460fSthorpej
188168de460fSthorpej int
hfscclose(dev_t dev,int flag,int fmt,struct lwp * l)1882168cd830Schristos hfscclose(dev_t dev, int flag, int fmt,
1883168cd830Schristos struct lwp *l)
188468de460fSthorpej {
188568de460fSthorpej struct hfsc_if *hif;
188668de460fSthorpej
188768de460fSthorpej while ((hif = hif_list) != NULL) {
188868de460fSthorpej /* destroy all */
188968de460fSthorpej if (ALTQ_IS_ENABLED(hif->hif_ifq))
189068de460fSthorpej altq_disable(hif->hif_ifq);
189168de460fSthorpej
1892ec004aeaSchristos int error = altq_detach(hif->hif_ifq);
1893ec004aeaSchristos switch (error) {
1894ec004aeaSchristos case 0:
1895ec004aeaSchristos case ENXIO: /* already disabled */
1896ec004aeaSchristos break;
1897ec004aeaSchristos default:
1898ec004aeaSchristos return error;
1899ec004aeaSchristos }
1900ec004aeaSchristos hfsc_detach(hif);
190168de460fSthorpej }
190268de460fSthorpej
1903ec004aeaSchristos return 0;
190468de460fSthorpej }
190568de460fSthorpej
190668de460fSthorpej int
hfscioctl(dev_t dev,ioctlcmd_t cmd,void * addr,int flag,struct lwp * l)190753524e44Schristos hfscioctl(dev_t dev, ioctlcmd_t cmd, void *addr, int flag,
19084d595fd7Schristos struct lwp *l)
190968de460fSthorpej {
191068de460fSthorpej struct hfsc_if *hif;
191168de460fSthorpej struct hfsc_interface *ifacep;
191268de460fSthorpej int error = 0;
191368de460fSthorpej
191468de460fSthorpej /* check super-user privilege */
191568de460fSthorpej switch (cmd) {
191668de460fSthorpej case HFSC_GETSTATS:
191768de460fSthorpej break;
191868de460fSthorpej default:
1919b8093b89Selad if ((error = kauth_authorize_network(l->l_cred,
1920b8093b89Selad KAUTH_NETWORK_ALTQ, KAUTH_REQ_NETWORK_ALTQ_HFSC, NULL,
1921b8093b89Selad NULL, NULL)) != 0)
192268de460fSthorpej return (error);
192368de460fSthorpej break;
192468de460fSthorpej }
192568de460fSthorpej
192668de460fSthorpej switch (cmd) {
192768de460fSthorpej
192868de460fSthorpej case HFSC_IF_ATTACH:
192968de460fSthorpej error = hfsccmd_if_attach((struct hfsc_attach *)addr);
193068de460fSthorpej break;
193168de460fSthorpej
193268de460fSthorpej case HFSC_IF_DETACH:
193368de460fSthorpej error = hfsccmd_if_detach((struct hfsc_interface *)addr);
193468de460fSthorpej break;
193568de460fSthorpej
193668de460fSthorpej case HFSC_ENABLE:
193768de460fSthorpej case HFSC_DISABLE:
193868de460fSthorpej case HFSC_CLEAR_HIERARCHY:
193968de460fSthorpej ifacep = (struct hfsc_interface *)addr;
194068de460fSthorpej if ((hif = altq_lookup(ifacep->hfsc_ifname,
194168de460fSthorpej ALTQT_HFSC)) == NULL) {
194268de460fSthorpej error = EBADF;
194368de460fSthorpej break;
194468de460fSthorpej }
194568de460fSthorpej
194668de460fSthorpej switch (cmd) {
194768de460fSthorpej
194868de460fSthorpej case HFSC_ENABLE:
194968de460fSthorpej if (hif->hif_defaultclass == NULL) {
1950dd191f37Speter #ifdef ALTQ_DEBUG
195168de460fSthorpej printf("hfsc: no default class\n");
195268de460fSthorpej #endif
195368de460fSthorpej error = EINVAL;
195468de460fSthorpej break;
195568de460fSthorpej }
195668de460fSthorpej error = altq_enable(hif->hif_ifq);
195768de460fSthorpej break;
195868de460fSthorpej
195968de460fSthorpej case HFSC_DISABLE:
196068de460fSthorpej error = altq_disable(hif->hif_ifq);
196168de460fSthorpej break;
196268de460fSthorpej
196368de460fSthorpej case HFSC_CLEAR_HIERARCHY:
196468de460fSthorpej hfsc_clear_interface(hif);
196568de460fSthorpej break;
196668de460fSthorpej }
196768de460fSthorpej break;
196868de460fSthorpej
196968de460fSthorpej case HFSC_ADD_CLASS:
197068de460fSthorpej error = hfsccmd_add_class((struct hfsc_add_class *)addr);
197168de460fSthorpej break;
197268de460fSthorpej
197368de460fSthorpej case HFSC_DEL_CLASS:
197468de460fSthorpej error = hfsccmd_delete_class((struct hfsc_delete_class *)addr);
197568de460fSthorpej break;
197668de460fSthorpej
197768de460fSthorpej case HFSC_MOD_CLASS:
197868de460fSthorpej error = hfsccmd_modify_class((struct hfsc_modify_class *)addr);
197968de460fSthorpej break;
198068de460fSthorpej
198168de460fSthorpej case HFSC_ADD_FILTER:
198268de460fSthorpej error = hfsccmd_add_filter((struct hfsc_add_filter *)addr);
198368de460fSthorpej break;
198468de460fSthorpej
198568de460fSthorpej case HFSC_DEL_FILTER:
198668de460fSthorpej error = hfsccmd_delete_filter((struct hfsc_delete_filter *)addr);
198768de460fSthorpej break;
198868de460fSthorpej
198968de460fSthorpej case HFSC_GETSTATS:
199068de460fSthorpej error = hfsccmd_class_stats((struct hfsc_class_stats *)addr);
199168de460fSthorpej break;
199268de460fSthorpej
199368de460fSthorpej default:
199468de460fSthorpej error = EINVAL;
199568de460fSthorpej break;
199668de460fSthorpej }
199768de460fSthorpej return error;
199868de460fSthorpej }
199968de460fSthorpej
200068de460fSthorpej static int
hfsccmd_if_attach(struct hfsc_attach * ap)2001dd191f37Speter hfsccmd_if_attach(struct hfsc_attach *ap)
200268de460fSthorpej {
200368de460fSthorpej struct hfsc_if *hif;
200468de460fSthorpej struct ifnet *ifp;
200568de460fSthorpej int error;
200668de460fSthorpej
200768de460fSthorpej if ((ifp = ifunit(ap->iface.hfsc_ifname)) == NULL)
200868de460fSthorpej return (ENXIO);
200968de460fSthorpej
201068de460fSthorpej if ((hif = hfsc_attach(&ifp->if_snd, ap->bandwidth)) == NULL)
201168de460fSthorpej return (ENOMEM);
201268de460fSthorpej
201368de460fSthorpej /*
201468de460fSthorpej * set HFSC to this ifnet structure.
201568de460fSthorpej */
201668de460fSthorpej if ((error = altq_attach(&ifp->if_snd, ALTQT_HFSC, hif,
201768de460fSthorpej hfsc_enqueue, hfsc_dequeue, hfsc_request,
201868de460fSthorpej &hif->hif_classifier, acc_classify)) != 0)
2019ec004aeaSchristos hfsc_detach(hif);
202068de460fSthorpej
202168de460fSthorpej return (error);
202268de460fSthorpej }
202368de460fSthorpej
202468de460fSthorpej static int
hfsccmd_if_detach(struct hfsc_interface * ap)2025dd191f37Speter hfsccmd_if_detach(struct hfsc_interface *ap)
202668de460fSthorpej {
202768de460fSthorpej struct hfsc_if *hif;
202868de460fSthorpej int error;
202968de460fSthorpej
203068de460fSthorpej if ((hif = altq_lookup(ap->hfsc_ifname, ALTQT_HFSC)) == NULL)
203168de460fSthorpej return (EBADF);
203268de460fSthorpej
203368de460fSthorpej if (ALTQ_IS_ENABLED(hif->hif_ifq))
203468de460fSthorpej altq_disable(hif->hif_ifq);
203568de460fSthorpej
203668de460fSthorpej if ((error = altq_detach(hif->hif_ifq)))
203768de460fSthorpej return (error);
203868de460fSthorpej
2039ec004aeaSchristos hfsc_detach(hif);
2040ec004aeaSchristos return 0;
204168de460fSthorpej }
204268de460fSthorpej
204368de460fSthorpej static int
hfsccmd_add_class(struct hfsc_add_class * ap)2044dd191f37Speter hfsccmd_add_class(struct hfsc_add_class *ap)
204568de460fSthorpej {
204668de460fSthorpej struct hfsc_if *hif;
204768de460fSthorpej struct hfsc_class *cl, *parent;
2048dd191f37Speter int i;
204968de460fSthorpej
205068de460fSthorpej if ((hif = altq_lookup(ap->iface.hfsc_ifname, ALTQT_HFSC)) == NULL)
205168de460fSthorpej return (EBADF);
205268de460fSthorpej
2053dd191f37Speter if (ap->parent_handle == HFSC_NULLCLASS_HANDLE &&
2054dd191f37Speter hif->hif_rootclass == NULL)
2055dd191f37Speter parent = NULL;
2056dd191f37Speter else if ((parent = clh_to_clp(hif, ap->parent_handle)) == NULL)
205768de460fSthorpej return (EINVAL);
205868de460fSthorpej
2059dd191f37Speter /* assign a class handle (use a free slot number for now) */
2060dd191f37Speter for (i = 1; i < HFSC_MAX_CLASSES; i++)
2061dd191f37Speter if (hif->hif_class_tbl[i] == NULL)
2062dd191f37Speter break;
2063dd191f37Speter if (i == HFSC_MAX_CLASSES)
2064dd191f37Speter return (EBUSY);
2065dd191f37Speter
2066dd191f37Speter if ((cl = hfsc_class_create(hif, &ap->service_curve, NULL, NULL,
2067dd191f37Speter parent, ap->qlimit, ap->flags, i)) == NULL)
206868de460fSthorpej return (ENOMEM);
206968de460fSthorpej
207068de460fSthorpej /* return a class handle to the user */
2071dd191f37Speter ap->class_handle = i;
2072dd191f37Speter
207368de460fSthorpej return (0);
207468de460fSthorpej }
207568de460fSthorpej
207668de460fSthorpej static int
hfsccmd_delete_class(struct hfsc_delete_class * ap)2077dd191f37Speter hfsccmd_delete_class(struct hfsc_delete_class *ap)
207868de460fSthorpej {
207968de460fSthorpej struct hfsc_if *hif;
208068de460fSthorpej struct hfsc_class *cl;
208168de460fSthorpej
208268de460fSthorpej if ((hif = altq_lookup(ap->iface.hfsc_ifname, ALTQT_HFSC)) == NULL)
208368de460fSthorpej return (EBADF);
208468de460fSthorpej
208568de460fSthorpej if ((cl = clh_to_clp(hif, ap->class_handle)) == NULL)
208668de460fSthorpej return (EINVAL);
208768de460fSthorpej
208868de460fSthorpej return hfsc_class_destroy(cl);
208968de460fSthorpej }
209068de460fSthorpej
209168de460fSthorpej static int
hfsccmd_modify_class(struct hfsc_modify_class * ap)2092dd191f37Speter hfsccmd_modify_class(struct hfsc_modify_class *ap)
209368de460fSthorpej {
209468de460fSthorpej struct hfsc_if *hif;
209568de460fSthorpej struct hfsc_class *cl;
209668de460fSthorpej struct service_curve *rsc = NULL;
209768de460fSthorpej struct service_curve *fsc = NULL;
2098dd191f37Speter struct service_curve *usc = NULL;
209968de460fSthorpej
210068de460fSthorpej if ((hif = altq_lookup(ap->iface.hfsc_ifname, ALTQT_HFSC)) == NULL)
210168de460fSthorpej return (EBADF);
210268de460fSthorpej
210368de460fSthorpej if ((cl = clh_to_clp(hif, ap->class_handle)) == NULL)
210468de460fSthorpej return (EINVAL);
210568de460fSthorpej
210668de460fSthorpej if (ap->sctype & HFSC_REALTIMESC)
210768de460fSthorpej rsc = &ap->service_curve;
210868de460fSthorpej if (ap->sctype & HFSC_LINKSHARINGSC)
210968de460fSthorpej fsc = &ap->service_curve;
2110dd191f37Speter if (ap->sctype & HFSC_UPPERLIMITSC)
2111dd191f37Speter usc = &ap->service_curve;
211268de460fSthorpej
2113dd191f37Speter return hfsc_class_modify(cl, rsc, fsc, usc);
211468de460fSthorpej }
211568de460fSthorpej
211668de460fSthorpej static int
hfsccmd_add_filter(struct hfsc_add_filter * ap)2117dd191f37Speter hfsccmd_add_filter(struct hfsc_add_filter *ap)
211868de460fSthorpej {
211968de460fSthorpej struct hfsc_if *hif;
212068de460fSthorpej struct hfsc_class *cl;
212168de460fSthorpej
212268de460fSthorpej if ((hif = altq_lookup(ap->iface.hfsc_ifname, ALTQT_HFSC)) == NULL)
212368de460fSthorpej return (EBADF);
212468de460fSthorpej
212568de460fSthorpej if ((cl = clh_to_clp(hif, ap->class_handle)) == NULL)
212668de460fSthorpej return (EINVAL);
212768de460fSthorpej
212868de460fSthorpej if (is_a_parent_class(cl)) {
2129dd191f37Speter #ifdef ALTQ_DEBUG
213068de460fSthorpej printf("hfsccmd_add_filter: not a leaf class!\n");
213168de460fSthorpej #endif
213268de460fSthorpej return (EINVAL);
213368de460fSthorpej }
213468de460fSthorpej
213568de460fSthorpej return acc_add_filter(&hif->hif_classifier, &ap->filter,
213668de460fSthorpej cl, &ap->filter_handle);
213768de460fSthorpej }
213868de460fSthorpej
213968de460fSthorpej static int
hfsccmd_delete_filter(struct hfsc_delete_filter * ap)2140dd191f37Speter hfsccmd_delete_filter(struct hfsc_delete_filter *ap)
214168de460fSthorpej {
214268de460fSthorpej struct hfsc_if *hif;
214368de460fSthorpej
214468de460fSthorpej if ((hif = altq_lookup(ap->iface.hfsc_ifname, ALTQT_HFSC)) == NULL)
214568de460fSthorpej return (EBADF);
214668de460fSthorpej
214768de460fSthorpej return acc_delete_filter(&hif->hif_classifier,
214868de460fSthorpej ap->filter_handle);
214968de460fSthorpej }
215068de460fSthorpej
215168de460fSthorpej static int
hfsccmd_class_stats(struct hfsc_class_stats * ap)2152dd191f37Speter hfsccmd_class_stats(struct hfsc_class_stats *ap)
215368de460fSthorpej {
215468de460fSthorpej struct hfsc_if *hif;
215568de460fSthorpej struct hfsc_class *cl;
2156dd191f37Speter struct hfsc_classstats stats, *usp;
215768de460fSthorpej int n, nclasses, error;
215868de460fSthorpej
215968de460fSthorpej if ((hif = altq_lookup(ap->iface.hfsc_ifname, ALTQT_HFSC)) == NULL)
216068de460fSthorpej return (EBADF);
216168de460fSthorpej
216268de460fSthorpej ap->cur_time = read_machclk();
2163dd191f37Speter ap->machclk_freq = machclk_freq;
216468de460fSthorpej ap->hif_classes = hif->hif_classes;
216568de460fSthorpej ap->hif_packets = hif->hif_packets;
216668de460fSthorpej
216768de460fSthorpej /* skip the first N classes in the tree */
216868de460fSthorpej nclasses = ap->nskip;
216968de460fSthorpej for (cl = hif->hif_rootclass, n = 0; cl != NULL && n < nclasses;
217068de460fSthorpej cl = hfsc_nextclass(cl), n++)
217168de460fSthorpej ;
217268de460fSthorpej if (n != nclasses)
217368de460fSthorpej return (EINVAL);
217468de460fSthorpej
217568de460fSthorpej /* then, read the next N classes in the tree */
217668de460fSthorpej nclasses = ap->nclasses;
217768de460fSthorpej usp = ap->stats;
217868de460fSthorpej for (n = 0; cl != NULL && n < nclasses; cl = hfsc_nextclass(cl), n++) {
217968de460fSthorpej
2180b593575dSriastradh memset(&stats, 0, sizeof(stats));
218168de460fSthorpej get_class_stats(&stats, cl);
218268de460fSthorpej
218353524e44Schristos if ((error = copyout((void *)&stats, (void *)usp++,
218468de460fSthorpej sizeof(stats))) != 0)
218568de460fSthorpej return (error);
218668de460fSthorpej }
218768de460fSthorpej
218868de460fSthorpej ap->nclasses = n;
218968de460fSthorpej
219068de460fSthorpej return (0);
219168de460fSthorpej }
219268de460fSthorpej
219368de460fSthorpej #ifdef KLD_MODULE
219468de460fSthorpej
219568de460fSthorpej static struct altqsw hfsc_sw =
219668de460fSthorpej {"hfsc", hfscopen, hfscclose, hfscioctl};
219768de460fSthorpej
219868de460fSthorpej ALTQ_MODULE(altq_hfsc, ALTQT_HFSC, &hfsc_sw);
2199dd191f37Speter MODULE_DEPEND(altq_hfsc, altq_red, 1, 1, 1);
2200dd191f37Speter MODULE_DEPEND(altq_hfsc, altq_rio, 1, 1, 1);
220168de460fSthorpej
220268de460fSthorpej #endif /* KLD_MODULE */
2203dd191f37Speter #endif /* ALTQ3_COMPAT */
220468de460fSthorpej
220568de460fSthorpej #endif /* ALTQ_HFSC */
2206