Skip to contentSkip to conversation

bpf: do not use bucket_lock for hashmap iterator

PATCH Applied Yonghong Song 3 participants 7 messages Sep 2, 2020 – Sep 4, 2020

Subsystems (5)
lore
Share & tools
lore
#0 lore raw

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
#1 lore raw

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
index 78dfff6a501b..7df28a45c66b 100644
@@ -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
#2 lore raw
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 selftests bpf_iter_bpf_hash_map.c, we will have the following deadlock:

[...]

Quoted 4 lines

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

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_map batch access syscall interface can be used.

---
 kernel/bpf/hashtab.c | 15 ++++-----------
 1 file changed, 4 insertions(+), 11 deletions(-)
kernel/bpf/hashtab.c +0 -2
index 78dfff6a501b..7df28a45c66b 100644
@@ -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 -0
                skip_elems = 0;
        }
 

[...]

#3 lore raw
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 selftests bpf_iter_bpf_hash_map.c, we will have the following deadlock:

[...]

Quoted 4 lines

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

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 30 lines

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 +0 -2
index 78dfff6a501b..7df28a45c66b 100644
@@ -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 elem
rcu_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 -0
                 skip_elems = 0;
         }
 

[...]

#4 lore raw
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 selftests bpf_iter_bpf_hash_map.c, we will have the following deadlock:

[...]

Quoted 4 lines

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

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 30 lines

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 +0 -2
index 78dfff6a501b..7df28a45c66b 100644
@@ -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

Quoted 6 lines

... ...
rcu_read_lock() rcu_read_lock_trace()
run prog1_nosleep run prog2_sleepable
lookup/update/delete map1 elem lookup/update/delete map1 elem
rcu_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.

#5 lore raw

PATCH 2/2 selftests/bpf: add bpf_{update,delete}_map_elem in hashmap iter program

In reply to Yonghong Song

Added 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
index 07ddbfdbcab7..6dfce3fd68bc 100644
@@ -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
#6 lore raw
In reply to Yonghong Song
Quoted 20 lines · Yonghong Song

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.

Quoted 2 lines

Patch #1 has the kernel implementation and Patch #2 added a selftest which can trigger deadlock without Patch #1.

Applied. Thanks