[Cake] [PATCH net-next v6 0/4] net/sched: cap the accounted backlog before it can wrap

[Cake] [PATCH net-next v6 0/4] net/sched: cap the accounted backlog before it can wrap

[Jamal Hadi Salim]

This series bounds the accounted backlog of the AQM qdiscs so that it
cannot wrap mod 2^32.

v1 widened the counters to u64 and was rejected; from v2 on the fix drops
at enqueue instead. The v5 posting was a single patch; at the reviewer's
request it is split here into four:

  1/4  classifier refactor: cake_tcf_classify() and fq_codel_classify()
       return their result to the caller.
  2/4  cake: use a dedicated split-GSO list iterator.
  3/4  the fix: drop at enqueue once the stored backlog is within one
       maximum-size packet of the wrap point, and clamp the stabless GSO
       producer in qdisc_pkt_len_segs_init(). Covers fq_codel, cake,
       codel, pie, fq_pie, dualpi2, RED, pfifo, plug and gred.
  4/4  cake: split cake_hash() into side-effect-free key extraction (on
       the unsegmented skb) and set-associative resolution (after
       admission), and move the split-GSO path ahead of the resolution.

The commit logs and the in-code comments are rewritten for readability.

The guard half is a net fix, but the CAKE hash split is new-code net-next
material, so the series targets net-next with no Fixes: (the aggregate
wrap predates every touched qdisc).

Changes in v6:
  - Rewrite as a four-patch series per Toke Høiland-Jørgensen's review of
    v5: split the classifier refactor, the split-GSO iterator, the overflow
    guard and the cake hash split into separate patches, and drop the
    verbose commit prose and the in-code comments that read as
    machine-written.
  - Considered the Sashiko gemini v5 TC_ACT_CONSUMED report; not folded.
    No in-tree producer can deliver TC_ACT_CONSUMED to a qdisc classify
    switch, so the fall-through it describes is unreachable: act_ct returns
    it only when bound to a clsact or ingress qdisc (11cb63b0d1a0), and
    act_mirred returns it only for a redirect that does not clone, which
    requires an ingress skb. cls_bpf and act_bpf map an unrecognized opcode
    such as CONSUMED to TC_ACT_UNSPEC.

v5 Considered Comments from Sashiko nipa and Simon:
  - cake: the cake_tcf_classify() block comment had an embedded "/*"
    ("else *flow/*host"), which trips a -Wcomment / W=1 build warning.
    Simon Horman reported it on v4 and noted it likely suppressed the
    Sashiko nipa review; reworded to drop the nested comment.
  - cake: reword the same comment so it no longer says the function
    returns true for "a matched no usable flow" result (Sashiko nipa v3
    Low): cake_tcf_classify() returns true only for a terminal TC action;
    a matched-but-unusable classid leaves the overrides at 0 and the
    packet is hashed as before (fq_codel_classify() differs).
  - commit log: soften the claim that the 1 MiB headroom always bounds a
    single packet (Sashiko nipa v3 High).

