1 // SPDX-License-Identifier: GPL-2.0 OR BSD-3-Clause
3 /* COMMON Applications Kept Enhanced (CAKE) discipline
4 *
5 * Copyright (C) 2014-2018 Jonathan Morton <chromatix99@gmail.com>
6 * Copyright (C) 2015-2018 Toke Høiland-Jørgensen <toke@toke.dk>
7 * Copyright (C) 2014-2018 Dave Täht <dave.taht@gmail.com>
8 * Copyright (C) 2015-2018 Sebastian Moeller <moeller0@gmx.de>
9 * (C) 2015-2018 Kevin Darbyshire-Bryant <kevin@darbyshire-bryant.me.uk>
10 * Copyright (C) 2017-2018 Ryan Mounce <ryan@mounce.com.au>
11 *
12 * The CAKE Principles:
13 * (or, how to have your cake and eat it too)
14 *
15 * This is a combination of several shaping, AQM and FQ techniques into one
16 * easy-to-use package:
17 *
18 * - An overall bandwidth shaper, to move the bottleneck away from dumb CPE
19 * equipment and bloated MACs. This operates in deficit mode (as in sch_fq),
20 * eliminating the need for any sort of burst parameter (eg. token bucket
21 * depth). Burst support is limited to that necessary to overcome scheduling
22 * latency.
23 *
24 * - A Diffserv-aware priority queue, giving more priority to certain classes,
25 * up to a specified fraction of bandwidth. Above that bandwidth threshold,
26 * the priority is reduced to avoid starving other tins.
27 *
28 * - Each priority tin has a separate Flow Queue system, to isolate traffic
29 * flows from each other. This prevents a burst on one flow from increasing
30 * the delay to another. Flows are distributed to queues using a
31 * set-associative hash function.
32 *
33 * - Each queue is actively managed by Cobalt, which is a combination of the
34 * Codel and Blue AQM algorithms. This serves flows fairly, and signals
35 * congestion early via ECN (if available) and/or packet drops, to keep
36 * latency low. The codel parameters are auto-tuned based on the bandwidth
37 * setting, as is necessary at low bandwidths.
38 *
39 * The configuration parameters are kept deliberately simple for ease of use.
40 * Everything has sane defaults. Complete generality of configuration is *not*
41 * a goal.
42 *
43 * The priority queue operates according to a weighted DRR scheme, combined with
44 * a bandwidth tracker which reuses the shaper logic to detect which side of the
45 * bandwidth sharing threshold the tin is operating. This determines whether a
46 * priority-based weight (high) or a bandwidth-based weight (low) is used for
47 * that tin in the current pass.
48 *
49 * This qdisc was inspired by Eric Dumazet's fq_codel code, which he kindly
50 * granted us permission to leverage.
51 */
53 #include <linux/module.h>
54 #include <linux/types.h>
55 #include <linux/kernel.h>
56 #include <linux/jiffies.h>
57 #include <linux/string.h>
58 #include <linux/in.h>
59 #include <linux/errno.h>
60 #include <linux/init.h>
61 #include <linux/skbuff.h>
62 #include <linux/jhash.h>
63 #include <linux/slab.h>
64 #include <linux/vmalloc.h>
65 #include <linux/reciprocal_div.h>
66 #include <net/netlink.h>
67 #include <linux/if_vlan.h>
68 #include <net/pkt_sched.h>
69 #include <net/pkt_cls.h>
70 #include <net/tcp.h>
71 #include <net/flow_dissector.h>
73 #if IS_ENABLED(CONFIG_NF_CONNTRACK)
74 #include <net/netfilter/nf_conntrack_core.h>
75 #endif
77 #define CAKE_SET_WAYS (8)
78 #define CAKE_MAX_TINS (8)
79 #define CAKE_QUEUES (1024)
80 #define CAKE_FLOW_MASK 63
81 #define CAKE_FLOW_NAT_FLAG 64
83 /* struct cobalt_params - contains codel and blue parameters
84 * @interval: codel initial drop rate
85 * @target: maximum persistent sojourn time & blue update rate
86 * @mtu_time: serialisation delay of maximum-size packet
87 * @p_inc: increment of blue drop probability (0.32 fxp)
88 * @p_dec: decrement of blue drop probability (0.32 fxp)
89 */
90 struct cobalt_params {
91 u64 interval;
92 u64 target;
93 u64 mtu_time;
94 u32 p_inc;
95 u32 p_dec;
96 };
98 /* struct cobalt_vars - contains codel and blue variables
99 * @count: codel dropping frequency
100 * @rec_inv_sqrt: reciprocal value of sqrt(count) >> 1
101 * @drop_next: time to drop next packet, or when we dropped last
102 * @blue_timer: Blue time to next drop
103 * @p_drop: BLUE drop probability (0.32 fxp)
104 * @dropping: set if in dropping state
105 * @ecn_marked: set if marked
106 */
107 struct cobalt_vars {
108 u32 count;
109 u32 rec_inv_sqrt;
110 ktime_t drop_next;
111 ktime_t blue_timer;
112 u32 p_drop;
113 bool dropping;
114 bool ecn_marked;
115 };
117 enum {
118 CAKE_SET_NONE = 0,
119 CAKE_SET_SPARSE,
120 CAKE_SET_SPARSE_WAIT, /* counted in SPARSE, actually in BULK */
121 CAKE_SET_BULK,
122 CAKE_SET_DECAYING
123 };
125 struct cake_flow {
126 /* this stuff is all needed per-flow at dequeue time */
127 struct sk_buff *head;
128 struct sk_buff *tail;
129 struct list_head flowchain;
130 s32 deficit;
131 u32 dropped;
132 struct cobalt_vars cvars;
133 u16 srchost; /* index into cake_host table */
134 u16 dsthost;
135 u8 set;
136 }; /* please try to keep this structure <= 64 bytes */
138 struct cake_host {
139 u32 srchost_tag;
140 u32 dsthost_tag;
141 u16 srchost_refcnt;
142 u16 dsthost_refcnt;
143 };
145 struct cake_heap_entry {
146 u16 t:3, b:10;
147 };
149 struct cake_tin_data {
150 struct cake_flow flows[CAKE_QUEUES];
151 u32 backlogs[CAKE_QUEUES];
152 u32 tags[CAKE_QUEUES]; /* for set association */
153 u16 overflow_idx[CAKE_QUEUES];
154 struct cake_host hosts[CAKE_QUEUES]; /* for triple isolation */
155 u16 flow_quantum;
157 struct cobalt_params cparams;
158 u32 drop_overlimit;
159 u16 bulk_flow_count;
160 u16 sparse_flow_count;
161 u16 decaying_flow_count;
162 u16 unresponsive_flow_count;
164 u32 max_skblen;
166 struct list_head new_flows;
167 struct list_head old_flows;
168 struct list_head decaying_flows;
170 /* time_next = time_this + ((len * rate_ns) >> rate_shft) */
171 ktime_t time_next_packet;
172 u64 tin_rate_ns;
173 u64 tin_rate_bps;
174 u16 tin_rate_shft;
176 u16 tin_quantum_prio;
177 u16 tin_quantum_band;
178 s32 tin_deficit;
179 u32 tin_backlog;
180 u32 tin_dropped;
181 u32 tin_ecn_mark;
183 u32 packets;
184 u64 bytes;
186 u32 ack_drops;
188 /* moving averages */
189 u64 avge_delay;
190 u64 peak_delay;
191 u64 base_delay;
193 /* hash function stats */
194 u32 way_directs;
195 u32 way_hits;
196 u32 way_misses;
197 u32 way_collisions;
198 }; /* number of tins is small, so size of this struct doesn't matter much */
200 struct cake_sched_data {
201 struct tcf_proto __rcu *filter_list; /* optional external classifier */
202 struct tcf_block *block;
203 struct cake_tin_data *tins;
205 struct cake_heap_entry overflow_heap[CAKE_QUEUES * CAKE_MAX_TINS];
206 u16 overflow_timeout;
208 u16 tin_cnt;
209 u8 tin_mode;
210 u8 flow_mode;
211 u8 ack_filter;
212 u8 atm_mode;
214 /* time_next = time_this + ((len * rate_ns) >> rate_shft) */
215 u16 rate_shft;
216 ktime_t time_next_packet;
217 ktime_t failsafe_next_packet;
218 u64 rate_ns;
219 u64 rate_bps;
220 u16 rate_flags;
221 s16 rate_overhead;
222 u16 rate_mpu;
223 u64 interval;
224 u64 target;
226 /* resource tracking */
227 u32 buffer_used;
228 u32 buffer_max_used;
229 u32 buffer_limit;
230 u32 buffer_config_limit;
232 /* indices for dequeue */
233 u16 cur_tin;
234 u16 cur_flow;
236 struct qdisc_watchdog watchdog;
237 const u8 *tin_index;
238 const u8 *tin_order;
240 /* bandwidth capacity estimate */
241 ktime_t last_packet_time;
242 ktime_t avg_window_begin;
243 u64 avg_packet_interval;
244 u64 avg_window_bytes;
245 u64 avg_peak_bandwidth;
246 ktime_t last_reconfig_time;
248 /* packet length stats */
249 u32 avg_netoff;
250 u16 max_netlen;
251 u16 max_adjlen;
252 u16 min_netlen;
253 u16 min_adjlen;
254 };
256 enum {
257 CAKE_FLAG_OVERHEAD = BIT(0),
258 CAKE_FLAG_AUTORATE_INGRESS = BIT(1),
259 CAKE_FLAG_INGRESS = BIT(2),
260 CAKE_FLAG_WASH = BIT(3),
261 CAKE_FLAG_SPLIT_GSO = BIT(4)
262 };
264 /* COBALT operates the Codel and BLUE algorithms in parallel, in order to
265 * obtain the best features of each. Codel is excellent on flows which
266 * respond to congestion signals in a TCP-like way. BLUE is more effective on
267 * unresponsive flows.
268 */
270 struct cobalt_skb_cb {
271 ktime_t enqueue_time;
272 u32 adjusted_len;
273 };
275 static u64 us_to_ns(u64 us)
276 {
277 return us * NSEC_PER_USEC;
278 }
280 static struct cobalt_skb_cb *get_cobalt_cb(const struct sk_buff *skb)
281 {
282 qdisc_cb_private_validate(skb, sizeof(struct cobalt_skb_cb));
283 return (struct cobalt_skb_cb *)qdisc_skb_cb(skb)->data;
284 }
286 static ktime_t cobalt_get_enqueue_time(const struct sk_buff *skb)
287 {
288 return get_cobalt_cb(skb)->enqueue_time;
289 }
291 static void cobalt_set_enqueue_time(struct sk_buff *skb,
292 ktime_t now)
293 {
294 get_cobalt_cb(skb)->enqueue_time = now;
295 }
297 static u16 quantum_div[CAKE_QUEUES + 1] = {0};
299 /* Diffserv lookup tables */
301 static const u8 precedence[] = {
302 0, 0, 0, 0, 0, 0, 0, 0,
303 1, 1, 1, 1, 1, 1, 1, 1,
304 2, 2, 2, 2, 2, 2, 2, 2,
305 3, 3, 3, 3, 3, 3, 3, 3,
306 4, 4, 4, 4, 4, 4, 4, 4,
307 5, 5, 5, 5, 5, 5, 5, 5,
308 6, 6, 6, 6, 6, 6, 6, 6,
309 7, 7, 7, 7, 7, 7, 7, 7,
310 };
312 static const u8 diffserv8[] = {
313 2, 5, 1, 2, 4, 2, 2, 2,
314 0, 2, 1, 2, 1, 2, 1, 2,
315 5, 2, 4, 2, 4, 2, 4, 2,
316 3, 2, 3, 2, 3, 2, 3, 2,
317 6, 2, 3, 2, 3, 2, 3, 2,
318 6, 2, 2, 2, 6, 2, 6, 2,
319 7, 2, 2, 2, 2, 2, 2, 2,
320 7, 2, 2, 2, 2, 2, 2, 2,
321 };
323 static const u8 diffserv4[] = {
324 0, 2, 0, 0, 2, 0, 0, 0,
325 1, 0, 0, 0, 0, 0, 0, 0,
326 2, 0, 2, 0, 2, 0, 2, 0,
327 2, 0, 2, 0, 2, 0, 2, 0,
328 3, 0, 2, 0, 2, 0, 2, 0,
329 3, 0, 0, 0, 3, 0, 3, 0,
330 3, 0, 0, 0, 0, 0, 0, 0,
331 3, 0, 0, 0, 0, 0, 0, 0,
332 };
334 static const u8 diffserv3[] = {
335 0, 0, 0, 0, 2, 0, 0, 0,
336 1, 0, 0, 0, 0, 0, 0, 0,
337 0, 0, 0, 0, 0, 0, 0, 0,
338 0, 0, 0, 0, 0, 0, 0, 0,
339 0, 0, 0, 0, 0, 0, 0, 0,
340 0, 0, 0, 0, 2, 0, 2, 0,
341 2, 0, 0, 0, 0, 0, 0, 0,
342 2, 0, 0, 0, 0, 0, 0, 0,
343 };
345 static const u8 besteffort[] = {
346 0, 0, 0, 0, 0, 0, 0, 0,
347 0, 0, 0, 0, 0, 0, 0, 0,
348 0, 0, 0, 0, 0, 0, 0, 0,
349 0, 0, 0, 0, 0, 0, 0, 0,
350 0, 0, 0, 0, 0, 0, 0, 0,
351 0, 0, 0, 0, 0, 0, 0, 0,
352 0, 0, 0, 0, 0, 0, 0, 0,
353 0, 0, 0, 0, 0, 0, 0, 0,
354 };
356 /* tin priority order for stats dumping */
358 static const u8 normal_order[] = {0, 1, 2, 3, 4, 5, 6, 7};
359 static const u8 bulk_order[] = {1, 0, 2, 3};
361 #define REC_INV_SQRT_CACHE (16)
362 static u32 cobalt_rec_inv_sqrt_cache[REC_INV_SQRT_CACHE] = {0};
364 /* http://en.wikipedia.org/wiki/Methods_of_computing_square_roots
365 * new_invsqrt = (invsqrt / 2) * (3 - count * invsqrt^2)
366 *
367 * Here, invsqrt is a fixed point number (< 1.0), 32bit mantissa, aka Q0.32
368 */
370 static void cobalt_newton_step(struct cobalt_vars *vars)
371 {
372 u32 invsqrt, invsqrt2;
373 u64 val;
375 invsqrt = vars->rec_inv_sqrt;
376 invsqrt2 = ((u64)invsqrt * invsqrt) >> 32;
377 val = (3LL << 32) - ((u64)vars->count * invsqrt2);
379 val >>= 2; /* avoid overflow in following multiply */
380 val = (val * invsqrt) >> (32 - 2 + 1);
382 vars->rec_inv_sqrt = val;
383 }
385 static void cobalt_invsqrt(struct cobalt_vars *vars)
386 {
387 if (vars->count < REC_INV_SQRT_CACHE)
388 vars->rec_inv_sqrt = cobalt_rec_inv_sqrt_cache[vars->count];
389 else
390 cobalt_newton_step(vars);
391 }
393 /* There is a big difference in timing between the accurate values placed in
394 * the cache and the approximations given by a single Newton step for small
395 * count values, particularly when stepping from count 1 to 2 or vice versa.
396 * Above 16, a single Newton step gives sufficient accuracy in either
397 * direction, given the precision stored.
398 *
399 * The magnitude of the error when stepping up to count 2 is such as to give
400 * the value that *should* have been produced at count 4.
401 */
403 static void cobalt_cache_init(void)
404 {
405 struct cobalt_vars v;
407 memset(&v, 0, sizeof(v));
408 v.rec_inv_sqrt = ~0U;
409 cobalt_rec_inv_sqrt_cache[0] = v.rec_inv_sqrt;
411 for (v.count = 1; v.count < REC_INV_SQRT_CACHE; v.count++) {
412 cobalt_newton_step(&v);
413 cobalt_newton_step(&v);
414 cobalt_newton_step(&v);
415 cobalt_newton_step(&v);
417 cobalt_rec_inv_sqrt_cache[v.count] = v.rec_inv_sqrt;
418 }
419 }
421 static void cobalt_vars_init(struct cobalt_vars *vars)
422 {
423 memset(vars, 0, sizeof(*vars));
425 if (!cobalt_rec_inv_sqrt_cache[0]) {
426 cobalt_cache_init();
427 cobalt_rec_inv_sqrt_cache[0] = ~0;
428 }
429 }
431 /* CoDel control_law is t + interval/sqrt(count)
432 * We maintain in rec_inv_sqrt the reciprocal value of sqrt(count) to avoid
433 * both sqrt() and divide operation.
434 */
435 static ktime_t cobalt_control(ktime_t t,
436 u64 interval,
437 u32 rec_inv_sqrt)
438 {
439 return ktime_add_ns(t, reciprocal_scale(interval,
440 rec_inv_sqrt));
441 }
443 /* Call this when a packet had to be dropped due to queue overflow. Returns
444 * true if the BLUE state was quiescent before but active after this call.
445 */
446 static bool cobalt_queue_full(struct cobalt_vars *vars,
447 struct cobalt_params *p,
448 ktime_t now)
449 {
450 bool up = false;
452 if (ktime_to_ns(ktime_sub(now, vars->blue_timer)) > p->target) {
453 up = !vars->p_drop;
454 vars->p_drop += p->p_inc;
455 if (vars->p_drop < p->p_inc)
456 vars->p_drop = ~0;
457 vars->blue_timer = now;
458 }
459 vars->dropping = true;
460 vars->drop_next = now;
461 if (!vars->count)
462 vars->count = 1;
464 return up;
465 }
467 /* Call this when the queue was serviced but turned out to be empty. Returns
468 * true if the BLUE state was active before but quiescent after this call.
469 */
470 static bool cobalt_queue_empty(struct cobalt_vars *vars,
471 struct cobalt_params *p,
472 ktime_t now)
473 {
474 bool down = false;
476 if (vars->p_drop &&
477 ktime_to_ns(ktime_sub(now, vars->blue_timer)) > p->target) {
478 if (vars->p_drop < p->p_dec)
479 vars->p_drop = 0;
480 else
481 vars->p_drop -= p->p_dec;
482 vars->blue_timer = now;
483 down = !vars->p_drop;
484 }
485 vars->dropping = false;
487 if (vars->count && ktime_to_ns(ktime_sub(now, vars->drop_next)) >= 0) {
488 vars->count--;
489 cobalt_invsqrt(vars);
490 vars->drop_next = cobalt_control(vars->drop_next,
491 p->interval,
492 vars->rec_inv_sqrt);
493 }
495 return down;
496 }
498 /* Call this with a freshly dequeued packet for possible congestion marking.
499 * Returns true as an instruction to drop the packet, false for delivery.
500 */
501 static bool cobalt_should_drop(struct cobalt_vars *vars,
502 struct cobalt_params *p,
503 ktime_t now,
504 struct sk_buff *skb,
505 u32 bulk_flows)
506 {
507 bool next_due, over_target, drop = false;
508 ktime_t schedule;
509 u64 sojourn;
511 /* The 'schedule' variable records, in its sign, whether 'now' is before or
512 * after 'drop_next'. This allows 'drop_next' to be updated before the next
513 * scheduling decision is actually branched, without destroying that
514 * information. Similarly, the first 'schedule' value calculated is preserved
515 * in the boolean 'next_due'.
516 *
517 * As for 'drop_next', we take advantage of the fact that 'interval' is both
518 * the delay between first exceeding 'target' and the first signalling event,
519 * *and* the scaling factor for the signalling frequency. It's therefore very
520 * natural to use a single mechanism for both purposes, and eliminates a
521 * significant amount of reference Codel's spaghetti code. To help with this,
522 * both the '0' and '1' entries in the invsqrt cache are 0xFFFFFFFF, as close
523 * as possible to 1.0 in fixed-point.
524 */
526 sojourn = ktime_to_ns(ktime_sub(now, cobalt_get_enqueue_time(skb)));
527 schedule = ktime_sub(now, vars->drop_next);
528 over_target = sojourn > p->target &&
529 sojourn > p->mtu_time * bulk_flows * 2 &&
530 sojourn > p->mtu_time * 4;
531 next_due = vars->count && ktime_to_ns(schedule) >= 0;
533 vars->ecn_marked = false;
535 if (over_target) {
536 if (!vars->dropping) {
537 vars->dropping = true;
538 vars->drop_next = cobalt_control(now,
539 p->interval,
540 vars->rec_inv_sqrt);
541 }
542 if (!vars->count)
543 vars->count = 1;
544 } else if (vars->dropping) {
545 vars->dropping = false;
546 }
548 if (next_due && vars->dropping) {
549 /* Use ECN mark if possible, otherwise drop */
550 drop = !(vars->ecn_marked = INET_ECN_set_ce(skb));
552 vars->count++;
553 if (!vars->count)
554 vars->count--;
555 cobalt_invsqrt(vars);
556 vars->drop_next = cobalt_control(vars->drop_next,
557 p->interval,
558 vars->rec_inv_sqrt);
559 schedule = ktime_sub(now, vars->drop_next);
560 } else {
561 while (next_due) {
562 vars->count--;
563 cobalt_invsqrt(vars);
564 vars->drop_next = cobalt_control(vars->drop_next,
565 p->interval,
566 vars->rec_inv_sqrt);
567 schedule = ktime_sub(now, vars->drop_next);
568 next_due = vars->count && ktime_to_ns(schedule) >= 0;
569 }
570 }
572 /* Simple BLUE implementation. Lack of ECN is deliberate. */
573 if (vars->p_drop)
574 drop |= (prandom_u32() < vars->p_drop);
576 /* Overload the drop_next field as an activity timeout */
577 if (!vars->count)
578 vars->drop_next = ktime_add_ns(now, p->interval);
579 else if (ktime_to_ns(schedule) > 0 && !drop)
580 vars->drop_next = now;
582 return drop;
583 }
585 static void cake_update_flowkeys(struct flow_keys *keys,
586 const struct sk_buff *skb)
587 {
588 #if IS_ENABLED(CONFIG_NF_CONNTRACK)
589 struct nf_conntrack_tuple tuple = {};
590 bool rev = !skb->_nfct;
592 if (tc_skb_protocol(skb) != htons(ETH_P_IP))
593 return;
595 if (!nf_ct_get_tuple_skb(&tuple, skb))
596 return;
598 keys->addrs.v4addrs.src = rev ? tuple.dst.u3.ip : tuple.src.u3.ip;
599 keys->addrs.v4addrs.dst = rev ? tuple.src.u3.ip : tuple.dst.u3.ip;
601 if (keys->ports.ports) {
602 keys->ports.src = rev ? tuple.dst.u.all : tuple.src.u.all;
603 keys->ports.dst = rev ? tuple.src.u.all : tuple.dst.u.all;
604 }
605 #endif
606 }
608 /* Cake has several subtle multiple bit settings. In these cases you
609 * would be matching triple isolate mode as well.
610 */
612 static bool cake_dsrc(int flow_mode)
613 {
614 return (flow_mode & CAKE_FLOW_DUAL_SRC) == CAKE_FLOW_DUAL_SRC;
615 }
617 static bool cake_ddst(int flow_mode)
618 {
619 return (flow_mode & CAKE_FLOW_DUAL_DST) == CAKE_FLOW_DUAL_DST;
620 }
622 static u32 cake_hash(struct cake_tin_data *q, const struct sk_buff *skb,
623 int flow_mode, u16 flow_override, u16 host_override)
624 {
625 u32 flow_hash = 0, srchost_hash = 0, dsthost_hash = 0;
626 u16 reduced_hash, srchost_idx, dsthost_idx;
627 struct flow_keys keys, host_keys;
629 if (unlikely(flow_mode == CAKE_FLOW_NONE))
630 return 0;
632 /* If both overrides are set we can skip packet dissection entirely */
633 if ((flow_override || !(flow_mode & CAKE_FLOW_FLOWS)) &&
634 (host_override || !(flow_mode & CAKE_FLOW_HOSTS)))
635 goto skip_hash;
637 skb_flow_dissect_flow_keys(skb, &keys,
638 FLOW_DISSECTOR_F_STOP_AT_FLOW_LABEL);
640 if (flow_mode & CAKE_FLOW_NAT_FLAG)
641 cake_update_flowkeys(&keys, skb);
643 /* flow_hash_from_keys() sorts the addresses by value, so we have
644 * to preserve their order in a separate data structure to treat
645 * src and dst host addresses as independently selectable.
646 */
647 host_keys = keys;
648 host_keys.ports.ports = 0;
649 host_keys.basic.ip_proto = 0;
650 host_keys.keyid.keyid = 0;
651 host_keys.tags.flow_label = 0;
653 switch (host_keys.control.addr_type) {
654 case FLOW_DISSECTOR_KEY_IPV4_ADDRS:
655 host_keys.addrs.v4addrs.src = 0;
656 dsthost_hash = flow_hash_from_keys(&host_keys);
657 host_keys.addrs.v4addrs.src = keys.addrs.v4addrs.src;
658 host_keys.addrs.v4addrs.dst = 0;
659 srchost_hash = flow_hash_from_keys(&host_keys);
660 break;
662 case FLOW_DISSECTOR_KEY_IPV6_ADDRS:
663 memset(&host_keys.addrs.v6addrs.src, 0,
664 sizeof(host_keys.addrs.v6addrs.src));
665 dsthost_hash = flow_hash_from_keys(&host_keys);
666 host_keys.addrs.v6addrs.src = keys.addrs.v6addrs.src;
667 memset(&host_keys.addrs.v6addrs.dst, 0,
668 sizeof(host_keys.addrs.v6addrs.dst));
669 srchost_hash = flow_hash_from_keys(&host_keys);
670 break;
672 default:
673 dsthost_hash = 0;
674 srchost_hash = 0;
675 }
677 /* This *must* be after the above switch, since as a
678 * side-effect it sorts the src and dst addresses.
679 */
680 if (flow_mode & CAKE_FLOW_FLOWS)
681 flow_hash = flow_hash_from_keys(&keys);
683 skip_hash:
684 if (flow_override)
685 flow_hash = flow_override - 1;
686 if (host_override) {
687 dsthost_hash = host_override - 1;
688 srchost_hash = host_override - 1;
689 }
691 if (!(flow_mode & CAKE_FLOW_FLOWS)) {
692 if (flow_mode & CAKE_FLOW_SRC_IP)
693 flow_hash ^= srchost_hash;
695 if (flow_mode & CAKE_FLOW_DST_IP)
696 flow_hash ^= dsthost_hash;
697 }
699 reduced_hash = flow_hash % CAKE_QUEUES;
701 /* set-associative hashing */
702 /* fast path if no hash collision (direct lookup succeeds) */
703 if (likely(q->tags[reduced_hash] == flow_hash &&
704 q->flows[reduced_hash].set)) {
705 q->way_directs++;
706 } else {
707 u32 inner_hash = reduced_hash % CAKE_SET_WAYS;
708 u32 outer_hash = reduced_hash - inner_hash;
709 bool allocate_src = false;
710 bool allocate_dst = false;
711 u32 i, k;
713 /* check if any active queue in the set is reserved for
714 * this flow.
715 */
716 for (i = 0, k = inner_hash; i < CAKE_SET_WAYS;
717 i++, k = (k + 1) % CAKE_SET_WAYS) {
718 if (q->tags[outer_hash + k] == flow_hash) {
719 if (i)
720 q->way_hits++;
722 if (!q->flows[outer_hash + k].set) {
723 /* need to increment host refcnts */
724 allocate_src = cake_dsrc(flow_mode);
725 allocate_dst = cake_ddst(flow_mode);
726 }
728 goto found;
729 }
730 }
732 /* no queue is reserved for this flow, look for an
733 * empty one.
734 */
735 for (i = 0; i < CAKE_SET_WAYS;
736 i++, k = (k + 1) % CAKE_SET_WAYS) {
737 if (!q->flows[outer_hash + k].set) {
738 q->way_misses++;
739 allocate_src = cake_dsrc(flow_mode);
740 allocate_dst = cake_ddst(flow_mode);
741 goto found;
742 }
743 }
745 /* With no empty queues, default to the original
746 * queue, accept the collision, update the host tags.
747 */
748 q->way_collisions++;
749 q->hosts[q->flows[reduced_hash].srchost].srchost_refcnt--;
750 q->hosts[q->flows[reduced_hash].dsthost].dsthost_refcnt--;
751 allocate_src = cake_dsrc(flow_mode);
752 allocate_dst = cake_ddst(flow_mode);
753 found:
754 /* reserve queue for future packets in same flow */
755 reduced_hash = outer_hash + k;
756 q->tags[reduced_hash] = flow_hash;
758 if (allocate_src) {
759 srchost_idx = srchost_hash % CAKE_QUEUES;
760 inner_hash = srchost_idx % CAKE_SET_WAYS;
761 outer_hash = srchost_idx - inner_hash;
762 for (i = 0, k = inner_hash; i < CAKE_SET_WAYS;
763 i++, k = (k + 1) % CAKE_SET_WAYS) {
764 if (q->hosts[outer_hash + k].srchost_tag ==
765 srchost_hash)
766 goto found_src;
767 }
768 for (i = 0; i < CAKE_SET_WAYS;
769 i++, k = (k + 1) % CAKE_SET_WAYS) {
770 if (!q->hosts[outer_hash + k].srchost_refcnt)
771 break;
772 }
773 q->hosts[outer_hash + k].srchost_tag = srchost_hash;
774 found_src:
775 srchost_idx = outer_hash + k;
776 q->hosts[srchost_idx].srchost_refcnt++;
777 q->flows[reduced_hash].srchost = srchost_idx;
778 }
780 if (allocate_dst) {
781 dsthost_idx = dsthost_hash % CAKE_QUEUES;
782 inner_hash = dsthost_idx % CAKE_SET_WAYS;
783 outer_hash = dsthost_idx - inner_hash;
784 for (i = 0, k = inner_hash; i < CAKE_SET_WAYS;
785 i++, k = (k + 1) % CAKE_SET_WAYS) {
786 if (q->hosts[outer_hash + k].dsthost_tag ==
787 dsthost_hash)
788 goto found_dst;
789 }
790 for (i = 0; i < CAKE_SET_WAYS;
791 i++, k = (k + 1) % CAKE_SET_WAYS) {
792 if (!q->hosts[outer_hash + k].dsthost_refcnt)
793 break;
794 }
795 q->hosts[outer_hash + k].dsthost_tag = dsthost_hash;
796 found_dst:
797 dsthost_idx = outer_hash + k;
798 q->hosts[dsthost_idx].dsthost_refcnt++;
799 q->flows[reduced_hash].dsthost = dsthost_idx;
800 }
801 }
803 return reduced_hash;
804 }
806 /* helper functions : might be changed when/if skb use a standard list_head */
807 /* remove one skb from head of slot queue */
809 static struct sk_buff *dequeue_head(struct cake_flow *flow)
810 {
811 struct sk_buff *skb = flow->head;
813 if (skb) {
814 flow->head = skb->next;
815 skb->next = NULL;
816 }
818 return skb;
819 }
821 /* add skb to flow queue (tail add) */
823 static void flow_queue_add(struct cake_flow *flow, struct sk_buff *skb)
824 {
825 if (!flow->head)
826 flow->head = skb;
827 else
828 flow->tail->next = skb;
829 flow->tail = skb;
830 skb->next = NULL;
831 }
833 static struct iphdr *cake_get_iphdr(const struct sk_buff *skb,
834 struct ipv6hdr *buf)
835 {
836 unsigned int offset = skb_network_offset(skb);
837 struct iphdr *iph;
839 iph = skb_header_pointer(skb, offset, sizeof(struct iphdr), buf);
841 if (!iph)
842 return NULL;
844 if (iph->version == 4 && iph->protocol == IPPROTO_IPV6)
845 return skb_header_pointer(skb, offset + iph->ihl * 4,
846 sizeof(struct ipv6hdr), buf);
848 else if (iph->version == 4)
849 return iph;
851 else if (iph->version == 6)
852 return skb_header_pointer(skb, offset, sizeof(struct ipv6hdr),
853 buf);
855 return NULL;
856 }
858 static struct tcphdr *cake_get_tcphdr(const struct sk_buff *skb,
859 void *buf, unsigned int bufsize)
860 {
861 unsigned int offset = skb_network_offset(skb);
862 const struct ipv6hdr *ipv6h;
863 const struct tcphdr *tcph;
864 const struct iphdr *iph;
865 struct ipv6hdr _ipv6h;
866 struct tcphdr _tcph;
868 ipv6h = skb_header_pointer(skb, offset, sizeof(_ipv6h), &_ipv6h);
870 if (!ipv6h)
871 return NULL;
873 if (ipv6h->version == 4) {
874 iph = (struct iphdr *)ipv6h;
875 offset += iph->ihl * 4;
877 /* special-case 6in4 tunnelling, as that is a common way to get
878 * v6 connectivity in the home
879 */
880 if (iph->protocol == IPPROTO_IPV6) {
881 ipv6h = skb_header_pointer(skb, offset,
882 sizeof(_ipv6h), &_ipv6h);
884 if (!ipv6h || ipv6h->nexthdr != IPPROTO_TCP)
885 return NULL;
887 offset += sizeof(struct ipv6hdr);
889 } else if (iph->protocol != IPPROTO_TCP) {
890 return NULL;
891 }
893 } else if (ipv6h->version == 6) {
894 if (ipv6h->nexthdr != IPPROTO_TCP)
895 return NULL;
897 offset += sizeof(struct ipv6hdr);
898 } else {
899 return NULL;
900 }
902 tcph = skb_header_pointer(skb, offset, sizeof(_tcph), &_tcph);
903 if (!tcph)
904 return NULL;
906 return skb_header_pointer(skb, offset,
907 min(__tcp_hdrlen(tcph), bufsize), buf);
908 }
910 static const void *cake_get_tcpopt(const struct tcphdr *tcph,
911 int code, int *oplen)
912 {
913 /* inspired by tcp_parse_options in tcp_input.c */
914 int length = __tcp_hdrlen(tcph) - sizeof(struct tcphdr);
915 const u8 *ptr = (const u8 *)(tcph + 1);
917 while (length > 0) {
918 int opcode = *ptr++;
919 int opsize;
921 if (opcode == TCPOPT_EOL)
922 break;
923 if (opcode == TCPOPT_NOP) {
924 length--;
925 continue;
926 }
927 opsize = *ptr++;
928 if (opsize < 2 || opsize > length)
929 break;
931 if (opcode == code) {
932 *oplen = opsize;
933 return ptr;
934 }
936 ptr += opsize - 2;
937 length -= opsize;
938 }
940 return NULL;
941 }
943 /* Compare two SACK sequences. A sequence is considered greater if it SACKs more
944 * bytes than the other. In the case where both sequences ACKs bytes that the
945 * other doesn't, A is considered greater. DSACKs in A also makes A be
946 * considered greater.
947 *
948 * @return -1, 0 or 1 as normal compare functions
949 */
950 static int cake_tcph_sack_compare(const struct tcphdr *tcph_a,
951 const struct tcphdr *tcph_b)
952 {
953 const struct tcp_sack_block_wire *sack_a, *sack_b;
954 u32 ack_seq_a = ntohl(tcph_a->ack_seq);
955 u32 bytes_a = 0, bytes_b = 0;
956 int oplen_a, oplen_b;
957 bool first = true;
959 sack_a = cake_get_tcpopt(tcph_a, TCPOPT_SACK, &oplen_a);
960 sack_b = cake_get_tcpopt(tcph_b, TCPOPT_SACK, &oplen_b);
962 /* pointers point to option contents */
963 oplen_a -= TCPOLEN_SACK_BASE;
964 oplen_b -= TCPOLEN_SACK_BASE;
966 if (sack_a && oplen_a >= sizeof(*sack_a) &&
967 (!sack_b || oplen_b < sizeof(*sack_b)))
968 return -1;
969 else if (sack_b && oplen_b >= sizeof(*sack_b) &&
970 (!sack_a || oplen_a < sizeof(*sack_a)))
971 return 1;
972 else if ((!sack_a || oplen_a < sizeof(*sack_a)) &&
973 (!sack_b || oplen_b < sizeof(*sack_b)))
974 return 0;
976 while (oplen_a >= sizeof(*sack_a)) {
977 const struct tcp_sack_block_wire *sack_tmp = sack_b;
978 u32 start_a = get_unaligned_be32(&sack_a->start_seq);
979 u32 end_a = get_unaligned_be32(&sack_a->end_seq);
980 int oplen_tmp = oplen_b;
981 bool found = false;
983 /* DSACK; always considered greater to prevent dropping */
984 if (before(start_a, ack_seq_a))
985 return -1;
987 bytes_a += end_a - start_a;
989 while (oplen_tmp >= sizeof(*sack_tmp)) {
990 u32 start_b = get_unaligned_be32(&sack_tmp->start_seq);
991 u32 end_b = get_unaligned_be32(&sack_tmp->end_seq);
993 /* first time through we count the total size */
994 if (first)
995 bytes_b += end_b - start_b;
997 if (!after(start_b, start_a) && !before(end_b, end_a)) {
998 found = true;
999 if (!first)
1000 break;
1001 }
1002 oplen_tmp -= sizeof(*sack_tmp);
1003 sack_tmp++;
1004 }
1006 if (!found)
1007 return -1;
1009 oplen_a -= sizeof(*sack_a);
1010 sack_a++;
1011 first = false;
1012 }
1014 /* If we made it this far, all ranges SACKed by A are covered by B, so
1015 * either the SACKs are equal, or B SACKs more bytes.
1016 */
1017 return bytes_b > bytes_a ? 1 : 0;
1018 }
1020 static void cake_tcph_get_tstamp(const struct tcphdr *tcph,
1021 u32 *tsval, u32 *tsecr)
1022 {
1023 const u8 *ptr;
1024 int opsize;
1026 ptr = cake_get_tcpopt(tcph, TCPOPT_TIMESTAMP, &opsize);
1028 if (ptr && opsize == TCPOLEN_TIMESTAMP) {
1029 *tsval = get_unaligned_be32(ptr);
1030 *tsecr = get_unaligned_be32(ptr + 4);
1031 }
1032 }
1034 static bool cake_tcph_may_drop(const struct tcphdr *tcph,
1035 u32 tstamp_new, u32 tsecr_new)
1036 {
1037 /* inspired by tcp_parse_options in tcp_input.c */
1038 int length = __tcp_hdrlen(tcph) - sizeof(struct tcphdr);
1039 const u8 *ptr = (const u8 *)(tcph + 1);
1040 u32 tstamp, tsecr;
1042 /* 3 reserved flags must be unset to avoid future breakage
1043 * ACK must be set
1044 * ECE/CWR are handled separately
1045 * All other flags URG/PSH/RST/SYN/FIN must be unset
1046 * 0x0FFF0000 = all TCP flags (confirm ACK=1, others zero)
1047 * 0x00C00000 = CWR/ECE (handled separately)
1048 * 0x0F3F0000 = 0x0FFF0000 & ~0x00C00000
1049 */
1050 if (((tcp_flag_word(tcph) &
1051 cpu_to_be32(0x0F3F0000)) != TCP_FLAG_ACK))
1052 return false;
1054 while (length > 0) {
1055 int opcode = *ptr++;
1056 int opsize;
1058 if (opcode == TCPOPT_EOL)
1059 break;
1060 if (opcode == TCPOPT_NOP) {
1061 length--;
1062 continue;
1063 }
1064 opsize = *ptr++;
1065 if (opsize < 2 || opsize > length)
1066 break;
1068 switch (opcode) {
1069 case TCPOPT_MD5SIG: /* doesn't influence state */
1070 break;
1072 case TCPOPT_SACK: /* stricter checking performed later */
1073 if (opsize % 8 != 2)
1074 return false;
1075 break;
1077 case TCPOPT_TIMESTAMP:
1078 /* only drop timestamps lower than new */
1079 if (opsize != TCPOLEN_TIMESTAMP)
1080 return false;
1081 tstamp = get_unaligned_be32(ptr);
1082 tsecr = get_unaligned_be32(ptr + 4);
1083 if (after(tstamp, tstamp_new) ||
1084 after(tsecr, tsecr_new))
1085 return false;
1086 break;
1088 case TCPOPT_MSS: /* these should only be set on SYN */
1089 case TCPOPT_WINDOW:
1090 case TCPOPT_SACK_PERM:
1091 case TCPOPT_FASTOPEN:
1092 case TCPOPT_EXP:
1093 default: /* don't drop if any unknown options are present */
1094 return false;
1095 }
1097 ptr += opsize - 2;
1098 length -= opsize;
1099 }
1101 return true;
1102 }
1104 static struct sk_buff *cake_ack_filter(struct cake_sched_data *q,
1105 struct cake_flow *flow)
1106 {
1107 bool aggressive = q->ack_filter == CAKE_ACK_AGGRESSIVE;
1108 struct sk_buff *elig_ack = NULL, *elig_ack_prev = NULL;
1109 struct sk_buff *skb_check, *skb_prev = NULL;
1110 const struct ipv6hdr *ipv6h, *ipv6h_check;
1111 unsigned char _tcph[64], _tcph_check[64];
1112 const struct tcphdr *tcph, *tcph_check;
1113 const struct iphdr *iph, *iph_check;
1114 struct ipv6hdr _iph, _iph_check;
1115 const struct sk_buff *skb;
1116 int seglen, num_found = 0;
1117 u32 tstamp = 0, tsecr = 0;
1118 __be32 elig_flags = 0;
1119 int sack_comp;
1121 /* no other possible ACKs to filter */
1122 if (flow->head == flow->tail)
1123 return NULL;
1125 skb = flow->tail;
1126 tcph = cake_get_tcphdr(skb, _tcph, sizeof(_tcph));
1127 iph = cake_get_iphdr(skb, &_iph);
1128 if (!tcph)
1129 return NULL;
1131 cake_tcph_get_tstamp(tcph, &tstamp, &tsecr);
1133 /* the 'triggering' packet need only have the ACK flag set.
1134 * also check that SYN is not set, as there won't be any previous ACKs.
1135 */
1136 if ((tcp_flag_word(tcph) &
1137 (TCP_FLAG_ACK | TCP_FLAG_SYN)) != TCP_FLAG_ACK)
1138 return NULL;
1140 /* the 'triggering' ACK is at the tail of the queue, we have already
1141 * returned if it is the only packet in the flow. loop through the rest
1142 * of the queue looking for pure ACKs with the same 5-tuple as the
1143 * triggering one.
1144 */
1145 for (skb_check = flow->head;
1146 skb_check && skb_check != skb;
1147 skb_prev = skb_check, skb_check = skb_check->next) {
1148 iph_check = cake_get_iphdr(skb_check, &_iph_check);
1149 tcph_check = cake_get_tcphdr(skb_check, &_tcph_check,
1150 sizeof(_tcph_check));
1152 /* only TCP packets with matching 5-tuple are eligible, and only
1153 * drop safe headers
1154 */
1155 if (!tcph_check || iph->version != iph_check->version ||
1156 tcph_check->source != tcph->source ||
1157 tcph_check->dest != tcph->dest)
1158 continue;
1160 if (iph_check->version == 4) {
1161 if (iph_check->saddr != iph->saddr ||
1162 iph_check->daddr != iph->daddr)
1163 continue;
1165 seglen = ntohs(iph_check->tot_len) -
1166 (4 * iph_check->ihl);
1167 } else if (iph_check->version == 6) {
1168 ipv6h = (struct ipv6hdr *)iph;
1169 ipv6h_check = (struct ipv6hdr *)iph_check;
1171 if (ipv6_addr_cmp(&ipv6h_check->saddr, &ipv6h->saddr) ||
1172 ipv6_addr_cmp(&ipv6h_check->daddr, &ipv6h->daddr))
1173 continue;
1175 seglen = ntohs(ipv6h_check->payload_len);
1176 } else {
1177 WARN_ON(1); /* shouldn't happen */
1178 continue;
1179 }
1181 /* If the ECE/CWR flags changed from the previous eligible
1182 * packet in the same flow, we should no longer be dropping that
1183 * previous packet as this would lose information.
1184 */
1185 if (elig_ack && (tcp_flag_word(tcph_check) &
1186 (TCP_FLAG_ECE | TCP_FLAG_CWR)) != elig_flags) {
1187 elig_ack = NULL;
1188 elig_ack_prev = NULL;
1189 num_found--;
1190 }
1192 /* Check TCP options and flags, don't drop ACKs with segment
1193 * data, and don't drop ACKs with a higher cumulative ACK
1194 * counter than the triggering packet. Check ACK seqno here to
1195 * avoid parsing SACK options of packets we are going to exclude
1196 * anyway.
1197 */
1198 if (!cake_tcph_may_drop(tcph_check, tstamp, tsecr) ||
1199 (seglen - __tcp_hdrlen(tcph_check)) != 0 ||
1200 after(ntohl(tcph_check->ack_seq), ntohl(tcph->ack_seq)))
1201 continue;
1203 /* Check SACK options. The triggering packet must SACK more data
1204 * than the ACK under consideration, or SACK the same range but
1205 * have a larger cumulative ACK counter. The latter is a
1206 * pathological case, but is contained in the following check
1207 * anyway, just to be safe.
1208 */
1209 sack_comp = cake_tcph_sack_compare(tcph_check, tcph);
1211 if (sack_comp < 0 ||
1212 (ntohl(tcph_check->ack_seq) == ntohl(tcph->ack_seq) &&
1213 sack_comp == 0))
1214 continue;
1216 /* At this point we have found an eligible pure ACK to drop; if
1217 * we are in aggressive mode, we are done. Otherwise, keep
1218 * searching unless this is the second eligible ACK we
1219 * found.
1220 *
1221 * Since we want to drop ACK closest to the head of the queue,
1222 * save the first eligible ACK we find, even if we need to loop
1223 * again.
1224 */
1225 if (!elig_ack) {
1226 elig_ack = skb_check;
1227 elig_ack_prev = skb_prev;
1228 elig_flags = (tcp_flag_word(tcph_check)
1229 & (TCP_FLAG_ECE | TCP_FLAG_CWR));
1230 }
1232 if (num_found++ > 0)
1233 goto found;
1234 }
1236 /* We made it through the queue without finding two eligible ACKs . If
1237 * we found a single eligible ACK we can drop it in aggressive mode if
1238 * we can guarantee that this does not interfere with ECN flag
1239 * information. We ensure this by dropping it only if the enqueued
1240 * packet is consecutive with the eligible ACK, and their flags match.
1241 */
1242 if (elig_ack && aggressive && elig_ack->next == skb &&
1243 (elig_flags == (tcp_flag_word(tcph) &
1244 (TCP_FLAG_ECE | TCP_FLAG_CWR))))
1245 goto found;
1247 return NULL;
1249 found:
1250 if (elig_ack_prev)
1251 elig_ack_prev->next = elig_ack->next;
1252 else
1253 flow->head = elig_ack->next;
1255 elig_ack->next = NULL;
1257 return elig_ack;
1258 }
1260 static u64 cake_ewma(u64 avg, u64 sample, u32 shift)
1261 {
1262 avg -= avg >> shift;
1263 avg += sample >> shift;
1264 return avg;
1265 }
1267 static u32 cake_calc_overhead(struct cake_sched_data *q, u32 len, u32 off)
1268 {
1269 if (q->rate_flags & CAKE_FLAG_OVERHEAD)
1270 len -= off;
1272 if (q->max_netlen < len)
1273 q->max_netlen = len;
1274 if (q->min_netlen > len)
1275 q->min_netlen = len;
1277 len += q->rate_overhead;
1279 if (len < q->rate_mpu)
1280 len = q->rate_mpu;
1282 if (q->atm_mode == CAKE_ATM_ATM) {
1283 len += 47;
1284 len /= 48;
1285 len *= 53;
1286 } else if (q->atm_mode == CAKE_ATM_PTM) {
1287 /* Add one byte per 64 bytes or part thereof.
1288 * This is conservative and easier to calculate than the
1289 * precise value.
1290 */
1291 len += (len + 63) / 64;
1292 }
1294 if (q->max_adjlen < len)
1295 q->max_adjlen = len;
1296 if (q->min_adjlen > len)
1297 q->min_adjlen = len;
1299 return len;
1300 }
1302 static u32 cake_overhead(struct cake_sched_data *q, const struct sk_buff *skb)
1303 {
1304 const struct skb_shared_info *shinfo = skb_shinfo(skb);
1305 unsigned int hdr_len, last_len = 0;
1306 u32 off = skb_network_offset(skb);
1307 u32 len = qdisc_pkt_len(skb);
1308 u16 segs = 1;
1310 q->avg_netoff = cake_ewma(q->avg_netoff, off << 16, 8);
1312 if (!shinfo->gso_size)
1313 return cake_calc_overhead(q, len, off);
1315 /* borrowed from qdisc_pkt_len_init() */
1316 hdr_len = skb_transport_header(skb) - skb_mac_header(skb);
1318 /* + transport layer */
1319 if (likely(shinfo->gso_type & (SKB_GSO_TCPV4 |
1320 SKB_GSO_TCPV6))) {
1321 const struct tcphdr *th;
1322 struct tcphdr _tcphdr;
1324 th = skb_header_pointer(skb, skb_transport_offset(skb),
1325 sizeof(_tcphdr), &_tcphdr);
1326 if (likely(th))
1327 hdr_len += __tcp_hdrlen(th);
1328 } else {
1329 struct udphdr _udphdr;
1331 if (skb_header_pointer(skb, skb_transport_offset(skb),
1332 sizeof(_udphdr), &_udphdr))
1333 hdr_len += sizeof(struct udphdr);
1334 }
1336 if (unlikely(shinfo->gso_type & SKB_GSO_DODGY))
1337 segs = DIV_ROUND_UP(skb->len - hdr_len,
1338 shinfo->gso_size);
1339 else
1340 segs = shinfo->gso_segs;
1342 len = shinfo->gso_size + hdr_len;
1343 last_len = skb->len - shinfo->gso_size * (segs - 1);
1345 return (cake_calc_overhead(q, len, off) * (segs - 1) +
1346 cake_calc_overhead(q, last_len, off));
1347 }
1349 static void cake_heap_swap(struct cake_sched_data *q, u16 i, u16 j)
1350 {
1351 struct cake_heap_entry ii = q->overflow_heap[i];
1352 struct cake_heap_entry jj = q->overflow_heap[j];
1354 q->overflow_heap[i] = jj;
1355 q->overflow_heap[j] = ii;
1357 q->tins[ii.t].overflow_idx[ii.b] = j;
1358 q->tins[jj.t].overflow_idx[jj.b] = i;
1359 }
1361 static u32 cake_heap_get_backlog(const struct cake_sched_data *q, u16 i)
1362 {
1363 struct cake_heap_entry ii = q->overflow_heap[i];
1365 return q->tins[ii.t].backlogs[ii.b];
1366 }
1368 static void cake_heapify(struct cake_sched_data *q, u16 i)
1369 {
1370 static const u32 a = CAKE_MAX_TINS * CAKE_QUEUES;
1371 u32 mb = cake_heap_get_backlog(q, i);
1372 u32 m = i;
1374 while (m < a) {
1375 u32 l = m + m + 1;
1376 u32 r = l + 1;
1378 if (l < a) {
1379 u32 lb = cake_heap_get_backlog(q, l);
1381 if (lb > mb) {
1382 m = l;
1383 mb = lb;
1384 }
1385 }
1387 if (r < a) {
1388 u32 rb = cake_heap_get_backlog(q, r);
1390 if (rb > mb) {
1391 m = r;
1392 mb = rb;
1393 }
1394 }
1396 if (m != i) {
1397 cake_heap_swap(q, i, m);
1398 i = m;
1399 } else {
1400 break;
1401 }
1402 }
1403 }
1405 static void cake_heapify_up(struct cake_sched_data *q, u16 i)
1406 {
1407 while (i > 0 && i < CAKE_MAX_TINS * CAKE_QUEUES) {
1408 u16 p = (i - 1) >> 1;
1409 u32 ib = cake_heap_get_backlog(q, i);
1410 u32 pb = cake_heap_get_backlog(q, p);
1412 if (ib > pb) {
1413 cake_heap_swap(q, i, p);
1414 i = p;
1415 } else {
1416 break;
1417 }
1418 }
1419 }
1421 static int cake_advance_shaper(struct cake_sched_data *q,
1422 struct cake_tin_data *b,
1423 struct sk_buff *skb,
1424 ktime_t now, bool drop)
1425 {
1426 u32 len = get_cobalt_cb(skb)->adjusted_len;
1428 /* charge packet bandwidth to this tin
1429 * and to the global shaper.
1430 */
1431 if (q->rate_ns) {
1432 u64 tin_dur = (len * b->tin_rate_ns) >> b->tin_rate_shft;
1433 u64 global_dur = (len * q->rate_ns) >> q->rate_shft;
1434 u64 failsafe_dur = global_dur + (global_dur >> 1);
1436 if (ktime_before(b->time_next_packet, now))
1437 b->time_next_packet = ktime_add_ns(b->time_next_packet,
1438 tin_dur);
1440 else if (ktime_before(b->time_next_packet,
1441 ktime_add_ns(now, tin_dur)))
1442 b->time_next_packet = ktime_add_ns(now, tin_dur);
1444 q->time_next_packet = ktime_add_ns(q->time_next_packet,
1445 global_dur);
1446 if (!drop)
1447 q->failsafe_next_packet = \
1448 ktime_add_ns(q->failsafe_next_packet,
1449 failsafe_dur);
1450 }
1451 return len;
1452 }
1454 static unsigned int cake_drop(struct Qdisc *sch, struct sk_buff **to_free)
1455 {
1456 struct cake_sched_data *q = qdisc_priv(sch);
1457 ktime_t now = ktime_get();
1458 u32 idx = 0, tin = 0, len;
1459 struct cake_heap_entry qq;
1460 struct cake_tin_data *b;
1461 struct cake_flow *flow;
1462 struct sk_buff *skb;
1464 if (!q->overflow_timeout) {
1465 int i;
1466 /* Build fresh max-heap */
1467 for (i = CAKE_MAX_TINS * CAKE_QUEUES / 2; i >= 0; i--)
1468 cake_heapify(q, i);
1469 }
1470 q->overflow_timeout = 65535;
1472 /* select longest queue for pruning */
1473 qq = q->overflow_heap[0];
1474 tin = qq.t;
1475 idx = qq.b;
1477 b = &q->tins[tin];
1478 flow = &b->flows[idx];
1479 skb = dequeue_head(flow);
1480 if (unlikely(!skb)) {
1481 /* heap has gone wrong, rebuild it next time */
1482 q->overflow_timeout = 0;
1483 return idx + (tin << 16);
1484 }
1486 if (cobalt_queue_full(&flow->cvars, &b->cparams, now))
1487 b->unresponsive_flow_count++;
1489 len = qdisc_pkt_len(skb);
1490 q->buffer_used -= skb->truesize;
1491 b->backlogs[idx] -= len;
1492 b->tin_backlog -= len;
1493 sch->qstats.backlog -= len;
1494 qdisc_tree_reduce_backlog(sch, 1, len);
1496 flow->dropped++;
1497 b->tin_dropped++;
1498 sch->qstats.drops++;
1500 if (q->rate_flags & CAKE_FLAG_INGRESS)
1501 cake_advance_shaper(q, b, skb, now, true);
1503 __qdisc_drop(skb, to_free);
1504 sch->q.qlen--;
1506 cake_heapify(q, 0);
1508 return idx + (tin << 16);
1509 }
1511 static void cake_wash_diffserv(struct sk_buff *skb)
1512 {
1513 switch (skb->protocol) {
1514 case htons(ETH_P_IP):
1515 ipv4_change_dsfield(ip_hdr(skb), INET_ECN_MASK, 0);
1516 break;
1517 case htons(ETH_P_IPV6):
1518 ipv6_change_dsfield(ipv6_hdr(skb), INET_ECN_MASK, 0);
1519 break;
1520 default:
1521 break;
1522 }
1523 }
1525 static u8 cake_handle_diffserv(struct sk_buff *skb, u16 wash)
1526 {
1527 u8 dscp;
1529 switch (skb->protocol) {
1530 case htons(ETH_P_IP):
1531 dscp = ipv4_get_dsfield(ip_hdr(skb)) >> 2;
1532 if (wash && dscp)
1533 ipv4_change_dsfield(ip_hdr(skb), INET_ECN_MASK, 0);
1534 return dscp;
1536 case htons(ETH_P_IPV6):
1537 dscp = ipv6_get_dsfield(ipv6_hdr(skb)) >> 2;
1538 if (wash && dscp)
1539 ipv6_change_dsfield(ipv6_hdr(skb), INET_ECN_MASK, 0);
1540 return dscp;
1542 case htons(ETH_P_ARP):
1543 return 0x38; /* CS7 - Net Control */
1545 default:
1546 /* If there is no Diffserv field, treat as best-effort */
1547 return 0;
1548 }
1549 }
1551 static struct cake_tin_data *cake_select_tin(struct Qdisc *sch,
1552 struct sk_buff *skb)
1553 {
1554 struct cake_sched_data *q = qdisc_priv(sch);
1555 u32 tin;
1557 if (TC_H_MAJ(skb->priority) == sch->handle &&
1558 TC_H_MIN(skb->priority) > 0 &&
1559 TC_H_MIN(skb->priority) <= q->tin_cnt) {
1560 tin = q->tin_order[TC_H_MIN(skb->priority) - 1];
1562 if (q->rate_flags & CAKE_FLAG_WASH)
1563 cake_wash_diffserv(skb);
1564 } else if (q->tin_mode != CAKE_DIFFSERV_BESTEFFORT) {
1565 /* extract the Diffserv Precedence field, if it exists */
1566 /* and clear DSCP bits if washing */
1567 tin = q->tin_index[cake_handle_diffserv(skb,
1568 q->rate_flags & CAKE_FLAG_WASH)];
1569 if (unlikely(tin >= q->tin_cnt))
1570 tin = 0;
1571 } else {
1572 tin = 0;
1573 if (q->rate_flags & CAKE_FLAG_WASH)
1574 cake_wash_diffserv(skb);
1575 }
1577 return &q->tins[tin];
1578 }
1580 static u32 cake_classify(struct Qdisc *sch, struct cake_tin_data **t,
1581 struct sk_buff *skb, int flow_mode, int *qerr)
1582 {
1583 struct cake_sched_data *q = qdisc_priv(sch);
1584 struct tcf_proto *filter;
1585 struct tcf_result res;
1586 u16 flow = 0, host = 0;
1587 int result;
1589 filter = rcu_dereference_bh(q->filter_list);
1590 if (!filter)
1591 goto hash;
1593 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
1594 result = tcf_classify(skb, filter, &res, false);
1596 if (result >= 0) {
1597 #ifdef CONFIG_NET_CLS_ACT
1598 switch (result) {
1599 case TC_ACT_STOLEN:
1600 case TC_ACT_QUEUED:
1601 case TC_ACT_TRAP:
1602 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
1603 /* fall through */
1604 case TC_ACT_SHOT:
1605 return 0;
1606 }
1607 #endif
1608 if (TC_H_MIN(res.classid) <= CAKE_QUEUES)
1609 flow = TC_H_MIN(res.classid);
1610 if (TC_H_MAJ(res.classid) <= (CAKE_QUEUES << 16))
1611 host = TC_H_MAJ(res.classid) >> 16;
1612 }
1613 hash:
1614 *t = cake_select_tin(sch, skb);
1615 return cake_hash(*t, skb, flow_mode, flow, host) + 1;
1616 }
1618 static void cake_reconfigure(struct Qdisc *sch);
1620 static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch,
1621 struct sk_buff **to_free)
1622 {
1623 struct cake_sched_data *q = qdisc_priv(sch);
1624 int len = qdisc_pkt_len(skb);
1625 int uninitialized_var(ret);
1626 struct sk_buff *ack = NULL;
1627 ktime_t now = ktime_get();
1628 struct cake_tin_data *b;
1629 struct cake_flow *flow;
1630 u32 idx;
1632 /* choose flow to insert into */
1633 idx = cake_classify(sch, &b, skb, q->flow_mode, &ret);
1634 if (idx == 0) {
1635 if (ret & __NET_XMIT_BYPASS)
1636 qdisc_qstats_drop(sch);
1637 __qdisc_drop(skb, to_free);
1638 return ret;
1639 }
1640 idx--;
1641 flow = &b->flows[idx];
1643 /* ensure shaper state isn't stale */
1644 if (!b->tin_backlog) {
1645 if (ktime_before(b->time_next_packet, now))
1646 b->time_next_packet = now;
1648 if (!sch->q.qlen) {
1649 if (ktime_before(q->time_next_packet, now)) {
1650 q->failsafe_next_packet = now;
1651 q->time_next_packet = now;
1652 } else if (ktime_after(q->time_next_packet, now) &&
1653 ktime_after(q->failsafe_next_packet, now)) {
1654 u64 next = \
1655 min(ktime_to_ns(q->time_next_packet),
1656 ktime_to_ns(
1657 q->failsafe_next_packet));
1658 sch->qstats.overlimits++;
1659 qdisc_watchdog_schedule_ns(&q->watchdog, next);
1660 }
1661 }
1662 }
1664 if (unlikely(len > b->max_skblen))
1665 b->max_skblen = len;
1667 if (skb_is_gso(skb) && q->rate_flags & CAKE_FLAG_SPLIT_GSO) {
1668 struct sk_buff *segs, *nskb;
1669 netdev_features_t features = netif_skb_features(skb);
1670 unsigned int slen = 0;
1672 segs = skb_gso_segment(skb, features & ~NETIF_F_GSO_MASK);
1673 if (IS_ERR_OR_NULL(segs))
1674 return qdisc_drop(skb, sch, to_free);
1676 while (segs) {
1677 nskb = segs->next;
1678 segs->next = NULL;
1679 qdisc_skb_cb(segs)->pkt_len = segs->len;
1680 cobalt_set_enqueue_time(segs, now);
1681 get_cobalt_cb(segs)->adjusted_len = cake_overhead(q,
1682 segs);
1683 flow_queue_add(flow, segs);
1685 sch->q.qlen++;
1686 slen += segs->len;
1687 q->buffer_used += segs->truesize;
1688 b->packets++;
1689 segs = nskb;
1690 }
1692 /* stats */
1693 b->bytes += slen;
1694 b->backlogs[idx] += slen;
1695 b->tin_backlog += slen;
1696 sch->qstats.backlog += slen;
1697 q->avg_window_bytes += slen;
1699 qdisc_tree_reduce_backlog(sch, 1, len);
1700 consume_skb(skb);
1701 } else {
1702 /* not splitting */
1703 cobalt_set_enqueue_time(skb, now);
1704 get_cobalt_cb(skb)->adjusted_len = cake_overhead(q, skb);
1705 flow_queue_add(flow, skb);
1707 if (q->ack_filter)
1708 ack = cake_ack_filter(q, flow);
1710 if (ack) {
1711 b->ack_drops++;
1712 sch->qstats.drops++;
1713 b->bytes += qdisc_pkt_len(ack);
1714 len -= qdisc_pkt_len(ack);
1715 q->buffer_used += skb->truesize - ack->truesize;
1716 if (q->rate_flags & CAKE_FLAG_INGRESS)
1717 cake_advance_shaper(q, b, ack, now, true);
1719 qdisc_tree_reduce_backlog(sch, 1, qdisc_pkt_len(ack));
1720 consume_skb(ack);
1721 } else {
1722 sch->q.qlen++;
1723 q->buffer_used += skb->truesize;
1724 }
1726 /* stats */
1727 b->packets++;
1728 b->bytes += len;
1729 b->backlogs[idx] += len;
1730 b->tin_backlog += len;
1731 sch->qstats.backlog += len;
1732 q->avg_window_bytes += len;
1733 }
1735 if (q->overflow_timeout)
1736 cake_heapify_up(q, b->overflow_idx[idx]);
1738 /* incoming bandwidth capacity estimate */
1739 if (q->rate_flags & CAKE_FLAG_AUTORATE_INGRESS) {
1740 u64 packet_interval = \
1741 ktime_to_ns(ktime_sub(now, q->last_packet_time));
1743 if (packet_interval > NSEC_PER_SEC)
1744 packet_interval = NSEC_PER_SEC;
1746 /* filter out short-term bursts, eg. wifi aggregation */
1747 q->avg_packet_interval = \
1748 cake_ewma(q->avg_packet_interval,
1749 packet_interval,
1750 (packet_interval > q->avg_packet_interval ?
1751 2 : 8));
1753 q->last_packet_time = now;
1755 if (packet_interval > q->avg_packet_interval) {
1756 u64 window_interval = \
1757 ktime_to_ns(ktime_sub(now,
1758 q->avg_window_begin));
1759 u64 b = q->avg_window_bytes * (u64)NSEC_PER_SEC;
1761 do_div(b, window_interval);
1762 q->avg_peak_bandwidth =
1763 cake_ewma(q->avg_peak_bandwidth, b,
1764 b > q->avg_peak_bandwidth ? 2 : 8);
1765 q->avg_window_bytes = 0;
1766 q->avg_window_begin = now;
1768 if (ktime_after(now,
1769 ktime_add_ms(q->last_reconfig_time,
1770 250))) {
1771 q->rate_bps = (q->avg_peak_bandwidth * 15) >> 4;
1772 cake_reconfigure(sch);
1773 }
1774 }
1775 } else {
1776 q->avg_window_bytes = 0;
1777 q->last_packet_time = now;
1778 }
1780 /* flowchain */
1781 if (!flow->set || flow->set == CAKE_SET_DECAYING) {
1782 struct cake_host *srchost = &b->hosts[flow->srchost];
1783 struct cake_host *dsthost = &b->hosts[flow->dsthost];
1784 u16 host_load = 1;
1786 if (!flow->set) {
1787 list_add_tail(&flow->flowchain, &b->new_flows);
1788 } else {
1789 b->decaying_flow_count--;
1790 list_move_tail(&flow->flowchain, &b->new_flows);
1791 }
1792 flow->set = CAKE_SET_SPARSE;
1793 b->sparse_flow_count++;
1795 if (cake_dsrc(q->flow_mode))
1796 host_load = max(host_load, srchost->srchost_refcnt);
1798 if (cake_ddst(q->flow_mode))
1799 host_load = max(host_load, dsthost->dsthost_refcnt);
1801 flow->deficit = (b->flow_quantum *
1802 quantum_div[host_load]) >> 16;
1803 } else if (flow->set == CAKE_SET_SPARSE_WAIT) {
1804 /* this flow was empty, accounted as a sparse flow, but actually
1805 * in the bulk rotation.
1806 */
1807 flow->set = CAKE_SET_BULK;
1808 b->sparse_flow_count--;
1809 b->bulk_flow_count++;
1810 }
1812 if (q->buffer_used > q->buffer_max_used)
1813 q->buffer_max_used = q->buffer_used;
1815 if (q->buffer_used > q->buffer_limit) {
1816 u32 dropped = 0;
1818 while (q->buffer_used > q->buffer_limit) {
1819 dropped++;
1820 cake_drop(sch, to_free);
1821 }
1822 b->drop_overlimit += dropped;
1823 }
1824 return NET_XMIT_SUCCESS;
1825 }
1827 static struct sk_buff *cake_dequeue_one(struct Qdisc *sch)
1828 {
1829 struct cake_sched_data *q = qdisc_priv(sch);
1830 struct cake_tin_data *b = &q->tins[q->cur_tin];
1831 struct cake_flow *flow = &b->flows[q->cur_flow];
1832 struct sk_buff *skb = NULL;
1833 u32 len;
1835 if (flow->head) {
1836 skb = dequeue_head(flow);
1837 len = qdisc_pkt_len(skb);
1838 b->backlogs[q->cur_flow] -= len;
1839 b->tin_backlog -= len;
1840 sch->qstats.backlog -= len;
1841 q->buffer_used -= skb->truesize;
1842 sch->q.qlen--;
1844 if (q->overflow_timeout)
1845 cake_heapify(q, b->overflow_idx[q->cur_flow]);
1846 }
1847 return skb;
1848 }
1850 /* Discard leftover packets from a tin no longer in use. */
1851 static void cake_clear_tin(struct Qdisc *sch, u16 tin)
1852 {
1853 struct cake_sched_data *q = qdisc_priv(sch);
1854 struct sk_buff *skb;
1856 q->cur_tin = tin;
1857 for (q->cur_flow = 0; q->cur_flow < CAKE_QUEUES; q->cur_flow++)
1858 while (!!(skb = cake_dequeue_one(sch)))
1859 kfree_skb(skb);
1860 }
1862 static struct sk_buff *cake_dequeue(struct Qdisc *sch)
1863 {
1864 struct cake_sched_data *q = qdisc_priv(sch);
1865 struct cake_tin_data *b = &q->tins[q->cur_tin];
1866 struct cake_host *srchost, *dsthost;
1867 ktime_t now = ktime_get();
1868 struct cake_flow *flow;
1869 struct list_head *head;
1870 bool first_flow = true;
1871 struct sk_buff *skb;
1872 u16 host_load;
1873 u64 delay;
1874 u32 len;
1876 begin:
1877 if (!sch->q.qlen)
1878 return NULL;
1880 /* global hard shaper */
1881 if (ktime_after(q->time_next_packet, now) &&
1882 ktime_after(q->failsafe_next_packet, now)) {
1883 u64 next = min(ktime_to_ns(q->time_next_packet),
1884 ktime_to_ns(q->failsafe_next_packet));
1886 sch->qstats.overlimits++;
1887 qdisc_watchdog_schedule_ns(&q->watchdog, next);
1888 return NULL;
1889 }
1891 /* Choose a class to work on. */
1892 if (!q->rate_ns) {
1893 /* In unlimited mode, can't rely on shaper timings, just balance
1894 * with DRR
1895 */
1896 bool wrapped = false, empty = true;
1898 while (b->tin_deficit < 0 ||
1899 !(b->sparse_flow_count + b->bulk_flow_count)) {
1900 if (b->tin_deficit <= 0)
1901 b->tin_deficit += b->tin_quantum_band;
1902 if (b->sparse_flow_count + b->bulk_flow_count)
1903 empty = false;
1905 q->cur_tin++;
1906 b++;
1907 if (q->cur_tin >= q->tin_cnt) {
1908 q->cur_tin = 0;
1909 b = q->tins;
1911 if (wrapped) {
1912 /* It's possible for q->qlen to be
1913 * nonzero when we actually have no
1914 * packets anywhere.
1915 */
1916 if (empty)
1917 return NULL;
1918 } else {
1919 wrapped = true;
1920 }
1921 }
1922 }
1923 } else {
1924 /* In shaped mode, choose:
1925 * - Highest-priority tin with queue and meeting schedule, or
1926 * - The earliest-scheduled tin with queue.
1927 */
1928 ktime_t best_time = KTIME_MAX;
1929 int tin, best_tin = 0;
1931 for (tin = 0; tin < q->tin_cnt; tin++) {
1932 b = q->tins + tin;
1933 if ((b->sparse_flow_count + b->bulk_flow_count) > 0) {
1934 ktime_t time_to_pkt = \
1935 ktime_sub(b->time_next_packet, now);
1937 if (ktime_to_ns(time_to_pkt) <= 0 ||
1938 ktime_compare(time_to_pkt,
1939 best_time) <= 0) {
1940 best_time = time_to_pkt;
1941 best_tin = tin;
1942 }
1943 }
1944 }
1946 q->cur_tin = best_tin;
1947 b = q->tins + best_tin;
1949 /* No point in going further if no packets to deliver. */
1950 if (unlikely(!(b->sparse_flow_count + b->bulk_flow_count)))
1951 return NULL;
1952 }
1954 retry:
1955 /* service this class */
1956 head = &b->decaying_flows;
1957 if (!first_flow || list_empty(head)) {
1958 head = &b->new_flows;
1959 if (list_empty(head)) {
1960 head = &b->old_flows;
1961 if (unlikely(list_empty(head))) {
1962 head = &b->decaying_flows;
1963 if (unlikely(list_empty(head)))
1964 goto begin;
1965 }
1966 }
1967 }
1968 flow = list_first_entry(head, struct cake_flow, flowchain);
1969 q->cur_flow = flow - b->flows;
1970 first_flow = false;
1972 /* triple isolation (modified DRR++) */
1973 srchost = &b->hosts[flow->srchost];
1974 dsthost = &b->hosts[flow->dsthost];
1975 host_load = 1;
1977 if (cake_dsrc(q->flow_mode))
1978 host_load = max(host_load, srchost->srchost_refcnt);
1980 if (cake_ddst(q->flow_mode))
1981 host_load = max(host_load, dsthost->dsthost_refcnt);
1983 WARN_ON(host_load > CAKE_QUEUES);
1985 /* flow isolation (DRR++) */
1986 if (flow->deficit <= 0) {
1987 /* The shifted prandom_u32() is a way to apply dithering to
1988 * avoid accumulating roundoff errors
1989 */
1990 flow->deficit += (b->flow_quantum * quantum_div[host_load] +
1991 (prandom_u32() >> 16)) >> 16;
1992 list_move_tail(&flow->flowchain, &b->old_flows);
1994 /* Keep all flows with deficits out of the sparse and decaying
1995 * rotations. No non-empty flow can go into the decaying
1996 * rotation, so they can't get deficits
1997 */
1998 if (flow->set == CAKE_SET_SPARSE) {
1999 if (flow->head) {
2000 b->sparse_flow_count--;
2001 b->bulk_flow_count++;
2002 flow->set = CAKE_SET_BULK;
2003 } else {
2004 /* we've moved it to the bulk rotation for
2005 * correct deficit accounting but we still want
2006 * to count it as a sparse flow, not a bulk one.
2007 */
2008 flow->set = CAKE_SET_SPARSE_WAIT;
2009 }
2010 }
2011 goto retry;
2012 }
2014 /* Retrieve a packet via the AQM */
2015 while (1) {
2016 skb = cake_dequeue_one(sch);
2017 if (!skb) {
2018 /* this queue was actually empty */
2019 if (cobalt_queue_empty(&flow->cvars, &b->cparams, now))
2020 b->unresponsive_flow_count--;
2022 if (flow->cvars.p_drop || flow->cvars.count ||
2023 ktime_before(now, flow->cvars.drop_next)) {
2024 /* keep in the flowchain until the state has
2025 * decayed to rest
2026 */
2027 list_move_tail(&flow->flowchain,
2028 &b->decaying_flows);
2029 if (flow->set == CAKE_SET_BULK) {
2030 b->bulk_flow_count--;
2031 b->decaying_flow_count++;
2032 } else if (flow->set == CAKE_SET_SPARSE ||
2033 flow->set == CAKE_SET_SPARSE_WAIT) {
2034 b->sparse_flow_count--;
2035 b->decaying_flow_count++;
2036 }
2037 flow->set = CAKE_SET_DECAYING;
2038 } else {
2039 /* remove empty queue from the flowchain */
2040 list_del_init(&flow->flowchain);
2041 if (flow->set == CAKE_SET_SPARSE ||
2042 flow->set == CAKE_SET_SPARSE_WAIT)
2043 b->sparse_flow_count--;
2044 else if (flow->set == CAKE_SET_BULK)
2045 b->bulk_flow_count--;
2046 else
2047 b->decaying_flow_count--;
2049 flow->set = CAKE_SET_NONE;
2050 srchost->srchost_refcnt--;
2051 dsthost->dsthost_refcnt--;
2052 }
2053 goto begin;
2054 }
2056 /* Last packet in queue may be marked, shouldn't be dropped */
2057 if (!cobalt_should_drop(&flow->cvars, &b->cparams, now, skb,
2058 (b->bulk_flow_count *
2059 !!(q->rate_flags &
2060 CAKE_FLAG_INGRESS))) ||
2061 !flow->head)
2062 break;
2064 /* drop this packet, get another one */
2065 if (q->rate_flags & CAKE_FLAG_INGRESS) {
2066 len = cake_advance_shaper(q, b, skb,
2067 now, true);
2068 flow->deficit -= len;
2069 b->tin_deficit -= len;
2070 }
2071 flow->dropped++;
2072 b->tin_dropped++;
2073 qdisc_tree_reduce_backlog(sch, 1, qdisc_pkt_len(skb));
2074 qdisc_qstats_drop(sch);
2075 kfree_skb(skb);
2076 if (q->rate_flags & CAKE_FLAG_INGRESS)
2077 goto retry;
2078 }
2080 b->tin_ecn_mark += !!flow->cvars.ecn_marked;
2081 qdisc_bstats_update(sch, skb);
2083 /* collect delay stats */
2084 delay = ktime_to_ns(ktime_sub(now, cobalt_get_enqueue_time(skb)));
2085 b->avge_delay = cake_ewma(b->avge_delay, delay, 8);
2086 b->peak_delay = cake_ewma(b->peak_delay, delay,
2087 delay > b->peak_delay ? 2 : 8);
2088 b->base_delay = cake_ewma(b->base_delay, delay,
2089 delay < b->base_delay ? 2 : 8);
2091 len = cake_advance_shaper(q, b, skb, now, false);
2092 flow->deficit -= len;
2093 b->tin_deficit -= len;
2095 if (ktime_after(q->time_next_packet, now) && sch->q.qlen) {
2096 u64 next = min(ktime_to_ns(q->time_next_packet),
2097 ktime_to_ns(q->failsafe_next_packet));
2099 qdisc_watchdog_schedule_ns(&q->watchdog, next);
2100 } else if (!sch->q.qlen) {
2101 int i;
2103 for (i = 0; i < q->tin_cnt; i++) {
2104 if (q->tins[i].decaying_flow_count) {
2105 ktime_t next = \
2106 ktime_add_ns(now,
2107 q->tins[i].cparams.target);
2109 qdisc_watchdog_schedule_ns(&q->watchdog,
2110 ktime_to_ns(next));
2111 break;
2112 }
2113 }
2114 }
2116 if (q->overflow_timeout)
2117 q->overflow_timeout--;
2119 return skb;
2120 }
2122 static void cake_reset(struct Qdisc *sch)
2123 {
2124 u32 c;
2126 for (c = 0; c < CAKE_MAX_TINS; c++)
2127 cake_clear_tin(sch, c);
2128 }
2130 static const struct nla_policy cake_policy[TCA_CAKE_MAX + 1] = {
2131 [TCA_CAKE_BASE_RATE64] = { .type = NLA_U64 },
2132 [TCA_CAKE_DIFFSERV_MODE] = { .type = NLA_U32 },
2133 [TCA_CAKE_ATM] = { .type = NLA_U32 },
2134 [TCA_CAKE_FLOW_MODE] = { .type = NLA_U32 },
2135 [TCA_CAKE_OVERHEAD] = { .type = NLA_S32 },
2136 [TCA_CAKE_RTT] = { .type = NLA_U32 },
2137 [TCA_CAKE_TARGET] = { .type = NLA_U32 },
2138 [TCA_CAKE_AUTORATE] = { .type = NLA_U32 },
2139 [TCA_CAKE_MEMORY] = { .type = NLA_U32 },
2140 [TCA_CAKE_NAT] = { .type = NLA_U32 },
2141 [TCA_CAKE_RAW] = { .type = NLA_U32 },
2142 [TCA_CAKE_WASH] = { .type = NLA_U32 },
2143 [TCA_CAKE_MPU] = { .type = NLA_U32 },
2144 [TCA_CAKE_INGRESS] = { .type = NLA_U32 },
2145 [TCA_CAKE_ACK_FILTER] = { .type = NLA_U32 },
2146 };
2148 static void cake_set_rate(struct cake_tin_data *b, u64 rate, u32 mtu,
2149 u64 target_ns, u64 rtt_est_ns)
2150 {
2151 /* convert byte-rate into time-per-byte
2152 * so it will always unwedge in reasonable time.
2153 */
2154 static const u64 MIN_RATE = 64;
2155 u32 byte_target = mtu;
2156 u64 byte_target_ns;
2157 u8 rate_shft = 0;
2158 u64 rate_ns = 0;
2160 b->flow_quantum = 1514;
2161 if (rate) {
2162 b->flow_quantum = max(min(rate >> 12, 1514ULL), 300ULL);
2163 rate_shft = 34;
2164 rate_ns = ((u64)NSEC_PER_SEC) << rate_shft;
2165 rate_ns = div64_u64(rate_ns, max(MIN_RATE, rate));
2166 while (!!(rate_ns >> 34)) {
2167 rate_ns >>= 1;
2168 rate_shft--;
2169 }
2170 } /* else unlimited, ie. zero delay */
2172 b->tin_rate_bps = rate;
2173 b->tin_rate_ns = rate_ns;
2174 b->tin_rate_shft = rate_shft;
2176 byte_target_ns = (byte_target * rate_ns) >> rate_shft;
2178 b->cparams.target = max((byte_target_ns * 3) / 2, target_ns);
2179 b->cparams.interval = max(rtt_est_ns +
2180 b->cparams.target - target_ns,
2181 b->cparams.target * 2);
2182 b->cparams.mtu_time = byte_target_ns;
2183 b->cparams.p_inc = 1 << 24; /* 1/256 */
2184 b->cparams.p_dec = 1 << 20; /* 1/4096 */
2185 }
2187 static int cake_config_besteffort(struct Qdisc *sch)
2188 {
2189 struct cake_sched_data *q = qdisc_priv(sch);
2190 struct cake_tin_data *b = &q->tins[0];
2191 u32 mtu = psched_mtu(qdisc_dev(sch));
2192 u64 rate = q->rate_bps;
2194 q->tin_cnt = 1;
2196 q->tin_index = besteffort;
2197 q->tin_order = normal_order;
2199 cake_set_rate(b, rate, mtu,
2200 us_to_ns(q->target), us_to_ns(q->interval));
2201 b->tin_quantum_band = 65535;
2202 b->tin_quantum_prio = 65535;
2204 return 0;
2205 }
2207 static int cake_config_precedence(struct Qdisc *sch)
2208 {
2209 /* convert high-level (user visible) parameters into internal format */
2210 struct cake_sched_data *q = qdisc_priv(sch);
2211 u32 mtu = psched_mtu(qdisc_dev(sch));
2212 u64 rate = q->rate_bps;
2213 u32 quantum1 = 256;
2214 u32 quantum2 = 256;
2215 u32 i;
2217 q->tin_cnt = 8;
2218 q->tin_index = precedence;
2219 q->tin_order = normal_order;
2221 for (i = 0; i < q->tin_cnt; i++) {
2222 struct cake_tin_data *b = &q->tins[i];
2224 cake_set_rate(b, rate, mtu, us_to_ns(q->target),
2225 us_to_ns(q->interval));
2227 b->tin_quantum_prio = max_t(u16, 1U, quantum1);
2228 b->tin_quantum_band = max_t(u16, 1U, quantum2);
2230 /* calculate next class's parameters */
2231 rate *= 7;
2232 rate >>= 3;
2234 quantum1 *= 3;
2235 quantum1 >>= 1;
2237 quantum2 *= 7;
2238 quantum2 >>= 3;
2239 }
2241 return 0;
2242 }
2244 /* List of known Diffserv codepoints:
2245 *
2246 * Least Effort (CS1)
2247 * Best Effort (CS0)
2248 * Max Reliability & LLT "Lo" (TOS1)
2249 * Max Throughput (TOS2)
2250 * Min Delay (TOS4)
2251 * LLT "La" (TOS5)
2252 * Assured Forwarding 1 (AF1x) - x3
2253 * Assured Forwarding 2 (AF2x) - x3
2254 * Assured Forwarding 3 (AF3x) - x3
2255 * Assured Forwarding 4 (AF4x) - x3
2256 * Precedence Class 2 (CS2)
2257 * Precedence Class 3 (CS3)
2258 * Precedence Class 4 (CS4)
2259 * Precedence Class 5 (CS5)
2260 * Precedence Class 6 (CS6)
2261 * Precedence Class 7 (CS7)
2262 * Voice Admit (VA)
2263 * Expedited Forwarding (EF)
2265 * Total 25 codepoints.
2266 */
2268 /* List of traffic classes in RFC 4594:
2269 * (roughly descending order of contended priority)
2270 * (roughly ascending order of uncontended throughput)
2271 *
2272 * Network Control (CS6,CS7) - routing traffic
2273 * Telephony (EF,VA) - aka. VoIP streams
2274 * Signalling (CS5) - VoIP setup
2275 * Multimedia Conferencing (AF4x) - aka. video calls
2276 * Realtime Interactive (CS4) - eg. games
2277 * Multimedia Streaming (AF3x) - eg. YouTube, NetFlix, Twitch
2278 * Broadcast Video (CS3)
2279 * Low Latency Data (AF2x,TOS4) - eg. database
2280 * Ops, Admin, Management (CS2,TOS1) - eg. ssh
2281 * Standard Service (CS0 & unrecognised codepoints)
2282 * High Throughput Data (AF1x,TOS2) - eg. web traffic
2283 * Low Priority Data (CS1) - eg. BitTorrent
2285 * Total 12 traffic classes.
2286 */
2288 static int cake_config_diffserv8(struct Qdisc *sch)
2289 {
2290 /* Pruned list of traffic classes for typical applications:
2291 *
2292 * Network Control (CS6, CS7)
2293 * Minimum Latency (EF, VA, CS5, CS4)
2294 * Interactive Shell (CS2, TOS1)
2295 * Low Latency Transactions (AF2x, TOS4)
2296 * Video Streaming (AF4x, AF3x, CS3)
2297 * Bog Standard (CS0 etc.)
2298 * High Throughput (AF1x, TOS2)
2299 * Background Traffic (CS1)
2300 *
2301 * Total 8 traffic classes.
2302 */
2304 struct cake_sched_data *q = qdisc_priv(sch);
2305 u32 mtu = psched_mtu(qdisc_dev(sch));
2306 u64 rate = q->rate_bps;
2307 u32 quantum1 = 256;
2308 u32 quantum2 = 256;
2309 u32 i;
2311 q->tin_cnt = 8;
2313 /* codepoint to class mapping */
2314 q->tin_index = diffserv8;
2315 q->tin_order = normal_order;
2317 /* class characteristics */
2318 for (i = 0; i < q->tin_cnt; i++) {
2319 struct cake_tin_data *b = &q->tins[i];
2321 cake_set_rate(b, rate, mtu, us_to_ns(q->target),
2322 us_to_ns(q->interval));
2324 b->tin_quantum_prio = max_t(u16, 1U, quantum1);
2325 b->tin_quantum_band = max_t(u16, 1U, quantum2);
2327 /* calculate next class's parameters */
2328 rate *= 7;
2329 rate >>= 3;
2331 quantum1 *= 3;
2332 quantum1 >>= 1;
2334 quantum2 *= 7;
2335 quantum2 >>= 3;
2336 }
2338 return 0;
2339 }
2341 static int cake_config_diffserv4(struct Qdisc *sch)
2342 {
2343 /* Further pruned list of traffic classes for four-class system:
2344 *
2345 * Latency Sensitive (CS7, CS6, EF, VA, CS5, CS4)
2346 * Streaming Media (AF4x, AF3x, CS3, AF2x, TOS4, CS2, TOS1)
2347 * Best Effort (CS0, AF1x, TOS2, and those not specified)
2348 * Background Traffic (CS1)
2349 *
2350 * Total 4 traffic classes.
2351 */
2353 struct cake_sched_data *q = qdisc_priv(sch);
2354 u32 mtu = psched_mtu(qdisc_dev(sch));
2355 u64 rate = q->rate_bps;
2356 u32 quantum = 1024;
2358 q->tin_cnt = 4;
2360 /* codepoint to class mapping */
2361 q->tin_index = diffserv4;
2362 q->tin_order = bulk_order;
2364 /* class characteristics */
2365 cake_set_rate(&q->tins[0], rate, mtu,
2366 us_to_ns(q->target), us_to_ns(q->interval));
2367 cake_set_rate(&q->tins[1], rate >> 4, mtu,
2368 us_to_ns(q->target), us_to_ns(q->interval));
2369 cake_set_rate(&q->tins[2], rate >> 1, mtu,
2370 us_to_ns(q->target), us_to_ns(q->interval));
2371 cake_set_rate(&q->tins[3], rate >> 2, mtu,
2372 us_to_ns(q->target), us_to_ns(q->interval));
2374 /* priority weights */
2375 q->tins[0].tin_quantum_prio = quantum;
2376 q->tins[1].tin_quantum_prio = quantum >> 4;
2377 q->tins[2].tin_quantum_prio = quantum << 2;
2378 q->tins[3].tin_quantum_prio = quantum << 4;
2380 /* bandwidth-sharing weights */
2381 q->tins[0].tin_quantum_band = quantum;
2382 q->tins[1].tin_quantum_band = quantum >> 4;
2383 q->tins[2].tin_quantum_band = quantum >> 1;
2384 q->tins[3].tin_quantum_band = quantum >> 2;
2386 return 0;
2387 }
2389 static int cake_config_diffserv3(struct Qdisc *sch)
2390 {
2391 /* Simplified Diffserv structure with 3 tins.
2392 * Low Priority (CS1)
2393 * Best Effort
2394 * Latency Sensitive (TOS4, VA, EF, CS6, CS7)
2395 */
2396 struct cake_sched_data *q = qdisc_priv(sch);
2397 u32 mtu = psched_mtu(qdisc_dev(sch));
2398 u64 rate = q->rate_bps;
2399 u32 quantum = 1024;
2401 q->tin_cnt = 3;
2403 /* codepoint to class mapping */
2404 q->tin_index = diffserv3;
2405 q->tin_order = bulk_order;
2407 /* class characteristics */
2408 cake_set_rate(&q->tins[0], rate, mtu,
2409 us_to_ns(q->target), us_to_ns(q->interval));
2410 cake_set_rate(&q->tins[1], rate >> 4, mtu,
2411 us_to_ns(q->target), us_to_ns(q->interval));
2412 cake_set_rate(&q->tins[2], rate >> 2, mtu,
2413 us_to_ns(q->target), us_to_ns(q->interval));
2415 /* priority weights */
2416 q->tins[0].tin_quantum_prio = quantum;
2417 q->tins[1].tin_quantum_prio = quantum >> 4;
2418 q->tins[2].tin_quantum_prio = quantum << 4;
2420 /* bandwidth-sharing weights */
2421 q->tins[0].tin_quantum_band = quantum;
2422 q->tins[1].tin_quantum_band = quantum >> 4;
2423 q->tins[2].tin_quantum_band = quantum >> 2;
2425 return 0;
2426 }
2428 static void cake_reconfigure(struct Qdisc *sch)
2429 {
2430 struct cake_sched_data *q = qdisc_priv(sch);
2431 int c, ft;
2433 switch (q->tin_mode) {
2434 case CAKE_DIFFSERV_BESTEFFORT:
2435 ft = cake_config_besteffort(sch);
2436 break;
2438 case CAKE_DIFFSERV_PRECEDENCE:
2439 ft = cake_config_precedence(sch);
2440 break;
2442 case CAKE_DIFFSERV_DIFFSERV8:
2443 ft = cake_config_diffserv8(sch);
2444 break;
2446 case CAKE_DIFFSERV_DIFFSERV4:
2447 ft = cake_config_diffserv4(sch);
2448 break;
2450 case CAKE_DIFFSERV_DIFFSERV3:
2451 default:
2452 ft = cake_config_diffserv3(sch);
2453 break;
2454 }
2456 for (c = q->tin_cnt; c < CAKE_MAX_TINS; c++) {
2457 cake_clear_tin(sch, c);
2458 q->tins[c].cparams.mtu_time = q->tins[ft].cparams.mtu_time;
2459 }
2461 q->rate_ns = q->tins[ft].tin_rate_ns;
2462 q->rate_shft = q->tins[ft].tin_rate_shft;
2464 if (q->buffer_config_limit) {
2465 q->buffer_limit = q->buffer_config_limit;
2466 } else if (q->rate_bps) {
2467 u64 t = q->rate_bps * q->interval;
2469 do_div(t, USEC_PER_SEC / 4);
2470 q->buffer_limit = max_t(u32, t, 4U << 20);
2471 } else {
2472 q->buffer_limit = ~0;
2473 }
2475 sch->flags &= ~TCQ_F_CAN_BYPASS;
2477 q->buffer_limit = min(q->buffer_limit,
2478 max(sch->limit * psched_mtu(qdisc_dev(sch)),
2479 q->buffer_config_limit));
2480 }
2482 static int cake_change(struct Qdisc *sch, struct nlattr *opt,
2483 struct netlink_ext_ack *extack)
2484 {
2485 struct cake_sched_data *q = qdisc_priv(sch);
2486 struct nlattr *tb[TCA_CAKE_MAX + 1];
2487 int err;
2489 if (!opt)
2490 return -EINVAL;
2492 err = nla_parse_nested(tb, TCA_CAKE_MAX, opt, cake_policy, extack);
2493 if (err < 0)
2494 return err;
2496 if (tb[TCA_CAKE_NAT]) {
2497 #if IS_ENABLED(CONFIG_NF_CONNTRACK)
2498 q->flow_mode &= ~CAKE_FLOW_NAT_FLAG;
2499 q->flow_mode |= CAKE_FLOW_NAT_FLAG *
2500 !!nla_get_u32(tb[TCA_CAKE_NAT]);
2501 #else
2502 NL_SET_ERR_MSG_ATTR(extack, tb[TCA_CAKE_NAT],
2503 "No conntrack support in kernel");
2504 return -EOPNOTSUPP;
2505 #endif
2506 }
2508 if (tb[TCA_CAKE_BASE_RATE64])
2509 q->rate_bps = nla_get_u64(tb[TCA_CAKE_BASE_RATE64]);
2511 if (tb[TCA_CAKE_DIFFSERV_MODE])
2512 q->tin_mode = nla_get_u32(tb[TCA_CAKE_DIFFSERV_MODE]);
2514 if (tb[TCA_CAKE_WASH]) {
2515 if (!!nla_get_u32(tb[TCA_CAKE_WASH]))
2516 q->rate_flags |= CAKE_FLAG_WASH;
2517 else
2518 q->rate_flags &= ~CAKE_FLAG_WASH;
2519 }
2521 if (tb[TCA_CAKE_FLOW_MODE])
2522 q->flow_mode = ((q->flow_mode & CAKE_FLOW_NAT_FLAG) |
2523 (nla_get_u32(tb[TCA_CAKE_FLOW_MODE]) &
2524 CAKE_FLOW_MASK));
2526 if (tb[TCA_CAKE_ATM])
2527 q->atm_mode = nla_get_u32(tb[TCA_CAKE_ATM]);
2529 if (tb[TCA_CAKE_OVERHEAD]) {
2530 q->rate_overhead = nla_get_s32(tb[TCA_CAKE_OVERHEAD]);
2531 q->rate_flags |= CAKE_FLAG_OVERHEAD;
2533 q->max_netlen = 0;
2534 q->max_adjlen = 0;
2535 q->min_netlen = ~0;
2536 q->min_adjlen = ~0;
2537 }
2539 if (tb[TCA_CAKE_RAW]) {
2540 q->rate_flags &= ~CAKE_FLAG_OVERHEAD;
2542 q->max_netlen = 0;
2543 q->max_adjlen = 0;
2544 q->min_netlen = ~0;
2545 q->min_adjlen = ~0;
2546 }
2548 if (tb[TCA_CAKE_MPU])
2549 q->rate_mpu = nla_get_u32(tb[TCA_CAKE_MPU]);
2551 if (tb[TCA_CAKE_RTT]) {
2552 q->interval = nla_get_u32(tb[TCA_CAKE_RTT]);
2554 if (!q->interval)
2555 q->interval = 1;
2556 }
2558 if (tb[TCA_CAKE_TARGET]) {
2559 q->target = nla_get_u32(tb[TCA_CAKE_TARGET]);
2561 if (!q->target)
2562 q->target = 1;
2563 }
2565 if (tb[TCA_CAKE_AUTORATE]) {
2566 if (!!nla_get_u32(tb[TCA_CAKE_AUTORATE]))
2567 q->rate_flags |= CAKE_FLAG_AUTORATE_INGRESS;
2568 else
2569 q->rate_flags &= ~CAKE_FLAG_AUTORATE_INGRESS;
2570 }
2572 if (tb[TCA_CAKE_INGRESS]) {
2573 if (!!nla_get_u32(tb[TCA_CAKE_INGRESS]))
2574 q->rate_flags |= CAKE_FLAG_INGRESS;
2575 else
2576 q->rate_flags &= ~CAKE_FLAG_INGRESS;
2577 }
2579 if (tb[TCA_CAKE_ACK_FILTER])
2580 q->ack_filter = nla_get_u32(tb[TCA_CAKE_ACK_FILTER]);
2582 if (tb[TCA_CAKE_MEMORY])
2583 q->buffer_config_limit = nla_get_u32(tb[TCA_CAKE_MEMORY]);
2585 if (tb[TCA_CAKE_SPLIT_GSO]) {
2586 if (!!nla_get_u32(tb[TCA_CAKE_SPLIT_GSO]))
2587 q->rate_flags |= CAKE_FLAG_SPLIT_GSO;
2588 else
2589 q->rate_flags &= ~CAKE_FLAG_SPLIT_GSO;
2590 }
2592 if (q->tins) {
2593 sch_tree_lock(sch);
2594 cake_reconfigure(sch);
2595 sch_tree_unlock(sch);
2596 }
2598 return 0;
2599 }
2601 static void cake_destroy(struct Qdisc *sch)
2602 {
2603 struct cake_sched_data *q = qdisc_priv(sch);
2605 qdisc_watchdog_cancel(&q->watchdog);
2606 tcf_block_put(q->block);
2607 kvfree(q->tins);
2608 }
2610 static int cake_init(struct Qdisc *sch, struct nlattr *opt,
2611 struct netlink_ext_ack *extack)
2612 {
2613 struct cake_sched_data *q = qdisc_priv(sch);
2614 int i, j, err;
2616 sch->limit = 10240;
2617 q->tin_mode = CAKE_DIFFSERV_DIFFSERV3;
2618 q->flow_mode = CAKE_FLOW_TRIPLE;
2620 q->rate_bps = 0; /* unlimited by default */
2622 q->interval = 100000; /* 100ms default */
2623 q->target = 5000; /* 5ms: codel RFC argues
2624 * for 5 to 10% of interval
2625 */
2626 q->rate_flags |= CAKE_FLAG_SPLIT_GSO;
2627 q->cur_tin = 0;
2628 q->cur_flow = 0;
2630 qdisc_watchdog_init(&q->watchdog, sch);
2632 if (opt) {
2633 int err = cake_change(sch, opt, extack);
2635 if (err)
2636 return err;
2637 }
2639 err = tcf_block_get(&q->block, &q->filter_list, sch, extack);
2640 if (err)
2641 return err;
2643 quantum_div[0] = ~0;
2644 for (i = 1; i <= CAKE_QUEUES; i++)
2645 quantum_div[i] = 65535 / i;
2647 q->tins = kvcalloc(CAKE_MAX_TINS, sizeof(struct cake_tin_data),
2648 GFP_KERNEL);
2649 if (!q->tins)
2650 goto nomem;
2652 for (i = 0; i < CAKE_MAX_TINS; i++) {
2653 struct cake_tin_data *b = q->tins + i;
2655 INIT_LIST_HEAD(&b->new_flows);
2656 INIT_LIST_HEAD(&b->old_flows);
2657 INIT_LIST_HEAD(&b->decaying_flows);
2658 b->sparse_flow_count = 0;
2659 b->bulk_flow_count = 0;
2660 b->decaying_flow_count = 0;
2662 for (j = 0; j < CAKE_QUEUES; j++) {
2663 struct cake_flow *flow = b->flows + j;
2664 u32 k = j * CAKE_MAX_TINS + i;
2666 INIT_LIST_HEAD(&flow->flowchain);
2667 cobalt_vars_init(&flow->cvars);
2669 q->overflow_heap[k].t = i;
2670 q->overflow_heap[k].b = j;
2671 b->overflow_idx[j] = k;
2672 }
2673 }
2675 cake_reconfigure(sch);
2676 q->avg_peak_bandwidth = q->rate_bps;
2677 q->min_netlen = ~0;
2678 q->min_adjlen = ~0;
2679 return 0;
2681 nomem:
2682 cake_destroy(sch);
2683 return -ENOMEM;
2684 }
2686 static int cake_dump(struct Qdisc *sch, struct sk_buff *skb)
2687 {
2688 struct cake_sched_data *q = qdisc_priv(sch);
2689 struct nlattr *opts;
2691 opts = nla_nest_start(skb, TCA_OPTIONS);
2692 if (!opts)
2693 goto nla_put_failure;
2695 if (nla_put_u64_64bit(skb, TCA_CAKE_BASE_RATE64, q->rate_bps,
2696 TCA_CAKE_PAD))
2697 goto nla_put_failure;
2699 if (nla_put_u32(skb, TCA_CAKE_FLOW_MODE,
2700 q->flow_mode & CAKE_FLOW_MASK))
2701 goto nla_put_failure;
2703 if (nla_put_u32(skb, TCA_CAKE_RTT, q->interval))
2704 goto nla_put_failure;
2706 if (nla_put_u32(skb, TCA_CAKE_TARGET, q->target))
2707 goto nla_put_failure;
2709 if (nla_put_u32(skb, TCA_CAKE_MEMORY, q->buffer_config_limit))
2710 goto nla_put_failure;
2712 if (nla_put_u32(skb, TCA_CAKE_AUTORATE,
2713 !!(q->rate_flags & CAKE_FLAG_AUTORATE_INGRESS)))
2714 goto nla_put_failure;
2716 if (nla_put_u32(skb, TCA_CAKE_INGRESS,
2717 !!(q->rate_flags & CAKE_FLAG_INGRESS)))
2718 goto nla_put_failure;
2720 if (nla_put_u32(skb, TCA_CAKE_ACK_FILTER, q->ack_filter))
2721 goto nla_put_failure;
2723 if (nla_put_u32(skb, TCA_CAKE_NAT,
2724 !!(q->flow_mode & CAKE_FLOW_NAT_FLAG)))
2725 goto nla_put_failure;
2727 if (nla_put_u32(skb, TCA_CAKE_DIFFSERV_MODE, q->tin_mode))
2728 goto nla_put_failure;
2730 if (nla_put_u32(skb, TCA_CAKE_WASH,
2731 !!(q->rate_flags & CAKE_FLAG_WASH)))
2732 goto nla_put_failure;
2734 if (nla_put_u32(skb, TCA_CAKE_OVERHEAD, q->rate_overhead))
2735 goto nla_put_failure;
2737 if (!(q->rate_flags & CAKE_FLAG_OVERHEAD))
2738 if (nla_put_u32(skb, TCA_CAKE_RAW, 0))
2739 goto nla_put_failure;
2741 if (nla_put_u32(skb, TCA_CAKE_ATM, q->atm_mode))
2742 goto nla_put_failure;
2744 if (nla_put_u32(skb, TCA_CAKE_MPU, q->rate_mpu))
2745 goto nla_put_failure;
2747 if (nla_put_u32(skb, TCA_CAKE_SPLIT_GSO,
2748 !!(q->rate_flags & CAKE_FLAG_SPLIT_GSO)))
2749 goto nla_put_failure;
2751 return nla_nest_end(skb, opts);
2753 nla_put_failure:
2754 return -1;
2755 }
2757 static int cake_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
2758 {
2759 struct nlattr *stats = nla_nest_start(d->skb, TCA_STATS_APP);
2760 struct cake_sched_data *q = qdisc_priv(sch);
2761 struct nlattr *tstats, *ts;
2762 int i;
2764 if (!stats)
2765 return -1;
2767 #define PUT_STAT_U32(attr, data) do { \
2768 if (nla_put_u32(d->skb, TCA_CAKE_STATS_ ## attr, data)) \
2769 goto nla_put_failure; \
2770 } while (0)
2771 #define PUT_STAT_U64(attr, data) do { \
2772 if (nla_put_u64_64bit(d->skb, TCA_CAKE_STATS_ ## attr, \
2773 data, TCA_CAKE_STATS_PAD)) \
2774 goto nla_put_failure; \
2775 } while (0)
2777 PUT_STAT_U64(CAPACITY_ESTIMATE64, q->avg_peak_bandwidth);
2778 PUT_STAT_U32(MEMORY_LIMIT, q->buffer_limit);
2779 PUT_STAT_U32(MEMORY_USED, q->buffer_max_used);
2780 PUT_STAT_U32(AVG_NETOFF, ((q->avg_netoff + 0x8000) >> 16));
2781 PUT_STAT_U32(MAX_NETLEN, q->max_netlen);
2782 PUT_STAT_U32(MAX_ADJLEN, q->max_adjlen);
2783 PUT_STAT_U32(MIN_NETLEN, q->min_netlen);
2784 PUT_STAT_U32(MIN_ADJLEN, q->min_adjlen);
2786 #undef PUT_STAT_U32
2787 #undef PUT_STAT_U64
2789 tstats = nla_nest_start(d->skb, TCA_CAKE_STATS_TIN_STATS);
2790 if (!tstats)
2791 goto nla_put_failure;
2793 #define PUT_TSTAT_U32(attr, data) do { \
2794 if (nla_put_u32(d->skb, TCA_CAKE_TIN_STATS_ ## attr, data)) \
2795 goto nla_put_failure; \
2796 } while (0)
2797 #define PUT_TSTAT_U64(attr, data) do { \
2798 if (nla_put_u64_64bit(d->skb, TCA_CAKE_TIN_STATS_ ## attr, \
2799 data, TCA_CAKE_TIN_STATS_PAD)) \
2800 goto nla_put_failure; \
2801 } while (0)
2803 for (i = 0; i < q->tin_cnt; i++) {
2804 struct cake_tin_data *b = &q->tins[q->tin_order[i]];
2806 ts = nla_nest_start(d->skb, i + 1);
2807 if (!ts)
2808 goto nla_put_failure;
2810 PUT_TSTAT_U64(THRESHOLD_RATE64, b->tin_rate_bps);
2811 PUT_TSTAT_U64(SENT_BYTES64, b->bytes);
2812 PUT_TSTAT_U32(BACKLOG_BYTES, b->tin_backlog);
2814 PUT_TSTAT_U32(TARGET_US,
2815 ktime_to_us(ns_to_ktime(b->cparams.target)));
2816 PUT_TSTAT_U32(INTERVAL_US,
2817 ktime_to_us(ns_to_ktime(b->cparams.interval)));
2819 PUT_TSTAT_U32(SENT_PACKETS, b->packets);
2820 PUT_TSTAT_U32(DROPPED_PACKETS, b->tin_dropped);
2821 PUT_TSTAT_U32(ECN_MARKED_PACKETS, b->tin_ecn_mark);
2822 PUT_TSTAT_U32(ACKS_DROPPED_PACKETS, b->ack_drops);
2824 PUT_TSTAT_U32(PEAK_DELAY_US,
2825 ktime_to_us(ns_to_ktime(b->peak_delay)));
2826 PUT_TSTAT_U32(AVG_DELAY_US,
2827 ktime_to_us(ns_to_ktime(b->avge_delay)));
2828 PUT_TSTAT_U32(BASE_DELAY_US,
2829 ktime_to_us(ns_to_ktime(b->base_delay)));
2831 PUT_TSTAT_U32(WAY_INDIRECT_HITS, b->way_hits);
2832 PUT_TSTAT_U32(WAY_MISSES, b->way_misses);
2833 PUT_TSTAT_U32(WAY_COLLISIONS, b->way_collisions);
2835 PUT_TSTAT_U32(SPARSE_FLOWS, b->sparse_flow_count +
2836 b->decaying_flow_count);
2837 PUT_TSTAT_U32(BULK_FLOWS, b->bulk_flow_count);
2838 PUT_TSTAT_U32(UNRESPONSIVE_FLOWS, b->unresponsive_flow_count);
2839 PUT_TSTAT_U32(MAX_SKBLEN, b->max_skblen);
2841 PUT_TSTAT_U32(FLOW_QUANTUM, b->flow_quantum);
2842 nla_nest_end(d->skb, ts);
2843 }
2845 #undef PUT_TSTAT_U32
2846 #undef PUT_TSTAT_U64
2848 nla_nest_end(d->skb, tstats);
2849 return nla_nest_end(d->skb, stats);
2851 nla_put_failure:
2852 nla_nest_cancel(d->skb, stats);
2853 return -1;
2854 }
2856 static struct Qdisc *cake_leaf(struct Qdisc *sch, unsigned long arg)
2857 {
2858 return NULL;
2859 }
2861 static unsigned long cake_find(struct Qdisc *sch, u32 classid)
2862 {
2863 return 0;
2864 }
2866 static unsigned long cake_bind(struct Qdisc *sch, unsigned long parent,
2867 u32 classid)
2868 {
2869 return 0;
2870 }
2872 static void cake_unbind(struct Qdisc *q, unsigned long cl)
2873 {
2874 }
2876 static struct tcf_block *cake_tcf_block(struct Qdisc *sch, unsigned long cl,
2877 struct netlink_ext_ack *extack)
2878 {
2879 struct cake_sched_data *q = qdisc_priv(sch);
2881 if (cl)
2882 return NULL;
2883 return q->block;
2884 }
2886 static int cake_dump_class(struct Qdisc *sch, unsigned long cl,
2887 struct sk_buff *skb, struct tcmsg *tcm)
2888 {
2889 tcm->tcm_handle |= TC_H_MIN(cl);
2890 return 0;
2891 }
2893 static int cake_dump_class_stats(struct Qdisc *sch, unsigned long cl,
2894 struct gnet_dump *d)
2895 {
2896 struct cake_sched_data *q = qdisc_priv(sch);
2897 const struct cake_flow *flow = NULL;
2898 struct gnet_stats_queue qs = { 0 };
2899 struct nlattr *stats;
2900 u32 idx = cl - 1;
2902 if (idx < CAKE_QUEUES * q->tin_cnt) {
2903 const struct cake_tin_data *b = \
2904 &q->tins[q->tin_order[idx / CAKE_QUEUES]];
2905 const struct sk_buff *skb;
2907 flow = &b->flows[idx % CAKE_QUEUES];
2909 if (flow->head) {
2910 sch_tree_lock(sch);
2911 skb = flow->head;
2912 while (skb) {
2913 qs.qlen++;
2914 skb = skb->next;
2915 }
2916 sch_tree_unlock(sch);
2917 }
2918 qs.backlog = b->backlogs[idx % CAKE_QUEUES];
2919 qs.drops = flow->dropped;
2920 }
2921 if (gnet_stats_copy_queue(d, NULL, &qs, qs.qlen) < 0)
2922 return -1;
2923 if (flow) {
2924 ktime_t now = ktime_get();
2926 stats = nla_nest_start(d->skb, TCA_STATS_APP);
2927 if (!stats)
2928 return -1;
2930 #define PUT_STAT_U32(attr, data) do { \
2931 if (nla_put_u32(d->skb, TCA_CAKE_STATS_ ## attr, data)) \
2932 goto nla_put_failure; \
2933 } while (0)
2934 #define PUT_STAT_S32(attr, data) do { \
2935 if (nla_put_s32(d->skb, TCA_CAKE_STATS_ ## attr, data)) \
2936 goto nla_put_failure; \
2937 } while (0)
2939 PUT_STAT_S32(DEFICIT, flow->deficit);
2940 PUT_STAT_U32(DROPPING, flow->cvars.dropping);
2941 PUT_STAT_U32(COBALT_COUNT, flow->cvars.count);
2942 PUT_STAT_U32(P_DROP, flow->cvars.p_drop);
2943 if (flow->cvars.p_drop) {
2944 PUT_STAT_S32(BLUE_TIMER_US,
2945 ktime_to_us(
2946 ktime_sub(now,
2947 flow->cvars.blue_timer)));
2948 }
2949 if (flow->cvars.dropping) {
2950 PUT_STAT_S32(DROP_NEXT_US,
2951 ktime_to_us(
2952 ktime_sub(now,
2953 flow->cvars.drop_next)));
2954 }
2956 if (nla_nest_end(d->skb, stats) < 0)
2957 return -1;
2958 }
2960 return 0;
2962 nla_put_failure:
2963 nla_nest_cancel(d->skb, stats);
2964 return -1;
2965 }
2967 static void cake_walk(struct Qdisc *sch, struct qdisc_walker *arg)
2968 {
2969 struct cake_sched_data *q = qdisc_priv(sch);
2970 unsigned int i, j;
2972 if (arg->stop)
2973 return;
2975 for (i = 0; i < q->tin_cnt; i++) {
2976 struct cake_tin_data *b = &q->tins[q->tin_order[i]];
2978 for (j = 0; j < CAKE_QUEUES; j++) {
2979 if (list_empty(&b->flows[j].flowchain) ||
2980 arg->count < arg->skip) {
2981 arg->count++;
2982 continue;
2983 }
2984 if (arg->fn(sch, i * CAKE_QUEUES + j + 1, arg) < 0) {
2985 arg->stop = 1;
2986 break;
2987 }
2988 arg->count++;
2989 }
2990 }
2991 }
2993 static const struct Qdisc_class_ops cake_class_ops = {
2994 .leaf = cake_leaf,
2995 .find = cake_find,
2996 .tcf_block = cake_tcf_block,
2997 .bind_tcf = cake_bind,
2998 .unbind_tcf = cake_unbind,
2999 .dump = cake_dump_class,
3000 .dump_stats = cake_dump_class_stats,
3001 .walk = cake_walk,
3002 };
3004 static struct Qdisc_ops cake_qdisc_ops __read_mostly = {
3005 .cl_ops = &cake_class_ops,
3006 .id = "cake",
3007 .priv_size = sizeof(struct cake_sched_data),
3008 .enqueue = cake_enqueue,
3009 .dequeue = cake_dequeue,
3010 .peek = qdisc_peek_dequeued,
3011 .init = cake_init,
3012 .reset = cake_reset,
3013 .destroy = cake_destroy,
3014 .change = cake_change,
3015 .dump = cake_dump,
3016 .dump_stats = cake_dump_stats,
3017 .owner = THIS_MODULE,
3018 };
3020 static int __init cake_module_init(void)
3021 {
3022 return register_qdisc(&cake_qdisc_ops);
3023 }
3025 static void __exit cake_module_exit(void)
3026 {
3027 unregister_qdisc(&cake_qdisc_ops);
3028 }
3030 module_init(cake_module_init)
3031 module_exit(cake_module_exit)
3032 MODULE_AUTHOR("Jonathan Morton");
3033 MODULE_LICENSE("Dual BSD/GPL");
3034 MODULE_DESCRIPTION("The CAKE shaper.");