[PATCH bpf v2 0/3] Don't reinit map value in prealloc_lru_pop

[PATCH bpf v2 0/3] Don't reinit map value in prealloc_lru_pop

[Kumar Kartikeya Dwivedi]

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

Changelog:
----------
v1 -> v2:
v1: https://lore.kernel.org/bpf/20220806014603.1771-1-memxor@gmail.com

 * 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        | 19 ++++++
 tools/testing/selftests/bpf/progs/lru_bug.c   | 67 +++++++++++++++++++
 4 files changed, 88 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

-- 
2.34.1

[PATCH bpf v2 1/3] bpf: Allow calling bpf_prog_test kfuncs in tracing programs

[Kumar Kartikeya Dwivedi]

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

Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
---
 net/bpf/test_run.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/net/bpf/test_run.c b/net/bpf/test_run.c
index cbc9cd5058cb..d11209367dd0 100644
--- a/net/bpf/test_run.c
+++ b/net/bpf/test_run.c
@@ -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);
-- 
2.34.1

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

[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.")
Acked-by: Yonghong Song <yhs@fb.com>
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
---
 kernel/bpf/hashtab.c | 6 +-----
 1 file changed, 1 insertion(+), 5 deletions(-)

diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
index da7578426a46..4d793a92301b 100644
--- a/kernel/bpf/hashtab.c
+++ b/kernel/bpf/hashtab.c
@@ -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;
 	}
 
-- 
2.34.1

[PATCH bpf v2 3/3] selftests/bpf: Add test for prealloc_lru_pop bug

[Kumar Kartikeya Dwivedi]

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

To actually observe a kind of problem this can cause, set debug to 1
when running the test locally without the fix. Then, just observe the
refcount which keeps increasing on each run of the test. With timers or
spin locks, it would cause unpredictable results when racing.

...

bash-5.1# ./test_progs -t lru_bug
      test_progs-192     [000] d..21   354.838821: bpf_trace_printk: ref: 4
      test_progs-192     [000] d..21   354.842824: bpf_trace_printk: ref: 5
bash-5.1# ./test_progs -t lru_bug
      test_progs-193     [000] d..21   356.722813: bpf_trace_printk: ref: 5
      test_progs-193     [000] d..21   356.727071: bpf_trace_printk: ref: 6

... and so on.

Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
---
 .../selftests/bpf/prog_tests/lru_bug.c        | 19 ++++++
 tools/testing/selftests/bpf/progs/lru_bug.c   | 67 +++++++++++++++++++
 2 files changed, 86 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/lru_bug.c
 create mode 100644 tools/testing/selftests/bpf/progs/lru_bug.c

