WIP FPC-III support

[linux/fpc-iii.git] / net / sched / sch_cake.c

// SPDX-License-Identifier: GPL-2.0 OR BSD-3-Clause

/* COMMON Applications Kept Enhanced (CAKE) discipline
 *
 * Copyright (C) 2014-2018 Jonathan Morton <chromatix99@gmail.com>
 * Copyright (C) 2015-2018 Toke Høiland-Jørgensen <toke@toke.dk>
 * Copyright (C) 2014-2018 Dave Täht <dave.taht@gmail.com>
 * Copyright (C) 2015-2018 Sebastian Moeller <moeller0@gmx.de>
 * (C) 2015-2018 Kevin Darbyshire-Bryant <kevin@darbyshire-bryant.me.uk>
 * Copyright (C) 2017-2018 Ryan Mounce <ryan@mounce.com.au>
 *
 * The CAKE Principles:
 *                 (or, how to have your cake and eat it too)
 *
 * This is a combination of several shaping, AQM and FQ techniques into one
 * easy-to-use package:
 *
 * - An overall bandwidth shaper, to move the bottleneck away from dumb CPE
 *   equipment and bloated MACs.  This operates in deficit mode (as in sch_fq),
 *   eliminating the need for any sort of burst parameter (eg. token bucket
 *   depth).  Burst support is limited to that necessary to overcome scheduling
 *   latency.
 *
 * - A Diffserv-aware priority queue, giving more priority to certain classes,
 *   up to a specified fraction of bandwidth.  Above that bandwidth threshold,
 *   the priority is reduced to avoid starving other tins.
 *
 * - Each priority tin has a separate Flow Queue system, to isolate traffic
 *   flows from each other.  This prevents a burst on one flow from increasing
 *   the delay to another.  Flows are distributed to queues using a
 *   set-associative hash function.
 *
 * - Each queue is actively managed by Cobalt, which is a combination of the
 *   Codel and Blue AQM algorithms.  This serves flows fairly, and signals
 *   congestion early via ECN (if available) and/or packet drops, to keep
 *   latency low.  The codel parameters are auto-tuned based on the bandwidth
 *   setting, as is necessary at low bandwidths.
 *
 * The configuration parameters are kept deliberately simple for ease of use.
 * Everything has sane defaults.  Complete generality of configuration is *not*
 * a goal.
 *
 * The priority queue operates according to a weighted DRR scheme, combined with
 * a bandwidth tracker which reuses the shaper logic to detect which side of the
 * bandwidth sharing threshold the tin is operating.  This determines whether a
 * priority-based weight (high) or a bandwidth-based weight (low) is used for
 * that tin in the current pass.
 *
 * This qdisc was inspired by Eric Dumazet's fq_codel code, which he kindly
 * granted us permission to leverage.
 */

#include <linux/module.h>
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/jiffies.h>
#include <linux/string.h>
#include <linux/in.h>
#include <linux/errno.h>
#include <linux/init.h>
#include <linux/skbuff.h>
#include <linux/jhash.h>
#include <linux/slab.h>
#include <linux/vmalloc.h>
#include <linux/reciprocal_div.h>
#include <net/netlink.h>
#include <linux/if_vlan.h>
#include <net/pkt_sched.h>
#include <net/pkt_cls.h>
#include <net/tcp.h>
#include <net/flow_dissector.h>

#if IS_ENABLED(CONFIG_NF_CONNTRACK)
#include <net/netfilter/nf_conntrack_core.h>
#endif

#define CAKE_SET_WAYS (8)
#define CAKE_MAX_TINS (8)
#define CAKE_QUEUES (1024)
#define CAKE_FLOW_MASK 63
#define CAKE_FLOW_NAT_FLAG 64

/* struct cobalt_params - contains codel and blue parameters
 * @interval:   codel initial drop rate
 * @target:     maximum persistent sojourn time & blue update rate
 * @mtu_time:   serialisation delay of maximum-size packet
 * @p_inc:      increment of blue drop probability (0.32 fxp)
 * @p_dec:      decrement of blue drop probability (0.32 fxp)
 */
struct cobalt_params {
        u64     interval;
        u64     target;
        u64     mtu_time;
        u32     p_inc;
        u32     p_dec;
};

/* struct cobalt_vars - contains codel and blue variables
 * @count:              codel dropping frequency
 * @rec_inv_sqrt:       reciprocal value of sqrt(count) >> 1
 * @drop_next:          time to drop next packet, or when we dropped last
 * @blue_timer:         Blue time to next drop
 * @p_drop:             BLUE drop probability (0.32 fxp)
 * @dropping:           set if in dropping state
 * @ecn_marked:         set if marked
 */
struct cobalt_vars {
        u32     count;
        u32     rec_inv_sqrt;
        ktime_t drop_next;
        ktime_t blue_timer;
        u32     p_drop;
        bool    dropping;
        bool    ecn_marked;
};

enum {
        CAKE_SET_NONE = 0,
        CAKE_SET_SPARSE,
        CAKE_SET_SPARSE_WAIT, /* counted in SPARSE, actually in BULK */
        CAKE_SET_BULK,
        CAKE_SET_DECAYING
};

struct cake_flow {
        /* this stuff is all needed per-flow at dequeue time */
        struct sk_buff    *head;
        struct sk_buff    *tail;
        struct list_head  flowchain;
        s32               deficit;
        u32               dropped;
        struct cobalt_vars cvars;
        u16               srchost; /* index into cake_host table */
        u16               dsthost;
        u8                set;
}; /* please try to keep this structure <= 64 bytes */

struct cake_host {
        u32 srchost_tag;
        u32 dsthost_tag;
        u16 srchost_bulk_flow_count;
        u16 dsthost_bulk_flow_count;
};

struct cake_heap_entry {
        u16 t:3, b:10;
};

struct cake_tin_data {
        struct cake_flow flows[CAKE_QUEUES];
        u32     backlogs[CAKE_QUEUES];
        u32     tags[CAKE_QUEUES]; /* for set association */
        u16     overflow_idx[CAKE_QUEUES];
        struct cake_host hosts[CAKE_QUEUES]; /* for triple isolation */
        u16     flow_quantum;

        struct cobalt_params cparams;
        u32     drop_overlimit;
        u16     bulk_flow_count;
        u16     sparse_flow_count;
        u16     decaying_flow_count;
        u16     unresponsive_flow_count;

        u32     max_skblen;

        struct list_head new_flows;
        struct list_head old_flows;
        struct list_head decaying_flows;

        /* time_next = time_this + ((len * rate_ns) >> rate_shft) */
        ktime_t time_next_packet;
        u64     tin_rate_ns;
        u64     tin_rate_bps;
        u16     tin_rate_shft;

        u16     tin_quantum;
        s32     tin_deficit;
        u32     tin_backlog;
        u32     tin_dropped;
        u32     tin_ecn_mark;

        u32     packets;
        u64     bytes;

        u32     ack_drops;

        /* moving averages */
        u64 avge_delay;
        u64 peak_delay;
        u64 base_delay;

        /* hash function stats */
        u32     way_directs;
        u32     way_hits;
        u32     way_misses;
        u32     way_collisions;
}; /* number of tins is small, so size of this struct doesn't matter much */

struct cake_sched_data {
        struct tcf_proto __rcu *filter_list; /* optional external classifier */
        struct tcf_block *block;
        struct cake_tin_data *tins;

        struct cake_heap_entry overflow_heap[CAKE_QUEUES * CAKE_MAX_TINS];
        u16             overflow_timeout;

        u16             tin_cnt;
        u8              tin_mode;
        u8              flow_mode;
        u8              ack_filter;
        u8              atm_mode;

        u32             fwmark_mask;
        u16             fwmark_shft;

        /* time_next = time_this + ((len * rate_ns) >> rate_shft) */
        u16             rate_shft;
        ktime_t         time_next_packet;
        ktime_t         failsafe_next_packet;
        u64             rate_ns;
        u64             rate_bps;
        u16             rate_flags;
        s16             rate_overhead;
        u16             rate_mpu;
        u64             interval;
        u64             target;

        /* resource tracking */
        u32             buffer_used;
        u32             buffer_max_used;
        u32             buffer_limit;
        u32             buffer_config_limit;

        /* indices for dequeue */
        u16             cur_tin;
        u16             cur_flow;

        struct qdisc_watchdog watchdog;
        const u8        *tin_index;
        const u8        *tin_order;

        /* bandwidth capacity estimate */
        ktime_t         last_packet_time;
        ktime_t         avg_window_begin;
        u64             avg_packet_interval;
        u64             avg_window_bytes;
        u64             avg_peak_bandwidth;
        ktime_t         last_reconfig_time;

        /* packet length stats */
        u32             avg_netoff;
        u16             max_netlen;
        u16             max_adjlen;
        u16             min_netlen;
        u16             min_adjlen;
};

enum {
        CAKE_FLAG_OVERHEAD         = BIT(0),
        CAKE_FLAG_AUTORATE_INGRESS = BIT(1),
        CAKE_FLAG_INGRESS          = BIT(2),
        CAKE_FLAG_WASH             = BIT(3),
        CAKE_FLAG_SPLIT_GSO        = BIT(4)
};

/* COBALT operates the Codel and BLUE algorithms in parallel, in order to
 * obtain the best features of each.  Codel is excellent on flows which
 * respond to congestion signals in a TCP-like way.  BLUE is more effective on
 * unresponsive flows.
 */

struct cobalt_skb_cb {
        ktime_t enqueue_time;
        u32     adjusted_len;
};

static u64 us_to_ns(u64 us)
{
        return us * NSEC_PER_USEC;
}

static struct cobalt_skb_cb *get_cobalt_cb(const struct sk_buff *skb)
{
        qdisc_cb_private_validate(skb, sizeof(struct cobalt_skb_cb));
        return (struct cobalt_skb_cb *)qdisc_skb_cb(skb)->data;
}

static ktime_t cobalt_get_enqueue_time(const struct sk_buff *skb)
{
        return get_cobalt_cb(skb)->enqueue_time;
}

static void cobalt_set_enqueue_time(struct sk_buff *skb,
                                    ktime_t now)
{
        get_cobalt_cb(skb)->enqueue_time = now;
}

static u16 quantum_div[CAKE_QUEUES + 1] = {0};

/* Diffserv lookup tables */

static const u8 precedence[] = {
        0, 0, 0, 0, 0, 0, 0, 0,
        1, 1, 1, 1, 1, 1, 1, 1,
        2, 2, 2, 2, 2, 2, 2, 2,
        3, 3, 3, 3, 3, 3, 3, 3,
        4, 4, 4, 4, 4, 4, 4, 4,
        5, 5, 5, 5, 5, 5, 5, 5,
        6, 6, 6, 6, 6, 6, 6, 6,
        7, 7, 7, 7, 7, 7, 7, 7,
};

static const u8 diffserv8[] = {
        2, 0, 1, 2, 4, 2, 2, 2,
        1, 2, 1, 2, 1, 2, 1, 2,
        5, 2, 4, 2, 4, 2, 4, 2,
        3, 2, 3, 2, 3, 2, 3, 2,
        6, 2, 3, 2, 3, 2, 3, 2,
        6, 2, 2, 2, 6, 2, 6, 2,
        7, 2, 2, 2, 2, 2, 2, 2,
        7, 2, 2, 2, 2, 2, 2, 2,
};

static const u8 diffserv4[] = {
        0, 1, 0, 0, 2, 0, 0, 0,
        1, 0, 0, 0, 0, 0, 0, 0,
        2, 0, 2, 0, 2, 0, 2, 0,
        2, 0, 2, 0, 2, 0, 2, 0,
        3, 0, 2, 0, 2, 0, 2, 0,
        3, 0, 0, 0, 3, 0, 3, 0,
        3, 0, 0, 0, 0, 0, 0, 0,
        3, 0, 0, 0, 0, 0, 0, 0,
};

static const u8 diffserv3[] = {
        0, 1, 0, 0, 2, 0, 0, 0,
        1, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 2, 0, 2, 0,
        2, 0, 0, 0, 0, 0, 0, 0,
        2, 0, 0, 0, 0, 0, 0, 0,
};

static const u8 besteffort[] = {
        0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0,
};

/* tin priority order for stats dumping */

static const u8 normal_order[] = {0, 1, 2, 3, 4, 5, 6, 7};
static const u8 bulk_order[] = {1, 0, 2, 3};

#define REC_INV_SQRT_CACHE (16)
static u32 cobalt_rec_inv_sqrt_cache[REC_INV_SQRT_CACHE] = {0};

/* http://en.wikipedia.org/wiki/Methods_of_computing_square_roots
 * new_invsqrt = (invsqrt / 2) * (3 - count * invsqrt^2)
 *
 * Here, invsqrt is a fixed point number (< 1.0), 32bit mantissa, aka Q0.32
 */

static void cobalt_newton_step(struct cobalt_vars *vars)
{
        u32 invsqrt, invsqrt2;
        u64 val;

        invsqrt = vars->rec_inv_sqrt;
        invsqrt2 = ((u64)invsqrt * invsqrt) >> 32;
        val = (3LL << 32) - ((u64)vars->count * invsqrt2);

        val >>= 2; /* avoid overflow in following multiply */
        val = (val * invsqrt) >> (32 - 2 + 1);

        vars->rec_inv_sqrt = val;
}

static void cobalt_invsqrt(struct cobalt_vars *vars)
{
        if (vars->count < REC_INV_SQRT_CACHE)
                vars->rec_inv_sqrt = cobalt_rec_inv_sqrt_cache[vars->count];
        else
                cobalt_newton_step(vars);
}

