[RFC PATCH 02/16] bpf: cfg: add edges between basic blocks to form CFG

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

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

This patch add edges between basic blocks. Both edges for predecessors and
successors are added.

Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
Signed-off-by: John Fastabend <john.fastabend@gmail.com>
---
 kernel/bpf/cfg.c      |  129 ++++++++++++++++++++++++++++++++++++++++++++++++-
 kernel/bpf/cfg.h      |    1 
 kernel/bpf/verifier.c |    3 +
 3 files changed, 131 insertions(+), 2 deletions(-)

diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
index b1af714..208aac7 100644
--- a/kernel/bpf/cfg.c
+++ b/kernel/bpf/cfg.c
@@ -11,8 +11,16 @@
 
 #include "cfg.h"
 
+struct edge_node {
+	struct list_head l;
+	struct bb_node *src;
+	struct bb_node *dst;
+};
+
 struct bb_node {
 	struct list_head l;
+	struct list_head e_prevs;
+	struct list_head e_succs;
 	u16 head;
 };
 
@@ -39,6 +47,8 @@ int subprog_append_bb(struct list_head *bb_list, int head)
 	if (!new_bb)
 		return -ENOMEM;
 
+	INIT_LIST_HEAD(&new_bb->e_prevs);
+	INIT_LIST_HEAD(&new_bb->e_succs);
 	new_bb->head = head;
 	list_add(&new_bb->l, &bb->l);
 
@@ -53,6 +63,8 @@ int subprog_fini_bb(struct list_head *bb_list, int subprog_end)
 		return -ENOMEM;
 	/* entry bb. */
 	bb->head = -1;
+	INIT_LIST_HEAD(&bb->e_prevs);
+	INIT_LIST_HEAD(&bb->e_succs);
 	list_add(&bb->l, bb_list);
 
 	bb = kzalloc(sizeof(*bb), GFP_KERNEL);
@@ -60,6 +72,8 @@ int subprog_fini_bb(struct list_head *bb_list, int subprog_end)
 		return -ENOMEM;
 	/* exit bb. */
 	bb->head = subprog_end;
+	INIT_LIST_HEAD(&bb->e_prevs);
+	INIT_LIST_HEAD(&bb->e_succs);
 	list_add_tail(&bb->l, bb_list);
 
 	return 0;
@@ -77,15 +91,126 @@ int subprog_init_bb(struct list_head *bb_list, int subprog_start)
 	return 0;
 }
 
