diff mbox series

[v5,bpf-next,21/23] selftests/bpf: adjust OP_EQ/OP_NE handling to use subranges for branch taken

Message ID 20231027181346.4019398-22-andrii@kernel.org (mailing list archive)
State Superseded
Delegated to: BPF
Headers show
Series BPF register bounds logic and testing improvements | expand

Checks

Context Check Description
bpf/vmtest-bpf-next-VM_Test-30 success Logs for x86_64-llvm-16 / test (test_progs_no_alu32_parallel, true, 30) / test_progs_no_alu32_parallel on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-31 success Logs for x86_64-llvm-16 / test (test_progs_parallel, true, 30) / test_progs_parallel on x86_64 with llvm-16
bpf/vmtest-bpf-next-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-next-VM_Test-33 success Logs for x86_64-llvm-16 / veristat
netdev/series_format fail Series longer than 15 patches (and no cover letter)
netdev/tree_selection success Clearly marked for bpf-next, async
netdev/fixes_present success Fixes tag not required for -next series
netdev/header_inline success No static functions without inline keyword in header files
netdev/build_32bit success Errors and warnings before: 9 this patch: 9
netdev/cc_maintainers warning 11 maintainers not CCed: john.fastabend@gmail.com kpsingh@kernel.org mykolal@fb.com song@kernel.org martin.lau@linux.dev sdf@google.com jolsa@kernel.org linux-kselftest@vger.kernel.org shuah@kernel.org haoluo@google.com yonghong.song@linux.dev
netdev/build_clang fail Errors and warnings before: 15 this patch: 15
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: 9 this patch: 9
netdev/checkpatch warning WARNING: line length of 82 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-next-VM_Test-0 success Logs for Lint
bpf/vmtest-bpf-next-VM_Test-2 success Logs for Validate matrix.py
bpf/vmtest-bpf-next-VM_Test-1 success Logs for ShellCheck
bpf/vmtest-bpf-next-VM_Test-3 success Logs for aarch64-gcc / build / build for aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-8 success Logs for aarch64-gcc / veristat
bpf/vmtest-bpf-next-VM_Test-4 success Logs for aarch64-gcc / test (test_maps, false, 360) / test_maps on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-5 success Logs for aarch64-gcc / test (test_progs, false, 360) / test_progs on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-6 success Logs for aarch64-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-7 success Logs for aarch64-gcc / test (test_verifier, false, 360) / test_verifier on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-9 success Logs for s390x-gcc / build / build for s390x with gcc
bpf/vmtest-bpf-next-VM_Test-14 success Logs for s390x-gcc / veristat
bpf/vmtest-bpf-next-VM_Test-15 success Logs for set-matrix
bpf/vmtest-bpf-next-VM_Test-16 success Logs for x86_64-gcc / build / build for x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-17 success Logs for x86_64-gcc / test (test_maps, false, 360) / test_maps on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-18 success Logs for x86_64-gcc / test (test_progs, false, 360) / test_progs on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-19 success Logs for x86_64-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on x86_64 with gcc
bpf/vmtest-bpf-next-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-next-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-next-VM_Test-22 success Logs for x86_64-gcc / test (test_verifier, false, 360) / test_verifier on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-23 success Logs for x86_64-gcc / veristat / veristat on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-24 success Logs for x86_64-llvm-16 / build / build for x86_64 with llvm-16
bpf/vmtest-bpf-next-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-next-VM_Test-26 success Logs for x86_64-llvm-16 / test (test_progs, false, 360) / test_progs on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-27 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-next-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-next-VM_Test-29 success Logs for x86_64-llvm-16 / veristat
bpf/vmtest-bpf-next-VM_Test-13 success Logs for s390x-gcc / test (test_verifier, false, 360) / test_verifier on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-12 success Logs for s390x-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on s390x with gcc
bpf/vmtest-bpf-next-PR success PR summary
bpf/vmtest-bpf-next-VM_Test-10 success Logs for s390x-gcc / test (test_maps, false, 360) / test_maps on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-11 success Logs for s390x-gcc / test (test_progs, false, 360) / test_progs on s390x with gcc

Commit Message

Andrii Nakryiko Oct. 27, 2023, 6:13 p.m. UTC 
Similar to kernel-side BPF verifier logic enhancements, use 32-bit
subrange knowledge for is_branch_taken() logic in reg_bounds selftests.

Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
---
 .../selftests/bpf/prog_tests/reg_bounds.c     | 19 +++++++++++++++----
 1 file changed, 15 insertions(+), 4 deletions(-)

Comments

