diff mbox series

[bpf,10/12] bpf: keep track of max number of bpf_loop callback iterations

Message ID 20231116021803.9982-11-eddyz87@gmail.com (mailing list archive)
State Superseded
Delegated to: BPF
Headers show
Series verify callbacks as if they are called unknown number of times | expand

Checks

Context Check Description
netdev/series_format success Posting correctly formatted
netdev/tree_selection success Clearly marked for bpf, async
netdev/fixes_present fail Series targets non-next tree, but doesn't contain any Fixes tags
netdev/header_inline success No static functions without inline keyword in header files
netdev/build_32bit success Errors and warnings before: 1197 this patch: 1197
netdev/cc_maintainers warning 6 maintainers not CCed: haoluo@google.com song@kernel.org kpsingh@kernel.org jolsa@kernel.org john.fastabend@gmail.com sdf@google.com
netdev/build_clang success Errors and warnings before: 1162 this patch: 1162
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 No Fixes tag
netdev/build_allmodconfig_warn success Errors and warnings before: 1224 this patch: 1224
netdev/checkpatch warning WARNING: line length of 85 exceeds 80 columns WARNING: line length of 89 exceeds 80 columns
netdev/build_clang_rust success No Rust files in patch. Skipping build
netdev/kdoc success Errors and warnings before: 0 this patch: 0
netdev/source_inline success Was 0 now: 0
bpf/vmtest-bpf-VM_Test-0 success Logs for Lint
bpf/vmtest-bpf-VM_Test-1 success Logs for ShellCheck
bpf/vmtest-bpf-VM_Test-2 success Logs for Validate matrix.py
bpf/vmtest-bpf-VM_Test-3 success Logs for aarch64-gcc / build / build for aarch64 with gcc
bpf/vmtest-bpf-VM_Test-7 success Logs for aarch64-gcc / test (test_verifier, false, 360) / test_verifier on aarch64 with gcc
bpf/vmtest-bpf-VM_Test-8 success Logs for aarch64-gcc / veristat
bpf/vmtest-bpf-VM_Test-4 success Logs for aarch64-gcc / test (test_maps, false, 360) / test_maps on aarch64 with gcc
bpf/vmtest-bpf-VM_Test-5 success Logs for aarch64-gcc / test (test_progs, false, 360) / test_progs on aarch64 with gcc
bpf/vmtest-bpf-VM_Test-6 success Logs for aarch64-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on aarch64 with gcc
bpf/vmtest-bpf-VM_Test-9 success Logs for s390x-gcc / build / build for s390x with gcc
bpf/vmtest-bpf-VM_Test-14 success Logs for s390x-gcc / veristat
bpf/vmtest-bpf-VM_Test-15 success Logs for set-matrix
bpf/vmtest-bpf-VM_Test-16 success Logs for x86_64-gcc / build / build for x86_64 with gcc
bpf/vmtest-bpf-VM_Test-17 success Logs for x86_64-gcc / test (test_maps, false, 360) / test_maps on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-18 success Logs for x86_64-gcc / test (test_progs, false, 360) / test_progs on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-19 success Logs for x86_64-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-20 success Logs for x86_64-gcc / test (test_progs_no_alu32_parallel, true, 30) / test_progs_no_alu32_parallel on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-21 success Logs for x86_64-gcc / test (test_progs_parallel, true, 30) / test_progs_parallel on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-22 success Logs for x86_64-gcc / test (test_verifier, false, 360) / test_verifier on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-23 success Logs for x86_64-gcc / veristat / veristat on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-24 success Logs for x86_64-llvm-16 / build / build for x86_64 with llvm-16
bpf/vmtest-bpf-VM_Test-25 success Logs for x86_64-llvm-16 / test (test_maps, false, 360) / test_maps on x86_64 with llvm-16
bpf/vmtest-bpf-VM_Test-26 success Logs for x86_64-llvm-16 / test (test_progs, false, 360) / test_progs on x86_64 with llvm-16
bpf/vmtest-bpf-VM_Test-27 success Logs for x86_64-llvm-16 / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on x86_64 with llvm-16
bpf/vmtest-bpf-VM_Test-28 success Logs for x86_64-llvm-16 / test (test_verifier, false, 360) / test_verifier on x86_64 with llvm-16
bpf/vmtest-bpf-VM_Test-29 success Logs for x86_64-llvm-16 / veristat
bpf/vmtest-bpf-VM_Test-13 success Logs for s390x-gcc / test (test_verifier, false, 360) / test_verifier on s390x with gcc
bpf/vmtest-bpf-VM_Test-12 success Logs for s390x-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on s390x with gcc
bpf/vmtest-bpf-VM_Test-11 success Logs for s390x-gcc / test (test_progs, false, 360) / test_progs on s390x with gcc
bpf/vmtest-bpf-PR success PR summary
bpf/vmtest-bpf-VM_Test-10 success Logs for s390x-gcc / test (test_maps, false, 360) / test_maps on s390x with gcc

