From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pg0-x235.google.com (mail-pg0-x235.google.com [IPv6:2607:f8b0:400e:c05::235]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id EF2623B2A4 for ; Tue, 21 Nov 2017 21:34:07 -0500 (EST) Received: by mail-pg0-x235.google.com with SMTP id p9so11770762pgc.8 for ; Tue, 21 Nov 2017 18:34:07 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=mounce.com.au; s=google; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=cxV7TTgQevwOODdtPqAr/UWzgLlf9x3pgxTrUeV/ulU=; b=jC/M/h6/NfIrQk5imh/+AQXHX+Q/hhOVBbxuNZknesKJGKuEBrn3PzLxSY67GHtLEm rdZgnEcQZXxijvTdCOnuq4X0Mui+p6lvIABqSMXQNESw9ANY2i4RKHJXDsxuZXIbGzyl eJMkgVeEEQFDpj21fOxwavcv7mQRCrdgdzvCsTznHOt5H1hg1lvlv7bd2N7w/Zo9/Xbn KK0l8kGoFs0Q+kYHanxf+yBZotaQ0vF7fIQBPSqBIwjvUnVuOMBeh5Yqh6yd+yRQzEhR gWXiA0hcITFvx2LRDltkTASn3C8AKxMyYvwyHlRPDfWax7ebIWdxUTfozXqcEf2HR/ii 2mWg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=cxV7TTgQevwOODdtPqAr/UWzgLlf9x3pgxTrUeV/ulU=; b=Ethp4wxzBoFFsJPrNQUqxrgO9rpeIbszm2XxMIQtpbUc+Usux5QCX2QdrDE/pg0M/Z iBiJ1t9dqR/NAekCrPDfYMs9OwRpPvcOvr3DC46s3jYzK4K2aooF61Ibaa6V1txC67dG FBYxmfksTh8yfLB0F9VJ8zlM7wn2hc9r8jH3wCFT98VDl3XwNaolKeUu2m9U1XLz3mt/ x2vCNylptsl/vq7p20S6RXbIdU8u4jiTyB0zZ8ErkhuXMRUQHyRPW52f79tGVYV0kZK+ YFgfNb3QwvlFaMi9MwHX3RpBmnyqzMvW+fA2eDYIA6G5JNXZODRehXL1aZdzzcuC5O8c 2a/g== X-Gm-Message-State: AJaThX6wOg4p+rIBqFHortlKEjfQ9zN34tw0ykzS+AZf+XRhNU+ejeJg cVS0t2HOIJrfIV3raRLufHllPkD2t71Vl6YX6fsJmA2L X-Google-Smtp-Source: AGs4zMZHJ2M6NLyfRYq7d8RXYyb3Ql7IfJ8OJo6X+MHKytpsGIOblOOQNvKnZbBtZ5Wql0tpXcZ3vvAAuidWBSVPEa4= X-Received: by 10.99.112.69 with SMTP id a5mr19012022pgn.179.1511318045494; Tue, 21 Nov 2017 18:34:05 -0800 (PST) MIME-Version: 1.0 Received: by 10.100.187.3 with HTTP; Tue, 21 Nov 2017 18:33:50 -0800 (PST) X-Originating-IP: [101.166.205.68] In-Reply-To: <87wp2jrv1f.fsf@nemesis.taht.net> References: <1511309382-24060-1-git-send-email-dave.taht@gmail.com> <1511309382-24060-3-git-send-email-dave.taht@gmail.com> <87wp2jrv1f.fsf@nemesis.taht.net> From: Ryan Mounce Date: Wed, 22 Nov 2017 13:03:50 +1030 Message-ID: To: Dave Taht Cc: Dave Taht , Cake List Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Subject: Re: [Cake] [PATCH 2/3] Add Common Applications Kept Enhanced (sch_cake) qdisc X-BeenThere: cake@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: Cake - FQ_codel the next generation List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 22 Nov 2017 02:34:08 -0000 On 22 November 2017 at 11:25, Dave Taht wrote: > > And now I can comment. > > I've added this version to a for_upstream branch in the hope that future > commits can be kept in sync. > > Is there anything more that should be added to the commit message? > Should I be less snarky? > > Dave Taht writes: > >> sch_cake is intended to squeeze the most bandwidth and lowest latency ou= t >> of even the slowest ISP links and routers, while presenting an API simpl= e >> enough that even an ISP can configure it. >> >> Example of use on an ISP uplink: >> >> tc qdisc add dev eth0 cake bandwidth 20Mbit nat docsis ack-filter >> >> Cake can also be used in unlimited mode to drive packets at the speed >> of the underlying link. >> >> Cake is filled with: >> >> * A hybrid Codel/Blue AQM algorithm, =E2=80=9CCobalt=E2=80=9D, tied to a= n FQ_Codel >> derived Flow Queuing system, which autoconfigures based on the bandwid= th. >> * A unique "triple-isolate" mode (the default) which balances per-flow >> and per-host flow FQ even through NAT. >> * An integral deficit based shaper with extensive dsl and docsis support >> that can also be used in unlimited mode. >> * 8 way set associative queuing to reduce flow collisions to a minimum. >> * A reasonable interpretation of various diffserv latency/loss tradeoffs= . >> * Support for washing diffserv for entering and exiting traffic. >> * Perfect support for interacting with Docsis 3.0 shapers. >> * Extensive support for DSL framing types. >> * (New) Support for ack filtering. >> - 20 % better throughput at a 16x1 down/up ratio on the rrul test. >> * Extensive statistics for measuring, loss, ecn markings, latency variat= ion. >> >> There are some features still considered experimental, notably the >> ingress_autorate bandwidth estimator and cobalt itself. >> >> Various versions shipping have been available as an out of tree build fo= r >> kernel versions going back to 3.10, as the embedded router world has bee= n >> running a few years behind mainline Linux. A stable version has been >> generally available on lede-17.01 and later. >> >> sch_cake replaces a combination of iptables, tc filter, htb and fq_codel= in >> the sqm-scripts, with sane defaults and vastly easier configuration. >> >> Cake's principal author is Jonathan Morton, with contributions from >> Kevin Darbyshire-Bryant, Toke H=C3=B8iland-J=C3=B8rgensen, Sebastian Moe= ller, >> Ryan Mounce, Dean Scarff, Guido Sarducci, Nils Andreas Svee, Dave T=C3= =A4ht, and >> Loganaden Velvindron. >> --- >> include/net/cobalt.h | 152 +++ >> net/sched/sch_cake.c | 2551 +++++++++++++++++++++++++++++++++++++++++++= +++++++ >> 2 files changed, 2703 insertions(+) >> create mode 100644 include/net/cobalt.h >> create mode 100644 net/sched/sch_cake.c >> >> diff --git a/include/net/cobalt.h b/include/net/cobalt.h >> new file mode 100644 >> index 0000000..0d1e794 >> --- /dev/null >> +++ b/include/net/cobalt.h >> @@ -0,0 +1,152 @@ >> +#ifndef __NET_SCHED_COBALT_H >> +#define __NET_SCHED_COBALT_H >> + >> +/* COBALT - Codel-BLUE Alternate AQM algorithm. >> + * >> + * Copyright (C) 2011-2012 Kathleen Nichols >> + * Copyright (C) 2011-2012 Van Jacobson >> + * Copyright (C) 2012 Eric Dumazet >> + * Copyright (C) 2016-2017 Michael D. T=C3=A4ht >> + * Copyright (c) 2015-2017 Jonathan Morton >> + * >> + * Redistribution and use in source and binary forms, with or without >> + * modification, are permitted provided that the following conditions >> + * are met: >> + * 1. Redistributions of source code must retain the above copyright >> + * notice, this list of conditions, and the following disclaimer, >> + * without modification. >> + * 2. Redistributions in binary form must reproduce the above copyright >> + * notice, this list of conditions and the following disclaimer in t= he >> + * documentation and/or other materials provided with the distributi= on. >> + * 3. The names of the authors may not be used to endorse or promote pr= oducts >> + * derived from this software without specific prior written permiss= ion. >> + * >> + * Alternatively, provided that this notice is retained in full, this >> + * software may be distributed under the terms of the GNU General >> + * Public License ("GPL") version 2, in which case the provisions of th= e >> + * GPL apply INSTEAD OF those given above. >> + * >> + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS >> + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT >> + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FO= R >> + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT >> + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL= , >> + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT >> + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE= , >> + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON AN= Y >> + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT >> + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE US= E >> + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH >> + * DAMAGE. >> + */ >> + >> +/* 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 effec= tive on >> + * unresponsive flows. >> + */ >> + >> +#include >> +#include >> +#include >> +#include >> +#include >> +#include >> +#include >> + >> +typedef u64 cobalt_time_t; >> +typedef s64 cobalt_tdiff_t; >> + >> +#define MS2TIME(a) (a * (u64) NSEC_PER_MSEC) >> +#define US2TIME(a) (a * (u64) NSEC_PER_USEC) >> + >> +struct cobalt_skb_cb { >> + cobalt_time_t enqueue_time; >> +}; >> + >> +static inline cobalt_time_t cobalt_get_time(void) >> +{ >> + return ktime_get_ns(); >> +} > > I don't see these typedefs as necessarily helpful in understanding > the code, just using ktime_get_ns might be saner. Can live with it. > >> +struct cake_flow { >> + /* this stuff is all needed per-flow at dequeue time */ >> + struct sk_buff *head; >> + struct sk_buff *tail; >> + struct sk_buff *ackcheck; >> + struct list_head flowchain; >> + s32 deficit; >> + struct cobalt_vars cvars; >> + u16 srchost; /* index into cake_host table */ >> + u16 dsthost; >> + u8 set; >> +}; /* please try to keep this structure <=3D 64 bytes */ > > It isn't. Can just kill the comment. It's below 64 bytes on 32-bit systems at least. > >> + >> +struct cake_host { >> + u32 srchost_tag; >> + u32 dsthost_tag; >> + u16 srchost_refcnt; >> + u16 dsthost_refcnt; >> +}; >> + >> +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 */ >> + u32 perturbation; >> + 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; >> + >> + u16 max_skblen; >> + >> + struct list_head new_flows; >> + struct list_head old_flows; >> + struct list_head decaying_flows; >> + >> + /* time_next =3D time_this + ((len * rate_ns) >> rate_shft) */ >> + u64 tin_time_next_packet; >> + u32 tin_rate_ns; >> + u32 tin_rate_bps; >> + u16 tin_rate_shft; >> + >> + u16 tin_quantum_prio; >> + u16 tin_quantum_band; >> + s32 tin_deficit; >> + u32 tin_backlog; >> + u32 tin_dropped; >> + u32 tin_ecn_mark; >> + >> + u32 packets; >> + u64 bytes; >> + >> + u32 ack_drops; >> + >> + /* moving averages */ >> + cobalt_time_t avge_delay; >> + cobalt_time_t peak_delay; >> + cobalt_time_t 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 mu= ch */ >> + >> +struct cake_sched_data { >> + 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; >> + >> + /* time_next =3D time_this + ((len * rate_ns) >> rate_shft) */ >> + u16 rate_shft; >> + u64 time_next_packet; >> + u64 failsafe_next_packet; >> + u32 rate_ns; >> + u32 rate_bps; >> + u16 rate_flags; >> + s16 rate_overhead; >> + u16 rate_mpu; >> + u32 interval; >> + u32 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 */ >> + u64 last_packet_time; >> + u64 avg_packet_interval; >> + u64 avg_window_begin; >> + u32 avg_window_bytes; >> + u32 avg_peak_bandwidth; >> + u64 last_reconfig_time; >> +}; >> + >> +enum { >> + CAKE_MODE_BESTEFFORT =3D 1, >> + CAKE_MODE_PRECEDENCE, >> + CAKE_MODE_DIFFSERV8, >> + CAKE_MODE_DIFFSERV4, >> + CAKE_MODE_LLT, >> + CAKE_MODE_DIFFSERV3, >> + CAKE_MODE_MAX >> +}; >> + >> +enum { >> + CAKE_FLAG_ATM =3D 0x0001, >> + CAKE_FLAG_PTM =3D 0x0002, >> + CAKE_FLAG_AUTORATE_INGRESS =3D 0x0010, >> + CAKE_FLAG_INGRESS =3D 0x0040, > > Why the gap? > >> + CAKE_FLAG_WASH =3D 0x0100, >> + CAKE_FLAG_ACK_FILTER =3D 0x0200, >> + CAKE_FLAG_ACK_AGGRESSIVE =3D 0x0400 >> +}; > > We could create a #define CAKE_ACK_FILTERS (CAKE_FLAG_ACK_FILTER |\ > CAKE_FLAG_ACK_AGGRESSIVE) > >> + >> +enum { >> + CAKE_FLOW_NONE =3D 0, >> + CAKE_FLOW_SRC_IP, >> + CAKE_FLOW_DST_IP, >> + CAKE_FLOW_HOSTS, /* =3D CAKE_FLOW_SRC_IP | CAKE_FLOW_DST_IP */ >> + CAKE_FLOW_FLOWS, >> + CAKE_FLOW_DUAL_SRC, /* =3D CAKE_FLOW_SRC_IP | CAKE_FLOW_FLOWS */ >> + CAKE_FLOW_DUAL_DST, /* =3D CAKE_FLOW_DST_IP | CAKE_FLOW_FLOWS */ >> + CAKE_FLOW_TRIPLE, /* =3D CAKE_FLOW_HOSTS | CAKE_FLOW_FLOWS */ >> + CAKE_FLOW_MAX, >> + CAKE_FLOW_NAT_FLAG =3D 64 >> +}; >> + >> +static u16 quantum_div[CAKE_QUEUES + 1] =3D {0}; >> + >> +/* Diffserv lookup tables */ >> + >> +static const u8 precedence[] =3D {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 diffserv_llt[] =3D {1, 0, 0, 1, 2, 2, 1, 1, >> + 3, 1, 1, 1, 1, 1, 1, 1, >> + 1, 1, 1, 1, 1, 1, 1, 1, >> + 1, 1, 1, 1, 1, 1, 1, 1, >> + 1, 1, 1, 1, 1, 1, 1, 1, >> + 1, 1, 1, 1, 2, 1, 2, 1, >> + 4, 1, 1, 1, 1, 1, 1, 1, >> + 4, 1, 1, 1, 1, 1, 1, 1, >> + }; >> + >> +static const u8 diffserv8[] =3D {2, 5, 1, 2, 4, 2, 2, 2, >> + 0, 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[] =3D {0, 2, 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[] =3D {0, 0, 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[] =3D {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[] =3D {0, 1, 2, 3, 4, 5, 6, 7}; >> +static const u8 bulk_order[] =3D {1, 0, 2, 3}; >> + >> +#define REC_INV_SQRT_CACHE (16) >> +static u32 cobalt_rec_inv_sqrt_cache[REC_INV_SQRT_CACHE] =3D {0}; >> + >> +/* http://en.wikipedia.org/wiki/Methods_of_computing_square_roots >> + * new_invsqrt =3D (invsqrt / 2) * (3 - count * invsqrt^2) >> + * >> + * Here, invsqrt is a fixed point number (< 1.0), 32bit mantissa, aka Q= 0.32 >> + */ >> + >> +static void cobalt_newton_step(struct cobalt_vars *vars) >> +{ >> + u32 invsqrt =3D vars->rec_inv_sqrt; >> + u32 invsqrt2 =3D ((u64)invsqrt * invsqrt) >> 32; >> + u64 val =3D (3LL << 32) - ((u64)vars->count * invsqrt2); >> + >> + val >>=3D 2; /* avoid overflow in following multiply */ >> + val =3D (val * invsqrt) >> (32 - 2 + 1); >> + >> + vars->rec_inv_sqrt =3D val; >> +} >> + >> +static void cobalt_invsqrt(struct cobalt_vars *vars) >> +{ >> + if (vars->count < REC_INV_SQRT_CACHE) >> + vars->rec_inv_sqrt =3D cobalt_rec_inv_sqrt_cache[vars->cou= nt]; >> + else >> + cobalt_newton_step(vars); >> +} >> + >> +/* There is a big difference in timing between the accurate values plac= ed in >> + * the cache and the approximations given by a single Newton step for s= mall >> + * count values, particularly when stepping from count 1 to 2 or vice v= ersa. >> + * 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 =3D ~0U; >> + cobalt_rec_inv_sqrt_cache[0] =3D v.rec_inv_sqrt; >> + >> + for (v.count =3D 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] =3D v.rec_inv_sqrt; >> + } >> +} >> + >> +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] =3D ~0; >> + } >> +} >> + >> +/* CoDel control_law is t + interval/sqrt(count) >> + * We maintain in rec_inv_sqrt the reciprocal value of sqrt(count) to a= void >> + * both sqrt() and divide operation. >> + */ >> +static cobalt_time_t cobalt_control_law(cobalt_time_t t, >> + cobalt_time_t interval, >> + u32 rec_inv_sqrt) >> +{ >> + return t + reciprocal_scale(interval, rec_inv_sqrt); >> +} >> + >> +/* Call this when a packet had to be dropped due to queue overflow. Re= turns >> + * true if the BLUE state was quiescent before but active after this ca= ll. >> + */ >> +bool cobalt_queue_full(struct cobalt_vars *vars, struct cobalt_params *= p, >> + cobalt_time_t now) > > oops, this should be static. > >> +{ >> + bool up =3D false; >> + >> + if ((now - vars->blue_timer) > p->target) { >> + up =3D !vars->p_drop; >> + vars->p_drop +=3D p->p_inc; >> + if (vars->p_drop < p->p_inc) >> + vars->p_drop =3D ~0; >> + vars->blue_timer =3D now; >> + } >> + vars->dropping =3D true; >> + vars->drop_next =3D now; >> + if (!vars->count) >> + vars->count =3D 1; >> + >> + return up; >> +} >> + >> +/* Call this when the queue was serviced but turned out to be empty. R= eturns >> + * true if the BLUE state was active before but quiescent after this ca= ll. >> + */ >> +bool cobalt_queue_empty(struct cobalt_vars *vars, struct cobalt_params = *p, >> + cobalt_time_t now) > > static > >> +{ >> + bool down =3D false; >> + >> + if (vars->p_drop && (now - vars->blue_timer) > p->target) { >> + if (vars->p_drop < p->p_dec) >> + vars->p_drop =3D 0; >> + else >> + vars->p_drop -=3D p->p_dec; >> + vars->blue_timer =3D now; >> + down =3D !vars->p_drop; >> + } >> + vars->dropping =3D false; >> + >> + if (vars->count && (now - vars->drop_next) >=3D 0) { >> + vars->count--; >> + cobalt_invsqrt(vars); >> + vars->drop_next =3D cobalt_control_law(vars->drop_next, >> + p->interval, >> + vars->rec_inv_sqrt); >> + } >> + >> + return down; >> +} >> + >> +/* Call this with a freshly dequeued packet for possible congestion mar= king. >> + * Returns true as an instruction to drop the packet, false for deliver= y. >> + */ >> +bool cobalt_should_drop(struct cobalt_vars *vars, >> + struct cobalt_params *p, >> + cobalt_time_t now, >> + struct sk_buff *skb) > static > >> +{ >> + bool drop =3D false; >> + >> + /* Simplified Codel implementation */ >> + cobalt_tdiff_t sojourn =3D now - cobalt_get_enqueue_time(skb); >> + >> +/* The 'schedule' variable records, in its sign, whether 'now' is befor= e 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 pr= eserved >> + * 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 therefo= re very >> + * natural to use a single mechanism for both purposes, and eliminates = a >> + * significant amount of reference Codel's spaghetti code. To help wit= h this, >> + * both the '0' and '1' entries in the invsqrt cache are 0xFFFFFFFF, as= close >> + * as possible to 1.0 in fixed-point. >> + */ >> + >> + cobalt_tdiff_t schedule =3D now - vars->drop_next; >> + bool over_target =3D sojourn > p->target; >> + bool next_due =3D vars->count && schedule >=3D 0; >> + >> + vars->ecn_marked =3D false; >> + >> + if (over_target) { >> + if (!vars->dropping) { >> + vars->dropping =3D true; >> + vars->drop_next =3D cobalt_control_law(now, >> + p->interval, >> + vars->rec_inv= _sqrt); >> + } >> + if (!vars->count) >> + vars->count =3D 1; >> + } else if (vars->dropping) { >> + vars->dropping =3D false; >> + } >> + >> + if (next_due && vars->dropping) { >> + /* Use ECN mark if possible, otherwise drop */ >> + drop =3D !(vars->ecn_marked =3D INET_ECN_set_ce(skb)); >> + >> + vars->count++; >> + if (!vars->count) >> + vars->count--; >> + cobalt_invsqrt(vars); >> + vars->drop_next =3D cobalt_control_law(vars->drop_next, >> + p->interval, >> + vars->rec_inv_sqrt); >> + schedule =3D now - vars->drop_next; >> + } else { >> + while (next_due) { >> + vars->count--; >> + cobalt_invsqrt(vars); >> + vars->drop_next =3D cobalt_control_law(vars->drop_= next, >> + p->interval, >> + vars->rec_inv= _sqrt); >> + schedule =3D now - vars->drop_next; >> + next_due =3D vars->count && schedule >=3D 0; >> + } >> + } >> + >> + /* Simple BLUE implementation. Lack of ECN is deliberate. */ >> + if (vars->p_drop) >> + drop |=3D (prandom_u32() < vars->p_drop); >> + >> + /* Overload the drop_next field as an activity timeout */ >> + if (!vars->count) >> + vars->drop_next =3D now + p->interval; >> + else if (schedule > 0 && !drop) >> + vars->drop_next =3D now; >> + >> + return drop; >> +} >> + >> +#if defined(CONFIG_NF_CONNTRACK) || defined(CONFIG_NF_CONNTRACK_MODULE) > > Oops, I meant to add IS_ENABLED(NF_CONNTRACK). How far back does that > define go? > >> +static inline void cake_update_flowkeys(struct flow_keys *keys, >> + const struct sk_buff *skb) >> +{ >> + enum ip_conntrack_info ctinfo; >> + bool rev =3D false; >> + >> + struct nf_conn *ct; >> + const struct nf_conntrack_tuple *tuple; >> + >> + if (tc_skb_protocol(skb) !=3D htons(ETH_P_IP)) >> + return; >> + >> + ct =3D nf_ct_get(skb, &ctinfo); >> + if (ct) { >> + tuple =3D nf_ct_tuple(ct, CTINFO2DIR(ctinfo)); >> + } else { >> + const struct nf_conntrack_tuple_hash *hash; >> + struct nf_conntrack_tuple srctuple; >> + >> + if (!nf_ct_get_tuplepr(skb, skb_network_offset(skb), >> + NFPROTO_IPV4, dev_net(skb->dev), >> + &srctuple)) >> + return; >> + >> + hash =3D nf_conntrack_find_get(dev_net(skb->dev), >> + &nf_ct_zone_dflt, >> + &srctuple); >> + if (!hash) >> + return; >> + >> + rev =3D true; >> + ct =3D nf_ct_tuplehash_to_ctrack(hash); >> + tuple =3D nf_ct_tuple(ct, !hash->tuple.dst.dir); >> + } >> + >> + keys->addrs.v4addrs.src =3D rev ? tuple->dst.u3.ip : tuple->src.u3= .ip; >> + keys->addrs.v4addrs.dst =3D rev ? tuple->src.u3.ip : tuple->dst.u3= .ip; >> + >> + if (keys->ports.ports) { >> + keys->ports.src =3D rev ? tuple->dst.u.all : tuple->src.u.= all; >> + keys->ports.dst =3D rev ? tuple->src.u.all : tuple->dst.u.= all; >> + } >> + >> + if (rev) >> + nf_ct_put(ct); >> +} >> +#else >> +static inline void cake_update_flowkeys(struct flow_keys *keys, >> + const struct sk_buff *skb) >> +{ >> + /* There is nothing we can do here without CONNTRACK */ >> +} >> +#endif >> + >> +static inline u32 >> +cake_hash(struct cake_tin_data *q, const struct sk_buff *skb, int flow_= mode) >> +{ >> + struct flow_keys keys, host_keys; >> + u32 flow_hash =3D 0, srchost_hash, dsthost_hash; >> + u16 reduced_hash, srchost_idx, dsthost_idx; >> + >> + if (unlikely(flow_mode =3D=3D CAKE_FLOW_NONE)) >> + return 0; >> + >> + skb_flow_dissect_flow_keys(skb, &keys, >> + FLOW_DISSECTOR_F_STOP_AT_FLOW_LABEL); >> + >> + if (flow_mode & CAKE_FLOW_NAT_FLAG) >> + cake_update_flowkeys(&keys, skb); >> + >> + /* 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 =3D keys; >> + host_keys.ports.ports =3D 0; >> + host_keys.basic.ip_proto =3D 0; >> + host_keys.keyid.keyid =3D 0; >> + host_keys.tags.flow_label =3D 0; >> + >> + switch (host_keys.control.addr_type) { >> + case FLOW_DISSECTOR_KEY_IPV4_ADDRS: >> + host_keys.addrs.v4addrs.src =3D 0; >> + dsthost_hash =3D flow_hash_from_keys(&host_keys); >> + host_keys.addrs.v4addrs.src =3D keys.addrs.v4addrs.src; >> + host_keys.addrs.v4addrs.dst =3D 0; >> + srchost_hash =3D 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 =3D flow_hash_from_keys(&host_keys); >> + host_keys.addrs.v6addrs.src =3D keys.addrs.v6addrs.src; >> + memset(&host_keys.addrs.v6addrs.dst, 0, >> + sizeof(host_keys.addrs.v6addrs.dst)); >> + srchost_hash =3D flow_hash_from_keys(&host_keys); >> + break; >> + >> + default: >> + dsthost_hash =3D 0; >> + srchost_hash =3D 0; >> + }; >> + >> + /* This *must* be after the above switch, since as a >> + * side-effect it sorts the src and dst addresses. >> + */ >> + if (flow_mode & CAKE_FLOW_FLOWS) >> + flow_hash =3D flow_hash_from_keys(&keys); >> + >> + if (!(flow_mode & CAKE_FLOW_FLOWS)) { >> + if (flow_mode & CAKE_FLOW_SRC_IP) >> + flow_hash ^=3D srchost_hash; >> + >> + if (flow_mode & CAKE_FLOW_DST_IP) >> + flow_hash ^=3D dsthost_hash; >> + } >> + >> + reduced_hash =3D flow_hash % CAKE_QUEUES; >> + srchost_idx =3D srchost_hash % CAKE_QUEUES; >> + dsthost_idx =3D dsthost_hash % CAKE_QUEUES; >> + >> + /* set-associative hashing */ >> + /* fast path if no hash collision (direct lookup succeeds) */ >> + if (likely(q->tags[reduced_hash] =3D=3D flow_hash && >> + q->flows[reduced_hash].set)) { >> + q->way_directs++; >> + } else { >> + u32 inner_hash =3D reduced_hash % CAKE_SET_WAYS; >> + u32 outer_hash =3D reduced_hash - inner_hash; >> + u32 i, k; >> + bool need_allocate_src =3D false; >> + bool need_allocate_dst =3D false; >> + >> + /* check if any active queue in the set is reserved for >> + * this flow. >> + */ >> + for (i =3D 0, k =3D inner_hash; i < CAKE_SET_WAYS; >> + i++, k =3D (k + 1) % CAKE_SET_WAYS) { >> + if (q->tags[outer_hash + k] =3D=3D flow_hash) { >> + if (i) >> + q->way_hits++; >> + >> + if (!q->flows[outer_hash + k].set) { >> + /* need to increment host refcnts = */ >> + need_allocate_src =3D true; >> + need_allocate_dst =3D true; >> + } >> + >> + goto found; >> + } >> + } >> + >> + /* no queue is reserved for this flow, look for an >> + * empty one. >> + */ >> + for (i =3D 0; i < CAKE_SET_WAYS; >> + i++, k =3D (k + 1) % CAKE_SET_WAYS) { >> + if (!q->flows[outer_hash + k].set) { >> + q->way_misses++; >> + need_allocate_src =3D true; >> + need_allocate_dst =3D true; >> + goto found; >> + } >> + } >> + >> + /* With no empty queues, default to the original >> + * queue, accept the collision, update the host tags. >> + */ >> + q->way_collisions++; >> + q->hosts[q->flows[reduced_hash].srchost].srchost_refcnt--; >> + q->hosts[q->flows[reduced_hash].dsthost].dsthost_refcnt--; >> + need_allocate_src =3D true; >> + need_allocate_dst =3D true; >> + >> +found: > > Not huge on dangling gotos, would rather move them to the below line. > >> + /* reserve queue for future packets in same flow */ >> + reduced_hash =3D outer_hash + k; >> + q->tags[reduced_hash] =3D flow_hash; >> + >> + if (need_allocate_src) { >> + inner_hash =3D srchost_idx % CAKE_SET_WAYS; >> + outer_hash =3D srchost_idx - inner_hash; >> + for (i =3D 0, k =3D inner_hash; i < CAKE_SET_WAYS; >> + i++, k =3D (k + 1) % CAKE_SET_WAYS) { >> + if (q->hosts[outer_hash + k].srchost_tag = =3D=3D >> + srchost_hash) >> + goto found_src; >> + } >> + for (i =3D 0; i < CAKE_SET_WAYS; >> + i++, k =3D (k + 1) % CAKE_SET_WAYS) { >> + if (!q->hosts[outer_hash + k].srchost_refc= nt) >> + break; >> + } >> + q->hosts[outer_hash + k].srchost_tag =3D srchost_h= ash; >> +found_src: >> + srchost_idx =3D outer_hash + k; >> + q->hosts[srchost_idx].srchost_refcnt++; >> + q->flows[reduced_hash].srchost =3D srchost_idx; >> + } >> + >> + if (need_allocate_dst) { >> + inner_hash =3D dsthost_idx % CAKE_SET_WAYS; >> + outer_hash =3D dsthost_idx - inner_hash; >> + for (i =3D 0, k =3D inner_hash; i < CAKE_SET_WAYS; >> + i++, k =3D (k + 1) % CAKE_SET_WAYS) { >> + if (q->hosts[outer_hash + k].dsthost_tag = =3D=3D >> + dsthost_hash) >> + goto found_dst; >> + } >> + for (i =3D 0; i < CAKE_SET_WAYS; >> + i++, k =3D (k + 1) % CAKE_SET_WAYS) { >> + if (!q->hosts[outer_hash + k].dsthost_refc= nt) >> + break; >> + } >> + q->hosts[outer_hash + k].dsthost_tag =3D dsthost_h= ash; >> +found_dst: >> + dsthost_idx =3D outer_hash + k; >> + q->hosts[dsthost_idx].dsthost_refcnt++; >> + q->flows[reduced_hash].dsthost =3D 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 inline struct sk_buff *dequeue_head(struct cake_flow *flow) >> +{ >> + struct sk_buff *skb =3D flow->head; >> + >> + if (skb) { >> + flow->head =3D skb->next; >> + skb->next =3D NULL; >> + >> + if (skb =3D=3D flow->ackcheck) >> + flow->ackcheck =3D NULL; > > Is there a sane way to move this check elsewhere and only when ack > filtering is enabled? > >> + } >> + >> + return skb; >> +} >> + >> +/* add skb to flow queue (tail add) */ >> + >> +static inline void >> +flow_queue_add(struct cake_flow *flow, struct sk_buff *skb) >> +{ >> + if (!flow->head) >> + flow->head =3D skb; >> + else >> + flow->tail->next =3D skb; >> + flow->tail =3D skb; >> + skb->next =3D NULL; >> +} >> + >> +static struct sk_buff *ack_filter(struct cake_flow *flow, bool aggressi= ve) >> +{ >> + int seglen; >> + struct sk_buff *skb =3D flow->tail, *skb_check, *skb_check_prev; >> + struct iphdr *iph, *iph_check; >> + struct ipv6hdr *ipv6h, *ipv6h_check; >> + struct tcphdr *tcph, *tcph_check; >> + >> + bool otherconn_ack_seen =3D false; >> + struct sk_buff *otherconn_checked_to =3D NULL; >> + bool thisconn_redundant_seen =3D false, thisconn_seen_last =3D fal= se; >> + struct sk_buff *thisconn_checked_to =3D NULL, *thisconn_ack =3D NU= LL; >> + >> + /* no other possible ACKs to filter */ >> + if (flow->head =3D=3D skb) >> + return NULL; >> + >> + iph =3D skb->encapsulation ? inner_ip_hdr(skb) : ip_hdr(skb); >> + ipv6h =3D skb->encapsulation ? inner_ipv6_hdr(skb) : ipv6_hdr(skb)= ; >> + >> + /* check that the innermost network header is v4/v6, and contains = TCP */ >> + if (iph->version =3D=3D 4) { >> + if (iph->protocol !=3D IPPROTO_TCP) >> + return NULL; >> + seglen =3D ntohs(iph->tot_len) - (4 * iph->ihl); >> + tcph =3D (struct tcphdr *)((void *)iph + (4 * iph->ihl)); >> + } else if (ipv6h->version =3D=3D 6) { >> + if (ipv6h->nexthdr !=3D IPPROTO_TCP) >> + return NULL; >> + seglen =3D ntohs(ipv6h->payload_len); >> + tcph =3D (struct tcphdr *)((void *)ipv6h + sizeof(struct i= pv6hdr)); >> + } else { >> + return NULL; >> + } >> + >> + /* 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) & >> + cpu_to_be32(0x00120000)) !=3D TCP_FLAG_ACK) > > Magic number > >> + return NULL; >> + >> + /* the 'triggering' ACK is at the end of the queue, >> + * we have already returned if it is the only packet in the flow. >> + * stop before last packet in queue, don't compare trigger ACK to = itself >> + * start where we finished last time if recorded in ->ackcheck >> + * otherwise start from the the head of the flow queue. >> + */ >> + skb_check_prev =3D flow->ackcheck; >> + skb_check =3D flow->ackcheck ?: flow->head; >> + >> + while (skb_check->next) { >> + bool pure_ack, thisconn; >> + >> + /* don't increment if at head of flow queue (_prev =3D=3D = NULL) */ >> + if (skb_check_prev) { >> + skb_check_prev =3D skb_check; >> + skb_check =3D skb_check->next; >> + if (!skb_check->next) >> + break; >> + } else { >> + skb_check_prev =3D ERR_PTR(-1); >> + } >> + >> + iph_check =3D skb_check->encapsulation ? >> + inner_ip_hdr(skb_check) : ip_hdr(skb_check); >> + ipv6h_check =3D skb_check->encapsulation ? >> + inner_ipv6_hdr(skb_check) : ipv6_hdr(skb_check); >> + >> + if (iph_check->version =3D=3D 4) { >> + if (iph_check->protocol !=3D IPPROTO_TCP) >> + continue; >> + seglen =3D ntohs(iph_check->tot_len) - (4 * iph_ch= eck->ihl); >> + tcph_check =3D (struct tcphdr *)((void *)iph_check >> + + (4 * iph_check->ihl)); >> + if (iph->version =3D=3D 4 && >> + iph_check->saddr =3D=3D iph->saddr && >> + iph_check->daddr =3D=3D iph->daddr) { >> + thisconn =3D true; >> + } else { >> + thisconn =3D false; >> + } >> + } else if (ipv6h_check->version =3D=3D 6) { >> + if (ipv6h_check->nexthdr !=3D IPPROTO_TCP) >> + continue; >> + seglen =3D ntohs(ipv6h_check->payload_len); >> + tcph_check =3D (struct tcphdr *)((void *)ipv6h_che= ck + >> + sizeof(struct ipv6hdr)); >> + if (ipv6h->version =3D=3D 6 && >> + ipv6_addr_cmp(&ipv6h_check->saddr, &ipv6h->sad= dr) && >> + ipv6_addr_cmp(&ipv6h_check->daddr, &ipv6h-= >daddr)) { >> + thisconn =3D true; >> + } else { >> + thisconn =3D false; >> + } >> + } else { >> + continue; >> + } >> + >> + /* stricter criteria apply to ACKs that we may filter >> + * 3 reserved flags must be unset to avoid future breakage >> + * ECE/CWR/NS can be safely ignored >> + * ACK must be set >> + * All other flags URG/PSH/RST/SYN/FIN must be unset >> + * must be 'pure' ACK, contain zero bytes of segment data >> + * options are ignored >> + */ >> + if ((tcp_flag_word(tcph) & >> + cpu_to_be32(0x00120000)) !=3D TCP_FLAG_ACK) { >> + continue; >> + } else if (((tcp_flag_word(tcph_check) & >> + cpu_to_be32(0x0E3F0000)) !=3D TCP_FLAG_ACK= ) || >> + ((seglen - 4 * tcph_check->doff) !=3D 0)) { >> + pure_ack =3D false; >> + } else { >> + pure_ack =3D true; >> + } >> + >> + /* if we find an ACK belonging to a different connection >> + * continue checking for other ACKs this round however >> + * restart checking from the other connection next time. >> + */ >> + if (thisconn && (tcph_check->source !=3D tcph->source || >> + tcph_check->dest !=3D tcph->dest)) { >> + thisconn =3D false; >> + } >> + >> + /* new ack sequence must be greater >> + */ >> + if (thisconn && >> + (ntohl(tcph_check->ack_seq) > ntohl(tcph->ack_seq))) >> + continue; >> + >> + /* DupACKs with an equal sequence number shouldn't be filt= ered, >> + * but we can filter if the triggering packet is a SACK >> + */ >> + if (thisconn && >> + (ntohl(tcph_check->ack_seq) =3D=3D ntohl(tcph->ack_seq= ))) { >> + /* inspired by tcp_parse_options in tcp_input.c */ >> + bool sack =3D false; >> + int length =3D (tcph->doff * 4) - sizeof(struct tc= phdr); >> + const u8 *ptr =3D (const u8 *)(tcph + 1); >> + >> + while (length > 0) { >> + int opcode =3D *ptr++; >> + int opsize; >> + >> + if (opcode =3D=3D TCPOPT_EOL) >> + break; >> + if (opcode =3D=3D TCPOPT_NOP) { >> + length--; >> + continue; >> + } >> + opsize =3D *ptr++; >> + if (opsize < 2 || opsize > length) >> + break; >> + if (opcode =3D=3D TCPOPT_SACK) { >> + sack =3D true; >> + break; >> + } >> + ptr +=3D opsize - 2; >> + length -=3D opsize; >> + } >> + if (!sack) >> + continue; >> + } >> + >> + /* somewhat complicated control flow for 'conservative' >> + * ACK filtering that aims to be more polite to slow-start= and >> + * in the presence of packet loss. >> + * does not filter if there is one 'redundant' ACK in the = queue. >> + * 'data' ACKs won't be filtered but do count as redundant= ACKs. >> + */ >> + if (thisconn) { >> + thisconn_seen_last =3D true; >> + /* if aggressive and this is a data ack we can ski= p >> + * checking it next time. >> + */ >> + thisconn_checked_to =3D (aggressive && !pure_ack) = ? >> + skb_check : skb_check_prev; >> + /* the first pure ack for this connection. >> + * record where it is, but only break if aggressiv= e >> + * or already seen data ack from the same connecti= on >> + */ >> + if (pure_ack && !thisconn_ack) { >> + thisconn_ack =3D skb_check_prev; >> + if (aggressive || thisconn_redundant_seen) >> + break; >> + /* data ack or subsequent pure ack */ >> + } else { >> + thisconn_redundant_seen =3D true; >> + /* this is the second ack for this connect= ion >> + * break to filter the first pure ack >> + */ >> + if (thisconn_ack) >> + break; >> + } >> + /* track packets from non-matching tcp connections that wi= ll >> + * need evaluation on the next run. >> + * if there are packets from both the matching connection = and >> + * others that requre checking next run, track which was u= pdated >> + * last and return the older of the two to ensure full cov= erage. >> + * if a non-matching pure ack has been seen, cannot skip a= ny >> + * further on the next run so don't update. >> + */ >> + } else if (!otherconn_ack_seen) { >> + thisconn_seen_last =3D false; >> + if (pure_ack) { >> + otherconn_ack_seen =3D true; >> + /* if aggressive we don't care about old d= ata, >> + * start from the pure ack. >> + * otherwise if there is a previous data a= ck, >> + * start checking from it next time. >> + */ >> + if (aggressive || !otherconn_checked_to) >> + otherconn_checked_to =3D skb_check= _prev; >> + } else { >> + otherconn_checked_to =3D aggressive ? >> + skb_check : skb_check_prev; >> + } >> + } >> + } >> + >> + /* skb_check is reused at this point >> + * it is the pure ACK to be filtered (if any) >> + */ >> + skb_check =3D NULL; >> + >> + /* next time start checking from the older/nearest to head of unfi= ltered >> + * but important tcp packets from this connection and other connec= tions. >> + * if none seen, start after the last packet evaluated in the loop= . >> + */ >> + if (thisconn_checked_to && otherconn_checked_to) >> + flow->ackcheck =3D thisconn_seen_last ? >> + otherconn_checked_to : thisconn_checked_to; >> + else if (thisconn_checked_to) >> + flow->ackcheck =3D thisconn_checked_to; >> + else if (otherconn_checked_to) >> + flow->ackcheck =3D otherconn_checked_to; >> + else >> + flow->ackcheck =3D skb_check_prev; >> + >> + /* if filtering, the pure ACK from the flow queue */ >> + if (thisconn_ack && (aggressive || thisconn_redundant_seen)) { >> + if (PTR_ERR(thisconn_ack) =3D=3D -1) { >> + skb_check =3D flow->head; >> + flow->head =3D flow->head->next; >> + } else { >> + skb_check =3D thisconn_ack->next; >> + thisconn_ack->next =3D thisconn_ack->next->next; >> + } >> + } >> + >> + /* we just filtered that ack, fix up the list */ >> + if (flow->ackcheck =3D=3D skb_check) >> + flow->ackcheck =3D thisconn_ack; >> + /* check the entire flow queue next time */ >> + if (PTR_ERR(flow->ackcheck) =3D=3D -1) >> + flow->ackcheck =3D NULL; >> + >> + return skb_check; >> +} >> + >> +static inline u32 cake_overhead(struct cake_sched_data *q, u32 in) >> +{ >> + u32 out =3D in + q->rate_overhead; >> + >> + if (q->rate_mpu && out < q->rate_mpu) >> + out =3D q->rate_mpu; >> + >> + if (q->rate_flags & CAKE_FLAG_ATM) { >> + out +=3D 47; >> + out /=3D 48; >> + out *=3D 53; >> + } else if (q->rate_flags & CAKE_FLAG_PTM) { >> + /* Add one byte per 64 bytes or part thereof. >> + * This is conservative and easier to calculate than the >> + * precise value. >> + */ >> + out +=3D (out / 64) + !!(out % 64); >> + } >> + >> + return out; >> +} >> + >> +static inline cobalt_time_t cake_ewma(cobalt_time_t avg, cobalt_time_t = sample, >> + u32 shift) >> +{ >> + avg -=3D avg >> shift; >> + avg +=3D sample >> shift; >> + return avg; >> +} >> + >> +static inline void cake_heap_swap(struct cake_sched_data *q, u16 i, u16= j) >> +{ >> + struct cake_heap_entry ii =3D q->overflow_heap[i]; >> + struct cake_heap_entry jj =3D q->overflow_heap[j]; >> + >> + q->overflow_heap[i] =3D jj; >> + q->overflow_heap[j] =3D ii; >> + >> + q->tins[ii.t].overflow_idx[ii.b] =3D j; >> + q->tins[jj.t].overflow_idx[jj.b] =3D i; >> +} >> + >> +static inline u32 cake_heap_get_backlog(const struct cake_sched_data *q= , u16 i) >> +{ >> + struct cake_heap_entry ii =3D 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 =3D CAKE_MAX_TINS * CAKE_QUEUES; >> + u32 m =3D i; >> + u32 mb =3D cake_heap_get_backlog(q, m); >> + >> + while (m < a) { >> + u32 l =3D m + m + 1; >> + u32 r =3D l + 1; >> + >> + if (l < a) { >> + u32 lb =3D cake_heap_get_backlog(q, l); >> + >> + if (lb > mb) { >> + m =3D l; >> + mb =3D lb; >> + } >> + } >> + >> + if (r < a) { >> + u32 rb =3D cake_heap_get_backlog(q, r); >> + >> + if (rb > mb) { >> + m =3D r; >> + mb =3D rb; >> + } >> + } >> + >> + if (m !=3D i) { >> + cake_heap_swap(q, i, m); >> + i =3D 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 =3D (i - 1) >> 1; >> + u32 ib =3D cake_heap_get_backlog(q, i); >> + u32 pb =3D cake_heap_get_backlog(q, p); >> + >> + if (ib > pb) { >> + cake_heap_swap(q, i, p); >> + i =3D p; >> + } else { >> + break; >> + } >> + } >> +} >> + >> +static void cake_advance_shaper(struct cake_sched_data *q, >> + struct cake_tin_data *b, u32 len, u64 now,= bool drop) >> +{ >> + /* charge packet bandwidth to this tin >> + * and to the global shaper. >> + */ >> + if (q->rate_ns) { >> + s64 tdiff1 =3D b->tin_time_next_packet - now; >> + s64 tdiff2 =3D (len * (u64)b->tin_rate_ns) >> b->tin_rate_= shft; >> + s64 tdiff3 =3D (len * (u64)q->rate_ns) >> q->rate_shft; >> + s64 tdiff4 =3D (len * (u64)q->rate_ns) >> (q->rate_shft - = 2); >> + >> + if (tdiff1 < 0) >> + b->tin_time_next_packet +=3D tdiff2; >> + else if (tdiff1 < tdiff2) >> + b->tin_time_next_packet =3D now + tdiff2; >> + >> + q->time_next_packet +=3D tdiff3; >> + if (!drop) >> + q->failsafe_next_packet +=3D tdiff4; >> + } >> +} >> + >> +static unsigned int cake_drop(struct Qdisc *sch, struct sk_buff **to_fr= ee) >> +{ >> + struct cake_sched_data *q =3D qdisc_priv(sch); >> + struct sk_buff *skb; >> + u32 idx =3D 0, tin =3D 0, len; >> + struct cake_tin_data *b; >> + struct cake_flow *flow; >> + struct cake_heap_entry qq; >> + u64 now =3D cobalt_get_time(); >> + >> + if (!q->overflow_timeout) { >> + int i; >> + /* Build fresh max-heap */ >> + for (i =3D CAKE_MAX_TINS * CAKE_QUEUES / 2; i >=3D 0; i--) >> + cake_heapify(q, i); >> + } >> + q->overflow_timeout =3D 65535; >> + >> + /* select longest queue for pruning */ >> + qq =3D q->overflow_heap[0]; >> + tin =3D qq.t; >> + idx =3D qq.b; >> + >> + b =3D &q->tins[tin]; >> + flow =3D &b->flows[idx]; >> + skb =3D dequeue_head(flow); >> + if (unlikely(!skb)) { >> + /* heap has gone wrong, rebuild it next time */ >> + q->overflow_timeout =3D 0; >> + return idx + (tin << 16); >> + } >> + >> + if (cobalt_queue_full(&flow->cvars, &b->cparams, now)) >> + b->unresponsive_flow_count++; >> + >> + len =3D qdisc_pkt_len(skb); >> + q->buffer_used -=3D skb->truesize; >> + b->backlogs[idx] -=3D len; >> + b->tin_backlog -=3D len; >> + sch->qstats.backlog -=3D len; >> + qdisc_tree_reduce_backlog(sch, 1, len); >> + >> + b->tin_dropped++; >> + sch->qstats.drops++; >> + >> + if (q->rate_flags & CAKE_FLAG_INGRESS) >> + cake_advance_shaper(q, b, cake_overhead(q, len), now, true= ); >> + >> + __qdisc_drop(skb, to_free); > > We use __qdisc_drop here, but other variants elsewhere. Why? > >> + sch->q.qlen--; >> + cake_heapify(q, 0); >> + >> + return idx + (tin << 16); >> +} >> + >> +static inline void cake_wash_diffserv(struct sk_buff *skb) >> +{ >> + switch (skb->protocol) { >> + case htons(ETH_P_IP): >> + ipv4_change_dsfield(ip_hdr(skb), INET_ECN_MASK, 0); >> + break; >> + case htons(ETH_P_IPV6): >> + ipv6_change_dsfield(ipv6_hdr(skb), INET_ECN_MASK, 0); >> + break; >> + default: >> + break; >> + }; >> +} >> + >> +static inline u8 cake_handle_diffserv(struct sk_buff *skb, u16 wash) >> +{ >> + u8 dscp; >> + >> + switch (skb->protocol) { >> + case htons(ETH_P_IP): >> + dscp =3D ipv4_get_dsfield(ip_hdr(skb)) >> 2; >> + if (wash && dscp) >> + ipv4_change_dsfield(ip_hdr(skb), INET_ECN_MASK, 0)= ; >> + return dscp; >> + >> + case htons(ETH_P_IPV6): >> + dscp =3D ipv6_get_dsfield(ipv6_hdr(skb)) >> 2; >> + if (wash && dscp) >> + 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 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 =3D qdisc_priv(sch); >> + u32 idx, tin; >> + struct cake_tin_data *b; >> + struct cake_flow *flow; >> + /* signed len to handle corner case filtered ACK larger than trigg= er */ >> + int len =3D qdisc_pkt_len(skb); >> + u64 now =3D cobalt_get_time(); >> + struct sk_buff *skb_filtered_ack =3D NULL; >> + >> + /* extract the Diffserv Precedence field, if it exists */ >> + /* and clear DSCP bits if washing */ >> + if (q->tin_mode !=3D CAKE_MODE_BESTEFFORT) { >> + tin =3D q->tin_index[cake_handle_diffserv(skb, >> + q->rate_flags & CAKE_FLAG_WASH)]; >> + if (unlikely(tin >=3D q->tin_cnt)) >> + tin =3D 0; >> + } else { >> + tin =3D 0; >> + if (q->rate_flags & CAKE_FLAG_WASH) >> + cake_wash_diffserv(skb); >> + } >> + >> + b =3D &q->tins[tin]; >> + >> + /* choose flow to insert into */ >> + idx =3D cake_hash(b, skb, q->flow_mode); >> + flow =3D &b->flows[idx]; >> + >> + /* ensure shaper state isn't stale */ >> + if (!b->tin_backlog) { >> + if (b->tin_time_next_packet < now) >> + b->tin_time_next_packet =3D now; >> + >> + if (!sch->q.qlen) { >> + if (q->time_next_packet < now) { >> + q->failsafe_next_packet =3D now; >> + q->time_next_packet =3D now; >> + } else if (q->time_next_packet > now && q->failsaf= e_next_packet > now) { >> + u64 next_time =3D (q->time_next_packet < q= ->failsafe_next_packet) >> + ? q->time_next_packet : q->failsaf= e_next_packet; >> + sch->qstats.overlimits++; >> + qdisc_watchdog_schedule_ns(&q->watchdog, n= ext_time); >> + } >> + } >> + } >> + >> + if (unlikely(len > b->max_skblen)) >> + b->max_skblen =3D len; >> + >> + /* Split GSO aggregates if they're likely to impair flow isolation >> + * or if we need to know individual packet sizes for framing overh= ead. >> + */ >> + >> + if (skb_is_gso(skb)) { >> + struct sk_buff *segs, *nskb; >> + netdev_features_t features =3D netif_skb_features(skb); >> + /* signed slen to handle corner case >> + * suppressed ACK larger than trigger >> + */ >> + int slen =3D 0; >> + >> + segs =3D skb_gso_segment(skb, features & ~NETIF_F_GSO_MASK= ); >> + if (IS_ERR_OR_NULL(segs)) >> + return qdisc_drop(skb, sch, to_free); > > Why __qdisc_drop elsewhere? > >> + while (segs) { >> + nskb =3D segs->next; >> + segs->next =3D NULL; >> + qdisc_skb_cb(segs)->pkt_len =3D segs->len; >> + cobalt_set_enqueue_time(segs, now); >> + flow_queue_add(flow, segs); >> + >> + if (q->rate_flags & CAKE_FLAG_ACK_FILTER) >> + skb_filtered_ack =3D ack_filter(flow, q->r= ate_flags & CAKE_FLAG_ACK_AGGRESSIVE); >> + >> + if (skb_filtered_ack) { >> + b->ack_drops++; >> + b->bytes +=3D skb_filtered_ack->len; >> + slen +=3D segs->len - skb_filtered_ack->le= n; >> + q->buffer_used +=3D segs->truesize - >> + skb_filtered_ack->truesize= ; >> + if (q->rate_flags & CAKE_FLAG_INGRESS) >> + cake_advance_shaper(q, b, cake_ove= rhead(q, skb_filtered_ack->len), now, true); >> + >> + qdisc_tree_reduce_backlog(sch, 1, >> + qdisc_pkt_len(sk= b_filtered_ack)); >> + consume_skb(skb_filtered_ack); >> + } else { >> + sch->q.qlen++; >> + slen +=3D segs->len; >> + q->buffer_used +=3D segs->truesize; >> + } >> + b->packets++; >> + segs =3D nskb; >> + } >> + /* stats */ >> + b->bytes +=3D slen; >> + b->backlogs[idx] +=3D slen; >> + b->tin_backlog +=3D slen; >> + sch->qstats.backlog +=3D slen; >> + q->avg_window_bytes +=3D slen; >> + >> + qdisc_tree_reduce_backlog(sch, 1, len); >> + consume_skb(skb); > > Still trying to figure out this > >> + } else { >> + /* not splitting */ >> + cobalt_set_enqueue_time(skb, now); >> + flow_queue_add(flow, skb); >> + >> + if (q->rate_flags & CAKE_FLAG_ACK_FILTER) >> + skb_filtered_ack =3D ack_filter(flow, (q->rate_fla= gs & CAKE_FLAG_ACK_AGGRESSIVE)); > > Could just pass q->rate_flags and sort it out there. > >> + if (skb_filtered_ack) { >> + b->ack_drops++; >> + b->bytes +=3D qdisc_pkt_len(skb_filtered_ack); >> + len -=3D qdisc_pkt_len(skb_filtered_ack); >> + q->buffer_used +=3D skb->truesize - >> + skb_filtered_ack->truesize; >> + if (q->rate_flags & CAKE_FLAG_INGRESS) >> + cake_advance_shaper(q, b, cake_overhead(q,= skb_filtered_ack->len), now, true); >> + >> + qdisc_tree_reduce_backlog(sch, 1, >> + qdisc_pkt_len(skb_filter= ed_ack)); >> + consume_skb(skb_filtered_ack); >> + } else { >> + sch->q.qlen++; >> + q->buffer_used +=3D skb->truesize; >> + } >> + /* stats */ >> + b->packets++; >> + b->bytes +=3D len; >> + b->backlogs[idx] +=3D len; >> + b->tin_backlog +=3D len; >> + sch->qstats.backlog +=3D len; >> + q->avg_window_bytes +=3D 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 =3D now - q->last_packet_time; >> + >> + if (packet_interval > NSEC_PER_SEC) >> + packet_interval =3D NSEC_PER_SEC; > > I do not understand this. Why? > >> + >> + /* filter out short-term bursts, eg. wifi aggregation */ >> + q->avg_packet_interval =3D cake_ewma(q->avg_packet_interva= l, >> + packet_interval, >> + packet_interval > q->avg_packet_interval ? 2 : 8); >> + >> + q->last_packet_time =3D now; >> + >> + if (packet_interval > q->avg_packet_interval) { >> + u64 window_interval =3D now - q->avg_window_begin; >> + u64 b =3D q->avg_window_bytes * (u64)NSEC_PER_SEC; >> + >> + do_div(b, window_interval); >> + q->avg_peak_bandwidth =3D >> + cake_ewma(q->avg_peak_bandwidth, b, >> + b > q->avg_peak_bandwidth ? 2 : = 8); >> + q->avg_window_bytes =3D 0; >> + q->avg_window_begin =3D now; >> + >> + if (q->rate_flags & CAKE_FLAG_AUTORATE_INGRESS && >> + now - q->last_reconfig_time > >> + (NSEC_PER_SEC / 4)) { >> + q->rate_bps =3D (q->avg_peak_bandwidth * 1= 5) >> 4; >> + cake_reconfigure(sch); >> + } >> + } >> + } else { >> + q->avg_window_bytes =3D 0; >> + q->last_packet_time =3D now; >> + } >> + >> + /* flowchain */ >> + if (!flow->set || flow->set =3D=3D CAKE_SET_DECAYING) { >> + struct cake_host *srchost =3D &b->hosts[flow->srchost]; >> + struct cake_host *dsthost =3D &b->hosts[flow->dsthost]; >> + u16 host_load =3D 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 =3D CAKE_SET_SPARSE; >> + b->sparse_flow_count++; >> + >> + if ((q->flow_mode & CAKE_FLOW_DUAL_SRC) =3D=3D CAKE_FLOW_D= UAL_SRC) >> + host_load =3D max(host_load, srchost->srchost_refc= nt); >> + >> + if ((q->flow_mode & CAKE_FLOW_DUAL_DST) =3D=3D CAKE_FLOW_D= UAL_DST) >> + host_load =3D max(host_load, dsthost->dsthost_refc= nt); >> + >> + flow->deficit =3D (b->flow_quantum * quantum_div[host_load= ]) >> 16; >> + } else if (flow->set =3D=3D CAKE_SET_SPARSE_WAIT) { >> + /* this flow was empty, accounted as a sparse flow, but ac= tually >> + * in the bulk rotation. >> + */ >> + flow->set =3D CAKE_SET_BULK; >> + b->sparse_flow_count--; >> + b->bulk_flow_count++; >> + } >> + >> + if (q->buffer_used > q->buffer_max_used) >> + q->buffer_max_used =3D q->buffer_used; >> + >> + if (q->buffer_used > q->buffer_limit) { >> + u32 dropped =3D 0; >> + >> + while (q->buffer_used > q->buffer_limit) { >> + dropped++; >> + cake_drop(sch, to_free); >> + } >> + b->drop_overlimit +=3D dropped; >> + } >> + return NET_XMIT_SUCCESS; >> +} >> + >> +static struct sk_buff *cake_dequeue_one(struct Qdisc *sch) >> +{ >> + struct cake_sched_data *q =3D qdisc_priv(sch); >> + struct cake_tin_data *b =3D &q->tins[q->cur_tin]; >> + struct cake_flow *flow =3D &b->flows[q->cur_flow]; >> + struct sk_buff *skb =3D NULL; >> + u32 len; >> + >> + /* WARN_ON(flow !=3D container_of(vars, struct cake_flow, cvars));= */ > > I should have deleted this comment. > >> + >> + if (flow->head) { >> + skb =3D dequeue_head(flow); >> + len =3D qdisc_pkt_len(skb); >> + b->backlogs[q->cur_flow] -=3D len; >> + b->tin_backlog -=3D len; >> + sch->qstats.backlog -=3D len; >> + q->buffer_used -=3D 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 =3D qdisc_priv(sch); >> + struct sk_buff *skb; >> + >> + q->cur_tin =3D tin; >> + for (q->cur_flow =3D 0; q->cur_flow < CAKE_QUEUES; q->cur_flow++) >> + while (!!(skb =3D cake_dequeue_one(sch))) >> + kfree_skb(skb); >> +} >> + >> +static struct sk_buff *cake_dequeue(struct Qdisc *sch) >> +{ >> + struct cake_sched_data *q =3D qdisc_priv(sch); >> + struct sk_buff *skb; >> + struct cake_tin_data *b =3D &q->tins[q->cur_tin]; >> + struct cake_flow *flow; >> + struct cake_host *srchost, *dsthost; >> + struct list_head *head; >> + u32 len; >> + u16 host_load; >> + cobalt_time_t now =3D ktime_get_ns(); >> + cobalt_time_t delay; >> + bool first_flow =3D true; >> + >> +begin: >> + if (!sch->q.qlen) >> + return NULL; >> + >> + /* global hard shaper */ >> + if (q->time_next_packet > now && q->failsafe_next_packet > now) { >> + u64 next_time =3D (q->time_next_packet < q->failsafe_next_= packet) >> + ? q->time_next_packet : q->failsafe_next_packet; >> + sch->qstats.overlimits++; >> + qdisc_watchdog_schedule_ns(&q->watchdog, next_time); >> + return NULL; >> + } >> + >> + /* Choose a class to work on. */ >> + if (!q->rate_ns) { >> + /* In unlimited mode, can't rely on shaper timings, just b= alance >> + * with DRR >> + */ >> + while (b->tin_deficit < 0 || >> + !(b->sparse_flow_count + b->bulk_flow_count)) { >> + if (b->tin_deficit <=3D 0) >> + b->tin_deficit +=3D b->tin_quantum_band; >> + >> + q->cur_tin++; >> + b++; >> + if (q->cur_tin >=3D q->tin_cnt) { >> + q->cur_tin =3D 0; >> + b =3D q->tins; >> + } >> + } >> + } else { >> + /* In shaped mode, choose: >> + * - Highest-priority tin with queue and meeting schedule,= or >> + * - The earliest-scheduled tin with queue. >> + */ >> + int tin, best_tin =3D 0; >> + s64 best_time =3D 0xFFFFFFFFFFFFUL; >> + >> + for (tin =3D 0; tin < q->tin_cnt; tin++) { >> + b =3D q->tins + tin; >> + if ((b->sparse_flow_count + b->bulk_flow_count) > = 0) { >> + s64 tdiff =3D b->tin_time_next_packet - no= w; >> + >> + if (tdiff <=3D 0 || tdiff <=3D best_time) = { >> + best_time =3D tdiff; >> + best_tin =3D tin; >> + } >> + } >> + } >> + >> + q->cur_tin =3D best_tin; >> + b =3D q->tins + best_tin; >> + } >> + >> +retry: >> + /* service this class */ >> + head =3D &b->decaying_flows; >> + if (!first_flow || list_empty(head)) { >> + head =3D &b->new_flows; >> + if (list_empty(head)) { >> + head =3D &b->old_flows; >> + if (unlikely(list_empty(head))) { >> + head =3D &b->decaying_flows; >> + if (unlikely(list_empty(head))) >> + goto begin; >> + } >> + } >> + } >> + flow =3D list_first_entry(head, struct cake_flow, flowchain); >> + q->cur_flow =3D flow - b->flows; >> + first_flow =3D false; >> + >> + /* triple isolation (modified DRR++) */ >> + srchost =3D &b->hosts[flow->srchost]; >> + dsthost =3D &b->hosts[flow->dsthost]; >> + host_load =3D 1; >> + >> + if ((q->flow_mode & CAKE_FLOW_DUAL_SRC) =3D=3D CAKE_FLOW_DUAL_SRC) >> + host_load =3D max(host_load, srchost->srchost_refcnt); >> + >> + if ((q->flow_mode & CAKE_FLOW_DUAL_DST) =3D=3D CAKE_FLOW_DUAL_DST) >> + host_load =3D max(host_load, dsthost->dsthost_refcnt); >> + >> + WARN_ON(host_load > CAKE_QUEUES); > > Should have nuked this also. > >> + >> + /* flow isolation (DRR++) */ >> + if (flow->deficit <=3D 0) { >> + flow->deficit +=3D (b->flow_quantum * quantum_div[host_loa= d] + >> + (prandom_u32() >> 16)) >> 16; >> + list_move_tail(&flow->flowchain, &b->old_flows); >> + >> + /* Keep all flows with deficits out of the sparse and deca= ying >> + * rotations. No non-empty flow can go into the decaying >> + * rotation, so they can't get deficits >> + */ >> + if (flow->set =3D=3D CAKE_SET_SPARSE) { >> + if (flow->head) { >> + b->sparse_flow_count--; >> + b->bulk_flow_count++; >> + flow->set =3D 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 bul= k one. >> + */ >> + flow->set =3D CAKE_SET_SPARSE_WAIT; >> + } >> + } >> + goto retry; >> + } >> + >> + /* Retrieve a packet via the AQM */ >> + while (1) { >> + skb =3D 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 || >> + (now - flow->cvars.drop_next) < 0) { >> + /* keep in the flowchain until the state h= as >> + * decayed to rest >> + */ >> + list_move_tail(&flow->flowchain, >> + &b->decaying_flows); >> + if (flow->set =3D=3D CAKE_SET_BULK) { >> + b->bulk_flow_count--; >> + b->decaying_flow_count++; >> + } else if (flow->set =3D=3D CAKE_SET_SPARS= E || >> + flow->set =3D=3D CAKE_SET_SPARS= E_WAIT) { >> + b->sparse_flow_count--; >> + b->decaying_flow_count++; >> + } >> + flow->set =3D CAKE_SET_DECAYING; >> + } else { >> + /* remove empty queue from the flowchain *= / >> + list_del_init(&flow->flowchain); >> + if (flow->set =3D=3D CAKE_SET_SPARSE || >> + flow->set =3D=3D CAKE_SET_SPARSE_WAIT) >> + b->sparse_flow_count--; >> + else if (flow->set =3D=3D CAKE_SET_BULK) >> + b->bulk_flow_count--; >> + else >> + b->decaying_flow_count--; >> + >> + flow->set =3D CAKE_SET_NONE; >> + srchost->srchost_refcnt--; >> + dsthost->dsthost_refcnt--; >> + } >> + goto begin; >> + } >> + >> + /* Last packet in queue may be marked, shouldn't be droppe= d */ >> + if (!cobalt_should_drop(&flow->cvars, &b->cparams, now, sk= b) || >> + !flow->head) >> + break; >> + >> + /* drop this packet, get another one */ >> + if (q->rate_flags & CAKE_FLAG_INGRESS) { >> + len =3D cake_overhead(q, qdisc_pkt_len(skb)); >> + cake_advance_shaper(q, b, len, now, true); >> + flow->deficit -=3D len; >> + b->tin_deficit -=3D len; >> + } >> + b->tin_dropped++; >> + qdisc_tree_reduce_backlog(sch, 1, qdisc_pkt_len(skb)); >> + qdisc_qstats_drop(sch); >> + kfree_skb(skb); > > And elsewhere I see __qdisc_drop. > >> + if (q->rate_flags & CAKE_FLAG_INGRESS) >> + goto retry; >> + } >> + >> + b->tin_ecn_mark +=3D !!flow->cvars.ecn_marked; >> + qdisc_bstats_update(sch, skb); >> + >> + len =3D cake_overhead(q, qdisc_pkt_len(skb)); >> + flow->deficit -=3D len; >> + b->tin_deficit -=3D len; >> + >> + /* collect delay stats */ >> + delay =3D now - cobalt_get_enqueue_time(skb); >> + b->avge_delay =3D cake_ewma(b->avge_delay, delay, 8); >> + b->peak_delay =3D cake_ewma(b->peak_delay, delay, >> + delay > b->peak_delay ? 2 : 8); >> + b->base_delay =3D cake_ewma(b->base_delay, delay, >> + delay < b->base_delay ? 2 : 8); >> + >> + cake_advance_shaper(q, b, len, now, false); >> + if (q->time_next_packet > now && sch->q.qlen) { >> + u64 next_time =3D (q->time_next_packet < q->failsafe_next_= packet) >> + ? q->time_next_packet : q->failsafe_next_packet; >> + qdisc_watchdog_schedule_ns(&q->watchdog, next_time); >> + } else if (!sch->q.qlen) { >> + int i; >> + >> + for (i =3D 0; i < q->tin_cnt; i++) { >> + if (q->tins[i].decaying_flow_count) { >> + qdisc_watchdog_schedule_ns(&q->watchdog, n= ow + >> + q->tins[i].cpar= ams.target); >> + break; >> + } >> + } >> + } >> + >> + if (q->overflow_timeout) >> + q->overflow_timeout--; >> + >> + return skb; >> +} >> + >> +static void cake_reset(struct Qdisc *sch) >> +{ >> + u32 c; >> + >> + for (c =3D 0; c < CAKE_MAX_TINS; c++) >> + cake_clear_tin(sch, c); >> +} >> + >> +static const struct nla_policy cake_policy[TCA_CAKE_MAX + 1] =3D { >> + [TCA_CAKE_BASE_RATE] =3D { .type =3D NLA_U32 }, >> + [TCA_CAKE_DIFFSERV_MODE] =3D { .type =3D NLA_U32 }, >> + [TCA_CAKE_ATM] =3D { .type =3D NLA_U32 }, >> + [TCA_CAKE_FLOW_MODE] =3D { .type =3D NLA_U32 }, >> + [TCA_CAKE_OVERHEAD] =3D { .type =3D NLA_S32 }, >> + [TCA_CAKE_RTT] =3D { .type =3D NLA_U32 }, >> + [TCA_CAKE_TARGET] =3D { .type =3D NLA_U32 }, >> + [TCA_CAKE_AUTORATE] =3D { .type =3D NLA_U32 }, >> + [TCA_CAKE_MEMORY] =3D { .type =3D NLA_U32 }, >> + [TCA_CAKE_NAT] =3D { .type =3D NLA_U32 }, >> + [TCA_CAKE_ETHERNET] =3D { .type =3D NLA_U32 }, >> + [TCA_CAKE_WASH] =3D { .type =3D NLA_U32 }, >> + [TCA_CAKE_MPU] =3D { .type =3D NLA_U32 }, >> + [TCA_CAKE_INGRESS] =3D { .type =3D NLA_U32 }, >> + [TCA_CAKE_ACK_FILTER] =3D { .type =3D NLA_U32 }, >> +}; > > Why here? > >> + >> +static void cake_set_rate(struct cake_tin_data *b, u64 rate, u32 mtu, >> + cobalt_time_t ns_target, cobalt_time_t rtt_est_n= s) >> +{ >> + /* convert byte-rate into time-per-byte >> + * so it will always unwedge in reasonable time. >> + */ >> + static const u64 MIN_RATE =3D 64; >> + u64 rate_ns =3D 0; >> + u8 rate_shft =3D 0; >> + cobalt_time_t byte_target_ns; >> + u32 byte_target =3D mtu + (mtu >> 1); >> + >> + b->flow_quantum =3D 1514; >> + if (rate) { >> + b->flow_quantum =3D max(min(rate >> 12, 1514ULL), 300ULL); >> + rate_shft =3D 32; >> + rate_ns =3D ((u64)NSEC_PER_SEC) << rate_shft; >> + do_div(rate_ns, max(MIN_RATE, rate)); >> + while (!!(rate_ns >> 32)) { >> + rate_ns >>=3D 1; >> + rate_shft--; >> + } >> + } /* else unlimited, ie. zero delay */ >> + >> + b->tin_rate_bps =3D rate; >> + b->tin_rate_ns =3D rate_ns; >> + b->tin_rate_shft =3D rate_shft; >> + >> + byte_target_ns =3D (byte_target * rate_ns) >> rate_shft; >> + >> + b->cparams.target =3D max(byte_target_ns, ns_target); >> + b->cparams.interval =3D max(rtt_est_ns + >> + b->cparams.target - ns_target, >> + b->cparams.target * 2); >> + b->cparams.p_inc =3D 1 << 24; /* 1/256 */ >> + b->cparams.p_dec =3D 1 << 20; /* 1/4096 */ >> +} >> + >> +static int cake_config_besteffort(struct Qdisc *sch) >> +{ >> + struct cake_sched_data *q =3D qdisc_priv(sch); >> + struct cake_tin_data *b =3D &q->tins[0]; >> + u32 rate =3D q->rate_bps; >> + u32 mtu =3D psched_mtu(qdisc_dev(sch)); >> + >> + q->tin_cnt =3D 1; >> + >> + q->tin_index =3D besteffort; >> + q->tin_order =3D normal_order; >> + >> + cake_set_rate(b, rate, mtu, US2TIME(q->target), US2TIME(q->interva= l)); >> + b->tin_quantum_band =3D 65535; >> + b->tin_quantum_prio =3D 65535; >> + >> + return 0; >> +} >> + >> +static int cake_config_precedence(struct Qdisc *sch) >> +{ >> + /* convert high-level (user visible) parameters into internal form= at */ >> + struct cake_sched_data *q =3D qdisc_priv(sch); >> + u32 rate =3D q->rate_bps; >> + u32 mtu =3D psched_mtu(qdisc_dev(sch)); >> + u32 quantum1 =3D 256; >> + u32 quantum2 =3D 256; >> + u32 i; >> + >> + q->tin_cnt =3D 8; >> + q->tin_index =3D precedence; >> + q->tin_order =3D normal_order; >> + >> + for (i =3D 0; i < q->tin_cnt; i++) { >> + struct cake_tin_data *b =3D &q->tins[i]; >> + >> + cake_set_rate(b, rate, mtu, US2TIME(q->target), >> + US2TIME(q->interval)); >> + >> + b->tin_quantum_prio =3D max_t(u16, 1U, quantum1); >> + b->tin_quantum_band =3D max_t(u16, 1U, quantum2); >> + >> + /* calculate next class's parameters */ >> + rate *=3D 7; >> + rate >>=3D 3; >> + >> + quantum1 *=3D 3; >> + quantum1 >>=3D 1; >> + >> + quantum2 *=3D 7; >> + quantum2 >>=3D 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 =3D qdisc_priv(sch); >> + u32 rate =3D q->rate_bps; >> + u32 mtu =3D psched_mtu(qdisc_dev(sch)); >> + u32 quantum1 =3D 256; >> + u32 quantum2 =3D 256; >> + u32 i; >> + >> + q->tin_cnt =3D 8; >> + >> + /* codepoint to class mapping */ >> + q->tin_index =3D diffserv8; >> + q->tin_order =3D normal_order; >> + >> + /* class characteristics */ >> + for (i =3D 0; i < q->tin_cnt; i++) { >> + struct cake_tin_data *b =3D &q->tins[i]; >> + >> + cake_set_rate(b, rate, mtu, US2TIME(q->target), >> + US2TIME(q->interval)); >> + >> + b->tin_quantum_prio =3D max_t(u16, 1U, quantum1); >> + b->tin_quantum_band =3D max_t(u16, 1U, quantum2); >> + >> + /* calculate next class's parameters */ >> + rate *=3D 7; >> + rate >>=3D 3; >> + >> + quantum1 *=3D 3; >> + quantum1 >>=3D 1; >> + >> + quantum2 *=3D 7; >> + quantum2 >>=3D 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 =3D qdisc_priv(sch); >> + u32 rate =3D q->rate_bps; >> + u32 mtu =3D psched_mtu(qdisc_dev(sch)); >> + u32 quantum =3D 1024; >> + >> + q->tin_cnt =3D 4; >> + >> + /* codepoint to class mapping */ >> + q->tin_index =3D diffserv4; >> + q->tin_order =3D bulk_order; >> + >> + /* class characteristics */ >> + cake_set_rate(&q->tins[0], rate, mtu, >> + US2TIME(q->target), US2TIME(q->interval)); >> + cake_set_rate(&q->tins[1], rate >> 4, mtu, >> + US2TIME(q->target), US2TIME(q->interval)); >> + cake_set_rate(&q->tins[2], rate >> 1, mtu, >> + US2TIME(q->target), US2TIME(q->interval)); >> + cake_set_rate(&q->tins[3], rate >> 2, mtu, >> + US2TIME(q->target), US2TIME(q->interval)); >> + >> + /* priority weights */ >> + q->tins[0].tin_quantum_prio =3D quantum; >> + q->tins[1].tin_quantum_prio =3D quantum >> 4; >> + q->tins[2].tin_quantum_prio =3D quantum << 2; >> + q->tins[3].tin_quantum_prio =3D quantum << 4; >> + >> + /* bandwidth-sharing weights */ >> + q->tins[0].tin_quantum_band =3D quantum; >> + q->tins[1].tin_quantum_band =3D quantum >> 4; >> + q->tins[2].tin_quantum_band =3D quantum >> 1; >> + q->tins[3].tin_quantum_band =3D 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 =3D qdisc_priv(sch); >> + u32 rate =3D q->rate_bps; >> + u32 mtu =3D psched_mtu(qdisc_dev(sch)); >> + u32 quantum =3D 1024; >> + >> + q->tin_cnt =3D 3; >> + >> + /* codepoint to class mapping */ >> + q->tin_index =3D diffserv3; >> + q->tin_order =3D bulk_order; >> + >> + /* class characteristics */ >> + cake_set_rate(&q->tins[0], rate, mtu, >> + US2TIME(q->target), US2TIME(q->interval)); >> + cake_set_rate(&q->tins[1], rate >> 4, mtu, >> + US2TIME(q->target), US2TIME(q->interval)); >> + cake_set_rate(&q->tins[2], rate >> 2, mtu, >> + US2TIME(q->target), US2TIME(q->target)); >> + >> + /* priority weights */ >> + q->tins[0].tin_quantum_prio =3D quantum; >> + q->tins[1].tin_quantum_prio =3D quantum >> 4; >> + q->tins[2].tin_quantum_prio =3D quantum << 4; >> + >> + /* bandwidth-sharing weights */ >> + q->tins[0].tin_quantum_band =3D quantum; >> + q->tins[1].tin_quantum_band =3D quantum >> 4; >> + q->tins[2].tin_quantum_band =3D quantum >> 2; >> + >> + return 0; >> +} >> + >> +static int cake_config_diffserv_llt(struct Qdisc *sch) >> +{ >> +/* Diffserv structure specialised for Latency-Loss-Tradeoff spec. >> + * Loss Sensitive (TOS1, TOS2) >> + * Best Effort >> + * Latency Sensitive (TOS4, TOS5, VA, EF) >> + * Low Priority (CS1) >> + * Network Control (CS6, CS7) >> + */ >> + struct cake_sched_data *q =3D qdisc_priv(sch); >> + u32 rate =3D q->rate_bps; >> + u32 mtu =3D psched_mtu(qdisc_dev(sch)); >> + >> + q->tin_cnt =3D 5; >> + >> + /* codepoint to class mapping */ >> + q->tin_index =3D diffserv_llt; >> + q->tin_order =3D normal_order; >> + >> + /* class characteristics */ >> + cake_set_rate(&q->tins[5], rate, mtu, >> + US2TIME(q->target), US2TIME(q->interval)); >> + >> + cake_set_rate(&q->tins[0], rate / 3, mtu, >> + US2TIME(q->target * 4), US2TIME(q->interval * 4)); >> + cake_set_rate(&q->tins[1], rate / 3, mtu, >> + US2TIME(q->target), US2TIME(q->interval)); >> + cake_set_rate(&q->tins[2], rate / 3, mtu, >> + US2TIME(q->target), US2TIME(q->target)); > > I tend to disagree with this, without some test showing it works. > It otherwise looks like a typo, and should gain a comment, at least. > >> + cake_set_rate(&q->tins[3], rate >> 4, mtu, >> + US2TIME(q->target), US2TIME(q->interval)); >> + cake_set_rate(&q->tins[4], rate >> 4, mtu, >> + US2TIME(q->target * 4), US2TIME(q->interval * 4)); >> + >> + /* priority weights */ >> + q->tins[0].tin_quantum_prio =3D 2048; >> + q->tins[1].tin_quantum_prio =3D 2048; >> + q->tins[2].tin_quantum_prio =3D 2048; >> + q->tins[3].tin_quantum_prio =3D 16384; >> + q->tins[4].tin_quantum_prio =3D 32768; >> + >> + /* bandwidth-sharing weights */ >> + q->tins[0].tin_quantum_band =3D 2048; >> + q->tins[1].tin_quantum_band =3D 2048; >> + q->tins[2].tin_quantum_band =3D 2048; >> + q->tins[3].tin_quantum_band =3D 256; >> + q->tins[4].tin_quantum_band =3D 16; >> + >> + return 5; >> +} >> + >> +static void cake_reconfigure(struct Qdisc *sch) >> +{ >> + struct cake_sched_data *q =3D qdisc_priv(sch); >> + int c, ft; >> + >> + switch (q->tin_mode) { >> + case CAKE_MODE_BESTEFFORT: >> + ft =3D cake_config_besteffort(sch); >> + break; >> + >> + case CAKE_MODE_PRECEDENCE: >> + ft =3D cake_config_precedence(sch); >> + break; >> + >> + case CAKE_MODE_DIFFSERV8: >> + ft =3D cake_config_diffserv8(sch); >> + break; >> + >> + case CAKE_MODE_DIFFSERV4: >> + ft =3D cake_config_diffserv4(sch); >> + break; >> + >> + case CAKE_MODE_LLT: >> + ft =3D cake_config_diffserv_llt(sch); >> + break; >> + >> + case CAKE_MODE_DIFFSERV3: >> + default: >> + ft =3D cake_config_diffserv3(sch); >> + break; >> + }; >> + >> + for (c =3D q->tin_cnt; c < CAKE_MAX_TINS; c++) >> + cake_clear_tin(sch, c); >> + >> + q->rate_ns =3D q->tins[ft].tin_rate_ns; >> + q->rate_shft =3D q->tins[ft].tin_rate_shft; >> + >> + if (q->buffer_config_limit) { >> + q->buffer_limit =3D q->buffer_config_limit; >> + } else if (q->rate_bps) { >> + u64 t =3D (u64)q->rate_bps * q->interval; >> + >> + do_div(t, USEC_PER_SEC / 4); >> + q->buffer_limit =3D max_t(u32, t, 4U << 20); >> + } else { >> + q->buffer_limit =3D ~0; >> + } >> + >> + if (1 || q->rate_bps) >> + sch->flags &=3D ~TCQ_F_CAN_BYPASS; >> + else >> + sch->flags |=3D TCQ_F_CAN_BYPASS; > > If we always disable bypass we slow down things by a lot, but at least > get accurate statistics. So I'm inclined to always > > sch->flags &=3D ~TCQ_F_CAN_BYPASS; > >> + q->buffer_limit =3D min(q->buffer_limit, max(sch->limit * psched_m= tu(qdisc_dev(sch)), q->buffer_config_limit)); >> +} >> + >> +static int cake_change(struct Qdisc *sch, struct nlattr *opt) >> +{ >> + struct cake_sched_data *q =3D qdisc_priv(sch); >> + struct nlattr *tb[TCA_CAKE_MAX + 1]; >> + int err; >> + >> + if (!opt) >> + return -EINVAL; >> + >> + err =3D nla_parse_nested(tb, TCA_CAKE_MAX, opt, cake_policy, NULL)= ; >> + if (err < 0) >> + return err; >> + >> + if (tb[TCA_CAKE_BASE_RATE]) >> + q->rate_bps =3D nla_get_u32(tb[TCA_CAKE_BASE_RATE]); >> + >> + if (tb[TCA_CAKE_DIFFSERV_MODE]) >> + q->tin_mode =3D nla_get_u32(tb[TCA_CAKE_DIFFSERV_MODE]); >> + >> + if (tb[TCA_CAKE_ATM]) { >> + q->rate_flags &=3D ~(CAKE_FLAG_ATM | CAKE_FLAG_PTM); >> + q->rate_flags |=3D nla_get_u32(tb[TCA_CAKE_ATM]) & >> + (CAKE_FLAG_ATM | CAKE_FLAG_PTM); >> + } >> + >> + if (tb[TCA_CAKE_WASH]) { >> + if (!!nla_get_u32(tb[TCA_CAKE_WASH])) >> + q->rate_flags |=3D CAKE_FLAG_WASH; >> + else >> + q->rate_flags &=3D ~CAKE_FLAG_WASH; >> + } >> + >> + if (tb[TCA_CAKE_FLOW_MODE]) >> + q->flow_mode =3D nla_get_u32(tb[TCA_CAKE_FLOW_MODE]); >> + >> + if (tb[TCA_CAKE_NAT]) { >> + q->flow_mode &=3D ~CAKE_FLOW_NAT_FLAG; >> + q->flow_mode |=3D CAKE_FLOW_NAT_FLAG * >> + !!nla_get_u32(tb[TCA_CAKE_NAT]); >> + } >> + >> + if (tb[TCA_CAKE_OVERHEAD]) { >> + if (tb[TCA_CAKE_ETHERNET]) >> + q->rate_overhead =3D -(nla_get_s32(tb[TCA_CAKE_ETH= ERNET])); >> + else >> + q->rate_overhead =3D -(qdisc_dev(sch)->hard_header= _len); >> + >> + q->rate_overhead +=3D nla_get_s32(tb[TCA_CAKE_OVERHEAD]); >> + } >> + >> + if (tb[TCA_CAKE_MPU]) >> + q->rate_mpu =3D nla_get_u32(tb[TCA_CAKE_MPU]); >> + >> + if (tb[TCA_CAKE_RTT]) { >> + q->interval =3D nla_get_u32(tb[TCA_CAKE_RTT]); >> + >> + if (!q->interval) >> + q->interval =3D 1; >> + } >> + >> + if (tb[TCA_CAKE_TARGET]) { >> + q->target =3D nla_get_u32(tb[TCA_CAKE_TARGET]); >> + >> + if (!q->target) >> + q->target =3D 1; >> + } >> + >> + if (tb[TCA_CAKE_AUTORATE]) { >> + if (!!nla_get_u32(tb[TCA_CAKE_AUTORATE])) >> + q->rate_flags |=3D CAKE_FLAG_AUTORATE_INGRESS; >> + else >> + q->rate_flags &=3D ~CAKE_FLAG_AUTORATE_INGRESS; >> + } >> + >> + if (tb[TCA_CAKE_INGRESS]) { >> + if (!!nla_get_u32(tb[TCA_CAKE_INGRESS])) >> + q->rate_flags |=3D CAKE_FLAG_INGRESS; >> + else >> + q->rate_flags &=3D ~CAKE_FLAG_INGRESS; >> + } >> + >> + if (tb[TCA_CAKE_ACK_FILTER]) { >> + q->rate_flags &=3D ~(CAKE_FLAG_ACK_FILTER | >> + CAKE_FLAG_ACK_AGGRESSIVE); >> + q->rate_flags |=3D nla_get_u32(tb[TCA_CAKE_ACK_FILTER]) & >> + (CAKE_FLAG_ACK_FILTER | >> + CAKE_FLAG_ACK_AGGRESSIVE); >> + } >> + >> + if (tb[TCA_CAKE_MEMORY]) >> + q->buffer_config_limit =3D nla_get_s32(tb[TCA_CAKE_MEMORY]= ); >> + >> + if (q->tins) { >> + sch_tree_lock(sch); >> + cake_reconfigure(sch); >> + sch_tree_unlock(sch); >> + } >> + >> + return 0; >> +} >> + >> +static void *cake_zalloc(size_t sz) >> +{ >> + void *ptr =3D kzalloc(sz, GFP_KERNEL | __GFP_NOWARN); >> + >> + if (!ptr) >> + ptr =3D vzalloc(sz); >> + return ptr; >> +} >> + > > Modern fq_codel uses kvzalloc and there isn't a __GFP_NOWARN. > >> +static void cake_free(void *addr) >> +{ >> + if (addr) >> + kvfree(addr); >> +} >> + >> +static void cake_destroy(struct Qdisc *sch) >> +{ >> + struct cake_sched_data *q =3D qdisc_priv(sch); >> + >> + qdisc_watchdog_cancel(&q->watchdog); >> + >> + if (q->tins) >> + cake_free(q->tins); >> +} >> + >> +static int cake_init(struct Qdisc *sch, struct nlattr *opt) >> +{ >> + struct cake_sched_data *q =3D qdisc_priv(sch); >> + int i, j; >> + >> + sch->limit =3D 10240; >> + q->tin_mode =3D CAKE_MODE_DIFFSERV3; >> + q->flow_mode =3D CAKE_FLOW_TRIPLE; >> + >> + q->rate_bps =3D 0; /* unlimited by default */ >> + >> + q->interval =3D 100000; /* 100ms default */ >> + q->target =3D 5000; /* 5ms: codel RFC argues >> + * for 5 to 10% of interval >> + */ >> + >> + q->cur_tin =3D 0; >> + q->cur_flow =3D 0; >> + >> + if (opt) { >> + int err =3D cake_change(sch, opt); >> + >> + if (err) >> + return err; >> + } >> + >> + qdisc_watchdog_init(&q->watchdog, sch); >> + >> + quantum_div[0] =3D ~0; >> + for (i =3D 1; i <=3D CAKE_QUEUES; i++) >> + quantum_div[i] =3D 65535 / i; >> + >> + q->tins =3D cake_zalloc(CAKE_MAX_TINS * sizeof(struct cake_tin_dat= a)); >> + if (!q->tins) >> + goto nomem; >> + >> + for (i =3D 0; i < CAKE_MAX_TINS; i++) { >> + struct cake_tin_data *b =3D q->tins + i; >> + >> + b->perturbation =3D prandom_u32(); > > Not that it matters all that much but we probably don't need > more than one perturb. > >> + INIT_LIST_HEAD(&b->new_flows); >> + INIT_LIST_HEAD(&b->old_flows); >> + INIT_LIST_HEAD(&b->decaying_flows); >> + b->sparse_flow_count =3D 0; >> + b->bulk_flow_count =3D 0; >> + b->decaying_flow_count =3D 0; >> + >> + for (j =3D 0; j < CAKE_QUEUES; j++) { >> + struct cake_flow *flow =3D b->flows + j; >> + u32 k =3D j * CAKE_MAX_TINS + i; >> + >> + INIT_LIST_HEAD(&flow->flowchain); >> + cobalt_vars_init(&flow->cvars); >> + >> + q->overflow_heap[k].t =3D i; >> + q->overflow_heap[k].b =3D j; >> + b->overflow_idx[j] =3D k; >> + } >> + } >> + >> + cake_reconfigure(sch); >> + q->avg_peak_bandwidth =3D q->rate_bps; >> + return 0; >> + >> +nomem: >> + cake_destroy(sch); >> + return -ENOMEM; >> +} >> + >> +static int cake_dump(struct Qdisc *sch, struct sk_buff *skb) >> +{ >> + struct cake_sched_data *q =3D qdisc_priv(sch); >> + struct nlattr *opts; >> + >> + opts =3D nla_nest_start(skb, TCA_OPTIONS); >> + if (!opts) >> + goto nla_put_failure; >> + >> + if (nla_put_u32(skb, TCA_CAKE_BASE_RATE, q->rate_bps)) >> + 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_ATM, (q->rate_flags & >> + (CAKE_FLAG_ATM | CAKE_FLAG_PTM)))) >> + goto nla_put_failure; >> + >> + if (nla_put_u32(skb, TCA_CAKE_FLOW_MODE, q->flow_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 + >> + qdisc_dev(sch)->hard_header_len)) >> + 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_ETHERNET, >> + qdisc_dev(sch)->hard_header_len)) >> + 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_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->rate_flags & >> + (CAKE_FLAG_ACK_FILTER | CAKE_FLAG_ACK_AGGRESSIVE))= )) >> + goto nla_put_failure; >> + >> + if (nla_put_u32(skb, TCA_CAKE_MEMORY, q->buffer_config_limit)) >> + 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) >> +{ >> + /* reuse fq_codel stats format */ >> + struct cake_sched_data *q =3D qdisc_priv(sch); >> + struct tc_cake_xstats *st =3D cake_zalloc(sizeof(*st)); > > Modern fq_codel uses kvzalloc. > >> + int i; >> + >> + if (!st) >> + return -1; >> + >> + st->version =3D 5; >> + st->max_tins =3D TC_CAKE_MAX_TINS; >> + st->tin_cnt =3D q->tin_cnt; >> + >> + for (i =3D 0; i < q->tin_cnt; i++) { >> + struct cake_tin_data *b =3D &q->tins[q->tin_order[i]]; >> + >> + st->threshold_rate[i] =3D b->tin_rate_bps; >> + st->target_us[i] =3D cobalt_time_to_us(b->cparams.tar= get); >> + st->interval_us[i] =3D cobalt_time_to_us(b->cparams.int= erval); >> + >> + /* TODO FIXME: add missing aspects of these composite stat= s */ >> + st->sent[i].packets =3D b->packets; >> + st->sent[i].bytes =3D b->bytes; >> + st->dropped[i].packets =3D b->tin_dropped; >> + st->ecn_marked[i].packets =3D b->tin_ecn_mark; >> + st->backlog[i].bytes =3D b->tin_backlog; >> + st->ack_drops[i].packets =3D b->ack_drops; >> + >> + st->peak_delay_us[i] =3D cobalt_time_to_us(b->peak_delay); >> + st->avge_delay_us[i] =3D cobalt_time_to_us(b->avge_delay); >> + st->base_delay_us[i] =3D cobalt_time_to_us(b->base_delay); >> + >> + st->way_indirect_hits[i] =3D b->way_hits; >> + st->way_misses[i] =3D b->way_misses; >> + st->way_collisions[i] =3D b->way_collisions; >> + >> + st->sparse_flows[i] =3D b->sparse_flow_count + >> + b->decaying_flow_count; >> + st->bulk_flows[i] =3D b->bulk_flow_count; >> + st->unresponse_flows[i] =3D b->unresponsive_flow_count; >> + st->spare[i] =3D 0; >> + st->max_skblen[i] =3D b->max_skblen; >> + } >> + st->capacity_estimate =3D q->avg_peak_bandwidth; >> + st->memory_limit =3D q->buffer_limit; >> + st->memory_used =3D q->buffer_max_used; >> + >> + i =3D gnet_stats_copy_app(d, st, sizeof(*st)); >> + cake_free(st); >> + return i; >> +} >> + >> +static struct Qdisc_ops cake_qdisc_ops __read_mostly =3D { >> + .id =3D "cake", >> + .priv_size =3D sizeof(struct cake_sched_data), >> + .enqueue =3D cake_enqueue, >> + .dequeue =3D cake_dequeue, >> + .peek =3D qdisc_peek_dequeued, >> + .init =3D cake_init, >> + .reset =3D cake_reset, >> + .destroy =3D cake_destroy, >> + .change =3D cake_change, >> + .dump =3D cake_dump, >> + .dump_stats =3D cake_dump_stats, >> + .owner =3D 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. Version: " CAKE_VERSION); > _______________________________________________ > Cake mailing list > Cake@lists.bufferbloat.net > https://lists.bufferbloat.net/listinfo/cake