[RFC bpf-next 00/10] initial control flow support for eBPF verifier

[RFC bpf-next 00/10] initial control flow support for eBPF verifier

[Jiong Wang]

This patch introduce initial control flow infrastructure to eBPF verifier.
Various control flow information are built in an incremental way, so they
could be easily maintained at various level.

After this patch set, information collection on eBPF insns are centred at
check_subprogs, check_cfg and related code then are replaced by new
infrastructure.

Checks/Analysis offered by check_cfg are still offered by new
infrastructure. For example loop detection, recursive function call,
unreachable insn, prune heuristic marking.

This infrastructure comes with some memory usage and execution time cost.
Memory pool based allocation is used to avoid frequently calling of
kmalloc/free. Singly linked list and compact pointer are used to reduce
various cfg node size.

data structure size
===
  basic blocks     edge        call-graph edge
  16-bytes         24-bytes    6-bytes

memory usage (test_l4lb_noinline, test_xdp_noinline)
====
(counted all subprogs):

test_l4lb_noinline:

  cfg info:  597 insns, 12 subprogs
             107 basic-blocks, 278 edges, 12 call edges.

  mem usage: 9216(9K)-bytes for memory pool (basic-blocks/edges/call-edges)
             644-bytes for dominator trees.

test_xdp_noinline:

  cfg info:  1029 insns, 21 subprogs
             191 basic-basics, 502 edges, 23 call edges.

  mem usage: 15360(15K)-bytes for memory pool.
             1192-bytes for dominator trees.

The existing check_cfg is using two auxiliary arrays (insn_state and
insn_stack), insn_cnt * sizeof(int) bytes for each, so would use ~5K and
~8K accordingly.  (looks to me insn_state could use 1-byte element,
insn_stack could use 2-byte, so probably could reduced to ~2K and ~3K).

The existing check_cfg is using 8-bytes for each insn during cfg check.
The new infrastructure basically use 2x mems, 16-bytes for each insn.

execution time
===
test_l4lb_noinline:
  existing check_subprog/check_cfg: ~55000 ns
  new infrastructure: ~135000 ns

test_xdp_noinline:
  existing check_subprog/check_cfg: ~52000 ns
  new infrastructure: ~120000 ns

The control flow infrastructure could possibly lay the ground for further
static analysis inside eBPF verifier, for example bounded loop detection,
path-sensitive data-flow analysis etc.

Jiong Wang (10):
  bpf: cfg: partition basic blocks for each subprog
  bpf: cfg: add edges between basic blocks to form CFG
  bpf: cfg: build domination tree using Tarjan algorithm
  bpf: cfg: detect loop use domination information
  bpf: cfg: detect unreachable basic blocks
  bpf: cfg: move find_subprog/add_subprog to cfg.c
  bpf: cfg: build call graph and detect unreachable/recursive call
  bpf: cfg: remove push_insn and check_cfg
  bpf: cfg: reduce k*alloc/free call by using memory pool for allocating
    nodes
  bpf: cfg: reduce memory usage by using singly list + compat pointer

 include/linux/bpf_verifier.h |   8 +
 kernel/bpf/Makefile          |   2 +-
 kernel/bpf/cfg.c             | 956 +++++++++++++++++++++++++++++++++++++++++++
 kernel/bpf/cfg.h             |  42 ++
 kernel/bpf/verifier.c        | 386 ++++++-----------
 5 files changed, 1131 insertions(+), 263 deletions(-)
 create mode 100644 kernel/bpf/cfg.c
 create mode 100644 kernel/bpf/cfg.h

-- 
2.7.4

[RFC bpf-next 01/10] bpf: cfg: partition basic blocks for each subprog

[Jiong Wang]

"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>
---
 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 8f70dc1..404a5d8 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -176,6 +176,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 35c485f..b4542d8 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 65a6e2e..9c3eeef 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -23,6 +23,7 @@
 #include <linux/bsearch.h>
 #include <linux/sort.h>
 
+#include "cfg.h"
 #include "disasm.h"
 
 static const struct bpf_verifier_ops * const bpf_verifier_ops[] = {
@@ -782,6 +783,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);
@@ -816,20 +818,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) {
@@ -840,15 +868,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
-- 
2.7.4

[RFC bpf-next 02/10] bpf: cfg: add edges between basic blocks to form CFG

[Jiong Wang]

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

Signed-off-by: Jiong Wang <jiong.wang@netronome.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 9c3eeef..585e0a0 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -875,6 +875,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) {
-- 
2.7.4

[RFC bpf-next 03/10] bpf: cfg: build domination tree using Tarjan algorithm

[Jiong Wang]

  - When building domination information, we need to some array data
    structure, and need to index into them using basic block index.
    Calculate the basic block index during adding edges.

  - The Step-1 in Tarjan algorithm is to assign dfs order number for
    each bb in the cfg. We need to iterate on all bbs in reverse dfs order.

  - Step-2 and Step-3 in Tarjan algorithm to calculate semi-dominators and
    immediate-dominators implicitly and explicitly.

  - Step-4, we add a new bitmap field inside subprog_info to keep the
    dominator tree there.

  - Post-domination information is built but not tested.

Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
---
 include/linux/bpf_verifier.h |   3 +
 kernel/bpf/cfg.c             | 386 ++++++++++++++++++++++++++++++++++++++++++-
 kernel/bpf/cfg.h             |   3 +-
 kernel/bpf/verifier.c        |   5 +-
 4 files changed, 393 insertions(+), 4 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 404a5d8..9c0a808 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -177,6 +177,9 @@ 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. */
+	u32 bb_num; /* total basic block num. */
+	unsigned long *dtree;
+	bool dtree_avail;
 };
 
 /* single container for all structs
diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
index 208aac7..b50937a 100644
--- a/kernel/bpf/cfg.c
+++ b/kernel/bpf/cfg.c
@@ -17,11 +17,33 @@ struct edge_node {
 	struct bb_node *dst;
 };
 
+struct edge_iter {
+	struct list_head *list_head;
+	struct edge_node *edge;
+};
+
+#define first_edge(e_list)	list_first_entry(e_list, struct edge_node, l)
+#define last_edge(e_list)	list_last_entry(e_list, struct edge_node, l)
+#define next_edge(e)		list_next_entry(e, l)
+
+static bool ei_end_p(struct edge_iter *ei)
+{
+	return &ei->edge->l == ei->list_head;
+}
+
+static void ei_next(struct edge_iter *ei)
+{
+	struct edge_node *e = ei->edge;
+
+	ei->edge = next_edge(e);
+}
+
 struct bb_node {
 	struct list_head l;
 	struct list_head e_prevs;
 	struct list_head e_succs;
 	u16 head;
+	u16 idx;
 };
 
 #define bb_prev(bb)		list_prev_entry(bb, l)
@@ -31,6 +53,27 @@ struct bb_node {
 #define entry_bb(bb_list)	bb_first(bb_list)
 #define exit_bb(bb_list)	bb_last(bb_list)
 
+struct dom_info {
+	u16 *dfs_parent;
+	u16 *dfs_order;
+	struct bb_node **dfs_to_bb;
+	/* immediate-dominator */
+	u16 *idom;
+	/* semi-dominator */
+	u16 *sdom;
+	u16 *bucket;
+	u16 *next_bucket;
+	/* best node during path compression. */
+	u16 *best;
+	/* ancestor along tree edge. */
+	u16 *ancestor;
+	/* size and child are used for tree balancing. */
+	u16 *size;
+	u16 *child;
+
+	u16 dfsnum;
+};
+
 int subprog_append_bb(struct list_head *bb_list, int head)
 {
 	struct bb_node *new_bb, *bb;
@@ -107,6 +150,7 @@ int subprog_add_bb_edges(struct bpf_insn *insns, struct list_head *bb_list)
 {
 	struct bb_node *bb, *exit_bb;
 	struct edge_node *edge;
+	int bb_num;
 
 	bb = entry_bb(bb_list);
 	edge = kcalloc(2, sizeof(*edge), GFP_KERNEL);
@@ -118,9 +162,12 @@ int subprog_add_bb_edges(struct bpf_insn *insns, struct list_head *bb_list)
 	edge[1].src = edge->src;
 	edge[1].dst = edge->dst;
 	list_add_tail(&edge[1].l, &edge[1].dst->e_prevs);
+	bb->idx = -1;
 
 	exit_bb = exit_bb(bb_list);
+	exit_bb->idx = -2;
 	bb = bb_next(bb);
+	bb_num = 0;
 	list_for_each_entry_from(bb, &exit_bb->l, l) {
 		bool has_fallthrough, only_has_fallthrough;
 		bool has_branch, only_has_branch;
@@ -129,6 +176,8 @@ int subprog_add_bb_edges(struct bpf_insn *insns, struct list_head *bb_list)
 		struct bpf_insn insn;
 		u8 code;
 
+		bb->idx = bb_num++;
+
 		edge = kcalloc(2, sizeof(*edge), GFP_KERNEL);
 		if (!edge)
 			return -ENOMEM;
@@ -184,9 +233,341 @@ int subprog_add_bb_edges(struct bpf_insn *insns, struct list_head *bb_list)
 		}
 	}
 
+	return bb_num + 2;
+}
+
+static int init_dom_info(struct bpf_subprog_info *subprog, struct dom_info *di)
+{
+	u16 *p, bb_num, i;
+
+	di->dfs_parent = NULL;
+	di->dfs_to_bb = NULL;
+
+	bb_num = subprog->bb_num;
+	p = kcalloc(10 * bb_num, sizeof(*p), GFP_KERNEL);
+	if (!p)
+		return -ENOMEM;
+
+	di->dfs_parent = p;
+	di->dfs_order = di->dfs_parent + bb_num;
+	di->idom = di->dfs_order + bb_num;
+	di->sdom = di->idom + bb_num;
+	di->bucket = di->sdom + bb_num;
+	di->next_bucket = di->bucket + bb_num;
+	di->best = di->next_bucket + bb_num;
+	di->ancestor = di->best + bb_num;
+	di->size = di->ancestor + bb_num;
+	di->child = di->size + bb_num;
+	di->dfs_to_bb = kcalloc(bb_num, sizeof(struct bb_node *), GFP_KERNEL);
+	di->dfsnum = 1;
+
+	for (i = 0; i < bb_num; i++) {
+		di->size[i] = 1;
+		di->best[i] = i;
+		di->sdom[i] = i;
+	}
+
 	return 0;
 }
 
