From patchwork Mon Jan 9 20:53:00 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Suren Baghdasaryan X-Patchwork-Id: 13094271 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 B6B52C61DB3 for ; Mon, 9 Jan 2023 20:53:56 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 4B6268E0009; Mon, 9 Jan 2023 15:53:56 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 466948E0001; Mon, 9 Jan 2023 15:53:56 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 3076E8E0009; Mon, 9 Jan 2023 15:53:56 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id 20F8D8E0001 for ; Mon, 9 Jan 2023 15:53:56 -0500 (EST) Received: from smtpin28.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id F05F8AB11A for ; Mon, 9 Jan 2023 20:53:55 +0000 (UTC) X-FDA: 80336462430.28.7F3E2AC Received: from mail-yb1-f201.google.com (mail-yb1-f201.google.com [209.85.219.201]) by imf04.hostedemail.com (Postfix) with ESMTP id 57B814000D for ; Mon, 9 Jan 2023 20:53:54 +0000 (UTC) Authentication-Results: imf04.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b=XZhB0Mur; spf=pass (imf04.hostedemail.com: domain of 34X68YwYKCPQoqnajXckkcha.Ykihejqt-iigrWYg.knc@flex--surenb.bounces.google.com designates 209.85.219.201 as permitted sender) smtp.mailfrom=34X68YwYKCPQoqnajXckkcha.Ykihejqt-iigrWYg.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=1673297634; a=rsa-sha256; cv=none; b=KkGTDcq9BKZnBBnYCSEKrzg4tMBkjWHAJOahg0VtQl9y7T28bhheeY42ICQSx4hGwzeB5X 21iUgWX96r1dr7AOKWLyjicndpMMsLnwocDehaGUzZdseI/uYuvbScTb0eBqDYvAcdK5DV sNNeqaIfiVoGNgEgSa3sKVyKgIkD+9Y= ARC-Authentication-Results: i=1; imf04.hostedemail.com; dkim=pass header.d=google.com header.s=20210112 header.b=XZhB0Mur; spf=pass (imf04.hostedemail.com: domain of 34X68YwYKCPQoqnajXckkcha.Ykihejqt-iigrWYg.knc@flex--surenb.bounces.google.com designates 209.85.219.201 as permitted sender) smtp.mailfrom=34X68YwYKCPQoqnajXckkcha.Ykihejqt-iigrWYg.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=1673297634; 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=r/ByKXL5/TL05Cni5RZ8/3QBk5f4BKrzjgLm3Nsczuc=; b=sr/bj4SbmzCiQZzRFNS5OmV6dhPTA2OM9WZLRiS0IgM4olViueV4Z1a5s067UR7Dmcs8BW izLoluCCf8Cj0KmNomqBTsG5mtr5vCvn0zi+HCLfTw0ypvX7cmkBFCyh4sbtHmmx10pQDa vBWL0XiXx1T1WYBBuL7hUJK9JlaK6s8= Received: by mail-yb1-f201.google.com with SMTP id 81-20020a250b54000000b007c002e178dfso1324296ybl.9 for ; Mon, 09 Jan 2023 12:53:54 -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=r/ByKXL5/TL05Cni5RZ8/3QBk5f4BKrzjgLm3Nsczuc=; b=XZhB0MurOIdgvWrQwu+hJ2lSxOQT+CHAxznZAlATY9tL6yBOIdJSyl09j7qs++7K6+ +noh5D5/c9QmPEOhqfvJHyQwq3kACUyssJheSfMwcYViJIFHS1/y1fiRpO9p3lukpSo8 zurDxJt/kmbPIHQRSNmtoT5iYyxem6gKfY8wpBL8JKkSoFXDKg0JciA3ABN5+4Pa/8FZ Svy0a58Amowv53Vk76UKApMAQ9ZprfLfSHlZL0fWzl8fmhDrZgAmkrOVH9/RFI/nNlnR WsAxkAJv9sUdL+8FTIMmDBza+16v8vXL8ENtWQu+olGHSLyyl/6A++OsnTnGdWDPMYeD K8RA== 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=r/ByKXL5/TL05Cni5RZ8/3QBk5f4BKrzjgLm3Nsczuc=; b=k1ipAbJIIrEmeKqsr3ZKJs6BXjKDrAQIaqSGUHExMXINJCNyqGJFqKGoMLezlin+fk Hfvamw9/UK0kZ9tkht0y+Ic/lkL1Iarnfnp4m3+8TeMmIXdOCQMXwj0KbD8a3EkSQfVJ DkzEASxEigw3nnSKH55A7zll3OtDjt6KneKMJMWovJDZeJ2JwPgnOQQmVX2JzfiBvF2U MEvMkh2ZEUCaTGnDYO3S1eKIj5EfLN3RR6BPEs9492Se/T+z5SzlkazLXkONK8ubXArx tTjWMrhTHeOW9pIjrHKO28icefu0suXDmf6/pRGShAow733XVuqMBB57ysAo1L7eRRQl UB5A== X-Gm-Message-State: AFqh2krfY7IwYdsWhzPv3taZC2Y+FFr7fKCkTfHq/i0pdYkHoL0zVWbJ Pt4EL0qeeO2bTd/Cc5y+X6GycE53K6s= X-Google-Smtp-Source: AMrXdXv6pxAJ0Ez+UVi7qfPaeqrQmlVnO2LvHLtbQu4X0J/l7RkUZy3CJtaYn7PIXuCjX2fZCm6e/eZrYK0= X-Received: from surenb-desktop.mtv.corp.google.com ([2620:15c:211:200:9393:6f7a:d410:55ca]) (user=surenb job=sendgmr) by 2002:a0d:f007:0:b0:388:941:23a8 with SMTP id z7-20020a0df007000000b00388094123a8mr1505536ywe.152.1673297633444; Mon, 09 Jan 2023 12:53:53 -0800 (PST) Date: Mon, 9 Jan 2023 12:53:00 -0800 In-Reply-To: <20230109205336.3665937-1-surenb@google.com> Mime-Version: 1.0 References: <20230109205336.3665937-1-surenb@google.com> X-Mailer: git-send-email 2.39.0.314.g84b9a713c41-goog Message-ID: <20230109205336.3665937-6-surenb@google.com> Subject: [PATCH 05/41] 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, laurent.dufour@fr.ibm.com, paulmck@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, jannh@google.com, shakeelb@google.com, tatashin@google.com, edumazet@google.com, gthelen@google.com, gurua@google.com, arjunroy@google.com, soheil@google.com, hughlynch@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-Rspam-User: X-Rspamd-Queue-Id: 57B814000D X-Rspamd-Server: rspam01 X-Stat-Signature: pq4f6a1y4i91j3h6ecop1wqchonfmjb8 X-HE-Tag: 1673297634-420735 X-HE-Meta: U2FsdGVkX1/3zekSpojF3H7e8rWRvMWjKmsJQ5xtJavgHIfxh7UYtCIHzCRufJaZTi2tBADgVC3s5B44gotUDZSf0QKwHrFcZq+D3kR7EzfD5MtsHshk8wdjed6iKx5YQFMh5Y8rTQTKegFiNDwbio9j32UfzhYKpMxGx6WoU3/nPlLOJ6///R65uDPEvZ0AtreaVUbBOIwodDPg5khWKR2TcG1F3CKFFYQ5d9NnNcTtW/WDDIDwtl1uY20dLCuapGBR2ztL7BZB5MXVc412l7AUf8+vEvoHkUxHOvVQMe/xTfgMdPNq1ILOjbzTzFIKrtBBXO2kqvH+TsJ+oMlQRm94GOVcZuOEuY6+YVxhVuA7d7/yGPYfZq7irQcbiVHOX0jaNo6LyzctmrLpY/KhJ5dfXKlIuQrpGneclcPjt4dhjTrOuqP2FubIgFCeNVjO/a0AONBiKo6Uy8sbcX6PH7sftewlTvkPTnXIkb6o3VIPi7FU1k+eWcyx8jsEBd+KXIUIzNqAA+VwG0B1/rU8lKeF6VbIYx0wRJ4lL996RJLA7xLVtCDIYJm9yQj57vSkf4kmzDQSLHWCBzSD7EyyMFC0bbruSzp28gFqPu8qvh113ggsHquks9t/OXc661lYbwIAbgODmfKjiQz+jalaIAoR+C0+BIJ7V+8wncAFHrsKbQPf6CGGupvmHY2QO8KaIuwYTBmQRcbO7fxv0ozGoMqXU7Ay650gzF/uP1ImAOkW2rdwnyWgdjHCVWNxx427/Oio2qBqUzorUxmEHHyJaFvm7GzlXbszNA0nRQ6+qI+/Gs6p0JHtoY2AMcp0K1CD75ouFKPad9tq6atXy0CQZkW2AP3vRE+bsmJ7yHl6rGAip98JGuwAd9vQvc4uVWBND1nWBhbtG6RiNv4kqdWK4u/Yx93tXYEuAWd+0CjGT+EN4P+JdNV0GvfdV3K2Vim6tLajk0nsXVoJ30lIiBp 9wEFHD8d TP/DRC0pM2gK8Jpvql59yAAzVY/YVj9gH6M4YAGHpyTNLaKlCrPMXeHFAoAINvSNWgPKcH6IUgeUy+kfV2wAsxV/vA9lc+L10677WmPJdgeXACNtMndJr9x/gShcI6wKBY6wfUIIMrYb1hTb7uMVmhr8LU4wxME+yTvky9t3L6gy/F0jnx2/MShETXLVjuElAFJ9rH/AcJEx5XikBeKCzHRA/xfX1e78TFrK9hzBMfKxpnFjx4qA9K+UFl9UO1Pja9bzehIkKfbasgbkF9yjTV0XLOHOTgpBGTXoIW0OruOUsY3puhxUOTDkOKxr4WaeDchohiHnyW5DYqkFYL3gksUYYfIEXLh3y6LljNwUKeKeOYnPif7UzWHQHR0Xcwi183ouH7KKYGnFIQC/HAJvaBr+cTPs4XSlx2Hix 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 d85291b19f86..8066fb1e8ec9 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -179,7 +179,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); } @@ -1775,8 +1775,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); + } } /* @@ -4217,6 +4219,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 81fa7ec2e66a..2539ad6c4777 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, ptr, 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, ptr, 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 */