[PATCH 1/4] maple_tree: Fix rcu reader NULL dereference after the tree is emptied
Liam R. Howlett (Google)
liam at infradead.org
Wed Oct 28 08:42:15 PDT 2026
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.
Initial fix was generated by LLM and sent by Chris Mason in private.
Cc: <stable at vger.kernel.org>
Fixes: fff4a58cc00b ("maple_tree: introduce mas_next_slot() interface")
Reported-by: Chris Mason <mason at kernel.org>
Signed-off-by: Liam R. Howlett (Google) <liam at infradead.org>
---
lib/maple_tree.c | 110 +++++++++++++++++++++++++++++++++++------------
1 file changed, 83 insertions(+), 27 deletions(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 0b0036c9f8489..22812ed49be5a 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -3891,14 +3891,54 @@ 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)
+ * @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, before the saved index: stop on it as mas_prev_setup() does.
+ *
+ * Return: The root entry if @min allows 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 min)
+{
+ mas->index = 0;
+ if (mas_is_none(mas)) {
+ mas->last = ULONG_MAX;
+ return NULL;
}
- return false;
+
+ mas->last = 0;
+ if (min)
+ return NULL;
+
+ return mas_root(mas);
}
/*
@@ -4006,14 +4046,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 +4068,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 +4083,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 +4101,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, min);
+ if (unlikely(xa_is_node(entry))) /* The root changed again */
+ goto dead;
+
+ return entry;
}
/*
@@ -4176,8 +4225,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 +4234,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 +4257,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 +4273,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 +4291,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 +5504,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
More information about the maple-tree
mailing list