Re: [PATCH v1] xarray: initialise the offset of a new root node

[Matthew Wilcox <willy@infradead.org>]

Same comment about the verbosity of the commit message.

On Mon, Oct 12, 2026 at 02:11:07PM -0400, Nickolai Zeldovich wrote:
> xas_alloc() sets node->offset only when the new node has a parent.  A
> root node, allocated by xas_create() for an empty array or by
> xas_expand() when the tree grows, keeps the offset its slab object had
> before: radix_tree_node_cachep has a constructor, so the slab does not
> clear the object, and radix_tree_node_rcu_free() only clears the slots
> and marks.  A node freed from slot N of its parent comes back as a root
> with offset N.
> 
> xas_expand() stores 0 to the old root's offset just before publishing it
> as slot 0 of the new root, so the value is right once the expansion is
> visible, but an RCU walker can see the old value.  The iterators climb
> out of a node with
> 
> 	xas->xa_offset = xas->xa_node->offset + 1;
> 	xas->xa_node = xa_parent(xas->xa, xas->xa_node);
> 
> (xas_find(), xas_find_marked() and __xas_next(); __xas_prev() uses
> "- 1").  A walker under rcu_read_lock() that reaches the end of the root
> while another thread expands the tree can load the stale offset before
> xas_expand() clears it and the parent pointer after xas_expand() sets
> it.  No reordering is needed: the two loads only have to straddle the
> two stores.  The walker then continues in the new root at slot
> (stale offset + 1) while xa_index is the first index of slot 1.  If that
> slot is populated by then (for example by the store that caused the
> expansion), the walker returns its entry with the wrong index.  With a
> root covering 0-63 and a stale offset of 5, xa_for_each() that runs
> concurrently with xa_store(xa, 384, p) can report p at index 64, and
> then again at 384; xa_find() stores the wrong index in *indexp.  Any
> entries in slots 1..5 of the new root are skipped.
> 
> The radix tree's radix_tree_node_alloc() always sets the offset, and
> radix_tree_extend() passes 0 for a new root.  xas_alloc() dropped this
> for root nodes when the XArray was introduced.
> 
> Set the offset of a node allocated without a parent to 0.  A node's
> offset then never changes while readers can see it: a child's offset is
> set before the node is published, xas_expand()'s store to the old root
> writes the value it already has, and the root that xas_shrink() leaves
> behind was the child in slot 0.  A walker climbing out of a root
> continues at slot 1 whichever parent pointer it loads.
> 
> The new test frees two nodes with non-zero offsets and checks that the
> roots created by xas_create() and xas_expand() have offset 0.  Its
> checks use a new XA_WARN_ON(), which warns and carries on, counted like
> XA_BUG_ON().  The test relies on the slab handing the freed nodes back;
> without this patch both checks fail in the userspace harness and in the
> self-test booted on x86_64 and riscv64 under QEMU.  The race itself has
> no deterministic test.

No, we don't want XA_WARN_ON.  We want XA_BUG_ON so it _stops_.  This
is really important.

