bpf: Refactor check_cfg to use a structured loop.
PATCH 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 | 157 +++++++++++++++++++++--------------------- 1 file changed, 78 insertions(+), 79 deletions(-)
kernel/bpf/verifier.c +78 -79
@@ -8099,16 +8099,82 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env,return 0 ; } +/* Visits instruction at index t and returns one of the following: +* < 0 - an error occurred +* 0 - the instruction was fully explored +* > 0 - 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 0 ; + +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 * loop == back-edge in directed graph */ 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 +8190,25 @@ 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); +if (ret <0 ) goto err_free; + +if (!ret) { + insn_state[t] =EXPLORED ; + env->cfg.cur_stack--; + } } -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.299.gdc1121823c-goog
Daniel Borkmann
maintainerQuoted 88 lines · Wedson Almeida Filho
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.
Signed-off-by Wedson Almeida Filho <[email protected]>--- kernel/bpf/verifier.c | 157 +++++++++++++++++++++--------------------- 1 file changed, 78 insertions(+), 79 deletions(-)kernel/bpf/verifier.c +67
-0@@ -8099,16 +8099,82 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env,return 0 ; } +/* Visits instruction at index t and returns one of the following: +* < 0 - an error occurred +* 0 - the instruction was fully explored +* > 0 - 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 0 ; + +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); + } +} +
[...]
kernel/bpf/verifier.c
Quoted 8 lines
kernel/bpf/verifier.c +7
-0+ ret =visit_insn (t, insn_cnt, env); +if (ret <0 ) goto err_free; + +if (!ret) { + insn_state[t] =EXPLORED ; + env->cfg.cur_stack--; + }
Looks good to me, and it's a nice simplification, imho. Perhaps we could take that even further while at it, make the walk opcodes more descriptive, and also reject anything unexpected (> 1) ... uncompiled diff on top:
kernel/bpf/verifier.c +23 -11
@@ -8047,6 +8047,9 @@ static void init_explored_state(struct bpf_verifier_env *env, int idx) env->insn_aux_data[idx].prune_point = true; } +#define DONE_EXPLORING 0 +#define KEEP_EXPLORING 1 +/* t, w, e - match pseudo-code above: * t - index of current instruction * w - next instruction
@@ -8059,10 +8062,9 @@ 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);
@@ -8080,11 +8082,13 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env, insn_state[w] =DISCOVERED ;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 +8100,8 @@ 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 instruction at index t and returns one of the following:
@@ -8116,7 +8121,7 @@ static int visit_insn(int t, int insn_cnt, struct bpf_verifier_env *env)switch (BPF_OP (insns[t].code)) {case BPF_EXIT : -return 0 ; +return DONE_EXPLORING ;case BPF_CALL : ret =push_insn (t, t +1 ,FALLTHROUGH , env, false);
@@ -8194,12 +8199,19 @@ static int check_cfg(struct bpf_verifier_env *env)int t = insn_stack[env->cfg.cur_stack -1 ]; ret =visit_insn (t, insn_cnt, env); -if (ret <0 ) - goto err_free; - -if (!ret) { +switch (ret) { +case DONE_EXPLORING : insn_state[t] =EXPLORED ; env->cfg.cur_stack--; +break ; +case KEEP_EXPLORING : +break ; +default : +if (ret >0 ) { +verbose (env,"insn visit internal bug\n" ); + ret = -EFAULT ; + } + goto err_free; } }