The Maple Tree and VMA Lookup

The maple tree is an RCU-safe, range-based B-tree that stores non-overlapping ranges of unsigned long keys, and since Linux 6.1 (merged in the October 2022 merge window) it is the structure that holds a process’s virtual memory areas inside the [[The mm_struct and Process Address Space|mm_struct]] — the field mm->mm_mt. It replaced three older structures at once: the augmented red-black tree that ordered VMAs by address, the small per-task VMA lookup cache, and the doubly-linked list that threaded the VMAs for in-order traversal (Howlett & Wilcox, “Introducing the Maple Tree,” LWN 2022). The payoff is threefold: a wide B-tree has far fewer cache misses than a binary tree when walked, it handles ranges natively (a VMA spanning [vm_start, vm_end) is one entry, not a point), and — the long-term goal — it can be read locklessly under RCU, letting page faults look up a VMA without contending on the address-space-wide mmap_lock. This note covers the structure, the lookup API, and how a fault resolves an address to a VMA. It pins implementation claims to Linux 6.12 LTS (2024-11-17), noting 6.18 LTS (2025-11-30) differences.

Why Replace the Red-Black Tree?

For most of Linux’s history each mm_struct kept its VMAs in a red-black tree (a self-balancing binary search tree, augmented to carry the largest free gap in each subtree for mmap placement) plus a doubly-linked list (so the fault handler and /proc/<pid>/maps could walk VMAs in address order without re-descending the tree) plus a single-entry per-task cache of the most recently found VMA. Three structures, all describing the same set of VMAs, all needing to be kept consistent on every change.

The introductory LWN article lays out why this was unsatisfactory (Howlett, “Introducing maple trees,” LWN 2021): “rbtrees do not support ranges well, they are difficult to handle in a lockless manner (the balancing operation of the rbtree affects multiple items at the same time), and rbtree traversal is inefficient.” The deeper problem was the mmap_lock. Because the rbtree’s rebalancing rotates nodes — touching several at once — there was no safe way for a reader to traverse it while a writer rebalanced. So every VMA lookup, even a read-only one on the page-fault fast path, had to take the address-space-wide mmap_lock, and on large threaded workloads that lock became the dominant scalability bottleneck. The maple tree was designed from the start to be walked by RCU readers concurrently with writers, which is the precondition for the per-VMA locking that finally lets faults skip mmap_lock (see below).

Mental Model — A Wide, Range-Keyed, RCU-Walkable B-Tree

flowchart TB
  ROOT["Internal node (up to 10 slots)<br/>pivots partition the key space"]
  L1["Leaf node (up to 16 slots)<br/>range [0x400000,0x401000) → VMA a<br/>range [0x401000,0x60a000) → VMA b<br/>gap<br/>..."]
  L2["Leaf node (16 slots)<br/>range [0x7f..0000, 0x7f..2000) → VMA m<br/>..."]
  L3["Leaf node (16 slots)<br/>stack VMA, vdso, ..."]
  ROOT --> L1
  ROOT --> L2
  ROOT --> L3
  FAULT["page fault @ addr"] -->|"mas_walk(addr)"| ROOT
  ROOT -.->|"descend by pivots"| L1
  L1 -.->|"slot covering addr"| VMA["vm_area_struct"]

The maple tree holding one process’s VMAs. What it shows: instead of a binary tree where each node holds one VMA and two child pointers, each maple node holds many entries — up to 16 in a leaf, 10 in an internal node on 64-bit (the MAPLE_RANGE64_SLOTS / MAPLE_ARANGE64_SLOTS constants in include/linux/maple_tree.h, v6.12, each node being 256 bytes, i.e. a few cache lines). A lookup descends only a couple of levels even for thousands of VMAs. The insight to take: width is the whole point — a fault walks far fewer cache lines than the old rbtree, and because internal nodes are not rotated on the read path, RCU readers can descend safely while a writer modifies a different part of the tree.

The tree stores values from 0 to ULONG_MAX; a stored value is the vm_area_struct *, and a NULL slot means that range of the address space is unmapped (a gap). Because the tree is range-based, a single VMA covering [vm_start, vm_end) occupies one logical entry no matter how large the range — there is no per-page bookkeeping (confirmed against the v6.12 maple-tree documentation).

The Lookup API: Three Layers

The kernel exposes the maple tree at three levels of abstraction, and the VMA code uses all three.

The “normal” (simple) API, for one-shot operations that manage their own locking. Reads (mtree_load(mt, index) to fetch the entry at an index, mt_find(mt, &index, max) to search upward from index, mt_for_each to iterate a range) take the RCU read lock internally; writes (mtree_store, mtree_store_range, mtree_insert, mtree_erase) take the tree’s internal spinlock (ma_lock) internally (per the v6.12 maple_tree.rst).

