The Linux Kernel Mailing List
 help / color / mirror / Atom feed
* [PATCH v2 0/2] xarray: initialise the offset of a new root node
@ 2026-11-21 22:18 Andrew Morton
  2026-11-21 22:18 ` [PATCH v2 1/2] lib/test_xarray: check the offset of new root nodes Andrew Morton
  2026-11-21 22:18 ` [PATCH v2 2/2] xarray: initialise the offset of a new root node Andrew Morton
  0 siblings, 2 replies; 3+ messages in thread
From: Andrew Morton @ 2026-11-21 22:18 UTC (permalink / raw)
  To: Matthew Wilcox (Oracle)
  Cc: linux-fsdevel, linux-mm, linux-kernel, Andrew Morton,
	Nickolai Zeldovich, Baoli Zhang, syzbot+73641b60a3bc11dfca8c,
	stable

An RCU XArray walker can read a stale root offset just before another
thread grows the tree and links that root beneath a new one.  The walker
can then return an entry with the wrong index or skip entries.  Check the
root offset after slab reuse and initialize it on allocation.

Nickolai Zeldovich (2):
  lib/test_xarray: check the offset of new root nodes
  xarray: initialise the offset of a new root node

 lib/test_xarray.c | 33 +++++++++++++++++++++++++++++++++
 lib/xarray.c      |  6 +++---
 2 files changed, 36 insertions(+), 3 deletions(-)

^ permalink raw reply	[flat|nested] 3+ messages in thread

* [PATCH v2 1/2] lib/test_xarray: check the offset of new root nodes
  2026-11-21 22:18 [PATCH v2 0/2] xarray: initialise the offset of a new root node Andrew Morton
@ 2026-11-21 22:18 ` Andrew Morton
  2026-11-21 22:18 ` [PATCH v2 2/2] xarray: initialise the offset of a new root node Andrew Morton
  1 sibling, 0 replies; 3+ messages in thread
From: Andrew Morton @ 2026-11-21 22:18 UTC (permalink / raw)
  To: Matthew Wilcox (Oracle)
  Cc: linux-fsdevel, linux-mm, linux-kernel, Andrew Morton,
	Nickolai Zeldovich, Baoli Zhang, syzbot+73641b60a3bc11dfca8c

From: Nickolai Zeldovich <nickolai@csail.mit.edu>

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 <nickolai@csail.mit.edu>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Cc: Matthew Wilcox (Oracle) <willy@infradead.org>
Cc: Baoli Zhang <baoli.zhang@intel.com>
Cc: <syzbot+73641b60a3bc11dfca8c@syzkaller.appspotmail.com>

 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);
_

^ permalink raw reply	[flat|nested] 3+ messages in thread

* [PATCH v2 2/2] xarray: initialise the offset of a new root node
  2026-11-21 22:18 [PATCH v2 0/2] xarray: initialise the offset of a new root node Andrew Morton
  2026-11-21 22:18 ` [PATCH v2 1/2] lib/test_xarray: check the offset of new root nodes Andrew Morton
@ 2026-11-21 22:18 ` Andrew Morton
  1 sibling, 0 replies; 3+ messages in thread
From: Andrew Morton @ 2026-11-21 22:18 UTC (permalink / raw)
  To: Matthew Wilcox (Oracle)
  Cc: linux-fsdevel, linux-mm, linux-kernel, Andrew Morton,
	Nickolai Zeldovich, syzbot+73641b60a3bc11dfca8c, Baoli Zhang,
	stable

From: Nickolai Zeldovich <nickolai@csail.mit.edu>

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 <nickolai@csail.mit.edu>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Reported-by: <syzbot+73641b60a3bc11dfca8c@syzkaller.appspotmail.com>
Closes: https://syzkaller.appspot.com/bug?extid=73641b60a3bc11dfca8c
Tested-by: Baoli Zhang <baoli.zhang@intel.com>
Tested-by: Andrew Morton <akpm@linux-foundation.org>
Cc: Matthew Wilcox (Oracle) <willy@infradead.org>
Cc: <stable@vger.kernel.org>
---
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);
_

^ permalink raw reply	[flat|nested] 3+ messages in thread

end of thread, other threads:[~2026-11-21 22:18 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2026-11-21 22:18 [PATCH v2 0/2] xarray: initialise the offset of a new root node Andrew Morton
2026-11-21 22:18 ` [PATCH v2 1/2] lib/test_xarray: check the offset of new root nodes Andrew Morton
2026-11-21 22:18 ` [PATCH v2 2/2] xarray: initialise the offset of a new root node Andrew Morton

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox