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>
---
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
