Two more fixes for check_max_stack_depth
Subsystems (4)
Kumar Kartikeya Dwivedi
maintainercover Two more fixes for check_max_stack_depth
I noticed two more bugs while reviewing the code, description and examples available in the patches.
One leads to incorrect subprog index to be stored in the frame stack maintained by the function (leading to incorrect tail_call_reachable marks, among other things).
The other problem is missing exploration pass of other async callbacks when they are not called from the main prog. Call chains rooted at them can thus bypass the stack limits (32 call frames * max permitted stack depth per function).
Kumar Kartikeya Dwivedi (3):
bpf: Fix subprog idx logic in check_max_stack_depth
bpf: Repeat check_max_stack_depth for async callbacks selftests/bpf: Add more tests for check_max_stack_depth bug
kernel/bpf/verifier.c | 32 +++++++++++++++---- .../selftests/bpf/progs/async_stack_depth.c | 25 +++++++++++++-- 2 files changed, 48 insertions(+), 9 deletions(-)
base-commit: 2e06c57d66d3f6c26faa5f5b479fb3add34ce85a
Signature · 1 line
2.40.1
Kumar Kartikeya Dwivedi
maintainerPATCH 1/3 bpf: Fix subprog idx logic in check_max_stack_depth
The assignment to idx in check_max_stack_depth happens once we see a bpf_pseudo_call or bpf_pseudo_func. This is not an issue as the rest of the code performs a few checks and then pushes the frame to the frame stack, except the case of async callbacks. If the async callback case causes the loop iteration to be skipped, the idx assignment will be incorrect on the next iteration of the loop. The value stored in the frame stack (as the subprogno of the current subprog) will be incorrect.
This leads to incorrect checks and incorrect tail_call_reachable marking. Save the target subprog in a new variable and only assign to idx once we are done with the is_async_cb check which may skip pushing of frame to the frame stack and subsequent stack depth checks and tail call markings.
--- kernel/bpf/verifier.c | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-)
kernel/bpf/verifier.c +6 -5
@@ -5621,7 +5621,7 @@ static int check_max_stack_depth(struct bpf_verifier_env *env) continue_func: subprog_end = subprog[idx +1 ].start;for (; i < subprog_end; i++) { -int next_insn; +int next_insn, sidx;if (!bpf_pseudo_call (insn + i) && !bpf_pseudo_func (insn + i))continue ;
@@ -5631,14 +5631,14 @@ static int check_max_stack_depth(struct bpf_verifier_env *env)/* find the callee */ next_insn = i + insn[i].imm +1 ; - idx =find_subprog (env, next_insn); -if (idx <0 ) { + sidx =find_subprog (env, next_insn); +if (sidx <0 ) {WARN_ONCE (1 ,"verifier bug. No program starts at insn %d\n" , next_insn);return -EFAULT ; } -if (subprog[idx].is_async_cb) { -if (subprog[idx].has_tail_call) { +if (subprog[sidx].is_async_cb) { +if (subprog[sidx].has_tail_call) {verbose (env,"verifier bug. subprog has tail_call and async cb\n" );return -EFAULT ; }
@@ -5647,6 +5647,7 @@ static int check_max_stack_depth(struct bpf_verifier_env *env)continue ; } i = next_insn; + idx = sidx;if (subprog[idx].has_tail_call) tail_call_reachable = true;
Signature · 1 line
2.40.1
Kumar Kartikeya Dwivedi
maintainerPATCH 2/3 bpf: Repeat check_max_stack_depth for async callbacks
In reply to Kumar Kartikeya DwivediWhile the check_max_stack_depth function explores call chains emanating from the main prog, which is typically enough to cover all possible call chains, it doesn't explore those rooted at async callbacks unless the async callback will have been directly called, since unlike non-async callbacks it skips their instruction exploration as they don't contribute to stack depth.
It could be the case that the async callback leads to a callchain which exceeds the stack depth, but this is never reachable while only exploring the entry point from main subprog. Hence, repeat the check for the main subprog *and* all async callbacks marked by the symbolic execution pass of the verifier, as execution of the program may begin at any of them.
Consider a function with following stack depths:
main : 256
async : 256
foo: 256
main:
rX = async
bpf_timer_set_callback(...)
async:
foo()
Here, async is never seen to contribute to the stack depth of main, so it is not descended, but when async is invoked asynchronously when the timer fires, it will end up breaching MAX_BPF_STACK limit imposed by the verifier.
--- kernel/bpf/verifier.c | 21 +++++++++++++++++++-- 1 file changed, 19 insertions(+), 2 deletions(-)
kernel/bpf/verifier.c +19 -2
@@ -5573,16 +5573,17 @@ static int update_stack_depth(struct bpf_verifier_env *env,* Since recursion is prevented by check_cfg() this algorithm * only needs a local stack of MAX_CALL_FRAMES to remember callsites */ -static int check_max_stack_depth (struct bpf_verifier_env *env) +static int check_max_stack_depth_subprog (struct bpf_verifier_env *env,int idx) { -int depth =0 , frame =0 , idx =0 , i =0 , subprog_end;struct bpf_subprog_info *subprog = env->subprog_info;struct bpf_insn *insn = env->prog->insnsi; +int depth =0 , frame =0 , i, subprog_end;bool tail_call_reachable = false;int ret_insn[MAX_CALL_FRAMES ];int ret_prog[MAX_CALL_FRAMES ];int j; + i = subprog[idx].start; process_func:/* protect against potential stack overflow that might happen when * bpf2bpf calls get combined with tailcalls. Limit the caller's stack
@@ -5683,6 +5684,22 @@ static int check_max_stack_depth(struct bpf_verifier_env *env) goto continue_func; } +static int check_max_stack_depth (struct bpf_verifier_env *env) +{ +struct bpf_subprog_info *si = env->subprog_info; +int ret; + +for (int i =0 ; i < env->subprog_cnt; i++) { +if (!i || si[i].is_async_cb) { + ret =check_max_stack_depth_subprog (env, i); +if (ret <0 ) +return ret; + } +continue ; + } +return 0 ; +} +#ifndef CONFIG_BPF_JIT_ALWAYS_ON static int get_callee_stack_depth (struct bpf_verifier_env *env,const struct bpf_insn *insn,int idx)
Signature · 1 line
2.40.1
Re: [PATCH bpf v1 2/3] bpf: Repeat check_max_stack_depth for async callbacks
Quoted 23 lines · Kumar Kartikeya Dwivedi
While the
check_max_stack_depthfunction explores call chains emanating from the main prog, which is typically enough to cover all possible call chains, it doesn't explore those rooted at async callbacks unless the async callback will have been directly called, since unlike non-async callbacks it skips their instruction exploration as they don't contribute to stack depth.It could be the case that the async callback leads to a callchain which exceeds the stack depth, but this is never reachable while only exploring the entry point from main subprog. Hence, repeat the check for the main subprog *and* all async callbacks marked by the symbolic execution pass of the verifier, as execution of the program may begin at any of them.
Consider a function with following stack depths:
main : 256
async : 256
foo: 256main:
rX = async
bpf_timer_set_callback(...)
Quoted 7 lines
async:
foo()Here, async is never seen to contribute to the stack depth of main, so it is not descended, but when async is invoked asynchronously when the timer fires, it will end up breaching
MAX_BPF_STACKlimit imposed by the verifier.
The fix is correct, but the above paragraph is misleading. async doesn't and shouldn't contribute to the stack depth of main prog. Could you rephrase it?
Quoted 57 lines
Fixes 7ddc80a476c2 ("bpf: Teach stack depth check about async callbacks.")Signed-off-by Kumar Kartikeya Dwivedi <[email protected]>--- kernel/bpf/verifier.c | 21 +++++++++++++++++++-- 1 file changed, 19 insertions(+), 2 deletions(-)kernel/bpf/verifier.c +19
-2@@ -5573,16 +5573,17 @@ static int update_stack_depth(struct bpf_verifier_env *env,* Since recursion is prevented by check_cfg() this algorithm * only needs a local stack of MAX_CALL_FRAMES to remember callsites */ -static int check_max_stack_depth (struct bpf_verifier_env *env) +static int check_max_stack_depth_subprog (struct bpf_verifier_env *env,int idx) { -int depth =0 , frame =0 , idx =0 , i =0 , subprog_end;struct bpf_subprog_info *subprog = env->subprog_info;struct bpf_insn *insn = env->prog->insnsi; +int depth =0 , frame =0 , i, subprog_end;bool tail_call_reachable = false;int ret_insn[MAX_CALL_FRAMES ];int ret_prog[MAX_CALL_FRAMES ];int j; + i = subprog[idx].start; process_func:/* protect against potential stack overflow that might happen when * bpf2bpf calls get combined with tailcalls. Limit the caller's stack @@ -5683,6 +5684,22 @@ static int check_max_stack_depth(struct bpf_verifier_env *env) goto continue_func; } +static int check_max_stack_depth (struct bpf_verifier_env *env) +{ +struct bpf_subprog_info *si = env->subprog_info; +int ret; + +for (int i =0 ; i < env->subprog_cnt; i++) { +if (!i || si[i].is_async_cb) { + ret =check_max_stack_depth_subprog (env, i); +if (ret <0 ) +return ret; + } +continue ; + } +return 0 ; +} +#ifndef CONFIG_BPF_JIT_ALWAYS_ON static int get_callee_stack_depth (struct bpf_verifier_env *env,const struct bpf_insn *insn,int idx)Signature · 1 line
2.40.1
Kumar Kartikeya Dwivedi
maintainerRe: [PATCH bpf v1 2/3] bpf: Repeat check_max_stack_depth for async callbacks
Quoted 28 lines · Alexei Starovoitov
Quoted 26 lines · Kumar Kartikeya Dwivedi
While the
check_max_stack_depthfunction explores call chains emanating from the main prog, which is typically enough to cover all possible call chains, it doesn't explore those rooted at async callbacks unless the async callback will have been directly called, since unlike non-async callbacks it skips their instruction exploration as they don't contribute to stack depth.It could be the case that the async callback leads to a callchain which exceeds the stack depth, but this is never reachable while only exploring the entry point from main subprog. Hence, repeat the check for the main subprog *and* all async callbacks marked by the symbolic execution pass of the verifier, as execution of the program may begin at any of them.
Consider a function with following stack depths:
main : 256
async : 256
foo: 256main:
rX = async
bpf_timer_set_callback(...)async:
foo()
Quoted 9 lines
Quoted 4 lines
Here, async is never seen to contribute to the stack depth of main, so it is not descended, but when async is invoked asynchronously when the timer fires, it will end up breaching
MAX_BPF_STACKlimit imposed by the verifier.The fix is correct, but the above paragraph is misleading. async doesn't and shouldn't contribute to the stack depth of main prog. Could you rephrase it?
Agreed, I sent a v2 with a clearer commit message.
Kumar Kartikeya Dwivedi
maintainerPATCH 3/3 selftests/bpf: Add more tests for check_max_stack_depth bug
In reply to Kumar Kartikeya DwivediAnother test which now exercies the path of the verifier where it will explore call chains rooted at the async callback. Without the prior fixes, this program loads successfully, which is incorrect.
--- .../selftests/bpf/progs/async_stack_depth.c | 25 +++++++++++++++++-- 1 file changed, 23 insertions(+), 2 deletions(-)
tools/testing/selftests/bpf/progs/async_stack_depth.c +23 -2
@@ -22,9 +22,16 @@ static int timer_cb(void *map, int *key, struct bpf_timer *timer)return buf[69 ]; } +__attribute__((noinline)) +static int bad_timer_cb (void *map,int *key,struct bpf_timer *timer) +{ +volatile char buf[300 ] = {}; +return buf[255 ] +timer_cb (NULL ,NULL ,NULL ); +} + SEC("tc") -__failure __msg("combined stack size of 2 calls") -int prog(struct __sk_buff *ctx) +__failure __msg("combined stack size of 2 calls is 576. Too large") +int pseudo_call_check(struct __sk_buff *ctx) {struct hmap_elem *elem;volatile char buf[256 ] = {};
@@ -37,4 +44,18 @@ int prog(struct __sk_buff *ctx)return bpf_timer_set_callback (&elem->timer, timer_cb) + buf[0 ]; } +SEC("tc") +__failure __msg("combined stack size of 2 calls is 608. Too large") +int async_call_root_check(struct __sk_buff *ctx) +{ +struct hmap_elem *elem; +volatile char buf[256 ] = {}; + + elem =bpf_map_lookup_elem (&hmap, &(int ){0 }); +if (!elem) +return 0 ; + +return bpf_timer_set_callback (&elem->timer, bad_timer_cb) + buf[0 ]; +} + char _license[] SEC("license") = "GPL";
Signature · 1 line
2.40.1