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,
 122         codel, CTLFLAG_RW, 0, "CODEL");
 123
 124 #ifdef SYSCTL_NODE
 125 SYSCTL_PROC(_net_inet_ip_dummynet_codel, OID_AUTO, target,
 126         CTLTYPE_LONG | CTLFLAG_RW, 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, NULL, 0, codel_sysctl_interval_handler, "L",
 131         "CoDel interval in microsecond");
 132 #endif
 133
 134 /* This function computes codel_interval/sqrt(count)
 135  *  Newton's method of approximation is used to compute 1/sqrt(count).
 136  * http://betterexplained.com/articles/
 137  *      understanding-quakes-fast-inverse-square-root/
 138  */
 139 aqm_time_t
 140 control_law(struct codel_status *cst, struct dn_aqm_codel_parms *cprms,
 141         aqm_time_t t)
 142 {
 143         uint32_t count;
 144         uint64_t temp;
 145         count = cst->count;
 146
 147         /* we don't calculate isqrt(1) to get more accurate result*/
 148         if (count == 1) {
 149                 /* prepare isqrt (old guess) for the next iteration i.e. 1/sqrt(2)*/
 150                 cst->isqrt = (1UL<< FIX_POINT_BITS) * 7/10;
 151                 /* return time + isqrt(1)*interval */
 152                 return t + cprms->interval;
 153         }
 154
 155         /* newguess = g(1.5 - 0.5*c*g^2)
 156          * Multiplying both sides by 2 to make all the constants intergers
 157          * newguess * 2  = g(3 - c*g^2) g=old guess, c=count
 158          * So, newguess = newguess /2
 159          * Fixed point operations are used here.
 160          */
 161
 162         /* Calculate g^2 */
 163         temp = (uint32_t) cst->isqrt * cst->isqrt;
 164         /* Calculate (3 - c*g^2) i.e. (3 - c * temp) */
 165         temp = (3ULL<< (FIX_POINT_BITS*2)) - (count * temp);
 166
 167         /*
 168          * Divide by 2 because we multiplied the original equation by two
 169          * Also, we shift the result by 8 bits to prevent overflow.
 170          * */
 171         temp >>= (1 + 8);
 172
 173         /*  Now, temp = (1.5 - 0.5*c*g^2)
 174          * Calculate g (1.5 - 0.5*c*g^2) i.e. g * temp
 175          */
 176         temp = (cst->isqrt * temp) >> (FIX_POINT_BITS + FIX_POINT_BITS - 8);
 177         cst->isqrt = temp;
 178
 179          /* calculate codel_interval/sqrt(count) */
 180          return t + ((cprms->interval * temp) >> FIX_POINT_BITS);
 181 }
 182
 183 /*
 184  * Extract a packet from the head of queue 'q'
 185  * Return a packet or NULL if the queue is empty.
 186  * Also extract packet's timestamp from mtag.
 187  */
 188 struct mbuf *
 189 codel_extract_head(struct dn_queue *q, aqm_time_t *pkt_ts)
 190 {
 191         struct m_tag *mtag;
 192         struct mbuf *m = q->mq.head;
 193
 194         if (m == NULL)
 195                 return m;
 196         q->mq.head = m->m_nextpkt;
 197
 198         /* Update stats */
 199         update_stats(q, -m->m_pkthdr.len, 0);
 200
 201         if (q->ni.length == 0) /* queue is now idle */
 202                         q->q_time = dn_cfg.curr_time;
 203
 204         /* extract packet TS*/
 205         mtag = m_tag_locate(m, MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, NULL);
 206         if (mtag == NULL) {
 207                 D("Codel timestamp mtag not found!");
 208                 *pkt_ts = 0;
 209         } else {
 210                 *pkt_ts = *(aqm_time_t *)(mtag + 1);
 211                 m_tag_delete(m,mtag);
 212         }
 213
 214         return m;
 215 }
 216
 217 /*
 218  * Enqueue a packet 'm' in queue 'q'
 219  */
 220 static int
 221 aqm_codel_enqueue(struct dn_queue *q, struct mbuf *m)
 222 {
 223         struct dn_fs *f;
 224         uint64_t len;
 225         struct codel_status *cst;       /*codel status variables */
 226         struct m_tag *mtag;
 227
 228         f = &(q->fs->fs);
 229         len = m->m_pkthdr.len;
 230         cst = q->aqm_status;
 231         if(!cst) {
 232                 D("Codel queue is not initialized\n");
 233                 goto drop;
 234         }
 235
 236         /* Finding maximum packet size */
 237         // XXX we can get MTU from driver instead
 238         if (len > cst->maxpkt_size)
 239                 cst->maxpkt_size = len;
 240
 241         /* check for queue size and drop the tail if exceed queue limit*/
 242         if (f->flags & DN_QSIZE_BYTES) {
 243                 if ( q->ni.len_bytes > f->qsize)
 244                         goto drop;
 245         }
 246         else {
 247                 if ( q->ni.length >= f->qsize)
 248                         goto drop;
 249         }
 250
 251         /* Add timestamp as mtag */
 252         mtag = m_tag_locate(m, MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, NULL);
 253         if (mtag == NULL)
 254                 mtag = m_tag_alloc(MTAG_ABI_COMPAT, DN_AQM_MTAG_TS,
 255                         sizeof(aqm_time_t), M_NOWAIT);
 256         if (mtag == NULL) {
 257                 m_freem(m);
 258                 goto drop;
 259         }
 260
 261         *(aqm_time_t *)(mtag + 1) = AQM_UNOW;
 262         m_tag_prepend(m, mtag);
 263
 264         mq_append(&q->mq, m);
 265         update_stats(q, len, 0);
 266         return (0);
 267
 268 drop:
 269         update_stats(q, 0, 1);
 270         FREE_PKT(m);
 271         return (1);
 272 }
 273
 274
 275 /* Dequeue a pcaket from queue q */
 276 static struct mbuf *
 277 aqm_codel_dequeue(struct dn_queue *q)
 278 {
 279         return codel_dequeue(q);
 280 }
 281
 282 /*
 283  * initialize Codel for queue 'q'
 284  * First allocate memory for codel status.
 285  */
 286 static int
 287 aqm_codel_init(struct dn_queue *q)
 288 {
 289         struct codel_status *cst;
 290
 291         if (!q->fs->aqmcfg) {
 292                 D("Codel is not configure!d");
 293                 return EINVAL;
 294         }
 295
 296         q->aqm_status = malloc(sizeof(struct codel_status),
 297                          M_DUMMYNET, M_NOWAIT | M_ZERO);
 298         if (q->aqm_status == NULL) {
 299                 D("Cannot allocate AQM_codel private data");
 300                 return ENOMEM ;
 301         }
 302
 303         /* init codel status variables */
 304         cst = q->aqm_status;
 305         cst->dropping=0;
 306         cst->first_above_time=0;
 307         cst->drop_next_time=0;
 308         cst->count=0;
 309         cst->maxpkt_size = 500;
 310
 311         /* increase reference counters */
 312         codel_desc.ref_count++;
 313
 314         return 0;
 315 }
 316
 317 /*
 318  * Clean up Codel status for queue 'q'
 319  * Destroy memory allocated for codel status.
 320  */
 321 static int
 322 aqm_codel_cleanup(struct dn_queue *q)
 323 {
 324
 325         if (q && q->aqm_status) {
 326                 free(q->aqm_status, M_DUMMYNET);
 327                 q->aqm_status = NULL;
 328                 /* decrease reference counters */
 329                 codel_desc.ref_count--;
 330         }
 331         else
 332                 D("Codel already cleaned up");
 333         return 0;
 334 }
 335
 336 /*
 337  * Config codel parameters
 338  * also allocate memory for codel configurations
 339  */
 340 static int
 341 aqm_codel_config(struct dn_fsk* fs, struct dn_extra_parms *ep, int len)
 342 {
 343         struct dn_aqm_codel_parms *ccfg;
 344
 345         int l = sizeof(struct dn_extra_parms);
 346         if (len < l) {
 347                 D("invalid sched parms length got %d need %d", len, l);
 348                 return EINVAL;
 349         }
 350         /* we free the old cfg because maybe the original allocation
 351          * not the same size as the new one (different AQM type).
 352          */
 353         if (fs->aqmcfg) {
 354                 free(fs->aqmcfg, M_DUMMYNET);
 355                 fs->aqmcfg = NULL;
 356         }
 357
 358         fs->aqmcfg = malloc(sizeof(struct dn_aqm_codel_parms),
 359                          M_DUMMYNET, M_NOWAIT | M_ZERO);
 360         if (fs->aqmcfg== NULL) {
 361                 D("cannot allocate AQM_codel configuration parameters");
 362                 return ENOMEM;
 363         }
 364
 365         /* configure codel parameters */
 366         ccfg = fs->aqmcfg;
 367
 368         if (ep->par[0] < 0)
 369                 ccfg->target = codel_sysctl.target;
 370         else
 371                 ccfg->target = ep->par[0] * AQM_TIME_1US;
 372
 373         if (ep->par[1] < 0)
 374                 ccfg->interval = codel_sysctl.interval;
 375         else
 376                 ccfg->interval = ep->par[1] * AQM_TIME_1US;
 377
 378         if (ep->par[2] < 0)
 379                 ccfg->flags = 0;
 380         else
 381                 ccfg->flags = ep->par[2];
 382
 383         /* bound codel configurations */
 384         ccfg->target = BOUND_VAR(ccfg->target,1, 5 * AQM_TIME_1S);
 385         ccfg->interval = BOUND_VAR(ccfg->interval,1, 5 * AQM_TIME_1S);
 386         /* increase config reference counter */
 387         codel_desc.cfg_ref_count++;
 388
 389         return 0;
 390 }
 391
 392 /*
 393  * Deconfigure Codel and free memory allocation
 394  */
 395 static int
 396 aqm_codel_deconfig(struct dn_fsk* fs)
 397 {
 398
 399         if (fs && fs->aqmcfg) {
 400                 free(fs->aqmcfg, M_DUMMYNET);
 401                 fs->aqmcfg = NULL;
 402                 fs->aqmfp = NULL;
 403                 /* decrease config reference counter */
 404                 codel_desc.cfg_ref_count--;
 405         }
 406
 407         return 0;
 408 }
 409
 410 /*
 411  * Retrieve Codel configuration parameters.
 412  */
 413 static int
 414 aqm_codel_getconfig(struct dn_fsk *fs, struct dn_extra_parms * ep)
 415 {
 416         struct dn_aqm_codel_parms *ccfg;
 417
 418         if (fs->aqmcfg) {
 419                 strcpy(ep->name, codel_desc.name);
 420                 ccfg = fs->aqmcfg;
 421                 ep->par[0] = ccfg->target / AQM_TIME_1US;
 422                 ep->par[1] = ccfg->interval / AQM_TIME_1US;
 423                 ep->par[2] = ccfg->flags;
 424                 return 0;
 425         }
 426         return 1;
 427 }
 428
 429 static struct dn_aqm codel_desc = {
 430         _SI( .type = )  DN_AQM_CODEL,
 431         _SI( .name = )  "CODEL",
 432         _SI( .enqueue = )  aqm_codel_enqueue,
 433         _SI( .dequeue = )  aqm_codel_dequeue,
 434         _SI( .config = )  aqm_codel_config,
 435         _SI( .getconfig = )  aqm_codel_getconfig,
 436         _SI( .deconfig = )  aqm_codel_deconfig,
 437         _SI( .init = )  aqm_codel_init,
 438         _SI( .cleanup = )  aqm_codel_cleanup,
 439 };
 440
 441 DECLARE_DNAQM_MODULE(dn_aqm_codel, &codel_desc);
 442
 443
 444 #endif