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 234184205Sdes rp = malloc(sizeof(red_t), M_DEVBUF, M_WAITOK); 235130365Smlaier if (rp == NULL) 236130365Smlaier return (NULL); 237130365Smlaier bzero(rp, sizeof(red_t)); 238130365Smlaier 239130365Smlaier rp->red_avg = 0; 240130365Smlaier rp->red_idle = 1; 241130365Smlaier 242130365Smlaier if (weight == 0) 243130365Smlaier rp->red_weight = W_WEIGHT; 244130365Smlaier else 245130365Smlaier rp->red_weight = weight; 246130365Smlaier if (inv_pmax == 0) 247130365Smlaier rp->red_inv_pmax = default_inv_pmax; 248130365Smlaier else 249130365Smlaier rp->red_inv_pmax = inv_pmax; 250130365Smlaier if (th_min == 0) 251130365Smlaier rp->red_thmin = default_th_min; 252130365Smlaier else 253130365Smlaier rp->red_thmin = th_min; 254130365Smlaier if (th_max == 0) 255130365Smlaier rp->red_thmax = default_th_max; 256130365Smlaier else 257130365Smlaier rp->red_thmax = th_max; 258130365Smlaier 259130365Smlaier rp->red_flags = flags; 260130365Smlaier 261130365Smlaier if (pkttime == 0) 262130365Smlaier /* default packet time: 1000 bytes / 10Mbps * 8 * 1000000 */ 263130365Smlaier rp->red_pkttime = 800; 264130365Smlaier else 265130365Smlaier rp->red_pkttime = pkttime; 266130365Smlaier 267130365Smlaier if (weight == 0) { 268130365Smlaier /* when the link is very slow, adjust red parameters */ 269130365Smlaier npkts_per_sec = 1000000 / rp->red_pkttime; 270130365Smlaier if (npkts_per_sec < 50) { 271130365Smlaier /* up to about 400Kbps */ 272130365Smlaier rp->red_weight = W_WEIGHT_2; 273130365Smlaier } else if (npkts_per_sec < 300) { 274130365Smlaier /* up to about 2.4Mbps */ 275130365Smlaier rp->red_weight = W_WEIGHT_1; 276130365Smlaier } 277130365Smlaier } 278130365Smlaier 279130365Smlaier /* calculate wshift. weight must be power of 2 */ 280130365Smlaier w = rp->red_weight; 281130365Smlaier for (i = 0; w > 1; i++) 282130365Smlaier w = w >> 1; 283130365Smlaier rp->red_wshift = i; 284130365Smlaier w = 1 << rp->red_wshift; 285130365Smlaier if (w != rp->red_weight) { 286130365Smlaier printf("invalid weight value %d for red! use %d\n", 287130365Smlaier rp->red_weight, w); 288130365Smlaier rp->red_weight = w; 289130365Smlaier } 290130365Smlaier 291130365Smlaier /* 292130365Smlaier * thmin_s and thmax_s are scaled versions of th_min and th_max 293130365Smlaier * to be compared with avg. 294130365Smlaier */ 295130365Smlaier rp->red_thmin_s = rp->red_thmin << (rp->red_wshift + FP_SHIFT); 296130365Smlaier rp->red_thmax_s = rp->red_thmax << (rp->red_wshift + FP_SHIFT); 297130365Smlaier 298130365Smlaier /* 299130365Smlaier * precompute probability denominator 300130365Smlaier * probd = (2 * (TH_MAX-TH_MIN) / pmax) in fixed-point 301130365Smlaier */ 302130365Smlaier rp->red_probd = (2 * (rp->red_thmax - rp->red_thmin) 303130365Smlaier * rp->red_inv_pmax) << FP_SHIFT; 304130365Smlaier 305130365Smlaier /* allocate weight table */ 306130365Smlaier rp->red_wtab = wtab_alloc(rp->red_weight); 307130365Smlaier 308130365Smlaier microtime(&rp->red_last); 309130365Smlaier return (rp); 310130365Smlaier} 311130365Smlaier 312130365Smlaiervoid 313130365Smlaierred_destroy(red_t *rp) 314130365Smlaier{ 315130365Smlaier#ifdef ALTQ3_COMPAT 316130365Smlaier#ifdef ALTQ_FLOWVALVE 317130365Smlaier if (rp->red_flowvalve != NULL) 318130365Smlaier fv_destroy(rp->red_flowvalve); 319130365Smlaier#endif 320130365Smlaier#endif /* ALTQ3_COMPAT */ 321130365Smlaier wtab_destroy(rp->red_wtab); 322184205Sdes free(rp, M_DEVBUF); 323130365Smlaier} 324130365Smlaier 325130365Smlaiervoid 326130365Smlaierred_getstats(red_t *rp, struct redstats *sp) 327130365Smlaier{ 328130365Smlaier sp->q_avg = rp->red_avg >> rp->red_wshift; 329130365Smlaier sp->xmit_cnt = rp->red_stats.xmit_cnt; 330130365Smlaier sp->drop_cnt = rp->red_stats.drop_cnt; 331130365Smlaier sp->drop_forced = rp->red_stats.drop_forced; 332130365Smlaier sp->drop_unforced = rp->red_stats.drop_unforced; 333130365Smlaier sp->marked_packets = rp->red_stats.marked_packets; 334130365Smlaier} 335130365Smlaier 336130365Smlaierint 337130365Smlaierred_addq(red_t *rp, class_queue_t *q, struct mbuf *m, 338130365Smlaier struct altq_pktattr *pktattr) 339130365Smlaier{ 340130365Smlaier int avg, droptype; 341130365Smlaier int n; 342130365Smlaier#ifdef ALTQ3_COMPAT 343130365Smlaier#ifdef ALTQ_FLOWVALVE 344130365Smlaier struct fve *fve = NULL; 345130365Smlaier 346130365Smlaier if (rp->red_flowvalve != NULL && rp->red_flowvalve->fv_flows > 0) 347130365Smlaier if (fv_checkflow(rp->red_flowvalve, pktattr, &fve)) { 348130365Smlaier m_freem(m); 349130365Smlaier return (-1); 350130365Smlaier } 351130365Smlaier#endif 352130365Smlaier#endif /* ALTQ3_COMPAT */ 353130365Smlaier 354130365Smlaier avg = rp->red_avg; 355130365Smlaier 356130365Smlaier /* 357130365Smlaier * if we were idle, we pretend that n packets arrived during 358130365Smlaier * the idle period. 359130365Smlaier */ 360130365Smlaier if (rp->red_idle) { 361130365Smlaier struct timeval now; 362130365Smlaier int t; 363130365Smlaier 364130365Smlaier rp->red_idle = 0; 365130365Smlaier microtime(&now); 366130365Smlaier t = (now.tv_sec - rp->red_last.tv_sec); 367130365Smlaier if (t > 60) { 368130365Smlaier /* 369130365Smlaier * being idle for more than 1 minute, set avg to zero. 370130365Smlaier * this prevents t from overflow. 371130365Smlaier */ 372130365Smlaier avg = 0; 373130365Smlaier } else { 374130365Smlaier t = t * 1000000 + (now.tv_usec - rp->red_last.tv_usec); 375130365Smlaier n = t / rp->red_pkttime - 1; 376130365Smlaier 377130365Smlaier /* the following line does (avg = (1 - Wq)^n * avg) */ 378130365Smlaier if (n > 0) 379130365Smlaier avg = (avg >> FP_SHIFT) * 380130365Smlaier pow_w(rp->red_wtab, n); 381130365Smlaier } 382130365Smlaier } 383130365Smlaier 384130365Smlaier /* run estimator. (note: avg is scaled by WEIGHT in fixed-point) */ 385130365Smlaier avg += (qlen(q) << FP_SHIFT) - (avg >> rp->red_wshift); 386130365Smlaier rp->red_avg = avg; /* save the new value */ 387130365Smlaier 388130365Smlaier /* 389130365Smlaier * red_count keeps a tally of arriving traffic that has not 390130365Smlaier * been dropped. 391130365Smlaier */ 392130365Smlaier rp->red_count++; 393130365Smlaier 394130365Smlaier /* see if we drop early */ 395130365Smlaier droptype = DTYPE_NODROP; 396130365Smlaier if (avg >= rp->red_thmin_s && qlen(q) > 1) { 397130365Smlaier if (avg >= rp->red_thmax_s) { 398130365Smlaier /* avg >= th_max: forced drop */ 399130365Smlaier droptype = DTYPE_FORCED; 400130365Smlaier } else if (rp->red_old == 0) { 401130365Smlaier /* first exceeds th_min */ 402130365Smlaier rp->red_count = 1; 403130365Smlaier rp->red_old = 1; 404130365Smlaier } else if (drop_early((avg - rp->red_thmin_s) >> rp->red_wshift, 405130365Smlaier rp->red_probd, rp->red_count)) { 406130365Smlaier /* mark or drop by red */ 407130365Smlaier if ((rp->red_flags & REDF_ECN) && 408130365Smlaier mark_ecn(m, pktattr, rp->red_flags)) { 409130365Smlaier /* successfully marked. do not drop. */ 410130365Smlaier rp->red_count = 0; 411130365Smlaier#ifdef RED_STATS 412130365Smlaier rp->red_stats.marked_packets++; 413130365Smlaier#endif 414130365Smlaier } else { 415130365Smlaier /* unforced drop by red */ 416130365Smlaier droptype = DTYPE_EARLY; 417130365Smlaier } 418130365Smlaier } 419130365Smlaier } else { 420130365Smlaier /* avg < th_min */ 421130365Smlaier rp->red_old = 0; 422130365Smlaier } 423130365Smlaier 424130365Smlaier /* 425130365Smlaier * if the queue length hits the hard limit, it's a forced drop. 426130365Smlaier */ 427130365Smlaier if (droptype == DTYPE_NODROP && qlen(q) >= qlimit(q)) 428130365Smlaier droptype = DTYPE_FORCED; 429130365Smlaier 430130365Smlaier#ifdef RED_RANDOM_DROP 431130365Smlaier /* if successful or forced drop, enqueue this packet. */ 432130365Smlaier if (droptype != DTYPE_EARLY) 433130365Smlaier _addq(q, m); 434130365Smlaier#else 435130365Smlaier /* if successful, enqueue this packet. */ 436130365Smlaier if (droptype == DTYPE_NODROP) 437130365Smlaier _addq(q, m); 438130365Smlaier#endif 439130365Smlaier if (droptype != DTYPE_NODROP) { 440130365Smlaier if (droptype == DTYPE_EARLY) { 441130365Smlaier /* drop the incoming packet */ 442130365Smlaier#ifdef RED_STATS 443130365Smlaier rp->red_stats.drop_unforced++; 444130365Smlaier#endif 445130365Smlaier } else { 446130365Smlaier /* forced drop, select a victim packet in the queue. */ 447130365Smlaier#ifdef RED_RANDOM_DROP 448130365Smlaier m = _getq_random(q); 449130365Smlaier#endif 450130365Smlaier#ifdef RED_STATS 451130365Smlaier rp->red_stats.drop_forced++; 452130365Smlaier#endif 453130365Smlaier } 454130365Smlaier#ifdef RED_STATS 455130365Smlaier PKTCNTR_ADD(&rp->red_stats.drop_cnt, m_pktlen(m)); 456130365Smlaier#endif 457130365Smlaier rp->red_count = 0; 458130365Smlaier#ifdef ALTQ3_COMPAT 459130365Smlaier#ifdef ALTQ_FLOWVALVE 460130365Smlaier if (rp->red_flowvalve != NULL) 461130365Smlaier fv_dropbyred(rp->red_flowvalve, pktattr, fve); 462130365Smlaier#endif 463130365Smlaier#endif /* ALTQ3_COMPAT */ 464130365Smlaier m_freem(m); 465130365Smlaier return (-1); 466130365Smlaier } 467130365Smlaier /* successfully queued */ 468130365Smlaier#ifdef RED_STATS 469130365Smlaier PKTCNTR_ADD(&rp->red_stats.xmit_cnt, m_pktlen(m)); 470130365Smlaier#endif 471130365Smlaier return (0); 472130365Smlaier} 473130365Smlaier 474130365Smlaier/* 475130365Smlaier * early-drop probability is calculated as follows: 476130365Smlaier * prob = p_max * (avg - th_min) / (th_max - th_min) 477130365Smlaier * prob_a = prob / (2 - count*prob) 478130365Smlaier * = (avg-th_min) / (2*(th_max-th_min)*inv_p_max - count*(avg-th_min)) 479130365Smlaier * here prob_a increases as successive undrop count increases. 480130365Smlaier * (prob_a starts from prob/2, becomes prob when (count == (1 / prob)), 481130365Smlaier * becomes 1 when (count >= (2 / prob))). 482130365Smlaier */ 483130365Smlaierint 484130365Smlaierdrop_early(int fp_len, int fp_probd, int count) 485130365Smlaier{ 486130365Smlaier int d; /* denominator of drop-probability */ 487130365Smlaier 488130365Smlaier d = fp_probd - count * fp_len; 489130365Smlaier if (d <= 0) 490130365Smlaier /* count exceeds the hard limit: drop or mark */ 491130365Smlaier return (1); 492130365Smlaier 493130365Smlaier /* 494130365Smlaier * now the range of d is [1..600] in fixed-point. (when 495130365Smlaier * th_max-th_min=10 and p_max=1/30) 496130365Smlaier * drop probability = (avg - TH_MIN) / d 497130365Smlaier */ 498130365Smlaier 499130365Smlaier if ((arc4random() % d) < fp_len) { 500130365Smlaier /* drop or mark */ 501130365Smlaier return (1); 502130365Smlaier } 503130365Smlaier /* no drop/mark */ 504130365Smlaier return (0); 505130365Smlaier} 506130365Smlaier 507130365Smlaier/* 508130365Smlaier * try to mark CE bit to the packet. 509130365Smlaier * returns 1 if successfully marked, 0 otherwise. 510130365Smlaier */ 511130365Smlaierint 512130365Smlaiermark_ecn(struct mbuf *m, struct altq_pktattr *pktattr, int flags) 513130365Smlaier{ 514130365Smlaier struct mbuf *m0; 515171173Smlaier struct pf_mtag *at; 516130365Smlaier void *hdr; 517130365Smlaier 518171173Smlaier at = pf_find_mtag(m); 519171173Smlaier if (at != NULL) { 520130365Smlaier hdr = at->hdr; 521130365Smlaier#ifdef ALTQ3_COMPAT 522130365Smlaier } else if (pktattr != NULL) { 523130365Smlaier af = pktattr->pattr_af; 524130365Smlaier hdr = pktattr->pattr_hdr; 525130365Smlaier#endif /* ALTQ3_COMPAT */ 526130365Smlaier } else 527130365Smlaier return (0); 528130365Smlaier 529130365Smlaier /* verify that pattr_hdr is within the mbuf data */ 530130365Smlaier for (m0 = m; m0 != NULL; m0 = m0->m_next) 531130365Smlaier if (((caddr_t)hdr >= m0->m_data) && 532130365Smlaier ((caddr_t)hdr < m0->m_data + m0->m_len)) 533130365Smlaier break; 534130365Smlaier if (m0 == NULL) { 535130365Smlaier /* ick, tag info is stale */ 536130365Smlaier return (0); 537130365Smlaier } 538130365Smlaier 539223637Sbz switch (((struct ip *)hdr)->ip_v) { 540223637Sbz case IPVERSION: 541130365Smlaier if (flags & REDF_ECN4) { 542130365Smlaier struct ip *ip = hdr; 543130365Smlaier u_int8_t otos; 544130365Smlaier int sum; 545130365Smlaier 546130365Smlaier if (ip->ip_v != 4) 547130365Smlaier return (0); /* version mismatch! */ 548130365Smlaier 549130365Smlaier if ((ip->ip_tos & IPTOS_ECN_MASK) == IPTOS_ECN_NOTECT) 550130365Smlaier return (0); /* not-ECT */ 551130365Smlaier if ((ip->ip_tos & IPTOS_ECN_MASK) == IPTOS_ECN_CE) 552130365Smlaier return (1); /* already marked */ 553130365Smlaier 554130365Smlaier /* 555130365Smlaier * ecn-capable but not marked, 556130365Smlaier * mark CE and update checksum 557130365Smlaier */ 558130365Smlaier otos = ip->ip_tos; 559130365Smlaier ip->ip_tos |= IPTOS_ECN_CE; 560130365Smlaier /* 561130365Smlaier * update checksum (from RFC1624) 562130365Smlaier * HC' = ~(~HC + ~m + m') 563130365Smlaier */ 564130365Smlaier sum = ~ntohs(ip->ip_sum) & 0xffff; 565130365Smlaier sum += (~otos & 0xffff) + ip->ip_tos; 566130365Smlaier sum = (sum >> 16) + (sum & 0xffff); 567130365Smlaier sum += (sum >> 16); /* add carry */ 568130365Smlaier ip->ip_sum = htons(~sum & 0xffff); 569130365Smlaier return (1); 570130365Smlaier } 571130365Smlaier break; 572130365Smlaier#ifdef INET6 573223637Sbz case (IPV6_VERSION >> 4): 574130365Smlaier if (flags & REDF_ECN6) { 575130365Smlaier struct ip6_hdr *ip6 = hdr; 576130365Smlaier u_int32_t flowlabel; 577130365Smlaier 578130365Smlaier flowlabel = ntohl(ip6->ip6_flow); 579130365Smlaier if ((flowlabel >> 28) != 6) 580130365Smlaier return (0); /* version mismatch! */ 581130365Smlaier if ((flowlabel & (IPTOS_ECN_MASK << 20)) == 582130365Smlaier (IPTOS_ECN_NOTECT << 20)) 583130365Smlaier return (0); /* not-ECT */ 584130365Smlaier if ((flowlabel & (IPTOS_ECN_MASK << 20)) == 585130365Smlaier (IPTOS_ECN_CE << 20)) 586130365Smlaier return (1); /* already marked */ 587130365Smlaier /* 588130365Smlaier * ecn-capable but not marked, mark CE 589130365Smlaier */ 590130365Smlaier flowlabel |= (IPTOS_ECN_CE << 20); 591130365Smlaier ip6->ip6_flow = htonl(flowlabel); 592130365Smlaier return (1); 593130365Smlaier } 594130365Smlaier break; 595130365Smlaier#endif /* INET6 */ 596130365Smlaier } 597130365Smlaier 598130365Smlaier /* not marked */ 599130365Smlaier return (0); 600130365Smlaier} 601130365Smlaier 602130365Smlaierstruct mbuf * 603130365Smlaierred_getq(rp, q) 604130365Smlaier red_t *rp; 605130365Smlaier class_queue_t *q; 606130365Smlaier{ 607130365Smlaier struct mbuf *m; 608130365Smlaier 609130365Smlaier if ((m = _getq(q)) == NULL) { 610130365Smlaier if (rp->red_idle == 0) { 611130365Smlaier rp->red_idle = 1; 612130365Smlaier microtime(&rp->red_last); 613130365Smlaier } 614130365Smlaier return NULL; 615130365Smlaier } 616130365Smlaier 617130365Smlaier rp->red_idle = 0; 618130365Smlaier return (m); 619130365Smlaier} 620130365Smlaier 621130365Smlaier/* 622130365Smlaier * helper routine to calibrate avg during idle. 623130365Smlaier * pow_w(wtab, n) returns (1 - Wq)^n in fixed-point 624130365Smlaier * here Wq = 1/weight and the code assumes Wq is close to zero. 625130365Smlaier * 626130365Smlaier * w_tab[n] holds ((1 - Wq)^(2^n)) in fixed-point. 627130365Smlaier */ 628130365Smlaierstatic struct wtab *wtab_list = NULL; /* pointer to wtab list */ 629130365Smlaier 630130365Smlaierstruct wtab * 631130365Smlaierwtab_alloc(int weight) 632130365Smlaier{ 633130365Smlaier struct wtab *w; 634130365Smlaier int i; 635130365Smlaier 636130365Smlaier for (w = wtab_list; w != NULL; w = w->w_next) 637130365Smlaier if (w->w_weight == weight) { 638130365Smlaier w->w_refcount++; 639130365Smlaier return (w); 640130365Smlaier } 641130365Smlaier 642184205Sdes w = malloc(sizeof(struct wtab), M_DEVBUF, M_WAITOK); 643130365Smlaier if (w == NULL) 644130365Smlaier panic("wtab_alloc: malloc failed!"); 645130365Smlaier bzero(w, sizeof(struct wtab)); 646130365Smlaier w->w_weight = weight; 647130365Smlaier w->w_refcount = 1; 648130365Smlaier w->w_next = wtab_list; 649130365Smlaier wtab_list = w; 650130365Smlaier 651130365Smlaier /* initialize the weight table */ 652130365Smlaier w->w_tab[0] = ((weight - 1) << FP_SHIFT) / weight; 653130365Smlaier for (i = 1; i < 32; i++) { 654130365Smlaier w->w_tab[i] = (w->w_tab[i-1] * w->w_tab[i-1]) >> FP_SHIFT; 655130365Smlaier if (w->w_tab[i] == 0 && w->w_param_max == 0) 656130365Smlaier w->w_param_max = 1 << i; 657130365Smlaier } 658130365Smlaier 659130365Smlaier return (w); 660130365Smlaier} 661130365Smlaier 662130365Smlaierint 663130365Smlaierwtab_destroy(struct wtab *w) 664130365Smlaier{ 665130365Smlaier struct wtab *prev; 666130365Smlaier 667130365Smlaier if (--w->w_refcount > 0) 668130365Smlaier return (0); 669130365Smlaier 670130365Smlaier if (wtab_list == w) 671130365Smlaier wtab_list = w->w_next; 672130365Smlaier else for (prev = wtab_list; prev->w_next != NULL; prev = prev->w_next) 673130365Smlaier if (prev->w_next == w) { 674130365Smlaier prev->w_next = w->w_next; 675130365Smlaier break; 676130365Smlaier } 677130365Smlaier 678184205Sdes free(w, M_DEVBUF); 679130365Smlaier return (0); 680130365Smlaier} 681130365Smlaier 682130365Smlaierint32_t 683130365Smlaierpow_w(struct wtab *w, int n) 684130365Smlaier{ 685130365Smlaier int i, bit; 686130365Smlaier int32_t val; 687130365Smlaier 688130365Smlaier if (n >= w->w_param_max) 689130365Smlaier return (0); 690130365Smlaier 691130365Smlaier val = 1 << FP_SHIFT; 692130365Smlaier if (n <= 0) 693130365Smlaier return (val); 694130365Smlaier 695130365Smlaier bit = 1; 696130365Smlaier i = 0; 697130365Smlaier while (n) { 698130365Smlaier if (n & bit) { 699130365Smlaier val = (val * w->w_tab[i]) >> FP_SHIFT; 700130365Smlaier n &= ~bit; 701130365Smlaier } 702130365Smlaier i++; 703130365Smlaier bit <<= 1; 704130365Smlaier } 705130365Smlaier return (val); 706130365Smlaier} 707130365Smlaier 708130365Smlaier#ifdef ALTQ3_COMPAT 709130365Smlaier/* 710130365Smlaier * red device interface 711130365Smlaier */ 712130365Smlaieraltqdev_decl(red); 713130365Smlaier 714130365Smlaierint 715130365Smlaierredopen(dev, flag, fmt, p) 716130365Smlaier dev_t dev; 717130365Smlaier int flag, fmt; 718130365Smlaier#if (__FreeBSD_version > 500000) 719130365Smlaier struct thread *p; 720130365Smlaier#else 721130365Smlaier struct proc *p; 722130365Smlaier#endif 723130365Smlaier{ 724130365Smlaier /* everything will be done when the queueing scheme is attached. */ 725130365Smlaier return 0; 726130365Smlaier} 727130365Smlaier 728130365Smlaierint 729130365Smlaierredclose(dev, flag, fmt, p) 730130365Smlaier dev_t dev; 731130365Smlaier int flag, fmt; 732130365Smlaier#if (__FreeBSD_version > 500000) 733130365Smlaier struct thread *p; 734130365Smlaier#else 735130365Smlaier struct proc *p; 736130365Smlaier#endif 737130365Smlaier{ 738130365Smlaier red_queue_t *rqp; 739130365Smlaier int err, error = 0; 740130365Smlaier 741130365Smlaier while ((rqp = red_list) != NULL) { 742130365Smlaier /* destroy all */ 743130365Smlaier err = red_detach(rqp); 744130365Smlaier if (err != 0 && error == 0) 745130365Smlaier error = err; 746130365Smlaier } 747130365Smlaier 748130365Smlaier return error; 749130365Smlaier} 750130365Smlaier 751130365Smlaierint 752130365Smlaierredioctl(dev, cmd, addr, flag, p) 753130365Smlaier dev_t dev; 754130365Smlaier ioctlcmd_t cmd; 755130365Smlaier caddr_t addr; 756130365Smlaier int flag; 757130365Smlaier#if (__FreeBSD_version > 500000) 758130365Smlaier struct thread *p; 759130365Smlaier#else 760130365Smlaier struct proc *p; 761130365Smlaier#endif 762130365Smlaier{ 763130365Smlaier red_queue_t *rqp; 764130365Smlaier struct red_interface *ifacep; 765130365Smlaier struct ifnet *ifp; 766130365Smlaier int error = 0; 767130365Smlaier 768130365Smlaier /* check super-user privilege */ 769130365Smlaier switch (cmd) { 770130365Smlaier case RED_GETSTATS: 771130365Smlaier break; 772130365Smlaier default: 773164033Srwatson#if (__FreeBSD_version > 700000) 774164033Srwatson if ((error = priv_check(p, PRIV_ALTQ_MANAGE)) != 0) 775164033Srwatson#elsif (__FreeBSD_version > 400000) 776130365Smlaier if ((error = suser(p)) != 0) 777130365Smlaier#else 778130365Smlaier if ((error = suser(p->p_ucred, &p->p_acflag)) != 0) 779130365Smlaier#endif 780130365Smlaier return (error); 781130365Smlaier break; 782130365Smlaier } 783130365Smlaier 784130365Smlaier switch (cmd) { 785130365Smlaier 786130365Smlaier case RED_ENABLE: 787130365Smlaier ifacep = (struct red_interface *)addr; 788130365Smlaier if ((rqp = altq_lookup(ifacep->red_ifname, ALTQT_RED)) == NULL) { 789130365Smlaier error = EBADF; 790130365Smlaier break; 791130365Smlaier } 792130365Smlaier error = altq_enable(rqp->rq_ifq); 793130365Smlaier break; 794130365Smlaier 795130365Smlaier case RED_DISABLE: 796130365Smlaier ifacep = (struct red_interface *)addr; 797130365Smlaier if ((rqp = altq_lookup(ifacep->red_ifname, ALTQT_RED)) == NULL) { 798130365Smlaier error = EBADF; 799130365Smlaier break; 800130365Smlaier } 801130365Smlaier error = altq_disable(rqp->rq_ifq); 802130365Smlaier break; 803130365Smlaier 804130365Smlaier case RED_IF_ATTACH: 805130365Smlaier ifp = ifunit(((struct red_interface *)addr)->red_ifname); 806130365Smlaier if (ifp == NULL) { 807130365Smlaier error = ENXIO; 808130365Smlaier break; 809130365Smlaier } 810130365Smlaier 811130365Smlaier /* allocate and initialize red_queue_t */ 812184205Sdes rqp = malloc(sizeof(red_queue_t), M_DEVBUF, M_WAITOK); 813130365Smlaier if (rqp == NULL) { 814130365Smlaier error = ENOMEM; 815130365Smlaier break; 816130365Smlaier } 817130365Smlaier bzero(rqp, sizeof(red_queue_t)); 818130365Smlaier 819184205Sdes rqp->rq_q = malloc(sizeof(class_queue_t), 820130365Smlaier M_DEVBUF, M_WAITOK); 821130365Smlaier if (rqp->rq_q == NULL) { 822184205Sdes free(rqp, M_DEVBUF); 823130365Smlaier error = ENOMEM; 824130365Smlaier break; 825130365Smlaier } 826130365Smlaier bzero(rqp->rq_q, sizeof(class_queue_t)); 827130365Smlaier 828130365Smlaier rqp->rq_red = red_alloc(0, 0, 0, 0, 0, 0); 829130365Smlaier if (rqp->rq_red == NULL) { 830184205Sdes free(rqp->rq_q, M_DEVBUF); 831184205Sdes free(rqp, M_DEVBUF); 832130365Smlaier error = ENOMEM; 833130365Smlaier break; 834130365Smlaier } 835130365Smlaier 836130365Smlaier rqp->rq_ifq = &ifp->if_snd; 837130365Smlaier qtail(rqp->rq_q) = NULL; 838130365Smlaier qlen(rqp->rq_q) = 0; 839130365Smlaier qlimit(rqp->rq_q) = RED_LIMIT; 840130365Smlaier qtype(rqp->rq_q) = Q_RED; 841130365Smlaier 842130365Smlaier /* 843130365Smlaier * set RED to this ifnet structure. 844130365Smlaier */ 845130365Smlaier error = altq_attach(rqp->rq_ifq, ALTQT_RED, rqp, 846130365Smlaier red_enqueue, red_dequeue, red_request, 847130365Smlaier NULL, NULL); 848130365Smlaier if (error) { 849130365Smlaier red_destroy(rqp->rq_red); 850184205Sdes free(rqp->rq_q, M_DEVBUF); 851184205Sdes free(rqp, M_DEVBUF); 852130365Smlaier break; 853130365Smlaier } 854130365Smlaier 855130365Smlaier /* add this state to the red list */ 856130365Smlaier rqp->rq_next = red_list; 857130365Smlaier red_list = rqp; 858130365Smlaier break; 859130365Smlaier 860130365Smlaier case RED_IF_DETACH: 861130365Smlaier ifacep = (struct red_interface *)addr; 862130365Smlaier if ((rqp = altq_lookup(ifacep->red_ifname, ALTQT_RED)) == NULL) { 863130365Smlaier error = EBADF; 864130365Smlaier break; 865130365Smlaier } 866130365Smlaier error = red_detach(rqp); 867130365Smlaier break; 868130365Smlaier 869130365Smlaier case RED_GETSTATS: 870130365Smlaier do { 871130365Smlaier struct red_stats *q_stats; 872130365Smlaier red_t *rp; 873130365Smlaier 874130365Smlaier q_stats = (struct red_stats *)addr; 875130365Smlaier if ((rqp = altq_lookup(q_stats->iface.red_ifname, 876130365Smlaier ALTQT_RED)) == NULL) { 877130365Smlaier error = EBADF; 878130365Smlaier break; 879130365Smlaier } 880130365Smlaier 881130365Smlaier q_stats->q_len = qlen(rqp->rq_q); 882130365Smlaier q_stats->q_limit = qlimit(rqp->rq_q); 883130365Smlaier 884130365Smlaier rp = rqp->rq_red; 885130365Smlaier q_stats->q_avg = rp->red_avg >> rp->red_wshift; 886130365Smlaier q_stats->xmit_cnt = rp->red_stats.xmit_cnt; 887130365Smlaier q_stats->drop_cnt = rp->red_stats.drop_cnt; 888130365Smlaier q_stats->drop_forced = rp->red_stats.drop_forced; 889130365Smlaier q_stats->drop_unforced = rp->red_stats.drop_unforced; 890130365Smlaier q_stats->marked_packets = rp->red_stats.marked_packets; 891130365Smlaier 892130365Smlaier q_stats->weight = rp->red_weight; 893130365Smlaier q_stats->inv_pmax = rp->red_inv_pmax; 894130365Smlaier q_stats->th_min = rp->red_thmin; 895130365Smlaier q_stats->th_max = rp->red_thmax; 896130365Smlaier 897130365Smlaier#ifdef ALTQ_FLOWVALVE 898130365Smlaier if (rp->red_flowvalve != NULL) { 899130365Smlaier struct flowvalve *fv = rp->red_flowvalve; 900130365Smlaier q_stats->fv_flows = fv->fv_flows; 901130365Smlaier q_stats->fv_pass = fv->fv_stats.pass; 902130365Smlaier q_stats->fv_predrop = fv->fv_stats.predrop; 903130365Smlaier q_stats->fv_alloc = fv->fv_stats.alloc; 904130365Smlaier q_stats->fv_escape = fv->fv_stats.escape; 905130365Smlaier } else { 906130365Smlaier#endif /* ALTQ_FLOWVALVE */ 907130365Smlaier q_stats->fv_flows = 0; 908130365Smlaier q_stats->fv_pass = 0; 909130365Smlaier q_stats->fv_predrop = 0; 910130365Smlaier q_stats->fv_alloc = 0; 911130365Smlaier q_stats->fv_escape = 0; 912130365Smlaier#ifdef ALTQ_FLOWVALVE 913130365Smlaier } 914130365Smlaier#endif /* ALTQ_FLOWVALVE */ 915130365Smlaier } while (/*CONSTCOND*/ 0); 916130365Smlaier break; 917130365Smlaier 918130365Smlaier case RED_CONFIG: 919130365Smlaier do { 920130365Smlaier struct red_conf *fc; 921130365Smlaier red_t *new; 922130365Smlaier int s, limit; 923130365Smlaier 924130365Smlaier fc = (struct red_conf *)addr; 925130365Smlaier if ((rqp = altq_lookup(fc->iface.red_ifname, 926130365Smlaier ALTQT_RED)) == NULL) { 927130365Smlaier error = EBADF; 928130365Smlaier break; 929130365Smlaier } 930130365Smlaier new = red_alloc(fc->red_weight, 931130365Smlaier fc->red_inv_pmax, 932130365Smlaier fc->red_thmin, 933130365Smlaier fc->red_thmax, 934130365Smlaier fc->red_flags, 935130365Smlaier fc->red_pkttime); 936130365Smlaier if (new == NULL) { 937130365Smlaier error = ENOMEM; 938130365Smlaier break; 939130365Smlaier } 940130365Smlaier 941130365Smlaier#ifdef __NetBSD__ 942130365Smlaier s = splnet(); 943130365Smlaier#else 944130365Smlaier s = splimp(); 945130365Smlaier#endif 946130365Smlaier red_purgeq(rqp); 947130365Smlaier limit = fc->red_limit; 948130365Smlaier if (limit < fc->red_thmax) 949130365Smlaier limit = fc->red_thmax; 950130365Smlaier qlimit(rqp->rq_q) = limit; 951130365Smlaier fc->red_limit = limit; /* write back the new value */ 952130365Smlaier 953130365Smlaier red_destroy(rqp->rq_red); 954130365Smlaier rqp->rq_red = new; 955130365Smlaier 956130365Smlaier splx(s); 957130365Smlaier 958130365Smlaier /* write back new values */ 959130365Smlaier fc->red_limit = limit; 960130365Smlaier fc->red_inv_pmax = rqp->rq_red->red_inv_pmax; 961130365Smlaier fc->red_thmin = rqp->rq_red->red_thmin; 962130365Smlaier fc->red_thmax = rqp->rq_red->red_thmax; 963130365Smlaier 964130365Smlaier } while (/*CONSTCOND*/ 0); 965130365Smlaier break; 966130365Smlaier 967130365Smlaier case RED_SETDEFAULTS: 968130365Smlaier do { 969130365Smlaier struct redparams *rp; 970130365Smlaier 971130365Smlaier rp = (struct redparams *)addr; 972130365Smlaier 973130365Smlaier default_th_min = rp->th_min; 974130365Smlaier default_th_max = rp->th_max; 975130365Smlaier default_inv_pmax = rp->inv_pmax; 976130365Smlaier } while (/*CONSTCOND*/ 0); 977130365Smlaier break; 978130365Smlaier 979130365Smlaier default: 980130365Smlaier error = EINVAL; 981130365Smlaier break; 982130365Smlaier } 983130365Smlaier return error; 984130365Smlaier} 985130365Smlaier 986130365Smlaierstatic int 987130365Smlaierred_detach(rqp) 988130365Smlaier red_queue_t *rqp; 989130365Smlaier{ 990130365Smlaier red_queue_t *tmp; 991130365Smlaier int error = 0; 992130365Smlaier 993130365Smlaier if (ALTQ_IS_ENABLED(rqp->rq_ifq)) 994130365Smlaier altq_disable(rqp->rq_ifq); 995130365Smlaier 996130365Smlaier if ((error = altq_detach(rqp->rq_ifq))) 997130365Smlaier return (error); 998130365Smlaier 999130365Smlaier if (red_list == rqp) 1000130365Smlaier red_list = rqp->rq_next; 1001130365Smlaier else { 1002130365Smlaier for (tmp = red_list; tmp != NULL; tmp = tmp->rq_next) 1003130365Smlaier if (tmp->rq_next == rqp) { 1004130365Smlaier tmp->rq_next = rqp->rq_next; 1005130365Smlaier break; 1006130365Smlaier } 1007130365Smlaier if (tmp == NULL) 1008130365Smlaier printf("red_detach: no state found in red_list!\n"); 1009130365Smlaier } 1010130365Smlaier 1011130365Smlaier red_destroy(rqp->rq_red); 1012184205Sdes free(rqp->rq_q, M_DEVBUF); 1013184205Sdes free(rqp, M_DEVBUF); 1014130365Smlaier return (error); 1015130365Smlaier} 1016130365Smlaier 1017130365Smlaier/* 1018130365Smlaier * enqueue routine: 1019130365Smlaier * 1020130365Smlaier * returns: 0 when successfully queued. 1021130365Smlaier * ENOBUFS when drop occurs. 1022130365Smlaier */ 1023130365Smlaierstatic int 1024130365Smlaierred_enqueue(ifq, m, pktattr) 1025130365Smlaier struct ifaltq *ifq; 1026130365Smlaier struct mbuf *m; 1027130365Smlaier struct altq_pktattr *pktattr; 1028130365Smlaier{ 1029130365Smlaier red_queue_t *rqp = (red_queue_t *)ifq->altq_disc; 1030130365Smlaier 1031130368Smlaier IFQ_LOCK_ASSERT(ifq); 1032130368Smlaier 1033130365Smlaier if (red_addq(rqp->rq_red, rqp->rq_q, m, pktattr) < 0) 1034130365Smlaier return ENOBUFS; 1035130365Smlaier ifq->ifq_len++; 1036130365Smlaier return 0; 1037130365Smlaier} 1038130365Smlaier 1039130365Smlaier/* 1040130365Smlaier * dequeue routine: 1041130365Smlaier * must be called in splimp. 1042130365Smlaier * 1043130365Smlaier * returns: mbuf dequeued. 1044130365Smlaier * NULL when no packet is available in the queue. 1045130365Smlaier */ 1046130365Smlaier 1047130365Smlaierstatic struct mbuf * 1048130365Smlaierred_dequeue(ifq, op) 1049130365Smlaier struct ifaltq *ifq; 1050130365Smlaier int op; 1051130365Smlaier{ 1052130365Smlaier red_queue_t *rqp = (red_queue_t *)ifq->altq_disc; 1053130365Smlaier struct mbuf *m; 1054130365Smlaier 1055130368Smlaier IFQ_LOCK_ASSERT(ifq); 1056130368Smlaier 1057130365Smlaier if (op == ALTDQ_POLL) 1058130365Smlaier return qhead(rqp->rq_q); 1059130365Smlaier 1060130365Smlaier /* op == ALTDQ_REMOVE */ 1061130365Smlaier m = red_getq(rqp->rq_red, rqp->rq_q); 1062130365Smlaier if (m != NULL) 1063130365Smlaier ifq->ifq_len--; 1064130365Smlaier return (m); 1065130365Smlaier} 1066130365Smlaier 1067130365Smlaierstatic int 1068130365Smlaierred_request(ifq, req, arg) 1069130365Smlaier struct ifaltq *ifq; 1070130365Smlaier int req; 1071130365Smlaier void *arg; 1072130365Smlaier{ 1073130365Smlaier red_queue_t *rqp = (red_queue_t *)ifq->altq_disc; 1074130365Smlaier 1075130368Smlaier IFQ_LOCK_ASSERT(ifq); 1076130368Smlaier 1077130365Smlaier switch (req) { 1078130365Smlaier case ALTRQ_PURGE: 1079130365Smlaier red_purgeq(rqp); 1080130365Smlaier break; 1081130365Smlaier } 1082130365Smlaier return (0); 1083130365Smlaier} 1084130365Smlaier 1085130365Smlaierstatic void 1086130365Smlaierred_purgeq(rqp) 1087130365Smlaier red_queue_t *rqp; 1088130365Smlaier{ 1089130365Smlaier _flushq(rqp->rq_q); 1090130365Smlaier if (ALTQ_IS_ENABLED(rqp->rq_ifq)) 1091130365Smlaier rqp->rq_ifq->ifq_len = 0; 1092130365Smlaier} 1093130365Smlaier 1094130365Smlaier#ifdef ALTQ_FLOWVALVE 1095130365Smlaier 1096130365Smlaier#define FV_PSHIFT 7 /* weight of average drop rate -- 1/128 */ 1097130365Smlaier#define FV_PSCALE(x) ((x) << FV_PSHIFT) 1098130365Smlaier#define FV_PUNSCALE(x) ((x) >> FV_PSHIFT) 1099130365Smlaier#define FV_FSHIFT 5 /* weight of average fraction -- 1/32 */ 1100130365Smlaier#define FV_FSCALE(x) ((x) << FV_FSHIFT) 1101130365Smlaier#define FV_FUNSCALE(x) ((x) >> FV_FSHIFT) 1102130365Smlaier 1103130365Smlaier#define FV_TIMER (3 * hz) /* timer value for garbage collector */ 1104130365Smlaier#define FV_FLOWLISTSIZE 64 /* how many flows in flowlist */ 1105130365Smlaier 1106130365Smlaier#define FV_N 10 /* update fve_f every FV_N packets */ 1107130365Smlaier 1108130365Smlaier#define FV_BACKOFFTHRESH 1 /* backoff threshold interval in second */ 1109130365Smlaier#define FV_TTHRESH 3 /* time threshold to delete fve */ 1110130365Smlaier#define FV_ALPHA 5 /* extra packet count */ 1111130365Smlaier 1112130365Smlaier#define FV_STATS 1113130365Smlaier 1114130365Smlaier#if (__FreeBSD_version > 300000) 1115130365Smlaier#define FV_TIMESTAMP(tp) getmicrotime(tp) 1116130365Smlaier#else 1117130365Smlaier#define FV_TIMESTAMP(tp) { (*(tp)) = time; } 1118130365Smlaier#endif 1119130365Smlaier 1120130365Smlaier/* 1121130365Smlaier * Brtt table: 127 entry table to convert drop rate (p) to 1122130365Smlaier * the corresponding bandwidth fraction (f) 1123130365Smlaier * the following equation is implemented to use scaled values, 1124130365Smlaier * fve_p and fve_f, in the fixed point format. 1125130365Smlaier * 1126130365Smlaier * Brtt(p) = 1 /(sqrt(4*p/3) + min(1,3*sqrt(p*6/8)) * p * (1+32 * p*p)) 1127130365Smlaier * f = Brtt(p) / (max_th + alpha) 1128130365Smlaier */ 1129130365Smlaier#define BRTT_SIZE 128 1130130365Smlaier#define BRTT_SHIFT 12 1131130365Smlaier#define BRTT_MASK 0x0007f000 1132130365Smlaier#define BRTT_PMAX (1 << (FV_PSHIFT + FP_SHIFT)) 1133130365Smlaier 1134130365Smlaierconst int brtt_tab[BRTT_SIZE] = { 1135130365Smlaier 0, 1262010, 877019, 703694, 598706, 525854, 471107, 427728, 1136130365Smlaier 392026, 361788, 335598, 312506, 291850, 273158, 256081, 240361, 1137130365Smlaier 225800, 212247, 199585, 187788, 178388, 169544, 161207, 153333, 1138130365Smlaier 145888, 138841, 132165, 125836, 119834, 114141, 108739, 103612, 1139130365Smlaier 98747, 94129, 89746, 85585, 81637, 77889, 74333, 70957, 1140130365Smlaier 67752, 64711, 61824, 59084, 56482, 54013, 51667, 49440, 1141130365Smlaier 47325, 45315, 43406, 41591, 39866, 38227, 36667, 35184, 1142130365Smlaier 33773, 32430, 31151, 29933, 28774, 27668, 26615, 25611, 1143130365Smlaier 24653, 23740, 22868, 22035, 21240, 20481, 19755, 19062, 1144130365Smlaier 18399, 17764, 17157, 16576, 16020, 15487, 14976, 14487, 1145130365Smlaier 14017, 13567, 13136, 12721, 12323, 11941, 11574, 11222, 1146130365Smlaier 10883, 10557, 10243, 9942, 9652, 9372, 9103, 8844, 1147130365Smlaier 8594, 8354, 8122, 7898, 7682, 7474, 7273, 7079, 1148130365Smlaier 6892, 6711, 6536, 6367, 6204, 6046, 5893, 5746, 1149130365Smlaier 5603, 5464, 5330, 5201, 5075, 4954, 4836, 4722, 1150130365Smlaier 4611, 4504, 4400, 4299, 4201, 4106, 4014, 3924 1151130365Smlaier}; 1152130365Smlaier 1153130365Smlaierstatic __inline struct fve * 1154130365Smlaierflowlist_lookup(fv, pktattr, now) 1155130365Smlaier struct flowvalve *fv; 1156130365Smlaier struct altq_pktattr *pktattr; 1157130365Smlaier struct timeval *now; 1158130365Smlaier{ 1159130365Smlaier struct fve *fve; 1160130365Smlaier int flows; 1161130365Smlaier struct ip *ip; 1162130365Smlaier#ifdef INET6 1163130365Smlaier struct ip6_hdr *ip6; 1164130365Smlaier#endif 1165130365Smlaier struct timeval tthresh; 1166130365Smlaier 1167130365Smlaier if (pktattr == NULL) 1168130365Smlaier return (NULL); 1169130365Smlaier 1170130365Smlaier tthresh.tv_sec = now->tv_sec - FV_TTHRESH; 1171130365Smlaier flows = 0; 1172130365Smlaier /* 1173130365Smlaier * search the flow list 1174130365Smlaier */ 1175130365Smlaier switch (pktattr->pattr_af) { 1176130365Smlaier case AF_INET: 1177130365Smlaier ip = (struct ip *)pktattr->pattr_hdr; 1178130365Smlaier TAILQ_FOREACH(fve, &fv->fv_flowlist, fve_lru){ 1179130365Smlaier if (fve->fve_lastdrop.tv_sec == 0) 1180130365Smlaier break; 1181130365Smlaier if (fve->fve_lastdrop.tv_sec < tthresh.tv_sec) { 1182130365Smlaier fve->fve_lastdrop.tv_sec = 0; 1183130365Smlaier break; 1184130365Smlaier } 1185130365Smlaier if (fve->fve_flow.flow_af == AF_INET && 1186130365Smlaier fve->fve_flow.flow_ip.ip_src.s_addr == 1187130365Smlaier ip->ip_src.s_addr && 1188130365Smlaier fve->fve_flow.flow_ip.ip_dst.s_addr == 1189130365Smlaier ip->ip_dst.s_addr) 1190130365Smlaier return (fve); 1191130365Smlaier flows++; 1192130365Smlaier } 1193130365Smlaier break; 1194130365Smlaier#ifdef INET6 1195130365Smlaier case AF_INET6: 1196130365Smlaier ip6 = (struct ip6_hdr *)pktattr->pattr_hdr; 1197130365Smlaier TAILQ_FOREACH(fve, &fv->fv_flowlist, fve_lru){ 1198130365Smlaier if (fve->fve_lastdrop.tv_sec == 0) 1199130365Smlaier break; 1200130365Smlaier if (fve->fve_lastdrop.tv_sec < tthresh.tv_sec) { 1201130365Smlaier fve->fve_lastdrop.tv_sec = 0; 1202130365Smlaier break; 1203130365Smlaier } 1204130365Smlaier if (fve->fve_flow.flow_af == AF_INET6 && 1205130365Smlaier IN6_ARE_ADDR_EQUAL(&fve->fve_flow.flow_ip6.ip6_src, 1206130365Smlaier &ip6->ip6_src) && 1207130365Smlaier IN6_ARE_ADDR_EQUAL(&fve->fve_flow.flow_ip6.ip6_dst, 1208130365Smlaier &ip6->ip6_dst)) 1209130365Smlaier return (fve); 1210130365Smlaier flows++; 1211130365Smlaier } 1212130365Smlaier break; 1213130365Smlaier#endif /* INET6 */ 1214130365Smlaier 1215130365Smlaier default: 1216130365Smlaier /* unknown protocol. no drop. */ 1217130365Smlaier return (NULL); 1218130365Smlaier } 1219130365Smlaier fv->fv_flows = flows; /* save the number of active fve's */ 1220130365Smlaier return (NULL); 1221130365Smlaier} 1222130365Smlaier 1223130365Smlaierstatic __inline struct fve * 1224130365Smlaierflowlist_reclaim(fv, pktattr) 1225130365Smlaier struct flowvalve *fv; 1226130365Smlaier struct altq_pktattr *pktattr; 1227130365Smlaier{ 1228130365Smlaier struct fve *fve; 1229130365Smlaier struct ip *ip; 1230130365Smlaier#ifdef INET6 1231130365Smlaier struct ip6_hdr *ip6; 1232130365Smlaier#endif 1233130365Smlaier 1234130365Smlaier /* 1235130365Smlaier * get an entry from the tail of the LRU list. 1236130365Smlaier */ 1237130365Smlaier fve = TAILQ_LAST(&fv->fv_flowlist, fv_flowhead); 1238130365Smlaier 1239130365Smlaier switch (pktattr->pattr_af) { 1240130365Smlaier case AF_INET: 1241130365Smlaier ip = (struct ip *)pktattr->pattr_hdr; 1242130365Smlaier fve->fve_flow.flow_af = AF_INET; 1243130365Smlaier fve->fve_flow.flow_ip.ip_src = ip->ip_src; 1244130365Smlaier fve->fve_flow.flow_ip.ip_dst = ip->ip_dst; 1245130365Smlaier break; 1246130365Smlaier#ifdef INET6 1247130365Smlaier case AF_INET6: 1248130365Smlaier ip6 = (struct ip6_hdr *)pktattr->pattr_hdr; 1249130365Smlaier fve->fve_flow.flow_af = AF_INET6; 1250130365Smlaier fve->fve_flow.flow_ip6.ip6_src = ip6->ip6_src; 1251130365Smlaier fve->fve_flow.flow_ip6.ip6_dst = ip6->ip6_dst; 1252130365Smlaier break; 1253130365Smlaier#endif 1254130365Smlaier } 1255130365Smlaier 1256130365Smlaier fve->fve_state = Green; 1257130365Smlaier fve->fve_p = 0.0; 1258130365Smlaier fve->fve_f = 0.0; 1259130365Smlaier fve->fve_ifseq = fv->fv_ifseq - 1; 1260130365Smlaier fve->fve_count = 0; 1261130365Smlaier 1262130365Smlaier fv->fv_flows++; 1263130365Smlaier#ifdef FV_STATS 1264130365Smlaier fv->fv_stats.alloc++; 1265130365Smlaier#endif 1266130365Smlaier return (fve); 1267130365Smlaier} 1268130365Smlaier 1269130365Smlaierstatic __inline void 1270130365Smlaierflowlist_move_to_head(fv, fve) 1271130365Smlaier struct flowvalve *fv; 1272130365Smlaier struct fve *fve; 1273130365Smlaier{ 1274130365Smlaier if (TAILQ_FIRST(&fv->fv_flowlist) != fve) { 1275130365Smlaier TAILQ_REMOVE(&fv->fv_flowlist, fve, fve_lru); 1276130365Smlaier TAILQ_INSERT_HEAD(&fv->fv_flowlist, fve, fve_lru); 1277130365Smlaier } 1278130365Smlaier} 1279130365Smlaier 1280130368Smlaier#if 0 /* XXX: make the compiler happy (fv_alloc unused) */ 1281130365Smlaier/* 1282130365Smlaier * allocate flowvalve structure 1283130365Smlaier */ 1284130365Smlaierstatic struct flowvalve * 1285130365Smlaierfv_alloc(rp) 1286130365Smlaier struct red *rp; 1287130365Smlaier{ 1288130365Smlaier struct flowvalve *fv; 1289130365Smlaier struct fve *fve; 1290130365Smlaier int i, num; 1291130365Smlaier 1292130365Smlaier num = FV_FLOWLISTSIZE; 1293184205Sdes fv = malloc(sizeof(struct flowvalve), 1294130365Smlaier M_DEVBUF, M_WAITOK); 1295130365Smlaier if (fv == NULL) 1296130365Smlaier return (NULL); 1297130365Smlaier bzero(fv, sizeof(struct flowvalve)); 1298130365Smlaier 1299184205Sdes fv->fv_fves = malloc(sizeof(struct fve) * num, 1300130365Smlaier M_DEVBUF, M_WAITOK); 1301130365Smlaier if (fv->fv_fves == NULL) { 1302184205Sdes free(fv, M_DEVBUF); 1303130365Smlaier return (NULL); 1304130365Smlaier } 1305130365Smlaier bzero(fv->fv_fves, sizeof(struct fve) * num); 1306130365Smlaier 1307130365Smlaier fv->fv_flows = 0; 1308130365Smlaier TAILQ_INIT(&fv->fv_flowlist); 1309130365Smlaier for (i = 0; i < num; i++) { 1310130365Smlaier fve = &fv->fv_fves[i]; 1311130365Smlaier fve->fve_lastdrop.tv_sec = 0; 1312130365Smlaier TAILQ_INSERT_TAIL(&fv->fv_flowlist, fve, fve_lru); 1313130365Smlaier } 1314130365Smlaier 1315130365Smlaier /* initialize drop rate threshold in scaled fixed-point */ 1316130365Smlaier fv->fv_pthresh = (FV_PSCALE(1) << FP_SHIFT) / rp->red_inv_pmax; 1317130365Smlaier 1318130365Smlaier /* initialize drop rate to fraction table */ 1319184205Sdes fv->fv_p2ftab = malloc(sizeof(int) * BRTT_SIZE, 1320130365Smlaier M_DEVBUF, M_WAITOK); 1321130365Smlaier if (fv->fv_p2ftab == NULL) { 1322184205Sdes free(fv->fv_fves, M_DEVBUF); 1323184205Sdes free(fv, M_DEVBUF); 1324130365Smlaier return (NULL); 1325130365Smlaier } 1326130365Smlaier /* 1327130365Smlaier * create the p2f table. 1328130365Smlaier * (shift is used to keep the precision) 1329130365Smlaier */ 1330130365Smlaier for (i = 1; i < BRTT_SIZE; i++) { 1331130365Smlaier int f; 1332130365Smlaier 1333130365Smlaier f = brtt_tab[i] << 8; 1334130365Smlaier fv->fv_p2ftab[i] = (f / (rp->red_thmax + FV_ALPHA)) >> 8; 1335130365Smlaier } 1336130365Smlaier 1337130365Smlaier return (fv); 1338130365Smlaier} 1339130368Smlaier#endif 1340130365Smlaier 1341130365Smlaierstatic void fv_destroy(fv) 1342130365Smlaier struct flowvalve *fv; 1343130365Smlaier{ 1344184205Sdes free(fv->fv_p2ftab, M_DEVBUF); 1345184205Sdes free(fv->fv_fves, M_DEVBUF); 1346184205Sdes free(fv, M_DEVBUF); 1347130365Smlaier} 1348130365Smlaier 1349130365Smlaierstatic __inline int 1350130365Smlaierfv_p2f(fv, p) 1351130365Smlaier struct flowvalve *fv; 1352130365Smlaier int p; 1353130365Smlaier{ 1354130365Smlaier int val, f; 1355130365Smlaier 1356130365Smlaier if (p >= BRTT_PMAX) 1357130365Smlaier f = fv->fv_p2ftab[BRTT_SIZE-1]; 1358130365Smlaier else if ((val = (p & BRTT_MASK))) 1359130365Smlaier f = fv->fv_p2ftab[(val >> BRTT_SHIFT)]; 1360130365Smlaier else 1361130365Smlaier f = fv->fv_p2ftab[1]; 1362130365Smlaier return (f); 1363130365Smlaier} 1364130365Smlaier 1365130365Smlaier/* 1366130365Smlaier * check if an arriving packet should be pre-dropped. 1367130365Smlaier * called from red_addq() when a packet arrives. 1368130365Smlaier * returns 1 when the packet should be pre-dropped. 1369130365Smlaier * should be called in splimp. 1370130365Smlaier */ 1371130365Smlaierstatic int 1372130365Smlaierfv_checkflow(fv, pktattr, fcache) 1373130365Smlaier struct flowvalve *fv; 1374130365Smlaier struct altq_pktattr *pktattr; 1375130365Smlaier struct fve **fcache; 1376130365Smlaier{ 1377130365Smlaier struct fve *fve; 1378130365Smlaier struct timeval now; 1379130365Smlaier 1380130365Smlaier fv->fv_ifseq++; 1381130365Smlaier FV_TIMESTAMP(&now); 1382130365Smlaier 1383130365Smlaier if ((fve = flowlist_lookup(fv, pktattr, &now)) == NULL) 1384130365Smlaier /* no matching entry in the flowlist */ 1385130365Smlaier return (0); 1386130365Smlaier 1387130365Smlaier *fcache = fve; 1388130365Smlaier 1389130365Smlaier /* update fraction f for every FV_N packets */ 1390130365Smlaier if (++fve->fve_count == FV_N) { 1391130365Smlaier /* 1392130365Smlaier * f = Wf * N / (fv_ifseq - fve_ifseq) + (1 - Wf) * f 1393130365Smlaier */ 1394130365Smlaier fve->fve_f = 1395130365Smlaier (FV_N << FP_SHIFT) / (fv->fv_ifseq - fve->fve_ifseq) 1396130365Smlaier + fve->fve_f - FV_FUNSCALE(fve->fve_f); 1397130365Smlaier fve->fve_ifseq = fv->fv_ifseq; 1398130365Smlaier fve->fve_count = 0; 1399130365Smlaier } 1400130365Smlaier 1401130365Smlaier /* 1402130365Smlaier * overpumping test 1403130365Smlaier */ 1404130365Smlaier if (fve->fve_state == Green && fve->fve_p > fv->fv_pthresh) { 1405130365Smlaier int fthresh; 1406130365Smlaier 1407130365Smlaier /* calculate a threshold */ 1408130365Smlaier fthresh = fv_p2f(fv, fve->fve_p); 1409130365Smlaier if (fve->fve_f > fthresh) 1410130365Smlaier fve->fve_state = Red; 1411130365Smlaier } 1412130365Smlaier 1413130365Smlaier if (fve->fve_state == Red) { 1414130365Smlaier /* 1415130365Smlaier * backoff test 1416130365Smlaier */ 1417130365Smlaier if (now.tv_sec - fve->fve_lastdrop.tv_sec > FV_BACKOFFTHRESH) { 1418130365Smlaier /* no drop for at least FV_BACKOFFTHRESH sec */ 1419130365Smlaier fve->fve_p = 0; 1420130365Smlaier fve->fve_state = Green; 1421130365Smlaier#ifdef FV_STATS 1422130365Smlaier fv->fv_stats.escape++; 1423130365Smlaier#endif 1424130365Smlaier } else { 1425130365Smlaier /* block this flow */ 1426130365Smlaier flowlist_move_to_head(fv, fve); 1427130365Smlaier fve->fve_lastdrop = now; 1428130365Smlaier#ifdef FV_STATS 1429130365Smlaier fv->fv_stats.predrop++; 1430130365Smlaier#endif 1431130365Smlaier return (1); 1432130365Smlaier } 1433130365Smlaier } 1434130365Smlaier 1435130365Smlaier /* 1436130365Smlaier * p = (1 - Wp) * p 1437130365Smlaier */ 1438130365Smlaier fve->fve_p -= FV_PUNSCALE(fve->fve_p); 1439130365Smlaier if (fve->fve_p < 0) 1440130365Smlaier fve->fve_p = 0; 1441130365Smlaier#ifdef FV_STATS 1442130365Smlaier fv->fv_stats.pass++; 1443130365Smlaier#endif 1444130365Smlaier return (0); 1445130365Smlaier} 1446130365Smlaier 1447130365Smlaier/* 1448130365Smlaier * called from red_addq when a packet is dropped by red. 1449130365Smlaier * should be called in splimp. 1450130365Smlaier */ 1451130365Smlaierstatic void fv_dropbyred(fv, pktattr, fcache) 1452130365Smlaier struct flowvalve *fv; 1453130365Smlaier struct altq_pktattr *pktattr; 1454130365Smlaier struct fve *fcache; 1455130365Smlaier{ 1456130365Smlaier struct fve *fve; 1457130365Smlaier struct timeval now; 1458130365Smlaier 1459130365Smlaier if (pktattr == NULL) 1460130365Smlaier return; 1461130365Smlaier FV_TIMESTAMP(&now); 1462130365Smlaier 1463130365Smlaier if (fcache != NULL) 1464130365Smlaier /* the fve of this packet is already cached */ 1465130365Smlaier fve = fcache; 1466130365Smlaier else if ((fve = flowlist_lookup(fv, pktattr, &now)) == NULL) 1467130365Smlaier fve = flowlist_reclaim(fv, pktattr); 1468130365Smlaier 1469130365Smlaier flowlist_move_to_head(fv, fve); 1470130365Smlaier 1471130365Smlaier /* 1472130365Smlaier * update p: the following line cancels the update 1473130365Smlaier * in fv_checkflow() and calculate 1474130365Smlaier * p = Wp + (1 - Wp) * p 1475130365Smlaier */ 1476130365Smlaier fve->fve_p = (1 << FP_SHIFT) + fve->fve_p; 1477130365Smlaier 1478130365Smlaier fve->fve_lastdrop = now; 1479130365Smlaier} 1480130365Smlaier 1481130365Smlaier#endif /* ALTQ_FLOWVALVE */ 1482130365Smlaier 1483130365Smlaier#ifdef KLD_MODULE 1484130365Smlaier 1485130365Smlaierstatic struct altqsw red_sw = 1486130365Smlaier {"red", redopen, redclose, redioctl}; 1487130365Smlaier 1488130365SmlaierALTQ_MODULE(altq_red, ALTQT_RED, &red_sw); 1489130365SmlaierMODULE_VERSION(altq_red, 1); 1490130365Smlaier 1491130365Smlaier#endif /* KLD_MODULE */ 1492130365Smlaier#endif /* ALTQ3_COMPAT */ 1493130365Smlaier 1494130365Smlaier#endif /* ALTQ_RED */ 1495