/* There is a big difference in timing between the accurate values placed in
 * the cache and the approximations given by a single Newton step for small
 * count values, particularly when stepping from count 1 to 2 or vice versa.
 * Above 16, a single Newton step gives sufficient accuracy in either
 * direction, given the precision stored.
 *
 * The magnitude of the error when stepping up to count 2 is such as to give
 * the value that *should* have been produced at count 4.
 */

static void cobalt_cache_init(void)
{
        struct cobalt_vars v;

        memset(&v, 0, sizeof(v));
        v.rec_inv_sqrt = ~0U;
        cobalt_rec_inv_sqrt_cache[0] = v.rec_inv_sqrt;

        for (v.count = 1; v.count < REC_INV_SQRT_CACHE; v.count++) {
                cobalt_newton_step(&v);
                cobalt_newton_step(&v);
                cobalt_newton_step(&v);
                cobalt_newton_step(&v);

                cobalt_rec_inv_sqrt_cache[v.count] = v.rec_inv_sqrt;
        }
}

static void cobalt_vars_init(struct cobalt_vars *vars)
{
        memset(vars, 0, sizeof(*vars));

        if (!cobalt_rec_inv_sqrt_cache[0]) {
                cobalt_cache_init();
                cobalt_rec_inv_sqrt_cache[0] = ~0;
        }
}

/* CoDel control_law is t + interval/sqrt(count)
 * We maintain in rec_inv_sqrt the reciprocal value of sqrt(count) to avoid
 * both sqrt() and divide operation.
 */
static ktime_t cobalt_control(ktime_t t,
                              u64 interval,
                              u32 rec_inv_sqrt)
{
        return ktime_add_ns(t, reciprocal_scale(interval,
                                                rec_inv_sqrt));
}

/* Call this when a packet had to be dropped due to queue overflow.  Returns
 * true if the BLUE state was quiescent before but active after this call.
 */
static bool cobalt_queue_full(struct cobalt_vars *vars,
                              struct cobalt_params *p,
                              ktime_t now)
{
        bool up = false;

        if (ktime_to_ns(ktime_sub(now, vars->blue_timer)) > p->target) {
                up = !vars->p_drop;
                vars->p_drop += p->p_inc;
                if (vars->p_drop < p->p_inc)
                        vars->p_drop = ~0;
                vars->blue_timer = now;
        }
        vars->dropping = true;
        vars->drop_next = now;
        if (!vars->count)
                vars->count = 1;

        return up;
}

/* Call this when the queue was serviced but turned out to be empty.  Returns
 * true if the BLUE state was active before but quiescent after this call.
 */
static bool cobalt_queue_empty(struct cobalt_vars *vars,
                               struct cobalt_params *p,
                               ktime_t now)
{
        bool down = false;

        if (vars->p_drop &&
            ktime_to_ns(ktime_sub(now, vars->blue_timer)) > p->target) {
                if (vars->p_drop < p->p_dec)
                        vars->p_drop = 0;
                else
                        vars->p_drop -= p->p_dec;
                vars->blue_timer = now;
                down = !vars->p_drop;
        }
        vars->dropping = false;

        if (vars->count && ktime_to_ns(ktime_sub(now, vars->drop_next)) >= 0) {
                vars->count--;
                cobalt_invsqrt(vars);
                vars->drop_next = cobalt_control(vars->drop_next,
                                                 p->interval,
                                                 vars->rec_inv_sqrt);
        }

        return down;
}

/* Call this with a freshly dequeued packet for possible congestion marking.
 * Returns true as an instruction to drop the packet, false for delivery.
 */
static bool cobalt_should_drop(struct cobalt_vars *vars,
                               struct cobalt_params *p,
                               ktime_t now,
                               struct sk_buff *skb,
                               u32 bulk_flows)
{
        bool next_due, over_target, drop = false;
        ktime_t schedule;
        u64 sojourn;

/* The 'schedule' variable records, in its sign, whether 'now' is before or
 * after 'drop_next'.  This allows 'drop_next' to be updated before the next
 * scheduling decision is actually branched, without destroying that
 * information.  Similarly, the first 'schedule' value calculated is preserved
 * in the boolean 'next_due'.
 *
 * As for 'drop_next', we take advantage of the fact that 'interval' is both
 * the delay between first exceeding 'target' and the first signalling event,
 * *and* the scaling factor for the signalling frequency.  It's therefore very
 * natural to use a single mechanism for both purposes, and eliminates a
 * significant amount of reference Codel's spaghetti code.  To help with this,
 * both the '0' and '1' entries in the invsqrt cache are 0xFFFFFFFF, as close
 * as possible to 1.0 in fixed-point.
 */

        sojourn = ktime_to_ns(ktime_sub(now, cobalt_get_enqueue_time(skb)));
        schedule = ktime_sub(now, vars->drop_next);
        over_target = sojourn > p->target &&
                      sojourn > p->mtu_time * bulk_flows * 2 &&
                      sojourn > p->mtu_time * 4;
        next_due = vars->count && ktime_to_ns(schedule) >= 0;

        vars->ecn_marked = false;

        if (over_target) {
                if (!vars->dropping) {
                        vars->dropping = true;
                        vars->drop_next = cobalt_control(now,
                                                         p->interval,
                                                         vars->rec_inv_sqrt);
                }
                if (!vars->count)
                        vars->count = 1;
        } else if (vars->dropping) {
                vars->dropping = false;
        }

        if (next_due && vars->dropping) {
                /* Use ECN mark if possible, otherwise drop */
                drop = !(vars->ecn_marked = INET_ECN_set_ce(skb));

                vars->count++;
                if (!vars->count)
                        vars->count--;
                cobalt_invsqrt(vars);
                vars->drop_next = cobalt_control(vars->drop_next,
                                                 p->interval,
                                                 vars->rec_inv_sqrt);
                schedule = ktime_sub(now, vars->drop_next);
        } else {
                while (next_due) {
                        vars->count--;
                        cobalt_invsqrt(vars);
                        vars->drop_next = cobalt_control(vars->drop_next,
                                                         p->interval,
                                                         vars->rec_inv_sqrt);
                        schedule = ktime_sub(now, vars->drop_next);
                        next_due = vars->count && ktime_to_ns(schedule) >= 0;
                }
        }

        /* Simple BLUE implementation.  Lack of ECN is deliberate. */
        if (vars->p_drop)
                drop |= (prandom_u32() < vars->p_drop);

        /* Overload the drop_next field as an activity timeout */
        if (!vars->count)
                vars->drop_next = ktime_add_ns(now, p->interval);
        else if (ktime_to_ns(schedule) > 0 && !drop)
                vars->drop_next = now;

        return drop;
}

static bool cake_update_flowkeys(struct flow_keys *keys,
                                 const struct sk_buff *skb)
{
#if IS_ENABLED(CONFIG_NF_CONNTRACK)
        struct nf_conntrack_tuple tuple = {};
        bool rev = !skb->_nfct, upd = false;
        __be32 ip;

        if (skb_protocol(skb, true) != htons(ETH_P_IP))
                return false;

        if (!nf_ct_get_tuple_skb(&tuple, skb))
                return false;

        ip = rev ? tuple.dst.u3.ip : tuple.src.u3.ip;
        if (ip != keys->addrs.v4addrs.src) {
                keys->addrs.v4addrs.src = ip;
                upd = true;
        }
        ip = rev ? tuple.src.u3.ip : tuple.dst.u3.ip;
        if (ip != keys->addrs.v4addrs.dst) {
                keys->addrs.v4addrs.dst = ip;
                upd = true;
        }

        if (keys->ports.ports) {
                __be16 port;

                port = rev ? tuple.dst.u.all : tuple.src.u.all;
                if (port != keys->ports.src) {
                        keys->ports.src = port;
                        upd = true;
                }
                port = rev ? tuple.src.u.all : tuple.dst.u.all;
                if (port != keys->ports.dst) {
                        port = keys->ports.dst;
                        upd = true;
                }
        }
        return upd;
#else
        return false;
#endif
}

/* Cake has several subtle multiple bit settings. In these cases you
 *  would be matching triple isolate mode as well.
 */

static bool cake_dsrc(int flow_mode)
{
        return (flow_mode & CAKE_FLOW_DUAL_SRC) == CAKE_FLOW_DUAL_SRC;
}

static bool cake_ddst(int flow_mode)
{
        return (flow_mode & CAKE_FLOW_DUAL_DST) == CAKE_FLOW_DUAL_DST;
}

static u32 cake_hash(struct cake_tin_data *q, const struct sk_buff *skb,
                     int flow_mode, u16 flow_override, u16 host_override)
{
        bool hash_flows = (!flow_override && !!(flow_mode & CAKE_FLOW_FLOWS));
        bool hash_hosts = (!host_override && !!(flow_mode & CAKE_FLOW_HOSTS));
        bool nat_enabled = !!(flow_mode & CAKE_FLOW_NAT_FLAG);
        u32 flow_hash = 0, srchost_hash = 0, dsthost_hash = 0;
        u16 reduced_hash, srchost_idx, dsthost_idx;
        struct flow_keys keys, host_keys;
        bool use_skbhash = skb->l4_hash;

        if (unlikely(flow_mode == CAKE_FLOW_NONE))
                return 0;

        /* If both overrides are set, or we can use the SKB hash and nat mode is
         * disabled, we can skip packet dissection entirely. If nat mode is
         * enabled there's another check below after doing the conntrack lookup.
         */
        if ((!hash_flows || (use_skbhash && !nat_enabled)) && !hash_hosts)
                goto skip_hash;

        skb_flow_dissect_flow_keys(skb, &keys,
                                   FLOW_DISSECTOR_F_STOP_AT_FLOW_LABEL);

        /* Don't use the SKB hash if we change the lookup keys from conntrack */
        if (nat_enabled && cake_update_flowkeys(&keys, skb))
                use_skbhash = false;

        /* If we can still use the SKB hash and don't need the host hash, we can
         * skip the rest of the hashing procedure
         */
        if (use_skbhash && !hash_hosts)
                goto skip_hash;

        /* flow_hash_from_keys() sorts the addresses by value, so we have
         * to preserve their order in a separate data structure to treat
         * src and dst host addresses as independently selectable.
         */
        host_keys = keys;
        host_keys.ports.ports     = 0;
        host_keys.basic.ip_proto  = 0;
        host_keys.keyid.keyid     = 0;
        host_keys.tags.flow_label = 0;

        switch (host_keys.control.addr_type) {
        case FLOW_DISSECTOR_KEY_IPV4_ADDRS:
                host_keys.addrs.v4addrs.src = 0;
                dsthost_hash = flow_hash_from_keys(&host_keys);
                host_keys.addrs.v4addrs.src = keys.addrs.v4addrs.src;
                host_keys.addrs.v4addrs.dst = 0;
                srchost_hash = flow_hash_from_keys(&host_keys);
                break;

        case FLOW_DISSECTOR_KEY_IPV6_ADDRS:
                memset(&host_keys.addrs.v6addrs.src, 0,
                       sizeof(host_keys.addrs.v6addrs.src));
                dsthost_hash = flow_hash_from_keys(&host_keys);
                host_keys.addrs.v6addrs.src = keys.addrs.v6addrs.src;
                memset(&host_keys.addrs.v6addrs.dst, 0,
                       sizeof(host_keys.addrs.v6addrs.dst));
                srchost_hash = flow_hash_from_keys(&host_keys);
                break;

        default:
                dsthost_hash = 0;
                srchost_hash = 0;
        }

        /* This *must* be after the above switch, since as a
         * side-effect it sorts the src and dst addresses.
         */
        if (hash_flows && !use_skbhash)
                flow_hash = flow_hash_from_keys(&keys);

skip_hash:
        if (flow_override)
                flow_hash = flow_override - 1;
        else if (use_skbhash)
                flow_hash = skb->hash;
        if (host_override) {
                dsthost_hash = host_override - 1;
                srchost_hash = host_override - 1;
        }

        if (!(flow_mode & CAKE_FLOW_FLOWS)) {
                if (flow_mode & CAKE_FLOW_SRC_IP)
                        flow_hash ^= srchost_hash;

                if (flow_mode & CAKE_FLOW_DST_IP)
                        flow_hash ^= dsthost_hash;
        }

        reduced_hash = flow_hash % CAKE_QUEUES;

        /* set-associative hashing */
        /* fast path if no hash collision (direct lookup succeeds) */
        if (likely(q->tags[reduced_hash] == flow_hash &&
                   q->flows[reduced_hash].set)) {
                q->way_directs++;
        } else {
                u32 inner_hash = reduced_hash % CAKE_SET_WAYS;
                u32 outer_hash = reduced_hash - inner_hash;
                bool allocate_src = false;
                bool allocate_dst = false;
                u32 i, k;

                /* check if any active queue in the set is reserved for
                 * this flow.
                 */
                for (i = 0, k = inner_hash; i < CAKE_SET_WAYS;
                     i++, k = (k + 1) % CAKE_SET_WAYS) {
                        if (q->tags[outer_hash + k] == flow_hash) {
                                if (i)
                                        q->way_hits++;

                                if (!q->flows[outer_hash + k].set) {
                                        /* need to increment host refcnts */
                                        allocate_src = cake_dsrc(flow_mode);
                                        allocate_dst = cake_ddst(flow_mode);
                                }

                                goto found;
                        }
                }

                /* no queue is reserved for this flow, look for an
                 * empty one.
                 */
                for (i = 0; i < CAKE_SET_WAYS;
                         i++, k = (k + 1) % CAKE_SET_WAYS) {
                        if (!q->flows[outer_hash + k].set) {
                                q->way_misses++;
                                allocate_src = cake_dsrc(flow_mode);
                                allocate_dst = cake_ddst(flow_mode);
                                goto found;
                        }
                }

                /* With no empty queues, default to the original
                 * queue, accept the collision, update the host tags.
                 */
                q->way_collisions++;
                if (q->flows[outer_hash + k].set == CAKE_SET_BULK) {
                        q->hosts[q->flows[reduced_hash].srchost].srchost_bulk_flow_count--;
                        q->hosts[q->flows[reduced_hash].dsthost].dsthost_bulk_flow_count--;
                }
                allocate_src = cake_dsrc(flow_mode);
                allocate_dst = cake_ddst(flow_mode);
found:
                /* reserve queue for future packets in same flow */
                reduced_hash = outer_hash + k;
                q->tags[reduced_hash] = flow_hash;

                if (allocate_src) {
                        srchost_idx = srchost_hash % CAKE_QUEUES;
                        inner_hash = srchost_idx % CAKE_SET_WAYS;
                        outer_hash = srchost_idx - inner_hash;
                        for (i = 0, k = inner_hash; i < CAKE_SET_WAYS;
                                i++, k = (k + 1) % CAKE_SET_WAYS) {
                                if (q->hosts[outer_hash + k].srchost_tag ==
                                    srchost_hash)
                                        goto found_src;
                        }
                        for (i = 0; i < CAKE_SET_WAYS;
                                i++, k = (k + 1) % CAKE_SET_WAYS) {
                                if (!q->hosts[outer_hash + k].srchost_bulk_flow_count)
                                        break;
                        }
                        q->hosts[outer_hash + k].srchost_tag = srchost_hash;
found_src:
                        srchost_idx = outer_hash + k;
                        if (q->flows[reduced_hash].set == CAKE_SET_BULK)
                                q->hosts[srchost_idx].srchost_bulk_flow_count++;
                        q->flows[reduced_hash].srchost = srchost_idx;
                }

                if (allocate_dst) {
                        dsthost_idx = dsthost_hash % CAKE_QUEUES;
                        inner_hash = dsthost_idx % CAKE_SET_WAYS;
                        outer_hash = dsthost_idx - inner_hash;
                        for (i = 0, k = inner_hash; i < CAKE_SET_WAYS;
                             i++, k = (k + 1) % CAKE_SET_WAYS) {
                                if (q->hosts[outer_hash + k].dsthost_tag ==
                                    dsthost_hash)
                                        goto found_dst;
                        }
                        for (i = 0; i < CAKE_SET_WAYS;
                             i++, k = (k + 1) % CAKE_SET_WAYS) {
                                if (!q->hosts[outer_hash + k].dsthost_bulk_flow_count)
                                        break;
                        }
                        q->hosts[outer_hash + k].dsthost_tag = dsthost_hash;
found_dst:
                        dsthost_idx = outer_hash + k;
                        if (q->flows[reduced_hash].set == CAKE_SET_BULK)
                                q->hosts[dsthost_idx].dsthost_bulk_flow_count++;
                        q->flows[reduced_hash].dsthost = dsthost_idx;
                }
        }

        return reduced_hash;
}

