sys/netpfil/ipfw/dn_aqm_codel.c

   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