2 * Copyright (C) 1997-2003
3 * Sony Computer Science Laboratories Inc. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
14 * THIS SOFTWARE IS PROVIDED BY SONY CSL AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL SONY CSL OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28 * Copyright (c) 1990-1994 Regents of the University of California.
29 * All rights reserved.
31 * Redistribution and use in source and binary forms, with or without
32 * modification, are permitted provided that the following conditions
34 * 1. Redistributions of source code must retain the above copyright
35 * notice, this list of conditions and the following disclaimer.
36 * 2. Redistributions in binary form must reproduce the above copyright
37 * notice, this list of conditions and the following disclaimer in the
38 * documentation and/or other materials provided with the distribution.
39 * 3. All advertising materials mentioning features or use of this software
40 * must display the following acknowledgement:
41 * This product includes software developed by the Computer Systems
42 * Engineering Group at Lawrence Berkeley Laboratory.
43 * 4. Neither the name of the University nor of the Laboratory may be used
44 * to endorse or promote products derived from this software without
45 * specific prior written permission.
47 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
48 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
49 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
50 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
51 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
52 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
53 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
54 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
55 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
56 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
59 * $KAME: altq_red.c,v 1.18 2003/09/05 22:40:36 itojun Exp $
65 #include "opt_inet6.h"
66 #ifdef ALTQ_RED /* red is enabled by ALTQ_RED option in opt_altq.h */
68 #include <sys/param.h>
69 #include <sys/malloc.h>
71 #include <sys/socket.h>
72 #include <sys/systm.h>
73 #include <sys/errno.h>
74 #if 1 /* ALTQ3_COMPAT */
75 #include <sys/sockio.h>
77 #include <sys/kernel.h>
79 #include <sys/queue.h>
82 #endif /* ALTQ3_COMPAT */
85 #include <net/if_var.h>
87 #include <netinet/in.h>
88 #include <netinet/in_systm.h>
89 #include <netinet/ip.h>
91 #include <netinet/ip6.h>
94 #include <netpfil/pf/pf.h>
95 #include <netpfil/pf/pf_altq.h>
96 #include <netpfil/pf/pf_mtag.h>
97 #include <net/altq/altq.h>
98 #include <net/altq/altq_red.h>
101 * ALTQ/RED (Random Early Detection) implementation using 32-bit
102 * fixed-point calculation.
104 * written by kjc using the ns code as a reference.
105 * you can learn more about red and ns from Sally's home page at
106 * http://www-nrg.ee.lbl.gov/floyd/
108 * most of the red parameter values are fixed in this implementation
109 * to prevent fixed-point overflow/underflow.
110 * if you change the parameters, watch out for overflow/underflow!
112 * the parameters used are recommended values by Sally.
113 * the corresponding ns config looks:
115 * minthresh=5 maxthresh=15 queue-size=60
118 * bytes=false (can't be handled by 32-bit fixed-point)
119 * doubleq=false dqthresh=false
123 * alternative red parameters for a slow link.
125 * assume the queue length becomes from zero to L and keeps L, it takes
126 * N packets for q_avg to reach 63% of L.
127 * when q_weight is 0.002, N is about 500 packets.
128 * for a slow link like dial-up, 500 packets takes more than 1 minute!
129 * when q_weight is 0.008, N is about 127 packets.
130 * when q_weight is 0.016, N is about 63 packets.
131 * bursts of 50 packets are allowed for 0.002, bursts of 25 packets
132 * are allowed for 0.016.
133 * see Sally's paper for more details.
135 /* normal red parameters */
136 #define W_WEIGHT 512 /* inverse of weight of EWMA (511/512) */
137 /* q_weight = 0.00195 */
139 /* red parameters for a slow link */
140 #define W_WEIGHT_1 128 /* inverse of weight of EWMA (127/128) */
141 /* q_weight = 0.0078125 */
143 /* red parameters for a very slow link (e.g., dialup) */
144 #define W_WEIGHT_2 64 /* inverse of weight of EWMA (63/64) */
145 /* q_weight = 0.015625 */
147 /* fixed-point uses 12-bit decimal places */
148 #define FP_SHIFT 12 /* fixed-point shift */
150 /* red parameters for drop probability */
151 #define INV_P_MAX 10 /* inverse of max drop probability */
152 #define TH_MIN 5 /* min threshold */
153 #define TH_MAX 15 /* max threshold */
155 #define RED_LIMIT 60 /* default max queue length */
156 #define RED_STATS /* collect statistics */
159 * our default policy for forced-drop is drop-tail.
160 * (in altq-1.1.2 or earlier, the default was random-drop.
161 * but it makes more sense to punish the cause of the surge.)
162 * to switch to the random-drop policy, define "RED_RANDOM_DROP".
165 /* default red parameter values */
166 static int default_th_min = TH_MIN;
167 static int default_th_max = TH_MAX;
168 static int default_inv_pmax = INV_P_MAX;
171 * red support routines
174 red_alloc(int weight, int inv_pmax, int th_min, int th_max, int flags,
181 rp = malloc(sizeof(red_t), M_DEVBUF, M_NOWAIT | M_ZERO);
186 rp->red_weight = W_WEIGHT;
188 rp->red_weight = weight;
190 /* allocate weight table */
191 rp->red_wtab = wtab_alloc(rp->red_weight);
192 if (rp->red_wtab == NULL) {
201 rp->red_inv_pmax = default_inv_pmax;
203 rp->red_inv_pmax = inv_pmax;
205 rp->red_thmin = default_th_min;
207 rp->red_thmin = th_min;
209 rp->red_thmax = default_th_max;
211 rp->red_thmax = th_max;
213 rp->red_flags = flags;
216 /* default packet time: 1000 bytes / 10Mbps * 8 * 1000000 */
217 rp->red_pkttime = 800;
219 rp->red_pkttime = pkttime;
222 /* when the link is very slow, adjust red parameters */
223 npkts_per_sec = 1000000 / rp->red_pkttime;
224 if (npkts_per_sec < 50) {
225 /* up to about 400Kbps */
226 rp->red_weight = W_WEIGHT_2;
227 } else if (npkts_per_sec < 300) {
228 /* up to about 2.4Mbps */
229 rp->red_weight = W_WEIGHT_1;
233 /* calculate wshift. weight must be power of 2 */
235 for (i = 0; w > 1; i++)
238 w = 1 << rp->red_wshift;
239 if (w != rp->red_weight) {
240 printf("invalid weight value %d for red! use %d\n",
246 * thmin_s and thmax_s are scaled versions of th_min and th_max
247 * to be compared with avg.
249 rp->red_thmin_s = rp->red_thmin << (rp->red_wshift + FP_SHIFT);
250 rp->red_thmax_s = rp->red_thmax << (rp->red_wshift + FP_SHIFT);
253 * precompute probability denominator
254 * probd = (2 * (TH_MAX-TH_MIN) / pmax) in fixed-point
256 rp->red_probd = (2 * (rp->red_thmax - rp->red_thmin)
257 * rp->red_inv_pmax) << FP_SHIFT;
259 microtime(&rp->red_last);
264 red_destroy(red_t *rp)
266 wtab_destroy(rp->red_wtab);
271 red_getstats(red_t *rp, struct redstats *sp)
273 sp->q_avg = rp->red_avg >> rp->red_wshift;
274 sp->xmit_cnt = rp->red_stats.xmit_cnt;
275 sp->drop_cnt = rp->red_stats.drop_cnt;
276 sp->drop_forced = rp->red_stats.drop_forced;
277 sp->drop_unforced = rp->red_stats.drop_unforced;
278 sp->marked_packets = rp->red_stats.marked_packets;
282 red_addq(red_t *rp, class_queue_t *q, struct mbuf *m,
283 struct altq_pktattr *pktattr)
291 * if we were idle, we pretend that n packets arrived during
300 t = (now.tv_sec - rp->red_last.tv_sec);
303 * being idle for more than 1 minute, set avg to zero.
304 * this prevents t from overflow.
308 t = t * 1000000 + (now.tv_usec - rp->red_last.tv_usec);
309 n = t / rp->red_pkttime - 1;
311 /* the following line does (avg = (1 - Wq)^n * avg) */
313 avg = (avg >> FP_SHIFT) *
314 pow_w(rp->red_wtab, n);
318 /* run estimator. (note: avg is scaled by WEIGHT in fixed-point) */
319 avg += (qlen(q) << FP_SHIFT) - (avg >> rp->red_wshift);
320 rp->red_avg = avg; /* save the new value */
323 * red_count keeps a tally of arriving traffic that has not
328 /* see if we drop early */
329 droptype = DTYPE_NODROP;
330 if (avg >= rp->red_thmin_s && qlen(q) > 1) {
331 if (avg >= rp->red_thmax_s) {
332 /* avg >= th_max: forced drop */
333 droptype = DTYPE_FORCED;
334 } else if (rp->red_old == 0) {
335 /* first exceeds th_min */
338 } else if (drop_early((avg - rp->red_thmin_s) >> rp->red_wshift,
339 rp->red_probd, rp->red_count)) {
340 /* mark or drop by red */
341 if ((rp->red_flags & REDF_ECN) &&
342 mark_ecn(m, pktattr, rp->red_flags)) {
343 /* successfully marked. do not drop. */
346 rp->red_stats.marked_packets++;
349 /* unforced drop by red */
350 droptype = DTYPE_EARLY;
359 * if the queue length hits the hard limit, it's a forced drop.
361 if (droptype == DTYPE_NODROP && qlen(q) >= qlimit(q))
362 droptype = DTYPE_FORCED;
364 #ifdef RED_RANDOM_DROP
365 /* if successful or forced drop, enqueue this packet. */
366 if (droptype != DTYPE_EARLY)
369 /* if successful, enqueue this packet. */
370 if (droptype == DTYPE_NODROP)
373 if (droptype != DTYPE_NODROP) {
374 if (droptype == DTYPE_EARLY) {
375 /* drop the incoming packet */
377 rp->red_stats.drop_unforced++;
380 /* forced drop, select a victim packet in the queue. */
381 #ifdef RED_RANDOM_DROP
385 rp->red_stats.drop_forced++;
389 PKTCNTR_ADD(&rp->red_stats.drop_cnt, m_pktlen(m));
395 /* successfully queued */
397 PKTCNTR_ADD(&rp->red_stats.xmit_cnt, m_pktlen(m));
403 * early-drop probability is calculated as follows:
404 * prob = p_max * (avg - th_min) / (th_max - th_min)
405 * prob_a = prob / (2 - count*prob)
406 * = (avg-th_min) / (2*(th_max-th_min)*inv_p_max - count*(avg-th_min))
407 * here prob_a increases as successive undrop count increases.
408 * (prob_a starts from prob/2, becomes prob when (count == (1 / prob)),
409 * becomes 1 when (count >= (2 / prob))).
412 drop_early(int fp_len, int fp_probd, int count)
414 int d; /* denominator of drop-probability */
416 d = fp_probd - count * fp_len;
418 /* count exceeds the hard limit: drop or mark */
422 * now the range of d is [1..600] in fixed-point. (when
423 * th_max-th_min=10 and p_max=1/30)
424 * drop probability = (avg - TH_MIN) / d
427 if ((arc4random() % d) < fp_len) {
436 * try to mark CE bit to the packet.
437 * returns 1 if successfully marked, 0 otherwise.
440 mark_ecn(struct mbuf *m, struct altq_pktattr *pktattr, int flags)
446 at = pf_find_mtag(m);
452 /* verify that pattr_hdr is within the mbuf data */
453 for (m0 = m; m0 != NULL; m0 = m0->m_next)
454 if (((caddr_t)hdr >= m0->m_data) &&
455 ((caddr_t)hdr < m0->m_data + m0->m_len))
458 /* ick, tag info is stale */
462 switch (((struct ip *)hdr)->ip_v) {
464 if (flags & REDF_ECN4) {
470 return (0); /* version mismatch! */
472 if ((ip->ip_tos & IPTOS_ECN_MASK) == IPTOS_ECN_NOTECT)
473 return (0); /* not-ECT */
474 if ((ip->ip_tos & IPTOS_ECN_MASK) == IPTOS_ECN_CE)
475 return (1); /* already marked */
478 * ecn-capable but not marked,
479 * mark CE and update checksum
482 ip->ip_tos |= IPTOS_ECN_CE;
484 * update checksum (from RFC1624)
485 * HC' = ~(~HC + ~m + m')
487 sum = ~ntohs(ip->ip_sum) & 0xffff;
488 sum += (~otos & 0xffff) + ip->ip_tos;
489 sum = (sum >> 16) + (sum & 0xffff);
490 sum += (sum >> 16); /* add carry */
491 ip->ip_sum = htons(~sum & 0xffff);
496 case (IPV6_VERSION >> 4):
497 if (flags & REDF_ECN6) {
498 struct ip6_hdr *ip6 = hdr;
501 flowlabel = ntohl(ip6->ip6_flow);
502 if ((flowlabel >> 28) != 6)
503 return (0); /* version mismatch! */
504 if ((flowlabel & (IPTOS_ECN_MASK << 20)) ==
505 (IPTOS_ECN_NOTECT << 20))
506 return (0); /* not-ECT */
507 if ((flowlabel & (IPTOS_ECN_MASK << 20)) ==
508 (IPTOS_ECN_CE << 20))
509 return (1); /* already marked */
511 * ecn-capable but not marked, mark CE
513 flowlabel |= (IPTOS_ECN_CE << 20);
514 ip6->ip6_flow = htonl(flowlabel);
532 if ((m = _getq(q)) == NULL) {
533 if (rp->red_idle == 0) {
535 microtime(&rp->red_last);
545 * helper routine to calibrate avg during idle.
546 * pow_w(wtab, n) returns (1 - Wq)^n in fixed-point
547 * here Wq = 1/weight and the code assumes Wq is close to zero.
549 * w_tab[n] holds ((1 - Wq)^(2^n)) in fixed-point.
551 static struct wtab *wtab_list = NULL; /* pointer to wtab list */
554 wtab_alloc(int weight)
559 for (w = wtab_list; w != NULL; w = w->w_next)
560 if (w->w_weight == weight) {
565 w = malloc(sizeof(struct wtab), M_DEVBUF, M_NOWAIT | M_ZERO);
568 w->w_weight = weight;
570 w->w_next = wtab_list;
573 /* initialize the weight table */
574 w->w_tab[0] = ((weight - 1) << FP_SHIFT) / weight;
575 for (i = 1; i < 32; i++) {
576 w->w_tab[i] = (w->w_tab[i-1] * w->w_tab[i-1]) >> FP_SHIFT;
577 if (w->w_tab[i] == 0 && w->w_param_max == 0)
578 w->w_param_max = 1 << i;
585 wtab_destroy(struct wtab *w)
589 if (--w->w_refcount > 0)
593 wtab_list = w->w_next;
594 else for (prev = wtab_list; prev->w_next != NULL; prev = prev->w_next)
595 if (prev->w_next == w) {
596 prev->w_next = w->w_next;
605 pow_w(struct wtab *w, int n)
610 if (n >= w->w_param_max)
621 val = (val * w->w_tab[i]) >> FP_SHIFT;
630 #endif /* ALTQ_RED */