v4  fold the Sashiko nipa v3 review:
  - cake: compute the flow/host hash keys from the packet as received
    (before skb_gso_segment(), which can rewrite an encapsulated GSO
    packet's headers to the inner ones), but defer the set-associative
    resolution that writes q->tags[], the flow host indices, the way
    counters and the host bulk-flow counts until after the split-GSO
    segment-sum admission check, so a packet rejected by that check
    commits no flow state.
  - cake: in the split-GSO rejection, handle a fraglist GSO (whose
    skb_segment_list() returns the original skb as the list head with an
    extra reference, segs == skb) by dropping the caller's reference and
    queueing the list once, instead of calling __qdisc_drop_all() and
    qdisc_drop_reason() on the same skb, which self-linked *to_free.

v3  fold the v2 review (Eric Dumazet) and Sashiko gemini v2:
  - Test the stored backlog via qdisc_backlog_at_max() instead of
    (u64)backlog + qdisc_pkt_len() > QDISC_MAX_BACKLOG: no double-count
    of the reserved 1 MiB headroom, no per-enqueue 64-bit add.
  - cake: run the external classifier first, honor its terminal TC
    actions, then the ceiling check, then the hash and the shaper state;
    the SPLIT_GSO segment sum is checked before any flow/host state is
    committed and the list is deferred to to_free rather than freed
    under the qdisc lock.
  - fq_codel: run the external classifier (terminal actions honored)
    first, then the ceiling check before fq_codel_hash(); document the
    fq_codel_drop() NULL flow->head consequence.
  - pfifo: same ceiling guard, since RED reads a (graftable) child's
    backlog and SFB's default child is pfifo.

v2 approach rewrite per list discussion of v1:
  v1 approached the wrap by widening the per-flow backlog counters to
  u64. Eric Dumazet rejected the framing ("Storing 4GB in a qdisc is
  absolutely insane") and asked for a drop at enqueue once the backlog
  approaches the wrap point. Sebastian Moeller noted tc-stab is the
  generic overhead-accounting mechanism, so the fix must not penalize
  normal stab use.
  v2 replaces the u64 widening with an enqueue-side pre-check against
  QDISC_MAX_BACKLOG and drops with QDISC_DROP_OVERLIMIT. No counter is
  widened, so the 32-bit sch->qstats.backlog the AQM reads can no longer
  wrap. Same-pattern siblings fixed in one patch: fq_codel, cake, codel,
  pie, fq_pie, dualpi2, RED.

Jamal Hadi Salim (4):
  net/sched: cake, fq_codel: return the classifier result to the caller
  net/sched: cake: use a dedicated split-GSO list iterator
  net/sched: cap the accounted backlog before it can wrap
  net/sched: cake: hash before segmenting and reject an overlong split

 include/net/pkt_sched.h   |   1 -
 include/net/sch_generic.h |  15 ++++
 net/core/dev.c            |  15 +++-
 net/sched/sch_cake.c      | 183 +++++++++++++++++++++++++++-----------
 net/sched/sch_codel.c     |  16 ++--
 net/sched/sch_dualpi2.c   |   1 +
 net/sched/sch_fifo.c      |   6 ++
 net/sched/sch_fq_codel.c  |  55 +++++++++---
 net/sched/sch_fq_pie.c    |   3 +-
 net/sched/sch_gred.c      |  10 +++
 net/sched/sch_pie.c       |   3 +-
 net/sched/sch_plug.c      |   9 +-
 net/sched/sch_red.c       |  25 ++++--
 13 files changed, 262 insertions(+), 80 deletions(-)

-- 
2.43.0

[Cake] [PATCH net-next v6 1/4] net/sched: cake, fq_codel: return the classifier result to the caller

[Jamal Hadi Salim]

The Fix:
cake and fq_codel run an optional external classifier from their enqueue
path and then compute the flow hash inside the helper. Have the helper
return the filter's overrides (cake) or a 1-based flow index or a request
to hash (fq_codel) instead, so the caller owns the flow selection.

This is preparation for the accounting changes that follow. Packet
classification and flow selection are unchanged.

Reviewed-by: Victor Nogueira <victor@mojatatu.com>
Signed-off-by: Jamal Hadi Salim <jhs@mojatatu.com>

---
v5 -> v6: split out of the single v5 patch; the classifier refactor is unchanged.
---
 net/sched/sch_cake.c     | 35 ++++++++++++++++++++------------
 net/sched/sch_fq_codel.c | 44 ++++++++++++++++++++++++++++------------
 2 files changed, 53 insertions(+), 26 deletions(-)

diff --git a/net/sched/sch_cake.c b/net/sched/sch_cake.c
index dc93267029e7..6432d10c992e 100644
--- a/net/sched/sch_cake.c
+++ b/net/sched/sch_cake.c
@@ -1712,18 +1712,24 @@ static struct cake_tin_data *cake_select_tin(struct Qdisc *sch,
 	return &qd->tins[tin];
 }
 
-static u32 cake_classify(struct Qdisc *sch, struct cake_tin_data **t,
-			 struct sk_buff *skb, int flow_mode, int *qerr)
+/* Run the qdisc's optional external classifier. Returns true when a
+ * terminal TC action consumed the packet, with the reason in *qerr;
+ * otherwise *flow and *host hold the filter's overrides (0 if none).
+ */
+static bool cake_tcf_classify(struct Qdisc *sch, struct sk_buff *skb,
+			      u16 *flow, u16 *host, int *qerr)
 {
 	struct cake_sched_data *q = qdisc_priv(sch);
 	struct tcf_proto *filter;
 	struct tcf_result res;
-	u16 flow = 0, host = 0;
 	int result;
 
+	*flow = 0;
+	*host = 0;
+
 	filter = rcu_dereference_bh(q->filter_list);
 	if (!filter)
-		goto hash;
+		return false;
 
 	*qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
 	result = tcf_classify_qdisc(skb, filter, &res, false);
@@ -1737,17 +1743,15 @@ static u32 cake_classify(struct Qdisc *sch, struct cake_tin_data **t,
 			*qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
 			fallthrough;
 		case TC_ACT_SHOT:
-			return 0;
+			return true;
 		}
 #endif
 		if (TC_H_MIN(res.classid) <= CAKE_QUEUES)
-			flow = TC_H_MIN(res.classid);
+			*flow = TC_H_MIN(res.classid);
 		if (TC_H_MAJ(res.classid) <= (CAKE_QUEUES << 16))
-			host = TC_H_MAJ(res.classid) >> 16;
+			*host = TC_H_MAJ(res.classid) >> 16;
 	}
-hash:
-	*t = cake_select_tin(sch, skb);
-	return cake_hash(*t, skb, flow_mode, flow, host) + 1;
+	return false;
 }
 
 static void cake_reconfigure(struct Qdisc *sch);
@@ -1758,20 +1762,25 @@ static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 	u32 idx, tin, prev_qlen, prev_backlog, drop_id;
 	struct cake_sched_data *q = qdisc_priv(sch);
 	int len = qdisc_pkt_len(skb), ret;
+	u16 flow_override, host_override;
 	struct sk_buff *ack = NULL;
 	ktime_t now = ktime_get();
 	struct cake_tin_data *b;
 	struct cake_flow *flow;
 	bool same_flow = false;
 
-	/* choose flow to insert into */
-	idx = cake_classify(sch, &b, skb, q->config->flow_mode, &ret);
-	if (idx == 0) {
+	/* Classify first: a terminal TC action consumes the packet. */
+	if (cake_tcf_classify(sch, skb, &flow_override, &host_override, &ret)) {
 		if (ret & __NET_XMIT_BYPASS)
 			qdisc_qstats_drop(sch);
 		__qdisc_drop(skb, to_free);
 		return ret;
 	}
+
+	/* choose flow to insert into */
+	b = cake_select_tin(sch, skb);
+	idx = cake_hash(b, skb, q->config->flow_mode, flow_override,
+			host_override) + 1;
 	tin = (u32)(b - q->tins);
 	idx--;
 	flow = &b->flows[idx];
diff --git a/net/sched/sch_fq_codel.c b/net/sched/sch_fq_codel.c
index e6c87a32950f..4cf3d379b8e9 100644
--- a/net/sched/sch_fq_codel.c
+++ b/net/sched/sch_fq_codel.c
@@ -73,22 +73,35 @@ static unsigned int fq_codel_hash(const struct fq_codel_sched_data *q,
 	return reciprocal_scale(skb_get_hash(skb), q->flows_cnt);
 }
 
-static unsigned int fq_codel_classify(struct sk_buff *skb, struct Qdisc *sch,
-				      int *qerr)
+/* Run the qdisc's optional external classifier. Returns true when the
+ * caller must drop the packet (a terminal TC action consumed it, or the
+ * result carried no class ID); the reason is then in *qerr. Otherwise *idx
+ * is the 1-based flow index, or *do_hash asks the caller to use
+ * fq_codel_hash().
+ */
+static bool fq_codel_classify(struct sk_buff *skb, struct Qdisc *sch,
+			      unsigned int *idx, bool *do_hash, int *qerr)
 {
 	struct fq_codel_sched_data *q = qdisc_priv(sch);
 	struct tcf_proto *filter;
 	struct tcf_result res;
 	int result;
 
+	*idx = 0;
+	*do_hash = false;
+
 	if (TC_H_MAJ(skb->priority) == sch->handle &&
 	    TC_H_MIN(skb->priority) > 0 &&
-	    TC_H_MIN(skb->priority) <= q->flows_cnt)
-		return TC_H_MIN(skb->priority);
+	    TC_H_MIN(skb->priority) <= q->flows_cnt) {
+		*idx = TC_H_MIN(skb->priority);
+		return false;
+	}
 
 	filter = rcu_dereference_bh(q->filter_list);
-	if (!filter)
-		return fq_codel_hash(q, skb) + 1;
+	if (!filter) {
+		*do_hash = true;
+		return false;
+	}
 
 	*qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
 	result = tcf_classify_qdisc(skb, filter, &res, false);
@@ -101,13 +114,16 @@ static unsigned int fq_codel_classify(struct sk_buff *skb, struct Qdisc *sch,
 			*qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
 			fallthrough;
 		case TC_ACT_SHOT:
-			return 0;
+			return true;
 		}
 #endif
-		if (TC_H_MIN(res.classid) <= q->flows_cnt)
-			return TC_H_MIN(res.classid);
+		if (TC_H_MIN(res.classid) > 0 &&
+		    TC_H_MIN(res.classid) <= q->flows_cnt) {
+			*idx = TC_H_MIN(res.classid);
+			return false;
+		}
 	}
-	return 0;
+	return true;
 }
 
 /* helper functions : might be changed when/if skb use a standard list_head */
