[v5.15] possible deadlock in trie_delete_elem

[syzbot]

Hello,

syzbot found the following issue on:

HEAD commit: b95c01af2113 Linux 5.15.152
git tree: linux-5.15.y
console output: https://syzkaller.appspot.com/x/log.txt?x=1246b091180000
kernel config: https://syzkaller.appspot.com/x/.config?x=b26cb65e5b8ad5c7
dashboard link: https://syzkaller.appspot.com/bug?extid=c361763297bd80b2cc11
compiler: Debian clang version 15.0.6, GNU ld (GNU Binutils for Debian) 2.40

Unfortunately, I don't have any reproducer for this issue yet.

Downloadable assets:
disk image: https://storage.googleapis.com/syzbot-assets/2fc98856fcae/disk-b95c01af.raw.xz
vmlinux: https://storage.googleapis.com/syzbot-assets/3186db0dfe08/vmlinux-b95c01af.xz
kernel image: https://storage.googleapis.com/syzbot-assets/0df136a3e808/bzImage-b95c01af.xz

IMPORTANT: if you fix the issue, please add the following tag to the commit:
Reported-by: syzbot+c36176...@syzkaller.appspotmail.com

======================================================
WARNING: possible circular locking dependency detected
5.15.152-syzkaller #0 Not tainted
------------------------------------------------------
syz-executor.1/19925 is trying to acquire lock:
ffff88802de635b8 (&trie->lock){....}-{2:2}, at: trie_delete_elem+0x90/0x690 kernel/bpf/lpm_trie.c:450

but task is already holding lock:
ffff8880b9a3a318 (&rq->__lock){-.-.}-{2:2}, at: raw_spin_rq_lock_nested+0x26/0x140 kernel/sched/core.c:475

which lock already depends on the new lock.


the existing dependency chain (in reverse order) is:

-> #5 (&rq->__lock){-.-.}-{2:2}:
lock_acquire+0x1db/0x4f0 kernel/locking/lockdep.c:5623
_raw_spin_lock_nested+0x2d/0x40 kernel/locking/spinlock.c:368
raw_spin_rq_lock_nested+0x26/0x140 kernel/sched/core.c:475
raw_spin_rq_lock kernel/sched/sched.h:1326 [inline]
rq_lock kernel/sched/sched.h:1621 [inline]
task_fork_fair+0x5d/0x350 kernel/sched/fair.c:11480
sched_cgroup_fork+0x2d3/0x330 kernel/sched/core.c:4466
copy_process+0x224a/0x3ef0 kernel/fork.c:2320
kernel_clone+0x210/0x960 kernel/fork.c:2604
kernel_thread+0x168/0x1e0 kernel/fork.c:2656
rest_init+0x21/0x330 init/main.c:703
start_kernel+0x48c/0x535 init/main.c:1137
secondary_startup_64_no_verify+0xb1/0xbb

-> #4 (&p->pi_lock){-.-.}-{2:2}:
lock_acquire+0x1db/0x4f0 kernel/locking/lockdep.c:5623
__raw_spin_lock_irqsave include/linux/spinlock_api_smp.h:110 [inline]
_raw_spin_lock_irqsave+0xd1/0x120 kernel/locking/spinlock.c:162
try_to_wake_up+0xae/0x1300 kernel/sched/core.c:4030
__wake_up_common+0x2a0/0x4e0 kernel/sched/wait.c:108
__wake_up_common_lock kernel/sched/wait.c:138 [inline]
__wake_up+0x112/0x1c0 kernel/sched/wait.c:157
tty_port_default_wakeup+0xa8/0x100 drivers/tty/tty_port.c:51
serial8250_tx_chars+0x60d/0x800 drivers/tty/serial/8250/8250_port.c:1834
serial8250_handle_irq+0x505/0x600 drivers/tty/serial/8250/8250_port.c:1930
serial8250_default_handle_irq+0xc8/0x1e0 drivers/tty/serial/8250/8250_port.c:1947
serial8250_interrupt+0xa1/0x1e0 drivers/tty/serial/8250/8250_core.c:127
__handle_irq_event_percpu+0x292/0xa70 kernel/irq/handle.c:156
handle_irq_event_percpu kernel/irq/handle.c:196 [inline]
handle_irq_event+0xff/0x2b0 kernel/irq/handle.c:213
handle_edge_irq+0x245/0xbf0 kernel/irq/chip.c:822
generic_handle_irq_desc include/linux/irqdesc.h:158 [inline]
handle_irq arch/x86/kernel/irq.c:231 [inline]
__common_interrupt+0xd7/0x1f0 arch/x86/kernel/irq.c:250
common_interrupt+0x9f/0xc0 arch/x86/kernel/irq.c:240
asm_common_interrupt+0x22/0x40 arch/x86/include/asm/idtentry.h:629
__sanitizer_cov_trace_cmp8+0x4/0x80 kernel/kcov.c:264
number+0x2a5/0xf80 lib/vsprintf.c:494
vsnprintf+0x12b6/0x1c70 lib/vsprintf.c:2877
seq_vprintf fs/seq_file.c:407 [inline]
seq_printf+0x16e/0x260 fs/seq_file.c:422
show_cpuinfo+0x8d6/0xd10 arch/x86/kernel/cpu/proc.c:137
seq_read_iter+0x43a/0xd10 fs/seq_file.c:230
call_read_iter include/linux/fs.h:2142 [inline]
new_sync_read fs/read_write.c:404 [inline]
vfs_read+0xa9f/0xe10 fs/read_write.c:485
ksys_read+0x1a2/0x2c0 fs/read_write.c:623
do_syscall_x64 arch/x86/entry/common.c:50 [inline]
do_syscall_64+0x3d/0xb0 arch/x86/entry/common.c:80
entry_SYSCALL_64_after_hwframe+0x61/0xcb