Commit Message

Eduard Zingerman Nov. 16, 2023, 2:18 a.m. UTC 
In some cases verifier can't infer convergence of the bpf_loop()
iteration. E.g. for the following program:

    static int cb(__u32 idx, struct num_context* ctx)
    {
        ctx->i++;
        return 0;
    }

    SEC("?raw_tp")
    int prog(void *_)
    {
        struct num_context ctx = { .i = 0 };
        __u8 choice_arr[2] = { 0, 1 };

        bpf_loop(2, cb, &ctx, 0);
        return choice_arr[ctx.i];
    }

Each 'cb' simulation would eventually return to 'prog' and reach
'return choice_arr[ctx.i]' statement. At which point ctx.i would be
marked precise, thus forcing verifier to track multitude of separate
states with {.i=0}, {.i=1}, ... at bpf_loop() callback entry.

This commit allows "brute force" handling for such cases by limiting
number of callback body simulations using 'umax' value of the first
bpf_loop() parameter.

For this, extend bpf_func_state with 'callback_depth' field.
Increment this field when callback visiting state is pushed to states
traversal stack. For frame #N it's 'callback_depth' field counts how
many times callback with frame depth N+1 had been executed.
Use bpf_func_state specifically to allow independent tracking of
callback depths when multiple nested bpf_loop() calls are present.

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 include/linux/bpf_verifier.h |  9 +++++++++
 kernel/bpf/verifier.c        | 12 ++++++++++--
 2 files changed, 19 insertions(+), 2 deletions(-)

Comments

