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