[PATCH] maple_tree: Annotate lockless pivot reads for KCSAN

[PATCH] maple_tree: Annotate lockless pivot reads for KCSAN

[Hui Zhu]

From: Hui Zhu <zhuhui@kylinos.cn>

In RCU mode, replaced maple nodes are marked dead and freed via RCU
after the new node has been published.  Arming the RCU free writes
node->rcu.next and node->rcu.func, which share storage with
pivot[0] and pivot[1] (see struct maple_node), while lockless
readers may still walk the dead node.  These stores therefore race
with the pivot loads performed by the walkers.

This is harmless: the writer marks the node dead with an smp_wmb()
before arming the rcu_head, and the walkers re-check ma_dead_node()
after reading the node and restart the walk when the node is dead,
so any pivot read that raced with the rcu_head stores is discarded.
KCSAN cannot see this protocol and reports the plain accesses, so
annotate the lockless pivot reads with data_race() through a new
ma_pivot_rcu() helper.

Found by fuzzing on a 6.6 kernel; the race still exists on
mainline.  No functional change intended.

BUG: KCSAN: data-race in __call_rcu_common.constprop.0 / mas_walk
write to 0xffff8db9bb7cde10 of 8 bytes by task 1065 on cpu 7:
__call_rcu_common.constprop.0+0x47/0x5d0
call_rcu+0x12/0x20
mas_wr_node_store+0x7a6/0x7d0
mas_wr_store_entry+0x3af/0x760
mas_store_prealloc+0x419/0x8a0
__mmap_region+0x7fa/0x1240
mmap_region+0x177/0x1c0
do_mmap+0x636/0x970
vm_mmap_pgoff+0x193/0x2e0
ksys_mmap_pgoff+0x276/0x2f0
__x64_sys_mmap+0x5b/0x80
x64_sys_call+0x1b9b/0x1ee0
do_syscall_64+0x5d/0x1b0
entry_SYSCALL_64_after_hwframe+0x76/0xe0
read to 0xffff8db9bb7cde10 of 8 bytes by task 1061 on cpu 4:
mas_walk+0x424/0x810
lock_vma_under_rcu+0x150/0x250
do_user_addr_fault+0x195/0x7d0
exc_page_fault+0x5d/0xd0
asm_exc_page_fault+0x26/0x30
Reported by Kernel Concurrency Sanitizer on:
CPU: 4 PID: 1061 Comm: syz-fuzzer Not tainted 6.6.127
Hardware name: QEMU Standard PC (i440FX + PIIX, 1996)

Fixes: 54a611b60590 ("Maple Tree: add new data structure")
Signed-off-by: Hui Zhu <zhuhui@kylinos.cn>
---
 lib/maple_tree.c | 57 ++++++++++++++++++++++++++++++++++++------------
 1 file changed, 43 insertions(+), 14 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 1aba6cced713..63dfc7edad81 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -546,6 +546,35 @@ static inline unsigned long *ma_pivots(struct maple_node *node,
 	return NULL;
 }
 
