[PATCH v2 0/3] maple_tree fixes for 7.3

[PATCH v2 0/3] maple_tree fixes for 7.3

[Liam R. Howlett (Google)]

Two bugs found by an LLM review, and one problem Lorenzo Stoakes
reported off list.

An RCU reader that restarts after its node dies can dereference NULL if
the tree was emptied, or holds a single entry in the root pointer.
Patch 1 fixes it and patch 2 adds a test.

With CONFIG_DEBUG_MAPLE_TREE, MT_WARN_ON() and the other WARN macros
print the tree and call dump_stack() rather than WARN(), so syzbot never
sees them.  Patch 3 makes them WARN once per call site, after the dump,
and makes the BUG macros BUG() after theirs.  The userspace tests make
WARN() fatal to keep failing as they did on dump_stack().

Changes since v1:
- Drop rhashtable patch.  It is still undecided and will go to linux-crypto
- A reverse walk from index 0 returned the new root entry a second time;
  fixed and tested (Andrew's review bot)
- Fixes tags point at the commits that introduced the problems
- The WARN macros' once state is reset by clear_warn_once
- WARN() is fatal in maple-shared.h (Lorenzo); the maple test exits
  non-zero on a failure

Liam R. Howlett (Google) (3):
  maple_tree: Fix rcu reader NULL dereference after the tree is emptied
  maple_tree: Test emptying tree while RCU reading
  maple_tree: Update internal warning and bug_on code

 include/linux/maple_tree.h          |  48 ++++----
 lib/maple_tree.c                    | 112 ++++++++++++++-----
 lib/test_maple_tree.c               | 165 ++++++++++++++++++++++++++++
 tools/testing/radix-tree/maple.c    |  13 ++-
 tools/testing/shared/maple-shared.h |  33 ++++++
 5 files changed, 316 insertions(+), 55 deletions(-)

-- 
2.47.3

[PATCH v2 1/3] maple_tree: Fix rcu reader NULL dereference after the tree is emptied

[Liam R. Howlett (Google)]

RCU readers may hit a NULL dereference if the tree is emptied while the
walker is restarted from a dead node.  Avoid the NULL dereference by
checking for an emptied/pointer tree (0->ptr, 1-ULONG_MAX -> NULL) and
set the maple state limits correctly.

A reader of /proc/<pid>/maps racing with an munmap() of the whole
address space can hit this.  The first implementation has the same
problem in both directions.

Initial fix was generated by LLM and sent by Chris Mason in private.

Cc: <stable@vger.kernel.org>
Fixes: 54a611b60590 ("Maple Tree: add new data structure")
Reported-by: Chris Mason <mason@kernel.org>
Signed-off-by: Liam R. Howlett (Google) <liam@infradead.org>
---
 lib/maple_tree.c | 112 +++++++++++++++++++++++++++++++++++------------
 1 file changed, 85 insertions(+), 27 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 0b0036c9f8489..a36dc20af84c4 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -3891,14 +3891,56 @@ static __always_inline void mas_rewalk(struct ma_state *mas, unsigned long index
 		goto retry;
 }
 
-static __always_inline bool mas_rewalk_if_dead(struct ma_state *mas,
-		struct maple_node *node, const unsigned long index)
+/*
+ * mas_next_no_node() - Finish a next walk that restarted into a tree without
+ * nodes.
+ * @mas: The inactive maple state (ma_none or ma_root)
+ *
+ * The arrival here is either because there is a root value or nothing.  Either
+ * way, the next entry is nothing.  So set the limits and overwrite the status.
+ *
+ * Return: NULL
+ */
+static inline void *mas_next_no_node(struct ma_state *mas)
 {
-	if (unlikely(ma_dead_node(node))) {
-		mas_rewalk(mas, index);
-		return true;
+	if (mas_is_ptr(mas))
+		mas->index = 1;
+	else
+		mas->index = 0;
+
+	mas->last = ULONG_MAX;
+	mas->status = ma_none;
+	return NULL;
+}
+
+/*
+ * mas_prev_no_node() - Finish a prev walk that restarted into a tree without
+ * nodes.
+ * @mas: The inactive maple state (ma_none or ma_root)
+ * @index: The start of the range the walk left
+ * @min: The lowest index to return
+ *
+ * The arrival here is either because there is a root value or nothing.  With
+ * nothing, leave the limits mas_walk() sets for an empty tree.  A root value
+ * sits at 0: stop on it as mas_prev_setup() does, unless the walk was at 0.
+ *
+ * Return: The root entry if @index and @min allow it, NULL otherwise.  A node
+ * if the root changed again since the walk; the caller restarts.
+ */
+static inline void *mas_prev_no_node(struct ma_state *mas, unsigned long index,
+		unsigned long min)
+{
+	mas->index = 0;
+	if (mas_is_none(mas)) {
+		mas->last = ULONG_MAX;
+		return NULL;
 	}
-	return false;
+
+	mas->last = 0;
+	if (!index || min)
+		return NULL;
+
+	return mas_root(mas);
 }
 
 /*
@@ -4006,14 +4048,14 @@ static void *mas_prev_slot(struct ma_state *mas, unsigned long min, bool empty)
 	node = mas_mn(mas);
 	type = mte_node_type(mas->node);
 	pivots = ma_pivots(node, type);
-	if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
-		goto retry;
+	if (unlikely(ma_dead_node(node)))
+		goto dead;
 
 	if (mas->min <= min) {
 		pivot = mas_safe_min(mas, pivots, mas->offset);
 
-		if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
-			goto retry;
+		if (unlikely(ma_dead_node(node)))
+			goto dead;
 
 		if (pivot <= min)
 			goto underflow;
@@ -4028,10 +4070,8 @@ static void *mas_prev_slot(struct ma_state *mas, unsigned long min, bool empty)
 		if (mas->index <= min)
 			goto underflow;
 
-		if (mas_prev_node(mas, min)) {
-			mas_rewalk(mas, save_point);
-			goto retry;
-		}
+		if (mas_prev_node(mas, min))
+			goto dead;
 
 		if (WARN_ON_ONCE(mas_is_underflow(mas)))
 			return NULL;
@@ -4045,8 +4085,8 @@ static void *mas_prev_slot(struct ma_state *mas, unsigned long min, bool empty)
 
 	slots = ma_slots(node, type);
 	entry = mas_slot(mas, slots, mas->offset);
-	if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
-		goto retry;
+	if (unlikely(ma_dead_node(node)))
+		goto dead;
 
 	if (likely(entry))
 		return entry;
@@ -4063,6 +4103,17 @@ static void *mas_prev_slot(struct ma_state *mas, unsigned long min, bool empty)
 underflow:
 	mas->status = ma_underflow;
 	return NULL;
+
+dead:
+	mas_rewalk(mas, save_point);
+	if (likely(mas_is_active(mas)))
+		goto retry;
+
+	entry = mas_prev_no_node(mas, save_point, min);
+	if (unlikely(xa_is_node(entry))) /* The root changed again */
+		goto dead;
+
+	return entry;
 }
 
 /*
@@ -4176,8 +4227,8 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty)
 	node = mas_mn(mas);
 	type = mte_node_type(mas->node);
 	pivots = ma_pivots(node, type);
-	if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
-		goto retry;
+	if (unlikely(ma_dead_node(node)))
+		goto dead;
 
 	if (mas->max >= max) {
 		if (likely(mas->offset < mas->end))
@@ -4185,8 +4236,8 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty)
 		else
 			pivot = mas->max;
 
-		if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
-			goto retry;
+		if (unlikely(ma_dead_node(node)))
+			goto dead;
 
 		if (pivot >= max) { /* Was at the limit, next will extend beyond */
 			mas->status = ma_overflow;
@@ -4208,10 +4259,8 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty)
 			return NULL;
 		}
 
