Skip to contentSkip to conversation

Don't reinit map value in prealloc_lru_pop

PATCH Applied Kumar Kartikeya Dwivedi 4 participants 9 messages Aug 9, 2022 – Aug 10, 2022

Subsystems (4)
lore
Share & tools
lore

Kumar Kartikeya Dwivedi

author maintainer
#0 lore raw

v3 cover Don't reinit map value in prealloc_lru_pop

Fix for a bug in prealloc_lru_pop spotted while reading the code, then a test + example that checks whether it is fixed.

Changelog:
----------
v2 -> v3:
v2: https://lore.kernel.org/bpf/[email protected]

* Switch test to use kptr instead of kptr_ref to stabilize test runs
* Fix missing lru_bug__destroy (Yonghong)
* Collect Acks

v1 -> v2:
v1: https://lore.kernel.org/bpf/[email protected]

* Expand commit log to include summary of the discussion with Yonghong
* Make lru_bug selftest serial to not mess up refcount for map_kptr test

Kumar Kartikeya Dwivedi (3):
bpf: Allow calling bpf_prog_test kfuncs in tracing programs
bpf: Don't reinit map value in prealloc_lru_pop selftests/bpf: Add test for prealloc_lru_pop bug

 kernel/bpf/hashtab.c                          |  6 +--
 net/bpf/test_run.c                            |  1 +
 .../selftests/bpf/prog_tests/lru_bug.c        | 21 ++++++++
 tools/testing/selftests/bpf/progs/lru_bug.c   | 49 +++++++++++++++++++
 4 files changed, 72 insertions(+), 5 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/lru_bug.c
 create mode 100644 tools/testing/selftests/bpf/progs/lru_bug.c
Signature · 1 line
2.34.1
author maintainer
#1 lore raw

PATCH v3 1/3 bpf: Allow calling bpf_prog_test kfuncs in tracing programs

In addition to TC hook, enable these in tracing programs so that they can be used in selftests.

---
 net/bpf/test_run.c | 1 +
 1 file changed, 1 insertion(+)
net/bpf/test_run.c +1 -0
index cbc9cd5058cb..d11209367dd0 100644
@@ -1628,6 +1628,7 @@ static int __init bpf_prog_test_run_init(void)
 	int ret;
 
 	ret = register_btf_kfunc_id_set(BPF_PROG_TYPE_SCHED_CLS, &bpf_prog_test_kfunc_set);
+	ret = ret ?: register_btf_kfunc_id_set(BPF_PROG_TYPE_TRACING, &bpf_prog_test_kfunc_set);
 	return ret ?: register_btf_id_dtor_kfuncs(bpf_prog_test_dtor_kfunc,
 						  ARRAY_SIZE(bpf_prog_test_dtor_kfunc),
 						  THIS_MODULE);
Signature · 1 line
2.34.1
author maintainer
#2 lore raw

PATCH v3 2/3 bpf: Don't reinit map value in prealloc_lru_pop

In reply to Kumar Kartikeya Dwivedi

The LRU map that is preallocated may have its elements reused while another program holds a pointer to it from bpf_map_lookup_elem. Hence, only check_and_free_fields is appropriate when the element is being deleted, as it ensures proper synchronization against concurrent access of the map value. After that, we cannot call check_and_init_map_value again as it may rewrite bpf_spin_lock, bpf_timer, and kptr fields while they can be concurrently accessed from a BPF program.

This is safe to do as when the map entry is deleted, concurrent access is protected against by check_and_free_fields, i.e. an existing timer would be freed, and any existing kptr will be released by it. The program can create further timers and kptrs after check_and_free_fields, but they will eventually be released once the preallocated items are freed on map destruction, even if the item is never reused again. Hence, the deleted item sitting in the free list can still have resources attached to it, and they would never leak.

