Line data Source code
1 : /*
2 : * Copyright (c) 2017 Mike Belopuhov
3 : *
4 : * Permission to use, copy, modify, and distribute this software for any
5 : * purpose with or without fee is hereby granted, provided that the above
6 : * copyright notice and this permission notice appear in all copies.
7 : *
8 : * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 : * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 : * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 : * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 : * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 : * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 : * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15 : */
16 :
17 : /*
18 : * Codel - The Controlled-Delay Active Queue Management algorithm
19 : * IETF draft-ietf-aqm-codel-07
20 : *
21 : * Based on the algorithm by Kathleen Nichols and Van Jacobson with
22 : * improvements from Dave Taht and Eric Dumazet.
23 : */
24 :
25 : /*
26 : * The FlowQueue-CoDel Packet Scheduler and Active Queue Management
27 : * IETF draft-ietf-aqm-fq-codel-06
28 : *
29 : * Based on the implementation by Rasool Al-Saadi, Centre for Advanced
30 : * Internet Architectures, Swinburne University of Technology, Melbourne,
31 : * Australia.
32 : */
33 :
34 : #include <sys/param.h>
35 : #include <sys/systm.h>
36 : #include <sys/socket.h>
37 : #include <sys/mbuf.h>
38 : #include <sys/queue.h>
39 :
40 : #include <net/if.h>
41 : #include <net/if_var.h>
42 : #include <net/pfvar.h>
43 : #include <net/fq_codel.h>
44 :
45 : /* #define FQCODEL_DEBUG 1 */
46 :
47 : #ifdef FQCODEL_DEBUG
48 : #define DPRINTF(x...) printf(x)
49 : #else
50 : #define DPRINTF(x...)
51 : #endif
52 :
53 : struct codel {
54 : struct mbuf_list q;
55 :
56 : unsigned int dropping:1; /* Dropping state */
57 : unsigned int backlog:31; /* Number of bytes in the queue */
58 :
59 : unsigned short drops; /* Free running counter of drops */
60 : unsigned short ldrops; /* Value from the previous run */
61 :
62 : int64_t start; /* The moment queue was above target */
63 : int64_t next; /* Next interval */
64 : int64_t delay; /* Delay incurred by the last packet */
65 : };
66 :
67 : struct codel_params {
68 : int64_t target;
69 : int64_t interval;
70 : int quantum;
71 :
72 : uint32_t *intervals;
73 : };
74 :
75 : void codel_initparams(struct codel_params *, unsigned int,
76 : unsigned int, int);
77 : void codel_freeparams(struct codel_params *);
78 : void codel_enqueue(struct codel *, int64_t, struct mbuf *);
79 : struct mbuf *codel_dequeue(struct codel *, struct codel_params *, int64_t,
80 : struct mbuf_list *, uint64_t *, uint64_t *);
81 : struct mbuf *codel_commit(struct codel *, struct mbuf *);
82 : void codel_purge(struct codel *, struct mbuf_list *ml);
83 :
84 : struct flow {
85 : struct codel cd;
86 : int active:1;
87 : int deficit:31;
88 : #ifdef FQCODEL_DEBUG
89 : uint16_t id;
90 : #endif
91 : SIMPLEQ_ENTRY(flow) flowentry;
92 : };
93 : SIMPLEQ_HEAD(flowq, flow);
94 :
95 : struct fqcodel {
96 : struct flowq newq;
97 : struct flowq oldq;
98 :
99 : struct flow *flows;
100 : unsigned int qlength;
101 :
102 : struct ifnet *ifp;
103 :
104 : struct codel_params cparams;
105 :
106 : unsigned int nflows;
107 : unsigned int qlimit;
108 : int quantum;
109 :
110 : unsigned int flags;
111 : #define FQCF_FIXED_QUANTUM 0x1
112 :
113 : /* stats */
114 : struct fqcodel_pktcntr xmit_cnt;
115 : struct fqcodel_pktcntr drop_cnt;
116 : };
117 :
118 : unsigned int fqcodel_idx(unsigned int, const struct mbuf *);
119 : void *fqcodel_alloc(unsigned int, void *);
120 : void fqcodel_free(unsigned int, void *);
121 : struct mbuf *fqcodel_if_enq(struct ifqueue *, struct mbuf *);
122 : struct mbuf *fqcodel_if_deq_begin(struct ifqueue *, void **);
123 : void fqcodel_if_deq_commit(struct ifqueue *, struct mbuf *, void *);
124 : void fqcodel_if_purge(struct ifqueue *, struct mbuf_list *);
125 :
126 : struct mbuf *fqcodel_enq(struct fqcodel *, struct mbuf *);
127 : struct mbuf *fqcodel_deq_begin(struct fqcodel *, void **,
128 : struct mbuf_list *);
129 : void fqcodel_deq_commit(struct fqcodel *, struct mbuf *, void *);
130 : void fqcodel_purge(struct fqcodel *, struct mbuf_list *);
131 :
132 : /*
133 : * ifqueue glue.
134 : */
135 :
136 : static const struct ifq_ops fqcodel_ops = {
137 : fqcodel_idx,
138 : fqcodel_if_enq,
139 : fqcodel_if_deq_begin,
140 : fqcodel_if_deq_commit,
141 : fqcodel_if_purge,
142 : fqcodel_alloc,
143 : fqcodel_free
144 : };
145 :
146 : const struct ifq_ops * const ifq_fqcodel_ops = &fqcodel_ops;
147 :
148 : void *fqcodel_pf_alloc(struct ifnet *);
149 : int fqcodel_pf_addqueue(void *, struct pf_queuespec *);
150 : void fqcodel_pf_free(void *);
151 : int fqcodel_pf_qstats(struct pf_queuespec *, void *, int *);
152 : unsigned int fqcodel_pf_qlength(void *);
153 : struct mbuf * fqcodel_pf_enqueue(void *, struct mbuf *);
154 : struct mbuf * fqcodel_pf_deq_begin(void *, void **, struct mbuf_list *);
155 : void fqcodel_pf_deq_commit(void *, struct mbuf *, void *);
156 : void fqcodel_pf_purge(void *, struct mbuf_list *);
157 :
158 : /*
159 : * pf queue glue.
160 : */
161 :
162 : static const struct pfq_ops fqcodel_pf_ops = {
163 : fqcodel_pf_alloc,
164 : fqcodel_pf_addqueue,
165 : fqcodel_pf_free,
166 : fqcodel_pf_qstats,
167 : fqcodel_pf_qlength,
168 : fqcodel_pf_enqueue,
169 : fqcodel_pf_deq_begin,
170 : fqcodel_pf_deq_commit,
171 : fqcodel_pf_purge
172 : };
173 :
174 : const struct pfq_ops * const pfq_fqcodel_ops = &fqcodel_pf_ops;
175 :
176 : /* Default aggregate queue depth */
177 : static const unsigned int fqcodel_qlimit = 1024;
178 :
179 : /*
180 : * CoDel implementation
181 : */
182 :
183 : /* Delay target, 5ms */
184 : static const int64_t codel_target = 5000000;
185 :
186 : /* Grace period after last drop, 16 100ms intervals */
187 : static const int64_t codel_grace = 1600000000;
188 :
189 : /* First 399 "100 / sqrt(x)" intervarls, ns precision */
190 : static const uint32_t codel_intervals[] = {
191 : 100000000, 70710678, 57735027, 50000000, 44721360, 40824829, 37796447,
192 : 35355339, 33333333, 31622777, 30151134, 28867513, 27735010, 26726124,
193 : 25819889, 25000000, 24253563, 23570226, 22941573, 22360680, 21821789,
194 : 21320072, 20851441, 20412415, 20000000, 19611614, 19245009, 18898224,
195 : 18569534, 18257419, 17960530, 17677670, 17407766, 17149859, 16903085,
196 : 16666667, 16439899, 16222142, 16012815, 15811388, 15617376, 15430335,
197 : 15249857, 15075567, 14907120, 14744196, 14586499, 14433757, 14285714,
198 : 14142136, 14002801, 13867505, 13736056, 13608276, 13483997, 13363062,
199 : 13245324, 13130643, 13018891, 12909944, 12803688, 12700013, 12598816,
200 : 12500000, 12403473, 12309149, 12216944, 12126781, 12038585, 11952286,
201 : 11867817, 11785113, 11704115, 11624764, 11547005, 11470787, 11396058,
202 : 11322770, 11250879, 11180340, 11111111, 11043153, 10976426, 10910895,
203 : 10846523, 10783277, 10721125, 10660036, 10599979, 10540926, 10482848,
204 : 10425721, 10369517, 10314212, 10259784, 10206207, 10153462, 10101525,
205 : 10050378, 10000000, 9950372, 9901475, 9853293, 9805807, 9759001,
206 : 9712859, 9667365, 9622504, 9578263, 9534626, 9491580, 9449112,
207 : 9407209, 9365858, 9325048, 9284767, 9245003, 9205746, 9166985,
208 : 9128709, 9090909, 9053575, 9016696, 8980265, 8944272, 8908708,
209 : 8873565, 8838835, 8804509, 8770580, 8737041, 8703883, 8671100,
210 : 8638684, 8606630, 8574929, 8543577, 8512565, 8481889, 8451543,
211 : 8421519, 8391814, 8362420, 8333333, 8304548, 8276059, 8247861,
212 : 8219949, 8192319, 8164966, 8137885, 8111071, 8084521, 8058230,
213 : 8032193, 8006408, 7980869, 7955573, 7930516, 7905694, 7881104,
214 : 7856742, 7832604, 7808688, 7784989, 7761505, 7738232, 7715167,
215 : 7692308, 7669650, 7647191, 7624929, 7602859, 7580980, 7559289,
216 : 7537784, 7516460, 7495317, 7474351, 7453560, 7432941, 7412493,
217 : 7392213, 7372098, 7352146, 7332356, 7312724, 7293250, 7273930,
218 : 7254763, 7235746, 7216878, 7198158, 7179582, 7161149, 7142857,
219 : 7124705, 7106691, 7088812, 7071068, 7053456, 7035975, 7018624,
220 : 7001400, 6984303, 6967330, 6950480, 6933752, 6917145, 6900656,
221 : 6884284, 6868028, 6851887, 6835859, 6819943, 6804138, 6788442,
222 : 6772855, 6757374, 6741999, 6726728, 6711561, 6696495, 6681531,
223 : 6666667, 6651901, 6637233, 6622662, 6608186, 6593805, 6579517,
224 : 6565322, 6551218, 6537205, 6523281, 6509446, 6495698, 6482037,
225 : 6468462, 6454972, 6441566, 6428243, 6415003, 6401844, 6388766,
226 : 6375767, 6362848, 6350006, 6337243, 6324555, 6311944, 6299408,
227 : 6286946, 6274558, 6262243, 6250000, 6237829, 6225728, 6213698,
228 : 6201737, 6189845, 6178021, 6166264, 6154575, 6142951, 6131393,
229 : 6119901, 6108472, 6097108, 6085806, 6074567, 6063391, 6052275,
230 : 6041221, 6030227, 6019293, 6008418, 5997601, 5986843, 5976143,
231 : 5965500, 5954913, 5944383, 5933908, 5923489, 5913124, 5902813,
232 : 5892557, 5882353, 5872202, 5862104, 5852057, 5842062, 5832118,
233 : 5822225, 5812382, 5802589, 5792844, 5783149, 5773503, 5763904,
234 : 5754353, 5744850, 5735393, 5725983, 5716620, 5707301, 5698029,
235 : 5688801, 5679618, 5670480, 5661385, 5652334, 5643326, 5634362,
236 : 5625440, 5616560, 5607722, 5598925, 5590170, 5581456, 5572782,
237 : 5564149, 5555556, 5547002, 5538488, 5530013, 5521576, 5513178,
238 : 5504819, 5496497, 5488213, 5479966, 5471757, 5463584, 5455447,
239 : 5447347, 5439283, 5431254, 5423261, 5415304, 5407381, 5399492,
240 : 5391639, 5383819, 5376033, 5368281, 5360563, 5352877, 5345225,
241 : 5337605, 5330018, 5322463, 5314940, 5307449, 5299989, 5292561,
242 : 5285164, 5277798, 5270463, 5263158, 5255883, 5248639, 5241424,
243 : 5234239, 5227084, 5219958, 5212860, 5205792, 5198752, 5191741,
244 : 5184758, 5177804, 5170877, 5163978, 5157106, 5150262, 5143445,
245 : 5136655, 5129892, 5123155, 5116445, 5109761, 5103104, 5096472,
246 : 5089866, 5083286, 5076731, 5070201, 5063697, 5057217, 5050763,
247 : 5044333, 5037927, 5031546, 5025189, 5018856, 5012547, 5006262
248 : };
249 :
250 : void
251 0 : codel_initparams(struct codel_params *cp, unsigned int target,
252 : unsigned int interval, int quantum)
253 : {
254 : uint64_t mult;
255 : unsigned int i;
256 :
257 : /*
258 : * Update observation intervals table according to the configured
259 : * initial interval value.
260 : */
261 0 : if (interval > codel_intervals[0]) {
262 : /* Select either specified target or 5% of an interval */
263 0 : cp->target = MAX(target, interval / 5);
264 0 : cp->interval = interval;
265 :
266 : /* The coefficient is scaled up by a 1000 */
267 0 : mult = ((uint64_t)cp->interval * 1000) / codel_intervals[0];
268 :
269 : /* Prepare table of intervals */
270 0 : cp->intervals = mallocarray(nitems(codel_intervals),
271 : sizeof(codel_intervals[0]), M_DEVBUF, M_WAITOK | M_ZERO);
272 0 : for (i = 0; i < nitems(codel_intervals); i++)
273 0 : cp->intervals[i] = ((uint64_t)codel_intervals[i] *
274 0 : mult) / 1000;
275 : } else {
276 0 : cp->target = MAX(target, codel_target);
277 0 : cp->interval = codel_intervals[0];
278 0 : cp->intervals = (uint32_t *)codel_intervals;
279 : }
280 :
281 0 : cp->quantum = quantum;
282 0 : }
283 :
284 : void
285 0 : codel_freeparams(struct codel_params *cp)
286 : {
287 0 : if (cp->intervals != codel_intervals)
288 0 : free(cp->intervals, M_DEVBUF, nitems(codel_intervals) *
289 : sizeof(codel_intervals[0]));
290 0 : cp->intervals = NULL;
291 0 : }
292 :
293 : static inline void
294 0 : codel_gettime(int64_t *now)
295 : {
296 0 : struct timespec tv;
297 :
298 0 : nanouptime(&tv);
299 0 : *now = tv.tv_sec * 1000000000LL + tv.tv_nsec;
300 0 : }
301 :
302 : static inline unsigned int
303 0 : codel_backlog(struct codel *cd)
304 : {
305 0 : return (cd->backlog);
306 : }
307 :
308 : static inline unsigned int
309 0 : codel_qlength(struct codel *cd)
310 : {
311 0 : return (ml_len(&cd->q));
312 : }
313 :
314 : static inline int64_t
315 0 : codel_delay(struct codel *cd)
316 : {
317 0 : return (cd->delay);
318 : }
319 :
320 : void
321 0 : codel_enqueue(struct codel *cd, int64_t now, struct mbuf *m)
322 : {
323 0 : m->m_pkthdr.ph_timestamp = now;
324 :
325 0 : ml_enqueue(&cd->q, m);
326 0 : cd->backlog += m->m_pkthdr.len;
327 0 : }
328 :
329 : /*
330 : * Select the next interval according to the number of drops
331 : * in the current one relative to the provided timestamp.
332 : */
333 : static inline void
334 0 : control_law(struct codel *cd, struct codel_params *cp, int64_t rts)
335 : {
336 : unsigned int idx;
337 :
338 0 : idx = min(cd->drops, nitems(codel_intervals) - 1);
339 0 : cd->next = rts + cp->intervals[idx];
340 0 : }
341 :
342 : /*
343 : * Pick the next enqueued packet and determine the queueing delay
344 : * as well as whether or not it's a good candidate for dropping
345 : * from the queue.
346 : *
347 : * The decision whether to drop the packet or not is made based
348 : * on the queueing delay target of 5ms and on the current queue
349 : * length in bytes which shouldn't be less than the amount of data
350 : * that arrives in a typical interarrival time (MTU-sized packets
351 : * arriving spaced by the amount of time it takes to send such a
352 : * packet on the bottleneck).
353 : */
354 : static inline struct mbuf *
355 0 : codel_next_packet(struct codel *cd, struct codel_params *cp, int64_t now,
356 : int *drop)
357 : {
358 : struct mbuf *m;
359 :
360 0 : *drop = 0;
361 :
362 0 : m = MBUF_LIST_FIRST(&cd->q);
363 0 : if (m == NULL) {
364 0 : KASSERT(cd->backlog == 0);
365 : /* Empty queue, reset interval */
366 0 : cd->start = 0;
367 0 : return (NULL);
368 : }
369 :
370 0 : if (now - m->m_pkthdr.ph_timestamp < cp->target ||
371 0 : cd->backlog <= cp->quantum) {
372 : /*
373 : * The minimum delay decreased below the target, reset
374 : * the current observation interval.
375 : */
376 0 : cd->start = 0;
377 0 : return (m);
378 : }
379 :
380 0 : if (cd->start == 0) {
381 : /*
382 : * This is the first packet to be delayed for more than
383 : * the target, start the first observation interval after
384 : * a single RTT and see if the minimum delay goes below
385 : * the target within the interval, otherwise punish the
386 : * next packet.
387 : */
388 0 : cd->start = now + cp->interval;
389 0 : } else if (now > cd->start) {
390 0 : *drop = 1;
391 0 : }
392 0 : return (m);
393 0 : }
394 :
395 : enum { INITIAL, ACCEPTING, FIRSTDROP, DROPPING, CONTROL, RECOVERY };
396 :
397 : static inline int
398 0 : codel_state_change(struct codel *cd, int64_t now, struct mbuf *m, int drop,
399 : int state)
400 : {
401 0 : if (state == FIRSTDROP)
402 0 : return (ACCEPTING);
403 :
404 0 : if (cd->dropping) {
405 0 : if (!drop)
406 0 : return (RECOVERY);
407 0 : else if (now >= cd->next)
408 0 : return (state == DROPPING ? CONTROL : DROPPING);
409 0 : } else if (drop)
410 0 : return (FIRSTDROP);
411 :
412 0 : if (m == NULL)
413 0 : return (RECOVERY);
414 :
415 0 : return (ACCEPTING);
416 0 : }
417 :
418 : struct mbuf *
419 0 : codel_dequeue(struct codel *cd, struct codel_params *cp, int64_t now,
420 : struct mbuf_list *free_ml, uint64_t *dpkts, uint64_t *dbytes)
421 : {
422 : struct mbuf *m;
423 : unsigned short delta;
424 0 : int drop, state, done = 0;
425 :
426 : state = INITIAL;
427 :
428 0 : while (!done) {
429 0 : m = codel_next_packet(cd, cp, now, &drop);
430 0 : state = codel_state_change(cd, now, m, drop, state);
431 :
432 0 : switch (state) {
433 : case FIRSTDROP:
434 0 : m = codel_commit(cd, m);
435 0 : ml_enqueue(free_ml, m);
436 :
437 0 : *dpkts += 1;
438 0 : *dbytes += m->m_pkthdr.len;
439 :
440 0 : cd->dropping = 1;
441 :
442 : /*
443 : * If we're still within the grace period and not
444 : * meeting our minimal delay target we treat this
445 : * as a continuation of the previous observation
446 : * interval and shrink it further. Otherwise we
447 : * start from the initial one.
448 : */
449 0 : delta = cd->drops - cd->ldrops;
450 0 : if (delta > 1) {
451 0 : if (now < cd->next ||
452 0 : now - cd->next < codel_grace)
453 0 : cd->drops = delta;
454 : else
455 0 : cd->drops = 1;
456 : } else
457 0 : cd->drops = 1;
458 0 : control_law(cd, cp, now);
459 0 : cd->ldrops = cd->drops;
460 :
461 : /* fetches the next packet and goes to ACCEPTING */
462 0 : break;
463 : case DROPPING:
464 0 : m = codel_commit(cd, m);
465 0 : ml_enqueue(free_ml, m);
466 0 : cd->drops++;
467 :
468 0 : *dpkts += 1;
469 0 : *dbytes += m->m_pkthdr.len;
470 :
471 : /* fetches the next packet and goes to CONTROL */
472 0 : break;
473 : case CONTROL:
474 0 : if (drop) {
475 0 : control_law(cd, cp, cd->next);
476 0 : continue;
477 : }
478 : /* FALLTHROUGH */
479 : case RECOVERY:
480 0 : cd->dropping = 0;
481 : /* FALLTHROUGH */
482 : case ACCEPTING:
483 : done = 1;
484 0 : break;
485 : }
486 : }
487 :
488 0 : if (m != NULL)
489 0 : cd->delay = now - m->m_pkthdr.ph_timestamp;
490 :
491 0 : return (m);
492 0 : }
493 :
494 : struct mbuf *
495 0 : codel_commit(struct codel *cd, struct mbuf *m)
496 : {
497 : struct mbuf *n;
498 :
499 0 : n = ml_dequeue(&cd->q);
500 0 : if (m)
501 0 : KASSERT(n == m);
502 0 : KASSERT(n != NULL);
503 0 : KASSERT(cd->backlog >= n->m_pkthdr.len);
504 0 : cd->backlog -= n->m_pkthdr.len;
505 0 : return (n);
506 : }
507 :
508 : void
509 0 : codel_purge(struct codel *cd, struct mbuf_list *ml)
510 : {
511 0 : ml_enlist(ml, &cd->q);
512 0 : cd->backlog = 0;
513 0 : }
514 :
515 : /*
516 : * FQ-CoDel implementation
517 : */
518 :
519 : static inline struct flow *
520 0 : classify_flow(struct fqcodel *fqc, struct mbuf *m)
521 : {
522 : unsigned int index;
523 :
524 0 : if (m->m_pkthdr.ph_flowid & M_FLOWID_VALID)
525 0 : index = (m->m_pkthdr.ph_flowid & M_FLOWID_MASK) % fqc->nflows;
526 : else
527 0 : index = arc4random_uniform(fqc->nflows);
528 :
529 : DPRINTF("%s: %u\n", __func__, index);
530 :
531 0 : return (&fqc->flows[index]);
532 : }
533 :
534 : struct mbuf *
535 0 : fqcodel_enq(struct fqcodel *fqc, struct mbuf *m)
536 : {
537 : struct flow *flow;
538 : unsigned int backlog = 0;
539 0 : int64_t now;
540 : int i;
541 :
542 0 : flow = classify_flow(fqc, m);
543 0 : if (flow == NULL)
544 0 : return (m);
545 :
546 0 : codel_gettime(&now);
547 0 : codel_enqueue(&flow->cd, now, m);
548 0 : fqc->qlength++;
549 :
550 0 : if (!flow->active) {
551 0 : SIMPLEQ_INSERT_TAIL(&fqc->newq, flow, flowentry);
552 0 : flow->deficit = fqc->quantum;
553 0 : flow->active = 1;
554 : DPRINTF("%s: flow %u active deficit %d\n", __func__,
555 : flow->id, flow->deficit);
556 0 : }
557 :
558 : /*
559 : * Check the limit for all queues and remove a packet
560 : * from the longest one.
561 : */
562 0 : if (fqc->qlength >= fqcodel_qlimit) {
563 0 : for (i = 0; i < fqc->nflows; i++) {
564 0 : if (codel_backlog(&fqc->flows[i].cd) > backlog) {
565 0 : flow = &fqc->flows[i];
566 0 : backlog = codel_backlog(&flow->cd);
567 0 : }
568 : }
569 :
570 0 : KASSERT(flow != NULL);
571 0 : m = codel_commit(&flow->cd, NULL);
572 :
573 0 : fqc->drop_cnt.packets++;
574 0 : fqc->drop_cnt.bytes += m->m_pkthdr.len;
575 :
576 0 : fqc->qlength--;
577 :
578 : DPRINTF("%s: dropping from flow %u\n", __func__,
579 : flow->id);
580 0 : return (m);
581 : }
582 :
583 0 : return (NULL);
584 0 : }
585 :
586 : static inline struct flowq *
587 0 : select_queue(struct fqcodel *fqc)
588 : {
589 : struct flowq *fq = NULL;
590 :
591 0 : if (!SIMPLEQ_EMPTY(&fqc->newq))
592 0 : fq = &fqc->newq;
593 0 : else if (!SIMPLEQ_EMPTY(&fqc->oldq))
594 0 : fq = &fqc->oldq;
595 0 : return (fq);
596 : }
597 :
598 : static inline struct flow *
599 0 : first_flow(struct fqcodel *fqc, struct flowq **fq)
600 : {
601 : struct flow *flow;
602 :
603 0 : while ((*fq = select_queue(fqc)) != NULL) {
604 0 : while ((flow = SIMPLEQ_FIRST(*fq)) != NULL) {
605 0 : if (flow->deficit <= 0) {
606 0 : flow->deficit += fqc->quantum;
607 0 : SIMPLEQ_REMOVE_HEAD(*fq, flowentry);
608 0 : SIMPLEQ_INSERT_TAIL(&fqc->oldq, flow,
609 : flowentry);
610 : DPRINTF("%s: flow %u deficit %d\n", __func__,
611 : flow->id, flow->deficit);
612 : } else
613 0 : return (flow);
614 : }
615 : }
616 :
617 0 : return (NULL);
618 0 : }
619 :
620 : static inline struct flow *
621 0 : next_flow(struct fqcodel *fqc, struct flow *flow, struct flowq **fq)
622 : {
623 0 : SIMPLEQ_REMOVE_HEAD(*fq, flowentry);
624 :
625 0 : if (*fq == &fqc->newq && !SIMPLEQ_EMPTY(&fqc->oldq)) {
626 : /* A packet was dropped, starve the queue */
627 0 : SIMPLEQ_INSERT_TAIL(&fqc->oldq, flow, flowentry);
628 : DPRINTF("%s: flow %u ->oldq deficit %d\n", __func__,
629 : flow->id, flow->deficit);
630 0 : } else {
631 : /* A packet was dropped on a starved queue, disable it */
632 0 : flow->active = 0;
633 : DPRINTF("%s: flow %u inactive deficit %d\n", __func__,
634 : flow->id, flow->deficit);
635 : }
636 :
637 0 : return (first_flow(fqc, fq));
638 : }
639 :
640 : struct mbuf *
641 0 : fqcodel_deq_begin(struct fqcodel *fqc, void **cookiep,
642 : struct mbuf_list *free_ml)
643 : {
644 0 : struct mbuf_list ml = MBUF_LIST_INITIALIZER();
645 0 : struct flowq *fq;
646 : struct flow *flow;
647 : struct mbuf *m;
648 0 : int64_t now;
649 :
650 0 : if ((fqc->flags & FQCF_FIXED_QUANTUM) == 0)
651 0 : fqc->quantum = fqc->ifp->if_mtu + max_linkhdr;
652 :
653 0 : codel_gettime(&now);
654 :
655 0 : for (flow = first_flow(fqc, &fq); flow != NULL;
656 0 : flow = next_flow(fqc, flow, &fq)) {
657 0 : m = codel_dequeue(&flow->cd, &fqc->cparams, now, &ml,
658 0 : &fqc->drop_cnt.packets, &fqc->drop_cnt.bytes);
659 :
660 0 : KASSERT(fqc->qlength >= ml_len(&ml));
661 0 : fqc->qlength -= ml_len(&ml);
662 :
663 0 : ml_enlist(free_ml, &ml);
664 :
665 0 : if (m != NULL) {
666 0 : flow->deficit -= m->m_pkthdr.len;
667 : DPRINTF("%s: flow %u deficit %d\n", __func__,
668 : flow->id, flow->deficit);
669 0 : *cookiep = flow;
670 0 : return (m);
671 : }
672 : }
673 :
674 0 : return (NULL);
675 0 : }
676 :
677 : void
678 0 : fqcodel_deq_commit(struct fqcodel *fqc, struct mbuf *m, void *cookie)
679 : {
680 0 : struct flow *flow = cookie;
681 :
682 0 : KASSERT(fqc->qlength > 0);
683 0 : fqc->qlength--;
684 :
685 0 : fqc->xmit_cnt.packets++;
686 0 : fqc->xmit_cnt.bytes += m->m_pkthdr.len;
687 :
688 0 : (void)codel_commit(&flow->cd, m);
689 0 : }
690 :
691 : void
692 0 : fqcodel_purge(struct fqcodel *fqc, struct mbuf_list *ml)
693 : {
694 : unsigned int i;
695 :
696 0 : for (i = 0; i < fqc->nflows; i++)
697 0 : codel_purge(&fqc->flows[i].cd, ml);
698 0 : fqc->qlength = 0;
699 0 : }
700 :
701 : struct mbuf *
702 0 : fqcodel_if_enq(struct ifqueue *ifq, struct mbuf *m)
703 : {
704 0 : return fqcodel_enq(ifq->ifq_q, m);
705 : }
706 :
707 : struct mbuf *
708 0 : fqcodel_if_deq_begin(struct ifqueue *ifq, void **cookiep)
709 : {
710 0 : struct mbuf_list free_ml = MBUF_LIST_INITIALIZER();
711 : struct mbuf *m;
712 :
713 0 : m = fqcodel_deq_begin(ifq->ifq_q, cookiep, &free_ml);
714 0 : ifq_mfreeml(ifq, &free_ml);
715 0 : return (m);
716 0 : }
717 :
718 : void
719 0 : fqcodel_if_deq_commit(struct ifqueue *ifq, struct mbuf *m, void *cookie)
720 : {
721 0 : return fqcodel_deq_commit(ifq->ifq_q, m, cookie);
722 : }
723 :
724 : void
725 0 : fqcodel_if_purge(struct ifqueue *ifq, struct mbuf_list *ml)
726 : {
727 0 : return fqcodel_purge(ifq->ifq_q, ml);
728 : }
729 :
730 : void *
731 0 : fqcodel_pf_alloc(struct ifnet *ifp)
732 : {
733 : struct fqcodel *fqc;
734 :
735 0 : fqc = malloc(sizeof(struct fqcodel), M_DEVBUF, M_WAITOK | M_ZERO);
736 :
737 0 : SIMPLEQ_INIT(&fqc->newq);
738 0 : SIMPLEQ_INIT(&fqc->oldq);
739 :
740 0 : return (fqc);
741 : }
742 :
743 : int
744 0 : fqcodel_pf_addqueue(void *arg, struct pf_queuespec *qs)
745 : {
746 0 : struct ifnet *ifp = qs->kif->pfik_ifp;
747 0 : struct fqcodel *fqc = arg;
748 :
749 0 : if (qs->flowqueue.flows == 0 || qs->flowqueue.flows > M_FLOWID_MASK)
750 0 : return (EINVAL);
751 :
752 0 : fqc->nflows = qs->flowqueue.flows;
753 0 : fqc->quantum = qs->flowqueue.quantum;
754 0 : if (qs->qlimit > 0)
755 0 : fqc->qlimit = qs->qlimit;
756 : else
757 0 : fqc->qlimit = fqcodel_qlimit;
758 0 : if (fqc->quantum > 0)
759 0 : fqc->flags |= FQCF_FIXED_QUANTUM;
760 : else
761 0 : fqc->quantum = ifp->if_mtu + max_linkhdr;
762 :
763 0 : codel_initparams(&fqc->cparams, qs->flowqueue.target,
764 0 : qs->flowqueue.interval, fqc->quantum);
765 :
766 0 : fqc->flows = mallocarray(fqc->nflows, sizeof(struct flow),
767 : M_DEVBUF, M_WAITOK | M_ZERO);
768 :
769 : #ifdef FQCODEL_DEBUG
770 : {
771 : unsigned int i;
772 :
773 : for (i = 0; i < fqc->nflows; i++)
774 : fqc->flows[i].id = i;
775 : }
776 : #endif
777 :
778 0 : fqc->ifp = ifp;
779 :
780 : DPRINTF("fq-codel on %s: %d queues %d deep, quantum %d target %llums "
781 : "interval %llums\n", ifp->if_xname, fqc->nflows, fqc->qlimit,
782 : fqc->quantum, fqc->cparams.target / 1000000,
783 : fqc->cparams.interval / 1000000);
784 :
785 0 : return (0);
786 0 : }
787 :
788 : void
789 0 : fqcodel_pf_free(void *arg)
790 : {
791 0 : struct fqcodel *fqc = arg;
792 :
793 0 : codel_freeparams(&fqc->cparams);
794 0 : free(fqc->flows, M_DEVBUF, fqc->nflows * sizeof(struct flow));
795 0 : free(fqc, M_DEVBUF, sizeof(struct fqcodel));
796 0 : }
797 :
798 : int
799 0 : fqcodel_pf_qstats(struct pf_queuespec *qs, void *ubuf, int *nbytes)
800 : {
801 0 : struct ifnet *ifp = qs->kif->pfik_ifp;
802 0 : struct fqcodel_stats stats;
803 : struct fqcodel *fqc;
804 : int64_t delay;
805 : unsigned int i;
806 : int error = 0;
807 :
808 0 : if (ifp == NULL)
809 0 : return (EBADF);
810 :
811 0 : if (*nbytes < sizeof(stats))
812 0 : return (EINVAL);
813 :
814 0 : memset(&stats, 0, sizeof(stats));
815 :
816 : /* XXX: multi-q? */
817 0 : fqc = ifq_q_enter(&ifp->if_snd, ifq_fqcodel_ops);
818 0 : if (fqc == NULL)
819 0 : return (EBADF);
820 :
821 0 : stats.xmit_cnt = fqc->xmit_cnt;
822 0 : stats.drop_cnt = fqc->drop_cnt;
823 :
824 0 : stats.qlength = ifq_len(&ifp->if_snd);
825 0 : stats.qlimit = fqc->qlimit;
826 :
827 0 : stats.flows = 0;
828 0 : stats.delaysum = stats.delaysumsq = 0;
829 :
830 0 : for (i = 0; i < fqc->nflows; i++) {
831 0 : if (codel_qlength(&fqc->flows[i].cd) == 0)
832 : continue;
833 : /* Scale down to microseconds to avoid overflows */
834 0 : delay = codel_delay(&fqc->flows[i].cd) / 1000;
835 0 : stats.delaysum += delay;
836 0 : stats.delaysumsq += delay * delay;
837 0 : stats.flows++;
838 0 : }
839 :
840 0 : ifq_q_leave(&ifp->if_snd, fqc);
841 :
842 0 : if ((error = copyout((caddr_t)&stats, ubuf, sizeof(stats))) != 0)
843 0 : return (error);
844 :
845 0 : *nbytes = sizeof(stats);
846 0 : return (0);
847 0 : }
848 :
849 : unsigned int
850 0 : fqcodel_pf_qlength(void *fqc)
851 : {
852 0 : return ((struct fqcodel *)fqc)->qlength;
853 : }
854 :
855 : struct mbuf *
856 0 : fqcodel_pf_enqueue(void *fqc, struct mbuf *m)
857 : {
858 0 : return fqcodel_enq(fqc, m);
859 : }
860 :
861 : struct mbuf *
862 0 : fqcodel_pf_deq_begin(void *fqc, void **cookiep, struct mbuf_list *free_ml)
863 : {
864 0 : return fqcodel_deq_begin(fqc, cookiep, free_ml);
865 : }
866 :
867 : void
868 0 : fqcodel_pf_deq_commit(void *fqc, struct mbuf *m, void *cookie)
869 : {
870 0 : return fqcodel_deq_commit(fqc, m, cookie);
871 : }
872 :
873 : void
874 0 : fqcodel_pf_purge(void *fqc, struct mbuf_list *ml)
875 : {
876 0 : return fqcodel_purge(fqc, ml);
877 : }
878 :
879 : unsigned int
880 0 : fqcodel_idx(unsigned int nqueues, const struct mbuf *m)
881 : {
882 0 : return (0);
883 : }
884 :
885 : void *
886 0 : fqcodel_alloc(unsigned int idx, void *arg)
887 : {
888 : /* Allocation is done in fqcodel_pf_alloc */
889 0 : return (arg);
890 : }
891 :
892 : void
893 0 : fqcodel_free(unsigned int idx, void *arg)
894 : {
895 : /* nothing to do here */
896 0 : }
|
