[PATCH v2] xarray: initialise the offset of a new root node
From: Nickolai Zeldovich
Date: Fri Oct 23 2026 - 21:44:11 EST
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@xxxxxxxxxxxxxxxxxxxxxxxxx
Closes: https://syzkaller.appspot.com/bug?extid=73641b60a3bc11dfca8c
Tested-by: Baoli Zhang <baoli.zhang@xxxxxxxxx>
Cc: stable@xxxxxxxxxxxxxxx
Signed-off-by: Nickolai Zeldovich <nickolai@xxxxxxxxxxxxx>
---
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@xxxxxxxxxxxxx/
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