sys/net/altq/altq_rmclass.c

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