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

Commit Message

Yonghong Song Jan. 16, 2025, 5:51 a.m. UTC

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 <[e-mail]>
---
 kernel/bpf/verifier.c | 36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)

Comments

Eduard Zingerman Jan. 16, 2025, 7:42 p.m. UTC | #1

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 <[e-mail]>
> ---

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 <[e-mail]>

>  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;
> +}

[...]

Alexei Starovoitov Jan. 17, 2025, 1:45 a.m. UTC | #2

On Thu, Jan 16, 2025 at 11:42 AM Eduard Zingerman <[e-mail]> 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 <[e-mail]>
> > ---
>
> 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 <[e-mail]>
>
> >  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 ?

pw-bot: cr

Yonghong Song Jan. 17, 2025, 3:43 a.m. UTC | #3

On 1/16/25 5:45 PM, Alexei Starovoitov wrote:
> On Thu, Jan 16, 2025 at 11:42 AM Eduard Zingerman <[e-mail]> 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 <[e-mail]>
>>> ---
>> 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 <[e-mail]>
>>
>>>   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

Patch

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);
+				if (err)
+					return err;
+				removed_cnt++;
+			}
+			j--;
+		}
+
+		insn_cnt -= removed_cnt;
+		i = last_may_goto - removed_cnt;
+	}
+
+	return 0;
+}
+
 static int opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
 					 const union bpf_attr *attr)
 {
@@ -23089,6 +23123,8 @@  int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3
 			ret = opt_remove_dead_code(env);
 		if (ret == 0)
 			ret = opt_remove_nops(env);
+		if (ret == 0)
+			ret = opt_remove_useless_may_gotos(env);
 	} else {
 		if (ret == 0)
 			sanitize_dead_code(env);