From mboxrd@z Thu Jan 1 00:00:00 1970 Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.remote-ip=198.137.202.133 ARC-Seal: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; cv=none; t=1793202165; b=Ke8MCNJjao7FJ/dzHCUh6QdxdRSujB89ify0XlDgtdTEy+Ym7oEJQVFspJ2qxGENVsgu b4jAouErRvYst9IMk3nz6SS7Fyd+opkXpzWgI5xWncdY00veu0FxZdtoDG5q3WhIMJK0m 8lEOlFtNuHKXKEKB+cduNqrMhT56MCC2swpAbDYNGysyaIPhEgpjRnVt1mC1J0UQ16YTE YvTFJLhdHX0y/0L4+W7j0y4KVyy4QZdy/1CBF9iGBmI8q8Id/5cQY6cLUKD61s0HoYN8g Um7Dpd5w9o2OGEU6ACk2IzRNj9kJ6vcCFO+yq9npQb6TkqyPs1zfY5IagfV1RR8/SFw== ARC-Message-Signature: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; c=relaxed/relaxed; t=1793202165; h=DMARC-Filter:DKIM-Signature:Received:From:To:Cc:Subject:Date: Message-ID:X-Mailer:In-Reply-To:References:MIME-Version: Content-Transfer-Encoding; bh=x+FxMyc8VBoBJuWtxhwMaxRzj9HBkqwJBoUXFm0B+Fg=; b=f02KSXIiqDapZtKnQvboSPKS+1m7iB+5KY+l2Z96LsVLFO0+Y0JNAjTXs/U+SSzXh3Yx 2rhQzsPSjHtlf+jlF5No27utjyyY0LmzphpRpvAp8+Og5uCxZxq6qYrYhaZSYBBxZ35gP ercM+HA9FdIAh7E0p3SgIbkZWRBJRT8/Dqafu/koJYQohfxc4wrdfDS6kRPKwv0PCW71c h+7FDeckx8DsboKBrYUATcJi8QQaBRh9BI0DufUbgWwxATzcDygduDsfIWm8EgIQUTMHt DzcYXGtBDPDj/nht1PGTen3nTjWoQbICQ26QVIM4P0zbE3fizyIiaT35VubeS4Td06g== ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass header.from=infradead.org; spf=pass smtp.mailfrom=infradead.org; dkim=pass header.d=infradead.org header.i=@infradead.org header.a=rsa-sha256 header.s=bombadil.20210309 header.b=lPiAT+ME; arc=none smtp.remote-ip=198.137.202.133 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (prime256v1) server-digest SHA256) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 11D2C606A31F for ; Wed, 28 Oct 2026 15:42:45 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.4.2 smtp.subspace.kernel.org 11D2C606A31F Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=infradead.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key, unprotected) header.d=infradead.org header.i=@infradead.org header.a=rsa-sha256 header.s=bombadil.20210309 header.b=lPiAT+ME DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20210309; h=Content-Transfer-Encoding: MIME-Version:References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Sender :Reply-To:Content-Type:Content-ID:Content-Description; bh=x+FxMyc8VBoBJuWtxhwMaxRzj9HBkqwJBoUXFm0B+Fg=; b=lPiAT+MERRmJ05OI4LtM24SW5H q6vq8GOmZSheoS0D7L+ZVVQ388CuaC4IF0zid0zVq9dejkrGnXkXVnZyx42Oynvo4RI2R6RaR6XXE oC+QZ+u8lDtuEHpLD540KGfgXT2G415p7z1I20po/MBk5xbNEKC+p1rJrbCURX13+k5SgjmLUZ+VX eZADsxJxTtS9wW2LgbvkYCumTlVj0UH55qhvWVWqjtylCODJokKwkG4iu3A0KJ7R6kfZbfR+vwhAq n28uQ2nZKG34/uNjd4iLhXdd34Nq1I2CF55FBLwqA4GVGcSMxiBjfVa4EWxqBG/55LqNL0tDWfnkA 7zZv9kKA==; Received: from [38.23.173.23] (helo=localhost) by bombadil.infradead.org with esmtpsa (Exim 4.100.1 #2 (Red Hat Linux)) id 1xM5nY-00000007QoX-22zr; Wed, 28 Oct 2026 15:42:44 +0000 From: "Liam R. Howlett (Google)" To: Andrew Morton , Thomas Graf , Herbert Xu Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Lorenzo Stoakes , Chris Mason , Alice Ryhl , Andrew Ballance , "Liam R. Howlett (Google)" Subject: [PATCH 2/4] maple_tree: Test emptying tree while RCU reading Date: Wed, 28 Oct 2026 11:42:16 -0400 Message-ID: <20261028154218.1668182-3-liam@infradead.org> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20261028154218.1668182-1-liam@infradead.org> References: <20261028154218.1668182-1-liam@infradead.org> X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Post: List-Help: List-Subscribe: List-Unsubscribe: List-Owner: Precedence: list MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Add a test case for the rcu reader being restarted by emptying the tree. Signed-off-by: Liam R. Howlett (Google) --- lib/test_maple_tree.c | 129 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 129 insertions(+) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index fb40e193a3cb7..894f5893e1be2 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -3740,6 +3740,134 @@ static noinline void __init check_range64_in_rcu(struct maple_tree *mt) rcu_barrier(); } +/* + * A reader that restarts after its leaf died may find a tree without nodes: + * emptied, or emptied and then given a single entry at 0. Each case starts + * from a tree with nodes, built by check_seq(). The stores run while the + * reader holds rcu_read_lock, so they use GFP_ATOMIC. + */ +static noinline void __init check_restart_no_node(struct maple_tree *mt) +{ + void *ptr = xa_mk_value(1234); + void *entry; + MA_STATE(mas, mt, 0, 0); + + MT_BUG_ON(mt, !mtree_empty(mt)); + mt_set_non_kernel(99999); + + /* find: the tree is emptied */ + mt_init_flags(mt, MT_FLAGS_USE_RCU); + check_seq(mt, 100, false); + rcu_read_lock(); + mas_set(&mas, 0); + entry = mas_find(&mas, ULONG_MAX); + MT_BUG_ON(mt, entry != xa_mk_value(0)); + MT_BUG_ON(mt, mtree_store_range(mt, 0, ULONG_MAX, NULL, GFP_ATOMIC)); + entry = mas_find(&mas, ULONG_MAX); + MT_BUG_ON(mt, entry != NULL); + MT_BUG_ON(mt, mas.status != ma_none); + MT_BUG_ON(mt, mas.index != 0); + MT_BUG_ON(mt, mas.last != ULONG_MAX); + entry = mas_find(&mas, ULONG_MAX); + MT_BUG_ON(mt, entry != NULL); + MT_BUG_ON(mt, mas.status != ma_none); + rcu_read_unlock(); + mtree_destroy(mt); + rcu_barrier(); + + /* next: the tree is emptied */ + mt_init_flags(mt, MT_FLAGS_USE_RCU); + check_seq(mt, 100, false); + rcu_read_lock(); + mas_set(&mas, 0); + entry = mas_find(&mas, ULONG_MAX); + MT_BUG_ON(mt, entry != xa_mk_value(0)); + MT_BUG_ON(mt, mtree_store_range(mt, 0, ULONG_MAX, NULL, GFP_ATOMIC)); + entry = mas_next(&mas, ULONG_MAX); + MT_BUG_ON(mt, entry != NULL); + MT_BUG_ON(mt, mas.status != ma_none); + MT_BUG_ON(mt, mas.index != 0); + MT_BUG_ON(mt, mas.last != ULONG_MAX); + rcu_read_unlock(); + mtree_destroy(mt); + rcu_barrier(); + + /* find: the tree is emptied, then holds one entry at 0 */ + mt_init_flags(mt, MT_FLAGS_USE_RCU); + check_seq(mt, 100, false); + rcu_read_lock(); + mas_set(&mas, 0); + entry = mas_find(&mas, ULONG_MAX); + MT_BUG_ON(mt, entry != xa_mk_value(0)); + MT_BUG_ON(mt, mtree_store_range(mt, 0, ULONG_MAX, NULL, GFP_ATOMIC)); + MT_BUG_ON(mt, mtree_store(mt, 0, ptr, GFP_ATOMIC)); + entry = mas_find(&mas, ULONG_MAX); + MT_BUG_ON(mt, entry != NULL); + MT_BUG_ON(mt, mas.status != ma_none); + MT_BUG_ON(mt, mas.index != 1); + MT_BUG_ON(mt, mas.last != ULONG_MAX); + rcu_read_unlock(); + mtree_destroy(mt); + rcu_barrier(); + + /* find_rev: the tree is emptied */ + mt_init_flags(mt, MT_FLAGS_USE_RCU); + check_seq(mt, 100, false); + rcu_read_lock(); + mas_set(&mas, ULONG_MAX); + entry = mas_find_rev(&mas, 0); + MT_BUG_ON(mt, entry != xa_mk_value(100)); + MT_BUG_ON(mt, mtree_store_range(mt, 0, ULONG_MAX, NULL, GFP_ATOMIC)); + entry = mas_find_rev(&mas, 0); + MT_BUG_ON(mt, entry != NULL); + MT_BUG_ON(mt, mas.status != ma_none); + MT_BUG_ON(mt, mas.index != 0); + MT_BUG_ON(mt, mas.last != ULONG_MAX); + entry = mas_find_rev(&mas, 0); + MT_BUG_ON(mt, entry != NULL); + MT_BUG_ON(mt, mas.status != ma_none); + rcu_read_unlock(); + mtree_destroy(mt); + rcu_barrier(); + + /* prev: the tree is emptied, then holds one entry at 0 */ + mt_init_flags(mt, MT_FLAGS_USE_RCU); + check_seq(mt, 100, false); + rcu_read_lock(); + mas_set(&mas, ULONG_MAX); + entry = mas_find_rev(&mas, 0); + MT_BUG_ON(mt, entry != xa_mk_value(100)); + MT_BUG_ON(mt, mtree_store_range(mt, 0, ULONG_MAX, NULL, GFP_ATOMIC)); + MT_BUG_ON(mt, mtree_store(mt, 0, ptr, GFP_ATOMIC)); + entry = mas_prev(&mas, 0); + MT_BUG_ON(mt, entry != ptr); + MT_BUG_ON(mt, mas.status != ma_root); + MT_BUG_ON(mt, mas.index != 0); + MT_BUG_ON(mt, mas.last != 0); + rcu_read_unlock(); + mtree_destroy(mt); + rcu_barrier(); + + /* find_rev: the entry at 0 is below the minimum */ + mt_init_flags(mt, MT_FLAGS_USE_RCU); + check_seq(mt, 100, false); + rcu_read_lock(); + mas_set(&mas, ULONG_MAX); + entry = mas_find_rev(&mas, 1); + MT_BUG_ON(mt, entry != xa_mk_value(100)); + MT_BUG_ON(mt, mtree_store_range(mt, 0, ULONG_MAX, NULL, GFP_ATOMIC)); + MT_BUG_ON(mt, mtree_store(mt, 0, ptr, GFP_ATOMIC)); + entry = mas_find_rev(&mas, 1); + MT_BUG_ON(mt, entry != NULL); + MT_BUG_ON(mt, mas.status != ma_root); + MT_BUG_ON(mt, mas.index != 0); + MT_BUG_ON(mt, mas.last != 0); + rcu_read_unlock(); + mtree_destroy(mt); + rcu_barrier(); + mt_set_non_kernel(0); +} + static DEFINE_MTREE(tree); static int __init maple_tree_seed(void) { @@ -4031,6 +4159,7 @@ static int __init maple_tree_seed(void) check_range64_in_rcu(&tree); + check_restart_no_node(&tree); #if defined(BENCH) skip: -- 2.47.3