diff --git a/tools/testing/selftests/bpf/prog_tests/lru_bug.c b/tools/testing/selftests/bpf/prog_tests/lru_bug.c
new file mode 100644
index 000000000000..3bcb5bc62d5a
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/lru_bug.c
@@ -0,0 +1,19 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <test_progs.h>
+
+#include "lru_bug.skel.h"
+
+void serial_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"))
+		return;
+	usleep(1);
+	ASSERT_OK(skel->data->result, "prealloc_lru_pop doesn't call check_and_init_map_value");
+}
diff --git a/tools/testing/selftests/bpf/progs/lru_bug.c b/tools/testing/selftests/bpf/progs/lru_bug.c
new file mode 100644
index 000000000000..35cbbe7aba9e
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/lru_bug.c
@@ -0,0 +1,67 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <vmlinux.h>
+#include <bpf/bpf_tracing.h>
+#include <bpf/bpf_helpers.h>
+
+struct map_value {
+	struct prog_test_ref_kfunc __kptr_ref *ptr;
+};
+
+struct {
+	__uint(type, BPF_MAP_TYPE_LRU_HASH);
+	__uint(max_entries, 1);
+	__type(key, int);
+	__type(value, struct map_value);
+} lru_map SEC(".maps");
+
+extern struct prog_test_ref_kfunc *bpf_kfunc_call_test_acquire(unsigned long *sp) __ksym;
+extern void bpf_kfunc_call_test_release(struct prog_test_ref_kfunc *s) __ksym;
+
+int pid = 0;
+const volatile int debug = 0;
+int result = 1;
+
+SEC("fentry/bpf_ktime_get_ns")
+int printk(void *ctx)
+{
+	struct map_value v = {};
+
+	if (pid == bpf_get_current_task_btf()->pid)
+		bpf_map_update_elem(&lru_map, &(int){0}, &v, 0);
+	return 0;
+}
+
+SEC("fentry/do_nanosleep")
+int nanosleep(void *ctx)
+{
+	struct map_value val = {}, *v;
+	struct prog_test_ref_kfunc *s;
+	unsigned long l = 0;
+
+	bpf_map_update_elem(&lru_map, &(int){0}, &val, 0);
+	v = bpf_map_lookup_elem(&lru_map, &(int){0});
+	if (!v)
+		return 0;
+	bpf_map_delete_elem(&lru_map, &(int){0});
+	s = bpf_kfunc_call_test_acquire(&l);
+	if (!s)
+		return 0;
+	if (debug)
+		bpf_printk("ref: %d\n", s->cnt.refs.counter);
+	s = bpf_kptr_xchg(&v->ptr, s);
+	if (s)
+		bpf_kfunc_call_test_release(s);
+	pid = bpf_get_current_task_btf()->pid;
+	bpf_ktime_get_ns();
+	if (debug) {
+		s = bpf_kfunc_call_test_acquire(&l);
+		if (!s)
+			return 0;
+		bpf_printk("ref: %d\n", s->cnt.refs.counter);
+		bpf_kfunc_call_test_release(s);
+	}
+	result = !v->ptr;
+	return 0;
+}
+
+char _license[] SEC("license") = "GPL";
-- 
2.34.1

Re: [PATCH bpf v2 1/3] bpf: Allow calling bpf_prog_test kfuncs in tracing programs

[Yonghong Song]

On 8/9/22 7:06 AM, Kumar Kartikeya Dwivedi wrote:
> In addition to TC hook, enable these in tracing programs so that they
> can be used in selftests.
> 
> Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>

Acked-by: Yonghong Song <yhs@fb.com>

Re: [PATCH bpf v2 3/3] selftests/bpf: Add test for prealloc_lru_pop bug

[Yonghong Song]

On 8/9/22 7:06 AM, Kumar Kartikeya Dwivedi wrote:
> Add a regression test to check against invalid check_and_init_map_value
> call inside prealloc_lru_pop.
> 
> To actually observe a kind of problem this can cause, set debug to 1
> when running the test locally without the fix. Then, just observe the
> refcount which keeps increasing on each run of the test. With timers or
> spin locks, it would cause unpredictable results when racing.
> 
> ...
> 
> bash-5.1# ./test_progs -t lru_bug
>        test_progs-192     [000] d..21   354.838821: bpf_trace_printk: ref: 4
>        test_progs-192     [000] d..21   354.842824: bpf_trace_printk: ref: 5
> bash-5.1# ./test_progs -t lru_bug
>        test_progs-193     [000] d..21   356.722813: bpf_trace_printk: ref: 5
>        test_progs-193     [000] d..21   356.727071: bpf_trace_printk: ref: 6
> 
> ... and so on.
> 
> Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>

Ack with a minor nit below.

Acked-by: Yonghong Song <yhs@fb.com>

> ---
>   .../selftests/bpf/prog_tests/lru_bug.c        | 19 ++++++
>   tools/testing/selftests/bpf/progs/lru_bug.c   | 67 +++++++++++++++++++
>   2 files changed, 86 insertions(+)
>   create mode 100644 tools/testing/selftests/bpf/prog_tests/lru_bug.c
>   create mode 100644 tools/testing/selftests/bpf/progs/lru_bug.c
> 
> diff --git a/tools/testing/selftests/bpf/prog_tests/lru_bug.c b/tools/testing/selftests/bpf/prog_tests/lru_bug.c
> new file mode 100644
> index 000000000000..3bcb5bc62d5a
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/prog_tests/lru_bug.c
> @@ -0,0 +1,19 @@
> +// SPDX-License-Identifier: GPL-2.0
> +#include <test_progs.h>
> +
> +#include "lru_bug.skel.h"
> +
> +void serial_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"))
> +		return;

If not ASSERT_OK, should go to lru_bug__destroy(skel).

