[PATCH v3 0/2] maple_tree: fix maple_range_64 crashes in RCU mode

[PATCH v3 0/2] maple_tree: fix maple_range_64 crashes in RCU mode

[Dimitris Charisis]

The patch series fixes two RCU destroy path issues on maple_range_64
nodes. Both arising from the fact that a maple_range_64 node repurposes
the last slot to hold metadata when the node is not full. Patch 1
addresses the issues, and patch 2 adds a test used to catch them.

Currently there is no in-tree user of maple_range_64 nodes in RCU mode.
All in-tree users of MT_FLAGS_USE_RCU also set MT_FLAGS_ALLOC_RANGE
which makes the internal nodes maple_arange_64.

Below is the minimal reproducer used during debugging:

static DEFINE_MTREE(tree);
static int __init maple_fix_init(void)
{
        unsigned long i, j;

        for (i = 10; i < 4000; i++) {
                mt_init_flags(&tree, MT_FLAGS_USE_RCU);

                for (j = 0; j < i; j++) {
                        mtree_insert_range(&tree, j * 10, j * 10 + 9,
                                        xa_mk_value(j), GFP_KERNEL);
                }

                mtree_destroy(&tree);
                rcu_barrier();
        }
        return 0;
}

The splat for the first issue addressed by the first patch is shown
below. mt_clear_meta() runs after the slots have been rewritten with raw
pointers by mte_dead_leaves(), so it cannot recognize a valid last
pointer because the type information is stripped. On my 64-bit LE
machine, it clears bytes 248 and 249 of the maple_range_64 which are the
two least significant bytes of the last pointer. The lowest byte is
already zero, since nodes are 256-byte aligned, but zeroing byte 249
corrupts the pointer.

KASAN catches it as a double-free, because that corrupted pointer
happens to land on a node that was freed previously. The splat appears
at 226 insertions in the reproducer. This is when the tree has a full
root node on a 64-bit build.

  ==================================================================
  BUG: KASAN: double-free in mt_free_walk+0x138/0x3a0
  Free of addr ffff0000f3d40000 by task swapper/2/0
  [...]
  Call trace:
   [...]
   kmem_cache_free_bulk+0x5b8/0xc18
   mt_free_walk+0x138/0x3a0
   rcu_core+0x5d0/0x1638
   rcu_core_si+0x18/0x30
   [...]

  Allocated by task 1218:
   [...]
   kmem_cache_alloc_from_sheaf_noprof+0xa8/0x2f0
   dst_setup+0x210/0x630
   mas_wr_split+0x568/0x26e0
   mas_wr_store_entry+0x98c/0x1de0
   mas_insert.isra.0+0x3d0/0x5d8
   mtree_insert_range+0xec/0x1c8
   maple_fix_init+0x94/0xff8 [maple_fix_obj]
   [...]

  Freed by task 0:
   [...]
   __kasan_slab_free+0x88/0xb8
   __rcu_free_sheaf_prepare+0x94/0x360
   rcu_free_sheaf+0x30/0x138
   rcu_core+0x5d0/0x1638
   rcu_core_si+0x18/0x30
   [...]

  The buggy address belongs to the object at ffff0000f3d40000
   which belongs to the cache maple_node of size 256
  The buggy address is located 0 bytes inside of
   256-byte region [ffff0000f3d40000, ffff0000f3d40100)

  [...]
  Memory state around the buggy address:
   ffff0000f3d3ff00: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
   ffff0000f3d3ff80: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
  >ffff0000f3d40000: fa fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb
                     ^
   ffff0000f3d40080: fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb
   ffff0000f3d40100: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
  ==================================================================

The second issue fixed in the first patch is in the mt_free_walk().
mt_free_walk() descends by checking if the corresponding slot[offset]
entry is non-zero. In a maple_range_64 node that has
MAPLE_RANGE64_SLOTS-1 valid pointers to child nodes, all slots will be
non-zero, since the last slot holds the metadata. Thus, mte_dead_walk()
dereferences the metadata as if it were a node and hits the
null-ptr-deref as shown in the splat below.

