1 /* 2 * Codel - The Controlled-Delay Active Queue Management algorithm. 3 * 4 * $FreeBSD$ 5 * 6 * Copyright (C) 2016 Centre for Advanced Internet Architectures, 7 * Swinburne University of Technology, Melbourne, Australia. 8 * Portions of this code were made possible in part by a gift from 9 * The Comcast Innovation Fund. 10 * Implemented by Rasool Al-Saadi <ralsaadi@swin.edu.au> 11 * 12 * Redistribution and use in source and binary forms, with or without 13 * modification, are permitted provided that the following conditions 14 * are met: 15 * 1. Redistributions of source code must retain the above copyright 16 * notice, this list of conditions and the following disclaimer. 17 * 2. Redistributions in binary form must reproduce the above copyright 18 * notice, this list of conditions and the following disclaimer in the 19 * documentation and/or other materials provided with the distribution. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 * SUCH DAMAGE. 32 */ 33 34 #include <sys/cdefs.h> 35 #include "opt_inet6.h" 36 37 #include <sys/param.h> 38 #include <sys/systm.h> 39 #include <sys/malloc.h> 40 #include <sys/mbuf.h> 41 #include <sys/kernel.h> 42 #include <sys/lock.h> 43 #include <sys/module.h> 44 #include <sys/priv.h> 45 #include <sys/proc.h> 46 #include <sys/rwlock.h> 47 #include <sys/socket.h> 48 #include <sys/time.h> 49 #include <sys/sysctl.h> 50 51 #include <net/if.h> /* IFNAMSIZ, struct ifaddr, ifq head, lock.h mutex.h */ 52 #include <net/netisr.h> 53 #include <net/vnet.h> 54 55 #include <netinet/in.h> 56 #include <netinet/ip.h> /* ip_len, ip_off */ 57 #include <netinet/ip_var.h> /* ip_output(), IP_FORWARDING */ 58 #include <netinet/ip_fw.h> 59 #include <netinet/ip_dummynet.h> 60 #include <netinet/if_ether.h> /* various ether_* routines */ 61 #include <netinet/ip6.h> /* for ip6_input, ip6_output prototypes */ 62 #include <netinet6/ip6_var.h> 63 #include <netpfil/ipfw/dn_heap.h> 64 65 #ifdef NEW_AQM 66 #include <netpfil/ipfw/ip_fw_private.h> 67 #include <netpfil/ipfw/ip_dn_private.h> 68 #include <netpfil/ipfw/dn_aqm.h> 69 #include <netpfil/ipfw/dn_aqm_codel.h> 70 #include <netpfil/ipfw/dn_sched.h> 71 72 #define DN_AQM_CODEL 1 73 74 static struct dn_aqm codel_desc; 75 76 /* default codel parameters */ 77 struct dn_aqm_codel_parms codel_sysctl = {5000 * AQM_TIME_1US, 78 100000 * AQM_TIME_1US, 0}; 79 80 static int 81 codel_sysctl_interval_handler(SYSCTL_HANDLER_ARGS) 82 { 83 int error; 84 long value; 85 86 value = codel_sysctl.interval; 87 value /= AQM_TIME_1US; 88 error = sysctl_handle_long(oidp, &value, 0, req); 89 if (error != 0 || req->newptr == NULL) 90 return (error); 91 if (value < 1 || value > 100 * AQM_TIME_1S) 92 return (EINVAL); 93 codel_sysctl.interval = value * AQM_TIME_1US ; 94 return (0); 95 } 96 97 static int 98 codel_sysctl_target_handler(SYSCTL_HANDLER_ARGS) 99 { 100 int error; 101 long value; 102 103 value = codel_sysctl.target; 104 value /= AQM_TIME_1US; 105 error = sysctl_handle_long(oidp, &value, 0, req); 106 if (error != 0 || req->newptr == NULL) 107 return (error); 108 D("%ld", value); 109 if (value < 1 || value > 5 * AQM_TIME_1S) 110 return (EINVAL); 111 codel_sysctl.target = value * AQM_TIME_1US ; 112 return (0); 113 } 114 115 /* defining Codel sysctl variables */ 116 SYSBEGIN(f4) 117 118 SYSCTL_DECL(_net_inet); 119 SYSCTL_DECL(_net_inet_ip); 120 SYSCTL_DECL(_net_inet_ip_dummynet); 121 static SYSCTL_NODE(_net_inet_ip_dummynet, OID_AUTO, codel, 122 CTLFLAG_RW | CTLFLAG_MPSAFE, 0, 123 "CODEL"); 124 125 #ifdef SYSCTL_NODE 126 SYSCTL_PROC(_net_inet_ip_dummynet_codel, OID_AUTO, target, 127 CTLTYPE_LONG | CTLFLAG_RW | CTLFLAG_NEEDGIANT, 128 NULL, 0,codel_sysctl_target_handler, "L", 129 "CoDel target in microsecond"); 130 131 SYSCTL_PROC(_net_inet_ip_dummynet_codel, OID_AUTO, interval, 132 CTLTYPE_LONG | CTLFLAG_RW | CTLFLAG_NEEDGIANT, 133 NULL, 0, codel_sysctl_interval_handler, "L", 134 "CoDel interval in microsecond"); 135 #endif 136 137 /* This function computes codel_interval/sqrt(count) 138 * Newton's method of approximation is used to compute 1/sqrt(count). 139 * http://betterexplained.com/articles/ 140 * understanding-quakes-fast-inverse-square-root/ 141 */ 142 aqm_time_t 143 control_law(struct codel_status *cst, struct dn_aqm_codel_parms *cprms, 144 aqm_time_t t) 145 { 146 uint32_t count; 147 uint64_t temp; 148 count = cst->count; 149 150 /* we don't calculate isqrt(1) to get more accurate result*/ 151 if (count == 1) { 152 /* prepare isqrt (old guess) for the next iteration i.e. 1/sqrt(2)*/ 153 cst->isqrt = (1UL<< FIX_POINT_BITS) * 7/10; 154 /* return time + isqrt(1)*interval */ 155 return t + cprms->interval; 156 } 157 158 /* newguess = g(1.5 - 0.5*c*g^2) 159 * Multiplying both sides by 2 to make all the constants intergers 160 * newguess * 2 = g(3 - c*g^2) g=old guess, c=count 161 * So, newguess = newguess /2 162 * Fixed point operations are used here. 163 */ 164 165 /* Calculate g^2 */ 166 temp = (uint32_t) cst->isqrt * cst->isqrt; 167 /* Calculate (3 - c*g^2) i.e. (3 - c * temp) */ 168 temp = (3ULL<< (FIX_POINT_BITS*2)) - (count * temp); 169 170 /* 171 * Divide by 2 because we multiplied the original equation by two 172 * Also, we shift the result by 8 bits to prevent overflow. 173 * */ 174 temp >>= (1 + 8); 175 176 /* Now, temp = (1.5 - 0.5*c*g^2) 177 * Calculate g (1.5 - 0.5*c*g^2) i.e. g * temp 178 */ 179 temp = (cst->isqrt * temp) >> (FIX_POINT_BITS + FIX_POINT_BITS - 8); 180 cst->isqrt = temp; 181 182 /* calculate codel_interval/sqrt(count) */ 183 return t + ((cprms->interval * temp) >> FIX_POINT_BITS); 184 } 185 186 /* 187 * Extract a packet from the head of queue 'q' 188 * Return a packet or NULL if the queue is empty. 189 * Also extract packet's timestamp from mtag. 190 */ 191 struct mbuf * 192 codel_extract_head(struct dn_queue *q, aqm_time_t *pkt_ts) 193 { 194 struct m_tag *mtag; 195 struct mbuf *m = q->mq.head; 196 197 if (m == NULL) 198 return m; 199 q->mq.head = m->m_nextpkt; 200 201 /* Update stats */ 202 update_stats(q, -m->m_pkthdr.len, 0); 203 204 if (q->ni.length == 0) /* queue is now idle */ 205 q->q_time = dn_cfg.curr_time; 206 207 /* extract packet TS*/ 208 mtag = m_tag_locate(m, MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, NULL); 209 if (mtag == NULL) { 210 D("Codel timestamp mtag not found!"); 211 *pkt_ts = 0; 212 } else { 213 *pkt_ts = *(aqm_time_t *)(mtag + 1); 214 m_tag_delete(m,mtag); 215 } 216 217 return m; 218 } 219 220 /* 221 * Enqueue a packet 'm' in queue 'q' 222 */ 223 static int 224 aqm_codel_enqueue(struct dn_queue *q, struct mbuf *m) 225 { 226 struct dn_fs *f; 227 uint64_t len; 228 struct codel_status *cst; /*codel status variables */ 229 struct m_tag *mtag; 230 231 f = &(q->fs->fs); 232 len = m->m_pkthdr.len; 233 cst = q->aqm_status; 234 if(!cst) { 235 D("Codel queue is not initialized\n"); 236 goto drop; 237 } 238 239 /* Finding maximum packet size */ 240 // XXX we can get MTU from driver instead 241 if (len > cst->maxpkt_size) 242 cst->maxpkt_size = len; 243 244 /* check for queue size and drop the tail if exceed queue limit*/ 245 if (f->flags & DN_QSIZE_BYTES) { 246 if ( q->ni.len_bytes > f->qsize) 247 goto drop; 248 } 249 else { 250 if ( q->ni.length >= f->qsize) 251 goto drop; 252 } 253 254 /* Add timestamp as mtag */ 255 mtag = m_tag_locate(m, MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, NULL); 256 if (mtag == NULL) 257 mtag = m_tag_alloc(MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, 258 sizeof(aqm_time_t), M_NOWAIT); 259 if (mtag == NULL) { 260 m_freem(m); 261 goto drop; 262 } 263 264 *(aqm_time_t *)(mtag + 1) = AQM_UNOW; 265 m_tag_prepend(m, mtag); 266 267 mq_append(&q->mq, m); 268 update_stats(q, len, 0); 269 return (0); 270 271 drop: 272 update_stats(q, 0, 1); 273 FREE_PKT(m); 274 return (1); 275 } 276 277 278 /* Dequeue a pcaket from queue q */ 279 static struct mbuf * 280 aqm_codel_dequeue(struct dn_queue *q) 281 { 282 return codel_dequeue(q); 283 } 284 285 /* 286 * initialize Codel for queue 'q' 287 * First allocate memory for codel status. 288 */ 289 static int 290 aqm_codel_init(struct dn_queue *q) 291 { 292 struct codel_status *cst; 293 294 if (!q->fs->aqmcfg) { 295 D("Codel is not configure!d"); 296 return EINVAL; 297 } 298 299 q->aqm_status = malloc(sizeof(struct codel_status), 300 M_DUMMYNET, M_NOWAIT | M_ZERO); 301 if (q->aqm_status == NULL) { 302 D("Cannot allocate AQM_codel private data"); 303 return ENOMEM ; 304 } 305 306 /* init codel status variables */ 307 cst = q->aqm_status; 308 cst->dropping=0; 309 cst->first_above_time=0; 310 cst->drop_next_time=0; 311 cst->count=0; 312 cst->maxpkt_size = 500; 313 314 /* increase reference counters */ 315 codel_desc.ref_count++; 316 317 return 0; 318 } 319 320 /* 321 * Clean up Codel status for queue 'q' 322 * Destroy memory allocated for codel status. 323 */ 324 static int 325 aqm_codel_cleanup(struct dn_queue *q) 326 { 327 328 if (q && q->aqm_status) { 329 free(q->aqm_status, M_DUMMYNET); 330 q->aqm_status = NULL; 331 /* decrease reference counters */ 332 codel_desc.ref_count--; 333 } 334 else 335 D("Codel already cleaned up"); 336 return 0; 337 } 338 339 /* 340 * Config codel parameters 341 * also allocate memory for codel configurations 342 */ 343 static int 344 aqm_codel_config(struct dn_fsk* fs, struct dn_extra_parms *ep, int len) 345 { 346 struct dn_aqm_codel_parms *ccfg; 347 348 int l = sizeof(struct dn_extra_parms); 349 if (len < l) { 350 D("invalid sched parms length got %d need %d", len, l); 351 return EINVAL; 352 } 353 /* we free the old cfg because maybe the original allocation 354 * not the same size as the new one (different AQM type). 355 */ 356 if (fs->aqmcfg) { 357 free(fs->aqmcfg, M_DUMMYNET); 358 fs->aqmcfg = NULL; 359 } 360 361 fs->aqmcfg = malloc(sizeof(struct dn_aqm_codel_parms), 362 M_DUMMYNET, M_NOWAIT | M_ZERO); 363 if (fs->aqmcfg== NULL) { 364 D("cannot allocate AQM_codel configuration parameters"); 365 return ENOMEM; 366 } 367 368 /* configure codel parameters */ 369 ccfg = fs->aqmcfg; 370 371 if (ep->par[0] < 0) 372 ccfg->target = codel_sysctl.target; 373 else 374 ccfg->target = ep->par[0] * AQM_TIME_1US; 375 376 if (ep->par[1] < 0) 377 ccfg->interval = codel_sysctl.interval; 378 else 379 ccfg->interval = ep->par[1] * AQM_TIME_1US; 380 381 if (ep->par[2] < 0) 382 ccfg->flags = 0; 383 else 384 ccfg->flags = ep->par[2]; 385 386 /* bound codel configurations */ 387 ccfg->target = BOUND_VAR(ccfg->target,1, 5 * AQM_TIME_1S); 388 ccfg->interval = BOUND_VAR(ccfg->interval,1, 5 * AQM_TIME_1S); 389 /* increase config reference counter */ 390 codel_desc.cfg_ref_count++; 391 392 return 0; 393 } 394 395 /* 396 * Deconfigure Codel and free memory allocation 397 */ 398 static int 399 aqm_codel_deconfig(struct dn_fsk* fs) 400 { 401 402 if (fs && fs->aqmcfg) { 403 free(fs->aqmcfg, M_DUMMYNET); 404 fs->aqmcfg = NULL; 405 fs->aqmfp = NULL; 406 /* decrease config reference counter */ 407 codel_desc.cfg_ref_count--; 408 } 409 410 return 0; 411 } 412 413 /* 414 * Retrieve Codel configuration parameters. 415 */ 416 static int 417 aqm_codel_getconfig(struct dn_fsk *fs, struct dn_extra_parms * ep) 418 { 419 struct dn_aqm_codel_parms *ccfg; 420 421 if (fs->aqmcfg) { 422 strlcpy(ep->name, codel_desc.name, sizeof(ep->name)); 423 ccfg = fs->aqmcfg; 424 ep->par[0] = ccfg->target / AQM_TIME_1US; 425 ep->par[1] = ccfg->interval / AQM_TIME_1US; 426 ep->par[2] = ccfg->flags; 427 return 0; 428 } 429 return 1; 430 } 431 432 static struct dn_aqm codel_desc = { 433 _SI( .type = ) DN_AQM_CODEL, 434 _SI( .name = ) "CODEL", 435 _SI( .enqueue = ) aqm_codel_enqueue, 436 _SI( .dequeue = ) aqm_codel_dequeue, 437 _SI( .config = ) aqm_codel_config, 438 _SI( .getconfig = ) aqm_codel_getconfig, 439 _SI( .deconfig = ) aqm_codel_deconfig, 440 _SI( .init = ) aqm_codel_init, 441 _SI( .cleanup = ) aqm_codel_cleanup, 442 }; 443 444 DECLARE_DNAQM_MODULE(dn_aqm_codel, &codel_desc); 445 446 447 #endif 448