diff mbox series

max<min after jset

Message ID 20231121173206.3594040-1-tao.lyu@epfl.ch (mailing list archive)
State Changes Requested
Delegated to: BPF
Headers show
Series max<min after jset | expand

Checks

Context Check Description
netdev/tree_selection success Not a local patch
bpf/vmtest-bpf-next-PR fail PR summary
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-8 success Logs for aarch64-gcc / veristat
bpf/vmtest-bpf-next-VM_Test-3 success Logs for aarch64-gcc / build / build for aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-14 success Logs for s390x-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-16 success Logs for x86_64-gcc / build / build for x86_64 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-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-15 success Logs for set-matrix
bpf/vmtest-bpf-next-VM_Test-9 success Logs for s390x-gcc / build / build for s390x with gcc
bpf/vmtest-bpf-next-VM_Test-29 success Logs for x86_64-llvm-16 / veristat
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-23 success Logs for x86_64-gcc / veristat / veristat on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-7 fail Logs for aarch64-gcc / test (test_verifier, false, 360) / test_verifier on aarch64 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-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-22 fail Logs for x86_64-gcc / test (test_verifier, false, 360) / test_verifier 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-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-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-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-5 success Logs for aarch64-gcc / test (test_progs, false, 360) / test_progs on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-28 fail 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-13 fail 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-VM_Test-11 success Logs for s390x-gcc / test (test_progs, false, 360) / test_progs on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-10 success Logs for s390x-gcc / test (test_maps, false, 360) / test_maps on s390x with gcc

Commit Message

Tao Lyu Nov. 21, 2023, 5:32 p.m. UTC 
Hi,

The eBPF program shown below leads to an reversed min and max
after insn 6 "if w0 & 0x894b6a55 goto +2",
whic means max < min.

Here is the introduction how it happens.

Before insn 6,
the range of r0 expressed by the min and max field is
min1 = 884670597, max1 = 900354100
And the range expressed by the var_off=(0x34000000; 0x1ff5fbf))
is min2=872415232, max2=905928639.

---min2-----------------------min1-----max1-----max2---

Here we can see that the range expressed by var_off is wider than that of min and max.

When verifying insn6,
it first uses the var_off and immediate "0x894b6a55" to
calculate the new var_off=(0x34b00000; 0x415aa).
The range expressed by the new var_off is:
min3=883949568, max3=884217258

---min2-----min3-----max3-----min1-----max1-----max2---

And then it will calculate the new min and max by:
(1) new-min = MAX(min3, min1) = min1
(2) new-max = MIN(max3, max1) = max3

---min2-----min3-----max3-----min1-----max1-----max2---
         "new-max"          "new-min" 

Now, the new-max becomes less than the new min.

Notably, [min1, max1] can never make "w0 & 0x894b6a55 == 0"
and thus cannot goes the fall-through branch.
In other words, actually the fall-trough branch is a dead path.

BTW, I cannot successfully compile this instruciton "if w0 != 0 goto +2;\"
in the c inline assembly code.
So I can only attach the bytecodes.

Signed-off-by: Tao Lyu <tao.lyu@epfl.ch>
---
 .../selftests/bpf/verifier/jset_reversed_range.c  | 15 +++++++++++++++
 1 file changed, 15 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/verifier/jset_reversed_range.c

Comments

