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