[v3,bpf-next,2/2] selftests/bpf: Added selftests to check deadlocks in queue and stack map

Commit Message

Siddharth Chintamaneni May 14, 2024, 12:40 p.m. UTC

Added selftests to check for nested deadlocks in queue  and stack maps.

test_map_queue_stack_nesting_success:PASS:test_queue_stack_nested_map__open 0 nsec
test_map_queue_stack_nesting_success:PASS:test_queue_stack_nested_map__load 0 nsec
test_map_queue_stack_nesting_success:PASS:test_queue_stack_nested_map__attach 0 nsec
test_map_queue_stack_nesting_success:PASS:MAP Write 0 nsec
test_map_queue_stack_nesting_success:PASS:no map nesting 0 nsec
test_map_queue_stack_nesting_success:PASS:no map nesting 0 nsec
384/1   test_queue_stack_nested_map/map_queue_nesting:OK
test_map_queue_stack_nesting_success:PASS:test_queue_stack_nested_map__open 0 nsec
test_map_queue_stack_nesting_success:PASS:test_queue_stack_nested_map__load 0 nsec
test_map_queue_stack_nesting_success:PASS:test_queue_stack_nested_map__attach 0 nsec
test_map_queue_stack_nesting_success:PASS:MAP Write 0 nsec
test_map_queue_stack_nesting_success:PASS:no map nesting 0 nsec
384/2   test_queue_stack_nested_map/map_stack_nesting:OK
384     test_queue_stack_nested_map:OK
Summary: 1/2 PASSED, 0 SKIPPED, 0 FAILED

Signed-off-by: Siddharth Chintamaneni <[e-mail]>
---
 .../prog_tests/test_queue_stack_nested_map.c  |  69 +++++++++++
 .../bpf/progs/test_queue_stack_nested_map.c   | 116 ++++++++++++++++++
 2 files changed, 185 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/test_queue_stack_nested_map.c
 create mode 100644 tools/testing/selftests/bpf/progs/test_queue_stack_nested_map.c

Comments

Kumar Kartikeya Dwivedi May 15, 2024, 5:02 p.m. UTC | #1

On Tue, 14 May 2024 at 14:41, Siddharth Chintamaneni
<[e-mail]> wrote:
>
> Added selftests to check for nested deadlocks in queue  and stack maps.
>
> test_map_queue_stack_nesting_success:PASS:test_queue_stack_nested_map__open 0 nsec
> test_map_queue_stack_nesting_success:PASS:test_queue_stack_nested_map__load 0 nsec
> test_map_queue_stack_nesting_success:PASS:test_queue_stack_nested_map__attach 0 nsec
> test_map_queue_stack_nesting_success:PASS:MAP Write 0 nsec
> test_map_queue_stack_nesting_success:PASS:no map nesting 0 nsec
> test_map_queue_stack_nesting_success:PASS:no map nesting 0 nsec
> 384/1   test_queue_stack_nested_map/map_queue_nesting:OK
> test_map_queue_stack_nesting_success:PASS:test_queue_stack_nested_map__open 0 nsec
> test_map_queue_stack_nesting_success:PASS:test_queue_stack_nested_map__load 0 nsec
> test_map_queue_stack_nesting_success:PASS:test_queue_stack_nested_map__attach 0 nsec
> test_map_queue_stack_nesting_success:PASS:MAP Write 0 nsec
> test_map_queue_stack_nesting_success:PASS:no map nesting 0 nsec
> 384/2   test_queue_stack_nested_map/map_stack_nesting:OK
> 384     test_queue_stack_nested_map:OK
> Summary: 1/2 PASSED, 0 SKIPPED, 0 FAILED
>
> Signed-off-by: Siddharth Chintamaneni <[e-mail]>
> ---

CI fails on s390
https://github.com/kernel-patches/bpf/actions/runs/9081519831/job/24957489598?pr=7031
A different method of triggering deadlock is required. Seems like
_raw_spin_lock_irqsave being available everywhere cannot be relied
upon.

Siddharth Chintamaneni May 15, 2024, 5:44 p.m. UTC | #2

> CI fails on s390
> https://github.com/kernel-patches/bpf/actions/runs/9081519831/job/24957489598?pr=7031
> A different method of triggering deadlock is required. Seems like
> _raw_spin_lock_irqsave being available everywhere cannot be relied
> upon.

The other functions which are in the critical section are getting
inlined so I have used
_raw_spin_lock_irqsave to write the selftests.

Other approach could be to just pass the tests if the function is
getting inlined just like in
https://elixir.bootlin.com/linux/latest/source/tools/testing/selftests/bpf/prog_tests/htab_update.c

Kumar Kartikeya Dwivedi May 15, 2024, 5:56 p.m. UTC | #3

