diff mbox series

[bpf,v2,11/11] selftests/bpf: check if max number of bpf_loop iterations is tracked

Message ID 20231118013355.7943-12-eddyz87@gmail.com (mailing list archive)
State Superseded
Delegated to: BPF
Headers show
Series verify callbacks as if they are called unknown number of times | expand

Checks

Context Check Description
bpf/vmtest-bpf-VM_Test-30 success Logs for x86_64-llvm-16 / test (test_progs, false, 360) / test_progs on x86_64 with llvm-16
bpf/vmtest-bpf-VM_Test-31 success Logs for x86_64-llvm-16 / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on x86_64 with llvm-16
bpf/vmtest-bpf-VM_Test-32 success Logs for x86_64-llvm-16 / test (test_verifier, false, 360) / test_verifier on x86_64 with llvm-16
bpf/vmtest-bpf-VM_Test-33 success Logs for x86_64-llvm-16 / veristat
bpf/vmtest-bpf-PR fail PR summary
netdev/series_format success Posting correctly formatted
netdev/tree_selection success Clearly marked for bpf, async
netdev/fixes_present fail Series targets non-next tree, but doesn't contain any Fixes tags
netdev/header_inline success No static functions without inline keyword in header files
netdev/build_32bit success Errors and warnings before: 8 this patch: 8
netdev/cc_maintainers warning 9 maintainers not CCed: haoluo@google.com song@kernel.org kpsingh@kernel.org jolsa@kernel.org john.fastabend@gmail.com linux-kselftest@vger.kernel.org shuah@kernel.org sdf@google.com mykolal@fb.com
netdev/build_clang success Errors and warnings before: 8 this patch: 8
netdev/verify_signedoff success Signed-off-by tag matches author and committer
netdev/deprecated_api success None detected
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: 8 this patch: 8
netdev/checkpatch warning WARNING: Prefer 'unsigned int' to bare use of 'unsigned' WARNING: line length of 94 exceeds 80 columns
netdev/build_clang_rust success No Rust files in patch. Skipping build
netdev/kdoc success Errors and warnings before: 0 this patch: 0
netdev/source_inline success Was 0 now: 0
bpf/vmtest-bpf-VM_Test-0 success Logs for Lint
bpf/vmtest-bpf-VM_Test-2 success Logs for Validate matrix.py
bpf/vmtest-bpf-VM_Test-1 success Logs for ShellCheck
bpf/vmtest-bpf-VM_Test-8 success Logs for aarch64-gcc / veristat
bpf/vmtest-bpf-VM_Test-3 success Logs for aarch64-gcc / build / build for aarch64 with gcc
bpf/vmtest-bpf-VM_Test-7 success Logs for aarch64-gcc / test (test_verifier, false, 360) / test_verifier on aarch64 with gcc
bpf/vmtest-bpf-VM_Test-10 success Logs for set-matrix
bpf/vmtest-bpf-VM_Test-5 fail Logs for aarch64-gcc / test (test_progs, false, 360) / test_progs on aarch64 with gcc
bpf/vmtest-bpf-VM_Test-4 success Logs for aarch64-gcc / test (test_maps, false, 360) / test_maps on aarch64 with gcc
bpf/vmtest-bpf-VM_Test-6 fail Logs for aarch64-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on aarch64 with gcc
bpf/vmtest-bpf-VM_Test-9 success Logs for s390x-gcc / build / build for s390x with gcc
bpf/vmtest-bpf-VM_Test-14 success Logs for s390x-gcc / veristat
bpf/vmtest-bpf-VM_Test-15 success Logs for set-matrix
bpf/vmtest-bpf-VM_Test-16 success Logs for x86_64-gcc / build / build for x86_64 with gcc
bpf/vmtest-bpf-VM_Test-17 success Logs for x86_64-gcc / test (test_maps, false, 360) / test_maps on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-18 fail Logs for x86_64-gcc / test (test_progs, false, 360) / test_progs on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-19 fail Logs for x86_64-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-20 success Logs for x86_64-gcc / test (test_progs_no_alu32_parallel, true, 30) / test_progs_no_alu32_parallel on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-21 success Logs for x86_64-gcc / test (test_progs_parallel, true, 30) / test_progs_parallel on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-22 success Logs for x86_64-gcc / test (test_verifier, false, 360) / test_verifier on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-23 success Logs for x86_64-gcc / veristat / veristat on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-24 success Logs for x86_64-llvm-16 / build / build for x86_64 with llvm-16
bpf/vmtest-bpf-VM_Test-25 success Logs for x86_64-llvm-16 / test (test_maps, false, 360) / test_maps on x86_64 with llvm-16
bpf/vmtest-bpf-VM_Test-26 fail Logs for x86_64-llvm-16 / test (test_progs, false, 360) / test_progs on x86_64 with llvm-16
bpf/vmtest-bpf-VM_Test-27 fail Logs for x86_64-llvm-16 / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on x86_64 with llvm-16
bpf/vmtest-bpf-VM_Test-28 success Logs for x86_64-llvm-16 / test (test_verifier, false, 360) / test_verifier on x86_64 with llvm-16
bpf/vmtest-bpf-VM_Test-29 success Logs for x86_64-llvm-16 / veristat
bpf/vmtest-bpf-VM_Test-12 fail Logs for s390x-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on s390x with gcc
bpf/vmtest-bpf-VM_Test-11 fail Logs for s390x-gcc / test (test_progs, false, 360) / test_progs on s390x with gcc
bpf/vmtest-bpf-VM_Test-13 success Logs for s390x-gcc / test (test_verifier, false, 360) / test_verifier on s390x with gcc

