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

[PATCH bpf-next v2 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.

Changelogs:
  v1 -> v2:
    - Instead of a separate function, removing 'may_goto 0' in existing
      func opt_remove_nops().

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

 kernel/bpf/verifier.c                         | 14 ++-
 .../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, 138 insertions(+), 5 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 v2 1/3] bpf: Allow 'may_goto 0' instruction in verifier

[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>
Acked-by: Eduard Zingerman <eddyz87@gmail.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 245f1f3f1aec..963dfda81c06 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -15972,9 +15972,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 v2 2/3] bpf: Remove 'may_goto 0' instruction in opt_remove_nops()

[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 | 9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 963dfda81c06..784547aa40a8 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -20187,20 +20187,25 @@ static const struct bpf_insn NOP = BPF_JMP_IMM(BPF_JA, 0, 0, 0);
 
 static int opt_remove_nops(struct bpf_verifier_env *env)
 {
+	const struct bpf_insn may_goto_0 = BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, 0, 0);
 	const struct bpf_insn ja = NOP;
 	struct bpf_insn *insn = env->prog->insnsi;
 	int insn_cnt = env->prog->len;
+	bool is_may_goto_0, is_ja;
 	int i, err;
 
 	for (i = 0; i < insn_cnt; i++) {
-		if (memcmp(&insn[i], &ja, sizeof(ja)))
+		is_may_goto_0 = !memcmp(&insn[i], &may_goto_0, sizeof(may_goto_0));
+		is_ja = !memcmp(&insn[i], &ja, sizeof(ja));
+
+		if (!is_may_goto_0 && !is_ja)
 			continue;
 
 		err = verifier_remove_insns(env, i, 1);
 		if (err)
 			return err;
 		insn_cnt--;
-		i--;
+		i -= (is_may_goto_0 && i > 0) ? 2 : 1;
 	}
 
 	return 0;
-- 
2.43.5

[PATCH bpf-next v2 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;

Acked-by: Eduard Zingerman <eddyz87@gmail.com>
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 v2 1/3] bpf: Allow 'may_goto 0' instruction in verifier

[Daniel Borkmann]

On 1/18/25 8:20 PM, 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>
> Acked-by: Eduard Zingerman <eddyz87@gmail.com>
> Signed-off-by: Yonghong Song <yonghong.song@linux.dev>

Acked-by: Daniel Borkmann <daniel@iogearbox.net>

Re: [PATCH bpf-next v2 2/3] bpf: Remove 'may_goto 0' instruction in opt_remove_nops()

[Daniel Borkmann]

On 1/18/25 8:20 PM, 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>
> ---
>   kernel/bpf/verifier.c | 9 +++++++--
>   1 file changed, 7 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 963dfda81c06..784547aa40a8 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -20187,20 +20187,25 @@ static const struct bpf_insn NOP = BPF_JMP_IMM(BPF_JA, 0, 0, 0);
>   
>   static int opt_remove_nops(struct bpf_verifier_env *env)
>   {
> +	const struct bpf_insn may_goto_0 = BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, 0, 0);
>   	const struct bpf_insn ja = NOP;
>   	struct bpf_insn *insn = env->prog->insnsi;
>   	int insn_cnt = env->prog->len;
> +	bool is_may_goto_0, is_ja;
>   	int i, err;
>   
>   	for (i = 0; i < insn_cnt; i++) {
> -		if (memcmp(&insn[i], &ja, sizeof(ja)))
> +		is_may_goto_0 = !memcmp(&insn[i], &may_goto_0, sizeof(may_goto_0));
> +		is_ja = !memcmp(&insn[i], &ja, sizeof(ja));
> +
> +		if (!is_may_goto_0 && !is_ja)
>   			continue;

Why the extra may_goto_0 stack var?

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 245f1f3f1aec..16ba26295ec7 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -20185,16 +20185,19 @@ static int opt_remove_dead_code(struct bpf_verifier_env *env)
  }
  
  static const struct bpf_insn NOP = BPF_JMP_IMM(BPF_JA, 0, 0, 0);
+static const struct bpf_insn MAY_GOTO_0 = BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, 0, 0);
  
  static int opt_remove_nops(struct bpf_verifier_env *env)
  {
-       const struct bpf_insn ja = NOP;
         struct bpf_insn *insn = env->prog->insnsi;
         int insn_cnt = env->prog->len;
+       bool is_ja, is_may_goto_0;
         int i, err;
  
         for (i = 0; i < insn_cnt; i++) {
-               if (memcmp(&insn[i], &ja, sizeof(ja)))
+               is_may_goto_0 = !memcmp(&insn[i], &MAY_GOTO_0, sizeof(MAY_GOTO_0));
+               is_ja         = !memcmp(&insn[i], &NOP, sizeof(NOP));
+               if (!is_may_goto_0 && !is_ja)
                         continue;

>   		err = verifier_remove_insns(env, i, 1);
>   		if (err)
>   			return err;
>   		insn_cnt--;
> -		i--;
> +		i -= (is_may_goto_0 && i > 0) ? 2 : 1;

Maybe add a comment for this logic?

Thanks,
Daniel

Re: [PATCH bpf-next v2 2/3] bpf: Remove 'may_goto 0' instruction in opt_remove_nops()

[Alexei Starovoitov]

On Mon, Jan 20, 2025 at 7:29 AM Daniel Borkmann <daniel@iogearbox.net> wrote:
>
> On 1/18/25 8:20 PM, 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>
> > ---
> >   kernel/bpf/verifier.c | 9 +++++++--
> >   1 file changed, 7 insertions(+), 2 deletions(-)
> >
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 963dfda81c06..784547aa40a8 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -20187,20 +20187,25 @@ static const struct bpf_insn NOP = BPF_JMP_IMM(BPF_JA, 0, 0, 0);
> >
> >   static int opt_remove_nops(struct bpf_verifier_env *env)
> >   {
> > +     const struct bpf_insn may_goto_0 = BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, 0, 0);
> >       const struct bpf_insn ja = NOP;
> >       struct bpf_insn *insn = env->prog->insnsi;
> >       int insn_cnt = env->prog->len;
> > +     bool is_may_goto_0, is_ja;
> >       int i, err;
> >
> >       for (i = 0; i < insn_cnt; i++) {
> > -             if (memcmp(&insn[i], &ja, sizeof(ja)))
> > +             is_may_goto_0 = !memcmp(&insn[i], &may_goto_0, sizeof(may_goto_0));
> > +             is_ja = !memcmp(&insn[i], &ja, sizeof(ja));
> > +
> > +             if (!is_may_goto_0 && !is_ja)
> >                       continue;
>
> Why the extra may_goto_0 stack var?
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 245f1f3f1aec..16ba26295ec7 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -20185,16 +20185,19 @@ static int opt_remove_dead_code(struct bpf_verifier_env *env)
>   }
>
>   static const struct bpf_insn NOP = BPF_JMP_IMM(BPF_JA, 0, 0, 0);
> +static const struct bpf_insn MAY_GOTO_0 = BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, 0, 0);
>
>   static int opt_remove_nops(struct bpf_verifier_env *env)
>   {
> -       const struct bpf_insn ja = NOP;
>          struct bpf_insn *insn = env->prog->insnsi;
>          int insn_cnt = env->prog->len;
> +       bool is_ja, is_may_goto_0;
>          int i, err;
>
>          for (i = 0; i < insn_cnt; i++) {
> -               if (memcmp(&insn[i], &ja, sizeof(ja)))
> +               is_may_goto_0 = !memcmp(&insn[i], &MAY_GOTO_0, sizeof(MAY_GOTO_0));
> +               is_ja         = !memcmp(&insn[i], &NOP, sizeof(NOP));
> +               if (!is_may_goto_0 && !is_ja)
>                          continue;
>
> >               err = verifier_remove_insns(env, i, 1);
> >               if (err)
> >                       return err;
> >               insn_cnt--;
> > -             i--;
> > +             i -= (is_may_goto_0 && i > 0) ? 2 : 1;
>
> Maybe add a comment for this logic?

Adjusted both while applying.
Thanks!

Re: [PATCH bpf-next v2 2/3] bpf: Remove 'may_goto 0' instruction in opt_remove_nops()

[Yonghong Song]

On 1/20/25 7:29 AM, Daniel Borkmann wrote:
> On 1/18/25 8:20 PM, 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>
>> ---
>>   kernel/bpf/verifier.c | 9 +++++++--
>>   1 file changed, 7 insertions(+), 2 deletions(-)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 963dfda81c06..784547aa40a8 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -20187,20 +20187,25 @@ static const struct bpf_insn NOP = 
>> BPF_JMP_IMM(BPF_JA, 0, 0, 0);
>>     static int opt_remove_nops(struct bpf_verifier_env *env)
>>   {
>> +    const struct bpf_insn may_goto_0 = BPF_RAW_INSN(BPF_JMP | 
>> BPF_JCOND, 0, 0, 0, 0);
>>       const struct bpf_insn ja = NOP;
>>       struct bpf_insn *insn = env->prog->insnsi;
>>       int insn_cnt = env->prog->len;
>> +    bool is_may_goto_0, is_ja;
>>       int i, err;
>>         for (i = 0; i < insn_cnt; i++) {
>> -        if (memcmp(&insn[i], &ja, sizeof(ja)))
>> +        is_may_goto_0 = !memcmp(&insn[i], &may_goto_0, 
>> sizeof(may_goto_0));
>> +        is_ja = !memcmp(&insn[i], &ja, sizeof(ja));
>> +
>> +        if (!is_may_goto_0 && !is_ja)
>>               continue;
>
> Why the extra may_goto_0 stack var?
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 245f1f3f1aec..16ba26295ec7 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -20185,16 +20185,19 @@ static int opt_remove_dead_code(struct 
> bpf_verifier_env *env)
>  }
>
>  static const struct bpf_insn NOP = BPF_JMP_IMM(BPF_JA, 0, 0, 0);
> +static const struct bpf_insn MAY_GOTO_0 = BPF_RAW_INSN(BPF_JMP | 
> BPF_JCOND, 0, 0, 0, 0);

This actually is what I did initially. I changed to use the stack var because
NOP is used in other functions too while MAY_GOTO_0 is only used in
opt_remove_nops(). Certainly, using MAY_GOTO_0 as static variable works too.

>
>  static int opt_remove_nops(struct bpf_verifier_env *env)
>  {
> -       const struct bpf_insn ja = NOP;
>         struct bpf_insn *insn = env->prog->insnsi;
>         int insn_cnt = env->prog->len;
> +       bool is_ja, is_may_goto_0;
>         int i, err;
>
>         for (i = 0; i < insn_cnt; i++) {
> -               if (memcmp(&insn[i], &ja, sizeof(ja)))
> +               is_may_goto_0 = !memcmp(&insn[i], &MAY_GOTO_0, 
> sizeof(MAY_GOTO_0));
> +               is_ja         = !memcmp(&insn[i], &NOP, sizeof(NOP));
> +               if (!is_may_goto_0 && !is_ja)
>                         continue;
>
>>           err = verifier_remove_insns(env, i, 1);
>>           if (err)
>>               return err;
>>           insn_cnt--;
>> -        i--;
>> +        i -= (is_may_goto_0 && i > 0) ? 2 : 1;
>
> Maybe add a comment for this logic?

Thanks Alexei for adding comments before merging!

>
> Thanks,
> Daniel