net/sched/sch

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

DEFINITIONS
