From nobody Sun Sep 14 01:47:19 2025 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 1378BC54EAA for ; Fri, 27 Jan 2023 19:43:10 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231980AbjA0TnI (ORCPT ); Fri, 27 Jan 2023 14:43:08 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:50624 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231859AbjA0Tm5 (ORCPT ); Fri, 27 Jan 2023 14:42:57 -0500 Received: from mail-pf1-x44a.google.com (mail-pf1-x44a.google.com [IPv6:2607:f8b0:4864:20::44a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 497B68242F for ; Fri, 27 Jan 2023 11:42:30 -0800 (PST) Received: by mail-pf1-x44a.google.com with SMTP id cr14-20020a056a000f0e00b0058da951c487so2786838pfb.0 for ; Fri, 27 Jan 2023 11:42:30 -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=zS84MyA4LiNIUaKu8tV8iiqiew1AwtBjNR252+XwRk/medbzfToEY5qFEQ+zBpSsJj VAi2TtzuhCBPjIui0ouzulTOHIDGtJeeX3ah+kpczFIBLuYLvbq+bcajcBiKW8+Qn4fw Bdl8dok5pWKoRaJICgbTF8uwKj3wELoV0gnx7zoM3K7B9lzTqsK2mTlUumSL31iMxYWj ckOtsW2wpqzHU6ee0rEGprHhJpjc3suqfz22jNb+7F14s7jBeLJ1sW4zxIMFotfHluPR KZhibpltSKLFSBynLXMYlQ7Jsun9rQfZwEuDrP1NIFUc+/SH7hxcuhEOBSHmQrAv8U5v l5aw== X-Gm-Message-State: AO0yUKXtDRsuF/qLUIR2cHZLt3zCNlQALXhEus6lHnEsvexDxod/az77 CYR2Pkg1ef53Db3jlwySejXsmbQ3S9Q= 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" Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" 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 =3D ma_parent_ptr(node); + WARN_ON(node->parent !=3D ma_parent_ptr(node)); call_rcu(&node->rcu, mt_free_rcu); } =20 @@ -1771,8 +1771,10 @@ static inline void mas_replace(struct ma_state *mas,= bool advanced) rcu_assign_pointer(slots[offset], mas->node); } =20 - if (!advanced) + if (!advanced) { + mte_set_node_dead(old_enode); mas_free(mas, old_enode); + } } =20 /* @@ -4211,6 +4213,7 @@ static inline bool mas_wr_node_store(struct ma_wr_sta= te *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 =3D 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/ma= ple.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] !=3D NULL); MT_BUG_ON(mt, mas_allocated(&mas) !=3D 0); =20 + mn->parent =3D ma_parent_ptr(mn); ma_free_rcu(mn); mas.node =3D 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) !=3D i); MT_BUG_ON(mt, !mn); MT_BUG_ON(mt, not_empty(mn)); + mn->parent =3D ma_parent_ptr(mn); ma_free_rcu(mn); } =20 @@ -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) !=3D i - 1); MT_BUG_ON(mt, !mn); + mn->parent =3D ma_parent_ptr(mn); ma_free_rcu(mn); } =20 @@ -210,6 +213,7 @@ static noinline void check_new_node(struct maple_tree *= mt) mn =3D mas_pop_node(&mas); MT_BUG_ON(mt, not_empty(mn)); MT_BUG_ON(mt, mas_allocated(&mas) !=3D j - 1); + mn->parent =3D ma_parent_ptr(mn); ma_free_rcu(mn); } MT_BUG_ON(mt, mas_allocated(&mas) !=3D 0); @@ -233,6 +237,7 @@ static noinline void check_new_node(struct maple_tree *= mt) MT_BUG_ON(mt, mas_allocated(&mas) !=3D i - j); mn =3D mas_pop_node(&mas); MT_BUG_ON(mt, not_empty(mn)); + mn->parent =3D ma_parent_ptr(mn); ma_free_rcu(mn); MT_BUG_ON(mt, mas_allocated(&mas) !=3D i - j - 1); } @@ -269,6 +274,7 @@ static noinline void check_new_node(struct maple_tree *= mt) mn =3D mas_pop_node(&mas); /* get the next node. */ MT_BUG_ON(mt, mn =3D=3D NULL); MT_BUG_ON(mt, not_empty(mn)); + mn->parent =3D ma_parent_ptr(mn); ma_free_rcu(mn); } MT_BUG_ON(mt, mas_allocated(&mas) !=3D 0); @@ -294,6 +300,7 @@ static noinline void check_new_node(struct maple_tree *= mt) mn =3D mas_pop_node(&mas2); /* get the next node. */ MT_BUG_ON(mt, mn =3D=3D NULL); MT_BUG_ON(mt, not_empty(mn)); + mn->parent =3D ma_parent_ptr(mn); ma_free_rcu(mn); } MT_BUG_ON(mt, mas_allocated(&mas2) !=3D 0); @@ -334,10 +341,12 @@ static noinline void check_new_node(struct maple_tree= *mt) MT_BUG_ON(mt, mas_allocated(&mas) !=3D MAPLE_ALLOC_SLOTS + 2); mn =3D mas_pop_node(&mas); MT_BUG_ON(mt, not_empty(mn)); + mn->parent =3D ma_parent_ptr(mn); ma_free_rcu(mn); for (i =3D 1; i <=3D MAPLE_ALLOC_SLOTS + 1; i++) { mn =3D mas_pop_node(&mas); MT_BUG_ON(mt, not_empty(mn)); + mn->parent =3D ma_parent_ptr(mn); ma_free_rcu(mn); } MT_BUG_ON(mt, mas_allocated(&mas) !=3D 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 =3D mas_pop_node(&mas); /* get the next node. */ + mn->parent =3D ma_parent_ptr(mn); ma_free_rcu(mn); mas_destroy(&mas); =20 @@ -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 =3D mas_pop_node(&mas); /* get the next node. */ + mn->parent =3D ma_parent_ptr(mn); ma_free_rcu(mn); mn =3D mas_pop_node(&mas); /* get the next node. */ + mn->parent =3D ma_parent_ptr(mn); ma_free_rcu(mn); mn =3D mas_pop_node(&mas); /* get the next node. */ + mn->parent =3D ma_parent_ptr(mn); ma_free_rcu(mn); mas_destroy(&mas); } @@ -35369,6 +35382,7 @@ static noinline void check_prealloc(struct maple_tr= ee *mt) MT_BUG_ON(mt, allocated !=3D 1 + height * 3); mn =3D mas_pop_node(&mas); MT_BUG_ON(mt, mas_allocated(&mas) !=3D allocated - 1); + mn->parent =3D ma_parent_ptr(mn); ma_free_rcu(mn); MT_BUG_ON(mt, mas_preallocate(&mas, GFP_KERNEL) !=3D 0); mas_destroy(&mas); @@ -35386,6 +35400,7 @@ static noinline void check_prealloc(struct maple_tr= ee *mt) mas_destroy(&mas); allocated =3D mas_allocated(&mas); MT_BUG_ON(mt, allocated !=3D 0); + mn->parent =3D ma_parent_ptr(mn); ma_free_rcu(mn); =20 MT_BUG_ON(mt, mas_preallocate(&mas, GFP_KERNEL) !=3D 0); @@ -35756,6 +35771,7 @@ void farmer_tests(void) tree.ma_root =3D mt_mk_node(node, maple_leaf_64); mt_dump(&tree); =20 + node->parent =3D ma_parent_ptr(node); ma_free_rcu(node); =20 /* Check things that will make lockdep angry */ --=20 2.39.1