2 /* $KAME: altq_rio.c,v 1.17 2003/07/10 12:07:49 kjc Exp $ */
5 * Copyright (C) 1998-2003
6 * Sony Computer Science Laboratories Inc. All rights reserved.
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.
17 * THIS SOFTWARE IS PROVIDED BY SONY CSL AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL SONY CSL OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * Copyright (c) 1990-1994 Regents of the University of California.
31 * All rights reserved.
33 * Redistribution and use in source and binary forms, with or without
34 * modification, are permitted provided that the following conditions
36 * 1. Redistributions of source code must retain the above copyright
37 * notice, this list of conditions and the following disclaimer.
38 * 2. Redistributions in binary form must reproduce the above copyright
39 * notice, this list of conditions and the following disclaimer in the
40 * documentation and/or other materials provided with the distribution.
41 * 3. All advertising materials mentioning features or use of this software
42 * must display the following acknowledgement:
43 * This product includes software developed by the Computer Systems
44 * Engineering Group at Lawrence Berkeley Laboratory.
45 * 4. Neither the name of the University nor of the Laboratory may be used
46 * to endorse or promote products derived from this software without
47 * specific prior written permission.
49 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
50 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
51 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
52 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
53 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
54 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
55 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
56 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
57 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
58 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
62 #if defined(__FreeBSD__) || defined(__NetBSD__)
66 #include "opt_inet6.h"
68 #endif /* __FreeBSD__ || __NetBSD__ */
69 #ifdef ALTQ_RIO /* rio is enabled by ALTQ_RIO option in opt_altq.h */
71 #include <sys/param.h>
72 #include <sys/malloc.h>
74 #include <sys/socket.h>
75 #include <sys/systm.h>
76 #include <sys/errno.h>
77 #if 1 /* ALTQ3_COMPAT */
79 #include <sys/sockio.h>
80 #include <sys/kernel.h>
84 #include <net/if_var.h>
86 #include <netinet/in.h>
87 #include <netinet/in_systm.h>
88 #include <netinet/ip.h>
90 #include <netinet/ip6.h>
93 #include <netpfil/pf/pf.h>
94 #include <netpfil/pf/pf_altq.h>
95 #include <altq/altq.h>
96 #include <altq/altq_cdnr.h>
97 #include <altq/altq_red.h>
98 #include <altq/altq_rio.h>
100 #include <altq/altq_conf.h>
104 * RIO: RED with IN/OUT bit
106 * "Explicit Allocation of Best Effort Packet Delivery Service"
107 * David D. Clark and Wenjia Fang, MIT Lab for Computer Science
108 * http://diffserv.lcs.mit.edu/Papers/exp-alloc-ddc-wf.{ps,pdf}
110 * this implementation is extended to support more than 2 drop precedence
111 * values as described in RFC2597 (Assured Forwarding PHB Group).
115 * AF DS (differentiated service) codepoints.
116 * (classes can be mapped to CBQ or H-FSC classes.)
119 * +---+---+---+---+---+---+---+---+
120 * | CLASS |DropPre| 0 | CU |
121 * +---+---+---+---+---+---+---+---+
129 * medium drop prec: 10
133 /* normal red parameters */
134 #define W_WEIGHT 512 /* inverse of weight of EWMA (511/512) */
135 /* q_weight = 0.00195 */
137 /* red parameters for a slow link */
138 #define W_WEIGHT_1 128 /* inverse of weight of EWMA (127/128) */
139 /* q_weight = 0.0078125 */
141 /* red parameters for a very slow link (e.g., dialup) */
142 #define W_WEIGHT_2 64 /* inverse of weight of EWMA (63/64) */
143 /* q_weight = 0.015625 */
145 /* fixed-point uses 12-bit decimal places */
146 #define FP_SHIFT 12 /* fixed-point shift */
148 /* red parameters for drop probability */
149 #define INV_P_MAX 10 /* inverse of max drop probability */
150 #define TH_MIN 5 /* min threshold */
151 #define TH_MAX 15 /* max threshold */
153 #define RIO_LIMIT 60 /* default max queue lenght */
154 #define RIO_STATS /* collect statistics */
156 #define TV_DELTA(a, b, delta) { \
159 delta = (a)->tv_usec - (b)->tv_usec; \
160 if ((xxs = (a)->tv_sec - (b)->tv_sec) != 0) { \
163 } else if (xxs > 4) { \
167 delta += xxs * 1000000; \
168 } else while (xxs > 0) { \
176 /* rio_list keeps all rio_queue_t's allocated. */
177 static rio_queue_t *rio_list = NULL;
179 /* default rio parameter values */
180 static struct redparams default_rio_params[RIO_NDROPPREC] = {
181 /* th_min, th_max, inv_pmax */
182 { TH_MAX * 2 + TH_MIN, TH_MAX * 3, INV_P_MAX }, /* low drop precedence */
183 { TH_MAX + TH_MIN, TH_MAX * 2, INV_P_MAX }, /* medium drop precedence */
184 { TH_MIN, TH_MAX, INV_P_MAX } /* high drop precedence */
187 /* internal function prototypes */
188 static int dscp2index(u_int8_t);
190 static int rio_enqueue(struct ifaltq *, struct mbuf *, struct altq_pktattr *);
191 static struct mbuf *rio_dequeue(struct ifaltq *, int);
192 static int rio_request(struct ifaltq *, int, void *);
193 static int rio_detach(rio_queue_t *);
196 * rio device interface
200 #endif /* ALTQ3_COMPAT */
203 rio_alloc(int weight, struct redparams *params, int flags, int pkttime)
209 rp = malloc(sizeof(rio_t), M_DEVBUF, M_NOWAIT | M_ZERO);
213 rp->rio_flags = flags;
215 /* default packet time: 1000 bytes / 10Mbps * 8 * 1000000 */
216 rp->rio_pkttime = 800;
218 rp->rio_pkttime = pkttime;
221 rp->rio_weight = weight;
224 rp->rio_weight = W_WEIGHT;
226 /* when the link is very slow, adjust red parameters */
227 npkts_per_sec = 1000000 / rp->rio_pkttime;
228 if (npkts_per_sec < 50) {
229 /* up to about 400Kbps */
230 rp->rio_weight = W_WEIGHT_2;
231 } else if (npkts_per_sec < 300) {
232 /* up to about 2.4Mbps */
233 rp->rio_weight = W_WEIGHT_1;
237 /* calculate wshift. weight must be power of 2 */
239 for (i = 0; w > 1; i++)
242 w = 1 << rp->rio_wshift;
243 if (w != rp->rio_weight) {
244 printf("invalid weight value %d for red! use %d\n",
249 /* allocate weight table */
250 rp->rio_wtab = wtab_alloc(rp->rio_weight);
252 for (i = 0; i < RIO_NDROPPREC; i++) {
253 struct dropprec_state *prec = &rp->rio_precstate[i];
258 if (params == NULL || params[i].inv_pmax == 0)
259 prec->inv_pmax = default_rio_params[i].inv_pmax;
261 prec->inv_pmax = params[i].inv_pmax;
262 if (params == NULL || params[i].th_min == 0)
263 prec->th_min = default_rio_params[i].th_min;
265 prec->th_min = params[i].th_min;
266 if (params == NULL || params[i].th_max == 0)
267 prec->th_max = default_rio_params[i].th_max;
269 prec->th_max = params[i].th_max;
272 * th_min_s and th_max_s are scaled versions of th_min
273 * and th_max to be compared with avg.
275 prec->th_min_s = prec->th_min << (rp->rio_wshift + FP_SHIFT);
276 prec->th_max_s = prec->th_max << (rp->rio_wshift + FP_SHIFT);
279 * precompute probability denominator
280 * probd = (2 * (TH_MAX-TH_MIN) / pmax) in fixed-point
282 prec->probd = (2 * (prec->th_max - prec->th_min)
283 * prec->inv_pmax) << FP_SHIFT;
285 microtime(&prec->last);
292 rio_destroy(rio_t *rp)
294 wtab_destroy(rp->rio_wtab);
299 rio_getstats(rio_t *rp, struct redstats *sp)
303 for (i = 0; i < RIO_NDROPPREC; i++) {
304 bcopy(&rp->q_stats[i], sp, sizeof(struct redstats));
305 sp->q_avg = rp->rio_precstate[i].avg >> rp->rio_wshift;
310 #if (RIO_NDROPPREC == 3)
312 * internally, a drop precedence value is converted to an index
316 dscp2index(u_int8_t dscp)
318 int dpindex = dscp & AF_DROPPRECMASK;
322 return ((dpindex >> 3) - 1);
328 * kludge: when a packet is dequeued, we need to know its drop precedence
329 * in order to keep the queue length of each drop precedence.
330 * use m_pkthdr.rcvif to pass this info.
332 #define RIOM_SET_PRECINDEX(m, idx) \
333 do { (m)->m_pkthdr.rcvif = (void *)((long)(idx)); } while (0)
334 #define RIOM_GET_PRECINDEX(m) \
335 ({ long idx; idx = (long)((m)->m_pkthdr.rcvif); \
336 (m)->m_pkthdr.rcvif = NULL; idx; })
340 rio_addq(rio_t *rp, class_queue_t *q, struct mbuf *m,
341 struct altq_pktattr *pktattr)
344 u_int8_t dsfield, odsfield;
345 int dpindex, i, n, t;
347 struct dropprec_state *prec;
349 dsfield = odsfield = read_dsfield(m, pktattr);
350 dpindex = dscp2index(dsfield);
353 * update avg of the precedence states whose drop precedence
354 * is larger than or equal to the drop precedence of the packet
357 for (i = dpindex; i < RIO_NDROPPREC; i++) {
358 prec = &rp->rio_precstate[i];
364 t = (now.tv_sec - prec->last.tv_sec);
369 (now.tv_usec - prec->last.tv_usec);
370 n = t / rp->rio_pkttime;
371 /* calculate (avg = (1 - Wq)^n * avg) */
373 avg = (avg >> FP_SHIFT) *
374 pow_w(rp->rio_wtab, n);
378 /* run estimator. (avg is scaled by WEIGHT in fixed-point) */
379 avg += (prec->qlen << FP_SHIFT) - (avg >> rp->rio_wshift);
380 prec->avg = avg; /* save the new value */
382 * count keeps a tally of arriving traffic that has not
388 prec = &rp->rio_precstate[dpindex];
391 /* see if we drop early */
392 droptype = DTYPE_NODROP;
393 if (avg >= prec->th_min_s && prec->qlen > 1) {
394 if (avg >= prec->th_max_s) {
395 /* avg >= th_max: forced drop */
396 droptype = DTYPE_FORCED;
397 } else if (prec->old == 0) {
398 /* first exceeds th_min */
401 } else if (drop_early((avg - prec->th_min_s) >> rp->rio_wshift,
402 prec->probd, prec->count)) {
403 /* unforced drop by red */
404 droptype = DTYPE_EARLY;
412 * if the queue length hits the hard limit, it's a forced drop.
414 if (droptype == DTYPE_NODROP && qlen(q) >= qlimit(q))
415 droptype = DTYPE_FORCED;
417 if (droptype != DTYPE_NODROP) {
418 /* always drop incoming packet (as opposed to randomdrop) */
419 for (i = dpindex; i < RIO_NDROPPREC; i++)
420 rp->rio_precstate[i].count = 0;
422 if (droptype == DTYPE_EARLY)
423 rp->q_stats[dpindex].drop_unforced++;
425 rp->q_stats[dpindex].drop_forced++;
426 PKTCNTR_ADD(&rp->q_stats[dpindex].drop_cnt, m_pktlen(m));
432 for (i = dpindex; i < RIO_NDROPPREC; i++)
433 rp->rio_precstate[i].qlen++;
435 /* save drop precedence index in mbuf hdr */
436 RIOM_SET_PRECINDEX(m, dpindex);
438 if (rp->rio_flags & RIOF_CLEARDSCP)
439 dsfield &= ~DSCP_MASK;
441 if (dsfield != odsfield)
442 write_dsfield(m, pktattr, dsfield);
447 PKTCNTR_ADD(&rp->q_stats[dpindex].xmit_cnt, m_pktlen(m));
453 rio_getq(rio_t *rp, class_queue_t *q)
458 if ((m = _getq(q)) == NULL)
461 dpindex = RIOM_GET_PRECINDEX(m);
462 for (i = dpindex; i < RIO_NDROPPREC; i++) {
463 if (--rp->rio_precstate[i].qlen == 0) {
464 if (rp->rio_precstate[i].idle == 0) {
465 rp->rio_precstate[i].idle = 1;
466 microtime(&rp->rio_precstate[i].last);
475 rioopen(dev, flag, fmt, p)
478 #if (__FreeBSD_version > 500000)
484 /* everything will be done when the queueing scheme is attached. */
489 rioclose(dev, flag, fmt, p)
492 #if (__FreeBSD_version > 500000)
501 while ((rqp = rio_list) != NULL) {
503 err = rio_detach(rqp);
504 if (err != 0 && error == 0)
512 rioioctl(dev, cmd, addr, flag, p)
517 #if (__FreeBSD_version > 500000)
524 struct rio_interface *ifacep;
528 /* check super-user privilege */
533 #if (__FreeBSD_version > 700000)
534 if ((error = priv_check(p, PRIV_ALTQ_MANAGE)) != 0)
536 #elsif (__FreeBSD_version > 400000)
537 if ((error = suser(p)) != 0)
540 if ((error = suser(p->p_ucred, &p->p_acflag)) != 0)
549 ifacep = (struct rio_interface *)addr;
550 if ((rqp = altq_lookup(ifacep->rio_ifname, ALTQT_RIO)) == NULL) {
554 error = altq_enable(rqp->rq_ifq);
558 ifacep = (struct rio_interface *)addr;
559 if ((rqp = altq_lookup(ifacep->rio_ifname, ALTQT_RIO)) == NULL) {
563 error = altq_disable(rqp->rq_ifq);
567 ifp = ifunit(((struct rio_interface *)addr)->rio_ifname);
573 /* allocate and initialize rio_queue_t */
574 rqp = malloc(sizeof(rio_queue_t), M_DEVBUF, M_WAITOK);
579 bzero(rqp, sizeof(rio_queue_t));
581 rqp->rq_q = malloc(sizeof(class_queue_t),
583 if (rqp->rq_q == NULL) {
588 bzero(rqp->rq_q, sizeof(class_queue_t));
590 rqp->rq_rio = rio_alloc(0, NULL, 0, 0);
591 if (rqp->rq_rio == NULL) {
592 free(rqp->rq_q, M_DEVBUF);
598 rqp->rq_ifq = &ifp->if_snd;
599 qtail(rqp->rq_q) = NULL;
601 qlimit(rqp->rq_q) = RIO_LIMIT;
602 qtype(rqp->rq_q) = Q_RIO;
605 * set RIO to this ifnet structure.
607 error = altq_attach(rqp->rq_ifq, ALTQT_RIO, rqp,
608 rio_enqueue, rio_dequeue, rio_request,
611 rio_destroy(rqp->rq_rio);
612 free(rqp->rq_q, M_DEVBUF);
617 /* add this state to the rio list */
618 rqp->rq_next = rio_list;
623 ifacep = (struct rio_interface *)addr;
624 if ((rqp = altq_lookup(ifacep->rio_ifname, ALTQT_RIO)) == NULL) {
628 error = rio_detach(rqp);
633 struct rio_stats *q_stats;
637 q_stats = (struct rio_stats *)addr;
638 if ((rqp = altq_lookup(q_stats->iface.rio_ifname,
639 ALTQT_RIO)) == NULL) {
646 q_stats->q_limit = qlimit(rqp->rq_q);
647 q_stats->weight = rp->rio_weight;
648 q_stats->flags = rp->rio_flags;
650 for (i = 0; i < RIO_NDROPPREC; i++) {
651 q_stats->q_len[i] = rp->rio_precstate[i].qlen;
652 bcopy(&rp->q_stats[i], &q_stats->q_stats[i],
653 sizeof(struct redstats));
654 q_stats->q_stats[i].q_avg =
655 rp->rio_precstate[i].avg >> rp->rio_wshift;
657 q_stats->q_params[i].inv_pmax
658 = rp->rio_precstate[i].inv_pmax;
659 q_stats->q_params[i].th_min
660 = rp->rio_precstate[i].th_min;
661 q_stats->q_params[i].th_max
662 = rp->rio_precstate[i].th_max;
664 } while (/*CONSTCOND*/ 0);
673 fc = (struct rio_conf *)addr;
674 if ((rqp = altq_lookup(fc->iface.rio_ifname,
675 ALTQT_RIO)) == NULL) {
680 new = rio_alloc(fc->rio_weight, &fc->q_params[0],
681 fc->rio_flags, fc->rio_pkttime);
693 limit = fc->rio_limit;
694 if (limit < fc->q_params[RIO_NDROPPREC-1].th_max)
695 limit = fc->q_params[RIO_NDROPPREC-1].th_max;
696 qlimit(rqp->rq_q) = limit;
698 rio_destroy(rqp->rq_rio);
703 /* write back new values */
704 fc->rio_limit = limit;
705 for (i = 0; i < RIO_NDROPPREC; i++) {
706 fc->q_params[i].inv_pmax =
707 rqp->rq_rio->rio_precstate[i].inv_pmax;
708 fc->q_params[i].th_min =
709 rqp->rq_rio->rio_precstate[i].th_min;
710 fc->q_params[i].th_max =
711 rqp->rq_rio->rio_precstate[i].th_max;
713 } while (/*CONSTCOND*/ 0);
716 case RIO_SETDEFAULTS:
718 struct redparams *rp;
721 rp = (struct redparams *)addr;
722 for (i = 0; i < RIO_NDROPPREC; i++)
723 default_rio_params[i] = rp[i];
724 } while (/*CONSTCOND*/ 0);
742 if (ALTQ_IS_ENABLED(rqp->rq_ifq))
743 altq_disable(rqp->rq_ifq);
745 if ((error = altq_detach(rqp->rq_ifq)))
749 rio_list = rqp->rq_next;
751 for (tmp = rio_list; tmp != NULL; tmp = tmp->rq_next)
752 if (tmp->rq_next == rqp) {
753 tmp->rq_next = rqp->rq_next;
757 printf("rio_detach: no state found in rio_list!\n");
760 rio_destroy(rqp->rq_rio);
761 free(rqp->rq_q, M_DEVBUF);
767 * rio support routines
770 rio_request(ifq, req, arg)
775 rio_queue_t *rqp = (rio_queue_t *)ifq->altq_disc;
777 IFQ_LOCK_ASSERT(ifq);
782 if (ALTQ_IS_ENABLED(ifq))
792 * returns: 0 when successfully queued.
793 * ENOBUFS when drop occurs.
796 rio_enqueue(ifq, m, pktattr)
799 struct altq_pktattr *pktattr;
801 rio_queue_t *rqp = (rio_queue_t *)ifq->altq_disc;
804 IFQ_LOCK_ASSERT(ifq);
806 if (rio_addq(rqp->rq_rio, rqp->rq_q, m, pktattr) == 0)
815 * must be called in splimp.
817 * returns: mbuf dequeued.
818 * NULL when no packet is available in the queue.
826 rio_queue_t *rqp = (rio_queue_t *)ifq->altq_disc;
827 struct mbuf *m = NULL;
829 IFQ_LOCK_ASSERT(ifq);
831 if (op == ALTDQ_POLL)
832 return qhead(rqp->rq_q);
834 m = rio_getq(rqp->rq_rio, rqp->rq_q);
842 static struct altqsw rio_sw =
843 {"rio", rioopen, rioclose, rioioctl};
845 ALTQ_MODULE(altq_rio, ALTQT_RIO, &rio_sw);
846 MODULE_VERSION(altq_rio, 1);
847 MODULE_DEPEND(altq_rio, altq_red, 1, 1, 1);
849 #endif /* KLD_MODULE */
850 #endif /* ALTQ3_COMPAT */
852 #endif /* ALTQ_RIO */