Re: [PATCH bpf-next v2 1/2] bpf: Get better reg range with ldsx and 32bit compare

[Yonghong Song <yonghong.song@linux.dev>]

On 7/12/24 1:49 PM, Eduard Zingerman wrote:
> On Fri, 2024-07-12 at 13:28 -0700, Yonghong Song wrote:
>
> [...]
>
>> +
>> +	/* Here we would like to handle a special case after sign extending load,
>> +	 * when upper bits for a 64-bit range are all 1s or all 0s.
>> +	 *
>> +	 * Upper bits are all 1s when register is in a rage:
>> +	 *   [0xffff_ffff_0000_0000, 0xffff_ffff_ffff_ffff]
>> +	 * Upper bits are all 0s when register is in a range:
>> +	 *   [0x0000_0000_0000_0000, 0x0000_0000_ffff_ffff]
>> +	 * Together this forms are continuous range:
>> +	 *   [0xffff_ffff_0000_0000, 0x0000_0000_ffff_ffff]
>> +	 *
>> +	 * Now, suppose that register range is in fact tighter:
>> +	 *   [0xffff_ffff_8000_0000, 0x0000_0000_ffff_ffff] (R)
>> +	 * Also suppose that it's 32-bit range is positive,
>> +	 * meaning that lower 32-bits of the full 64-bit register
>> +	 * are in the range:
>> +	 *   [0x0000_0000, 0x7fff_ffff] (W)
>> +	 *
>> +	 * It this happens, then any value in a range:
>> +	 *   [0xffff_ffff_0000_0000, 0xffff_ffff_7fff_ffff]
>> +	 * is smaller than a lowest bound of the range (R):
>> +	 *   0xffff_ffff_8000_0000
>> +	 * which means that upper bits of the full 64-bit register
>> +	 * can't be all 1s, when lower bits are in range (W).
>> +	 *
>> +	 * Note that:
>> +	 *  - 0xffff_ffff_8000_0000 == (s64)S32_MIN
>> +	 *  - 0x0000_0000_ffff_ffff == (s64)S32_MAX
>> +	 * These relations are used in the conditions below.
>> +	 */
>> +	if (reg->s32_min_value >= 0) {
>> +		if ((reg->smin_value >= S32_MIN && reg->smax_value <= S32_MAX) ||
>> +		    (reg->smin_value >= S16_MIN && reg->smax_value <= S16_MAX) ||
>> +		    (reg->smin_value >= S8_MIN && reg->smax_value <= S8_MAX)) {
> Sorry, maybe there is still something I don't understand.
> Why do we need 3 different checks here?
> - S32_MIN <= r <= S32_MAX (R32)
> - S16_MIN <= r <= S16_MAX (R16)
> -  S8_MIN <= r <=  S8_MAX (R8)
>
> If R8 or R16 is true then R32 is true, so it seems this condition is redundant.

You are right! I changed from '==' to '>=' but missed this.
Will make changes in the next revision.

>
>> +			reg->smin_value = reg->umin_value = reg->s32_min_value;
>> +			reg->smax_value = reg->umax_value = reg->s32_max_value;
>> +			reg->var_off = tnum_intersect(reg->var_off,
>> +						      tnum_range(reg->smin_value,
>> +								 reg->smax_value));
>> +		}
>> +	}
> [...]