Commit Message

Eduard Zingerman Nov. 18, 2023, 1:33 a.m. UTC 
Check that even if bpf_loop() callback simulation does not converge to
a specific state, verification could proceed via "brute force"
simulation of maximal number of callback calls.

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 .../bpf/progs/verifier_iterating_callbacks.c  | 83 +++++++++++++++++++
 1 file changed, 83 insertions(+)

Comments

Alexei Starovoitov Nov. 20, 2023, 2:09 a.m. UTC | #1 
On Fri, Nov 17, 2023 at 5:34 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> +
> +SEC("?raw_tp")
> +__success __log_level(2)
> +/* Check that path visiting every callback function once had been
> + * reached by verifier. Variable 'i' below (stored as r2) serves
> + * as a flag, with each decimal digit corresponding to a callback
> + * visit marker.
> + */
> +__msg("(73) *(u8 *)(r1 +0) = r2          ; R1_w=map_value(off=0,ks=4,vs=2,imm=0) R2_w=111111")
> +int bpf_loop_iter_limit_nested(void *unused)
> +{
> +       struct num_context ctx1 = { .i = 0 };
> +       struct num_context ctx2 = { .i = 0 };
> +       /* Set registers for 'i' and 'p' to get guaranteed asm
> +        * instruction shape for __msg matching.
> +        */
> +       register unsigned i asm("r2");
> +       register __u8 *p asm("r1");

I suspect this is fragile.
The compiler will use r2 for 'i' if 'i' is actually there,
but if it can optimize 'i' and 'p' away the r1 and r2 may be used
for something else.
The "register" keyword is not mandatory. Unlike "volatile".

> +       unsigned a, b;
> +
> +       bpf_loop(1, iter_limit_level1_cb, &ctx1, 0);
> +       bpf_loop(1, iter_limit_level1_cb, &ctx2, 0);
> +       a = ctx1.i;
> +       b = ctx2.i;
> +       i = a * 1000 + b;
> +       /* Force 'ctx1.i' and 'ctx2.i' precise. */
> +       p = &choice_arr[(a % 2 + b % 2) % 2];
> +       /* Make sure that verifier does not visit 'impossible' states:
> +        * enumerate all possible callback visit masks.
> +        */
> +       if (a != 0 && a != 1 && a != 11 && a != 101 && a != 111 &&
> +           b != 0 && b != 1 && b != 11 && b != 101 && b != 111)
> +               asm volatile ("r0 /= 0;" ::: "r0");
> +       /* Instruction for match in __msg spec. */
> +       asm volatile ("*(u8 *)(r1 + 0) = r2;" :: "r"(p), "r"(i) : "memory");

Feels even more fragile. Not sure what gcc will do.
Can 'i' be checked as run-time value ?
If it passes the verifier and after bpf_prog_run the 'i' is equal
to expected value we're good, no?
Eduard Zingerman Nov. 20, 2023, 2:23 a.m. UTC | #2 
On Sun, 2023-11-19 at 18:09 -0800, Alexei Starovoitov wrote:
[...]
> > +       register unsigned i asm("r2");
> > +       register __u8 *p asm("r1");
> 
> I suspect this is fragile.
> The compiler will use r2 for 'i' if 'i' is actually there,
> but if it can optimize 'i' and 'p' away the r1 and r2 may be used
> for something else.
> The "register" keyword is not mandatory. Unlike "volatile".
[...]
> > +       if (a != 0 && a != 1 && a != 11 && a != 101 && a != 111 &&
> > +           b != 0 && b != 1 && b != 11 && b != 101 && b != 111)
> > +               asm volatile ("r0 /= 0;" ::: "r0");
> > +       /* Instruction for match in __msg spec. */
> > +       asm volatile ("*(u8 *)(r1 + 0) = r2;" :: "r"(p), "r"(i) : "memory");
> 
> Feels even more fragile. Not sure what gcc will do.
> Can 'i' be checked as run-time value ?
> If it passes the verifier and after bpf_prog_run the 'i' is equal
> to expected value we're good, no?

Runtime check should work, thank you for this suggestion.
I'll remove unnecessary 'asm' blocks and use __retval instead
('r0 /= 0' will remain).
diff mbox series

Patch

diff --git a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
index 598c1e984b26..fe0ce06de55f 100644
--- a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
+++ b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
@@ -164,4 +164,87 @@  int unsafe_find_vma(void *unused)
 	return choice_arr[loop_ctx.i];
 }
 
