From patchwork Wed Sep 11 04:40:17 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yonghong Song X-Patchwork-Id: 13799673 X-Patchwork-Delegate: bpf@iogearbox.net Received: from 66-220-155-178.mail-mxout.facebook.com (66-220-155-178.mail-mxout.facebook.com [66.220.155.178]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 7B21840862 for ; Wed, 11 Sep 2024 04:40:31 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=66.220.155.178 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1726029634; cv=none; b=iB8ymL67Y3F5Bm42Unu3v8ULjPFJVYgNGN6dgRhV1FrK0KWYTCcwYjdQTO5vL62x4nKhGZcS6IFWXOj3mw+Jzg1ivc1+WglbgxzYmOyHXSPWlCRwe6PlKFY/RlsiyoBb9wbRRVzNJw1K8Dq+nZY0VO1wN5CSBIYIvA+00zwTpSQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1726029634; c=relaxed/simple; bh=wmP1+XKfIQT+c6T+nJ5AZHLmvdy4a+5xaCDTXWhz5/M=; h=From:To:Cc:Subject:Date:Message-ID:MIME-Version; b=JEujnTWDN3dw92kWkwvA0Qerj+xJ+y8BXP0EIBENFloIF3FJMOWixBM8u2jTLyEBgk6u6OCxsG7pVLhr036Eyy9xrFAwamiQk/s6jbAReAYqKZjEEFsueGrzvvSBs+UadrIWYvsCCPd4u9n6jh0veFUWOkoC+8DMQq/V7WjNBxw= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=fail (p=none dis=none) header.from=linux.dev; spf=fail smtp.mailfrom=linux.dev; arc=none smtp.client-ip=66.220.155.178 Authentication-Results: smtp.subspace.kernel.org; dmarc=fail (p=none dis=none) header.from=linux.dev Authentication-Results: smtp.subspace.kernel.org; spf=fail smtp.mailfrom=linux.dev Received: by devbig309.ftw3.facebook.com (Postfix, from userid 128203) id D70C18D48E4C; Tue, 10 Sep 2024 21:40:17 -0700 (PDT) From: Yonghong Song To: bpf@vger.kernel.org Cc: Alexei Starovoitov , Andrii Nakryiko , Daniel Borkmann , kernel-team@fb.com, Martin KaFai Lau , Zac Ecob Subject: [PATCH bpf-next 1/2] bpf: Fix a sdiv overflow issue Date: Tue, 10 Sep 2024 21:40:17 -0700 Message-ID: <20240911044017.2261738-1-yonghong.song@linux.dev> X-Mailer: git-send-email 2.43.5 Precedence: bulk X-Mailing-List: bpf@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Patchwork-Delegate: bpf@iogearbox.net Zac Ecob reported a problem where a bpf program may cause kernel crash due to the following error: Oops: divide error: 0000 [#1] PREEMPT SMP KASAN PTI The failure is due to the below signed divide: LLONG_MIN/-1 where LLONG_MIN equals to -9,223,372,036,854,775,808. LLONG_MIN/-1 is supposed to give a positive number 9,223,372,036,854,775,808, but it is impossible since for 64-bit system, the maximum positive number is 9,223,372,036,854,775,807. On x86_64, LLONG_MIN/-1 will cause a kernel exception. On arm64, the result for LLONG_MIN/-1 is LLONG_MIN. So for 64-bit signed divide (sdiv), some additional insns are patched to check LLONG_MIN/-1 pattern. If such a pattern does exist, the result will be LLONG_MIN. Otherwise, it follows normal sdiv operation. [1] https://lore.kernel.org/bpf/tPJLTEh7S_DxFEqAI2Ji5MBSoZVg7_G-Py2iaZpAaWtM961fFTWtsnlzwvTbzBzaUzwQAoNATXKUlt0LZOFgnDcIyKCswAnAGdUF3LBrhGQ=@protonmail.com/ Reported-by: Zac Ecob Signed-off-by: Yonghong Song --- kernel/bpf/verifier.c | 29 ++++++++++++++++++++++++++--- 1 file changed, 26 insertions(+), 3 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index f35b80c16cda..d77f1a05a065 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -20506,6 +20506,7 @@ static int do_misc_fixups(struct bpf_verifier_env *env) insn->code == (BPF_ALU | BPF_DIV | BPF_X)) { bool is64 = BPF_CLASS(insn->code) == BPF_ALU64; bool isdiv = BPF_OP(insn->code) == BPF_DIV; + bool is_sdiv64 = is64 && isdiv && insn->off == 1; struct bpf_insn *patchlet; struct bpf_insn chk_and_div[] = { /* [R,W]x div 0 -> 0 */ @@ -20525,10 +20526,32 @@ static int do_misc_fixups(struct bpf_verifier_env *env) BPF_JMP_IMM(BPF_JA, 0, 0, 1), BPF_MOV32_REG(insn->dst_reg, insn->dst_reg), }; + struct bpf_insn chk_and_sdiv64[] = { + /* Rx sdiv 0 -> 0 */ + BPF_RAW_INSN(BPF_JMP | BPF_JNE | BPF_K, insn->src_reg, + 0, 2, 0), + BPF_ALU32_REG(BPF_XOR, insn->dst_reg, insn->dst_reg), + BPF_JMP_IMM(BPF_JA, 0, 0, 8), + /* LLONG_MIN sdiv -1 -> LLONG_MIN */ + BPF_RAW_INSN(BPF_JMP | BPF_JNE | BPF_K, insn->src_reg, + 0, 6, -1), + BPF_LD_IMM64(insn->src_reg, LLONG_MIN), + BPF_RAW_INSN(BPF_JMP | BPF_JNE | BPF_X, insn->dst_reg, + insn->src_reg, 2, 0), + BPF_MOV64_IMM(insn->src_reg, -1), + BPF_JMP_IMM(BPF_JA, 0, 0, 2), + BPF_MOV64_IMM(insn->src_reg, -1), + *insn, + }; - patchlet = isdiv ? chk_and_div : chk_and_mod; - cnt = isdiv ? ARRAY_SIZE(chk_and_div) : - ARRAY_SIZE(chk_and_mod) - (is64 ? 2 : 0); + if (is_sdiv64) { + patchlet = chk_and_sdiv64; + cnt = ARRAY_SIZE(chk_and_sdiv64); + } else { + patchlet = isdiv ? chk_and_div : chk_and_mod; + cnt = isdiv ? ARRAY_SIZE(chk_and_div) : + ARRAY_SIZE(chk_and_mod) - (is64 ? 2 : 0); + } new_prog = bpf_patch_insn_data(env, i + delta, patchlet, cnt); if (!new_prog) From patchwork Wed Sep 11 04:40:22 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yonghong Song X-Patchwork-Id: 13799674 X-Patchwork-Delegate: bpf@iogearbox.net Received: from 69-171-232-180.mail-mxout.facebook.com (69-171-232-180.mail-mxout.facebook.com [69.171.232.180]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 6128640862 for ; Wed, 11 Sep 2024 04:40:35 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=69.171.232.180 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1726029637; cv=none; b=tg2Gj/boKFYw/zrtKatCKGeDvfPSu9z8Z0FxVxBcRk5BrVsDZZMFT9uyuih30S/5Z8l//FVSkrfShyR37rkkZVLmGxIcb73/UQ5AANYLb7xNtURcZr9kml2F8jjg8+z2lo6gDan7bbYJuufvXIZTOwR1rwIH75auldaEcy0CTMM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1726029637; c=relaxed/simple; bh=R/FLHw0BdYsh5xBYKCad7p6buEuf7UZX1DMA7VuoYqQ=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=I36ghz5Qw5+s9cKxB7GyCJzLssIpmsKSeyHbS486w+IlaRyHb9mbIPEPudq8pPlWGeUyra1kJ7plc77S4fJCjS1GVGDRbSLUBoq81cn7NCbJuqjLpVmUJXEo8R6bAkPxc1kjNDhYkaHKfKZY4Aj6TSObIOQPQXaUJMZ/mfufm0Y= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=fail (p=none dis=none) header.from=linux.dev; spf=fail smtp.mailfrom=linux.dev; arc=none smtp.client-ip=69.171.232.180 Authentication-Results: smtp.subspace.kernel.org; dmarc=fail (p=none dis=none) header.from=linux.dev Authentication-Results: smtp.subspace.kernel.org; spf=fail smtp.mailfrom=linux.dev Received: by devbig309.ftw3.facebook.com (Postfix, from userid 128203) id EF6858D48E66; Tue, 10 Sep 2024 21:40:22 -0700 (PDT) From: Yonghong Song To: bpf@vger.kernel.org Cc: Alexei Starovoitov , Andrii Nakryiko , Daniel Borkmann , kernel-team@fb.com, Martin KaFai Lau Subject: [PATCH bpf-next 2/2] selftests/bpf: Add a couple of tests for potential sdiv overflow Date: Tue, 10 Sep 2024 21:40:22 -0700 Message-ID: <20240911044022.2262427-1-yonghong.song@linux.dev> X-Mailer: git-send-email 2.43.5 In-Reply-To: <20240911044017.2261738-1-yonghong.song@linux.dev> References: <20240911044017.2261738-1-yonghong.song@linux.dev> Precedence: bulk X-Mailing-List: bpf@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Patchwork-Delegate: bpf@iogearbox.net Two subtests are added to exercise the patched code which handles LLONG_MIN/-1. The first subtest will cause kernel exception without previous kernel verifier change. The second subtest exercises part of the patched code logic and the end result is still correct. Translated asm codes are parts of correctness checking and those asm codes also make it easy to understand the patched code in verifier. Signed-off-by: Yonghong Song --- .../selftests/bpf/progs/verifier_sdiv.c | 69 +++++++++++++++++++ 1 file changed, 69 insertions(+) diff --git a/tools/testing/selftests/bpf/progs/verifier_sdiv.c b/tools/testing/selftests/bpf/progs/verifier_sdiv.c index 2a2271cf0294..c9c56008e534 100644 --- a/tools/testing/selftests/bpf/progs/verifier_sdiv.c +++ b/tools/testing/selftests/bpf/progs/verifier_sdiv.c @@ -1,6 +1,7 @@ // SPDX-License-Identifier: GPL-2.0 #include +#include #include #include "bpf_misc.h" @@ -770,6 +771,74 @@ __naked void smod64_zero_divisor(void) " ::: __clobber_all); } +SEC("socket") +__description("SDIV64, overflow, LLONG_MIN/-1") +__success __retval(1) +__arch_x86_64 +__xlated("0: r2 = 0x8000000000000000") +__xlated("2: r3 = -1") +__xlated("3: r4 = r2") +__xlated("4: if r3 != 0x0 goto pc+2") +__xlated("5: w2 ^= w2") +__xlated("6: goto pc+8") +__xlated("7: if r3 != 0xffffffff goto pc+6") +__xlated("8: r3 = 0x8000000000000000") +__xlated("10: if r2 != r3 goto pc+2") +__xlated("11: r3 = -1") +__xlated("12: goto pc+2") +__xlated("13: r3 = -1") +__xlated("14: r2 s/= r3") +__xlated("15: r0 = 0") +__xlated("16: if r2 != r4 goto pc+1") +__xlated("17: r0 = 1") +__xlated("18: exit") +__naked void sdiv64_overflow(void) +{ + asm volatile (" \ + r2 = %[llong_min] ll; \ + r3 = -1; \ + r4 = r2; \ + r2 s/= r3; \ + r0 = 0; \ + if r2 != r4 goto +1; \ + r0 = 1; \ + exit; \ +" : + : __imm_const(llong_min, LLONG_MIN) + : __clobber_all); +} + +SEC("socket") +__description("SDIV64, divisor -1") +__success __retval(-5) +__arch_x86_64 +__xlated("0: r2 = 5") +__xlated("1: r3 = -1") +__xlated("2: if r3 != 0x0 goto pc+2") +__xlated("3: w2 ^= w2") +__xlated("4: goto pc+8") +__xlated("5: if r3 != 0xffffffff goto pc+6") +__xlated("6: r3 = 0x8000000000000000") +__xlated("8: if r2 != r3 goto pc+2") +__xlated("9: r3 = -1") +__xlated("10: goto pc+2") +__xlated("11: r3 = -1") +__xlated("12: r2 s/= r3") +__xlated("13: r0 = r2") +__xlated("14: exit") +__naked void sdiv64_divisor_neg_1(void) +{ + asm volatile (" \ + r2 = 5; \ + r3 = -1; \ + r2 s/= r3; \ + r0 = r2; \ + exit; \ +" : + : __imm_const(llong_min, LLONG_MIN) + : __clobber_all); +} + #else SEC("socket")