diff mbox series

[bpf-next,1/4] bpf: replace env->cur_hist_ent with a getter function

Message ID 20240222005005.31784-2-eddyz87@gmail.com (mailing list archive)
State Changes Requested
Delegated to: BPF
Headers show
Series bpf: track find_equal_scalars history on per-instruction level | expand

Checks

Context Check Description
bpf/vmtest-bpf-next-PR success PR summary
netdev/series_format success Posting correctly formatted
netdev/tree_selection success Clearly marked for bpf-next
netdev/ynl success Generated files up to date; no warnings/errors; no diff in generated;
netdev/fixes_present success Fixes tag not required for -next series
netdev/header_inline success No static functions without inline keyword in header files
netdev/build_32bit success Errors and warnings before: 1113 this patch: 1113
netdev/build_tools success Errors and warnings before: 0 this patch: 0
netdev/cc_maintainers warning 6 maintainers not CCed: jolsa@kernel.org john.fastabend@gmail.com kpsingh@kernel.org song@kernel.org sdf@google.com haoluo@google.com
netdev/build_clang success Errors and warnings before: 1066 this patch: 1066
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: 1130 this patch: 1130
netdev/checkpatch warning WARNING: line length of 83 exceeds 80 columns WARNING: line length of 86 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-next-VM_Test-0 success Logs for Lint
bpf/vmtest-bpf-next-VM_Test-1 success Logs for ShellCheck
bpf/vmtest-bpf-next-VM_Test-3 success Logs for Validate matrix.py
bpf/vmtest-bpf-next-VM_Test-2 success Logs for Unittests
bpf/vmtest-bpf-next-VM_Test-5 success Logs for aarch64-gcc / build-release
bpf/vmtest-bpf-next-VM_Test-4 success Logs for aarch64-gcc / build / build for aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-9 success Logs for aarch64-gcc / test (test_verifier, false, 360) / test_verifier on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-11 success Logs for s390x-gcc / build / build for s390x with gcc
bpf/vmtest-bpf-next-VM_Test-10 success Logs for aarch64-gcc / veristat
bpf/vmtest-bpf-next-VM_Test-12 success Logs for s390x-gcc / build-release
bpf/vmtest-bpf-next-VM_Test-16 success Logs for s390x-gcc / test (test_verifier, false, 360) / test_verifier on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-18 success Logs for set-matrix
bpf/vmtest-bpf-next-VM_Test-17 success Logs for s390x-gcc / veristat
bpf/vmtest-bpf-next-VM_Test-19 success Logs for x86_64-gcc / build / build for x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-20 success Logs for x86_64-gcc / build-release
bpf/vmtest-bpf-next-VM_Test-33 success Logs for x86_64-llvm-17 / test (test_verifier, false, 360) / test_verifier on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-28 success Logs for x86_64-llvm-17 / build / build for x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-34 success Logs for x86_64-llvm-17 / veristat
bpf/vmtest-bpf-next-VM_Test-35 success Logs for x86_64-llvm-18 / build / build for x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-41 success Logs for x86_64-llvm-18 / test (test_verifier, false, 360) / test_verifier on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-42 success Logs for x86_64-llvm-18 / veristat
bpf/vmtest-bpf-next-VM_Test-6 success Logs for aarch64-gcc / test (test_maps, false, 360) / test_maps on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-7 success Logs for aarch64-gcc / test (test_progs, false, 360) / test_progs on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-31 success Logs for x86_64-llvm-17 / test (test_progs, false, 360) / test_progs on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-30 success Logs for x86_64-llvm-17 / test (test_maps, false, 360) / test_maps on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-32 success Logs for x86_64-llvm-17 / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-37 success Logs for x86_64-llvm-18 / test (test_maps, false, 360) / test_maps on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-38 success Logs for x86_64-llvm-18 / test (test_progs, false, 360) / test_progs on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-39 success Logs for x86_64-llvm-18 / test (test_progs_cpuv4, false, 360) / test_progs_cpuv4 on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-40 success Logs for x86_64-llvm-18 / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-8 success Logs for aarch64-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-13 success Logs for s390x-gcc / test (test_maps, false, 360) / test_maps on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-21 success Logs for x86_64-gcc / test (test_maps, false, 360) / test_maps on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-27 success Logs for x86_64-gcc / veristat / veristat on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-26 success Logs for x86_64-gcc / test (test_verifier, false, 360) / test_verifier on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-22 success Logs for x86_64-gcc / test (test_progs, false, 360) / test_progs on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-23 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-next-VM_Test-24 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-next-VM_Test-25 success Logs for x86_64-gcc / test (test_progs_parallel, true, 30) / test_progs_parallel on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-15 success Logs for s390x-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-36 success Logs for x86_64-llvm-18 / build-release / build for x86_64 with llvm-18 and -O2 optimization
bpf/vmtest-bpf-next-VM_Test-14 success Logs for s390x-gcc / test (test_progs, false, 360) / test_progs on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-29 success Logs for x86_64-llvm-17 / build-release / build for x86_64 with llvm-17 and -O2 optimization

Commit Message

Eduard Zingerman Feb. 22, 2024, 12:50 a.m. UTC 
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@gmail.com>
---
 include/linux/bpf_verifier.h |  1 -
 kernel/bpf/verifier.c        | 34 ++++++++++++++++------------------
 2 files changed, 16 insertions(+), 19 deletions(-)

Comments

Andrii Nakryiko Feb. 28, 2024, 7:46 p.m. UTC | #1 
On Wed, Feb 21, 2024 at 4:50 PM Eduard Zingerman <eddyz87@gmail.com> 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@gmail.com>
> ---
>  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
>
Eduard Zingerman Feb. 28, 2024, 9:23 p.m. UTC | #2 
On Wed, 2024-02-28 at 11:46 -0800, Andrii Nakryiko wrote:
[...]

> > 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.

You are correct.

> 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.

No need, the patch-set does not rely on capability to push entry for
several states simultaneously. I'll just drop this patch from v2.

[...]
diff mbox series

Patch

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);
+
 	/* 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",