[RFC PATCH 05/16] bpf: cfg: detect unreachable basic blocks

[John Fastabend]

From: Jiong Wang <jiong.w...@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.w...@netronome.com>
Signed-off-by: John Fastabend <john.fastab...@gmail.com>
---
 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])) {