-		if (mas_next_node(mas, node, max)) {
-			mas_rewalk(mas, save_point);
-			goto retry;
-		}
+		if (mas_next_node(mas, node, max))
+			goto dead;
 
 		if (WARN_ON_ONCE(mas_is_overflow(mas)))
 			return NULL;
@@ -4226,8 +4275,8 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty)
 
 	slots = ma_slots(node, type);
 	entry = mt_slot(mas->tree, slots, mas->offset);
-	if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
-		goto retry;
+	if (unlikely(ma_dead_node(node)))
+		goto dead;
 
 	if (entry)
 		return entry;
@@ -4244,6 +4293,13 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty)
 	}
 
 	return entry;
+
+dead:
+	mas_rewalk(mas, save_point);
+	if (likely(mas_is_active(mas)))
+		goto retry;
+
+	return mas_next_no_node(mas);
 }
 
 /*
@@ -5450,7 +5506,9 @@ void *mas_find(struct ma_state *mas, unsigned long max)
 	/* Retries on dead nodes handled by mas_next_slot */
 	entry = mas_next_slot(mas, max, false);
 	/* Ignore overflow */
-	mas->status = ma_active;
+	if (mas_is_overflow(mas))
+		mas->status = ma_active;
+
 	return entry;
 }
 EXPORT_SYMBOL_GPL(mas_find);
