From: Nickolai Zeldovich Free XArray nodes whose offsets are nonzero, then check that roots created by xas_create() and xas_expand() have offset zero. An old root with a stale offset can make a concurrent iterator resume in the wrong slot after expansion. Link: https://lore.kernel.org/r/20261024014344.830116-1-nickolai@csail.mit.edu Signed-off-by: Nickolai Zeldovich Signed-off-by: Andrew Morton Cc: Matthew Wilcox (Oracle) Cc: Baoli Zhang Cc: lib/test_xarray.c | 33 +++++++++++++++++++++++++++++++++ 1 file changed, 33 insertions(+) --- a/lib/test_xarray.c~lib-test_xarray-check-the-offset-of-new-root-nodes +++ a/lib/test_xarray.c @@ -370,6 +370,38 @@ static noinline void check_xa_shrink(str } } +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; @@ -2336,6 +2368,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); _ From: Nickolai Zeldovich xas_alloc() sets node->offset only when the new node has a parent. A root node can retain a nonzero offset from its previous use in the slab. While xas_expand() links that root below a new one, an RCU walker can read the stale offset and then the new parent pointer. It can resume at the wrong slot and report an entry at the wrong index or skip entries. Initialize the offset to zero when allocating a root. The old root already has that offset when xas_expand() links it beneath the new root, so remove the store to its offset during expansion. Link: https://patch.msgid.link/20261024014344.830116-1-nickolai@csail.mit.edu Fixes: 58d6ea3085f2 ("xarray: Add XArray unconditional store operations") Signed-off-by: Nickolai Zeldovich Signed-off-by: Andrew Morton Reported-by: Closes: https://syzkaller.appspot.com/bug?extid=73641b60a3bc11dfca8c Tested-by: Baoli Zhang Tested-by: Andrew Morton Cc: Matthew Wilcox (Oracle) Cc: --- akpm: Tested the two-patch series on x86-64, with the new test present on both kernels. Without the fix, 64 runs of the test each failed both root-offset checks. With the fix, neither check failed and all XArray checks passed. Both kernels used the same configuration and test setup. This tests the stale root offset; it does not separately reproduce the concurrent RCU-walker failure. lib/xarray.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) --- a/lib/xarray.c~xarray-initialise-the-offset-of-a-new-root-node +++ a/lib/xarray.c @@ -387,6 +387,8 @@ static void *xas_alloc(struct xa_state * 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)); @@ -617,10 +619,8 @@ static int xas_expand(struct xa_state *x * 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); _