Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.37 as permitted sender) client-ip=23.128.96.37;
Message-ID: <9c1549f9-78c2-441b-8617-3ea3c080a5a4@alu.unizg.hr>
Date:   Thu, 21 Sep 2023 23:01:05 +0200
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
Content-Language: en-US
To:     maple-tree@lists.infradead.org
Cc:     "Liam R. Howlett" <Liam.Howlett@oracle.com>, linux-mm@kvack.org,
        linux-kernel@vger.kernel.org
From:   Mirsad Todorovac <mirsad.todorovac@alu.unizg.hr>
Subject: BUG: maple_tree: KCSAN: data-race in mas_topiary_replace /
 mtree_range_walk
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Precedence: bulk

Hi,

On the 6.6-rc2 vanilla torvalds tree kernel, KCSAN had reported a number of data-races:

[ 6413.367326] ==================================================================
[ 6413.367349] BUG: KCSAN: data-race in mas_topiary_replace / mtree_range_walk

[ 6413.367375] write to 0xffff8883a0c5db00 of 8 bytes by task 5475 on cpu 24:
[ 6413.367386] mas_topiary_replace (/home/marvin/linux/kernel/torvalds2/lib/maple_tree.c:491 /home/marvin/linux/kernel/torvalds2/lib/maple_tree.c:1701 /home/marvin/linux/kernel/torvalds2/lib/maple_tree.c:2590)
[ 6413.367399] mas_spanning_rebalance.isra.0 (/home/marvin/linux/kernel/torvalds2/lib/maple_tree.c:2664 /home/marvin/linux/kernel/torvalds2/lib/maple_tree.c:2961)
[ 6413.367413] mas_wr_spanning_store.isra.0 (/home/marvin/linux/kernel/torvalds2/lib/maple_tree.c:3894)
[ 6413.367428] mas_wr_store_entry.isra.0 (/home/marvin/linux/kernel/torvalds2/lib/maple_tree.c:4242)
[ 6413.367442] mas_store_prealloc (/home/marvin/linux/kernel/torvalds2/lib/maple_tree.c:256 /home/marvin/linux/kernel/torvalds2/lib/maple_tree.c:5408)
[ 6413.367455] vma_merge (/home/marvin/linux/kernel/torvalds2/mm/internal.h:1127 /home/marvin/linux/kernel/torvalds2/mm/mmap.c:1005)
[ 6413.367466] mprotect_fixup (/home/marvin/linux/kernel/torvalds2/mm/mprotect.c:632)
[ 6413.367480] do_mprotect_pkey (/home/marvin/linux/kernel/torvalds2/mm/mprotect.c:819)
[ 6413.367494] __x64_sys_mprotect (/home/marvin/linux/kernel/torvalds2/mm/mprotect.c:837)
[ 6413.367503] do_syscall_64 (/home/marvin/linux/kernel/torvalds2/arch/x86/entry/common.c:50 /home/marvin/linux/kernel/torvalds2/arch/x86/entry/common.c:80)
[ 6413.367517] entry_SYSCALL_64_after_hwframe (/home/marvin/linux/kernel/torvalds2/arch/x86/entry/entry_64.S:120)

[ 6413.367534] read to 0xffff8883a0c5db00 of 8 bytes by task 5558 on cpu 11:
[ 6413.367545] mtree_range_walk (/home/marvin/linux/kernel/torvalds2/lib/maple_tree.c:539 /home/marvin/linux/kernel/torvalds2/lib/maple_tree.c:2789)
[ 6413.367556] mas_walk (/home/marvin/linux/kernel/torvalds2/lib/maple_tree.c:251 /home/marvin/linux/kernel/torvalds2/lib/maple_tree.c:4844)
[ 6413.367567] lock_vma_under_rcu (/home/marvin/linux/kernel/torvalds2/mm/memory.c:5436)
[ 6413.367579] do_user_addr_fault (/home/marvin/linux/kernel/torvalds2/arch/x86/mm/fault.c:1357)
[ 6413.367593] exc_page_fault (/home/marvin/linux/kernel/torvalds2/./arch/x86/include/asm/paravirt.h:695 /home/marvin/linux/kernel/torvalds2/arch/x86/mm/fault.c:1513 /home/marvin/linux/kernel/torvalds2/arch/x86/mm/fault.c:1561)
[ 6413.367602] asm_exc_page_fault (/home/marvin/linux/kernel/torvalds2/./arch/x86/include/asm/idtentry.h:570)

