diff mbox series

[bpf-next,4/4] selftests/bpf: check if verifier.c:check_ids() handles 64+5 ids

Message ID 20221217021711.172247-5-eddyz87@gmail.com (mailing list archive)
State Changes Requested
Delegated to: BPF
Headers show
Series reduce BPF_ID_MAP_SIZE to fit only valid programs | expand

Checks

Context Check Description
netdev/tree_selection success Clearly marked for bpf-next, async
netdev/fixes_present success Fixes tag not required for -next series
netdev/subject_prefix success Link
netdev/cover_letter success Series has a cover letter
netdev/patch_count success Link
netdev/header_inline success No static functions without inline keyword in header files
netdev/build_32bit success Errors and warnings before: 0 this patch: 0
netdev/cc_maintainers warning 10 maintainers not CCed: linux-kselftest@vger.kernel.org kpsingh@kernel.org haoluo@google.com song@kernel.org martin.lau@linux.dev sdf@google.com john.fastabend@gmail.com shuah@kernel.org jolsa@kernel.org mykolal@fb.com
netdev/build_clang success Errors and warnings before: 0 this patch: 0
netdev/module_param success Was 0 now: 0
netdev/verify_signedoff success Signed-off-by tag matches author and committer
netdev/check_selftest success No net selftest shell script
netdev/verify_fixes success No Fixes tag
netdev/build_allmodconfig_warn success Errors and warnings before: 0 this patch: 0
netdev/checkpatch warning CHECK: Lines should not end with a '(' WARNING: added, moved or deleted file(s), does MAINTAINERS need updating? WARNING: quoted string split across lines
netdev/kdoc success Errors and warnings before: 0 this patch: 0
netdev/source_inline success Was 0 now: 0
bpf/vmtest-bpf-next-VM_Test-1 success Logs for ShellCheck
bpf/vmtest-bpf-next-VM_Test-7 success Logs for llvm-toolchain
bpf/vmtest-bpf-next-VM_Test-8 success Logs for set-matrix
bpf/vmtest-bpf-next-VM_Test-2 success Logs for build for aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-3 success Logs for build for aarch64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-5 success Logs for build for x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-6 success Logs for build for x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-4 success Logs for build for s390x with gcc
bpf/vmtest-bpf-next-VM_Test-34 success Logs for test_verifier on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-35 success Logs for test_verifier on aarch64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-37 success Logs for test_verifier on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-38 success Logs for test_verifier on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-9 success Logs for test_maps on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-10 success Logs for test_maps on aarch64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-12 success Logs for test_maps on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-13 success Logs for test_maps on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-14 success Logs for test_progs on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-15 fail Logs for test_progs on aarch64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-17 success Logs for test_progs on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-18 success Logs for test_progs on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-19 fail Logs for test_progs_no_alu32 on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-20 success Logs for test_progs_no_alu32 on aarch64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-22 success Logs for test_progs_no_alu32 on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-23 success Logs for test_progs_no_alu32 on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-24 success Logs for test_progs_no_alu32_parallel on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-25 success Logs for test_progs_no_alu32_parallel on aarch64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-27 success Logs for test_progs_no_alu32_parallel on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-28 success Logs for test_progs_no_alu32_parallel on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-29 success Logs for test_progs_parallel on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-30 success Logs for test_progs_parallel on aarch64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-32 success Logs for test_progs_parallel on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-33 success Logs for test_progs_parallel on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-21 success Logs for test_progs_no_alu32 on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-26 success Logs for test_progs_no_alu32_parallel on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-31 success Logs for test_progs_parallel on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-36 success Logs for test_verifier on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-16 success Logs for test_progs on s390x with gcc
bpf/vmtest-bpf-next-PR fail PR summary
bpf/vmtest-bpf-next-VM_Test-11 success Logs for test_maps on s390x with gcc

Commit Message

