From mboxrd@z Thu Jan 1 00:00:00 1970 From: Jiong Wang Subject: [RFC bpf-next 05/10] bpf: cfg: detect unreachable basic blocks Date: Mon, 7 May 2018 06:22:41 -0400 Message-ID: <1525688567-19618-6-git-send-email-jiong.wang@netronome.com> References: <1525688567-19618-1-git-send-email-jiong.wang@netronome.com> Cc: john.fastabend@gmail.com, netdev@vger.kernel.org, oss-drivers@netronome.com, Jiong Wang To: alexei.starovoitov@gmail.com, daniel@iogearbox.net Return-path: Received: from mail-wm0-f66.google.com ([74.125.82.66]:50275 "EHLO mail-wm0-f66.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751889AbeEGKXK (ORCPT ); Mon, 7 May 2018 06:23:10 -0400 Received: by mail-wm0-f66.google.com with SMTP id t11so12566881wmt.0 for ; Mon, 07 May 2018 03:23:09 -0700 (PDT) In-Reply-To: <1525688567-19618-1-git-send-email-jiong.wang@netronome.com> Sender: netdev-owner@vger.kernel.org List-ID: Do unreachable basic blocks detection as a side-product of the dfs walk when building domination information. Signed-off-by: Jiong Wang --- kernel/bpf/cfg.c | 31 ++++++++++++++++++++++++++----- kernel/bpf/cfg.h | 3 ++- kernel/bpf/verifier.c | 3 ++- 3 files changed, 30 insertions(+), 7 deletions(-) diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c index 90692e4..7ce1472 100644 --- a/kernel/bpf/cfg.c +++ b/kernel/bpf/cfg.c @@ -407,15 +407,17 @@ static void calc_idoms(struct bpf_subprog_info *subprog, struct dom_info *di, di->idom[idx] = di->idom[di->idom[idx]]; } -static int calc_dfs_tree(struct bpf_subprog_info *subprog, struct dom_info *di, - bool reverse) +static int +calc_dfs_tree(struct bpf_verifier_env *env, struct bpf_subprog_info *subprog, + struct dom_info *di, bool reverse) { - u16 bb_num = subprog->bb_num, sp = 0, idx, parent_idx; + u16 bb_num = subprog->bb_num, sp = 0, idx, parent_idx, i; struct list_head *bb_list = &subprog->bbs; u16 entry_bb_fake_idx = bb_num - 2; struct bb_node *entry_bb, *exit_bb; struct edge_iter ei, *stack; struct edge_node *e; + bool *visited; di->dfs_order[entry_bb_fake_idx] = di->dfsnum; @@ -423,6 +425,10 @@ static int calc_dfs_tree(struct bpf_subprog_info *subprog, struct dom_info *di, if (!stack) return -ENOMEM; + visited = kcalloc(bb_num - 2, sizeof(bool), GFP_KERNEL); + if (!visited) + return -ENOMEM; + if (reverse) { entry_bb = exit_bb(bb_list); exit_bb = entry_bb(bb_list); @@ -445,6 +451,8 @@ static int calc_dfs_tree(struct bpf_subprog_info *subprog, struct dom_info *di, if (reverse) { bb_dst = e->src; + if (bb_dst != exit_bb) + visited[bb_dst->idx] = true; if (bb_dst == exit_bb || di->dfs_order[bb_dst->idx]) { ei_next(&ei); @@ -453,6 +461,8 @@ static int calc_dfs_tree(struct bpf_subprog_info *subprog, struct dom_info *di, bb_src = e->dst; } else { bb_dst = e->dst; + if (bb_dst != exit_bb) + visited[bb_dst->idx] = true; if (bb_dst == exit_bb || di->dfs_order[bb_dst->idx]) { ei_next(&ei); @@ -490,6 +500,16 @@ static int calc_dfs_tree(struct bpf_subprog_info *subprog, struct dom_info *di, kfree(stack); + for (i = 0; i < bb_num - 2; i++) { + if (!visited[i]) { + bpf_verifier_log_write(env, "cfg - unreachable insn\n"); + kfree(visited); + return -EINVAL; + } + } + + kfree(visited); + return 0; } @@ -541,7 +561,8 @@ static int idoms_to_doms(struct bpf_subprog_info *subprog, struct dom_info *di) * The implementation also referenced GNU GCC 3.0. */ -int subprog_build_dom_info(struct bpf_subprog_info *subprog) +int subprog_build_dom_info(struct bpf_verifier_env *env, + struct bpf_subprog_info *subprog) { struct dom_info di; int ret; @@ -550,7 +571,7 @@ int subprog_build_dom_info(struct bpf_subprog_info *subprog) if (ret < 0) goto free_dominfo; - ret = calc_dfs_tree(subprog, &di, false); + ret = calc_dfs_tree(env, subprog, &di, false); if (ret < 0) goto free_dominfo; diff --git a/kernel/bpf/cfg.h b/kernel/bpf/cfg.h index c02c4cf..02729a9 100644 --- a/kernel/bpf/cfg.h +++ b/kernel/bpf/cfg.h @@ -10,7 +10,8 @@ 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_build_dom_info(struct bpf_subprog_info *subprog); +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); bool subprog_has_loop(struct bpf_subprog_info *subprog); 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 a93aa43..46d5eae 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -879,7 +879,8 @@ static int check_subprogs(struct bpf_verifier_env *env) if (ret < 0) goto free_nodes; subprog[cur_subprog].bb_num = ret; - ret = subprog_build_dom_info(&subprog[cur_subprog]); + ret = subprog_build_dom_info(env, + &subprog[cur_subprog]); if (ret < 0) goto free_nodes; if (subprog_has_loop(&subprog[cur_subprog])) { -- 2.7.4