bpf: Allow 'may_goto 0' instruction
Subsystems (4)
Yonghong Song
reviewercover 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
Yonghong Song
reviewerPATCH 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
@@ -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
Quoted 20 lines · Yonghong Song
Commit
011832b97b31("bpf: Introducemay_gotoinstruction") added support formay_gotoinsn. The 'may_goto0' 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_goto0' 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_goto0' insn to avoid verification failure for codes like the above.Reported-by Emil Tsalapatis <[email protected]>Signed-off-by Yonghong Song <[email protected]>---
[...]
Yonghong Song
reviewerPATCH 2/3 bpf: Remove 'may_goto 0' instruction
In reply to Yonghong SongSince '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
@@ -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
Re: [PATCH bpf-next 2/3] bpf: Remove 'may_goto 0' instruction
Quoted 16 lines · Yonghong Song
Since '
may_goto0' 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 ==0x0goto pc+2
r11 -= 1
*(u64 *)(r10 -8) = r11which is the pure overhead.
The following code patterns (from the previous commit) are also handled:
may_goto2
may_goto1
may_goto0
Quoted 5 lines
With this commit, the above three '
may_goto' insns are all eliminated.Signed-off-by Yonghong Song <[email protected]>---
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) = r11On 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@@ -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 ; +}
[...]
Re: [PATCH bpf-next 2/3] bpf: Remove 'may_goto 0' instruction
Quoted 65 lines · Eduard Zingerman
Quoted 16 lines · Yonghong Song
Since '
may_goto0' 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 ==0x0goto pc+2
r11 -= 1
*(u64 *)(r10 -8) = r11which is the pure overhead.
The following code patterns (from the previous commit) are also handled:
may_goto2
may_goto1
may_goto0Quoted 5 lines
With this commit, the above three '
may_goto' insns are all eliminated.Signed-off-by Yonghong Song <[email protected]>---
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) = r11On 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 <[email protected]>Quoted 27 lines
kernel/bpf/verifier.c | 36 ++++++++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+)kernel/bpf/verifier.c +16
-0@@ -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 toverifier_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
reviewerRe: [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_goto0' 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) = r11which is the pure overhead.
The following code patterns (from the previous commit) are also handled:
may_goto2
may_goto1
may_goto0Quoted 5 lines
With this commit, the above three '
may_goto' insns are all eliminated.Signed-off-by Yonghong Song <[email protected]>---
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) = r11On 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 <[email protected]>Quoted 26 lines
kernel/bpf/verifier.c | 36 ++++++++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+)kernel/bpf/verifier.c +15
-0@@ -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 toverifier_remove_insns().True,
but more generally I don't see whymay_gotoneeds 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 ofmay_goto+2, +1, +0
only the last one will be removed, I think,
butopt_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
Yonghong Song
reviewerPATCH 3/3 selftests/bpf: Add some tests related to 'may_goto 0' insns
In reply to Yonghong SongAdd 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
@@ -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
@@ -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
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_goto0' 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_goto2
may_goto1
may_goto0
r1 = 0
r2 = 0
r3 = 0The 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_goto5
r1 = 0
may_goto3
r2 = 0
may_goto1
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;Signed-off-by Yonghong Song <[email protected]>---
[...]
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 ) +{ + asmvolatile ( +".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); +}
[...]