From mboxrd@z Thu Jan 1 00:00:00 1970 From: John Fastabend Subject: [RFC PATCH 05/16] bpf: cfg: detect unreachable basic blocks Date: Fri, 01 Jun 2018 02:32:43 -0700 Message-ID: <20180601093243.15353.83087.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]:35680 "EHLO john-Precision-Tower-5810" rhost-flags-FAIL-FAIL-OK-FAIL) by vger.kernel.org with ESMTP id S1750868AbeFAJcr (ORCPT ); Fri, 1 Jun 2018 05:32:47 -0400 In-Reply-To: <20180601092646.15353.28269.stgit@john-Precision-Tower-5810> Sender: netdev-owner@vger.kernel.org List-ID: From: Jiong Wang Do unreachable basic blocks detection as a side-product of the dfs walk when building domination information. Signed-off-by: Jiong Wang Signed-off-by: John Fastabend --- kernel/bpf/cfg.c | 19 ++++++++++++++----- kernel/bpf/cfg.h | 3 ++- kernel/bpf/verifier.c | 3 ++- 3 files changed, 18 insertions(+), 7 deletions(-) diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c index 90692e4..2f0ac00 100644 --- a/kernel/bpf/cfg.c +++ b/kernel/bpf/cfg.c @@ -407,10 +407,11 @@ 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; @@ -490,6 +491,13 @@ 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 (!di->dfs_order[i]) { + bpf_verifier_log_write(env, "cfg - unreachable insn\n"); + return -EINVAL; + } + } + return 0; } @@ -541,7 +549,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 +559,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 c349c45..29797d2 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -904,7 +904,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])) {