From mboxrd@z Thu Jan 1 00:00:00 1970 From: Jiong Wang Subject: [RFC bpf-next 04/10] bpf: cfg: detect loop use domination information Date: Mon, 7 May 2018 06:22:40 -0400 Message-ID: <1525688567-19618-5-git-send-email-jiong.wang@netronome.com> References: <1525688567-19618-1-git-send-email-jiong.wang@netronome.com> Cc: john.fastabend@gmail.com, netdev@vger.kernel.org, oss-drivers@netronome.com, Jiong Wang To: alexei.starovoitov@gmail.com, daniel@iogearbox.net Return-path: Received: from mail-wm0-f65.google.com ([74.125.82.65]:52298 "EHLO mail-wm0-f65.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752042AbeEGKXI (ORCPT ); Mon, 7 May 2018 06:23:08 -0400 Received: by mail-wm0-f65.google.com with SMTP id w194so12492753wmf.2 for ; Mon, 07 May 2018 03:23:08 -0700 (PDT) In-Reply-To: <1525688567-19618-1-git-send-email-jiong.wang@netronome.com> Sender: netdev-owner@vger.kernel.org List-ID: If one bb is dominating its predecessor, then there is loop. Signed-off-by: Jiong Wang --- 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