[PATCH v2] xarray: initialise the offset of a new root node

[Nickolai Zeldovich <nickolai@csail.mit.edu>]

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 <baoli.zhang@intel.com>
Cc: stable@vger.kernel.org
Signed-off-by: Nickolai Zeldovich <nickolai@csail.mit.edu>
---

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