]> git.saurik.com Git - apple/xnu.git/blob - bsd/net/pktsched/pktsched_hfsc.c
projects / apple / xnu.git / blob
? search:


c7b405380f0e86631d81b50277d8b0cb54ef6e08
[apple/xnu.git] / bsd / net / pktsched / pktsched_hfsc.c
1 /*
2 * Copyright (c) 2007-2012 Apple Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28
29 /* $OpenBSD: altq_hfsc.c,v 1.25 2007/09/13 20:40:02 chl Exp $ */
30 /* $KAME: altq_hfsc.c,v 1.17 2002/11/29 07:48:33 kjc Exp $ */
31
32 /*
33 * Copyright (c) 1997-1999 Carnegie Mellon University. All Rights Reserved.
34 *
35 * Permission to use, copy, modify, and distribute this software and
36 * its documentation is hereby granted (including for commercial or
37 * for-profit use), provided that both the copyright notice and this
38 * permission notice appear in all copies of the software, derivative
39 * works, or modified versions, and any portions thereof.
40 *
41 * THIS SOFTWARE IS EXPERIMENTAL AND IS KNOWN TO HAVE BUGS, SOME OF
42 * WHICH MAY HAVE SERIOUS CONSEQUENCES. CARNEGIE MELLON PROVIDES THIS
43 * SOFTWARE IN ITS ``AS IS'' CONDITION, AND ANY EXPRESS OR IMPLIED
44 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
45 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
46 * DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY BE LIABLE
47 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
48 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
49 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
50 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
51 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
52 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
53 * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
54 * DAMAGE.
55 *
56 * Carnegie Mellon encourages (but does not require) users of this
57 * software to return any improvements or extensions that they make,
58 * and to grant Carnegie Mellon the rights to redistribute these
59 * changes without encumbrance.
60 */
61 /*
62 * H-FSC is described in Proceedings of SIGCOMM'97,
63 * "A Hierarchical Fair Service Curve Algorithm for Link-Sharing,
64 * Real-Time and Priority Service"
65 * by Ion Stoica, Hui Zhang, and T. S. Eugene Ng.
66 *
67 * Oleg Cherevko <olwi@aq.ml.com.ua> added the upperlimit for link-sharing.
68 * when a class has an upperlimit, the fit-time is computed from the
69 * upperlimit service curve. the link-sharing scheduler does not schedule
70 * a class whose fit-time exceeds the current time.
71 */
72
73 #if PKTSCHED_HFSC
74
75 #include <sys/cdefs.h>
76 #include <sys/param.h>
77 #include <sys/malloc.h>
78 #include <sys/mbuf.h>
79 #include <sys/systm.h>
80 #include <sys/errno.h>
81 #include <sys/kernel.h>
82 #include <sys/syslog.h>
83
84 #include <kern/zalloc.h>
85
86 #include <net/if.h>
87 #include <net/net_osdep.h>
88
89 #include <net/pktsched/pktsched_hfsc.h>
90 #include <netinet/in.h>
91
92 /*
93 * function prototypes
94 */
95 #if 0
96 static int hfsc_enqueue_ifclassq(struct ifclassq *, struct mbuf *);
97 static struct mbuf *hfsc_dequeue_ifclassq(struct ifclassq *, cqdq_op_t);
98 static int hfsc_request_ifclassq(struct ifclassq *, cqrq_t, void *);
99 #endif
100 static int hfsc_addq(struct hfsc_class *, struct mbuf *, struct pf_mtag *);
101 static struct mbuf *hfsc_getq(struct hfsc_class *);
102 static struct mbuf *hfsc_pollq(struct hfsc_class *);
103 static void hfsc_purgeq(struct hfsc_if *, struct hfsc_class *, u_int32_t,
104 u_int32_t *, u_int32_t *);
105 static void hfsc_print_sc(struct hfsc_if *, u_int32_t, u_int64_t,
106 struct service_curve *, struct internal_sc *, const char *);
107 static void hfsc_updateq_linkrate(struct hfsc_if *, struct hfsc_class *);
108 static void hfsc_updateq(struct hfsc_if *, struct hfsc_class *, cqev_t);
109
110 static int hfsc_clear_interface(struct hfsc_if *);
111 static struct hfsc_class *hfsc_class_create(struct hfsc_if *,
112 struct service_curve *, struct service_curve *, struct service_curve *,
113 struct hfsc_class *, u_int32_t, int, u_int32_t);
114 static int hfsc_class_destroy(struct hfsc_if *, struct hfsc_class *);
115 static int hfsc_destroy_locked(struct hfsc_if *);
116 static struct hfsc_class *hfsc_nextclass(struct hfsc_class *);
117 static struct hfsc_class *hfsc_clh_to_clp(struct hfsc_if *, u_int32_t);
118 static const char *hfsc_style(struct hfsc_if *);
119
120 static void set_active(struct hfsc_class *, u_int32_t);
121 static void set_passive(struct hfsc_class *);
122
123 static void init_ed(struct hfsc_class *, u_int32_t);
124 static void update_ed(struct hfsc_class *, u_int32_t);
125 static void update_d(struct hfsc_class *, u_int32_t);
126 static void init_vf(struct hfsc_class *, u_int32_t);
127 static void update_vf(struct hfsc_class *, u_int32_t, u_int64_t);
128 static void update_cfmin(struct hfsc_class *);
129 static void ellist_insert(struct hfsc_class *);
130 static void ellist_remove(struct hfsc_class *);
131 static void ellist_update(struct hfsc_class *);
132 static struct hfsc_class *ellist_get_mindl(ellist_t *, u_int64_t);
133 static void actlist_insert(struct hfsc_class *);
134 static void actlist_remove(struct hfsc_class *);
135 static void actlist_update(struct hfsc_class *);
136 static struct hfsc_class *actlist_firstfit(struct hfsc_class *, u_int64_t);
137
138 static inline u_int64_t seg_x2y(u_int64_t, u_int64_t);
139 static inline u_int64_t seg_y2x(u_int64_t, u_int64_t);
140 static inline u_int64_t m2sm(u_int64_t);
141 static inline u_int64_t m2ism(u_int64_t);
142 static inline u_int64_t d2dx(u_int64_t);
143 static u_int64_t sm2m(u_int64_t);
144 static u_int64_t dx2d(u_int64_t);
145
146 static boolean_t sc2isc(struct hfsc_class *, struct service_curve *,
147 struct internal_sc *, u_int64_t);
148 static void rtsc_init(struct runtime_sc *, struct internal_sc *,
149 u_int64_t, u_int64_t);
150 static u_int64_t rtsc_y2x(struct runtime_sc *, u_int64_t);
151 static u_int64_t rtsc_x2y(struct runtime_sc *, u_int64_t);
152 static void rtsc_min(struct runtime_sc *, struct internal_sc *,
153 u_int64_t, u_int64_t);
154
155 #define HFSC_ZONE_MAX 32 /* maximum elements in zone */
156 #define HFSC_ZONE_NAME "pktsched_hfsc" /* zone name */
157
158 static unsigned int hfsc_size; /* size of zone element */
159 static struct zone *hfsc_zone; /* zone for hfsc_if */
160
161 #define HFSC_CL_ZONE_MAX 32 /* maximum elements in zone */
162 #define HFSC_CL_ZONE_NAME "pktsched_hfsc_cl" /* zone name */
163
164 static unsigned int hfsc_cl_size; /* size of zone element */
165 static struct zone *hfsc_cl_zone; /* zone for hfsc_class */
166
167 /*
168 * macros
169 */
170 #define HFSC_IS_A_PARENT_CLASS(cl) ((cl)->cl_children != NULL)
171
172 #define HT_INFINITY 0xffffffffffffffffLL /* infinite time value */
173
174 void
175 hfsc_init(void)
176 {
177 hfsc_size = sizeof (struct hfsc_if);
178 hfsc_zone = zinit(hfsc_size, HFSC_ZONE_MAX * hfsc_size,
179 0, HFSC_ZONE_NAME);
180 if (hfsc_zone == NULL) {
181 panic("%s: failed allocating %s", __func__, HFSC_ZONE_NAME);
182 /* NOTREACHED */
183 }
184 zone_change(hfsc_zone, Z_EXPAND, TRUE);
185 zone_change(hfsc_zone, Z_CALLERACCT, TRUE);
186
187 hfsc_cl_size = sizeof (struct hfsc_class);
188 hfsc_cl_zone = zinit(hfsc_cl_size, HFSC_CL_ZONE_MAX * hfsc_cl_size,
189 0, HFSC_CL_ZONE_NAME);
190 if (hfsc_cl_zone == NULL) {
191 panic("%s: failed allocating %s", __func__, HFSC_CL_ZONE_NAME);
192 /* NOTREACHED */
193 }
194 zone_change(hfsc_cl_zone, Z_EXPAND, TRUE);
195 zone_change(hfsc_cl_zone, Z_CALLERACCT, TRUE);
196 }
197
198 struct hfsc_if *
199 hfsc_alloc(struct ifnet *ifp, int how, boolean_t altq)
200 {
201 struct hfsc_if *hif;
202
203 hif = (how == M_WAITOK) ? zalloc(hfsc_zone) : zalloc_noblock(hfsc_zone);
204 if (hif == NULL)
205 return (NULL);
206
207 bzero(hif, hfsc_size);
208 TAILQ_INIT(&hif->hif_eligible);
209 hif->hif_ifq = &ifp->if_snd;
210 if (altq) {
211 hif->hif_maxclasses = HFSC_MAX_CLASSES;
212 hif->hif_flags |= HFSCIFF_ALTQ;
213 } else {
214 hif->hif_maxclasses = IFCQ_SC_MAX + 1; /* incl. root class */
215 }
216
217 if ((hif->hif_class_tbl = _MALLOC(sizeof (struct hfsc_class *) *
218 hif->hif_maxclasses, M_DEVBUF, M_WAITOK|M_ZERO)) == NULL) {
219 log(LOG_ERR, "%s: %s unable to allocate class table array\n",
220 if_name(ifp), hfsc_style(hif));
221 goto error;
222 }
223
224 if (pktsched_verbose) {
225 log(LOG_DEBUG, "%s: %s scheduler allocated\n",
226 if_name(ifp), hfsc_style(hif));
227 }
228
229 return (hif);
230
231 error:
232 if (hif->hif_class_tbl != NULL) {
233 _FREE(hif->hif_class_tbl, M_DEVBUF);
234 hif->hif_class_tbl = NULL;
235 }
236 zfree(hfsc_zone, hif);
237
238 return (NULL);
239 }
240
241 int
242 hfsc_destroy(struct hfsc_if *hif)
243 {
244 struct ifclassq *ifq = hif->hif_ifq;
245 int err;
246
247 IFCQ_LOCK(ifq);
248 err = hfsc_destroy_locked(hif);
249 IFCQ_UNLOCK(ifq);
250
251 return (err);
252 }
253
254 static int
255 hfsc_destroy_locked(struct hfsc_if *hif)
256 {
257 IFCQ_LOCK_ASSERT_HELD(hif->hif_ifq);
258
259 (void) hfsc_clear_interface(hif);
260 (void) hfsc_class_destroy(hif, hif->hif_rootclass);
261
262 VERIFY(hif->hif_class_tbl != NULL);
263 _FREE(hif->hif_class_tbl, M_DEVBUF);
264 hif->hif_class_tbl = NULL;
265
266 if (pktsched_verbose) {
267 log(LOG_DEBUG, "%s: %s scheduler destroyed\n",
268 if_name(HFSCIF_IFP(hif)), hfsc_style(hif));
269 }
270
271 zfree(hfsc_zone, hif);
272
273 return (0);
274 }
275
276 /*
277 * bring the interface back to the initial state by discarding
278 * all the filters and classes except the root class.
279 */
280 static int
281 hfsc_clear_interface(struct hfsc_if *hif)
282 {
283 struct hfsc_class *cl;
284
285 IFCQ_LOCK_ASSERT_HELD(hif->hif_ifq);
286
287 /* clear out the classes */
288 while (hif->hif_rootclass != NULL &&
289 (cl = hif->hif_rootclass->cl_children) != NULL) {
290 /*
291 * remove the first leaf class found in the hierarchy
292 * then start over
293 */
294 for (; cl != NULL; cl = hfsc_nextclass(cl)) {
295 if (!HFSC_IS_A_PARENT_CLASS(cl)) {
296 (void) hfsc_class_destroy(hif, cl);
297 break;
298 }
299 }
300 }
301
302 return (0);
303 }
304
305 /* discard all the queued packets on the interface */
306 void
307 hfsc_purge(struct hfsc_if *hif)
308 {
309 struct hfsc_class *cl;
310
311 IFCQ_LOCK_ASSERT_HELD(hif->hif_ifq);
312
313 for (cl = hif->hif_rootclass; cl != NULL; cl = hfsc_nextclass(cl)) {
314 if (!qempty(&cl->cl_q))
315 hfsc_purgeq(hif, cl, 0, NULL, NULL);
316 }
317 #if !PF_ALTQ
318 /*
319 * This assertion is safe to be made only when PF_ALTQ is not
320 * configured; otherwise, IFCQ_LEN represents the sum of the
321 * packets managed by ifcq_disc and altq_disc instances, which
322 * is possible when transitioning between the two.
323 */
324 VERIFY(IFCQ_LEN(hif->hif_ifq) == 0);
325 #endif /* !PF_ALTQ */
326 }
327
328 void
329 hfsc_event(struct hfsc_if *hif, cqev_t ev)
330 {
331 struct hfsc_class *cl;
332
333 IFCQ_LOCK_ASSERT_HELD(hif->hif_ifq);
334
335 for (cl = hif->hif_rootclass; cl != NULL; cl = hfsc_nextclass(cl))
336 hfsc_updateq(hif, cl, ev);
337 }
338
339 int
340 hfsc_add_queue(struct hfsc_if *hif, struct service_curve *rtsc,
341 struct service_curve *lssc, struct service_curve *ulsc,
342 u_int32_t qlimit, int flags, u_int32_t parent_qid, u_int32_t qid,
343 struct hfsc_class **clp)
344 {
345 struct hfsc_class *cl = NULL, *parent;
346
347 IFCQ_LOCK_ASSERT_HELD(hif->hif_ifq);
348
349 if (parent_qid == HFSC_NULLCLASS_HANDLE && hif->hif_rootclass == NULL)
350 parent = NULL;
351 else if ((parent = hfsc_clh_to_clp(hif, parent_qid)) == NULL)
352 return (EINVAL);
353
354 if (hfsc_clh_to_clp(hif, qid) != NULL)
355 return (EBUSY);
356
357 cl = hfsc_class_create(hif, rtsc, lssc, ulsc, parent,
358 qlimit, flags, qid);
359 if (cl == NULL)
360 return (ENOMEM);
361
362 if (clp != NULL)
363 *clp = cl;
364
365 return (0);
366 }
367
368 static struct hfsc_class *
369 hfsc_class_create(struct hfsc_if *hif, struct service_curve *rsc,
370 struct service_curve *fsc, struct service_curve *usc,
371 struct hfsc_class *parent, u_int32_t qlimit, int flags, u_int32_t qid)
372 {
373 struct ifnet *ifp;
374 struct ifclassq *ifq;
375 struct hfsc_class *cl, *p;
376 u_int64_t eff_rate;
377 u_int32_t i;
378
379 IFCQ_LOCK_ASSERT_HELD(hif->hif_ifq);
380
381 /* Sanitize flags unless internally configured */
382 if (hif->hif_flags & HFSCIFF_ALTQ)
383 flags &= HFCF_USERFLAGS;
384
385 if (hif->hif_classes >= hif->hif_maxclasses) {
386 log(LOG_ERR, "%s: %s out of classes! (max %d)\n",
387 if_name(HFSCIF_IFP(hif)), hfsc_style(hif),
388 hif->hif_maxclasses);
389 return (NULL);
390 }
391
392 #if !CLASSQ_RED
393 if (flags & HFCF_RED) {
394 log(LOG_ERR, "%s: %s RED not available!\n",
395 if_name(HFSCIF_IFP(hif)), hfsc_style(hif));
396 return (NULL);
397 }
398 #endif /* !CLASSQ_RED */
399
400 #if !CLASSQ_RIO
401 if (flags & HFCF_RIO) {
402 log(LOG_ERR, "%s: %s RIO not available!\n",
403 if_name(HFSCIF_IFP(hif)), hfsc_style(hif));
404 return (NULL);
405 }
406 #endif /* CLASSQ_RIO */
407
408 #if !CLASSQ_BLUE
409 if (flags & HFCF_BLUE) {
410 log(LOG_ERR, "%s: %s BLUE not available!\n",
411 if_name(HFSCIF_IFP(hif)), hfsc_style(hif));
412 return (NULL);
413 }
414 #endif /* CLASSQ_BLUE */
415
416 /* These are mutually exclusive */
417 if ((flags & (HFCF_RED|HFCF_RIO|HFCF_BLUE|HFCF_SFB)) &&
418 (flags & (HFCF_RED|HFCF_RIO|HFCF_BLUE|HFCF_SFB)) != HFCF_RED &&
419 (flags & (HFCF_RED|HFCF_RIO|HFCF_BLUE|HFCF_SFB)) != HFCF_RIO &&
420 (flags & (HFCF_RED|HFCF_RIO|HFCF_BLUE|HFCF_SFB)) != HFCF_BLUE &&
421 (flags & (HFCF_RED|HFCF_RIO|HFCF_BLUE|HFCF_SFB)) != HFCF_SFB) {
422 log(LOG_ERR, "%s: %s more than one RED|RIO|BLUE|SFB\n",
423 if_name(HFSCIF_IFP(hif)), hfsc_style(hif));
424 return (NULL);
425 }
426
427 cl = zalloc(hfsc_cl_zone);
428 if (cl == NULL)
429 return (NULL);
430
431 bzero(cl, hfsc_cl_size);
432 TAILQ_INIT(&cl->cl_actc);
433 ifq = hif->hif_ifq;
434 ifp = HFSCIF_IFP(hif);
435
436 if (qlimit == 0 || qlimit > IFCQ_MAXLEN(ifq)) {
437 qlimit = IFCQ_MAXLEN(ifq);
438 if (qlimit == 0)
439 qlimit = DEFAULT_QLIMIT; /* use default */
440 }
441 _qinit(&cl->cl_q, Q_DROPTAIL, qlimit);
442
443 cl->cl_flags = flags;
444 if (flags & (HFCF_RED|HFCF_RIO|HFCF_BLUE|HFCF_SFB)) {
445 #if CLASSQ_RED || CLASSQ_RIO
446 int pkttime;
447 #endif /* CLASSQ_RED || CLASSQ_RIO */
448 u_int64_t m2;
449
450 m2 = 0;
451 if (rsc != NULL && rsc->m2 > m2)
452 m2 = rsc->m2;
453 if (fsc != NULL && fsc->m2 > m2)
454 m2 = fsc->m2;
455 if (usc != NULL && usc->m2 > m2)
456 m2 = usc->m2;
457
458 cl->cl_qflags = 0;
459 if (flags & HFCF_ECN) {
460 if (flags & HFCF_BLUE)
461 cl->cl_qflags |= BLUEF_ECN;
462 else if (flags & HFCF_SFB)
463 cl->cl_qflags |= SFBF_ECN;
464 else if (flags & HFCF_RED)
465 cl->cl_qflags |= REDF_ECN;
466 else if (flags & HFCF_RIO)
467 cl->cl_qflags |= RIOF_ECN;
468 }
469 if (flags & HFCF_FLOWCTL) {
470 if (flags & HFCF_SFB)
471 cl->cl_qflags |= SFBF_FLOWCTL;
472 }
473 if (flags & HFCF_CLEARDSCP) {
474 if (flags & HFCF_RIO)
475 cl->cl_qflags |= RIOF_CLEARDSCP;
476 }
477 #if CLASSQ_RED || CLASSQ_RIO
478 /*
479 * XXX: RED & RIO should be watching link speed and MTU
480 * events and recompute pkttime accordingly.
481 */
482 if (m2 < 8)
483 pkttime = 1000 * 1000 * 1000; /* 1 sec */
484 else
485 pkttime = (int64_t)ifp->if_mtu * 1000 * 1000 * 1000 /
486 (m2 / 8);
487
488 /* Test for exclusivity {RED,RIO,BLUE,SFB} was done above */
489 #if CLASSQ_RED
490 if (flags & HFCF_RED) {
491 cl->cl_red = red_alloc(ifp, 0, 0,
492 qlimit(&cl->cl_q) * 10/100,
493 qlimit(&cl->cl_q) * 30/100,
494 cl->cl_qflags, pkttime);
495 if (cl->cl_red != NULL)
496 qtype(&cl->cl_q) = Q_RED;
497 }
498 #endif /* CLASSQ_RED */
499 #if CLASSQ_RIO
500 if (flags & HFCF_RIO) {
501 cl->cl_rio =
502 rio_alloc(ifp, 0, NULL, cl->cl_qflags, pkttime);
503 if (cl->cl_rio != NULL)
504 qtype(&cl->cl_q) = Q_RIO;
505 }
506 #endif /* CLASSQ_RIO */
507 #endif /* CLASSQ_RED || CLASSQ_RIO */
508 #if CLASSQ_BLUE
509 if (flags & HFCF_BLUE) {
510 cl->cl_blue = blue_alloc(ifp, 0, 0, cl->cl_qflags);
511 if (cl->cl_blue != NULL)
512 qtype(&cl->cl_q) = Q_BLUE;
513 }
514 #endif /* CLASSQ_BLUE */
515 if (flags & HFCF_SFB) {
516 if (!(cl->cl_flags & HFCF_LAZY))
517 cl->cl_sfb = sfb_alloc(ifp, qid,
518 qlimit(&cl->cl_q), cl->cl_qflags);
519 if (cl->cl_sfb != NULL || (cl->cl_flags & HFCF_LAZY))
520 qtype(&cl->cl_q) = Q_SFB;
521 }
522 }
523
524 cl->cl_id = hif->hif_classid++;
525 cl->cl_handle = qid;
526 cl->cl_hif = hif;
527 cl->cl_parent = parent;
528
529 eff_rate = ifnet_output_linkrate(HFSCIF_IFP(hif));
530 hif->hif_eff_rate = eff_rate;
531
532 if (rsc != NULL && (rsc->m1 != 0 || rsc->m2 != 0) &&
533 (!(rsc->fl & HFSCF_M1_PCT) || (rsc->m1 > 0 && rsc->m1 <= 100)) &&
534 (!(rsc->fl & HFSCF_M2_PCT) || (rsc->m2 > 0 && rsc->m2 <= 100))) {
535 rsc->fl &= HFSCF_USERFLAGS;
536 cl->cl_flags |= HFCF_RSC;
537 cl->cl_rsc0 = *rsc;
538 (void) sc2isc(cl, &cl->cl_rsc0, &cl->cl_rsc, eff_rate);
539 rtsc_init(&cl->cl_deadline, &cl->cl_rsc, 0, 0);
540 rtsc_init(&cl->cl_eligible, &cl->cl_rsc, 0, 0);
541 }
542 if (fsc != NULL && (fsc->m1 != 0 || fsc->m2 != 0) &&
543 (!(fsc->fl & HFSCF_M1_PCT) || (fsc->m1 > 0 && fsc->m1 <= 100)) &&
544 (!(fsc->fl & HFSCF_M2_PCT) || (fsc->m2 > 0 && fsc->m2 <= 100))) {
545 fsc->fl &= HFSCF_USERFLAGS;
546 cl->cl_flags |= HFCF_FSC;
547 cl->cl_fsc0 = *fsc;
548 (void) sc2isc(cl, &cl->cl_fsc0, &cl->cl_fsc, eff_rate);
549 rtsc_init(&cl->cl_virtual, &cl->cl_fsc, 0, 0);
550 }
551 if (usc != NULL && (usc->m1 != 0 || usc->m2 != 0) &&
552 (!(usc->fl & HFSCF_M1_PCT) || (usc->m1 > 0 && usc->m1 <= 100)) &&
553 (!(usc->fl & HFSCF_M2_PCT) || (usc->m2 > 0 && usc->m2 <= 100))) {
554 usc->fl &= HFSCF_USERFLAGS;
555 cl->cl_flags |= HFCF_USC;
556 cl->cl_usc0 = *usc;
557 (void) sc2isc(cl, &cl->cl_usc0, &cl->cl_usc, eff_rate);
558 rtsc_init(&cl->cl_ulimit, &cl->cl_usc, 0, 0);
559 }
560
561 /*
562 * find a free slot in the class table. if the slot matching
563 * the lower bits of qid is free, use this slot. otherwise,
564 * use the first free slot.
565 */
566 i = qid % hif->hif_maxclasses;
567 if (hif->hif_class_tbl[i] == NULL) {
568 hif->hif_class_tbl[i] = cl;
569 } else {
570 for (i = 0; i < hif->hif_maxclasses; i++)
571 if (hif->hif_class_tbl[i] == NULL) {
572 hif->hif_class_tbl[i] = cl;
573 break;
574 }
575 if (i == hif->hif_maxclasses) {
576 goto err_ret;
577 }
578 }
579 hif->hif_classes++;
580
581 if (flags & HFCF_DEFAULTCLASS)
582 hif->hif_defaultclass = cl;
583
584 if (parent == NULL) {
585 /* this is root class */
586 hif->hif_rootclass = cl;
587 } else {
588 /* add this class to the children list of the parent */
589 if ((p = parent->cl_children) == NULL)
590 parent->cl_children = cl;
591 else {
592 while (p->cl_siblings != NULL)
593 p = p->cl_siblings;
594 p->cl_siblings = cl;
595 }
596 }
597
598 if (pktsched_verbose) {
599 log(LOG_DEBUG, "%s: %s created qid=%d pqid=%d qlimit=%d "
600 "flags=%b\n", if_name(ifp), hfsc_style(hif), cl->cl_handle,
601 (cl->cl_parent != NULL) ? cl->cl_parent->cl_handle : 0,
602 qlimit(&cl->cl_q), cl->cl_flags, HFCF_BITS);
603 if (cl->cl_flags & HFCF_RSC) {
604 hfsc_print_sc(hif, cl->cl_handle, eff_rate,
605 &cl->cl_rsc0, &cl->cl_rsc, "rsc");
606 }
607 if (cl->cl_flags & HFCF_FSC) {
608 hfsc_print_sc(hif, cl->cl_handle, eff_rate,
609 &cl->cl_fsc0, &cl->cl_fsc, "fsc");
610 }
611 if (cl->cl_flags & HFCF_USC) {
612 hfsc_print_sc(hif, cl->cl_handle, eff_rate,
613 &cl->cl_usc0, &cl->cl_usc, "usc");
614 }
615 }
616
617 return (cl);
618
619 err_ret:
620 if (cl->cl_qalg.ptr != NULL) {
621 #if CLASSQ_RIO
622 if (q_is_rio(&cl->cl_q))
623 rio_destroy(cl->cl_rio);
624 #endif /* CLASSQ_RIO */
625 #if CLASSQ_RED
626 if (q_is_red(&cl->cl_q))
627 red_destroy(cl->cl_red);
628 #endif /* CLASSQ_RED */
629 #if CLASSQ_BLUE
630 if (q_is_blue(&cl->cl_q))
631 blue_destroy(cl->cl_blue);
632 #endif /* CLASSQ_BLUE */
633 if (q_is_sfb(&cl->cl_q) && cl->cl_sfb != NULL)
634 sfb_destroy(cl->cl_sfb);
635 cl->cl_qalg.ptr = NULL;
636 qtype(&cl->cl_q) = Q_DROPTAIL;
637 qstate(&cl->cl_q) = QS_RUNNING;
638 }
639 zfree(hfsc_cl_zone, cl);
640 return (NULL);
641 }
642
643 int
644 hfsc_remove_queue(struct hfsc_if *hif, u_int32_t qid)
645 {
646 struct hfsc_class *cl;
647
648 IFCQ_LOCK_ASSERT_HELD(hif->hif_ifq);
649
650 if ((cl = hfsc_clh_to_clp(hif, qid)) == NULL)
651 return (EINVAL);
652
653 return (hfsc_class_destroy(hif, cl));
654 }
655
656 static int
657 hfsc_class_destroy(struct hfsc_if *hif, struct hfsc_class *cl)
658 {
659 u_int32_t i;
660
661 if (cl == NULL)
662 return (0);
663
664 if (HFSC_IS_A_PARENT_CLASS(cl))
665 return (EBUSY);
666
667 IFCQ_LOCK_ASSERT_HELD(hif->hif_ifq);
668
669 if (!qempty(&cl->cl_q))
670 hfsc_purgeq(hif, cl, 0, NULL, NULL);
671
672 if (cl->cl_parent == NULL) {
673 /* this is root class */
674 } else {
675 struct hfsc_class *p = cl->cl_parent->cl_children;
676
677 if (p == cl)
678 cl->cl_parent->cl_children = cl->cl_siblings;
679 else do {
680 if (p->cl_siblings == cl) {
681 p->cl_siblings = cl->cl_siblings;
682 break;
683 }
684 } while ((p = p->cl_siblings) != NULL);
685 VERIFY(p != NULL);
686 }
687
688 for (i = 0; i < hif->hif_maxclasses; i++)
689 if (hif->hif_class_tbl[i] == cl) {
690 hif->hif_class_tbl[i] = NULL;
691 break;
692 }
693
694 hif->hif_classes--;
695
696 if (cl->cl_qalg.ptr != NULL) {
697 #if CLASSQ_RIO
698 if (q_is_rio(&cl->cl_q))
699 rio_destroy(cl->cl_rio);
700 #endif /* CLASSQ_RIO */
701 #if CLASSQ_RED
702 if (q_is_red(&cl->cl_q))
703 red_destroy(cl->cl_red);
704 #endif /* CLASSQ_RED */
705 #if CLASSQ_BLUE
706 if (q_is_blue(&cl->cl_q))
707 blue_destroy(cl->cl_blue);
708 #endif /* CLASSQ_BLUE */
709 if (q_is_sfb(&cl->cl_q) && cl->cl_sfb != NULL)
710 sfb_destroy(cl->cl_sfb);
711 cl->cl_qalg.ptr = NULL;
712 qtype(&cl->cl_q) = Q_DROPTAIL;
713 qstate(&cl->cl_q) = QS_RUNNING;
714 }
715
716 if (cl == hif->hif_rootclass)
717 hif->hif_rootclass = NULL;
718 if (cl == hif->hif_defaultclass)
719 hif->hif_defaultclass = NULL;
720
721 if (pktsched_verbose) {
722 log(LOG_DEBUG, "%s: %s destroyed qid=%d slot=%d\n",
723 if_name(HFSCIF_IFP(hif)), hfsc_style(hif),
724 cl->cl_handle, cl->cl_id);
725 }
726
727 zfree(hfsc_cl_zone, cl);
728
729 return (0);
730 }
731
732 /*
733 * hfsc_nextclass returns the next class in the tree.
734 * usage:
735 * for (cl = hif->hif_rootclass; cl != NULL; cl = hfsc_nextclass(cl))
736 * do_something;
737 */
738 static struct hfsc_class *
739 hfsc_nextclass(struct hfsc_class *cl)
740 {
741 IFCQ_LOCK_ASSERT_HELD(cl->cl_hif->hif_ifq);
742
743 if (cl->cl_children != NULL)
744 cl = cl->cl_children;
745 else if (cl->cl_siblings != NULL)
746 cl = cl->cl_siblings;
747 else {
748 while ((cl = cl->cl_parent) != NULL)
749 if (cl->cl_siblings) {
750 cl = cl->cl_siblings;
751 break;
752 }
753 }
754
755 return (cl);
756 }
757
758 int
759 hfsc_enqueue(struct hfsc_if *hif, struct hfsc_class *cl, struct mbuf *m,
760 struct pf_mtag *t)
761 {
762 struct ifclassq *ifq = hif->hif_ifq;
763 u_int32_t len;
764 int ret;
765
766 IFCQ_LOCK_ASSERT_HELD(ifq);
767 VERIFY(cl == NULL || cl->cl_hif == hif);
768
769 if (cl == NULL) {
770 cl = hfsc_clh_to_clp(hif, t->pftag_qid);
771 if (cl == NULL || HFSC_IS_A_PARENT_CLASS(cl)) {
772 cl = hif->hif_defaultclass;
773 if (cl == NULL) {
774 IFCQ_CONVERT_LOCK(ifq);
775 m_freem(m);
776 return (ENOBUFS);
777 }
778 }
779 }
780
781 len = m_pktlen(m);
782
783 ret = hfsc_addq(cl, m, t);
784 if (ret != 0) {
785 if (ret == CLASSQEQ_SUCCESS_FC) {
786 /* packet enqueued, return advisory feedback */
787 ret = EQFULL;
788 } else {
789 VERIFY(ret == CLASSQEQ_DROPPED ||
790 ret == CLASSQEQ_DROPPED_FC ||
791 ret == CLASSQEQ_DROPPED_SP);
792 /* packet has been freed in hfsc_addq */
793 PKTCNTR_ADD(&cl->cl_stats.drop_cnt, 1, len);
794 IFCQ_DROP_ADD(ifq, 1, len);
795 switch (ret) {
796 case CLASSQEQ_DROPPED:
797 return (ENOBUFS);
798 case CLASSQEQ_DROPPED_FC:
799 return (EQFULL);
800 case CLASSQEQ_DROPPED_SP:
801 return (EQSUSPENDED);
802 }
803 /* NOT_REACHED */
804 }
805 }
806 IFCQ_INC_LEN(ifq);
807 cl->cl_hif->hif_packets++;
808
809 /* successfully queued. */
810 if (qlen(&cl->cl_q) == 1)
811 set_active(cl, len);
812
813 return (ret);
814 }
815
816 /*
817 * note: CLASSQDQ_POLL returns the next packet without removing the packet
818 * from the queue. CLASSQDQ_REMOVE is a normal dequeue operation.
819 * CLASSQDQ_REMOVE must return the same packet if called immediately
820 * after CLASSQDQ_POLL.
821 */
822 struct mbuf *
823 hfsc_dequeue(struct hfsc_if *hif, cqdq_op_t op)
824 {
825 struct ifclassq *ifq = hif->hif_ifq;
826 struct hfsc_class *cl;
827 struct mbuf *m;
828 u_int32_t len, next_len;
829 int realtime = 0;
830 u_int64_t cur_time;
831
832 IFCQ_LOCK_ASSERT_HELD(ifq);
833
834 if (hif->hif_packets == 0)
835 /* no packet in the tree */
836 return (NULL);
837
838 cur_time = read_machclk();
839
840 if (op == CLASSQDQ_REMOVE && hif->hif_pollcache != NULL) {
841
842 cl = hif->hif_pollcache;
843 hif->hif_pollcache = NULL;
844 /* check if the class was scheduled by real-time criteria */
845 if (cl->cl_flags & HFCF_RSC)
846 realtime = (cl->cl_e <= cur_time);
847 } else {
848 /*
849 * if there are eligible classes, use real-time criteria.
850 * find the class with the minimum deadline among
851 * the eligible classes.
852 */
853 if ((cl = ellist_get_mindl(&hif->hif_eligible, cur_time))
854 != NULL) {
855 realtime = 1;
856 } else {
857 int fits = 0;
858 /*
859 * use link-sharing criteria
860 * get the class with the minimum vt in the hierarchy
861 */
862 cl = hif->hif_rootclass;
863 while (HFSC_IS_A_PARENT_CLASS(cl)) {
864
865 cl = actlist_firstfit(cl, cur_time);
866 if (cl == NULL) {
867 if (fits > 0)
868 log(LOG_ERR, "%s: %s "
869 "%d fit but none found\n",
870 if_name(HFSCIF_IFP(hif)),
871 hfsc_style(hif), fits);
872 return (NULL);
873 }
874 /*
875 * update parent's cl_cvtmin.
876 * don't update if the new vt is smaller.
877 */
878 if (cl->cl_parent->cl_cvtmin < cl->cl_vt)
879 cl->cl_parent->cl_cvtmin = cl->cl_vt;
880 fits++;
881 }
882 }
883
884 if (op == CLASSQDQ_POLL) {
885 hif->hif_pollcache = cl;
886 m = hfsc_pollq(cl);
887 return (m);
888 }
889 }
890
891 m = hfsc_getq(cl);
892 VERIFY(m != NULL);
893 len = m_pktlen(m);
894 cl->cl_hif->hif_packets--;
895 IFCQ_DEC_LEN(ifq);
896 IFCQ_XMIT_ADD(ifq, 1, len);
897 PKTCNTR_ADD(&cl->cl_stats.xmit_cnt, 1, len);
898
899 update_vf(cl, len, cur_time);
900 if (realtime)
901 cl->cl_cumul += len;
902
903 if (!qempty(&cl->cl_q)) {
904 if (cl->cl_flags & HFCF_RSC) {
905 /* update ed */
906 next_len = m_pktlen(qhead(&cl->cl_q));
907
908 if (realtime)
909 update_ed(cl, next_len);
910 else
911 update_d(cl, next_len);
912 }
913 } else {
914 /* the class becomes passive */
915 set_passive(cl);
916 }
917
918 return (m);
919
920 }
921
922 static int
923 hfsc_addq(struct hfsc_class *cl, struct mbuf *m, struct pf_mtag *t)
924 {
925 struct ifclassq *ifq = cl->cl_hif->hif_ifq;
926
927 IFCQ_LOCK_ASSERT_HELD(ifq);
928
929 #if CLASSQ_RIO
930 if (q_is_rio(&cl->cl_q))
931 return (rio_addq(cl->cl_rio, &cl->cl_q, m, t));
932 else
933 #endif /* CLASSQ_RIO */
934 #if CLASSQ_RED
935 if (q_is_red(&cl->cl_q))
936 return (red_addq(cl->cl_red, &cl->cl_q, m, t));
937 else
938 #endif /* CLASSQ_RED */
939 #if CLASSQ_BLUE
940 if (q_is_blue(&cl->cl_q))
941 return (blue_addq(cl->cl_blue, &cl->cl_q, m, t));
942 else
943 #endif /* CLASSQ_BLUE */
944 if (q_is_sfb(&cl->cl_q)) {
945 if (cl->cl_sfb == NULL) {
946 struct ifnet *ifp = HFSCIF_IFP(cl->cl_hif);
947
948 VERIFY(cl->cl_flags & HFCF_LAZY);
949 IFCQ_CONVERT_LOCK(ifq);
950
951 cl->cl_sfb = sfb_alloc(ifp, cl->cl_handle,
952 qlimit(&cl->cl_q), cl->cl_qflags);
953 if (cl->cl_sfb == NULL) {
954 /* fall back to droptail */
955 qtype(&cl->cl_q) = Q_DROPTAIL;
956 cl->cl_flags &= ~HFCF_SFB;
957 cl->cl_qflags &= ~(SFBF_ECN | SFBF_FLOWCTL);
958
959 log(LOG_ERR, "%s: %s SFB lazy allocation "
960 "failed for qid=%d slot=%d, falling back "
961 "to DROPTAIL\n", if_name(ifp),
962 hfsc_style(cl->cl_hif), cl->cl_handle,
963 cl->cl_id);
964 }
965 }
966 if (cl->cl_sfb != NULL)
967 return (sfb_addq(cl->cl_sfb, &cl->cl_q, m, t));
968 } else if (qlen(&cl->cl_q) >= qlimit(&cl->cl_q)) {
969 IFCQ_CONVERT_LOCK(ifq);
970 m_freem(m);
971 return (CLASSQEQ_DROPPED);
972 }
973
974 if (cl->cl_flags & HFCF_CLEARDSCP)
975 write_dsfield(m, t, 0);
976
977 _addq(&cl->cl_q, m);
978
979 return (0);
980 }
981
982 static struct mbuf *
983 hfsc_getq(struct hfsc_class *cl)
984 {
985 IFCQ_LOCK_ASSERT_HELD(cl->cl_hif->hif_ifq);
986
987 #if CLASSQ_RIO
988 if (q_is_rio(&cl->cl_q))
989 return (rio_getq(cl->cl_rio, &cl->cl_q));
990 else
991 #endif /* CLASSQ_RIO */
992 #if CLASSQ_RED
993 if (q_is_red(&cl->cl_q))
994 return (red_getq(cl->cl_red, &cl->cl_q));
995 else
996 #endif /* CLASSQ_RED */
997 #if CLASSQ_BLUE
998 if (q_is_blue(&cl->cl_q))
999 return (blue_getq(cl->cl_blue, &cl->cl_q));
1000 else
1001 #endif /* CLASSQ_BLUE */
1002 if (q_is_sfb(&cl->cl_q) && cl->cl_sfb != NULL)
1003 return (sfb_getq(cl->cl_sfb, &cl->cl_q));
1004
1005 return (_getq(&cl->cl_q));
1006 }
1007
1008 static struct mbuf *
1009 hfsc_pollq(struct hfsc_class *cl)
1010 {
1011 IFCQ_LOCK_ASSERT_HELD(cl->cl_hif->hif_ifq);
1012
1013 return (qhead(&cl->cl_q));
1014 }
1015
1016 static void
1017 hfsc_purgeq(struct hfsc_if *hif, struct hfsc_class *cl, u_int32_t flow,
1018 u_int32_t *packets, u_int32_t *bytes)
1019 {
1020 struct ifclassq *ifq = hif->hif_ifq;
1021 u_int32_t cnt = 0, len = 0, qlen;
1022
1023 IFCQ_LOCK_ASSERT_HELD(ifq);
1024
1025 if ((qlen = qlen(&cl->cl_q)) == 0) {
1026 VERIFY(hif->hif_packets == 0);
1027 goto done;
1028 }
1029
1030 /* become regular mutex before freeing mbufs */
1031 IFCQ_CONVERT_LOCK(ifq);
1032
1033 #if CLASSQ_RIO
1034 if (q_is_rio(&cl->cl_q))
1035 rio_purgeq(cl->cl_rio, &cl->cl_q, flow, &cnt, &len);
1036 else
1037 #endif /* CLASSQ_RIO */
1038 #if CLASSQ_RED
1039 if (q_is_red(&cl->cl_q))
1040 red_purgeq(cl->cl_red, &cl->cl_q, flow, &cnt, &len);
1041 else
1042 #endif /* CLASSQ_RED */
1043 #if CLASSQ_BLUE
1044 if (q_is_blue(&cl->cl_q))
1045 blue_purgeq(cl->cl_blue, &cl->cl_q, flow, &cnt, &len);
1046 else
1047 #endif /* CLASSQ_BLUE */
1048 if (q_is_sfb(&cl->cl_q) && cl->cl_sfb != NULL)
1049 sfb_purgeq(cl->cl_sfb, &cl->cl_q, flow, &cnt, &len);
1050 else
1051 _flushq_flow(&cl->cl_q, flow, &cnt, &len);
1052
1053 if (cnt > 0) {
1054 VERIFY(qlen(&cl->cl_q) == (qlen - cnt));
1055
1056 PKTCNTR_ADD(&cl->cl_stats.drop_cnt, cnt, len);
1057 IFCQ_DROP_ADD(ifq, cnt, len);
1058
1059 VERIFY(hif->hif_packets >= cnt);
1060 hif->hif_packets -= cnt;
1061
1062 VERIFY(((signed)IFCQ_LEN(ifq) - cnt) >= 0);
1063 IFCQ_LEN(ifq) -= cnt;
1064
1065 if (qempty(&cl->cl_q)) {
1066 update_vf(cl, 0, 0); /* remove cl from the actlist */
1067 set_passive(cl);
1068 }
1069
1070 if (pktsched_verbose) {
1071 log(LOG_DEBUG, "%s: %s purge qid=%d slot=%d "
1072 "qlen=[%d,%d] cnt=%d len=%d flow=0x%x\n",
1073 if_name(HFSCIF_IFP(hif)), hfsc_style(hif),
1074 cl->cl_handle, cl->cl_id, qlen, qlen(&cl->cl_q),
1075 cnt, len, flow);
1076 }
1077 }
1078 done:
1079 if (packets != NULL)
1080 *packets = cnt;
1081 if (bytes != NULL)
1082 *bytes = len;
1083 }
1084
1085 static void
1086 hfsc_print_sc(struct hfsc_if *hif, u_int32_t qid, u_int64_t eff_rate,
1087 struct service_curve *sc, struct internal_sc *isc, const char *which)
1088 {
1089 struct ifnet *ifp = HFSCIF_IFP(hif);
1090
1091 log(LOG_DEBUG, "%s: %s qid=%d {%s_m1=%llu%s [%llu], "
1092 "%s_d=%u msec, %s_m2=%llu%s [%llu]} linkrate=%llu bps\n",
1093 if_name(ifp), hfsc_style(hif), qid,
1094 which, sc->m1, (sc->fl & HFSCF_M1_PCT) ? "%" : " bps", isc->sm1,
1095 which, sc->d,
1096 which, sc->m2, (sc->fl & HFSCF_M2_PCT) ? "%" : " bps", isc->sm2,
1097 eff_rate);
1098 }
1099
1100 static void
1101 hfsc_updateq_linkrate(struct hfsc_if *hif, struct hfsc_class *cl)
1102 {
1103 u_int64_t eff_rate = ifnet_output_linkrate(HFSCIF_IFP(hif));
1104 struct service_curve *sc;
1105 struct internal_sc *isc;
1106
1107 /* Update parameters only if rate has changed */
1108 if (eff_rate == hif->hif_eff_rate)
1109 return;
1110
1111 sc = &cl->cl_rsc0;
1112 isc = &cl->cl_rsc;
1113 if ((cl->cl_flags & HFCF_RSC) && sc2isc(cl, sc, isc, eff_rate)) {
1114 rtsc_init(&cl->cl_deadline, isc, 0, 0);
1115 rtsc_init(&cl->cl_eligible, isc, 0, 0);
1116 if (pktsched_verbose) {
1117 hfsc_print_sc(hif, cl->cl_handle, eff_rate,
1118 sc, isc, "rsc");
1119 }
1120 }
1121 sc = &cl->cl_fsc0;
1122 isc = &cl->cl_fsc;
1123 if ((cl->cl_flags & HFCF_FSC) && sc2isc(cl, sc, isc, eff_rate)) {
1124 rtsc_init(&cl->cl_virtual, isc, 0, 0);
1125 if (pktsched_verbose) {
1126 hfsc_print_sc(hif, cl->cl_handle, eff_rate,
1127 sc, isc, "fsc");
1128 }
1129 }
1130 sc = &cl->cl_usc0;
1131 isc = &cl->cl_usc;
1132 if ((cl->cl_flags & HFCF_USC) && sc2isc(cl, sc, isc, eff_rate)) {
1133 rtsc_init(&cl->cl_ulimit, isc, 0, 0);
1134 if (pktsched_verbose) {
1135 hfsc_print_sc(hif, cl->cl_handle, eff_rate,
1136 sc, isc, "usc");
1137 }
1138 }
1139 }
1140
1141 static void
1142 hfsc_updateq(struct hfsc_if *hif, struct hfsc_class *cl, cqev_t ev)
1143 {
1144 IFCQ_LOCK_ASSERT_HELD(hif->hif_ifq);
1145
1146 if (pktsched_verbose) {
1147 log(LOG_DEBUG, "%s: %s update qid=%d slot=%d event=%s\n",
1148 if_name(HFSCIF_IFP(hif)), hfsc_style(hif),
1149 cl->cl_handle, cl->cl_id, ifclassq_ev2str(ev));
1150 }
1151
1152 if (ev == CLASSQ_EV_LINK_SPEED)
1153 hfsc_updateq_linkrate(hif, cl);
1154
1155 #if CLASSQ_RIO
1156 if (q_is_rio(&cl->cl_q))
1157 return (rio_updateq(cl->cl_rio, ev));
1158 #endif /* CLASSQ_RIO */
1159 #if CLASSQ_RED
1160 if (q_is_red(&cl->cl_q))
1161 return (red_updateq(cl->cl_red, ev));
1162 #endif /* CLASSQ_RED */
1163 #if CLASSQ_BLUE
1164 if (q_is_blue(&cl->cl_q))
1165 return (blue_updateq(cl->cl_blue, ev));
1166 #endif /* CLASSQ_BLUE */
1167 if (q_is_sfb(&cl->cl_q) && cl->cl_sfb != NULL)
1168 return (sfb_updateq(cl->cl_sfb, ev));
1169 }
1170
1171 static void
1172 set_active(struct hfsc_class *cl, u_int32_t len)
1173 {
1174 if (cl->cl_flags & HFCF_RSC)
1175 init_ed(cl, len);
1176 if (cl->cl_flags & HFCF_FSC)
1177 init_vf(cl, len);
1178
1179 cl->cl_stats.period++;
1180 }
1181
1182 static void
1183 set_passive(struct hfsc_class *cl)
1184 {
1185 if (cl->cl_flags & HFCF_RSC)
1186 ellist_remove(cl);
1187
1188 /*
1189 * actlist is now handled in update_vf() so that update_vf(cl, 0, 0)
1190 * needs to be called explicitly to remove a class from actlist
1191 */
1192 }
1193
1194 static void
1195 init_ed(struct hfsc_class *cl, u_int32_t next_len)
1196 {
1197 u_int64_t cur_time;
1198
1199 cur_time = read_machclk();
1200
1201 /* update the deadline curve */
1202 rtsc_min(&cl->cl_deadline, &cl->cl_rsc, cur_time, cl->cl_cumul);
1203
1204 /*
1205 * update the eligible curve.
1206 * for concave, it is equal to the deadline curve.
1207 * for convex, it is a linear curve with slope m2.
1208 */
1209 cl->cl_eligible = cl->cl_deadline;
1210 if (cl->cl_rsc.sm1 <= cl->cl_rsc.sm2) {
1211 cl->cl_eligible.dx = 0;
1212 cl->cl_eligible.dy = 0;
1213 }
1214
1215 /* compute e and d */
1216 cl->cl_e = rtsc_y2x(&cl->cl_eligible, cl->cl_cumul);
1217 cl->cl_d = rtsc_y2x(&cl->cl_deadline, cl->cl_cumul + next_len);
1218
1219 ellist_insert(cl);
1220 }
1221
1222 static void
1223 update_ed(struct hfsc_class *cl, u_int32_t next_len)
1224 {
1225 cl->cl_e = rtsc_y2x(&cl->cl_eligible, cl->cl_cumul);
1226 cl->cl_d = rtsc_y2x(&cl->cl_deadline, cl->cl_cumul + next_len);
1227
1228 ellist_update(cl);
1229 }
1230
1231 static void
1232 update_d(struct hfsc_class *cl, u_int32_t next_len)
1233 {
1234 cl->cl_d = rtsc_y2x(&cl->cl_deadline, cl->cl_cumul + next_len);
1235 }
1236
1237 static void
1238 init_vf(struct hfsc_class *cl, u_int32_t len)
1239 {
1240 #pragma unused(len)
1241 struct hfsc_class *max_cl, *p;
1242 u_int64_t vt, f, cur_time;
1243 int go_active;
1244
1245 cur_time = 0;
1246 go_active = 1;
1247 for (; cl->cl_parent != NULL; cl = cl->cl_parent) {
1248
1249 if (go_active && cl->cl_nactive++ == 0)
1250 go_active = 1;
1251 else
1252 go_active = 0;
1253
1254 if (go_active) {
1255 max_cl = actlist_last(&cl->cl_parent->cl_actc);
1256 if (max_cl != NULL) {
1257 /*
1258 * set vt to the average of the min and max
1259 * classes. if the parent's period didn't
1260 * change, don't decrease vt of the class.
1261 */
1262 vt = max_cl->cl_vt;
1263 if (cl->cl_parent->cl_cvtmin != 0)
1264 vt = (cl->cl_parent->cl_cvtmin + vt)/2;
1265
1266 if (cl->cl_parent->cl_vtperiod !=
1267 cl->cl_parentperiod || vt > cl->cl_vt)
1268 cl->cl_vt = vt;
1269 } else {
1270 /*
1271 * first child for a new parent backlog period.
1272 * add parent's cvtmax to vtoff of children
1273 * to make a new vt (vtoff + vt) larger than
1274 * the vt in the last period for all children.
1275 */
1276 vt = cl->cl_parent->cl_cvtmax;
1277 for (p = cl->cl_parent->cl_children; p != NULL;
1278 p = p->cl_siblings)
1279 p->cl_vtoff += vt;
1280 cl->cl_vt = 0;
1281 cl->cl_parent->cl_cvtmax = 0;
1282 cl->cl_parent->cl_cvtmin = 0;
1283 }
1284 cl->cl_initvt = cl->cl_vt;
1285
1286 /* update the virtual curve */
1287 vt = cl->cl_vt + cl->cl_vtoff;
1288 rtsc_min(&cl->cl_virtual, &cl->cl_fsc,
1289 vt, cl->cl_total);
1290 if (cl->cl_virtual.x == vt) {
1291 cl->cl_virtual.x -= cl->cl_vtoff;
1292 cl->cl_vtoff = 0;
1293 }
1294 cl->cl_vtadj = 0;
1295
1296 cl->cl_vtperiod++; /* increment vt period */
1297 cl->cl_parentperiod = cl->cl_parent->cl_vtperiod;
1298 if (cl->cl_parent->cl_nactive == 0)
1299 cl->cl_parentperiod++;
1300 cl->cl_f = 0;
1301
1302 actlist_insert(cl);
1303
1304 if (cl->cl_flags & HFCF_USC) {
1305 /* class has upper limit curve */
1306 if (cur_time == 0)
1307 cur_time = read_machclk();
1308
1309 /* update the ulimit curve */
1310 rtsc_min(&cl->cl_ulimit, &cl->cl_usc, cur_time,
1311 cl->cl_total);
1312 /* compute myf */
1313 cl->cl_myf = rtsc_y2x(&cl->cl_ulimit,
1314 cl->cl_total);
1315 cl->cl_myfadj = 0;
1316 }
1317 }
1318
1319 if (cl->cl_myf > cl->cl_cfmin)
1320 f = cl->cl_myf;
1321 else
1322 f = cl->cl_cfmin;
1323 if (f != cl->cl_f) {
1324 cl->cl_f = f;
1325 update_cfmin(cl->cl_parent);
1326 }
1327 }
1328 }
1329
1330 static void
1331 update_vf(struct hfsc_class *cl, u_int32_t len, u_int64_t cur_time)
1332 {
1333 #pragma unused(cur_time)
1334 #if 0
1335 u_int64_t myf_bound, delta;
1336 #endif
1337 u_int64_t f;
1338 int go_passive;
1339
1340 go_passive = (qempty(&cl->cl_q) && (cl->cl_flags & HFCF_FSC));
1341
1342 for (; cl->cl_parent != NULL; cl = cl->cl_parent) {
1343
1344 cl->cl_total += len;
1345
1346 if (!(cl->cl_flags & HFCF_FSC) || cl->cl_nactive == 0)
1347 continue;
1348
1349 if (go_passive && --cl->cl_nactive == 0)
1350 go_passive = 1;
1351 else
1352 go_passive = 0;
1353
1354 if (go_passive) {
1355 /* no more active child, going passive */
1356
1357 /* update cvtmax of the parent class */
1358 if (cl->cl_vt > cl->cl_parent->cl_cvtmax)
1359 cl->cl_parent->cl_cvtmax = cl->cl_vt;
1360
1361 /* remove this class from the vt list */
1362 actlist_remove(cl);
1363
1364 update_cfmin(cl->cl_parent);
1365
1366 continue;
1367 }
1368
1369 /*
1370 * update vt and f
1371 */
1372 cl->cl_vt = rtsc_y2x(&cl->cl_virtual, cl->cl_total)
1373 - cl->cl_vtoff + cl->cl_vtadj;
1374
1375 /*
1376 * if vt of the class is smaller than cvtmin,
1377 * the class was skipped in the past due to non-fit.
1378 * if so, we need to adjust vtadj.
1379 */
1380 if (cl->cl_vt < cl->cl_parent->cl_cvtmin) {
1381 cl->cl_vtadj += cl->cl_parent->cl_cvtmin - cl->cl_vt;
1382 cl->cl_vt = cl->cl_parent->cl_cvtmin;
1383 }
1384
1385 /* update the vt list */
1386 actlist_update(cl);
1387
1388 if (cl->cl_flags & HFCF_USC) {
1389 cl->cl_myf = cl->cl_myfadj +
1390 rtsc_y2x(&cl->cl_ulimit, cl->cl_total);
1391 #if 0
1392 /*
1393 * if myf lags behind by more than one clock tick
1394 * from the current time, adjust myfadj to prevent
1395 * a rate-limited class from going greedy.
1396 * in a steady state under rate-limiting, myf
1397 * fluctuates within one clock tick.
1398 */
1399 myf_bound = cur_time - machclk_per_tick;
1400 if (cl->cl_myf < myf_bound) {
1401 delta = cur_time - cl->cl_myf;
1402 cl->cl_myfadj += delta;
1403 cl->cl_myf += delta;
1404 }
1405 #endif
1406 }
1407
1408 /* cl_f is max(cl_myf, cl_cfmin) */
1409 if (cl->cl_myf > cl->cl_cfmin)
1410 f = cl->cl_myf;
1411 else
1412 f = cl->cl_cfmin;
1413 if (f != cl->cl_f) {
1414 cl->cl_f = f;
1415 update_cfmin(cl->cl_parent);
1416 }
1417 }
1418 }
1419
1420 static void
1421 update_cfmin(struct hfsc_class *cl)
1422 {
1423 struct hfsc_class *p;
1424 u_int64_t cfmin;
1425
1426 if (TAILQ_EMPTY(&cl->cl_actc)) {
1427 cl->cl_cfmin = 0;
1428 return;
1429 }
1430 cfmin = HT_INFINITY;
1431 TAILQ_FOREACH(p, &cl->cl_actc, cl_actlist) {
1432 if (p->cl_f == 0) {
1433 cl->cl_cfmin = 0;
1434 return;
1435 }
1436 if (p->cl_f < cfmin)
1437 cfmin = p->cl_f;
1438 }
1439 cl->cl_cfmin = cfmin;
1440 }
1441
1442 /*
1443 * TAILQ based ellist and actlist implementation
1444 * (ion wanted to make a calendar queue based implementation)
1445 */
1446 /*
1447 * eligible list holds backlogged classes being sorted by their eligible times.
1448 * there is one eligible list per interface.
1449 */
1450
1451 static void
1452 ellist_insert(struct hfsc_class *cl)
1453 {
1454 struct hfsc_if *hif = cl->cl_hif;
1455 struct hfsc_class *p;
1456
1457 /* check the last entry first */
1458 if ((p = TAILQ_LAST(&hif->hif_eligible, _eligible)) == NULL ||
1459 p->cl_e <= cl->cl_e) {
1460 TAILQ_INSERT_TAIL(&hif->hif_eligible, cl, cl_ellist);
1461 return;
1462 }
1463
1464 TAILQ_FOREACH(p, &hif->hif_eligible, cl_ellist) {
1465 if (cl->cl_e < p->cl_e) {
1466 TAILQ_INSERT_BEFORE(p, cl, cl_ellist);
1467 return;
1468 }
1469 }
1470 VERIFY(0); /* should not reach here */
1471 }
1472
1473 static void
1474 ellist_remove(struct hfsc_class *cl)
1475 {
1476 struct hfsc_if *hif = cl->cl_hif;
1477
1478 TAILQ_REMOVE(&hif->hif_eligible, cl, cl_ellist);
1479 }
1480
1481 static void
1482 ellist_update(struct hfsc_class *cl)
1483 {
1484 struct hfsc_if *hif = cl->cl_hif;
1485 struct hfsc_class *p, *last;
1486
1487 /*
1488 * the eligible time of a class increases monotonically.
1489 * if the next entry has a larger eligible time, nothing to do.
1490 */
1491 p = TAILQ_NEXT(cl, cl_ellist);
1492 if (p == NULL || cl->cl_e <= p->cl_e)
1493 return;
1494
1495 /* check the last entry */
1496 last = TAILQ_LAST(&hif->hif_eligible, _eligible);
1497 VERIFY(last != NULL);
1498 if (last->cl_e <= cl->cl_e) {
1499 TAILQ_REMOVE(&hif->hif_eligible, cl, cl_ellist);
1500 TAILQ_INSERT_TAIL(&hif->hif_eligible, cl, cl_ellist);
1501 return;
1502 }
1503
1504 /*
1505 * the new position must be between the next entry
1506 * and the last entry
1507 */
1508 while ((p = TAILQ_NEXT(p, cl_ellist)) != NULL) {
1509 if (cl->cl_e < p->cl_e) {
1510 TAILQ_REMOVE(&hif->hif_eligible, cl, cl_ellist);
1511 TAILQ_INSERT_BEFORE(p, cl, cl_ellist);
1512 return;
1513 }
1514 }
1515 VERIFY(0); /* should not reach here */
1516 }
1517
1518 /* find the class with the minimum deadline among the eligible classes */
1519 static struct hfsc_class *
1520 ellist_get_mindl(ellist_t *head, u_int64_t cur_time)
1521 {
1522 struct hfsc_class *p, *cl = NULL;
1523
1524 TAILQ_FOREACH(p, head, cl_ellist) {
1525 if (p->cl_e > cur_time)
1526 break;
1527 if (cl == NULL || p->cl_d < cl->cl_d)
1528 cl = p;
1529 }
1530 return (cl);
1531 }
1532
1533 /*
1534 * active children list holds backlogged child classes being sorted
1535 * by their virtual time.
1536 * each intermediate class has one active children list.
1537 */
1538
1539 static void
1540 actlist_insert(struct hfsc_class *cl)
1541 {
1542 struct hfsc_class *p;
1543
1544 /* check the last entry first */
1545 if ((p = TAILQ_LAST(&cl->cl_parent->cl_actc, _active)) == NULL ||
1546 p->cl_vt <= cl->cl_vt) {
1547 TAILQ_INSERT_TAIL(&cl->cl_parent->cl_actc, cl, cl_actlist);
1548 return;
1549 }
1550
1551 TAILQ_FOREACH(p, &cl->cl_parent->cl_actc, cl_actlist) {
1552 if (cl->cl_vt < p->cl_vt) {
1553 TAILQ_INSERT_BEFORE(p, cl, cl_actlist);
1554 return;
1555 }
1556 }
1557 VERIFY(0); /* should not reach here */
1558 }
1559
1560 static void
1561 actlist_remove(struct hfsc_class *cl)
1562 {
1563 TAILQ_REMOVE(&cl->cl_parent->cl_actc, cl, cl_actlist);
1564 }
1565
1566 static void
1567 actlist_update(struct hfsc_class *cl)
1568 {
1569 struct hfsc_class *p, *last;
1570
1571 /*
1572 * the virtual time of a class increases monotonically during its
1573 * backlogged period.
1574 * if the next entry has a larger virtual time, nothing to do.
1575 */
1576 p = TAILQ_NEXT(cl, cl_actlist);
1577 if (p == NULL || cl->cl_vt < p->cl_vt)
1578 return;
1579
1580 /* check the last entry */
1581 last = TAILQ_LAST(&cl->cl_parent->cl_actc, _active);
1582 VERIFY(last != NULL);
1583 if (last->cl_vt <= cl->cl_vt) {
1584 TAILQ_REMOVE(&cl->cl_parent->cl_actc, cl, cl_actlist);
1585 TAILQ_INSERT_TAIL(&cl->cl_parent->cl_actc, cl, cl_actlist);
1586 return;
1587 }
1588
1589 /*
1590 * the new position must be between the next entry
1591 * and the last entry
1592 */
1593 while ((p = TAILQ_NEXT(p, cl_actlist)) != NULL) {
1594 if (cl->cl_vt < p->cl_vt) {
1595 TAILQ_REMOVE(&cl->cl_parent->cl_actc, cl, cl_actlist);
1596 TAILQ_INSERT_BEFORE(p, cl, cl_actlist);
1597 return;
1598 }
1599 }
1600 VERIFY(0); /* should not reach here */
1601 }
1602
1603 static struct hfsc_class *
1604 actlist_firstfit(struct hfsc_class *cl, u_int64_t cur_time)
1605 {
1606 struct hfsc_class *p;
1607
1608 TAILQ_FOREACH(p, &cl->cl_actc, cl_actlist) {
1609 if (p->cl_f <= cur_time)
1610 return (p);
1611 }
1612 return (NULL);
1613 }
1614
1615 /*
1616 * service curve support functions
1617 *
1618 * external service curve parameters
1619 * m: bits/sec
1620 * d: msec
1621 * internal service curve parameters
1622 * sm: (bytes/tsc_interval) << SM_SHIFT
1623 * ism: (tsc_count/byte) << ISM_SHIFT
1624 * dx: tsc_count
1625 *
1626 * SM_SHIFT and ISM_SHIFT are scaled in order to keep effective digits.
1627 * we should be able to handle 100K-1Gbps linkspeed with 200Hz-1GHz CPU
1628 * speed. SM_SHIFT and ISM_SHIFT are selected to have at least 3 effective
1629 * digits in decimal using the following table.
1630 *
1631 * bits/sec 100Kbps 1Mbps 10Mbps 100Mbps 1Gbps
1632 * ----------+-------------------------------------------------------
1633 * bytes/nsec 12.5e-6 125e-6 1250e-6 12500e-6 125000e-6
1634 * sm(500MHz) 25.0e-6 250e-6 2500e-6 25000e-6 250000e-6
1635 * sm(200MHz) 62.5e-6 625e-6 6250e-6 62500e-6 625000e-6
1636 *
1637 * nsec/byte 80000 8000 800 80 8
1638 * ism(500MHz) 40000 4000 400 40 4
1639 * ism(200MHz) 16000 1600 160 16 1.6
1640 */
1641 #define SM_SHIFT 24
1642 #define ISM_SHIFT 10
1643
1644 #define SM_MASK ((1LL << SM_SHIFT) - 1)
1645 #define ISM_MASK ((1LL << ISM_SHIFT) - 1)
1646
1647 static inline u_int64_t
1648 seg_x2y(u_int64_t x, u_int64_t sm)
1649 {
1650 u_int64_t y;
1651
1652 /*
1653 * compute
1654 * y = x * sm >> SM_SHIFT
1655 * but divide it for the upper and lower bits to avoid overflow
1656 */
1657 y = (x >> SM_SHIFT) * sm + (((x & SM_MASK) * sm) >> SM_SHIFT);
1658 return (y);
1659 }
1660
1661 static inline u_int64_t
1662 seg_y2x(u_int64_t y, u_int64_t ism)
1663 {
1664 u_int64_t x;
1665
1666 if (y == 0)
1667 x = 0;
1668 else if (ism == HT_INFINITY)
1669 x = HT_INFINITY;
1670 else {
1671 x = (y >> ISM_SHIFT) * ism
1672 + (((y & ISM_MASK) * ism) >> ISM_SHIFT);
1673 }
1674 return (x);
1675 }
1676
1677 static inline u_int64_t
1678 m2sm(u_int64_t m)
1679 {
1680 u_int64_t sm;
1681
1682 sm = (m << SM_SHIFT) / 8 / machclk_freq;
1683 return (sm);
1684 }
1685
1686 static inline u_int64_t
1687 m2ism(u_int64_t m)
1688 {
1689 u_int64_t ism;
1690
1691 if (m == 0)
1692 ism = HT_INFINITY;
1693 else
1694 ism = ((u_int64_t)machclk_freq << ISM_SHIFT) * 8 / m;
1695 return (ism);
1696 }
1697
1698 static inline u_int64_t
1699 d2dx(u_int64_t d)
1700 {
1701 u_int64_t dx;
1702
1703 dx = (d * machclk_freq) / 1000;
1704 return (dx);
1705 }
1706
1707 static u_int64_t
1708 sm2m(u_int64_t sm)
1709 {
1710 u_int64_t m;
1711
1712 m = (sm * 8 * machclk_freq) >> SM_SHIFT;
1713 return (m);
1714 }
1715
1716 static u_int64_t
1717 dx2d(u_int64_t dx)
1718 {
1719 u_int64_t d;
1720
1721 d = dx * 1000 / machclk_freq;
1722 return (d);
1723 }
1724
1725 static boolean_t
1726 sc2isc(struct hfsc_class *cl, struct service_curve *sc, struct internal_sc *isc,
1727 u_int64_t eff_rate)
1728 {
1729 struct hfsc_if *hif = cl->cl_hif;
1730 struct internal_sc oisc = *isc;
1731 u_int64_t m1, m2;
1732
1733 if (eff_rate == 0 && (sc->fl & (HFSCF_M1_PCT | HFSCF_M2_PCT))) {
1734 /*
1735 * If service curve is configured with percentage and the
1736 * effective uplink rate is not known, assume this is a
1737 * transient case, and that the rate will be updated in
1738 * the near future via CLASSQ_EV_LINK_SPEED. Pick a
1739 * reasonable number for now, e.g. 10 Mbps.
1740 */
1741 eff_rate = (10 * 1000 * 1000);
1742
1743 log(LOG_WARNING, "%s: %s qid=%d slot=%d eff_rate unknown; "
1744 "using temporary rate %llu bps\n", if_name(HFSCIF_IFP(hif)),
1745 hfsc_style(hif), cl->cl_handle, cl->cl_id, eff_rate);
1746 }
1747
1748 m1 = sc->m1;
1749 if (sc->fl & HFSCF_M1_PCT) {
1750 VERIFY(m1 > 0 && m1 <= 100);
1751 m1 = (eff_rate * m1) / 100;
1752 }
1753
1754 m2 = sc->m2;
1755 if (sc->fl & HFSCF_M2_PCT) {
1756 VERIFY(m2 > 0 && m2 <= 100);
1757 m2 = (eff_rate * m2) / 100;
1758 }
1759
1760 isc->sm1 = m2sm(m1);
1761 isc->ism1 = m2ism(m1);
1762 isc->dx = d2dx(sc->d);
1763 isc->dy = seg_x2y(isc->dx, isc->sm1);
1764 isc->sm2 = m2sm(m2);
1765 isc->ism2 = m2ism(m2);
1766
1767 /* return non-zero if there's any change */
1768 return (bcmp(&oisc, isc, sizeof (*isc)));
1769 }
1770
1771 /*
1772 * initialize the runtime service curve with the given internal
1773 * service curve starting at (x, y).
1774 */
1775 static void
1776 rtsc_init(struct runtime_sc *rtsc, struct internal_sc *isc, u_int64_t x,
1777 u_int64_t y)
1778 {
1779 rtsc->x = x;
1780 rtsc->y = y;
1781 rtsc->sm1 = isc->sm1;
1782 rtsc->ism1 = isc->ism1;
1783 rtsc->dx = isc->dx;
1784 rtsc->dy = isc->dy;
1785 rtsc->sm2 = isc->sm2;
1786 rtsc->ism2 = isc->ism2;
1787 }
1788
1789 /*
1790 * calculate the y-projection of the runtime service curve by the
1791 * given x-projection value
1792 */
1793 static u_int64_t
1794 rtsc_y2x(struct runtime_sc *rtsc, u_int64_t y)
1795 {
1796 u_int64_t x;
1797
1798 if (y < rtsc->y)
1799 x = rtsc->x;
1800 else if (y <= rtsc->y + rtsc->dy) {
1801 /* x belongs to the 1st segment */
1802 if (rtsc->dy == 0)
1803 x = rtsc->x + rtsc->dx;
1804 else
1805 x = rtsc->x + seg_y2x(y - rtsc->y, rtsc->ism1);
1806 } else {
1807 /* x belongs to the 2nd segment */
1808 x = rtsc->x + rtsc->dx
1809 + seg_y2x(y - rtsc->y - rtsc->dy, rtsc->ism2);
1810 }
1811 return (x);
1812 }
1813
1814 static u_int64_t
1815 rtsc_x2y(struct runtime_sc *rtsc, u_int64_t x)
1816 {
1817 u_int64_t y;
1818
1819 if (x <= rtsc->x)
1820 y = rtsc->y;
1821 else if (x <= rtsc->x + rtsc->dx)
1822 /* y belongs to the 1st segment */
1823 y = rtsc->y + seg_x2y(x - rtsc->x, rtsc->sm1);
1824 else
1825 /* y belongs to the 2nd segment */
1826 y = rtsc->y + rtsc->dy
1827 + seg_x2y(x - rtsc->x - rtsc->dx, rtsc->sm2);
1828 return (y);
1829 }
1830
1831 /*
1832 * update the runtime service curve by taking the minimum of the current
1833 * runtime service curve and the service curve starting at (x, y).
1834 */
1835 static void
1836 rtsc_min(struct runtime_sc *rtsc, struct internal_sc *isc, u_int64_t x,
1837 u_int64_t y)
1838 {
1839 u_int64_t y1, y2, dx, dy;
1840
1841 if (isc->sm1 <= isc->sm2) {
1842 /* service curve is convex */
1843 y1 = rtsc_x2y(rtsc, x);
1844 if (y1 < y)
1845 /* the current rtsc is smaller */
1846 return;
1847 rtsc->x = x;
1848 rtsc->y = y;
1849 return;
1850 }
1851
1852 /*
1853 * service curve is concave
1854 * compute the two y values of the current rtsc
1855 * y1: at x
1856 * y2: at (x + dx)
1857 */
1858 y1 = rtsc_x2y(rtsc, x);
1859 if (y1 <= y) {
1860 /* rtsc is below isc, no change to rtsc */
1861 return;
1862 }
1863
1864 y2 = rtsc_x2y(rtsc, x + isc->dx);
1865 if (y2 >= y + isc->dy) {
1866 /* rtsc is above isc, replace rtsc by isc */
1867 rtsc->x = x;
1868 rtsc->y = y;
1869 rtsc->dx = isc->dx;
1870 rtsc->dy = isc->dy;
1871 return;
1872 }
1873
1874 /*
1875 * the two curves intersect
1876 * compute the offsets (dx, dy) using the reverse
1877 * function of seg_x2y()
1878 * seg_x2y(dx, sm1) == seg_x2y(dx, sm2) + (y1 - y)
1879 */
1880 dx = ((y1 - y) << SM_SHIFT) / (isc->sm1 - isc->sm2);
1881 /*
1882 * check if (x, y1) belongs to the 1st segment of rtsc.
1883 * if so, add the offset.
1884 */
1885 if (rtsc->x + rtsc->dx > x)
1886 dx += rtsc->x + rtsc->dx - x;
1887 dy = seg_x2y(dx, isc->sm1);
1888
1889 rtsc->x = x;
1890 rtsc->y = y;
1891 rtsc->dx = dx;
1892 rtsc->dy = dy;
1893 }
1894
1895 int
1896 hfsc_get_class_stats(struct hfsc_if *hif, u_int32_t qid,
1897 struct hfsc_classstats *sp)
1898 {
1899 struct hfsc_class *cl;
1900
1901 IFCQ_LOCK_ASSERT_HELD(hif->hif_ifq);
1902
1903 if ((cl = hfsc_clh_to_clp(hif, qid)) == NULL)
1904 return (EINVAL);
1905
1906 sp->class_id = cl->cl_id;
1907 sp->class_handle = cl->cl_handle;
1908
1909 if (cl->cl_flags & HFCF_RSC) {
1910 sp->rsc.m1 = sm2m(cl->cl_rsc.sm1);
1911 sp->rsc.d = dx2d(cl->cl_rsc.dx);
1912 sp->rsc.m2 = sm2m(cl->cl_rsc.sm2);
1913 } else {
1914 sp->rsc.m1 = 0;
1915 sp->rsc.d = 0;
1916 sp->rsc.m2 = 0;
1917 }
1918 if (cl->cl_flags & HFCF_FSC) {
1919 sp->fsc.m1 = sm2m(cl->cl_fsc.sm1);
1920 sp->fsc.d = dx2d(cl->cl_fsc.dx);
1921 sp->fsc.m2 = sm2m(cl->cl_fsc.sm2);
1922 } else {
1923 sp->fsc.m1 = 0;
1924 sp->fsc.d = 0;
1925 sp->fsc.m2 = 0;
1926 }
1927 if (cl->cl_flags & HFCF_USC) {
1928 sp->usc.m1 = sm2m(cl->cl_usc.sm1);
1929 sp->usc.d = dx2d(cl->cl_usc.dx);
1930 sp->usc.m2 = sm2m(cl->cl_usc.sm2);
1931 } else {
1932 sp->usc.m1 = 0;
1933 sp->usc.d = 0;
1934 sp->usc.m2 = 0;
1935 }
1936
1937 sp->total = cl->cl_total;
1938 sp->cumul = cl->cl_cumul;
1939
1940 sp->d = cl->cl_d;
1941 sp->e = cl->cl_e;
1942 sp->vt = cl->cl_vt;
1943 sp->f = cl->cl_f;
1944
1945 sp->initvt = cl->cl_initvt;
1946 sp->vtperiod = cl->cl_vtperiod;
1947 sp->parentperiod = cl->cl_parentperiod;
1948 sp->nactive = cl->cl_nactive;
1949 sp->vtoff = cl->cl_vtoff;
1950 sp->cvtmax = cl->cl_cvtmax;
1951 sp->myf = cl->cl_myf;
1952 sp->cfmin = cl->cl_cfmin;
1953 sp->cvtmin = cl->cl_cvtmin;
1954 sp->myfadj = cl->cl_myfadj;
1955 sp->vtadj = cl->cl_vtadj;
1956
1957 sp->cur_time = read_machclk();
1958 sp->machclk_freq = machclk_freq;
1959
1960 sp->qlength = qlen(&cl->cl_q);
1961 sp->qlimit = qlimit(&cl->cl_q);
1962 sp->xmit_cnt = cl->cl_stats.xmit_cnt;
1963 sp->drop_cnt = cl->cl_stats.drop_cnt;
1964 sp->period = cl->cl_stats.period;
1965
1966 sp->qtype = qtype(&cl->cl_q);
1967 sp->qstate = qstate(&cl->cl_q);
1968 #if CLASSQ_RED
1969 if (q_is_red(&cl->cl_q))
1970 red_getstats(cl->cl_red, &sp->red[0]);
1971 #endif /* CLASSQ_RED */
1972 #if CLASSQ_RIO
1973 if (q_is_rio(&cl->cl_q))
1974 rio_getstats(cl->cl_rio, &sp->red[0]);
1975 #endif /* CLASSQ_RIO */
1976 #if CLASSQ_BLUE
1977 if (q_is_blue(&cl->cl_q))
1978 blue_getstats(cl->cl_blue, &sp->blue);
1979 #endif /* CLASSQ_BLUE */
1980 if (q_is_sfb(&cl->cl_q) && cl->cl_sfb != NULL)
1981 sfb_getstats(cl->cl_sfb, &sp->sfb);
1982
1983 return (0);
1984 }
1985
1986 /* convert a class handle to the corresponding class pointer */
1987 static struct hfsc_class *
1988 hfsc_clh_to_clp(struct hfsc_if *hif, u_int32_t chandle)
1989 {
1990 u_int32_t i;
1991 struct hfsc_class *cl;
1992
1993 IFCQ_LOCK_ASSERT_HELD(hif->hif_ifq);
1994
1995 /*
1996 * first, try optimistically the slot matching the lower bits of
1997 * the handle. if it fails, do the linear table search.
1998 */
1999 i = chandle % hif->hif_maxclasses;
2000 if ((cl = hif->hif_class_tbl[i]) != NULL && cl->cl_handle == chandle)
2001 return (cl);
2002 for (i = 0; i < hif->hif_maxclasses; i++)
2003 if ((cl = hif->hif_class_tbl[i]) != NULL &&
2004 cl->cl_handle == chandle)
2005 return (cl);
2006 return (NULL);
2007 }
2008
2009 static const char *
2010 hfsc_style(struct hfsc_if *hif)
2011 {
2012 return ((hif->hif_flags & HFSCIFF_ALTQ) ? "ALTQ_HFSC" : "HFSC");
2013 }
2014
2015 int
2016 hfsc_setup_ifclassq(struct ifclassq *ifq, u_int32_t flags)
2017 {
2018 #pragma unused(ifq, flags)
2019 return (ENXIO); /* not yet */
2020 }
2021
2022 int
2023 hfsc_teardown_ifclassq(struct ifclassq *ifq)
2024 {
2025 struct hfsc_if *hif = ifq->ifcq_disc;
2026 int i;
2027
2028 IFCQ_LOCK_ASSERT_HELD(ifq);
2029 VERIFY(hif != NULL && ifq->ifcq_type == PKTSCHEDT_HFSC);
2030
2031 (void) hfsc_destroy_locked(hif);
2032
2033 ifq->ifcq_disc = NULL;
2034 for (i = 0; i < IFCQ_SC_MAX; i++) {
2035 ifq->ifcq_disc_slots[i].qid = 0;
2036 ifq->ifcq_disc_slots[i].cl = NULL;
2037 }
2038
2039 return (ifclassq_detach(ifq));
2040 }
2041
2042 int
2043 hfsc_getqstats_ifclassq(struct ifclassq *ifq, u_int32_t slot,
2044 struct if_ifclassq_stats *ifqs)
2045 {
2046 struct hfsc_if *hif = ifq->ifcq_disc;
2047
2048 IFCQ_LOCK_ASSERT_HELD(ifq);
2049 VERIFY(ifq->ifcq_type == PKTSCHEDT_HFSC);
2050
2051 if (slot >= IFCQ_SC_MAX)
2052 return (EINVAL);
2053
2054 return (hfsc_get_class_stats(hif, ifq->ifcq_disc_slots[slot].qid,
2055 &ifqs->ifqs_hfsc_stats));
2056 }
2057 #endif /* PKTSCHED_HFSC */
mirror of XNU