altq_red.c revision 1.2.2.2
1 1.2.2.2 bouyer /* $NetBSD: altq_red.c,v 1.2.2.2 2001/01/05 17:39:37 bouyer Exp $ */ 2 1.2.2.2 bouyer /* $KAME: altq_red.c,v 1.8 2000/12/14 08:12:46 thorpej Exp $ */ 3 1.2.2.2 bouyer 4 1.2.2.2 bouyer /* 5 1.2.2.2 bouyer * Copyright (C) 1997-2000 6 1.2.2.2 bouyer * Sony Computer Science Laboratories Inc. All rights reserved. 7 1.2.2.2 bouyer * 8 1.2.2.2 bouyer * Redistribution and use in source and binary forms, with or without 9 1.2.2.2 bouyer * modification, are permitted provided that the following conditions 10 1.2.2.2 bouyer * are met: 11 1.2.2.2 bouyer * 1. Redistributions of source code must retain the above copyright 12 1.2.2.2 bouyer * notice, this list of conditions and the following disclaimer. 13 1.2.2.2 bouyer * 2. Redistributions in binary form must reproduce the above copyright 14 1.2.2.2 bouyer * notice, this list of conditions and the following disclaimer in the 15 1.2.2.2 bouyer * documentation and/or other materials provided with the distribution. 16 1.2.2.2 bouyer * 17 1.2.2.2 bouyer * THIS SOFTWARE IS PROVIDED BY SONY CSL AND CONTRIBUTORS ``AS IS'' AND 18 1.2.2.2 bouyer * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 1.2.2.2 bouyer * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20 1.2.2.2 bouyer * ARE DISCLAIMED. IN NO EVENT SHALL SONY CSL OR CONTRIBUTORS BE LIABLE 21 1.2.2.2 bouyer * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22 1.2.2.2 bouyer * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23 1.2.2.2 bouyer * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24 1.2.2.2 bouyer * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25 1.2.2.2 bouyer * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26 1.2.2.2 bouyer * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27 1.2.2.2 bouyer * SUCH DAMAGE. 28 1.2.2.2 bouyer * 29 1.2.2.2 bouyer */ 30 1.2.2.2 bouyer /* 31 1.2.2.2 bouyer * Copyright (c) 1990-1994 Regents of the University of California. 32 1.2.2.2 bouyer * All rights reserved. 33 1.2.2.2 bouyer * 34 1.2.2.2 bouyer * Redistribution and use in source and binary forms, with or without 35 1.2.2.2 bouyer * modification, are permitted provided that the following conditions 36 1.2.2.2 bouyer * are met: 37 1.2.2.2 bouyer * 1. Redistributions of source code must retain the above copyright 38 1.2.2.2 bouyer * notice, this list of conditions and the following disclaimer. 39 1.2.2.2 bouyer * 2. Redistributions in binary form must reproduce the above copyright 40 1.2.2.2 bouyer * notice, this list of conditions and the following disclaimer in the 41 1.2.2.2 bouyer * documentation and/or other materials provided with the distribution. 42 1.2.2.2 bouyer * 3. All advertising materials mentioning features or use of this software 43 1.2.2.2 bouyer * must display the following acknowledgement: 44 1.2.2.2 bouyer * This product includes software developed by the Computer Systems 45 1.2.2.2 bouyer * Engineering Group at Lawrence Berkeley Laboratory. 46 1.2.2.2 bouyer * 4. Neither the name of the University nor of the Laboratory may be used 47 1.2.2.2 bouyer * to endorse or promote products derived from this software without 48 1.2.2.2 bouyer * specific prior written permission. 49 1.2.2.2 bouyer * 50 1.2.2.2 bouyer * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 51 1.2.2.2 bouyer * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 52 1.2.2.2 bouyer * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 53 1.2.2.2 bouyer * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 54 1.2.2.2 bouyer * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 55 1.2.2.2 bouyer * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 56 1.2.2.2 bouyer * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 57 1.2.2.2 bouyer * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 58 1.2.2.2 bouyer * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 59 1.2.2.2 bouyer * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 60 1.2.2.2 bouyer * SUCH DAMAGE. 61 1.2.2.2 bouyer */ 62 1.2.2.2 bouyer 63 1.2.2.2 bouyer #if defined(__FreeBSD__) || defined(__NetBSD__) 64 1.2.2.2 bouyer #include "opt_altq.h" 65 1.2.2.2 bouyer #if (__FreeBSD__ != 2) 66 1.2.2.2 bouyer #include "opt_inet.h" 67 1.2.2.2 bouyer #ifdef __FreeBSD__ 68 1.2.2.2 bouyer #include "opt_inet6.h" 69 1.2.2.2 bouyer #endif 70 1.2.2.2 bouyer #endif 71 1.2.2.2 bouyer #endif /* __FreeBSD__ || __NetBSD__ */ 72 1.2.2.2 bouyer #ifdef ALTQ_RED /* red is enabled by ALTQ_RED option in opt_altq.h */ 73 1.2.2.2 bouyer 74 1.2.2.2 bouyer #include <sys/param.h> 75 1.2.2.2 bouyer #include <sys/malloc.h> 76 1.2.2.2 bouyer #include <sys/mbuf.h> 77 1.2.2.2 bouyer #include <sys/socket.h> 78 1.2.2.2 bouyer #include <sys/sockio.h> 79 1.2.2.2 bouyer #include <sys/systm.h> 80 1.2.2.2 bouyer #include <sys/proc.h> 81 1.2.2.2 bouyer #include <sys/errno.h> 82 1.2.2.2 bouyer #include <sys/kernel.h> 83 1.2.2.2 bouyer #ifdef ALTQ_FLOWVALVE 84 1.2.2.2 bouyer #include <sys/queue.h> 85 1.2.2.2 bouyer #include <sys/time.h> 86 1.2.2.2 bouyer #endif 87 1.2.2.2 bouyer 88 1.2.2.2 bouyer #include <net/if.h> 89 1.2.2.2 bouyer #include <net/if_types.h> 90 1.2.2.2 bouyer 91 1.2.2.2 bouyer #include <netinet/in.h> 92 1.2.2.2 bouyer #include <netinet/in_systm.h> 93 1.2.2.2 bouyer #include <netinet/ip.h> 94 1.2.2.2 bouyer #ifdef INET6 95 1.2.2.2 bouyer #include <netinet/ip6.h> 96 1.2.2.2 bouyer #endif 97 1.2.2.2 bouyer 98 1.2.2.2 bouyer #include <altq/altq.h> 99 1.2.2.2 bouyer #include <altq/altq_conf.h> 100 1.2.2.2 bouyer #include <altq/altq_red.h> 101 1.2.2.2 bouyer #ifdef ALTQ_FLOWVALVE 102 1.2.2.2 bouyer #include <altq/altq_flowvalve.h> 103 1.2.2.2 bouyer #endif 104 1.2.2.2 bouyer 105 1.2.2.2 bouyer /* 106 1.2.2.2 bouyer * ALTQ/RED (Random Early Detection) implementation using 32-bit 107 1.2.2.2 bouyer * fixed-point calculation. 108 1.2.2.2 bouyer * 109 1.2.2.2 bouyer * written by kjc using the ns code as a reference. 110 1.2.2.2 bouyer * you can learn more about red and ns from Sally's home page at 111 1.2.2.2 bouyer * http://www-nrg.ee.lbl.gov/floyd/ 112 1.2.2.2 bouyer * 113 1.2.2.2 bouyer * most of the red parameter values are fixed in this implementation 114 1.2.2.2 bouyer * to prevent fixed-point overflow/underflow. 115 1.2.2.2 bouyer * if you change the parameters, watch out for overflow/underflow! 116 1.2.2.2 bouyer * 117 1.2.2.2 bouyer * the parameters used are recommended values by Sally. 118 1.2.2.2 bouyer * the corresponding ns config looks: 119 1.2.2.2 bouyer * q_weight=0.00195 120 1.2.2.2 bouyer * minthresh=5 maxthresh=15 queue-size=60 121 1.2.2.2 bouyer * linterm=30 122 1.2.2.2 bouyer * dropmech=drop-tail 123 1.2.2.2 bouyer * bytes=false (can't be handled by 32-bit fixed-point) 124 1.2.2.2 bouyer * doubleq=false dqthresh=false 125 1.2.2.2 bouyer * wait=true 126 1.2.2.2 bouyer */ 127 1.2.2.2 bouyer /* 128 1.2.2.2 bouyer * alternative red parameters for a slow link. 129 1.2.2.2 bouyer * 130 1.2.2.2 bouyer * assume the queue length becomes from zero to L and keeps L, it takes 131 1.2.2.2 bouyer * N packets for q_avg to reach 63% of L. 132 1.2.2.2 bouyer * when q_weight is 0.002, N is about 500 packets. 133 1.2.2.2 bouyer * for a slow link like dial-up, 500 packets takes more than 1 minute! 134 1.2.2.2 bouyer * when q_weight is 0.008, N is about 127 packets. 135 1.2.2.2 bouyer * when q_weight is 0.016, N is about 63 packets. 136 1.2.2.2 bouyer * bursts of 50 packets are allowd for 0.002, bursts of 25 packets 137 1.2.2.2 bouyer * are allowed for 0.016. 138 1.2.2.2 bouyer * see Sally's paper for more details. 139 1.2.2.2 bouyer */ 140 1.2.2.2 bouyer /* normal red parameters */ 141 1.2.2.2 bouyer #define W_WEIGHT 512 /* inverse of weight of EWMA (511/512) */ 142 1.2.2.2 bouyer /* q_weight = 0.00195 */ 143 1.2.2.2 bouyer 144 1.2.2.2 bouyer /* red parameters for a slow link */ 145 1.2.2.2 bouyer #define W_WEIGHT_1 128 /* inverse of weight of EWMA (127/128) */ 146 1.2.2.2 bouyer /* q_weight = 0.0078125 */ 147 1.2.2.2 bouyer 148 1.2.2.2 bouyer /* red parameters for a very slow link (e.g., dialup) */ 149 1.2.2.2 bouyer #define W_WEIGHT_2 64 /* inverse of weight of EWMA (63/64) */ 150 1.2.2.2 bouyer /* q_weight = 0.015625 */ 151 1.2.2.2 bouyer 152 1.2.2.2 bouyer /* fixed-point uses 12-bit decimal places */ 153 1.2.2.2 bouyer #define FP_SHIFT 12 /* fixed-point shift */ 154 1.2.2.2 bouyer 155 1.2.2.2 bouyer /* red parameters for drop probability */ 156 1.2.2.2 bouyer #define INV_P_MAX 10 /* inverse of max drop probability */ 157 1.2.2.2 bouyer #define TH_MIN 5 /* min threshold */ 158 1.2.2.2 bouyer #define TH_MAX 15 /* max threshold */ 159 1.2.2.2 bouyer 160 1.2.2.2 bouyer #define RED_LIMIT 60 /* default max queue lenght */ 161 1.2.2.2 bouyer #define RED_STATS /* collect statistics */ 162 1.2.2.2 bouyer 163 1.2.2.2 bouyer /* 164 1.2.2.2 bouyer * our default policy for forced-drop is drop-tail. 165 1.2.2.2 bouyer * (in altq-1.1.2 or earlier, the default was random-drop. 166 1.2.2.2 bouyer * but it makes more sense to punish the cause of the surge.) 167 1.2.2.2 bouyer * to switch to the random-drop policy, define "RED_RANDOM_DROP". 168 1.2.2.2 bouyer */ 169 1.2.2.2 bouyer 170 1.2.2.2 bouyer #ifdef ALTQ_FLOWVALVE 171 1.2.2.2 bouyer /* 172 1.2.2.2 bouyer * flow-valve is an extention to protect red from unresponsive flows 173 1.2.2.2 bouyer * and to promote end-to-end congestion control. 174 1.2.2.2 bouyer * flow-valve observes the average drop rates of the flows that have 175 1.2.2.2 bouyer * experienced packet drops in the recent past. 176 1.2.2.2 bouyer * when the average drop rate exceeds the threshold, the flow is 177 1.2.2.2 bouyer * blocked by the flow-valve. the trapped flow should back off 178 1.2.2.2 bouyer * exponentially to escape from the flow-valve. 179 1.2.2.2 bouyer */ 180 1.2.2.2 bouyer #ifdef RED_RANDOM_DROP 181 1.2.2.2 bouyer #error "random-drop can't be used with flow-valve!" 182 1.2.2.2 bouyer #endif 183 1.2.2.2 bouyer #endif /* ALTQ_FLOWVALVE */ 184 1.2.2.2 bouyer 185 1.2.2.2 bouyer /* red_list keeps all red_queue_t's allocated. */ 186 1.2.2.2 bouyer static red_queue_t *red_list = NULL; 187 1.2.2.2 bouyer 188 1.2.2.2 bouyer /* default red parameter values */ 189 1.2.2.2 bouyer static int default_th_min = TH_MIN; 190 1.2.2.2 bouyer static int default_th_max = TH_MAX; 191 1.2.2.2 bouyer static int default_inv_pmax = INV_P_MAX; 192 1.2.2.2 bouyer 193 1.2.2.2 bouyer /* internal function prototypes */ 194 1.2.2.2 bouyer static int red_enqueue __P((struct ifaltq *, struct mbuf *, 195 1.2.2.2 bouyer struct altq_pktattr *)); 196 1.2.2.2 bouyer static struct mbuf *red_dequeue __P((struct ifaltq *, int)); 197 1.2.2.2 bouyer static int red_request __P((struct ifaltq *, int, void *)); 198 1.2.2.2 bouyer static void red_purgeq __P((red_queue_t *)); 199 1.2.2.2 bouyer static int red_detach __P((red_queue_t *)); 200 1.2.2.2 bouyer #ifdef ALTQ_FLOWVALVE 201 1.2.2.2 bouyer static __inline struct fve *flowlist_lookup __P((struct flowvalve *, 202 1.2.2.2 bouyer struct altq_pktattr *, struct timeval *)); 203 1.2.2.2 bouyer static __inline struct fve *flowlist_reclaim __P((struct flowvalve *, 204 1.2.2.2 bouyer struct altq_pktattr *)); 205 1.2.2.2 bouyer static __inline void flowlist_move_to_head __P((struct flowvalve *, 206 1.2.2.2 bouyer struct fve *)); 207 1.2.2.2 bouyer static __inline int fv_p2f __P((struct flowvalve *, int)); 208 1.2.2.2 bouyer static struct flowvalve *fv_alloc __P((struct red *)); 209 1.2.2.2 bouyer static void fv_destroy __P((struct flowvalve *)); 210 1.2.2.2 bouyer static int fv_checkflow __P((struct flowvalve *, struct altq_pktattr *, 211 1.2.2.2 bouyer struct fve **)); 212 1.2.2.2 bouyer static void fv_dropbyred __P((struct flowvalve *fv, struct altq_pktattr *, 213 1.2.2.2 bouyer struct fve *)); 214 1.2.2.2 bouyer #endif 215 1.2.2.2 bouyer 216 1.2.2.2 bouyer /* 217 1.2.2.2 bouyer * red device interface 218 1.2.2.2 bouyer */ 219 1.2.2.2 bouyer altqdev_decl(red); 220 1.2.2.2 bouyer 221 1.2.2.2 bouyer int 222 1.2.2.2 bouyer redopen(dev, flag, fmt, p) 223 1.2.2.2 bouyer dev_t dev; 224 1.2.2.2 bouyer int flag, fmt; 225 1.2.2.2 bouyer struct proc *p; 226 1.2.2.2 bouyer { 227 1.2.2.2 bouyer /* everything will be done when the queueing scheme is attached. */ 228 1.2.2.2 bouyer return 0; 229 1.2.2.2 bouyer } 230 1.2.2.2 bouyer 231 1.2.2.2 bouyer int 232 1.2.2.2 bouyer redclose(dev, flag, fmt, p) 233 1.2.2.2 bouyer dev_t dev; 234 1.2.2.2 bouyer int flag, fmt; 235 1.2.2.2 bouyer struct proc *p; 236 1.2.2.2 bouyer { 237 1.2.2.2 bouyer red_queue_t *rqp; 238 1.2.2.2 bouyer int err, error = 0; 239 1.2.2.2 bouyer 240 1.2.2.2 bouyer while ((rqp = red_list) != NULL) { 241 1.2.2.2 bouyer /* destroy all */ 242 1.2.2.2 bouyer err = red_detach(rqp); 243 1.2.2.2 bouyer if (err != 0 && error == 0) 244 1.2.2.2 bouyer error = err; 245 1.2.2.2 bouyer } 246 1.2.2.2 bouyer 247 1.2.2.2 bouyer return error; 248 1.2.2.2 bouyer } 249 1.2.2.2 bouyer 250 1.2.2.2 bouyer int 251 1.2.2.2 bouyer redioctl(dev, cmd, addr, flag, p) 252 1.2.2.2 bouyer dev_t dev; 253 1.2.2.2 bouyer ioctlcmd_t cmd; 254 1.2.2.2 bouyer caddr_t addr; 255 1.2.2.2 bouyer int flag; 256 1.2.2.2 bouyer struct proc *p; 257 1.2.2.2 bouyer { 258 1.2.2.2 bouyer red_queue_t *rqp; 259 1.2.2.2 bouyer struct red_interface *ifacep; 260 1.2.2.2 bouyer struct ifnet *ifp; 261 1.2.2.2 bouyer int error = 0; 262 1.2.2.2 bouyer 263 1.2.2.2 bouyer /* check super-user privilege */ 264 1.2.2.2 bouyer switch (cmd) { 265 1.2.2.2 bouyer case RED_GETSTATS: 266 1.2.2.2 bouyer break; 267 1.2.2.2 bouyer default: 268 1.2.2.2 bouyer #if (__FreeBSD_version > 400000) 269 1.2.2.2 bouyer if ((error = suser(p)) != 0) 270 1.2.2.2 bouyer #else 271 1.2.2.2 bouyer if ((error = suser(p->p_ucred, &p->p_acflag)) != 0) 272 1.2.2.2 bouyer #endif 273 1.2.2.2 bouyer return (error); 274 1.2.2.2 bouyer break; 275 1.2.2.2 bouyer } 276 1.2.2.2 bouyer 277 1.2.2.2 bouyer switch (cmd) { 278 1.2.2.2 bouyer 279 1.2.2.2 bouyer case RED_ENABLE: 280 1.2.2.2 bouyer ifacep = (struct red_interface *)addr; 281 1.2.2.2 bouyer if ((rqp = altq_lookup(ifacep->red_ifname, ALTQT_RED)) == NULL) { 282 1.2.2.2 bouyer error = EBADF; 283 1.2.2.2 bouyer break; 284 1.2.2.2 bouyer } 285 1.2.2.2 bouyer error = altq_enable(rqp->rq_ifq); 286 1.2.2.2 bouyer break; 287 1.2.2.2 bouyer 288 1.2.2.2 bouyer case RED_DISABLE: 289 1.2.2.2 bouyer ifacep = (struct red_interface *)addr; 290 1.2.2.2 bouyer if ((rqp = altq_lookup(ifacep->red_ifname, ALTQT_RED)) == NULL) { 291 1.2.2.2 bouyer error = EBADF; 292 1.2.2.2 bouyer break; 293 1.2.2.2 bouyer } 294 1.2.2.2 bouyer error = altq_disable(rqp->rq_ifq); 295 1.2.2.2 bouyer break; 296 1.2.2.2 bouyer 297 1.2.2.2 bouyer case RED_IF_ATTACH: 298 1.2.2.2 bouyer ifp = ifunit(((struct red_interface *)addr)->red_ifname); 299 1.2.2.2 bouyer if (ifp == NULL) { 300 1.2.2.2 bouyer error = ENXIO; 301 1.2.2.2 bouyer break; 302 1.2.2.2 bouyer } 303 1.2.2.2 bouyer 304 1.2.2.2 bouyer /* allocate and initialize red_queue_t */ 305 1.2.2.2 bouyer MALLOC(rqp, red_queue_t *, sizeof(red_queue_t), M_DEVBUF, M_WAITOK); 306 1.2.2.2 bouyer if (rqp == NULL) { 307 1.2.2.2 bouyer error = ENOMEM; 308 1.2.2.2 bouyer break; 309 1.2.2.2 bouyer } 310 1.2.2.2 bouyer bzero(rqp, sizeof(red_queue_t)); 311 1.2.2.2 bouyer 312 1.2.2.2 bouyer MALLOC(rqp->rq_q, class_queue_t *, sizeof(class_queue_t), 313 1.2.2.2 bouyer M_DEVBUF, M_WAITOK); 314 1.2.2.2 bouyer if (rqp->rq_q == NULL) { 315 1.2.2.2 bouyer FREE(rqp, M_DEVBUF); 316 1.2.2.2 bouyer error = ENOMEM; 317 1.2.2.2 bouyer break; 318 1.2.2.2 bouyer } 319 1.2.2.2 bouyer bzero(rqp->rq_q, sizeof(class_queue_t)); 320 1.2.2.2 bouyer 321 1.2.2.2 bouyer rqp->rq_red = red_alloc(0, 0, 0, 0, 0, 0); 322 1.2.2.2 bouyer if (rqp->rq_red == NULL) { 323 1.2.2.2 bouyer FREE(rqp->rq_q, M_DEVBUF); 324 1.2.2.2 bouyer FREE(rqp, M_DEVBUF); 325 1.2.2.2 bouyer error = ENOMEM; 326 1.2.2.2 bouyer break; 327 1.2.2.2 bouyer } 328 1.2.2.2 bouyer 329 1.2.2.2 bouyer rqp->rq_ifq = &ifp->if_snd; 330 1.2.2.2 bouyer qtail(rqp->rq_q) = NULL; 331 1.2.2.2 bouyer qlen(rqp->rq_q) = 0; 332 1.2.2.2 bouyer qlimit(rqp->rq_q) = RED_LIMIT; 333 1.2.2.2 bouyer qtype(rqp->rq_q) = Q_RED; 334 1.2.2.2 bouyer 335 1.2.2.2 bouyer /* 336 1.2.2.2 bouyer * set RED to this ifnet structure. 337 1.2.2.2 bouyer */ 338 1.2.2.2 bouyer error = altq_attach(rqp->rq_ifq, ALTQT_RED, rqp, 339 1.2.2.2 bouyer red_enqueue, red_dequeue, red_request, 340 1.2.2.2 bouyer NULL, NULL); 341 1.2.2.2 bouyer if (error) { 342 1.2.2.2 bouyer red_destroy(rqp->rq_red); 343 1.2.2.2 bouyer FREE(rqp->rq_q, M_DEVBUF); 344 1.2.2.2 bouyer FREE(rqp, M_DEVBUF); 345 1.2.2.2 bouyer break; 346 1.2.2.2 bouyer } 347 1.2.2.2 bouyer 348 1.2.2.2 bouyer /* add this state to the red list */ 349 1.2.2.2 bouyer rqp->rq_next = red_list; 350 1.2.2.2 bouyer red_list = rqp; 351 1.2.2.2 bouyer break; 352 1.2.2.2 bouyer 353 1.2.2.2 bouyer case RED_IF_DETACH: 354 1.2.2.2 bouyer ifacep = (struct red_interface *)addr; 355 1.2.2.2 bouyer if ((rqp = altq_lookup(ifacep->red_ifname, ALTQT_RED)) == NULL) { 356 1.2.2.2 bouyer error = EBADF; 357 1.2.2.2 bouyer break; 358 1.2.2.2 bouyer } 359 1.2.2.2 bouyer error = red_detach(rqp); 360 1.2.2.2 bouyer break; 361 1.2.2.2 bouyer 362 1.2.2.2 bouyer case RED_GETSTATS: 363 1.2.2.2 bouyer do { 364 1.2.2.2 bouyer struct red_stats *q_stats; 365 1.2.2.2 bouyer red_t *rp; 366 1.2.2.2 bouyer 367 1.2.2.2 bouyer q_stats = (struct red_stats *)addr; 368 1.2.2.2 bouyer if ((rqp = altq_lookup(q_stats->iface.red_ifname, 369 1.2.2.2 bouyer ALTQT_RED)) == NULL) { 370 1.2.2.2 bouyer error = EBADF; 371 1.2.2.2 bouyer break; 372 1.2.2.2 bouyer } 373 1.2.2.2 bouyer 374 1.2.2.2 bouyer q_stats->q_len = qlen(rqp->rq_q); 375 1.2.2.2 bouyer q_stats->q_limit = qlimit(rqp->rq_q); 376 1.2.2.2 bouyer 377 1.2.2.2 bouyer rp = rqp->rq_red; 378 1.2.2.2 bouyer q_stats->q_avg = rp->red_avg >> rp->red_wshift; 379 1.2.2.2 bouyer q_stats->xmit_cnt = rp->red_stats.xmit_cnt; 380 1.2.2.2 bouyer q_stats->drop_cnt = rp->red_stats.drop_cnt; 381 1.2.2.2 bouyer q_stats->drop_forced = rp->red_stats.drop_forced; 382 1.2.2.2 bouyer q_stats->drop_unforced = rp->red_stats.drop_unforced; 383 1.2.2.2 bouyer q_stats->marked_packets = rp->red_stats.marked_packets; 384 1.2.2.2 bouyer 385 1.2.2.2 bouyer q_stats->weight = rp->red_weight; 386 1.2.2.2 bouyer q_stats->inv_pmax = rp->red_inv_pmax; 387 1.2.2.2 bouyer q_stats->th_min = rp->red_thmin; 388 1.2.2.2 bouyer q_stats->th_max = rp->red_thmax; 389 1.2.2.2 bouyer 390 1.2.2.2 bouyer #ifdef ALTQ_FLOWVALVE 391 1.2.2.2 bouyer if (rp->red_flowvalve != NULL) { 392 1.2.2.2 bouyer struct flowvalve *fv = rp->red_flowvalve; 393 1.2.2.2 bouyer q_stats->fv_flows = fv->fv_flows; 394 1.2.2.2 bouyer q_stats->fv_pass = fv->fv_stats.pass; 395 1.2.2.2 bouyer q_stats->fv_predrop = fv->fv_stats.predrop; 396 1.2.2.2 bouyer q_stats->fv_alloc = fv->fv_stats.alloc; 397 1.2.2.2 bouyer q_stats->fv_escape = fv->fv_stats.escape; 398 1.2.2.2 bouyer } else { 399 1.2.2.2 bouyer #endif /* ALTQ_FLOWVALVE */ 400 1.2.2.2 bouyer q_stats->fv_flows = 0; 401 1.2.2.2 bouyer q_stats->fv_pass = 0; 402 1.2.2.2 bouyer q_stats->fv_predrop = 0; 403 1.2.2.2 bouyer q_stats->fv_alloc = 0; 404 1.2.2.2 bouyer q_stats->fv_escape = 0; 405 1.2.2.2 bouyer #ifdef ALTQ_FLOWVALVE 406 1.2.2.2 bouyer } 407 1.2.2.2 bouyer #endif /* ALTQ_FLOWVALVE */ 408 1.2.2.2 bouyer } while (0); 409 1.2.2.2 bouyer break; 410 1.2.2.2 bouyer 411 1.2.2.2 bouyer case RED_CONFIG: 412 1.2.2.2 bouyer do { 413 1.2.2.2 bouyer struct red_conf *fc; 414 1.2.2.2 bouyer red_t *new; 415 1.2.2.2 bouyer int s, limit; 416 1.2.2.2 bouyer 417 1.2.2.2 bouyer fc = (struct red_conf *)addr; 418 1.2.2.2 bouyer if ((rqp = altq_lookup(fc->iface.red_ifname, 419 1.2.2.2 bouyer ALTQT_RED)) == NULL) { 420 1.2.2.2 bouyer error = EBADF; 421 1.2.2.2 bouyer break; 422 1.2.2.2 bouyer } 423 1.2.2.2 bouyer new = red_alloc(fc->red_weight, 424 1.2.2.2 bouyer fc->red_inv_pmax, 425 1.2.2.2 bouyer fc->red_thmin, 426 1.2.2.2 bouyer fc->red_thmax, 427 1.2.2.2 bouyer fc->red_flags, 428 1.2.2.2 bouyer fc->red_pkttime); 429 1.2.2.2 bouyer if (new == NULL) { 430 1.2.2.2 bouyer error = ENOMEM; 431 1.2.2.2 bouyer break; 432 1.2.2.2 bouyer } 433 1.2.2.2 bouyer 434 1.2.2.2 bouyer s = splimp(); 435 1.2.2.2 bouyer red_purgeq(rqp); 436 1.2.2.2 bouyer limit = fc->red_limit; 437 1.2.2.2 bouyer if (limit < fc->red_thmax) 438 1.2.2.2 bouyer limit = fc->red_thmax; 439 1.2.2.2 bouyer qlimit(rqp->rq_q) = limit; 440 1.2.2.2 bouyer fc->red_limit = limit; /* write back the new value */ 441 1.2.2.2 bouyer 442 1.2.2.2 bouyer red_destroy(rqp->rq_red); 443 1.2.2.2 bouyer rqp->rq_red = new; 444 1.2.2.2 bouyer 445 1.2.2.2 bouyer splx(s); 446 1.2.2.2 bouyer 447 1.2.2.2 bouyer /* write back new values */ 448 1.2.2.2 bouyer fc->red_limit = limit; 449 1.2.2.2 bouyer fc->red_inv_pmax = rqp->rq_red->red_inv_pmax; 450 1.2.2.2 bouyer fc->red_thmin = rqp->rq_red->red_thmin; 451 1.2.2.2 bouyer fc->red_thmax = rqp->rq_red->red_thmax; 452 1.2.2.2 bouyer 453 1.2.2.2 bouyer } while (0); 454 1.2.2.2 bouyer break; 455 1.2.2.2 bouyer 456 1.2.2.2 bouyer case RED_SETDEFAULTS: 457 1.2.2.2 bouyer do { 458 1.2.2.2 bouyer struct redparams *rp; 459 1.2.2.2 bouyer 460 1.2.2.2 bouyer rp = (struct redparams *)addr; 461 1.2.2.2 bouyer 462 1.2.2.2 bouyer default_th_min = rp->th_min; 463 1.2.2.2 bouyer default_th_max = rp->th_max; 464 1.2.2.2 bouyer default_inv_pmax = rp->inv_pmax; 465 1.2.2.2 bouyer } while (0); 466 1.2.2.2 bouyer break; 467 1.2.2.2 bouyer 468 1.2.2.2 bouyer default: 469 1.2.2.2 bouyer error = EINVAL; 470 1.2.2.2 bouyer break; 471 1.2.2.2 bouyer } 472 1.2.2.2 bouyer return error; 473 1.2.2.2 bouyer } 474 1.2.2.2 bouyer 475 1.2.2.2 bouyer static int 476 1.2.2.2 bouyer red_detach(rqp) 477 1.2.2.2 bouyer red_queue_t *rqp; 478 1.2.2.2 bouyer { 479 1.2.2.2 bouyer red_queue_t *tmp; 480 1.2.2.2 bouyer int error = 0; 481 1.2.2.2 bouyer 482 1.2.2.2 bouyer if (ALTQ_IS_ENABLED(rqp->rq_ifq)) 483 1.2.2.2 bouyer altq_disable(rqp->rq_ifq); 484 1.2.2.2 bouyer 485 1.2.2.2 bouyer if ((error = altq_detach(rqp->rq_ifq))) 486 1.2.2.2 bouyer return (error); 487 1.2.2.2 bouyer 488 1.2.2.2 bouyer if (red_list == rqp) 489 1.2.2.2 bouyer red_list = rqp->rq_next; 490 1.2.2.2 bouyer else { 491 1.2.2.2 bouyer for (tmp = red_list; tmp != NULL; tmp = tmp->rq_next) 492 1.2.2.2 bouyer if (tmp->rq_next == rqp) { 493 1.2.2.2 bouyer tmp->rq_next = rqp->rq_next; 494 1.2.2.2 bouyer break; 495 1.2.2.2 bouyer } 496 1.2.2.2 bouyer if (tmp == NULL) 497 1.2.2.2 bouyer printf("red_detach: no state found in red_list!\n"); 498 1.2.2.2 bouyer } 499 1.2.2.2 bouyer 500 1.2.2.2 bouyer red_destroy(rqp->rq_red); 501 1.2.2.2 bouyer FREE(rqp->rq_q, M_DEVBUF); 502 1.2.2.2 bouyer FREE(rqp, M_DEVBUF); 503 1.2.2.2 bouyer return (error); 504 1.2.2.2 bouyer } 505 1.2.2.2 bouyer 506 1.2.2.2 bouyer /* 507 1.2.2.2 bouyer * red support routines 508 1.2.2.2 bouyer */ 509 1.2.2.2 bouyer 510 1.2.2.2 bouyer red_t * 511 1.2.2.2 bouyer red_alloc(weight, inv_pmax, th_min, th_max, flags, pkttime) 512 1.2.2.2 bouyer int weight, inv_pmax, th_min, th_max; 513 1.2.2.2 bouyer int flags, pkttime; 514 1.2.2.2 bouyer { 515 1.2.2.2 bouyer red_t *rp; 516 1.2.2.2 bouyer int w, i; 517 1.2.2.2 bouyer int npkts_per_sec; 518 1.2.2.2 bouyer 519 1.2.2.2 bouyer MALLOC(rp, red_t *, sizeof(red_t), M_DEVBUF, M_WAITOK); 520 1.2.2.2 bouyer if (rp == NULL) 521 1.2.2.2 bouyer return (NULL); 522 1.2.2.2 bouyer bzero(rp, sizeof(red_t)); 523 1.2.2.2 bouyer 524 1.2.2.2 bouyer rp->red_avg = 0; 525 1.2.2.2 bouyer rp->red_idle = 1; 526 1.2.2.2 bouyer 527 1.2.2.2 bouyer if (weight == 0) 528 1.2.2.2 bouyer rp->red_weight = W_WEIGHT; 529 1.2.2.2 bouyer else 530 1.2.2.2 bouyer rp->red_weight = weight; 531 1.2.2.2 bouyer if (inv_pmax == 0) 532 1.2.2.2 bouyer rp->red_inv_pmax = default_inv_pmax; 533 1.2.2.2 bouyer else 534 1.2.2.2 bouyer rp->red_inv_pmax = inv_pmax; 535 1.2.2.2 bouyer if (th_min == 0) 536 1.2.2.2 bouyer rp->red_thmin = default_th_min; 537 1.2.2.2 bouyer else 538 1.2.2.2 bouyer rp->red_thmin = th_min; 539 1.2.2.2 bouyer if (th_max == 0) 540 1.2.2.2 bouyer rp->red_thmax = default_th_max; 541 1.2.2.2 bouyer else 542 1.2.2.2 bouyer rp->red_thmax = th_max; 543 1.2.2.2 bouyer 544 1.2.2.2 bouyer rp->red_flags = flags; 545 1.2.2.2 bouyer 546 1.2.2.2 bouyer if (pkttime == 0) 547 1.2.2.2 bouyer /* default packet time: 1000 bytes / 10Mbps * 8 * 1000000 */ 548 1.2.2.2 bouyer rp->red_pkttime = 800; 549 1.2.2.2 bouyer else 550 1.2.2.2 bouyer rp->red_pkttime = pkttime; 551 1.2.2.2 bouyer 552 1.2.2.2 bouyer if (weight == 0) { 553 1.2.2.2 bouyer /* when the link is very slow, adjust red parameters */ 554 1.2.2.2 bouyer npkts_per_sec = 1000000 / rp->red_pkttime; 555 1.2.2.2 bouyer if (npkts_per_sec < 50) { 556 1.2.2.2 bouyer /* up to about 400Kbps */ 557 1.2.2.2 bouyer rp->red_weight = W_WEIGHT_2; 558 1.2.2.2 bouyer } else if (npkts_per_sec < 300) { 559 1.2.2.2 bouyer /* up to about 2.4Mbps */ 560 1.2.2.2 bouyer rp->red_weight = W_WEIGHT_1; 561 1.2.2.2 bouyer } 562 1.2.2.2 bouyer } 563 1.2.2.2 bouyer 564 1.2.2.2 bouyer /* calculate wshift. weight must be power of 2 */ 565 1.2.2.2 bouyer w = rp->red_weight; 566 1.2.2.2 bouyer for (i = 0; w > 1; i++) 567 1.2.2.2 bouyer w = w >> 1; 568 1.2.2.2 bouyer rp->red_wshift = i; 569 1.2.2.2 bouyer w = 1 << rp->red_wshift; 570 1.2.2.2 bouyer if (w != rp->red_weight) { 571 1.2.2.2 bouyer printf("invalid weight value %d for red! use %d\n", 572 1.2.2.2 bouyer rp->red_weight, w); 573 1.2.2.2 bouyer rp->red_weight = w; 574 1.2.2.2 bouyer } 575 1.2.2.2 bouyer 576 1.2.2.2 bouyer /* 577 1.2.2.2 bouyer * thmin_s and thmax_s are scaled versions of th_min and th_max 578 1.2.2.2 bouyer * to be compared with avg. 579 1.2.2.2 bouyer */ 580 1.2.2.2 bouyer rp->red_thmin_s = rp->red_thmin << (rp->red_wshift + FP_SHIFT); 581 1.2.2.2 bouyer rp->red_thmax_s = rp->red_thmax << (rp->red_wshift + FP_SHIFT); 582 1.2.2.2 bouyer 583 1.2.2.2 bouyer /* 584 1.2.2.2 bouyer * precompute probability denominator 585 1.2.2.2 bouyer * probd = (2 * (TH_MAX-TH_MIN) / pmax) in fixed-point 586 1.2.2.2 bouyer */ 587 1.2.2.2 bouyer rp->red_probd = (2 * (rp->red_thmax - rp->red_thmin) 588 1.2.2.2 bouyer * rp->red_inv_pmax) << FP_SHIFT; 589 1.2.2.2 bouyer 590 1.2.2.2 bouyer /* allocate weight table */ 591 1.2.2.2 bouyer rp->red_wtab = wtab_alloc(rp->red_weight); 592 1.2.2.2 bouyer 593 1.2.2.2 bouyer microtime(&rp->red_last); 594 1.2.2.2 bouyer #ifdef ALTQ_FLOWVALVE 595 1.2.2.2 bouyer if (flags & REDF_FLOWVALVE) 596 1.2.2.2 bouyer rp->red_flowvalve = fv_alloc(rp); 597 1.2.2.2 bouyer /* if fv_alloc failes, flowvalve is just disabled */ 598 1.2.2.2 bouyer #endif 599 1.2.2.2 bouyer return (rp); 600 1.2.2.2 bouyer } 601 1.2.2.2 bouyer 602 1.2.2.2 bouyer void 603 1.2.2.2 bouyer red_destroy(rp) 604 1.2.2.2 bouyer red_t *rp; 605 1.2.2.2 bouyer { 606 1.2.2.2 bouyer #ifdef ALTQ_FLOWVALVE 607 1.2.2.2 bouyer if (rp->red_flowvalve != NULL) 608 1.2.2.2 bouyer fv_destroy(rp->red_flowvalve); 609 1.2.2.2 bouyer #endif 610 1.2.2.2 bouyer wtab_destroy(rp->red_wtab); 611 1.2.2.2 bouyer FREE(rp, M_DEVBUF); 612 1.2.2.2 bouyer } 613 1.2.2.2 bouyer 614 1.2.2.2 bouyer void 615 1.2.2.2 bouyer red_getstats(rp, sp) 616 1.2.2.2 bouyer red_t *rp; 617 1.2.2.2 bouyer struct redstats *sp; 618 1.2.2.2 bouyer { 619 1.2.2.2 bouyer sp->q_avg = rp->red_avg >> rp->red_wshift; 620 1.2.2.2 bouyer sp->xmit_cnt = rp->red_stats.xmit_cnt; 621 1.2.2.2 bouyer sp->drop_cnt = rp->red_stats.drop_cnt; 622 1.2.2.2 bouyer sp->drop_forced = rp->red_stats.drop_forced; 623 1.2.2.2 bouyer sp->drop_unforced = rp->red_stats.drop_unforced; 624 1.2.2.2 bouyer sp->marked_packets = rp->red_stats.marked_packets; 625 1.2.2.2 bouyer } 626 1.2.2.2 bouyer 627 1.2.2.2 bouyer /* 628 1.2.2.2 bouyer * enqueue routine: 629 1.2.2.2 bouyer * 630 1.2.2.2 bouyer * returns: 0 when successfully queued. 631 1.2.2.2 bouyer * ENOBUFS when drop occurs. 632 1.2.2.2 bouyer */ 633 1.2.2.2 bouyer static int 634 1.2.2.2 bouyer red_enqueue(ifq, m, pktattr) 635 1.2.2.2 bouyer struct ifaltq *ifq; 636 1.2.2.2 bouyer struct mbuf *m; 637 1.2.2.2 bouyer struct altq_pktattr *pktattr; 638 1.2.2.2 bouyer { 639 1.2.2.2 bouyer red_queue_t *rqp = (red_queue_t *)ifq->altq_disc; 640 1.2.2.2 bouyer 641 1.2.2.2 bouyer if (red_addq(rqp->rq_red, rqp->rq_q, m, pktattr) < 0) 642 1.2.2.2 bouyer return ENOBUFS; 643 1.2.2.2 bouyer ifq->ifq_len++; 644 1.2.2.2 bouyer return 0; 645 1.2.2.2 bouyer } 646 1.2.2.2 bouyer 647 1.2.2.2 bouyer int 648 1.2.2.2 bouyer red_addq(rp, q, m, pktattr) 649 1.2.2.2 bouyer red_t *rp; 650 1.2.2.2 bouyer class_queue_t *q; 651 1.2.2.2 bouyer struct mbuf *m; 652 1.2.2.2 bouyer struct altq_pktattr *pktattr; 653 1.2.2.2 bouyer { 654 1.2.2.2 bouyer int avg, droptype; 655 1.2.2.2 bouyer int n; 656 1.2.2.2 bouyer #ifdef ALTQ_FLOWVALVE 657 1.2.2.2 bouyer struct fve *fve = NULL; 658 1.2.2.2 bouyer 659 1.2.2.2 bouyer if (rp->red_flowvalve != NULL && rp->red_flowvalve->fv_flows > 0) 660 1.2.2.2 bouyer if (fv_checkflow(rp->red_flowvalve, pktattr, &fve)) { 661 1.2.2.2 bouyer m_freem(m); 662 1.2.2.2 bouyer return (-1); 663 1.2.2.2 bouyer } 664 1.2.2.2 bouyer #endif 665 1.2.2.2 bouyer 666 1.2.2.2 bouyer avg = rp->red_avg; 667 1.2.2.2 bouyer 668 1.2.2.2 bouyer /* 669 1.2.2.2 bouyer * if we were idle, we pretend that n packets arrived during 670 1.2.2.2 bouyer * the idle period. 671 1.2.2.2 bouyer */ 672 1.2.2.2 bouyer if (rp->red_idle) { 673 1.2.2.2 bouyer struct timeval now; 674 1.2.2.2 bouyer int t; 675 1.2.2.2 bouyer 676 1.2.2.2 bouyer rp->red_idle = 0; 677 1.2.2.2 bouyer microtime(&now); 678 1.2.2.2 bouyer t = (now.tv_sec - rp->red_last.tv_sec); 679 1.2.2.2 bouyer if (t > 60) { 680 1.2.2.2 bouyer /* 681 1.2.2.2 bouyer * being idle for more than 1 minute, set avg to zero. 682 1.2.2.2 bouyer * this prevents t from overflow. 683 1.2.2.2 bouyer */ 684 1.2.2.2 bouyer avg = 0; 685 1.2.2.2 bouyer } else { 686 1.2.2.2 bouyer t = t * 1000000 + (now.tv_usec - rp->red_last.tv_usec); 687 1.2.2.2 bouyer n = t / rp->red_pkttime - 1; 688 1.2.2.2 bouyer 689 1.2.2.2 bouyer /* the following line does (avg = (1 - Wq)^n * avg) */ 690 1.2.2.2 bouyer if (n > 0) 691 1.2.2.2 bouyer avg = (avg >> FP_SHIFT) * 692 1.2.2.2 bouyer pow_w(rp->red_wtab, n); 693 1.2.2.2 bouyer } 694 1.2.2.2 bouyer } 695 1.2.2.2 bouyer 696 1.2.2.2 bouyer /* run estimator. (note: avg is scaled by WEIGHT in fixed-point) */ 697 1.2.2.2 bouyer avg += (qlen(q) << FP_SHIFT) - (avg >> rp->red_wshift); 698 1.2.2.2 bouyer rp->red_avg = avg; /* save the new value */ 699 1.2.2.2 bouyer 700 1.2.2.2 bouyer /* 701 1.2.2.2 bouyer * red_count keeps a tally of arriving traffic that has not 702 1.2.2.2 bouyer * been dropped. 703 1.2.2.2 bouyer */ 704 1.2.2.2 bouyer rp->red_count++; 705 1.2.2.2 bouyer 706 1.2.2.2 bouyer /* see if we drop early */ 707 1.2.2.2 bouyer droptype = DTYPE_NODROP; 708 1.2.2.2 bouyer if (avg >= rp->red_thmin_s && qlen(q) > 1) { 709 1.2.2.2 bouyer if (avg >= rp->red_thmax_s) { 710 1.2.2.2 bouyer /* avg >= th_max: forced drop */ 711 1.2.2.2 bouyer droptype = DTYPE_FORCED; 712 1.2.2.2 bouyer } else if (rp->red_old == 0) { 713 1.2.2.2 bouyer /* first exceeds th_min */ 714 1.2.2.2 bouyer rp->red_count = 1; 715 1.2.2.2 bouyer rp->red_old = 1; 716 1.2.2.2 bouyer } else if (drop_early((avg - rp->red_thmin_s) >> rp->red_wshift, 717 1.2.2.2 bouyer rp->red_probd, rp->red_count)) { 718 1.2.2.2 bouyer /* mark or drop by red */ 719 1.2.2.2 bouyer if ((rp->red_flags & REDF_ECN) && 720 1.2.2.2 bouyer mark_ecn(m, pktattr, rp->red_flags)) { 721 1.2.2.2 bouyer /* successfully marked. do not drop. */ 722 1.2.2.2 bouyer rp->red_count = 0; 723 1.2.2.2 bouyer #ifdef RED_STATS 724 1.2.2.2 bouyer rp->red_stats.marked_packets++; 725 1.2.2.2 bouyer #endif 726 1.2.2.2 bouyer } else { 727 1.2.2.2 bouyer /* unforced drop by red */ 728 1.2.2.2 bouyer droptype = DTYPE_EARLY; 729 1.2.2.2 bouyer } 730 1.2.2.2 bouyer } 731 1.2.2.2 bouyer } else { 732 1.2.2.2 bouyer /* avg < th_min */ 733 1.2.2.2 bouyer rp->red_old = 0; 734 1.2.2.2 bouyer } 735 1.2.2.2 bouyer 736 1.2.2.2 bouyer /* 737 1.2.2.2 bouyer * if the queue length hits the hard limit, it's a forced drop. 738 1.2.2.2 bouyer */ 739 1.2.2.2 bouyer if (droptype == DTYPE_NODROP && qlen(q) >= qlimit(q)) 740 1.2.2.2 bouyer droptype = DTYPE_FORCED; 741 1.2.2.2 bouyer 742 1.2.2.2 bouyer #ifdef RED_RANDOM_DROP 743 1.2.2.2 bouyer /* if successful or forced drop, enqueue this packet. */ 744 1.2.2.2 bouyer if (droptype != DTYPE_EARLY) 745 1.2.2.2 bouyer _addq(q, m); 746 1.2.2.2 bouyer #else 747 1.2.2.2 bouyer /* if successful, enqueue this packet. */ 748 1.2.2.2 bouyer if (droptype == DTYPE_NODROP) 749 1.2.2.2 bouyer _addq(q, m); 750 1.2.2.2 bouyer #endif 751 1.2.2.2 bouyer if (droptype != DTYPE_NODROP) { 752 1.2.2.2 bouyer if (droptype == DTYPE_EARLY) { 753 1.2.2.2 bouyer /* drop the incoming packet */ 754 1.2.2.2 bouyer #ifdef RED_STATS 755 1.2.2.2 bouyer rp->red_stats.drop_unforced++; 756 1.2.2.2 bouyer #endif 757 1.2.2.2 bouyer } else { 758 1.2.2.2 bouyer /* forced drop, select a victim packet in the queue. */ 759 1.2.2.2 bouyer #ifdef RED_RANDOM_DROP 760 1.2.2.2 bouyer m = _getq_random(q); 761 1.2.2.2 bouyer #endif 762 1.2.2.2 bouyer #ifdef RED_STATS 763 1.2.2.2 bouyer rp->red_stats.drop_forced++; 764 1.2.2.2 bouyer #endif 765 1.2.2.2 bouyer } 766 1.2.2.2 bouyer #ifdef RED_STATS 767 1.2.2.2 bouyer PKTCNTR_ADD(&rp->red_stats.drop_cnt, m_pktlen(m)); 768 1.2.2.2 bouyer #endif 769 1.2.2.2 bouyer rp->red_count = 0; 770 1.2.2.2 bouyer #ifdef ALTQ_FLOWVALVE 771 1.2.2.2 bouyer if (rp->red_flowvalve != NULL) 772 1.2.2.2 bouyer fv_dropbyred(rp->red_flowvalve, pktattr, fve); 773 1.2.2.2 bouyer #endif 774 1.2.2.2 bouyer m_freem(m); 775 1.2.2.2 bouyer return (-1); 776 1.2.2.2 bouyer } 777 1.2.2.2 bouyer /* successfully queued */ 778 1.2.2.2 bouyer #ifdef RED_STATS 779 1.2.2.2 bouyer PKTCNTR_ADD(&rp->red_stats.xmit_cnt, m_pktlen(m)); 780 1.2.2.2 bouyer #endif 781 1.2.2.2 bouyer return (0); 782 1.2.2.2 bouyer } 783 1.2.2.2 bouyer 784 1.2.2.2 bouyer /* 785 1.2.2.2 bouyer * early-drop probability is calculated as follows: 786 1.2.2.2 bouyer * prob = p_max * (avg - th_min) / (th_max - th_min) 787 1.2.2.2 bouyer * prob_a = prob / (2 - count*prob) 788 1.2.2.2 bouyer * = (avg-th_min) / (2*(th_max-th_min)*inv_p_max - count*(avg-th_min)) 789 1.2.2.2 bouyer * here prob_a increases as successive undrop count increases. 790 1.2.2.2 bouyer * (prob_a starts from prob/2, becomes prob when (count == (1 / prob)), 791 1.2.2.2 bouyer * becomes 1 when (count >= (2 / prob))). 792 1.2.2.2 bouyer */ 793 1.2.2.2 bouyer int 794 1.2.2.2 bouyer drop_early(fp_len, fp_probd, count) 795 1.2.2.2 bouyer int fp_len; /* (avg - TH_MIN) in fixed-point */ 796 1.2.2.2 bouyer int fp_probd; /* (2 * (TH_MAX-TH_MIN) / pmax) in fixed-point */ 797 1.2.2.2 bouyer int count; /* how many successive undropped packets */ 798 1.2.2.2 bouyer { 799 1.2.2.2 bouyer int d; /* denominator of drop-probability */ 800 1.2.2.2 bouyer 801 1.2.2.2 bouyer d = fp_probd - count * fp_len; 802 1.2.2.2 bouyer if (d <= 0) 803 1.2.2.2 bouyer /* count exceeds the hard limit: drop or mark */ 804 1.2.2.2 bouyer return (1); 805 1.2.2.2 bouyer 806 1.2.2.2 bouyer /* 807 1.2.2.2 bouyer * now the range of d is [1..600] in fixed-point. (when 808 1.2.2.2 bouyer * th_max-th_min=10 and p_max=1/30) 809 1.2.2.2 bouyer * drop probability = (avg - TH_MIN) / d 810 1.2.2.2 bouyer */ 811 1.2.2.2 bouyer 812 1.2.2.2 bouyer if ((random() % d) < fp_len) { 813 1.2.2.2 bouyer /* drop or mark */ 814 1.2.2.2 bouyer return (1); 815 1.2.2.2 bouyer } 816 1.2.2.2 bouyer /* no drop/mark */ 817 1.2.2.2 bouyer return (0); 818 1.2.2.2 bouyer } 819 1.2.2.2 bouyer 820 1.2.2.2 bouyer /* 821 1.2.2.2 bouyer * try to mark CE bit to the packet. 822 1.2.2.2 bouyer * returns 1 if successfully marked, 0 otherwise. 823 1.2.2.2 bouyer */ 824 1.2.2.2 bouyer int 825 1.2.2.2 bouyer mark_ecn(m, pktattr, flags) 826 1.2.2.2 bouyer struct mbuf *m; 827 1.2.2.2 bouyer struct altq_pktattr *pktattr; 828 1.2.2.2 bouyer int flags; 829 1.2.2.2 bouyer { 830 1.2.2.2 bouyer struct mbuf *m0; 831 1.2.2.2 bouyer 832 1.2.2.2 bouyer if (pktattr == NULL || 833 1.2.2.2 bouyer (pktattr->pattr_af != AF_INET && pktattr->pattr_af != AF_INET6)) 834 1.2.2.2 bouyer return (0); 835 1.2.2.2 bouyer 836 1.2.2.2 bouyer /* verify that pattr_hdr is within the mbuf data */ 837 1.2.2.2 bouyer for (m0 = m; m0 != NULL; m0 = m0->m_next) 838 1.2.2.2 bouyer if ((pktattr->pattr_hdr >= m0->m_data) && 839 1.2.2.2 bouyer (pktattr->pattr_hdr < m0->m_data + m0->m_len)) 840 1.2.2.2 bouyer break; 841 1.2.2.2 bouyer if (m0 == NULL) { 842 1.2.2.2 bouyer /* ick, pattr_hdr is stale */ 843 1.2.2.2 bouyer pktattr->pattr_af = AF_UNSPEC; 844 1.2.2.2 bouyer return (0); 845 1.2.2.2 bouyer } 846 1.2.2.2 bouyer 847 1.2.2.2 bouyer switch (pktattr->pattr_af) { 848 1.2.2.2 bouyer case AF_INET: 849 1.2.2.2 bouyer if (flags & REDF_ECN4) { 850 1.2.2.2 bouyer struct ip *ip = (struct ip *)pktattr->pattr_hdr; 851 1.2.2.2 bouyer 852 1.2.2.2 bouyer if (ip->ip_v != 4) 853 1.2.2.2 bouyer return (0); /* version mismatch! */ 854 1.2.2.2 bouyer if (ip->ip_tos & IPTOS_ECT) { 855 1.2.2.2 bouyer /* ECN-capable, mark ECN bit. */ 856 1.2.2.2 bouyer if ((ip->ip_tos & IPTOS_CE) == 0) { 857 1.2.2.2 bouyer #if (IPTOS_CE == 0x01) 858 1.2.2.2 bouyer u_short sum; 859 1.2.2.2 bouyer 860 1.2.2.2 bouyer ip->ip_tos |= IPTOS_CE; 861 1.2.2.2 bouyer /* 862 1.2.2.2 bouyer * optimized version when IPTOS_CE 863 1.2.2.2 bouyer * is 0x01. 864 1.2.2.2 bouyer * HC' = HC -1 when HC > 0 865 1.2.2.2 bouyer * = 0xfffe when HC = 0 866 1.2.2.2 bouyer */ 867 1.2.2.2 bouyer sum = ntohs(ip->ip_sum); 868 1.2.2.2 bouyer if (sum == 0) 869 1.2.2.2 bouyer sum = 0xfffe; 870 1.2.2.2 bouyer else 871 1.2.2.2 bouyer sum -= 1; 872 1.2.2.2 bouyer ip->ip_sum = htons(sum); 873 1.2.2.2 bouyer #else /* IPTOS_CE != 0x01 */ 874 1.2.2.2 bouyer long sum; 875 1.2.2.2 bouyer 876 1.2.2.2 bouyer ip->ip_tos |= IPTOS_CE; 877 1.2.2.2 bouyer /* 878 1.2.2.2 bouyer * update checksum (from RFC1624) 879 1.2.2.2 bouyer * HC' = ~(~HC + ~m + m') 880 1.2.2.2 bouyer */ 881 1.2.2.2 bouyer sum = ~ntohs(ip->ip_sum) & 0xffff; 882 1.2.2.2 bouyer sum += 0xffff + IPTOS_CE; 883 1.2.2.2 bouyer sum = (sum >> 16) + (sum & 0xffff); 884 1.2.2.2 bouyer sum += (sum >> 16); /* add carry */ 885 1.2.2.2 bouyer 886 1.2.2.2 bouyer ip->ip_sum = htons(~sum & 0xffff); 887 1.2.2.2 bouyer #endif /* IPTOS_CE != 0x01 */ 888 1.2.2.2 bouyer } 889 1.2.2.2 bouyer return (1); 890 1.2.2.2 bouyer } 891 1.2.2.2 bouyer } 892 1.2.2.2 bouyer break; 893 1.2.2.2 bouyer #ifdef INET6 894 1.2.2.2 bouyer case AF_INET6: 895 1.2.2.2 bouyer if (flags & REDF_ECN6) { 896 1.2.2.2 bouyer struct ip6_hdr *ip6 = (struct ip6_hdr *)pktattr->pattr_hdr; 897 1.2.2.2 bouyer u_int32_t flowlabel; 898 1.2.2.2 bouyer 899 1.2.2.2 bouyer flowlabel = ntohl(ip6->ip6_flow); 900 1.2.2.2 bouyer if ((flowlabel >> 28) != 6) 901 1.2.2.2 bouyer return (0); /* version mismatch! */ 902 1.2.2.2 bouyer if (flowlabel & (IPTOS_ECT << 20)) { 903 1.2.2.2 bouyer /* ECN-capable, mark ECN bit. */ 904 1.2.2.2 bouyer flowlabel |= (IPTOS_CE << 20); 905 1.2.2.2 bouyer ip6->ip6_flow = htonl(flowlabel); 906 1.2.2.2 bouyer return (1); 907 1.2.2.2 bouyer } 908 1.2.2.2 bouyer } 909 1.2.2.2 bouyer break; 910 1.2.2.2 bouyer #endif /* INET6 */ 911 1.2.2.2 bouyer } 912 1.2.2.2 bouyer 913 1.2.2.2 bouyer /* not marked */ 914 1.2.2.2 bouyer return (0); 915 1.2.2.2 bouyer } 916 1.2.2.2 bouyer 917 1.2.2.2 bouyer /* 918 1.2.2.2 bouyer * dequeue routine: 919 1.2.2.2 bouyer * must be called in splimp. 920 1.2.2.2 bouyer * 921 1.2.2.2 bouyer * returns: mbuf dequeued. 922 1.2.2.2 bouyer * NULL when no packet is available in the queue. 923 1.2.2.2 bouyer */ 924 1.2.2.2 bouyer 925 1.2.2.2 bouyer static struct mbuf * 926 1.2.2.2 bouyer red_dequeue(ifq, op) 927 1.2.2.2 bouyer struct ifaltq *ifq; 928 1.2.2.2 bouyer int op; 929 1.2.2.2 bouyer { 930 1.2.2.2 bouyer red_queue_t *rqp = (red_queue_t *)ifq->altq_disc; 931 1.2.2.2 bouyer struct mbuf *m; 932 1.2.2.2 bouyer 933 1.2.2.2 bouyer if (op == ALTDQ_POLL) 934 1.2.2.2 bouyer return qhead(rqp->rq_q); 935 1.2.2.2 bouyer 936 1.2.2.2 bouyer /* op == ALTDQ_REMOVE */ 937 1.2.2.2 bouyer m = red_getq(rqp->rq_red, rqp->rq_q); 938 1.2.2.2 bouyer if (m != NULL) 939 1.2.2.2 bouyer ifq->ifq_len--; 940 1.2.2.2 bouyer return (m); 941 1.2.2.2 bouyer } 942 1.2.2.2 bouyer 943 1.2.2.2 bouyer struct mbuf * 944 1.2.2.2 bouyer red_getq(rp, q) 945 1.2.2.2 bouyer red_t *rp; 946 1.2.2.2 bouyer class_queue_t *q; 947 1.2.2.2 bouyer { 948 1.2.2.2 bouyer struct mbuf *m; 949 1.2.2.2 bouyer 950 1.2.2.2 bouyer if ((m = _getq(q)) == NULL) { 951 1.2.2.2 bouyer if (rp->red_idle == 0) { 952 1.2.2.2 bouyer rp->red_idle = 1; 953 1.2.2.2 bouyer microtime(&rp->red_last); 954 1.2.2.2 bouyer } 955 1.2.2.2 bouyer return NULL; 956 1.2.2.2 bouyer } 957 1.2.2.2 bouyer 958 1.2.2.2 bouyer rp->red_idle = 0; 959 1.2.2.2 bouyer return (m); 960 1.2.2.2 bouyer } 961 1.2.2.2 bouyer 962 1.2.2.2 bouyer static int 963 1.2.2.2 bouyer red_request(ifq, req, arg) 964 1.2.2.2 bouyer struct ifaltq *ifq; 965 1.2.2.2 bouyer int req; 966 1.2.2.2 bouyer void *arg; 967 1.2.2.2 bouyer { 968 1.2.2.2 bouyer red_queue_t *rqp = (red_queue_t *)ifq->altq_disc; 969 1.2.2.2 bouyer 970 1.2.2.2 bouyer switch (req) { 971 1.2.2.2 bouyer case ALTRQ_PURGE: 972 1.2.2.2 bouyer red_purgeq(rqp); 973 1.2.2.2 bouyer break; 974 1.2.2.2 bouyer } 975 1.2.2.2 bouyer return (0); 976 1.2.2.2 bouyer } 977 1.2.2.2 bouyer 978 1.2.2.2 bouyer static void 979 1.2.2.2 bouyer red_purgeq(rqp) 980 1.2.2.2 bouyer red_queue_t *rqp; 981 1.2.2.2 bouyer { 982 1.2.2.2 bouyer _flushq(rqp->rq_q); 983 1.2.2.2 bouyer if (ALTQ_IS_ENABLED(rqp->rq_ifq)) 984 1.2.2.2 bouyer rqp->rq_ifq->ifq_len = 0; 985 1.2.2.2 bouyer } 986 1.2.2.2 bouyer 987 1.2.2.2 bouyer 988 1.2.2.2 bouyer /* 989 1.2.2.2 bouyer * helper routine to calibrate avg during idle. 990 1.2.2.2 bouyer * pow_w(wtab, n) returns (1 - Wq)^n in fixed-point 991 1.2.2.2 bouyer * here Wq = 1/weight and the code assumes Wq is close to zero. 992 1.2.2.2 bouyer * 993 1.2.2.2 bouyer * w_tab[n] holds ((1 - Wq)^(2^n)) in fixed-point. 994 1.2.2.2 bouyer */ 995 1.2.2.2 bouyer static struct wtab *wtab_list = NULL; /* pointer to wtab list */ 996 1.2.2.2 bouyer 997 1.2.2.2 bouyer struct wtab * 998 1.2.2.2 bouyer wtab_alloc(weight) 999 1.2.2.2 bouyer int weight; 1000 1.2.2.2 bouyer { 1001 1.2.2.2 bouyer struct wtab *w; 1002 1.2.2.2 bouyer int i; 1003 1.2.2.2 bouyer 1004 1.2.2.2 bouyer for (w = wtab_list; w != NULL; w = w->w_next) 1005 1.2.2.2 bouyer if (w->w_weight == weight) { 1006 1.2.2.2 bouyer w->w_refcount++; 1007 1.2.2.2 bouyer return (w); 1008 1.2.2.2 bouyer } 1009 1.2.2.2 bouyer 1010 1.2.2.2 bouyer MALLOC(w, struct wtab *, sizeof(struct wtab), M_DEVBUF, M_WAITOK); 1011 1.2.2.2 bouyer if (w == NULL) 1012 1.2.2.2 bouyer panic("wtab_alloc: malloc failed!"); 1013 1.2.2.2 bouyer bzero(w, sizeof(struct wtab)); 1014 1.2.2.2 bouyer w->w_weight = weight; 1015 1.2.2.2 bouyer w->w_refcount = 1; 1016 1.2.2.2 bouyer w->w_next = wtab_list; 1017 1.2.2.2 bouyer wtab_list = w; 1018 1.2.2.2 bouyer 1019 1.2.2.2 bouyer /* initialize the weight table */ 1020 1.2.2.2 bouyer w->w_tab[0] = ((weight - 1) << FP_SHIFT) / weight; 1021 1.2.2.2 bouyer for (i = 1; i < 32; i++) { 1022 1.2.2.2 bouyer w->w_tab[i] = (w->w_tab[i-1] * w->w_tab[i-1]) >> FP_SHIFT; 1023 1.2.2.2 bouyer if (w->w_tab[i] == 0 && w->w_param_max == 0) 1024 1.2.2.2 bouyer w->w_param_max = 1 << i; 1025 1.2.2.2 bouyer } 1026 1.2.2.2 bouyer 1027 1.2.2.2 bouyer return (w); 1028 1.2.2.2 bouyer } 1029 1.2.2.2 bouyer 1030 1.2.2.2 bouyer int 1031 1.2.2.2 bouyer wtab_destroy(w) 1032 1.2.2.2 bouyer struct wtab *w; 1033 1.2.2.2 bouyer { 1034 1.2.2.2 bouyer struct wtab *prev; 1035 1.2.2.2 bouyer 1036 1.2.2.2 bouyer if (--w->w_refcount > 0) 1037 1.2.2.2 bouyer return (0); 1038 1.2.2.2 bouyer 1039 1.2.2.2 bouyer if (wtab_list == w) 1040 1.2.2.2 bouyer wtab_list = w->w_next; 1041 1.2.2.2 bouyer else for (prev = wtab_list; prev->w_next != NULL; prev = prev->w_next) 1042 1.2.2.2 bouyer if (prev->w_next == w) { 1043 1.2.2.2 bouyer prev->w_next = w->w_next; 1044 1.2.2.2 bouyer break; 1045 1.2.2.2 bouyer } 1046 1.2.2.2 bouyer 1047 1.2.2.2 bouyer FREE(w, M_DEVBUF); 1048 1.2.2.2 bouyer return (0); 1049 1.2.2.2 bouyer } 1050 1.2.2.2 bouyer 1051 1.2.2.2 bouyer int32_t 1052 1.2.2.2 bouyer pow_w(w, n) 1053 1.2.2.2 bouyer struct wtab *w; 1054 1.2.2.2 bouyer int n; 1055 1.2.2.2 bouyer { 1056 1.2.2.2 bouyer int i, bit; 1057 1.2.2.2 bouyer int32_t val; 1058 1.2.2.2 bouyer 1059 1.2.2.2 bouyer if (n >= w->w_param_max) 1060 1.2.2.2 bouyer return (0); 1061 1.2.2.2 bouyer 1062 1.2.2.2 bouyer val = 1 << FP_SHIFT; 1063 1.2.2.2 bouyer if (n <= 0) 1064 1.2.2.2 bouyer return (val); 1065 1.2.2.2 bouyer 1066 1.2.2.2 bouyer bit = 1; 1067 1.2.2.2 bouyer i = 0; 1068 1.2.2.2 bouyer while (n) { 1069 1.2.2.2 bouyer if (n & bit) { 1070 1.2.2.2 bouyer val = (val * w->w_tab[i]) >> FP_SHIFT; 1071 1.2.2.2 bouyer n &= ~bit; 1072 1.2.2.2 bouyer } 1073 1.2.2.2 bouyer i++; 1074 1.2.2.2 bouyer bit <<= 1; 1075 1.2.2.2 bouyer } 1076 1.2.2.2 bouyer return (val); 1077 1.2.2.2 bouyer } 1078 1.2.2.2 bouyer 1079 1.2.2.2 bouyer #ifdef ALTQ_FLOWVALVE 1080 1.2.2.2 bouyer 1081 1.2.2.2 bouyer #define FV_PSHIFT 7 /* weight of average drop rate -- 1/128 */ 1082 1.2.2.2 bouyer #define FV_PSCALE(x) ((x) << FV_PSHIFT) 1083 1.2.2.2 bouyer #define FV_PUNSCALE(x) ((x) >> FV_PSHIFT) 1084 1.2.2.2 bouyer #define FV_FSHIFT 5 /* weight of average fraction -- 1/32 */ 1085 1.2.2.2 bouyer #define FV_FSCALE(x) ((x) << FV_FSHIFT) 1086 1.2.2.2 bouyer #define FV_FUNSCALE(x) ((x) >> FV_FSHIFT) 1087 1.2.2.2 bouyer 1088 1.2.2.2 bouyer #define FV_TIMER (3 * hz) /* timer value for garbage collector */ 1089 1.2.2.2 bouyer #define FV_FLOWLISTSIZE 64 /* how many flows in flowlist */ 1090 1.2.2.2 bouyer 1091 1.2.2.2 bouyer #define FV_N 10 /* update fve_f every FV_N packets */ 1092 1.2.2.2 bouyer 1093 1.2.2.2 bouyer #define FV_BACKOFFTHRESH 1 /* backoff threshold interval in second */ 1094 1.2.2.2 bouyer #define FV_TTHRESH 3 /* time threshold to delete fve */ 1095 1.2.2.2 bouyer #define FV_ALPHA 5 /* extra packet count */ 1096 1.2.2.2 bouyer 1097 1.2.2.2 bouyer #define FV_STATS 1098 1.2.2.2 bouyer 1099 1.2.2.2 bouyer #if (__FreeBSD_version > 300000) 1100 1.2.2.2 bouyer #define FV_TIMESTAMP(tp) getmicrotime(tp) 1101 1.2.2.2 bouyer #else 1102 1.2.2.2 bouyer #define FV_TIMESTAMP(tp) { (*(tp)) = time; } 1103 1.2.2.2 bouyer #endif 1104 1.2.2.2 bouyer 1105 1.2.2.2 bouyer /* 1106 1.2.2.2 bouyer * Brtt table: 127 entry table to convert drop rate (p) to 1107 1.2.2.2 bouyer * the corresponding bandwidth fraction (f) 1108 1.2.2.2 bouyer * the following equation is implemented to use scaled values, 1109 1.2.2.2 bouyer * fve_p and fve_f, in the fixed point format. 1110 1.2.2.2 bouyer * 1111 1.2.2.2 bouyer * Brtt(p) = 1 /(sqrt(4*p/3) + min(1,3*sqrt(p*6/8)) * p * (1+32 * p*p)) 1112 1.2.2.2 bouyer * f = Brtt(p) / (max_th + alpha) 1113 1.2.2.2 bouyer */ 1114 1.2.2.2 bouyer #define BRTT_SIZE 128 1115 1.2.2.2 bouyer #define BRTT_SHIFT 12 1116 1.2.2.2 bouyer #define BRTT_MASK 0x0007f000 1117 1.2.2.2 bouyer #define BRTT_PMAX (1 << (FV_PSHIFT + FP_SHIFT)) 1118 1.2.2.2 bouyer 1119 1.2.2.2 bouyer const int brtt_tab[BRTT_SIZE] = { 1120 1.2.2.2 bouyer 0, 1262010, 877019, 703694, 598706, 525854, 471107, 427728, 1121 1.2.2.2 bouyer 392026, 361788, 335598, 312506, 291850, 273158, 256081, 240361, 1122 1.2.2.2 bouyer 225800, 212247, 199585, 187788, 178388, 169544, 161207, 153333, 1123 1.2.2.2 bouyer 145888, 138841, 132165, 125836, 119834, 114141, 108739, 103612, 1124 1.2.2.2 bouyer 98747, 94129, 89746, 85585, 81637, 77889, 74333, 70957, 1125 1.2.2.2 bouyer 67752, 64711, 61824, 59084, 56482, 54013, 51667, 49440, 1126 1.2.2.2 bouyer 47325, 45315, 43406, 41591, 39866, 38227, 36667, 35184, 1127 1.2.2.2 bouyer 33773, 32430, 31151, 29933, 28774, 27668, 26615, 25611, 1128 1.2.2.2 bouyer 24653, 23740, 22868, 22035, 21240, 20481, 19755, 19062, 1129 1.2.2.2 bouyer 18399, 17764, 17157, 16576, 16020, 15487, 14976, 14487, 1130 1.2.2.2 bouyer 14017, 13567, 13136, 12721, 12323, 11941, 11574, 11222, 1131 1.2.2.2 bouyer 10883, 10557, 10243, 9942, 9652, 9372, 9103, 8844, 1132 1.2.2.2 bouyer 8594, 8354, 8122, 7898, 7682, 7474, 7273, 7079, 1133 1.2.2.2 bouyer 6892, 6711, 6536, 6367, 6204, 6046, 5893, 5746, 1134 1.2.2.2 bouyer 5603, 5464, 5330, 5201, 5075, 4954, 4836, 4722, 1135 1.2.2.2 bouyer 4611, 4504, 4400, 4299, 4201, 4106, 4014, 3924 1136 1.2.2.2 bouyer }; 1137 1.2.2.2 bouyer 1138 1.2.2.2 bouyer static __inline struct fve * 1139 1.2.2.2 bouyer flowlist_lookup(fv, pktattr, now) 1140 1.2.2.2 bouyer struct flowvalve *fv; 1141 1.2.2.2 bouyer struct altq_pktattr *pktattr; 1142 1.2.2.2 bouyer struct timeval *now; 1143 1.2.2.2 bouyer { 1144 1.2.2.2 bouyer struct fve *fve; 1145 1.2.2.2 bouyer int flows; 1146 1.2.2.2 bouyer struct ip *ip; 1147 1.2.2.2 bouyer #ifdef INET6 1148 1.2.2.2 bouyer struct ip6_hdr *ip6; 1149 1.2.2.2 bouyer #endif 1150 1.2.2.2 bouyer struct timeval tthresh; 1151 1.2.2.2 bouyer 1152 1.2.2.2 bouyer if (pktattr == NULL) 1153 1.2.2.2 bouyer return (NULL); 1154 1.2.2.2 bouyer 1155 1.2.2.2 bouyer tthresh.tv_sec = now->tv_sec - FV_TTHRESH; 1156 1.2.2.2 bouyer flows = 0; 1157 1.2.2.2 bouyer /* 1158 1.2.2.2 bouyer * search the flow list 1159 1.2.2.2 bouyer */ 1160 1.2.2.2 bouyer switch (pktattr->pattr_af) { 1161 1.2.2.2 bouyer case AF_INET: 1162 1.2.2.2 bouyer ip = (struct ip *)pktattr->pattr_hdr; 1163 1.2.2.2 bouyer TAILQ_FOREACH(fve, &fv->fv_flowlist, fve_lru){ 1164 1.2.2.2 bouyer if (fve->fve_lastdrop.tv_sec == 0) 1165 1.2.2.2 bouyer break; 1166 1.2.2.2 bouyer if (fve->fve_lastdrop.tv_sec < tthresh.tv_sec) { 1167 1.2.2.2 bouyer fve->fve_lastdrop.tv_sec = 0; 1168 1.2.2.2 bouyer break; 1169 1.2.2.2 bouyer } 1170 1.2.2.2 bouyer if (fve->fve_flow.flow_af == AF_INET && 1171 1.2.2.2 bouyer fve->fve_flow.flow_ip.ip_src.s_addr == 1172 1.2.2.2 bouyer ip->ip_src.s_addr && 1173 1.2.2.2 bouyer fve->fve_flow.flow_ip.ip_dst.s_addr == 1174 1.2.2.2 bouyer ip->ip_dst.s_addr) 1175 1.2.2.2 bouyer return (fve); 1176 1.2.2.2 bouyer flows++; 1177 1.2.2.2 bouyer } 1178 1.2.2.2 bouyer break; 1179 1.2.2.2 bouyer #ifdef INET6 1180 1.2.2.2 bouyer case AF_INET6: 1181 1.2.2.2 bouyer ip6 = (struct ip6_hdr *)pktattr->pattr_hdr; 1182 1.2.2.2 bouyer TAILQ_FOREACH(fve, &fv->fv_flowlist, fve_lru){ 1183 1.2.2.2 bouyer if (fve->fve_lastdrop.tv_sec == 0) 1184 1.2.2.2 bouyer break; 1185 1.2.2.2 bouyer if (fve->fve_lastdrop.tv_sec < tthresh.tv_sec) { 1186 1.2.2.2 bouyer fve->fve_lastdrop.tv_sec = 0; 1187 1.2.2.2 bouyer break; 1188 1.2.2.2 bouyer } 1189 1.2.2.2 bouyer if (fve->fve_flow.flow_af == AF_INET6 && 1190 1.2.2.2 bouyer IN6_ARE_ADDR_EQUAL(&fve->fve_flow.flow_ip6.ip6_src, 1191 1.2.2.2 bouyer &ip6->ip6_src) && 1192 1.2.2.2 bouyer IN6_ARE_ADDR_EQUAL(&fve->fve_flow.flow_ip6.ip6_dst, 1193 1.2.2.2 bouyer &ip6->ip6_dst)) 1194 1.2.2.2 bouyer return (fve); 1195 1.2.2.2 bouyer flows++; 1196 1.2.2.2 bouyer } 1197 1.2.2.2 bouyer break; 1198 1.2.2.2 bouyer #endif /* INET6 */ 1199 1.2.2.2 bouyer 1200 1.2.2.2 bouyer default: 1201 1.2.2.2 bouyer /* unknown protocol. no drop. */ 1202 1.2.2.2 bouyer return (NULL); 1203 1.2.2.2 bouyer } 1204 1.2.2.2 bouyer fv->fv_flows = flows; /* save the number of active fve's */ 1205 1.2.2.2 bouyer return (NULL); 1206 1.2.2.2 bouyer } 1207 1.2.2.2 bouyer 1208 1.2.2.2 bouyer static __inline struct fve * 1209 1.2.2.2 bouyer flowlist_reclaim(fv, pktattr) 1210 1.2.2.2 bouyer struct flowvalve *fv; 1211 1.2.2.2 bouyer struct altq_pktattr *pktattr; 1212 1.2.2.2 bouyer { 1213 1.2.2.2 bouyer struct fve *fve; 1214 1.2.2.2 bouyer struct ip *ip; 1215 1.2.2.2 bouyer #ifdef INET6 1216 1.2.2.2 bouyer struct ip6_hdr *ip6; 1217 1.2.2.2 bouyer #endif 1218 1.2.2.2 bouyer 1219 1.2.2.2 bouyer /* 1220 1.2.2.2 bouyer * get an entry from the tail of the LRU list. 1221 1.2.2.2 bouyer */ 1222 1.2.2.2 bouyer fve = TAILQ_LAST(&fv->fv_flowlist, fv_flowhead); 1223 1.2.2.2 bouyer 1224 1.2.2.2 bouyer switch (pktattr->pattr_af) { 1225 1.2.2.2 bouyer case AF_INET: 1226 1.2.2.2 bouyer ip = (struct ip *)pktattr->pattr_hdr; 1227 1.2.2.2 bouyer fve->fve_flow.flow_af = AF_INET; 1228 1.2.2.2 bouyer fve->fve_flow.flow_ip.ip_src = ip->ip_src; 1229 1.2.2.2 bouyer fve->fve_flow.flow_ip.ip_dst = ip->ip_dst; 1230 1.2.2.2 bouyer break; 1231 1.2.2.2 bouyer #ifdef INET6 1232 1.2.2.2 bouyer case AF_INET6: 1233 1.2.2.2 bouyer ip6 = (struct ip6_hdr *)pktattr->pattr_hdr; 1234 1.2.2.2 bouyer fve->fve_flow.flow_af = AF_INET6; 1235 1.2.2.2 bouyer fve->fve_flow.flow_ip6.ip6_src = ip6->ip6_src; 1236 1.2.2.2 bouyer fve->fve_flow.flow_ip6.ip6_dst = ip6->ip6_dst; 1237 1.2.2.2 bouyer break; 1238 1.2.2.2 bouyer #endif 1239 1.2.2.2 bouyer } 1240 1.2.2.2 bouyer 1241 1.2.2.2 bouyer fve->fve_state = Green; 1242 1.2.2.2 bouyer fve->fve_p = 0.0; 1243 1.2.2.2 bouyer fve->fve_f = 0.0; 1244 1.2.2.2 bouyer fve->fve_ifseq = fv->fv_ifseq - 1; 1245 1.2.2.2 bouyer fve->fve_count = 0; 1246 1.2.2.2 bouyer 1247 1.2.2.2 bouyer fv->fv_flows++; 1248 1.2.2.2 bouyer #ifdef FV_STATS 1249 1.2.2.2 bouyer fv->fv_stats.alloc++; 1250 1.2.2.2 bouyer #endif 1251 1.2.2.2 bouyer return (fve); 1252 1.2.2.2 bouyer } 1253 1.2.2.2 bouyer 1254 1.2.2.2 bouyer static __inline void 1255 1.2.2.2 bouyer flowlist_move_to_head(fv, fve) 1256 1.2.2.2 bouyer struct flowvalve *fv; 1257 1.2.2.2 bouyer struct fve *fve; 1258 1.2.2.2 bouyer { 1259 1.2.2.2 bouyer if (TAILQ_FIRST(&fv->fv_flowlist) != fve) { 1260 1.2.2.2 bouyer TAILQ_REMOVE(&fv->fv_flowlist, fve, fve_lru); 1261 1.2.2.2 bouyer TAILQ_INSERT_HEAD(&fv->fv_flowlist, fve, fve_lru); 1262 1.2.2.2 bouyer } 1263 1.2.2.2 bouyer } 1264 1.2.2.2 bouyer 1265 1.2.2.2 bouyer /* 1266 1.2.2.2 bouyer * allocate flowvalve structure 1267 1.2.2.2 bouyer */ 1268 1.2.2.2 bouyer static struct flowvalve * 1269 1.2.2.2 bouyer fv_alloc(rp) 1270 1.2.2.2 bouyer struct red *rp; 1271 1.2.2.2 bouyer { 1272 1.2.2.2 bouyer struct flowvalve *fv; 1273 1.2.2.2 bouyer struct fve *fve; 1274 1.2.2.2 bouyer int i, num; 1275 1.2.2.2 bouyer 1276 1.2.2.2 bouyer num = FV_FLOWLISTSIZE; 1277 1.2.2.2 bouyer MALLOC(fv, struct flowvalve *, sizeof(struct flowvalve), 1278 1.2.2.2 bouyer M_DEVBUF, M_WAITOK); 1279 1.2.2.2 bouyer if (fv == NULL) 1280 1.2.2.2 bouyer return (NULL); 1281 1.2.2.2 bouyer bzero(fv, sizeof(struct flowvalve)); 1282 1.2.2.2 bouyer 1283 1.2.2.2 bouyer MALLOC(fv->fv_fves, struct fve *, sizeof(struct fve) * num, 1284 1.2.2.2 bouyer M_DEVBUF, M_WAITOK); 1285 1.2.2.2 bouyer if (fv->fv_fves == NULL) { 1286 1.2.2.2 bouyer FREE(fv, M_DEVBUF); 1287 1.2.2.2 bouyer return (NULL); 1288 1.2.2.2 bouyer } 1289 1.2.2.2 bouyer bzero(fv->fv_fves, sizeof(struct fve) * num); 1290 1.2.2.2 bouyer 1291 1.2.2.2 bouyer fv->fv_flows = 0; 1292 1.2.2.2 bouyer TAILQ_INIT(&fv->fv_flowlist); 1293 1.2.2.2 bouyer for (i = 0; i < num; i++) { 1294 1.2.2.2 bouyer fve = &fv->fv_fves[i]; 1295 1.2.2.2 bouyer fve->fve_lastdrop.tv_sec = 0; 1296 1.2.2.2 bouyer TAILQ_INSERT_TAIL(&fv->fv_flowlist, fve, fve_lru); 1297 1.2.2.2 bouyer } 1298 1.2.2.2 bouyer 1299 1.2.2.2 bouyer /* initialize drop rate threshold in scaled fixed-point */ 1300 1.2.2.2 bouyer fv->fv_pthresh = (FV_PSCALE(1) << FP_SHIFT) / rp->red_inv_pmax; 1301 1.2.2.2 bouyer 1302 1.2.2.2 bouyer /* initialize drop rate to fraction table */ 1303 1.2.2.2 bouyer MALLOC(fv->fv_p2ftab, int *, sizeof(int) * BRTT_SIZE, 1304 1.2.2.2 bouyer M_DEVBUF, M_WAITOK); 1305 1.2.2.2 bouyer if (fv->fv_p2ftab == NULL) { 1306 1.2.2.2 bouyer FREE(fv->fv_fves, M_DEVBUF); 1307 1.2.2.2 bouyer FREE(fv, M_DEVBUF); 1308 1.2.2.2 bouyer return (NULL); 1309 1.2.2.2 bouyer } 1310 1.2.2.2 bouyer /* 1311 1.2.2.2 bouyer * create the p2f table. 1312 1.2.2.2 bouyer * (shift is used to keep the precision) 1313 1.2.2.2 bouyer */ 1314 1.2.2.2 bouyer for (i = 1; i < BRTT_SIZE; i++) { 1315 1.2.2.2 bouyer int f; 1316 1.2.2.2 bouyer 1317 1.2.2.2 bouyer f = brtt_tab[i] << 8; 1318 1.2.2.2 bouyer fv->fv_p2ftab[i] = (f / (rp->red_thmax + FV_ALPHA)) >> 8; 1319 1.2.2.2 bouyer } 1320 1.2.2.2 bouyer 1321 1.2.2.2 bouyer return (fv); 1322 1.2.2.2 bouyer } 1323 1.2.2.2 bouyer 1324 1.2.2.2 bouyer static void fv_destroy(fv) 1325 1.2.2.2 bouyer struct flowvalve *fv; 1326 1.2.2.2 bouyer { 1327 1.2.2.2 bouyer FREE(fv->fv_p2ftab, M_DEVBUF); 1328 1.2.2.2 bouyer FREE(fv->fv_fves, M_DEVBUF); 1329 1.2.2.2 bouyer FREE(fv, M_DEVBUF); 1330 1.2.2.2 bouyer } 1331 1.2.2.2 bouyer 1332 1.2.2.2 bouyer static __inline int 1333 1.2.2.2 bouyer fv_p2f(fv, p) 1334 1.2.2.2 bouyer struct flowvalve *fv; 1335 1.2.2.2 bouyer int p; 1336 1.2.2.2 bouyer { 1337 1.2.2.2 bouyer int val, f; 1338 1.2.2.2 bouyer 1339 1.2.2.2 bouyer if (p >= BRTT_PMAX) 1340 1.2.2.2 bouyer f = fv->fv_p2ftab[BRTT_SIZE-1]; 1341 1.2.2.2 bouyer else if ((val = (p & BRTT_MASK))) 1342 1.2.2.2 bouyer f = fv->fv_p2ftab[(val >> BRTT_SHIFT)]; 1343 1.2.2.2 bouyer else 1344 1.2.2.2 bouyer f = fv->fv_p2ftab[1]; 1345 1.2.2.2 bouyer return (f); 1346 1.2.2.2 bouyer } 1347 1.2.2.2 bouyer 1348 1.2.2.2 bouyer /* 1349 1.2.2.2 bouyer * check if an arriving packet should be pre-dropped. 1350 1.2.2.2 bouyer * called from red_addq() when a packet arrives. 1351 1.2.2.2 bouyer * returns 1 when the packet should be pre-dropped. 1352 1.2.2.2 bouyer * should be called in splimp. 1353 1.2.2.2 bouyer */ 1354 1.2.2.2 bouyer static int 1355 1.2.2.2 bouyer fv_checkflow(fv, pktattr, fcache) 1356 1.2.2.2 bouyer struct flowvalve *fv; 1357 1.2.2.2 bouyer struct altq_pktattr *pktattr; 1358 1.2.2.2 bouyer struct fve **fcache; 1359 1.2.2.2 bouyer { 1360 1.2.2.2 bouyer struct fve *fve; 1361 1.2.2.2 bouyer struct timeval now; 1362 1.2.2.2 bouyer 1363 1.2.2.2 bouyer fv->fv_ifseq++; 1364 1.2.2.2 bouyer FV_TIMESTAMP(&now); 1365 1.2.2.2 bouyer 1366 1.2.2.2 bouyer if ((fve = flowlist_lookup(fv, pktattr, &now)) == NULL) 1367 1.2.2.2 bouyer /* no matching entry in the flowlist */ 1368 1.2.2.2 bouyer return (0); 1369 1.2.2.2 bouyer 1370 1.2.2.2 bouyer *fcache = fve; 1371 1.2.2.2 bouyer 1372 1.2.2.2 bouyer /* update fraction f for every FV_N packets */ 1373 1.2.2.2 bouyer if (++fve->fve_count == FV_N) { 1374 1.2.2.2 bouyer /* 1375 1.2.2.2 bouyer * f = Wf * N / (fv_ifseq - fve_ifseq) + (1 - Wf) * f 1376 1.2.2.2 bouyer */ 1377 1.2.2.2 bouyer fve->fve_f = 1378 1.2.2.2 bouyer (FV_N << FP_SHIFT) / (fv->fv_ifseq - fve->fve_ifseq) 1379 1.2.2.2 bouyer + fve->fve_f - FV_FUNSCALE(fve->fve_f); 1380 1.2.2.2 bouyer fve->fve_ifseq = fv->fv_ifseq; 1381 1.2.2.2 bouyer fve->fve_count = 0; 1382 1.2.2.2 bouyer } 1383 1.2.2.2 bouyer 1384 1.2.2.2 bouyer /* 1385 1.2.2.2 bouyer * overpumping test 1386 1.2.2.2 bouyer */ 1387 1.2.2.2 bouyer if (fve->fve_state == Green && fve->fve_p > fv->fv_pthresh) { 1388 1.2.2.2 bouyer int fthresh; 1389 1.2.2.2 bouyer 1390 1.2.2.2 bouyer /* calculate a threshold */ 1391 1.2.2.2 bouyer fthresh = fv_p2f(fv, fve->fve_p); 1392 1.2.2.2 bouyer if (fve->fve_f > fthresh) 1393 1.2.2.2 bouyer fve->fve_state = Red; 1394 1.2.2.2 bouyer } 1395 1.2.2.2 bouyer 1396 1.2.2.2 bouyer if (fve->fve_state == Red) { 1397 1.2.2.2 bouyer /* 1398 1.2.2.2 bouyer * backoff test 1399 1.2.2.2 bouyer */ 1400 1.2.2.2 bouyer if (now.tv_sec - fve->fve_lastdrop.tv_sec > FV_BACKOFFTHRESH) { 1401 1.2.2.2 bouyer /* no drop for at least FV_BACKOFFTHRESH sec */ 1402 1.2.2.2 bouyer fve->fve_p = 0; 1403 1.2.2.2 bouyer fve->fve_state = Green; 1404 1.2.2.2 bouyer #ifdef FV_STATS 1405 1.2.2.2 bouyer fv->fv_stats.escape++; 1406 1.2.2.2 bouyer #endif 1407 1.2.2.2 bouyer } else { 1408 1.2.2.2 bouyer /* block this flow */ 1409 1.2.2.2 bouyer flowlist_move_to_head(fv, fve); 1410 1.2.2.2 bouyer fve->fve_lastdrop = now; 1411 1.2.2.2 bouyer #ifdef FV_STATS 1412 1.2.2.2 bouyer fv->fv_stats.predrop++; 1413 1.2.2.2 bouyer #endif 1414 1.2.2.2 bouyer return (1); 1415 1.2.2.2 bouyer } 1416 1.2.2.2 bouyer } 1417 1.2.2.2 bouyer 1418 1.2.2.2 bouyer /* 1419 1.2.2.2 bouyer * p = (1 - Wp) * p 1420 1.2.2.2 bouyer */ 1421 1.2.2.2 bouyer fve->fve_p -= FV_PUNSCALE(fve->fve_p); 1422 1.2.2.2 bouyer if (fve->fve_p < 0) 1423 1.2.2.2 bouyer fve->fve_p = 0; 1424 1.2.2.2 bouyer #ifdef FV_STATS 1425 1.2.2.2 bouyer fv->fv_stats.pass++; 1426 1.2.2.2 bouyer #endif 1427 1.2.2.2 bouyer return (0); 1428 1.2.2.2 bouyer } 1429 1.2.2.2 bouyer 1430 1.2.2.2 bouyer /* 1431 1.2.2.2 bouyer * called from red_addq when a packet is dropped by red. 1432 1.2.2.2 bouyer * should be called in splimp. 1433 1.2.2.2 bouyer */ 1434 1.2.2.2 bouyer static void fv_dropbyred(fv, pktattr, fcache) 1435 1.2.2.2 bouyer struct flowvalve *fv; 1436 1.2.2.2 bouyer struct altq_pktattr *pktattr; 1437 1.2.2.2 bouyer struct fve *fcache; 1438 1.2.2.2 bouyer { 1439 1.2.2.2 bouyer struct fve *fve; 1440 1.2.2.2 bouyer struct timeval now; 1441 1.2.2.2 bouyer 1442 1.2.2.2 bouyer if (pktattr == NULL) 1443 1.2.2.2 bouyer return; 1444 1.2.2.2 bouyer FV_TIMESTAMP(&now); 1445 1.2.2.2 bouyer 1446 1.2.2.2 bouyer if (fcache != NULL) 1447 1.2.2.2 bouyer /* the fve of this packet is already cached */ 1448 1.2.2.2 bouyer fve = fcache; 1449 1.2.2.2 bouyer else if ((fve = flowlist_lookup(fv, pktattr, &now)) == NULL) 1450 1.2.2.2 bouyer fve = flowlist_reclaim(fv, pktattr); 1451 1.2.2.2 bouyer 1452 1.2.2.2 bouyer flowlist_move_to_head(fv, fve); 1453 1.2.2.2 bouyer 1454 1.2.2.2 bouyer /* 1455 1.2.2.2 bouyer * update p: the following line cancels the update 1456 1.2.2.2 bouyer * in fv_checkflow() and calculate 1457 1.2.2.2 bouyer * p = Wp + (1 - Wp) * p 1458 1.2.2.2 bouyer */ 1459 1.2.2.2 bouyer fve->fve_p = (1 << FP_SHIFT) + fve->fve_p; 1460 1.2.2.2 bouyer 1461 1.2.2.2 bouyer fve->fve_lastdrop = now; 1462 1.2.2.2 bouyer } 1463 1.2.2.2 bouyer 1464 1.2.2.2 bouyer #endif /* ALTQ_FLOWVALVE */ 1465 1.2.2.2 bouyer 1466 1.2.2.2 bouyer #ifdef KLD_MODULE 1467 1.2.2.2 bouyer 1468 1.2.2.2 bouyer static struct altqsw red_sw = 1469 1.2.2.2 bouyer {"red", redopen, redclose, redioctl}; 1470 1.2.2.2 bouyer 1471 1.2.2.2 bouyer ALTQ_MODULE(altq_red, ALTQT_RED, &red_sw); 1472 1.2.2.2 bouyer 1473 1.2.2.2 bouyer #endif /* KLD_MODULE */ 1474 1.2.2.2 bouyer 1475 1.2.2.2 bouyer #endif /* ALTQ_RED */ 1476
Indexes created Mon Oct 27 08:10:08 GMT 2025