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 #ifdef ALTQ3_COMPAT 74 #include <net/altq/altq_conf.h> 75 #endif 76 77 /* 78 * function prototypes 79 */ 80 static int hfsc_clear_interface(struct hfsc_if *); 81 static int hfsc_request(struct ifaltq *, int, void *); 82 static void hfsc_purge(struct hfsc_if *); 83 static struct hfsc_class *hfsc_class_create(struct hfsc_if *, 84 struct service_curve *, struct service_curve *, struct service_curve *, 85 struct hfsc_class *, int, int, int); 86 static int hfsc_class_destroy(struct hfsc_class *); 87 static struct hfsc_class *hfsc_nextclass(struct hfsc_class *); 88 static int hfsc_enqueue(struct ifaltq *, struct mbuf *, 89 struct altq_pktattr *); 90 static struct mbuf *hfsc_dequeue(struct ifaltq *, int); 91 92 static int hfsc_addq(struct hfsc_class *, struct mbuf *); 93 static struct mbuf *hfsc_getq(struct hfsc_class *); 94 static struct mbuf *hfsc_pollq(struct hfsc_class *); 95 static void hfsc_purgeq(struct hfsc_class *); 96 97 static void update_cfmin(struct hfsc_class *); 98 static void set_active(struct hfsc_class *, int); 99 static void set_passive(struct hfsc_class *); 100 101 static void init_ed(struct hfsc_class *, int); 102 static void update_ed(struct hfsc_class *, int); 103 static void update_d(struct hfsc_class *, int); 104 static void init_vf(struct hfsc_class *, int); 105 static void update_vf(struct hfsc_class *, int, u_int64_t); 106 static void ellist_insert(struct hfsc_class *); 107 static void ellist_remove(struct hfsc_class *); 108 static void ellist_update(struct hfsc_class *); 109 struct hfsc_class *hfsc_get_mindl(struct hfsc_if *, u_int64_t); 110 static void actlist_insert(struct hfsc_class *); 111 static void actlist_remove(struct hfsc_class *); 112 static void actlist_update(struct hfsc_class *); 113 114 static struct hfsc_class *actlist_firstfit(struct hfsc_class *, 115 u_int64_t); 116 117 static __inline u_int64_t seg_x2y(u_int64_t, u_int64_t); 118 static __inline u_int64_t seg_y2x(u_int64_t, u_int64_t); 119 static __inline u_int64_t m2sm(u_int); 120 static __inline u_int64_t m2ism(u_int); 121 static __inline u_int64_t d2dx(u_int); 122 static u_int sm2m(u_int64_t); 123 static u_int dx2d(u_int64_t); 124 125 static void sc2isc(struct service_curve *, struct internal_sc *); 126 static void rtsc_init(struct runtime_sc *, struct internal_sc *, 127 u_int64_t, u_int64_t); 128 static u_int64_t rtsc_y2x(struct runtime_sc *, u_int64_t); 129 static u_int64_t rtsc_x2y(struct runtime_sc *, u_int64_t); 130 static void rtsc_min(struct runtime_sc *, struct internal_sc *, 131 u_int64_t, u_int64_t); 132 133 static void get_class_stats(struct hfsc_classstats *, 134 struct hfsc_class *); 135 static struct hfsc_class *clh_to_clp(struct hfsc_if *, u_int32_t); 136 137 138 #ifdef ALTQ3_COMPAT 139 static struct hfsc_if *hfsc_attach(struct ifaltq *, u_int); 140 static int hfsc_detach(struct hfsc_if *); 141 static int hfsc_class_modify(struct hfsc_class *, struct service_curve *, 142 struct service_curve *, struct service_curve *); 143 144 static int hfsccmd_if_attach(struct hfsc_attach *); 145 static int hfsccmd_if_detach(struct hfsc_interface *); 146 static int hfsccmd_add_class(struct hfsc_add_class *); 147 static int hfsccmd_delete_class(struct hfsc_delete_class *); 148 static int hfsccmd_modify_class(struct hfsc_modify_class *); 149 static int hfsccmd_add_filter(struct hfsc_add_filter *); 150 static int hfsccmd_delete_filter(struct hfsc_delete_filter *); 151 static int hfsccmd_class_stats(struct hfsc_class_stats *); 152 153 altqdev_decl(hfsc); 154 #endif /* ALTQ3_COMPAT */ 155 156 /* 157 * macros 158 */ 159 #define is_a_parent_class(cl) ((cl)->cl_children != NULL) 160 161 #define HT_INFINITY 0xffffffffffffffffLL /* infinite time value */ 162 163 #ifdef ALTQ3_COMPAT 164 /* hif_list keeps all hfsc_if's allocated. */ 165 static struct hfsc_if *hif_list = NULL; 166 #endif /* ALTQ3_COMPAT */ 167 168 int 169 hfsc_pfattach(struct pf_altq *a) 170 { 171 struct ifnet *ifp; 172 int s, error; 173 174 if ((ifp = ifunit(a->ifname)) == NULL || a->altq_disc == NULL) 175 return (EINVAL); 176 s = splnet(); 177 error = altq_attach(&ifp->if_snd, ALTQT_HFSC, a->altq_disc, 178 hfsc_enqueue, hfsc_dequeue, hfsc_request, NULL, NULL); 179 splx(s); 180 return (error); 181 } 182 183 int 184 hfsc_add_altq(struct pf_altq *a) 185 { 186 struct hfsc_if *hif; 187 struct ifnet *ifp; 188 189 if ((ifp = ifunit(a->ifname)) == NULL) 190 return (EINVAL); 191 if (!ALTQ_IS_READY(&ifp->if_snd)) 192 return (ENODEV); 193 194 hif = malloc(sizeof(struct hfsc_if), M_DEVBUF, M_NOWAIT | M_ZERO); 195 if (hif == NULL) 196 return (ENOMEM); 197 198 TAILQ_INIT(&hif->hif_eligible); 199 hif->hif_ifq = &ifp->if_snd; 200 201 /* keep the state in pf_altq */ 202 a->altq_disc = hif; 203 204 return (0); 205 } 206 207 int 208 hfsc_remove_altq(struct pf_altq *a) 209 { 210 struct hfsc_if *hif; 211 212 if ((hif = a->altq_disc) == NULL) 213 return (EINVAL); 214 a->altq_disc = NULL; 215 216 (void)hfsc_clear_interface(hif); 217 (void)hfsc_class_destroy(hif->hif_rootclass); 218 219 free(hif, M_DEVBUF); 220 221 return (0); 222 } 223 224 int 225 hfsc_add_queue(struct pf_altq *a) 226 { 227 struct hfsc_if *hif; 228 struct hfsc_class *cl, *parent; 229 struct hfsc_opts *opts; 230 struct service_curve rtsc, lssc, ulsc; 231 232 if ((hif = a->altq_disc) == NULL) 233 return (EINVAL); 234 235 opts = &a->pq_u.hfsc_opts; 236 237 if (a->parent_qid == HFSC_NULLCLASS_HANDLE && 238 hif->hif_rootclass == NULL) 239 parent = NULL; 240 else if ((parent = clh_to_clp(hif, a->parent_qid)) == NULL) 241 return (EINVAL); 242 243 if (a->qid == 0) 244 return (EINVAL); 245 246 if (clh_to_clp(hif, a->qid) != NULL) 247 return (EBUSY); 248 249 rtsc.m1 = opts->rtsc_m1; 250 rtsc.d = opts->rtsc_d; 251 rtsc.m2 = opts->rtsc_m2; 252 lssc.m1 = opts->lssc_m1; 253 lssc.d = opts->lssc_d; 254 lssc.m2 = opts->lssc_m2; 255 ulsc.m1 = opts->ulsc_m1; 256 ulsc.d = opts->ulsc_d; 257 ulsc.m2 = opts->ulsc_m2; 258 259 cl = hfsc_class_create(hif, &rtsc, &lssc, &ulsc, 260 parent, a->qlimit, opts->flags, a->qid); 261 if (cl == NULL) 262 return (ENOMEM); 263 264 return (0); 265 } 266 267 int 268 hfsc_remove_queue(struct pf_altq *a) 269 { 270 struct hfsc_if *hif; 271 struct hfsc_class *cl; 272 273 if ((hif = a->altq_disc) == NULL) 274 return (EINVAL); 275 276 if ((cl = clh_to_clp(hif, a->qid)) == NULL) 277 return (EINVAL); 278 279 return (hfsc_class_destroy(cl)); 280 } 281 282 int 283 hfsc_getqstats(struct pf_altq *a, void *ubuf, int *nbytes) 284 { 285 struct hfsc_if *hif; 286 struct hfsc_class *cl; 287 struct hfsc_classstats stats; 288 int error = 0; 289 290 if ((hif = altq_lookup(a->ifname, ALTQT_HFSC)) == NULL) 291 return (EBADF); 292 293 if ((cl = clh_to_clp(hif, a->qid)) == NULL) 294 return (EINVAL); 295 296 if (*nbytes < sizeof(stats)) 297 return (EINVAL); 298 299 get_class_stats(&stats, cl); 300 301 if ((error = copyout((caddr_t)&stats, ubuf, sizeof(stats))) != 0) 302 return (error); 303 *nbytes = sizeof(stats); 304 return (0); 305 } 306 307 /* 308 * bring the interface back to the initial state by discarding 309 * all the filters and classes except the root class. 310 */ 311 static int 312 hfsc_clear_interface(struct hfsc_if *hif) 313 { 314 struct hfsc_class *cl; 315 316 #ifdef ALTQ3_COMPAT 317 /* free the filters for this interface */ 318 acc_discard_filters(&hif->hif_classifier, NULL, 1); 319 #endif 320 321 /* clear out the classes */ 322 while (hif->hif_rootclass != NULL && 323 (cl = hif->hif_rootclass->cl_children) != NULL) { 324 /* 325 * remove the first leaf class found in the hierarchy 326 * then start over 327 */ 328 for (; cl != NULL; cl = hfsc_nextclass(cl)) { 329 if (!is_a_parent_class(cl)) { 330 (void)hfsc_class_destroy(cl); 331 break; 332 } 333 } 334 } 335 336 return (0); 337 } 338 339 static int 340 hfsc_request(struct ifaltq *ifq, int req, void *arg) 341 { 342 struct hfsc_if *hif = (struct hfsc_if *)ifq->altq_disc; 343 344 IFQ_LOCK_ASSERT(ifq); 345 346 switch (req) { 347 case ALTRQ_PURGE: 348 hfsc_purge(hif); 349 break; 350 } 351 return (0); 352 } 353 354 /* discard all the queued packets on the interface */ 355 static void 356 hfsc_purge(struct hfsc_if *hif) 357 { 358 struct hfsc_class *cl; 359 360 for (cl = hif->hif_rootclass; cl != NULL; cl = hfsc_nextclass(cl)) 361 if (!qempty(cl->cl_q)) 362 hfsc_purgeq(cl); 363 if (ALTQ_IS_ENABLED(hif->hif_ifq)) 364 hif->hif_ifq->ifq_len = 0; 365 } 366 367 struct hfsc_class * 368 hfsc_class_create(struct hfsc_if *hif, struct service_curve *rsc, 369 struct service_curve *fsc, struct service_curve *usc, 370 struct hfsc_class *parent, int qlimit, int flags, int qid) 371 { 372 struct hfsc_class *cl, *p; 373 int i, s; 374 375 if (hif->hif_classes >= HFSC_MAX_CLASSES) 376 return (NULL); 377 378 #ifndef ALTQ_RED 379 if (flags & HFCF_RED) { 380 #ifdef ALTQ_DEBUG 381 printf("hfsc_class_create: RED not configured for HFSC!\n"); 382 #endif 383 return (NULL); 384 } 385 #endif 386 #ifndef ALTQ_CODEL 387 if (flags & HFCF_CODEL) { 388 #ifdef ALTQ_DEBUG 389 printf("hfsc_class_create: CODEL not configured for HFSC!\n"); 390 #endif 391 return (NULL); 392 } 393 #endif 394 395 cl = malloc(sizeof(struct hfsc_class), M_DEVBUF, M_NOWAIT | M_ZERO); 396 if (cl == NULL) 397 return (NULL); 398 399 cl->cl_q = malloc(sizeof(class_queue_t), M_DEVBUF, M_NOWAIT | M_ZERO); 400 if (cl->cl_q == NULL) 401 goto err_ret; 402 403 TAILQ_INIT(&cl->cl_actc); 404 405 if (qlimit == 0) 406 qlimit = 50; /* use default */ 407 qlimit(cl->cl_q) = qlimit; 408 qtype(cl->cl_q) = Q_DROPTAIL; 409 qlen(cl->cl_q) = 0; 410 qsize(cl->cl_q) = 0; 411 cl->cl_flags = flags; 412 #ifdef ALTQ_RED 413 if (flags & (HFCF_RED|HFCF_RIO)) { 414 int red_flags, red_pkttime; 415 u_int m2; 416 417 m2 = 0; 418 if (rsc != NULL && rsc->m2 > m2) 419 m2 = rsc->m2; 420 if (fsc != NULL && fsc->m2 > m2) 421 m2 = fsc->m2; 422 if (usc != NULL && usc->m2 > m2) 423 m2 = usc->m2; 424 425 red_flags = 0; 426 if (flags & HFCF_ECN) 427 red_flags |= REDF_ECN; 428 #ifdef ALTQ_RIO 429 if (flags & HFCF_CLEARDSCP) 430 red_flags |= RIOF_CLEARDSCP; 431 #endif 432 if (m2 < 8) 433 red_pkttime = 1000 * 1000 * 1000; /* 1 sec */ 434 else 435 red_pkttime = (int64_t)hif->hif_ifq->altq_ifp->if_mtu 436 * 1000 * 1000 * 1000 / (m2 / 8); 437 if (flags & HFCF_RED) { 438 cl->cl_red = red_alloc(0, 0, 439 qlimit(cl->cl_q) * 10/100, 440 qlimit(cl->cl_q) * 30/100, 441 red_flags, red_pkttime); 442 if (cl->cl_red != NULL) 443 qtype(cl->cl_q) = Q_RED; 444 } 445 #ifdef ALTQ_RIO 446 else { 447 cl->cl_red = (red_t *)rio_alloc(0, NULL, 448 red_flags, red_pkttime); 449 if (cl->cl_red != NULL) 450 qtype(cl->cl_q) = Q_RIO; 451 } 452 #endif 453 } 454 #endif /* ALTQ_RED */ 455 #ifdef ALTQ_CODEL 456 if (flags & HFCF_CODEL) { 457 cl->cl_codel = codel_alloc(5, 100, 0); 458 if (cl->cl_codel != NULL) 459 qtype(cl->cl_q) = Q_CODEL; 460 } 461 #endif 462 463 if (rsc != NULL && (rsc->m1 != 0 || rsc->m2 != 0)) { 464 cl->cl_rsc = malloc(sizeof(struct internal_sc), 465 M_DEVBUF, M_NOWAIT); 466 if (cl->cl_rsc == NULL) 467 goto err_ret; 468 sc2isc(rsc, cl->cl_rsc); 469 rtsc_init(&cl->cl_deadline, cl->cl_rsc, 0, 0); 470 rtsc_init(&cl->cl_eligible, cl->cl_rsc, 0, 0); 471 } 472 if (fsc != NULL && (fsc->m1 != 0 || fsc->m2 != 0)) { 473 cl->cl_fsc = malloc(sizeof(struct internal_sc), 474 M_DEVBUF, M_NOWAIT); 475 if (cl->cl_fsc == NULL) 476 goto err_ret; 477 sc2isc(fsc, cl->cl_fsc); 478 rtsc_init(&cl->cl_virtual, cl->cl_fsc, 0, 0); 479 } 480 if (usc != NULL && (usc->m1 != 0 || usc->m2 != 0)) { 481 cl->cl_usc = malloc(sizeof(struct internal_sc), 482 M_DEVBUF, M_NOWAIT); 483 if (cl->cl_usc == NULL) 484 goto err_ret; 485 sc2isc(usc, cl->cl_usc); 486 rtsc_init(&cl->cl_ulimit, cl->cl_usc, 0, 0); 487 } 488 489 cl->cl_id = hif->hif_classid++; 490 cl->cl_handle = qid; 491 cl->cl_hif = hif; 492 cl->cl_parent = parent; 493 494 s = splnet(); 495 IFQ_LOCK(hif->hif_ifq); 496 hif->hif_classes++; 497 498 /* 499 * find a free slot in the class table. if the slot matching 500 * the lower bits of qid is free, use this slot. otherwise, 501 * use the first free slot. 502 */ 503 i = qid % HFSC_MAX_CLASSES; 504 if (hif->hif_class_tbl[i] == NULL) 505 hif->hif_class_tbl[i] = cl; 506 else { 507 for (i = 0; i < HFSC_MAX_CLASSES; i++) 508 if (hif->hif_class_tbl[i] == NULL) { 509 hif->hif_class_tbl[i] = cl; 510 break; 511 } 512 if (i == HFSC_MAX_CLASSES) { 513 IFQ_UNLOCK(hif->hif_ifq); 514 splx(s); 515 goto err_ret; 516 } 517 } 518 519 if (flags & HFCF_DEFAULTCLASS) 520 hif->hif_defaultclass = cl; 521 522 if (parent == NULL) { 523 /* this is root class */ 524 hif->hif_rootclass = cl; 525 } else { 526 /* add this class to the children list of the parent */ 527 if ((p = parent->cl_children) == NULL) 528 parent->cl_children = cl; 529 else { 530 while (p->cl_siblings != NULL) 531 p = p->cl_siblings; 532 p->cl_siblings = cl; 533 } 534 } 535 IFQ_UNLOCK(hif->hif_ifq); 536 splx(s); 537 538 return (cl); 539 540 err_ret: 541 if (cl->cl_red != NULL) { 542 #ifdef ALTQ_RIO 543 if (q_is_rio(cl->cl_q)) 544 rio_destroy((rio_t *)cl->cl_red); 545 #endif 546 #ifdef ALTQ_RED 547 if (q_is_red(cl->cl_q)) 548 red_destroy(cl->cl_red); 549 #endif 550 #ifdef ALTQ_CODEL 551 if (q_is_codel(cl->cl_q)) 552 codel_destroy(cl->cl_codel); 553 #endif 554 } 555 if (cl->cl_fsc != NULL) 556 free(cl->cl_fsc, M_DEVBUF); 557 if (cl->cl_rsc != NULL) 558 free(cl->cl_rsc, M_DEVBUF); 559 if (cl->cl_usc != NULL) 560 free(cl->cl_usc, M_DEVBUF); 561 if (cl->cl_q != NULL) 562 free(cl->cl_q, M_DEVBUF); 563 free(cl, M_DEVBUF); 564 return (NULL); 565 } 566 567 static int 568 hfsc_class_destroy(struct hfsc_class *cl) 569 { 570 int i, s; 571 572 if (cl == NULL) 573 return (0); 574 575 if (is_a_parent_class(cl)) 576 return (EBUSY); 577 578 s = splnet(); 579 IFQ_LOCK(cl->cl_hif->hif_ifq); 580 581 #ifdef ALTQ3_COMPAT 582 /* delete filters referencing to this class */ 583 acc_discard_filters(&cl->cl_hif->hif_classifier, cl, 0); 584 #endif /* ALTQ3_COMPAT */ 585 586 if (!qempty(cl->cl_q)) 587 hfsc_purgeq(cl); 588 589 if (cl->cl_parent == NULL) { 590 /* this is root class */ 591 } else { 592 struct hfsc_class *p = cl->cl_parent->cl_children; 593 594 if (p == cl) 595 cl->cl_parent->cl_children = cl->cl_siblings; 596 else do { 597 if (p->cl_siblings == cl) { 598 p->cl_siblings = cl->cl_siblings; 599 break; 600 } 601 } while ((p = p->cl_siblings) != NULL); 602 ASSERT(p != NULL); 603 } 604 605 for (i = 0; i < HFSC_MAX_CLASSES; i++) 606 if (cl->cl_hif->hif_class_tbl[i] == cl) { 607 cl->cl_hif->hif_class_tbl[i] = NULL; 608 break; 609 } 610 611 cl->cl_hif->hif_classes--; 612 IFQ_UNLOCK(cl->cl_hif->hif_ifq); 613 splx(s); 614 615 if (cl->cl_red != NULL) { 616 #ifdef ALTQ_RIO 617 if (q_is_rio(cl->cl_q)) 618 rio_destroy((rio_t *)cl->cl_red); 619 #endif 620 #ifdef ALTQ_RED 621 if (q_is_red(cl->cl_q)) 622 red_destroy(cl->cl_red); 623 #endif 624 #ifdef ALTQ_CODEL 625 if (q_is_codel(cl->cl_q)) 626 codel_destroy(cl->cl_codel); 627 #endif 628 } 629 630 IFQ_LOCK(cl->cl_hif->hif_ifq); 631 if (cl == cl->cl_hif->hif_rootclass) 632 cl->cl_hif->hif_rootclass = NULL; 633 if (cl == cl->cl_hif->hif_defaultclass) 634 cl->cl_hif->hif_defaultclass = NULL; 635 IFQ_UNLOCK(cl->cl_hif->hif_ifq); 636 637 if (cl->cl_usc != NULL) 638 free(cl->cl_usc, M_DEVBUF); 639 if (cl->cl_fsc != NULL) 640 free(cl->cl_fsc, M_DEVBUF); 641 if (cl->cl_rsc != NULL) 642 free(cl->cl_rsc, M_DEVBUF); 643 free(cl->cl_q, M_DEVBUF); 644 free(cl, M_DEVBUF); 645 646 return (0); 647 } 648 649 /* 650 * hfsc_nextclass returns the next class in the tree. 651 * usage: 652 * for (cl = hif->hif_rootclass; cl != NULL; cl = hfsc_nextclass(cl)) 653 * do_something; 654 */ 655 static struct hfsc_class * 656 hfsc_nextclass(struct hfsc_class *cl) 657 { 658 if (cl->cl_children != NULL) 659 cl = cl->cl_children; 660 else if (cl->cl_siblings != NULL) 661 cl = cl->cl_siblings; 662 else { 663 while ((cl = cl->cl_parent) != NULL) 664 if (cl->cl_siblings) { 665 cl = cl->cl_siblings; 666 break; 667 } 668 } 669 670 return (cl); 671 } 672 673 /* 674 * hfsc_enqueue is an enqueue function to be registered to 675 * (*altq_enqueue) in struct ifaltq. 676 */ 677 static int 678 hfsc_enqueue(struct ifaltq *ifq, struct mbuf *m, struct altq_pktattr *pktattr) 679 { 680 struct hfsc_if *hif = (struct hfsc_if *)ifq->altq_disc; 681 struct hfsc_class *cl; 682 struct pf_mtag *t; 683 int len; 684 685 IFQ_LOCK_ASSERT(ifq); 686 687 /* grab class set by classifier */ 688 if ((m->m_flags & M_PKTHDR) == 0) { 689 /* should not happen */ 690 printf("altq: packet for %s does not have pkthdr\n", 691 ifq->altq_ifp->if_xname); 692 m_freem(m); 693 return (ENOBUFS); 694 } 695 cl = NULL; 696 if ((t = pf_find_mtag(m)) != NULL) 697 cl = clh_to_clp(hif, t->qid); 698 #ifdef ALTQ3_COMPAT 699 else if ((ifq->altq_flags & ALTQF_CLASSIFY) && pktattr != NULL) 700 cl = pktattr->pattr_class; 701 #endif 702 if (cl == NULL || is_a_parent_class(cl)) { 703 cl = hif->hif_defaultclass; 704 if (cl == NULL) { 705 m_freem(m); 706 return (ENOBUFS); 707 } 708 } 709 #ifdef ALTQ3_COMPAT 710 if (pktattr != NULL) 711 cl->cl_pktattr = pktattr; /* save proto hdr used by ECN */ 712 else 713 #endif 714 cl->cl_pktattr = NULL; 715 len = m_pktlen(m); 716 if (hfsc_addq(cl, m) != 0) { 717 /* drop occurred. mbuf was freed in hfsc_addq. */ 718 PKTCNTR_ADD(&cl->cl_stats.drop_cnt, len); 719 return (ENOBUFS); 720 } 721 IFQ_INC_LEN(ifq); 722 cl->cl_hif->hif_packets++; 723 724 /* successfully queued. */ 725 if (qlen(cl->cl_q) == 1) 726 set_active(cl, m_pktlen(m)); 727 728 return (0); 729 } 730 731 /* 732 * hfsc_dequeue is a dequeue function to be registered to 733 * (*altq_dequeue) in struct ifaltq. 734 * 735 * note: ALTDQ_POLL returns the next packet without removing the packet 736 * from the queue. ALTDQ_REMOVE is a normal dequeue operation. 737 * ALTDQ_REMOVE must return the same packet if called immediately 738 * after ALTDQ_POLL. 739 */ 740 static struct mbuf * 741 hfsc_dequeue(struct ifaltq *ifq, int op) 742 { 743 struct hfsc_if *hif = (struct hfsc_if *)ifq->altq_disc; 744 struct hfsc_class *cl; 745 struct mbuf *m; 746 int len, next_len; 747 int realtime = 0; 748 u_int64_t cur_time; 749 750 IFQ_LOCK_ASSERT(ifq); 751 752 if (hif->hif_packets == 0) 753 /* no packet in the tree */ 754 return (NULL); 755 756 cur_time = read_machclk(); 757 758 if (op == ALTDQ_REMOVE && hif->hif_pollcache != NULL) { 759 760 cl = hif->hif_pollcache; 761 hif->hif_pollcache = NULL; 762 /* check if the class was scheduled by real-time criteria */ 763 if (cl->cl_rsc != NULL) 764 realtime = (cl->cl_e <= cur_time); 765 } else { 766 /* 767 * if there are eligible classes, use real-time criteria. 768 * find the class with the minimum deadline among 769 * the eligible classes. 770 */ 771 if ((cl = hfsc_get_mindl(hif, cur_time)) 772 != NULL) { 773 realtime = 1; 774 } else { 775 #ifdef ALTQ_DEBUG 776 int fits = 0; 777 #endif 778 /* 779 * use link-sharing criteria 780 * get the class with the minimum vt in the hierarchy 781 */ 782 cl = hif->hif_rootclass; 783 while (is_a_parent_class(cl)) { 784 785 cl = actlist_firstfit(cl, cur_time); 786 if (cl == NULL) { 787 #ifdef ALTQ_DEBUG 788 if (fits > 0) 789 printf("%d fit but none found\n",fits); 790 #endif 791 return (NULL); 792 } 793 /* 794 * update parent's cl_cvtmin. 795 * don't update if the new vt is smaller. 796 */ 797 if (cl->cl_parent->cl_cvtmin < cl->cl_vt) 798 cl->cl_parent->cl_cvtmin = cl->cl_vt; 799 #ifdef ALTQ_DEBUG 800 fits++; 801 #endif 802 } 803 } 804 805 if (op == ALTDQ_POLL) { 806 hif->hif_pollcache = cl; 807 m = hfsc_pollq(cl); 808 return (m); 809 } 810 } 811 812 m = hfsc_getq(cl); 813 if (m == NULL) 814 panic("hfsc_dequeue:"); 815 len = m_pktlen(m); 816 cl->cl_hif->hif_packets--; 817 IFQ_DEC_LEN(ifq); 818 PKTCNTR_ADD(&cl->cl_stats.xmit_cnt, len); 819 820 update_vf(cl, len, cur_time); 821 if (realtime) 822 cl->cl_cumul += len; 823 824 if (!qempty(cl->cl_q)) { 825 if (cl->cl_rsc != NULL) { 826 /* update ed */ 827 next_len = m_pktlen(qhead(cl->cl_q)); 828 829 if (realtime) 830 update_ed(cl, next_len); 831 else 832 update_d(cl, next_len); 833 } 834 } else { 835 /* the class becomes passive */ 836 set_passive(cl); 837 } 838 839 return (m); 840 } 841 842 static int 843 hfsc_addq(struct hfsc_class *cl, struct mbuf *m) 844 { 845 846 #ifdef ALTQ_RIO 847 if (q_is_rio(cl->cl_q)) 848 return rio_addq((rio_t *)cl->cl_red, cl->cl_q, 849 m, cl->cl_pktattr); 850 #endif 851 #ifdef ALTQ_RED 852 if (q_is_red(cl->cl_q)) 853 return red_addq(cl->cl_red, cl->cl_q, m, cl->cl_pktattr); 854 #endif 855 #ifdef ALTQ_CODEL 856 if (q_is_codel(cl->cl_q)) 857 return codel_addq(cl->cl_codel, cl->cl_q, m); 858 #endif 859 if (qlen(cl->cl_q) >= qlimit(cl->cl_q)) { 860 m_freem(m); 861 return (-1); 862 } 863 864 if (cl->cl_flags & HFCF_CLEARDSCP) 865 write_dsfield(m, cl->cl_pktattr, 0); 866 867 _addq(cl->cl_q, m); 868 869 return (0); 870 } 871 872 static struct mbuf * 873 hfsc_getq(struct hfsc_class *cl) 874 { 875 #ifdef ALTQ_RIO 876 if (q_is_rio(cl->cl_q)) 877 return rio_getq((rio_t *)cl->cl_red, cl->cl_q); 878 #endif 879 #ifdef ALTQ_RED 880 if (q_is_red(cl->cl_q)) 881 return red_getq(cl->cl_red, cl->cl_q); 882 #endif 883 #ifdef ALTQ_CODEL 884 if (q_is_codel(cl->cl_q)) 885 return codel_getq(cl->cl_codel, cl->cl_q); 886 #endif 887 return _getq(cl->cl_q); 888 } 889 890 static struct mbuf * 891 hfsc_pollq(struct hfsc_class *cl) 892 { 893 return qhead(cl->cl_q); 894 } 895 896 static void 897 hfsc_purgeq(struct hfsc_class *cl) 898 { 899 struct mbuf *m; 900 901 if (qempty(cl->cl_q)) 902 return; 903 904 while ((m = _getq(cl->cl_q)) != NULL) { 905 PKTCNTR_ADD(&cl->cl_stats.drop_cnt, m_pktlen(m)); 906 m_freem(m); 907 cl->cl_hif->hif_packets--; 908 IFQ_DEC_LEN(cl->cl_hif->hif_ifq); 909 } 910 ASSERT(qlen(cl->cl_q) == 0); 911 912 update_vf(cl, 0, 0); /* remove cl from the actlist */ 913 set_passive(cl); 914 } 915 916 static void 917 set_active(struct hfsc_class *cl, int len) 918 { 919 if (cl->cl_rsc != NULL) 920 init_ed(cl, len); 921 if (cl->cl_fsc != NULL) 922 init_vf(cl, len); 923 924 cl->cl_stats.period++; 925 } 926 927 static void 928 set_passive(struct hfsc_class *cl) 929 { 930 if (cl->cl_rsc != NULL) 931 ellist_remove(cl); 932 933 /* 934 * actlist is now handled in update_vf() so that update_vf(cl, 0, 0) 935 * needs to be called explicitly to remove a class from actlist 936 */ 937 } 938 939 static void 940 init_ed(struct hfsc_class *cl, int next_len) 941 { 942 u_int64_t cur_time; 943 944 cur_time = read_machclk(); 945 946 /* update the deadline curve */ 947 rtsc_min(&cl->cl_deadline, cl->cl_rsc, cur_time, cl->cl_cumul); 948 949 /* 950 * update the eligible curve. 951 * for concave, it is equal to the deadline curve. 952 * for convex, it is a linear curve with slope m2. 953 */ 954 cl->cl_eligible = cl->cl_deadline; 955 if (cl->cl_rsc->sm1 <= cl->cl_rsc->sm2) { 956 cl->cl_eligible.dx = 0; 957 cl->cl_eligible.dy = 0; 958 } 959 960 /* compute e and d */ 961 cl->cl_e = rtsc_y2x(&cl->cl_eligible, cl->cl_cumul); 962 cl->cl_d = rtsc_y2x(&cl->cl_deadline, cl->cl_cumul + next_len); 963 964 ellist_insert(cl); 965 } 966 967 static void 968 update_ed(struct hfsc_class *cl, int next_len) 969 { 970 cl->cl_e = rtsc_y2x(&cl->cl_eligible, cl->cl_cumul); 971 cl->cl_d = rtsc_y2x(&cl->cl_deadline, cl->cl_cumul + next_len); 972 973 ellist_update(cl); 974 } 975 976 static void 977 update_d(struct hfsc_class *cl, int next_len) 978 { 979 cl->cl_d = rtsc_y2x(&cl->cl_deadline, cl->cl_cumul + next_len); 980 } 981 982 static void 983 init_vf(struct hfsc_class *cl, int len) 984 { 985 struct hfsc_class *max_cl, *p; 986 u_int64_t vt, f, cur_time; 987 int go_active; 988 989 cur_time = 0; 990 go_active = 1; 991 for ( ; cl->cl_parent != NULL; cl = cl->cl_parent) { 992 993 if (go_active && cl->cl_nactive++ == 0) 994 go_active = 1; 995 else 996 go_active = 0; 997 998 if (go_active) { 999 max_cl = TAILQ_LAST(&cl->cl_parent->cl_actc, acthead); 1000 if (max_cl != NULL) { 1001 /* 1002 * set vt to the average of the min and max 1003 * classes. if the parent's period didn't 1004 * change, don't decrease vt of the class. 1005 */ 1006 vt = max_cl->cl_vt; 1007 if (cl->cl_parent->cl_cvtmin != 0) 1008 vt = (cl->cl_parent->cl_cvtmin + vt)/2; 1009 1010 if (cl->cl_parent->cl_vtperiod != 1011 cl->cl_parentperiod || vt > cl->cl_vt) 1012 cl->cl_vt = vt; 1013 } else { 1014 /* 1015 * first child for a new parent backlog period. 1016 * add parent's cvtmax to vtoff of children 1017 * to make a new vt (vtoff + vt) larger than 1018 * the vt in the last period for all children. 1019 */ 1020 vt = cl->cl_parent->cl_cvtmax; 1021 for (p = cl->cl_parent->cl_children; p != NULL; 1022 p = p->cl_siblings) 1023 p->cl_vtoff += vt; 1024 cl->cl_vt = 0; 1025 cl->cl_parent->cl_cvtmax = 0; 1026 cl->cl_parent->cl_cvtmin = 0; 1027 } 1028 cl->cl_initvt = cl->cl_vt; 1029 1030 /* update the virtual curve */ 1031 vt = cl->cl_vt + cl->cl_vtoff; 1032 rtsc_min(&cl->cl_virtual, cl->cl_fsc, vt, cl->cl_total); 1033 if (cl->cl_virtual.x == vt) { 1034 cl->cl_virtual.x -= cl->cl_vtoff; 1035 cl->cl_vtoff = 0; 1036 } 1037 cl->cl_vtadj = 0; 1038 1039 cl->cl_vtperiod++; /* increment vt period */ 1040 cl->cl_parentperiod = cl->cl_parent->cl_vtperiod; 1041 if (cl->cl_parent->cl_nactive == 0) 1042 cl->cl_parentperiod++; 1043 cl->cl_f = 0; 1044 1045 actlist_insert(cl); 1046 1047 if (cl->cl_usc != NULL) { 1048 /* class has upper limit curve */ 1049 if (cur_time == 0) 1050 cur_time = read_machclk(); 1051 1052 /* update the ulimit curve */ 1053 rtsc_min(&cl->cl_ulimit, cl->cl_usc, cur_time, 1054 cl->cl_total); 1055 /* compute myf */ 1056 cl->cl_myf = rtsc_y2x(&cl->cl_ulimit, 1057 cl->cl_total); 1058 cl->cl_myfadj = 0; 1059 } 1060 } 1061 1062 if (cl->cl_myf > cl->cl_cfmin) 1063 f = cl->cl_myf; 1064 else 1065 f = cl->cl_cfmin; 1066 if (f != cl->cl_f) { 1067 cl->cl_f = f; 1068 update_cfmin(cl->cl_parent); 1069 } 1070 } 1071 } 1072 1073 static void 1074 update_vf(struct hfsc_class *cl, int len, u_int64_t cur_time) 1075 { 1076 u_int64_t f, myf_bound, delta; 1077 int go_passive; 1078 1079 go_passive = qempty(cl->cl_q); 1080 1081 for (; cl->cl_parent != NULL; cl = cl->cl_parent) { 1082 1083 cl->cl_total += len; 1084 1085 if (cl->cl_fsc == NULL || cl->cl_nactive == 0) 1086 continue; 1087 1088 if (go_passive && --cl->cl_nactive == 0) 1089 go_passive = 1; 1090 else 1091 go_passive = 0; 1092 1093 if (go_passive) { 1094 /* no more active child, going passive */ 1095 1096 /* update cvtmax of the parent class */ 1097 if (cl->cl_vt > cl->cl_parent->cl_cvtmax) 1098 cl->cl_parent->cl_cvtmax = cl->cl_vt; 1099 1100 /* remove this class from the vt list */ 1101 actlist_remove(cl); 1102 1103 update_cfmin(cl->cl_parent); 1104 1105 continue; 1106 } 1107 1108 /* 1109 * update vt and f 1110 */ 1111 cl->cl_vt = rtsc_y2x(&cl->cl_virtual, cl->cl_total) 1112 - cl->cl_vtoff + cl->cl_vtadj; 1113 1114 /* 1115 * if vt of the class is smaller than cvtmin, 1116 * the class was skipped in the past due to non-fit. 1117 * if so, we need to adjust vtadj. 1118 */ 1119 if (cl->cl_vt < cl->cl_parent->cl_cvtmin) { 1120 cl->cl_vtadj += cl->cl_parent->cl_cvtmin - cl->cl_vt; 1121 cl->cl_vt = cl->cl_parent->cl_cvtmin; 1122 } 1123 1124 /* update the vt list */ 1125 actlist_update(cl); 1126 1127 if (cl->cl_usc != NULL) { 1128 cl->cl_myf = cl->cl_myfadj 1129 + rtsc_y2x(&cl->cl_ulimit, cl->cl_total); 1130 1131 /* 1132 * if myf lags behind by more than one clock tick 1133 * from the current time, adjust myfadj to prevent 1134 * a rate-limited class from going greedy. 1135 * in a steady state under rate-limiting, myf 1136 * fluctuates within one clock tick. 1137 */ 1138 myf_bound = cur_time - machclk_per_tick; 1139 if (cl->cl_myf < myf_bound) { 1140 delta = cur_time - cl->cl_myf; 1141 cl->cl_myfadj += delta; 1142 cl->cl_myf += delta; 1143 } 1144 } 1145 1146 /* cl_f is max(cl_myf, cl_cfmin) */ 1147 if (cl->cl_myf > cl->cl_cfmin) 1148 f = cl->cl_myf; 1149 else 1150 f = cl->cl_cfmin; 1151 if (f != cl->cl_f) { 1152 cl->cl_f = f; 1153 update_cfmin(cl->cl_parent); 1154 } 1155 } 1156 } 1157 1158 static void 1159 update_cfmin(struct hfsc_class *cl) 1160 { 1161 struct hfsc_class *p; 1162 u_int64_t cfmin; 1163 1164 if (TAILQ_EMPTY(&cl->cl_actc)) { 1165 cl->cl_cfmin = 0; 1166 return; 1167 } 1168 cfmin = HT_INFINITY; 1169 TAILQ_FOREACH(p, &cl->cl_actc, cl_actlist) { 1170 if (p->cl_f == 0) { 1171 cl->cl_cfmin = 0; 1172 return; 1173 } 1174 if (p->cl_f < cfmin) 1175 cfmin = p->cl_f; 1176 } 1177 cl->cl_cfmin = cfmin; 1178 } 1179 1180 /* 1181 * TAILQ based ellist and actlist implementation 1182 * (ion wanted to make a calendar queue based implementation) 1183 */ 1184 /* 1185 * eligible list holds backlogged classes being sorted by their eligible times. 1186 * there is one eligible list per interface. 1187 */ 1188 1189 static void 1190 ellist_insert(struct hfsc_class *cl) 1191 { 1192 struct hfsc_if *hif = cl->cl_hif; 1193 struct hfsc_class *p; 1194 1195 /* check the last entry first */ 1196 if ((p = TAILQ_LAST(&hif->hif_eligible, elighead)) == NULL || 1197 p->cl_e <= cl->cl_e) { 1198 TAILQ_INSERT_TAIL(&hif->hif_eligible, cl, cl_ellist); 1199 return; 1200 } 1201 1202 TAILQ_FOREACH(p, &hif->hif_eligible, cl_ellist) { 1203 if (cl->cl_e < p->cl_e) { 1204 TAILQ_INSERT_BEFORE(p, cl, cl_ellist); 1205 return; 1206 } 1207 } 1208 ASSERT(0); /* should not reach here */ 1209 } 1210 1211 static void 1212 ellist_remove(struct hfsc_class *cl) 1213 { 1214 struct hfsc_if *hif = cl->cl_hif; 1215 1216 TAILQ_REMOVE(&hif->hif_eligible, cl, cl_ellist); 1217 } 1218 1219 static void 1220 ellist_update(struct hfsc_class *cl) 1221 { 1222 struct hfsc_if *hif = cl->cl_hif; 1223 struct hfsc_class *p, *last; 1224 1225 /* 1226 * the eligible time of a class increases monotonically. 1227 * if the next entry has a larger eligible time, nothing to do. 1228 */ 1229 p = TAILQ_NEXT(cl, cl_ellist); 1230 if (p == NULL || cl->cl_e <= p->cl_e) 1231 return; 1232 1233 /* check the last entry */ 1234 last = TAILQ_LAST(&hif->hif_eligible, elighead); 1235 ASSERT(last != NULL); 1236 if (last->cl_e <= cl->cl_e) { 1237 TAILQ_REMOVE(&hif->hif_eligible, cl, cl_ellist); 1238 TAILQ_INSERT_TAIL(&hif->hif_eligible, cl, cl_ellist); 1239 return; 1240 } 1241 1242 /* 1243 * the new position must be between the next entry 1244 * and the last entry 1245 */ 1246 while ((p = TAILQ_NEXT(p, cl_ellist)) != NULL) { 1247 if (cl->cl_e < p->cl_e) { 1248 TAILQ_REMOVE(&hif->hif_eligible, cl, cl_ellist); 1249 TAILQ_INSERT_BEFORE(p, cl, cl_ellist); 1250 return; 1251 } 1252 } 1253 ASSERT(0); /* should not reach here */ 1254 } 1255 1256 /* find the class with the minimum deadline among the eligible classes */ 1257 struct hfsc_class * 1258 hfsc_get_mindl(struct hfsc_if *hif, u_int64_t cur_time) 1259 { 1260 struct hfsc_class *p, *cl = NULL; 1261 1262 TAILQ_FOREACH(p, &hif->hif_eligible, cl_ellist) { 1263 if (p->cl_e > cur_time) 1264 break; 1265 if (cl == NULL || p->cl_d < cl->cl_d) 1266 cl = p; 1267 } 1268 return (cl); 1269 } 1270 1271 /* 1272 * active children list holds backlogged child classes being sorted 1273 * by their virtual time. 1274 * each intermediate class has one active children list. 1275 */ 1276 1277 static void 1278 actlist_insert(struct hfsc_class *cl) 1279 { 1280 struct hfsc_class *p; 1281 1282 /* check the last entry first */ 1283 if ((p = TAILQ_LAST(&cl->cl_parent->cl_actc, acthead)) == NULL 1284 || p->cl_vt <= cl->cl_vt) { 1285 TAILQ_INSERT_TAIL(&cl->cl_parent->cl_actc, cl, cl_actlist); 1286 return; 1287 } 1288 1289 TAILQ_FOREACH(p, &cl->cl_parent->cl_actc, cl_actlist) { 1290 if (cl->cl_vt < p->cl_vt) { 1291 TAILQ_INSERT_BEFORE(p, cl, cl_actlist); 1292 return; 1293 } 1294 } 1295 ASSERT(0); /* should not reach here */ 1296 } 1297 1298 static void 1299 actlist_remove(struct hfsc_class *cl) 1300 { 1301 TAILQ_REMOVE(&cl->cl_parent->cl_actc, cl, cl_actlist); 1302 } 1303 1304 static void 1305 actlist_update(struct hfsc_class *cl) 1306 { 1307 struct hfsc_class *p, *last; 1308 1309 /* 1310 * the virtual time of a class increases monotonically during its 1311 * backlogged period. 1312 * if the next entry has a larger virtual time, nothing to do. 1313 */ 1314 p = TAILQ_NEXT(cl, cl_actlist); 1315 if (p == NULL || cl->cl_vt < p->cl_vt) 1316 return; 1317 1318 /* check the last entry */ 1319 last = TAILQ_LAST(&cl->cl_parent->cl_actc, acthead); 1320 ASSERT(last != NULL); 1321 if (last->cl_vt <= cl->cl_vt) { 1322 TAILQ_REMOVE(&cl->cl_parent->cl_actc, cl, cl_actlist); 1323 TAILQ_INSERT_TAIL(&cl->cl_parent->cl_actc, cl, cl_actlist); 1324 return; 1325 } 1326 1327 /* 1328 * the new position must be between the next entry 1329 * and the last entry 1330 */ 1331 while ((p = TAILQ_NEXT(p, cl_actlist)) != NULL) { 1332 if (cl->cl_vt < p->cl_vt) { 1333 TAILQ_REMOVE(&cl->cl_parent->cl_actc, cl, cl_actlist); 1334 TAILQ_INSERT_BEFORE(p, cl, cl_actlist); 1335 return; 1336 } 1337 } 1338 ASSERT(0); /* should not reach here */ 1339 } 1340 1341 static struct hfsc_class * 1342 actlist_firstfit(struct hfsc_class *cl, u_int64_t cur_time) 1343 { 1344 struct hfsc_class *p; 1345 1346 TAILQ_FOREACH(p, &cl->cl_actc, cl_actlist) { 1347 if (p->cl_f <= cur_time) 1348 return (p); 1349 } 1350 return (NULL); 1351 } 1352 1353 /* 1354 * service curve support functions 1355 * 1356 * external service curve parameters 1357 * m: bits/sec 1358 * d: msec 1359 * internal service curve parameters 1360 * sm: (bytes/tsc_interval) << SM_SHIFT 1361 * ism: (tsc_count/byte) << ISM_SHIFT 1362 * dx: tsc_count 1363 * 1364 * SM_SHIFT and ISM_SHIFT are scaled in order to keep effective digits. 1365 * we should be able to handle 100K-1Gbps linkspeed with 200Hz-1GHz CPU 1366 * speed. SM_SHIFT and ISM_SHIFT are selected to have at least 3 effective 1367 * digits in decimal using the following table. 1368 * 1369 * bits/sec 100Kbps 1Mbps 10Mbps 100Mbps 1Gbps 1370 * ----------+------------------------------------------------------- 1371 * bytes/nsec 12.5e-6 125e-6 1250e-6 12500e-6 125000e-6 1372 * sm(500MHz) 25.0e-6 250e-6 2500e-6 25000e-6 250000e-6 1373 * sm(200MHz) 62.5e-6 625e-6 6250e-6 62500e-6 625000e-6 1374 * 1375 * nsec/byte 80000 8000 800 80 8 1376 * ism(500MHz) 40000 4000 400 40 4 1377 * ism(200MHz) 16000 1600 160 16 1.6 1378 */ 1379 #define SM_SHIFT 24 1380 #define ISM_SHIFT 10 1381 1382 #define SM_MASK ((1LL << SM_SHIFT) - 1) 1383 #define ISM_MASK ((1LL << ISM_SHIFT) - 1) 1384 1385 static __inline u_int64_t 1386 seg_x2y(u_int64_t x, u_int64_t sm) 1387 { 1388 u_int64_t y; 1389 1390 /* 1391 * compute 1392 * y = x * sm >> SM_SHIFT 1393 * but divide it for the upper and lower bits to avoid overflow 1394 */ 1395 y = (x >> SM_SHIFT) * sm + (((x & SM_MASK) * sm) >> SM_SHIFT); 1396 return (y); 1397 } 1398 1399 static __inline u_int64_t 1400 seg_y2x(u_int64_t y, u_int64_t ism) 1401 { 1402 u_int64_t x; 1403 1404 if (y == 0) 1405 x = 0; 1406 else if (ism == HT_INFINITY) 1407 x = HT_INFINITY; 1408 else { 1409 x = (y >> ISM_SHIFT) * ism 1410 + (((y & ISM_MASK) * ism) >> ISM_SHIFT); 1411 } 1412 return (x); 1413 } 1414 1415 static __inline u_int64_t 1416 m2sm(u_int m) 1417 { 1418 u_int64_t sm; 1419 1420 sm = ((u_int64_t)m << SM_SHIFT) / 8 / machclk_freq; 1421 return (sm); 1422 } 1423 1424 static __inline u_int64_t 1425 m2ism(u_int m) 1426 { 1427 u_int64_t ism; 1428 1429 if (m == 0) 1430 ism = HT_INFINITY; 1431 else 1432 ism = ((u_int64_t)machclk_freq << ISM_SHIFT) * 8 / m; 1433 return (ism); 1434 } 1435 1436 static __inline u_int64_t 1437 d2dx(u_int d) 1438 { 1439 u_int64_t dx; 1440 1441 dx = ((u_int64_t)d * machclk_freq) / 1000; 1442 return (dx); 1443 } 1444 1445 static u_int 1446 sm2m(u_int64_t sm) 1447 { 1448 u_int64_t m; 1449 1450 m = (sm * 8 * machclk_freq) >> SM_SHIFT; 1451 return ((u_int)m); 1452 } 1453 1454 static u_int 1455 dx2d(u_int64_t dx) 1456 { 1457 u_int64_t d; 1458 1459 d = dx * 1000 / machclk_freq; 1460 return ((u_int)d); 1461 } 1462 1463 static void 1464 sc2isc(struct service_curve *sc, struct internal_sc *isc) 1465 { 1466 isc->sm1 = m2sm(sc->m1); 1467 isc->ism1 = m2ism(sc->m1); 1468 isc->dx = d2dx(sc->d); 1469 isc->dy = seg_x2y(isc->dx, isc->sm1); 1470 isc->sm2 = m2sm(sc->m2); 1471 isc->ism2 = m2ism(sc->m2); 1472 } 1473 1474 /* 1475 * initialize the runtime service curve with the given internal 1476 * service curve starting at (x, y). 1477 */ 1478 static void 1479 rtsc_init(struct runtime_sc *rtsc, struct internal_sc * isc, u_int64_t x, 1480 u_int64_t y) 1481 { 1482 rtsc->x = x; 1483 rtsc->y = y; 1484 rtsc->sm1 = isc->sm1; 1485 rtsc->ism1 = isc->ism1; 1486 rtsc->dx = isc->dx; 1487 rtsc->dy = isc->dy; 1488 rtsc->sm2 = isc->sm2; 1489 rtsc->ism2 = isc->ism2; 1490 } 1491 1492 /* 1493 * calculate the y-projection of the runtime service curve by the 1494 * given x-projection value 1495 */ 1496 static u_int64_t 1497 rtsc_y2x(struct runtime_sc *rtsc, u_int64_t y) 1498 { 1499 u_int64_t x; 1500 1501 if (y < rtsc->y) 1502 x = rtsc->x; 1503 else if (y <= rtsc->y + rtsc->dy) { 1504 /* x belongs to the 1st segment */ 1505 if (rtsc->dy == 0) 1506 x = rtsc->x + rtsc->dx; 1507 else 1508 x = rtsc->x + seg_y2x(y - rtsc->y, rtsc->ism1); 1509 } else { 1510 /* x belongs to the 2nd segment */ 1511 x = rtsc->x + rtsc->dx 1512 + seg_y2x(y - rtsc->y - rtsc->dy, rtsc->ism2); 1513 } 1514 return (x); 1515 } 1516 1517 static u_int64_t 1518 rtsc_x2y(struct runtime_sc *rtsc, u_int64_t x) 1519 { 1520 u_int64_t y; 1521 1522 if (x <= rtsc->x) 1523 y = rtsc->y; 1524 else if (x <= rtsc->x + rtsc->dx) 1525 /* y belongs to the 1st segment */ 1526 y = rtsc->y + seg_x2y(x - rtsc->x, rtsc->sm1); 1527 else 1528 /* y belongs to the 2nd segment */ 1529 y = rtsc->y + rtsc->dy 1530 + seg_x2y(x - rtsc->x - rtsc->dx, rtsc->sm2); 1531 return (y); 1532 } 1533 1534 /* 1535 * update the runtime service curve by taking the minimum of the current 1536 * runtime service curve and the service curve starting at (x, y). 1537 */ 1538 static void 1539 rtsc_min(struct runtime_sc *rtsc, struct internal_sc *isc, u_int64_t x, 1540 u_int64_t y) 1541 { 1542 u_int64_t y1, y2, dx, dy; 1543 1544 if (isc->sm1 <= isc->sm2) { 1545 /* service curve is convex */ 1546 y1 = rtsc_x2y(rtsc, x); 1547 if (y1 < y) 1548 /* the current rtsc is smaller */ 1549 return; 1550 rtsc->x = x; 1551 rtsc->y = y; 1552 return; 1553 } 1554 1555 /* 1556 * service curve is concave 1557 * compute the two y values of the current rtsc 1558 * y1: at x 1559 * y2: at (x + dx) 1560 */ 1561 y1 = rtsc_x2y(rtsc, x); 1562 if (y1 <= y) { 1563 /* rtsc is below isc, no change to rtsc */ 1564 return; 1565 } 1566 1567 y2 = rtsc_x2y(rtsc, x + isc->dx); 1568 if (y2 >= y + isc->dy) { 1569 /* rtsc is above isc, replace rtsc by isc */ 1570 rtsc->x = x; 1571 rtsc->y = y; 1572 rtsc->dx = isc->dx; 1573 rtsc->dy = isc->dy; 1574 return; 1575 } 1576 1577 /* 1578 * the two curves intersect 1579 * compute the offsets (dx, dy) using the reverse 1580 * function of seg_x2y() 1581 * seg_x2y(dx, sm1) == seg_x2y(dx, sm2) + (y1 - y) 1582 */ 1583 dx = ((y1 - y) << SM_SHIFT) / (isc->sm1 - isc->sm2); 1584 /* 1585 * check if (x, y1) belongs to the 1st segment of rtsc. 1586 * if so, add the offset. 1587 */ 1588 if (rtsc->x + rtsc->dx > x) 1589 dx += rtsc->x + rtsc->dx - x; 1590 dy = seg_x2y(dx, isc->sm1); 1591 1592 rtsc->x = x; 1593 rtsc->y = y; 1594 rtsc->dx = dx; 1595 rtsc->dy = dy; 1596 return; 1597 } 1598 1599 static void 1600 get_class_stats(struct hfsc_classstats *sp, struct hfsc_class *cl) 1601 { 1602 sp->class_id = cl->cl_id; 1603 sp->class_handle = cl->cl_handle; 1604 1605 if (cl->cl_rsc != NULL) { 1606 sp->rsc.m1 = sm2m(cl->cl_rsc->sm1); 1607 sp->rsc.d = dx2d(cl->cl_rsc->dx); 1608 sp->rsc.m2 = sm2m(cl->cl_rsc->sm2); 1609 } else { 1610 sp->rsc.m1 = 0; 1611 sp->rsc.d = 0; 1612 sp->rsc.m2 = 0; 1613 } 1614 if (cl->cl_fsc != NULL) { 1615 sp->fsc.m1 = sm2m(cl->cl_fsc->sm1); 1616 sp->fsc.d = dx2d(cl->cl_fsc->dx); 1617 sp->fsc.m2 = sm2m(cl->cl_fsc->sm2); 1618 } else { 1619 sp->fsc.m1 = 0; 1620 sp->fsc.d = 0; 1621 sp->fsc.m2 = 0; 1622 } 1623 if (cl->cl_usc != NULL) { 1624 sp->usc.m1 = sm2m(cl->cl_usc->sm1); 1625 sp->usc.d = dx2d(cl->cl_usc->dx); 1626 sp->usc.m2 = sm2m(cl->cl_usc->sm2); 1627 } else { 1628 sp->usc.m1 = 0; 1629 sp->usc.d = 0; 1630 sp->usc.m2 = 0; 1631 } 1632 1633 sp->total = cl->cl_total; 1634 sp->cumul = cl->cl_cumul; 1635 1636 sp->d = cl->cl_d; 1637 sp->e = cl->cl_e; 1638 sp->vt = cl->cl_vt; 1639 sp->f = cl->cl_f; 1640 1641 sp->initvt = cl->cl_initvt; 1642 sp->vtperiod = cl->cl_vtperiod; 1643 sp->parentperiod = cl->cl_parentperiod; 1644 sp->nactive = cl->cl_nactive; 1645 sp->vtoff = cl->cl_vtoff; 1646 sp->cvtmax = cl->cl_cvtmax; 1647 sp->myf = cl->cl_myf; 1648 sp->cfmin = cl->cl_cfmin; 1649 sp->cvtmin = cl->cl_cvtmin; 1650 sp->myfadj = cl->cl_myfadj; 1651 sp->vtadj = cl->cl_vtadj; 1652 1653 sp->cur_time = read_machclk(); 1654 sp->machclk_freq = machclk_freq; 1655 1656 sp->qlength = qlen(cl->cl_q); 1657 sp->qlimit = qlimit(cl->cl_q); 1658 sp->xmit_cnt = cl->cl_stats.xmit_cnt; 1659 sp->drop_cnt = cl->cl_stats.drop_cnt; 1660 sp->period = cl->cl_stats.period; 1661 1662 sp->qtype = qtype(cl->cl_q); 1663 #ifdef ALTQ_RED 1664 if (q_is_red(cl->cl_q)) 1665 red_getstats(cl->cl_red, &sp->red[0]); 1666 #endif 1667 #ifdef ALTQ_RIO 1668 if (q_is_rio(cl->cl_q)) 1669 rio_getstats((rio_t *)cl->cl_red, &sp->red[0]); 1670 #endif 1671 #ifdef ALTQ_CODEL 1672 if (q_is_codel(cl->cl_q)) 1673 codel_getstats(cl->cl_codel, &sp->codel); 1674 #endif 1675 } 1676 1677 /* convert a class handle to the corresponding class pointer */ 1678 static struct hfsc_class * 1679 clh_to_clp(struct hfsc_if *hif, u_int32_t chandle) 1680 { 1681 int i; 1682 struct hfsc_class *cl; 1683 1684 if (chandle == 0) 1685 return (NULL); 1686 /* 1687 * first, try optimistically the slot matching the lower bits of 1688 * the handle. if it fails, do the linear table search. 1689 */ 1690 i = chandle % HFSC_MAX_CLASSES; 1691 if ((cl = hif->hif_class_tbl[i]) != NULL && cl->cl_handle == chandle) 1692 return (cl); 1693 for (i = 0; i < HFSC_MAX_CLASSES; i++) 1694 if ((cl = hif->hif_class_tbl[i]) != NULL && 1695 cl->cl_handle == chandle) 1696 return (cl); 1697 return (NULL); 1698 } 1699 1700 #ifdef ALTQ3_COMPAT 1701 static struct hfsc_if * 1702 hfsc_attach(ifq, bandwidth) 1703 struct ifaltq *ifq; 1704 u_int bandwidth; 1705 { 1706 struct hfsc_if *hif; 1707 1708 hif = malloc(sizeof(struct hfsc_if), M_DEVBUF, M_WAITOK); 1709 if (hif == NULL) 1710 return (NULL); 1711 bzero(hif, sizeof(struct hfsc_if)); 1712 1713 hif->hif_eligible = ellist_alloc(); 1714 if (hif->hif_eligible == NULL) { 1715 free(hif, M_DEVBUF); 1716 return NULL; 1717 } 1718 1719 hif->hif_ifq = ifq; 1720 1721 /* add this state to the hfsc list */ 1722 hif->hif_next = hif_list; 1723 hif_list = hif; 1724 1725 return (hif); 1726 } 1727 1728 static int 1729 hfsc_detach(hif) 1730 struct hfsc_if *hif; 1731 { 1732 (void)hfsc_clear_interface(hif); 1733 (void)hfsc_class_destroy(hif->hif_rootclass); 1734 1735 /* remove this interface from the hif list */ 1736 if (hif_list == hif) 1737 hif_list = hif->hif_next; 1738 else { 1739 struct hfsc_if *h; 1740 1741 for (h = hif_list; h != NULL; h = h->hif_next) 1742 if (h->hif_next == hif) { 1743 h->hif_next = hif->hif_next; 1744 break; 1745 } 1746 ASSERT(h != NULL); 1747 } 1748 1749 ellist_destroy(hif->hif_eligible); 1750 1751 free(hif, M_DEVBUF); 1752 1753 return (0); 1754 } 1755 1756 static int 1757 hfsc_class_modify(cl, rsc, fsc, usc) 1758 struct hfsc_class *cl; 1759 struct service_curve *rsc, *fsc, *usc; 1760 { 1761 struct internal_sc *rsc_tmp, *fsc_tmp, *usc_tmp; 1762 u_int64_t cur_time; 1763 int s; 1764 1765 rsc_tmp = fsc_tmp = usc_tmp = NULL; 1766 if (rsc != NULL && (rsc->m1 != 0 || rsc->m2 != 0) && 1767 cl->cl_rsc == NULL) { 1768 rsc_tmp = malloc(sizeof(struct internal_sc), 1769 M_DEVBUF, M_WAITOK); 1770 if (rsc_tmp == NULL) 1771 return (ENOMEM); 1772 } 1773 if (fsc != NULL && (fsc->m1 != 0 || fsc->m2 != 0) && 1774 cl->cl_fsc == NULL) { 1775 fsc_tmp = malloc(sizeof(struct internal_sc), 1776 M_DEVBUF, M_WAITOK); 1777 if (fsc_tmp == NULL) { 1778 free(rsc_tmp); 1779 return (ENOMEM); 1780 } 1781 } 1782 if (usc != NULL && (usc->m1 != 0 || usc->m2 != 0) && 1783 cl->cl_usc == NULL) { 1784 usc_tmp = malloc(sizeof(struct internal_sc), 1785 M_DEVBUF, M_WAITOK); 1786 if (usc_tmp == NULL) { 1787 free(rsc_tmp); 1788 free(fsc_tmp); 1789 return (ENOMEM); 1790 } 1791 } 1792 1793 cur_time = read_machclk(); 1794 s = splnet(); 1795 IFQ_LOCK(cl->cl_hif->hif_ifq); 1796 1797 if (rsc != NULL) { 1798 if (rsc->m1 == 0 && rsc->m2 == 0) { 1799 if (cl->cl_rsc != NULL) { 1800 if (!qempty(cl->cl_q)) 1801 hfsc_purgeq(cl); 1802 free(cl->cl_rsc, M_DEVBUF); 1803 cl->cl_rsc = NULL; 1804 } 1805 } else { 1806 if (cl->cl_rsc == NULL) 1807 cl->cl_rsc = rsc_tmp; 1808 sc2isc(rsc, cl->cl_rsc); 1809 rtsc_init(&cl->cl_deadline, cl->cl_rsc, cur_time, 1810 cl->cl_cumul); 1811 cl->cl_eligible = cl->cl_deadline; 1812 if (cl->cl_rsc->sm1 <= cl->cl_rsc->sm2) { 1813 cl->cl_eligible.dx = 0; 1814 cl->cl_eligible.dy = 0; 1815 } 1816 } 1817 } 1818 1819 if (fsc != NULL) { 1820 if (fsc->m1 == 0 && fsc->m2 == 0) { 1821 if (cl->cl_fsc != NULL) { 1822 if (!qempty(cl->cl_q)) 1823 hfsc_purgeq(cl); 1824 free(cl->cl_fsc, M_DEVBUF); 1825 cl->cl_fsc = NULL; 1826 } 1827 } else { 1828 if (cl->cl_fsc == NULL) 1829 cl->cl_fsc = fsc_tmp; 1830 sc2isc(fsc, cl->cl_fsc); 1831 rtsc_init(&cl->cl_virtual, cl->cl_fsc, cl->cl_vt, 1832 cl->cl_total); 1833 } 1834 } 1835 1836 if (usc != NULL) { 1837 if (usc->m1 == 0 && usc->m2 == 0) { 1838 if (cl->cl_usc != NULL) { 1839 free(cl->cl_usc, M_DEVBUF); 1840 cl->cl_usc = NULL; 1841 cl->cl_myf = 0; 1842 } 1843 } else { 1844 if (cl->cl_usc == NULL) 1845 cl->cl_usc = usc_tmp; 1846 sc2isc(usc, cl->cl_usc); 1847 rtsc_init(&cl->cl_ulimit, cl->cl_usc, cur_time, 1848 cl->cl_total); 1849 } 1850 } 1851 1852 if (!qempty(cl->cl_q)) { 1853 if (cl->cl_rsc != NULL) 1854 update_ed(cl, m_pktlen(qhead(cl->cl_q))); 1855 if (cl->cl_fsc != NULL) 1856 update_vf(cl, 0, cur_time); 1857 /* is this enough? */ 1858 } 1859 1860 IFQ_UNLOCK(cl->cl_hif->hif_ifq); 1861 splx(s); 1862 1863 return (0); 1864 } 1865 1866 /* 1867 * hfsc device interface 1868 */ 1869 int 1870 hfscopen(dev, flag, fmt, p) 1871 dev_t dev; 1872 int flag, fmt; 1873 #if (__FreeBSD_version > 500000) 1874 struct thread *p; 1875 #else 1876 struct proc *p; 1877 #endif 1878 { 1879 if (machclk_freq == 0) 1880 init_machclk(); 1881 1882 if (machclk_freq == 0) { 1883 printf("hfsc: no cpu clock available!\n"); 1884 return (ENXIO); 1885 } 1886 1887 /* everything will be done when the queueing scheme is attached. */ 1888 return 0; 1889 } 1890 1891 int 1892 hfscclose(dev, flag, fmt, p) 1893 dev_t dev; 1894 int flag, fmt; 1895 #if (__FreeBSD_version > 500000) 1896 struct thread *p; 1897 #else 1898 struct proc *p; 1899 #endif 1900 { 1901 struct hfsc_if *hif; 1902 int err, error = 0; 1903 1904 while ((hif = hif_list) != NULL) { 1905 /* destroy all */ 1906 if (ALTQ_IS_ENABLED(hif->hif_ifq)) 1907 altq_disable(hif->hif_ifq); 1908 1909 err = altq_detach(hif->hif_ifq); 1910 if (err == 0) 1911 err = hfsc_detach(hif); 1912 if (err != 0 && error == 0) 1913 error = err; 1914 } 1915 1916 return error; 1917 } 1918 1919 int 1920 hfscioctl(dev, cmd, addr, flag, p) 1921 dev_t dev; 1922 ioctlcmd_t cmd; 1923 caddr_t addr; 1924 int flag; 1925 #if (__FreeBSD_version > 500000) 1926 struct thread *p; 1927 #else 1928 struct proc *p; 1929 #endif 1930 { 1931 struct hfsc_if *hif; 1932 struct hfsc_interface *ifacep; 1933 int error = 0; 1934 1935 /* check super-user privilege */ 1936 switch (cmd) { 1937 case HFSC_GETSTATS: 1938 break; 1939 default: 1940 #if (__FreeBSD_version > 700000) 1941 if ((error = priv_check(p, PRIV_ALTQ_MANAGE)) != 0) 1942 return (error); 1943 #elsif (__FreeBSD_version > 400000) 1944 if ((error = suser(p)) != 0) 1945 return (error); 1946 #else 1947 if ((error = suser(p->p_ucred, &p->p_acflag)) != 0) 1948 return (error); 1949 #endif 1950 break; 1951 } 1952 1953 switch (cmd) { 1954 1955 case HFSC_IF_ATTACH: 1956 error = hfsccmd_if_attach((struct hfsc_attach *)addr); 1957 break; 1958 1959 case HFSC_IF_DETACH: 1960 error = hfsccmd_if_detach((struct hfsc_interface *)addr); 1961 break; 1962 1963 case HFSC_ENABLE: 1964 case HFSC_DISABLE: 1965 case HFSC_CLEAR_HIERARCHY: 1966 ifacep = (struct hfsc_interface *)addr; 1967 if ((hif = altq_lookup(ifacep->hfsc_ifname, 1968 ALTQT_HFSC)) == NULL) { 1969 error = EBADF; 1970 break; 1971 } 1972 1973 switch (cmd) { 1974 1975 case HFSC_ENABLE: 1976 if (hif->hif_defaultclass == NULL) { 1977 #ifdef ALTQ_DEBUG 1978 printf("hfsc: no default class\n"); 1979 #endif 1980 error = EINVAL; 1981 break; 1982 } 1983 error = altq_enable(hif->hif_ifq); 1984 break; 1985 1986 case HFSC_DISABLE: 1987 error = altq_disable(hif->hif_ifq); 1988 break; 1989 1990 case HFSC_CLEAR_HIERARCHY: 1991 hfsc_clear_interface(hif); 1992 break; 1993 } 1994 break; 1995 1996 case HFSC_ADD_CLASS: 1997 error = hfsccmd_add_class((struct hfsc_add_class *)addr); 1998 break; 1999 2000 case HFSC_DEL_CLASS: 2001 error = hfsccmd_delete_class((struct hfsc_delete_class *)addr); 2002 break; 2003 2004 case HFSC_MOD_CLASS: 2005 error = hfsccmd_modify_class((struct hfsc_modify_class *)addr); 2006 break; 2007 2008 case HFSC_ADD_FILTER: 2009 error = hfsccmd_add_filter((struct hfsc_add_filter *)addr); 2010 break; 2011 2012 case HFSC_DEL_FILTER: 2013 error = hfsccmd_delete_filter((struct hfsc_delete_filter *)addr); 2014 break; 2015 2016 case HFSC_GETSTATS: 2017 error = hfsccmd_class_stats((struct hfsc_class_stats *)addr); 2018 break; 2019 2020 default: 2021 error = EINVAL; 2022 break; 2023 } 2024 return error; 2025 } 2026 2027 static int 2028 hfsccmd_if_attach(ap) 2029 struct hfsc_attach *ap; 2030 { 2031 struct hfsc_if *hif; 2032 struct ifnet *ifp; 2033 int error; 2034 2035 if ((ifp = ifunit(ap->iface.hfsc_ifname)) == NULL) 2036 return (ENXIO); 2037 2038 if ((hif = hfsc_attach(&ifp->if_snd, ap->bandwidth)) == NULL) 2039 return (ENOMEM); 2040 2041 /* 2042 * set HFSC to this ifnet structure. 2043 */ 2044 if ((error = altq_attach(&ifp->if_snd, ALTQT_HFSC, hif, 2045 hfsc_enqueue, hfsc_dequeue, hfsc_request, 2046 &hif->hif_classifier, acc_classify)) != 0) 2047 (void)hfsc_detach(hif); 2048 2049 return (error); 2050 } 2051 2052 static int 2053 hfsccmd_if_detach(ap) 2054 struct hfsc_interface *ap; 2055 { 2056 struct hfsc_if *hif; 2057 int error; 2058 2059 if ((hif = altq_lookup(ap->hfsc_ifname, ALTQT_HFSC)) == NULL) 2060 return (EBADF); 2061 2062 if (ALTQ_IS_ENABLED(hif->hif_ifq)) 2063 altq_disable(hif->hif_ifq); 2064 2065 if ((error = altq_detach(hif->hif_ifq))) 2066 return (error); 2067 2068 return hfsc_detach(hif); 2069 } 2070 2071 static int 2072 hfsccmd_add_class(ap) 2073 struct hfsc_add_class *ap; 2074 { 2075 struct hfsc_if *hif; 2076 struct hfsc_class *cl, *parent; 2077 int i; 2078 2079 if ((hif = altq_lookup(ap->iface.hfsc_ifname, ALTQT_HFSC)) == NULL) 2080 return (EBADF); 2081 2082 if (ap->parent_handle == HFSC_NULLCLASS_HANDLE && 2083 hif->hif_rootclass == NULL) 2084 parent = NULL; 2085 else if ((parent = clh_to_clp(hif, ap->parent_handle)) == NULL) 2086 return (EINVAL); 2087 2088 /* assign a class handle (use a free slot number for now) */ 2089 for (i = 1; i < HFSC_MAX_CLASSES; i++) 2090 if (hif->hif_class_tbl[i] == NULL) 2091 break; 2092 if (i == HFSC_MAX_CLASSES) 2093 return (EBUSY); 2094 2095 if ((cl = hfsc_class_create(hif, &ap->service_curve, NULL, NULL, 2096 parent, ap->qlimit, ap->flags, i)) == NULL) 2097 return (ENOMEM); 2098 2099 /* return a class handle to the user */ 2100 ap->class_handle = i; 2101 2102 return (0); 2103 } 2104 2105 static int 2106 hfsccmd_delete_class(ap) 2107 struct hfsc_delete_class *ap; 2108 { 2109 struct hfsc_if *hif; 2110 struct hfsc_class *cl; 2111 2112 if ((hif = altq_lookup(ap->iface.hfsc_ifname, ALTQT_HFSC)) == NULL) 2113 return (EBADF); 2114 2115 if ((cl = clh_to_clp(hif, ap->class_handle)) == NULL) 2116 return (EINVAL); 2117 2118 return hfsc_class_destroy(cl); 2119 } 2120 2121 static int 2122 hfsccmd_modify_class(ap) 2123 struct hfsc_modify_class *ap; 2124 { 2125 struct hfsc_if *hif; 2126 struct hfsc_class *cl; 2127 struct service_curve *rsc = NULL; 2128 struct service_curve *fsc = NULL; 2129 struct service_curve *usc = NULL; 2130 2131 if ((hif = altq_lookup(ap->iface.hfsc_ifname, ALTQT_HFSC)) == NULL) 2132 return (EBADF); 2133 2134 if ((cl = clh_to_clp(hif, ap->class_handle)) == NULL) 2135 return (EINVAL); 2136 2137 if (ap->sctype & HFSC_REALTIMESC) 2138 rsc = &ap->service_curve; 2139 if (ap->sctype & HFSC_LINKSHARINGSC) 2140 fsc = &ap->service_curve; 2141 if (ap->sctype & HFSC_UPPERLIMITSC) 2142 usc = &ap->service_curve; 2143 2144 return hfsc_class_modify(cl, rsc, fsc, usc); 2145 } 2146 2147 static int 2148 hfsccmd_add_filter(ap) 2149 struct hfsc_add_filter *ap; 2150 { 2151 struct hfsc_if *hif; 2152 struct hfsc_class *cl; 2153 2154 if ((hif = altq_lookup(ap->iface.hfsc_ifname, ALTQT_HFSC)) == NULL) 2155 return (EBADF); 2156 2157 if ((cl = clh_to_clp(hif, ap->class_handle)) == NULL) 2158 return (EINVAL); 2159 2160 if (is_a_parent_class(cl)) { 2161 #ifdef ALTQ_DEBUG 2162 printf("hfsccmd_add_filter: not a leaf class!\n"); 2163 #endif 2164 return (EINVAL); 2165 } 2166 2167 return acc_add_filter(&hif->hif_classifier, &ap->filter, 2168 cl, &ap->filter_handle); 2169 } 2170 2171 static int 2172 hfsccmd_delete_filter(ap) 2173 struct hfsc_delete_filter *ap; 2174 { 2175 struct hfsc_if *hif; 2176 2177 if ((hif = altq_lookup(ap->iface.hfsc_ifname, ALTQT_HFSC)) == NULL) 2178 return (EBADF); 2179 2180 return acc_delete_filter(&hif->hif_classifier, 2181 ap->filter_handle); 2182 } 2183 2184 static int 2185 hfsccmd_class_stats(ap) 2186 struct hfsc_class_stats *ap; 2187 { 2188 struct hfsc_if *hif; 2189 struct hfsc_class *cl; 2190 struct hfsc_classstats stats, *usp; 2191 int n, nclasses, error; 2192 2193 if ((hif = altq_lookup(ap->iface.hfsc_ifname, ALTQT_HFSC)) == NULL) 2194 return (EBADF); 2195 2196 ap->cur_time = read_machclk(); 2197 ap->machclk_freq = machclk_freq; 2198 ap->hif_classes = hif->hif_classes; 2199 ap->hif_packets = hif->hif_packets; 2200 2201 /* skip the first N classes in the tree */ 2202 nclasses = ap->nskip; 2203 for (cl = hif->hif_rootclass, n = 0; cl != NULL && n < nclasses; 2204 cl = hfsc_nextclass(cl), n++) 2205 ; 2206 if (n != nclasses) 2207 return (EINVAL); 2208 2209 /* then, read the next N classes in the tree */ 2210 nclasses = ap->nclasses; 2211 usp = ap->stats; 2212 for (n = 0; cl != NULL && n < nclasses; cl = hfsc_nextclass(cl), n++) { 2213 2214 get_class_stats(&stats, cl); 2215 2216 if ((error = copyout((caddr_t)&stats, (caddr_t)usp++, 2217 sizeof(stats))) != 0) 2218 return (error); 2219 } 2220 2221 ap->nclasses = n; 2222 2223 return (0); 2224 } 2225 2226 #ifdef KLD_MODULE 2227 2228 static struct altqsw hfsc_sw = 2229 {"hfsc", hfscopen, hfscclose, hfscioctl}; 2230 2231 ALTQ_MODULE(altq_hfsc, ALTQT_HFSC, &hfsc_sw); 2232 MODULE_DEPEND(altq_hfsc, altq_red, 1, 1, 1); 2233 MODULE_DEPEND(altq_hfsc, altq_rio, 1, 1, 1); 2234 2235 #endif /* KLD_MODULE */ 2236 #endif /* ALTQ3_COMPAT */ 2237 2238 #endif /* ALTQ_HFSC */ 2239