Re: [PATCH bpf-next v1 1/2] bpf: refine u32/s32 bounds when ranges cross min/max boundary

["Emil Tsalapatis" <emil@etsalapatis.com>]

On Thu Mar 5, 2026 at 6:09 AM EST, Eduard Zingerman wrote:
> Same as in __reg64_deduce_bounds(), refine s32/u32 ranges
> in __reg32_deduce_bounds() in the following situations:
Nit: Can we add a cover letter since this is a 2-patch series?

Also, can we explicitly state the condition: IIUC it's: "When
the signed and unsigned ranges of a register partially overlap
on an entirely (signed) positive of (signed) negative interval".
This helps with the ASCII and also covers the question "what happens
when the ranges overlap in two places" - nothing, we don't refine
the register's bounds in that case, as noted in __reg64_deduce_bounds.

>
> 0                                                   U32_MAX
> |  [xxxxxxxxxxxxxx u32 range xxxxxxxxxxxxxx]              |
> |----------------------------|----------------------------|
> |xxxxx s32 range xxxxxxxxx]                       [xxxxxxx|
> 0                     S32_MAX S32_MIN                    -1
>
> 0                                                   U32_MAX
> |              [xxxxxxxxxxxxxx u32 range xxxxxxxxxxxxxx]  |
> |----------------------------|----------------------------|
> |xxxxxxxxx]                       [xxxxxxxxxxxx s32 range |
> 0                     S32_MAX S32_MIN                    -1
>
> This helps for e.g. consider the following program:
>
>    call %[bpf_get_prandom_u32];
>    w0 &= 0xffffffff;
>    if w0 < 0x3 goto 1f;    // on fall-through u32 range [3..U32_MAX]
>    if w0 s> 0x1 goto 1f;   // on fall-through s32 range [S32_MIN..1]
>    if w0 s< 0x0 goto 1f;   // range can be narrowed to  [S32_MIN..-1]
>    r10 = 0;
> 1: ...;
>
> The reg_bounds.c selftest is updated to incorporate identical logic,
> refinement based on non-overflowing range halves:
>
>   ((x ∩ [0, smax]) ∩ (y ∩ [0, smax])) ∪
>   ((x ∩ [smin,-1]) ∩ (y ∩ [smin,-1]))
>

> Reported-by: Andrea Righi <arighi@nvidia.com>
> Reported-by: Emil Tsalapatis <emil@etsalapatis.com>
> Closes: https://lore.kernel.org/bpf/aakqucg4vcujVwif@gpd4/T/
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
>  kernel/bpf/verifier.c                         | 24 ++++++++
>  .../selftests/bpf/prog_tests/reg_bounds.c     | 58 +++++++++++++++++--
>  2 files changed, 78 insertions(+), 4 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index d92cf2821657..2b79a2a4d1b5 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -2532,6 +2532,30 @@ static void __reg32_deduce_bounds(struct bpf_reg_state *reg)
>  	if ((u32)reg->s32_min_value <= (u32)reg->s32_max_value) {
>  		reg->u32_min_value = max_t(u32, reg->s32_min_value, reg->u32_min_value);
>  		reg->u32_max_value = min_t(u32, reg->s32_max_value, reg->u32_max_value);
> +	} else {
> +		if (reg->u32_max_value < (u32)reg->s32_min_value) {
> +			/* See __reg64_deduce_bounds() for detailed explanation.
> +			 * Refine ranges in the following situation:
> +			 *
> +			 * 0                                                   U32_MAX
> +			 * |  [xxxxxxxxxxxxxx u32 range xxxxxxxxxxxxxx]              |
> +			 * |----------------------------|----------------------------|
> +			 * |xxxxx s32 range xxxxxxxxx]                       [xxxxxxx|
> +			 * 0                     S32_MAX S32_MIN                    -1
> +			 */
> +			reg->s32_min_value = (s32)reg->u32_min_value;
> +			reg->u32_max_value = min_t(u32, reg->u32_max_value, reg->s32_max_value);
> +		} else if ((u32)reg->s32_max_value < reg->u32_min_value) {
> +			/*
> +			 * 0                                                   U32_MAX
> +			 * |              [xxxxxxxxxxxxxx u32 range xxxxxxxxxxxxxx]  |
> +			 * |----------------------------|----------------------------|
> +			 * |xxxxxxxxx]                       [xxxxxxxxxxxx s32 range |
> +			 * 0                     S32_MAX S32_MIN                    -1
> +			 */
> +			reg->s32_max_value = (s32)reg->u32_max_value;
> +			reg->u32_min_value = max_t(u32, reg->u32_min_value, reg->s32_min_value);
> +		}
>  	}
>  }
>  
> diff --git a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
> index 0322f817d07b..446e5ef62f44 100644
> --- a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
> +++ b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
> @@ -422,15 +422,65 @@ static bool is_valid_range(enum num_t t, struct range x)
>  	}
>  }
>  
> -static struct range range_improve(enum num_t t, struct range old, struct range new)
> +static struct range range_intersection(enum num_t t, struct range old, struct range new)
>  {
>  	return range(t, max_t(t, old.a, new.a), min_t(t, old.b, new.b));
>  }
>  
> +static struct range range_union(enum num_t t, struct range x, struct range y)
> +{
> +	if (!is_valid_range(t, x))
> +		return y;
> +	if (!is_valid_range(t, y))
> +		return x;
> +	return range(t, min_t(t, x.a, y.a), max_t(t, x.b, y.b));
> +}
> +

