bpf: Fix a kernel verifier crash in stacksafe()
Subsystems (4)
Yonghong Song
reviewerPATCH 1/2 bpf: Fix a kernel verifier crash in stacksafe()
Daniel Hodges reported a kernel verifier crash when playing with sched-ext. The crash dump looks like below:
[ 65.874474] BUG: kernel NULL pointer dereference, address: 0000000000000088
[ 65.888406] #PF: supervisor read access in kernel mode
[ 65.898682] #PF: error_code(0x0000) - not-present page
[ 65.908957] PGD 0 P4D 0
[ 65.914020] Oops: 0000 [#1] SMP
[ 65.920300] CPU: 19 PID: 9364 Comm: scx_layered Kdump: loaded Tainted: G S E 6.9.5-g93cea04637ea-dirty #7
[ 65.941874] Hardware name: Quanta Delta Lake MP 29F0EMA01D0/Delta Lake-Class1, BIOS F0E_3A19 04/27/2023
[ 65.960664] RIP: 0010:states_equal+0x3ee/0x770
[ 65.969559] Code: 33 85 ed 89 e8 41 0f 48 c7 83 e0 f8 89 e9 29 c1 48 63 c1 4c 89 e9 48 c1 e1 07 49 8d 14 08 0f
b6 54 10 78 49 03 8a 58 05 00 00 <3a> 54 08 78 0f 85 60 03 00 00 49 c1 e5 07 43 8b 44 28 70 83 e0 03
[ 66.007120] RSP: 0018:ffffc9000ebeb8b8 EFLAGS: 00010202
[ 66.017570] RAX: 0000000000000000 RBX: ffff888149719680 RCX: 0000000000000010
[ 66.031843] RDX: 0000000000000000 RSI: ffff88907f4e0c08 RDI: ffff8881572f0000
[ 66.046115] RBP: 0000000000000000 R08: ffff8883d5014000 R09: ffffffff83065d50
[ 66.060386] R10: ffff8881bf9a1800 R11: 0000000000000002 R12: 0000000000000000
[ 66.074659] R13: 0000000000000000 R14: ffff888149719a40 R15: 0000000000000007
[ 66.088932] FS: 00007f5d5da96800(0000) GS:ffff88907f4c0000(0000) knlGS:0000000000000000
[ 66.105114] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[ 66.116606] CR2: 0000000000000088 CR3: 0000000388261001 CR4: 00000000007706f0
[ 66.130873] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
[ 66.145145] DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400
[ 66.159416] PKRU: 55555554
[ 66.164823] Call Trace:
[ 66.169709] <TASK>
[ 66.173906] ? __die_body+0x66/0xb0
[ 66.180890] ? page_fault_oops+0x370/0x3d0
[ 66.189082] ? console_unlock+0xb5/0x140
[ 66.196926] ? exc_page_fault+0x4f/0xb0
[ 66.204597] ? asm_exc_page_fault+0x22/0x30
[ 66.212974] ? states_equal+0x3ee/0x770
[ 66.220643] ? states_equal+0x529/0x770
[ 66.228312] do_check+0x60f/0x5240
[ 66.235114] do_check_common+0x388/0x840
[ 66.242960] do_check_subprogs+0x101/0x150
[ 66.251150] bpf_check+0x5d5/0x4b60
[ 66.258134] ? __mod_memcg_state+0x79/0x110
[ 66.266506] ? pcpu_alloc+0x892/0xba0
[ 66.273829] bpf_prog_load+0x5bb/0x660
[ 66.281324] ? bpf_prog_bind_map+0x1e1/0x290
[ 66.289862] __sys_bpf+0x29d/0x3a0
[ 66.296664] __x64_sys_bpf+0x18/0x20
[ 66.303811] do_syscall_64+0x6a/0x140
[ 66.311133] entry_SYSCALL_64_after_hwframe+0x4b/0x53Forther investigation shows that the crash is due to invalid memory access in stacksafe(). More specifically, it is the following code:
if (exact != NOT_EXACT &&
old->stack[spi].slot_type[i % BPF_REG_SIZE] !=
cur->stack[spi].slot_type[i % BPF_REG_SIZE])
return false;If cur->allocated_stack is 0, cur->stack will be a ZERO_SIZE_PTR. If this happens, cur->stack[spi].slot_type[i % BPF_REG_SIZE] will crash the kernel as the memory address is illegal. This is exactly what happened in the above crash dump. If cur->allocated_stack is not 0, the above code could trigger array out-of-bound access.
The patch added a condition 'i < cur->allocated_stack' to ensure cur->stack[spi].slot_type[i % BPF_REG_SIZE] memory access always legal.
--- kernel/bpf/verifier.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/bpf/verifier.c +1 -1
@@ -16883,7 +16883,7 @@ static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old, spi = i /BPF_REG_SIZE ; -if (exact !=NOT_EXACT && +if (exact !=NOT_EXACT && i < cur->allocated_stack && old->stack[spi].slot_type[i %BPF_REG_SIZE ] != cur->stack[spi].slot_type[i %BPF_REG_SIZE ])return false;
Signature · 1 line
2.43.5
Yonghong Song
reviewerPATCH 2/2 selftests/bpf: Add a test to verify previous stacksafe() fix
A selftest is added such that without the previous patch, a crash can happen. With the previous patch, the test can run successfully. The new test is written in a way which mimics original crash case:
main_prog
static_prog_1
static_prog_2
where static_prog_1 has different paths to static_prog_2 and some path has stack allocated and some other path does not. A stacksafe() checking in static_prog_2() triggered the crash.
--- tools/testing/selftests/bpf/progs/iters.c | 54 +++++++++++++++++++++++ 1 file changed, 54 insertions(+)
tools/testing/selftests/bpf/progs/iters.c +54 -0
@@ -1432,4 +1432,58 @@ int iter_arr_with_actual_elem_count(const void *ctx)return sum; } +__u32 upper, select_n, result; +__u64 global; + +static __noinline bool nest_2(char *str, int len) +{ +/* some insns (including branch insns) to ensure stacksafe() is triggered +* in nest_2(). This way, stacksafe() can compare frame associated with nest_1(). +*/ +if (str[0 ] =='t' ) +return true; +if (str[1 ] =='e' ) +return true; +if (str[2 ] =='s' ) +return true; +if (str[3 ] =='t' ) +return true; +return false; +} + +static __noinline bool nest_1(int n) +{ +/* case 0: allocate stack, case 1: no allocate stack */ +switch (n) { +case 0 : { +char comm[16 ]; + +if (bpf_get_current_comm (comm,16 )) +return false; +return nest_2 (comm,16 ); + } +case 1 : +return nest_2 ((char *)&global,sizeof (global)); +default : +return false; + } +} + +SEC("raw_tp") +__success +int iter_subprog_check_stacksafe (const void *ctx) +{ +long i; + + bpf_for(i, 0, upper) { +if (!nest_1 (select_n)) { + result =1 ; +return 0 ; + } + } + + result =2 ; +return 0 ; +} + char _license[] SEC("license") = "GPL";
Signature · 1 line
2.43.5
Yonghong Song
reviewerRe: [PATCH bpf 2/2] selftests/bpf: Add a test to verify previous stacksafe() fix
Quoted 22 lines · Yonghong Song
A selftest is added such that without the previous patch, a crash can happen. With the previous patch, the test can run successfully. The new test is written in a way which mimics original crash case:
main_prog
static_prog_1
static_prog_2
wherestatic_prog_1has different paths tostatic_prog_2and some path has stack allocated and some other path does not. Astacksafe()checking instatic_prog_2()triggered the crash.Signed-off-by Yonghong Song <[email protected]>--- tools/testing/selftests/bpf/progs/iters.c | 54 +++++++++++++++++++++++ 1 file changed, 54 insertions(+)tools/testing/selftests/bpf/progs/iters.c +0
-0
tools/testing/selftests/bpf/progs/iters.c int iter_arr_with_actual_elem_count(const void *ctx) · line 1438
Quoted 7 lines
tools/testing/selftests/bpf/progs/iters.c +4
-0@@ -1432,4 +1432,58 @@ int iter_arr_with_actual_elem_count(const void *ctx)return sum; } +__u32 upper, select_n, result; +__u64 global; + +static __noinline bool nest_2(char *str, int len)
Argument 'len' is not needed here. I can make the change after some additional comments.
Quoted 21 lines
tools/testing/selftests/bpf/progs/iters.c +21
-0+{ +/* some insns (including branch insns) to ensure stacksafe() is triggered +* in nest_2(). This way, stacksafe() can compare frame associated with nest_1(). +*/ +if (str[0 ] =='t' ) +return true; +if (str[1 ] =='e' ) +return true; +if (str[2 ] =='s' ) +return true; +if (str[3 ] =='t' ) +return true; +return false; +} + +static __noinline bool nest_1(int n) +{ +/* case 0: allocate stack, case 1: no allocate stack */ +switch (n) { +case 0 : { +char comm[16 ];
tools/testing/selftests/bpf/progs/iters.c int iter_arr_with_actual_elem_count(const void *ctx) · line 1469
Quoted 10 lines
tools/testing/selftests/bpf/progs/iters.c +10
-0+ +if (bpf_get_current_comm (comm,16 )) +return false; +return nest_2 (comm,16 ); + } +case 1 : +return nest_2 ((char *)&global,sizeof (global)); +default : +return false; + }
To triger the failure, we rely on 'case 0' is explored by the verifier first and 'case 1' is explored later. This seems the case for llvm18 and llvm20.
Quoted 20 lines
tools/testing/selftests/bpf/progs/iters.c +19
-0+} + +SEC("raw_tp") +__success +int iter_subprog_check_stacksafe (const void *ctx) +{ +long i; + + bpf_for(i, 0, upper) { +if (!nest_1 (select_n)) { + result =1 ; +return 0 ; + } + } + + result =2 ; +return 0 ; +} + char _license[] SEC("license") = "GPL";
Quoted 61 lines · Yonghong Song
Daniel Hodges reported a kernel verifier crash when playing with sched-ext. The crash dump looks like below:
[ 65.874474] BUG: kernel NULL pointer dereference, address: 0000000000000088 [ 65.888406] #PF: supervisor read access in kernel mode [ 65.898682] #PF: error_code(0x0000) - not-present page [ 65.908957] PGD 0 P4D 0 [ 65.914020] Oops: 0000 [#1] SMP [ 65.920300] CPU: 19 PID: 9364 Comm: scx_layered Kdump: loaded Tainted: G S E 6.9.5-g93cea04637ea-dirty #7 [ 65.941874] Hardware name: Quanta Delta Lake MP 29F0EMA01D0/Delta Lake-Class1, BIOS F0E_3A19 04/27/2023 [ 65.960664] RIP: 0010:states_equal+0x3ee/0x770 [ 65.969559] Code: 33 85 ed 89 e8 41 0f 48 c7 83 e0 f8 89 e9 29 c1 48 63 c1 4c 89 e9 48 c1 e1 07 49 8d 14 08 0f b6 54 10 78 49 03 8a 58 05 00 00 <3a> 54 08 78 0f 85 60 03 00 00 49 c1 e5 07 43 8b 44 28 70 83 e0 03 [ 66.007120] RSP: 0018:ffffc9000ebeb8b8 EFLAGS: 00010202 [ 66.017570] RAX: 0000000000000000 RBX: ffff888149719680 RCX: 0000000000000010 [ 66.031843] RDX: 0000000000000000 RSI: ffff88907f4e0c08 RDI: ffff8881572f0000 [ 66.046115] RBP: 0000000000000000 R08: ffff8883d5014000 R09: ffffffff83065d50 [ 66.060386] R10: ffff8881bf9a1800 R11: 0000000000000002 R12: 0000000000000000 [ 66.074659] R13: 0000000000000000 R14: ffff888149719a40 R15: 0000000000000007 [ 66.088932] FS: 00007f5d5da96800(0000) GS:ffff88907f4c0000(0000) knlGS:0000000000000000 [ 66.105114] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033 [ 66.116606] CR2: 0000000000000088 CR3: 0000000388261001 CR4: 00000000007706f0 [ 66.130873] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000 [ 66.145145] DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400 [ 66.159416] PKRU: 55555554 [ 66.164823] Call Trace: [ 66.169709] <TASK> [ 66.173906] ? __die_body+0x66/0xb0 [ 66.180890] ? page_fault_oops+0x370/0x3d0 [ 66.189082] ? console_unlock+0xb5/0x140 [ 66.196926] ? exc_page_fault+0x4f/0xb0 [ 66.204597] ? asm_exc_page_fault+0x22/0x30 [ 66.212974] ? states_equal+0x3ee/0x770 [ 66.220643] ? states_equal+0x529/0x770 [ 66.228312] do_check+0x60f/0x5240 [ 66.235114] do_check_common+0x388/0x840 [ 66.242960] do_check_subprogs+0x101/0x150 [ 66.251150] bpf_check+0x5d5/0x4b60 [ 66.258134] ? __mod_memcg_state+0x79/0x110 [ 66.266506] ? pcpu_alloc+0x892/0xba0 [ 66.273829] bpf_prog_load+0x5bb/0x660 [ 66.281324] ? bpf_prog_bind_map+0x1e1/0x290 [ 66.289862] __sys_bpf+0x29d/0x3a0 [ 66.296664] __x64_sys_bpf+0x18/0x20 [ 66.303811] do_syscall_64+0x6a/0x140 [ 66.311133] entry_SYSCALL_64_after_hwframe+0x4b/0x53Forther investigation shows that the crash is due to invalid memory access in
stacksafe(). More specifically, it is the following code:if (exact != NOT_EXACT && old->stack[spi].slot_type[i % BPF_REG_SIZE] != cur->stack[spi].slot_type[i % BPF_REG_SIZE]) return false;If
cur->allocated_stackis 0,cur->stackwill be aZERO_SIZE_PTR. If this happens, cur->stack[spi].slot_type[i %BPF_REG_SIZE] will crash the kernel as the memory address is illegal. This is exactly what happened in the above crash dump. Ifcur->allocated_stackis not 0, the above code could trigger array out-of-bound access.
Quoted 8 lines
The patch added a condition 'i <
cur->allocated_stack' to ensure cur->stack[spi].slot_type[i %BPF_REG_SIZE] memory access always legal.Fixes 2793a8b015f7 ("bpf: exact states comparison for iterator convergence checks")Cc Eduard Zingerman <[email protected]>Reported-by Daniel Hodges <[email protected]>Signed-off-by Yonghong Song <[email protected]>---
My bad, for some reason I thought that 'if (i >= cur->allocated_stack) return false;' check below would be sufficient. (Which is obviously not true, sigh...).
[...]
Quoted 72 lines · Eduard Zingerman
Quoted 61 lines · Yonghong Song
Daniel Hodges reported a kernel verifier crash when playing with sched-ext. The crash dump looks like below:
[ 65.874474] BUG: kernel NULL pointer dereference, address: 0000000000000088 [ 65.888406] #PF: supervisor read access in kernel mode [ 65.898682] #PF: error_code(0x0000) - not-present page [ 65.908957] PGD 0 P4D 0 [ 65.914020] Oops: 0000 [#1] SMP [ 65.920300] CPU: 19 PID: 9364 Comm: scx_layered Kdump: loaded Tainted: G S E 6.9.5-g93cea04637ea-dirty #7 [ 65.941874] Hardware name: Quanta Delta Lake MP 29F0EMA01D0/Delta Lake-Class1, BIOS F0E_3A19 04/27/2023 [ 65.960664] RIP: 0010:states_equal+0x3ee/0x770 [ 65.969559] Code: 33 85 ed 89 e8 41 0f 48 c7 83 e0 f8 89 e9 29 c1 48 63 c1 4c 89 e9 48 c1 e1 07 49 8d 14 08 0f b6 54 10 78 49 03 8a 58 05 00 00 <3a> 54 08 78 0f 85 60 03 00 00 49 c1 e5 07 43 8b 44 28 70 83 e0 03 [ 66.007120] RSP: 0018:ffffc9000ebeb8b8 EFLAGS: 00010202 [ 66.017570] RAX: 0000000000000000 RBX: ffff888149719680 RCX: 0000000000000010 [ 66.031843] RDX: 0000000000000000 RSI: ffff88907f4e0c08 RDI: ffff8881572f0000 [ 66.046115] RBP: 0000000000000000 R08: ffff8883d5014000 R09: ffffffff83065d50 [ 66.060386] R10: ffff8881bf9a1800 R11: 0000000000000002 R12: 0000000000000000 [ 66.074659] R13: 0000000000000000 R14: ffff888149719a40 R15: 0000000000000007 [ 66.088932] FS: 00007f5d5da96800(0000) GS:ffff88907f4c0000(0000) knlGS:0000000000000000 [ 66.105114] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033 [ 66.116606] CR2: 0000000000000088 CR3: 0000000388261001 CR4: 00000000007706f0 [ 66.130873] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000 [ 66.145145] DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400 [ 66.159416] PKRU: 55555554 [ 66.164823] Call Trace: [ 66.169709] <TASK> [ 66.173906] ? __die_body+0x66/0xb0 [ 66.180890] ? page_fault_oops+0x370/0x3d0 [ 66.189082] ? console_unlock+0xb5/0x140 [ 66.196926] ? exc_page_fault+0x4f/0xb0 [ 66.204597] ? asm_exc_page_fault+0x22/0x30 [ 66.212974] ? states_equal+0x3ee/0x770 [ 66.220643] ? states_equal+0x529/0x770 [ 66.228312] do_check+0x60f/0x5240 [ 66.235114] do_check_common+0x388/0x840 [ 66.242960] do_check_subprogs+0x101/0x150 [ 66.251150] bpf_check+0x5d5/0x4b60 [ 66.258134] ? __mod_memcg_state+0x79/0x110 [ 66.266506] ? pcpu_alloc+0x892/0xba0 [ 66.273829] bpf_prog_load+0x5bb/0x660 [ 66.281324] ? bpf_prog_bind_map+0x1e1/0x290 [ 66.289862] __sys_bpf+0x29d/0x3a0 [ 66.296664] __x64_sys_bpf+0x18/0x20 [ 66.303811] do_syscall_64+0x6a/0x140 [ 66.311133] entry_SYSCALL_64_after_hwframe+0x4b/0x53Forther investigation shows that the crash is due to invalid memory access in
stacksafe(). More specifically, it is the following code:if (exact != NOT_EXACT && old->stack[spi].slot_type[i % BPF_REG_SIZE] != cur->stack[spi].slot_type[i % BPF_REG_SIZE]) return false;If
cur->allocated_stackis 0,cur->stackwill be aZERO_SIZE_PTR. If this happens, cur->stack[spi].slot_type[i %BPF_REG_SIZE] will crash the kernel as the memory address is illegal. This is exactly what happened in the above crash dump. Ifcur->allocated_stackis not 0, the above code could trigger array out-of-bound access.Quoted 8 lines
The patch added a condition 'i <
cur->allocated_stack' to ensure cur->stack[spi].slot_type[i %BPF_REG_SIZE] memory access always legal.Fixes 2793a8b015f7 ("bpf: exact states comparison for iterator convergence checks")Cc Eduard Zingerman <[email protected]>Reported-by Daniel Hodges <[email protected]>Signed-off-by Yonghong Song <[email protected]>---
Quoted 4 lines
My bad, for some reason I thought that 'if (i >=
cur->allocated_stack) return false;' check below would be sufficient. (Which is obviously not true, sigh...).Acked-by Eduard Zingerman <[email protected]>
Should we move the check up instead?
if (i >= cur->allocated_stack)
return false;
Checking it twice looks odd.
Eduard Zingerman
maintainerOn Mon, 2024-08-12 at 10:44 -0700, Alexei Starovoitov wrote:
[...]
Quoted 6 lines
Should we move the check up instead?
if (i >=
cur->allocated_stack)return false;Checking it twice looks odd.
A few checks before that, namely:
if (!(old->stack[spi].spilled_ptr.live & REG_LIVE_READ)
&& exact == NOT_EXACT) {
i += BPF_REG_SIZE - 1;
/* explored state didn't use this */
continue;
}
if (old->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_INVALID)
continue;
if (env->allow_uninit_stack &&
old->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_MISC)
continue;Should be done regardless cur->allocated_stack.
Quoted 28 lines · Eduard Zingerman
On Mon, 2024-08-12 at 10:44 -0700, Alexei Starovoitov wrote:
[...]
Quoted 6 lines
Should we move the check up instead?
if (i >=
cur->allocated_stack)return false;Checking it twice looks odd.
A few checks before that, namely:
if (!(old->stack[spi].spilled_ptr.live & REG_LIVE_READ) && exact == NOT_EXACT) { i += BPF_REG_SIZE - 1; /* explored state didn't use this */ continue; } if (old->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_INVALID) continue; if (env->allow_uninit_stack && old->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_MISC) continue;
Quoted 1 line
Should be done regardless
cur->allocated_stack.
Right, but then let's sink old->slot_type != cur->slot_type down?
Eduard Zingerman
maintainerQuoted 25 lines · Alexei Starovoitov
Quoted 24 lines · Eduard Zingerman
On Mon, 2024-08-12 at 10:44 -0700, Alexei Starovoitov wrote:
[...]
Quoted 6 lines
Should we move the check up instead?
if (i >=
cur->allocated_stack)return false;Checking it twice looks odd.
A few checks before that, namely:
if (!(old->stack[spi].spilled_ptr.live & REG_LIVE_READ) && exact == NOT_EXACT) { i += BPF_REG_SIZE - 1; /* explored state didn't use this */ continue; } if (old->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_INVALID) continue;
Quoted 7 lines
Quoted 5 lines
if (env->allow_uninit_stack && old->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_MISC) continue;Should be done regardless
cur->allocated_stack.Right, but then let's sink
old->slot_type!=cur->slot_typedown?
It does not seem correct to swap the order for these two checks:
if (exact != NOT_EXACT && i < cur->allocated_stack &&
old->stack[spi].slot_type[i % BPF_REG_SIZE] !=
cur->stack[spi].slot_type[i % BPF_REG_SIZE])
return false;
if (!(old->stack[spi].spilled_ptr.live & REG_LIVE_READ)
&& exact == NOT_EXACT) {
i += BPF_REG_SIZE - 1;
/* explored state didn't use this */
continue;
}if we do, 'slot_type' won't be checked for 'cur' when 'old' register is not marked live.
Quoted 49 lines · Eduard Zingerman
Quoted 25 lines · Alexei Starovoitov
Quoted 24 lines · Eduard Zingerman
On Mon, 2024-08-12 at 10:44 -0700, Alexei Starovoitov wrote:
[...]
Quoted 6 lines
Should we move the check up instead?
if (i >=
cur->allocated_stack)return false;Checking it twice looks odd.
A few checks before that, namely:
if (!(old->stack[spi].spilled_ptr.live & REG_LIVE_READ) && exact == NOT_EXACT) { i += BPF_REG_SIZE - 1; /* explored state didn't use this */ continue; } if (old->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_INVALID) continue;Quoted 7 lines
Quoted 5 lines
if (env->allow_uninit_stack && old->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_MISC) continue;Should be done regardless
cur->allocated_stack.Right, but then let's sink
old->slot_type!=cur->slot_typedown?It does not seem correct to swap the order for these two checks:
if (exact != NOT_EXACT && i < cur->allocated_stack && old->stack[spi].slot_type[i % BPF_REG_SIZE] != cur->stack[spi].slot_type[i % BPF_REG_SIZE]) return false; if (!(old->stack[spi].spilled_ptr.live & REG_LIVE_READ) && exact == NOT_EXACT) { i += BPF_REG_SIZE - 1; /* explored state didn't use this */ continue; }
Quoted 1 line
if we do, '
slot_type' won't be checked for 'cur' when 'old' register is not marked live.
I see. This is to compare states in open coded iter loops when liveness is not propagated yet, right?
Then when comparing for exact states we should probably do:
if (exact != NOT_EXACT &&
(i >= cur->allocated_stack ||
old->stack[spi].slot_type[i % BPF_REG_SIZE] !=
cur->stack[spi].slot_type[i % BPF_REG_SIZE]))return false;
?
Eduard Zingerman
maintainerOn Mon, 2024-08-12 at 12:29 -0700, Alexei Starovoitov wrote:
[...]
Quoted 14 lines
Quoted 14 lines
It does not seem correct to swap the order for these two checks:
if (exact != NOT_EXACT && i < cur->allocated_stack && old->stack[spi].slot_type[i % BPF_REG_SIZE] != cur->stack[spi].slot_type[i % BPF_REG_SIZE]) return false; if (!(old->stack[spi].spilled_ptr.live & REG_LIVE_READ) && exact == NOT_EXACT) { i += BPF_REG_SIZE - 1; /* explored state didn't use this */ continue; }
Quoted 4 lines
Quoted 1 line
if we do, '
slot_type' won't be checked for 'cur' when 'old' register is not marked live.I see. This is to compare states in open coded iter loops when liveness is not propagated yet, right?
Yes
Quoted 9 lines
Then when comparing for exact states we should probably do:
if (exact !=NOT_EXACT&&(i >= cur->allocated_stack || old->stack[spi].slot_type[i % BPF_REG_SIZE] != cur->stack[spi].slot_type[i % BPF_REG_SIZE]))return false;
?
Hm, right, otherwise the old slots in the interval [cur->allocated_stack..old->allocated_stack) won't be checked using exact rules.
Yonghong Song
reviewerQuoted 30 lines · Eduard Zingerman
On Mon, 2024-08-12 at 12:29 -0700, Alexei Starovoitov wrote:
[...]
Quoted 14 lines
Quoted 14 lines
It does not seem correct to swap the order for these two checks:
if (exact != NOT_EXACT && i < cur->allocated_stack && old->stack[spi].slot_type[i % BPF_REG_SIZE] != cur->stack[spi].slot_type[i % BPF_REG_SIZE]) return false; if (!(old->stack[spi].spilled_ptr.live & REG_LIVE_READ) && exact == NOT_EXACT) { i += BPF_REG_SIZE - 1; /* explored state didn't use this */ continue; }Quoted 3 lines
Quoted 1 line
if we do, '
slot_type' won't be checked for 'cur' when 'old' register is not marked live.I see. This is to compare states in open coded iter loops when liveness is not propagated yet, right?
Yes
Quoted 7 lines
Then when comparing for exact states we should probably do:
if (exact !=NOT_EXACT&&(i >= cur->allocated_stack || old->stack[spi].slot_type[i % BPF_REG_SIZE] != cur->stack[spi].slot_type[i % BPF_REG_SIZE])) return false;
Quoted 4 lines
Quoted 1 line
?
Hm, right, otherwise the old slots in the interval [cur->allocated_stack..old->allocated_stack) won't be checked using exact rules.
Okay, for *exact* stack slot_type comparison. Will make the change and send v2 soon.
Yonghong Song
reviewerQuoted 23 lines · Alexei Starovoitov
Quoted 22 lines · Eduard Zingerman
On Mon, 2024-08-12 at 10:44 -0700, Alexei Starovoitov wrote:
[...]
Quoted 6 lines
Should we move the check up instead?
if (i >=
cur->allocated_stack)return false;Checking it twice looks odd.
A few checks before that, namely:
if (!(old->stack[spi].spilled_ptr.live & REG_LIVE_READ) && exact == NOT_EXACT) { i += BPF_REG_SIZE - 1; /* explored state didn't use this */ continue; } if (old->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_INVALID) continue;
Quoted 6 lines
Quoted 5 lines
if (env->allow_uninit_stack && old->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_MISC) continue;Should be done regardless
cur->allocated_stack.Right, but then let's sink
old->slot_type!=cur->slot_typedown?
We could do the following to avoid double comparison: diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index df3be12096cf..1906798f1a3d 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -17338,10 +17338,13 @@ static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old, */ for (i = 0; i < old->allocated_stack; i++) { struct bpf_reg_state *old_reg, *cur_reg; + bool cur_exceed_bound; spi = i / BPF_REG_SIZE; - if (exact != NOT_EXACT && + cur_exceed_bound = i >= cur->allocated_stack; + + if (exact != NOT_EXACT && !cur_exceed_bound && old->stack[spi].slot_type[i % BPF_REG_SIZE] != cur->stack[spi].slot_type[i % BPF_REG_SIZE]) return false; @@ -17363,7 +17366,7 @@ static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old, /* explored stack has more populated slots than current stack * and these slots were used */ - if (i >= cur->allocated_stack) + if (cur_exceed_bound) return false; /* 64-bit scalar spill vs all slots MISC and vice versa. WDYT?
Eduard Zingerman
maintainerOn Mon, 2024-08-12 at 11:26 -0700, Yonghong Song wrote:
[...]
Quoted 18 lines
We could do the following to avoid double comparison: diff --git
a/kernel/bpf/verifier.cb/kernel/bpf/verifier.cindexdf3be12096cf..1906798f1a3d100644 ---a/kernel/bpf/verifier.c+++b/kernel/bpf/verifier.c@@ -17338,10 +17338,13 @@ static bool stacksafe(structbpf_verifier_env*env, structbpf_func_state*old, */ for (i = 0; i <old->allocated_stack; i++) { structbpf_reg_state*old_reg,*cur_reg; + boolcur_exceed_bound; spi = i /BPF_REG_SIZE; - if (exact !=NOT_EXACT&& +cur_exceed_bound= i >=cur->allocated_stack; + + if (exact !=NOT_EXACT&& !cur_exceed_bound && old->stack[spi].slot_type[i %BPF_REG_SIZE] != cur->stack[spi].slot_type[i %BPF_REG_SIZE]) return false; @@ -17363,7 +17366,7 @@ static bool stacksafe(structbpf_verifier_env*env, structbpf_func_state*old, /* explored stack has more populated slots than current stack * and these slots were used */ - if (i >=cur->allocated_stack) + if (cur_exceed_bound) return false; /* 64-bit scalar spill vs all slots MISC and vice versa. WDYT?
Yonghong, something went wrong with formatting of the above email, could you please resend?
Yonghong Song
reviewerQuoted 21 lines · Eduard Zingerman
On Mon, 2024-08-12 at 11:26 -0700, Yonghong Song wrote:
[...]
Quoted 8 lines
We could do the following to avoid double comparison: diff --git
a/kernel/bpf/verifier.cb/kernel/bpf/verifier.cindexdf3be12096cf..1906798f1a3d100644 ---a/kernel/bpf/verifier.c+++b/kernel/bpf/verifier.c@@ -17338,10 +17338,13 @@ static bool stacksafe(structbpf_verifier_env*env, structbpf_func_state*old, */ for (i = 0; i <old->allocated_stack; i++) { structbpf_reg_state*old_reg,*cur_reg; + boolcur_exceed_bound; spi = i /BPF_REG_SIZE; - if (exact !=NOT_EXACT&& +cur_exceed_bound= i >=Quoted 9 lines
cur->allocated_stack; + + if (exact !=NOT_EXACT&& !cur_exceed_bound && old->stack[spi].slot_type[i %BPF_REG_SIZE] != cur->stack[spi].slot_type[i %BPF_REG_SIZE]) return false; @@ -17363,7 +17366,7 @@ static bool stacksafe(structbpf_verifier_env*env, structbpf_func_state*old, /* explored stack has more populated slots than current stack * and these slots were used */ - if (i >=cur->allocated_stack) + if (cur_exceed_bound) return false; /* 64-bit scalar spill vs all slots MISC and vice versa. WDYT?
Quoted 2 lines
Yonghong, something went wrong with formatting of the above email, could you please resend?
Sorry, I copy-paste from 'git diff' result to my email window. Not sure why it caused the format issue after I sent out. Anyway, the following is the patch I suggested:
kernel/bpf/verifier.c +5 -2
@@ -17338,10 +17338,13 @@ static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,*/ for (i =0 ; i < old->allocated_stack; i++) {struct bpf_reg_state *old_reg, *cur_reg; +bool cur_exceed_bound; spi = i /BPF_REG_SIZE ; -if (exact !=NOT_EXACT && + cur_exceed_bound = i >= cur->allocated_stack; + +if (exact !=NOT_EXACT && !cur_exceed_bound && old->stack[spi].slot_type[i %BPF_REG_SIZE ] != cur->stack[spi].slot_type[i %BPF_REG_SIZE ])return false;
@@ -17363,7 +17366,7 @@ static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,/* explored stack has more populated slots than current stack * and these slots were used */ -if (i >= cur->allocated_stack) +if (cur_exceed_bound)return false;/* 64-bit scalar spill vs all slots MISC and vice versa.
Eduard Zingerman
maintainerOn Mon, 2024-08-12 at 11:36 -0700, Yonghong Song wrote:
[...]
Quoted 2 lines
Sorry, I copy-paste from 'git diff' result to my email window. Not sure why it caused the format issue after I sent out.
Sure, no problem
Quoted 7 lines
Anyway, the following is the patch I suggested:
kernel/bpf/verifier.c +0
-0
kernel/bpf/verifier.c static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old, · line 17345
Quoted 9 lines
kernel/bpf/verifier.c +2
-1@@ -17338,10 +17338,13 @@ static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,*/ for (i =0 ; i < old->allocated_stack; i++) {struct bpf_reg_state *old_reg, *cur_reg; +bool cur_exceed_bound; spi = i /BPF_REG_SIZE ; - if (exact != NOT_EXACT && + cur_exceed_bound = i >= cur->allocated_stack;
idk, I think C compiler would do this anyways,
to me the code is fine both with and without this additional variable.
Quoted 15 lines
kernel/bpf/verifier.c +3
-1+ +if (exact !=NOT_EXACT && !cur_exceed_bound && old->stack[spi].slot_type[i %BPF_REG_SIZE ] != cur->stack[spi].slot_type[i %BPF_REG_SIZE ])return false;@@ -17363,7 +17366,7 @@ static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,/* explored stack has more populated slots than current stack * and these slots were used */ -if (i >= cur->allocated_stack) +if (cur_exceed_bound)return false;/* 64-bit scalar spill vs all slots MISC and vice versa.
Yonghong Song
reviewerQuoted 20 lines · Eduard Zingerman
On Mon, 2024-08-12 at 11:36 -0700, Yonghong Song wrote:
[...]
Quoted 2 lines
Sorry, I copy-paste from 'git diff' result to my email window. Not sure why it caused the format issue after I sent out.
Sure, no problem
Quoted 12 lines
Anyway, the following is the patch I suggested:
kernel/bpf/verifier.c +1
-0@@ -17338,10 +17338,13 @@ static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,*/ for (i =0 ; i < old->allocated_stack; i++) {struct bpf_reg_state *old_reg, *cur_reg; +bool cur_exceed_bound;
Quoted 6 lines
kernel/bpf/verifier.c static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old, · line 17345
Quoted 4 lines
kernel/bpf/verifier.c +1
-1spi = i /BPF_REG_SIZE ; - if (exact != NOT_EXACT && + cur_exceed_bound = i >= cur->allocated_stack;idk, I think C compiler would do this anyways,
to me the code is fine both with and without this additional variable.
Okay, I will keep the original (simpler) patch then.
Quoted 17 lines
Quoted 16 lines
kernel/bpf/verifier.c +3
-1+ +if (exact !=NOT_EXACT && !cur_exceed_bound && old->stack[spi].slot_type[i %BPF_REG_SIZE ] != cur->stack[spi].slot_type[i %BPF_REG_SIZE ])return false;@@ -17363,7 +17366,7 @@ static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,/* explored stack has more populated slots than current stack * and these slots were used */ -if (i >= cur->allocated_stack) +if (cur_exceed_bound)return false;/* 64-bit scalar spill vs all slots MISC and vice versa.