[Cake] [PATCH net-next] net/sched: fq_codel, cake: widen backlogs to u64

[Cake] [PATCH net-next] net/sched: fq_codel, cake: widen backlogs to u64

[Jamal Hadi Salim]

This is a follow-up to commit 8f735d64382d ("net/sched: bound
qdisc_pkt_len to prevent qdisc soft lockup"), which capped
qdisc_pkt_len() at QDISC_PKT_LEN_MAX (1 MiB). That cap bounds the stab
amplifier but leaves the per-flow backlog counter u32:
fq_codel_enqueue() accumulates qdisc_pkt_len(skb) into q->backlogs[idx],
so a flow can still accumulate 4096 packets of 1 MiB each and wrap the
counter mod 2^32. After a wrap, fq_codel_drop() sees a tiny maxbacklog
and drops from an almost-empty flow, and the dequeue-side subtractions
corrupt the counter further.

Widen the fq_codel backlogs table, the fat-flow scan (maxbacklog/len) and
the drop threshold to u64. fq_codel is not lockless: every writer runs
under the root qdisc lock, so plain u64 arithmetic keeps the WRITE_ONCE
publish / READ_ONCE-consume pattern. The dump path
(fq_codel_dump_class_stats) stays a lockless stat-only read.

CAKE accumulates the same generic qdisc_pkt_len(skb) into its per-flow
b->backlogs[] and per-tin b->tin_backlog and consumes the values for
longest-flow pruning (cake_heapify/cake_heapify_up) and for the shaper
staleness check, so it shares the bug. Widen those counters and the heap
comparison locals to u64; the class/tin stats keep exporting the low 32
bits through the unchanged uAPI fields.

Conditions to recreate the bug: CAP_NET_ADMIN in a user namespace;
CONFIG_NET_SCH_FQ_CODEL=y.

  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 4200 ecn drop_batch 4096
  # hold the tun fd open without reading (IFF_BACKPRESSURE) so the qdisc
  # backlog persists, then send at least 4300 packets (the wrap starts
  # at 4096 resident; the over-limit drop that reads the wrapped
  # threshold fires past the 4200 limit): backlogs[0] wraps at 4096 x
  # 1 MiB and the fat-flow threshold reads the wrapped value.

With a 1 MiB qdisc_pkt_len cap the counter wraps at 4096 resident
packets. At limit 4200 the first over-limit enqueue (the 4201st) sees a
wrapped 105 MiB (half-backlog threshold 52 MiB, a ~52 packet drop burst),
where the u64 counter sees 4201 MiB (threshold 2100 MiB, a ~2100 packet
drop burst).

Reported-by: Sashiko (nipa) <sashiko-bot@kernel.org>
Closes: https://netdev-ai.bots.linux.dev/sashiko/#/patchset/20260818101130.16203-1-jhs@mojatatu.com
Link: https://lore.kernel.org/netdev/20260818101130.16203-1-jhs@mojatatu.com/
Tested-by: hybris <hybris@mojatatu.ai>
Signed-off-by: Jamal Hadi Salim <jhs@mojatatu.com>
---
 net/sched/sch_cake.c     | 23 ++++++++++++-----------
 net/sched/sch_fq_codel.c | 22 ++++++++++++----------
 2 files changed, 24 insertions(+), 21 deletions(-)

diff --git a/net/sched/sch_cake.c b/net/sched/sch_cake.c
index dc93267029e7..8e99c85dab17 100644
--- a/net/sched/sch_cake.c
+++ b/net/sched/sch_cake.c
@@ -150,7 +150,7 @@ struct cake_heap_entry {
 
 struct cake_tin_data {
 	struct cake_flow flows[CAKE_QUEUES];
-	u32	backlogs[CAKE_QUEUES];
+	u64	backlogs[CAKE_QUEUES];
 	u32	tags[CAKE_QUEUES]; /* for set association */
 	u16	overflow_idx[CAKE_QUEUES];
 	struct cake_host hosts[CAKE_QUEUES]; /* for triple isolation */
@@ -177,7 +177,7 @@ struct cake_tin_data {
 
 	u16	tin_quantum;
 	s32	tin_deficit;
-	u32	tin_backlog;
+	u64	tin_backlog;
 	u32	tin_dropped;
 	u32	tin_ecn_mark;
 
@@ -1466,17 +1466,17 @@ static void cake_heap_swap(struct cake_sched_data *q, u16 i, u16 j)
 	q->tins[jj.t].overflow_idx[jj.b] = i;
 }
 
-static u32 cake_heap_get_backlog(const struct cake_sched_data *q, u16 i)
+static u64 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];
+	return READ_ONCE(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);
+	u64 mb = cake_heap_get_backlog(q, i);
 	u32 m = i;
 
 	while (m < a) {
@@ -1484,7 +1484,7 @@ static void cake_heapify(struct cake_sched_data *q, u16 i)
 		u32 r = l + 1;
 
 		if (l < a) {
-			u32 lb = cake_heap_get_backlog(q, l);
+			u64 lb = cake_heap_get_backlog(q, l);
 
 			if (lb > mb) {
 				m  = l;
@@ -1493,7 +1493,7 @@ static void cake_heapify(struct cake_sched_data *q, u16 i)
 		}
 
 		if (r < a) {
-			u32 rb = cake_heap_get_backlog(q, r);
+			u64 rb = cake_heap_get_backlog(q, r);
 
 			if (rb > mb) {
 				m  = r;
@@ -1514,8 +1514,8 @@ 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);
+		u64 ib = cake_heap_get_backlog(q, i);
+		u64 pb = cake_heap_get_backlog(q, p);
 
 		if (ib > pb) {
 			cake_heap_swap(q, i, p);
@@ -3046,7 +3046,8 @@ static int cake_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
 
 		PUT_TSTAT_U64(THRESHOLD_RATE64, READ_ONCE(b->tin_rate_bps));
 		PUT_TSTAT_U64(SENT_BYTES64, READ_ONCE(b->bytes));
-		PUT_TSTAT_U32(BACKLOG_BYTES, READ_ONCE(b->tin_backlog));
+		PUT_TSTAT_U32(BACKLOG_BYTES,
+			      (u32)READ_ONCE(b->tin_backlog));
 
 		PUT_TSTAT_U32(TARGET_US,
 			      ktime_to_us(ns_to_ktime(READ_ONCE(b->cparams.target))));
@@ -3152,7 +3153,7 @@ static int cake_dump_class_stats(struct Qdisc *sch, unsigned long cl,
 			}
 			sch_tree_unlock(sch);
 		}
-		qs.backlog = READ_ONCE(b->backlogs[idx % CAKE_QUEUES]);
+		qs.backlog = (u32)READ_ONCE(b->backlogs[idx % CAKE_QUEUES]);
 		qs.drops = READ_ONCE(flow->dropped);
 	}
 	if (gnet_stats_copy_queue(d, NULL, &qs, qs.qlen) < 0)
diff --git a/net/sched/sch_fq_codel.c b/net/sched/sch_fq_codel.c
index 969b2510b0b8..3c20297cef07 100644
--- a/net/sched/sch_fq_codel.c
+++ b/net/sched/sch_fq_codel.c
@@ -51,7 +51,7 @@ struct fq_codel_sched_data {
 	struct tcf_proto __rcu *filter_list; /* optional external classifier */
 	struct tcf_block *block;
 	struct fq_codel_flow *flows;	/* Flows table [flows_cnt] */
-	u32		*backlogs;	/* backlog table [flows_cnt] */
+	u64		*backlogs;	/* backlog table [flows_cnt] */
 	u32		flows_cnt;	/* number of flows */
 	u32		quantum;	/* psched_mtu(qdisc_dev(sch)); */
 	u32		drop_batch_size;
@@ -138,22 +138,25 @@ static unsigned int fq_codel_drop(struct Qdisc *sch, unsigned int max_packets,
 				  struct sk_buff **to_free)
 {
 	struct fq_codel_sched_data *q = qdisc_priv(sch);
+	u64 maxbacklog = 0, len = 0;
 	struct sk_buff *skb;
-	unsigned int maxbacklog = 0, idx = 0, i, len;
 	struct fq_codel_flow *flow;
-	unsigned int threshold;
+	unsigned int idx = 0, i;
 	unsigned int mem = 0;
+	u64 threshold;
 
 	/* Queue is full! Find the fat flow and drop packet(s) from it.
 	 * This might sound expensive, but with 1024 flows, we scan
-	 * 4KB of memory, and we dont need to handle a complex tree
+	 * 8KB of memory, and we dont need to handle a complex tree
 	 * in fast path (packet queue/enqueue) with many cache misses.
 	 * In stress mode, we'll try to drop 64 packets from the flow,
 	 * amortizing this linear lookup to one cache line per drop.
 	 */
 	for (i = 0; i < q->flows_cnt; i++) {
-		if (q->backlogs[i] > maxbacklog) {
-			maxbacklog = q->backlogs[i];
+		u64 backlog = READ_ONCE(q->backlogs[i]);
+
+		if (backlog > maxbacklog) {
+			maxbacklog = backlog;
 			idx = i;
 		}
 	}
@@ -162,7 +165,6 @@ static unsigned int fq_codel_drop(struct Qdisc *sch, unsigned int max_packets,
 	threshold = maxbacklog >> 1;
 
 	flow = &q->flows[idx];
-	len = 0;
 	i = 0;
 	do {
 		skb = dequeue_head(flow);
@@ -384,7 +386,7 @@ static void fq_codel_reset(struct Qdisc *sch)
 		INIT_LIST_HEAD(&flow->flowchain);
 		codel_vars_init(&flow->cvars);
 	}
-	memset(q->backlogs, 0, q->flows_cnt * sizeof(u32));
+	memset(q->backlogs, 0, q->flows_cnt * sizeof(u64));
 	q->memory_usage = 0;
 }
 
@@ -542,7 +544,7 @@ static int fq_codel_init(struct Qdisc *sch, struct nlattr *opt,
 			err = -ENOMEM;
 			goto init_failure;
 		}
-		q->backlogs = kvcalloc(q->flows_cnt, sizeof(u32), GFP_KERNEL);
+		q->backlogs = kvcalloc(q->flows_cnt, sizeof(u64), GFP_KERNEL);
 		if (!q->backlogs) {
 			err = -ENOMEM;
 			goto alloc_failure;
@@ -720,7 +722,7 @@ static int fq_codel_dump_class_stats(struct Qdisc *sch, unsigned long cl,
 			}
 			sch_tree_unlock(sch);
 		}
-		qs.backlog = READ_ONCE(q->backlogs[idx]);
+		qs.backlog = (u32)READ_ONCE(q->backlogs[idx]);
 		qs.drops = 0;
 	}
 	if (gnet_stats_copy_queue(d, NULL, &qs, qs.qlen) < 0)
-- 
2.43.0

[Cake] Re: [PATCH net-next] net/sched: fq_codel, cake: widen backlogs to u64

[Eric Dumazet]

On Fri, Sep 25, 2026 at 10:54 AM Jamal Hadi Salim <jhs@mojatatu.com> wrote:
>
> This is a follow-up to commit 8f735d64382d ("net/sched: bound
> qdisc_pkt_len to prevent qdisc soft lockup"), which capped
> qdisc_pkt_len() at QDISC_PKT_LEN_MAX (1 MiB). That cap bounds the stab
> amplifier but leaves the per-flow backlog counter u32:
> fq_codel_enqueue() accumulates qdisc_pkt_len(skb) into q->backlogs[idx],
> so a flow can still accumulate 4096 packets of 1 MiB each and wrap the
> counter mod 2^32. After a wrap, fq_codel_drop() sees a tiny maxbacklog
> and drops from an almost-empty flow, and the dequeue-side subtractions
> corrupt the counter further.
>
> Widen the fq_codel backlogs table, the fat-flow scan (maxbacklog/len) and
> the drop threshold to u64. fq_codel is not lockless: every writer runs
> under the root qdisc lock, so plain u64 arithmetic keeps the WRITE_ONCE
> publish / READ_ONCE-consume pattern. The dump path
> (fq_codel_dump_class_stats) stays a lockless stat-only read.
>
> CAKE accumulates the same generic qdisc_pkt_len(skb) into its per-flow
> b->backlogs[] and per-tin b->tin_backlog and consumes the values for
> longest-flow pruning (cake_heapify/cake_heapify_up) and for the shaper
> staleness check, so it shares the bug. Widen those counters and the heap
> comparison locals to u64; the class/tin stats keep exporting the low 32
> bits through the unchanged uAPI fields.
>
> Conditions to recreate the bug: CAP_NET_ADMIN in a user namespace;
> CONFIG_NET_SCH_FQ_CODEL=y.
>
>   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 4200 ecn drop_batch 4096
>   # hold the tun fd open without reading (IFF_BACKPRESSURE) so the qdisc
>   # backlog persists, then send at least 4300 packets (the wrap starts
>   # at 4096 resident; the over-limit drop that reads the wrapped
>   # threshold fires past the 4200 limit): backlogs[0] wraps at 4096 x
>   # 1 MiB and the fat-flow threshold reads the wrapped value.
>
> With a 1 MiB qdisc_pkt_len cap the counter wraps at 4096 resident
> packets. At limit 4200 the first over-limit enqueue (the 4201st) sees a
> wrapped 105 MiB (half-backlog threshold 52 MiB, a ~52 packet drop burst),
> where the u64 counter sees 4201 MiB (threshold 2100 MiB, a ~2100 packet
> drop burst).
>
> Reported-by: Sashiko (nipa) <sashiko-bot@kernel.org>
> Closes: https://netdev-ai.bots.linux.dev/sashiko/#/patchset/20260818101130.16203-1-jhs@mojatatu.com
> Link: https://lore.kernel.org/netdev/20260818101130.16203-1-jhs@mojatatu.com/
> Tested-by: hybris <hybris@mojatatu.ai>
> Signed-off-by: Jamal Hadi Salim <jhs@mojatatu.com>
> ---

This makes no sense.

These qdisc have been developped to address bufferbloat issues.

Storing 4GB in a qdisc is absolutely insane.

Let's drop at enqueue if the current backlog is approaching 4GB (this
can later be a new config/attribute in net-next)

[Cake] Re: [PATCH net-next] net/sched: fq_codel, cake: widen backlogs to u64

[Jamal Hadi Salim]

On Fri, Sep 25, 2026 at 5:13 AM Eric Dumazet <edumazet@google.com> wrote:
>
> On Fri, Sep 25, 2026 at 10:54 AM Jamal Hadi Salim <jhs@mojatatu.com> wrote:
> >
> > This is a follow-up to commit 8f735d64382d ("net/sched: bound
> > qdisc_pkt_len to prevent qdisc soft lockup"), which capped
> > qdisc_pkt_len() at QDISC_PKT_LEN_MAX (1 MiB). That cap bounds the stab
> > amplifier but leaves the per-flow backlog counter u32:
> > fq_codel_enqueue() accumulates qdisc_pkt_len(skb) into q->backlogs[idx],
> > so a flow can still accumulate 4096 packets of 1 MiB each and wrap the
> > counter mod 2^32. After a wrap, fq_codel_drop() sees a tiny maxbacklog
> > and drops from an almost-empty flow, and the dequeue-side subtractions
> > corrupt the counter further.
> >
> > Widen the fq_codel backlogs table, the fat-flow scan (maxbacklog/len) and
> > the drop threshold to u64. fq_codel is not lockless: every writer runs
> > under the root qdisc lock, so plain u64 arithmetic keeps the WRITE_ONCE
> > publish / READ_ONCE-consume pattern. The dump path
> > (fq_codel_dump_class_stats) stays a lockless stat-only read.
> >
> > CAKE accumulates the same generic qdisc_pkt_len(skb) into its per-flow
> > b->backlogs[] and per-tin b->tin_backlog and consumes the values for
> > longest-flow pruning (cake_heapify/cake_heapify_up) and for the shaper
> > staleness check, so it shares the bug. Widen those counters and the heap
> > comparison locals to u64; the class/tin stats keep exporting the low 32
> > bits through the unchanged uAPI fields.
> >
> > Conditions to recreate the bug: CAP_NET_ADMIN in a user namespace;
> > CONFIG_NET_SCH_FQ_CODEL=y.
> >
> >   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 4200 ecn drop_batch 4096
> >   # hold the tun fd open without reading (IFF_BACKPRESSURE) so the qdisc
> >   # backlog persists, then send at least 4300 packets (the wrap starts
> >   # at 4096 resident; the over-limit drop that reads the wrapped
> >   # threshold fires past the 4200 limit): backlogs[0] wraps at 4096 x
> >   # 1 MiB and the fat-flow threshold reads the wrapped value.
> >
> > With a 1 MiB qdisc_pkt_len cap the counter wraps at 4096 resident
> > packets. At limit 4200 the first over-limit enqueue (the 4201st) sees a
> > wrapped 105 MiB (half-backlog threshold 52 MiB, a ~52 packet drop burst),
> > where the u64 counter sees 4201 MiB (threshold 2100 MiB, a ~2100 packet
> > drop burst).
> >
> > Reported-by: Sashiko (nipa) <sashiko-bot@kernel.org>
> > Closes: https://netdev-ai.bots.linux.dev/sashiko/#/patchset/20260818101130.16203-1-jhs@mojatatu.com
> > Link: https://lore.kernel.org/netdev/20260818101130.16203-1-jhs@mojatatu.com/
> > Tested-by: hybris <hybris@mojatatu.ai>
> > Signed-off-by: Jamal Hadi Salim <jhs@mojatatu.com>
> > ---
>
> This makes no sense.
>

As absurd as it looks that code is reachable ;->

> These qdisc have been developped to address bufferbloat issues.
>
> Storing 4GB in a qdisc is absolutely insane.
>

The counter wrap is not because we stored 4GB, rather it is because
"tc .. stab overhead ..." inflates qdisc_pkt_len() for a 64B pkt to
1MB. So ~4K packets (put in other words a few "real" KB) makes that
backlog[0] cross 2^32.
Result is pruning the wrong flow..

> Let's drop at enqueue if the current backlog is approaching 4GB (this
> can later be a new config/attribute in net-next)

Note, this is net-next already. Enqueue is fast path - are you ok with that?

cheers,
jamal

[Cake] Re: [PATCH net-next] net/sched: fq_codel, cake: widen backlogs to u64

[Jamal Hadi Salim]

On Fri, Sep 25, 2026 at 7:27 AM Jamal Hadi Salim <jhs@mojatatu.com> wrote:
>
> On Fri, Sep 25, 2026 at 5:13 AM Eric Dumazet <edumazet@google.com> wrote:
> >
> > On Fri, Sep 25, 2026 at 10:54 AM Jamal Hadi Salim <jhs@mojatatu.com> wrote:
> > >
> > > This is a follow-up to commit 8f735d64382d ("net/sched: bound
> > > qdisc_pkt_len to prevent qdisc soft lockup"), which capped
> > > qdisc_pkt_len() at QDISC_PKT_LEN_MAX (1 MiB). That cap bounds the stab
> > > amplifier but leaves the per-flow backlog counter u32:
> > > fq_codel_enqueue() accumulates qdisc_pkt_len(skb) into q->backlogs[idx],
> > > so a flow can still accumulate 4096 packets of 1 MiB each and wrap the
> > > counter mod 2^32. After a wrap, fq_codel_drop() sees a tiny maxbacklog
> > > and drops from an almost-empty flow, and the dequeue-side subtractions
> > > corrupt the counter further.
> > >
> > > Widen the fq_codel backlogs table, the fat-flow scan (maxbacklog/len) and
> > > the drop threshold to u64. fq_codel is not lockless: every writer runs
> > > under the root qdisc lock, so plain u64 arithmetic keeps the WRITE_ONCE
> > > publish / READ_ONCE-consume pattern. The dump path
> > > (fq_codel_dump_class_stats) stays a lockless stat-only read.
> > >
> > > CAKE accumulates the same generic qdisc_pkt_len(skb) into its per-flow
> > > b->backlogs[] and per-tin b->tin_backlog and consumes the values for
> > > longest-flow pruning (cake_heapify/cake_heapify_up) and for the shaper
> > > staleness check, so it shares the bug. Widen those counters and the heap
> > > comparison locals to u64; the class/tin stats keep exporting the low 32
> > > bits through the unchanged uAPI fields.
> > >
> > > Conditions to recreate the bug: CAP_NET_ADMIN in a user namespace;
> > > CONFIG_NET_SCH_FQ_CODEL=y.
> > >
> > >   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 4200 ecn drop_batch 4096
> > >   # hold the tun fd open without reading (IFF_BACKPRESSURE) so the qdisc
> > >   # backlog persists, then send at least 4300 packets (the wrap starts
> > >   # at 4096 resident; the over-limit drop that reads the wrapped
> > >   # threshold fires past the 4200 limit): backlogs[0] wraps at 4096 x
> > >   # 1 MiB and the fat-flow threshold reads the wrapped value.
> > >
> > > With a 1 MiB qdisc_pkt_len cap the counter wraps at 4096 resident
> > > packets. At limit 4200 the first over-limit enqueue (the 4201st) sees a
> > > wrapped 105 MiB (half-backlog threshold 52 MiB, a ~52 packet drop burst),
> > > where the u64 counter sees 4201 MiB (threshold 2100 MiB, a ~2100 packet
> > > drop burst).
> > >
> > > Reported-by: Sashiko (nipa) <sashiko-bot@kernel.org>
> > > Closes: https://netdev-ai.bots.linux.dev/sashiko/#/patchset/20260818101130.16203-1-jhs@mojatatu.com
> > > Link: https://lore.kernel.org/netdev/20260818101130.16203-1-jhs@mojatatu.com/
> > > Tested-by: hybris <hybris@mojatatu.ai>
> > > Signed-off-by: Jamal Hadi Salim <jhs@mojatatu.com>
> > > ---
> >
> > This makes no sense.
> >
>
> As absurd as it looks that code is reachable ;->
>
> > These qdisc have been developped to address bufferbloat issues.
> >
> > Storing 4GB in a qdisc is absolutely insane.
> >
>
> The counter wrap is not because we stored 4GB, rather it is because
> "tc .. stab overhead ..." inflates qdisc_pkt_len() for a 64B pkt to
> 1MB. So ~4K packets (put in other words a few "real" KB) makes that
> backlog[0] cross 2^32.
> Result is pruning the wrong flow..
>
> > Let's drop at enqueue if the current backlog is approaching 4GB (this
> > can later be a new config/attribute in net-next)
>
> Note, this is net-next already. Enqueue is fast path - are you ok with that?
>

And the least ugly approach (not tested) is attached.

cheers,
jamal

> cheers,
> jamal

[Cake] Re: [PATCH net-next] net/sched: fq_codel, cake: widen backlogs to u64

[Eric Dumazet]

On Fri, Sep 25, 2026 at 1:28 PM Jamal Hadi Salim <jhs@mojatatu.com> wrote:
>
> On Fri, Sep 25, 2026 at 5:13 AM Eric Dumazet <edumazet@google.com> wrote:
> >
> > On Fri, Sep 25, 2026 at 10:54 AM Jamal Hadi Salim <jhs@mojatatu.com> wrote:
> > >
> > > This is a follow-up to commit 8f735d64382d ("net/sched: bound
> > > qdisc_pkt_len to prevent qdisc soft lockup"), which capped
> > > qdisc_pkt_len() at QDISC_PKT_LEN_MAX (1 MiB). That cap bounds the stab
> > > amplifier but leaves the per-flow backlog counter u32:
> > > fq_codel_enqueue() accumulates qdisc_pkt_len(skb) into q->backlogs[idx],
> > > so a flow can still accumulate 4096 packets of 1 MiB each and wrap the
> > > counter mod 2^32. After a wrap, fq_codel_drop() sees a tiny maxbacklog
> > > and drops from an almost-empty flow, and the dequeue-side subtractions
> > > corrupt the counter further.
> > >
> > > Widen the fq_codel backlogs table, the fat-flow scan (maxbacklog/len) and
> > > the drop threshold to u64. fq_codel is not lockless: every writer runs
> > > under the root qdisc lock, so plain u64 arithmetic keeps the WRITE_ONCE
> > > publish / READ_ONCE-consume pattern. The dump path
> > > (fq_codel_dump_class_stats) stays a lockless stat-only read.
> > >
> > > CAKE accumulates the same generic qdisc_pkt_len(skb) into its per-flow
> > > b->backlogs[] and per-tin b->tin_backlog and consumes the values for
> > > longest-flow pruning (cake_heapify/cake_heapify_up) and for the shaper
> > > staleness check, so it shares the bug. Widen those counters and the heap
> > > comparison locals to u64; the class/tin stats keep exporting the low 32
> > > bits through the unchanged uAPI fields.
> > >
> > > Conditions to recreate the bug: CAP_NET_ADMIN in a user namespace;
> > > CONFIG_NET_SCH_FQ_CODEL=y.
> > >
> > >   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 4200 ecn drop_batch 4096
> > >   # hold the tun fd open without reading (IFF_BACKPRESSURE) so the qdisc
> > >   # backlog persists, then send at least 4300 packets (the wrap starts
> > >   # at 4096 resident; the over-limit drop that reads the wrapped
> > >   # threshold fires past the 4200 limit): backlogs[0] wraps at 4096 x
> > >   # 1 MiB and the fat-flow threshold reads the wrapped value.
> > >
> > > With a 1 MiB qdisc_pkt_len cap the counter wraps at 4096 resident
> > > packets. At limit 4200 the first over-limit enqueue (the 4201st) sees a
> > > wrapped 105 MiB (half-backlog threshold 52 MiB, a ~52 packet drop burst),
> > > where the u64 counter sees 4201 MiB (threshold 2100 MiB, a ~2100 packet
> > > drop burst).
> > >
> > > Reported-by: Sashiko (nipa) <sashiko-bot@kernel.org>
> > > Closes: https://netdev-ai.bots.linux.dev/sashiko/#/patchset/20260818101130.16203-1-jhs@mojatatu.com
> > > Link: https://lore.kernel.org/netdev/20260818101130.16203-1-jhs@mojatatu.com/
> > > Tested-by: hybris <hybris@mojatatu.ai>
> > > Signed-off-by: Jamal Hadi Salim <jhs@mojatatu.com>
> > > ---
> >
> > This makes no sense.
> >
>
> As absurd as it looks that code is reachable ;->
>
> > These qdisc have been developped to address bufferbloat issues.
> >
> > Storing 4GB in a qdisc is absolutely insane.
> >
>
> The counter wrap is not because we stored 4GB, rather it is because
> "tc .. stab overhead ..." inflates qdisc_pkt_len() for a 64B pkt to
> 1MB. So ~4K packets (put in other words a few "real" KB) makes that
> backlog[0] cross 2^32.

Kill this stuff ? Who is still using this, for what reason ?

Really, it is time we stop adding code only for fuzzers.

> Result is pruning the wrong flow..
>
> > Let's drop at enqueue if the current backlog is approaching 4GB (this
> > can later be a new config/attribute in net-next)
>
> Note, this is net-next already. Enqueue is fast path - are you ok with that?
>
> cheers,
> jamal

[Cake] Re: [PATCH net-next] net/sched: fq_codel, cake: widen backlogs to u64

[Sebastian Moeller]

Hi Eric,


> On Sep 25, 2026, at 15:03, Eric Dumazet via Cake <cake@lists.bufferbloat.net> wrote:
> 
> On Fri, Sep 25, 2026 at 1:28 PM Jamal Hadi Salim <jhs@mojatatu.com> wrote:
>> 
>> On Fri, Sep 25, 2026 at 5:13 AM Eric Dumazet <edumazet@google.com> wrote:
>>> 
>>> On Fri, Sep 25, 2026 at 10:54 AM Jamal Hadi Salim <jhs@mojatatu.com> wrote:
>>>> 
>>>> This is a follow-up to commit 8f735d64382d ("net/sched: bound
>>>> qdisc_pkt_len to prevent qdisc soft lockup"), which capped
>>>> qdisc_pkt_len() at QDISC_PKT_LEN_MAX (1 MiB). That cap bounds the stab
>>>> amplifier but leaves the per-flow backlog counter u32:
>>>> fq_codel_enqueue() accumulates qdisc_pkt_len(skb) into q->backlogs[idx],
>>>> so a flow can still accumulate 4096 packets of 1 MiB each and wrap the
>>>> counter mod 2^32. After a wrap, fq_codel_drop() sees a tiny maxbacklog
>>>> and drops from an almost-empty flow, and the dequeue-side subtractions
>>>> corrupt the counter further.
>>>> 
>>>> Widen the fq_codel backlogs table, the fat-flow scan (maxbacklog/len) and
>>>> the drop threshold to u64. fq_codel is not lockless: every writer runs
>>>> under the root qdisc lock, so plain u64 arithmetic keeps the WRITE_ONCE
>>>> publish / READ_ONCE-consume pattern. The dump path
>>>> (fq_codel_dump_class_stats) stays a lockless stat-only read.
>>>> 
>>>> CAKE accumulates the same generic qdisc_pkt_len(skb) into its per-flow
>>>> b->backlogs[] and per-tin b->tin_backlog and consumes the values for
>>>> longest-flow pruning (cake_heapify/cake_heapify_up) and for the shaper
>>>> staleness check, so it shares the bug. Widen those counters and the heap
>>>> comparison locals to u64; the class/tin stats keep exporting the low 32
>>>> bits through the unchanged uAPI fields.
>>>> 
>>>> Conditions to recreate the bug: CAP_NET_ADMIN in a user namespace;
>>>> CONFIG_NET_SCH_FQ_CODEL=y.
>>>> 
>>>>  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 4200 ecn drop_batch 4096
>>>>  # hold the tun fd open without reading (IFF_BACKPRESSURE) so the qdisc
>>>>  # backlog persists, then send at least 4300 packets (the wrap starts
>>>>  # at 4096 resident; the over-limit drop that reads the wrapped
>>>>  # threshold fires past the 4200 limit): backlogs[0] wraps at 4096 x
>>>>  # 1 MiB and the fat-flow threshold reads the wrapped value.
>>>> 
>>>> With a 1 MiB qdisc_pkt_len cap the counter wraps at 4096 resident
>>>> packets. At limit 4200 the first over-limit enqueue (the 4201st) sees a
>>>> wrapped 105 MiB (half-backlog threshold 52 MiB, a ~52 packet drop burst),
>>>> where the u64 counter sees 4201 MiB (threshold 2100 MiB, a ~2100 packet
>>>> drop burst).
>>>> 
>>>> Reported-by: Sashiko (nipa) <sashiko-bot@kernel.org>
>>>> Closes: https://netdev-ai.bots.linux.dev/sashiko/#/patchset/20260818101130.16203-1-jhs@mojatatu.com
>>>> Link: https://lore.kernel.org/netdev/20260818101130.16203-1-jhs@mojatatu.com/
>>>> Tested-by: hybris <hybris@mojatatu.ai>
>>>> Signed-off-by: Jamal Hadi Salim <jhs@mojatatu.com>
>>>> ---
>>> 
>>> This makes no sense.
>>> 
>> 
>> As absurd as it looks that code is reachable ;->
>> 
>>> These qdisc have been developped to address bufferbloat issues.
>>> 
>>> Storing 4GB in a qdisc is absolutely insane.
>>> 
>> 
>> The counter wrap is not because we stored 4GB, rather it is because
>> "tc .. stab overhead ..." inflates qdisc_pkt_len() for a 64B pkt to
>> 1MB. So ~4K packets (put in other words a few "real" KB) makes that
>> backlog[0] cross 2^32.
> 
> Kill this stuff ? Who is still using this, for what reason ?

tc-stab? Same as before, if you need want to model a remote bottleneck with a local traffic shaper tc-stab is the generic solution (off the top of my head I only can enumerate cake as having its own traffic shaper that handles overheads).
One could argue that the "virtual" length should be accounted against cake's memlimit or fq-codel's memory_limit somehow...
In sane?/typical configurations overhead is expected to stay relatively small, so this would not limit the actual queue size too much, while potentially silencing this issue.

I might be off my rocker, in which has ignore (or preferably enlighten me).

Regards
	Sebastian

> 
> Really, it is time we stop adding code only for fuzzers.
> 
>> Result is pruning the wrong flow..
>> 
>>> Let's drop at enqueue if the current backlog is approaching 4GB (this
>>> can later be a new config/attribute in net-next)
>> 
>> Note, this is net-next already. Enqueue is fast path - are you ok with that?
>> 
>> cheers,
>> jamal
> _______________________________________________
> Cake mailing list -- cake@lists.bufferbloat.net
> To unsubscribe send an email to cake-leave@lists.bufferbloat.net

[Cake] Re: [PATCH net-next] net/sched: fq_codel, cake: widen backlogs to u64

[Eric Dumazet]

On Fri, Sep 25, 2026 at 3:30 PM Sebastian Moeller <moeller0@gmx.de> wrote:
>
> Hi Eric,
>
>
> > On Sep 25, 2026, at 15:03, Eric Dumazet via Cake <cake@lists.bufferbloat.net> wrote:
> >
> > On Fri, Sep 25, 2026 at 1:28 PM Jamal Hadi Salim <jhs@mojatatu.com> wrote:
> >>
> >> On Fri, Sep 25, 2026 at 5:13 AM Eric Dumazet <edumazet@google.com> wrote:
> >>>
> >>> On Fri, Sep 25, 2026 at 10:54 AM Jamal Hadi Salim <jhs@mojatatu.com> wrote:
> >>>>
> >>>> This is a follow-up to commit 8f735d64382d ("net/sched: bound
> >>>> qdisc_pkt_len to prevent qdisc soft lockup"), which capped
> >>>> qdisc_pkt_len() at QDISC_PKT_LEN_MAX (1 MiB). That cap bounds the stab
> >>>> amplifier but leaves the per-flow backlog counter u32:
> >>>> fq_codel_enqueue() accumulates qdisc_pkt_len(skb) into q->backlogs[idx],
> >>>> so a flow can still accumulate 4096 packets of 1 MiB each and wrap the
> >>>> counter mod 2^32. After a wrap, fq_codel_drop() sees a tiny maxbacklog
> >>>> and drops from an almost-empty flow, and the dequeue-side subtractions
> >>>> corrupt the counter further.
> >>>>
> >>>> Widen the fq_codel backlogs table, the fat-flow scan (maxbacklog/len) and
> >>>> the drop threshold to u64. fq_codel is not lockless: every writer runs
> >>>> under the root qdisc lock, so plain u64 arithmetic keeps the WRITE_ONCE
> >>>> publish / READ_ONCE-consume pattern. The dump path
> >>>> (fq_codel_dump_class_stats) stays a lockless stat-only read.
> >>>>
> >>>> CAKE accumulates the same generic qdisc_pkt_len(skb) into its per-flow
> >>>> b->backlogs[] and per-tin b->tin_backlog and consumes the values for
> >>>> longest-flow pruning (cake_heapify/cake_heapify_up) and for the shaper
> >>>> staleness check, so it shares the bug. Widen those counters and the heap
> >>>> comparison locals to u64; the class/tin stats keep exporting the low 32
> >>>> bits through the unchanged uAPI fields.
> >>>>
> >>>> Conditions to recreate the bug: CAP_NET_ADMIN in a user namespace;
> >>>> CONFIG_NET_SCH_FQ_CODEL=y.
> >>>>
> >>>>  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 4200 ecn drop_batch 4096
> >>>>  # hold the tun fd open without reading (IFF_BACKPRESSURE) so the qdisc
> >>>>  # backlog persists, then send at least 4300 packets (the wrap starts
> >>>>  # at 4096 resident; the over-limit drop that reads the wrapped
> >>>>  # threshold fires past the 4200 limit): backlogs[0] wraps at 4096 x
> >>>>  # 1 MiB and the fat-flow threshold reads the wrapped value.
> >>>>
> >>>> With a 1 MiB qdisc_pkt_len cap the counter wraps at 4096 resident
> >>>> packets. At limit 4200 the first over-limit enqueue (the 4201st) sees a
> >>>> wrapped 105 MiB (half-backlog threshold 52 MiB, a ~52 packet drop burst),
> >>>> where the u64 counter sees 4201 MiB (threshold 2100 MiB, a ~2100 packet
> >>>> drop burst).
> >>>>
> >>>> Reported-by: Sashiko (nipa) <sashiko-bot@kernel.org>
> >>>> Closes: https://netdev-ai.bots.linux.dev/sashiko/#/patchset/20260818101130.16203-1-jhs@mojatatu.com
> >>>> Link: https://lore.kernel.org/netdev/20260818101130.16203-1-jhs@mojatatu.com/
> >>>> Tested-by: hybris <hybris@mojatatu.ai>
> >>>> Signed-off-by: Jamal Hadi Salim <jhs@mojatatu.com>
> >>>> ---
> >>>
> >>> This makes no sense.
> >>>
> >>
> >> As absurd as it looks that code is reachable ;->
> >>
> >>> These qdisc have been developped to address bufferbloat issues.
> >>>
> >>> Storing 4GB in a qdisc is absolutely insane.
> >>>
> >>
> >> The counter wrap is not because we stored 4GB, rather it is because
> >> "tc .. stab overhead ..." inflates qdisc_pkt_len() for a 64B pkt to
> >> 1MB. So ~4K packets (put in other words a few "real" KB) makes that
> >> backlog[0] cross 2^32.
> >
> > Kill this stuff ? Who is still using this, for what reason ?
>
> tc-stab? Same as before, if you need want to model a remote bottleneck with a local traffic shaper tc-stab is the generic solution (off the top of my head I only can enumerate cake as having its own traffic shaper that handles overheads).
> One could argue that the "virtual" length should be accounted against cake's memlimit or fq-codel's memory_limit somehow...
> In sane?/typical configurations overhead is expected to stay relatively small, so this would not limit the actual queue size too much, while potentially silencing this issue.

linux qdisc are in the fast path, for nearly all packets sent over this planet.
They aleady consume GW of energy.

Modeling / network emulation should incur zero cost on these
production grade qdisc.

netem could be one answer, I do not know, or a special
CONFIG_NET_SCHED_EXPENSIVE_EMULATION

>
> I might be off my rocker, in which has ignore (or preferably enlighten me).

[Cake] Re: [PATCH net-next] net/sched: fq_codel, cake: widen backlogs to u64

[Sebastian Moeller]

Hi Eric,


> On Sep 25, 2026, at 15:43, Eric Dumazet <edumazet@google.com> wrote:
> 
> On Fri, Sep 25, 2026 at 3:30 PM Sebastian Moeller <moeller0@gmx.de> wrote:
>> 
>> Hi Eric,
>> 
>> 
>>> On Sep 25, 2026, at 15:03, Eric Dumazet via Cake <cake@lists.bufferbloat.net> wrote:
>>> 
>>> On Fri, Sep 25, 2026 at 1:28 PM Jamal Hadi Salim <jhs@mojatatu.com> wrote:
>>>> 
>>>> On Fri, Sep 25, 2026 at 5:13 AM Eric Dumazet <edumazet@google.com> wrote:
>>>>> 
>>>>> On Fri, Sep 25, 2026 at 10:54 AM Jamal Hadi Salim <jhs@mojatatu.com> wrote:
>>>>>> 
>>>>>> This is a follow-up to commit 8f735d64382d ("net/sched: bound
>>>>>> qdisc_pkt_len to prevent qdisc soft lockup"), which capped
>>>>>> qdisc_pkt_len() at QDISC_PKT_LEN_MAX (1 MiB). That cap bounds the stab
>>>>>> amplifier but leaves the per-flow backlog counter u32:
>>>>>> fq_codel_enqueue() accumulates qdisc_pkt_len(skb) into q->backlogs[idx],
>>>>>> so a flow can still accumulate 4096 packets of 1 MiB each and wrap the
>>>>>> counter mod 2^32. After a wrap, fq_codel_drop() sees a tiny maxbacklog
>>>>>> and drops from an almost-empty flow, and the dequeue-side subtractions
>>>>>> corrupt the counter further.
>>>>>> 
>>>>>> Widen the fq_codel backlogs table, the fat-flow scan (maxbacklog/len) and
>>>>>> the drop threshold to u64. fq_codel is not lockless: every writer runs
>>>>>> under the root qdisc lock, so plain u64 arithmetic keeps the WRITE_ONCE
>>>>>> publish / READ_ONCE-consume pattern. The dump path
>>>>>> (fq_codel_dump_class_stats) stays a lockless stat-only read.
>>>>>> 
>>>>>> CAKE accumulates the same generic qdisc_pkt_len(skb) into its per-flow
>>>>>> b->backlogs[] and per-tin b->tin_backlog and consumes the values for
>>>>>> longest-flow pruning (cake_heapify/cake_heapify_up) and for the shaper
>>>>>> staleness check, so it shares the bug. Widen those counters and the heap
>>>>>> comparison locals to u64; the class/tin stats keep exporting the low 32
>>>>>> bits through the unchanged uAPI fields.
>>>>>> 
>>>>>> Conditions to recreate the bug: CAP_NET_ADMIN in a user namespace;
>>>>>> CONFIG_NET_SCH_FQ_CODEL=y.
>>>>>> 
>>>>>> 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 4200 ecn drop_batch 4096
>>>>>> # hold the tun fd open without reading (IFF_BACKPRESSURE) so the qdisc
>>>>>> # backlog persists, then send at least 4300 packets (the wrap starts
>>>>>> # at 4096 resident; the over-limit drop that reads the wrapped
>>>>>> # threshold fires past the 4200 limit): backlogs[0] wraps at 4096 x
>>>>>> # 1 MiB and the fat-flow threshold reads the wrapped value.
>>>>>> 
>>>>>> With a 1 MiB qdisc_pkt_len cap the counter wraps at 4096 resident
>>>>>> packets. At limit 4200 the first over-limit enqueue (the 4201st) sees a
>>>>>> wrapped 105 MiB (half-backlog threshold 52 MiB, a ~52 packet drop burst),
>>>>>> where the u64 counter sees 4201 MiB (threshold 2100 MiB, a ~2100 packet
>>>>>> drop burst).
>>>>>> 
>>>>>> Reported-by: Sashiko (nipa) <sashiko-bot@kernel.org>
>>>>>> Closes: https://netdev-ai.bots.linux.dev/sashiko/#/patchset/20260818101130.16203-1-jhs@mojatatu.com
>>>>>> Link: https://lore.kernel.org/netdev/20260818101130.16203-1-jhs@mojatatu.com/
>>>>>> Tested-by: hybris <hybris@mojatatu.ai>
>>>>>> Signed-off-by: Jamal Hadi Salim <jhs@mojatatu.com>
>>>>>> ---
>>>>> 
>>>>> This makes no sense.
>>>>> 
>>>> 
>>>> As absurd as it looks that code is reachable ;->
>>>> 
>>>>> These qdisc have been developped to address bufferbloat issues.
>>>>> 
>>>>> Storing 4GB in a qdisc is absolutely insane.
>>>>> 
>>>> 
>>>> The counter wrap is not because we stored 4GB, rather it is because
>>>> "tc .. stab overhead ..." inflates qdisc_pkt_len() for a 64B pkt to
>>>> 1MB. So ~4K packets (put in other words a few "real" KB) makes that
>>>> backlog[0] cross 2^32.
>>> 
>>> Kill this stuff ? Who is still using this, for what reason ?
>> 
>> tc-stab? Same as before, if you need want to model a remote bottleneck with a local traffic shaper tc-stab is the generic solution (off the top of my head I only can enumerate cake as having its own traffic shaper that handles overheads).
>> One could argue that the "virtual" length should be accounted against cake's memlimit or fq-codel's memory_limit somehow...
>> In sane?/typical configurations overhead is expected to stay relatively small, so this would not limit the actual queue size too much, while potentially silencing this issue.
> 
> linux qdisc are in the fast path, for nearly all packets sent over this planet.

Tip of the head to the linux network experts that enabled that and that take care of it being efficient!

> They aleady consume GW of energy.
> 
> Modeling / network emulation should incur zero cost on these
> production grade qdisc.

It is not modeling in a scientific sense (sorry I used inappropriate terminology here), but simply the fact that to shape traffic to avoid filling remote queues one needs to be able to take the properties of that remote queue/interface/link-layer into account.
And that can be surprisingly close by. Last time I looked the kernel on say eth0 added the 14 bytes of ethernet related overhead it handled itself to the packet size on top of the payload (no complaints that makes sense) but that is insufficient to properly traffic shape e.g. the same ethernet interface... (as the relevant ethernet L1-frame overhead contains more bytes, like the FCS, preamble and SFD). And that gets worse with stuff like DSL, cable or fibre modems that are connected via ethernet to a linux router.

> 
> netem could be one answer, I do not know, or a special
> CONFIG_NET_SCHED_EXPENSIVE_EMULATION

Well, tc-stab (or cake's overhead accounting) is already optional, so only those incur the cost that actually use it (and only those users are affected by the reported issue, it took tc-stab to cause the problem and arguably in a configuration that is "insane"). 
I might be trying to explain the internet here to people that make the internet work, so apologies in advance but I want to make this as explicit as I can.
TTraffic shaping without proper overhead accounting will not work as expected (at least if the expectation is that the traffic shaper will honor the set gross shaper rate). For a fixed packet size the lack over overhead accounting can be papered over with reducing the shaper rate, but the amount of the required "over-shaping" depends on packet size (smaller packets require more over-shaping), so generally that is sub optimal, because either the shaper's guarantee is brittle or the over-shaping quite extreme (think the header to payload ration of minimally- and MTU-sized packets).

All I am saying is, we do still have use cases for tc-stab and proper overhead accounting, at least on the leafs of the network like home internet links.


> 
>> 
>> I might be off my rocker, in which has ignore (or preferably enlighten me).

[Cake] Re: [PATCH net-next] net/sched: fq_codel, cake: widen backlogs to u64

[Eric Dumazet]

On Sat, Sep 26, 2026 at 11:43 AM Jamal Hadi Salim <hadi@mojatatu.com> wrote:
> I am working on a v2 that drops at enqueue once the accounted backlog
> crosses  (U32_MAX - QDISC_PKT_LEN_MAX), so no counter can wrap.
> That is Eric's original suggestion which preserves the point you raised.
>
> While looking at this closely for this update i noticed more qdiscs
> which for different reasons also suffer from ((u64)backlog + len <=
> limit idiom.
> So far it's clear from bfifo, gred and plug are the only ones safe
> because their limit is in bytes (as opposed to others which are packet
> counting)
>
> Eric: Unless i hear otherwise from you, the configurable byte ceiling
> you mentioned (a good noun seems to be CONFIG_NET_SCH_BACKLOG_CEILING)
> is a follow-up;

SGTM, thanks Jamal.