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

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

[Dimitris Charisis]

I was running a patched kernel using a maple tree in RCU mode without
specifying the MT_FLAGS_ALLOC_RANGE flag and the kernel crashed. I
switched to an upstream kernel, and after some investigation and
debugging (thanks tools/testing/radix-tree/maple.c) I discovered that
there were two separate issues on the RCU destroy path that were
responsible. Both arising from the fact that a maple_range_64 node that
is not full repurposes its last slot to hold metadata. Each issue is
addressed by one of the two patches.

AFAIK there is no in-tree user of maple_range_64 nodes in RCU mode at
the moment. All in-tree users of MT_FLAGS_USE_RCU that I found also set
MT_FLAGS_ALLOC_RANGE which makes the internal nodes maple_arange_64.

Below is the minimal reproducer I 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;
}

Patch 1 fixes the first issue. The splat 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 usually
appears at around 226 insertions in the reproducer. The exact tree size
that triggers it may vary because it depends on where the corrupted
pointer lands.

  ==================================================================
  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
  ==================================================================

Patch 2 fixes the second issue. 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 applying patch 1, 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.

Patch 1 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
before patch 1, 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>

---
Dimitris Charisis (2):
      maple_tree: remove mt_clear_meta() to fix a pointer corruption
      maple_tree: fix invalid memory access in mt_free_walk()

 lib/maple_tree.c | 43 +------------------------------------------
 1 file changed, 1 insertion(+), 42 deletions(-)
---
base-commit: e2e54005e20fb42d4a5e140d70a65be4a2363045
change-id: 20260912-fix-maple-tree-range64-rcu-02fa3d2e59a7

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

[PATCH 1/2] maple_tree: remove mt_clear_meta() to fix a pointer corruption

[Dimitris Charisis]

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().

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 | 39 ---------------------------------------
 1 file changed, 39 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 1aba6cced71307245cbbca26986e14e74b35a14f..e86eee43aa0ada6963995cd74495d9344f6ccd06 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
@@ -4885,8 +4848,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 2/2] maple_tree: fix invalid memory access in mt_free_walk()

[Dimitris Charisis]

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);

A maple_range_64 node has MAPLE_RANGE64_SLOTS slots. When it's not full,
the last slot carries a struct maple_metadata holding the offset of the
last valid slot. So on a 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")
Signed-off-by: Dimitris Charisis <dchar@cslab.ece.ntua.gr>
---
 lib/maple_tree.c | 4 +---
 1 file changed, 1 insertion(+), 3 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index e86eee43aa0ada6963995cd74495d9344f6ccd06..0b0036c9f848929a7c9a26650ccd935c44aa1376 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4752,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));

-- 
2.47.3

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

[Liam R. Howlett]

On 26/09/13 03:26PM, Dimitris Charisis wrote:
> I was running a patched kernel using a maple tree in RCU mode without
> specifying the MT_FLAGS_ALLOC_RANGE flag and the kernel crashed. I
> switched to an upstream kernel, and after some investigation and
> debugging (thanks tools/testing/radix-tree/maple.c) I discovered that
> there were two separate issues on the RCU destroy path that were
> responsible. Both arising from the fact that a maple_range_64 node that
> is not full repurposes its last slot to hold metadata. Each issue is
> addressed by one of the two patches.
> 
> AFAIK there is no in-tree user of maple_range_64 nodes in RCU mode at
> the moment. All in-tree users of MT_FLAGS_USE_RCU that I found also set
> MT_FLAGS_ALLOC_RANGE which makes the internal nodes maple_arange_64.

Hello!

Thank you for your investigation and patches.  I will have a closer look
soon, but for now I have a request for this series.

> 
> Below is the minimal reproducer I 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;
> }

Awesome!  What I ask people to do is to create a patch for the
tools/testing/radix-tree/maple.c with the reproducer in its own patch
that gets added after the fix.  This way we never re-introduce new
features and the testing keeps passing for every bisection.

If you have one of these for each bug, then please add them after the
fix.  I understand rcu is tricky to test when a race is involved, but I
do have testing for many threads (which you probably saw).

The testing is less organized than I'd like and since this is RCU
specific, you may need to use the testing file and not the module
testing in lib/test_maple_tree.c.  If possible, I add the testing to the
module, but if internal poking or threads need to be used, we put them
in the userspace testing.

