There has been a nasty yet subtle maple tree corruption bug that appears to
have been in existence since the inception of the algorithm.
This bug seems far more likely to happen since commit f8d112a4e657
("mm/mmap: avoid zeroing vma tree in mmap_region()"), which is the point at
which reports started to be submitted concerning this bug.
We were made definitely aware of the bug thanks to the kind efforts of Bert
Karwatzki who helped enormously in my being able to track this down and
identify the cause of it.
The bug arises when an attempt is made to perform a spanning store across
two leaf nodes, where the right leaf node is the rightmost child of the
shared parent, AND the store completely consumes the right-mode node.
This results in mas_wr_spanning_store() mitakenly duplicating the new and
existing entries at the maximum pivot within the range, and thus maple tree
corruption.
The fix patch corrects this by detecting this scenario and disallowing the
mistaken duplicate copy.
The fix patch commit message goes into great detail as to how this occurs.
This series also includes a test which reliably reproduces the issue, and
asserts that the fix works correctly.
Bert has kindly tested the fix and confirmed it resolved his issues. Also
Mikhail Gavrilov kindly reported what appears to be precisely the same bug,
which this fix should also resolve.
Please note - I am intentionally holding off on cc'ing stable until we've
had a chance to be satisfied the series has stabilised in 6.12 as this is a
highly subtle change.
v3:
* Significantly simplify the solution to a one-liner as suggested by Liam.
* Eliminate incorrect boolean return type in mas_wr_walk_index().
v2:
* Majorly improve clarity of commit message describing the problem.
* Add a reproducable test.
* Add missing maple tree mailing list to cc- list.
https://lore.kernel.org/linux-mm/cover.1728223996.git.lorenzo.stoakes@oracle.com/
v1:
https://lore.kernel.org/linux-mm/20241005064114.42770-1-lorenzo.stoakes@oracle.com/
Lorenzo Stoakes (2):
maple_tree: correct tree corruption on spanning store
maple_tree: add regression test for spanning store bug
lib/maple_tree.c | 12 ++---
tools/testing/radix-tree/maple.c | 84 ++++++++++++++++++++++++++++++++
2 files changed, 90 insertions(+), 6 deletions(-)
--
2.46.2