Fix lockdep warning for htab of map
Subsystems (3)
cover Fix lockdep warning for htab of map
From: Hou Tao <[email protected]>
Hi,
The patch set fixes a lockdep warning for htab of map. The warning is found when running test_maps. The warning occurs when htab_put_fd_value() attempts to acquire map_idr_lock to free the map id of the inner map while already holding the bucket lock (raw_spinlock_t).
The fix moves the invocation of free_htab_elem() after htab_unlock_bucket() and adds a test case to verify the solution. Please see the individual patches for details. Comments are always welcome.
Hou Tao (3):
bpf: Call free_htab_elem() after htab_unlock_bucket() selftests/bpf: Move ENOTSUPP from bpf_util.h selftests/bpf: Test the update operations for htab of maps
kernel/bpf/hashtab.c | 56 +++++--- tools/testing/selftests/bpf/bpf_util.h | 4 + .../selftests/bpf/prog_tests/bpf_tcp_ca.c | 4 - .../selftests/bpf/prog_tests/lsm_cgroup.c | 4 - .../selftests/bpf/prog_tests/map_in_map.c | 132 +++++++++++++++++- .../selftests/bpf/prog_tests/sock_addr.c | 4 - .../selftests/bpf/progs/update_map_in_htab.c | 30 ++++ tools/testing/selftests/bpf/test_maps.c | 4 - tools/testing/selftests/bpf/test_verifier.c | 4 - 9 files changed, 204 insertions(+), 38 deletions(-) create mode 100644 tools/testing/selftests/bpf/progs/update_map_in_htab.c
Signature · 1 line
2.29.2
PATCH 1/3 bpf: Call free_htab_elem() after htab_unlock_bucket()
From: Hou Tao <[email protected]>
For htab of maps, when the map is removed from the htab, it may hold the last reference of the map. bpf_map_fd_put_ptr() will invoke bpf_map_free_id() to free the id of the removed map element. However, bpf_map_fd_put_ptr() is invoked while holding a bucket lock (raw_spin_lock_t), and bpf_map_free_id() attempts to acquire map_idr_lock (spinlock_t), triggering the following lockdep warning:
=============================
[ BUG: Invalid wait context ]
6.11.0-rc4+ #49 Not tainted
-----------------------------
test_maps/4881 is trying to lock:
ffffffff84884578 (map_idr_lock){+...}-{3:3}, at: bpf_map_free_id.part.0+0x21/0x70 other info that might help us debug this:
context-{5:5}
2 locks held by test_maps/4881:
#0: ffffffff846caf60 (rcu_read_lock){....}-{1:3}, at: bpf_fd_htab_map_update_elem+0xf9/0x270 #1: ffff888149ced148 (&htab->lockdep_key#2){....}-{2:2}, at: htab_map_update_elem+0x178/0xa80
stack backtrace: CPU: 0 UID: 0 PID: 4881 Comm: test_maps Not tainted 6.11.0-rc4+ #49 Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), ... Call Trace: <TASK> dump_stack_lvl+0x6e/0xb0 dump_stack+0x10/0x20 __lock_acquire+0x73e/0x36c0 lock_acquire+0x182/0x450 _raw_spin_lock_irqsave+0x43/0x70 bpf_map_free_id.part.0+0x21/0x70 bpf_map_put+0xcf/0x110 bpf_map_fd_put_ptr+0x9a/0xb0 free_htab_elem+0x69/0xe0 htab_map_update_elem+0x50f/0xa80 bpf_fd_htab_map_update_elem+0x131/0x270 htab_map_update_elem+0x50f/0xa80 bpf_fd_htab_map_update_elem+0x131/0x270 bpf_map_update_value+0x266/0x380 __sys_bpf+0x21bb/0x36b0 __x64_sys_bpf+0x45/0x60 x64_sys_call+0x1b2a/0x20d0 do_syscall_64+0x5d/0x100 entry_SYSCALL_64_after_hwframe+0x76/0x7e
One way to fix the lockdep warning is using raw_spinlock_t for map_idr_lock as well. However, bpf_map_alloc_id() invokes idr_alloc_cyclic() after acquiring map_idr_lock, it will trigger a similar lockdep warning because the slab's lock (s->cpu_slab->lock) is still a spinlock.
Instead of changing map_idr_lock's type, fix the issue by invoking htab_put_fd_value() after htab_unlock_bucket(). However, only deferring the invocation of htab_put_fd_value() is not enough, because the old map pointers in htab of maps can not be saved during batched deletion. Therefore, also defer the invocation of free_htab_elem(), so these to-be-freed elements could be linked together similar to lru map.
There are four callers for ->map_fd_put_ptr:
(1) alloc_htab_elem() (through htab_put_fd_value())
It invokes ->map_fd_put_ptr() under a raw_spinlock_t. The invocation of htab_put_fd_value() can not simply move after htab_unlock_bucket(), because the old element has already been stashed in htab->extra_elems. It may be reused immediately after htab_unlock_bucket() and the invocation of htab_put_fd_value() after htab_unlock_bucket() may release the newly-added element incorrectly. Therefore, saving the map pointer of the old element for htab of maps before unlocking the bucket and releasing the map_ptr after unlock. Beside the map pointer in the old element, should do the same thing for the special fields in the old element as well.
(2) free_htab_elem() (through htab_put_fd_value())
Its caller includes __htab_map_lookup_and_delete_elem(), htab_map_delete_elem() and __htab_map_lookup_and_delete_batch().
For htab_map_delete_elem(), simply invoke free_htab_elem() after htab_unlock_bucket(). For __htab_map_lookup_and_delete_batch(), just like lru map, linking the to-be-freed element into node_to_free list and invoking free_htab_elem() for these element after unlock. It is safe to reuse batch_flink as the link for node_to_free, because these elements have been removed from the hash llist.
Because htab of maps doesn't support lookup_and_delete operation, __htab_map_lookup_and_delete_elem() doesn't have the problem, so kept it as is.
(3) fd_htab_map_free()
It invokes ->map_fd_put_ptr without raw_spinlock_t.
(4) bpf_fd_htab_map_update_elem()
It invokes ->map_fd_put_ptr without raw_spinlock_t.
After moving free_htab_elem() outside htab bucket lock scope, using pcpu_freelist_push() instead of __pcpu_freelist_push() to disable the irq before freeing elements, and protecting the invocations of bpf_mem_cache_free() with migrate_{disable|enable} pair.
--- kernel/bpf/hashtab.c | 56 ++++++++++++++++++++++++++++++-------------- 1 file changed, 39 insertions(+), 17 deletions(-)
kernel/bpf/hashtab.c +39 -17
@@ -896,9 +896,12 @@ static int htab_map_get_next_key(struct bpf_map *map, void *key, void *next_key)static void htab_elem_free (struct bpf_htab *htab,struct htab_elem *l) {check_and_free_fields (htab, l); + +migrate_disable ();if (htab->map.map_type ==BPF_MAP_TYPE_PERCPU_HASH )bpf_mem_cache_free (&htab->pcpu_ma, l->ptr_to_pptr);bpf_mem_cache_free (&htab->ma, l); +migrate_enable (); }static void htab_put_fd_value (struct bpf_htab *htab,struct htab_elem *l)
@@ -948,7 +951,7 @@ static void free_htab_elem(struct bpf_htab *htab, struct htab_elem *l)if (htab_is_prealloc (htab)) {bpf_map_dec_elem_count (&htab->map);check_and_free_fields (htab, l); -__pcpu_freelist_push (&htab->freelist, &l->fnode); +pcpu_freelist_push (&htab->freelist, &l->fnode); }else {dec_elem_count (htab);htab_elem_free (htab, l);
@@ -1018,7 +1021,6 @@ static struct htab_elem *alloc_htab_elem(struct bpf_htab *htab, void *key,*/ pl_new =this_cpu_ptr (htab->extra_elems); l_new = *pl_new; -htab_put_fd_value (htab, old_elem); *pl_new = old_elem; }else {struct pcpu_freelist_node *l;
@@ -1105,6 +1107,7 @@ static long htab_map_update_elem(struct bpf_map *map, void *key, void *value,struct htab_elem *l_new =NULL , *l_old;struct hlist_nulls_head *head;unsigned long flags; +void *old_map_ptr;struct bucket *b;u32 key_size, hash;int ret;
@@ -1183,12 +1186,27 @@ static long htab_map_update_elem(struct bpf_map *map, void *key, void *value,hlist_nulls_add_head_rcu (&l_new->hash_node, head);if (l_old) {hlist_nulls_del_rcu (&l_old->hash_node); + +/* l_old has already been stashed in htab->extra_elems, free +* its special fields before it is available for reuse. Also +* save the old map pointer in htab of maps before unlock +* and release it after unlock. +*/ + old_map_ptr =NULL ; +if (htab_is_prealloc (htab)) { +if (map->ops->map_fd_put_ptr) + old_map_ptr =fd_htab_map_get_ptr (map, l_old); +check_and_free_fields (htab, l_old); + } + } +htab_unlock_bucket (htab, b, hash, flags); +if (l_old) { +if (old_map_ptr) + map->ops->map_fd_put_ptr (map, old_map_ptr, true);if (!htab_is_prealloc (htab))free_htab_elem (htab, l_old); -else -check_and_free_fields (htab, l_old); } - ret =0 ; +return 0 ; err:htab_unlock_bucket (htab, b, hash, flags);return ret;
@@ -1432,15 +1450,15 @@ static long htab_map_delete_elem(struct bpf_map *map, void *key)return ret; l =lookup_elem_raw (head, hash, key, key_size); - -if (l) { +if (l)hlist_nulls_del_rcu (&l->hash_node); -free_htab_elem (htab, l); - }else { +else ret = -ENOENT ; - }htab_unlock_bucket (htab, b, hash, flags); + +if (l) +free_htab_elem (htab, l);return ret; }
@@ -1853,13 +1871,14 @@ __htab_map_lookup_and_delete_batch(struct bpf_map *map,* may cause deadlock. See comments in function * prealloc_lru_pop(). Let us do bpf_lru_push_free() * after releasing the bucket lock. +* +* For htab of maps, htab_put_fd_value() in +* free_htab_elem() may acquire a spinlock with bucket +* lock being held and it violates the lock rule, so +* invoke free_htab_elem() after unlock as well. */ -if (is_lru_map) { - l->batch_flink = node_to_free; - node_to_free = l; - }else { -free_htab_elem (htab, l); - } + l->batch_flink = node_to_free; + node_to_free = l; } dst_key += key_size; dst_val += value_size;
@@ -1871,7 +1890,10 @@ __htab_map_lookup_and_delete_batch(struct bpf_map *map,while (node_to_free) { l = node_to_free; node_to_free = node_to_free->batch_flink; -htab_lru_push_free (htab, l); +if (is_lru_map) +htab_lru_push_free (htab, l); +else +free_htab_elem (htab, l); } next_batch:
Signature · 1 line
2.29.2
Re: [PATCH bpf-next 1/3] bpf: Call free_htab_elem() after htab_unlock_bucket()
Quoted 45 lines · Hou Tao
From: Hou Tao <[email protected]>
For htab of maps, when the map is removed from the htab, it may hold the last reference of the map.
bpf_map_fd_put_ptr()will invokebpf_map_free_id()to free the id of the removed map element. However,bpf_map_fd_put_ptr()is invoked while holding a bucket lock (raw_spin_lock_t), andbpf_map_free_id()attempts to acquiremap_idr_lock(spinlock_t), triggering the following lockdep warning:=============================
[ BUG: Invalid wait context ]
6.11.0-rc4+ #49 Not tainted
-----------------------------
test_maps/4881 is trying to lock:
ffffffff84884578(map_idr_lock){+...}-{3:3}, at: bpf_map_free_id.part.0+0x21/0x70 other info that might help us debug this:
context-{5:5}
2 locks held by test_maps/4881:#0: ffffffff846caf60 (rcu_read_lock){....}-{1:3}, at: bpf_fd_htab_map_update_elem+0xf9/0x270 #1: ffff888149ced148 (&htab->lockdep_key#2){....}-{2:2}, at: htab_map_update_elem+0x178/0xa80 stack backtrace: CPU: 0 UID: 0 PID: 4881 Comm: test_maps Not tainted 6.11.0-rc4+ #49 Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), ... Call Trace: <TASK> dump_stack_lvl+0x6e/0xb0 dump_stack+0x10/0x20 __lock_acquire+0x73e/0x36c0 lock_acquire+0x182/0x450 _raw_spin_lock_irqsave+0x43/0x70 bpf_map_free_id.part.0+0x21/0x70 bpf_map_put+0xcf/0x110 bpf_map_fd_put_ptr+0x9a/0xb0 free_htab_elem+0x69/0xe0 htab_map_update_elem+0x50f/0xa80 bpf_fd_htab_map_update_elem+0x131/0x270 htab_map_update_elem+0x50f/0xa80 bpf_fd_htab_map_update_elem+0x131/0x270 bpf_map_update_value+0x266/0x380 __sys_bpf+0x21bb/0x36b0 __x64_sys_bpf+0x45/0x60 x64_sys_call+0x1b2a/0x20d0 do_syscall_64+0x5d/0x100 entry_SYSCALL_64_after_hwframe+0x76/0x7e
Quoted 5 lines
One way to fix the lockdep warning is using
raw_spinlock_tformap_idr_lockas well. However,bpf_map_alloc_id()invokesidr_alloc_cyclic()after acquiringmap_idr_lock, it will trigger a similar lockdep warning because the slab's lock (s->cpu_slab->lock) is still a spinlock.
Is it OK to move the calling of bpf_map_free_id() from bpf_map_put() to bpf_map_free_deferred() ? It could fix the lockdep warning for htab of maps. Its downside is that the free of map id will be delayed, but I think it will not make a visible effect to the user, because the refcnt is already 0, trying to get the map fd through map id will return -ENOENT.
Quoted 179 lines
Instead of changing map_idr_lock's type, fix the issue by invoking
htab_put_fd_value()afterhtab_unlock_bucket(). However, only deferring the invocation ofhtab_put_fd_value()is not enough, because the old map pointers in htab of maps can not be saved during batched deletion. Therefore, also defer the invocation offree_htab_elem(), so these to-be-freed elements could be linked together similar to lru map.There are four callers for ->map_fd_put_ptr:
(1)
alloc_htab_elem()(throughhtab_put_fd_value())
It invokes ->map_fd_put_ptr() under araw_spinlock_t. The invocation ofhtab_put_fd_value()can not simply move afterhtab_unlock_bucket(), because the old element has already been stashed inhtab->extra_elems. It may be reused immediately afterhtab_unlock_bucket()and the invocation ofhtab_put_fd_value()afterhtab_unlock_bucket()may release the newly-added element incorrectly. Therefore, saving the map pointer of the old element for htab of maps before unlocking the bucket and releasing themap_ptrafter unlock. Beside the map pointer in the old element, should do the same thing for the special fields in the old element as well.(2)
free_htab_elem()(throughhtab_put_fd_value())
Its caller includes__htab_map_lookup_and_delete_elem(),htab_map_delete_elem()and__htab_map_lookup_and_delete_batch().For
htab_map_delete_elem(), simply invokefree_htab_elem()afterhtab_unlock_bucket(). For__htab_map_lookup_and_delete_batch(), just like lru map, linking the to-be-freed element intonode_to_freelist and invokingfree_htab_elem()for these element after unlock. It is safe to reusebatch_flinkas the link fornode_to_free, because these elements have been removed from the hash llist.Because htab of maps doesn't support
lookup_and_deleteoperation,__htab_map_lookup_and_delete_elem()doesn't have the problem, so kept it as is.(3)
fd_htab_map_free()
It invokes ->map_fd_put_ptr withoutraw_spinlock_t.(4)
bpf_fd_htab_map_update_elem()
It invokes ->map_fd_put_ptr withoutraw_spinlock_t.After moving
free_htab_elem()outside htab bucket lock scope, usingpcpu_freelist_push()instead of__pcpu_freelist_push()to disable the irq before freeing elements, and protecting the invocations ofbpf_mem_cache_free()with migrate_{disable|enable} pair.Signed-off-by Hou Tao <[email protected]>--- kernel/bpf/hashtab.c | 56 ++++++++++++++++++++++++++++++-------------- 1 file changed, 39 insertions(+), 17 deletions(-)kernel/bpf/hashtab.c +39
-17@@ -896,9 +896,12 @@ static int htab_map_get_next_key(struct bpf_map *map, void *key, void *next_key)static void htab_elem_free (struct bpf_htab *htab,struct htab_elem *l) {check_and_free_fields (htab, l); + +migrate_disable ();if (htab->map.map_type ==BPF_MAP_TYPE_PERCPU_HASH )bpf_mem_cache_free (&htab->pcpu_ma, l->ptr_to_pptr);bpf_mem_cache_free (&htab->ma, l); +migrate_enable (); }static void htab_put_fd_value (struct bpf_htab *htab,struct htab_elem *l)@@ -948,7 +951,7 @@ static void free_htab_elem(struct bpf_htab *htab, struct htab_elem *l)if (htab_is_prealloc (htab)) {bpf_map_dec_elem_count (&htab->map);check_and_free_fields (htab, l); -__pcpu_freelist_push (&htab->freelist, &l->fnode); +pcpu_freelist_push (&htab->freelist, &l->fnode); }else {dec_elem_count (htab);htab_elem_free (htab, l);@@ -1018,7 +1021,6 @@ static struct htab_elem *alloc_htab_elem(struct bpf_htab *htab, void *key,*/ pl_new =this_cpu_ptr (htab->extra_elems); l_new = *pl_new; -htab_put_fd_value (htab, old_elem); *pl_new = old_elem; }else {struct pcpu_freelist_node *l;@@ -1105,6 +1107,7 @@ static long htab_map_update_elem(struct bpf_map *map, void *key, void *value,struct htab_elem *l_new =NULL , *l_old;struct hlist_nulls_head *head;unsigned long flags; +void *old_map_ptr;struct bucket *b;u32 key_size, hash;int ret;@@ -1183,12 +1186,27 @@ static long htab_map_update_elem(struct bpf_map *map, void *key, void *value,hlist_nulls_add_head_rcu (&l_new->hash_node, head);if (l_old) {hlist_nulls_del_rcu (&l_old->hash_node); + +/* l_old has already been stashed in htab->extra_elems, free +* its special fields before it is available for reuse. Also +* save the old map pointer in htab of maps before unlock +* and release it after unlock. +*/ + old_map_ptr =NULL ; +if (htab_is_prealloc (htab)) { +if (map->ops->map_fd_put_ptr) + old_map_ptr =fd_htab_map_get_ptr (map, l_old); +check_and_free_fields (htab, l_old); + } + } +htab_unlock_bucket (htab, b, hash, flags); +if (l_old) { +if (old_map_ptr) + map->ops->map_fd_put_ptr (map, old_map_ptr, true);if (!htab_is_prealloc (htab))free_htab_elem (htab, l_old); -else -check_and_free_fields (htab, l_old); } - ret =0 ; +return 0 ; err:htab_unlock_bucket (htab, b, hash, flags);return ret;@@ -1432,15 +1450,15 @@ static long htab_map_delete_elem(struct bpf_map *map, void *key)return ret; l =lookup_elem_raw (head, hash, key, key_size); - -if (l) { +if (l)hlist_nulls_del_rcu (&l->hash_node); -free_htab_elem (htab, l); - }else { +else ret = -ENOENT ; - }htab_unlock_bucket (htab, b, hash, flags); + +if (l) +free_htab_elem (htab, l);return ret; }@@ -1853,13 +1871,14 @@ __htab_map_lookup_and_delete_batch(struct bpf_map *map,* may cause deadlock. See comments in function * prealloc_lru_pop(). Let us do bpf_lru_push_free() * after releasing the bucket lock. +* +* For htab of maps, htab_put_fd_value() in +* free_htab_elem() may acquire a spinlock with bucket +* lock being held and it violates the lock rule, so +* invoke free_htab_elem() after unlock as well. */ -if (is_lru_map) { - l->batch_flink = node_to_free; - node_to_free = l; - }else { -free_htab_elem (htab, l); - } + l->batch_flink = node_to_free; + node_to_free = l; } dst_key += key_size; dst_val += value_size;@@ -1871,7 +1890,10 @@ __htab_map_lookup_and_delete_batch(struct bpf_map *map,while (node_to_free) { l = node_to_free; node_to_free = node_to_free->batch_flink; -htab_lru_push_free (htab, l); +if (is_lru_map) +htab_lru_push_free (htab, l); +else +free_htab_elem (htab, l); } next_batch:
Re: [PATCH bpf-next 1/3] bpf: Call free_htab_elem() after htab_unlock_bucket()
Quoted 55 lines · Hou Tao
Quoted 45 lines · Hou Tao
From: Hou Tao <[email protected]>
For htab of maps, when the map is removed from the htab, it may hold the last reference of the map.
bpf_map_fd_put_ptr()will invokebpf_map_free_id()to free the id of the removed map element. However,bpf_map_fd_put_ptr()is invoked while holding a bucket lock (raw_spin_lock_t), andbpf_map_free_id()attempts to acquiremap_idr_lock(spinlock_t), triggering the following lockdep warning:=============================
[ BUG: Invalid wait context ]
6.11.0-rc4+ #49 Not tainted
-----------------------------
test_maps/4881 is trying to lock:
ffffffff84884578(map_idr_lock){+...}-{3:3}, at: bpf_map_free_id.part.0+0x21/0x70 other info that might help us debug this:
context-{5:5}
2 locks held by test_maps/4881:#0: ffffffff846caf60 (rcu_read_lock){....}-{1:3}, at: bpf_fd_htab_map_update_elem+0xf9/0x270 #1: ffff888149ced148 (&htab->lockdep_key#2){....}-{2:2}, at: htab_map_update_elem+0x178/0xa80 stack backtrace: CPU: 0 UID: 0 PID: 4881 Comm: test_maps Not tainted 6.11.0-rc4+ #49 Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), ... Call Trace: <TASK> dump_stack_lvl+0x6e/0xb0 dump_stack+0x10/0x20 __lock_acquire+0x73e/0x36c0 lock_acquire+0x182/0x450 _raw_spin_lock_irqsave+0x43/0x70 bpf_map_free_id.part.0+0x21/0x70 bpf_map_put+0xcf/0x110 bpf_map_fd_put_ptr+0x9a/0xb0 free_htab_elem+0x69/0xe0 htab_map_update_elem+0x50f/0xa80 bpf_fd_htab_map_update_elem+0x131/0x270 htab_map_update_elem+0x50f/0xa80 bpf_fd_htab_map_update_elem+0x131/0x270 bpf_map_update_value+0x266/0x380 __sys_bpf+0x21bb/0x36b0 __x64_sys_bpf+0x45/0x60 x64_sys_call+0x1b2a/0x20d0 do_syscall_64+0x5d/0x100 entry_SYSCALL_64_after_hwframe+0x76/0x7eQuoted 5 lines
One way to fix the lockdep warning is using
raw_spinlock_tformap_idr_lockas well. However,bpf_map_alloc_id()invokesidr_alloc_cyclic()after acquiringmap_idr_lock, it will trigger a similar lockdep warning because the slab's lock (s->cpu_slab->lock) is still a spinlock.
Quoted 5 lines
Is it OK to move the calling of
bpf_map_free_id()frombpf_map_put()tobpf_map_free_deferred()? It could fix the lockdep warning for htab of maps. Its downside is that the free of map id will be delayed, but I think it will not make a visible effect to the user, because the refcnt is already 0, trying to get the map fd through map id will return-ENOENT.
I've applied the current patch, since doing free outside of bucket lock is a good thing to do anyway.
With that no need to move bpf_map_free_id(), right?
At least offload case relies on id being removed immediately. I don't remember what else might care.
Re: [PATCH bpf-next 1/3] bpf: Call free_htab_elem() after htab_unlock_bucket()
Hi,
Quoted 59 lines · Alexei Starovoitov
Quoted 53 lines · Hou Tao
Quoted 45 lines · Hou Tao
From: Hou Tao <[email protected]>
For htab of maps, when the map is removed from the htab, it may hold the last reference of the map.
bpf_map_fd_put_ptr()will invokebpf_map_free_id()to free the id of the removed map element. However,bpf_map_fd_put_ptr()is invoked while holding a bucket lock (raw_spin_lock_t), andbpf_map_free_id()attempts to acquiremap_idr_lock(spinlock_t), triggering the following lockdep warning:=============================
[ BUG: Invalid wait context ]
6.11.0-rc4+ #49 Not tainted
-----------------------------
test_maps/4881 is trying to lock:
ffffffff84884578(map_idr_lock){+...}-{3:3}, at: bpf_map_free_id.part.0+0x21/0x70 other info that might help us debug this:
context-{5:5}
2 locks held by test_maps/4881:#0: ffffffff846caf60 (rcu_read_lock){....}-{1:3}, at: bpf_fd_htab_map_update_elem+0xf9/0x270 #1: ffff888149ced148 (&htab->lockdep_key#2){....}-{2:2}, at: htab_map_update_elem+0x178/0xa80 stack backtrace: CPU: 0 UID: 0 PID: 4881 Comm: test_maps Not tainted 6.11.0-rc4+ #49 Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), ... Call Trace: <TASK> dump_stack_lvl+0x6e/0xb0 dump_stack+0x10/0x20 __lock_acquire+0x73e/0x36c0 lock_acquire+0x182/0x450 _raw_spin_lock_irqsave+0x43/0x70 bpf_map_free_id.part.0+0x21/0x70 bpf_map_put+0xcf/0x110 bpf_map_fd_put_ptr+0x9a/0xb0 free_htab_elem+0x69/0xe0 htab_map_update_elem+0x50f/0xa80 bpf_fd_htab_map_update_elem+0x131/0x270 htab_map_update_elem+0x50f/0xa80 bpf_fd_htab_map_update_elem+0x131/0x270 bpf_map_update_value+0x266/0x380 __sys_bpf+0x21bb/0x36b0 __x64_sys_bpf+0x45/0x60 x64_sys_call+0x1b2a/0x20d0 do_syscall_64+0x5d/0x100 entry_SYSCALL_64_after_hwframe+0x76/0x7eQuoted 5 lines
One way to fix the lockdep warning is using
raw_spinlock_tformap_idr_lockas well. However,bpf_map_alloc_id()invokesidr_alloc_cyclic()after acquiringmap_idr_lock, it will trigger a similar lockdep warning because the slab's lock (s->cpu_slab->lock) is still a spinlock.Quoted 5 lines
Is it OK to move the calling of
bpf_map_free_id()frombpf_map_put()tobpf_map_free_deferred()? It could fix the lockdep warning for htab of maps. Its downside is that the free of map id will be delayed, but I think it will not make a visible effect to the user, because the refcnt is already 0, trying to get the map fd through map id will return-ENOENT.
Quoted 6 lines
I've applied the current patch, since doing free outside of bucket lock is a good thing to do anyway.
With that no need to movebpf_map_free_id(), right?
At least offload case relies on id being removed immediately. I don't remember what else might care.
.
Yes. There is no need to move bpf_map_free_id() after applying the patch. Thanks for the information about offload map. According to the implementation of _bpf_map_offload_destroy(), it seems that it may need to call bpf_map_free_id() twice, so now bpf_map_free_id() frees the immediately and sets map->id as 0.
PATCH 2/3 selftests/bpf: Move ENOTSUPP from bpf_util.h
In reply to Hou TaoFrom: Hou Tao <[email protected]>
Moving the definition of ENOTSUPP into bpf_util.h to remove the duplicated definitions in multiple files.
--- tools/testing/selftests/bpf/bpf_util.h | 4 ++++ tools/testing/selftests/bpf/prog_tests/bpf_tcp_ca.c | 4 ---- tools/testing/selftests/bpf/prog_tests/lsm_cgroup.c | 4 ---- tools/testing/selftests/bpf/prog_tests/sock_addr.c | 4 ---- tools/testing/selftests/bpf/test_maps.c | 4 ---- tools/testing/selftests/bpf/test_verifier.c | 4 ---- 6 files changed, 4 insertions(+), 20 deletions(-)
tools/testing/selftests/bpf/bpf_util.h +4 -0
@@ -59,4 +59,8 @@ static inline void bpf_strlcpy(char *dst, const char *src, size_t sz) (offsetof(TYPE, MEMBER) + sizeof_field(TYPE, MEMBER))#endif +#ifndef ENOTSUPP +#define ENOTSUPP 524 +#endif +#endif /* __BPF_UTIL__ */
tools/testing/selftests/bpf/prog_tests/bpf_tcp_ca.c +0 -4
@@ -16,10 +16,6 @@#include "tcp_ca_kfunc.skel.h" #include "bpf_cc_cubic.skel.h" -#ifndef ENOTSUPP -#define ENOTSUPP 524 -#endif -static const unsigned int total_bytes =10 *1024 *1024 ;static int expected_stg =0xeB9F ;
tools/testing/selftests/bpf/prog_tests/lsm_cgroup.c +0 -4
@@ -10,10 +10,6 @@#include "cgroup_helpers.h" #include "network_helpers.h" -#ifndef ENOTSUPP -#define ENOTSUPP 524 -#endif -static struct btf *btf;static __u32 query_prog_cnt (int cgroup_fd,const char *attach_func)
tools/testing/selftests/bpf/prog_tests/sock_addr.c +0 -4
@@ -23,10 +23,6 @@#include "getpeername_unix_prog.skel.h" #include "network_helpers.h" -#ifndef ENOTSUPP -# define ENOTSUPP 524 -#endif -#define TEST_NS "sock_addr"#define TEST_IF_PREFIX "test_sock_addr"#define TEST_IPV4 "127.0.0.4"
tools/testing/selftests/bpf/test_maps.c +0 -4
@@ -26,10 +26,6 @@#include "test_maps.h" #include "testing_helpers.h" -#ifndef ENOTSUPP -#define ENOTSUPP 524 -#endif -int skips;static struct bpf_map_create_opts map_opts = { .sz =sizeof (map_opts) };
tools/testing/selftests/bpf/test_verifier.c +0 -4
@@ -42,10 +42,6 @@#include "../../../include/linux/filter.h" #include "testing_helpers.h" -#ifndef ENOTSUPP -#define ENOTSUPP 524 -#endif -#define MAX_INSNS BPF_MAXINSNS#define MAX_EXPECTED_INSNS 32#define MAX_UNEXPECTED_INSNS 32
Signature · 1 line
2.29.2
PATCH 3/3 selftests/bpf: Test the update operations for htab of maps
In reply to Hou TaoFrom: Hou Tao <[email protected]>
Add test cases to verify the following four update operations on htab of maps don't trigger lockdep warning:
(1) add then delete
(2) add, overwrite, then delete
(3) add, then lookup_and_delete
(4) add two elements, then lookup_and_delete_batch
Test cases are added for pre-allocated and non-preallocated htab of maps respectively.
--- .../selftests/bpf/prog_tests/map_in_map.c | 132 +++++++++++++++++- .../selftests/bpf/progs/update_map_in_htab.c | 30 ++++ 2 files changed, 161 insertions(+), 1 deletion(-) create mode 100644 tools/testing/selftests/bpf/progs/update_map_in_htab.c
tools/testing/selftests/bpf/prog_tests/map_in_map.c +131 -1
@@ -5,7 +5,9 @@#include <sys/syscall.h> #include <test_progs.h> #include <bpf/btf.h> +#include "access_map_in_map.skel.h" +#include "update_map_in_htab.skel.h" struct thread_ctx {pthread_barrier_t barrier;
@@ -127,6 +129,131 @@ static void test_map_in_map_access(const char *prog_name, const char *map_name)access_map_in_map__destroy (skel); } +static void add_del_fd_htab (int outer_fd) +{ +int inner_fd, err; +int key =1 ; + + inner_fd =bpf_map_create (BPF_MAP_TYPE_ARRAY ,"arr1" ,4 ,4 ,1 ,NULL ); +if (!ASSERT_OK_FD (inner_fd,"inner1" )) +return ; + err =bpf_map_update_elem (outer_fd, &key, &inner_fd,BPF_NOEXIST ); +close (inner_fd); +if (!ASSERT_OK (err,"add" )) +return ; + +/* Delete */ + err =bpf_map_delete_elem (outer_fd, &key); +ASSERT_OK (err,"del" ); +} + +static void overwrite_fd_htab (int outer_fd) +{ +int inner_fd, err; +int key =1 ; + + inner_fd =bpf_map_create (BPF_MAP_TYPE_ARRAY ,"arr1" ,4 ,4 ,1 ,NULL ); +if (!ASSERT_OK_FD (inner_fd,"inner1" )) +return ; + err =bpf_map_update_elem (outer_fd, &key, &inner_fd,BPF_NOEXIST ); +close (inner_fd); +if (!ASSERT_OK (err,"add" )) +return ; + +/* Overwrite */ + inner_fd =bpf_map_create (BPF_MAP_TYPE_ARRAY ,"arr2" ,4 ,4 ,1 ,NULL ); +if (!ASSERT_OK_FD (inner_fd,"inner2" )) + goto out; + err =bpf_map_update_elem (outer_fd, &key, &inner_fd,BPF_EXIST ); +close (inner_fd); +if (!ASSERT_OK (err,"overwrite" )) + goto out; + + err =bpf_map_delete_elem (outer_fd, &key); +ASSERT_OK (err,"del" ); +return ; +out: +bpf_map_delete_elem (outer_fd, &key); +} + +static void lookup_delete_fd_htab (int outer_fd) +{ +int key =1 , value; +int inner_fd, err; + + inner_fd =bpf_map_create (BPF_MAP_TYPE_ARRAY ,"arr1" ,4 ,4 ,1 ,NULL ); +if (!ASSERT_OK_FD (inner_fd,"inner1" )) +return ; + err =bpf_map_update_elem (outer_fd, &key, &inner_fd,BPF_NOEXIST ); +close (inner_fd); +if (!ASSERT_OK (err,"add" )) +return ; + +/* lookup_and_delete is not supported for htab of maps */ + err =bpf_map_lookup_and_delete_elem (outer_fd, &key, &value); +ASSERT_EQ (err, -ENOTSUPP ,"lookup_del" ); + + err =bpf_map_delete_elem (outer_fd, &key); +ASSERT_OK (err,"del" ); +} + +static void batched_lookup_delete_fd_htab (int outer_fd) +{ +int keys[2 ] = {1 ,2 }, values[2 ]; +unsigned int cnt, batch; +int inner_fd, err; + + inner_fd =bpf_map_create (BPF_MAP_TYPE_ARRAY ,"arr1" ,4 ,4 ,1 ,NULL ); +if (!ASSERT_OK_FD (inner_fd,"inner1" )) +return ; + + err =bpf_map_update_elem (outer_fd, &keys[0 ], &inner_fd,BPF_NOEXIST ); +close (inner_fd); +if (!ASSERT_OK (err,"add1" )) +return ; + + inner_fd =bpf_map_create (BPF_MAP_TYPE_ARRAY ,"arr2" ,4 ,4 ,1 ,NULL ); +if (!ASSERT_OK_FD (inner_fd,"inner2" )) + goto out; + err =bpf_map_update_elem (outer_fd, &keys[1 ], &inner_fd,BPF_NOEXIST ); +close (inner_fd); +if (!ASSERT_OK (err,"add2" )) + goto out; + +/* batched lookup_and_delete */ + cnt =ARRAY_SIZE (keys); + err =bpf_map_lookup_and_delete_batch (outer_fd,NULL , &batch, keys, values, &cnt,NULL ); +ASSERT_TRUE ((!err || err == -ENOENT ),"delete_batch ret" ); +ASSERT_EQ (cnt,ARRAY_SIZE (keys),"delete_batch cnt" ); + +out: +bpf_map_delete_elem (outer_fd, &keys[0 ]); +} + +static void test_update_map_in_htab (bool preallocate) +{ +struct update_map_in_htab *skel; +int err, fd; + + skel =update_map_in_htab__open (); +if (!ASSERT_OK_PTR (skel,"open" )) +return ; + + err =update_map_in_htab__load (skel); +if (!ASSERT_OK (err,"load" )) + goto out; + + fd = preallocate ?bpf_map__fd (skel->maps.outer_htab_map) : +bpf_map__fd (skel->maps.outer_alloc_htab_map); + +add_del_fd_htab (fd); +overwrite_fd_htab (fd); +lookup_delete_fd_htab (fd); +batched_lookup_delete_fd_htab (fd); +out: +update_map_in_htab__destroy (skel); +} +void test_map_in_map (void ) {if (test__start_subtest ("acc_map_in_array" ))
@@ -137,5 +264,8 @@ void test_map_in_map(void)test_map_in_map_access ("access_map_in_htab" ,"outer_htab_map" );if (test__start_subtest ("sleepable_acc_map_in_htab" ))test_map_in_map_access ("sleepable_access_map_in_htab" ,"outer_htab_map" ); +if (test__start_subtest ("update_map_in_htab" )) +test_update_map_in_htab (true); +if (test__start_subtest ("update_map_in_alloc_htab" )) +test_update_map_in_htab (false); } -
tools/testing/selftests/bpf/progs/update_map_in_htab.c new file +30 -0
@@ -0,0 +1,30 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (C) 2024. Huawei Technologies Co., Ltd */ +#include <linux/bpf.h> +#include <bpf/bpf_helpers.h> + +struct inner_map_type { + __uint(type, BPF_MAP_TYPE_ARRAY); + __uint(key_size, 4); + __uint(value_size, 4); + __uint(max_entries, 1); +} inner_map SEC(".maps"); + +struct { + __uint(type, BPF_MAP_TYPE_HASH_OF_MAPS); + __type(key, int); + __type(value, int); + __uint(max_entries, 2); + __array(values, struct inner_map_type); +} outer_htab_map SEC(".maps"); + +struct { + __uint(type, BPF_MAP_TYPE_HASH_OF_MAPS); + __uint(map_flags, BPF_F_NO_PREALLOC); + __type(key, int); + __type(value, int); + __uint(max_entries, 2); + __array(values, struct inner_map_type); +} outer_alloc_htab_map SEC(".maps"); + +char _license[] SEC("license") = "GPL";
Signature · 1 line
2.29.2
Quoted 3 lines · Hou Tao
From: Hou Tao <[email protected]>
Hi,
Hi Hou,
Quoted 8 lines
The patch set fixes a lockdep warning for htab of map. The warning is found when running
test_maps. The warning occurs whenhtab_put_fd_value()attempts to acquiremap_idr_lockto free the map id of the inner map while already holding the bucket lock (raw_spinlock_t).The fix moves the invocation of
free_htab_elem()afterhtab_unlock_bucket()and adds a test case to verify the solution. Please see the individual patches for details. Comments are always welcome.
Thank you.
I've seen that you didn't move check_and_free_fields() out of the bucket locked section. Type BPF_TIMER does hrtimer_cancel() if the timer happens to run on a remote CPU. On PREEMPT_RT this will acquire a sleeping lock which is problematic due to the raw_spinlock_t. Would it be okay, to cleanup the timer unconditionally via the workqueue?
Sebastian
Hi,
Quoted 16 lines · Sebastian Andrzej Siewior
Quoted 3 lines · Hou Tao
From: Hou Tao <[email protected]>
Hi,
Hi Hou,
Quoted 8 lines
The patch set fixes a lockdep warning for htab of map. The warning is found when running
test_maps. The warning occurs whenhtab_put_fd_value()attempts to acquiremap_idr_lockto free the map id of the inner map while already holding the bucket lock (raw_spinlock_t).The fix moves the invocation of
free_htab_elem()afterhtab_unlock_bucket()and adds a test case to verify the solution. Please see the individual patches for details. Comments are always welcome.Thank you.
Quoted 8 lines
I've seen that you didn't move
check_and_free_fields()out of the bucket locked section. TypeBPF_TIMERdoeshrtimer_cancel()if the timer happens to run on a remote CPU. OnPREEMPT_RTthis will acquire a sleeping lock which is problematic due to theraw_spinlock_t. Would it be okay, to cleanup the timer unconditionally via the workqueue?
Yes. The patch set still invokes check_and_free_fields() under the bucket lock when updating an existing element in a pre-allocated htab. I missed the hrtimer case. For the sleeping lock, you mean the cpu_base->softirq_expiry_lock in hrtimer_cancel_waiting_running(), right ? Instead of cancelling the timer in workqueue, maybe we could save the old value temporarily in the bucket lock, and try to free it outside of the bucket lock or disabling the extra_elems logic temporarily for the case ?
Quoted 1 line
Sebastian
Quoted 1 line · Hou Tao
Hi,
Hi,
Quoted 4 lines
Yes. The patch set still invokes
check_and_free_fields()under the bucket lock when updating an existing element in a pre-allocated htab. I missed the hrtimer case. For the sleeping lock, you mean thecpu_base->softirq_expiry_lockinhrtimer_cancel_waiting_running(), right
Yes.
Quoted 4 lines
? Instead of cancelling the timer in workqueue, maybe we could save the old value temporarily in the bucket lock, and try to free it outside of the bucket lock or disabling the
extra_elemslogic temporarily for the case ?
Well, it is up to you. Either:
kernel/bpf/helpers.c +1 -4
@@ -1593,10 +1593,7 @@ void bpf_timer_cancel_and_free(void *val)* To avoid these issues, punt to workqueue context when we are in a * timer callback. */ -if (this_cpu_read (hrtimer_running)) -queue_work (system_unbound_wq, &t->cb.delete_work); -else -bpf_timer_delete_work (&t->cb.delete_work); +queue_work (system_unbound_wq, &t->cb.delete_work); }/* This function is called by map_delete/update_elem for individual element and
Or something smarter where you cancel the timer outside of the bucket lock.
Sebastian
Quoted 18 lines · Hou Tao
Hi,
Quoted 14 lines · Sebastian Andrzej Siewior
Quoted 3 lines · Hou Tao
From: Hou Tao <[email protected]>
Hi,
Hi Hou,
Quoted 8 lines
The patch set fixes a lockdep warning for htab of map. The warning is found when running
test_maps. The warning occurs whenhtab_put_fd_value()attempts to acquiremap_idr_lockto free the map id of the inner map while already holding the bucket lock (raw_spinlock_t).The fix moves the invocation of
free_htab_elem()afterhtab_unlock_bucket()and adds a test case to verify the solution. Please see the individual patches for details. Comments are always welcome.
The fix makes sense.
I manually resolved merge conflict and applied.
Quoted 11 lines
Quoted 10 lines
Thank you.
I've seen that you didn't move
check_and_free_fields()out of the bucket locked section. TypeBPF_TIMERdoeshrtimer_cancel()if the timer happens to run on a remote CPU. OnPREEMPT_RTthis will acquire a sleeping lock which is problematic due to theraw_spinlock_t. Would it be okay, to cleanup the timer unconditionally via the workqueue?
Quoted 8 lines
Yes. The patch set still invokes
check_and_free_fields()under the bucket lock when updating an existing element in a pre-allocated htab. I missed the hrtimer case. For the sleeping lock, you mean thecpu_base->softirq_expiry_lockinhrtimer_cancel_waiting_running(), right ? Instead of cancelling the timer in workqueue, maybe we could save the old value temporarily in the bucket lock, and try to free it outside of the bucket lock or disabling theextra_elemslogic temporarily for the case ?
We definitely need to avoid spamming wq when cancelling timers. wq may not be able to handle the volume.
Moving it outside of bucket lock is certainly better.
Hi,
Quoted 15 lines · Alexei Starovoitov
Quoted 14 lines · Hou Tao
Hi,
Quoted 11 lines · Sebastian Andrzej Siewior
Quoted 3 lines · Hou Tao
From: Hou Tao <[email protected]>
Hi,
Hi Hou,
Quoted 5 lines
The patch set fixes a lockdep warning for htab of map. The warning is found when running
test_maps. The warning occurs whenhtab_put_fd_value()attempts to acquiremap_idr_lockto free the map id of the inner map while already holding the bucket lock (raw_spinlock_t).
Quoted 5 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
The fix moves the invocation of
free_htab_elem()afterhtab_unlock_bucket()and adds a test case to verify the solution. Please see the individual patches for details. Comments are always welcome.The fix makes sense.
I manually resolved merge conflict and applied.
Thanks for the manually conflict resolving. However, the patch set doesn't move all free operations outside of lock scope (e.g., for bpf_map_lookup_and_delete()), because htab of maps doesn't support it. I could post another patch set to do that.
Quoted 19 lines
Quoted 11 lines
Quoted 11 lines
Thank you.
I've seen that you didn't move
check_and_free_fields()out of the bucket locked section. TypeBPF_TIMERdoeshrtimer_cancel()if the timer happens to run on a remote CPU. OnPREEMPT_RTthis will acquire a sleeping lock which is problematic due to theraw_spinlock_t. Would it be okay, to cleanup the timer unconditionally via the workqueue?Quoted 8 lines
Yes. The patch set still invokes
check_and_free_fields()under the bucket lock when updating an existing element in a pre-allocated htab. I missed the hrtimer case. For the sleeping lock, you mean thecpu_base->softirq_expiry_lockinhrtimer_cancel_waiting_running(), right ? Instead of cancelling the timer in workqueue, maybe we could save the old value temporarily in the bucket lock, and try to free it outside of the bucket lock or disabling theextra_elemslogic temporarily for the case ?
Quoted 4 lines
We definitely need to avoid spamming wq when cancelling timers. wq may not be able to handle the volume.
Moving it outside of bucket lock is certainly better. .
OK. Will try whether there is a better way to handle the cancelling of timer case.
Quoted 22 lines · Hou Tao
Hi,
Quoted 18 lines · Alexei Starovoitov
Quoted 17 lines · Hou Tao
Hi,
Quoted 14 lines · Sebastian Andrzej Siewior
Quoted 3 lines · Hou Tao
From: Hou Tao <[email protected]>
Hi,
Hi Hou,
Quoted 8 lines
The patch set fixes a lockdep warning for htab of map. The warning is found when running
test_maps. The warning occurs whenhtab_put_fd_value()attempts to acquiremap_idr_lockto free the map id of the inner map while already holding the bucket lock (raw_spinlock_t).The fix moves the invocation of
free_htab_elem()afterhtab_unlock_bucket()and adds a test case to verify the solution. Please see the individual patches for details. Comments are always welcome.
Quoted 7 lines
Quoted 2 lines
The fix makes sense.
I manually resolved merge conflict and applied.Thanks for the manually conflict resolving. However, the patch set doesn't move all free operations outside of lock scope (e.g., for
bpf_map_lookup_and_delete()), because htab of maps doesn't support it. I could post another patch set to do that.
Pls do. It's easier to review incrementally.
For the last year we've been working on "resilient spin lock" and hope to post patches in a couple weeks.
In those patches we will be replacing htab bucket lock with this new lock, so moving other locks out of htab lock region fits very well.
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Hello:
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Quoted 10 lines · On Wed, 6 Nov 2024 14:35:39 +0800 you wrote:
From: Hou Tao <[email protected]>
Hi,
The patch set fixes a lockdep warning for htab of map. The warning is found when running
test_maps. The warning occurs whenhtab_put_fd_value()attempts to acquiremap_idr_lockto free the map id of the inner map while already holding the bucket lock (raw_spinlock_t).[...]
Here is the summary with links:
- [bpf-next,1/3] bpf: Call free_htab_elem() after htab_unlock_bucket()
https://git.kernel.org/bpf/bpf-next/c/81eef03cbf70 - [bpf-next,2/3] selftests/bpf: Move ENOTSUPP from bpf_util.h https://git.kernel.org/bpf/bpf-next/c/7d5e83b4d41b - [bpf-next,3/3] selftests/bpf: Test the update operations for htab of maps https://git.kernel.org/bpf/bpf-next/c/ff605ec69735
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html