On Mon, Nov 20, 2023 at 3:00 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 | 11 ++++++
> kernel/bpf/verifier.c | 17 +++++++--
> .../bpf/progs/verifier_subprog_precision.c | 35 +++++++++++++------
> 3 files changed, 51 insertions(+), 12 deletions(-)
>
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 6e21d74a64e7..9ed6672534c7 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -301,6 +301,17 @@ 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.
> + * Value in frame N refers to number of times callback with frame
> + * N+1 was simulated, e.g. for the following call:
> + *
> + * bpf_loop(..., fn, ...); | suppose current frame is N
> + * | fn would be simulated in frame N+1
> + * | number of simulations is tracked in frame N
> + */
> + 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 004de7c32bae..37d8c22c292a 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -9505,6 +9505,8 @@ static int push_callback_call(struct bpf_verifier_env *env, struct bpf_insn *ins
> return err;
>
> callback_state->cumulative_callback_depth++;
> + callback_state->frame[callback_state->curframe - 1]->callback_depth++;
> + caller->callback_depth = 0;
> return 0;
> }
>
> @@ -10309,8 +10311,19 @@ 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);
> + /* Verifier relies on R1 value to determine if bpf_loop() iteration
> + * is finished, thus mark it precise.
> + */
> + mark_chain_precision(env, BPF_REG_1);
huh? What about error handling?
> + 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, "frame%d bpf_loop iteration limit reached\n",
> + env->cur_state->curframe);
> + }
> break;
> case BPF_FUNC_dynptr_from_mem:
> if (regs[BPF_REG_1].type != PTR_TO_MAP_VALUE) {
> diff --git a/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c b/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c
> index da803cffb5ef..f61d623b1ce8 100644
> --- a/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c
> +++ b/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c
> @@ -119,7 +119,23 @@ __naked int global_subprog_result_precise(void)
>
> SEC("?raw_tp")
> __success __log_level(2)
> -/* First simulated path does not include callback body */
> +/* First simulated path does not include callback body,
> + * r1 and r4 are always precise for bpf_loop() calls.
> + */
> +__msg("9: (85) call bpf_loop#181")
> +__msg("mark_precise: frame0: last_idx 9 first_idx 9 subseq_idx -1")
> +__msg("mark_precise: frame0: parent state regs=r4 stack=:")
> +__msg("mark_precise: frame0: last_idx 8 first_idx 0 subseq_idx 9")
> +__msg("mark_precise: frame0: regs=r4 stack= before 8: (b7) r4 = 0")
> +__msg("mark_precise: frame0: last_idx 9 first_idx 9 subseq_idx -1")
> +__msg("mark_precise: frame0: parent state regs=r1 stack=:")
> +__msg("mark_precise: frame0: last_idx 8 first_idx 0 subseq_idx 9")
> +__msg("mark_precise: frame0: regs=r1 stack= before 8: (b7) r4 = 0")
> +__msg("mark_precise: frame0: regs=r1 stack= before 7: (b7) r3 = 0")
> +__msg("mark_precise: frame0: regs=r1 stack= before 6: (bf) r2 = r8")
> +__msg("mark_precise: frame0: regs=r1 stack= before 5: (bf) r1 = r6")
> +__msg("mark_precise: frame0: regs=r6 stack= before 4: (b7) r6 = 3")
> +/* r6 precision propagation */
> __msg("14: (0f) r1 += r6")
> __msg("mark_precise: frame0: last_idx 14 first_idx 9")
> __msg("mark_precise: frame0: regs=r6 stack= before 13: (bf) r1 = r7")
> @@ -134,10 +150,9 @@ __msg("17: (b7) r0 = 0")
> __msg("18: (95) exit")
> __msg("returning from callee:")
> __msg("to caller at 9:")
> -/* r4 (flags) is always precise for bpf_loop() */
> -__msg("frame 0: propagating r4")
> +__msg("frame 0: propagating r1,r4")
> __msg("mark_precise: frame0: last_idx 9 first_idx 9 subseq_idx -1")
> -__msg("mark_precise: frame0: regs=r4 stack= before 18: (95) exit")
> +__msg("mark_precise: frame0: regs=r1,r4 stack= before 18: (95) exit")
> __msg("from 18 to 9: safe")
> __naked int callback_result_precise(void)
> {
> @@ -264,12 +279,12 @@ __msg("15: (b7) r0 = 0")
> __msg("16: (95) exit")
> __msg("returning from callee:")
> __msg("to caller at 9:")
> -/* r4 (flags) is always precise for bpf_loop(),
> +/* r1, r4 are always precise for bpf_loop(),
> * r6 was marked before backtracking to callback body.
> */
> -__msg("frame 0: propagating r4,r6")
> +__msg("frame 0: propagating r1,r4,r6")
> __msg("mark_precise: frame0: last_idx 9 first_idx 9 subseq_idx -1")
> -__msg("mark_precise: frame0: regs=r4,r6 stack= before 16: (95) exit")
> +__msg("mark_precise: frame0: regs=r1,r4,r6 stack= before 16: (95) exit")
> __msg("mark_precise: frame1: regs= stack= before 15: (b7) r0 = 0")
> __msg("mark_precise: frame1: regs= stack= before 9: (85) call bpf_loop")
> __msg("mark_precise: frame0: parent state regs= stack=:")
> @@ -422,12 +437,12 @@ __msg("17: (b7) r0 = 0")
> __msg("18: (95) exit")
> __msg("returning from callee:")
> __msg("to caller at 10:")
> -/* r4 (flags) is always precise for bpf_loop(),
> +/* r1, r4 are always precise for bpf_loop(),
> * fp-8 was marked before backtracking to callback body.
> */
> -__msg("frame 0: propagating r4,fp-8")
> +__msg("frame 0: propagating r1,r4,fp-8")
> __msg("mark_precise: frame0: last_idx 10 first_idx 10 subseq_idx -1")
> -__msg("mark_precise: frame0: regs=r4 stack=-8 before 18: (95) exit")
> +__msg("mark_precise: frame0: regs=r1,r4 stack=-8 before 18: (95) exit")
> __msg("mark_precise: frame1: regs= stack= before 17: (b7) r0 = 0")
> __msg("mark_precise: frame1: regs= stack= before 10: (85) call bpf_loop#181")
> __msg("mark_precise: frame0: parent state regs= stack=:")
> --
> 2.42.1
>
