Re: [PATCH bpf-next 2/3] bpf: Remove 'may_goto 0' instruction

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

On 1/16/25 5:45 PM, Alexei Starovoitov wrote:
> On Thu, Jan 16, 2025 at 11:42 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>> On Wed, 2025-01-15 at 21:51 -0800, Yonghong Song wrote:
>>> Since 'may_goto 0' insns are actually no-op, let us remove them.
>>> Otherwise, verifier will generate code like
>>>     /* r10 - 8 stores the implicit loop count */
>>>     r11 = *(u64 *)(r10 -8)
>>>     if r11 == 0x0 goto pc+2
>>>     r11 -= 1
>>>     *(u64 *)(r10 -8) = r11
>>>
>>> which is the pure overhead.
>>>
>>> The following code patterns (from the previous commit) are also
>>> handled:
>>>     may_goto 2
>>>     may_goto 1
>>>     may_goto 0
>>>
>>> With this commit, the above three 'may_goto' insns are all
>>> eliminated.
>>>
>>> Signed-off-by: Yonghong Song <yonghong.song@linux.dev>
>>> ---
>> Technically this is a side-effect, it subtracts 1 from total loop budget.
>> An alternative transformation might be:
>>
>>      r11 = *(u64 *)(r10 -8)
>>      if r11 == 0x0 goto pc+2
>>      r11 -= 3     <---------------- note 3 here
>>      *(u64 *)(r10 -8) = r11
>>
>> On the other hand, it looks like there is no way to trick verifier
>> into an infinite loop by removing these statements, so this should be
>> safe modulo exceeding the 8M iterations budget.
>>
>> Acked-by: Eduard Zingerman <eddyz87@gmail.com>
>>
>>>   kernel/bpf/verifier.c | 36 ++++++++++++++++++++++++++++++++++++
>>>   1 file changed, 36 insertions(+)
>>>
>>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>>> index edf3cc42a220..72b474bfba2d 100644
>>> --- a/kernel/bpf/verifier.c
>>> +++ b/kernel/bpf/verifier.c
>>> @@ -20133,6 +20133,40 @@ static int opt_remove_nops(struct bpf_verifier_env *env)
>>>        return 0;
>>>   }
>>>
>>> +static int opt_remove_useless_may_gotos(struct bpf_verifier_env *env)
>>> +{
>>> +     struct bpf_insn *insn = env->prog->insnsi;
>>> +     int i, j, err, last_may_goto, removed_cnt;
>>> +     int insn_cnt = env->prog->len;
>>> +
>>> +     for (i = 0; i < insn_cnt; i++) {
>>> +             if (!is_may_goto_insn(&insn[i]))
>>> +                     continue;
>>> +
>>> +             for (j = i + 1; j < insn_cnt; j++) {
>>> +                     if (!is_may_goto_insn(&insn[j]))
>>> +                             break;
>>> +             }
>>> +
>>> +             last_may_goto = --j;
>>> +             removed_cnt = 0;
>>> +             while (j >= i) {
>>> +                     if (insn[j].off == 0) {
>>> +                             err = verifier_remove_insns(env, j, 1);
>> Nit: given how ineffective the verifier_remove_insns() is I'd count
>>       the number of matching may_goto's and removed them using one call
>>       to verifier_remove_insns().
> True,
> but more generally I don't see why may_goto needs special treatment.
> opt_remove_nops() should handle both.
>
> if (memcmp(&insn[i], &ja, sizeof(ja)) &&
>      memcmp(&insn[i], &may_goto0, sizeof(ja)))
>   continue;
>
> will almost work.
> In the sequence of may_goto +2, +1, +0
> only the last one will be removed, I think,
> but opt_remove_nops() can be tweaked to achieve that as well.
> -                 i--;
> +                 i -= 2;
>
> will do ?

Okay. Let me give a try.

>
> pw-bot: cr