From: Jiong Wang <jiong.w...@netronome.com>
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.w...@netronome.com>
Signed-off-by: John Fastabend <john.fastab...@gmail.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 56c08e8..d213289 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;
@@ -741,6 +850,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)
{
@@ -755,7 +865,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;
@@ -766,41 +876,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 338ebc5..5a5016d 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -768,7 +768,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);
@@ -777,8 +780,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) {
@@ -789,6 +802,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;
@@ -809,10 +823,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;
@@ -825,7 +843,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;
}
@@ -837,6 +856,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);
@@ -860,12 +880,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;
}
@@ -889,10 +909,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;
@@ -910,7 +932,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;
@@ -926,6 +948,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;
