[PATCH bpf-next 0/3] bpf: Allow 'may_goto 0' instruction

[PATCH bpf-next 0/3] bpf: Allow 'may_goto 0' instruction

[Yonghong Song]

Emil Tsalapatis from Meta reported such a case where 'may_goto 0' insn is
generated by clang-19 compiler and this caused verification failure
since 'may_goto 0' is rejected by verifier.

In fact, 'may_goto 0' insn is actually a no-op and it won't hurt
verification. The only side effect is that the verifier will convert
the insn to a sequence of codes like
   /* r10 - 8 stores the implicit loop count */
   r11 = *(u64 *)(r10 -8)
   if r11 == 0x0 goto pc+2
   r11 -= 1
   *(u64 *)(r10 -8) = r11

With this patch set 'may_goto 0' insns are allowed in verification which
also removes those insns.

Yonghong Song (3):
  bpf: Allow 'may_goto 0' instruction
  bpf: Remove 'may_goto 0' instruction
  selftests/bpf: Add some tests related to 'may_goto 0' insns

 kernel/bpf/verifier.c                         | 41 +++++++-
 .../selftests/bpf/prog_tests/verifier.c       |  4 +
 .../selftests/bpf/progs/verifier_may_goto_1.c | 97 +++++++++++++++++++
 .../selftests/bpf/progs/verifier_may_goto_2.c | 28 ++++++
 4 files changed, 167 insertions(+), 3 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_may_goto_1.c
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_may_goto_2.c

-- 
2.43.5

[PATCH bpf-next 1/3] bpf: Allow 'may_goto 0' instruction

[Yonghong Song]

Commit 011832b97b31 ("bpf: Introduce may_goto instruction") added support
for may_goto insn. The 'may_goto 0' insn is disallowed since the insn is
equivalent to a nop as both branch will go to the next insn.

But it is possible that compiler transformation may generate 'may_goto 0'
insn. Emil Tsalapatis from Meta reported such a case which caused
verification failure. For example, for the following code,
   int i, tmp[3];
   for (i = 0; i < 3 && can_loop; i++)
     tmp[i] = 0;
   ...

clang 20 may generate code like
   may_goto 2;
   may_goto 1;
   may_goto 0;
   r1 = 0; /* tmp[0] = 0; */
   r2 = 0; /* tmp[1] = 0; */
   r3 = 0; /* tmp[2] = 0; */

Let us permit 'may_goto 0' insn to avoid verification failure for codes
like the above.

Reported-by: Emil Tsalapatis <etsal@meta.com>
Signed-off-by: Yonghong Song <yonghong.song@linux.dev>
---
 kernel/bpf/verifier.c | 5 ++---
 1 file changed, 2 insertions(+), 3 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index b8ca227c78af..edf3cc42a220 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -15899,9 +15899,8 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
 
 		if (insn->code != (BPF_JMP | BPF_JCOND) ||
 		    insn->src_reg != BPF_MAY_GOTO ||
-		    insn->dst_reg || insn->imm || insn->off == 0) {
-			verbose(env, "invalid may_goto off %d imm %d\n",
-				insn->off, insn->imm);
+		    insn->dst_reg || insn->imm) {
+			verbose(env, "invalid may_goto imm %d\n", insn->imm);
 			return -EINVAL;
 		}
 		prev_st = find_prev_entry(env, cur_st->parent, idx);
-- 
2.43.5

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

[Yonghong Song]

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>
---
 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);
+				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);
-- 
2.43.5

[PATCH bpf-next 3/3] selftests/bpf: Add some tests related to 'may_goto 0' insns

[Yonghong Song]

Add both asm-based and C-based tests which have 'may_goto 0' insns.

For the following code in C-based test,
   int i, tmp[3];
   for (i = 0; i < 3 && can_loop; i++)
       tmp[i] = 0;

The clang compiler (clang 19 and 20) generates
   may_goto 2
   may_goto 1
   may_goto 0
   r1 = 0
   r2 = 0
   r3 = 0

The above asm codes are due to llvm pass SROAPass. This ensures the
successful verification since tmp[0-2] are initialized.  Otherwise,
the code without SROAPass like
   may_goto 5
   r1 = 0
   may_goto 3
   r2 = 0
   may_goto 1
   r3 = 0
will have verification failure.

Although from the source code C-based test should have verification
failure, clang compiler optimization generates code with successful
verification. If gcc generates different asm codes than clang, the
following code can be used for gcc:
   int i, tmp[3];
   for (i = 0; i < 3; i++)
       tmp[i] = 0;

Signed-off-by: Yonghong Song <yonghong.song@linux.dev>
---
 .../selftests/bpf/prog_tests/verifier.c       |  4 +
 .../selftests/bpf/progs/verifier_may_goto_1.c | 97 +++++++++++++++++++
 .../selftests/bpf/progs/verifier_may_goto_2.c | 28 ++++++
 3 files changed, 129 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_may_goto_1.c
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_may_goto_2.c