-> #3 (&tty->write_wait){-...}-{2:2}:
lock_acquire+0x1db/0x4f0 kernel/locking/lockdep.c:5623
__raw_spin_lock_irqsave include/linux/spinlock_api_smp.h:110 [inline]
_raw_spin_lock_irqsave+0xd1/0x120 kernel/locking/spinlock.c:162
__wake_up_common_lock kernel/sched/wait.c:137 [inline]
__wake_up+0xf5/0x1c0 kernel/sched/wait.c:157
tty_port_default_wakeup+0xa8/0x100 drivers/tty/tty_port.c:51
serial8250_tx_chars+0x60d/0x800 drivers/tty/serial/8250/8250_port.c:1834
serial8250_handle_irq+0x505/0x600 drivers/tty/serial/8250/8250_port.c:1930
serial8250_default_handle_irq+0xc8/0x1e0 drivers/tty/serial/8250/8250_port.c:1947
serial8250_interrupt+0xa1/0x1e0 drivers/tty/serial/8250/8250_core.c:127
__handle_irq_event_percpu+0x292/0xa70 kernel/irq/handle.c:156
handle_irq_event_percpu kernel/irq/handle.c:196 [inline]
handle_irq_event+0xff/0x2b0 kernel/irq/handle.c:213
handle_edge_irq+0x245/0xbf0 kernel/irq/chip.c:822
generic_handle_irq_desc include/linux/irqdesc.h:158 [inline]
handle_irq arch/x86/kernel/irq.c:231 [inline]
__common_interrupt+0xd7/0x1f0 arch/x86/kernel/irq.c:250
common_interrupt+0x9f/0xc0 arch/x86/kernel/irq.c:240
asm_common_interrupt+0x22/0x40 arch/x86/include/asm/idtentry.h:629
__raw_spin_unlock_irqrestore include/linux/spinlock_api_smp.h:161 [inline]
_raw_spin_unlock_irqrestore+0xd4/0x130 kernel/locking/spinlock.c:194
spin_unlock_irqrestore include/linux/spinlock.h:418 [inline]
uart_write+0x6af/0x930 drivers/tty/serial/serial_core.c:590
process_output_block drivers/tty/n_tty.c:592 [inline]
n_tty_write+0xd7e/0x1280 drivers/tty/n_tty.c:2339
do_tty_write drivers/tty/tty_io.c:1038 [inline]
file_tty_write+0x561/0x920 drivers/tty/tty_io.c:1110
call_write_iter include/linux/fs.h:2148 [inline]
new_sync_write fs/read_write.c:507 [inline]
vfs_write+0xacf/0xe50 fs/read_write.c:594
ksys_write+0x1a2/0x2c0 fs/read_write.c:647
do_syscall_x64 arch/x86/entry/common.c:50 [inline]
do_syscall_64+0x3d/0xb0 arch/x86/entry/common.c:80
entry_SYSCALL_64_after_hwframe+0x61/0xcb

-> #2 (&port_lock_key){-...}-{2:2}:
lock_acquire+0x1db/0x4f0 kernel/locking/lockdep.c:5623
__raw_spin_lock_irqsave include/linux/spinlock_api_smp.h:110 [inline]
_raw_spin_lock_irqsave+0xd1/0x120 kernel/locking/spinlock.c:162
serial8250_console_write+0x19d/0x1180 drivers/tty/serial/8250/8250_port.c:3360
console_unlock+0xced/0x12b0 kernel/printk/printk.c:2738
vprintk_emit+0xbf/0x150 kernel/printk/printk.c:2268
_printk+0xd1/0x111 kernel/printk/printk.c:2293
register_console+0x68c/0x970 kernel/printk/printk.c:3078
univ8250_console_init+0x41/0x43 drivers/tty/serial/8250/8250_core.c:690
console_init+0x18c/0x652 kernel/printk/printk.c:3178
start_kernel+0x301/0x535 init/main.c:1073
secondary_startup_64_no_verify+0xb1/0xbb

