[RFC PATCH 12/16] bpf: cfg: pretty print CFG and DOM

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

Add functions to pretty print the CFG and DOM table. We can also
add contrib scripts to print this dot format so tools can visualize
them. I at least found this helpful. Will add scripts in tools/bpf
follow up patch.

For development we are always printing these but should put these
noisy routines behind a verbose bit and/or only print when an error
has occured in bounded-loop logic.

Signed-off-by: John Fastabend <john.fastabend@gmail.com>
---
 kernel/bpf/cfg.c      |   54 +++++++++++++++++++++++++++++++++++++++++++++++++
 kernel/bpf/cfg.h      |    5 +++++
 kernel/bpf/verifier.c |    2 ++
 3 files changed, 61 insertions(+)

diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
index c67541c..0d50646 100644
--- a/kernel/bpf/cfg.c
+++ b/kernel/bpf/cfg.c
@@ -62,6 +62,60 @@ static struct bb_node *bb_next(struct cfg_node_allocator *allocator,
 	return (struct bb_node *)cfg_node_delink(allocator, &bb->link);
 }
 
+void cfg_pretty_print(struct bpf_verifier_env *env,
+		      struct cfg_node_allocator *allocator,
+		      struct bpf_subprog_info *subprog)
+{
+	void **bb_list = (void **)&subprog->bbs;
+	struct bb_node *bb, *exit_bb;
+
+	bb = entry_bb(bb_list);
+	exit_bb = exit_bb(bb_list);
+
+	bpf_verifier_log_write(env, "CFG: ");
+	while (bb && bb != exit_bb) {
+		struct bb_node *next_bb = bb_next(allocator, bb);
+		struct edge_node *e;
+
+		e = cfg_node_delink(allocator, &bb->e_succs);
+		while (e) {
+			struct bb_node *dst = e->dst;
+			int tail = next_bb->head - 1;
+			struct bb_node *dst_next;
+			int dst_tail;
+
+			dst_next = bb_next(allocator, dst);
+			dst_tail = dst_next ? dst_next->head - 1 : 65534;
+
+			bpf_verifier_log_write(env, " %i[%i,%i] -> %i[%i,%i] ",
+					       bb->idx, bb->head, tail, dst->idx, dst->head, dst_tail);
+			e = cfg_node_delink(allocator, &e->link);
+		}
+		bb = bb_next(allocator, bb);
+	}
+	bpf_verifier_log_write(env, "\n");
+}
+
+void dom_pretty_print(struct bpf_verifier_env *env,
+		      struct bpf_subprog_info *subprog)
+{
+	int lane_len, bb_num = subprog->bb_num - 2;
+	int i, j;
+
+	lane_len = BITS_TO_LONGS(bb_num);
+
+	bpf_verifier_log_write(env, "DOM:\n");
+	for (i = 0; i < bb_num; i++) {
+		for (j = 0; j < bb_num; j++) {
+			bpf_verifier_log_write(env, " %i ",
+			    test_bit(j,
+				     subprog->dtree + i * lane_len) ? 1 : 0);
+		}
+		bpf_verifier_log_write(env, "\n");
+	}
+	bpf_verifier_log_write(env, "\n");
+}
+
 struct dom_info {
 	u16 *dfs_parent;
 	u16 *dfs_order;
diff --git a/kernel/bpf/cfg.h b/kernel/bpf/cfg.h
index 8363406..44dcabb 100644
--- a/kernel/bpf/cfg.h
+++ b/kernel/bpf/cfg.h
@@ -37,6 +37,11 @@ bool subprog_has_loop(struct cfg_node_allocator *allocator,
 		      struct bpf_subprog_info *subprog);
 int subprog_has_irreduciable_loop(struct cfg_node_allocator *allocator,
 				  struct bpf_subprog_info *subprog);
+void cfg_pretty_print(struct bpf_verifier_env *env,
+		      struct cfg_node_allocator *allocator,
+		      struct bpf_subprog_info *subprog);
+void dom_pretty_print(struct bpf_verifier_env *env,
+		      struct bpf_subprog_info *subprog);
 int subprog_init_bb(struct cfg_node_allocator *allocator, void **bb_list,
 		    int subprog_start, int subprog_end);
 void subprog_free(struct bpf_subprog_info *subprog, int end_idx);
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 49895f3..610559a 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -913,6 +913,8 @@ static int check_subprogs(struct bpf_verifier_env *env)
 						     &subprog[cur_subprog]);
 			if (ret < 0)
 				goto free_nodes;
+			cfg_pretty_print(env, &allocator, &subprog[cur_subprog]);
+			dom_pretty_print(env, &subprog[cur_subprog]);
 			ret = subprog_has_irreduciable_loop(&allocator,
 							&subprog[cur_subprog]);
 			if (ret < 0)