On Wed, Nov 15, 2023 at 9:18 PM Eduard Zingerman <eddyz87@xxxxxxxxx> 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@xxxxxxxxx>
> ---
> 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
>