-> #1 (console_owner){-...}-{0:0}:
lock_acquire+0x1db/0x4f0 kernel/locking/lockdep.c:5623
console_lock_spinning_enable+0x51/0x60 kernel/printk/printk.c:1805
console_unlock+0xa47/0x12b0 kernel/printk/printk.c:2735
vprintk_emit+0xbf/0x150 kernel/printk/printk.c:2268
_printk+0xd1/0x111 kernel/printk/printk.c:2293
debug_objects_oom+0xb4/0x370 lib/debugobjects.c:472
debug_object_activate+0x42d/0x4e0 lib/debugobjects.c:698
debug_rcu_head_queue kernel/rcu/rcu.h:176 [inline]
kvfree_call_rcu+0xb6/0x8a0 kernel/rcu/tree.c:3587
trie_update_elem+0x808/0xc00 kernel/bpf/lpm_trie.c:384
bpf_map_update_value+0x5d7/0x6c0 kernel/bpf/syscall.c:221
generic_map_update_batch+0x54d/0x8b0 kernel/bpf/syscall.c:1399
bpf_map_do_batch+0x4d0/0x620
__sys_bpf+0x55c/0x670
__do_sys_bpf kernel/bpf/syscall.c:4733 [inline]
__se_sys_bpf kernel/bpf/syscall.c:4731 [inline]
__x64_sys_bpf+0x78/0x90 kernel/bpf/syscall.c:4731
do_syscall_x64 arch/x86/entry/common.c:50 [inline]
do_syscall_64+0x3d/0xb0 arch/x86/entry/common.c:80
entry_SYSCALL_64_after_hwframe+0x61/0xcb

-> #0 (&trie->lock){....}-{2:2}:
check_prev_add kernel/locking/lockdep.c:3053 [inline]
check_prevs_add kernel/locking/lockdep.c:3172 [inline]
validate_chain+0x1649/0x5930 kernel/locking/lockdep.c:3788
__lock_acquire+0x1295/0x1ff0 kernel/locking/lockdep.c:5012
lock_acquire+0x1db/0x4f0 kernel/locking/lockdep.c:5623
__raw_spin_lock_irqsave include/linux/spinlock_api_smp.h:110 [inline]
_raw_spin_lock_irqsave+0xd1/0x120 kernel/locking/spinlock.c:162
trie_delete_elem+0x90/0x690 kernel/bpf/lpm_trie.c:450
bpf_prog_2c29ac5cdc6b1842+0x3a/0x2cc
bpf_dispatcher_nop_func include/linux/bpf.h:780 [inline]
__bpf_prog_run include/linux/filter.h:618 [inline]
bpf_prog_run include/linux/filter.h:632 [inline]
__bpf_trace_run kernel/trace/bpf_trace.c:1880 [inline]
bpf_trace_run2+0x29e/0x340 kernel/trace/bpf_trace.c:1917
trace_tlb_flush+0xed/0x110 include/trace/events/tlb.h:38
switch_mm_irqs_off+0x748/0xa30
context_switch kernel/sched/core.c:5016 [inline]
__schedule+0x1167/0x45b0 kernel/sched/core.c:6376
preempt_schedule_common+0x83/0xd0 kernel/sched/core.c:6552
preempt_schedule+0xd9/0xe0 kernel/sched/core.c:6577
preempt_schedule_thunk+0x16/0x18 arch/x86/entry/thunk_64.S:34
__raw_spin_unlock include/linux/spinlock_api_smp.h:152 [inline]
_raw_spin_unlock+0x36/0x40 kernel/locking/spinlock.c:186
spin_unlock include/linux/spinlock.h:403 [inline]
__text_poke+0x871/0x9e0 arch/x86/kernel/alternative.c:1148
text_poke arch/x86/kernel/alternative.c:1172 [inline]
text_poke_bp_batch+0x145/0x830 arch/x86/kernel/alternative.c:1389
text_poke_flush arch/x86/kernel/alternative.c:1560 [inline]
text_poke_finish+0x16/0x30 arch/x86/kernel/alternative.c:1567
arch_jump_label_transform_apply+0x13/0x20 arch/x86/kernel/jump_label.c:146
static_key_enable_cpuslocked+0x12e/0x250 kernel/jump_label.c:177
static_key_enable+0x16/0x20 kernel/jump_label.c:190
tracepoint_add_func+0x947/0x9d0 kernel/tracepoint.c:361
tracepoint_probe_register_prio_may_exist+0x11e/0x190 kernel/tracepoint.c:482
bpf_raw_tracepoint_open+0x65a/0x750 kernel/bpf/syscall.c:3091
__sys_bpf+0x468/0x670 kernel/bpf/syscall.c:4671
__do_sys_bpf kernel/bpf/syscall.c:4733 [inline]
__se_sys_bpf kernel/bpf/syscall.c:4731 [inline]
__x64_sys_bpf+0x78/0x90 kernel/bpf/syscall.c:4731
do_syscall_x64 arch/x86/entry/common.c:50 [inline]
do_syscall_64+0x3d/0xb0 arch/x86/entry/common.c:80
entry_SYSCALL_64_after_hwframe+0x61/0xcb