/* helper functions : might be changed when/if skb use a standard list_head */
/* remove one skb from head of slot queue */

static struct sk_buff *dequeue_head(struct cake_flow *flow)
{
        struct sk_buff *skb = flow->head;

        if (skb) {
                flow->head = skb->next;
                skb_mark_not_on_list(skb);
        }

        return skb;
}

/* add skb to flow queue (tail add) */

static void flow_queue_add(struct cake_flow *flow, struct sk_buff *skb)
{
        if (!flow->head)
                flow->head = skb;
        else
                flow->tail->next = skb;
        flow->tail = skb;
        skb->next = NULL;
}

static struct iphdr *cake_get_iphdr(const struct sk_buff *skb,
                                    struct ipv6hdr *buf)
{
        unsigned int offset = skb_network_offset(skb);
        struct iphdr *iph;

        iph = skb_header_pointer(skb, offset, sizeof(struct iphdr), buf);

        if (!iph)
                return NULL;

        if (iph->version == 4 && iph->protocol == IPPROTO_IPV6)
                return skb_header_pointer(skb, offset + iph->ihl * 4,
                                          sizeof(struct ipv6hdr), buf);

        else if (iph->version == 4)
                return iph;

        else if (iph->version == 6)
                return skb_header_pointer(skb, offset, sizeof(struct ipv6hdr),
                                          buf);

        return NULL;
}

static struct tcphdr *cake_get_tcphdr(const struct sk_buff *skb,
                                      void *buf, unsigned int bufsize)
{
        unsigned int offset = skb_network_offset(skb);
        const struct ipv6hdr *ipv6h;
        const struct tcphdr *tcph;
        const struct iphdr *iph;
        struct ipv6hdr _ipv6h;
        struct tcphdr _tcph;

        ipv6h = skb_header_pointer(skb, offset, sizeof(_ipv6h), &_ipv6h);

        if (!ipv6h)
                return NULL;

        if (ipv6h->version == 4) {
                iph = (struct iphdr *)ipv6h;
                offset += iph->ihl * 4;

                /* special-case 6in4 tunnelling, as that is a common way to get
                 * v6 connectivity in the home
                 */
                if (iph->protocol == IPPROTO_IPV6) {
                        ipv6h = skb_header_pointer(skb, offset,
                                                   sizeof(_ipv6h), &_ipv6h);

                        if (!ipv6h || ipv6h->nexthdr != IPPROTO_TCP)
                                return NULL;

                        offset += sizeof(struct ipv6hdr);

                } else if (iph->protocol != IPPROTO_TCP) {
                        return NULL;
                }

        } else if (ipv6h->version == 6) {
                if (ipv6h->nexthdr != IPPROTO_TCP)
                        return NULL;

                offset += sizeof(struct ipv6hdr);
        } else {
                return NULL;
        }

        tcph = skb_header_pointer(skb, offset, sizeof(_tcph), &_tcph);
        if (!tcph)
                return NULL;

        return skb_header_pointer(skb, offset,
                                  min(__tcp_hdrlen(tcph), bufsize), buf);
}

static const void *cake_get_tcpopt(const struct tcphdr *tcph,
                                   int code, int *oplen)
{
        /* inspired by tcp_parse_options in tcp_input.c */
        int length = __tcp_hdrlen(tcph) - sizeof(struct tcphdr);
        const u8 *ptr = (const u8 *)(tcph + 1);

        while (length > 0) {
                int opcode = *ptr++;
                int opsize;

                if (opcode == TCPOPT_EOL)
                        break;
                if (opcode == TCPOPT_NOP) {
                        length--;
                        continue;
                }
                opsize = *ptr++;
                if (opsize < 2 || opsize > length)
                        break;

                if (opcode == code) {
                        *oplen = opsize;
                        return ptr;
                }

                ptr += opsize - 2;
                length -= opsize;
        }

        return NULL;
}

/* Compare two SACK sequences. A sequence is considered greater if it SACKs more
 * bytes than the other. In the case where both sequences ACKs bytes that the
 * other doesn't, A is considered greater. DSACKs in A also makes A be
 * considered greater.
 *
 * @return -1, 0 or 1 as normal compare functions
 */
static int cake_tcph_sack_compare(const struct tcphdr *tcph_a,
                                  const struct tcphdr *tcph_b)
{
        const struct tcp_sack_block_wire *sack_a, *sack_b;
        u32 ack_seq_a = ntohl(tcph_a->ack_seq);
        u32 bytes_a = 0, bytes_b = 0;
        int oplen_a, oplen_b;
        bool first = true;

        sack_a = cake_get_tcpopt(tcph_a, TCPOPT_SACK, &oplen_a);
        sack_b = cake_get_tcpopt(tcph_b, TCPOPT_SACK, &oplen_b);

        /* pointers point to option contents */
        oplen_a -= TCPOLEN_SACK_BASE;
        oplen_b -= TCPOLEN_SACK_BASE;

        if (sack_a && oplen_a >= sizeof(*sack_a) &&
            (!sack_b || oplen_b < sizeof(*sack_b)))
                return -1;
        else if (sack_b && oplen_b >= sizeof(*sack_b) &&
                 (!sack_a || oplen_a < sizeof(*sack_a)))
                return 1;
        else if ((!sack_a || oplen_a < sizeof(*sack_a)) &&
                 (!sack_b || oplen_b < sizeof(*sack_b)))
                return 0;

        while (oplen_a >= sizeof(*sack_a)) {
                const struct tcp_sack_block_wire *sack_tmp = sack_b;
                u32 start_a = get_unaligned_be32(&sack_a->start_seq);
                u32 end_a = get_unaligned_be32(&sack_a->end_seq);
                int oplen_tmp = oplen_b;
                bool found = false;

                /* DSACK; always considered greater to prevent dropping */
                if (before(start_a, ack_seq_a))
                        return -1;

                bytes_a += end_a - start_a;

                while (oplen_tmp >= sizeof(*sack_tmp)) {
                        u32 start_b = get_unaligned_be32(&sack_tmp->start_seq);
                        u32 end_b = get_unaligned_be32(&sack_tmp->end_seq);

                        /* first time through we count the total size */
                        if (first)
                                bytes_b += end_b - start_b;

                        if (!after(start_b, start_a) && !before(end_b, end_a)) {
                                found = true;
                                if (!first)
                                        break;
                        }
                        oplen_tmp -= sizeof(*sack_tmp);
                        sack_tmp++;
                }

                if (!found)
                        return -1;

                oplen_a -= sizeof(*sack_a);
                sack_a++;
                first = false;
        }

        /* If we made it this far, all ranges SACKed by A are covered by B, so
         * either the SACKs are equal, or B SACKs more bytes.
         */
        return bytes_b > bytes_a ? 1 : 0;
}

static void cake_tcph_get_tstamp(const struct tcphdr *tcph,
                                 u32 *tsval, u32 *tsecr)
{
        const u8 *ptr;
        int opsize;

        ptr = cake_get_tcpopt(tcph, TCPOPT_TIMESTAMP, &opsize);

        if (ptr && opsize == TCPOLEN_TIMESTAMP) {
                *tsval = get_unaligned_be32(ptr);
                *tsecr = get_unaligned_be32(ptr + 4);
        }
}

static bool cake_tcph_may_drop(const struct tcphdr *tcph,
                               u32 tstamp_new, u32 tsecr_new)
{
        /* inspired by tcp_parse_options in tcp_input.c */
        int length = __tcp_hdrlen(tcph) - sizeof(struct tcphdr);
        const u8 *ptr = (const u8 *)(tcph + 1);
        u32 tstamp, tsecr;

        /* 3 reserved flags must be unset to avoid future breakage
         * ACK must be set
         * ECE/CWR are handled separately
         * All other flags URG/PSH/RST/SYN/FIN must be unset
         * 0x0FFF0000 = all TCP flags (confirm ACK=1, others zero)
         * 0x00C00000 = CWR/ECE (handled separately)
         * 0x0F3F0000 = 0x0FFF0000 & ~0x00C00000
         */
        if (((tcp_flag_word(tcph) &
              cpu_to_be32(0x0F3F0000)) != TCP_FLAG_ACK))
                return false;

        while (length > 0) {
                int opcode = *ptr++;
                int opsize;

                if (opcode == TCPOPT_EOL)
                        break;
                if (opcode == TCPOPT_NOP) {
                        length--;
                        continue;
                }
                opsize = *ptr++;
                if (opsize < 2 || opsize > length)
                        break;

                switch (opcode) {
                case TCPOPT_MD5SIG: /* doesn't influence state */
                        break;

                case TCPOPT_SACK: /* stricter checking performed later */
                        if (opsize % 8 != 2)
                                return false;
                        break;

                case TCPOPT_TIMESTAMP:
                        /* only drop timestamps lower than new */
                        if (opsize != TCPOLEN_TIMESTAMP)
                                return false;
                        tstamp = get_unaligned_be32(ptr);
                        tsecr = get_unaligned_be32(ptr + 4);
                        if (after(tstamp, tstamp_new) ||
                            after(tsecr, tsecr_new))
                                return false;
                        break;

                case TCPOPT_MSS:  /* these should only be set on SYN */
                case TCPOPT_WINDOW:
                case TCPOPT_SACK_PERM:
                case TCPOPT_FASTOPEN:
                case TCPOPT_EXP:
                default: /* don't drop if any unknown options are present */
                        return false;
                }

                ptr += opsize - 2;
                length -= opsize;
        }

        return true;
}

static struct sk_buff *cake_ack_filter(struct cake_sched_data *q,
                                       struct cake_flow *flow)
{
        bool aggressive = q->ack_filter == CAKE_ACK_AGGRESSIVE;
        struct sk_buff *elig_ack = NULL, *elig_ack_prev = NULL;
        struct sk_buff *skb_check, *skb_prev = NULL;
        const struct ipv6hdr *ipv6h, *ipv6h_check;
        unsigned char _tcph[64], _tcph_check[64];
        const struct tcphdr *tcph, *tcph_check;
        const struct iphdr *iph, *iph_check;
        struct ipv6hdr _iph, _iph_check;
        const struct sk_buff *skb;
        int seglen, num_found = 0;
        u32 tstamp = 0, tsecr = 0;
        __be32 elig_flags = 0;
        int sack_comp;

        /* no other possible ACKs to filter */
        if (flow->head == flow->tail)
                return NULL;

        skb = flow->tail;
        tcph = cake_get_tcphdr(skb, _tcph, sizeof(_tcph));
        iph = cake_get_iphdr(skb, &_iph);
        if (!tcph)
                return NULL;

        cake_tcph_get_tstamp(tcph, &tstamp, &tsecr);

        /* the 'triggering' packet need only have the ACK flag set.
         * also check that SYN is not set, as there won't be any previous ACKs.
         */
        if ((tcp_flag_word(tcph) &
             (TCP_FLAG_ACK | TCP_FLAG_SYN)) != TCP_FLAG_ACK)
                return NULL;

