BUG: KCSAN: data-race in mas_wr_store_entry / mtree_range_walk

BUG: KCSAN: data-race in mas_wr_store_entry / mtree_range_walk

[Jianzhou Zhao]

Subject: [BUG] maple_tree: KCSAN: data-race in mas_wr_store_entry / mtree_range_walk

Dear Maintainers,

We are writing to report a KCSAN-detected data-race vulnerability in the Linux kernel involving the maple tree subsystem. This bug was found by our custom fuzzing tool, RacePilot. The bug occurs because `mtree_range_walk` reads tree node pivots locklessly while a writer is concurrently updating those bounds through `mas_wr_slot_store` without explicit memory access annotations. We observed this on the Linux kernel version 6.18.0-08691-g2061f18ad76e-dirty.

Call Trace & Context
==================================================================
BUG: KCSAN: data-race in mas_wr_store_entry / mtree_range_walk

write to 0xffff88800c50aa30 of 8 bytes by task 214464 on cpu 1:
 mas_wr_slot_store lib/maple_tree.c:3601 [inline]
 mas_wr_store_entry+0xf54/0x1120 lib/maple_tree.c:3777
 mas_store_prealloc+0x47c/0xa60 lib/maple_tree.c:5191
 vma_iter_store_overwrite mm/vma.h:481 [inline]
 commit_merge+0x3ea/0x740 mm/vma.c:766
 vma_merge_existing_range mm/vma.c:980 [inline]
 vma_modify+0x5ff/0xdd0 mm/vma.c:1620
 vma_modify_flags+0x16c/0x1a0 mm/vma.c:1662
 mprotect_fixup+0x170/0x660 mm/mprotect.c:816
 do_mprotect_pkey+0x5fe/0x930 mm/mprotect.c:990
 __do_sys_mprotect mm/mprotect.c:1011 [inline]
 __se_sys_mprotect mm/mprotect.c:1008 [inline]
 __x64_sys_mprotect+0x47/0x60 mm/mprotect.c:1008
 x64_sys_call+0xc6c/0x2030 arch/x86/include/generated/asm/syscalls_64.h:11
 do_syscall_x64 arch/x86/entry/syscall_64.c:63 [inline]
 do_syscall_64+0xae/0x2c0 arch/x86/entry/syscall_64.c:94
 entry_SYSCALL_64_after_hwframe+0x77/0x7f

read to 0xffff88800c50aa30 of 8 bytes by task 214467 on cpu 0:
 mtree_range_walk+0x368/0x630 lib/maple_tree.c:2581
 mas_state_walk lib/maple_tree.c:3313 [inline]
 mas_walk+0x2a4/0x400 lib/maple_tree.c:4617
 lock_vma_under_rcu+0xd3/0x710 mm/mmap_lock.c:238
 do_user_addr_fault arch/x86/mm/fault.c:1327 [inline]
 handle_page_fault arch/x86/mm/fault.c:1476 [inline]
 exc_page_fault+0x294/0x10d0 arch/x86/mm/fault.c:1532
 asm_exc_page_fault+0x26/0x30 arch/x86/include/asm/idtentry.h:618

value changed: 0x00007f571d344fff -> 0x00007f571d324fff

Reported by Kernel Concurrency Sanitizer on:
CPU: 0 UID: 0 PID: 214467 Comm: syz.8.13076 Not tainted 6.18.0-08691-g2061f18ad76e-dirty #44 PREEMPT(voluntary) 
Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.15.0-1 04/01/2014
==================================================================

Execution Flow & Code Context
During a virtual memory modification (via `mprotect`), `vma_modify` invokes `mas_store_prealloc` which calls `mas_wr_store_entry` -> `mas_wr_slot_store` to insert elements and overwrite node boundaries. This involves updating `wr_mas->pivots` arrays with plain assignments:
```c
// lib/maple_tree.c
static inline void mas_wr_slot_store(struct ma_wr_state *wr_mas)
{
	...
		if (mas->index == wr_mas->r_min) {
			/* Overwriting the range and a part of the next one */
			rcu_assign_pointer(slots[offset], wr_mas->entry);
			wr_mas->pivots[offset] = mas->last; // <-- Plain Write
		} else {
	...
}
```