other info that might help us debug this:

Chain exists of:
&trie->lock --> &p->pi_lock --> &rq->__lock

Possible unsafe locking scenario:

CPU0 CPU1
---- ----
lock(&rq->__lock);
lock(&p->pi_lock);
lock(&rq->__lock);
lock(&trie->lock);

*** DEADLOCK ***

6 locks held by syz-executor.1/19925:
#0: ffffffff8c95f5a8 (tracepoints_mutex){+.+.}-{3:3}, at: tracepoint_probe_register_prio_may_exist+0xb7/0x190 kernel/tracepoint.c:478
#1: ffffffff8c7bcf90 (cpu_hotplug_lock){++++}-{0:0}, at: static_key_enable+0xe/0x20 kernel/jump_label.c:189
#2: ffffffff8c9ac688 (jump_label_mutex){+.+.}-{3:3}, at: jump_label_lock kernel/jump_label.c:27 [inline]
#2: ffffffff8c9ac688 (jump_label_mutex){+.+.}-{3:3}, at: static_key_enable_cpuslocked+0xcf/0x250 kernel/jump_label.c:174
#3: ffffffff8c7d4c08 (text_mutex){+.+.}-{3:3}, at: arch_jump_label_transform_apply+0xe/0x20 arch/x86/kernel/jump_label.c:145
#4: ffff8880b9a3a318 (&rq->__lock){-.-.}-{2:2}, at: raw_spin_rq_lock_nested+0x26/0x140 kernel/sched/core.c:475
#5: ffffffff8c91f720 (rcu_read_lock){....}-{1:2}, at: rcu_lock_acquire+0x5/0x30 include/linux/rcupdate.h:268

stack backtrace:
CPU: 0 PID: 19925 Comm: syz-executor.1 Not tainted 5.15.152-syzkaller #0
Hardware name: Google Google Compute Engine/Google Compute Engine, BIOS Google 02/29/2024
Call Trace:
<TASK>
__dump_stack lib/dump_stack.c:88 [inline]
dump_stack_lvl+0x1e3/0x2cb lib/dump_stack.c:106
check_noncircular+0x2f8/0x3b0 kernel/locking/lockdep.c:2133
check_prev_add kernel/locking/lockdep.c:3053 [inline]
check_prevs_add kernel/locking/lockdep.c:3172 [inline]
validate_chain+0x1649/0x5930 kernel/locking/lockdep.c:3788
__lock_acquire+0x1295/0x1ff0 kernel/locking/lockdep.c:5012
lock_acquire+0x1db/0x4f0 kernel/locking/lockdep.c:5623
__raw_spin_lock_irqsave include/linux/spinlock_api_smp.h:110 [inline]
_raw_spin_lock_irqsave+0xd1/0x120 kernel/locking/spinlock.c:162
trie_delete_elem+0x90/0x690 kernel/bpf/lpm_trie.c:450
bpf_prog_2c29ac5cdc6b1842+0x3a/0x2cc
bpf_dispatcher_nop_func include/linux/bpf.h:780 [inline]
__bpf_prog_run include/linux/filter.h:618 [inline]
bpf_prog_run include/linux/filter.h:632 [inline]
__bpf_trace_run kernel/trace/bpf_trace.c:1880 [inline]
bpf_trace_run2+0x29e/0x340 kernel/trace/bpf_trace.c:1917
trace_tlb_flush+0xed/0x110 include/trace/events/tlb.h:38
switch_mm_irqs_off+0x748/0xa30
context_switch kernel/sched/core.c:5016 [inline]
__schedule+0x1167/0x45b0 kernel/sched/core.c:6376
preempt_schedule_common+0x83/0xd0 kernel/sched/core.c:6552
preempt_schedule+0xd9/0xe0 kernel/sched/core.c:6577
preempt_schedule_thunk+0x16/0x18 arch/x86/entry/thunk_64.S:34
__raw_spin_unlock include/linux/spinlock_api_smp.h:152 [inline]
_raw_spin_unlock+0x36/0x40 kernel/locking/spinlock.c:186
spin_unlock include/linux/spinlock.h:403 [inline]
__text_poke+0x871/0x9e0 arch/x86/kernel/alternative.c:1148
text_poke arch/x86/kernel/alternative.c:1172 [inline]
text_poke_bp_batch+0x145/0x830 arch/x86/kernel/alternative.c:1389
text_poke_flush arch/x86/kernel/alternative.c:1560 [inline]
text_poke_finish+0x16/0x30 arch/x86/kernel/alternative.c:1567
arch_jump_label_transform_apply+0x13/0x20 arch/x86/kernel/jump_label.c:146
static_key_enable_cpuslocked+0x12e/0x250 kernel/jump_label.c:177
static_key_enable+0x16/0x20 kernel/jump_label.c:190
tracepoint_add_func+0x947/0x9d0 kernel/tracepoint.c:361
tracepoint_probe_register_prio_may_exist+0x11e/0x190 kernel/tracepoint.c:482
bpf_raw_tracepoint_open+0x65a/0x750 kernel/bpf/syscall.c:3091
__sys_bpf+0x468/0x670 kernel/bpf/syscall.c:4671
__do_sys_bpf kernel/bpf/syscall.c:4733 [inline]
__se_sys_bpf kernel/bpf/syscall.c:4731 [inline]
__x64_sys_bpf+0x78/0x90 kernel/bpf/syscall.c:4731
do_syscall_x64 arch/x86/entry/common.c:50 [inline]
do_syscall_64+0x3d/0xb0 arch/x86/entry/common.c:80
entry_SYSCALL_64_after_hwframe+0x61/0xcb
RIP: 0033:0x7f893eeeeda9
Code: Unable to access opcode bytes at RIP 0x7f893eeeed7f.
RSP: 002b:00007f893d46f0c8 EFLAGS: 00000246 ORIG_RAX: 0000000000000141
RAX: ffffffffffffffda RBX: 00007f893f01cf80 RCX: 00007f893eeeeda9
RDX: 0000000000000010 RSI: 00000000200000c0 RDI: 0000000000000011
RBP: 00007f893ef3b47a R08: 0000000000000000 R09: 0000000000000000
R10: 0000000000000000 R11: 0000000000000246 R12: 0000000000000000
R13: 000000000000000b R14: 00007f893f01cf80 R15: 00007ffd558650d8
</TASK>


