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