Andrii Nakryiko Nov. 16, 2023, 2:08 p.m. UTC | #1 
On Wed, Nov 15, 2023 at 9:18 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> In some cases verifier can't infer convergence of the bpf_loop()
> iteration. E.g. for the following program:
>
>     static int cb(__u32 idx, struct num_context* ctx)
>     {
>         ctx->i++;
>         return 0;
>     }
>
>     SEC("?raw_tp")
>     int prog(void *_)
>     {
>         struct num_context ctx = { .i = 0 };
>         __u8 choice_arr[2] = { 0, 1 };
>
>         bpf_loop(2, cb, &ctx, 0);
>         return choice_arr[ctx.i];
>     }
>
> Each 'cb' simulation would eventually return to 'prog' and reach
> 'return choice_arr[ctx.i]' statement. At which point ctx.i would be
> marked precise, thus forcing verifier to track multitude of separate
> states with {.i=0}, {.i=1}, ... at bpf_loop() callback entry.
>
> This commit allows "brute force" handling for such cases by limiting
> number of callback body simulations using 'umax' value of the first
> bpf_loop() parameter.
>
> For this, extend bpf_func_state with 'callback_depth' field.
> Increment this field when callback visiting state is pushed to states
> traversal stack. For frame #N it's 'callback_depth' field counts how
> many times callback with frame depth N+1 had been executed.
> Use bpf_func_state specifically to allow independent tracking of
> callback depths when multiple nested bpf_loop() calls are present.
>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
>  include/linux/bpf_verifier.h |  9 +++++++++
>  kernel/bpf/verifier.c        | 12 ++++++++++--
>  2 files changed, 19 insertions(+), 2 deletions(-)
>
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 0ffb479c72d8..302f9c310de7 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -301,6 +301,15 @@ struct bpf_func_state {
>         struct tnum callback_ret_range;
>         bool in_async_callback_fn;
>         bool in_exception_callback_fn;
> +       /* For callback calling functions that limit number of possible
> +        * callback executions (e.g. bpf_loop) keeps track of current
> +        * simulated iteration number. When non-zero either:
> +        * - current frame has a child frame, in such case it's callsite points
> +        *   to callback calling function;
> +        * - current frame is a topmost frame, in such case callback has just
> +        *   returned and env->insn_idx points to callback calling function.
> +        */
> +       u32 callback_depth;
>
>         /* The following fields should be last. See copy_func_state() */
>         int acquired_refs;
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 5b8c0ebcb4f6..474af277ea54 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -9680,6 +9680,8 @@ static int push_callback_call(struct bpf_verifier_env *env, struct bpf_insn *ins
>                 return err;
>
>         callback_state->callback_iter_depth++;
> +       callback_state->frame[callback_state->curframe - 1]->callback_depth++;
> +       caller->callback_depth = 0;
>         return 0;
>  }
>
> @@ -10479,8 +10481,14 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn
>                 break;
>         case BPF_FUNC_loop:
>                 update_loop_inline_state(env, meta.subprogno);
> -               err = push_callback_call(env, insn, insn_idx, meta.subprogno,
> -                                        set_loop_callback_state);
> +               if (env->log.level & BPF_LOG_LEVEL2)
> +                       verbose(env, "frame%d callback_depth=%u\n",
> +                               env->cur_state->curframe, cur_func(env)->callback_depth);
> +               if (cur_func(env)->callback_depth < regs[BPF_REG_1].umax_value)

I haven't had time to look at the patch set properly yet and I'm not
sure if I'll have time today. But one thing that I randomly realized
is that if you are taking umax_value into account then this BPF_REG_1
has to be precise, so please make sure to mark_chain_precision() on it
first.

> +                       err = push_callback_call(env, insn, insn_idx, meta.subprogno,
> +                                                set_loop_callback_state);
> +               else
> +                       cur_func(env)->callback_depth = 0;
>                 break;
>         case BPF_FUNC_dynptr_from_mem:
>                 if (regs[BPF_REG_1].type != PTR_TO_MAP_VALUE) {
> --
> 2.42.0
>
Eduard Zingerman Nov. 16, 2023, 2:13 p.m. UTC | #2 
On Thu, 2023-11-16 at 09:08 -0500, Andrii Nakryiko wrote:
[...]
> > @@ -10479,8 +10481,14 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn
> >                 break;
> >         case BPF_FUNC_loop:
> >                 update_loop_inline_state(env, meta.subprogno);
> > -               err = push_callback_call(env, insn, insn_idx, meta.subprogno,
> > -                                        set_loop_callback_state);
> > +               if (env->log.level & BPF_LOG_LEVEL2)
> > +                       verbose(env, "frame%d callback_depth=%u\n",
> > +                               env->cur_state->curframe, cur_func(env)->callback_depth);
> > +               if (cur_func(env)->callback_depth < regs[BPF_REG_1].umax_value)
> 
> I haven't had time to look at the patch set properly yet and I'm not
> sure if I'll have time today. But one thing that I randomly realized
> is that if you are taking umax_value into account then this BPF_REG_1
> has to be precise, so please make sure to mark_chain_precision() on it
> first.

Yes, makes sense, thank you for spotting this.
Will update in v2, waiting for some more feedback before resending.
Andrii Nakryiko Nov. 17, 2023, 4:47 p.m. UTC | #3 
On Wed, Nov 15, 2023 at 9:18 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> In some cases verifier can't infer convergence of the bpf_loop()
> iteration. E.g. for the following program:
>
>     static int cb(__u32 idx, struct num_context* ctx)
>     {
>         ctx->i++;
>         return 0;
>     }
>
>     SEC("?raw_tp")
>     int prog(void *_)
>     {
>         struct num_context ctx = { .i = 0 };
>         __u8 choice_arr[2] = { 0, 1 };
>
>         bpf_loop(2, cb, &ctx, 0);
>         return choice_arr[ctx.i];
>     }
>
> Each 'cb' simulation would eventually return to 'prog' and reach
> 'return choice_arr[ctx.i]' statement. At which point ctx.i would be
> marked precise, thus forcing verifier to track multitude of separate
> states with {.i=0}, {.i=1}, ... at bpf_loop() callback entry.
>
> This commit allows "brute force" handling for such cases by limiting
> number of callback body simulations using 'umax' value of the first
> bpf_loop() parameter.
>
> For this, extend bpf_func_state with 'callback_depth' field.
> Increment this field when callback visiting state is pushed to states
> traversal stack. For frame #N it's 'callback_depth' field counts how
> many times callback with frame depth N+1 had been executed.
> Use bpf_func_state specifically to allow independent tracking of
> callback depths when multiple nested bpf_loop() calls are present.
>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
>  include/linux/bpf_verifier.h |  9 +++++++++
>  kernel/bpf/verifier.c        | 12 ++++++++++--
>  2 files changed, 19 insertions(+), 2 deletions(-)
>
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 0ffb479c72d8..302f9c310de7 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -301,6 +301,15 @@ struct bpf_func_state {
>         struct tnum callback_ret_range;
>         bool in_async_callback_fn;
>         bool in_exception_callback_fn;
> +       /* For callback calling functions that limit number of possible
> +        * callback executions (e.g. bpf_loop) keeps track of current
> +        * simulated iteration number. When non-zero either:
> +        * - current frame has a child frame, in such case it's callsite points
> +        *   to callback calling function;
> +        * - current frame is a topmost frame, in such case callback has just
> +        *   returned and env->insn_idx points to callback calling function.
> +        */
> +       u32 callback_depth;
>
>         /* The following fields should be last. See copy_func_state() */
>         int acquired_refs;
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 5b8c0ebcb4f6..474af277ea54 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -9680,6 +9680,8 @@ static int push_callback_call(struct bpf_verifier_env *env, struct bpf_insn *ins
>                 return err;
>
>         callback_state->callback_iter_depth++;
> +       callback_state->frame[callback_state->curframe - 1]->callback_depth++;
> +       caller->callback_depth = 0;
>         return 0;
>  }
>
> @@ -10479,8 +10481,14 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn
>                 break;
>         case BPF_FUNC_loop:
>                 update_loop_inline_state(env, meta.subprogno);
> -               err = push_callback_call(env, insn, insn_idx, meta.subprogno,
> -                                        set_loop_callback_state);
> +               if (env->log.level & BPF_LOG_LEVEL2)
> +                       verbose(env, "frame%d callback_depth=%u\n",
> +                               env->cur_state->curframe, cur_func(env)->callback_depth);

btw, is this a debugging leftover or intentional? If the latter, why
is it done only for bpf_loop()? Maybe push_callback_call() be a better
place for it?

> +               if (cur_func(env)->callback_depth < regs[BPF_REG_1].umax_value)
> +                       err = push_callback_call(env, insn, insn_idx, meta.subprogno,
> +                                                set_loop_callback_state);
> +               else
> +                       cur_func(env)->callback_depth = 0;

I guess it's actually a bit more interesting to know that we stopped
iterating because umax is reached. But I'm actually not sure whether
we should be adding these logs at all, though I don't have a strong
preference.



>                 break;
>         case BPF_FUNC_dynptr_from_mem:
>                 if (regs[BPF_REG_1].type != PTR_TO_MAP_VALUE) {
> --
> 2.42.0
>
Eduard Zingerman Nov. 17, 2023, 6:53 p.m. UTC | #4 
On Fri, 2023-11-17 at 11:47 -0500, Andrii Nakryiko wrote:
[...]
> > @@ -10479,8 +10481,14 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn
> >                 break;
> >         case BPF_FUNC_loop:
> >                 update_loop_inline_state(env, meta.subprogno);
> > -               err = push_callback_call(env, insn, insn_idx, meta.subprogno,
> > -                                        set_loop_callback_state);
> > +               if (env->log.level & BPF_LOG_LEVEL2)
> > +                       verbose(env, "frame%d callback_depth=%u\n",
> > +                               env->cur_state->curframe, cur_func(env)->callback_depth);
> 
> btw, is this a debugging leftover or intentional? If the latter, why
> is it done only for bpf_loop()? Maybe push_callback_call() be a better
> place for it?

Intentional...

> 
> > +               if (cur_func(env)->callback_depth < regs[BPF_REG_1].umax_value)
> > +                       err = push_callback_call(env, insn, insn_idx, meta.subprogno,
> > +                                                set_loop_callback_state);
> > +               else
> > +                       cur_func(env)->callback_depth = 0;
> 
> I guess it's actually a bit more interesting to know that we stopped
> iterating because umax is reached. But I'm actually not sure whether
> we should be adding these logs at all, though I don't have a strong
> preference.

... it is not obvious to infer current depth looking at the log, so I
think something should be printed. Note about stopped iteration sounds
good, and it could be placed here, not in the push_callback_call(), e.g.:

               if (cur_func(env)->callback_depth < regs[BPF_REG_1].umax_value)
                       err = push_callback_call(env, insn, insn_idx, meta.subprogno,
                                                set_loop_callback_state);
               else {
                       cur_func(env)->callback_depth = 0;
                       if (env->log.level & BPF_LOG_LEVEL2)
                               verbose(env, "bpf_loop iteration limit reached\n");
               }

wdyt?
Andrii Nakryiko Nov. 17, 2023, 8:30 p.m. UTC | #5 
On Fri, Nov 17, 2023 at 1:53 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Fri, 2023-11-17 at 11:47 -0500, Andrii Nakryiko wrote:
> [...]
> > > @@ -10479,8 +10481,14 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn
> > >                 break;
> > >         case BPF_FUNC_loop:
> > >                 update_loop_inline_state(env, meta.subprogno);
> > > -               err = push_callback_call(env, insn, insn_idx, meta.subprogno,
> > > -                                        set_loop_callback_state);
> > > +               if (env->log.level & BPF_LOG_LEVEL2)
> > > +                       verbose(env, "frame%d callback_depth=%u\n",
> > > +                               env->cur_state->curframe, cur_func(env)->callback_depth);
> >
> > btw, is this a debugging leftover or intentional? If the latter, why
> > is it done only for bpf_loop()? Maybe push_callback_call() be a better
> > place for it?
>
> Intentional...
>
> >
> > > +               if (cur_func(env)->callback_depth < regs[BPF_REG_1].umax_value)
> > > +                       err = push_callback_call(env, insn, insn_idx, meta.subprogno,
> > > +                                                set_loop_callback_state);
> > > +               else
> > > +                       cur_func(env)->callback_depth = 0;
> >
> > I guess it's actually a bit more interesting to know that we stopped
> > iterating because umax is reached. But I'm actually not sure whether
> > we should be adding these logs at all, though I don't have a strong
> > preference.
>
> ... it is not obvious to infer current depth looking at the log, so I
> think something should be printed. Note about stopped iteration sounds
> good, and it could be placed here, not in the push_callback_call(), e.g.:
>
>                if (cur_func(env)->callback_depth < regs[BPF_REG_1].umax_value)
>                        err = push_callback_call(env, insn, insn_idx, meta.subprogno,
>                                                 set_loop_callback_state);
>                else {
>                        cur_func(env)->callback_depth = 0;
>                        if (env->log.level & BPF_LOG_LEVEL2)
>                                verbose(env, "bpf_loop iteration limit reached\n");
>                }
>
> wdyt?
>
>

Sure, I don't mind.
diff mbox series

Patch

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 0ffb479c72d8..302f9c310de7 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -301,6 +301,15 @@  struct bpf_func_state {
 	struct tnum callback_ret_range;
 	bool in_async_callback_fn;
 	bool in_exception_callback_fn;
+	/* For callback calling functions that limit number of possible
+	 * callback executions (e.g. bpf_loop) keeps track of current
+	 * simulated iteration number. When non-zero either:
+	 * - current frame has a child frame, in such case it's callsite points
+	 *   to callback calling function;
+	 * - current frame is a topmost frame, in such case callback has just
+	 *   returned and env->insn_idx points to callback calling function.
+	 */
+	u32 callback_depth;
 
 	/* The following fields should be last. See copy_func_state() */
 	int acquired_refs;
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 5b8c0ebcb4f6..474af277ea54 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -9680,6 +9680,8 @@  static int push_callback_call(struct bpf_verifier_env *env, struct bpf_insn *ins
 		return err;
 
 	callback_state->callback_iter_depth++;
+	callback_state->frame[callback_state->curframe - 1]->callback_depth++;
+	caller->callback_depth = 0;
 	return 0;
 }
 
@@ -10479,8 +10481,14 @@  static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn
 		break;
 	case BPF_FUNC_loop:
 		update_loop_inline_state(env, meta.subprogno);
-		err = push_callback_call(env, insn, insn_idx, meta.subprogno,
-					 set_loop_callback_state);
+		if (env->log.level & BPF_LOG_LEVEL2)
+			verbose(env, "frame%d callback_depth=%u\n",
+				env->cur_state->curframe, cur_func(env)->callback_depth);
+		if (cur_func(env)->callback_depth < regs[BPF_REG_1].umax_value)
+			err = push_callback_call(env, insn, insn_idx, meta.subprogno,
+						 set_loop_callback_state);
+		else
+			cur_func(env)->callback_depth = 0;
 		break;
 	case BPF_FUNC_dynptr_from_mem:
 		if (regs[BPF_REG_1].type != PTR_TO_MAP_VALUE) {