From nobody Wed Feb 11 13:13:14 2026 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 47EB5C6FD1C for ; Tue, 14 Mar 2023 12:43:31 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231303AbjCNMn3 (ORCPT ); Tue, 14 Mar 2023 08:43:29 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59020 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231629AbjCNMnE (ORCPT ); Tue, 14 Mar 2023 08:43:04 -0400 Received: from mail-pj1-x1034.google.com (mail-pj1-x1034.google.com [IPv6:2607:f8b0:4864:20::1034]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 87879A189C for ; Tue, 14 Mar 2023 05:42:19 -0700 (PDT) Received: by mail-pj1-x1034.google.com with SMTP id cn6so2661857pjb.2 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=C4ql3GXnIg8h0FzsI4z6zAv6a3hDFjLx/jEGfcpURks8dxGJPaeiSLnacmH0MtOdVP hgygV1PbOTw0CRrlr3xi0GzqiqUEn/edWZMbGHyyX/q77FNsO7Vv3A5VFarau9nMuYaz l002ro7RzuF2ZXQUtFrxho1B1WvxKsSuoZT1N2BwR3TXuJyxw+IM4rRZB7fabZGWAV3q sHmP+AGK7M+0LtNKbn7bNoA6baYwpMqmkQ+iPq1b+aWWn62BDtfogccL6RikgM+fEA+u bvThKQJi1y8TQrxh4acwdqkxg1QQpZQiMSI/2YA2rjjhuNuTip6aA1ZeH/0QdqNeTQmr wo1A== X-Gm-Message-State: AO0yUKWmNVr5uKJ1vZ2RzM9WkY1yDd4Cv+stJcQ9CZ4IGxd6dpT6eejY OJ8MCyjdmnvB3Bf6kGB7oF5hXQ== 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 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" if (likely(offset > end)) max =3D 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 Reported-by: --- 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_sta= te *mas) end =3D ma_data_end(node, type, pivots, max); if (unlikely(ma_dead_node(node))) goto dead_node; - - if (pivots[offset] >=3D mas->index) - goto next; - do { - offset++; - } while ((offset < end) && (pivots[offset] < mas->index)); - - if (likely(offset > end)) - max =3D pivots[offset]; + if (pivots[offset] >=3D mas->index) { + max =3D pivots[offset]; + break; + } + } while (++offset < end); =20 -next: slots =3D ma_slots(node, type); next =3D mt_slot(mas->tree, slots, offset); if (unlikely(ma_dead_node(node))) --=20 2.20.1 From nobody Wed Feb 11 13:13:14 2026 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 0A256C6FD1D for ; Tue, 14 Mar 2023 12:43:35 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231723AbjCNMnc (ORCPT ); Tue, 14 Mar 2023 08:43:32 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:57810 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231264AbjCNMnK (ORCPT ); Tue, 14 Mar 2023 08:43:10 -0400 Received: from mail-pj1-x102b.google.com (mail-pj1-x102b.google.com [IPv6:2607:f8b0:4864:20::102b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 365FCB479 for ; Tue, 14 Mar 2023 05:42:26 -0700 (PDT) Received: by mail-pj1-x102b.google.com with SMTP id cn6so2661994pjb.2 for ; Tue, 14 Mar 2023 05:42:26 -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=NQQFZJeRa7aKRpKXdQdv/GDJv4FxS3WpfYbzr5UPXAVXsaB9YNwo8wVP7TLAL+kQx/ JXukAicTNBAA9e4xExlwTa0/DUiUBCau6iiDONuVjUibm4hsa6B3YSMtCNwNiiWElNMk +Ja4ontLhKrG5Xgr3ezJ5LYyhZsUTkcVheGstXF9FLbOXPgtfGaK0hF03ZqdLQ+GL2+I MH1a9KKLpd0MOirUih7DIgGlUbq3dMxgnSnkc5P7BqcKGQkJANh8CQpv0jshYmeBgcwZ 5xi+pu90DqvidgmyayEW6gDG/wSOGwv7DWksmHzwzAwjMFFbsrkxXST+gbi+8AienMhL s88g== X-Gm-Message-State: AO0yUKXRvHR8v4txIfphtyx+ZYwtVPzFBtgszS9zISslQslreksWIfxQ JdxqJRWafmH0HTwjGRKVheB/76iRS5A/WmmEqvQ= 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 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" 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 Reported-by: --- 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(st= ruct maple_enode *enode) static inline void mas_wr_node_walk(struct ma_wr_state *wr_mas) { struct ma_state *mas =3D wr_mas->mas; - unsigned char count; - unsigned char offset; - unsigned long index, min, max; + unsigned char count, offset; =20 if (unlikely(ma_is_dense(wr_mas->type))) { wr_mas->r_max =3D wr_mas->r_min =3D mas->index; @@ -2266,34 +2264,12 @@ static inline void mas_wr_node_walk(struct ma_wr_st= ate *wr_mas) count =3D wr_mas->node_end =3D ma_data_end(wr_mas->node, wr_mas->type, wr_mas->pivots, mas->max); offset =3D mas->offset; - min =3D mas_safe_min(mas, wr_mas->pivots, offset); - if (unlikely(offset =3D=3D count)) - goto max; - - max =3D wr_mas->pivots[offset]; - index =3D mas->index; - if (unlikely(index <=3D max)) - goto done; - - if (unlikely(!max && offset)) - goto max; =20 - min =3D max + 1; - while (++offset < count) { - max =3D wr_mas->pivots[offset]; - if (index <=3D max) - goto done; - else if (unlikely(!max)) - break; - - min =3D max + 1; - } + while (offset < count && mas->index > wr_mas->pivots[offset]) + offset++; =20 -max: - max =3D mas->max; -done: - wr_mas->r_max =3D max; - wr_mas->r_min =3D min; + wr_mas->r_max =3D offset < count ? wr_mas->pivots[offset] : mas->max; + wr_mas->r_min =3D mas_safe_min(mas, wr_mas->pivots, offset); wr_mas->offset_end =3D mas->offset =3D offset; } =20 --=20 2.20.1 From nobody Wed Feb 11 13:13:14 2026 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 C8E7BC6FD1C for ; Tue, 14 Mar 2023 12:43:15 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231331AbjCNMnO (ORCPT ); Tue, 14 Mar 2023 08:43:14 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:55410 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231387AbjCNMmu (ORCPT ); Tue, 14 Mar 2023 08:42:50 -0400 Received: from mail-pf1-x433.google.com (mail-pf1-x433.google.com [IPv6:2607:f8b0:4864:20::433]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 87F6D97FE9 for ; Tue, 14 Mar 2023 05:42:27 -0700 (PDT) Received: by mail-pf1-x433.google.com with SMTP id ce7so9608064pfb.9 for ; Tue, 14 Mar 2023 05:42:27 -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=YlS2jwTMM7GNkRhSQikiy7r+PtxojPi14WSV1PTe52W6wz+VmqUkYQInCxCLMDXtic CCAknwdFRuS65QcVwN9LXf4n5djTAA/2d9gy8MUmplIocDh6a4FGifmsR2lfdUyNJq53 yMyKNFS1UQj7hFkOVygtl33HKuB22wtlEK0ALqDXd2iqTSpj4S2wFB8n99pDzRG+VAlJ eKwF3r1Dq3Ol94vrivqIFn3Ar32hRwtqP7tbhn+EsqFvbeSVLxWRsxx84btKErEJPJyf gtsnyRfxuKEE2z0/4T5m+ONaVx/YiFRLKFbwx2DV+d6rJTc9XGHkTv58pD2JGm4sXHc4 qdqw== X-Gm-Message-State: AO0yUKWgFdCQuAlDkvodazisZhYK/nYEpHP5JjWynhfT4oy5Unl9tJq7 ry+9qga8FniA2cVDL73MbWE3Zg== 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 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" 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 =3D 0 ; i< 30; ++i) { val =3D (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 Reported-by: --- 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 *m= as, void *entry) slot++; mas->depth =3D 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; } =20 --=20 2.20.1