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

[Liam R. Howlett]

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@xxxxxxxxxxxxxxxxx>
> 
> ---
> 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@xxxxxxxxxxxxxxxxx
> 
> ---
> 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@xxxxxxxxxxxxxxxxx>
> 
> 
> -- 
> maple-tree mailing list
> maple-tree@xxxxxxxxxxxxxxxxxxx
> https://lists.infradead.org/mailman/listinfo/maple-tree