> 
> Patch 1 fixes the first issue. The splat 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 usually
> appears at around 226 insertions in the reproducer. The exact tree size
> that triggers it may vary because it depends on where the corrupted
> pointer lands.
> 
>   ==================================================================
>   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
>   ==================================================================
> 
> Patch 2 fixes the second issue. 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 applying patch 1, 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.
> 
> Patch 1 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
> before patch 1, 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.

Ah.  I'll have to look closer at this.  The metadata had caused issues
on BE machines in the past which required some tricky figuring to avoid
using the metadata as a node pointer.

> 
> Signed-off-by: Dimitris Charisis <dchar@cslab.ece.ntua.gr>
> 
> ---
> Dimitris Charisis (2):
>       maple_tree: remove mt_clear_meta() to fix a pointer corruption
>       maple_tree: fix invalid memory access in mt_free_walk()
> 
>  lib/maple_tree.c | 43 +------------------------------------------
>  1 file changed, 1 insertion(+), 42 deletions(-)
> ---
> base-commit: e2e54005e20fb42d4a5e140d70a65be4a2363045
> change-id: 20260912-fix-maple-tree-range64-rcu-02fa3d2e59a7
> 
> Best regards,
> -- 
> Dimitris Charisis <dchar@cslab.ece.ntua.gr>
> 
> 
> -- 
> maple-tree mailing list
> maple-tree@lists.infradead.org
> https://lists.infradead.org/mailman/listinfo/maple-tree

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

[Liam R. Howlett]

On 26/09/15 11:23AM, Liam R. Howlett wrote:
> On 26/09/13 03:26PM, Dimitris Charisis wrote:
> > I was running a patched kernel using a maple tree in RCU mode without
> > specifying the MT_FLAGS_ALLOC_RANGE flag and the kernel crashed. I
> > switched to an upstream kernel, and after some investigation and
> > debugging (thanks tools/testing/radix-tree/maple.c) I discovered that
> > there were two separate issues on the RCU destroy path that were
> > responsible. Both arising from the fact that a maple_range_64 node that
> > is not full repurposes its last slot to hold metadata. Each issue is
> > addressed by one of the two patches.
> > 
> > AFAIK there is no in-tree user of maple_range_64 nodes in RCU mode at
> > the moment. All in-tree users of MT_FLAGS_USE_RCU that I found also set
> > MT_FLAGS_ALLOC_RANGE which makes the internal nodes maple_arange_64.
> 
> Hello!
> 
> Thank you for your investigation and patches.  I will have a closer look
> soon, but for now I have a request for this series.
> 
> > 
> > Below is the minimal reproducer I 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;
> > }
> 
> Awesome!  What I ask people to do is to create a patch for the
> tools/testing/radix-tree/maple.c with the reproducer in its own patch
> that gets added after the fix.  This way we never re-introduce new
> features and the testing keeps passing for every bisection.
> 
> If you have one of these for each bug, then please add them after the
> fix.  I understand rcu is tricky to test when a race is involved, but I
> do have testing for many threads (which you probably saw).
> 
> The testing is less organized than I'd like and since this is RCU
> specific, you may need to use the testing file and not the module
> testing in lib/test_maple_tree.c.  If possible, I add the testing to the
> module, but if internal poking or threads need to be used, we put them
> in the userspace testing.

Your fixes look good - Thanks again.

Please respin with a few changes:
1. The message in this email will be preserved by Andrew including it as
part of the first patch change log so "I was running a patched kernel.."
should probably be removed and made more into a change log statement.

2. Add the testing to the userspace testing patch to enhance the test
suite please.

Thanks,
Liam

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

[Dimitris Charisis]

Στις 15/09/2026 20:13, Liam R. Howlett έγραψε:
> 
> Please respin with a few changes:
> 1. The message in this email will be preserved by Andrew including it 
> as
> part of the first patch change log so "I was running a patched 
> kernel.."
> should probably be removed and made more into a change log statement.
> 
> 2. Add the testing to the userspace testing patch to enhance the test
> suite please.
> 
> Thanks,
> Liam

Thanks! I will, as soon as I work out the way to properly add the tests
to the suite.