diff mbox series

[bpf,v1,2/3] bpf: Repeat check_max_stack_depth for async callbacks

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

Checks

Context Check Description
bpf/vmtest-bpf-PR success PR summary
netdev/series_format success Posting correctly formatted
netdev/tree_selection success Clearly marked for bpf
netdev/fixes_present success Fixes tag present in non-next series
netdev/header_inline success No static functions without inline keyword in header files
netdev/build_32bit success Errors and warnings before: 1353 this patch: 1353
netdev/cc_maintainers fail 1 blamed authors not CCed: toke@redhat.com; 8 maintainers not CCed: yhs@fb.com kpsingh@kernel.org john.fastabend@gmail.com song@kernel.org sdf@google.com jolsa@kernel.org haoluo@google.com toke@redhat.com
netdev/build_clang success Errors and warnings before: 1364 this patch: 1364
netdev/verify_signedoff success Signed-off-by tag matches author and committer
netdev/deprecated_api success None detected
netdev/check_selftest success No net selftest shell script
netdev/verify_fixes success Fixes tag looks correct
netdev/build_allmodconfig_warn success Errors and warnings before: 1376 this patch: 1376
netdev/checkpatch success total: 0 errors, 0 warnings, 0 checks, 41 lines checked
netdev/kdoc success Errors and warnings before: 0 this patch: 0
netdev/source_inline success Was 0 now: 0
bpf/vmtest-bpf-VM_Test-1 success Logs for ShellCheck
bpf/vmtest-bpf-VM_Test-6 success Logs for set-matrix
bpf/vmtest-bpf-VM_Test-2 success Logs for build for aarch64 with gcc
bpf/vmtest-bpf-VM_Test-4 success Logs for build for x86_64 with gcc
bpf/vmtest-bpf-VM_Test-5 success Logs for build for x86_64 with llvm-16
bpf/vmtest-bpf-VM_Test-3 success Logs for build for s390x with gcc
bpf/vmtest-bpf-VM_Test-9 success Logs for test_maps on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-10 success Logs for test_maps on x86_64 with llvm-16
bpf/vmtest-bpf-VM_Test-20 success Logs for test_progs_no_alu32_parallel on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-21 success Logs for test_progs_no_alu32_parallel on x86_64 with llvm-16
bpf/vmtest-bpf-VM_Test-25 success Logs for test_verifier on aarch64 with gcc
bpf/vmtest-bpf-VM_Test-27 success Logs for test_verifier on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-28 success Logs for test_verifier on x86_64 with llvm-16
bpf/vmtest-bpf-VM_Test-29 success Logs for veristat
bpf/vmtest-bpf-VM_Test-7 success Logs for test_maps on aarch64 with gcc
bpf/vmtest-bpf-VM_Test-11 success Logs for test_progs on aarch64 with gcc
bpf/vmtest-bpf-VM_Test-13 success Logs for test_progs on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-14 success Logs for test_progs on x86_64 with llvm-16
bpf/vmtest-bpf-VM_Test-15 success Logs for test_progs_no_alu32 on aarch64 with gcc
bpf/vmtest-bpf-VM_Test-17 success Logs for test_progs_no_alu32 on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-18 success Logs for test_progs_no_alu32 on x86_64 with llvm-16
bpf/vmtest-bpf-VM_Test-19 success Logs for test_progs_no_alu32_parallel on aarch64 with gcc
bpf/vmtest-bpf-VM_Test-22 success Logs for test_progs_parallel on aarch64 with gcc
bpf/vmtest-bpf-VM_Test-23 success Logs for test_progs_parallel on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-24 success Logs for test_progs_parallel on x86_64 with llvm-16
bpf/vmtest-bpf-VM_Test-26 success Logs for test_verifier on s390x with gcc
bpf/vmtest-bpf-VM_Test-16 success Logs for test_progs_no_alu32 on s390x with gcc
bpf/vmtest-bpf-VM_Test-12 success Logs for test_progs on s390x with gcc
bpf/vmtest-bpf-VM_Test-8 success Logs for test_maps on s390x with gcc

Commit Message

Kumar Kartikeya Dwivedi July 13, 2023, 12:31 a.m. UTC
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(-)

Comments

Alexei Starovoitov July 14, 2023, 9:48 p.m. UTC | #1
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
>
Kumar Kartikeya Dwivedi July 17, 2023, 4:16 p.m. UTC | #2
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 mbox series

Patch

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)