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