From patchwork Fri Dec 7 17:16:18 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jiong Wang X-Patchwork-Id: 1009580 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="P5+921AQ"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 43BJzP2DX1z9s3C for ; Sat, 8 Dec 2018 04:16:33 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726077AbeLGRQb (ORCPT ); Fri, 7 Dec 2018 12:16:31 -0500 Received: from mail-wr1-f65.google.com ([209.85.221.65]:40837 "EHLO mail-wr1-f65.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726045AbeLGRQb (ORCPT ); Fri, 7 Dec 2018 12:16:31 -0500 Received: by mail-wr1-f65.google.com with SMTP id p4so4503605wrt.7 for ; Fri, 07 Dec 2018 09:16:29 -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; bh=xg3ETvI6kWW8T5q/nGI0cczeMf64vAXrDJbgw4glltM=; b=P5+921AQiB/f3YqSQlZxG88q47jtMHGNdnWawLWXYDH7L8oUQfsv4DAJD99lt9wJEZ mKuoGrEipVi+G86f/QuvQUe0zrWrcbO+J1yjqC6HqhMfiZjT8r2XeC9eUJpzEwIKnomq u1riWeXrSyUzQjz/6A1yjw6CxkyttckFmYUdvucEeHd/yL7oDvoByBP7YoQ6paIfy89k RntCqDkXuoS+DHNYSQhLl7O0toUUkg6jzIYJTMuB0gz65Gc4AY9G51AVnCKZgjPQtT8G ZW1u9WYkQiGLMgtdE0uN807NikOpnUe+Yk/tDwhddWSbVJzSDRqAXsL3jTTgfVI6ckPy c1Ew== 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; bh=xg3ETvI6kWW8T5q/nGI0cczeMf64vAXrDJbgw4glltM=; b=VhS33X0u+lG787/BME275eoK91iZwRp0OZlJV/c2r67jm4+XoLxprvKOqVd2AUFSxG ScXhqCCSAk9QJ0JxzCuuPnvBrhbdsoM9vSfasprq2z6vSxMX9OSHVgbbIuVBs7JulAZf s+id+Nr2Qf65qfER57oDtYckSIlhP9FMgc2AMRGGg3IQ5Y6LpwmazTsZzW7JcV4QPffK KIsoMdlziDTJ7iRyViiSV0XNkNkpvz7JzsG7c2HjE6c49C8B6/DfRd1uWxmOvTeFJQ9a /yFkwy5qX6JKJVvN9ZLA6/dpDqPSyRxj34k3VTE1W93Ag7VAzdtbdDiJcUllTpyTCpmg 753g== X-Gm-Message-State: AA+aEWbjafaycMQf0/uQlll6d42flmLWhjjXeizjYp4ZfWhzXYJ/IOS3 oGawF6YyOS/JgT4l6w3aKnFIgA== X-Google-Smtp-Source: AFSGD/WorpJTQ/3xWuJB3vfKf5/hx+dE1WgRemldHytQO9RLRPwYKYs/nd1Vp16utjtaPVgHruTpog== X-Received: by 2002:adf:e983:: with SMTP id h3mr2425500wrm.232.1544202988943; Fri, 07 Dec 2018 09:16:28 -0800 (PST) Received: from cbtest28.netronome.com ([217.38.71.146]) by smtp.gmail.com with ESMTPSA id o15sm3219319wrp.12.2018.12.07.09.16.27 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Fri, 07 Dec 2018 09:16:27 -0800 (PST) From: Jiong Wang To: ast@kernel.org, daniel@iogearbox.net Cc: ecree@solarflare.com, netdev@vger.kernel.org, oss-drivers@netronome.com, Jiong Wang Subject: [PATCH v2 bpf-next] bpf: relax verifier restriction on BPF_MOV | BPF_ALU Date: Fri, 7 Dec 2018 12:16:18 -0500 Message-Id: <1544202978-19548-1-git-send-email-jiong.wang@netronome.com> X-Mailer: git-send-email 2.7.4 Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org Currently, the destination register is marked as unknown for 32-bit sub-register move (BPF_MOV | BPF_ALU) whenever the source register type is SCALAR_VALUE. This is too conservative that some valid cases will be rejected. Especially, this may turn a constant scalar value into unknown value that could break some assumptions of verifier. For example, test_l4lb_noinline.c has the following C code: struct real_definition *dst 1: if (!get_packet_dst(&dst, &pckt, vip_info, is_ipv6)) 2: return TC_ACT_SHOT; 3: 4: if (dst->flags & F_IPV6) { get_packet_dst is responsible for initializing "dst" into valid pointer and return true (1), otherwise return false (0). The compiled instruction sequence using alu32 will be: 412: (54) (u32) r7 &= (u32) 1 413: (bc) (u32) r0 = (u32) r7 414: (95) exit insn 413, a BPF_MOV | BPF_ALU, however will turn r0 into unknown value even r7 contains SCALAR_VALUE 1. This causes trouble when verifier is walking the code path that hasn't initialized "dst" inside get_packet_dst, for which case 0 is returned and we would then expect verifier concluding line 1 in the above C code pass the "if" check, therefore would skip fall through path starting at line 4. Now, because r0 returned from callee has became unknown value, so verifier won't skip analyzing path starting at line 4 and "dst->flags" requires dereferencing the pointer "dst" which actually hasn't be initialized for this path. This patch relaxed the code marking sub-register move destination. For a SCALAR_VALUE, it is safe to just copy the value from source then truncate it into 32-bit. A unit test also included to demonstrate this issue. This test will fail before this patch. This relaxation could let verifier skipping more paths for conditional comparison against immediate. It also let verifier recording a more accurate/strict value for one register at one state, if this state end up with going through exit without rejection and it is used for state comparison later, then it is possible an inaccurate/permissive value is better. So the real impact on verifier processed insn number is complex. But in all, without this fix, valid program could be rejected. From real benchmarking on kernel selftests and Cilium bpf tests, there is no impact on processed instruction number when tests ares compiled with default compilation options. There is slightly improvements when they are compiled with -mattr=+alu32 after this patch. Also, test_xdp_noinline/-mattr=+alu32 now passed verification. It is rejected before this fix. Insn processed before/after this patch: default -mattr=+alu32 Kernel selftest === test_xdp.o 371/371 369/369 test_l4lb.o 6345/6345 5623/5623 test_xdp_noinline.o 2971/2971 rejected/2727 test_tcp_estates.o 429/429 430/430 Cilium bpf === bpf_lb-DLB_L3.o: 2085/2085 1685/1687 bpf_lb-DLB_L4.o: 2287/2287 1986/1982 bpf_lb-DUNKNOWN.o: 690/690 622/622 bpf_lxc.o: 95033/95033 N/A bpf_netdev.o: 7245/7245 N/A bpf_overlay.o: 2898/2898 3085/2947 NOTE: - bpf_lxc.o and bpf_netdev.o compiled by -mattr=+alu32 are rejected by verifier due to another issue inside verifier on supporting alu32 binary. - Each cilium bpf program could generate several processed insn number, above number is sum of them. v1->v2: - Restrict the change on SCALAR_VALUE. - Update benchmark numbers on Cilium bpf tests. Signed-off-by: Jiong Wang --- kernel/bpf/verifier.c | 16 ++++++++++++---- tools/testing/selftests/bpf/test_verifier.c | 13 +++++++++++++ 2 files changed, 25 insertions(+), 4 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 9584438..777720a 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -3583,12 +3583,15 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) return err; if (BPF_SRC(insn->code) == BPF_X) { + struct bpf_reg_state *src_reg = regs + insn->src_reg; + struct bpf_reg_state *dst_reg = regs + insn->dst_reg; + if (BPF_CLASS(insn->code) == BPF_ALU64) { /* case: R1 = R2 * copy register state to dest reg */ - regs[insn->dst_reg] = regs[insn->src_reg]; - regs[insn->dst_reg].live |= REG_LIVE_WRITTEN; + *dst_reg = *src_reg; + dst_reg->live |= REG_LIVE_WRITTEN; } else { /* R1 = (u32) R2 */ if (is_pointer_value(env, insn->src_reg)) { @@ -3596,9 +3599,14 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) "R%d partial copy of pointer\n", insn->src_reg); return -EACCES; + } else if (src_reg->type == SCALAR_VALUE) { + *dst_reg = *src_reg; + dst_reg->live |= REG_LIVE_WRITTEN; + } else { + mark_reg_unknown(env, regs, + insn->dst_reg); } - mark_reg_unknown(env, regs, insn->dst_reg); - coerce_reg_to_size(®s[insn->dst_reg], 4); + coerce_reg_to_size(dst_reg, 4); } } else { /* case: R = imm diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c index 17021d2..18d0b7f 100644 --- a/tools/testing/selftests/bpf/test_verifier.c +++ b/tools/testing/selftests/bpf/test_verifier.c @@ -2936,6 +2936,19 @@ static struct bpf_test tests[] = { .result = ACCEPT, }, { + "alu32: mov u32 const", + .insns = { + BPF_MOV32_IMM(BPF_REG_7, 0), + BPF_ALU32_IMM(BPF_AND, BPF_REG_7, 1), + BPF_MOV32_REG(BPF_REG_0, BPF_REG_7), + BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1), + BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_7, 0), + BPF_EXIT_INSN(), + }, + .result = ACCEPT, + .retval = 0, + }, + { "unpriv: partial copy of pointer", .insns = { BPF_MOV32_REG(BPF_REG_1, BPF_REG_10),