Re: [PATCH v4 bpf-next 3/7] bpf: enhance subregister bounds deduction logic

[Shung-Hsi Yu <shung-hsi.yu@suse.com>]

On Mon, Oct 23, 2023 at 09:23:57AM -0700, Andrii Nakryiko wrote:
> On Sun, Oct 22, 2023 at 8:57 PM Shung-Hsi Yu <shung-hsi.yu@suse.com> wrote:
> >
> > On Mon, Oct 23, 2023 at 11:20:46AM +0800, Shung-Hsi Yu wrote:
> > > On Sun, Oct 22, 2023 at 01:57:39PM -0700, Andrii Nakryiko wrote:
> > > > Add handling of a bunch of possible cases which allows deducing extra
> > > > information about subregister bounds, both u32 and s32, from full register
> > > > u64/s64 bounds.
> > > >
> > > > Also add smin32/smax32 bounds derivation from corresponding umin32/umax32
> > > > bounds, similar to what we did with smin/smax from umin/umax derivation in
> > > > previous patch.
> > > >
> > > > Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
> > > >
> > > > ---
> > > >  kernel/bpf/verifier.c | 52 +++++++++++++++++++++++++++++++++++++++++++
> > > >  1 file changed, 52 insertions(+)
> > > >
> > > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > > index 885dd4a2ff3a..3fc9bd5e72b8 100644
> > > > --- a/kernel/bpf/verifier.c
> > > > +++ b/kernel/bpf/verifier.c
> > > > @@ -2130,6 +2130,58 @@ static void __update_reg_bounds(struct bpf_reg_state *reg)
> > > >  /* Uses signed min/max values to inform unsigned, and vice-versa */
> > > >  static void __reg32_deduce_bounds(struct bpf_reg_state *reg)
> > > >  {
> > > > +   /* if upper 32 bits of u64/s64 range don't change,
> > > > +    * we can use lower 32 bits to improve our u32/s32 boundaries
> > > > +    */
> > > > +   if ((reg->umin_value >> 32) == (reg->umax_value >> 32)) {
> > > > +           /* u64 to u32 casting preserves validity of low 32 bits as
> > > > +            * a range, if upper 32 bits are the same
> > > > +            */
> > > > +           reg->u32_min_value = max_t(u32, reg->u32_min_value, (u32)reg->umin_value);
> > > > +           reg->u32_max_value = min_t(u32, reg->u32_max_value, (u32)reg->umax_value);
> > > > +
> > > > +           if ((s32)reg->umin_value <= (s32)reg->umax_value) {
> > > > +                   reg->s32_min_value = max_t(s32, reg->s32_min_value, (s32)reg->umin_value);
> > > > +                   reg->s32_max_value = min_t(s32, reg->s32_max_value, (s32)reg->umax_value);
> > > > +           }
> > > > +   }
> > > > +   if ((reg->smin_value >> 32) == (reg->smax_value >> 32)) {
> > > > +           /* low 32 bits should form a proper u32 range */
> > > > +           if ((u32)reg->smin_value <= (u32)reg->smax_value) {
> > > > +                   reg->u32_min_value = max_t(u32, reg->u32_min_value, (u32)reg->smin_value);
> > > > +                   reg->u32_max_value = min_t(u32, reg->u32_max_value, (u32)reg->smax_value);
> > > > +           }
> > > > +           /* low 32 bits should form a proper s32 range */
> > > > +           if ((s32)reg->smin_value <= (s32)reg->smax_value) {
> > > > +                   reg->s32_min_value = max_t(s32, reg->s32_min_value, (s32)reg->smin_value);
> > > > +                   reg->s32_max_value = min_t(s32, reg->s32_max_value, (s32)reg->smax_value);
> > > > +           }
> > > > +   }
> > > > +   /* Special case where upper bits form a small sequence of two
> > > > +    * sequential numbers (in 32-bit unsigned space, so 0xffffffff to
> > > > +    * 0x00000000 is also valid), while lower bits form a proper s32 range
> > > > +    * going from negative numbers to positive numbers.
> > > > +    * E.g.: [0xfffffff0ffffff00; 0xfffffff100000010]. Iterating
> > > > +    * over full 64-bit numbers range will form a proper [-16, 16]
> > > > +    * ([0xffffff00; 0x00000010]) range in its lower 32 bits.
> > > > +    */
> >
> > ... [graph removed]
> 
> Yeah, tbh, the graphs above weren't really all that helpful, rather
> more confusing. But I think you got the point correctly, that we are
> stitching two s32 ranges, if we can. And we can if upper 32 bits are
> two consecutive numbers and lower 32-bits goes from negative to
> positive (as s32).

Alright, graph removed. FWIW I think "stitching two s32 ranges together" is
a great way to put it concisely to give some intuitive sense, it'd be nice
if it can be incorporated into the above comment.

> > > > +   if ((u32)(reg->umin_value >> 32) + 1 == (u32)(reg->umax_value >> 32) &&
> > > > +       (s32)reg->umin_value < 0 && (s32)reg->umax_value >= 0) {
> > > > +           reg->s32_min_value = max_t(s32, reg->s32_min_value, (s32)reg->umin_value);
> > > > +           reg->s32_max_value = min_t(s32, reg->s32_max_value, (s32)reg->umax_value);
> > > > +   }
> > > > +   if ((u32)(reg->smin_value >> 32) + 1 == (u32)(reg->smax_value >> 32) &&
> > > > +       (s32)reg->smin_value < 0 && (s32)reg->smax_value >= 0) {
> > > > +           reg->s32_min_value = max_t(s32, reg->s32_min_value, (s32)reg->smin_value);
> > > > +           reg->s32_max_value = min_t(s32, reg->s32_max_value, (s32)reg->smax_value);
> > > > +   }
> > > > +   /* if u32 range forms a valid s32 range (due to matching sign bit),
> > > > +    * try to learn from that
> > > > +    */
> > > > +   if ((s32)reg->u32_min_value <= (s32)reg->u32_max_value) {
> > > > +           reg->s32_min_value = max_t(s32, reg->s32_min_value, reg->u32_min_value);
> > > > +           reg->s32_max_value = min_t(s32, reg->s32_max_value, reg->u32_max_value);
> > > > +   }
> > > >     /* Learn sign from signed bounds.
> > > >      * If we cannot cross the sign boundary, then signed and unsigned bounds
> > > >      * are the same, so combine.  This works even in the negative case, e.g.
> > > > --
> > > > 2.34.1
> > > >