---
This report is generated by a bot. It may contain errors.
See https://goo.gl/tpsmEJ for more information about syzbot.
syzbot engineers can be reached at syzk...@googlegroups.com.

syzbot will keep track of this issue. See:
https://goo.gl/tpsmEJ#status for how to communicate with syzbot.

If the report is already addressed, let syzbot know by replying with:
#syz fix: exact-commit-title

If you want to overwrite report's subsystems, reply with:
#syz set subsystems: new-subsystem
(See the list of subsystem names on the web dashboard)

If the report is a duplicate of another one, reply with:
#syz dup: exact-subject-of-another-report

If you want to undo deduplication, reply with:
#syz undup

[syzbot]

Hello,

syzbot found the following issue on:

HEAD commit: d7543167affd Linux 6.1.82
git tree: linux-6.1.y
console output: https://syzkaller.appspot.com/x/log.txt?x=1358bffa180000
kernel config: https://syzkaller.appspot.com/x/.config?x=59059e181681c079
dashboard link: https://syzkaller.appspot.com/bug?extid=c3353f07776560dde75c

compiler: Debian clang version 15.0.6, GNU ld (GNU Binutils for Debian) 2.40

Unfortunately, I don't have any reproducer for this issue yet.

Downloadable assets:

disk image: https://storage.googleapis.com/syzbot-assets/88220954516a/disk-d7543167.raw.xz
vmlinux: https://storage.googleapis.com/syzbot-assets/c9062e074717/vmlinux-d7543167.xz
kernel image: https://storage.googleapis.com/syzbot-assets/70391b45a752/bzImage-d7543167.xz

IMPORTANT: if you fix the issue, please add the following tag to the commit:

Reported-by: syzbot+c3353f...@syzkaller.appspotmail.com

============================================
WARNING: possible recursive locking detected
6.1.82-syzkaller #0 Not tainted
--------------------------------------------
syz-executor.2/13536 is trying to acquire lock:
ffff88807d6eca38 (&trie->lock){....}-{2:2}, at: trie_delete_elem+0x90/0x690 kernel/bpf/lpm_trie.c:451

but task is already holding lock:

ffff88807b039238 (&trie->lock){....}-{2:2}, at: trie_update_elem+0xc5/0xc00 kernel/bpf/lpm_trie.c:324

other info that might help us debug this:

Possible unsafe locking scenario:

CPU0

----
lock(&trie->lock);

lock(&trie->lock);

*** DEADLOCK ***

May be due to missing lock nesting notation

3 locks held by syz-executor.2/13536:
#0: ffffffff8d12a940 (rcu_read_lock){....}-{1:2}, at: rcu_lock_acquire include/linux/rcupdate.h:319 [inline]
#0: ffffffff8d12a940 (rcu_read_lock){....}-{1:2}, at: rcu_read_lock include/linux/rcupdate.h:760 [inline]
#0: ffffffff8d12a940 (rcu_read_lock){....}-{1:2}, at: bpf_map_update_value+0x207/0x6f0 kernel/bpf/syscall.c:225
#1: ffff88807b039238 (&trie->lock){....}-{2:2}, at: trie_update_elem+0xc5/0xc00 kernel/bpf/lpm_trie.c:324
#2: ffffffff8d12a940 (rcu_read_lock){....}-{1:2}, at: rcu_lock_acquire include/linux/rcupdate.h:319 [inline]
#2: ffffffff8d12a940 (rcu_read_lock){....}-{1:2}, at: rcu_read_lock include/linux/rcupdate.h:760 [inline]
#2: ffffffff8d12a940 (rcu_read_lock){....}-{1:2}, at: __bpf_trace_run kernel/trace/bpf_trace.c:2272 [inline]
#2: ffffffff8d12a940 (rcu_read_lock){....}-{1:2}, at: bpf_trace_run4+0x16a/0x470 kernel/trace/bpf_trace.c:2314

