Date:   Mon,  7 May 2018 06:22:45 -0400
From:   Jiong Wang <jiong.wang@...ronome.com>
To:     alexei.starovoitov@...il.com, daniel@...earbox.net
Cc:     john.fastabend@...il.com, netdev@...r.kernel.org,
        oss-drivers@...ronome.com, Jiong Wang <jiong.wang@...ronome.com>
Subject: [RFC bpf-next 09/10] bpf: cfg: reduce k*alloc/free call by using memory pool for allocating nodes

During building control flow graph, we need to build basic block nodes
and edge nodes etc. These nodes needs to allocated dynamically as we
don't have pre-scan pass to know how many nodes we need accurately.
It is better to manage their allocation using memory pool which could
reduce calling of *alloc/kfree functions and also could simplify freeing
nodes.

This patch:
  - implements a simple memory pool based node allocator.
    nodes need dynamic allocation migrated to this allocator.
  - estimate node numbers inside subprog detection pass, asking allocator
    to do an initial allocation of estimated size (aligned to 2K). The pool
    will grow later if space are not enough.
  - There is no support on returning memory back to the pool.

Signed-off-by: Jiong Wang <jiong.wang@...ronome.com>
---
 kernel/bpf/cfg.c      | 164 +++++++++++++++++++++++++++++++++++++-------------
 kernel/bpf/cfg.h      |  21 +++++--
 kernel/bpf/verifier.c |  39 +++++++++---
 3 files changed, 170 insertions(+), 54 deletions(-)

diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
index 174e3f0..1aeac49 100644
--- a/kernel/bpf/cfg.c
+++ b/kernel/bpf/cfg.c
@@ -82,7 +82,113 @@ struct dom_info {
 	u16 dfsnum;
 };
 
-int subprog_append_bb(struct list_head *bb_list, int head)
+struct node_pool {
+	struct list_head l;
+	void *data;
+	u32 size;
+	u32 used;
+};
+
+#define first_node_pool(pool_list)	\
+	list_first_entry(pool_list, struct node_pool, l)
+
+#define MEM_CHUNK_SIZE	(1024)
+
+static int cfg_node_allocator_grow(struct cfg_node_allocator *allocator,
+				   int min_grow_size)
+{
+	int s = min_grow_size;
+	struct node_pool *pool;
+	void *data;
+
+	s += sizeof(struct node_pool);
+	s = ALIGN(s, MEM_CHUNK_SIZE);
+	data = kzalloc(s, GFP_KERNEL);
+	if (!data)
+		return -ENOMEM;
+
+	pool = (struct node_pool *)data;
+	pool->data = pool + 1;
+	pool->size = s - sizeof(struct node_pool);
+	pool->used = 0;
+	allocator->cur_free_pool = pool;
+	list_add_tail(&pool->l, &allocator->pools);
+
+	return 0;
+}
+
+static void *cfg_node_alloc(struct cfg_node_allocator *allocator, int size)
+{
+	struct node_pool *pool = allocator->cur_free_pool;
+	void *p;
+
+	if (pool->used + size > pool->size) {
+		int ret = cfg_node_allocator_grow(allocator, size);
+
+		if (ret < 0)
+			return NULL;
+
+		pool = allocator->cur_free_pool;
+	}
+
+	p = pool->data + pool->used;
+	pool->used += size;
+
+	return p;
+}
+
+static struct bb_node *get_single_bb_nodes(struct cfg_node_allocator *allocator)
+{
+	int size = sizeof(struct bb_node);
+
+	return (struct bb_node *)cfg_node_alloc(allocator, size);
+}
+
+static struct edge_node *get_edge_nodes(struct cfg_node_allocator *allocator,
+					int num)
+{
+	int size = num * sizeof(struct edge_node);
+
+	return (struct edge_node *)cfg_node_alloc(allocator, size);
+}
+
+static struct cedge_node *
+get_single_cedge_node(struct cfg_node_allocator *allocator)
+{
+	int size = sizeof(struct cedge_node);
+
+	return (struct cedge_node *)cfg_node_alloc(allocator, size);
+}
+
+int cfg_node_allocator_init(struct cfg_node_allocator *allocator,
+			    int bb_num_esti, int cedge_num_esti)
+{
+	int s = bb_num_esti * sizeof(struct bb_node), ret;
+
+	s += 2 * bb_num_esti * sizeof(struct edge_node);
+	s += cedge_num_esti * sizeof(struct cedge_node);
+	INIT_LIST_HEAD(&allocator->pools);
+	ret = cfg_node_allocator_grow(allocator, s);
+	if (ret < 0)
+		return ret;
+
+	return 0;
+}
+
+void cfg_node_allocator_free(struct cfg_node_allocator *allocator)
+{
+	struct list_head *pools = &allocator->pools;
+	struct node_pool *pool, *tmp;
+
+	pool = first_node_pool(pools);
+	list_for_each_entry_safe_from(pool, tmp, pools, l) {
+		list_del(&pool->l);
+		kfree(pool);
+	}
+}
+
+int subprog_append_bb(struct cfg_node_allocator *allocator,
+		      struct list_head *bb_list, int head)
 {
 	struct bb_node *new_bb, *bb;
 
@@ -94,7 +200,7 @@ int subprog_append_bb(struct list_head *bb_list, int head)
 	}
 
 	bb = bb_prev(bb);
