diff mbox series

[v5,bpf-next,2/4] bpf: Recognize that two registers are safe when their ranges match

Message ID 20240305045219.66142-3-alexei.starovoitov@gmail.com (mailing list archive)
State Superseded
Delegated to: BPF
Headers show
Series bpf: Introduce may_goto and cond_break | expand

Checks

Context Check Description
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-0 success Logs for Lint
bpf/vmtest-bpf-next-VM_Test-5 success Logs for aarch64-gcc / build-release
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-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-4 success Logs for aarch64-gcc / build / build for aarch64 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-9 success Logs for aarch64-gcc / test (test_verifier, false, 360) / test_verifier on aarch64 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-19 success Logs for x86_64-gcc / build / build for x86_64 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-20 success Logs for x86_64-gcc / build-release
bpf/vmtest-bpf-next-VM_Test-17 success Logs for s390x-gcc / veristat
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-18 success Logs for set-matrix
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-28 success Logs for x86_64-llvm-17 / build / build for 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-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-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-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-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-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-7 success Logs for aarch64-gcc / test (test_progs, false, 360) / test_progs on aarch64 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-13 success Logs for s390x-gcc / test (test_maps, false, 360) / test_maps on s390x 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-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-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-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-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-PR success PR summary
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-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-29 success Logs for x86_64-llvm-17 / build-release / build for x86_64 with llvm-17 and -O2 optimization
netdev/series_format success Posting correctly formatted
netdev/tree_selection success Clearly marked for bpf-next, async
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: 952 this patch: 952
netdev/build_tools success No tools touched, skip
netdev/cc_maintainers warning 7 maintainers not CCed: jolsa@kernel.org yonghong.song@linux.dev kpsingh@kernel.org song@kernel.org martin.lau@linux.dev haoluo@google.com sdf@google.com
netdev/build_clang success Errors and warnings before: 957 this patch: 957
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: 968 this patch: 968
netdev/checkpatch warning WARNING: line length of 81 exceeds 80 columns WARNING: line length of 85 exceeds 80 columns WARNING: line length of 87 exceeds 80 columns WARNING: line length of 97 exceeds 80 columns WARNING: line length of 98 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

Commit Message

Alexei Starovoitov March 5, 2024, 4:52 a.m. UTC 
From: Alexei Starovoitov <ast@kernel.org>

When open code iterators, bpf_loop or may_goto is used the following two states
are equivalent and safe to prune the search:

cur state: fp-8_w=scalar(id=3,smin=umin=smin32=umin32=2,smax=umax=smax32=umax32=11,var_off=(0x0; 0xf))
old state: fp-8_rw=scalar(id=2,smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=11,var_off=(0x0; 0xf))

In other words "exact" state match should ignore liveness and precision marks,
since open coded iterator logic didn't complete their propagation,
but range_within logic that applies to scalars, ptr_to_mem, map_value, pkt_ptr
is safe to rely on.

Avoid doing such comparison when regular infinite loop detection logic is used,
otherwise bounded loop logic will declare such "infinite loop" as false
positive. Such example is in progs/verifier_loops1.c not_an_inifinite_loop().

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 kernel/bpf/verifier.c | 39 ++++++++++++++++++++++-----------------
 1 file changed, 22 insertions(+), 17 deletions(-)

Comments

Andrii Nakryiko March 5, 2024, 7:03 p.m. UTC | #1 
On Mon, Mar 4, 2024 at 8:52 PM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> From: Alexei Starovoitov <ast@kernel.org>
>
> When open code iterators, bpf_loop or may_goto is used the following two states
> are equivalent and safe to prune the search:
>
> cur state: fp-8_w=scalar(id=3,smin=umin=smin32=umin32=2,smax=umax=smax32=umax32=11,var_off=(0x0; 0xf))
> old state: fp-8_rw=scalar(id=2,smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=11,var_off=(0x0; 0xf))
>
> In other words "exact" state match should ignore liveness and precision marks,
> since open coded iterator logic didn't complete their propagation,
> but range_within logic that applies to scalars, ptr_to_mem, map_value, pkt_ptr
> is safe to rely on.
>
> Avoid doing such comparison when regular infinite loop detection logic is used,
> otherwise bounded loop logic will declare such "infinite loop" as false
> positive. Such example is in progs/verifier_loops1.c not_an_inifinite_loop().
>
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> ---