+static struct bb_node *search_bb_with_head(struct list_head *bb_list, int head)
+{
+	struct bb_node *bb;
+
+	list_for_each_entry(bb, bb_list, l) {
+		if (bb->head == head)
+			return bb;
+	}
+
+	return NULL;
+}
+
+int subprog_add_bb_edges(struct bpf_insn *insns, struct list_head *bb_list)
+{
+	struct bb_node *bb, *exit_bb;
+	struct edge_node *edge;
+
+	bb = entry_bb(bb_list);
+	edge = kcalloc(2, sizeof(*edge), GFP_KERNEL);
+	if (!edge)
+		return -ENOMEM;
+	edge->src = bb;
+	edge->dst = bb_next(bb);
+	list_add_tail(&edge->l, &bb->e_succs);
+	edge[1].src = edge->src;
+	edge[1].dst = edge->dst;
+	list_add_tail(&edge[1].l, &edge[1].dst->e_prevs);
+
+	exit_bb = exit_bb(bb_list);
+	bb = bb_next(bb);
+	list_for_each_entry_from(bb, &exit_bb->l, l) {
+		bool has_fallthrough, only_has_fallthrough;
+		bool has_branch, only_has_branch;
+		struct bb_node *next_bb = bb_next(bb);
+		int tail = next_bb->head - 1;
+		struct bpf_insn insn;
+		u8 code;
+
+		edge = kcalloc(2, sizeof(*edge), GFP_KERNEL);
+		if (!edge)
+			return -ENOMEM;
+		edge->src = bb;
+		edge[1].src = bb;
+
+		insn = insns[tail];
+		code = insn.code;
+		only_has_fallthrough = BPF_CLASS(code) != BPF_JMP ||
+				       BPF_OP(code) == BPF_EXIT;
+		has_fallthrough = only_has_fallthrough ||
+				  (BPF_CLASS(code) == BPF_JMP &&
+				   BPF_OP(code) != BPF_CALL &&
+				   BPF_OP(code) != BPF_JA);
+		only_has_branch = BPF_CLASS(code) == BPF_JMP &&
+				  BPF_OP(code) == BPF_JA;
+		has_branch = only_has_branch ||
+			     (BPF_CLASS(code) == BPF_JMP &&
+			      BPF_OP(code) != BPF_EXIT &&
+			      BPF_OP(code) != BPF_CALL);
+
+		if (has_fallthrough) {
+			if (BPF_CLASS(code) == BPF_JMP &&
+			    BPF_OP(code) == BPF_EXIT)
+				next_bb = exit_bb;
+			edge->dst = next_bb;
+			edge[1].dst = next_bb;
+			list_add_tail(&edge->l, &bb->e_succs);
+			list_add_tail(&edge[1].l, &edge[1].dst->e_prevs);
+			edge = NULL;
+		}
+
+		if (has_branch) {
+			struct bb_node *tgt;
+
+			if (!edge) {
+				edge = kcalloc(2, sizeof(*edge), GFP_KERNEL);
+				if (!edge)
+					return -ENOMEM;
+				edge->src = bb;
+				edge[1].src = bb;
+			}
+
+			tgt = search_bb_with_head(bb_list,
+						  tail + insn.off + 1);
+			if (!tgt)
+				return -EINVAL;
+
+			edge->dst = tgt;
+			edge[1].dst = tgt;
+			list_add_tail(&edge->l, &bb->e_succs);
+			list_add_tail(&edge[1].l, &tgt->e_prevs);
+		}
+	}
+
+	return 0;
+}
+
+static void subprog_free_edge(struct bb_node *bb)
+{
+	struct list_head *succs = &bb->e_succs;
+	struct edge_node *e, *tmp;
+
+	/* prevs and succs are allocated as pair, succs is the start addr. */
+	list_for_each_entry_safe(e, tmp, succs, l) {
+		list_del(&e->l);
+		kfree(e);
+	}
+}
+
 void subprog_free_bb(struct bpf_subprog_info *subprog, int end_idx)
 {
 	int i = 0;
 
 	for (; i <= end_idx; i++) {
 		struct list_head *bbs = &subprog[i].bbs;
-		struct bb_node *bb, *tmp;
+		struct bb_node *bb, *tmp, *exit;
 
-		list_for_each_entry_safe(bb, tmp, bbs, l) {
+		bb = entry_bb(bbs);
+		exit = exit_bb(bbs);
+		list_for_each_entry_safe_from(bb, tmp, &exit->l, l) {
+			subprog_free_edge(bb);
 			list_del(&bb->l);
 			kfree(bb);
 		}
diff --git a/kernel/bpf/cfg.h b/kernel/bpf/cfg.h
index 4092145..7a9d5dd 100644
--- a/kernel/bpf/cfg.h
+++ b/kernel/bpf/cfg.h
@@ -8,6 +8,7 @@
 #ifndef __BPF_CFG_H__
 #define __BPF_CFG_H__
 
+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_fini_bb(struct list_head *bb_list, int subprog_end);
 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 523e440..bcac7c8 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -900,6 +900,9 @@ static int check_subprogs(struct bpf_verifier_env *env)
 			ret = subprog_fini_bb(cur_bb_list, subprog_end);
 			if (ret < 0)
 				goto free_nodes;
+			ret = subprog_add_bb_edges(insn, cur_bb_list);
+			if (ret < 0)
+				goto free_nodes;
 			subprog_start = subprog_end;
 			cur_subprog++;
 			if (cur_subprog < env->subprog_cnt) {