Skip to contentSkip to conversation

bpf: Allow 'may_goto 0' instruction

PATCH Superseded Yonghong Song 3 participants 9 messages Jan 16, 2025 – Jan 17, 2025

Subsystems (4)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Yonghong Song

author reviewer
#0 lore raw

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.

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

PATCH 1/3 bpf: Allow 'may_goto 0' instruction

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 b8ca227c78af..edf3cc42a220 100644
@@ -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);
Signature · 1 line
2.43.5
maintainer Acked-by on v1 1/3
#2 lore raw
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 2/3 bpf: Remove 'may_goto 0' instruction

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 | 36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)
kernel/bpf/verifier.c +36 -0
index edf3cc42a220..72b474bfba2d 100644
@@ -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);
Signature · 1 line
2.43.5
maintainer Acked-by on v1 2/3
#4 lore raw

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

Quoted 16 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

Quoted 5 lines

With this commit, the above three 'may_goto' insns are all eliminated.

---

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.

Quoted 21 lines
 kernel/bpf/verifier.c | 36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)
kernel/bpf/verifier.c +10 -0
index edf3cc42a220..72b474bfba2d 100644
@@ -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;
+

kernel/bpf/verifier.c static int opt_remove_nops(struct bpf_verifier_env *env) · line 20155

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+		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().

Quoted 13 lines
kernel/bpf/verifier.c +13 -0
+				if (err)
+					return err;
+				removed_cnt++;
+			}
+			j--;
+		}
+
+		insn_cnt -= removed_cnt;
+		i = last_may_goto - removed_cnt;
+	}
+
+	return 0;
+}

[...]

#5 lore raw

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

Quoted 65 lines · Eduard Zingerman
Quoted 16 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

Quoted 5 lines

With this commit, the above three 'may_goto' insns are all eliminated.

---

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.

Quoted 27 lines
 kernel/bpf/verifier.c | 36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)
kernel/bpf/verifier.c +16 -0
index edf3cc42a220..72b474bfba2d 100644
@@ -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;
Quoted 8 lines

kernel/bpf/verifier.c static int opt_remove_nops(struct bpf_verifier_env *env) · line 20155

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

author reviewer
#6 lore raw

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

Quoted 86 lines · Alexei Starovoitov
Quoted 62 lines · Eduard Zingerman
Quoted 16 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

Quoted 5 lines

With this commit, the above three 'may_goto' insns are all eliminated.

---

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.

Quoted 26 lines
  kernel/bpf/verifier.c | 36 ++++++++++++++++++++++++++++++++++++
  1 file changed, 36 insertions(+)
kernel/bpf/verifier.c +15 -0
index edf3cc42a220..72b474bfba2d 100644
@@ -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;
+             }
+
Quoted 8 lines

kernel/bpf/verifier.c static int opt_remove_nops(struct bpf_verifier_env *env) · line 20155

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

(quoted diff) +1 -1
-                 i--;
+                 i -= 2;
Quoted 1 line

will do ?

Okay. Let me give a try.

Quoted 2 lines

pw-bot: cr

author reviewer
#7 lore raw

PATCH 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
maintainer Acked-by on v1 3/3
#8 lore raw

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

Quoted 30 lines · 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:

Quoted 6 lines
   int i, tmp[3];
   for (i = 0; i < 3; i++)
       tmp[i] = 0;

---

[...]

Quoted 11 lines
tools/testing/selftests/bpf/progs/verifier_may_goto_1.c new file +11 -0
+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];"

tools/testing/selftests/bpf/progs/verifier_may_goto_1.c line 67

Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_may_goto_1.c new file +10 -0
+	".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 :)

Quoted 2 lines
(quoted diff) +2 -0
+	: __clobber_all);
+}

[...]