You haven't updated stacksafe() to work with enums (the code still
assumes bool), please adjust.

pw-bot: cr

Also, I wonder if we actually need three cases. We need EXACT only for
infinite loop detection, right? I wonder if that infinite loop
detection is actually that useful in practice, I rarely encounter it
(if at all), and it constantly causes issues.

What if we just dropped infinite loop detection logic altogether and
have NOT_EXACT vs RANGE_WITHIN logic only?

>  kernel/bpf/verifier.c | 39 ++++++++++++++++++++++-----------------
>  1 file changed, 22 insertions(+), 17 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 226bb65f9c2c..74b55d5571c7 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -16254,8 +16254,8 @@ static int check_btf_info(struct bpf_verifier_env *env,
>  }
>
>  /* check %cur's range satisfies %old's */
> -static bool range_within(struct bpf_reg_state *old,
> -                        struct bpf_reg_state *cur)
> +static bool range_within(const struct bpf_reg_state *old,
> +                        const struct bpf_reg_state *cur)
>  {
>         return old->umin_value <= cur->umin_value &&
>                old->umax_value >= cur->umax_value &&
> @@ -16419,21 +16419,26 @@ static bool regs_exact(const struct bpf_reg_state *rold,
>                check_ids(rold->ref_obj_id, rcur->ref_obj_id, idmap);
>  }
>
> +enum exact_level {
> +       NOT_EXACT,
> +       EXACT,
> +       RANGE_WITHIN
> +};
> +
>  /* Returns true if (rold safe implies rcur safe) */
>  static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
> -                   struct bpf_reg_state *rcur, struct bpf_idmap *idmap, bool exact)
> +                   struct bpf_reg_state *rcur, struct bpf_idmap *idmap,
> +                   enum exact_level exact)
>  {
> -       if (exact)
> +       if (exact == EXACT)
>                 return regs_exact(rold, rcur, idmap);
>
> -       if (!(rold->live & REG_LIVE_READ))
> +       if (!(rold->live & REG_LIVE_READ) && exact != RANGE_WITHIN)

imo, `exact == NOT_EXACT` is easier to follow (we excluded EXACT above)

>                 /* explored state didn't use this */
>                 return true;
> -       if (rold->type == NOT_INIT)
> +       if (rold->type == NOT_INIT && exact != RANGE_WITHIN)

ditto

>                 /* explored state can't have used this */
>                 return true;
> -       if (rcur->type == NOT_INIT)
> -               return false;

do we need to remove this? in which case will it do the wrong thing?

>
>         /* Enforce that register types have to match exactly, including their
>          * modifiers (like PTR_MAYBE_NULL, MEM_RDONLY, etc), as a general
> @@ -16468,7 +16473,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
>                         return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 &&
>                                check_scalar_ids(rold->id, rcur->id, idmap);
>                 }
> -               if (!rold->precise)
> +               if (!rold->precise && exact != RANGE_WITHIN)

same, I think explicit `exact == NOT_EXACT` is easier to follow

>                         return true;
>                 /* Why check_ids() for scalar registers?
>                  *
> @@ -16579,7 +16584,7 @@ static struct bpf_reg_state *scalar_reg_for_stack(struct bpf_verifier_env *env,
>  }
>
>  static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,
> -                     struct bpf_func_state *cur, struct bpf_idmap *idmap, bool exact)
> +                     struct bpf_func_state *cur, struct bpf_idmap *idmap, enum exact_level exact)
>  {
>         int i, spi;
>
> @@ -16743,7 +16748,7 @@ static bool refsafe(struct bpf_func_state *old, struct bpf_func_state *cur,
>   * the current state will reach 'bpf_exit' instruction safely
>   */
>  static bool func_states_equal(struct bpf_verifier_env *env, struct bpf_func_state *old,
> -                             struct bpf_func_state *cur, bool exact)
> +                             struct bpf_func_state *cur, enum exact_level exact)
>  {
>         int i;
>
> @@ -16770,7 +16775,7 @@ static void reset_idmap_scratch(struct bpf_verifier_env *env)
>  static bool states_equal(struct bpf_verifier_env *env,
>                          struct bpf_verifier_state *old,
>                          struct bpf_verifier_state *cur,
> -                        bool exact)
> +                        enum exact_level exact)
>  {
>         int i;
>
> @@ -17144,7 +17149,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
>                          * => unsafe memory access at 11 would not be caught.
>                          */
>                         if (is_iter_next_insn(env, insn_idx)) {
> -                               if (states_equal(env, &sl->state, cur, true)) {
> +                               if (states_equal(env, &sl->state, cur, RANGE_WITHIN)) {
>                                         struct bpf_func_state *cur_frame;
>                                         struct bpf_reg_state *iter_state, *iter_reg;
>                                         int spi;
> @@ -17168,20 +17173,20 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
>                                 goto skip_inf_loop_check;
>                         }
>                         if (is_may_goto_insn(env, insn_idx)) {
> -                               if (states_equal(env, &sl->state, cur, true)) {
> +                               if (states_equal(env, &sl->state, cur, RANGE_WITHIN)) {
>                                         update_loop_entry(cur, &sl->state);
>                                         goto hit;
>                                 }
>                                 goto skip_inf_loop_check;
>                         }
>                         if (calls_callback(env, insn_idx)) {
> -                               if (states_equal(env, &sl->state, cur, true))
> +                               if (states_equal(env, &sl->state, cur, RANGE_WITHIN))
>                                         goto hit;
>                                 goto skip_inf_loop_check;
>                         }
>                         /* attempt to detect infinite loop to avoid unnecessary doomed work */
>                         if (states_maybe_looping(&sl->state, cur) &&
> -                           states_equal(env, &sl->state, cur, true) &&
> +                           states_equal(env, &sl->state, cur, EXACT) &&
>                             !iter_active_depths_differ(&sl->state, cur) &&
>                             sl->state.may_goto_cnt == cur->may_goto_cnt &&
>                             sl->state.callback_unroll_depth == cur->callback_unroll_depth) {
> @@ -17239,7 +17244,7 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
>                  */
>                 loop_entry = get_loop_entry(&sl->state);
>                 force_exact = loop_entry && loop_entry->branches > 0;
> -               if (states_equal(env, &sl->state, cur, force_exact)) {
> +               if (states_equal(env, &sl->state, cur, force_exact ? RANGE_WITHIN : NOT_EXACT)) {
>                         if (force_exact)
>                                 update_loop_entry(cur, loop_entry);
>  hit:
> --
> 2.43.0
>
Alexei Starovoitov March 5, 2024, 9:18 p.m. UTC | #2 
On Tue, Mar 5, 2024 at 11:03 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Mon, Mar 4, 2024 at 8:52 PM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> >
> > From: Alexei Starovoitov <ast@kernel.org>
> >
> > When open code iterators, bpf_loop or may_goto is used the following two states
> > are equivalent and safe to prune the search:
> >
> > cur state: fp-8_w=scalar(id=3,smin=umin=smin32=umin32=2,smax=umax=smax32=umax32=11,var_off=(0x0; 0xf))
> > old state: fp-8_rw=scalar(id=2,smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=11,var_off=(0x0; 0xf))
> >
> > In other words "exact" state match should ignore liveness and precision marks,
> > since open coded iterator logic didn't complete their propagation,
> > but range_within logic that applies to scalars, ptr_to_mem, map_value, pkt_ptr
> > is safe to rely on.
> >
> > Avoid doing such comparison when regular infinite loop detection logic is used,
> > otherwise bounded loop logic will declare such "infinite loop" as false
> > positive. Such example is in progs/verifier_loops1.c not_an_inifinite_loop().
> >
> > Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> > ---
>
> You haven't updated stacksafe() to work with enums (the code still
> assumes bool), please adjust.

great catch.

> pw-bot: cr
>
> Also, I wonder if we actually need three cases. We need EXACT only for
> infinite loop detection, right? I wonder if that infinite loop
> detection is actually that useful in practice, I rarely encounter it
> (if at all), and it constantly causes issues.
>
> What if we just dropped infinite loop detection logic altogether and
> have NOT_EXACT vs RANGE_WITHIN logic only?

The infinite loop logic is for better user experience.
With:
time ./test_verifier 145
#145/p calls: conditional call 6 OK
Summary: 1 PASSED, 0 SKIPPED, 0 FAILED

real    0m0.191s
user    0m0.001s
sys    0m0.053s

without (on prod kernel):
time ./test_verifier 145
#145/p calls: conditional call 6 FAIL
Unexpected error message!
    EXP: infinite loop detected
    RES: BPF program is too large. Processed 1000001 insn
verification time 5182443 usec
stack depth 0+0
processed 1000001 insns (limit 1000000) max_states_per_insn 4
total_states 33336 peak_states 33336 mark_read 1

real    0m5.375s
user    0m0.002s
sys    0m4.700s

I hope that eventually we can replace the 1M insn limit with
"if the verifier is making progress, keep going".
Then states_maybe_looping() will be replaced with something else.
It should address non-converging bpf_loop/open iterators
that hit 1M right now while walking the same insns over and over again.
Something like "did we visit this insn 1k times" may be enough.

> >  kernel/bpf/verifier.c | 39 ++++++++++++++++++++++-----------------
> >  1 file changed, 22 insertions(+), 17 deletions(-)
> >
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 226bb65f9c2c..74b55d5571c7 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -16254,8 +16254,8 @@ static int check_btf_info(struct bpf_verifier_env *env,
> >  }
> >
> >  /* check %cur's range satisfies %old's */
> > -static bool range_within(struct bpf_reg_state *old,
> > -                        struct bpf_reg_state *cur)
> > +static bool range_within(const struct bpf_reg_state *old,
> > +                        const struct bpf_reg_state *cur)
> >  {
> >         return old->umin_value <= cur->umin_value &&
> >                old->umax_value >= cur->umax_value &&
> > @@ -16419,21 +16419,26 @@ static bool regs_exact(const struct bpf_reg_state *rold,
> >                check_ids(rold->ref_obj_id, rcur->ref_obj_id, idmap);
> >  }
> >
> > +enum exact_level {
> > +       NOT_EXACT,
> > +       EXACT,
> > +       RANGE_WITHIN
> > +};
> > +
> >  /* Returns true if (rold safe implies rcur safe) */
> >  static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
> > -                   struct bpf_reg_state *rcur, struct bpf_idmap *idmap, bool exact)
> > +                   struct bpf_reg_state *rcur, struct bpf_idmap *idmap,
> > +                   enum exact_level exact)
> >  {
> > -       if (exact)
> > +       if (exact == EXACT)
> >                 return regs_exact(rold, rcur, idmap);
> >
> > -       if (!(rold->live & REG_LIVE_READ))
> > +       if (!(rold->live & REG_LIVE_READ) && exact != RANGE_WITHIN)
>
> imo, `exact == NOT_EXACT` is easier to follow (we excluded EXACT above)

ok.

> >                 /* explored state didn't use this */
> >                 return true;
> > -       if (rold->type == NOT_INIT)
> > +       if (rold->type == NOT_INIT && exact != RANGE_WITHIN)
>
> ditto
>
> >                 /* explored state can't have used this */
> >                 return true;
> > -       if (rcur->type == NOT_INIT)
> > -               return false;
>
> do we need to remove this? in which case will it do the wrong thing?

Yes.
Consider cur-type == rold->type == NOT_INIT exact == RANGE_WITHIN
and regsafe() will return false, but should return true via:
        default:
                return regs_exact(rold, rcur, idmap);

Having said that it's better to change above two 'if'-s to
if (rold->type == NOT_INIT) {
    if (exact == NOT_EXACT || rcur->type == NOT_INIT)
      return true;
}
to avoid doing regs_exact() for the common case.

> >
> >         /* Enforce that register types have to match exactly, including their
> >          * modifiers (like PTR_MAYBE_NULL, MEM_RDONLY, etc), as a general
> > @@ -16468,7 +16473,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
> >                         return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 &&
> >                                check_scalar_ids(rold->id, rcur->id, idmap);
> >                 }
> > -               if (!rold->precise)
> > +               if (!rold->precise && exact != RANGE_WITHIN)
>
> same, I think explicit `exact == NOT_EXACT` is easier to follow

ok
Andrii Nakryiko March 5, 2024, 9:57 p.m. UTC | #3 
On Tue, Mar 5, 2024 at 1:18 PM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Tue, Mar 5, 2024 at 11:03 AM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> >
> > On Mon, Mar 4, 2024 at 8:52 PM Alexei Starovoitov
> > <alexei.starovoitov@gmail.com> wrote:
> > >
> > > From: Alexei Starovoitov <ast@kernel.org>
> > >
> > > When open code iterators, bpf_loop or may_goto is used the following two states
> > > are equivalent and safe to prune the search:
> > >
> > > cur state: fp-8_w=scalar(id=3,smin=umin=smin32=umin32=2,smax=umax=smax32=umax32=11,var_off=(0x0; 0xf))
> > > old state: fp-8_rw=scalar(id=2,smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=11,var_off=(0x0; 0xf))
> > >
> > > In other words "exact" state match should ignore liveness and precision marks,
> > > since open coded iterator logic didn't complete their propagation,
> > > but range_within logic that applies to scalars, ptr_to_mem, map_value, pkt_ptr
> > > is safe to rely on.
> > >
> > > Avoid doing such comparison when regular infinite loop detection logic is used,
> > > otherwise bounded loop logic will declare such "infinite loop" as false
> > > positive. Such example is in progs/verifier_loops1.c not_an_inifinite_loop().
> > >
> > > Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> > > ---
> >
> > You haven't updated stacksafe() to work with enums (the code still
> > assumes bool), please adjust.
>
> great catch.
>
> > pw-bot: cr
> >
> > Also, I wonder if we actually need three cases. We need EXACT only for
> > infinite loop detection, right? I wonder if that infinite loop
> > detection is actually that useful in practice, I rarely encounter it
> > (if at all), and it constantly causes issues.
> >
> > What if we just dropped infinite loop detection logic altogether and
> > have NOT_EXACT vs RANGE_WITHIN logic only?
>
> The infinite loop logic is for better user experience.
> With:
> time ./test_verifier 145
> #145/p calls: conditional call 6 OK
> Summary: 1 PASSED, 0 SKIPPED, 0 FAILED
>
> real    0m0.191s
> user    0m0.001s
> sys    0m0.053s
>
> without (on prod kernel):
> time ./test_verifier 145
> #145/p calls: conditional call 6 FAIL
> Unexpected error message!
>     EXP: infinite loop detected
>     RES: BPF program is too large. Processed 1000001 insn
> verification time 5182443 usec
> stack depth 0+0
> processed 1000001 insns (limit 1000000) max_states_per_insn 4
> total_states 33336 peak_states 33336 mark_read 1
>
> real    0m5.375s
> user    0m0.002s
> sys    0m4.700s
>
> I hope that eventually we can replace the 1M insn limit with
> "if the verifier is making progress, keep going".
> Then states_maybe_looping() will be replaced with something else.
> It should address non-converging bpf_loop/open iterators
> that hit 1M right now while walking the same insns over and over again.
> Something like "did we visit this insn 1k times" may be enough.

Yeah, my hopes were very low for getting rid of that check, but it
always is causing problems... Alright, fine, we'll have to live with a
more complicated tri-state exactness check, unfortunately.

>
> > >  kernel/bpf/verifier.c | 39 ++++++++++++++++++++++-----------------
> > >  1 file changed, 22 insertions(+), 17 deletions(-)
> > >
> > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > index 226bb65f9c2c..74b55d5571c7 100644
> > > --- a/kernel/bpf/verifier.c
> > > +++ b/kernel/bpf/verifier.c
> > > @@ -16254,8 +16254,8 @@ static int check_btf_info(struct bpf_verifier_env *env,
> > >  }
> > >
> > >  /* check %cur's range satisfies %old's */
> > > -static bool range_within(struct bpf_reg_state *old,
> > > -                        struct bpf_reg_state *cur)
> > > +static bool range_within(const struct bpf_reg_state *old,
> > > +                        const struct bpf_reg_state *cur)
> > >  {
> > >         return old->umin_value <= cur->umin_value &&
> > >                old->umax_value >= cur->umax_value &&
> > > @@ -16419,21 +16419,26 @@ static bool regs_exact(const struct bpf_reg_state *rold,
> > >                check_ids(rold->ref_obj_id, rcur->ref_obj_id, idmap);
> > >  }
> > >
> > > +enum exact_level {
> > > +       NOT_EXACT,
> > > +       EXACT,
> > > +       RANGE_WITHIN
> > > +};
> > > +
> > >  /* Returns true if (rold safe implies rcur safe) */
> > >  static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
> > > -                   struct bpf_reg_state *rcur, struct bpf_idmap *idmap, bool exact)
> > > +                   struct bpf_reg_state *rcur, struct bpf_idmap *idmap,
> > > +                   enum exact_level exact)
> > >  {
> > > -       if (exact)
> > > +       if (exact == EXACT)
> > >                 return regs_exact(rold, rcur, idmap);
> > >
> > > -       if (!(rold->live & REG_LIVE_READ))
> > > +       if (!(rold->live & REG_LIVE_READ) && exact != RANGE_WITHIN)
> >
> > imo, `exact == NOT_EXACT` is easier to follow (we excluded EXACT above)
>
> ok.
>
> > >                 /* explored state didn't use this */
> > >                 return true;
> > > -       if (rold->type == NOT_INIT)
> > > +       if (rold->type == NOT_INIT && exact != RANGE_WITHIN)
> >
> > ditto
> >
> > >                 /* explored state can't have used this */
> > >                 return true;
> > > -       if (rcur->type == NOT_INIT)
> > > -               return false;
> >
> > do we need to remove this? in which case will it do the wrong thing?
>
> Yes.
> Consider cur-type == rold->type == NOT_INIT exact == RANGE_WITHIN
> and regsafe() will return false, but should return true via:
>         default:
>                 return regs_exact(rold, rcur, idmap);

oh, very subtle and error-prone, so yeah, I like the explicit check below more

>
> Having said that it's better to change above two 'if'-s to
> if (rold->type == NOT_INIT) {
>     if (exact == NOT_EXACT || rcur->type == NOT_INIT)
>       return true;
> }
> to avoid doing regs_exact() for the common case.

sure, give it a try, but I got to say that it is now quite hard to
follow the logic with the tri-state "exactness"

>
> > >
> > >         /* Enforce that register types have to match exactly, including their
> > >          * modifiers (like PTR_MAYBE_NULL, MEM_RDONLY, etc), as a general
> > > @@ -16468,7 +16473,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
> > >                         return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 &&
> > >                                check_scalar_ids(rold->id, rcur->id, idmap);
> > >                 }
> > > -               if (!rold->precise)
> > > +               if (!rold->precise && exact != RANGE_WITHIN)
> >
> > same, I think explicit `exact == NOT_EXACT` is easier to follow
>
> ok
diff mbox series

Patch

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 226bb65f9c2c..74b55d5571c7 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -16254,8 +16254,8 @@  static int check_btf_info(struct bpf_verifier_env *env,
 }
 
 /* check %cur's range satisfies %old's */
-static bool range_within(struct bpf_reg_state *old,
-			 struct bpf_reg_state *cur)
+static bool range_within(const struct bpf_reg_state *old,
+			 const struct bpf_reg_state *cur)
 {
 	return old->umin_value <= cur->umin_value &&
 	       old->umax_value >= cur->umax_value &&
@@ -16419,21 +16419,26 @@  static bool regs_exact(const struct bpf_reg_state *rold,
 	       check_ids(rold->ref_obj_id, rcur->ref_obj_id, idmap);
 }
 
+enum exact_level {
+	NOT_EXACT,
+	EXACT,
+	RANGE_WITHIN
+};
+
 /* Returns true if (rold safe implies rcur safe) */
 static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
-		    struct bpf_reg_state *rcur, struct bpf_idmap *idmap, bool exact)
+		    struct bpf_reg_state *rcur, struct bpf_idmap *idmap,
+		    enum exact_level exact)
 {
-	if (exact)
+	if (exact == EXACT)
 		return regs_exact(rold, rcur, idmap);
 
-	if (!(rold->live & REG_LIVE_READ))
+	if (!(rold->live & REG_LIVE_READ) && exact != RANGE_WITHIN)
 		/* explored state didn't use this */
 		return true;
-	if (rold->type == NOT_INIT)
+	if (rold->type == NOT_INIT && exact != RANGE_WITHIN)
 		/* explored state can't have used this */
 		return true;
-	if (rcur->type == NOT_INIT)
-		return false;
 
 	/* Enforce that register types have to match exactly, including their
 	 * modifiers (like PTR_MAYBE_NULL, MEM_RDONLY, etc), as a general
@@ -16468,7 +16473,7 @@  static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 			return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 &&
 			       check_scalar_ids(rold->id, rcur->id, idmap);
 		}
-		if (!rold->precise)
+		if (!rold->precise && exact != RANGE_WITHIN)
 			return true;
 		/* Why check_ids() for scalar registers?
 		 *
@@ -16579,7 +16584,7 @@  static struct bpf_reg_state *scalar_reg_for_stack(struct bpf_verifier_env *env,
 }
 
 static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,
-		      struct bpf_func_state *cur, struct bpf_idmap *idmap, bool exact)
+		      struct bpf_func_state *cur, struct bpf_idmap *idmap, enum exact_level exact)
 {
 	int i, spi;
 
@@ -16743,7 +16748,7 @@  static bool refsafe(struct bpf_func_state *old, struct bpf_func_state *cur,
  * the current state will reach 'bpf_exit' instruction safely
  */
 static bool func_states_equal(struct bpf_verifier_env *env, struct bpf_func_state *old,
-			      struct bpf_func_state *cur, bool exact)
+			      struct bpf_func_state *cur, enum exact_level exact)
 {
 	int i;
 
@@ -16770,7 +16775,7 @@  static void reset_idmap_scratch(struct bpf_verifier_env *env)
 static bool states_equal(struct bpf_verifier_env *env,
 			 struct bpf_verifier_state *old,
 			 struct bpf_verifier_state *cur,
-			 bool exact)
+			 enum exact_level exact)
 {
 	int i;
 
@@ -17144,7 +17149,7 @@  static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 			 * => unsafe memory access at 11 would not be caught.
 			 */
 			if (is_iter_next_insn(env, insn_idx)) {
-				if (states_equal(env, &sl->state, cur, true)) {
+				if (states_equal(env, &sl->state, cur, RANGE_WITHIN)) {
 					struct bpf_func_state *cur_frame;
 					struct bpf_reg_state *iter_state, *iter_reg;
 					int spi;
@@ -17168,20 +17173,20 @@  static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 				goto skip_inf_loop_check;
 			}
 			if (is_may_goto_insn(env, insn_idx)) {
-				if (states_equal(env, &sl->state, cur, true)) {
+				if (states_equal(env, &sl->state, cur, RANGE_WITHIN)) {
 					update_loop_entry(cur, &sl->state);
 					goto hit;
 				}
 				goto skip_inf_loop_check;
 			}
 			if (calls_callback(env, insn_idx)) {
-				if (states_equal(env, &sl->state, cur, true))
+				if (states_equal(env, &sl->state, cur, RANGE_WITHIN))
 					goto hit;
 				goto skip_inf_loop_check;
 			}
 			/* attempt to detect infinite loop to avoid unnecessary doomed work */
 			if (states_maybe_looping(&sl->state, cur) &&
-			    states_equal(env, &sl->state, cur, true) &&
+			    states_equal(env, &sl->state, cur, EXACT) &&
 			    !iter_active_depths_differ(&sl->state, cur) &&
 			    sl->state.may_goto_cnt == cur->may_goto_cnt &&
 			    sl->state.callback_unroll_depth == cur->callback_unroll_depth) {
@@ -17239,7 +17244,7 @@  static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 		 */
 		loop_entry = get_loop_entry(&sl->state);
 		force_exact = loop_entry && loop_entry->branches > 0;
-		if (states_equal(env, &sl->state, cur, force_exact)) {
+		if (states_equal(env, &sl->state, cur, force_exact ? RANGE_WITHIN : NOT_EXACT)) {
 			if (force_exact)
 				update_loop_entry(cur, loop_entry);
 hit: