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