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; 196 197 next: m = q->mq.head; 198 if (m == NULL) 199 return m; 200 q->mq.head = m->m_nextpkt; 201 202 /* Update stats */ 203 update_stats(q, -m->m_pkthdr.len, 0); 204 205 if (q->ni.length == 0) /* queue is now idle */ 206 q->q_time = V_dn_cfg.curr_time; 207 208 /* extract packet TS*/ 209 mtag = m_tag_locate(m, MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, NULL); 210 if (mtag == NULL) { 211 D("Codel timestamp mtag not found!"); 212 *pkt_ts = 0; 213 } else { 214 *pkt_ts = *(aqm_time_t *)(mtag + 1); 215 m_tag_delete(m,mtag); 216 } 217 if (m->m_pkthdr.rcvif != NULL && 218 __predict_false(m_rcvif_restore(m) == NULL)) { 219 m_freem(m); 220 goto next; 221 } 222 223 return m; 224 } 225 226 /* 227 * Enqueue a packet 'm' in queue 'q' 228 */ 229 static int 230 aqm_codel_enqueue(struct dn_queue *q, struct mbuf *m) 231 { 232 struct dn_fs *f; 233 uint64_t len; 234 struct codel_status *cst; /*codel status variables */ 235 struct m_tag *mtag; 236 237 f = &(q->fs->fs); 238 len = m->m_pkthdr.len; 239 cst = q->aqm_status; 240 if(!cst) { 241 D("Codel queue is not initialized\n"); 242 goto drop; 243 } 244 245 /* Finding maximum packet size */ 246 // XXX we can get MTU from driver instead 247 if (len > cst->maxpkt_size) 248 cst->maxpkt_size = len; 249 250 /* check for queue size and drop the tail if exceed queue limit*/ 251 if (f->flags & DN_QSIZE_BYTES) { 252 if ( q->ni.len_bytes > f->qsize) 253 goto drop; 254 } 255 else { 256 if ( q->ni.length >= f->qsize) 257 goto drop; 258 } 259 260 /* Add timestamp as mtag */ 261 mtag = m_tag_locate(m, MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, NULL); 262 if (mtag == NULL) 263 mtag = m_tag_alloc(MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, 264 sizeof(aqm_time_t), M_NOWAIT); 265 if (mtag == NULL) 266 goto drop; 267 268 *(aqm_time_t *)(mtag + 1) = AQM_UNOW; 269 m_tag_prepend(m, mtag); 270 271 mq_append(&q->mq, m); 272 update_stats(q, len, 0); 273 return (0); 274 275 drop: 276 update_stats(q, 0, 1); 277 FREE_PKT(m); 278 return (1); 279 } 280 281 /* Dequeue a pcaket from queue q */ 282 static struct mbuf * 283 aqm_codel_dequeue(struct dn_queue *q) 284 { 285 return codel_dequeue(q); 286 } 287 288 /* 289 * initialize Codel for queue 'q' 290 * First allocate memory for codel status. 291 */ 292 static int 293 aqm_codel_init(struct dn_queue *q) 294 { 295 struct codel_status *cst; 296 297 if (!q->fs->aqmcfg) { 298 D("Codel is not configure!d"); 299 return EINVAL; 300 } 301 302 q->aqm_status = malloc(sizeof(struct codel_status), 303 M_DUMMYNET, M_NOWAIT | M_ZERO); 304 if (q->aqm_status == NULL) { 305 D("Cannot allocate AQM_codel private data"); 306 return ENOMEM ; 307 } 308 309 /* init codel status variables */ 310 cst = q->aqm_status; 311 cst->dropping=0; 312 cst->first_above_time=0; 313 cst->drop_next_time=0; 314 cst->count=0; 315 cst->maxpkt_size = 500; 316 317 /* increase reference counters */ 318 codel_desc.ref_count++; 319 320 return 0; 321 } 322 323 /* 324 * Clean up Codel status for queue 'q' 325 * Destroy memory allocated for codel status. 326 */ 327 static int 328 aqm_codel_cleanup(struct dn_queue *q) 329 { 330 331 if (q && q->aqm_status) { 332 free(q->aqm_status, M_DUMMYNET); 333 q->aqm_status = NULL; 334 /* decrease reference counters */ 335 codel_desc.ref_count--; 336 } 337 else 338 D("Codel already cleaned up"); 339 return 0; 340 } 341 342 /* 343 * Config codel parameters 344 * also allocate memory for codel configurations 345 */ 346 static int 347 aqm_codel_config(struct dn_fsk* fs, struct dn_extra_parms *ep, int len) 348 { 349 struct dn_aqm_codel_parms *ccfg; 350 351 int l = sizeof(struct dn_extra_parms); 352 if (len < l) { 353 D("invalid sched parms length got %d need %d", len, l); 354 return EINVAL; 355 } 356 /* we free the old cfg because maybe the original allocation 357 * not the same size as the new one (different AQM type). 358 */ 359 if (fs->aqmcfg) { 360 free(fs->aqmcfg, M_DUMMYNET); 361 fs->aqmcfg = NULL; 362 } 363 364 fs->aqmcfg = malloc(sizeof(struct dn_aqm_codel_parms), 365 M_DUMMYNET, M_NOWAIT | M_ZERO); 366 if (fs->aqmcfg== NULL) { 367 D("cannot allocate AQM_codel configuration parameters"); 368 return ENOMEM; 369 } 370 371 /* configure codel parameters */ 372 ccfg = fs->aqmcfg; 373 374 if (ep->par[0] < 0) 375 ccfg->target = codel_sysctl.target; 376 else 377 ccfg->target = ep->par[0] * AQM_TIME_1US; 378 379 if (ep->par[1] < 0) 380 ccfg->interval = codel_sysctl.interval; 381 else 382 ccfg->interval = ep->par[1] * AQM_TIME_1US; 383 384 if (ep->par[2] < 0) 385 ccfg->flags = 0; 386 else 387 ccfg->flags = ep->par[2]; 388 389 /* bound codel configurations */ 390 ccfg->target = BOUND_VAR(ccfg->target,1, 5 * AQM_TIME_1S); 391 ccfg->interval = BOUND_VAR(ccfg->interval,1, 5 * AQM_TIME_1S); 392 /* increase config reference counter */ 393 codel_desc.cfg_ref_count++; 394 395 return 0; 396 } 397 398 /* 399 * Deconfigure Codel and free memory allocation 400 */ 401 static int 402 aqm_codel_deconfig(struct dn_fsk* fs) 403 { 404 405 if (fs && fs->aqmcfg) { 406 free(fs->aqmcfg, M_DUMMYNET); 407 fs->aqmcfg = NULL; 408 fs->aqmfp = NULL; 409 /* decrease config reference counter */ 410 codel_desc.cfg_ref_count--; 411 } 412 413 return 0; 414 } 415 416 /* 417 * Retrieve Codel configuration parameters. 418 */ 419 static int 420 aqm_codel_getconfig(struct dn_fsk *fs, struct dn_extra_parms * ep) 421 { 422 struct dn_aqm_codel_parms *ccfg; 423 424 if (fs->aqmcfg) { 425 strlcpy(ep->name, codel_desc.name, sizeof(ep->name)); 426 ccfg = fs->aqmcfg; 427 ep->par[0] = ccfg->target / AQM_TIME_1US; 428 ep->par[1] = ccfg->interval / AQM_TIME_1US; 429 ep->par[2] = ccfg->flags; 430 return 0; 431 } 432 return 1; 433 } 434 435 static struct dn_aqm codel_desc = { 436 _SI( .type = ) DN_AQM_CODEL, 437 _SI( .name = ) "CODEL", 438 _SI( .enqueue = ) aqm_codel_enqueue, 439 _SI( .dequeue = ) aqm_codel_dequeue, 440 _SI( .config = ) aqm_codel_config, 441 _SI( .getconfig = ) aqm_codel_getconfig, 442 _SI( .deconfig = ) aqm_codel_deconfig, 443 _SI( .init = ) aqm_codel_init, 444 _SI( .cleanup = ) aqm_codel_cleanup, 445 }; 446 447 DECLARE_DNAQM_MODULE(dn_aqm_codel, &codel_desc); 448 449 #endif 450