On Wed, 15 May 2024 at 19:44, Siddharth Chintamaneni
<[e-mail]> wrote:
>
> > CI fails on s390
> > https://github.com/kernel-patches/bpf/actions/runs/9081519831/job/24957489598?pr=7031
> > A different method of triggering deadlock is required. Seems like
> > _raw_spin_lock_irqsave being available everywhere cannot be relied
> > upon.
>
> The other functions which are in the critical section are getting
> inlined so I have used
> _raw_spin_lock_irqsave to write the selftests.
>
> Other approach could be to just pass the tests if the function is
> getting inlined just like in
> https://elixir.bootlin.com/linux/latest/source/tools/testing/selftests/bpf/prog_tests/htab_update.c

Yeah, it is certainly tricky.
Skipping seems fragile because what if x86 and others also inline the
function? Then this test would simply report success while not
testing anything.

One option is to place it at trace_contention_begin, and spawn
multiple threads in the test and try until you hit -EBUSY (due to
increased contention, leading to queued_spin_lock_slowpath being
called and the tracepoint being hit).

The other option would be to add a dummy empty call within the
critical section marked as noinline, and then attach the BPF program
there. But I think this might not be liked by everyone since we're
introducing code in the kernel just to test stuff.

So option 1 seems better to me, but the test needs to be set up
carefully to ensure contention occurs.
Others can chime in with better ideas.

Kumar Kartikeya Dwivedi May 15, 2024, 5:58 p.m. UTC | #4

On Wed, 15 May 2024 at 19:56, Kumar Kartikeya Dwivedi <[e-mail]> wrote:
>
> On Wed, 15 May 2024 at 19:44, Siddharth Chintamaneni
> <[e-mail]> wrote:
> >
> > > CI fails on s390
> > > https://github.com/kernel-patches/bpf/actions/runs/9081519831/job/24957489598?pr=7031
> > > A different method of triggering deadlock is required. Seems like
> > > _raw_spin_lock_irqsave being available everywhere cannot be relied
> > > upon.
> >
> > The other functions which are in the critical section are getting
> > inlined so I have used
> > _raw_spin_lock_irqsave to write the selftests.
> >
> > Other approach could be to just pass the tests if the function is
> > getting inlined just like in
> > https://elixir.bootlin.com/linux/latest/source/tools/testing/selftests/bpf/prog_tests/htab_update.c
>
> Yeah, it is certainly tricky.
> Skipping seems fragile because what if x86 and others also inline the
> function? Then this test would simply report success while not
> testing anything.
>
> One option is to place it at trace_contention_begin, and spawn

Sorry, this should be trace_contention_end, the lock is only held at that point.

Patch

