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