| Message ID | 20230713003118.1327943-3-memxor@gmail.com (mailing list archive) |
|---|---|
| State | Superseded |
| Delegated to: | BPF |
| Headers | show |
| Series | Two more fixes for check_max_stack_depth | expand |
On Thu, Jul 13, 2023 at 06:01:17AM +0530, Kumar Kartikeya Dwivedi wrote: > While 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. 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? > > Fixes: 7ddc80a476c2 ("bpf: Teach stack depth check about async callbacks.") > Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com> > --- > kernel/bpf/verifier.c | 21 +++++++++++++++++++-- > 1 file changed, 19 insertions(+), 2 deletions(-) > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > index e682056dd144..02a021c524ab 100644 > --- a/kernel/bpf/verifier.c > +++ b/kernel/bpf/verifier.c > @@ -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) > -- > 2.40.1 >
On Sat, 15 Jul 2023 at 03:18, Alexei Starovoitov <alexei.starovoitov@gmail.com> wrote: > > On Thu, Jul 13, 2023 at 06:01:17AM +0530, Kumar Kartikeya Dwivedi wrote: > > While 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. > > 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.
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index e682056dd144..02a021c524ab 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -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)
While 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. Fixes: 7ddc80a476c2 ("bpf: Teach stack depth check about async callbacks.") Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com> --- kernel/bpf/verifier.c | 21 +++++++++++++++++++-- 1 file changed, 19 insertions(+), 2 deletions(-)