From: John Fastabend <john.fastabend@gmail.com>
To: alexei.starovoitov@gmail.com, daniel@iogearbox.net, davem@davemloft.net
Cc: netdev@vger.kernel.org
Subject: [RFC PATCH 05/16] bpf: cfg: detect unreachable basic blocks
Date: Fri, 01 Jun 2018 02:32:43 -0700 [thread overview]
Message-ID: <20180601093243.15353.83087.stgit@john-Precision-Tower-5810> (raw)
In-Reply-To: <20180601092646.15353.28269.stgit@john-Precision-Tower-5810>
From: Jiong Wang <jiong.wang@netronome.com>
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>
Signed-off-by: John Fastabend <john.fastabend@gmail.com>
---
kernel/bpf/cfg.c | 19 ++++++++++++++-----
kernel/bpf/cfg.h | 3 ++-
kernel/bpf/verifier.c | 3 ++-
3 files changed, 18 insertions(+), 7 deletions(-)
diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
index 90692e4..2f0ac00 100644
--- a/kernel/bpf/cfg.c
+++ b/kernel/bpf/cfg.c
@@ -407,10 +407,11 @@ 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;
@@ -490,6 +491,13 @@ 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 (!di->dfs_order[i]) {
+ bpf_verifier_log_write(env, "cfg - unreachable insn\n");
+ return -EINVAL;
+ }
+ }
+
return 0;
}
@@ -541,7 +549,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 +559,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 c349c45..29797d2 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -904,7 +904,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])) {
next prev parent reply other threads:[~2018-06-01 9:32 UTC|newest]
Thread overview: 17+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-06-01 9:32 [RFC PATCH 00/16] bpf, bounded loop support work in progress John Fastabend
2018-06-01 9:32 ` [RFC PATCH 01/16] bpf: cfg: partition basic blocks for each subprog John Fastabend
2018-06-01 9:32 ` [RFC PATCH 02/16] bpf: cfg: add edges between basic blocks to form CFG John Fastabend
2018-06-01 9:32 ` [RFC PATCH 03/16] bpf: cfg: build domination tree using Tarjan algorithm John Fastabend
2018-06-01 9:32 ` [RFC PATCH 04/16] bpf: cfg: detect loop use domination information John Fastabend
2018-06-01 9:32 ` John Fastabend [this message]
2018-06-01 9:32 ` [RFC PATCH 06/16] bpf: cfg: move find_subprog/add_subprog to cfg.c John Fastabend
2018-06-01 9:32 ` [RFC PATCH 07/16] bpf: cfg: build call graph and detect unreachable/recursive call John Fastabend
2018-06-01 9:32 ` [RFC PATCH 08/16] bpf: cfg: remove push_insn and check_cfg John Fastabend
2018-06-01 9:33 ` [RFC PATCH 09/16] bpf: cfg: reduce k*alloc/free call by using memory pool for allocating nodes John Fastabend
2018-06-01 9:33 ` [RFC PATCH 10/16] bpf: cfg: reduce memory usage by using singly list + compat pointer John Fastabend
2018-06-01 9:33 ` [RFC PATCH 11/16] bpf: cfg: detect irreducible loop using Eric Stoltz algorithm John Fastabend
2018-06-01 9:33 ` [RFC PATCH 12/16] bpf: cfg: pretty print CFG and DOM John Fastabend
2018-06-01 9:33 ` [RFC PATCH 13/16] bpf: verifier, can ptr range be calculated with scalar ALU op John Fastabend
2018-06-01 9:33 ` [RFC PATCH 14/16] bpf: verifier, add initial support to allow bounded loops John Fastabend
2018-06-01 9:33 ` [RFC PATCH 15/16] bpf: verifier, simple loop examples John Fastabend
2018-06-01 9:33 ` [RFC PATCH 16/16] bpf: tools: dbg patch to turn on debugging and add primitive examples John Fastabend
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20180601093243.15353.83087.stgit@john-Precision-Tower-5810 \
--to=john.fastabend@gmail.com \
--cc=alexei.starovoitov@gmail.com \
--cc=daniel@iogearbox.net \
--cc=davem@davemloft.net \
--cc=netdev@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox