bpf: do not use bucket_lock for hashmap iterator
Subsystems (5)
cover bpf: do not use bucket_lock for hashmap iterator
Currently, the bpf hashmap iterator takes a bucket_lock, a spin_lock, before visiting each element in the bucket. This will cause a deadlock if a map update/delete operates on an element with the same bucket id of the visited map.
To avoid the deadlock, let us just use rcu_read_lock instead of bucket_lock. This may result in visiting stale elements, missing some elements, or repeating some elements, if concurrent map delete/update happens for the same map. I think using rcu_read_lock is a reasonable compromise. For users caring stale/missing/repeating element issues, bpf map batch access syscall interface can be used.
Note that another approach is during bpf_iter link stage, we check whether the iter program might be able to do update/delete to the visited map. If it is, reject the link_create. Verifier needs to record whether an update/delete operation happens for each map for this approach. I just feel this checking is too specialized, hence still prefer rcu_read_lock approach.
Patch #1 has the kernel implementation and Patch #2 added a selftest which can trigger deadlock without Patch #1.
Yonghong Song (2):
bpf: do not use bucket_lock for hashmap iterator selftests/bpf: add bpf_{update,delete}_map_elem in hashmap iter
program
kernel/bpf/hashtab.c | 15 ++++----------- .../selftests/bpf/progs/bpf_iter_bpf_hash_map.c | 15 +++++++++++++++ 2 files changed, 19 insertions(+), 11 deletions(-)
Signature · 1 line
2.24.1
PATCH 1/2 bpf: do not use bucket_lock for hashmap iterator
Currently, for hashmap, the bpf iterator will grab a bucket lock, a spinlock, before traversing the elements in the bucket. This can ensure all bpf visted elements are valid. But this mechanism may cause deadlock if update/deletion happens to the same bucket of the visited map in the program. For example, if we added bpf_map_update_elem() call to the same visited element in selftests bpf_iter_bpf_hash_map.c, we will have the following deadlock:
============================================
WARNING: possible recursive locking detected
5.9.0-rc1+ #841 Not tainted
--------------------------------------------
test_progs/1750 is trying to acquire lock:
ffff9a5bb73c5e70 (&htab->buckets[i].raw_lock){....}-{2:2}, at: htab_map_update_elem+0x1cf/0x410
but task is already holding lock:
ffff9a5bb73c5e20 (&htab->buckets[i].raw_lock){....}-{2:2}, at: bpf_hash_map_seq_find_next+0x94/0x120
other info that might help us debug this:
Possible unsafe locking scenario:
CPU0
----
lock(&htab->buckets[i].raw_lock);
lock(&htab->buckets[i].raw_lock); *** DEADLOCK ***
...
Call Trace: dump_stack+0x78/0xa0 __lock_acquire.cold.74+0x209/0x2e3 lock_acquire+0xba/0x380 ? htab_map_update_elem+0x1cf/0x410 ? __lock_acquire+0x639/0x20c0 _raw_spin_lock_irqsave+0x3b/0x80 ? htab_map_update_elem+0x1cf/0x410 htab_map_update_elem+0x1cf/0x410 ? lock_acquire+0xba/0x380 bpf_prog_ad6dab10433b135d_dump_bpf_hash_map+0x88/0xa9c ? find_held_lock+0x34/0xa0 bpf_iter_run_prog+0x81/0x16e __bpf_hash_map_seq_show+0x145/0x180 bpf_seq_read+0xff/0x3d0 vfs_read+0xad/0x1c0 ksys_read+0x5f/0xe0 do_syscall_64+0x33/0x40 entry_SYSCALL_64_after_hwframe+0x44/0xa9 ...
The bucket_lock first grabbed in seq_ops->next() called by bpf_seq_read(), and then grabbed again in htab_map_update_elem() in the bpf program, causing deadlocks.
Actually, we do not need bucket_lock here, we can just use rcu_read_lock() similar to netlink iterator where the rcu_read_{lock,unlock} likes below:
seq_ops->start():
rcu_read_lock();
seq_ops->next():
rcu_read_unlock();
/* next element */
rcu_read_lock();
seq_ops->stop();
rcu_read_unlock();Compared to old bucket_lock mechanism, if concurrent updata/delete happens, we may visit stale elements, miss some elements, or repeat some elements. I think this is a reasonable compromise. For users wanting to avoid stale, missing/repeated accesses, bpf_map batch access syscall interface can be used.
--- kernel/bpf/hashtab.c | 15 ++++----------- 1 file changed, 4 insertions(+), 11 deletions(-)
kernel/bpf/hashtab.c +4 -11
@@ -1622,7 +1622,6 @@ struct bpf_iter_seq_hash_map_info {struct bpf_map *map;struct bpf_htab *htab;void *percpu_value_buf;// non-zero means percpu hash -unsigned long flags;u32 bucket_id;u32 skip_elems; };
@@ -1632,7 +1631,6 @@ bpf_hash_map_seq_find_next(struct bpf_iter_seq_hash_map_info *info, struct htab_elem *prev_elem) {const struct bpf_htab *htab = info->htab; -unsigned long flags = info->flags;u32 skip_elems = info->skip_elems;u32 bucket_id = info->bucket_id;struct hlist_nulls_head *head;
@@ -1656,19 +1654,18 @@ bpf_hash_map_seq_find_next(struct bpf_iter_seq_hash_map_info *info,/* not found, unlock and go to the next bucket */ b = &htab->buckets[bucket_id++]; -htab_unlock_bucket (htab, b, flags); +rcu_read_unlock (); skip_elems =0 ; }for (i = bucket_id; i < htab->n_buckets; i++) { b = &htab->buckets[i]; - flags =htab_lock_bucket (htab, b); +rcu_read_lock (); count =0 ; head = &b->head;hlist_nulls_for_each_entry_rcu (elem, n, head, hash_node) {if (count >= skip_elems) { - info->flags = flags; info->bucket_id = i; info->skip_elems = count;return elem;
@@ -1676,7 +1673,7 @@ bpf_hash_map_seq_find_next(struct bpf_iter_seq_hash_map_info *info, count++; } -htab_unlock_bucket (htab, b, flags); +rcu_read_unlock (); skip_elems =0 ; }
@@ -1754,14 +1751,10 @@ static int bpf_hash_map_seq_show(struct seq_file *seq, void *v)static void bpf_hash_map_seq_stop (struct seq_file *seq,void *v) { -struct bpf_iter_seq_hash_map_info *info = seq->private; -if (!v) (void )__bpf_hash_map_seq_show (seq,NULL );else -htab_unlock_bucket (info->htab, - &info->htab->buckets[info->bucket_id], - info->flags); +rcu_read_unlock (); } static int bpf_iter_init_hash_map(void *priv_data,
Signature · 1 line
2.24.1
Quoted 9 lines · Yonghong Song
Currently, for hashmap, the bpf iterator will grab a bucket lock, a spinlock, before traversing the elements in the bucket. This can ensure all bpf visted elements are valid. But this mechanism may cause deadlock if update/deletion happens to the same bucket of the visited map in the program. For example, if we added
bpf_map_update_elem()call to the same visited element in selftestsbpf_iter_bpf_hash_map.c, we will have the following deadlock:
[...]
Quoted 4 lines
Compared to old
bucket_lockmechanism, if concurrent updata/delete happens, we may visit stale elements, miss some elements, or repeat some elements. I think this is a reasonable compromise. For users wanting to avoid
I agree, the only reliable way to iterate map without duplicates and missed elements is to not update that map during iteration (unless we start supporting point-in-time snapshots, which is a very different matter).
Quoted 29 lines
stale, missing/repeated accesses,
bpf_mapbatch access syscall interface can be used.Signed-off-by Yonghong Song <[email protected]>--- kernel/bpf/hashtab.c | 15 ++++----------- 1 file changed, 4 insertions(+), 11 deletions(-)kernel/bpf/hashtab.c +0
-2@@ -1622,7 +1622,6 @@ struct bpf_iter_seq_hash_map_info {struct bpf_map *map;struct bpf_htab *htab;void *percpu_value_buf;// non-zero means percpu hash -unsigned long flags;u32 bucket_id;u32 skip_elems; };@@ -1632,7 +1631,6 @@ bpf_hash_map_seq_find_next(struct bpf_iter_seq_hash_map_info *info, struct htab_elem *prev_elem) {const struct bpf_htab *htab = info->htab; -unsigned long flags = info->flags;u32 skip_elems = info->skip_elems;u32 bucket_id = info->bucket_id;struct hlist_nulls_head *head;
kernel/bpf/hashtab.c bpf_hash_map_seq_find_next(struct bpf_iter_seq_hash_map_info *info, · line 1657
Quoted 5 lines
kernel/bpf/hashtab.c +1
-1@@ -1656,19 +1654,18 @@ bpf_hash_map_seq_find_next(struct bpf_iter_seq_hash_map_info *info,/* not found, unlock and go to the next bucket */ b = &htab->buckets[bucket_id++]; -htab_unlock_bucket (htab, b, flags); +rcu_read_unlock ();
Just double checking as I don't yet completely understand all the sleepable BPF implications. If the map is used from a sleepable BPF program, we are still ok doing just rcu_read_lock/rcu_read_unlock when accessing BPF map elements, right? No need for extra rcu_read_lock_trace/rcu_read_unlock_trace?
Quoted 3 lines
kernel/bpf/hashtab.c +0
-0skip_elems =0 ; }
[...]
Quoted 54 lines · Andrii Nakryiko
Quoted 9 lines · Yonghong Song
Currently, for hashmap, the bpf iterator will grab a bucket lock, a spinlock, before traversing the elements in the bucket. This can ensure all bpf visted elements are valid. But this mechanism may cause deadlock if update/deletion happens to the same bucket of the visited map in the program. For example, if we added
bpf_map_update_elem()call to the same visited element in selftestsbpf_iter_bpf_hash_map.c, we will have the following deadlock:[...]
Quoted 4 lines
Compared to old
bucket_lockmechanism, if concurrent updata/delete happens, we may visit stale elements, miss some elements, or repeat some elements. I think this is a reasonable compromise. For users wanting to avoidI agree, the only reliable way to iterate map without duplicates and missed elements is to not update that map during iteration (unless we start supporting point-in-time snapshots, which is a very different matter).
Quoted 30 lines
stale, missing/repeated accesses,
bpf_mapbatch access syscall interface can be used.Signed-off-by Yonghong Song <[email protected]>--- kernel/bpf/hashtab.c | 15 ++++----------- 1 file changed, 4 insertions(+), 11 deletions(-)kernel/bpf/hashtab.c +0
-2@@ -1622,7 +1622,6 @@ struct bpf_iter_seq_hash_map_info {struct bpf_map *map;struct bpf_htab *htab;void *percpu_value_buf;// non-zero means percpu hash -unsigned long flags;u32 bucket_id;u32 skip_elems; };@@ -1632,7 +1631,6 @@ bpf_hash_map_seq_find_next(struct bpf_iter_seq_hash_map_info *info, struct htab_elem *prev_elem) {const struct bpf_htab *htab = info->htab; -unsigned long flags = info->flags;u32 skip_elems = info->skip_elems;u32 bucket_id = info->bucket_id;struct hlist_nulls_head *head;@@ -1656,19 +1654,18 @@ bpf_hash_map_seq_find_next(struct bpf_iter_seq_hash_map_info *info,
Quoted 10 lines
kernel/bpf/hashtab.c bpf_hash_map_seq_find_next(struct bpf_iter_seq_hash_map_info *info, · line 1657
Quoted 4 lines
kernel/bpf/hashtab.c +1
-1/* not found, unlock and go to the next bucket */ b = &htab->buckets[bucket_id++]; -htab_unlock_bucket (htab, b, flags); +rcu_read_unlock ();Just double checking as I don't yet completely understand all the sleepable BPF implications. If the map is used from a sleepable BPF program, we are still ok doing just rcu_read_lock/rcu_read_unlock when accessing BPF map elements, right? No need for extra rcu_read_lock_trace/rcu_read_unlock_trace?
I think it is fine now since currently bpf_iter program cannot be sleepable and the current sleepable program framework already allows the following scenario.
- map1 is a preallocated hashmap shared by two programs,
prog1_nosleep and prog2_sleepable
... ...rcu_read_lock() rcu_read_lock_trace()
run prog1_nosleep run prog2_sleepable
lookup/update/delete map1 elem lookup/update/delete map1 elemrcu_read_unlock() rcu_read_unlock_trace()
... ...
The prog1_nosleep could be a bpf_iter program or a networking problem.
Alexei, could you confirm the above scenario is properly supported now?
Quoted 7 lines
Quoted 4 lines
kernel/bpf/hashtab.c +0
-0skip_elems =0 ; }[...]
Quoted 73 lines · Yonghong Song
Quoted 54 lines · Andrii Nakryiko
Quoted 9 lines · Yonghong Song
Currently, for hashmap, the bpf iterator will grab a bucket lock, a spinlock, before traversing the elements in the bucket. This can ensure all bpf visted elements are valid. But this mechanism may cause deadlock if update/deletion happens to the same bucket of the visited map in the program. For example, if we added
bpf_map_update_elem()call to the same visited element in selftestsbpf_iter_bpf_hash_map.c, we will have the following deadlock:[...]
Quoted 4 lines
Compared to old
bucket_lockmechanism, if concurrent updata/delete happens, we may visit stale elements, miss some elements, or repeat some elements. I think this is a reasonable compromise. For users wanting to avoidI agree, the only reliable way to iterate map without duplicates and missed elements is to not update that map during iteration (unless we start supporting point-in-time snapshots, which is a very different matter).
Quoted 30 lines
stale, missing/repeated accesses,
bpf_mapbatch access syscall interface can be used.Signed-off-by Yonghong Song <[email protected]>--- kernel/bpf/hashtab.c | 15 ++++----------- 1 file changed, 4 insertions(+), 11 deletions(-)kernel/bpf/hashtab.c +0
-2@@ -1622,7 +1622,6 @@ struct bpf_iter_seq_hash_map_info {struct bpf_map *map;struct bpf_htab *htab;void *percpu_value_buf;// non-zero means percpu hash -unsigned long flags;u32 bucket_id;u32 skip_elems; };@@ -1632,7 +1631,6 @@ bpf_hash_map_seq_find_next(struct bpf_iter_seq_hash_map_info *info, struct htab_elem *prev_elem) {const struct bpf_htab *htab = info->htab; -unsigned long flags = info->flags;u32 skip_elems = info->skip_elems;u32 bucket_id = info->bucket_id;struct hlist_nulls_head *head;@@ -1656,19 +1654,18 @@ bpf_hash_map_seq_find_next(struct bpf_iter_seq_hash_map_info *info,Quoted 10 lines
kernel/bpf/hashtab.c bpf_hash_map_seq_find_next(struct bpf_iter_seq_hash_map_info *info, · line 1657
Quoted 4 lines
kernel/bpf/hashtab.c +1
-1/* not found, unlock and go to the next bucket */ b = &htab->buckets[bucket_id++]; -htab_unlock_bucket (htab, b, flags); +rcu_read_unlock ();Just double checking as I don't yet completely understand all the sleepable BPF implications. If the map is used from a sleepable BPF program, we are still ok doing just rcu_read_lock/rcu_read_unlock when accessing BPF map elements, right? No need for extra rcu_read_lock_trace/rcu_read_unlock_trace?
I think it is fine now since currently
bpf_iterprogram cannot be sleepable and the current sleepable program framework already allows the following scenario.
- map1 is a preallocated hashmap shared by two programs,prog1_nosleepandprog2_sleepable
Quoted 6 lines
... ...
rcu_read_lock()rcu_read_lock_trace()
runprog1_nosleeprunprog2_sleepable
lookup/update/delete map1 elem lookup/update/delete map1 elemrcu_read_unlock()rcu_read_unlock_trace()
... ...
rcu_trace doesn't protect the map. It protects the program. Even for prog2_sleepable the map is protected by rcu. The whole map including all elements will be freed after both sleepable and non-sleepable progs stop executing. This rcu_read_lock is needed for non-preallocated hash maps where individual elements are rcu protected. See free_htab_elem() doing call_rcu(). When the combination of sleepable progs and non-prealloc hashmap is enabled we would need to revisit this iterator assumption.
PATCH 2/2 selftests/bpf: add bpf_{update,delete}_map_elem in hashmap iter program
In reply to Yonghong SongAdded bpf_{updata,delete}_map_elem to the very map element the iter program is visiting. Due to rcu protection, the visited map elements, although stale, should still contain correct values.
$ ./test_progs -n 4/18 #4/18 bpf_hash_map:OK #4 bpf_iter:OK Summary: 1/1 PASSED, 0 SKIPPED, 0 FAILED
--- .../selftests/bpf/progs/bpf_iter_bpf_hash_map.c | 15 +++++++++++++++ 1 file changed, 15 insertions(+)
tools/testing/selftests/bpf/progs/bpf_iter_bpf_hash_map.c +15 -0
@@ -47,7 +47,10 @@ int dump_bpf_hash_map(struct bpf_iter__bpf_map_elem *ctx)__u32 seq_num = ctx->meta->seq_num;struct bpf_map *map = ctx->map;struct key_t *key = ctx->key; +struct key_t tmp_key;__u64 *val = ctx->value; +__u64 tmp_val =0 ; +int ret;if (in_test_mode) {/* test mode is used by selftests to
@@ -61,6 +64,18 @@ int dump_bpf_hash_map(struct bpf_iter__bpf_map_elem *ctx)if (key == (void *)0 || val == (void *)0 )return 0 ; +/* update the value and then delete the <key, value> pair. +* it should not impact the existing 'val' which is still +* accessible under rcu. +*/ +__builtin_memcpy (&tmp_key, key,sizeof (struct key_t )); + ret =bpf_map_update_elem (&hashmap1, &tmp_key, &tmp_val,0 ); +if (ret) +return 0 ; + ret =bpf_map_delete_elem (&hashmap1, &tmp_key); +if (ret) +return 0 ; + key_sum_a += key->a; key_sum_b += key->b; key_sum_c += key->c;
Signature · 1 line
2.24.1
Alexei Starovoitov
AppliedQuoted 20 lines · Yonghong Song
Currently, the bpf hashmap iterator takes a
bucket_lock, aspin_lock, before visiting each element in the bucket. This will cause a deadlock if a map update/delete operates on an element with the same bucket id of the visited map.To avoid the deadlock, let us just use
rcu_read_lockinstead ofbucket_lock. This may result in visiting stale elements, missing some elements, or repeating some elements, if concurrent map delete/update happens for the same map. I think usingrcu_read_lockis a reasonable compromise. For users caring stale/missing/repeating element issues, bpf map batch access syscall interface can be used.Note that another approach is during
bpf_iterlink stage, we check whether the iter program might be able to do update/delete to the visited map. If it is, reject thelink_create. Verifier needs to record whether an update/delete operation happens for each map for this approach. I just feel this checking is too specialized, hence still preferrcu_read_lockapproach.
Quoted 2 lines
Patch #1 has the kernel implementation and Patch #2 added a selftest which can trigger deadlock without Patch #1.
Applied. Thanks