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

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

[Nickolai Zeldovich]

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.

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));

base-commit: 24a19b953e2a3d0ea5a8c4951a0ab8f32720c907
-- 
2.53.0

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

[Matthew Wilcox]

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).

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

[Nickolai Zeldovich]

An RCU walker such as xas_find() that climbs out of the root while
xas_expand() adds a level above it can resume in the new root at the
wrong slot and return an entry with the wrong index.

xas_alloc() sets node->offset only for a node with a parent, so a new
root keeps the offset its slab object had before.  xas_expand() stores
0 to the old root's offset just before linking it below the new root,
and a walker can load the stale offset before that store and the new
parent pointer after it.

Set the offset of a node allocated without a parent to 0.  The store in
xas_expand() then writes the value the old root already has, so remove
it.

Fixes: 58d6ea3085f2 ("xarray: Add XArray unconditional store operations")
Reported-by: syzbot+73641b60a3bc11dfca8c@syzkaller.appspotmail.com
Closes: https://syzkaller.appspot.com/bug?extid=73641b60a3bc11dfca8c
Tested-by: Baoli Zhang <baoli.zhang@intel.com>
Cc: stable@vger.kernel.org
Signed-off-by: Nickolai Zeldovich <nickolai@csail.mit.edu>
---

Notes:
    Changes in v2:
    - The test uses XA_BUG_ON() instead of a new XA_WARN_ON() (Matthew Wilcox).
    - Remove the store to the old root's offset in xas_expand(), which now
      writes the value already there (Baoli Zhang).
    - The first root in the test now comes from xas_create(); in v1 both
      came from xas_expand().
    v1: https://lore.kernel.org/all/20261012181107.772545-1-nickolai@csail.mit.edu/
    
    Setting node->offset = xas->xa_offset for a root too does not work:
    xas_set() keeps xa_offset, so a loop like the one in check_xas_erase()
    (xas_set(&xas, j); xas_store(&xas, ...)) grows the tree with the offset
    of the previous index.  In the XArray tests 2929 of 104963 allocations
    without a parent see a non-zero xa_offset, and with that variant
    check_xas_erase() fails.
    
    The syzbot report is this race seen by KCSAN: xas_expand() changes the
    old root's offset from 3 to 0 while xas_find() reads it.  After this
    patch xas_expand() no longer writes it.
    
    Reproducer (tools/testing/radix-tree with a hook in xas_find() between
    "xas->xa_offset = xas->xa_node->offset + 1;" and the xa_parent() load:
    "if (xa_climb_hook) xa_climb_hook();"; add "rootoff: rootoff.o
    $(CORE_OFILES)" to the Makefile):
    
    #include <stdio.h>
    #include <linux/xarray.h>
    #include "test.h"
    
    extern void (*xa_climb_hook)(void);
    static DEFINE_XARRAY(tmp);
    static DEFINE_XARRAY(xa);
    
    static void expand(void)
    {
    	xa_climb_hook = NULL;
    	xa_store(&xa, 6UL << XA_CHUNK_SHIFT, xa_mk_value(48), GFP_KERNEL);
    }
    
    int main(void)
    {
    	unsigned long index;
    	void *entry;
    
    	rcu_register_thread();
    	radix_tree_init();
    
    	/* free a leaf that sat in slot 5 of its parent */
    	xa_store(&tmp, 0, xa_mk_value(0), GFP_KERNEL);
    	xa_store(&tmp, 5UL << XA_CHUNK_SHIFT, xa_mk_value(0), GFP_KERNEL);
    	xa_store(&tmp, 7UL << XA_CHUNK_SHIFT, xa_mk_value(0), GFP_KERNEL);
    	xa_erase(&tmp, 5UL << XA_CHUNK_SHIFT);
    	rcu_barrier();
    
    	/* the new root of xa reuses it */
    	xa_store(&xa, 1, xa_mk_value(1), GFP_KERNEL);
    	printf("root offset %u\n", xa_to_node(xa.xa_head)->offset);
    
    	xa_climb_hook = expand;
    	xa_for_each(&xa, index, entry)
    		printf("index %lu entry %lu\n", index, xa_to_value(entry));
    	return 0;
    }
    
    $ make rootoff && ./rootoff
    Without this patch:       With it:
    root offset 5             root offset 0
    index 1 entry 1           index 1 entry 1
    index 8 entry 48          index 48 entry 48
    index 48 entry 48
    
    Tested with tools/testing/radix-tree and with test_xarray built in on
    x86_64 and riscv64 under QEMU; without the lib/xarray.c change both new
    checks fail.
    
    The analysis, the patch and the tests were done with the help of an AI
    coding assistant.

 lib/test_xarray.c | 33 +++++++++++++++++++++++++++++++++
 lib/xarray.c      |  6 +++---
 2 files changed, 36 insertions(+), 3 deletions(-)

diff --git a/lib/test_xarray.c b/lib/test_xarray.c
index 5ca0aefee9aa5..046abad609648 100644
--- a/lib/test_xarray.c
+++ b/lib/test_xarray.c
@@ -370,6 +370,38 @@ 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_BUG_ON(xa, xa_store_index(xa, 1, GFP_KERNEL));
+	rcu_read_lock();
+	node = xa_to_node(xa_head(xa));
+	XA_BUG_ON(xa, node->offset != 0);
+	rcu_read_unlock();
+
+	/* And so must a root created by xas_expand() */
+	XA_BUG_ON(xa, xa_store_index(xa, XA_CHUNK_SIZE, GFP_KERNEL));
+	rcu_read_lock();
+	node = xa_to_node(xa_head(xa));
+	XA_BUG_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 +2267,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 bfe7bef80f34e..1e2380e3194d6 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));
@@ -616,10 +618,8 @@ static int xas_expand(struct xa_state *xas, void *head)
 		 * Now that the new node is fully initialised, we can add
 		 * it to the tree
 		 */
-		if (xa_is_node(head)) {
-			xa_to_node(head)->offset = 0;
+		if (xa_is_node(head))
 			rcu_assign_pointer(xa_to_node(head)->parent, node);
-		}
 		head = xa_mk_node(node);
 		rcu_assign_pointer(xa->xa_head, head);
 		xas_update(xas, node);

base-commit: 26344c0dd32af8790d8474d233619db825441138
-- 
2.53.0