bpf: Allow 'may_goto 0' instruction
Subsystems (4)
Yonghong Song
reviewerv2 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
Yonghong Song
reviewerPATCH 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
@@ -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
Re: [PATCH bpf-next v2 1/3] bpf: Allow 'may_goto 0' instruction in verifier
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]>Acked-by Eduard Zingerman <[email protected]>Signed-off-by Yonghong Song <[email protected]>
Yonghong Song
reviewerPATCH v2 2/3 bpf: Remove 'may_goto 0' instruction in opt_remove_nops()
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 | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-)
kernel/bpf/verifier.c +7 -2
@@ -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
Daniel Borkmann
maintainerRe: [PATCH bpf-next v2 2/3] bpf: Remove 'may_goto 0' instruction in opt_remove_nops()
Quoted 36 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_goto0With this commit, the above three '
may_goto' insns are all eliminated.Signed-off-by Yonghong Song <[email protected]>--- kernel/bpf/verifier.c | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-)kernel/bpf/verifier.c +1
-0@@ -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
@@ -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
-1err =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()
Quoted 83 lines · Daniel Borkmann
Quoted 36 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_goto0With this commit, the above three '
may_goto' insns are all eliminated.Signed-off-by Yonghong Song <[email protected]>--- kernel/bpf/verifier.c | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-)kernel/bpf/verifier.c +1
-0@@ -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_0stack var?kernel/bpf/verifier.c +5
-2@@ -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
-1if (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!
Yonghong Song
reviewerRe: [PATCH bpf-next v2 2/3] bpf: Remove 'may_goto 0' instruction in opt_remove_nops()
In reply to Daniel BorkmannQuoted 56 lines · Daniel Borkmann
Quoted 37 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_goto0With this commit, the above three '
may_goto' insns are all eliminated.Signed-off-by Yonghong Song <[email protected]>---
kernel/bpf/verifier.c| 9 +++++++--1 file changed, 7 insertions(+), 2 deletions(-)kernel/bpf/verifier.c +1
-0@@ -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_0stack var?kernel/bpf/verifier.c +0
-0
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
-2static 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
-1err = 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
Yonghong Song
reviewerPATCH v2 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