altq_hfsc.c revision 1.14
1 /* $NetBSD: altq_hfsc.c,v 1.14 2006/04/23 16:57:22 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.14 2006/04/23 16:57:22 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 if (head != NULL) 939 TAILQ_INIT(head); 940 return (head); 941 } 942 943 static void 944 ellist_destroy(head) 945 ellist_t *head; 946 { 947 free(head, M_DEVBUF); 948 } 949 950 static void 951 ellist_insert(cl) 952 struct hfsc_class *cl; 953 { 954 struct hfsc_if *hif = cl->cl_hif; 955 struct hfsc_class *p; 956 957 /* check the last entry first */ 958 if ((p = TAILQ_LAST(hif->hif_eligible, _eligible)) == NULL || 959 p->cl_e <= cl->cl_e) { 960 TAILQ_INSERT_TAIL(hif->hif_eligible, cl, cl_ellist); 961 return; 962 } 963 964 TAILQ_FOREACH(p, hif->hif_eligible, cl_ellist) { 965 if (cl->cl_e < p->cl_e) { 966 TAILQ_INSERT_BEFORE(p, cl, cl_ellist); 967 return; 968 } 969 } 970 ASSERT(0); /* should not reach here */ 971 } 972 973 static void 974 ellist_remove(cl) 975 struct hfsc_class *cl; 976 { 977 struct hfsc_if *hif = cl->cl_hif; 978 979 TAILQ_REMOVE(hif->hif_eligible, cl, cl_ellist); 980 } 981 982 static void 983 ellist_update(cl) 984 struct hfsc_class *cl; 985 { 986 struct hfsc_if *hif = cl->cl_hif; 987 struct hfsc_class *p, *last; 988 989 /* 990 * the eligible time of a class increases monotonically. 991 * if the next entry has a larger eligible time, nothing to do. 992 */ 993 p = TAILQ_NEXT(cl, cl_ellist); 994 if (p == NULL || cl->cl_e <= p->cl_e) 995 return; 996 997 /* check the last entry */ 998 last = TAILQ_LAST(hif->hif_eligible, _eligible); 999 ASSERT(last != NULL); 1000 if (last->cl_e <= cl->cl_e) { 1001 TAILQ_REMOVE(hif->hif_eligible, cl, cl_ellist); 1002 TAILQ_INSERT_TAIL(hif->hif_eligible, cl, cl_ellist); 1003 return; 1004 } 1005 1006 /* 1007 * the new position must be between the next entry 1008 * and the last entry 1009 */ 1010 while ((p = TAILQ_NEXT(p, cl_ellist)) != NULL) { 1011 if (cl->cl_e < p->cl_e) { 1012 TAILQ_REMOVE(hif->hif_eligible, cl, cl_ellist); 1013 TAILQ_INSERT_BEFORE(p, cl, cl_ellist); 1014 return; 1015 } 1016 } 1017 ASSERT(0); /* should not reach here */ 1018 } 1019 1020 /* find the class with the minimum deadline among the eligible classes */ 1021 struct hfsc_class * 1022 ellist_get_mindl(head) 1023 ellist_t *head; 1024 { 1025 struct hfsc_class *p, *cl = NULL; 1026 u_int64_t cur_time; 1027 1028 cur_time = read_machclk(); 1029 1030 TAILQ_FOREACH(p, head, cl_ellist) { 1031 if (p->cl_e > cur_time) 1032 break; 1033 if (cl == NULL || p->cl_d < cl->cl_d) 1034 cl = p; 1035 } 1036 return (cl); 1037 } 1038 1039 /* 1040 * active children list holds backlogged child classes being sorted 1041 * by their virtual time. 1042 * each intermediate class has one active children list. 1043 */ 1044 static actlist_t * 1045 actlist_alloc() 1046 { 1047 actlist_t *head; 1048 1049 head = malloc(sizeof(actlist_t), M_DEVBUF, M_WAITOK); 1050 if (head != NULL) 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, l) 1396 dev_t dev; 1397 int flag, fmt; 1398 struct lwp *l; 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, l) 1414 dev_t dev; 1415 int flag, fmt; 1416 struct lwp *l; 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, l) 1438 dev_t dev; 1439 ioctlcmd_t cmd; 1440 caddr_t addr; 1441 int flag; 1442 struct lwp *l; 1443 { 1444 struct hfsc_if *hif; 1445 struct hfsc_interface *ifacep; 1446 struct proc* p = l->l_proc; 1447 int error = 0; 1448 1449 /* check super-user privilege */ 1450 switch (cmd) { 1451 case HFSC_GETSTATS: 1452 break; 1453 default: 1454 #if (__FreeBSD_version > 400000) 1455 if ((error = suser(p)) != 0) 1456 return (error); 1457 #else 1458 if ((error = suser(p->p_ucred, &p->p_acflag)) != 0) 1459 return (error); 1460 #endif 1461 break; 1462 } 1463 1464 switch (cmd) { 1465 1466 case HFSC_IF_ATTACH: 1467 error = hfsccmd_if_attach((struct hfsc_attach *)addr); 1468 break; 1469 1470 case HFSC_IF_DETACH: 1471 error = hfsccmd_if_detach((struct hfsc_interface *)addr); 1472 break; 1473 1474 case HFSC_ENABLE: 1475 case HFSC_DISABLE: 1476 case HFSC_CLEAR_HIERARCHY: 1477 ifacep = (struct hfsc_interface *)addr; 1478 if ((hif = altq_lookup(ifacep->hfsc_ifname, 1479 ALTQT_HFSC)) == NULL) { 1480 error = EBADF; 1481 break; 1482 } 1483 1484 switch (cmd) { 1485 1486 case HFSC_ENABLE: 1487 if (hif->hif_defaultclass == NULL) { 1488 #if 1 1489 printf("hfsc: no default class\n"); 1490 #endif 1491 error = EINVAL; 1492 break; 1493 } 1494 error = altq_enable(hif->hif_ifq); 1495 break; 1496 1497 case HFSC_DISABLE: 1498 error = altq_disable(hif->hif_ifq); 1499 break; 1500 1501 case HFSC_CLEAR_HIERARCHY: 1502 hfsc_clear_interface(hif); 1503 break; 1504 } 1505 break; 1506 1507 case HFSC_ADD_CLASS: 1508 error = hfsccmd_add_class((struct hfsc_add_class *)addr); 1509 break; 1510 1511 case HFSC_DEL_CLASS: 1512 error = hfsccmd_delete_class((struct hfsc_delete_class *)addr); 1513 break; 1514 1515 case HFSC_MOD_CLASS: 1516 error = hfsccmd_modify_class((struct hfsc_modify_class *)addr); 1517 break; 1518 1519 case HFSC_ADD_FILTER: 1520 error = hfsccmd_add_filter((struct hfsc_add_filter *)addr); 1521 break; 1522 1523 case HFSC_DEL_FILTER: 1524 error = hfsccmd_delete_filter((struct hfsc_delete_filter *)addr); 1525 break; 1526 1527 case HFSC_GETSTATS: 1528 error = hfsccmd_class_stats((struct hfsc_class_stats *)addr); 1529 break; 1530 1531 default: 1532 error = EINVAL; 1533 break; 1534 } 1535 return error; 1536 } 1537 1538 static int 1539 hfsccmd_if_attach(ap) 1540 struct hfsc_attach *ap; 1541 { 1542 struct hfsc_if *hif; 1543 struct ifnet *ifp; 1544 int error; 1545 1546 if ((ifp = ifunit(ap->iface.hfsc_ifname)) == NULL) 1547 return (ENXIO); 1548 1549 if ((hif = hfsc_attach(&ifp->if_snd, ap->bandwidth)) == NULL) 1550 return (ENOMEM); 1551 1552 /* 1553 * set HFSC to this ifnet structure. 1554 */ 1555 if ((error = altq_attach(&ifp->if_snd, ALTQT_HFSC, hif, 1556 hfsc_enqueue, hfsc_dequeue, hfsc_request, 1557 &hif->hif_classifier, acc_classify)) != 0) 1558 (void)hfsc_detach(hif); 1559 1560 return (error); 1561 } 1562 1563 static int 1564 hfsccmd_if_detach(ap) 1565 struct hfsc_interface *ap; 1566 { 1567 struct hfsc_if *hif; 1568 int error; 1569 1570 if ((hif = altq_lookup(ap->hfsc_ifname, ALTQT_HFSC)) == NULL) 1571 return (EBADF); 1572 1573 if (ALTQ_IS_ENABLED(hif->hif_ifq)) 1574 altq_disable(hif->hif_ifq); 1575 1576 if ((error = altq_detach(hif->hif_ifq))) 1577 return (error); 1578 1579 return hfsc_detach(hif); 1580 } 1581 1582 static int 1583 hfsccmd_add_class(ap) 1584 struct hfsc_add_class *ap; 1585 { 1586 struct hfsc_if *hif; 1587 struct hfsc_class *cl, *parent; 1588 1589 if ((hif = altq_lookup(ap->iface.hfsc_ifname, ALTQT_HFSC)) == NULL) 1590 return (EBADF); 1591 1592 if ((parent = clh_to_clp(hif, ap->parent_handle)) == NULL) { 1593 if (ap->parent_handle == HFSC_ROOTCLASS_HANDLE) 1594 parent = hif->hif_rootclass; 1595 else 1596 return (EINVAL); 1597 } 1598 1599 if ((cl = hfsc_class_create(hif, &ap->service_curve, parent, 1600 ap->qlimit, ap->flags)) == NULL) 1601 return (ENOMEM); 1602 1603 /* return a class handle to the user */ 1604 ap->class_handle = clp_to_clh(cl); 1605 return (0); 1606 } 1607 1608 static int 1609 hfsccmd_delete_class(ap) 1610 struct hfsc_delete_class *ap; 1611 { 1612 struct hfsc_if *hif; 1613 struct hfsc_class *cl; 1614 1615 if ((hif = altq_lookup(ap->iface.hfsc_ifname, ALTQT_HFSC)) == NULL) 1616 return (EBADF); 1617 1618 if ((cl = clh_to_clp(hif, ap->class_handle)) == NULL) 1619 return (EINVAL); 1620 1621 return hfsc_class_destroy(cl); 1622 } 1623 1624 static int 1625 hfsccmd_modify_class(ap) 1626 struct hfsc_modify_class *ap; 1627 { 1628 struct hfsc_if *hif; 1629 struct hfsc_class *cl; 1630 struct service_curve *rsc = NULL; 1631 struct service_curve *fsc = NULL; 1632 1633 if ((hif = altq_lookup(ap->iface.hfsc_ifname, ALTQT_HFSC)) == NULL) 1634 return (EBADF); 1635 1636 if ((cl = clh_to_clp(hif, ap->class_handle)) == NULL) 1637 return (EINVAL); 1638 1639 if (ap->sctype & HFSC_REALTIMESC) 1640 rsc = &ap->service_curve; 1641 if (ap->sctype & HFSC_LINKSHARINGSC) 1642 fsc = &ap->service_curve; 1643 1644 return hfsc_class_modify(cl, rsc, fsc); 1645 } 1646 1647 static int 1648 hfsccmd_add_filter(ap) 1649 struct hfsc_add_filter *ap; 1650 { 1651 struct hfsc_if *hif; 1652 struct hfsc_class *cl; 1653 1654 if ((hif = altq_lookup(ap->iface.hfsc_ifname, ALTQT_HFSC)) == NULL) 1655 return (EBADF); 1656 1657 if ((cl = clh_to_clp(hif, ap->class_handle)) == NULL) 1658 return (EINVAL); 1659 1660 if (is_a_parent_class(cl)) { 1661 #if 1 1662 printf("hfsccmd_add_filter: not a leaf class!\n"); 1663 #endif 1664 return (EINVAL); 1665 } 1666 1667 return acc_add_filter(&hif->hif_classifier, &ap->filter, 1668 cl, &ap->filter_handle); 1669 } 1670 1671 static int 1672 hfsccmd_delete_filter(ap) 1673 struct hfsc_delete_filter *ap; 1674 { 1675 struct hfsc_if *hif; 1676 1677 if ((hif = altq_lookup(ap->iface.hfsc_ifname, ALTQT_HFSC)) == NULL) 1678 return (EBADF); 1679 1680 return acc_delete_filter(&hif->hif_classifier, 1681 ap->filter_handle); 1682 } 1683 1684 static int 1685 hfsccmd_class_stats(ap) 1686 struct hfsc_class_stats *ap; 1687 { 1688 struct hfsc_if *hif; 1689 struct hfsc_class *cl; 1690 struct hfsc_basic_class_stats stats, *usp; 1691 int n, nclasses, error; 1692 1693 if ((hif = altq_lookup(ap->iface.hfsc_ifname, ALTQT_HFSC)) == NULL) 1694 return (EBADF); 1695 1696 ap->cur_time = read_machclk(); 1697 ap->hif_classes = hif->hif_classes; 1698 ap->hif_packets = hif->hif_packets; 1699 1700 /* skip the first N classes in the tree */ 1701 nclasses = ap->nskip; 1702 for (cl = hif->hif_rootclass, n = 0; cl != NULL && n < nclasses; 1703 cl = hfsc_nextclass(cl), n++) 1704 ; 1705 if (n != nclasses) 1706 return (EINVAL); 1707 1708 /* then, read the next N classes in the tree */ 1709 nclasses = ap->nclasses; 1710 usp = ap->stats; 1711 for (n = 0; cl != NULL && n < nclasses; cl = hfsc_nextclass(cl), n++) { 1712 1713 get_class_stats(&stats, cl); 1714 1715 if ((error = copyout((caddr_t)&stats, (caddr_t)usp++, 1716 sizeof(stats))) != 0) 1717 return (error); 1718 } 1719 1720 ap->nclasses = n; 1721 1722 return (0); 1723 } 1724 1725 static void get_class_stats(sp, cl) 1726 struct hfsc_basic_class_stats *sp; 1727 struct hfsc_class *cl; 1728 { 1729 sp->class_id = cl->cl_id; 1730 sp->class_handle = clp_to_clh(cl); 1731 1732 if (cl->cl_rsc != NULL) { 1733 sp->rsc.m1 = sm2m(cl->cl_rsc->sm1); 1734 sp->rsc.d = dx2d(cl->cl_rsc->dx); 1735 sp->rsc.m2 = sm2m(cl->cl_rsc->sm2); 1736 } else { 1737 sp->rsc.m1 = 0; 1738 sp->rsc.d = 0; 1739 sp->rsc.m2 = 0; 1740 } 1741 if (cl->cl_fsc != NULL) { 1742 sp->fsc.m1 = sm2m(cl->cl_fsc->sm1); 1743 sp->fsc.d = dx2d(cl->cl_fsc->dx); 1744 sp->fsc.m2 = sm2m(cl->cl_fsc->sm2); 1745 } else { 1746 sp->fsc.m1 = 0; 1747 sp->fsc.d = 0; 1748 sp->fsc.m2 = 0; 1749 } 1750 1751 sp->total = cl->cl_total; 1752 sp->cumul = cl->cl_cumul; 1753 1754 sp->d = cl->cl_d; 1755 sp->e = cl->cl_e; 1756 sp->vt = cl->cl_vt; 1757 1758 sp->qlength = qlen(cl->cl_q); 1759 sp->xmit_cnt = cl->cl_stats.xmit_cnt; 1760 sp->drop_cnt = cl->cl_stats.drop_cnt; 1761 sp->period = cl->cl_stats.period; 1762 1763 sp->qtype = qtype(cl->cl_q); 1764 #ifdef ALTQ_RED 1765 if (q_is_red(cl->cl_q)) 1766 red_getstats(cl->cl_red, &sp->red[0]); 1767 #endif 1768 #ifdef ALTQ_RIO 1769 if (q_is_rio(cl->cl_q)) 1770 rio_getstats((rio_t *)cl->cl_red, &sp->red[0]); 1771 #endif 1772 } 1773 1774 /* convert a class handle to the corresponding class pointer */ 1775 static struct hfsc_class * 1776 clh_to_clp(hif, chandle) 1777 struct hfsc_if *hif; 1778 u_long chandle; 1779 { 1780 struct hfsc_class *cl; 1781 1782 cl = (struct hfsc_class *)chandle; 1783 if (chandle != ALIGN(cl)) { 1784 #if 1 1785 printf("clh_to_cl: unaligned pointer %p\n", cl); 1786 #endif 1787 return (NULL); 1788 } 1789 1790 if (cl == NULL || cl->cl_handle != chandle || cl->cl_hif != hif) 1791 return (NULL); 1792 1793 return (cl); 1794 } 1795 1796 /* convert a class pointer to the corresponding class handle */ 1797 static u_long 1798 clp_to_clh(cl) 1799 struct hfsc_class *cl; 1800 { 1801 if (cl->cl_parent == NULL) 1802 return (HFSC_ROOTCLASS_HANDLE); /* XXX */ 1803 return (cl->cl_handle); 1804 } 1805 1806 #ifdef KLD_MODULE 1807 1808 static struct altqsw hfsc_sw = 1809 {"hfsc", hfscopen, hfscclose, hfscioctl}; 1810 1811 ALTQ_MODULE(altq_hfsc, ALTQT_HFSC, &hfsc_sw); 1812 1813 #endif /* KLD_MODULE */ 1814 1815 #endif /* ALTQ_HFSC */ 1816
Indexes created Tue Sep 30 17:09:57 GMT 2025