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