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

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

On 7/12/24 11:30 AM, Alexei Starovoitov wrote:
> On Thu, Jul 11, 2024 at 10:07 PM Yonghong Song <yonghong.song@linux.dev> 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 so happens, that 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.
>> Sounds good. I will add some comments like the above in v2.
> I would add Ed's explanation verbatim as a comment to verifier.c
>
>>>> +    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)) {
>>> The explanation above also lands a question, would it be correct to
>>> replace the checks above by a single one?
>>>
>>>     reg->smin_value >= S32_MIN && reg->smax_value <= S32_MAX
>> You are correct, the range check can be better. The following is the related
>> description in the commit message:
>>
>>> This patch fixed the issue by adding additional register deduction after 32-bit compare
>>> insn such that if the signed 32-bit register range is non-negative and 64-bit smin is
>>> {S32/S16/S8}_MIN and 64-bit max is no greater than {U32/U16/U8}_MAX.
>>> Here, we check smin with {S32/S16/S8}_MIN since this is the most common result related to
>>> signed extension load.
>> The corrent code simply represents the most common pattern.
>> Since you mention this, I will resive it as below in v2:
>>      reg->smin_value >= S32_MIN && reg->smin_value < 0 && reg->smax_value <= S32_MAX
> Why add smin_value < 0 check ?
>
> I'd think
> if (reg->s32_min_value >= 0 && reg->smin_value >= S32_MIN &&
>      reg->smax_value <= S32_MAX)
>
> is enough?

This is enough and correct. As you mentioned below, if smin_value >= 0 it is just
a redundant work but no hurt.

I will do as you suggested.

>
> If smin_value is >=0 it's fine to reassign it with s32_min_value
> which is positive as well.