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