> Found while formally verifying the lockless XArray iterators against the
> kernel binary.
> 
> Fixes: 58d6ea3085f2 ("xarray: Add XArray unconditional store operations")
> Cc: stable@vger.kernel.org
> Assisted-by: LLM
> Signed-off-by: Nickolai Zeldovich <nickolai@csail.mit.edu>
> ---
> 
> Notes:
>     - The patch and its analysis were drafted with an LLM coding assistant
>       and then reviewed and tested as described here and in the commit
>       message.
>     
>     - Reproduction of the race (test build only, not part of this patch): in
>       tools/testing/radix-tree (XA_CHUNK_SHIFT 3), a hook between the two
>       loads of the climb in xas_find() runs the expanding store, i.e. the
>       writer runs after the walker loaded the root's offset and before it
>       loaded the parent.  The root was reallocated from a leaf freed at
>       offset 5.  Without this patch xa_for_each() prints "index 8 entry 48",
>       then "index 48 entry 48"; with it, only "index 48 entry 48".  Nothing
>       was reproduced without the injected hook: the window is two loads wide.
>     
>  lib/test_xarray.c | 50 +++++++++++++++++++++++++++++++++++++++++++++++
>  lib/xarray.c      |  2 ++
>  2 files changed, 52 insertions(+)
> 
> diff --git a/lib/test_xarray.c b/lib/test_xarray.c
> index 5ca0aefee9aa..27988441e71c 100644
> --- a/lib/test_xarray.c
> +++ b/lib/test_xarray.c
> @@ -32,6 +32,22 @@ void xa_dump(const struct xarray *xa) { }
>  } while (0)
>  #endif
>  
> +/*
> + * Warn if @x holds and return whether it did, so that the caller can skip
> + * checks which would not terminate or would not mean anything on the
> + * broken state.  Counted with tests_run and tests_passed like the rest.
> + */
> +#define XA_WARN_ON(xa, x) ({					\
> +	bool __failed = WARN_ON(x);				\
> +								\
> +	tests_run++;						\
> +	if (__failed)						\
> +		xa_dump(xa);					\
> +	else							\
> +		tests_passed++;					\
> +	__failed;						\
> +})
> +
>  static void *xa_mk_index(unsigned long index)
>  {
>  	return xa_mk_value(index & LONG_MAX);
> @@ -370,6 +386,39 @@ static noinline void check_xa_shrink(struct xarray *xa)
>  	}
>  }
>  
> +static noinline void check_xa_root_offset(struct xarray *xa)
> +{
> +	DEFINE_XARRAY(tmp);
> +	struct xa_node *node;
> +
> +	/* Free two nodes with non-zero offsets so the slab can reuse them */
> +	xa_store_index(&tmp, 0, GFP_KERNEL);
> +	xa_store_index(&tmp, 5UL << XA_CHUNK_SHIFT, GFP_KERNEL);
> +	xa_store_index(&tmp, 6UL << XA_CHUNK_SHIFT, GFP_KERNEL);
> +	xa_store_index(&tmp, 7UL << XA_CHUNK_SHIFT, GFP_KERNEL);
> +	xa_erase_index(&tmp, 5UL << XA_CHUNK_SHIFT);
> +	xa_erase_index(&tmp, 6UL << XA_CHUNK_SHIFT);
> +	rcu_barrier();
> +
> +	/* A root created by xas_create() must have offset 0 */
> +	XA_WARN_ON(xa, xa_store_index(xa, 0, GFP_KERNEL));
> +	XA_WARN_ON(xa, xa_store_index(xa, 1, GFP_KERNEL));
> +	rcu_read_lock();
> +	node = xa_to_node(xa_head(xa));
> +	XA_WARN_ON(xa, node->offset != 0);
> +	rcu_read_unlock();
> +
> +	/* And so must a root created by xas_expand() */
> +	XA_WARN_ON(xa, xa_store_index(xa, XA_CHUNK_SIZE, GFP_KERNEL));
> +	rcu_read_lock();
> +	node = xa_to_node(xa_head(xa));
> +	XA_WARN_ON(xa, node->offset != 0);
> +	rcu_read_unlock();
> +
> +	xa_destroy(xa);
> +	xa_destroy(&tmp);
> +}
> +
>  static noinline void check_insert(struct xarray *xa)
>  {
>  	unsigned long i;
> @@ -2235,6 +2284,7 @@ static int xarray_checks(void)
>  	check_xa_load(&array);
>  	check_xa_mark(&array);
>  	check_xa_shrink(&array);
> +	check_xa_root_offset(&array);
>  	check_xas_erase(&array);
>  	check_insert(&array);
>  	check_cmpxchg(&array);
> diff --git a/lib/xarray.c b/lib/xarray.c
> index bfe7bef80f34..720d46e8b14a 100644
> --- a/lib/xarray.c
> +++ b/lib/xarray.c
> @@ -387,6 +387,8 @@ static void *xas_alloc(struct xa_state *xas, unsigned int shift)
>  		parent->count++;
>  		XA_NODE_BUG_ON(node, parent->count > XA_CHUNK_SIZE);
>  		xas_update(xas, parent);
> +	} else {
> +		node->offset = 0;
>  	}
>  	XA_NODE_BUG_ON(node, shift > BITS_PER_LONG);
>  	XA_NODE_BUG_ON(node, !list_empty(&node->private_list));
> 

I think we should include Baoli's addition as well, but other than that,
I think the patch is correct.  (I have a suspicion that xas->xa_offset
will be 0 if !parent, so we could just initialise node->offset to
xas->xa_offset unconditionally, but I'm not sure that level of
microoptimisation is worth it at this point).