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