[RFC PATCH 04/16] bpf: cfg: detect loop use domination information

[John Fastabend]

From: Jiong Wang <jiong.w...@netronome.com>

If one bb is dominating its predecessor, then there is loop.

Signed-off-by: Jiong Wang <jiong.w...@netronome.com>
Signed-off-by: John Fastabend <john.fastab...@gmail.com>
---
 kernel/bpf/cfg.c      |   22 ++++++++++++++++++++++
 kernel/bpf/cfg.h      |    1 +
 kernel/bpf/verifier.c |    8 ++++++++
 3 files changed, 31 insertions(+)

diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
index b50937a..90692e4 100644
--- a/kernel/bpf/cfg.c
+++ b/kernel/bpf/cfg.c
@@ -568,6 +568,28 @@ int subprog_build_dom_info(struct bpf_subprog_info 
*subprog)
        return ret;
 }
 
+bool subprog_has_loop(struct bpf_subprog_info *subprog)
+{
+       int lane_len = BITS_TO_LONGS(subprog->bb_num - 2);
+       struct list_head *bb_list = &subprog->bbs;
+       struct bb_node *bb, *entry_bb;
+       struct edge_node *e;
+
+       entry_bb = entry_bb(bb_list);
+       bb = bb_next(entry_bb);
+       list_for_each_entry_from(bb, &exit_bb(bb_list)->l, l)
+               list_for_each_entry(e, &bb->e_prevs, l) {
+                       struct bb_node *latch = e->src;
+
+                       if (latch != entry_bb &&
+                           test_bit(bb->idx,
+                                    subprog->dtree + latch->idx * lane_len))
+                               return true;
+               }
+
+       return false;
+}
+
 static void subprog_free_edge(struct bb_node *bb)
 {
        struct list_head *succs = &bb->e_succs;
diff --git a/kernel/bpf/cfg.h b/kernel/bpf/cfg.h
index cbb44f2..c02c4cf 100644
--- a/kernel/bpf/cfg.h
+++ b/kernel/bpf/cfg.h
@@ -12,6 +12,7 @@
 int subprog_append_bb(struct list_head *bb_list, int head);
 int subprog_build_dom_info(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);
 void subprog_free(struct bpf_subprog_info *subprog, int end_idx);
 
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index eccaee4..c349c45 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -904,6 +904,14 @@ 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]);
+                       if (ret < 0)
+                               goto free_nodes;
+                       if (subprog_has_loop(&subprog[cur_subprog])) {
+                               verbose(env, "cfg - loop detected");
+                               ret = -EINVAL;
+                               goto free_nodes;
+                       }
                        subprog_start = subprog_end;
                        cur_subprog++;
                        if (cur_subprog < env->subprog_cnt) {