1 /*- 2 * Copyright (c) 1991-1997 Regents of the University of California. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 3. All advertising materials mentioning features or use of this software 14 * must display the following acknowledgement: 15 * This product includes software developed by the Network Research 16 * Group at Lawrence Berkeley Laboratory. 17 * 4. Neither the name of the University nor of the Laboratory may be used 18 * to endorse or promote products derived from this software without 19 * specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 * SUCH DAMAGE. 32 * 33 * LBL code modified by speer@eng.sun.com, May 1977. 34 * For questions and/or comments, please send mail to cbq@ee.lbl.gov 35 * 36 * @(#)rm_class.c 1.48 97/12/05 SMI 37 * $KAME: altq_rmclass.c,v 1.19 2005/04/13 03:44:25 suz Exp $ 38 * $FreeBSD$ 39 */ 40 #include "opt_altq.h" 41 #include "opt_inet.h" 42 #include "opt_inet6.h" 43 #ifdef ALTQ_CBQ /* cbq is enabled by ALTQ_CBQ option in opt_altq.h */ 44 45 #include <sys/param.h> 46 #include <sys/malloc.h> 47 #include <sys/mbuf.h> 48 #include <sys/socket.h> 49 #include <sys/systm.h> 50 #include <sys/errno.h> 51 #include <sys/time.h> 52 53 #include <net/if.h> 54 #include <net/if_var.h> 55 56 #include <net/altq/if_altq.h> 57 #include <net/altq/altq.h> 58 #include <net/altq/altq_codel.h> 59 #include <net/altq/altq_rmclass.h> 60 #include <net/altq/altq_rmclass_debug.h> 61 #include <net/altq/altq_red.h> 62 #include <net/altq/altq_rio.h> 63 64 /* 65 * Local Macros 66 */ 67 #define reset_cutoff(ifd) { ifd->cutoff_ = RM_MAXDEPTH; } 68 69 /* 70 * Local routines. 71 */ 72 73 static int rmc_satisfied(struct rm_class *, struct timeval *); 74 static void rmc_wrr_set_weights(struct rm_ifdat *); 75 static void rmc_depth_compute(struct rm_class *); 76 static void rmc_depth_recompute(rm_class_t *); 77 78 static mbuf_t *_rmc_wrr_dequeue_next(struct rm_ifdat *, int); 79 static mbuf_t *_rmc_prr_dequeue_next(struct rm_ifdat *, int); 80 81 static int _rmc_addq(rm_class_t *, mbuf_t *); 82 static void _rmc_dropq(rm_class_t *); 83 static mbuf_t *_rmc_getq(rm_class_t *); 84 static mbuf_t *_rmc_pollq(rm_class_t *); 85 86 static int rmc_under_limit(struct rm_class *, struct timeval *); 87 static void rmc_tl_satisfied(struct rm_ifdat *, struct timeval *); 88 static void rmc_drop_action(struct rm_class *); 89 static void rmc_restart(void *); 90 static void rmc_root_overlimit(struct rm_class *, struct rm_class *); 91 92 #define BORROW_OFFTIME 93 /* 94 * BORROW_OFFTIME (experimental): 95 * borrow the offtime of the class borrowing from. 96 * the reason is that when its own offtime is set, the class is unable 97 * to borrow much, especially when cutoff is taking effect. 98 * but when the borrowed class is overloaded (advidle is close to minidle), 99 * use the borrowing class's offtime to avoid overload. 100 */ 101 #define ADJUST_CUTOFF 102 /* 103 * ADJUST_CUTOFF (experimental): 104 * if no underlimit class is found due to cutoff, increase cutoff and 105 * retry the scheduling loop. 106 * also, don't invoke delay_actions while cutoff is taking effect, 107 * since a sleeping class won't have a chance to be scheduled in the 108 * next loop. 109 * 110 * now heuristics for setting the top-level variable (cutoff_) becomes: 111 * 1. if a packet arrives for a not-overlimit class, set cutoff 112 * to the depth of the class. 113 * 2. if cutoff is i, and a packet arrives for an overlimit class 114 * with an underlimit ancestor at a lower level than i (say j), 115 * then set cutoff to j. 116 * 3. at scheduling a packet, if there is no underlimit class 117 * due to the current cutoff level, increase cutoff by 1 and 118 * then try to schedule again. 119 */ 120 121 /* 122 * rm_class_t * 123 * rmc_newclass(...) - Create a new resource management class at priority 124 * 'pri' on the interface given by 'ifd'. 125 * 126 * nsecPerByte is the data rate of the interface in nanoseconds/byte. 127 * E.g., 800 for a 10Mb/s ethernet. If the class gets less 128 * than 100% of the bandwidth, this number should be the 129 * 'effective' rate for the class. Let f be the 130 * bandwidth fraction allocated to this class, and let 131 * nsPerByte be the data rate of the output link in 132 * nanoseconds/byte. Then nsecPerByte is set to 133 * nsPerByte / f. E.g., 1600 (= 800 / .5) 134 * for a class that gets 50% of an ethernet's bandwidth. 135 * 136 * action the routine to call when the class is over limit. 137 * 138 * maxq max allowable queue size for class (in packets). 139 * 140 * parent parent class pointer. 141 * 142 * borrow class to borrow from (should be either 'parent' or null). 143 * 144 * maxidle max value allowed for class 'idle' time estimate (this 145 * parameter determines how large an initial burst of packets 146 * can be before overlimit action is invoked. 147 * 148 * offtime how long 'delay' action will delay when class goes over 149 * limit (this parameter determines the steady-state burst 150 * size when a class is running over its limit). 151 * 152 * Maxidle and offtime have to be computed from the following: If the 153 * average packet size is s, the bandwidth fraction allocated to this 154 * class is f, we want to allow b packet bursts, and the gain of the 155 * averaging filter is g (= 1 - 2^(-RM_FILTER_GAIN)), then: 156 * 157 * ptime = s * nsPerByte * (1 - f) / f 158 * maxidle = ptime * (1 - g^b) / g^b 159 * minidle = -ptime * (1 / (f - 1)) 160 * offtime = ptime * (1 + 1/(1 - g) * (1 - g^(b - 1)) / g^(b - 1) 161 * 162 * Operationally, it's convenient to specify maxidle & offtime in units 163 * independent of the link bandwidth so the maxidle & offtime passed to 164 * this routine are the above values multiplied by 8*f/(1000*nsPerByte). 165 * (The constant factor is a scale factor needed to make the parameters 166 * integers. This scaling also means that the 'unscaled' values of 167 * maxidle*nsecPerByte/8 and offtime*nsecPerByte/8 will be in microseconds, 168 * not nanoseconds.) Also note that the 'idle' filter computation keeps 169 * an estimate scaled upward by 2^RM_FILTER_GAIN so the passed value of 170 * maxidle also must be scaled upward by this value. Thus, the passed 171 * values for maxidle and offtime can be computed as follows: 172 * 173 * maxidle = maxidle * 2^RM_FILTER_GAIN * 8 / (1000 * nsecPerByte) 174 * offtime = offtime * 8 / (1000 * nsecPerByte) 175 * 176 * When USE_HRTIME is employed, then maxidle and offtime become: 177 * maxidle = maxilde * (8.0 / nsecPerByte); 178 * offtime = offtime * (8.0 / nsecPerByte); 179 */ 180 struct rm_class * 181 rmc_newclass(int pri, struct rm_ifdat *ifd, u_int nsecPerByte, 182 void (*action)(rm_class_t *, rm_class_t *), int maxq, 183 struct rm_class *parent, struct rm_class *borrow, u_int maxidle, 184 int minidle, u_int offtime, int pktsize, int flags) 185 { 186 struct rm_class *cl; 187 struct rm_class *peer; 188 int s; 189 190 if (pri >= RM_MAXPRIO) 191 return (NULL); 192 #ifndef ALTQ_RED 193 if (flags & RMCF_RED) { 194 #ifdef ALTQ_DEBUG 195 printf("rmc_newclass: RED not configured for CBQ!\n"); 196 #endif 197 return (NULL); 198 } 199 #endif 200 #ifndef ALTQ_RIO 201 if (flags & RMCF_RIO) { 202 #ifdef ALTQ_DEBUG 203 printf("rmc_newclass: RIO not configured for CBQ!\n"); 204 #endif 205 return (NULL); 206 } 207 #endif 208 #ifndef ALTQ_CODEL 209 if (flags & RMCF_CODEL) { 210 #ifdef ALTQ_DEBUG 211 printf("rmc_newclass: CODEL not configured for CBQ!\n"); 212 #endif 213 return (NULL); 214 } 215 #endif 216 217 cl = malloc(sizeof(struct rm_class), M_DEVBUF, M_NOWAIT | M_ZERO); 218 if (cl == NULL) 219 return (NULL); 220 CALLOUT_INIT(&cl->callout_); 221 cl->q_ = malloc(sizeof(class_queue_t), M_DEVBUF, M_NOWAIT | M_ZERO); 222 if (cl->q_ == NULL) { 223 free(cl, M_DEVBUF); 224 return (NULL); 225 } 226 227 /* 228 * Class initialization. 229 */ 230 cl->children_ = NULL; 231 cl->parent_ = parent; 232 cl->borrow_ = borrow; 233 cl->leaf_ = 1; 234 cl->ifdat_ = ifd; 235 cl->pri_ = pri; 236 cl->allotment_ = RM_NS_PER_SEC / nsecPerByte; /* Bytes per sec */ 237 cl->depth_ = 0; 238 cl->qthresh_ = 0; 239 cl->ns_per_byte_ = nsecPerByte; 240 241 qlimit(cl->q_) = maxq; 242 qtype(cl->q_) = Q_DROPHEAD; 243 qlen(cl->q_) = 0; 244 cl->flags_ = flags; 245 246 #if 1 /* minidle is also scaled in ALTQ */ 247 cl->minidle_ = (minidle * (int)nsecPerByte) / 8; 248 if (cl->minidle_ > 0) 249 cl->minidle_ = 0; 250 #else 251 cl->minidle_ = minidle; 252 #endif 253 cl->maxidle_ = (maxidle * nsecPerByte) / 8; 254 if (cl->maxidle_ == 0) 255 cl->maxidle_ = 1; 256 #if 1 /* offtime is also scaled in ALTQ */ 257 cl->avgidle_ = cl->maxidle_; 258 cl->offtime_ = ((offtime * nsecPerByte) / 8) >> RM_FILTER_GAIN; 259 if (cl->offtime_ == 0) 260 cl->offtime_ = 1; 261 #else 262 cl->avgidle_ = 0; 263 cl->offtime_ = (offtime * nsecPerByte) / 8; 264 #endif 265 cl->overlimit = action; 266 267 #ifdef ALTQ_RED 268 if (flags & (RMCF_RED|RMCF_RIO)) { 269 int red_flags, red_pkttime; 270 271 red_flags = 0; 272 if (flags & RMCF_ECN) 273 red_flags |= REDF_ECN; 274 if (flags & RMCF_FLOWVALVE) 275 red_flags |= REDF_FLOWVALVE; 276 #ifdef ALTQ_RIO 277 if (flags & RMCF_CLEARDSCP) 278 red_flags |= RIOF_CLEARDSCP; 279 #endif 280 red_pkttime = nsecPerByte * pktsize / 1000; 281 282 if (flags & RMCF_RED) { 283 cl->red_ = red_alloc(0, 0, 284 qlimit(cl->q_) * 10/100, 285 qlimit(cl->q_) * 30/100, 286 red_flags, red_pkttime); 287 if (cl->red_ != NULL) 288 qtype(cl->q_) = Q_RED; 289 } 290 #ifdef ALTQ_RIO 291 else { 292 cl->red_ = (red_t *)rio_alloc(0, NULL, 293 red_flags, red_pkttime); 294 if (cl->red_ != NULL) 295 qtype(cl->q_) = Q_RIO; 296 } 297 #endif 298 } 299 #endif /* ALTQ_RED */ 300 #ifdef ALTQ_CODEL 301 if (flags & RMCF_CODEL) { 302 cl->codel_ = codel_alloc(5, 100, 0); 303 if (cl->codel_ != NULL) 304 qtype(cl->q_) = Q_CODEL; 305 } 306 #endif 307 308 /* 309 * put the class into the class tree 310 */ 311 s = splnet(); 312 IFQ_LOCK(ifd->ifq_); 313 if ((peer = ifd->active_[pri]) != NULL) { 314 /* find the last class at this pri */ 315 cl->peer_ = peer; 316 while (peer->peer_ != ifd->active_[pri]) 317 peer = peer->peer_; 318 peer->peer_ = cl; 319 } else { 320 ifd->active_[pri] = cl; 321 cl->peer_ = cl; 322 } 323 324 if (cl->parent_) { 325 cl->next_ = parent->children_; 326 parent->children_ = cl; 327 parent->leaf_ = 0; 328 } 329 330 /* 331 * Compute the depth of this class and its ancestors in the class 332 * hierarchy. 333 */ 334 rmc_depth_compute(cl); 335 336 /* 337 * If CBQ's WRR is enabled, then initialize the class WRR state. 338 */ 339 if (ifd->wrr_) { 340 ifd->num_[pri]++; 341 ifd->alloc_[pri] += cl->allotment_; 342 rmc_wrr_set_weights(ifd); 343 } 344 IFQ_UNLOCK(ifd->ifq_); 345 splx(s); 346 return (cl); 347 } 348 349 int 350 rmc_modclass(struct rm_class *cl, u_int nsecPerByte, int maxq, u_int maxidle, 351 int minidle, u_int offtime, int pktsize) 352 { 353 struct rm_ifdat *ifd; 354 u_int old_allotment; 355 int s; 356 357 ifd = cl->ifdat_; 358 old_allotment = cl->allotment_; 359 360 s = splnet(); 361 IFQ_LOCK(ifd->ifq_); 362 cl->allotment_ = RM_NS_PER_SEC / nsecPerByte; /* Bytes per sec */ 363 cl->qthresh_ = 0; 364 cl->ns_per_byte_ = nsecPerByte; 365 366 qlimit(cl->q_) = maxq; 367 368 #if 1 /* minidle is also scaled in ALTQ */ 369 cl->minidle_ = (minidle * nsecPerByte) / 8; 370 if (cl->minidle_ > 0) 371 cl->minidle_ = 0; 372 #else 373 cl->minidle_ = minidle; 374 #endif 375 cl->maxidle_ = (maxidle * nsecPerByte) / 8; 376 if (cl->maxidle_ == 0) 377 cl->maxidle_ = 1; 378 #if 1 /* offtime is also scaled in ALTQ */ 379 cl->avgidle_ = cl->maxidle_; 380 cl->offtime_ = ((offtime * nsecPerByte) / 8) >> RM_FILTER_GAIN; 381 if (cl->offtime_ == 0) 382 cl->offtime_ = 1; 383 #else 384 cl->avgidle_ = 0; 385 cl->offtime_ = (offtime * nsecPerByte) / 8; 386 #endif 387 388 /* 389 * If CBQ's WRR is enabled, then initialize the class WRR state. 390 */ 391 if (ifd->wrr_) { 392 ifd->alloc_[cl->pri_] += cl->allotment_ - old_allotment; 393 rmc_wrr_set_weights(ifd); 394 } 395 IFQ_UNLOCK(ifd->ifq_); 396 splx(s); 397 return (0); 398 } 399 400 /* 401 * static void 402 * rmc_wrr_set_weights(struct rm_ifdat *ifdat) - This function computes 403 * the appropriate run robin weights for the CBQ weighted round robin 404 * algorithm. 405 * 406 * Returns: NONE 407 */ 408 409 static void 410 rmc_wrr_set_weights(struct rm_ifdat *ifd) 411 { 412 int i; 413 struct rm_class *cl, *clh; 414 415 for (i = 0; i < RM_MAXPRIO; i++) { 416 /* 417 * This is inverted from that of the simulator to 418 * maintain precision. 419 */ 420 if (ifd->num_[i] == 0) 421 ifd->M_[i] = 0; 422 else 423 ifd->M_[i] = ifd->alloc_[i] / 424 (ifd->num_[i] * ifd->maxpkt_); 425 /* 426 * Compute the weighted allotment for each class. 427 * This takes the expensive div instruction out 428 * of the main loop for the wrr scheduling path. 429 * These only get recomputed when a class comes or 430 * goes. 431 */ 432 if (ifd->active_[i] != NULL) { 433 clh = cl = ifd->active_[i]; 434 do { 435 /* safe-guard for slow link or alloc_ == 0 */ 436 if (ifd->M_[i] == 0) 437 cl->w_allotment_ = 0; 438 else 439 cl->w_allotment_ = cl->allotment_ / 440 ifd->M_[i]; 441 cl = cl->peer_; 442 } while ((cl != NULL) && (cl != clh)); 443 } 444 } 445 } 446 447 int 448 rmc_get_weight(struct rm_ifdat *ifd, int pri) 449 { 450 if ((pri >= 0) && (pri < RM_MAXPRIO)) 451 return (ifd->M_[pri]); 452 else 453 return (0); 454 } 455 456 /* 457 * static void 458 * rmc_depth_compute(struct rm_class *cl) - This function computes the 459 * appropriate depth of class 'cl' and its ancestors. 460 * 461 * Returns: NONE 462 */ 463 464 static void 465 rmc_depth_compute(struct rm_class *cl) 466 { 467 rm_class_t *t = cl, *p; 468 469 /* 470 * Recompute the depth for the branch of the tree. 471 */ 472 while (t != NULL) { 473 p = t->parent_; 474 if (p && (t->depth_ >= p->depth_)) { 475 p->depth_ = t->depth_ + 1; 476 t = p; 477 } else 478 t = NULL; 479 } 480 } 481 482 /* 483 * static void 484 * rmc_depth_recompute(struct rm_class *cl) - This function re-computes 485 * the depth of the tree after a class has been deleted. 486 * 487 * Returns: NONE 488 */ 489 490 static void 491 rmc_depth_recompute(rm_class_t *cl) 492 { 493 #if 1 /* ALTQ */ 494 rm_class_t *p, *t; 495 496 p = cl; 497 while (p != NULL) { 498 if ((t = p->children_) == NULL) { 499 p->depth_ = 0; 500 } else { 501 int cdepth = 0; 502 503 while (t != NULL) { 504 if (t->depth_ > cdepth) 505 cdepth = t->depth_; 506 t = t->next_; 507 } 508 509 if (p->depth_ == cdepth + 1) 510 /* no change to this parent */ 511 return; 512 513 p->depth_ = cdepth + 1; 514 } 515 516 p = p->parent_; 517 } 518 #else 519 rm_class_t *t; 520 521 if (cl->depth_ >= 1) { 522 if (cl->children_ == NULL) { 523 cl->depth_ = 0; 524 } else if ((t = cl->children_) != NULL) { 525 while (t != NULL) { 526 if (t->children_ != NULL) 527 rmc_depth_recompute(t); 528 t = t->next_; 529 } 530 } else 531 rmc_depth_compute(cl); 532 } 533 #endif 534 } 535 536 /* 537 * void 538 * rmc_delete_class(struct rm_ifdat *ifdat, struct rm_class *cl) - This 539 * function deletes a class from the link-sharing structure and frees 540 * all resources associated with the class. 541 * 542 * Returns: NONE 543 */ 544 545 void 546 rmc_delete_class(struct rm_ifdat *ifd, struct rm_class *cl) 547 { 548 struct rm_class *p, *head, *previous; 549 int s; 550 551 ASSERT(cl->children_ == NULL); 552 553 if (cl->sleeping_) 554 CALLOUT_STOP(&cl->callout_); 555 556 s = splnet(); 557 IFQ_LOCK(ifd->ifq_); 558 /* 559 * Free packets in the packet queue. 560 * XXX - this may not be a desired behavior. Packets should be 561 * re-queued. 562 */ 563 rmc_dropall(cl); 564 565 /* 566 * If the class has a parent, then remove the class from the 567 * class from the parent's children chain. 568 */ 569 if (cl->parent_ != NULL) { 570 head = cl->parent_->children_; 571 p = previous = head; 572 if (head->next_ == NULL) { 573 ASSERT(head == cl); 574 cl->parent_->children_ = NULL; 575 cl->parent_->leaf_ = 1; 576 } else while (p != NULL) { 577 if (p == cl) { 578 if (cl == head) 579 cl->parent_->children_ = cl->next_; 580 else 581 previous->next_ = cl->next_; 582 cl->next_ = NULL; 583 p = NULL; 584 } else { 585 previous = p; 586 p = p->next_; 587 } 588 } 589 } 590 591 /* 592 * Delete class from class priority peer list. 593 */ 594 if ((p = ifd->active_[cl->pri_]) != NULL) { 595 /* 596 * If there is more than one member of this priority 597 * level, then look for class(cl) in the priority level. 598 */ 599 if (p != p->peer_) { 600 while (p->peer_ != cl) 601 p = p->peer_; 602 p->peer_ = cl->peer_; 603 604 if (ifd->active_[cl->pri_] == cl) 605 ifd->active_[cl->pri_] = cl->peer_; 606 } else { 607 ASSERT(p == cl); 608 ifd->active_[cl->pri_] = NULL; 609 } 610 } 611 612 /* 613 * Recompute the WRR weights. 614 */ 615 if (ifd->wrr_) { 616 ifd->alloc_[cl->pri_] -= cl->allotment_; 617 ifd->num_[cl->pri_]--; 618 rmc_wrr_set_weights(ifd); 619 } 620 621 /* 622 * Re-compute the depth of the tree. 623 */ 624 #if 1 /* ALTQ */ 625 rmc_depth_recompute(cl->parent_); 626 #else 627 rmc_depth_recompute(ifd->root_); 628 #endif 629 630 IFQ_UNLOCK(ifd->ifq_); 631 splx(s); 632 633 /* 634 * Free the class structure. 635 */ 636 if (cl->red_ != NULL) { 637 #ifdef ALTQ_RIO 638 if (q_is_rio(cl->q_)) 639 rio_destroy((rio_t *)cl->red_); 640 #endif 641 #ifdef ALTQ_RED 642 if (q_is_red(cl->q_)) 643 red_destroy(cl->red_); 644 #endif 645 #ifdef ALTQ_CODEL 646 if (q_is_codel(cl->q_)) 647 codel_destroy(cl->codel_); 648 #endif 649 } 650 free(cl->q_, M_DEVBUF); 651 free(cl, M_DEVBUF); 652 } 653 654 /* 655 * void 656 * rmc_init(...) - Initialize the resource management data structures 657 * associated with the output portion of interface 'ifp'. 'ifd' is 658 * where the structures will be built (for backwards compatibility, the 659 * structures aren't kept in the ifnet struct). 'nsecPerByte' 660 * gives the link speed (inverse of bandwidth) in nanoseconds/byte. 661 * 'restart' is the driver-specific routine that the generic 'delay 662 * until under limit' action will call to restart output. `maxq' 663 * is the queue size of the 'link' & 'default' classes. 'maxqueued' 664 * is the maximum number of packets that the resource management 665 * code will allow to be queued 'downstream' (this is typically 1). 666 * 667 * Returns: NONE 668 */ 669 670 void 671 rmc_init(struct ifaltq *ifq, struct rm_ifdat *ifd, u_int nsecPerByte, 672 void (*restart)(struct ifaltq *), int maxq, int maxqueued, u_int maxidle, 673 int minidle, u_int offtime, int flags) 674 { 675 int i, mtu; 676 677 /* 678 * Initialize the CBQ tracing/debug facility. 679 */ 680 CBQTRACEINIT(); 681 682 bzero((char *)ifd, sizeof (*ifd)); 683 mtu = ifq->altq_ifp->if_mtu; 684 ifd->ifq_ = ifq; 685 ifd->restart = restart; 686 ifd->maxqueued_ = maxqueued; 687 ifd->ns_per_byte_ = nsecPerByte; 688 ifd->maxpkt_ = mtu; 689 ifd->wrr_ = (flags & RMCF_WRR) ? 1 : 0; 690 ifd->efficient_ = (flags & RMCF_EFFICIENT) ? 1 : 0; 691 #if 1 692 ifd->maxiftime_ = mtu * nsecPerByte / 1000 * 16; 693 if (mtu * nsecPerByte > 10 * 1000000) 694 ifd->maxiftime_ /= 4; 695 #endif 696 697 reset_cutoff(ifd); 698 CBQTRACE(rmc_init, 'INIT', ifd->cutoff_); 699 700 /* 701 * Initialize the CBQ's WRR state. 702 */ 703 for (i = 0; i < RM_MAXPRIO; i++) { 704 ifd->alloc_[i] = 0; 705 ifd->M_[i] = 0; 706 ifd->num_[i] = 0; 707 ifd->na_[i] = 0; 708 ifd->active_[i] = NULL; 709 } 710 711 /* 712 * Initialize current packet state. 713 */ 714 ifd->qi_ = 0; 715 ifd->qo_ = 0; 716 for (i = 0; i < RM_MAXQUEUED; i++) { 717 ifd->class_[i] = NULL; 718 ifd->curlen_[i] = 0; 719 ifd->borrowed_[i] = NULL; 720 } 721 722 /* 723 * Create the root class of the link-sharing structure. 724 */ 725 if ((ifd->root_ = rmc_newclass(0, ifd, 726 nsecPerByte, 727 rmc_root_overlimit, maxq, 0, 0, 728 maxidle, minidle, offtime, 729 0, 0)) == NULL) { 730 printf("rmc_init: root class not allocated\n"); 731 return ; 732 } 733 ifd->root_->depth_ = 0; 734 } 735 736 /* 737 * void 738 * rmc_queue_packet(struct rm_class *cl, mbuf_t *m) - Add packet given by 739 * mbuf 'm' to queue for resource class 'cl'. This routine is called 740 * by a driver's if_output routine. This routine must be called with 741 * output packet completion interrupts locked out (to avoid racing with 742 * rmc_dequeue_next). 743 * 744 * Returns: 0 on successful queueing 745 * -1 when packet drop occurs 746 */ 747 int 748 rmc_queue_packet(struct rm_class *cl, mbuf_t *m) 749 { 750 struct timeval now; 751 struct rm_ifdat *ifd = cl->ifdat_; 752 int cpri = cl->pri_; 753 int is_empty = qempty(cl->q_); 754 755 RM_GETTIME(now); 756 if (ifd->cutoff_ > 0) { 757 if (TV_LT(&cl->undertime_, &now)) { 758 if (ifd->cutoff_ > cl->depth_) 759 ifd->cutoff_ = cl->depth_; 760 CBQTRACE(rmc_queue_packet, 'ffoc', cl->depth_); 761 } 762 #if 1 /* ALTQ */ 763 else { 764 /* 765 * the class is overlimit. if the class has 766 * underlimit ancestors, set cutoff to the lowest 767 * depth among them. 768 */ 769 struct rm_class *borrow = cl->borrow_; 770 771 while (borrow != NULL && 772 borrow->depth_ < ifd->cutoff_) { 773 if (TV_LT(&borrow->undertime_, &now)) { 774 ifd->cutoff_ = borrow->depth_; 775 CBQTRACE(rmc_queue_packet, 'ffob', ifd->cutoff_); 776 break; 777 } 778 borrow = borrow->borrow_; 779 } 780 } 781 #else /* !ALTQ */ 782 else if ((ifd->cutoff_ > 1) && cl->borrow_) { 783 if (TV_LT(&cl->borrow_->undertime_, &now)) { 784 ifd->cutoff_ = cl->borrow_->depth_; 785 CBQTRACE(rmc_queue_packet, 'ffob', 786 cl->borrow_->depth_); 787 } 788 } 789 #endif /* !ALTQ */ 790 } 791 792 if (_rmc_addq(cl, m) < 0) 793 /* failed */ 794 return (-1); 795 796 if (is_empty) { 797 CBQTRACE(rmc_queue_packet, 'ytpe', cl->stats_.handle); 798 ifd->na_[cpri]++; 799 } 800 801 if (qlen(cl->q_) > qlimit(cl->q_)) { 802 /* note: qlimit can be set to 0 or 1 */ 803 rmc_drop_action(cl); 804 return (-1); 805 } 806 return (0); 807 } 808 809 /* 810 * void 811 * rmc_tl_satisfied(struct rm_ifdat *ifd, struct timeval *now) - Check all 812 * classes to see if there are satified. 813 */ 814 815 static void 816 rmc_tl_satisfied(struct rm_ifdat *ifd, struct timeval *now) 817 { 818 int i; 819 rm_class_t *p, *bp; 820 821 for (i = RM_MAXPRIO - 1; i >= 0; i--) { 822 if ((bp = ifd->active_[i]) != NULL) { 823 p = bp; 824 do { 825 if (!rmc_satisfied(p, now)) { 826 ifd->cutoff_ = p->depth_; 827 return; 828 } 829 p = p->peer_; 830 } while (p != bp); 831 } 832 } 833 834 reset_cutoff(ifd); 835 } 836 837 /* 838 * rmc_satisfied - Return 1 of the class is satisfied. O, otherwise. 839 */ 840 841 static int 842 rmc_satisfied(struct rm_class *cl, struct timeval *now) 843 { 844 rm_class_t *p; 845 846 if (cl == NULL) 847 return (1); 848 if (TV_LT(now, &cl->undertime_)) 849 return (1); 850 if (cl->depth_ == 0) { 851 if (!cl->sleeping_ && (qlen(cl->q_) > cl->qthresh_)) 852 return (0); 853 else 854 return (1); 855 } 856 if (cl->children_ != NULL) { 857 p = cl->children_; 858 while (p != NULL) { 859 if (!rmc_satisfied(p, now)) 860 return (0); 861 p = p->next_; 862 } 863 } 864 865 return (1); 866 } 867 868 /* 869 * Return 1 if class 'cl' is under limit or can borrow from a parent, 870 * 0 if overlimit. As a side-effect, this routine will invoke the 871 * class overlimit action if the class if overlimit. 872 */ 873 874 static int 875 rmc_under_limit(struct rm_class *cl, struct timeval *now) 876 { 877 rm_class_t *p = cl; 878 rm_class_t *top; 879 struct rm_ifdat *ifd = cl->ifdat_; 880 881 ifd->borrowed_[ifd->qi_] = NULL; 882 /* 883 * If cl is the root class, then always return that it is 884 * underlimit. Otherwise, check to see if the class is underlimit. 885 */ 886 if (cl->parent_ == NULL) 887 return (1); 888 889 if (cl->sleeping_) { 890 if (TV_LT(now, &cl->undertime_)) 891 return (0); 892 893 CALLOUT_STOP(&cl->callout_); 894 cl->sleeping_ = 0; 895 cl->undertime_.tv_sec = 0; 896 return (1); 897 } 898 899 top = NULL; 900 while (cl->undertime_.tv_sec && TV_LT(now, &cl->undertime_)) { 901 if (((cl = cl->borrow_) == NULL) || 902 (cl->depth_ > ifd->cutoff_)) { 903 #ifdef ADJUST_CUTOFF 904 if (cl != NULL) 905 /* cutoff is taking effect, just 906 return false without calling 907 the delay action. */ 908 return (0); 909 #endif 910 #ifdef BORROW_OFFTIME 911 /* 912 * check if the class can borrow offtime too. 913 * borrow offtime from the top of the borrow 914 * chain if the top class is not overloaded. 915 */ 916 if (cl != NULL) { 917 /* cutoff is taking effect, use this class as top. */ 918 top = cl; 919 CBQTRACE(rmc_under_limit, 'ffou', ifd->cutoff_); 920 } 921 if (top != NULL && top->avgidle_ == top->minidle_) 922 top = NULL; 923 p->overtime_ = *now; 924 (p->overlimit)(p, top); 925 #else 926 p->overtime_ = *now; 927 (p->overlimit)(p, NULL); 928 #endif 929 return (0); 930 } 931 top = cl; 932 } 933 934 if (cl != p) 935 ifd->borrowed_[ifd->qi_] = cl; 936 return (1); 937 } 938 939 /* 940 * _rmc_wrr_dequeue_next() - This is scheduler for WRR as opposed to 941 * Packet-by-packet round robin. 942 * 943 * The heart of the weighted round-robin scheduler, which decides which 944 * class next gets to send a packet. Highest priority first, then 945 * weighted round-robin within priorites. 946 * 947 * Each able-to-send class gets to send until its byte allocation is 948 * exhausted. Thus, the active pointer is only changed after a class has 949 * exhausted its allocation. 950 * 951 * If the scheduler finds no class that is underlimit or able to borrow, 952 * then the first class found that had a nonzero queue and is allowed to 953 * borrow gets to send. 954 */ 955 956 static mbuf_t * 957 _rmc_wrr_dequeue_next(struct rm_ifdat *ifd, int op) 958 { 959 struct rm_class *cl = NULL, *first = NULL; 960 u_int deficit; 961 int cpri; 962 mbuf_t *m; 963 struct timeval now; 964 965 RM_GETTIME(now); 966 967 /* 968 * if the driver polls the top of the queue and then removes 969 * the polled packet, we must return the same packet. 970 */ 971 if (op == ALTDQ_REMOVE && ifd->pollcache_) { 972 cl = ifd->pollcache_; 973 cpri = cl->pri_; 974 if (ifd->efficient_) { 975 /* check if this class is overlimit */ 976 if (cl->undertime_.tv_sec != 0 && 977 rmc_under_limit(cl, &now) == 0) 978 first = cl; 979 } 980 ifd->pollcache_ = NULL; 981 goto _wrr_out; 982 } 983 else { 984 /* mode == ALTDQ_POLL || pollcache == NULL */ 985 ifd->pollcache_ = NULL; 986 ifd->borrowed_[ifd->qi_] = NULL; 987 } 988 #ifdef ADJUST_CUTOFF 989 _again: 990 #endif 991 for (cpri = RM_MAXPRIO - 1; cpri >= 0; cpri--) { 992 if (ifd->na_[cpri] == 0) 993 continue; 994 deficit = 0; 995 /* 996 * Loop through twice for a priority level, if some class 997 * was unable to send a packet the first round because 998 * of the weighted round-robin mechanism. 999 * During the second loop at this level, deficit==2. 1000 * (This second loop is not needed if for every class, 1001 * "M[cl->pri_])" times "cl->allotment" is greater than 1002 * the byte size for the largest packet in the class.) 1003 */ 1004 _wrr_loop: 1005 cl = ifd->active_[cpri]; 1006 ASSERT(cl != NULL); 1007 do { 1008 if ((deficit < 2) && (cl->bytes_alloc_ <= 0)) 1009 cl->bytes_alloc_ += cl->w_allotment_; 1010 if (!qempty(cl->q_)) { 1011 if ((cl->undertime_.tv_sec == 0) || 1012 rmc_under_limit(cl, &now)) { 1013 if (cl->bytes_alloc_ > 0 || deficit > 1) 1014 goto _wrr_out; 1015 1016 /* underlimit but no alloc */ 1017 deficit = 1; 1018 #if 1 1019 ifd->borrowed_[ifd->qi_] = NULL; 1020 #endif 1021 } 1022 else if (first == NULL && cl->borrow_ != NULL) 1023 first = cl; /* borrowing candidate */ 1024 } 1025 1026 cl->bytes_alloc_ = 0; 1027 cl = cl->peer_; 1028 } while (cl != ifd->active_[cpri]); 1029 1030 if (deficit == 1) { 1031 /* first loop found an underlimit class with deficit */ 1032 /* Loop on same priority level, with new deficit. */ 1033 deficit = 2; 1034 goto _wrr_loop; 1035 } 1036 } 1037 1038 #ifdef ADJUST_CUTOFF 1039 /* 1040 * no underlimit class found. if cutoff is taking effect, 1041 * increase cutoff and try again. 1042 */ 1043 if (first != NULL && ifd->cutoff_ < ifd->root_->depth_) { 1044 ifd->cutoff_++; 1045 CBQTRACE(_rmc_wrr_dequeue_next, 'ojda', ifd->cutoff_); 1046 goto _again; 1047 } 1048 #endif /* ADJUST_CUTOFF */ 1049 /* 1050 * If LINK_EFFICIENCY is turned on, then the first overlimit 1051 * class we encounter will send a packet if all the classes 1052 * of the link-sharing structure are overlimit. 1053 */ 1054 reset_cutoff(ifd); 1055 CBQTRACE(_rmc_wrr_dequeue_next, 'otsr', ifd->cutoff_); 1056 1057 if (!ifd->efficient_ || first == NULL) 1058 return (NULL); 1059 1060 cl = first; 1061 cpri = cl->pri_; 1062 #if 0 /* too time-consuming for nothing */ 1063 if (cl->sleeping_) 1064 CALLOUT_STOP(&cl->callout_); 1065 cl->sleeping_ = 0; 1066 cl->undertime_.tv_sec = 0; 1067 #endif 1068 ifd->borrowed_[ifd->qi_] = cl->borrow_; 1069 ifd->cutoff_ = cl->borrow_->depth_; 1070 1071 /* 1072 * Deque the packet and do the book keeping... 1073 */ 1074 _wrr_out: 1075 if (op == ALTDQ_REMOVE) { 1076 m = _rmc_getq(cl); 1077 if (m == NULL) 1078 panic("_rmc_wrr_dequeue_next"); 1079 if (qempty(cl->q_)) 1080 ifd->na_[cpri]--; 1081 1082 /* 1083 * Update class statistics and link data. 1084 */ 1085 if (cl->bytes_alloc_ > 0) 1086 cl->bytes_alloc_ -= m_pktlen(m); 1087 1088 if ((cl->bytes_alloc_ <= 0) || first == cl) 1089 ifd->active_[cl->pri_] = cl->peer_; 1090 else 1091 ifd->active_[cl->pri_] = cl; 1092 1093 ifd->class_[ifd->qi_] = cl; 1094 ifd->curlen_[ifd->qi_] = m_pktlen(m); 1095 ifd->now_[ifd->qi_] = now; 1096 ifd->qi_ = (ifd->qi_ + 1) % ifd->maxqueued_; 1097 ifd->queued_++; 1098 } else { 1099 /* mode == ALTDQ_PPOLL */ 1100 m = _rmc_pollq(cl); 1101 ifd->pollcache_ = cl; 1102 } 1103 return (m); 1104 } 1105 1106 /* 1107 * Dequeue & return next packet from the highest priority class that 1108 * has a packet to send & has enough allocation to send it. This 1109 * routine is called by a driver whenever it needs a new packet to 1110 * output. 1111 */ 1112 static mbuf_t * 1113 _rmc_prr_dequeue_next(struct rm_ifdat *ifd, int op) 1114 { 1115 mbuf_t *m; 1116 int cpri; 1117 struct rm_class *cl, *first = NULL; 1118 struct timeval now; 1119 1120 RM_GETTIME(now); 1121 1122 /* 1123 * if the driver polls the top of the queue and then removes 1124 * the polled packet, we must return the same packet. 1125 */ 1126 if (op == ALTDQ_REMOVE && ifd->pollcache_) { 1127 cl = ifd->pollcache_; 1128 cpri = cl->pri_; 1129 ifd->pollcache_ = NULL; 1130 goto _prr_out; 1131 } else { 1132 /* mode == ALTDQ_POLL || pollcache == NULL */ 1133 ifd->pollcache_ = NULL; 1134 ifd->borrowed_[ifd->qi_] = NULL; 1135 } 1136 #ifdef ADJUST_CUTOFF 1137 _again: 1138 #endif 1139 for (cpri = RM_MAXPRIO - 1; cpri >= 0; cpri--) { 1140 if (ifd->na_[cpri] == 0) 1141 continue; 1142 cl = ifd->active_[cpri]; 1143 ASSERT(cl != NULL); 1144 do { 1145 if (!qempty(cl->q_)) { 1146 if ((cl->undertime_.tv_sec == 0) || 1147 rmc_under_limit(cl, &now)) 1148 goto _prr_out; 1149 if (first == NULL && cl->borrow_ != NULL) 1150 first = cl; 1151 } 1152 cl = cl->peer_; 1153 } while (cl != ifd->active_[cpri]); 1154 } 1155 1156 #ifdef ADJUST_CUTOFF 1157 /* 1158 * no underlimit class found. if cutoff is taking effect, increase 1159 * cutoff and try again. 1160 */ 1161 if (first != NULL && ifd->cutoff_ < ifd->root_->depth_) { 1162 ifd->cutoff_++; 1163 goto _again; 1164 } 1165 #endif /* ADJUST_CUTOFF */ 1166 /* 1167 * If LINK_EFFICIENCY is turned on, then the first overlimit 1168 * class we encounter will send a packet if all the classes 1169 * of the link-sharing structure are overlimit. 1170 */ 1171 reset_cutoff(ifd); 1172 if (!ifd->efficient_ || first == NULL) 1173 return (NULL); 1174 1175 cl = first; 1176 cpri = cl->pri_; 1177 #if 0 /* too time-consuming for nothing */ 1178 if (cl->sleeping_) 1179 CALLOUT_STOP(&cl->callout_); 1180 cl->sleeping_ = 0; 1181 cl->undertime_.tv_sec = 0; 1182 #endif 1183 ifd->borrowed_[ifd->qi_] = cl->borrow_; 1184 ifd->cutoff_ = cl->borrow_->depth_; 1185 1186 /* 1187 * Deque the packet and do the book keeping... 1188 */ 1189 _prr_out: 1190 if (op == ALTDQ_REMOVE) { 1191 m = _rmc_getq(cl); 1192 if (m == NULL) 1193 panic("_rmc_prr_dequeue_next"); 1194 if (qempty(cl->q_)) 1195 ifd->na_[cpri]--; 1196 1197 ifd->active_[cpri] = cl->peer_; 1198 1199 ifd->class_[ifd->qi_] = cl; 1200 ifd->curlen_[ifd->qi_] = m_pktlen(m); 1201 ifd->now_[ifd->qi_] = now; 1202 ifd->qi_ = (ifd->qi_ + 1) % ifd->maxqueued_; 1203 ifd->queued_++; 1204 } else { 1205 /* mode == ALTDQ_POLL */ 1206 m = _rmc_pollq(cl); 1207 ifd->pollcache_ = cl; 1208 } 1209 return (m); 1210 } 1211 1212 /* 1213 * mbuf_t * 1214 * rmc_dequeue_next(struct rm_ifdat *ifd, struct timeval *now) - this function 1215 * is invoked by the packet driver to get the next packet to be 1216 * dequeued and output on the link. If WRR is enabled, then the 1217 * WRR dequeue next routine will determine the next packet to sent. 1218 * Otherwise, packet-by-packet round robin is invoked. 1219 * 1220 * Returns: NULL, if a packet is not available or if all 1221 * classes are overlimit. 1222 * 1223 * Otherwise, Pointer to the next packet. 1224 */ 1225 1226 mbuf_t * 1227 rmc_dequeue_next(struct rm_ifdat *ifd, int mode) 1228 { 1229 if (ifd->queued_ >= ifd->maxqueued_) 1230 return (NULL); 1231 else if (ifd->wrr_) 1232 return (_rmc_wrr_dequeue_next(ifd, mode)); 1233 else 1234 return (_rmc_prr_dequeue_next(ifd, mode)); 1235 } 1236 1237 /* 1238 * Update the utilization estimate for the packet that just completed. 1239 * The packet's class & the parent(s) of that class all get their 1240 * estimators updated. This routine is called by the driver's output- 1241 * packet-completion interrupt service routine. 1242 */ 1243 1244 /* 1245 * a macro to approximate "divide by 1000" that gives 0.000999, 1246 * if a value has enough effective digits. 1247 * (on pentium, mul takes 9 cycles but div takes 46!) 1248 */ 1249 #define NSEC_TO_USEC(t) (((t) >> 10) + ((t) >> 16) + ((t) >> 17)) 1250 void 1251 rmc_update_class_util(struct rm_ifdat *ifd) 1252 { 1253 int idle, avgidle, pktlen; 1254 int pkt_time, tidle; 1255 rm_class_t *cl, *borrowed; 1256 rm_class_t *borrows; 1257 struct timeval *nowp; 1258 1259 /* 1260 * Get the most recent completed class. 1261 */ 1262 if ((cl = ifd->class_[ifd->qo_]) == NULL) 1263 return; 1264 1265 pktlen = ifd->curlen_[ifd->qo_]; 1266 borrowed = ifd->borrowed_[ifd->qo_]; 1267 borrows = borrowed; 1268 1269 PKTCNTR_ADD(&cl->stats_.xmit_cnt, pktlen); 1270 1271 /* 1272 * Run estimator on class and its ancestors. 1273 */ 1274 /* 1275 * rm_update_class_util is designed to be called when the 1276 * transfer is completed from a xmit complete interrupt, 1277 * but most drivers don't implement an upcall for that. 1278 * so, just use estimated completion time. 1279 * as a result, ifd->qi_ and ifd->qo_ are always synced. 1280 */ 1281 nowp = &ifd->now_[ifd->qo_]; 1282 /* get pkt_time (for link) in usec */ 1283 #if 1 /* use approximation */ 1284 pkt_time = ifd->curlen_[ifd->qo_] * ifd->ns_per_byte_; 1285 pkt_time = NSEC_TO_USEC(pkt_time); 1286 #else 1287 pkt_time = ifd->curlen_[ifd->qo_] * ifd->ns_per_byte_ / 1000; 1288 #endif 1289 #if 1 /* ALTQ4PPP */ 1290 if (TV_LT(nowp, &ifd->ifnow_)) { 1291 int iftime; 1292 1293 /* 1294 * make sure the estimated completion time does not go 1295 * too far. it can happen when the link layer supports 1296 * data compression or the interface speed is set to 1297 * a much lower value. 1298 */ 1299 TV_DELTA(&ifd->ifnow_, nowp, iftime); 1300 if (iftime+pkt_time < ifd->maxiftime_) { 1301 TV_ADD_DELTA(&ifd->ifnow_, pkt_time, &ifd->ifnow_); 1302 } else { 1303 TV_ADD_DELTA(nowp, ifd->maxiftime_, &ifd->ifnow_); 1304 } 1305 } else { 1306 TV_ADD_DELTA(nowp, pkt_time, &ifd->ifnow_); 1307 } 1308 #else 1309 if (TV_LT(nowp, &ifd->ifnow_)) { 1310 TV_ADD_DELTA(&ifd->ifnow_, pkt_time, &ifd->ifnow_); 1311 } else { 1312 TV_ADD_DELTA(nowp, pkt_time, &ifd->ifnow_); 1313 } 1314 #endif 1315 1316 while (cl != NULL) { 1317 TV_DELTA(&ifd->ifnow_, &cl->last_, idle); 1318 if (idle >= 2000000) 1319 /* 1320 * this class is idle enough, reset avgidle. 1321 * (TV_DELTA returns 2000000 us when delta is large.) 1322 */ 1323 cl->avgidle_ = cl->maxidle_; 1324 1325 /* get pkt_time (for class) in usec */ 1326 #if 1 /* use approximation */ 1327 pkt_time = pktlen * cl->ns_per_byte_; 1328 pkt_time = NSEC_TO_USEC(pkt_time); 1329 #else 1330 pkt_time = pktlen * cl->ns_per_byte_ / 1000; 1331 #endif 1332 idle -= pkt_time; 1333 1334 avgidle = cl->avgidle_; 1335 avgidle += idle - (avgidle >> RM_FILTER_GAIN); 1336 cl->avgidle_ = avgidle; 1337 1338 /* Are we overlimit ? */ 1339 if (avgidle <= 0) { 1340 CBQTRACE(rmc_update_class_util, 'milo', cl->stats_.handle); 1341 #if 1 /* ALTQ */ 1342 /* 1343 * need some lower bound for avgidle, otherwise 1344 * a borrowing class gets unbounded penalty. 1345 */ 1346 if (avgidle < cl->minidle_) 1347 avgidle = cl->avgidle_ = cl->minidle_; 1348 #endif 1349 /* set next idle to make avgidle 0 */ 1350 tidle = pkt_time + 1351 (((1 - RM_POWER) * avgidle) >> RM_FILTER_GAIN); 1352 TV_ADD_DELTA(nowp, tidle, &cl->undertime_); 1353 ++cl->stats_.over; 1354 } else { 1355 cl->avgidle_ = 1356 (avgidle > cl->maxidle_) ? cl->maxidle_ : avgidle; 1357 cl->undertime_.tv_sec = 0; 1358 if (cl->sleeping_) { 1359 CALLOUT_STOP(&cl->callout_); 1360 cl->sleeping_ = 0; 1361 } 1362 } 1363 1364 if (borrows != NULL) { 1365 if (borrows != cl) 1366 ++cl->stats_.borrows; 1367 else 1368 borrows = NULL; 1369 } 1370 cl->last_ = ifd->ifnow_; 1371 cl->last_pkttime_ = pkt_time; 1372 1373 #if 1 1374 if (cl->parent_ == NULL) { 1375 /* take stats of root class */ 1376 PKTCNTR_ADD(&cl->stats_.xmit_cnt, pktlen); 1377 } 1378 #endif 1379 1380 cl = cl->parent_; 1381 } 1382 1383 /* 1384 * Check to see if cutoff needs to set to a new level. 1385 */ 1386 cl = ifd->class_[ifd->qo_]; 1387 if (borrowed && (ifd->cutoff_ >= borrowed->depth_)) { 1388 #if 1 /* ALTQ */ 1389 if ((qlen(cl->q_) <= 0) || TV_LT(nowp, &borrowed->undertime_)) { 1390 rmc_tl_satisfied(ifd, nowp); 1391 CBQTRACE(rmc_update_class_util, 'broe', ifd->cutoff_); 1392 } else { 1393 ifd->cutoff_ = borrowed->depth_; 1394 CBQTRACE(rmc_update_class_util, 'ffob', borrowed->depth_); 1395 } 1396 #else /* !ALTQ */ 1397 if ((qlen(cl->q_) <= 1) || TV_LT(&now, &borrowed->undertime_)) { 1398 reset_cutoff(ifd); 1399 #ifdef notdef 1400 rmc_tl_satisfied(ifd, &now); 1401 #endif 1402 CBQTRACE(rmc_update_class_util, 'broe', ifd->cutoff_); 1403 } else { 1404 ifd->cutoff_ = borrowed->depth_; 1405 CBQTRACE(rmc_update_class_util, 'ffob', borrowed->depth_); 1406 } 1407 #endif /* !ALTQ */ 1408 } 1409 1410 /* 1411 * Release class slot 1412 */ 1413 ifd->borrowed_[ifd->qo_] = NULL; 1414 ifd->class_[ifd->qo_] = NULL; 1415 ifd->qo_ = (ifd->qo_ + 1) % ifd->maxqueued_; 1416 ifd->queued_--; 1417 } 1418 1419 /* 1420 * void 1421 * rmc_drop_action(struct rm_class *cl) - Generic (not protocol-specific) 1422 * over-limit action routines. These get invoked by rmc_under_limit() 1423 * if a class with packets to send if over its bandwidth limit & can't 1424 * borrow from a parent class. 1425 * 1426 * Returns: NONE 1427 */ 1428 1429 static void 1430 rmc_drop_action(struct rm_class *cl) 1431 { 1432 struct rm_ifdat *ifd = cl->ifdat_; 1433 1434 ASSERT(qlen(cl->q_) > 0); 1435 _rmc_dropq(cl); 1436 if (qempty(cl->q_)) 1437 ifd->na_[cl->pri_]--; 1438 } 1439 1440 void rmc_dropall(struct rm_class *cl) 1441 { 1442 struct rm_ifdat *ifd = cl->ifdat_; 1443 1444 if (!qempty(cl->q_)) { 1445 _flushq(cl->q_); 1446 1447 ifd->na_[cl->pri_]--; 1448 } 1449 } 1450 1451 #if (__FreeBSD_version > 300000) 1452 /* hzto() is removed from FreeBSD-3.0 */ 1453 static int hzto(struct timeval *); 1454 1455 static int 1456 hzto(tv) 1457 struct timeval *tv; 1458 { 1459 struct timeval t2; 1460 1461 getmicrotime(&t2); 1462 t2.tv_sec = tv->tv_sec - t2.tv_sec; 1463 t2.tv_usec = tv->tv_usec - t2.tv_usec; 1464 return (tvtohz(&t2)); 1465 } 1466 #endif /* __FreeBSD_version > 300000 */ 1467 1468 /* 1469 * void 1470 * rmc_delay_action(struct rm_class *cl) - This function is the generic CBQ 1471 * delay action routine. It is invoked via rmc_under_limit when the 1472 * packet is discoverd to be overlimit. 1473 * 1474 * If the delay action is result of borrow class being overlimit, then 1475 * delay for the offtime of the borrowing class that is overlimit. 1476 * 1477 * Returns: NONE 1478 */ 1479 1480 void 1481 rmc_delay_action(struct rm_class *cl, struct rm_class *borrow) 1482 { 1483 int delay, t, extradelay; 1484 1485 cl->stats_.overactions++; 1486 TV_DELTA(&cl->undertime_, &cl->overtime_, delay); 1487 #ifndef BORROW_OFFTIME 1488 delay += cl->offtime_; 1489 #endif 1490 1491 if (!cl->sleeping_) { 1492 CBQTRACE(rmc_delay_action, 'yled', cl->stats_.handle); 1493 #ifdef BORROW_OFFTIME 1494 if (borrow != NULL) 1495 extradelay = borrow->offtime_; 1496 else 1497 #endif 1498 extradelay = cl->offtime_; 1499 1500 #ifdef ALTQ 1501 /* 1502 * XXX recalculate suspend time: 1503 * current undertime is (tidle + pkt_time) calculated 1504 * from the last transmission. 1505 * tidle: time required to bring avgidle back to 0 1506 * pkt_time: target waiting time for this class 1507 * we need to replace pkt_time by offtime 1508 */ 1509 extradelay -= cl->last_pkttime_; 1510 #endif 1511 if (extradelay > 0) { 1512 TV_ADD_DELTA(&cl->undertime_, extradelay, &cl->undertime_); 1513 delay += extradelay; 1514 } 1515 1516 cl->sleeping_ = 1; 1517 cl->stats_.delays++; 1518 1519 /* 1520 * Since packets are phased randomly with respect to the 1521 * clock, 1 tick (the next clock tick) can be an arbitrarily 1522 * short time so we have to wait for at least two ticks. 1523 * NOTE: If there's no other traffic, we need the timer as 1524 * a 'backstop' to restart this class. 1525 */ 1526 if (delay > tick * 2) { 1527 /* FreeBSD rounds up the tick */ 1528 t = hzto(&cl->undertime_); 1529 } else 1530 t = 2; 1531 CALLOUT_RESET(&cl->callout_, t, rmc_restart, cl); 1532 } 1533 } 1534 1535 /* 1536 * void 1537 * rmc_restart() - is just a helper routine for rmc_delay_action -- it is 1538 * called by the system timer code & is responsible checking if the 1539 * class is still sleeping (it might have been restarted as a side 1540 * effect of the queue scan on a packet arrival) and, if so, restarting 1541 * output for the class. Inspecting the class state & restarting output 1542 * require locking the class structure. In general the driver is 1543 * responsible for locking but this is the only routine that is not 1544 * called directly or indirectly from the interface driver so it has 1545 * know about system locking conventions. Under bsd, locking is done 1546 * by raising IPL to splimp so that's what's implemented here. On a 1547 * different system this would probably need to be changed. 1548 * 1549 * Returns: NONE 1550 */ 1551 1552 static void 1553 rmc_restart(void *arg) 1554 { 1555 struct rm_class *cl = arg; 1556 struct rm_ifdat *ifd = cl->ifdat_; 1557 int s; 1558 1559 s = splnet(); 1560 IFQ_LOCK(ifd->ifq_); 1561 if (cl->sleeping_) { 1562 cl->sleeping_ = 0; 1563 cl->undertime_.tv_sec = 0; 1564 1565 if (ifd->queued_ < ifd->maxqueued_ && ifd->restart != NULL) { 1566 CBQTRACE(rmc_restart, 'trts', cl->stats_.handle); 1567 (ifd->restart)(ifd->ifq_); 1568 } 1569 } 1570 IFQ_UNLOCK(ifd->ifq_); 1571 splx(s); 1572 } 1573 1574 /* 1575 * void 1576 * rmc_root_overlimit(struct rm_class *cl) - This the generic overlimit 1577 * handling routine for the root class of the link sharing structure. 1578 * 1579 * Returns: NONE 1580 */ 1581 1582 static void 1583 rmc_root_overlimit(struct rm_class *cl, struct rm_class *borrow) 1584 { 1585 panic("rmc_root_overlimit"); 1586 } 1587 1588 /* 1589 * Packet Queue handling routines. Eventually, this is to localize the 1590 * effects on the code whether queues are red queues or droptail 1591 * queues. 1592 */ 1593 1594 static int 1595 _rmc_addq(rm_class_t *cl, mbuf_t *m) 1596 { 1597 #ifdef ALTQ_RIO 1598 if (q_is_rio(cl->q_)) 1599 return rio_addq((rio_t *)cl->red_, cl->q_, m, cl->pktattr_); 1600 #endif 1601 #ifdef ALTQ_RED 1602 if (q_is_red(cl->q_)) 1603 return red_addq(cl->red_, cl->q_, m, cl->pktattr_); 1604 #endif /* ALTQ_RED */ 1605 #ifdef ALTQ_CODEL 1606 if (q_is_codel(cl->q_)) 1607 return codel_addq(cl->codel_, cl->q_, m); 1608 #endif 1609 1610 if (cl->flags_ & RMCF_CLEARDSCP) 1611 write_dsfield(m, cl->pktattr_, 0); 1612 1613 _addq(cl->q_, m); 1614 return (0); 1615 } 1616 1617 /* note: _rmc_dropq is not called for red */ 1618 static void 1619 _rmc_dropq(rm_class_t *cl) 1620 { 1621 mbuf_t *m; 1622 1623 if ((m = _getq(cl->q_)) != NULL) 1624 m_freem(m); 1625 } 1626 1627 static mbuf_t * 1628 _rmc_getq(rm_class_t *cl) 1629 { 1630 #ifdef ALTQ_RIO 1631 if (q_is_rio(cl->q_)) 1632 return rio_getq((rio_t *)cl->red_, cl->q_); 1633 #endif 1634 #ifdef ALTQ_RED 1635 if (q_is_red(cl->q_)) 1636 return red_getq(cl->red_, cl->q_); 1637 #endif 1638 #ifdef ALTQ_CODEL 1639 if (q_is_codel(cl->q_)) 1640 return codel_getq(cl->codel_, cl->q_); 1641 #endif 1642 return _getq(cl->q_); 1643 } 1644 1645 static mbuf_t * 1646 _rmc_pollq(rm_class_t *cl) 1647 { 1648 return qhead(cl->q_); 1649 } 1650 1651 #ifdef CBQ_TRACE 1652 1653 struct cbqtrace cbqtrace_buffer[NCBQTRACE+1]; 1654 struct cbqtrace *cbqtrace_ptr = NULL; 1655 int cbqtrace_count; 1656 1657 /* 1658 * DDB hook to trace cbq events: 1659 * the last 1024 events are held in a circular buffer. 1660 * use "call cbqtrace_dump(N)" to display 20 events from Nth event. 1661 */ 1662 void cbqtrace_dump(int); 1663 static char *rmc_funcname(void *); 1664 1665 static struct rmc_funcs { 1666 void *func; 1667 char *name; 1668 } rmc_funcs[] = 1669 { 1670 rmc_init, "rmc_init", 1671 rmc_queue_packet, "rmc_queue_packet", 1672 rmc_under_limit, "rmc_under_limit", 1673 rmc_update_class_util, "rmc_update_class_util", 1674 rmc_delay_action, "rmc_delay_action", 1675 rmc_restart, "rmc_restart", 1676 _rmc_wrr_dequeue_next, "_rmc_wrr_dequeue_next", 1677 NULL, NULL 1678 }; 1679 1680 static char *rmc_funcname(void *func) 1681 { 1682 struct rmc_funcs *fp; 1683 1684 for (fp = rmc_funcs; fp->func != NULL; fp++) 1685 if (fp->func == func) 1686 return (fp->name); 1687 return ("unknown"); 1688 } 1689 1690 void cbqtrace_dump(int counter) 1691 { 1692 int i, *p; 1693 char *cp; 1694 1695 counter = counter % NCBQTRACE; 1696 p = (int *)&cbqtrace_buffer[counter]; 1697 1698 for (i=0; i<20; i++) { 1699 printf("[0x%x] ", *p++); 1700 printf("%s: ", rmc_funcname((void *)*p++)); 1701 cp = (char *)p++; 1702 printf("%c%c%c%c: ", cp[0], cp[1], cp[2], cp[3]); 1703 printf("%d\n",*p++); 1704 1705 if (p >= (int *)&cbqtrace_buffer[NCBQTRACE]) 1706 p = (int *)cbqtrace_buffer; 1707 } 1708 } 1709 #endif /* CBQ_TRACE */ 1710 #endif /* ALTQ_CBQ */ 1711 1712 #if defined(ALTQ_CBQ) || defined(ALTQ_RED) || defined(ALTQ_RIO) || \ 1713 defined(ALTQ_HFSC) || defined(ALTQ_PRIQ) || defined(ALTQ_CODEL) 1714 #if !defined(__GNUC__) || defined(ALTQ_DEBUG) 1715 1716 void 1717 _addq(class_queue_t *q, mbuf_t *m) 1718 { 1719 mbuf_t *m0; 1720 1721 if ((m0 = qtail(q)) != NULL) 1722 m->m_nextpkt = m0->m_nextpkt; 1723 else 1724 m0 = m; 1725 m0->m_nextpkt = m; 1726 qtail(q) = m; 1727 qlen(q)++; 1728 } 1729 1730 mbuf_t * 1731 _getq(class_queue_t *q) 1732 { 1733 mbuf_t *m, *m0; 1734 1735 if ((m = qtail(q)) == NULL) 1736 return (NULL); 1737 if ((m0 = m->m_nextpkt) != m) 1738 m->m_nextpkt = m0->m_nextpkt; 1739 else { 1740 ASSERT(qlen(q) == 1); 1741 qtail(q) = NULL; 1742 } 1743 qlen(q)--; 1744 m0->m_nextpkt = NULL; 1745 return (m0); 1746 } 1747 1748 /* drop a packet at the tail of the queue */ 1749 mbuf_t * 1750 _getq_tail(class_queue_t *q) 1751 { 1752 mbuf_t *m, *m0, *prev; 1753 1754 if ((m = m0 = qtail(q)) == NULL) 1755 return NULL; 1756 do { 1757 prev = m0; 1758 m0 = m0->m_nextpkt; 1759 } while (m0 != m); 1760 prev->m_nextpkt = m->m_nextpkt; 1761 if (prev == m) { 1762 ASSERT(qlen(q) == 1); 1763 qtail(q) = NULL; 1764 } else 1765 qtail(q) = prev; 1766 qlen(q)--; 1767 m->m_nextpkt = NULL; 1768 return (m); 1769 } 1770 1771 /* randomly select a packet in the queue */ 1772 mbuf_t * 1773 _getq_random(class_queue_t *q) 1774 { 1775 struct mbuf *m; 1776 int i, n; 1777 1778 if ((m = qtail(q)) == NULL) 1779 return NULL; 1780 if (m->m_nextpkt == m) { 1781 ASSERT(qlen(q) == 1); 1782 qtail(q) = NULL; 1783 } else { 1784 struct mbuf *prev = NULL; 1785 1786 n = arc4random() % qlen(q) + 1; 1787 for (i = 0; i < n; i++) { 1788 prev = m; 1789 m = m->m_nextpkt; 1790 } 1791 prev->m_nextpkt = m->m_nextpkt; 1792 if (m == qtail(q)) 1793 qtail(q) = prev; 1794 } 1795 qlen(q)--; 1796 m->m_nextpkt = NULL; 1797 return (m); 1798 } 1799 1800 void 1801 _removeq(class_queue_t *q, mbuf_t *m) 1802 { 1803 mbuf_t *m0, *prev; 1804 1805 m0 = qtail(q); 1806 do { 1807 prev = m0; 1808 m0 = m0->m_nextpkt; 1809 } while (m0 != m); 1810 prev->m_nextpkt = m->m_nextpkt; 1811 if (prev == m) 1812 qtail(q) = NULL; 1813 else if (qtail(q) == m) 1814 qtail(q) = prev; 1815 qlen(q)--; 1816 } 1817 1818 void 1819 _flushq(class_queue_t *q) 1820 { 1821 mbuf_t *m; 1822 1823 while ((m = _getq(q)) != NULL) 1824 m_freem(m); 1825 ASSERT(qlen(q) == 0); 1826 } 1827 1828 #endif /* !__GNUC__ || ALTQ_DEBUG */ 1829 #endif /* ALTQ_CBQ || ALTQ_RED || ALTQ_RIO || ALTQ_HFSC || ALTQ_PRIQ */ 1830