[PATCH v3 0/2] maple_tree: fix maple_range_64 crashes in RCU mode
Liam R. Howlett
liam at infradead.org
Tue Oct 20 05:57:05 PDT 2026
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 at 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 at 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 at cslab.ece.ntua.gr>
>
More information about the maple-tree
mailing list