From patchwork Fri Dec 28 00:54:46 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 1019037 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="blLxH0/q"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 43QpDR6PMwz9s55 for ; Fri, 28 Dec 2018 11:56:07 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730790AbeL1Azt (ORCPT ); Thu, 27 Dec 2018 19:55:49 -0500 Received: from mail-qk1-f195.google.com ([209.85.222.195]:33786 "EHLO mail-qk1-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730566AbeL1Azs (ORCPT ); Thu, 27 Dec 2018 19:55:48 -0500 Received: by mail-qk1-f195.google.com with SMTP id o89so11817639qko.0 for ; Thu, 27 Dec 2018 16:55: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=YXfYLv4wO9VWtJO1deLy3wHhS0P8juZmzpEE5ZK5tjE=; b=blLxH0/qZ06gfLMu5PJWFW75PKRvG3X4mTRpJf9RgNEYcqsV2bi+vHQZxRZ//LOdmV PNHL1jCVAt1pOp4INp28XVrpqKHGv6EAaEnl4Da6SA70f3BTU8eIKx46bsLOCNv313L9 J9W5GRyC8uHi9f6m2E9kUip4dbVrHr2UECn5DKwlsKT7Rx6+QNp7OowhDs6lw595sPxP 2BN6GqFpVPD1sM82kwKY9JaXTGRKQTCo6CzxzDoSMGi2QTtjn2v1Pk9WwmIlXynxXtmx qBnoMC2avJ0/NBMEA3J8qMi0OovH6ktb7xyJkFJDOlle5Z1ze577ZyZP8B3ThD7CR6jK CIlg== 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=YpfY8zU1c3Vdg/DJ5NaGhnlk1fJ0gac1kqWkbt8PEsVxgaHXVXo+g+9jcJkenuqZRr nZPLhZOMxJVJ+UI1PrPgPAPfTLkcKyrMKIe8q9beAabD8HhucZG2H3A1nyckTb3rr/cp ctzlgFCbBQOJrsUaeCcZjCBOTz/1f1sydBmB9GqdkKsdNu+OQz84xsUb3LbooATngwdz i6bqnHZbwQc9KRdgOF0wbXLhbdrmEIdlYgK5kEWvrTDgHn7pF/uikuIQKDn3k2O3fDzl EK9Yj/0oXfLZeHmoAZjHcYMN9sUF+Z2QOH10kw2aa073p7Bol8KM1v8RAM/5imSwX5/X Cw5Q== X-Gm-Message-State: AJcUukf6hRmBWyRkAW3uBLTyCF70Ot9owELsgFnbJvd9VubXL6fL3Bpz 1T8oh4uCN7X4jlIJ3FV1ofTwug== X-Google-Smtp-Source: ALg8bN7oE0SmGUpx8ZuI1PB/rKiZkr99ZpKp50bkpxlvnQokizsjFOu7t0Z7CwTOYENyNnU2yhI8kg== X-Received: by 2002:a37:484c:: with SMTP id v73mr22704868qka.196.1545958547444; Thu, 27 Dec 2018 16:55:47 -0800 (PST) Received: from jkicinski-Precision-T1700.netronome.com ([66.60.152.14]) by smtp.gmail.com with ESMTPSA id w81sm23195212qkg.43.2018.12.27.16.55.46 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 27 Dec 2018 16:55: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 v2 01/12] bpf: change parameters of call/branch offset adjustment Date: Thu, 27 Dec 2018 16:54:46 -0800 Message-Id: <20181228005457.9230-2-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.19.2 In-Reply-To: <20181228005457.9230-1-jakub.kicinski@netronome.com> References: <20181228005457.9230-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 Fri Dec 28 00:54:47 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 1019038 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="C3GGbIIb"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 43QpDS4TTXz9s2P for ; Fri, 28 Dec 2018 11:56:08 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730822AbeL1Azv (ORCPT ); Thu, 27 Dec 2018 19:55:51 -0500 Received: from mail-qk1-f193.google.com ([209.85.222.193]:35808 "EHLO mail-qk1-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730787AbeL1Azu (ORCPT ); Thu, 27 Dec 2018 19:55:50 -0500 Received: by mail-qk1-f193.google.com with SMTP id w204so11805203qka.2 for ; Thu, 27 Dec 2018 16:55:49 -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=lOrC23OpRDynYK3EYrNq+d/eNQGDRL3TS4I6wo6O02M=; b=C3GGbIIb/uyO2LQX0ZIaGpBjgN+vPVgsipMjwcSiNDvDidG/E1P9qq6nun0roBlvkc jPu+UWkSFVsxuu4qjdC54BvRHD8eDjrZ0ViGKMeSKL3pMzMP+oCPIL2VAgfVwyljkBOr 1mmMJ5faykrybAflRc55pWF2ecaF9/zqNJwtvuVI+jJSpaEHDes6ujPsYAy9Ay2E1Fma sFRMZZTTKoyrhQ0lPeDNnML8aoqUcHc9ytMdK2ySq3n606DMnoJAHucMn35h8+8SNxrR tJKcvOS/nKwuToTv/gSe5I5xVtoAMqipXZDXRo6Phmvch0wvZKZSSjWK90F8UPLSlzFD fMrg== 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=lOrC23OpRDynYK3EYrNq+d/eNQGDRL3TS4I6wo6O02M=; b=hu1v1tvd38czNAzyc3BrdJIjXv3atKlVcIXKqLso2m+w9c2kdWyiBqm0aY2PJLuYIa rFlfQ4/eucgDfWS08NlDIs8yISsf6fgEvoVuOAcTrd42P2tHNQJpRM5PIly1nmSz+7qO dC9TNOzXvnc8Dn22l46rtq6VhrXWZ9jRbSioLBX2d+/qY9cAYd5RoR4XLwB/xYodyWRA yh+/oDiJkFTYHVmwcaJCC/ltuHPcxJw1SvIFaVZzR6GB95aR2cbhWo2UdwSQO0cOg+xm BwylpNNV+3qq66ocG+vSb/Jp274pLG7D+lmVzkBQRpEEE5p0lcx8GMga7CZfTpLm7d3O cs7Q== X-Gm-Message-State: AJcUukfrI8L5p9EdrrDGBHcxs9p8WCpE1BTNkW1VjY/GlYRHVfX2wANu ho9pdF8qyfA5OXR+8AQC/e7x2A== X-Google-Smtp-Source: ALg8bN4eLVda/j5fE6we88dcgn2oHt++G1bitpqH1woj1tWlYd8gbznmJ614Xu/UZYK+EJGdDHjsgQ== X-Received: by 2002:a37:7e86:: with SMTP id z128mr22428052qkc.20.1545958548849; Thu, 27 Dec 2018 16:55:48 -0800 (PST) Received: from jkicinski-Precision-T1700.netronome.com ([66.60.152.14]) by smtp.gmail.com with ESMTPSA id w81sm23195212qkg.43.2018.12.27.16.55.47 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 27 Dec 2018 16:55:48 -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 v2 02/12] bpf: verifier: hard wire branches to dead code Date: Thu, 27 Dec 2018 16:54:47 -0800 Message-Id: <20181228005457.9230-3-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.19.2 In-Reply-To: <20181228005457.9230-1-jakub.kicinski@netronome.com> References: <20181228005457.9230-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 | 43 ++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 42 insertions(+), 1 deletion(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 71d86e3024ae..567ebe8baab4 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) @@ -6962,7 +6997,8 @@ 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); + is_priv = capable(CAP_SYS_ADMIN); + env->allow_ptr_leaks = is_priv; ret = check_subprogs(env); if (ret < 0) @@ -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 Fri Dec 28 00:54:48 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 1019039 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="rgBV3MzE"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 43QpDT2T19z9s55 for ; Fri, 28 Dec 2018 11:56:09 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730847AbeL1Azw (ORCPT ); Thu, 27 Dec 2018 19:55:52 -0500 Received: from mail-qt1-f194.google.com ([209.85.160.194]:32992 "EHLO mail-qt1-f194.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730799AbeL1Azv (ORCPT ); Thu, 27 Dec 2018 19:55:51 -0500 Received: by mail-qt1-f194.google.com with SMTP id l11so21995635qtp.0 for ; Thu, 27 Dec 2018 16:55: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=8QOkGqTwFZ4XLtTRmEFxuEODfv8vlbU+jRaCufaapuI=; b=rgBV3MzEFb/WtHwhk3lqOv4QBYvZ5n5QpLp/A0tJPsaHFhZegk0cYvgHC6QhJ30lGw Scyo6s8tCpeepwOyE8K3HELHrjysjJFM9h8UVRxqaDa2Ppd4NX+1lIzSj2AMRm+TDoQZ t8Lz1OKoSdC3fZqRczH3EJdKZBEAX9JlgJ2MEzmmZKY5yhaJ+0d4Snb9YI/bBaDw4BiN PnyUVLTmYmQ5/JGAu+T1LctffaAiibTc2YVwaNf1DIIXtzk8ZPB5WyvN57qtlTll5z+X d9FTXUSfvM1jBIZRsNNoK9w+Asi6Og6mv49tMBQ09BFp23uijMAOzZlioVftE+hUOzkd 8siA== 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=8QOkGqTwFZ4XLtTRmEFxuEODfv8vlbU+jRaCufaapuI=; b=MVrbFkHvFKJXuW/fvov09aLH+L5kIQb9UMNvNWv0KoTsCxjzQIo7G4oV1J5PzelsD7 pgRKtBSJewgXVWymCj6l3yKBdxoEvxIBZW/F61qNt4LDX/6MxaHPrY9dZzYmpmZLAXr8 gpAIj2J2nDAeqMG93Ob1znHk/v0hj9Z6XlHfa1CPPVxLIceHg9z2b6MMdPQwgdo8siSK WkkRT/UAsN8mV8Tzylv6GIjmmxplwIWkXtkMXQH4I3iHgvnLCoAxbX8VNiVXaFcrHd6G 2yQt76SWajVpibC3sDqJyLiZJq0rxlPdHNV1pCCQzwUGPwFrfJ5G0wsCKIecPg+DJMhh dnqw== X-Gm-Message-State: AA+aEWZ2UVYwfpPDa2K/THQ50dJs6F5Ya/EIaOOGZfliOyQQVA3swxuh Zh4gBu24U1Ji5OT2/KfweXwHKQ== X-Google-Smtp-Source: ALg8bN7vOzZBBQogtPt+B9S7fl8iWHuQ2cx0a5t6+/CB5PwyZjokS1ue30GnQQ8xnUzDVYEenJ4Awg== X-Received: by 2002:ac8:88:: with SMTP id c8mr24685083qtg.218.1545958550332; Thu, 27 Dec 2018 16:55:50 -0800 (PST) Received: from jkicinski-Precision-T1700.netronome.com ([66.60.152.14]) by smtp.gmail.com with ESMTPSA id w81sm23195212qkg.43.2018.12.27.16.55.48 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 27 Dec 2018 16:55: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 v2 03/12] bpf: verifier: remove dead code Date: Thu, 27 Dec 2018 16:54:48 -0800 Message-Id: <20181228005457.9230-4-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.19.2 In-Reply-To: <20181228005457.9230-1-jakub.kicinski@netronome.com> References: <20181228005457.9230-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 567ebe8baab4..e562b6112871 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 Fri Dec 28 00:54:49 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 1019048 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="x68szPC2"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 43QpDb68hsz9s2P for ; Fri, 28 Dec 2018 11:56:15 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730889AbeL1Azz (ORCPT ); Thu, 27 Dec 2018 19:55:55 -0500 Received: from mail-qk1-f193.google.com ([209.85.222.193]:44182 "EHLO mail-qk1-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730823AbeL1Azw (ORCPT ); Thu, 27 Dec 2018 19:55:52 -0500 Received: by mail-qk1-f193.google.com with SMTP id n12so11782374qkh.11 for ; Thu, 27 Dec 2018 16:55: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=hkpdwz4zXhMrnBDGWIf3+8NPwdPvV39f5cU7rLH4qnQ=; b=x68szPC2TA+9mjDo3Tne4u73jh5PdckUPr2BBw0koIWTam8EDZq/VQEXzpVqBFQeVh K3DwwELaOnctjYZ5N1jJoLS5JoZ4B+i+19vOmM6n6/Oa40Ik9ke+i44ES/kuP9e4niHA XZd0I5nzRT9POBsrMLrQEV/I1hh4pr61nLuvEDkPGXQsftK7Zj7HLSfY7vNDR/8to/br a1g6ddCKlObQ2D5msr460LKdDboK7qsst0FpmV48F3chI7iTsx+OcCHX58fxRKXsx8i+ 44UGa/mulNV5Tq49dtqLzt8P0iOI6GPGXl6zGfiSdQ9j1FM4fwWpyj81R6IAta/TMbwj pSvQ== 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=hkpdwz4zXhMrnBDGWIf3+8NPwdPvV39f5cU7rLH4qnQ=; b=TqiEFWaQy4Sp1d8MtDvPIXgzdGjbpm+FJOZfzpdc3+BHIHP8OJkK0U3fUWh0j9y+3x N1spbseTZ3uR4IULmNjE5YSs0DryL5+U2l9LFvanrZDYr61mO2VSsnDv/nM6LfWqUEnt FiI+erTnDTcTqQo0MzSY+m5pQbMw15NU+lY7O6btzAVTH8MvT9AOySXlYsX1LRKeIoEn s9Wsay9noremDo6lb6QNw6g0Lgul+LTuh7PhdEUrH7oBs8d0mAzpN3xFcPHAQ66048RX YFxvTxe5Ey2QzW1cLCuBFWfoGpvfqmVE1eb4w4aQvqklWsDUJvXD2U7QCgIJacZqQQ78 vi8w== X-Gm-Message-State: AJcUukfVCPGjmXKbUjnqEzdE+yOhZzfEV0/tFlNmkGd679ZGdAKoVEIj TyZhJNiD7LRLLyu12AIozoPJBQ== X-Google-Smtp-Source: ALg8bN4x3KQMZ3ZalV/R+bv0h1NwgK4+MRgYm1HoUKuJYQUtZOSK4v5Uo/IgMq0S2dRbdSpB75172Q== X-Received: by 2002:a37:4d03:: with SMTP id a3mr23246718qkb.181.1545958551760; Thu, 27 Dec 2018 16:55:51 -0800 (PST) Received: from jkicinski-Precision-T1700.netronome.com ([66.60.152.14]) by smtp.gmail.com with ESMTPSA id w81sm23195212qkg.43.2018.12.27.16.55.50 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 27 Dec 2018 16:55: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 v2 04/12] bpf: verifier: remove unconditional branches by 0 Date: Thu, 27 Dec 2018 16:54:49 -0800 Message-Id: <20181228005457.9230-5-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.19.2 In-Reply-To: <20181228005457.9230-1-jakub.kicinski@netronome.com> References: <20181228005457.9230-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 e562b6112871..a92b9eeff79c 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 Fri Dec 28 00:54:50 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 1019040 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="Pw6MHHe2"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 43QpDV0JF2z9s2P for ; Fri, 28 Dec 2018 11:56:10 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730898AbeL1Az4 (ORCPT ); Thu, 27 Dec 2018 19:55:56 -0500 Received: from mail-qk1-f196.google.com ([209.85.222.196]:40306 "EHLO mail-qk1-f196.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730862AbeL1Azy (ORCPT ); Thu, 27 Dec 2018 19:55:54 -0500 Received: by mail-qk1-f196.google.com with SMTP id y16so11796396qki.7 for ; Thu, 27 Dec 2018 16:55:54 -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=Pw6MHHe2obFalDnhEZ3XPLNl0qMCungEGP9+w4KysAQApqtVWAAEeXwAKYaRf7gu91 UAKdUZ2MhlTiao+NkcEelThYkA6CtAyR4qiNm+EggW93Y5wSpTu+Goz4abIqQCypTOHV X84A5m36tT1l42GzAXccQwEk9mOjUot0par1QKP8ldyalrsU8j5U+uBNVIKlh7g3Zvga J6n6GryxHmia1+IM2sg/IuTFe4Yg3GJTTF4lbqnhIyv0u93TCmxXysZuMMHtgWCfyk0q pLae7Sc+GFmDAH4pjBIlXkCsAVOzWTvSdKtvOYjO19yOPi51ZhDJS2qeyn8kcNCTC1aE X7UQ== 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=fPdedKo4vTIr+D4eApjhzLBnnJgxgJ20ktsnu122MfSvyf5SuRt+TAjtsiQPWlxml+ 8byGwekzUMij4OyIDXyZy8PZfGeUhUq2nRYd45fTtLFsbukBjIx1iB6UVwiWjiFLZUkq 4KhDTzHZjvHpXBWegzciZE9VLiUnTeGK8R2TiQTy37J/8MND0ToD/uR3WBnhsE1xq2/w BAAykNkkt0eXiV4OflV0KQ860FOQCiQo1jiavOo9JbfKkavaE/HX2VrTmfzYJS0M9RY+ MnPxeYzg55O8sc3T+0jsjWTo5vPvVZ3MHcQPV7JhIA35MnNaW711A7wadZbql2wFzXJH JbWw== X-Gm-Message-State: AJcUukeJMZ5y8JWIhqQD/9vvELmxtivtPQPA1lJ0iBfpxl/Z9x659T0P tq533aGdPcpglGLqKwKqCW0qPw== X-Google-Smtp-Source: ALg8bN4AuTJz28B8/Ez0CC+UiaHIFHZOyqgXMapWvZqswgHWZBQR1+g7blMAkbksfiBISEXM+kzelQ== X-Received: by 2002:a37:b1c7:: with SMTP id a190mr22658379qkf.94.1545958553289; Thu, 27 Dec 2018 16:55:53 -0800 (PST) Received: from jkicinski-Precision-T1700.netronome.com ([66.60.152.14]) by smtp.gmail.com with ESMTPSA id w81sm23195212qkg.43.2018.12.27.16.55.51 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 27 Dec 2018 16:55: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 v2 05/12] selftests: bpf: add tests for dead code removal Date: Thu, 27 Dec 2018 16:54:50 -0800 Message-Id: <20181228005457.9230-6-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.19.2 In-Reply-To: <20181228005457.9230-1-jakub.kicinski@netronome.com> References: <20181228005457.9230-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 Fri Dec 28 00:54:51 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 1019041 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="REV+IcXY"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 43QpDV5gqxz9s55 for ; Fri, 28 Dec 2018 11:56:10 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730906AbeL1Az4 (ORCPT ); Thu, 27 Dec 2018 19:55:56 -0500 Received: from mail-qk1-f193.google.com ([209.85.222.193]:41963 "EHLO mail-qk1-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730865AbeL1Az4 (ORCPT ); Thu, 27 Dec 2018 19:55:56 -0500 Received: by mail-qk1-f193.google.com with SMTP id 189so11778485qkj.8 for ; Thu, 27 Dec 2018 16:55: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=PVdYvt2LnyVWpyLfZNKdvG0QIKX/4zSLM45aNowLVgo=; b=REV+IcXY4nL6RLWOGcvsgr6Oi0qY90Tafydof9b95oS22CDTsMRo2LvHiPjopJsx6i OjXUoNaFU52uTcYYZnIK8gKVOLcbEFP4FyKyIadBzijM1qVUu2SItV17ceOR/zBjSnZ+ NIDX3tDmN4hxX4HKedh/M5IVBkiEHD4lymAU+n/ba6ZkO0TaREgtIhxL04hy5Pyb66LV RPVam+Oog+ep2nCTWyEBKON+mFhRiHkEtMGWiQHAil9pgY5K+lCQ4ws1zdFrBEMAGDJW +TE32f7SWF23E9EejSA3zW4khedlAmulQc0E4F6L0ZyZjuJTjYiXRkK1VH4to4ELo8Ys ygag== 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=PVdYvt2LnyVWpyLfZNKdvG0QIKX/4zSLM45aNowLVgo=; b=lo1kKelT4y4qY+KWDemlthuIR6rBAX9VC7ikKy2WnoeQZHgjGY3Ycf5cs6embqsoui ziCrJjFTCir3d2+MBw3OSyArA4J0YFsxUjwiU/z8ocVW0JixGMr5C/8VdOJ1AE6KqAq2 nKWymye6G/icwsNRu8npO2uXSYEgGlzaDE3Y8zTKLM3LJ6jEQp8pmEy6utHl5+mOHVbF +ksmoUeZk1twhDMnhY3CqEozaAaTYppjDtWrob9Q+VMu5/VVjaIalsiza4Tkpqb1aefS DLQPBb9Xwf9b6hKhSTZ9IoOLQe6mu5uZ17L/e/5wIo/oBqAfOqeObFGsT+0FO3ICIsU3 Rc5A== X-Gm-Message-State: AJcUukdhtPi3jtjlueXjjFe3FNBZAQa6n53MJje5C1RZkuY31gmZl/rh rK66nqF82YwbryZqskf4k7wB7Q== X-Google-Smtp-Source: ALg8bN69+1AumENNlHU7/pPiYOOfruLFpW5gQ1ckbFbKacEsIY13JuLpV6RRJ26byDikycXa6j4hEw== X-Received: by 2002:a37:9f46:: with SMTP id i67mr22609498qke.331.1545958554696; Thu, 27 Dec 2018 16:55:54 -0800 (PST) Received: from jkicinski-Precision-T1700.netronome.com ([66.60.152.14]) by smtp.gmail.com with ESMTPSA id w81sm23195212qkg.43.2018.12.27.16.55.53 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 27 Dec 2018 16:55: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 v2 06/12] bpf: verifier: record original instruction index Date: Thu, 27 Dec 2018 16:54:51 -0800 Message-Id: <20181228005457.9230-7-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.19.2 In-Reply-To: <20181228005457.9230-1-jakub.kicinski@netronome.com> References: <20181228005457.9230-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 a92b9eeff79c..dea4f70250c8 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 Fri Dec 28 00:54:52 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 1019042 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="XvhMXDqg"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 43QpDW3r4Mz9s2P for ; Fri, 28 Dec 2018 11:56:11 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730927AbeL1A4A (ORCPT ); Thu, 27 Dec 2018 19:56:00 -0500 Received: from mail-qt1-f194.google.com ([209.85.160.194]:37574 "EHLO mail-qt1-f194.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730905AbeL1Az5 (ORCPT ); Thu, 27 Dec 2018 19:55:57 -0500 Received: by mail-qt1-f194.google.com with SMTP id t33so21947771qtt.4 for ; Thu, 27 Dec 2018 16:55: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=dHNZnjxGFLfgzKdsP8xSfdUYrdbHcQvkoXGNwi2R2PI=; b=XvhMXDqgF5Gi2SATpA9x9BD42PH3ZcmTeTM/Mj9a8hukjVCvjWGBCyGaTkiEbJNrI7 QPwnwb7jHoY4XvGXafPz/m7wJ+CARINg0gO7t6kRqI8o6ooUyZ1amQggpnGIPv21gTKS bZyO24ggUeovQGeWjjRmGWNtH0J92AyHH+ychI9rLewyBmmMSM20oslL2If2UE2BfTw6 jEt9x85rM8w6GDbQsIbvnl5UQWtJoGUOULeuuk8S8zS2LWGt8ctiSXSKytAjJKzCcyc6 xjTGLNe4kScJODD17rm2V6NswlLPjJgeMrVaSCPIQrLi5aCvwKqtzoHGdvCo+2IKEsfx kVgw== 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=dHNZnjxGFLfgzKdsP8xSfdUYrdbHcQvkoXGNwi2R2PI=; b=Kp2fGDj4QJr80L4WX2h68XrvAfkmxRZKup+SgtRhsZa2M/5kg87JMOe5E55EN+LRDS M8zwmj9Ar4cNZBfFNFVtAc6vtbeZ/3JlQHOFtptx1j9OEXSbBd34n8fL5kmqOcPIckhC YtJxisnYUk3MhNHDDA2mTK016grciKYpCcwkckxr2Q27G7KhVl28xxXIxBnnokeLZdtp JNKlqO0y2XlFK/xf6Uv1+mfXGbVTH3PfSLg/rdvUU2Y/5jzG8K7OLLOv4lHwlpS2+aS5 i88ZjYgY7kNLlxNX1QugoyF3aY+W+GuhNdz/ZXvQi09E62HpMMzefJdrh9oDamjh2S7d kLgg== X-Gm-Message-State: AA+aEWbs3Jk3j7WwABm6gZ/HzprzFSgYtIlmDXwoTbQ/f+fv5yt2hfgz YvXGu7FbUAL48FDTWbZ2WYD8ew== X-Google-Smtp-Source: AFSGD/XpTpyCW36GkbbT6FaLVD9agWuSMe2KcIz0lu9rDoUn7u0f+ZN3NIhjkP+Xw0ifkDw10uf5sQ== X-Received: by 2002:ac8:21aa:: with SMTP id 39mr24672566qty.122.1545958556142; Thu, 27 Dec 2018 16:55:56 -0800 (PST) Received: from jkicinski-Precision-T1700.netronome.com ([66.60.152.14]) by smtp.gmail.com with ESMTPSA id w81sm23195212qkg.43.2018.12.27.16.55.54 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 27 Dec 2018 16:55: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 v2 07/12] bpf: notify offload JITs about optimizations Date: Thu, 27 Dec 2018 16:54:52 -0800 Message-Id: <20181228005457.9230-8-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.19.2 In-Reply-To: <20181228005457.9230-1-jakub.kicinski@netronome.com> References: <20181228005457.9230-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 dea4f70250c8..0ee89538d77d 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 Fri Dec 28 00:54:53 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 1019047 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="MaWKf7M+"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 43QpDb1Bxgz9s55 for ; Fri, 28 Dec 2018 11:56:15 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730919AbeL1Az7 (ORCPT ); Thu, 27 Dec 2018 19:55:59 -0500 Received: from mail-qk1-f193.google.com ([209.85.222.193]:38809 "EHLO mail-qk1-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730865AbeL1Az6 (ORCPT ); Thu, 27 Dec 2018 19:55:58 -0500 Received: by mail-qk1-f193.google.com with SMTP id a1so11800655qkc.5 for ; Thu, 27 Dec 2018 16:55:58 -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=MaWKf7M+e+Z/jXzZZ+JjJxw0x/6e0osnUk5uUmII7FmiCkbRaj8HEAq+1BzgTNZWrM pU+O9lC95irgpflM11Y7A3Rvo3MTazj7bFvmmDNbUAWbGXPLpmEwbbaiVDFpSPt+ELCP bwKpTu1RGH179KdWXJzQxiq1iVWXfgh4XjX32TVCv+ssZ4Vbi16hX5a5meqzIKh5gZI5 1FWUBNgx7e0YY13zR0Jqz4XfzOqQDcVCq293s23QDnc7M8sSfBvJcbkvw75Jdu72d2iI NZHYZbBj0np9n9OeLijwCoNKhKsWJ7+jbBqLBcBhfFhBuEIZMLvBM7qB9fqkk/Ke3IPc 2NCA== 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=XMDSsHaNvq7aySn7UqB0QCWoAJD4ypj2uM8flH49ScTlujjpUhcPmUsh79G07Stu7I 7R2Si0Q8oAumuT225djkK8uAXnfLBCuQNpzPnFld1/Y+NlFbivTLucGApq6RIo0HmYYi sihjLV7lU512u8B6oyrURmom0LhyZm//WOVVztdv+O8awbRFONnAAfi/rqE7Hp/kbBiu w9AWvLBCWQdOxRqtyEzgOV2wK+tPUpazTCwvqO0uoWvd8M5qq7E+qR6Lc0lFmAAS5RXg Net5VIyRbDP4dpR4FXQP82ZRYRo+b0VHtzWgyzSfTcZws7YdV2IZ9aP/X0FrrqBbMqZ6 D12Q== X-Gm-Message-State: AJcUukcX7Fc9xN/FtmFuPUEGelDOOrkprNqcB4e+yiJqc0jKtn5ACdbi Coj3FHVAocHHcrkgHl7duWGN3A== X-Google-Smtp-Source: ALg8bN65ANjP1y/pUwgwPFGE/HXoG9h7SAbqAvLowqFppXj47bl1nYJrOy0TnvSYFAQvGH36GCgzlA== X-Received: by 2002:a37:8c04:: with SMTP id o4mr22378221qkd.165.1545958557579; Thu, 27 Dec 2018 16:55:57 -0800 (PST) Received: from jkicinski-Precision-T1700.netronome.com ([66.60.152.14]) by smtp.gmail.com with ESMTPSA id w81sm23195212qkg.43.2018.12.27.16.55.56 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 27 Dec 2018 16:55:57 -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 v2 08/12] nfp: bpf: don't use instruction number for jump target Date: Thu, 27 Dec 2018 16:54:53 -0800 Message-Id: <20181228005457.9230-9-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.19.2 In-Reply-To: <20181228005457.9230-1-jakub.kicinski@netronome.com> References: <20181228005457.9230-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 Fri Dec 28 00:54:54 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 1019043 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="dWw/bCpe"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 43QpDX1m0fz9s55 for ; Fri, 28 Dec 2018 11:56:12 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730935AbeL1A4C (ORCPT ); Thu, 27 Dec 2018 19:56:02 -0500 Received: from mail-qt1-f195.google.com ([209.85.160.195]:43364 "EHLO mail-qt1-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730924AbeL1A4A (ORCPT ); Thu, 27 Dec 2018 19:56:00 -0500 Received: by mail-qt1-f195.google.com with SMTP id i7so21939001qtj.10 for ; Thu, 27 Dec 2018 16:55: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=3rZXzgyy1JJNg/THmYA5WRz8V3LXcQh3i0TaslLrNkM=; b=dWw/bCpebAEffBnwDfTmuaCpqp9hP2D0Rmfgy++KM603oZGKJ89U/4G4mqhxj8t8je 403wLH1y3hebFH7J4xvHyR1z2s/3tk/ryAuHcDUpxuGihDCYJwcF57XbwPVMfZ4mR8py olzbYrFfYE/rqCoHEjLSB3Q9rKUuhUBB+x2XDHPKyFs5on73o4UVQ01a7hAYNsNtwhrs 5wydiDFcvZjVViRPwcUC07amgN+JlsWa/fs1nG8LmMAIH26yt7VizACRuZmlWlKYnnya liSoKhk43NO0DAgisOTCo+ejtott4X1s3N79Sn2C73PpaFLEQi2ZSvfFW+sP8lMG9x6y Go5Q== 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=kFZtljPQQrCoSG4b2YPITV/r45vl28+E05mdablCz9FSyCOQIzwyaLnQ8UHjjlYO3s vDM4cXYedeaUl1cSlavge8IzUCKUU9d8oMhn8qRjFlFLoJGkS+ofTYtznIjc4LAOae4Z 99M/3+OSU2TA9rCi42AcOdX6/VTBJ4s1K58aI5h576vdAc2pF9498xzjCRW+fdIQo9xG /Roi0BKtSJYDzzS0VQlFM9GH1lBYyl9TIKpoheD68epREPPBfk9N/azll4KRMWG5WoD0 Y2CGHRE/Q6CebnGtLTjB/pWvdAhFYBiFP4cKuBlVF/Y5bXAxRas+U0F6jftQS0B1Q5im SLXA== X-Gm-Message-State: AA+aEWZoqCwBKMFoxYDVGrneNXuRmKcC00jBE5u+rSEot4ok51bzvQXH Nn9b3UCJA/7eQT5lse8r40PLnA== X-Google-Smtp-Source: ALg8bN5rH8G4UzrsWrS7vl67r+A3WpWkooB90cmu1XC8FN46RbAqxx5NpSXXdWfZMmCZbO+CBYbWzQ== X-Received: by 2002:ac8:42c1:: with SMTP id g1mr24505057qtm.118.1545958559232; Thu, 27 Dec 2018 16:55:59 -0800 (PST) Received: from jkicinski-Precision-T1700.netronome.com ([66.60.152.14]) by smtp.gmail.com with ESMTPSA id w81sm23195212qkg.43.2018.12.27.16.55.57 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 27 Dec 2018 16:55: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 v2 09/12] nfp: bpf: split up the skip flag Date: Thu, 27 Dec 2018 16:54:54 -0800 Message-Id: <20181228005457.9230-10-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.19.2 In-Reply-To: <20181228005457.9230-1-jakub.kicinski@netronome.com> References: <20181228005457.9230-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 Fri Dec 28 00:54:55 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 1019044 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="mDNkkvRF"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 43QpDX6g27z9s2P for ; Fri, 28 Dec 2018 11:56:12 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730942AbeL1A4D (ORCPT ); Thu, 27 Dec 2018 19:56:03 -0500 Received: from mail-qt1-f179.google.com ([209.85.160.179]:43612 "EHLO mail-qt1-f179.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730905AbeL1A4C (ORCPT ); Thu, 27 Dec 2018 19:56:02 -0500 Received: by mail-qt1-f179.google.com with SMTP id i7so21939076qtj.10 for ; Thu, 27 Dec 2018 16:56:01 -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=mDNkkvRFOEr3bAniKMv9Z/J87UCjChwzADYTTO+RZijQdIqEBoGRiOpRKwbCP8eq4Q G4by4EzLco+8frLJu4Q1w3MYX6ALPYO+hVadUQ2sDHDilAVzsCTwZGpdopFnmphA71zg AccLsX18rSqSZwefhljILFRlQKsm+YLmOiCvr9HtirR1u2YjG+105w0tV8F0EuhF+osh 7AFHPoQNVcUs3vjIwqxEXjLoMwoFME1cxdMua2rqAqfR5aQurhvy9A6Jfdyw9Nnr2fdD juBkQmc1qtwn4+J4yx20O9r2CHGwjTYwN+8EAmHuDsEk0fSQVNRdJY7xhRGdUKJFLCht gRlA== 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=mKC2JvCRASApl12606BF5xCPjrjGCNhj4bBPL3PQ4M9ElpRLSeCCMTsEGmQ+ijqXZK VbXWs/5GP/1zdID/JE289jdbIk88d4HDTLr37k/L0SPb9g8ZvcosGNlWGE7qHxg801gf nzA39EHN/2YcbYfMWXG++Exx2ic2kFQChrXFbCNLgxifV0clD7YUIyBdMko67lDjeQ3s pJDKtgEAyZz59yz67zHPID0c0ym5yvGKrqu8fTVIz7EVXhlczsKOi46XPmznLze0iq+Y JG9QkYg8qZv5zFZ5/bd7v3zFXCSfgSE/wqAFmIWIwjdR/ESMFG6QE9+Pn7XLbMIf5cbw YPZQ== X-Gm-Message-State: AA+aEWabJO0EfJahZONu/6N5zMYGl7jvHG0p+66tkPeEEXuYZlQI47Ap AaD9nBdYV0dRj34iS3WEvdu3ng== X-Google-Smtp-Source: ALg8bN7iktFYb2tJEpv7oMeKGMX9X+vOK8greJMRXwHSu9PnNsN6ixPugAZ1rD936nfgpnZHJTfKJQ== X-Received: by 2002:ac8:203:: with SMTP id k3mr24919113qtg.64.1545958560748; Thu, 27 Dec 2018 16:56:00 -0800 (PST) Received: from jkicinski-Precision-T1700.netronome.com ([66.60.152.14]) by smtp.gmail.com with ESMTPSA id w81sm23195212qkg.43.2018.12.27.16.55.59 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 27 Dec 2018 16:56:00 -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 v2 10/12] nfp: bpf: save original program length Date: Thu, 27 Dec 2018 16:54:55 -0800 Message-Id: <20181228005457.9230-11-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.19.2 In-Reply-To: <20181228005457.9230-1-jakub.kicinski@netronome.com> References: <20181228005457.9230-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 Fri Dec 28 00:54:56 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 1019045 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="iMrWWbqm"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 43QpDY5VDRz9s55 for ; Fri, 28 Dec 2018 11:56:13 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730953AbeL1A4G (ORCPT ); Thu, 27 Dec 2018 19:56:06 -0500 Received: from mail-qt1-f195.google.com ([209.85.160.195]:43371 "EHLO mail-qt1-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730939AbeL1A4E (ORCPT ); Thu, 27 Dec 2018 19:56:04 -0500 Received: by mail-qt1-f195.google.com with SMTP id i7so21939126qtj.10 for ; Thu, 27 Dec 2018 16:56:02 -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=iMrWWbqmOIzAXzd15H7ioXdFebh3QGOhjEVL5haBklALHr/16IxUatMh96h9Qz8i3q IvDywtm7SvaUWNGgdCLeqY16eVtS0neV6Q8rIWThVilQ1H3RWeIK/7pI76pF8TxsrH6c HhfI9ljfDMFeBvuhA9w4c3gFnctpuxfvQwXYwWr06ojcOxFPW27Bp7Z73/iQtNrSWVgZ zcntZwITTBXC/QaH7a6FqMpd33tysmf/oOjv1GL2GuiVqpIh1YGiBZUcMvSVuI2HPLbQ Bso5BauJp4PieY82P2SMU68eq+SgXQv+UhmImeUK4597pT124u6xkErJYdmbxYnPrv6B YPlQ== 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=CBciKfYb6csLKu4SV5203pI589V0whH/+ia8wrApH9rZ7XFCvdtpGS/wCQBSPtUOXP QqD0gxaeREMigGI7qFxB0WeX4fxJ/CxvmGHb66VQLgtxFhWJXQo2HgS8xFzs1Oq6qL0x j2Diut+uuBlN1L6nZmfclvrokGtTYfjr1iiDX/rfNxFkFI/IPL6qLmthI2oORytEJZ+k J+MgIjyvUF0UUpnW/GPbnUOAYw/oxL7e6QkTsahxdzaLWOsZp7X4or/HzTqA1eQ/isDU R0MWaIcmLE0HRCKb9rf8iLxEpHYtB3dN3IOIRzl1NSEHwZeAkLGJcf8bmn0JASa5XQxk VTFQ== X-Gm-Message-State: AA+aEWbVjWCIBys71XU/cqqjtLnl9VDFknNUDsvTYgcvTZYDSqRC8HeX VUBtDRJvNbHG3edjSLbmjg5v2A== X-Google-Smtp-Source: ALg8bN6NUKJ1Z5eDgkp+QEjIm34csU27NfZOu7VmSmJxTCF7EVW0cQMIt/ld59ubg2O+/0EjH4NqJw== X-Received: by 2002:ac8:4595:: with SMTP id l21mr24668488qtn.124.1545958562451; Thu, 27 Dec 2018 16:56:02 -0800 (PST) Received: from jkicinski-Precision-T1700.netronome.com ([66.60.152.14]) by smtp.gmail.com with ESMTPSA id w81sm23195212qkg.43.2018.12.27.16.56.00 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 27 Dec 2018 16:56:01 -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 v2 11/12] nfp: bpf: support optimizing dead branches Date: Thu, 27 Dec 2018 16:54:56 -0800 Message-Id: <20181228005457.9230-12-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.19.2 In-Reply-To: <20181228005457.9230-1-jakub.kicinski@netronome.com> References: <20181228005457.9230-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 Fri Dec 28 00:54:57 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Kicinski X-Patchwork-Id: 1019046 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="oEnSNvaS"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 43QpDZ3MZ1z9s2P for ; Fri, 28 Dec 2018 11:56:14 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1730964AbeL1A4I (ORCPT ); Thu, 27 Dec 2018 19:56:08 -0500 Received: from mail-qt1-f195.google.com ([209.85.160.195]:46237 "EHLO mail-qt1-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730905AbeL1A4F (ORCPT ); Thu, 27 Dec 2018 19:56:05 -0500 Received: by mail-qt1-f195.google.com with SMTP id y20so21929372qtm.13 for ; Thu, 27 Dec 2018 16:56:04 -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=oEnSNvaSwF8cWqpZPUVAd8RVMGIYUsKYYPOxpj9n1Lob1R3sErCvy3f5kMNc/qApM4 3Wd9Pc2dbrOMpGk5XdAyyJehx4cUwY83OpqzE0RJvIVW/ZgerG5IQ1ig4PcW6FNzR+ry gfN4c+cn36AdKkQVyPw+9XNapZ9v+wQtZ9Q+VjFFyyP5XVzkOTK/1TXpd0oi30khKBWg sWvZe9BTTl7dZChHPs2EQSB4aHrsvC8t8p7QPuLLAgKNzVGgQhATuDHHCjsWxfUU3pnz nu8ISHX76p3IsXMrN4RXGd1qvYV8HjcuA0oV0/OJrFhQuFLyxfC5eE+EYj5rEMDUoN+f Z5HA== 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=kHbnlChOaCymCArpbbuzEGS95e2eMTfipovDFHudmI2+SjU95S6UOlutsMryxNwGcY G5t7R+ob8u6zdoD0/4IxjKqNuRU4ANn8uJlws/W7Uv2cUsqHcCG4SAMq5LJQe71F8tRK B5oc8T6BtdceFxRMkQ+8JX50Aq43SwtQzn1jy7EpGi62lm2zhWuV8Op0K7gLI1d9jCNn M1Sdc7MGL7uPFp88SWBYz/DB/DVroPHQhWwt3d4Kl9Pn79RsvnHmaucFaJGg5+9c5tn6 qJuop60XN0tNPFaLuMAw3iWecFPmMEu+Fy8OBWRUPPagOW0iXxacWoFUslDLxhvRFrAL qUiA== X-Gm-Message-State: AA+aEWbYPErdbEdcaWM7bAnmtCpgJj5OUKMYLqINW2RJk7eqhisdjf2o m9cyMGVD6RKs886uTDD9BzIVLQ== X-Google-Smtp-Source: ALg8bN4P/4eJhTW6W3JO9h+6E1vi35MDi+vroANB+lCs4+bHAN7Lur5U2GXMbgjhEpWgFv4A1fTfwQ== X-Received: by 2002:ac8:7201:: with SMTP id a1mr24113260qtp.291.1545958563897; Thu, 27 Dec 2018 16:56:03 -0800 (PST) Received: from jkicinski-Precision-T1700.netronome.com ([66.60.152.14]) by smtp.gmail.com with ESMTPSA id w81sm23195212qkg.43.2018.12.27.16.56.02 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 27 Dec 2018 16:56:03 -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 v2 12/12] nfp: bpf: support removing dead code Date: Thu, 27 Dec 2018 16:54:57 -0800 Message-Id: <20181228005457.9230-13-jakub.kicinski@netronome.com> X-Mailer: git-send-email 2.19.2 In-Reply-To: <20181228005457.9230-1-jakub.kicinski@netronome.com> References: <20181228005457.9230-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; +}