stack backtrace:
CPU: 0 PID: 13536 Comm: syz-executor.2 Not tainted 6.1.82-syzkaller #0

Hardware name: Google Google Compute Engine/Google Compute Engine, BIOS Google 02/29/2024
Call Trace:
<TASK>
__dump_stack lib/dump_stack.c:88 [inline]
dump_stack_lvl+0x1e3/0x2cb lib/dump_stack.c:106

print_deadlock_bug kernel/locking/lockdep.c:2983 [inline]
check_deadlock kernel/locking/lockdep.c:3026 [inline]
validate_chain+0x4711/0x5950 kernel/locking/lockdep.c:3812
__lock_acquire+0x125b/0x1f80 kernel/locking/lockdep.c:5049
lock_acquire+0x1f8/0x5a0 kernel/locking/lockdep.c:5662

__raw_spin_lock_irqsave include/linux/spinlock_api_smp.h:110 [inline]
_raw_spin_lock_irqsave+0xd1/0x120 kernel/locking/spinlock.c:162

trie_delete_elem+0x90/0x690 kernel/bpf/lpm_trie.c:451
bpf_prog_2c29ac5cdc6b1842+0x3a/0x3e
bpf_dispatcher_nop_func include/linux/bpf.h:989 [inline]
__bpf_prog_run include/linux/filter.h:600 [inline]
bpf_prog_run include/linux/filter.h:607 [inline]
__bpf_trace_run kernel/trace/bpf_trace.c:2273 [inline]
bpf_trace_run4+0x253/0x470 kernel/trace/bpf_trace.c:2314
__bpf_trace_mm_page_alloc+0xba/0xe0 include/trace/events/kmem.h:177
trace_mm_page_alloc include/trace/events/kmem.h:177 [inline]
__alloc_pages+0x717/0x770 mm/page_alloc.c:5567
__alloc_pages_node include/linux/gfp.h:237 [inline]
alloc_pages_node include/linux/gfp.h:260 [inline]
__kmalloc_large_node+0x91/0x1d0 mm/slab_common.c:1096
__do_kmalloc_node mm/slab_common.c:943 [inline]
__kmalloc_node+0x111/0x230 mm/slab_common.c:962
kmalloc_node include/linux/slab.h:582 [inline]
bpf_map_kmalloc_node+0xce/0x1c0 kernel/bpf/syscall.c:452
lpm_trie_node_alloc kernel/bpf/lpm_trie.c:291 [inline]
trie_update_elem+0x1cb/0xc00 kernel/bpf/lpm_trie.c:333
bpf_map_update_value+0x5cf/0x6f0 kernel/bpf/syscall.c:226
map_update_elem+0x503/0x680 kernel/bpf/syscall.c:1448
__sys_bpf+0x337/0x6c0 kernel/bpf/syscall.c:4993
__do_sys_bpf kernel/bpf/syscall.c:5109 [inline]
__se_sys_bpf kernel/bpf/syscall.c:5107 [inline]
__x64_sys_bpf+0x78/0x90 kernel/bpf/syscall.c:5107
do_syscall_x64 arch/x86/entry/common.c:51 [inline]
do_syscall_64+0x3d/0xb0 arch/x86/entry/common.c:81
entry_SYSCALL_64_after_hwframe+0x63/0xcd
RIP: 0033:0x7f289567dda9
Code: 28 00 00 00 75 05 48 83 c4 28 c3 e8 e1 20 00 00 90 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 b0 ff ff ff f7 d8 64 89 01 48
RSP: 002b:00007f28963fc0c8 EFLAGS: 00000246 ORIG_RAX: 0000000000000141
RAX: ffffffffffffffda RBX: 00007f28957abf80 RCX: 00007f289567dda9
RDX: 0000000000000020 RSI: 0000000020000180 RDI: 0000000000000002
RBP: 00007f28956ca47a R08: 0000000000000000 R09: 0000000000000000

R10: 0000000000000000 R11: 0000000000000246 R12: 0000000000000000

R13: 000000000000000b R14: 00007f28957abf80 R15: 00007fff1adc7618

[syzbot]

syzbot has found a reproducer for the following issue on:

HEAD commit: b95c01af2113 Linux 5.15.152
git tree: linux-5.15.y

console output: https://syzkaller.appspot.com/x/log.txt?x=1516fc6e180000

