[RFC bpf-next 05/10] bpf: cfg: detect unreachable basic blocks

[Jiong Wang <jiong.wang@netronome.com>]

Do unreachable basic blocks detection as a side-product of the dfs walk
when building domination information.

Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
---
 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