From patchwork Tue Mar 14 12:42:01 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13174288 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 kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id A0964C74A5B for ; Tue, 14 Mar 2023 12:42:22 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 2DDE56B0074; Tue, 14 Mar 2023 08:42:22 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 28DB58E0003; Tue, 14 Mar 2023 08:42:22 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 155F48E0002; Tue, 14 Mar 2023 08:42:22 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0016.hostedemail.com [216.40.44.16]) by kanga.kvack.org (Postfix) with ESMTP id 003B36B0074 for ; Tue, 14 Mar 2023 08:42:21 -0400 (EDT) Received: from smtpin16.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id CC93C160C53 for ; Tue, 14 Mar 2023 12:42:21 +0000 (UTC) X-FDA: 80567466882.16.0B8730F Received: from mail-pj1-f51.google.com (mail-pj1-f51.google.com [209.85.216.51]) by imf05.hostedemail.com (Postfix) with ESMTP id 00627100012 for ; Tue, 14 Mar 2023 12:42:19 +0000 (UTC) Authentication-Results: imf05.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=Q0EWqbll; spf=pass (imf05.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.51 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=none) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1678797740; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=V3vWZFEyoFMtyU6NTTWlVAUK8MBUwQjg+G+jzZCDuAk=; b=2YoeB1Z49Cr0dgnxQeHo70e2qwvkuh8ClLb0f26vFvvazEHyT1HBp0e37QIK8tXwRocr3M BB0c0f91mPdTMW1qevx//7f/tGQtU9SWl1rruPs/YMyYxhzcGJsis1o5VYdvZ2rhuL3EUK 7E8i+LU+sqzGw2/mi8SSv4gtM6favfY= ARC-Authentication-Results: i=1; imf05.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=Q0EWqbll; spf=pass (imf05.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.51 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=none) header.from=bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1678797740; a=rsa-sha256; cv=none; b=4AGLx2/XGltPoPomkseeigu1q5gPjmHmSdGQcdhsyoXuqRUMQ9Xx8nZ4c0NEu+J9X2LsgS y8g7KcByVdDquYddGQUz8erkRFpCgErSEoezJvqrzz2rOXw271Rtt7Uh7XcNpD/hqqJkNI nm2jpO17jHw9zg+RX+7e8l07GkIIIOI= Received: by mail-pj1-f51.google.com with SMTP id gp15-20020a17090adf0f00b0023d1bbd9f9eso4805896pjb.0 for ; Tue, 14 Mar 2023 05:42:19 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1678797738; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=V3vWZFEyoFMtyU6NTTWlVAUK8MBUwQjg+G+jzZCDuAk=; b=Q0EWqbllJxrbZyB/Dz9VLiyjmY6OKzQ9ODkPXCtv1PHZFxEXHWUGy9j8P3QCubHPW6 laPUIMP5ae5R8SQ31VbcE0PP2Qxc0ZRZeq9ial6QzAMDElJuHuLPmKq8qz8iadur2NK2 Qc6llIatsVC/fIYVCuEaCkKpavYWo5xV0MCwYao4CrA7z5VX0new9FRvp3QEbxYXkyiI SLS6EiaBUB2md6d10HaQRcz8rW8OxSMc7iQFehdRbjLPyp5kXZppj44STkAZGKtyjsmc olYO/uynIoSxt0B+X/x9asOLPNhgHb9CaVT7qrMmAGPN7MuDUu025M1syzM8Q6iWO8yG UYOw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1678797738; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=V3vWZFEyoFMtyU6NTTWlVAUK8MBUwQjg+G+jzZCDuAk=; b=dXCZsqEllk7RkIvWSzBYReumwyRng5z9ATsOhIaziN4hX6wHJIwswmYZ0Xt4x5pbjU Z1E5rsTT/Pf6JAS5QGooknffeokVo7LZKh7hgz/Mucf5OFZIyDoT6zHff0BaIuoVvlEd uqaigF91NAND4EJUr7KvgEO0PLq4aoAsJP4tJHAPqBXo9dpY1tlmAMpdjIz5kP7fIais C27xiik8tbLM+oUOcoaVYfcj/DDCiCBhAAZlOSkrrJODhnmdiyghlEHZuS8XmPVh4/cs A2bpG1sQSCUA5M+PVppUzbIZHZU/1ET2r4ot1nqcZu8oF5ZfiptoFx4FyMX7erYo74O1 Hdgg== X-Gm-Message-State: AO0yUKUzHVPcMXiMGIIcdNH5vvjHEmcvKSmE6q25ren2nn2o/RLoDmut 3OL05BasGjXuz50Uh/WS7NR9tQ== X-Google-Smtp-Source: AK7set9Ud5nZcxsuvhOGQRUujTT++2XEg590TsbcJ3Ds1UZrcs20nPDnaJZcfAnEuMlVPZqCfqCn0A== X-Received: by 2002:a05:6a20:bc97:b0:d5:74f:37a1 with SMTP id fx23-20020a056a20bc9700b000d5074f37a1mr3510720pzb.27.1678797738697; Tue, 14 Mar 2023 05:42:18 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.234]) by smtp.gmail.com with ESMTPSA id s11-20020aa7828b000000b005ded5d2d571sm1509385pfm.185.2023.03.14.05.42.16 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 14 Mar 2023 05:42:18 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH v2 1/3] maple_tree: Fix get wrong data_end in mtree_lookup_walk() Date: Tue, 14 Mar 2023 20:42:01 +0800 Message-Id: <20230314124203.91572-2-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230314124203.91572-1-zhangpeng.00@bytedance.com> References: <20230314124203.91572-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: 00627100012 X-Rspam-User: X-Stat-Signature: bhzjg9k17zxodu1ipxs9neamcrhxrnnk X-HE-Tag: 1678797739-342419 X-HE-Meta: U2FsdGVkX1/waJn0Jotum19oQZM/lnqBau2BJnDUH5kgLgYJ5e9srSPNSERVeD5Cl0FptJ/fMCL9hhY2tuR1Y6zTLVMDaExt4F5EOxAeqJ/UUmkPL+iZ9yT1Kctm/G1oDh6HYHhKZJYtqBr2mnG1LCQsTwUakllmVfKxOz3aFlVF3SwHBPWGmTS4ml/zF20TyHwe3GNFDrIVasAOMmkgvRdwo8OW4hRTFIb4/Hf5Uc7qxQSlh86aWkKWufSPZaOtNKcXCyX/ghNm9suBVHwwvWmOmw95OYvpYhcOTRKaJXZ+EirEPdcW6pdDKVXfOdGDVY8PQpGVhlcEn6iSYTCB+92M/N3zg0Q8XXcygkYNs9u4aIlddeTRmi9ax1W0s6fb0TCWMzG+gTq9AQzaUhb2Rvs0eQgJVXtRXSVUrHdYWu9y5KP0ne6/2fmKXijPrBNkaDPofVFnUP4n4UA02FhplkM6P3j1bdjhOEMtrJzpjOGdAwv14l2UWWbHvmC3mBX+IqmCG3TnGb7nzQI8TSII8YzsK5KrdQWjUR1HORYl/1flVlazRPD84U4sRubm5p99mNgTMR8ckRkXhl4wzVR6Y9+9N9CTuQkv8iGY1OgSDt11xTO5WZz5aWaExgASh0FQ9WTBtY9/IfuxQK9vkTyDvD/1ngs5OVsmXaru/neN4i6eiSPq5Q9MV+J5wdEWS7Qn0j6MkEBvryqmozVDaIotMawKHa5p4vg6/K1+aGERa1oNZZMpAnRWinYBK5AbzbNlB8qncSymobWlM9gIalnE9O7wJ2Va/9TCR/e2xVKloVDnrZbA6YVnBQtPjUKO2ssDo7quWWLjrwIMxi+3dOsAHPkXDzJCydtvtea/sPssRUY4Z4sQ9ZjL3dSxJPdfjPqJbZV1dsFRaMZh3Dtt0CHTM3SY/atbQjPIlrd68b7wrR1vBmgASaNh60yF4uGy9b2dGnKL3yIfyPllC1XY1sF aj8lQsZn 06oorOFOeQvhHmeqfXHRg192Sh0/1HJFuHDIdcXa8D0LhgTEIWVB8tW8+8pu2wsemAA0ru9RnOb6ecKm33G+R+dQy4lILn2PKBT9FvPul82VrmablLXFG383flmhCOWLN2d9IYlqmJQFiND2wBP48d+TVio0vCl2eb+t0H/l7f5EYqLOIzLJzG6nuOn6F/4JzJJsUXi71r5WV1BqyNnV0bVRpmF15kkPPM+SZ73pIMnlG2VPHx3RiGMOnICziXuAwweNmNT8fMA5BJpMjU70DzLB+gLpdeHN0kandR7neLFRMDNYbFy1sCVh68OFlwUyxyGUZ/pIkFsdre3wE/sfrZ9IkpQ+NvIi5YL7e0+Bg6izcvJw05iJnta2mrGfoF1MI8HqYKitAixqKD8bkPCCgexjy3rPDVwy2okQ8K71a/Vkspbpm3AVLEsOukS8lA7JCs7/Y56mEysBv2YJ8tb7+P848oHRu/iaK3LXG05JXc42ffOw= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: if (likely(offset > end)) max = pivots[offset]; The above code should be changed to if (likely(offset < end)), which is correct. This affects the correctness of ma_data_end(). Now it seems that the final result will not be wrong, but it is best to change it. This patch does not change the code as above, because it simplifies the code by the way. Fixes: 54a611b60590 ("Maple Tree: add new data structure") Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- lib/maple_tree.c | 15 +++++---------- 1 file changed, 5 insertions(+), 10 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 646297cae5d1..b3164266cfde 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3875,18 +3875,13 @@ static inline void *mtree_lookup_walk(struct ma_state *mas) end = ma_data_end(node, type, pivots, max); if (unlikely(ma_dead_node(node))) goto dead_node; - - if (pivots[offset] >= mas->index) - goto next; - do { - offset++; - } while ((offset < end) && (pivots[offset] < mas->index)); - - if (likely(offset > end)) - max = pivots[offset]; + if (pivots[offset] >= mas->index) { + max = pivots[offset]; + break; + } + } while (++offset < end); -next: slots = ma_slots(node, type); next = mt_slot(mas->tree, slots, offset); if (unlikely(ma_dead_node(node))) From patchwork Tue Mar 14 12:42:02 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13174289 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 kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 620FCC6FD1C for ; Tue, 14 Mar 2023 12:42:25 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id F3AB08E0002; Tue, 14 Mar 2023 08:42:24 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id EE9A16B0078; Tue, 14 Mar 2023 08:42:24 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id D8B578E0002; Tue, 14 Mar 2023 08:42:24 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0012.hostedemail.com [216.40.44.12]) by kanga.kvack.org (Postfix) with ESMTP id CAC806B0075 for ; Tue, 14 Mar 2023 08:42:24 -0400 (EDT) Received: from smtpin25.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 7B2B3160EA5 for ; Tue, 14 Mar 2023 12:42:24 +0000 (UTC) X-FDA: 80567467008.25.28783B4 Received: from mail-pj1-f44.google.com (mail-pj1-f44.google.com [209.85.216.44]) by imf22.hostedemail.com (Postfix) with ESMTP id AFD68C0014 for ; Tue, 14 Mar 2023 12:42:22 +0000 (UTC) Authentication-Results: imf22.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=ix7uri1I; dmarc=pass (policy=none) header.from=bytedance.com; spf=pass (imf22.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.44 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1678797742; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=6gfvzdPPIJNGgSXDt2FDnmzg914LTKb84rb4IiYC554=; b=MORGy78jRwU96l1PkjVvDoZtlqTrVV2bm9D9gjAkloYM6qt/OmhH116QXQ8G4cCexuK2ym 5xwloOjueyJ+8oi/AjeMDZACaGSHwxA1VKTq6avZTH4fWPrJNurZ7Pj5JM0oT7Vu0Es7pC 5eynGY293VOkaLHgUGKmw2j/zTzVdYo= ARC-Authentication-Results: i=1; imf22.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=ix7uri1I; dmarc=pass (policy=none) header.from=bytedance.com; spf=pass (imf22.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.44 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1678797742; a=rsa-sha256; cv=none; b=701aEptoIY2Zr81YbPRVH6fxuW6A6fdZaIZ9tio9NPe+tu6ndos0C5qX9R8PgmEdYVA9UO cQVZrFAstTxMbv1swEi6hLuyBu1SjIeOyNNJCLyrw/y7KTss7AYZU4RPmVHowURa5WjmHc +EJyAgTExC6/bUOCFypRTI0eI0g02O0= Received: by mail-pj1-f44.google.com with SMTP id j3-20020a17090adc8300b0023d09aea4a6so5905257pjv.5 for ; Tue, 14 Mar 2023 05:42:22 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1678797741; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=6gfvzdPPIJNGgSXDt2FDnmzg914LTKb84rb4IiYC554=; b=ix7uri1ILEEPiyasmKqakK5ccU2YG24dfCqDDUm43gJDsFxSpoQlzQG6Qa5vAndQXl jMsc70HggeW+6NgiokrIJmXArEGC7yYYQFla6ShFJyEAu682f+SnE7+XfbcrU66ksx4k 4kFZv0Dv44qxaNHR7T52669L7YDxYZP8MT6K0pu3uVwc9FzRsE26xZIDVpEpoMyw28YW MOOhI9tAbzpkS1N0dmHOI8A3Mjy9YteguHhhITQL9vclsticEYAqAYzAg9nbqA/MOwqh 1X/UnNuLY7zn0mc1PHipCaOAx3+hJALDo3nOjHAZK3iZrjkSJ7K3Sx5kaOdlPd/iXTXb 3Yww== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1678797741; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=6gfvzdPPIJNGgSXDt2FDnmzg914LTKb84rb4IiYC554=; b=7AywfIEqvRKLTSuYjKjMhSt3aBgbbv9mmPVjGoeF3XUmZ8LW9xt+Fx5rmsf8Piq7B7 gSNIbZu32Orfky7zhu/e+8yR1tvAn6BaWiz+HLWLWvlcOq7vxP99V/AhveIJOlIiWePo WEmFOONN6I+QTu4cLPj+j5+GrB+7T3FEDwA6ZwlKRTLWTmde27GXttpUi0pOKLV0qXeU Ka3xjBDHB6VNoGPKBNMo8Ho9EX2r3pI3sgUOaPOtAmUQBKLORceTYJw4nflPjQ9qdo8V pN0MvDiU0E7PBWnI8V51CwKtnNJop3m967D21/yJCYTeejXpwlnFzjj/o7D65SSWYeYw v5JQ== X-Gm-Message-State: AO0yUKXigirbmHog2uifiKoq62sskmlx7QjdwE1QY8hMX7OhemofsqxM 8ChNFQD4E1pewgS2fpSRvhakkQ== X-Google-Smtp-Source: AK7set866q8ia7BqTKzVyRrZrn8XKi3vOB+iHtRWLixU8F08+MZkneSL6K4NMfRCAB9Z+YCcxDUR4A== X-Received: by 2002:a05:6a20:1bdd:b0:cd:87ef:3f21 with SMTP id cv29-20020a056a201bdd00b000cd87ef3f21mr36837359pzb.8.1678797741688; Tue, 14 Mar 2023 05:42:21 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.234]) by smtp.gmail.com with ESMTPSA id s11-20020aa7828b000000b005ded5d2d571sm1509385pfm.185.2023.03.14.05.42.19 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 14 Mar 2023 05:42:21 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH v2 2/3] maple_tree: Simplify mas_wr_node_walk() Date: Tue, 14 Mar 2023 20:42:02 +0800 Message-Id: <20230314124203.91572-3-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230314124203.91572-1-zhangpeng.00@bytedance.com> References: <20230314124203.91572-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: AFD68C0014 X-Rspamd-Server: rspam09 X-Rspam-User: X-Stat-Signature: qpx1c1ucqb5yj73h6bybam3o796cef85 X-HE-Tag: 1678797742-180116 X-HE-Meta: U2FsdGVkX1/7at29MgG9BxH5w6hLtj3O9A8XQ/Lky4O54XOuTRhyWIhS93DNYlik03M8XPYUHFuL/HcNjCPbkOfKhAI4z2qh9xKtRyUic8pU06U+UOnN17N/QwRjT+P6B3FErT3YVTdLNAeQXpm4eEjlHNkXDdVCg+UtSpbTUnmpwVvbqlVU0FhbEPyhRxWZJBWR2wKJf+dUUsTD8OcOpVB9J0QM3gYBRIV4Fx/aTktDr9aJVP791MWg7E71pxiJ1Bb9CE2dHnJRcdZEi6koPKUH/2qKPw3YILbylUPgt69L5y888ZfNGB/JQaQx8A8NxEtMtxvTnY1I+gJEdkEqHHJAYjYDpo6bRpSrU5OR1tM1ZB4wvdWvWu5G0SlMa8PjpkOrM5VHXtAc11mInUBPVWbKhDF4UszAYt0IYBGTUoyj9IOw445J7vbLw5gcb5txN4iialacmO6iHhX1A9Aj8XhJCR1ldH6p856UO3cQZPwPaJfdg0rxSipHFk3TYC82yuZmcsHYiVNCL13M2rAeiWMP/wS0e5UaVBu8zrhvbThsHbUDkLGBVsSTaV8i/QF6lQ+p9RNyZXFr/dAIc+2Pcb2tGEjT7f3NI8v7TvrSRP+0bBevdWjCxms1gaEm3ZUF4fqpILVXuODVvdcnM2Zz4T7f3TFQXKVBH2uW0fl6rdXYMPoft3DfztU5Uglph5hnZ9Lu0EZMFEp7v3ep4PPFJgfMss9bg6WNS896FqvhcsqS/pouppPMlVMGmHRwpL04+LtejZb6NkcDTo4D2ZWGv3+wj0IZOA3ofVAaBlh6t21m7Nti0N6iTn04XEcyKIF7XYEs2SuoMsvZGfKJlIpKlbgGv2cYa/dnUuwPPc5vQYWuEngKR5SCxo+YbQ5aXRKnTsEOqe4NT95WEPiBxGr+QexpXicW7mnZDkePWdevuVFRNUnk+5vfmMFQ545rPL4EC0WYqN1SfkJWeGcro7/ J+WasnC/ FRaon6L6vHAPDFGKcKEQmxvnLXKjUG7QSwRj22Zw/vVQaZ4BoFOgmrNdf/+Xxa5e/QDkjzsCC8VN/wa+HICkda3hFwuLaXmTKwnv8eDLsIBYx/tV/yaK+iDXi7HQ8Ib8yt6JNpB1YvO3nsWuM7vqKrQvjso9yAMW3Kq+nyiHcPNucCAyMG1Fb84aVvVsOkeU3dGfrto17Hq0AGMOlkbdVy5k4te+LfHHahl4wSp3aA3xe1pKT1jlquFrdYJczT1aBTu/jGZlPWFeg/BAfunhCJvbQ0x8Fzn0z2GqGJT1D0XON+/Ug2RKTQJtjr75W0shjf9wLjR4qwSThBpl13MFrZ2ZbByZa1Dxe51BqgCAd9jXxs9vuhkOx0q0PP4TTHEgOjvouEGMmSKb51wj4/4K0+tC1X+rW4E4Eg8FySpB5nvBWWtwkUnUwXvasNUbxL3yxbI6HLtMmNFQRCCKj+peHpmOaAhk1pFcVqC2nxl1TuMAY4B8= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Simplify code of mas_wr_node_walk() without changing functionality, and improve readability. Remove some special judgments. Instead of dynamically recording the min and max in the loop, get the final min and max directly at the end. Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- lib/maple_tree.c | 34 +++++----------------------------- 1 file changed, 5 insertions(+), 29 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index b3164266cfde..4d15202a0692 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2251,9 +2251,7 @@ static inline struct maple_enode *mte_node_or_none(struct maple_enode *enode) static inline void mas_wr_node_walk(struct ma_wr_state *wr_mas) { struct ma_state *mas = wr_mas->mas; - unsigned char count; - unsigned char offset; - unsigned long index, min, max; + unsigned char count, offset; if (unlikely(ma_is_dense(wr_mas->type))) { wr_mas->r_max = wr_mas->r_min = mas->index; @@ -2266,34 +2264,12 @@ static inline void mas_wr_node_walk(struct ma_wr_state *wr_mas) count = wr_mas->node_end = ma_data_end(wr_mas->node, wr_mas->type, wr_mas->pivots, mas->max); offset = mas->offset; - min = mas_safe_min(mas, wr_mas->pivots, offset); - if (unlikely(offset == count)) - goto max; - - max = wr_mas->pivots[offset]; - index = mas->index; - if (unlikely(index <= max)) - goto done; - - if (unlikely(!max && offset)) - goto max; - min = max + 1; - while (++offset < count) { - max = wr_mas->pivots[offset]; - if (index <= max) - goto done; - else if (unlikely(!max)) - break; - - min = max + 1; - } + while (offset < count && mas->index > wr_mas->pivots[offset]) + offset++; -max: - max = mas->max; -done: - wr_mas->r_max = max; - wr_mas->r_min = min; + wr_mas->r_max = offset < count ? wr_mas->pivots[offset] : mas->max; + wr_mas->r_min = mas_safe_min(mas, wr_mas->pivots, offset); wr_mas->offset_end = mas->offset = offset; } From patchwork Tue Mar 14 12:42:03 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13174290 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 kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 91D59C6FD1D for ; Tue, 14 Mar 2023 12:42:28 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 2DF186B0078; Tue, 14 Mar 2023 08:42:28 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 28D728E0003; Tue, 14 Mar 2023 08:42:28 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 155F86B007D; Tue, 14 Mar 2023 08:42:28 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id 086256B0078 for ; Tue, 14 Mar 2023 08:42:28 -0400 (EDT) Received: from smtpin20.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id D9248A019D for ; Tue, 14 Mar 2023 12:42:27 +0000 (UTC) X-FDA: 80567467134.20.A17CB0B Received: from mail-pg1-f171.google.com (mail-pg1-f171.google.com [209.85.215.171]) by imf16.hostedemail.com (Postfix) with ESMTP id 10FD818001B for ; Tue, 14 Mar 2023 12:42:25 +0000 (UTC) Authentication-Results: imf16.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=ioJxPaNM; dmarc=pass (policy=none) header.from=bytedance.com; spf=pass (imf16.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.171 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1678797746; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=XK+BKqU6HfXh7xMbbpXKGNWRO1+XUkCbhB/Ff11LzHc=; b=K0Af/7WVGnNxzex4cdF4Fk3T0oknRwBmuWAjObXr2RPfatoHrw/8YKJBFq9+eBo2MOWTTz HZfGAIB4RoUmWPfz3OTHFcDA0BFMOczZZCHdAL94y8ui7PlUaFMI3DbrFX5DntJbmc1lYw 3HrVWpHAvtywFrN8GthsFX2BAunsao0= ARC-Authentication-Results: i=1; imf16.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=ioJxPaNM; dmarc=pass (policy=none) header.from=bytedance.com; spf=pass (imf16.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.171 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1678797746; a=rsa-sha256; cv=none; b=YPjH37vKbfq96CmlHAqkLrB+bbRS3krAqcbcZOku+G+ZrArPYIshbSwovr7CgmAllbBLMJ s8M/XEevImNcpR1p9paeCLyhmXhk9J+UmcfnVYrV3kb4BenBnWgxQ5xgNhvjEPue8PqBJA WPGEpabO/kTM2XNYUDJAOUb8e+Ocf6g= Received: by mail-pg1-f171.google.com with SMTP id h31so8808655pgl.6 for ; Tue, 14 Mar 2023 05:42:25 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1678797744; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=XK+BKqU6HfXh7xMbbpXKGNWRO1+XUkCbhB/Ff11LzHc=; b=ioJxPaNMnP30bTwv1b4MqjbilZtnlKQ9m1hdLXAwZsIGL9l6MV5d4U/YSj+W/3nvNV Ku35QSwZHVI0wCWwz1lxNOn2pyfHnoDzp9HWWmr5MpAlXnIvsHuvDcKqSDSPIsFT7W8R wVHRLuCkrLHPYsENx47uJPNzAhK/PTrJYPmq8hYbjB5uLb9bEk6NqHk5MjthH0X2TVV4 z5m81EIIf6x/uQXAB65ULJPGnSZx4SFKOioo7XNeZuBlpDoHpyfZqtpJ/vrQssKbNQsq nVNT5PABOsTqgFPrvIW3eSDPG7ApKweSPxEkSgE0b3UVV92ZUOizfBMzoJcKaTLRqJjE DDXQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1678797744; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=XK+BKqU6HfXh7xMbbpXKGNWRO1+XUkCbhB/Ff11LzHc=; b=LoloahZmRN4EimRdVVn88EvNJfu0p1KCaH+umLvdRUUJX/4u9O7IRXIhC22lc104Fb W1f/8h4+oSrnTWrAHyQm8dOI1QMbgNa6MS9XsoYLaaMW+Zds/lS+u2uUtmLtlsWNVjl1 yvJ3YvqNB6szQRuIjBFK+SuZHmEWj6CEKmwgcJiSLsA0iIzwdpnD7NY/VQl+WsMS8DZR Kv0uft2jPUnxQUbf7N+X38ro0+qhOZD4Syf8ghsFuo0nhVUjMxyZYjYegVtF46KfL4+P QmpnDUoA9CkBoDOlXVpci22qkAir/hqlVZcKhpZMQ6UiFGVyPaIO4rpowQkz/CvjIcJK 5rPA== X-Gm-Message-State: AO0yUKUM9midGFOdgC8pT4q9OdmvoiZbllFQ52NFghKcquGJhBgWaDmf ZI4I7I7nSW9934OcBlypY0vmT29ZzAPmtaAwOak= X-Google-Smtp-Source: AK7set/nDUsbru5ncTlCJv4TgTsvyXHPDS4DSbVvInYybh9jiXPMSrWHEU2CHjsLEfjfSOlWaZnt9w== X-Received: by 2002:a62:1756:0:b0:625:13f3:9409 with SMTP id 83-20020a621756000000b0062513f39409mr3941069pfx.26.1678797744687; Tue, 14 Mar 2023 05:42:24 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.234]) by smtp.gmail.com with ESMTPSA id s11-20020aa7828b000000b005ded5d2d571sm1509385pfm.185.2023.03.14.05.42.22 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 14 Mar 2023 05:42:24 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH v2 3/3] maple_tree: Fix a potential concurrency bug in RCU mode Date: Tue, 14 Mar 2023 20:42:03 +0800 Message-Id: <20230314124203.91572-4-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230314124203.91572-1-zhangpeng.00@bytedance.com> References: <20230314124203.91572-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: 10FD818001B X-Rspamd-Server: rspam09 X-Rspam-User: X-Stat-Signature: 99ec58atzuto46na9nu8khhbgwycajh3 X-HE-Tag: 1678797745-280422 X-HE-Meta: U2FsdGVkX1/ItMg2ETJGYuG9jFMrY98ne43Z4w9dFhbry/San4LuN8dGmFciQAfMljGEY3H+2k4EU2o4NIe8hVMQymxyyonPWyVA2Xo2D2y2U+tn0GBaAnXSzib1nBmc64m8EyxdhKKatBBYsLxV7f8Y6yhHXQ8liw3txBQt3U1krX62DvVjXKtlxC2Oz2MA6VGc9xoxYKvG5xXhFw/YPce87Ym8S8F+kipu+rqafpJBXeiJCsknDkZudPuUiN/6KXH05eN2r3C6rfZFjGjvvS5IS/IB8FXW0Asq0zlBmaHaz597Ey2j5uHyhdQcboR/RWHUaSQ+SS1wSZIpH7IbBFO8MBvUEYAtFfDrXIjTy/OZ8fRtZ8BHd5RYcj4HrvrltoA0i1WkqdF5OSH7UWa3LSKHaTLX67dl8ebsOZkWicgmiXjWKX8HyNSxRloQy/wjXEZ4VEGAK5pBonHLfM9J82DLoyvZqMstpXTD6dQoC+Bt2b1AEMSNW8VCVMnB0Xncq99nvhY98XnUliB7mXPwSI2tUlW9vmdTbF5knyfHwGzUrQpmDGNt0LnIJ+86+PJrtIAQJQ3L0i/vVDaw4EpwHXi+0iMHHUhvFlXkFBXOw/YXycwGC3PdsvXSZPkVhbZDLwmG0QKHcvTxvm6w/9Cx1hb8mBJ6HSFTdmjwJPIFEPPlx6leTOIGTy/zsGQqhqtA9e/N5MkuV5/iGfdYbMQKvoas4NWvAXHYQsjtwGnXPn0+Y4yatG0d+LXLQD82HkWM1giyL+t9qNxj1bLxH1QNiibU0X/Q22/d8rFkNgVLnUeAYS4YMR1iOLZ3BKfSJzqhCaavH8rpLRGTjvO4wa60PFMAlNqG5LqviwgM4KmQK07f6u9tALTmMWllfe3D+UQmsG8urO1tR9RyRFQm7uyNMn6ou5PPsB8D/rKG0c6HIu+QH0ZuHvUonHWECKIVZ3oVfO7w8r50ZXli0dUf+O5 HVxWOg9f vC/cmy9kjYxILxVbgihqvjIvSln8SxDVNqcWuPI5Kdc3DMj8QV2SVTfIIrnB7bjnhLmRqituwComzkDeJDb4x4mGBe4xVs4GaO2QLF1UZwBcqh9XtzU3nY0M4yOlryQZm76B6+RY0fPVTY/J+3JOJCMzvLjCXrEu46g/QLywo4/G3Ma8bPfV6SoOxRVH0bc6XLJ4FYSema66yp+89cu51WtqbrAUBuBynhuCJcDZdtqksytNj7cacH2s6HUIsZzP8AMfGYDc1cY0qI6YI8fQDgjUM7irV27rXBsDbf8/Fv4Sp0Nns44oo3PLe77iB0hnyGnZkm/mOtTCfqfhng++X0GxSLENwWLLwKVArVBWeg878ezi92U8ZzMbGaDv5gvRimM/rmnd05P3CXIA6a5ikAjKxixFy0d/kuR/sIRjgMlXKb7q5EFkiBfLDJMpP4LAX1Etco10DxkL0Uk24RRFhkPeahNSxuVKrSBMibxPcXuDsweg= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: There is a concurrency bug that may cause the wrong value to be loaded when a CPU is modifying the maple tree. CPU1: mtree_insert_range() mas_insert() mas_store_root() ... mas_root_expand() ... rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); ma_set_meta(node, maple_leaf_64, 0, slot); <---IP CPU2: mtree_load() mtree_lookup_walk() ma_data_end(); When CPU1 is about to execute the instruction pointed to by IP, the ma_data_end() executed by CPU2 may return the wrong end position, which will cause the value loaded by mtree_load() to be wrong. An example of triggering the bug: Add mdelay(100) between rcu_assign_pointer() and ma_set_meta() in mas_root_expand(). static DEFINE_MTREE(tree); int work(void *p) { unsigned long val; for (int i = 0 ; i< 30; ++i) { val = (unsigned long)mtree_load(&tree, 8); mdelay(5); pr_info("%lu",val); } return 0; } mt_init_flags(&tree, MT_FLAGS_USE_RCU); mtree_insert(&tree, 0, (void*)12345, GFP_KERNEL); run_thread(work) mtree_insert(&tree, 1, (void*)56789, GFP_KERNEL); In RCU mode, mtree_load() should always return the value before or after the data structure is modified, and in this example mtree_load(&tree, 8) may return 56789 which is not expected, it should always return NULL. Fix it by put ma_set_meta() before rcu_assign_pointer(). Fixes: 54a611b60590 ("Maple Tree: add new data structure") Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- lib/maple_tree.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 4d15202a0692..de43ff19da72 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3635,10 +3635,9 @@ static inline int mas_root_expand(struct ma_state *mas, void *entry) slot++; mas->depth = 1; mas_set_height(mas); - + ma_set_meta(node, maple_leaf_64, 0, slot); /* swap the new root into the tree */ rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); - ma_set_meta(node, maple_leaf_64, 0, slot); return slot; }