diff --git a/tools/testing/selftests/bpf/prog_tests/test_queue_stack_nested_map.c b/tools/testing/selftests/bpf/prog_tests/test_queue_stack_nested_map.c
new file mode 100644
index 000000000000..fc46561788af
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/test_queue_stack_nested_map.c
@@ -0,0 +1,69 @@ 
+// SPDX-License-Identifier: GPL-2.0
+#include <test_progs.h>
+#include <network_helpers.h>
+
+#include "test_queue_stack_nested_map.skel.h"
+
+
+static void test_map_queue_stack_nesting_success(bool is_map_queue)
+{
+	struct test_queue_stack_nested_map *skel;
+	int err;
+
+	skel = test_queue_stack_nested_map__open();
+	if (!ASSERT_OK_PTR(skel, "test_queue_stack_nested_map__open"))
+		return;
+
+	err = test_queue_stack_nested_map__load(skel);
+	if (!ASSERT_OK(err, "test_queue_stack_nested_map__load"))
+		goto out;
+
+	skel->bss->pid = getpid();
+	err = test_queue_stack_nested_map__attach(skel);
+	if (!ASSERT_OK(err, "test_queue_stack_nested_map__attach"))
+		goto out;
+
+	/* trigger map from userspace to check nesting */
+	int value = 0;
+
+	do {
+		if (is_map_queue) {
+			err = bpf_map_update_elem(bpf_map__fd(skel->maps.map_queue),
+								NULL, &value, 0);
+			if (err < 0)
+				break;
+			err = bpf_map_lookup_and_delete_elem(bpf_map__fd(skel->maps.map_queue),
+								 NULL, &value);
+		} else {
+			err = bpf_map_update_elem(bpf_map__fd(skel->maps.map_stack),
+								NULL, &value, 0);
+			if (err < 0)
+				break;
+			err = bpf_map_lookup_and_delete_elem(bpf_map__fd(skel->maps.map_stack),
+								NULL, &value);
+		}
+	} while (0);
+
+
+	if (!ASSERT_OK(err, "MAP Write"))
+		goto out;
+
+	if (is_map_queue) {
+		ASSERT_EQ(skel->bss->err_queue_push, -EBUSY, "no map nesting");
+		ASSERT_EQ(skel->bss->err_queue_pop, -EBUSY, "no map nesting");
+	} else {
+		ASSERT_EQ(skel->bss->err_stack, -EBUSY, "no map nesting");
+	}
+out:
+	test_queue_stack_nested_map__destroy(skel);
+}
+
+void test_test_queue_stack_nested_map(void)
+{
+	if (test__start_subtest("map_queue_nesting"))
+		test_map_queue_stack_nesting_success(true);
+	if (test__start_subtest("map_stack_nesting"))
+		test_map_queue_stack_nesting_success(false);
+
+}
+
diff --git a/tools/testing/selftests/bpf/progs/test_queue_stack_nested_map.c b/tools/testing/selftests/bpf/progs/test_queue_stack_nested_map.c
new file mode 100644
index 000000000000..893a37593206
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/test_queue_stack_nested_map.c
@@ -0,0 +1,116 @@ 
+// SPDX-License-Identifier: GPL-2.0
+#include "vmlinux.h"
+#include <bpf/bpf_helpers.h>
+#include <bpf/bpf_tracing.h>
+
+struct {
+	__uint(type, BPF_MAP_TYPE_STACK);
+	__uint(max_entries, 32);
+	__uint(key_size, 0);
+	__uint(value_size, sizeof(__u32));
+} map_stack SEC(".maps");
+
+struct {
+	__uint(type, BPF_MAP_TYPE_QUEUE);
+	__uint(max_entries, 32);
+	__uint(key_size, 0);
+	__uint(value_size, sizeof(__u32));
+} map_queue SEC(".maps");
+
+
+int err_queue_push;
+int err_queue_pop;
+int err_stack;
+int pid;
+__u32 trigger_flag_queue_push;
+__u32 trigger_flag_queue_pop;
+__u32 trigger_flag_stack;
+
+SEC("fentry/queue_stack_map_push_elem")
+int BPF_PROG(test_queue_stack_push_trigger, raw_spinlock_t *lock, unsigned long flags)
+{
+
+	if ((bpf_get_current_pid_tgid() >> 32) != pid)
+		return 0;
+
+
+	trigger_flag_queue_push = 1;
+
+	return 0;
+}
+
+SEC("fentry/queue_map_pop_elem")
+int BPF_PROG(test_queue_pop_trigger, raw_spinlock_t *lock, unsigned long flags)
+{
+
+	if ((bpf_get_current_pid_tgid() >> 32) != pid)
+		return 0;
+
+	trigger_flag_queue_pop = 1;
+
+	return 0;
+}
+
+
+SEC("fentry/stack_map_pop_elem")
+int BPF_PROG(test_stack_pop_trigger, raw_spinlock_t *lock, unsigned long flags)
+{
+
+	if ((bpf_get_current_pid_tgid() >> 32) != pid)
+		return 0;
+
+	trigger_flag_stack = 1;
+
+	return 0;
+}
+
+SEC("fentry/_raw_spin_unlock_irqrestore")
+int BPF_PROG(test_queue_pop_nesting, raw_spinlock_t *lock, unsigned long flags)
+{
+	__u32 val;
+
+	if ((bpf_get_current_pid_tgid() >> 32) != pid || trigger_flag_queue_pop != 1)
+		return 0;
+
+
+	err_queue_pop = bpf_map_pop_elem(&map_queue, &val);
+
+	trigger_flag_queue_pop = 0;
+
+	return 0;
+}
+
+SEC("fentry/_raw_spin_unlock_irqrestore")
+int BPF_PROG(test_stack_nesting, raw_spinlock_t *lock, unsigned long flags)
+{
+	__u32 val;
+
+	if ((bpf_get_current_pid_tgid() >> 32) != pid || trigger_flag_stack != 1)
+		return 0;
+
+
+	err_stack = bpf_map_pop_elem(&map_stack, &val);
+
+	trigger_flag_stack = 0;
+
+	return 0;
+}
+
+
+SEC("fentry/_raw_spin_unlock_irqrestore")
+int BPF_PROG(test_queue_push_nesting, raw_spinlock_t *lock, unsigned long flags)
+{
+	__u32 val = 1;
+
+	if ((bpf_get_current_pid_tgid() >> 32) != pid || trigger_flag_queue_push != 1) {
+		return 0;
+	}
+
+	err_queue_push = bpf_map_push_elem(&map_queue, &val, 0);
+
+	trigger_flag_queue_push = 0;
+
+	return 0;
+}
+
+char _license[] SEC("license") = "GPL";