        /* the 'triggering' ACK is at the tail of the queue, we have already
         * returned if it is the only packet in the flow. loop through the rest
         * of the queue looking for pure ACKs with the same 5-tuple as the
         * triggering one.
         */
        for (skb_check = flow->head;
             skb_check && skb_check != skb;
             skb_prev = skb_check, skb_check = skb_check->next) {
                iph_check = cake_get_iphdr(skb_check, &_iph_check);
                tcph_check = cake_get_tcphdr(skb_check, &_tcph_check,
                                             sizeof(_tcph_check));

                /* only TCP packets with matching 5-tuple are eligible, and only
                 * drop safe headers
                 */
                if (!tcph_check || iph->version != iph_check->version ||
                    tcph_check->source != tcph->source ||
                    tcph_check->dest != tcph->dest)
                        continue;

                if (iph_check->version == 4) {
                        if (iph_check->saddr != iph->saddr ||
                            iph_check->daddr != iph->daddr)
                                continue;

                        seglen = ntohs(iph_check->tot_len) -
                                       (4 * iph_check->ihl);
                } else if (iph_check->version == 6) {
                        ipv6h = (struct ipv6hdr *)iph;
                        ipv6h_check = (struct ipv6hdr *)iph_check;

                        if (ipv6_addr_cmp(&ipv6h_check->saddr, &ipv6h->saddr) ||
                            ipv6_addr_cmp(&ipv6h_check->daddr, &ipv6h->daddr))
                                continue;

                        seglen = ntohs(ipv6h_check->payload_len);
                } else {
                        WARN_ON(1);  /* shouldn't happen */
                        continue;
                }

                /* If the ECE/CWR flags changed from the previous eligible
                 * packet in the same flow, we should no longer be dropping that
                 * previous packet as this would lose information.
                 */
                if (elig_ack && (tcp_flag_word(tcph_check) &
                                 (TCP_FLAG_ECE | TCP_FLAG_CWR)) != elig_flags) {
                        elig_ack = NULL;
                        elig_ack_prev = NULL;
                        num_found--;
                }

                /* Check TCP options and flags, don't drop ACKs with segment
                 * data, and don't drop ACKs with a higher cumulative ACK
                 * counter than the triggering packet. Check ACK seqno here to
                 * avoid parsing SACK options of packets we are going to exclude
                 * anyway.
                 */
                if (!cake_tcph_may_drop(tcph_check, tstamp, tsecr) ||
                    (seglen - __tcp_hdrlen(tcph_check)) != 0 ||
                    after(ntohl(tcph_check->ack_seq), ntohl(tcph->ack_seq)))
                        continue;

                /* Check SACK options. The triggering packet must SACK more data
                 * than the ACK under consideration, or SACK the same range but
                 * have a larger cumulative ACK counter. The latter is a
                 * pathological case, but is contained in the following check
                 * anyway, just to be safe.
                 */
                sack_comp = cake_tcph_sack_compare(tcph_check, tcph);

                if (sack_comp < 0 ||
                    (ntohl(tcph_check->ack_seq) == ntohl(tcph->ack_seq) &&
                     sack_comp == 0))
                        continue;

                /* At this point we have found an eligible pure ACK to drop; if
                 * we are in aggressive mode, we are done. Otherwise, keep
                 * searching unless this is the second eligible ACK we
                 * found.
                 *
                 * Since we want to drop ACK closest to the head of the queue,
                 * save the first eligible ACK we find, even if we need to loop
                 * again.
                 */
                if (!elig_ack) {
                        elig_ack = skb_check;
                        elig_ack_prev = skb_prev;
                        elig_flags = (tcp_flag_word(tcph_check)
                                      & (TCP_FLAG_ECE | TCP_FLAG_CWR));
                }

                if (num_found++ > 0)
                        goto found;
        }

        /* We made it through the queue without finding two eligible ACKs . If
         * we found a single eligible ACK we can drop it in aggressive mode if
         * we can guarantee that this does not interfere with ECN flag
         * information. We ensure this by dropping it only if the enqueued
         * packet is consecutive with the eligible ACK, and their flags match.
         */
        if (elig_ack && aggressive && elig_ack->next == skb &&
            (elig_flags == (tcp_flag_word(tcph) &
                            (TCP_FLAG_ECE | TCP_FLAG_CWR))))
                goto found;

        return NULL;

found:
        if (elig_ack_prev)
                elig_ack_prev->next = elig_ack->next;
        else
                flow->head = elig_ack->next;

        skb_mark_not_on_list(elig_ack);

        return elig_ack;
}

static u64 cake_ewma(u64 avg, u64 sample, u32 shift)
{
        avg -= avg >> shift;
        avg += sample >> shift;
        return avg;
}

static u32 cake_calc_overhead(struct cake_sched_data *q, u32 len, u32 off)
{
        if (q->rate_flags & CAKE_FLAG_OVERHEAD)
                len -= off;

        if (q->max_netlen < len)
                q->max_netlen = len;
        if (q->min_netlen > len)
                q->min_netlen = len;

        len += q->rate_overhead;

        if (len < q->rate_mpu)
                len = q->rate_mpu;

        if (q->atm_mode == CAKE_ATM_ATM) {
                len += 47;
                len /= 48;
                len *= 53;
        } else if (q->atm_mode == CAKE_ATM_PTM) {
                /* Add one byte per 64 bytes or part thereof.
                 * This is conservative and easier to calculate than the
                 * precise value.
                 */
                len += (len + 63) / 64;
        }

        if (q->max_adjlen < len)
                q->max_adjlen = len;
        if (q->min_adjlen > len)
                q->min_adjlen = len;

        return len;
}

static u32 cake_overhead(struct cake_sched_data *q, const struct sk_buff *skb)
{
        const struct skb_shared_info *shinfo = skb_shinfo(skb);
        unsigned int hdr_len, last_len = 0;
        u32 off = skb_network_offset(skb);
        u32 len = qdisc_pkt_len(skb);
        u16 segs = 1;

        q->avg_netoff = cake_ewma(q->avg_netoff, off << 16, 8);

        if (!shinfo->gso_size)
                return cake_calc_overhead(q, len, off);

        /* borrowed from qdisc_pkt_len_init() */
        hdr_len = skb_transport_header(skb) - skb_mac_header(skb);

        /* + transport layer */
        if (likely(shinfo->gso_type & (SKB_GSO_TCPV4 |
                                                SKB_GSO_TCPV6))) {
                const struct tcphdr *th;
                struct tcphdr _tcphdr;

                th = skb_header_pointer(skb, skb_transport_offset(skb),
                                        sizeof(_tcphdr), &_tcphdr);
                if (likely(th))
                        hdr_len += __tcp_hdrlen(th);
        } else {
                struct udphdr _udphdr;

                if (skb_header_pointer(skb, skb_transport_offset(skb),
                                       sizeof(_udphdr), &_udphdr))
                        hdr_len += sizeof(struct udphdr);
        }

        if (unlikely(shinfo->gso_type & SKB_GSO_DODGY))
                segs = DIV_ROUND_UP(skb->len - hdr_len,
                                    shinfo->gso_size);
        else
                segs = shinfo->gso_segs;

        len = shinfo->gso_size + hdr_len;
        last_len = skb->len - shinfo->gso_size * (segs - 1);

        return (cake_calc_overhead(q, len, off) * (segs - 1) +
                cake_calc_overhead(q, last_len, off));
}

static void cake_heap_swap(struct cake_sched_data *q, u16 i, u16 j)
{
        struct cake_heap_entry ii = q->overflow_heap[i];
        struct cake_heap_entry jj = q->overflow_heap[j];

        q->overflow_heap[i] = jj;
        q->overflow_heap[j] = ii;

        q->tins[ii.t].overflow_idx[ii.b] = j;
        q->tins[jj.t].overflow_idx[jj.b] = i;
}

static u32 cake_heap_get_backlog(const struct cake_sched_data *q, u16 i)
{
        struct cake_heap_entry ii = q->overflow_heap[i];

        return q->tins[ii.t].backlogs[ii.b];
}

static void cake_heapify(struct cake_sched_data *q, u16 i)
{
        static const u32 a = CAKE_MAX_TINS * CAKE_QUEUES;
        u32 mb = cake_heap_get_backlog(q, i);
        u32 m = i;

        while (m < a) {
                u32 l = m + m + 1;
                u32 r = l + 1;

                if (l < a) {
                        u32 lb = cake_heap_get_backlog(q, l);

                        if (lb > mb) {
                                m  = l;
                                mb = lb;
                        }
                }

                if (r < a) {
                        u32 rb = cake_heap_get_backlog(q, r);

                        if (rb > mb) {
                                m  = r;
                                mb = rb;
                        }
                }

                if (m != i) {
                        cake_heap_swap(q, i, m);
                        i = m;
                } else {
                        break;
                }
        }
}

static void cake_heapify_up(struct cake_sched_data *q, u16 i)
{
        while (i > 0 && i < CAKE_MAX_TINS * CAKE_QUEUES) {
                u16 p = (i - 1) >> 1;
                u32 ib = cake_heap_get_backlog(q, i);
                u32 pb = cake_heap_get_backlog(q, p);

                if (ib > pb) {
                        cake_heap_swap(q, i, p);
                        i = p;
                } else {
                        break;
                }
        }
}

static int cake_advance_shaper(struct cake_sched_data *q,
                               struct cake_tin_data *b,
                               struct sk_buff *skb,
                               ktime_t now, bool drop)
{
        u32 len = get_cobalt_cb(skb)->adjusted_len;

        /* charge packet bandwidth to this tin
         * and to the global shaper.
         */
        if (q->rate_ns) {
                u64 tin_dur = (len * b->tin_rate_ns) >> b->tin_rate_shft;
                u64 global_dur = (len * q->rate_ns) >> q->rate_shft;
                u64 failsafe_dur = global_dur + (global_dur >> 1);

                if (ktime_before(b->time_next_packet, now))
                        b->time_next_packet = ktime_add_ns(b->time_next_packet,
                                                           tin_dur);

                else if (ktime_before(b->time_next_packet,
                                      ktime_add_ns(now, tin_dur)))
                        b->time_next_packet = ktime_add_ns(now, tin_dur);

                q->time_next_packet = ktime_add_ns(q->time_next_packet,
                                                   global_dur);
                if (!drop)
                        q->failsafe_next_packet = \
                                ktime_add_ns(q->failsafe_next_packet,
                                             failsafe_dur);
        }
        return len;
}

static unsigned int cake_drop(struct Qdisc *sch, struct sk_buff **to_free)
{
        struct cake_sched_data *q = qdisc_priv(sch);
        ktime_t now = ktime_get();
        u32 idx = 0, tin = 0, len;
        struct cake_heap_entry qq;
        struct cake_tin_data *b;
        struct cake_flow *flow;
        struct sk_buff *skb;

        if (!q->overflow_timeout) {
                int i;
                /* Build fresh max-heap */
                for (i = CAKE_MAX_TINS * CAKE_QUEUES / 2; i >= 0; i--)
                        cake_heapify(q, i);
        }
        q->overflow_timeout = 65535;

        /* select longest queue for pruning */
        qq  = q->overflow_heap[0];
        tin = qq.t;
        idx = qq.b;

        b = &q->tins[tin];
        flow = &b->flows[idx];
        skb = dequeue_head(flow);
        if (unlikely(!skb)) {
                /* heap has gone wrong, rebuild it next time */
                q->overflow_timeout = 0;
                return idx + (tin << 16);
        }

        if (cobalt_queue_full(&flow->cvars, &b->cparams, now))
                b->unresponsive_flow_count++;

        len = qdisc_pkt_len(skb);
        q->buffer_used      -= skb->truesize;
        b->backlogs[idx]    -= len;
        b->tin_backlog      -= len;
        sch->qstats.backlog -= len;
        qdisc_tree_reduce_backlog(sch, 1, len);

        flow->dropped++;
        b->tin_dropped++;
        sch->qstats.drops++;

        if (q->rate_flags & CAKE_FLAG_INGRESS)
                cake_advance_shaper(q, b, skb, now, true);

        __qdisc_drop(skb, to_free);
        sch->q.qlen--;

        cake_heapify(q, 0);

        return idx + (tin << 16);
}

static u8 cake_handle_diffserv(struct sk_buff *skb, bool wash)
{
        const int offset = skb_network_offset(skb);
        u16 *buf, buf_;
        u8 dscp;

        switch (skb_protocol(skb, true)) {
        case htons(ETH_P_IP):
                buf = skb_header_pointer(skb, offset, sizeof(buf_), &buf_);
                if (unlikely(!buf))
                        return 0;

                /* ToS is in the second byte of iphdr */
                dscp = ipv4_get_dsfield((struct iphdr *)buf) >> 2;

                if (wash && dscp) {
                        const int wlen = offset + sizeof(struct iphdr);

                        if (!pskb_may_pull(skb, wlen) ||
                            skb_try_make_writable(skb, wlen))
                                return 0;

                        ipv4_change_dsfield(ip_hdr(skb), INET_ECN_MASK, 0);
                }

                return dscp;

        case htons(ETH_P_IPV6):
                buf = skb_header_pointer(skb, offset, sizeof(buf_), &buf_);
                if (unlikely(!buf))
                        return 0;

                /* Traffic class is in the first and second bytes of ipv6hdr */
                dscp = ipv6_get_dsfield((struct ipv6hdr *)buf) >> 2;

                if (wash && dscp) {
                        const int wlen = offset + sizeof(struct ipv6hdr);

                        if (!pskb_may_pull(skb, wlen) ||
                            skb_try_make_writable(skb, wlen))
                                return 0;

                        ipv6_change_dsfield(ipv6_hdr(skb), INET_ECN_MASK, 0);
                }

                return dscp;

        case htons(ETH_P_ARP):
                return 0x38;  /* CS7 - Net Control */

        default:
                /* If there is no Diffserv field, treat as best-effort */
                return 0;
        }
}

