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 Cc: stable@vger.kernel.org Signed-off-by: Nickolai Zeldovich --- 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 #include #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