From patchwork Sat Dec 29 03:09:12 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 1019286 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=netronome.com Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=netronome-com.20150623.gappssmtp.com header.i=@netronome-com.20150623.gappssmtp.com header.b="Rg04LEDL"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 43RT8W2WyKz9s3q for ; Sat, 29 Dec 2018 14:10:03 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730070AbeL2DJq (ORCPT ); Fri, 28 Dec 2018 22:09:46 -0500 Received: from mail-qk1-f196.google.com ([209.85.222.196]:38926 "EHLO mail-qk1-f196.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728574AbeL2DJp (ORCPT ); Fri, 28 Dec 2018 22:09:45 -0500 Received: by mail-qk1-f196.google.com with SMTP id q70so13453647qkh.6 for ; Fri, 28 Dec 2018 19:09:44 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=netronome-com.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=YXfYLv4wO9VWtJO1deLy3wHhS0P8juZmzpEE5ZK5tjE=; b=Rg04LEDLtTtfIEGEhlU6shzjbv2w9urG4i5T23HTzaOK5+1qEI3Y8HJY6klPWcuZmw xJbac8E3RNOYHfX8/uwnNqW/suVN49foK5vmbreCucq/M2x1lx+/Icz6WjU+FJK2C9dZ 0aiDKs+Y+bTfem+cyOZ+lIsAjV+5ANTpl0rAfp0WL38z2v+X4PzXEW3wZ0Sr8rAy2vyU 24Knw9hr7+R9fgB2h9lvk+v+28hGhyeasqZJ/pcFThWOQ+T7C1v3m9yzX2VWOTQxGfAB e7ido3RwU3UwBLDywb2jbVqqwMG5H6nw4BGbpbHdFUIbq5KZTuUocq9gunHXzz5yJgcz PKZg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=YXfYLv4wO9VWtJO1deLy3wHhS0P8juZmzpEE5ZK5tjE=; b=pRuV+LuDp8j7+gS6POPEwhifbK3mSX3NaRckbYYY8D4ynXBQddadHAvuxDl9JY5ZQD 0kj3m/2goMqQbXalg4zTvVac7rmgMFX8BdhPyQJT9zGKQ6qzgbEVsKOU5vqWGsZAJ61t Jv4zp+fSOlxS5pJZU7pZrPjarARxsr4hCPPucL1zk96766MDUhDaHJSDGm2j4jJF3C3i am2dKxO74+nOgpWzFj+FBg/0+TSXjnpEu0c+nZ7mwFtG94Wo4sPO9q7d0ZYHGuvjd8oE /7OIudIWhHEtbuZQ+IlsJVxS55d1DcwLe7h9SvaqR+0IRasgry5LYm6UeRV9IvTbEM4t sBIw== X-Gm-Message-State: AJcUukfLvYGItmqaJVvq/G8CruizCnXa472O64nn+1CJVqkbcN3e8FPn KUPGgzv43v9PVLKaafTvgNQZqg== X-Google-Smtp-Source: ALg8bN6wPNfvoXepGNILo9yA36ctF1Z9nGRZirWsLRLpN5e3EqrdBRm0zGPzAdOtCVYjLYc65eHkSw== X-Received: by 2002:a37:86c5:: with SMTP id i188mr27633550qkd.81.1546052984004; Fri, 28 Dec 2018 19:09:44 -0800 (PST) Received: from jkicinski-Precision-T1700.netronome.com ([66.60.152.14]) by smtp.gmail.com with ESMTPSA id i26sm14508170qkg.12.2018.12.28.19.09.42 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 28 Dec 2018 19:09:43 -0800 (PST) From: Jakub Kicinski To: alexei.starovoitov@gmail.com, daniel@iogearbox.net Cc: yhs@fb.com, netdev@vger.kernel.org, oss-drivers@netronome.com, Jakub Kicinski Subject: [RFC bpf-next v3 01/12] bpf: change parameters of call/branch offset adjustment Date: Fri, 28 Dec 2018 19:09:12 -0800 Message-Id: <20181229030923.4804-2-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.19.2 In-Reply-To: <20181229030923.4804-1-jakub.kicinski@netronome.com> References: <20181229030923.4804-1-jakub.kicinski@netronome.com> MIME-Version: 1.0 Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org In preparation for code removal change parameters to branch and call adjustment functions to be more universal. The current parameters assume we are patching a single instruction with a longer set. A diagram may help reading the change, this is for the patch single case, patching instruction 1 with a replacement of 4: ____ 0 |____| 1 |____| <-- pos ^ 2 | | <-- end old ^ | 3 | | | delta | len 4 |____| | | (patch region) 5 | | <-- end new v v 6 |____| end_old = pos + 1 end_new = pos + delta + 1 If we are before the patch region - curr variable and the target are fully in old coordinates (hence comparing against end_old). If we are after the region curr is in new coordinates (hence the comparison to end_new) but target is in mixed coordinates, so we just check if it falls before end_new, and if so it needs the adjustment. Note that we will not fix up branches which land in removed region in case of removal, which should be okay, as we are only going to remove dead code. Signed-off-by: Jakub Kicinski --- kernel/bpf/core.c | 40 +++++++++++++++++++++------------------- 1 file changed, 21 insertions(+), 19 deletions(-) diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c index 38de580abcc2..a40057b2c556 100644 --- a/kernel/bpf/core.c +++ b/kernel/bpf/core.c @@ -306,15 +306,16 @@ int bpf_prog_calc_tag(struct bpf_prog *fp) return 0; } -static int bpf_adj_delta_to_imm(struct bpf_insn *insn, u32 pos, u32 delta, - u32 curr, const bool probe_pass) +static int bpf_adj_delta_to_imm(struct bpf_insn *insn, u32 pos, s32 end_old, + s32 end_new, u32 curr, const bool probe_pass) { const s64 imm_min = S32_MIN, imm_max = S32_MAX; + s32 delta = end_new - end_old; s64 imm = insn->imm; - if (curr < pos && curr + imm + 1 > pos) + if (curr < pos && curr + imm + 1 >= end_old) imm += delta; - else if (curr > pos + delta && curr + imm + 1 <= pos + delta) + else if (curr >= end_new && curr + imm + 1 < end_new) imm -= delta; if (imm < imm_min || imm > imm_max) return -ERANGE; @@ -323,15 +324,16 @@ static int bpf_adj_delta_to_imm(struct bpf_insn *insn, u32 pos, u32 delta, return 0; } -static int bpf_adj_delta_to_off(struct bpf_insn *insn, u32 pos, u32 delta, - u32 curr, const bool probe_pass) +static int bpf_adj_delta_to_off(struct bpf_insn *insn, u32 pos, s32 end_old, + s32 end_new, u32 curr, const bool probe_pass) { const s32 off_min = S16_MIN, off_max = S16_MAX; + s32 delta = end_new - end_old; s32 off = insn->off; - if (curr < pos && curr + off + 1 > pos) + if (curr < pos && curr + off + 1 >= end_old) off += delta; - else if (curr > pos + delta && curr + off + 1 <= pos + delta) + else if (curr >= end_new && curr + off + 1 < end_new) off -= delta; if (off < off_min || off > off_max) return -ERANGE; @@ -340,10 +342,10 @@ static int bpf_adj_delta_to_off(struct bpf_insn *insn, u32 pos, u32 delta, return 0; } -static int bpf_adj_branches(struct bpf_prog *prog, u32 pos, u32 delta, - const bool probe_pass) +static int bpf_adj_branches(struct bpf_prog *prog, u32 pos, s32 end_old, + s32 end_new, const bool probe_pass) { - u32 i, insn_cnt = prog->len + (probe_pass ? delta : 0); + u32 i, insn_cnt = prog->len + (probe_pass ? end_new - end_old : 0); struct bpf_insn *insn = prog->insnsi; int ret = 0; @@ -355,8 +357,8 @@ static int bpf_adj_branches(struct bpf_prog *prog, u32 pos, u32 delta, * do any other adjustments. Therefore skip the patchlet. */ if (probe_pass && i == pos) { - i += delta + 1; - insn++; + i = end_new; + insn = prog->insnsi + end_old; } code = insn->code; if (BPF_CLASS(code) != BPF_JMP || @@ -366,11 +368,11 @@ static int bpf_adj_branches(struct bpf_prog *prog, u32 pos, u32 delta, if (BPF_OP(code) == BPF_CALL) { if (insn->src_reg != BPF_PSEUDO_CALL) continue; - ret = bpf_adj_delta_to_imm(insn, pos, delta, i, - probe_pass); + ret = bpf_adj_delta_to_imm(insn, pos, end_old, + end_new, i, probe_pass); } else { - ret = bpf_adj_delta_to_off(insn, pos, delta, i, - probe_pass); + ret = bpf_adj_delta_to_off(insn, pos, end_old, + end_new, i, probe_pass); } if (ret) break; @@ -420,7 +422,7 @@ struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off, * we afterwards may not fail anymore. */ if (insn_adj_cnt > cnt_max && - bpf_adj_branches(prog, off, insn_delta, true)) + bpf_adj_branches(prog, off, off + 1, off + len, true)) return NULL; /* Several new instructions need to be inserted. Make room @@ -452,7 +454,7 @@ struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off, * the ship has sailed to reverse to the original state. An * overflow cannot happen at this point. */ - BUG_ON(bpf_adj_branches(prog_adj, off, insn_delta, false)); + BUG_ON(bpf_adj_branches(prog_adj, off, off + 1, off + len, false)); bpf_adj_linfo(prog_adj, off, insn_delta); From patchwork Sat Dec 29 03:09:13 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 1019287 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=netronome.com Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=netronome-com.20150623.gappssmtp.com header.i=@netronome-com.20150623.gappssmtp.com header.b="QTYl6l78"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 43RT8X0s8cz9s3l for ; Sat, 29 Dec 2018 14:10:04 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730075AbeL2DJr (ORCPT ); Fri, 28 Dec 2018 22:09:47 -0500 Received: from mail-qt1-f194.google.com ([209.85.160.194]:40348 "EHLO mail-qt1-f194.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730064AbeL2DJq (ORCPT ); Fri, 28 Dec 2018 22:09:46 -0500 Received: by mail-qt1-f194.google.com with SMTP id k12so25052212qtf.7 for ; Fri, 28 Dec 2018 19:09:45 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=netronome-com.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=KlHv0MYf6PVoc0fve+JklP0jSJiChO5vXMsgY5CUigk=; b=QTYl6l78zgkT2m5yf3YUFTLFQmkAG7dhWoGGLB0IeXRL1a8Avv5/w35B/Vke13zj/R lIeeH09dGUzH9RLnW+PIGnJAQQy2u44B7EexfexXmmI0JNiODT5jPXw0SBcYj0D1DW32 LoJbemvaVw6F771jNY+/02+Mh4unScNLTSBpitfkVmdkWgnQU7YeCbYtRRtBtXvIvi3S I6IbvMRwGc5yLtScrspNtdIY6EAr1wErj+xUzQy7sAUBEYVHBBUHkaIa9XbgMG6FHuRa AEb8itOw1LkfbyAZP86jJAL1r6U09w2y5g0pgsOnIUtk+XYyBvrIyvtWl40iE/X4bwCR LNNw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=KlHv0MYf6PVoc0fve+JklP0jSJiChO5vXMsgY5CUigk=; b=mxKa1BVHq4T/IlO56js4N00f1xTzKKKgutAuYLvXC+ZPPUojJ2A8qcpsd9JUogSZUQ 0h58UNmn+NO1JJLGO5o69hjhEmk7cYSzKZ0MuOAyjVAsodj4ValeE9dY006ONd3IsNtB 38N4ai42GCN+AVrNRYPTyj4lUs62FUHO7UGTGw3QiSA+Wveh+MkbdUnXPOZAWSDLw5P7 0thWpMmibD0GqpXYslwIvp+/F5TMMazYZRUWwYDxdfpOL9jSNy2TKx9EhUTTtOpqwr2E rtf4TAPIe1Qg84PorpLNIfWFX2GwSryBwM/y9ozMjSiLCZmtYQyu+Ilqh9H/24OA1F6z 98hg== X-Gm-Message-State: AJcUukeFvGDZf4zUanrxWjXQG6riYGRv/WozOKNRfrLUP8HOLlFfnO1D Z12DsXOwo7/7SJVax81yo4Jk+w== X-Google-Smtp-Source: AFSGD/Vh+VFga3COary0Niqq0WMk5+5tHK/UaCSkvkZ6mCufxq58bB9yXXBFYrM74u6CI0LKLNjjGQ== X-Received: by 2002:ac8:d86:: with SMTP id s6mr27565334qti.324.1546052985438; Fri, 28 Dec 2018 19:09:45 -0800 (PST) Received: from jkicinski-Precision-T1700.netronome.com ([66.60.152.14]) by smtp.gmail.com with ESMTPSA id i26sm14508170qkg.12.2018.12.28.19.09.44 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 28 Dec 2018 19:09:44 -0800 (PST) From: Jakub Kicinski To: alexei.starovoitov@gmail.com, daniel@iogearbox.net Cc: yhs@fb.com, netdev@vger.kernel.org, oss-drivers@netronome.com, Jakub Kicinski Subject: [RFC bpf-next v3 02/12] bpf: verifier: hard wire branches to dead code Date: Fri, 28 Dec 2018 19:09:13 -0800 Message-Id: <20181229030923.4804-3-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.19.2 In-Reply-To: <20181229030923.4804-1-jakub.kicinski@netronome.com> References: <20181229030923.4804-1-jakub.kicinski@netronome.com> MIME-Version: 1.0 Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org Loading programs with dead code becomes more and more common, as people begin to patch constants at load time. Turn conditional jumps to unconditional ones, to avoid potential branch misprediction penalty. This optimization is enabled for privileged users only. For branches which just fall through we could just mark them as not seen and have dead code removal take care of them, but that seems less clean. v0.2: - don't call capable(CAP_SYS_ADMIN) twice (Jiong). Signed-off-by: Jakub Kicinski --- kernel/bpf/verifier.c | 45 +++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 43 insertions(+), 2 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 71d86e3024ae..30e2cd399b4a 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -6259,6 +6259,40 @@ static void sanitize_dead_code(struct bpf_verifier_env *env) } } +static bool insn_is_cond_jump(u8 code) +{ + u8 op; + + if (BPF_CLASS(code) != BPF_JMP) + return false; + + op = BPF_OP(code); + return op != BPF_JA && op != BPF_EXIT && op != BPF_CALL; +} + +static void opt_hard_wire_dead_code_branches(struct bpf_verifier_env *env) +{ + struct bpf_insn_aux_data *aux_data = env->insn_aux_data; + struct bpf_insn ja = BPF_JMP_IMM(BPF_JA, 0, 0, 0); + struct bpf_insn *insn = env->prog->insnsi; + const int insn_cnt = env->prog->len; + int i; + + for (i = 0; i < insn_cnt; i++, insn++) { + if (!insn_is_cond_jump(insn->code)) + continue; + + if (!aux_data[i + 1].seen) + ja.off = insn->off; + else if (!aux_data[i + 1 + insn->off].seen) + ja.off = 0; + else + continue; + + memcpy(insn, &ja, sizeof(ja)); + } +} + /* convert load instructions that access fields of a context type into a * sequence of instructions that access fields of the underlying structure: * struct __sk_buff -> struct sk_buff @@ -6899,6 +6933,7 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, struct bpf_verifier_env *env; struct bpf_verifier_log *log; int ret = -EINVAL; + bool is_priv; /* no program is valid */ if (ARRAY_SIZE(bpf_verifier_ops) == 0) @@ -6945,6 +6980,9 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, if (attr->prog_flags & BPF_F_ANY_ALIGNMENT) env->strict_alignment = false; + is_priv = capable(CAP_SYS_ADMIN); + env->allow_ptr_leaks = is_priv; + ret = replace_map_fd_with_map_ptr(env); if (ret < 0) goto skip_full_check; @@ -6962,8 +7000,6 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, if (!env->explored_states) goto skip_full_check; - env->allow_ptr_leaks = capable(CAP_SYS_ADMIN); - ret = check_subprogs(env); if (ret < 0) goto skip_full_check; @@ -6993,6 +7029,11 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, ret = check_max_stack_depth(env); /* instruction rewrites happen after this point */ + if (is_priv) { + if (ret == 0) + opt_hard_wire_dead_code_branches(env); + } + if (ret == 0) sanitize_dead_code(env); From patchwork Sat Dec 29 03:09:14 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 1019288 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=netronome.com Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=netronome-com.20150623.gappssmtp.com header.i=@netronome-com.20150623.gappssmtp.com header.b="io4cg/cD"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 43RT8X5lkXz9s3q for ; Sat, 29 Dec 2018 14:10:04 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730081AbeL2DJt (ORCPT ); Fri, 28 Dec 2018 22:09:49 -0500 Received: from mail-qt1-f193.google.com ([209.85.160.193]:34304 "EHLO mail-qt1-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730064AbeL2DJs (ORCPT ); Fri, 28 Dec 2018 22:09:48 -0500 Received: by mail-qt1-f193.google.com with SMTP id r14so25111572qtp.1 for ; Fri, 28 Dec 2018 19:09:47 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=netronome-com.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=OKAb4ip1nSdsL9VXy78UH5qAUWRjOMuFVQkTNRI/PaQ=; b=io4cg/cDiZ80KclLN3eH7qyJapWrwV+iXKYhQ+XG9s0dbqp3t5fTYJapcvCgJNpn9B Hj2Nmc9edMbyw4G7u69/rqxuvIu4I05twX3/V1BQKMEcdGLw1Q3zU/feHxGCxbnrSWsL V/YKtNs6tXGXZB1s5T55JjAGl7pfqCLD1jiGguBQhM2FnOpdUYkrXJQScHc/9M5BCjKC SJXheYZZbAPRiV/aDPk94a1bV2K+eYoCVp1gT3UXJDa67h7tOhNdDu17ScXgY3BiSsEo OHUGmznfsRCag1BuLsT/FsT4M2zz8HiTPalZsIyWU4tWzEvTAEVpAaY9OrtIy3mAm/YH Dc2A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=OKAb4ip1nSdsL9VXy78UH5qAUWRjOMuFVQkTNRI/PaQ=; b=K5efg4xaqUoTFUM8SIguPyvPwZ3/JkovkSx+LO7tsrPSjdL6iiGxD/HAx0AL4IBtSi IiZTtuL1EPoEi+RZtlp40/R+0zLW7UKqkryGxExuOdlZDv+2QVxSVtvpehAYYpu4GxLh j2qOqkRQb9rzbE/w2Qk0Yk2WBW7b2MKFgp5klHUUGejthkhXat/nuVARg7Jk4kNvWIiM qNQ96j1XG7pS/PHHBffzMDNDSHBCopOsZuFLoAGYpNzlH1FTGofOcv4OKMlUar2NpIxH 06SG6hWjvgyfj93w9aQCpzLBl+BI2NUnRC6Jt84+fBe7MQ/IHZ4z5TVusyPFvCHcal48 k/kw== X-Gm-Message-State: AA+aEWZ0hToRFrJVqNJIDp197I0V3HUSuI3kQqZXuw2hMw/8ws/K6sIG OZ6dJHnmjyI6bvSZIbdzKj5nhQ== X-Google-Smtp-Source: ALg8bN6k5sOG1yp1qY1eROWTDO9VkLwAIHdZf/IaKghawcwHldky16p5BB1PRcEXzobaFFp+Famiug== X-Received: by 2002:aed:3482:: with SMTP id x2mr27051852qtd.72.1546052986916; Fri, 28 Dec 2018 19:09:46 -0800 (PST) Received: from jkicinski-Precision-T1700.netronome.com ([66.60.152.14]) by smtp.gmail.com with ESMTPSA id i26sm14508170qkg.12.2018.12.28.19.09.45 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 28 Dec 2018 19:09:46 -0800 (PST) From: Jakub Kicinski To: alexei.starovoitov@gmail.com, daniel@iogearbox.net Cc: yhs@fb.com, netdev@vger.kernel.org, oss-drivers@netronome.com, Jakub Kicinski Subject: [RFC bpf-next v3 03/12] bpf: verifier: remove dead code Date: Fri, 28 Dec 2018 19:09:14 -0800 Message-Id: <20181229030923.4804-4-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.19.2 In-Reply-To: <20181229030923.4804-1-jakub.kicinski@netronome.com> References: <20181229030923.4804-1-jakub.kicinski@netronome.com> MIME-Version: 1.0 Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org Instead of overwriting dead code with jmp -1 instructions remove it completely for root. Adjust verifier state and line info appropriately. v2: - adjust func_info (Alexei); - make sure first instruction retains line info (Alexei). Signed-off-by: Jakub Kicinski --- include/linux/filter.h | 1 + kernel/bpf/core.c | 12 +++ kernel/bpf/verifier.c | 197 ++++++++++++++++++++++++++++++++++++++++- 3 files changed, 207 insertions(+), 3 deletions(-) diff --git a/include/linux/filter.h b/include/linux/filter.h index 8c8544b375eb..2cdb50bbf867 100644 --- a/include/linux/filter.h +++ b/include/linux/filter.h @@ -782,6 +782,7 @@ static inline bool bpf_dump_raw_ok(void) struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off, const struct bpf_insn *patch, u32 len); +int bpf_remove_insns(struct bpf_prog *prog, u32 off, u32 cnt); void bpf_clear_redirect_map(struct bpf_map *map); diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c index a40057b2c556..cc6fa754627c 100644 --- a/kernel/bpf/core.c +++ b/kernel/bpf/core.c @@ -461,6 +461,18 @@ struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off, return prog_adj; } +int bpf_remove_insns(struct bpf_prog *prog, u32 off, u32 cnt) +{ + /* Branch offsets can't overflow when program is shrinking, no need + * to call bpf_adj_branches(..., true) here + */ + memmove(prog->insnsi + off, prog->insnsi + off + cnt, + sizeof(struct bpf_insn) * (prog->len - off - cnt)); + prog->len -= cnt; + + return WARN_ON_ONCE(bpf_adj_branches(prog, off, off + cnt, off, false)); +} + void bpf_prog_kallsyms_del_subprogs(struct bpf_prog *fp) { int i; diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 30e2cd399b4a..a3880c6dac97 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -6233,6 +6233,171 @@ static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 of return new_prog; } +static int adjust_subprog_starts_after_remove(struct bpf_verifier_env *env, + u32 off, u32 cnt) +{ + int i, j; + + /* find first prog starting at or after off (first to remove) */ + for (i = 0; i < env->subprog_cnt; i++) + if (env->subprog_info[i].start >= off) + break; + /* find first prog starting at or after off + cnt (first to stay) */ + for (j = i; j < env->subprog_cnt; j++) + if (env->subprog_info[j].start >= off + cnt) + break; + /* if j doesn't start exactly at off + cnt, we are just removing + * the front of previous prog + */ + if (env->subprog_info[j].start != off + cnt) + j--; + + if (j > i) { + struct bpf_prog_aux *aux = env->prog->aux; + int move; + + /* move fake 'exit' subprog as well */ + move = env->subprog_cnt + 1 - j; + + memmove(env->subprog_info + i, + env->subprog_info + j, + sizeof(*env->subprog_info) * move); + env->subprog_cnt -= j - i; + + /* remove func_info */ + if (aux->func_info) { + move = aux->func_info_cnt - j; + + memmove(aux->func_info + i, + aux->func_info + j, + sizeof(*aux->func_info) * move); + aux->func_info_cnt -= j - i; + } + } else { + /* convert i from "first prog to remove" to "first to adjust" */ + if (env->subprog_info[i].start == off) + i++; + } + + /* update fake 'exit' subprog as well */ + for (; i <= env->subprog_cnt; i++) + env->subprog_info[i].start -= cnt; + + return 0; +} + +static int bpf_adj_linfo_after_remove(struct bpf_verifier_env *env, u32 off, + u32 cnt) +{ + struct bpf_subprog_info *need_first_linfo; + struct bpf_prog *prog = env->prog; + u32 i, l_off, l_cnt, nr_linfo; + struct bpf_line_info *linfo; + + nr_linfo = prog->aux->nr_linfo; + if (!nr_linfo || !cnt) + return 0; + + linfo = prog->aux->linfo; + + /* progs are already adjusted/removed, if program starts on off, it may + * had its start cut off and its line info may need to be preserved + */ + for (i = 0; i < env->subprog_cnt; i++) + if (env->subprog_info[i].start >= off) + break; + if (i < env->subprog_cnt && env->subprog_info[i].start == off) + need_first_linfo = &env->subprog_info[i]; + else + need_first_linfo = NULL; + + /* find first line info to remove */ + for (i = 0; i < nr_linfo; i++) + if (linfo[i].insn_off >= off) + break; + + /* count lines to be removed */ + l_off = i; + l_cnt = 0; + for (; i < nr_linfo; i++) + if (linfo[i].insn_off < off + cnt) + l_cnt++; + else + break; + + /* either we didn't actually cut the start or we can just use line info + * of first instruction if it exists + */ + if (i < nr_linfo && linfo[i].insn_off == off + cnt) + need_first_linfo = NULL; + if (need_first_linfo) { + if (WARN_ONCE(!l_cnt, + "verifier bug - no linfo removed, yet its missing")) + return -EINVAL; + if (WARN_ONCE(need_first_linfo->linfo_idx < l_off || + need_first_linfo->linfo_idx >= l_off + l_cnt, + "verifier bug - removed prog linfo not in removed range")) + return -EINVAL; + /* subprog linfo_idx is not adjusted yet, so just find out + * which line it used to be and swap it + */ + memmove(linfo + l_off, linfo + need_first_linfo->linfo_idx, + sizeof(*linfo)); + need_first_linfo->linfo_idx = l_off; + linfo[l_off].insn_off = off; + + l_off++; + l_cnt--; + } + + /* remove the line info which refers to the removed instructions */ + if (l_cnt) { + memmove(linfo + l_off, linfo + i, + sizeof(*linfo) * (nr_linfo - i)); + + prog->aux->nr_linfo -= l_cnt; + nr_linfo = prog->aux->nr_linfo; + } + + /* pull all linfo[i].insn_off >= off + cnt in by cnt */ + for (i = l_off; i < nr_linfo; i++) + linfo[i].insn_off -= cnt; + + /* fix up all subprogs (incl. 'exit') which start >= off */ + for (i = 0; i <= env->subprog_cnt; i++) + if (env->subprog_info[i].linfo_idx >= l_off + l_cnt) + env->subprog_info[i].linfo_idx -= l_cnt; + + return 0; +} + +static int verifier_remove_insns(struct bpf_verifier_env *env, u32 off, u32 cnt) +{ + struct bpf_insn_aux_data *aux_data = env->insn_aux_data; + unsigned int orig_prog_len = env->prog->len; + int err; + + if (!cnt) + return 0; + + err = bpf_remove_insns(env->prog, off, cnt); + if (err) + return err; + + err = adjust_subprog_starts_after_remove(env, off, cnt); + if (err) + return err; + + err = bpf_adj_linfo_after_remove(env, off, cnt); + if (err) + return err; + + memmove(aux_data + off, aux_data + off + cnt, + sizeof(*aux_data) * (orig_prog_len - off - cnt)); + + return 0; +} + /* The verifier does more data flow analysis than llvm and will not * explore branches that are dead at run time. Malicious programs can * have dead code too. Therefore replace all dead at-run-time code @@ -6293,6 +6458,30 @@ static void opt_hard_wire_dead_code_branches(struct bpf_verifier_env *env) } } +static int opt_remove_dead_code(struct bpf_verifier_env *env) +{ + struct bpf_insn_aux_data *aux_data = env->insn_aux_data; + int insn_cnt = env->prog->len; + int i, err; + + for (i = 0; i < insn_cnt; i++) { + int j; + + j = 0; + while (i + j < insn_cnt && !aux_data[i + j].seen) + j++; + if (!j) + continue; + + err = verifier_remove_insns(env, i, j); + if (err) + return err; + insn_cnt = env->prog->len; + } + + return 0; +} + /* convert load instructions that access fields of a context type into a * sequence of instructions that access fields of the underlying structure: * struct __sk_buff -> struct sk_buff @@ -7032,11 +7221,13 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, if (is_priv) { if (ret == 0) opt_hard_wire_dead_code_branches(env); + if (ret == 0) + ret = opt_remove_dead_code(env); + } else { + if (ret == 0) + sanitize_dead_code(env); } - if (ret == 0) - sanitize_dead_code(env); - if (ret == 0) /* program is valid, convert *(u32*)(ctx + off) accesses */ ret = convert_ctx_accesses(env); From patchwork Sat Dec 29 03:09:15 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 1019289 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=netronome.com Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=netronome-com.20150623.gappssmtp.com header.i=@netronome-com.20150623.gappssmtp.com header.b="BU/tEmsJ"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 43RT8Y3sB4z9s3l for ; Sat, 29 Dec 2018 14:10:05 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730087AbeL2DJv (ORCPT ); Fri, 28 Dec 2018 22:09:51 -0500 Received: from mail-qk1-f196.google.com ([209.85.222.196]:34409 "EHLO mail-qk1-f196.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730076AbeL2DJt (ORCPT ); Fri, 28 Dec 2018 22:09:49 -0500 Received: by mail-qk1-f196.google.com with SMTP id q8so13476395qke.1 for ; Fri, 28 Dec 2018 19:09:48 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=netronome-com.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=MKrOUkFcIPGBJ3UY6d5RMQm/kmktgYox4OdIO6ptptA=; b=BU/tEmsJ3T5i+TDvm9RWBWdLJFI2eYgeVrXD1X5W2PMz8xhCyjAwfrRARyAzraz+GC LAaY/Y77ovZBP0kLpV3SQ9YE+47NhSNLYAoVQOvZcRHLrmwlimsk7TbRfZEEJ1aTUj2T kDfRBwbVAWRlvwtwqgnofVY4ej7zL24iJWGthmNNK7b/x4IGQguxZGZIPHTP2wamVIW8 Yi0KEkxxkNcilwtkW1UxoGYu1NYpFYbVcUUhjKp65kgo2zObLV2UxvJ1B4FS1qrrd/ZU 0aXtl0BPU5EiUfLkwpWzY+UvTr/rg/KY7IafF8EQUVohkqgVAvH7RNovlJGOukDRxtEP Rqag== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=MKrOUkFcIPGBJ3UY6d5RMQm/kmktgYox4OdIO6ptptA=; b=BOClxn/vahQ4Jh+KZNXeklckwAxffQt6flaMkAakJl3kgIu3xtExh3Ax9Ed+TgdN4Q /qouT1aNvVKMtbfyF6omcAAXFRQ/nOVGHdcmtFj+pSpUJl8k2o11Pg/v6hTc/wJ9QEy+ 32STA7/zvO5/rxztBqbTv7hZ3VF+zD0Vdmhss/hatJBxqcvAf8MELd1MhjT/4W86Zk0o iF+adg/+GnxbK0Ma0Yu6O7LXkES8VrkKqAmLLdvjQS8OYCwwZ8vFQRaASCXOQ/N8jYDa R5epge/R+r1ErFlaL3rv8EbLpWc+LwIJTs9bno8fp1bSjBckq2G6rh0ppINUo5N1rmNm AGkw== X-Gm-Message-State: AJcUuke2OYhXRPCzFUixuJkyaRrBpnJMsKP2PlT7I9dB4BdJ/37OC8c8 /Pcrd9ba8j7NCsmc+qWPjclHXA== X-Google-Smtp-Source: ALg8bN7VgGbTVD2oTpy2AVRH23pNN85OoyOaT3NgM8PnISJ4kIwtSXqgIlTHkevA/KeRVgzUyngZiw== X-Received: by 2002:a37:c304:: with SMTP id a4mr27347081qkj.269.1546052988357; Fri, 28 Dec 2018 19:09:48 -0800 (PST) Received: from jkicinski-Precision-T1700.netronome.com ([66.60.152.14]) by smtp.gmail.com with ESMTPSA id i26sm14508170qkg.12.2018.12.28.19.09.47 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 28 Dec 2018 19:09:47 -0800 (PST) From: Jakub Kicinski To: alexei.starovoitov@gmail.com, daniel@iogearbox.net Cc: yhs@fb.com, netdev@vger.kernel.org, oss-drivers@netronome.com, Jakub Kicinski Subject: [RFC bpf-next v3 04/12] bpf: verifier: remove unconditional branches by 0 Date: Fri, 28 Dec 2018 19:09:15 -0800 Message-Id: <20181229030923.4804-5-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.19.2 In-Reply-To: <20181229030923.4804-1-jakub.kicinski@netronome.com> References: <20181229030923.4804-1-jakub.kicinski@netronome.com> MIME-Version: 1.0 Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org Unconditional branches by 0 instructions are basically noops but they can result from earlier optimizations, e.g. a conditional jumps which would never be taken or a conditional jump around dead code. Remove those branches. v0.2: - s/opt_remove_dead_branches/opt_remove_nops/ (Jiong). Signed-off-by: Jakub Kicinski Reviewed-by: Jiong Wang --- kernel/bpf/verifier.c | 23 +++++++++++++++++++++++ 1 file changed, 23 insertions(+) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index a3880c6dac97..598ef51e299d 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -6482,6 +6482,27 @@ static int opt_remove_dead_code(struct bpf_verifier_env *env) return 0; } +static int opt_remove_nops(struct bpf_verifier_env *env) +{ + const struct bpf_insn ja = BPF_JMP_IMM(BPF_JA, 0, 0, 0); + struct bpf_insn *insn = env->prog->insnsi; + int insn_cnt = env->prog->len; + int i, err; + + for (i = 0; i < insn_cnt; i++) { + if (memcmp(&insn[i], &ja, sizeof(ja))) + continue; + + err = verifier_remove_insns(env, i, 1); + if (err) + return err; + insn_cnt--; + i--; + } + + return 0; +} + /* convert load instructions that access fields of a context type into a * sequence of instructions that access fields of the underlying structure: * struct __sk_buff -> struct sk_buff @@ -7223,6 +7244,8 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, opt_hard_wire_dead_code_branches(env); if (ret == 0) ret = opt_remove_dead_code(env); + if (ret == 0) + ret = opt_remove_nops(env); } else { if (ret == 0) sanitize_dead_code(env); From patchwork Sat Dec 29 03:09:16 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 1019291 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=netronome.com Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=netronome-com.20150623.gappssmtp.com header.i=@netronome-com.20150623.gappssmtp.com header.b="A7X8n9eo"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 43RT8b04yMz9s3l for ; Sat, 29 Dec 2018 14:10:07 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730105AbeL2DJy (ORCPT ); Fri, 28 Dec 2018 22:09:54 -0500 Received: from mail-qt1-f196.google.com ([209.85.160.196]:38018 "EHLO mail-qt1-f196.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730076AbeL2DJw (ORCPT ); Fri, 28 Dec 2018 22:09:52 -0500 Received: by mail-qt1-f196.google.com with SMTP id p17so25054632qtl.5 for ; Fri, 28 Dec 2018 19:09:50 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=netronome-com.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=EFKqktDq5IG4I9DAKTgW++Yh3uFH3MGuzfKjmMlKXFY=; b=A7X8n9eo5JLl/l5EHenOkjRhqRE0CdkZzVtkcIGS8BRODfZASJ9A6LKPvp5DP1L6kJ YYOjLOahbCTcfIWwdcoVbFclmyQsF4kN1BWD9Wgi/6Opu75VijX23Um/B5rvnhToOpiO JL6wX4cIJlB8+RfeQvHeod5uqNRNuMhVEnm+531MhPBRO31nY80DwQ6X32Ox1cR0zw/R lQWsVbFjDcuwhyDo+PiD+6FAZ4rJ3La4XD+IhFe6zJv11IYdBKcL6XJBnu93Va4wRBLp rz9pc6QsnYwMkgGtU2FPF87oa1EW+TffhvT2s1yjHLT5J+WvzemR1zdQu84P1//sFFun j+qQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=EFKqktDq5IG4I9DAKTgW++Yh3uFH3MGuzfKjmMlKXFY=; b=KKroAQOY56Holpk4p3LKNJprpcOfiULJ9uEIEmyEmshQ6Pyudr+o3oAxItqKfK5GL4 nq20ZSWf5FpUCcj382ElPngB8xciLa5SylAUstwN9cjuNBUSzz8jNdSjHd01rGpN7aK4 rlaQE+3DWNnIIWLsuexwB9nxBLzM9SUg1lzuryx41CtPWKS42ZpwRrljoysSKWery+U/ Rn6pD9IqbCepnmfgrP5GJVYbKfv1y91FG30vzBq75RqlZZs6cWe8fTzHXGOicCoWTkLm F6zmFWmuDGDxpz8IwNM2xFOPf2GhOjl+KauOzu1Ez57NyfhDNPWw+w9VCDaWi3UGPoYe D2Wg== X-Gm-Message-State: AJcUukd7c4vpsRS3hPk6wjWd6lPVNgFGBP5mHQTf/7ezZfTW0hnGIAps cNEZok4qnQwFnNLQMw12E/guaQ== X-Google-Smtp-Source: ALg8bN6DYWio8LZxbHfanHzlQl2Qppc2NGzFc2xzVdIaOJ7l/zCVupVB9LbSradI51w0hJUZadT7HA== X-Received: by 2002:aed:2946:: with SMTP id s64mr27883951qtd.383.1546052990051; Fri, 28 Dec 2018 19:09:50 -0800 (PST) Received: from jkicinski-Precision-T1700.netronome.com ([66.60.152.14]) by smtp.gmail.com with ESMTPSA id i26sm14508170qkg.12.2018.12.28.19.09.48 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 28 Dec 2018 19:09:49 -0800 (PST) From: Jakub Kicinski To: alexei.starovoitov@gmail.com, daniel@iogearbox.net Cc: yhs@fb.com, netdev@vger.kernel.org, oss-drivers@netronome.com, Jakub Kicinski Subject: [RFC bpf-next v3 05/12] selftests: bpf: add tests for dead code removal Date: Fri, 28 Dec 2018 19:09:16 -0800 Message-Id: <20181229030923.4804-6-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.19.2 In-Reply-To: <20181229030923.4804-1-jakub.kicinski@netronome.com> References: <20181229030923.4804-1-jakub.kicinski@netronome.com> MIME-Version: 1.0 Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org Add tests for newly added dead code elimination. Both verifier and BTF tests are added. BTF test infrastructure has to be extended to be able to account for line info which is eliminated during dead code removal. Signed-off-by: Jakub Kicinski --- tools/testing/selftests/bpf/test_btf.c | 364 +++++++++++++++++++- tools/testing/selftests/bpf/test_verifier.c | 160 +++++++++ 2 files changed, 517 insertions(+), 7 deletions(-) diff --git a/tools/testing/selftests/bpf/test_btf.c b/tools/testing/selftests/bpf/test_btf.c index 8bcd38010582..2332d108087a 100644 --- a/tools/testing/selftests/bpf/test_btf.c +++ b/tools/testing/selftests/bpf/test_btf.c @@ -4070,6 +4070,10 @@ static struct prog_info_raw_test { __u32 line_info_rec_size; __u32 nr_jited_ksyms; bool expected_prog_load_failure; + __u32 dead_code_cnt; + __u32 dead_code_mask; + __u32 dead_func_cnt; + __u32 dead_func_mask; } info_raw_tests[] = { { .descr = "func_type (main func + one sub)", @@ -4496,6 +4500,337 @@ static struct prog_info_raw_test { .expected_prog_load_failure = true, }, +{ + .descr = "line_info (dead start)", + .raw_types = { + BTF_TYPE_INT_ENC(NAME_TBD, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ + BTF_END_RAW, + }, + BTF_STR_SEC("\0int\0/* dead jmp */\0int a=1;\0int b=2;\0return a + b;\0return a + b;"), + .insns = { + BPF_JMP_IMM(BPF_JA, 0, 0, 0), + BPF_MOV64_IMM(BPF_REG_0, 1), + BPF_MOV64_IMM(BPF_REG_1, 2), + BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1), + BPF_EXIT_INSN(), + }, + .prog_type = BPF_PROG_TYPE_TRACEPOINT, + .func_info_cnt = 0, + .line_info = { + BPF_LINE_INFO_ENC(0, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(1, 0, NAME_TBD, 2, 9), + BPF_LINE_INFO_ENC(2, 0, NAME_TBD, 3, 8), + BPF_LINE_INFO_ENC(3, 0, NAME_TBD, 4, 7), + BPF_LINE_INFO_ENC(4, 0, NAME_TBD, 5, 6), + BTF_END_RAW, + }, + .line_info_rec_size = sizeof(struct bpf_line_info), + .nr_jited_ksyms = 1, + .dead_code_cnt = 1, + .dead_code_mask = 0x01, +}, + +{ + .descr = "line_info (dead end)", + .raw_types = { + BTF_TYPE_INT_ENC(NAME_TBD, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ + BTF_END_RAW, + }, + BTF_STR_SEC("\0int\0int a=1;\0int b=2;\0return a + b;\0/* dead jmp */\0return a + b;\0/* dead exit */"), + .insns = { + BPF_MOV64_IMM(BPF_REG_0, 1), + BPF_MOV64_IMM(BPF_REG_1, 2), + BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1), + BPF_JMP_IMM(BPF_JGE, BPF_REG_0, 10, 1), + BPF_EXIT_INSN(), + BPF_EXIT_INSN(), + }, + .prog_type = BPF_PROG_TYPE_TRACEPOINT, + .func_info_cnt = 0, + .line_info = { + BPF_LINE_INFO_ENC(0, 0, NAME_TBD, 1, 12), + BPF_LINE_INFO_ENC(1, 0, NAME_TBD, 2, 11), + BPF_LINE_INFO_ENC(2, 0, NAME_TBD, 3, 10), + BPF_LINE_INFO_ENC(3, 0, NAME_TBD, 4, 9), + BPF_LINE_INFO_ENC(4, 0, NAME_TBD, 5, 8), + BPF_LINE_INFO_ENC(5, 0, NAME_TBD, 6, 7), + BTF_END_RAW, + }, + .line_info_rec_size = sizeof(struct bpf_line_info), + .nr_jited_ksyms = 1, + .dead_code_cnt = 2, + .dead_code_mask = 0x28, +}, + +{ + .descr = "line_info (dead code + subprog + func_info)", + .raw_types = { + BTF_TYPE_INT_ENC(NAME_TBD, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ + BTF_FUNC_PROTO_ENC(1, 1), /* [2] */ + BTF_FUNC_PROTO_ARG_ENC(NAME_TBD, 1), + BTF_FUNC_ENC(NAME_TBD, 2), /* [3] */ + BTF_FUNC_ENC(NAME_TBD, 2), /* [4] */ + BTF_END_RAW, + }, + BTF_STR_SEC("\0int\0x\0sub\0main\0int a=1+1;\0/* dead jmp */" + "\0/* dead */\0/* dead */\0/* dead */\0/* dead */" + "\0/* dead */\0/* dead */\0/* dead */\0/* dead */" + "\0return func(a);\0b+=1;\0return b;"), + .insns = { + BPF_MOV64_IMM(BPF_REG_2, 1), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, 1), + BPF_MOV64_REG(BPF_REG_1, BPF_REG_2), + BPF_JMP_IMM(BPF_JGE, BPF_REG_2, 0, 8), + BPF_MOV64_IMM(BPF_REG_2, 1), + BPF_MOV64_IMM(BPF_REG_2, 1), + BPF_MOV64_IMM(BPF_REG_2, 1), + BPF_MOV64_IMM(BPF_REG_2, 1), + BPF_MOV64_IMM(BPF_REG_2, 1), + BPF_MOV64_IMM(BPF_REG_2, 1), + BPF_MOV64_IMM(BPF_REG_2, 1), + BPF_MOV64_IMM(BPF_REG_2, 1), + BPF_CALL_REL(1), + BPF_EXIT_INSN(), + BPF_MOV64_REG(BPF_REG_0, BPF_REG_1), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1), + BPF_EXIT_INSN(), + }, + .prog_type = BPF_PROG_TYPE_TRACEPOINT, + .func_info_cnt = 2, + .func_info_rec_size = 8, + .func_info = { {0, 4}, {14, 3} }, + .line_info = { + BPF_LINE_INFO_ENC(0, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(3, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(4, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(5, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(6, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(7, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(8, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(9, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(10, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(11, 0, NAME_TBD, 2, 9), + BPF_LINE_INFO_ENC(12, 0, NAME_TBD, 2, 9), + BPF_LINE_INFO_ENC(14, 0, NAME_TBD, 3, 8), + BPF_LINE_INFO_ENC(16, 0, NAME_TBD, 4, 7), + BTF_END_RAW, + }, + .line_info_rec_size = sizeof(struct bpf_line_info), + .nr_jited_ksyms = 2, + .dead_code_cnt = 9, + .dead_code_mask = 0x3fe, +}, + +{ + .descr = "line_info (dead subprog)", + .raw_types = { + BTF_TYPE_INT_ENC(NAME_TBD, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ + BTF_FUNC_PROTO_ENC(1, 1), /* [2] */ + BTF_FUNC_PROTO_ARG_ENC(NAME_TBD, 1), + BTF_FUNC_ENC(NAME_TBD, 2), /* [3] */ + BTF_FUNC_ENC(NAME_TBD, 2), /* [4] */ + BTF_FUNC_ENC(NAME_TBD, 2), /* [5] */ + BTF_END_RAW, + }, + BTF_STR_SEC("\0int\0x\0daed\0main\0func\0int a=1+1;\0/* live call */" + "\0return 0;\0return 0;\0/* dead */\0/* dead */" + "\0/* dead */\0return bla + 1;\0return bla + 1;" + "\0return bla + 1;\0return func(a);\0b+=1;\0return b;"), + .insns = { + BPF_MOV64_IMM(BPF_REG_2, 1), + BPF_JMP_IMM(BPF_JGE, BPF_REG_2, 0, 1), + BPF_CALL_REL(3), + BPF_CALL_REL(5), + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_EXIT_INSN(), + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_CALL_REL(1), + BPF_EXIT_INSN(), + BPF_MOV64_REG(BPF_REG_0, 2), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1), + BPF_EXIT_INSN(), + }, + .prog_type = BPF_PROG_TYPE_TRACEPOINT, + .func_info_cnt = 3, + .func_info_rec_size = 8, + .func_info = { {0, 4}, {6, 3}, {9, 5} }, + .line_info = { + BPF_LINE_INFO_ENC(0, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(3, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(4, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(5, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(6, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(7, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(8, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(9, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(10, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(11, 0, NAME_TBD, 2, 9), + BTF_END_RAW, + }, + .line_info_rec_size = sizeof(struct bpf_line_info), + .nr_jited_ksyms = 2, + .dead_code_cnt = 3, + .dead_code_mask = 0x70, + .dead_func_cnt = 1, + .dead_func_mask = 0x2, +}, + +{ + .descr = "line_info (dead last subprog)", + .raw_types = { + BTF_TYPE_INT_ENC(NAME_TBD, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ + BTF_FUNC_PROTO_ENC(1, 1), /* [2] */ + BTF_FUNC_PROTO_ARG_ENC(NAME_TBD, 1), + BTF_FUNC_ENC(NAME_TBD, 2), /* [3] */ + BTF_FUNC_ENC(NAME_TBD, 2), /* [5] */ + BTF_END_RAW, + }, + BTF_STR_SEC("\0int\0x\0dead\0main\0int a=1+1;\0/* live call */" + "\0return 0;\0return 0;\0/* dead */\0/* dead */" + "\0/* dead */\0return bla + 1;\0return bla + 1;" + "\0return bla + 1;\0return func(a);\0b+=1;\0return b;"), + .insns = { + BPF_MOV64_IMM(BPF_REG_2, 1), + BPF_JMP_IMM(BPF_JGE, BPF_REG_2, 0, 1), + BPF_CALL_REL(2), + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_EXIT_INSN(), + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_EXIT_INSN(), + }, + .prog_type = BPF_PROG_TYPE_TRACEPOINT, + .func_info_cnt = 2, + .func_info_rec_size = 8, + .func_info = { {0, 4}, {5, 3} }, + .line_info = { + BPF_LINE_INFO_ENC(0, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(3, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(4, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(5, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(6, 0, NAME_TBD, 1, 10), + BTF_END_RAW, + }, + .line_info_rec_size = sizeof(struct bpf_line_info), + .nr_jited_ksyms = 1, + .dead_code_cnt = 2, + .dead_code_mask = 0x18, + .dead_func_cnt = 1, + .dead_func_mask = 0x2, +}, + +{ + .descr = "line_info (dead subprog + dead start)", + .raw_types = { + BTF_TYPE_INT_ENC(NAME_TBD, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ + BTF_FUNC_PROTO_ENC(1, 1), /* [2] */ + BTF_FUNC_PROTO_ARG_ENC(NAME_TBD, 1), + BTF_FUNC_ENC(NAME_TBD, 2), /* [3] */ + BTF_FUNC_ENC(NAME_TBD, 2), /* [4] */ + BTF_FUNC_ENC(NAME_TBD, 2), /* [5] */ + BTF_END_RAW, + }, + BTF_STR_SEC("\0int\0x\0daed\0main\0func\0int a=1+1;\0/* live call */" + "\0return 0;\0return 0;\0/* dead */\0/* dead */" + "\0/* dead */\0return bla + 1;\0return bla + 1;" + "\0return bla + 1;\0return func(a);\0b+=1;\0return b;"), + .insns = { + BPF_JMP_IMM(BPF_JA, 0, 0, 0), + BPF_MOV64_IMM(BPF_REG_2, 1), + BPF_JMP_IMM(BPF_JGE, BPF_REG_2, 0, 1), + BPF_CALL_REL(3), + BPF_CALL_REL(5), + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_EXIT_INSN(), + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_CALL_REL(1), + BPF_EXIT_INSN(), + BPF_JMP_IMM(BPF_JA, 0, 0, 0), + BPF_MOV64_REG(BPF_REG_0, 2), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1), + BPF_EXIT_INSN(), + }, + .prog_type = BPF_PROG_TYPE_TRACEPOINT, + .func_info_cnt = 3, + .func_info_rec_size = 8, + .func_info = { {0, 4}, {7, 3}, {10, 5} }, + .line_info = { + BPF_LINE_INFO_ENC(0, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(3, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(4, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(5, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(6, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(7, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(8, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(9, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(10, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(11, 0, NAME_TBD, 2, 9), + BPF_LINE_INFO_ENC(12, 0, NAME_TBD, 2, 9), + BPF_LINE_INFO_ENC(13, 0, NAME_TBD, 2, 9), + BTF_END_RAW, + }, + .line_info_rec_size = sizeof(struct bpf_line_info), + .nr_jited_ksyms = 2, + .dead_code_cnt = 5, + .dead_code_mask = 0x1e2, + .dead_func_cnt = 1, + .dead_func_mask = 0x2, +}, + +{ + .descr = "line_info (dead subprog + dead start w/ move)", + .raw_types = { + BTF_TYPE_INT_ENC(NAME_TBD, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ + BTF_FUNC_PROTO_ENC(1, 1), /* [2] */ + BTF_FUNC_PROTO_ARG_ENC(NAME_TBD, 1), + BTF_FUNC_ENC(NAME_TBD, 2), /* [3] */ + BTF_FUNC_ENC(NAME_TBD, 2), /* [4] */ + BTF_FUNC_ENC(NAME_TBD, 2), /* [5] */ + BTF_END_RAW, + }, + BTF_STR_SEC("\0int\0x\0daed\0main\0func\0int a=1+1;\0/* live call */" + "\0return 0;\0return 0;\0/* dead */\0/* dead */" + "\0/* dead */\0return bla + 1;\0return bla + 1;" + "\0return bla + 1;\0return func(a);\0b+=1;\0return b;"), + .insns = { + BPF_MOV64_IMM(BPF_REG_2, 1), + BPF_JMP_IMM(BPF_JGE, BPF_REG_2, 0, 1), + BPF_CALL_REL(3), + BPF_CALL_REL(5), + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_EXIT_INSN(), + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_CALL_REL(1), + BPF_EXIT_INSN(), + BPF_JMP_IMM(BPF_JA, 0, 0, 0), + BPF_MOV64_REG(BPF_REG_0, 2), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1), + BPF_EXIT_INSN(), + }, + .prog_type = BPF_PROG_TYPE_TRACEPOINT, + .func_info_cnt = 3, + .func_info_rec_size = 8, + .func_info = { {0, 4}, {6, 3}, {9, 5} }, + .line_info = { + BPF_LINE_INFO_ENC(0, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(3, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(4, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(5, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(6, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(7, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(8, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(9, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(11, 0, NAME_TBD, 1, 10), + BPF_LINE_INFO_ENC(12, 0, NAME_TBD, 2, 9), + BTF_END_RAW, + }, + .line_info_rec_size = sizeof(struct bpf_line_info), + .nr_jited_ksyms = 2, + .dead_code_cnt = 3, + .dead_code_mask = 0x70, + .dead_func_cnt = 1, + .dead_func_mask = 0x2, +}, + }; static size_t probe_prog_length(const struct bpf_insn *fp) @@ -4555,6 +4890,7 @@ static int test_get_finfo(const struct prog_info_raw_test *test, struct bpf_func_info *finfo; __u32 info_len, rec_size, i; void *func_info = NULL; + __u32 nr_func_info; int err; /* get necessary lens */ @@ -4564,7 +4900,8 @@ static int test_get_finfo(const struct prog_info_raw_test *test, fprintf(stderr, "%s\n", btf_log_buf); return -1; } - if (CHECK(info.nr_func_info != test->func_info_cnt, + nr_func_info = test->func_info_cnt - test->dead_func_cnt; + if (CHECK(info.nr_func_info != nr_func_info, "incorrect info.nr_func_info (1st) %d", info.nr_func_info)) { return -1; @@ -4585,7 +4922,7 @@ static int test_get_finfo(const struct prog_info_raw_test *test, /* reset info to only retrieve func_info related data */ memset(&info, 0, sizeof(info)); - info.nr_func_info = test->func_info_cnt; + info.nr_func_info = nr_func_info; info.func_info_rec_size = rec_size; info.func_info = ptr_to_u64(func_info); err = bpf_obj_get_info_by_fd(prog_fd, &info, &info_len); @@ -4594,7 +4931,7 @@ static int test_get_finfo(const struct prog_info_raw_test *test, err = -1; goto done; } - if (CHECK(info.nr_func_info != test->func_info_cnt, + if (CHECK(info.nr_func_info != nr_func_info, "incorrect info.nr_func_info (2nd) %d", info.nr_func_info)) { err = -1; @@ -4608,7 +4945,9 @@ static int test_get_finfo(const struct prog_info_raw_test *test, } finfo = func_info; - for (i = 0; i < test->func_info_cnt; i++) { + for (i = 0; i < nr_func_info; i++) { + if (test->dead_func_mask & (1 << i)) + continue; if (CHECK(finfo->type_id != test->func_info[i][1], "incorrect func_type %u expected %u", finfo->type_id, test->func_info[i][1])) { @@ -4637,6 +4976,7 @@ static int test_get_linfo(const struct prog_info_raw_test *test, struct bpf_prog_info info = {}; __u32 *jited_func_lens = NULL; __u64 cur_func_ksyms; + __u32 dead_insns; int err; jited_cnt = cnt; @@ -4645,7 +4985,7 @@ static int test_get_linfo(const struct prog_info_raw_test *test, if (test->nr_jited_ksyms) nr_jited_ksyms = test->nr_jited_ksyms; else - nr_jited_ksyms = test->func_info_cnt; + nr_jited_ksyms = test->func_info_cnt - test->dead_func_cnt; nr_jited_func_lens = nr_jited_ksyms; info_len = sizeof(struct bpf_prog_info); @@ -4747,12 +5087,20 @@ static int test_get_linfo(const struct prog_info_raw_test *test, goto done; } + dead_insns = 0; + while (test->dead_code_mask & (1 << dead_insns)) + dead_insns++; + CHECK(linfo[0].insn_off, "linfo[0].insn_off:%u", linfo[0].insn_off); for (i = 1; i < cnt; i++) { const struct bpf_line_info *expected_linfo; - expected_linfo = patched_linfo + (i * test->line_info_rec_size); + while (test->dead_code_mask & (1 << (i + dead_insns))) + dead_insns++; + + expected_linfo = patched_linfo + + ((i + dead_insns) * test->line_info_rec_size); if (CHECK(linfo[i].insn_off <= linfo[i - 1].insn_off, "linfo[%u].insn_off:%u <= linfo[%u].insn_off:%u", i, linfo[i].insn_off, @@ -4910,7 +5258,9 @@ static int do_test_info_raw(unsigned int test_num) if (err) goto done; - err = test_get_linfo(test, patched_linfo, attr.line_info_cnt, prog_fd); + err = test_get_linfo(test, patched_linfo, + attr.line_info_cnt - test->dead_code_cnt, + prog_fd); if (err) goto done; diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c index 33f7d38849b8..3fb9b2a73174 100644 --- a/tools/testing/selftests/bpf/test_verifier.c +++ b/tools/testing/selftests/bpf/test_verifier.c @@ -14388,6 +14388,166 @@ static struct bpf_test tests[] = { .result_unpriv = ACCEPT, .result = ACCEPT, }, + { + "dead code: start", + .insns = { + BPF_JMP_IMM(BPF_JA, 0, 0, 2), + BPF_LDX_MEM(BPF_B, BPF_REG_8, BPF_REG_9, 0), + BPF_JMP_IMM(BPF_JA, 0, 0, 2), + BPF_MOV64_IMM(BPF_REG_0, 7), + BPF_JMP_IMM(BPF_JGE, BPF_REG_0, 10, -4), + BPF_EXIT_INSN(), + }, + .result = ACCEPT, + .retval = 7, + }, + { + "dead code: mid 1", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, 7), + BPF_JMP_IMM(BPF_JGE, BPF_REG_0, 0, 1), + BPF_JMP_IMM(BPF_JGE, BPF_REG_0, 10, 0), + BPF_EXIT_INSN(), + }, + .result = ACCEPT, + .retval = 7, + }, + { + "dead code: mid 2", + .insns = { + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, + BPF_FUNC_get_prandom_u32), + BPF_JMP_IMM(BPF_JSET, BPF_REG_0, 1, 4), + BPF_JMP_IMM(BPF_JSET, BPF_REG_0, 1, 1), + BPF_JMP_IMM(BPF_JA, 0, 0, 2), + BPF_MOV64_IMM(BPF_REG_0, 7), + BPF_EXIT_INSN(), + BPF_MOV64_IMM(BPF_REG_0, 1), + BPF_EXIT_INSN(), + }, + .result = ACCEPT, + .retval = 1, + }, + { + "dead code: end 1", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, 7), + BPF_JMP_IMM(BPF_JGE, BPF_REG_0, 10, 1), + BPF_EXIT_INSN(), + BPF_EXIT_INSN(), + }, + .result = ACCEPT, + .retval = 7, + }, + { + "dead code: end 2", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, 7), + BPF_JMP_IMM(BPF_JGE, BPF_REG_0, 10, 1), + BPF_EXIT_INSN(), + BPF_MOV64_IMM(BPF_REG_0, 12), + BPF_EXIT_INSN(), + }, + .result = ACCEPT, + .retval = 7, + }, + { + "dead code: end 3", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, 7), + BPF_JMP_IMM(BPF_JGE, BPF_REG_0, 8, 1), + BPF_EXIT_INSN(), + BPF_JMP_IMM(BPF_JGE, BPF_REG_0, 10, 1), + BPF_JMP_IMM(BPF_JA, 0, 0, 1), + BPF_MOV64_IMM(BPF_REG_0, 12), + BPF_JMP_IMM(BPF_JA, 0, 0, -5), + }, + .result = ACCEPT, + .retval = 7, + }, + { + "dead code: tail of main + func", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, 7), + BPF_JMP_IMM(BPF_JGE, BPF_REG_0, 8, 1), + BPF_EXIT_INSN(), + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, 1), + BPF_EXIT_INSN(), + BPF_MOV64_IMM(BPF_REG_0, 12), + BPF_EXIT_INSN(), + }, + .errstr_unpriv = "function calls to other bpf functions are allowed for root only", + .result_unpriv = REJECT, + .result = ACCEPT, + .retval = 7, + }, + { + "dead code: tail of main + two functions", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, 7), + BPF_JMP_IMM(BPF_JGE, BPF_REG_0, 8, 1), + BPF_EXIT_INSN(), + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, 1), + BPF_EXIT_INSN(), + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, 1), + BPF_EXIT_INSN(), + BPF_MOV64_IMM(BPF_REG_0, 12), + BPF_EXIT_INSN(), + }, + .errstr_unpriv = "function calls to other bpf functions are allowed for root only", + .result_unpriv = REJECT, + .result = ACCEPT, + .retval = 7, + }, + { + "dead code: function in the middle and mid of another func", + .insns = { + BPF_MOV64_IMM(BPF_REG_1, 7), + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, 3), + BPF_EXIT_INSN(), + BPF_MOV64_IMM(BPF_REG_0, 12), + BPF_EXIT_INSN(), + BPF_MOV64_IMM(BPF_REG_0, 7), + BPF_JMP_IMM(BPF_JGE, BPF_REG_1, 7, 1), + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, -5), + BPF_EXIT_INSN(), + }, + .errstr_unpriv = "function calls to other bpf functions are allowed for root only", + .result_unpriv = REJECT, + .result = ACCEPT, + .retval = 7, + }, + { + "dead code: middle of main before call", + .insns = { + BPF_MOV64_IMM(BPF_REG_1, 2), + BPF_JMP_IMM(BPF_JGE, BPF_REG_1, 2, 1), + BPF_MOV64_IMM(BPF_REG_1, 5), + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, 1), + BPF_EXIT_INSN(), + BPF_MOV64_REG(BPF_REG_0, BPF_REG_1), + BPF_EXIT_INSN(), + }, + .errstr_unpriv = "function calls to other bpf functions are allowed for root only", + .result_unpriv = REJECT, + .result = ACCEPT, + .retval = 2, + }, + { + "dead code: start of a function", + .insns = { + BPF_MOV64_IMM(BPF_REG_1, 2), + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, 1), + BPF_EXIT_INSN(), + BPF_JMP_IMM(BPF_JA, 0, 0, 0), + BPF_MOV64_REG(BPF_REG_0, BPF_REG_1), + BPF_EXIT_INSN(), + }, + .errstr_unpriv = "function calls to other bpf functions are allowed for root only", + .result_unpriv = REJECT, + .result = ACCEPT, + .retval = 2, + }, }; static int probe_filter_length(const struct bpf_insn *fp) From patchwork Sat Dec 29 03:09:17 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 1019290 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=netronome.com Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=netronome-com.20150623.gappssmtp.com header.i=@netronome-com.20150623.gappssmtp.com header.b="gLL3hwWX"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 43RT8Z1wMrz9s3q for ; Sat, 29 Dec 2018 14:10:06 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730098AbeL2DJx (ORCPT ); Fri, 28 Dec 2018 22:09:53 -0500 Received: from mail-qt1-f195.google.com ([209.85.160.195]:40356 "EHLO mail-qt1-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730088AbeL2DJw (ORCPT ); Fri, 28 Dec 2018 22:09:52 -0500 Received: by mail-qt1-f195.google.com with SMTP id k12so25052314qtf.7 for ; Fri, 28 Dec 2018 19:09:52 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=netronome-com.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=G/rur4kh3bv1nDz8YzE5/yHSe9Bod/zk4G4IWjmHD/Y=; b=gLL3hwWXz1QvzjAsTHmwnFWpkvI8i9NxDfI9wQAWTv40D3MFsfzY0dz/OcdS3Qok46 XHZs/G5dcz+h5ytlGr7LtHBH/LoVbt2pcvH9l3/KpKyx2vyT07/AVt5oMZLgNl1TxkaA rUSkPZt6YdJh6f28015r6l2ntEIj/4Zci7ZAQ8EGSGkUcMclWNN/wIV+CWoMOYcudk3J 6t65hD5bWBxSV0JPThAfN0jkpckTqVmHAZyHVIPMVMsknxzjy7f1iqejz9akaY6fy6C0 j22u3Qe5goZOtw5mA4clPCnsrSNeQ30E0y3/rtJFPuHs6ZYzsf3Sgii+Jm4F/HwiQPsk JngQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=G/rur4kh3bv1nDz8YzE5/yHSe9Bod/zk4G4IWjmHD/Y=; b=CXHWehq7KGYheMepgRY3aMkvIQRy6Qr4zUeXGPl84C7Dt3Us7BGd+EFggajGJKiUKy zFSwFO3ec5ume2zLZOUWZhvJlRokZl+wnfaOX88JwGVGziTAE6DO7Jdp9nUFL6GGM6jT ZL0zqjdQXiceLP+xE9j4To7yqdH3m3+DI70ckUEYVGTEbHonqckn03ig3tf2S1EDmpIh ZCsTI3ctsNJ0rwaXz5s2L/9JSr50KolErx7aLrw9JYlwKHwtISqe/QXLB2IxL+kk1Mas 5sW5Rzv7rY73UaXk5Kl0dAgBu9RrHSRnSN4wSTmjhBtZ95NbwsW8U297NMoMAf1q2Lv0 GT8g== X-Gm-Message-State: AA+aEWZpfjTGu3QYCaKYwvUZtZNbqNoLGs1yC9S6ZVi2Q1Aqa6h7xkLA iLfJz06vamroJMfm7Pw3JUslOlmUJjM= X-Google-Smtp-Source: ALg8bN4b5FpwigjS6qjso2P8XP7BZ1cKn4r7/IisA9+x0iT+lKDmoBKbQBS52EwSRzsHfKhVr7yl0w== X-Received: by 2002:ac8:c7:: with SMTP id d7mr27414455qtg.326.1546052991635; Fri, 28 Dec 2018 19:09:51 -0800 (PST) Received: from jkicinski-Precision-T1700.netronome.com ([66.60.152.14]) by smtp.gmail.com with ESMTPSA id i26sm14508170qkg.12.2018.12.28.19.09.50 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 28 Dec 2018 19:09:51 -0800 (PST) From: Jakub Kicinski To: alexei.starovoitov@gmail.com, daniel@iogearbox.net Cc: yhs@fb.com, netdev@vger.kernel.org, oss-drivers@netronome.com, Jakub Kicinski Subject: [RFC bpf-next v3 06/12] bpf: verifier: record original instruction index Date: Fri, 28 Dec 2018 19:09:17 -0800 Message-Id: <20181229030923.4804-7-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.19.2 In-Reply-To: <20181229030923.4804-1-jakub.kicinski@netronome.com> References: <20181229030923.4804-1-jakub.kicinski@netronome.com> MIME-Version: 1.0 Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org The communication between the verifier and advanced JITs is based on instruction indexes. We have to keep them stable throughout the optimizations otherwise referring to a particular instruction gets messy quickly. Signed-off-by: Jakub Kicinski Reviewed-by: Quentin Monnet --- include/linux/bpf_verifier.h | 1 + kernel/bpf/verifier.c | 8 +++++--- 2 files changed, 6 insertions(+), 3 deletions(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index c233efc106c6..414d1aeba897 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -176,6 +176,7 @@ struct bpf_insn_aux_data { int ctx_field_size; /* the ctx field size for load insn, maybe 0 */ int sanitize_stack_off; /* stack slot to be cleared */ bool seen; /* this insn was processed by the verifier */ + unsigned int orig_idx; /* original instruction index */ }; #define MAX_USED_MAPS 64 /* max number of maps accessed by one eBPF program */ diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 598ef51e299d..d04c403b7c40 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -7142,7 +7142,7 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, { struct bpf_verifier_env *env; struct bpf_verifier_log *log; - int ret = -EINVAL; + int i, len, ret = -EINVAL; bool is_priv; /* no program is valid */ @@ -7157,12 +7157,14 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, return -ENOMEM; log = &env->log; + len = (*prog)->len; env->insn_aux_data = - vzalloc(array_size(sizeof(struct bpf_insn_aux_data), - (*prog)->len)); + vzalloc(array_size(sizeof(struct bpf_insn_aux_data), len)); ret = -ENOMEM; if (!env->insn_aux_data) goto err_free_env; + for (i = 0; i < len; i++) + env->insn_aux_data[i].orig_idx = i; env->prog = *prog; env->ops = bpf_verifier_ops[env->prog->type]; From patchwork Sat Dec 29 03:09:18 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 1019292 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=netronome.com Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=netronome-com.20150623.gappssmtp.com header.i=@netronome-com.20150623.gappssmtp.com header.b="KOnBtd4I"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 43RT8b6L7Yz9s3q for ; Sat, 29 Dec 2018 14:10:07 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730113AbeL2DJ4 (ORCPT ); Fri, 28 Dec 2018 22:09:56 -0500 Received: from mail-qt1-f195.google.com ([209.85.160.195]:46026 "EHLO mail-qt1-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730100AbeL2DJy (ORCPT ); Fri, 28 Dec 2018 22:09:54 -0500 Received: by mail-qt1-f195.google.com with SMTP id e5so25021568qtr.12 for ; Fri, 28 Dec 2018 19:09:53 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=netronome-com.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=Ew5QMWvUQ/agm2V/DS8HAIDBgn5hFZDjGjbaL3YL+gg=; b=KOnBtd4Ic/8lBKwY6LH3c5OYGHGMnFSCmhVdBucJYodmMO/6S9ZYZcYjGnb2tpSAFD 63uPCtfMeUrBK4nTHunAeT6qkOVDLVfCAg3C15p6MHty2Yb5ElD2NZlHt5Um74NtnRqn AavjUdKzd/GhdEpkiumkZS5N+9kGPmSlbMvKmj9UYZF7Pbbu1770kqHQVaKw+ch/kfmA cJqZXPIo6fE0lbYOHAcwlDd+ppvkgbpy90Jj0xyTu9y3pvwPG/tgGwBcCSwJIx+w2+lb qlwsFrwAskexkvDA+IGMuj489Hv/qfKWwwFmDMB467u+x3blNrqOT0uRhDInHrFyY/lL Jflw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=Ew5QMWvUQ/agm2V/DS8HAIDBgn5hFZDjGjbaL3YL+gg=; b=keV5CMlhyKP209LDIkkBsWlPTodd+C5g9DCvcsdn7T5N5IUfoJpLECcLWMoBxzlXQE pxlkATCT42vPrt+TCzkLx0OOlOiC5K+M7mzENH2TgH1Rfax5ui66NzqFh3oT2ZDLy/xa k+6PJtH7FpZflC3wFRH26VoAiErQpt8u7Fl069j1/pR9GsmnibDnyn/PsosAVcYhpNp0 r5FuqocyaXa99qtwnl0vLIRNwiSSeyrgZG0h24eKNbaD+FIOdarxzk8leDw0x3XoUDpE zGTPkqvDinXEYCaeKARJOdYqBIpjtbPBYkwidWxV3bVsk8z6EtdsFAJQxskx2LdWtkb+ 59IA== X-Gm-Message-State: AA+aEWbtPvcTAY8w7PoCWC8i48FQ/n6iTwQ8AtSVbcVdVenPns/9THSI 7bh1d1Wg7w6kgxR4gpUs7pnKug== X-Google-Smtp-Source: ALg8bN5yxtAJ80ZaU9dvor+IlJBdE0B6rwt4FbwC+EthgRUCqpjc++ASWNIqhfSmXQ/l1gW6rIc5Aw== X-Received: by 2002:ac8:3896:: with SMTP id f22mr26959247qtc.337.1546052993188; Fri, 28 Dec 2018 19:09:53 -0800 (PST) Received: from jkicinski-Precision-T1700.netronome.com ([66.60.152.14]) by smtp.gmail.com with ESMTPSA id i26sm14508170qkg.12.2018.12.28.19.09.51 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 28 Dec 2018 19:09:52 -0800 (PST) From: Jakub Kicinski To: alexei.starovoitov@gmail.com, daniel@iogearbox.net Cc: yhs@fb.com, netdev@vger.kernel.org, oss-drivers@netronome.com, Jakub Kicinski Subject: [RFC bpf-next v3 07/12] bpf: notify offload JITs about optimizations Date: Fri, 28 Dec 2018 19:09:18 -0800 Message-Id: <20181229030923.4804-8-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.19.2 In-Reply-To: <20181229030923.4804-1-jakub.kicinski@netronome.com> References: <20181229030923.4804-1-jakub.kicinski@netronome.com> MIME-Version: 1.0 Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org Let offload JITs know when instructions are replaced and optimized out, so they can update their state appropriately. The optimizations are best effort, if JIT returns an error from any callback verifier will stop notifying it as state may now be out of sync, but the verifier continues making progress. Signed-off-by: Jakub Kicinski Reviewed-by: Quentin Monnet --- include/linux/bpf.h | 7 +++++++ include/linux/bpf_verifier.h | 5 +++++ kernel/bpf/offload.c | 35 +++++++++++++++++++++++++++++++++++ kernel/bpf/verifier.c | 6 ++++++ 4 files changed, 53 insertions(+) diff --git a/include/linux/bpf.h b/include/linux/bpf.h index e734f163bd0b..3851529062ec 100644 --- a/include/linux/bpf.h +++ b/include/linux/bpf.h @@ -268,9 +268,15 @@ struct bpf_verifier_ops { }; struct bpf_prog_offload_ops { + /* verifier basic callbacks */ int (*insn_hook)(struct bpf_verifier_env *env, int insn_idx, int prev_insn_idx); int (*finalize)(struct bpf_verifier_env *env); + /* verifier optimization callbacks (called after .finalize) */ + int (*replace_insn)(struct bpf_verifier_env *env, u32 off, + struct bpf_insn *insn); + int (*remove_insns)(struct bpf_verifier_env *env, u32 off, u32 cnt); + /* program management callbacks */ int (*prepare)(struct bpf_prog *prog); int (*translate)(struct bpf_prog *prog); void (*destroy)(struct bpf_prog *prog); @@ -283,6 +289,7 @@ struct bpf_prog_offload { void *dev_priv; struct list_head offloads; bool dev_state; + bool opt_failed; void *jited_image; u32 jited_len; }; diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 414d1aeba897..ff6653fc8c45 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -253,5 +253,10 @@ int bpf_prog_offload_verifier_prep(struct bpf_prog *prog); int bpf_prog_offload_verify_insn(struct bpf_verifier_env *env, int insn_idx, int prev_insn_idx); int bpf_prog_offload_finalize(struct bpf_verifier_env *env); +void +bpf_prog_offload_replace_insn(struct bpf_verifier_env *env, u32 off, + struct bpf_insn *insn); +void +bpf_prog_offload_remove_insns(struct bpf_verifier_env *env, u32 off, u32 cnt); #endif /* _LINUX_BPF_VERIFIER_H */ diff --git a/kernel/bpf/offload.c b/kernel/bpf/offload.c index 54cf2b9c44a4..39dba8c90331 100644 --- a/kernel/bpf/offload.c +++ b/kernel/bpf/offload.c @@ -173,6 +173,41 @@ int bpf_prog_offload_finalize(struct bpf_verifier_env *env) return ret; } +void +bpf_prog_offload_replace_insn(struct bpf_verifier_env *env, u32 off, + struct bpf_insn *insn) +{ + const struct bpf_prog_offload_ops *ops; + struct bpf_prog_offload *offload; + int ret = -EOPNOTSUPP; + + down_read(&bpf_devs_lock); + offload = env->prog->aux->offload; + if (offload) { + ops = offload->offdev->ops; + if (!offload->opt_failed && ops->replace_insn) + ret = ops->replace_insn(env, off, insn); + offload->opt_failed |= ret; + } + up_read(&bpf_devs_lock); +} + +void +bpf_prog_offload_remove_insns(struct bpf_verifier_env *env, u32 off, u32 cnt) +{ + struct bpf_prog_offload *offload; + int ret = -EOPNOTSUPP; + + down_read(&bpf_devs_lock); + offload = env->prog->aux->offload; + if (offload) { + if (!offload->opt_failed && offload->offdev->ops->remove_insns) + ret = offload->offdev->ops->remove_insns(env, off, cnt); + offload->opt_failed |= ret; + } + up_read(&bpf_devs_lock); +} + static void __bpf_prog_offload_destroy(struct bpf_prog *prog) { struct bpf_prog_offload *offload = prog->aux->offload; diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index d04c403b7c40..6c0ceb08f8c4 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -6380,6 +6380,9 @@ static int verifier_remove_insns(struct bpf_verifier_env *env, u32 off, u32 cnt) if (!cnt) return 0; + if (bpf_prog_is_dev_bound(env->prog->aux)) + bpf_prog_offload_remove_insns(env, off, cnt); + err = bpf_remove_insns(env->prog, off, cnt); if (err) return err; @@ -6454,6 +6457,9 @@ static void opt_hard_wire_dead_code_branches(struct bpf_verifier_env *env) else continue; + if (bpf_prog_is_dev_bound(env->prog->aux)) + bpf_prog_offload_replace_insn(env, i, &ja); + memcpy(insn, &ja, sizeof(ja)); } } From patchwork Sat Dec 29 03:09:19 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 1019293 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=netronome.com Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=netronome-com.20150623.gappssmtp.com header.i=@netronome-com.20150623.gappssmtp.com header.b="0qRr9Luo"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 43RT8c4Fndz9s3l for ; Sat, 29 Dec 2018 14:10:08 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730121AbeL2DKA (ORCPT ); Fri, 28 Dec 2018 22:10:00 -0500 Received: from mail-qt1-f193.google.com ([209.85.160.193]:34317 "EHLO mail-qt1-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730107AbeL2DJz (ORCPT ); Fri, 28 Dec 2018 22:09:55 -0500 Received: by mail-qt1-f193.google.com with SMTP id r14so25111733qtp.1 for ; Fri, 28 Dec 2018 19:09:55 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=netronome-com.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=1q4aFkUv51IkHwt4k3g17/VMVNN46EG7Z0O9ShePG0U=; b=0qRr9Luo1vS+1KmXxbkh2vDoIC4JdzmW9lEMtwof9ZJR+GMDQ0AxLqZj/a7QPpZeUg 7EUeyvdx76m31242kJdUNMJjNTKbTJ8z9irT21w6+Q6Y93MvLe+ztdVPQdJ79aVUcuvN 06CTyr6+6rtl6SA2tibRjTc2smvqA7lX4atBk+8rPJkNFfsel3IhA88IEZIjYaY5UKK3 YMv3ZIZGBwDIztE26Bnpv/LSxaEaQu4V9fiqoRkpDeWpRfqQ5U6z6NIgralmC/i+Y1DX kWMBBf/K43CESGndFlKk8YzQPaXnKIqxTm5eAd5CQZ4Y9XMYPGqfnQjXtVFHX4AoPodH hxCg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=1q4aFkUv51IkHwt4k3g17/VMVNN46EG7Z0O9ShePG0U=; b=IO+NuEob8XK0ks4EvdKxNItw+x3/Y6RxupYmPU3RMObz0hdtcXKXbFGYFOwC+RtbZ0 RPVZ4cDC3CUDRT2vxey0iGqxGSFF8juzSeyFZhUBgbCUTnt4k72mY5H/FRuKznY6llc6 4ymJz0gG+2OQcHK2ywPlDzZ/L5rDfj171/WyO8teeWTmjV+X9yR4RG/XkRRYNJdlFvZG jW7E6LvUy+BiOFOKxv6A7vqfn2oRNir7iK5ttdSrR40ykQ3LUS2R0mbOu6IKKHjSTGdO 8XNS3fN330gYpUpeAvNn7HGw4gMD/5QoYc1pB1j/Pdbckh/aEYqGd+TosGb9rIIK1ZH/ kNOw== X-Gm-Message-State: AJcUukdj7RZGmGIV/JO1e+R3lu6SD5KSd72tv/Gn6wf5Re+0wXo9W/eL oFbjjqV1REFy4AqaGteS4ZKzWg== X-Google-Smtp-Source: AFSGD/VWOi14pSZ/cUSBDPWLmJHDoTeaW1q8qyu/rGkdSfjBl+Nc0W0t6yBSt8v00lmhvmzD8p5Cag== X-Received: by 2002:ac8:27c8:: with SMTP id x8mr27540805qtx.352.1546052994573; Fri, 28 Dec 2018 19:09:54 -0800 (PST) Received: from jkicinski-Precision-T1700.netronome.com ([66.60.152.14]) by smtp.gmail.com with ESMTPSA id i26sm14508170qkg.12.2018.12.28.19.09.53 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 28 Dec 2018 19:09:54 -0800 (PST) From: Jakub Kicinski To: alexei.starovoitov@gmail.com, daniel@iogearbox.net Cc: yhs@fb.com, netdev@vger.kernel.org, oss-drivers@netronome.com, Jakub Kicinski Subject: [RFC bpf-next v3 08/12] nfp: bpf: don't use instruction number for jump target Date: Fri, 28 Dec 2018 19:09:19 -0800 Message-Id: <20181229030923.4804-9-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.19.2 In-Reply-To: <20181229030923.4804-1-jakub.kicinski@netronome.com> References: <20181229030923.4804-1-jakub.kicinski@netronome.com> MIME-Version: 1.0 Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org Instruction number is meaningless at code gen phase. The target of the instruction is overwritten by nfp_fixup_branches(). The convention is to put the raw offset in target address as a place holder. See cmp_* functions. Signed-off-by: Jakub Kicinski Reviewed-by: Quentin Monnet --- drivers/net/ethernet/netronome/nfp/bpf/jit.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/drivers/net/ethernet/netronome/nfp/bpf/jit.c b/drivers/net/ethernet/netronome/nfp/bpf/jit.c index e23ca90289f7..323587dee498 100644 --- a/drivers/net/ethernet/netronome/nfp/bpf/jit.c +++ b/drivers/net/ethernet/netronome/nfp/bpf/jit.c @@ -3182,7 +3182,7 @@ bpf_to_bpf_call(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta) wrp_immed_relo(nfp_prog, imm_b(nfp_prog), 0, RELO_IMMED_REL); } else { ret_tgt = nfp_prog_current_offset(nfp_prog) + 2; - emit_br(nfp_prog, BR_UNC, meta->n + 1 + meta->insn.imm, 1); + emit_br(nfp_prog, BR_UNC, meta->insn.imm, 1); offset_br = nfp_prog_current_offset(nfp_prog); } wrp_immed_relo(nfp_prog, ret_reg(nfp_prog), ret_tgt, RELO_IMMED_REL); From patchwork Sat Dec 29 03:09:20 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 1019297 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=netronome.com Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=netronome-com.20150623.gappssmtp.com header.i=@netronome-com.20150623.gappssmtp.com header.b="y7VJdC2z"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 43RT8h2cKBz9s3l for ; Sat, 29 Dec 2018 14:10:12 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730145AbeL2DKL (ORCPT ); Fri, 28 Dec 2018 22:10:11 -0500 Received: from mail-qt1-f193.google.com ([209.85.160.193]:46028 "EHLO mail-qt1-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730114AbeL2DJ6 (ORCPT ); Fri, 28 Dec 2018 22:09:58 -0500 Received: by mail-qt1-f193.google.com with SMTP id e5so25021636qtr.12 for ; Fri, 28 Dec 2018 19:09:56 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=netronome-com.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=3rZXzgyy1JJNg/THmYA5WRz8V3LXcQh3i0TaslLrNkM=; b=y7VJdC2zZpwLk3rFEfU3WWFaybniJksIdzbQiwwGXUGldCYmBdaIwmijmbAzpVVrVU WiJeM2SA38XvG8C8++B/oVH6Oe0g9Xlf+fsKxxIqx8RhOQCvbrdTsivYjzSbDKmfI1l3 GS6LrBmWEgnR5ZtNNU5A/OtthlsXA5in/+AIszD2PIB0l7l8Du78tefXpKFIfRaBpobh X1RQepsA04ftgjnuvhB4EJ48jGsQhQOKOJ2+PqzfzkR9BpD6a6dgpYDDT4SefIM5v+Xg UPlrvHfFL0hKmx4OzBMKtkrJgW3/MeorqO2deysz3CvMeLFUvByMCt9wiiJmjtUH+Tnb 5OfQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=3rZXzgyy1JJNg/THmYA5WRz8V3LXcQh3i0TaslLrNkM=; b=RkOuo/D7Aby7GNEzKxNW3+FM/VQ500ZEgChKOmPfsP/prYvmT2GBZuR+wCMp/3g2HF 6/t7x2ojf0jw0MbPt+kRHRecwF5Ih89ZKNZmE/OGDCGjvxUxDaIXRwrlRlZGFDleXkjb An7p8YuRA6k9MKn5rHtiiNShxK8UU1hx+iQYzqNDdMUVCZmZuaiFOZeEm7qnAn5ryIDz PNkLehYyOB62N4osf+j2YwAtwT1COUunZRJ3v+7pam64vvspB62atRsYDQEm3LGYJHyY 7vLmxpiLOpKboS53OMZpYsE/O1siOp514oo7VIIbDJ/fmlFbRCJGR09NObJvvM0dceA8 LopA== X-Gm-Message-State: AA+aEWaz3rXlWFWilCEL1yHfXne3QHrt3knw6p3IemGDN4xp33GlISvy 0HHGow1BNOnRYTKmMNIaVlM++A== X-Google-Smtp-Source: AFSGD/U/PfJNPsMiTrh9Ax/yyG12U1XtUdn6V23vU4+fH22tAhwgLQJGJSUupYE2tFmrcBSKwvNpUg== X-Received: by 2002:ac8:3038:: with SMTP id f53mr27650699qte.45.1546052995980; Fri, 28 Dec 2018 19:09:55 -0800 (PST) Received: from jkicinski-Precision-T1700.netronome.com ([66.60.152.14]) by smtp.gmail.com with ESMTPSA id i26sm14508170qkg.12.2018.12.28.19.09.54 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 28 Dec 2018 19:09:55 -0800 (PST) From: Jakub Kicinski To: alexei.starovoitov@gmail.com, daniel@iogearbox.net Cc: yhs@fb.com, netdev@vger.kernel.org, oss-drivers@netronome.com, Jakub Kicinski Subject: [RFC bpf-next v3 09/12] nfp: bpf: split up the skip flag Date: Fri, 28 Dec 2018 19:09:20 -0800 Message-Id: <20181229030923.4804-10-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.19.2 In-Reply-To: <20181229030923.4804-1-jakub.kicinski@netronome.com> References: <20181229030923.4804-1-jakub.kicinski@netronome.com> MIME-Version: 1.0 Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org We fail program loading if jump lands on a skipped instruction. This is for historical reasons, it used to be that we only skipped instructions optimized out based on prior context, and therefore the optimization would be buggy if we jumped directly to such instruction (because the context would be skipped by the jump). There are cases where instructions can be skipped without any context, for example there is no point in generating code for: r0 |= 0 We will also soon support dropping dead code, so make the skip logic differentiate between "optimized with preceding context" vs other skip types. Signed-off-by: Jakub Kicinski Reviewed-by: Quentin Monnet --- drivers/net/ethernet/netronome/nfp/bpf/jit.c | 36 ++++++++++--------- drivers/net/ethernet/netronome/nfp/bpf/main.h | 9 +++-- 2 files changed, 26 insertions(+), 19 deletions(-) diff --git a/drivers/net/ethernet/netronome/nfp/bpf/jit.c b/drivers/net/ethernet/netronome/nfp/bpf/jit.c index 323587dee498..054382b9cbe6 100644 --- a/drivers/net/ethernet/netronome/nfp/bpf/jit.c +++ b/drivers/net/ethernet/netronome/nfp/bpf/jit.c @@ -1266,7 +1266,7 @@ wrp_alu64_imm(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta, u64 imm = insn->imm; /* sign extend */ if (skip) { - meta->skip = true; + meta->flags |= FLAG_INSN_SKIP_NOOP; return 0; } @@ -1296,7 +1296,7 @@ wrp_alu32_imm(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta, const struct bpf_insn *insn = &meta->insn; if (skip) { - meta->skip = true; + meta->flags |= FLAG_INSN_SKIP_NOOP; return 0; } @@ -3395,7 +3395,7 @@ static int nfp_fixup_branches(struct nfp_prog *nfp_prog) int err; list_for_each_entry(meta, &nfp_prog->insns, l) { - if (meta->skip) + if (meta->flags & FLAG_INSN_SKIP_MASK) continue; if (BPF_CLASS(meta->insn.code) != BPF_JMP) continue; @@ -3439,7 +3439,7 @@ static int nfp_fixup_branches(struct nfp_prog *nfp_prog) jmp_dst = meta->jmp_dst; - if (jmp_dst->skip) { + if (jmp_dst->flags & FLAG_INSN_SKIP_PREC_DEPENDENT) { pr_err("Branch landing on removed instruction!!\n"); return -ELOOP; } @@ -3689,7 +3689,7 @@ static int nfp_translate(struct nfp_prog *nfp_prog) return nfp_prog->error; } - if (meta->skip) { + if (meta->flags & FLAG_INSN_SKIP_MASK) { nfp_prog->n_translated++; continue; } @@ -3737,10 +3737,10 @@ static void nfp_bpf_opt_reg_init(struct nfp_prog *nfp_prog) /* Programs start with R6 = R1 but we ignore the skb pointer */ if (insn.code == (BPF_ALU64 | BPF_MOV | BPF_X) && insn.src_reg == 1 && insn.dst_reg == 6) - meta->skip = true; + meta->flags |= FLAG_INSN_SKIP_PREC_DEPENDENT; /* Return as soon as something doesn't match */ - if (!meta->skip) + if (!(meta->flags & FLAG_INSN_SKIP_MASK)) return; } } @@ -3755,7 +3755,7 @@ static void nfp_bpf_opt_neg_add_sub(struct nfp_prog *nfp_prog) list_for_each_entry(meta, &nfp_prog->insns, l) { struct bpf_insn insn = meta->insn; - if (meta->skip) + if (meta->flags & FLAG_INSN_SKIP_MASK) continue; if (BPF_CLASS(insn.code) != BPF_ALU && @@ -3829,7 +3829,7 @@ static void nfp_bpf_opt_ld_mask(struct nfp_prog *nfp_prog) if (meta2->flags & FLAG_INSN_IS_JUMP_DST) continue; - meta2->skip = true; + meta2->flags |= FLAG_INSN_SKIP_PREC_DEPENDENT; } } @@ -3869,8 +3869,8 @@ static void nfp_bpf_opt_ld_shift(struct nfp_prog *nfp_prog) meta3->flags & FLAG_INSN_IS_JUMP_DST) continue; - meta2->skip = true; - meta3->skip = true; + meta2->flags |= FLAG_INSN_SKIP_PREC_DEPENDENT; + meta3->flags |= FLAG_INSN_SKIP_PREC_DEPENDENT; } } @@ -4065,7 +4065,8 @@ static void nfp_bpf_opt_ldst_gather(struct nfp_prog *nfp_prog) } head_ld_meta->paired_st = &head_st_meta->insn; - head_st_meta->skip = true; + head_st_meta->flags |= + FLAG_INSN_SKIP_PREC_DEPENDENT; } else { head_ld_meta->ldst_gather_len = 0; } @@ -4098,8 +4099,8 @@ static void nfp_bpf_opt_ldst_gather(struct nfp_prog *nfp_prog) head_ld_meta = meta1; head_st_meta = meta2; } else { - meta1->skip = true; - meta2->skip = true; + meta1->flags |= FLAG_INSN_SKIP_PREC_DEPENDENT; + meta2->flags |= FLAG_INSN_SKIP_PREC_DEPENDENT; } head_ld_meta->ldst_gather_len += BPF_LDST_BYTES(ld); @@ -4124,7 +4125,7 @@ static void nfp_bpf_opt_pkt_cache(struct nfp_prog *nfp_prog) if (meta->flags & FLAG_INSN_IS_JUMP_DST) cache_avail = false; - if (meta->skip) + if (meta->flags & FLAG_INSN_SKIP_MASK) continue; insn = &meta->insn; @@ -4210,7 +4211,7 @@ static void nfp_bpf_opt_pkt_cache(struct nfp_prog *nfp_prog) } list_for_each_entry(meta, &nfp_prog->insns, l) { - if (meta->skip) + if (meta->flags & FLAG_INSN_SKIP_MASK) continue; if (is_mbpf_load_pkt(meta) && !meta->ldst_gather_len) { @@ -4246,7 +4247,8 @@ static int nfp_bpf_replace_map_ptrs(struct nfp_prog *nfp_prog) u32 id; nfp_for_each_insn_walk2(nfp_prog, meta1, meta2) { - if (meta1->skip || meta2->skip) + if (meta1->flags & FLAG_INSN_SKIP_MASK || + meta2->flags & FLAG_INSN_SKIP_MASK) continue; if (meta1->insn.code != (BPF_LD | BPF_IMM | BPF_DW) || diff --git a/drivers/net/ethernet/netronome/nfp/bpf/main.h b/drivers/net/ethernet/netronome/nfp/bpf/main.h index 941277936475..40291aedd895 100644 --- a/drivers/net/ethernet/netronome/nfp/bpf/main.h +++ b/drivers/net/ethernet/netronome/nfp/bpf/main.h @@ -243,6 +243,13 @@ struct nfp_bpf_reg_state { #define FLAG_INSN_IS_JUMP_DST BIT(0) #define FLAG_INSN_IS_SUBPROG_START BIT(1) #define FLAG_INSN_PTR_CALLER_STACK_FRAME BIT(2) +/* Instruction is pointless, noop even on its own */ +#define FLAG_INSN_SKIP_NOOP BIT(3) +/* Instruction is optimized out based on preceding instructions */ +#define FLAG_INSN_SKIP_PREC_DEPENDENT BIT(4) + +#define FLAG_INSN_SKIP_MASK (FLAG_INSN_SKIP_NOOP | \ + FLAG_INSN_SKIP_PREC_DEPENDENT) /** * struct nfp_insn_meta - BPF instruction wrapper @@ -271,7 +278,6 @@ struct nfp_bpf_reg_state { * @n: eBPF instruction number * @flags: eBPF instruction extra optimization flags * @subprog_idx: index of subprogram to which the instruction belongs - * @skip: skip this instruction (optimized out) * @double_cb: callback for second part of the instruction * @l: link on nfp_prog->insns list */ @@ -319,7 +325,6 @@ struct nfp_insn_meta { unsigned short n; unsigned short flags; unsigned short subprog_idx; - bool skip; instr_cb_t double_cb; struct list_head l; From patchwork Sat Dec 29 03:09:21 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 1019295 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=netronome.com Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=netronome-com.20150623.gappssmtp.com header.i=@netronome-com.20150623.gappssmtp.com header.b="CH+faExy"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 43RT8f050lz9s3l for ; Sat, 29 Dec 2018 14:10:10 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730136AbeL2DKH (ORCPT ); Fri, 28 Dec 2018 22:10:07 -0500 Received: from mail-qt1-f173.google.com ([209.85.160.173]:41801 "EHLO mail-qt1-f173.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730116AbeL2DJ7 (ORCPT ); Fri, 28 Dec 2018 22:09:59 -0500 Received: by mail-qt1-f173.google.com with SMTP id l12so25008021qtf.8 for ; Fri, 28 Dec 2018 19:09:57 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=netronome-com.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=0RMxGdn96kDJ6PcTIV1cEN7RYiBzuvSdpJiVJXTtmCM=; b=CH+faExynRPWIiMIDtWNy4Jj76VOWu2Cj+vuqgqA6QgobIQhpzkw0zB5gWYcEhiecz Hd9Mdx1n6vPx3mxdb6fki27tpXelX6IMW3n0BuZgM4J7Coil7U//CReI+oTZhc9iGyLX diY3ggmY20MikE0zxIKm8JW65Kd4lpR1HTUTn+gMoqfTB9qf0SuW8fL8qsSp6XHSEhat qzUbfliZZkfMKCAJA29oXLcYjh+vCXzkaI3D7WX03IhHV0kRtSzIpCIDljSGb/fEOZSm E7Cwf8cDRfBgjq2Ak2xzt/59WHz5CZ4jM+ZMOZlhwrdNnXctz/cHfC/F3xqy4WFjoFe7 jh9Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=0RMxGdn96kDJ6PcTIV1cEN7RYiBzuvSdpJiVJXTtmCM=; b=nleVPzaP8+H8OIlyULANmwFxqFcOma2q38Gfby+N4DuIXK18QE+uKS/N6n9ZkB0hsC UqBYvy05SaqlI4Lu7nyhtLdNdD90Dr9ALOu8YaI3QdqB0URAYuXr1lyCosY8lDG4gZCw SBZ/1KGsrHMpLXJ5an00hEdd2goitcERKgs4897Ih4Jega6FM77u5fRHoMWqa1czmGA3 NDsZdx5hBnWIY5F1INaGYTpkIipQh/oztaLGsSdKtaeV52SmvZ9Sh4VNrr+kzgpOFnYs FmmH/pl9dh68gyFLHbaN/zd0KykGHBiCJOrojB2/j66OZY7i3dsiznuRsyjuRHGYKAjm 3pGA== X-Gm-Message-State: AJcUukfk7Z/JkQVVmKjbeR4UgSDMdOdKx1a21nNH/4hA+WNj3mpasiDh V/JFFD79WqvepO7sZpjHlxNcfg== X-Google-Smtp-Source: ALg8bN6iMbqsDWU/7dJNb8EJFWf+nEBf1uppmBpgd6/oy7YPzZv+6gQCtFBNpMQyULt48vrjIF9nvg== X-Received: by 2002:a0c:878d:: with SMTP id 13mr28301551qvj.8.1546052997375; Fri, 28 Dec 2018 19:09:57 -0800 (PST) Received: from jkicinski-Precision-T1700.netronome.com ([66.60.152.14]) by smtp.gmail.com with ESMTPSA id i26sm14508170qkg.12.2018.12.28.19.09.56 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 28 Dec 2018 19:09:56 -0800 (PST) From: Jakub Kicinski To: alexei.starovoitov@gmail.com, daniel@iogearbox.net Cc: yhs@fb.com, netdev@vger.kernel.org, oss-drivers@netronome.com, Jakub Kicinski Subject: [RFC bpf-next v3 10/12] nfp: bpf: save original program length Date: Fri, 28 Dec 2018 19:09:21 -0800 Message-Id: <20181229030923.4804-11-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.19.2 In-Reply-To: <20181229030923.4804-1-jakub.kicinski@netronome.com> References: <20181229030923.4804-1-jakub.kicinski@netronome.com> MIME-Version: 1.0 Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org Instead of passing env->prog->len around, and trying to adjust for optimized out instructions just save the initial number of instructions in struct nfp_prog. Signed-off-by: Jakub Kicinski Reviewed-by: Quentin Monnet --- drivers/net/ethernet/netronome/nfp/bpf/jit.c | 4 ++-- drivers/net/ethernet/netronome/nfp/bpf/main.h | 6 ++++-- drivers/net/ethernet/netronome/nfp/bpf/offload.c | 3 ++- .../net/ethernet/netronome/nfp/bpf/verifier.c | 16 +++++++--------- 4 files changed, 15 insertions(+), 14 deletions(-) diff --git a/drivers/net/ethernet/netronome/nfp/bpf/jit.c b/drivers/net/ethernet/netronome/nfp/bpf/jit.c index 054382b9cbe6..3308fd92c017 100644 --- a/drivers/net/ethernet/netronome/nfp/bpf/jit.c +++ b/drivers/net/ethernet/netronome/nfp/bpf/jit.c @@ -4327,7 +4327,7 @@ int nfp_bpf_jit(struct nfp_prog *nfp_prog) return ret; } -void nfp_bpf_jit_prepare(struct nfp_prog *nfp_prog, unsigned int cnt) +void nfp_bpf_jit_prepare(struct nfp_prog *nfp_prog) { struct nfp_insn_meta *meta; @@ -4355,7 +4355,7 @@ void nfp_bpf_jit_prepare(struct nfp_prog *nfp_prog, unsigned int cnt) else dst_idx = meta->n + 1 + meta->insn.off; - dst_meta = nfp_bpf_goto_meta(nfp_prog, meta, dst_idx, cnt); + dst_meta = nfp_bpf_goto_meta(nfp_prog, meta, dst_idx); if (pseudo_call) dst_meta->flags |= FLAG_INSN_IS_SUBPROG_START; diff --git a/drivers/net/ethernet/netronome/nfp/bpf/main.h b/drivers/net/ethernet/netronome/nfp/bpf/main.h index 40291aedd895..07879eee3d46 100644 --- a/drivers/net/ethernet/netronome/nfp/bpf/main.h +++ b/drivers/net/ethernet/netronome/nfp/bpf/main.h @@ -462,6 +462,7 @@ struct nfp_bpf_subprog_info { * @subprog_cnt: number of sub-programs, including main function * @map_records: the map record pointers from bpf->maps_neutral * @subprog: pointer to an array of objects holding info about sub-programs + * @n_insns: number of instructions on @insns list * @insns: list of BPF instruction wrappers (struct nfp_insn_meta) */ struct nfp_prog { @@ -494,6 +495,7 @@ struct nfp_prog { struct nfp_bpf_neutral_map **map_records; struct nfp_bpf_subprog_info *subprog; + unsigned int n_insns; struct list_head insns; }; @@ -510,7 +512,7 @@ struct nfp_bpf_vnic { }; bool nfp_is_subprog_start(struct nfp_insn_meta *meta); -void nfp_bpf_jit_prepare(struct nfp_prog *nfp_prog, unsigned int cnt); +void nfp_bpf_jit_prepare(struct nfp_prog *nfp_prog); int nfp_bpf_jit(struct nfp_prog *prog); bool nfp_bpf_supported_opcode(u8 code); @@ -531,7 +533,7 @@ int nfp_net_bpf_offload(struct nfp_net *nn, struct bpf_prog *prog, struct nfp_insn_meta * nfp_bpf_goto_meta(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta, - unsigned int insn_idx, unsigned int n_insns); + unsigned int insn_idx); void *nfp_bpf_relo_for_vnic(struct nfp_prog *nfp_prog, struct nfp_bpf_vnic *bv); diff --git a/drivers/net/ethernet/netronome/nfp/bpf/offload.c b/drivers/net/ethernet/netronome/nfp/bpf/offload.c index f0283854fade..c10aab392cf6 100644 --- a/drivers/net/ethernet/netronome/nfp/bpf/offload.c +++ b/drivers/net/ethernet/netronome/nfp/bpf/offload.c @@ -163,8 +163,9 @@ nfp_prog_prepare(struct nfp_prog *nfp_prog, const struct bpf_insn *prog, list_add_tail(&meta->l, &nfp_prog->insns); } + nfp_prog->n_insns = cnt; - nfp_bpf_jit_prepare(nfp_prog, cnt); + nfp_bpf_jit_prepare(nfp_prog); return 0; } diff --git a/drivers/net/ethernet/netronome/nfp/bpf/verifier.c b/drivers/net/ethernet/netronome/nfp/bpf/verifier.c index 337bb862ec1d..2712ab17d57c 100644 --- a/drivers/net/ethernet/netronome/nfp/bpf/verifier.c +++ b/drivers/net/ethernet/netronome/nfp/bpf/verifier.c @@ -18,15 +18,15 @@ struct nfp_insn_meta * nfp_bpf_goto_meta(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta, - unsigned int insn_idx, unsigned int n_insns) + unsigned int insn_idx) { unsigned int forward, backward, i; backward = meta->n - insn_idx; forward = insn_idx - meta->n; - if (min(forward, backward) > n_insns - insn_idx - 1) { - backward = n_insns - insn_idx - 1; + if (min(forward, backward) > nfp_prog->n_insns - insn_idx - 1) { + backward = nfp_prog->n_insns - insn_idx - 1; meta = nfp_prog_last_meta(nfp_prog); } if (min(forward, backward) > insn_idx && backward > insn_idx) { @@ -629,7 +629,7 @@ int nfp_verify_insn(struct bpf_verifier_env *env, int insn_idx, struct nfp_prog *nfp_prog = env->prog->aux->offload->dev_priv; struct nfp_insn_meta *meta = nfp_prog->verifier_meta; - meta = nfp_bpf_goto_meta(nfp_prog, meta, insn_idx, env->prog->len); + meta = nfp_bpf_goto_meta(nfp_prog, meta, insn_idx); nfp_prog->verifier_meta = meta; if (!nfp_bpf_supported_opcode(meta->insn.code)) { @@ -690,8 +690,7 @@ nfp_assign_subprog_idx_and_regs(struct bpf_verifier_env *env, return 0; } -static unsigned int -nfp_bpf_get_stack_usage(struct nfp_prog *nfp_prog, unsigned int cnt) +static unsigned int nfp_bpf_get_stack_usage(struct nfp_prog *nfp_prog) { struct nfp_insn_meta *meta = nfp_prog_first_meta(nfp_prog); unsigned int max_depth = 0, depth = 0, frame = 0; @@ -726,7 +725,7 @@ nfp_bpf_get_stack_usage(struct nfp_prog *nfp_prog, unsigned int cnt) /* Find the callee and start processing it. */ meta = nfp_bpf_goto_meta(nfp_prog, meta, - meta->n + 1 + meta->insn.imm, cnt); + meta->n + 1 + meta->insn.imm); idx = meta->subprog_idx; frame++; goto process_subprog; @@ -778,8 +777,7 @@ int nfp_bpf_finalize(struct bpf_verifier_env *env) nn = netdev_priv(env->prog->aux->offload->netdev); max_stack = nn_readb(nn, NFP_NET_CFG_BPF_STACK_SZ) * 64; - nfp_prog->stack_size = nfp_bpf_get_stack_usage(nfp_prog, - env->prog->len); + nfp_prog->stack_size = nfp_bpf_get_stack_usage(nfp_prog); if (nfp_prog->stack_size > max_stack) { pr_vlog(env, "stack too large: program %dB > FW stack %dB\n", nfp_prog->stack_size, max_stack); From patchwork Sat Dec 29 03:09:22 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 1019294 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=netronome.com Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=netronome-com.20150623.gappssmtp.com header.i=@netronome-com.20150623.gappssmtp.com header.b="EQEdnB6K"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 43RT8d2Dngz9s3q for ; Sat, 29 Dec 2018 14:10:09 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730132AbeL2DKC (ORCPT ); Fri, 28 Dec 2018 22:10:02 -0500 Received: from mail-qt1-f194.google.com ([209.85.160.194]:38027 "EHLO mail-qt1-f194.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730120AbeL2DKA (ORCPT ); Fri, 28 Dec 2018 22:10:00 -0500 Received: by mail-qt1-f194.google.com with SMTP id p17so25054789qtl.5 for ; Fri, 28 Dec 2018 19:09:59 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=netronome-com.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=NOp6sT6CHytWb1J/7ArxZ4Iyc1CHTEcJJ8Nb2Z8A0lo=; b=EQEdnB6Kk9o8mD/jykh7hpq3rma8lai+AChqEB3MOKTGWIYu+NRU4ZbQGMAE7+CHwa YbJtWpnFstMFjqRcKamccVA7RRLOrJvSj9D1xgfdPsOpG8GjokAnstrHdh7X3AKkfhwR 87qHlv7CYnXxcqDt3KEtK5Fl6MM5HzBGRqmG2VkBU0dNAKkQuxSNVKJKosthCiohHtsH GNJ01mYFnkArLh9F1ntfKaJiV5nFoxOWYkFWf1yEV4dGwyPDJfMLIW48nx45qO37RuMU cE82haEvoo+VMM93ps8HmuIfcHFHrJ1EV6kFFrmt+pPAfa2xG/NlNLp15IZwYOTKTKRw Wn9A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=NOp6sT6CHytWb1J/7ArxZ4Iyc1CHTEcJJ8Nb2Z8A0lo=; b=Wr8gqetGP9yCXT0jbKux0sdvozGYuNhzimhGFi8NSQfOdW8fFxH5uT3U841kBpJU7p SIhryKXXQbrht1dMtbAk/DHJI5dZHza8kCyfkX7p1dFRDZnm7hBhaQ8JAzM+7sDQCEov i6b2wHiVEzyp7kVO9xmhPldzBuEdhcwZPGJZ5DYsIIU/py/1fJRTOJ3DgRFGfW7J+Htn D4+dZd4JWfq5goMooQ19QCJ8OFSc+Rn8/iZ6sP3l8TZWCRVmF2RWd4VeEFHzk4CG+Im7 CCC4VD2xfRL0iZ0vhRIWI5xutJ3HYqKSfv/8Vz9APe+xk7S0BRqKXXs00z6taC5vc9Za AyxA== X-Gm-Message-State: AA+aEWaewVFxr9924H9wCl9LoDlinACp+ohJeXa413mbnyWCOL9J9cc9 DqyZIFzGNNGzRskfIL5RWKRGmQ== X-Google-Smtp-Source: ALg8bN6P143R0OD5vbpUHWs6ph/oe0pjL5+aCksvJb9Y/wdph/oAL3IG0BKu1xsKO9NMb/eBXHcDmA== X-Received: by 2002:ac8:6606:: with SMTP id c6mr27922113qtp.376.1546052998808; Fri, 28 Dec 2018 19:09:58 -0800 (PST) Received: from jkicinski-Precision-T1700.netronome.com ([66.60.152.14]) by smtp.gmail.com with ESMTPSA id i26sm14508170qkg.12.2018.12.28.19.09.57 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 28 Dec 2018 19:09:58 -0800 (PST) From: Jakub Kicinski To: alexei.starovoitov@gmail.com, daniel@iogearbox.net Cc: yhs@fb.com, netdev@vger.kernel.org, oss-drivers@netronome.com, Jakub Kicinski Subject: [RFC bpf-next v3 11/12] nfp: bpf: support optimizing dead branches Date: Fri, 28 Dec 2018 19:09:22 -0800 Message-Id: <20181229030923.4804-12-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.19.2 In-Reply-To: <20181229030923.4804-1-jakub.kicinski@netronome.com> References: <20181229030923.4804-1-jakub.kicinski@netronome.com> MIME-Version: 1.0 Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org Verifier will now optimize out branches to dead code, implement the replace_insn callback to take advantage of that optimization. Signed-off-by: Jakub Kicinski Reviewed-by: Quentin Monnet --- drivers/net/ethernet/netronome/nfp/bpf/main.h | 14 ++++++++ .../net/ethernet/netronome/nfp/bpf/offload.c | 1 + .../net/ethernet/netronome/nfp/bpf/verifier.c | 34 +++++++++++++++++++ 3 files changed, 49 insertions(+) diff --git a/drivers/net/ethernet/netronome/nfp/bpf/main.h b/drivers/net/ethernet/netronome/nfp/bpf/main.h index 07879eee3d46..a33aa7df1979 100644 --- a/drivers/net/ethernet/netronome/nfp/bpf/main.h +++ b/drivers/net/ethernet/netronome/nfp/bpf/main.h @@ -412,6 +412,17 @@ static inline bool is_mbpf_div(const struct nfp_insn_meta *meta) return is_mbpf_alu(meta) && mbpf_op(meta) == BPF_DIV; } +static inline bool is_mbpf_cond_jump(const struct nfp_insn_meta *meta) +{ + u8 op; + + if (BPF_CLASS(meta->insn.code) != BPF_JMP) + return false; + + op = BPF_OP(meta->insn.code); + return op != BPF_JA && op != BPF_EXIT && op != BPF_CALL; +} + static inline bool is_mbpf_helper_call(const struct nfp_insn_meta *meta) { struct bpf_insn insn = meta->insn; @@ -520,6 +531,9 @@ int nfp_verify_insn(struct bpf_verifier_env *env, int insn_idx, int prev_insn_idx); int nfp_bpf_finalize(struct bpf_verifier_env *env); +int nfp_bpf_opt_replace_insn(struct bpf_verifier_env *env, u32 off, + struct bpf_insn *insn); + extern const struct bpf_prog_offload_ops nfp_bpf_dev_ops; struct netdev_bpf; diff --git a/drivers/net/ethernet/netronome/nfp/bpf/offload.c b/drivers/net/ethernet/netronome/nfp/bpf/offload.c index c10aab392cf6..877c1b8f95e2 100644 --- a/drivers/net/ethernet/netronome/nfp/bpf/offload.c +++ b/drivers/net/ethernet/netronome/nfp/bpf/offload.c @@ -592,6 +592,7 @@ int nfp_net_bpf_offload(struct nfp_net *nn, struct bpf_prog *prog, const struct bpf_prog_offload_ops nfp_bpf_dev_ops = { .insn_hook = nfp_verify_insn, .finalize = nfp_bpf_finalize, + .replace_insn = nfp_bpf_opt_replace_insn, .prepare = nfp_bpf_verifier_prep, .translate = nfp_bpf_translate, .destroy = nfp_bpf_destroy, diff --git a/drivers/net/ethernet/netronome/nfp/bpf/verifier.c b/drivers/net/ethernet/netronome/nfp/bpf/verifier.c index 2712ab17d57c..32468e1b1b73 100644 --- a/drivers/net/ethernet/netronome/nfp/bpf/verifier.c +++ b/drivers/net/ethernet/netronome/nfp/bpf/verifier.c @@ -786,3 +786,37 @@ int nfp_bpf_finalize(struct bpf_verifier_env *env) return 0; } + +int nfp_bpf_opt_replace_insn(struct bpf_verifier_env *env, u32 off, + struct bpf_insn *insn) +{ + struct nfp_prog *nfp_prog = env->prog->aux->offload->dev_priv; + struct bpf_insn_aux_data *aux_data = env->insn_aux_data; + struct nfp_insn_meta *meta = nfp_prog->verifier_meta; + + meta = nfp_bpf_goto_meta(nfp_prog, meta, aux_data[off].orig_idx); + nfp_prog->verifier_meta = meta; + + /* conditional jump to jump conversion */ + if (is_mbpf_cond_jump(meta) && + insn->code == (BPF_JMP | BPF_JA | BPF_K)) { + unsigned int tgt_off; + + tgt_off = off + insn->off + 1; + + if (!insn->off) { + meta->jmp_dst = list_next_entry(meta, l); + meta->jump_neg_op = false; + } else if (meta->jmp_dst->n != aux_data[tgt_off].orig_idx) { + pr_vlog(env, "branch hard wire at %d changes target %d -> %d\n", + off, meta->jmp_dst->n, + aux_data[tgt_off].orig_idx); + return -EINVAL; + } + return 0; + } + + pr_vlog(env, "unsupported instruction replacement %hhx -> %hhx\n", + meta->insn.code, insn->code); + return -EINVAL; +} From patchwork Sat Dec 29 03:09:23 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 1019296 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Original-To: patchwork-incoming-netdev@ozlabs.org Delivered-To: patchwork-incoming-netdev@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=netronome.com Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=netronome-com.20150623.gappssmtp.com header.i=@netronome-com.20150623.gappssmtp.com header.b="Xip1trBK"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 43RT8f72pKz9s3q for ; Sat, 29 Dec 2018 14:10:10 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730140AbeL2DKJ (ORCPT ); Fri, 28 Dec 2018 22:10:09 -0500 Received: from mail-qt1-f193.google.com ([209.85.160.193]:46031 "EHLO mail-qt1-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730122AbeL2DKB (ORCPT ); Fri, 28 Dec 2018 22:10:01 -0500 Received: by mail-qt1-f193.google.com with SMTP id e5so25021702qtr.12 for ; Fri, 28 Dec 2018 19:10:00 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=netronome-com.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=1Z1TS2RUMgtRfNBvs/oRkXHlXOMpPmew3MWWNqzkUX4=; b=Xip1trBKQOf+U+oJ+WMPy2m8NS2UxllmUnXRK6qgomN+VrdLGJCBheFejT0/amljB6 u39JVlj00GTkHn5F572tXPAYOTK6v8X+P79nSAAaB7CjYotdSoaWdrYJwDoVTQrdOzpI GyNdsyQu7Vk6MmnbK98sl036HJCVlWDuyVyqifkDjc26n3k2WjxLGKuO10nVzCedliDb zMPhJE1o6CBdVFodehKss2KRuYG7tmNGYF3uIkRE6t4WncH7XBWILrveHgolRCjmZv55 KUD5ZbGop5pmbpRL2u8GquZ98l4AhkRSBGrSbaRwVQcye4ccg3j8do8AVvUXNIxBT/gE R7wg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=1Z1TS2RUMgtRfNBvs/oRkXHlXOMpPmew3MWWNqzkUX4=; b=uMYByYVCB9e1Ne5DpiMY0vmL/udyiJTnuREvaRVtYPSLpSzhS8KS0U0Ie+tg+5vxvx wp2OXvWkrFgp0JLLOedsyrOGd9fZ63EyReoKnZlGvFsFo9zHAeGlPUUl7ST+6zRu/UQ4 z7jFlaMyPtfRZD3ZZvW2/pZkT+nsmngdFkFzbAoZvi4j11bqjwPmyu2BXqNowPIXtpz5 xDWIGImsBtOjzXu0RuRE8XsvxYgV8A58RCbJW9myKp+Tywdzu1vKSRIRgS/QDckoduiW 7TcYIeNK4+eTEWA/MEU3r+XIGw/pBSgGYTE7oJjyKSNp6b+jvX190Rx2bI5NxXnDqQL9 NKxg== X-Gm-Message-State: AJcUukeYdUWeTiUdiSMeBcssBfQrZ6JtMNs8Ttgr13GUJWjaYg/Adlj6 9dUL5vNpnrmm+wYezndOJb5yCw== X-Google-Smtp-Source: AFSGD/WlaINlHdB1B/8BTeVbG1SHoEAo1D0SZucRDYJQeS0zf9h1JURjiIyT09w+vay5aQirqlG4jw== X-Received: by 2002:aed:26e1:: with SMTP id q88mr28062115qtd.148.1546053000196; Fri, 28 Dec 2018 19:10:00 -0800 (PST) Received: from jkicinski-Precision-T1700.netronome.com ([66.60.152.14]) by smtp.gmail.com with ESMTPSA id i26sm14508170qkg.12.2018.12.28.19.09.58 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 28 Dec 2018 19:09:59 -0800 (PST) From: Jakub Kicinski To: alexei.starovoitov@gmail.com, daniel@iogearbox.net Cc: yhs@fb.com, netdev@vger.kernel.org, oss-drivers@netronome.com, Jakub Kicinski Subject: [RFC bpf-next v3 12/12] nfp: bpf: support removing dead code Date: Fri, 28 Dec 2018 19:09:23 -0800 Message-Id: <20181229030923.4804-13-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.19.2 In-Reply-To: <20181229030923.4804-1-jakub.kicinski@netronome.com> References: <20181229030923.4804-1-jakub.kicinski@netronome.com> MIME-Version: 1.0 Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org Add a verifier callback to the nfp JIT to remove the instructions the verifier deemed to be dead. Signed-off-by: Jakub Kicinski Reviewed-by: Quentin Monnet --- drivers/net/ethernet/netronome/nfp/bpf/main.h | 6 ++++- .../net/ethernet/netronome/nfp/bpf/offload.c | 5 ++++ .../net/ethernet/netronome/nfp/bpf/verifier.c | 24 +++++++++++++++++++ 3 files changed, 34 insertions(+), 1 deletion(-) diff --git a/drivers/net/ethernet/netronome/nfp/bpf/main.h b/drivers/net/ethernet/netronome/nfp/bpf/main.h index a33aa7df1979..5813c3e13ebe 100644 --- a/drivers/net/ethernet/netronome/nfp/bpf/main.h +++ b/drivers/net/ethernet/netronome/nfp/bpf/main.h @@ -247,9 +247,12 @@ struct nfp_bpf_reg_state { #define FLAG_INSN_SKIP_NOOP BIT(3) /* Instruction is optimized out based on preceding instructions */ #define FLAG_INSN_SKIP_PREC_DEPENDENT BIT(4) +/* Instruction is optimized by the verifier */ +#define FLAG_INSN_SKIP_VERIFIER_OPT BIT(5) #define FLAG_INSN_SKIP_MASK (FLAG_INSN_SKIP_NOOP | \ - FLAG_INSN_SKIP_PREC_DEPENDENT) + FLAG_INSN_SKIP_PREC_DEPENDENT | \ + FLAG_INSN_SKIP_VERIFIER_OPT) /** * struct nfp_insn_meta - BPF instruction wrapper @@ -533,6 +536,7 @@ int nfp_bpf_finalize(struct bpf_verifier_env *env); int nfp_bpf_opt_replace_insn(struct bpf_verifier_env *env, u32 off, struct bpf_insn *insn); +int nfp_bpf_opt_remove_insns(struct bpf_verifier_env *env, u32 off, u32 cnt); extern const struct bpf_prog_offload_ops nfp_bpf_dev_ops; diff --git a/drivers/net/ethernet/netronome/nfp/bpf/offload.c b/drivers/net/ethernet/netronome/nfp/bpf/offload.c index 877c1b8f95e2..55c7dbf8b421 100644 --- a/drivers/net/ethernet/netronome/nfp/bpf/offload.c +++ b/drivers/net/ethernet/netronome/nfp/bpf/offload.c @@ -220,6 +220,10 @@ static int nfp_bpf_translate(struct bpf_prog *prog) unsigned int max_instr; int err; + /* We depend on dead code elimination succeeding */ + if (prog->aux->offload->opt_failed) + return -EINVAL; + max_instr = nn_readw(nn, NFP_NET_CFG_BPF_MAX_LEN); nfp_prog->__prog_alloc_len = max_instr * sizeof(u64); @@ -593,6 +597,7 @@ const struct bpf_prog_offload_ops nfp_bpf_dev_ops = { .insn_hook = nfp_verify_insn, .finalize = nfp_bpf_finalize, .replace_insn = nfp_bpf_opt_replace_insn, + .remove_insns = nfp_bpf_opt_remove_insns, .prepare = nfp_bpf_verifier_prep, .translate = nfp_bpf_translate, .destroy = nfp_bpf_destroy, diff --git a/drivers/net/ethernet/netronome/nfp/bpf/verifier.c b/drivers/net/ethernet/netronome/nfp/bpf/verifier.c index 32468e1b1b73..36f56eb4cbe2 100644 --- a/drivers/net/ethernet/netronome/nfp/bpf/verifier.c +++ b/drivers/net/ethernet/netronome/nfp/bpf/verifier.c @@ -820,3 +820,27 @@ int nfp_bpf_opt_replace_insn(struct bpf_verifier_env *env, u32 off, meta->insn.code, insn->code); return -EINVAL; } + +int nfp_bpf_opt_remove_insns(struct bpf_verifier_env *env, u32 off, u32 cnt) +{ + struct nfp_prog *nfp_prog = env->prog->aux->offload->dev_priv; + struct bpf_insn_aux_data *aux_data = env->insn_aux_data; + struct nfp_insn_meta *meta = nfp_prog->verifier_meta; + unsigned int i; + + meta = nfp_bpf_goto_meta(nfp_prog, meta, aux_data[off].orig_idx); + + for (i = 0; i < cnt; i++) { + if (WARN_ON_ONCE(&meta->l == &nfp_prog->insns)) + return -EINVAL; + + /* doesn't count if it already has the flag */ + if (meta->flags & FLAG_INSN_SKIP_VERIFIER_OPT) + i--; + + meta->flags |= FLAG_INSN_SKIP_VERIFIER_OPT; + meta = list_next_entry(meta, l); + } + + return 0; +}