Skip to contentSkip to conversation

bpf: parallel verification

PATCH In review Alexei Starovoitov 4 participants 6 messages Apr 19, 2019 – Apr 23, 2019

Subsystems (4)
lore
Share & tools
lore

Alexei Starovoitov

author maintainer
#0 lore raw

cover 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
author maintainer
#1 lore raw

PATCH 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
index b3ab61fe1932..1305ccbd8fe6 100644
@@ -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
index db301e9b5295..5f0eb5bd5589 100644
@@ -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
author maintainer
#2 lore raw

PATCH 2/2 bpf: drop bpf_verifier_lock

In reply to Alexei Starovoitov

Drop 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
index 5f0eb5bd5589..423f242a5efb 100644
@@ -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
Acked-by on the v1 series
#3 lore raw
In reply to Alexei Starovoitov
Quoted 7 lines · Alexei Starovoitov

Allow the bpf verifier to run in parallel for root.

Alexei Starovoitov (2):
bpf: remove global variables
bpf: drop bpf_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:

maintainer
#4 lore raw
In reply to Alexei Starovoitov
Quoted 10 lines · Alexei Starovoitov

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(-)

Too bad we still need to keep it around for unpriv. Anyway, applied, thanks!

#5 lore raw
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: drop bpf_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.