The memory descriptor (mm_struct) maintains information about a process's address space (current memory it owns). One of its members is a linked list of Virtual Memory Areas (VMAs), represented by vm_area_struct.
The memory descriptor (mm_struct) contains a field named mmap, which points to the head of the linked list of Virtual Memory Areas (VMAs). Each VMA (vm_area_struct) contains a pointer vm_next to the next memory region, allowing the kernel to traverse all virtual memory regions owned by the process.
The number of VMAs currently owned by the process is stored in map_count. The Linux kernel also imposes a maximum number of VMAs (65,536 by default), although most processes use far fewer.
A linked list works well when a process owns only a small number of memory regions. However, applications that frequently allocate memory (for example, through malloc(), shared libraries, or memory-mapped files) may end up with hundreds or thousands of VMAs.
Searching for a particular memory region by traversing the linked list requires examining each node until the desired region is found, giving a time complexity of O(n).
To improve lookup performance, Linux also stores the VMAs in a red-black tree. Since the tree remains approximately balanced, searching for a memory region requires only O(log n) time.
Each VMA contains an embedded red-black tree node (vm_rb of type struct rb_node). The root of the tree is stored in the process's memory descriptor (mm_rb).
The tree is ordered by the starting virtual address (vm_start) of each memory region:
- Memory regions with a smaller starting address are placed in the left subtree.
- Memory regions with a larger starting address are placed in the right subtree.
A red-black tree maintains balance using the following properties:
- Every node is coloured either red or black.
- The root node is always black.
- If a node is red, both of its children must be black. (Two consecutive red nodes are not allowed.)
- Every path from a node to any descendant NIL (null) leaf contains the same number of black nodes. The NIL leaves are conceptual nodes and are considered black.
These rules ensure that the tree remains balanced, limiting its height to at most 2 logâ‚‚(n + 1). As a result, searching, inserting, and deleting VMAs all have O(log n) time complexity, making them significantly faster than traversing a linked list when a process owns many memory regions.
Maple Tree (Linux 6.1+)
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.
Previously, the memory descriptor (mm_struct) contained both:
struct vm_area_struct *mmap; // Linked list of VMAs
struct rb_root mm_rb; // Red-black tree of VMAs
The linked list was used to iterate through all memory regions, while the red-black tree provided fast lookups. Every time a VMA was inserted or removed, both structures had to be updated.
In modern kernels, these fields have been replaced by a single Maple Tree:
struct maple_tree mm_mt;
The Maple Tree performs both tasks:
- Fast searching for a memory region.
- Efficient traversal of all VMAs. As a result, the kernel only needs to maintain one data structure instead of two.
How the Maple Tree works
Unlike a red-black tree, where each node stores only a single memory region, a Maple Tree stores multiple memory regions within each node.
For example, a red-black tree might look like:
40
/ \
20 60
/ \ / \
10 30 50 70
where each node stores one key.
A Maple Tree is conceptually more like:
+--------------------------------------+
| 10 | 20 | 30 | 40 | 50 | 60 | 70 |
+--------------------------------------+
where a single node stores multiple keys and pointers to child nodes. This is similar to a B-tree, although the Maple Tree has its own specialised implementation for managing ranges of virtual addresses.
Searching, inserting, and deleting VMAs continue to have a time complexity of O(log n), but with lower constant overhead and better real-world performance than the previous implementation.
Top comments (0)