CVE-2024-50200

In the Linux kernel, the following vulnerability has been resolved:<br /> <br /> maple_tree: correct tree corruption on spanning store<br /> <br /> Patch series "maple_tree: correct tree corruption on spanning store", v3.<br /> <br /> There has been a nasty yet subtle maple tree corruption bug that appears<br /> to have been in existence since the inception of the algorithm.<br /> <br /> This bug seems far more likely to happen since commit f8d112a4e657<br /> ("mm/mmap: avoid zeroing vma tree in mmap_region()"), which is the point<br /> at which reports started to be submitted concerning this bug.<br /> <br /> We were made definitely aware of the bug thanks to the kind efforts of<br /> Bert Karwatzki who helped enormously in my being able to track this down<br /> and identify the cause of it.<br /> <br /> The bug arises when an attempt is made to perform a spanning store across<br /> two leaf nodes, where the right leaf node is the rightmost child of the<br /> shared parent, AND the store completely consumes the right-mode node.<br /> <br /> This results in mas_wr_spanning_store() mitakenly duplicating the new and<br /> existing entries at the maximum pivot within the range, and thus maple<br /> tree corruption.<br /> <br /> The fix patch corrects this by detecting this scenario and disallowing the<br /> mistaken duplicate copy.<br /> <br /> The fix patch commit message goes into great detail as to how this occurs.<br /> <br /> This series also includes a test which reliably reproduces the issue, and<br /> asserts that the fix works correctly.<br /> <br /> Bert has kindly tested the fix and confirmed it resolved his issues. Also<br /> Mikhail Gavrilov kindly reported what appears to be precisely the same<br /> bug, which this fix should also resolve.<br /> <br /> <br /> This patch (of 2):<br /> <br /> There has been a subtle bug present in the maple tree implementation from<br /> its inception.<br /> <br /> This arises from how stores are performed - when a store occurs, it will<br /> overwrite overlapping ranges and adjust the tree as necessary to<br /> accommodate this.<br /> <br /> A range may always ultimately span two leaf nodes. In this instance we<br /> walk the two leaf nodes, determine which elements are not overwritten to<br /> the left and to the right of the start and end of the ranges respectively<br /> and then rebalance the tree to contain these entries and the newly<br /> inserted one.<br /> <br /> This kind of store is dubbed a &amp;#39;spanning store&amp;#39; and is implemented by<br /> mas_wr_spanning_store().<br /> <br /> In order to reach this stage, mas_store_gfp() invokes<br /> mas_wr_preallocate(), mas_wr_store_type() and mas_wr_walk() in turn to<br /> walk the tree and update the object (mas) to traverse to the location<br /> where the write should be performed, determining its store type.<br /> <br /> When a spanning store is required, this function returns false stopping at<br /> the parent node which contains the target range, and mas_wr_store_type()<br /> marks the mas-&gt;store_type as wr_spanning_store to denote this fact.<br /> <br /> When we go to perform the store in mas_wr_spanning_store(), we first<br /> determine the elements AFTER the END of the range we wish to store (that<br /> is, to the right of the entry to be inserted) - we do this by walking to<br /> the NEXT pivot in the tree (i.e. r_mas.last + 1), starting at the node we<br /> have just determined contains the range over which we intend to write.<br /> <br /> We then turn our attention to the entries to the left of the entry we are<br /> inserting, whose state is represented by l_mas, and copy these into a &amp;#39;big<br /> node&amp;#39;, which is a special node which contains enough slots to contain two<br /> leaf node&amp;#39;s worth of data.<br /> <br /> We then copy the entry we wish to store immediately after this - the copy<br /> and the insertion of the new entry is performed by mas_store_b_node().<br /> <br /> After this we copy the elements to the right of the end of the range which<br /> we are inserting, if we have not exceeded the length of the node (i.e. <br /> r_mas.offset