-- 
2.47.3

[PATCH v2 2/3] maple_tree: Test emptying tree while RCU reading

[Liam R. Howlett (Google)]

Add a test case for the rcu reader being restarted by emptying the tree.
A reverse walk from index 0 must not return the new root entry.

Signed-off-by: Liam R. Howlett (Google) <liam@infradead.org>
---
 lib/test_maple_tree.c | 165 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 165 insertions(+)

diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
index fb40e193a3cb7..10e5577ea0f19 100644
--- a/lib/test_maple_tree.c
+++ b/lib/test_maple_tree.c
@@ -3740,6 +3740,170 @@ 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();
+
+	/* find_rev: the reader is at 0 when the tree gets 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_rev(&mas, 0);
+	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_rev(&mas, 0);
+	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();
+
+	/* find_range_rev: the reader is at 0 when the tree gets 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_range_rev(&mas, 0);
+	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_range_rev(&mas, 0);
+	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 +4195,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

[PATCH v2 3/3] maple_tree: Update internal warning and bug_on code

[Liam R. Howlett (Google)]

When CONFIG_DEBUG_MAPLE_TREE is set, call WARN_ON() once per site after
the custom information is dumped about the tree.  Without using the
kernel's WARN_ON calls, syzbot will not catch issues detected by this
code.  The BUG_ON variants now stop instead of dumping and continuing.

Update the non-debug code to call WARN_ON_ONCE() as well.

The userspace tests asserted on dump_stack() but only print on
WARN_ON(), so make WARN() fatal in maple-shared.h and have the maple
test exit with the result of maple_tree_seed().

Cc: <stable@vger.kernel.org>
Reported-by: Lorenzo Stoakes <ljs@kernel.org>
Fixes: f0a1f866aba1 ("maple_tree: add debug BUG_ON and WARN_ON variants")
Signed-off-by: Liam R. Howlett (Google) <liam@infradead.org>
---
 include/linux/maple_tree.h          | 48 ++++++++++++++---------------
 tools/testing/radix-tree/maple.c    | 13 +++++---
 tools/testing/shared/maple-shared.h | 33 ++++++++++++++++++++
 3 files changed, 66 insertions(+), 28 deletions(-)

diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
index e30e57f5f3df9..3a9751c6689fc 100644
--- a/include/linux/maple_tree.h
+++ b/include/linux/maple_tree.h
@@ -680,7 +680,7 @@ void mt_cache_shrink(void);
 		pr_info("Pass: %u Run:%u\n",				\
 			atomic_read(&maple_tree_tests_passed),		\
 			atomic_read(&maple_tree_tests_run));		\
-		dump_stack();						\
+		BUG_ON(1);						\
 	} else {							\
 		atomic_inc(&maple_tree_tests_passed);			\
 	}								\
@@ -696,7 +696,7 @@ void mt_cache_shrink(void);
 		pr_info("Pass: %u Run:%u\n",				\
 			atomic_read(&maple_tree_tests_passed),		\
 			atomic_read(&maple_tree_tests_run));		\
-		dump_stack();						\
+		BUG_ON(1);						\
 	} else {							\
 		atomic_inc(&maple_tree_tests_passed);			\
 	}								\
@@ -713,7 +713,7 @@ void mt_cache_shrink(void);
 		pr_info("Pass: %u Run:%u\n",				\
 			atomic_read(&maple_tree_tests_passed),		\
 			atomic_read(&maple_tree_tests_run));		\
-		dump_stack();						\
+		BUG_ON(1);						\
 	} else {							\
 		atomic_inc(&maple_tree_tests_passed);			\
 	}								\
@@ -722,16 +722,16 @@ void mt_cache_shrink(void);
 #define MT_WARN_ON(__tree, __x)  ({					\
 	int ret = !!(__x);						\
 	atomic_inc(&maple_tree_tests_run);				\
-	if (ret) {							\
-		pr_info("WARN at %s:%d (%u)\n",				\
-		__func__, __LINE__, __x);				\
+	if (!ret) {							\
+		atomic_inc(&maple_tree_tests_passed);			\
+	} else if (__ONCE_LITE_IF(ret)) {				\
+		pr_info("WARN at %s:%d\n",				\
+		__func__, __LINE__);					\
 		mt_dump(__tree, mt_dump_hex);				\
 		pr_info("Pass: %u Run:%u\n",				\
 			atomic_read(&maple_tree_tests_passed),		\
 			atomic_read(&maple_tree_tests_run));		\
-		dump_stack();						\
-	} else {							\
-		atomic_inc(&maple_tree_tests_passed);			\
+		WARN_ON(1);						\
 	}								\
 	unlikely(ret);							\
 })
@@ -739,17 +739,17 @@ void mt_cache_shrink(void);
 #define MAS_WARN_ON(__mas, __x) ({					\
 	int ret = !!(__x);						\
 	atomic_inc(&maple_tree_tests_run);				\
-	if (ret) {							\
-		pr_info("WARN at %s:%d (%u)\n",				\
-		__func__, __LINE__, __x);				\
+	if (!ret) {							\
+		atomic_inc(&maple_tree_tests_passed);			\
+	} else if (__ONCE_LITE_IF(ret)) {				\
+		pr_info("WARN at %s:%d\n",				\
+		__func__, __LINE__);					\
 		mas_dump(__mas);					\
 		mt_dump((__mas)->tree, mt_dump_hex);			\
 		pr_info("Pass: %u Run:%u\n",				\
 			atomic_read(&maple_tree_tests_passed),		\
 			atomic_read(&maple_tree_tests_run));		\
-		dump_stack();						\
-	} else {							\
-		atomic_inc(&maple_tree_tests_passed);			\
+		WARN_ON(1);						\
 	}								\
 	unlikely(ret);							\
 })
@@ -757,18 +757,18 @@ void mt_cache_shrink(void);
 #define MAS_WR_WARN_ON(__wrmas, __x) ({					\
 	int ret = !!(__x);						\
 	atomic_inc(&maple_tree_tests_run);				\
-	if (ret) {							\
-		pr_info("WARN at %s:%d (%u)\n",				\
-		__func__, __LINE__, __x);				\
+	if (!ret) {							\
+		atomic_inc(&maple_tree_tests_passed);			\
+	} else if (__ONCE_LITE_IF(ret)) {				\
+		pr_info("WARN at %s:%d\n",				\
+		__func__, __LINE__);					\
 		mas_wr_dump(__wrmas);					\
 		mas_dump((__wrmas)->mas);				\
 		mt_dump((__wrmas)->mas->tree, mt_dump_hex);		\
 		pr_info("Pass: %u Run:%u\n",				\
 			atomic_read(&maple_tree_tests_passed),		\
 			atomic_read(&maple_tree_tests_run));		\
-		dump_stack();						\
-	} else {							\
-		atomic_inc(&maple_tree_tests_passed);			\
+		WARN_ON(1);						\
 	}								\
 	unlikely(ret);							\
 })
@@ -776,9 +776,9 @@ void mt_cache_shrink(void);
 #define MT_BUG_ON(__tree, __x)		BUG_ON(__x)
 #define MAS_BUG_ON(__mas, __x)		BUG_ON(__x)
 #define MAS_WR_BUG_ON(__mas, __x)	BUG_ON(__x)
-#define MT_WARN_ON(__tree, __x)		WARN_ON(__x)
-#define MAS_WARN_ON(__mas, __x)		WARN_ON(__x)
-#define MAS_WR_WARN_ON(__mas, __x)	WARN_ON(__x)
+#define MT_WARN_ON(__tree, __x)		WARN_ON_ONCE(__x)
+#define MAS_WARN_ON(__mas, __x)		WARN_ON_ONCE(__x)
+#define MAS_WR_WARN_ON(__mas, __x)	WARN_ON_ONCE(__x)
 #endif /* CONFIG_DEBUG_MAPLE_TREE */
 
 /**
diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
index bfe4b8626c429..846c67e20e82a 100644
--- a/tools/testing/radix-tree/maple.c
+++ b/tools/testing/radix-tree/maple.c
@@ -36502,22 +36502,27 @@ static void regression_tests(void)
 	test_spanning_store_regression();
 }
 
-void maple_tree_tests(void)
+int maple_tree_tests(void)
 {
+	int ret;
+
 #if !defined(BENCH)
 	regression_tests();
 	farmer_tests();
 #endif
-	maple_tree_seed();
+	ret = maple_tree_seed();
 	maple_tree_harvest();
+	return ret;
 }
 
 int __weak main(void)
 {
+	int ret;
+
 	maple_tree_init();
-	maple_tree_tests();
+	ret = maple_tree_tests();
 	rcu_barrier();
 	if (nr_allocated)
 		printf("nr_allocated = %d\n", nr_allocated);
-	return 0;
+	return ret ? EXIT_FAILURE : EXIT_SUCCESS;
 }
diff --git a/tools/testing/shared/maple-shared.h b/tools/testing/shared/maple-shared.h
index 2a1e9a8594a28..5f827709773a0 100644
--- a/tools/testing/shared/maple-shared.h
+++ b/tools/testing/shared/maple-shared.h
@@ -8,6 +8,7 @@
 #include "shared.h"
 #include <stdlib.h>
 #include <time.h>
+#include <assert.h>
 #include "linux/init.h"
 
 void maple_rcu_cb(struct rcu_head *head);
@@ -20,5 +21,37 @@ do {                                            \
     call_rcu(&((_p_struct)->_memb), rcu_cb);    \
 } while(0);
 
+/* Make WARN() fatal */
+#undef WARN
+#undef WARN_ON
+#undef WARN_ONCE
+#undef WARN_ON_ONCE
+#define WARN(condition, format...) ({				\
+	int __ret_warn_on = !!(condition);			\
+	if (unlikely(__ret_warn_on)) {				\
+		__WARN_printf(format);				\
+		assert(0);					\
+	}							\
+	unlikely(__ret_warn_on);				\
+})
+#define WARN_ON(condition)					\
+	WARN(condition, "assertion failed at %s:%d\n", __FILE__, __LINE__)
+#define WARN_ONCE(condition, format...)	WARN(condition, format)
+#define WARN_ON_ONCE(condition)		WARN_ON(condition)
+
+/* Once state for the debug macros */
+#ifndef __ONCE_LITE_IF
+#define __ONCE_LITE_IF(condition)				\
+	({							\
+		static bool __already_done;			\
+		bool __ret_once = false;			\
+								\
+		if ((condition) && !__already_done) {		\
+			__already_done = true;			\
+			__ret_once = true;			\
+		}						\
+		__ret_once;					\
+	})
+#endif
 
 #endif /* __MAPLE_SHARED_H__ */