@@ -188,17 +204,19 @@ static int fq_codel_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 	struct fq_codel_sched_data *q = qdisc_priv(sch);
 	unsigned int idx, prev_backlog, prev_qlen;
 	struct fq_codel_flow *flow;
-	int ret;
+	bool do_hash = false;
 	unsigned int pkt_len;
 	bool memory_limited;
+	int ret;
 
-	idx = fq_codel_classify(skb, sch, &ret);
-	if (idx == 0) {
+	if (fq_codel_classify(skb, sch, &idx, &do_hash, &ret)) {
 		if (ret & __NET_XMIT_BYPASS)
 			qdisc_qstats_drop(sch);
 		__qdisc_drop(skb, to_free);
 		return ret;
 	}
+	if (do_hash)
+		idx = fq_codel_hash(q, skb) + 1;
 	idx--;
 
 	codel_set_enqueue_time(skb);
-- 
2.43.0

[Cake] [PATCH net-next v6 2/4] net/sched: cake: use a dedicated split-GSO list iterator

[Jamal Hadi Salim]

skb_list_walk_safe(segs, segs, nskb) reuses the list head as the walk
cursor, so segs no longer names the segment list once the walk finishes.
Use a separate seg cursor to keep the head and the walker distinct. No
behaviour change.

Reviewed-by: Victor Nogueira <victor@mojatatu.com>
Signed-off-by: Jamal Hadi Salim <jhs@mojatatu.com>

---
v5 -> v6: split out of the single v5 patch; no code change.
---
 net/sched/sch_cake.c | 22 +++++++++++-----------
 1 file changed, 11 insertions(+), 11 deletions(-)

diff --git a/net/sched/sch_cake.c b/net/sched/sch_cake.c
index 6432d10c992e..0d13c4b0bfe3 100644
--- a/net/sched/sch_cake.c
+++ b/net/sched/sch_cake.c
@@ -1810,7 +1810,7 @@ static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 		WRITE_ONCE(b->max_skblen, len);
 
 	if (qdisc_pkt_segs(skb) > 1 && q->config->rate_flags & CAKE_FLAG_SPLIT_GSO) {
-		struct sk_buff *segs, *nskb;
+		struct sk_buff *segs, *nskb, *seg;
 		netdev_features_t features = netif_skb_features(skb);
 		unsigned int slen = 0, numsegs = 0;
 
@@ -1818,19 +1818,19 @@ static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 		if (IS_ERR_OR_NULL(segs))
 			return qdisc_drop(skb, sch, to_free);
 
-		skb_list_walk_safe(segs, segs, nskb) {
-			skb_mark_not_on_list(segs);
-			qdisc_skb_cb(segs)->pkt_len = segs->len;
-			qdisc_skb_cb(segs)->pkt_segs = 1;
-			cobalt_set_enqueue_time(segs, now);
-			get_cobalt_cb(segs)->adjusted_len = cake_overhead(q,
-									  segs);
-			flow_queue_add(flow, segs);
+		skb_list_walk_safe(segs, seg, nskb) {
+			skb_mark_not_on_list(seg);
+			qdisc_skb_cb(seg)->pkt_len = seg->len;
+			qdisc_skb_cb(seg)->pkt_segs = 1;
+			cobalt_set_enqueue_time(seg, now);
+			get_cobalt_cb(seg)->adjusted_len = cake_overhead(q,
+									 seg);
+			flow_queue_add(flow, seg);
 
 			qdisc_qlen_inc(sch);
 			numsegs++;
-			slen += segs->len;
-			q->buffer_used += segs->truesize;
+			q->buffer_used += seg->truesize;
+			slen += seg->len;
 			WRITE_ONCE(b->packets, b->packets + 1);
 		}
 
-- 
2.43.0

[Cake] [PATCH net-next v6 3/4] net/sched: cap the accounted backlog before it can wrap

[Jamal Hadi Salim]

This is a followup of commit 709f34f7c28d ("net/sched: fq: add overflow
bounds to quantum and initial quantum") as reported by Sashiko.

The issue: fq_codel, cake, codel, pie, fq_pie, dualpi2, RED, pfifo, plug
and (non-WRED) gred account every enqueued packet's stab-adjusted length
into the 32-bit sch->qstats.backlog, which the AQM logic reads back (for
non-WRED gred it is the reported stats and the dequeue-side subtractions
that go wrong instead). A crafted tc size table inflates qdisc_pkt_len()
up to QDISC_PKT_LEN_MAX (1 MiB), and a dodgy GSO skb can account even more
through qdisc_pkt_len_segs_init(), so a few thousand packets wrap the
counter mod 2^32. The AQM then reads a small backlog and makes the wrong
drop decision, and the dequeue-side subtractions leave it corrupt. In
fq_codel a wrapped per-flow backlog can also make fq_codel_drop()'s scan
pick an empty flow, dereferencing a NULL flow->head.

The Fix: drop at enqueue once the stored backlog is within
QDISC_MAX_BACKLOG (U32_MAX - QDISC_PKT_LEN_MAX) of the wrap point, the
largest backlog one more stab-clamped packet cannot wrap. Test the
stored backlog itself via qdisc_backlog_at_max() rather than adding the
incoming length, so there is no per-enqueue 64-bit add and the reserved
1 MiB headroom is not counted twice. Clamp the accounted length in
qdisc_pkt_len_segs_init() at initialization, before the non-GSO and
missing-transport-header returns, and again after the GSO header
estimate, so a dodgy or oversized skb cannot exceed the headroom either.
Cover sch_plug and non-WRED sch_gred too: plug admits on skb->len while
qdisc_enqueue_tail() adds qdisc_pkt_len(), and gred bounds each virtual
queue but adds every VQ into the one aggregate. pfifo is included because
RED reads a grafted child's backlog into red_calc_qavg(); it can be
reached standalone or as the default child of SFB. In RED, account the
packet to the aggregate before handing it to the child, because a
duplicating netem child re-enqueues its clone at the root while the
stored backlog is still un-updated -- one guard check must not authorize
two additions.

The guard bounds each qdisc's own enqueue path: a child that segments a
GSO skb (tbf, netem) can still grow a parent's aggregate through
qdisc_tree_reduce_backlog()'s unclamped byte delta, which is left to a
separate change.

Conditions to recreate the bug:
  ip tuntap add tun0 mode tun
  ip link set tun0 txqueuelen 32 up
  ip addr add 10.99.0.1/24 dev tun0
  tc qdisc add dev tun0 root handle 1: stab overhead 2000000000 \
      fq_codel flows 1 limit 20000 ecn
  # hold the tun fd open without reading so the backlog persists, then
  # send 6000 packets: the counter wraps and the unfixed kernel reports
  # a wrapped backlog, while the fixed one drops at the ceiling.

Reported-by: Sashiko (nipa) <sashiko-bot@kernel.org>
Closes: https://lore.kernel.org/netdev/20260818101130.16203-1-jhs@mojatatu.com/
Link: https://netdev-ai.bots.linux.dev/sashiko/#/patchset/20260818101130.16203-1-jhs@mojatatu.com
Link: https://lore.kernel.org/netdev/CANn89iLfMJV7ancKH1Gjzzm7ZUG-gKcrczkJjJEWN5sCuWd-ug@mail.gmail.com/
Link: https://lore.kernel.org/netdev/CANn89i+GOFH_8g+vSV0jUj0aBqLYVWuFOrHuDggZu9kPC_m6tQ@mail.gmail.com/
Link: https://lore.kernel.org/netdev/87a4oottcj.fsf@toke.dk/
Link: https://lore.kernel.org/netdev/87pkxks68f.fsf@toke.dk/
Reviewed-by: Victor Nogueira <victor@mojatatu.com>
Signed-off-by: Jamal Hadi Salim <jhs@mojatatu.com>

---
v5 -> v6: resend, rewritten as a series per review feedback.

The v5 posting carried a refactor, the overflow fix and unrelated
changes in a single patch, with a commit log the reviewer found hard to
read. It is split into four patches:

  0001  classifier refactor
  0002  split-GSO list iterator rename
  0003  enqueue ceiling guard plus qdisc_pkt_len_segs_init() producer clamp
  0004  cake hash key/resolve split and split-GSO relocation
---
 include/net/pkt_sched.h   |  1 -
 include/net/sch_generic.h | 15 +++++++++++++++
 net/core/dev.c            | 15 ++++++++++++++-
 net/sched/sch_cake.c      | 10 ++++++++++
 net/sched/sch_codel.c     | 16 +++++++++-------
 net/sched/sch_dualpi2.c   |  1 +
 net/sched/sch_fifo.c      |  6 ++++++
 net/sched/sch_fq_codel.c  | 11 +++++++++++
 net/sched/sch_fq_pie.c    |  3 ++-
 net/sched/sch_gred.c      | 10 ++++++++++
 net/sched/sch_pie.c       |  3 ++-
 net/sched/sch_plug.c      |  9 ++++++++-
 net/sched/sch_red.c       | 25 ++++++++++++++++++++-----
 13 files changed, 108 insertions(+), 17 deletions(-)

diff --git a/include/net/pkt_sched.h b/include/net/pkt_sched.h
index 90d3e7943b19..18a419cd9d94 100644
--- a/include/net/pkt_sched.h
+++ b/include/net/pkt_sched.h
@@ -12,7 +12,6 @@
 
 #define DEFAULT_TX_QUEUE_LEN	1000
 #define STAB_SIZE_LOG_MAX	30
-#define QDISC_PKT_LEN_MAX	(1 << 20)	/* 1 MiB */
 
 struct qdisc_walker {
 	int	stop;
diff --git a/include/net/sch_generic.h b/include/net/sch_generic.h
index 1acaadb3e2cf..43a3e1e9ee89 100644
--- a/include/net/sch_generic.h
+++ b/include/net/sch_generic.h
@@ -915,6 +915,21 @@ static inline unsigned int qdisc_pkt_len(const struct sk_buff *skb)
 	return qdisc_skb_cb(skb)->pkt_len;
 }
 
+#define QDISC_PKT_LEN_MAX	(1 << 20)	/* 1 MiB */
+
+/* Largest accounted backlog one more maximum-size packet cannot wrap
+ * the 32-bit sch->qstats.backlog past.
+ */
+#define QDISC_MAX_BACKLOG	(U32_MAX - QDISC_PKT_LEN_MAX)
+
+/* Backlog close enough to U32_MAX that one more packet could wrap it.
+ * A packet-limited qdisc must drop at enqueue when this holds.
+ */
+static inline bool qdisc_backlog_at_max(const struct Qdisc *sch)
+{
+	return READ_ONCE(sch->qstats.backlog) > QDISC_MAX_BACKLOG;
+}
+
 static inline unsigned int qdisc_pkt_segs(const struct sk_buff *skb)
 {
 	u32 pkt_segs = qdisc_skb_cb(skb)->pkt_segs;
diff --git a/net/core/dev.c b/net/core/dev.c
index a6951ea08961..5165bd531cd9 100644
--- a/net/core/dev.c
+++ b/net/core/dev.c
@@ -4215,7 +4215,12 @@ static enum skb_drop_reason qdisc_pkt_len_segs_init(struct sk_buff *skb)
 	unsigned int hdr_len, tlen;
 	u16 gso_segs;
 
-	qdisc_skb_cb(skb)->pkt_len = skb->len;
+	/* Clamp from the start: the non-GSO and missing-transport-header
+	 * returns below leave pkt_len at this value, and a stabless skb
+	 * larger than QDISC_PKT_LEN_MAX would otherwise bypass the guard.
+	 */
+	qdisc_skb_cb(skb)->pkt_len =
+		min_t(unsigned int, skb->len, QDISC_PKT_LEN_MAX);
 	if (!shinfo->gso_size) {
 		qdisc_skb_cb(skb)->pkt_segs = 1;
 		return SKB_NOT_DROPPED_YET;
@@ -4268,6 +4273,14 @@ static enum skb_drop_reason qdisc_pkt_len_segs_init(struct sk_buff *skb)
 		qdisc_skb_cb(skb)->pkt_segs = gso_segs;
 	}
 	qdisc_skb_cb(skb)->pkt_len += (gso_segs - 1) * hdr_len;
+	/* (gso_segs - 1) * hdr_len can exceed QDISC_PKT_LEN_MAX for a dodgy
+	 * GSO skb, so clamp the accounted length as a size table does in
+	 * __qdisc_calculate_pkt_len(), keeping the backlog within one
+	 * stab-clamped packet of U32_MAX.
+	 */
+	qdisc_skb_cb(skb)->pkt_len = min_t(unsigned int,
+					   qdisc_skb_cb(skb)->pkt_len,
+					   QDISC_PKT_LEN_MAX);
 	return SKB_NOT_DROPPED_YET;
 }
 
diff --git a/net/sched/sch_cake.c b/net/sched/sch_cake.c
index 0d13c4b0bfe3..adfe11737c66 100644
--- a/net/sched/sch_cake.c
+++ b/net/sched/sch_cake.c
@@ -1777,6 +1777,16 @@ static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 		return ret;
 	}
 
+	/* Drop before hash/shaper state so a rejected packet disturbs
+	 * neither; the QDISC_MAX_BACKLOG margin leaves room for one more
+	 * stab-clamped packet.
+	 */
+	if (unlikely(qdisc_backlog_at_max(sch))) {
+		qdisc_qstats_overlimit(sch);
+		return qdisc_drop_reason(skb, sch, to_free,
+					 QDISC_DROP_OVERLIMIT);
+	}
+
 	/* choose flow to insert into */
 	b = cake_select_tin(sch, skb);
 	idx = cake_hash(b, skb, q->config->flow_mode, flow_override,
diff --git a/net/sched/sch_codel.c b/net/sched/sch_codel.c
index a1ba2e355f2d..ff7e72989dfc 100644
--- a/net/sched/sch_codel.c
+++ b/net/sched/sch_codel.c
@@ -116,15 +116,17 @@ static struct sk_buff *codel_peek(struct Qdisc *sch)
 static int codel_qdisc_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 			       struct sk_buff **to_free)
 {
-	struct codel_sched_data *q;
+	struct codel_sched_data *q = qdisc_priv(sch);
 
-	if (likely(qdisc_qlen(sch) < sch->limit)) {
-		codel_set_enqueue_time(skb);
-		return qdisc_enqueue_tail(skb, sch);
+	if (unlikely(qdisc_qlen(sch) >= sch->limit) ||
+	    unlikely(qdisc_backlog_at_max(sch))) {
+		WRITE_ONCE(q->drop_overlimit, q->drop_overlimit + 1);
+		return qdisc_drop_reason(skb, sch, to_free,
+					 QDISC_DROP_OVERLIMIT);
 	}
-	q = qdisc_priv(sch);
-	WRITE_ONCE(q->drop_overlimit, q->drop_overlimit + 1);
-	return qdisc_drop_reason(skb, sch, to_free, QDISC_DROP_OVERLIMIT);
+
+	codel_set_enqueue_time(skb);
+	return qdisc_enqueue_tail(skb, sch);
 }
 
 static const struct nla_policy codel_policy[TCA_CODEL_MAX + 1] = {
diff --git a/net/sched/sch_dualpi2.c b/net/sched/sch_dualpi2.c
index 4947def7c49e..5c746e9b60cd 100644
--- a/net/sched/sch_dualpi2.c
+++ b/net/sched/sch_dualpi2.c
@@ -392,6 +392,7 @@ static int dualpi2_enqueue_skb(struct sk_buff *skb, struct Qdisc *sch,
 	struct dualpi2_skb_cb *cb;
 
 	if (unlikely(qdisc_qlen(sch) >= sch->limit) ||
+	    unlikely(qdisc_backlog_at_max(sch)) ||
 	    unlikely((u64)q->memory_used + skb->truesize > q->memory_limit)) {
 		qdisc_qstats_overlimit(sch);
 		if (skb_in_l_queue(skb))
diff --git a/net/sched/sch_fifo.c b/net/sched/sch_fifo.c
index 1b6388d50967..d5e5cd49377d 100644
--- a/net/sched/sch_fifo.c
+++ b/net/sched/sch_fifo.c
@@ -29,6 +29,9 @@ static int bfifo_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 static int pfifo_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 			 struct sk_buff **to_free)
 {
+	if (unlikely(qdisc_backlog_at_max(sch)))
+		return qdisc_drop(skb, sch, to_free);
+
 	if (likely(sch->q.qlen < READ_ONCE(sch->limit)))
 		return qdisc_enqueue_tail(skb, sch);
 
@@ -43,6 +46,9 @@ static int pfifo_tail_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 	if (unlikely(READ_ONCE(sch->limit) == 0))
 		return qdisc_drop(skb, sch, to_free);
 
+	if (unlikely(qdisc_backlog_at_max(sch)))
+		return qdisc_drop(skb, sch, to_free);
+
 	if (likely(sch->q.qlen < READ_ONCE(sch->limit)))
 		return qdisc_enqueue_tail(skb, sch);
 
diff --git a/net/sched/sch_fq_codel.c b/net/sched/sch_fq_codel.c
index 4cf3d379b8e9..7def7e7dff6c 100644
--- a/net/sched/sch_fq_codel.c
+++ b/net/sched/sch_fq_codel.c
@@ -215,6 +215,17 @@ static int fq_codel_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 		__qdisc_drop(skb, to_free);
 		return ret;
 	}
+
+	/* Drop before hashing so a rejected packet disturbs no flow hash;
+	 * the QDISC_MAX_BACKLOG margin leaves room for one more stab-clamped
+	 * packet.
+	 */
+	if (unlikely(qdisc_backlog_at_max(sch))) {
+		q->drop_overlimit++;
+		return qdisc_drop_reason(skb, sch, to_free,
+					 QDISC_DROP_OVERLIMIT);
+	}
+
 	if (do_hash)
 		idx = fq_codel_hash(q, skb) + 1;
 	idx--;
diff --git a/net/sched/sch_fq_pie.c b/net/sched/sch_fq_pie.c
index 5982847df8f8..394f015cec36 100644
--- a/net/sched/sch_fq_pie.c
+++ b/net/sched/sch_fq_pie.c
@@ -155,7 +155,8 @@ static int fq_pie_qdisc_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 	memory_limited = q->memory_usage > q->memory_limit + skb->truesize;
 
 	/* Checks if the qdisc is full */
-	if (unlikely(qdisc_qlen(sch) >= sch->limit)) {
+	if (unlikely(qdisc_qlen(sch) >= sch->limit) ||
+	    unlikely(qdisc_backlog_at_max(sch))) {
 		q->stats.overlimit++;
 		goto out;
 	} else if (unlikely(memory_limited)) {
diff --git a/net/sched/sch_gred.c b/net/sched/sch_gred.c
index f04f425c6c44..3ef38d5cb5b5 100644
--- a/net/sched/sch_gred.c
+++ b/net/sched/sch_gred.c
@@ -170,6 +170,16 @@ static int gred_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 	unsigned long qavg = 0;
 	u16 dp = tc_index_to_dp(skb);
 
+	/* The per-VQ limits do not bound sch->qstats.backlog: qdisc_enqueue_tail()
+	 * adds every VQ into the one u32 aggregate, so individually legal VQs
+	 * can wrap it. Guard the aggregate before dispatching.
+	 */
+	if (unlikely(qdisc_backlog_at_max(sch))) {
+		qdisc_qstats_overlimit(sch);
+		return qdisc_drop_reason(skb, sch, to_free,
+					 QDISC_DROP_OVERLIMIT);
+	}
+
 	if (dp >= t->DPs || (q = t->tab[dp]) == NULL) {
 		dp = t->def;
 
diff --git a/net/sched/sch_pie.c b/net/sched/sch_pie.c
index 3b7863ffd284..9e38f38ce923 100644
--- a/net/sched/sch_pie.c
+++ b/net/sched/sch_pie.c
@@ -89,7 +89,8 @@ static int pie_qdisc_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 	struct pie_sched_data *q = qdisc_priv(sch);
 	bool enqueue = false;
 
-	if (unlikely(qdisc_qlen(sch) >= sch->limit)) {
+	if (unlikely(qdisc_qlen(sch) >= sch->limit) ||
+	    unlikely(qdisc_backlog_at_max(sch))) {
 		WRITE_ONCE(q->stats.overlimit, q->stats.overlimit + 1);
 		goto out;
 	}
diff --git a/net/sched/sch_plug.c b/net/sched/sch_plug.c
index b60ddfee6a68..bf707f6342b9 100644
--- a/net/sched/sch_plug.c
+++ b/net/sched/sch_plug.c
@@ -89,7 +89,14 @@ static int plug_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 {
 	struct plug_sched_data *q = qdisc_priv(sch);
 
-	if (likely((u64)sch->qstats.backlog + skb->len <= q->limit)) {
+	if (unlikely(qdisc_backlog_at_max(sch))) {
+		qdisc_qstats_overlimit(sch);
+		return qdisc_drop_reason(skb, sch, to_free,
+					 QDISC_DROP_OVERLIMIT);
+	}
+
+	if (likely((u64)sch->qstats.backlog + qdisc_pkt_len(skb) <=
+		   q->limit)) {
 		if (!q->unplug_indefinite)
 			q->pkts_current_epoch++;
 		return qdisc_enqueue_tail(skb, sch);
diff --git a/net/sched/sch_red.c b/net/sched/sch_red.c
index d7598214270b..99126c4b26bc 100644
--- a/net/sched/sch_red.c
+++ b/net/sched/sch_red.c
@@ -76,6 +76,12 @@ static int red_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 	unsigned int len;
 	int ret;
 
+	if (unlikely(qdisc_backlog_at_max(sch))) {
+		qdisc_qstats_overlimit(sch);
+		return qdisc_drop_reason(skb, sch, to_free,
+					 QDISC_DROP_OVERLIMIT);
+	}
+
 	q->vars.qavg = red_calc_qavg(&q->parms,
 				     &q->vars,
 				     child->qstats.backlog);
@@ -136,14 +142,23 @@ static int red_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 	}
 
 	len = qdisc_pkt_len(skb);
+	/* Reserve the accounted length before handing the packet to the
+	 * child. A duplicating child (netem) re-enqueues its clone at the
+	 * root, re-entering this function while the stored backlog is still
+	 * un-updated; without the reservation one guard check would authorize
+	 * two additions. Roll the reservation back if the child rejects.
+	 */
+	qstats_backlog_add(sch, len);
 	ret = qdisc_enqueue(skb, child, to_free);
 	if (likely(ret == NET_XMIT_SUCCESS)) {
-		qstats_backlog_add(sch, len);
 		qdisc_qlen_inc(sch);
-	} else if (net_xmit_drop_count(ret)) {
-		WRITE_ONCE(q->stats.pdrop,
-			   q->stats.pdrop + 1);
-		qdisc_qstats_drop(sch);
+	} else {
+		qstats_backlog_sub(sch, len);
+		if (net_xmit_drop_count(ret)) {
+			WRITE_ONCE(q->stats.pdrop,
+				   q->stats.pdrop + 1);
+			qdisc_qstats_drop(sch);
+		}
 	}
 	return ret;
 
-- 
2.43.0

[Cake] [PATCH net-next v6 4/4] net/sched: cake: hash before segmenting and reject an overlong split

[Jamal Hadi Salim]

The Fix:
with CAKE_FLAG_SPLIT_GSO, cake computes the flow/host hash keys, then
splits a GSO skb into segments it accounts individually. Key extraction
must run on the unsegmented skb -- skb_gso_segment() can rewrite an
encapsulated packet's headers to the inner ones -- and the resolution
must wait until the packet is admitted, since it commits the
set-associative tags, host indices and way counters that a later
rejection would leave mutated (a GSO skb whose segmentation fails was
dropped with that state already committed).

Split cake_hash() into a side-effect-free cake_hash_keys(), run on the
unsegmented skb, and cake_hash_resolve(), run only once the packet is
admitted. Move the split-GSO path ahead of the resolution: sum the
segment list, test the total against the ceiling before linking any
segment, and drop the whole list on rejection so no persistent state is
committed. The list is deferred to to_free so the tail segment's
sock_wfree() never runs under the qdisc lock; a fraglist GSO, where
skb_segment_list() returns the original skb as the head, drops the
caller's reference and queues the list once instead of self-linking it.

Reviewed-by: Victor Nogueira <victor@mojatatu.com>
Signed-off-by: Jamal Hadi Salim <jhs@mojatatu.com>

---
v5 -> v6: split out of the single v5 patch; the hash logic is unchanged.
---
 net/sched/sch_cake.c | 126 ++++++++++++++++++++++++++++++++-----------
 1 file changed, 95 insertions(+), 31 deletions(-)

diff --git a/net/sched/sch_cake.c b/net/sched/sch_cake.c
index adfe11737c66..c67db1c61a90 100644
--- a/net/sched/sch_cake.c
+++ b/net/sched/sch_cake.c
@@ -706,19 +706,28 @@ static u16 cake_get_flow_quantum(struct cake_tin_data *q,
 		get_random_u16()) >> 16;
 }
 
-static u32 cake_hash(struct cake_tin_data *q, const struct sk_buff *skb,
-		     int flow_mode, u16 flow_override, u16 host_override)
+struct cake_hash_keys {
+	u32 srchost_hash;
+	u32 dsthost_hash;
+	u32 flow_hash;
+};
+
+static void cake_hash_keys(const struct sk_buff *skb, int flow_mode,
+			   u16 flow_override, u16 host_override,
+			   struct cake_hash_keys *out)
 {
 	bool hash_flows = (!flow_override && !!(flow_mode & CAKE_FLOW_FLOWS));
 	bool hash_hosts = (!host_override && !!(flow_mode & CAKE_FLOW_HOSTS));
 	bool nat_enabled = !!(flow_mode & CAKE_FLOW_NAT_FLAG);
-	u32 flow_hash = 0, srchost_hash = 0, dsthost_hash = 0;
-	u16 reduced_hash, srchost_idx, dsthost_idx;
 	struct flow_keys keys, host_keys;
 	bool use_skbhash = skb->l4_hash;
 
+	out->flow_hash = 0;
+	out->srchost_hash = 0;
+	out->dsthost_hash = 0;
+
 	if (unlikely(flow_mode == CAKE_FLOW_NONE))
-		return 0;
+		return;
 
 	/* If both overrides are set, or we can use the SKB hash and nat mode is
 	 * disabled, we can skip packet dissection entirely. If nat mode is
@@ -753,50 +762,65 @@ static u32 cake_hash(struct cake_tin_data *q, const struct sk_buff *skb,
 	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);
+		out->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);
+		out->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);
+		out->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);
+		out->srchost_hash = flow_hash_from_keys(&host_keys);
 		break;
 
 	default:
-		dsthost_hash = 0;
-		srchost_hash = 0;
+		out->dsthost_hash = 0;
+		out->srchost_hash = 0;
 	}
 
 	/* This *must* be after the above switch, since as a
 	 * side-effect it sorts the src and dst addresses.
 	 */
 	if (hash_flows && !use_skbhash)
-		flow_hash = flow_hash_from_keys(&keys);
+		out->flow_hash = flow_hash_from_keys(&keys);
 
 skip_hash:
 	if (flow_override)
-		flow_hash = flow_override - 1;
+		out->flow_hash = flow_override - 1;
 	else if (use_skbhash && (flow_mode & CAKE_FLOW_FLOWS))
-		flow_hash = skb->hash;
+		out->flow_hash = skb->hash;
 	if (host_override) {
-		dsthost_hash = host_override - 1;
-		srchost_hash = host_override - 1;
+		out->dsthost_hash = host_override - 1;
+		out->srchost_hash = host_override - 1;
 	}
 
 	if (!(flow_mode & CAKE_FLOW_FLOWS)) {
 		if (flow_mode & CAKE_FLOW_SRC_IP)
-			flow_hash ^= srchost_hash;
+			out->flow_hash ^= out->srchost_hash;
 
 		if (flow_mode & CAKE_FLOW_DST_IP)
-			flow_hash ^= dsthost_hash;
+			out->flow_hash ^= out->dsthost_hash;
 	}
+}
+
+/* Commit the resolved flow into the set-associative table. Mutates
+ * q->tags[], the flow host indices, the way counters and the host
+ * bulk-flow counts, so run only after admission.
+ */
+static u32 cake_hash_resolve(struct cake_tin_data *q,
+			     const struct cake_hash_keys *keys, int flow_mode)
+{
+	u32 flow_hash = keys->flow_hash, srchost_hash = keys->srchost_hash,
+	    dsthost_hash = keys->dsthost_hash;
+	u16 reduced_hash, srchost_idx, dsthost_idx;
+
+	if (unlikely(flow_mode == CAKE_FLOW_NONE))
+		return 0;
 
 	reduced_hash = flow_hash % CAKE_QUEUES;
 
@@ -1763,11 +1787,14 @@ static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 	struct cake_sched_data *q = qdisc_priv(sch);
 	int len = qdisc_pkt_len(skb), ret;
 	u16 flow_override, host_override;
+	struct sk_buff *segs = NULL;
+	struct cake_hash_keys keys;
 	struct sk_buff *ack = NULL;
 	ktime_t now = ktime_get();
 	struct cake_tin_data *b;
 	struct cake_flow *flow;
 	bool same_flow = false;
+	u64 slen = 0;
 
 	/* Classify first: a terminal TC action consumes the packet. */
 	if (cake_tcf_classify(sch, skb, &flow_override, &host_override, &ret)) {
@@ -1787,12 +1814,55 @@ static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 					 QDISC_DROP_OVERLIMIT);
 	}
 
-	/* choose flow to insert into */
+	/* Tin selection and key extraction run on the unsegmented skb:
+	 * skb_gso_segment() rewrites an encapsulated GSO packet's headers to
+	 * the inner ones, changing the keys. Neither commits state.
+	 */
 	b = cake_select_tin(sch, skb);
-	idx = cake_hash(b, skb, q->config->flow_mode, flow_override,
-			host_override) + 1;
+	cake_hash_keys(skb, q->config->flow_mode, flow_override,
+		       host_override, &keys);
+
+	if (qdisc_pkt_segs(skb) > 1 && q->config->rate_flags & CAKE_FLAG_SPLIT_GSO) {
+		struct sk_buff *nskb, *seg;
+		netdev_features_t features = netif_skb_features(skb);
+
+		segs = skb_gso_segment(skb, features & ~NETIF_F_GSO_MASK);
+		if (IS_ERR_OR_NULL(segs))
+			return qdisc_drop(skb, sch, to_free);
+
+		/* The split path accounts the segment sum, not the
+		 * stab-adjusted qdisc_pkt_len(), so the top check does not
+		 * bound it. Sum the list and reject it whole.
+		 */
+		skb_list_walk_safe(segs, seg, nskb)
+			slen += seg->len;
+
+		if (unlikely((u64)sch->qstats.backlog + slen > QDISC_MAX_BACKLOG)) {
+			qdisc_qstats_overlimit(sch);
+			/* skb_gso_segment() moved the sock_wfree destructor to
+			 * the tail segment; defer the whole list to to_free,
+			 * never free it under the qdisc lock.
+			 *
+			 * Fraglist GSO is the exception: skb_segment_list()
+			 * returns the original skb as the head with an extra
+			 * ref (segs == skb), so drop the caller's ref and
+			 * queue the list once, or the two drops self-link it.
+			 */
+			if (unlikely(segs == skb)) {
+				tcf_set_qdisc_drop_reason(skb,
+							  QDISC_DROP_OVERLIMIT);
+				consume_skb(skb);
+				return qdisc_drop_all(segs, sch, to_free);
+			}
+			__qdisc_drop_all(segs, to_free);
+			return qdisc_drop_reason(skb, sch, to_free,
+						 QDISC_DROP_OVERLIMIT);
+		}
+	}
+
+	/* Admitted: resolve the keys and commit flow/shaper state. */
+	idx = cake_hash_resolve(b, &keys, q->config->flow_mode);
 	tin = (u32)(b - q->tins);
-	idx--;
 	flow = &b->flows[idx];
 
 	/* ensure shaper state isn't stale */
@@ -1819,14 +1889,9 @@ static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 	if (unlikely(len > b->max_skblen))
 		WRITE_ONCE(b->max_skblen, len);
 
-	if (qdisc_pkt_segs(skb) > 1 && q->config->rate_flags & CAKE_FLAG_SPLIT_GSO) {
-		struct sk_buff *segs, *nskb, *seg;
-		netdev_features_t features = netif_skb_features(skb);
-		unsigned int slen = 0, numsegs = 0;
-
-		segs = skb_gso_segment(skb, features & ~NETIF_F_GSO_MASK);
-		if (IS_ERR_OR_NULL(segs))
-			return qdisc_drop(skb, sch, to_free);
+	if (segs) {
+		struct sk_buff *nskb, *seg;
+		unsigned int numsegs = 0;
 
 		skb_list_walk_safe(segs, seg, nskb) {
 			skb_mark_not_on_list(seg);
@@ -1840,7 +1905,6 @@ static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 			qdisc_qlen_inc(sch);
 			numsegs++;
 			q->buffer_used += seg->truesize;
-			slen += seg->len;
 			WRITE_ONCE(b->packets, b->packets + 1);
 		}
 
-- 
2.43.0