From patchwork Fri Jan 27 19:40:42 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Suren Baghdasaryan X-Patchwork-Id: 13119254 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 CEF79C61DA7 for ; Fri, 27 Jan 2023 19:41:52 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 0DDDD6B0089; Fri, 27 Jan 2023 14:41:52 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 068146B008A; Fri, 27 Jan 2023 14:41:52 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id DFD576B008C; Fri, 27 Jan 2023 14:41:51 -0500 (EST) 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 9E8976B0089 for ; Fri, 27 Jan 2023 14:41:51 -0500 (EST) Received: from smtpin13.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 7FEA5AB7E5 for ; Fri, 27 Jan 2023 19:41:51 +0000 (UTC) X-FDA: 80401599222.13.A58535F Received: from mail-pf1-f202.google.com (mail-pf1-f202.google.com [209.85.210.202]) by imf21.hostedemail.com (Postfix) with ESMTP id 2B8B91C000B for ; Fri, 27 Jan 2023 19:41:44 +0000 (UTC) Authentication-Results: imf21.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b=B0QFA0zT; spf=pass (imf21.hostedemail.com: domain of 35SjUYwYKCKwegdQZNSaaSXQ.OaYXUZgj-YYWhMOW.adS@flex--surenb.bounces.google.com designates 209.85.210.202 as permitted sender) smtp.mailfrom=35SjUYwYKCKwegdQZNSaaSXQ.OaYXUZgj-YYWhMOW.adS@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=1674848505; 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=fluAUEldqgo6Mr/4Su/gpwJVTd/f+QKHo7F0iCGeqOg=; b=XSFsMFNcfmHupgz7Ht3Qra/z4cyWvwOu6wQA+dx4iOeEjNj59Wa8mboP2RuyWEwieZy8iu l2TL8NSQbNiN0N9QsH7c1Imf57fEkg99E+lUCFbjnCDr+1jA0NUvlPkl/p9U7F8T7Fkejt sBA9pOaV/UGOV381oEmAGJchKqMX5ho= ARC-Authentication-Results: i=1; imf21.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b=B0QFA0zT; spf=pass (imf21.hostedemail.com: domain of 35SjUYwYKCKwegdQZNSaaSXQ.OaYXUZgj-YYWhMOW.adS@flex--surenb.bounces.google.com designates 209.85.210.202 as permitted sender) smtp.mailfrom=35SjUYwYKCKwegdQZNSaaSXQ.OaYXUZgj-YYWhMOW.adS@flex--surenb.bounces.google.com; dmarc=pass (policy=reject) header.from=google.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1674848505; a=rsa-sha256; cv=none; b=5pMKbVsE9IXKjCOQyfkgJzxcimqq5mph/sHgSniIsRfSJrY9L7rGI2vSc7bSFPJwMeke7o 1tsCDUtMq2b+g3HJOVN2566t+cKtbPyzk7r5KRFLVo8jyMpjB0P5z8/XowsQRv4lJg42Ir Rj5DTi0cGy9pZVktgS7DqBQ9+lz+gfM= Received: by mail-pf1-f202.google.com with SMTP id c5-20020aa78805000000b0058d983c708aso2831864pfo.22 for ; Fri, 27 Jan 2023 11:41:44 -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=fluAUEldqgo6Mr/4Su/gpwJVTd/f+QKHo7F0iCGeqOg=; b=B0QFA0zTTAgJFhNgrdDgKRfLtInL5VmAHE1KFwNYXYIlcWvaJJq1PKzYA8ckdy7Kyn xAwTf5YPOblK6+TJj1tGvdojweaIBaHFiTxRDHhkDnK6qDnyvgtYbq5iiXWxBxOCwUuh WaET5h8CLSuaMj6adU6fJWH6EpE5SqyIKnzFJ/pir1JZwDIco5M5jQ2a/9VWhgwD3iWL QgWDwglZ0wa8AC1rJh0bk86XOm5Sb2wt2duuTU/yqZcdsgUl6ZFLCYWIeCgAmHx4ObRd hHIbD6pxz2ke/VukXpDhoYuOo0GEGrcZQn8DqZwlpC0FiE7wMl7MPAjekSdb7LenTMW0 255w== 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=fluAUEldqgo6Mr/4Su/gpwJVTd/f+QKHo7F0iCGeqOg=; b=I4vdcfttTSIEQV1VE8xumi232mL80QLjrugXZQMap7ibveo5eTm3qZ+bC4BiPMXzQW WlgdJyxD4k0o5iFGuEkqHe7+dHcRpoB1fKCNCSPpzeljJEkzkoGHPpQkxDs79JyOcSF1 R1NVnaOmKHjBwLBfZ0zjCFhgC0C3SZx9WDkamYBmLnWLJNKpau7mw48AxygcDFJlObo6 E6/LVeWDQKbUAHGKE1klSzZYiGkCV8185hOsP5k/GFBl9gyjwGpo5irxFF6qsPthpusZ zY9zMYfpqdTSyAWoGlV1hUNLxPrDEVK0bUwYhm6LZIH1jRYgQxbPcmLdbn8BSnXB+8FS /M7g== X-Gm-Message-State: AO0yUKWVLQDTjGJVn6E01BXtxljCsKKVmwntODNbxg7OiPzcTfgyuAdu Bi5kbpAqO0YQwm85tX0MNoxNVpRd1fo= X-Google-Smtp-Source: AK7set+gvzIFHouo+ELhD7kNJY3eRZqYYIzPpjJr9+paWQDRkxxsh7BJRXlaLIfiaGLvKexw3FDEYkSiOQU= X-Received: from surenb-desktop.mtv.corp.google.com ([2620:15c:211:200:4e19:be9:c5d0:8483]) (user=surenb job=sendgmr) by 2002:a17:90b:a16:b0:225:eaa2:3f5d with SMTP id gg22-20020a17090b0a1600b00225eaa23f5dmr12984pjb.2.1674848485998; Fri, 27 Jan 2023 11:41:25 -0800 (PST) Date: Fri, 27 Jan 2023 11:40:42 -0800 In-Reply-To: <20230127194110.533103-1-surenb@google.com> Mime-Version: 1.0 References: <20230127194110.533103-1-surenb@google.com> X-Mailer: git-send-email 2.39.1.456.gfc5497dd1b-goog Message-ID: <20230127194110.533103-6-surenb@google.com> Subject: [PATCH v2 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, 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, 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, surenb@google.com, "Liam R. Howlett" X-Rspamd-Server: rspam05 X-Rspamd-Queue-Id: 2B8B91C000B X-Stat-Signature: ns3wgkt888wr9kbm1h5ii6xwmjt6fsrx X-Rspam-User: X-HE-Tag: 1674848504-672410 X-HE-Meta: U2FsdGVkX18RDQuCBI/nFsaR1Ygy0O6X/Ix7PRtdJnUS9l+lyCDlv2AmU6QY3xwsTFtwwBmoKKxuKvf5n1+jc6Wewy+ZTvN0c0DK1lQLDIlTJ142tV2A+rvYo53Dgh9BQsFK4aVgvfbfTxxaiQmyTOIhc2z2odJJzicOh9Y1rlCT1wACtx6GJsxPSvifBXh+nZKnWEakNZD4caJHLTix9/qKklUeh2YZWTNWNKGISJvd0L3Jz4AI8j1up1K5vMkD0/G/7m8BqyQyQFp5cdwSw4YkySEmDHo9Gr1sctC0LILzumkLEpimXSOtJO/xEnwgfqzqwIV+zXz6CGASJ+eg4yH7WgNd6rxCdy89g3yy9PH4rYyYeymBh7h+LIiBIaY03w8zE/Mla9REjbdU64NiknZ8+Nr+e8I+rs5Ibl5UTKm35U8siXSieC2pmCb3F7OsYAL6slxxv1nzTq0ejdNfKCUCr60ykg3t3gy/VtJE0byEKDX9gXesPyHBp0YSyrp4prpHwBNzCTY6g63tBVUehzQAbfJelRr1uSTuqKJuL7XR4X24z0SuTvji/aRbHKrveuTlxz2giyqaKoGwDeQrFwVRigkb/kW3pUK+G/rX/x+QKNQU072hxie6Y5IRT6oK22ox91x1F6O2dTv9pjhq01RUSorbyLQ06d4vtr7oPb1Ycr2B22TNGPhbUIpCIxh/3JL/ezAYd2EDdSHhHFaNBo7gU3svuEfBYVIAMEK90Kz5GTtVGoMBXzE15xk0zyOylelgWoKknzXJmMP2Pr33qLoDsl6/QMi8Xutsdk3pdpDRzeL/6xZ9PW0onnlsI2cJr8uMdp+VXYB4tsfsOSeIuROjU8jOK5qleTM0a4gYUv+Mehr5Eulyx/7DQ/OXrFDBiw2dsTXh4EsIZPxCWtA8ZMIQ+i5TfaNWki5JPFThpnuJYQxAj0Vj/wHAH8D3fE4e4qjPUo7KcOHz8++MXeu uaVm9GEY e3tslG1C428Fnn6K7P0B6Bwj9pDJCxOsAIoJfCGLkRmE5Pa/2eKhUUeip1eN8xCd3NgLXd0lvc98hn/jN5xX20ncD9hKdB4uL7pOLJ/98Wo0aA+N5jTyt4hqcBCbIDJpqc2LrvvBd4qJFLEM/kVQgtATdPWC99zcZ/mFfnam8etRrjqXmcaVj/+MBwbJzW7FjbsImUWkImPwSrsQSEl1lMLIEEip8yEFVwu734ZH7xIQMVi79PabNz9ploIr7G8HIQSPFeDlztpV9HRMj88i/P1DZ5ouS8jArwN4bz8k1GBCGcr4cgxoOUQGEfHRr8w8Kyars1aBNlYGM+2wLk8u6k0/xqnHzn7hvP0IdXopPUnviQotZ4whFd4NXVTcEomM1dOwglNbEwOt140z/dH+C5kjbSXmX+NeAaLqZtfJDy6dunJ9xMTOY1Qczrue98h4NVtPkxMSqGO6uBMEbqYCNx4LLrejWPRJGsn5AlIAfgCSLk+G2LGXng3msqvxiOPRsEuE0u9F6XgVJe3wZ1S50JIh8RC7SUVel6c22Tqk3SeyC628gmnku6fJrnns+bxqkQOqJ+ougDJInX1W/MeZRDJBrpW8OfX2ui7rhISokex4uZ9yA55nb+5P+XQLeUoPWLVqBLHtG2UlfflbPXXvxoRx0qEozoaM9nDjWuZxfwUTRGqwc9kAdYLNT4NY/W9/l9DiA 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 75cce2d4d5da..49e399e8afaa 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -178,7 +178,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); } @@ -1771,8 +1771,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); + } } /* @@ -4211,6 +4213,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 */