2 * Codel - The Controlled-Delay Active Queue Management algorithm.
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>
12 * Redistribution and use in source and binary forms, with or without
13 * modification, are permitted provided that the following conditions
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.
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
34 #include <sys/cdefs.h>
35 #include "opt_inet6.h"
37 #include <sys/param.h>
38 #include <sys/systm.h>
39 #include <sys/malloc.h>
41 #include <sys/kernel.h>
43 #include <sys/module.h>
46 #include <sys/rwlock.h>
47 #include <sys/socket.h>
49 #include <sys/sysctl.h>
51 #include <net/if.h> /* IFNAMSIZ, struct ifaddr, ifq head, lock.h mutex.h */
52 #include <net/netisr.h>
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>
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>
72 #define DN_AQM_CODEL 1
74 static struct dn_aqm codel_desc;
76 /* default codel parameters */
77 struct dn_aqm_codel_parms codel_sysctl = {5000 * AQM_TIME_1US,
78 100000 * AQM_TIME_1US, 0};
81 codel_sysctl_interval_handler(SYSCTL_HANDLER_ARGS)
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)
91 if (value < 1 || value > 100 * AQM_TIME_1S)
93 codel_sysctl.interval = value * AQM_TIME_1US ;
98 codel_sysctl_target_handler(SYSCTL_HANDLER_ARGS)
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)
109 if (value < 1 || value > 5 * AQM_TIME_1S)
111 codel_sysctl.target = value * AQM_TIME_1US ;
115 /* defining Codel sysctl variables */
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,
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");
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");
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/
143 control_law(struct codel_status *cst, struct dn_aqm_codel_parms *cprms,
150 /* we don't calculate isqrt(1) to get more accurate result*/
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;
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.
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);
171 * Divide by 2 because we multiplied the original equation by two
172 * Also, we shift the result by 8 bits to prevent overflow.
176 /* Now, temp = (1.5 - 0.5*c*g^2)
177 * Calculate g (1.5 - 0.5*c*g^2) i.e. g * temp
179 temp = (cst->isqrt * temp) >> (FIX_POINT_BITS + FIX_POINT_BITS - 8);
182 /* calculate codel_interval/sqrt(count) */
183 return t + ((cprms->interval * temp) >> FIX_POINT_BITS);
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.
192 codel_extract_head(struct dn_queue *q, aqm_time_t *pkt_ts)
195 struct mbuf *m = q->mq.head;
199 q->mq.head = m->m_nextpkt;
202 update_stats(q, -m->m_pkthdr.len, 0);
204 if (q->ni.length == 0) /* queue is now idle */
205 q->q_time = dn_cfg.curr_time;
207 /* extract packet TS*/
208 mtag = m_tag_locate(m, MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, NULL);
210 D("Codel timestamp mtag not found!");
213 *pkt_ts = *(aqm_time_t *)(mtag + 1);
214 m_tag_delete(m,mtag);
221 * Enqueue a packet 'm' in queue 'q'
224 aqm_codel_enqueue(struct dn_queue *q, struct mbuf *m)
228 struct codel_status *cst; /*codel status variables */
232 len = m->m_pkthdr.len;
235 D("Codel queue is not initialized\n");
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;
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)
250 if ( q->ni.length >= f->qsize)
254 /* Add timestamp as mtag */
255 mtag = m_tag_locate(m, MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, NULL);
257 mtag = m_tag_alloc(MTAG_ABI_COMPAT, DN_AQM_MTAG_TS,
258 sizeof(aqm_time_t), M_NOWAIT);
264 *(aqm_time_t *)(mtag + 1) = AQM_UNOW;
265 m_tag_prepend(m, mtag);
267 mq_append(&q->mq, m);
268 update_stats(q, len, 0);
272 update_stats(q, 0, 1);
278 /* Dequeue a pcaket from queue q */
280 aqm_codel_dequeue(struct dn_queue *q)
282 return codel_dequeue(q);
286 * initialize Codel for queue 'q'
287 * First allocate memory for codel status.
290 aqm_codel_init(struct dn_queue *q)
292 struct codel_status *cst;
294 if (!q->fs->aqmcfg) {
295 D("Codel is not configure!d");
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");
306 /* init codel status variables */
309 cst->first_above_time=0;
310 cst->drop_next_time=0;
312 cst->maxpkt_size = 500;
314 /* increase reference counters */
315 codel_desc.ref_count++;
321 * Clean up Codel status for queue 'q'
322 * Destroy memory allocated for codel status.
325 aqm_codel_cleanup(struct dn_queue *q)
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--;
335 D("Codel already cleaned up");
340 * Config codel parameters
341 * also allocate memory for codel configurations
344 aqm_codel_config(struct dn_fsk* fs, struct dn_extra_parms *ep, int len)
346 struct dn_aqm_codel_parms *ccfg;
348 int l = sizeof(struct dn_extra_parms);
350 D("invalid sched parms length got %d need %d", len, l);
353 /* we free the old cfg because maybe the original allocation
354 * not the same size as the new one (different AQM type).
357 free(fs->aqmcfg, M_DUMMYNET);
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");
368 /* configure codel parameters */
372 ccfg->target = codel_sysctl.target;
374 ccfg->target = ep->par[0] * AQM_TIME_1US;
377 ccfg->interval = codel_sysctl.interval;
379 ccfg->interval = ep->par[1] * AQM_TIME_1US;
384 ccfg->flags = ep->par[2];
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++;
396 * Deconfigure Codel and free memory allocation
399 aqm_codel_deconfig(struct dn_fsk* fs)
402 if (fs && fs->aqmcfg) {
403 free(fs->aqmcfg, M_DUMMYNET);
406 /* decrease config reference counter */
407 codel_desc.cfg_ref_count--;
414 * Retrieve Codel configuration parameters.
417 aqm_codel_getconfig(struct dn_fsk *fs, struct dn_extra_parms * ep)
419 struct dn_aqm_codel_parms *ccfg;
422 strlcpy(ep->name, codel_desc.name, sizeof(ep->name));
424 ep->par[0] = ccfg->target / AQM_TIME_1US;
425 ep->par[1] = ccfg->interval / AQM_TIME_1US;
426 ep->par[2] = ccfg->flags;
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,
444 DECLARE_DNAQM_MODULE(dn_aqm_codel, &codel_desc);