Re: [PATCH bpf-next v3 5/5] bpf: Add third round of bounds deduction

[Eduard Zingerman <eddyz87@gmail.com>]

On Fri, 2025-07-25 at 21:08 +0200, Paul Chaignon wrote:
> Commit d7f008738171 ("bpf: try harder to deduce register bounds from
> different numeric domains") added a second call to __reg_deduce_bounds
> in reg_bounds_sync because a single call wasn't enough to converge to a
> fixed point in terms of register bounds.
> 
> With patch "bpf: Improve bounds when s64 crosses sign boundary" from
> this series, Eduard noticed that calling __reg_deduce_bounds twice isn't
> enough anymore to converge. The first selftest added in "selftests/bpf:
> Test cross-sign 64bits range refinement" highlights the need for a third
> call to __reg_deduce_bounds. After instruction 7, reg_bounds_sync
> performs the following bounds deduction:
> 
>   reg_bounds_sync entry:          scalar(smin=-655,smax=0xeffffeee,smin32=-783,smax32=-146)
>   __update_reg_bounds:            scalar(smin=-655,smax=0xeffffeee,smin32=-783,smax32=-146)
>   __reg_deduce_bounds:
>       __reg32_deduce_bounds:      scalar(smin=-655,smax=0xeffffeee,smin32=-783,smax32=-146,umin32=0xfffffcf1,umax32=0xffffff6e)
>       __reg64_deduce_bounds:      scalar(smin=-655,smax=0xeffffeee,smin32=-783,smax32=-146,umin32=0xfffffcf1,umax32=0xffffff6e)
>       __reg_deduce_mixed_bounds:  scalar(smin=-655,smax=0xeffffeee,umin=umin32=0xfffffcf1,umax=0xffffffffffffff6e,smin32=-783,smax32=-146,umax32=0xffffff6e)
>   __reg_deduce_bounds:
>       __reg32_deduce_bounds:      scalar(smin=-655,smax=0xeffffeee,umin=umin32=0xfffffcf1,umax=0xffffffffffffff6e,smin32=-783,smax32=-146,umax32=0xffffff6e)
>       __reg64_deduce_bounds:      scalar(smin=-655,smax=smax32=-146,umin=0xfffffffffffffd71,umax=0xffffffffffffff6e,smin32=-783,umin32=0xfffffcf1,umax32=0xffffff6e)
>       __reg_deduce_mixed_bounds:  scalar(smin=-655,smax=smax32=-146,umin=0xfffffffffffffd71,umax=0xffffffffffffff6e,smin32=-783,umin32=0xfffffcf1,umax32=0xffffff6e)
>   __reg_bound_offset:             scalar(smin=-655,smax=smax32=-146,umin=0xfffffffffffffd71,umax=0xffffffffffffff6e,smin32=-783,umin32=0xfffffcf1,umax32=0xffffff6e,var_off=(0xfffffffffffffc00; 0x3ff))
>   __update_reg_bounds:            scalar(smin=-655,smax=smax32=-146,umin=0xfffffffffffffd71,umax=0xffffffffffffff6e,smin32=-783,umin32=0xfffffcf1,umax32=0xffffff6e,var_off=(0xfffffffffffffc00; 0x3ff))
> 
> In particular, notice how:
> 1. In the first call to __reg_deduce_bounds, __reg32_deduce_bounds
>    learns new u32 bounds.
> 2. __reg64_deduce_bounds is unable to improve bounds at this point.
> 3. __reg_deduce_mixed_bounds derives new u64 bounds from the u32 bounds.
> 4. In the second call to __reg_deduce_bounds, __reg64_deduce_bounds
>    improves the smax and umin bounds thanks to patch "bpf: Improve
>    bounds when s64 crosses sign boundary" from this series.
> 5. Subsequent functions are unable to improve the ranges further (only
>    tnums). Yet, a better smin32 bound could be learned from the smin
>    bound.
> 
> __reg32_deduce_bounds is able to improve smin32 from smin, but for that
> we need a third call to __reg_deduce_bounds.
> 
> As discussed in [1], there may be a better way to organize the deduction
> rules to learn the same information with less calls to the same
> functions. Such an optimization requires further analysis and is
> orthogonal to the present patchset.
> 
> Link: https://lore.kernel.org/bpf/aIKtSK9LjQXB8FLY@mail.gmail.com/ [1]
> Co-developed-by: Eduard Zingerman <eddyz87@gmail.com>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> Signed-off-by: Paul Chaignon <paul.chaignon@gmail.com>
> ---

Acked-by: Eduard Zingerman <eddyz87@gmail.com>

[...]