-- 
2.47.3

Re: [PATCH v2 1/3] maple_tree: Fix rcu reader NULL dereference after the tree is emptied

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] maple_tree: race in mas_prev_slot() when root is emptied after mas_rewalk()
--

commit edc2da191bb5cf8aae2a20e02f12ca0a680681ac
Author: Liam R. Howlett (Google) <liam@infradead.org>

maple_tree: Fix rcu reader NULL dereference after the tree is emptied

This commit fixes a NULL dereference when RCU readers restart a forward or
reverse walk from a dead node after the maple tree has been emptied or
reduced to a single root pointer.

> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 0b0036c9f8489..a36dc20af84c4 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -3891,14 +3891,56 @@ static __always_inline void mas_rewalk(struct ma_state *mas, unsigned long index
[ ... ]
> +static inline void *mas_prev_no_node(struct ma_state *mas, unsigned long index,
> +		unsigned long min)
> +{
> +	mas->index = 0;
> +	if (mas_is_none(mas)) {
> +		mas->last = ULONG_MAX;
> +		return NULL;
> +	}
> +
> +	mas->last = 0;
> +	if (!index || min)
> +		return NULL;
> +
> +	return mas_root(mas);
>  }
[ ... ]
> @@ -4063,6 +4103,17 @@ static void *mas_prev_slot(struct ma_state *mas, unsigned long min, bool empty)
>  underflow:
>  	mas->status = ma_underflow;
>  	return NULL;
> +
> +dead:
> +	mas_rewalk(mas, save_point);
> +	if (likely(mas_is_active(mas)))
> +		goto retry;
> +
> +	entry = mas_prev_no_node(mas, save_point, min);
> +	if (unlikely(xa_is_node(entry))) /* The root changed again */
> +		goto dead;
> +
> +	return entry;
>  }

