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

[Eduard Zingerman <eddyz87@gmail.com>]

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().

> +				if (err)
> +					return err;
> +				removed_cnt++;
> +			}
> +			j--;
> +		}
> +
> +		insn_cnt -= removed_cnt;
> +		i = last_may_goto - removed_cnt;
> +	}
> +
> +	return 0;
> +}

[...]