static struct cake_tin_data *cake_select_tin(struct Qdisc *sch,
                                             struct sk_buff *skb)
{
        struct cake_sched_data *q = qdisc_priv(sch);
        u32 tin, mark;
        bool wash;
        u8 dscp;

        /* Tin selection: Default to diffserv-based selection, allow overriding
         * using firewall marks or skb->priority. Call DSCP parsing early if
         * wash is enabled, otherwise defer to below to skip unneeded parsing.
         */
        mark = (skb->mark & q->fwmark_mask) >> q->fwmark_shft;
        wash = !!(q->rate_flags & CAKE_FLAG_WASH);
        if (wash)
                dscp = cake_handle_diffserv(skb, wash);

        if (q->tin_mode == CAKE_DIFFSERV_BESTEFFORT)
                tin = 0;

        else if (mark && mark <= q->tin_cnt)
                tin = q->tin_order[mark - 1];

        else if (TC_H_MAJ(skb->priority) == sch->handle &&
                 TC_H_MIN(skb->priority) > 0 &&
                 TC_H_MIN(skb->priority) <= q->tin_cnt)
                tin = q->tin_order[TC_H_MIN(skb->priority) - 1];

        else {
                if (!wash)
                        dscp = cake_handle_diffserv(skb, wash);
                tin = q->tin_index[dscp];

                if (unlikely(tin >= q->tin_cnt))
                        tin = 0;
        }

        return &q->tins[tin];
}

static u32 cake_classify(struct Qdisc *sch, struct cake_tin_data **t,
                         struct sk_buff *skb, int flow_mode, int *qerr)
{
        struct cake_sched_data *q = qdisc_priv(sch);
        struct tcf_proto *filter;
        struct tcf_result res;
        u16 flow = 0, host = 0;
        int result;

        filter = rcu_dereference_bh(q->filter_list);
        if (!filter)
                goto hash;

        *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
        result = tcf_classify(skb, filter, &res, false);

        if (result >= 0) {
#ifdef CONFIG_NET_CLS_ACT
                switch (result) {
                case TC_ACT_STOLEN:
                case TC_ACT_QUEUED:
                case TC_ACT_TRAP:
                        *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
                        fallthrough;
                case TC_ACT_SHOT:
                        return 0;
                }
#endif
                if (TC_H_MIN(res.classid) <= CAKE_QUEUES)
                        flow = TC_H_MIN(res.classid);
                if (TC_H_MAJ(res.classid) <= (CAKE_QUEUES << 16))
                        host = TC_H_MAJ(res.classid) >> 16;
        }
hash:
        *t = cake_select_tin(sch, skb);
        return cake_hash(*t, skb, flow_mode, flow, host) + 1;
}

static void cake_reconfigure(struct Qdisc *sch);

static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch,
                        struct sk_buff **to_free)
{
        struct cake_sched_data *q = qdisc_priv(sch);
        int len = qdisc_pkt_len(skb);
        int ret;
        struct sk_buff *ack = NULL;
        ktime_t now = ktime_get();
        struct cake_tin_data *b;
        struct cake_flow *flow;
        u32 idx;

        /* choose flow to insert into */
        idx = cake_classify(sch, &b, skb, q->flow_mode, &ret);
        if (idx == 0) {
                if (ret & __NET_XMIT_BYPASS)
                        qdisc_qstats_drop(sch);
                __qdisc_drop(skb, to_free);
                return ret;
        }
        idx--;
        flow = &b->flows[idx];

        /* ensure shaper state isn't stale */
        if (!b->tin_backlog) {
                if (ktime_before(b->time_next_packet, now))
                        b->time_next_packet = now;

                if (!sch->q.qlen) {
                        if (ktime_before(q->time_next_packet, now)) {
                                q->failsafe_next_packet = now;
                                q->time_next_packet = now;
                        } else if (ktime_after(q->time_next_packet, now) &&
                                   ktime_after(q->failsafe_next_packet, now)) {
                                u64 next = \
                                        min(ktime_to_ns(q->time_next_packet),
                                            ktime_to_ns(
                                                   q->failsafe_next_packet));
                                sch->qstats.overlimits++;
                                qdisc_watchdog_schedule_ns(&q->watchdog, next);
                        }
                }
        }

        if (unlikely(len > b->max_skblen))
                b->max_skblen = len;

        if (skb_is_gso(skb) && q->rate_flags & CAKE_FLAG_SPLIT_GSO) {
                struct sk_buff *segs, *nskb;
                netdev_features_t features = netif_skb_features(skb);
                unsigned int slen = 0, numsegs = 0;

                segs = skb_gso_segment(skb, features & ~NETIF_F_GSO_MASK);
                if (IS_ERR_OR_NULL(segs))
                        return qdisc_drop(skb, sch, to_free);

                skb_list_walk_safe(segs, segs, nskb) {
                        skb_mark_not_on_list(segs);
                        qdisc_skb_cb(segs)->pkt_len = segs->len;
                        cobalt_set_enqueue_time(segs, now);
                        get_cobalt_cb(segs)->adjusted_len = cake_overhead(q,
                                                                          segs);
                        flow_queue_add(flow, segs);

                        sch->q.qlen++;
                        numsegs++;
                        slen += segs->len;
                        q->buffer_used += segs->truesize;
                        b->packets++;
                }

                /* stats */
                b->bytes            += slen;
                b->backlogs[idx]    += slen;
                b->tin_backlog      += slen;
                sch->qstats.backlog += slen;
                q->avg_window_bytes += slen;

                qdisc_tree_reduce_backlog(sch, 1-numsegs, len-slen);
                consume_skb(skb);
        } else {
                /* not splitting */
                cobalt_set_enqueue_time(skb, now);
                get_cobalt_cb(skb)->adjusted_len = cake_overhead(q, skb);
                flow_queue_add(flow, skb);

                if (q->ack_filter)
                        ack = cake_ack_filter(q, flow);

                if (ack) {
                        b->ack_drops++;
                        sch->qstats.drops++;
                        b->bytes += qdisc_pkt_len(ack);
                        len -= qdisc_pkt_len(ack);
                        q->buffer_used += skb->truesize - ack->truesize;
                        if (q->rate_flags & CAKE_FLAG_INGRESS)
                                cake_advance_shaper(q, b, ack, now, true);

                        qdisc_tree_reduce_backlog(sch, 1, qdisc_pkt_len(ack));
                        consume_skb(ack);
                } else {
                        sch->q.qlen++;
                        q->buffer_used      += skb->truesize;
                }

                /* stats */
                b->packets++;
                b->bytes            += len;
                b->backlogs[idx]    += len;
                b->tin_backlog      += len;
                sch->qstats.backlog += len;
                q->avg_window_bytes += len;
        }

        if (q->overflow_timeout)
                cake_heapify_up(q, b->overflow_idx[idx]);

        /* incoming bandwidth capacity estimate */
        if (q->rate_flags & CAKE_FLAG_AUTORATE_INGRESS) {
                u64 packet_interval = \
                        ktime_to_ns(ktime_sub(now, q->last_packet_time));

                if (packet_interval > NSEC_PER_SEC)
                        packet_interval = NSEC_PER_SEC;

                /* filter out short-term bursts, eg. wifi aggregation */
                q->avg_packet_interval = \
                        cake_ewma(q->avg_packet_interval,
                                  packet_interval,
                                  (packet_interval > q->avg_packet_interval ?
                                          2 : 8));

                q->last_packet_time = now;

                if (packet_interval > q->avg_packet_interval) {
                        u64 window_interval = \
                                ktime_to_ns(ktime_sub(now,
                                                      q->avg_window_begin));
                        u64 b = q->avg_window_bytes * (u64)NSEC_PER_SEC;

                        b = div64_u64(b, window_interval);
                        q->avg_peak_bandwidth =
                                cake_ewma(q->avg_peak_bandwidth, b,
                                          b > q->avg_peak_bandwidth ? 2 : 8);
                        q->avg_window_bytes = 0;
                        q->avg_window_begin = now;

                        if (ktime_after(now,
                                        ktime_add_ms(q->last_reconfig_time,
                                                     250))) {
                                q->rate_bps = (q->avg_peak_bandwidth * 15) >> 4;
                                cake_reconfigure(sch);
                        }
                }
        } else {
                q->avg_window_bytes = 0;
                q->last_packet_time = now;
        }

        /* flowchain */
        if (!flow->set || flow->set == CAKE_SET_DECAYING) {
                struct cake_host *srchost = &b->hosts[flow->srchost];
                struct cake_host *dsthost = &b->hosts[flow->dsthost];
                u16 host_load = 1;

                if (!flow->set) {
                        list_add_tail(&flow->flowchain, &b->new_flows);
                } else {
                        b->decaying_flow_count--;
                        list_move_tail(&flow->flowchain, &b->new_flows);
                }
                flow->set = CAKE_SET_SPARSE;
                b->sparse_flow_count++;

                if (cake_dsrc(q->flow_mode))
                        host_load = max(host_load, srchost->srchost_bulk_flow_count);

                if (cake_ddst(q->flow_mode))
                        host_load = max(host_load, dsthost->dsthost_bulk_flow_count);

                flow->deficit = (b->flow_quantum *
                                 quantum_div[host_load]) >> 16;
        } else if (flow->set == CAKE_SET_SPARSE_WAIT) {
                struct cake_host *srchost = &b->hosts[flow->srchost];
                struct cake_host *dsthost = &b->hosts[flow->dsthost];

                /* this flow was empty, accounted as a sparse flow, but actually
                 * in the bulk rotation.
                 */
                flow->set = CAKE_SET_BULK;
                b->sparse_flow_count--;
                b->bulk_flow_count++;

                if (cake_dsrc(q->flow_mode))
                        srchost->srchost_bulk_flow_count++;

                if (cake_ddst(q->flow_mode))
                        dsthost->dsthost_bulk_flow_count++;

        }

        if (q->buffer_used > q->buffer_max_used)
                q->buffer_max_used = q->buffer_used;

        if (q->buffer_used > q->buffer_limit) {
                u32 dropped = 0;

                while (q->buffer_used > q->buffer_limit) {
                        dropped++;
                        cake_drop(sch, to_free);
                }
                b->drop_overlimit += dropped;
        }
        return NET_XMIT_SUCCESS;
}

static struct sk_buff *cake_dequeue_one(struct Qdisc *sch)
{
        struct cake_sched_data *q = qdisc_priv(sch);
        struct cake_tin_data *b = &q->tins[q->cur_tin];
        struct cake_flow *flow = &b->flows[q->cur_flow];
        struct sk_buff *skb = NULL;
        u32 len;

        if (flow->head) {
                skb = dequeue_head(flow);
                len = qdisc_pkt_len(skb);
                b->backlogs[q->cur_flow] -= len;
                b->tin_backlog           -= len;
                sch->qstats.backlog      -= len;
                q->buffer_used           -= skb->truesize;
                sch->q.qlen--;

                if (q->overflow_timeout)
                        cake_heapify(q, b->overflow_idx[q->cur_flow]);
        }
        return skb;
}

/* Discard leftover packets from a tin no longer in use. */
static void cake_clear_tin(struct Qdisc *sch, u16 tin)
{
        struct cake_sched_data *q = qdisc_priv(sch);
        struct sk_buff *skb;

        q->cur_tin = tin;
        for (q->cur_flow = 0; q->cur_flow < CAKE_QUEUES; q->cur_flow++)
                while (!!(skb = cake_dequeue_one(sch)))
                        kfree_skb(skb);
}

static struct sk_buff *cake_dequeue(struct Qdisc *sch)
{
        struct cake_sched_data *q = qdisc_priv(sch);
        struct cake_tin_data *b = &q->tins[q->cur_tin];
        struct cake_host *srchost, *dsthost;
        ktime_t now = ktime_get();
        struct cake_flow *flow;
        struct list_head *head;
        bool first_flow = true;
        struct sk_buff *skb;
        u16 host_load;
        u64 delay;
        u32 len;

begin:
        if (!sch->q.qlen)
                return NULL;

        /* global hard shaper */
        if (ktime_after(q->time_next_packet, now) &&
            ktime_after(q->failsafe_next_packet, now)) {
                u64 next = min(ktime_to_ns(q->time_next_packet),
                               ktime_to_ns(q->failsafe_next_packet));

                sch->qstats.overlimits++;
                qdisc_watchdog_schedule_ns(&q->watchdog, next);
                return NULL;
        }

