* Help with verifier failure
@ 2021-04-21 12:23 Brendan Jackman
2021-04-21 15:06 ` Yonghong Song
2021-04-21 16:41 ` John Fastabend
0 siblings, 2 replies; 8+ messages in thread
From: Brendan Jackman @ 2021-04-21 12:23 UTC (permalink / raw)
To: bpf; +Cc: ast, daniel, andrii, linux-kernel, Brendan Jackman
Hi,
Recently when our internal Clang build was updated to 0e92cbd6a652 we started
hitting a verifier issue that I can't see an easy fix for. I've narrowed it down
to a minimal reproducer - this email is a patch to add that repro as a prog
test (./test_progs -t example).
Here's the BPF code I get from the attached source:
0000000000000000 <exec>:
; int BPF_PROG(exec, struct linux_binprm *bprm) {
0: 79 11 00 00 00 00 00 00 r1 = *(u64 *)(r1 + 0)
1: 7b 1a e8 ff 00 00 00 00 *(u64 *)(r10 - 24) = r1
; uint64_t args_size = bprm->argc & 0xFFFFFFF;
2: 61 17 58 00 00 00 00 00 r7 = *(u32 *)(r1 + 88)
3: b4 01 00 00 00 00 00 00 w1 = 0
; int map_key = 0;
4: 63 1a fc ff 00 00 00 00 *(u32 *)(r10 - 4) = r1
5: bf a2 00 00 00 00 00 00 r2 = r10
6: 07 02 00 00 fc ff ff ff r2 += -4
; void *buf = bpf_map_lookup_elem(&buf_map, &map_key);
7: 18 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r1 = 0 ll
9: 85 00 00 00 01 00 00 00 call 1
10: 7b 0a f0 ff 00 00 00 00 *(u64 *)(r10 - 16) = r0
11: 57 07 00 00 ff ff ff 0f r7 &= 268435455
12: bf 76 00 00 00 00 00 00 r6 = r7
; if (!buf)
13: 16 07 12 00 00 00 00 00 if w7 == 0 goto +18 <LBB0_7>
14: 79 a1 f0 ff 00 00 00 00 r1 = *(u64 *)(r10 - 16)
15: 15 01 10 00 00 00 00 00 if r1 == 0 goto +16 <LBB0_7>
16: b4 09 00 00 00 00 00 00 w9 = 0
17: b7 01 00 00 00 10 00 00 r1 = 4096
18: bf 68 00 00 00 00 00 00 r8 = r6
19: 05 00 0e 00 00 00 00 00 goto +14 <LBB0_3>
00000000000000a0 <LBB0_5>:
; void *src = (void *)(char *)bprm->p + offset;
20: 79 a1 e8 ff 00 00 00 00 r1 = *(u64 *)(r10 - 24)
21: 79 13 18 00 00 00 00 00 r3 = *(u64 *)(r1 + 24)
; uint64_t read_size = args_size - offset;
22: 0f 73 00 00 00 00 00 00 r3 += r7
23: 07 03 00 00 00 f0 ff ff r3 += -4096
; (void) bpf_probe_read_user(buf, read_size, src);
24: 79 a1 f0 ff 00 00 00 00 r1 = *(u64 *)(r10 - 16)
25: 85 00 00 00 70 00 00 00 call 112
; for (int i = 0; i < 512 && offset < args_size; i++) {
26: 26 09 05 00 fe 01 00 00 if w9 > 510 goto +5 <LBB0_7>
27: 07 08 00 00 00 f0 ff ff r8 += -4096
28: bf 71 00 00 00 00 00 00 r1 = r7
29: 07 01 00 00 00 10 00 00 r1 += 4096
30: 04 09 00 00 01 00 00 00 w9 += 1
; for (int i = 0; i < 512 && offset < args_size; i++) {
31: ad 67 02 00 00 00 00 00 if r7 < r6 goto +2 <LBB0_3>
0000000000000100 <LBB0_7>:
; int BPF_PROG(exec, struct linux_binprm *bprm) {
32: b4 00 00 00 00 00 00 00 w0 = 0
33: 95 00 00 00 00 00 00 00 exit
0000000000000110 <LBB0_3>:
34: bf 17 00 00 00 00 00 00 r7 = r1
; (void) bpf_probe_read_user(buf, read_size, src);
35: bc 82 00 00 00 00 00 00 w2 = w8
36: a5 08 ef ff 00 10 00 00 if r8 < 4096 goto -17 <LBB0_5>
37: b4 02 00 00 00 10 00 00 w2 = 4096
38: 05 00 ed ff 00 00 00 00 goto -19 <LBB0_5>
The full log I get is at
https://gist.githubusercontent.com/bjackman/2928c4ff4cc89545f3993bddd9d5edb2/raw/feda6d7c165d24be3ea72c3cf7045c50246abd83/gistfile1.txt,
but basically the verifier runs through the loop a large number of times, going
down the true path of the `if (read_size > CHUNK_LEN)` every time. Then
eventually it takes the false path.
In the disassembly this is basically instructions 35-37 - pseudocode:
w2 = w8
if (r8 < 4096) {
w2 = 4096
}
w2 can't exceed 4096 but the verifier doesn't seem to "backpropagate" those
bounds from r8 (note the umax_value for R8 goes to 4095 after the branch from 36
to 20, but R2's umax_value is still 266342399)
from 31 to 34: R0_w=inv(id=0) R1_w=inv2097152 R6=inv(id=2,umin_value=2093057,umax_value=268435455,var_off=(0x0; 0xfffffff)) R7_w=inv2093056 R8_w=inv(id=0,umax_value=266342399,var_off=(0x0; 0xfffffff)) R9_w=invP511 R10=fp0 fp-8=mmmm???? fp-16=map_value fp-24=ptr_
; int BPF_PROG(exec, struct linux_binprm *bprm) {
34: (bf) r7 = r1
; (void) bpf_probe_read_user(buf, read_size, src);
35: (bc) w2 = w8
36: (a5) if r8 < 0x1000 goto pc-17
from 36 to 20: R0_w=inv(id=0) R1_w=inv2097152 R2_w=inv(id=0,umax_value=266342399,var_off=(0x0; 0xfffffff)) R6=inv(id=2,umin_value=2093057,umax_value=268435455,var_off=(0x0; 0xfffffff)) R7_w=inv2097152 R8_w=inv(id=0,umax_value=4095,var_off=(0x0; 0xfff)) R9_w=invP511 R10=fp0 fp-8=mmmm???? fp-16=map_value fp-24=ptr_
; void *src = (void *)(char *)bprm->p + offset;
20: (79) r1 = *(u64 *)(r10 -24)
21: (79) r3 = *(u64 *)(r1 +24)
; uint64_t read_size = args_size - offset;
22: (0f) r3 += r7
23: (07) r3 += -4096
; (void) bpf_probe_read_user(buf, read_size, src);
24: (79) r1 = *(u64 *)(r10 -16)
25: (85) call bpf_probe_read_user#112
R0_w=inv(id=0) R1_w=map_value(id=0,off=0,ks=4,vs=4096,imm=0) R2_w=inv(id=0,umax_value=266342399,var_off=(0x0; 0xfffffff)) R3_w=inv(id=0) R6=inv(id=2,umin_value=2093057,umax_value=268435455,var_off=(0x0; 0xfffffff)) R7_w=inv2097152 R8_w=inv(id=0,umax_value=4095,var_off=(0x0; 0xfff)) R9_w=invP511 R10=fp0 fp-8=mmmm???? fp-16=map_value fp-24=ptr_
R0_w=inv(id=0) R1_w=map_value(id=0,off=0,ks=4,vs=4096,imm=0) R2_w=inv(id=0,umax_value=266342399,var_off=(0x0; 0xfffffff)) R3_w=inv(id=0) R6=inv(id=2,umin_value=2093057,umax_value=268435455,var_off=(0x0; 0xfffffff)) R7_w=inv2097152 R8_w=inv(id=0,umax_value=4095,var_off=(0x0; 0xfff)) R9_w=invP511 R10=fp0 fp-8=mmmm???? fp-16=map_value fp-24=ptr_
invalid access to map value, value_size=4096 off=0 size=266342399
R1 min value is outside of the allowed memory range
processed 9239 insns (limit 1000000) max_states_per_insn 4 total_states 133 peak_states 133 mark_read 2
This seems like it must be a common pitfall, any idea what we can do to fix it
and avoid it in future? Am I misunderstanding the issue?
Cheers,
Brendan
---
.../selftests/bpf/prog_tests/example.c | 17 ++++++++
tools/testing/selftests/bpf/progs/example.c | 42 +++++++++++++++++++
2 files changed, 59 insertions(+)
create mode 100644 tools/testing/selftests/bpf/prog_tests/example.c
create mode 100644 tools/testing/selftests/bpf/progs/example.c
diff --git a/tools/testing/selftests/bpf/prog_tests/example.c b/tools/testing/selftests/bpf/prog_tests/example.c
new file mode 100644
index 000000000000..9c36858019b3
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/example.c
@@ -0,0 +1,17 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <test_progs.h>
+
+#include "example.skel.h"
+
+void test_example(void)
+{
+ struct example *skel;
+ __u32 duration = 0;
+
+ skel = example__open_and_load();
+ if (CHECK(!skel, "skel_load", "couldn't load program\n"))
+ return;
+
+ example__destroy(skel);
+}
diff --git a/tools/testing/selftests/bpf/progs/example.c b/tools/testing/selftests/bpf/progs/example.c
new file mode 100644
index 000000000000..6c90060e92e0
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/example.c
@@ -0,1 +1,42 @@
+#include "vmlinux.h"
+
+#include <bpf/bpf_helpers.h>
+#include <bpf/bpf_tracing.h>
+
+char _license[] SEC("license") = "GPL";
+
+#define CHUNK_LEN (uint64_t)4096
+struct {
+ __uint(type, BPF_MAP_TYPE_PERCPU_ARRAY);
+ __uint(key_size, sizeof(int));
+ __uint(value_size, CHUNK_LEN);
+ __uint(max_entries, 1);
+} buf_map SEC(".maps");
+
+SEC("lsm/bprm_committed_creds")
+int BPF_PROG(exec, struct linux_binprm *bprm) {
+ /* Actual value doesn't make sense here, just picking something unknown to the
+ * verifier that produces simple disassembly
+ */
+ uint64_t args_size = bprm->argc & 0xFFFFFFF;
+ int map_key = 0;
+ void *buf = bpf_map_lookup_elem(&buf_map, &map_key);
+ uint64_t offset = 0;
+ if (!buf)
+ return 0;
+
+ for (int i = 0; i < 512 && offset < args_size; i++) {
+ void *src = (void *)(char *)bprm->p + offset;
+ uint64_t read_size = args_size - offset;
+
+ if (read_size > CHUNK_LEN) {
+ read_size = CHUNK_LEN;
+ }
+
+ (void) bpf_probe_read_user(buf, read_size, src);
+
+ offset += CHUNK_LEN;
+ }
+
+ return 0;
+}
--
2.31.1.368.gbe11c130af-goog
^ permalink raw reply related [flat|nested] 8+ messages in thread
* Re: Help with verifier failure
2021-04-21 12:23 Help with verifier failure Brendan Jackman
@ 2021-04-21 15:06 ` Yonghong Song
2021-04-21 16:59 ` Yonghong Song
2021-04-21 16:41 ` John Fastabend
1 sibling, 1 reply; 8+ messages in thread
From: Yonghong Song @ 2021-04-21 15:06 UTC (permalink / raw)
To: Brendan Jackman, bpf; +Cc: ast, daniel, andrii, linux-kernel
On 4/21/21 5:23 AM, Brendan Jackman wrote:
> Hi,
>
> Recently when our internal Clang build was updated to 0e92cbd6a652 we started
> hitting a verifier issue that I can't see an easy fix for. I've narrowed it down
> to a minimal reproducer - this email is a patch to add that repro as a prog
> test (./test_progs -t example).
>
> Here's the BPF code I get from the attached source:
>
> 0000000000000000 <exec>:
> ; int BPF_PROG(exec, struct linux_binprm *bprm) {
> 0: 79 11 00 00 00 00 00 00 r1 = *(u64 *)(r1 + 0)
> 1: 7b 1a e8 ff 00 00 00 00 *(u64 *)(r10 - 24) = r1
> ; uint64_t args_size = bprm->argc & 0xFFFFFFF;
> 2: 61 17 58 00 00 00 00 00 r7 = *(u32 *)(r1 + 88)
> 3: b4 01 00 00 00 00 00 00 w1 = 0
> ; int map_key = 0;
> 4: 63 1a fc ff 00 00 00 00 *(u32 *)(r10 - 4) = r1
> 5: bf a2 00 00 00 00 00 00 r2 = r10
> 6: 07 02 00 00 fc ff ff ff r2 += -4
> ; void *buf = bpf_map_lookup_elem(&buf_map, &map_key);
> 7: 18 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r1 = 0 ll
> 9: 85 00 00 00 01 00 00 00 call 1
> 10: 7b 0a f0 ff 00 00 00 00 *(u64 *)(r10 - 16) = r0
> 11: 57 07 00 00 ff ff ff 0f r7 &= 268435455
> 12: bf 76 00 00 00 00 00 00 r6 = r7
> ; if (!buf)
> 13: 16 07 12 00 00 00 00 00 if w7 == 0 goto +18 <LBB0_7>
> 14: 79 a1 f0 ff 00 00 00 00 r1 = *(u64 *)(r10 - 16)
> 15: 15 01 10 00 00 00 00 00 if r1 == 0 goto +16 <LBB0_7>
> 16: b4 09 00 00 00 00 00 00 w9 = 0
> 17: b7 01 00 00 00 10 00 00 r1 = 4096
> 18: bf 68 00 00 00 00 00 00 r8 = r6
> 19: 05 00 0e 00 00 00 00 00 goto +14 <LBB0_3>
>
> 00000000000000a0 <LBB0_5>:
> ; void *src = (void *)(char *)bprm->p + offset;
> 20: 79 a1 e8 ff 00 00 00 00 r1 = *(u64 *)(r10 - 24)
> 21: 79 13 18 00 00 00 00 00 r3 = *(u64 *)(r1 + 24)
> ; uint64_t read_size = args_size - offset;
> 22: 0f 73 00 00 00 00 00 00 r3 += r7
> 23: 07 03 00 00 00 f0 ff ff r3 += -4096
> ; (void) bpf_probe_read_user(buf, read_size, src);
> 24: 79 a1 f0 ff 00 00 00 00 r1 = *(u64 *)(r10 - 16)
> 25: 85 00 00 00 70 00 00 00 call 112
> ; for (int i = 0; i < 512 && offset < args_size; i++) {
> 26: 26 09 05 00 fe 01 00 00 if w9 > 510 goto +5 <LBB0_7>
> 27: 07 08 00 00 00 f0 ff ff r8 += -4096
> 28: bf 71 00 00 00 00 00 00 r1 = r7
> 29: 07 01 00 00 00 10 00 00 r1 += 4096
> 30: 04 09 00 00 01 00 00 00 w9 += 1
> ; for (int i = 0; i < 512 && offset < args_size; i++) {
> 31: ad 67 02 00 00 00 00 00 if r7 < r6 goto +2 <LBB0_3>
>
> 0000000000000100 <LBB0_7>:
> ; int BPF_PROG(exec, struct linux_binprm *bprm) {
> 32: b4 00 00 00 00 00 00 00 w0 = 0
> 33: 95 00 00 00 00 00 00 00 exit
>
> 0000000000000110 <LBB0_3>:
> 34: bf 17 00 00 00 00 00 00 r7 = r1
> ; (void) bpf_probe_read_user(buf, read_size, src);
> 35: bc 82 00 00 00 00 00 00 w2 = w8
> 36: a5 08 ef ff 00 10 00 00 if r8 < 4096 goto -17 <LBB0_5>
> 37: b4 02 00 00 00 10 00 00 w2 = 4096
> 38: 05 00 ed ff 00 00 00 00 goto -19 <LBB0_5>
>
>
> The full log I get is at
> https://gist.githubusercontent.com/bjackman/2928c4ff4cc89545f3993bddd9d5edb2/raw/feda6d7c165d24be3ea72c3cf7045c50246abd83/gistfile1.txt ,
> but basically the verifier runs through the loop a large number of times, going
> down the true path of the `if (read_size > CHUNK_LEN)` every time. Then
> eventually it takes the false path.
>
> In the disassembly this is basically instructions 35-37 - pseudocode:
> w2 = w8
> if (r8 < 4096) {
> w2 = 4096
> }
>
> w2 can't exceed 4096 but the verifier doesn't seem to "backpropagate" those
> bounds from r8 (note the umax_value for R8 goes to 4095 after the branch from 36
> to 20, but R2's umax_value is still 266342399)
>
> from 31 to 34: R0_w=inv(id=0) R1_w=inv2097152 R6=inv(id=2,umin_value=2093057,umax_value=268435455,var_off=(0x0; 0xfffffff)) R7_w=inv2093056 R8_w=inv(id=0,umax_value=266342399,var_off=(0x0; 0xfffffff)) R9_w=invP511 R10=fp0 fp-8=mmmm???? fp-16=map_value fp-24=ptr_
> ; int BPF_PROG(exec, struct linux_binprm *bprm) {
> 34: (bf) r7 = r1
> ; (void) bpf_probe_read_user(buf, read_size, src);
> 35: (bc) w2 = w8
> 36: (a5) if r8 < 0x1000 goto pc-17
>
> from 36 to 20: R0_w=inv(id=0) R1_w=inv2097152 R2_w=inv(id=0,umax_value=266342399,var_off=(0x0; 0xfffffff)) R6=inv(id=2,umin_value=2093057,umax_value=268435455,var_off=(0x0; 0xfffffff)) R7_w=inv2097152 R8_w=inv(id=0,umax_value=4095,var_off=(0x0; 0xfff)) R9_w=invP511 R10=fp0 fp-8=mmmm???? fp-16=map_value fp-24=ptr_
> ; void *src = (void *)(char *)bprm->p + offset;
> 20: (79) r1 = *(u64 *)(r10 -24)
> 21: (79) r3 = *(u64 *)(r1 +24)
> ; uint64_t read_size = args_size - offset;
> 22: (0f) r3 += r7
> 23: (07) r3 += -4096
> ; (void) bpf_probe_read_user(buf, read_size, src);
> 24: (79) r1 = *(u64 *)(r10 -16)
> 25: (85) call bpf_probe_read_user#112
> R0_w=inv(id=0) R1_w=map_value(id=0,off=0,ks=4,vs=4096,imm=0) R2_w=inv(id=0,umax_value=266342399,var_off=(0x0; 0xfffffff)) R3_w=inv(id=0) R6=inv(id=2,umin_value=2093057,umax_value=268435455,var_off=(0x0; 0xfffffff)) R7_w=inv2097152 R8_w=inv(id=0,umax_value=4095,var_off=(0x0; 0xfff)) R9_w=invP511 R10=fp0 fp-8=mmmm???? fp-16=map_value fp-24=ptr_
> R0_w=inv(id=0) R1_w=map_value(id=0,off=0,ks=4,vs=4096,imm=0) R2_w=inv(id=0,umax_value=266342399,var_off=(0x0; 0xfffffff)) R3_w=inv(id=0) R6=inv(id=2,umin_value=2093057,umax_value=268435455,var_off=(0x0; 0xfffffff)) R7_w=inv2097152 R8_w=inv(id=0,umax_value=4095,var_off=(0x0; 0xfff)) R9_w=invP511 R10=fp0 fp-8=mmmm???? fp-16=map_value fp-24=ptr_
> invalid access to map value, value_size=4096 off=0 size=266342399
> R1 min value is outside of the allowed memory range
> processed 9239 insns (limit 1000000) max_states_per_insn 4 total_states 133 peak_states 133 mark_read 2
Thanks, Brendan. Looks at least the verifier failure is triggered
by recent clang changes. I will take a look whether we could
improve verifier for such a case and whether we could improve
clang to avoid generate such codes the verifier doesn't like.
Will get back to you once I had concrete analysis.
>
> This seems like it must be a common pitfall, any idea what we can do to fix it
> and avoid it in future? Am I misunderstanding the issue?
>
> Cheers,
> Brendan
>
[...]
^ permalink raw reply [flat|nested] 8+ messages in thread
* RE: Help with verifier failure
2021-04-21 12:23 Help with verifier failure Brendan Jackman
2021-04-21 15:06 ` Yonghong Song
@ 2021-04-21 16:41 ` John Fastabend
1 sibling, 0 replies; 8+ messages in thread
From: John Fastabend @ 2021-04-21 16:41 UTC (permalink / raw)
To: Brendan Jackman, bpf; +Cc: ast, daniel, andrii, linux-kernel, Brendan Jackman
Brendan Jackman wrote:
> Hi,
>
> Recently when our internal Clang build was updated to 0e92cbd6a652 we started
> hitting a verifier issue that I can't see an easy fix for. I've narrowed it down
> to a minimal reproducer - this email is a patch to add that repro as a prog
> test (./test_progs -t example).
>
> Here's the BPF code I get from the attached source:
>
[...]
>
> w2 can't exceed 4096 but the verifier doesn't seem to "backpropagate" those
> bounds from r8 (note the umax_value for R8 goes to 4095 after the branch from 36
> to 20, but R2's umax_value is still 266342399)
>
> from 31 to 34: R0_w=inv(id=0) R1_w=inv2097152 R6=inv(id=2,umin_value=2093057,umax_value=268435455,var_off=(0x0; 0xfffffff)) R7_w=inv2093056 R8_w=inv(id=0,umax_value=266342399,var_off=(0x0; 0xfffffff)) R9_w=invP511 R10=fp0 fp-8=mmmm???? fp-16=map_value fp-24=ptr_
> ; int BPF_PROG(exec, struct linux_binprm *bprm) {
> 34: (bf) r7 = r1
> ; (void) bpf_probe_read_user(buf, read_size, src);
> 35: (bc) w2 = w8
> 36: (a5) if r8 < 0x1000 goto pc-17
>
> from 36 to 20: R0_w=inv(id=0) R1_w=inv2097152 R2_w=inv(id=0,umax_value=266342399,var_off=(0x0; 0xfffffff)) R6=inv(id=2,umin_value=2093057,umax_value=268435455,var_off=(0x0; 0xfffffff)) R7_w=inv2097152 R8_w=inv(id=0,umax_value=4095,var_off=(0x0; 0xfff)) R9_w=invP511 R10=fp0 fp-8=mmmm???? fp-16=map_value fp-24=ptr_
> ; void *src = (void *)(char *)bprm->p + offset;
> 20: (79) r1 = *(u64 *)(r10 -24)
> 21: (79) r3 = *(u64 *)(r1 +24)
> ; uint64_t read_size = args_size - offset;
> 22: (0f) r3 += r7
> 23: (07) r3 += -4096
> ; (void) bpf_probe_read_user(buf, read_size, src);
> 24: (79) r1 = *(u64 *)(r10 -16)
> 25: (85) call bpf_probe_read_user#112
> R0_w=inv(id=0) R1_w=map_value(id=0,off=0,ks=4,vs=4096,imm=0) R2_w=inv(id=0,umax_value=266342399,var_off=(0x0; 0xfffffff)) R3_w=inv(id=0) R6=inv(id=2,umin_value=2093057,umax_value=268435455,var_off=(0x0; 0xfffffff)) R7_w=inv2097152 R8_w=inv(id=0,umax_value=4095,var_off=(0x0; 0xfff)) R9_w=invP511 R10=fp0 fp-8=mmmm???? fp-16=map_value fp-24=ptr_
> R0_w=inv(id=0) R1_w=map_value(id=0,off=0,ks=4,vs=4096,imm=0) R2_w=inv(id=0,umax_value=266342399,var_off=(0x0; 0xfffffff)) R3_w=inv(id=0) R6=inv(id=2,umin_value=2093057,umax_value=268435455,var_off=(0x0; 0xfffffff)) R7_w=inv2097152 R8_w=inv(id=0,umax_value=4095,var_off=(0x0; 0xfff)) R9_w=invP511 R10=fp0 fp-8=mmmm???? fp-16=map_value fp-24=ptr_
> invalid access to map value, value_size=4096 off=0 size=266342399
> R1 min value is outside of the allowed memory range
> processed 9239 insns (limit 1000000) max_states_per_insn 4 total_states 133 peak_states 133 mark_read 2
>
> This seems like it must be a common pitfall, any idea what we can do to fix it
> and avoid it in future? Am I misunderstanding the issue?
We also hit this from time to time. I have asm blocks to work-around
at the moment. I was going to see how ugly propagating the bounds
backwards gets. I had some code for this some time ago but never
pushed it, it was smashed in with some CFG building for loops back
before loops were possible. I can take a look next week unless someone
beats me there.
>
> Cheers,
> Brendan
>
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Help with verifier failure
2021-04-21 15:06 ` Yonghong Song
@ 2021-04-21 16:59 ` Yonghong Song
2021-04-22 13:55 ` Brendan Jackman
0 siblings, 1 reply; 8+ messages in thread
From: Yonghong Song @ 2021-04-21 16:59 UTC (permalink / raw)
To: Brendan Jackman, bpf; +Cc: ast, daniel, andrii, linux-kernel
On 4/21/21 8:06 AM, Yonghong Song wrote:
>
>
> On 4/21/21 5:23 AM, Brendan Jackman wrote:
>> Hi,
>>
>> Recently when our internal Clang build was updated to 0e92cbd6a652 we
>> started
>> hitting a verifier issue that I can't see an easy fix for. I've
>> narrowed it down
>> to a minimal reproducer - this email is a patch to add that repro as a
>> prog
>> test (./test_progs -t example).
>>
>> Here's the BPF code I get from the attached source:
>>
>> 0000000000000000 <exec>:
>> ; int BPF_PROG(exec, struct linux_binprm *bprm) {
>> 0: 79 11 00 00 00 00 00 00 r1 = *(u64 *)(r1 + 0)
>> 1: 7b 1a e8 ff 00 00 00 00 *(u64 *)(r10 - 24) = r1
>> ; uint64_t args_size = bprm->argc & 0xFFFFFFF;
>> 2: 61 17 58 00 00 00 00 00 r7 = *(u32 *)(r1 + 88)
>> 3: b4 01 00 00 00 00 00 00 w1 = 0
>> ; int map_key = 0;
>> 4: 63 1a fc ff 00 00 00 00 *(u32 *)(r10 - 4) = r1
>> 5: bf a2 00 00 00 00 00 00 r2 = r10
>> 6: 07 02 00 00 fc ff ff ff r2 += -4
>> ; void *buf = bpf_map_lookup_elem(&buf_map, &map_key);
>> 7: 18 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r1 = 0ll
>> 9: 85 00 00 00 01 00 00 00 call 1
>> 10: 7b 0a f0 ff 00 00 00 00 *(u64 *)(r10 - 16) = r0
>> 11: 57 07 00 00 ff ff ff 0f r7 &= 268435455
>> 12: bf 76 00 00 00 00 00 00 r6 = r7
>> ; if (!buf)
>> 13: 16 07 12 00 00 00 00 00 if w7 == 0 goto +18 <LBB0_7>
>> 14: 79 a1 f0 ff 00 00 00 00 r1 = *(u64 *)(r10 - 16)
>> 15: 15 01 10 00 00 00 00 00 if r1 == 0 goto +16 <LBB0_7>
>> 16: b4 09 00 00 00 00 00 00 w9 = 0
>> 17: b7 01 00 00 00 10 00 00 r1 = 4096
>> 18: bf 68 00 00 00 00 00 00 r8 = r6
>> 19: 05 00 0e 00 00 00 00 00 goto +14 <LBB0_3>
>>
>> 00000000000000a0 <LBB0_5>:
>> ; void *src = (void *)(char *)bprm->p + offset;
>> 20: 79 a1 e8 ff 00 00 00 00 r1 = *(u64 *)(r10 - 24)
>> 21: 79 13 18 00 00 00 00 00 r3 = *(u64 *)(r1 + 24)
>> ; uint64_t read_size = args_size - offset;
>> 22: 0f 73 00 00 00 00 00 00 r3 += r7
>> 23: 07 03 00 00 00 f0 ff ff r3 += -4096
>> ; (void) bpf_probe_read_user(buf, read_size, src);
>> 24: 79 a1 f0 ff 00 00 00 00 r1 = *(u64 *)(r10 - 16)
>> 25: 85 00 00 00 70 00 00 00 call 112
>> ; for (int i = 0; i < 512 && offset < args_size; i++) {
>> 26: 26 09 05 00 fe 01 00 00 if w9 > 510 goto +5 <LBB0_7>
>> 27: 07 08 00 00 00 f0 ff ff r8 += -4096
>> 28: bf 71 00 00 00 00 00 00 r1 = r7
>> 29: 07 01 00 00 00 10 00 00 r1 += 4096
>> 30: 04 09 00 00 01 00 00 00 w9 += 1
>> ; for (int i = 0; i < 512 && offset < args_size; i++) {
>> 31: ad 67 02 00 00 00 00 00 if r7 < r6 goto +2 <LBB0_3>
>>
>> 0000000000000100 <LBB0_7>:
>> ; int BPF_PROG(exec, struct linux_binprm *bprm) {
>> 32: b4 00 00 00 00 00 00 00 w0 = 0
>> 33: 95 00 00 00 00 00 00 00 exit
>>
>> 0000000000000110 <LBB0_3>:
>> 34: bf 17 00 00 00 00 00 00 r7 = r1
>> ; (void) bpf_probe_read_user(buf, read_size, src);
>> 35: bc 82 00 00 00 00 00 00 w2 = w8
>> 36: a5 08 ef ff 00 10 00 00 if r8 < 4096 goto -17 <LBB0_5>
>> 37: b4 02 00 00 00 10 00 00 w2 = 4096
>> 38: 05 00 ed ff 00 00 00 00 goto -19 <LBB0_5>
>>
>>
>> The full log I get is at
>> https://gist.githubusercontent.com/bjackman/2928c4ff4cc89545f3993bddd9d5edb2/raw/feda6d7c165d24be3ea72c3cf7045c50246abd83/gistfile1.txt
>> ,
>> but basically the verifier runs through the loop a large number of
>> times,going
>> down the true path of the `if (read_size > CHUNK_LEN)` every time. Then
>> eventually it takes the false path.
>>
>> In the disassembly this is basically instructions 35-37 - pseudocode:
>> w2 = w8
>> if (r8 < 4096) {
>> w2 = 4096
>> }
>>
>> w2 can't exceed 4096 but the verifier doesn't seem to "backpropagate"
>> those
>> bounds from r8 (note the umax_value for R8 goes to 4095 after the
>> branch from 36
>> to 20, but R2's umax_value is still 266342399)
>>
>> from 31 to 34: R0_w=inv(id=0) R1_w=inv2097152
>> R6=inv(id=2,umin_value=2093057,umax_value=268435455,var_off=(0x0;
>> 0xfffffff)) R7_w=inv2093056
>> R8_w=inv(id=0,umax_value=266342399,var_off=(0x0; 0xfffffff))
>> R9_w=invP511 R10=fp0 fp-8=mmmm???? fp-16=map_value fp-24=ptr_
>> ; int BPF_PROG(exec, struct linux_binprm *bprm) {
>> 34: (bf) r7 = r1
>> ; (void) bpf_probe_read_user(buf, read_size, src);
>> 35: (bc) w2 = w8
>> 36: (a5) if r8 < 0x1000 goto pc-17
>>
>> from 36 to 20: R0_w=inv(id=0) R1_w=inv2097152
>> R2_w=inv(id=0,umax_value=266342399,var_off=(0x0; 0xfffffff))
>> R6=inv(id=2,umin_value=2093057,umax_value=268435455,var_off=(0x0;
>> 0xfffffff)) R7_w=inv2097152
>> R8_w=inv(id=0,umax_value=4095,var_off=(0x0; 0xfff)) R9_w=invP511
>> R10=fp0 fp-8=mmmm???? fp-16=map_value fp-24=ptr_
>> ; void *src = (void *)(char *)bprm->p + offset;
>> 20: (79) r1 = *(u64 *)(r10 -24)
>> 21: (79) r3 = *(u64 *)(r1 +24)
>> ; uint64_t read_size = args_size - offset;
>> 22: (0f) r3 += r7
>> 23: (07) r3 += -4096
>> ; (void) bpf_probe_read_user(buf, read_size, src);
>> 24: (79) r1 = *(u64 *)(r10 -16)
>> 25: (85) call bpf_probe_read_user#112
>> R0_w=inv(id=0) R1_w=map_value(id=0,off=0,ks=4,vs=4096,imm=0)
>> R2_w=inv(id=0,umax_value=266342399,var_off=(0x0; 0xfffffff))
>> R3_w=inv(id=0)
>> R6=inv(id=2,umin_value=2093057,umax_value=268435455,var_off=(0x0;
>> 0xfffffff)) R7_w=inv2097152
>> R8_w=inv(id=0,umax_value=4095,var_off=(0x0; 0xfff)) R9_w=invP511
>> R10=fp0 fp-8=mmmm????fp-16=map_value fp-24=ptr_
>> R0_w=inv(id=0) R1_w=map_value(id=0,off=0,ks=4,vs=4096,imm=0)
>> R2_w=inv(id=0,umax_value=266342399,var_off=(0x0; 0xfffffff))
>> R3_w=inv(id=0)
>> R6=inv(id=2,umin_value=2093057,umax_value=268435455,var_off=(0x0;
>> 0xfffffff)) R7_w=inv2097152
>> R8_w=inv(id=0,umax_value=4095,var_off=(0x0; 0xfff)) R9_w=invP511
>> R10=fp0 fp-8=mmmm????fp-16=map_value fp-24=ptr_
>> invalid access to map value, value_size=4096 off=0 size=266342399
>> R1 min value is outside of the allowed memory range
>> processed 9239 insns (limit 1000000) max_states_per_insn 4
>> total_states 133 peak_states 133 mark_read 2
>
> Thanks, Brendan. Looks at least the verifier failure is triggered
> by recent clang changes. I will take a look whether we could
> improve verifier for such a case and whether we could improve
> clang to avoid generate such codes the verifier doesn't like.
> Will get back to you once I had concrete analysis.
>
>>
>> This seems like it must be a common pitfall, any idea what we can do
>> to fix it
>> and avoid it in future? Am I misunderstanding the issue?
First, for the example code you provided, I checked with llvm11, llvm12
and latest trunk llvm (llvm13-dev) and they all generated similar codes,
which may trigger verifier failure. Somehow you original code could be
different may only show up with a recent llvm, I guess.
Checking llvm IR, the divergence between "w2 = w8" and "if r8 < 0x1000"
appears in insn scheduling phase related handling PHIs. Need to further
check whether it is possible to prevent the compiler from generating
such codes.
The latest kernel already had the ability to track register equivalence.
However, the tracking is conservative for 32bit mov like "w2 = w8" as
you described in the above. if we have code like "r2 = r8; if r8 <
0x1000 ...", we will be all good.
The following hack fixed the issue,
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 58730872f7e5..54f418fd6a4a 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -7728,12 +7728,20 @@ static int check_alu_op(struct bpf_verifier_env
*env, struct bpf_insn *insn)
insn->src_reg);
return -EACCES;
} else if (src_reg->type == SCALAR_VALUE) {
+ /* If src_reg is in 32bit range,
there is
+ * no need to reset the ID.
+ */
+ bool is_32bit_src =
src_reg->umax_value <= 0x7fffffff;
+
+ if (is_32bit_src && !src_reg->id)
+ src_reg->id = ++env->id_gen;
*dst_reg = *src_reg;
/* Make sure ID is cleared
otherwise
* dst_reg min/max could be
incorrectly
* propagated into src_reg by
find_equal_scalars()
*/
- dst_reg->id = 0;
+ if (!is_32bit_src)
+ dst_reg->id = 0;
dst_reg->live |= REG_LIVE_WRITTEN;
dst_reg->subreg_def =
env->insn_idx + 1;
} else {
Basically, for a 32bit mov insn like "w2 = w8", if we can ensure
that "w8" is 32bit and has no possibility that upper 32bit is set
for r8, we can declare them equivalent. This fixed your issue.
Will try to submit a formal patch later.
>>
>> Cheers,
>> Brendan
>>
> [...]
^ permalink raw reply related [flat|nested] 8+ messages in thread
* Re: Help with verifier failure
2021-04-21 16:59 ` Yonghong Song
@ 2021-04-22 13:55 ` Brendan Jackman
2021-04-22 14:35 ` Yonghong Song
0 siblings, 1 reply; 8+ messages in thread
From: Brendan Jackman @ 2021-04-22 13:55 UTC (permalink / raw)
To: Yonghong Song
Cc: bpf, Alexei Starovoitov, Daniel Borkmann, Andrii Nakryiko, LKML
On Wed, 21 Apr 2021 at 18:59, Yonghong Song <yhs@fb.com> wrote:
> On 4/21/21 8:06 AM, Yonghong Song wrote:
> > On 4/21/21 5:23 AM, Brendan Jackman wrote:
> > Thanks, Brendan. Looks at least the verifier failure is triggered
> > by recent clang changes. I will take a look whether we could
> > improve verifier for such a case and whether we could improve
> > clang to avoid generate such codes the verifier doesn't like.
> > Will get back to you once I had concrete analysis.
> >
> >>
> >> This seems like it must be a common pitfall, any idea what we can do
> >> to fix it
> >> and avoid it in future? Am I misunderstanding the issue?
>
> First, for the example code you provided, I checked with llvm11, llvm12
> and latest trunk llvm (llvm13-dev) and they all generated similar codes,
> which may trigger verifier failure. Somehow you original code could be
> different may only show up with a recent llvm, I guess.
>
> Checking llvm IR, the divergence between "w2 = w8" and "if r8 < 0x1000"
> appears in insn scheduling phase related handling PHIs. Need to further
> check whether it is possible to prevent the compiler from generating
> such codes.
>
> The latest kernel already had the ability to track register equivalence.
> However, the tracking is conservative for 32bit mov like "w2 = w8" as
> you described in the above. if we have code like "r2 = r8; if r8 <
> 0x1000 ...", we will be all good.
>
> The following hack fixed the issue,
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 58730872f7e5..54f418fd6a4a 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -7728,12 +7728,20 @@ static int check_alu_op(struct bpf_verifier_env
> *env, struct bpf_insn *insn)
> insn->src_reg);
> return -EACCES;
> } else if (src_reg->type == SCALAR_VALUE) {
> + /* If src_reg is in 32bit range,
> there is
> + * no need to reset the ID.
> + */
> + bool is_32bit_src =
> src_reg->umax_value <= 0x7fffffff;
> +
> + if (is_32bit_src && !src_reg->id)
> + src_reg->id = ++env->id_gen;
> *dst_reg = *src_reg;
> /* Make sure ID is cleared
> otherwise
> * dst_reg min/max could be
> incorrectly
> * propagated into src_reg by
> find_equal_scalars()
> */
> - dst_reg->id = 0;
> + if (!is_32bit_src)
> + dst_reg->id = 0;
> dst_reg->live |= REG_LIVE_WRITTEN;
> dst_reg->subreg_def =
> env->insn_idx + 1;
> } else {
>
> Basically, for a 32bit mov insn like "w2 = w8", if we can ensure
> that "w8" is 32bit and has no possibility that upper 32bit is set
> for r8, we can declare them equivalent. This fixed your issue.
>
> Will try to submit a formal patch later.
Ah.. I did not realise this equivalence tracking with reg.id was there
for scalar values! I also didn't take any notice of the use of 32-bit
operations in the assembly, thanks for pointing that out.
Yes it sounds like this is certainly worth fixing in the kernel - even
if Clang stops generating the code today it will probably start doing
so again in the future. I can also help with the verifier work if
needed.
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Help with verifier failure
2021-04-22 13:55 ` Brendan Jackman
@ 2021-04-22 14:35 ` Yonghong Song
2021-05-07 15:05 ` Brendan Jackman
0 siblings, 1 reply; 8+ messages in thread
From: Yonghong Song @ 2021-04-22 14:35 UTC (permalink / raw)
To: Brendan Jackman
Cc: bpf, Alexei Starovoitov, Daniel Borkmann, Andrii Nakryiko, LKML
On 4/22/21 6:55 AM, Brendan Jackman wrote:
> On Wed, 21 Apr 2021 at 18:59, Yonghong Song <yhs@fb.com> wrote:
>> On 4/21/21 8:06 AM, Yonghong Song wrote:
>>> On 4/21/21 5:23 AM, Brendan Jackman wrote:
>>> Thanks, Brendan. Looks at least the verifier failure is triggered
>>> by recent clang changes. I will take a look whether we could
>>> improve verifier for such a case and whether we could improve
>>> clang to avoid generate such codes the verifier doesn't like.
>>> Will get back to you once I had concrete analysis.
>>>
>>>>
>>>> This seems like it must be a common pitfall, any idea what we can do
>>>> to fix it
>>>> and avoid it in future? Am I misunderstanding the issue?
>>
>> First, for the example code you provided, I checked with llvm11, llvm12
>> and latest trunk llvm (llvm13-dev) and they all generated similar codes,
>> which may trigger verifier failure. Somehow you original code could be
>> different may only show up with a recent llvm, I guess.
>>
>> Checking llvm IR, the divergence between "w2 = w8" and "if r8 < 0x1000"
>> appears in insn scheduling phase related handling PHIs. Need to further
>> check whether it is possible to prevent the compiler from generating
>> such codes.
>>
>> The latest kernel already had the ability to track register equivalence.
>> However, the tracking is conservative for 32bit mov like "w2 = w8" as
>> you described in the above. if we have code like "r2 = r8; if r8 <
>> 0x1000 ...", we will be all good.
>>
>> The following hack fixed the issue,
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 58730872f7e5..54f418fd6a4a 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -7728,12 +7728,20 @@ static int check_alu_op(struct bpf_verifier_env
>> *env, struct bpf_insn *insn)
>> insn->src_reg);
>> return -EACCES;
>> } else if (src_reg->type == SCALAR_VALUE) {
>> + /* If src_reg is in 32bit range,
>> there is
>> + * no need to reset the ID.
>> + */
>> + bool is_32bit_src =
>> src_reg->umax_value <= 0x7fffffff;
>> +
>> + if (is_32bit_src && !src_reg->id)
>> + src_reg->id = ++env->id_gen;
>> *dst_reg = *src_reg;
>> /* Make sure ID is cleared
>> otherwise
>> * dst_reg min/max could be
>> incorrectly
>> * propagated into src_reg by
>> find_equal_scalars()
>> */
>> - dst_reg->id = 0;
>> + if (!is_32bit_src)
>> + dst_reg->id = 0;
>> dst_reg->live |= REG_LIVE_WRITTEN;
>> dst_reg->subreg_def =
>> env->insn_idx + 1;
>> } else {
>>
>> Basically, for a 32bit mov insn like "w2 = w8", if we can ensure
>> that "w8" is 32bit and has no possibility that upper 32bit is set
>> for r8, we can declare them equivalent. This fixed your issue.
>>
>> Will try to submit a formal patch later.
>
> Ah.. I did not realise this equivalence tracking with reg.id was there
> for scalar values! I also didn't take any notice of the use of 32-bit
> operations in the assembly, thanks for pointing that out.
>
> Yes it sounds like this is certainly worth fixing in the kernel - even
> if Clang stops generating the code today it will probably start doing
> so again in the future. I can also help with the verifier work if
> needed.
I won't have time for this in the next few days.
Considering the current upstream merge window is close, yes, please
go head to work on this. Thanks!
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Help with verifier failure
2021-04-22 14:35 ` Yonghong Song
@ 2021-05-07 15:05 ` Brendan Jackman
2021-05-07 18:32 ` Yonghong Song
0 siblings, 1 reply; 8+ messages in thread
From: Brendan Jackman @ 2021-05-07 15:05 UTC (permalink / raw)
To: Yonghong Song
Cc: bpf, Alexei Starovoitov, Daniel Borkmann, Andrii Nakryiko, LKML
On Thu, 22 Apr 2021 at 16:35, Yonghong Song <yhs@fb.com> wrote:
>
>
>
> On 4/22/21 6:55 AM, Brendan Jackman wrote:
> > On Wed, 21 Apr 2021 at 18:59, Yonghong Song <yhs@fb.com> wrote:
> >> On 4/21/21 8:06 AM, Yonghong Song wrote:
> >>> On 4/21/21 5:23 AM, Brendan Jackman wrote:
> >>> Thanks, Brendan. Looks at least the verifier failure is triggered
> >>> by recent clang changes. I will take a look whether we could
> >>> improve verifier for such a case and whether we could improve
> >>> clang to avoid generate such codes the verifier doesn't like.
> >>> Will get back to you once I had concrete analysis.
> >>>
> >>>>
> >>>> This seems like it must be a common pitfall, any idea what we can do
> >>>> to fix it
> >>>> and avoid it in future? Am I misunderstanding the issue?
> >>
> >> First, for the example code you provided, I checked with llvm11, llvm12
> >> and latest trunk llvm (llvm13-dev) and they all generated similar codes,
> >> which may trigger verifier failure. Somehow you original code could be
> >> different may only show up with a recent llvm, I guess.
> >>
> >> Checking llvm IR, the divergence between "w2 = w8" and "if r8 < 0x1000"
> >> appears in insn scheduling phase related handling PHIs. Need to further
> >> check whether it is possible to prevent the compiler from generating
> >> such codes.
> >>
> >> The latest kernel already had the ability to track register equivalence.
> >> However, the tracking is conservative for 32bit mov like "w2 = w8" as
> >> you described in the above. if we have code like "r2 = r8; if r8 <
> >> 0x1000 ...", we will be all good.
> >>
> >> The following hack fixed the issue,
> >>
> >> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> >> index 58730872f7e5..54f418fd6a4a 100644
> >> --- a/kernel/bpf/verifier.c
> >> +++ b/kernel/bpf/verifier.c
> >> @@ -7728,12 +7728,20 @@ static int check_alu_op(struct bpf_verifier_env
> >> *env, struct bpf_insn *insn)
> >> insn->src_reg);
> >> return -EACCES;
> >> } else if (src_reg->type == SCALAR_VALUE) {
> >> + /* If src_reg is in 32bit range,
> >> there is
> >> + * no need to reset the ID.
> >> + */
> >> + bool is_32bit_src =
> >> src_reg->umax_value <= 0x7fffffff;
> >> +
> >> + if (is_32bit_src && !src_reg->id)
> >> + src_reg->id = ++env->id_gen;
> >> *dst_reg = *src_reg;
> >> /* Make sure ID is cleared
> >> otherwise
> >> * dst_reg min/max could be
> >> incorrectly
> >> * propagated into src_reg by
> >> find_equal_scalars()
> >> */
> >> - dst_reg->id = 0;
> >> + if (!is_32bit_src)
> >> + dst_reg->id = 0;
> >> dst_reg->live |= REG_LIVE_WRITTEN;
> >> dst_reg->subreg_def =
> >> env->insn_idx + 1;
> >> } else {
> >>
> >> Basically, for a 32bit mov insn like "w2 = w8", if we can ensure
> >> that "w8" is 32bit and has no possibility that upper 32bit is set
> >> for r8, we can declare them equivalent. This fixed your issue.
I just got around to looking into this - spent some time reading and
realised it's simpler than I thought :) I also double checked that it
fixes the test with my current Clang too.
Beyond cleaning up and putting it into a patch, did you have anything
in particular in mind when you called this a "hack"?
Do I understand correctly that in this code we only need to check
umax_value, because it anyway gets folded into the other bounds fields
during adjust_min_max_reg_vals?
It seems like the next rung on the "ladder" of solution completeness
here would be quite a big step up, something like a more comprehensive
representation of register relationships (instead of just "these regs
have the same value" vs. "these regs have no relationship"), which I
guess would be more extreme than necessary right now.
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Help with verifier failure
2021-05-07 15:05 ` Brendan Jackman
@ 2021-05-07 18:32 ` Yonghong Song
0 siblings, 0 replies; 8+ messages in thread
From: Yonghong Song @ 2021-05-07 18:32 UTC (permalink / raw)
To: Brendan Jackman
Cc: bpf, Alexei Starovoitov, Daniel Borkmann, Andrii Nakryiko, LKML
On 5/7/21 8:05 AM, Brendan Jackman wrote:
> On Thu, 22 Apr 2021 at 16:35, Yonghong Song <yhs@fb.com> wrote:
>>
>>
>>
>> On 4/22/21 6:55 AM, Brendan Jackman wrote:
>>> On Wed, 21 Apr 2021 at 18:59, Yonghong Song <yhs@fb.com> wrote:
>>>> On 4/21/21 8:06 AM, Yonghong Song wrote:
>>>>> On 4/21/21 5:23 AM, Brendan Jackman wrote:
>>>>> Thanks, Brendan. Looks at least the verifier failure is triggered
>>>>> by recent clang changes. I will take a look whether we could
>>>>> improve verifier for such a case and whether we could improve
>>>>> clang to avoid generate such codes the verifier doesn't like.
>>>>> Will get back to you once I had concrete analysis.
>>>>>
>>>>>>
>>>>>> This seems like it must be a common pitfall, any idea what we can do
>>>>>> to fix it
>>>>>> and avoid it in future? Am I misunderstanding the issue?
>>>>
>>>> First, for the example code you provided, I checked with llvm11, llvm12
>>>> and latest trunk llvm (llvm13-dev) and they all generated similar codes,
>>>> which may trigger verifier failure. Somehow you original code could be
>>>> different may only show up with a recent llvm, I guess.
>>>>
>>>> Checking llvm IR, the divergence between "w2 = w8" and "if r8 < 0x1000"
>>>> appears in insn scheduling phase related handling PHIs. Need to further
>>>> check whether it is possible to prevent the compiler from generating
>>>> such codes.
>>>>
>>>> The latest kernel already had the ability to track register equivalence.
>>>> However, the tracking is conservative for 32bit mov like "w2 = w8" as
>>>> you described in the above. if we have code like "r2 = r8; if r8 <
>>>> 0x1000 ...", we will be all good.
>>>>
>>>> The following hack fixed the issue,
>>>>
>>>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>>>> index 58730872f7e5..54f418fd6a4a 100644
>>>> --- a/kernel/bpf/verifier.c
>>>> +++ b/kernel/bpf/verifier.c
>>>> @@ -7728,12 +7728,20 @@ static int check_alu_op(struct bpf_verifier_env
>>>> *env, struct bpf_insn *insn)
>>>> insn->src_reg);
>>>> return -EACCES;
>>>> } else if (src_reg->type == SCALAR_VALUE) {
>>>> + /* If src_reg is in 32bit range,
>>>> there is
>>>> + * no need to reset the ID.
>>>> + */
>>>> + bool is_32bit_src =
>>>> src_reg->umax_value <= 0x7fffffff;
>>>> +
>>>> + if (is_32bit_src && !src_reg->id)
>>>> + src_reg->id = ++env->id_gen;
>>>> *dst_reg = *src_reg;
>>>> /* Make sure ID is cleared
>>>> otherwise
>>>> * dst_reg min/max could be
>>>> incorrectly
>>>> * propagated into src_reg by
>>>> find_equal_scalars()
>>>> */
>>>> - dst_reg->id = 0;
>>>> + if (!is_32bit_src)
>>>> + dst_reg->id = 0;
>>>> dst_reg->live |= REG_LIVE_WRITTEN;
>>>> dst_reg->subreg_def =
>>>> env->insn_idx + 1;
>>>> } else {
>>>>
>>>> Basically, for a 32bit mov insn like "w2 = w8", if we can ensure
>>>> that "w8" is 32bit and has no possibility that upper 32bit is set
>>>> for r8, we can declare them equivalent. This fixed your issue.
>
> I just got around to looking into this - spent some time reading and
> realised it's simpler than I thought :) I also double checked that it
> fixes the test with my current Clang too.
>
> Beyond cleaning up and putting it into a patch, did you have anything
> in particular in mind when you called this a "hack"?
>
> Do I understand correctly that in this code we only need to check
> umax_value, because it anyway gets folded into the other bounds fields
> during adjust_min_max_reg_vals?
If the umax_value is less than or equal to INT_MAX, if all *_value's are
consistent in the register state, yes, it will be sufficient to
declare the reg is indeed holding a 32bit value in a 64bit register.
I mentioned it as a "hack" as I did not go through all the reg
range refining before/after this piece of codes. Since you have
looked at it and it seems fine. I would suggest you can just
with my patch above plus your test and submit it to the mailing
list for review.
>
> It seems like the next rung on the "ladder" of solution completeness
> here would be quite a big step up, something like a more comprehensive
> representation of register relationships (instead of just "these regs
> have the same value" vs. "these regs have no relationship"), which I
> guess would be more extreme than necessary right now.
We have to weigh between verifier complexity and whether it is general
enough for compilation transformation. Yes, if you have such use cases,
please share and we can discuss how to address them.
^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2021-05-07 18:32 UTC | newest]
Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-04-21 12:23 Help with verifier failure Brendan Jackman
2021-04-21 15:06 ` Yonghong Song
2021-04-21 16:59 ` Yonghong Song
2021-04-22 13:55 ` Brendan Jackman
2021-04-22 14:35 ` Yonghong Song
2021-05-07 15:05 ` Brendan Jackman
2021-05-07 18:32 ` Yonghong Song
2021-04-21 16:41 ` John Fastabend
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).