-	new_bb = kzalloc(sizeof(*new_bb), GFP_KERNEL);
+	new_bb = get_single_bb_nodes(allocator);
 	if (!new_bb)
 		return -ENOMEM;
 
@@ -106,9 +212,10 @@ int subprog_append_bb(struct list_head *bb_list, int head)
 	return 0;
 }
 
-int subprog_fini_bb(struct list_head *bb_list, int subprog_end)
+int subprog_fini_bb(struct cfg_node_allocator *allocator,
+		    struct list_head *bb_list, int subprog_end)
 {
-	struct bb_node *bb = kzalloc(sizeof(*bb), GFP_KERNEL);
+	struct bb_node *bb = get_single_bb_nodes(allocator);
 
 	if (!bb)
 		return -ENOMEM;
@@ -118,7 +225,7 @@ int subprog_fini_bb(struct list_head *bb_list, int subprog_end)
 	INIT_LIST_HEAD(&bb->e_succs);
 	list_add(&bb->l, bb_list);
 
-	bb = kzalloc(sizeof(*bb), GFP_KERNEL);
+	bb = get_single_bb_nodes(allocator);
 	if (!bb)
 		return -ENOMEM;
 	/* exit bb. */
@@ -130,12 +237,13 @@ int subprog_fini_bb(struct list_head *bb_list, int subprog_end)
 	return 0;
 }
 
-int subprog_init_bb(struct list_head *bb_list, int subprog_start)
+int subprog_init_bb(struct cfg_node_allocator *allocator,
+		    struct list_head *bb_list, int subprog_start)
 {
 	int ret;
 
 	INIT_LIST_HEAD(bb_list);
-	ret = subprog_append_bb(bb_list, subprog_start);
+	ret = subprog_append_bb(allocator, bb_list, subprog_start);
 	if (ret < 0)
 		return ret;
 
@@ -154,14 +262,15 @@ static struct bb_node *search_bb_with_head(struct list_head *bb_list, int head)
 	return NULL;
 }
 