        /* Choose a class to work on. */
        if (!q->rate_ns) {
                /* In unlimited mode, can't rely on shaper timings, just balance
                 * with DRR
                 */
                bool wrapped = false, empty = true;

                while (b->tin_deficit < 0 ||
                       !(b->sparse_flow_count + b->bulk_flow_count)) {
                        if (b->tin_deficit <= 0)
                                b->tin_deficit += b->tin_quantum;
                        if (b->sparse_flow_count + b->bulk_flow_count)
                                empty = false;

                        q->cur_tin++;
                        b++;
                        if (q->cur_tin >= q->tin_cnt) {
                                q->cur_tin = 0;
                                b = q->tins;

                                if (wrapped) {
                                        /* It's possible for q->qlen to be
                                         * nonzero when we actually have no
                                         * packets anywhere.
                                         */
                                        if (empty)
                                                return NULL;
                                } else {
                                        wrapped = true;
                                }
                        }
                }
        } else {
                /* In shaped mode, choose:
                 * - Highest-priority tin with queue and meeting schedule, or
                 * - The earliest-scheduled tin with queue.
                 */
                ktime_t best_time = KTIME_MAX;
                int tin, best_tin = 0;

                for (tin = 0; tin < q->tin_cnt; tin++) {
                        b = q->tins + tin;
                        if ((b->sparse_flow_count + b->bulk_flow_count) > 0) {
                                ktime_t time_to_pkt = \
                                        ktime_sub(b->time_next_packet, now);

                                if (ktime_to_ns(time_to_pkt) <= 0 ||
                                    ktime_compare(time_to_pkt,
                                                  best_time) <= 0) {
                                        best_time = time_to_pkt;
                                        best_tin = tin;
                                }
                        }
                }

                q->cur_tin = best_tin;
                b = q->tins + best_tin;

                /* No point in going further if no packets to deliver. */
                if (unlikely(!(b->sparse_flow_count + b->bulk_flow_count)))
                        return NULL;
        }

retry:
        /* service this class */
        head = &b->decaying_flows;
        if (!first_flow || list_empty(head)) {
                head = &b->new_flows;
                if (list_empty(head)) {
                        head = &b->old_flows;
                        if (unlikely(list_empty(head))) {
                                head = &b->decaying_flows;
                                if (unlikely(list_empty(head)))
                                        goto begin;
                        }
                }
        }
        flow = list_first_entry(head, struct cake_flow, flowchain);
        q->cur_flow = flow - b->flows;
        first_flow = false;

        /* triple isolation (modified DRR++) */
        srchost = &b->hosts[flow->srchost];
        dsthost = &b->hosts[flow->dsthost];
        host_load = 1;

        /* flow isolation (DRR++) */
        if (flow->deficit <= 0) {
                /* Keep all flows with deficits out of the sparse and decaying
                 * rotations.  No non-empty flow can go into the decaying
                 * rotation, so they can't get deficits
                 */
                if (flow->set == CAKE_SET_SPARSE) {
                        if (flow->head) {
                                b->sparse_flow_count--;
                                b->bulk_flow_count++;

                                if (cake_dsrc(q->flow_mode))
                                        srchost->srchost_bulk_flow_count++;

                                if (cake_ddst(q->flow_mode))
                                        dsthost->dsthost_bulk_flow_count++;

                                flow->set = CAKE_SET_BULK;
                        } else {
                                /* we've moved it to the bulk rotation for
                                 * correct deficit accounting but we still want
                                 * to count it as a sparse flow, not a bulk one.
                                 */
                                flow->set = CAKE_SET_SPARSE_WAIT;
                        }
                }

                if (cake_dsrc(q->flow_mode))
                        host_load = max(host_load, srchost->srchost_bulk_flow_count);

                if (cake_ddst(q->flow_mode))
                        host_load = max(host_load, dsthost->dsthost_bulk_flow_count);

                WARN_ON(host_load > CAKE_QUEUES);

                /* The shifted prandom_u32() is a way to apply dithering to
                 * avoid accumulating roundoff errors
                 */
                flow->deficit += (b->flow_quantum * quantum_div[host_load] +
                                  (prandom_u32() >> 16)) >> 16;
                list_move_tail(&flow->flowchain, &b->old_flows);

                goto retry;
        }

        /* Retrieve a packet via the AQM */
        while (1) {
                skb = cake_dequeue_one(sch);
                if (!skb) {
                        /* this queue was actually empty */
                        if (cobalt_queue_empty(&flow->cvars, &b->cparams, now))
                                b->unresponsive_flow_count--;

                        if (flow->cvars.p_drop || flow->cvars.count ||
                            ktime_before(now, flow->cvars.drop_next)) {
                                /* keep in the flowchain until the state has
                                 * decayed to rest
                                 */
                                list_move_tail(&flow->flowchain,
                                               &b->decaying_flows);
                                if (flow->set == CAKE_SET_BULK) {
                                        b->bulk_flow_count--;

                                        if (cake_dsrc(q->flow_mode))
                                                srchost->srchost_bulk_flow_count--;

                                        if (cake_ddst(q->flow_mode))
                                                dsthost->dsthost_bulk_flow_count--;

                                        b->decaying_flow_count++;
                                } else if (flow->set == CAKE_SET_SPARSE ||
                                           flow->set == CAKE_SET_SPARSE_WAIT) {
                                        b->sparse_flow_count--;
                                        b->decaying_flow_count++;
                                }
                                flow->set = CAKE_SET_DECAYING;
                        } else {
                                /* remove empty queue from the flowchain */
                                list_del_init(&flow->flowchain);
                                if (flow->set == CAKE_SET_SPARSE ||
                                    flow->set == CAKE_SET_SPARSE_WAIT)
                                        b->sparse_flow_count--;
                                else if (flow->set == CAKE_SET_BULK) {
                                        b->bulk_flow_count--;

                                        if (cake_dsrc(q->flow_mode))
                                                srchost->srchost_bulk_flow_count--;

                                        if (cake_ddst(q->flow_mode))
                                                dsthost->dsthost_bulk_flow_count--;

                                } else
                                        b->decaying_flow_count--;

                                flow->set = CAKE_SET_NONE;
                        }
                        goto begin;
                }

                /* Last packet in queue may be marked, shouldn't be dropped */
                if (!cobalt_should_drop(&flow->cvars, &b->cparams, now, skb,
                                        (b->bulk_flow_count *
                                         !!(q->rate_flags &
                                            CAKE_FLAG_INGRESS))) ||
                    !flow->head)
                        break;

                /* drop this packet, get another one */
                if (q->rate_flags & CAKE_FLAG_INGRESS) {
                        len = cake_advance_shaper(q, b, skb,
                                                  now, true);
                        flow->deficit -= len;
                        b->tin_deficit -= len;
                }
                flow->dropped++;
                b->tin_dropped++;
                qdisc_tree_reduce_backlog(sch, 1, qdisc_pkt_len(skb));
                qdisc_qstats_drop(sch);
                kfree_skb(skb);
                if (q->rate_flags & CAKE_FLAG_INGRESS)
                        goto retry;
        }

        b->tin_ecn_mark += !!flow->cvars.ecn_marked;
        qdisc_bstats_update(sch, skb);

        /* collect delay stats */
        delay = ktime_to_ns(ktime_sub(now, cobalt_get_enqueue_time(skb)));
        b->avge_delay = cake_ewma(b->avge_delay, delay, 8);
        b->peak_delay = cake_ewma(b->peak_delay, delay,
                                  delay > b->peak_delay ? 2 : 8);
        b->base_delay = cake_ewma(b->base_delay, delay,
                                  delay < b->base_delay ? 2 : 8);

        len = cake_advance_shaper(q, b, skb, now, false);
        flow->deficit -= len;
        b->tin_deficit -= len;

        if (ktime_after(q->time_next_packet, now) && sch->q.qlen) {
                u64 next = min(ktime_to_ns(q->time_next_packet),
                               ktime_to_ns(q->failsafe_next_packet));

                qdisc_watchdog_schedule_ns(&q->watchdog, next);
        } else if (!sch->q.qlen) {
                int i;

                for (i = 0; i < q->tin_cnt; i++) {
                        if (q->tins[i].decaying_flow_count) {
                                ktime_t next = \
                                        ktime_add_ns(now,
                                                     q->tins[i].cparams.target);

                                qdisc_watchdog_schedule_ns(&q->watchdog,
                                                           ktime_to_ns(next));
                                break;
                        }
                }
        }

        if (q->overflow_timeout)
                q->overflow_timeout--;

        return skb;
}

static void cake_reset(struct Qdisc *sch)
{
        u32 c;

        for (c = 0; c < CAKE_MAX_TINS; c++)
                cake_clear_tin(sch, c);
}

static const struct nla_policy cake_policy[TCA_CAKE_MAX + 1] = {
        [TCA_CAKE_BASE_RATE64]   = { .type = NLA_U64 },
        [TCA_CAKE_DIFFSERV_MODE] = { .type = NLA_U32 },
        [TCA_CAKE_ATM]           = { .type = NLA_U32 },
        [TCA_CAKE_FLOW_MODE]     = { .type = NLA_U32 },
        [TCA_CAKE_OVERHEAD]      = { .type = NLA_S32 },
        [TCA_CAKE_RTT]           = { .type = NLA_U32 },
        [TCA_CAKE_TARGET]        = { .type = NLA_U32 },
        [TCA_CAKE_AUTORATE]      = { .type = NLA_U32 },
        [TCA_CAKE_MEMORY]        = { .type = NLA_U32 },
        [TCA_CAKE_NAT]           = { .type = NLA_U32 },
        [TCA_CAKE_RAW]           = { .type = NLA_U32 },
        [TCA_CAKE_WASH]          = { .type = NLA_U32 },
        [TCA_CAKE_MPU]           = { .type = NLA_U32 },
        [TCA_CAKE_INGRESS]       = { .type = NLA_U32 },
        [TCA_CAKE_ACK_FILTER]    = { .type = NLA_U32 },
        [TCA_CAKE_SPLIT_GSO]     = { .type = NLA_U32 },
        [TCA_CAKE_FWMARK]        = { .type = NLA_U32 },
};

static void cake_set_rate(struct cake_tin_data *b, u64 rate, u32 mtu,
                          u64 target_ns, u64 rtt_est_ns)
{
        /* convert byte-rate into time-per-byte
         * so it will always unwedge in reasonable time.
         */
        static const u64 MIN_RATE = 64;
        u32 byte_target = mtu;
        u64 byte_target_ns;
        u8  rate_shft = 0;
        u64 rate_ns = 0;

        b->flow_quantum = 1514;
        if (rate) {
                b->flow_quantum = max(min(rate >> 12, 1514ULL), 300ULL);
                rate_shft = 34;
                rate_ns = ((u64)NSEC_PER_SEC) << rate_shft;
                rate_ns = div64_u64(rate_ns, max(MIN_RATE, rate));
                while (!!(rate_ns >> 34)) {
                        rate_ns >>= 1;
                        rate_shft--;
                }
        } /* else unlimited, ie. zero delay */

        b->tin_rate_bps  = rate;
        b->tin_rate_ns   = rate_ns;
        b->tin_rate_shft = rate_shft;

        byte_target_ns = (byte_target * rate_ns) >> rate_shft;

        b->cparams.target = max((byte_target_ns * 3) / 2, target_ns);
        b->cparams.interval = max(rtt_est_ns +
                                     b->cparams.target - target_ns,
                                     b->cparams.target * 2);
        b->cparams.mtu_time = byte_target_ns;
        b->cparams.p_inc = 1 << 24; /* 1/256 */
        b->cparams.p_dec = 1 << 20; /* 1/4096 */
}

static int cake_config_besteffort(struct Qdisc *sch)
{
        struct cake_sched_data *q = qdisc_priv(sch);
        struct cake_tin_data *b = &q->tins[0];
        u32 mtu = psched_mtu(qdisc_dev(sch));
        u64 rate = q->rate_bps;

        q->tin_cnt = 1;

        q->tin_index = besteffort;
        q->tin_order = normal_order;

        cake_set_rate(b, rate, mtu,
                      us_to_ns(q->target), us_to_ns(q->interval));
        b->tin_quantum = 65535;

        return 0;
}

static int cake_config_precedence(struct Qdisc *sch)
{
        /* convert high-level (user visible) parameters into internal format */
        struct cake_sched_data *q = qdisc_priv(sch);
        u32 mtu = psched_mtu(qdisc_dev(sch));
        u64 rate = q->rate_bps;
        u32 quantum = 256;
        u32 i;

        q->tin_cnt = 8;
        q->tin_index = precedence;
        q->tin_order = normal_order;

        for (i = 0; i < q->tin_cnt; i++) {
                struct cake_tin_data *b = &q->tins[i];

                cake_set_rate(b, rate, mtu, us_to_ns(q->target),
                              us_to_ns(q->interval));

                b->tin_quantum = max_t(u16, 1U, quantum);

                /* calculate next class's parameters */
                rate  *= 7;
                rate >>= 3;

                quantum  *= 7;
                quantum >>= 3;
        }

        return 0;
}

/*      List of known Diffserv codepoints:
 *
 *      Least Effort (CS1)
 *      Best Effort (CS0)
 *      Max Reliability & LLT "Lo" (TOS1)
 *      Max Throughput (TOS2)
 *      Min Delay (TOS4)
 *      LLT "La" (TOS5)
 *      Assured Forwarding 1 (AF1x) - x3
 *      Assured Forwarding 2 (AF2x) - x3
 *      Assured Forwarding 3 (AF3x) - x3
 *      Assured Forwarding 4 (AF4x) - x3
 *      Precedence Class 2 (CS2)
 *      Precedence Class 3 (CS3)
 *      Precedence Class 4 (CS4)
 *      Precedence Class 5 (CS5)
 *      Precedence Class 6 (CS6)
 *      Precedence Class 7 (CS7)
 *      Voice Admit (VA)
 *      Expedited Forwarding (EF)

 *      Total 25 codepoints.
 */

/*      List of traffic classes in RFC 4594:
 *              (roughly descending order of contended priority)
 *              (roughly ascending order of uncontended throughput)
 *
 *      Network Control (CS6,CS7)      - routing traffic
 *      Telephony (EF,VA)         - aka. VoIP streams
 *      Signalling (CS5)               - VoIP setup
 *      Multimedia Conferencing (AF4x) - aka. video calls
 *      Realtime Interactive (CS4)     - eg. games
 *      Multimedia Streaming (AF3x)    - eg. YouTube, NetFlix, Twitch
 *      Broadcast Video (CS3)
 *      Low Latency Data (AF2x,TOS4)      - eg. database
 *      Ops, Admin, Management (CS2,TOS1) - eg. ssh
 *      Standard Service (CS0 & unrecognised codepoints)
 *      High Throughput Data (AF1x,TOS2)  - eg. web traffic
 *      Low Priority Data (CS1)           - eg. BitTorrent

 *      Total 12 traffic classes.
 */

