[PATCH v2 0/4] maple_tree: fix maple_range_64 crashes in RCU mode
Liam R. Howlett
liam at infradead.org
Thu Oct 1 07:13:30 PDT 2026
On 26/09/16 11:38AM, 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. Patches 1 and
> 3 address each issue, and patches 2 and 4 add the tests 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.
Dimitris,
Sorry for the delayed response.
Thanks for adding the tests to the patches.
Right now the mt_clear_metadata() will avoid descending into an invalid
child (metadata being detected as node on mt_free_walk()). Your first
fix made the second fix necessary. Both are needed, but the ordering is
wrong.
If we use them in the order you sent, then a bisect hole is crated where
we may descend into the metadata thinking it is a node. So testing
between the two may cause a crash otherwise not seen.
Considering how tightly bound these fixes are, I would consider them to
be two parts of the same issue; they should be combined into a single
fix.
Thanks for the testing patches, please keep them for v3.
>
> 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;
> }
>
> 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 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
> ==================================================================
>
> Patch 3 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 at 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 (4):
> maple_tree: remove mt_clear_meta() to fix a pointer corruption
> test_maple_tree: test a full maple_range_64 node in RCU mode
> maple_tree: fix invalid memory access in mt_free_walk()
> test_maple_tree: test a maple_range_64 metadata slot 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>
>
>
> --
> maple-tree mailing list
> maple-tree at lists.infradead.org
> https://lists.infradead.org/mailman/listinfo/maple-tree
More information about the maple-tree
mailing list