+static void compress_path(struct dom_info *di, unsigned int v)
+{
+	unsigned int parent = di->ancestor[v];
+
+	if (di->ancestor[parent]) {
+		compress_path(di, parent);
+
+		if (di->sdom[di->best[parent]] < di->sdom[di->best[v]])
+			di->best[v] = di->best[parent];
+
+		di->ancestor[v] = di->ancestor[parent];
+	}
+}
+
+static unsigned int eval(struct dom_info *di, unsigned int v)
+{
+	unsigned int ancestor = di->ancestor[v];
+
+	/* v is root. */
+	if (!ancestor)
+		return di->best[v];
+
+	/* compress path */
+	compress_path(di, v);
+	ancestor = di->ancestor[v];
+
+	if (di->sdom[di->best[ancestor]] >= di->sdom[di->best[v]])
+		return di->best[v];
+	else
+		return di->best[ancestor];
+}
+
+/* Re-balancing the tree before linking. */
+static void link(struct dom_info *di, unsigned int v, unsigned int w)
+{
+	unsigned int s = w;
+
+	while (di->sdom[di->best[w]] < di->sdom[di->best[di->child[s]]]) {
+		if (di->size[s] + di->size[di->child[di->child[s]]] >=
+			2 * di->size[di->child[s]]) {
+			di->ancestor[di->child[s]] = s;
+			di->child[s] = di->child[di->child[s]];
+		} else {
+			di->size[di->child[s]] = di->size[s];
+			di->ancestor[s] = di->child[s];
+			s = di->child[s];
+		}
+	}
+
+	di->best[s] = di->best[w];
+	di->size[v] += di->size[w];
+	if (di->size[v] < 2 * di->size[w]) {
+		unsigned int t = s;
+
+		s = di->child[v];
+		di->child[v] = t;
+	}
+
+	while (s) {
+		di->ancestor[s] = v;
+		s = di->child[s];
+	}
+}
+
+static void calc_idoms(struct bpf_subprog_info *subprog, struct dom_info *di,
+		       bool reverse)
+{
+	u16 entry_bb_fake_idx = subprog->bb_num - 2, idx, w, k, par;
+	struct list_head *bb_list = &subprog->bbs;
+	struct bb_node *entry_bb;
+	struct edge_iter ei;
+
+	if (reverse)
+		entry_bb = exit_bb(bb_list);
+	else
+		entry_bb = entry_bb(bb_list);
+	idx = di->dfsnum - 1;
+
+	while (idx > 1) {
+		struct bb_node *bb = di->dfs_to_bb[idx];
+		struct edge_node *e;
+
+		par = di->dfs_parent[idx];
+		k = idx;
+
+		if (reverse) {
+			ei.edge = first_edge(&bb->e_succs);
+			ei.list_head = &bb->e_succs;
+		} else {
+			ei.edge = first_edge(&bb->e_prevs);
+			ei.list_head = &bb->e_prevs;
+		}
+
+		while (!ei_end_p(&ei)) {
+			struct bb_node *b;
+			u16 k1;
+
+			e = ei.edge;
+			if (reverse)
+				b = e->dst;
+			else
+				b = e->src;
+			ei_next(&ei);
+
+			if (b == entry_bb)
+				k1 = di->dfs_order[entry_bb_fake_idx];
+			else
+				k1 = di->dfs_order[b->idx];
+
+			if (k1 > idx)
+				k1 = di->sdom[eval(di, k1)];
+			if (k1 < k)
+				k = k1;
+		}
+
+		di->sdom[idx] = k;
+		link(di, par, idx);
+		di->next_bucket[idx] = di->bucket[k];
+		di->bucket[k] = idx;
+
+		for (w = di->bucket[par]; w; w = di->next_bucket[w]) {
+			k = eval(di, w);
+			if (di->sdom[k] < di->sdom[w])
+				di->idom[w] = k;
+			else
+				di->idom[w] = par;
+		}
+		di->bucket[par] = 0;
+		idx--;
+	}
+
+	di->idom[1] = 0;
+	for (idx = 2; idx <= di->dfsnum - 1; idx++)
+		if (di->idom[idx] != di->sdom[idx])
+			di->idom[idx] = di->idom[di->idom[idx]];
+}
+
+static int calc_dfs_tree(struct bpf_subprog_info *subprog, struct dom_info *di,
+			 bool reverse)
+{
+	u16 bb_num = subprog->bb_num, sp = 0, idx, parent_idx;
+	struct list_head *bb_list = &subprog->bbs;
+	u16 entry_bb_fake_idx = bb_num - 2;
+	struct bb_node *entry_bb, *exit_bb;
+	struct edge_iter ei, *stack;
+	struct edge_node *e;
+
+	di->dfs_order[entry_bb_fake_idx] = di->dfsnum;
+
+	stack = kmalloc_array(bb_num - 1, sizeof(struct edge_iter), GFP_KERNEL);
+	if (!stack)
+		return -ENOMEM;
+
+	if (reverse) {
+		entry_bb = exit_bb(bb_list);
+		exit_bb = entry_bb(bb_list);
+		di->dfs_to_bb[di->dfsnum++] = exit_bb;
+		ei.edge = first_edge(&entry_bb->e_prevs);
+		ei.list_head = &entry_bb->e_prevs;
+	} else {
+		entry_bb = entry_bb(bb_list);
+		exit_bb = exit_bb(bb_list);
+		di->dfs_to_bb[di->dfsnum++] = entry_bb;
+		ei.edge = first_edge(&entry_bb->e_succs);
+		ei.list_head = &entry_bb->e_succs;
+	}
+
+	while (1) {
+		struct bb_node *bb_dst, *bb_src;
+
+		while (!ei_end_p(&ei)) {
+			e = ei.edge;
+
+			if (reverse) {
+				bb_dst = e->src;
+				if (bb_dst == exit_bb ||
+				    di->dfs_order[bb_dst->idx]) {
+					ei_next(&ei);
+					continue;
+				}
+				bb_src = e->dst;
+			} else {
+				bb_dst = e->dst;
+				if (bb_dst == exit_bb ||
+				    di->dfs_order[bb_dst->idx]) {
+					ei_next(&ei);
+					continue;
+				}
+				bb_src = e->src;
+			}
+
+			if (bb_src != entry_bb)
+				parent_idx = di->dfs_order[bb_src->idx];
+			else
+				parent_idx = di->dfs_order[entry_bb_fake_idx];
+
+			idx = di->dfsnum++;
+			di->dfs_order[bb_dst->idx] = idx;
+			di->dfs_to_bb[idx] = bb_dst;
+			di->dfs_parent[idx] = parent_idx;
+
+			stack[sp++] = ei;
+			if (reverse) {
+				ei.edge = first_edge(&bb_dst->e_prevs);
+				ei.list_head = &bb_dst->e_prevs;
+			} else {
+				ei.edge = first_edge(&bb_dst->e_succs);
+				ei.list_head = &bb_dst->e_succs;
+			}
+		}
+
+		if (!sp)
+			break;
+
+		ei = stack[--sp];
+		ei_next(&ei);
+	}
+
+	kfree(stack);
+
+	return 0;
+}
+
+static int idoms_to_doms(struct bpf_subprog_info *subprog, struct dom_info *di)
+{
+	int bb_num, i, end_index, bb, bb_idom, lane_len;
+	unsigned long *bitmap;
+
+	bb_num = subprog->bb_num - 2;
+	lane_len = BITS_TO_LONGS(bb_num);
+	bitmap = kcalloc(bb_num, lane_len * sizeof(long), GFP_KERNEL);
+	subprog->dtree = bitmap;
+	if (!subprog->dtree)
+		return -ENOMEM;
+	subprog->dtree_avail = true;
+	end_index = di->dfs_order[bb_num];
+
+	for (i = 1; i <= di->dfsnum - 1; i++) {
+		if (i == end_index)
+			continue;
+
+		bb = di->dfs_to_bb[i]->idx;
+		if (di->idom[i] && di->idom[i] != end_index) {
+			bb_idom = di->dfs_to_bb[di->idom[i]]->idx;
+			bitmap_copy(bitmap + bb * lane_len,
+				    bitmap + bb_idom * lane_len, bb_num);
+		}
+
+		bitmap_set(bitmap + bb * lane_len, bb, 1);
+	}
+
+	return 0;
+}
+
+/* Build domination information using Lengauer and Tarjan algorithm.
+ *
+ *   1. dfs on cfg to assign dfs-num for each node(bb).
+ *   2. calculate semi-dominator and calculate immediate dominator when
+ *      possible.
+ *   3. calculate immediate dominator not finished during step 2.
+ *   4. build domination bitmap using immediate dominator information.
+ *
+ * See:
+ *   A fast algorithm for finding dominators in a flowgraph.
+ *     - 1979, by T Lengauer and R Tarjan
+ *
+ *   Especially, Appendix B: The Complete Dominators Algorithms.
+ *
+ * The implementation also referenced GNU GCC 3.0.
+ */
+
+int subprog_build_dom_info(struct bpf_subprog_info *subprog)
+{
+	struct dom_info di;
+	int ret;
+
+	ret = init_dom_info(subprog, &di);
+	if (ret < 0)
+		goto free_dominfo;
+
+	ret = calc_dfs_tree(subprog, &di, false);
+	if (ret < 0)
+		goto free_dominfo;
+
+	calc_idoms(subprog, &di, false);
+	ret = idoms_to_doms(subprog, &di);
+	if (ret < 0)
+		goto free_dominfo;
+
+	ret = 0;
+
+free_dominfo:
+	if (di.dfs_parent)
+		kfree(di.dfs_parent);
+
+	return ret;
+}
+
 static void subprog_free_edge(struct bb_node *bb)
 {
 	struct list_head *succs = &bb->e_succs;
@@ -199,7 +580,7 @@ static void subprog_free_edge(struct bb_node *bb)
 	}
 }
 
-void subprog_free_bb(struct bpf_subprog_info *subprog, int end_idx)
+void subprog_free(struct bpf_subprog_info *subprog, int end_idx)
 {
 	int i = 0;
 
@@ -214,5 +595,8 @@ void subprog_free_bb(struct bpf_subprog_info *subprog, int end_idx)
 			list_del(&bb->l);
 			kfree(bb);
 		}
+
+		if (subprog[i].dtree_avail)
+			kfree(subprog[i].dtree);
 	}
 }
diff --git a/kernel/bpf/cfg.h b/kernel/bpf/cfg.h
index 7a9d5dd..cbb44f2 100644
--- a/kernel/bpf/cfg.h
+++ b/kernel/bpf/cfg.h
@@ -10,8 +10,9 @@
 
 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_build_dom_info(struct bpf_subprog_info *subprog);
 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);
+void subprog_free(struct bpf_subprog_info *subprog, int end_idx);
 
 #endif
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 585e0a0..6543470 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -878,6 +878,7 @@ static int check_subprogs(struct bpf_verifier_env *env)
 			ret = subprog_add_bb_edges(insn, cur_bb_list);
 			if (ret < 0)
 				goto free_nodes;
+			subprog[cur_subprog].bb_num = ret;
 			subprog_start = subprog_end;
 			cur_subprog++;
 			if (cur_subprog < env->subprog_cnt) {
@@ -894,8 +895,8 @@ static int check_subprogs(struct bpf_verifier_env *env)
 	ret = 0;
 
 free_nodes:
-	subprog_free_bb(subprog, cur_subprog == env->subprog_cnt ?
-					cur_subprog - 1 : cur_subprog);
+	subprog_free(subprog, cur_subprog == env->subprog_cnt ?
+				cur_subprog - 1 : cur_subprog);
 	return ret;
 }
 
-- 
2.7.4

[RFC bpf-next 04/10] bpf: cfg: detect loop use domination information

[Jiong Wang]

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