Concurrently, a page fault handler (`do_user_addr_fault`) tries to lock the VMA under RCU using `mas_walk`, which descends into `mtree_range_walk()`. The reader locklessly accesses `pivots[offset]` values in order to resolve bounding boxes of ranges evaluating exactly against `mas->index`: 
```c
// lib/maple_tree.c
static inline void *mtree_range_walk(struct ma_state *mas)
{
	...
		if (pivots[0] >= mas->index) { // <-- Plain Read
			offset = 0;
			max = pivots[0]; // <-- Potentially double read / torn value
			goto next;
		}

		offset = 1;
		while (offset < end) {
			if (pivots[offset] >= mas->index) { // <-- Plain Read
				max = pivots[offset];
				break;
			}
			offset++;
		}
	...
}
```

Root Cause Analysis
A data race occurs because the maple tree iterates `pivots[]` boundaries out of RCU order and locklessly in the reader, whilst `mas_wr_slot_store()` can execute a concurrent update on the exact same layout. Both accesses are compiled as plain C loads and stores. As `pivots[]` can be updated natively, tearing could occur where `mtree_range_walk` witnesses a split or intermediate bounds state, leading to broken limits being assigned to `max`. 
Furthermore, `pivots[offset]` is fetched repeatedly in sequence in `max = pivots[offset]` creating a risk of fetching inconsistent values across multiple evaluations.
Unfortunately, we were unable to generate a reproducer for this bug.

Potential Impact
A torn pivot read or an inconsistent repeated read can misdirect the range walk entirely, fetching the wrong VMA structures or crashing tree navigation logic. This could result in random local Denial of Service (DoS) faults or unmapped memory panics due to mismatched virtual mappings under high memory stress.

Proposed Fix
To safely inform the compiler that these memory slots are concurrently accessed in RCU readers and avoid torn logic, `WRITE_ONCE()` should be used when updating pivots in `mas_wr_slot_store`. Correspondingly, the walker should fetch the pivot exactly once via `READ_ONCE()` into a single local variable before using it:

```diff
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -2577,15 +2577,18 @@ 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) {
+		
+		unsigned long pivot = READ_ONCE(pivots[0]);
+		if (pivot >= mas->index) {
 			offset = 0;
-			max = pivots[0];
+			max = pivot;
 			goto next;
 		}
 
 		offset = 1;
 		while (offset < end) {
-			if (pivots[offset] >= mas->index) {
-				max = pivots[offset];
+			pivot = READ_ONCE(pivots[offset]);
+			if (pivot >= mas->index) {
+				max = pivot;
 				break;
 			}
@@ -3605,10 +3613,10 @@ static inline void mas_wr_slot_store(struct ma_wr_state *wr_mas)
 		if (mas->index == wr_mas->r_min) {
 			/* Overwriting the range and a part of the next one */
 			rcu_assign_pointer(slots[offset], wr_mas->entry);
-			wr_mas->pivots[offset] = mas->last;
+			WRITE_ONCE(wr_mas->pivots[offset], mas->last);
 		} else {
 			/* Overwriting a part of the range and the next one */
 			rcu_assign_pointer(slots[offset + 1], wr_mas->entry);
-			wr_mas->pivots[offset] = mas->index - 1;
+			WRITE_ONCE(wr_mas->pivots[offset], mas->index - 1);
 			mas->offset++; /* Keep mas accurate. */
 		}
 	} else {
@@ -3621,8 +3629,8 @@ static inline void mas_wr_slot_store(struct ma_wr_state *wr_mas)
 		 */
 		gap |= !mt_slot_locked(mas->tree, slots, offset + 2);
 		rcu_assign_pointer(slots[offset + 1], wr_mas->entry);
-		wr_mas->pivots[offset] = mas->index - 1;
-		wr_mas->pivots[offset + 1] = mas->last;
+		WRITE_ONCE(wr_mas->pivots[offset], mas->index - 1);
+		WRITE_ONCE(wr_mas->pivots[offset + 1], mas->last);
 		mas->offset++; /* Keep mas accurate. */
 	}
```

We would be highly honored if this could be of any help.

Best regards,
RacePilot Team