]>
Commit | Line | Data |
---|---|---|
046f6fd5 THJ |
1 | // SPDX-License-Identifier: GPL-2.0 OR BSD-3-Clause |
2 | ||
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 | */ | |
52 | ||
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> | |
046f6fd5 THJ |
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> | |
72 | ||
ea825115 THJ |
73 | #if IS_ENABLED(CONFIG_NF_CONNTRACK) |
74 | #include <net/netfilter/nf_conntrack_core.h> | |
75 | #endif | |
76 | ||
046f6fd5 THJ |
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 | |
82 | ||
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 | }; | |
97 | ||
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 | }; | |
116 | ||
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 | }; | |
124 | ||
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 */ | |
137 | ||
138 | struct cake_host { | |
139 | u32 srchost_tag; | |
140 | u32 dsthost_tag; | |
71263992 GA |
141 | u16 srchost_bulk_flow_count; |
142 | u16 dsthost_bulk_flow_count; | |
046f6fd5 THJ |
143 | }; |
144 | ||
145 | struct cake_heap_entry { | |
146 | u16 t:3, b:10; | |
147 | }; | |
148 | ||
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; | |
156 | ||
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; | |
163 | ||
164 | u32 max_skblen; | |
165 | ||
166 | struct list_head new_flows; | |
167 | struct list_head old_flows; | |
168 | struct list_head decaying_flows; | |
169 | ||
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; | |
175 | ||
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; | |
182 | ||
183 | u32 packets; | |
184 | u64 bytes; | |
185 | ||
186 | u32 ack_drops; | |
187 | ||
188 | /* moving averages */ | |
189 | u64 avge_delay; | |
190 | u64 peak_delay; | |
191 | u64 base_delay; | |
192 | ||
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 */ | |
199 | ||
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; | |
204 | ||
205 | struct cake_heap_entry overflow_heap[CAKE_QUEUES * CAKE_MAX_TINS]; | |
206 | u16 overflow_timeout; | |
207 | ||
208 | u16 tin_cnt; | |
209 | u8 tin_mode; | |
210 | u8 flow_mode; | |
211 | u8 ack_filter; | |
212 | u8 atm_mode; | |
213 | ||
eab2fc82 THJ |
214 | u32 fwmark_mask; |
215 | u16 fwmark_shft; | |
216 | ||
046f6fd5 THJ |
217 | /* time_next = time_this + ((len * rate_ns) >> rate_shft) */ |
218 | u16 rate_shft; | |
219 | ktime_t time_next_packet; | |
220 | ktime_t failsafe_next_packet; | |
221 | u64 rate_ns; | |
222 | u64 rate_bps; | |
223 | u16 rate_flags; | |
224 | s16 rate_overhead; | |
225 | u16 rate_mpu; | |
226 | u64 interval; | |
227 | u64 target; | |
228 | ||
229 | /* resource tracking */ | |
230 | u32 buffer_used; | |
231 | u32 buffer_max_used; | |
232 | u32 buffer_limit; | |
233 | u32 buffer_config_limit; | |
234 | ||
235 | /* indices for dequeue */ | |
236 | u16 cur_tin; | |
237 | u16 cur_flow; | |
238 | ||
239 | struct qdisc_watchdog watchdog; | |
240 | const u8 *tin_index; | |
241 | const u8 *tin_order; | |
242 | ||
243 | /* bandwidth capacity estimate */ | |
244 | ktime_t last_packet_time; | |
245 | ktime_t avg_window_begin; | |
246 | u64 avg_packet_interval; | |
247 | u64 avg_window_bytes; | |
248 | u64 avg_peak_bandwidth; | |
249 | ktime_t last_reconfig_time; | |
250 | ||
251 | /* packet length stats */ | |
252 | u32 avg_netoff; | |
253 | u16 max_netlen; | |
254 | u16 max_adjlen; | |
255 | u16 min_netlen; | |
256 | u16 min_adjlen; | |
257 | }; | |
258 | ||
259 | enum { | |
260 | CAKE_FLAG_OVERHEAD = BIT(0), | |
261 | CAKE_FLAG_AUTORATE_INGRESS = BIT(1), | |
262 | CAKE_FLAG_INGRESS = BIT(2), | |
263 | CAKE_FLAG_WASH = BIT(3), | |
eab2fc82 | 264 | CAKE_FLAG_SPLIT_GSO = BIT(4) |
046f6fd5 THJ |
265 | }; |
266 | ||
267 | /* COBALT operates the Codel and BLUE algorithms in parallel, in order to | |
268 | * obtain the best features of each. Codel is excellent on flows which | |
269 | * respond to congestion signals in a TCP-like way. BLUE is more effective on | |
270 | * unresponsive flows. | |
271 | */ | |
272 | ||
273 | struct cobalt_skb_cb { | |
274 | ktime_t enqueue_time; | |
a729b7f0 | 275 | u32 adjusted_len; |
046f6fd5 THJ |
276 | }; |
277 | ||
278 | static u64 us_to_ns(u64 us) | |
279 | { | |
280 | return us * NSEC_PER_USEC; | |
281 | } | |
282 | ||
283 | static struct cobalt_skb_cb *get_cobalt_cb(const struct sk_buff *skb) | |
284 | { | |
285 | qdisc_cb_private_validate(skb, sizeof(struct cobalt_skb_cb)); | |
286 | return (struct cobalt_skb_cb *)qdisc_skb_cb(skb)->data; | |
287 | } | |
288 | ||
289 | static ktime_t cobalt_get_enqueue_time(const struct sk_buff *skb) | |
290 | { | |
291 | return get_cobalt_cb(skb)->enqueue_time; | |
292 | } | |
293 | ||
294 | static void cobalt_set_enqueue_time(struct sk_buff *skb, | |
295 | ktime_t now) | |
296 | { | |
297 | get_cobalt_cb(skb)->enqueue_time = now; | |
298 | } | |
299 | ||
300 | static u16 quantum_div[CAKE_QUEUES + 1] = {0}; | |
301 | ||
83f8fd69 THJ |
302 | /* Diffserv lookup tables */ |
303 | ||
304 | static const u8 precedence[] = { | |
305 | 0, 0, 0, 0, 0, 0, 0, 0, | |
306 | 1, 1, 1, 1, 1, 1, 1, 1, | |
307 | 2, 2, 2, 2, 2, 2, 2, 2, | |
308 | 3, 3, 3, 3, 3, 3, 3, 3, | |
309 | 4, 4, 4, 4, 4, 4, 4, 4, | |
310 | 5, 5, 5, 5, 5, 5, 5, 5, | |
311 | 6, 6, 6, 6, 6, 6, 6, 6, | |
312 | 7, 7, 7, 7, 7, 7, 7, 7, | |
313 | }; | |
314 | ||
315 | static const u8 diffserv8[] = { | |
316 | 2, 5, 1, 2, 4, 2, 2, 2, | |
317 | 0, 2, 1, 2, 1, 2, 1, 2, | |
318 | 5, 2, 4, 2, 4, 2, 4, 2, | |
319 | 3, 2, 3, 2, 3, 2, 3, 2, | |
320 | 6, 2, 3, 2, 3, 2, 3, 2, | |
321 | 6, 2, 2, 2, 6, 2, 6, 2, | |
322 | 7, 2, 2, 2, 2, 2, 2, 2, | |
323 | 7, 2, 2, 2, 2, 2, 2, 2, | |
324 | }; | |
325 | ||
326 | static const u8 diffserv4[] = { | |
327 | 0, 2, 0, 0, 2, 0, 0, 0, | |
328 | 1, 0, 0, 0, 0, 0, 0, 0, | |
329 | 2, 0, 2, 0, 2, 0, 2, 0, | |
330 | 2, 0, 2, 0, 2, 0, 2, 0, | |
331 | 3, 0, 2, 0, 2, 0, 2, 0, | |
332 | 3, 0, 0, 0, 3, 0, 3, 0, | |
333 | 3, 0, 0, 0, 0, 0, 0, 0, | |
334 | 3, 0, 0, 0, 0, 0, 0, 0, | |
335 | }; | |
336 | ||
337 | static const u8 diffserv3[] = { | |
338 | 0, 0, 0, 0, 2, 0, 0, 0, | |
339 | 1, 0, 0, 0, 0, 0, 0, 0, | |
340 | 0, 0, 0, 0, 0, 0, 0, 0, | |
341 | 0, 0, 0, 0, 0, 0, 0, 0, | |
342 | 0, 0, 0, 0, 0, 0, 0, 0, | |
343 | 0, 0, 0, 0, 2, 0, 2, 0, | |
344 | 2, 0, 0, 0, 0, 0, 0, 0, | |
345 | 2, 0, 0, 0, 0, 0, 0, 0, | |
346 | }; | |
347 | ||
348 | static const u8 besteffort[] = { | |
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 | 0, 0, 0, 0, 0, 0, 0, 0, | |
355 | 0, 0, 0, 0, 0, 0, 0, 0, | |
356 | 0, 0, 0, 0, 0, 0, 0, 0, | |
357 | }; | |
358 | ||
359 | /* tin priority order for stats dumping */ | |
360 | ||
361 | static const u8 normal_order[] = {0, 1, 2, 3, 4, 5, 6, 7}; | |
362 | static const u8 bulk_order[] = {1, 0, 2, 3}; | |
363 | ||
046f6fd5 THJ |
364 | #define REC_INV_SQRT_CACHE (16) |
365 | static u32 cobalt_rec_inv_sqrt_cache[REC_INV_SQRT_CACHE] = {0}; | |
366 | ||
367 | /* http://en.wikipedia.org/wiki/Methods_of_computing_square_roots | |
368 | * new_invsqrt = (invsqrt / 2) * (3 - count * invsqrt^2) | |
369 | * | |
370 | * Here, invsqrt is a fixed point number (< 1.0), 32bit mantissa, aka Q0.32 | |
371 | */ | |
372 | ||
373 | static void cobalt_newton_step(struct cobalt_vars *vars) | |
374 | { | |
375 | u32 invsqrt, invsqrt2; | |
376 | u64 val; | |
377 | ||
378 | invsqrt = vars->rec_inv_sqrt; | |
379 | invsqrt2 = ((u64)invsqrt * invsqrt) >> 32; | |
380 | val = (3LL << 32) - ((u64)vars->count * invsqrt2); | |
381 | ||
382 | val >>= 2; /* avoid overflow in following multiply */ | |
383 | val = (val * invsqrt) >> (32 - 2 + 1); | |
384 | ||
385 | vars->rec_inv_sqrt = val; | |
386 | } | |
387 | ||
388 | static void cobalt_invsqrt(struct cobalt_vars *vars) | |
389 | { | |
390 | if (vars->count < REC_INV_SQRT_CACHE) | |
391 | vars->rec_inv_sqrt = cobalt_rec_inv_sqrt_cache[vars->count]; | |
392 | else | |
393 | cobalt_newton_step(vars); | |
394 | } | |
395 | ||
396 | /* There is a big difference in timing between the accurate values placed in | |
397 | * the cache and the approximations given by a single Newton step for small | |
398 | * count values, particularly when stepping from count 1 to 2 or vice versa. | |
399 | * Above 16, a single Newton step gives sufficient accuracy in either | |
400 | * direction, given the precision stored. | |
401 | * | |
402 | * The magnitude of the error when stepping up to count 2 is such as to give | |
403 | * the value that *should* have been produced at count 4. | |
404 | */ | |
405 | ||
406 | static void cobalt_cache_init(void) | |
407 | { | |
408 | struct cobalt_vars v; | |
409 | ||
410 | memset(&v, 0, sizeof(v)); | |
411 | v.rec_inv_sqrt = ~0U; | |
412 | cobalt_rec_inv_sqrt_cache[0] = v.rec_inv_sqrt; | |
413 | ||
414 | for (v.count = 1; v.count < REC_INV_SQRT_CACHE; v.count++) { | |
415 | cobalt_newton_step(&v); | |
416 | cobalt_newton_step(&v); | |
417 | cobalt_newton_step(&v); | |
418 | cobalt_newton_step(&v); | |
419 | ||
420 | cobalt_rec_inv_sqrt_cache[v.count] = v.rec_inv_sqrt; | |
421 | } | |
422 | } | |
423 | ||
424 | static void cobalt_vars_init(struct cobalt_vars *vars) | |
425 | { | |
426 | memset(vars, 0, sizeof(*vars)); | |
427 | ||
428 | if (!cobalt_rec_inv_sqrt_cache[0]) { | |
429 | cobalt_cache_init(); | |
430 | cobalt_rec_inv_sqrt_cache[0] = ~0; | |
431 | } | |
432 | } | |
433 | ||
434 | /* CoDel control_law is t + interval/sqrt(count) | |
435 | * We maintain in rec_inv_sqrt the reciprocal value of sqrt(count) to avoid | |
436 | * both sqrt() and divide operation. | |
437 | */ | |
438 | static ktime_t cobalt_control(ktime_t t, | |
439 | u64 interval, | |
440 | u32 rec_inv_sqrt) | |
441 | { | |
442 | return ktime_add_ns(t, reciprocal_scale(interval, | |
443 | rec_inv_sqrt)); | |
444 | } | |
445 | ||
446 | /* Call this when a packet had to be dropped due to queue overflow. Returns | |
447 | * true if the BLUE state was quiescent before but active after this call. | |
448 | */ | |
449 | static bool cobalt_queue_full(struct cobalt_vars *vars, | |
450 | struct cobalt_params *p, | |
451 | ktime_t now) | |
452 | { | |
453 | bool up = false; | |
454 | ||
455 | if (ktime_to_ns(ktime_sub(now, vars->blue_timer)) > p->target) { | |
456 | up = !vars->p_drop; | |
457 | vars->p_drop += p->p_inc; | |
458 | if (vars->p_drop < p->p_inc) | |
459 | vars->p_drop = ~0; | |
460 | vars->blue_timer = now; | |
461 | } | |
462 | vars->dropping = true; | |
463 | vars->drop_next = now; | |
464 | if (!vars->count) | |
465 | vars->count = 1; | |
466 | ||
467 | return up; | |
468 | } | |
469 | ||
470 | /* Call this when the queue was serviced but turned out to be empty. Returns | |
471 | * true if the BLUE state was active before but quiescent after this call. | |
472 | */ | |
473 | static bool cobalt_queue_empty(struct cobalt_vars *vars, | |
474 | struct cobalt_params *p, | |
475 | ktime_t now) | |
476 | { | |
477 | bool down = false; | |
478 | ||
479 | if (vars->p_drop && | |
480 | ktime_to_ns(ktime_sub(now, vars->blue_timer)) > p->target) { | |
481 | if (vars->p_drop < p->p_dec) | |
482 | vars->p_drop = 0; | |
483 | else | |
484 | vars->p_drop -= p->p_dec; | |
485 | vars->blue_timer = now; | |
486 | down = !vars->p_drop; | |
487 | } | |
488 | vars->dropping = false; | |
489 | ||
490 | if (vars->count && ktime_to_ns(ktime_sub(now, vars->drop_next)) >= 0) { | |
491 | vars->count--; | |
492 | cobalt_invsqrt(vars); | |
493 | vars->drop_next = cobalt_control(vars->drop_next, | |
494 | p->interval, | |
495 | vars->rec_inv_sqrt); | |
496 | } | |
497 | ||
498 | return down; | |
499 | } | |
500 | ||
501 | /* Call this with a freshly dequeued packet for possible congestion marking. | |
502 | * Returns true as an instruction to drop the packet, false for delivery. | |
503 | */ | |
504 | static bool cobalt_should_drop(struct cobalt_vars *vars, | |
505 | struct cobalt_params *p, | |
506 | ktime_t now, | |
7298de9c THJ |
507 | struct sk_buff *skb, |
508 | u32 bulk_flows) | |
046f6fd5 THJ |
509 | { |
510 | bool next_due, over_target, drop = false; | |
511 | ktime_t schedule; | |
512 | u64 sojourn; | |
513 | ||
514 | /* The 'schedule' variable records, in its sign, whether 'now' is before or | |
515 | * after 'drop_next'. This allows 'drop_next' to be updated before the next | |
516 | * scheduling decision is actually branched, without destroying that | |
517 | * information. Similarly, the first 'schedule' value calculated is preserved | |
518 | * in the boolean 'next_due'. | |
519 | * | |
520 | * As for 'drop_next', we take advantage of the fact that 'interval' is both | |
521 | * the delay between first exceeding 'target' and the first signalling event, | |
522 | * *and* the scaling factor for the signalling frequency. It's therefore very | |
523 | * natural to use a single mechanism for both purposes, and eliminates a | |
524 | * significant amount of reference Codel's spaghetti code. To help with this, | |
525 | * both the '0' and '1' entries in the invsqrt cache are 0xFFFFFFFF, as close | |
526 | * as possible to 1.0 in fixed-point. | |
527 | */ | |
528 | ||
529 | sojourn = ktime_to_ns(ktime_sub(now, cobalt_get_enqueue_time(skb))); | |
530 | schedule = ktime_sub(now, vars->drop_next); | |
531 | over_target = sojourn > p->target && | |
7298de9c | 532 | sojourn > p->mtu_time * bulk_flows * 2 && |
046f6fd5 THJ |
533 | sojourn > p->mtu_time * 4; |
534 | next_due = vars->count && ktime_to_ns(schedule) >= 0; | |
535 | ||
536 | vars->ecn_marked = false; | |
537 | ||
538 | if (over_target) { | |
539 | if (!vars->dropping) { | |
540 | vars->dropping = true; | |
541 | vars->drop_next = cobalt_control(now, | |
542 | p->interval, | |
543 | vars->rec_inv_sqrt); | |
544 | } | |
545 | if (!vars->count) | |
546 | vars->count = 1; | |
547 | } else if (vars->dropping) { | |
548 | vars->dropping = false; | |
549 | } | |
550 | ||
551 | if (next_due && vars->dropping) { | |
552 | /* Use ECN mark if possible, otherwise drop */ | |
553 | drop = !(vars->ecn_marked = INET_ECN_set_ce(skb)); | |
554 | ||
555 | vars->count++; | |
556 | if (!vars->count) | |
557 | vars->count--; | |
558 | cobalt_invsqrt(vars); | |
559 | vars->drop_next = cobalt_control(vars->drop_next, | |
560 | p->interval, | |
561 | vars->rec_inv_sqrt); | |
562 | schedule = ktime_sub(now, vars->drop_next); | |
563 | } else { | |
564 | while (next_due) { | |
565 | vars->count--; | |
566 | cobalt_invsqrt(vars); | |
567 | vars->drop_next = cobalt_control(vars->drop_next, | |
568 | p->interval, | |
569 | vars->rec_inv_sqrt); | |
570 | schedule = ktime_sub(now, vars->drop_next); | |
571 | next_due = vars->count && ktime_to_ns(schedule) >= 0; | |
572 | } | |
573 | } | |
574 | ||
575 | /* Simple BLUE implementation. Lack of ECN is deliberate. */ | |
576 | if (vars->p_drop) | |
577 | drop |= (prandom_u32() < vars->p_drop); | |
578 | ||
579 | /* Overload the drop_next field as an activity timeout */ | |
580 | if (!vars->count) | |
581 | vars->drop_next = ktime_add_ns(now, p->interval); | |
582 | else if (ktime_to_ns(schedule) > 0 && !drop) | |
583 | vars->drop_next = now; | |
584 | ||
585 | return drop; | |
586 | } | |
587 | ||
ea825115 THJ |
588 | static void cake_update_flowkeys(struct flow_keys *keys, |
589 | const struct sk_buff *skb) | |
590 | { | |
591 | #if IS_ENABLED(CONFIG_NF_CONNTRACK) | |
592 | struct nf_conntrack_tuple tuple = {}; | |
593 | bool rev = !skb->_nfct; | |
594 | ||
595 | if (tc_skb_protocol(skb) != htons(ETH_P_IP)) | |
596 | return; | |
597 | ||
598 | if (!nf_ct_get_tuple_skb(&tuple, skb)) | |
599 | return; | |
600 | ||
601 | keys->addrs.v4addrs.src = rev ? tuple.dst.u3.ip : tuple.src.u3.ip; | |
602 | keys->addrs.v4addrs.dst = rev ? tuple.src.u3.ip : tuple.dst.u3.ip; | |
603 | ||
604 | if (keys->ports.ports) { | |
605 | keys->ports.src = rev ? tuple.dst.u.all : tuple.src.u.all; | |
606 | keys->ports.dst = rev ? tuple.src.u.all : tuple.dst.u.all; | |
607 | } | |
608 | #endif | |
609 | } | |
610 | ||
046f6fd5 THJ |
611 | /* Cake has several subtle multiple bit settings. In these cases you |
612 | * would be matching triple isolate mode as well. | |
613 | */ | |
614 | ||
615 | static bool cake_dsrc(int flow_mode) | |
616 | { | |
617 | return (flow_mode & CAKE_FLOW_DUAL_SRC) == CAKE_FLOW_DUAL_SRC; | |
618 | } | |
619 | ||
620 | static bool cake_ddst(int flow_mode) | |
621 | { | |
622 | return (flow_mode & CAKE_FLOW_DUAL_DST) == CAKE_FLOW_DUAL_DST; | |
623 | } | |
624 | ||
625 | static u32 cake_hash(struct cake_tin_data *q, const struct sk_buff *skb, | |
93cfb6c1 | 626 | int flow_mode, u16 flow_override, u16 host_override) |
046f6fd5 | 627 | { |
93cfb6c1 | 628 | u32 flow_hash = 0, srchost_hash = 0, dsthost_hash = 0; |
046f6fd5 THJ |
629 | u16 reduced_hash, srchost_idx, dsthost_idx; |
630 | struct flow_keys keys, host_keys; | |
631 | ||
632 | if (unlikely(flow_mode == CAKE_FLOW_NONE)) | |
633 | return 0; | |
634 | ||
93cfb6c1 THJ |
635 | /* If both overrides are set we can skip packet dissection entirely */ |
636 | if ((flow_override || !(flow_mode & CAKE_FLOW_FLOWS)) && | |
637 | (host_override || !(flow_mode & CAKE_FLOW_HOSTS))) | |
638 | goto skip_hash; | |
639 | ||
046f6fd5 THJ |
640 | skb_flow_dissect_flow_keys(skb, &keys, |
641 | FLOW_DISSECTOR_F_STOP_AT_FLOW_LABEL); | |
642 | ||
ea825115 THJ |
643 | if (flow_mode & CAKE_FLOW_NAT_FLAG) |
644 | cake_update_flowkeys(&keys, skb); | |
645 | ||
046f6fd5 THJ |
646 | /* flow_hash_from_keys() sorts the addresses by value, so we have |
647 | * to preserve their order in a separate data structure to treat | |
648 | * src and dst host addresses as independently selectable. | |
649 | */ | |
650 | host_keys = keys; | |
651 | host_keys.ports.ports = 0; | |
652 | host_keys.basic.ip_proto = 0; | |
653 | host_keys.keyid.keyid = 0; | |
654 | host_keys.tags.flow_label = 0; | |
655 | ||
656 | switch (host_keys.control.addr_type) { | |
657 | case FLOW_DISSECTOR_KEY_IPV4_ADDRS: | |
658 | host_keys.addrs.v4addrs.src = 0; | |
659 | dsthost_hash = flow_hash_from_keys(&host_keys); | |
660 | host_keys.addrs.v4addrs.src = keys.addrs.v4addrs.src; | |
661 | host_keys.addrs.v4addrs.dst = 0; | |
662 | srchost_hash = flow_hash_from_keys(&host_keys); | |
663 | break; | |
664 | ||
665 | case FLOW_DISSECTOR_KEY_IPV6_ADDRS: | |
666 | memset(&host_keys.addrs.v6addrs.src, 0, | |
667 | sizeof(host_keys.addrs.v6addrs.src)); | |
668 | dsthost_hash = flow_hash_from_keys(&host_keys); | |
669 | host_keys.addrs.v6addrs.src = keys.addrs.v6addrs.src; | |
670 | memset(&host_keys.addrs.v6addrs.dst, 0, | |
671 | sizeof(host_keys.addrs.v6addrs.dst)); | |
672 | srchost_hash = flow_hash_from_keys(&host_keys); | |
673 | break; | |
674 | ||
675 | default: | |
676 | dsthost_hash = 0; | |
677 | srchost_hash = 0; | |
678 | } | |
679 | ||
680 | /* This *must* be after the above switch, since as a | |
681 | * side-effect it sorts the src and dst addresses. | |
682 | */ | |
683 | if (flow_mode & CAKE_FLOW_FLOWS) | |
684 | flow_hash = flow_hash_from_keys(&keys); | |
685 | ||
93cfb6c1 THJ |
686 | skip_hash: |
687 | if (flow_override) | |
688 | flow_hash = flow_override - 1; | |
689 | if (host_override) { | |
690 | dsthost_hash = host_override - 1; | |
691 | srchost_hash = host_override - 1; | |
692 | } | |
693 | ||
046f6fd5 THJ |
694 | if (!(flow_mode & CAKE_FLOW_FLOWS)) { |
695 | if (flow_mode & CAKE_FLOW_SRC_IP) | |
696 | flow_hash ^= srchost_hash; | |
697 | ||
698 | if (flow_mode & CAKE_FLOW_DST_IP) | |
699 | flow_hash ^= dsthost_hash; | |
700 | } | |
701 | ||
702 | reduced_hash = flow_hash % CAKE_QUEUES; | |
703 | ||
704 | /* set-associative hashing */ | |
705 | /* fast path if no hash collision (direct lookup succeeds) */ | |
706 | if (likely(q->tags[reduced_hash] == flow_hash && | |
707 | q->flows[reduced_hash].set)) { | |
708 | q->way_directs++; | |
709 | } else { | |
710 | u32 inner_hash = reduced_hash % CAKE_SET_WAYS; | |
711 | u32 outer_hash = reduced_hash - inner_hash; | |
712 | bool allocate_src = false; | |
713 | bool allocate_dst = false; | |
714 | u32 i, k; | |
715 | ||
716 | /* check if any active queue in the set is reserved for | |
717 | * this flow. | |
718 | */ | |
719 | for (i = 0, k = inner_hash; i < CAKE_SET_WAYS; | |
720 | i++, k = (k + 1) % CAKE_SET_WAYS) { | |
721 | if (q->tags[outer_hash + k] == flow_hash) { | |
722 | if (i) | |
723 | q->way_hits++; | |
724 | ||
725 | if (!q->flows[outer_hash + k].set) { | |
726 | /* need to increment host refcnts */ | |
727 | allocate_src = cake_dsrc(flow_mode); | |
728 | allocate_dst = cake_ddst(flow_mode); | |
729 | } | |
730 | ||
731 | goto found; | |
732 | } | |
733 | } | |
734 | ||
735 | /* no queue is reserved for this flow, look for an | |
736 | * empty one. | |
737 | */ | |
738 | for (i = 0; i < CAKE_SET_WAYS; | |
739 | i++, k = (k + 1) % CAKE_SET_WAYS) { | |
740 | if (!q->flows[outer_hash + k].set) { | |
741 | q->way_misses++; | |
742 | allocate_src = cake_dsrc(flow_mode); | |
743 | allocate_dst = cake_ddst(flow_mode); | |
744 | goto found; | |
745 | } | |
746 | } | |
747 | ||
748 | /* With no empty queues, default to the original | |
749 | * queue, accept the collision, update the host tags. | |
750 | */ | |
751 | q->way_collisions++; | |
71263992 GA |
752 | if (q->flows[outer_hash + k].set == CAKE_SET_BULK) { |
753 | q->hosts[q->flows[reduced_hash].srchost].srchost_bulk_flow_count--; | |
754 | q->hosts[q->flows[reduced_hash].dsthost].dsthost_bulk_flow_count--; | |
755 | } | |
046f6fd5 THJ |
756 | allocate_src = cake_dsrc(flow_mode); |
757 | allocate_dst = cake_ddst(flow_mode); | |
758 | found: | |
759 | /* reserve queue for future packets in same flow */ | |
760 | reduced_hash = outer_hash + k; | |
761 | q->tags[reduced_hash] = flow_hash; | |
762 | ||
763 | if (allocate_src) { | |
764 | srchost_idx = srchost_hash % CAKE_QUEUES; | |
765 | inner_hash = srchost_idx % CAKE_SET_WAYS; | |
766 | outer_hash = srchost_idx - inner_hash; | |
767 | for (i = 0, k = inner_hash; i < CAKE_SET_WAYS; | |
768 | i++, k = (k + 1) % CAKE_SET_WAYS) { | |
769 | if (q->hosts[outer_hash + k].srchost_tag == | |
770 | srchost_hash) | |
771 | goto found_src; | |
772 | } | |
773 | for (i = 0; i < CAKE_SET_WAYS; | |
774 | i++, k = (k + 1) % CAKE_SET_WAYS) { | |
71263992 | 775 | if (!q->hosts[outer_hash + k].srchost_bulk_flow_count) |
046f6fd5 THJ |
776 | break; |
777 | } | |
778 | q->hosts[outer_hash + k].srchost_tag = srchost_hash; | |
779 | found_src: | |
780 | srchost_idx = outer_hash + k; | |
71263992 GA |
781 | if (q->flows[reduced_hash].set == CAKE_SET_BULK) |
782 | q->hosts[srchost_idx].srchost_bulk_flow_count++; | |
046f6fd5 THJ |
783 | q->flows[reduced_hash].srchost = srchost_idx; |
784 | } | |
785 | ||
786 | if (allocate_dst) { | |
787 | dsthost_idx = dsthost_hash % CAKE_QUEUES; | |
788 | inner_hash = dsthost_idx % CAKE_SET_WAYS; | |
789 | outer_hash = dsthost_idx - inner_hash; | |
790 | for (i = 0, k = inner_hash; i < CAKE_SET_WAYS; | |
791 | i++, k = (k + 1) % CAKE_SET_WAYS) { | |
792 | if (q->hosts[outer_hash + k].dsthost_tag == | |
793 | dsthost_hash) | |
794 | goto found_dst; | |
795 | } | |
796 | for (i = 0; i < CAKE_SET_WAYS; | |
797 | i++, k = (k + 1) % CAKE_SET_WAYS) { | |
71263992 | 798 | if (!q->hosts[outer_hash + k].dsthost_bulk_flow_count) |
046f6fd5 THJ |
799 | break; |
800 | } | |
801 | q->hosts[outer_hash + k].dsthost_tag = dsthost_hash; | |
802 | found_dst: | |
803 | dsthost_idx = outer_hash + k; | |
71263992 GA |
804 | if (q->flows[reduced_hash].set == CAKE_SET_BULK) |
805 | q->hosts[dsthost_idx].dsthost_bulk_flow_count++; | |
046f6fd5 THJ |
806 | q->flows[reduced_hash].dsthost = dsthost_idx; |
807 | } | |
808 | } | |
809 | ||
810 | return reduced_hash; | |
811 | } | |
812 | ||
813 | /* helper functions : might be changed when/if skb use a standard list_head */ | |
814 | /* remove one skb from head of slot queue */ | |
815 | ||
816 | static struct sk_buff *dequeue_head(struct cake_flow *flow) | |
817 | { | |
818 | struct sk_buff *skb = flow->head; | |
819 | ||
820 | if (skb) { | |
821 | flow->head = skb->next; | |
a8305bff | 822 | skb_mark_not_on_list(skb); |
046f6fd5 THJ |
823 | } |
824 | ||
825 | return skb; | |
826 | } | |
827 | ||
828 | /* add skb to flow queue (tail add) */ | |
829 | ||
830 | static void flow_queue_add(struct cake_flow *flow, struct sk_buff *skb) | |
831 | { | |
832 | if (!flow->head) | |
833 | flow->head = skb; | |
834 | else | |
835 | flow->tail->next = skb; | |
836 | flow->tail = skb; | |
837 | skb->next = NULL; | |
838 | } | |
839 | ||
8b713881 THJ |
840 | static struct iphdr *cake_get_iphdr(const struct sk_buff *skb, |
841 | struct ipv6hdr *buf) | |
842 | { | |
843 | unsigned int offset = skb_network_offset(skb); | |
844 | struct iphdr *iph; | |
845 | ||
846 | iph = skb_header_pointer(skb, offset, sizeof(struct iphdr), buf); | |
847 | ||
848 | if (!iph) | |
849 | return NULL; | |
850 | ||
851 | if (iph->version == 4 && iph->protocol == IPPROTO_IPV6) | |
852 | return skb_header_pointer(skb, offset + iph->ihl * 4, | |
853 | sizeof(struct ipv6hdr), buf); | |
854 | ||
855 | else if (iph->version == 4) | |
856 | return iph; | |
857 | ||
858 | else if (iph->version == 6) | |
859 | return skb_header_pointer(skb, offset, sizeof(struct ipv6hdr), | |
860 | buf); | |
861 | ||
862 | return NULL; | |
863 | } | |
864 | ||
865 | static struct tcphdr *cake_get_tcphdr(const struct sk_buff *skb, | |
866 | void *buf, unsigned int bufsize) | |
867 | { | |
868 | unsigned int offset = skb_network_offset(skb); | |
869 | const struct ipv6hdr *ipv6h; | |
870 | const struct tcphdr *tcph; | |
871 | const struct iphdr *iph; | |
872 | struct ipv6hdr _ipv6h; | |
873 | struct tcphdr _tcph; | |
874 | ||
875 | ipv6h = skb_header_pointer(skb, offset, sizeof(_ipv6h), &_ipv6h); | |
876 | ||
877 | if (!ipv6h) | |
878 | return NULL; | |
879 | ||
880 | if (ipv6h->version == 4) { | |
881 | iph = (struct iphdr *)ipv6h; | |
882 | offset += iph->ihl * 4; | |
883 | ||
884 | /* special-case 6in4 tunnelling, as that is a common way to get | |
885 | * v6 connectivity in the home | |
886 | */ | |
887 | if (iph->protocol == IPPROTO_IPV6) { | |
888 | ipv6h = skb_header_pointer(skb, offset, | |
889 | sizeof(_ipv6h), &_ipv6h); | |
890 | ||
891 | if (!ipv6h || ipv6h->nexthdr != IPPROTO_TCP) | |
892 | return NULL; | |
893 | ||
894 | offset += sizeof(struct ipv6hdr); | |
895 | ||
896 | } else if (iph->protocol != IPPROTO_TCP) { | |
897 | return NULL; | |
898 | } | |
899 | ||
900 | } else if (ipv6h->version == 6) { | |
901 | if (ipv6h->nexthdr != IPPROTO_TCP) | |
902 | return NULL; | |
903 | ||
904 | offset += sizeof(struct ipv6hdr); | |
905 | } else { | |
906 | return NULL; | |
907 | } | |
908 | ||
909 | tcph = skb_header_pointer(skb, offset, sizeof(_tcph), &_tcph); | |
910 | if (!tcph) | |
911 | return NULL; | |
912 | ||
913 | return skb_header_pointer(skb, offset, | |
914 | min(__tcp_hdrlen(tcph), bufsize), buf); | |
915 | } | |
916 | ||
917 | static const void *cake_get_tcpopt(const struct tcphdr *tcph, | |
918 | int code, int *oplen) | |
919 | { | |
920 | /* inspired by tcp_parse_options in tcp_input.c */ | |
921 | int length = __tcp_hdrlen(tcph) - sizeof(struct tcphdr); | |
922 | const u8 *ptr = (const u8 *)(tcph + 1); | |
923 | ||
924 | while (length > 0) { | |
925 | int opcode = *ptr++; | |
926 | int opsize; | |
927 | ||
928 | if (opcode == TCPOPT_EOL) | |
929 | break; | |
930 | if (opcode == TCPOPT_NOP) { | |
931 | length--; | |
932 | continue; | |
933 | } | |
934 | opsize = *ptr++; | |
935 | if (opsize < 2 || opsize > length) | |
936 | break; | |
937 | ||
938 | if (opcode == code) { | |
939 | *oplen = opsize; | |
940 | return ptr; | |
941 | } | |
942 | ||
943 | ptr += opsize - 2; | |
944 | length -= opsize; | |
945 | } | |
946 | ||
947 | return NULL; | |
948 | } | |
949 | ||
950 | /* Compare two SACK sequences. A sequence is considered greater if it SACKs more | |
951 | * bytes than the other. In the case where both sequences ACKs bytes that the | |
952 | * other doesn't, A is considered greater. DSACKs in A also makes A be | |
953 | * considered greater. | |
954 | * | |
955 | * @return -1, 0 or 1 as normal compare functions | |
956 | */ | |
957 | static int cake_tcph_sack_compare(const struct tcphdr *tcph_a, | |
958 | const struct tcphdr *tcph_b) | |
959 | { | |
960 | const struct tcp_sack_block_wire *sack_a, *sack_b; | |
961 | u32 ack_seq_a = ntohl(tcph_a->ack_seq); | |
962 | u32 bytes_a = 0, bytes_b = 0; | |
963 | int oplen_a, oplen_b; | |
964 | bool first = true; | |
965 | ||
966 | sack_a = cake_get_tcpopt(tcph_a, TCPOPT_SACK, &oplen_a); | |
967 | sack_b = cake_get_tcpopt(tcph_b, TCPOPT_SACK, &oplen_b); | |
968 | ||
969 | /* pointers point to option contents */ | |
970 | oplen_a -= TCPOLEN_SACK_BASE; | |
971 | oplen_b -= TCPOLEN_SACK_BASE; | |
972 | ||
973 | if (sack_a && oplen_a >= sizeof(*sack_a) && | |
974 | (!sack_b || oplen_b < sizeof(*sack_b))) | |
975 | return -1; | |
976 | else if (sack_b && oplen_b >= sizeof(*sack_b) && | |
977 | (!sack_a || oplen_a < sizeof(*sack_a))) | |
978 | return 1; | |
979 | else if ((!sack_a || oplen_a < sizeof(*sack_a)) && | |
980 | (!sack_b || oplen_b < sizeof(*sack_b))) | |
981 | return 0; | |
982 | ||
983 | while (oplen_a >= sizeof(*sack_a)) { | |
984 | const struct tcp_sack_block_wire *sack_tmp = sack_b; | |
985 | u32 start_a = get_unaligned_be32(&sack_a->start_seq); | |
986 | u32 end_a = get_unaligned_be32(&sack_a->end_seq); | |
987 | int oplen_tmp = oplen_b; | |
988 | bool found = false; | |
989 | ||
990 | /* DSACK; always considered greater to prevent dropping */ | |
991 | if (before(start_a, ack_seq_a)) | |
992 | return -1; | |
993 | ||
994 | bytes_a += end_a - start_a; | |
995 | ||
996 | while (oplen_tmp >= sizeof(*sack_tmp)) { | |
997 | u32 start_b = get_unaligned_be32(&sack_tmp->start_seq); | |
998 | u32 end_b = get_unaligned_be32(&sack_tmp->end_seq); | |
999 | ||
1000 | /* first time through we count the total size */ | |
1001 | if (first) | |
1002 | bytes_b += end_b - start_b; | |
1003 | ||
1004 | if (!after(start_b, start_a) && !before(end_b, end_a)) { | |
1005 | found = true; | |
1006 | if (!first) | |
1007 | break; | |
1008 | } | |
1009 | oplen_tmp -= sizeof(*sack_tmp); | |
1010 | sack_tmp++; | |
1011 | } | |
1012 | ||
1013 | if (!found) | |
1014 | return -1; | |
1015 | ||
1016 | oplen_a -= sizeof(*sack_a); | |
1017 | sack_a++; | |
1018 | first = false; | |
1019 | } | |
1020 | ||
1021 | /* If we made it this far, all ranges SACKed by A are covered by B, so | |
1022 | * either the SACKs are equal, or B SACKs more bytes. | |
1023 | */ | |
1024 | return bytes_b > bytes_a ? 1 : 0; | |
1025 | } | |
1026 | ||
1027 | static void cake_tcph_get_tstamp(const struct tcphdr *tcph, | |
1028 | u32 *tsval, u32 *tsecr) | |
1029 | { | |
1030 | const u8 *ptr; | |
1031 | int opsize; | |
1032 | ||
1033 | ptr = cake_get_tcpopt(tcph, TCPOPT_TIMESTAMP, &opsize); | |
1034 | ||
1035 | if (ptr && opsize == TCPOLEN_TIMESTAMP) { | |
1036 | *tsval = get_unaligned_be32(ptr); | |
1037 | *tsecr = get_unaligned_be32(ptr + 4); | |
1038 | } | |
1039 | } | |
1040 | ||
1041 | static bool cake_tcph_may_drop(const struct tcphdr *tcph, | |
1042 | u32 tstamp_new, u32 tsecr_new) | |
1043 | { | |
1044 | /* inspired by tcp_parse_options in tcp_input.c */ | |
1045 | int length = __tcp_hdrlen(tcph) - sizeof(struct tcphdr); | |
1046 | const u8 *ptr = (const u8 *)(tcph + 1); | |
1047 | u32 tstamp, tsecr; | |
1048 | ||
1049 | /* 3 reserved flags must be unset to avoid future breakage | |
1050 | * ACK must be set | |
1051 | * ECE/CWR are handled separately | |
1052 | * All other flags URG/PSH/RST/SYN/FIN must be unset | |
1053 | * 0x0FFF0000 = all TCP flags (confirm ACK=1, others zero) | |
1054 | * 0x00C00000 = CWR/ECE (handled separately) | |
1055 | * 0x0F3F0000 = 0x0FFF0000 & ~0x00C00000 | |
1056 | */ | |
1057 | if (((tcp_flag_word(tcph) & | |
1058 | cpu_to_be32(0x0F3F0000)) != TCP_FLAG_ACK)) | |
1059 | return false; | |
1060 | ||
1061 | while (length > 0) { | |
1062 | int opcode = *ptr++; | |
1063 | int opsize; | |
1064 | ||
1065 | if (opcode == TCPOPT_EOL) | |
1066 | break; | |
1067 | if (opcode == TCPOPT_NOP) { | |
1068 | length--; | |
1069 | continue; | |
1070 | } | |
1071 | opsize = *ptr++; | |
1072 | if (opsize < 2 || opsize > length) | |
1073 | break; | |
1074 | ||
1075 | switch (opcode) { | |
1076 | case TCPOPT_MD5SIG: /* doesn't influence state */ | |
1077 | break; | |
1078 | ||
1079 | case TCPOPT_SACK: /* stricter checking performed later */ | |
1080 | if (opsize % 8 != 2) | |
1081 | return false; | |
1082 | break; | |
1083 | ||
1084 | case TCPOPT_TIMESTAMP: | |
1085 | /* only drop timestamps lower than new */ | |
1086 | if (opsize != TCPOLEN_TIMESTAMP) | |
1087 | return false; | |
1088 | tstamp = get_unaligned_be32(ptr); | |
1089 | tsecr = get_unaligned_be32(ptr + 4); | |
1090 | if (after(tstamp, tstamp_new) || | |
1091 | after(tsecr, tsecr_new)) | |
1092 | return false; | |
1093 | break; | |
1094 | ||
1095 | case TCPOPT_MSS: /* these should only be set on SYN */ | |
1096 | case TCPOPT_WINDOW: | |
1097 | case TCPOPT_SACK_PERM: | |
1098 | case TCPOPT_FASTOPEN: | |
1099 | case TCPOPT_EXP: | |
1100 | default: /* don't drop if any unknown options are present */ | |
1101 | return false; | |
1102 | } | |
1103 | ||
1104 | ptr += opsize - 2; | |
1105 | length -= opsize; | |
1106 | } | |
1107 | ||
1108 | return true; | |
1109 | } | |
1110 | ||
1111 | static struct sk_buff *cake_ack_filter(struct cake_sched_data *q, | |
1112 | struct cake_flow *flow) | |
1113 | { | |
1114 | bool aggressive = q->ack_filter == CAKE_ACK_AGGRESSIVE; | |
1115 | struct sk_buff *elig_ack = NULL, *elig_ack_prev = NULL; | |
1116 | struct sk_buff *skb_check, *skb_prev = NULL; | |
1117 | const struct ipv6hdr *ipv6h, *ipv6h_check; | |
1118 | unsigned char _tcph[64], _tcph_check[64]; | |
1119 | const struct tcphdr *tcph, *tcph_check; | |
1120 | const struct iphdr *iph, *iph_check; | |
1121 | struct ipv6hdr _iph, _iph_check; | |
1122 | const struct sk_buff *skb; | |
1123 | int seglen, num_found = 0; | |
1124 | u32 tstamp = 0, tsecr = 0; | |
1125 | __be32 elig_flags = 0; | |
1126 | int sack_comp; | |
1127 | ||
1128 | /* no other possible ACKs to filter */ | |
1129 | if (flow->head == flow->tail) | |
1130 | return NULL; | |
1131 | ||
1132 | skb = flow->tail; | |
1133 | tcph = cake_get_tcphdr(skb, _tcph, sizeof(_tcph)); | |
1134 | iph = cake_get_iphdr(skb, &_iph); | |
1135 | if (!tcph) | |
1136 | return NULL; | |
1137 | ||
1138 | cake_tcph_get_tstamp(tcph, &tstamp, &tsecr); | |
1139 | ||
1140 | /* the 'triggering' packet need only have the ACK flag set. | |
1141 | * also check that SYN is not set, as there won't be any previous ACKs. | |
1142 | */ | |
1143 | if ((tcp_flag_word(tcph) & | |
1144 | (TCP_FLAG_ACK | TCP_FLAG_SYN)) != TCP_FLAG_ACK) | |
1145 | return NULL; | |
1146 | ||
1147 | /* the 'triggering' ACK is at the tail of the queue, we have already | |
1148 | * returned if it is the only packet in the flow. loop through the rest | |
1149 | * of the queue looking for pure ACKs with the same 5-tuple as the | |
1150 | * triggering one. | |
1151 | */ | |
1152 | for (skb_check = flow->head; | |
1153 | skb_check && skb_check != skb; | |
1154 | skb_prev = skb_check, skb_check = skb_check->next) { | |
1155 | iph_check = cake_get_iphdr(skb_check, &_iph_check); | |
1156 | tcph_check = cake_get_tcphdr(skb_check, &_tcph_check, | |
1157 | sizeof(_tcph_check)); | |
1158 | ||
1159 | /* only TCP packets with matching 5-tuple are eligible, and only | |
1160 | * drop safe headers | |
1161 | */ | |
1162 | if (!tcph_check || iph->version != iph_check->version || | |
1163 | tcph_check->source != tcph->source || | |
1164 | tcph_check->dest != tcph->dest) | |
1165 | continue; | |
1166 | ||
1167 | if (iph_check->version == 4) { | |
1168 | if (iph_check->saddr != iph->saddr || | |
1169 | iph_check->daddr != iph->daddr) | |
1170 | continue; | |
1171 | ||
1172 | seglen = ntohs(iph_check->tot_len) - | |
1173 | (4 * iph_check->ihl); | |
1174 | } else if (iph_check->version == 6) { | |
1175 | ipv6h = (struct ipv6hdr *)iph; | |
1176 | ipv6h_check = (struct ipv6hdr *)iph_check; | |
1177 | ||
1178 | if (ipv6_addr_cmp(&ipv6h_check->saddr, &ipv6h->saddr) || | |
1179 | ipv6_addr_cmp(&ipv6h_check->daddr, &ipv6h->daddr)) | |
1180 | continue; | |
1181 | ||
1182 | seglen = ntohs(ipv6h_check->payload_len); | |
1183 | } else { | |
1184 | WARN_ON(1); /* shouldn't happen */ | |
1185 | continue; | |
1186 | } | |
1187 | ||
1188 | /* If the ECE/CWR flags changed from the previous eligible | |
1189 | * packet in the same flow, we should no longer be dropping that | |
1190 | * previous packet as this would lose information. | |
1191 | */ | |
1192 | if (elig_ack && (tcp_flag_word(tcph_check) & | |
1193 | (TCP_FLAG_ECE | TCP_FLAG_CWR)) != elig_flags) { | |
1194 | elig_ack = NULL; | |
1195 | elig_ack_prev = NULL; | |
1196 | num_found--; | |
1197 | } | |
1198 | ||
1199 | /* Check TCP options and flags, don't drop ACKs with segment | |
1200 | * data, and don't drop ACKs with a higher cumulative ACK | |
1201 | * counter than the triggering packet. Check ACK seqno here to | |
1202 | * avoid parsing SACK options of packets we are going to exclude | |
1203 | * anyway. | |
1204 | */ | |
1205 | if (!cake_tcph_may_drop(tcph_check, tstamp, tsecr) || | |
1206 | (seglen - __tcp_hdrlen(tcph_check)) != 0 || | |
1207 | after(ntohl(tcph_check->ack_seq), ntohl(tcph->ack_seq))) | |
1208 | continue; | |
1209 | ||
1210 | /* Check SACK options. The triggering packet must SACK more data | |
1211 | * than the ACK under consideration, or SACK the same range but | |
1212 | * have a larger cumulative ACK counter. The latter is a | |
1213 | * pathological case, but is contained in the following check | |
1214 | * anyway, just to be safe. | |
1215 | */ | |
1216 | sack_comp = cake_tcph_sack_compare(tcph_check, tcph); | |
1217 | ||
1218 | if (sack_comp < 0 || | |
1219 | (ntohl(tcph_check->ack_seq) == ntohl(tcph->ack_seq) && | |
1220 | sack_comp == 0)) | |
1221 | continue; | |
1222 | ||
1223 | /* At this point we have found an eligible pure ACK to drop; if | |
1224 | * we are in aggressive mode, we are done. Otherwise, keep | |
1225 | * searching unless this is the second eligible ACK we | |
1226 | * found. | |
1227 | * | |
1228 | * Since we want to drop ACK closest to the head of the queue, | |
1229 | * save the first eligible ACK we find, even if we need to loop | |
1230 | * again. | |
1231 | */ | |
1232 | if (!elig_ack) { | |
1233 | elig_ack = skb_check; | |
1234 | elig_ack_prev = skb_prev; | |
1235 | elig_flags = (tcp_flag_word(tcph_check) | |
1236 | & (TCP_FLAG_ECE | TCP_FLAG_CWR)); | |
1237 | } | |
1238 | ||
1239 | if (num_found++ > 0) | |
1240 | goto found; | |
1241 | } | |
1242 | ||
1243 | /* We made it through the queue without finding two eligible ACKs . If | |
1244 | * we found a single eligible ACK we can drop it in aggressive mode if | |
1245 | * we can guarantee that this does not interfere with ECN flag | |
1246 | * information. We ensure this by dropping it only if the enqueued | |
1247 | * packet is consecutive with the eligible ACK, and their flags match. | |
1248 | */ | |
1249 | if (elig_ack && aggressive && elig_ack->next == skb && | |
1250 | (elig_flags == (tcp_flag_word(tcph) & | |
1251 | (TCP_FLAG_ECE | TCP_FLAG_CWR)))) | |
1252 | goto found; | |
1253 | ||
1254 | return NULL; | |
1255 | ||
1256 | found: | |
1257 | if (elig_ack_prev) | |
1258 | elig_ack_prev->next = elig_ack->next; | |
1259 | else | |
1260 | flow->head = elig_ack->next; | |
1261 | ||
a8305bff | 1262 | skb_mark_not_on_list(elig_ack); |
8b713881 THJ |
1263 | |
1264 | return elig_ack; | |
1265 | } | |
1266 | ||
046f6fd5 THJ |
1267 | static u64 cake_ewma(u64 avg, u64 sample, u32 shift) |
1268 | { | |
1269 | avg -= avg >> shift; | |
1270 | avg += sample >> shift; | |
1271 | return avg; | |
1272 | } | |
1273 | ||
a729b7f0 THJ |
1274 | static u32 cake_calc_overhead(struct cake_sched_data *q, u32 len, u32 off) |
1275 | { | |
1276 | if (q->rate_flags & CAKE_FLAG_OVERHEAD) | |
1277 | len -= off; | |
1278 | ||
1279 | if (q->max_netlen < len) | |
1280 | q->max_netlen = len; | |
1281 | if (q->min_netlen > len) | |
1282 | q->min_netlen = len; | |
1283 | ||
1284 | len += q->rate_overhead; | |
1285 | ||
1286 | if (len < q->rate_mpu) | |
1287 | len = q->rate_mpu; | |
1288 | ||
1289 | if (q->atm_mode == CAKE_ATM_ATM) { | |
1290 | len += 47; | |
1291 | len /= 48; | |
1292 | len *= 53; | |
1293 | } else if (q->atm_mode == CAKE_ATM_PTM) { | |
1294 | /* Add one byte per 64 bytes or part thereof. | |
1295 | * This is conservative and easier to calculate than the | |
1296 | * precise value. | |
1297 | */ | |
1298 | len += (len + 63) / 64; | |
1299 | } | |
1300 | ||
1301 | if (q->max_adjlen < len) | |
1302 | q->max_adjlen = len; | |
1303 | if (q->min_adjlen > len) | |
1304 | q->min_adjlen = len; | |
1305 | ||
1306 | return len; | |
1307 | } | |
1308 | ||
1309 | static u32 cake_overhead(struct cake_sched_data *q, const struct sk_buff *skb) | |
1310 | { | |
1311 | const struct skb_shared_info *shinfo = skb_shinfo(skb); | |
1312 | unsigned int hdr_len, last_len = 0; | |
1313 | u32 off = skb_network_offset(skb); | |
1314 | u32 len = qdisc_pkt_len(skb); | |
1315 | u16 segs = 1; | |
1316 | ||
1317 | q->avg_netoff = cake_ewma(q->avg_netoff, off << 16, 8); | |
1318 | ||
1319 | if (!shinfo->gso_size) | |
1320 | return cake_calc_overhead(q, len, off); | |
1321 | ||
1322 | /* borrowed from qdisc_pkt_len_init() */ | |
1323 | hdr_len = skb_transport_header(skb) - skb_mac_header(skb); | |
1324 | ||
1325 | /* + transport layer */ | |
1326 | if (likely(shinfo->gso_type & (SKB_GSO_TCPV4 | | |
1327 | SKB_GSO_TCPV6))) { | |
1328 | const struct tcphdr *th; | |
1329 | struct tcphdr _tcphdr; | |
1330 | ||
1331 | th = skb_header_pointer(skb, skb_transport_offset(skb), | |
1332 | sizeof(_tcphdr), &_tcphdr); | |
1333 | if (likely(th)) | |
1334 | hdr_len += __tcp_hdrlen(th); | |
1335 | } else { | |
1336 | struct udphdr _udphdr; | |
1337 | ||
1338 | if (skb_header_pointer(skb, skb_transport_offset(skb), | |
1339 | sizeof(_udphdr), &_udphdr)) | |
1340 | hdr_len += sizeof(struct udphdr); | |
1341 | } | |
1342 | ||
1343 | if (unlikely(shinfo->gso_type & SKB_GSO_DODGY)) | |
1344 | segs = DIV_ROUND_UP(skb->len - hdr_len, | |
1345 | shinfo->gso_size); | |
1346 | else | |
1347 | segs = shinfo->gso_segs; | |
1348 | ||
1349 | len = shinfo->gso_size + hdr_len; | |
1350 | last_len = skb->len - shinfo->gso_size * (segs - 1); | |
1351 | ||
1352 | return (cake_calc_overhead(q, len, off) * (segs - 1) + | |
1353 | cake_calc_overhead(q, last_len, off)); | |
1354 | } | |
1355 | ||
046f6fd5 THJ |
1356 | static void cake_heap_swap(struct cake_sched_data *q, u16 i, u16 j) |
1357 | { | |
1358 | struct cake_heap_entry ii = q->overflow_heap[i]; | |
1359 | struct cake_heap_entry jj = q->overflow_heap[j]; | |
1360 | ||
1361 | q->overflow_heap[i] = jj; | |
1362 | q->overflow_heap[j] = ii; | |
1363 | ||
1364 | q->tins[ii.t].overflow_idx[ii.b] = j; | |
1365 | q->tins[jj.t].overflow_idx[jj.b] = i; | |
1366 | } | |
1367 | ||
1368 | static u32 cake_heap_get_backlog(const struct cake_sched_data *q, u16 i) | |
1369 | { | |
1370 | struct cake_heap_entry ii = q->overflow_heap[i]; | |
1371 | ||
1372 | return q->tins[ii.t].backlogs[ii.b]; | |
1373 | } | |
1374 | ||
1375 | static void cake_heapify(struct cake_sched_data *q, u16 i) | |
1376 | { | |
1377 | static const u32 a = CAKE_MAX_TINS * CAKE_QUEUES; | |
1378 | u32 mb = cake_heap_get_backlog(q, i); | |
1379 | u32 m = i; | |
1380 | ||
1381 | while (m < a) { | |
1382 | u32 l = m + m + 1; | |
1383 | u32 r = l + 1; | |
1384 | ||
1385 | if (l < a) { | |
1386 | u32 lb = cake_heap_get_backlog(q, l); | |
1387 | ||
1388 | if (lb > mb) { | |
1389 | m = l; | |
1390 | mb = lb; | |
1391 | } | |
1392 | } | |
1393 | ||
1394 | if (r < a) { | |
1395 | u32 rb = cake_heap_get_backlog(q, r); | |
1396 | ||
1397 | if (rb > mb) { | |
1398 | m = r; | |
1399 | mb = rb; | |
1400 | } | |
1401 | } | |
1402 | ||
1403 | if (m != i) { | |
1404 | cake_heap_swap(q, i, m); | |
1405 | i = m; | |
1406 | } else { | |
1407 | break; | |
1408 | } | |
1409 | } | |
1410 | } | |
1411 | ||
1412 | static void cake_heapify_up(struct cake_sched_data *q, u16 i) | |
1413 | { | |
1414 | while (i > 0 && i < CAKE_MAX_TINS * CAKE_QUEUES) { | |
1415 | u16 p = (i - 1) >> 1; | |
1416 | u32 ib = cake_heap_get_backlog(q, i); | |
1417 | u32 pb = cake_heap_get_backlog(q, p); | |
1418 | ||
1419 | if (ib > pb) { | |
1420 | cake_heap_swap(q, i, p); | |
1421 | i = p; | |
1422 | } else { | |
1423 | break; | |
1424 | } | |
1425 | } | |
1426 | } | |
1427 | ||
1428 | static int cake_advance_shaper(struct cake_sched_data *q, | |
1429 | struct cake_tin_data *b, | |
1430 | struct sk_buff *skb, | |
1431 | ktime_t now, bool drop) | |
1432 | { | |
a729b7f0 | 1433 | u32 len = get_cobalt_cb(skb)->adjusted_len; |
046f6fd5 THJ |
1434 | |
1435 | /* charge packet bandwidth to this tin | |
1436 | * and to the global shaper. | |
1437 | */ | |
1438 | if (q->rate_ns) { | |
1439 | u64 tin_dur = (len * b->tin_rate_ns) >> b->tin_rate_shft; | |
1440 | u64 global_dur = (len * q->rate_ns) >> q->rate_shft; | |
1441 | u64 failsafe_dur = global_dur + (global_dur >> 1); | |
1442 | ||
1443 | if (ktime_before(b->time_next_packet, now)) | |
1444 | b->time_next_packet = ktime_add_ns(b->time_next_packet, | |
1445 | tin_dur); | |
1446 | ||
1447 | else if (ktime_before(b->time_next_packet, | |
1448 | ktime_add_ns(now, tin_dur))) | |
1449 | b->time_next_packet = ktime_add_ns(now, tin_dur); | |
1450 | ||
1451 | q->time_next_packet = ktime_add_ns(q->time_next_packet, | |
1452 | global_dur); | |
1453 | if (!drop) | |
1454 | q->failsafe_next_packet = \ | |
1455 | ktime_add_ns(q->failsafe_next_packet, | |
1456 | failsafe_dur); | |
1457 | } | |
1458 | return len; | |
1459 | } | |
1460 | ||
1461 | static unsigned int cake_drop(struct Qdisc *sch, struct sk_buff **to_free) | |
1462 | { | |
1463 | struct cake_sched_data *q = qdisc_priv(sch); | |
1464 | ktime_t now = ktime_get(); | |
1465 | u32 idx = 0, tin = 0, len; | |
1466 | struct cake_heap_entry qq; | |
1467 | struct cake_tin_data *b; | |
1468 | struct cake_flow *flow; | |
1469 | struct sk_buff *skb; | |
1470 | ||
1471 | if (!q->overflow_timeout) { | |
1472 | int i; | |
1473 | /* Build fresh max-heap */ | |
1474 | for (i = CAKE_MAX_TINS * CAKE_QUEUES / 2; i >= 0; i--) | |
1475 | cake_heapify(q, i); | |
1476 | } | |
1477 | q->overflow_timeout = 65535; | |
1478 | ||
1479 | /* select longest queue for pruning */ | |
1480 | qq = q->overflow_heap[0]; | |
1481 | tin = qq.t; | |
1482 | idx = qq.b; | |
1483 | ||
1484 | b = &q->tins[tin]; | |
1485 | flow = &b->flows[idx]; | |
1486 | skb = dequeue_head(flow); | |
1487 | if (unlikely(!skb)) { | |
1488 | /* heap has gone wrong, rebuild it next time */ | |
1489 | q->overflow_timeout = 0; | |
1490 | return idx + (tin << 16); | |
1491 | } | |
1492 | ||
1493 | if (cobalt_queue_full(&flow->cvars, &b->cparams, now)) | |
1494 | b->unresponsive_flow_count++; | |
1495 | ||
1496 | len = qdisc_pkt_len(skb); | |
1497 | q->buffer_used -= skb->truesize; | |
1498 | b->backlogs[idx] -= len; | |
1499 | b->tin_backlog -= len; | |
1500 | sch->qstats.backlog -= len; | |
1501 | qdisc_tree_reduce_backlog(sch, 1, len); | |
1502 | ||
1503 | flow->dropped++; | |
1504 | b->tin_dropped++; | |
1505 | sch->qstats.drops++; | |
1506 | ||
7298de9c THJ |
1507 | if (q->rate_flags & CAKE_FLAG_INGRESS) |
1508 | cake_advance_shaper(q, b, skb, now, true); | |
1509 | ||
046f6fd5 THJ |
1510 | __qdisc_drop(skb, to_free); |
1511 | sch->q.qlen--; | |
1512 | ||
1513 | cake_heapify(q, 0); | |
1514 | ||
1515 | return idx + (tin << 16); | |
1516 | } | |
1517 | ||
83f8fd69 THJ |
1518 | static u8 cake_handle_diffserv(struct sk_buff *skb, u16 wash) |
1519 | { | |
1520 | u8 dscp; | |
1521 | ||
1522 | switch (skb->protocol) { | |
1523 | case htons(ETH_P_IP): | |
1524 | dscp = ipv4_get_dsfield(ip_hdr(skb)) >> 2; | |
1525 | if (wash && dscp) | |
1526 | ipv4_change_dsfield(ip_hdr(skb), INET_ECN_MASK, 0); | |
1527 | return dscp; | |
1528 | ||
1529 | case htons(ETH_P_IPV6): | |
1530 | dscp = ipv6_get_dsfield(ipv6_hdr(skb)) >> 2; | |
1531 | if (wash && dscp) | |
1532 | ipv6_change_dsfield(ipv6_hdr(skb), INET_ECN_MASK, 0); | |
1533 | return dscp; | |
1534 | ||
1535 | case htons(ETH_P_ARP): | |
1536 | return 0x38; /* CS7 - Net Control */ | |
1537 | ||
1538 | default: | |
1539 | /* If there is no Diffserv field, treat as best-effort */ | |
1540 | return 0; | |
1541 | } | |
1542 | } | |
1543 | ||
1544 | static struct cake_tin_data *cake_select_tin(struct Qdisc *sch, | |
1545 | struct sk_buff *skb) | |
1546 | { | |
1547 | struct cake_sched_data *q = qdisc_priv(sch); | |
eab2fc82 | 1548 | u32 tin, mark; |
4976e3c6 | 1549 | u8 dscp; |
83f8fd69 | 1550 | |
4976e3c6 THJ |
1551 | /* Tin selection: Default to diffserv-based selection, allow overriding |
1552 | * using firewall marks or skb->priority. | |
1553 | */ | |
1554 | dscp = cake_handle_diffserv(skb, | |
1555 | q->rate_flags & CAKE_FLAG_WASH); | |
eab2fc82 | 1556 | mark = (skb->mark & q->fwmark_mask) >> q->fwmark_shft; |
83f8fd69 | 1557 | |
4976e3c6 | 1558 | if (q->tin_mode == CAKE_DIFFSERV_BESTEFFORT) |
83f8fd69 | 1559 | tin = 0; |
4976e3c6 | 1560 | |
eab2fc82 THJ |
1561 | else if (mark && mark <= q->tin_cnt) |
1562 | tin = q->tin_order[mark - 1]; | |
4976e3c6 THJ |
1563 | |
1564 | else if (TC_H_MAJ(skb->priority) == sch->handle && | |
1565 | TC_H_MIN(skb->priority) > 0 && | |
1566 | TC_H_MIN(skb->priority) <= q->tin_cnt) | |
1567 | tin = q->tin_order[TC_H_MIN(skb->priority) - 1]; | |
1568 | ||
1569 | else { | |
1570 | tin = q->tin_index[dscp]; | |
1571 | ||
1572 | if (unlikely(tin >= q->tin_cnt)) | |
1573 | tin = 0; | |
83f8fd69 THJ |
1574 | } |
1575 | ||
1576 | return &q->tins[tin]; | |
1577 | } | |
1578 | ||
1579 | static u32 cake_classify(struct Qdisc *sch, struct cake_tin_data **t, | |
046f6fd5 THJ |
1580 | struct sk_buff *skb, int flow_mode, int *qerr) |
1581 | { | |
1582 | struct cake_sched_data *q = qdisc_priv(sch); | |
1583 | struct tcf_proto *filter; | |
1584 | struct tcf_result res; | |
93cfb6c1 | 1585 | u16 flow = 0, host = 0; |
046f6fd5 THJ |
1586 | int result; |
1587 | ||
1588 | filter = rcu_dereference_bh(q->filter_list); | |
1589 | if (!filter) | |
83f8fd69 | 1590 | goto hash; |
046f6fd5 THJ |
1591 | |
1592 | *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS; | |
1593 | result = tcf_classify(skb, filter, &res, false); | |
83f8fd69 | 1594 | |
046f6fd5 THJ |
1595 | if (result >= 0) { |
1596 | #ifdef CONFIG_NET_CLS_ACT | |
1597 | switch (result) { | |
1598 | case TC_ACT_STOLEN: | |
1599 | case TC_ACT_QUEUED: | |
1600 | case TC_ACT_TRAP: | |
1601 | *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN; | |
1602 | /* fall through */ | |
1603 | case TC_ACT_SHOT: | |
1604 | return 0; | |
1605 | } | |
1606 | #endif | |
1607 | if (TC_H_MIN(res.classid) <= CAKE_QUEUES) | |
83f8fd69 | 1608 | flow = TC_H_MIN(res.classid); |
93cfb6c1 THJ |
1609 | if (TC_H_MAJ(res.classid) <= (CAKE_QUEUES << 16)) |
1610 | host = TC_H_MAJ(res.classid) >> 16; | |
046f6fd5 | 1611 | } |
83f8fd69 THJ |
1612 | hash: |
1613 | *t = cake_select_tin(sch, skb); | |
93cfb6c1 | 1614 | return cake_hash(*t, skb, flow_mode, flow, host) + 1; |
046f6fd5 THJ |
1615 | } |
1616 | ||
7298de9c THJ |
1617 | static void cake_reconfigure(struct Qdisc *sch); |
1618 | ||
046f6fd5 THJ |
1619 | static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch, |
1620 | struct sk_buff **to_free) | |
1621 | { | |
1622 | struct cake_sched_data *q = qdisc_priv(sch); | |
1623 | int len = qdisc_pkt_len(skb); | |
1624 | int uninitialized_var(ret); | |
8b713881 | 1625 | struct sk_buff *ack = NULL; |
046f6fd5 THJ |
1626 | ktime_t now = ktime_get(); |
1627 | struct cake_tin_data *b; | |
1628 | struct cake_flow *flow; | |
83f8fd69 | 1629 | u32 idx; |
046f6fd5 THJ |
1630 | |
1631 | /* choose flow to insert into */ | |
83f8fd69 | 1632 | idx = cake_classify(sch, &b, skb, q->flow_mode, &ret); |
046f6fd5 THJ |
1633 | if (idx == 0) { |
1634 | if (ret & __NET_XMIT_BYPASS) | |
1635 | qdisc_qstats_drop(sch); | |
1636 | __qdisc_drop(skb, to_free); | |
1637 | return ret; | |
1638 | } | |
1639 | idx--; | |
1640 | flow = &b->flows[idx]; | |
1641 | ||
1642 | /* ensure shaper state isn't stale */ | |
1643 | if (!b->tin_backlog) { | |
1644 | if (ktime_before(b->time_next_packet, now)) | |
1645 | b->time_next_packet = now; | |
1646 | ||
1647 | if (!sch->q.qlen) { | |
1648 | if (ktime_before(q->time_next_packet, now)) { | |
1649 | q->failsafe_next_packet = now; | |
1650 | q->time_next_packet = now; | |
1651 | } else if (ktime_after(q->time_next_packet, now) && | |
1652 | ktime_after(q->failsafe_next_packet, now)) { | |
1653 | u64 next = \ | |
1654 | min(ktime_to_ns(q->time_next_packet), | |
1655 | ktime_to_ns( | |
1656 | q->failsafe_next_packet)); | |
1657 | sch->qstats.overlimits++; | |
1658 | qdisc_watchdog_schedule_ns(&q->watchdog, next); | |
1659 | } | |
1660 | } | |
1661 | } | |
1662 | ||
1663 | if (unlikely(len > b->max_skblen)) | |
1664 | b->max_skblen = len; | |
1665 | ||
0c850344 THJ |
1666 | if (skb_is_gso(skb) && q->rate_flags & CAKE_FLAG_SPLIT_GSO) { |
1667 | struct sk_buff *segs, *nskb; | |
1668 | netdev_features_t features = netif_skb_features(skb); | |
8c6c37fd | 1669 | unsigned int slen = 0, numsegs = 0; |
0c850344 THJ |
1670 | |
1671 | segs = skb_gso_segment(skb, features & ~NETIF_F_GSO_MASK); | |
1672 | if (IS_ERR_OR_NULL(segs)) | |
1673 | return qdisc_drop(skb, sch, to_free); | |
1674 | ||
1675 | while (segs) { | |
1676 | nskb = segs->next; | |
a8305bff | 1677 | skb_mark_not_on_list(segs); |
0c850344 THJ |
1678 | qdisc_skb_cb(segs)->pkt_len = segs->len; |
1679 | cobalt_set_enqueue_time(segs, now); | |
1680 | get_cobalt_cb(segs)->adjusted_len = cake_overhead(q, | |
1681 | segs); | |
1682 | flow_queue_add(flow, segs); | |
1683 | ||
1684 | sch->q.qlen++; | |
8c6c37fd | 1685 | numsegs++; |
0c850344 THJ |
1686 | slen += segs->len; |
1687 | q->buffer_used += segs->truesize; | |
1688 | b->packets++; | |
1689 | segs = nskb; | |
1690 | } | |
8b713881 | 1691 | |
0c850344 THJ |
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; | |
8b713881 | 1698 | |
8c6c37fd | 1699 | qdisc_tree_reduce_backlog(sch, 1-numsegs, len-slen); |
0c850344 | 1700 | consume_skb(skb); |
8b713881 | 1701 | } else { |
0c850344 THJ |
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); | |
1706 | ||
1707 | if (q->ack_filter) | |
1708 | ack = cake_ack_filter(q, flow); | |
1709 | ||
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); | |
1718 | ||
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 | } | |
046f6fd5 | 1725 | |
0c850344 THJ |
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 | } | |
046f6fd5 THJ |
1734 | |
1735 | if (q->overflow_timeout) | |
1736 | cake_heapify_up(q, b->overflow_idx[idx]); | |
1737 | ||
1738 | /* incoming bandwidth capacity estimate */ | |
7298de9c THJ |
1739 | if (q->rate_flags & CAKE_FLAG_AUTORATE_INGRESS) { |
1740 | u64 packet_interval = \ | |
1741 | ktime_to_ns(ktime_sub(now, q->last_packet_time)); | |
1742 | ||
1743 | if (packet_interval > NSEC_PER_SEC) | |
1744 | packet_interval = NSEC_PER_SEC; | |
1745 | ||
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)); | |
1752 | ||
1753 | q->last_packet_time = now; | |
1754 | ||
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; | |
1760 | ||
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; | |
1767 | ||
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 | } | |
046f6fd5 THJ |
1779 | |
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; | |
1785 | ||
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++; | |
1794 | ||
1795 | if (cake_dsrc(q->flow_mode)) | |
71263992 | 1796 | host_load = max(host_load, srchost->srchost_bulk_flow_count); |
046f6fd5 THJ |
1797 | |
1798 | if (cake_ddst(q->flow_mode)) | |
71263992 | 1799 | host_load = max(host_load, dsthost->dsthost_bulk_flow_count); |
046f6fd5 THJ |
1800 | |
1801 | flow->deficit = (b->flow_quantum * | |
1802 | quantum_div[host_load]) >> 16; | |
1803 | } else if (flow->set == CAKE_SET_SPARSE_WAIT) { | |
71263992 GA |
1804 | struct cake_host *srchost = &b->hosts[flow->srchost]; |
1805 | struct cake_host *dsthost = &b->hosts[flow->dsthost]; | |
1806 | ||
046f6fd5 THJ |
1807 | /* this flow was empty, accounted as a sparse flow, but actually |
1808 | * in the bulk rotation. | |
1809 | */ | |
1810 | flow->set = CAKE_SET_BULK; | |
1811 | b->sparse_flow_count--; | |
1812 | b->bulk_flow_count++; | |
71263992 GA |
1813 | |
1814 | if (cake_dsrc(q->flow_mode)) | |
1815 | srchost->srchost_bulk_flow_count++; | |
1816 | ||
1817 | if (cake_ddst(q->flow_mode)) | |
1818 | dsthost->dsthost_bulk_flow_count++; | |
1819 | ||
046f6fd5 THJ |
1820 | } |
1821 | ||
1822 | if (q->buffer_used > q->buffer_max_used) | |
1823 | q->buffer_max_used = q->buffer_used; | |
1824 | ||
1825 | if (q->buffer_used > q->buffer_limit) { | |
1826 | u32 dropped = 0; | |
1827 | ||
1828 | while (q->buffer_used > q->buffer_limit) { | |
1829 | dropped++; | |
1830 | cake_drop(sch, to_free); | |
1831 | } | |
1832 | b->drop_overlimit += dropped; | |
1833 | } | |
1834 | return NET_XMIT_SUCCESS; | |
1835 | } | |
1836 | ||
1837 | static struct sk_buff *cake_dequeue_one(struct Qdisc *sch) | |
1838 | { | |
1839 | struct cake_sched_data *q = qdisc_priv(sch); | |
1840 | struct cake_tin_data *b = &q->tins[q->cur_tin]; | |
1841 | struct cake_flow *flow = &b->flows[q->cur_flow]; | |
1842 | struct sk_buff *skb = NULL; | |
1843 | u32 len; | |
1844 | ||
1845 | if (flow->head) { | |
1846 | skb = dequeue_head(flow); | |
1847 | len = qdisc_pkt_len(skb); | |
1848 | b->backlogs[q->cur_flow] -= len; | |
1849 | b->tin_backlog -= len; | |
1850 | sch->qstats.backlog -= len; | |
1851 | q->buffer_used -= skb->truesize; | |
1852 | sch->q.qlen--; | |
1853 | ||
1854 | if (q->overflow_timeout) | |
1855 | cake_heapify(q, b->overflow_idx[q->cur_flow]); | |
1856 | } | |
1857 | return skb; | |
1858 | } | |
1859 | ||
1860 | /* Discard leftover packets from a tin no longer in use. */ | |
1861 | static void cake_clear_tin(struct Qdisc *sch, u16 tin) | |
1862 | { | |
1863 | struct cake_sched_data *q = qdisc_priv(sch); | |
1864 | struct sk_buff *skb; | |
1865 | ||
1866 | q->cur_tin = tin; | |
1867 | for (q->cur_flow = 0; q->cur_flow < CAKE_QUEUES; q->cur_flow++) | |
1868 | while (!!(skb = cake_dequeue_one(sch))) | |
1869 | kfree_skb(skb); | |
1870 | } | |
1871 | ||
1872 | static struct sk_buff *cake_dequeue(struct Qdisc *sch) | |
1873 | { | |
1874 | struct cake_sched_data *q = qdisc_priv(sch); | |
1875 | struct cake_tin_data *b = &q->tins[q->cur_tin]; | |
1876 | struct cake_host *srchost, *dsthost; | |
1877 | ktime_t now = ktime_get(); | |
1878 | struct cake_flow *flow; | |
1879 | struct list_head *head; | |
1880 | bool first_flow = true; | |
1881 | struct sk_buff *skb; | |
1882 | u16 host_load; | |
1883 | u64 delay; | |
1884 | u32 len; | |
1885 | ||
1886 | begin: | |
1887 | if (!sch->q.qlen) | |
1888 | return NULL; | |
1889 | ||
1890 | /* global hard shaper */ | |
1891 | if (ktime_after(q->time_next_packet, now) && | |
1892 | ktime_after(q->failsafe_next_packet, now)) { | |
1893 | u64 next = min(ktime_to_ns(q->time_next_packet), | |
1894 | ktime_to_ns(q->failsafe_next_packet)); | |
1895 | ||
1896 | sch->qstats.overlimits++; | |
1897 | qdisc_watchdog_schedule_ns(&q->watchdog, next); | |
1898 | return NULL; | |
1899 | } | |
1900 | ||
1901 | /* Choose a class to work on. */ | |
1902 | if (!q->rate_ns) { | |
1903 | /* In unlimited mode, can't rely on shaper timings, just balance | |
1904 | * with DRR | |
1905 | */ | |
1906 | bool wrapped = false, empty = true; | |
1907 | ||
1908 | while (b->tin_deficit < 0 || | |
1909 | !(b->sparse_flow_count + b->bulk_flow_count)) { | |
1910 | if (b->tin_deficit <= 0) | |
1911 | b->tin_deficit += b->tin_quantum_band; | |
1912 | if (b->sparse_flow_count + b->bulk_flow_count) | |
1913 | empty = false; | |
1914 | ||
1915 | q->cur_tin++; | |
1916 | b++; | |
1917 | if (q->cur_tin >= q->tin_cnt) { | |
1918 | q->cur_tin = 0; | |
1919 | b = q->tins; | |
1920 | ||
1921 | if (wrapped) { | |
1922 | /* It's possible for q->qlen to be | |
1923 | * nonzero when we actually have no | |
1924 | * packets anywhere. | |
1925 | */ | |
1926 | if (empty) | |
1927 | return NULL; | |
1928 | } else { | |
1929 | wrapped = true; | |
1930 | } | |
1931 | } | |
1932 | } | |
1933 | } else { | |
1934 | /* In shaped mode, choose: | |
1935 | * - Highest-priority tin with queue and meeting schedule, or | |
1936 | * - The earliest-scheduled tin with queue. | |
1937 | */ | |
1938 | ktime_t best_time = KTIME_MAX; | |
1939 | int tin, best_tin = 0; | |
1940 | ||
1941 | for (tin = 0; tin < q->tin_cnt; tin++) { | |
1942 | b = q->tins + tin; | |
1943 | if ((b->sparse_flow_count + b->bulk_flow_count) > 0) { | |
1944 | ktime_t time_to_pkt = \ | |
1945 | ktime_sub(b->time_next_packet, now); | |
1946 | ||
1947 | if (ktime_to_ns(time_to_pkt) <= 0 || | |
1948 | ktime_compare(time_to_pkt, | |
1949 | best_time) <= 0) { | |
1950 | best_time = time_to_pkt; | |
1951 | best_tin = tin; | |
1952 | } | |
1953 | } | |
1954 | } | |
1955 | ||
1956 | q->cur_tin = best_tin; | |
1957 | b = q->tins + best_tin; | |
1958 | ||
1959 | /* No point in going further if no packets to deliver. */ | |
1960 | if (unlikely(!(b->sparse_flow_count + b->bulk_flow_count))) | |
1961 | return NULL; | |
1962 | } | |
1963 | ||
1964 | retry: | |
1965 | /* service this class */ | |
1966 | head = &b->decaying_flows; | |
1967 | if (!first_flow || list_empty(head)) { | |
1968 | head = &b->new_flows; | |
1969 | if (list_empty(head)) { | |
1970 | head = &b->old_flows; | |
1971 | if (unlikely(list_empty(head))) { | |
1972 | head = &b->decaying_flows; | |
1973 | if (unlikely(list_empty(head))) | |
1974 | goto begin; | |
1975 | } | |
1976 | } | |
1977 | } | |
1978 | flow = list_first_entry(head, struct cake_flow, flowchain); | |
1979 | q->cur_flow = flow - b->flows; | |
1980 | first_flow = false; | |
1981 | ||
1982 | /* triple isolation (modified DRR++) */ | |
1983 | srchost = &b->hosts[flow->srchost]; | |
1984 | dsthost = &b->hosts[flow->dsthost]; | |
1985 | host_load = 1; | |
1986 | ||
046f6fd5 THJ |
1987 | /* flow isolation (DRR++) */ |
1988 | if (flow->deficit <= 0) { | |
046f6fd5 THJ |
1989 | /* Keep all flows with deficits out of the sparse and decaying |
1990 | * rotations. No non-empty flow can go into the decaying | |
1991 | * rotation, so they can't get deficits | |
1992 | */ | |
1993 | if (flow->set == CAKE_SET_SPARSE) { | |
1994 | if (flow->head) { | |
1995 | b->sparse_flow_count--; | |
1996 | b->bulk_flow_count++; | |
71263992 GA |
1997 | |
1998 | if (cake_dsrc(q->flow_mode)) | |
1999 | srchost->srchost_bulk_flow_count++; | |
2000 | ||
2001 | if (cake_ddst(q->flow_mode)) | |
2002 | dsthost->dsthost_bulk_flow_count++; | |
2003 | ||
046f6fd5 THJ |
2004 | flow->set = CAKE_SET_BULK; |
2005 | } else { | |
2006 | /* we've moved it to the bulk rotation for | |
2007 | * correct deficit accounting but we still want | |
2008 | * to count it as a sparse flow, not a bulk one. | |
2009 | */ | |
2010 | flow->set = CAKE_SET_SPARSE_WAIT; | |
2011 | } | |
2012 | } | |
71263992 GA |
2013 | |
2014 | if (cake_dsrc(q->flow_mode)) | |
2015 | host_load = max(host_load, srchost->srchost_bulk_flow_count); | |
2016 | ||
2017 | if (cake_ddst(q->flow_mode)) | |
2018 | host_load = max(host_load, dsthost->dsthost_bulk_flow_count); | |
2019 | ||
2020 | WARN_ON(host_load > CAKE_QUEUES); | |
2021 | ||
2022 | /* The shifted prandom_u32() is a way to apply dithering to | |
2023 | * avoid accumulating roundoff errors | |
2024 | */ | |
2025 | flow->deficit += (b->flow_quantum * quantum_div[host_load] + | |
2026 | (prandom_u32() >> 16)) >> 16; | |
2027 | list_move_tail(&flow->flowchain, &b->old_flows); | |
2028 | ||
046f6fd5 THJ |
2029 | goto retry; |
2030 | } | |
2031 | ||
2032 | /* Retrieve a packet via the AQM */ | |
2033 | while (1) { | |
2034 | skb = cake_dequeue_one(sch); | |
2035 | if (!skb) { | |
2036 | /* this queue was actually empty */ | |
2037 | if (cobalt_queue_empty(&flow->cvars, &b->cparams, now)) | |
2038 | b->unresponsive_flow_count--; | |
2039 | ||
2040 | if (flow->cvars.p_drop || flow->cvars.count || | |
2041 | ktime_before(now, flow->cvars.drop_next)) { | |
2042 | /* keep in the flowchain until the state has | |
2043 | * decayed to rest | |
2044 | */ | |
2045 | list_move_tail(&flow->flowchain, | |
2046 | &b->decaying_flows); | |
2047 | if (flow->set == CAKE_SET_BULK) { | |
2048 | b->bulk_flow_count--; | |
71263992 GA |
2049 | |
2050 | if (cake_dsrc(q->flow_mode)) | |
2051 | srchost->srchost_bulk_flow_count--; | |
2052 | ||
2053 | if (cake_ddst(q->flow_mode)) | |
2054 | dsthost->dsthost_bulk_flow_count--; | |
2055 | ||
046f6fd5 THJ |
2056 | b->decaying_flow_count++; |
2057 | } else if (flow->set == CAKE_SET_SPARSE || | |
2058 | flow->set == CAKE_SET_SPARSE_WAIT) { | |
2059 | b->sparse_flow_count--; | |
2060 | b->decaying_flow_count++; | |
2061 | } | |
2062 | flow->set = CAKE_SET_DECAYING; | |
2063 | } else { | |
2064 | /* remove empty queue from the flowchain */ | |
2065 | list_del_init(&flow->flowchain); | |
2066 | if (flow->set == CAKE_SET_SPARSE || | |
2067 | flow->set == CAKE_SET_SPARSE_WAIT) | |
2068 | b->sparse_flow_count--; | |
71263992 | 2069 | else if (flow->set == CAKE_SET_BULK) { |
046f6fd5 | 2070 | b->bulk_flow_count--; |
71263992 GA |
2071 | |
2072 | if (cake_dsrc(q->flow_mode)) | |
2073 | srchost->srchost_bulk_flow_count--; | |
2074 | ||
2075 | if (cake_ddst(q->flow_mode)) | |
2076 | dsthost->dsthost_bulk_flow_count--; | |
2077 | ||
2078 | } else | |
046f6fd5 THJ |
2079 | b->decaying_flow_count--; |
2080 | ||
2081 | flow->set = CAKE_SET_NONE; | |
046f6fd5 THJ |
2082 | } |
2083 | goto begin; | |
2084 | } | |
2085 | ||
2086 | /* Last packet in queue may be marked, shouldn't be dropped */ | |
7298de9c THJ |
2087 | if (!cobalt_should_drop(&flow->cvars, &b->cparams, now, skb, |
2088 | (b->bulk_flow_count * | |
2089 | !!(q->rate_flags & | |
2090 | CAKE_FLAG_INGRESS))) || | |
046f6fd5 THJ |
2091 | !flow->head) |
2092 | break; | |
2093 | ||
7298de9c THJ |
2094 | /* drop this packet, get another one */ |
2095 | if (q->rate_flags & CAKE_FLAG_INGRESS) { | |
2096 | len = cake_advance_shaper(q, b, skb, | |
2097 | now, true); | |
2098 | flow->deficit -= len; | |
2099 | b->tin_deficit -= len; | |
2100 | } | |
046f6fd5 THJ |
2101 | flow->dropped++; |
2102 | b->tin_dropped++; | |
2103 | qdisc_tree_reduce_backlog(sch, 1, qdisc_pkt_len(skb)); | |
2104 | qdisc_qstats_drop(sch); | |
2105 | kfree_skb(skb); | |
7298de9c THJ |
2106 | if (q->rate_flags & CAKE_FLAG_INGRESS) |
2107 | goto retry; | |
046f6fd5 THJ |
2108 | } |
2109 | ||
2110 | b->tin_ecn_mark += !!flow->cvars.ecn_marked; | |
2111 | qdisc_bstats_update(sch, skb); | |
2112 | ||
2113 | /* collect delay stats */ | |
2114 | delay = ktime_to_ns(ktime_sub(now, cobalt_get_enqueue_time(skb))); | |
2115 | b->avge_delay = cake_ewma(b->avge_delay, delay, 8); | |
2116 | b->peak_delay = cake_ewma(b->peak_delay, delay, | |
2117 | delay > b->peak_delay ? 2 : 8); | |
2118 | b->base_delay = cake_ewma(b->base_delay, delay, | |
2119 | delay < b->base_delay ? 2 : 8); | |
2120 | ||
2121 | len = cake_advance_shaper(q, b, skb, now, false); | |
2122 | flow->deficit -= len; | |
2123 | b->tin_deficit -= len; | |
2124 | ||
2125 | if (ktime_after(q->time_next_packet, now) && sch->q.qlen) { | |
2126 | u64 next = min(ktime_to_ns(q->time_next_packet), | |
2127 | ktime_to_ns(q->failsafe_next_packet)); | |
2128 | ||
2129 | qdisc_watchdog_schedule_ns(&q->watchdog, next); | |
2130 | } else if (!sch->q.qlen) { | |
2131 | int i; | |
2132 | ||
2133 | for (i = 0; i < q->tin_cnt; i++) { | |
2134 | if (q->tins[i].decaying_flow_count) { | |
2135 | ktime_t next = \ | |
2136 | ktime_add_ns(now, | |
2137 | q->tins[i].cparams.target); | |
2138 | ||
2139 | qdisc_watchdog_schedule_ns(&q->watchdog, | |
2140 | ktime_to_ns(next)); | |
2141 | break; | |
2142 | } | |
2143 | } | |
2144 | } | |
2145 | ||
2146 | if (q->overflow_timeout) | |
2147 | q->overflow_timeout--; | |
2148 | ||
2149 | return skb; | |
2150 | } | |
2151 | ||
2152 | static void cake_reset(struct Qdisc *sch) | |
2153 | { | |
2154 | u32 c; | |
2155 | ||
2156 | for (c = 0; c < CAKE_MAX_TINS; c++) | |
2157 | cake_clear_tin(sch, c); | |
2158 | } | |
2159 | ||
2160 | static const struct nla_policy cake_policy[TCA_CAKE_MAX + 1] = { | |
2161 | [TCA_CAKE_BASE_RATE64] = { .type = NLA_U64 }, | |
2162 | [TCA_CAKE_DIFFSERV_MODE] = { .type = NLA_U32 }, | |
2163 | [TCA_CAKE_ATM] = { .type = NLA_U32 }, | |
2164 | [TCA_CAKE_FLOW_MODE] = { .type = NLA_U32 }, | |
2165 | [TCA_CAKE_OVERHEAD] = { .type = NLA_S32 }, | |
2166 | [TCA_CAKE_RTT] = { .type = NLA_U32 }, | |
2167 | [TCA_CAKE_TARGET] = { .type = NLA_U32 }, | |
2168 | [TCA_CAKE_AUTORATE] = { .type = NLA_U32 }, | |
2169 | [TCA_CAKE_MEMORY] = { .type = NLA_U32 }, | |
2170 | [TCA_CAKE_NAT] = { .type = NLA_U32 }, | |
2171 | [TCA_CAKE_RAW] = { .type = NLA_U32 }, | |
2172 | [TCA_CAKE_WASH] = { .type = NLA_U32 }, | |
2173 | [TCA_CAKE_MPU] = { .type = NLA_U32 }, | |
2174 | [TCA_CAKE_INGRESS] = { .type = NLA_U32 }, | |
2175 | [TCA_CAKE_ACK_FILTER] = { .type = NLA_U32 }, | |
eab2fc82 | 2176 | [TCA_CAKE_FWMARK] = { .type = NLA_U32 }, |
046f6fd5 THJ |
2177 | }; |
2178 | ||
2179 | static void cake_set_rate(struct cake_tin_data *b, u64 rate, u32 mtu, | |
2180 | u64 target_ns, u64 rtt_est_ns) | |
2181 | { | |
2182 | /* convert byte-rate into time-per-byte | |
2183 | * so it will always unwedge in reasonable time. | |
2184 | */ | |
2185 | static const u64 MIN_RATE = 64; | |
2186 | u32 byte_target = mtu; | |
2187 | u64 byte_target_ns; | |
2188 | u8 rate_shft = 0; | |
2189 | u64 rate_ns = 0; | |
2190 | ||
2191 | b->flow_quantum = 1514; | |
2192 | if (rate) { | |
2193 | b->flow_quantum = max(min(rate >> 12, 1514ULL), 300ULL); | |
2194 | rate_shft = 34; | |
2195 | rate_ns = ((u64)NSEC_PER_SEC) << rate_shft; | |
2196 | rate_ns = div64_u64(rate_ns, max(MIN_RATE, rate)); | |
2197 | while (!!(rate_ns >> 34)) { | |
2198 | rate_ns >>= 1; | |
2199 | rate_shft--; | |
2200 | } | |
2201 | } /* else unlimited, ie. zero delay */ | |
2202 | ||
2203 | b->tin_rate_bps = rate; | |
2204 | b->tin_rate_ns = rate_ns; | |
2205 | b->tin_rate_shft = rate_shft; | |
2206 | ||
2207 | byte_target_ns = (byte_target * rate_ns) >> rate_shft; | |
2208 | ||
2209 | b->cparams.target = max((byte_target_ns * 3) / 2, target_ns); | |
2210 | b->cparams.interval = max(rtt_est_ns + | |
2211 | b->cparams.target - target_ns, | |
2212 | b->cparams.target * 2); | |
2213 | b->cparams.mtu_time = byte_target_ns; | |
2214 | b->cparams.p_inc = 1 << 24; /* 1/256 */ | |
2215 | b->cparams.p_dec = 1 << 20; /* 1/4096 */ | |
2216 | } | |
2217 | ||
83f8fd69 | 2218 | static int cake_config_besteffort(struct Qdisc *sch) |
046f6fd5 THJ |
2219 | { |
2220 | struct cake_sched_data *q = qdisc_priv(sch); | |
2221 | struct cake_tin_data *b = &q->tins[0]; | |
83f8fd69 THJ |
2222 | u32 mtu = psched_mtu(qdisc_dev(sch)); |
2223 | u64 rate = q->rate_bps; | |
046f6fd5 THJ |
2224 | |
2225 | q->tin_cnt = 1; | |
83f8fd69 THJ |
2226 | |
2227 | q->tin_index = besteffort; | |
2228 | q->tin_order = normal_order; | |
2229 | ||
2230 | cake_set_rate(b, rate, mtu, | |
046f6fd5 THJ |
2231 | us_to_ns(q->target), us_to_ns(q->interval)); |
2232 | b->tin_quantum_band = 65535; | |
2233 | b->tin_quantum_prio = 65535; | |
2234 | ||
83f8fd69 THJ |
2235 | return 0; |
2236 | } | |
2237 | ||
2238 | static int cake_config_precedence(struct Qdisc *sch) | |
2239 | { | |
2240 | /* convert high-level (user visible) parameters into internal format */ | |
2241 | struct cake_sched_data *q = qdisc_priv(sch); | |
2242 | u32 mtu = psched_mtu(qdisc_dev(sch)); | |
2243 | u64 rate = q->rate_bps; | |
2244 | u32 quantum1 = 256; | |
2245 | u32 quantum2 = 256; | |
2246 | u32 i; | |
2247 | ||
2248 | q->tin_cnt = 8; | |
2249 | q->tin_index = precedence; | |
2250 | q->tin_order = normal_order; | |
2251 | ||
2252 | for (i = 0; i < q->tin_cnt; i++) { | |
2253 | struct cake_tin_data *b = &q->tins[i]; | |
2254 | ||
2255 | cake_set_rate(b, rate, mtu, us_to_ns(q->target), | |
2256 | us_to_ns(q->interval)); | |
2257 | ||
2258 | b->tin_quantum_prio = max_t(u16, 1U, quantum1); | |
2259 | b->tin_quantum_band = max_t(u16, 1U, quantum2); | |
2260 | ||
2261 | /* calculate next class's parameters */ | |
2262 | rate *= 7; | |
2263 | rate >>= 3; | |
2264 | ||
2265 | quantum1 *= 3; | |
2266 | quantum1 >>= 1; | |
2267 | ||
2268 | quantum2 *= 7; | |
2269 | quantum2 >>= 3; | |
2270 | } | |
2271 | ||
2272 | return 0; | |
2273 | } | |
2274 | ||
2275 | /* List of known Diffserv codepoints: | |
2276 | * | |
2277 | * Least Effort (CS1) | |
2278 | * Best Effort (CS0) | |
2279 | * Max Reliability & LLT "Lo" (TOS1) | |
2280 | * Max Throughput (TOS2) | |
2281 | * Min Delay (TOS4) | |
2282 | * LLT "La" (TOS5) | |
2283 | * Assured Forwarding 1 (AF1x) - x3 | |
2284 | * Assured Forwarding 2 (AF2x) - x3 | |
2285 | * Assured Forwarding 3 (AF3x) - x3 | |
2286 | * Assured Forwarding 4 (AF4x) - x3 | |
2287 | * Precedence Class 2 (CS2) | |
2288 | * Precedence Class 3 (CS3) | |
2289 | * Precedence Class 4 (CS4) | |
2290 | * Precedence Class 5 (CS5) | |
2291 | * Precedence Class 6 (CS6) | |
2292 | * Precedence Class 7 (CS7) | |
2293 | * Voice Admit (VA) | |
2294 | * Expedited Forwarding (EF) | |
2295 | ||
2296 | * Total 25 codepoints. | |
2297 | */ | |
2298 | ||
2299 | /* List of traffic classes in RFC 4594: | |
2300 | * (roughly descending order of contended priority) | |
2301 | * (roughly ascending order of uncontended throughput) | |
2302 | * | |
2303 | * Network Control (CS6,CS7) - routing traffic | |
2304 | * Telephony (EF,VA) - aka. VoIP streams | |
2305 | * Signalling (CS5) - VoIP setup | |
2306 | * Multimedia Conferencing (AF4x) - aka. video calls | |
2307 | * Realtime Interactive (CS4) - eg. games | |
2308 | * Multimedia Streaming (AF3x) - eg. YouTube, NetFlix, Twitch | |
2309 | * Broadcast Video (CS3) | |
2310 | * Low Latency Data (AF2x,TOS4) - eg. database | |
2311 | * Ops, Admin, Management (CS2,TOS1) - eg. ssh | |
2312 | * Standard Service (CS0 & unrecognised codepoints) | |
2313 | * High Throughput Data (AF1x,TOS2) - eg. web traffic | |
2314 | * Low Priority Data (CS1) - eg. BitTorrent | |
2315 | ||
2316 | * Total 12 traffic classes. | |
2317 | */ | |
2318 | ||
2319 | static int cake_config_diffserv8(struct Qdisc *sch) | |
2320 | { | |
2321 | /* Pruned list of traffic classes for typical applications: | |
2322 | * | |
2323 | * Network Control (CS6, CS7) | |
2324 | * Minimum Latency (EF, VA, CS5, CS4) | |
2325 | * Interactive Shell (CS2, TOS1) | |
2326 | * Low Latency Transactions (AF2x, TOS4) | |
2327 | * Video Streaming (AF4x, AF3x, CS3) | |
2328 | * Bog Standard (CS0 etc.) | |
2329 | * High Throughput (AF1x, TOS2) | |
2330 | * Background Traffic (CS1) | |
2331 | * | |
2332 | * Total 8 traffic classes. | |
2333 | */ | |
2334 | ||
2335 | struct cake_sched_data *q = qdisc_priv(sch); | |
2336 | u32 mtu = psched_mtu(qdisc_dev(sch)); | |
2337 | u64 rate = q->rate_bps; | |
2338 | u32 quantum1 = 256; | |
2339 | u32 quantum2 = 256; | |
2340 | u32 i; | |
2341 | ||
2342 | q->tin_cnt = 8; | |
2343 | ||
2344 | /* codepoint to class mapping */ | |
2345 | q->tin_index = diffserv8; | |
2346 | q->tin_order = normal_order; | |
2347 | ||
2348 | /* class characteristics */ | |
2349 | for (i = 0; i < q->tin_cnt; i++) { | |
2350 | struct cake_tin_data *b = &q->tins[i]; | |
2351 | ||
2352 | cake_set_rate(b, rate, mtu, us_to_ns(q->target), | |
2353 | us_to_ns(q->interval)); | |
2354 | ||
2355 | b->tin_quantum_prio = max_t(u16, 1U, quantum1); | |
2356 | b->tin_quantum_band = max_t(u16, 1U, quantum2); | |
2357 | ||
2358 | /* calculate next class's parameters */ | |
2359 | rate *= 7; | |
2360 | rate >>= 3; | |
2361 | ||
2362 | quantum1 *= 3; | |
2363 | quantum1 >>= 1; | |
2364 | ||
2365 | quantum2 *= 7; | |
2366 | quantum2 >>= 3; | |
2367 | } | |
2368 | ||
2369 | return 0; | |
2370 | } | |
2371 | ||
2372 | static int cake_config_diffserv4(struct Qdisc *sch) | |
2373 | { | |
2374 | /* Further pruned list of traffic classes for four-class system: | |
2375 | * | |
2376 | * Latency Sensitive (CS7, CS6, EF, VA, CS5, CS4) | |
2377 | * Streaming Media (AF4x, AF3x, CS3, AF2x, TOS4, CS2, TOS1) | |
2378 | * Best Effort (CS0, AF1x, TOS2, and those not specified) | |
2379 | * Background Traffic (CS1) | |
2380 | * | |
2381 | * Total 4 traffic classes. | |
2382 | */ | |
2383 | ||
2384 | struct cake_sched_data *q = qdisc_priv(sch); | |
2385 | u32 mtu = psched_mtu(qdisc_dev(sch)); | |
2386 | u64 rate = q->rate_bps; | |
2387 | u32 quantum = 1024; | |
2388 | ||
2389 | q->tin_cnt = 4; | |
2390 | ||
2391 | /* codepoint to class mapping */ | |
2392 | q->tin_index = diffserv4; | |
2393 | q->tin_order = bulk_order; | |
2394 | ||
2395 | /* class characteristics */ | |
2396 | cake_set_rate(&q->tins[0], rate, mtu, | |
2397 | us_to_ns(q->target), us_to_ns(q->interval)); | |
2398 | cake_set_rate(&q->tins[1], rate >> 4, mtu, | |
2399 | us_to_ns(q->target), us_to_ns(q->interval)); | |
2400 | cake_set_rate(&q->tins[2], rate >> 1, mtu, | |
2401 | us_to_ns(q->target), us_to_ns(q->interval)); | |
2402 | cake_set_rate(&q->tins[3], rate >> 2, mtu, | |
2403 | us_to_ns(q->target), us_to_ns(q->interval)); | |
2404 | ||
2405 | /* priority weights */ | |
2406 | q->tins[0].tin_quantum_prio = quantum; | |
2407 | q->tins[1].tin_quantum_prio = quantum >> 4; | |
2408 | q->tins[2].tin_quantum_prio = quantum << 2; | |
2409 | q->tins[3].tin_quantum_prio = quantum << 4; | |
2410 | ||
2411 | /* bandwidth-sharing weights */ | |
2412 | q->tins[0].tin_quantum_band = quantum; | |
2413 | q->tins[1].tin_quantum_band = quantum >> 4; | |
2414 | q->tins[2].tin_quantum_band = quantum >> 1; | |
2415 | q->tins[3].tin_quantum_band = quantum >> 2; | |
2416 | ||
2417 | return 0; | |
2418 | } | |
2419 | ||
2420 | static int cake_config_diffserv3(struct Qdisc *sch) | |
2421 | { | |
2422 | /* Simplified Diffserv structure with 3 tins. | |
2423 | * Low Priority (CS1) | |
2424 | * Best Effort | |
2425 | * Latency Sensitive (TOS4, VA, EF, CS6, CS7) | |
2426 | */ | |
2427 | struct cake_sched_data *q = qdisc_priv(sch); | |
2428 | u32 mtu = psched_mtu(qdisc_dev(sch)); | |
2429 | u64 rate = q->rate_bps; | |
2430 | u32 quantum = 1024; | |
2431 | ||
2432 | q->tin_cnt = 3; | |
2433 | ||
2434 | /* codepoint to class mapping */ | |
2435 | q->tin_index = diffserv3; | |
2436 | q->tin_order = bulk_order; | |
2437 | ||
2438 | /* class characteristics */ | |
2439 | cake_set_rate(&q->tins[0], rate, mtu, | |
2440 | us_to_ns(q->target), us_to_ns(q->interval)); | |
2441 | cake_set_rate(&q->tins[1], rate >> 4, mtu, | |
2442 | us_to_ns(q->target), us_to_ns(q->interval)); | |
2443 | cake_set_rate(&q->tins[2], rate >> 2, mtu, | |
2444 | us_to_ns(q->target), us_to_ns(q->interval)); | |
2445 | ||
2446 | /* priority weights */ | |
2447 | q->tins[0].tin_quantum_prio = quantum; | |
2448 | q->tins[1].tin_quantum_prio = quantum >> 4; | |
2449 | q->tins[2].tin_quantum_prio = quantum << 4; | |
2450 | ||
2451 | /* bandwidth-sharing weights */ | |
2452 | q->tins[0].tin_quantum_band = quantum; | |
2453 | q->tins[1].tin_quantum_band = quantum >> 4; | |
2454 | q->tins[2].tin_quantum_band = quantum >> 2; | |
2455 | ||
2456 | return 0; | |
2457 | } | |
2458 | ||
2459 | static void cake_reconfigure(struct Qdisc *sch) | |
2460 | { | |
2461 | struct cake_sched_data *q = qdisc_priv(sch); | |
2462 | int c, ft; | |
2463 | ||
2464 | switch (q->tin_mode) { | |
2465 | case CAKE_DIFFSERV_BESTEFFORT: | |
2466 | ft = cake_config_besteffort(sch); | |
2467 | break; | |
2468 | ||
2469 | case CAKE_DIFFSERV_PRECEDENCE: | |
2470 | ft = cake_config_precedence(sch); | |
2471 | break; | |
2472 | ||
2473 | case CAKE_DIFFSERV_DIFFSERV8: | |
2474 | ft = cake_config_diffserv8(sch); | |
2475 | break; | |
2476 | ||
2477 | case CAKE_DIFFSERV_DIFFSERV4: | |
2478 | ft = cake_config_diffserv4(sch); | |
2479 | break; | |
2480 | ||
2481 | case CAKE_DIFFSERV_DIFFSERV3: | |
2482 | default: | |
2483 | ft = cake_config_diffserv3(sch); | |
2484 | break; | |
2485 | } | |
2486 | ||
046f6fd5 THJ |
2487 | for (c = q->tin_cnt; c < CAKE_MAX_TINS; c++) { |
2488 | cake_clear_tin(sch, c); | |
2489 | q->tins[c].cparams.mtu_time = q->tins[ft].cparams.mtu_time; | |
2490 | } | |
2491 | ||
2492 | q->rate_ns = q->tins[ft].tin_rate_ns; | |
2493 | q->rate_shft = q->tins[ft].tin_rate_shft; | |
2494 | ||
2495 | if (q->buffer_config_limit) { | |
2496 | q->buffer_limit = q->buffer_config_limit; | |
2497 | } else if (q->rate_bps) { | |
2498 | u64 t = q->rate_bps * q->interval; | |
2499 | ||
2500 | do_div(t, USEC_PER_SEC / 4); | |
2501 | q->buffer_limit = max_t(u32, t, 4U << 20); | |
2502 | } else { | |
2503 | q->buffer_limit = ~0; | |
2504 | } | |
2505 | ||
2506 | sch->flags &= ~TCQ_F_CAN_BYPASS; | |
2507 | ||
2508 | q->buffer_limit = min(q->buffer_limit, | |
2509 | max(sch->limit * psched_mtu(qdisc_dev(sch)), | |
2510 | q->buffer_config_limit)); | |
2511 | } | |
2512 | ||
2513 | static int cake_change(struct Qdisc *sch, struct nlattr *opt, | |
2514 | struct netlink_ext_ack *extack) | |
2515 | { | |
2516 | struct cake_sched_data *q = qdisc_priv(sch); | |
2517 | struct nlattr *tb[TCA_CAKE_MAX + 1]; | |
2518 | int err; | |
2519 | ||
2520 | if (!opt) | |
2521 | return -EINVAL; | |
2522 | ||
2523 | err = nla_parse_nested(tb, TCA_CAKE_MAX, opt, cake_policy, extack); | |
2524 | if (err < 0) | |
2525 | return err; | |
2526 | ||
ea825115 THJ |
2527 | if (tb[TCA_CAKE_NAT]) { |
2528 | #if IS_ENABLED(CONFIG_NF_CONNTRACK) | |
2529 | q->flow_mode &= ~CAKE_FLOW_NAT_FLAG; | |
2530 | q->flow_mode |= CAKE_FLOW_NAT_FLAG * | |
2531 | !!nla_get_u32(tb[TCA_CAKE_NAT]); | |
2532 | #else | |
2533 | NL_SET_ERR_MSG_ATTR(extack, tb[TCA_CAKE_NAT], | |
2534 | "No conntrack support in kernel"); | |
2535 | return -EOPNOTSUPP; | |
2536 | #endif | |
2537 | } | |
2538 | ||
046f6fd5 THJ |
2539 | if (tb[TCA_CAKE_BASE_RATE64]) |
2540 | q->rate_bps = nla_get_u64(tb[TCA_CAKE_BASE_RATE64]); | |
2541 | ||
83f8fd69 THJ |
2542 | if (tb[TCA_CAKE_DIFFSERV_MODE]) |
2543 | q->tin_mode = nla_get_u32(tb[TCA_CAKE_DIFFSERV_MODE]); | |
2544 | ||
2545 | if (tb[TCA_CAKE_WASH]) { | |
2546 | if (!!nla_get_u32(tb[TCA_CAKE_WASH])) | |
2547 | q->rate_flags |= CAKE_FLAG_WASH; | |
2548 | else | |
2549 | q->rate_flags &= ~CAKE_FLAG_WASH; | |
2550 | } | |
2551 | ||
046f6fd5 | 2552 | if (tb[TCA_CAKE_FLOW_MODE]) |
ea825115 THJ |
2553 | q->flow_mode = ((q->flow_mode & CAKE_FLOW_NAT_FLAG) | |
2554 | (nla_get_u32(tb[TCA_CAKE_FLOW_MODE]) & | |
2555 | CAKE_FLOW_MASK)); | |
046f6fd5 | 2556 | |
a729b7f0 THJ |
2557 | if (tb[TCA_CAKE_ATM]) |
2558 | q->atm_mode = nla_get_u32(tb[TCA_CAKE_ATM]); | |
2559 | ||
2560 | if (tb[TCA_CAKE_OVERHEAD]) { | |
2561 | q->rate_overhead = nla_get_s32(tb[TCA_CAKE_OVERHEAD]); | |
2562 | q->rate_flags |= CAKE_FLAG_OVERHEAD; | |
2563 | ||
2564 | q->max_netlen = 0; | |
2565 | q->max_adjlen = 0; | |
2566 | q->min_netlen = ~0; | |
2567 | q->min_adjlen = ~0; | |
2568 | } | |
2569 | ||
2570 | if (tb[TCA_CAKE_RAW]) { | |
2571 | q->rate_flags &= ~CAKE_FLAG_OVERHEAD; | |
2572 | ||
2573 | q->max_netlen = 0; | |
2574 | q->max_adjlen = 0; | |
2575 | q->min_netlen = ~0; | |
2576 | q->min_adjlen = ~0; | |
2577 | } | |
2578 | ||
2579 | if (tb[TCA_CAKE_MPU]) | |
2580 | q->rate_mpu = nla_get_u32(tb[TCA_CAKE_MPU]); | |
2581 | ||
046f6fd5 THJ |
2582 | if (tb[TCA_CAKE_RTT]) { |
2583 | q->interval = nla_get_u32(tb[TCA_CAKE_RTT]); | |
2584 | ||
2585 | if (!q->interval) | |
2586 | q->interval = 1; | |
2587 | } | |
2588 | ||
2589 | if (tb[TCA_CAKE_TARGET]) { | |
2590 | q->target = nla_get_u32(tb[TCA_CAKE_TARGET]); | |
2591 | ||
2592 | if (!q->target) | |
2593 | q->target = 1; | |
2594 | } | |
2595 | ||
7298de9c THJ |
2596 | if (tb[TCA_CAKE_AUTORATE]) { |
2597 | if (!!nla_get_u32(tb[TCA_CAKE_AUTORATE])) | |
2598 | q->rate_flags |= CAKE_FLAG_AUTORATE_INGRESS; | |
2599 | else | |
2600 | q->rate_flags &= ~CAKE_FLAG_AUTORATE_INGRESS; | |
2601 | } | |
2602 | ||
2603 | if (tb[TCA_CAKE_INGRESS]) { | |
2604 | if (!!nla_get_u32(tb[TCA_CAKE_INGRESS])) | |
2605 | q->rate_flags |= CAKE_FLAG_INGRESS; | |
2606 | else | |
2607 | q->rate_flags &= ~CAKE_FLAG_INGRESS; | |
2608 | } | |
2609 | ||
8b713881 THJ |
2610 | if (tb[TCA_CAKE_ACK_FILTER]) |
2611 | q->ack_filter = nla_get_u32(tb[TCA_CAKE_ACK_FILTER]); | |
2612 | ||
046f6fd5 THJ |
2613 | if (tb[TCA_CAKE_MEMORY]) |
2614 | q->buffer_config_limit = nla_get_u32(tb[TCA_CAKE_MEMORY]); | |
2615 | ||
2db6dc26 DT |
2616 | if (tb[TCA_CAKE_SPLIT_GSO]) { |
2617 | if (!!nla_get_u32(tb[TCA_CAKE_SPLIT_GSO])) | |
2618 | q->rate_flags |= CAKE_FLAG_SPLIT_GSO; | |
2619 | else | |
2620 | q->rate_flags &= ~CAKE_FLAG_SPLIT_GSO; | |
2621 | } | |
0c850344 | 2622 | |
0b5c7efd | 2623 | if (tb[TCA_CAKE_FWMARK]) { |
eab2fc82 THJ |
2624 | q->fwmark_mask = nla_get_u32(tb[TCA_CAKE_FWMARK]); |
2625 | q->fwmark_shft = q->fwmark_mask ? __ffs(q->fwmark_mask) : 0; | |
0b5c7efd KDB |
2626 | } |
2627 | ||
046f6fd5 THJ |
2628 | if (q->tins) { |
2629 | sch_tree_lock(sch); | |
2630 | cake_reconfigure(sch); | |
2631 | sch_tree_unlock(sch); | |
2632 | } | |
2633 | ||
2634 | return 0; | |
2635 | } | |
2636 | ||
2637 | static void cake_destroy(struct Qdisc *sch) | |
2638 | { | |
2639 | struct cake_sched_data *q = qdisc_priv(sch); | |
2640 | ||
2641 | qdisc_watchdog_cancel(&q->watchdog); | |
2642 | tcf_block_put(q->block); | |
2643 | kvfree(q->tins); | |
2644 | } | |
2645 | ||
2646 | static int cake_init(struct Qdisc *sch, struct nlattr *opt, | |
2647 | struct netlink_ext_ack *extack) | |
2648 | { | |
2649 | struct cake_sched_data *q = qdisc_priv(sch); | |
2650 | int i, j, err; | |
2651 | ||
2652 | sch->limit = 10240; | |
83f8fd69 | 2653 | q->tin_mode = CAKE_DIFFSERV_DIFFSERV3; |
046f6fd5 THJ |
2654 | q->flow_mode = CAKE_FLOW_TRIPLE; |
2655 | ||
2656 | q->rate_bps = 0; /* unlimited by default */ | |
2657 | ||
2658 | q->interval = 100000; /* 100ms default */ | |
2659 | q->target = 5000; /* 5ms: codel RFC argues | |
2660 | * for 5 to 10% of interval | |
2661 | */ | |
2db6dc26 | 2662 | q->rate_flags |= CAKE_FLAG_SPLIT_GSO; |
046f6fd5 THJ |
2663 | q->cur_tin = 0; |
2664 | q->cur_flow = 0; | |
2665 | ||
2666 | qdisc_watchdog_init(&q->watchdog, sch); | |
2667 | ||
2668 | if (opt) { | |
2669 | int err = cake_change(sch, opt, extack); | |
2670 | ||
2671 | if (err) | |
2672 | return err; | |
2673 | } | |
2674 | ||
2675 | err = tcf_block_get(&q->block, &q->filter_list, sch, extack); | |
2676 | if (err) | |
2677 | return err; | |
2678 | ||
2679 | quantum_div[0] = ~0; | |
2680 | for (i = 1; i <= CAKE_QUEUES; i++) | |
2681 | quantum_div[i] = 65535 / i; | |
2682 | ||
329e0989 | 2683 | q->tins = kvcalloc(CAKE_MAX_TINS, sizeof(struct cake_tin_data), |
046f6fd5 THJ |
2684 | GFP_KERNEL); |
2685 | if (!q->tins) | |
2686 | goto nomem; | |
2687 | ||
2688 | for (i = 0; i < CAKE_MAX_TINS; i++) { | |
2689 | struct cake_tin_data *b = q->tins + i; | |
2690 | ||
2691 | INIT_LIST_HEAD(&b->new_flows); | |
2692 | INIT_LIST_HEAD(&b->old_flows); | |
2693 | INIT_LIST_HEAD(&b->decaying_flows); | |
2694 | b->sparse_flow_count = 0; | |
2695 | b->bulk_flow_count = 0; | |
2696 | b->decaying_flow_count = 0; | |
2697 | ||
2698 | for (j = 0; j < CAKE_QUEUES; j++) { | |
2699 | struct cake_flow *flow = b->flows + j; | |
2700 | u32 k = j * CAKE_MAX_TINS + i; | |
2701 | ||
2702 | INIT_LIST_HEAD(&flow->flowchain); | |
2703 | cobalt_vars_init(&flow->cvars); | |
2704 | ||
2705 | q->overflow_heap[k].t = i; | |
2706 | q->overflow_heap[k].b = j; | |
2707 | b->overflow_idx[j] = k; | |
2708 | } | |
2709 | } | |
2710 | ||
2711 | cake_reconfigure(sch); | |
2712 | q->avg_peak_bandwidth = q->rate_bps; | |
2713 | q->min_netlen = ~0; | |
2714 | q->min_adjlen = ~0; | |
2715 | return 0; | |
2716 | ||
2717 | nomem: | |
2718 | cake_destroy(sch); | |
2719 | return -ENOMEM; | |
2720 | } | |
2721 | ||
2722 | static int cake_dump(struct Qdisc *sch, struct sk_buff *skb) | |
2723 | { | |
2724 | struct cake_sched_data *q = qdisc_priv(sch); | |
2725 | struct nlattr *opts; | |
2726 | ||
2727 | opts = nla_nest_start(skb, TCA_OPTIONS); | |
2728 | if (!opts) | |
2729 | goto nla_put_failure; | |
2730 | ||
2731 | if (nla_put_u64_64bit(skb, TCA_CAKE_BASE_RATE64, q->rate_bps, | |
2732 | TCA_CAKE_PAD)) | |
2733 | goto nla_put_failure; | |
2734 | ||
2735 | if (nla_put_u32(skb, TCA_CAKE_FLOW_MODE, | |
2736 | q->flow_mode & CAKE_FLOW_MASK)) | |
2737 | goto nla_put_failure; | |
2738 | ||
2739 | if (nla_put_u32(skb, TCA_CAKE_RTT, q->interval)) | |
2740 | goto nla_put_failure; | |
2741 | ||
2742 | if (nla_put_u32(skb, TCA_CAKE_TARGET, q->target)) | |
2743 | goto nla_put_failure; | |
2744 | ||
2745 | if (nla_put_u32(skb, TCA_CAKE_MEMORY, q->buffer_config_limit)) | |
2746 | goto nla_put_failure; | |
2747 | ||
7298de9c THJ |
2748 | if (nla_put_u32(skb, TCA_CAKE_AUTORATE, |
2749 | !!(q->rate_flags & CAKE_FLAG_AUTORATE_INGRESS))) | |
2750 | goto nla_put_failure; | |
2751 | ||
2752 | if (nla_put_u32(skb, TCA_CAKE_INGRESS, | |
2753 | !!(q->rate_flags & CAKE_FLAG_INGRESS))) | |
2754 | goto nla_put_failure; | |
2755 | ||
8b713881 THJ |
2756 | if (nla_put_u32(skb, TCA_CAKE_ACK_FILTER, q->ack_filter)) |
2757 | goto nla_put_failure; | |
2758 | ||
ea825115 THJ |
2759 | if (nla_put_u32(skb, TCA_CAKE_NAT, |
2760 | !!(q->flow_mode & CAKE_FLOW_NAT_FLAG))) | |
2761 | goto nla_put_failure; | |
2762 | ||
83f8fd69 THJ |
2763 | if (nla_put_u32(skb, TCA_CAKE_DIFFSERV_MODE, q->tin_mode)) |
2764 | goto nla_put_failure; | |
2765 | ||
2766 | if (nla_put_u32(skb, TCA_CAKE_WASH, | |
2767 | !!(q->rate_flags & CAKE_FLAG_WASH))) | |
2768 | goto nla_put_failure; | |
a729b7f0 THJ |
2769 | |
2770 | if (nla_put_u32(skb, TCA_CAKE_OVERHEAD, q->rate_overhead)) | |
2771 | goto nla_put_failure; | |
2772 | ||
2773 | if (!(q->rate_flags & CAKE_FLAG_OVERHEAD)) | |
2774 | if (nla_put_u32(skb, TCA_CAKE_RAW, 0)) | |
2775 | goto nla_put_failure; | |
2776 | ||
2777 | if (nla_put_u32(skb, TCA_CAKE_ATM, q->atm_mode)) | |
2778 | goto nla_put_failure; | |
2779 | ||
2780 | if (nla_put_u32(skb, TCA_CAKE_MPU, q->rate_mpu)) | |
2781 | goto nla_put_failure; | |
0c850344 THJ |
2782 | |
2783 | if (nla_put_u32(skb, TCA_CAKE_SPLIT_GSO, | |
2784 | !!(q->rate_flags & CAKE_FLAG_SPLIT_GSO))) | |
2785 | goto nla_put_failure; | |
0b5c7efd | 2786 | |
eab2fc82 | 2787 | if (nla_put_u32(skb, TCA_CAKE_FWMARK, q->fwmark_mask)) |
0b5c7efd | 2788 | goto nla_put_failure; |
83f8fd69 | 2789 | |
046f6fd5 THJ |
2790 | return nla_nest_end(skb, opts); |
2791 | ||
2792 | nla_put_failure: | |
2793 | return -1; | |
2794 | } | |
2795 | ||
2796 | static int cake_dump_stats(struct Qdisc *sch, struct gnet_dump *d) | |
2797 | { | |
2798 | struct nlattr *stats = nla_nest_start(d->skb, TCA_STATS_APP); | |
2799 | struct cake_sched_data *q = qdisc_priv(sch); | |
2800 | struct nlattr *tstats, *ts; | |
2801 | int i; | |
2802 | ||
2803 | if (!stats) | |
2804 | return -1; | |
2805 | ||
2806 | #define PUT_STAT_U32(attr, data) do { \ | |
2807 | if (nla_put_u32(d->skb, TCA_CAKE_STATS_ ## attr, data)) \ | |
2808 | goto nla_put_failure; \ | |
2809 | } while (0) | |
2810 | #define PUT_STAT_U64(attr, data) do { \ | |
2811 | if (nla_put_u64_64bit(d->skb, TCA_CAKE_STATS_ ## attr, \ | |
2812 | data, TCA_CAKE_STATS_PAD)) \ | |
2813 | goto nla_put_failure; \ | |
2814 | } while (0) | |
2815 | ||
2816 | PUT_STAT_U64(CAPACITY_ESTIMATE64, q->avg_peak_bandwidth); | |
2817 | PUT_STAT_U32(MEMORY_LIMIT, q->buffer_limit); | |
2818 | PUT_STAT_U32(MEMORY_USED, q->buffer_max_used); | |
2819 | PUT_STAT_U32(AVG_NETOFF, ((q->avg_netoff + 0x8000) >> 16)); | |
2820 | PUT_STAT_U32(MAX_NETLEN, q->max_netlen); | |
2821 | PUT_STAT_U32(MAX_ADJLEN, q->max_adjlen); | |
2822 | PUT_STAT_U32(MIN_NETLEN, q->min_netlen); | |
2823 | PUT_STAT_U32(MIN_ADJLEN, q->min_adjlen); | |
2824 | ||
2825 | #undef PUT_STAT_U32 | |
2826 | #undef PUT_STAT_U64 | |
2827 | ||
2828 | tstats = nla_nest_start(d->skb, TCA_CAKE_STATS_TIN_STATS); | |
2829 | if (!tstats) | |
2830 | goto nla_put_failure; | |
2831 | ||
2832 | #define PUT_TSTAT_U32(attr, data) do { \ | |
2833 | if (nla_put_u32(d->skb, TCA_CAKE_TIN_STATS_ ## attr, data)) \ | |
2834 | goto nla_put_failure; \ | |
2835 | } while (0) | |
2836 | #define PUT_TSTAT_U64(attr, data) do { \ | |
2837 | if (nla_put_u64_64bit(d->skb, TCA_CAKE_TIN_STATS_ ## attr, \ | |
2838 | data, TCA_CAKE_TIN_STATS_PAD)) \ | |
2839 | goto nla_put_failure; \ | |
2840 | } while (0) | |
2841 | ||
2842 | for (i = 0; i < q->tin_cnt; i++) { | |
83f8fd69 | 2843 | struct cake_tin_data *b = &q->tins[q->tin_order[i]]; |
046f6fd5 THJ |
2844 | |
2845 | ts = nla_nest_start(d->skb, i + 1); | |
2846 | if (!ts) | |
2847 | goto nla_put_failure; | |
2848 | ||
2849 | PUT_TSTAT_U64(THRESHOLD_RATE64, b->tin_rate_bps); | |
2850 | PUT_TSTAT_U64(SENT_BYTES64, b->bytes); | |
2851 | PUT_TSTAT_U32(BACKLOG_BYTES, b->tin_backlog); | |
2852 | ||
2853 | PUT_TSTAT_U32(TARGET_US, | |
2854 | ktime_to_us(ns_to_ktime(b->cparams.target))); | |
2855 | PUT_TSTAT_U32(INTERVAL_US, | |
2856 | ktime_to_us(ns_to_ktime(b->cparams.interval))); | |
2857 | ||
2858 | PUT_TSTAT_U32(SENT_PACKETS, b->packets); | |
2859 | PUT_TSTAT_U32(DROPPED_PACKETS, b->tin_dropped); | |
2860 | PUT_TSTAT_U32(ECN_MARKED_PACKETS, b->tin_ecn_mark); | |
2861 | PUT_TSTAT_U32(ACKS_DROPPED_PACKETS, b->ack_drops); | |
2862 | ||
2863 | PUT_TSTAT_U32(PEAK_DELAY_US, | |
2864 | ktime_to_us(ns_to_ktime(b->peak_delay))); | |
2865 | PUT_TSTAT_U32(AVG_DELAY_US, | |
2866 | ktime_to_us(ns_to_ktime(b->avge_delay))); | |
2867 | PUT_TSTAT_U32(BASE_DELAY_US, | |
2868 | ktime_to_us(ns_to_ktime(b->base_delay))); | |
2869 | ||
2870 | PUT_TSTAT_U32(WAY_INDIRECT_HITS, b->way_hits); | |
2871 | PUT_TSTAT_U32(WAY_MISSES, b->way_misses); | |
2872 | PUT_TSTAT_U32(WAY_COLLISIONS, b->way_collisions); | |
2873 | ||
2874 | PUT_TSTAT_U32(SPARSE_FLOWS, b->sparse_flow_count + | |
2875 | b->decaying_flow_count); | |
2876 | PUT_TSTAT_U32(BULK_FLOWS, b->bulk_flow_count); | |
2877 | PUT_TSTAT_U32(UNRESPONSIVE_FLOWS, b->unresponsive_flow_count); | |
2878 | PUT_TSTAT_U32(MAX_SKBLEN, b->max_skblen); | |
2879 | ||
2880 | PUT_TSTAT_U32(FLOW_QUANTUM, b->flow_quantum); | |
2881 | nla_nest_end(d->skb, ts); | |
2882 | } | |
2883 | ||
2884 | #undef PUT_TSTAT_U32 | |
2885 | #undef PUT_TSTAT_U64 | |
2886 | ||
2887 | nla_nest_end(d->skb, tstats); | |
2888 | return nla_nest_end(d->skb, stats); | |
2889 | ||
2890 | nla_put_failure: | |
2891 | nla_nest_cancel(d->skb, stats); | |
2892 | return -1; | |
2893 | } | |
2894 | ||
2895 | static struct Qdisc *cake_leaf(struct Qdisc *sch, unsigned long arg) | |
2896 | { | |
2897 | return NULL; | |
2898 | } | |
2899 | ||
2900 | static unsigned long cake_find(struct Qdisc *sch, u32 classid) | |
2901 | { | |
2902 | return 0; | |
2903 | } | |
2904 | ||
2905 | static unsigned long cake_bind(struct Qdisc *sch, unsigned long parent, | |
2906 | u32 classid) | |
2907 | { | |
2908 | return 0; | |
2909 | } | |
2910 | ||
2911 | static void cake_unbind(struct Qdisc *q, unsigned long cl) | |
2912 | { | |
2913 | } | |
2914 | ||
2915 | static struct tcf_block *cake_tcf_block(struct Qdisc *sch, unsigned long cl, | |
2916 | struct netlink_ext_ack *extack) | |
2917 | { | |
2918 | struct cake_sched_data *q = qdisc_priv(sch); | |
2919 | ||
2920 | if (cl) | |
2921 | return NULL; | |
2922 | return q->block; | |
2923 | } | |
2924 | ||
2925 | static int cake_dump_class(struct Qdisc *sch, unsigned long cl, | |
2926 | struct sk_buff *skb, struct tcmsg *tcm) | |
2927 | { | |
2928 | tcm->tcm_handle |= TC_H_MIN(cl); | |
2929 | return 0; | |
2930 | } | |
2931 | ||
2932 | static int cake_dump_class_stats(struct Qdisc *sch, unsigned long cl, | |
2933 | struct gnet_dump *d) | |
2934 | { | |
2935 | struct cake_sched_data *q = qdisc_priv(sch); | |
2936 | const struct cake_flow *flow = NULL; | |
2937 | struct gnet_stats_queue qs = { 0 }; | |
2938 | struct nlattr *stats; | |
2939 | u32 idx = cl - 1; | |
2940 | ||
2941 | if (idx < CAKE_QUEUES * q->tin_cnt) { | |
83f8fd69 THJ |
2942 | const struct cake_tin_data *b = \ |
2943 | &q->tins[q->tin_order[idx / CAKE_QUEUES]]; | |
046f6fd5 THJ |
2944 | const struct sk_buff *skb; |
2945 | ||
2946 | flow = &b->flows[idx % CAKE_QUEUES]; | |
2947 | ||
2948 | if (flow->head) { | |
2949 | sch_tree_lock(sch); | |
2950 | skb = flow->head; | |
2951 | while (skb) { | |
2952 | qs.qlen++; | |
2953 | skb = skb->next; | |
2954 | } | |
2955 | sch_tree_unlock(sch); | |
2956 | } | |
2957 | qs.backlog = b->backlogs[idx % CAKE_QUEUES]; | |
2958 | qs.drops = flow->dropped; | |
2959 | } | |
2960 | if (gnet_stats_copy_queue(d, NULL, &qs, qs.qlen) < 0) | |
2961 | return -1; | |
2962 | if (flow) { | |
2963 | ktime_t now = ktime_get(); | |
2964 | ||
2965 | stats = nla_nest_start(d->skb, TCA_STATS_APP); | |
2966 | if (!stats) | |
2967 | return -1; | |
2968 | ||
2969 | #define PUT_STAT_U32(attr, data) do { \ | |
2970 | if (nla_put_u32(d->skb, TCA_CAKE_STATS_ ## attr, data)) \ | |
2971 | goto nla_put_failure; \ | |
2972 | } while (0) | |
2973 | #define PUT_STAT_S32(attr, data) do { \ | |
2974 | if (nla_put_s32(d->skb, TCA_CAKE_STATS_ ## attr, data)) \ | |
2975 | goto nla_put_failure; \ | |
2976 | } while (0) | |
2977 | ||
2978 | PUT_STAT_S32(DEFICIT, flow->deficit); | |
2979 | PUT_STAT_U32(DROPPING, flow->cvars.dropping); | |
2980 | PUT_STAT_U32(COBALT_COUNT, flow->cvars.count); | |
2981 | PUT_STAT_U32(P_DROP, flow->cvars.p_drop); | |
2982 | if (flow->cvars.p_drop) { | |
2983 | PUT_STAT_S32(BLUE_TIMER_US, | |
2984 | ktime_to_us( | |
2985 | ktime_sub(now, | |
2986 | flow->cvars.blue_timer))); | |
2987 | } | |
2988 | if (flow->cvars.dropping) { | |
2989 | PUT_STAT_S32(DROP_NEXT_US, | |
2990 | ktime_to_us( | |
2991 | ktime_sub(now, | |
2992 | flow->cvars.drop_next))); | |
2993 | } | |
2994 | ||
2995 | if (nla_nest_end(d->skb, stats) < 0) | |
2996 | return -1; | |
2997 | } | |
2998 | ||
2999 | return 0; | |
3000 | ||
3001 | nla_put_failure: | |
3002 | nla_nest_cancel(d->skb, stats); | |
3003 | return -1; | |
3004 | } | |
3005 | ||
3006 | static void cake_walk(struct Qdisc *sch, struct qdisc_walker *arg) | |
3007 | { | |
3008 | struct cake_sched_data *q = qdisc_priv(sch); | |
3009 | unsigned int i, j; | |
3010 | ||
3011 | if (arg->stop) | |
3012 | return; | |
3013 | ||
3014 | for (i = 0; i < q->tin_cnt; i++) { | |
83f8fd69 | 3015 | struct cake_tin_data *b = &q->tins[q->tin_order[i]]; |
046f6fd5 THJ |
3016 | |
3017 | for (j = 0; j < CAKE_QUEUES; j++) { | |
3018 | if (list_empty(&b->flows[j].flowchain) || | |
3019 | arg->count < arg->skip) { | |
3020 | arg->count++; | |
3021 | continue; | |
3022 | } | |
3023 | if (arg->fn(sch, i * CAKE_QUEUES + j + 1, arg) < 0) { | |
3024 | arg->stop = 1; | |
3025 | break; | |
3026 | } | |
3027 | arg->count++; | |
3028 | } | |
3029 | } | |
3030 | } | |
3031 | ||
3032 | static const struct Qdisc_class_ops cake_class_ops = { | |
3033 | .leaf = cake_leaf, | |
3034 | .find = cake_find, | |
3035 | .tcf_block = cake_tcf_block, | |
3036 | .bind_tcf = cake_bind, | |
3037 | .unbind_tcf = cake_unbind, | |
3038 | .dump = cake_dump_class, | |
3039 | .dump_stats = cake_dump_class_stats, | |
3040 | .walk = cake_walk, | |
3041 | }; | |
3042 | ||
3043 | static struct Qdisc_ops cake_qdisc_ops __read_mostly = { | |
3044 | .cl_ops = &cake_class_ops, | |
3045 | .id = "cake", | |
3046 | .priv_size = sizeof(struct cake_sched_data), | |
3047 | .enqueue = cake_enqueue, | |
3048 | .dequeue = cake_dequeue, | |
3049 | .peek = qdisc_peek_dequeued, | |
3050 | .init = cake_init, | |
3051 | .reset = cake_reset, | |
3052 | .destroy = cake_destroy, | |
3053 | .change = cake_change, | |
3054 | .dump = cake_dump, | |
3055 | .dump_stats = cake_dump_stats, | |
3056 | .owner = THIS_MODULE, | |
3057 | }; | |
3058 | ||
3059 | static int __init cake_module_init(void) | |
3060 | { | |
3061 | return register_qdisc(&cake_qdisc_ops); | |
3062 | } | |
3063 | ||
3064 | static void __exit cake_module_exit(void) | |
3065 | { | |
3066 | unregister_qdisc(&cake_qdisc_ops); | |
3067 | } | |
3068 | ||
3069 | module_init(cake_module_init) | |
3070 | module_exit(cake_module_exit) | |
3071 | MODULE_AUTHOR("Jonathan Morton"); | |
3072 | MODULE_LICENSE("Dual BSD/GPL"); | |
3073 | MODULE_DESCRIPTION("The CAKE shaper."); |