sys/net/altq/altq_rmclass.c

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