Refactor verifier prune and jump point handling
Andrii Nakryiko
maintainerv2 cover Refactor verifier prune and jump point handling
Disentangle prune and jump points in BPF verifier code. They are conceptually independent but currently coupled together. This small patch set refactors related code and make it possible to have some instruction marked as pruning or jump point independently.
Besides just conceptual cleanliness, this allows to remove unnecessary jump points (saving a tiny bit of performance and memory usage, potentially), and even more importantly it allows for clean extension of special pruning points, similarly to how it's done for BPF_FUNC_timer_set_callback. This will be used by future patches implementing open-coded BPF iterators.
v1->v2:
- clarified path #3 commit message and a comment in the code (John);
- added back mark_jmp_point() to right after subprog call to record non-linear implicit jump from BPF_EXIT to right after CALL <subprog>.
Andrii Nakryiko (3):
bpf: decouple prune and jump points
bpf: mostly decouple jump history management from is_state_visited()
bpf: remove unnecessary prune and jump points
include/linux/bpf_verifier.h | 1 + kernel/bpf/verifier.c | 108 ++++++++++++++++++++--------------- 2 files changed, 64 insertions(+), 45 deletions(-)
Signature · 1 line
2.30.2
Andrii Nakryiko
maintainerPATCH v2 1/3 bpf: decouple prune and jump points
BPF verifier marks some instructions as prune points. Currently these prune points serve two purposes.
It's a point where verifier tries to find previously verified state and check current state's equivalence to short circuit verification for current code path.
But also currently it's a point where jump history, used for precision backtracking, is updated. This is done so that non-linear flow of execution could be properly backtracked.
Such coupling is coincidental and unnecessary. Some prune points are not part of some non-linear jump path, so don't need update of jump history. On the other hand, not all instructions which have to be recorded in jump history necessarily are good prune points.
This patch splits prune and jump points into independent flags. Currently all prune points are marked as jump points to minimize amount of changes in this patch, but next patch will perform some optimization of prune vs jmp point placement.
No functional changes are intended.
--- include/linux/bpf_verifier.h | 1 + kernel/bpf/verifier.c | 57 +++++++++++++++++++++++++++--------- 2 files changed, 44 insertions(+), 14 deletions(-)
include/linux/bpf_verifier.h +1 -0
@@ -452,6 +452,7 @@ struct bpf_insn_aux_data {/* below fields are initialized once */ unsigned int orig_idx;/* original instruction index */ bool prune_point; +bool jmp_point; };#define MAX_USED_MAPS 64/* max number of maps accessed by one eBPF program */
kernel/bpf/verifier.c +43 -14
127 lines not on this page · raw message
Signature · 1 line
2.30.2
Andrii Nakryiko
maintainerPATCH v2 2/3 bpf: mostly decouple jump history management from is_state_visited()
In reply to Andrii NakryikoJump history updating and state equivalence checks are conceptually independent, so move push_jmp_history() out of is_state_visited(). Also make a decision whether to perform state equivalence checks or not one layer higher in do_check(), keeping is_state_visited() unconditionally performing state checks.
push_jmp_history() should be performed after state checks. There is just one small non-uniformity. When is_state_visited() finds already validated equivalent state, it propagates precision marks to current state's parent chain. For this to work correctly, jump history has to be updated, so is_state_visited() is doing that internally.
But if no equivalent verified state is found, jump history has to be updated in a newly cloned child state, so is_jmp_point()
+ push_jmp_history() is performed after is_state_visited() exited with zero result, which means "proceed with validation".
This change has no functional changes. It's not strictly necessary, but feels right to decouple these two processes.
--- kernel/bpf/verifier.c | 49 +++++++++++++++++++++++-------------------- 1 file changed, 26 insertions(+), 23 deletions(-)
kernel/bpf/verifier.c +26 -23
@@ -13343,13 +13343,6 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)int i, j, err, states_cnt =0 ;bool add_new_state = env->test_state_freq ? true : false; - cur->last_insn_idx = env->prev_insn_idx; -if (!is_prune_point (env, insn_idx)) -/* this 'insn_idx' instruction wasn't marked, so we will not -* be doing state search here -*/ -return push_jmp_history (env, cur); -/* bpf progs typically have pruning point every 4 instructions * http://vger.kernel.org/bpfconf2019.html#session-1 * Do not add new state for future pruning if the verifier hasn't seen
@@ -13484,10 +13477,10 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx) env->max_states_per_insn = states_cnt;if (!env->bpf_capable && states_cnt >BPF_COMPLEXITY_LIMIT_STATES ) -return push_jmp_history (env, cur); +return 0 ;if (!add_new_state) -return push_jmp_history (env, cur); +return 0 ;/* There were no equivalent states, remember the current one. * Technically the current state is not proven to be safe yet,
@@ -13627,21 +13620,31 @@ static int do_check(struct bpf_verifier_env *env)return -E2BIG ; } - err =is_state_visited (env, env->insn_idx); -if (err <0 ) -return err; -if (err ==1 ) { -/* found equivalent state, can prune the search */ -if (env->log.level &BPF_LOG_LEVEL ) { -if (do_print_state) -verbose (env,"\nfrom %d to %d%s: safe\n" , - env->prev_insn_idx, env->insn_idx, - env->cur_state->speculative ? -" (speculative execution)" :"" ); -else -verbose (env,"%d: safe\n" , env->insn_idx); + state->last_insn_idx = env->prev_insn_idx; + +if (is_prune_point (env, env->insn_idx)) { + err =is_state_visited (env, env->insn_idx); +if (err <0 ) +return err; +if (err ==1 ) { +/* found equivalent state, can prune the search */ +if (env->log.level &BPF_LOG_LEVEL ) { +if (do_print_state) +verbose (env,"\nfrom %d to %d%s: safe\n" , + env->prev_insn_idx, env->insn_idx, + env->cur_state->speculative ? +" (speculative execution)" :"" ); +else +verbose (env,"%d: safe\n" , env->insn_idx); + } + goto process_bpf_exit; } - goto process_bpf_exit; + } + +if (is_jmp_point (env, env->insn_idx)) { + err =push_jmp_history (env, state); +if (err) +return err; }if (signal_pending (current))
Signature · 1 line
2.30.2
Andrii Nakryiko
maintainerPATCH v2 3/3 bpf: remove unnecessary prune and jump points
In reply to Andrii NakryikoDon't mark some instructions as jump points when there are actually no jumps and instructions are just processed sequentially. Such case is handled naturally by precision backtracking logic without the need to update jump history. See get_prev_insn_idx(). It goes back linearly by one instruction, unless current top of jmp_history is pointing to current instruction. In such case we use st->jmp_history[cnt - 1].prev_idx to find instruction from which we jumped to the current instruction non-linearly.
Also remove both jump and prune point marking for instruction right after unconditional jumps, as program flow can get to the instruction right after unconditional jump instruction only if there is a jump to that instruction from somewhere else in the program. In such case we'll mark such instruction as prune/jump point because it's a destination of a jump.
This change has no changes in terms of number of instructions or states processes across Cilium and selftests programs.
--- kernel/bpf/verifier.c | 34 ++++++++++------------------------ 1 file changed, 10 insertions(+), 24 deletions(-)
kernel/bpf/verifier.c +10 -24
@@ -12228,13 +12228,12 @@ static int visit_func_call_insn(int t, int insn_cnt,if (ret)return ret; -if (t +1 < insn_cnt) { -mark_prune_point (env, t +1 ); -mark_jmp_point (env, t +1 ); - } +mark_prune_point (env, t +1 ); +/* when we exit from subprog, we need to record non-linear history */ +mark_jmp_point (env, t +1 ); +if (visit_callee) {mark_prune_point (env, t); -mark_jmp_point (env, t); ret = push_insn(t, t + insns[t].imm + 1, BRANCH, env,/* It's ok to allow recursion from CFG point of * view. __check_func_call() will do the actual
@@ -12268,15 +12267,13 @@ static int visit_insn(int t, int insn_cnt, struct bpf_verifier_env *env)return DONE_EXPLORING ;case BPF_CALL : -if (insns[t].imm == BPF_FUNC_timer_set_callback) { -/* Mark this call insn to trigger is_state_visited() check -* before call itself is processed by __check_func_call(). -* Otherwise new async state will be pushed for further -* exploration. +if (insns[t].imm == BPF_FUNC_timer_set_callback) +/* Mark this call insn as a prune point to trigger +* is_state_visited() check before call itself is +* processed by __check_func_call(). Otherwise new +* async state will be pushed for further exploration. */ mark_prune_point (env, t); -mark_jmp_point (env, t); - }return visit_func_call_insn (t, insn_cnt, insns, env, insns[t].src_reg ==BPF_PSEUDO_CALL );
@@ -12290,26 +12287,15 @@ static int visit_insn(int t, int insn_cnt, struct bpf_verifier_env *env)if (ret)return ret; -/* unconditional jmp is not a good pruning point, -* but it's marked, since backtracking needs -* to record jmp history in is_state_visited(). -*/ mark_prune_point (env, t + insns[t].off +1 );mark_jmp_point (env, t + insns[t].off +1 ); -/* tell verifier to check for equivalent states -* after every call and jump -*/ -if (t +1 < insn_cnt) { -mark_prune_point (env, t +1 ); -mark_jmp_point (env, t +1 ); - }return ret;default :/* conditional jump with two edges */ mark_prune_point (env, t); -mark_jmp_point (env, t); + ret =push_insn (t, t +1 ,FALLTHROUGH , env, true);if (ret)return ret;
Signature · 1 line
2.30.2
RE: [PATCH v2 bpf-next 3/3] bpf: remove unnecessary prune and jump points
Quoted 16 lines · Andrii Nakryiko
Don't mark some instructions as jump points when there are actually no jumps and instructions are just processed sequentially. Such case is handled naturally by precision backtracking logic without the need to update jump history. See
get_prev_insn_idx(). It goes back linearly by one instruction, unless current top ofjmp_historyis pointing to current instruction. In such case we usest->jmp_history[cnt - 1].prev_idxto find instruction from which we jumped to the current instruction non-linearly.Also remove both jump and prune point marking for instruction right after unconditional jumps, as program flow can get to the instruction right after unconditional jump instruction only if there is a jump to that instruction from somewhere else in the program. In such case we'll mark such instruction as prune/jump point because it's a destination of a jump.
Quoted 5 lines
This change has no changes in terms of number of instructions or states processes across Cilium and selftests programs.
Signed-off-by Andrii Nakryiko <[email protected]>---
Thanks.
Re: [PATCH v2 bpf-next 3/3] bpf: remove unnecessary prune and jump points
In reply to Andrii NakryikoQuoted 30 lines · Andrii Nakryiko
Don't mark some instructions as jump points when there are actually no jumps and instructions are just processed sequentially. Such case is handled naturally by precision backtracking logic without the need to update jump history. See
get_prev_insn_idx(). It goes back linearly by one instruction, unless current top ofjmp_historyis pointing to current instruction. In such case we usest->jmp_history[cnt - 1].prev_idxto find instruction from which we jumped to the current instruction non-linearly.Also remove both jump and prune point marking for instruction right after unconditional jumps, as program flow can get to the instruction right after unconditional jump instruction only if there is a jump to that instruction from somewhere else in the program. In such case we'll mark such instruction as prune/jump point because it's a destination of a jump.
This change has no changes in terms of number of instructions or states processes across Cilium and selftests programs.
Signed-off-by Andrii Nakryiko <[email protected]>--- kernel/bpf/verifier.c | 34 ++++++++++------------------------ 1 file changed, 10 insertions(+), 24 deletions(-)kernel/bpf/verifier.c +0
-0@@ -12228,13 +12228,12 @@ static int visit_func_call_insn(int t, int insn_cnt,if (ret)
kernel/bpf/verifier.c static int visit_func_call_insn(int t, int insn_cnt, · line 12234
Quoted 10 lines
kernel/bpf/verifier.c +4
-4return ret; -if (t +1 < insn_cnt) { -mark_prune_point (env, t +1 ); -mark_jmp_point (env, t +1 ); - } +mark_prune_point (env, t +1 ); +/* when we exit from subprog, we need to record non-linear history */ +mark_jmp_point (env, t +1 ); +
With this we probably should remove 'insn_cnt' from visit_func_call_insn(). and in-turn from visit_insn() as well.
Pls consider as a follow up.
Re: [PATCH v2 bpf-next 3/3] bpf: remove unnecessary prune and jump points
Quoted 34 lines · Alexei Starovoitov
Quoted 32 lines · Andrii Nakryiko
Don't mark some instructions as jump points when there are actually no jumps and instructions are just processed sequentially. Such case is handled naturally by precision backtracking logic without the need to update jump history. See
get_prev_insn_idx(). It goes back linearly by one instruction, unless current top ofjmp_historyis pointing to current instruction. In such case we usest->jmp_history[cnt - 1].prev_idxto find instruction from which we jumped to the current instruction non-linearly.Also remove both jump and prune point marking for instruction right after unconditional jumps, as program flow can get to the instruction right after unconditional jump instruction only if there is a jump to that instruction from somewhere else in the program. In such case we'll mark such instruction as prune/jump point because it's a destination of a jump.
This change has no changes in terms of number of instructions or states processes across Cilium and selftests programs.
Signed-off-by Andrii Nakryiko <[email protected]>--- kernel/bpf/verifier.c | 34 ++++++++++------------------------ 1 file changed, 10 insertions(+), 24 deletions(-)kernel/bpf/verifier.c +0
-0@@ -12228,13 +12228,12 @@ static int visit_func_call_insn(int t, int insn_cnt,if (ret)return ret;
Quoted 12 lines
kernel/bpf/verifier.c static int visit_func_call_insn(int t, int insn_cnt, · line 12234
Quoted 8 lines
kernel/bpf/verifier.c +4
-4-if (t +1 < insn_cnt) { -mark_prune_point (env, t +1 ); -mark_jmp_point (env, t +1 ); - } +mark_prune_point (env, t +1 ); +/* when we exit from subprog, we need to record non-linear history */ +mark_jmp_point (env, t +1 ); +With this we probably should remove '
insn_cnt' fromvisit_func_call_insn(). and in-turn fromvisit_insn()as well.
Pls consider as a follow up.
Yep, will do, didn't notice it's not needed anymore.
BTW, no one asked why it was ok to drop the if (t + 1 < insns_cnt) check, I was a bit surprised. But this is because push_insns() already validates that t+1 is correct and doesn't go beyond the insns array, so this was not needed in the first place.
Re: [PATCH v2 bpf-next 3/3] bpf: remove unnecessary prune and jump points
Quoted 50 lines · Andrii Nakryiko
Quoted 34 lines · Alexei Starovoitov
Quoted 32 lines · Andrii Nakryiko
Don't mark some instructions as jump points when there are actually no jumps and instructions are just processed sequentially. Such case is handled naturally by precision backtracking logic without the need to update jump history. See
get_prev_insn_idx(). It goes back linearly by one instruction, unless current top ofjmp_historyis pointing to current instruction. In such case we usest->jmp_history[cnt - 1].prev_idxto find instruction from which we jumped to the current instruction non-linearly.Also remove both jump and prune point marking for instruction right after unconditional jumps, as program flow can get to the instruction right after unconditional jump instruction only if there is a jump to that instruction from somewhere else in the program. In such case we'll mark such instruction as prune/jump point because it's a destination of a jump.
This change has no changes in terms of number of instructions or states processes across Cilium and selftests programs.
Signed-off-by Andrii Nakryiko <[email protected]>--- kernel/bpf/verifier.c | 34 ++++++++++------------------------ 1 file changed, 10 insertions(+), 24 deletions(-)kernel/bpf/verifier.c +0
-0@@ -12228,13 +12228,12 @@ static int visit_func_call_insn(int t, int insn_cnt,if (ret)return ret;Quoted 12 lines
kernel/bpf/verifier.c static int visit_func_call_insn(int t, int insn_cnt, · line 12234
Quoted 8 lines
kernel/bpf/verifier.c +4
-4-if (t +1 < insn_cnt) { -mark_prune_point (env, t +1 ); -mark_jmp_point (env, t +1 ); - } +mark_prune_point (env, t +1 ); +/* when we exit from subprog, we need to record non-linear history */ +mark_jmp_point (env, t +1 ); +With this we probably should remove '
insn_cnt' fromvisit_func_call_insn(). and in-turn fromvisit_insn()as well.
Pls consider as a follow up.
Quoted 1 line
Yep, will do, didn't notice it's not needed anymore.
Thanks
Quoted 4 lines
BTW, no one asked why it was ok to drop the
if (t + 1 < insns_cnt)check, I was a bit surprised. But this is becausepush_insns()already validates that t+1 is correct and doesn't go beyond the insns array, so this was not needed in the first place.
Correct. I read the code the same way.
I was a bit concerned whether insn_cnt is always equal to env->prog->len. I thought we're tightening insn_cnt to be the subprog insn_cnt only. But that doesn't look to be the case.
So looks safe to remove that 'if' and hence insn_cnt is useless too, since it's the same as env->prog->len.
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Hello:
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Quoted 5 lines · On Tue, 6 Dec 2022 15:33:42 -0800 you wrote:
Disentangle prune and jump points in BPF verifier code. They are conceptually independent but currently coupled together. This small patch set refactors related code and make it possible to have some instruction marked as pruning or jump point independently.
Quoted 7 lines
Besides just conceptual cleanliness, this allows to remove unnecessary jump points (saving a tiny bit of performance and memory usage, potentially), and even more importantly it allows for clean extension of special pruning points, similarly to how it's done for
BPF_FUNC_timer_set_callback. This will be used by future patches implementing open-coded BPF iterators.[...]
Here is the summary with links:
- [v2,bpf-next,1/3] bpf: decouple prune and jump points
https://git.kernel.org/bpf/bpf-next/c/bffdeaa8a5af
- [v2,bpf-next,2/3] bpf: mostly decouple jump history management from is_state_visited()
https://git.kernel.org/bpf/bpf-next/c/a095f421057e - [v2,bpf-next,3/3] bpf: remove unnecessary prune and jump points https://git.kernel.org/bpf/bpf-next/c/618945fbed50
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html