linux-kernel - [PATCH v2 hotfix 6.12 0/2] maple_tree: correct tree corruption on spanning store

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-ID: <cover.1728223996.git.lorenzo.stoakes@oracle.com>
Date: Sun,  6 Oct 2024 15:31:06 +0100
From: Lorenzo Stoakes <lorenzo.stoakes@...cle.com>
To: Andrew Morton <akpm@...ux-foundation.org>,
        "Liam R . Howlett" <Liam.Howlett@...cle.com>
Cc: Matthew Wilcox <willy@...radead.org>, Vlastimil Babka <vbabka@...e.cz>,
        linux-mm@...ck.org, linux-kernel@...r.kernel.org,
        Sidhartha Kumar <sidhartha.kumar@...cle.com>,
        Bert Karwatzki <spasswolf@....de>,
        Mikhail Gavrilov <mikhail.v.gavrilov@...il.com>,
        maple-tree@...ts.infradead.org
Subject: [PATCH v2 hotfix 6.12 0/2] maple_tree: correct tree corruption on spanning store

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.

v2:
* Majorly improve clarity of commit message describing the problem.
* Add a reproducable test.
* Add missing maple tree mailing list to cc- list.

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                 | 20 ++++++--
 tools/testing/radix-tree/maple.c | 84 ++++++++++++++++++++++++++++++++
 2 files changed, 100 insertions(+), 4 deletions(-)

--
2.46.2