bpf: Refactor check_cfg to use a structured loop.
PATCH v2 1/1 bpf: Refactor check_cfg to use a structured loop.
The current implementation uses a number of gotos to implement a loop and different paths within the loop, which makes the code less readable than it would be with an explicit while-loop. This patch also replaces a chain of if/if-elses keyed on the same expression with a switch statement.
No change in behaviour is intended.
--- kernel/bpf/verifier.c | 179 ++++++++++++++++++++++-------------------- 1 file changed, 95 insertions(+), 84 deletions(-)
kernel/bpf/verifier.c +95 -84
@@ -8047,6 +8047,11 @@ static void init_explored_state(struct bpf_verifier_env *env, int idx) env->insn_aux_data[idx].prune_point = true; } +enum { +DONE_EXPLORING =0 , +KEEP_EXPLORING =1 , +}; +/* t, w, e - match pseudo-code above: * t - index of current instruction * w - next instruction
@@ -8059,10 +8064,10 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env,int *insn_state = env->cfg.insn_state;if (e ==FALLTHROUGH && insn_state[t] >= (DISCOVERED |FALLTHROUGH )) -return 0 ; +return DONE_EXPLORING ;if (e ==BRANCH && insn_state[t] >= (DISCOVERED |BRANCH )) -return 0 ; +return DONE_EXPLORING ;if (w <0 || w >= env->prog->len) {verbose_linfo (env, t,"%d: " , t);
@@ -8081,10 +8086,10 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env,if (env->cfg.cur_stack >= env->prog->len)return -E2BIG ; insn_stack[env->cfg.cur_stack++] = w; -return 1 ; +return KEEP_EXPLORING ; }else if ((insn_state[w] &0xF0 ) ==DISCOVERED ) {if (loop_ok && env->bpf_capable) -return 0 ; +return DONE_EXPLORING ;verbose_linfo (env, t,"%d: " , t);verbose_linfo (env, w,"%d: " , w);verbose (env,"back-edge from insn %d to %d\n" , t, w);
@@ -8096,7 +8101,74 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env,verbose (env,"insn state internal bug\n" );return -EFAULT ; } -return 0 ; +return DONE_EXPLORING ; +} + +/* Visits the instruction at index t and returns one of the following: +* < 0 - an error occurred +* DONE_EXPLORING - the instruction was fully explored +* KEEP_EXPLORING - there is still work to be done before it is fully explored +*/ +static int visit_insn (int t,int insn_cnt,struct bpf_verifier_env *env) +{ +struct bpf_insn *insns = env->prog->insnsi; +int ret; + +/* All non-branch instructions have a single fall-through edge. */ +if (BPF_CLASS (insns[t].code) !=BPF_JMP && +BPF_CLASS (insns[t].code) !=BPF_JMP32 ) +return push_insn (t, t +1 ,FALLTHROUGH , env, false); + +switch (BPF_OP (insns[t].code)) { +case BPF_EXIT : +return DONE_EXPLORING ; + +case BPF_CALL : + ret =push_insn (t, t +1 ,FALLTHROUGH , env, false); +if (ret) +return ret; + +if (t +1 < insn_cnt) +init_explored_state (env, t +1 ); +if (insns[t].src_reg ==BPF_PSEUDO_CALL ) { +init_explored_state (env, t); + ret =push_insn (t, t + insns[t].imm +1 ,BRANCH , + env, false); + } +return ret; + +case BPF_JA : +if (BPF_SRC (insns[t].code) !=BPF_K ) +return -EINVAL ; + +/* unconditional jump with single edge */ + ret =push_insn (t, t + insns[t].off +1 ,FALLTHROUGH , env, + true); +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(). +*/ +init_explored_state (env, t + insns[t].off +1 ); +/* tell verifier to check for equivalent states +* after every call and jump +*/ +if (t +1 < insn_cnt) +init_explored_state (env, t +1 ); + +return ret; + +default : +/* conditional jump with two edges */ +init_explored_state (env, t); + ret =push_insn (t, t +1 ,FALLTHROUGH , env, true); +if (ret) +return ret; + +return push_insn (t, t + insns[t].off +1 ,BRANCH , env, true); + } }/* non-recursive depth-first-search to detect loops in BPF program
@@ -8104,11 +8176,10 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env,*/ static int check_cfg (struct bpf_verifier_env *env) { -struct bpf_insn *insns = env->prog->insnsi;int insn_cnt = env->prog->len;int *insn_stack, *insn_state;int ret =0 ; -int i, t; +int i; insn_state = env->cfg.insn_state =kvcalloc (insn_cnt,sizeof (int ),GFP_KERNEL );if (!insn_state)
@@ -8124,92 +8195,32 @@ static int check_cfg(struct bpf_verifier_env *env) insn_stack[0 ] =0 ;/* 0 is the first instruction */ env->cfg.cur_stack =1 ; -peek_stack: -if (env->cfg.cur_stack ==0 ) - goto check_state; - t = insn_stack[env->cfg.cur_stack -1 ]; - -if (BPF_CLASS (insns[t].code) ==BPF_JMP || -BPF_CLASS (insns[t].code) ==BPF_JMP32 ) { -u8 opcode =BPF_OP (insns[t].code); - -if (opcode ==BPF_EXIT ) { - goto mark_explored; - }else if (opcode ==BPF_CALL ) { - ret =push_insn (t, t +1 ,FALLTHROUGH , env, false); -if (ret ==1 ) - goto peek_stack; -else if (ret <0 ) - goto err_free; -if (t +1 < insn_cnt) -init_explored_state (env, t +1 ); -if (insns[t].src_reg ==BPF_PSEUDO_CALL ) { -init_explored_state (env, t); - ret =push_insn (t, t + insns[t].imm +1 ,BRANCH , - env, false); -if (ret ==1 ) - goto peek_stack; -else if (ret <0 ) - goto err_free; - } - }else if (opcode ==BPF_JA ) { -if (BPF_SRC (insns[t].code) !=BPF_K ) { - ret = -EINVAL ; - goto err_free; - } -/* unconditional jump with single edge */ - ret =push_insn (t, t + insns[t].off +1 , -FALLTHROUGH , env, true); -if (ret ==1 ) - goto peek_stack; -else if (ret <0 ) - goto err_free; -/* unconditional jmp is not a good pruning point, -* but it's marked, since backtracking needs -* to record jmp history in is_state_visited(). -*/ -init_explored_state (env, t + insns[t].off +1 ); -/* tell verifier to check for equivalent states -* after every call and jump -*/ -if (t +1 < insn_cnt) -init_explored_state (env, t +1 ); - }else { -/* conditional jump with two edges */ -init_explored_state (env, t); - ret =push_insn (t, t +1 ,FALLTHROUGH , env, true); -if (ret ==1 ) - goto peek_stack; -else if (ret <0 ) - goto err_free; +while (env->cfg.cur_stack >0 ) { +int t = insn_stack[env->cfg.cur_stack -1 ]; - ret =push_insn (t, t + insns[t].off +1 ,BRANCH , env, true); -if (ret ==1 ) - goto peek_stack; -else if (ret <0 ) - goto err_free; - } - }else { -/* all other non-branch instructions with single -* fall-through edge -*/ - ret =push_insn (t, t +1 ,FALLTHROUGH , env, false); -if (ret ==1 ) - goto peek_stack; -else if (ret <0 ) + ret =visit_insn (t, insn_cnt, env); +switch (ret) { +case DONE_EXPLORING : + insn_state[t] =EXPLORED ; + env->cfg.cur_stack--; +break ; +case KEEP_EXPLORING : +break ; +default : +if (ret >0 ) { +verbose (env,"visit_insn internal bug\n" ); + ret = -EFAULT ; + } goto err_free; + } } -mark_explored: - insn_state[t] =EXPLORED ; -if (env->cfg.cur_stack-- <=0 ) { +if (env->cfg.cur_stack <0 ) {verbose (env,"pop stack internal bug\n" ); ret = -EFAULT ; goto err_free; } - goto peek_stack; -check_state:for (i =0 ; i < insn_cnt; i++) {if (insn_state[i] !=EXPLORED ) {verbose (env,"unreachable insn %d\n" , i);
Signature · 1 line
2.29.2.454.gaff20da3a2-goog
This patch was applied to bpf/bpf-next.git (refs/heads/master):
Hello:
This patch was applied to bpf/bpf-next.git (refs/heads/master):
Quoted 9 lines · On Sat, 21 Nov 2020 01:55:09 +0000 you wrote:
The current implementation uses a number of gotos to implement a loop and different paths within the loop, which makes the code less readable than it would be with an explicit while-loop. This patch also replaces a chain of if/if-elses keyed on the same expression with a switch statement.
No change in behaviour is intended.
[...]
Here is the summary with links:
- [bpf-next,v2] bpf: Refactor check_cfg to use a structured loop.
https://git.kernel.org/bpf/bpf-next/c/59e2e27d227a
You are awesome, thank you!
--
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html