Yonghong Song Nov. 22, 2023, 12:25 a.m. UTC | #1 
On 11/21/23 12:32 PM, Tao Lyu wrote:
> Hi,
>
> The eBPF program shown below leads to an reversed min and max
> after insn 6 "if w0 & 0x894b6a55 goto +2",
> whic means max < min.
>
> Here is the introduction how it happens.
>
> Before insn 6,
> the range of r0 expressed by the min and max field is
> min1 = 884670597, max1 = 900354100
> And the range expressed by the var_off=(0x34000000; 0x1ff5fbf))
> is min2=872415232, max2=905928639.
>
> ---min2-----------------------min1-----max1-----max2---
>
> Here we can see that the range expressed by var_off is wider than that of min and max.
>
> When verifying insn6,
> it first uses the var_off and immediate "0x894b6a55" to
> calculate the new var_off=(0x34b00000; 0x415aa).
> The range expressed by the new var_off is:
> min3=883949568, max3=884217258
>
> ---min2-----min3-----max3-----min1-----max1-----max2---
>
> And then it will calculate the new min and max by:
> (1) new-min = MAX(min3, min1) = min1
> (2) new-max = MIN(max3, max1) = max3
>
> ---min2-----min3-----max3-----min1-----max1-----max2---
>           "new-max"          "new-min"
>
> Now, the new-max becomes less than the new min.
>
> Notably, [min1, max1] can never make "w0 & 0x894b6a55 == 0"
> and thus cannot goes the fall-through branch.
> In other words, actually the fall-trough branch is a dead path.
>
> BTW, I cannot successfully compile this instruciton "if w0 != 0 goto +2;\"
> in the c inline assembly code.

The format "if w0 != 0 goto +2;\" should be supported by recent clang compiler.
Which clang version you are using? Maybe try clang 15/16? Could you also
post the C inline assembly code here so we can investigate?

> So I can only attach the bytecodes.
>
> Signed-off-by: Tao Lyu <tao.lyu@epfl.ch>
> ---
>   .../selftests/bpf/verifier/jset_reversed_range.c  | 15 +++++++++++++++
>   1 file changed, 15 insertions(+)
>   create mode 100644 tools/testing/selftests/bpf/verifier/jset_reversed_range.c
>
> diff --git a/tools/testing/selftests/bpf/verifier/jset_reversed_range.c b/tools/testing/selftests/bpf/verifier/jset_reversed_range.c
> new file mode 100644
> index 000000000000..734f492a2a96
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/verifier/jset_reversed_range.c
> @@ -0,0 +1,15 @@
> +{
> +    "BPF_JSET: incorrect scalar range",
> +    .insns = {
> +    BPF_MOV64_IMM(BPF_REG_5, 100),
> +    BPF_ALU64_IMM(BPF_DIV, BPF_REG_5, 3),
> +    BPF_ALU32_IMM(BPF_RSH, BPF_REG_5, 7),
> +    BPF_ALU64_IMM(BPF_AND, BPF_REG_5, -386969681),
> +    BPF_ALU64_IMM(BPF_SUB, BPF_REG_5, -884670597),
> +    BPF_MOV32_REG(BPF_REG_0, BPF_REG_5),
> +    BPF_JMP32_IMM(BPF_JSET, BPF_REG_0, 0x894b6a55, 1),
> +    BPF_MOV64_IMM(BPF_REG_0, 1),
> +    BPF_MOV64_IMM(BPF_REG_0, 0),
> +    BPF_EXIT_INSN(),
> +    },
> +},
Yonghong Song Nov. 28, 2023, 4:16 a.m. UTC | #2 
On 11/21/23 12:32 PM, Tao Lyu wrote:
> Hi,
>
> The eBPF program shown below leads to an reversed min and max
> after insn 6 "if w0 & 0x894b6a55 goto +2",
> whic means max < min.
>
> Here is the introduction how it happens.
>
> Before insn 6,
> the range of r0 expressed by the min and max field is
> min1 = 884670597, max1 = 900354100
> And the range expressed by the var_off=(0x34000000; 0x1ff5fbf))
> is min2=872415232, max2=905928639.
>
> ---min2-----------------------min1-----max1-----max2---
>
> Here we can see that the range expressed by var_off is wider than that of min and max.
>
> When verifying insn6,
> it first uses the var_off and immediate "0x894b6a55" to
> calculate the new var_off=(0x34b00000; 0x415aa).
> The range expressed by the new var_off is:
> min3=883949568, max3=884217258
>
> ---min2-----min3-----max3-----min1-----max1-----max2---
>
> And then it will calculate the new min and max by:
> (1) new-min = MAX(min3, min1) = min1
> (2) new-max = MIN(max3, max1) = max3
>
> ---min2-----min3-----max3-----min1-----max1-----max2---
>           "new-max"          "new-min"
>
> Now, the new-max becomes less than the new min.
>
> Notably, [min1, max1] can never make "w0 & 0x894b6a55 == 0"
> and thus cannot goes the fall-through branch.
> In other words, actually the fall-trough branch is a dead path.
>
> BTW, I cannot successfully compile this instruciton "if w0 != 0 goto +2;\"
> in the c inline assembly code.
> So I can only attach the bytecodes.
>
> Signed-off-by: Tao Lyu <tao.lyu@epfl.ch>
> ---
>   .../selftests/bpf/verifier/jset_reversed_range.c  | 15 +++++++++++++++
>   1 file changed, 15 insertions(+)
>   create mode 100644 tools/testing/selftests/bpf/verifier/jset_reversed_range.c
>
> diff --git a/tools/testing/selftests/bpf/verifier/jset_reversed_range.c b/tools/testing/selftests/bpf/verifier/jset_reversed_range.c
> new file mode 100644
> index 000000000000..734f492a2a96
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/verifier/jset_reversed_range.c
> @@ -0,0 +1,15 @@
> +{
> +    "BPF_JSET: incorrect scalar range",
> +    .insns = {
> +    BPF_MOV64_IMM(BPF_REG_5, 100),
> +    BPF_ALU64_IMM(BPF_DIV, BPF_REG_5, 3),
> +    BPF_ALU32_IMM(BPF_RSH, BPF_REG_5, 7),
> +    BPF_ALU64_IMM(BPF_AND, BPF_REG_5, -386969681),
> +    BPF_ALU64_IMM(BPF_SUB, BPF_REG_5, -884670597),
> +    BPF_MOV32_REG(BPF_REG_0, BPF_REG_5),
> +    BPF_JMP32_IMM(BPF_JSET, BPF_REG_0, 0x894b6a55, 1),
> +    BPF_MOV64_IMM(BPF_REG_0, 1),
> +    BPF_MOV64_IMM(BPF_REG_0, 0),
> +    BPF_EXIT_INSN(),
> +    },
> +},

