BPF control flow graph and precision backtrack fixes
Subsystems (4)
Andrii Nakryiko
maintainerv2 cover BPF control flow graph and precision backtrack fixes
A small fix to BPF verifier's CFG logic around handling and reporting ldimm64 instructions. Patch #1 was previously submitted separately ([0]), and so this patch set supersedes that patch.
Second patch is fixing obscure corner case in mark_chain_precise() logic. See patch for details. Patch #3 adds a dedicated test, however fragile it might.
[0] https://patchwork.kernel.org/project/netdevbpf/patch/[email protected]/
Andrii Nakryiko (3):
bpf: handle ldimm64 properly in check_cfg()
bpf: fix precision backtracking instruction iteration selftests/bpf: add edge case backtracking logic test
include/linux/bpf.h | 8 +++- kernel/bpf/verifier.c | 48 +++++++++++++++---- .../selftests/bpf/progs/verifier_precision.c | 40 ++++++++++++++++ .../testing/selftests/bpf/verifier/ld_imm64.c | 8 ++-- 4 files changed, 89 insertions(+), 15 deletions(-)
Signature · 1 line
2.34.1
Andrii Nakryiko
maintainerPATCH v2 1/3 bpf: handle ldimm64 properly in check_cfg()
ldimm64 instructions are 16-byte long, and so have to be handled appropriately in check_cfg(), just like the rest of BPF verifier does.
This has implications in three places:
- when determining next instruction for non-jump instructions;
- when determining next instruction for callback address ldimm64
instructions (in visit_func_call_insn());
- when checking for unreachable instructions, where second half of
ldimm64 is expected to be unreachable;We take this also as an opportunity to report jump into the middle of ldimm64. And adjust few test_verifier tests accordingly.
--- include/linux/bpf.h | 8 ++++-- kernel/bpf/verifier.c | 27 ++++++++++++++----- .../testing/selftests/bpf/verifier/ld_imm64.c | 8 +++--- 3 files changed, 30 insertions(+), 13 deletions(-)
include/linux/bpf.h +6 -2
@@ -909,10 +909,14 @@ bpf_ctx_record_field_size(struct bpf_insn_access_aux *aux, u32 size) aux->ctx_field_size = size; } +static bool bpf_is_ldimm64 (const struct bpf_insn *insn) +{ +return insn->code == (BPF_LD |BPF_IMM |BPF_DW ); +} +static inline bool bpf_pseudo_func (const struct bpf_insn *insn) { -return insn->code == (BPF_LD |BPF_IMM |BPF_DW ) && - insn->src_reg ==BPF_PSEUDO_FUNC ; +return bpf_is_ldimm64 (insn) && insn->src_reg ==BPF_PSEUDO_FUNC ; }struct bpf_prog_ops {
kernel/bpf/verifier.c +20 -7
@@ -15439,15 +15439,16 @@ static int visit_func_call_insn(int t, struct bpf_insn *insns,struct bpf_verifier_env *env, bool visit_callee) { - int ret; + int ret, insn_sz; - ret =push_insn (t, t +1 ,FALLTHROUGH , env, false); + insn_sz =bpf_is_ldimm64 (&insns[t]) ?2 :1 ; + ret =push_insn (t, t + insn_sz,FALLTHROUGH , env, false);if (ret)return ret; -mark_prune_point (env, t +1 ); +mark_prune_point (env, t + insn_sz);/* when we exit from subprog, we need to record non-linear history */ -mark_jmp_point (env, t +1 ); +mark_jmp_point (env, t + insn_sz);if (visit_callee) {mark_prune_point (env, t);
@@ -15469,15 +15470,17 @@ static int visit_func_call_insn(int t, struct bpf_insn *insns,static int visit_insn (int t,struct bpf_verifier_env *env) {struct bpf_insn *insns = env->prog->insnsi, *insn = &insns[t]; -int ret, off; +int ret, off, insn_sz;if (bpf_pseudo_func (insn))return visit_func_call_insn (t, insns, env, true);/* All non-branch instructions have a single fall-through edge. */ if (BPF_CLASS (insn->code) !=BPF_JMP && -BPF_CLASS (insn->code) !=BPF_JMP32 ) -return push_insn (t, t +1 ,FALLTHROUGH , env, false); +BPF_CLASS (insn->code) !=BPF_JMP32 ) { + insn_sz =bpf_is_ldimm64 (insn) ?2 :1 ; +return push_insn (t, t + insn_sz,FALLTHROUGH , env, false); + }switch (BPF_OP (insn->code)) {case BPF_EXIT :
@@ -15607,11 +15610,21 @@ static int check_cfg(struct bpf_verifier_env *env) }for (i =0 ; i < insn_cnt; i++) { +struct bpf_insn *insn = &env->prog->insnsi[i]; +if (insn_state[i] !=EXPLORED ) {verbose (env,"unreachable insn %d\n" , i); ret = -EINVAL ; goto err_free; } +if (bpf_is_ldimm64 (insn)) { +if (insn_state[i +1 ] !=0 ) { +verbose (env,"jump into the middle of ldimm64 insn %d\n" , i); + ret = -EINVAL ; + goto err_free; + } + i++;/* skip second half of ldimm64 */ + } } ret =0 ;/* cfg looks good */
tools/testing/selftests/bpf/verifier/ld_imm64.c +4 -4
@@ -9,8 +9,8 @@BPF_MOV64_IMM (BPF_REG_0 ,2 ), BPF_EXIT_INSN(), }, - .errstr ="invalid BPF_LD_IMM insn" , - .errstr_unpriv = "R1 pointer comparison", + .errstr ="jump into the middle of ldimm64 insn 1" , + .errstr_unpriv = "jump into the middle of ldimm64 insn 1", .result = REJECT, }, {
@@ -23,8 +23,8 @@BPF_LD_IMM64 (BPF_REG_0 ,1 ), BPF_EXIT_INSN(), }, - .errstr ="invalid BPF_LD_IMM insn" , - .errstr_unpriv = "R1 pointer comparison", + .errstr ="jump into the middle of ldimm64 insn 1" , + .errstr_unpriv = "jump into the middle of ldimm64 insn 1", .result = REJECT, }, {
Signature · 1 line
2.34.1
Andrii Nakryiko
maintainerPATCH v2 2/3 bpf: fix precision backtracking instruction iteration
In reply to Andrii NakryikoFix an edge case in __mark_chain_precision() which prematurely stops backtracking instructions in a state if it happens that state's first and last instruction indexes are the same. This situations doesn't necessarily mean that there were no instructions simulated in a state, but rather that we starting from the instruction, jumped around a bit, and then ended up at the same instruction before checkpointing or marking precision.
To distinguish between these two possible situations, we need to consult jump history. If it's empty or contain a single record "bridging" parent state and first instruction of processed state, then we indeed backtracked all instructions in this state. But if history is not empty, we are definitely not done yet.
Move this logic inside get_prev_insn_idx() to contain it more nicely. Use -ENOENT return code to denote "we are out of instructions" situation.
This bug was exposed by verifier_loop1.c's bounded_recursion subtest, once the next fix in this patch set is applied.
--- kernel/bpf/verifier.c | 21 +++++++++++++++++++-- 1 file changed, 19 insertions(+), 2 deletions(-)
kernel/bpf/verifier.c +19 -2
@@ -3516,12 +3516,29 @@ static int push_jmp_history(struct bpf_verifier_env *env,/* Backtrack one insn at a time. If idx is not at the top of recorded * history then previous instruction came from straight line execution. +* Return -ENOENT if we exhausted all instructions within given state. +* +* It's legal to have a bit of a looping with the same starting and ending +* insn index within the same state, e.g.: 3->4->5->3, so just because current +* instruction index is the same as state's first_idx doesn't mean we are +* done. If there is still some jump history left, we should keep going. We +* need to take into account that we might have a jump history between given +* state's parent and itself, due to checkpointing. In this case, we'll have +* history entry recording a jump from last instruction of parent state and +* first instruction of given state. */ static int get_prev_insn_idx (struct bpf_verifier_state *st,int i,u32 *history) {u32 cnt = *history; +if (i == st->first_insn_idx) { +if (cnt ==0 ) +return -ENOENT ; +if (cnt ==1 && st->jmp_history[0 ].idx == i) +return -ENOENT ; + } +if (cnt && st->jmp_history[cnt -1 ].idx == i) { i = st->jmp_history[cnt -1 ].prev_idx; (*history)--;
@@ -4401,10 +4418,10 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)* Nothing to be tracked further in the parent state. */ return 0 ; -if (i == first_idx) -break ; subseq_idx = i; i =get_prev_insn_idx (st, i, &history); +if (i == -ENOENT ) +break ;if (i >= env->prog->len) {/* This can happen if backtracking reached insn 0 * and there are still reg_mask or stack_mask
Signature · 1 line
2.34.1
Andrii Nakryiko
maintainerPATCH v2 3/3 selftests/bpf: add edge case backtracking logic test
In reply to Andrii NakryikoAdd a dedicated selftests to try to set up conditions to have a state with same first and last instruction index, but it actually is a loop 3->4->1->2->3. This confuses mark_chain_precision() if verifier doesn't take into account jump history.
--- .../selftests/bpf/progs/verifier_precision.c | 40 +++++++++++++++++++ 1 file changed, 40 insertions(+)
tools/testing/selftests/bpf/progs/verifier_precision.c +40 -0
@@ -91,3 +91,43 @@ __naked int bpf_end_bswap(void) }#endif /* v4 instruction */ + +SEC("?raw_tp") +__success __log_level(2) +/* +* Without the bug fix there will be no history between "last_idx 3 first_idx 3" +* and "parent state regs=" lines. "R0_w=6" parts are here to help anchor +* expected log messages to the one specific mark_chain_precision operation. +* +* This is quite fragile: if verifier checkpointing heuristic changes, this +* might need adjusting. + */ +__msg("2: (07) r0 += 1 ; R0_w=6") +__msg("3: (35) if r0 >= 0xa goto pc+1") +__msg("mark_precise: frame0: last_idx 3 first_idx 3 subseq_idx -1") +__msg("mark_precise: frame0: regs=r0 stack= before 2: (07) r0 += 1") +__msg("mark_precise: frame0: regs=r0 stack= before 1: (07) r0 += 1") +__msg("mark_precise: frame0: regs=r0 stack= before 4: (05) goto pc-4") +__msg("mark_precise: frame0: regs=r0 stack= before 3: (35) if r0 >= 0xa goto pc+1") +__msg("mark_precise: frame0: parent state regs= stack=: R0_rw=P4") +__msg("3: R0_w=6") +__naked int state_loop_first_last_equal (void ) +{ + asmvolatile ( +"r0 = 0;" +"l0_%=:" +"r0 += 1;" +"r0 += 1;" +/* every few iterations we'll have a checkpoint here with +* first_idx == last_idx, potentially confusing precision +* backtracking logic +*/ +"if r0 >= 10 goto l1_%=;" /* checkpoint + mark_precise */ +"goto l0_%=;" +"l1_%=:" +"exit;" + ::: __clobber_common + ); +} + +char _license[] SEC("license") = "GPL";
Signature · 1 line
2.34.1
Re: [PATCH v2 bpf 3/3] selftests/bpf: add edge case backtracking logic test
Quoted 19 lines · Andrii Nakryiko
Add a dedicated selftests to try to set up conditions to have a state with same first and last instruction index, but it actually is a loop 3->4->1->2->3. This confuses
mark_chain_precision()if verifier doesn't take into account jump history.Signed-off-by Andrii Nakryiko <[email protected]>--- .../selftests/bpf/progs/verifier_precision.c | 40 +++++++++++++++++++ 1 file changed, 40 insertions(+)tools/testing/selftests/bpf/progs/verifier_precision.c +0
-0@@ -91,3 +91,43 @@ __naked int bpf_end_bswap(void) }#endif /* v4 instruction */
tools/testing/selftests/bpf/progs/verifier_precision.c __naked int bpf_end_bswap(void) · line 103
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_precision.c +10
-0+ +SEC("?raw_tp") +__success __log_level(2) +/* +* Without the bug fix there will be no history between "last_idx 3 first_idx 3" +* and "parent state regs=" lines. "R0_w=6" parts are here to help anchor +* expected log messages to the one specific mark_chain_precision operation. +* +* This is quite fragile: if verifier checkpointing heuristic changes, this +* might need adjusting.
Hmm, but that what__flag(BPF_F_TEST_STATE_FREQ)
supposed to address.
Quoted 7 lines
tools/testing/selftests/bpf/progs/verifier_precision.c +7
-0+*/ +__msg("2: (07) r0 += 1 ; R0_w=6") +__msg("3: (35) if r0 >= 0xa goto pc+1") +__msg("mark_precise: frame0: last_idx 3 first_idx 3 subseq_idx -1") +__msg("mark_precise: frame0: regs=r0 stack= before 2: (07) r0 += 1") +__msg("mark_precise: frame0: regs=r0 stack= before 1: (07) r0 += 1") +__msg ("mark_precise: frame0: regs=r0 stack= before 4: (05) goto pc-4" )
tools/testing/selftests/bpf/progs/verifier_precision.c __naked int bpf_end_bswap(void) · line 120
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_precision.c +10
-0+__msg("mark_precise: frame0: regs=r0 stack= before 3: (35) if r0 >= 0xa goto pc+1") +__msg("mark_precise: frame0: parent state regs= stack=: R0_rw=P4") +__msg("3: R0_w=6") +__naked int state_loop_first_last_equal (void ) +{ + asmvolatile ( +"r0 = 0;" +"l0_%=:" +"r0 += 1;" + "r0 += 1;"
That's why you had two ++ ?
Add state_freq and remove one of them?
Re: [PATCH v2 bpf 3/3] selftests/bpf: add edge case backtracking logic test
Quoted 20 lines · Alexei Starovoitov
Quoted 18 lines · Andrii Nakryiko
Add a dedicated selftests to try to set up conditions to have a state with same first and last instruction index, but it actually is a loop 3->4->1->2->3. This confuses
mark_chain_precision()if verifier doesn't take into account jump history.Signed-off-by Andrii Nakryiko <[email protected]>--- .../selftests/bpf/progs/verifier_precision.c | 40 +++++++++++++++++++ 1 file changed, 40 insertions(+)tools/testing/selftests/bpf/progs/verifier_precision.c +0
-0@@ -91,3 +91,43 @@ __naked int bpf_end_bswap(void) }
Quoted 15 lines
tools/testing/selftests/bpf/progs/verifier_precision.c __naked int bpf_end_bswap(void) · line 103
Quoted 11 lines
tools/testing/selftests/bpf/progs/verifier_precision.c +10
-0#endif /* v4 instruction */ + +SEC("?raw_tp") +__success __log_level(2) +/* +* Without the bug fix there will be no history between "last_idx 3 first_idx 3" +* and "parent state regs=" lines. "R0_w=6" parts are here to help anchor +* expected log messages to the one specific mark_chain_precision operation. +* +* This is quite fragile: if verifier checkpointing heuristic changes, this +* might need adjusting. Hmm, but that what
__flag(BPF_F_TEST_STATE_FREQ)
supposed to address.
When I was analysing and crafting the test I for some reason assumed I need to have a jump inside the state that won't trigger state checkpoint. But I think that's not necessary, just doing conditional jump and jumping back an instruction or two should do. With that yes, TEST_STATE_FREQ should be a better way to do this.
Quoted 21 lines
Quoted 8 lines
tools/testing/selftests/bpf/progs/verifier_precision.c +7
-0+*/ +__msg("2: (07) r0 += 1 ; R0_w=6") +__msg("3: (35) if r0 >= 0xa goto pc+1") +__msg("mark_precise: frame0: last_idx 3 first_idx 3 subseq_idx -1") +__msg("mark_precise: frame0: regs=r0 stack= before 2: (07) r0 += 1") +__msg("mark_precise: frame0: regs=r0 stack= before 1: (07) r0 += 1") +__msg ("mark_precise: frame0: regs=r0 stack= before 4: (05) goto pc-4" )tools/testing/selftests/bpf/progs/verifier_precision.c __naked int bpf_end_bswap(void) · line 120
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_precision.c +10
-0+__msg("mark_precise: frame0: regs=r0 stack= before 3: (35) if r0 >= 0xa goto pc+1") +__msg("mark_precise: frame0: parent state regs= stack=: R0_rw=P4") +__msg("3: R0_w=6") +__naked int state_loop_first_last_equal (void ) +{ + asmvolatile ( +"r0 = 0;" +"l0_%=:" +"r0 += 1;" + "r0 += 1;"That's why you had two ++ ?
Addstate_freqand remove one of them?
Re: [PATCH v2 bpf 3/3] selftests/bpf: add edge case backtracking logic test
Quoted 39 lines · Andrii Nakryiko
Quoted 20 lines · Alexei Starovoitov
Quoted 18 lines · Andrii Nakryiko
Add a dedicated selftests to try to set up conditions to have a state with same first and last instruction index, but it actually is a loop 3->4->1->2->3. This confuses
mark_chain_precision()if verifier doesn't take into account jump history.Signed-off-by Andrii Nakryiko <[email protected]>--- .../selftests/bpf/progs/verifier_precision.c | 40 +++++++++++++++++++ 1 file changed, 40 insertions(+)tools/testing/selftests/bpf/progs/verifier_precision.c +0
-0@@ -91,3 +91,43 @@ __naked int bpf_end_bswap(void) }Quoted 15 lines
tools/testing/selftests/bpf/progs/verifier_precision.c __naked int bpf_end_bswap(void) · line 103
Quoted 11 lines
tools/testing/selftests/bpf/progs/verifier_precision.c +10
-0#endif /* v4 instruction */ + +SEC("?raw_tp") +__success __log_level(2) +/* +* Without the bug fix there will be no history between "last_idx 3 first_idx 3" +* and "parent state regs=" lines. "R0_w=6" parts are here to help anchor +* expected log messages to the one specific mark_chain_precision operation. +* +* This is quite fragile: if verifier checkpointing heuristic changes, this +* might need adjusting. Hmm, but that what
__flag(BPF_F_TEST_STATE_FREQ)
supposed to address.
Quoted 5 lines
When I was analysing and crafting the test I for some reason assumed I need to have a jump inside the state that won't trigger state checkpoint. But I think that's not necessary, just doing conditional jump and jumping back an instruction or two should do. With that yes,
TEST_STATE_FREQshould be a better way to do this.
Ah, ok, TEST_STATE_FREQ won't work. It triggers state checkpointing both at conditional jump instruction and on its target, because target is prune point.
So I think this test has to be the way it is.
Quoted 22 lines
Quoted 22 lines
Quoted 9 lines
tools/testing/selftests/bpf/progs/verifier_precision.c +7
-0+*/ +__msg("2: (07) r0 += 1 ; R0_w=6") +__msg("3: (35) if r0 >= 0xa goto pc+1") +__msg("mark_precise: frame0: last_idx 3 first_idx 3 subseq_idx -1") +__msg("mark_precise: frame0: regs=r0 stack= before 2: (07) r0 += 1") +__msg("mark_precise: frame0: regs=r0 stack= before 1: (07) r0 += 1") +__msg ("mark_precise: frame0: regs=r0 stack= before 4: (05) goto pc-4" )tools/testing/selftests/bpf/progs/verifier_precision.c __naked int bpf_end_bswap(void) · line 120
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_precision.c +10
-0+__msg("mark_precise: frame0: regs=r0 stack= before 3: (35) if r0 >= 0xa goto pc+1") +__msg("mark_precise: frame0: parent state regs= stack=: R0_rw=P4") +__msg("3: R0_w=6") +__naked int state_loop_first_last_equal (void ) +{ + asmvolatile ( +"r0 = 0;" +"l0_%=:" +"r0 += 1;" + "r0 += 1;"That's why you had two ++ ?
Addstate_freqand remove one of them?
Re: [PATCH v2 bpf 3/3] selftests/bpf: add edge case backtracking logic test
Quoted 8 lines · Andrii Nakryiko
Quoted 7 lines
When I was analysing and crafting the test I for some reason assumed I need to have a jump inside the state that won't trigger state checkpoint. But I think that's not necessary, just doing conditional jump and jumping back an instruction or two should do. With that yes,
TEST_STATE_FREQshould be a better way to do this.
Quoted 5 lines
Ah, ok,
TEST_STATE_FREQwon't work. It triggers state checkpointing both at conditional jump instruction and on its target, because target is prune point.So I think this test has to be the way it is.
I see.
I was about to apply it, but then noticed:
numamove_bpf-numamove_bpf.o |migrate_misplaced_page |success -> failure (!!)|-100.00 %
veristat is not known for sporadic failures.
Is this a real issue?
Re: [PATCH v2 bpf 3/3] selftests/bpf: add edge case backtracking logic test
Quoted 17 lines · Alexei Starovoitov
Quoted 8 lines · Andrii Nakryiko
Quoted 7 lines
When I was analysing and crafting the test I for some reason assumed I need to have a jump inside the state that won't trigger state checkpoint. But I think that's not necessary, just doing conditional jump and jumping back an instruction or two should do. With that yes,
TEST_STATE_FREQshould be a better way to do this.Quoted 5 lines
Ah, ok,
TEST_STATE_FREQwon't work. It triggers state checkpointing both at conditional jump instruction and on its target, because target is prune point.So I think this test has to be the way it is.
Quoted 7 lines
I see.
I was about to apply it, but then noticed:
numamove_bpf-numamove_bpf.o |migrate_misplaced_page |success -> failure (!!)|-100.00 %veristat is not known for sporadic failures.
Is this a real issue?
No idea what this is, I don't have it in my local object files, will need to regenerate them and check.
Re: [PATCH v2 bpf 3/3] selftests/bpf: add edge case backtracking logic test
Quoted 25 lines · Andrii Nakryiko
Quoted 22 lines · Alexei Starovoitov
Quoted 8 lines · Andrii Nakryiko
Quoted 7 lines
When I was analysing and crafting the test I for some reason assumed I need to have a jump inside the state that won't trigger state checkpoint. But I think that's not necessary, just doing conditional jump and jumping back an instruction or two should do. With that yes,
TEST_STATE_FREQshould be a better way to do this.Quoted 5 lines
Ah, ok,
TEST_STATE_FREQwon't work. It triggers state checkpointing both at conditional jump instruction and on its target, because target is prune point.So I think this test has to be the way it is.
I see.
I was about to apply it, but then noticed:
numamove_bpf-numamove_bpf.o |migrate_misplaced_page |success -> failure (!!)|-100.00 %
Quoted 5 lines
Quoted 2 lines
veristat is not known for sporadic failures.
Is this a real issue?No idea what this is, I don't have it in my local object files, will need to regenerate them and check.
libbpf: prog 'migrate_misplaced_page_exit': failed to find kernel BTF type ID of 'migrate_misplaced_page': -3
It fails also on bpf-next/master.
I think CI compares with the last state before net/net-next merge, and now this tool (it's from libbpf-tools) fails to find migrate_misplaced_page kernel function, apparently.
So veristat itself doesn't have sporadic failures, but our CI setup is not 100% reliable, it seems.
This series was applied to bpf/bpf.git (master) by Alexei Starovoitov <[email protected]>:
Hello:
This series was applied to bpf/bpf.git (master)
by Alexei Starovoitov <[email protected]>:
Quoted 8 lines · On Thu, 9 Nov 2023 16:26:35 -0800 you wrote:
A small fix to BPF verifier's CFG logic around handling and reporting ldimm64 instructions. Patch #1 was previously submitted separately ([0]), and so this patch set supersedes that patch.
Second patch is fixing obscure corner case in
mark_chain_precise()logic. See patch for details. Patch #3 adds a dedicated test, however fragile it might.[...]
Here is the summary with links:
- [v2,bpf,1/3] bpf: handle ldimm64 properly in check_cfg()
https://git.kernel.org/bpf/bpf/c/3feb263bb516 - [v2,bpf,2/3] bpf: fix precision backtracking instruction iteration https://git.kernel.org/bpf/bpf/c/4bb7ea946a37 - [v2,bpf,3/3] selftests/bpf: add edge case backtracking logic test https://git.kernel.org/bpf/bpf/c/62ccdb11d3c6
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html