maple_tree: KCSAN: data-race in mas_wr_node_store / mtree_range_walk
Subject: [BUG] maple_tree: KCSAN: data-race in mas_wr_node_store / mtree_range_walk
Dear Maintainers,
We are writing to report a KCSAN-detected data-race vulnerability in the Linux kernel. This bug was found by our custom fuzzing tool, RacePilot. The bug occurs in the maple tree component during concurrent node storage manipulation and tree traversal/RCU walk operations. We observed this on the Linux kernel version 6.18.0-08691-g2061f18ad76e-dirty.
Call Trace & Context
==================================================================
BUG: KCSAN: data-race in mas_wr_node_store / mtree_range_walk
write to 0xffff888023e00900 of 8 bytes by task 62996 on cpu 0:
mte_set_node_dead home/kfuzz/linux/lib/maple_tree.c:335 [inline] mas_put_in_tree home/kfuzz/linux/lib/maple_tree.c:1571 [inline] mas_replace_node home/kfuzz/linux/lib/maple_tree.c:1587 [inline] mas_wr_node_store+0xa5c/0xc10 home/kfuzz/linux/lib/maple_tree.c:3568 mas_wr_store_entry+0xabd/0x1120 home/kfuzz/linux/lib/maple_tree.c:3780 mas_store_prealloc+0x47c/0xa60 home/kfuzz/linux/lib/maple_tree.c:5191 vma_iter_store_overwrite home/kfuzz/linux/mm/vma.h:481 [inline] vma_iter_store_new home/kfuzz/linux/mm/vma.h:488 [inline] __mmap_new_vma home/kfuzz/linux/mm/vma.c:2508 [inline] __mmap_region+0x12d5/0x1ef0 home/kfuzz/linux/mm/vma.c:2681 mmap_region+0x15f/0x260 home/kfuzz/linux/mm/vma.c:2751 do_mmap+0x754/0xcd0 home/kfuzz/linux/mm/mmap.c:558 vm_mmap_pgoff+0x15d/0x2e0 home/kfuzz/linux/mm/util.c:587 ksys_mmap_pgoff+0x7d/0x380 home/kfuzz/linux/mm/mmap.c:604 __do_sys_mmap home/kfuzz/linux/arch/x86/kernel/sys_x86_64.c:89 [inline] __se_sys_mmap home/kfuzz/linux/arch/x86/kernel/sys_x86_64.c:82 [inline] __x64_sys_mmap+0x71/0xa0 home/kfuzz/linux/arch/x86/kernel/sys_x86_64.c:82 x64_sys_call+0x1b42/0x2030 home/kfuzz/linux/arch/x86/include/generated/asm/syscalls_64.h:10 do_syscall_x64 home/kfuzz/linux/arch/x86/entry/syscall_64.c:63 [inline] do_syscall_64+0xae/0x2c0 home/kfuzz/linux/arch/x86/entry/syscall_64.c:94 entry_SYSCALL_64_after_hwframe+0x77/0x7f
read to 0xffff888023e00900 of 8 bytes by task 62997 on cpu 1:
ma_dead_node home/kfuzz/linux/lib/maple_tree.c:576 [inline] mtree_range_walk+0x11e/0x630 home/kfuzz/linux/lib/maple_tree.c:2594 mas_state_walk home/kfuzz/linux/lib/maple_tree.c:3313 [inline] mas_walk+0x2a4/0x400 home/kfuzz/linux/lib/maple_tree.c:4617 lock_vma_under_rcu+0xd3/0x710 home/kfuzz/linux/mm/mmap_lock.c:238 do_user_addr_fault home/kfuzz/linux/arch/x86/mm/fault.c:1327 [inline] handle_page_fault home/kfuzz/linux/arch/x86/mm/fault.c:1476 [inline] exc_page_fault+0x294/0x10d0 home/kfuzz/linux/arch/x86/mm/fault.c:1532 asm_exc_page_fault+0x26/0x30 home/kfuzz/linux/arch/x86/include/asm/idtentry.h:618
value changed: 0xffff88800bf0d706 -> 0xffff888023e00900
Reported by Kernel Concurrency Sanitizer on:
CPU: 1 UID: 0 PID: 62997 Comm: syz.8.4355 Not tainted 6.18.0-08691-g2061f18ad76e-dirty #42 PREEMPT(voluntary) Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.15.0-1 04/01/2014 ==================================================================
Execution Flow & Code Context
The CPU 0 task is currently modifying the maple tree mapping memory ranges via __mmap_region. The tree update routine uses mas_wr_node_store(), which calls mas_replace_node() to swap the old node with the new one. As part of replacing the node, it calls mte_set_node_dead(), performing a plain write to update the node->parent pointer to point to itself to indicate the node is dead:
```c
// lib/maple_tree.c
static inline void mte_set_node_dead(struct maple_enode *mn)
{
mte_to_node(mn)->parent = ma_parent_ptr(mte_to_node(mn)); // <-- Write
smp_wmb(); /* Needed for RCU */
}
```Simultaneously, CPU 1 tries to handle a page fault with lockless concurrent RCU lookup using lock_vma_under_rcu. The maple tree traversal routines mtree_range_walk() calls ma_dead_node() on the nodes it fetches to ensure it hasn't stepped into a dead tree node. ma_dead_node() locklessly fetches the node->parent using a simple unannotated fetch in C:
```c
// lib/maple_tree.c
static __always_inline bool ma_dead_node(const struct maple_node *node)
{
struct maple_node *parent;
/* Do not reorder reads from the node prior to the parent check */
smp_rmb();
parent = (void *)((unsigned long)node->parent & ~MAPLE_NODE_MASK); // <-- Lockless Read
return (parent == node);
}
```Root Cause Analysis
A data race occurs over node->parent between the writer updating it to indicate tree modification explicitly (via mte_set_node_dead()) and the fast-path page fault traversal logic trying to deduce if the node is live concurrently (ma_dead_node()). The lockless reader runs while the writer makes an unsynchronized plain store in C. Unfortunately, we were unable to generate a reproducer for this bug.
Potential Impact
If ma_dead_node() reads a partially torn or out-of-date pointer due to missing compiler annotations (read-tearing/store-tearing architectures or aggressive optimizations like value caching and hoisting), a dead node could be erroneously evaluated as alive (or vice versa). This could lead to a use-after-free, memory corruption, infinite loops inside the maple_tree navigation routines, or local Denial of Service (DoS) scenarios under heavy concurrent page-faulting load.
Proposed Fix
To safely resolve this data race without compromising the performance of the RCU walk path, we suggest adding standard Linux kernel concurrent annotations around the node->parent access manually. The writer should use WRITE_ONCE() and the reader should fetch the pointer context via READ_ONCE().
```diff
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -332,7 +332,7 @@ static inline struct maple_node *mas_mn(const struct ma_state *mas)
static inline void mte_set_node_dead(struct maple_enode *mn)
{
- mte_to_node(mn)->parent = ma_parent_ptr(mte_to_node(mn));
+ WRITE_ONCE(mte_to_node(mn)->parent, ma_parent_ptr(mte_to_node(mn)));
smp_wmb(); /* Needed for RCU */
}
@@ -576,7 +576,8 @@ static __always_inline bool ma_dead_node(const struct maple_node *node)
/* Do not reorder reads from the node prior to the parent check */
smp_rmb();
- parent = (void *)((unsigned long)node->parent & ~MAPLE_NODE_MASK);
+ parent = (void *)((unsigned long)READ_ONCE(node->parent) &
+ ~MAPLE_NODE_MASK);
return (parent == node);
}
```We would be highly honored if this could be of any help.
Best regards,
RacePilot Team
Quoted 76 lines · Jianzhou Zhao
Subject: [BUG]
maple_tree: KCSAN: data-race inmas_wr_node_store/mtree_range_walkDear Maintainers,
We are writing to report a KCSAN-detected data-race vulnerability in the Linux kernel. This bug was found by our custom fuzzing tool, RacePilot. The bug occurs in the maple tree component during concurrent node storage manipulation and tree traversal/RCU walk operations. We observed this on the Linux kernel version 6.18.0-08691-g2061f18ad76e-dirty.
Call Trace & Context
==================================================================BUG: KCSAN: data-race in mas_wr_node_store / mtree_range_walkwrite to
0xffff888023e00900of 8 bytes by task 62996 on cpu 0:mte_set_node_dead home/kfuzz/linux/lib/maple_tree.c:335 [inline] mas_put_in_tree home/kfuzz/linux/lib/maple_tree.c:1571 [inline] mas_replace_node home/kfuzz/linux/lib/maple_tree.c:1587 [inline] mas_wr_node_store+0xa5c/0xc10 home/kfuzz/linux/lib/maple_tree.c:3568 mas_wr_store_entry+0xabd/0x1120 home/kfuzz/linux/lib/maple_tree.c:3780 mas_store_prealloc+0x47c/0xa60 home/kfuzz/linux/lib/maple_tree.c:5191 vma_iter_store_overwrite home/kfuzz/linux/mm/vma.h:481 [inline] vma_iter_store_new home/kfuzz/linux/mm/vma.h:488 [inline] __mmap_new_vma home/kfuzz/linux/mm/vma.c:2508 [inline] __mmap_region+0x12d5/0x1ef0 home/kfuzz/linux/mm/vma.c:2681 mmap_region+0x15f/0x260 home/kfuzz/linux/mm/vma.c:2751 do_mmap+0x754/0xcd0 home/kfuzz/linux/mm/mmap.c:558 vm_mmap_pgoff+0x15d/0x2e0 home/kfuzz/linux/mm/util.c:587 ksys_mmap_pgoff+0x7d/0x380 home/kfuzz/linux/mm/mmap.c:604 __do_sys_mmap home/kfuzz/linux/arch/x86/kernel/sys_x86_64.c:89 [inline] __se_sys_mmap home/kfuzz/linux/arch/x86/kernel/sys_x86_64.c:82 [inline] __x64_sys_mmap+0x71/0xa0 home/kfuzz/linux/arch/x86/kernel/sys_x86_64.c:82 x64_sys_call+0x1b42/0x2030 home/kfuzz/linux/arch/x86/include/generated/asm/syscalls_64.h:10 do_syscall_x64 home/kfuzz/linux/arch/x86/entry/syscall_64.c:63 [inline] do_syscall_64+0xae/0x2c0 home/kfuzz/linux/arch/x86/entry/syscall_64.c:94 entry_SYSCALL_64_after_hwframe+0x77/0x7fread to
0xffff888023e00900of 8 bytes by task 62997 on cpu 1:ma_dead_node home/kfuzz/linux/lib/maple_tree.c:576 [inline] mtree_range_walk+0x11e/0x630 home/kfuzz/linux/lib/maple_tree.c:2594 mas_state_walk home/kfuzz/linux/lib/maple_tree.c:3313 [inline] mas_walk+0x2a4/0x400 home/kfuzz/linux/lib/maple_tree.c:4617 lock_vma_under_rcu+0xd3/0x710 home/kfuzz/linux/mm/mmap_lock.c:238 do_user_addr_fault home/kfuzz/linux/arch/x86/mm/fault.c:1327 [inline] handle_page_fault home/kfuzz/linux/arch/x86/mm/fault.c:1476 [inline] exc_page_fault+0x294/0x10d0 home/kfuzz/linux/arch/x86/mm/fault.c:1532 asm_exc_page_fault+0x26/0x30 home/kfuzz/linux/arch/x86/include/asm/idtentry.h:618value changed:
0xffff88800bf0d706->0xffff888023e00900Reported by Kernel Concurrency Sanitizer on:
CPU: 1 UID: 0 PID: 62997 Comm: syz.8.4355 Not tainted 6.18.0-08691-g2061f18ad76e-dirty #42 PREEMPT(voluntary) Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.15.0-1 04/01/2014 ==================================================================Execution Flow & Code Context
The CPU 0 task is currently modifying the maple tree mapping memory ranges via__mmap_region. The tree update routine usesmas_wr_node_store(), which callsmas_replace_node()to swap the old node with the new one. As part of replacing the node, it callsmte_set_node_dead(), performing a plain write to update thenode->parentpointer to point to itself to indicate the node is dead:```c // lib/maple_tree.c static inline void mte_set_node_dead(struct maple_enode *mn) { mte_to_node(mn)->parent = ma_parent_ptr(mte_to_node(mn)); // <-- Write smp_wmb(); /* Needed for RCU */ } ```Simultaneously, CPU 1 tries to handle a page fault with lockless concurrent RCU lookup using
lock_vma_under_rcu. The maple tree traversal routinesmtree_range_walk()callsma_dead_node()on the nodes it fetches to ensure it hasn't stepped into a dead tree node.ma_dead_node()locklessly fetches thenode->parentusing a simple unannotated fetch in C:```c // lib/maple_tree.c static __always_inline bool ma_dead_node(const struct maple_node *node) { struct maple_node *parent; /* Do not reorder reads from the node prior to the parent check */ smp_rmb(); parent = (void *)((unsigned long)node->parent & ~MAPLE_NODE_MASK); // <-- Lockless Read return (parent == node); } ```
Quoted 7 lines
Root Cause Analysis
A data race occurs overnode->parentbetween the writer updating it to indicate tree modification explicitly (viamte_set_node_dead()) and the fast-path page fault traversal logic trying to deduce if the node is live concurrently (ma_dead_node()). The lockless reader runs while the writer makes an unsynchronized plain store in C. Unfortunately, we were unable to generate a reproducer for this bug.Potential Impact
Ifma_dead_node()reads a partially torn or out-of-date pointer due to missing compiler annotations (read-tearing/store-tearing architectures or aggressive optimizations like value caching and hoisting), a dead node could be erroneously evaluated as alive (or vice versa). This could lead to a use-after-free, memory corruption, infinite loops inside themaple_treenavigation routines, or local Denial of Service (DoS) scenarios under heavy concurrent page-faulting load.
What arch allows tearing across reading/writing of a pointer?
The node is checked if it's dead or not twice: Once before operating on the node and once after the information has been read from the node. With the included smp_wmb() and smp_rmb(), I believe this is sufficient to ensure we do not use data from a dead node.
Does this explain why you were unable to produce an issue?
Quoted 29 lines
Proposed Fix
To safely resolve this data race without compromising the performance of the RCU walk path, we suggest adding standard Linux kernel concurrent annotations around thenode->parentaccess manually. The writer should useWRITE_ONCE()and the reader should fetch the pointer context viaREAD_ONCE().```diff
lib/maple_tree.c +3
-2@@ -332,7 +332,7 @@ static inline struct maple_node *mas_mn(const struct ma_state *mas)static inline void mte_set_node_dead (struct maple_enode *mn) { -mte_to_node (mn)->parent =ma_parent_ptr (mte_to_node (mn)); +WRITE_ONCE (mte_to_node (mn)->parent,ma_parent_ptr (mte_to_node (mn)));smp_wmb ();/* Needed for RCU */ }@@ -576,7 +576,8 @@ static __always_inline bool ma_dead_node(const struct maple_node *node)/* Do not reorder reads from the node prior to the parent check */ smp_rmb (); - parent = (void *)((unsigned long )node->parent & ~MAPLE_NODE_MASK ); + parent = (void *)((unsigned long )READ_ONCE (node->parent) & + ~MAPLE_NODE_MASK );return (parent == node); }```
We would be highly honored if this could be of any help.
Best regards,
RacePilot Team