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