From patchwork Thu Feb 16 05:17:20 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Suren Baghdasaryan X-Patchwork-Id: 13142498 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 53DADC636D7 for ; Thu, 16 Feb 2023 05:18:10 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id DF0556B0080; Thu, 16 Feb 2023 00:18:09 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id DA14F6B0081; Thu, 16 Feb 2023 00:18:09 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id C18EC6B0082; Thu, 16 Feb 2023 00:18:09 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id B1EA86B0080 for ; Thu, 16 Feb 2023 00:18:09 -0500 (EST) Received: from smtpin29.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 81B5AA8E11 for ; Thu, 16 Feb 2023 05:18:09 +0000 (UTC) X-FDA: 80471998698.29.088307F Received: from mail-yb1-f202.google.com (mail-yb1-f202.google.com [209.85.219.202]) by imf24.hostedemail.com (Postfix) with ESMTP id BBF8A180004 for ; Thu, 16 Feb 2023 05:18:07 +0000 (UTC) Authentication-Results: imf24.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b="nzJ7S/CJ"; spf=pass (imf24.hostedemail.com: domain of 3jrztYwYKCOMXZWJSGLTTLQJ.HTRQNSZc-RRPaFHP.TWL@flex--surenb.bounces.google.com designates 209.85.219.202 as permitted sender) smtp.mailfrom=3jrztYwYKCOMXZWJSGLTTLQJ.HTRQNSZc-RRPaFHP.TWL@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=1676524687; 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=rDMlMLTEmJU/Y3crV2atsbCBmpKXyma0yO0OAyc8vDw=; b=CiEE/MTwB64s35oDdAtQgJ/bL9d2woISs4brGfUMUF+jrdR5ssXJtgyjKTEYXPl0rog2PS 8Hvt6aLEpJ3FFRUruwfaNlrV2q5pIzCVq1csr691vkPtEmar3aaaFZqgXiBS49RIyF99px 8mYtfOtos9IuPhdET19QRkpDiWuTpaE= ARC-Authentication-Results: i=1; imf24.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b="nzJ7S/CJ"; spf=pass (imf24.hostedemail.com: domain of 3jrztYwYKCOMXZWJSGLTTLQJ.HTRQNSZc-RRPaFHP.TWL@flex--surenb.bounces.google.com designates 209.85.219.202 as permitted sender) smtp.mailfrom=3jrztYwYKCOMXZWJSGLTTLQJ.HTRQNSZc-RRPaFHP.TWL@flex--surenb.bounces.google.com; dmarc=pass (policy=reject) header.from=google.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1676524687; a=rsa-sha256; cv=none; b=pg1vW61TB5aUPABssz94EVCBNKXRQwyt8y0JouXu6HdY+5/LtehIENffiKYzBlJAfvFvjn uWoVFK9y49U+SUh/fT83HvRIZYj6wILdeZ7jBj7Z1RiLfhXPNZOoRQcmMsuW/bZAH3qCNV x+9E8kT1Lu/+ZJx04dOPrksXl4uqCQw= Received: by mail-yb1-f202.google.com with SMTP id h14-20020a258a8e000000b00827819f87e5so917209ybl.0 for ; Wed, 15 Feb 2023 21:18:07 -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=rDMlMLTEmJU/Y3crV2atsbCBmpKXyma0yO0OAyc8vDw=; b=nzJ7S/CJB/US/rZvNC3fs8J8fXfgfseovx93tCDYzLZ8vkCeR9OXHCG0j7Ki073PZN rg58gpprBwFVBX+ke7DxYuYcgkrSQGYt8YR1LUHO8qrBrJHNZzYIw0fWkCpsF9iepuD5 iMfSL7cYbKTG2WSIKdzRhuGyAIwfPFbrqz4Ug3Wxq2wbPU6P8gVi3bWvRrz9dl4kYYU2 r7gzF5YCRjQDAYOvUYbM1k4rIOQJ+5ffpqKzLjZIEvFTLYyWs4Q62tIpz4Jjx53AOh2l MDbSaQOmeWEl4DEmE5lvlD2J9UkQB4Iedo6XxOd2amw2xyG9CIFDXUp1l5UWlLjXi78n VOeg== 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=rDMlMLTEmJU/Y3crV2atsbCBmpKXyma0yO0OAyc8vDw=; b=WdpvKt5Wl9MBWZ0/MDZdutKOIZPFqhnzbZQ4IomlUpyxNpxGG7TsdwAhiybkXIuiMy OhdS8QifwJnX8kbjLHp6M+/gPJm17f4uz5lg57I5RbBUmrkpFPfIRIdLhR9dED3SdOVu pIhyphhj5adgtqzAg6D7sc8a7/3a4azmERCYipzQgPdXVQ9vWTwi4d2cb+mjI5qyroAX CqKkJ3ISRG7gq56bTvtFxmlTadjDryL5NZcV8BZRIbd+zSPuzXbN9pvx400MTwMlY6A9 z00G58wBPU9LWjptY5ZF0VKaPJAQSHM7VQDHkGvdOaM+GGOuyvpBM3Oaa3OuoGdwRLG/ vVkw== X-Gm-Message-State: AO0yUKWrrF8orwjbKZXlvv6vFQdnAXKLRpi2k7OtFFS+vQO00h6qlr0F yBRD3o2h7Ou9uWsnSGghAMVHNEMytVU= X-Google-Smtp-Source: AK7set/lb47TNs4WZdV/lfneGa3vlSnF3eCz7HT/YLrrRFQlj7qxX88gXTKYg9jHepFjlMCGZaF+lFhq4LY= X-Received: from surenb-desktop.mtv.corp.google.com ([2620:15c:211:200:f781:d5ed:1806:6ebb]) (user=surenb job=sendgmr) by 2002:a81:4309:0:b0:52e:c2c5:b75e with SMTP id q9-20020a814309000000b0052ec2c5b75emr19ywa.2.1676524686391; Wed, 15 Feb 2023 21:18:06 -0800 (PST) Date: Wed, 15 Feb 2023 21:17:20 -0800 In-Reply-To: <20230216051750.3125598-1-surenb@google.com> Mime-Version: 1.0 References: <20230216051750.3125598-1-surenb@google.com> X-Mailer: git-send-email 2.39.1.581.gbfd45094c4-goog Message-ID: <20230216051750.3125598-6-surenb@google.com> Subject: [PATCH v3 05/35] 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-Rspam-User: X-Rspamd-Server: rspam04 X-Rspamd-Queue-Id: BBF8A180004 X-Stat-Signature: w3pjs1378jj1sswyqkbaiw9z8zmaz4s6 X-HE-Tag: 1676524687-760182 X-HE-Meta: U2FsdGVkX19F2cpcDBYCfu2jlJ0U0aUrJ/F1llUid9WG+vc69jm/s2xHR2kosijQMNxc5cCy7kr7ffZZsbiygpf4iNN+OFlIaqqj6hxbWPBLXXzvDPf5BOC4IngECgm7sDJ4jk/45IIsEsU9d3ZzfB3y1QE5KSSfBt53FdUXZMqG26EKXpQgLGGO/96l4MeVPO9XJSk0IN6OpddH1D94GMFIsUwsXDUTxn0l7Hl0L8nJvGVhb7JeL9Dc+FvsfXAclHxZ3kX0KLKnrkmYdTeLhaY7+YG4aYxSGInXeyoU0wNhB3VTihJbyllfSN+0Lt42TMQyuiCOdIOv3FnZvCO38QA1qADmX13lYuYvN9Y9pz0rnDVnhhYXSRBz47vWB9QJ/vzxgwCaCboOWT+QYhsNXwetIPFF12Zdg926ZTwFucFRw+Xih/4srzcIITl2I9SZ4mt6LlPkQ4QKj5UnjRhFlexs2ftMmdGaB857dLsTJ6R40fl3nXh73ddQtHixSQ+8JPgeGOtK88hHOHF/xgiuWPoq7zsVFws2DdjleHKhvKhbt2VkFXCaMDpIfInMJKdQfVhgBzVYkOdBXUBuxlH3320ZyIbNOwfIqUF+06ovj78Tpnl7hqIJEnw5ruZ/i6O17T6Iyfdcncavesa2EJwfuM8na4Ar2k7g4o410g5uAGrZ08ooe+aHCTp1pTcOAj+dfDchHKo18y+SvrEXy619/FJlM0C+KcLDh/mnfdMRi8u+Rx0e8EOBQ2p6XTqecx4BWwICFXXVjdpQvcg/IMGfnqdFw5jAE8aHdcMhJEoTj7InmeCdDLKMggTrM7yt5eX0lVxOQkhEjb5/wOCPow99N1cXpNbAZiP+S7Wukni81nBf7hM6sPUfAMnNTjdvyOpWXMXFbRMqc23anfkGOt2ds5nJiuFAGzV4p0/HV23LAD9UgSPU9Rp9uzmop3Vcbzdsg4qAKtVw1JVd77hs3MR lAoSLPiR p76Mz2bob4QC10J2w7C+ZifUYfZ5tS5gM3MyUFP8L1UT8LX5aC4z6tf+CkDsTd2Ca0/B43qR45f3bIiY4FrfOHhqr0ncKfRj+Yeg/1KWeQFUSX+r+KVLL9U1eWxkB5U4smDsdua7wU02J+1rUBW5+I7x+6o+Wq4JUb7kzp6vMEdjqnzdlq3LwyuTeN6Z6lu5QFKRZhO7Xv/YFpMKTA7KY/9raTFSehkVN4KmDrNPZgbb+yoiDCPeIWsmMvWkHp3XtzfdHgAbuWujpcYdgGYLytNVr82CGt4ViyY3HMOIRWiDXtWjk2V6+w7r+uIICX/MSeFM4rwOUVo56zSrozNTdIn8lab2SBIurNHzOg2/32MhRAvc68Q/Wu4OgxIejYmtsy0T51W6Tla52EGkJsm8q/K3FFPT5Dcz8ng3tTsJNSwWJa51PNNMSxkOTE4MwY67eWSt3O9FHjwXIyOjO2eq9UxTQyTnTSmAftDlY+2v1PhFIR/EO2sX6pMIfeyqhTzDnPSRkURNpDpl7UMAO0NB9kiEoSB39EpnJW48kAFXbmmRgatejv8cOblG+ZW0mlRXh0Ry1lhy57D3SPg57cA87m2o4BWQw2OWLKThdzdO/UbEs+vQ= 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 */