[Cake] [PATCH V2 RESEND] net/sched: sch_cake: Fix incorrect qlen reduction in cake_drop

[Cake] [PATCH V2 RESEND] net/sched: sch_cake: Fix incorrect qlen reduction in cake_drop

[Xiang Mei]

In cake_drop(), the function qdisc_tree_reduce_backlog() is called to
decrement the qlen of the qdisc hierarchy. However, it may incorrectly
reduce the qlen when the dropped packet was not enqueued, leading to
a potential null-pointer dereference (e.g., when using qfq sched as
the parent qdisc).

This issue occurs when the caller (cake_enqueue()) returns NET_XMIT_CN,
causing the parent qdisc not to enqueue the current packet, while
qdisc_tree_reduce_backlog() still decrements the backlog.

This patch prevents invalid qlen reduction by verifying that the
dropped packet was actually enqueued before adjusting the backlog.

Fixes: 15de71d06a40 ("net/sched: Make cake_enqueue return NET_XMIT_CN when past buffer_limit")
Signed-off-by: Xiang Mei <xmei5@asu.edu>
---
v2: add missing cc

 net/sched/sch_cake.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

diff --git a/net/sched/sch_cake.c b/net/sched/sch_cake.c
index 32bacfc314c2..3a2ba9dfc22d 100644
--- a/net/sched/sch_cake.c
+++ b/net/sched/sch_cake.c
@@ -1548,7 +1548,7 @@ static int cake_advance_shaper(struct cake_sched_data *q,
 	return len;
 }
 