+static int iter_limit_cb(__u32 idx, struct num_context *ctx)
+{
+	ctx->i++;
+	return 0;
+}
+
+SEC("?raw_tp")
+__success
+int bpf_loop_iter_limit_ok(void *unused)
+{
+	struct num_context ctx = { .i = 0 };
+
+	bpf_loop(1, iter_limit_cb, &ctx, 0);
+	return choice_arr[ctx.i];
+}
+
+SEC("?raw_tp")
+__failure __msg("invalid access to map value, value_size=2 off=2 size=1")
+int bpf_loop_iter_limit_overflow(void *unused)
+{
+	struct num_context ctx = { .i = 0 };
+
+	bpf_loop(2, iter_limit_cb, &ctx, 0);
+	return choice_arr[ctx.i];
+}
+
+static int iter_limit_level2a_cb(__u32 idx, struct num_context *ctx)
+{
+	ctx->i += 100;
+	return 0;
+}
+
+static int iter_limit_level2b_cb(__u32 idx, struct num_context *ctx)
+{
+	ctx->i += 10;
+	return 0;
+}
+
+static int iter_limit_level1_cb(__u32 idx, struct num_context *ctx)
+{
+	ctx->i += 1;
+	bpf_loop(1, iter_limit_level2a_cb, ctx, 0);
+	bpf_loop(1, iter_limit_level2b_cb, ctx, 0);
+	return 0;
+}
+
+SEC("?raw_tp")
+__success __log_level(2)
+/* Check that path visiting every callback function once had been
+ * reached by verifier. Variable 'i' below (stored as r2) serves
+ * as a flag, with each decimal digit corresponding to a callback
+ * visit marker.
+ */
+__msg("(73) *(u8 *)(r1 +0) = r2          ; R1_w=map_value(off=0,ks=4,vs=2,imm=0) R2_w=111111")
+int bpf_loop_iter_limit_nested(void *unused)
+{
+	struct num_context ctx1 = { .i = 0 };
+	struct num_context ctx2 = { .i = 0 };
+	/* Set registers for 'i' and 'p' to get guaranteed asm
+	 * instruction shape for __msg matching.
+	 */
+	register unsigned i asm("r2");
+	register __u8 *p asm("r1");
+	unsigned a, b;
+
+	bpf_loop(1, iter_limit_level1_cb, &ctx1, 0);
+	bpf_loop(1, iter_limit_level1_cb, &ctx2, 0);
+	a = ctx1.i;
+	b = ctx2.i;
+	i = a * 1000 + b;
+	/* Force 'ctx1.i' and 'ctx2.i' precise. */
+	p = &choice_arr[(a % 2 + b % 2) % 2];
+	/* Make sure that verifier does not visit 'impossible' states:
+	 * enumerate all possible callback visit masks.
+	 */
+	if (a != 0 && a != 1 && a != 11 && a != 101 && a != 111 &&
+	    b != 0 && b != 1 && b != 11 && b != 101 && b != 111)
+		asm volatile ("r0 /= 0;" ::: "r0");
+	/* Instruction for match in __msg spec. */
+	asm volatile ("*(u8 *)(r1 + 0) = r2;" :: "r"(p), "r"(i) : "memory");
+	return 0;
+}
+
 char _license[] SEC("license") = "GPL";