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