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