net/sched/sch_cake.c

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