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