1/*- 2 * Copyright (C) 1997-2003 3 * Sony Computer Science Laboratories Inc. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 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. 13 * 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 24 * SUCH DAMAGE. 25 * 26 */ 27/*- 28 * Copyright (c) 1990-1994 Regents of the University of California. 29 * All rights reserved. 30 * 31 * Redistribution and use in source and binary forms, with or without 32 * modification, are permitted provided that the following conditions 33 * are met: 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. 46 * 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 57 * SUCH DAMAGE. 58 * 59 * $KAME: altq_red.c,v 1.18 2003/09/05 22:40:36 itojun Exp $ 60 * $FreeBSD$ 61 */ 62 63#include "opt_altq.h" 64#include "opt_inet.h" 65#include "opt_inet6.h" 66#ifdef ALTQ_RED /* red is enabled by ALTQ_RED option in opt_altq.h */ 67 68#include <sys/param.h> 69#include <sys/malloc.h> 70#include <sys/mbuf.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> 76#include <sys/proc.h> 77#include <sys/kernel.h> 78#ifdef ALTQ_FLOWVALVE 79#include <sys/queue.h> 80#include <sys/time.h> 81#endif 82#endif /* ALTQ3_COMPAT */ 83 84#include <net/if.h> 85#include <net/if_var.h> 86 87#include <netinet/in.h> 88#include <netinet/in_systm.h> 89#include <netinet/ip.h> 90#ifdef INET6 91#include <netinet/ip6.h> 92#endif 93 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> 99 100/* 101 * ALTQ/RED (Random Early Detection) implementation using 32-bit 102 * fixed-point calculation. 103 * 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/ 107 * 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! 111 * 112 * the parameters used are recommended values by Sally. 113 * the corresponding ns config looks: 114 * q_weight=0.00195 115 * minthresh=5 maxthresh=15 queue-size=60 116 * linterm=30 117 * dropmech=drop-tail 118 * bytes=false (can't be handled by 32-bit fixed-point) 119 * doubleq=false dqthresh=false 120 * wait=true 121 */ 122/* 123 * alternative red parameters for a slow link. 124 * 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. 134 */ 135/* normal red parameters */ 136#define W_WEIGHT 512 /* inverse of weight of EWMA (511/512) */ 137 /* q_weight = 0.00195 */ 138 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 */ 142 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 */ 146 147/* fixed-point uses 12-bit decimal places */ 148#define FP_SHIFT 12 /* fixed-point shift */ 149 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 */ 154 155#define RED_LIMIT 60 /* default max queue length */ 156#define RED_STATS /* collect statistics */ 157 158/* 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". 163 */ 164 165/* default red parameter values */ 166static int default_th_min = TH_MIN; 167static int default_th_max = TH_MAX; 168static int default_inv_pmax = INV_P_MAX; 169 170/* 171 * red support routines 172 */ 173red_t * 174red_alloc(int weight, int inv_pmax, int th_min, int th_max, int flags, 175 int pkttime) 176{ 177 red_t *rp; 178 int w, i; 179 int npkts_per_sec; 180 181 rp = malloc(sizeof(red_t), M_DEVBUF, M_NOWAIT | M_ZERO); 182 if (rp == NULL) 183 return (NULL); 184 185 if (weight == 0) 186 rp->red_weight = W_WEIGHT; 187 else 188 rp->red_weight = weight; 189 190 /* allocate weight table */ 191 rp->red_wtab = wtab_alloc(rp->red_weight); 192 if (rp->red_wtab == NULL) { 193 free(rp, M_DEVBUF); 194 return (NULL); 195 } 196 197 rp->red_avg = 0; 198 rp->red_idle = 1; 199 200 if (inv_pmax == 0) 201 rp->red_inv_pmax = default_inv_pmax; 202 else 203 rp->red_inv_pmax = inv_pmax; 204 if (th_min == 0) 205 rp->red_thmin = default_th_min; 206 else 207 rp->red_thmin = th_min; 208 if (th_max == 0) 209 rp->red_thmax = default_th_max; 210 else 211 rp->red_thmax = th_max; 212 213 rp->red_flags = flags; 214 215 if (pkttime == 0) 216 /* default packet time: 1000 bytes / 10Mbps * 8 * 1000000 */ 217 rp->red_pkttime = 800; 218 else 219 rp->red_pkttime = pkttime; 220 221 if (weight == 0) { 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; 230 } 231 } 232 233 /* calculate wshift. weight must be power of 2 */ 234 w = rp->red_weight; 235 for (i = 0; w > 1; i++) 236 w = w >> 1; 237 rp->red_wshift = i; 238 w = 1 << rp->red_wshift; 239 if (w != rp->red_weight) { 240 printf("invalid weight value %d for red! use %d\n", 241 rp->red_weight, w); 242 rp->red_weight = w; 243 } 244 245 /* 246 * thmin_s and thmax_s are scaled versions of th_min and th_max 247 * to be compared with avg. 248 */ 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); 251 252 /* 253 * precompute probability denominator 254 * probd = (2 * (TH_MAX-TH_MIN) / pmax) in fixed-point 255 */ 256 rp->red_probd = (2 * (rp->red_thmax - rp->red_thmin) 257 * rp->red_inv_pmax) << FP_SHIFT; 258 259 microtime(&rp->red_last); 260 return (rp); 261} 262 263void 264red_destroy(red_t *rp) 265{ 266 wtab_destroy(rp->red_wtab); 267 free(rp, M_DEVBUF); 268} 269 270void 271red_getstats(red_t *rp, struct redstats *sp) 272{ 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; 279} 280 281int 282red_addq(red_t *rp, class_queue_t *q, struct mbuf *m, 283 struct altq_pktattr *pktattr) 284{ 285 int avg, droptype; 286 int n; 287 288 avg = rp->red_avg; 289 290 /* 291 * if we were idle, we pretend that n packets arrived during 292 * the idle period. 293 */ 294 if (rp->red_idle) { 295 struct timeval now; 296 int t; 297 298 rp->red_idle = 0; 299 microtime(&now); 300 t = (now.tv_sec - rp->red_last.tv_sec); 301 if (t > 60) { 302 /* 303 * being idle for more than 1 minute, set avg to zero. 304 * this prevents t from overflow. 305 */ 306 avg = 0; 307 } else { 308 t = t * 1000000 + (now.tv_usec - rp->red_last.tv_usec); 309 n = t / rp->red_pkttime - 1; 310 311 /* the following line does (avg = (1 - Wq)^n * avg) */ 312 if (n > 0) 313 avg = (avg >> FP_SHIFT) * 314 pow_w(rp->red_wtab, n); 315 } 316 } 317 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 */ 321 322 /* 323 * red_count keeps a tally of arriving traffic that has not 324 * been dropped. 325 */ 326 rp->red_count++; 327 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 */ 336 rp->red_count = 1; 337 rp->red_old = 1; 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. */ 344 rp->red_count = 0; 345#ifdef RED_STATS 346 rp->red_stats.marked_packets++; 347#endif 348 } else { 349 /* unforced drop by red */ 350 droptype = DTYPE_EARLY; 351 } 352 } 353 } else { 354 /* avg < th_min */ 355 rp->red_old = 0; 356 } 357 358 /* 359 * if the queue length hits the hard limit, it's a forced drop. 360 */ 361 if (droptype == DTYPE_NODROP && qlen(q) >= qlimit(q)) 362 droptype = DTYPE_FORCED; 363 364#ifdef RED_RANDOM_DROP 365 /* if successful or forced drop, enqueue this packet. */ 366 if (droptype != DTYPE_EARLY) 367 _addq(q, m); 368#else 369 /* if successful, enqueue this packet. */ 370 if (droptype == DTYPE_NODROP) 371 _addq(q, m); 372#endif 373 if (droptype != DTYPE_NODROP) { 374 if (droptype == DTYPE_EARLY) { 375 /* drop the incoming packet */ 376#ifdef RED_STATS 377 rp->red_stats.drop_unforced++; 378#endif 379 } else { 380 /* forced drop, select a victim packet in the queue. */ 381#ifdef RED_RANDOM_DROP 382 m = _getq_random(q); 383#endif 384#ifdef RED_STATS 385 rp->red_stats.drop_forced++; 386#endif 387 } 388#ifdef RED_STATS 389 PKTCNTR_ADD(&rp->red_stats.drop_cnt, m_pktlen(m)); 390#endif 391 rp->red_count = 0; 392 m_freem(m); 393 return (-1); 394 } 395 /* successfully queued */ 396#ifdef RED_STATS 397 PKTCNTR_ADD(&rp->red_stats.xmit_cnt, m_pktlen(m)); 398#endif 399 return (0); 400} 401 402/* 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))). 410 */ 411int 412drop_early(int fp_len, int fp_probd, int count) 413{ 414 int d; /* denominator of drop-probability */ 415 416 d = fp_probd - count * fp_len; 417 if (d <= 0) 418 /* count exceeds the hard limit: drop or mark */ 419 return (1); 420 421 /* 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 425 */ 426 427 if ((arc4random() % d) < fp_len) { 428 /* drop or mark */ 429 return (1); 430 } 431 /* no drop/mark */ 432 return (0); 433} 434 435/* 436 * try to mark CE bit to the packet. 437 * returns 1 if successfully marked, 0 otherwise. 438 */ 439int 440mark_ecn(struct mbuf *m, struct altq_pktattr *pktattr, int flags) 441{ 442 struct mbuf *m0; 443 struct pf_mtag *at; 444 void *hdr; 445 446 at = pf_find_mtag(m); 447 if (at != NULL) { 448 hdr = at->hdr; 449 } else 450 return (0); 451 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)) 456 break; 457 if (m0 == NULL) { 458 /* ick, tag info is stale */ 459 return (0); 460 } 461 462 switch (((struct ip *)hdr)->ip_v) { 463 case IPVERSION: 464 if (flags & REDF_ECN4) { 465 struct ip *ip = hdr; 466 u_int8_t otos; 467 int sum; 468 469 if (ip->ip_v != 4) 470 return (0); /* version mismatch! */ 471 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 */ 476 477 /* 478 * ecn-capable but not marked, 479 * mark CE and update checksum 480 */ 481 otos = ip->ip_tos; 482 ip->ip_tos |= IPTOS_ECN_CE; 483 /* 484 * update checksum (from RFC1624) 485 * HC' = ~(~HC + ~m + m') 486 */ 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); 492 return (1); 493 } 494 break; 495#ifdef INET6 496 case (IPV6_VERSION >> 4): 497 if (flags & REDF_ECN6) { 498 struct ip6_hdr *ip6 = hdr; 499 u_int32_t flowlabel; 500 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 */ 510 /* 511 * ecn-capable but not marked, mark CE 512 */ 513 flowlabel |= (IPTOS_ECN_CE << 20); 514 ip6->ip6_flow = htonl(flowlabel); 515 return (1); 516 } 517 break; 518#endif /* INET6 */ 519 } 520 521 /* not marked */ 522 return (0); 523} 524 525struct mbuf * 526red_getq(rp, q) 527 red_t *rp; 528 class_queue_t *q; 529{ 530 struct mbuf *m; 531 532 if ((m = _getq(q)) == NULL) { 533 if (rp->red_idle == 0) { 534 rp->red_idle = 1; 535 microtime(&rp->red_last); 536 } 537 return NULL; 538 } 539 540 rp->red_idle = 0; 541 return (m); 542} 543 544/* 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. 548 * 549 * w_tab[n] holds ((1 - Wq)^(2^n)) in fixed-point. 550 */ 551static struct wtab *wtab_list = NULL; /* pointer to wtab list */ 552 553struct wtab * 554wtab_alloc(int weight) 555{ 556 struct wtab *w; 557 int i; 558 559 for (w = wtab_list; w != NULL; w = w->w_next) 560 if (w->w_weight == weight) { 561 w->w_refcount++; 562 return (w); 563 } 564 565 w = malloc(sizeof(struct wtab), M_DEVBUF, M_NOWAIT | M_ZERO); 566 if (w == NULL) 567 return (NULL); 568 w->w_weight = weight; 569 w->w_refcount = 1; 570 w->w_next = wtab_list; 571 wtab_list = w; 572 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; 579 } 580 581 return (w); 582} 583 584int 585wtab_destroy(struct wtab *w) 586{ 587 struct wtab *prev; 588 589 if (--w->w_refcount > 0) 590 return (0); 591 592 if (wtab_list == w) 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; 597 break; 598 } 599 600 free(w, M_DEVBUF); 601 return (0); 602} 603 604int32_t 605pow_w(struct wtab *w, int n) 606{ 607 int i, bit; 608 int32_t val; 609 610 if (n >= w->w_param_max) 611 return (0); 612 613 val = 1 << FP_SHIFT; 614 if (n <= 0) 615 return (val); 616 617 bit = 1; 618 i = 0; 619 while (n) { 620 if (n & bit) { 621 val = (val * w->w_tab[i]) >> FP_SHIFT; 622 n &= ~bit; 623 } 624 i++; 625 bit <<= 1; 626 } 627 return (val); 628} 629 630#endif /* ALTQ_RED */ 631