diff --git a/tools/testing/selftests/bpf/prog_tests/verifier.c b/tools/testing/selftests/bpf/prog_tests/verifier.c
index 33cd3e035071..8a0e1ff8a2dc 100644
--- a/tools/testing/selftests/bpf/prog_tests/verifier.c
+++ b/tools/testing/selftests/bpf/prog_tests/verifier.c
@@ -52,6 +52,8 @@
 #include "verifier_map_ptr_mixing.skel.h"
 #include "verifier_map_ret_val.skel.h"
 #include "verifier_masking.skel.h"
+#include "verifier_may_goto_1.skel.h"
+#include "verifier_may_goto_2.skel.h"
 #include "verifier_meta_access.skel.h"
 #include "verifier_movsx.skel.h"
 #include "verifier_mtu.skel.h"
@@ -182,6 +184,8 @@ void test_verifier_map_ptr(void)              { RUN(verifier_map_ptr); }
 void test_verifier_map_ptr_mixing(void)       { RUN(verifier_map_ptr_mixing); }
 void test_verifier_map_ret_val(void)          { RUN(verifier_map_ret_val); }
 void test_verifier_masking(void)              { RUN(verifier_masking); }
+void test_verifier_may_goto_1(void)           { RUN(verifier_may_goto_1); }
+void test_verifier_may_goto_2(void)           { RUN(verifier_may_goto_2); }
 void test_verifier_meta_access(void)          { RUN(verifier_meta_access); }
 void test_verifier_movsx(void)                 { RUN(verifier_movsx); }
 void test_verifier_netfilter_ctx(void)        { RUN(verifier_netfilter_ctx); }
diff --git a/tools/testing/selftests/bpf/progs/verifier_may_goto_1.c b/tools/testing/selftests/bpf/progs/verifier_may_goto_1.c
new file mode 100644
index 000000000000..e81097c96fe2
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/verifier_may_goto_1.c
@@ -0,0 +1,97 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2025 Meta Platforms, Inc. and affiliates. */
+
+#include <linux/bpf.h>
+#include <bpf/bpf_helpers.h>
+#include "../../../include/linux/filter.h"
+#include "bpf_misc.h"
+
+SEC("raw_tp")
+__description("may_goto 0")
+__arch_x86_64
+__xlated("0: r0 = 1")
+__xlated("1: exit")
+__success
+__naked void may_goto_simple(void)
+{
+	asm volatile (
+	".8byte %[may_goto];"
+	"r0 = 1;"
+	".8byte %[may_goto];"
+	"exit;"
+	:
+	: __imm_insn(may_goto, BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, 0 /* offset */, 0))
+	: __clobber_all);
+}
+
+SEC("raw_tp")
+__description("batch 2 of may_goto 0")
+__arch_x86_64
+__xlated("0: r0 = 1")
+__xlated("1: exit")
+__success
+__naked void may_goto_batch_0(void)
+{
+	asm volatile (
+	".8byte %[may_goto1];"
+	".8byte %[may_goto1];"
+	"r0 = 1;"
+	".8byte %[may_goto1];"
+	".8byte %[may_goto1];"
+	"exit;"
+	:
+	: __imm_insn(may_goto1, BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, 0 /* offset */, 0))
+	: __clobber_all);
+}
+
+SEC("raw_tp")
+__description("may_goto batch with offsets 2/1/0")
+__arch_x86_64
+__xlated("0: r0 = 1")
+__xlated("1: exit")
+__success
+__naked void may_goto_batch_1(void)
+{
+	asm volatile (
+	".8byte %[may_goto1];"
+	".8byte %[may_goto2];"
+	".8byte %[may_goto3];"
+	"r0 = 1;"
+	".8byte %[may_goto1];"
+	".8byte %[may_goto2];"
+	".8byte %[may_goto3];"
+	"exit;"
+	:
+	: __imm_insn(may_goto1, BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, 2 /* offset */, 0)),
+	  __imm_insn(may_goto2, BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, 1 /* offset */, 0)),
+	  __imm_insn(may_goto3, BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, 0 /* offset */, 0))
+	: __clobber_all);
+}
+
+SEC("raw_tp")
+__description("may_goto batch with offsets 2/0")
+__arch_x86_64
+__xlated("0: *(u64 *)(r10 -8) = 8388608")
+__xlated("1: r11 = *(u64 *)(r10 -8)")
+__xlated("2: if r11 == 0x0 goto pc+3")
+__xlated("3: r11 -= 1")
+__xlated("4: *(u64 *)(r10 -8) = r11")
+__xlated("5: r0 = 1")
+__xlated("6: r0 = 2")
+__xlated("7: exit")
+__success
+__naked void may_goto_batch_2(void)
+{
+	asm volatile (
+	".8byte %[may_goto1];"
+	".8byte %[may_goto3];"
+	"r0 = 1;"
+	"r0 = 2;"
+	"exit;"
+	:
+	: __imm_insn(may_goto1, BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, 2 /* offset */, 0)),
+	  __imm_insn(may_goto3, BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, 0 /* offset */, 0))
+	: __clobber_all);
+}
+
+char _license[] SEC("license") = "GPL";
diff --git a/tools/testing/selftests/bpf/progs/verifier_may_goto_2.c b/tools/testing/selftests/bpf/progs/verifier_may_goto_2.c
new file mode 100644
index 000000000000..b891faf50660
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/verifier_may_goto_2.c
@@ -0,0 +1,28 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2025 Meta Platforms, Inc. and affiliates. */
+
+#include "bpf_misc.h"
+#include "bpf_experimental.h"
+
+int gvar;
+
+SEC("raw_tp")
+__description("C code with may_goto 0")
+__success
+int may_goto_c_code(void)
+{
+	int i, tmp[3];
+
+	for (i = 0; i < 3 && can_loop; i++)
+		tmp[i] = 0;
+
+	for (i = 0; i < 3 && can_loop; i++)
+		tmp[i] = gvar - i;
+
+	for (i = 0; i < 3 && can_loop; i++)
+		gvar += tmp[i];
+
+	return 0;
+}
+
+char _license[] SEC("license") = "GPL";
-- 
2.43.5