static int cake_config_diffserv8(struct Qdisc *sch)
{
/*      Pruned list of traffic classes for typical applications:
 *
 *              Network Control          (CS6, CS7)
 *              Minimum Latency          (EF, VA, CS5, CS4)
 *              Interactive Shell        (CS2, TOS1)
 *              Low Latency Transactions (AF2x, TOS4)
 *              Video Streaming          (AF4x, AF3x, CS3)
 *              Bog Standard             (CS0 etc.)
 *              High Throughput          (AF1x, TOS2)
 *              Background Traffic       (CS1)
 *
 *              Total 8 traffic classes.
 */

        struct cake_sched_data *q = qdisc_priv(sch);
        u32 mtu = psched_mtu(qdisc_dev(sch));
        u64 rate = q->rate_bps;
        u32 quantum = 256;
        u32 i;

        q->tin_cnt = 8;

        /* codepoint to class mapping */
        q->tin_index = diffserv8;
        q->tin_order = normal_order;

        /* class characteristics */
        for (i = 0; i < q->tin_cnt; i++) {
                struct cake_tin_data *b = &q->tins[i];

                cake_set_rate(b, rate, mtu, us_to_ns(q->target),
                              us_to_ns(q->interval));

                b->tin_quantum = max_t(u16, 1U, quantum);

                /* calculate next class's parameters */
                rate  *= 7;
                rate >>= 3;

                quantum  *= 7;
                quantum >>= 3;
        }

        return 0;
}

static int cake_config_diffserv4(struct Qdisc *sch)
{
/*  Further pruned list of traffic classes for four-class system:
 *
 *          Latency Sensitive  (CS7, CS6, EF, VA, CS5, CS4)
 *          Streaming Media    (AF4x, AF3x, CS3, AF2x, TOS4, CS2, TOS1)
 *          Best Effort        (CS0, AF1x, TOS2, and those not specified)
 *          Background Traffic (CS1)
 *
 *              Total 4 traffic classes.
 */

        struct cake_sched_data *q = qdisc_priv(sch);
        u32 mtu = psched_mtu(qdisc_dev(sch));
        u64 rate = q->rate_bps;
        u32 quantum = 1024;

        q->tin_cnt = 4;

        /* codepoint to class mapping */
        q->tin_index = diffserv4;
        q->tin_order = bulk_order;

        /* class characteristics */
        cake_set_rate(&q->tins[0], rate, mtu,
                      us_to_ns(q->target), us_to_ns(q->interval));
        cake_set_rate(&q->tins[1], rate >> 4, mtu,
                      us_to_ns(q->target), us_to_ns(q->interval));
        cake_set_rate(&q->tins[2], rate >> 1, mtu,
                      us_to_ns(q->target), us_to_ns(q->interval));
        cake_set_rate(&q->tins[3], rate >> 2, mtu,
                      us_to_ns(q->target), us_to_ns(q->interval));

        /* bandwidth-sharing weights */
        q->tins[0].tin_quantum = quantum;
        q->tins[1].tin_quantum = quantum >> 4;
        q->tins[2].tin_quantum = quantum >> 1;
        q->tins[3].tin_quantum = quantum >> 2;

        return 0;
}

static int cake_config_diffserv3(struct Qdisc *sch)
{
/*  Simplified Diffserv structure with 3 tins.
 *              Low Priority            (CS1)
 *              Best Effort
 *              Latency Sensitive       (TOS4, VA, EF, CS6, CS7)
 */
        struct cake_sched_data *q = qdisc_priv(sch);
        u32 mtu = psched_mtu(qdisc_dev(sch));
        u64 rate = q->rate_bps;
        u32 quantum = 1024;

        q->tin_cnt = 3;

        /* codepoint to class mapping */
        q->tin_index = diffserv3;
        q->tin_order = bulk_order;

        /* class characteristics */
        cake_set_rate(&q->tins[0], rate, mtu,
                      us_to_ns(q->target), us_to_ns(q->interval));
        cake_set_rate(&q->tins[1], rate >> 4, mtu,
                      us_to_ns(q->target), us_to_ns(q->interval));
        cake_set_rate(&q->tins[2], rate >> 2, mtu,
                      us_to_ns(q->target), us_to_ns(q->interval));

        /* bandwidth-sharing weights */
        q->tins[0].tin_quantum = quantum;
        q->tins[1].tin_quantum = quantum >> 4;
        q->tins[2].tin_quantum = quantum >> 2;

        return 0;
}

static void cake_reconfigure(struct Qdisc *sch)
{
        struct cake_sched_data *q = qdisc_priv(sch);
        int c, ft;

        switch (q->tin_mode) {
        case CAKE_DIFFSERV_BESTEFFORT:
                ft = cake_config_besteffort(sch);
                break;

        case CAKE_DIFFSERV_PRECEDENCE:
                ft = cake_config_precedence(sch);
                break;

        case CAKE_DIFFSERV_DIFFSERV8:
                ft = cake_config_diffserv8(sch);
                break;

        case CAKE_DIFFSERV_DIFFSERV4:
                ft = cake_config_diffserv4(sch);
                break;

        case CAKE_DIFFSERV_DIFFSERV3:
        default:
                ft = cake_config_diffserv3(sch);
                break;
        }

        for (c = q->tin_cnt; c < CAKE_MAX_TINS; c++) {
                cake_clear_tin(sch, c);
                q->tins[c].cparams.mtu_time = q->tins[ft].cparams.mtu_time;
        }

        q->rate_ns   = q->tins[ft].tin_rate_ns;
        q->rate_shft = q->tins[ft].tin_rate_shft;

        if (q->buffer_config_limit) {
                q->buffer_limit = q->buffer_config_limit;
        } else if (q->rate_bps) {
                u64 t = q->rate_bps * q->interval;

                do_div(t, USEC_PER_SEC / 4);
                q->buffer_limit = max_t(u32, t, 4U << 20);
        } else {
                q->buffer_limit = ~0;
        }

        sch->flags &= ~TCQ_F_CAN_BYPASS;

        q->buffer_limit = min(q->buffer_limit,
                              max(sch->limit * psched_mtu(qdisc_dev(sch)),
                                  q->buffer_config_limit));
}

static int cake_change(struct Qdisc *sch, struct nlattr *opt,
                       struct netlink_ext_ack *extack)
{
        struct cake_sched_data *q = qdisc_priv(sch);
        struct nlattr *tb[TCA_CAKE_MAX + 1];
        int err;

        if (!opt)
                return -EINVAL;

        err = nla_parse_nested_deprecated(tb, TCA_CAKE_MAX, opt, cake_policy,
                                          extack);
        if (err < 0)
                return err;

        if (tb[TCA_CAKE_NAT]) {
#if IS_ENABLED(CONFIG_NF_CONNTRACK)
                q->flow_mode &= ~CAKE_FLOW_NAT_FLAG;
                q->flow_mode |= CAKE_FLOW_NAT_FLAG *
                        !!nla_get_u32(tb[TCA_CAKE_NAT]);
#else
                NL_SET_ERR_MSG_ATTR(extack, tb[TCA_CAKE_NAT],
                                    "No conntrack support in kernel");
                return -EOPNOTSUPP;
#endif
        }

        if (tb[TCA_CAKE_BASE_RATE64])
                q->rate_bps = nla_get_u64(tb[TCA_CAKE_BASE_RATE64]);

        if (tb[TCA_CAKE_DIFFSERV_MODE])
                q->tin_mode = nla_get_u32(tb[TCA_CAKE_DIFFSERV_MODE]);

        if (tb[TCA_CAKE_WASH]) {
                if (!!nla_get_u32(tb[TCA_CAKE_WASH]))
                        q->rate_flags |= CAKE_FLAG_WASH;
                else
                        q->rate_flags &= ~CAKE_FLAG_WASH;
        }

        if (tb[TCA_CAKE_FLOW_MODE])
                q->flow_mode = ((q->flow_mode & CAKE_FLOW_NAT_FLAG) |
                                (nla_get_u32(tb[TCA_CAKE_FLOW_MODE]) &
                                        CAKE_FLOW_MASK));

        if (tb[TCA_CAKE_ATM])
                q->atm_mode = nla_get_u32(tb[TCA_CAKE_ATM]);

        if (tb[TCA_CAKE_OVERHEAD]) {
                q->rate_overhead = nla_get_s32(tb[TCA_CAKE_OVERHEAD]);
                q->rate_flags |= CAKE_FLAG_OVERHEAD;

                q->max_netlen = 0;
                q->max_adjlen = 0;
                q->min_netlen = ~0;
                q->min_adjlen = ~0;
        }

        if (tb[TCA_CAKE_RAW]) {
                q->rate_flags &= ~CAKE_FLAG_OVERHEAD;

                q->max_netlen = 0;
                q->max_adjlen = 0;
                q->min_netlen = ~0;
                q->min_adjlen = ~0;
        }

        if (tb[TCA_CAKE_MPU])
                q->rate_mpu = nla_get_u32(tb[TCA_CAKE_MPU]);

        if (tb[TCA_CAKE_RTT]) {
                q->interval = nla_get_u32(tb[TCA_CAKE_RTT]);

                if (!q->interval)
                        q->interval = 1;
        }

        if (tb[TCA_CAKE_TARGET]) {
                q->target = nla_get_u32(tb[TCA_CAKE_TARGET]);

                if (!q->target)
                        q->target = 1;
        }

        if (tb[TCA_CAKE_AUTORATE]) {
                if (!!nla_get_u32(tb[TCA_CAKE_AUTORATE]))
                        q->rate_flags |= CAKE_FLAG_AUTORATE_INGRESS;
                else
                        q->rate_flags &= ~CAKE_FLAG_AUTORATE_INGRESS;
        }

        if (tb[TCA_CAKE_INGRESS]) {
                if (!!nla_get_u32(tb[TCA_CAKE_INGRESS]))
                        q->rate_flags |= CAKE_FLAG_INGRESS;
                else
                        q->rate_flags &= ~CAKE_FLAG_INGRESS;
        }

        if (tb[TCA_CAKE_ACK_FILTER])
                q->ack_filter = nla_get_u32(tb[TCA_CAKE_ACK_FILTER]);

        if (tb[TCA_CAKE_MEMORY])
                q->buffer_config_limit = nla_get_u32(tb[TCA_CAKE_MEMORY]);

        if (tb[TCA_CAKE_SPLIT_GSO]) {
                if (!!nla_get_u32(tb[TCA_CAKE_SPLIT_GSO]))
                        q->rate_flags |= CAKE_FLAG_SPLIT_GSO;
                else
                        q->rate_flags &= ~CAKE_FLAG_SPLIT_GSO;
        }

        if (tb[TCA_CAKE_FWMARK]) {
                q->fwmark_mask = nla_get_u32(tb[TCA_CAKE_FWMARK]);
                q->fwmark_shft = q->fwmark_mask ? __ffs(q->fwmark_mask) : 0;
        }

        if (q->tins) {
                sch_tree_lock(sch);
                cake_reconfigure(sch);
                sch_tree_unlock(sch);
        }

        return 0;
}

static void cake_destroy(struct Qdisc *sch)
{
        struct cake_sched_data *q = qdisc_priv(sch);

        qdisc_watchdog_cancel(&q->watchdog);
        tcf_block_put(q->block);
        kvfree(q->tins);
}

static int cake_init(struct Qdisc *sch, struct nlattr *opt,
                     struct netlink_ext_ack *extack)
{
        struct cake_sched_data *q = qdisc_priv(sch);
        int i, j, err;

        sch->limit = 10240;
        q->tin_mode = CAKE_DIFFSERV_DIFFSERV3;
        q->flow_mode  = CAKE_FLOW_TRIPLE;

        q->rate_bps = 0; /* unlimited by default */

        q->interval = 100000; /* 100ms default */
        q->target   =   5000; /* 5ms: codel RFC argues
                               * for 5 to 10% of interval
                               */
        q->rate_flags |= CAKE_FLAG_SPLIT_GSO;
        q->cur_tin = 0;
        q->cur_flow  = 0;

        qdisc_watchdog_init(&q->watchdog, sch);

        if (opt) {
                err = cake_change(sch, opt, extack);

                if (err)
                        return err;
        }

        err = tcf_block_get(&q->block, &q->filter_list, sch, extack);
        if (err)
                return err;

        quantum_div[0] = ~0;
        for (i = 1; i <= CAKE_QUEUES; i++)
                quantum_div[i] = 65535 / i;

        q->tins = kvcalloc(CAKE_MAX_TINS, sizeof(struct cake_tin_data),
                           GFP_KERNEL);
        if (!q->tins)
                goto nomem;

        for (i = 0; i < CAKE_MAX_TINS; i++) {
                struct cake_tin_data *b = q->tins + i;

                INIT_LIST_HEAD(&b->new_flows);
                INIT_LIST_HEAD(&b->old_flows);
                INIT_LIST_HEAD(&b->decaying_flows);
                b->sparse_flow_count = 0;
                b->bulk_flow_count = 0;
                b->decaying_flow_count = 0;

                for (j = 0; j < CAKE_QUEUES; j++) {
                        struct cake_flow *flow = b->flows + j;
                        u32 k = j * CAKE_MAX_TINS + i;

                        INIT_LIST_HEAD(&flow->flowchain);
                        cobalt_vars_init(&flow->cvars);

                        q->overflow_heap[k].t = i;
                        q->overflow_heap[k].b = j;
                        b->overflow_idx[j] = k;
                }
        }