Eduard Zingerman Dec. 17, 2022, 2:17 a.m. UTC 
A simple program that allocates a bunch of unique register ids than
branches. The goal is to confirm that idmap used in verifier.c:check_ids()
has sufficient capacity to verify that branches converge to a same state.

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 .../selftests/bpf/prog_tests/verifier.c       | 12 +++
 .../selftests/bpf/progs/check_ids_limits.c    | 77 +++++++++++++++++++
 2 files changed, 89 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/verifier.c
 create mode 100644 tools/testing/selftests/bpf/progs/check_ids_limits.c

Comments

Yonghong Song Dec. 17, 2022, 7:17 p.m. UTC | #1 
On 12/16/22 6:17 PM, Eduard Zingerman wrote:
> A simple program that allocates a bunch of unique register ids than
> branches. The goal is to confirm that idmap used in verifier.c:check_ids()
> has sufficient capacity to verify that branches converge to a same state.
> 
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>

Acked-by: Yonghong Song <yhs@fb.com>
Andrii Nakryiko Dec. 20, 2022, 9:18 p.m. UTC | #2 
On Fri, Dec 16, 2022 at 6:17 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> A simple program that allocates a bunch of unique register ids than
> branches. The goal is to confirm that idmap used in verifier.c:check_ids()
> has sufficient capacity to verify that branches converge to a same state.
>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
>  .../selftests/bpf/prog_tests/verifier.c       | 12 +++
>  .../selftests/bpf/progs/check_ids_limits.c    | 77 +++++++++++++++++++
>  2 files changed, 89 insertions(+)
>  create mode 100644 tools/testing/selftests/bpf/prog_tests/verifier.c
>  create mode 100644 tools/testing/selftests/bpf/progs/check_ids_limits.c
>
> diff --git a/tools/testing/selftests/bpf/prog_tests/verifier.c b/tools/testing/selftests/bpf/prog_tests/verifier.c
> new file mode 100644
> index 000000000000..3933141928a7
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/prog_tests/verifier.c
> @@ -0,0 +1,12 @@
> +// SPDX-License-Identifier: GPL-2.0-only
> +#include <test_progs.h>
> +
> +#include "check_ids_limits.skel.h"
> +
> +#define TEST_SET(skel)                 \
> +       void test_##skel(void)          \
> +       {                               \
> +               RUN_TESTS(skel);        \
> +       }

Let's not use such trivial macros, please. It makes grepping for tests
much harder and saves 1 line of code only. Let's define funcs
explicitly?

I'm also surprised it works at all (it does, right?), because Makefile
is grepping explicitly for `void (serial_)test_xxx` pattern when
generating a list of tests. So this shouldn't have worked, unless I'm
missing something.

> +
> +TEST_SET(check_ids_limits)
> diff --git a/tools/testing/selftests/bpf/progs/check_ids_limits.c b/tools/testing/selftests/bpf/progs/check_ids_limits.c
> new file mode 100644
> index 000000000000..36c4a8bbe8ca
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/progs/check_ids_limits.c
> @@ -0,0 +1,77 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +#include <linux/bpf.h>
> +#include <bpf/bpf_helpers.h>
> +#include "bpf_misc.h"
> +
> +struct map_struct {
> +       __uint(type, BPF_MAP_TYPE_ARRAY);
> +       __uint(max_entries, 1);
> +       __type(key, int);
> +       __type(value, int);
> +} map SEC(".maps");
> +
> +/* Make sure that verifier.c:check_ids() can handle (almost) maximal
> + * number of ids.
> + */
> +SEC("?raw_tp")
> +__naked __test_state_freq __log_level(2) __msg("43 to 45: safe")

it's not clear what's special about 43 -> 45 jump?

can we also validate that id=69 was somewhere in verifier output?
which would require multiple __msg support, of course.

