From: Hui Zhu 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 --- 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