Re: [PATCH v1 2/3] bpf: verifier: Simplify register sign extension with tnum_scast

[Eduard Zingerman <eddyz87@gmail.com>]

On Tue, 2025-12-02 at 12:53 +0200, Dimitar Kanaliev wrote:
> On Tue, Dec 2, 2025 at 1:50 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > 
> > On Tue, 2025-11-25 at 14:56 +0200, Dimitar Kanaliev wrote:
> > 
> > [...]
> > 
> > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > index 766695491bc5..c9a6bf85b4ad 100644
> > > --- a/kernel/bpf/verifier.c
> > > +++ b/kernel/bpf/verifier.c
> > > @@ -6876,147 +6876,57 @@ static void coerce_reg_to_size(struct bpf_reg_state *reg, int size)
> > >       reg_bounds_sync(reg);
> > >  }
> > > 
> > > -static void set_sext64_default_val(struct bpf_reg_state *reg, int size)
> > > -{
> > > -     if (size == 1) {
> > > -             reg->smin_value = reg->s32_min_value = S8_MIN;
> > > -             reg->smax_value = reg->s32_max_value = S8_MAX;
> > > -     } else if (size == 2) {
> > > -             reg->smin_value = reg->s32_min_value = S16_MIN;
> > > -             reg->smax_value = reg->s32_max_value = S16_MAX;
> > > -     } else {
> > > -             /* size == 4 */
> > > -             reg->smin_value = reg->s32_min_value = S32_MIN;
> > > -             reg->smax_value = reg->s32_max_value = S32_MAX;
> > > -     }
> > > -     reg->umin_value = reg->u32_min_value = 0;
> > > -     reg->umax_value = U64_MAX;
> > > -     reg->u32_max_value = U32_MAX;
> > > -     reg->var_off = tnum_unknown;
> > > -}
> > > -
> > >  static void coerce_reg_to_size_sx(struct bpf_reg_state *reg, int size)
> > >  {
> > > -     s64 init_s64_max, init_s64_min, s64_max, s64_min, u64_cval;
> > > -     u64 top_smax_value, top_smin_value;
> > > -     u64 num_bits = size * 8;
> > > +     s64 smin_value, smax_value;
> > > 
> > > -     if (tnum_is_const(reg->var_off)) {
> > > -             u64_cval = reg->var_off.value;
> > > -             if (size == 1)
> > > -                     reg->var_off = tnum_const((s8)u64_cval);
> > > -             else if (size == 2)
> > > -                     reg->var_off = tnum_const((s16)u64_cval);
> > > -             else
> > > -                     /* size == 4 */
> > > -                     reg->var_off = tnum_const((s32)u64_cval);
> > > -
> > > -             u64_cval = reg->var_off.value;
> > > -             reg->smax_value = reg->smin_value = u64_cval;
> > > -             reg->umax_value = reg->umin_value = u64_cval;
> > > -             reg->s32_max_value = reg->s32_min_value = u64_cval;
> > > -             reg->u32_max_value = reg->u32_min_value = u64_cval;
> > > +     if (size >= 8)
> > >               return;
> > > -     }
> > > 
> > > -     top_smax_value = ((u64)reg->smax_value >> num_bits) << num_bits;
> > > -     top_smin_value = ((u64)reg->smin_value >> num_bits) << num_bits;
> > > +     reg->var_off = tnum_scast(reg->var_off, size);
> > > 
> > > -     if (top_smax_value != top_smin_value)
> > > -             goto out;
> > > +     smin_value = -(1LL << (size * 8 - 1));
> > > +     smax_value = (1LL << (size * 8 - 1)) - 1;
> > > 
> > > -     /* find the s64_min and s64_min after sign extension */
> > > -     if (size == 1) {
> > > -             init_s64_max = (s8)reg->smax_value;
> > > -             init_s64_min = (s8)reg->smin_value;
> > > -     } else if (size == 2) {
> > > -             init_s64_max = (s16)reg->smax_value;
> > > -             init_s64_min = (s16)reg->smin_value;
> > > -     } else {
> > > -             init_s64_max = (s32)reg->smax_value;
> > > -             init_s64_min = (s32)reg->smin_value;
> > > -     }
> > > -
> > > -     s64_max = max(init_s64_max, init_s64_min);
> > > -     s64_min = min(init_s64_max, init_s64_min);
> > > +     reg->smin_value = smin_value;
> > > +     reg->smax_value = smax_value;
> > > 
> > > -     /* both of s64_max/s64_min positive or negative */
> > > -     if ((s64_max >= 0) == (s64_min >= 0)) {
> > > -             reg->s32_min_value = reg->smin_value = s64_min;
> > > -             reg->s32_max_value = reg->smax_value = s64_max;
> > > -             reg->u32_min_value = reg->umin_value = s64_min;
> > > -             reg->u32_max_value = reg->umax_value = s64_max;
> > > -             reg->var_off = tnum_range(s64_min, s64_max);
> > > -             return;
> > > -     }
> > > +     reg->s32_min_value = (s32)smin_value;
> > > +     reg->s32_max_value = (s32)smax_value;
> > > 
> > > -out:
> > > -     set_sext64_default_val(reg, size);
> > > -}
> > 
> > Assume that size == 1, s64_min = 0b000, s64_max == 0b100.
> > This corresponds to tnum with value == 0b000 and mask == 0b111.
> > Old algorithm computes more precise range in this situation.
> > Old:
> > 
> >   0: (85) call bpf_get_prandom_u32#7    ; R0=scalar()
> >   1: (25) if r0 > 0x4 goto pc+2         ; R0=scalar(smin=smin32=0,smax=umax=smax32=umax32=4,var_off=(0x0; 0x7))
> >   2: (7b) *(u64 *)(r10 -8) = r0         ; R0=scalar(id=1,smin=smin32=0,smax=umax=smax32=umax32=4,var_off=(0x0; 0x7)) ...
> >   3: (91) r0 = *(s8 *)(r10 -8)          ; R0=scalar(id=1,smin=smin32=0,smax=umax=smax32=umax32=4,var_off=(0x0; 0x7)) ...
> >   4: (b7) r0 = 0                        ; R0=0
> >   5: (95) exit
> > 
> > New:
> > 
> >   0: (85) call bpf_get_prandom_u32#7    ; R0=scalar()
> >   1: (25) if r0 > 0x4 goto pc+2         ; R0=scalar(smin=smin32=0,smax=umax=smax32=umax32=4,var_off=(0x0; 0x7))
> >   2: (7b) *(u64 *)(r10 -8) = r0         ; R0=scalar(id=1,smin=smin32=0,smax=umax=smax32=umax32=4,var_off=(0x0; 0x7)) ...
> >   3: (91) r0 = *(s8 *)(r10 -8)          ; R0=scalar(id=1,smin=smin32=0,smax=umax=smax32=umax32=7,var_off=(0x0; 0x7)) ...
> >   4: (b7) r0 = 0                        ; R0=0
> >   5: (95) exit
> > 
> > Note that range for R0 at (3) is 0..4 for old algorithm and 0..7 for
> > new algorithm.
> > 
> > Can we keep both algorithms by e.g. replacing set_sext64_default_val()
> > implementation with tnum_scast() adding tnum_scast() in
> > coerce_reg_to_size_sx()?
> > 
> > In general, for such kinds of patch-sets it is interesting to see how
> > much precision is gained/lost with the change. It shouldn't be hard to
> > collect such data for e.g. complete s8 range by writing a small
> > user-space program that enumerates the s8 x s8 range and applies both
> > old an new range computations.
> > 
> > [...]
> 
> I was mostly focused on preserving the info from tnum for sparse ranges, so
> I kind of forgot about continuous ranges entirely.
> As per your suggestion, I plucked out anything relevant from the kernel,
> and compared the smax / smin values for the entire -1024,1024 range in a
> loop, like so:
> 
>   struct bpf_reg_state r_old, r_new;
> 
>   init_reg(&r_old, start, end);
>   r_new = r_old;
> 
>   coerce_reg_to_size_sx_old(&r_old, size);
>   coerce_reg_to_size_sx_new(&r_new, size);
> 
>   s64 range_old = r_old.smax_value - r_old.smin_value;
>   s64 range_new = r_new.smax_value - r_new.smin_value;
> 
>   if (range_old < range_new) { ...
> 
> In these continous ranges, the old implementation is much better:
> 
>   [-1024, 1024]:
>   Old Better: 128016
>   New Better: 0
>   Equal: 1972209
> 
> So I endeed up drafting this:
> 
>   static void coerce_reg_to_size_sx(struct bpf_reg_state *reg, int size)
>   {
>     s64 smin_value, smax_value;
>     u64 num_bits = size * 8;
>     u64 top_smax_value, top_smin_value;
> 
>     reg->var_off = tnum_scast(reg->var_off, size);
> 
>     top_smax_value = ((u64)reg->smax_value >> num_bits) << num_bits;
>     top_smin_value = ((u64)reg->smin_value >> num_bits) << num_bits;
> 
>     if (top_smax_value == top_smin_value) {
>             if (size == 1) {
>                 smin_value = (s8)reg->smin_value;
>                 smax_value = (s8)reg->smax_value;
>             } else if (size == 2) {
>                 smin_value = (s16)reg->smin_value;
>                 smax_value = (s16)reg->smax_value;
>             } else {
>                 smin_value = (s32)reg->smin_value;
>                 smax_value = (s32)reg->smax_value;
>             }
>         } else {
>             smin_value = -(1LL << (num_bits - 1));
>             smax_value = (1LL << (num_bits - 1)) - 1;
>         }

The current implementation has the following part:

         s64_max = max(init_s64_max, init_s64_min);
         s64_min = min(init_s64_max, init_s64_min);

And I think this part is necessary. E.g. consider that
smin_value==0x00 and smax_value=0x80, then with suggested
implementation:

  clang-repl> #include <stdio.h>
  clang-repl> printf("%ld\n", (long)(char)(0x80UL));
  -128

Sign of the smin_value will be positive, while sign of the smax_value
will become negative.

When respining for v2, could you please also provide a link to a
repository with test harness you use to check range [-1024,1024]?
(E.g. push it to the github).

> 
>         reg->smin_value = smin_value;
>         reg->smax_value = smax_value;
> 
>         reg->umin_value = 0;
>         reg->umax_value = U64_MAX;
> 
>         reg->s32_min_value = (s32)smin_value;
>         reg->s32_max_value = (s32)smax_value;
>         reg->u32_min_value = 0;
>         reg->u32_max_value = U32_MAX;
> 
>         __update_reg_bounds(reg);
> }
> 
> I'm trying to always perform tnum_scast in order to preserve bitwise
> info, but attempt to use the old numeric logic first. If the range fits
> into the target size, we preserve the existing numeric bounds. If not, we
> fall back to the type limits and let __update_reg_bounds reconstruct the
> range from var_off. The imeplementation is similar for the subreg variant.
> 
> Rerunning the comparison for the same range looks much better, we should be
> consistently seeing precision gains in the cases where the original
> implementation bails out via goto:
> 
>   [-1024, 1024]:
>   Old Better: 0
>   New Better: 131072
>   Equal: 1969153
> 
> I also went through the CI, the existing selftest in the series still
> covers the change.
> 
> wdyt?