[Severity: Medium]
Can this leave mas in an inconsistent state if the root is concurrently
emptied between mas_rewalk() and the mas_root() read in mas_prev_no_node()?

When an RCU reader in mas_prev_slot() hits a dead node with save_point > 0
and min == 0, it jumps to dead: and runs:

    mas_rewalk(mas, save_point)
      -> mas_state_walk(mas)
        -> mas_start(mas)

If the tree holds a single pointer at index 0 at that moment, mas_start()
sets mas->status = ma_root and returns NULL because mas->index > 0.

Back in mas_prev_slot(), mas_prev_no_node() sees mas->status == ma_root,
sets mas->index = 0 and mas->last = 0, and performs a second RCU read via
mas_root(mas).

If a concurrent writer finishes emptying the tree (setting ma_root to NULL)
before that second mas_root(mas) read, mas_prev_no_node() returns NULL.
Because mas_prev_slot() only checks xa_is_node(entry) to detect a concurrent
root change, it returns NULL with mas->status == ma_root, mas->index == 0,
and mas->last == 0 instead of mas->status == ma_none and
mas->last == ULONG_MAX.

Could this leave callers like mas_prev_range() or mas_find_range_rev() with
a bogus [0, 0] range, or cause a subsequent forward walk on the same state
to skip index 0?

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261103020724.2614498-1-liam@infradead.org?part=1

