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@xxxxxxxxxxxxxx/ [1]
> Co-developed-by: Eduard Zingerman <eddyz87@xxxxxxxxx>
> Signed-off-by: Eduard Zingerman <eddyz87@xxxxxxxxx>
> Signed-off-by: Paul Chaignon <paul.chaignon@xxxxxxxxx>
> ---
Acked-by: Eduard Zingerman <eddyz87@xxxxxxxxx>
[...]
