[PATCH v1 0/2] maple_tree: fix RCU-mode destroy of trees without MT_FLAGS_ALLOC_RANGE

[Nickolai Zeldovich]

Destroying a maple tree in RCU mode marks its nodes dead and leaves the
freeing to an RCU callback.  In a tree without MT_FLAGS_ALLOC_RANGE the
internal nodes keep their metadata in the last slot when it is unused,
and that path gets the two cases wrong:

1. mt_free_walk() takes the metadata of a 15-child node for a child and
   dereferences address 0x0e + 0x24 from the RCU softirq: oops, panic.
2. mt_destroy_walk() "clears the metadata" of a full start node after
   its slots were rewritten, which corrupts its last child pointer;
   mt_free_walk() then frees the wrong address (double free or freeing
   a live node) and leaks the real child.

Both come from the v6.3-rc6 RCU fixes: 2e5b4921f8ef cleared the metadata
of every node in mte_destroy_descend() and once more at the end of
mt_destroy_walk(); 790e1fa86b34 dropped the per-node call.  Patch 1
restores it; patch 2 removes the late call, which then only does harm.
Patch 2 depends on patch 1.  Both are deterministic, no race needed.

No in-tree user reaches either today: every tree used in RCU mode has
MT_FLAGS_ALLOC_RANGE.  The API allows RCU mode on any tree, though.

Found while formally verifying the maple tree destroy path against the
kernel binary.

Testing: each patch adds a case to lib/test_maple_tree.c that fails
without the fix (userspace suite: SIGSEGV, AddressSanitizer bad free;
kernel: oops at boot, KASAN report) and passes with it.  The userspace
maple suite passes; x86_64 and riscv defconfig builds with LLVM=1 have
no warnings, W=1 and sparse report nothing new for lib/maple_tree.o and
lib/test_maple_tree.o; x86_64 (also with KASAN) and riscv64 QEMU boots
with CONFIG_TEST_MAPLE_TREE=y pass the maple tree tests.

Nickolai Zeldovich (2):
  maple_tree: restore per-node metadata clearing in
    mte_destroy_descend()
  maple_tree: remove the late metadata clearing from mt_destroy_walk()

 lib/maple_tree.c      |  3 +--
 lib/test_maple_tree.c | 19 +++++++++++++++++++
 2 files changed, 20 insertions(+), 2 deletions(-)


base-commit: 24a19b953e2a3d0ea5a8c4951a0ab8f32720c907
-- 
2.53.0