> +	usleep(1);
> +	ASSERT_OK(skel->data->result, "prealloc_lru_pop doesn't call check_and_init_map_value");

Missing
	lru_bug__destroy(skel);
.

> +}
[...]

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

[Alexei Starovoitov]

On Tue, Aug 9, 2022 at 7:06 AM Kumar Kartikeya Dwivedi <memxor@gmail.com> wrote:
>
> Fix for a bug in prelloc_lru_pop spotted while reading the code, then a test +
> example that checks whether it is fixed.
>
> Changelog:
> ----------
> v1 -> v2:
> v1: https://lore.kernel.org/bpf/20220806014603.1771-1-memxor@gmail.com
>
>  * 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

hmm. CI is still not happy.

Re: [PATCH bpf v2 3/3] selftests/bpf: Add test for prealloc_lru_pop bug

[Kumar Kartikeya Dwivedi]

On Tue, 9 Aug 2022 at 18:01, Yonghong Song <yhs@fb.com> wrote:
> On 8/9/22 7:06 AM, Kumar Kartikeya Dwivedi wrote:
> > Add a regression test to check against invalid check_and_init_map_value
> > call inside prealloc_lru_pop.
> >
> > To actually observe a kind of problem this can cause, set debug to 1
> > when running the test locally without the fix. Then, just observe the
> > refcount which keeps increasing on each run of the test. With timers or
> > spin locks, it would cause unpredictable results when racing.
> >
> > ...
> >
> > bash-5.1# ./test_progs -t lru_bug
> >        test_progs-192     [000] d..21   354.838821: bpf_trace_printk: ref: 4
> >        test_progs-192     [000] d..21   354.842824: bpf_trace_printk: ref: 5
> > bash-5.1# ./test_progs -t lru_bug
> >        test_progs-193     [000] d..21   356.722813: bpf_trace_printk: ref: 5
> >        test_progs-193     [000] d..21   356.727071: bpf_trace_printk: ref: 6
> >
> > ... and so on.
> >
> > Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
>
> Ack with a minor nit below.
>
> Acked-by: Yonghong Song <yhs@fb.com>
>
> > ---
> >   .../selftests/bpf/prog_tests/lru_bug.c        | 19 ++++++
> >   tools/testing/selftests/bpf/progs/lru_bug.c   | 67 +++++++++++++++++++
> >   2 files changed, 86 insertions(+)
> >   create mode 100644 tools/testing/selftests/bpf/prog_tests/lru_bug.c
> >   create mode 100644 tools/testing/selftests/bpf/progs/lru_bug.c
> >
> > diff --git a/tools/testing/selftests/bpf/prog_tests/lru_bug.c b/tools/testing/selftests/bpf/prog_tests/lru_bug.c
> > new file mode 100644
> > index 000000000000..3bcb5bc62d5a
> > --- /dev/null
> > +++ b/tools/testing/selftests/bpf/prog_tests/lru_bug.c
> > @@ -0,0 +1,19 @@
> > +// SPDX-License-Identifier: GPL-2.0
> > +#include <test_progs.h>
> > +
> > +#include "lru_bug.skel.h"
> > +
> > +void serial_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"))
> > +             return;
>
> If not ASSERT_OK, should go to lru_bug__destroy(skel).
>
> > +     usleep(1);
> > +     ASSERT_OK(skel->data->result, "prealloc_lru_pop doesn't call check_and_init_map_value");
>
> Missing
>         lru_bug__destroy(skel);

Oops, thanks for catching, will fix.

> .
>
> > +}
> [...]

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

[Kumar Kartikeya Dwivedi]

On Tue, 9 Aug 2022 at 20:49, Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Tue, Aug 9, 2022 at 7:06 AM Kumar Kartikeya Dwivedi <memxor@gmail.com> wrote:
> >
> > Fix for a bug in prelloc_lru_pop spotted while reading the code, then a test +
> > example that checks whether it is fixed.
> >
> > Changelog:
> > ----------
> > v1 -> v2:
> > v1: https://lore.kernel.org/bpf/20220806014603.1771-1-memxor@gmail.com
> >
> >  * 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
>
> hmm. CI is still not happy.

Yeah, I'll try to check for it differently.