bpf: Convert lpm_trie::lock to 'raw_spinlock_t'
Subsystems (2)
PATCH 1/1 bpf: Convert lpm_trie::lock to 'raw_spinlock_t'
From: Kunwu Chan <[email protected]>
When PREEMPT_RT is enabled, 'spinlock_t' becomes preemptible and bpf program has owned a raw_spinlock under a interrupt handler, which results in invalid lock acquire context.
[ BUG: Invalid wait context ] 6.12.0-rc5-next-20241031-syzkaller #0 Not tainted
-----------------------------
swapper/0/0 is trying to lock:ffff8880261e7a00 (&trie->lock){....}-{3:3},
at: trie_delete_elem+0x96/0x6a0 kernel/bpf/lpm_trie.c:462 other info that might help us debug this:
context-{3:3}
5 locks held by swapper/0/0:
#0: ffff888020bb75c8 (&vp_dev->lock){-...}-{3:3},
at: vp_vring_interrupt drivers/virtio/virtio_pci_common.c:80 [inline]
#0: ffff888020bb75c8 (&vp_dev->lock){-...}-{3:3},
at: vp_interrupt+0x142/0x200 drivers/virtio/virtio_pci_common.c:113
#1: ffff88814174a120 (&vb->stop_update_lock){-...}-{3:3},
at: spin_lock include/linux/spinlock.h:351 [inline]
#1: ffff88814174a120 (&vb->stop_update_lock){-...}-{3:3},
at: stats_request+0x6f/0x230 drivers/virtio/virtio_balloon.c:438
#2: ffffffff8e939f20 (rcu_read_lock){....}-{1:3},
at: rcu_lock_acquire include/linux/rcupdate.h:337 [inline]
#2: ffffffff8e939f20 (rcu_read_lock){....}-{1:3},
at: rcu_read_lock include/linux/rcupdate.h:849 [inline]
#2: ffffffff8e939f20 (rcu_read_lock){....}-{1:3},
at: __queue_work+0x199/0xf50 kernel/workqueue.c:2259
#3: ffff8880b863dd18 (&pool->lock){-.-.}-{2:2},
at: __queue_work+0x759/0xf50
#4: ffffffff8e939f20 (rcu_read_lock){....}-{1:3},
at: rcu_lock_acquire include/linux/rcupdate.h:337 [inline]
#4: ffffffff8e939f20 (rcu_read_lock){....}-{1:3},
at: rcu_read_lock include/linux/rcupdate.h:849 [inline]
#4: ffffffff8e939f20 (rcu_read_lock){....}-{1:3},
at: __bpf_trace_run kernel/trace/bpf_trace.c:2339 [inline]
#4: ffffffff8e939f20 (rcu_read_lock){....}-{1:3},
at: bpf_trace_run1+0x1d6/0x520 kernel/trace/bpf_trace.c:2380
stack backtrace: CPU: 0 UID: 0 PID: 0 Comm: swapper/0 Not tainted 6.12.0-rc5-next-20241031-syzkaller #0 Hardware name: Google Compute Engine/Google Compute Engine, BIOS Google 09/13/2024 Call Trace: <IRQ> __dump_stack lib/dump_stack.c:94 [inline] dump_stack_lvl+0x241/0x360 lib/dump_stack.c:120 print_lock_invalid_wait_context kernel/locking/lockdep.c:4826 [inline] check_wait_context kernel/locking/lockdep.c:4898 [inline] __lock_acquire+0x15a8/0x2100 kernel/locking/lockdep.c:5176 lock_acquire+0x1ed/0x550 kernel/locking/lockdep.c:5849 __raw_spin_lock_irqsave include/linux/spinlock_api_smp.h:110 [inline] _raw_spin_lock_irqsave+0xd5/0x120 kernel/locking/spinlock.c:162 trie_delete_elem+0x96/0x6a0 kernel/bpf/lpm_trie.c:462 bpf_prog_2c29ac5cdc6b1842+0x43/0x47 bpf_dispatcher_nop_func include/linux/bpf.h:1290 [inline] __bpf_prog_run include/linux/filter.h:701 [inline] bpf_prog_run include/linux/filter.h:708 [inline] __bpf_trace_run kernel/trace/bpf_trace.c:2340 [inline] bpf_trace_run1+0x2ca/0x520 kernel/trace/bpf_trace.c:2380 trace_workqueue_activate_work+0x186/0x1f0 include/trace/events/workqueue.h:59 __queue_work+0xc7b/0xf50 kernel/workqueue.c:2338 queue_work_on+0x1c2/0x380 kernel/workqueue.c:2390 queue_work include/linux/workqueue.h:662 [inline] stats_request+0x1a3/0x230 drivers/virtio/virtio_balloon.c:441 vring_interrupt+0x21d/0x380 drivers/virtio/virtio_ring.c:2595 vp_vring_interrupt drivers/virtio/virtio_pci_common.c:82 [inline] vp_interrupt+0x192/0x200 drivers/virtio/virtio_pci_common.c:113 __handle_irq_event_percpu+0x29a/0xa80 kernel/irq/handle.c:158 handle_irq_event_percpu kernel/irq/handle.c:193 [inline] handle_irq_event+0x89/0x1f0 kernel/irq/handle.c:210 handle_fasteoi_irq+0x48a/0xae0 kernel/irq/chip.c:720 generic_handle_irq_desc include/linux/irqdesc.h:173 [inline] handle_irq arch/x86/kernel/irq.c:247 [inline] call_irq_handler arch/x86/kernel/irq.c:259 [inline] __common_interrupt+0x136/0x230 arch/x86/kernel/irq.c:285 common_interrupt+0xb4/0xd0 arch/x86/kernel/irq.c:278 </IRQ>
--- kernel/bpf/lpm_trie.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-)
kernel/bpf/lpm_trie.c +6 -6
@@ -35,7 +35,7 @@ struct lpm_trie {size_t n_entries;size_t max_prefixlen;size_t data_size; -spinlock_t lock; +raw_spinlock_t lock; };/* This trie implements a longest prefix match algorithm that can be used to
@@ -330,7 +330,7 @@ static long trie_update_elem(struct bpf_map *map,if (key->prefixlen > trie->max_prefixlen)return -EINVAL ; -spin_lock_irqsave (&trie->lock, irq_flags); +raw_spin_lock_irqsave (&trie->lock, irq_flags);/* Allocate and fill a new node */
@@ -437,7 +437,7 @@ static long trie_update_elem(struct bpf_map *map,kfree (im_node); } -spin_unlock_irqrestore (&trie->lock, irq_flags); +raw_spin_unlock_irqrestore (&trie->lock, irq_flags);kfree_rcu (free_node, rcu);return ret;
@@ -459,7 +459,7 @@ static long trie_delete_elem(struct bpf_map *map, void *_key)if (key->prefixlen > trie->max_prefixlen)return -EINVAL ; -spin_lock_irqsave (&trie->lock, irq_flags); +raw_spin_lock_irqsave (&trie->lock, irq_flags);/* Walk the tree looking for an exact key/length match and keeping * track of the path we traverse. We will need to know the node
@@ -535,7 +535,7 @@ static long trie_delete_elem(struct bpf_map *map, void *_key) free_node = node; out: -spin_unlock_irqrestore (&trie->lock, irq_flags); +raw_spin_unlock_irqrestore (&trie->lock, irq_flags);kfree_rcu (free_parent, rcu);kfree_rcu (free_node, rcu);
@@ -581,7 +581,7 @@ static struct bpf_map *trie_alloc(union bpf_attr *attr) offsetof(struct bpf_lpm_trie_key_u8 , data); trie->max_prefixlen = trie->data_size *8 ; -spin_lock_init (&trie->lock); +raw_spin_lock_init (&trie->lock);return &trie->map; }
Signature · 1 line
2.34.1
Quoted 40 lines · Kunwu Chan
From: Kunwu Chan <[email protected]>
When
PREEMPT_RTis enabled, 'spinlock_t' becomes preemptible and bpf program has owned araw_spinlockunder a interrupt handler, which results in invalid lock acquire context.[ BUG: Invalid wait context ] 6.12.0-rc5-next-20241031-syzkaller #0 Not tainted
-----------------------------
swapper/0/0 is trying to lock:ffff8880261e7a00(&trie->lock){....}-{3:3},
at:trie_delete_elem+0x96/0x6a0kernel/bpf/lpm_trie.c:462other info that might help us debug this:
context-{3:3}
5 locks held by swapper/0/0:
#0:ffff888020bb75c8(&vp_dev->lock){-...}-{3:3},
at:vp_vring_interruptdrivers/virtio/virtio_pci_common.c:80[inline]
#0:ffff888020bb75c8(&vp_dev->lock){-...}-{3:3},
at:vp_interrupt+0x142/0x200drivers/virtio/virtio_pci_common.c:113
#1:ffff88814174a120(&vb->stop_update_lock){-...}-{3:3},
at:spin_lockinclude/linux/spinlock.h:351[inline]
#1:ffff88814174a120(&vb->stop_update_lock){-...}-{3:3},
at:stats_request+0x6f/0x230drivers/virtio/virtio_balloon.c:438
#2:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:rcu_lock_acquireinclude/linux/rcupdate.h:337[inline]
#2:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:rcu_read_lockinclude/linux/rcupdate.h:849[inline]
#2:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:__queue_work+0x199/0xf50kernel/workqueue.c:2259
#3:ffff8880b863dd18(&pool->lock){-.-.}-{2:2},
at:__queue_work+0x759/0xf50
#4:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:rcu_lock_acquireinclude/linux/rcupdate.h:337[inline]
#4:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:rcu_read_lockinclude/linux/rcupdate.h:849[inline]
#4:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:__bpf_trace_runkernel/trace/bpf_trace.c:2339[inline]
#4:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:bpf_trace_run1+0x1d6/0x520kernel/trace/bpf_trace.c:2380
Quoted 16 lines
stack backtrace: CPU: 0 UID: 0 PID: 0 Comm: swapper/0 Not tainted 6.12.0-rc5-next-20241031-syzkaller #0 Hardware name: Google Compute Engine/Google Compute Engine, BIOS Google 09/13/2024 Call Trace: <IRQ> __dump_stack lib/dump_stack.c:94 [inline] dump_stack_lvl+0x241/0x360 lib/dump_stack.c:120 print_lock_invalid_wait_context kernel/locking/lockdep.c:4826 [inline] check_wait_context kernel/locking/lockdep.c:4898 [inline] __lock_acquire+0x15a8/0x2100 kernel/locking/lockdep.c:5176 lock_acquire+0x1ed/0x550 kernel/locking/lockdep.c:5849 __raw_spin_lock_irqsave include/linux/spinlock_api_smp.h:110 [inline] _raw_spin_lock_irqsave+0xd5/0x120 kernel/locking/spinlock.c:162 trie_delete_elem+0x96/0x6a0 kernel/bpf/lpm_trie.c:462
This trace is from non-RT kernel where spin_lock == raw_spin_lock.
I don't think Hou's explanation earlier is correct.
https://lore.kernel.org/bpf/[email protected]/
Quoted 9 lines
bpf_prog_2c29ac5cdc6b1842+0x43/0x47 bpf_dispatcher_nop_func include/linux/bpf.h:1290 [inline] __bpf_prog_run include/linux/filter.h:701 [inline] bpf_prog_run include/linux/filter.h:708 [inline] __bpf_trace_run kernel/trace/bpf_trace.c:2340 [inline] bpf_trace_run1+0x2ca/0x520 kernel/trace/bpf_trace.c:2380 trace_workqueue_activate_work+0x186/0x1f0 include/trace/events/workqueue.h:59 __queue_work+0xc7b/0xf50 kernel/workqueue.c:2338 queue_work_on+0x1c2/0x380 kernel/workqueue.c:2390
here irqs are disabled, but raw_spin_lock in lpm should be fine.
Quoted 29 lines
queue_work include/linux/workqueue.h:662 [inline] stats_request+0x1a3/0x230 drivers/virtio/virtio_balloon.c:441 vring_interrupt+0x21d/0x380 drivers/virtio/virtio_ring.c:2595 vp_vring_interrupt drivers/virtio/virtio_pci_common.c:82 [inline] vp_interrupt+0x192/0x200 drivers/virtio/virtio_pci_common.c:113 __handle_irq_event_percpu+0x29a/0xa80 kernel/irq/handle.c:158 handle_irq_event_percpu kernel/irq/handle.c:193 [inline] handle_irq_event+0x89/0x1f0 kernel/irq/handle.c:210 handle_fasteoi_irq+0x48a/0xae0 kernel/irq/chip.c:720 generic_handle_irq_desc include/linux/irqdesc.h:173 [inline] handle_irq arch/x86/kernel/irq.c:247 [inline] call_irq_handler arch/x86/kernel/irq.c:259 [inline] __common_interrupt+0x136/0x230 arch/x86/kernel/irq.c:285 common_interrupt+0xb4/0xd0 arch/x86/kernel/irq.c:278 </IRQ>Reported-by [email protected]Fixes 66150d0dde03 ("bpf, lpm: Make locking RT friendly")Signed-off-by Kunwu Chan <[email protected]>--- kernel/bpf/lpm_trie.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-)kernel/bpf/lpm_trie.c +0
-0
kernel/bpf/lpm_trie.c struct lpm_trie { · line 39
Quoted 6 lines
kernel/bpf/lpm_trie.c +1
-1@@ -35,7 +35,7 @@ struct lpm_trie {size_t n_entries;size_t max_prefixlen;size_t data_size; -spinlock_t lock; +raw_spinlock_t lock; };
We're certainly not going back.
pw-bot: cr
Hi Alexei,
Quoted 56 lines · Alexei Starovoitov
Quoted 39 lines · Kunwu Chan
From: Kunwu Chan <[email protected]>
When
PREEMPT_RTis enabled, 'spinlock_t' becomes preemptible and bpf program has owned araw_spinlockunder a interrupt handler, which results in invalid lock acquire context.[ BUG: Invalid wait context ] 6.12.0-rc5-next-20241031-syzkaller #0 Not tainted
-----------------------------
swapper/0/0 is trying to lock:ffff8880261e7a00(&trie->lock){....}-{3:3},
at:trie_delete_elem+0x96/0x6a0kernel/bpf/lpm_trie.c:462other info that might help us debug this:
context-{3:3}
5 locks held by swapper/0/0:
#0:ffff888020bb75c8(&vp_dev->lock){-...}-{3:3},
at:vp_vring_interruptdrivers/virtio/virtio_pci_common.c:80[inline]
#0:ffff888020bb75c8(&vp_dev->lock){-...}-{3:3},
at:vp_interrupt+0x142/0x200drivers/virtio/virtio_pci_common.c:113
#1:ffff88814174a120(&vb->stop_update_lock){-...}-{3:3},
at:spin_lockinclude/linux/spinlock.h:351[inline]
#1:ffff88814174a120(&vb->stop_update_lock){-...}-{3:3},
at:stats_request+0x6f/0x230drivers/virtio/virtio_balloon.c:438
#2:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:rcu_lock_acquireinclude/linux/rcupdate.h:337[inline]
#2:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:rcu_read_lockinclude/linux/rcupdate.h:849[inline]
#2:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:__queue_work+0x199/0xf50kernel/workqueue.c:2259
#3:ffff8880b863dd18(&pool->lock){-.-.}-{2:2},
at:__queue_work+0x759/0xf50
#4:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:rcu_lock_acquireinclude/linux/rcupdate.h:337[inline]
#4:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:rcu_read_lockinclude/linux/rcupdate.h:849[inline]
#4:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:__bpf_trace_runkernel/trace/bpf_trace.c:2339[inline]
#4:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:bpf_trace_run1+0x1d6/0x520kernel/trace/bpf_trace.c:2380Quoted 16 lines
stack backtrace: CPU: 0 UID: 0 PID: 0 Comm: swapper/0 Not tainted 6.12.0-rc5-next-20241031-syzkaller #0 Hardware name: Google Compute Engine/Google Compute Engine, BIOS Google 09/13/2024 Call Trace: <IRQ> __dump_stack lib/dump_stack.c:94 [inline] dump_stack_lvl+0x241/0x360 lib/dump_stack.c:120 print_lock_invalid_wait_context kernel/locking/lockdep.c:4826 [inline] check_wait_context kernel/locking/lockdep.c:4898 [inline] __lock_acquire+0x15a8/0x2100 kernel/locking/lockdep.c:5176 lock_acquire+0x1ed/0x550 kernel/locking/lockdep.c:5849 __raw_spin_lock_irqsave include/linux/spinlock_api_smp.h:110 [inline] _raw_spin_lock_irqsave+0xd5/0x120 kernel/locking/spinlock.c:162 trie_delete_elem+0x96/0x6a0 kernel/bpf/lpm_trie.c:462
Quoted 1 line
This trace is from non-RT kernel where
spin_lock==raw_spin_lock.
Yes. However, I think the reason for the warning is that lockdep considers the case is possible under PREEMPT_RT and it violates the rule of lock [1].
Quoted 3 lines
I don't think Hou's explanation earlier is correct.
https://lore.kernel.org/bpf/[email protected]/
OK. Is the bpf mem allocator part OK for you ?
Quoted 36 lines
Quoted 10 lines
bpf_prog_2c29ac5cdc6b1842+0x43/0x47 bpf_dispatcher_nop_func include/linux/bpf.h:1290 [inline] __bpf_prog_run include/linux/filter.h:701 [inline] bpf_prog_run include/linux/filter.h:708 [inline] __bpf_trace_run kernel/trace/bpf_trace.c:2340 [inline] bpf_trace_run1+0x2ca/0x520 kernel/trace/bpf_trace.c:2380 trace_workqueue_activate_work+0x186/0x1f0 include/trace/events/workqueue.h:59 __queue_work+0xc7b/0xf50 kernel/workqueue.c:2338 queue_work_on+0x1c2/0x380 kernel/workqueue.c:2390here irqs are disabled, but
raw_spin_lockin lpm should be fine.Quoted 24 lines
queue_work include/linux/workqueue.h:662 [inline] stats_request+0x1a3/0x230 drivers/virtio/virtio_balloon.c:441 vring_interrupt+0x21d/0x380 drivers/virtio/virtio_ring.c:2595 vp_vring_interrupt drivers/virtio/virtio_pci_common.c:82 [inline] vp_interrupt+0x192/0x200 drivers/virtio/virtio_pci_common.c:113 __handle_irq_event_percpu+0x29a/0xa80 kernel/irq/handle.c:158 handle_irq_event_percpu kernel/irq/handle.c:193 [inline] handle_irq_event+0x89/0x1f0 kernel/irq/handle.c:210 handle_fasteoi_irq+0x48a/0xae0 kernel/irq/chip.c:720 generic_handle_irq_desc include/linux/irqdesc.h:173 [inline] handle_irq arch/x86/kernel/irq.c:247 [inline] call_irq_handler arch/x86/kernel/irq.c:259 [inline] __common_interrupt+0x136/0x230 arch/x86/kernel/irq.c:285 common_interrupt+0xb4/0xd0 arch/x86/kernel/irq.c:278 </IRQ>Reported-by [email protected]Fixes 66150d0dde03 ("bpf, lpm: Make locking RT friendly")Signed-off-by Kunwu Chan <[email protected]>--- kernel/bpf/lpm_trie.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-)
Quoted 12 lines
kernel/bpf/lpm_trie.c struct lpm_trie { · line 39
Quoted 11 lines
kernel/bpf/lpm_trie.c +1
-1@@ -35,7 +35,7 @@ struct lpm_trie {size_t n_entries;size_t max_prefixlen;size_t data_size; -spinlock_t lock; +raw_spinlock_t lock; };We're certainly not going back.
Only switching from spinlock_t to raw_spinlock_t is not enough, running it under PREEMPT_RT after the change will still trigger the similar lockdep warning. That is because kmalloc() may acquire a spinlock_t as well. However, after changing the kmalloc and its variants to bpf memory allocator, I think the switch to raw_spinlock_t will be safe. I have already written a draft patch set. Will post after after polishing and testing it. WDYT ?
Quoted 2 lines
pw-bot: cr
Quoted 122 lines · Hou Tao
Hi Alexei,
Quoted 56 lines · Alexei Starovoitov
Quoted 39 lines · Kunwu Chan
From: Kunwu Chan <[email protected]>
When
PREEMPT_RTis enabled, 'spinlock_t' becomes preemptible and bpf program has owned araw_spinlockunder a interrupt handler, which results in invalid lock acquire context.[ BUG: Invalid wait context ] 6.12.0-rc5-next-20241031-syzkaller #0 Not tainted
-----------------------------
swapper/0/0 is trying to lock:ffff8880261e7a00(&trie->lock){....}-{3:3},
at:trie_delete_elem+0x96/0x6a0kernel/bpf/lpm_trie.c:462other info that might help us debug this:
context-{3:3}
5 locks held by swapper/0/0:
#0:ffff888020bb75c8(&vp_dev->lock){-...}-{3:3},
at:vp_vring_interruptdrivers/virtio/virtio_pci_common.c:80[inline]
#0:ffff888020bb75c8(&vp_dev->lock){-...}-{3:3},
at:vp_interrupt+0x142/0x200drivers/virtio/virtio_pci_common.c:113
#1:ffff88814174a120(&vb->stop_update_lock){-...}-{3:3},
at:spin_lockinclude/linux/spinlock.h:351[inline]
#1:ffff88814174a120(&vb->stop_update_lock){-...}-{3:3},
at:stats_request+0x6f/0x230drivers/virtio/virtio_balloon.c:438
#2:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:rcu_lock_acquireinclude/linux/rcupdate.h:337[inline]
#2:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:rcu_read_lockinclude/linux/rcupdate.h:849[inline]
#2:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:__queue_work+0x199/0xf50kernel/workqueue.c:2259
#3:ffff8880b863dd18(&pool->lock){-.-.}-{2:2},
at:__queue_work+0x759/0xf50
#4:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:rcu_lock_acquireinclude/linux/rcupdate.h:337[inline]
#4:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:rcu_read_lockinclude/linux/rcupdate.h:849[inline]
#4:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:__bpf_trace_runkernel/trace/bpf_trace.c:2339[inline]
#4:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:bpf_trace_run1+0x1d6/0x520kernel/trace/bpf_trace.c:2380Quoted 16 lines
stack backtrace: CPU: 0 UID: 0 PID: 0 Comm: swapper/0 Not tainted 6.12.0-rc5-next-20241031-syzkaller #0 Hardware name: Google Compute Engine/Google Compute Engine, BIOS Google 09/13/2024 Call Trace: <IRQ> __dump_stack lib/dump_stack.c:94 [inline] dump_stack_lvl+0x241/0x360 lib/dump_stack.c:120 print_lock_invalid_wait_context kernel/locking/lockdep.c:4826 [inline] check_wait_context kernel/locking/lockdep.c:4898 [inline] __lock_acquire+0x15a8/0x2100 kernel/locking/lockdep.c:5176 lock_acquire+0x1ed/0x550 kernel/locking/lockdep.c:5849 __raw_spin_lock_irqsave include/linux/spinlock_api_smp.h:110 [inline] _raw_spin_lock_irqsave+0xd5/0x120 kernel/locking/spinlock.c:162 trie_delete_elem+0x96/0x6a0 kernel/bpf/lpm_trie.c:462Quoted 1 line
This trace is from non-RT kernel where
spin_lock==raw_spin_lock.Yes. However, I think the reason for the warning is that lockdep considers the case is possible under
PREEMPT_RTand it violates the rule of lock [1].Quoted 3 lines
I don't think Hou's explanation earlier is correct.
https://lore.kernel.org/bpf/[email protected]/OK. Is the bpf mem allocator part OK for you ?
Quoted 36 lines
Quoted 10 lines
bpf_prog_2c29ac5cdc6b1842+0x43/0x47 bpf_dispatcher_nop_func include/linux/bpf.h:1290 [inline] __bpf_prog_run include/linux/filter.h:701 [inline] bpf_prog_run include/linux/filter.h:708 [inline] __bpf_trace_run kernel/trace/bpf_trace.c:2340 [inline] bpf_trace_run1+0x2ca/0x520 kernel/trace/bpf_trace.c:2380 trace_workqueue_activate_work+0x186/0x1f0 include/trace/events/workqueue.h:59 __queue_work+0xc7b/0xf50 kernel/workqueue.c:2338 queue_work_on+0x1c2/0x380 kernel/workqueue.c:2390here irqs are disabled, but
raw_spin_lockin lpm should be fine.Quoted 24 lines
queue_work include/linux/workqueue.h:662 [inline] stats_request+0x1a3/0x230 drivers/virtio/virtio_balloon.c:441 vring_interrupt+0x21d/0x380 drivers/virtio/virtio_ring.c:2595 vp_vring_interrupt drivers/virtio/virtio_pci_common.c:82 [inline] vp_interrupt+0x192/0x200 drivers/virtio/virtio_pci_common.c:113 __handle_irq_event_percpu+0x29a/0xa80 kernel/irq/handle.c:158 handle_irq_event_percpu kernel/irq/handle.c:193 [inline] handle_irq_event+0x89/0x1f0 kernel/irq/handle.c:210 handle_fasteoi_irq+0x48a/0xae0 kernel/irq/chip.c:720 generic_handle_irq_desc include/linux/irqdesc.h:173 [inline] handle_irq arch/x86/kernel/irq.c:247 [inline] call_irq_handler arch/x86/kernel/irq.c:259 [inline] __common_interrupt+0x136/0x230 arch/x86/kernel/irq.c:285 common_interrupt+0xb4/0xd0 arch/x86/kernel/irq.c:278 </IRQ>Reported-by [email protected]Fixes 66150d0dde03 ("bpf, lpm: Make locking RT friendly")Signed-off-by Kunwu Chan <[email protected]>--- kernel/bpf/lpm_trie.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-)Quoted 12 lines
kernel/bpf/lpm_trie.c struct lpm_trie { · line 39
Quoted 11 lines
kernel/bpf/lpm_trie.c +1
-1@@ -35,7 +35,7 @@ struct lpm_trie {size_t n_entries;size_t max_prefixlen;size_t data_size; -spinlock_t lock; +raw_spinlock_t lock; };We're certainly not going back.
Quoted 7 lines
Only switching from
spinlock_ttoraw_spinlock_tis not enough, running it underPREEMPT_RTafter the change will still trigger the similar lockdep warning. That is becausekmalloc()may acquire aspinlock_tas well. However, after changing the kmalloc and its variants to bpf memory allocator, I think the switch toraw_spinlock_twill be safe. I have already written a draft patch set. Will post after after polishing and testing it. WDYT ?
Switching lpm to bpf_mem_alloc would address the issue. Why do you want a switch to raw_spin_lock as well? kfree_rcu() is already done outside of the lock.
Hi,
Quoted 124 lines · Alexei Starovoitov
Quoted 116 lines · Hou Tao
Hi Alexei,
Quoted 56 lines · Alexei Starovoitov
Quoted 39 lines · Kunwu Chan
From: Kunwu Chan <[email protected]>
When
PREEMPT_RTis enabled, 'spinlock_t' becomes preemptible and bpf program has owned araw_spinlockunder a interrupt handler, which results in invalid lock acquire context.[ BUG: Invalid wait context ] 6.12.0-rc5-next-20241031-syzkaller #0 Not tainted
-----------------------------
swapper/0/0 is trying to lock:ffff8880261e7a00(&trie->lock){....}-{3:3},
at:trie_delete_elem+0x96/0x6a0kernel/bpf/lpm_trie.c:462other info that might help us debug this:
context-{3:3}
5 locks held by swapper/0/0:
#0:ffff888020bb75c8(&vp_dev->lock){-...}-{3:3},
at:vp_vring_interruptdrivers/virtio/virtio_pci_common.c:80[inline]
#0:ffff888020bb75c8(&vp_dev->lock){-...}-{3:3},
at:vp_interrupt+0x142/0x200drivers/virtio/virtio_pci_common.c:113
#1:ffff88814174a120(&vb->stop_update_lock){-...}-{3:3},
at:spin_lockinclude/linux/spinlock.h:351[inline]
#1:ffff88814174a120(&vb->stop_update_lock){-...}-{3:3},
at:stats_request+0x6f/0x230drivers/virtio/virtio_balloon.c:438
#2:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:rcu_lock_acquireinclude/linux/rcupdate.h:337[inline]
#2:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:rcu_read_lockinclude/linux/rcupdate.h:849[inline]
#2:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:__queue_work+0x199/0xf50kernel/workqueue.c:2259
#3:ffff8880b863dd18(&pool->lock){-.-.}-{2:2},
at:__queue_work+0x759/0xf50
#4:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:rcu_lock_acquireinclude/linux/rcupdate.h:337[inline]
#4:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:rcu_read_lockinclude/linux/rcupdate.h:849[inline]
#4:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:__bpf_trace_runkernel/trace/bpf_trace.c:2339[inline]
#4:ffffffff8e939f20(rcu_read_lock){....}-{1:3},
at:bpf_trace_run1+0x1d6/0x520kernel/trace/bpf_trace.c:2380Quoted 16 lines
stack backtrace: CPU: 0 UID: 0 PID: 0 Comm: swapper/0 Not tainted 6.12.0-rc5-next-20241031-syzkaller #0 Hardware name: Google Compute Engine/Google Compute Engine, BIOS Google 09/13/2024 Call Trace: <IRQ> __dump_stack lib/dump_stack.c:94 [inline] dump_stack_lvl+0x241/0x360 lib/dump_stack.c:120 print_lock_invalid_wait_context kernel/locking/lockdep.c:4826 [inline] check_wait_context kernel/locking/lockdep.c:4898 [inline] __lock_acquire+0x15a8/0x2100 kernel/locking/lockdep.c:5176 lock_acquire+0x1ed/0x550 kernel/locking/lockdep.c:5849 __raw_spin_lock_irqsave include/linux/spinlock_api_smp.h:110 [inline] _raw_spin_lock_irqsave+0xd5/0x120 kernel/locking/spinlock.c:162 trie_delete_elem+0x96/0x6a0 kernel/bpf/lpm_trie.c:462Quoted 1 line
This trace is from non-RT kernel where
spin_lock==raw_spin_lock.Yes. However, I think the reason for the warning is that lockdep considers the case is possible under
PREEMPT_RTand it violates the rule of lock [1].Quoted 2 lines
I don't think Hou's explanation earlier is correct.
https://lore.kernel.org/bpf/[email protected]/OK. Is the bpf mem allocator part OK for you ?
Quoted 35 lines
Quoted 9 lines
bpf_prog_2c29ac5cdc6b1842+0x43/0x47 bpf_dispatcher_nop_func include/linux/bpf.h:1290 [inline] __bpf_prog_run include/linux/filter.h:701 [inline] bpf_prog_run include/linux/filter.h:708 [inline] __bpf_trace_run kernel/trace/bpf_trace.c:2340 [inline] bpf_trace_run1+0x2ca/0x520 kernel/trace/bpf_trace.c:2380 trace_workqueue_activate_work+0x186/0x1f0 include/trace/events/workqueue.h:59 __queue_work+0xc7b/0xf50 kernel/workqueue.c:2338 queue_work_on+0x1c2/0x380 kernel/workqueue.c:2390here irqs are disabled, but
raw_spin_lockin lpm should be fine.Quoted 24 lines
queue_work include/linux/workqueue.h:662 [inline] stats_request+0x1a3/0x230 drivers/virtio/virtio_balloon.c:441 vring_interrupt+0x21d/0x380 drivers/virtio/virtio_ring.c:2595 vp_vring_interrupt drivers/virtio/virtio_pci_common.c:82 [inline] vp_interrupt+0x192/0x200 drivers/virtio/virtio_pci_common.c:113 __handle_irq_event_percpu+0x29a/0xa80 kernel/irq/handle.c:158 handle_irq_event_percpu kernel/irq/handle.c:193 [inline] handle_irq_event+0x89/0x1f0 kernel/irq/handle.c:210 handle_fasteoi_irq+0x48a/0xae0 kernel/irq/chip.c:720 generic_handle_irq_desc include/linux/irqdesc.h:173 [inline] handle_irq arch/x86/kernel/irq.c:247 [inline] call_irq_handler arch/x86/kernel/irq.c:259 [inline] __common_interrupt+0x136/0x230 arch/x86/kernel/irq.c:285 common_interrupt+0xb4/0xd0 arch/x86/kernel/irq.c:278 </IRQ>Reported-by [email protected]Fixes 66150d0dde03 ("bpf, lpm: Make locking RT friendly")Signed-off-by Kunwu Chan <[email protected]>--- kernel/bpf/lpm_trie.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-)Quoted 12 lines
kernel/bpf/lpm_trie.c struct lpm_trie { · line 39
Quoted 11 lines
kernel/bpf/lpm_trie.c +1
-1@@ -35,7 +35,7 @@ struct lpm_trie {size_t n_entries;size_t max_prefixlen;size_t data_size; -spinlock_t lock; +raw_spinlock_t lock; };We're certainly not going back.
Quoted 7 lines
Only switching from
spinlock_ttoraw_spinlock_tis not enough, running it underPREEMPT_RTafter the change will still trigger the similar lockdep warning. That is becausekmalloc()may acquire aspinlock_tas well. However, after changing the kmalloc and its variants to bpf memory allocator, I think the switch toraw_spinlock_twill be safe. I have already written a draft patch set. Will post after after polishing and testing it. WDYT ?
Quoted 3 lines
Switching lpm to
bpf_mem_allocwould address the issue. Why do you want a switch toraw_spin_lockas well?kfree_rcu()is already done outside of the lock.
After switching to raw_spinlock_t, the lpm trie could be used under interrupt context even under PREEMPT_RT.
Quoted 1 line
.
Sebastian Sewior
maintainerQuoted 10 lines · Hou Tao
Quoted 7 lines
Quoted 4 lines
well. However, after changing the kmalloc and its variants to bpf memory allocator, I think the switch to
raw_spinlock_twill be safe. I have already written a draft patch set. Will post after after polishing and testing it. WDYT ?Switching lpm to
bpf_mem_allocwould address the issue. Why do you want a switch toraw_spin_lockas well?kfree_rcu()is already done outside of the lock.After switching to
raw_spinlock_t, the lpm trie could be used under interrupt context even underPREEMPT_RT.
I would have to dig why the lock has been moved away from raw_spinlock_t and why we need it back and what changed since. I have some vague memory that there was a test case which added plenty of items and cleaning it up created latency spikes.
Note that interrupts are threaded on PREEMPT_RT. Using it in "interrupt context" would mean you need this in the primary handler/ hardirq.
Sebastian
Quoted 3 lines · Kunwu Chan
When
PREEMPT_RTis enabled, 'spinlock_t' becomes preemptible and bpf program has owned araw_spinlockunder a interrupt handler, which results in invalid lock acquire context.
This explanation is just wrong.
The problem has nothing to do with an interrupt handler. Interrupt handlers on RT kernels are force threaded.
Quoted 11 lines
__raw_spin_lock_irqsave include/linux/spinlock_api_smp.h:110 [inline] _raw_spin_lock_irqsave+0xd5/0x120 kernel/locking/spinlock.c:162 trie_delete_elem+0x96/0x6a0 kernel/bpf/lpm_trie.c:462 bpf_prog_2c29ac5cdc6b1842+0x43/0x47 bpf_dispatcher_nop_func include/linux/bpf.h:1290 [inline] __bpf_prog_run include/linux/filter.h:701 [inline] bpf_prog_run include/linux/filter.h:708 [inline] __bpf_trace_run kernel/trace/bpf_trace.c:2340 [inline] bpf_trace_run1+0x2ca/0x520 kernel/trace/bpf_trace.c:2380 trace_workqueue_activate_work+0x186/0x1f0 include/trace/events/workqueue.h:59 __queue_work+0xc7b/0xf50 kernel/workqueue.c:2338
The problematic lock nesting is the work queue pool lock, which is a raw spinlock.
kernel/bpf/lpm_trie.c static long trie_update_elem(struct bpf_map *map, · line 335
Quoted 8 lines
kernel/bpf/lpm_trie.c +1
-1@@ -330,7 +330,7 @@ static long trie_update_elem(struct bpf_map *map,if (key->prefixlen > trie->max_prefixlen)return -EINVAL ; -spin_lock_irqsave (&trie->lock, irq_flags); +raw_spin_lock_irqsave (&trie->lock, irq_flags);/* Allocate and fill a new node */
Making this a raw spinlock moves the problem from the BPF trie code into the memory allocator. On RT the memory allocator cannot be invoked under a raw spinlock.
Thanks,
tglx
Thanks all for the reply.
Quoted 27 lines · Thomas Gleixner
Quoted 3 lines · Kunwu Chan
When
PREEMPT_RTis enabled, 'spinlock_t' becomes preemptible and bpf program has owned araw_spinlockunder a interrupt handler, which results in invalid lock acquire context.This explanation is just wrong.
The problem has nothing to do with an interrupt handler. Interrupt handlers on RT kernels are force threaded.
Quoted 11 lines
__raw_spin_lock_irqsave include/linux/spinlock_api_smp.h:110 [inline] _raw_spin_lock_irqsave+0xd5/0x120 kernel/locking/spinlock.c:162 trie_delete_elem+0x96/0x6a0 kernel/bpf/lpm_trie.c:462 bpf_prog_2c29ac5cdc6b1842+0x43/0x47 bpf_dispatcher_nop_func include/linux/bpf.h:1290 [inline] __bpf_prog_run include/linux/filter.h:701 [inline] bpf_prog_run include/linux/filter.h:708 [inline] __bpf_trace_run kernel/trace/bpf_trace.c:2340 [inline] bpf_trace_run1+0x2ca/0x520 kernel/trace/bpf_trace.c:2380 trace_workqueue_activate_work+0x186/0x1f0 include/trace/events/workqueue.h:59 __queue_work+0xc7b/0xf50 kernel/workqueue.c:2338The problematic lock nesting is the work queue pool lock, which is a raw spinlock.
Quoted 4 lines
kernel/bpf/lpm_trie.c +0
-0@@ -330,7 +330,7 @@ static long trie_update_elem(struct bpf_map *map,if (key->prefixlen > trie->max_prefixlen)return -EINVAL ;
Quoted 7 lines
kernel/bpf/lpm_trie.c static long trie_update_elem(struct bpf_map *map, · line 335
Quoted 4 lines
kernel/bpf/lpm_trie.c +1
-1-spin_lock_irqsave (&trie->lock, irq_flags); +raw_spin_lock_irqsave (&trie->lock, irq_flags);/* Allocate and fill a new node */ Making this a raw spinlock moves the problem from the BPF trie code into the memory allocator. On RT the memory allocator cannot be invoked under a raw spinlock.
I'am newbiee in this field. But actually when i change it to a raw spinlock, the problem syzbot reported dispeared. If don't change like this, we should do what to deal with this problem, if you have any good idea, pls tell me to do.
Quoted 4 lines
Thanks,
tglx
Signature · 2 lines
Thanks, Kunwu.Chan
Quoted 8 lines · Kunwu Chan
Quoted 7 lines · Thomas Gleixner
Quoted 7 lines
kernel/bpf/lpm_trie.c +1
-1@@ -330,7 +330,7 @@ static long trie_update_elem(struct bpf_map *map,if (key->prefixlen > trie->max_prefixlen)return -EINVAL ; -spin_lock_irqsave (&trie->lock, irq_flags); +raw_spin_lock_irqsave (&trie->lock, irq_flags);
Quoted 6 lines
Quoted 4 lines
kernel/bpf/lpm_trie.c static long trie_update_elem(struct bpf_map *map, · line 335
Quoted 1 line
kernel/bpf/lpm_trie.c +0
-0/* Allocate and fill a new node */ Making this a raw spinlock moves the problem from the BPF trie code into the memory allocator. On RT the memory allocator cannot be invoked under a raw spinlock.
I'am newbiee in this field. But actually when i change it to a raw spinlock, the problem syzbot reported dispeared.
Yes, because the actual code path which is going to trigger this, is not reached. But it will be reached at some point.
IIRC, BPF has it's own allocator which can be used everywhere.
Thanks,
tglx
Sebastian Andrzej Siewior
maintainerQuoted 1 line · Thomas Gleixner
IIRC, BPF has it's own allocator which can be used everywhere.
Thomas Weißschuh made something. It appears to work. Need to take a closer look.
Quoted 3 lines
Thanks,
tglx
Sebastian
Quoted 6 lines · Sebastian Andrzej Siewior
Quoted 1 line · Thomas Gleixner
IIRC, BPF has it's own allocator which can be used everywhere.
Thomas Weißschuh made something. It appears to work. Need to take a closer look.
Any more details?bpf_mem_alloc is a stop gap.
As Vlastimil Babka suggested long ago:
https://lwn.net/Articles/974138/
"...next on the target list is the special allocator used by the BPF subsystem. This allocator is intended to succeed in any calling context, including in non-maskable interrupts (NMIs). BPF maintainer Alexei Starovoitov is evidently in favor of this removal if SLUB is able to handle the same use cases..."
Here is the first step:
https://lore.kernel.org/bpf/[email protected]/
Quoted 11 lines · Alexei Starovoitov
Quoted 6 lines · Sebastian Andrzej Siewior
Quoted 1 line · Thomas Gleixner
IIRC, BPF has it's own allocator which can be used everywhere.
Thomas Weißschuh made something. It appears to work. Need to take a closer look.
Any more details?
bpf_mem_allocis a stop gap.
It is indeed using bpf_mem_alloc.
It is a fairly straightforward conversion, using one cache for intermediate and one for non-intermediate nodes.
I'll try to send it early next week.
Quoted 10 lines
As Vlastimil Babka suggested long ago:
https://lwn.net/Articles/974138/
"...next on the target list is the special allocator used by the BPF subsystem. This allocator is intended to succeed in any calling context, including in non-maskable interrupts (NMIs). BPF maintainer Alexei Starovoitov is evidently in favor of this removal if SLUB is able to handle the same use cases..."Here is the first step:
https://lore.kernel.org/bpf/[email protected]/
Quoted 11 lines · Thomas Weißschuh
Quoted 9 lines · Alexei Starovoitov
Quoted 6 lines · Sebastian Andrzej Siewior
Quoted 1 line · Thomas Gleixner
IIRC, BPF has it's own allocator which can be used everywhere.
Thomas Weißschuh made something. It appears to work. Need to take a closer look.
Quoted 6 lines
Quoted 2 lines
Any more details?
bpf_mem_allocis a stop gap.It is indeed using
bpf_mem_alloc.
It is a fairly straightforward conversion, using one cache for intermediate and one for non-intermediate nodes.
Sounds like you're proposing to allocate two lpm specific bpf_ma-s ? Just use bpf_global_ma.
More ma-s means more memory pinned in bpf specific freelists. That's the main reason to teach slub and page_alloc about bpf requirements. All memory should be shared by all subsystems.
Custom memory pools / freelists, whether it's bpf, networking or whatever else, is a pain point for somebody.
The kernel needs to be optimal for all use cases.
Quoted 1 line
I'll try to send it early next week.
Looking forward.
Quoted 10 lines
Quoted 10 lines
As Vlastimil Babka suggested long ago:
https://lwn.net/Articles/974138/
"...next on the target list is the special allocator used by the BPF subsystem. This allocator is intended to succeed in any calling context, including in non-maskable interrupts (NMIs). BPF maintainer Alexei Starovoitov is evidently in favor of this removal if SLUB is able to handle the same use cases..."Here is the first step:
https://lore.kernel.org/bpf/[email protected]/
Hi,
Quoted 13 lines · Alexei Starovoitov
Quoted 4 lines · Thomas Weißschuh
Quoted 3 lines · Alexei Starovoitov
Quoted 1 line · Sebastian Andrzej Siewior
On 2024-11-15 23:29:31 [+0100], Thomas Gleixner wrote:
Quoted 8 lines
Quoted 5 lines
Quoted 3 lines
Quoted 1 line
IIRC, BPF has it's own allocator which can be used everywhere.
Thomas Weißschuh made something. It appears to work. Need to take a closer look.
Any more details?
bpf_mem_allocis a stop gap.It is indeed using
bpf_mem_alloc.
It is a fairly straightforward conversion, using one cache for intermediate and one for non-intermediate nodes.
Quoted 8 lines
Sounds like you're proposing to allocate two lpm specific bpf_ma-s ? Just use
bpf_global_ma.
More ma-s means more memory pinned in bpf specific freelists. That's the main reason to teach slub andpage_allocabout bpf requirements. All memory should be shared by all subsystems.
Custom memory pools / freelists, whether it's bpf, networking or whatever else, is a pain point for somebody.
The kernel needs to be optimal for all use cases.
I have been working on it since last week [1] and have already written a patch (a patch in a patch set) for it. In my patch, these two allocators will be merged if they are mergable and now the merge is decided by the return value of kmalloc_size_roundup(). Also considering about using bpf_global_ma instead, but the biggest problem for bpf_global_ma is the memory accounting. The allocated memory will be accounted under root memory cgroup instead of the memory cgroup of users.
[1]:
https://lore.kernel.org/bpf/[email protected]/
Quoted 16 lines
Quoted 2 lines
I'll try to send it early next week.
Looking forward.
Quoted 10 lines
Quoted 10 lines
As Vlastimil Babka suggested long ago:
https://lwn.net/Articles/974138/
"...next on the target list is the special allocator used by the BPF subsystem. This allocator is intended to succeed in any calling context, including in non-maskable interrupts (NMIs). BPF maintainer Alexei Starovoitov is evidently in favor of this removal if SLUB is able to handle the same use cases..."Here is the first step:
https://lore.kernel.org/bpf/[email protected]/.