1 /*- 2 * Copyright (c) 1997-1999 Carnegie Mellon University. All Rights Reserved. 3 * 4 * Permission to use, copy, modify, and distribute this software and 5 * its documentation is hereby granted (including for commercial or 6 * for-profit use), provided that both the copyright notice and this 7 * permission notice appear in all copies of the software, derivative 8 * works, or modified versions, and any portions thereof. 9 * 10 * THIS SOFTWARE IS EXPERIMENTAL AND IS KNOWN TO HAVE BUGS, SOME OF 11 * WHICH MAY HAVE SERIOUS CONSEQUENCES. CARNEGIE MELLON PROVIDES THIS 12 * SOFTWARE IN ITS ``AS IS'' CONDITION, AND ANY EXPRESS OR IMPLIED 13 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 14 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 15 * DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY BE LIABLE 16 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 17 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT 18 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 19 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 20 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 21 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE 22 * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH 23 * DAMAGE. 24 * 25 * Carnegie Mellon encourages (but does not require) users of this 26 * software to return any improvements or extensions that they make, 27 * and to grant Carnegie Mellon the rights to redistribute these 28 * changes without encumbrance. 29 * 30 * $KAME: altq_hfsc.c,v 1.24 2003/12/05 05:40:46 kjc Exp $ 31 * $FreeBSD$ 32 */ 33 /* 34 * H-FSC is described in Proceedings of SIGCOMM'97, 35 * "A Hierarchical Fair Service Curve Algorithm for Link-Sharing, 36 * Real-Time and Priority Service" 37 * by Ion Stoica, Hui Zhang, and T. S. Eugene Ng. 38 * 39 * Oleg Cherevko <olwi@aq.ml.com.ua> added the upperlimit for link-sharing. 40 * when a class has an upperlimit, the fit-time is computed from the 41 * upperlimit service curve. the link-sharing scheduler does not schedule 42 * a class whose fit-time exceeds the current time. 43 */ 44 45 #include "opt_altq.h" 46 #include "opt_inet.h" 47 #include "opt_inet6.h" 48 49 #ifdef ALTQ_HFSC /* hfsc is enabled by ALTQ_HFSC option in opt_altq.h */ 50 51 #include <sys/param.h> 52 #include <sys/malloc.h> 53 #include <sys/mbuf.h> 54 #include <sys/socket.h> 55 #include <sys/systm.h> 56 #include <sys/errno.h> 57 #include <sys/queue.h> 58 #if 1 /* ALTQ3_COMPAT */ 59 #include <sys/sockio.h> 60 #include <sys/proc.h> 61 #include <sys/kernel.h> 62 #endif /* ALTQ3_COMPAT */ 63 64 #include <net/if.h> 65 #include <net/if_var.h> 66 #include <netinet/in.h> 67 68 #include <netpfil/pf/pf.h> 69 #include <netpfil/pf/pf_altq.h> 70 #include <netpfil/pf/pf_mtag.h> 71 #include <net/altq/altq.h> 72 #include <net/altq/altq_hfsc.h> 73 74 /* 75 * function prototypes 76 */ 77 static int hfsc_clear_interface(struct hfsc_if *); 78 static int hfsc_request(struct ifaltq *, int, void *); 79 static void hfsc_purge(struct hfsc_if *); 80 static struct hfsc_class *hfsc_class_create(struct hfsc_if *, 81 struct service_curve *, struct service_curve *, struct service_curve *, 82 struct hfsc_class *, int, int, int); 83 static int hfsc_class_destroy(struct hfsc_class *); 84 static struct hfsc_class *hfsc_nextclass(struct hfsc_class *); 85 static int hfsc_enqueue(struct ifaltq *, struct mbuf *, 86 struct altq_pktattr *); 87 static struct mbuf *hfsc_dequeue(struct ifaltq *, int); 88 89 static int hfsc_addq(struct hfsc_class *, struct mbuf *); 90 static struct mbuf *hfsc_getq(struct hfsc_class *); 91 static struct mbuf *hfsc_pollq(struct hfsc_class *); 92 static void hfsc_purgeq(struct hfsc_class *); 93 94 static void update_cfmin(struct hfsc_class *); 95 static void set_active(struct hfsc_class *, int); 96 static void set_passive(struct hfsc_class *); 97 98 static void init_ed(struct hfsc_class *, int); 99 static void update_ed(struct hfsc_class *, int); 100 static void update_d(struct hfsc_class *, int); 101 static void init_vf(struct hfsc_class *, int); 102 static void update_vf(struct hfsc_class *, int, u_int64_t); 103 static void ellist_insert(struct hfsc_class *); 104 static void ellist_remove(struct hfsc_class *); 105 static void ellist_update(struct hfsc_class *); 106 struct hfsc_class *hfsc_get_mindl(struct hfsc_if *, u_int64_t); 107 static void actlist_insert(struct hfsc_class *); 108 static void actlist_remove(struct hfsc_class *); 109 static void actlist_update(struct hfsc_class *); 110 111 static struct hfsc_class *actlist_firstfit(struct hfsc_class *, 112 u_int64_t); 113 114 static __inline u_int64_t seg_x2y(u_int64_t, u_int64_t); 115 static __inline u_int64_t seg_y2x(u_int64_t, u_int64_t); 116 static __inline u_int64_t m2sm(u_int64_t); 117 static __inline u_int64_t m2ism(u_int64_t); 118 static __inline u_int64_t d2dx(u_int); 119 static u_int64_t sm2m(u_int64_t); 120 static u_int dx2d(u_int64_t); 121 122 static void sc2isc(struct service_curve *, struct internal_sc *); 123 static void rtsc_init(struct runtime_sc *, struct internal_sc *, 124 u_int64_t, u_int64_t); 125 static u_int64_t rtsc_y2x(struct runtime_sc *, u_int64_t); 126 static u_int64_t rtsc_x2y(struct runtime_sc *, u_int64_t); 127 static void rtsc_min(struct runtime_sc *, struct internal_sc *, 128 u_int64_t, u_int64_t); 129 130 static void get_class_stats_v0(struct hfsc_classstats_v0 *, 131 struct hfsc_class *); 132 static void get_class_stats_v1(struct hfsc_classstats_v1 *, 133 struct hfsc_class *); 134 static struct hfsc_class *clh_to_clp(struct hfsc_if *, u_int32_t); 135 136 137 138 /* 139 * macros 140 */ 141 #define is_a_parent_class(cl) ((cl)->cl_children != NULL) 142 143 #define HT_INFINITY 0xffffffffffffffffULL /* infinite time value */ 144 145 146 int 147 hfsc_pfattach(struct pf_altq *a) 148 { 149 struct ifnet *ifp; 150 int s, error; 151 152 if ((ifp = ifunit(a->ifname)) == NULL || a->altq_disc == NULL) 153 return (EINVAL); 154 s = splnet(); 155 error = altq_attach(&ifp->if_snd, ALTQT_HFSC, a->altq_disc, 156 hfsc_enqueue, hfsc_dequeue, hfsc_request, NULL, NULL); 157 splx(s); 158 return (error); 159 } 160 161 int 162 hfsc_add_altq(struct pf_altq *a) 163 { 164 struct hfsc_if *hif; 165 struct ifnet *ifp; 166 167 if ((ifp = ifunit(a->ifname)) == NULL) 168 return (EINVAL); 169 if (!ALTQ_IS_READY(&ifp->if_snd)) 170 return (ENODEV); 171 172 hif = malloc(sizeof(struct hfsc_if), M_DEVBUF, M_NOWAIT | M_ZERO); 173 if (hif == NULL) 174 return (ENOMEM); 175 176 TAILQ_INIT(&hif->hif_eligible); 177 hif->hif_ifq = &ifp->if_snd; 178 179 /* keep the state in pf_altq */ 180 a->altq_disc = hif; 181 182 return (0); 183 } 184 185 int 186 hfsc_remove_altq(struct pf_altq *a) 187 { 188 struct hfsc_if *hif; 189 190 if ((hif = a->altq_disc) == NULL) 191 return (EINVAL); 192 a->altq_disc = NULL; 193 194 (void)hfsc_clear_interface(hif); 195 (void)hfsc_class_destroy(hif->hif_rootclass); 196 197 free(hif, M_DEVBUF); 198 199 return (0); 200 } 201 202 int 203 hfsc_add_queue(struct pf_altq *a) 204 { 205 struct hfsc_if *hif; 206 struct hfsc_class *cl, *parent; 207 struct hfsc_opts_v1 *opts; 208 struct service_curve rtsc, lssc, ulsc; 209 210 if ((hif = a->altq_disc) == NULL) 211 return (EINVAL); 212 213 opts = &a->pq_u.hfsc_opts; 214 215 if (a->parent_qid == HFSC_NULLCLASS_HANDLE && 216 hif->hif_rootclass == NULL) 217 parent = NULL; 218 else if ((parent = clh_to_clp(hif, a->parent_qid)) == NULL) 219 return (EINVAL); 220 221 if (a->qid == 0) 222 return (EINVAL); 223 224 if (clh_to_clp(hif, a->qid) != NULL) 225 return (EBUSY); 226 227 rtsc.m1 = opts->rtsc_m1; 228 rtsc.d = opts->rtsc_d; 229 rtsc.m2 = opts->rtsc_m2; 230 lssc.m1 = opts->lssc_m1; 231 lssc.d = opts->lssc_d; 232 lssc.m2 = opts->lssc_m2; 233 ulsc.m1 = opts->ulsc_m1; 234 ulsc.d = opts->ulsc_d; 235 ulsc.m2 = opts->ulsc_m2; 236 237 cl = hfsc_class_create(hif, &rtsc, &lssc, &ulsc, 238 parent, a->qlimit, opts->flags, a->qid); 239 if (cl == NULL) 240 return (ENOMEM); 241 242 return (0); 243 } 244 245 int 246 hfsc_remove_queue(struct pf_altq *a) 247 { 248 struct hfsc_if *hif; 249 struct hfsc_class *cl; 250 251 if ((hif = a->altq_disc) == NULL) 252 return (EINVAL); 253 254 if ((cl = clh_to_clp(hif, a->qid)) == NULL) 255 return (EINVAL); 256 257 return (hfsc_class_destroy(cl)); 258 } 259 260 int 261 hfsc_getqstats(struct pf_altq *a, void *ubuf, int *nbytes, int version) 262 { 263 struct hfsc_if *hif; 264 struct hfsc_class *cl; 265 union { 266 struct hfsc_classstats_v0 v0; 267 struct hfsc_classstats_v1 v1; 268 } stats; 269 size_t stats_size; 270 int error = 0; 271 272 if ((hif = altq_lookup(a->ifname, ALTQT_HFSC)) == NULL) 273 return (EBADF); 274 275 if ((cl = clh_to_clp(hif, a->qid)) == NULL) 276 return (EINVAL); 277 278 if (version > HFSC_STATS_VERSION) 279 return (EINVAL); 280 281 memset(&stats, 0, sizeof(stats)); 282 switch (version) { 283 case 0: 284 get_class_stats_v0(&stats.v0, cl); 285 stats_size = sizeof(struct hfsc_classstats_v0); 286 break; 287 case 1: 288 get_class_stats_v1(&stats.v1, cl); 289 stats_size = sizeof(struct hfsc_classstats_v1); 290 break; 291 } 292 293 if (*nbytes < stats_size) 294 return (EINVAL); 295 296 if ((error = copyout((caddr_t)&stats, ubuf, stats_size)) != 0) 297 return (error); 298 *nbytes = stats_size; 299 return (0); 300 } 301 302 /* 303 * bring the interface back to the initial state by discarding 304 * all the filters and classes except the root class. 305 */ 306 static int 307 hfsc_clear_interface(struct hfsc_if *hif) 308 { 309 struct hfsc_class *cl; 310 311 312 /* clear out the classes */ 313 while (hif->hif_rootclass != NULL && 314 (cl = hif->hif_rootclass->cl_children) != NULL) { 315 /* 316 * remove the first leaf class found in the hierarchy 317 * then start over 318 */ 319 for (; cl != NULL; cl = hfsc_nextclass(cl)) { 320 if (!is_a_parent_class(cl)) { 321 (void)hfsc_class_destroy(cl); 322 break; 323 } 324 } 325 } 326 327 return (0); 328 } 329 330 static int 331 hfsc_request(struct ifaltq *ifq, int req, void *arg) 332 { 333 struct hfsc_if *hif = (struct hfsc_if *)ifq->altq_disc; 334 335 IFQ_LOCK_ASSERT(ifq); 336 337 switch (req) { 338 case ALTRQ_PURGE: 339 hfsc_purge(hif); 340 break; 341 } 342 return (0); 343 } 344 345 /* discard all the queued packets on the interface */ 346 static void 347 hfsc_purge(struct hfsc_if *hif) 348 { 349 struct hfsc_class *cl; 350 351 for (cl = hif->hif_rootclass; cl != NULL; cl = hfsc_nextclass(cl)) 352 if (!qempty(cl->cl_q)) 353 hfsc_purgeq(cl); 354 if (ALTQ_IS_ENABLED(hif->hif_ifq)) 355 hif->hif_ifq->ifq_len = 0; 356 } 357 358 struct hfsc_class * 359 hfsc_class_create(struct hfsc_if *hif, struct service_curve *rsc, 360 struct service_curve *fsc, struct service_curve *usc, 361 struct hfsc_class *parent, int qlimit, int flags, int qid) 362 { 363 struct hfsc_class *cl, *p; 364 int i, s; 365 366 if (hif->hif_classes >= HFSC_MAX_CLASSES) 367 return (NULL); 368 369 #ifndef ALTQ_RED 370 if (flags & HFCF_RED) { 371 #ifdef ALTQ_DEBUG 372 printf("hfsc_class_create: RED not configured for HFSC!\n"); 373 #endif 374 return (NULL); 375 } 376 #endif 377 #ifndef ALTQ_CODEL 378 if (flags & HFCF_CODEL) { 379 #ifdef ALTQ_DEBUG 380 printf("hfsc_class_create: CODEL not configured for HFSC!\n"); 381 #endif 382 return (NULL); 383 } 384 #endif 385 386 cl = malloc(sizeof(struct hfsc_class), M_DEVBUF, M_NOWAIT | M_ZERO); 387 if (cl == NULL) 388 return (NULL); 389 390 cl->cl_q = malloc(sizeof(class_queue_t), M_DEVBUF, M_NOWAIT | M_ZERO); 391 if (cl->cl_q == NULL) 392 goto err_ret; 393 394 TAILQ_INIT(&cl->cl_actc); 395 396 if (qlimit == 0) 397 qlimit = 50; /* use default */ 398 qlimit(cl->cl_q) = qlimit; 399 qtype(cl->cl_q) = Q_DROPTAIL; 400 qlen(cl->cl_q) = 0; 401 qsize(cl->cl_q) = 0; 402 cl->cl_flags = flags; 403 #ifdef ALTQ_RED 404 if (flags & (HFCF_RED|HFCF_RIO)) { 405 int red_flags, red_pkttime; 406 u_int m2; 407 408 m2 = 0; 409 if (rsc != NULL && rsc->m2 > m2) 410 m2 = rsc->m2; 411 if (fsc != NULL && fsc->m2 > m2) 412 m2 = fsc->m2; 413 if (usc != NULL && usc->m2 > m2) 414 m2 = usc->m2; 415 416 red_flags = 0; 417 if (flags & HFCF_ECN) 418 red_flags |= REDF_ECN; 419 #ifdef ALTQ_RIO 420 if (flags & HFCF_CLEARDSCP) 421 red_flags |= RIOF_CLEARDSCP; 422 #endif 423 if (m2 < 8) 424 red_pkttime = 1000 * 1000 * 1000; /* 1 sec */ 425 else 426 red_pkttime = (int64_t)hif->hif_ifq->altq_ifp->if_mtu 427 * 1000 * 1000 * 1000 / (m2 / 8); 428 if (flags & HFCF_RED) { 429 cl->cl_red = red_alloc(0, 0, 430 qlimit(cl->cl_q) * 10/100, 431 qlimit(cl->cl_q) * 30/100, 432 red_flags, red_pkttime); 433 if (cl->cl_red != NULL) 434 qtype(cl->cl_q) = Q_RED; 435 } 436 #ifdef ALTQ_RIO 437 else { 438 cl->cl_red = (red_t *)rio_alloc(0, NULL, 439 red_flags, red_pkttime); 440 if (cl->cl_red != NULL) 441 qtype(cl->cl_q) = Q_RIO; 442 } 443 #endif 444 } 445 #endif /* ALTQ_RED */ 446 #ifdef ALTQ_CODEL 447 if (flags & HFCF_CODEL) { 448 cl->cl_codel = codel_alloc(5, 100, 0); 449 if (cl->cl_codel != NULL) 450 qtype(cl->cl_q) = Q_CODEL; 451 } 452 #endif 453 454 if (rsc != NULL && (rsc->m1 != 0 || rsc->m2 != 0)) { 455 cl->cl_rsc = malloc(sizeof(struct internal_sc), 456 M_DEVBUF, M_NOWAIT); 457 if (cl->cl_rsc == NULL) 458 goto err_ret; 459 sc2isc(rsc, cl->cl_rsc); 460 rtsc_init(&cl->cl_deadline, cl->cl_rsc, 0, 0); 461 rtsc_init(&cl->cl_eligible, cl->cl_rsc, 0, 0); 462 } 463 if (fsc != NULL && (fsc->m1 != 0 || fsc->m2 != 0)) { 464 cl->cl_fsc = malloc(sizeof(struct internal_sc), 465 M_DEVBUF, M_NOWAIT); 466 if (cl->cl_fsc == NULL) 467 goto err_ret; 468 sc2isc(fsc, cl->cl_fsc); 469 rtsc_init(&cl->cl_virtual, cl->cl_fsc, 0, 0); 470 } 471 if (usc != NULL && (usc->m1 != 0 || usc->m2 != 0)) { 472 cl->cl_usc = malloc(sizeof(struct internal_sc), 473 M_DEVBUF, M_NOWAIT); 474 if (cl->cl_usc == NULL) 475 goto err_ret; 476 sc2isc(usc, cl->cl_usc); 477 rtsc_init(&cl->cl_ulimit, cl->cl_usc, 0, 0); 478 } 479 480 cl->cl_id = hif->hif_classid++; 481 cl->cl_handle = qid; 482 cl->cl_hif = hif; 483 cl->cl_parent = parent; 484 485 s = splnet(); 486 IFQ_LOCK(hif->hif_ifq); 487 hif->hif_classes++; 488 489 /* 490 * find a free slot in the class table. if the slot matching 491 * the lower bits of qid is free, use this slot. otherwise, 492 * use the first free slot. 493 */ 494 i = qid % HFSC_MAX_CLASSES; 495 if (hif->hif_class_tbl[i] == NULL) 496 hif->hif_class_tbl[i] = cl; 497 else { 498 for (i = 0; i < HFSC_MAX_CLASSES; i++) 499 if (hif->hif_class_tbl[i] == NULL) { 500 hif->hif_class_tbl[i] = cl; 501 break; 502 } 503 if (i == HFSC_MAX_CLASSES) { 504 IFQ_UNLOCK(hif->hif_ifq); 505 splx(s); 506 goto err_ret; 507 } 508 } 509 510 if (flags & HFCF_DEFAULTCLASS) 511 hif->hif_defaultclass = cl; 512 513 if (parent == NULL) { 514 /* this is root class */ 515 hif->hif_rootclass = cl; 516 } else { 517 /* add this class to the children list of the parent */ 518 if ((p = parent->cl_children) == NULL) 519 parent->cl_children = cl; 520 else { 521 while (p->cl_siblings != NULL) 522 p = p->cl_siblings; 523 p->cl_siblings = cl; 524 } 525 } 526 IFQ_UNLOCK(hif->hif_ifq); 527 splx(s); 528 529 return (cl); 530 531 err_ret: 532 if (cl->cl_red != NULL) { 533 #ifdef ALTQ_RIO 534 if (q_is_rio(cl->cl_q)) 535 rio_destroy((rio_t *)cl->cl_red); 536 #endif 537 #ifdef ALTQ_RED 538 if (q_is_red(cl->cl_q)) 539 red_destroy(cl->cl_red); 540 #endif 541 #ifdef ALTQ_CODEL 542 if (q_is_codel(cl->cl_q)) 543 codel_destroy(cl->cl_codel); 544 #endif 545 } 546 if (cl->cl_fsc != NULL) 547 free(cl->cl_fsc, M_DEVBUF); 548 if (cl->cl_rsc != NULL) 549 free(cl->cl_rsc, M_DEVBUF); 550 if (cl->cl_usc != NULL) 551 free(cl->cl_usc, M_DEVBUF); 552 if (cl->cl_q != NULL) 553 free(cl->cl_q, M_DEVBUF); 554 free(cl, M_DEVBUF); 555 return (NULL); 556 } 557 558 static int 559 hfsc_class_destroy(struct hfsc_class *cl) 560 { 561 int i, s; 562 563 if (cl == NULL) 564 return (0); 565 566 if (is_a_parent_class(cl)) 567 return (EBUSY); 568 569 s = splnet(); 570 IFQ_LOCK(cl->cl_hif->hif_ifq); 571 572 573 if (!qempty(cl->cl_q)) 574 hfsc_purgeq(cl); 575 576 if (cl->cl_parent == NULL) { 577 /* this is root class */ 578 } else { 579 struct hfsc_class *p = cl->cl_parent->cl_children; 580 581 if (p == cl) 582 cl->cl_parent->cl_children = cl->cl_siblings; 583 else do { 584 if (p->cl_siblings == cl) { 585 p->cl_siblings = cl->cl_siblings; 586 break; 587 } 588 } while ((p = p->cl_siblings) != NULL); 589 ASSERT(p != NULL); 590 } 591 592 for (i = 0; i < HFSC_MAX_CLASSES; i++) 593 if (cl->cl_hif->hif_class_tbl[i] == cl) { 594 cl->cl_hif->hif_class_tbl[i] = NULL; 595 break; 596 } 597 598 cl->cl_hif->hif_classes--; 599 IFQ_UNLOCK(cl->cl_hif->hif_ifq); 600 splx(s); 601 602 if (cl->cl_red != NULL) { 603 #ifdef ALTQ_RIO 604 if (q_is_rio(cl->cl_q)) 605 rio_destroy((rio_t *)cl->cl_red); 606 #endif 607 #ifdef ALTQ_RED 608 if (q_is_red(cl->cl_q)) 609 red_destroy(cl->cl_red); 610 #endif 611 #ifdef ALTQ_CODEL 612 if (q_is_codel(cl->cl_q)) 613 codel_destroy(cl->cl_codel); 614 #endif 615 } 616 617 IFQ_LOCK(cl->cl_hif->hif_ifq); 618 if (cl == cl->cl_hif->hif_rootclass) 619 cl->cl_hif->hif_rootclass = NULL; 620 if (cl == cl->cl_hif->hif_defaultclass) 621 cl->cl_hif->hif_defaultclass = NULL; 622 IFQ_UNLOCK(cl->cl_hif->hif_ifq); 623 624 if (cl->cl_usc != NULL) 625 free(cl->cl_usc, M_DEVBUF); 626 if (cl->cl_fsc != NULL) 627 free(cl->cl_fsc, M_DEVBUF); 628 if (cl->cl_rsc != NULL) 629 free(cl->cl_rsc, M_DEVBUF); 630 free(cl->cl_q, M_DEVBUF); 631 free(cl, M_DEVBUF); 632 633 return (0); 634 } 635 636 /* 637 * hfsc_nextclass returns the next class in the tree. 638 * usage: 639 * for (cl = hif->hif_rootclass; cl != NULL; cl = hfsc_nextclass(cl)) 640 * do_something; 641 */ 642 static struct hfsc_class * 643 hfsc_nextclass(struct hfsc_class *cl) 644 { 645 if (cl->cl_children != NULL) 646 cl = cl->cl_children; 647 else if (cl->cl_siblings != NULL) 648 cl = cl->cl_siblings; 649 else { 650 while ((cl = cl->cl_parent) != NULL) 651 if (cl->cl_siblings) { 652 cl = cl->cl_siblings; 653 break; 654 } 655 } 656 657 return (cl); 658 } 659 660 /* 661 * hfsc_enqueue is an enqueue function to be registered to 662 * (*altq_enqueue) in struct ifaltq. 663 */ 664 static int 665 hfsc_enqueue(struct ifaltq *ifq, struct mbuf *m, struct altq_pktattr *pktattr) 666 { 667 struct hfsc_if *hif = (struct hfsc_if *)ifq->altq_disc; 668 struct hfsc_class *cl; 669 struct pf_mtag *t; 670 int len; 671 672 IFQ_LOCK_ASSERT(ifq); 673 674 /* grab class set by classifier */ 675 if ((m->m_flags & M_PKTHDR) == 0) { 676 /* should not happen */ 677 printf("altq: packet for %s does not have pkthdr\n", 678 ifq->altq_ifp->if_xname); 679 m_freem(m); 680 return (ENOBUFS); 681 } 682 cl = NULL; 683 if ((t = pf_find_mtag(m)) != NULL) 684 cl = clh_to_clp(hif, t->qid); 685 if (cl == NULL || is_a_parent_class(cl)) { 686 cl = hif->hif_defaultclass; 687 if (cl == NULL) { 688 m_freem(m); 689 return (ENOBUFS); 690 } 691 } 692 cl->cl_pktattr = NULL; 693 len = m_pktlen(m); 694 if (hfsc_addq(cl, m) != 0) { 695 /* drop occurred. mbuf was freed in hfsc_addq. */ 696 PKTCNTR_ADD(&cl->cl_stats.drop_cnt, len); 697 return (ENOBUFS); 698 } 699 IFQ_INC_LEN(ifq); 700 cl->cl_hif->hif_packets++; 701 702 /* successfully queued. */ 703 if (qlen(cl->cl_q) == 1) 704 set_active(cl, m_pktlen(m)); 705 706 return (0); 707 } 708 709 /* 710 * hfsc_dequeue is a dequeue function to be registered to 711 * (*altq_dequeue) in struct ifaltq. 712 * 713 * note: ALTDQ_POLL returns the next packet without removing the packet 714 * from the queue. ALTDQ_REMOVE is a normal dequeue operation. 715 * ALTDQ_REMOVE must return the same packet if called immediately 716 * after ALTDQ_POLL. 717 */ 718 static struct mbuf * 719 hfsc_dequeue(struct ifaltq *ifq, int op) 720 { 721 struct hfsc_if *hif = (struct hfsc_if *)ifq->altq_disc; 722 struct hfsc_class *cl; 723 struct mbuf *m; 724 int len, next_len; 725 int realtime = 0; 726 u_int64_t cur_time; 727 728 IFQ_LOCK_ASSERT(ifq); 729 730 if (hif->hif_packets == 0) 731 /* no packet in the tree */ 732 return (NULL); 733 734 cur_time = read_machclk(); 735 736 if (op == ALTDQ_REMOVE && hif->hif_pollcache != NULL) { 737 738 cl = hif->hif_pollcache; 739 hif->hif_pollcache = NULL; 740 /* check if the class was scheduled by real-time criteria */ 741 if (cl->cl_rsc != NULL) 742 realtime = (cl->cl_e <= cur_time); 743 } else { 744 /* 745 * if there are eligible classes, use real-time criteria. 746 * find the class with the minimum deadline among 747 * the eligible classes. 748 */ 749 if ((cl = hfsc_get_mindl(hif, cur_time)) 750 != NULL) { 751 realtime = 1; 752 } else { 753 #ifdef ALTQ_DEBUG 754 int fits = 0; 755 #endif 756 /* 757 * use link-sharing criteria 758 * get the class with the minimum vt in the hierarchy 759 */ 760 cl = hif->hif_rootclass; 761 while (is_a_parent_class(cl)) { 762 763 cl = actlist_firstfit(cl, cur_time); 764 if (cl == NULL) { 765 #ifdef ALTQ_DEBUG 766 if (fits > 0) 767 printf("%d fit but none found\n",fits); 768 #endif 769 return (NULL); 770 } 771 /* 772 * update parent's cl_cvtmin. 773 * don't update if the new vt is smaller. 774 */ 775 if (cl->cl_parent->cl_cvtmin < cl->cl_vt) 776 cl->cl_parent->cl_cvtmin = cl->cl_vt; 777 #ifdef ALTQ_DEBUG 778 fits++; 779 #endif 780 } 781 } 782 783 if (op == ALTDQ_POLL) { 784 hif->hif_pollcache = cl; 785 m = hfsc_pollq(cl); 786 return (m); 787 } 788 } 789 790 m = hfsc_getq(cl); 791 if (m == NULL) 792 panic("hfsc_dequeue:"); 793 len = m_pktlen(m); 794 cl->cl_hif->hif_packets--; 795 IFQ_DEC_LEN(ifq); 796 PKTCNTR_ADD(&cl->cl_stats.xmit_cnt, len); 797 798 update_vf(cl, len, cur_time); 799 if (realtime) 800 cl->cl_cumul += len; 801 802 if (!qempty(cl->cl_q)) { 803 if (cl->cl_rsc != NULL) { 804 /* update ed */ 805 next_len = m_pktlen(qhead(cl->cl_q)); 806 807 if (realtime) 808 update_ed(cl, next_len); 809 else 810 update_d(cl, next_len); 811 } 812 } else { 813 /* the class becomes passive */ 814 set_passive(cl); 815 } 816 817 return (m); 818 } 819 820 static int 821 hfsc_addq(struct hfsc_class *cl, struct mbuf *m) 822 { 823 824 #ifdef ALTQ_RIO 825 if (q_is_rio(cl->cl_q)) 826 return rio_addq((rio_t *)cl->cl_red, cl->cl_q, 827 m, cl->cl_pktattr); 828 #endif 829 #ifdef ALTQ_RED 830 if (q_is_red(cl->cl_q)) 831 return red_addq(cl->cl_red, cl->cl_q, m, cl->cl_pktattr); 832 #endif 833 #ifdef ALTQ_CODEL 834 if (q_is_codel(cl->cl_q)) 835 return codel_addq(cl->cl_codel, cl->cl_q, m); 836 #endif 837 if (qlen(cl->cl_q) >= qlimit(cl->cl_q)) { 838 m_freem(m); 839 return (-1); 840 } 841 842 if (cl->cl_flags & HFCF_CLEARDSCP) 843 write_dsfield(m, cl->cl_pktattr, 0); 844 845 _addq(cl->cl_q, m); 846 847 return (0); 848 } 849 850 static struct mbuf * 851 hfsc_getq(struct hfsc_class *cl) 852 { 853 #ifdef ALTQ_RIO 854 if (q_is_rio(cl->cl_q)) 855 return rio_getq((rio_t *)cl->cl_red, cl->cl_q); 856 #endif 857 #ifdef ALTQ_RED 858 if (q_is_red(cl->cl_q)) 859 return red_getq(cl->cl_red, cl->cl_q); 860 #endif 861 #ifdef ALTQ_CODEL 862 if (q_is_codel(cl->cl_q)) 863 return codel_getq(cl->cl_codel, cl->cl_q); 864 #endif 865 return _getq(cl->cl_q); 866 } 867 868 static struct mbuf * 869 hfsc_pollq(struct hfsc_class *cl) 870 { 871 return qhead(cl->cl_q); 872 } 873 874 static void 875 hfsc_purgeq(struct hfsc_class *cl) 876 { 877 struct mbuf *m; 878 879 if (qempty(cl->cl_q)) 880 return; 881 882 while ((m = _getq(cl->cl_q)) != NULL) { 883 PKTCNTR_ADD(&cl->cl_stats.drop_cnt, m_pktlen(m)); 884 m_freem(m); 885 cl->cl_hif->hif_packets--; 886 IFQ_DEC_LEN(cl->cl_hif->hif_ifq); 887 } 888 ASSERT(qlen(cl->cl_q) == 0); 889 890 update_vf(cl, 0, 0); /* remove cl from the actlist */ 891 set_passive(cl); 892 } 893 894 static void 895 set_active(struct hfsc_class *cl, int len) 896 { 897 if (cl->cl_rsc != NULL) 898 init_ed(cl, len); 899 if (cl->cl_fsc != NULL) 900 init_vf(cl, len); 901 902 cl->cl_stats.period++; 903 } 904 905 static void 906 set_passive(struct hfsc_class *cl) 907 { 908 if (cl->cl_rsc != NULL) 909 ellist_remove(cl); 910 911 /* 912 * actlist is now handled in update_vf() so that update_vf(cl, 0, 0) 913 * needs to be called explicitly to remove a class from actlist 914 */ 915 } 916 917 static void 918 init_ed(struct hfsc_class *cl, int next_len) 919 { 920 u_int64_t cur_time; 921 922 cur_time = read_machclk(); 923 924 /* update the deadline curve */ 925 rtsc_min(&cl->cl_deadline, cl->cl_rsc, cur_time, cl->cl_cumul); 926 927 /* 928 * update the eligible curve. 929 * for concave, it is equal to the deadline curve. 930 * for convex, it is a linear curve with slope m2. 931 */ 932 cl->cl_eligible = cl->cl_deadline; 933 if (cl->cl_rsc->sm1 <= cl->cl_rsc->sm2) { 934 cl->cl_eligible.dx = 0; 935 cl->cl_eligible.dy = 0; 936 } 937 938 /* compute e and d */ 939 cl->cl_e = rtsc_y2x(&cl->cl_eligible, cl->cl_cumul); 940 cl->cl_d = rtsc_y2x(&cl->cl_deadline, cl->cl_cumul + next_len); 941 942 ellist_insert(cl); 943 } 944 945 static void 946 update_ed(struct hfsc_class *cl, int next_len) 947 { 948 cl->cl_e = rtsc_y2x(&cl->cl_eligible, cl->cl_cumul); 949 cl->cl_d = rtsc_y2x(&cl->cl_deadline, cl->cl_cumul + next_len); 950 951 ellist_update(cl); 952 } 953 954 static void 955 update_d(struct hfsc_class *cl, int next_len) 956 { 957 cl->cl_d = rtsc_y2x(&cl->cl_deadline, cl->cl_cumul + next_len); 958 } 959 960 static void 961 init_vf(struct hfsc_class *cl, int len) 962 { 963 struct hfsc_class *max_cl, *p; 964 u_int64_t vt, f, cur_time; 965 int go_active; 966 967 cur_time = 0; 968 go_active = 1; 969 for ( ; cl->cl_parent != NULL; cl = cl->cl_parent) { 970 971 if (go_active && cl->cl_nactive++ == 0) 972 go_active = 1; 973 else 974 go_active = 0; 975 976 if (go_active) { 977 max_cl = TAILQ_LAST(&cl->cl_parent->cl_actc, acthead); 978 if (max_cl != NULL) { 979 /* 980 * set vt to the average of the min and max 981 * classes. if the parent's period didn't 982 * change, don't decrease vt of the class. 983 */ 984 vt = max_cl->cl_vt; 985 if (cl->cl_parent->cl_cvtmin != 0) 986 vt = (cl->cl_parent->cl_cvtmin + vt)/2; 987 988 if (cl->cl_parent->cl_vtperiod != 989 cl->cl_parentperiod || vt > cl->cl_vt) 990 cl->cl_vt = vt; 991 } else { 992 /* 993 * first child for a new parent backlog period. 994 * add parent's cvtmax to vtoff of children 995 * to make a new vt (vtoff + vt) larger than 996 * the vt in the last period for all children. 997 */ 998 vt = cl->cl_parent->cl_cvtmax; 999 for (p = cl->cl_parent->cl_children; p != NULL; 1000 p = p->cl_siblings) 1001 p->cl_vtoff += vt; 1002 cl->cl_vt = 0; 1003 cl->cl_parent->cl_cvtmax = 0; 1004 cl->cl_parent->cl_cvtmin = 0; 1005 } 1006 cl->cl_initvt = cl->cl_vt; 1007 1008 /* update the virtual curve */ 1009 vt = cl->cl_vt + cl->cl_vtoff; 1010 rtsc_min(&cl->cl_virtual, cl->cl_fsc, vt, cl->cl_total); 1011 if (cl->cl_virtual.x == vt) { 1012 cl->cl_virtual.x -= cl->cl_vtoff; 1013 cl->cl_vtoff = 0; 1014 } 1015 cl->cl_vtadj = 0; 1016 1017 cl->cl_vtperiod++; /* increment vt period */ 1018 cl->cl_parentperiod = cl->cl_parent->cl_vtperiod; 1019 if (cl->cl_parent->cl_nactive == 0) 1020 cl->cl_parentperiod++; 1021 cl->cl_f = 0; 1022 1023 actlist_insert(cl); 1024 1025 if (cl->cl_usc != NULL) { 1026 /* class has upper limit curve */ 1027 if (cur_time == 0) 1028 cur_time = read_machclk(); 1029 1030 /* update the ulimit curve */ 1031 rtsc_min(&cl->cl_ulimit, cl->cl_usc, cur_time, 1032 cl->cl_total); 1033 /* compute myf */ 1034 cl->cl_myf = rtsc_y2x(&cl->cl_ulimit, 1035 cl->cl_total); 1036 cl->cl_myfadj = 0; 1037 } 1038 } 1039 1040 if (cl->cl_myf > cl->cl_cfmin) 1041 f = cl->cl_myf; 1042 else 1043 f = cl->cl_cfmin; 1044 if (f != cl->cl_f) { 1045 cl->cl_f = f; 1046 update_cfmin(cl->cl_parent); 1047 } 1048 } 1049 } 1050 1051 static void 1052 update_vf(struct hfsc_class *cl, int len, u_int64_t cur_time) 1053 { 1054 u_int64_t f, myf_bound, delta; 1055 int go_passive; 1056 1057 go_passive = qempty(cl->cl_q); 1058 1059 for (; cl->cl_parent != NULL; cl = cl->cl_parent) { 1060 1061 cl->cl_total += len; 1062 1063 if (cl->cl_fsc == NULL || cl->cl_nactive == 0) 1064 continue; 1065 1066 if (go_passive && --cl->cl_nactive == 0) 1067 go_passive = 1; 1068 else 1069 go_passive = 0; 1070 1071 if (go_passive) { 1072 /* no more active child, going passive */ 1073 1074 /* update cvtmax of the parent class */ 1075 if (cl->cl_vt > cl->cl_parent->cl_cvtmax) 1076 cl->cl_parent->cl_cvtmax = cl->cl_vt; 1077 1078 /* remove this class from the vt list */ 1079 actlist_remove(cl); 1080 1081 update_cfmin(cl->cl_parent); 1082 1083 continue; 1084 } 1085 1086 /* 1087 * update vt and f 1088 */ 1089 cl->cl_vt = rtsc_y2x(&cl->cl_virtual, cl->cl_total) 1090 - cl->cl_vtoff + cl->cl_vtadj; 1091 1092 /* 1093 * if vt of the class is smaller than cvtmin, 1094 * the class was skipped in the past due to non-fit. 1095 * if so, we need to adjust vtadj. 1096 */ 1097 if (cl->cl_vt < cl->cl_parent->cl_cvtmin) { 1098 cl->cl_vtadj += cl->cl_parent->cl_cvtmin - cl->cl_vt; 1099 cl->cl_vt = cl->cl_parent->cl_cvtmin; 1100 } 1101 1102 /* update the vt list */ 1103 actlist_update(cl); 1104 1105 if (cl->cl_usc != NULL) { 1106 cl->cl_myf = cl->cl_myfadj 1107 + rtsc_y2x(&cl->cl_ulimit, cl->cl_total); 1108 1109 /* 1110 * if myf lags behind by more than one clock tick 1111 * from the current time, adjust myfadj to prevent 1112 * a rate-limited class from going greedy. 1113 * in a steady state under rate-limiting, myf 1114 * fluctuates within one clock tick. 1115 */ 1116 myf_bound = cur_time - machclk_per_tick; 1117 if (cl->cl_myf < myf_bound) { 1118 delta = cur_time - cl->cl_myf; 1119 cl->cl_myfadj += delta; 1120 cl->cl_myf += delta; 1121 } 1122 } 1123 1124 /* cl_f is max(cl_myf, cl_cfmin) */ 1125 if (cl->cl_myf > cl->cl_cfmin) 1126 f = cl->cl_myf; 1127 else 1128 f = cl->cl_cfmin; 1129 if (f != cl->cl_f) { 1130 cl->cl_f = f; 1131 update_cfmin(cl->cl_parent); 1132 } 1133 } 1134 } 1135 1136 static void 1137 update_cfmin(struct hfsc_class *cl) 1138 { 1139 struct hfsc_class *p; 1140 u_int64_t cfmin; 1141 1142 if (TAILQ_EMPTY(&cl->cl_actc)) { 1143 cl->cl_cfmin = 0; 1144 return; 1145 } 1146 cfmin = HT_INFINITY; 1147 TAILQ_FOREACH(p, &cl->cl_actc, cl_actlist) { 1148 if (p->cl_f == 0) { 1149 cl->cl_cfmin = 0; 1150 return; 1151 } 1152 if (p->cl_f < cfmin) 1153 cfmin = p->cl_f; 1154 } 1155 cl->cl_cfmin = cfmin; 1156 } 1157 1158 /* 1159 * TAILQ based ellist and actlist implementation 1160 * (ion wanted to make a calendar queue based implementation) 1161 */ 1162 /* 1163 * eligible list holds backlogged classes being sorted by their eligible times. 1164 * there is one eligible list per interface. 1165 */ 1166 1167 static void 1168 ellist_insert(struct hfsc_class *cl) 1169 { 1170 struct hfsc_if *hif = cl->cl_hif; 1171 struct hfsc_class *p; 1172 1173 /* check the last entry first */ 1174 if ((p = TAILQ_LAST(&hif->hif_eligible, elighead)) == NULL || 1175 p->cl_e <= cl->cl_e) { 1176 TAILQ_INSERT_TAIL(&hif->hif_eligible, cl, cl_ellist); 1177 return; 1178 } 1179 1180 TAILQ_FOREACH(p, &hif->hif_eligible, cl_ellist) { 1181 if (cl->cl_e < p->cl_e) { 1182 TAILQ_INSERT_BEFORE(p, cl, cl_ellist); 1183 return; 1184 } 1185 } 1186 ASSERT(0); /* should not reach here */ 1187 } 1188 1189 static void 1190 ellist_remove(struct hfsc_class *cl) 1191 { 1192 struct hfsc_if *hif = cl->cl_hif; 1193 1194 TAILQ_REMOVE(&hif->hif_eligible, cl, cl_ellist); 1195 } 1196 1197 static void 1198 ellist_update(struct hfsc_class *cl) 1199 { 1200 struct hfsc_if *hif = cl->cl_hif; 1201 struct hfsc_class *p, *last; 1202 1203 /* 1204 * the eligible time of a class increases monotonically. 1205 * if the next entry has a larger eligible time, nothing to do. 1206 */ 1207 p = TAILQ_NEXT(cl, cl_ellist); 1208 if (p == NULL || cl->cl_e <= p->cl_e) 1209 return; 1210 1211 /* check the last entry */ 1212 last = TAILQ_LAST(&hif->hif_eligible, elighead); 1213 ASSERT(last != NULL); 1214 if (last->cl_e <= cl->cl_e) { 1215 TAILQ_REMOVE(&hif->hif_eligible, cl, cl_ellist); 1216 TAILQ_INSERT_TAIL(&hif->hif_eligible, cl, cl_ellist); 1217 return; 1218 } 1219 1220 /* 1221 * the new position must be between the next entry 1222 * and the last entry 1223 */ 1224 while ((p = TAILQ_NEXT(p, cl_ellist)) != NULL) { 1225 if (cl->cl_e < p->cl_e) { 1226 TAILQ_REMOVE(&hif->hif_eligible, cl, cl_ellist); 1227 TAILQ_INSERT_BEFORE(p, cl, cl_ellist); 1228 return; 1229 } 1230 } 1231 ASSERT(0); /* should not reach here */ 1232 } 1233 1234 /* find the class with the minimum deadline among the eligible classes */ 1235 struct hfsc_class * 1236 hfsc_get_mindl(struct hfsc_if *hif, u_int64_t cur_time) 1237 { 1238 struct hfsc_class *p, *cl = NULL; 1239 1240 TAILQ_FOREACH(p, &hif->hif_eligible, cl_ellist) { 1241 if (p->cl_e > cur_time) 1242 break; 1243 if (cl == NULL || p->cl_d < cl->cl_d) 1244 cl = p; 1245 } 1246 return (cl); 1247 } 1248 1249 /* 1250 * active children list holds backlogged child classes being sorted 1251 * by their virtual time. 1252 * each intermediate class has one active children list. 1253 */ 1254 1255 static void 1256 actlist_insert(struct hfsc_class *cl) 1257 { 1258 struct hfsc_class *p; 1259 1260 /* check the last entry first */ 1261 if ((p = TAILQ_LAST(&cl->cl_parent->cl_actc, acthead)) == NULL 1262 || p->cl_vt <= cl->cl_vt) { 1263 TAILQ_INSERT_TAIL(&cl->cl_parent->cl_actc, cl, cl_actlist); 1264 return; 1265 } 1266 1267 TAILQ_FOREACH(p, &cl->cl_parent->cl_actc, cl_actlist) { 1268 if (cl->cl_vt < p->cl_vt) { 1269 TAILQ_INSERT_BEFORE(p, cl, cl_actlist); 1270 return; 1271 } 1272 } 1273 ASSERT(0); /* should not reach here */ 1274 } 1275 1276 static void 1277 actlist_remove(struct hfsc_class *cl) 1278 { 1279 TAILQ_REMOVE(&cl->cl_parent->cl_actc, cl, cl_actlist); 1280 } 1281 1282 static void 1283 actlist_update(struct hfsc_class *cl) 1284 { 1285 struct hfsc_class *p, *last; 1286 1287 /* 1288 * the virtual time of a class increases monotonically during its 1289 * backlogged period. 1290 * if the next entry has a larger virtual time, nothing to do. 1291 */ 1292 p = TAILQ_NEXT(cl, cl_actlist); 1293 if (p == NULL || cl->cl_vt < p->cl_vt) 1294 return; 1295 1296 /* check the last entry */ 1297 last = TAILQ_LAST(&cl->cl_parent->cl_actc, acthead); 1298 ASSERT(last != NULL); 1299 if (last->cl_vt <= cl->cl_vt) { 1300 TAILQ_REMOVE(&cl->cl_parent->cl_actc, cl, cl_actlist); 1301 TAILQ_INSERT_TAIL(&cl->cl_parent->cl_actc, cl, cl_actlist); 1302 return; 1303 } 1304 1305 /* 1306 * the new position must be between the next entry 1307 * and the last entry 1308 */ 1309 while ((p = TAILQ_NEXT(p, cl_actlist)) != NULL) { 1310 if (cl->cl_vt < p->cl_vt) { 1311 TAILQ_REMOVE(&cl->cl_parent->cl_actc, cl, cl_actlist); 1312 TAILQ_INSERT_BEFORE(p, cl, cl_actlist); 1313 return; 1314 } 1315 } 1316 ASSERT(0); /* should not reach here */ 1317 } 1318 1319 static struct hfsc_class * 1320 actlist_firstfit(struct hfsc_class *cl, u_int64_t cur_time) 1321 { 1322 struct hfsc_class *p; 1323 1324 TAILQ_FOREACH(p, &cl->cl_actc, cl_actlist) { 1325 if (p->cl_f <= cur_time) 1326 return (p); 1327 } 1328 return (NULL); 1329 } 1330 1331 /* 1332 * service curve support functions 1333 * 1334 * external service curve parameters 1335 * m: bits/sec 1336 * d: msec 1337 * internal service curve parameters 1338 * sm: (bytes/machclk tick) << SM_SHIFT 1339 * ism: (machclk ticks/byte) << ISM_SHIFT 1340 * dx: machclk ticks 1341 * 1342 * SM_SHIFT and ISM_SHIFT are scaled in order to keep effective digits. we 1343 * should be able to handle 100K-100Gbps linkspeed with 256 MHz machclk 1344 * frequency and at least 3 effective digits in decimal. 1345 * 1346 */ 1347 #define SM_SHIFT 24 1348 #define ISM_SHIFT 14 1349 1350 #define SM_MASK ((1LL << SM_SHIFT) - 1) 1351 #define ISM_MASK ((1LL << ISM_SHIFT) - 1) 1352 1353 static __inline u_int64_t 1354 seg_x2y(u_int64_t x, u_int64_t sm) 1355 { 1356 u_int64_t y; 1357 1358 /* 1359 * compute 1360 * y = x * sm >> SM_SHIFT 1361 * but divide it for the upper and lower bits to avoid overflow 1362 */ 1363 y = (x >> SM_SHIFT) * sm + (((x & SM_MASK) * sm) >> SM_SHIFT); 1364 return (y); 1365 } 1366 1367 static __inline u_int64_t 1368 seg_y2x(u_int64_t y, u_int64_t ism) 1369 { 1370 u_int64_t x; 1371 1372 if (y == 0) 1373 x = 0; 1374 else if (ism == HT_INFINITY) 1375 x = HT_INFINITY; 1376 else { 1377 x = (y >> ISM_SHIFT) * ism 1378 + (((y & ISM_MASK) * ism) >> ISM_SHIFT); 1379 } 1380 return (x); 1381 } 1382 1383 static __inline u_int64_t 1384 m2sm(u_int64_t m) 1385 { 1386 u_int64_t sm; 1387 1388 sm = (m << SM_SHIFT) / 8 / machclk_freq; 1389 return (sm); 1390 } 1391 1392 static __inline u_int64_t 1393 m2ism(u_int64_t m) 1394 { 1395 u_int64_t ism; 1396 1397 if (m == 0) 1398 ism = HT_INFINITY; 1399 else 1400 ism = ((u_int64_t)machclk_freq << ISM_SHIFT) * 8 / m; 1401 return (ism); 1402 } 1403 1404 static __inline u_int64_t 1405 d2dx(u_int d) 1406 { 1407 u_int64_t dx; 1408 1409 dx = ((u_int64_t)d * machclk_freq) / 1000; 1410 return (dx); 1411 } 1412 1413 static u_int64_t 1414 sm2m(u_int64_t sm) 1415 { 1416 u_int64_t m; 1417 1418 m = (sm * 8 * machclk_freq) >> SM_SHIFT; 1419 return (m); 1420 } 1421 1422 static u_int 1423 dx2d(u_int64_t dx) 1424 { 1425 u_int64_t d; 1426 1427 d = dx * 1000 / machclk_freq; 1428 return ((u_int)d); 1429 } 1430 1431 static void 1432 sc2isc(struct service_curve *sc, struct internal_sc *isc) 1433 { 1434 isc->sm1 = m2sm(sc->m1); 1435 isc->ism1 = m2ism(sc->m1); 1436 isc->dx = d2dx(sc->d); 1437 isc->dy = seg_x2y(isc->dx, isc->sm1); 1438 isc->sm2 = m2sm(sc->m2); 1439 isc->ism2 = m2ism(sc->m2); 1440 } 1441 1442 /* 1443 * initialize the runtime service curve with the given internal 1444 * service curve starting at (x, y). 1445 */ 1446 static void 1447 rtsc_init(struct runtime_sc *rtsc, struct internal_sc * isc, u_int64_t x, 1448 u_int64_t y) 1449 { 1450 rtsc->x = x; 1451 rtsc->y = y; 1452 rtsc->sm1 = isc->sm1; 1453 rtsc->ism1 = isc->ism1; 1454 rtsc->dx = isc->dx; 1455 rtsc->dy = isc->dy; 1456 rtsc->sm2 = isc->sm2; 1457 rtsc->ism2 = isc->ism2; 1458 } 1459 1460 /* 1461 * calculate the y-projection of the runtime service curve by the 1462 * given x-projection value 1463 */ 1464 static u_int64_t 1465 rtsc_y2x(struct runtime_sc *rtsc, u_int64_t y) 1466 { 1467 u_int64_t x; 1468 1469 if (y < rtsc->y) 1470 x = rtsc->x; 1471 else if (y <= rtsc->y + rtsc->dy) { 1472 /* x belongs to the 1st segment */ 1473 if (rtsc->dy == 0) 1474 x = rtsc->x + rtsc->dx; 1475 else 1476 x = rtsc->x + seg_y2x(y - rtsc->y, rtsc->ism1); 1477 } else { 1478 /* x belongs to the 2nd segment */ 1479 x = rtsc->x + rtsc->dx 1480 + seg_y2x(y - rtsc->y - rtsc->dy, rtsc->ism2); 1481 } 1482 return (x); 1483 } 1484 1485 static u_int64_t 1486 rtsc_x2y(struct runtime_sc *rtsc, u_int64_t x) 1487 { 1488 u_int64_t y; 1489 1490 if (x <= rtsc->x) 1491 y = rtsc->y; 1492 else if (x <= rtsc->x + rtsc->dx) 1493 /* y belongs to the 1st segment */ 1494 y = rtsc->y + seg_x2y(x - rtsc->x, rtsc->sm1); 1495 else 1496 /* y belongs to the 2nd segment */ 1497 y = rtsc->y + rtsc->dy 1498 + seg_x2y(x - rtsc->x - rtsc->dx, rtsc->sm2); 1499 return (y); 1500 } 1501 1502 /* 1503 * update the runtime service curve by taking the minimum of the current 1504 * runtime service curve and the service curve starting at (x, y). 1505 */ 1506 static void 1507 rtsc_min(struct runtime_sc *rtsc, struct internal_sc *isc, u_int64_t x, 1508 u_int64_t y) 1509 { 1510 u_int64_t y1, y2, dx, dy; 1511 1512 if (isc->sm1 <= isc->sm2) { 1513 /* service curve is convex */ 1514 y1 = rtsc_x2y(rtsc, x); 1515 if (y1 < y) 1516 /* the current rtsc is smaller */ 1517 return; 1518 rtsc->x = x; 1519 rtsc->y = y; 1520 return; 1521 } 1522 1523 /* 1524 * service curve is concave 1525 * compute the two y values of the current rtsc 1526 * y1: at x 1527 * y2: at (x + dx) 1528 */ 1529 y1 = rtsc_x2y(rtsc, x); 1530 if (y1 <= y) { 1531 /* rtsc is below isc, no change to rtsc */ 1532 return; 1533 } 1534 1535 y2 = rtsc_x2y(rtsc, x + isc->dx); 1536 if (y2 >= y + isc->dy) { 1537 /* rtsc is above isc, replace rtsc by isc */ 1538 rtsc->x = x; 1539 rtsc->y = y; 1540 rtsc->dx = isc->dx; 1541 rtsc->dy = isc->dy; 1542 return; 1543 } 1544 1545 /* 1546 * the two curves intersect 1547 * compute the offsets (dx, dy) using the reverse 1548 * function of seg_x2y() 1549 * seg_x2y(dx, sm1) == seg_x2y(dx, sm2) + (y1 - y) 1550 */ 1551 dx = ((y1 - y) << SM_SHIFT) / (isc->sm1 - isc->sm2); 1552 /* 1553 * check if (x, y1) belongs to the 1st segment of rtsc. 1554 * if so, add the offset. 1555 */ 1556 if (rtsc->x + rtsc->dx > x) 1557 dx += rtsc->x + rtsc->dx - x; 1558 dy = seg_x2y(dx, isc->sm1); 1559 1560 rtsc->x = x; 1561 rtsc->y = y; 1562 rtsc->dx = dx; 1563 rtsc->dy = dy; 1564 return; 1565 } 1566 1567 static void 1568 get_class_stats_v0(struct hfsc_classstats_v0 *sp, struct hfsc_class *cl) 1569 { 1570 sp->class_id = cl->cl_id; 1571 sp->class_handle = cl->cl_handle; 1572 1573 #define SATU32(x) (u_int32_t)uqmin((x), UINT_MAX) 1574 1575 if (cl->cl_rsc != NULL) { 1576 sp->rsc.m1 = SATU32(sm2m(cl->cl_rsc->sm1)); 1577 sp->rsc.d = dx2d(cl->cl_rsc->dx); 1578 sp->rsc.m2 = SATU32(sm2m(cl->cl_rsc->sm2)); 1579 } else { 1580 sp->rsc.m1 = 0; 1581 sp->rsc.d = 0; 1582 sp->rsc.m2 = 0; 1583 } 1584 if (cl->cl_fsc != NULL) { 1585 sp->fsc.m1 = SATU32(sm2m(cl->cl_fsc->sm1)); 1586 sp->fsc.d = dx2d(cl->cl_fsc->dx); 1587 sp->fsc.m2 = SATU32(sm2m(cl->cl_fsc->sm2)); 1588 } else { 1589 sp->fsc.m1 = 0; 1590 sp->fsc.d = 0; 1591 sp->fsc.m2 = 0; 1592 } 1593 if (cl->cl_usc != NULL) { 1594 sp->usc.m1 = SATU32(sm2m(cl->cl_usc->sm1)); 1595 sp->usc.d = dx2d(cl->cl_usc->dx); 1596 sp->usc.m2 = SATU32(sm2m(cl->cl_usc->sm2)); 1597 } else { 1598 sp->usc.m1 = 0; 1599 sp->usc.d = 0; 1600 sp->usc.m2 = 0; 1601 } 1602 1603 #undef SATU32 1604 1605 sp->total = cl->cl_total; 1606 sp->cumul = cl->cl_cumul; 1607 1608 sp->d = cl->cl_d; 1609 sp->e = cl->cl_e; 1610 sp->vt = cl->cl_vt; 1611 sp->f = cl->cl_f; 1612 1613 sp->initvt = cl->cl_initvt; 1614 sp->vtperiod = cl->cl_vtperiod; 1615 sp->parentperiod = cl->cl_parentperiod; 1616 sp->nactive = cl->cl_nactive; 1617 sp->vtoff = cl->cl_vtoff; 1618 sp->cvtmax = cl->cl_cvtmax; 1619 sp->myf = cl->cl_myf; 1620 sp->cfmin = cl->cl_cfmin; 1621 sp->cvtmin = cl->cl_cvtmin; 1622 sp->myfadj = cl->cl_myfadj; 1623 sp->vtadj = cl->cl_vtadj; 1624 1625 sp->cur_time = read_machclk(); 1626 sp->machclk_freq = machclk_freq; 1627 1628 sp->qlength = qlen(cl->cl_q); 1629 sp->qlimit = qlimit(cl->cl_q); 1630 sp->xmit_cnt = cl->cl_stats.xmit_cnt; 1631 sp->drop_cnt = cl->cl_stats.drop_cnt; 1632 sp->period = cl->cl_stats.period; 1633 1634 sp->qtype = qtype(cl->cl_q); 1635 #ifdef ALTQ_RED 1636 if (q_is_red(cl->cl_q)) 1637 red_getstats(cl->cl_red, &sp->red[0]); 1638 #endif 1639 #ifdef ALTQ_RIO 1640 if (q_is_rio(cl->cl_q)) 1641 rio_getstats((rio_t *)cl->cl_red, &sp->red[0]); 1642 #endif 1643 #ifdef ALTQ_CODEL 1644 if (q_is_codel(cl->cl_q)) 1645 codel_getstats(cl->cl_codel, &sp->codel); 1646 #endif 1647 } 1648 1649 static void 1650 get_class_stats_v1(struct hfsc_classstats_v1 *sp, struct hfsc_class *cl) 1651 { 1652 sp->class_id = cl->cl_id; 1653 sp->class_handle = cl->cl_handle; 1654 1655 if (cl->cl_rsc != NULL) { 1656 sp->rsc.m1 = sm2m(cl->cl_rsc->sm1); 1657 sp->rsc.d = dx2d(cl->cl_rsc->dx); 1658 sp->rsc.m2 = sm2m(cl->cl_rsc->sm2); 1659 } else { 1660 sp->rsc.m1 = 0; 1661 sp->rsc.d = 0; 1662 sp->rsc.m2 = 0; 1663 } 1664 if (cl->cl_fsc != NULL) { 1665 sp->fsc.m1 = sm2m(cl->cl_fsc->sm1); 1666 sp->fsc.d = dx2d(cl->cl_fsc->dx); 1667 sp->fsc.m2 = sm2m(cl->cl_fsc->sm2); 1668 } else { 1669 sp->fsc.m1 = 0; 1670 sp->fsc.d = 0; 1671 sp->fsc.m2 = 0; 1672 } 1673 if (cl->cl_usc != NULL) { 1674 sp->usc.m1 = sm2m(cl->cl_usc->sm1); 1675 sp->usc.d = dx2d(cl->cl_usc->dx); 1676 sp->usc.m2 = sm2m(cl->cl_usc->sm2); 1677 } else { 1678 sp->usc.m1 = 0; 1679 sp->usc.d = 0; 1680 sp->usc.m2 = 0; 1681 } 1682 1683 sp->total = cl->cl_total; 1684 sp->cumul = cl->cl_cumul; 1685 1686 sp->d = cl->cl_d; 1687 sp->e = cl->cl_e; 1688 sp->vt = cl->cl_vt; 1689 sp->f = cl->cl_f; 1690 1691 sp->initvt = cl->cl_initvt; 1692 sp->vtperiod = cl->cl_vtperiod; 1693 sp->parentperiod = cl->cl_parentperiod; 1694 sp->nactive = cl->cl_nactive; 1695 sp->vtoff = cl->cl_vtoff; 1696 sp->cvtmax = cl->cl_cvtmax; 1697 sp->myf = cl->cl_myf; 1698 sp->cfmin = cl->cl_cfmin; 1699 sp->cvtmin = cl->cl_cvtmin; 1700 sp->myfadj = cl->cl_myfadj; 1701 sp->vtadj = cl->cl_vtadj; 1702 1703 sp->cur_time = read_machclk(); 1704 sp->machclk_freq = machclk_freq; 1705 1706 sp->qlength = qlen(cl->cl_q); 1707 sp->qlimit = qlimit(cl->cl_q); 1708 sp->xmit_cnt = cl->cl_stats.xmit_cnt; 1709 sp->drop_cnt = cl->cl_stats.drop_cnt; 1710 sp->period = cl->cl_stats.period; 1711 1712 sp->qtype = qtype(cl->cl_q); 1713 #ifdef ALTQ_RED 1714 if (q_is_red(cl->cl_q)) 1715 red_getstats(cl->cl_red, &sp->red[0]); 1716 #endif 1717 #ifdef ALTQ_RIO 1718 if (q_is_rio(cl->cl_q)) 1719 rio_getstats((rio_t *)cl->cl_red, &sp->red[0]); 1720 #endif 1721 #ifdef ALTQ_CODEL 1722 if (q_is_codel(cl->cl_q)) 1723 codel_getstats(cl->cl_codel, &sp->codel); 1724 #endif 1725 } 1726 1727 /* convert a class handle to the corresponding class pointer */ 1728 static struct hfsc_class * 1729 clh_to_clp(struct hfsc_if *hif, u_int32_t chandle) 1730 { 1731 int i; 1732 struct hfsc_class *cl; 1733 1734 if (chandle == 0) 1735 return (NULL); 1736 /* 1737 * first, try optimistically the slot matching the lower bits of 1738 * the handle. if it fails, do the linear table search. 1739 */ 1740 i = chandle % HFSC_MAX_CLASSES; 1741 if ((cl = hif->hif_class_tbl[i]) != NULL && cl->cl_handle == chandle) 1742 return (cl); 1743 for (i = 0; i < HFSC_MAX_CLASSES; i++) 1744 if ((cl = hif->hif_class_tbl[i]) != NULL && 1745 cl->cl_handle == chandle) 1746 return (cl); 1747 return (NULL); 1748 } 1749 1750 1751 #endif /* ALTQ_HFSC */ 1752