From mboxrd@z Thu Jan 1 00:00:00 1970 From: John Fastabend Subject: [RFC PATCH 04/16] bpf: cfg: detect loop use domination information Date: Fri, 01 Jun 2018 02:32:38 -0700 Message-ID: <20180601093238.15353.12809.stgit@john-Precision-Tower-5810> References: <20180601092646.15353.28269.stgit@john-Precision-Tower-5810> Mime-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit Cc: netdev@vger.kernel.org To: alexei.starovoitov@gmail.com, daniel@iogearbox.net, davem@davemloft.net Return-path: Received: from [184.63.162.180] ([184.63.162.180]:35674 "EHLO john-Precision-Tower-5810" rhost-flags-FAIL-FAIL-OK-FAIL) by vger.kernel.org with ESMTP id S1751533AbeFAJcn (ORCPT ); Fri, 1 Jun 2018 05:32:43 -0400 In-Reply-To: <20180601092646.15353.28269.stgit@john-Precision-Tower-5810> Sender: netdev-owner@vger.kernel.org List-ID: From: Jiong Wang If one bb is dominating its predecessor, then there is loop. Signed-off-by: Jiong Wang Signed-off-by: John Fastabend --- 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_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 eccaee4..c349c45 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -904,6 +904,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) {