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 /* Dequeue a pcaket from queue q */ 278 static struct mbuf * 279 aqm_codel_dequeue(struct dn_queue *q) 280 { 281 return codel_dequeue(q); 282 } 283 284 /* 285 * initialize Codel for queue 'q' 286 * First allocate memory for codel status. 287 */ 288 static int 289 aqm_codel_init(struct dn_queue *q) 290 { 291 struct codel_status *cst; 292 293 if (!q->fs->aqmcfg) { 294 D("Codel is not configure!d"); 295 return EINVAL; 296 } 297 298 q->aqm_status = malloc(sizeof(struct codel_status), 299 M_DUMMYNET, M_NOWAIT | M_ZERO); 300 if (q->aqm_status == NULL) { 301 D("Cannot allocate AQM_codel private data"); 302 return ENOMEM ; 303 } 304 305 /* init codel status variables */ 306 cst = q->aqm_status; 307 cst->dropping=0; 308 cst->first_above_time=0; 309 cst->drop_next_time=0; 310 cst->count=0; 311 cst->maxpkt_size = 500; 312 313 /* increase reference counters */ 314 codel_desc.ref_count++; 315 316 return 0; 317 } 318 319 /* 320 * Clean up Codel status for queue 'q' 321 * Destroy memory allocated for codel status. 322 */ 323 static int 324 aqm_codel_cleanup(struct dn_queue *q) 325 { 326 327 if (q && q->aqm_status) { 328 free(q->aqm_status, M_DUMMYNET); 329 q->aqm_status = NULL; 330 /* decrease reference counters */ 331 codel_desc.ref_count--; 332 } 333 else 334 D("Codel already cleaned up"); 335 return 0; 336 } 337 338 /* 339 * Config codel parameters 340 * also allocate memory for codel configurations 341 */ 342 static int 343 aqm_codel_config(struct dn_fsk* fs, struct dn_extra_parms *ep, int len) 344 { 345 struct dn_aqm_codel_parms *ccfg; 346 347 int l = sizeof(struct dn_extra_parms); 348 if (len < l) { 349 D("invalid sched parms length got %d need %d", len, l); 350 return EINVAL; 351 } 352 /* we free the old cfg because maybe the original allocation 353 * not the same size as the new one (different AQM type). 354 */ 355 if (fs->aqmcfg) { 356 free(fs->aqmcfg, M_DUMMYNET); 357 fs->aqmcfg = NULL; 358 } 359 360 fs->aqmcfg = malloc(sizeof(struct dn_aqm_codel_parms), 361 M_DUMMYNET, M_NOWAIT | M_ZERO); 362 if (fs->aqmcfg== NULL) { 363 D("cannot allocate AQM_codel configuration parameters"); 364 return ENOMEM; 365 } 366 367 /* configure codel parameters */ 368 ccfg = fs->aqmcfg; 369 370 if (ep->par[0] < 0) 371 ccfg->target = codel_sysctl.target; 372 else 373 ccfg->target = ep->par[0] * AQM_TIME_1US; 374 375 if (ep->par[1] < 0) 376 ccfg->interval = codel_sysctl.interval; 377 else 378 ccfg->interval = ep->par[1] * AQM_TIME_1US; 379 380 if (ep->par[2] < 0) 381 ccfg->flags = 0; 382 else 383 ccfg->flags = ep->par[2]; 384 385 /* bound codel configurations */ 386 ccfg->target = BOUND_VAR(ccfg->target,1, 5 * AQM_TIME_1S); 387 ccfg->interval = BOUND_VAR(ccfg->interval,1, 5 * AQM_TIME_1S); 388 /* increase config reference counter */ 389 codel_desc.cfg_ref_count++; 390 391 return 0; 392 } 393 394 /* 395 * Deconfigure Codel and free memory allocation 396 */ 397 static int 398 aqm_codel_deconfig(struct dn_fsk* fs) 399 { 400 401 if (fs && fs->aqmcfg) { 402 free(fs->aqmcfg, M_DUMMYNET); 403 fs->aqmcfg = NULL; 404 fs->aqmfp = NULL; 405 /* decrease config reference counter */ 406 codel_desc.cfg_ref_count--; 407 } 408 409 return 0; 410 } 411 412 /* 413 * Retrieve Codel configuration parameters. 414 */ 415 static int 416 aqm_codel_getconfig(struct dn_fsk *fs, struct dn_extra_parms * ep) 417 { 418 struct dn_aqm_codel_parms *ccfg; 419 420 if (fs->aqmcfg) { 421 strlcpy(ep->name, codel_desc.name, sizeof(ep->name)); 422 ccfg = fs->aqmcfg; 423 ep->par[0] = ccfg->target / AQM_TIME_1US; 424 ep->par[1] = ccfg->interval / AQM_TIME_1US; 425 ep->par[2] = ccfg->flags; 426 return 0; 427 } 428 return 1; 429 } 430 431 static struct dn_aqm codel_desc = { 432 _SI( .type = ) DN_AQM_CODEL, 433 _SI( .name = ) "CODEL", 434 _SI( .enqueue = ) aqm_codel_enqueue, 435 _SI( .dequeue = ) aqm_codel_dequeue, 436 _SI( .config = ) aqm_codel_config, 437 _SI( .getconfig = ) aqm_codel_getconfig, 438 _SI( .deconfig = ) aqm_codel_deconfig, 439 _SI( .init = ) aqm_codel_init, 440 _SI( .cleanup = ) aqm_codel_cleanup, 441 }; 442 443 DECLARE_DNAQM_MODULE(dn_aqm_codel, &codel_desc); 444 445 #endif 446