The “advanced” API, built around a maple state (struct ma_state) that remembers where the last operation left off, so a caller can do several operations without re-descending from the root each time. It is set up with the macro MA_STATE(name, mt, first, end), which initializes a state on tree mt positioned at range [first, end]. The advanced functions all take mas_ prefixes: mas_walk() (walk to the entry containing mas->index), mas_load(), mas_store()/mas_store_gfp(), mas_find() (first entry at or above an index), mas_find_rev(), mas_next()/mas_prev() (traverse as if the tree were a linked list), mas_pause() (drop the lock mid-iteration safely), and mas_empty_area()/mas_empty_area_rev() (find a free gap — the operation that backs mmap’s “find an unmapped hole” search, replacing the rbtree’s augmented gap tracking). The advanced API does not lock for you — the caller holds mmap_lock or the RCU read lock as appropriate.

The VMA wrappers, a thin MM-specific layer that hides the maple state behind familiar names (from include/linux/mm.h, v6.12 and include/linux/mm_types.h). A struct vma_iterator simply is a wrapped ma_state:

struct vma_iterator { struct ma_state mas; };
#define VMA_ITERATOR(name, __mm, __addr) \
    struct vma_iterator name = { .mas = { .tree = &(__mm)->mm_mt, \
        .index = __addr, .node = NULL, .status = ma_start } }

The iterator is consumed by for_each_vma(vmi, vma) (walk every VMA from the iterator’s start to the end of the address space) and for_each_vma_range(vmi, vma, end) (walk VMAs up to end). Internally vma_next() calls mas_find(&vmi->mas, ULONG_MAX) and vma_prev() calls mas_prev(&vmi->mas, 0) — note the comment in the source that vma_next uses mas_find rather than mas_next for the first call, because mas_next would skip the entry the iterator is already sitting on.

Looking Up a VMA by Address — Two Different Queries

There are two subtly different “find the VMA” questions, and the kernel answers them with two different maple-tree primitives — a contrast worth internalizing because using the wrong one is a real bug class.

“Is this exact address inside a VMA?” → vma_lookup(mm, addr), which is simply mtree_load(&mm->mm_mt, addr) (from v6.12 mm.h). mtree_load returns the entry stored at that index, or NULL if addr falls in a gap. So vma_lookup returns the VMA covering addr or NULL — it never returns a VMA that starts after addr.

“What is the first VMA at or after this address?” → find_vma(mm, addr), the historical workhorse used by the fault handler and much else. In v6.12 it is:

struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
{
    unsigned long index = addr;
    mmap_assert_locked(mm);
    return mt_find(&mm->mm_mt, &index, ULONG_MAX);
}

mt_find searches upward from index, so find_vma returns the VMA containing addr or, if addr is in a gap, the next VMA above it (or NULL if there is none). The fault handler then checks whether addr actually falls within the returned VMA’s [vm_start, vm_end); if addr < vma->vm_start the fault is below all mappings (or in a gap), and stack-growth or SIGSEGV logic takes over. find_vma_intersection(mm, start, end) is the range version (mt_find bounded by end - 1), and find_vma_prev uses a VMA_ITERATOR to return both the VMA and its predecessor in one descent (all from v6.12 mm/mmap.c). Note the mmap_assert_locked(mm) — these functions require the mmap_lock to be held, because they do not use RCU.

The Lockless Fast Path: lock_vma_under_rcu

The reason the maple tree was made RCU-safe is the per-VMA-locked page-fault fast path. When a fault arrives, before grabbing the contended mmap_lock, the handler tries to find and read-lock just the one VMA it needs, entirely under RCU. The function is lock_vma_under_rcu() (v6.12 mm/memory.c):

struct vm_area_struct *lock_vma_under_rcu(struct mm_struct *mm,
                                          unsigned long address)
{
    MA_STATE(mas, &mm->mm_mt, address, address);
    struct vm_area_struct *vma;
 
    rcu_read_lock();
retry:
    vma = mas_walk(&mas);                 /* lockless descent of the maple tree */
    if (!vma)
        goto inval;
    if (!vma_start_read(vma))             /* try to take the per-VMA read lock */
        goto inval;
    if (vma->detached) {                  /* did it get isolated from the tree? */
        vma_end_read(vma);
        count_vm_vma_lock_event(VMA_LOCK_MISS);
        goto retry;                       /* tree changed under us — try again */
    }
    /* stable, locked VMA from here */
    if (unlikely(address < vma->vm_start || address >= vma->vm_end))
        goto inval_end_read;              /* bounds shifted before we locked */
    rcu_read_unlock();
    return vma;                           /* caller faults under the per-VMA lock */
 
inval_end_read:
    vma_end_read(vma);
inval:
    rcu_read_unlock();
    count_vm_vma_lock_event(VMA_LOCK_ABORT);
    return NULL;                          /* fall back to mmap_lock */
}

Walking through it: MA_STATE positions a maple state at the faulting address; mas_walk descends the tree under rcu_read_lock with no mmap_lock. If it lands on a VMA, vma_start_read attempts the per-VMA read lock. That lock is itself a careful sequence-number dance — in 6.12 it compares the VMA’s vm_lock_seq against the mm’s mm_lock_seq and, only if they differ, tries down_read_trylock on a separately-allocated struct vma_lock. If the whole address space was write-locked (the two sequence numbers match), the read lock is refused and the path bails to the slow mmap_lock. After locking, it re-checks two things that could have changed between the lockless walk and acquiring the lock: whether the VMA was detached (removed from the tree — retry), and whether the address still lies within [vm_start, vm_end) (the VMA could have been split/shrunk — abort). Only then is the VMA safe to fault under, with mmap_lock never touched. On any failure the function returns NULL and the caller retries the whole fault under mmap_lock.