Re: [PATCH bpf-next 1/3] bpf: Allow 'may_goto 0' instruction

[Eduard Zingerman]

On Wed, 2025-01-15 at 21:51 -0800, Yonghong Song wrote:
> Commit 011832b97b31 ("bpf: Introduce may_goto instruction") added support
> for may_goto insn. The 'may_goto 0' insn is disallowed since the insn is
> equivalent to a nop as both branch will go to the next insn.
> 
> But it is possible that compiler transformation may generate 'may_goto 0'
> insn. Emil Tsalapatis from Meta reported such a case which caused
> verification failure. For example, for the following code,
>    int i, tmp[3];
>    for (i = 0; i < 3 && can_loop; i++)
>      tmp[i] = 0;
>    ...
> 
> clang 20 may generate code like
>    may_goto 2;
>    may_goto 1;
>    may_goto 0;
>    r1 = 0; /* tmp[0] = 0; */
>    r2 = 0; /* tmp[1] = 0; */
>    r3 = 0; /* tmp[2] = 0; */
> 
> Let us permit 'may_goto 0' insn to avoid verification failure for codes
> like the above.
> 
> Reported-by: Emil Tsalapatis <etsal@meta.com>
> Signed-off-by: Yonghong Song <yonghong.song@linux.dev>
> ---

Acked-by: Eduard Zingerman <eddyz87@gmail.com>

[...]

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

[Eduard Zingerman]

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

[...]

Re: [PATCH bpf-next 3/3] selftests/bpf: Add some tests related to 'may_goto 0' insns

[Eduard Zingerman]

On Wed, 2025-01-15 at 21:51 -0800, Yonghong Song wrote:
> Add both asm-based and C-based tests which have 'may_goto 0' insns.
> 
> For the following code in C-based test,
>    int i, tmp[3];
>    for (i = 0; i < 3 && can_loop; i++)
>        tmp[i] = 0;
> 
> The clang compiler (clang 19 and 20) generates
>    may_goto 2
>    may_goto 1
>    may_goto 0
>    r1 = 0
>    r2 = 0
>    r3 = 0
> 
> The above asm codes are due to llvm pass SROAPass. This ensures the
> successful verification since tmp[0-2] are initialized.  Otherwise,
> the code without SROAPass like
>    may_goto 5
>    r1 = 0
>    may_goto 3
>    r2 = 0
>    may_goto 1
>    r3 = 0
> will have verification failure.
> 
> Although from the source code C-based test should have verification
> failure, clang compiler optimization generates code with successful
> verification. If gcc generates different asm codes than clang, the
> following code can be used for gcc:
>    int i, tmp[3];
>    for (i = 0; i < 3; i++)
>        tmp[i] = 0;
> 
> Signed-off-by: Yonghong Song <yonghong.song@linux.dev>
> ---

Acked-by: Eduard Zingerman <eddyz87@gmail.com>

[...]

> +SEC("raw_tp")
> +__description("may_goto batch with offsets 2/1/0")
> +__arch_x86_64
> +__xlated("0: r0 = 1")
> +__xlated("1: exit")
> +__success
> +__naked void may_goto_batch_1(void)
> +{
> +	asm volatile (
> +	".8byte %[may_goto1];"
> +	".8byte %[may_goto2];"
> +	".8byte %[may_goto3];"
> +	"r0 = 1;"
> +	".8byte %[may_goto1];"
> +	".8byte %[may_goto2];"
> +	".8byte %[may_goto3];"
> +	"exit;"
> +	:
> +	: __imm_insn(may_goto1, BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, 2 /* offset */, 0)),
> +	  __imm_insn(may_goto2, BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, 1 /* offset */, 0)),
> +	  __imm_insn(may_goto3, BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, 0 /* offset */, 0))

Rant: may_goto3 that does +0 jump is a bit confusing :)

> +	: __clobber_all);
> +}

[...]

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

[Alexei Starovoitov]

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 ?

pw-bot: cr

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

[Yonghong Song]

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