[PATCH 0/3] maple_tree: fix two bugs when freeing RCU-mode trees

[Florian Schmaus]

Destroying a non-allocation maple tree with MT_FLAGS_USE_RCU defers freeing
its nodes to mt_free_walk(). There are two independent bugs on that path,
both caused by the metadata that a maple_range_64 node may keep in its last
slot:

 1. mt_free_walk() takes the metadata of a node with 15 children for a
    child node and dereferences it.
    Reproduced with: 2768 ranges / height 4

 2. mt_destroy_walk() takes the last child of a full node for metadata
    and corrupts its pointer, so mt_free_walk() frees a bogus address.
    Reproduced with: 120 ranges / a full root

Patch 3 adds a regression test for both cases to lib/test_maple_tree.c.

Testing: on x86_64, in the userspace test harness
(tools/testing/radix-tree) built with ASan and UBSan, the new test fails at
120 ranges without patch 2 and at 2768 ranges without patch 1. With the
whole series, all maple tree tests pass. The full suite also passes on
s390x (big-endian) under qemu-user.

No in-tree user is known to hit either bug, because all in-tree RCU-mode
trees (mm_mt, sparse_irqs) are allocation trees, whose nodes keep the
metadata in a separate field.

We identified these issues on a CHERI [1, 2] system, which provides
fine-grained memory protection through architectural capabilities. Our
CHERI Linux port uses plain RCU-mode maple trees for CHERI-based temporal
safety via revocation and destroys them after every revocation sweep, which
exercises a path that in-tree users do not reach. Unlike traditional
MMU-based protection, under which zeroing the low bytes of a node pointer
silently yields another "valid" address, CHERI invalidated the damaged
pointer: the partial write cleared its capability tag. Consequently, the
kernel trapped at the next use of that pointer, and the bounds of the
faulting capability, exactly one maple node, pointed to a corrupted maple
node pointer. We then reproduced both bugs without CHERI on x86 with the
userspace test harness under ASan.

1: https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/
2: https://codasip.com/solutions/riscv-processor-safety-security/cheri/

Signed-off-by: Florian Schmaus <florian.schmaus at codasip.com>
---
Florian Schmaus (3):
      maple_tree: do not descend into metadata in mt_free_walk()
      maple_tree: do not clear the metadata of a full dead node
      maple_tree: add a test for destroying RCU-mode trees

 lib/maple_tree.c      | 19 +++++++++++++++----
 lib/test_maple_tree.c | 32 ++++++++++++++++++++++++++++++++
 2 files changed, 47 insertions(+), 4 deletions(-)
---
base-commit: 4056b3c9d3c92ea45955641dbafeb9b960e146ef
change-id: 20261015-maple-tree-fix-slab-corruption-d1f098521d15

Best regards,
--  
Florian Schmaus <florian.schmaus at codasip.com>