> +int allocate_many_ids(void)
> +{
> +       /* Use bpf_map_lookup_elem() as a way to get a bunch of values
> +        * with unique ids.
> +        */
> +#define __lookup(dst)                          \
> +               "r1 = %[map] ll;"               \
> +               "r2 = r10;"                     \
> +               "r2 += -8;"                     \
> +               "call %[bpf_map_lookup_elem];"  \
> +               dst " = r0;"
> +       asm volatile(
> +               "r0 = 0;"
> +               "*(u64*)(r10 - 8) = r0;"
> +               "r7 = r10;"
> +               "r8 = 0;"
> +               /* Spill 64 bpf_map_lookup_elem() results to stack,
> +                * each lookup gets its own unique id.
> +                */
> +       "write_loop:"
> +               "r7 += -8;"
> +               "r8 += -8;"
> +               __lookup("*(u64*)(r7 + 0)")
> +               "if r8 != -512 goto write_loop;"
> +               /* No way to source unique ids for r1-r5 as these
> +                * would be clobbered by bpf_map_lookup_elem call,
> +                * so make do with 64+5 unique ids.
> +                */
> +               __lookup("r6")
> +               __lookup("r7")
> +               __lookup("r8")
> +               __lookup("r9")
> +               __lookup("r0")
> +               /* Create a branching point for states comparison. */
> +/* 43: */      "if r0 != 0 goto skip_one;"
> +               /* Read all registers and stack spills to make these
> +                * persist in the checkpoint state.
> +                */
> +               "r0 = r0;"
> +       "skip_one:"

where you trying to just create a checkpoint here? given
__test_state_freq the simplest way would be just

goto +0;

no?

> +/* 45: */      "r0 = r6;"
> +               "r0 = r7;"
> +               "r0 = r8;"
> +               "r0 = r9;"
> +               "r0 = r10;"
> +               "r1 = 0;"
> +       "read_loop:"
> +               "r0 += -8;"
> +               "r1 += -8;"
> +               "r2 = *(u64*)(r0 + 0);"
> +               "if r1 != -512 goto read_loop;"
> +               "r0 = 0;"
> +               "exit;"
> +               :
> +               : __imm(bpf_map_lookup_elem),
> +                 __imm_addr(map)
> +               : __clobber_all);
> +#undef __lookup
> +}
> --
> 2.38.2
>
Eduard Zingerman Dec. 22, 2022, 12:33 a.m. UTC | #3 
On Tue, 2022-12-20 at 13:18 -0800, Andrii Nakryiko wrote:
> On Fri, Dec 16, 2022 at 6:17 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > 
> > A simple program that allocates a bunch of unique register ids than
> > branches. The goal is to confirm that idmap used in verifier.c:check_ids()
> > has sufficient capacity to verify that branches converge to a same state.
> > 
> > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> > ---
> >  .../selftests/bpf/prog_tests/verifier.c       | 12 +++
> >  .../selftests/bpf/progs/check_ids_limits.c    | 77 +++++++++++++++++++
> >  2 files changed, 89 insertions(+)
> >  create mode 100644 tools/testing/selftests/bpf/prog_tests/verifier.c
> >  create mode 100644 tools/testing/selftests/bpf/progs/check_ids_limits.c
> > 
> > diff --git a/tools/testing/selftests/bpf/prog_tests/verifier.c b/tools/testing/selftests/bpf/prog_tests/verifier.c
> > new file mode 100644
> > index 000000000000..3933141928a7
> > --- /dev/null
> > +++ b/tools/testing/selftests/bpf/prog_tests/verifier.c
> > @@ -0,0 +1,12 @@
> > +// SPDX-License-Identifier: GPL-2.0-only
> > +#include <test_progs.h>
> > +
> > +#include "check_ids_limits.skel.h"
> > +
> > +#define TEST_SET(skel)                 \
> > +       void test_##skel(void)          \
> > +       {                               \
> > +               RUN_TESTS(skel);        \
> > +       }
> 
> Let's not use such trivial macros, please. It makes grepping for tests
> much harder and saves 1 line of code only. Let's define funcs
> explicitly?
> 
> I'm also surprised it works at all (it does, right?), because Makefile

