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