From mboxrd@z Thu Jan 1 00:00:00 1970 From: John Fastabend Subject: [RFC PATCH 02/16] bpf: cfg: add edges between basic blocks to form CFG Date: Fri, 01 Jun 2018 02:32:28 -0700 Message-ID: <20180601093228.15353.75335.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]:35652 "EHLO john-Precision-Tower-5810" rhost-flags-FAIL-FAIL-OK-FAIL) by vger.kernel.org with ESMTP id S1750737AbeFAJcc (ORCPT ); Fri, 1 Jun 2018 05:32:32 -0400 In-Reply-To: <20180601092646.15353.28269.stgit@john-Precision-Tower-5810> Sender: netdev-owner@vger.kernel.org List-ID: From: Jiong Wang This patch add edges between basic blocks. Both edges for predecessors and successors are added. Signed-off-by: Jiong Wang Signed-off-by: John Fastabend --- kernel/bpf/cfg.c | 129 ++++++++++++++++++++++++++++++++++++++++++++++++- kernel/bpf/cfg.h | 1 kernel/bpf/verifier.c | 3 + 3 files changed, 131 insertions(+), 2 deletions(-) diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c index b1af714..208aac7 100644 --- a/kernel/bpf/cfg.c +++ b/kernel/bpf/cfg.c @@ -11,8 +11,16 @@ #include "cfg.h" +struct edge_node { + struct list_head l; + struct bb_node *src; + struct bb_node *dst; +}; + struct bb_node { struct list_head l; + struct list_head e_prevs; + struct list_head e_succs; u16 head; }; @@ -39,6 +47,8 @@ int subprog_append_bb(struct list_head *bb_list, int head) if (!new_bb) return -ENOMEM; + INIT_LIST_HEAD(&new_bb->e_prevs); + INIT_LIST_HEAD(&new_bb->e_succs); new_bb->head = head; list_add(&new_bb->l, &bb->l); @@ -53,6 +63,8 @@ int subprog_fini_bb(struct list_head *bb_list, int subprog_end) return -ENOMEM; /* entry bb. */ bb->head = -1; + INIT_LIST_HEAD(&bb->e_prevs); + INIT_LIST_HEAD(&bb->e_succs); list_add(&bb->l, bb_list); bb = kzalloc(sizeof(*bb), GFP_KERNEL); @@ -60,6 +72,8 @@ int subprog_fini_bb(struct list_head *bb_list, int subprog_end) return -ENOMEM; /* exit bb. */ bb->head = subprog_end; + INIT_LIST_HEAD(&bb->e_prevs); + INIT_LIST_HEAD(&bb->e_succs); list_add_tail(&bb->l, bb_list); return 0; @@ -77,15 +91,126 @@ int subprog_init_bb(struct list_head *bb_list, int subprog_start) return 0; } +static struct bb_node *search_bb_with_head(struct list_head *bb_list, int head) +{ + struct bb_node *bb; + + list_for_each_entry(bb, bb_list, l) { + if (bb->head == head) + return bb; + } + + return NULL; +} + +int subprog_add_bb_edges(struct bpf_insn *insns, struct list_head *bb_list) +{ + struct bb_node *bb, *exit_bb; + struct edge_node *edge; + + bb = entry_bb(bb_list); + edge = kcalloc(2, sizeof(*edge), GFP_KERNEL); + if (!edge) + return -ENOMEM; + edge->src = bb; + edge->dst = bb_next(bb); + list_add_tail(&edge->l, &bb->e_succs); + edge[1].src = edge->src; + edge[1].dst = edge->dst; + list_add_tail(&edge[1].l, &edge[1].dst->e_prevs); + + exit_bb = exit_bb(bb_list); + bb = bb_next(bb); + list_for_each_entry_from(bb, &exit_bb->l, l) { + bool has_fallthrough, only_has_fallthrough; + bool has_branch, only_has_branch; + struct bb_node *next_bb = bb_next(bb); + int tail = next_bb->head - 1; + struct bpf_insn insn; + u8 code; + + edge = kcalloc(2, sizeof(*edge), GFP_KERNEL); + if (!edge) + return -ENOMEM; + edge->src = bb; + edge[1].src = bb; + + insn = insns[tail]; + code = insn.code; + only_has_fallthrough = BPF_CLASS(code) != BPF_JMP || + BPF_OP(code) == BPF_EXIT; + has_fallthrough = only_has_fallthrough || + (BPF_CLASS(code) == BPF_JMP && + BPF_OP(code) != BPF_CALL && + BPF_OP(code) != BPF_JA); + only_has_branch = BPF_CLASS(code) == BPF_JMP && + BPF_OP(code) == BPF_JA; + has_branch = only_has_branch || + (BPF_CLASS(code) == BPF_JMP && + BPF_OP(code) != BPF_EXIT && + BPF_OP(code) != BPF_CALL); + + if (has_fallthrough) { + if (BPF_CLASS(code) == BPF_JMP && + BPF_OP(code) == BPF_EXIT) + next_bb = exit_bb; + edge->dst = next_bb; + edge[1].dst = next_bb; + list_add_tail(&edge->l, &bb->e_succs); + list_add_tail(&edge[1].l, &edge[1].dst->e_prevs); + edge = NULL; + } + + if (has_branch) { + struct bb_node *tgt; + + if (!edge) { + edge = kcalloc(2, sizeof(*edge), GFP_KERNEL); + if (!edge) + return -ENOMEM; + edge->src = bb; + edge[1].src = bb; + } + + tgt = search_bb_with_head(bb_list, + tail + insn.off + 1); + if (!tgt) + return -EINVAL; + + edge->dst = tgt; + edge[1].dst = tgt; + list_add_tail(&edge->l, &bb->e_succs); + list_add_tail(&edge[1].l, &tgt->e_prevs); + } + } + + 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_bb(struct bpf_subprog_info *subprog, int end_idx) { int i = 0; for (; i <= end_idx; i++) { struct list_head *bbs = &subprog[i].bbs; - struct bb_node *bb, *tmp; + struct bb_node *bb, *tmp, *exit; - list_for_each_entry_safe(bb, tmp, bbs, l) { + 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); } diff --git a/kernel/bpf/cfg.h b/kernel/bpf/cfg.h index 4092145..7a9d5dd 100644 --- a/kernel/bpf/cfg.h +++ b/kernel/bpf/cfg.h @@ -8,6 +8,7 @@ #ifndef __BPF_CFG_H__ #define __BPF_CFG_H__ +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_fini_bb(struct list_head *bb_list, int subprog_end); int subprog_init_bb(struct list_head *bb_list, int subprog_start); diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 523e440..bcac7c8 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -900,6 +900,9 @@ static int check_subprogs(struct bpf_verifier_env *env) ret = subprog_fini_bb(cur_bb_list, subprog_end); if (ret < 0) goto free_nodes; + ret = subprog_add_bb_edges(insn, cur_bb_list); + if (ret < 0) + goto free_nodes; subprog_start = subprog_end; cur_subprog++; if (cur_subprog < env->subprog_cnt) {