+/*
+ * ma_pivot_rcu() - Read a pivot from a node that may be concurrently
+ * freed via RCU.
+ * @pivots: The pointer to the maple node pivots
+ * @offset: The offset into the pivot array
+ *
+ * Lockless readers may walk a node that the writer has already marked
+ * dead and queued for RCU freeing.  The rcu_head used to queue the
+ * node for freeing shares storage with pivot[0] and pivot[1] (see
+ * struct maple_node), so arming the rcu_head races with reads of
+ * those pivots.
+ *
+ * Such reads are safe: the writer marks the node dead with an
+ * smp_wmb() before arming the rcu_head (see mte_set_node_dead()) and
+ * the walkers re-check ma_dead_node() with an smp_rmb() after reading
+ * the node, restarting the walk when the node is dead.  Any pivot
+ * read that raced with the rcu_head stores is discarded.
+ *
+ * Annotate the read so that KCSAN does not report this race.
+ *
+ * Return: The pivot at @offset.
+ */
+static inline unsigned long ma_pivot_rcu(unsigned long *pivots,
+					 unsigned char offset)
+{
+	/* Data race with rcu_head arming of a dying node, see above. */
+	return data_race(pivots[offset]);
+}
+
 /*
  * ma_gaps() - Get a pointer to the maple node gaps.
  * @node: the maple node
@@ -1019,12 +1048,12 @@ static int mas_ascend(struct ma_state *mas)
 
 		if (!set_min && a_slot) {
 			set_min = true;
-			min = pivots[a_slot - 1] + 1;
+			min = ma_pivot_rcu(pivots, a_slot - 1) + 1;
 		}
 
 		if (!set_max && a_slot < mt_pivots[a_type]) {
 			set_max = true;
-			max = pivots[a_slot];
+			max = ma_pivot_rcu(pivots, a_slot);
 		}
 
 		if (unlikely(ma_dead_node(a_node)))
@@ -2097,22 +2126,22 @@ static inline void *mtree_range_walk(struct ma_state *mas)
 		end = ma_data_end(node, type, pivots, max);
 		prev_min = min;
 		prev_max = max;
-		if (pivots[0] >= mas->index) {
+		if (ma_pivot_rcu(pivots, 0) >= mas->index) {
 			offset = 0;
-			max = pivots[0];
+			max = ma_pivot_rcu(pivots, 0);
 			goto next;
 		}
 
 		offset = 1;
 		while (offset < end) {
-			if (pivots[offset] >= mas->index) {
-				max = pivots[offset];
+			if (ma_pivot_rcu(pivots, offset) >= mas->index) {
+				max = ma_pivot_rcu(pivots, offset);
 				break;
 			}
 			offset++;
 		}
 
-		min = pivots[offset - 1] + 1;
+		min = ma_pivot_rcu(pivots, offset - 1) + 1;
 next:
 		slots = ma_slots(node, type);
 		next = mt_slot(mas->tree, slots, offset);
@@ -3040,7 +3069,7 @@ static inline void *mtree_lookup_walk(struct ma_state *mas)
 		end = mt_pivots[type];
 		offset = 0;
 		do {
-			if (pivots[offset] >= mas->index)
+			if (ma_pivot_rcu(pivots, offset) >= mas->index)
 				break;
 		} while (++offset < end);
 
@@ -4003,7 +4032,7 @@ static int mas_prev_node(struct ma_state *mas, unsigned long min)
 		return 1;
 
 	if (likely(offset))
-		mas->min = pivots[offset - 1] + 1;
+		mas->min = ma_pivot_rcu(pivots, offset - 1) + 1;
 	mas->max = max;
 	mas->offset = mas_data_end(mas);
 	if (unlikely(mte_dead_node(mas->node)))
@@ -4077,7 +4106,7 @@ static void *mas_prev_slot(struct ma_state *mas, unsigned long min, bool empty)
 		node = mas_mn(mas);
 		type = mte_node_type(mas->node);
 		pivots = ma_pivots(node, type);
-		mas->index = pivots[mas->offset - 1] + 1;
+		mas->index = ma_pivot_rcu(pivots, mas->offset - 1) + 1;
 	}
 
 	slots = ma_slots(node, type);
@@ -4218,7 +4247,7 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty)
 
 	if (mas->max >= max) {
 		if (likely(mas->offset < mas->end))
-			pivot = pivots[mas->offset];
+			pivot = ma_pivot_rcu(pivots, mas->offset);
 		else
 			pivot = mas->max;
 
@@ -4232,11 +4261,11 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty)
 	}
 
 	if (likely(mas->offset < mas->end)) {
-		mas->index = pivots[mas->offset] + 1;
+		mas->index = ma_pivot_rcu(pivots, mas->offset) + 1;
 again:
 		mas->offset++;
 		if (likely(mas->offset < mas->end))
-			mas->last = pivots[mas->offset];
+			mas->last = ma_pivot_rcu(pivots, mas->offset);
 		else
 			mas->last = mas->max;
 	} else  {
@@ -4258,7 +4287,7 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty)
 		node = mas_mn(mas);
 		type = mte_node_type(mas->node);
 		pivots = ma_pivots(node, type);
-		mas->last = pivots[0];
+		mas->last = ma_pivot_rcu(pivots, 0);
 	}
 
 	slots = ma_slots(node, type);
-- 
2.53.0

Re: [PATCH] maple_tree: Annotate lockless pivot reads for KCSAN

[Andrew Morton]

On Wed, 26 Aug 2026 15:44:30 +0800 "Hui Zhu" <hui.zhu@linux.dev> wrote:

> In RCU mode, replaced maple nodes are marked dead and freed via RCU
> after the new node has been published.  Arming the RCU free writes
> node->rcu.next and node->rcu.func, which share storage with
> pivot[0] and pivot[1] (see struct maple_node), while lockless
> readers may still walk the dead node.  These stores therefore race
> with the pivot loads performed by the walkers.
> 
> This is harmless: the writer marks the node dead with an smp_wmb()
> before arming the rcu_head, and the walkers re-check ma_dead_node()
> after reading the node and restart the walk when the node is dead,
> so any pivot read that raced with the rcu_head stores is discarded.
> KCSAN cannot see this protocol and reports the plain accesses, so
> annotate the lockless pivot reads with data_race() through a new
> ma_pivot_rcu() helper.
> 
> Found by fuzzing on a 6.6 kernel; the race still exists on
> mainline.  No functional change intended.


Thanks.  AI review suggests that the patch is correct, but incomplete?

	https://sashiko.dev/#/patchset/20260826074430.1139325-1-hui.zhu@linux.dev

Re: [PATCH] maple_tree: Annotate lockless pivot reads for KCSAN

[Liam R. Howlett]

On 26/08/26 09:41AM, Andrew Morton wrote:
> On Wed, 26 Aug 2026 15:44:30 +0800 "Hui Zhu" <hui.zhu@linux.dev> wrote:
> 
> > In RCU mode, replaced maple nodes are marked dead and freed via RCU
> > after the new node has been published.  Arming the RCU free writes
> > node->rcu.next and node->rcu.func, which share storage with
> > pivot[0] and pivot[1] (see struct maple_node), while lockless
> > readers may still walk the dead node.  These stores therefore race
> > with the pivot loads performed by the walkers.
> > 
> > This is harmless: the writer marks the node dead with an smp_wmb()
> > before arming the rcu_head, and the walkers re-check ma_dead_node()
> > after reading the node and restart the walk when the node is dead,
> > so any pivot read that raced with the rcu_head stores is discarded.
> > KCSAN cannot see this protocol and reports the plain accesses, so
> > annotate the lockless pivot reads with data_race() through a new
> > ma_pivot_rcu() helper.
> > 
> > Found by fuzzing on a 6.6 kernel; the race still exists on
> > mainline.  No functional change intended.
> 
> 
> Thanks.  AI review suggests that the patch is correct, but incomplete?
> 
> 	https://sashiko.dev/#/patchset/20260826074430.1139325-1-hui.zhu@linux.dev


Yes, this is literally every read of numerous pivots on any reader that
would need something like this.  Most code is shared with the writer
side, so we'll have data_race() annotation where it is not needed there.

I don't like the name of the function and I don't agree that it is worth
doing, especially half of it.  If you notice ma_ functions take a maple
node as the first argument, but your new function takes an array pointer
in the node.

The from address does not agree with the sign-off on the patch.

I also don't think a benign race needs a Fixes tag?

It might be worth looking at other ways to calm kcsans down such as the
type qualifier __data_racy, or maybe the makefile option.

Thanks,
Liam

Re: [PATCH] maple_tree: Annotate lockless pivot reads for KCSAN

[Hui Zhu]

> 
> On 26/08/26 09:41AM, Andrew Morton wrote:
> 
> > 
> > On Wed, 26 Aug 2026 15:44:30 +0800 "Hui Zhu" <hui.zhu@linux.dev> wrote:
> >  
> >  In RCU mode, replaced maple nodes are marked dead and freed via RCU
> >  after the new node has been published. Arming the RCU free writes
> >  node->rcu.next and node->rcu.func, which share storage with
> >  pivot[0] and pivot[1] (see struct maple_node), while lockless
> >  readers may still walk the dead node. These stores therefore race
> >  with the pivot loads performed by the walkers.
> >  
> >  This is harmless: the writer marks the node dead with an smp_wmb()
> >  before arming the rcu_head, and the walkers re-check ma_dead_node()
> >  after reading the node and restart the walk when the node is dead,
> >  so any pivot read that raced with the rcu_head stores is discarded.
> >  KCSAN cannot see this protocol and reports the plain accesses, so
> >  annotate the lockless pivot reads with data_race() through a new
> >  ma_pivot_rcu() helper.
> >  
> >  Found by fuzzing on a 6.6 kernel; the race still exists on
> >  mainline. No functional change intended.
> >  
> >  
> >  Thanks. AI review suggests that the patch is correct, but incomplete?
> >  
> >  https://sashiko.dev/#/patchset/20260826074430.1139325-1-hui.zhu@linux.dev
> > 
> Yes, this is literally every read of numerous pivots on any reader that
> would need something like this. Most code is shared with the writer
> side, so we'll have data_race() annotation where it is not needed there.
> 
> I don't like the name of the function and I don't agree that it is worth
> doing, especially half of it. If you notice ma_ functions take a maple
> node as the first argument, but your new function takes an array pointer
> in the node.
> 
> The from address does not agree with the sign-off on the patch.
> 
> I also don't think a benign race needs a Fixes tag?
> 
> It might be worth looking at other ways to calm kcsans down such as the
> type qualifier __data_racy, or maybe the makefile option.

Hi Liam,

__data_racy is defined as volatile for KCSAN kernels, so the qualifier
has to propagate to every access site: ma_pivots() would return a
volatile pointer, and all the "unsigned long *pivots" locals and helper
parameters in maple_tree.c (about 25 sites) would need the qualifier
too.
It also marks the whole pivot array as racy, while only pivot[0] and
pivot[1] actually overlap the rcu_head.

The Makefile option (KCSAN_SANITIZE_maple_tree.o := n) is a one-liner,
but it disables KCSAN for the entire file, so any real data race
introduced in maple_tree.c later would go unnoticed.

Do you think one of these two is still the better choice, or should I
keep the current approach and fix the patch according to your review
comments?

Best,
Hui

> 
> Thanks,
> Liam
>