[ 6413.367617] value changed: 0xffff888341d43116 -> 0xffff888340f92116

[ 6413.367632] Reported by Kernel Concurrency Sanitizer on:
[ 6413.367640] CPU: 11 PID: 5558 Comm: ThreadPoolForeg Tainted: G             L     6.6.0-rc2-kcsan-00143-gb5cbe7c00aa0 #41
[ 6413.367653] Hardware name: ASRock X670E PG Lightning/X670E PG Lightning, BIOS 1.21 04/26/2023
[ 6413.367660] ==================================================================

For your convenience, took the trouble of finding those suspicious lines of code:

The write side:

lib/maple_tree.c:491
--------------------
   456 /*
   457  * mas_set_parent() - Set the parent node and encode the slot
   458  * @enode: The encoded maple node.
   459  * @parent: The encoded maple node that is the parent of @enode.
   460  * @slot: The slot that @enode resides in @parent.
   461  *
   462  * Slot number is encoded in the enode->parent bit 3-6 or 2-6, depending on the
   463  * parent type.
   464  */
   465 static inline
   466 void mas_set_parent(struct ma_state *mas, struct maple_enode *enode,
   467                     const struct maple_enode *parent, unsigned char slot)
   468 {
   469         unsigned long val = (unsigned long)parent;
   470         unsigned long shift;
   471         unsigned long type;
   472         enum maple_type p_type = mte_node_type(parent);
   473
   474         MAS_BUG_ON(mas, p_type == maple_dense);
   475         MAS_BUG_ON(mas, p_type == maple_leaf_64);
   476
   477         switch (p_type) {
   478         case maple_range_64:
   479         case maple_arange_64:
   480                 shift = MAPLE_PARENT_SLOT_SHIFT;
   481                 type = MAPLE_PARENT_RANGE64;
   482                 break;
   483         default:
   484         case maple_dense:
   485         case maple_leaf_64:
   486                 shift = type = 0;
   487                 break;
   488         }
   489
   490         val &= ~MAPLE_NODE_MASK; /* Clear all node metadata in parent */
→ 491         val |= (slot << shift) | type;
   492         mte_to_node(enode)->parent = ma_parent_ptr(val);
   493 }