Re: [PATCH v2 3/3] maple_tree: Update internal warning and bug_on code

[Lorenzo Stoakes (ARM)]

On Mon, Nov 02, 2026 at 09:07:24PM -0500, Liam R. Howlett (Google) wrote:
> When CONFIG_DEBUG_MAPLE_TREE is set, call WARN_ON() once per site after
> the custom information is dumped about the tree.  Without using the
> kernel's WARN_ON calls, syzbot will not catch issues detected by this
> code.  The BUG_ON variants now stop instead of dumping and continuing.
>
> Update the non-debug code to call WARN_ON_ONCE() as well.
>
> The userspace tests asserted on dump_stack() but only print on
> WARN_ON(), so make WARN() fatal in maple-shared.h and have the maple
> test exit with the result of maple_tree_seed().
>
> Cc: <stable@vger.kernel.org>
> Reported-by: Lorenzo Stoakes <ljs@kernel.org>
> Fixes: f0a1f866aba1 ("maple_tree: add debug BUG_ON and WARN_ON variants")
> Signed-off-by: Liam R. Howlett (Google) <liam@infradead.org>

Thanks for doing this! This covers off my concerns with the userland testing
changes so all LGTM and:

Reviewed-by: Lorenzo Stoakes (ARM) <ljs@kernel.org>

