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

[sashiko-bot@kernel.org]

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