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

[Eduard Zingerman <eddyz87@gmail.com>]

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.

[...]