Annotation of sys/altq/altq_red.c, Revision 1.1.1.1
1.1 nbrk 1: /* $OpenBSD: altq_red.c,v 1.13 2007/05/28 17:16:38 henning Exp $ */
2: /* $KAME: altq_red.c,v 1.10 2002/04/03 05:38:51 kjc Exp $ */
3:
4: /*
5: * Copyright (C) 1997-2002
6: * Sony Computer Science Laboratories Inc. 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: *
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
27: * SUCH DAMAGE.
28: *
29: */
30: /*
31: * Copyright (c) 1990-1994 Regents of the University of California.
32: * All rights reserved.
33: *
34: * Redistribution and use in source and binary forms, with or without
35: * modification, are permitted provided that the following conditions
36: * are met:
37: * 1. Redistributions of source code must retain the above copyright
38: * notice, this list of conditions and the following disclaimer.
39: * 2. Redistributions in binary form must reproduce the above copyright
40: * notice, this list of conditions and the following disclaimer in the
41: * documentation and/or other materials provided with the distribution.
42: * 3. All advertising materials mentioning features or use of this software
43: * must display the following acknowledgement:
44: * This product includes software developed by the Computer Systems
45: * Engineering Group at Lawrence Berkeley Laboratory.
46: * 4. Neither the name of the University nor of the Laboratory may be used
47: * to endorse or promote products derived from this software without
48: * specific prior written permission.
49: *
50: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
51: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
52: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
53: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
54: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
55: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
56: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
57: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
58: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
59: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
60: * SUCH DAMAGE.
61: */
62:
63: #include <sys/param.h>
64: #include <sys/malloc.h>
65: #include <sys/mbuf.h>
66: #include <sys/socket.h>
67: #include <sys/systm.h>
68: #include <sys/errno.h>
69:
70: #include <net/if.h>
71: #include <net/if_types.h>
72:
73: #include <netinet/in.h>
74: #include <netinet/in_systm.h>
75: #include <netinet/ip.h>
76: #ifdef INET6
77: #include <netinet/ip6.h>
78: #endif
79:
80: #include <net/pfvar.h>
81: #include <altq/altq.h>
82: #include <altq/altq_red.h>
83:
84: /*
85: * ALTQ/RED (Random Early Detection) implementation using 32-bit
86: * fixed-point calculation.
87: *
88: * written by kjc using the ns code as a reference.
89: * you can learn more about red and ns from Sally's home page at
90: * http://www-nrg.ee.lbl.gov/floyd/
91: *
92: * most of the red parameter values are fixed in this implementation
93: * to prevent fixed-point overflow/underflow.
94: * if you change the parameters, watch out for overflow/underflow!
95: *
96: * the parameters used are recommended values by Sally.
97: * the corresponding ns config looks:
98: * q_weight=0.00195
99: * minthresh=5 maxthresh=15 queue-size=60
100: * linterm=30
101: * dropmech=drop-tail
102: * bytes=false (can't be handled by 32-bit fixed-point)
103: * doubleq=false dqthresh=false
104: * wait=true
105: */
106: /*
107: * alternative red parameters for a slow link.
108: *
109: * assume the queue length becomes from zero to L and keeps L, it takes
110: * N packets for q_avg to reach 63% of L.
111: * when q_weight is 0.002, N is about 500 packets.
112: * for a slow link like dial-up, 500 packets takes more than 1 minute!
113: * when q_weight is 0.008, N is about 127 packets.
114: * when q_weight is 0.016, N is about 63 packets.
115: * bursts of 50 packets are allowed for 0.002, bursts of 25 packets
116: * are allowed for 0.016.
117: * see Sally's paper for more details.
118: */
119: /* normal red parameters */
120: #define W_WEIGHT 512 /* inverse of weight of EWMA (511/512) */
121: /* q_weight = 0.00195 */
122:
123: /* red parameters for a slow link */
124: #define W_WEIGHT_1 128 /* inverse of weight of EWMA (127/128) */
125: /* q_weight = 0.0078125 */
126:
127: /* red parameters for a very slow link (e.g., dialup) */
128: #define W_WEIGHT_2 64 /* inverse of weight of EWMA (63/64) */
129: /* q_weight = 0.015625 */
130:
131: /* fixed-point uses 12-bit decimal places */
132: #define FP_SHIFT 12 /* fixed-point shift */
133:
134: /* red parameters for drop probability */
135: #define INV_P_MAX 10 /* inverse of max drop probability */
136: #define TH_MIN 5 /* min threshold */
137: #define TH_MAX 15 /* max threshold */
138:
139: #define RED_LIMIT 60 /* default max queue length */
140: #define RED_STATS /* collect statistics */
141:
142: /*
143: * our default policy for forced-drop is drop-tail.
144: * (in altq-1.1.2 or earlier, the default was random-drop.
145: * but it makes more sense to punish the cause of the surge.)
146: * to switch to the random-drop policy, define "RED_RANDOM_DROP".
147: */
148:
149: /* default red parameter values */
150: static int default_th_min = TH_MIN;
151: static int default_th_max = TH_MAX;
152: static int default_inv_pmax = INV_P_MAX;
153:
154: /*
155: * red support routines
156: */
157: red_t *
158: red_alloc(int weight, int inv_pmax, int th_min, int th_max, int flags,
159: int pkttime)
160: {
161: red_t *rp;
162: int w, i;
163: int npkts_per_sec;
164:
165: MALLOC(rp, red_t *, sizeof(red_t), M_DEVBUF, M_WAITOK);
166: if (rp == NULL)
167: return (NULL);
168: bzero(rp, sizeof(red_t));
169:
170: rp->red_avg = 0;
171: rp->red_idle = 1;
172:
173: if (weight == 0)
174: rp->red_weight = W_WEIGHT;
175: else
176: rp->red_weight = weight;
177: if (inv_pmax == 0)
178: rp->red_inv_pmax = default_inv_pmax;
179: else
180: rp->red_inv_pmax = inv_pmax;
181: if (th_min == 0)
182: rp->red_thmin = default_th_min;
183: else
184: rp->red_thmin = th_min;
185: if (th_max == 0)
186: rp->red_thmax = default_th_max;
187: else
188: rp->red_thmax = th_max;
189:
190: rp->red_flags = flags;
191:
192: if (pkttime == 0)
193: /* default packet time: 1000 bytes / 10Mbps * 8 * 1000000 */
194: rp->red_pkttime = 800;
195: else
196: rp->red_pkttime = pkttime;
197:
198: if (weight == 0) {
199: /* when the link is very slow, adjust red parameters */
200: npkts_per_sec = 1000000 / rp->red_pkttime;
201: if (npkts_per_sec < 50) {
202: /* up to about 400Kbps */
203: rp->red_weight = W_WEIGHT_2;
204: } else if (npkts_per_sec < 300) {
205: /* up to about 2.4Mbps */
206: rp->red_weight = W_WEIGHT_1;
207: }
208: }
209:
210: /* calculate wshift. weight must be power of 2 */
211: w = rp->red_weight;
212: for (i = 0; w > 1; i++)
213: w = w >> 1;
214: rp->red_wshift = i;
215: w = 1 << rp->red_wshift;
216: if (w != rp->red_weight) {
217: printf("invalid weight value %d for red! use %d\n",
218: rp->red_weight, w);
219: rp->red_weight = w;
220: }
221:
222: /*
223: * thmin_s and thmax_s are scaled versions of th_min and th_max
224: * to be compared with avg.
225: */
226: rp->red_thmin_s = rp->red_thmin << (rp->red_wshift + FP_SHIFT);
227: rp->red_thmax_s = rp->red_thmax << (rp->red_wshift + FP_SHIFT);
228:
229: /*
230: * precompute probability denominator
231: * probd = (2 * (TH_MAX-TH_MIN) / pmax) in fixed-point
232: */
233: rp->red_probd = (2 * (rp->red_thmax - rp->red_thmin)
234: * rp->red_inv_pmax) << FP_SHIFT;
235:
236: /* allocate weight table */
237: rp->red_wtab = wtab_alloc(rp->red_weight);
238:
239: microtime(&rp->red_last);
240: return (rp);
241: }
242:
243: void
244: red_destroy(red_t *rp)
245: {
246: wtab_destroy(rp->red_wtab);
247: FREE(rp, M_DEVBUF);
248: }
249:
250: void
251: red_getstats(red_t *rp, struct redstats *sp)
252: {
253: sp->q_avg = rp->red_avg >> rp->red_wshift;
254: sp->xmit_cnt = rp->red_stats.xmit_cnt;
255: sp->drop_cnt = rp->red_stats.drop_cnt;
256: sp->drop_forced = rp->red_stats.drop_forced;
257: sp->drop_unforced = rp->red_stats.drop_unforced;
258: sp->marked_packets = rp->red_stats.marked_packets;
259: }
260:
261: int
262: red_addq(red_t *rp, class_queue_t *q, struct mbuf *m,
263: struct altq_pktattr *pktattr)
264: {
265: int avg, droptype;
266: int n;
267:
268: avg = rp->red_avg;
269:
270: /*
271: * if we were idle, we pretend that n packets arrived during
272: * the idle period.
273: */
274: if (rp->red_idle) {
275: struct timeval now;
276: int t;
277:
278: rp->red_idle = 0;
279: microtime(&now);
280: t = (now.tv_sec - rp->red_last.tv_sec);
281: if (t > 60) {
282: /*
283: * being idle for more than 1 minute, set avg to zero.
284: * this prevents t from overflow.
285: */
286: avg = 0;
287: } else {
288: t = t * 1000000 + (now.tv_usec - rp->red_last.tv_usec);
289: n = t / rp->red_pkttime - 1;
290:
291: /* the following line does (avg = (1 - Wq)^n * avg) */
292: if (n > 0)
293: avg = (avg >> FP_SHIFT) *
294: pow_w(rp->red_wtab, n);
295: }
296: }
297:
298: /* run estimator. (note: avg is scaled by WEIGHT in fixed-point) */
299: avg += (qlen(q) << FP_SHIFT) - (avg >> rp->red_wshift);
300: rp->red_avg = avg; /* save the new value */
301:
302: /*
303: * red_count keeps a tally of arriving traffic that has not
304: * been dropped.
305: */
306: rp->red_count++;
307:
308: /* see if we drop early */
309: droptype = DTYPE_NODROP;
310: if (avg >= rp->red_thmin_s && qlen(q) > 1) {
311: if (avg >= rp->red_thmax_s) {
312: /* avg >= th_max: forced drop */
313: droptype = DTYPE_FORCED;
314: } else if (rp->red_old == 0) {
315: /* first exceeds th_min */
316: rp->red_count = 1;
317: rp->red_old = 1;
318: } else if (drop_early((avg - rp->red_thmin_s) >> rp->red_wshift,
319: rp->red_probd, rp->red_count)) {
320: /* mark or drop by red */
321: if ((rp->red_flags & REDF_ECN) &&
322: mark_ecn(m, pktattr, rp->red_flags)) {
323: /* successfully marked. do not drop. */
324: rp->red_count = 0;
325: #ifdef RED_STATS
326: rp->red_stats.marked_packets++;
327: #endif
328: } else {
329: /* unforced drop by red */
330: droptype = DTYPE_EARLY;
331: }
332: }
333: } else {
334: /* avg < th_min */
335: rp->red_old = 0;
336: }
337:
338: /*
339: * if the queue length hits the hard limit, it's a forced drop.
340: */
341: if (droptype == DTYPE_NODROP && qlen(q) >= qlimit(q))
342: droptype = DTYPE_FORCED;
343:
344: #ifdef RED_RANDOM_DROP
345: /* if successful or forced drop, enqueue this packet. */
346: if (droptype != DTYPE_EARLY)
347: _addq(q, m);
348: #else
349: /* if successful, enqueue this packet. */
350: if (droptype == DTYPE_NODROP)
351: _addq(q, m);
352: #endif
353: if (droptype != DTYPE_NODROP) {
354: if (droptype == DTYPE_EARLY) {
355: /* drop the incoming packet */
356: #ifdef RED_STATS
357: rp->red_stats.drop_unforced++;
358: #endif
359: } else {
360: /* forced drop, select a victim packet in the queue. */
361: #ifdef RED_RANDOM_DROP
362: m = _getq_random(q);
363: #endif
364: #ifdef RED_STATS
365: rp->red_stats.drop_forced++;
366: #endif
367: }
368: #ifdef RED_STATS
369: PKTCNTR_ADD(&rp->red_stats.drop_cnt, m_pktlen(m));
370: #endif
371: rp->red_count = 0;
372: m_freem(m);
373: return (-1);
374: }
375: /* successfully queued */
376: #ifdef RED_STATS
377: PKTCNTR_ADD(&rp->red_stats.xmit_cnt, m_pktlen(m));
378: #endif
379: return (0);
380: }
381:
382: /*
383: * early-drop probability is calculated as follows:
384: * prob = p_max * (avg - th_min) / (th_max - th_min)
385: * prob_a = prob / (2 - count*prob)
386: * = (avg-th_min) / (2*(th_max-th_min)*inv_p_max - count*(avg-th_min))
387: * here prob_a increases as successive undrop count increases.
388: * (prob_a starts from prob/2, becomes prob when (count == (1 / prob)),
389: * becomes 1 when (count >= (2 / prob))).
390: */
391: int
392: drop_early(int fp_len, int fp_probd, int count)
393: {
394: int d; /* denominator of drop-probability */
395:
396: d = fp_probd - count * fp_len;
397: if (d <= 0)
398: /* count exceeds the hard limit: drop or mark */
399: return (1);
400:
401: /*
402: * now the range of d is [1..600] in fixed-point. (when
403: * th_max-th_min=10 and p_max=1/30)
404: * drop probability = (avg - TH_MIN) / d
405: */
406:
407: if ((random() % d) < fp_len) {
408: /* drop or mark */
409: return (1);
410: }
411: /* no drop/mark */
412: return (0);
413: }
414:
415: /*
416: * try to mark CE bit to the packet.
417: * returns 1 if successfully marked, 0 otherwise.
418: */
419: int
420: mark_ecn(struct mbuf *m, struct altq_pktattr *pktattr, int flags)
421: {
422: struct mbuf *m0;
423: void *hdr;
424:
425: hdr = m->m_pkthdr.pf.hdr;
426:
427: /* verify that pattr_hdr is within the mbuf data */
428: for (m0 = m; m0 != NULL; m0 = m0->m_next)
429: if (((caddr_t)(hdr) >= m0->m_data) &&
430: ((caddr_t)(hdr) < m0->m_data + m0->m_len))
431: break;
432: if (m0 == NULL) {
433: /* ick, tag info is stale */
434: return (0);
435: }
436:
437: switch (((struct ip *)hdr)->ip_v) {
438: case 4:
439: if (flags & REDF_ECN4) {
440: struct ip *ip = hdr;
441: u_int8_t otos;
442: int sum;
443:
444: if ((ip->ip_tos & IPTOS_ECN_MASK) == IPTOS_ECN_NOTECT)
445: return (0); /* not-ECT */
446: if ((ip->ip_tos & IPTOS_ECN_MASK) == IPTOS_ECN_CE)
447: return (1); /* already marked */
448:
449: /*
450: * ecn-capable but not marked,
451: * mark CE and update checksum
452: */
453: otos = ip->ip_tos;
454: ip->ip_tos |= IPTOS_ECN_CE;
455: /*
456: * update checksum (from RFC1624)
457: * HC' = ~(~HC + ~m + m')
458: */
459: sum = ~ntohs(ip->ip_sum) & 0xffff;
460: sum += (~otos & 0xffff) + ip->ip_tos;
461: sum = (sum >> 16) + (sum & 0xffff);
462: sum += (sum >> 16); /* add carry */
463: ip->ip_sum = htons(~sum & 0xffff);
464: return (1);
465: }
466: break;
467: #ifdef INET6
468: case 6:
469: if (flags & REDF_ECN6) {
470: struct ip6_hdr *ip6 = hdr;
471: u_int32_t flowlabel;
472:
473: flowlabel = ntohl(ip6->ip6_flow);
474: if ((flowlabel >> 28) != 6)
475: return (0); /* version mismatch! */
476: if ((flowlabel & (IPTOS_ECN_MASK << 20)) ==
477: (IPTOS_ECN_NOTECT << 20))
478: return (0); /* not-ECT */
479: if ((flowlabel & (IPTOS_ECN_MASK << 20)) ==
480: (IPTOS_ECN_CE << 20))
481: return (1); /* already marked */
482: /*
483: * ecn-capable but not marked, mark CE
484: */
485: flowlabel |= (IPTOS_ECN_CE << 20);
486: ip6->ip6_flow = htonl(flowlabel);
487: return (1);
488: }
489: break;
490: #endif /* INET6 */
491: }
492:
493: /* not marked */
494: return (0);
495: }
496:
497: struct mbuf *
498: red_getq(rp, q)
499: red_t *rp;
500: class_queue_t *q;
501: {
502: struct mbuf *m;
503:
504: if ((m = _getq(q)) == NULL) {
505: if (rp->red_idle == 0) {
506: rp->red_idle = 1;
507: microtime(&rp->red_last);
508: }
509: return NULL;
510: }
511:
512: rp->red_idle = 0;
513: return (m);
514: }
515:
516: /*
517: * helper routine to calibrate avg during idle.
518: * pow_w(wtab, n) returns (1 - Wq)^n in fixed-point
519: * here Wq = 1/weight and the code assumes Wq is close to zero.
520: *
521: * w_tab[n] holds ((1 - Wq)^(2^n)) in fixed-point.
522: */
523: static struct wtab *wtab_list = NULL; /* pointer to wtab list */
524:
525: struct wtab *
526: wtab_alloc(int weight)
527: {
528: struct wtab *w;
529: int i;
530:
531: for (w = wtab_list; w != NULL; w = w->w_next)
532: if (w->w_weight == weight) {
533: w->w_refcount++;
534: return (w);
535: }
536:
537: MALLOC(w, struct wtab *, sizeof(struct wtab), M_DEVBUF, M_WAITOK);
538: if (w == NULL)
539: panic("wtab_alloc: malloc failed!");
540: bzero(w, sizeof(struct wtab));
541: w->w_weight = weight;
542: w->w_refcount = 1;
543: w->w_next = wtab_list;
544: wtab_list = w;
545:
546: /* initialize the weight table */
547: w->w_tab[0] = ((weight - 1) << FP_SHIFT) / weight;
548: for (i = 1; i < 32; i++) {
549: w->w_tab[i] = (w->w_tab[i-1] * w->w_tab[i-1]) >> FP_SHIFT;
550: if (w->w_tab[i] == 0 && w->w_param_max == 0)
551: w->w_param_max = 1 << i;
552: }
553:
554: return (w);
555: }
556:
557: int
558: wtab_destroy(struct wtab *w)
559: {
560: struct wtab *prev;
561:
562: if (--w->w_refcount > 0)
563: return (0);
564:
565: if (wtab_list == w)
566: wtab_list = w->w_next;
567: else for (prev = wtab_list; prev->w_next != NULL; prev = prev->w_next)
568: if (prev->w_next == w) {
569: prev->w_next = w->w_next;
570: break;
571: }
572:
573: FREE(w, M_DEVBUF);
574: return (0);
575: }
576:
577: int32_t
578: pow_w(struct wtab *w, int n)
579: {
580: int i, bit;
581: int32_t val;
582:
583: if (n >= w->w_param_max)
584: return (0);
585:
586: val = 1 << FP_SHIFT;
587: if (n <= 0)
588: return (val);
589:
590: bit = 1;
591: i = 0;
592: while (n) {
593: if (n & bit) {
594: val = (val * w->w_tab[i]) >> FP_SHIFT;
595: n &= ~bit;
596: }
597: i++;
598: bit <<= 1;
599: }
600: return (val);
601: }
CVSweb
![[BACK]](/icons/back.gif){kind=icon}
Return to altq_red.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / sys / altq