1 /*
2 * Codel - The Controlled-Delay Active Queue Management algorithm.
3 *
4 * Copyright (C) 2016 Centre for Advanced Internet Architectures,
5 * Swinburne University of Technology, Melbourne, Australia.
6 * Portions of this code were made possible in part by a gift from
7 * The Comcast Innovation Fund.
8 * Implemented by Rasool Al-Saadi <ralsaadi@swin.edu.au>
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 * SUCH DAMAGE.
30 */
31
32 #include <sys/cdefs.h>
33 #include "opt_inet6.h"
34
35 #include <sys/param.h>
36 #include <sys/systm.h>
37 #include <sys/malloc.h>
38 #include <sys/mbuf.h>
39 #include <sys/kernel.h>
40 #include <sys/lock.h>
41 #include <sys/module.h>
42 #include <sys/priv.h>
43 #include <sys/proc.h>
44 #include <sys/rwlock.h>
45 #include <sys/socket.h>
46 #include <sys/time.h>
47 #include <sys/sysctl.h>
48
49 #include <net/if.h> /* IFNAMSIZ, struct ifaddr, ifq head, lock.h mutex.h */
50 #include <net/netisr.h>
51 #include <net/vnet.h>
52
53 #include <netinet/in.h>
54 #include <netinet/ip.h> /* ip_len, ip_off */
55 #include <netinet/ip_var.h> /* ip_output(), IP_FORWARDING */
56 #include <netinet/ip_fw.h>
57 #include <netinet/ip_dummynet.h>
58 #include <netinet/if_ether.h> /* various ether_* routines */
59 #include <netinet/ip6.h> /* for ip6_input, ip6_output prototypes */
60 #include <netinet6/ip6_var.h>
61 #include <netpfil/ipfw/dn_heap.h>
62
63 #ifdef NEW_AQM
64 #include <netpfil/ipfw/ip_fw_private.h>
65 #include <netpfil/ipfw/ip_dn_private.h>
66 #include <netpfil/ipfw/dn_aqm.h>
67 #include <netpfil/ipfw/dn_aqm_codel.h>
68 #include <netpfil/ipfw/dn_sched.h>
69
70 #define DN_AQM_CODEL 1
71
72 static struct dn_aqm codel_desc;
73
74 /* default codel parameters */
75 struct dn_aqm_codel_parms codel_sysctl = {5000 * AQM_TIME_1US,
76 100000 * AQM_TIME_1US, 0};
77
78 static int
codel_sysctl_interval_handler(SYSCTL_HANDLER_ARGS)79 codel_sysctl_interval_handler(SYSCTL_HANDLER_ARGS)
80 {
81 int error;
82 long value;
83
84 value = codel_sysctl.interval;
85 value /= AQM_TIME_1US;
86 error = sysctl_handle_long(oidp, &value, 0, req);
87 if (error != 0 || req->newptr == NULL)
88 return (error);
89 if (value < 1 || value > 100 * AQM_TIME_1S)
90 return (EINVAL);
91 codel_sysctl.interval = value * AQM_TIME_1US ;
92 return (0);
93 }
94
95 static int
codel_sysctl_target_handler(SYSCTL_HANDLER_ARGS)96 codel_sysctl_target_handler(SYSCTL_HANDLER_ARGS)
97 {
98 int error;
99 long value;
100
101 value = codel_sysctl.target;
102 value /= AQM_TIME_1US;
103 error = sysctl_handle_long(oidp, &value, 0, req);
104 if (error != 0 || req->newptr == NULL)
105 return (error);
106 D("%ld", value);
107 if (value < 1 || value > 5 * AQM_TIME_1S)
108 return (EINVAL);
109 codel_sysctl.target = value * AQM_TIME_1US ;
110 return (0);
111 }
112
113 /* defining Codel sysctl variables */
114 SYSBEGIN(f4)
115
116 SYSCTL_DECL(_net_inet);
117 SYSCTL_DECL(_net_inet_ip);
118 SYSCTL_DECL(_net_inet_ip_dummynet);
119 static SYSCTL_NODE(_net_inet_ip_dummynet, OID_AUTO, codel,
120 CTLFLAG_RW | CTLFLAG_MPSAFE, 0,
121 "CODEL");
122
123 #ifdef SYSCTL_NODE
124 SYSCTL_PROC(_net_inet_ip_dummynet_codel, OID_AUTO, target,
125 CTLTYPE_LONG | CTLFLAG_RW | CTLFLAG_NEEDGIANT,
126 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 | CTLFLAG_NEEDGIANT,
131 NULL, 0, codel_sysctl_interval_handler, "L",
132 "CoDel interval in microsecond");
133 #endif
134
135 /* This function computes codel_interval/sqrt(count)
136 * Newton's method of approximation is used to compute 1/sqrt(count).
137 * http://betterexplained.com/articles/
138 * understanding-quakes-fast-inverse-square-root/
139 */
140 aqm_time_t
control_law(struct codel_status * cst,struct dn_aqm_codel_parms * cprms,aqm_time_t t)141 control_law(struct codel_status *cst, struct dn_aqm_codel_parms *cprms,
142 aqm_time_t t)
143 {
144 uint32_t count;
145 uint64_t temp;
146 count = cst->count;
147
148 /* we don't calculate isqrt(1) to get more accurate result*/
149 if (count == 1) {
150 /* prepare isqrt (old guess) for the next iteration i.e. 1/sqrt(2)*/
151 cst->isqrt = (1UL<< FIX_POINT_BITS) * 7/10;
152 /* return time + isqrt(1)*interval */
153 return t + cprms->interval;
154 }
155
156 /* newguess = g(1.5 - 0.5*c*g^2)
157 * Multiplying both sides by 2 to make all the constants integers
158 * newguess * 2 = g(3 - c*g^2) g=old guess, c=count
159 * So, newguess = newguess /2
160 * Fixed point operations are used here.
161 */
162
163 /* Calculate g^2 */
164 temp = (uint32_t) cst->isqrt * cst->isqrt;
165 /* Calculate (3 - c*g^2) i.e. (3 - c * temp) */
166 temp = (3ULL<< (FIX_POINT_BITS*2)) - (count * temp);
167
168 /*
169 * Divide by 2 because we multiplied the original equation by two
170 * Also, we shift the result by 8 bits to prevent overflow.
171 * */
172 temp >>= (1 + 8);
173
174 /* Now, temp = (1.5 - 0.5*c*g^2)
175 * Calculate g (1.5 - 0.5*c*g^2) i.e. g * temp
176 */
177 temp = (cst->isqrt * temp) >> (FIX_POINT_BITS + FIX_POINT_BITS - 8);
178 cst->isqrt = temp;
179
180 /* calculate codel_interval/sqrt(count) */
181 return t + ((cprms->interval * temp) >> FIX_POINT_BITS);
182 }
183
184 /*
185 * Extract a packet from the head of queue 'q'
186 * Return a packet or NULL if the queue is empty.
187 * Also extract packet's timestamp from mtag.
188 */
189 struct mbuf *
codel_extract_head(struct dn_queue * q,aqm_time_t * pkt_ts)190 codel_extract_head(struct dn_queue *q, aqm_time_t *pkt_ts)
191 {
192 struct m_tag *mtag;
193 struct mbuf *m;
194
195 next: m = q->mq.head;
196 if (m == NULL)
197 return m;
198 q->mq.head = m->m_nextpkt;
199
200 /* Update stats */
201 update_stats(q, -m->m_pkthdr.len, 0);
202
203 if (q->ni.length == 0) /* queue is now idle */
204 q->q_time = V_dn_cfg.curr_time;
205
206 /* extract packet TS*/
207 mtag = m_tag_locate(m, MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, NULL);
208 if (mtag == NULL) {
209 D("Codel timestamp mtag not found!");
210 *pkt_ts = 0;
211 } else {
212 *pkt_ts = *(aqm_time_t *)(mtag + 1);
213 m_tag_delete(m,mtag);
214 }
215 if (m->m_pkthdr.rcvif != NULL &&
216 __predict_false(m_rcvif_restore(m) == NULL)) {
217 m_freem(m);
218 goto next;
219 }
220
221 return m;
222 }
223
224 /*
225 * Enqueue a packet 'm' in queue 'q'
226 */
227 static int
aqm_codel_enqueue(struct dn_queue * q,struct mbuf * m)228 aqm_codel_enqueue(struct dn_queue *q, struct mbuf *m)
229 {
230 struct dn_fs *f;
231 uint64_t len;
232 struct codel_status *cst; /*codel status variables */
233 struct m_tag *mtag;
234
235 f = &(q->fs->fs);
236 len = m->m_pkthdr.len;
237 cst = q->aqm_status;
238 if(!cst) {
239 D("Codel queue is not initialized\n");
240 goto drop;
241 }
242
243 /* Finding maximum packet size */
244 // XXX we can get MTU from driver instead
245 if (len > cst->maxpkt_size)
246 cst->maxpkt_size = len;
247
248 /* check for queue size and drop the tail if exceed queue limit*/
249 if (f->flags & DN_QSIZE_BYTES) {
250 if ( q->ni.len_bytes > f->qsize)
251 goto drop;
252 }
253 else {
254 if ( q->ni.length >= f->qsize)
255 goto drop;
256 }
257
258 /* Add timestamp as mtag */
259 mtag = m_tag_locate(m, MTAG_ABI_COMPAT, DN_AQM_MTAG_TS, NULL);
260 if (mtag == NULL)
261 mtag = m_tag_alloc(MTAG_ABI_COMPAT, DN_AQM_MTAG_TS,
262 sizeof(aqm_time_t), M_NOWAIT);
263 if (mtag == NULL)
264 goto drop;
265
266 *(aqm_time_t *)(mtag + 1) = AQM_UNOW;
267 m_tag_prepend(m, mtag);
268
269 mq_append(&q->mq, m);
270 update_stats(q, len, 0);
271 return (0);
272
273 drop:
274 update_stats(q, 0, 1);
275 FREE_PKT(m);
276 return (1);
277 }
278
279 /* Dequeue a pcaket from queue q */
280 static struct mbuf *
aqm_codel_dequeue(struct dn_queue * q)281 aqm_codel_dequeue(struct dn_queue *q)
282 {
283 return codel_dequeue(q);
284 }
285
286 /*
287 * initialize Codel for queue 'q'
288 * First allocate memory for codel status.
289 */
290 static int
aqm_codel_init(struct dn_queue * q)291 aqm_codel_init(struct dn_queue *q)
292 {
293 struct codel_status *cst;
294
295 if (!q->fs->aqmcfg) {
296 D("Codel is not configure!d");
297 return EINVAL;
298 }
299
300 q->aqm_status = malloc(sizeof(struct codel_status),
301 M_DUMMYNET, M_NOWAIT | M_ZERO);
302 if (q->aqm_status == NULL) {
303 D("Cannot allocate AQM_codel private data");
304 return ENOMEM ;
305 }
306
307 /* init codel status variables */
308 cst = q->aqm_status;
309 cst->dropping=0;
310 cst->first_above_time=0;
311 cst->drop_next_time=0;
312 cst->count=0;
313 cst->maxpkt_size = 500;
314
315 /* increase reference counters */
316 codel_desc.ref_count++;
317
318 return 0;
319 }
320
321 /*
322 * Clean up Codel status for queue 'q'
323 * Destroy memory allocated for codel status.
324 */
325 static int
aqm_codel_cleanup(struct dn_queue * q)326 aqm_codel_cleanup(struct dn_queue *q)
327 {
328
329 if (q && q->aqm_status) {
330 free(q->aqm_status, M_DUMMYNET);
331 q->aqm_status = NULL;
332 /* decrease reference counters */
333 codel_desc.ref_count--;
334 }
335 else
336 D("Codel already cleaned up");
337 return 0;
338 }
339
340 /*
341 * Config codel parameters
342 * also allocate memory for codel configurations
343 */
344 static int
aqm_codel_config(struct dn_fsk * fs,struct dn_extra_parms * ep,int len)345 aqm_codel_config(struct dn_fsk* fs, struct dn_extra_parms *ep, int len)
346 {
347 struct dn_aqm_codel_parms *ccfg;
348
349 int l = sizeof(struct dn_extra_parms);
350 if (len < l) {
351 D("invalid sched parms length got %d need %d", len, l);
352 return EINVAL;
353 }
354 /* we free the old cfg because maybe the original allocation
355 * not the same size as the new one (different AQM type).
356 */
357 if (fs->aqmcfg) {
358 free(fs->aqmcfg, M_DUMMYNET);
359 fs->aqmcfg = NULL;
360 }
361
362 fs->aqmcfg = malloc(sizeof(struct dn_aqm_codel_parms),
363 M_DUMMYNET, M_NOWAIT | M_ZERO);
364 if (fs->aqmcfg== NULL) {
365 D("cannot allocate AQM_codel configuration parameters");
366 return ENOMEM;
367 }
368
369 /* configure codel parameters */
370 ccfg = fs->aqmcfg;
371
372 if (ep->par[0] < 0)
373 ccfg->target = codel_sysctl.target;
374 else
375 ccfg->target = ep->par[0] * AQM_TIME_1US;
376
377 if (ep->par[1] < 0)
378 ccfg->interval = codel_sysctl.interval;
379 else
380 ccfg->interval = ep->par[1] * AQM_TIME_1US;
381
382 if (ep->par[2] < 0)
383 ccfg->flags = 0;
384 else
385 ccfg->flags = ep->par[2];
386
387 /* bound codel configurations */
388 ccfg->target = BOUND_VAR(ccfg->target,1, 5 * AQM_TIME_1S);
389 ccfg->interval = BOUND_VAR(ccfg->interval,1, 5 * AQM_TIME_1S);
390 /* increase config reference counter */
391 codel_desc.cfg_ref_count++;
392
393 return 0;
394 }
395
396 /*
397 * Deconfigure Codel and free memory allocation
398 */
399 static int
aqm_codel_deconfig(struct dn_fsk * fs)400 aqm_codel_deconfig(struct dn_fsk* fs)
401 {
402
403 if (fs && fs->aqmcfg) {
404 free(fs->aqmcfg, M_DUMMYNET);
405 fs->aqmcfg = NULL;
406 fs->aqmfp = NULL;
407 /* decrease config reference counter */
408 codel_desc.cfg_ref_count--;
409 }
410
411 return 0;
412 }
413
414 /*
415 * Retrieve Codel configuration parameters.
416 */
417 static int
aqm_codel_getconfig(struct dn_fsk * fs,struct dn_extra_parms * ep)418 aqm_codel_getconfig(struct dn_fsk *fs, struct dn_extra_parms * ep)
419 {
420 struct dn_aqm_codel_parms *ccfg;
421
422 if (fs->aqmcfg) {
423 strlcpy(ep->name, codel_desc.name, sizeof(ep->name));
424 ccfg = fs->aqmcfg;
425 ep->par[0] = ccfg->target / AQM_TIME_1US;
426 ep->par[1] = ccfg->interval / AQM_TIME_1US;
427 ep->par[2] = ccfg->flags;
428 return 0;
429 }
430 return 1;
431 }
432
433 static struct dn_aqm codel_desc = {
434 _SI( .type = ) DN_AQM_CODEL,
435 _SI( .name = ) "CODEL",
436 _SI( .enqueue = ) aqm_codel_enqueue,
437 _SI( .dequeue = ) aqm_codel_dequeue,
438 _SI( .config = ) aqm_codel_config,
439 _SI( .getconfig = ) aqm_codel_getconfig,
440 _SI( .deconfig = ) aqm_codel_deconfig,
441 _SI( .init = ) aqm_codel_init,
442 _SI( .cleanup = ) aqm_codel_cleanup,
443 };
444
445 DECLARE_DNAQM_MODULE(dn_aqm_codel, &codel_desc);
446
447 #endif
448