[PATCH] maple_tree: Annotate lockless pivot reads for KCSAN

["Hui Zhu" <hui.zhu@linux.dev>]

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