From patchwork Mon Feb 27 17:36:04 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Suren Baghdasaryan X-Patchwork-Id: 13153968 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 B7C6AC64ED8 for ; Mon, 27 Feb 2023 17:36:54 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 5303B6B0081; Mon, 27 Feb 2023 12:36:54 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 4DF8B6B0082; Mon, 27 Feb 2023 12:36:54 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 359676B0083; Mon, 27 Feb 2023 12:36:54 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0013.hostedemail.com [216.40.44.13]) by kanga.kvack.org (Postfix) with ESMTP id 2769E6B0081 for ; Mon, 27 Feb 2023 12:36:54 -0500 (EST) Received: from smtpin12.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id D0BD1AAF4F for ; Mon, 27 Feb 2023 17:36:53 +0000 (UTC) X-FDA: 80513777106.12.70FB05E Received: from mail-pg1-f201.google.com (mail-pg1-f201.google.com [209.85.215.201]) by imf29.hostedemail.com (Postfix) with ESMTP id 052B2120022 for ; Mon, 27 Feb 2023 17:36:50 +0000 (UTC) Authentication-Results: imf29.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b=mjTDCe3u; spf=pass (imf29.hostedemail.com: domain of 3Mer8YwYKCCAOQNAJ7CKKCHA.8KIHEJQT-IIGR68G.KNC@flex--surenb.bounces.google.com designates 209.85.215.201 as permitted sender) smtp.mailfrom=3Mer8YwYKCCAOQNAJ7CKKCHA.8KIHEJQT-IIGR68G.KNC@flex--surenb.bounces.google.com; dmarc=pass (policy=reject) header.from=google.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1677519411; 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-type:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=9Ei1aTodbgKgkLCHkAcrfXghqfC4aFVkwG1NwHfqe18=; b=PJ3Y3L8cxGecGgkKHufPAleZh0vJRKX8TI92Tmj1wtcByh7wJ7sfkvGRoC41Nww28tWEQk d/2i4FIh/dgKiIfLqbBy2xgV2dhaG8DAUQVr0P3AkdVHhSJ/Lnid+PhtAFo29Q5bRt8dsR /elF7MOsCnYJuQ4dndwg7Aw7xKPBWEU= ARC-Authentication-Results: i=1; imf29.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b=mjTDCe3u; spf=pass (imf29.hostedemail.com: domain of 3Mer8YwYKCCAOQNAJ7CKKCHA.8KIHEJQT-IIGR68G.KNC@flex--surenb.bounces.google.com designates 209.85.215.201 as permitted sender) smtp.mailfrom=3Mer8YwYKCCAOQNAJ7CKKCHA.8KIHEJQT-IIGR68G.KNC@flex--surenb.bounces.google.com; dmarc=pass (policy=reject) header.from=google.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1677519411; a=rsa-sha256; cv=none; b=x8jCEULJ2+4514FMCTb+L/D5/g3cQD495KJXNJw//TrCb6336h/UzEdi10eo3KoUnVgNG/ Mp/jp3pOSTCHwBh91g0vdUzivVsYPCaBUK+C/K6CUpcSc/F1oZfGjiCuF8bFolCyJxaz/k Ym5W49Mnge3/mQVpc0OuH3lnf/Rmmlc= Received: by mail-pg1-f201.google.com with SMTP id h19-20020a63f913000000b00502f20ab936so2202836pgi.20 for ; Mon, 27 Feb 2023 09:36:50 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20210112; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=9Ei1aTodbgKgkLCHkAcrfXghqfC4aFVkwG1NwHfqe18=; b=mjTDCe3um0lc/xjVfVjgd+Npe9HefebnR6MJBHLvf3YF1uIBfRxVZUnFRJLGFeQ5Qn 8RjZv63JPHIbjxEVYDv4CrjZbJnnn4Mt2fDeT1LOlyG88MFvPDh3biXldQxmJDhFfhkL MeulbY1wD03auJFox9o7eR+S24BryOLDDsTTZGQeZ4URN1aDTRabL9SThEbzRf62X937 1Tp2+9t6o/KfoCPMJmoRWi+E8Rd5yccUzXxzvOPdrAcdSgNX0Ahh/fjHi6t+VXE449Oh mngGw09qy20HWkPARPiqIZAx0mZi+xWfyiKlsc96M1s7LVT+aejv+nyRL84gn5iOqmCZ H2mg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=9Ei1aTodbgKgkLCHkAcrfXghqfC4aFVkwG1NwHfqe18=; b=YN5MklP1jPYv3wK5ekssP8S17/h0MonZQ9cZ0+YQSkp+5J5n9RjtenUbVT90TBheAd 1wVNF3azxzt5vXtIz9mJRm0nTWKP1NpuK369Cg/cPzB1K0aPBAXO5vjAQNM9MXJF/F3F xbiNPPeropUFKtGVM3AX8UJ5jjNy0dfS2FeAFDT6tctom+8cR3SU5BGAcBbSHLWG0Qli AkCBgiL2uBbRcECxWl5L+jc4FpGvG4Ce/PFg50URhSjPzWdKYafwXJbPYAtZite0MN9/ N7m5sr6ecWwn0OuYSNymrcfeG5Iurtv9im8dyFyzV0FFZSSbQkGjFnSzTaLWACv13riN rypg== X-Gm-Message-State: AO0yUKXOd0F3WUAwZ7HshKTG+roKhmMfxjeQ+QQdkgREcTR9odjeyoUi d6LNbipNSrZQRExCDytaZ3m1SIgB/W0= X-Google-Smtp-Source: AK7set8gSrJb7C7al4vp6knawTGaEfFTfMkKKVc0fZqqef6Oc8nGI6YkUfCL0eSaXZ77p/UxVJxZTTA+0vM= X-Received: from surenb-desktop.mtv.corp.google.com ([2620:15c:211:200:e1f6:21d1:eead:3897]) (user=surenb job=sendgmr) by 2002:a63:714f:0:b0:4fc:2058:fa2b with SMTP id b15-20020a63714f000000b004fc2058fa2bmr6283546pgn.3.1677519409843; Mon, 27 Feb 2023 09:36:49 -0800 (PST) Date: Mon, 27 Feb 2023 09:36:04 -0800 In-Reply-To: <20230227173632.3292573-1-surenb@google.com> Mime-Version: 1.0 References: <20230227173632.3292573-1-surenb@google.com> X-Mailer: git-send-email 2.39.2.722.g9855ee24e9-goog Message-ID: <20230227173632.3292573-6-surenb@google.com> Subject: [PATCH v4 05/33] maple_tree: Fix write memory barrier of nodes once dead for RCU mode From: Suren Baghdasaryan To: akpm@linux-foundation.org Cc: michel@lespinasse.org, jglisse@google.com, mhocko@suse.com, vbabka@suse.cz, hannes@cmpxchg.org, mgorman@techsingularity.net, dave@stgolabs.net, willy@infradead.org, liam.howlett@oracle.com, peterz@infradead.org, ldufour@linux.ibm.com, paulmck@kernel.org, mingo@redhat.com, will@kernel.org, luto@kernel.org, songliubraving@fb.com, peterx@redhat.com, david@redhat.com, dhowells@redhat.com, hughd@google.com, bigeasy@linutronix.de, kent.overstreet@linux.dev, punit.agrawal@bytedance.com, lstoakes@gmail.com, peterjung1337@gmail.com, rientjes@google.com, chriscli@google.com, axelrasmussen@google.com, joelaf@google.com, minchan@google.com, rppt@kernel.org, jannh@google.com, shakeelb@google.com, tatashin@google.com, edumazet@google.com, gthelen@google.com, gurua@google.com, arjunroy@google.com, soheil@google.com, leewalsh@google.com, posk@google.com, michalechner92@googlemail.com, linux-mm@kvack.org, linux-arm-kernel@lists.infradead.org, linuxppc-dev@lists.ozlabs.org, x86@kernel.org, linux-kernel@vger.kernel.org, kernel-team@android.com, "Liam R. Howlett" , Suren Baghdasaryan X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: 052B2120022 X-Rspam-User: X-Stat-Signature: 3teut3cf9i49zn5asw4sxcsdnbdqu9dp X-HE-Tag: 1677519410-133002 X-HE-Meta: U2FsdGVkX18pSJ2Jrls0FjeDuyyYHV7IyFn5IsQeI0nGZOkRZ+6iCCs9so6kMVHOzZKU9Ysae/yh27DQfRdRBe74SldYyRVEHrIqI7+2iDoa2X0jc8/oorMe/Vo+jdeEiB7YousfHU/WSTku1om2Hox6LmM0JjY4INXhMOTK8qZt5DMN6hbAgatGDO9PvIH4Wiylzn0KmvtFDoUyji1I42xmvd8uHzB/W7zu352XcfPD4vjf0QGvWOx2m5fqUjUg4+QBJhgAzXkozkyqSsSH6x6YllLaXC/bw1mTMQmUBcZqirlQMsUzabeDPcjdmWPq/P5CAk7U1XYQvAUb+BazqQ8/qzR5tT+12fGEIfQ++Mn4jQ7PjERSqTdvCTLUakw6py3mz9b+gjYt5w111mB0H+0VRXk6AXFu+2jo1gfIJSv1e0nOdC24mzQQgssgWdy5zO+iJv04bebgeT20JLCDsxDxUZj8Y7DpASeVS42w1rtETWJSNlc9imSFXCkw135B0JGn4+pDjGyV4PCM/fh84aS/VDq29ar22cWBk7XqBgzNpoxVWhFrMqi5S8p6aKh7FYV1a6U1Cv/e09KGSfDSAjtMe6j1NmBQVmefHYZRG524Bro4KbxgpOZ1Fw/KEUHShnTSnHhuiGLMj+Txnh3VA5IprCXiPxCaiOkSASlNxeARFmnS0LB0CGSI0tfump2E5jiRjtvhMroNsA4HvMS/0o+tGDTBfJaICk0R9YMKpGIRDf5LsSsj2i8PNhKR3EFtJJhV8/oq+pAYdMEILOhZB/ylQb9I1RDC09pxRyXZEISIqPlcTAxYV46NpVTcFVRzt4GY0E2RCERz2s6pEekwJtMfcsB+zuy2/tMI+K73OTD4/kJkXzYKCCiJvoYdzY+ngmQbTY4UqxbsdMZqPA3FBgDDAVbTYo934IBgg90V5/YYy1hNLckBu1R1M+5/uFR2j6UCCCJmwG2ecZSsft1 /mBP2HgN MzzAWPn/zUGRPGm5aqLa8adzvVZqFBniuyoXS2znz5yopATjrYf5dC3Zl/7vZhIug9p/Nac1cElyrOdWHQqr2u1LR+Tsm6teJlZmL8MrpnFP7TVXGpVOr7lwO+mpew1ZMBlXQ8tywNRO/htaH7ZoDIc40T35yZFhrAmKT+k6OW4lo49bbH/S33fLgQ4yn2v8fDKVgK/3vFOIJuGyjDgEiuhbL1s2wMm74w2f0MQ3P+EZN3QtRObe1KR8BT6lqdB/a5ty/fGfBpdTDItyVT0Ja0yQgAyDzR1slWcUymKR6pc7ogvlCdKuWylbTJKCQdXMCEpyzq98R2VLh3NOycn3ADyWD6bSaxzPfam7MMMzszi3s6bCVxlOmu4XnhrEK7AvJTV3yz+k6rti0CuZWVQScMqSOF7s1A0HQIYZXOyDpGAPX80jDVGDT7yTtfpvzhATvZQG3L8rIObtY9C/0H9/OxT9VALKrtleWuebCVFxrEcVKEdCh1BEqg6WXWl2kpN+V7WCRCmtbZvXc6BM488/51kqzFvdr9HgSmgerx3hnAzlx20tvSdV67QPC6KAFgUHOY1UJHlOi448fFxD5yd24cJbgBkGE7O+WCYX39l1PeHtv9eh9wcq99pZF0Y84UlpLphiOhzPuNSr5WIRRRVPgll7vJp+gs1A09Iqk+B3JNdDs/ll0Qqzq5dN/ki9iPZeh5ET8 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: From: "Liam R. Howlett" During the development of the maple tree, the strategy of freeing multiple nodes changed and, in the process, the pivots were reused to store pointers to dead nodes. To ensure the readers see accurate pivots, the writers need to mark the nodes as dead and call smp_wmb() to ensure any readers can identify the node as dead before using the pivot values. There were two places where the old method of marking the node as dead without smp_wmb() were being used, which resulted in RCU readers seeing the wrong pivot value before seeing the node was dead. Fix this race condition by using mte_set_node_dead() which has the smp_wmb() call to ensure the race is closed. Add a WARN_ON() to the ma_free_rcu() call to ensure all nodes being freed are marked as dead to ensure there are no other call paths besides the two updated paths. This is necessary for the RCU mode of the maple tree. Fixes: 54a611b60590 ("Maple Tree: add new data structure") Signed-off-by: Liam R. Howlett Signed-off-by: Suren Baghdasaryan --- lib/maple_tree.c | 7 +++++-- tools/testing/radix-tree/maple.c | 16 ++++++++++++++++ 2 files changed, 21 insertions(+), 2 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 3d5ab02f981a..6b6eddadd9d2 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -185,7 +185,7 @@ static void mt_free_rcu(struct rcu_head *head) */ static void ma_free_rcu(struct maple_node *node) { - node->parent = ma_parent_ptr(node); + WARN_ON(node->parent != ma_parent_ptr(node)); call_rcu(&node->rcu, mt_free_rcu); } @@ -1778,8 +1778,10 @@ static inline void mas_replace(struct ma_state *mas, bool advanced) rcu_assign_pointer(slots[offset], mas->node); } - if (!advanced) + if (!advanced) { + mte_set_node_dead(old_enode); mas_free(mas, old_enode); + } } /* @@ -4218,6 +4220,7 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas) done: mas_leaf_set_meta(mas, newnode, dst_pivots, maple_leaf_64, new_end); if (in_rcu) { + mte_set_node_dead(mas->node); mas->node = mt_mk_node(newnode, wr_mas->type); mas_replace(mas, false); } else { diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index 958ee9bdb316..4c89ff333f6f 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -108,6 +108,7 @@ static noinline void check_new_node(struct maple_tree *mt) MT_BUG_ON(mt, mn->slot[1] != NULL); MT_BUG_ON(mt, mas_allocated(&mas) != 0); + mn->parent = ma_parent_ptr(mn); ma_free_rcu(mn); mas.node = MAS_START; mas_nomem(&mas, GFP_KERNEL); @@ -160,6 +161,7 @@ static noinline void check_new_node(struct maple_tree *mt) MT_BUG_ON(mt, mas_allocated(&mas) != i); MT_BUG_ON(mt, !mn); MT_BUG_ON(mt, not_empty(mn)); + mn->parent = ma_parent_ptr(mn); ma_free_rcu(mn); } @@ -192,6 +194,7 @@ static noinline void check_new_node(struct maple_tree *mt) MT_BUG_ON(mt, not_empty(mn)); MT_BUG_ON(mt, mas_allocated(&mas) != i - 1); MT_BUG_ON(mt, !mn); + mn->parent = ma_parent_ptr(mn); ma_free_rcu(mn); } @@ -210,6 +213,7 @@ static noinline void check_new_node(struct maple_tree *mt) mn = mas_pop_node(&mas); MT_BUG_ON(mt, not_empty(mn)); MT_BUG_ON(mt, mas_allocated(&mas) != j - 1); + mn->parent = ma_parent_ptr(mn); ma_free_rcu(mn); } MT_BUG_ON(mt, mas_allocated(&mas) != 0); @@ -233,6 +237,7 @@ static noinline void check_new_node(struct maple_tree *mt) MT_BUG_ON(mt, mas_allocated(&mas) != i - j); mn = mas_pop_node(&mas); MT_BUG_ON(mt, not_empty(mn)); + mn->parent = ma_parent_ptr(mn); ma_free_rcu(mn); MT_BUG_ON(mt, mas_allocated(&mas) != i - j - 1); } @@ -269,6 +274,7 @@ static noinline void check_new_node(struct maple_tree *mt) mn = mas_pop_node(&mas); /* get the next node. */ MT_BUG_ON(mt, mn == NULL); MT_BUG_ON(mt, not_empty(mn)); + mn->parent = ma_parent_ptr(mn); ma_free_rcu(mn); } MT_BUG_ON(mt, mas_allocated(&mas) != 0); @@ -294,6 +300,7 @@ static noinline void check_new_node(struct maple_tree *mt) mn = mas_pop_node(&mas2); /* get the next node. */ MT_BUG_ON(mt, mn == NULL); MT_BUG_ON(mt, not_empty(mn)); + mn->parent = ma_parent_ptr(mn); ma_free_rcu(mn); } MT_BUG_ON(mt, mas_allocated(&mas2) != 0); @@ -334,10 +341,12 @@ static noinline void check_new_node(struct maple_tree *mt) MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 2); mn = mas_pop_node(&mas); MT_BUG_ON(mt, not_empty(mn)); + mn->parent = ma_parent_ptr(mn); ma_free_rcu(mn); for (i = 1; i <= MAPLE_ALLOC_SLOTS + 1; i++) { mn = mas_pop_node(&mas); MT_BUG_ON(mt, not_empty(mn)); + mn->parent = ma_parent_ptr(mn); ma_free_rcu(mn); } MT_BUG_ON(mt, mas_allocated(&mas) != 0); @@ -375,6 +384,7 @@ static noinline void check_new_node(struct maple_tree *mt) mas_node_count(&mas, i); /* Request */ mas_nomem(&mas, GFP_KERNEL); /* Fill request */ mn = mas_pop_node(&mas); /* get the next node. */ + mn->parent = ma_parent_ptr(mn); ma_free_rcu(mn); mas_destroy(&mas); @@ -382,10 +392,13 @@ static noinline void check_new_node(struct maple_tree *mt) mas_node_count(&mas, i); /* Request */ mas_nomem(&mas, GFP_KERNEL); /* Fill request */ mn = mas_pop_node(&mas); /* get the next node. */ + mn->parent = ma_parent_ptr(mn); ma_free_rcu(mn); mn = mas_pop_node(&mas); /* get the next node. */ + mn->parent = ma_parent_ptr(mn); ma_free_rcu(mn); mn = mas_pop_node(&mas); /* get the next node. */ + mn->parent = ma_parent_ptr(mn); ma_free_rcu(mn); mas_destroy(&mas); } @@ -35369,6 +35382,7 @@ static noinline void check_prealloc(struct maple_tree *mt) MT_BUG_ON(mt, allocated != 1 + height * 3); mn = mas_pop_node(&mas); MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1); + mn->parent = ma_parent_ptr(mn); ma_free_rcu(mn); MT_BUG_ON(mt, mas_preallocate(&mas, GFP_KERNEL) != 0); mas_destroy(&mas); @@ -35386,6 +35400,7 @@ static noinline void check_prealloc(struct maple_tree *mt) mas_destroy(&mas); allocated = mas_allocated(&mas); MT_BUG_ON(mt, allocated != 0); + mn->parent = ma_parent_ptr(mn); ma_free_rcu(mn); MT_BUG_ON(mt, mas_preallocate(&mas, GFP_KERNEL) != 0); @@ -35756,6 +35771,7 @@ void farmer_tests(void) tree.ma_root = mt_mk_node(node, maple_leaf_64); mt_dump(&tree); + node->parent = ma_parent_ptr(node); ma_free_rcu(node); /* Check things that will make lockdep angry */