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