[PATCH net v2] net/sched: sch_netem: prevent packet length underflow with negative overhead

[PATCH net v2] net/sched: sch_netem: prevent packet length underflow with negative overhead

[Bui Viet Dung]

packet_time_ns() calculates transmission time for netem rate shaping.
It adds q->packet_overhead (signed 32-bit integer) to len (unsigned
64-bit integer).

When userspace configures a negative packet overhead (via
TCA_NETEM_RATE packet_overhead attribute) and an enqueued packet's
length is smaller than the absolute overhead, (s64)len +
q->packet_overhead is non-positive. Because len is u64, the addition
wraps into an astronomical value (~2^64 - 1). When multiplied by
NSEC_PER_SEC and divided by q->rate, the calculated delay spans days,
causing enqueued packets to be frozen in the qdisc indefinitely and
stalling transmission.

A similar underflow can occur in cell length calculation when
(q->cell_size + q->cell_overhead) is non-positive.

Furthermore, computing cell_len in s64 prevents sign corruption if
cell_size >= 0x80000000 or if cell_size + cell_overhead exceeds INT_MAX.
Computing the final transmission time with mul_u64_u64_div_u64() and
clamping to S64_MAX avoids 64-bit multiplication overflow and prevents
the resulting delay from turning negative in s64 delay arithmetic.

Return 0 delay if effective packet length or cell length is non-positive
so that non-positive effective packet lengths experience no rate
throttling rather than freezing transmission.

The issue was discovered via manual code audit of sch_netem.c and
verified on a test VM using 'tc qdisc add dev lo root netem rate 100Mbit
overhead -100', which caused immediate backlog stalls on small packets.

Fixes: 7bc0f28c7a0c ("netem: rate extension")
Cc: stable@vger.kernel.org
Signed-off-by: Bui Viet Dung <dungvn2345@gmail.com>
---
Link to v1: https://lore.kernel.org/netdev/20261008035656.330667-1-dungvn2345@gmail.com/

v1 -> v2:
- Calculate cell_len as s64 to avoid sign corruption when cell_size >= 0x80000000 or upon s32 overflow (Sashiko AI review).
- Use mul_u64_u64_div_u64() to prevent u64 multiplication overflow with large cell configurations, and clamp result to S64_MAX to prevent negative s64 delays (Sashiko AI review).
- Reword commit message: remove inaccurate comparisons to sch_cake and sch_tbf; clarify the clamping policy for non-positive effective length (Sashiko AI review).
- Include <linux/math64.h>.

 net/sched/sch_netem.c | 14 ++++++++++++--
 1 file changed, 12 insertions(+), 2 deletions(-)

diff --git a/net/sched/sch_netem.c b/net/sched/sch_netem.c
index 8a1b89a289d8..3eccdc93c0b6 100644
--- a/net/sched/sch_netem.c
+++ b/net/sched/sch_netem.c
@@ -21,6 +21,7 @@
 #include <linux/rtnetlink.h>
 #include <linux/reciprocal_div.h>
 #include <linux/rbtree.h>
+#include <linux/math64.h>
 
 #include <net/gso.h>
 #include <net/netlink.h>
