From patchwork Thu Mar 30 05:56:00 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yonghong Song X-Patchwork-Id: 13193406 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 23350C761AF for ; Thu, 30 Mar 2023 05:56:21 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229919AbjC3F4T (ORCPT ); Thu, 30 Mar 2023 01:56:19 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:52402 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229925AbjC3F4S (ORCPT ); Thu, 30 Mar 2023 01:56:18 -0400 Received: from mx0a-00082601.pphosted.com (mx0a-00082601.pphosted.com [67.231.145.42]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id CCC935B8E for ; Wed, 29 Mar 2023 22:56:09 -0700 (PDT) Received: from pps.filterd (m0044010.ppops.net [127.0.0.1]) by mx0a-00082601.pphosted.com (8.17.1.19/8.17.1.19) with ESMTP id 32U0B3Ju003930 for ; Wed, 29 Mar 2023 22:56:09 -0700 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=fb.com; h=from : to : cc : subject : date : message-id : content-type : content-transfer-encoding : mime-version; s=facebook; bh=goFsdJ5l/64dPrBtRd9UXqUAtaNzQVbA2rVQ/PAQceo=; b=k8U+NcIlwVDFc8nTU5HB6oLu35d7FnFcBc8YgIE/IgnWsj4t+L9lbzWVDrb/+X3r3/il iwPTflDTd1n9hoeiYkD+0yRnq+vZ8f/nKMFLi8/tF4tlCmEKnJ87GL2jkWMnNDFk5xKi Yw+uP4zu57HNvRF+O+o4kGyXNXM+OaFa0/M= Received: from mail.thefacebook.com ([163.114.132.120]) by mx0a-00082601.pphosted.com (PPS) with ESMTPS id 3pmyn5sgub-2 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT) for ; Wed, 29 Mar 2023 22:56:09 -0700 Received: from twshared8568.05.ash9.facebook.com (2620:10d:c085:208::11) by mail.thefacebook.com (2620:10d:c085:21d::4) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2507.17; Wed, 29 Mar 2023 22:56:08 -0700 Received: by devbig309.ftw3.facebook.com (Postfix, from userid 128203) id 17DA51BA2D6F8; Wed, 29 Mar 2023 22:56:00 -0700 (PDT) From: Yonghong Song To: CC: Alexei Starovoitov , Andrii Nakryiko , Daniel Borkmann , , Martin KaFai Lau Subject: [PATCH bpf-next 0/7] bpf: Improve verifier for cond_op and spilled loop index variables Date: Wed, 29 Mar 2023 22:56:00 -0700 Message-ID: <20230330055600.86870-1-yhs@fb.com> X-Mailer: git-send-email 2.34.1 X-FB-Internal: Safe X-Proofpoint-GUID: O-knJl57xAYpfeJWDR1VDiAhZcauxJWp X-Proofpoint-ORIG-GUID: O-knJl57xAYpfeJWDR1VDiAhZcauxJWp X-Proofpoint-UnRewURL: 0 URL was un-rewritten MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.254,Aquarius:18.0.942,Hydra:6.0.573,FMLib:17.11.170.22 definitions=2023-03-30_02,2023-03-30_01,2023-02-09_01 Precedence: bulk List-ID: X-Mailing-List: bpf@vger.kernel.org X-Patchwork-Delegate: bpf@iogearbox.net LLVM commit [1] introduced hoistMinMax optimization like (i < VIRTIO_MAX_SGS) && (i < out_sgs) to upper = MIN(VIRTIO_MAX_SGS, out_sgs) ... i < upper ... and caused the verification failure. Commit [2] workarounded the issue by adding some bpf assembly code to prohibit the above optimization. This patch improved verifier such that verification can succeed without the above workaround. Without [2], the current verifier will hit the following failures: ... 119: (15) if r1 == 0x0 goto pc+1 The sequence of 8193 jumps is too complex. verification time 525829 usec stack depth 64 processed 156616 insns (limit 1000000) max_states_per_insn 8 total_states 1754 peak_states 1712 mark_read 12 -- END PROG LOAD LOG -- libbpf: prog 'trace_virtqueue_add_sgs': failed to load: -14 libbpf: failed to load object 'loop6.bpf.o' ... The failure is due to verifier inadequately handling ' ' which will go through both pathes and generate the following verificaiton states: ... 89: (07) r2 += 1 ; R2_w=5 90: (79) r8 = *(u64 *)(r10 -48) ; R8_w=scalar() R10=fp0 91: (79) r1 = *(u64 *)(r10 -56) ; R1_w=scalar(umax=5,var_off=(0x0; 0x7)) R10=fp0 92: (ad) if r2 < r1 goto pc+41 ; R0_w=scalar() R1_w=scalar(umin=6,umax=5,var_off=(0x4; 0x3)) R2_w=5 R6_w=scalar(id=385) R7_w=0 R8_w=scalar() R9_w=scalar(umax=21474836475,var_off=(0x0; 0x7ffffffff)) R10=fp0 fp-8=mmmmmmmm fp-16=mmmmmmmm fp-24=mmmm???? fp-32= fp-40_w=4 fp-48=mmmmmmmm fp-56= fp-64=mmmmmmmm ... 89: (07) r2 += 1 ; R2_w=6 90: (79) r8 = *(u64 *)(r10 -48) ; R8_w=scalar() R10=fp0 91: (79) r1 = *(u64 *)(r10 -56) ; R1_w=scalar(umax=5,var_off=(0x0; 0x7)) R10=fp0 92: (ad) if r2 < r1 goto pc+41 ; R0_w=scalar() R1_w=scalar(umin=7,umax=5,var_off=(0x4; 0x3)) R2_w=6 R6=scalar(id=388) R7=0 R8_w=scalar() R9_w=scalar(umax=25769803770,var_off=(0x0; 0x7ffffffff)) R10=fp0 fp-8=mmmmmmmm fp-16=mmmmmmmm fp-24=mmmm???? fp-32= fp-40=5 fp-48=mmmmmmmm fp-56= fp-64=mmmmmmmm ... 89: (07) r2 += 1 ; R2_w=4088 90: (79) r8 = *(u64 *)(r10 -48) ; R8_w=scalar() R10=fp0 91: (79) r1 = *(u64 *)(r10 -56) ; R1_w=scalar(umax=5,var_off=(0x0; 0x7)) R10=fp0 92: (ad) if r2 < r1 goto pc+41 ; R0=scalar() R1=scalar(umin=4089,umax=5,var_off=(0x0; 0x7)) R2=4088 R6=scalar(id=12634) R7=0 R8=scalar() R9=scalar(umax=17557826301960,var_off=(0x0; 0xfffffffffff)) R10=fp0 fp-8=mmmmmmmm fp-16=mmmmmmmm fp-24=mmmm???? fp-32= fp-40=4087 fp-48=mmmmmmmm fp-56= fp-64=mmmmmmmm Patch 3 fixed the above issue by handling ' ' properly. During developing selftests for Patch 3, I found some issues with bound deduction with BPF_EQ/BPF_NE and fixed the issue in Patch 1. After the above issue is fixed, the second issue shows up. ... 67: (07) r1 += -16 ; R1_w=fp-16 ; bpf_probe_read_kernel(&sgp, sizeof(sgp), sgs + i); 68: (b4) w2 = 8 ; R2_w=8 69: (85) call bpf_probe_read_kernel#113 ; R0_w=scalar() fp-16=mmmmmmmm ; return sgp; 70: (79) r6 = *(u64 *)(r10 -16) ; R6=scalar() R10=fp0 ; for (n = 0, sgp = get_sgp(sgs, i); sgp && (n < SG_MAX); 71: (15) if r6 == 0x0 goto pc-49 ; R6=scalar() 72: (b4) w1 = 0 ; R1_w=0 73: (05) goto pc-46 ; for (i = 0; (i < VIRTIO_MAX_SGS) && (i < out_sgs); i++) { 28: (bc) w7 = w1 ; R1_w=0 R7_w=0 ; bpf_probe_read_kernel(&len, sizeof(len), &sgp->length); ... 23: (79) r3 = *(u64 *)(r10 -40) ; R3_w=2 R10=fp0 ; for (i = 0; (i < VIRTIO_MAX_SGS) && (i < out_sgs); i++) { 24: (07) r3 += 1 ; R3_w=3 ; for (i = 0; (i < VIRTIO_MAX_SGS) && (i < out_sgs); i++) { 25: (79) r1 = *(u64 *)(r10 -56) ; R1_w=scalar(umax=5,var_off=(0x0; 0x7)) R10=fp0 26: (ad) if r3 < r1 goto pc+34 61: R0=scalar() R1_w=scalar(umin=4,umax=5,var_off=(0x4; 0x1)) R3_w=3 R6=scalar(id=1658) R7=0 R8=scalar(id=1653) R9=scalar(umax=4294967295,var_off=(0x0; 0xffffffff)) R10=fp0 fp-8=mmmmmmmm fp-16=mmmmmmmm fp-24=mmmm???? fp-32= fp-40=2 fp-56= fp-64=mmmmmmmm ; if (sg_is_chain(&sg)) 61: (7b) *(u64 *)(r10 -40) = r3 ; R3_w=3 R10=fp0 fp-40_w=3 ... 67: (07) r1 += -16 ; R1_w=fp-16 ; bpf_probe_read_kernel(&sgp, sizeof(sgp), sgs + i); 68: (b4) w2 = 8 ; R2_w=8 69: (85) call bpf_probe_read_kernel#113 ; R0_w=scalar() fp-16=mmmmmmmm ; return sgp; 70: (79) r6 = *(u64 *)(r10 -16) ; for (n = 0, sgp = get_sgp(sgs, i); sgp && (n < SG_MAX); infinite loop detected at insn 71 verification time 90800 usec stack depth 64 processed 25017 insns (limit 1000000) max_states_per_insn 20 total_states 491 peak_states 169 mark_read 12 -- END PROG LOAD LOG -- libbpf: prog 'trace_virtqueue_add_sgs': failed to load: -22 Further analysis found the index variable 'i' is spilled but since it is not marked as precise, regsafe will ignore comparison since they are scalar values. Since it is hard for verifier to determine whether a particular scalar is index variable or not, Patch 5 implemented a heuristic such that if both old and new reg states are constant, mark the old one as precise to force scalar value comparison and this fixed the problem. The rest of patches are selftests related. [1] https://reviews.llvm.org/D143726 [2] Commit 3c2611bac08a ("selftests/bpf: Fix trace_virtqueue_add_sgs test issue with LLVM 17.") Yonghong Song (7): bpf: Improve verifier JEQ/JNE insn branch taken checking selftests/bpf: Add tests for non-constant cond_op NE/EQ bound deduction bpf: Improve handling of pattern ' ' in verifier selftests/bpf: Add verifier tests for code pattern ' ' bpf: Mark potential spilled loop index variable as precise selftests/bpf: Remove previous workaround for test verif_scale_loop6 selftests/bpf: Add a new test based on loop6.c kernel/bpf/verifier.c | 40 +- .../bpf/prog_tests/bpf_verif_scale.c | 5 + .../selftests/bpf/prog_tests/verifier.c | 2 + tools/testing/selftests/bpf/progs/loop6.c | 2 - tools/testing/selftests/bpf/progs/loop7.c | 102 ++++ .../verifier_bounds_deduction_non_const.c | 553 ++++++++++++++++++ .../progs/verifier_bounds_mix_sign_unsign.c | 2 +- 7 files changed, 701 insertions(+), 5 deletions(-) create mode 100644 tools/testing/selftests/bpf/progs/loop7.c create mode 100644 tools/testing/selftests/bpf/progs/verifier_bounds_deduction_non_const.c