1300779Struckman/* 2300779Struckman * Codel - The Controlled-Delay Active Queue Management algorithm. 3300779Struckman * 4300779Struckman * $FreeBSD: stable/11/sys/netpfil/ipfw/dn_aqm_codel.c 317488 2017-04-27 07:30:48Z truckman $ 5300779Struckman * 6300779Struckman * Copyright (C) 2016 Centre for Advanced Internet Architectures, 7300779Struckman * Swinburne University of Technology, Melbourne, Australia. 8300779Struckman * Portions of this code were made possible in part by a gift from 9300779Struckman * The Comcast Innovation Fund. 10300779Struckman * Implemented by Rasool Al-Saadi <ralsaadi@swin.edu.au> 11300779Struckman * 12300779Struckman * Redistribution and use in source and binary forms, with or without 13300779Struckman * modification, are permitted provided that the following conditions 14300779Struckman * are met: 15300779Struckman * 1. Redistributions of source code must retain the above copyright 16300779Struckman * notice, this list of conditions and the following disclaimer. 17300779Struckman * 2. Redistributions in binary form must reproduce the above copyright 18300779Struckman * notice, this list of conditions and the following disclaimer in the 19300779Struckman * documentation and/or other materials provided with the distribution. 20300779Struckman * 21300779Struckman * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 22300779Struckman * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23300779Struckman * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24300779Struckman * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 25300779Struckman * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26300779Struckman * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27300779Struckman * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28300779Struckman * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29300779Struckman * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30300779Struckman * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31300779Struckman * SUCH DAMAGE. 32300779Struckman */ 33300779Struckman 34300779Struckman#include <sys/cdefs.h> 35300779Struckman#include "opt_inet6.h" 36300779Struckman 37300779Struckman#include <sys/param.h> 38300779Struckman#include <sys/systm.h> 39300779Struckman#include <sys/malloc.h> 40300779Struckman#include <sys/mbuf.h> 41300779Struckman#include <sys/kernel.h> 42300779Struckman#include <sys/lock.h> 43300779Struckman#include <sys/module.h> 44300779Struckman#include <sys/priv.h> 45300779Struckman#include <sys/proc.h> 46300779Struckman#include <sys/rwlock.h> 47300779Struckman#include <sys/socket.h> 48300779Struckman#include <sys/time.h> 49300779Struckman#include <sys/sysctl.h> 50300779Struckman 51300779Struckman#include <net/if.h> /* IFNAMSIZ, struct ifaddr, ifq head, lock.h mutex.h */ 52300779Struckman#include <net/netisr.h> 53300779Struckman#include <net/vnet.h> 54300779Struckman 55300779Struckman#include <netinet/in.h> 56300779Struckman#include <netinet/ip.h> /* ip_len, ip_off */ 57300779Struckman#include <netinet/ip_var.h> /* ip_output(), IP_FORWARDING */ 58300779Struckman#include <netinet/ip_fw.h> 59300779Struckman#include <netinet/ip_dummynet.h> 60300779Struckman#include <netinet/if_ether.h> /* various ether_* routines */ 61300779Struckman#include <netinet/ip6.h> /* for ip6_input, ip6_output prototypes */ 62300779Struckman#include <netinet6/ip6_var.h> 63300779Struckman#include <netpfil/ipfw/dn_heap.h> 64300779Struckman 65300779Struckman#ifdef NEW_AQM 66300779Struckman#include <netpfil/ipfw/ip_fw_private.h> 67300779Struckman#include <netpfil/ipfw/ip_dn_private.h> 68300779Struckman#include <netpfil/ipfw/dn_aqm.h> 69300779Struckman#include <netpfil/ipfw/dn_aqm_codel.h> 70300779Struckman#include <netpfil/ipfw/dn_sched.h> 71300779Struckman 72300779Struckman#define DN_AQM_CODEL 1 73300779Struckman 74300779Struckmanstatic struct dn_aqm codel_desc; 75300779Struckman 76300779Struckman/* default codel parameters */ 77300779Struckmanstruct dn_aqm_codel_parms codel_sysctl = {5000 * AQM_TIME_1US, 78300779Struckman 100000 * AQM_TIME_1US, 0}; 79300779Struckman 80300779Struckmanstatic int 81300779Struckmancodel_sysctl_interval_handler(SYSCTL_HANDLER_ARGS) 82300779Struckman{ 83300779Struckman int error; 84300779Struckman long value; 85300779Struckman 86300779Struckman value = codel_sysctl.interval; 87300779Struckman value /= AQM_TIME_1US; 88300779Struckman error = sysctl_handle_long(oidp, &value, 0, req); 89300779Struckman if (error != 0 || req->newptr == NULL) 90300779Struckman return (error); 91300779Struckman if (value < 1 || value > 100 * AQM_TIME_1S) 92300779Struckman return (EINVAL); 93300779Struckman codel_sysctl.interval = value * AQM_TIME_1US ; 94300779Struckman return (0); 95300779Struckman} 96300779Struckman 97300779Struckmanstatic int 98300779Struckmancodel_sysctl_target_handler(SYSCTL_HANDLER_ARGS) 99300779Struckman{ 100300779Struckman int error; 101300779Struckman long value; 102300779Struckman 103300779Struckman value = codel_sysctl.target; 104300779Struckman value /= AQM_TIME_1US; 105300779Struckman error = sysctl_handle_long(oidp, &value, 0, req); 106300779Struckman if (error != 0 || req->newptr == NULL) 107300779Struckman return (error); 108300779Struckman D("%ld", value); 109300779Struckman if (value < 1 || value > 5 * AQM_TIME_1S) 110300779Struckman return (EINVAL); 111300779Struckman codel_sysctl.target = value * AQM_TIME_1US ; 112300779Struckman return (0); 113300779Struckman} 114300779Struckman 115300779Struckman/* defining Codel sysctl variables */ 116300779StruckmanSYSBEGIN(f4) 117300779Struckman 118300779StruckmanSYSCTL_DECL(_net_inet); 119300779StruckmanSYSCTL_DECL(_net_inet_ip); 120300779StruckmanSYSCTL_DECL(_net_inet_ip_dummynet); 121300779Struckmanstatic SYSCTL_NODE(_net_inet_ip_dummynet, OID_AUTO, 122300779Struckman codel, CTLFLAG_RW, 0, "CODEL"); 123300779Struckman 124300779Struckman#ifdef SYSCTL_NODE 125300779StruckmanSYSCTL_PROC(_net_inet_ip_dummynet_codel, OID_AUTO, target, 126300779Struckman CTLTYPE_LONG | CTLFLAG_RW, NULL, 0,codel_sysctl_target_handler, "L", 127300779Struckman "CoDel target in microsecond"); 128300779Struckman 129300779StruckmanSYSCTL_PROC(_net_inet_ip_dummynet_codel, OID_AUTO, interval, 130300779Struckman CTLTYPE_LONG | CTLFLAG_RW, NULL, 0, codel_sysctl_interval_handler, "L", 131300779Struckman "CoDel interval in microsecond"); 132300779Struckman#endif 133300779Struckman 134300779Struckman/* This function computes codel_interval/sqrt(count) 135300779Struckman * Newton's method of approximation is used to compute 1/sqrt(count). 136300779Struckman * http://betterexplained.com/articles/ 137300779Struckman * understanding-quakes-fast-inverse-square-root/ 138300779Struckman */ 139300779Struckmanaqm_time_t 140300779Struckmancontrol_law(struct codel_status *cst, struct dn_aqm_codel_parms *cprms, 141300779Struckman aqm_time_t t) 142300779Struckman{ 143300779Struckman uint32_t count; 144300779Struckman uint64_t temp; 145300779Struckman count = cst->count; 146300779Struckman 147300779Struckman /* we don't calculate isqrt(1) to get more accurate result*/ 148300779Struckman if (count == 1) { 149300779Struckman /* prepare isqrt (old guess) for the next iteration i.e. 1/sqrt(2)*/ 150300779Struckman cst->isqrt = (1UL<< FIX_POINT_BITS) * 7/10; 151300779Struckman /* return time + isqrt(1)*interval */ 152300779Struckman return t + cprms->interval; 153300779Struckman } 154300779Struckman 155300779Struckman /* newguess = g(1.5 - 0.5*c*g^2) 156300779Struckman * Multiplying both sides by 2 to make all the constants intergers 157300779Struckman * newguess * 2 = g(3 - c*g^2) g=old guess, c=count 158300779Struckman * So, newguess = newguess /2 159300779Struckman * Fixed point operations are used here. 160300779Struckman */ 161300779Struckman 162300779Struckman /* Calculate g^2 */ 163300779Struckman temp = (uint32_t) cst->isqrt * cst->isqrt; 164300779Struckman /* Calculate (3 - c*g^2) i.e. (3 - c * temp) */ 165300779Struckman temp = (3ULL<< (FIX_POINT_BITS*2)) - (count * temp); 166300779Struckman 167300779Struckman /* 168300779Struckman * Divide by 2 because we multiplied the original equation by two 169300779Struckman * Also, we shift the result by 8 bits to prevent overflow. 170300779Struckman * */ 171300779Struckman temp >>= (1 + 8); 172300779Struckman 173300779Struckman /* Now, temp = (1.5 - 0.5*c*g^2) 174300779Struckman * Calculate g (1.5 - 0.5*c*g^2) i.e. g * temp 175300779Struckman */ 176300779Struckman temp = (cst->isqrt * temp) >> (FIX_POINT_BITS + FIX_POINT_BITS - 8); 177300779Struckman cst->isqrt = temp; 178300779Struckman 179300779Struckman /* calculate codel_interval/sqrt(count) */ 180300779Struckman return t + ((cprms->interval * temp) >> FIX_POINT_BITS); 181300779Struckman} 182300779Struckman 183300779Struckman/* 184300779Struckman * Extract a packet from the head of queue 'q' 185300779Struckman * Return a packet or NULL if the queue is empty. 186300779Struckman * Also extract packet's timestamp from mtag. 187300779Struckman */ 188300779Struckmanstruct mbuf * 189300779Struckmancodel_extract_head(struct dn_queue *q, aqm_time_t *pkt_ts) 190300779Struckman{ 191300779Struckman struct m_tag *mtag; 192300779Struckman struct mbuf *m = q->mq.head; 193300779Struckman 194300779Struckman if (m == NULL) 195300779Struckman return m; 196300779Struckman q->mq.head = m->m_nextpkt; 197300779Struckman 198300779Struckman /* Update stats */ 199300779Struckman update_stats(q, -m->m_pkthdr.len, 0); 200300779Struckman 201300779Struckman if (q->ni.length == 0) /* queue is now idle */ 202300779Struckman q->q_time = dn_cfg.curr_time; 203300779Struckman 204300779Struckman /* extract packet TS*/ 205300779Struckman mtag = m_tag_locate(m, MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, NULL); 206300779Struckman if (mtag == NULL) { 207300779Struckman D("Codel timestamp mtag not found!"); 208300779Struckman *pkt_ts = 0; 209300779Struckman } else { 210300779Struckman *pkt_ts = *(aqm_time_t *)(mtag + 1); 211300779Struckman m_tag_delete(m,mtag); 212300779Struckman } 213300779Struckman 214300779Struckman return m; 215300779Struckman} 216300779Struckman 217300779Struckman/* 218300779Struckman * Enqueue a packet 'm' in queue 'q' 219300779Struckman */ 220300779Struckmanstatic int 221300779Struckmanaqm_codel_enqueue(struct dn_queue *q, struct mbuf *m) 222300779Struckman{ 223300779Struckman struct dn_fs *f; 224300779Struckman uint64_t len; 225300779Struckman struct codel_status *cst; /*codel status variables */ 226300779Struckman struct m_tag *mtag; 227300779Struckman 228300779Struckman f = &(q->fs->fs); 229300779Struckman len = m->m_pkthdr.len; 230300779Struckman cst = q->aqm_status; 231300779Struckman if(!cst) { 232300779Struckman D("Codel queue is not initialized\n"); 233300779Struckman goto drop; 234300779Struckman } 235300779Struckman 236300779Struckman /* Finding maximum packet size */ 237300779Struckman // XXX we can get MTU from driver instead 238300779Struckman if (len > cst->maxpkt_size) 239300779Struckman cst->maxpkt_size = len; 240300779Struckman 241300779Struckman /* check for queue size and drop the tail if exceed queue limit*/ 242300779Struckman if (f->flags & DN_QSIZE_BYTES) { 243300779Struckman if ( q->ni.len_bytes > f->qsize) 244300779Struckman goto drop; 245300779Struckman } 246300779Struckman else { 247300779Struckman if ( q->ni.length >= f->qsize) 248300779Struckman goto drop; 249300779Struckman } 250300779Struckman 251300779Struckman /* Add timestamp as mtag */ 252300779Struckman mtag = m_tag_locate(m, MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, NULL); 253300779Struckman if (mtag == NULL) 254300779Struckman mtag = m_tag_alloc(MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, 255300779Struckman sizeof(aqm_time_t), M_NOWAIT); 256300779Struckman if (mtag == NULL) { 257300779Struckman m_freem(m); 258300779Struckman goto drop; 259300779Struckman } 260300779Struckman 261300779Struckman *(aqm_time_t *)(mtag + 1) = AQM_UNOW; 262300779Struckman m_tag_prepend(m, mtag); 263300779Struckman 264300779Struckman mq_append(&q->mq, m); 265300779Struckman update_stats(q, len, 0); 266300779Struckman return (0); 267300779Struckman 268300779Struckmandrop: 269300779Struckman update_stats(q, 0, 1); 270300779Struckman FREE_PKT(m); 271300779Struckman return (1); 272300779Struckman} 273300779Struckman 274300779Struckman 275300779Struckman/* Dequeue a pcaket from queue q */ 276300779Struckmanstatic struct mbuf * 277300779Struckmanaqm_codel_dequeue(struct dn_queue *q) 278300779Struckman{ 279300779Struckman return codel_dequeue(q); 280300779Struckman} 281300779Struckman 282300779Struckman/* 283300779Struckman * initialize Codel for queue 'q' 284300779Struckman * First allocate memory for codel status. 285300779Struckman */ 286300779Struckmanstatic int 287300779Struckmanaqm_codel_init(struct dn_queue *q) 288300779Struckman{ 289300779Struckman struct codel_status *cst; 290300779Struckman 291300779Struckman if (!q->fs->aqmcfg) { 292300779Struckman D("Codel is not configure!d"); 293300779Struckman return EINVAL; 294300779Struckman } 295300779Struckman 296300779Struckman q->aqm_status = malloc(sizeof(struct codel_status), 297300779Struckman M_DUMMYNET, M_NOWAIT | M_ZERO); 298300779Struckman if (q->aqm_status == NULL) { 299300779Struckman D("Cannot allocate AQM_codel private data"); 300300779Struckman return ENOMEM ; 301300779Struckman } 302300779Struckman 303300779Struckman /* init codel status variables */ 304300779Struckman cst = q->aqm_status; 305300779Struckman cst->dropping=0; 306300779Struckman cst->first_above_time=0; 307300779Struckman cst->drop_next_time=0; 308300779Struckman cst->count=0; 309300779Struckman cst->maxpkt_size = 500; 310300779Struckman 311300779Struckman /* increase reference counters */ 312300779Struckman codel_desc.ref_count++; 313300779Struckman 314300779Struckman return 0; 315300779Struckman} 316300779Struckman 317300779Struckman/* 318300779Struckman * Clean up Codel status for queue 'q' 319300779Struckman * Destroy memory allocated for codel status. 320300779Struckman */ 321300779Struckmanstatic int 322300779Struckmanaqm_codel_cleanup(struct dn_queue *q) 323300779Struckman{ 324300779Struckman 325300779Struckman if (q && q->aqm_status) { 326300779Struckman free(q->aqm_status, M_DUMMYNET); 327300779Struckman q->aqm_status = NULL; 328300779Struckman /* decrease reference counters */ 329300779Struckman codel_desc.ref_count--; 330300779Struckman } 331300779Struckman else 332300779Struckman D("Codel already cleaned up"); 333300779Struckman return 0; 334300779Struckman} 335300779Struckman 336300779Struckman/* 337300779Struckman * Config codel parameters 338300779Struckman * also allocate memory for codel configurations 339300779Struckman */ 340300779Struckmanstatic int 341300779Struckmanaqm_codel_config(struct dn_fsk* fs, struct dn_extra_parms *ep, int len) 342300779Struckman{ 343300779Struckman struct dn_aqm_codel_parms *ccfg; 344300779Struckman 345300779Struckman int l = sizeof(struct dn_extra_parms); 346300779Struckman if (len < l) { 347300779Struckman D("invalid sched parms length got %d need %d", len, l); 348300779Struckman return EINVAL; 349300779Struckman } 350300779Struckman /* we free the old cfg because maybe the original allocation 351300779Struckman * not the same size as the new one (different AQM type). 352300779Struckman */ 353300779Struckman if (fs->aqmcfg) { 354300779Struckman free(fs->aqmcfg, M_DUMMYNET); 355300779Struckman fs->aqmcfg = NULL; 356300779Struckman } 357300779Struckman 358300779Struckman fs->aqmcfg = malloc(sizeof(struct dn_aqm_codel_parms), 359300779Struckman M_DUMMYNET, M_NOWAIT | M_ZERO); 360300779Struckman if (fs->aqmcfg== NULL) { 361300779Struckman D("cannot allocate AQM_codel configuration parameters"); 362300779Struckman return ENOMEM; 363300779Struckman } 364300779Struckman 365300779Struckman /* configure codel parameters */ 366300779Struckman ccfg = fs->aqmcfg; 367300779Struckman 368300779Struckman if (ep->par[0] < 0) 369300779Struckman ccfg->target = codel_sysctl.target; 370300779Struckman else 371300779Struckman ccfg->target = ep->par[0] * AQM_TIME_1US; 372300779Struckman 373300779Struckman if (ep->par[1] < 0) 374300779Struckman ccfg->interval = codel_sysctl.interval; 375300779Struckman else 376300779Struckman ccfg->interval = ep->par[1] * AQM_TIME_1US; 377300779Struckman 378300779Struckman if (ep->par[2] < 0) 379300779Struckman ccfg->flags = 0; 380300779Struckman else 381300779Struckman ccfg->flags = ep->par[2]; 382300779Struckman 383300779Struckman /* bound codel configurations */ 384300779Struckman ccfg->target = BOUND_VAR(ccfg->target,1, 5 * AQM_TIME_1S); 385300779Struckman ccfg->interval = BOUND_VAR(ccfg->interval,1, 5 * AQM_TIME_1S); 386300779Struckman /* increase config reference counter */ 387300779Struckman codel_desc.cfg_ref_count++; 388300779Struckman 389300779Struckman return 0; 390300779Struckman} 391300779Struckman 392300779Struckman/* 393300779Struckman * Deconfigure Codel and free memory allocation 394300779Struckman */ 395300779Struckmanstatic int 396300779Struckmanaqm_codel_deconfig(struct dn_fsk* fs) 397300779Struckman{ 398300779Struckman 399300779Struckman if (fs && fs->aqmcfg) { 400300779Struckman free(fs->aqmcfg, M_DUMMYNET); 401300779Struckman fs->aqmcfg = NULL; 402300779Struckman fs->aqmfp = NULL; 403300779Struckman /* decrease config reference counter */ 404300779Struckman codel_desc.cfg_ref_count--; 405300779Struckman } 406300779Struckman 407300779Struckman return 0; 408300779Struckman} 409300779Struckman 410300779Struckman/* 411300779Struckman * Retrieve Codel configuration parameters. 412300779Struckman */ 413300779Struckmanstatic int 414300779Struckmanaqm_codel_getconfig(struct dn_fsk *fs, struct dn_extra_parms * ep) 415300779Struckman{ 416300779Struckman struct dn_aqm_codel_parms *ccfg; 417300779Struckman 418300779Struckman if (fs->aqmcfg) { 419317488Struckman strlcpy(ep->name, codel_desc.name, sizeof(ep->name)); 420300779Struckman ccfg = fs->aqmcfg; 421300779Struckman ep->par[0] = ccfg->target / AQM_TIME_1US; 422300779Struckman ep->par[1] = ccfg->interval / AQM_TIME_1US; 423300779Struckman ep->par[2] = ccfg->flags; 424300779Struckman return 0; 425300779Struckman } 426300779Struckman return 1; 427300779Struckman} 428300779Struckman 429300779Struckmanstatic struct dn_aqm codel_desc = { 430300779Struckman _SI( .type = ) DN_AQM_CODEL, 431300779Struckman _SI( .name = ) "CODEL", 432300779Struckman _SI( .enqueue = ) aqm_codel_enqueue, 433300779Struckman _SI( .dequeue = ) aqm_codel_dequeue, 434300779Struckman _SI( .config = ) aqm_codel_config, 435300779Struckman _SI( .getconfig = ) aqm_codel_getconfig, 436300779Struckman _SI( .deconfig = ) aqm_codel_deconfig, 437300779Struckman _SI( .init = ) aqm_codel_init, 438300779Struckman _SI( .cleanup = ) aqm_codel_cleanup, 439300779Struckman}; 440300779Struckman 441300779StruckmanDECLARE_DNAQM_MODULE(dn_aqm_codel, &codel_desc); 442300779Struckman 443300779Struckman 444300779Struckman#endif 445