> ---
>  include/linux/maple_tree.h          | 48 ++++++++++++++---------------
>  tools/testing/radix-tree/maple.c    | 13 +++++---
>  tools/testing/shared/maple-shared.h | 33 ++++++++++++++++++++
>  3 files changed, 66 insertions(+), 28 deletions(-)
>
> diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
> index e30e57f5f3df9..3a9751c6689fc 100644
> --- a/include/linux/maple_tree.h
> +++ b/include/linux/maple_tree.h
> @@ -680,7 +680,7 @@ void mt_cache_shrink(void);
>  		pr_info("Pass: %u Run:%u\n",				\
>  			atomic_read(&maple_tree_tests_passed),		\
>  			atomic_read(&maple_tree_tests_run));		\
> -		dump_stack();						\
> +		BUG_ON(1);						\
>  	} else {							\
>  		atomic_inc(&maple_tree_tests_passed);			\
>  	}								\
> @@ -696,7 +696,7 @@ void mt_cache_shrink(void);
>  		pr_info("Pass: %u Run:%u\n",				\
>  			atomic_read(&maple_tree_tests_passed),		\
>  			atomic_read(&maple_tree_tests_run));		\
> -		dump_stack();						\
> +		BUG_ON(1);						\
>  	} else {							\
>  		atomic_inc(&maple_tree_tests_passed);			\
>  	}								\
> @@ -713,7 +713,7 @@ void mt_cache_shrink(void);
>  		pr_info("Pass: %u Run:%u\n",				\
>  			atomic_read(&maple_tree_tests_passed),		\
>  			atomic_read(&maple_tree_tests_run));		\
> -		dump_stack();						\
> +		BUG_ON(1);						\
>  	} else {							\
>  		atomic_inc(&maple_tree_tests_passed);			\
>  	}								\
> @@ -722,16 +722,16 @@ void mt_cache_shrink(void);
>  #define MT_WARN_ON(__tree, __x)  ({					\
>  	int ret = !!(__x);						\
>  	atomic_inc(&maple_tree_tests_run);				\
> -	if (ret) {							\
> -		pr_info("WARN at %s:%d (%u)\n",				\
> -		__func__, __LINE__, __x);				\
> +	if (!ret) {							\
> +		atomic_inc(&maple_tree_tests_passed);			\
> +	} else if (__ONCE_LITE_IF(ret)) {				\
> +		pr_info("WARN at %s:%d\n",				\
> +		__func__, __LINE__);					\
>  		mt_dump(__tree, mt_dump_hex);				\
>  		pr_info("Pass: %u Run:%u\n",				\
>  			atomic_read(&maple_tree_tests_passed),		\
>  			atomic_read(&maple_tree_tests_run));		\
> -		dump_stack();						\
> -	} else {							\
> -		atomic_inc(&maple_tree_tests_passed);			\
> +		WARN_ON(1);						\
>  	}								\
>  	unlikely(ret);							\
>  })
> @@ -739,17 +739,17 @@ void mt_cache_shrink(void);
>  #define MAS_WARN_ON(__mas, __x) ({					\
>  	int ret = !!(__x);						\
>  	atomic_inc(&maple_tree_tests_run);				\
> -	if (ret) {							\
> -		pr_info("WARN at %s:%d (%u)\n",				\
> -		__func__, __LINE__, __x);				\
> +	if (!ret) {							\
> +		atomic_inc(&maple_tree_tests_passed);			\
> +	} else if (__ONCE_LITE_IF(ret)) {				\
> +		pr_info("WARN at %s:%d\n",				\
> +		__func__, __LINE__);					\
>  		mas_dump(__mas);					\
>  		mt_dump((__mas)->tree, mt_dump_hex);			\
>  		pr_info("Pass: %u Run:%u\n",				\
>  			atomic_read(&maple_tree_tests_passed),		\
>  			atomic_read(&maple_tree_tests_run));		\
> -		dump_stack();						\
> -	} else {							\
> -		atomic_inc(&maple_tree_tests_passed);			\
> +		WARN_ON(1);						\
>  	}								\
>  	unlikely(ret);							\
>  })
> @@ -757,18 +757,18 @@ void mt_cache_shrink(void);
>  #define MAS_WR_WARN_ON(__wrmas, __x) ({					\
>  	int ret = !!(__x);						\
>  	atomic_inc(&maple_tree_tests_run);				\
> -	if (ret) {							\
> -		pr_info("WARN at %s:%d (%u)\n",				\
> -		__func__, __LINE__, __x);				\
> +	if (!ret) {							\
> +		atomic_inc(&maple_tree_tests_passed);			\
> +	} else if (__ONCE_LITE_IF(ret)) {				\
> +		pr_info("WARN at %s:%d\n",				\
> +		__func__, __LINE__);					\
>  		mas_wr_dump(__wrmas);					\
>  		mas_dump((__wrmas)->mas);				\
>  		mt_dump((__wrmas)->mas->tree, mt_dump_hex);		\
>  		pr_info("Pass: %u Run:%u\n",				\
>  			atomic_read(&maple_tree_tests_passed),		\
>  			atomic_read(&maple_tree_tests_run));		\
> -		dump_stack();						\
> -	} else {							\
> -		atomic_inc(&maple_tree_tests_passed);			\
> +		WARN_ON(1);						\
>  	}								\
>  	unlikely(ret);							\
>  })
> @@ -776,9 +776,9 @@ void mt_cache_shrink(void);
>  #define MT_BUG_ON(__tree, __x)		BUG_ON(__x)
>  #define MAS_BUG_ON(__mas, __x)		BUG_ON(__x)
>  #define MAS_WR_BUG_ON(__mas, __x)	BUG_ON(__x)
> -#define MT_WARN_ON(__tree, __x)		WARN_ON(__x)
> -#define MAS_WARN_ON(__mas, __x)		WARN_ON(__x)
> -#define MAS_WR_WARN_ON(__mas, __x)	WARN_ON(__x)
> +#define MT_WARN_ON(__tree, __x)		WARN_ON_ONCE(__x)
> +#define MAS_WARN_ON(__mas, __x)		WARN_ON_ONCE(__x)
> +#define MAS_WR_WARN_ON(__mas, __x)	WARN_ON_ONCE(__x)
>  #endif /* CONFIG_DEBUG_MAPLE_TREE */
>
>  /**
> diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
> index bfe4b8626c429..846c67e20e82a 100644
> --- a/tools/testing/radix-tree/maple.c
> +++ b/tools/testing/radix-tree/maple.c
> @@ -36502,22 +36502,27 @@ static void regression_tests(void)
>  	test_spanning_store_regression();
>  }
>
> -void maple_tree_tests(void)
> +int maple_tree_tests(void)
>  {
> +	int ret;
> +
>  #if !defined(BENCH)
>  	regression_tests();
>  	farmer_tests();
>  #endif
> -	maple_tree_seed();
> +	ret = maple_tree_seed();
>  	maple_tree_harvest();
> +	return ret;
>  }
>
>  int __weak main(void)
>  {
> +	int ret;
> +
>  	maple_tree_init();
> -	maple_tree_tests();
> +	ret = maple_tree_tests();
>  	rcu_barrier();
>  	if (nr_allocated)
>  		printf("nr_allocated = %d\n", nr_allocated);
> -	return 0;
> +	return ret ? EXIT_FAILURE : EXIT_SUCCESS;
>  }
> diff --git a/tools/testing/shared/maple-shared.h b/tools/testing/shared/maple-shared.h
> index 2a1e9a8594a28..5f827709773a0 100644
> --- a/tools/testing/shared/maple-shared.h
> +++ b/tools/testing/shared/maple-shared.h
> @@ -8,6 +8,7 @@
>  #include "shared.h"
>  #include <stdlib.h>
>  #include <time.h>
> +#include <assert.h>
>  #include "linux/init.h"
>
>  void maple_rcu_cb(struct rcu_head *head);
> @@ -20,5 +21,37 @@ do {                                            \
>      call_rcu(&((_p_struct)->_memb), rcu_cb);    \
>  } while(0);
>
> +/* Make WARN() fatal */
> +#undef WARN
> +#undef WARN_ON
> +#undef WARN_ONCE
> +#undef WARN_ON_ONCE
> +#define WARN(condition, format...) ({				\
> +	int __ret_warn_on = !!(condition);			\
> +	if (unlikely(__ret_warn_on)) {				\
> +		__WARN_printf(format);				\
> +		assert(0);					\
> +	}							\
> +	unlikely(__ret_warn_on);				\
> +})
> +#define WARN_ON(condition)					\
> +	WARN(condition, "assertion failed at %s:%d\n", __FILE__, __LINE__)
> +#define WARN_ONCE(condition, format...)	WARN(condition, format)
> +#define WARN_ON_ONCE(condition)		WARN_ON(condition)
> +
> +/* Once state for the debug macros */
> +#ifndef __ONCE_LITE_IF
> +#define __ONCE_LITE_IF(condition)				\
> +	({							\
> +		static bool __already_done;			\
> +		bool __ret_once = false;			\
> +								\
> +		if ((condition) && !__already_done) {		\
> +			__already_done = true;			\
> +			__ret_once = true;			\
> +		}						\
> +		__ret_once;					\
> +	})
> +#endif
>
>  #endif /* __MAPLE_SHARED_H__ */
> --
> 2.47.3
>

--
Cheers, Lorenzo