After fixing the first issue, the reproducer reaches this case at 3166
insertions. The affected node is the root on a tree with height 3 and it
has 15 valid child nodes on a 64-bit machine. The first fix does not
introduce this bug, but it exposes it for the root node because it no
longer clears the root metadata. On an unmodified kernel, the same bug
exists and is reachable when such a maple_range_64 node appears below
the root, where mt_clear_meta() is not called.

Second KASAN splat:

  Unable to handle kernel paging request at virtual address dfff800000000006
  KASAN: null-ptr-deref in range [0x0000000000000030-0x0000000000000037]
  [...]
  Call trace:
   mte_dead_walk+0x78/0x140 (P)
   mt_free_walk+0x1f8/0x3a0
   rcu_core+0x5d0/0x1638
   rcu_core_si+0x18/0x30
   [..]

Both splats are from an arm64 QEMU guest. The test_maple_tree and the
userspace suite pass after each patch in the series.

---
Note for reviewers:

* Before commit 790e1fa86b34 ("maple_tree: add RCU lock checking to rcu
  callback functions") mas_clear_meta() was called while descending the
  tree, so metadata was cleared on every node. That commit removed the
  call from the descend path leaving only the final call for the root
  node, and renamed it to mt_clear_meta().

  An alternative fix would be to restore metadata clearing for every
  node and fix mt_clear_meta() for full maple_range_64 nodes. I
  preferred removing the clearing and use slot_len to identify the valid
  slots directly.

Signed-off-by: Dimitris Charisis <dchar@cslab.ece.ntua.gr>

---
Changes in v3:
- Combine both fixes into one patch, as suggested by Liam, to avoid
  leaving an intermediate commit where removing mt_clear_meta() exposes
  the second bug at the root node.
- Combine both regression tests into the next patch.
- Link to v2: https://lore.kernel.org/r/20260916-fix-maple-tree-range64-rcu-v2-0-0b09de37eb69@cslab.ece.ntua.gr

Changes in v2:
- Add one test after each fix.
- Reword the cover letter.
- Link to v1: https://lore.kernel.org/r/20260913-fix-maple-tree-range64-rcu-v1-0-31a130bb8cbf@cslab.ece.ntua.gr

---
Dimitris Charisis (2):
      maple_tree: fix maple_range_64 crashes in RCU mode
      test_maple_tree: test maple_range_64 node in RCU mode

 lib/maple_tree.c      | 43 +------------------------------------------
 lib/test_maple_tree.c | 32 ++++++++++++++++++++++++++++++++
 2 files changed, 33 insertions(+), 42 deletions(-)
---
base-commit: e2e54005e20fb42d4a5e140d70a65be4a2363045
change-id: 20260912-fix-maple-tree-range64-rcu-02fa3d2e59a7

Best regards,
-- 
Dimitris Charisis <dchar@cslab.ece.ntua.gr>

[PATCH v3 1/2] maple_tree: fix maple_range_64 crashes in RCU mode

[Dimitris Charisis]

This commit fixes two issues in maple_range_64 nodes under RCU mode. A
maple_range_64 node repurposes its last slot to hold metadata whenever
the node is not full. Both issues arise from mishandling that last slot.

More specifically the two fixes are:

1. Remove mt_clear_meta() function. mt_clear_meta() decides whether the
   last slot of a maple_range_64 node holds a child pointer or a
   struct maple_metadata with the check

        if (unlikely((mte_to_node(next) &&
                      mte_node_type(next))))
                return; /* no metadata, could be node */

   The check expects the pointer to be encoded.  But the only callsite
   of mt_clear_meta() is mt_destroy_walk() on the RCU destroy path, and
   by the time it runs, mte_dead_leaves() has overwritten every slot on
   a full node with a raw pointer, stripping the type information. Thus,
   the check above never returns early for a full node as it should. It
   falls through and then:
           meta->gap = 0;
           meta->end = 0;
   zeroes two bytes of a valid child pointer. Later, mt_free_walk()
   dereferences the corrupted pointer.

  Fix this by removing mt_clear_meta() along with its only callsite.
  mt_clear_meta() is only called for the root of each sub-tree destroyed
  under RCU. Descendant nodes retain their metadata until they are
  freed. RCU readers may use the metadata while traversing a node, but
  do not use cleared metadata to detect that a node has been removed.
  They detect a dead node via ma_dead_node().

2. Fix invalid memory access in mt_free_walk().  mt_free_walk() descends
   to the left-most unvisited "parent-of-a-leaf" node by checking the
   condition:

        if ((offset < mt_slots[type]) &&
            rcu_dereference_protected(slots[offset],
                                      lock_is_held(&rcu_callback_map)))
                slots = mte_dead_walk(&enode, offset);

   On a maple_range_64 node with MAPLE_RANGE64_SLOTS-1 children *all*
   slots are non-NULL. The first MAPLE_RANGE64_SLOTS-1  hold valid
   pointers to child nodes, and the last slot contains metadata. The
   above check therefore passes for all offsets, and mte_dead_walk()
   dereferences the metadata as if it were a node.

   To trigger this, a node at least two levels above the leaves has to
   have exactly MAPLE_RANGE64_SLOTS-1 valid pointers to other nodes.
   maple_arange_64 nodes cannot hit this since they store the metadata
   in a separate field.

   Fix this by bounding the descent with slot_len which holds the number
   of children of a dead node.

Fixes: 54a611b60590 ("Maple Tree: add new data structure")
Fixes: 2e5b4921f8ef ("maple_tree: fix freeing of nodes in rcu mode")
Signed-off-by: Dimitris Charisis <dchar@cslab.ece.ntua.gr>
---
 lib/maple_tree.c | 43 +------------------------------------------
 1 file changed, 1 insertion(+), 42 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 1aba6cced71307245cbbca26986e14e74b35a14f..0b0036c9f848929a7c9a26650ccd935c44aa1376 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -763,43 +763,6 @@ static inline void ma_set_meta(struct maple_node *mn, enum maple_type mt,
 	meta->end = end;
 }
 
-/*
- * mt_clear_meta() - clear the metadata information of a node, if it exists
- * @mt: The maple tree
- * @mn: The maple node
- * @type: The maple node type
- */
-static inline void mt_clear_meta(struct maple_tree *mt, struct maple_node *mn,
-				  enum maple_type type)
-{
-	struct maple_metadata *meta;
-	unsigned long *pivots;
-	void __rcu **slots;
-	void *next;
-
-	switch (type) {
-	case maple_range_64:
-		pivots = mn->mr64.pivot;
-		if (unlikely(pivots[MAPLE_RANGE64_SLOTS - 2])) {
-			slots = mn->mr64.slot;
-			next = mt_slot_locked(mt, slots,
-					      MAPLE_RANGE64_SLOTS - 1);
-			if (unlikely((mte_to_node(next) &&
-				      mte_node_type(next))))
-				return; /* no metadata, could be node */
-		}
-		fallthrough;
-	case maple_arange_64:
-		meta = ma_meta(mn, type);
-		break;
-	default:
-		return;
-	}
-
-	meta->gap = 0;
-	meta->end = 0;
-}
-
 /*
  * ma_meta_end() - Get the data end of a node from the metadata
  * @mn: The maple node
@@ -4789,9 +4752,7 @@ static void mt_free_walk(struct rcu_head *head)
 
 		type = mte_node_type(enode);
 		slots = ma_slots(mte_to_node(enode), type);
-		if ((offset < mt_slots[type]) &&
-		    rcu_dereference_protected(slots[offset],
-					      lock_is_held(&rcu_callback_map)))
+		if (offset < mte_to_node(enode)->slot_len)
 			slots = mte_dead_walk(&enode, offset);
 		node = mte_to_node(enode);
 	} while ((node != start) || (node->slot_len < offset));
@@ -4885,8 +4846,6 @@ static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt,
 free_leaf:
 	if (free)
 		kfree(node);
-	else
-		mt_clear_meta(mt, node, node->type);
 }
 
 /*

-- 
2.47.3

[PATCH v3 2/2] test_maple_tree: test maple_range_64 node in RCU mode

[Dimitris Charisis]

This commit adds a test that builds two maple_range_64 trees in RCU
mode.  The first tree has a root that is a full maple_range_64 node and
ensures that the destruction under RCU does not misinterpret the last
slot as metadata. 226 insertions produce such a root on a 64-bit build.

The second tree is a height 3 tree whose root holds 15 child pointers
and metadata in its last slot, so every slot is non-zero and ensures
that the destruction under RCU does not descend into the metadata slot.
3166 insertions produce such a tree on a 64-bit build.

Signed-off-by: Dimitris Charisis <dchar@cslab.ece.ntua.gr>
---
 lib/test_maple_tree.c | 32 ++++++++++++++++++++++++++++++++
 1 file changed, 32 insertions(+)

diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
index b9367c61e8b50d107ab972fc5222fb6a531fad87..fb40e193a3cb76f0eb02af3aa4a38630692a4a9b 100644
--- a/lib/test_maple_tree.c
+++ b/lib/test_maple_tree.c
@@ -3710,6 +3710,36 @@ static noinline void __init alloc_cyclic_testing(struct maple_tree *mt)
 	MT_BUG_ON(mt, ret != 1);
 }
 
+static noinline void __init check_range64_in_rcu(struct maple_tree *mt)
+{
+	unsigned long i;
+	unsigned long nr_entries = 226; /* Build a full maple_range_64 root node */
+
+	MT_BUG_ON(mt, !mtree_empty(mt));
+	mt_init_flags(mt, MT_FLAGS_USE_RCU);
+
+	for (i = 0; i < nr_entries; i++) {
+		MT_BUG_ON(mt, mtree_test_insert_range(mt, i*10, i*10 + 9,
+						      xa_mk_value(i)));
+	}
+
+	mtree_destroy(mt);
+	rcu_barrier();
+
+	nr_entries = 3166; /* Height 3. Root has 15 children + metadata */
+
+	MT_BUG_ON(mt, !mtree_empty(mt));
+	mt_init_flags(mt, MT_FLAGS_USE_RCU);
+
+	for (i = 0; i < nr_entries; i++) {
+		MT_BUG_ON(mt, mtree_test_insert_range(mt, i*10, i*10 + 9,
+						      xa_mk_value(i)));
+	}
+
+	mtree_destroy(mt);
+	rcu_barrier();
+}
+
 static DEFINE_MTREE(tree);
 static int __init maple_tree_seed(void)
 {
@@ -3999,6 +4029,8 @@ static int __init maple_tree_seed(void)
 	alloc_cyclic_testing(&tree);
 	mtree_destroy(&tree);
 
+	check_range64_in_rcu(&tree);
+
 
 #if defined(BENCH)
 skip:

-- 
2.47.3

Re: [PATCH v3 0/2] maple_tree: fix maple_range_64 crashes in RCU mode

[Liam R. Howlett]

On 26/10/05 12:47PM, Dimitris Charisis wrote:
> The patch series fixes two RCU destroy path issues on maple_range_64
> nodes. Both arising from the fact that a maple_range_64 node repurposes
> the last slot to hold metadata when the node is not full. Patch 1
> addresses the issues, and patch 2 adds a test used to catch them.
> 
> Currently there is no in-tree user of maple_range_64 nodes in RCU mode.
> All in-tree users of MT_FLAGS_USE_RCU also set MT_FLAGS_ALLOC_RANGE
> which makes the internal nodes maple_arange_64.

Thanks.  This looks good despite the massive change log.

Reviewed-by: Liam R. Howlett (Google) <liam@infradead.org>

> 
> Below is the minimal reproducer used during debugging:
> 
> static DEFINE_MTREE(tree);
> static int __init maple_fix_init(void)
> {
>         unsigned long i, j;
> 
>         for (i = 10; i < 4000; i++) {
>                 mt_init_flags(&tree, MT_FLAGS_USE_RCU);
> 
>                 for (j = 0; j < i; j++) {
>                         mtree_insert_range(&tree, j * 10, j * 10 + 9,
>                                         xa_mk_value(j), GFP_KERNEL);
>                 }
> 
>                 mtree_destroy(&tree);
>                 rcu_barrier();
>         }
>         return 0;
> }
> 
> The splat for the first issue addressed by the first patch is shown
> below. mt_clear_meta() runs after the slots have been rewritten with raw
> pointers by mte_dead_leaves(), so it cannot recognize a valid last
> pointer because the type information is stripped. On my 64-bit LE
> machine, it clears bytes 248 and 249 of the maple_range_64 which are the
> two least significant bytes of the last pointer. The lowest byte is
> already zero, since nodes are 256-byte aligned, but zeroing byte 249
> corrupts the pointer.
> 
> KASAN catches it as a double-free, because that corrupted pointer
> happens to land on a node that was freed previously. The splat appears
> at 226 insertions in the reproducer. This is when the tree has a full
> root node on a 64-bit build.
> 
>   ==================================================================
>   BUG: KASAN: double-free in mt_free_walk+0x138/0x3a0
>   Free of addr ffff0000f3d40000 by task swapper/2/0
>   [...]
>   Call trace:
>    [...]
>    kmem_cache_free_bulk+0x5b8/0xc18
>    mt_free_walk+0x138/0x3a0
>    rcu_core+0x5d0/0x1638
>    rcu_core_si+0x18/0x30
>    [...]
> 
>   Allocated by task 1218:
>    [...]
>    kmem_cache_alloc_from_sheaf_noprof+0xa8/0x2f0
>    dst_setup+0x210/0x630
>    mas_wr_split+0x568/0x26e0
>    mas_wr_store_entry+0x98c/0x1de0
>    mas_insert.isra.0+0x3d0/0x5d8
>    mtree_insert_range+0xec/0x1c8
>    maple_fix_init+0x94/0xff8 [maple_fix_obj]
>    [...]
> 
>   Freed by task 0:
>    [...]
>    __kasan_slab_free+0x88/0xb8
>    __rcu_free_sheaf_prepare+0x94/0x360
>    rcu_free_sheaf+0x30/0x138
>    rcu_core+0x5d0/0x1638
>    rcu_core_si+0x18/0x30
>    [...]
> 
>   The buggy address belongs to the object at ffff0000f3d40000
>    which belongs to the cache maple_node of size 256
>   The buggy address is located 0 bytes inside of
>    256-byte region [ffff0000f3d40000, ffff0000f3d40100)
> 
>   [...]
>   Memory state around the buggy address:
>    ffff0000f3d3ff00: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
>    ffff0000f3d3ff80: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
>   >ffff0000f3d40000: fa fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb
>                      ^
>    ffff0000f3d40080: fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb
>    ffff0000f3d40100: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
>   ==================================================================
> 
> The second issue fixed in the first patch is in the mt_free_walk().
> mt_free_walk() descends by checking if the corresponding slot[offset]
> entry is non-zero. In a maple_range_64 node that has
> MAPLE_RANGE64_SLOTS-1 valid pointers to child nodes, all slots will be
> non-zero, since the last slot holds the metadata. Thus, mte_dead_walk()
> dereferences the metadata as if it were a node and hits the
> null-ptr-deref as shown in the splat below.
> 
> After fixing the first issue, the reproducer reaches this case at 3166
> insertions. The affected node is the root on a tree with height 3 and it
> has 15 valid child nodes on a 64-bit machine. The first fix does not
> introduce this bug, but it exposes it for the root node because it no
> longer clears the root metadata. On an unmodified kernel, the same bug
> exists and is reachable when such a maple_range_64 node appears below
> the root, where mt_clear_meta() is not called.
> 
> Second KASAN splat:
> 
>   Unable to handle kernel paging request at virtual address dfff800000000006
>   KASAN: null-ptr-deref in range [0x0000000000000030-0x0000000000000037]
>   [...]
>   Call trace:
>    mte_dead_walk+0x78/0x140 (P)
>    mt_free_walk+0x1f8/0x3a0
>    rcu_core+0x5d0/0x1638
>    rcu_core_si+0x18/0x30
>    [..]
> 
> Both splats are from an arm64 QEMU guest. The test_maple_tree and the
> userspace suite pass after each patch in the series.
> 
> ---
> Note for reviewers:
> 
> * Before commit 790e1fa86b34 ("maple_tree: add RCU lock checking to rcu
>   callback functions") mas_clear_meta() was called while descending the
>   tree, so metadata was cleared on every node. That commit removed the
>   call from the descend path leaving only the final call for the root
>   node, and renamed it to mt_clear_meta().
> 
>   An alternative fix would be to restore metadata clearing for every
>   node and fix mt_clear_meta() for full maple_range_64 nodes. I
>   preferred removing the clearing and use slot_len to identify the valid
>   slots directly.
> 
> Signed-off-by: Dimitris Charisis <dchar@cslab.ece.ntua.gr>
> 
> ---
> Changes in v3:
> - Combine both fixes into one patch, as suggested by Liam, to avoid
>   leaving an intermediate commit where removing mt_clear_meta() exposes
>   the second bug at the root node.
> - Combine both regression tests into the next patch.
> - Link to v2: https://lore.kernel.org/r/20260916-fix-maple-tree-range64-rcu-v2-0-0b09de37eb69@cslab.ece.ntua.gr
> 
> Changes in v2:
> - Add one test after each fix.
> - Reword the cover letter.
> - Link to v1: https://lore.kernel.org/r/20260913-fix-maple-tree-range64-rcu-v1-0-31a130bb8cbf@cslab.ece.ntua.gr
> 
> ---
> Dimitris Charisis (2):
>       maple_tree: fix maple_range_64 crashes in RCU mode
>       test_maple_tree: test maple_range_64 node in RCU mode
> 
>  lib/maple_tree.c      | 43 +------------------------------------------
>  lib/test_maple_tree.c | 32 ++++++++++++++++++++++++++++++++
>  2 files changed, 33 insertions(+), 42 deletions(-)
> ---
> base-commit: e2e54005e20fb42d4a5e140d70a65be4a2363045
> change-id: 20260912-fix-maple-tree-range64-rcu-02fa3d2e59a7
> 
> Best regards,
> -- 
> Dimitris Charisis <dchar@cslab.ece.ntua.gr>
> 

Re: [PATCH v3 1/2] maple_tree: fix maple_range_64 crashes in RCU mode

[Florian Schmaus]

On Mon, 05 Oct 2026 12:47:27 +0000, Dimitris Charisis <dchar@cslab.ece.ntua.gr> wrote:
> This commit fixes two issues in maple_range_64 nodes under RCU mode. A
> maple_range_64 node repurposes its last slot to hold metadata whenever
> the node is not full. Both issues arise from mishandling that last slot.
> 
> More specifically the two fixes are:
> 
> 1. Remove mt_clear_meta() function. mt_clear_meta() decides whether the
>    last slot of a maple_range_64 node holds a child pointer or a
>    struct maple_metadata with the check
> 
> [...]

Reviewed-by: Florian Schmaus <florian.schmaus@codasip.com>

-- 
Florian Schmaus <florian.schmaus@codasip.com>

Re: [PATCH v3 2/2] test_maple_tree: test maple_range_64 node in RCU mode

[Florian Schmaus]

> This commit adds a test that builds two maple_range_64 trees in RCU
> mode.  The first tree has a root that is a full maple_range_64 node and
> ensures that the destruction under RCU does not misinterpret the last
> slot as metadata. 226 insertions produce such a root on a 64-bit build.
> 
> The second tree is a height 3 tree whose root holds 15 child pointers
> and metadata in its last slot, so every slot is non-zero and ensures
> that the destruction under RCU does not descend into the metadata slot.
> 3166 insertions produce such a tree on a 64-bit build.
> 
> Signed-off-by: Dimitris Charisis <dchar@cslab.ece.ntua.gr>
>
> diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
> index b9367c61e8b5..fb40e193a3cb 100644
> --- a/lib/test_maple_tree.c
> +++ b/lib/test_maple_tree.c
> @@ -3710,6 +3710,36 @@ static noinline void __init alloc_cyclic_testing(struct maple_tree *mt)
>  	MT_BUG_ON(mt, ret != 1);
>  }
>  
> +static noinline void __init check_range64_in_rcu(struct maple_tree *mt)
> +{
> +	unsigned long i;
> +	unsigned long nr_entries = 226; /* Build a full maple_range_64 root node */
> +
> +	MT_BUG_ON(mt, !mtree_empty(mt));
> +	mt_init_flags(mt, MT_FLAGS_USE_RCU);
> +
> +	for (i = 0; i < nr_entries; i++) {
> +		MT_BUG_ON(mt, mtree_test_insert_range(mt, i*10, i*10 + 9,
> +						      xa_mk_value(i)));
> +	}
> +
> +	mtree_destroy(mt);
> +	rcu_barrier();
> +
> +	nr_entries = 3166; /* Height 3. Root has 15 children + metadata */
> +
> +	MT_BUG_ON(mt, !mtree_empty(mt));
> +	mt_init_flags(mt, MT_FLAGS_USE_RCU);
> +
> +	for (i = 0; i < nr_entries; i++) {
> +		MT_BUG_ON(mt, mtree_test_insert_range(mt, i*10, i*10 + 9,
> +						      xa_mk_value(i)));
> +	}
> +
> +	mtree_destroy(mt);
> +	rcu_barrier();

This case passes on an unfixed kernel.

The bug that exists today requires a non-root node with 15 children and a
tree of height 4. The size-2768 test case in my series covers that. You can
find my test at

https://lore.kernel.org/all/20261015-maple-tree-fix-slab-corruption-v1-3-160d97f7304c@codasip.com/

and may fold it into your check_range64_in_rcu(). It fails without your (or
my) fix and succeed with.

-- 
Florian Schmaus <florian.schmaus@codasip.com>

Re: [PATCH v3 2/2] test_maple_tree: test maple_range_64 node in RCU mode

[Dimitris Charisis]

On 10/23/26 17:14, Florian Schmaus wrote:
>> This commit adds a test that builds two maple_range_64 trees in RCU
>> mode.  The first tree has a root that is a full maple_range_64 node and
>> ensures that the destruction under RCU does not misinterpret the last
>> slot as metadata. 226 insertions produce such a root on a 64-bit build.
>>
>> The second tree is a height 3 tree whose root holds 15 child pointers
>> and metadata in its last slot, so every slot is non-zero and ensures
>> that the destruction under RCU does not descend into the metadata slot.
>> 3166 insertions produce such a tree on a 64-bit build.
>>
>> Signed-off-by: Dimitris Charisis <dchar@cslab.ece.ntua.gr>
>>
>> diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
>> index b9367c61e8b5..fb40e193a3cb 100644
>> --- a/lib/test_maple_tree.c
>> +++ b/lib/test_maple_tree.c
>> @@ -3710,6 +3710,36 @@ static noinline void __init alloc_cyclic_testing(struct maple_tree *mt)
>>   	MT_BUG_ON(mt, ret != 1);
>>   }
>>   
>> +static noinline void __init check_range64_in_rcu(struct maple_tree *mt)
>> +{
>> +	unsigned long i;
>> +	unsigned long nr_entries = 226; /* Build a full maple_range_64 root node */
>> +
>> +	MT_BUG_ON(mt, !mtree_empty(mt));
>> +	mt_init_flags(mt, MT_FLAGS_USE_RCU);
>> +
>> +	for (i = 0; i < nr_entries; i++) {
>> +		MT_BUG_ON(mt, mtree_test_insert_range(mt, i*10, i*10 + 9,
>> +						      xa_mk_value(i)));
>> +	}
>> +
>> +	mtree_destroy(mt);
>> +	rcu_barrier();
>> +
>> +	nr_entries = 3166; /* Height 3. Root has 15 children + metadata */
>> +
>> +	MT_BUG_ON(mt, !mtree_empty(mt));
>> +	mt_init_flags(mt, MT_FLAGS_USE_RCU);
>> +
>> +	for (i = 0; i < nr_entries; i++) {
>> +		MT_BUG_ON(mt, mtree_test_insert_range(mt, i*10, i*10 + 9,
>> +						      xa_mk_value(i)));
>> +	}
>> +
>> +	mtree_destroy(mt);
>> +	rcu_barrier();
> This case passes on an unfixed kernel.
>
> The bug that exists today requires a non-root node with 15 children and a
> tree of height 4. The size-2768 test case in my series covers that. You can
> find my test at
>
> https://lore.kernel.org/all/20261015-maple-tree-fix-slab-corruption-v1-3-160d97f7304c@codasip.com/
>
> and may fold it into your check_range64_in_rcu(). It fails without your (or
> my) fix and succeed with.
Hi Florian!

KASAN catches the invalid pointer access in the first tested tree on
an unmodified kernel. The second test guards against the cause of the
second bug: a node (at least) two levels above the leaves with exactly
15 valid child pointers.

That being said, I do think that covering the case where this is an
intermediate node has its own value. After all, more testing is never
bad :-).  Feel free to send / extend the test. Since it exercises the
same underlying issue, extending check_range64_in_rcu() seems like
the right place to me.

Dimitris