Re: [PATCH bpf-next v4 1/4] bpf: use scalar ids in mark_chain_precision()

[Andrii Nakryiko <andrii.nakryiko@gmail.com>]

On Fri, Jun 9, 2023 at 2:01 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> Change mark_chain_precision() to track precision in situations
> like below:
>
>     r2 = unknown value
>     ...
>   --- state #0 ---
>     ...
>     r1 = r2                 // r1 and r2 now share the same ID
>     ...
>   --- state #1 {r1.id = A, r2.id = A} ---
>     ...
>     if (r2 > 10) goto exit; // find_equal_scalars() assigns range to r1
>     ...
>   --- state #2 {r1.id = A, r2.id = A} ---
>     r3 = r10
>     r3 += r1                // need to mark both r1 and r2
>
> At the beginning of the processing of each state, ensure that if a
> register with a scalar ID is marked as precise, all registers sharing
> this ID are also marked as precise.
>
> This property would be used by a follow-up change in regsafe().
>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
>  include/linux/bpf_verifier.h                  |  10 +-
>  kernel/bpf/verifier.c                         | 115 ++++++++++++++++++
>  .../testing/selftests/bpf/verifier/precise.c  |   8 +-
>  3 files changed, 128 insertions(+), 5 deletions(-)
>
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 5fe589e11ac8..73a98f6240fd 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -559,6 +559,11 @@ struct backtrack_state {
>         u64 stack_masks[MAX_CALL_FRAMES];
>  };
>
> +struct bpf_idset {
> +       u32 count;
> +       u32 ids[BPF_ID_MAP_SIZE];
> +};
> +
>  /* single container for all structs
>   * one verifier_env per bpf_check() call
>   */
> @@ -590,7 +595,10 @@ struct bpf_verifier_env {
>         const struct bpf_line_info *prev_linfo;
>         struct bpf_verifier_log log;
>         struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS + 1];
> -       struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE];
> +       union {
> +               struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE];
> +               struct bpf_idset idset_scratch;
> +       };
>         struct {
>                 int *insn_state;
>                 int *insn_stack;
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index ed79a93398f8..f719de396c61 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -3787,6 +3787,96 @@ static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_
>         }
>  }
>
> +static bool idset_contains(struct bpf_idset *s, u32 id)
> +{
> +       u32 i;
> +
> +       for (i = 0; i < s->count; ++i)
> +               if (s->ids[i] == id)
> +                       return true;
> +
> +       return false;
> +}
> +
> +static int idset_push(struct bpf_idset *s, u32 id)
> +{
> +       if (WARN_ON_ONCE(s->count >= ARRAY_SIZE(s->ids)))
> +               return -1;
> +       s->ids[s->count++] = id;
> +       return 0;
> +}
> +
> +static void idset_reset(struct bpf_idset *s)
> +{
> +       s->count = 0;
> +}
> +
> +/* Collect a set of IDs for all registers currently marked as precise in env->bt.
> + * Mark all registers with these IDs as precise.
> + */
> +static int mark_precise_scalar_ids(struct bpf_verifier_env *env, struct bpf_verifier_state *st)
> +{
> +       struct bpf_idset *precise_ids = &env->idset_scratch;
> +       struct backtrack_state *bt = &env->bt;
> +       struct bpf_func_state *func;
> +       struct bpf_reg_state *reg;
> +       DECLARE_BITMAP(mask, 64);
> +       int i, fr;
> +
> +       idset_reset(precise_ids);
> +
> +       for (fr = bt->frame; fr >= 0; fr--) {
> +               func = st->frame[fr];
> +
> +               bitmap_from_u64(mask, bt_frame_reg_mask(bt, fr));
> +               for_each_set_bit(i, mask, 32) {
> +                       reg = &func->regs[i];
> +                       if (!reg->id || reg->type != SCALAR_VALUE)
> +                               continue;
> +                       if (idset_push(precise_ids, reg->id))
> +                               return -1;
> +               }
> +
> +               bitmap_from_u64(mask, bt_frame_stack_mask(bt, fr));
> +               for_each_set_bit(i, mask, 64) {
> +                       if (i >= func->allocated_stack / BPF_REG_SIZE)
> +                               break;
> +                       if (!is_spilled_scalar_reg(&func->stack[i]))
> +                               continue;
> +                       reg = &func->stack[i].spilled_ptr;
> +                       if (!reg->id)
> +                               continue;
> +                       if (idset_push(precise_ids, reg->id))
> +                               return -1;

-EFAULT, -1 is -EPERM, super confusing if it ever bubbles up. Same for
idset_push return code, please use more appropriate error code
constants

Other than that, it looks good. Please add my ack once you fix error values:

Acked-by: Andrii Nakryiko <andrii@kernel.org>


> +               }
> +       }
> +
> +       for (fr = 0; fr <= st->curframe; ++fr) {
> +               func = st->frame[fr];
> +
> +               for (i = BPF_REG_0; i < BPF_REG_10; ++i) {
> +                       reg = &func->regs[i];
> +                       if (!reg->id)
> +                               continue;
> +                       if (!idset_contains(precise_ids, reg->id))
> +                               continue;
> +                       bt_set_frame_reg(bt, fr, i);
> +               }
> +               for (i = 0; i < func->allocated_stack / BPF_REG_SIZE; ++i) {
> +                       if (!is_spilled_scalar_reg(&func->stack[i]))
> +                               continue;
> +                       reg = &func->stack[i].spilled_ptr;
> +                       if (!reg->id)
> +                               continue;
> +                       if (!idset_contains(precise_ids, reg->id))
> +                               continue;
> +                       bt_set_frame_slot(bt, fr, i);
> +               }
> +       }
> +
> +       return 0;
> +}
> +

[...]