[PATCH v1] xarray: unlink a node before freeing it

[Nickolai Zeldovich]

xas_delete_node() passes an empty node to xa_node_free(), which queues it
with call_rcu(), and only then stores NULL over the pointer to the node,
in the parent's slot or in xa_head.  Between the two, a lockless walker
can still reach the node, and RCU does not protect it: call_rcu() waits
only for the read-side critical sections that were running when the
callback's grace period started, and that grace period can start before
the store that unlinks the node.  A walker that begins its RCU read-side
critical section after that point can load the old pointer and keep
using the node after it has been freed:

  CPU 0: xa_erase(), xa_lock held   CPU 1: RCU walker, e.g. xa_load()

  xas_delete_node()
    xa_node_free(node)
      call_rcu()
                    <grace period starts>
                                     passes a quiescent state
                                     rcu_read_lock()
                                     xas_load(): parent->slots[offset]
                                     is still node
    parent->slots[offset] = NULL
  xa_unlock()
  quiescent state
                    <grace period ends>
  radix_tree_node_rcu_free(node)
                                     reads node->shift, node->slots[]

The grace period does not wait for CPU 1: CPU 1 reported its quiescent
state before its critical section began.  Holding xa_lock does not help
either.  It makes CPU 0 an RCU reader, which delays the end of the grace
period until after the unlinking store, but not its start.  The start can
fall inside the window whenever the callback is assigned to a grace
period before the unlink: from call_rcu() itself when many callbacks are
queued, from an interrupt that arrives in the window (interrupts are
enabled under xa_lock(), and RCU core processing and the other softirqs
may run on interrupt exit for milliseconds), from the rcuog kthread on
another CPU when callbacks are offloaded (rcu_nocbs=), or while the
writer is preempted under PREEMPT_RT.  Interrupts, and in a guest a
preempted vCPU, also stretch the window.

Setting node->array to XA_RCU_FREE does not make walkers retry: no
lockless path looks at node->array.  xas_load() and xas_descend() look
only at the entries and at node->shift, and the marker is overwritten
when the slab reuses the object.  The XA_RETRY_ENTRY markers that
xas_shrink() and xas_free_nodes() store only help walkers that reached
a node before it was unlinked; the grace period waits for those because
both functions unlink before they free.

radix_tree_node_cachep is not SLAB_TYPESAFE_BY_RCU, so the walker reads
freed memory.  Once the object is reused for a node of another array,
the walker can descend through the wrong node and return an entry of
the other array.  In a page cache lookup, the xas_reload() recheck in
filemap_get_entry() reads the same reused slot and accepts the result,
so in the worst case the lookup returns a folio of another file.

The order dates from the introduction of xas_delete_node() in the
commit below, which reimplemented the radix tree's delete_node().
delete_node() unlinks first and frees after, and still does in
lib/radix-tree.c, as do xas_shrink() and xas_free_nodes(), the other two
paths that free nodes in lib/xarray.c.  The commit gives no reason for
the different order and nothing depends on it: xa_node_free() only marks
the node and queues the callback, node->offset is read before the free,
and the stores and xas_update() on the parent do not involve the node.

Move xa_node_free() after the store that unlinks the node, in both
branches.  The stores and their order are unchanged, nothing reads the
node after it is freed, and every caller sees the same tree and the
same xa_state.

The radix-tree test suite already runs into this.  Its multiorder test
(multiorder_iteration_race(): one thread inserts and deletes an entry at
index 0 while the others walk the array under rcu_read_lock(), with
liburcu's call_rcu()) reported a heap-use-after-free in xas_start(),
reading the shift of a head node freed through call_rcu(), in 10 of 200
unpatched runs under AddressSanitizer on a 160-CPU machine, and in none
of 200 runs with this patch.  A harness check that no node passed to
xa_node_free() is still reachable from xa_head fails 556941 times in the
XArray tests without this patch (all in xas_delete_node(), both
branches) and never with it.  No test is added: the race is not
deterministic and the check needs a hook on xa_node_free().  On a
kernel, the window is too short to hit on demand.  With a 100 ms delay
injected between call_rcu() and the unlink in a test build, a lookup
that starts on another CPU 20 ms into the window reaches the node, and
KASAN reports a slab-use-after-free of the radix_tree_node freed from
rcu_core() when the lookup reads it again.  With this patch and the
same delay between the unlink and the free, no lookup reaches the node.
The XArray and IDA self-tests pass on x86_64 and riscv64.

Found while formally verifying xas_store() against the kernel binary.

Fixes: 58d6ea3085f2 ("xarray: Add XArray unconditional store operations")
Cc: stable@xxxxxxxxxxxxxxx
Assisted-by: LLM
Signed-off-by: Nickolai Zeldovich <nickolai@xxxxxxxxxxxxx>
---

Notes:
    Reproduction details: the harness numbers come from
    tools/testing/radix-tree built as is (AddressSanitizer is on by
    default), running ./multiorder 200 times on master and on master plus
    this patch.  The ordering check wraps each xa_node_free(node) call in a
    copy of lib/xarray.c with a function that walks the tree from xa_head
    and reports the node if it is still reachable; it is not part of this
    patch.  The kernel demonstration is a test build (x86_64 defconfig +
    KASAN, QEMU -smp 4) with mdelay(100) after xa_node_free() in
    xas_delete_node() for one test array, a writer kthread on CPU 0 doing
    xa_store()/xa_erase() and a reader kthread on CPU 1 doing
    xas_load()/xas_next() under rcu_read_lock().  I can send any of these
    if useful.
    
    The patch and its analysis were drafted with an LLM coding assistant
    and then reviewed and tested as described in the commit message.

 lib/xarray.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/lib/xarray.c b/lib/xarray.c
index bfe7bef80f34..d48754c5f8b8 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -500,17 +500,18 @@ static void xas_delete_node(struct xa_state *xas)
 		parent = xa_parent_locked(xas->xa, node);
 		xas->xa_node = parent;
 		xas->xa_offset = node->offset;
-		xa_node_free(node);
 
 		if (!parent) {
 			xas->xa->xa_head = NULL;
 			xas->xa_node = XAS_BOUNDS;
+			xa_node_free(node);
 			return;
 		}
 
 		parent->slots[xas->xa_offset] = NULL;
 		parent->count--;
 		XA_NODE_BUG_ON(parent, parent->count > XA_CHUNK_SIZE);
+		xa_node_free(node);
 		node = parent;
 		xas_update(xas, node);
 	}

base-commit: 24a19b953e2a3d0ea5a8c4951a0ab8f32720c907
-- 
2.53.0