[RFC PATCH 01/16] bpf: cfg: partition basic blocks for each subprog

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

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

"check_subprogs" has partitioned subprogs and is doing insn scan for each
subprog already, this patch extends it to also partition basic blocks (BB)
for each subprog.

  - The first insn for each subprog start a BB.
  - Branch (both cond and absolute) target start a BB.
  - Insn immediately follows branch insn start a BB.
    Insn immediately follows exit and within subprog start a BB.

BBs for each subprog are organized as a list in ascending head.

Two special BBs, entry and exit are added as well.

Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
Signed-off-by: John Fastabend <john.fastabend@gmail.com>
---
 include/linux/bpf_verifier.h |    1 
 kernel/bpf/Makefile          |    2 -
 kernel/bpf/cfg.c             |   93 ++++++++++++++++++++++++++++++++++++++++++
 kernel/bpf/cfg.h             |   16 +++++++
 kernel/bpf/verifier.c        |   57 +++++++++++++++++++++++---
 5 files changed, 162 insertions(+), 7 deletions(-)
 create mode 100644 kernel/bpf/cfg.c
 create mode 100644 kernel/bpf/cfg.h

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 38b04f5..c70faf5 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -177,6 +177,7 @@ static inline bool bpf_verifier_log_needed(const struct bpf_verifier_log *log)
 struct bpf_subprog_info {
 	u32 start; /* insn idx of function entry point */
 	u16 stack_depth; /* max. stack depth used by this function */
+	struct list_head bbs; /* basic blocks list. */
 };
 
 /* single container for all structs
diff --git a/kernel/bpf/Makefile b/kernel/bpf/Makefile
index f27f549..3ee9036 100644
--- a/kernel/bpf/Makefile
+++ b/kernel/bpf/Makefile
@@ -1,7 +1,7 @@
 # SPDX-License-Identifier: GPL-2.0
 obj-y := core.o
 
-obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o inode.o helpers.o tnum.o
+obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o inode.o helpers.o tnum.o cfg.o
 obj-$(CONFIG_BPF_SYSCALL) += hashtab.o arraymap.o percpu_freelist.o bpf_lru_list.o lpm_trie.o map_in_map.o
 obj-$(CONFIG_BPF_SYSCALL) += disasm.o
 obj-$(CONFIG_BPF_SYSCALL) += btf.o
diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
new file mode 100644
index 0000000..b1af714
--- /dev/null
+++ b/kernel/bpf/cfg.c
@@ -0,0 +1,93 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/* Copyright (C) 2018 Netronome Systems, Inc. */
+/* This program is free software; you can redistribute it and/or
+ * modify it under the terms of version 2 of the GNU General Public
+ * License as published by the Free Software Foundation.
+ */
+
+#include <linux/bpf_verifier.h>
+#include <linux/list.h>
+#include <linux/slab.h>
+
+#include "cfg.h"
+
+struct bb_node {
+	struct list_head l;
+	u16 head;
+};
+
+#define bb_prev(bb)		list_prev_entry(bb, l)
+#define bb_next(bb)		list_next_entry(bb, l)
+#define bb_first(bb_list)	list_first_entry(bb_list, struct bb_node, l)
+#define bb_last(bb_list)	list_last_entry(bb_list, struct bb_node, l)
+#define entry_bb(bb_list)	bb_first(bb_list)
+#define exit_bb(bb_list)	bb_last(bb_list)
+
+int subprog_append_bb(struct list_head *bb_list, int head)
+{
+	struct bb_node *new_bb, *bb;
+
+	list_for_each_entry(bb, bb_list, l) {
+		if (bb->head == head)
+			return 0;
+		else if (bb->head > head)
+			break;
+	}
+
+	bb = bb_prev(bb);
+	new_bb = kzalloc(sizeof(*new_bb), GFP_KERNEL);
+	if (!new_bb)
+		return -ENOMEM;
+
+	new_bb->head = head;
+	list_add(&new_bb->l, &bb->l);
+
+	return 0;
+}
+
+int subprog_fini_bb(struct list_head *bb_list, int subprog_end)
+{
+	struct bb_node *bb = kzalloc(sizeof(*bb), GFP_KERNEL);
+
+	if (!bb)
+		return -ENOMEM;
+	/* entry bb. */
+	bb->head = -1;
+	list_add(&bb->l, bb_list);
+
+	bb = kzalloc(sizeof(*bb), GFP_KERNEL);
+	if (!bb)
+		return -ENOMEM;
+	/* exit bb. */
+	bb->head = subprog_end;
+	list_add_tail(&bb->l, bb_list);
+
+	return 0;
+}
+
+int subprog_init_bb(struct list_head *bb_list, int subprog_start)
+{
+	int ret;
+
+	INIT_LIST_HEAD(bb_list);
+	ret = subprog_append_bb(bb_list, subprog_start);
+	if (ret < 0)
+		return ret;
+
+	return 0;
+}
+
+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;
+
+		list_for_each_entry_safe(bb, tmp, bbs, l) {
+			list_del(&bb->l);
+			kfree(bb);
+		}
+	}
+}
diff --git a/kernel/bpf/cfg.h b/kernel/bpf/cfg.h
new file mode 100644
index 0000000..4092145
--- /dev/null
+++ b/kernel/bpf/cfg.h
@@ -0,0 +1,16 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/* Copyright (C) 2018 Netronome Systems, Inc. */
+/* This program is free software; you can redistribute it and/or
+ * modify it under the terms of version 2 of the GNU General Public
+ * License as published by the Free Software Foundation.
+ */
+
+#ifndef __BPF_CFG_H__
+#define __BPF_CFG_H__
+
+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);
+void subprog_free_bb(struct bpf_subprog_info *subprog, int end_idx);
+
+#endif
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 1fd9667b..523e440 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -24,6 +24,7 @@
 #include <linux/sort.h>
 #include <linux/perf_event.h>
 
