* + xarray-clear-the-new-heads-parent-before-freeing-the-old-head.patch added to mm-unstable branch
@ 2026-10-23 18:11 Andrew Morton
2026-10-27 17:41 ` Matthew Wilcox
0 siblings, 1 reply; 3+ messages in thread
From: Andrew Morton @ 2026-10-23 18:11 UTC (permalink / raw)
To: mm-commits, willy, stable, nickolai, akpm
The patch titled
Subject: xarray: clear the new head's parent before freeing the old head
has been added to the -mm mm-unstable branch. Its filename is
xarray-clear-the-new-heads-parent-before-freeing-the-old-head.patch
This patch will shortly appear at
https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/xarray-clear-the-new-heads-parent-before-freeing-the-old-head.patch
This patch will later appear in the mm-unstable branch at
git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***
The -mm tree is included into linux-next via various
branches at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
and is updated there most days
------------------------------------------------------
From: Nickolai Zeldovich <nickolai@csail.mit.edu>
Subject: xarray: clear the new head's parent before freeing the old head
Date: Mon, 12 Oct 2026 16:25:49 -0400
When xas_shrink() replaces the head node of an array with the node in its
slot 0, it stores the child in xa_head, passes the old head to
xa_node_free(), which queues it with call_rcu(), and only then clears the
child's ->parent pointer. In between, a lockless walker can still reach
the old head, not from xa_head but upwards from the new head: xas_find(),
xas_find_marked(), xas_next() and xas_prev() climb through xa_parent()
when they step past the end of a node. RCU does not protect a walker that
gets there: 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 parent pointer is cleared.
CPU 0: xa_erase(), xa_lock held CPU 1: RCU walker, e.g. xa_find()
xas_shrink()
xa->xa_head = child
xa_node_free(old head)
call_rcu()
<grace period starts>
passes a quiescent state
rcu_read_lock()
xas_find(): loads xa_head (child),
steps past its last slot,
child->parent is still old head
child->parent = NULL
xa_unlock()
quiescent state
<grace period ends>
radix_tree_node_rcu_free(old head)
reads old head's slots[], shift,
offset and parent
The grace period does not wait for CPU 1, which reported its quiescent
state before its critical section began; holding xa_lock delays the end of
the grace period, not its start. The start can fall inside the window
when an interrupt arrives in it (interrupts are enabled under xa_lock(),
and RCU core processing may run on interrupt exit), when callbacks are
offloaded (rcu_nocbs=) and the rcuog kthread on another CPU handles the
callback, when many callbacks are queued, or while the writer is preempted
under PREEMPT_RT. Interrupts, and in a guest a preempted vCPU, also
stretch the window.
After the climb, xas_find(), xas_find_marked() and xas_next() resume in
the old head at the slot after the child and read its slots[] and shift
(xas_find_marked() also its mark bitmaps); xas_prev(), for which the child
is the first slot, steps past the old head at once and reads its offset
and parent, as the others do when they reach its end. Nothing in the walk
notices that the node is gone. The climb takes ->parent as it is, no
lockless path looks at node->array (XA_RCU_FREE), and xas_shrink() stores
XA_RETRY_ENTRY in slot 0 of the old head only when the head shrinks to a
single entry, not to a node; the walker does not look at slot 0 anyway.
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 returns that array's entries or descends and climbs into its nodes.
The order dates from the introduction of xas_shrink() in the commit below,
which reimplemented radix_tree_shrink(). radix_tree_shrink() clears the
child's parent pointer before it replaces the head and frees the old node,
and still does in lib/radix-tree.c. The commit gives no reason for the
different order and nothing depends on it: xas_update() and xa_node_free()
only touch the old head.
Clear the child's parent pointer before freeing the old head, as
radix_tree_shrink() does. The stores are the same, the tree and the
xa_state the caller sees are the same, and a walker that starts after the
callback's grace period has begun sees the cleared pointer, like every
store before call_rcu(), and ends its walk at the new head, which covers
every index that the old head had an entry for.
A check in the radix-tree test harness that no node passed to
xa_node_free() is still the parent of a node reachable from xa_head fails
in xas_shrink() 4731 times in the XArray tests without this patch and
never with it. No test is added: the race is not deterministic and the
check needs a hook on xa_node_free(). A harness race test (readers
walking the whole array with the four climbing walkers while a writer
stores and erases an entry that adds three levels above the leaf) did not
hit the window in 20 runs of 200000 erases; with a 1 ms sleep injected
after xa_node_free() in xas_shrink(), every one of 20 runs reported a
heap-use-after-free in __xas_next() or __xas_prev() under
AddressSanitizer, and none did with this patch and the same sleep. On a
kernel (x86_64 defconfig + KASAN, QEMU), with a 100 ms delay injected at
the same place, a walk that starts on another CPU 20 ms into the window
climbs to the old head in each of 20 rounds, and KASAN reports a
slab-use-after-free of the radix_tree_node freed from rcu_core() when the
walk takes its next step; with this patch, the walk ends at the new head.
The XArray and IDA self-tests pass on x86_64 and riscv64.
Found while formally verifying xas_store() against the kernel binary.
Link: https://lore.kernel.org/20261012202549.772887-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>
Assisted-by: LLM
Cc: Matthew Wilcox (Oracle) <willy@infradead.org>
Cc: <stable@vger.kernel.org>
---
lib/xarray.c | 3 ++-
1 file changed, 2 insertions(+), 1 deletion(-)
--- a/lib/xarray.c~xarray-clear-the-new-heads-parent-before-freeing-the-old-head
+++ a/lib/xarray.c
@@ -471,11 +471,12 @@ static void xas_shrink(struct xa_state *
if (!xa_is_node(entry))
RCU_INIT_POINTER(node->slots[0], XA_RETRY_ENTRY);
xas_update(xas, node);
+ if (xa_is_node(entry))
+ xa_to_node(entry)->parent = NULL;
xa_node_free(node);
if (!xa_is_node(entry))
break;
node = xa_to_node(entry);
- node->parent = NULL;
}
}
_
Patches currently in -mm which might be from nickolai@csail.mit.edu are
mm-mlock-use-a-long-for-the-page-count-in-mlock_fixup.patch
mm-truncate-fix-the-zeroing-end-of-pagecache_isize_extended.patch
resource-report-a-devm_request_resource-conflict-under-the-lock.patch
mm-bdi-reset-min_ratio-after-the-sysfs-attributes-are-gone.patch
xarray-clear-the-new-heads-parent-before-freeing-the-old-head.patch
mm-vmalloc-read-vm_map_ram-block-regions-from-the-requested-offset.patch
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: + xarray-clear-the-new-heads-parent-before-freeing-the-old-head.patch added to mm-unstable branch
2026-10-23 18:11 + xarray-clear-the-new-heads-parent-before-freeing-the-old-head.patch added to mm-unstable branch Andrew Morton
@ 2026-10-27 17:41 ` Matthew Wilcox
2026-10-27 18:13 ` Andrew Morton
0 siblings, 1 reply; 3+ messages in thread
From: Matthew Wilcox @ 2026-10-27 17:41 UTC (permalink / raw)
To: Andrew Morton; +Cc: mm-commits, stable, nickolai
i said this patch wasn't acceptable with the commit message the way it
was, and the very next mail i get is you taking it into your tree.
please stop doing this, it really makes me wonder if i have any value
left.
On Fri, Oct 23, 2026 at 11:11:59AM -0700, Andrew Morton wrote:
>
> The patch titled
> Subject: xarray: clear the new head's parent before freeing the old head
> has been added to the -mm mm-unstable branch. Its filename is
> xarray-clear-the-new-heads-parent-before-freeing-the-old-head.patch
>
> This patch will shortly appear at
> https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/xarray-clear-the-new-heads-parent-before-freeing-the-old-head.patch
>
> This patch will later appear in the mm-unstable branch at
> git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
>
> Before you just go and hit "reply", please:
> a) Consider who else should be cc'ed
> b) Prefer to cc a suitable mailing list as well
> c) Ideally: find the original patch on the mailing list and do a
> reply-to-all to that, adding suitable additional cc's
>
> *** Remember to use Documentation/process/submit-checklist.rst when testing your code ***
>
> The -mm tree is included into linux-next via various
> branches at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
> and is updated there most days
>
> ------------------------------------------------------
> From: Nickolai Zeldovich <nickolai@csail.mit.edu>
> Subject: xarray: clear the new head's parent before freeing the old head
> Date: Mon, 12 Oct 2026 16:25:49 -0400
>
> When xas_shrink() replaces the head node of an array with the node in its
> slot 0, it stores the child in xa_head, passes the old head to
> xa_node_free(), which queues it with call_rcu(), and only then clears the
> child's ->parent pointer. In between, a lockless walker can still reach
> the old head, not from xa_head but upwards from the new head: xas_find(),
> xas_find_marked(), xas_next() and xas_prev() climb through xa_parent()
> when they step past the end of a node. RCU does not protect a walker that
> gets there: 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 parent pointer is cleared.
>
> CPU 0: xa_erase(), xa_lock held CPU 1: RCU walker, e.g. xa_find()
>
> xas_shrink()
> xa->xa_head = child
> xa_node_free(old head)
> call_rcu()
> <grace period starts>
> passes a quiescent state
> rcu_read_lock()
> xas_find(): loads xa_head (child),
> steps past its last slot,
> child->parent is still old head
> child->parent = NULL
> xa_unlock()
> quiescent state
> <grace period ends>
> radix_tree_node_rcu_free(old head)
> reads old head's slots[], shift,
> offset and parent
>
> The grace period does not wait for CPU 1, which reported its quiescent
> state before its critical section began; holding xa_lock delays the end of
> the grace period, not its start. The start can fall inside the window
> when an interrupt arrives in it (interrupts are enabled under xa_lock(),
> and RCU core processing may run on interrupt exit), when callbacks are
> offloaded (rcu_nocbs=) and the rcuog kthread on another CPU handles the
> callback, when many callbacks are queued, or while the writer is preempted
> under PREEMPT_RT. Interrupts, and in a guest a preempted vCPU, also
> stretch the window.
>
> After the climb, xas_find(), xas_find_marked() and xas_next() resume in
> the old head at the slot after the child and read its slots[] and shift
> (xas_find_marked() also its mark bitmaps); xas_prev(), for which the child
> is the first slot, steps past the old head at once and reads its offset
> and parent, as the others do when they reach its end. Nothing in the walk
> notices that the node is gone. The climb takes ->parent as it is, no
> lockless path looks at node->array (XA_RCU_FREE), and xas_shrink() stores
> XA_RETRY_ENTRY in slot 0 of the old head only when the head shrinks to a
> single entry, not to a node; the walker does not look at slot 0 anyway.
> 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 returns that array's entries or descends and climbs into its nodes.
>
> The order dates from the introduction of xas_shrink() in the commit below,
> which reimplemented radix_tree_shrink(). radix_tree_shrink() clears the
> child's parent pointer before it replaces the head and frees the old node,
> and still does in lib/radix-tree.c. The commit gives no reason for the
> different order and nothing depends on it: xas_update() and xa_node_free()
> only touch the old head.
>
> Clear the child's parent pointer before freeing the old head, as
> radix_tree_shrink() does. The stores are the same, the tree and the
> xa_state the caller sees are the same, and a walker that starts after the
> callback's grace period has begun sees the cleared pointer, like every
> store before call_rcu(), and ends its walk at the new head, which covers
> every index that the old head had an entry for.
>
> A check in the radix-tree test harness that no node passed to
> xa_node_free() is still the parent of a node reachable from xa_head fails
> in xas_shrink() 4731 times in the XArray tests without this patch and
> never with it. No test is added: the race is not deterministic and the
> check needs a hook on xa_node_free(). A harness race test (readers
> walking the whole array with the four climbing walkers while a writer
> stores and erases an entry that adds three levels above the leaf) did not
> hit the window in 20 runs of 200000 erases; with a 1 ms sleep injected
> after xa_node_free() in xas_shrink(), every one of 20 runs reported a
> heap-use-after-free in __xas_next() or __xas_prev() under
> AddressSanitizer, and none did with this patch and the same sleep. On a
> kernel (x86_64 defconfig + KASAN, QEMU), with a 100 ms delay injected at
> the same place, a walk that starts on another CPU 20 ms into the window
> climbs to the old head in each of 20 rounds, and KASAN reports a
> slab-use-after-free of the radix_tree_node freed from rcu_core() when the
> walk takes its next step; with this patch, the walk ends at the new head.
> The XArray and IDA self-tests pass on x86_64 and riscv64.
>
> Found while formally verifying xas_store() against the kernel binary.
>
> Link: https://lore.kernel.org/20261012202549.772887-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>
> Assisted-by: LLM
> Cc: Matthew Wilcox (Oracle) <willy@infradead.org>
> Cc: <stable@vger.kernel.org>
> ---
>
> lib/xarray.c | 3 ++-
> 1 file changed, 2 insertions(+), 1 deletion(-)
>
> --- a/lib/xarray.c~xarray-clear-the-new-heads-parent-before-freeing-the-old-head
> +++ a/lib/xarray.c
> @@ -471,11 +471,12 @@ static void xas_shrink(struct xa_state *
> if (!xa_is_node(entry))
> RCU_INIT_POINTER(node->slots[0], XA_RETRY_ENTRY);
> xas_update(xas, node);
> + if (xa_is_node(entry))
> + xa_to_node(entry)->parent = NULL;
> xa_node_free(node);
> if (!xa_is_node(entry))
> break;
> node = xa_to_node(entry);
> - node->parent = NULL;
> }
> }
>
> _
>
> Patches currently in -mm which might be from nickolai@csail.mit.edu are
>
> mm-mlock-use-a-long-for-the-page-count-in-mlock_fixup.patch
> mm-truncate-fix-the-zeroing-end-of-pagecache_isize_extended.patch
> resource-report-a-devm_request_resource-conflict-under-the-lock.patch
> mm-bdi-reset-min_ratio-after-the-sysfs-attributes-are-gone.patch
> xarray-clear-the-new-heads-parent-before-freeing-the-old-head.patch
> mm-vmalloc-read-vm_map_ram-block-regions-from-the-requested-offset.patch
>
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: + xarray-clear-the-new-heads-parent-before-freeing-the-old-head.patch added to mm-unstable branch
2026-10-27 17:41 ` Matthew Wilcox
@ 2026-10-27 18:13 ` Andrew Morton
0 siblings, 0 replies; 3+ messages in thread
From: Andrew Morton @ 2026-10-27 18:13 UTC (permalink / raw)
To: Matthew Wilcox; +Cc: mm-commits, stable, nickolai
On Tue, 27 Oct 2026 17:41:59 +0000 Matthew Wilcox <willy@infradead.org> wrote:
>
> i said this patch wasn't acceptable with the commit message the way it
> was, and the very next mail i get is you taking it into your tree.
> please stop doing this, it really makes me wonder if i have any value
> left.
You said the code change itself was OK so I grabbed it for testing and
added a note "TBU (changelog)".
So it won't be going any further until that open issue is resolved.
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2026-10-27 18:13 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2026-10-23 18:11 + xarray-clear-the-new-heads-parent-before-freeing-the-old-head.patch added to mm-unstable branch Andrew Morton
2026-10-27 17:41 ` Matthew Wilcox
2026-10-27 18:13 ` Andrew Morton
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.