@@ -366,17 +367,26 @@ static s64 tabledist(s64 mu, s32 sigma,
 
 static u64 packet_time_ns(u64 len, const struct netem_sched_data *q)
 {
+	u64 d;
+
+	if ((s64)len + q->packet_overhead <= 0)
+		return 0;
+
 	len += q->packet_overhead;
 
 	if (q->cell_size) {
 		u32 cells = reciprocal_divide(len, q->cell_size_reciprocal);
+		s64 cell_len = (s64)q->cell_size + q->cell_overhead;
 
 		if (len > cells * q->cell_size)	/* extra cell needed for remainder */
 			cells++;
-		len = cells * (q->cell_size + q->cell_overhead);
+		if (cell_len <= 0)
+			return 0;
+		len = (u64)cells * cell_len;
 	}
 
-	return div64_u64(len * NSEC_PER_SEC, q->rate);
+	d = mul_u64_u64_div_u64(len, NSEC_PER_SEC, q->rate);
+	return min_t(u64, d, S64_MAX);
 }
 
 static void tfifo_reset(struct Qdisc *sch)
-- 
2.43.0

[syzbot ci] Re: net/sched: sch_netem: prevent packet length underflow with negative overhead

[syzbot ci]

syzbot ci has tested the following series

[v2] net/sched: sch_netem: prevent packet length underflow with negative overhead
https://lore.kernel.org/all/20261012044322.503949-1-dungvn2345@gmail.com
* [PATCH net v2] net/sched: sch_netem: prevent packet length underflow with negative overhead

and found the following issue:
divide error in netem_enqueue

Full report is available here:
https://ci.syzbot.org/series/eff5cc04-13f7-4a28-9b83-b6e0de530bc2

***

divide error in netem_enqueue

tree:      net
URL:       https://kernel.googlesource.com/pub/scm/linux/kernel/git/netdev/net.git
base:      af32da41b0327b9c6a37856ba82b6760d6c8d10e
arch:      amd64
compiler:  Debian clang version 22.1.8 (++20260613092233+e80beda6e255-1~exp1~20260613092250.77), Debian LLD 22.1.8
config:    https://ci.syzbot.org/builds/bf12d8a1-2cda-46fc-9150-cadd809b1c71/config

Oops: divide error: 0000 [#1] SMP KASAN PTI
CPU: 0 UID: 0 PID: 17390 Comm: syz.0.2912 Not tainted syzkaller #0 PREEMPT(full) 
Hardware name: QEMU Standard PC (Q35 + ICH9, 2009), BIOS 1.16.2-debian-1.16.2-1 04/01/2014
RIP: 0010:netem_enqueue+0x20f6/0x3300
Code: 8b 74 24 38 48 8b 44 24 50 42 80 3c 28 00 74 08 4c 89 f7 e8 cc f4 51 f8 49 8b 0e 4c 89 f8 48 f7 25 b7 9c 8b 04 48 89 4c 24 78 <48> f7 74 24 78 48 b9 ff ff ff ff ff ff ff 7f 48 39 c8 48 0f 42 c8
RSP: 0018:ffffc900082cf4b0 EFLAGS: 00010a07
RAX: 3599740d73380000 RBX: 0000005c44b22572 RCX: 000000000000002c
RDX: 0000000000000077 RSI: 00000000000001ed RDI: 00000000000001ee
RBP: ffff88810e973000 R08: ffffffff917a717f R09: 1ffffffff22f4e2f
R10: dffffc0000000000 R11: ffffffff81776d40 R12: ffff888026e62330
R13: dffffc0000000000 R14: ffff88810e9732b0 R15: 0000020000176c00
FS:  00007f87167196c0(0000) GS:ffff88818c4bf000(0000) knlGS:0000000000000000
CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
CR2: 00007f8716718ff8 CR3: 000000002756e000 CR4: 00000000000006f0
Call Trace:
 <TASK>
 netem_enqueue+0x16f1/0x3300
 dev_qdisc_enqueue+0x4e/0x260
 __dev_queue_xmit+0x1b6c/0x3920
 packet_sendmsg+0x3f11/0x51a0
 sock_sendmsg_nosec+0x13a/0x180
 __sys_sendto+0x408/0x5a0
 __x64_sys_sendto+0xde/0x100
 do_syscall_64+0x166/0x520
 entry_SYSCALL_64_after_hwframe+0x77/0x7f
RIP: 0033:0x7f871579e1d9
Code: ff c3 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 44 00 00 48 89 f8 48 89 f7 48 89 d6 48 89 ca 4d 89 c2 4d 89 c8 4c 8b 4c 24 08 0f 05 <48> 3d 01 f0 ff ff 73 01 c3 48 c7 c1 e8 ff ff ff f7 d8 64 89 01 48
RSP: 002b:00007f8716719028 EFLAGS: 00000246 ORIG_RAX: 000000000000002c
RAX: ffffffffffffffda RBX: 00007f8715a25fa0 RCX: 00007f871579e1d9
RDX: 00000000000005dc RSI: 0000200000000280 RDI: 0000000000000009
RBP: 00007f8715835888 R08: 0000200000000140 R09: 0000000000000014
R10: 0000000000004009 R11: 0000000000000246 R12: 0000000000000000
R13: 00007f8715a26038 R14: 00007f8715a25fa0 R15: 00007ffc85273198
 </TASK>
Modules linked in:
---[ end trace 0000000000000000 ]---
RIP: 0010:netem_enqueue+0x20f6/0x3300
Code: 8b 74 24 38 48 8b 44 24 50 42 80 3c 28 00 74 08 4c 89 f7 e8 cc f4 51 f8 49 8b 0e 4c 89 f8 48 f7 25 b7 9c 8b 04 48 89 4c 24 78 <48> f7 74 24 78 48 b9 ff ff ff ff ff ff ff 7f 48 39 c8 48 0f 42 c8
RSP: 0018:ffffc900082cf4b0 EFLAGS: 00010a07
RAX: 3599740d73380000 RBX: 0000005c44b22572 RCX: 000000000000002c
RDX: 0000000000000077 RSI: 00000000000001ed RDI: 00000000000001ee
RBP: ffff88810e973000 R08: ffffffff917a717f R09: 1ffffffff22f4e2f
R10: dffffc0000000000 R11: ffffffff81776d40 R12: ffff888026e62330
R13: dffffc0000000000 R14: ffff88810e9732b0 R15: 0000020000176c00
FS:  00007f87167196c0(0000) GS:ffff88818c4bf000(0000) knlGS:0000000000000000
CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
CR2: 00007f8716718ff8 CR3: 000000002756e000 CR4: 00000000000006f0


***

If these findings have caused you to resend the series or submit a
separate fix, please add the following tag to your commit message:
  Tested-by: syzbot@syzkaller.appspotmail.com

---
This report is generated by a bot. It may contain errors.
syzbot ci engineers can be reached at syzkaller@googlegroups.com.

To test a fix for this bug, please reply with `#syz test`
(on a separate line) and attach the patch to the email.

Notes:
- The patch will be applied on top of the tested series (as an
  incremental fix).
- To test a new version of the whole series, please send it directly
  to syzbot@lists.linux.dev.
- Arguments like custom git repos and branches are not supported.

Re: [PATCH net v2] net/sched: sch_netem: prevent packet length underflow with negative overhead

[netdev-bot+sashiko]

Thank you for your contribution! Sashiko AI review found 2 potential
issue(s) to consider.

Critical: 1 · High: 0 · Medium: 1 · Low: 0

If you believe none of the issues are legitimate, please reply to each
issue of Medium severity or higher and explain why the AI is wrong.
If any of them are legitimate and you plan to respin, please let patchwork
know by including "pw-bot: cr" as a separate line at the end of your reply
(one such reply per series is enough).

- [Critical] In packet_time_ns() (net/sched/sch_netem.c), the patch swaps
  `div64_u64(len * NSEC_PER_SEC, q->rate)` for `mul_u64_u64_div_u64(len,…
- [Medium] The commit message says clamping packet_time_ns() to S64_MAX
  "prevents the resulting delay from turning negative in s64 delay…

--

net/sched: sch_netem: prevent packet length underflow with negative overhead

This patch makes packet_time_ns() return 0 when the effective packet
length or the cell length is non-positive. A negative packet_overhead
then no longer wraps len to a huge value and stalls the qdisc. The patch
also computes cell_len as s64, uses mul_u64_u64_div_u64() for the final
calculation, and clamps the result to S64_MAX.

> diff --git a/net/sched/sch_netem.c b/net/sched/sch_netem.c
> index 8a1b89a289d8f..3eccdc93c0b6b 100644
> --- a/net/sched/sch_netem.c
> +++ b/net/sched/sch_netem.c

[ ... ]

> @@ -366,17 +367,26 @@ static s64 tabledist(s64 mu, s32 sigma,
>  
>  static u64 packet_time_ns(u64 len, const struct netem_sched_data *q)
>  {
> +	u64 d;
> +
> +	if ((s64)len + q->packet_overhead <= 0)
> +		return 0;
> +
>  	len += q->packet_overhead;
>  
>  	if (q->cell_size) {
>  		u32 cells = reciprocal_divide(len, q->cell_size_reciprocal);
> +		s64 cell_len = (s64)q->cell_size + q->cell_overhead;
>  
>  		if (len > cells * q->cell_size)	/* extra cell needed for remainder */
>  			cells++;
> -		len = cells * (q->cell_size + q->cell_overhead);
> +		if (cell_len <= 0)
> +			return 0;
> +		len = (u64)cells * cell_len;
>  	}
>  
> -	return div64_u64(len * NSEC_PER_SEC, q->rate);
> +	d = mul_u64_u64_div_u64(len, NSEC_PER_SEC, q->rate);

[Severity: Critical]
Can this trap on x86-64 before the S64_MAX clamp is reached?

mul_u64_u64_div_u64() expands to mul_u64_add_u64_div_u64(). On x86-64,
arch/x86/include/asm/div64.h implements that as a plain mulq followed by
divq:

/*
 * Will generate an #DE when the result doesn't fit u64, could fix with an
 * __ex_table[] entry when it becomes an issue.
 */
static inline u64 mul_u64_add_u64_div_u64(u64 rax, u64 mul, u64 add, u64 div)
{
	...
	asm ("divq %[div]" : "+a" (rax), "+d" (rdx) : [div] "rm" (div));
	...
}

include/linux/math64.h also says "Architecture specific code may trap on
zero or overflow". So this code can't depend on the saturating behaviour
of the generic version.

The new s64 cell_len also makes the overflow much easier to hit. The old
expression cells * (q->cell_size + q->cell_overhead) was a u32 product,
so len * NSEC_PER_SEC stayed within u64. With len = (u64)cells * cell_len,
len can now get close to 2^62.

get_rate() copies rate, packet_overhead, cell_size and cell_overhead from
TCA_NETEM_RATE without range checks. For example, with rate=1,
cell_size=1, cell_overhead=INT_MAX and a 100 byte packet:

  cell_len                 = 2^31
  len                      = 100 * 2^31   ~= 2.1e11
  len * NSEC_PER_SEC / 1   ~= 2.1e20      > U64_MAX

The divq would then raise #DE in this path:

netem_enqueue()
  packet_time_ns()
    mul_u64_u64_div_u64()
      mul_u64_add_u64_div_u64()   /* divq */

This runs under the qdisc root lock, possibly in softirq context. The
first packet enqueued would oops the kernel. Triggering it only needs
CAP_NET_ADMIN in the netns, and unprivileged user namespaces can provide
that.

If packet_overhead=INT_MAX is also set, len is about 4.6e18. Any rate
below roughly 250 MB/s then traps.

The commit message says:

    Computing the final transmission time with mul_u64_u64_div_u64() and
    clamping to S64_MAX avoids 64-bit multiplication overflow

Could the value be saturated before the helper is called? One option is
to return S64_MAX when div64_u64(len, q->rate) >= div_u64(S64_MAX,
NSEC_PER_SEC). Another is for get_rate()/netem_change() to reject rate and
cell combinations that can overflow.

> +	return min_t(u64, d, S64_MAX);

[Severity: Medium]
The commit message also says the clamp "prevents the resulting delay from
turning negative in s64 delay arithmetic". Is that true for the caller?

The clamp only limits the value that packet_time_ns() returns. In
netem_enqueue() that value is added to a delay that may already be
positive. The result is then added to a now that may already be a
deadline far in the future:

net/sched/sch_netem.c:netem_enqueue() {
    ...
			if (last) {
				...
				delay -= last->time_to_send - now;
				delay = max_t(s64, 0, delay);
				now = last->time_to_send;
			}

			delay += packet_time_ns(qdisc_pkt_len(skb), q);
		}

		cb->time_to_send = now + delay;
    ...
}

validate_time() only checks that the TCA_NETEM_LATENCY64 latency is not
negative, so delay can already be large before this addition. Adding a
result close to S64_MAX to any positive delay wraps it negative.

The absolute deadline can wrap even with zero latency. Take
packet_overhead=0, cell_size=1, cell_overhead=INT_MAX, rate=8 and a 64
byte packet. The quotient is about 1.7e19, which fits in u64 and gets
clamped to S64_MAX:

  packet 1: time_to_send = T + S64_MAX
  packet 2: now = T + S64_MAX
            time_to_send = T + 2 * S64_MAX  ~= T - 2

tfifo_enqueue() would sort packet 2 ahead of packet 1, and
netem_dequeue() would treat it as already due. The packet skips rate
shaping and goes out of order.

Should netem_enqueue() saturate the accumulated delay and
cb->time_to_send as well, instead of only the per-packet interval?

>  }
>  
>  static void tfifo_reset(struct Qdisc *sch)

-- 
Sashiko AI review · https://netdev-ai.bots.linux.dev/sashiko/#/patchset/20261012044322.503949-1-dungvn2345%40gmail.com

Re: [PATCH net v2] net/sched: sch_netem: prevent packet length underflow with negative overhead

[Bui Viet Dung]

Hi,

Thanks for the detailed review. Both points are valid and critical:

1. mul_u64_u64_div_u64() on x86-64 uses 'divq' without overflow handling,
   which raises a #DE divide exception when (len * NSEC_PER_SEC) / rate
   overflows u64.
2. Returning S64_MAX can overflow the subsequent 'now + delay' addition in
   netem_enqueue().

I will retract v2 and prepare a proper v3.

pw-bot: cr