-int subprog_add_bb_edges(struct bpf_insn *insns, struct list_head *bb_list)
+int subprog_add_bb_edges(struct cfg_node_allocator *allocator,
+			 struct bpf_insn *insns, struct list_head *bb_list)
 {
 	struct bb_node *bb, *exit_bb;
 	struct edge_node *edge;
 	int bb_num;
 
 	bb = entry_bb(bb_list);
-	edge = kcalloc(2, sizeof(*edge), GFP_KERNEL);
+	edge = get_edge_nodes(allocator, 2);
 	if (!edge)
 		return -ENOMEM;
 	edge->src = bb;
@@ -186,7 +295,7 @@ int subprog_add_bb_edges(struct bpf_insn *insns, struct list_head *bb_list)
 
 		bb->idx = bb_num++;
 
-		edge = kcalloc(2, sizeof(*edge), GFP_KERNEL);
+		edge = get_edge_nodes(allocator, 2);
 		if (!edge)
 			return -ENOMEM;
 		edge->src = bb;
@@ -222,7 +331,7 @@ int subprog_add_bb_edges(struct bpf_insn *insns, struct list_head *bb_list)
 			struct bb_node *tgt;
 
 			if (!edge) {
-				edge = kcalloc(2, sizeof(*edge), GFP_KERNEL);
+				edge = get_edge_nodes(allocator, 2);
 				if (!edge)
 					return -ENOMEM;
 				edge->src = bb;
@@ -753,6 +862,7 @@ int cgraph_check_recursive_unreachable(struct bpf_verifier_env *env,
 }
 
 int subprog_append_callee(struct bpf_verifier_env *env,
+			  struct cfg_node_allocator *allocator,
 			  struct list_head *callees_list,
 			  int caller_idx, int off)
 {
@@ -767,7 +877,7 @@ int subprog_append_callee(struct bpf_verifier_env *env,
 			return 0;
 	}
 
-	new_callee = kzalloc(sizeof(*new_callee), GFP_KERNEL);
+	new_callee = get_single_cedge_node(allocator);
 	if (!new_callee)
 		return -ENOMEM;
 
@@ -778,41 +888,11 @@ int subprog_append_callee(struct bpf_verifier_env *env,
 	return 0;
 }
 
-static void subprog_free_edge(struct bb_node *bb)
-{
-	struct list_head *succs = &bb->e_succs;
-	struct edge_node *e, *tmp;
-
-	/* prevs and succs are allocated as pair, succs is the start addr. */
-	list_for_each_entry_safe(e, tmp, succs, l) {
-		list_del(&e->l);
-		kfree(e);
-	}
-}
-
 void subprog_free(struct bpf_subprog_info *subprog, int end_idx)
 {
 	int i = 0;
 
 	for (; i <= end_idx; i++) {
-		struct list_head *callees = &subprog[i].callees;
-		struct list_head *bbs = &subprog[i].bbs;
-		struct cedge_node *callee, *tmp_callee;
-		struct bb_node *bb, *tmp, *exit;
-
-		bb = entry_bb(bbs);
-		exit = exit_bb(bbs);
-		list_for_each_entry_safe_from(bb, tmp, &exit->l, l) {
-			subprog_free_edge(bb);
-			list_del(&bb->l);
-			kfree(bb);
-		}
-
-		list_for_each_entry_safe(callee, tmp_callee, callees, l) {
-			list_del(&callee->l);
-			kfree(callee);
-		}
-
 		if (subprog[i].dtree_avail)
 			kfree(subprog[i].dtree);
 	}
diff --git a/kernel/bpf/cfg.h b/kernel/bpf/cfg.h
index 577c22c..1868587 100644
--- a/kernel/bpf/cfg.h
+++ b/kernel/bpf/cfg.h
@@ -8,19 +8,32 @@
 #ifndef __BPF_CFG_H__
 #define __BPF_CFG_H__
 
+struct cfg_node_allocator {
+	struct list_head pools;
+	struct node_pool *cur_free_pool;
+};
+
 int add_subprog(struct bpf_verifier_env *env, int off);
+void cfg_node_allocator_free(struct cfg_node_allocator *allocator);
+int cfg_node_allocator_init(struct cfg_node_allocator *allocator,
+			    int bb_num_esti, int cedge_num_esti);
 int cgraph_check_recursive_unreachable(struct bpf_verifier_env *env,
 				       struct bpf_subprog_info *subprog);
 int find_subprog(struct bpf_verifier_env *env, int off);
-int subprog_add_bb_edges(struct bpf_insn *insns, struct list_head *bb_list);
-int subprog_append_bb(struct list_head *bb_list, int head);
+int subprog_add_bb_edges(struct cfg_node_allocator *allocator,
+			 struct bpf_insn *insns, struct list_head *bb_list);
+int subprog_append_bb(struct cfg_node_allocator *allocator,
+		      struct list_head *bb_list, int head);
 int subprog_append_callee(struct bpf_verifier_env *env,
+			  struct cfg_node_allocator *allocator,
 			  struct list_head *bb_list, int caller_idx, int off);
 int subprog_build_dom_info(struct bpf_verifier_env *env,
 			   struct bpf_subprog_info *subprog);
-int subprog_fini_bb(struct list_head *bb_list, int subprog_end);
+int subprog_fini_bb(struct cfg_node_allocator *allocator,
+		    struct list_head *bb_list, int subprog_end);
 bool subprog_has_loop(struct bpf_subprog_info *subprog);
-int subprog_init_bb(struct list_head *bb_list, int subprog_start);
+int subprog_init_bb(struct cfg_node_allocator *allocator,
+		    struct list_head *bb_list, int subprog_start);
 void subprog_free(struct bpf_subprog_info *subprog, int end_idx);
 
 #endif
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 54f2fe3..db4a3ca 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -743,7 +743,10 @@ static int check_subprogs(struct bpf_verifier_env *env)
 	struct bpf_subprog_info *subprog = env->subprog_info;
 	struct list_head *cur_bb_list, *cur_callee_list;
 	struct bpf_insn *insn = env->prog->insnsi;
+	int cedge_num_esti = 0, bb_num_esti = 3;
+	struct cfg_node_allocator allocator;
 	int insn_cnt = env->prog->len;
+	u8 code;
 
 	/* Add entry function. */
 	ret = add_subprog(env, 0);
@@ -752,8 +755,18 @@ static int check_subprogs(struct bpf_verifier_env *env)
 
 	/* determine subprog starts. The end is one before the next starts */
 	for (i = 0; i < insn_cnt; i++) {
-		if (insn[i].code != (BPF_JMP | BPF_CALL))
+		code = insn[i].code;
+		if (BPF_CLASS(code) != BPF_JMP)
+			continue;
+		if (BPF_OP(code) == BPF_EXIT) {
+			if (i + 1 < insn_cnt)
+				bb_num_esti++;
 			continue;
+		}
+		if (BPF_OP(code) != BPF_CALL) {
+			bb_num_esti += 2;
+			continue;
+		}
 		if (insn[i].src_reg != BPF_PSEUDO_CALL)
 			continue;
 		if (!env->allow_ptr_leaks) {
@@ -764,6 +777,7 @@ static int check_subprogs(struct bpf_verifier_env *env)
 			verbose(env, "function calls in offloaded programs are not supported yet\n");
 			return -EINVAL;
 		}
+		cedge_num_esti++;
 		ret = add_subprog(env, i + insn[i].imm + 1);
 		if (ret < 0)
 			return ret;
@@ -784,10 +798,14 @@ static int check_subprogs(struct bpf_verifier_env *env)
 		INIT_LIST_HEAD(&subprog[i].callees);
 	}
 
+	ret = cfg_node_allocator_init(&allocator, bb_num_esti,
+				      cedge_num_esti);
+	if (ret < 0)
+		return ret;
 	subprog_start = subprog[cur_subprog].start;
 	subprog_end = subprog[cur_subprog + 1].start;
 	cur_bb_list = &subprog[cur_subprog].bbs;
-	ret = subprog_init_bb(cur_bb_list, subprog_start);
+	ret = subprog_init_bb(&allocator, cur_bb_list, subprog_start);
 	if (ret < 0)
 		goto free_nodes;
 	cur_callee_list = &env->subprog_info[cur_subprog].callees;
@@ -800,7 +818,8 @@ static int check_subprogs(struct bpf_verifier_env *env)
 
 		if (BPF_OP(code) == BPF_EXIT) {
 			if (i + 1 < subprog_end) {
-				ret = subprog_append_bb(cur_bb_list, i + 1);
+				ret = subprog_append_bb(&allocator, cur_bb_list,
+							i + 1);
 				if (ret < 0)
 					goto free_nodes;
 			}
@@ -812,6 +831,7 @@ static int check_subprogs(struct bpf_verifier_env *env)
 				int target = i + insn[i].imm + 1;
 
 				ret = subprog_append_callee(env,
+							    &allocator,
 							    cur_callee_list,
 							    cur_subprog,
 							    target);
@@ -835,12 +855,12 @@ static int check_subprogs(struct bpf_verifier_env *env)
 			goto free_nodes;
 		}
 
-		ret = subprog_append_bb(cur_bb_list, off);
+		ret = subprog_append_bb(&allocator, cur_bb_list, off);
 		if (ret < 0)
 			goto free_nodes;
 
 		if (i + 1 < subprog_end) {
-			ret = subprog_append_bb(cur_bb_list, i + 1);
+			ret = subprog_append_bb(&allocator, cur_bb_list, i + 1);
 			if (ret < 0)
 				goto free_nodes;
 		}
@@ -864,10 +884,12 @@ static int check_subprogs(struct bpf_verifier_env *env)
 				goto free_nodes;
 			}
 
-			ret = subprog_fini_bb(cur_bb_list, subprog_end);
+			ret = subprog_fini_bb(&allocator, cur_bb_list,
+					      subprog_end);
 			if (ret < 0)
 				goto free_nodes;
-			ret = subprog_add_bb_edges(insn, cur_bb_list);
+			ret = subprog_add_bb_edges(&allocator, insn,
+						   cur_bb_list);
 			if (ret < 0)
 				goto free_nodes;
 			subprog[cur_subprog].bb_num = ret;
@@ -885,7 +907,7 @@ static int check_subprogs(struct bpf_verifier_env *env)
 			if (cur_subprog < env->subprog_cnt) {
 				subprog_end = subprog[cur_subprog + 1].start;
 				cur_bb_list = &subprog[cur_subprog].bbs;
-				ret = subprog_init_bb(cur_bb_list,
+				ret = subprog_init_bb(&allocator, cur_bb_list,
 						      subprog_start);
 				if (ret < 0)
 					goto free_nodes;
@@ -901,6 +923,7 @@ static int check_subprogs(struct bpf_verifier_env *env)
 	ret = 0;
 
 free_nodes:
+	cfg_node_allocator_free(&allocator);
 	subprog_free(subprog, cur_subprog == env->subprog_cnt ?
 				cur_subprog - 1 : cur_subprog);
 	return ret;
-- 
2.7.4

Powered by blists - more mailing lists