Eduard Zingerman Nov. 8, 2023, 6:22 p.m. UTC | #1 
On Fri, 2023-10-27 at 11:13 -0700, Andrii Nakryiko wrote:
> Similar to kernel-side BPF verifier logic enhancements, use 32-bit
> subrange knowledge for is_branch_taken() logic in reg_bounds selftests.
> 
> Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
> ---
>  .../selftests/bpf/prog_tests/reg_bounds.c     | 19 +++++++++++++++----
>  1 file changed, 15 insertions(+), 4 deletions(-)
> 
> diff --git a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
> index ac7354cfe139..330618cc12e7 100644
> --- a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
> +++ b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
> @@ -750,16 +750,27 @@ static int reg_state_branch_taken_op(enum num_t t, struct reg_state *x, struct r
>  		/* OP_EQ and OP_NE are sign-agnostic */
>  		enum num_t tu = t_unsigned(t);
>  		enum num_t ts = t_signed(t);
> -		int br_u, br_s;
> +		int br_u, br_s, br;
>  
>  		br_u = range_branch_taken_op(tu, x->r[tu], y->r[tu], op);
>  		br_s = range_branch_taken_op(ts, x->r[ts], y->r[ts], op);
>  
>  		if (br_u >= 0 && br_s >= 0 && br_u != br_s)
>  			ASSERT_FALSE(true, "branch taken inconsistency!\n");
> -		if (br_u >= 0)
> -			return br_u;
> -		return br_s;
> +
> +		/* if 64-bit ranges are indecisive, use 32-bit subranges to
> +		 * eliminate always/never taken branches, if possible
> +		 */
> +		if (br_u == -1 && (t == U64 || t == S64)) {
> +			br = range_branch_taken_op(U32, x->r[U32], y->r[U32], op);
> +			if (br != -1)
> +				return br;
> +			br = range_branch_taken_op(S32, x->r[S32], y->r[S32], op);
> +			if (br != -1)
> +				return br;

I'm not sure that these two checks are consistent with kernel side.
In kernel:
- for BPF_JEQ we can derive "won't happen" from u32/s32 ranges;
- for BPF_JNE we can derive "will happen" from u32/s32 ranges.

But here we seem to accept "will happen" for OP_EQ, which does not
seem right. E.g. it is possible to have inconclusive upper 32 bits and
equal lower 32 bits. What am I missing?
Andrii Nakryiko Nov. 8, 2023, 7:59 p.m. UTC | #2 
On Wed, Nov 8, 2023 at 10:22 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Fri, 2023-10-27 at 11:13 -0700, Andrii Nakryiko wrote:
> > Similar to kernel-side BPF verifier logic enhancements, use 32-bit
> > subrange knowledge for is_branch_taken() logic in reg_bounds selftests.
> >
> > Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
> > ---
> >  .../selftests/bpf/prog_tests/reg_bounds.c     | 19 +++++++++++++++----
> >  1 file changed, 15 insertions(+), 4 deletions(-)
> >
> > diff --git a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
> > index ac7354cfe139..330618cc12e7 100644
> > --- a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
> > +++ b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
> > @@ -750,16 +750,27 @@ static int reg_state_branch_taken_op(enum num_t t, struct reg_state *x, struct r
> >               /* OP_EQ and OP_NE are sign-agnostic */
> >               enum num_t tu = t_unsigned(t);
> >               enum num_t ts = t_signed(t);
> > -             int br_u, br_s;
> > +             int br_u, br_s, br;
> >
> >               br_u = range_branch_taken_op(tu, x->r[tu], y->r[tu], op);
> >               br_s = range_branch_taken_op(ts, x->r[ts], y->r[ts], op);
> >
> >               if (br_u >= 0 && br_s >= 0 && br_u != br_s)
> >                       ASSERT_FALSE(true, "branch taken inconsistency!\n");
> > -             if (br_u >= 0)
> > -                     return br_u;
> > -             return br_s;
> > +
> > +             /* if 64-bit ranges are indecisive, use 32-bit subranges to
> > +              * eliminate always/never taken branches, if possible
> > +              */
> > +             if (br_u == -1 && (t == U64 || t == S64)) {
> > +                     br = range_branch_taken_op(U32, x->r[U32], y->r[U32], op);
> > +                     if (br != -1)
> > +                             return br;
> > +                     br = range_branch_taken_op(S32, x->r[S32], y->r[S32], op);
> > +                     if (br != -1)
> > +                             return br;
>
> I'm not sure that these two checks are consistent with kernel side.
> In kernel:
> - for BPF_JEQ we can derive "won't happen" from u32/s32 ranges;
> - for BPF_JNE we can derive "will happen" from u32/s32 ranges.
>
> But here we seem to accept "will happen" for OP_EQ, which does not
> seem right. E.g. it is possible to have inconclusive upper 32 bits and
> equal lower 32 bits. What am I missing?

I think you are right, I should take into account OP_EQ vs OP_NE here
and the specific value of br. Will update. Nice catch!
diff mbox series

Patch

diff --git a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
index ac7354cfe139..330618cc12e7 100644
--- a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
+++ b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
@@ -750,16 +750,27 @@  static int reg_state_branch_taken_op(enum num_t t, struct reg_state *x, struct r
 		/* OP_EQ and OP_NE are sign-agnostic */
 		enum num_t tu = t_unsigned(t);
 		enum num_t ts = t_signed(t);
-		int br_u, br_s;
+		int br_u, br_s, br;
 
 		br_u = range_branch_taken_op(tu, x->r[tu], y->r[tu], op);
 		br_s = range_branch_taken_op(ts, x->r[ts], y->r[ts], op);
 
 		if (br_u >= 0 && br_s >= 0 && br_u != br_s)
 			ASSERT_FALSE(true, "branch taken inconsistency!\n");
-		if (br_u >= 0)
-			return br_u;
-		return br_s;
+
+		/* if 64-bit ranges are indecisive, use 32-bit subranges to
+		 * eliminate always/never taken branches, if possible
+		 */
+		if (br_u == -1 && (t == U64 || t == S64)) {
+			br = range_branch_taken_op(U32, x->r[U32], y->r[U32], op);
+			if (br != -1)
+				return br;
+			br = range_branch_taken_op(S32, x->r[S32], y->r[S32], op);
+			if (br != -1)
+				return br;
+		}
+
+		return br_u >= 0 ? br_u : br_s;
 	}
 	return range_branch_taken_op(t, x->r[t], y->r[t], op);
 }