AFAICT this is only fully accurate if the ranges are intersect/are consecutive.
Is it that it's fine to include extra values into the interval since
we're dealing with bounds checking, and so can relax the bounds as we
please? If so, then this is fine. 

If not, can we either change the name to make it clear we assume the caller has 
ensured this, or add a check in the function itself? 

> +/*
> + * This function attempts to improve x range intersecting it with y.
> + * range_cast(... to_t ...) looses precision for ranges that pass to_t
> + * min/max boundaries. To avoid such precision loses this function
> + * splits both x and y into halves corresponding to non-overflowing
> + * sub-ranges: [0, smin] and [smax, -1].
> + * Final result is computed as follows:
> + *
> + *   ((x ∩ [0, smax]) ∩ (y ∩ [0, smax])) ∪
> + *   ((x ∩ [smin,-1]) ∩ (y ∩ [smin,-1]))
> + *
> + * Precision might still be lost if final union is not a continuous range.
> + */
> +static struct range range_refine_in_halves(enum num_t x_t, struct range x,
> +					   enum num_t y_t, struct range y)
> +{
> +	struct range x_pos, x_neg, y_pos, y_neg, r_pos, r_neg;
> +	u64 smax, smin, neg_one;
> +
> +	if (t_is_32(x_t)) {
> +		smax = (u64)(u32)S32_MAX;
> +		smin = (u64)(u32)S32_MIN;
> +		neg_one = (u64)(u32)(s32)(-1);
> +	} else {
> +		smax = (u64)S64_MAX;
> +		smin = (u64)S64_MIN;
> +		neg_one = U64_MAX;
> +	}
> +	x_pos = range_intersection(x_t, x, range(x_t, 0, smax));
> +	x_neg = range_intersection(x_t, x, range(x_t, smin, neg_one));
> +	y_pos = range_intersection(y_t, y, range(x_t, 0, smax));
> +	y_neg = range_intersection(y_t, y, range(y_t, smin, neg_one));
> +	r_pos = range_intersection(x_t, x_pos, range_cast(y_t, x_t, y_pos));
> +	r_neg = range_intersection(x_t, x_neg, range_cast(y_t, x_t, y_neg));
> +	return range_union(x_t, r_pos, r_neg);
> +
> +}
> +
>  static struct range range_refine(enum num_t x_t, struct range x, enum num_t y_t, struct range y)
>  {
>  	struct range y_cast;
>  
> +	if (t_is_32(x_t) == t_is_32(y_t))
> +		x = range_refine_in_halves(x_t, x, y_t, y);
> +
>  	y_cast = range_cast(y_t, x_t, y);
>  
>  	/* If we know that
> @@ -444,7 +494,7 @@ static struct range range_refine(enum num_t x_t, struct range x, enum num_t y_t,
>  	 */
>  	if (x_t == S64 && y_t == S32 && y_cast.a <= S32_MAX  && y_cast.b <= S32_MAX &&
>  	    (s64)x.a >= S32_MIN && (s64)x.b <= S32_MAX)
> -		return range_improve(x_t, x, y_cast);
> +		return range_intersection(x_t, x, y_cast);
>  
>  	/* the case when new range knowledge, *y*, is a 32-bit subregister
>  	 * range, while previous range knowledge, *x*, is a full register
> @@ -462,7 +512,7 @@ static struct range range_refine(enum num_t x_t, struct range x, enum num_t y_t,
>  		x_swap = range(x_t, swap_low32(x.a, y_cast.a), swap_low32(x.b, y_cast.b));
>  		if (!is_valid_range(x_t, x_swap))
>  			return x;
> -		return range_improve(x_t, x, x_swap);
> +		return range_intersection(x_t, x, x_swap);
>  	}
>  
>  	if (!t_is_32(x_t) && !t_is_32(y_t) && x_t != y_t) {
> @@ -480,7 +530,7 @@ static struct range range_refine(enum num_t x_t, struct range x, enum num_t y_t,
>  	}
>  
>  	/* otherwise, plain range cast and intersection works */
> -	return range_improve(x_t, x, y_cast);
> +	return range_intersection(x_t, x, y_cast);
>  }
>  
>  /* =======================