kernel config: https://syzkaller.appspot.com/x/.config?x=b26cb65e5b8ad5c7
dashboard link: https://syzkaller.appspot.com/bug?extid=c361763297bd80b2cc11
compiler: Debian clang version 15.0.6, GNU ld (GNU Binutils for Debian) 2.40

syz repro: https://syzkaller.appspot.com/x/repro.syz?x=14622546180000
C reproducer: https://syzkaller.appspot.com/x/repro.c?x=16cfb83a180000

Downloadable assets:
disk image: https://storage.googleapis.com/syzbot-assets/5cd4262a21bb/disk-b95c01af.raw.xz
vmlinux: https://storage.googleapis.com/syzbot-assets/85698e4f8310/vmlinux-b95c01af.xz
kernel image: https://storage.googleapis.com/syzbot-assets/f57a616768d4/bzImage-b95c01af.xz

IMPORTANT: if you fix the issue, please add the following tag to the commit:
Reported-by: syzbot+c36176...@syzkaller.appspotmail.com

============================================
WARNING: possible recursive locking detected

5.15.152-syzkaller #0 Not tainted
--------------------------------------------

syz-executor349/3498 is trying to acquire lock:
ffff88801f9c11b8 (&trie->lock){....}-{2:2}, at: trie_delete_elem+0x90/0x690 kernel/bpf/lpm_trie.c:450

but task is already holding lock:

ffff88801f9c15b8 (&trie->lock){....}-{2:2}, at: trie_update_elem+0xc5/0xc00 kernel/bpf/lpm_trie.c:323

other info that might help us debug this:

Possible unsafe locking scenario:

CPU0

----
lock(&trie->lock);

lock(&trie->lock);

*** DEADLOCK ***

May be due to missing lock nesting notation

3 locks held by syz-executor349/3498:
#0: ffffffff8c91f720 (rcu_read_lock){....}-{1:2}, at: rcu_lock_acquire+0x5/0x30 include/linux/rcupdate.h:268
#1: ffff88801f9c15b8 (&trie->lock){....}-{2:2}, at: trie_update_elem+0xc5/0xc00 kernel/bpf/lpm_trie.c:323
#2: ffffffff8c91f720 (rcu_read_lock){....}-{1:2}, at: rcu_lock_acquire+0x5/0x30 include/linux/rcupdate.h:268

stack backtrace:
CPU: 1 PID: 3498 Comm: syz-executor349 Not tainted 5.15.152-syzkaller #0

Hardware name: Google Google Compute Engine/Google Compute Engine, BIOS Google 02/29/2024
Call Trace:
<TASK>
__dump_stack lib/dump_stack.c:88 [inline]
dump_stack_lvl+0x1e3/0x2cb lib/dump_stack.c:106

print_deadlock_bug kernel/locking/lockdep.c:2946 [inline]
check_deadlock kernel/locking/lockdep.c:2989 [inline]
validate_chain+0x46d2/0x5930 kernel/locking/lockdep.c:3775

__lock_acquire+0x1295/0x1ff0 kernel/locking/lockdep.c:5012
lock_acquire+0x1db/0x4f0 kernel/locking/lockdep.c:5623
__raw_spin_lock_irqsave include/linux/spinlock_api_smp.h:110 [inline]
_raw_spin_lock_irqsave+0xd1/0x120 kernel/locking/spinlock.c:162
trie_delete_elem+0x90/0x690 kernel/bpf/lpm_trie.c:450

bpf_prog_2c29ac5cdc6b1842+0x3a/0x748
bpf_dispatcher_nop_func include/linux/bpf.h:780 [inline]
__bpf_prog_run include/linux/filter.h:625 [inline]

bpf_prog_run include/linux/filter.h:632 [inline]
__bpf_trace_run kernel/trace/bpf_trace.c:1880 [inline]

bpf_trace_run4+0x1ea/0x390 kernel/trace/bpf_trace.c:1919
__bpf_trace_mm_page_alloc+0xba/0xe0 include/trace/events/kmem.h:201
trace_mm_page_alloc include/trace/events/kmem.h:201 [inline]
__alloc_pages+0x6e0/0x700 mm/page_alloc.c:5443
__alloc_pages_node include/linux/gfp.h:570 [inline]
alloc_pages_node include/linux/gfp.h:584 [inline]
kmalloc_large_node+0x7c/0x180 mm/slub.c:4421
__kmalloc_node+0x22d/0x390 mm/slub.c:4437
kmalloc_node include/linux/slab.h:614 [inline]
bpf_map_kmalloc_node+0xdb/0x160 kernel/bpf/syscall.c:430
lpm_trie_node_alloc kernel/bpf/lpm_trie.c:290 [inline]
trie_update_elem+0x1cb/0xc00 kernel/bpf/lpm_trie.c:332
bpf_map_update_value+0x5d7/0x6c0 kernel/bpf/syscall.c:221
map_update_elem+0x6a0/0x7c0 kernel/bpf/syscall.c:1163
__sys_bpf+0x2fd/0x670 kernel/bpf/syscall.c:4617