-static unsigned int cake_drop(struct Qdisc *sch, struct sk_buff **to_free)
+static unsigned int cake_drop(struct Qdisc *sch, struct sk_buff **to_free, u32 current_flow)
 {
 	struct cake_sched_data *q = qdisc_priv(sch);
 	ktime_t now = ktime_get();
@@ -1597,7 +1597,8 @@ static unsigned int cake_drop(struct Qdisc *sch, struct sk_buff **to_free)
 
 	qdisc_drop_reason(skb, sch, to_free, SKB_DROP_REASON_QDISC_OVERLIMIT);
 	sch->q.qlen--;
-	qdisc_tree_reduce_backlog(sch, 1, len);
+	if (likely(current_flow != idx + (tin << 16)))
+		qdisc_tree_reduce_backlog(sch, 1, len);
 
 	cake_heapify(q, 0);
 
@@ -1934,7 +1935,7 @@ static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 
 		while (q->buffer_used > q->buffer_limit) {
 			dropped++;
-			drop_id = cake_drop(sch, to_free);
+			drop_id = cake_drop(sch, to_free, idx + (tin << 16));
 
 			if ((drop_id >> 16) == tin &&
 			    (drop_id & 0xFFFF) == idx)
-- 
2.43.0

[Cake] Re: [PATCH V2 RESEND] net/sched: sch_cake: Fix incorrect qlen reduction in cake_drop

[Xiang Mei]

On Tue, Nov 11, 2025 at 12:27:09AM -0700, Xiang Mei wrote:
> In cake_drop(), the function qdisc_tree_reduce_backlog() is called to
> decrement the qlen of the qdisc hierarchy. However, it may incorrectly
> reduce the qlen when the dropped packet was not enqueued, leading to
> a potential null-pointer dereference (e.g., when using qfq sched as
> the parent qdisc).
> 
> This issue occurs when the caller (cake_enqueue()) returns NET_XMIT_CN,
> causing the parent qdisc not to enqueue the current packet, while
> qdisc_tree_reduce_backlog() still decrements the backlog.
> 
> This patch prevents invalid qlen reduction by verifying that the
> dropped packet was actually enqueued before adjusting the backlog.
> 
> Fixes: 15de71d06a40 ("net/sched: Make cake_enqueue return NET_XMIT_CN when past buffer_limit")
> Signed-off-by: Xiang Mei <xmei5@asu.edu>
> ---
> v2: add missing cc
> 
>  net/sched/sch_cake.c | 7 ++++---
>  1 file changed, 4 insertions(+), 3 deletions(-)
> 
> diff --git a/net/sched/sch_cake.c b/net/sched/sch_cake.c
> index 32bacfc314c2..3a2ba9dfc22d 100644
> --- a/net/sched/sch_cake.c
> +++ b/net/sched/sch_cake.c
> @@ -1548,7 +1548,7 @@ static int cake_advance_shaper(struct cake_sched_data *q,
>  	return len;
>  }
>  
> -static unsigned int cake_drop(struct Qdisc *sch, struct sk_buff **to_free)
> +static unsigned int cake_drop(struct Qdisc *sch, struct sk_buff **to_free, u32 current_flow)
>  {
>  	struct cake_sched_data *q = qdisc_priv(sch);
>  	ktime_t now = ktime_get();
> @@ -1597,7 +1597,8 @@ static unsigned int cake_drop(struct Qdisc *sch, struct sk_buff **to_free)
>  
>  	qdisc_drop_reason(skb, sch, to_free, SKB_DROP_REASON_QDISC_OVERLIMIT);
>  	sch->q.qlen--;
> -	qdisc_tree_reduce_backlog(sch, 1, len);
> +	if (likely(current_flow != idx + (tin << 16)))
> +		qdisc_tree_reduce_backlog(sch, 1, len);
>  
>  	cake_heapify(q, 0);
>  
> @@ -1934,7 +1935,7 @@ static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch,
>  
>  		while (q->buffer_used > q->buffer_limit) {
>  			dropped++;
> -			drop_id = cake_drop(sch, to_free);
> +			drop_id = cake_drop(sch, to_free, idx + (tin << 16));
>  
>  			if ((drop_id >> 16) == tin &&
>  			    (drop_id & 0xFFFF) == idx)
> -- 
> 2.43.0
>

This is a resend patch since I didn't cc the correct maintainer.

The POC of the fixed bug is as follows (NET_ADMIN is required):

```sh
tc qdisc add dev lo handle 1: root qfq
tc class add dev lo parent 1: classid 1:1 qfq maxpkt 1024
tc qdisc add dev lo parent 1:1 handle 2: cake memlimit 9
tc filter add dev lo protocol ip parent 1: prio 1 u32 \
  match ip protocol 1 0xff \
  flowid 1:1
ping -I lo -f -c1 -s64 -W0.001 127.0.0.1
tc qdisc replace dev lo parent 1:1 handle 3: netem delay 0ms
ping -I lo -f -c1 -s64 -W0.001 127.0.0.1
```

Please enable the following configs to support necessary qdiscs and filters:
```config
./scripts/config -e CONFIG_NET_SCH_QFQ \
-e CONFIG_NET_SCH_CAKE -e CONFIG_NET_SCH_NETEM \
-e CONFIG_NET_CLS_U32
```

The intended crash is also attached for your refference
```log
[   13.816429] BUG: kernel NULL pointer dereference, address: 0000000000000048
[   13.818414] #PF: supervisor read access in kernel mode
[   13.819946] #PF: error_code(0x0000) - not-present page
[   13.821466] PGD 0 P4D 0
[   13.822262] Oops: Oops: 0000 [#1] PREEMPT SMP NOPTI
[   13.823785] CPU: 1 UID: 0 PID: 226 Comm: ping Not tainted 6.12.57 #4
[   13.825583] Hardware name: QEMU Ubuntu 24.04 PC (i440FX + PIIX, 1996), BIOS 1.16.3-debian-1.16.3-2 04/01/2014
[   13.827700] RIP: 0010:qfq_dequeue+0x166/0x3b0
[   13.828627] Code: 59 48 0f af ce 48 89 43 10 48 89 de 4c 89 ef 48 01 c1 48 89 4b 18 e8 99 f0 ff ff 4c 89 ef e8 c1 f6 ff ff 48 89 85 b8 01 8
[   13.831956] RSP: 0018:ffffc900004c3a68 EFLAGS: 00010246
[   13.832889] RAX: 0000000000000000 RBX: ffff888102b9d280 RCX: 0000000000000000
[   13.834230] RDX: 0000000000000000 RSI: 0000001a80000000 RDI: ffff888100a1e180
[   13.835530] RBP: ffff888100a1e000 R08: 0000000000000001 R09: 0000000000000000
[   13.836800] R10: 0000000000000000 R11: 0000000000000000 R12: ffff888102b9d2c8
[   13.838069] R13: ffff888100a1e180 R14: ffff8881029a3e00 R15: ffff888100a1e000
[   13.839340] FS:  00007f91c48f4c40(0000) GS:ffff88811c500000(0000) knlGS:0000000000000000
[   13.840742] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[   13.841781] CR2: 0000000000000048 CR3: 0000000102ad8000 CR4: 0000000000350ef0
[   13.843049] Call Trace:
[   13.843568]  <TASK>
[   13.843972]  __qdisc_run+0x87/0x570
[   13.844662]  __dev_queue_xmit+0x55b/0xe10
[   13.845427]  ? sock_alloc_send_pskb+0x1fb/0x230
```

The patched code passed related self-test (qdiscs/cake.json):
```log
1..21
ok 1 1212 - Create CAKE with default setting
ok 2 3281 - Create CAKE with bandwidth limit
ok 3 c940 - Create CAKE with autorate-ingress flag
ok 4 2310 - Create CAKE with rtt time
ok 5 2385 - Create CAKE with besteffort flag
ok 6 a032 - Create CAKE with diffserv8 flag
ok 7 2349 - Create CAKE with diffserv4 flag
ok 8 8472 - Create CAKE with flowblind flag
ok 9 2341 - Create CAKE with dsthost and nat flag
ok 10 5134 - Create CAKE with wash flag
ok 11 2302 - Create CAKE with flowblind and no-split-gso flag
ok 12 0768 - Create CAKE with dual-srchost and ack-filter flag
ok 13 0238 - Create CAKE with dual-dsthost and ack-filter-aggressive flag
ok 14 6572 - Create CAKE with memlimit and ptm flag
ok 15 2436 - Create CAKE with fwmark and atm flag
ok 16 3984 - Create CAKE with overhead and mpu
ok 17 5421 - Create CAKE with conservative and ingress flag
ok 18 6854 - Delete CAKE with conservative and ingress flag
ok 19 2342 - Replace CAKE with mpu
ok 20 2313 - Change CAKE with mpu
ok 21 4365 - Show CAKE class
```

Feel free to ask any questions about this bug/patch.

Thanks,
Xiang

[Cake] Re: [PATCH V2 RESEND] net/sched: sch_cake: Fix incorrect qlen reduction in cake_drop

[Toke Høiland-Jørgensen]

Xiang Mei <xmei5@asu.edu> writes:

> In cake_drop(), the function qdisc_tree_reduce_backlog() is called to
> decrement the qlen of the qdisc hierarchy. However, it may incorrectly
> reduce the qlen when the dropped packet was not enqueued, leading to
> a potential null-pointer dereference (e.g., when using qfq sched as
> the parent qdisc).
>
> This issue occurs when the caller (cake_enqueue()) returns NET_XMIT_CN,
> causing the parent qdisc not to enqueue the current packet, while
> qdisc_tree_reduce_backlog() still decrements the backlog.
>
> This patch prevents invalid qlen reduction by verifying that the
> dropped packet was actually enqueued before adjusting the backlog.
>
> Fixes: 15de71d06a40 ("net/sched: Make cake_enqueue return NET_XMIT_CN when past buffer_limit")
> Signed-off-by: Xiang Mei <xmei5@asu.edu>

Thank you for the patch! I think the issue is valid, but I don't think
the fix is quite right - see below.

Also, this should probably go through netdev? Please include
netdev@vger.kernel.org and add a 'net' tag to the patch subject when you
respin (so it'll look like [PATCH net v3]).

> ---
> v2: add missing cc
>
>  net/sched/sch_cake.c | 7 ++++---
>  1 file changed, 4 insertions(+), 3 deletions(-)
>
> diff --git a/net/sched/sch_cake.c b/net/sched/sch_cake.c
> index 32bacfc314c2..3a2ba9dfc22d 100644
> --- a/net/sched/sch_cake.c
> +++ b/net/sched/sch_cake.c
> @@ -1548,7 +1548,7 @@ static int cake_advance_shaper(struct cake_sched_data *q,
>  	return len;
>  }
>  
> -static unsigned int cake_drop(struct Qdisc *sch, struct sk_buff **to_free)
> +static unsigned int cake_drop(struct Qdisc *sch, struct sk_buff **to_free, u32 current_flow)
>  {
>  	struct cake_sched_data *q = qdisc_priv(sch);
>  	ktime_t now = ktime_get();
> @@ -1597,7 +1597,8 @@ static unsigned int cake_drop(struct Qdisc *sch, struct sk_buff **to_free)
>  
>  	qdisc_drop_reason(skb, sch, to_free, SKB_DROP_REASON_QDISC_OVERLIMIT);
>  	sch->q.qlen--;
> -	qdisc_tree_reduce_backlog(sch, 1, len);
> +	if (likely(current_flow != idx + (tin << 16)))
> +		qdisc_tree_reduce_backlog(sch, 1, len);

Since cake_drop() is called in a loop, the number of bytes/packets
dropped may not match the packet coming in. So we can't just skip this.

I think the simplest would probably be to move the
qdisc_tree_reduce_backlog() out of cake_drop entirely, and then
replicate the logic from fq_codel in the caller. I.e., the bit where it
saves the qlen and backlog before dropping and calls
qdisc_tree_reduce_backlog() once after. So we'll end up with something
like:

prev_backlog = sch->qstats.backlog;
prev_qlen = sch->q.qlen;
while (q->buffer_used > q->buffer_limit) {
/*...*/
}
prev_qlen -= sch->q.qlen;
prev_backlog -= sch->qstats.backlog;
if (same_flow)
   qdisc_tree_reduce_backlog(sch, prev_qlen - 1,
				  prev_backlog - pkt_len);
   return NET_XMIT_CN;
}
qdisc_tree_reduce_backlog(sch, prev_qlen,b
				  prev_backlog);

/* etc */

-Toke