Signed-off-by: Jiong Wang <jiong.wang@netronome.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_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_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 6543470..a93aa43 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -879,6 +879,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) {
-- 
2.7.4

[RFC bpf-next 05/10] bpf: cfg: detect unreachable basic blocks

[Jiong Wang]

Do unreachable basic blocks detection as a side-product of the dfs walk
when building domination information.

Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
---
 kernel/bpf/cfg.c      | 31 ++++++++++++++++++++++++++-----
 kernel/bpf/cfg.h      |  3 ++-
 kernel/bpf/verifier.c |  3 ++-
 3 files changed, 30 insertions(+), 7 deletions(-)

diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
index 90692e4..7ce1472 100644
--- a/kernel/bpf/cfg.c
+++ b/kernel/bpf/cfg.c
@@ -407,15 +407,17 @@ static void calc_idoms(struct bpf_subprog_info *subprog, struct dom_info *di,
 			di->idom[idx] = di->idom[di->idom[idx]];
 }
 
-static int calc_dfs_tree(struct bpf_subprog_info *subprog, struct dom_info *di,
-			 bool reverse)
+static int
+calc_dfs_tree(struct bpf_verifier_env *env, struct bpf_subprog_info *subprog,
+	      struct dom_info *di, bool reverse)
 {
-	u16 bb_num = subprog->bb_num, sp = 0, idx, parent_idx;
+	u16 bb_num = subprog->bb_num, sp = 0, idx, parent_idx, i;
 	struct list_head *bb_list = &subprog->bbs;
 	u16 entry_bb_fake_idx = bb_num - 2;
 	struct bb_node *entry_bb, *exit_bb;
 	struct edge_iter ei, *stack;
 	struct edge_node *e;
+	bool *visited;
 
 	di->dfs_order[entry_bb_fake_idx] = di->dfsnum;
 
@@ -423,6 +425,10 @@ static int calc_dfs_tree(struct bpf_subprog_info *subprog, struct dom_info *di,
 	if (!stack)
 		return -ENOMEM;
 
+	visited = kcalloc(bb_num - 2, sizeof(bool), GFP_KERNEL);
+	if (!visited)
+		return -ENOMEM;
+
 	if (reverse) {
 		entry_bb = exit_bb(bb_list);
 		exit_bb = entry_bb(bb_list);
@@ -445,6 +451,8 @@ static int calc_dfs_tree(struct bpf_subprog_info *subprog, struct dom_info *di,
 
 			if (reverse) {
 				bb_dst = e->src;
+				if (bb_dst != exit_bb)
+					visited[bb_dst->idx] = true;
 				if (bb_dst == exit_bb ||
 				    di->dfs_order[bb_dst->idx]) {
 					ei_next(&ei);
@@ -453,6 +461,8 @@ static int calc_dfs_tree(struct bpf_subprog_info *subprog, struct dom_info *di,
 				bb_src = e->dst;
 			} else {
 				bb_dst = e->dst;
+				if (bb_dst != exit_bb)
+					visited[bb_dst->idx] = true;
 				if (bb_dst == exit_bb ||
 				    di->dfs_order[bb_dst->idx]) {
 					ei_next(&ei);
@@ -490,6 +500,16 @@ static int calc_dfs_tree(struct bpf_subprog_info *subprog, struct dom_info *di,
 
 	kfree(stack);
 
+	for (i = 0; i < bb_num - 2; i++) {
+		if (!visited[i]) {
+			bpf_verifier_log_write(env, "cfg - unreachable insn\n");
+			kfree(visited);
+			return -EINVAL;
+		}
+	}
+
+	kfree(visited);
+
 	return 0;
 }
 
@@ -541,7 +561,8 @@ static int idoms_to_doms(struct bpf_subprog_info *subprog, struct dom_info *di)
  * The implementation also referenced GNU GCC 3.0.
  */
 
-int subprog_build_dom_info(struct bpf_subprog_info *subprog)
+int subprog_build_dom_info(struct bpf_verifier_env *env,
+			   struct bpf_subprog_info *subprog)
 {
 	struct dom_info di;
 	int ret;
@@ -550,7 +571,7 @@ int subprog_build_dom_info(struct bpf_subprog_info *subprog)
 	if (ret < 0)
 		goto free_dominfo;
 
-	ret = calc_dfs_tree(subprog, &di, false);
+	ret = calc_dfs_tree(env, subprog, &di, false);
 	if (ret < 0)
 		goto free_dominfo;
 
diff --git a/kernel/bpf/cfg.h b/kernel/bpf/cfg.h
index c02c4cf..02729a9 100644
--- a/kernel/bpf/cfg.h
+++ b/kernel/bpf/cfg.h
@@ -10,7 +10,8 @@
 
 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_build_dom_info(struct bpf_subprog_info *subprog);
+int subprog_build_dom_info(struct bpf_verifier_env *env,
+			   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);
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index a93aa43..46d5eae 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -879,7 +879,8 @@ 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]);
+			ret = subprog_build_dom_info(env,
+						     &subprog[cur_subprog]);
 			if (ret < 0)
 				goto free_nodes;
 			if (subprog_has_loop(&subprog[cur_subprog])) {
-- 
2.7.4

[RFC bpf-next 06/10] bpf: cfg: move find_subprog/add_subprog to cfg.c

[Jiong Wang]

This patch centre find_subprog and add_subprog to cfg.c.

Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
---
 kernel/bpf/cfg.c      | 41 +++++++++++++++++++++++++++++++++++++++++
 kernel/bpf/cfg.h      |  2 ++
 kernel/bpf/verifier.c | 42 ------------------------------------------
 3 files changed, 43 insertions(+), 42 deletions(-)

diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
index 7ce1472..a34a95c 100644
--- a/kernel/bpf/cfg.c
+++ b/kernel/bpf/cfg.c
@@ -6,8 +6,10 @@
  */
 
 #include <linux/bpf_verifier.h>
+#include <linux/bsearch.h>
 #include <linux/list.h>
 #include <linux/slab.h>
+#include <linux/sort.h>
 
 #include "cfg.h"
 
@@ -611,6 +613,45 @@ bool subprog_has_loop(struct bpf_subprog_info *subprog)
 	return false;
 }
 
+static int cmp_subprogs(const void *a, const void *b)
+{
+	return ((struct bpf_subprog_info *)a)->start -
+	       ((struct bpf_subprog_info *)b)->start;
+}
+
+int find_subprog(struct bpf_verifier_env *env, int off)
+{
+	struct bpf_subprog_info *p;
+
+	p = bsearch(&off, env->subprog_info, env->subprog_cnt,
+		    sizeof(env->subprog_info[0]), cmp_subprogs);
+	if (!p)
+		return -ENOENT;
+	return p - env->subprog_info;
+}
+
+int add_subprog(struct bpf_verifier_env *env, int off)
+{
+	int insn_cnt = env->prog->len;
+	int ret;
+
+	if (off >= insn_cnt || off < 0) {
+		bpf_verifier_log_write(env, "call to invalid destination\n");
+		return -EINVAL;
+	}
+	ret = find_subprog(env, off);
+	if (ret >= 0)
+		return 0;
+	if (env->subprog_cnt >= BPF_MAX_SUBPROGS) {
+		bpf_verifier_log_write(env, "too many subprograms\n");
+		return -E2BIG;
+	}
+	env->subprog_info[env->subprog_cnt++].start = off;
+	sort(env->subprog_info, env->subprog_cnt,
+	     sizeof(env->subprog_info[0]), cmp_subprogs, NULL);
+	return 0;
+}
+
 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 02729a9..57eab9b 100644
--- a/kernel/bpf/cfg.h
+++ b/kernel/bpf/cfg.h
@@ -8,6 +8,8 @@
 #ifndef __BPF_CFG_H__
 #define __BPF_CFG_H__
 
+int add_subprog(struct bpf_verifier_env *env, int off);
+int find_subprog(struct bpf_verifier_env *env, int off);
 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_build_dom_info(struct bpf_verifier_env *env,
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 46d5eae..72bda84 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -20,8 +20,6 @@
 #include <linux/file.h>
 #include <linux/vmalloc.h>
 #include <linux/stringify.h>
-#include <linux/bsearch.h>
-#include <linux/sort.h>
 
 #include "cfg.h"
 #include "disasm.h"
@@ -737,46 +735,6 @@ enum reg_arg_type {
 	DST_OP_NO_MARK	/* same as above, check only, don't mark */
 };
 
-static int cmp_subprogs(const void *a, const void *b)
-{
-	return ((struct bpf_subprog_info *)a)->start -
-	       ((struct bpf_subprog_info *)b)->start;
-}
-
-static int find_subprog(struct bpf_verifier_env *env, int off)
-{
-	struct bpf_subprog_info *p;
-
-	p = bsearch(&off, env->subprog_info, env->subprog_cnt,
-		    sizeof(env->subprog_info[0]), cmp_subprogs);
-	if (!p)
-		return -ENOENT;
-	return p - env->subprog_info;
-
-}
-
-static int add_subprog(struct bpf_verifier_env *env, int off)
-{
-	int insn_cnt = env->prog->len;
-	int ret;
-
-	if (off >= insn_cnt || off < 0) {
-		verbose(env, "call to invalid destination\n");
-		return -EINVAL;
-	}
-	ret = find_subprog(env, off);
-	if (ret >= 0)
-		return 0;
-	if (env->subprog_cnt >= BPF_MAX_SUBPROGS) {
-		verbose(env, "too many subprograms\n");
-		return -E2BIG;
-	}
-	env->subprog_info[env->subprog_cnt++].start = off;
-	sort(env->subprog_info, env->subprog_cnt,
-	     sizeof(env->subprog_info[0]), cmp_subprogs, NULL);
-	return 0;
-}
-
 static int check_subprogs(struct bpf_verifier_env *env)
 {
 	int i, ret, subprog_start, subprog_end, off, cur_subprog = 0;
-- 
2.7.4

[RFC bpf-next 07/10] bpf: cfg: build call graph and detect unreachable/recursive call

[Jiong Wang]

This patch build call graph during insn scan inside check_subprogs.
Then do recursive and unreachable subprog detection using call graph.

Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
---
 include/linux/bpf_verifier.h |   1 +
 kernel/bpf/cfg.c             | 133 +++++++++++++++++++++++++++++++++++++++++++
 kernel/bpf/cfg.h             |   4 ++
 kernel/bpf/verifier.c        |  32 +++++++++--
 4 files changed, 166 insertions(+), 4 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 9c0a808..96337ba 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -176,6 +176,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 callees; /* callees list. */
 	struct list_head bbs; /* basic blocks list. */
 	u32 bb_num; /* total basic block num. */
 	unsigned long *dtree;
diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
index a34a95c..174e3f0 100644
--- a/kernel/bpf/cfg.c
+++ b/kernel/bpf/cfg.c
@@ -13,6 +13,12 @@
 
 #include "cfg.h"
 
+struct cedge_node {
+	struct list_head l;
+	u8 caller_idx;
+	u8 callee_idx;
+};
+
 struct edge_node {
 	struct list_head l;
 	struct bb_node *src;
@@ -652,6 +658,126 @@ int add_subprog(struct bpf_verifier_env *env, int off)
 	return 0;
 }
 
+struct callee_iter {
+	struct list_head *list_head;
+	struct cedge_node *callee;
+};
+
+#define first_callee(c_list)	list_first_entry(c_list, struct cedge_node, l)
+#define next_callee(c)		list_next_entry(c, l)
+
+static bool ci_end_p(struct callee_iter *ci)
+{
+	return &ci->callee->l == ci->list_head;
+}
+
+static void ci_next(struct callee_iter *ci)
+{
+	struct cedge_node *c = ci->callee;
+
+	ci->callee = next_callee(c);
+}
+
+#define EXPLORING	1
+#define EXPLORED	2
+int cgraph_check_recursive_unreachable(struct bpf_verifier_env *env,
+				       struct bpf_subprog_info *subprog)
+{
+	struct callee_iter *stack;
+	struct cedge_node *callee;
+	int sp = 0, idx = 0, ret;
+	struct callee_iter ci;
+	int *status;
+
+	stack = kmalloc_array(128, sizeof(struct callee_iter), GFP_KERNEL);
+	if (!stack)
+		return -ENOMEM;
+	status = kcalloc(env->subprog_cnt, sizeof(int), GFP_KERNEL);
+	if (!status) {
+		kfree(stack);
+		return -ENOMEM;
+	}
+	ci.callee = first_callee(&subprog->callees);
+	ci.list_head = &subprog->callees;
+	status[0] = EXPLORING;
+
+	while (1) {
+		while (!ci_end_p(&ci)) {
+			callee = ci.callee;
+			idx = callee->callee_idx;
+			if (status[idx] == EXPLORING) {
+				bpf_verifier_log_write(env, "cgraph - recursive call\n");
+				ret = -EINVAL;
+				goto err_free;
+			}
+
+			status[idx] = EXPLORING;
+
+			if (sp == 127) {
+				bpf_verifier_log_write(env, "cgraph - call frame too deep\n");
+				ret = -EINVAL;
+				goto err_free;
+			}
+
+			stack[sp++] = ci;
+			ci.callee = first_callee(&subprog[idx].callees);
+			ci.list_head = &subprog[idx].callees;
+		}
+
+		if (!list_empty(ci.list_head))
+			status[first_callee(ci.list_head)->caller_idx] =
+				EXPLORED;
+		else
+			/* leaf func. */
+			status[idx] = EXPLORED;
+
+		if (!sp)
+			break;
+
+		ci = stack[--sp];
+		ci_next(&ci);
+	}
+
+	for (idx = 0; idx < env->subprog_cnt; idx++)
+		if (status[idx] != EXPLORED) {
+			bpf_verifier_log_write(env, "cgraph - unreachable subprog\n");
+			ret = -EINVAL;
+			goto err_free;
+		}
+
+	ret = 0;
+err_free:
+	kfree(status);
+	kfree(stack);
+	return ret;
+}
+
+int subprog_append_callee(struct bpf_verifier_env *env,
+			  struct list_head *callees_list,
+			  int caller_idx, int off)
+{
+	int callee_idx = find_subprog(env, off);
+	struct cedge_node *new_callee, *callee;
+
+	if (callee_idx < 0)
+		return callee_idx;
+
+	list_for_each_entry(callee, callees_list, l) {
+		if (callee->callee_idx == callee_idx)
+			return 0;
+	}
+
+	new_callee = kzalloc(sizeof(*new_callee), GFP_KERNEL);
+	if (!new_callee)
+		return -ENOMEM;
+
+	new_callee->caller_idx = caller_idx;
+	new_callee->callee_idx = callee_idx;
+	list_add_tail(&new_callee->l, callees_list);
+
+	return 0;
+}
+
 static void subprog_free_edge(struct bb_node *bb)
 {
 	struct list_head *succs = &bb->e_succs;
@@ -669,7 +795,9 @@ void subprog_free(struct bpf_subprog_info *subprog, int end_idx)
 	int i = 0;
 
 	for (; i <= end_idx; i++) {
+		struct list_head *callees = &subprog[i].callees;
 		struct list_head *bbs = &subprog[i].bbs;
+		struct cedge_node *callee, *tmp_callee;
 		struct bb_node *bb, *tmp, *exit;
 
 		bb = entry_bb(bbs);
@@ -680,6 +808,11 @@ void subprog_free(struct bpf_subprog_info *subprog, int end_idx)
 			kfree(bb);
 		}
 
+		list_for_each_entry_safe(callee, tmp_callee, callees, l) {
+			list_del(&callee->l);
+			kfree(callee);
+		}
+
 		if (subprog[i].dtree_avail)
 			kfree(subprog[i].dtree);
 	}
diff --git a/kernel/bpf/cfg.h b/kernel/bpf/cfg.h
index 57eab9b..577c22c 100644
--- a/kernel/bpf/cfg.h
+++ b/kernel/bpf/cfg.h
@@ -9,9 +9,13 @@
 #define __BPF_CFG_H__
 
 int add_subprog(struct bpf_verifier_env *env, int off);
+int cgraph_check_recursive_unreachable(struct bpf_verifier_env *env,
+				       struct bpf_subprog_info *subprog);
 int find_subprog(struct bpf_verifier_env *env, int off);
 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_append_callee(struct bpf_verifier_env *env,
+			  struct list_head *bb_list, int caller_idx, int off);
 int subprog_build_dom_info(struct bpf_verifier_env *env,
 			   struct bpf_subprog_info *subprog);
 int subprog_fini_bb(struct list_head *bb_list, int subprog_end);
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 72bda84..12f5399 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -739,9 +739,9 @@ static int check_subprogs(struct bpf_verifier_env *env)
 {
 	int i, ret, subprog_start, subprog_end, off, cur_subprog = 0;
 	struct bpf_subprog_info *subprog = env->subprog_info;
+	struct list_head *cur_bb_list, *cur_callee_list;
 	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);
@@ -772,16 +772,23 @@ static int check_subprogs(struct bpf_verifier_env *env)
 	 */
 	subprog[env->subprog_cnt].start = insn_cnt;
 
-	if (env->log.level > 1)
-		for (i = 0; i < env->subprog_cnt; i++)
+	for (i = 0; i < env->subprog_cnt; i++) {
+		if (env->log.level > 1)
 			verbose(env, "func#%d @%d\n", i, subprog[i].start);
 
+		/* Don't init callees inside add_subprog which will sort the
+		 * array which breaks list link.
+		 */
+		INIT_LIST_HEAD(&subprog[i].callees);
+	}
+
 	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;
+	cur_callee_list = &env->subprog_info[cur_subprog].callees;
 	/* now check that all jumps are within the same subprog */
 	for (i = 0; i < insn_cnt; i++) {
 		u8 code = insn[i].code;
@@ -798,8 +805,20 @@ static int check_subprogs(struct bpf_verifier_env *env)
 			goto next;
 		}
 
-		if (BPF_OP(code) == BPF_CALL)
+		if (BPF_OP(code) == BPF_CALL) {
+			if (insn[i].src_reg == BPF_PSEUDO_CALL) {
+				int target = i + insn[i].imm + 1;
+
+				ret = subprog_append_callee(env,
+							    cur_callee_list,
+							    cur_subprog,
+							    target);
+				if (ret < 0)
+					return ret;
+			}
+
 			goto next;
+		}
 
 		off = i + insn[i].off + 1;
 		if (off < subprog_start || off >= subprog_end) {
@@ -855,10 +874,15 @@ static int check_subprogs(struct bpf_verifier_env *env)
 						      subprog_start);
 				if (ret < 0)
 					goto free_nodes;
+				cur_callee_list = &subprog[cur_subprog].callees;
 			}
 		}
 	}
 
+	ret = cgraph_check_recursive_unreachable(env, env->subprog_info);
+	if (ret < 0)
+		goto free_nodes;
+
 	ret = 0;
 
 free_nodes:
-- 
2.7.4

[RFC bpf-next 08/10] bpf: cfg: remove push_insn and check_cfg

[Jiong Wang]

As we have detected loop and unreachable insns based on domination
information and call graph, there is no need of check_cfg.

This patch removes check_cfg and it's associated push_insn.

state prune heuristic marking as moved to check_subprog.

Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
---
 kernel/bpf/verifier.c | 228 ++++----------------------------------------------
 1 file changed, 16 insertions(+), 212 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 12f5399..54f2fe3 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -735,6 +735,8 @@ enum reg_arg_type {
 	DST_OP_NO_MARK	/* same as above, check only, don't mark */
 };
 
+#define STATE_LIST_MARK ((struct bpf_verifier_state_list *)-1L)
+
 static int check_subprogs(struct bpf_verifier_env *env)
 {
 	int i, ret, subprog_start, subprog_end, off, cur_subprog = 0;
@@ -815,8 +817,14 @@ static int check_subprogs(struct bpf_verifier_env *env)
 							    target);
 				if (ret < 0)
 					return ret;
+
+				env->explored_states[target] = STATE_LIST_MARK;
+				env->explored_states[i] = STATE_LIST_MARK;
 			}
 
+			if (i + 1 < insn_cnt)
+				env->explored_states[i + 1] = STATE_LIST_MARK;
+
 			goto next;
 		}
 
@@ -836,6 +844,13 @@ static int check_subprogs(struct bpf_verifier_env *env)
 			if (ret < 0)
 				goto free_nodes;
 		}
+
+		if (BPF_OP(code) != BPF_JA) {
+			env->explored_states[i] = STATE_LIST_MARK;
+			env->explored_states[off] = STATE_LIST_MARK;
+		} else if (i + 1 < insn_cnt) {
+			env->explored_states[i + 1] = STATE_LIST_MARK;
+		}
 next:
 		if (i == subprog_end - 1) {
 			/* to avoid fall-through from one subprog into another
@@ -3951,217 +3966,6 @@ static int check_return_code(struct bpf_verifier_env *env)
 	return 0;
 }
 
-/* non-recursive DFS pseudo code
- * 1  procedure DFS-iterative(G,v):
- * 2      label v as discovered
- * 3      let S be a stack
- * 4      S.push(v)
- * 5      while S is not empty
- * 6            t <- S.pop()
- * 7            if t is what we're looking for:
- * 8                return t
- * 9            for all edges e in G.adjacentEdges(t) do
- * 10               if edge e is already labelled
- * 11                   continue with the next edge
- * 12               w <- G.adjacentVertex(t,e)
- * 13               if vertex w is not discovered and not explored
- * 14                   label e as tree-edge
- * 15                   label w as discovered
- * 16                   S.push(w)
- * 17                   continue at 5
- * 18               else if vertex w is discovered
- * 19                   label e as back-edge
- * 20               else
- * 21                   // vertex w is explored
- * 22                   label e as forward- or cross-edge
- * 23           label t as explored
- * 24           S.pop()
- *
- * convention:
- * 0x10 - discovered
- * 0x11 - discovered and fall-through edge labelled
- * 0x12 - discovered and fall-through and branch edges labelled
- * 0x20 - explored
- */
-
-enum {
-	DISCOVERED = 0x10,
-	EXPLORED = 0x20,
-	FALLTHROUGH = 1,
-	BRANCH = 2,
-};
-
-#define STATE_LIST_MARK ((struct bpf_verifier_state_list *) -1L)
-
-static int *insn_stack;	/* stack of insns to process */
-static int cur_stack;	/* current stack index */
-static int *insn_state;
-
-/* t, w, e - match pseudo-code above:
- * t - index of current instruction
- * w - next instruction
- * e - edge
- */
-static int push_insn(int t, int w, int e, struct bpf_verifier_env *env)
-{
-	if (e == FALLTHROUGH && insn_state[t] >= (DISCOVERED | FALLTHROUGH))
-		return 0;
-
-	if (e == BRANCH && insn_state[t] >= (DISCOVERED | BRANCH))
-		return 0;
-
-	if (w < 0 || w >= env->prog->len) {
-		verbose(env, "jump out of range from insn %d to %d\n", t, w);
-		return -EINVAL;
-	}
-
-	if (e == BRANCH)
-		/* mark branch target for state pruning */
-		env->explored_states[w] = STATE_LIST_MARK;
-
-	if (insn_state[w] == 0) {
-		/* tree-edge */
-		insn_state[t] = DISCOVERED | e;
-		insn_state[w] = DISCOVERED;
-		if (cur_stack >= env->prog->len)
-			return -E2BIG;
-		insn_stack[cur_stack++] = w;
-		return 1;
-	} else if ((insn_state[w] & 0xF0) == DISCOVERED) {
-		verbose(env, "back-edge from insn %d to %d\n", t, w);
-		return -EINVAL;
-	} else if (insn_state[w] == EXPLORED) {
-		/* forward- or cross-edge */
-		insn_state[t] = DISCOVERED | e;
-	} else {
-		verbose(env, "insn state internal bug\n");
-		return -EFAULT;
-	}
-	return 0;
-}
-
-/* non-recursive depth-first-search to detect loops in BPF program
- * loop == back-edge in directed graph
- */
-static int check_cfg(struct bpf_verifier_env *env)
-{
-	struct bpf_insn *insns = env->prog->insnsi;
-	int insn_cnt = env->prog->len;
-	int ret = 0;
-	int i, t;
-
-	ret = check_subprogs(env);
-	if (ret < 0)
-		return ret;
-
-	insn_state = kcalloc(insn_cnt, sizeof(int), GFP_KERNEL);
-	if (!insn_state)
-		return -ENOMEM;
-
-	insn_stack = kcalloc(insn_cnt, sizeof(int), GFP_KERNEL);
-	if (!insn_stack) {
-		kfree(insn_state);
-		return -ENOMEM;
-	}
-
-	insn_state[0] = DISCOVERED; /* mark 1st insn as discovered */
-	insn_stack[0] = 0; /* 0 is the first instruction */
-	cur_stack = 1;
-
-peek_stack:
-	if (cur_stack == 0)
-		goto check_state;
-	t = insn_stack[cur_stack - 1];
-
-	if (BPF_CLASS(insns[t].code) == BPF_JMP) {
-		u8 opcode = BPF_OP(insns[t].code);
-
-		if (opcode == BPF_EXIT) {
-			goto mark_explored;
-		} else if (opcode == BPF_CALL) {
-			ret = push_insn(t, t + 1, FALLTHROUGH, env);
-			if (ret == 1)
-				goto peek_stack;
-			else if (ret < 0)
-				goto err_free;
-			if (t + 1 < insn_cnt)
-				env->explored_states[t + 1] = STATE_LIST_MARK;
-			if (insns[t].src_reg == BPF_PSEUDO_CALL) {
-				env->explored_states[t] = STATE_LIST_MARK;
-				ret = push_insn(t, t + insns[t].imm + 1, BRANCH, env);
-				if (ret == 1)
-					goto peek_stack;
-				else if (ret < 0)
-					goto err_free;
-			}
-		} else if (opcode == BPF_JA) {
-			if (BPF_SRC(insns[t].code) != BPF_K) {
-				ret = -EINVAL;
-				goto err_free;
-			}
-			/* unconditional jump with single edge */
-			ret = push_insn(t, t + insns[t].off + 1,
-					FALLTHROUGH, env);
-			if (ret == 1)
-				goto peek_stack;
-			else if (ret < 0)
-				goto err_free;
-			/* tell verifier to check for equivalent states
-			 * after every call and jump
-			 */
-			if (t + 1 < insn_cnt)
-				env->explored_states[t + 1] = STATE_LIST_MARK;
-		} else {
-			/* conditional jump with two edges */
-			env->explored_states[t] = STATE_LIST_MARK;
-			ret = push_insn(t, t + 1, FALLTHROUGH, env);
-			if (ret == 1)
-				goto peek_stack;
-			else if (ret < 0)
-				goto err_free;
-
-			ret = push_insn(t, t + insns[t].off + 1, BRANCH, env);
-			if (ret == 1)
-				goto peek_stack;
-			else if (ret < 0)
-				goto err_free;
-		}
-	} else {
-		/* all other non-branch instructions with single
-		 * fall-through edge
-		 */
-		ret = push_insn(t, t + 1, FALLTHROUGH, env);
-		if (ret == 1)
-			goto peek_stack;
-		else if (ret < 0)
-			goto err_free;
-	}
-
-mark_explored:
-	insn_state[t] = EXPLORED;
-	if (cur_stack-- <= 0) {
-		verbose(env, "pop stack internal bug\n");
-		ret = -EFAULT;
-		goto err_free;
-	}
-	goto peek_stack;
-
-check_state:
-	for (i = 0; i < insn_cnt; i++) {
-		if (insn_state[i] != EXPLORED) {
-			verbose(env, "unreachable insn %d\n", i);
-			ret = -EINVAL;
-			goto err_free;
-		}
-	}
-	ret = 0; /* cfg looks good */
-
-err_free:
-	kfree(insn_state);
-	kfree(insn_stack);
-	return ret;
-}
-
 /* check %cur's range satisfies %old's */
 static bool range_within(struct bpf_reg_state *old,
 			 struct bpf_reg_state *cur)
@@ -5710,7 +5514,7 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr)
 
 	env->allow_ptr_leaks = capable(CAP_SYS_ADMIN);
 
-	ret = check_cfg(env);
+	ret = check_subprogs(env);
 	if (ret < 0)
 		goto skip_full_check;
 
-- 
2.7.4

[RFC bpf-next 09/10] bpf: cfg: reduce k*alloc/free call by using memory pool for allocating nodes

[Jiong Wang]

During building control flow graph, we need to build basic block nodes
and edge nodes etc. These nodes needs to allocated dynamically as we
don't have pre-scan pass to know how many nodes we need accurately.
It is better to manage their allocation using memory pool which could
reduce calling of *alloc/kfree functions and also could simplify freeing
nodes.

This patch:
  - implements a simple memory pool based node allocator.
    nodes need dynamic allocation migrated to this allocator.
  - estimate node numbers inside subprog detection pass, asking allocator
    to do an initial allocation of estimated size (aligned to 2K). The pool
    will grow later if space are not enough.
  - There is no support on returning memory back to the pool.

Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
---
 kernel/bpf/cfg.c      | 164 +++++++++++++++++++++++++++++++++++++-------------
 kernel/bpf/cfg.h      |  21 +++++--
 kernel/bpf/verifier.c |  39 +++++++++---
 3 files changed, 170 insertions(+), 54 deletions(-)

diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
index 174e3f0..1aeac49 100644
--- a/kernel/bpf/cfg.c
+++ b/kernel/bpf/cfg.c
@@ -82,7 +82,113 @@ struct dom_info {
 	u16 dfsnum;
 };
 
-int subprog_append_bb(struct list_head *bb_list, int head)
+struct node_pool {
+	struct list_head l;
+	void *data;
+	u32 size;
+	u32 used;
+};
+
+#define first_node_pool(pool_list)	\
+	list_first_entry(pool_list, struct node_pool, l)
+
+#define MEM_CHUNK_SIZE	(1024)
+
+static int cfg_node_allocator_grow(struct cfg_node_allocator *allocator,
+				   int min_grow_size)
+{
+	int s = min_grow_size;
+	struct node_pool *pool;
+	void *data;
+
+	s += sizeof(struct node_pool);
+	s = ALIGN(s, MEM_CHUNK_SIZE);
+	data = kzalloc(s, GFP_KERNEL);
+	if (!data)
+		return -ENOMEM;
+
+	pool = (struct node_pool *)data;
+	pool->data = pool + 1;
+	pool->size = s - sizeof(struct node_pool);
+	pool->used = 0;
+	allocator->cur_free_pool = pool;
+	list_add_tail(&pool->l, &allocator->pools);
+
+	return 0;
+}
+
+static void *cfg_node_alloc(struct cfg_node_allocator *allocator, int size)
+{
+	struct node_pool *pool = allocator->cur_free_pool;
+	void *p;
+
+	if (pool->used + size > pool->size) {
+		int ret = cfg_node_allocator_grow(allocator, size);
+
+		if (ret < 0)
+			return NULL;
+
+		pool = allocator->cur_free_pool;
+	}
+
+	p = pool->data + pool->used;
+	pool->used += size;
+
+	return p;
+}
+
+static struct bb_node *get_single_bb_nodes(struct cfg_node_allocator *allocator)
+{
+	int size = sizeof(struct bb_node);
+
+	return (struct bb_node *)cfg_node_alloc(allocator, size);
+}
+
+static struct edge_node *get_edge_nodes(struct cfg_node_allocator *allocator,
+					int num)
+{
+	int size = num * sizeof(struct edge_node);
+
+	return (struct edge_node *)cfg_node_alloc(allocator, size);
+}
+
+static struct cedge_node *
+get_single_cedge_node(struct cfg_node_allocator *allocator)
+{
+	int size = sizeof(struct cedge_node);
+
+	return (struct cedge_node *)cfg_node_alloc(allocator, size);
+}
+
+int cfg_node_allocator_init(struct cfg_node_allocator *allocator,
+			    int bb_num_esti, int cedge_num_esti)
+{
+	int s = bb_num_esti * sizeof(struct bb_node), ret;
+
+	s += 2 * bb_num_esti * sizeof(struct edge_node);
+	s += cedge_num_esti * sizeof(struct cedge_node);
+	INIT_LIST_HEAD(&allocator->pools);
+	ret = cfg_node_allocator_grow(allocator, s);
+	if (ret < 0)
+		return ret;
+
+	return 0;
+}
+
+void cfg_node_allocator_free(struct cfg_node_allocator *allocator)
+{
+	struct list_head *pools = &allocator->pools;
+	struct node_pool *pool, *tmp;
+
+	pool = first_node_pool(pools);
+	list_for_each_entry_safe_from(pool, tmp, pools, l) {
+		list_del(&pool->l);
+		kfree(pool);
+	}
+}
+
+int subprog_append_bb(struct cfg_node_allocator *allocator,
+		      struct list_head *bb_list, int head)
 {
 	struct bb_node *new_bb, *bb;
 
@@ -94,7 +200,7 @@ int subprog_append_bb(struct list_head *bb_list, int head)
 	}
 
 	bb = bb_prev(bb);
-	new_bb = kzalloc(sizeof(*new_bb), GFP_KERNEL);
+	new_bb = get_single_bb_nodes(allocator);
 	if (!new_bb)
 		return -ENOMEM;
 
@@ -106,9 +212,10 @@ int subprog_append_bb(struct list_head *bb_list, int head)
 	return 0;
 }
 
-int subprog_fini_bb(struct list_head *bb_list, int subprog_end)
+int subprog_fini_bb(struct cfg_node_allocator *allocator,
+		    struct list_head *bb_list, int subprog_end)
 {
-	struct bb_node *bb = kzalloc(sizeof(*bb), GFP_KERNEL);
+	struct bb_node *bb = get_single_bb_nodes(allocator);
 
 	if (!bb)
 		return -ENOMEM;
@@ -118,7 +225,7 @@ int subprog_fini_bb(struct list_head *bb_list, int subprog_end)
 	INIT_LIST_HEAD(&bb->e_succs);
 	list_add(&bb->l, bb_list);
 
-	bb = kzalloc(sizeof(*bb), GFP_KERNEL);
+	bb = get_single_bb_nodes(allocator);
 	if (!bb)
 		return -ENOMEM;
 	/* exit bb. */
@@ -130,12 +237,13 @@ int subprog_fini_bb(struct list_head *bb_list, int subprog_end)
 	return 0;
 }
 
-int subprog_init_bb(struct list_head *bb_list, int subprog_start)
+int subprog_init_bb(struct cfg_node_allocator *allocator,
+		    struct list_head *bb_list, int subprog_start)
 {
 	int ret;
 
 	INIT_LIST_HEAD(bb_list);
-	ret = subprog_append_bb(bb_list, subprog_start);
+	ret = subprog_append_bb(allocator, bb_list, subprog_start);
 	if (ret < 0)
 		return ret;
 
@@ -154,14 +262,15 @@ static struct bb_node *search_bb_with_head(struct list_head *bb_list, int head)
 	return NULL;
 }
 
-int subprog_add_bb_edges(struct bpf_insn *insns, struct list_head *bb_list)
+int subprog_add_bb_edges(struct cfg_node_allocator *allocator,
+			 struct bpf_insn *insns, struct list_head *bb_list)
 {
 	struct bb_node *bb, *exit_bb;
 	struct edge_node *edge;
 	int bb_num;
 
 	bb = entry_bb(bb_list);
-	edge = kcalloc(2, sizeof(*edge), GFP_KERNEL);
+	edge = get_edge_nodes(allocator, 2);
 	if (!edge)
 		return -ENOMEM;
 	edge->src = bb;
@@ -186,7 +295,7 @@ int subprog_add_bb_edges(struct bpf_insn *insns, struct list_head *bb_list)
 
 		bb->idx = bb_num++;
 
-		edge = kcalloc(2, sizeof(*edge), GFP_KERNEL);
+		edge = get_edge_nodes(allocator, 2);
 		if (!edge)
 			return -ENOMEM;
 		edge->src = bb;
@@ -222,7 +331,7 @@ int subprog_add_bb_edges(struct bpf_insn *insns, struct list_head *bb_list)
 			struct bb_node *tgt;
 
 			if (!edge) {
-				edge = kcalloc(2, sizeof(*edge), GFP_KERNEL);
+				edge = get_edge_nodes(allocator, 2);
 				if (!edge)
 					return -ENOMEM;
 				edge->src = bb;
@@ -753,6 +862,7 @@ int cgraph_check_recursive_unreachable(struct bpf_verifier_env *env,
 }
 
 int subprog_append_callee(struct bpf_verifier_env *env,
+			  struct cfg_node_allocator *allocator,
 			  struct list_head *callees_list,
 			  int caller_idx, int off)
 {
@@ -767,7 +877,7 @@ int subprog_append_callee(struct bpf_verifier_env *env,
 			return 0;
 	}
 
-	new_callee = kzalloc(sizeof(*new_callee), GFP_KERNEL);
+	new_callee = get_single_cedge_node(allocator);
 	if (!new_callee)
 		return -ENOMEM;
 
@@ -778,41 +888,11 @@ int subprog_append_callee(struct bpf_verifier_env *env,
 	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(struct bpf_subprog_info *subprog, int end_idx)
 {
 	int i = 0;
 
 	for (; i <= end_idx; i++) {
-		struct list_head *callees = &subprog[i].callees;
-		struct list_head *bbs = &subprog[i].bbs;
-		struct cedge_node *callee, *tmp_callee;
-		struct bb_node *bb, *tmp, *exit;
-
-		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);
-		}
-
-		list_for_each_entry_safe(callee, tmp_callee, callees, l) {
-			list_del(&callee->l);
-			kfree(callee);
-		}
-
 		if (subprog[i].dtree_avail)
 			kfree(subprog[i].dtree);
 	}
diff --git a/kernel/bpf/cfg.h b/kernel/bpf/cfg.h
index 577c22c..1868587 100644
--- a/kernel/bpf/cfg.h
+++ b/kernel/bpf/cfg.h
@@ -8,19 +8,32 @@
 #ifndef __BPF_CFG_H__
 #define __BPF_CFG_H__
 
+struct cfg_node_allocator {
+	struct list_head pools;
+	struct node_pool *cur_free_pool;
+};
+
 int add_subprog(struct bpf_verifier_env *env, int off);
+void cfg_node_allocator_free(struct cfg_node_allocator *allocator);
+int cfg_node_allocator_init(struct cfg_node_allocator *allocator,
+			    int bb_num_esti, int cedge_num_esti);
 int cgraph_check_recursive_unreachable(struct bpf_verifier_env *env,
 				       struct bpf_subprog_info *subprog);
 int find_subprog(struct bpf_verifier_env *env, int off);
-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_add_bb_edges(struct cfg_node_allocator *allocator,
+			 struct bpf_insn *insns, struct list_head *bb_list);
+int subprog_append_bb(struct cfg_node_allocator *allocator,
+		      struct list_head *bb_list, int head);
 int subprog_append_callee(struct bpf_verifier_env *env,
+			  struct cfg_node_allocator *allocator,
 			  struct list_head *bb_list, int caller_idx, int off);
 int subprog_build_dom_info(struct bpf_verifier_env *env,
 			   struct bpf_subprog_info *subprog);
-int subprog_fini_bb(struct list_head *bb_list, int subprog_end);
+int subprog_fini_bb(struct cfg_node_allocator *allocator,
+		    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);
+int subprog_init_bb(struct cfg_node_allocator *allocator,
+		    struct list_head *bb_list, int subprog_start);
 void subprog_free(struct bpf_subprog_info *subprog, int end_idx);
 
 #endif
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 54f2fe3..db4a3ca 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -743,7 +743,10 @@ static int check_subprogs(struct bpf_verifier_env *env)
 	struct bpf_subprog_info *subprog = env->subprog_info;
 	struct list_head *cur_bb_list, *cur_callee_list;
 	struct bpf_insn *insn = env->prog->insnsi;
+	int cedge_num_esti = 0, bb_num_esti = 3;
+	struct cfg_node_allocator allocator;
 	int insn_cnt = env->prog->len;
+	u8 code;
 
 	/* Add entry function. */
 	ret = add_subprog(env, 0);
@@ -752,8 +755,18 @@ static int check_subprogs(struct bpf_verifier_env *env)
 
 	/* determine subprog starts. The end is one before the next starts */
 	for (i = 0; i < insn_cnt; i++) {
-		if (insn[i].code != (BPF_JMP | BPF_CALL))
+		code = insn[i].code;
+		if (BPF_CLASS(code) != BPF_JMP)
+			continue;
+		if (BPF_OP(code) == BPF_EXIT) {
+			if (i + 1 < insn_cnt)
+				bb_num_esti++;
 			continue;
+		}
+		if (BPF_OP(code) != BPF_CALL) {
+			bb_num_esti += 2;
+			continue;
+		}
 		if (insn[i].src_reg != BPF_PSEUDO_CALL)
 			continue;
 		if (!env->allow_ptr_leaks) {
@@ -764,6 +777,7 @@ static int check_subprogs(struct bpf_verifier_env *env)
 			verbose(env, "function calls in offloaded programs are not supported yet\n");
 			return -EINVAL;
 		}
+		cedge_num_esti++;
 		ret = add_subprog(env, i + insn[i].imm + 1);
 		if (ret < 0)
 			return ret;
@@ -784,10 +798,14 @@ static int check_subprogs(struct bpf_verifier_env *env)
 		INIT_LIST_HEAD(&subprog[i].callees);
 	}
 
+	ret = cfg_node_allocator_init(&allocator, bb_num_esti,
+				      cedge_num_esti);
+	if (ret < 0)
+		return ret;
 	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);
+	ret = subprog_init_bb(&allocator, cur_bb_list, subprog_start);
 	if (ret < 0)
 		goto free_nodes;
 	cur_callee_list = &env->subprog_info[cur_subprog].callees;
@@ -800,7 +818,8 @@ static int check_subprogs(struct bpf_verifier_env *env)
 
 		if (BPF_OP(code) == BPF_EXIT) {
 			if (i + 1 < subprog_end) {
-				ret = subprog_append_bb(cur_bb_list, i + 1);
+				ret = subprog_append_bb(&allocator, cur_bb_list,
+							i + 1);
 				if (ret < 0)
 					goto free_nodes;
 			}
@@ -812,6 +831,7 @@ static int check_subprogs(struct bpf_verifier_env *env)
 				int target = i + insn[i].imm + 1;
 
 				ret = subprog_append_callee(env,
+							    &allocator,
 							    cur_callee_list,
 							    cur_subprog,
 							    target);
@@ -835,12 +855,12 @@ static int check_subprogs(struct bpf_verifier_env *env)
 			goto free_nodes;
 		}
 
-		ret = subprog_append_bb(cur_bb_list, off);
+		ret = subprog_append_bb(&allocator, cur_bb_list, off);
 		if (ret < 0)
 			goto free_nodes;
 
 		if (i + 1 < subprog_end) {
-			ret = subprog_append_bb(cur_bb_list, i + 1);
+			ret = subprog_append_bb(&allocator, cur_bb_list, i + 1);
 			if (ret < 0)
 				goto free_nodes;
 		}
@@ -864,10 +884,12 @@ static int check_subprogs(struct bpf_verifier_env *env)
 				goto free_nodes;
 			}
 
-			ret = subprog_fini_bb(cur_bb_list, subprog_end);
+			ret = subprog_fini_bb(&allocator, cur_bb_list,
+					      subprog_end);
 			if (ret < 0)
 				goto free_nodes;
-			ret = subprog_add_bb_edges(insn, cur_bb_list);
+			ret = subprog_add_bb_edges(&allocator, insn,
+						   cur_bb_list);
 			if (ret < 0)
 				goto free_nodes;
 			subprog[cur_subprog].bb_num = ret;
@@ -885,7 +907,7 @@ static int check_subprogs(struct bpf_verifier_env *env)
 			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,
+				ret = subprog_init_bb(&allocator, cur_bb_list,
 						      subprog_start);
 				if (ret < 0)
 					goto free_nodes;
@@ -901,6 +923,7 @@ static int check_subprogs(struct bpf_verifier_env *env)
 	ret = 0;
 
 free_nodes:
+	cfg_node_allocator_free(&allocator);
 	subprog_free(subprog, cur_subprog == env->subprog_cnt ?
 				cur_subprog - 1 : cur_subprog);
 	return ret;
-- 
2.7.4

[RFC bpf-next 10/10] bpf: cfg: reduce memory usage by using singly list + compat pointer

[Jiong Wang]

Because there are going to be quite a few nodes (bb, edge etc) for a
reasonable sized program, the size of cfg nodes matters.

The cfg traversal used at the moment are mostly via edge which contains
pointers to both src and dst basic block. The traversal is not via links
between basic blocks and edge nodes themselves, so link them with doubly
list_head is unnecessary, and is too heavy on 64-bit host as pointer will
take 8-bytes.

This patch reduce memory usage from two ways:
  1. use singly linked list to link basic block and edge nodes.
  2. introduce a compact pointer representation for pointers generated from
     memory pool. If a pointer is from pool, we could represent it using
     pool_base + pool_offset,

       struct cfg_node_link {
         u16 offset;
         s8 idx;
       };

     the compact pointer "cfg_node_link" will only take 3-bytes.
     the delink of the pointer will becomes:

     static void *cfg_node_delink(struct cfg_node_allocator *allocator,
                            struct cfg_node_link *link)
     {
       s8 idx = link->idx;

       if (idx == -1)
               return NULL;

       return allocator->base[idx] + link->offset;
     }

For example, basic blocks nodes changed from:

    struct bb_node {
       struct list_head l;
       struct list_head e_prevs;
       struct list_head e_succs;
       s16 head;
       u16 idx;
    };

into:

    struct bb_node {
	struct cfg_node_link link;
	struct cfg_node_link e_prevs;
	struct cfg_node_link e_succs;
	s16 head;
	u16 idx;
    };

We reduced node size from 52 to 16. We could further reduce node size to 14
if we reshuffle fields of link/e_prevs/e_succs to avoid alignment padding,
but that will with a cost of code readability.

>From benchmarks like test_xdp_noinline, this patch reduce peek memory usage
of new cfg infrastructure by more than 50%.

Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
---
 include/linux/bpf_verifier.h |   7 +-
 kernel/bpf/cfg.c             | 503 ++++++++++++++++++++++++-------------------
 kernel/bpf/cfg.h             |  23 +-
 kernel/bpf/verifier.c        |  33 ++-
 4 files changed, 312 insertions(+), 254 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 96337ba..c291461 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -176,8 +176,11 @@ 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 callees; /* callees list. */
-	struct list_head bbs; /* basic blocks list. */
+	void *callees; /* callees list. */
+	struct {
+		void *entry_bb; /* basic blocks list head. */
+		void *exit_bb; /* basic blocks list tail. */
+	} bbs;
 	u32 bb_num; /* total basic block num. */
 	unsigned long *dtree;
 	bool dtree_avail;
diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
index 1aeac49..bda63ab 100644
--- a/kernel/bpf/cfg.c
+++ b/kernel/bpf/cfg.c
@@ -13,54 +13,55 @@
 
 #include "cfg.h"
 
+/* The size of cfg nodes matters, therefore we try to avoid using doubly linked
+ * list and we try to use base + offset to address node, by this we only need
+ * to keep offset.
+ */
+struct cfg_node_link {
+	u16 offset;
+	s8 idx;
+};
+
+static void *cfg_node_delink(struct cfg_node_allocator *allocator,
+			     struct cfg_node_link *link)
+{
+	s8 idx = link->idx;
+
+	if (idx == -1)
+		return NULL;
+
+	return allocator->base[idx] + link->offset;
+}
+
 struct cedge_node {
-	struct list_head l;
+	struct cfg_node_link link;
 	u8 caller_idx;
 	u8 callee_idx;
 };
 
 struct edge_node {
-	struct list_head l;
+	struct cfg_node_link link;
 	struct bb_node *src;
 	struct bb_node *dst;
 };
 
-struct edge_iter {
-	struct list_head *list_head;
-	struct edge_node *edge;
+struct bb_node {
+	struct cfg_node_link link;
+	struct cfg_node_link e_prevs;
+	struct cfg_node_link e_succs;
+	s16 head;
+	u16 idx;
 };
 
-#define first_edge(e_list)	list_first_entry(e_list, struct edge_node, l)
-#define last_edge(e_list)	list_last_entry(e_list, struct edge_node, l)
-#define next_edge(e)		list_next_entry(e, l)
+#define entry_bb(bb_list)		(struct bb_node *)(*bb_list)
+#define exit_bb(bb_list)		(struct bb_node *)(*(bb_list + 1))
 
-static bool ei_end_p(struct edge_iter *ei)
+static struct bb_node *bb_next(struct cfg_node_allocator *allocator,
+			       struct bb_node *bb)
 {
-	return &ei->edge->l == ei->list_head;
+	return (struct bb_node *)cfg_node_delink(allocator, &bb->link);
 }
 
-static void ei_next(struct edge_iter *ei)
-{
-	struct edge_node *e = ei->edge;
-
-	ei->edge = next_edge(e);
-}
-
-struct bb_node {
-	struct list_head l;
-	struct list_head e_prevs;
-	struct list_head e_succs;
-	u16 head;
-	u16 idx;
-};
-
-#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)
-
 struct dom_info {
 	u16 *dfs_parent;
 	u16 *dfs_order;
@@ -82,9 +83,12 @@ struct dom_info {
 	u16 dfsnum;
 };
 
-struct node_pool {
-	struct list_head l;
-	void *data;
+struct mem_frag {
+	struct cfg_node_link link;
+	void *p;
+};
+
+struct pool_head {
 	u32 size;
 	u32 used;
 };
@@ -97,67 +101,103 @@ struct node_pool {
 static int cfg_node_allocator_grow(struct cfg_node_allocator *allocator,
 				   int min_grow_size)
 {
-	int s = min_grow_size;
-	struct node_pool *pool;
-	void *data;
+	int s = min_grow_size, pool_cnt = allocator->pool_cnt;
+	struct pool_head *pool;
 
-	s += sizeof(struct node_pool);
+	if (pool_cnt >= MAX_POOL_NUM)
+		return -E2BIG;
+
+	s += sizeof(struct pool_head);
 	s = ALIGN(s, MEM_CHUNK_SIZE);
-	data = kzalloc(s, GFP_KERNEL);
-	if (!data)
+	if (s > U16_MAX)
+		return -E2BIG;
+
+	pool = kzalloc(s, GFP_KERNEL);
+	if (!pool)
 		return -ENOMEM;
 
-	pool = (struct node_pool *)data;
-	pool->data = pool + 1;
-	pool->size = s - sizeof(struct node_pool);
-	pool->used = 0;
-	allocator->cur_free_pool = pool;
-	list_add_tail(&pool->l, &allocator->pools);
+	allocator->base[pool_cnt] = pool;
+	pool->size = s;
+	pool->used = sizeof(struct pool_head);
+	allocator->pool_cnt++;
 
 	return 0;
 }
 
-static void *cfg_node_alloc(struct cfg_node_allocator *allocator, int size)
+static int cfg_node_alloc(struct cfg_node_allocator *allocator,
+			  struct mem_frag *frag, int size)
 {
-	struct node_pool *pool = allocator->cur_free_pool;
+	int pool_idx = allocator->pool_cnt - 1;
+	struct pool_head *pool;
 	void *p;
 
+	pool = allocator->base[pool_idx];
 	if (pool->used + size > pool->size) {
 		int ret = cfg_node_allocator_grow(allocator, size);
 
 		if (ret < 0)
-			return NULL;
+			return ret;
 
-		pool = allocator->cur_free_pool;
+		pool_idx++;
+		pool = allocator->base[pool_idx];
 	}
 
-	p = pool->data + pool->used;
+	p = (void *)pool + pool->used;
+	frag->p = p;
+	frag->link.idx = pool_idx;
+	frag->link.offset = pool->used;
 	pool->used += size;
 
-	return p;
+	return 0;
 }
 
-static struct bb_node *get_single_bb_nodes(struct cfg_node_allocator *allocator)
+static int get_link_nodes(struct cfg_node_allocator *allocator,
+			  struct mem_frag *frag, int num, int elem_size)
 {
-	int size = sizeof(struct bb_node);
+	int i, ret;
+	struct cfg_node_link *link;
 
-	return (struct bb_node *)cfg_node_alloc(allocator, size);
+	ret = cfg_node_alloc(allocator, frag, num * elem_size);
+	if (ret < 0)
+		return ret;
+
+	for (i = 0; i < num; i++) {
+		link = frag->p + i * elem_size;
+		link->idx = -1;
+	}
+
+	return 0;
 }
 
-static struct edge_node *get_edge_nodes(struct cfg_node_allocator *allocator,
-					int num)
+static int get_bb_nodes(struct cfg_node_allocator *allocator,
+			struct mem_frag *frag, int num)
 {
-	int size = num * sizeof(struct edge_node);
+	struct bb_node *bb;
+	int i, ret;
+
+	ret = get_link_nodes(allocator, frag, num, sizeof(struct bb_node));
+	if (ret < 0)
+		return ret;
+
+	bb = frag->p;
+	for (i = 0; i < num; i++) {
+		bb[i].e_prevs.idx = -1;
+		bb[i].e_succs.idx = -1;
+	}
 
-	return (struct edge_node *)cfg_node_alloc(allocator, size);
+	return 0;
 }
 
-static struct cedge_node *
-get_single_cedge_node(struct cfg_node_allocator *allocator)
+static int get_edge_nodes(struct cfg_node_allocator *allocator,
+			  struct mem_frag *frag, int num)
 {
-	int size = sizeof(struct cedge_node);
+	return get_link_nodes(allocator, frag, num, sizeof(struct edge_node));
+}
 
-	return (struct cedge_node *)cfg_node_alloc(allocator, size);
+static int get_single_cedge_node(struct cfg_node_allocator *allocator,
+				 struct mem_frag *frag)
+{
+	return get_link_nodes(allocator, frag, 1, sizeof(struct cedge_node));
 }
 
 int cfg_node_allocator_init(struct cfg_node_allocator *allocator,
@@ -167,7 +207,8 @@ int cfg_node_allocator_init(struct cfg_node_allocator *allocator,
 
 	s += 2 * bb_num_esti * sizeof(struct edge_node);
 	s += cedge_num_esti * sizeof(struct cedge_node);
-	INIT_LIST_HEAD(&allocator->pools);
+
+	allocator->pool_cnt = 0;
 	ret = cfg_node_allocator_grow(allocator, s);
 	if (ret < 0)
 		return ret;
@@ -177,127 +218,123 @@ int cfg_node_allocator_init(struct cfg_node_allocator *allocator,
 
 void cfg_node_allocator_free(struct cfg_node_allocator *allocator)
 {
-	struct list_head *pools = &allocator->pools;
-	struct node_pool *pool, *tmp;
+	int i, cnt = allocator->pool_cnt;
 
-	pool = first_node_pool(pools);
-	list_for_each_entry_safe_from(pool, tmp, pools, l) {
-		list_del(&pool->l);
-		kfree(pool);
-	}
+	for (i = 0; i < cnt; i++)
+		kfree(allocator->base[i]);
 }
 
-int subprog_append_bb(struct cfg_node_allocator *allocator,
-		      struct list_head *bb_list, int head)
+int subprog_append_bb(struct cfg_node_allocator *allocator, void **bb_list,
+		      int head)
 {
-	struct bb_node *new_bb, *bb;
+	struct bb_node *cur = entry_bb(bb_list);
+	struct bb_node *prev = cur;
+	struct mem_frag frag;
+	int ret;
 
-	list_for_each_entry(bb, bb_list, l) {
-		if (bb->head == head)
+	while (cur) {
+		if (cur->head == head)
 			return 0;
-		else if (bb->head > head)
+		else if (cur->head > head)
 			break;
-	}
+		prev = cur;
+		cur = cfg_node_delink(allocator, &cur->link);
+	};
 
-	bb = bb_prev(bb);
-	new_bb = get_single_bb_nodes(allocator);
-	if (!new_bb)
-		return -ENOMEM;
+	ret = get_bb_nodes(allocator, &frag, 1);
+	if (ret < 0)
+		return ret;
 
-	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);
+	cur = frag.p;
+	cur->head = head;
+	cur->link = prev->link;
+	prev->link = frag.link;
 
 	return 0;
 }
 
-int subprog_fini_bb(struct cfg_node_allocator *allocator,
-		    struct list_head *bb_list, int subprog_end)
+int subprog_init_bb(struct cfg_node_allocator *allocator, void **bb_list,
+		    int subprog_start, int subprog_end)
 {
-	struct bb_node *bb = get_single_bb_nodes(allocator);
-
-	if (!bb)
-		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 = get_single_bb_nodes(allocator);
-	if (!bb)
-		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;
-}
+	struct bb_node **list_head = (struct bb_node **)bb_list;
+	struct bb_node **list_tail = (struct bb_node **)(bb_list + 1);
+	struct bb_node *entry_bb, *first_bb, *exit_bb;
+	int ret, s = sizeof(struct bb_node);
+	struct mem_frag frag;
 
-int subprog_init_bb(struct cfg_node_allocator *allocator,
-		    struct list_head *bb_list, int subprog_start)
-{
-	int ret;
-
-	INIT_LIST_HEAD(bb_list);
-	ret = subprog_append_bb(allocator, bb_list, subprog_start);
+	ret = get_bb_nodes(allocator, &frag, 3);
 	if (ret < 0)
 		return ret;
 
+	entry_bb = frag.p;
+	*list_head = entry_bb;
+	entry_bb->head = -1;
+	first_bb = frag.p + s;
+	first_bb->head = subprog_start;
+	exit_bb = frag.p + 2 * s;
+	exit_bb->head = subprog_end;
+	entry_bb->link.idx = frag.link.idx;
+	entry_bb->link.offset = frag.link.offset + s;
+	first_bb->link.idx = frag.link.idx;
+	first_bb->link.offset = frag.link.offset + 2 * s;
+	*list_tail = exit_bb;
+
 	return 0;
 }
 
-static struct bb_node *search_bb_with_head(struct list_head *bb_list, int head)
+static struct bb_node *search_bb_with_head(struct cfg_node_allocator *allocator,
+					   void **bb_list, int head)
 {
-	struct bb_node *bb;
+	struct bb_node *cur = entry_bb(bb_list);
 
-	list_for_each_entry(bb, bb_list, l) {
-		if (bb->head == head)
-			return bb;
-	}
+	while (cur) {
+		if (cur->head == head)
+			return cur;
+
+		cur = cfg_node_delink(allocator, &cur->link);
+	};
 
 	return NULL;
 }
 
 int subprog_add_bb_edges(struct cfg_node_allocator *allocator,
-			 struct bpf_insn *insns, struct list_head *bb_list)
+			 struct bpf_insn *insns, void **bb_list)
 {
-	struct bb_node *bb, *exit_bb;
+	struct bb_node *bb = entry_bb(bb_list), *exit_bb;
 	struct edge_node *edge;
-	int bb_num;
+	struct mem_frag frag;
+	int ret, bb_num;
 
-	bb = entry_bb(bb_list);
-	edge = get_edge_nodes(allocator, 2);
-	if (!edge)
-		return -ENOMEM;
+	ret = get_edge_nodes(allocator, &frag, 2);
+	if (ret < 0)
+		return ret;
+	edge = frag.p;
 	edge->src = bb;
-	edge->dst = bb_next(bb);
-	list_add_tail(&edge->l, &bb->e_succs);
+	edge->dst = bb_next(allocator, bb);
+	bb->e_succs = frag.link;
 	edge[1].src = edge->src;
 	edge[1].dst = edge->dst;
-	list_add_tail(&edge[1].l, &edge[1].dst->e_prevs);
+	edge->dst->e_prevs = frag.link;
 	bb->idx = -1;
 
 	exit_bb = exit_bb(bb_list);
 	exit_bb->idx = -2;
-	bb = bb_next(bb);
+	bb = edge->dst;
 	bb_num = 0;
-	list_for_each_entry_from(bb, &exit_bb->l, l) {
+	while (bb && bb != exit_bb) {
+		struct bb_node *next_bb = bb_next(allocator, bb);
 		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;
 
 		bb->idx = bb_num++;
 
-		edge = get_edge_nodes(allocator, 2);
-		if (!edge)
-			return -ENOMEM;
+		ret = get_edge_nodes(allocator, &frag, 2);
+		if (ret < 0)
+			return ret;
+		edge = frag.p;
 		edge->src = bb;
 		edge[1].src = bb;
 
@@ -322,8 +359,11 @@ int subprog_add_bb_edges(struct cfg_node_allocator *allocator,
 				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->link = bb->e_succs;
+			bb->e_succs = frag.link;
+			frag.link.offset += sizeof(struct edge_node);
+			edge[1].link = next_bb->e_prevs;
+			next_bb->e_prevs = frag.link;
 			edge = NULL;
 		}
 
@@ -331,23 +371,29 @@ int subprog_add_bb_edges(struct cfg_node_allocator *allocator,
 			struct bb_node *tgt;
 
 			if (!edge) {
-				edge = get_edge_nodes(allocator, 2);
-				if (!edge)
-					return -ENOMEM;
+				ret = get_edge_nodes(allocator, &frag, 2);
+				if (ret < 0)
+					return ret;
+				edge = frag.p;
 				edge->src = bb;
 				edge[1].src = bb;
 			}
 
-			tgt = search_bb_with_head(bb_list,
+			tgt = search_bb_with_head(allocator, 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);
+			edge->link = bb->e_succs;
+			bb->e_succs = frag.link;
+			frag.link.offset += sizeof(struct edge_node);
+			edge[1].link = tgt->e_prevs;
+			tgt->e_prevs = frag.link;
 		}
+
+		bb = bb_next(allocator, bb);
 	}
 
 	return bb_num + 2;
@@ -451,13 +497,13 @@ static void link(struct dom_info *di, unsigned int v, unsigned int w)
 	}
 }
 
-static void calc_idoms(struct bpf_subprog_info *subprog, struct dom_info *di,
-		       bool reverse)
+static void
+calc_idoms(struct cfg_node_allocator *allocator,
+	   struct bpf_subprog_info *subprog, struct dom_info *di, bool reverse)
 {
 	u16 entry_bb_fake_idx = subprog->bb_num - 2, idx, w, k, par;
-	struct list_head *bb_list = &subprog->bbs;
+	void **bb_list = (void **)&subprog->bbs;
 	struct bb_node *entry_bb;
-	struct edge_iter ei;
 
 	if (reverse)
 		entry_bb = exit_bb(bb_list);
@@ -472,24 +518,21 @@ static void calc_idoms(struct bpf_subprog_info *subprog, struct dom_info *di,
 		par = di->dfs_parent[idx];
 		k = idx;
 
-		if (reverse) {
-			ei.edge = first_edge(&bb->e_succs);
-			ei.list_head = &bb->e_succs;
-		} else {
-			ei.edge = first_edge(&bb->e_prevs);
-			ei.list_head = &bb->e_prevs;
-		}
+		if (reverse)
+			e = cfg_node_delink(allocator, &bb->e_succs);
+		else
+			e = cfg_node_delink(allocator, &bb->e_prevs);
 
-		while (!ei_end_p(&ei)) {
+		while (e) {
 			struct bb_node *b;
 			u16 k1;
 
-			e = ei.edge;
 			if (reverse)
 				b = e->dst;
 			else
 				b = e->src;
-			ei_next(&ei);
+
+			e = cfg_node_delink(allocator, &e->link);
 
 			if (b == entry_bb)
 				k1 = di->dfs_order[entry_bb_fake_idx];
@@ -525,20 +568,22 @@ static void calc_idoms(struct bpf_subprog_info *subprog, struct dom_info *di,
 }
 
 static int
-calc_dfs_tree(struct bpf_verifier_env *env, struct bpf_subprog_info *subprog,
-	      struct dom_info *di, bool reverse)
+calc_dfs_tree(struct bpf_verifier_env *env,
+	      struct cfg_node_allocator *allocator,
+	      struct bpf_subprog_info *subprog, struct dom_info *di,
+	      bool reverse)
 {
 	u16 bb_num = subprog->bb_num, sp = 0, idx, parent_idx, i;
-	struct list_head *bb_list = &subprog->bbs;
+	void **bb_list = (void **)&subprog->bbs;
 	u16 entry_bb_fake_idx = bb_num - 2;
 	struct bb_node *entry_bb, *exit_bb;
-	struct edge_iter ei, *stack;
-	struct edge_node *e;
+	struct edge_node **stack, *e;
 	bool *visited;
 
 	di->dfs_order[entry_bb_fake_idx] = di->dfsnum;
 
-	stack = kmalloc_array(bb_num - 1, sizeof(struct edge_iter), GFP_KERNEL);
+	stack = kmalloc_array(bb_num - 1, sizeof(struct edge_node *),
+			      GFP_KERNEL);
 	if (!stack)
 		return -ENOMEM;
 
@@ -550,29 +595,26 @@ calc_dfs_tree(struct bpf_verifier_env *env, struct bpf_subprog_info *subprog,
 		entry_bb = exit_bb(bb_list);
 		exit_bb = entry_bb(bb_list);
 		di->dfs_to_bb[di->dfsnum++] = exit_bb;
-		ei.edge = first_edge(&entry_bb->e_prevs);
-		ei.list_head = &entry_bb->e_prevs;
+		e = cfg_node_delink(allocator, &entry_bb->e_prevs);
 	} else {
 		entry_bb = entry_bb(bb_list);
 		exit_bb = exit_bb(bb_list);
 		di->dfs_to_bb[di->dfsnum++] = entry_bb;
-		ei.edge = first_edge(&entry_bb->e_succs);
-		ei.list_head = &entry_bb->e_succs;
+		e = cfg_node_delink(allocator, &entry_bb->e_succs);
 	}
 
 	while (1) {
 		struct bb_node *bb_dst, *bb_src;
 
-		while (!ei_end_p(&ei)) {
-			e = ei.edge;
-
+		while (e) {
 			if (reverse) {
 				bb_dst = e->src;
 				if (bb_dst != exit_bb)
 					visited[bb_dst->idx] = true;
 				if (bb_dst == exit_bb ||
 				    di->dfs_order[bb_dst->idx]) {
-					ei_next(&ei);
+					e = cfg_node_delink(allocator,
+							    &e->link);
 					continue;
 				}
 				bb_src = e->dst;
@@ -582,7 +624,8 @@ calc_dfs_tree(struct bpf_verifier_env *env, struct bpf_subprog_info *subprog,
 					visited[bb_dst->idx] = true;
 				if (bb_dst == exit_bb ||
 				    di->dfs_order[bb_dst->idx]) {
-					ei_next(&ei);
+					e = cfg_node_delink(allocator,
+							    &e->link);
 					continue;
 				}
 				bb_src = e->src;
@@ -598,21 +641,20 @@ calc_dfs_tree(struct bpf_verifier_env *env, struct bpf_subprog_info *subprog,
 			di->dfs_to_bb[idx] = bb_dst;
 			di->dfs_parent[idx] = parent_idx;
 
-			stack[sp++] = ei;
-			if (reverse) {
-				ei.edge = first_edge(&bb_dst->e_prevs);
-				ei.list_head = &bb_dst->e_prevs;
-			} else {
-				ei.edge = first_edge(&bb_dst->e_succs);
-				ei.list_head = &bb_dst->e_succs;
-			}
+			stack[sp++] = e;
+			if (reverse)
+				e = cfg_node_delink(allocator,
+						    &bb_dst->e_prevs);
+			else
+				e = cfg_node_delink(allocator,
+						    &bb_dst->e_succs);
 		}
 
 		if (!sp)
 			break;
 
-		ei = stack[--sp];
-		ei_next(&ei);
+		e = stack[--sp];
+		e = cfg_node_delink(allocator, &e->link);
 	}
 
 	kfree(stack);
@@ -679,6 +721,7 @@ static int idoms_to_doms(struct bpf_subprog_info *subprog, struct dom_info *di)
  */
 
 int subprog_build_dom_info(struct bpf_verifier_env *env,
+			   struct cfg_node_allocator *allocator,
 			   struct bpf_subprog_info *subprog)
 {
 	struct dom_info di;
@@ -688,11 +731,11 @@ int subprog_build_dom_info(struct bpf_verifier_env *env,
 	if (ret < 0)
 		goto free_dominfo;
 
-	ret = calc_dfs_tree(env, subprog, &di, false);
+	ret = calc_dfs_tree(env, allocator, subprog, &di, false);
 	if (ret < 0)
 		goto free_dominfo;
 
-	calc_idoms(subprog, &di, false);
+	calc_idoms(allocator, subprog, &di, false);
 	ret = idoms_to_doms(subprog, &di);
 	if (ret < 0)
 		goto free_dominfo;
@@ -706,25 +749,33 @@ int subprog_build_dom_info(struct bpf_verifier_env *env,
 	return ret;
 }
 
-bool subprog_has_loop(struct bpf_subprog_info *subprog)
+bool subprog_has_loop(struct cfg_node_allocator *allocator,
+		      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 bb_node *bb, *entry_bb, *exit_bb;
+	void **bb_list = (void **)&subprog->bbs;
 	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) {
+	exit_bb = exit_bb(bb_list);
+	bb = bb_next(allocator, entry_bb);
+	while (bb && bb != exit_bb) {
+		e = cfg_node_delink(allocator, &bb->e_prevs);
+		while (e) {
 			struct bb_node *latch = e->src;
 
 			if (latch != entry_bb &&
 			    test_bit(bb->idx,
 				     subprog->dtree + latch->idx * lane_len))
 				return true;
+
+			e = cfg_node_delink(allocator, &e->link);
 		}
 
+		bb = bb_next(allocator, bb);
+	}
+
 	return false;
 }
 
@@ -768,37 +819,34 @@ int add_subprog(struct bpf_verifier_env *env, int off)
 }
 
 struct callee_iter {
-	struct list_head *list_head;
+	struct cedge_node *head;
 	struct cedge_node *callee;
 };
 
-#define first_callee(c_list)	list_first_entry(c_list, struct cedge_node, l)
-#define next_callee(c)		list_next_entry(c, l)
-
 static bool ci_end_p(struct callee_iter *ci)
 {
-	return &ci->callee->l == ci->list_head;
+	return !ci->callee;
 }
 
-static void ci_next(struct callee_iter *ci)
+static void ci_next(struct cfg_node_allocator *allocator,
+		    struct callee_iter *ci)
 {
 	struct cedge_node *c = ci->callee;
 
-	ci->callee = next_callee(c);
+	ci->callee = cfg_node_delink(allocator, &c->link);
 }
 
 #define EXPLORING	1
 #define EXPLORED	2
 int cgraph_check_recursive_unreachable(struct bpf_verifier_env *env,
+				       struct cfg_node_allocator *allocator,
 				       struct bpf_subprog_info *subprog)
 {
-	struct callee_iter *stack;
+	int sp = 0, idx = 0, ret, *status;
+	struct callee_iter *stack, ci;
 	struct cedge_node *callee;
-	int sp = 0, idx = 0, ret;
-	struct callee_iter ci;
-	int *status;
 
-	stack = kmalloc_array(128, sizeof(struct callee_iter), GFP_KERNEL);
+	stack = kmalloc_array(64, sizeof(struct callee_iter), GFP_KERNEL);
 	if (!stack)
 		return -ENOMEM;
 	status = kcalloc(env->subprog_cnt, sizeof(int), GFP_KERNEL);
@@ -806,8 +854,8 @@ int cgraph_check_recursive_unreachable(struct bpf_verifier_env *env,
 		kfree(stack);
 		return -ENOMEM;
 	}
-	ci.callee = first_callee(&subprog->callees);
-	ci.list_head = &subprog->callees;
+	ci.head = subprog->callees;
+	ci.callee = subprog->callees;
 	status[0] = EXPLORING;
 
 	while (1) {
@@ -822,20 +870,19 @@ int cgraph_check_recursive_unreachable(struct bpf_verifier_env *env,
 
 			status[idx] = EXPLORING;
 
-			if (sp == 127) {
+			if (sp == 64) {
 				bpf_verifier_log_write(env, "cgraph - call frame too deep\n");
 				ret = -EINVAL;
 				goto err_free;
 			}
 
 			stack[sp++] = ci;
-			ci.callee = first_callee(&subprog[idx].callees);
-			ci.list_head = &subprog[idx].callees;
+			ci.head = subprog[idx].callees;
+			ci.callee = subprog[idx].callees;
 		}
 
-		if (!list_empty(ci.list_head))
-			status[first_callee(ci.list_head)->caller_idx] =
-				EXPLORED;
+		if (ci.head)
+			status[ci.head->caller_idx] = EXPLORED;
 		else
 			/* leaf func. */
 			status[idx] = EXPLORED;
@@ -844,7 +891,7 @@ int cgraph_check_recursive_unreachable(struct bpf_verifier_env *env,
 			break;
 
 		ci = stack[--sp];
-		ci_next(&ci);
+		ci_next(allocator, &ci);
 	}
 
 	for (idx = 0; idx < env->subprog_cnt; idx++)
@@ -863,27 +910,37 @@ int cgraph_check_recursive_unreachable(struct bpf_verifier_env *env,
 
 int subprog_append_callee(struct bpf_verifier_env *env,
 			  struct cfg_node_allocator *allocator,
-			  struct list_head *callees_list,
-			  int caller_idx, int off)
+			  void **callees_list, int caller_idx, int off)
 {
-	int callee_idx = find_subprog(env, off);
+	int callee_idx = find_subprog(env, off), ret;
 	struct cedge_node *new_callee, *callee;
+	struct mem_frag frag;
 
 	if (callee_idx < 0)
 		return callee_idx;
 
-	list_for_each_entry(callee, callees_list, l) {
+	callee = (struct cedge_node *)*callees_list;
+	while (callee) {
 		if (callee->callee_idx == callee_idx)
 			return 0;
+
+		callee = cfg_node_delink(allocator, &callee->link);
 	}
 
-	new_callee = get_single_cedge_node(allocator);
-	if (!new_callee)
-		return -ENOMEM;
+	ret = get_single_cedge_node(allocator, &frag);
+	if (ret < 0)
+		return ret;
 
+	new_callee = frag.p;
 	new_callee->caller_idx = caller_idx;
 	new_callee->callee_idx = callee_idx;
-	list_add_tail(&new_callee->l, callees_list);
+	callee = (struct cedge_node *)*callees_list;
+	if (!callee) {
+		*callees_list = new_callee;
+	} else {
+		new_callee->link = callee->link;
+		callee->link = frag.link;
+	}
 
 	return 0;
 }
diff --git a/kernel/bpf/cfg.h b/kernel/bpf/cfg.h
index 1868587..cb833bd 100644
--- a/kernel/bpf/cfg.h
+++ b/kernel/bpf/cfg.h
@@ -8,9 +8,11 @@
 #ifndef __BPF_CFG_H__
 #define __BPF_CFG_H__
 
+#define MAX_POOL_NUM	32
+
 struct cfg_node_allocator {
-	struct list_head pools;
-	struct node_pool *cur_free_pool;
+	void *base[MAX_POOL_NUM];
+	u8 pool_cnt;
 };
 
 int add_subprog(struct bpf_verifier_env *env, int off);
@@ -18,22 +20,23 @@ void cfg_node_allocator_free(struct cfg_node_allocator *allocator);
 int cfg_node_allocator_init(struct cfg_node_allocator *allocator,
 			    int bb_num_esti, int cedge_num_esti);
 int cgraph_check_recursive_unreachable(struct bpf_verifier_env *env,
+				       struct cfg_node_allocator *allocator,
 				       struct bpf_subprog_info *subprog);
 int find_subprog(struct bpf_verifier_env *env, int off);
 int subprog_add_bb_edges(struct cfg_node_allocator *allocator,
-			 struct bpf_insn *insns, struct list_head *bb_list);
+			 struct bpf_insn *insns, void **bb_list);
 int subprog_append_bb(struct cfg_node_allocator *allocator,
-		      struct list_head *bb_list, int head);
+		      void **bb_list, int head);
 int subprog_append_callee(struct bpf_verifier_env *env,
 			  struct cfg_node_allocator *allocator,
-			  struct list_head *bb_list, int caller_idx, int off);
+			  void **callees, int caller_idx, int off);
 int subprog_build_dom_info(struct bpf_verifier_env *env,
+			   struct cfg_node_allocator *allocator,
 			   struct bpf_subprog_info *subprog);
-int subprog_fini_bb(struct cfg_node_allocator *allocator,
-		    struct list_head *bb_list, int subprog_end);
-bool subprog_has_loop(struct bpf_subprog_info *subprog);
-int subprog_init_bb(struct cfg_node_allocator *allocator,
-		    struct list_head *bb_list, int subprog_start);
+bool subprog_has_loop(struct cfg_node_allocator *allocator,
+		      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);
 
 #endif
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index db4a3ca..fad0975 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -741,9 +741,9 @@ static int check_subprogs(struct bpf_verifier_env *env)
 {
 	int i, ret, subprog_start, subprog_end, off, cur_subprog = 0;
 	struct bpf_subprog_info *subprog = env->subprog_info;
-	struct list_head *cur_bb_list, *cur_callee_list;
 	struct bpf_insn *insn = env->prog->insnsi;
 	int cedge_num_esti = 0, bb_num_esti = 3;
+	void **cur_bb_list, **cur_callee_list;
 	struct cfg_node_allocator allocator;
 	int insn_cnt = env->prog->len;
 	u8 code;
@@ -788,24 +788,19 @@ static int check_subprogs(struct bpf_verifier_env *env)
 	 */
 	subprog[env->subprog_cnt].start = insn_cnt;
 
-	for (i = 0; i < env->subprog_cnt; i++) {
+	for (i = 0; i < env->subprog_cnt; i++)
 		if (env->log.level > 1)
 			verbose(env, "func#%d @%d\n", i, subprog[i].start);
 
-		/* Don't init callees inside add_subprog which will sort the
-		 * array which breaks list link.
-		 */
-		INIT_LIST_HEAD(&subprog[i].callees);
-	}
-
 	ret = cfg_node_allocator_init(&allocator, bb_num_esti,
 				      cedge_num_esti);
 	if (ret < 0)
 		return ret;
 	subprog_start = subprog[cur_subprog].start;
 	subprog_end = subprog[cur_subprog + 1].start;
-	cur_bb_list = &subprog[cur_subprog].bbs;
-	ret = subprog_init_bb(&allocator, cur_bb_list, subprog_start);
+	cur_bb_list = (void **)&subprog[cur_subprog].bbs;
+	ret = subprog_init_bb(&allocator, cur_bb_list, subprog_start,
+			      subprog_end);
 	if (ret < 0)
 		goto free_nodes;
 	cur_callee_list = &env->subprog_info[cur_subprog].callees;
@@ -884,20 +879,17 @@ static int check_subprogs(struct bpf_verifier_env *env)
 				goto free_nodes;
 			}
 
-			ret = subprog_fini_bb(&allocator, cur_bb_list,
-					      subprog_end);
-			if (ret < 0)
-				goto free_nodes;
 			ret = subprog_add_bb_edges(&allocator, insn,
 						   cur_bb_list);
 			if (ret < 0)
 				goto free_nodes;
 			subprog[cur_subprog].bb_num = ret;
-			ret = subprog_build_dom_info(env,
+			ret = subprog_build_dom_info(env, &allocator,
 						     &subprog[cur_subprog]);
 			if (ret < 0)
 				goto free_nodes;
-			if (subprog_has_loop(&subprog[cur_subprog])) {
+			if (subprog_has_loop(&allocator,
+					     &subprog[cur_subprog])) {
 				verbose(env, "cfg - loop detected");
 				ret = -EINVAL;
 				goto free_nodes;
@@ -906,9 +898,11 @@ static int check_subprogs(struct bpf_verifier_env *env)
 			cur_subprog++;
 			if (cur_subprog < env->subprog_cnt) {
 				subprog_end = subprog[cur_subprog + 1].start;
-				cur_bb_list = &subprog[cur_subprog].bbs;
+				cur_bb_list =
+					(void **)&subprog[cur_subprog].bbs;
 				ret = subprog_init_bb(&allocator, cur_bb_list,
-						      subprog_start);
+						      subprog_start,
+						      subprog_end);
 				if (ret < 0)
 					goto free_nodes;
 				cur_callee_list = &subprog[cur_subprog].callees;
@@ -916,7 +910,8 @@ static int check_subprogs(struct bpf_verifier_env *env)
 		}
 	}
 
-	ret = cgraph_check_recursive_unreachable(env, env->subprog_info);
+	ret = cgraph_check_recursive_unreachable(env, &allocator,
+						 env->subprog_info);
 	if (ret < 0)
 		goto free_nodes;
 
-- 
2.7.4

Re: [RFC bpf-next 00/10] initial control flow support for eBPF verifier

[Jiong Wang]

On 07/05/2018 11:22, Jiong Wang wrote:
> execution time
> ===
> test_l4lb_noinline:
>    existing check_subprog/check_cfg: ~55000 ns
>    new infrastructure: ~135000 ns
>
> test_xdp_noinline:
>    existing check_subprog/check_cfg: ~52000 ns
>    new infrastructure: ~120000 ns

Intel(R) Xeon(R) CPU E5-2630 v4 @ 2.20GHz

Regards,
Jiong

Re: [RFC bpf-next 00/10] initial control flow support for eBPF verifier

[David Miller]

From: Jiong Wang <jiong.wang@netronome.com>
Date: Mon,  7 May 2018 06:22:36 -0400

> This infrastructure comes with some memory usage and execution time cost.
> Memory pool based allocation is used to avoid frequently calling of
> kmalloc/free. Singly linked list and compact pointer are used to reduce
> various cfg node size.

The memory and execution time costs are unfortunate, but we will
certainly need a real control flow graph in the verifier whether we
like it or not.

Re: [RFC bpf-next 04/10] bpf: cfg: detect loop use domination information

[John Fastabend]

On 05/07/2018 03:22 AM, Jiong Wang wrote:
> If one bb is dominating its predecessor, then there is loop.
> 
> Signed-off-by: Jiong Wang <jiong.wang@netronome.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;
> +}
> +

Because we are using this to guard against loops we need to detect
all loops not just reducible loops. And because (assuming my understanding
is correct) Tarjan's algorithm will only detect all loops when the
graph is reducible we need additional tests.

There are a couple options to fix this with varying levels of complexity.
Because I'm using this to build loop info structures to find induction
variables and show termination. After the loop structures are built we
could search for any back-edges not in valid loops. This would be similar
to the existing back-edge detection code but with an extra check to
allow edges that have been validated. I would need to check that this
doesn't have any escapes before actually proposing it though.

The other method would be to properly test for reducibility using one of
the algorithms for this. I think the most intuitive is to remove back-edges
and test the graph is acyclic. This would be run before the dom tree is
built. This is IMO what we should do, it seems the most "correct" way to
do this.

The most complex would be to handle irreducible programs using some of the
more complex methods. I really don't think this is necessary but in theory
at least we could use something like Havlak-Tarjan algorithm and allow
some programs with irreducible loops. This is likely overkill especially
in a first iteration.

Here is a sample that fails without this series, using original back-edge
detection, but is allowed with this patch,

SEC("classifier_tc_mark")
int _tc_mark(struct __sk_buff *ctx)
{
        void *data      = (void *)(unsigned long)ctx->data;
        void *data_end  = (void *)(unsigned long)ctx->data_end;
        void *data_meta = (void *)(unsigned long)ctx->data_meta;
        struct meta_info *meta = data_meta;
        volatile int mark = ctx->mark;

        mark += 1;

        if (meta + 1 > data) {
B:
                mark += 2;

                if (mark < ctx->mark * 3)
                        goto C;
        } else if (meta < data) {
C:
                mark += 1;
                if (mark < 1000)
                        goto  B;
        }

        return TC_ACT_OK;
}

A more concise example could be made but I just hacked on one of the
sample programs. This generates the CFG as follows (I have a patch
on top of your stack to print the CFG and DOM tables)

CFG:  65535[-1,-1] -> 0[0,9]  0[0,9] -> 3[20,20]  0[0,9] -> 1[10,18]  1[10,18] -> 4[21,28]  1[10,18] -> 2[19,19]  2[19,19] -> 5[29,30]  3[20,20] -> 5[29,30]  3[20,20] -> 4[21,28]  4[21,28] -> 1[10,18]  4[21,28] -> 5[29,30]  5[29,30] -> 65534[31,65534] 
DOM:
 1  0  0  0  0  0 
 1  1  0  0  0  0 
 1  1  1  0  0  0 
 1  0  0  1  0  0 
 1  0  0  0  1  0 
 1  0  0  0  0  1 


Here we have the loop 1[10,18]->4[21,28] and the back-edge 4[21,28]->1[10,18].
The notation is #idx[head_insn,tail_insn]. The above can then be imported
into dot notation and graphed if needed.

Jiong, please verify this analysis is correct.

Thanks,
John

Re: [RFC bpf-next 04/10] bpf: cfg: detect loop use domination information

[Jiong Wang]

On 10/05/2018 19:17, John Fastabend wrote:
> On 05/07/2018 03:22 AM, Jiong Wang wrote:
>> If one bb is dominating its predecessor, then there is loop.
>>
>> Signed-off-by: Jiong Wang <jiong.wang@netronome.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;
>> +}
>> +
> Because we are using this to guard against loops we need to detect
> all loops not just reducible loops. And because (assuming my understanding
> is correct) Tarjan's algorithm will only detect all loops when the
> graph is reducible we need additional tests.

Hi John,

Yes, the current DOM based loop detection can't detect irreducible loop.

And I feel both the first and second approaches you listed below are good,
might worth implementing both and measure which one is with less overhead.

I could give a try on approach 2.  The alg given by Eric Stoltz might be a
good choice (https://compilers.iecc.com/comparch/article/94-01-053). We
have dom info now, so could do another DFS, and see if the head of one
back-edge doesn't dom the tail that there is multiple entries to the loop.

I guess the first approach is with less overhead as there is no existing
DFS pass to reuse after dom build that we need a new pass for approach 2.

Regards,
Jiong

>
> There are a couple options to fix this with varying levels of complexity.
> Because I'm using this to build loop info structures to find induction
> variables and show termination. After the loop structures are built we
> could search for any back-edges not in valid loops. This would be similar
> to the existing back-edge detection code but with an extra check to
> allow edges that have been validated. I would need to check that this
> doesn't have any escapes before actually proposing it though.
>
> The other method would be to properly test for reducibility using one of
> the algorithms for this. I think the most intuitive is to remove back-edges
> and test the graph is acyclic. This would be run before the dom tree is
> built. This is IMO what we should do, it seems the most "correct" way to
> do this.
>
> The most complex would be to handle irreducible programs using some of the
> more complex methods. I really don't think this is necessary but in theory
> at least we could use something like Havlak-Tarjan algorithm and allow
> some programs with irreducible loops. This is likely overkill especially
> in a first iteration.
>
> Here is a sample that fails without this series, using original back-edge
> detection, but is allowed with this patch,
>
> SEC("classifier_tc_mark")
> int _tc_mark(struct __sk_buff *ctx)
> {
>          void *data      = (void *)(unsigned long)ctx->data;
>          void *data_end  = (void *)(unsigned long)ctx->data_end;
>          void *data_meta = (void *)(unsigned long)ctx->data_meta;
>          struct meta_info *meta = data_meta;
>          volatile int mark = ctx->mark;
>
>          mark += 1;
>
>          if (meta + 1 > data) {
> B:
>                  mark += 2;
>
>                  if (mark < ctx->mark * 3)
>                          goto C;
>          } else if (meta < data) {
> C:
>                  mark += 1;
>                  if (mark < 1000)
>                          goto  B;
>          }
>
>          return TC_ACT_OK;
> }
>
> A more concise example could be made but I just hacked on one of the
> sample programs. This generates the CFG as follows (I have a patch
> on top of your stack to print the CFG and DOM tables)
>
> CFG:  65535[-1,-1] -> 0[0,9]  0[0,9] -> 3[20,20]  0[0,9] -> 1[10,18]  1[10,18] -> 4[21,28]  1[10,18] -> 2[19,19]  2[19,19] -> 5[29,30]  3[20,20] -> 5[29,30]  3[20,20] -> 4[21,28]  4[21,28] -> 1[10,18]  4[21,28] -> 5[29,30]  5[29,30] -> 65534[31,65534]
> DOM:
>   1  0  0  0  0  0
>   1  1  0  0  0  0
>   1  1  1  0  0  0
>   1  0  0  1  0  0
>   1  0  0  0  1  0
>   1  0  0  0  0  1
>
>
> Here we have the loop 1[10,18]->4[21,28] and the back-edge 4[21,28]->1[10,18].
> The notation is #idx[head_insn,tail_insn]. The above can then be imported
> into dot notation and graphed if needed.
>
> Jiong, please verify this analysis is correct.
>
> Thanks,
> John
>