How Maple Tree Manages VMAs

Starting from Linux 6.1, the kernel replaced both the linked list (mmap) and the red-black tree (mm_rb) used to manage Virtual Memory Areas (VMAs) with a new data structure called the Maple Tree.
Maple Tree is a range-based tree structure designed for storing non-overlapping ranges.
It provides:

• Fast lookup
• Efficient traversal
• Better memory usage
• Read Copy and Update (RCU) safe operations Unlike a red-black tree, Maple Tree stores ranges directly, which matches how VMAs are represented.

Maple Tree Structure

Maple Tree nodes contain:

• Slots
• Pivots Each node 15x pivots and 16x entries. A slot stores an entry, while pivots define the range boundaries. The range information is implied by the pivot values instead of storing every range boundary explicitly. This allows Maple Tree to store large numbers of memory ranges efficiently.

Replace Operation

When modifying a Maple Tree node:

1. Maple Tree locates the node containing the target range.
2. A new empty node is allocated.
3. Existing entries and pivots before the modified range are copied into the new node.
4. The node is split at the position where the new range will be inserted.
5. The new entry is inserted into the correct slot.
6. The remaining entries and pivots after the modified range are copied into the new node.
7. The original node is replaced with the newly created node.

This replacement approach allows Maple Tree to support safe concurrent reads using RCU. Readers can continue accessing the old node while the writer prepares the updated version. Once the new node is complete, the kernel switches the reference to the new node.

Node Splitting

When a Maple Tree node becomes full and cannot store another entry:

1. The full node is removed from the active tree structure.
2. Two new nodes are created.
3. Existing entries and pivots are redistributed between the two new nodes.
4. The new entry is inserted into the correct position during the redistribution process.
5. The parent node is updated with the new child nodes and new pivot values. The split operation tries to keep the data density balanced between the two nodes while avoiding unnecessary tree height growth. After splitting, the parent node receives an additional slot pointing to the new node. The new pivot information is updated to represent the new range boundaries.

Maple Tree tries to maintain:

• High Data Density: Nodes should contain many entries to reduce memory usage and improve cache efficiency.
• Lower Tree Height: A shorter tree reduces the number of steps required during lookup.
• Avoid Underfilled Nodes: After deletion or modification, entries may be redistributed or merged to avoid wasting space.

When multiple entries can be represented more efficiently as a single range:

1. A new node is created for the reorganized entries.
2. Existing entries are copied from the previous nodes.
3. Entries that can be represented as a continuous range are compressed into a single slot and pivot.
4. Remaining entries are moved together with neighbouring nodes.
5. The parent node is updated with the new node layout and pivot information.

This reduces the number of slots required and keeps the tree compact.
The goal of rebalancing is to maintain efficient storage by reducing unnecessary nodes while keeping lookup performance high.

Special thanks to the Linux Foundation and Liam Howlett's talk "The Maple Tree: Structure and Algorithms", which helped me understand the internal design and algorithms behind Maple Tree.
Link: https://www.youtube.com/watch?v=RaXhP-QLUxI