lib/maple_tree.c:1701
---------------------
   1682 /*
   1683  * mas_adopt_children() - Set the parent pointer of all nodes in @parent to
   1684  * @parent with the slot encoded.
   1685  * @mas - the maple state (for the tree)
   1686  * @parent - the maple encoded node containing the children.
   1687  */
   1688 static inline void mas_adopt_children(struct ma_state *mas,
   1689                 struct maple_enode *parent)
   1690 {
   1691         enum maple_type type = mte_node_type(parent);
   1692         struct maple_node *node = mte_to_node(parent);
   1693         void __rcu **slots = ma_slots(node, type);
   1694         unsigned long *pivots = ma_pivots(node, type);
   1695         struct maple_enode *child;
   1696         unsigned char offset;
   1697
   1698         offset = ma_data_end(node, type, pivots, mas->max);
   1699         do {
   1700                 child = mas_slot_locked(mas, slots, offset);
→ 1701                 mas_set_parent(mas, child, parent, offset);
   1702         } while (offset--);
   1703 }

   2562 static inline void mas_topiary_replace(struct ma_state *mas,
   2563                 struct maple_enode *old_enode)
   2564 {
   2565         struct ma_state tmp[3], tmp_next[3];
   2566         MA_TOPIARY(subtrees, mas->tree);
   2567         bool in_rcu;
   2568         int i, n;
   2569
   2570         /* Place data in tree & then mark node as old */
   2571         mas_put_in_tree(mas, old_enode);
   2572
   2573         /* Update the parent pointers in the tree */
   2574         tmp[0] = *mas;
   2575         tmp[0].offset = 0;
   2576         tmp[1].node = MAS_NONE;
   2577         tmp[2].node = MAS_NONE;
   2578         while (!mte_is_leaf(tmp[0].node)) {
   2579                 n = 0;
   2580                 for (i = 0; i < 3; i++) {
   2581                         if (mas_is_none(&tmp[i]))
   2582                                 continue;
   2583
   2584                         while (n < 3) {
   2585                                 if (!mas_find_child(&tmp[i], &tmp_next[n]))
   2586                                         break;
   2587                                 n++;
   2588                         }
   2589
→ 2590                        mas_adopt_children(&tmp[i], tmp[i].node);
   2591                 }
   2592
   2593                 if (MAS_WARN_ON(mas, n == 0))
   2594                         break;
   2595
   2596                 while (n < 3)
   2597                         tmp_next[n++].node = MAS_NONE;
   2598
   2599                 for (i = 0; i < 3; i++)
   2600                         tmp[i] = tmp_next[i];
   2601         }
   2602
   2603         /* Collect the old nodes that need to be discarded */
   2604         if (mte_is_leaf(old_enode))
   2605                 return mas_free(mas, old_enode);
   2606
   2607         tmp[0] = *mas;
   2608         tmp[0].offset = 0;
   2609         tmp[0].node = old_enode;
   2610         tmp[1].node = MAS_NONE;
   2611         tmp[2].node = MAS_NONE;
   2612         in_rcu = mt_in_rcu(mas->tree);
   2613         do {
   2614                 n = 0;
   2615                 for (i = 0; i < 3; i++) {
   2616                         if (mas_is_none(&tmp[i]))
   2617                                 continue;

The read side:

    527 /*
    528  * ma_dead_node() - check if the @enode is dead.
    529  * @enode: The encoded maple node
    530  *
    531  * Return: true if dead, false otherwise.
    532  */
    533 static inline bool ma_dead_node(const struct maple_node *node)
    534 {
    535         struct maple_node *parent;
    536
    537         /* Do not reorder reads from the node prior to the parent check */
    538         smp_rmb();
→  539         parent = (void *)((unsigned long) node->parent & ~MAPLE_NODE_MASK);
    540         return (parent == node);
    541 }

   2767 static inline void *mtree_range_walk(struct ma_state *mas)
   2768 {
   2769         unsigned long *pivots;
   2770         unsigned char offset;
   2771         struct maple_node *node;
   2772         struct maple_enode *next, *last;
   2773         enum maple_type type;
   2774         void __rcu **slots;
   2775         unsigned char end;
   2776         unsigned long max, min;
   2777         unsigned long prev_max, prev_min;
   2778
   2779         next = mas->node;
   2780         min = mas->min;
   2781         max = mas->max;
   2782         do {
   2783                 offset = 0;
   2784                 last = next;
   2785                 node = mte_to_node(next);
   2786                 type = mte_node_type(next);
   2787                 pivots = ma_pivots(node, type);
   2788                 end = ma_data_end(node, type, pivots, max);
→ 2789                 if (unlikely(ma_dead_node(node)))
   2790                         goto dead_node;
   2791
   2792                 if (pivots[offset] >= mas->index) {
   2793                         prev_max = max;
   2794                         prev_min = min;
   2795                         max = pivots[offset];
   2796                         goto next;
   2797                 }
   2798
   2799                 do {
   2800                         offset++;
   2801                 } while ((offset < end) && (pivots[offset] < mas->index));

As it is evident, ma_dead_node() expands to:

    527 /*
    528  * ma_dead_node() - check if the @enode is dead.
    529  * @enode: The encoded maple node
    530  *
    531  * Return: true if dead, false otherwise.
    532  */
    533 static inline bool ma_dead_node(const struct maple_node *node)
    534 {
    535         struct maple_node *parent;
    536
    537         /* Do not reorder reads from the node prior to the parent check */
    538         smp_rmb();
→  539         parent = (void *)((unsigned long) node->parent & ~MAPLE_NODE_MASK);
    540         return (parent == node);
    541 }

as above, but the smb_rmb() protection is here, so the KCSAN warning should be double-checked for
validity.

But I do not really understand maple trees to their depth, I am only reporting the symptomatic
outlook of the reported data-race.

This is all-in-all a very interested subject, and I wish there was a way to just slurp all those
interesting kernel intrinsics into the brain, but it just ain't that easy. Forgive me for being
open ...

Best regards,
Mirsad Todorovac