        cake_reconfigure(sch);
        q->avg_peak_bandwidth = q->rate_bps;
        q->min_netlen = ~0;
        q->min_adjlen = ~0;
        return 0;

nomem:
        cake_destroy(sch);
        return -ENOMEM;
}

static int cake_dump(struct Qdisc *sch, struct sk_buff *skb)
{
        struct cake_sched_data *q = qdisc_priv(sch);
        struct nlattr *opts;

        opts = nla_nest_start_noflag(skb, TCA_OPTIONS);
        if (!opts)
                goto nla_put_failure;

        if (nla_put_u64_64bit(skb, TCA_CAKE_BASE_RATE64, q->rate_bps,
                              TCA_CAKE_PAD))
                goto nla_put_failure;

        if (nla_put_u32(skb, TCA_CAKE_FLOW_MODE,
                        q->flow_mode & CAKE_FLOW_MASK))
                goto nla_put_failure;

        if (nla_put_u32(skb, TCA_CAKE_RTT, q->interval))
                goto nla_put_failure;

        if (nla_put_u32(skb, TCA_CAKE_TARGET, q->target))
                goto nla_put_failure;

        if (nla_put_u32(skb, TCA_CAKE_MEMORY, q->buffer_config_limit))
                goto nla_put_failure;

        if (nla_put_u32(skb, TCA_CAKE_AUTORATE,
                        !!(q->rate_flags & CAKE_FLAG_AUTORATE_INGRESS)))
                goto nla_put_failure;

        if (nla_put_u32(skb, TCA_CAKE_INGRESS,
                        !!(q->rate_flags & CAKE_FLAG_INGRESS)))
                goto nla_put_failure;

        if (nla_put_u32(skb, TCA_CAKE_ACK_FILTER, q->ack_filter))
                goto nla_put_failure;

        if (nla_put_u32(skb, TCA_CAKE_NAT,
                        !!(q->flow_mode & CAKE_FLOW_NAT_FLAG)))
                goto nla_put_failure;

        if (nla_put_u32(skb, TCA_CAKE_DIFFSERV_MODE, q->tin_mode))
                goto nla_put_failure;

        if (nla_put_u32(skb, TCA_CAKE_WASH,
                        !!(q->rate_flags & CAKE_FLAG_WASH)))
                goto nla_put_failure;

        if (nla_put_u32(skb, TCA_CAKE_OVERHEAD, q->rate_overhead))
                goto nla_put_failure;

        if (!(q->rate_flags & CAKE_FLAG_OVERHEAD))
                if (nla_put_u32(skb, TCA_CAKE_RAW, 0))
                        goto nla_put_failure;

        if (nla_put_u32(skb, TCA_CAKE_ATM, q->atm_mode))
                goto nla_put_failure;

        if (nla_put_u32(skb, TCA_CAKE_MPU, q->rate_mpu))
                goto nla_put_failure;

        if (nla_put_u32(skb, TCA_CAKE_SPLIT_GSO,
                        !!(q->rate_flags & CAKE_FLAG_SPLIT_GSO)))
                goto nla_put_failure;

        if (nla_put_u32(skb, TCA_CAKE_FWMARK, q->fwmark_mask))
                goto nla_put_failure;

        return nla_nest_end(skb, opts);

nla_put_failure:
        return -1;
}

static int cake_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
{
        struct nlattr *stats = nla_nest_start_noflag(d->skb, TCA_STATS_APP);
        struct cake_sched_data *q = qdisc_priv(sch);
        struct nlattr *tstats, *ts;
        int i;

        if (!stats)
                return -1;

#define PUT_STAT_U32(attr, data) do {                                  \
                if (nla_put_u32(d->skb, TCA_CAKE_STATS_ ## attr, data)) \
                        goto nla_put_failure;                          \
        } while (0)
#define PUT_STAT_U64(attr, data) do {                                  \
                if (nla_put_u64_64bit(d->skb, TCA_CAKE_STATS_ ## attr, \
                                        data, TCA_CAKE_STATS_PAD)) \
                        goto nla_put_failure;                          \
        } while (0)

        PUT_STAT_U64(CAPACITY_ESTIMATE64, q->avg_peak_bandwidth);
        PUT_STAT_U32(MEMORY_LIMIT, q->buffer_limit);
        PUT_STAT_U32(MEMORY_USED, q->buffer_max_used);
        PUT_STAT_U32(AVG_NETOFF, ((q->avg_netoff + 0x8000) >> 16));
        PUT_STAT_U32(MAX_NETLEN, q->max_netlen);
        PUT_STAT_U32(MAX_ADJLEN, q->max_adjlen);
        PUT_STAT_U32(MIN_NETLEN, q->min_netlen);
        PUT_STAT_U32(MIN_ADJLEN, q->min_adjlen);

#undef PUT_STAT_U32
#undef PUT_STAT_U64

        tstats = nla_nest_start_noflag(d->skb, TCA_CAKE_STATS_TIN_STATS);
        if (!tstats)
                goto nla_put_failure;

#define PUT_TSTAT_U32(attr, data) do {                                  \
                if (nla_put_u32(d->skb, TCA_CAKE_TIN_STATS_ ## attr, data)) \
                        goto nla_put_failure;                           \
        } while (0)
#define PUT_TSTAT_U64(attr, data) do {                                  \
                if (nla_put_u64_64bit(d->skb, TCA_CAKE_TIN_STATS_ ## attr, \
                                        data, TCA_CAKE_TIN_STATS_PAD))  \
                        goto nla_put_failure;                           \
        } while (0)

        for (i = 0; i < q->tin_cnt; i++) {
                struct cake_tin_data *b = &q->tins[q->tin_order[i]];

                ts = nla_nest_start_noflag(d->skb, i + 1);
                if (!ts)
                        goto nla_put_failure;

                PUT_TSTAT_U64(THRESHOLD_RATE64, b->tin_rate_bps);
                PUT_TSTAT_U64(SENT_BYTES64, b->bytes);
                PUT_TSTAT_U32(BACKLOG_BYTES, b->tin_backlog);

                PUT_TSTAT_U32(TARGET_US,
                              ktime_to_us(ns_to_ktime(b->cparams.target)));
                PUT_TSTAT_U32(INTERVAL_US,
                              ktime_to_us(ns_to_ktime(b->cparams.interval)));

                PUT_TSTAT_U32(SENT_PACKETS, b->packets);
                PUT_TSTAT_U32(DROPPED_PACKETS, b->tin_dropped);
                PUT_TSTAT_U32(ECN_MARKED_PACKETS, b->tin_ecn_mark);
                PUT_TSTAT_U32(ACKS_DROPPED_PACKETS, b->ack_drops);

                PUT_TSTAT_U32(PEAK_DELAY_US,
                              ktime_to_us(ns_to_ktime(b->peak_delay)));
                PUT_TSTAT_U32(AVG_DELAY_US,
                              ktime_to_us(ns_to_ktime(b->avge_delay)));
                PUT_TSTAT_U32(BASE_DELAY_US,
                              ktime_to_us(ns_to_ktime(b->base_delay)));

                PUT_TSTAT_U32(WAY_INDIRECT_HITS, b->way_hits);
                PUT_TSTAT_U32(WAY_MISSES, b->way_misses);
                PUT_TSTAT_U32(WAY_COLLISIONS, b->way_collisions);

                PUT_TSTAT_U32(SPARSE_FLOWS, b->sparse_flow_count +
                                            b->decaying_flow_count);
                PUT_TSTAT_U32(BULK_FLOWS, b->bulk_flow_count);
                PUT_TSTAT_U32(UNRESPONSIVE_FLOWS, b->unresponsive_flow_count);
                PUT_TSTAT_U32(MAX_SKBLEN, b->max_skblen);

                PUT_TSTAT_U32(FLOW_QUANTUM, b->flow_quantum);
                nla_nest_end(d->skb, ts);
        }

#undef PUT_TSTAT_U32
#undef PUT_TSTAT_U64

        nla_nest_end(d->skb, tstats);
        return nla_nest_end(d->skb, stats);

nla_put_failure:
        nla_nest_cancel(d->skb, stats);
        return -1;
}

static struct Qdisc *cake_leaf(struct Qdisc *sch, unsigned long arg)
{
        return NULL;
}

static unsigned long cake_find(struct Qdisc *sch, u32 classid)
{
        return 0;
}

static unsigned long cake_bind(struct Qdisc *sch, unsigned long parent,
                               u32 classid)
{
        return 0;
}

static void cake_unbind(struct Qdisc *q, unsigned long cl)
{
}

static struct tcf_block *cake_tcf_block(struct Qdisc *sch, unsigned long cl,
                                        struct netlink_ext_ack *extack)
{
        struct cake_sched_data *q = qdisc_priv(sch);

        if (cl)
                return NULL;
        return q->block;
}

static int cake_dump_class(struct Qdisc *sch, unsigned long cl,
                           struct sk_buff *skb, struct tcmsg *tcm)
{
        tcm->tcm_handle |= TC_H_MIN(cl);
        return 0;
}

static int cake_dump_class_stats(struct Qdisc *sch, unsigned long cl,
                                 struct gnet_dump *d)
{
        struct cake_sched_data *q = qdisc_priv(sch);
        const struct cake_flow *flow = NULL;
        struct gnet_stats_queue qs = { 0 };
        struct nlattr *stats;
        u32 idx = cl - 1;

        if (idx < CAKE_QUEUES * q->tin_cnt) {
                const struct cake_tin_data *b = \
                        &q->tins[q->tin_order[idx / CAKE_QUEUES]];
                const struct sk_buff *skb;

                flow = &b->flows[idx % CAKE_QUEUES];

                if (flow->head) {
                        sch_tree_lock(sch);
                        skb = flow->head;
                        while (skb) {
                                qs.qlen++;
                                skb = skb->next;
                        }
                        sch_tree_unlock(sch);
                }
                qs.backlog = b->backlogs[idx % CAKE_QUEUES];
                qs.drops = flow->dropped;
        }
        if (gnet_stats_copy_queue(d, NULL, &qs, qs.qlen) < 0)
                return -1;
        if (flow) {
                ktime_t now = ktime_get();

                stats = nla_nest_start_noflag(d->skb, TCA_STATS_APP);
                if (!stats)
                        return -1;

#define PUT_STAT_U32(attr, data) do {                                  \
                if (nla_put_u32(d->skb, TCA_CAKE_STATS_ ## attr, data)) \
                        goto nla_put_failure;                          \
        } while (0)
#define PUT_STAT_S32(attr, data) do {                                  \
                if (nla_put_s32(d->skb, TCA_CAKE_STATS_ ## attr, data)) \
                        goto nla_put_failure;                          \
        } while (0)

                PUT_STAT_S32(DEFICIT, flow->deficit);
                PUT_STAT_U32(DROPPING, flow->cvars.dropping);
                PUT_STAT_U32(COBALT_COUNT, flow->cvars.count);
                PUT_STAT_U32(P_DROP, flow->cvars.p_drop);
                if (flow->cvars.p_drop) {
                        PUT_STAT_S32(BLUE_TIMER_US,
                                     ktime_to_us(
                                             ktime_sub(now,
                                                       flow->cvars.blue_timer)));
                }
                if (flow->cvars.dropping) {
                        PUT_STAT_S32(DROP_NEXT_US,
                                     ktime_to_us(
                                             ktime_sub(now,
                                                       flow->cvars.drop_next)));
                }

                if (nla_nest_end(d->skb, stats) < 0)
                        return -1;
        }

        return 0;

nla_put_failure:
        nla_nest_cancel(d->skb, stats);
        return -1;
}

static void cake_walk(struct Qdisc *sch, struct qdisc_walker *arg)
{
        struct cake_sched_data *q = qdisc_priv(sch);
        unsigned int i, j;

        if (arg->stop)
                return;

        for (i = 0; i < q->tin_cnt; i++) {
                struct cake_tin_data *b = &q->tins[q->tin_order[i]];

                for (j = 0; j < CAKE_QUEUES; j++) {
                        if (list_empty(&b->flows[j].flowchain) ||
                            arg->count < arg->skip) {
                                arg->count++;
                                continue;
                        }
                        if (arg->fn(sch, i * CAKE_QUEUES + j + 1, arg) < 0) {
                                arg->stop = 1;
                                break;
                        }
                        arg->count++;
                }
        }
}

static const struct Qdisc_class_ops cake_class_ops = {
        .leaf           =       cake_leaf,
        .find           =       cake_find,
        .tcf_block      =       cake_tcf_block,
        .bind_tcf       =       cake_bind,
        .unbind_tcf     =       cake_unbind,
        .dump           =       cake_dump_class,
        .dump_stats     =       cake_dump_class_stats,
        .walk           =       cake_walk,
};

static struct Qdisc_ops cake_qdisc_ops __read_mostly = {
        .cl_ops         =       &cake_class_ops,
        .id             =       "cake",
        .priv_size      =       sizeof(struct cake_sched_data),
        .enqueue        =       cake_enqueue,
        .dequeue        =       cake_dequeue,
        .peek           =       qdisc_peek_dequeued,
        .init           =       cake_init,
        .reset          =       cake_reset,
        .destroy        =       cake_destroy,
        .change         =       cake_change,
        .dump           =       cake_dump,
        .dump_stats     =       cake_dump_stats,
        .owner          =       THIS_MODULE,
};

static int __init cake_module_init(void)
{
        return register_qdisc(&cake_qdisc_ops);
}

static void __exit cake_module_exit(void)
{
        unregister_qdisc(&cake_qdisc_ops);
}

module_init(cake_module_init)
module_exit(cake_module_exit)
MODULE_AUTHOR("Jonathan Morton");
MODULE_LICENSE("Dual BSD/GPL");
MODULE_DESCRIPTION("The CAKE shaper.");