Re: [PATCH v5 bpf-next 19/23] bpf: generalize is_scalar_branch_taken() logic

Andrii Nakryiko
2023-10-31T18:02:12Z

On Tue, Oct 31, 2023 at 9:35 AM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Mon, Oct 30, 2023 at 11:12 PM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> >
> > On Mon, Oct 30, 2023 at 7:12 PM Alexei Starovoitov
> > <alexei.starovoitov@gmail.com> wrote:
> > >
> > > On Fri, Oct 27, 2023 at 11:13:42AM -0700, Andrii Nakryiko wrote:
> > > > Generalize is_branch_taken logic for SCALAR_VALUE register to handle
> > > > cases when both registers are not constants. Previously supported
> > > > <range> vs <scalar> cases are a natural subset of more generic <range>
> > > > vs <range> set of cases.
> > > >
> > > > Generalized logic relies on straightforward segment intersection checks.
> > > >
> > > > Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
> > > > ---
> > > > kernel/bpf/verifier.c | 104 ++++++++++++++++++++++++++----------------
> > > > 1 file changed, 64 insertions(+), 40 deletions(-)
> > > >
> > > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > > index 4c974296127b..f18a8247e5e2 100644
> > > > --- a/kernel/bpf/verifier.c
> > > > +++ b/kernel/bpf/verifier.c
> > > > @@ -14189,82 +14189,105 @@ static int is_scalar_branch_taken(struct bpf_reg_state *reg1, struct bpf_reg_sta
> > > > u8 opcode, bool is_jmp32)
> > > > {
> > > > struct tnum t1 = is_jmp32 ? tnum_subreg(reg1->var_off) : reg1->var_off;
> > > > + struct tnum t2 = is_jmp32 ? tnum_subreg(reg2->var_off) : reg2->var_off;
> > > > u64 umin1 = is_jmp32 ? (u64)reg1->u32_min_value : reg1->umin_value;
> > > > u64 umax1 = is_jmp32 ? (u64)reg1->u32_max_value : reg1->umax_value;
> > > > s64 smin1 = is_jmp32 ? (s64)reg1->s32_min_value : reg1->smin_value;
> > > > s64 smax1 = is_jmp32 ? (s64)reg1->s32_max_value : reg1->smax_value;
> > > > - u64 val = is_jmp32 ? (u32)tnum_subreg(reg2->var_off).value : reg2->var_off.value;
> > > > - s64 sval = is_jmp32 ? (s32)val : (s64)val;
> > > > + u64 umin2 = is_jmp32 ? (u64)reg2->u32_min_value : reg2->umin_value;
> > > > + u64 umax2 = is_jmp32 ? (u64)reg2->u32_max_value : reg2->umax_value;
> > > > + s64 smin2 = is_jmp32 ? (s64)reg2->s32_min_value : reg2->smin_value;
> > > > + s64 smax2 = is_jmp32 ? (s64)reg2->s32_max_value : reg2->smax_value;
> > > >
> > > > switch (opcode) {
> > > > case BPF_JEQ:
> > > > - if (tnum_is_const(t1))
> > > > - return !!tnum_equals_const(t1, val);
> > > > - else if (val < umin1 || val > umax1)
> > > > + /* const tnums */
> > > > + if (tnum_is_const(t1) && tnum_is_const(t2))
> > > > + return t1.value == t2.value;
> > > > + /* const ranges */
> > > > + if (umin1 == umax1 && umin2 == umax2)
> > > > + return umin1 == umin2;
> > >
> > > I don't follow this logic.
> > > umin1 == umax1 means that it's a single constant and
> > > it should have been handled by earlier tnum_is_const check.
> >
> > I think you follow the logic, you just think it's redundant. Yes, it's
> > basically the same as
> >
> > if (tnum_is_const(t1) && tnum_is_const(t2))
> > return t1.value == t2.value;
> >
> > but based on ranges. I didn't feel comfortable to assume that if umin1
> > == umax1 then tnum_is_const(t1) will always be true. At worst we'll
> > perform one redundant check.
> >
> > In short, I don't trust tnum to be as precise as umin/umax and other ranges.
> >
> > >
> > > > + if (smin1 == smax1 && smin2 == smax2)
> > > > + return umin1 == umin2;
> > >
> > > here it's even more confusing. smin == smax -> singel const,
> > > but then compare umin1 with umin2 ?!
> >
> > Eagle eyes! Typo, sorry :( it should be `smin1 == smin2`, of course.
> >
> > What saves us is reg_bounds_sync(), and if we have umin1 == umax1 then
> > we'll have also smin1 == smax1 == umin1 == umax1 (and corresponding
> > relation for second register). But I fixed these typos in both BPF_JEQ
> > and BPF_JNE branches.
>
> Not just 'saves us'. The tnum <-> bounds sync is mandatory.
> I think we have a test where a function returns [-errno, 0]
> and then we do if (ret < 0) check. At this point the reg has
> to be tnum_is_const and zero.
> So if smin1 == smax1 == umin1 == umax1 it should be tnum_is_const.
> Otherwise it's a bug in sync logic.
> I think instead of doing redundant and confusing check may be
> add WARN either here or in sync logic to make sure it's all good ?

Ok, let's add it as part of register state sanity checks we discussed
on another patch. I'll drop the checks and will re-run all the test to
make sure we are not missing anything.