__do_sys_bpf kernel/bpf/syscall.c:4733 [inline]
__se_sys_bpf kernel/bpf/syscall.c:4731 [inline]
__x64_sys_bpf+0x78/0x90 kernel/bpf/syscall.c:4731
do_syscall_x64 arch/x86/entry/common.c:50 [inline]
do_syscall_64+0x3d/0xb0 arch/x86/entry/common.c:80
entry_SYSCALL_64_after_hwframe+0x61/0xcb

RIP: 0033:0x7f2199ff27a9
Code: 48 83 c4 28 c3 e8 37 17 00 00 0f 1f 80 00 00 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 b8 ff ff ff f7 d8 64 89 01 48
RSP: 002b:00007ffcd1e75b48 EFLAGS: 00000246 ORIG_RAX: 0000000000000141
RAX: ffffffffffffffda


---
If you want syzbot to run the reproducer, reply with:
#syz test: git://repo/address.git branch-or-commit-hash
If you attach or paste a git patch, syzbot will apply it before testing.

[syzbot]

syzbot has found a reproducer for the following issue on:

HEAD commit: d7543167affd Linux 6.1.82
git tree: linux-6.1.y

console output: https://syzkaller.appspot.com/x/log.txt?x=176fdaa5180000

kernel config: https://syzkaller.appspot.com/x/.config?x=59059e181681c079
dashboard link: https://syzkaller.appspot.com/bug?extid=c3353f07776560dde75c
compiler: Debian clang version 15.0.6, GNU ld (GNU Binutils for Debian) 2.40

syz repro: https://syzkaller.appspot.com/x/repro.syz?x=1460bbb9180000
C reproducer: https://syzkaller.appspot.com/x/repro.c?x=14644c81180000

Downloadable assets:
disk image: https://storage.googleapis.com/syzbot-assets/a2421980b49a/disk-d7543167.raw.xz
vmlinux: https://storage.googleapis.com/syzbot-assets/52a6bb44161f/vmlinux-d7543167.xz
kernel image: https://storage.googleapis.com/syzbot-assets/9b3723bf43a9/bzImage-d7543167.xz

IMPORTANT: if you fix the issue, please add the following tag to the commit:
Reported-by: syzbot+c3353f...@syzkaller.appspotmail.com

============================================
WARNING: possible recursive locking detected
6.1.82-syzkaller #0 Not tainted
--------------------------------------------

syz-executor146/3540 is trying to acquire lock:
ffff88807c4fe238 (&trie->lock){....}-{2:2}, at: trie_delete_elem+0x90/0x690 kernel/bpf/lpm_trie.c:451

but task is already holding lock:

ffff88807e66aa38 (&trie->lock){....}-{2:2}, at: trie_update_elem+0xc5/0xc00 kernel/bpf/lpm_trie.c:324

other info that might help us debug this:
Possible unsafe locking scenario:

CPU0
----
lock(&trie->lock);
lock(&trie->lock);

*** DEADLOCK ***

May be due to missing lock nesting notation

3 locks held by syz-executor146/3540:

#0: ffffffff8d12a940 (rcu_read_lock){....}-{1:2}, at: rcu_lock_acquire include/linux/rcupdate.h:319 [inline]
#0: ffffffff8d12a940 (rcu_read_lock){....}-{1:2}, at: rcu_read_lock include/linux/rcupdate.h:760 [inline]
#0: ffffffff8d12a940 (rcu_read_lock){....}-{1:2}, at: bpf_map_update_value+0x207/0x6f0 kernel/bpf/syscall.c:225

#1: ffff88807e66aa38 (&trie->lock){....}-{2:2}, at: trie_update_elem+0xc5/0xc00 kernel/bpf/lpm_trie.c:324

#2: ffffffff8d12a940 (rcu_read_lock){....}-{1:2}, at: rcu_lock_acquire include/linux/rcupdate.h:319 [inline]
#2: ffffffff8d12a940 (rcu_read_lock){....}-{1:2}, at: rcu_read_lock include/linux/rcupdate.h:760 [inline]
#2: ffffffff8d12a940 (rcu_read_lock){....}-{1:2}, at: __bpf_trace_run kernel/trace/bpf_trace.c:2272 [inline]
#2: ffffffff8d12a940 (rcu_read_lock){....}-{1:2}, at: bpf_trace_run4+0x16a/0x470 kernel/trace/bpf_trace.c:2314

stack backtrace:

CPU: 1 PID: 3540 Comm: syz-executor146 Not tainted 6.1.82-syzkaller #0

RIP: 0033:0x7f8271a687a9
Code: 48 83 c4 28 c3 e8 37 17 00 00 0f 1f 80 00 00 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 b8 ff ff ff f7 d8 64 89 01 48
RSP: 002b:00007ffdfbceaea8 EFLAGS: 000