Skip to contentSkip to conversation

bpf: Allow 'may_goto 0' instruction

PATCH In review Yonghong Song 3 participants 8 messages Jan 18, 2025 – Jan 21, 2025

Subsystems (4)
lore
Share & tools
lore

Yonghong Song

author reviewer
#0 lore raw

v2 cover bpf: Allow 'may_goto 0' instruction

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
Signature · 1 line
2.43.5
author reviewer
#1 lore raw

PATCH v2 1/3 bpf: Allow 'may_goto 0' instruction in verifier

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.

---
 kernel/bpf/verifier.c | 5 ++---
 1 file changed, 2 insertions(+), 3 deletions(-)
kernel/bpf/verifier.c +2 -3
index 245f1f3f1aec..963dfda81c06 100644
@@ -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);
Signature · 1 line
2.43.5
maintainer Acked-by on v2 1/3
#2 lore raw

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

Quoted 20 lines · 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; */
Quoted 6 lines

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

author reviewer
#3 lore raw

PATCH v2 2/3 bpf: Remove 'may_goto 0' instruction in opt_remove_nops()

In reply to 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.

---
 kernel/bpf/verifier.c | 9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)
kernel/bpf/verifier.c +7 -2
index 963dfda81c06..784547aa40a8 100644
@@ -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;
Signature · 1 line
2.43.5
maintainer
#4 lore raw

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

Quoted 36 lines · 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.

---
  kernel/bpf/verifier.c | 9 +++++++--
  1 file changed, 7 insertions(+), 2 deletions(-)
kernel/bpf/verifier.c +1 -0
index 963dfda81c06..784547aa40a8 100644
@@ -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;

kernel/bpf/verifier.c static const struct bpf_insn NOP = BPF_JMP_IMM(BPF_JA, 0, 0, 0); · line 20202

Quoted 10 lines
kernel/bpf/verifier.c +5 -1
+	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?

kernel/bpf/verifier.c +5 -2
index 245f1f3f1aec..16ba26295ec7 100644
@@ -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;
 

kernel/bpf/verifier.c static const struct bpf_insn NOP = BPF_JMP_IMM(BPF_JA, 0, 0, 0); · line 20207

Quoted 6 lines
kernel/bpf/verifier.c +1 -1
  		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

#5 lore raw

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

Quoted 83 lines · Daniel Borkmann
Quoted 36 lines · 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.

---
  kernel/bpf/verifier.c | 9 +++++++--
  1 file changed, 7 insertions(+), 2 deletions(-)
kernel/bpf/verifier.c +1 -0
index 963dfda81c06..784547aa40a8 100644
@@ -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;

kernel/bpf/verifier.c static const struct bpf_insn NOP = BPF_JMP_IMM(BPF_JA, 0, 0, 0); · line 20202

Quoted 10 lines
kernel/bpf/verifier.c +5 -1
+     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?

kernel/bpf/verifier.c +5 -2
index 245f1f3f1aec..16ba26295ec7 100644
@@ -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);

kernel/bpf/verifier.c static const struct bpf_insn NOP = BPF_JMP_IMM(BPF_JA, 0, 0, 0); · line 20206

Quoted 5 lines
kernel/bpf/verifier.c +1 -1
              if (err)
                      return err;
              insn_cnt--;
-             i--;
+             i -= (is_may_goto_0 && i > 0) ? 2 : 1;
Quoted 1 line

Maybe add a comment for this logic?

Adjusted both while applying.
Thanks!

author reviewer
#6 lore raw

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

In reply to Daniel Borkmann
Quoted 56 lines · Daniel Borkmann
Quoted 37 lines · 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.

---
  kernel/bpf/verifier.c | 9 +++++++--

  1 file changed, 7 insertions(+), 2 deletions(-)
kernel/bpf/verifier.c +1 -0
index 963dfda81c06..784547aa40a8 100644
@@ -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;

kernel/bpf/verifier.c static const struct bpf_insn NOP = · line 20203

Quoted 10 lines
kernel/bpf/verifier.c +5 -1
+    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?

kernel/bpf/verifier.c +0 -0
index 245f1f3f1aec..16ba26295ec7 100644

kernel/bpf/verifier.c static int opt_remove_dead_code(struct · line 20190

Quoted 6 lines
kernel/bpf/verifier.c +1 -0
@@ -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.

Quoted 17 lines
kernel/bpf/verifier.c +4 -2
  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;
Quoted 8 lines

kernel/bpf/verifier.c static const struct bpf_insn NOP = · line 20208

Quoted 6 lines
kernel/bpf/verifier.c +1 -1
           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!

Quoted 3 lines

Thanks,
Daniel

author reviewer
#7 lore raw

PATCH v2 3/3 selftests/bpf: Add some tests related to 'may_goto 0' insns

In reply to 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;
---
 .../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
tools/testing/selftests/bpf/prog_tests/verifier.c +4 -0
index 33cd3e035071..8a0e1ff8a2dc 100644
@@ -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); }
tools/testing/selftests/bpf/progs/verifier_may_goto_1.c new file +97 -0

97 lines not on this page · raw message

tools/testing/selftests/bpf/progs/verifier_may_goto_2.c new file +28 -0
new file mode 100644
index 000000000000..b891faf50660
@@ -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";
Signature · 1 line
2.43.5