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 $ */
5 * Copyright (c) 1991-1997 Regents of the University of California.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
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.
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
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
42 #include "opt_inet6.h"
44 #ifdef ALTQ_CBQ /* cbq is enabled by ALTQ_CBQ option in opt_altq.h */
46 #include <sys/param.h>
47 #include <sys/malloc.h>
49 #include <sys/socket.h>
50 #include <sys/systm.h>
51 #include <sys/callout.h>
52 #include <sys/errno.h>
54 #include <sys/thread.h>
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>
64 #include <sys/thread2.h>
67 static struct cbqtrace cbqtrace_buffer[NCBQTRACE+1];
68 static struct cbqtrace *cbqtrace_ptr = NULL;
69 static int cbqtrace_count;
76 #define reset_cutoff(ifd) { ifd->cutoff_ = RM_MAXDEPTH; }
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 *);
87 static struct mbuf *_rmc_wrr_dequeue_next(struct rm_ifdat *, int);
88 static struct mbuf *_rmc_prr_dequeue_next(struct rm_ifdat *, int);
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 *);
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 *);
101 #define BORROW_OFFTIME
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.
110 #define ADJUST_CUTOFF
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
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.
132 * rmc_newclass(...) - Create a new resource management class at priority
133 * 'pri' on the interface given by 'ifd'.
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.
145 * action the routine to call when the class is over limit.
147 * maxq max allowable queue size for class (in packets).
149 * parent parent class pointer.
151 * borrow class to borrow from (should be either 'parent' or null).
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.
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).
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:
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)
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:
182 * maxidle = maxidle * 2^RM_FILTER_GAIN * 8 / (1000 * nsecPerByte)
183 * offtime = offtime * 8 / (1000 * nsecPerByte)
185 * When USE_HRTIME is employed, then maxidle and offtime become:
186 * maxidle = maxilde * (8.0 / nsecPerByte);
187 * offtime = offtime * (8.0 / nsecPerByte);
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)
196 struct rm_class *peer;
198 if (pri >= RM_MAXPRIO)
201 if (flags & RMCF_RED) {
203 kprintf("rmc_newclass: RED not configured for CBQ!\n");
209 if (flags & RMCF_RIO) {
211 kprintf("rmc_newclass: RIO not configured for CBQ!\n");
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);
222 * Class initialization.
224 cl->children_ = NULL;
225 cl->parent_ = parent;
226 cl->borrow_ = borrow;
230 cl->allotment_ = RM_NS_PER_SEC / nsecPerByte; /* Bytes per sec */
233 cl->ns_per_byte_ = nsecPerByte;
235 qlimit(cl->q_) = maxq;
236 qtype(cl->q_) = Q_DROPHEAD;
240 #if 1 /* minidle is also scaled in ALTQ */
241 cl->minidle_ = (minidle * (int)nsecPerByte) / 8;
242 if (cl->minidle_ > 0)
245 cl->minidle_ = minidle;
247 cl->maxidle_ = (maxidle * nsecPerByte) / 8;
248 if (cl->maxidle_ == 0)
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)
257 cl->offtime_ = (offtime * nsecPerByte) / 8;
259 cl->overlimit = action;
262 if (flags & (RMCF_RED|RMCF_RIO)) {
263 int red_flags, red_pkttime;
266 if (flags & RMCF_ECN)
267 red_flags |= REDF_ECN;
269 if (flags & RMCF_CLEARDSCP)
270 red_flags |= RIOF_CLEARDSCP;
272 red_pkttime = nsecPerByte * pktsize / 1000;
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;
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;
291 #endif /* ALTQ_RED */
294 * put the class into the class tree
297 if ((peer = ifd->active_[pri]) != NULL) {
298 /* find the last class at this pri */
300 while (peer->peer_ != ifd->active_[pri])
304 ifd->active_[pri] = cl;
309 cl->next_ = parent->children_;
310 parent->children_ = cl;
315 * Compute the depth of this class and its ancestors in the class
318 rmc_depth_compute(cl);
321 * If CBQ's WRR is enabled, then initialize the class WRR state.
325 ifd->alloc_[pri] += cl->allotment_;
326 rmc_wrr_set_weights(ifd);
333 rmc_modclass(struct rm_class *cl, u_int nsecPerByte, int maxq, u_int maxidle,
334 int minidle, u_int offtime, int pktsize)
336 struct rm_ifdat *ifd;
340 old_allotment = cl->allotment_;
343 cl->allotment_ = RM_NS_PER_SEC / nsecPerByte; /* Bytes per sec */
345 cl->ns_per_byte_ = nsecPerByte;
347 qlimit(cl->q_) = maxq;
349 #if 1 /* minidle is also scaled in ALTQ */
350 cl->minidle_ = (minidle * nsecPerByte) / 8;
351 if (cl->minidle_ > 0)
354 cl->minidle_ = minidle;
356 cl->maxidle_ = (maxidle * nsecPerByte) / 8;
357 if (cl->maxidle_ == 0)
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)
366 cl->offtime_ = (offtime * nsecPerByte) / 8;
370 * If CBQ's WRR is enabled, then initialize the class WRR state.
373 ifd->alloc_[cl->pri_] += cl->allotment_ - old_allotment;
374 rmc_wrr_set_weights(ifd);
382 * rmc_wrr_set_weights(struct rm_ifdat *ifdat) - This function computes
383 * the appropriate run robin weights for the CBQ weighted round robin
390 rmc_wrr_set_weights(struct rm_ifdat *ifd)
393 struct rm_class *cl, *clh;
395 for (i = 0; i < RM_MAXPRIO; i++) {
397 * This is inverted from that of the simulator to
398 * maintain precision.
400 if (ifd->num_[i] == 0)
403 ifd->M_[i] = ifd->alloc_[i] /
404 (ifd->num_[i] * ifd->maxpkt_);
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
412 if (ifd->active_[i] != NULL) {
413 clh = cl = ifd->active_[i];
415 /* safe-guard for slow link or alloc_ == 0 */
417 cl->w_allotment_ = 0;
419 cl->w_allotment_ = cl->allotment_ /
422 } while ((cl != NULL) && (cl != clh));
428 rmc_get_weight(struct rm_ifdat *ifd, int pri)
430 if ((pri >= 0) && (pri < RM_MAXPRIO))
431 return (ifd->M_[pri]);
438 * rmc_depth_compute(struct rm_class *cl) - This function computes the
439 * appropriate depth of class 'cl' and its ancestors.
445 rmc_depth_compute(struct rm_class *cl)
447 rm_class_t *t = cl, *p;
450 * Recompute the depth for the branch of the tree.
454 if (p && (t->depth_ >= p->depth_)) {
455 p->depth_ = t->depth_ + 1;
464 * rmc_depth_recompute(struct rm_class *cl) - This function re-computes
465 * the depth of the tree after a class has been deleted.
471 rmc_depth_recompute(rm_class_t *cl)
478 if ((t = p->children_) == NULL) {
484 if (t->depth_ > cdepth)
489 if (p->depth_ == cdepth + 1)
490 /* no change to this parent */
493 p->depth_ = cdepth + 1;
501 if (cl->depth_ >= 1) {
502 if (cl->children_ == NULL) {
504 } else if ((t = cl->children_) != NULL) {
506 if (t->children_ != NULL)
507 rmc_depth_recompute(t);
511 rmc_depth_compute(cl);
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.
526 rmc_delete_class(struct rm_ifdat *ifd, struct rm_class *cl)
528 struct rm_class *p, *head, *previous;
530 KKASSERT(cl->children_ == NULL);
533 callout_stop(&cl->callout_);
537 * Free packets in the packet queue.
538 * XXX - this may not be a desired behavior. Packets should be
544 * If the class has a parent, then remove the class from the
545 * class from the parent's children chain.
547 if (cl->parent_ != NULL) {
548 head = cl->parent_->children_;
550 if (head->next_ == NULL) {
551 KKASSERT(head == cl);
552 cl->parent_->children_ = NULL;
553 cl->parent_->leaf_ = 1;
554 } else while (p != NULL) {
557 cl->parent_->children_ = cl->next_;
559 previous->next_ = cl->next_;
570 * Delete class from class priority peer list.
572 if ((p = ifd->active_[cl->pri_]) != NULL) {
574 * If there is more than one member of this priority
575 * level, then look for class(cl) in the priority level.
578 while (p->peer_ != cl)
580 p->peer_ = cl->peer_;
582 if (ifd->active_[cl->pri_] == cl)
583 ifd->active_[cl->pri_] = cl->peer_;
586 ifd->active_[cl->pri_] = NULL;
591 * Recompute the WRR weights.
594 ifd->alloc_[cl->pri_] -= cl->allotment_;
595 ifd->num_[cl->pri_]--;
596 rmc_wrr_set_weights(ifd);
600 * Re-compute the depth of the tree.
603 rmc_depth_recompute(cl->parent_);
605 rmc_depth_recompute(ifd->root_);
611 * Free the class structure.
613 if (cl->red_ != NULL) {
615 if (q_is_rio(cl->q_))
616 rio_destroy((rio_t *)cl->red_);
619 if (q_is_red(cl->q_))
620 red_destroy(cl->red_);
623 kfree(cl->q_, M_ALTQ);
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).
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)
651 * Initialize the CBQ tracing/debug facility.
655 bzero(ifd, sizeof (*ifd));
656 mtu = ifq->altq_ifp->if_mtu;
658 ifd->restart = restart;
659 ifd->maxqueued_ = maxqueued;
660 ifd->ns_per_byte_ = nsecPerByte;
662 ifd->wrr_ = (flags & RMCF_WRR) ? 1 : 0;
663 ifd->efficient_ = (flags & RMCF_EFFICIENT) ? 1 : 0;
665 ifd->maxiftime_ = mtu * nsecPerByte / 1000 * 16;
666 if (mtu * nsecPerByte > 10 * 1000000)
667 ifd->maxiftime_ /= 4;
671 CBQTRACE(rmc_init, 'INIT', ifd->cutoff_);
674 * Initialize the CBQ's WRR state.
676 for (i = 0; i < RM_MAXPRIO; i++) {
681 ifd->active_[i] = NULL;
685 * Initialize current packet state.
689 for (i = 0; i < RM_MAXQUEUED; i++) {
690 ifd->class_[i] = NULL;
692 ifd->borrowed_[i] = NULL;
696 * Create the root class of the link-sharing structure.
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");
704 ifd->root_->depth_ = 0;
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
715 * Returns: 0 on successful queueing
716 * -1 when packet drop occurs
719 rmc_queue_packet(struct rm_class *cl, struct mbuf *m)
722 struct rm_ifdat *ifd = cl->ifdat_;
724 int is_empty = qempty(cl->q_);
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_);
736 * the class is overlimit. if the class has
737 * underlimit ancestors, set cutoff to the lowest
740 struct rm_class *borrow = cl->borrow_;
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_);
749 borrow = borrow->borrow_;
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_);
763 if (_rmc_addq(cl, m) < 0)
768 CBQTRACE(rmc_queue_packet, 'ytpe', cl->stats_.handle);
772 if (qlen(cl->q_) > qlimit(cl->q_)) {
773 /* note: qlimit can be set to 0 or 1 */
782 * rmc_tl_satisfied(struct rm_ifdat *ifd, struct timeval *now) - Check all
783 * classes to see if there are satified.
787 rmc_tl_satisfied(struct rm_ifdat *ifd, struct timeval *now)
792 for (i = RM_MAXPRIO - 1; i >= 0; i--) {
793 if ((bp = ifd->active_[i]) != NULL) {
796 if (!rmc_satisfied(p, now)) {
797 ifd->cutoff_ = p->depth_;
809 * rmc_satisfied - Return 1 of the class is satisfied. O, otherwise.
813 rmc_satisfied(struct rm_class *cl, struct timeval *now)
819 if (TV_LT(now, &cl->undertime_))
821 if (cl->depth_ == 0) {
822 if (!cl->sleeping_ && (qlen(cl->q_) > cl->qthresh_))
827 if (cl->children_ != NULL) {
830 if (!rmc_satisfied(p, now))
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.
846 rmc_under_limit(struct rm_class *cl, struct timeval *now)
850 struct rm_ifdat *ifd = cl->ifdat_;
852 ifd->borrowed_[ifd->qi_] = NULL;
854 * If cl is the root class, then always return that it is
855 * underlimit. Otherwise, check to see if the class is underlimit.
857 if (cl->parent_ == NULL)
861 if (TV_LT(now, &cl->undertime_))
864 callout_stop(&cl->callout_);
866 cl->undertime_.tv_sec = 0;
871 while (cl->undertime_.tv_sec && TV_LT(now, &cl->undertime_)) {
872 if (((cl = cl->borrow_) == NULL) ||
873 (cl->depth_ > ifd->cutoff_)) {
876 /* cutoff is taking effect, just
877 return false without calling
881 #ifdef BORROW_OFFTIME
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.
888 /* cutoff is taking effect, use this class as top. */
890 CBQTRACE(rmc_under_limit, 'ffou', ifd->cutoff_);
892 if (top != NULL && top->avgidle_ == top->minidle_)
895 (p->overlimit)(p, top);
898 (p->overlimit)(p, NULL);
906 ifd->borrowed_[ifd->qi_] = cl;
911 * _rmc_wrr_dequeue_next() - This is scheduler for WRR as opposed to
912 * Packet-by-packet round robin.
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.
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.
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.
928 _rmc_wrr_dequeue_next(struct rm_ifdat *ifd, int op)
930 struct rm_class *cl = NULL, *first = NULL;
939 * if the driver polls the top of the queue and then removes
940 * the polled packet, we must return the same packet.
942 if (op == ALTDQ_REMOVE && ifd->pollcache_) {
943 cl = ifd->pollcache_;
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)
951 ifd->pollcache_ = NULL;
955 /* mode == ALTDQ_POLL || pollcache == NULL */
956 ifd->pollcache_ = NULL;
957 ifd->borrowed_[ifd->qi_] = NULL;
962 for (cpri = RM_MAXPRIO - 1; cpri >= 0; cpri--) {
963 if (ifd->na_[cpri] == 0)
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.)
976 cl = ifd->active_[cpri];
977 KKASSERT(cl != NULL);
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)
987 /* underlimit but no alloc */
990 ifd->borrowed_[ifd->qi_] = NULL;
993 else if (first == NULL && cl->borrow_ != NULL)
994 first = cl; /* borrowing candidate */
997 cl->bytes_alloc_ = 0;
999 } while (cl != ifd->active_[cpri]);
1002 /* first loop found an underlimit class with deficit */
1003 /* Loop on same priority level, with new deficit. */
1009 #ifdef ADJUST_CUTOFF
1011 * no underlimit class found. if cutoff is taking effect,
1012 * increase cutoff and try again.
1014 if (first != NULL && ifd->cutoff_ < ifd->root_->depth_) {
1016 CBQTRACE(_rmc_wrr_dequeue_next, 'ojda', ifd->cutoff_);
1019 #endif /* ADJUST_CUTOFF */
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.
1026 CBQTRACE(_rmc_wrr_dequeue_next, 'otsr', ifd->cutoff_);
1028 if (!ifd->efficient_ || first == NULL)
1033 #if 0 /* too time-consuming for nothing */
1035 callout_stop(&cl->callout_);
1037 cl->undertime_.tv_sec = 0;
1039 ifd->borrowed_[ifd->qi_] = cl->borrow_;
1040 ifd->cutoff_ = cl->borrow_->depth_;
1043 * Deque the packet and do the book keeping...
1046 if (op == ALTDQ_REMOVE) {
1049 panic("_rmc_wrr_dequeue_next");
1054 * Update class statistics and link data.
1056 if (cl->bytes_alloc_ > 0)
1057 cl->bytes_alloc_ -= m_pktlen(m);
1059 if ((cl->bytes_alloc_ <= 0) || first == cl)
1060 ifd->active_[cl->pri_] = cl->peer_;
1062 ifd->active_[cl->pri_] = cl;
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_;
1070 /* mode == ALTDQ_PPOLL */
1072 ifd->pollcache_ = cl;
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
1083 static struct mbuf *
1084 _rmc_prr_dequeue_next(struct rm_ifdat *ifd, int op)
1088 struct rm_class *cl, *first = NULL;
1094 * if the driver polls the top of the queue and then removes
1095 * the polled packet, we must return the same packet.
1097 if (op == ALTDQ_REMOVE && ifd->pollcache_) {
1098 cl = ifd->pollcache_;
1100 ifd->pollcache_ = NULL;
1103 /* mode == ALTDQ_POLL || pollcache == NULL */
1104 ifd->pollcache_ = NULL;
1105 ifd->borrowed_[ifd->qi_] = NULL;
1107 #ifdef ADJUST_CUTOFF
1110 for (cpri = RM_MAXPRIO - 1; cpri >= 0; cpri--) {
1111 if (ifd->na_[cpri] == 0)
1113 cl = ifd->active_[cpri];
1114 KKASSERT(cl != NULL);
1116 if (!qempty(cl->q_)) {
1117 if ((cl->undertime_.tv_sec == 0) ||
1118 rmc_under_limit(cl, &now))
1120 if (first == NULL && cl->borrow_ != NULL)
1124 } while (cl != ifd->active_[cpri]);
1127 #ifdef ADJUST_CUTOFF
1129 * no underlimit class found. if cutoff is taking effect, increase
1130 * cutoff and try again.
1132 if (first != NULL && ifd->cutoff_ < ifd->root_->depth_) {
1136 #endif /* ADJUST_CUTOFF */
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.
1143 if (!ifd->efficient_ || first == NULL)
1148 #if 0 /* too time-consuming for nothing */
1150 callout_stop(&cl->callout_);
1152 cl->undertime_.tv_sec = 0;
1154 ifd->borrowed_[ifd->qi_] = cl->borrow_;
1155 ifd->cutoff_ = cl->borrow_->depth_;
1158 * Deque the packet and do the book keeping...
1161 if (op == ALTDQ_REMOVE) {
1164 panic("_rmc_prr_dequeue_next");
1168 ifd->active_[cpri] = cl->peer_;
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_;
1176 /* mode == ALTDQ_POLL */
1178 ifd->pollcache_ = cl;
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.
1191 * Returns: NULL, if a packet is not available or if all
1192 * classes are overlimit.
1194 * Otherwise, Pointer to the next packet.
1198 rmc_dequeue_next(struct rm_ifdat *ifd, int mode)
1200 if (ifd->queued_ >= ifd->maxqueued_)
1203 return (_rmc_wrr_dequeue_next(ifd, mode));
1205 return (_rmc_prr_dequeue_next(ifd, mode));
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.
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!)
1220 #define NSEC_TO_USEC(t) (((t) >> 10) + ((t) >> 16) + ((t) >> 17))
1222 rmc_update_class_util(struct rm_ifdat *ifd)
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;
1231 * Get the most recent completed class.
1233 if ((cl = ifd->class_[ifd->qo_]) == NULL)
1236 pktlen = ifd->curlen_[ifd->qo_];
1237 borrowed = ifd->borrowed_[ifd->qo_];
1240 PKTCNTR_ADD(&cl->stats_.xmit_cnt, pktlen);
1243 * Run estimator on class and its ancestors.
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.
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);
1258 pkt_time = ifd->curlen_[ifd->qo_] * ifd->ns_per_byte_ / 1000;
1260 #if 1 /* ALTQ4PPP */
1261 if (TV_LT(nowp, &ifd->ifnow_)) {
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.
1270 TV_DELTA(&ifd->ifnow_, nowp, iftime);
1271 if (iftime+pkt_time < ifd->maxiftime_) {
1272 TV_ADD_DELTA(&ifd->ifnow_, pkt_time, &ifd->ifnow_);
1274 TV_ADD_DELTA(nowp, ifd->maxiftime_, &ifd->ifnow_);
1277 TV_ADD_DELTA(nowp, pkt_time, &ifd->ifnow_);
1280 if (TV_LT(nowp, &ifd->ifnow_)) {
1281 TV_ADD_DELTA(&ifd->ifnow_, pkt_time, &ifd->ifnow_);
1283 TV_ADD_DELTA(nowp, pkt_time, &ifd->ifnow_);
1287 while (cl != NULL) {
1288 TV_DELTA(&ifd->ifnow_, &cl->last_, idle);
1289 if (idle >= 2000000)
1291 * this class is idle enough, reset avgidle.
1292 * (TV_DELTA returns 2000000 us when delta is large.)
1294 cl->avgidle_ = cl->maxidle_;
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);
1301 pkt_time = pktlen * cl->ns_per_byte_ / 1000;
1305 avgidle = cl->avgidle_;
1306 avgidle += idle - (avgidle >> RM_FILTER_GAIN);
1307 cl->avgidle_ = avgidle;
1309 /* Are we overlimit ? */
1311 CBQTRACE(rmc_update_class_util, 'milo', cl->stats_.handle);
1314 * need some lower bound for avgidle, otherwise
1315 * a borrowing class gets unbounded penalty.
1317 if (avgidle < cl->minidle_)
1318 avgidle = cl->avgidle_ = cl->minidle_;
1320 /* set next idle to make avgidle 0 */
1322 (((1 - RM_POWER) * avgidle) >> RM_FILTER_GAIN);
1323 TV_ADD_DELTA(nowp, tidle, &cl->undertime_);
1327 (avgidle > cl->maxidle_) ? cl->maxidle_ : avgidle;
1328 cl->undertime_.tv_sec = 0;
1329 if (cl->sleeping_) {
1330 callout_stop(&cl->callout_);
1335 if (borrows != NULL) {
1337 ++cl->stats_.borrows;
1341 cl->last_ = ifd->ifnow_;
1342 cl->last_pkttime_ = pkt_time;
1345 if (cl->parent_ == NULL) {
1346 /* take stats of root class */
1347 PKTCNTR_ADD(&cl->stats_.xmit_cnt, pktlen);
1355 * Check to see if cutoff needs to set to a new level.
1357 cl = ifd->class_[ifd->qo_];
1358 if (borrowed && (ifd->cutoff_ >= borrowed->depth_)) {
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_);
1364 ifd->cutoff_ = borrowed->depth_;
1365 CBQTRACE(rmc_update_class_util, 'ffob', borrowed->depth_);
1368 if ((qlen(cl->q_) <= 1) || TV_LT(&now, &borrowed->undertime_)) {
1371 rmc_tl_satisfied(ifd, &now);
1373 CBQTRACE(rmc_update_class_util, 'broe', ifd->cutoff_);
1375 ifd->cutoff_ = borrowed->depth_;
1376 CBQTRACE(rmc_update_class_util, 'ffob', borrowed->depth_);
1382 * Release class slot
1384 ifd->borrowed_[ifd->qo_] = NULL;
1385 ifd->class_[ifd->qo_] = NULL;
1386 ifd->qo_ = (ifd->qo_ + 1) % ifd->maxqueued_;
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.
1401 rmc_drop_action(struct rm_class *cl)
1403 struct rm_ifdat *ifd = cl->ifdat_;
1405 KKASSERT(qlen(cl->q_) > 0);
1408 ifd->na_[cl->pri_]--;
1412 rmc_dropall(struct rm_class *cl)
1414 struct rm_ifdat *ifd = cl->ifdat_;
1416 if (!qempty(cl->q_)) {
1419 ifd->na_[cl->pri_]--;
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.
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.
1436 rmc_delay_action(struct rm_class *cl, struct rm_class *borrow)
1438 int delay, t, extradelay;
1440 cl->stats_.overactions++;
1441 TV_DELTA(&cl->undertime_, &cl->overtime_, delay);
1442 #ifndef BORROW_OFFTIME
1443 delay += cl->offtime_;
1446 if (!cl->sleeping_) {
1447 CBQTRACE(rmc_delay_action, 'yled', cl->stats_.handle);
1448 #ifdef BORROW_OFFTIME
1450 extradelay = borrow->offtime_;
1453 extradelay = cl->offtime_;
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
1464 extradelay -= cl->last_pkttime_;
1466 if (extradelay > 0) {
1467 TV_ADD_DELTA(&cl->undertime_, extradelay, &cl->undertime_);
1468 delay += extradelay;
1472 cl->stats_.delays++;
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.
1481 if (delay > ustick * 2)
1482 t = (delay + ustick - 1) / ustick;
1485 callout_reset(&cl->callout_, t, rmc_restart, cl);
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.
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.
1511 rmc_restart(void *arg)
1513 struct rm_class *cl = arg;
1514 struct rm_ifdat *ifd = cl->ifdat_;
1516 ALTQ_LOCK(ifd->ifq_);
1517 if (cl->sleeping_) {
1519 cl->undertime_.tv_sec = 0;
1521 if (ifd->queued_ < ifd->maxqueued_ && ifd->restart != NULL) {
1522 CBQTRACE(rmc_restart, 'trts', cl->stats_.handle);
1523 (ifd->restart)(ifd->ifq_);
1526 ALTQ_UNLOCK(ifd->ifq_);
1531 * rmc_root_overlimit(struct rm_class *cl) - This the generic overlimit
1532 * handling routine for the root class of the link sharing structure.
1538 rmc_root_overlimit(struct rm_class *cl, struct rm_class *borrow)
1540 panic("rmc_root_overlimit");
1544 * Packet Queue handling routines. Eventually, this is to localize the
1545 * effects on the code whether queues are red queues or droptail
1550 _rmc_addq(rm_class_t *cl, struct mbuf *m)
1553 if (q_is_rio(cl->q_))
1554 return rio_addq((rio_t *)cl->red_, cl->q_, m, cl->pktattr_);
1557 if (q_is_red(cl->q_))
1558 return red_addq(cl->red_, cl->q_, m, cl->pktattr_);
1559 #endif /* ALTQ_RED */
1561 if (cl->flags_ & RMCF_CLEARDSCP)
1562 write_dsfield(m, cl->pktattr_, 0);
1568 /* note: _rmc_dropq is not called for red */
1570 _rmc_dropq(rm_class_t *cl)
1574 if ((m = _getq(cl->q_)) != NULL)
1578 static struct mbuf *
1579 _rmc_getq(rm_class_t *cl)
1582 if (q_is_rio(cl->q_))
1583 return rio_getq((rio_t *)cl->red_, cl->q_);
1586 if (q_is_red(cl->q_))
1587 return red_getq(cl->red_, cl->q_);
1589 return _getq(cl->q_);
1592 static struct mbuf *
1593 _rmc_pollq(rm_class_t *cl)
1595 return qhead(cl->q_);
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.
1604 void cbqtrace_dump(int);
1605 static char *rmc_funcname(void *);
1607 static struct 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",
1622 rmc_funcname(void *func)
1624 struct rmc_funcs *fp;
1626 for (fp = rmc_funcs; fp->func != NULL; fp++) {
1627 if (fp->func == func)
1635 cbqtrace_dump(int counter)
1640 counter = counter % NCBQTRACE;
1641 p = (int *)&cbqtrace_buffer[counter];
1643 for (i=0; i<20; i++) {
1644 kprintf("[0x%x] ", *p++);
1645 kprintf("%s: ", rmc_funcname((void *)*p++));
1647 kprintf("%c%c%c%c: ", cp[0], cp[1], cp[2], cp[3]);
1648 kprintf("%d\n",*p++);
1650 if (p >= (int *)&cbqtrace_buffer[NCBQTRACE])
1651 p = (int *)cbqtrace_buffer;
1654 #endif /* CBQ_TRACE */
1655 #endif /* ALTQ_CBQ */