* [PATCH v2 1/3] maple_tree: Fix rcu reader NULL dereference after the tree is emptied
[not found] <20261103020724.2614498-1-liam@infradead.org>
@ 2026-11-03 2:07 ` Liam R. Howlett (Google)
2026-11-03 2:07 ` [PATCH v2 3/3] maple_tree: Update internal warning and bug_on code Liam R. Howlett (Google)
1 sibling, 0 replies; 3+ messages in thread
From: Liam R. Howlett (Google) @ 2026-11-03 2:07 UTC (permalink / raw)
To: Andrew Morton
Cc: linux-mm, linux-kernel, maple-tree, Lorenzo Stoakes, Chris Mason,
Alice Ryhl, Andrew Ballance, Liam R. Howlett (Google), stable
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
^ permalink raw reply related [flat|nested] 3+ messages in thread* [PATCH v2 3/3] maple_tree: Update internal warning and bug_on code
[not found] <20261103020724.2614498-1-liam@infradead.org>
2026-11-03 2:07 ` [PATCH v2 1/3] maple_tree: Fix rcu reader NULL dereference after the tree is emptied Liam R. Howlett (Google)
@ 2026-11-03 2:07 ` Liam R. Howlett (Google)
2026-11-03 11:52 ` Lorenzo Stoakes (ARM)
1 sibling, 1 reply; 3+ messages in thread
From: Liam R. Howlett (Google) @ 2026-11-03 2:07 UTC (permalink / raw)
To: Andrew Morton
Cc: linux-mm, linux-kernel, maple-tree, Lorenzo Stoakes, Chris Mason,
Alice Ryhl, Andrew Ballance, Liam R. Howlett (Google), stable
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
^ permalink raw reply related [flat|nested] 3+ messages in thread