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