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