Nope, it doesn't work and it is embarrassing. I've tested w/o this
macro and only added it before final tests run. And didn't check the log.
Thank you for catching it. Will remove this macro.

> is grepping explicitly for `void (serial_)test_xxx` pattern when
> generating a list of tests. So this shouldn't have worked, unless I'm
> missing something.
> 
> > +
> > +TEST_SET(check_ids_limits)
> > diff --git a/tools/testing/selftests/bpf/progs/check_ids_limits.c b/tools/testing/selftests/bpf/progs/check_ids_limits.c
> > new file mode 100644
> > index 000000000000..36c4a8bbe8ca
> > --- /dev/null
> > +++ b/tools/testing/selftests/bpf/progs/check_ids_limits.c
> > @@ -0,0 +1,77 @@
> > +// SPDX-License-Identifier: GPL-2.0
> > +
> > +#include <linux/bpf.h>
> > +#include <bpf/bpf_helpers.h>
> > +#include "bpf_misc.h"
> > +
> > +struct map_struct {
> > +       __uint(type, BPF_MAP_TYPE_ARRAY);
> > +       __uint(max_entries, 1);
> > +       __type(key, int);
> > +       __type(value, int);
> > +} map SEC(".maps");
> > +
> > +/* Make sure that verifier.c:check_ids() can handle (almost) maximal
> > + * number of ids.
> > + */
> > +SEC("?raw_tp")
> > +__naked __test_state_freq __log_level(2) __msg("43 to 45: safe")
> 
> it's not clear what's special about 43 -> 45 jump?
> 
> can we also validate that id=69 was somewhere in verifier output?
> which would require multiple __msg support, of course.
> 
> > +int allocate_many_ids(void)
> > +{
> > +       /* Use bpf_map_lookup_elem() as a way to get a bunch of values
> > +        * with unique ids.
> > +        */
> > +#define __lookup(dst)                          \
> > +               "r1 = %[map] ll;"               \
> > +               "r2 = r10;"                     \
> > +               "r2 += -8;"                     \
> > +               "call %[bpf_map_lookup_elem];"  \
> > +               dst " = r0;"
> > +       asm volatile(
> > +               "r0 = 0;"
> > +               "*(u64*)(r10 - 8) = r0;"
> > +               "r7 = r10;"
> > +               "r8 = 0;"
> > +               /* Spill 64 bpf_map_lookup_elem() results to stack,
> > +                * each lookup gets its own unique id.
> > +                */
> > +       "write_loop:"
> > +               "r7 += -8;"
> > +               "r8 += -8;"
> > +               __lookup("*(u64*)(r7 + 0)")
> > +               "if r8 != -512 goto write_loop;"
> > +               /* No way to source unique ids for r1-r5 as these
> > +                * would be clobbered by bpf_map_lookup_elem call,
> > +                * so make do with 64+5 unique ids.
> > +                */
> > +               __lookup("r6")
> > +               __lookup("r7")
> > +               __lookup("r8")
> > +               __lookup("r9")
> > +               __lookup("r0")
> > +               /* Create a branching point for states comparison. */
> > +/* 43: */      "if r0 != 0 goto skip_one;"
> > +               /* Read all registers and stack spills to make these
> > +                * persist in the checkpoint state.
> > +                */
> > +               "r0 = r0;"
> > +       "skip_one:"
> 
> where you trying to just create a checkpoint here? given
> __test_state_freq the simplest way would be just
> 
> goto +0;
> 
> no?
> 
> > +/* 45: */      "r0 = r6;"
> > +               "r0 = r7;"
> > +               "r0 = r8;"
> > +               "r0 = r9;"
> > +               "r0 = r10;"
> > +               "r1 = 0;"
> > +       "read_loop:"
> > +               "r0 += -8;"
> > +               "r1 += -8;"
> > +               "r2 = *(u64*)(r0 + 0);"
> > +               "if r1 != -512 goto read_loop;"
> > +               "r0 = 0;"
> > +               "exit;"
> > +               :
> > +               : __imm(bpf_map_lookup_elem),
> > +                 __imm_addr(map)
> > +               : __clobber_all);
> > +#undef __lookup
> > +}
> > --
> > 2.38.2
> >
diff mbox series

