1 /*
2 * Codel - The Controlled-Delay Active Queue Management algorithm.
3 *
4 * $FreeBSD: stable/12/sys/netpfil/ipfw/dn_aqm_codel.c 372482 2022-09-06 05:50:16Z gbe $
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
codel_sysctl_interval_handler(SYSCTL_HANDLER_ARGS)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
codel_sysctl_target_handler(SYSCTL_HANDLER_ARGS)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
control_law(struct codel_status * cst,struct dn_aqm_codel_parms * cprms,aqm_time_t 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 integers
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 *
codel_extract_head(struct dn_queue * q,aqm_time_t * pkt_ts)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 = V_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
aqm_codel_enqueue(struct dn_queue * q,struct mbuf * m)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 goto drop;
258
259 *(aqm_time_t *)(mtag + 1) = AQM_UNOW;
260 m_tag_prepend(m, mtag);
261
262 mq_append(&q->mq, m);
263 update_stats(q, len, 0);
264 return (0);
265
266 drop:
267 update_stats(q, 0, 1);
268 FREE_PKT(m);
269 return (1);
270 }
271
272
273 /* Dequeue a pcaket from queue q */
274 static struct mbuf *
aqm_codel_dequeue(struct dn_queue * q)275 aqm_codel_dequeue(struct dn_queue *q)
276 {
277 return codel_dequeue(q);
278 }
279
280 /*
281 * initialize Codel for queue 'q'
282 * First allocate memory for codel status.
283 */
284 static int
aqm_codel_init(struct dn_queue * q)285 aqm_codel_init(struct dn_queue *q)
286 {
287 struct codel_status *cst;
288
289 if (!q->fs->aqmcfg) {
290 D("Codel is not configure!d");
291 return EINVAL;
292 }
293
294 q->aqm_status = malloc(sizeof(struct codel_status),
295 M_DUMMYNET, M_NOWAIT | M_ZERO);
296 if (q->aqm_status == NULL) {
297 D("Cannot allocate AQM_codel private data");
298 return ENOMEM ;
299 }
300
301 /* init codel status variables */
302 cst = q->aqm_status;
303 cst->dropping=0;
304 cst->first_above_time=0;
305 cst->drop_next_time=0;
306 cst->count=0;
307 cst->maxpkt_size = 500;
308
309 /* increase reference counters */
310 codel_desc.ref_count++;
311
312 return 0;
313 }
314
315 /*
316 * Clean up Codel status for queue 'q'
317 * Destroy memory allocated for codel status.
318 */
319 static int
aqm_codel_cleanup(struct dn_queue * q)320 aqm_codel_cleanup(struct dn_queue *q)
321 {
322
323 if (q && q->aqm_status) {
324 free(q->aqm_status, M_DUMMYNET);
325 q->aqm_status = NULL;
326 /* decrease reference counters */
327 codel_desc.ref_count--;
328 }
329 else
330 D("Codel already cleaned up");
331 return 0;
332 }
333
334 /*
335 * Config codel parameters
336 * also allocate memory for codel configurations
337 */
338 static int
aqm_codel_config(struct dn_fsk * fs,struct dn_extra_parms * ep,int len)339 aqm_codel_config(struct dn_fsk* fs, struct dn_extra_parms *ep, int len)
340 {
341 struct dn_aqm_codel_parms *ccfg;
342
343 int l = sizeof(struct dn_extra_parms);
344 if (len < l) {
345 D("invalid sched parms length got %d need %d", len, l);
346 return EINVAL;
347 }
348 /* we free the old cfg because maybe the original allocation
349 * not the same size as the new one (different AQM type).
350 */
351 if (fs->aqmcfg) {
352 free(fs->aqmcfg, M_DUMMYNET);
353 fs->aqmcfg = NULL;
354 }
355
356 fs->aqmcfg = malloc(sizeof(struct dn_aqm_codel_parms),
357 M_DUMMYNET, M_NOWAIT | M_ZERO);
358 if (fs->aqmcfg== NULL) {
359 D("cannot allocate AQM_codel configuration parameters");
360 return ENOMEM;
361 }
362
363 /* configure codel parameters */
364 ccfg = fs->aqmcfg;
365
366 if (ep->par[0] < 0)
367 ccfg->target = codel_sysctl.target;
368 else
369 ccfg->target = ep->par[0] * AQM_TIME_1US;
370
371 if (ep->par[1] < 0)
372 ccfg->interval = codel_sysctl.interval;
373 else
374 ccfg->interval = ep->par[1] * AQM_TIME_1US;
375
376 if (ep->par[2] < 0)
377 ccfg->flags = 0;
378 else
379 ccfg->flags = ep->par[2];
380
381 /* bound codel configurations */
382 ccfg->target = BOUND_VAR(ccfg->target,1, 5 * AQM_TIME_1S);
383 ccfg->interval = BOUND_VAR(ccfg->interval,1, 5 * AQM_TIME_1S);
384 /* increase config reference counter */
385 codel_desc.cfg_ref_count++;
386
387 return 0;
388 }
389
390 /*
391 * Deconfigure Codel and free memory allocation
392 */
393 static int
aqm_codel_deconfig(struct dn_fsk * fs)394 aqm_codel_deconfig(struct dn_fsk* fs)
395 {
396
397 if (fs && fs->aqmcfg) {
398 free(fs->aqmcfg, M_DUMMYNET);
399 fs->aqmcfg = NULL;
400 fs->aqmfp = NULL;
401 /* decrease config reference counter */
402 codel_desc.cfg_ref_count--;
403 }
404
405 return 0;
406 }
407
408 /*
409 * Retrieve Codel configuration parameters.
410 */
411 static int
aqm_codel_getconfig(struct dn_fsk * fs,struct dn_extra_parms * ep)412 aqm_codel_getconfig(struct dn_fsk *fs, struct dn_extra_parms * ep)
413 {
414 struct dn_aqm_codel_parms *ccfg;
415
416 if (fs->aqmcfg) {
417 strlcpy(ep->name, codel_desc.name, sizeof(ep->name));
418 ccfg = fs->aqmcfg;
419 ep->par[0] = ccfg->target / AQM_TIME_1US;
420 ep->par[1] = ccfg->interval / AQM_TIME_1US;
421 ep->par[2] = ccfg->flags;
422 return 0;
423 }
424 return 1;
425 }
426
427 static struct dn_aqm codel_desc = {
428 _SI( .type = ) DN_AQM_CODEL,
429 _SI( .name = ) "CODEL",
430 _SI( .enqueue = ) aqm_codel_enqueue,
431 _SI( .dequeue = ) aqm_codel_dequeue,
432 _SI( .config = ) aqm_codel_config,
433 _SI( .getconfig = ) aqm_codel_getconfig,
434 _SI( .deconfig = ) aqm_codel_deconfig,
435 _SI( .init = ) aqm_codel_init,
436 _SI( .cleanup = ) aqm_codel_cleanup,
437 };
438
439 DECLARE_DNAQM_MODULE(dn_aqm_codel, &codel_desc);
440
441
442 #endif
443