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