altq_hfsc.c revision 1.13
1 /* $NetBSD: altq_hfsc.c,v 1.13 2006/04/23 06:46:40 christos Exp $ */ 2 /* $KAME: altq_hfsc.c,v 1.9 2001/10/26 04:56:11 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, and that 12 * both notices appear in supporting documentation, and that credit 13 * is given to Carnegie Mellon University in all publications reporting 14 * on direct or indirect use of this code or its derivatives. 15 * 16 * THIS SOFTWARE IS EXPERIMENTAL AND IS KNOWN TO HAVE BUGS, SOME OF 17 * WHICH MAY HAVE SERIOUS CONSEQUENCES. CARNEGIE MELLON PROVIDES THIS 18 * SOFTWARE IN ITS ``AS IS'' CONDITION, AND ANY EXPRESS OR IMPLIED 19 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 21 * DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY BE LIABLE 22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 23 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT 24 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 25 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 26 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE 28 * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH 29 * DAMAGE. 30 * 31 * Carnegie Mellon encourages (but does not require) users of this 32 * software to return any improvements or extensions that they make, 33 * and to grant Carnegie Mellon the rights to redistribute these 34 * changes without encumbrance. 35 */ 36 /* 37 * H-FSC is described in Proceedings of SIGCOMM'97, 38 * "A Hierarchical Fair Service Curve Algorithm for Link-Sharing, 39 * Real-Time and Priority Service" 40 * by Ion Stoica, Hui Zhang, and T. S. Eugene Ng. 41 */ 42 43 #include <sys/cdefs.h> 44 __KERNEL_RCSID(0, "$NetBSD: altq_hfsc.c,v 1.13 2006/04/23 06:46:40 christos Exp $"); 45 46 #if defined(__FreeBSD__) || defined(__NetBSD__) 47 #include "opt_altq.h" 48 #if (__FreeBSD__ != 2) 49 #include "opt_inet.h" 50 #ifdef __FreeBSD__ 51 #include "opt_inet6.h" 52 #endif 53 #endif 54 #endif /* __FreeBSD__ || __NetBSD__ */ 55 56 #ifdef ALTQ_HFSC /* hfsc is enabled by ALTQ_HFSC option in opt_altq.h */ 57 58 #include <sys/param.h> 59 #include <sys/malloc.h> 60 #include <sys/mbuf.h> 61 #include <sys/socket.h> 62 #include <sys/sockio.h> 63 #include <sys/systm.h> 64 #include <sys/proc.h> 65 #include <sys/errno.h> 66 #include <sys/kernel.h> 67 #include <sys/queue.h> 68 69 #include <net/if.h> 70 #include <net/if_types.h> 71 72 #include <altq/altq.h> 73 #include <altq/altq_conf.h> 74 #include <altq/altq_hfsc.h> 75 76 /* 77 * function prototypes 78 */ 79 static struct hfsc_if *hfsc_attach __P((struct ifaltq *, u_int)); 80 static int hfsc_detach __P((struct hfsc_if *)); 81 static int hfsc_clear_interface __P((struct hfsc_if *)); 82 static int hfsc_request __P((struct ifaltq *, int, void *)); 83 static void hfsc_purge __P((struct hfsc_if *)); 84 static struct hfsc_class *hfsc_class_create __P((struct hfsc_if *, 85 struct service_curve *, struct hfsc_class *, int, int)); 86 static int hfsc_class_destroy __P((struct hfsc_class *)); 87 static int hfsc_class_modify __P((struct hfsc_class *, 88 struct service_curve *, struct service_curve *)); 89 static struct hfsc_class *hfsc_nextclass __P((struct hfsc_class *)); 90 91 static int hfsc_enqueue __P((struct ifaltq *, struct mbuf *, 92 struct altq_pktattr *)); 93 static struct mbuf *hfsc_dequeue __P((struct ifaltq *, int)); 94 95 static int hfsc_addq __P((struct hfsc_class *, struct mbuf *)); 96 static struct mbuf *hfsc_getq __P((struct hfsc_class *)); 97 static struct mbuf *hfsc_pollq __P((struct hfsc_class *)); 98 static void hfsc_purgeq __P((struct hfsc_class *)); 99 100 static void set_active __P((struct hfsc_class *, int)); 101 static void set_passive __P((struct hfsc_class *)); 102 103 static void init_ed __P((struct hfsc_class *, int)); 104 static void update_ed __P((struct hfsc_class *, int)); 105 static void update_d __P((struct hfsc_class *, int)); 106 static void init_v __P((struct hfsc_class *, int)); 107 static void update_v __P((struct hfsc_class *, int)); 108 static ellist_t *ellist_alloc __P((void)); 109 static void ellist_destroy __P((ellist_t *)); 110 static void ellist_insert __P((struct hfsc_class *)); 111 static void ellist_remove __P((struct hfsc_class *)); 112 static void ellist_update __P((struct hfsc_class *)); 113 struct hfsc_class *ellist_get_mindl __P((ellist_t *)); 114 static actlist_t *actlist_alloc __P((void)); 115 static void actlist_destroy __P((actlist_t *)); 116 static void actlist_insert __P((struct hfsc_class *)); 117 static void actlist_remove __P((struct hfsc_class *)); 118 static void actlist_update __P((struct hfsc_class *)); 119 120 static inline u_int64_t seg_x2y __P((u_int64_t, u_int64_t)); 121 static inline u_int64_t seg_y2x __P((u_int64_t, u_int64_t)); 122 static inline u_int64_t m2sm __P((u_int)); 123 static inline u_int64_t m2ism __P((u_int)); 124 static inline u_int64_t d2dx __P((u_int)); 125 static u_int sm2m __P((u_int64_t)); 126 static u_int dx2d __P((u_int64_t)); 127 128 static void sc2isc __P((struct service_curve *, struct internal_sc *)); 129 static void rtsc_init __P((struct runtime_sc *, struct internal_sc *, 130 u_int64_t, u_int64_t)); 131 static u_int64_t rtsc_y2x __P((struct runtime_sc *, u_int64_t)); 132 static u_int64_t rtsc_x2y __P((struct runtime_sc *, u_int64_t)); 133 static void rtsc_min __P((struct runtime_sc *, struct internal_sc *, 134 u_int64_t, u_int64_t)); 135 136 int hfscopen __P((dev_t, int, int, struct lwp *)); 137 int hfscclose __P((dev_t, int, int, struct lwp *)); 138 int hfscioctl __P((dev_t, ioctlcmd_t, caddr_t, int, struct lwp *)); 139 static int hfsccmd_if_attach __P((struct hfsc_attach *)); 140 static int hfsccmd_if_detach __P((struct hfsc_interface *)); 141 static int hfsccmd_add_class __P((struct hfsc_add_class *)); 142 static int hfsccmd_delete_class __P((struct hfsc_delete_class *)); 143 static int hfsccmd_modify_class __P((struct hfsc_modify_class *)); 144 static int hfsccmd_add_filter __P((struct hfsc_add_filter *)); 145 static int hfsccmd_delete_filter __P((struct hfsc_delete_filter *)); 146 static int hfsccmd_class_stats __P((struct hfsc_class_stats *)); 147 static void get_class_stats __P((struct hfsc_basic_class_stats *, 148 struct hfsc_class *)); 149 static struct hfsc_class *clh_to_clp __P((struct hfsc_if *, u_long)); 150 static u_long clp_to_clh __P((struct hfsc_class *)); 151 152 /* 153 * macros 154 */ 155 #define is_a_parent_class(cl) ((cl)->cl_children != NULL) 156 157 /* hif_list keeps all hfsc_if's allocated. */ 158 static struct hfsc_if *hif_list = NULL; 159 160 static struct hfsc_if * 161 hfsc_attach(ifq, bandwidth) 162 struct ifaltq *ifq; 163 u_int bandwidth; 164 { 165 struct hfsc_if *hif; 166 struct service_curve root_sc; 167 168 hif = malloc(sizeof(struct hfsc_if), M_DEVBUF, M_WAITOK|M_ZERO); 169 if (hif == NULL) 170 return (NULL); 171 172 hif->hif_eligible = ellist_alloc(); 173 if (hif->hif_eligible == NULL) { 174 free(hif, M_DEVBUF); 175 return NULL; 176 } 177 178 hif->hif_ifq = ifq; 179 180 /* 181 * create root class 182 */ 183 root_sc.m1 = bandwidth; 184 root_sc.d = 0; 185 root_sc.m2 = bandwidth; 186 if ((hif->hif_rootclass = 187 hfsc_class_create(hif, &root_sc, NULL, 0, 0)) == NULL) { 188 free(hif, M_DEVBUF); 189 return (NULL); 190 } 191 192 /* add this state to the hfsc list */ 193 hif->hif_next = hif_list; 194 hif_list = hif; 195 196 return (hif); 197 } 198 199 static int 200 hfsc_detach(hif) 201 struct hfsc_if *hif; 202 { 203 (void)hfsc_clear_interface(hif); 204 (void)hfsc_class_destroy(hif->hif_rootclass); 205 206 /* remove this interface from the hif list */ 207 if (hif_list == hif) 208 hif_list = hif->hif_next; 209 else { 210 struct hfsc_if *h; 211 212 for (h = hif_list; h != NULL; h = h->hif_next) 213 if (h->hif_next == hif) { 214 h->hif_next = hif->hif_next; 215 break; 216 } 217 ASSERT(h != NULL); 218 } 219 220 ellist_destroy(hif->hif_eligible); 221 222 free(hif, M_DEVBUF); 223 224 return (0); 225 } 226 227 /* 228 * bring the interface back to the initial state by discarding 229 * all the filters and classes except the root class. 230 */ 231 static int 232 hfsc_clear_interface(hif) 233 struct hfsc_if *hif; 234 { 235 struct hfsc_class *cl; 236 237 /* free the filters for this interface */ 238 acc_discard_filters(&hif->hif_classifier, NULL, 1); 239 240 /* clear out the classes */ 241 while ((cl = hif->hif_rootclass->cl_children) != NULL) { 242 /* 243 * remove the first leaf class found in the hierarchy 244 * then start over 245 */ 246 for (; cl != NULL; cl = hfsc_nextclass(cl)) { 247 if (!is_a_parent_class(cl)) { 248 (void)hfsc_class_destroy(cl); 249 break; 250 } 251 } 252 } 253 254 return (0); 255 } 256 257 static int 258 hfsc_request(ifq, req, arg) 259 struct ifaltq *ifq; 260 int req; 261 void *arg; 262 { 263 struct hfsc_if *hif = (struct hfsc_if *)ifq->altq_disc; 264 265 switch (req) { 266 case ALTRQ_PURGE: 267 hfsc_purge(hif); 268 break; 269 } 270 return (0); 271 } 272 273 /* discard all the queued packets on the interface */ 274 static void 275 hfsc_purge(hif) 276 struct hfsc_if *hif; 277 { 278 struct hfsc_class *cl; 279 280 for (cl = hif->hif_rootclass; cl != NULL; cl = hfsc_nextclass(cl)) 281 if (!qempty(cl->cl_q)) 282 hfsc_purgeq(cl); 283 if (ALTQ_IS_ENABLED(hif->hif_ifq)) 284 hif->hif_ifq->ifq_len = 0; 285 } 286 287 struct hfsc_class * 288 hfsc_class_create(hif, sc, parent, qlimit, flags) 289 struct hfsc_if *hif; 290 struct service_curve *sc; 291 struct hfsc_class *parent; 292 int qlimit, flags; 293 { 294 struct hfsc_class *cl, *p; 295 int s; 296 297 #ifndef ALTQ_RED 298 if (flags & HFCF_RED) { 299 printf("hfsc_class_create: RED not configured for HFSC!\n"); 300 return (NULL); 301 } 302 #endif 303 304 cl = malloc(sizeof(struct hfsc_class), M_DEVBUF, M_WAITOK|M_ZERO); 305 if (cl == NULL) 306 return (NULL); 307 308 cl->cl_q = malloc(sizeof(class_queue_t), M_DEVBUF, M_WAITOK|M_ZERO); 309 if (cl->cl_q == NULL) 310 goto err_ret; 311 312 cl->cl_actc = actlist_alloc(); 313 if (cl->cl_actc == NULL) 314 goto err_ret; 315 316 if (qlimit == 0) 317 qlimit = 50; /* use default */ 318 qlimit(cl->cl_q) = qlimit; 319 qtype(cl->cl_q) = Q_DROPTAIL; 320 qlen(cl->cl_q) = 0; 321 cl->cl_flags = flags; 322 #ifdef ALTQ_RED 323 if (flags & (HFCF_RED|HFCF_RIO)) { 324 int red_flags, red_pkttime; 325 326 red_flags = 0; 327 if (flags & HFCF_ECN) 328 red_flags |= REDF_ECN; 329 #ifdef ALTQ_RIO 330 if (flags & HFCF_CLEARDSCP) 331 red_flags |= RIOF_CLEARDSCP; 332 #endif 333 if (sc->m2 < 8) 334 red_pkttime = 1000 * 1000 * 1000; /* 1 sec */ 335 else 336 red_pkttime = (int64_t)hif->hif_ifq->altq_ifp->if_mtu 337 * 1000 * 1000 * 1000 / (sc->m2 / 8); 338 if (flags & HFCF_RED) { 339 cl->cl_red = red_alloc(0, 0, 0, 0, 340 red_flags, red_pkttime); 341 if (cl->cl_red != NULL) 342 qtype(cl->cl_q) = Q_RED; 343 } 344 #ifdef ALTQ_RIO 345 else { 346 cl->cl_red = (red_t *)rio_alloc(0, NULL, 347 red_flags, red_pkttime); 348 if (cl->cl_red != NULL) 349 qtype(cl->cl_q) = Q_RIO; 350 } 351 #endif 352 } 353 #endif /* ALTQ_RED */ 354 355 if (sc != NULL && (sc->m1 != 0 || sc->m2 != 0)) { 356 cl->cl_rsc = malloc(sizeof(struct internal_sc), M_DEVBUF, 357 M_WAITOK|M_ZERO); 358 if (cl->cl_rsc == NULL) 359 goto err_ret; 360 sc2isc(sc, cl->cl_rsc); 361 rtsc_init(&cl->cl_deadline, cl->cl_rsc, 0, 0); 362 rtsc_init(&cl->cl_eligible, cl->cl_rsc, 0, 0); 363 364 cl->cl_fsc = malloc(sizeof(struct internal_sc), M_DEVBUF, 365 M_WAITOK|M_ZERO); 366 if (cl->cl_fsc == NULL) 367 goto err_ret; 368 sc2isc(sc, cl->cl_fsc); 369 rtsc_init(&cl->cl_virtual, cl->cl_fsc, 0, 0); 370 } 371 372 cl->cl_id = hif->hif_classid++; 373 cl->cl_handle = (u_long)cl; /* XXX: just a pointer to this class */ 374 cl->cl_hif = hif; 375 cl->cl_parent = parent; 376 377 s = splnet(); 378 hif->hif_classes++; 379 if (flags & HFCF_DEFAULTCLASS) 380 hif->hif_defaultclass = cl; 381 382 /* add this class to the children list of the parent */ 383 if (parent == NULL) { 384 /* this is root class */ 385 } 386 else if ((p = parent->cl_children) == NULL) 387 parent->cl_children = cl; 388 else { 389 while (p->cl_siblings != NULL) 390 p = p->cl_siblings; 391 p->cl_siblings = cl; 392 } 393 splx(s); 394 395 return (cl); 396 397 err_ret: 398 if (cl->cl_actc != NULL) 399 actlist_destroy(cl->cl_actc); 400 if (cl->cl_red != NULL) { 401 #ifdef ALTQ_RIO 402 if (q_is_rio(cl->cl_q)) 403 rio_destroy((rio_t *)cl->cl_red); 404 #endif 405 #ifdef ALTQ_RED 406 if (q_is_red(cl->cl_q)) 407 red_destroy(cl->cl_red); 408 #endif 409 } 410 if (cl->cl_fsc != NULL) 411 free(cl->cl_fsc, M_DEVBUF); 412 if (cl->cl_rsc != NULL) 413 free(cl->cl_rsc, M_DEVBUF); 414 if (cl->cl_q != NULL) 415 free(cl->cl_q, M_DEVBUF); 416 free(cl, M_DEVBUF); 417 return (NULL); 418 } 419 420 static int 421 hfsc_class_destroy(cl) 422 struct hfsc_class *cl; 423 { 424 int s; 425 426 if (is_a_parent_class(cl)) 427 return (EBUSY); 428 429 s = splnet(); 430 431 /* delete filters referencing to this class */ 432 acc_discard_filters(&cl->cl_hif->hif_classifier, cl, 0); 433 434 if (!qempty(cl->cl_q)) 435 hfsc_purgeq(cl); 436 437 if (cl->cl_parent == NULL) { 438 /* this is root class */ 439 } else { 440 struct hfsc_class *p = cl->cl_parent->cl_children; 441 442 if (p == cl) 443 cl->cl_parent->cl_children = cl->cl_siblings; 444 else do { 445 if (p->cl_siblings == cl) { 446 p->cl_siblings = cl->cl_siblings; 447 break; 448 } 449 } while ((p = p->cl_siblings) != NULL); 450 ASSERT(p != NULL); 451 } 452 cl->cl_hif->hif_classes--; 453 splx(s); 454 455 actlist_destroy(cl->cl_actc); 456 457 if (cl->cl_red != NULL) { 458 #ifdef ALTQ_RIO 459 if (q_is_rio(cl->cl_q)) 460 rio_destroy((rio_t *)cl->cl_red); 461 #endif 462 #ifdef ALTQ_RED 463 if (q_is_red(cl->cl_q)) 464 red_destroy(cl->cl_red); 465 #endif 466 } 467 if (cl->cl_fsc != NULL) 468 free(cl->cl_fsc, M_DEVBUF); 469 if (cl->cl_rsc != NULL) 470 free(cl->cl_rsc, M_DEVBUF); 471 free(cl->cl_q, M_DEVBUF); 472 free(cl, M_DEVBUF); 473 474 return (0); 475 } 476 477 static int 478 hfsc_class_modify(cl, rsc, fsc) 479 struct hfsc_class *cl; 480 struct service_curve *rsc, *fsc; 481 { 482 struct internal_sc *rsc_tmp, *fsc_tmp; 483 int s; 484 485 if (rsc != NULL && (rsc->m1 != 0 || rsc->m2 != 0) && 486 cl->cl_rsc == NULL) { 487 rsc_tmp = malloc(sizeof(struct internal_sc), M_DEVBUF, 488 M_WAITOK|M_ZERO); 489 if (rsc_tmp == NULL) 490 return (ENOMEM); 491 } else 492 rsc_tmp = NULL; 493 if (fsc != NULL && (fsc->m1 != 0 || fsc->m2 != 0) && 494 cl->cl_fsc == NULL) { 495 fsc_tmp = malloc(sizeof(struct internal_sc), M_DEVBUF, 496 M_WAITOK|M_ZERO); 497 if (fsc_tmp == NULL) 498 return (ENOMEM); 499 } else 500 fsc_tmp = NULL; 501 502 s = splnet(); 503 if (!qempty(cl->cl_q)) 504 hfsc_purgeq(cl); 505 506 if (rsc != NULL) { 507 if (rsc->m1 == 0 && rsc->m2 == 0) { 508 if (cl->cl_rsc != NULL) { 509 free(cl->cl_rsc, M_DEVBUF); 510 cl->cl_rsc = NULL; 511 } 512 } else { 513 if (cl->cl_rsc == NULL) 514 cl->cl_rsc = rsc_tmp; 515 sc2isc(rsc, cl->cl_rsc); 516 rtsc_init(&cl->cl_deadline, cl->cl_rsc, 0, 0); 517 rtsc_init(&cl->cl_eligible, cl->cl_rsc, 0, 0); 518 } 519 } 520 521 if (fsc != NULL) { 522 if (fsc->m1 == 0 && fsc->m2 == 0) { 523 if (cl->cl_fsc != NULL) { 524 free(cl->cl_fsc, M_DEVBUF); 525 cl->cl_fsc = NULL; 526 } 527 } else { 528 if (cl->cl_fsc == NULL) 529 cl->cl_fsc = fsc_tmp; 530 sc2isc(fsc, cl->cl_fsc); 531 rtsc_init(&cl->cl_virtual, cl->cl_fsc, 0, 0); 532 } 533 } 534 splx(s); 535 536 return (0); 537 } 538 539 /* 540 * hfsc_nextclass returns the next class in the tree. 541 * usage: 542 * for (cl = hif->hif_rootclass; cl != NULL; cl = hfsc_nextclass(cl)) 543 * do_something; 544 */ 545 static struct hfsc_class * 546 hfsc_nextclass(cl) 547 struct hfsc_class *cl; 548 { 549 if (cl->cl_children != NULL) 550 cl = cl->cl_children; 551 else if (cl->cl_siblings != NULL) 552 cl = cl->cl_siblings; 553 else { 554 while ((cl = cl->cl_parent) != NULL) 555 if (cl->cl_siblings) { 556 cl = cl->cl_siblings; 557 break; 558 } 559 } 560 561 return (cl); 562 } 563 564 /* 565 * hfsc_enqueue is an enqueue function to be registered to 566 * (*altq_enqueue) in struct ifaltq. 567 */ 568 static int 569 hfsc_enqueue(ifq, m, pktattr) 570 struct ifaltq *ifq; 571 struct mbuf *m; 572 struct altq_pktattr *pktattr; 573 { 574 struct hfsc_if *hif = (struct hfsc_if *)ifq->altq_disc; 575 struct hfsc_class *cl; 576 int len; 577 578 /* grab class set by classifier */ 579 if (pktattr == NULL || (cl = pktattr->pattr_class) == NULL) 580 cl = hif->hif_defaultclass; 581 cl->cl_pktattr = pktattr; /* save proto hdr used by ECN */ 582 583 len = m_pktlen(m); 584 if (hfsc_addq(cl, m) != 0) { 585 /* drop occurred. mbuf was freed in hfsc_addq. */ 586 PKTCNTR_ADD(&cl->cl_stats.drop_cnt, len); 587 return (ENOBUFS); 588 } 589 IFQ_INC_LEN(ifq); 590 cl->cl_hif->hif_packets++; 591 592 /* successfully queued. */ 593 if (qlen(cl->cl_q) == 1) 594 set_active(cl, m_pktlen(m)); 595 596 #ifdef HFSC_PKTLOG 597 /* put the logging_hook here */ 598 #endif 599 return (0); 600 } 601 602 /* 603 * hfsc_dequeue is a dequeue function to be registered to 604 * (*altq_dequeue) in struct ifaltq. 605 * 606 * note: ALTDQ_POLL returns the next packet without removing the packet 607 * from the queue. ALTDQ_REMOVE is a normal dequeue operation. 608 * ALTDQ_REMOVE must return the same packet if called immediately 609 * after ALTDQ_POLL. 610 */ 611 static struct mbuf * 612 hfsc_dequeue(ifq, op) 613 struct ifaltq *ifq; 614 int op; 615 { 616 struct hfsc_if *hif = (struct hfsc_if *)ifq->altq_disc; 617 struct hfsc_class *cl; 618 struct mbuf *m; 619 int len, next_len; 620 int realtime = 0; 621 622 if (hif->hif_packets == 0) 623 /* no packet in the tree */ 624 return (NULL); 625 626 if (op == ALTDQ_REMOVE && hif->hif_pollcache != NULL) { 627 u_int64_t cur_time; 628 629 cl = hif->hif_pollcache; 630 hif->hif_pollcache = NULL; 631 /* check if the class was scheduled by real-time criteria */ 632 if (cl->cl_rsc != NULL) { 633 cur_time = read_machclk(); 634 realtime = (cl->cl_e <= cur_time); 635 } 636 } else { 637 /* 638 * if there are eligible classes, use real-time criteria. 639 * find the class with the minimum deadline among 640 * the eligible classes. 641 */ 642 if ((cl = ellist_get_mindl(hif->hif_eligible)) != NULL) { 643 realtime = 1; 644 } else { 645 /* 646 * use link-sharing criteria 647 * get the class with the minimum vt in the hierarchy 648 */ 649 cl = hif->hif_rootclass; 650 while (is_a_parent_class(cl)) { 651 cl = actlist_first(cl->cl_actc); 652 if (cl == NULL) 653 return (NULL); 654 } 655 } 656 657 if (op == ALTDQ_POLL) { 658 hif->hif_pollcache = cl; 659 m = hfsc_pollq(cl); 660 return (m); 661 } 662 } 663 664 m = hfsc_getq(cl); 665 len = m_pktlen(m); 666 cl->cl_hif->hif_packets--; 667 IFQ_DEC_LEN(ifq); 668 PKTCNTR_ADD(&cl->cl_stats.xmit_cnt, len); 669 670 update_v(cl, len); 671 if (realtime) 672 cl->cl_cumul += len; 673 674 if (!qempty(cl->cl_q)) { 675 if (cl->cl_rsc != NULL) { 676 /* update ed */ 677 next_len = m_pktlen(qhead(cl->cl_q)); 678 679 if (realtime) 680 update_ed(cl, next_len); 681 else 682 update_d(cl, next_len); 683 } 684 } else { 685 /* the class becomes passive */ 686 set_passive(cl); 687 } 688 689 #ifdef HFSC_PKTLOG 690 /* put the logging_hook here */ 691 #endif 692 693 return (m); 694 } 695 696 static int 697 hfsc_addq(cl, m) 698 struct hfsc_class *cl; 699 struct mbuf *m; 700 { 701 702 #ifdef ALTQ_RIO 703 if (q_is_rio(cl->cl_q)) 704 return rio_addq((rio_t *)cl->cl_red, cl->cl_q, 705 m, cl->cl_pktattr); 706 #endif 707 #ifdef ALTQ_RED 708 if (q_is_red(cl->cl_q)) 709 return red_addq(cl->cl_red, cl->cl_q, m, cl->cl_pktattr); 710 #endif 711 if (qlen(cl->cl_q) >= qlimit(cl->cl_q)) { 712 m_freem(m); 713 return (-1); 714 } 715 716 if (cl->cl_flags & HFCF_CLEARDSCP) 717 write_dsfield(m, cl->cl_pktattr, 0); 718 719 _addq(cl->cl_q, m); 720 721 return (0); 722 } 723 724 static struct mbuf * 725 hfsc_getq(cl) 726 struct hfsc_class *cl; 727 { 728 #ifdef ALTQ_RIO 729 if (q_is_rio(cl->cl_q)) 730 return rio_getq((rio_t *)cl->cl_red, cl->cl_q); 731 #endif 732 #ifdef ALTQ_RED 733 if (q_is_red(cl->cl_q)) 734 return red_getq(cl->cl_red, cl->cl_q); 735 #endif 736 return _getq(cl->cl_q); 737 } 738 739 static struct mbuf * 740 hfsc_pollq(cl) 741 struct hfsc_class *cl; 742 { 743 return qhead(cl->cl_q); 744 } 745 746 static void 747 hfsc_purgeq(cl) 748 struct hfsc_class *cl; 749 { 750 struct mbuf *m; 751 752 if (qempty(cl->cl_q)) 753 return; 754 755 while ((m = _getq(cl->cl_q)) != NULL) { 756 PKTCNTR_ADD(&cl->cl_stats.drop_cnt, m_pktlen(m)); 757 m_freem(m); 758 } 759 ASSERT(qlen(cl->cl_q) == 0); 760 761 set_passive(cl); 762 } 763 764 static void 765 set_active(cl, len) 766 struct hfsc_class *cl; 767 int len; 768 { 769 if (cl->cl_rsc != NULL) 770 init_ed(cl, len); 771 if (cl->cl_fsc != NULL) 772 init_v(cl, len); 773 774 cl->cl_stats.period++; 775 } 776 777 static void 778 set_passive(cl) 779 struct hfsc_class *cl; 780 { 781 if (cl->cl_rsc != NULL) 782 ellist_remove(cl); 783 784 if (cl->cl_fsc != NULL) { 785 while (cl->cl_parent != NULL) { 786 if (--cl->cl_nactive == 0) { 787 /* remove this class from the vt list */ 788 actlist_remove(cl); 789 } else 790 /* still has active children */ 791 break; 792 793 /* go up to the parent class */ 794 cl = cl->cl_parent; 795 } 796 } 797 } 798 799 static void 800 init_ed(cl, next_len) 801 struct hfsc_class *cl; 802 int next_len; 803 { 804 u_int64_t cur_time; 805 806 cur_time = read_machclk(); 807 808 /* update the deadline curve */ 809 rtsc_min(&cl->cl_deadline, cl->cl_rsc, cur_time, cl->cl_cumul); 810 811 /* 812 * update the eligible curve. 813 * for concave, it is equal to the deadline curve. 814 * for convex, it is a linear curve with slope m2. 815 */ 816 cl->cl_eligible = cl->cl_deadline; 817 if (cl->cl_rsc->sm1 <= cl->cl_rsc->sm2) { 818 cl->cl_eligible.dx = 0; 819 cl->cl_eligible.dy = 0; 820 } 821 822 /* compute e and d */ 823 cl->cl_e = rtsc_y2x(&cl->cl_eligible, cl->cl_cumul); 824 cl->cl_d = rtsc_y2x(&cl->cl_deadline, cl->cl_cumul + next_len); 825 826 ellist_insert(cl); 827 } 828 829 static void 830 update_ed(cl, next_len) 831 struct hfsc_class *cl; 832 int next_len; 833 { 834 cl->cl_e = rtsc_y2x(&cl->cl_eligible, cl->cl_cumul); 835 cl->cl_d = rtsc_y2x(&cl->cl_deadline, cl->cl_cumul + next_len); 836 837 ellist_update(cl); 838 } 839 840 static void 841 update_d(cl, next_len) 842 struct hfsc_class *cl; 843 int next_len; 844 { 845 cl->cl_d = rtsc_y2x(&cl->cl_deadline, cl->cl_cumul + next_len); 846 } 847 848 static void 849 init_v(cl, len) 850 struct hfsc_class *cl; 851 int len; 852 { 853 struct hfsc_class *min_cl, *max_cl; 854 855 while (cl->cl_parent != NULL) { 856 857 if (cl->cl_nactive++ > 0) 858 /* already active */ 859 break; 860 861 /* 862 * if parent became idle while this class was idle. 863 * reset vt and the runtime service curve. 864 */ 865 if (cl->cl_parent->cl_nactive == 0 || 866 cl->cl_parent->cl_vtperiod != cl->cl_parentperiod) { 867 cl->cl_vt = 0; 868 rtsc_init(&cl->cl_virtual, cl->cl_fsc, 869 0, cl->cl_total); 870 } 871 min_cl = actlist_first(cl->cl_parent->cl_actc); 872 if (min_cl != NULL) { 873 u_int64_t vt; 874 875 /* 876 * set vt to the average of the min and max classes. 877 * if the parent's period didn't change, 878 * don't decrease vt of the class. 879 */ 880 max_cl = actlist_last(cl->cl_parent->cl_actc); 881 vt = (min_cl->cl_vt + max_cl->cl_vt) / 2; 882 if (cl->cl_parent->cl_vtperiod != cl->cl_parentperiod 883 || vt > cl->cl_vt) 884 cl->cl_vt = vt; 885 } 886 887 /* update the virtual curve */ 888 rtsc_min(&cl->cl_virtual, cl->cl_fsc, cl->cl_vt, cl->cl_total); 889 890 cl->cl_vtperiod++; /* increment vt period */ 891 cl->cl_parentperiod = cl->cl_parent->cl_vtperiod; 892 if (cl->cl_parent->cl_nactive == 0) 893 cl->cl_parentperiod++; 894 895 actlist_insert(cl); 896 897 /* go up to the parent class */ 898 cl = cl->cl_parent; 899 } 900 } 901 902 static void 903 update_v(cl, len) 904 struct hfsc_class *cl; 905 int len; 906 { 907 while (cl->cl_parent != NULL) { 908 909 cl->cl_total += len; 910 911 if (cl->cl_fsc != NULL) { 912 cl->cl_vt = rtsc_y2x(&cl->cl_virtual, cl->cl_total); 913 914 /* update the vt list */ 915 actlist_update(cl); 916 } 917 918 /* go up to the parent class */ 919 cl = cl->cl_parent; 920 } 921 } 922 923 /* 924 * TAILQ based ellist and actlist implementation 925 * (ion wanted to make a calendar queue based implementation) 926 */ 927 /* 928 * eligible list holds backlogged classes being sorted by their eligible times. 929 * there is one eligible list per interface. 930 */ 931 932 static ellist_t * 933 ellist_alloc() 934 { 935 ellist_t *head; 936 937 head = malloc(sizeof(ellist_t), M_DEVBUF, M_WAITOK); 938 TAILQ_INIT(head); 939 return (head); 940 } 941 942 static void 943 ellist_destroy(head) 944 ellist_t *head; 945 { 946 free(head, M_DEVBUF); 947 } 948 949 static void 950 ellist_insert(cl) 951 struct hfsc_class *cl; 952 { 953 struct hfsc_if *hif = cl->cl_hif; 954 struct hfsc_class *p; 955 956 /* check the last entry first */ 957 if ((p = TAILQ_LAST(hif->hif_eligible, _eligible)) == NULL || 958 p->cl_e <= cl->cl_e) { 959 TAILQ_INSERT_TAIL(hif->hif_eligible, cl, cl_ellist); 960 return; 961 } 962 963 TAILQ_FOREACH(p, hif->hif_eligible, cl_ellist) { 964 if (cl->cl_e < p->cl_e) { 965 TAILQ_INSERT_BEFORE(p, cl, cl_ellist); 966 return; 967 } 968 } 969 ASSERT(0); /* should not reach here */ 970 } 971 972 static void 973 ellist_remove(cl) 974 struct hfsc_class *cl; 975 { 976 struct hfsc_if *hif = cl->cl_hif; 977 978 TAILQ_REMOVE(hif->hif_eligible, cl, cl_ellist); 979 } 980 981 static void 982 ellist_update(cl) 983 struct hfsc_class *cl; 984 { 985 struct hfsc_if *hif = cl->cl_hif; 986 struct hfsc_class *p, *last; 987 988 /* 989 * the eligible time of a class increases monotonically. 990 * if the next entry has a larger eligible time, nothing to do. 991 */ 992 p = TAILQ_NEXT(cl, cl_ellist); 993 if (p == NULL || cl->cl_e <= p->cl_e) 994 return; 995 996 /* check the last entry */ 997 last = TAILQ_LAST(hif->hif_eligible, _eligible); 998 ASSERT(last != NULL); 999 if (last->cl_e <= cl->cl_e) { 1000 TAILQ_REMOVE(hif->hif_eligible, cl, cl_ellist); 1001 TAILQ_INSERT_TAIL(hif->hif_eligible, cl, cl_ellist); 1002 return; 1003 } 1004 1005 /* 1006 * the new position must be between the next entry 1007 * and the last entry 1008 */ 1009 while ((p = TAILQ_NEXT(p, cl_ellist)) != NULL) { 1010 if (cl->cl_e < p->cl_e) { 1011 TAILQ_REMOVE(hif->hif_eligible, cl, cl_ellist); 1012 TAILQ_INSERT_BEFORE(p, cl, cl_ellist); 1013 return; 1014 } 1015 } 1016 ASSERT(0); /* should not reach here */ 1017 } 1018 1019 /* find the class with the minimum deadline among the eligible classes */ 1020 struct hfsc_class * 1021 ellist_get_mindl(head) 1022 ellist_t *head; 1023 { 1024 struct hfsc_class *p, *cl = NULL; 1025 u_int64_t cur_time; 1026 1027 cur_time = read_machclk(); 1028 1029 TAILQ_FOREACH(p, head, cl_ellist) { 1030 if (p->cl_e > cur_time) 1031 break; 1032 if (cl == NULL || p->cl_d < cl->cl_d) 1033 cl = p; 1034 } 1035 return (cl); 1036 } 1037 1038 /* 1039 * active children list holds backlogged child classes being sorted 1040 * by their virtual time. 1041 * each intermediate class has one active children list. 1042 */ 1043 static actlist_t * 1044 actlist_alloc() 1045 { 1046 actlist_t *head; 1047 1048 head = malloc(sizeof(actlist_t), M_DEVBUF, M_WAITOK); 1049 TAILQ_INIT(head); 1050 return (head); 1051 } 1052 1053 static void 1054 actlist_destroy(head) 1055 actlist_t *head; 1056 { 1057 free(head, M_DEVBUF); 1058 } 1059 static void 1060 actlist_insert(cl) 1061 struct hfsc_class *cl; 1062 { 1063 struct hfsc_class *p; 1064 1065 /* check the last entry first */ 1066 if ((p = TAILQ_LAST(cl->cl_parent->cl_actc, _active)) == NULL 1067 || p->cl_vt <= cl->cl_vt) { 1068 TAILQ_INSERT_TAIL(cl->cl_parent->cl_actc, cl, cl_actlist); 1069 return; 1070 } 1071 1072 TAILQ_FOREACH(p, cl->cl_parent->cl_actc, cl_actlist) { 1073 if (cl->cl_vt < p->cl_vt) { 1074 TAILQ_INSERT_BEFORE(p, cl, cl_actlist); 1075 return; 1076 } 1077 } 1078 ASSERT(0); /* should not reach here */ 1079 } 1080 1081 static void 1082 actlist_remove(cl) 1083 struct hfsc_class *cl; 1084 { 1085 TAILQ_REMOVE(cl->cl_parent->cl_actc, cl, cl_actlist); 1086 } 1087 1088 static void 1089 actlist_update(cl) 1090 struct hfsc_class *cl; 1091 { 1092 struct hfsc_class *p, *last; 1093 1094 /* 1095 * the virtual time of a class increases monotonically during its 1096 * backlogged period. 1097 * if the next entry has a larger virtual time, nothing to do. 1098 */ 1099 p = TAILQ_NEXT(cl, cl_actlist); 1100 if (p == NULL || cl->cl_vt <= p->cl_vt) 1101 return; 1102 1103 /* check the last entry */ 1104 last = TAILQ_LAST(cl->cl_parent->cl_actc, _active); 1105 ASSERT(last != NULL); 1106 if (last->cl_vt <= cl->cl_vt) { 1107 TAILQ_REMOVE(cl->cl_parent->cl_actc, cl, cl_actlist); 1108 TAILQ_INSERT_TAIL(cl->cl_parent->cl_actc, cl, cl_actlist); 1109 return; 1110 } 1111 1112 /* 1113 * the new position must be between the next entry 1114 * and the last entry 1115 */ 1116 while ((p = TAILQ_NEXT(p, cl_actlist)) != NULL) { 1117 if (cl->cl_vt < p->cl_vt) { 1118 TAILQ_REMOVE(cl->cl_parent->cl_actc, cl, cl_actlist); 1119 TAILQ_INSERT_BEFORE(p, cl, cl_actlist); 1120 return; 1121 } 1122 } 1123 ASSERT(0); /* should not reach here */ 1124 } 1125 1126 /* 1127 * service curve support functions 1128 * 1129 * external service curve parameters 1130 * m: bits/sec 1131 * d: msec 1132 * internal service curve parameters 1133 * sm: (bytes/tsc_interval) << SM_SHIFT 1134 * ism: (tsc_count/byte) << ISM_SHIFT 1135 * dx: tsc_count 1136 * 1137 * SM_SHIFT and ISM_SHIFT are scaled in order to keep effective digits. 1138 * we should be able to handle 100K-1Gbps linkspeed with 200Hz-1GHz CPU 1139 * speed. SM_SHIFT and ISM_SHIFT are selected to have at least 3 effective 1140 * digits in decimal using the following table. 1141 * 1142 * bits/set 100Kbps 1Mbps 10Mbps 100Mbps 1Gbps 1143 * ----------+------------------------------------------------------- 1144 * bytes/nsec 12.5e-6 125e-6 1250e-6 12500e-6 125000e-6 1145 * sm(500MHz) 25.0e-6 250e-6 2500e-6 25000e-6 250000e-6 1146 * sm(200MHz) 62.5e-6 625e-6 6250e-6 62500e-6 625000e-6 1147 * 1148 * nsec/byte 80000 8000 800 80 8 1149 * ism(500MHz) 40000 4000 400 40 4 1150 * ism(200MHz) 16000 1600 160 16 1.6 1151 */ 1152 #define SM_SHIFT 24 1153 #define ISM_SHIFT 10 1154 1155 #define SC_LARGEVAL (1LL << 32) 1156 #define SC_INFINITY 0xffffffffffffffffLL 1157 1158 static inline u_int64_t 1159 seg_x2y(x, sm) 1160 u_int64_t x; 1161 u_int64_t sm; 1162 { 1163 u_int64_t y; 1164 1165 if (x < SC_LARGEVAL) 1166 y = x * sm >> SM_SHIFT; 1167 else 1168 y = (x >> SM_SHIFT) * sm; 1169 return (y); 1170 } 1171 1172 static inline u_int64_t 1173 seg_y2x(y, ism) 1174 u_int64_t y; 1175 u_int64_t ism; 1176 { 1177 u_int64_t x; 1178 1179 if (y == 0) 1180 x = 0; 1181 else if (ism == SC_INFINITY) 1182 x = SC_INFINITY; 1183 else if (y < SC_LARGEVAL) 1184 x = y * ism >> ISM_SHIFT; 1185 else 1186 x = (y >> ISM_SHIFT) * ism; 1187 return (x); 1188 } 1189 1190 static inline u_int64_t 1191 m2sm(m) 1192 u_int m; 1193 { 1194 u_int64_t sm; 1195 1196 sm = ((u_int64_t)m << SM_SHIFT) / 8 / machclk_freq; 1197 return (sm); 1198 } 1199 1200 static inline u_int64_t 1201 m2ism(m) 1202 u_int m; 1203 { 1204 u_int64_t ism; 1205 1206 if (m == 0) 1207 ism = SC_INFINITY; 1208 else 1209 ism = ((u_int64_t)machclk_freq << ISM_SHIFT) * 8 / m; 1210 return (ism); 1211 } 1212 1213 static inline u_int64_t 1214 d2dx(d) 1215 u_int d; 1216 { 1217 u_int64_t dx; 1218 1219 dx = ((u_int64_t)d * machclk_freq) / 1000; 1220 return (dx); 1221 } 1222 1223 static u_int 1224 sm2m(sm) 1225 u_int64_t sm; 1226 { 1227 u_int64_t m; 1228 1229 m = (sm * 8 * machclk_freq) >> SM_SHIFT; 1230 return ((u_int)m); 1231 } 1232 1233 static u_int 1234 dx2d(dx) 1235 u_int64_t dx; 1236 { 1237 u_int64_t d; 1238 1239 d = dx * 1000 / machclk_freq; 1240 return ((u_int)d); 1241 } 1242 1243 static void 1244 sc2isc(sc, isc) 1245 struct service_curve *sc; 1246 struct internal_sc *isc; 1247 { 1248 isc->sm1 = m2sm(sc->m1); 1249 isc->ism1 = m2ism(sc->m1); 1250 isc->dx = d2dx(sc->d); 1251 isc->dy = seg_x2y(isc->dx, isc->sm1); 1252 isc->sm2 = m2sm(sc->m2); 1253 isc->ism2 = m2ism(sc->m2); 1254 } 1255 1256 /* 1257 * initialize the runtime service curve with the given internal 1258 * service curve starting at (x, y). 1259 */ 1260 static void 1261 rtsc_init(rtsc, isc, x, y) 1262 struct runtime_sc *rtsc; 1263 struct internal_sc *isc; 1264 u_int64_t x, y; 1265 { 1266 rtsc->x = x; 1267 rtsc->y = y; 1268 rtsc->sm1 = isc->sm1; 1269 rtsc->ism1 = isc->ism1; 1270 rtsc->dx = isc->dx; 1271 rtsc->dy = isc->dy; 1272 rtsc->sm2 = isc->sm2; 1273 rtsc->ism2 = isc->ism2; 1274 } 1275 1276 /* 1277 * calculate the y-projection of the runtime service curve by the 1278 * given x-projection value 1279 */ 1280 static u_int64_t 1281 rtsc_y2x(rtsc, y) 1282 struct runtime_sc *rtsc; 1283 u_int64_t y; 1284 { 1285 u_int64_t x; 1286 1287 if (y < rtsc->y) 1288 x = rtsc->x; 1289 else if (y <= rtsc->y + rtsc->dy) { 1290 /* x belongs to the 1st segment */ 1291 if (rtsc->dy == 0) 1292 x = rtsc->x + rtsc->dx; 1293 else 1294 x = rtsc->x + seg_y2x(y - rtsc->y, rtsc->ism1); 1295 } else { 1296 /* x belongs to the 2nd segment */ 1297 x = rtsc->x + rtsc->dx 1298 + seg_y2x(y - rtsc->y - rtsc->dy, rtsc->ism2); 1299 } 1300 return (x); 1301 } 1302 1303 static u_int64_t 1304 rtsc_x2y(rtsc, x) 1305 struct runtime_sc *rtsc; 1306 u_int64_t x; 1307 { 1308 u_int64_t y; 1309 1310 if (x <= rtsc->x) 1311 y = rtsc->y; 1312 else if (x <= rtsc->x + rtsc->dx) 1313 /* y belongs to the 1st segment */ 1314 y = rtsc->y + seg_x2y(x - rtsc->x, rtsc->sm1); 1315 else 1316 /* y belongs to the 2nd segment */ 1317 y = rtsc->y + rtsc->dy 1318 + seg_x2y(x - rtsc->x - rtsc->dx, rtsc->sm2); 1319 return (y); 1320 } 1321 1322 /* 1323 * update the runtime service curve by taking the minimum of the current 1324 * runtime service curve and the service curve starting at (x, y). 1325 */ 1326 static void 1327 rtsc_min(rtsc, isc, x, y) 1328 struct runtime_sc *rtsc; 1329 struct internal_sc *isc; 1330 u_int64_t x, y; 1331 { 1332 u_int64_t y1, y2, dx, dy; 1333 1334 if (isc->sm1 <= isc->sm2) { 1335 /* service curve is convex */ 1336 y1 = rtsc_x2y(rtsc, x); 1337 if (y1 < y) 1338 /* the current rtsc is smaller */ 1339 return; 1340 rtsc->x = x; 1341 rtsc->y = y; 1342 return; 1343 } 1344 1345 /* 1346 * service curve is concave 1347 * compute the two y values of the current rtsc 1348 * y1: at x 1349 * y2: at (x + dx) 1350 */ 1351 y1 = rtsc_x2y(rtsc, x); 1352 if (y1 <= y) { 1353 /* rtsc is below isc, no change to rtsc */ 1354 return; 1355 } 1356 1357 y2 = rtsc_x2y(rtsc, x + isc->dx); 1358 if (y2 >= y + isc->dy) { 1359 /* rtsc is above isc, replace rtsc by isc */ 1360 rtsc->x = x; 1361 rtsc->y = y; 1362 rtsc->dx = isc->dx; 1363 rtsc->dy = isc->dy; 1364 return; 1365 } 1366 1367 /* 1368 * the two curves intersect 1369 * compute the offsets (dx, dy) using the reverse 1370 * function of seg_x2y() 1371 * seg_x2y(dx, sm1) == seg_x2y(dx, sm2) + (y1 - y) 1372 */ 1373 dx = ((y1 - y) << SM_SHIFT) / (isc->sm1 - isc->sm2); 1374 /* 1375 * check if (x, y1) belongs to the 1st segment of rtsc. 1376 * if so, add the offset. 1377 */ 1378 if (rtsc->x + rtsc->dx > x) 1379 dx += rtsc->x + rtsc->dx - x; 1380 dy = seg_x2y(dx, isc->sm1); 1381 1382 rtsc->x = x; 1383 rtsc->y = y; 1384 rtsc->dx = dx; 1385 rtsc->dy = dy; 1386 return; 1387 } 1388 1389 /* 1390 * hfsc device interface 1391 */ 1392 int 1393 hfscopen(dev, flag, fmt, l) 1394 dev_t dev; 1395 int flag, fmt; 1396 struct lwp *l; 1397 { 1398 if (machclk_freq == 0) 1399 init_machclk(); 1400 1401 if (machclk_freq == 0) { 1402 printf("hfsc: no CPU clock available!\n"); 1403 return (ENXIO); 1404 } 1405 1406 /* everything will be done when the queueing scheme is attached. */ 1407 return 0; 1408 } 1409 1410 int 1411 hfscclose(dev, flag, fmt, l) 1412 dev_t dev; 1413 int flag, fmt; 1414 struct lwp *l; 1415 { 1416 struct hfsc_if *hif; 1417 int err, error = 0; 1418 1419 while ((hif = hif_list) != NULL) { 1420 /* destroy all */ 1421 if (ALTQ_IS_ENABLED(hif->hif_ifq)) 1422 altq_disable(hif->hif_ifq); 1423 1424 err = altq_detach(hif->hif_ifq); 1425 if (err == 0) 1426 err = hfsc_detach(hif); 1427 if (err != 0 && error == 0) 1428 error = err; 1429 } 1430 1431 return error; 1432 } 1433 1434 int 1435 hfscioctl(dev, cmd, addr, flag, l) 1436 dev_t dev; 1437 ioctlcmd_t cmd; 1438 caddr_t addr; 1439 int flag; 1440 struct lwp *l; 1441 { 1442 struct hfsc_if *hif; 1443 struct hfsc_interface *ifacep; 1444 struct proc* p = l->l_proc; 1445 int error = 0; 1446 1447 /* check super-user privilege */ 1448 switch (cmd) { 1449 case HFSC_GETSTATS: 1450 break; 1451 default: 1452 #if (__FreeBSD_version > 400000) 1453 if ((error = suser(p)) != 0) 1454 return (error); 1455 #else 1456 if ((error = suser(p->p_ucred, &p->p_acflag)) != 0) 1457 return (error); 1458 #endif 1459 break; 1460 } 1461 1462 switch (cmd) { 1463 1464 case HFSC_IF_ATTACH: 1465 error = hfsccmd_if_attach((struct hfsc_attach *)addr); 1466 break; 1467 1468 case HFSC_IF_DETACH: 1469 error = hfsccmd_if_detach((struct hfsc_interface *)addr); 1470 break; 1471 1472 case HFSC_ENABLE: 1473 case HFSC_DISABLE: 1474 case HFSC_CLEAR_HIERARCHY: 1475 ifacep = (struct hfsc_interface *)addr; 1476 if ((hif = altq_lookup(ifacep->hfsc_ifname, 1477 ALTQT_HFSC)) == NULL) { 1478 error = EBADF; 1479 break; 1480 } 1481 1482 switch (cmd) { 1483 1484 case HFSC_ENABLE: 1485 if (hif->hif_defaultclass == NULL) { 1486 #if 1 1487 printf("hfsc: no default class\n"); 1488 #endif 1489 error = EINVAL; 1490 break; 1491 } 1492 error = altq_enable(hif->hif_ifq); 1493 break; 1494 1495 case HFSC_DISABLE: 1496 error = altq_disable(hif->hif_ifq); 1497 break; 1498 1499 case HFSC_CLEAR_HIERARCHY: 1500 hfsc_clear_interface(hif); 1501 break; 1502 } 1503 break; 1504 1505 case HFSC_ADD_CLASS: 1506 error = hfsccmd_add_class((struct hfsc_add_class *)addr); 1507 break; 1508 1509 case HFSC_DEL_CLASS: 1510 error = hfsccmd_delete_class((struct hfsc_delete_class *)addr); 1511 break; 1512 1513 case HFSC_MOD_CLASS: 1514 error = hfsccmd_modify_class((struct hfsc_modify_class *)addr); 1515 break; 1516 1517 case HFSC_ADD_FILTER: 1518 error = hfsccmd_add_filter((struct hfsc_add_filter *)addr); 1519 break; 1520 1521 case HFSC_DEL_FILTER: 1522 error = hfsccmd_delete_filter((struct hfsc_delete_filter *)addr); 1523 break; 1524 1525 case HFSC_GETSTATS: 1526 error = hfsccmd_class_stats((struct hfsc_class_stats *)addr); 1527 break; 1528 1529 default: 1530 error = EINVAL; 1531 break; 1532 } 1533 return error; 1534 } 1535 1536 static int 1537 hfsccmd_if_attach(ap) 1538 struct hfsc_attach *ap; 1539 { 1540 struct hfsc_if *hif; 1541 struct ifnet *ifp; 1542 int error; 1543 1544 if ((ifp = ifunit(ap->iface.hfsc_ifname)) == NULL) 1545 return (ENXIO); 1546 1547 if ((hif = hfsc_attach(&ifp->if_snd, ap->bandwidth)) == NULL) 1548 return (ENOMEM); 1549 1550 /* 1551 * set HFSC to this ifnet structure. 1552 */ 1553 if ((error = altq_attach(&ifp->if_snd, ALTQT_HFSC, hif, 1554 hfsc_enqueue, hfsc_dequeue, hfsc_request, 1555 &hif->hif_classifier, acc_classify)) != 0) 1556 (void)hfsc_detach(hif); 1557 1558 return (error); 1559 } 1560 1561 static int 1562 hfsccmd_if_detach(ap) 1563 struct hfsc_interface *ap; 1564 { 1565 struct hfsc_if *hif; 1566 int error; 1567 1568 if ((hif = altq_lookup(ap->hfsc_ifname, ALTQT_HFSC)) == NULL) 1569 return (EBADF); 1570 1571 if (ALTQ_IS_ENABLED(hif->hif_ifq)) 1572 altq_disable(hif->hif_ifq); 1573 1574 if ((error = altq_detach(hif->hif_ifq))) 1575 return (error); 1576 1577 return hfsc_detach(hif); 1578 } 1579 1580 static int 1581 hfsccmd_add_class(ap) 1582 struct hfsc_add_class *ap; 1583 { 1584 struct hfsc_if *hif; 1585 struct hfsc_class *cl, *parent; 1586 1587 if ((hif = altq_lookup(ap->iface.hfsc_ifname, ALTQT_HFSC)) == NULL) 1588 return (EBADF); 1589 1590 if ((parent = clh_to_clp(hif, ap->parent_handle)) == NULL) { 1591 if (ap->parent_handle == HFSC_ROOTCLASS_HANDLE) 1592 parent = hif->hif_rootclass; 1593 else 1594 return (EINVAL); 1595 } 1596 1597 if ((cl = hfsc_class_create(hif, &ap->service_curve, parent, 1598 ap->qlimit, ap->flags)) == NULL) 1599 return (ENOMEM); 1600 1601 /* return a class handle to the user */ 1602 ap->class_handle = clp_to_clh(cl); 1603 return (0); 1604 } 1605 1606 static int 1607 hfsccmd_delete_class(ap) 1608 struct hfsc_delete_class *ap; 1609 { 1610 struct hfsc_if *hif; 1611 struct hfsc_class *cl; 1612 1613 if ((hif = altq_lookup(ap->iface.hfsc_ifname, ALTQT_HFSC)) == NULL) 1614 return (EBADF); 1615 1616 if ((cl = clh_to_clp(hif, ap->class_handle)) == NULL) 1617 return (EINVAL); 1618 1619 return hfsc_class_destroy(cl); 1620 } 1621 1622 static int 1623 hfsccmd_modify_class(ap) 1624 struct hfsc_modify_class *ap; 1625 { 1626 struct hfsc_if *hif; 1627 struct hfsc_class *cl; 1628 struct service_curve *rsc = NULL; 1629 struct service_curve *fsc = NULL; 1630 1631 if ((hif = altq_lookup(ap->iface.hfsc_ifname, ALTQT_HFSC)) == NULL) 1632 return (EBADF); 1633 1634 if ((cl = clh_to_clp(hif, ap->class_handle)) == NULL) 1635 return (EINVAL); 1636 1637 if (ap->sctype & HFSC_REALTIMESC) 1638 rsc = &ap->service_curve; 1639 if (ap->sctype & HFSC_LINKSHARINGSC) 1640 fsc = &ap->service_curve; 1641 1642 return hfsc_class_modify(cl, rsc, fsc); 1643 } 1644 1645 static int 1646 hfsccmd_add_filter(ap) 1647 struct hfsc_add_filter *ap; 1648 { 1649 struct hfsc_if *hif; 1650 struct hfsc_class *cl; 1651 1652 if ((hif = altq_lookup(ap->iface.hfsc_ifname, ALTQT_HFSC)) == NULL) 1653 return (EBADF); 1654 1655 if ((cl = clh_to_clp(hif, ap->class_handle)) == NULL) 1656 return (EINVAL); 1657 1658 if (is_a_parent_class(cl)) { 1659 #if 1 1660 printf("hfsccmd_add_filter: not a leaf class!\n"); 1661 #endif 1662 return (EINVAL); 1663 } 1664 1665 return acc_add_filter(&hif->hif_classifier, &ap->filter, 1666 cl, &ap->filter_handle); 1667 } 1668 1669 static int 1670 hfsccmd_delete_filter(ap) 1671 struct hfsc_delete_filter *ap; 1672 { 1673 struct hfsc_if *hif; 1674 1675 if ((hif = altq_lookup(ap->iface.hfsc_ifname, ALTQT_HFSC)) == NULL) 1676 return (EBADF); 1677 1678 return acc_delete_filter(&hif->hif_classifier, 1679 ap->filter_handle); 1680 } 1681 1682 static int 1683 hfsccmd_class_stats(ap) 1684 struct hfsc_class_stats *ap; 1685 { 1686 struct hfsc_if *hif; 1687 struct hfsc_class *cl; 1688 struct hfsc_basic_class_stats stats, *usp; 1689 int n, nclasses, error; 1690 1691 if ((hif = altq_lookup(ap->iface.hfsc_ifname, ALTQT_HFSC)) == NULL) 1692 return (EBADF); 1693 1694 ap->cur_time = read_machclk(); 1695 ap->hif_classes = hif->hif_classes; 1696 ap->hif_packets = hif->hif_packets; 1697 1698 /* skip the first N classes in the tree */ 1699 nclasses = ap->nskip; 1700 for (cl = hif->hif_rootclass, n = 0; cl != NULL && n < nclasses; 1701 cl = hfsc_nextclass(cl), n++) 1702 ; 1703 if (n != nclasses) 1704 return (EINVAL); 1705 1706 /* then, read the next N classes in the tree */ 1707 nclasses = ap->nclasses; 1708 usp = ap->stats; 1709 for (n = 0; cl != NULL && n < nclasses; cl = hfsc_nextclass(cl), n++) { 1710 1711 get_class_stats(&stats, cl); 1712 1713 if ((error = copyout((caddr_t)&stats, (caddr_t)usp++, 1714 sizeof(stats))) != 0) 1715 return (error); 1716 } 1717 1718 ap->nclasses = n; 1719 1720 return (0); 1721 } 1722 1723 static void get_class_stats(sp, cl) 1724 struct hfsc_basic_class_stats *sp; 1725 struct hfsc_class *cl; 1726 { 1727 sp->class_id = cl->cl_id; 1728 sp->class_handle = clp_to_clh(cl); 1729 1730 if (cl->cl_rsc != NULL) { 1731 sp->rsc.m1 = sm2m(cl->cl_rsc->sm1); 1732 sp->rsc.d = dx2d(cl->cl_rsc->dx); 1733 sp->rsc.m2 = sm2m(cl->cl_rsc->sm2); 1734 } else { 1735 sp->rsc.m1 = 0; 1736 sp->rsc.d = 0; 1737 sp->rsc.m2 = 0; 1738 } 1739 if (cl->cl_fsc != NULL) { 1740 sp->fsc.m1 = sm2m(cl->cl_fsc->sm1); 1741 sp->fsc.d = dx2d(cl->cl_fsc->dx); 1742 sp->fsc.m2 = sm2m(cl->cl_fsc->sm2); 1743 } else { 1744 sp->fsc.m1 = 0; 1745 sp->fsc.d = 0; 1746 sp->fsc.m2 = 0; 1747 } 1748 1749 sp->total = cl->cl_total; 1750 sp->cumul = cl->cl_cumul; 1751 1752 sp->d = cl->cl_d; 1753 sp->e = cl->cl_e; 1754 sp->vt = cl->cl_vt; 1755 1756 sp->qlength = qlen(cl->cl_q); 1757 sp->xmit_cnt = cl->cl_stats.xmit_cnt; 1758 sp->drop_cnt = cl->cl_stats.drop_cnt; 1759 sp->period = cl->cl_stats.period; 1760 1761 sp->qtype = qtype(cl->cl_q); 1762 #ifdef ALTQ_RED 1763 if (q_is_red(cl->cl_q)) 1764 red_getstats(cl->cl_red, &sp->red[0]); 1765 #endif 1766 #ifdef ALTQ_RIO 1767 if (q_is_rio(cl->cl_q)) 1768 rio_getstats((rio_t *)cl->cl_red, &sp->red[0]); 1769 #endif 1770 } 1771 1772 /* convert a class handle to the corresponding class pointer */ 1773 static struct hfsc_class * 1774 clh_to_clp(hif, chandle) 1775 struct hfsc_if *hif; 1776 u_long chandle; 1777 { 1778 struct hfsc_class *cl; 1779 1780 cl = (struct hfsc_class *)chandle; 1781 if (chandle != ALIGN(cl)) { 1782 #if 1 1783 printf("clh_to_cl: unaligned pointer %p\n", cl); 1784 #endif 1785 return (NULL); 1786 } 1787 1788 if (cl == NULL || cl->cl_handle != chandle || cl->cl_hif != hif) 1789 return (NULL); 1790 1791 return (cl); 1792 } 1793 1794 /* convert a class pointer to the corresponding class handle */ 1795 static u_long 1796 clp_to_clh(cl) 1797 struct hfsc_class *cl; 1798 { 1799 if (cl->cl_parent == NULL) 1800 return (HFSC_ROOTCLASS_HANDLE); /* XXX */ 1801 return (cl->cl_handle); 1802 } 1803 1804 #ifdef KLD_MODULE 1805 1806 static struct altqsw hfsc_sw = 1807 {"hfsc", hfscopen, hfscclose, hfscioctl}; 1808 1809 ALTQ_MODULE(altq_hfsc, ALTQT_HFSC, &hfsc_sw); 1810 1811 #endif /* KLD_MODULE */ 1812 1813 #endif /* ALTQ_HFSC */ 1814
Indexes created Tue Sep 30 10:09:55 GMT 2025