From mboxrd@z Thu Jan 1 00:00:00 1970 From: John Fastabend Subject: [RFC PATCH 09/16] bpf: cfg: reduce k*alloc/free call by using memory pool for allocating nodes Date: Fri, 01 Jun 2018 02:33:03 -0700 Message-ID: <20180601093303.15353.86894.stgit@john-Precision-Tower-5810> References: <20180601092646.15353.28269.stgit@john-Precision-Tower-5810> Mime-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit Cc: netdev@vger.kernel.org To: alexei.starovoitov@gmail.com, daniel@iogearbox.net, davem@davemloft.net Return-path: Received: from [184.63.162.180] ([184.63.162.180]:35736 "EHLO john-Precision-Tower-5810" rhost-flags-FAIL-FAIL-OK-FAIL) by vger.kernel.org with ESMTP id S1751561AbeFAJdJ (ORCPT ); Fri, 1 Jun 2018 05:33:09 -0400 In-Reply-To: <20180601092646.15353.28269.stgit@john-Precision-Tower-5810> Sender: netdev-owner@vger.kernel.org List-ID: From: Jiong Wang 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 Signed-off-by: John Fastabend --- 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;