1130368Smlaier/* $FreeBSD$ */ 2130365Smlaier/* $KAME: altq_red.c,v 1.18 2003/09/05 22:40:36 itojun Exp $ */ 3130365Smlaier 4130365Smlaier/* 5130365Smlaier * Copyright (C) 1997-2003 6130365Smlaier * Sony Computer Science Laboratories Inc. All rights reserved. 7130365Smlaier * 8130365Smlaier * Redistribution and use in source and binary forms, with or without 9130365Smlaier * modification, are permitted provided that the following conditions 10130365Smlaier * are met: 11130365Smlaier * 1. Redistributions of source code must retain the above copyright 12130365Smlaier * notice, this list of conditions and the following disclaimer. 13130365Smlaier * 2. Redistributions in binary form must reproduce the above copyright 14130365Smlaier * notice, this list of conditions and the following disclaimer in the 15130365Smlaier * documentation and/or other materials provided with the distribution. 16130365Smlaier * 17130365Smlaier * THIS SOFTWARE IS PROVIDED BY SONY CSL AND CONTRIBUTORS ``AS IS'' AND 18130365Smlaier * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19130365Smlaier * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20130365Smlaier * ARE DISCLAIMED. IN NO EVENT SHALL SONY CSL OR CONTRIBUTORS BE LIABLE 21130365Smlaier * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22130365Smlaier * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23130365Smlaier * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24130365Smlaier * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25130365Smlaier * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26130365Smlaier * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27130365Smlaier * SUCH DAMAGE. 28130365Smlaier * 29130365Smlaier */ 30130365Smlaier/* 31130365Smlaier * Copyright (c) 1990-1994 Regents of the University of California. 32130365Smlaier * All rights reserved. 33130365Smlaier * 34130365Smlaier * Redistribution and use in source and binary forms, with or without 35130365Smlaier * modification, are permitted provided that the following conditions 36130365Smlaier * are met: 37130365Smlaier * 1. Redistributions of source code must retain the above copyright 38130365Smlaier * notice, this list of conditions and the following disclaimer. 39130365Smlaier * 2. Redistributions in binary form must reproduce the above copyright 40130365Smlaier * notice, this list of conditions and the following disclaimer in the 41130365Smlaier * documentation and/or other materials provided with the distribution. 42130365Smlaier * 3. All advertising materials mentioning features or use of this software 43130365Smlaier * must display the following acknowledgement: 44130365Smlaier * This product includes software developed by the Computer Systems 45130365Smlaier * Engineering Group at Lawrence Berkeley Laboratory. 46130365Smlaier * 4. Neither the name of the University nor of the Laboratory may be used 47130365Smlaier * to endorse or promote products derived from this software without 48130365Smlaier * specific prior written permission. 49130365Smlaier * 50130365Smlaier * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 51130365Smlaier * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 52130365Smlaier * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 53130365Smlaier * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 54130365Smlaier * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 55130365Smlaier * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 56130365Smlaier * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 57130365Smlaier * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 58130365Smlaier * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 59130365Smlaier * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 60130365Smlaier * SUCH DAMAGE. 61130365Smlaier */ 62130365Smlaier 63130365Smlaier#if defined(__FreeBSD__) || defined(__NetBSD__) 64130365Smlaier#include "opt_altq.h" 65130365Smlaier#include "opt_inet.h" 66130365Smlaier#ifdef __FreeBSD__ 67130365Smlaier#include "opt_inet6.h" 68130365Smlaier#endif 69130365Smlaier#endif /* __FreeBSD__ || __NetBSD__ */ 70130365Smlaier#ifdef ALTQ_RED /* red is enabled by ALTQ_RED option in opt_altq.h */ 71130365Smlaier 72130365Smlaier#include <sys/param.h> 73130365Smlaier#include <sys/malloc.h> 74130365Smlaier#include <sys/mbuf.h> 75130365Smlaier#include <sys/socket.h> 76130365Smlaier#include <sys/systm.h> 77130365Smlaier#include <sys/errno.h> 78130365Smlaier#if 1 /* ALTQ3_COMPAT */ 79130365Smlaier#include <sys/sockio.h> 80130365Smlaier#include <sys/proc.h> 81130365Smlaier#include <sys/kernel.h> 82130365Smlaier#ifdef ALTQ_FLOWVALVE 83130365Smlaier#include <sys/queue.h> 84130365Smlaier#include <sys/time.h> 85130365Smlaier#endif 86130365Smlaier#endif /* ALTQ3_COMPAT */ 87130365Smlaier 88130365Smlaier#include <net/if.h> 89130365Smlaier 90130365Smlaier#include <netinet/in.h> 91130365Smlaier#include <netinet/in_systm.h> 92130365Smlaier#include <netinet/ip.h> 93130365Smlaier#ifdef INET6 94130365Smlaier#include <netinet/ip6.h> 95130365Smlaier#endif 96130365Smlaier 97130365Smlaier#include <net/pfvar.h> 98130365Smlaier#include <altq/altq.h> 99130365Smlaier#include <altq/altq_red.h> 100130365Smlaier#ifdef ALTQ3_COMPAT 101130365Smlaier#include <altq/altq_conf.h> 102130365Smlaier#ifdef ALTQ_FLOWVALVE 103130365Smlaier#include <altq/altq_flowvalve.h> 104130365Smlaier#endif 105130365Smlaier#endif 106130365Smlaier 107130365Smlaier/* 108130365Smlaier * ALTQ/RED (Random Early Detection) implementation using 32-bit 109130365Smlaier * fixed-point calculation. 110130365Smlaier * 111130365Smlaier * written by kjc using the ns code as a reference. 112130365Smlaier * you can learn more about red and ns from Sally's home page at 113130365Smlaier * http://www-nrg.ee.lbl.gov/floyd/ 114130365Smlaier * 115130365Smlaier * most of the red parameter values are fixed in this implementation 116130365Smlaier * to prevent fixed-point overflow/underflow. 117130365Smlaier * if you change the parameters, watch out for overflow/underflow! 118130365Smlaier * 119130365Smlaier * the parameters used are recommended values by Sally. 120130365Smlaier * the corresponding ns config looks: 121130365Smlaier * q_weight=0.00195 122130365Smlaier * minthresh=5 maxthresh=15 queue-size=60 123130365Smlaier * linterm=30 124130365Smlaier * dropmech=drop-tail 125130365Smlaier * bytes=false (can't be handled by 32-bit fixed-point) 126130365Smlaier * doubleq=false dqthresh=false 127130365Smlaier * wait=true 128130365Smlaier */ 129130365Smlaier/* 130130365Smlaier * alternative red parameters for a slow link. 131130365Smlaier * 132130365Smlaier * assume the queue length becomes from zero to L and keeps L, it takes 133130365Smlaier * N packets for q_avg to reach 63% of L. 134130365Smlaier * when q_weight is 0.002, N is about 500 packets. 135130365Smlaier * for a slow link like dial-up, 500 packets takes more than 1 minute! 136130365Smlaier * when q_weight is 0.008, N is about 127 packets. 137130365Smlaier * when q_weight is 0.016, N is about 63 packets. 138130365Smlaier * bursts of 50 packets are allowed for 0.002, bursts of 25 packets 139130365Smlaier * are allowed for 0.016. 140130365Smlaier * see Sally's paper for more details. 141130365Smlaier */ 142130365Smlaier/* normal red parameters */ 143130365Smlaier#define W_WEIGHT 512 /* inverse of weight of EWMA (511/512) */ 144130365Smlaier /* q_weight = 0.00195 */ 145130365Smlaier 146130365Smlaier/* red parameters for a slow link */ 147130365Smlaier#define W_WEIGHT_1 128 /* inverse of weight of EWMA (127/128) */ 148130365Smlaier /* q_weight = 0.0078125 */ 149130365Smlaier 150130365Smlaier/* red parameters for a very slow link (e.g., dialup) */ 151130365Smlaier#define W_WEIGHT_2 64 /* inverse of weight of EWMA (63/64) */ 152130365Smlaier /* q_weight = 0.015625 */ 153130365Smlaier 154130365Smlaier/* fixed-point uses 12-bit decimal places */ 155130365Smlaier#define FP_SHIFT 12 /* fixed-point shift */ 156130365Smlaier 157130365Smlaier/* red parameters for drop probability */ 158130365Smlaier#define INV_P_MAX 10 /* inverse of max drop probability */ 159130365Smlaier#define TH_MIN 5 /* min threshold */ 160130365Smlaier#define TH_MAX 15 /* max threshold */ 161130365Smlaier 162130365Smlaier#define RED_LIMIT 60 /* default max queue lenght */ 163130365Smlaier#define RED_STATS /* collect statistics */ 164130365Smlaier 165130365Smlaier/* 166130365Smlaier * our default policy for forced-drop is drop-tail. 167130365Smlaier * (in altq-1.1.2 or earlier, the default was random-drop. 168130365Smlaier * but it makes more sense to punish the cause of the surge.) 169130365Smlaier * to switch to the random-drop policy, define "RED_RANDOM_DROP". 170130365Smlaier */ 171130365Smlaier 172130365Smlaier#ifdef ALTQ3_COMPAT 173130365Smlaier#ifdef ALTQ_FLOWVALVE 174130365Smlaier/* 175130365Smlaier * flow-valve is an extention to protect red from unresponsive flows 176130365Smlaier * and to promote end-to-end congestion control. 177130365Smlaier * flow-valve observes the average drop rates of the flows that have 178130365Smlaier * experienced packet drops in the recent past. 179130365Smlaier * when the average drop rate exceeds the threshold, the flow is 180130365Smlaier * blocked by the flow-valve. the trapped flow should back off 181130365Smlaier * exponentially to escape from the flow-valve. 182130365Smlaier */ 183130365Smlaier#ifdef RED_RANDOM_DROP 184130365Smlaier#error "random-drop can't be used with flow-valve!" 185130365Smlaier#endif 186130365Smlaier#endif /* ALTQ_FLOWVALVE */ 187130365Smlaier 188130365Smlaier/* red_list keeps all red_queue_t's allocated. */ 189130365Smlaierstatic red_queue_t *red_list = NULL; 190130365Smlaier 191130365Smlaier#endif /* ALTQ3_COMPAT */ 192130365Smlaier 193130365Smlaier/* default red parameter values */ 194130365Smlaierstatic int default_th_min = TH_MIN; 195130365Smlaierstatic int default_th_max = TH_MAX; 196130365Smlaierstatic int default_inv_pmax = INV_P_MAX; 197130365Smlaier 198130365Smlaier#ifdef ALTQ3_COMPAT 199130365Smlaier/* internal function prototypes */ 200130365Smlaierstatic int red_enqueue(struct ifaltq *, struct mbuf *, struct altq_pktattr *); 201130365Smlaierstatic struct mbuf *red_dequeue(struct ifaltq *, int); 202130365Smlaierstatic int red_request(struct ifaltq *, int, void *); 203130365Smlaierstatic void red_purgeq(red_queue_t *); 204130365Smlaierstatic int red_detach(red_queue_t *); 205130365Smlaier#ifdef ALTQ_FLOWVALVE 206130365Smlaierstatic __inline struct fve *flowlist_lookup(struct flowvalve *, 207130365Smlaier struct altq_pktattr *, struct timeval *); 208130365Smlaierstatic __inline struct fve *flowlist_reclaim(struct flowvalve *, 209130365Smlaier struct altq_pktattr *); 210130365Smlaierstatic __inline void flowlist_move_to_head(struct flowvalve *, struct fve *); 211130365Smlaierstatic __inline int fv_p2f(struct flowvalve *, int); 212130368Smlaier#if 0 /* XXX: make the compiler happy (fv_alloc unused) */ 213130365Smlaierstatic struct flowvalve *fv_alloc(struct red *); 214130368Smlaier#endif 215130365Smlaierstatic void fv_destroy(struct flowvalve *); 216130365Smlaierstatic int fv_checkflow(struct flowvalve *, struct altq_pktattr *, 217130365Smlaier struct fve **); 218130365Smlaierstatic void fv_dropbyred(struct flowvalve *fv, struct altq_pktattr *, 219130365Smlaier struct fve *); 220130365Smlaier#endif 221130365Smlaier#endif /* ALTQ3_COMPAT */ 222130365Smlaier 223130365Smlaier/* 224130365Smlaier * red support routines 225130365Smlaier */ 226130365Smlaierred_t * 227130365Smlaierred_alloc(int weight, int inv_pmax, int th_min, int th_max, int flags, 228130365Smlaier int pkttime) 229130365Smlaier{ 230130365Smlaier red_t *rp; 231130365Smlaier int w, i; 232130365Smlaier int npkts_per_sec; 233130365Smlaier 234240824Sglebius rp = malloc(sizeof(red_t), M_DEVBUF, M_NOWAIT | M_ZERO); 235130365Smlaier if (rp == NULL) 236130365Smlaier return (NULL); 237130365Smlaier 238240918Sglebius if (weight == 0) 239240918Sglebius rp->red_weight = W_WEIGHT; 240240918Sglebius else 241240918Sglebius rp->red_weight = weight; 242240918Sglebius 243240835Sglebius /* allocate weight table */ 244240835Sglebius rp->red_wtab = wtab_alloc(rp->red_weight); 245240835Sglebius if (rp->red_wtab == NULL) { 246240835Sglebius free(rp, M_DEVBUF); 247240835Sglebius return (NULL); 248240835Sglebius } 249240835Sglebius 250130365Smlaier rp->red_avg = 0; 251130365Smlaier rp->red_idle = 1; 252130365Smlaier 253130365Smlaier if (inv_pmax == 0) 254130365Smlaier rp->red_inv_pmax = default_inv_pmax; 255130365Smlaier else 256130365Smlaier rp->red_inv_pmax = inv_pmax; 257130365Smlaier if (th_min == 0) 258130365Smlaier rp->red_thmin = default_th_min; 259130365Smlaier else 260130365Smlaier rp->red_thmin = th_min; 261130365Smlaier if (th_max == 0) 262130365Smlaier rp->red_thmax = default_th_max; 263130365Smlaier else 264130365Smlaier rp->red_thmax = th_max; 265130365Smlaier 266130365Smlaier rp->red_flags = flags; 267130365Smlaier 268130365Smlaier if (pkttime == 0) 269130365Smlaier /* default packet time: 1000 bytes / 10Mbps * 8 * 1000000 */ 270130365Smlaier rp->red_pkttime = 800; 271130365Smlaier else 272130365Smlaier rp->red_pkttime = pkttime; 273130365Smlaier 274130365Smlaier if (weight == 0) { 275130365Smlaier /* when the link is very slow, adjust red parameters */ 276130365Smlaier npkts_per_sec = 1000000 / rp->red_pkttime; 277130365Smlaier if (npkts_per_sec < 50) { 278130365Smlaier /* up to about 400Kbps */ 279130365Smlaier rp->red_weight = W_WEIGHT_2; 280130365Smlaier } else if (npkts_per_sec < 300) { 281130365Smlaier /* up to about 2.4Mbps */ 282130365Smlaier rp->red_weight = W_WEIGHT_1; 283130365Smlaier } 284130365Smlaier } 285130365Smlaier 286130365Smlaier /* calculate wshift. weight must be power of 2 */ 287130365Smlaier w = rp->red_weight; 288130365Smlaier for (i = 0; w > 1; i++) 289130365Smlaier w = w >> 1; 290130365Smlaier rp->red_wshift = i; 291130365Smlaier w = 1 << rp->red_wshift; 292130365Smlaier if (w != rp->red_weight) { 293130365Smlaier printf("invalid weight value %d for red! use %d\n", 294130365Smlaier rp->red_weight, w); 295130365Smlaier rp->red_weight = w; 296130365Smlaier } 297130365Smlaier 298130365Smlaier /* 299130365Smlaier * thmin_s and thmax_s are scaled versions of th_min and th_max 300130365Smlaier * to be compared with avg. 301130365Smlaier */ 302130365Smlaier rp->red_thmin_s = rp->red_thmin << (rp->red_wshift + FP_SHIFT); 303130365Smlaier rp->red_thmax_s = rp->red_thmax << (rp->red_wshift + FP_SHIFT); 304130365Smlaier 305130365Smlaier /* 306130365Smlaier * precompute probability denominator 307130365Smlaier * probd = (2 * (TH_MAX-TH_MIN) / pmax) in fixed-point 308130365Smlaier */ 309130365Smlaier rp->red_probd = (2 * (rp->red_thmax - rp->red_thmin) 310130365Smlaier * rp->red_inv_pmax) << FP_SHIFT; 311130365Smlaier 312130365Smlaier microtime(&rp->red_last); 313130365Smlaier return (rp); 314130365Smlaier} 315130365Smlaier 316130365Smlaiervoid 317130365Smlaierred_destroy(red_t *rp) 318130365Smlaier{ 319130365Smlaier#ifdef ALTQ3_COMPAT 320130365Smlaier#ifdef ALTQ_FLOWVALVE 321130365Smlaier if (rp->red_flowvalve != NULL) 322130365Smlaier fv_destroy(rp->red_flowvalve); 323130365Smlaier#endif 324130365Smlaier#endif /* ALTQ3_COMPAT */ 325130365Smlaier wtab_destroy(rp->red_wtab); 326184205Sdes free(rp, M_DEVBUF); 327130365Smlaier} 328130365Smlaier 329130365Smlaiervoid 330130365Smlaierred_getstats(red_t *rp, struct redstats *sp) 331130365Smlaier{ 332130365Smlaier sp->q_avg = rp->red_avg >> rp->red_wshift; 333130365Smlaier sp->xmit_cnt = rp->red_stats.xmit_cnt; 334130365Smlaier sp->drop_cnt = rp->red_stats.drop_cnt; 335130365Smlaier sp->drop_forced = rp->red_stats.drop_forced; 336130365Smlaier sp->drop_unforced = rp->red_stats.drop_unforced; 337130365Smlaier sp->marked_packets = rp->red_stats.marked_packets; 338130365Smlaier} 339130365Smlaier 340130365Smlaierint 341130365Smlaierred_addq(red_t *rp, class_queue_t *q, struct mbuf *m, 342130365Smlaier struct altq_pktattr *pktattr) 343130365Smlaier{ 344130365Smlaier int avg, droptype; 345130365Smlaier int n; 346130365Smlaier#ifdef ALTQ3_COMPAT 347130365Smlaier#ifdef ALTQ_FLOWVALVE 348130365Smlaier struct fve *fve = NULL; 349130365Smlaier 350130365Smlaier if (rp->red_flowvalve != NULL && rp->red_flowvalve->fv_flows > 0) 351130365Smlaier if (fv_checkflow(rp->red_flowvalve, pktattr, &fve)) { 352130365Smlaier m_freem(m); 353130365Smlaier return (-1); 354130365Smlaier } 355130365Smlaier#endif 356130365Smlaier#endif /* ALTQ3_COMPAT */ 357130365Smlaier 358130365Smlaier avg = rp->red_avg; 359130365Smlaier 360130365Smlaier /* 361130365Smlaier * if we were idle, we pretend that n packets arrived during 362130365Smlaier * the idle period. 363130365Smlaier */ 364130365Smlaier if (rp->red_idle) { 365130365Smlaier struct timeval now; 366130365Smlaier int t; 367130365Smlaier 368130365Smlaier rp->red_idle = 0; 369130365Smlaier microtime(&now); 370130365Smlaier t = (now.tv_sec - rp->red_last.tv_sec); 371130365Smlaier if (t > 60) { 372130365Smlaier /* 373130365Smlaier * being idle for more than 1 minute, set avg to zero. 374130365Smlaier * this prevents t from overflow. 375130365Smlaier */ 376130365Smlaier avg = 0; 377130365Smlaier } else { 378130365Smlaier t = t * 1000000 + (now.tv_usec - rp->red_last.tv_usec); 379130365Smlaier n = t / rp->red_pkttime - 1; 380130365Smlaier 381130365Smlaier /* the following line does (avg = (1 - Wq)^n * avg) */ 382130365Smlaier if (n > 0) 383130365Smlaier avg = (avg >> FP_SHIFT) * 384130365Smlaier pow_w(rp->red_wtab, n); 385130365Smlaier } 386130365Smlaier } 387130365Smlaier 388130365Smlaier /* run estimator. (note: avg is scaled by WEIGHT in fixed-point) */ 389130365Smlaier avg += (qlen(q) << FP_SHIFT) - (avg >> rp->red_wshift); 390130365Smlaier rp->red_avg = avg; /* save the new value */ 391130365Smlaier 392130365Smlaier /* 393130365Smlaier * red_count keeps a tally of arriving traffic that has not 394130365Smlaier * been dropped. 395130365Smlaier */ 396130365Smlaier rp->red_count++; 397130365Smlaier 398130365Smlaier /* see if we drop early */ 399130365Smlaier droptype = DTYPE_NODROP; 400130365Smlaier if (avg >= rp->red_thmin_s && qlen(q) > 1) { 401130365Smlaier if (avg >= rp->red_thmax_s) { 402130365Smlaier /* avg >= th_max: forced drop */ 403130365Smlaier droptype = DTYPE_FORCED; 404130365Smlaier } else if (rp->red_old == 0) { 405130365Smlaier /* first exceeds th_min */ 406130365Smlaier rp->red_count = 1; 407130365Smlaier rp->red_old = 1; 408130365Smlaier } else if (drop_early((avg - rp->red_thmin_s) >> rp->red_wshift, 409130365Smlaier rp->red_probd, rp->red_count)) { 410130365Smlaier /* mark or drop by red */ 411130365Smlaier if ((rp->red_flags & REDF_ECN) && 412130365Smlaier mark_ecn(m, pktattr, rp->red_flags)) { 413130365Smlaier /* successfully marked. do not drop. */ 414130365Smlaier rp->red_count = 0; 415130365Smlaier#ifdef RED_STATS 416130365Smlaier rp->red_stats.marked_packets++; 417130365Smlaier#endif 418130365Smlaier } else { 419130365Smlaier /* unforced drop by red */ 420130365Smlaier droptype = DTYPE_EARLY; 421130365Smlaier } 422130365Smlaier } 423130365Smlaier } else { 424130365Smlaier /* avg < th_min */ 425130365Smlaier rp->red_old = 0; 426130365Smlaier } 427130365Smlaier 428130365Smlaier /* 429130365Smlaier * if the queue length hits the hard limit, it's a forced drop. 430130365Smlaier */ 431130365Smlaier if (droptype == DTYPE_NODROP && qlen(q) >= qlimit(q)) 432130365Smlaier droptype = DTYPE_FORCED; 433130365Smlaier 434130365Smlaier#ifdef RED_RANDOM_DROP 435130365Smlaier /* if successful or forced drop, enqueue this packet. */ 436130365Smlaier if (droptype != DTYPE_EARLY) 437130365Smlaier _addq(q, m); 438130365Smlaier#else 439130365Smlaier /* if successful, enqueue this packet. */ 440130365Smlaier if (droptype == DTYPE_NODROP) 441130365Smlaier _addq(q, m); 442130365Smlaier#endif 443130365Smlaier if (droptype != DTYPE_NODROP) { 444130365Smlaier if (droptype == DTYPE_EARLY) { 445130365Smlaier /* drop the incoming packet */ 446130365Smlaier#ifdef RED_STATS 447130365Smlaier rp->red_stats.drop_unforced++; 448130365Smlaier#endif 449130365Smlaier } else { 450130365Smlaier /* forced drop, select a victim packet in the queue. */ 451130365Smlaier#ifdef RED_RANDOM_DROP 452130365Smlaier m = _getq_random(q); 453130365Smlaier#endif 454130365Smlaier#ifdef RED_STATS 455130365Smlaier rp->red_stats.drop_forced++; 456130365Smlaier#endif 457130365Smlaier } 458130365Smlaier#ifdef RED_STATS 459130365Smlaier PKTCNTR_ADD(&rp->red_stats.drop_cnt, m_pktlen(m)); 460130365Smlaier#endif 461130365Smlaier rp->red_count = 0; 462130365Smlaier#ifdef ALTQ3_COMPAT 463130365Smlaier#ifdef ALTQ_FLOWVALVE 464130365Smlaier if (rp->red_flowvalve != NULL) 465130365Smlaier fv_dropbyred(rp->red_flowvalve, pktattr, fve); 466130365Smlaier#endif 467130365Smlaier#endif /* ALTQ3_COMPAT */ 468130365Smlaier m_freem(m); 469130365Smlaier return (-1); 470130365Smlaier } 471130365Smlaier /* successfully queued */ 472130365Smlaier#ifdef RED_STATS 473130365Smlaier PKTCNTR_ADD(&rp->red_stats.xmit_cnt, m_pktlen(m)); 474130365Smlaier#endif 475130365Smlaier return (0); 476130365Smlaier} 477130365Smlaier 478130365Smlaier/* 479130365Smlaier * early-drop probability is calculated as follows: 480130365Smlaier * prob = p_max * (avg - th_min) / (th_max - th_min) 481130365Smlaier * prob_a = prob / (2 - count*prob) 482130365Smlaier * = (avg-th_min) / (2*(th_max-th_min)*inv_p_max - count*(avg-th_min)) 483130365Smlaier * here prob_a increases as successive undrop count increases. 484130365Smlaier * (prob_a starts from prob/2, becomes prob when (count == (1 / prob)), 485130365Smlaier * becomes 1 when (count >= (2 / prob))). 486130365Smlaier */ 487130365Smlaierint 488130365Smlaierdrop_early(int fp_len, int fp_probd, int count) 489130365Smlaier{ 490130365Smlaier int d; /* denominator of drop-probability */ 491130365Smlaier 492130365Smlaier d = fp_probd - count * fp_len; 493130365Smlaier if (d <= 0) 494130365Smlaier /* count exceeds the hard limit: drop or mark */ 495130365Smlaier return (1); 496130365Smlaier 497130365Smlaier /* 498130365Smlaier * now the range of d is [1..600] in fixed-point. (when 499130365Smlaier * th_max-th_min=10 and p_max=1/30) 500130365Smlaier * drop probability = (avg - TH_MIN) / d 501130365Smlaier */ 502130365Smlaier 503130365Smlaier if ((arc4random() % d) < fp_len) { 504130365Smlaier /* drop or mark */ 505130365Smlaier return (1); 506130365Smlaier } 507130365Smlaier /* no drop/mark */ 508130365Smlaier return (0); 509130365Smlaier} 510130365Smlaier 511130365Smlaier/* 512130365Smlaier * try to mark CE bit to the packet. 513130365Smlaier * returns 1 if successfully marked, 0 otherwise. 514130365Smlaier */ 515130365Smlaierint 516130365Smlaiermark_ecn(struct mbuf *m, struct altq_pktattr *pktattr, int flags) 517130365Smlaier{ 518130365Smlaier struct mbuf *m0; 519171173Smlaier struct pf_mtag *at; 520130365Smlaier void *hdr; 521130365Smlaier 522171173Smlaier at = pf_find_mtag(m); 523171173Smlaier if (at != NULL) { 524130365Smlaier hdr = at->hdr; 525130365Smlaier#ifdef ALTQ3_COMPAT 526130365Smlaier } else if (pktattr != NULL) { 527130365Smlaier af = pktattr->pattr_af; 528130365Smlaier hdr = pktattr->pattr_hdr; 529130365Smlaier#endif /* ALTQ3_COMPAT */ 530130365Smlaier } else 531130365Smlaier return (0); 532130365Smlaier 533130365Smlaier /* verify that pattr_hdr is within the mbuf data */ 534130365Smlaier for (m0 = m; m0 != NULL; m0 = m0->m_next) 535130365Smlaier if (((caddr_t)hdr >= m0->m_data) && 536130365Smlaier ((caddr_t)hdr < m0->m_data + m0->m_len)) 537130365Smlaier break; 538130365Smlaier if (m0 == NULL) { 539130365Smlaier /* ick, tag info is stale */ 540130365Smlaier return (0); 541130365Smlaier } 542130365Smlaier 543223637Sbz switch (((struct ip *)hdr)->ip_v) { 544223637Sbz case IPVERSION: 545130365Smlaier if (flags & REDF_ECN4) { 546130365Smlaier struct ip *ip = hdr; 547130365Smlaier u_int8_t otos; 548130365Smlaier int sum; 549130365Smlaier 550130365Smlaier if (ip->ip_v != 4) 551130365Smlaier return (0); /* version mismatch! */ 552130365Smlaier 553130365Smlaier if ((ip->ip_tos & IPTOS_ECN_MASK) == IPTOS_ECN_NOTECT) 554130365Smlaier return (0); /* not-ECT */ 555130365Smlaier if ((ip->ip_tos & IPTOS_ECN_MASK) == IPTOS_ECN_CE) 556130365Smlaier return (1); /* already marked */ 557130365Smlaier 558130365Smlaier /* 559130365Smlaier * ecn-capable but not marked, 560130365Smlaier * mark CE and update checksum 561130365Smlaier */ 562130365Smlaier otos = ip->ip_tos; 563130365Smlaier ip->ip_tos |= IPTOS_ECN_CE; 564130365Smlaier /* 565130365Smlaier * update checksum (from RFC1624) 566130365Smlaier * HC' = ~(~HC + ~m + m') 567130365Smlaier */ 568130365Smlaier sum = ~ntohs(ip->ip_sum) & 0xffff; 569130365Smlaier sum += (~otos & 0xffff) + ip->ip_tos; 570130365Smlaier sum = (sum >> 16) + (sum & 0xffff); 571130365Smlaier sum += (sum >> 16); /* add carry */ 572130365Smlaier ip->ip_sum = htons(~sum & 0xffff); 573130365Smlaier return (1); 574130365Smlaier } 575130365Smlaier break; 576130365Smlaier#ifdef INET6 577223637Sbz case (IPV6_VERSION >> 4): 578130365Smlaier if (flags & REDF_ECN6) { 579130365Smlaier struct ip6_hdr *ip6 = hdr; 580130365Smlaier u_int32_t flowlabel; 581130365Smlaier 582130365Smlaier flowlabel = ntohl(ip6->ip6_flow); 583130365Smlaier if ((flowlabel >> 28) != 6) 584130365Smlaier return (0); /* version mismatch! */ 585130365Smlaier if ((flowlabel & (IPTOS_ECN_MASK << 20)) == 586130365Smlaier (IPTOS_ECN_NOTECT << 20)) 587130365Smlaier return (0); /* not-ECT */ 588130365Smlaier if ((flowlabel & (IPTOS_ECN_MASK << 20)) == 589130365Smlaier (IPTOS_ECN_CE << 20)) 590130365Smlaier return (1); /* already marked */ 591130365Smlaier /* 592130365Smlaier * ecn-capable but not marked, mark CE 593130365Smlaier */ 594130365Smlaier flowlabel |= (IPTOS_ECN_CE << 20); 595130365Smlaier ip6->ip6_flow = htonl(flowlabel); 596130365Smlaier return (1); 597130365Smlaier } 598130365Smlaier break; 599130365Smlaier#endif /* INET6 */ 600130365Smlaier } 601130365Smlaier 602130365Smlaier /* not marked */ 603130365Smlaier return (0); 604130365Smlaier} 605130365Smlaier 606130365Smlaierstruct mbuf * 607130365Smlaierred_getq(rp, q) 608130365Smlaier red_t *rp; 609130365Smlaier class_queue_t *q; 610130365Smlaier{ 611130365Smlaier struct mbuf *m; 612130365Smlaier 613130365Smlaier if ((m = _getq(q)) == NULL) { 614130365Smlaier if (rp->red_idle == 0) { 615130365Smlaier rp->red_idle = 1; 616130365Smlaier microtime(&rp->red_last); 617130365Smlaier } 618130365Smlaier return NULL; 619130365Smlaier } 620130365Smlaier 621130365Smlaier rp->red_idle = 0; 622130365Smlaier return (m); 623130365Smlaier} 624130365Smlaier 625130365Smlaier/* 626130365Smlaier * helper routine to calibrate avg during idle. 627130365Smlaier * pow_w(wtab, n) returns (1 - Wq)^n in fixed-point 628130365Smlaier * here Wq = 1/weight and the code assumes Wq is close to zero. 629130365Smlaier * 630130365Smlaier * w_tab[n] holds ((1 - Wq)^(2^n)) in fixed-point. 631130365Smlaier */ 632130365Smlaierstatic struct wtab *wtab_list = NULL; /* pointer to wtab list */ 633130365Smlaier 634130365Smlaierstruct wtab * 635130365Smlaierwtab_alloc(int weight) 636130365Smlaier{ 637130365Smlaier struct wtab *w; 638130365Smlaier int i; 639130365Smlaier 640130365Smlaier for (w = wtab_list; w != NULL; w = w->w_next) 641130365Smlaier if (w->w_weight == weight) { 642130365Smlaier w->w_refcount++; 643130365Smlaier return (w); 644130365Smlaier } 645130365Smlaier 646240835Sglebius w = malloc(sizeof(struct wtab), M_DEVBUF, M_NOWAIT | M_ZERO); 647130365Smlaier if (w == NULL) 648240835Sglebius return (NULL); 649130365Smlaier w->w_weight = weight; 650130365Smlaier w->w_refcount = 1; 651130365Smlaier w->w_next = wtab_list; 652130365Smlaier wtab_list = w; 653130365Smlaier 654130365Smlaier /* initialize the weight table */ 655130365Smlaier w->w_tab[0] = ((weight - 1) << FP_SHIFT) / weight; 656130365Smlaier for (i = 1; i < 32; i++) { 657130365Smlaier w->w_tab[i] = (w->w_tab[i-1] * w->w_tab[i-1]) >> FP_SHIFT; 658130365Smlaier if (w->w_tab[i] == 0 && w->w_param_max == 0) 659130365Smlaier w->w_param_max = 1 << i; 660130365Smlaier } 661130365Smlaier 662130365Smlaier return (w); 663130365Smlaier} 664130365Smlaier 665130365Smlaierint 666130365Smlaierwtab_destroy(struct wtab *w) 667130365Smlaier{ 668130365Smlaier struct wtab *prev; 669130365Smlaier 670130365Smlaier if (--w->w_refcount > 0) 671130365Smlaier return (0); 672130365Smlaier 673130365Smlaier if (wtab_list == w) 674130365Smlaier wtab_list = w->w_next; 675130365Smlaier else for (prev = wtab_list; prev->w_next != NULL; prev = prev->w_next) 676130365Smlaier if (prev->w_next == w) { 677130365Smlaier prev->w_next = w->w_next; 678130365Smlaier break; 679130365Smlaier } 680130365Smlaier 681184205Sdes free(w, M_DEVBUF); 682130365Smlaier return (0); 683130365Smlaier} 684130365Smlaier 685130365Smlaierint32_t 686130365Smlaierpow_w(struct wtab *w, int n) 687130365Smlaier{ 688130365Smlaier int i, bit; 689130365Smlaier int32_t val; 690130365Smlaier 691130365Smlaier if (n >= w->w_param_max) 692130365Smlaier return (0); 693130365Smlaier 694130365Smlaier val = 1 << FP_SHIFT; 695130365Smlaier if (n <= 0) 696130365Smlaier return (val); 697130365Smlaier 698130365Smlaier bit = 1; 699130365Smlaier i = 0; 700130365Smlaier while (n) { 701130365Smlaier if (n & bit) { 702130365Smlaier val = (val * w->w_tab[i]) >> FP_SHIFT; 703130365Smlaier n &= ~bit; 704130365Smlaier } 705130365Smlaier i++; 706130365Smlaier bit <<= 1; 707130365Smlaier } 708130365Smlaier return (val); 709130365Smlaier} 710130365Smlaier 711130365Smlaier#ifdef ALTQ3_COMPAT 712130365Smlaier/* 713130365Smlaier * red device interface 714130365Smlaier */ 715130365Smlaieraltqdev_decl(red); 716130365Smlaier 717130365Smlaierint 718130365Smlaierredopen(dev, flag, fmt, p) 719130365Smlaier dev_t dev; 720130365Smlaier int flag, fmt; 721130365Smlaier#if (__FreeBSD_version > 500000) 722130365Smlaier struct thread *p; 723130365Smlaier#else 724130365Smlaier struct proc *p; 725130365Smlaier#endif 726130365Smlaier{ 727130365Smlaier /* everything will be done when the queueing scheme is attached. */ 728130365Smlaier return 0; 729130365Smlaier} 730130365Smlaier 731130365Smlaierint 732130365Smlaierredclose(dev, flag, fmt, p) 733130365Smlaier dev_t dev; 734130365Smlaier int flag, fmt; 735130365Smlaier#if (__FreeBSD_version > 500000) 736130365Smlaier struct thread *p; 737130365Smlaier#else 738130365Smlaier struct proc *p; 739130365Smlaier#endif 740130365Smlaier{ 741130365Smlaier red_queue_t *rqp; 742130365Smlaier int err, error = 0; 743130365Smlaier 744130365Smlaier while ((rqp = red_list) != NULL) { 745130365Smlaier /* destroy all */ 746130365Smlaier err = red_detach(rqp); 747130365Smlaier if (err != 0 && error == 0) 748130365Smlaier error = err; 749130365Smlaier } 750130365Smlaier 751130365Smlaier return error; 752130365Smlaier} 753130365Smlaier 754130365Smlaierint 755130365Smlaierredioctl(dev, cmd, addr, flag, p) 756130365Smlaier dev_t dev; 757130365Smlaier ioctlcmd_t cmd; 758130365Smlaier caddr_t addr; 759130365Smlaier int flag; 760130365Smlaier#if (__FreeBSD_version > 500000) 761130365Smlaier struct thread *p; 762130365Smlaier#else 763130365Smlaier struct proc *p; 764130365Smlaier#endif 765130365Smlaier{ 766130365Smlaier red_queue_t *rqp; 767130365Smlaier struct red_interface *ifacep; 768130365Smlaier struct ifnet *ifp; 769130365Smlaier int error = 0; 770130365Smlaier 771130365Smlaier /* check super-user privilege */ 772130365Smlaier switch (cmd) { 773130365Smlaier case RED_GETSTATS: 774130365Smlaier break; 775130365Smlaier default: 776164033Srwatson#if (__FreeBSD_version > 700000) 777164033Srwatson if ((error = priv_check(p, PRIV_ALTQ_MANAGE)) != 0) 778164033Srwatson#elsif (__FreeBSD_version > 400000) 779130365Smlaier if ((error = suser(p)) != 0) 780130365Smlaier#else 781130365Smlaier if ((error = suser(p->p_ucred, &p->p_acflag)) != 0) 782130365Smlaier#endif 783130365Smlaier return (error); 784130365Smlaier break; 785130365Smlaier } 786130365Smlaier 787130365Smlaier switch (cmd) { 788130365Smlaier 789130365Smlaier case RED_ENABLE: 790130365Smlaier ifacep = (struct red_interface *)addr; 791130365Smlaier if ((rqp = altq_lookup(ifacep->red_ifname, ALTQT_RED)) == NULL) { 792130365Smlaier error = EBADF; 793130365Smlaier break; 794130365Smlaier } 795130365Smlaier error = altq_enable(rqp->rq_ifq); 796130365Smlaier break; 797130365Smlaier 798130365Smlaier case RED_DISABLE: 799130365Smlaier ifacep = (struct red_interface *)addr; 800130365Smlaier if ((rqp = altq_lookup(ifacep->red_ifname, ALTQT_RED)) == NULL) { 801130365Smlaier error = EBADF; 802130365Smlaier break; 803130365Smlaier } 804130365Smlaier error = altq_disable(rqp->rq_ifq); 805130365Smlaier break; 806130365Smlaier 807130365Smlaier case RED_IF_ATTACH: 808130365Smlaier ifp = ifunit(((struct red_interface *)addr)->red_ifname); 809130365Smlaier if (ifp == NULL) { 810130365Smlaier error = ENXIO; 811130365Smlaier break; 812130365Smlaier } 813130365Smlaier 814130365Smlaier /* allocate and initialize red_queue_t */ 815184205Sdes rqp = malloc(sizeof(red_queue_t), M_DEVBUF, M_WAITOK); 816130365Smlaier if (rqp == NULL) { 817130365Smlaier error = ENOMEM; 818130365Smlaier break; 819130365Smlaier } 820130365Smlaier bzero(rqp, sizeof(red_queue_t)); 821130365Smlaier 822184205Sdes rqp->rq_q = malloc(sizeof(class_queue_t), 823130365Smlaier M_DEVBUF, M_WAITOK); 824130365Smlaier if (rqp->rq_q == NULL) { 825184205Sdes free(rqp, M_DEVBUF); 826130365Smlaier error = ENOMEM; 827130365Smlaier break; 828130365Smlaier } 829130365Smlaier bzero(rqp->rq_q, sizeof(class_queue_t)); 830130365Smlaier 831130365Smlaier rqp->rq_red = red_alloc(0, 0, 0, 0, 0, 0); 832130365Smlaier if (rqp->rq_red == NULL) { 833184205Sdes free(rqp->rq_q, M_DEVBUF); 834184205Sdes free(rqp, M_DEVBUF); 835130365Smlaier error = ENOMEM; 836130365Smlaier break; 837130365Smlaier } 838130365Smlaier 839130365Smlaier rqp->rq_ifq = &ifp->if_snd; 840130365Smlaier qtail(rqp->rq_q) = NULL; 841130365Smlaier qlen(rqp->rq_q) = 0; 842130365Smlaier qlimit(rqp->rq_q) = RED_LIMIT; 843130365Smlaier qtype(rqp->rq_q) = Q_RED; 844130365Smlaier 845130365Smlaier /* 846130365Smlaier * set RED to this ifnet structure. 847130365Smlaier */ 848130365Smlaier error = altq_attach(rqp->rq_ifq, ALTQT_RED, rqp, 849130365Smlaier red_enqueue, red_dequeue, red_request, 850130365Smlaier NULL, NULL); 851130365Smlaier if (error) { 852130365Smlaier red_destroy(rqp->rq_red); 853184205Sdes free(rqp->rq_q, M_DEVBUF); 854184205Sdes free(rqp, M_DEVBUF); 855130365Smlaier break; 856130365Smlaier } 857130365Smlaier 858130365Smlaier /* add this state to the red list */ 859130365Smlaier rqp->rq_next = red_list; 860130365Smlaier red_list = rqp; 861130365Smlaier break; 862130365Smlaier 863130365Smlaier case RED_IF_DETACH: 864130365Smlaier ifacep = (struct red_interface *)addr; 865130365Smlaier if ((rqp = altq_lookup(ifacep->red_ifname, ALTQT_RED)) == NULL) { 866130365Smlaier error = EBADF; 867130365Smlaier break; 868130365Smlaier } 869130365Smlaier error = red_detach(rqp); 870130365Smlaier break; 871130365Smlaier 872130365Smlaier case RED_GETSTATS: 873130365Smlaier do { 874130365Smlaier struct red_stats *q_stats; 875130365Smlaier red_t *rp; 876130365Smlaier 877130365Smlaier q_stats = (struct red_stats *)addr; 878130365Smlaier if ((rqp = altq_lookup(q_stats->iface.red_ifname, 879130365Smlaier ALTQT_RED)) == NULL) { 880130365Smlaier error = EBADF; 881130365Smlaier break; 882130365Smlaier } 883130365Smlaier 884130365Smlaier q_stats->q_len = qlen(rqp->rq_q); 885130365Smlaier q_stats->q_limit = qlimit(rqp->rq_q); 886130365Smlaier 887130365Smlaier rp = rqp->rq_red; 888130365Smlaier q_stats->q_avg = rp->red_avg >> rp->red_wshift; 889130365Smlaier q_stats->xmit_cnt = rp->red_stats.xmit_cnt; 890130365Smlaier q_stats->drop_cnt = rp->red_stats.drop_cnt; 891130365Smlaier q_stats->drop_forced = rp->red_stats.drop_forced; 892130365Smlaier q_stats->drop_unforced = rp->red_stats.drop_unforced; 893130365Smlaier q_stats->marked_packets = rp->red_stats.marked_packets; 894130365Smlaier 895130365Smlaier q_stats->weight = rp->red_weight; 896130365Smlaier q_stats->inv_pmax = rp->red_inv_pmax; 897130365Smlaier q_stats->th_min = rp->red_thmin; 898130365Smlaier q_stats->th_max = rp->red_thmax; 899130365Smlaier 900130365Smlaier#ifdef ALTQ_FLOWVALVE 901130365Smlaier if (rp->red_flowvalve != NULL) { 902130365Smlaier struct flowvalve *fv = rp->red_flowvalve; 903130365Smlaier q_stats->fv_flows = fv->fv_flows; 904130365Smlaier q_stats->fv_pass = fv->fv_stats.pass; 905130365Smlaier q_stats->fv_predrop = fv->fv_stats.predrop; 906130365Smlaier q_stats->fv_alloc = fv->fv_stats.alloc; 907130365Smlaier q_stats->fv_escape = fv->fv_stats.escape; 908130365Smlaier } else { 909130365Smlaier#endif /* ALTQ_FLOWVALVE */ 910130365Smlaier q_stats->fv_flows = 0; 911130365Smlaier q_stats->fv_pass = 0; 912130365Smlaier q_stats->fv_predrop = 0; 913130365Smlaier q_stats->fv_alloc = 0; 914130365Smlaier q_stats->fv_escape = 0; 915130365Smlaier#ifdef ALTQ_FLOWVALVE 916130365Smlaier } 917130365Smlaier#endif /* ALTQ_FLOWVALVE */ 918130365Smlaier } while (/*CONSTCOND*/ 0); 919130365Smlaier break; 920130365Smlaier 921130365Smlaier case RED_CONFIG: 922130365Smlaier do { 923130365Smlaier struct red_conf *fc; 924130365Smlaier red_t *new; 925130365Smlaier int s, limit; 926130365Smlaier 927130365Smlaier fc = (struct red_conf *)addr; 928130365Smlaier if ((rqp = altq_lookup(fc->iface.red_ifname, 929130365Smlaier ALTQT_RED)) == NULL) { 930130365Smlaier error = EBADF; 931130365Smlaier break; 932130365Smlaier } 933130365Smlaier new = red_alloc(fc->red_weight, 934130365Smlaier fc->red_inv_pmax, 935130365Smlaier fc->red_thmin, 936130365Smlaier fc->red_thmax, 937130365Smlaier fc->red_flags, 938130365Smlaier fc->red_pkttime); 939130365Smlaier if (new == NULL) { 940130365Smlaier error = ENOMEM; 941130365Smlaier break; 942130365Smlaier } 943130365Smlaier 944130365Smlaier#ifdef __NetBSD__ 945130365Smlaier s = splnet(); 946130365Smlaier#else 947130365Smlaier s = splimp(); 948130365Smlaier#endif 949130365Smlaier red_purgeq(rqp); 950130365Smlaier limit = fc->red_limit; 951130365Smlaier if (limit < fc->red_thmax) 952130365Smlaier limit = fc->red_thmax; 953130365Smlaier qlimit(rqp->rq_q) = limit; 954130365Smlaier fc->red_limit = limit; /* write back the new value */ 955130365Smlaier 956130365Smlaier red_destroy(rqp->rq_red); 957130365Smlaier rqp->rq_red = new; 958130365Smlaier 959130365Smlaier splx(s); 960130365Smlaier 961130365Smlaier /* write back new values */ 962130365Smlaier fc->red_limit = limit; 963130365Smlaier fc->red_inv_pmax = rqp->rq_red->red_inv_pmax; 964130365Smlaier fc->red_thmin = rqp->rq_red->red_thmin; 965130365Smlaier fc->red_thmax = rqp->rq_red->red_thmax; 966130365Smlaier 967130365Smlaier } while (/*CONSTCOND*/ 0); 968130365Smlaier break; 969130365Smlaier 970130365Smlaier case RED_SETDEFAULTS: 971130365Smlaier do { 972130365Smlaier struct redparams *rp; 973130365Smlaier 974130365Smlaier rp = (struct redparams *)addr; 975130365Smlaier 976130365Smlaier default_th_min = rp->th_min; 977130365Smlaier default_th_max = rp->th_max; 978130365Smlaier default_inv_pmax = rp->inv_pmax; 979130365Smlaier } while (/*CONSTCOND*/ 0); 980130365Smlaier break; 981130365Smlaier 982130365Smlaier default: 983130365Smlaier error = EINVAL; 984130365Smlaier break; 985130365Smlaier } 986130365Smlaier return error; 987130365Smlaier} 988130365Smlaier 989130365Smlaierstatic int 990130365Smlaierred_detach(rqp) 991130365Smlaier red_queue_t *rqp; 992130365Smlaier{ 993130365Smlaier red_queue_t *tmp; 994130365Smlaier int error = 0; 995130365Smlaier 996130365Smlaier if (ALTQ_IS_ENABLED(rqp->rq_ifq)) 997130365Smlaier altq_disable(rqp->rq_ifq); 998130365Smlaier 999130365Smlaier if ((error = altq_detach(rqp->rq_ifq))) 1000130365Smlaier return (error); 1001130365Smlaier 1002130365Smlaier if (red_list == rqp) 1003130365Smlaier red_list = rqp->rq_next; 1004130365Smlaier else { 1005130365Smlaier for (tmp = red_list; tmp != NULL; tmp = tmp->rq_next) 1006130365Smlaier if (tmp->rq_next == rqp) { 1007130365Smlaier tmp->rq_next = rqp->rq_next; 1008130365Smlaier break; 1009130365Smlaier } 1010130365Smlaier if (tmp == NULL) 1011130365Smlaier printf("red_detach: no state found in red_list!\n"); 1012130365Smlaier } 1013130365Smlaier 1014130365Smlaier red_destroy(rqp->rq_red); 1015184205Sdes free(rqp->rq_q, M_DEVBUF); 1016184205Sdes free(rqp, M_DEVBUF); 1017130365Smlaier return (error); 1018130365Smlaier} 1019130365Smlaier 1020130365Smlaier/* 1021130365Smlaier * enqueue routine: 1022130365Smlaier * 1023130365Smlaier * returns: 0 when successfully queued. 1024130365Smlaier * ENOBUFS when drop occurs. 1025130365Smlaier */ 1026130365Smlaierstatic int 1027130365Smlaierred_enqueue(ifq, m, pktattr) 1028130365Smlaier struct ifaltq *ifq; 1029130365Smlaier struct mbuf *m; 1030130365Smlaier struct altq_pktattr *pktattr; 1031130365Smlaier{ 1032130365Smlaier red_queue_t *rqp = (red_queue_t *)ifq->altq_disc; 1033130365Smlaier 1034130368Smlaier IFQ_LOCK_ASSERT(ifq); 1035130368Smlaier 1036130365Smlaier if (red_addq(rqp->rq_red, rqp->rq_q, m, pktattr) < 0) 1037130365Smlaier return ENOBUFS; 1038130365Smlaier ifq->ifq_len++; 1039130365Smlaier return 0; 1040130365Smlaier} 1041130365Smlaier 1042130365Smlaier/* 1043130365Smlaier * dequeue routine: 1044130365Smlaier * must be called in splimp. 1045130365Smlaier * 1046130365Smlaier * returns: mbuf dequeued. 1047130365Smlaier * NULL when no packet is available in the queue. 1048130365Smlaier */ 1049130365Smlaier 1050130365Smlaierstatic struct mbuf * 1051130365Smlaierred_dequeue(ifq, op) 1052130365Smlaier struct ifaltq *ifq; 1053130365Smlaier int op; 1054130365Smlaier{ 1055130365Smlaier red_queue_t *rqp = (red_queue_t *)ifq->altq_disc; 1056130365Smlaier struct mbuf *m; 1057130365Smlaier 1058130368Smlaier IFQ_LOCK_ASSERT(ifq); 1059130368Smlaier 1060130365Smlaier if (op == ALTDQ_POLL) 1061130365Smlaier return qhead(rqp->rq_q); 1062130365Smlaier 1063130365Smlaier /* op == ALTDQ_REMOVE */ 1064130365Smlaier m = red_getq(rqp->rq_red, rqp->rq_q); 1065130365Smlaier if (m != NULL) 1066130365Smlaier ifq->ifq_len--; 1067130365Smlaier return (m); 1068130365Smlaier} 1069130365Smlaier 1070130365Smlaierstatic int 1071130365Smlaierred_request(ifq, req, arg) 1072130365Smlaier struct ifaltq *ifq; 1073130365Smlaier int req; 1074130365Smlaier void *arg; 1075130365Smlaier{ 1076130365Smlaier red_queue_t *rqp = (red_queue_t *)ifq->altq_disc; 1077130365Smlaier 1078130368Smlaier IFQ_LOCK_ASSERT(ifq); 1079130368Smlaier 1080130365Smlaier switch (req) { 1081130365Smlaier case ALTRQ_PURGE: 1082130365Smlaier red_purgeq(rqp); 1083130365Smlaier break; 1084130365Smlaier } 1085130365Smlaier return (0); 1086130365Smlaier} 1087130365Smlaier 1088130365Smlaierstatic void 1089130365Smlaierred_purgeq(rqp) 1090130365Smlaier red_queue_t *rqp; 1091130365Smlaier{ 1092130365Smlaier _flushq(rqp->rq_q); 1093130365Smlaier if (ALTQ_IS_ENABLED(rqp->rq_ifq)) 1094130365Smlaier rqp->rq_ifq->ifq_len = 0; 1095130365Smlaier} 1096130365Smlaier 1097130365Smlaier#ifdef ALTQ_FLOWVALVE 1098130365Smlaier 1099130365Smlaier#define FV_PSHIFT 7 /* weight of average drop rate -- 1/128 */ 1100130365Smlaier#define FV_PSCALE(x) ((x) << FV_PSHIFT) 1101130365Smlaier#define FV_PUNSCALE(x) ((x) >> FV_PSHIFT) 1102130365Smlaier#define FV_FSHIFT 5 /* weight of average fraction -- 1/32 */ 1103130365Smlaier#define FV_FSCALE(x) ((x) << FV_FSHIFT) 1104130365Smlaier#define FV_FUNSCALE(x) ((x) >> FV_FSHIFT) 1105130365Smlaier 1106130365Smlaier#define FV_TIMER (3 * hz) /* timer value for garbage collector */ 1107130365Smlaier#define FV_FLOWLISTSIZE 64 /* how many flows in flowlist */ 1108130365Smlaier 1109130365Smlaier#define FV_N 10 /* update fve_f every FV_N packets */ 1110130365Smlaier 1111130365Smlaier#define FV_BACKOFFTHRESH 1 /* backoff threshold interval in second */ 1112130365Smlaier#define FV_TTHRESH 3 /* time threshold to delete fve */ 1113130365Smlaier#define FV_ALPHA 5 /* extra packet count */ 1114130365Smlaier 1115130365Smlaier#define FV_STATS 1116130365Smlaier 1117130365Smlaier#if (__FreeBSD_version > 300000) 1118130365Smlaier#define FV_TIMESTAMP(tp) getmicrotime(tp) 1119130365Smlaier#else 1120130365Smlaier#define FV_TIMESTAMP(tp) { (*(tp)) = time; } 1121130365Smlaier#endif 1122130365Smlaier 1123130365Smlaier/* 1124130365Smlaier * Brtt table: 127 entry table to convert drop rate (p) to 1125130365Smlaier * the corresponding bandwidth fraction (f) 1126130365Smlaier * the following equation is implemented to use scaled values, 1127130365Smlaier * fve_p and fve_f, in the fixed point format. 1128130365Smlaier * 1129130365Smlaier * Brtt(p) = 1 /(sqrt(4*p/3) + min(1,3*sqrt(p*6/8)) * p * (1+32 * p*p)) 1130130365Smlaier * f = Brtt(p) / (max_th + alpha) 1131130365Smlaier */ 1132130365Smlaier#define BRTT_SIZE 128 1133130365Smlaier#define BRTT_SHIFT 12 1134130365Smlaier#define BRTT_MASK 0x0007f000 1135130365Smlaier#define BRTT_PMAX (1 << (FV_PSHIFT + FP_SHIFT)) 1136130365Smlaier 1137130365Smlaierconst int brtt_tab[BRTT_SIZE] = { 1138130365Smlaier 0, 1262010, 877019, 703694, 598706, 525854, 471107, 427728, 1139130365Smlaier 392026, 361788, 335598, 312506, 291850, 273158, 256081, 240361, 1140130365Smlaier 225800, 212247, 199585, 187788, 178388, 169544, 161207, 153333, 1141130365Smlaier 145888, 138841, 132165, 125836, 119834, 114141, 108739, 103612, 1142130365Smlaier 98747, 94129, 89746, 85585, 81637, 77889, 74333, 70957, 1143130365Smlaier 67752, 64711, 61824, 59084, 56482, 54013, 51667, 49440, 1144130365Smlaier 47325, 45315, 43406, 41591, 39866, 38227, 36667, 35184, 1145130365Smlaier 33773, 32430, 31151, 29933, 28774, 27668, 26615, 25611, 1146130365Smlaier 24653, 23740, 22868, 22035, 21240, 20481, 19755, 19062, 1147130365Smlaier 18399, 17764, 17157, 16576, 16020, 15487, 14976, 14487, 1148130365Smlaier 14017, 13567, 13136, 12721, 12323, 11941, 11574, 11222, 1149130365Smlaier 10883, 10557, 10243, 9942, 9652, 9372, 9103, 8844, 1150130365Smlaier 8594, 8354, 8122, 7898, 7682, 7474, 7273, 7079, 1151130365Smlaier 6892, 6711, 6536, 6367, 6204, 6046, 5893, 5746, 1152130365Smlaier 5603, 5464, 5330, 5201, 5075, 4954, 4836, 4722, 1153130365Smlaier 4611, 4504, 4400, 4299, 4201, 4106, 4014, 3924 1154130365Smlaier}; 1155130365Smlaier 1156130365Smlaierstatic __inline struct fve * 1157130365Smlaierflowlist_lookup(fv, pktattr, now) 1158130365Smlaier struct flowvalve *fv; 1159130365Smlaier struct altq_pktattr *pktattr; 1160130365Smlaier struct timeval *now; 1161130365Smlaier{ 1162130365Smlaier struct fve *fve; 1163130365Smlaier int flows; 1164130365Smlaier struct ip *ip; 1165130365Smlaier#ifdef INET6 1166130365Smlaier struct ip6_hdr *ip6; 1167130365Smlaier#endif 1168130365Smlaier struct timeval tthresh; 1169130365Smlaier 1170130365Smlaier if (pktattr == NULL) 1171130365Smlaier return (NULL); 1172130365Smlaier 1173130365Smlaier tthresh.tv_sec = now->tv_sec - FV_TTHRESH; 1174130365Smlaier flows = 0; 1175130365Smlaier /* 1176130365Smlaier * search the flow list 1177130365Smlaier */ 1178130365Smlaier switch (pktattr->pattr_af) { 1179130365Smlaier case AF_INET: 1180130365Smlaier ip = (struct ip *)pktattr->pattr_hdr; 1181130365Smlaier TAILQ_FOREACH(fve, &fv->fv_flowlist, fve_lru){ 1182130365Smlaier if (fve->fve_lastdrop.tv_sec == 0) 1183130365Smlaier break; 1184130365Smlaier if (fve->fve_lastdrop.tv_sec < tthresh.tv_sec) { 1185130365Smlaier fve->fve_lastdrop.tv_sec = 0; 1186130365Smlaier break; 1187130365Smlaier } 1188130365Smlaier if (fve->fve_flow.flow_af == AF_INET && 1189130365Smlaier fve->fve_flow.flow_ip.ip_src.s_addr == 1190130365Smlaier ip->ip_src.s_addr && 1191130365Smlaier fve->fve_flow.flow_ip.ip_dst.s_addr == 1192130365Smlaier ip->ip_dst.s_addr) 1193130365Smlaier return (fve); 1194130365Smlaier flows++; 1195130365Smlaier } 1196130365Smlaier break; 1197130365Smlaier#ifdef INET6 1198130365Smlaier case AF_INET6: 1199130365Smlaier ip6 = (struct ip6_hdr *)pktattr->pattr_hdr; 1200130365Smlaier TAILQ_FOREACH(fve, &fv->fv_flowlist, fve_lru){ 1201130365Smlaier if (fve->fve_lastdrop.tv_sec == 0) 1202130365Smlaier break; 1203130365Smlaier if (fve->fve_lastdrop.tv_sec < tthresh.tv_sec) { 1204130365Smlaier fve->fve_lastdrop.tv_sec = 0; 1205130365Smlaier break; 1206130365Smlaier } 1207130365Smlaier if (fve->fve_flow.flow_af == AF_INET6 && 1208130365Smlaier IN6_ARE_ADDR_EQUAL(&fve->fve_flow.flow_ip6.ip6_src, 1209130365Smlaier &ip6->ip6_src) && 1210130365Smlaier IN6_ARE_ADDR_EQUAL(&fve->fve_flow.flow_ip6.ip6_dst, 1211130365Smlaier &ip6->ip6_dst)) 1212130365Smlaier return (fve); 1213130365Smlaier flows++; 1214130365Smlaier } 1215130365Smlaier break; 1216130365Smlaier#endif /* INET6 */ 1217130365Smlaier 1218130365Smlaier default: 1219130365Smlaier /* unknown protocol. no drop. */ 1220130365Smlaier return (NULL); 1221130365Smlaier } 1222130365Smlaier fv->fv_flows = flows; /* save the number of active fve's */ 1223130365Smlaier return (NULL); 1224130365Smlaier} 1225130365Smlaier 1226130365Smlaierstatic __inline struct fve * 1227130365Smlaierflowlist_reclaim(fv, pktattr) 1228130365Smlaier struct flowvalve *fv; 1229130365Smlaier struct altq_pktattr *pktattr; 1230130365Smlaier{ 1231130365Smlaier struct fve *fve; 1232130365Smlaier struct ip *ip; 1233130365Smlaier#ifdef INET6 1234130365Smlaier struct ip6_hdr *ip6; 1235130365Smlaier#endif 1236130365Smlaier 1237130365Smlaier /* 1238130365Smlaier * get an entry from the tail of the LRU list. 1239130365Smlaier */ 1240130365Smlaier fve = TAILQ_LAST(&fv->fv_flowlist, fv_flowhead); 1241130365Smlaier 1242130365Smlaier switch (pktattr->pattr_af) { 1243130365Smlaier case AF_INET: 1244130365Smlaier ip = (struct ip *)pktattr->pattr_hdr; 1245130365Smlaier fve->fve_flow.flow_af = AF_INET; 1246130365Smlaier fve->fve_flow.flow_ip.ip_src = ip->ip_src; 1247130365Smlaier fve->fve_flow.flow_ip.ip_dst = ip->ip_dst; 1248130365Smlaier break; 1249130365Smlaier#ifdef INET6 1250130365Smlaier case AF_INET6: 1251130365Smlaier ip6 = (struct ip6_hdr *)pktattr->pattr_hdr; 1252130365Smlaier fve->fve_flow.flow_af = AF_INET6; 1253130365Smlaier fve->fve_flow.flow_ip6.ip6_src = ip6->ip6_src; 1254130365Smlaier fve->fve_flow.flow_ip6.ip6_dst = ip6->ip6_dst; 1255130365Smlaier break; 1256130365Smlaier#endif 1257130365Smlaier } 1258130365Smlaier 1259130365Smlaier fve->fve_state = Green; 1260130365Smlaier fve->fve_p = 0.0; 1261130365Smlaier fve->fve_f = 0.0; 1262130365Smlaier fve->fve_ifseq = fv->fv_ifseq - 1; 1263130365Smlaier fve->fve_count = 0; 1264130365Smlaier 1265130365Smlaier fv->fv_flows++; 1266130365Smlaier#ifdef FV_STATS 1267130365Smlaier fv->fv_stats.alloc++; 1268130365Smlaier#endif 1269130365Smlaier return (fve); 1270130365Smlaier} 1271130365Smlaier 1272130365Smlaierstatic __inline void 1273130365Smlaierflowlist_move_to_head(fv, fve) 1274130365Smlaier struct flowvalve *fv; 1275130365Smlaier struct fve *fve; 1276130365Smlaier{ 1277130365Smlaier if (TAILQ_FIRST(&fv->fv_flowlist) != fve) { 1278130365Smlaier TAILQ_REMOVE(&fv->fv_flowlist, fve, fve_lru); 1279130365Smlaier TAILQ_INSERT_HEAD(&fv->fv_flowlist, fve, fve_lru); 1280130365Smlaier } 1281130365Smlaier} 1282130365Smlaier 1283130368Smlaier#if 0 /* XXX: make the compiler happy (fv_alloc unused) */ 1284130365Smlaier/* 1285130365Smlaier * allocate flowvalve structure 1286130365Smlaier */ 1287130365Smlaierstatic struct flowvalve * 1288130365Smlaierfv_alloc(rp) 1289130365Smlaier struct red *rp; 1290130365Smlaier{ 1291130365Smlaier struct flowvalve *fv; 1292130365Smlaier struct fve *fve; 1293130365Smlaier int i, num; 1294130365Smlaier 1295130365Smlaier num = FV_FLOWLISTSIZE; 1296184205Sdes fv = malloc(sizeof(struct flowvalve), 1297130365Smlaier M_DEVBUF, M_WAITOK); 1298130365Smlaier if (fv == NULL) 1299130365Smlaier return (NULL); 1300130365Smlaier bzero(fv, sizeof(struct flowvalve)); 1301130365Smlaier 1302184205Sdes fv->fv_fves = malloc(sizeof(struct fve) * num, 1303130365Smlaier M_DEVBUF, M_WAITOK); 1304130365Smlaier if (fv->fv_fves == NULL) { 1305184205Sdes free(fv, M_DEVBUF); 1306130365Smlaier return (NULL); 1307130365Smlaier } 1308130365Smlaier bzero(fv->fv_fves, sizeof(struct fve) * num); 1309130365Smlaier 1310130365Smlaier fv->fv_flows = 0; 1311130365Smlaier TAILQ_INIT(&fv->fv_flowlist); 1312130365Smlaier for (i = 0; i < num; i++) { 1313130365Smlaier fve = &fv->fv_fves[i]; 1314130365Smlaier fve->fve_lastdrop.tv_sec = 0; 1315130365Smlaier TAILQ_INSERT_TAIL(&fv->fv_flowlist, fve, fve_lru); 1316130365Smlaier } 1317130365Smlaier 1318130365Smlaier /* initialize drop rate threshold in scaled fixed-point */ 1319130365Smlaier fv->fv_pthresh = (FV_PSCALE(1) << FP_SHIFT) / rp->red_inv_pmax; 1320130365Smlaier 1321130365Smlaier /* initialize drop rate to fraction table */ 1322184205Sdes fv->fv_p2ftab = malloc(sizeof(int) * BRTT_SIZE, 1323130365Smlaier M_DEVBUF, M_WAITOK); 1324130365Smlaier if (fv->fv_p2ftab == NULL) { 1325184205Sdes free(fv->fv_fves, M_DEVBUF); 1326184205Sdes free(fv, M_DEVBUF); 1327130365Smlaier return (NULL); 1328130365Smlaier } 1329130365Smlaier /* 1330130365Smlaier * create the p2f table. 1331130365Smlaier * (shift is used to keep the precision) 1332130365Smlaier */ 1333130365Smlaier for (i = 1; i < BRTT_SIZE; i++) { 1334130365Smlaier int f; 1335130365Smlaier 1336130365Smlaier f = brtt_tab[i] << 8; 1337130365Smlaier fv->fv_p2ftab[i] = (f / (rp->red_thmax + FV_ALPHA)) >> 8; 1338130365Smlaier } 1339130365Smlaier 1340130365Smlaier return (fv); 1341130365Smlaier} 1342130368Smlaier#endif 1343130365Smlaier 1344130365Smlaierstatic void fv_destroy(fv) 1345130365Smlaier struct flowvalve *fv; 1346130365Smlaier{ 1347184205Sdes free(fv->fv_p2ftab, M_DEVBUF); 1348184205Sdes free(fv->fv_fves, M_DEVBUF); 1349184205Sdes free(fv, M_DEVBUF); 1350130365Smlaier} 1351130365Smlaier 1352130365Smlaierstatic __inline int 1353130365Smlaierfv_p2f(fv, p) 1354130365Smlaier struct flowvalve *fv; 1355130365Smlaier int p; 1356130365Smlaier{ 1357130365Smlaier int val, f; 1358130365Smlaier 1359130365Smlaier if (p >= BRTT_PMAX) 1360130365Smlaier f = fv->fv_p2ftab[BRTT_SIZE-1]; 1361130365Smlaier else if ((val = (p & BRTT_MASK))) 1362130365Smlaier f = fv->fv_p2ftab[(val >> BRTT_SHIFT)]; 1363130365Smlaier else 1364130365Smlaier f = fv->fv_p2ftab[1]; 1365130365Smlaier return (f); 1366130365Smlaier} 1367130365Smlaier 1368130365Smlaier/* 1369130365Smlaier * check if an arriving packet should be pre-dropped. 1370130365Smlaier * called from red_addq() when a packet arrives. 1371130365Smlaier * returns 1 when the packet should be pre-dropped. 1372130365Smlaier * should be called in splimp. 1373130365Smlaier */ 1374130365Smlaierstatic int 1375130365Smlaierfv_checkflow(fv, pktattr, fcache) 1376130365Smlaier struct flowvalve *fv; 1377130365Smlaier struct altq_pktattr *pktattr; 1378130365Smlaier struct fve **fcache; 1379130365Smlaier{ 1380130365Smlaier struct fve *fve; 1381130365Smlaier struct timeval now; 1382130365Smlaier 1383130365Smlaier fv->fv_ifseq++; 1384130365Smlaier FV_TIMESTAMP(&now); 1385130365Smlaier 1386130365Smlaier if ((fve = flowlist_lookup(fv, pktattr, &now)) == NULL) 1387130365Smlaier /* no matching entry in the flowlist */ 1388130365Smlaier return (0); 1389130365Smlaier 1390130365Smlaier *fcache = fve; 1391130365Smlaier 1392130365Smlaier /* update fraction f for every FV_N packets */ 1393130365Smlaier if (++fve->fve_count == FV_N) { 1394130365Smlaier /* 1395130365Smlaier * f = Wf * N / (fv_ifseq - fve_ifseq) + (1 - Wf) * f 1396130365Smlaier */ 1397130365Smlaier fve->fve_f = 1398130365Smlaier (FV_N << FP_SHIFT) / (fv->fv_ifseq - fve->fve_ifseq) 1399130365Smlaier + fve->fve_f - FV_FUNSCALE(fve->fve_f); 1400130365Smlaier fve->fve_ifseq = fv->fv_ifseq; 1401130365Smlaier fve->fve_count = 0; 1402130365Smlaier } 1403130365Smlaier 1404130365Smlaier /* 1405130365Smlaier * overpumping test 1406130365Smlaier */ 1407130365Smlaier if (fve->fve_state == Green && fve->fve_p > fv->fv_pthresh) { 1408130365Smlaier int fthresh; 1409130365Smlaier 1410130365Smlaier /* calculate a threshold */ 1411130365Smlaier fthresh = fv_p2f(fv, fve->fve_p); 1412130365Smlaier if (fve->fve_f > fthresh) 1413130365Smlaier fve->fve_state = Red; 1414130365Smlaier } 1415130365Smlaier 1416130365Smlaier if (fve->fve_state == Red) { 1417130365Smlaier /* 1418130365Smlaier * backoff test 1419130365Smlaier */ 1420130365Smlaier if (now.tv_sec - fve->fve_lastdrop.tv_sec > FV_BACKOFFTHRESH) { 1421130365Smlaier /* no drop for at least FV_BACKOFFTHRESH sec */ 1422130365Smlaier fve->fve_p = 0; 1423130365Smlaier fve->fve_state = Green; 1424130365Smlaier#ifdef FV_STATS 1425130365Smlaier fv->fv_stats.escape++; 1426130365Smlaier#endif 1427130365Smlaier } else { 1428130365Smlaier /* block this flow */ 1429130365Smlaier flowlist_move_to_head(fv, fve); 1430130365Smlaier fve->fve_lastdrop = now; 1431130365Smlaier#ifdef FV_STATS 1432130365Smlaier fv->fv_stats.predrop++; 1433130365Smlaier#endif 1434130365Smlaier return (1); 1435130365Smlaier } 1436130365Smlaier } 1437130365Smlaier 1438130365Smlaier /* 1439130365Smlaier * p = (1 - Wp) * p 1440130365Smlaier */ 1441130365Smlaier fve->fve_p -= FV_PUNSCALE(fve->fve_p); 1442130365Smlaier if (fve->fve_p < 0) 1443130365Smlaier fve->fve_p = 0; 1444130365Smlaier#ifdef FV_STATS 1445130365Smlaier fv->fv_stats.pass++; 1446130365Smlaier#endif 1447130365Smlaier return (0); 1448130365Smlaier} 1449130365Smlaier 1450130365Smlaier/* 1451130365Smlaier * called from red_addq when a packet is dropped by red. 1452130365Smlaier * should be called in splimp. 1453130365Smlaier */ 1454130365Smlaierstatic void fv_dropbyred(fv, pktattr, fcache) 1455130365Smlaier struct flowvalve *fv; 1456130365Smlaier struct altq_pktattr *pktattr; 1457130365Smlaier struct fve *fcache; 1458130365Smlaier{ 1459130365Smlaier struct fve *fve; 1460130365Smlaier struct timeval now; 1461130365Smlaier 1462130365Smlaier if (pktattr == NULL) 1463130365Smlaier return; 1464130365Smlaier FV_TIMESTAMP(&now); 1465130365Smlaier 1466130365Smlaier if (fcache != NULL) 1467130365Smlaier /* the fve of this packet is already cached */ 1468130365Smlaier fve = fcache; 1469130365Smlaier else if ((fve = flowlist_lookup(fv, pktattr, &now)) == NULL) 1470130365Smlaier fve = flowlist_reclaim(fv, pktattr); 1471130365Smlaier 1472130365Smlaier flowlist_move_to_head(fv, fve); 1473130365Smlaier 1474130365Smlaier /* 1475130365Smlaier * update p: the following line cancels the update 1476130365Smlaier * in fv_checkflow() and calculate 1477130365Smlaier * p = Wp + (1 - Wp) * p 1478130365Smlaier */ 1479130365Smlaier fve->fve_p = (1 << FP_SHIFT) + fve->fve_p; 1480130365Smlaier 1481130365Smlaier fve->fve_lastdrop = now; 1482130365Smlaier} 1483130365Smlaier 1484130365Smlaier#endif /* ALTQ_FLOWVALVE */ 1485130365Smlaier 1486130365Smlaier#ifdef KLD_MODULE 1487130365Smlaier 1488130365Smlaierstatic struct altqsw red_sw = 1489130365Smlaier {"red", redopen, redclose, redioctl}; 1490130365Smlaier 1491130365SmlaierALTQ_MODULE(altq_red, ALTQT_RED, &red_sw); 1492130365SmlaierMODULE_VERSION(altq_red, 1); 1493130365Smlaier 1494130365Smlaier#endif /* KLD_MODULE */ 1495130365Smlaier#endif /* ALTQ3_COMPAT */ 1496130365Smlaier 1497130365Smlaier#endif /* ALTQ_RED */ 1498