Patch

diff --git a/tools/testing/selftests/bpf/prog_tests/verifier.c b/tools/testing/selftests/bpf/prog_tests/verifier.c
new file mode 100644
index 000000000000..3933141928a7
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/verifier.c
@@ -0,0 +1,12 @@ 
+// SPDX-License-Identifier: GPL-2.0-only
+#include <test_progs.h>
+
+#include "check_ids_limits.skel.h"
+
+#define TEST_SET(skel)			\
+	void test_##skel(void)		\
+	{				\
+		RUN_TESTS(skel);	\
+	}
+
+TEST_SET(check_ids_limits)
diff --git a/tools/testing/selftests/bpf/progs/check_ids_limits.c b/tools/testing/selftests/bpf/progs/check_ids_limits.c
new file mode 100644
index 000000000000..36c4a8bbe8ca
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/check_ids_limits.c
@@ -0,0 +1,77 @@ 
+// SPDX-License-Identifier: GPL-2.0
+
+#include <linux/bpf.h>
+#include <bpf/bpf_helpers.h>
+#include "bpf_misc.h"
+
+struct map_struct {
+	__uint(type, BPF_MAP_TYPE_ARRAY);
+	__uint(max_entries, 1);
+	__type(key, int);
+	__type(value, int);
+} map SEC(".maps");
+
+/* Make sure that verifier.c:check_ids() can handle (almost) maximal
+ * number of ids.
+ */
+SEC("?raw_tp")
+__naked __test_state_freq __log_level(2) __msg("43 to 45: safe")
+int allocate_many_ids(void)
+{
+	/* Use bpf_map_lookup_elem() as a way to get a bunch of values
+	 * with unique ids.
+	 */
+#define __lookup(dst)				\
+		"r1 = %[map] ll;"		\
+		"r2 = r10;"			\
+		"r2 += -8;"			\
+		"call %[bpf_map_lookup_elem];"	\
+		dst " = r0;"
+	asm volatile(
+		"r0 = 0;"
+		"*(u64*)(r10 - 8) = r0;"
+		"r7 = r10;"
+		"r8 = 0;"
+		/* Spill 64 bpf_map_lookup_elem() results to stack,
+		 * each lookup gets its own unique id.
+		 */
+	"write_loop:"
+		"r7 += -8;"
+		"r8 += -8;"
+		__lookup("*(u64*)(r7 + 0)")
+		"if r8 != -512 goto write_loop;"
+		/* No way to source unique ids for r1-r5 as these
+		 * would be clobbered by bpf_map_lookup_elem call,
+		 * so make do with 64+5 unique ids.
+		 */
+		__lookup("r6")
+		__lookup("r7")
+		__lookup("r8")
+		__lookup("r9")
+		__lookup("r0")
+		/* Create a branching point for states comparison. */
+/* 43: */	"if r0 != 0 goto skip_one;"
+		/* Read all registers and stack spills to make these
+		 * persist in the checkpoint state.
+		 */
+		"r0 = r0;"
+	"skip_one:"
+/* 45: */	"r0 = r6;"
+		"r0 = r7;"
+		"r0 = r8;"
+		"r0 = r9;"
+		"r0 = r10;"
+		"r1 = 0;"
+	"read_loop:"
+		"r0 += -8;"
+		"r1 += -8;"
+		"r2 = *(u64*)(r0 + 0);"
+		"if r1 != -512 goto read_loop;"
+		"r0 = 0;"
+		"exit;"
+		:
+		: __imm(bpf_map_lookup_elem),
+		  __imm_addr(map)
+		: __clobber_all);
+#undef __lookup
+}