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

[Paul Chaignon <paul.chaignon@gmail.com>]

On Thu, Mar 05, 2026 at 11:48:22AM -0800, Eduard Zingerman wrote:

[...]

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 401d6c4960eccfa90893660b7d8aece859787f7f..f960b382fdb3d4a4f5f2a66a525c2f594de529ff 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -2511,6 +2511,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);
> +		}

Looks good to me. I also ran it through Agni and __reg_deduce_bounds
(aka special instruction BPF_SYNC2) is still found to be sound.

>  	}
>  }
>  
> diff --git a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
> index 0322f817d07be5d003c17dd7cedfa3aa4197678e..04938d0d431b38e086b50fe28b99e4ad2682742e 100644
> --- a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
> +++ b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
> @@ -422,15 +422,69 @@ 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));
>  }
>  
> +/*
> + * Result is precise when 'x' and 'y' overlap or form a continuous range,
> + * result is an over-approximation if 'x' and 'y' do not overlap.
> + */
> +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));
> +}
> +
> +/*
> + * 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);

Don't we usually put changes to this file in a separate commit, as for
test changes in general?

Also I believe with these changes, we can now revert commit da653de268d3
("selftests/bpf: Update reg_bound range refinement logic").

> +
>  	y_cast = range_cast(y_t, x_t, y);
>  
>  	/* If we know that
> @@ -444,7 +498,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 +516,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 +534,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);
>  }
>  
>  /* =======================
> 
> -- 
> 2.53.0
>