+#include "cfg.h"
 #include "disasm.h"
 
 static const struct bpf_verifier_ops * const bpf_verifier_ops[] = {
@@ -807,6 +808,7 @@ static int check_subprogs(struct bpf_verifier_env *env)
 	struct bpf_subprog_info *subprog = env->subprog_info;
 	struct bpf_insn *insn = env->prog->insnsi;
 	int insn_cnt = env->prog->len;
+	struct list_head *cur_bb_list;
 
 	/* Add entry function. */
 	ret = add_subprog(env, 0);
@@ -841,20 +843,46 @@ static int check_subprogs(struct bpf_verifier_env *env)
 		for (i = 0; i < env->subprog_cnt; i++)
 			verbose(env, "func#%d @%d\n", i, subprog[i].start);
 
-	/* now check that all jumps are within the same subprog */
 	subprog_start = subprog[cur_subprog].start;
 	subprog_end = subprog[cur_subprog + 1].start;
+	cur_bb_list = &subprog[cur_subprog].bbs;
+	ret = subprog_init_bb(cur_bb_list, subprog_start);
+	if (ret < 0)
+		goto free_nodes;
+	/* now check that all jumps are within the same subprog */
 	for (i = 0; i < insn_cnt; i++) {
 		u8 code = insn[i].code;
 
 		if (BPF_CLASS(code) != BPF_JMP)
 			goto next;
-		if (BPF_OP(code) == BPF_EXIT || BPF_OP(code) == BPF_CALL)
+
+		if (BPF_OP(code) == BPF_EXIT) {
+			if (i + 1 < subprog_end) {
+				ret = subprog_append_bb(cur_bb_list, i + 1);
+				if (ret < 0)
+					goto free_nodes;
+			}
+			goto next;
+		}
+
+		if (BPF_OP(code) == BPF_CALL)
 			goto next;
+
 		off = i + insn[i].off + 1;
 		if (off < subprog_start || off >= subprog_end) {
 			verbose(env, "jump out of range from insn %d to %d\n", i, off);
-			return -EINVAL;
+			ret = -EINVAL;
+			goto free_nodes;
+		}
+
+		ret = subprog_append_bb(cur_bb_list, off);
+		if (ret < 0)
+			goto free_nodes;
+
+		if (i + 1 < subprog_end) {
+			ret = subprog_append_bb(cur_bb_list, i + 1);
+			if (ret < 0)
+				goto free_nodes;
 		}
 next:
 		if (i == subprog_end - 1) {
@@ -865,15 +893,32 @@ static int check_subprogs(struct bpf_verifier_env *env)
 			if (code != (BPF_JMP | BPF_EXIT) &&
 			    code != (BPF_JMP | BPF_JA)) {
 				verbose(env, "last insn is not an exit or jmp\n");
-				return -EINVAL;
+				ret = -EINVAL;
+				goto free_nodes;
 			}
+
+			ret = subprog_fini_bb(cur_bb_list, subprog_end);
+			if (ret < 0)
+				goto free_nodes;
 			subprog_start = subprog_end;
 			cur_subprog++;
-			if (cur_subprog < env->subprog_cnt)
+			if (cur_subprog < env->subprog_cnt) {
 				subprog_end = subprog[cur_subprog + 1].start;
+				cur_bb_list = &subprog[cur_subprog].bbs;
+				ret = subprog_init_bb(cur_bb_list,
+						      subprog_start);
+				if (ret < 0)
+					goto free_nodes;
+			}
 		}
 	}
-	return 0;
+
+	ret = 0;
+
+free_nodes:
+	subprog_free_bb(subprog, cur_subprog == env->subprog_cnt ?
+					cur_subprog - 1 : cur_subprog);
+	return ret;
 }
 
 static