Tao Lyu,

The llvm patch to support BPF_JSET asm has been merged into upstream.
    https://github.com/yonghong-song/llvm-project/commit/e247e6ff272ce70003ca67f62be178f332f9de0f

Now you can write inline asm code with BPF_JSET insn with latest llvm18.
If you intend to submit a patch to the kernel, please guard the test case
with
     #if __clang_major__ >= 18

This should also facilitate to add inline asm test cases with BPF_JSET
in bpf selftests.

Thanks,
Yonghong
diff mbox series

Patch

diff --git a/tools/testing/selftests/bpf/verifier/jset_reversed_range.c b/tools/testing/selftests/bpf/verifier/jset_reversed_range.c
new file mode 100644
index 000000000000..734f492a2a96
--- /dev/null
+++ b/tools/testing/selftests/bpf/verifier/jset_reversed_range.c
@@ -0,0 +1,15 @@ 
+{
+    "BPF_JSET: incorrect scalar range",
+    .insns = {
+    BPF_MOV64_IMM(BPF_REG_5, 100),
+    BPF_ALU64_IMM(BPF_DIV, BPF_REG_5, 3),
+    BPF_ALU32_IMM(BPF_RSH, BPF_REG_5, 7),
+    BPF_ALU64_IMM(BPF_AND, BPF_REG_5, -386969681),
+    BPF_ALU64_IMM(BPF_SUB, BPF_REG_5, -884670597),
+    BPF_MOV32_REG(BPF_REG_0, BPF_REG_5),
+    BPF_JMP32_IMM(BPF_JSET, BPF_REG_0, 0x894b6a55, 1),
+    BPF_MOV64_IMM(BPF_REG_0, 1),
+    BPF_MOV64_IMM(BPF_REG_0, 0),
+    BPF_EXIT_INSN(),
+    },
+},