From patchwork Mon Mar 6 03:31:18 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Xu Kuohai X-Patchwork-Id: 64320 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:5915:0:0:0:0:0 with SMTP id v21csp1406347wrd; Sun, 5 Mar 2023 06:59:11 -0800 (PST) X-Google-Smtp-Source: AK7set8dALrLXVEJqs+cpRTMJF2fYs6bSEelin5mzfVITTBS6jMPuPfUctTINrIF8jONlHvvGJTx X-Received: by 2002:a17:902:bd93:b0:19c:be03:d1a3 with SMTP id q19-20020a170902bd9300b0019cbe03d1a3mr7439706pls.40.1678028350863; Sun, 05 Mar 2023 06:59:10 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1678028350; cv=none; d=google.com; s=arc-20160816; b=JARj5Lvp4MYpmpsZooslqDDDD6Xz13UjvE8UWwo1Q9cqRLAZq2Fg7E7gI3+5fxZr2X m2ArTTSGa/WynA6594fYtHMl6PbkJbv456PXuEboapMMrKQPQW9qREgw/0kI8gXXbhYf gtUOB45f9FnqEV8xDTfMzRBxu3ieKTyixhQ9XLWhAv4eObnU66wBTN1/TdMMPtkK65bR wRejaB1WUxshpoLambHC9o1RtsD+f/466JQOlgbnDpsS8GgRbKwmEcuBOowHMFs6eZZI SSmxV+5i8qoeVRL3k5lDugwZFlG0CCfKj2c/NON8L6l7Otau6glv4bDy4h2Z+MSZ5xOW keew== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from; bh=T75qVqnKBKtGa5AxuFEQjE4pNgpRYdQ7L9wTFNs/kLw=; b=MNTIO5uN4VdssGmR9kkimResMwG5ezYXciz76kDp56oLT056S9eRYnHHjoPEwBfJsZ de4o5dS/5bSeSRLjNuHZpbylwaUZLBju70HQT7fWxuzj+JxTN1jbqNdJjk+eNFl79Fzq TpoM7RSDritgRBRj5f3AfjIXIiE7JvZIKLuT/D5L5Qme+0oLEApGPRIFRn36WO6QIJ/O F3Wsgs9CZur9XxV+gRoYQQNt0aehWYpM9V/AzDcTkA2I5RPQ8Kyba2UXSf6pXc+OItis lsx049vZyxkzNuyl0HlTQCyFyjrFUXqhwZIpQvUpU6A16uj3GFjL5Sp/62N2eym40nep WnSw== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id s14-20020a170902ea0e00b0019935e9b087si7749122plg.234.2023.03.05.06.58.58; Sun, 05 Mar 2023 06:59:10 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229839AbjCEObr (ORCPT + 99 others); Sun, 5 Mar 2023 09:31:47 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56672 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229787AbjCEObo (ORCPT ); Sun, 5 Mar 2023 09:31:44 -0500 Received: from dggsgout12.his.huawei.com (dggsgout12.his.huawei.com [45.249.212.56]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id A0F0A10A95; Sun, 5 Mar 2023 06:31:36 -0800 (PST) Received: from mail02.huawei.com (unknown [172.30.67.153]) by dggsgout12.his.huawei.com (SkyGuard) with ESMTP id 4PV40243qhz4f3kpB; Sun, 5 Mar 2023 22:31:30 +0800 (CST) Received: from k01.huawei.com (unknown [10.67.174.197]) by APP4 (Coremail) with SMTP id gCh0CgBnF6vApwRkTwIvEw--.13658S3; Sun, 05 Mar 2023 22:31:32 +0800 (CST) From: Xu Kuohai To: bpf@vger.kernel.org, linux-kselftest@vger.kernel.org, linux-kernel@vger.kernel.org Cc: Alexei Starovoitov , Daniel Borkmann , John Fastabend , Andrii Nakryiko , Martin KaFai Lau , Song Liu , Yonghong Song , KP Singh , Stanislav Fomichev , Hao Luo , Jiri Olsa , Mykola Lysenko , Shuah Khan Subject: [PATCH bpf-next 1/2] bpf: add bound tracking for BPF_MOD Date: Sun, 5 Mar 2023 22:31:18 -0500 Message-Id: <20230306033119.2634976-2-xukuohai@huaweicloud.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20230306033119.2634976-1-xukuohai@huaweicloud.com> References: <20230306033119.2634976-1-xukuohai@huaweicloud.com> MIME-Version: 1.0 X-CM-TRANSID: gCh0CgBnF6vApwRkTwIvEw--.13658S3 X-Coremail-Antispam: 1UD129KBjvJXoW3WFy8tFWDZFy8Gr4kGFWrGrg_yoW7XFWrpF ZxWrZxXr4DA3y7Awn2qw4DArZ5WF18J3Wruryqk34xJry7JFyYy3WDKF12ya4ayrZ2yr4f tF1UW39rWa1Uta7anT9S1TB71UUUUU7qnTZGkaVYY2UrUUUUjbIjqfuFe4nvWSU5nxnvy2 9KBjDU0xBIdaVrnRJUUUPab4IE77IF4wAFF20E14v26rWj6s0DM7CY07I20VC2zVCF04k2 6cxKx2IYs7xG6rWj6s0DM7CIcVAFz4kK6r1j6r18M280x2IEY4vEnII2IxkI6r4Y6ry7M2 8IrcIa0xkI8VA2jI8067AKxVWUGwA2048vs2IY020Ec7CjxVAFwI0_Gr0_Xr1l8cAvFVAK 0II2c7xJM28CjxkF64kEwVA0rcxSw2x7M28EF7xvwVC0I7IYx2IY67AKxVWDJVCq3wA2z4 x0Y4vE2Ix0cI8IcVCY1x0267AKxVW8Jr0_Cr1UM28EF7xvwVC2z280aVAFwI0_GcCE3s1l 84ACjcxK6I8E87Iv6xkF7I0E14v26rxl6s0DM2AIxVAIcxkEcVAq07x20xvEncxIr21l5I 8CrVACY4xI64kE6c02F40Ex7xfMcIj6xIIjxv20xvE14v26r1Y6r17McIj6I8E87Iv67AK xVWUJVW8JwAm72CE4IkC6x0Yz7v_Jr0_Gr1lF7xvr2IYc2Ij64vIr41lFIxGxcIEc7CjxV A2Y2ka0xkIwI1l42xK82IYc2Ij64vIr41l4I8I3I0E4IkC6x0Yz7v_Jr0_Gr1lx2IqxVAq x4xG67AKxVWUJVWUGwC20s026x8GjcxK67AKxVWUGVWUWwC2zVAF1VAY17CE14v26r4a6r W5MIIYrxkI7VAKI48JMIIF0xvE2Ix0cI8IcVAFwI0_Jr0_JF4lIxAIcVC0I7IYx2IY6xkF 7I0E14v26r4j6F4UMIIF0xvE42xK8VAvwI8IcIk0rVWUJVWUCwCI42IY6I8E87Iv67AKxV WUJVW8JwCI42IY6I8E87Iv6xkF7I0E14v26r4j6r4UJbIYCTnIWIevJa73UjIFyTuYvjxU IdgAUUUUU X-CM-SenderInfo: 50xn30hkdlqx5xdzvxpfor3voofrz/ X-CFilter-Loop: Reflected X-Spam-Status: No, score=1.3 required=5.0 tests=BAYES_00,DATE_IN_FUTURE_12_24, SPF_HELO_NONE,SPF_NONE autolearn=no autolearn_force=no version=3.4.6 X-Spam-Level: * X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1759540210969995922?= X-GMAIL-MSGID: =?utf-8?q?1759540256070851003?= From: Xu Kuohai dst_reg is marked as unknown when BPF_MOD instruction is verified, causing the following bpf prog to be incorrectly rejected. 0: r0 = 0 1: r0 %= 10 // r0 is marked as unknown 2: r1 = 0 3: r1 += 1 4: if r1 < r0 goto pc-2 // verifier concludes the loop is unbounded 5: exit To teach verifier to accept the above prog, this patch adds bound tracking for BPF_MOD, based on the following observation. BPF_MOD is unsigned and for a given unsigned divisor x: 1. when x != 0, dst_reg bits are in the range [0, x); 2. when x == 0, dst_reg is truncated to 32 bits by mod32 or remains unchanged by mod64. Signed-off-by: Xu Kuohai --- kernel/bpf/verifier.c | 98 ++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 93 insertions(+), 5 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 272563a0b770..d44a33a53e8e 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -11257,6 +11257,87 @@ static void scalar_min_max_arsh(struct bpf_reg_state *dst_reg, __update_reg_bounds(dst_reg); } +static void scalar32_min_max_mod(struct bpf_reg_state *dst_reg, + struct bpf_reg_state *src_reg) +{ + u32 val = (u32)src_reg->var_off.value; /* src_reg is const */ + u32 umax = dst_reg->u32_max_value; + u32 umin = dst_reg->u32_min_value; + u32 umax_rem, umin_rem; + + /* dst_reg is 32-bit truncated when mod32 zero, since + * adjust_scalar_min_max_vals calls zext_32_to_64 to do truncation for + * all alu32 ops, here we do nothing and just return. + */ + if (!val) + return; + + umax_rem = do_div(umax, val); + umin_rem = do_div(umin, val); + + /* no winding */ + if (umax - umin < val && umin_rem <= umax_rem) { + dst_reg->var_off = tnum_range(umin_rem, umax_rem); + dst_reg->u32_min_value = umin_rem; + dst_reg->u32_max_value = umax_rem; + } else { + dst_reg->var_off = tnum_range(0, val - 1); + dst_reg->u32_min_value = 0; + dst_reg->u32_max_value = val - 1; + } + + /* cross the sign boundary */ + if ((s32)dst_reg->u32_min_value > (s32)dst_reg->u32_max_value) { + dst_reg->s32_min_value = S32_MIN; + dst_reg->s32_max_value = S32_MAX; + } else { + dst_reg->s32_min_value = (s32)dst_reg->u32_min_value; + dst_reg->s32_max_value = (s32)dst_reg->u32_max_value; + } + + /* mark reg64 unbounded to deduce 64-bit bounds from var_off */ + __mark_reg64_unbounded(dst_reg); +} + +static void scalar_min_max_mod(struct bpf_reg_state *dst_reg, + struct bpf_reg_state *src_reg) +{ + u64 val = src_reg->var_off.value; /* src_reg is const */ + u64 umax = dst_reg->umax_value; + u64 umin = dst_reg->umin_value; + u64 umax_rem, umin_rem; + + /* dst_reg is untouched when mod64 zero */ + if (!val) + return; + + div64_u64_rem(umin, val, &umin_rem); + div64_u64_rem(umax, val, &umax_rem); + + /* no winding */ + if (umax - umin < val && umin_rem <= umax_rem) { + dst_reg->var_off = tnum_range(umin_rem, umax_rem); + dst_reg->umin_value = umin_rem; + dst_reg->umax_value = umax_rem; + } else { + dst_reg->var_off = tnum_range(0, val - 1); + dst_reg->umin_value = 0; + dst_reg->umax_value = val - 1; + } + + /* cross the sign boundary */ + if ((s64)dst_reg->umin_value > (s64)dst_reg->umax_value) { + dst_reg->smin_value = S64_MIN; + dst_reg->smax_value = S64_MAX; + } else { + dst_reg->smin_value = (s64)dst_reg->umin_value; + dst_reg->smax_value = (s64)dst_reg->umax_value; + } + + /* mark reg32 unbounded to deduce 32-bit bounds from var_off */ + __mark_reg32_unbounded(dst_reg); +} + /* WARNING: This function does calculations on 64-bit values, but the actual * execution may occur on 32-bit values. Therefore, things like bitshifts * need extra checks in the 32-bit case. @@ -11331,11 +11412,12 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, * and BPF_OR. This is possible because these ops have fairly easy to * understand and calculate behavior in both 32-bit and 64-bit alu ops. * See alu32 verifier tests for examples. The second class of - * operations, BPF_LSH, BPF_RSH, and BPF_ARSH, however are not so easy - * with regards to tracking sign/unsigned bounds because the bits may - * cross subreg boundaries in the alu64 case. When this happens we mark - * the reg unbounded in the subreg bound space and use the resulting - * tnum to calculate an approximation of the sign/unsigned bounds. + * operations, BPF_LSH, BPF_RSH, BPF_ARSH and BPF_MOD, however are not + * so easy with regards to tracking sign/unsigned bounds because the + * bits may cross subreg boundaries in the alu64 case. When this happens + * we mark the reg unbounded in the subreg bound space and use the + * resulting tnum to calculate an approximation of the sign/unsigned + * bounds. */ switch (opcode) { case BPF_ADD: @@ -11407,6 +11489,12 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, else scalar_min_max_arsh(dst_reg, &src_reg); break; + case BPF_MOD: + if (alu32) + scalar32_min_max_mod(dst_reg, &src_reg); + else + scalar_min_max_mod(dst_reg, &src_reg); + break; default: mark_reg_unknown(env, regs, insn->dst_reg); break; From patchwork Mon Mar 6 03:31:19 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Xu Kuohai X-Patchwork-Id: 64321 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:5915:0:0:0:0:0 with SMTP id v21csp1407085wrd; Sun, 5 Mar 2023 07:00:49 -0800 (PST) X-Google-Smtp-Source: AK7set/y2WY7URzYZNjVHABtwItig8JtkVI6M3RbhWG8N80f5C0+jsHdSIx6SNpd/0utbrve72Gi X-Received: by 2002:a05:6a20:6982:b0:cb:c276:58d6 with SMTP id t2-20020a056a20698200b000cbc27658d6mr15516110pzk.34.1678028449672; Sun, 05 Mar 2023 07:00:49 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1678028449; cv=none; d=google.com; s=arc-20160816; b=WdPhoSzu2ZGqKZ5ebztBdTX1r5p8jeFJIosqXBJyYd3t1TGMraROcKAAG1JTMWAVIT YY+wagMaYWNqgMfD7n4ycmXdwbCI6UtfJeggxVuxrGd1mZk8N0Hd83UKOyapZ4HGlWG2 9ToRlKgvXwQlTcd4okdrj0xbtvxgOCBu8EYu4YiuXJxc3NMChNjcnHfEdgUvO5RxGdpZ ujFWtxAb5K96thOjuQ8VUexoFJ8/laWYc5ewaWu7/ifEqTup5g6/YCaW1HbHnAPJZa9n IO2ZFDVbxQmhjAkN12VtQ9WSOAkRGJBZnP7vBkm+gnMPBTTOqL8vYJHHZEA9Gok16DKt /3RQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from; bh=9nb5fyqYun9AQA37OA1TIfWPtAt7QWTTcOIzdc6P+xg=; b=La/N+atCKyDeZtqsC4JCqcNxOTQuoDkYeBEWG6dAtm+zbTxldCIDbGRjkrLIV3bXjr kU9C31uyCjT0fzGgIVlhmjJ5zeq/WLoT70wCzx+o0SMFcULZZ9ax4YJGE//ZQQIoCYjT RcT6hpQYvfxCI080CcMwFbgS2/EGOUuikvd9krp1av9x8n3DDZkW7ERMfgCKPx4H4IE7 wpgFvfHohtq/vSoLvmcEXiBeI5lEepy/60bKuPK6I14bTEz3VU0E9bwe0hj4z4yy172C m6cAekl92pzddRPWxab4ue6vVN+irQoaJH02U3mjyFX0+CxLjw5TqpjS/F1Pattv0oGs knSg== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id bc22-20020a656d96000000b004fb850691adsi7551051pgb.718.2023.03.05.07.00.36; Sun, 05 Mar 2023 07:00:49 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229946AbjCEOby (ORCPT + 99 others); Sun, 5 Mar 2023 09:31:54 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56822 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229880AbjCEObu (ORCPT ); Sun, 5 Mar 2023 09:31:50 -0500 Received: from dggsgout11.his.huawei.com (unknown [45.249.212.51]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id BC2801117E; Sun, 5 Mar 2023 06:31:37 -0800 (PST) Received: from mail02.huawei.com (unknown [172.30.67.153]) by dggsgout11.his.huawei.com (SkyGuard) with ESMTP id 4PV4042pC9z4f3jMK; Sun, 5 Mar 2023 22:31:32 +0800 (CST) Received: from k01.huawei.com (unknown [10.67.174.197]) by APP4 (Coremail) with SMTP id gCh0CgBnF6vApwRkTwIvEw--.13658S4; Sun, 05 Mar 2023 22:31:34 +0800 (CST) From: Xu Kuohai To: bpf@vger.kernel.org, linux-kselftest@vger.kernel.org, linux-kernel@vger.kernel.org Cc: Alexei Starovoitov , Daniel Borkmann , John Fastabend , Andrii Nakryiko , Martin KaFai Lau , Song Liu , Yonghong Song , KP Singh , Stanislav Fomichev , Hao Luo , Jiri Olsa , Mykola Lysenko , Shuah Khan Subject: [PATCH bpf-next 2/2] selftests/bpf: check if verifier tracks dst_reg bound for BPF_MOD Date: Sun, 5 Mar 2023 22:31:19 -0500 Message-Id: <20230306033119.2634976-3-xukuohai@huaweicloud.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20230306033119.2634976-1-xukuohai@huaweicloud.com> References: <20230306033119.2634976-1-xukuohai@huaweicloud.com> MIME-Version: 1.0 X-CM-TRANSID: gCh0CgBnF6vApwRkTwIvEw--.13658S4 X-Coremail-Antispam: 1UD129KBjvJXoWxtr48uw1UGr4xtF48XF43Wrg_yoWxuF1xp3 4Fq3WDJr48Jw4YvaykKFyI93W3Kr4kJrsrC3s29r17Zay3J3WfW3WUta15CwnxJr1rJrsY qr15Cw1kJayjvrUanT9S1TB71UUUUU7qnTZGkaVYY2UrUUUUjbIjqfuFe4nvWSU5nxnvy2 9KBjDU0xBIdaVrnRJUUUPSb4IE77IF4wAFF20E14v26rWj6s0DM7CY07I20VC2zVCF04k2 6cxKx2IYs7xG6rWj6s0DM7CIcVAFz4kK6r1j6r18M280x2IEY4vEnII2IxkI6r4Y6ry7M2 8IrcIa0xkI8VA2jI8067AKxVWUXwA2048vs2IY020Ec7CjxVAFwI0_Xr0E3s1l8cAvFVAK 0II2c7xJM28CjxkF64kEwVA0rcxSw2x7M28EF7xvwVC0I7IYx2IY67AKxVWDJVCq3wA2z4 x0Y4vE2Ix0cI8IcVCY1x0267AKxVW8Jr0_Cr1UM28EF7xvwVC2z280aVAFwI0_GcCE3s1l 84ACjcxK6I8E87Iv6xkF7I0E14v26rxl6s0DM2AIxVAIcxkEcVAq07x20xvEncxIr21l5I 8CrVACY4xI64kE6c02F40Ex7xfMcIj6xIIjxv20xvE14v26r1Y6r17McIj6I8E87Iv67AK xVWUJVW8JwAm72CE4IkC6x0Yz7v_Jr0_Gr1lF7xvr2IYc2Ij64vIr41lFIxGxcIEc7CjxV A2Y2ka0xkIwI1l42xK82IYc2Ij64vIr41l4I8I3I0E4IkC6x0Yz7v_Jr0_Gr1lx2IqxVAq x4xG67AKxVWUJVWUGwC20s026x8GjcxK67AKxVWUGVWUWwC2zVAF1VAY17CE14v26r4a6r W5MIIYrxkI7VAKI48JMIIF0xvE2Ix0cI8IcVAFwI0_JFI_Gr1lIxAIcVC0I7IYx2IY6xkF 7I0E14v26F4j6r4UJwCI42IY6xAIw20EY4v20xvaj40_Jr0_JF4lIxAIcVC2z280aVAFwI 0_Jr0_Gr1lIxAIcVC2z280aVCY1x0267AKxVW8JVW8JrUvcSsGvfC2KfnxnUUI43ZEXa7I U8HKZJUUUUU== X-CM-SenderInfo: 50xn30hkdlqx5xdzvxpfor3voofrz/ X-CFilter-Loop: Reflected X-Spam-Status: No, score=2.7 required=5.0 tests=BAYES_00,DATE_IN_FUTURE_12_24, KHOP_HELO_FCRDNS,MAY_BE_FORGED,SPF_HELO_NONE,SPF_NONE,UPPERCASE_50_75 autolearn=no autolearn_force=no version=3.4.6 X-Spam-Level: ** X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1759540359310609158?= X-GMAIL-MSGID: =?utf-8?q?1759540359310609158?= From: Xu Kuohai Test cases to check if verifier tracks dst_reg bound for BPF_MOD. Signed-off-by: Xu Kuohai --- tools/testing/selftests/bpf/verifier/mod.c | 247 +++++++++++++++++++++ 1 file changed, 247 insertions(+) create mode 100644 tools/testing/selftests/bpf/verifier/mod.c diff --git a/tools/testing/selftests/bpf/verifier/mod.c b/tools/testing/selftests/bpf/verifier/mod.c new file mode 100644 index 000000000000..717e4cd08e59 --- /dev/null +++ b/tools/testing/selftests/bpf/verifier/mod.c @@ -0,0 +1,247 @@ +{ + "mod64 positive imm", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_ALU64_IMM(BPF_MOD, BPF_REG_0, 1), + + BPF_MOV64_IMM(BPF_REG_1, 0), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 1), + BPF_JMP_REG(BPF_JLT, BPF_REG_1, BPF_REG_0, -2), + + BPF_EXIT_INSN(), + }, + .result = ACCEPT, + .prog_type = BPF_PROG_TYPE_XDP, +}, +{ + "mod64 positive reg", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_MOV64_IMM(BPF_REG_1, 1), + BPF_ALU64_REG(BPF_MOD, BPF_REG_0, BPF_REG_1), + + BPF_MOV64_IMM(BPF_REG_1, 0), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 1), + BPF_JMP_REG(BPF_JLT, BPF_REG_1, BPF_REG_0, -2), + + BPF_EXIT_INSN(), + }, + .result = ACCEPT, + .prog_type = BPF_PROG_TYPE_XDP, +}, +{ + "mod64 zero", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_MOV64_IMM(BPF_REG_1, 0), + BPF_ALU64_REG(BPF_MOD, BPF_REG_0, BPF_REG_1), + + BPF_MOV64_IMM(BPF_REG_1, 0), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 1), + BPF_JMP_REG(BPF_JLT, BPF_REG_1, BPF_REG_0, -2), + + BPF_EXIT_INSN(), + }, + .result = ACCEPT, + .prog_type = BPF_PROG_TYPE_XDP, +}, +{ + "mod64 negative 1", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, 1), + BPF_MOV64_IMM(BPF_REG_1, -1), + BPF_ALU64_REG(BPF_MOD, BPF_REG_0, BPF_REG_1), + + BPF_MOV64_IMM(BPF_REG_1, 0), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 1), + BPF_JMP_REG(BPF_JLT, BPF_REG_1, BPF_REG_0, -2), + + BPF_EXIT_INSN(), + }, + .result = ACCEPT, + .prog_type = BPF_PROG_TYPE_XDP, + .retval = 1, +}, +{ + "mod64 negative 2", + .insns = { + BPF_MOV64_IMM(BPF_REG_0, -4), + BPF_MOV32_IMM(BPF_REG_1, 5), + BPF_ALU64_REG(BPF_MOD, BPF_REG_0, BPF_REG_1), + + BPF_MOV64_IMM(BPF_REG_1, 0), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 1), + BPF_JMP_REG(BPF_JLT, BPF_REG_1, BPF_REG_0, -2), + + BPF_EXIT_INSN(), + }, + .result = ACCEPT, + .prog_type = BPF_PROG_TYPE_XDP, + .retval = 2, +}, +{ + "mod64 negative 3", + .insns = { + BPF_MOV32_IMM(BPF_REG_0, -4), + BPF_MOV32_IMM(BPF_REG_1, -5), + BPF_ALU64_REG(BPF_MOD, BPF_REG_0, BPF_REG_1), + + BPF_MOV64_IMM(BPF_REG_1, 0), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 1), + BPF_JMP_REG(BPF_JLT, BPF_REG_1, BPF_REG_0, -2), + + BPF_EXIT_INSN(), + }, + .result = ACCEPT, + .prog_type = BPF_PROG_TYPE_XDP, + .retval = 1, +}, +{ + "mod64 variable dividend cross signed boundary", + .insns = { + BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1, offsetof(struct xdp_md, data)), + BPF_LDX_MEM(BPF_W, BPF_REG_3, BPF_REG_1, offsetof(struct xdp_md, data_end)), + BPF_MOV64_REG(BPF_REG_1, BPF_REG_2), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 1), + BPF_JMP_REG(BPF_JGT, BPF_REG_1, BPF_REG_3, 11), + + BPF_LDX_MEM(BPF_B, BPF_REG_1, BPF_REG_2, 0), + BPF_LD_IMM64(BPF_REG_0, 0x7fffffffffffff10), + BPF_ALU64_REG(BPF_ADD, BPF_REG_1, BPF_REG_0), + BPF_LD_IMM64(BPF_REG_0, 0x80000000000000ff), + BPF_ALU64_REG(BPF_MOD, BPF_REG_1, BPF_REG_0), + + BPF_LD_IMM64(BPF_REG_0, 0x8000000000000000), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 1), + BPF_JMP_REG(BPF_JSLT, BPF_REG_0, BPF_REG_1, -2), + + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_EXIT_INSN(), + }, + .errstr = "BPF program is too large.", + .result = REJECT, + .prog_type = BPF_PROG_TYPE_XDP, +}, +{ + "mod32 positive imm", + .insns = { + BPF_MOV32_IMM(BPF_REG_0, 0), + BPF_ALU32_IMM(BPF_MOD, BPF_REG_0, 1), + + BPF_MOV64_IMM(BPF_REG_1, 0), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 1), + BPF_JMP_REG(BPF_JLT, BPF_REG_1, BPF_REG_0, -2), + + BPF_EXIT_INSN(), + }, + .result = ACCEPT, + .prog_type = BPF_PROG_TYPE_XDP, +}, +{ + "mod32 positive reg", + .insns = { + BPF_MOV32_IMM(BPF_REG_0, 0), + BPF_MOV32_IMM(BPF_REG_1, 1), + BPF_ALU32_REG(BPF_MOD, BPF_REG_0, BPF_REG_1), + + BPF_MOV64_IMM(BPF_REG_1, 0), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 1), + BPF_JMP_REG(BPF_JLT, BPF_REG_1, BPF_REG_0, -2), + + BPF_EXIT_INSN(), + }, + .result = ACCEPT, + .prog_type = BPF_PROG_TYPE_XDP, +}, +{ + "mod32 zero", + .insns = { + BPF_MOV32_IMM(BPF_REG_0, 0), + BPF_MOV32_IMM(BPF_REG_1, 0), + BPF_ALU32_REG(BPF_MOD, BPF_REG_0, BPF_REG_1), + + BPF_MOV64_IMM(BPF_REG_1, 0), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 1), + BPF_JMP_REG(BPF_JLT, BPF_REG_1, BPF_REG_0, -2), + + BPF_EXIT_INSN(), + }, + .result = ACCEPT, + .prog_type = BPF_PROG_TYPE_XDP, +}, +{ + "mod32 negative 1", + .insns = { + BPF_MOV32_IMM(BPF_REG_0, 1), + BPF_MOV32_IMM(BPF_REG_1, -1), + BPF_ALU32_REG(BPF_MOD, BPF_REG_0, BPF_REG_1), + + BPF_MOV64_IMM(BPF_REG_1, 0), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 1), + BPF_JMP_REG(BPF_JLT, BPF_REG_1, BPF_REG_0, -2), + + BPF_EXIT_INSN(), + }, + .result = ACCEPT, + .prog_type = BPF_PROG_TYPE_XDP, + .retval = 1, +}, +{ + "mod32 negative 2", + .insns = { + BPF_MOV32_IMM(BPF_REG_0, -4), + BPF_MOV32_IMM(BPF_REG_1, 5), + BPF_ALU32_REG(BPF_MOD, BPF_REG_0, BPF_REG_1), + + BPF_MOV64_IMM(BPF_REG_1, 0), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 1), + BPF_JMP_REG(BPF_JLT, BPF_REG_1, BPF_REG_0, -2), + + BPF_EXIT_INSN(), + }, + .result = ACCEPT, + .prog_type = BPF_PROG_TYPE_XDP, + .retval = 2, +}, +{ + "mod32 negative 3", + .insns = { + BPF_MOV32_IMM(BPF_REG_0, -4), + BPF_MOV32_IMM(BPF_REG_1, -5), + BPF_ALU32_REG(BPF_MOD, BPF_REG_0, BPF_REG_1), + + BPF_MOV64_IMM(BPF_REG_1, 0), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 1), + BPF_JMP_REG(BPF_JLT, BPF_REG_1, BPF_REG_0, -2), + + BPF_EXIT_INSN(), + }, + .result = ACCEPT, + .prog_type = BPF_PROG_TYPE_XDP, + .retval = 1, +}, +{ + "mod32 variable dividend cross signed boundary", + .insns = { + BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1, offsetof(struct xdp_md, data)), + BPF_LDX_MEM(BPF_W, BPF_REG_3, BPF_REG_1, offsetof(struct xdp_md, data_end)), + BPF_MOV64_REG(BPF_REG_1, BPF_REG_2), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 1), + BPF_JMP_REG(BPF_JGT, BPF_REG_1, BPF_REG_3, 7), + + BPF_LDX_MEM(BPF_B, BPF_REG_1, BPF_REG_2, 0), + BPF_MOV64_IMM(BPF_REG_0, 0x7fffff10), + BPF_ALU64_REG(BPF_ADD, BPF_REG_1, BPF_REG_0), + BPF_ALU32_IMM(BPF_MOD, BPF_REG_1, 0x800000ff), + + BPF_MOV32_IMM(BPF_REG_0, 0x80000000), + BPF_ALU32_IMM(BPF_ADD, BPF_REG_0, 1), + BPF_JMP32_REG(BPF_JSLT, BPF_REG_0, BPF_REG_1, -2), + + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_EXIT_INSN(), + }, + .errstr = "BPF program is too large.", + .result = REJECT, + .prog_type = BPF_PROG_TYPE_XDP, +},