Uncertain

Verify: the per-VMA lock internals differ across the 6.12↔6.18 range and must not be stated generically. In 6.12 LTS a VMA holds bool detached, int vm_lock_seq, and a pointer to a separately-allocated struct vma_lock (an rw_semaphore), and mm->mm_lock_seq is an int (verified, v6.12 mm_types.h). In 6.18 LTS this was reworked to an embedded refcount_t vm_refcnt (cacheline-aligned), unsigned int vm_lock_seq, no separate vm_lock/detached, and mm->mm_lock_seq is now a seqcount_t (verified, v6.18 mm_types.h). The lock_vma_under_rcu body quoted above is the 6.12 form; the 6.18 form uses the refcount scheme and differs in the detach check. Reason: actively-reworked subsystem; only 6.12’s memory.c body was read in full. To resolve: read lock_vma_under_rcu/vma_start_read in the v6.18 mm/memory.c and include/linux/mm.h. The maple-tree lookup part (mas_walk under RCU) is stable across both. uncertain

Store, Erase, and Gap-Finding

A write — an mmap adding a VMA, a munmap removing one, an mprotect splitting one — uses the iterator’s store path. vma_iter_bulk_store sets mas.index = vma->vm_start and mas.last = vma->vm_end - 1 and calls mas_store, which overwrites whatever ranges those keys cover and may allocate new maple nodes (hence mas_store_gfp variants that take GFP flags and can return -ENOMEM). Because a store can fail to allocate, the VMA code often preallocates maple nodes before taking the lock, so the critical section itself cannot fail. Erasing a range stores NULL over it. Finding an unmapped hole for a fresh mmap — the job the old augmented rbtree did with per-subtree max-gap tracking — is now mas_empty_area/mas_empty_area_rev, which the maple tree answers directly because it tracks gaps internally for trees flagged as allocation trees.

Failure Modes and Pitfalls

Walking the tree without the right lock. find_vma/vma_lookup assert mmap_lock is held (mmap_assert_locked); calling them locklessly is a bug that the assert catches in debug builds. The only sanctioned lockless lookup is lock_vma_under_rcu, and even it must re-validate the VMA after locking because the tree can change under an RCU reader.

The detached/bounds re-check is not optional. Skipping the vma->detached and address-in-range re-checks after vma_start_read reintroduces exactly the use-after-free / wrong-VMA bugs the careful dance exists to prevent — a VMA found locklessly may have been removed or resized before the lock was acquired.

StackRot (CVE-2023-3269). The first high-profile bug of the maple-tree VMA conversion: a use-after-free in stack-expansion VMA handling, present “since version 6.1 when the VMA tree structure was changed from red-black trees to maple trees” (StackRot), exploitable for local privilege escalation. It underscores that swapping the core address-space data structure also changed lifetime and locking invariants, and that the maple tree’s RCU lifetime rules (a VMA freed via RCU callback so lockless readers don’t trip) are load-bearing for security.

Confusing mtree_load vs mt_find semantics (the vma_lookup vs find_vma distinction above): code expecting “the VMA at this address” but calling find_vma will silently get the next VMA above a gap and, if it forgets the bounds check, operate on the wrong region.

Alternatives and When the Old Design Still Appears

The maple tree is now the universal VMA store in mainline; the rbtree-plus-list-plus-cache design exists only in kernels older than 6.1. The augmented red-black tree is still used elsewhere in the kernel (the CFS/EEVDF scheduler runqueue, the high-resolution timer tree) where the keys are points rather than ranges and lockless reads are not needed — so “rbtree vs maple tree” is really “point keys vs range keys, and do you need RCU readers.” Where you need ordered ranges with lockless lookup, the maple tree wins; where you need a simple ordered set of points, an rbtree is lighter. The maple tree’s own next steps (large-folio-aware gaps, broader adoption beyond VMAs) were discussed at the 2024 summit (LWN, “The next steps for the maple tree”).

See Also

• The mm_struct and Process Address Space — owns the mm_mt field this note’s tree lives in; the sibling note.
• Virtual Memory Areas — the vm_area_struct entries the tree stores.
• Red-Black Tree — the structure (plus a VMA cache and linked list) the maple tree replaced in 6.1.
• The Page Fault Handler — the chief consumer of lock_vma_under_rcu and find_vma.
• Split Page Table Locks — the finer-grained locking story the RCU-walkable tree enables, alongside the per-VMA lock.
• mmap brk and Address Space System Calls — the writers (mmap/munmap/mprotect) that store into and erase from the tree, using mas_empty_area to place new mappings.
• MOC: Linux Memory Management MOC (section 1, Virtual Memory and the Process Address Space).