On Wed, Feb 21, 2024 at 4:50 PM Eduard Zingerman <eddyz87@xxxxxxxxx> wrote:
>
> Let push_jmp_history() peek current jump history entry basing on the
> passed bpf_verifier_state. This replaces a "global" variable in
> bpf_verifier_env allowing to use push_jmp_history() for states other
> than env->cur_state.
>
> Signed-off-by: Eduard Zingerman <eddyz87@xxxxxxxxx>
> ---
> include/linux/bpf_verifier.h | 1 -
> kernel/bpf/verifier.c | 34 ++++++++++++++++------------------
> 2 files changed, 16 insertions(+), 19 deletions(-)
>
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 84365e6dd85d..cbfb235984c8 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -705,7 +705,6 @@ struct bpf_verifier_env {
> int cur_stack;
> } cfg;
> struct backtrack_state bt;
> - struct bpf_jmp_history_entry *cur_hist_ent;
> u32 pass_cnt; /* number of times do_check() was called */
> u32 subprog_cnt;
> /* number of instructions analyzed by the verifier */
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 011d54a1dc53..759ef089b33c 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -3304,24 +3304,34 @@ static bool is_jmp_point(struct bpf_verifier_env *env, int insn_idx)
> return env->insn_aux_data[insn_idx].jmp_point;
> }
>
> +static struct bpf_jmp_history_entry *get_jmp_hist_entry(struct bpf_verifier_state *st,
> + u32 hist_end, int insn_idx)
> +{
> + if (hist_end > 0 && st->jmp_history[hist_end - 1].idx == insn_idx)
> + return &st->jmp_history[hist_end - 1];
> + return NULL;
> +}
> +
> /* for any branch, call, exit record the history of jmps in the given state */
> static int push_jmp_history(struct bpf_verifier_env *env, struct bpf_verifier_state *cur,
> int insn_flags)
> {
> + struct bpf_jmp_history_entry *p, *cur_hist_ent;
> u32 cnt = cur->jmp_history_cnt;
> - struct bpf_jmp_history_entry *p;
> size_t alloc_size;
>
> + cur_hist_ent = get_jmp_hist_entry(cur, cnt, env->insn_idx);
> +
This is, generally speaking, not correct to do. You can have a tight
loop where the instruction with the same insn_idx is executed multiple
times and so we'll get multiple consecutive entries in jmp_history
with the same insn_idx. We shouldn't reuse hist_ent for all of them,
each simulated instruction execution should have its own entry in jump
history.
It's fine to use get_jmp_hist_entry() in backtracking, though.
I'll look through the rest of patches more closely first before
suggesting any alternatives. But what you do in this patch is not 100%
correct.
> /* combine instruction flags if we already recorded this instruction */
> - if (env->cur_hist_ent) {
> + if (cur_hist_ent) {
> /* atomic instructions push insn_flags twice, for READ and
> * WRITE sides, but they should agree on stack slot
> */
> - WARN_ONCE((env->cur_hist_ent->flags & insn_flags) &&
> - (env->cur_hist_ent->flags & insn_flags) != insn_flags,
> + WARN_ONCE((cur_hist_ent->flags & insn_flags) &&
> + (cur_hist_ent->flags & insn_flags) != insn_flags,
> "verifier insn history bug: insn_idx %d cur flags %x new flags %x\n",
> - env->insn_idx, env->cur_hist_ent->flags, insn_flags);
> - env->cur_hist_ent->flags |= insn_flags;
> + env->insn_idx, cur_hist_ent->flags, insn_flags);
> + cur_hist_ent->flags |= insn_flags;
> return 0;
> }
>
> @@ -3337,19 +3347,10 @@ static int push_jmp_history(struct bpf_verifier_env *env, struct bpf_verifier_st
> p->prev_idx = env->prev_insn_idx;
> p->flags = insn_flags;
> cur->jmp_history_cnt = cnt;
> - env->cur_hist_ent = p;
>
> return 0;
> }
>
> -static struct bpf_jmp_history_entry *get_jmp_hist_entry(struct bpf_verifier_state *st,
> - u32 hist_end, int insn_idx)
> -{
> - if (hist_end > 0 && st->jmp_history[hist_end - 1].idx == insn_idx)
> - return &st->jmp_history[hist_end - 1];
> - return NULL;
> -}
> -
> /* Backtrack one insn at a time. If idx is not at the top of recorded
> * history then previous instruction came from straight line execution.
> * Return -ENOENT if we exhausted all instructions within given state.
> @@ -17437,9 +17438,6 @@ static int do_check(struct bpf_verifier_env *env)
> u8 class;
> int err;
>
> - /* reset current history entry on each new instruction */
> - env->cur_hist_ent = NULL;
> -
> env->prev_insn_idx = prev_insn_idx;
> if (env->insn_idx >= insn_cnt) {
> verbose(env, "invalid insn idx %d insn_cnt %d\n",
> --
> 2.43.0
>