With spin_lock, we never touch the field at all on delete or update, as we may end up modifying the state of the lock. Since the verifier ensures that a bpf_spin_lock call is always paired with bpf_spin_unlock call, the program will eventually release the lock so that on reuse the new user of the value can take the lock.

Essentially, for the preallocated case, we must assume that the map value may always be in use by the program, even when it is sitting in the freelist, and handle things accordingly, i.e. use proper synchronization inside check_and_free_fields, and never reinitialize the special fields when it is reused on update.

Fixes 68134668c17f ("bpf: Add map side support for bpf timers.")
---
 kernel/bpf/hashtab.c | 6 +-----
 1 file changed, 1 insertion(+), 5 deletions(-)
kernel/bpf/hashtab.c +1 -5
index da7578426a46..4d793a92301b 100644
@@ -311,12 +311,8 @@ static struct htab_elem *prealloc_lru_pop(struct bpf_htab *htab, void *key,
 	struct htab_elem *l;
 
 	if (node) {
-		u32 key_size = htab->map.key_size;
-
 		l = container_of(node, struct htab_elem, lru_node);
-		memcpy(l->key, key, key_size);
-		check_and_init_map_value(&htab->map,
-					 l->key + round_up(key_size, 8));
+		memcpy(l->key, key, htab->map.key_size);
 		return l;
 	}
 
Signature · 1 line
2.34.1
Acked-by on v3 2/3
#3 lore raw

Re: [PATCH bpf v3 2/3] bpf: Don't reinit map value in prealloc_lru_pop

Quoted 17 lines · Kumar Kartikeya Dwivedi

The LRU map that is preallocated may have its elements reused while another program holds a pointer to it from bpf_map_lookup_elem. Hence, only check_and_free_fields is appropriate when the element is being deleted, as it ensures proper synchronization against concurrent access of the map value. After that, we cannot call check_and_init_map_value again as it may rewrite bpf_spin_lock, bpf_timer, and kptr fields while they can be concurrently accessed from a BPF program.

This is safe to do as when the map entry is deleted, concurrent access is protected against by check_and_free_fields, i.e. an existing timer would be freed, and any existing kptr will be released by it. The program can create further timers and kptrs after check_and_free_fields, but they will eventually be released once the preallocated items are freed on map destruction, even if the item is never reused again. Hence, the deleted item sitting in the free list can still have resources attached to it, and they would never leak.

Quoted 5 lines

With spin_lock, we never touch the field at all on delete or update, as we may end up modifying the state of the lock. Since the verifier ensures that a bpf_spin_lock call is always paired with bpf_spin_unlock call, the program will eventually release the lock so that on reuse the new user of the value can take the lock.

The bpf_spin_lock's verifier description makes sense. Note that the lru map does not support spin lock for now.

Quoted 6 lines

Essentially, for the preallocated case, we must assume that the map value may always be in use by the program, even when it is sitting in the freelist, and handle things accordingly, i.e. use proper synchronization inside check_and_free_fields, and never reinitialize the special fields when it is reused on update.

#4 lore raw

Re: [PATCH bpf v3 2/3] bpf: Don't reinit map value in prealloc_lru_pop

Quoted 19 lines · Martin KaFai Lau
Quoted 17 lines · Kumar Kartikeya Dwivedi

The LRU map that is preallocated may have its elements reused while another program holds a pointer to it from bpf_map_lookup_elem. Hence, only check_and_free_fields is appropriate when the element is being deleted, as it ensures proper synchronization against concurrent access of the map value. After that, we cannot call check_and_init_map_value again as it may rewrite bpf_spin_lock, bpf_timer, and kptr fields while they can be concurrently accessed from a BPF program.

This is safe to do as when the map entry is deleted, concurrent access is protected against by check_and_free_fields, i.e. an existing timer would be freed, and any existing kptr will be released by it. The program can create further timers and kptrs after check_and_free_fields, but they will eventually be released once the preallocated items are freed on map destruction, even if the item is never reused again. Hence, the deleted item sitting in the free list can still have resources attached to it, and they would never leak.

Quoted 7 lines
Quoted 5 lines

With spin_lock, we never touch the field at all on delete or update, as we may end up modifying the state of the lock. Since the verifier ensures that a bpf_spin_lock call is always paired with bpf_spin_unlock call, the program will eventually release the lock so that on reuse the new user of the value can take the lock.

The bpf_spin_lock's verifier description makes sense. Note that the lru map does not support spin lock for now.

ahh. then it's not a bpf tree material.
It's a minor cleanup for bpf-next?

Quoted 7 lines
Quoted 6 lines

Essentially, for the preallocated case, we must assume that the map value may always be in use by the program, even when it is sitting in the freelist, and handle things accordingly, i.e. use proper synchronization inside check_and_free_fields, and never reinitialize the special fields when it is reused on update.

author maintainer
#5 lore raw

Re: [PATCH bpf v3 2/3] bpf: Don't reinit map value in prealloc_lru_pop

Quoted 26 lines · Alexei Starovoitov
Quoted 24 lines · Martin KaFai Lau
Quoted 22 lines · Kumar Kartikeya Dwivedi

The LRU map that is preallocated may have its elements reused while another program holds a pointer to it from bpf_map_lookup_elem. Hence, only check_and_free_fields is appropriate when the element is being deleted, as it ensures proper synchronization against concurrent access of the map value. After that, we cannot call check_and_init_map_value again as it may rewrite bpf_spin_lock, bpf_timer, and kptr fields while they can be concurrently accessed from a BPF program.

This is safe to do as when the map entry is deleted, concurrent access is protected against by check_and_free_fields, i.e. an existing timer would be freed, and any existing kptr will be released by it. The program can create further timers and kptrs after check_and_free_fields, but they will eventually be released once the preallocated items are freed on map destruction, even if the item is never reused again. Hence, the deleted item sitting in the free list can still have resources attached to it, and they would never leak.

With spin_lock, we never touch the field at all on delete or update, as we may end up modifying the state of the lock. Since the verifier ensures that a bpf_spin_lock call is always paired with bpf_spin_unlock call, the program will eventually release the lock so that on reuse the new user of the value can take the lock.

Quoted 6 lines
Quoted 2 lines

The bpf_spin_lock's verifier description makes sense. Note that the lru map does not support spin lock for now.

ahh. then it's not a bpf tree material.
It's a minor cleanup for bpf-next?

I was just describing what we do for each of the three types in the commit log. It still affects timers and kptrs, which lru map supports.

Quoted 7 lines
Quoted 7 lines
Quoted 6 lines

Essentially, for the preallocated case, we must assume that the map value may always be in use by the program, even when it is sitting in the freelist, and handle things accordingly, i.e. use proper synchronization inside check_and_free_fields, and never reinitialize the special fields when it is reused on update.

#6 lore raw

Re: [PATCH bpf v3 2/3] bpf: Don't reinit map value in prealloc_lru_pop

Quoted 32 lines · Kumar Kartikeya Dwivedi
Quoted 29 lines · Alexei Starovoitov
Quoted 26 lines · Martin KaFai Lau
Quoted 17 lines · Kumar Kartikeya Dwivedi

The LRU map that is preallocated may have its elements reused while another program holds a pointer to it from bpf_map_lookup_elem. Hence, only check_and_free_fields is appropriate when the element is being deleted, as it ensures proper synchronization against concurrent access of the map value. After that, we cannot call check_and_init_map_value again as it may rewrite bpf_spin_lock, bpf_timer, and kptr fields while they can be concurrently accessed from a BPF program.

This is safe to do as when the map entry is deleted, concurrent access is protected against by check_and_free_fields, i.e. an existing timer would be freed, and any existing kptr will be released by it. The program can create further timers and kptrs after check_and_free_fields, but they will eventually be released once the preallocated items are freed on map destruction, even if the item is never reused again. Hence, the deleted item sitting in the free list can still have resources attached to it, and they would never leak.

Quoted 5 lines

With spin_lock, we never touch the field at all on delete or update, as we may end up modifying the state of the lock. Since the verifier ensures that a bpf_spin_lock call is always paired with bpf_spin_unlock call, the program will eventually release the lock so that on reuse the new user of the value can take the lock.

The bpf_spin_lock's verifier description makes sense. Note that the lru map does not support spin lock for now.

Quoted 6 lines
Quoted 3 lines

ahh. then it's not a bpf tree material.
It's a minor cleanup for bpf-next?

I was just describing what we do for each of the three types in the commit log. It still affects timers and kptrs, which lru map supports.

got it.
The uaf-ing cpu can use kptr field of deleted elem and things go bad it lru_pop-ing cpu will clear it.

author maintainer
#7 lore raw

PATCH v3 3/3 selftests/bpf: Add test for prealloc_lru_pop bug

In reply to Kumar Kartikeya Dwivedi

Add a regression test to check against invalid check_and_init_map_value call inside prealloc_lru_pop.

The kptr should not be reset to NULL once we set it after deleting the map element. Hence, we trigger a program that updates the element causing its reuse, and checks whether the unref kptr is reset or not. If it is, prealloc_lru_pop does an incorrect check_and_init_map_value call and the test fails.

---
 .../selftests/bpf/prog_tests/lru_bug.c        | 21 ++++++++
 tools/testing/selftests/bpf/progs/lru_bug.c   | 49 +++++++++++++++++++
 2 files changed, 70 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/lru_bug.c
 create mode 100644 tools/testing/selftests/bpf/progs/lru_bug.c
tools/testing/selftests/bpf/prog_tests/lru_bug.c new file +21 -0
new file mode 100644
index 000000000000..3c7822390827
@@ -0,0 +1,21 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <test_progs.h>
+
+#include "lru_bug.skel.h"
+
+void test_lru_bug(void)
+{
+	struct lru_bug *skel;
+	int ret;
+
+	skel = lru_bug__open_and_load();
+	if (!ASSERT_OK_PTR(skel, "lru_bug__open_and_load"))
+		return;
+	ret = lru_bug__attach(skel);
+	if (!ASSERT_OK(ret, "lru_bug__attach"))
+		goto end;
+	usleep(1);
+	ASSERT_OK(skel->data->result, "prealloc_lru_pop doesn't call check_and_init_map_value");
+end:
+	lru_bug__destroy(skel);
+}
tools/testing/selftests/bpf/progs/lru_bug.c new file +49 -0

49 lines not on this page · raw message

Signature · 1 line
2.34.1
#8 lore raw
In reply to Kumar Kartikeya Dwivedi
This series was applied to bpf/bpf.git (master) by Alexei Starovoitov <[email protected]>:

Hello:

This series was applied to bpf/bpf.git (master)
by Alexei Starovoitov <[email protected]>:

Quoted 9 lines · On Tue, 9 Aug 2022 23:30:30 +0200 you wrote:

Fix for a bug in prealloc_lru_pop spotted while reading the code, then a test + example that checks whether it is fixed.

Changelog:
----------
v2 -> v3:
v2: https://lore.kernel.org/bpf/[email protected]

[...]

Here is the summary with links:
- [bpf,v3,1/3] bpf: Allow calling bpf_prog_test kfuncs in tracing programs

    https://git.kernel.org/bpf/bpf/c/1f0752628e76
  - [bpf,v3,2/3] bpf: Don't reinit map value in prealloc_lru_pop
    https://git.kernel.org/bpf/bpf/c/275c30bcee66
  - [bpf,v3,3/3] selftests/bpf: Add test for prealloc_lru_pop bug
    https://git.kernel.org/bpf/bpf/c/de7b9927105b

You are awesome, thank you!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html