bpf: parallel verification
Subsystems (4)
Alexei Starovoitov
maintainercover bpf: parallel verification
Allow the bpf verifier to run in parallel for root.
Alexei Starovoitov (2):
bpf: remove global variables
bpf: drop bpf_verifier_lock
include/linux/bpf_verifier.h | 5 +++++ kernel/bpf/verifier.c | 33 ++++++++++++++++++--------------- 2 files changed, 23 insertions(+), 15 deletions(-)
Signature · 1 line
2.20.0
Alexei Starovoitov
maintainerPATCH 1/2 bpf: remove global variables
Move three global variables protected by bpf_verifier_lock into 'struct bpf_verifier_env' to allow parallel verification.
--- include/linux/bpf_verifier.h | 5 +++++ kernel/bpf/verifier.c | 25 +++++++++++++------------ 2 files changed, 18 insertions(+), 12 deletions(-)
include/linux/bpf_verifier.h +5 -0
@@ -295,6 +295,11 @@ struct bpf_verifier_env {const struct bpf_line_info *prev_linfo;struct bpf_verifier_log log;struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS +1 ]; +struct { +int *insn_state; +int *insn_stack; +int cur_stack; + } cfg;u32 subprog_cnt;/* number of instructions analyzed by the verifier */ u32 insn_processed;
kernel/bpf/verifier.c +13 -12
@@ -5369,10 +5369,6 @@ enum {#define STATE_LIST_MARK ((struct bpf_verifier_state_list *) -1L) -static int *insn_stack;/* stack of insns to process */ -static int cur_stack;/* current stack index */ -static int *insn_state; -/* t, w, e - match pseudo-code above: * t - index of current instruction * w - next instruction
@@ -5380,6 +5376,9 @@ static int *insn_state;*/ static int push_insn (int t,int w,int e,struct bpf_verifier_env *env) { +int *insn_stack = env->cfg.insn_stack; +int *insn_state = env->cfg.insn_state; +if (e ==FALLTHROUGH && insn_state[t] >= (DISCOVERED |FALLTHROUGH ))return 0 ;
@@ -5400,9 +5399,9 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env)/* tree-edge */ insn_state[t] =DISCOVERED | e; insn_state[w] =DISCOVERED ; -if (cur_stack >= env->prog->len) +if (env->cfg.cur_stack >= env->prog->len)return -E2BIG ; - insn_stack[cur_stack++] = w; + insn_stack[env->cfg.cur_stack++] = w;return 1 ; }else if ((insn_state[w] &0xF0 ) ==DISCOVERED ) {verbose_linfo (env, t,"%d: " , t);
@@ -5426,14 +5425,15 @@ 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; - insn_state =kvcalloc (insn_cnt,sizeof (int ),GFP_KERNEL ); + insn_state = env->cfg.insn_state =kvcalloc (insn_cnt,sizeof (int ),GFP_KERNEL );if (!insn_state)return -ENOMEM ; - insn_stack =kvcalloc (insn_cnt,sizeof (int ),GFP_KERNEL ); + insn_stack = env->cfg.insn_stack =kvcalloc (insn_cnt,sizeof (int ),GFP_KERNEL );if (!insn_stack) {kvfree (insn_state);return -ENOMEM ;
@@ -5441,12 +5441,12 @@ static int check_cfg(struct bpf_verifier_env *env) insn_state[0 ] =DISCOVERED ;/* mark 1st insn as discovered */ insn_stack[0 ] =0 ;/* 0 is the first instruction */ - cur_stack =1 ; + env->cfg.cur_stack =1 ; peek_stack: -if (cur_stack ==0 ) +if (env->cfg.cur_stack ==0 ) goto check_state; - t = insn_stack[cur_stack -1 ]; + t = insn_stack[env->cfg.cur_stack -1 ];if (BPF_CLASS (insns[t].code) ==BPF_JMP ||BPF_CLASS (insns[t].code) ==BPF_JMP32 ) {
@@ -5515,7 +5515,7 @@ static int check_cfg(struct bpf_verifier_env *env) mark_explored: insn_state[t] =EXPLORED ; -if (cur_stack-- <=0 ) { +if (env->cfg.cur_stack-- <=0 ) {verbose (env,"pop stack internal bug\n" ); ret = -EFAULT ; goto err_free;
@@ -5535,6 +5535,7 @@ static int check_cfg(struct bpf_verifier_env *env) err_free:kvfree (insn_state);kvfree (insn_stack); + env->cfg.insn_state = env->cfg.insn_stack =NULL ;return ret; }
Signature · 1 line
2.20.0
Alexei Starovoitov
maintainerPATCH 2/2 bpf: drop bpf_verifier_lock
In reply to Alexei StarovoitovDrop bpf_verifier_lock for root to avoid being DoS-ed by unprivileged. The BPF verifier is now fully parallel.
All unpriv users are still serialized by bpf_verifier_lock to avoid exhausting kernel memory by running N parallel verifications.
--- kernel/bpf/verifier.c | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-)
kernel/bpf/verifier.c +5 -3
@@ -8132,9 +8132,11 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, env->insn_aux_data[i].orig_idx = i; env->prog = *prog; env->ops = bpf_verifier_ops[env->prog->type]; + is_priv =capable (CAP_SYS_ADMIN );/* grab the mutex to protect few globals used by verifier */ -mutex_lock (&bpf_verifier_lock); +if (!is_priv) +mutex_lock (&bpf_verifier_lock);if (attr->log_level || attr->log_buf || attr->log_size) {/* user requested verbose verifier output
@@ -8157,7 +8159,6 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr,if (attr->prog_flags &BPF_F_ANY_ALIGNMENT ) env->strict_alignment = false; - is_priv =capable (CAP_SYS_ADMIN ); env->allow_ptr_leaks = is_priv; ret =replace_map_fd_with_map_ptr (env);
@@ -8270,7 +8271,8 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr,release_maps (env); *prog = env->prog; err_unlock: -mutex_unlock (&bpf_verifier_lock); +if (!is_priv) +mutex_unlock (&bpf_verifier_lock);vfree (env->insn_aux_data); err_free_env:kfree (env);
Signature · 1 line
2.20.0
Quoted 7 lines · Alexei Starovoitov
Allow the bpf verifier to run in parallel for root.
Alexei Starovoitov (2):
bpf: remove global variables
bpf: dropbpf_verifier_lock
Quoted 7 lines
include/linux/bpf_verifier.h | 5 +++++ kernel/bpf/verifier.c | 33 ++++++++++++++++++--------------- 2 files changed, 23 insertions(+), 15 deletions(-)--
2.20.0
lgtm, for the set:
Daniel Borkmann
maintainerQuoted 10 lines · Alexei Starovoitov
Allow the bpf verifier to run in parallel for root.
Alexei Starovoitov (2):
bpf: remove global variables
bpf: dropbpf_verifier_lockinclude/linux/bpf_verifier.h | 5 +++++ kernel/bpf/verifier.c | 33 ++++++++++++++++++--------------- 2 files changed, 23 insertions(+), 15 deletions(-)
Too bad we still need to keep it around for unpriv. Anyway, applied, thanks!
Quoted 7 lines · Daniel Borkmann
Quoted 6 lines · Alexei Starovoitov
Allow the bpf verifier to run in parallel for root.
Alexei Starovoitov (2):
bpf: remove global variables
bpf: dropbpf_verifier_lock
Quoted 6 lines
Quoted 4 lines
include/linux/bpf_verifier.h | 5 +++++ kernel/bpf/verifier.c | 33 ++++++++++++++++++--------------- 2 files changed, 23 insertions(+), 15 deletions(-)Too bad we still need to keep it around for unpriv. Anyway, applied, thanks!
I'm planing to add memcg accounting and teach oom_badness about the memory used during verification. Then we can drop the mutex for unpriv as well.