* Re: [PATCH 05/14] net: sched: always take reference to action
From: Vlad Buslov @ 2018-05-14 18:49 UTC (permalink / raw)
To: Jiri Pirko
Cc: netdev, davem, jhs, xiyou.wangcong, pablo, kadlec, fw, ast,
daniel, edumazet, keescook, linux-kernel, netfilter-devel,
coreteam, kliteyn
In-Reply-To: <20180514162301.GC2134@nanopsycho.orion>
On Mon 14 May 2018 at 16:23, Jiri Pirko <jiri@resnulli.us> wrote:
> Mon, May 14, 2018 at 04:27:06PM CEST, vladbu@mellanox.com wrote:
>>Without rtnl lock protection it is no longer safe to use pointer to tc
>>action without holding reference to it. (it can be destroyed concurrently)
>>
>>Remove unsafe action idr lookup function. Instead of it, implement safe tcf
>>idr check function that atomically looks up action in idr and increments
>>its reference and bind counters.
>>
>>Implement both action search and check using new safe function.
>>
>>Signed-off-by: Vlad Buslov <vladbu@mellanox.com>
>>---
>> net/sched/act_api.c | 38 ++++++++++++++++----------------------
>> 1 file changed, 16 insertions(+), 22 deletions(-)
>>
>>diff --git a/net/sched/act_api.c b/net/sched/act_api.c
>>index 1331beb..9459cce 100644
>>--- a/net/sched/act_api.c
>>+++ b/net/sched/act_api.c
>>@@ -284,44 +284,38 @@ int tcf_generic_walker(struct tc_action_net *tn, struct sk_buff *skb,
>> }
>> EXPORT_SYMBOL(tcf_generic_walker);
>>
>>-static struct tc_action *tcf_idr_lookup(u32 index, struct tcf_idrinfo *idrinfo)
>>+bool __tcf_idr_check(struct tc_action_net *tn, u32 index, struct tc_action **a,
>>+ int bind)
>> {
>>- struct tc_action *p = NULL;
>>+ struct tcf_idrinfo *idrinfo = tn->idrinfo;
>>+ struct tc_action *p;
>>
>> spin_lock_bh(&idrinfo->lock);
>
> Why "_bh" variant is necessary here?
It is not my code.
>
>> p = idr_find(&idrinfo->action_idr, index);
>>+ if (p) {
>>+ refcount_inc(&p->tcfa_refcnt);
>>+ if (bind)
>>+ atomic_inc(&p->tcfa_bindcnt);
>>+ }
>> spin_unlock_bh(&idrinfo->lock);
>
> [...]
^ permalink raw reply
* Re: iproute2 - modifying routes in place
From: David Ahern @ 2018-05-14 18:49 UTC (permalink / raw)
To: Ryan Whelan; +Cc: netdev
In-Reply-To: <CAM3m09SowB_i7eoC4FGH=gYBoYRTdBO5S4paVdJ4Mb1RtYfe=A@mail.gmail.com>
On 5/14/18 12:40 PM, Ryan Whelan wrote:
> Same behavior:
>
>
> root@rwhelan-linux ~
> # ip -6 route
> ::1 dev lo proto kernel metric 256 pref medium
> fd9b:caee:ff93:ceef:3431:3831:3930:3031 dev internal0 proto kernel metric
> 256 pref medium
> fd9b:caee:ff93:ceef:3431:3831:3930:3032 dev internal0 src
> fd9b:caee:ff93:ceef:3431:3831:3930:3031 metric 1024 pref medium
> fe80::/64 dev enp0s3 proto kernel metric 256 pref medium
> fe80::/64 dev enp0s8 proto kernel metric 256 pref medium
> fe80::/64 dev internal0 proto kernel metric 256 pref medium
>
> root@rwhelan-linux ~
> # ip -6 route change fd9b:caee:ff93:ceef:3431:3831:3930:3032 dev internal0
> src fd9b:caee:ff93:ceef:3431:3831:3930:3031 metric 10
> RTNETLINK answers: No such file or directory
'change' only sets NLM_F_REPLACE. Since NLM_F_CREATE is not set ('ip ro
replace') it does not add a new route and expects one to exist. Your
table above shows the prefix with metric 256 not metric 10 so the route
does not match. You should be seeing a message in dmesg to this effect.
>
> root@rwhelan-linux ~
> # ip -6 route replace fd9b:caee:ff93:ceef:3431:3831:3930:3032 dev internal0
> src fd9b:caee:ff93:ceef:3431:3831:3930:3031 metric 10
Adds a new entry because of NLM_F_CREATE.
>
> root@rwhelan-linux ~
> # ip -6 route
> ::1 dev lo proto kernel metric 256 pref medium
> fd9b:caee:ff93:ceef:3431:3831:3930:3031 dev internal0 proto kernel metric
> 256 pref medium
> fd9b:caee:ff93:ceef:3431:3831:3930:3032 dev internal0 src
> fd9b:caee:ff93:ceef:3431:3831:3930:3031 metric 10 pref medium
> fd9b:caee:ff93:ceef:3431:3831:3930:3032 dev internal0 src
> fd9b:caee:ff93:ceef:3431:3831:3930:3031 metric 1024 pref medium
> fe80::/64 dev enp0s3 proto kernel metric 256 pref medium
> fe80::/64 dev enp0s8 proto kernel metric 256 pref medium
> fe80::/64 dev internal0 proto kernel metric 256 pref medium
>
> root@rwhelan-linux ~
> # uname -a
> Linux rwhelan-linux 4.17.0-rc3-ipv6-route-bugs+ #2 SMP Mon May 14 11:30:38
> EDT 2018 x86_64 x86_64 x86_64 GNU/Linux
> On Sat, May 12, 2018 at 1:01 PM David Ahern <dsahern@gmail.com> wrote:
>
>> On 5/11/18 4:42 AM, Ryan Whelan wrote:
>>> `ip route` has 2 subcommands that don't seem to work as expected and i'm
>>> not sure if its a bug, or if i'm misunderstanding the semantics.
>
>> Can you try with ipv6/route-bugs branch in
>> https://github.com/dsahern/linux
^ permalink raw reply
* Re: [PATCH net-next 0/3] net: dsa: mv88e6xxx: remove Global 1 setup
From: David Miller @ 2018-05-14 18:50 UTC (permalink / raw)
To: vivien.didelot; +Cc: netdev, linux-kernel, kernel, andrew, f.fainelli
In-Reply-To: <20180511211636.25995-1-vivien.didelot@savoirfairelinux.com>
From: Vivien Didelot <vivien.didelot@savoirfairelinux.com>
Date: Fri, 11 May 2018 17:16:33 -0400
> The mv88e6xxx driver is still writing arbitrary registers at setup time,
> e.g. priority override bits. Add ops for them and provide specific setup
> functions for priority and stats before getting rid of the erroneous
> mv88e6xxx_g1_setup code, as previously done with Global 2.
Series applied, thanks Vivien.
^ permalink raw reply
* Re: [PATCH] net/mlx5: Use 'kvfree()' for memory allocated by 'kvzalloc()'
From: David Miller @ 2018-05-14 18:56 UTC (permalink / raw)
To: christophe.jaillet
Cc: saeedm, matanb, leon, netdev, linux-rdma, linux-kernel,
kernel-janitors
In-Reply-To: <20180512170925.23690-1-christophe.jaillet@wanadoo.fr>
From: Christophe JAILLET <christophe.jaillet@wanadoo.fr>
Date: Sat, 12 May 2018 19:09:25 +0200
> 'out' is allocated with 'kvzalloc()'. 'kvfree()' must be used to free it.
>
> Signed-off-by: Christophe JAILLET <christophe.jaillet@wanadoo.fr>
Saeed, I assume I will see this in one of your forthcoming pull
requests.
Thanks.
^ permalink raw reply
* [PATCH net-next v10 0/7] sched: Add Common Applications Kept Enhanced (cake) qdisc
From: Toke Høiland-Jørgensen @ 2018-05-14 19:00 UTC (permalink / raw)
To: netdev; +Cc: cake
This patch series adds the CAKE qdisc, and has been split up to ease
review.
I have attempted to split out each configurable feature into its own patch.
The first commit adds the base shaper and packet scheduler, while
subsequent commits add the optional features. The full userspace API and
most data structures are included in this commit, but options not
understood in the base version will be ignored.
The result of applying the entire series is identical to the out of tree
version that have seen extensive testing in previous deployments, most
notably as an out of tree patch to OpenWrt. However, note that I have only
compile tested the individual patches; so the whole series should be
considered as a unit.
---
Changelog
v10:
- Christmas tree gardening (fix variable declarations to be in reverse
line length order)
v9:
- Remove duplicated checks around kvfree() and just call it
unconditionally.
- Don't pass __GFP_NOWARN when allocating memory
- Move options in cake_dump() that are related to optional features to
later patches implementing the features.
- Support attaching filters to the qdisc and use the classification
result to select flow queue.
- Support overriding diffserv priority tin from skb->priority
v8:
- Remove inline keyword from function definitions
- Simplify ACK filter; remove the complex state handling to make the
logic easier to follow. This will potentially be a bit less efficient,
but I have not been able to measure a difference.
v7:
- Split up patch into a series to ease review.
- Constify the ACK filter.
v6:
- Fix 6in4 encapsulation checks in ACK filter code
- Checkpatch fixes
v5:
- Refactor ACK filter code and hopefully fix the safety issues
properly this time.
v4:
- Only split GSO packets if shaping at speeds <= 1Gbps
- Fix overhead calculation code to also work for GSO packets
- Don't re-implement kvzalloc()
- Remove local header include from out-of-tree build (fixes kbuild-bot
complaint).
- Several fixes to the ACK filter:
- Check pskb_may_pull() before deref of transport headers.
- Don't run ACK filter logic on split GSO packets
- Fix TCP sequence number compare to deal with wraparounds
v3:
- Use IS_REACHABLE() macro to fix compilation when sch_cake is
built-in and conntrack is a module.
- Switch the stats output to use nested netlink attributes instead
of a versioned struct.
- Remove GPL boilerplate.
- Fix array initialisation style.
v2:
- Fix kbuild test bot complaint
- Clean up the netlink ABI
- Fix checkpatch complaints
- A few tweaks to the behaviour of cake based on testing carried out
while writing the paper.
---
Toke Høiland-Jørgensen (7):
sched: Add Common Applications Kept Enhanced (cake) qdisc
sch_cake: Add ingress mode
sch_cake: Add optional ACK filter
sch_cake: Add NAT awareness to packet classifier
sch_cake: Add DiffServ handling
sch_cake: Add overhead compensation support to the rate shaper
sch_cake: Conditionally split GSO segments
include/uapi/linux/pkt_sched.h | 105 ++
net/sched/Kconfig | 11
net/sched/Makefile | 1
net/sched/sch_cake.c | 2684 ++++++++++++++++++++++++++++++++++++++++
4 files changed, 2801 insertions(+)
create mode 100644 net/sched/sch_cake.c
^ permalink raw reply
* [PATCH net-next v10 5/7] sch_cake: Add DiffServ handling
From: Toke Høiland-Jørgensen @ 2018-05-14 19:00 UTC (permalink / raw)
To: netdev; +Cc: cake
In-Reply-To: <152632431302.4861.16657365789045735410.stgit@alrua-kau>
This adds support for DiffServ-based priority queueing to CAKE. If the
shaper is in use, each priority tier gets its own virtual clock, which
limits that tier's rate to a fraction of the overall shaped rate, to
discourage trying to game the priority mechanism.
CAKE defaults to a simple, three-tier mode that interprets most code points
as "best effort", but places CS1 traffic into a low-priority "bulk" tier
which is assigned 1/16 of the total rate, and a few code points indicating
latency-sensitive or control traffic (specifically TOS4, VA, EF, CS6, CS7)
into a "latency sensitive" high-priority tier, which is assigned 1/4 rate.
The other supported DiffServ modes are a 4-tier mode matching the 802.11e
precedence rules, as well as two 8-tier modes, one of which implements
strict precedence of the eight priority levels.
This commit also adds an optional DiffServ 'wash' mode, which will zero out
the DSCP fields of any packet passing through CAKE. While this can
technically be done with other mechanisms in the kernel, having the feature
available in CAKE significantly decreases configuration complexity; and the
implementation cost is low on top of the other DiffServ-handling code.
Filters and applications can set the skb->priority field to override the
DSCP-based classification into tiers. If TC_H_MAJ(skb->priority) matches CAKE's
qdisc handle, the minor number will be interpreted as a priority tier if it is
less than or equal to the number of configured priority tiers.
Signed-off-by: Toke Høiland-Jørgensen <toke@toke.dk>
---
net/sched/sch_cake.c | 408 +++++++++++++++++++++++++++++++++++++++++++++++++-
1 file changed, 401 insertions(+), 7 deletions(-)
diff --git a/net/sched/sch_cake.c b/net/sched/sch_cake.c
index 2802bb2ace84..ccc6f26b306c 100644
--- a/net/sched/sch_cake.c
+++ b/net/sched/sch_cake.c
@@ -307,6 +307,68 @@ static void cobalt_set_enqueue_time(struct sk_buff *skb,
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, 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[] = {
+ 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[] = {
+ 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[] = {
+ 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};
@@ -1224,6 +1286,46 @@ static unsigned int cake_drop(struct Qdisc *sch, struct sk_buff **to_free)
return idx + (tin << 16);
}
+static 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 u8 cake_handle_diffserv(struct sk_buff *skb, u16 wash)
+{
+ u8 dscp;
+
+ switch (skb->protocol) {
+ case htons(ETH_P_IP):
+ dscp = 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 = 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,
@@ -1238,7 +1340,26 @@ static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch,
struct cake_flow *flow;
u32 idx, tin;
- tin = 0;
+ if (TC_H_MAJ(skb->priority) == sch->handle &&
+ TC_H_MIN(skb->priority) > 0 &&
+ TC_H_MIN(skb->priority) <= q->tin_cnt) {
+ tin = TC_H_MIN(skb->priority) - 1;
+
+ if (q->rate_flags & CAKE_FLAG_WASH)
+ cake_wash_diffserv(skb);
+ } else if (q->tin_mode != CAKE_DIFFSERV_BESTEFFORT) {
+ /* extract the Diffserv Precedence field, if it exists */
+ /* and clear DSCP bits if washing */
+ tin = q->tin_index[cake_handle_diffserv(skb,
+ q->rate_flags & CAKE_FLAG_WASH)];
+ if (unlikely(tin >= q->tin_cnt))
+ tin = 0;
+ } else {
+ tin = 0;
+ if (q->rate_flags & CAKE_FLAG_WASH)
+ cake_wash_diffserv(skb);
+ }
+
b = &q->tins[tin];
/* choose flow to insert into */
@@ -1720,18 +1841,274 @@ static void cake_set_rate(struct cake_tin_data *b, u64 rate, u32 mtu,
b->cparams.p_dec = 1 << 20; /* 1/4096 */
}
-static void cake_reconfigure(struct Qdisc *sch)
+static int cake_config_besteffort(struct Qdisc *sch)
{
struct cake_sched_data *q = qdisc_priv(sch);
struct cake_tin_data *b = &q->tins[0];
- int c, ft = 0;
+ u32 mtu = psched_mtu(qdisc_dev(sch));
+ u32 rate = q->rate_bps;
q->tin_cnt = 1;
- cake_set_rate(b, q->rate_bps, psched_mtu(qdisc_dev(sch)),
- US2TIME(q->target), US2TIME(q->interval));
+
+ q->tin_index = besteffort;
+ q->tin_order = normal_order;
+
+ cake_set_rate(b, rate, mtu, US2TIME(q->target), US2TIME(q->interval));
b->tin_quantum_band = 65535;
b->tin_quantum_prio = 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));
+ u32 rate = q->rate_bps;
+ u32 quantum1 = 256;
+ u32 quantum2 = 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, US2TIME(q->target),
+ US2TIME(q->interval));
+
+ b->tin_quantum_prio = max_t(u16, 1U, quantum1);
+ b->tin_quantum_band = max_t(u16, 1U, quantum2);
+
+ /* calculate next class's parameters */
+ rate *= 7;
+ rate >>= 3;
+
+ quantum1 *= 3;
+ quantum1 >>= 1;
+
+ quantum2 *= 7;
+ quantum2 >>= 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));
+ u32 rate = q->rate_bps;
+ u32 quantum1 = 256;
+ u32 quantum2 = 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, US2TIME(q->target),
+ US2TIME(q->interval));
+
+ b->tin_quantum_prio = max_t(u16, 1U, quantum1);
+ b->tin_quantum_band = max_t(u16, 1U, quantum2);
+
+ /* calculate next class's parameters */
+ rate *= 7;
+ rate >>= 3;
+
+ quantum1 *= 3;
+ quantum1 >>= 1;
+
+ quantum2 *= 7;
+ quantum2 >>= 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));
+ u32 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,
+ 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 = quantum;
+ q->tins[1].tin_quantum_prio = quantum >> 4;
+ q->tins[2].tin_quantum_prio = quantum << 2;
+ q->tins[3].tin_quantum_prio = quantum << 4;
+
+ /* bandwidth-sharing weights */
+ q->tins[0].tin_quantum_band = quantum;
+ q->tins[1].tin_quantum_band = quantum >> 4;
+ q->tins[2].tin_quantum_band = quantum >> 1;
+ q->tins[3].tin_quantum_band = 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));
+ u32 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,
+ 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->interval));
+
+ /* priority weights */
+ q->tins[0].tin_quantum_prio = quantum;
+ q->tins[1].tin_quantum_prio = quantum >> 4;
+ q->tins[2].tin_quantum_prio = quantum << 4;
+
+ /* bandwidth-sharing weights */
+ q->tins[0].tin_quantum_band = quantum;
+ q->tins[1].tin_quantum_band = quantum >> 4;
+ q->tins[2].tin_quantum_band = 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;
@@ -1775,6 +2152,16 @@ static int cake_change(struct Qdisc *sch, struct nlattr *opt,
if (tb[TCA_CAKE_BASE_RATE])
q->rate_bps = nla_get_u32(tb[TCA_CAKE_BASE_RATE]);
+ 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 = (nla_get_u32(tb[TCA_CAKE_FLOW_MODE]) &
CAKE_FLOW_MASK);
@@ -1844,7 +2231,7 @@ static int cake_init(struct Qdisc *sch, struct nlattr *opt,
int i, j, err;
sch->limit = 10240;
- q->tin_mode = CAKE_DIFFSERV_BESTEFFORT;
+ q->tin_mode = CAKE_DIFFSERV_DIFFSERV3;
q->flow_mode = CAKE_FLOW_TRIPLE;
q->rate_bps = 0; /* unlimited by default */
@@ -1952,6 +2339,13 @@ static int cake_dump(struct Qdisc *sch, struct sk_buff *skb)
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;
+
return nla_nest_end(skb, opts);
nla_put_failure:
@@ -1999,7 +2393,7 @@ static int cake_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
} while (0)
for (i = 0; i < q->tin_cnt; i++) {
- struct cake_tin_data *b = &q->tins[i];
+ struct cake_tin_data *b = &q->tins[q->tin_order[i]];
ts = nla_nest_start(d->skb, i + 1);
if (!ts)
^ permalink raw reply related
* [PATCH net-next v10 4/7] sch_cake: Add NAT awareness to packet classifier
From: Toke Høiland-Jørgensen @ 2018-05-14 19:00 UTC (permalink / raw)
To: netdev; +Cc: cake
In-Reply-To: <152632431302.4861.16657365789045735410.stgit@alrua-kau>
When CAKE is deployed on a gateway that also performs NAT (which is a
common deployment mode), the host fairness mechanism cannot distinguish
internal hosts from each other, and so fails to work correctly.
To fix this, we add an optional NAT awareness mode, which will query the
kernel conntrack mechanism to obtain the pre-NAT addresses for each packet
and use that in the flow and host hashing.
When the shaper is enabled and the host is already performing NAT, the cost
of this lookup is negligible. However, in unlimited mode with no NAT being
performed, there is a significant CPU cost at higher bandwidths. For this
reason, the feature is turned off by default.
Signed-off-by: Toke Høiland-Jørgensen <toke@toke.dk>
---
net/sched/sch_cake.c | 72 ++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 72 insertions(+)
diff --git a/net/sched/sch_cake.c b/net/sched/sch_cake.c
index 4bc178c09f3a..2802bb2ace84 100644
--- a/net/sched/sch_cake.c
+++ b/net/sched/sch_cake.c
@@ -71,6 +71,12 @@
#include <net/tcp.h>
#include <net/flow_dissector.h>
+#if IS_REACHABLE(CONFIG_NF_CONNTRACK)
+#include <net/netfilter/nf_conntrack_core.h>
+#include <net/netfilter/nf_conntrack_zones.h>
+#include <net/netfilter/nf_conntrack.h>
+#endif
+
#define CAKE_SET_WAYS (8)
#define CAKE_MAX_TINS (8)
#define CAKE_QUEUES (1024)
@@ -522,6 +528,60 @@ static bool cobalt_should_drop(struct cobalt_vars *vars,
return drop;
}
+#if IS_REACHABLE(CONFIG_NF_CONNTRACK)
+
+static void cake_update_flowkeys(struct flow_keys *keys,
+ const struct sk_buff *skb)
+{
+ const struct nf_conntrack_tuple *tuple;
+ enum ip_conntrack_info ctinfo;
+ struct nf_conn *ct;
+ bool rev = false;
+
+ if (tc_skb_protocol(skb) != htons(ETH_P_IP))
+ return;
+
+ ct = nf_ct_get(skb, &ctinfo);
+ if (ct) {
+ tuple = 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 = nf_conntrack_find_get(dev_net(skb->dev),
+ &nf_ct_zone_dflt,
+ &srctuple);
+ if (!hash)
+ return;
+
+ rev = true;
+ ct = nf_ct_tuplehash_to_ctrack(hash);
+ tuple = nf_ct_tuple(ct, !hash->tuple.dst.dir);
+ }
+
+ keys->addrs.v4addrs.src = rev ? tuple->dst.u3.ip : tuple->src.u3.ip;
+ keys->addrs.v4addrs.dst = rev ? tuple->src.u3.ip : tuple->dst.u3.ip;
+
+ if (keys->ports.ports) {
+ keys->ports.src = rev ? tuple->dst.u.all : tuple->src.u.all;
+ keys->ports.dst = rev ? tuple->src.u.all : tuple->dst.u.all;
+ }
+ if (rev)
+ nf_ct_put(ct);
+}
+#else
+static void cake_update_flowkeys(struct flow_keys *keys,
+ const struct sk_buff *skb)
+{
+ /* There is nothing we can do here without CONNTRACK */
+}
+#endif
+
/* Cake has several subtle multiple bit settings. In these cases you
* would be matching triple isolate mode as well.
*/
@@ -549,6 +609,9 @@ static u32 cake_hash(struct cake_tin_data *q, const struct sk_buff *skb,
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.
@@ -1716,6 +1779,12 @@ static int cake_change(struct Qdisc *sch, struct nlattr *opt,
q->flow_mode = (nla_get_u32(tb[TCA_CAKE_FLOW_MODE]) &
CAKE_FLOW_MASK);
+ if (tb[TCA_CAKE_NAT]) {
+ q->flow_mode &= ~CAKE_FLOW_NAT_FLAG;
+ q->flow_mode |= CAKE_FLOW_NAT_FLAG *
+ !!nla_get_u32(tb[TCA_CAKE_NAT]);
+ }
+
if (tb[TCA_CAKE_RTT]) {
q->interval = nla_get_u32(tb[TCA_CAKE_RTT]);
@@ -1880,6 +1949,9 @@ static int cake_dump(struct Qdisc *sch, struct sk_buff *skb)
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;
+
return nla_nest_end(skb, opts);
nla_put_failure:
^ permalink raw reply related
* [PATCH net-next v10 2/7] sch_cake: Add ingress mode
From: Toke Høiland-Jørgensen @ 2018-05-14 19:00 UTC (permalink / raw)
To: netdev; +Cc: cake
In-Reply-To: <152632431302.4861.16657365789045735410.stgit@alrua-kau>
The ingress mode is meant to be enabled when CAKE runs downlink of the
actual bottleneck (such as on an IFB device). The mode changes the shaper
to also account dropped packets to the shaped rate, as these have already
traversed the bottleneck.
Enabling ingress mode will also tune the AQM to always keep at least two
packets queued *for each flow*. This is done by scaling the minimum queue
occupancy level that will disable the AQM by the number of active bulk
flows. The rationale for this is that retransmits are more expensive in
ingress mode, since dropped packets have to traverse the bottleneck again
when they are retransmitted; thus, being more lenient and keeping a minimum
number of packets queued will improve throughput in cases where the number
of active flows are so large that they saturate the bottleneck even at
their minimum window size.
This commit also adds a separate switch to enable ingress mode rate
autoscaling. If enabled, the autoscaling code will observe the actual
traffic rate and adjust the shaper rate to match it. This can help avoid
latency increases in the case where the actual bottleneck rate decreases
below the shaped rate. The scaling filters out spikes by an EWMA filter.
Signed-off-by: Toke Høiland-Jørgensen <toke@toke.dk>
---
net/sched/sch_cake.c | 78 +++++++++++++++++++++++++++++++++++++++++++++++---
1 file changed, 74 insertions(+), 4 deletions(-)
diff --git a/net/sched/sch_cake.c b/net/sched/sch_cake.c
index e22c712602fa..179bfa9e501f 100644
--- a/net/sched/sch_cake.c
+++ b/net/sched/sch_cake.c
@@ -442,7 +442,8 @@ static bool cobalt_queue_empty(struct cobalt_vars *vars,
static bool cobalt_should_drop(struct cobalt_vars *vars,
struct cobalt_params *p,
cobalt_time_t now,
- struct sk_buff *skb)
+ struct sk_buff *skb,
+ u32 bulk_flows)
{
bool next_due, over_target, drop = false;
cobalt_tdiff_t sojourn, schedule;
@@ -465,6 +466,7 @@ static bool cobalt_should_drop(struct cobalt_vars *vars,
sojourn = now - cobalt_get_enqueue_time(skb);
schedule = 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 && schedule >= 0;
@@ -915,6 +917,9 @@ static unsigned int cake_drop(struct Qdisc *sch, struct sk_buff **to_free)
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--;
@@ -990,8 +995,39 @@ static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch,
cake_heapify_up(q, b->overflow_idx[idx]);
/* incoming bandwidth capacity estimate */
- q->avg_window_bytes = 0;
- q->last_packet_time = now;
+ if (q->rate_flags & CAKE_FLAG_AUTORATE_INGRESS) {
+ u64 packet_interval = 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 = now - q->avg_window_begin;
+ u64 b = q->avg_window_bytes * (u64)NSEC_PER_SEC;
+
+ do_div(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 (now - q->last_reconfig_time > (NSEC_PER_SEC / 4)) {
+ 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) {
@@ -1246,14 +1282,26 @@ static struct sk_buff *cake_dequeue(struct Qdisc *sch)
}
/* Last packet in queue may be marked, shouldn't be dropped */
- if (!cobalt_should_drop(&flow->cvars, &b->cparams, now, skb) ||
+ 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;
+ }
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;
@@ -1432,6 +1480,20 @@ static int cake_change(struct Qdisc *sch, struct nlattr *opt,
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_MEMORY])
q->buffer_config_limit = nla_get_u32(tb[TCA_CAKE_MEMORY]);
@@ -1554,6 +1616,14 @@ static int cake_dump(struct Qdisc *sch, struct sk_buff *skb)
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;
+
return nla_nest_end(skb, opts);
nla_put_failure:
^ permalink raw reply related
* [PATCH net-next v10 3/7] sch_cake: Add optional ACK filter
From: Toke Høiland-Jørgensen @ 2018-05-14 19:00 UTC (permalink / raw)
To: netdev; +Cc: cake
In-Reply-To: <152632431302.4861.16657365789045735410.stgit@alrua-kau>
The ACK filter is an optional feature of CAKE which is designed to improve
performance on links with very asymmetrical rate limits. On such links
(which are unfortunately quite prevalent, especially for DSL and cable
subscribers), the downstream throughput can be limited by the number of
ACKs capable of being transmitted in the *upstream* direction.
Filtering ACKs can, in general, have adverse effects on TCP performance
because it interferes with ACK clocking (especially in slow start), and it
reduces the flow's resiliency to ACKs being dropped further along the path.
To alleviate these drawbacks, the ACK filter in CAKE tries its best to
always keep enough ACKs queued to ensure forward progress in the TCP flow
being filtered. It does this by only filtering redundant ACKs. In its
default 'conservative' mode, the filter will always keep at least two
redundant ACKs in the queue, while in 'aggressive' mode, it will filter
down to a single ACK.
The ACK filter works by inspecting the per-flow queue on every packet
enqueue. Starting at the head of the queue, the filter looks for another
eligible packet to drop (so the ACK being dropped is always closer to the
head of the queue than the packet being enqueued). An ACK is eligible only
if it ACKs *fewer* cumulative bytes than the new packet being enqueued.
This prevents duplicate ACKs from being filtered (unless there is also SACK
options present), to avoid interfering with retransmission logic. In
aggressive mode, an eligible packet is always dropped, while in
conservative mode, at least two ACKs are kept in the queue. Only pure ACKs
(with no data segments) are considered eligible for dropping, but when an
ACK with data segments is enqueued, this can cause another pure ACK to
become eligible for dropping.
The approach described above ensures that this ACK filter avoids most of
the drawbacks of a naive filtering mechanism that only keeps flow state but
does not inspect the queue. This is the rationale for including the ACK
filter in CAKE itself rather than as separate module (as the TC filter, for
instance).
Our performance evaluation has shown that on a 30/1 Mbps link with a
bidirectional traffic test (RRUL), turning on the ACK filter on the
upstream link improves downstream throughput by ~20% (both modes) and
upstream throughput by ~12% in conservative mode and ~40% in aggressive
mode, at the cost of ~5ms of inter-flow latency due to the increased
congestion.
In *really* pathological cases, the effect can be a lot more; for instance,
the ACK filter increases the achievable downstream throughput on a link
with 100 Kbps in the upstream direction by an order of magnitude (from ~2.5
Mbps to ~25 Mbps).
Finally, even though we consider the ACK filter to be safer than most, we
do not recommend turning it on everywhere: on more symmetrical link
bandwidths the effect is negligible at best.
Signed-off-by: Toke Høiland-Jørgensen <toke@toke.dk>
---
net/sched/sch_cake.c | 260 ++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 258 insertions(+), 2 deletions(-)
diff --git a/net/sched/sch_cake.c b/net/sched/sch_cake.c
index 179bfa9e501f..4bc178c09f3a 100644
--- a/net/sched/sch_cake.c
+++ b/net/sched/sch_cake.c
@@ -764,6 +764,239 @@ static void flow_queue_add(struct cake_flow *flow, struct sk_buff *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 bool cake_tcph_is_sack(const struct tcphdr *tcph)
+{
+ /* 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 == TCPOPT_SACK)
+ return true;
+ ptr += opsize - 2;
+ length -= opsize;
+ }
+
+ return false;
+}
+
+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;
+ const struct tcphdr *tcph, *tcph_check;
+ const struct iphdr *iph, *iph_check;
+ struct ipv6hdr _iph, _iph_check;
+ const struct sk_buff *skb;
+ struct tcphdr _tcph_check;
+ int seglen, num_found = 0;
+ unsigned char _tcph[64]; /* need to hold maximum hdr size */
+
+ /* 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;
+
+ /* 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 */
+ 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;
+ }
+
+ /* 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
+ * 0x0FFF0000 = all TCP flags (confirm ACK=1, others zero)
+ * 0x01C00000 = NS/CWR/ECE (safe to ignore)
+ * 0x0E3F0000 = 0x0FFF0000 & ~0x01C00000
+ * must be 'pure' ACK, contain zero bytes of segment data
+ * options are ignored
+ */
+ if (((tcp_flag_word(tcph_check) &
+ cpu_to_be32(0x0E3F0000)) != TCP_FLAG_ACK) ||
+ ((seglen - __tcp_hdrlen(tcph_check)) != 0))
+ continue;
+
+ /* The triggering packet must ACK more data than the ACK under
+ * consideration, either because is has a strictly higher ACK
+ * sequence number or because it is a SACK
+ */
+ if ((ntohl(tcph_check->ack_seq) == ntohl(tcph->ack_seq) &&
+ !cake_tcph_is_sack(tcph)) ||
+ (int32_t)(ntohl(tcph_check->ack_seq) -
+ ntohl(tcph->ack_seq)) > 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;
+ }
+
+ if (num_found++ > 0 || aggressive)
+ goto found;
+ }
+
+ return NULL;
+
+found:
+ if (elig_ack_prev)
+ elig_ack_prev->next = elig_ack->next;
+ else
+ flow->head = elig_ack->next;
+
+ elig_ack->next = NULL;
+
+ return elig_ack;
+}
+
static cobalt_time_t cake_ewma(cobalt_time_t avg, cobalt_time_t sample,
u32 shift)
{
@@ -937,6 +1170,7 @@ static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch,
int len = qdisc_pkt_len(skb);
u64 now = cobalt_get_time();
int uninitialized_var(ret);
+ struct sk_buff *ack = NULL;
struct cake_tin_data *b;
struct cake_flow *flow;
u32 idx, tin;
@@ -980,8 +1214,24 @@ static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch,
cobalt_set_enqueue_time(skb, now);
flow_queue_add(flow, skb);
- sch->q.qlen++;
- q->buffer_used += skb->truesize;
+ 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++;
@@ -1494,6 +1744,9 @@ static int cake_change(struct Qdisc *sch, struct nlattr *opt,
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]);
@@ -1624,6 +1877,9 @@ static int cake_dump(struct Qdisc *sch, struct sk_buff *skb)
!!(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;
+
return nla_nest_end(skb, opts);
nla_put_failure:
^ permalink raw reply related
* [PATCH net-next v10 6/7] sch_cake: Add overhead compensation support to the rate shaper
From: Toke Høiland-Jørgensen @ 2018-05-14 19:00 UTC (permalink / raw)
To: netdev; +Cc: cake
In-Reply-To: <152632431302.4861.16657365789045735410.stgit@alrua-kau>
This commit adds configurable overhead compensation support to the rate
shaper. With this feature, userspace can configure the actual bottleneck
link overhead and encapsulation mode used, which will be used by the shaper
to calculate the precise duration of each packet on the wire.
This feature is needed because CAKE is often deployed one or two hops
upstream of the actual bottleneck (which can be, e.g., inside a DSL or
cable modem). In this case, the link layer characteristics and overhead
reported by the kernel does not match the actual bottleneck. Being able to
set the actual values in use makes it possible to configure the shaper rate
much closer to the actual bottleneck rate (our experience shows it is
possible to get with 0.1% of the actual physical bottleneck rate), thus
keeping latency low without sacrificing bandwidth.
The overhead compensation has three tunables: A fixed per-packet overhead
size (which, if set, will be accounted from the IP packet header), a
minimum packet size (MPU) and a framing mode supporting either ATM or PTM
framing. We include a set of common keywords in TC to help users configure
the right parameters. If no overhead value is set, the value reported by
the kernel is used.
Signed-off-by: Toke Høiland-Jørgensen <toke@toke.dk>
---
net/sched/sch_cake.c | 123 ++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 122 insertions(+), 1 deletion(-)
diff --git a/net/sched/sch_cake.c b/net/sched/sch_cake.c
index ccc6f26b306c..6314a089a204 100644
--- a/net/sched/sch_cake.c
+++ b/net/sched/sch_cake.c
@@ -275,6 +275,7 @@ enum {
struct cobalt_skb_cb {
cobalt_time_t enqueue_time;
+ u32 adjusted_len;
};
static cobalt_time_t cobalt_get_time(void)
@@ -1130,6 +1131,87 @@ static cobalt_time_t cake_ewma(cobalt_time_t avg, cobalt_time_t sample,
return avg;
}
+static u32 cake_overhead(struct cake_sched_data *q, struct sk_buff *skb)
+{
+ const struct skb_shared_info *shinfo = skb_shinfo(skb);
+ u32 off = skb_network_offset(skb);
+ u32 len = qdisc_pkt_len(skb);
+ u16 segs = 1;
+
+ if (unlikely(shinfo->gso_size)) {
+ /* borrowed from qdisc_pkt_len_init() */
+ unsigned int hdr_len;
+
+ 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;
+
+ /* The last segment may be shorter; we ignore this, which means
+ * that we will over-estimate the size of the whole GSO segment
+ * by the difference in size. This is conservative, so we live
+ * with that to avoid the complexity of dealing with it.
+ */
+ len = shinfo->gso_size + hdr_len;
+ }
+
+ q->avg_netoff = cake_ewma(q->avg_netoff, off << 16, 8);
+
+ 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;
+
+ get_cobalt_cb(skb)->adjusted_len = len * segs;
+ return len;
+}
+
static void cake_heap_swap(struct cake_sched_data *q, u16 i, u16 j)
{
struct cake_heap_entry ii = q->overflow_heap[i];
@@ -1207,7 +1289,7 @@ static int cake_advance_shaper(struct cake_sched_data *q,
struct sk_buff *skb,
u64 now, bool drop)
{
- u32 len = qdisc_pkt_len(skb);
+ u32 len = get_cobalt_cb(skb)->adjusted_len;
/* charge packet bandwidth to this tin
* and to the global shaper.
@@ -1396,6 +1478,7 @@ static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch,
b->max_skblen = len;
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)
@@ -2172,6 +2255,31 @@ static int cake_change(struct Qdisc *sch, struct nlattr *opt,
!!nla_get_u32(tb[TCA_CAKE_NAT]);
}
+ 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]);
@@ -2346,6 +2454,19 @@ static int cake_dump(struct Qdisc *sch, struct sk_buff *skb)
!!(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;
+
return nla_nest_end(skb, opts);
nla_put_failure:
^ permalink raw reply related
* [PATCH net-next v10 1/7] sched: Add Common Applications Kept Enhanced (cake) qdisc
From: Toke Høiland-Jørgensen @ 2018-05-14 19:00 UTC (permalink / raw)
To: netdev; +Cc: cake
In-Reply-To: <152632431302.4861.16657365789045735410.stgit@alrua-kau>
sch_cake targets the home router use case and is intended to squeeze the
most bandwidth and latency out of even the slowest ISP links and routers,
while presenting an API simple enough that even an ISP can configure it.
Example of use on a cable ISP uplink:
tc qdisc add dev eth0 cake bandwidth 20Mbit nat docsis ack-filter
To shape a cable download link (ifb and tc-mirred setup elided)
tc qdisc add dev ifb0 cake bandwidth 200mbit nat docsis ingress wash
CAKE is filled with:
* A hybrid Codel/Blue AQM algorithm, "Cobalt", tied to an FQ_Codel
derived Flow Queuing system, which autoconfigures based on the bandwidth.
* A novel "triple-isolate" mode (the default) which balances per-host
and per-flow FQ even through NAT.
* An deficit based shaper, that can also be used in an unlimited mode.
* 8 way set associative hashing to reduce flow collisions to a minimum.
* A reasonable interpretation of various diffserv latency/loss tradeoffs.
* Support for zeroing diffserv markings for entering and exiting traffic.
* Support for interacting well with Docsis 3.0 shaper framing.
* Extensive support for DSL framing types.
* Support for ack filtering.
* Extensive statistics for measuring, loss, ecn markings, latency
variation.
A paper describing the design of CAKE is available at
https://arxiv.org/abs/1804.07617, and will be published at the 2018 IEEE
International Symposium on Local and Metropolitan Area Networks (LANMAN).
This patch adds the base shaper and packet scheduler, while subsequent
commits add the optional (configurable) features. The full userspace API
and most data structures are included in this commit, but options not
understood in the base version will be ignored.
Various versions baking have been available as an out of tree build for
kernel versions going back to 3.10, as the embedded router world has been
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 simpler configuration.
CAKE's principal author is Jonathan Morton, with contributions from
Kevin Darbyshire-Bryant, Toke Høiland-Jørgensen, Sebastian Moeller,
Ryan Mounce, Guido Sarducci, Dean Scarff, Nils Andreas Svee, Dave Täht,
and Loganaden Velvindron.
Testing from Pete Heist, Georgios Amanakis, and the many other members of
the cake@lists.bufferbloat.net mailing list.
tc -s qdisc show dev eth2
qdisc cake 1: root refcnt 2 bandwidth 100Mbit diffserv3 triple-isolate rtt 100.0ms raw overhead 0
Sent 0 bytes 0 pkt (dropped 0, overlimits 0 requeues 0)
backlog 0b 0p requeues 0
memory used: 0b of 5000000b
capacity estimate: 100Mbit
min/max network layer size: 65535 / 0
min/max overhead-adjusted size: 65535 / 0
average network hdr offset: 0
Bulk Best Effort Voice
thresh 6250Kbit 100Mbit 25Mbit
target 5.0ms 5.0ms 5.0ms
interval 100.0ms 100.0ms 100.0ms
pk_delay 0us 0us 0us
av_delay 0us 0us 0us
sp_delay 0us 0us 0us
pkts 0 0 0
bytes 0 0 0
way_inds 0 0 0
way_miss 0 0 0
way_cols 0 0 0
drops 0 0 0
marks 0 0 0
ack_drop 0 0 0
sp_flows 0 0 0
bk_flows 0 0 0
un_flows 0 0 0
max_len 0 0 0
quantum 300 1514 762
Tested-by: Pete Heist <peteheist@gmail.com>
Tested-by: Georgios Amanakis <gamanakis@gmail.com>
Signed-off-by: Dave Taht <dave.taht@gmail.com>
Signed-off-by: Toke Høiland-Jørgensen <toke@toke.dk>
---
include/uapi/linux/pkt_sched.h | 105 ++
net/sched/Kconfig | 11
net/sched/Makefile | 1
net/sched/sch_cake.c | 1724 ++++++++++++++++++++++++++++++++++++++++
4 files changed, 1841 insertions(+)
create mode 100644 net/sched/sch_cake.c
diff --git a/include/uapi/linux/pkt_sched.h b/include/uapi/linux/pkt_sched.h
index 37b5096ae97b..bc581473c0b0 100644
--- a/include/uapi/linux/pkt_sched.h
+++ b/include/uapi/linux/pkt_sched.h
@@ -934,4 +934,109 @@ enum {
#define TCA_CBS_MAX (__TCA_CBS_MAX - 1)
+/* CAKE */
+enum {
+ TCA_CAKE_UNSPEC,
+ TCA_CAKE_BASE_RATE,
+ TCA_CAKE_DIFFSERV_MODE,
+ TCA_CAKE_ATM,
+ TCA_CAKE_FLOW_MODE,
+ TCA_CAKE_OVERHEAD,
+ TCA_CAKE_RTT,
+ TCA_CAKE_TARGET,
+ TCA_CAKE_AUTORATE,
+ TCA_CAKE_MEMORY,
+ TCA_CAKE_NAT,
+ TCA_CAKE_RAW,
+ TCA_CAKE_WASH,
+ TCA_CAKE_MPU,
+ TCA_CAKE_INGRESS,
+ TCA_CAKE_ACK_FILTER,
+ TCA_CAKE_SPLIT_GSO,
+ __TCA_CAKE_MAX
+};
+#define TCA_CAKE_MAX (__TCA_CAKE_MAX - 1)
+
+enum {
+ __TCA_CAKE_STATS_INVALID,
+ TCA_CAKE_STATS_CAPACITY_ESTIMATE,
+ TCA_CAKE_STATS_MEMORY_LIMIT,
+ TCA_CAKE_STATS_MEMORY_USED,
+ TCA_CAKE_STATS_AVG_NETOFF,
+ TCA_CAKE_STATS_MIN_NETLEN,
+ TCA_CAKE_STATS_MAX_NETLEN,
+ TCA_CAKE_STATS_MIN_ADJLEN,
+ TCA_CAKE_STATS_MAX_ADJLEN,
+ TCA_CAKE_STATS_TIN_STATS,
+ __TCA_CAKE_STATS_MAX
+};
+#define TCA_CAKE_STATS_MAX (__TCA_CAKE_STATS_MAX - 1)
+
+enum {
+ __TCA_CAKE_TIN_STATS_INVALID,
+ TCA_CAKE_TIN_STATS_PAD,
+ TCA_CAKE_TIN_STATS_SENT_PACKETS,
+ TCA_CAKE_TIN_STATS_SENT_BYTES64,
+ TCA_CAKE_TIN_STATS_DROPPED_PACKETS,
+ TCA_CAKE_TIN_STATS_DROPPED_BYTES64,
+ TCA_CAKE_TIN_STATS_ACKS_DROPPED_PACKETS,
+ TCA_CAKE_TIN_STATS_ACKS_DROPPED_BYTES64,
+ TCA_CAKE_TIN_STATS_ECN_MARKED_PACKETS,
+ TCA_CAKE_TIN_STATS_ECN_MARKED_BYTES64,
+ TCA_CAKE_TIN_STATS_BACKLOG_PACKETS,
+ TCA_CAKE_TIN_STATS_BACKLOG_BYTES64,
+ TCA_CAKE_TIN_STATS_THRESHOLD_RATE,
+ TCA_CAKE_TIN_STATS_TARGET_US,
+ TCA_CAKE_TIN_STATS_INTERVAL_US,
+ TCA_CAKE_TIN_STATS_WAY_INDIRECT_HITS,
+ TCA_CAKE_TIN_STATS_WAY_MISSES,
+ TCA_CAKE_TIN_STATS_WAY_COLLISIONS,
+ TCA_CAKE_TIN_STATS_PEAK_DELAY_US,
+ TCA_CAKE_TIN_STATS_AVG_DELAY_US,
+ TCA_CAKE_TIN_STATS_BASE_DELAY_US,
+ TCA_CAKE_TIN_STATS_SPARSE_FLOWS,
+ TCA_CAKE_TIN_STATS_BULK_FLOWS,
+ TCA_CAKE_TIN_STATS_UNRESPONSIVE_FLOWS,
+ TCA_CAKE_TIN_STATS_MAX_SKBLEN,
+ TCA_CAKE_TIN_STATS_FLOW_QUANTUM,
+ __TCA_CAKE_TIN_STATS_MAX
+};
+#define TCA_CAKE_TIN_STATS_MAX (__TCA_CAKE_TIN_STATS_MAX - 1)
+#define TC_CAKE_MAX_TINS (8)
+
+enum {
+ CAKE_FLOW_NONE = 0,
+ CAKE_FLOW_SRC_IP,
+ CAKE_FLOW_DST_IP,
+ CAKE_FLOW_HOSTS, /* = CAKE_FLOW_SRC_IP | CAKE_FLOW_DST_IP */
+ CAKE_FLOW_FLOWS,
+ CAKE_FLOW_DUAL_SRC, /* = CAKE_FLOW_SRC_IP | CAKE_FLOW_FLOWS */
+ CAKE_FLOW_DUAL_DST, /* = CAKE_FLOW_DST_IP | CAKE_FLOW_FLOWS */
+ CAKE_FLOW_TRIPLE, /* = CAKE_FLOW_HOSTS | CAKE_FLOW_FLOWS */
+ CAKE_FLOW_MAX,
+};
+
+enum {
+ CAKE_DIFFSERV_DIFFSERV3 = 0,
+ CAKE_DIFFSERV_DIFFSERV4,
+ CAKE_DIFFSERV_DIFFSERV8,
+ CAKE_DIFFSERV_BESTEFFORT,
+ CAKE_DIFFSERV_PRECEDENCE,
+ CAKE_DIFFSERV_MAX
+};
+
+enum {
+ CAKE_ACK_NONE = 0,
+ CAKE_ACK_FILTER,
+ CAKE_ACK_AGGRESSIVE,
+ CAKE_ACK_MAX
+};
+
+enum {
+ CAKE_ATM_NONE = 0,
+ CAKE_ATM_ATM,
+ CAKE_ATM_PTM,
+ CAKE_ATM_MAX
+};
+
#endif
diff --git a/net/sched/Kconfig b/net/sched/Kconfig
index a01169fb5325..6e7d614b5757 100644
--- a/net/sched/Kconfig
+++ b/net/sched/Kconfig
@@ -284,6 +284,17 @@ config NET_SCH_FQ_CODEL
If unsure, say N.
+config NET_SCH_CAKE
+ tristate "Common Applications Kept Enhanced (CAKE)"
+ help
+ Say Y here if you want to use the Common Applications Kept Enhanced
+ (CAKE) queue management algorithm.
+
+ To compile this driver as a module, choose M here: the module
+ will be called sch_cake.
+
+ If unsure, say N.
+
config NET_SCH_FQ
tristate "Fair Queue"
help
diff --git a/net/sched/Makefile b/net/sched/Makefile
index 8811d3804878..435054cee32c 100644
--- a/net/sched/Makefile
+++ b/net/sched/Makefile
@@ -50,6 +50,7 @@ obj-$(CONFIG_NET_SCH_CHOKE) += sch_choke.o
obj-$(CONFIG_NET_SCH_QFQ) += sch_qfq.o
obj-$(CONFIG_NET_SCH_CODEL) += sch_codel.o
obj-$(CONFIG_NET_SCH_FQ_CODEL) += sch_fq_codel.o
+obj-$(CONFIG_NET_SCH_CAKE) += sch_cake.o
obj-$(CONFIG_NET_SCH_FQ) += sch_fq.o
obj-$(CONFIG_NET_SCH_HHF) += sch_hhf.o
obj-$(CONFIG_NET_SCH_PIE) += sch_pie.o
diff --git a/net/sched/sch_cake.c b/net/sched/sch_cake.c
new file mode 100644
index 000000000000..e22c712602fa
--- /dev/null
+++ b/net/sched/sch_cake.c
@@ -0,0 +1,1724 @@
+// 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 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/version.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>
+
+#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
+#define US2TIME(a) (a * (u64)NSEC_PER_USEC)
+
+typedef u64 cobalt_time_t;
+typedef s64 cobalt_tdiff_t;
+
+/* 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 {
+ cobalt_time_t interval;
+ cobalt_time_t target;
+ cobalt_time_t 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;
+ cobalt_time_t drop_next;
+ cobalt_time_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;
+ 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_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 */
+ 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) */
+ 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 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;
+
+ /* time_next = 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;
+
+ /* 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 {
+ cobalt_time_t enqueue_time;
+};
+
+static cobalt_time_t cobalt_get_time(void)
+{
+ return ktime_get_ns();
+}
+
+static u32 cobalt_time_to_us(cobalt_time_t val)
+{
+ do_div(val, NSEC_PER_USEC);
+ return (u32)val;
+}
+
+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 cobalt_time_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,
+ cobalt_time_t now)
+{
+ get_cobalt_cb(skb)->enqueue_time = now;
+}
+
+static u16 quantum_div[CAKE_QUEUES + 1] = {0};
+
+#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 cobalt_time_t cobalt_control(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. 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,
+ cobalt_time_t now)
+{
+ bool up = false;
+
+ if ((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,
+ cobalt_time_t now)
+{
+ bool down = false;
+
+ if (vars->p_drop && (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 && (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,
+ cobalt_time_t now,
+ struct sk_buff *skb)
+{
+ bool next_due, over_target, drop = false;
+ cobalt_tdiff_t sojourn, schedule;
+
+/* 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 = now - cobalt_get_enqueue_time(skb);
+ schedule = now - vars->drop_next;
+ over_target = sojourn > p->target &&
+ sojourn > p->mtu_time * 4;
+ next_due = vars->count && 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 = 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 = now - vars->drop_next;
+ next_due = vars->count && 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 = now + p->interval;
+ else if (schedule > 0 && !drop)
+ vars->drop_next = now;
+
+ return drop;
+}
+
+/* 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)
+{
+ u32 flow_hash = 0, srchost_hash, dsthost_hash;
+ u16 reduced_hash, srchost_idx, dsthost_idx;
+ struct flow_keys keys, host_keys;
+
+ if (unlikely(flow_mode == CAKE_FLOW_NONE))
+ return 0;
+
+ skb_flow_dissect_flow_keys(skb, &keys,
+ FLOW_DISSECTOR_F_STOP_AT_FLOW_LABEL);
+
+ /* 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 (flow_mode & CAKE_FLOW_FLOWS)
+ flow_hash = flow_hash_from_keys(&keys);
+
+ 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++;
+ q->hosts[q->flows[reduced_hash].srchost].srchost_refcnt--;
+ q->hosts[q->flows[reduced_hash].dsthost].dsthost_refcnt--;
+ 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_refcnt)
+ break;
+ }
+ q->hosts[outer_hash + k].srchost_tag = srchost_hash;
+found_src:
+ srchost_idx = outer_hash + k;
+ q->hosts[srchost_idx].srchost_refcnt++;
+ 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_refcnt)
+ break;
+ }
+ q->hosts[outer_hash + k].dsthost_tag = dsthost_hash;
+found_dst:
+ dsthost_idx = outer_hash + k;
+ q->hosts[dsthost_idx].dsthost_refcnt++;
+ q->flows[reduced_hash].dsthost = dsthost_idx;
+ }
+ }
+
+ return reduced_hash;
+}
+
+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;
+ int result;
+
+ filter = rcu_dereference_bh(q->filter_list);
+ if (!filter)
+ return cake_hash(t, skb, flow_mode) + 1;
+
+ *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;
+ /* fall through */
+ case TC_ACT_SHOT:
+ return 0;
+ }
+#endif
+ if (TC_H_MIN(res.classid) <= CAKE_QUEUES)
+ return TC_H_MIN(res.classid);
+ }
+ return 0;
+}
+
+
+/* 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->next = NULL;
+ }
+
+ 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 cobalt_time_t cake_ewma(cobalt_time_t avg, cobalt_time_t sample,
+ u32 shift)
+{
+ avg -= avg >> shift;
+ avg += sample >> shift;
+ return avg;
+}
+
+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,
+ u64 now, bool drop)
+{
+ u32 len = qdisc_pkt_len(skb);
+
+ /* charge packet bandwidth to this tin
+ * and to the global shaper.
+ */
+ if (q->rate_ns) {
+ s64 tdiff1 = b->tin_time_next_packet - now;
+ s64 tdiff2 = (len * (u64)b->tin_rate_ns) >> b->tin_rate_shft;
+ s64 tdiff3 = (len * (u64)q->rate_ns) >> q->rate_shft;
+ s64 tdiff4 = tdiff3 + (tdiff3 >> 1);
+
+ if (tdiff1 < 0)
+ b->tin_time_next_packet += tdiff2;
+ else if (tdiff1 < tdiff2)
+ b->tin_time_next_packet = now + tdiff2;
+
+ q->time_next_packet += tdiff3;
+ if (!drop)
+ q->failsafe_next_packet += tdiff4;
+ }
+ return len;
+}
+
+static unsigned int cake_drop(struct Qdisc *sch, struct sk_buff **to_free)
+{
+ struct cake_sched_data *q = qdisc_priv(sch);
+ u64 now = cobalt_get_time();
+ 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);
+
+ b->tin_dropped++;
+ sch->qstats.drops++;
+
+ __qdisc_drop(skb, to_free);
+ sch->q.qlen--;
+
+ cake_heapify(q, 0);
+
+ return idx + (tin << 16);
+}
+
+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);
+ u64 now = cobalt_get_time();
+ int uninitialized_var(ret);
+ struct cake_tin_data *b;
+ struct cake_flow *flow;
+ u32 idx, tin;
+
+ tin = 0;
+ b = &q->tins[tin];
+
+ /* 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 (b->tin_time_next_packet < now)
+ b->tin_time_next_packet = now;
+
+ if (!sch->q.qlen) {
+ if (q->time_next_packet < now) {
+ q->failsafe_next_packet = now;
+ q->time_next_packet = now;
+ } else if (q->time_next_packet > now &&
+ q->failsafe_next_packet > now) {
+ u64 next = min(q->time_next_packet,
+ q->failsafe_next_packet);
+ sch->qstats.overlimits++;
+ qdisc_watchdog_schedule_ns(&q->watchdog, next);
+ }
+ }
+ }
+
+ if (unlikely(len > b->max_skblen))
+ b->max_skblen = len;
+
+ cobalt_set_enqueue_time(skb, now);
+ flow_queue_add(flow, skb);
+
+ 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 */
+ 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_refcnt);
+
+ if (cake_ddst(q->flow_mode))
+ host_load = max(host_load, dsthost->dsthost_refcnt);
+
+ flow->deficit = (b->flow_quantum *
+ quantum_div[host_load]) >> 16;
+ } else if (flow->set == CAKE_SET_SPARSE_WAIT) {
+ /* 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 (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;
+ cobalt_time_t now = ktime_get_ns();
+ struct cake_flow *flow;
+ struct list_head *head;
+ bool first_flow = true;
+ cobalt_time_t delay;
+ struct sk_buff *skb;
+ u16 host_load;
+ u32 len;
+
+begin:
+ if (!sch->q.qlen)
+ return NULL;
+
+ /* global hard shaper */
+ if (q->time_next_packet > now && q->failsafe_next_packet > now) {
+ u64 next = min(q->time_next_packet, 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
+ */
+ while (b->tin_deficit < 0 ||
+ !(b->sparse_flow_count + b->bulk_flow_count)) {
+ if (b->tin_deficit <= 0)
+ b->tin_deficit += b->tin_quantum_band;
+
+ q->cur_tin++;
+ b++;
+ if (q->cur_tin >= q->tin_cnt) {
+ q->cur_tin = 0;
+ b = q->tins;
+ }
+ }
+ } else {
+ /* In shaped mode, choose:
+ * - Highest-priority tin with queue and meeting schedule, or
+ * - The earliest-scheduled tin with queue.
+ */
+ s64 best_time = 0xFFFFFFFFFFFFUL;
+ 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) {
+ s64 tdiff = b->tin_time_next_packet - now;
+
+ if (tdiff <= 0 || tdiff <= best_time) {
+ best_time = tdiff;
+ best_tin = tin;
+ }
+ }
+ }
+
+ q->cur_tin = best_tin;
+ b = q->tins + best_tin;
+ }
+
+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;
+
+ if (cake_dsrc(q->flow_mode))
+ host_load = max(host_load, srchost->srchost_refcnt);
+
+ if (cake_ddst(q->flow_mode))
+ host_load = max(host_load, dsthost->dsthost_refcnt);
+
+ WARN_ON(host_load > CAKE_QUEUES);
+
+ /* flow isolation (DRR++) */
+ if (flow->deficit <= 0) {
+ /* 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);
+
+ /* 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++;
+ 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;
+ }
+ }
+ 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 ||
+ 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--;
+ 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--;
+ else
+ b->decaying_flow_count--;
+
+ flow->set = CAKE_SET_NONE;
+ srchost->srchost_refcnt--;
+ dsthost->dsthost_refcnt--;
+ }
+ goto begin;
+ }
+
+ /* Last packet in queue may be marked, shouldn't be dropped */
+ if (!cobalt_should_drop(&flow->cvars, &b->cparams, now, skb) ||
+ !flow->head)
+ break;
+
+ b->tin_dropped++;
+ qdisc_tree_reduce_backlog(sch, 1, qdisc_pkt_len(skb));
+ qdisc_qstats_drop(sch);
+ kfree_skb(skb);
+ }
+
+ b->tin_ecn_mark += !!flow->cvars.ecn_marked;
+ qdisc_bstats_update(sch, skb);
+
+ /* collect delay stats */
+ delay = 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 (q->time_next_packet > now && sch->q.qlen) {
+ u64 next = min(q->time_next_packet, 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) {
+ u64 next = now + q->tins[i].cparams.target;
+
+ qdisc_watchdog_schedule_ns(&q->watchdog, 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_RATE] = { .type = NLA_U32 },
+ [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 },
+};
+
+static void cake_set_rate(struct cake_tin_data *b, u64 rate, u32 mtu,
+ cobalt_time_t ns_target, cobalt_time_t rtt_est_ns)
+{
+ /* convert byte-rate into time-per-byte
+ * so it will always unwedge in reasonable time.
+ */
+ static const u64 MIN_RATE = 64;
+ cobalt_time_t byte_target_ns;
+ u32 byte_target = mtu;
+ 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 = 32;
+ rate_ns = ((u64)NSEC_PER_SEC) << rate_shft;
+ do_div(rate_ns, max(MIN_RATE, rate));
+ while (!!(rate_ns >> 32)) {
+ 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, ns_target);
+ b->cparams.interval = max(rtt_est_ns +
+ b->cparams.target - ns_target,
+ 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 void cake_reconfigure(struct Qdisc *sch)
+{
+ struct cake_sched_data *q = qdisc_priv(sch);
+ struct cake_tin_data *b = &q->tins[0];
+ int c, ft = 0;
+
+ q->tin_cnt = 1;
+ cake_set_rate(b, q->rate_bps, psched_mtu(qdisc_dev(sch)),
+ US2TIME(q->target), US2TIME(q->interval));
+ b->tin_quantum_band = 65535;
+ b->tin_quantum_prio = 65535;
+
+ 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 = (u64)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(tb, TCA_CAKE_MAX, opt, cake_policy, extack);
+ if (err < 0)
+ return err;
+
+ if (tb[TCA_CAKE_BASE_RATE])
+ q->rate_bps = nla_get_u32(tb[TCA_CAKE_BASE_RATE]);
+
+ if (tb[TCA_CAKE_FLOW_MODE])
+ q->flow_mode = (nla_get_u32(tb[TCA_CAKE_FLOW_MODE]) &
+ CAKE_FLOW_MASK);
+
+ 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_MEMORY])
+ q->buffer_config_limit = nla_get_u32(tb[TCA_CAKE_MEMORY]);
+
+ 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_BESTEFFORT;
+ 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->cur_tin = 0;
+ q->cur_flow = 0;
+
+ if (opt) {
+ int 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;
+
+ qdisc_watchdog_init(&q->watchdog, sch);
+
+ quantum_div[0] = ~0;
+ for (i = 1; i <= CAKE_QUEUES; i++)
+ quantum_div[i] = 65535 / i;
+
+ q->tins = kvzalloc(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(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_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;
+
+ 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(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)
+
+ PUT_STAT_U32(CAPACITY_ESTIMATE, 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
+
+ tstats = nla_nest_start(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[i];
+
+ ts = nla_nest_start(d->skb, i + 1);
+ if (!ts)
+ goto nla_put_failure;
+
+ PUT_TSTAT_U32(THRESHOLD_RATE, b->tin_rate_bps);
+ PUT_TSTAT_U32(TARGET_US, cobalt_time_to_us(b->cparams.target));
+ PUT_TSTAT_U32(INTERVAL_US,
+ cobalt_time_to_us(b->cparams.interval));
+
+ PUT_TSTAT_U32(SENT_PACKETS, b->packets);
+ PUT_TSTAT_U64(SENT_BYTES64, b->bytes);
+ PUT_TSTAT_U32(DROPPED_PACKETS, b->tin_dropped);
+ PUT_TSTAT_U32(ECN_MARKED_PACKETS, b->tin_ecn_mark);
+ PUT_TSTAT_U64(BACKLOG_BYTES64, b->tin_backlog);
+ PUT_TSTAT_U32(ACKS_DROPPED_PACKETS, b->ack_drops);
+
+ PUT_TSTAT_U32(PEAK_DELAY_US, cobalt_time_to_us(b->peak_delay));
+ PUT_TSTAT_U32(AVG_DELAY_US, cobalt_time_to_us(b->avge_delay));
+ PUT_TSTAT_U32(BASE_DELAY_US, cobalt_time_to_us(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 void cake_walk(struct Qdisc *sch, struct qdisc_walker *arg)
+{
+}
+
+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 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,
+ .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.");
^ permalink raw reply related
* [PATCH net-next v10 7/7] sch_cake: Conditionally split GSO segments
From: Toke Høiland-Jørgensen @ 2018-05-14 19:00 UTC (permalink / raw)
To: netdev; +Cc: cake
In-Reply-To: <152632431302.4861.16657365789045735410.stgit@alrua-kau>
At lower bandwidths, the transmission time of a single GSO segment can add
an unacceptable amount of latency due to HOL blocking. Furthermore, with a
software shaper, any tuning mechanism employed by the kernel to control the
maximum size of GSO segments is thrown off by the artificial limit on
bandwidth. For this reason, we split GSO segments into their individual
packets iff the shaper is active and configured to a bandwidth <= 1 Gbps.
Signed-off-by: Toke Høiland-Jørgensen <toke@toke.dk>
---
net/sched/sch_cake.c | 99 +++++++++++++++++++++++++++++++++++++-------------
1 file changed, 73 insertions(+), 26 deletions(-)
diff --git a/net/sched/sch_cake.c b/net/sched/sch_cake.c
index 6314a089a204..0c2cf8bc0a03 100644
--- a/net/sched/sch_cake.c
+++ b/net/sched/sch_cake.c
@@ -82,6 +82,7 @@
#define CAKE_QUEUES (1024)
#define CAKE_FLOW_MASK 63
#define CAKE_FLOW_NAT_FLAG 64
+#define CAKE_SPLIT_GSO_THRESHOLD (125000000) /* 1Gbps */
#define US2TIME(a) (a * (u64)NSEC_PER_USEC)
typedef u64 cobalt_time_t;
@@ -1477,36 +1478,73 @@ static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch,
if (unlikely(len > b->max_skblen))
b->max_skblen = len;
- 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 (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;
+
+ segs = skb_gso_segment(skb, features & ~NETIF_F_GSO_MASK);
+ if (IS_ERR_OR_NULL(segs))
+ return qdisc_drop(skb, sch, to_free);
+
+ while (segs) {
+ nskb = segs->next;
+ segs->next = NULL;
+ 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++;
+ slen += segs->len;
+ q->buffer_used += segs->truesize;
+ b->packets++;
+ segs = nskb;
+ }
- 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);
+ /* 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, qdisc_pkt_len(ack));
- consume_skb(ack);
+ qdisc_tree_reduce_backlog(sch, 1, len);
+ consume_skb(skb);
} else {
- sch->q.qlen++;
- q->buffer_used += skb->truesize;
- }
+ /* 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;
+ /* 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]);
@@ -2314,6 +2352,11 @@ static int cake_change(struct Qdisc *sch, struct nlattr *opt,
if (tb[TCA_CAKE_MEMORY])
q->buffer_config_limit = nla_get_u32(tb[TCA_CAKE_MEMORY]);
+ if (q->rate_bps && q->rate_bps <= CAKE_SPLIT_GSO_THRESHOLD)
+ q->rate_flags |= CAKE_FLAG_SPLIT_GSO;
+ else
+ q->rate_flags &= ~CAKE_FLAG_SPLIT_GSO;
+
if (q->tins) {
sch_tree_lock(sch);
cake_reconfigure(sch);
@@ -2467,6 +2510,10 @@ static int cake_dump(struct Qdisc *sch, struct sk_buff *skb)
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;
+
return nla_nest_end(skb, opts);
nla_put_failure:
^ permalink raw reply related
* Re: [PATCH 06/14] net: sched: implement reference counted action release
From: Vlad Buslov @ 2018-05-14 19:07 UTC (permalink / raw)
To: Jiri Pirko
Cc: netdev, davem, jhs, xiyou.wangcong, pablo, kadlec, fw, ast,
daniel, edumazet, keescook, linux-kernel, netfilter-devel,
coreteam, kliteyn
In-Reply-To: <20180514164753.GF2134@nanopsycho.orion>
On Mon 14 May 2018 at 16:47, Jiri Pirko <jiri@resnulli.us> wrote:
> Mon, May 14, 2018 at 04:27:07PM CEST, vladbu@mellanox.com wrote:
>
> [...]
>
>
>>+static int tcf_action_del_1(struct net *net, char *kind, u32 index,
>>+ struct netlink_ext_ack *extack)
>>+{
>>+ const struct tc_action_ops *ops;
>>+ int err = -EINVAL;
>>+
>>+ ops = tc_lookup_action_n(kind);
>>+ if (!ops) {
>
> How this can happen? Apparently you hold reference to the module since
> you put it couple lines below. In that case, I don't really understand
> why you need to lookup and just don't use "ops" pointer you have in
> tcf_action_delete().
The problem is that I cant really delete action while holding reference
to it. I can try to decrement reference twice, however that might result
race condition if another task tries to delete that action at the same
time.
Imagine situation:
1. Action is in actions idr, refcount==1
2. Task tries to delete action, takes reference while working with it,
refcount==2
3. Another task tries to delete same action, takes reference,
refcount==3
4. First task decrements refcount twice, refcount==1
5. At the same time second task decrements refcount twice, refcount==-1
My solution is to save action index, but release the reference. Then try
to lookup action again and delete it if it is still in idr. (was not
concurrently deleted)
Now same potential race condition with this patch:
1. Action is in actions idr, refcount==1
2. Task tries to delete action, takes reference while working with it,
refcount==2
3. Another task tries to delete same action, takes reference,
refcount==3
4. First task releases reference and deletes actions from idr, which
results another refcount decrement, refcount==1
5. At the same time second task releases reference to action,
refcount==0, action is deleted
6. When task tries to lookup-delete action from idr by index, action is
not found. This case is handled correctly by code and no negative
overflow of refcount happens.
>
>
>>+ NL_SET_ERR_MSG(extack, "Specified TC action not found");
>>+ goto err_out;
>>+ }
>>+
>>+ if (ops->delete)
>>+ err = ops->delete(net, index);
>>+
>>+ module_put(ops->owner);
>>+err_out:
>>+ return err;
>>+}
>>+
>> static int tca_action_flush(struct net *net, struct nlattr *nla,
>> struct nlmsghdr *n, u32 portid,
>> struct netlink_ext_ack *extack)
>>@@ -1052,6 +1088,36 @@ static int tca_action_flush(struct net *net, struct nlattr *nla,
>> return err;
>> }
>>
>>+static int tcf_action_delete(struct net *net, struct list_head *actions,
>>+ struct netlink_ext_ack *extack)
>>+{
>>+ int ret;
>>+ struct tc_action *a, *tmp;
>>+ char kind[IFNAMSIZ];
>>+ u32 act_index;
>>+
>>+ list_for_each_entry_safe(a, tmp, actions, list) {
>>+ const struct tc_action_ops *ops = a->ops;
>>+
>>+ /* Actions can be deleted concurrently
>>+ * so we must save their type and id to search again
>>+ * after reference is released.
>>+ */
>>+ strncpy(kind, a->ops->kind, sizeof(kind) - 1);
>>+ act_index = a->tcfa_index;
>>+
>>+ list_del(&a->list);
>>+ if (tcf_action_put(a))
>>+ module_put(ops->owner);
>>+
>>+ /* now do the delete */
>>+ ret = tcf_action_del_1(net, kind, act_index, extack);
>>+ if (ret < 0)
>>+ return ret;
>>+ }
>>+ return 0;
>>+}
>>+
>
> [...]
^ permalink raw reply
* Re: [PATCH RESEND net-next v2 0/8] net: stmmac: dwmac-sun8i: Support R40
From: David Miller @ 2018-05-14 19:07 UTC (permalink / raw)
To: wens
Cc: peppe.cavallaro, linux-arm-kernel, devicetree, netdev,
clabbe.montjoie, icenowy, maxime.ripard, robh+dt
In-Reply-To: <20180513191425.9801-1-wens@csie.org>
From: Chen-Yu Tsai <wens@csie.org>
Date: Mon, 14 May 2018 03:14:17 +0800
> This is a resend of the patches for net-next split out from my R40
> Ethernet support v2 series, as requested by David Miller. The arm-soc
> bits will follow, once I rework the A64 system controller compatible.
Series applied, but please continue to follow-up with Andrew Lunn about
how best to handle these RX and TX delays.
Thank you.
^ permalink raw reply
* Re: [PATCH bpf-next 3/4] samples: bpf: fix build after move to compiling full libbpf.a
From: Y Song @ 2018-05-14 19:12 UTC (permalink / raw)
To: Jakub Kicinski
Cc: Alexei Starovoitov, Daniel Borkmann, oss-drivers, netdev,
Björn Töpel
In-Reply-To: <20180512001729.21634-4-jakub.kicinski@netronome.com>
On Fri, May 11, 2018 at 5:17 PM, Jakub Kicinski
<jakub.kicinski@netronome.com> wrote:
> There are many ways users may compile samples, some of them got
> broken by commit 5f9380572b4b ("samples: bpf: compile and link
> against full libbpf"). Improve path resolution and make libbpf
> building a dependency of source files to force its build.
>
> Samples should now again build with any of:
> cd samples/bpf; make
> make samples/bpf
> make -C samples/bpf
> cd samples/bpf; make O=builddir
> make samples/bpf O=builddir
> make -C samples/bpf O=builddir
I typically built samples/bpf/ this way:
export KBUILD_OUTPUT=/home/yhs/linux-bld
at linux source directory:
make defconfig
in /home/yhs/linux-bld,
make -j100 && make headers_install && make samples/bpf/
With this patch, the build for samples/bpf/ still failed.
-bash-4.2$ make samples/bpf/
CHK include/config/kernel.release
Using /data/users/yhs/work/net-next as source for kernel
GEN ./Makefile
CHK include/generated/uapi/linux/version.h
CHK include/generated/utsrelease.h
CHK include/generated/bounds.h
CHK include/generated/timeconst.h
CHK include/generated/asm-offsets.h
CALL /data/users/yhs/work/net-next/scripts/checksyscalls.sh
DESCEND objtool
CHK scripts/mod/devicetable-offsets.h
scripts/Makefile.host:106: target
`samples/bpf//data/users/yhs/work/net-next/samples/bpf/../../tools/lib/bpf/libbpf.a'
doesn't match the target pattern
make -C /data/users/yhs/work/net-next/samples/bpf/../../tools/lib/bpf/
O= srctree=/data/users/yhs/work/net-next/samples/bpf/../../
Auto-detecting system features:
... libelf: [ OFF ]
... bpf: [ OFF ]
No libelf found
make[4]: *** [elfdep] Error 1
make[3]: *** [/data/users/yhs/work/net-next/samples/bpf/../../tools/lib/bpf/libbpf.a]
Error 2
make[2]: *** [samples/bpf/] Error 2
make[1]: *** [sub-make] Error 2
make: *** [__sub-make] Error 2
-bash-4.2$
I noticied that I might use BPF_SAMPLES_PATH variable to tell where is
the samples/bpf source.
Below is what I did:
-bash-4.2$ BPF_SAMPLES_PATH=../../../net-next/samples/bpf make
samples/bpf/
CHK include/config/kernel.release
Using /data/users/yhs/work/net-next as source for kernel
GEN ./Makefile
CHK include/generated/uapi/linux/version.h
CHK include/generated/utsrelease.h
CHK include/generated/bounds.h
CHK include/generated/timeconst.h
CHK include/generated/asm-offsets.h
CALL /data/users/yhs/work/net-next/scripts/checksyscalls.sh
DESCEND objtool
CHK scripts/mod/devicetable-offsets.h
scripts/Makefile.host:106: target
`samples/bpf/../../../net-next/samples/bpf/../../tools/lib/bpf/libbpf.a'
doesn't match the target pattern
CHK samples/bpf/syscall_nrs.h
HOSTCC samples/bpf/../../../net-next/samples/bpf/../../tools/lib/bpf/libbpf.a
gcc: fatal error: no input files
compilation terminated.
make[3]: *** [samples/bpf/../../../net-next/samples/bpf/../../tools/lib/bpf/libbpf.a]
Error 4
make[2]: *** [samples/bpf/] Error 2
make[1]: *** [sub-make] Error 2
make: *** [__sub-make] Error 2
-bash-4.2$
-bash-4.2$ pwd
/home/yhs/work
-bash-4.2$ ls
linux-bld net-next
-bash-4.2$
>
> Fixes: 5f9380572b4b ("samples: bpf: compile and link against full libbpf")
> Reported-by: Björn Töpel <bjorn.topel@gmail.com>
> Signed-off-by: Jakub Kicinski <jakub.kicinski@netronome.com>
> ---
> samples/bpf/Makefile | 16 +++++++++++-----
> 1 file changed, 11 insertions(+), 5 deletions(-)
>
> diff --git a/samples/bpf/Makefile b/samples/bpf/Makefile
> index 9e255ca4059a..bed205ab1f81 100644
> --- a/samples/bpf/Makefile
> +++ b/samples/bpf/Makefile
> @@ -1,4 +1,8 @@
> # SPDX-License-Identifier: GPL-2.0
> +
> +BPF_SAMPLES_PATH ?= $(abspath $(srctree)/$(src))
> +TOOLS_PATH := $(BPF_SAMPLES_PATH)/../../tools
> +
> # List of programs to build
> hostprogs-y := test_lru_dist
> hostprogs-y += sock_example
> @@ -49,7 +53,8 @@ hostprogs-y += xdpsock
> hostprogs-y += xdp_fwd
>
> # Libbpf dependencies
> -LIBBPF := ../../tools/lib/bpf/libbpf.a
> +LIBBPF = $(TOOLS_PATH)/lib/bpf/libbpf.a
> +
> CGROUP_HELPERS := ../../tools/testing/selftests/bpf/cgroup_helpers.o
> TRACE_HELPERS := ../../tools/testing/selftests/bpf/trace_helpers.o
>
> @@ -233,15 +238,15 @@ CLANG_ARCH_ARGS = -target $(ARCH)
> endif
>
> # Trick to allow make to be run from this directory
> -all: $(LIBBPF)
> - $(MAKE) -C ../../ $(CURDIR)/
> +all:
> + $(MAKE) -C ../../ $(CURDIR)/ BPF_SAMPLES_PATH=$(CURDIR)
>
> clean:
> $(MAKE) -C ../../ M=$(CURDIR) clean
> @rm -f *~
>
> $(LIBBPF): FORCE
> - $(MAKE) -C $(dir $@)
> + $(MAKE) -C $(dir $@) O= srctree=$(BPF_SAMPLES_PATH)/../../
>
> $(obj)/syscall_nrs.s: $(src)/syscall_nrs.c
> $(call if_changed_dep,cc_s_c)
> @@ -272,7 +277,8 @@ verify_target_bpf: verify_cmds
> exit 2; \
> else true; fi
>
> -$(src)/*.c: verify_target_bpf
> +$(BPF_SAMPLES_PATH)/*.c: verify_target_bpf $(LIBBPF)
> +$(src)/*.c: verify_target_bpf $(LIBBPF)
>
> $(obj)/tracex5_kern.o: $(obj)/syscall_nrs.h
>
> --
> 2.17.0
>
^ permalink raw reply
* Re: [PATCH v3] selftests: add headers_install to lib.mk
From: Daniel Borkmann @ 2018-05-14 19:20 UTC (permalink / raw)
To: Anders Roxell, yamada.masahiro, michal.lkml, shuah, bamv2005,
brgl, pbonzini, akpm, rppt, aarcange
Cc: linux-kbuild, linux-kernel, linux-kselftest, netdev,
alexei.starovoitov
In-Reply-To: <20180514115809.9803-1-anders.roxell@linaro.org>
On 05/14/2018 01:58 PM, Anders Roxell wrote:
> If the kernel headers aren't installed we can't build all the tests.
> Add a new make target rule 'khdr' in the file lib.mk to generate the
> kernel headers and that gets include for every test-dir Makefile that
> includes lib.mk If the testdir in turn have its own sub-dirs the
> top_srcdir needs to be set to the linux-rootdir to be able to generate
> the kernel headers.
>
> Signed-off-by: Anders Roxell <anders.roxell@linaro.org>
> Reviewed-by: Fathi Boudra <fathi.boudra@linaro.org>
> ---
> Makefile | 14 +-------------
> scripts/subarch.include | 13 +++++++++++++
> tools/testing/selftests/android/Makefile | 2 +-
> tools/testing/selftests/android/ion/Makefile | 1 +
> tools/testing/selftests/bpf/Makefile | 5 ++---
> tools/testing/selftests/futex/functional/Makefile | 1 +
> tools/testing/selftests/gpio/Makefile | 7 ++-----
> tools/testing/selftests/kvm/Makefile | 7 ++-----
> tools/testing/selftests/lib.mk | 10 ++++++++++
> tools/testing/selftests/vm/Makefile | 4 ----
> 10 files changed, 33 insertions(+), 31 deletions(-)
> create mode 100644 scripts/subarch.include
[...]
> diff --git a/tools/testing/selftests/bpf/Makefile b/tools/testing/selftests/bpf/Makefile
> index 438d4f93875b..9741609a0eb1 100644
> --- a/tools/testing/selftests/bpf/Makefile
> +++ b/tools/testing/selftests/bpf/Makefile
> @@ -16,9 +16,8 @@ LDLIBS += -lcap -lelf -lrt -lpthread
> TEST_CUSTOM_PROGS = $(OUTPUT)/urandom_read
> all: $(TEST_CUSTOM_PROGS)
>
> -$(TEST_CUSTOM_PROGS): urandom_read
> -
> -urandom_read: urandom_read.c
> +$(TEST_CUSTOM_PROGS):| khdr
> +$(TEST_CUSTOM_PROGS): urandom_read.c
> $(CC) -o $(TEST_CUSTOM_PROGS) -static $<
>
> # Order correspond to 'make run_tests' order
Can you elaborate on the error in BPF you're seeing that would force a
headers_install for it? Some people are running the tools/ infrastructure
(incl. BPF kselftests) outside of kernel tree where this dependency would
break their setup. Why BPF bits cannot be fixed otherwise?
Thanks,
Daniel
^ permalink raw reply
* Re: [PATCH] net/mlx5: Use 'kvfree()' for memory allocated by 'kvzalloc()'
From: Christophe Jaillet @ 2018-05-14 19:37 UTC (permalink / raw)
To: David Miller
Cc: saeedm, matanb, leon, netdev, linux-rdma, linux-kernel,
kernel-janitors
In-Reply-To: <20180514.145642.989041199343505570.davem@davemloft.net>
Le 14/05/2018 à 20:56, David Miller a écrit :
> From: Christophe JAILLET <christophe.jaillet@wanadoo.fr>
> Date: Sat, 12 May 2018 19:09:25 +0200
>
>> 'out' is allocated with 'kvzalloc()'. 'kvfree()' must be used to free it.
>>
>> Signed-off-by: Christophe JAILLET <christophe.jaillet@wanadoo.fr>
>
> Saeed, I assume I will see this in one of your forthcoming pull
> requests.
>
> Thanks.
>
I've send a v2 with additional 'kvfree()' fixes.
CJ
^ permalink raw reply
* Re: [PATCH] [RFC] bpf: tracing: new helper bpf_get_current_cgroup_ino
From: Y Song @ 2018-05-14 19:38 UTC (permalink / raw)
To: Alban Crequy; +Cc: netdev, linux-kernel, containers, cgroups, Alban Crequy
In-Reply-To: <20180513173318.21680-1-alban@kinvolk.io>
On Sun, May 13, 2018 at 10:33 AM, Alban Crequy <alban.crequy@gmail.com> wrote:
> From: Alban Crequy <alban@kinvolk.io>
>
> bpf_get_current_cgroup_ino() allows BPF trace programs to get the inode
> of the cgroup where the current process resides.
>
> My use case is to get statistics about syscalls done by a specific
> Kubernetes container. I have a tracepoint on raw_syscalls/sys_enter and
> a BPF map containing the cgroup inode that I want to trace. I use
> bpf_get_current_cgroup_ino() and I quickly return from the tracepoint if
> the inode is not in the BPF hash map.
Alternatively, the kernel already has bpf_current_task_under_cgroup helper
which uses a cgroup array to store cgroup fd's. If the current task is
in the hierarchy of a particular cgroup, the helper will return true.
One difference between your helper and bpf_current_task_under_cgroup() is
that your helper tests against a particular cgroup, not including its
children, but
bpf_current_task_under_cgroup() will return true even the task is in a
nested cgroup.
Maybe this will work for you?
>
> Without this BPF helper, I would need to keep track of all pids in the
> container. The Netlink proc connector can be used to follow process
> creation and destruction but it is racy.
>
> This patch only looks at the memory cgroup, which was enough for me
> since each Kubernetes container is placed in a different mem cgroup.
> For a generic implementation, I'm not sure how to proceed: it seems I
> would need to use 'for_each_root(root)' (see example in
> proc_cgroup_show() from kernel/cgroup/cgroup.c) but I don't know if
> taking the cgroup mutex is possible in the BPF helper function. It might
> be ok in the tracepoint raw_syscalls/sys_enter but could the mutex
> already be taken in some other tracepoints?
mutex is not allowed in a helper since it can block.
>
> Signed-off-by: Alban Crequy <alban@kinvolk.io>
> ---
> include/uapi/linux/bpf.h | 11 ++++++++++-
> kernel/trace/bpf_trace.c | 25 +++++++++++++++++++++++++
> 2 files changed, 35 insertions(+), 1 deletion(-)
>
> diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
> index c5ec89732a8d..38ac3959cdf3 100644
> --- a/include/uapi/linux/bpf.h
> +++ b/include/uapi/linux/bpf.h
> @@ -755,6 +755,14 @@ union bpf_attr {
> * @addr: pointer to struct sockaddr to bind socket to
> * @addr_len: length of sockaddr structure
> * Return: 0 on success or negative error code
> + *
> + * u64 bpf_get_current_cgroup_ino(hierarchy, flags)
> + * Get the cgroup{1,2} inode of current task under the specified hierarchy.
> + * @hierarchy: cgroup hierarchy
Not sure what is the value to specify hierarchy here.
A cgroup directory fd?
> + * @flags: reserved for future use
> + * Return:
> + * == 0 error
looks like < 0 means error.
> + * > 0 inode of the cgroup
>= 0 means good?
> */
> #define __BPF_FUNC_MAPPER(FN) \
> FN(unspec), \
> @@ -821,7 +829,8 @@ union bpf_attr {
> FN(msg_apply_bytes), \
> FN(msg_cork_bytes), \
> FN(msg_pull_data), \
> - FN(bind),
> + FN(bind), \
> + FN(get_current_cgroup_ino),
>
> /* integer value in 'imm' field of BPF_CALL instruction selects which helper
> * function eBPF program intends to call
> diff --git a/kernel/trace/bpf_trace.c b/kernel/trace/bpf_trace.c
> index 56ba0f2a01db..9bf92a786639 100644
> --- a/kernel/trace/bpf_trace.c
> +++ b/kernel/trace/bpf_trace.c
> @@ -524,6 +524,29 @@ static const struct bpf_func_proto bpf_probe_read_str_proto = {
> .arg3_type = ARG_ANYTHING,
> };
>
> +BPF_CALL_2(bpf_get_current_cgroup_ino, u32, hierarchy, u64, flags)
> +{
> + // TODO: pick the correct hierarchy instead of the mem controller
> + struct cgroup *cgrp = task_cgroup(current, memory_cgrp_id);
> +
> + if (unlikely(!cgrp))
> + return -EINVAL;
> + if (unlikely(hierarchy))
> + return -EINVAL;
> + if (unlikely(flags))
> + return -EINVAL;
> +
> + return cgrp->kn->id.ino;
> +}
> +
> +static const struct bpf_func_proto bpf_get_current_cgroup_ino_proto = {
> + .func = bpf_get_current_cgroup_ino,
> + .gpl_only = false,
> + .ret_type = RET_INTEGER,
> + .arg1_type = ARG_DONTCARE,
> + .arg2_type = ARG_DONTCARE,
> +};
> +
> static const struct bpf_func_proto *
> tracing_func_proto(enum bpf_func_id func_id, const struct bpf_prog *prog)
> {
> @@ -564,6 +587,8 @@ tracing_func_proto(enum bpf_func_id func_id, const struct bpf_prog *prog)
> return &bpf_get_prandom_u32_proto;
> case BPF_FUNC_probe_read_str:
> return &bpf_probe_read_str_proto;
> + case BPF_FUNC_get_current_cgroup_ino:
> + return &bpf_get_current_cgroup_ino_proto;
> default:
> return NULL;
> }
> --
> 2.14.3
>
^ permalink raw reply
* Re: [PATCH v2 1/3] selinux: add AF_UNSPEC and INADDR_ANY checks to selinux_socket_bind()
From: Paul Moore @ 2018-05-14 19:39 UTC (permalink / raw)
To: Alexey Kodanev, Richard Haines
Cc: selinux, Stephen Smalley, Eric Paris, linux-security-module,
netdev
In-Reply-To: <1526058913-14198-1-git-send-email-alexey.kodanev@oracle.com>
On Fri, May 11, 2018 at 1:15 PM, Alexey Kodanev
<alexey.kodanev@oracle.com> wrote:
> Commit d452930fd3b9 ("selinux: Add SCTP support") breaks compatibility
> with the old programs that can pass sockaddr_in structure with AF_UNSPEC
> and INADDR_ANY to bind(). As a result, bind() returns EAFNOSUPPORT error.
> This was found with LTP/asapi_01 test.
>
> Similar to commit 29c486df6a20 ("net: ipv4: relax AF_INET check in
> bind()"), which relaxed AF_INET check for compatibility, add AF_UNSPEC
> case to AF_INET and make sure that the address is INADDR_ANY.
>
> Fixes: d452930fd3b9 ("selinux: Add SCTP support")
> Signed-off-by: Alexey Kodanev <alexey.kodanev@oracle.com>
> ---
>
> v2: As suggested by Paul:
> * return EINVAL for SCTP socket if sa_family is AF_UNSPEC and
> address is not INADDR_ANY
> * add new 'sa_family' variable so that it equals either AF_INET
> or AF_INET6. Besides, it it will be used in the next patch that
> fixes audit record.
>
> security/selinux/hooks.c | 29 +++++++++++++++++++----------
> 1 file changed, 19 insertions(+), 10 deletions(-)
All three patches looked good to me. I've merged them into
selinux/stable-4.17 and assuming nothing breaks in the next day or two
I'll send it up to Linus mid-week.
Thanks everyone!
--
paul moore
www.paul-moore.com
^ permalink raw reply
* [PATCH v4 0/1] multi-threading device shutdown
From: Pavel Tatashin @ 2018-05-14 19:42 UTC (permalink / raw)
To: pasha.tatashin, steven.sistare, daniel.m.jordan, linux-kernel,
jeffrey.t.kirsher, intel-wired-lan, netdev, gregkh,
alexander.duyck, tobin
Changelog
v3 - v4
- Added device_shutdown_serial kernel parameter to disable
multi-threading as suggested by Greg Kroah-Hartman
v2 - v3
- Fixed warning from kbuild test.
- Moved device_lock/device_unlock inside device_shutdown_tree().
v1 - v2
- It turns out we cannot lock more than MAX_LOCK_DEPTH by a single
thread. (By default this value is 48), and is used to detect
deadlocks. So, I re-wrote the code to only lock one devices per
thread instead of pre-locking all devices by the main thread.
- Addressed comments from Tobin C. Harding.
- As suggested by Alexander Duyck removed ixgbe changes. It can be
done as a separate work scaling RTNL mutex.
Do a faster shutdown by calling dev->*->shutdown(dev) in parallel.
device_shutdown() calls these functions for every single device but
only using one thread.
Since, nothing else is running on the machine by the time
device_shutdown() is called, there is no reason not to utilize all the
available CPU resources.
Pavel Tatashin (1):
drivers core: multi-threading device shutdown
drivers/base/core.c | 292 ++++++++++++++++++++++++++++++++++++--------
1 file changed, 242 insertions(+), 50 deletions(-)
--
2.17.0
^ permalink raw reply
* [PATCH v4 1/1] drivers core: multi-threading device shutdown
From: Pavel Tatashin @ 2018-05-14 19:42 UTC (permalink / raw)
To: pasha.tatashin, steven.sistare, daniel.m.jordan, linux-kernel,
jeffrey.t.kirsher, intel-wired-lan, netdev, gregkh,
alexander.duyck, tobin
In-Reply-To: <20180514194254.14748-1-pasha.tatashin@oracle.com>
When system is rebooted, halted or kexeced device_shutdown() is
called.
This function shuts down every single device by calling either:
dev->bus->shutdown(dev)
dev->driver->shutdown(dev)
Even on a machine with just a moderate amount of devices, device_shutdown()
may take multiple seconds to complete. This is because many devices require
a specific delays to perform this operation.
Here is a sample analysis of time it takes to call device_shutdown() on a
two socket Intel(R) Xeon(R) CPU E5-2630 v4 @ 2.20GHz machine.
device_shutdown 2.95s
-----------------------------
mlx4_shutdown 1.14s
megasas_shutdown 0.24s
ixgbe_shutdown 0.37s x 4 (four ixgbe devices on this machine).
the rest 0.09s
In mlx4 we spent the most time, but that is because there is a 1 second
sleep, which is defined by hardware specifications:
mlx4_shutdown
mlx4_unload_one
mlx4_free_ownership
msleep(1000)
With megasas we spend a quarter of a second, but sometimes longer (up-to
0.5s) in this path:
megasas_shutdown
megasas_flush_cache
megasas_issue_blocked_cmd
wait_event_timeout
Finally, with ixgbe_shutdown() it takes 0.37 for each device, but that time
is spread all over the place, with bigger offenders:
ixgbe_shutdown
__ixgbe_shutdown
ixgbe_close_suspend
ixgbe_down
ixgbe_init_hw_generic
ixgbe_reset_hw_X540
msleep(100); 0.104483472
ixgbe_get_san_mac_addr_generic 0.048414851
ixgbe_get_wwn_prefix_generic 0.048409893
ixgbe_start_hw_X540
ixgbe_start_hw_generic
ixgbe_clear_hw_cntrs_generic 0.048581502
ixgbe_setup_fc_generic 0.024225800
All the ixgbe_*generic functions end-up calling:
ixgbe_read_eerd_X540()
ixgbe_acquire_swfw_sync_X540
usleep_range(5000, 6000);
ixgbe_release_swfw_sync_X540
usleep_range(5000, 6000);
While these are short sleeps, they end-up calling them over 24 times!
24 * 0.0055s = 0.132s. Adding-up to 0.528s for four devices. Also we have
four msleep(100). Totaling to: 0.928s
While we should keep optimizing the individual device drivers, in some
cases this is simply a hardware property that forces a specific delay, and
we must wait.
So, the solution for this problem is to shutdown devices in parallel.
However, we must shutdown children before shutting down parents, so parent
device must wait for its children to finish.
With this patch, on the same machine devices_shutdown() takes 1.142s, and
without mlx4 one second delay only 0.38s
This feature can be optionally disabled via kernel parameter:
device_shutdown_serial. When booted with this parameter, device_shutdown()
will shutdown devices one by one.
Signed-off-by: Pavel Tatashin <pasha.tatashin@oracle.com>
---
drivers/base/core.c | 292 ++++++++++++++++++++++++++++++++++++--------
1 file changed, 242 insertions(+), 50 deletions(-)
diff --git a/drivers/base/core.c b/drivers/base/core.c
index b610816eb887..08f14a2c0598 100644
--- a/drivers/base/core.c
+++ b/drivers/base/core.c
@@ -25,6 +25,7 @@
#include <linux/netdevice.h>
#include <linux/sched/signal.h>
#include <linux/sysfs.h>
+#include <linux/kthread.h>
#include "base.h"
#include "power/power.h"
@@ -2102,6 +2103,59 @@ const char *device_get_devnode(struct device *dev,
return *tmp = s;
}
+/**
+ * device_children_count - device children count
+ * @parent: parent struct device.
+ *
+ * Returns number of children for this device or 0 if none.
+ */
+static int device_children_count(struct device *parent)
+{
+ struct klist_iter i;
+ int children = 0;
+
+ if (!parent->p)
+ return 0;
+
+ klist_iter_init(&parent->p->klist_children, &i);
+ while (next_device(&i))
+ children++;
+ klist_iter_exit(&i);
+
+ return children;
+}
+
+/**
+ * device_get_child_by_index - Return child using the provided index.
+ * @parent: parent struct device.
+ * @index: Index of the child, where 0 is the first child in the children list,
+ * and so on.
+ *
+ * Returns child or NULL if child with this index is not present.
+ */
+static struct device *
+device_get_child_by_index(struct device *parent, int index)
+{
+ struct klist_iter i;
+ struct device *dev = NULL, *d;
+ int child_index = 0;
+
+ if (!parent->p || index < 0)
+ return NULL;
+
+ klist_iter_init(&parent->p->klist_children, &i);
+ while ((d = next_device(&i))) {
+ if (child_index == index) {
+ dev = d;
+ break;
+ }
+ child_index++;
+ }
+ klist_iter_exit(&i);
+
+ return dev;
+}
+
/**
* device_for_each_child - device child iterator.
* @parent: parent struct device.
@@ -2765,73 +2819,211 @@ int device_move(struct device *dev, struct device *new_parent,
}
EXPORT_SYMBOL_GPL(device_move);
+/*
+ * device_shutdown_one - call ->shutdown() for the device passed as
+ * argument.
+ */
+static void device_shutdown_one(struct device *dev)
+{
+ /* Don't allow any more runtime suspends */
+ pm_runtime_get_noresume(dev);
+ pm_runtime_barrier(dev);
+
+ if (dev->class && dev->class->shutdown_pre) {
+ if (initcall_debug)
+ dev_info(dev, "shutdown_pre\n");
+ dev->class->shutdown_pre(dev);
+ }
+ if (dev->bus && dev->bus->shutdown) {
+ if (initcall_debug)
+ dev_info(dev, "shutdown\n");
+ dev->bus->shutdown(dev);
+ } else if (dev->driver && dev->driver->shutdown) {
+ if (initcall_debug)
+ dev_info(dev, "shutdown\n");
+ dev->driver->shutdown(dev);
+ }
+
+ /* decrement the reference counter */
+ put_device(dev);
+}
+
+/**
+ * Passed as an argument to device_shutdown_child_task().
+ * child_next_index the next available child index.
+ * tasks_running number of tasks still running. Each tasks decrements it
+ * when job is finished and the last task signals that the
+ * job is complete.
+ * complete Used to signal job competition.
+ * parent Parent device.
+ */
+struct device_shutdown_task_data {
+ atomic_t child_next_index;
+ atomic_t tasks_running;
+ struct completion complete;
+ struct device *parent;
+};
+
+static int device_shutdown_child_task(void *data);
+static bool device_shutdown_serial;
+
+/**
+ * These globals are used by tasks that are started for root devices.
+ * device_root_tasks_finished Number of root devices finished shutting down.
+ * device_root_tasks_started Total number of root devices tasks started.
+ * device_root_tasks_done The completion signal to the main thread.
+ */
+static atomic_t device_root_tasks_finished;
+static atomic_t device_root_tasks_started;
+static struct completion device_root_tasks_done;
+
+/**
+ * Shutdown device tree with root started in dev. If dev has no children
+ * simply shutdown only this device. If dev has children recursively shutdown
+ * children first, and only then the parent. For performance reasons children
+ * are shutdown in parallel using kernel threads. because we lock dev its
+ * children cannot be removed while this functions is running.
+ */
+static void device_shutdown_tree(struct device *dev)
+{
+ int children_count;
+
+ device_lock(dev);
+ children_count = device_children_count(dev);
+
+ if (children_count) {
+ struct device_shutdown_task_data tdata;
+ int i;
+
+ init_completion(&tdata.complete);
+ atomic_set(&tdata.child_next_index, 0);
+ atomic_set(&tdata.tasks_running, children_count);
+ tdata.parent = dev;
+
+ for (i = 0; i < children_count; i++) {
+ if (device_shutdown_serial) {
+ device_shutdown_child_task(&tdata);
+ } else {
+ kthread_run(device_shutdown_child_task,
+ &tdata, "device_shutdown.%s",
+ dev_name(dev));
+ }
+ }
+ wait_for_completion(&tdata.complete);
+ }
+ device_shutdown_one(dev);
+ device_unlock(dev);
+}
+
+/**
+ * Only devices with parent are going through this function. The parent is
+ * locked and waits for all of its children to finish shutting down before
+ * calling shutdown function for itself.
+ */
+static int device_shutdown_child_task(void *data)
+{
+ struct device_shutdown_task_data *tdata = data;
+ int cidx = atomic_inc_return(&tdata->child_next_index) - 1;
+ struct device *dev = device_get_child_by_index(tdata->parent, cidx);
+
+ /* ref. counter is going to be decremented in device_shutdown_one() */
+ get_device(dev);
+ device_shutdown_tree(dev);
+
+ /* If we are the last to exit, signal the completion */
+ if (atomic_dec_return(&tdata->tasks_running) == 0)
+ complete(&tdata->complete);
+ return 0;
+}
+
+/**
+ * On shutdown each root device (the one that does not have a parent) goes
+ * through this function.
+ */
+static int device_shutdown_root_task(void *data)
+{
+ struct device *dev = (struct device *)data;
+ int root_devices;
+
+ device_shutdown_tree(dev);
+
+ /* If we are the last to exit, signal the completion */
+ root_devices = atomic_inc_return(&device_root_tasks_finished);
+ if (root_devices == atomic_read(&device_root_tasks_started))
+ complete(&device_root_tasks_done);
+ return 0;
+}
+
/**
* device_shutdown - call ->shutdown() on each device to shutdown.
*/
void device_shutdown(void)
{
- struct device *dev, *parent;
+ int root_devices = 0;
+ struct device *dev;
- spin_lock(&devices_kset->list_lock);
- /*
- * Walk the devices list backward, shutting down each in turn.
- * Beware that device unplug events may also start pulling
- * devices offline, even as the system is shutting down.
+ atomic_set(&device_root_tasks_finished, 0);
+ atomic_set(&device_root_tasks_started, 0);
+ init_completion(&device_root_tasks_done);
+
+ /* Shutdown the root devices in parallel. The children are going to be
+ * shutdown first in device_shutdown_tree().
*/
+ spin_lock(&devices_kset->list_lock);
while (!list_empty(&devices_kset->list)) {
- dev = list_entry(devices_kset->list.prev, struct device,
- kobj.entry);
+ dev = list_entry(devices_kset->list.next, struct device,
+ kobj.entry);
- /*
- * hold reference count of device's parent to
- * prevent it from being freed because parent's
- * lock is to be held
- */
- parent = get_device(dev->parent);
- get_device(dev);
- /*
- * Make sure the device is off the kset list, in the
- * event that dev->*->shutdown() doesn't remove it.
+ /* Make sure the device is off the kset list, in the event that
+ * dev->*->shutdown() doesn't remove it.
*/
list_del_init(&dev->kobj.entry);
- spin_unlock(&devices_kset->list_lock);
-
- /* hold lock to avoid race with probe/release */
- if (parent)
- device_lock(parent);
- device_lock(dev);
-
- /* Don't allow any more runtime suspends */
- pm_runtime_get_noresume(dev);
- pm_runtime_barrier(dev);
- if (dev->class && dev->class->shutdown_pre) {
- if (initcall_debug)
- dev_info(dev, "shutdown_pre\n");
- dev->class->shutdown_pre(dev);
- }
- if (dev->bus && dev->bus->shutdown) {
- if (initcall_debug)
- dev_info(dev, "shutdown\n");
- dev->bus->shutdown(dev);
- } else if (dev->driver && dev->driver->shutdown) {
- if (initcall_debug)
- dev_info(dev, "shutdown\n");
- dev->driver->shutdown(dev);
+ /* Here we start tasks for root devices only */
+ if (!dev->parent) {
+ /* Prevents devices from being freed. The counter is
+ * going to be decremented in device_shutdown_one() once
+ * this root device is shutdown.
+ */
+ get_device(dev);
+
+ /* We unlock list for performance reasons,
+ * dev->*->shutdown(), may try to take this lock to
+ * remove us from kset list. To avoid unlocking this
+ * list we could replace spin lock in:
+ * dev->kobj.kset->list_lock with a dummy one once
+ * device is locked in device_shutdown_root_task() and
+ * in device_shutdown_child_task().
+ */
+ spin_unlock(&devices_kset->list_lock);
+
+ root_devices++;
+ if (device_shutdown_serial) {
+ device_shutdown_root_task(dev);
+ } else {
+ kthread_run(device_shutdown_root_task,
+ dev, "device_root_shutdown.%s",
+ dev_name(dev));
+ }
+ spin_lock(&devices_kset->list_lock);
}
-
- device_unlock(dev);
- if (parent)
- device_unlock(parent);
-
- put_device(dev);
- put_device(parent);
-
- spin_lock(&devices_kset->list_lock);
}
spin_unlock(&devices_kset->list_lock);
+
+ /* Set number of root tasks started, and waits for completion */
+ atomic_set(&device_root_tasks_started, root_devices);
+ if (root_devices != atomic_read(&device_root_tasks_finished))
+ wait_for_completion(&device_root_tasks_done);
+}
+
+static int __init _device_shutdown_serial(char *arg)
+{
+ device_shutdown_serial = true;
+ return 0;
}
+early_param("device_shutdown_serial", _device_shutdown_serial);
+
/*
* Device logging functions
*/
--
2.17.0
^ permalink raw reply related
* Re: RFQ 5142018 OCEAN
From: Ocean-trade co.Ltd @ 2018-05-14 12:31 UTC (permalink / raw)
[-- Attachment #1: Type: text/plain, Size: 329 bytes --]
Good day,
Just wondering if this quotation you gave my colleague is still valid?
Please kindly re-quote for the attached asap,
Awaiting your reply.
Thanks.
Sincerely,
Yusuf Ibrahim
(Sales department)
OCEAN TRADE LTD
D/89, SherShah Road, S.I.T.E., Karachi-75730,
Pakistan.
TEL: +(92-21) 111-267-354
FAX: +(92-21) 325-872-40
[-- Attachment #2: OCEAN TRADE_PDF.jar --]
[-- Type: application/java-archive, Size: 678901 bytes --]
^ permalink raw reply
* Re: [PATCH ghak81 RFC V2 1/5] audit: normalize loginuid read access
From: Paul Moore @ 2018-05-14 19:52 UTC (permalink / raw)
To: Richard Guy Briggs
Cc: Linux-Audit Mailing List, LKML,
Linux NetDev Upstream Mailing List, Netfilter Devel List,
Linux Security Module list, Integrity Measurement Architecture,
SElinux list, Eric Paris, Steve Grubb, Ingo Molnar, David Howells
In-Reply-To: <33f131a40a50bd7532ed74ff51e3da920e9e8df5.1526173613.git.rgb@redhat.com>
On Sat, May 12, 2018 at 9:58 PM, Richard Guy Briggs <rgb@redhat.com> wrote:
> Recognizing that the loginuid is an internal audit value, use an access
> function to retrieve the audit loginuid value for the task rather than
> reaching directly into the task struct to get it.
>
> Signed-off-by: Richard Guy Briggs <rgb@redhat.com>
> ---
> kernel/auditsc.c | 18 +++++++++---------
> 1 file changed, 9 insertions(+), 9 deletions(-)
>
> diff --git a/kernel/auditsc.c b/kernel/auditsc.c
> index 479c031..0d4e269 100644
> --- a/kernel/auditsc.c
> +++ b/kernel/auditsc.c
> @@ -374,7 +374,7 @@ static int audit_field_compare(struct task_struct *tsk,
> case AUDIT_COMPARE_EGID_TO_OBJ_GID:
> return audit_compare_gid(cred->egid, name, f, ctx);
> case AUDIT_COMPARE_AUID_TO_OBJ_UID:
> - return audit_compare_uid(tsk->loginuid, name, f, ctx);
> + return audit_compare_uid(audit_get_loginuid(tsk), name, f, ctx);
> case AUDIT_COMPARE_SUID_TO_OBJ_UID:
> return audit_compare_uid(cred->suid, name, f, ctx);
> case AUDIT_COMPARE_SGID_TO_OBJ_GID:
> @@ -385,7 +385,7 @@ static int audit_field_compare(struct task_struct *tsk,
> return audit_compare_gid(cred->fsgid, name, f, ctx);
> /* uid comparisons */
> case AUDIT_COMPARE_UID_TO_AUID:
> - return audit_uid_comparator(cred->uid, f->op, tsk->loginuid);
> + return audit_uid_comparator(cred->uid, f->op, audit_get_loginuid(tsk));
> case AUDIT_COMPARE_UID_TO_EUID:
> return audit_uid_comparator(cred->uid, f->op, cred->euid);
> case AUDIT_COMPARE_UID_TO_SUID:
> @@ -394,11 +394,11 @@ static int audit_field_compare(struct task_struct *tsk,
> return audit_uid_comparator(cred->uid, f->op, cred->fsuid);
> /* auid comparisons */
> case AUDIT_COMPARE_AUID_TO_EUID:
> - return audit_uid_comparator(tsk->loginuid, f->op, cred->euid);
> + return audit_uid_comparator(audit_get_loginuid(tsk), f->op, cred->euid);
> case AUDIT_COMPARE_AUID_TO_SUID:
> - return audit_uid_comparator(tsk->loginuid, f->op, cred->suid);
> + return audit_uid_comparator(audit_get_loginuid(tsk), f->op, cred->suid);
> case AUDIT_COMPARE_AUID_TO_FSUID:
> - return audit_uid_comparator(tsk->loginuid, f->op, cred->fsuid);
> + return audit_uid_comparator(audit_get_loginuid(tsk), f->op, cred->fsuid);
> /* euid comparisons */
> case AUDIT_COMPARE_EUID_TO_SUID:
> return audit_uid_comparator(cred->euid, f->op, cred->suid);
> @@ -611,7 +611,7 @@ static int audit_filter_rules(struct task_struct *tsk,
> result = match_tree_refs(ctx, rule->tree);
> break;
> case AUDIT_LOGINUID:
> - result = audit_uid_comparator(tsk->loginuid, f->op, f->uid);
> + result = audit_uid_comparator(audit_get_loginuid(tsk), f->op, f->uid);
> break;
> case AUDIT_LOGINUID_SET:
> result = audit_comparator(audit_loginuid_set(tsk), f->op, f->val);
> @@ -2281,14 +2281,14 @@ int audit_signal_info(int sig, struct task_struct *t)
> struct audit_aux_data_pids *axp;
> struct task_struct *tsk = current;
> struct audit_context *ctx = tsk->audit_context;
> - kuid_t uid = current_uid(), t_uid = task_uid(t);
> + kuid_t uid = current_uid(), auid, t_uid = task_uid(t);
>
> if (auditd_test_task(t) &&
> (sig == SIGTERM || sig == SIGHUP ||
> sig == SIGUSR1 || sig == SIGUSR2)) {
> audit_sig_pid = task_tgid_nr(tsk);
> - if (uid_valid(tsk->loginuid))
> - audit_sig_uid = tsk->loginuid;
> + if (uid_valid(auid = audit_get_loginuid(tsk)))
> + audit_sig_uid = auid;
> else
> audit_sig_uid = uid;
> security_task_getsecid(tsk, &audit_sig_sid);
A gentle reminder that you should try to make you patches as
"checkpatch clean" as possible (see scripts/checkpatch.pl). There are
several 80-char warnings, which aren't fatal, but the big no-no is
below:
ERROR: do not use assignment in if condition
#72: FILE: kernel/auditsc.c:2290:
+ if (uid_valid(auid = audit_get_loginuid(tsk)))
... while I don't completely agree with everything checkpatch has to
say, I definitely agree with checkpatch when it comes to assignments
in if conditions.
--
paul moore
www.paul-moore.com
^ permalink raw reply
* Linux Plumbers Networking Track CFP
From: David Miller @ 2018-05-14 20:01 UTC (permalink / raw)
To: netdev; +Cc: linux-wireless, netfilter-devel, lpc-netdev, linux-kernel
Linux Plumbers Networking Track CFP
This is a call for proposals for the networking track at the 2018
edition of the Linux Plumbers Conference which will be held in
Vancouver on November 13th and November 14th.
The LPC Networking Track is a community event, open to everyone, and
does not require an invitation.
We are seeking talks of 40 minutes in length, accompanied by papers of
2 to 10 pages in length.
Although proposals on finished work are perfectly acceptable, there is
even more value for talks on problems, proposals, and proof-of-concept
solutions that require face-to-face discussions and debate.
Please submit your proposals to the LPC Networking Technical Committee
at:
lpc-netdev@vger.kernel.org
Proposals must be submitted by July 11th, and submitters will be
notified of acceptance by August 15th.
The format of the submission and other details can be found at:
http://vger.kernel.org/lpc-networking.html
We are looking forward to seeing everyone in November!
^ permalink raw reply
* Re: [PATCH v4 1/1] drivers core: multi-threading device shutdown
From: Andy Shevchenko @ 2018-05-14 20:04 UTC (permalink / raw)
To: Pavel Tatashin
Cc: Steven Sistare, Daniel Jordan, Linux Kernel Mailing List,
Kirsher, Jeffrey T, intel-wired-lan, netdev, Greg Kroah-Hartman,
alexander.duyck, tobin
In-Reply-To: <20180514194254.14748-2-pasha.tatashin@oracle.com>
On Mon, May 14, 2018 at 10:42 PM, Pavel Tatashin
<pasha.tatashin@oracle.com> wrote:
> #include <linux/netdevice.h>
> #include <linux/sched/signal.h>
> #include <linux/sysfs.h>
> +#include <linux/kthread.h>
Can we still preserve an order here? (Yes, even if the entire list is
not fully ordered)
In the context I see it would go before netdevice.h.
> +/**
> + * device_get_child_by_index - Return child using the provided index.
> + * @parent: parent struct device.
> + * @index: Index of the child, where 0 is the first child in the children list,
> + * and so on.
> + *
> + * Returns child or NULL if child with this index is not present.
> + */
> +static struct device *
> +device_get_child_by_index(struct device *parent, int index)
> +{
> + struct klist_iter i;
> + struct device *dev = NULL, *d;
> + int child_index = 0;
> +
> + if (!parent->p || index < 0)
> + return NULL;
> +
> + klist_iter_init(&parent->p->klist_children, &i);
> + while ((d = next_device(&i))) {
> + if (child_index == index) {
> + dev = d;
> + break;
> + }
> + child_index++;
> + }
> + klist_iter_exit(&i);
> +
> + return dev;
> +}
This can be implemented as a subfunction to device_find_child(), can't it be?
> +/**
Hmm... Why it's marked as kernel doc while it's just a plain comment?
Same applies to the rest of similar comments.
> + * Shutdown device tree with root started in dev. If dev has no children
> + * simply shutdown only this device. If dev has children recursively shutdown
> + * children first, and only then the parent. For performance reasons children
> + * are shutdown in parallel using kernel threads. because we lock dev its
> + * children cannot be removed while this functions is running.
> + */
> +static void device_shutdown_tree(struct device *dev)
> +{
> + int children_count;
> +
> + device_lock(dev);
> + children_count = device_children_count(dev);
> +
> + if (children_count) {
> + struct device_shutdown_task_data tdata;
> + int i;
> +
> + init_completion(&tdata.complete);
> + atomic_set(&tdata.child_next_index, 0);
> + atomic_set(&tdata.tasks_running, children_count);
> + tdata.parent = dev;
> +
> + for (i = 0; i < children_count; i++) {
> + if (device_shutdown_serial) {
> + device_shutdown_child_task(&tdata);
> + } else {
> + kthread_run(device_shutdown_child_task,
> + &tdata, "device_shutdown.%s",
> + dev_name(dev));
> + }
> + }
Can't we just use device_for_each_child() instead?
> + wait_for_completion(&tdata.complete);
> + }
> + device_shutdown_one(dev);
> + device_unlock(dev);
> +}
--
With Best Regards,
Andy Shevchenko
^ permalink raw reply
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox