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

[John Fastabend <john.fastabend@gmail.com>]

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

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

Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
Signed-off-by: John Fastabend <john.fastabend@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) {