VMA and Maple Tree

Coverage: vm_area_struct → VMA operations (mmap/munmap/mprotect/mremap) → Maple Tree replacing Red-Black Tree (6.1+) → VMA merging → Page fault and VMA lookup Kernel version: 2.6 ~ 6.x, with a focus on the Maple Tree migration

Overview

The address space of each process is described by a set of VMAs (Virtual Memory Areas). A VMA represents a contiguous range of virtual addresses with identical protection attributes and mapping types (anonymous memory, file mappings, device mappings, etc.). mmap() creates a VMA, munmap() destroys a VMA, and mprotect() modifies VMA attributes.

Traditionally, VMAs were managed using a Red-Black Tree plus a doubly linked list (O(log n) lookup, O(n) traversal). The Maple Tree, introduced in version 6.1, reduces operations to O(log n) while supporting lockless read traversal—one of the most significant data structure changes in the memory management subsystem in recent years.

vm_area_struct

// include/linux/mm_types.h
struct vm_area_struct {
    // Address range
    unsigned long           vm_start;
    unsigned long           vm_end;         // Not included in the VMA (half-open interval)

    // List/tree nodes (Old: Red-Black Tree, New: Maple Tree)
    union {
        struct {
            struct list_head    vm_list;    // Doubly linked list (for traversal)
            struct rb_node      vm_rb;      // Red-Black Tree (for lookup, 6.0-)
        };
        // 6.1+: VMAs are fully managed by the Maple Tree; these fields are overwritten
    };

    // Attributes
    pgprot_t                vm_page_prot;  // Page protection bits (R/W/X encoding)
    unsigned long           vm_flags;      // VM_READ, VM_WRITE, VM_EXEC, VM_SHARED, ...

    // Associated mm_struct and file (if file-backed)
    struct mm_struct        *vm_mm;
    struct file             *vm_file;      // NULL for anonymous
    unsigned long           vm_pgoff;      // Offset in the file (in pages)

    // Operation function table
    const struct vm_operations_struct *vm_ops;  // open, close, fault, ...

    // Anonymous mapping
    struct anon_vma         *anon_vma;     // Key for reverse mapping (rmap)
    struct anon_vma_name    *anon_name;    // [anon:name] (5.17+)

    // Shared memory (shmem / MAP_SHARED anonymous)
    struct address_space    *vm_swap;      // address_space for the swap cache
};

Key vm_flags

Anonymous vs. File-backed VMA Classification

Anonymous VMA:
  vm_file == NULL
  Examples: Heap/stack allocated by malloc/mmap(MAP_ANONYMOUS)
  Data has no corresponding disk file
  Written to swap partition/file during swapping

File-backed VMA:
  vm_file != NULL
  Examples: mmap(regular file), code segments (ELF LOAD segments from exec)
  Pages in the page cache match file contents
  Dirty pages are written back to the corresponding file

VMA Operations

mmap: Creating a VMA

flowchart TD
    SYSCALL["mmap() System Call"] --> AREA["get_unmapped_area()<br/>Find free address range"]

    AREA --> ARCH{"Architecture-specific search"}
    ARCH -->|"x86"| TOPDOWN["Top-down search<br/>(top-down, ASLR)"]
    ARCH -->|"legacy"| BOTTOMUP["Bottom-up<br/>(mmap_legacy_base)"]

    AREA --> REGION["mmap_region()"]

    REGION --> CHECK{"Check relationship with existing<br/>VMAs"}
    CHECK -->|"Exact match"| MERGE["Reuse or merge"]
    CHECK -->|"Partial overlap"| SPLIT["Split VMA"]
    CHECK -->|"No overlap"| NEW["Create new VMA"]

    NEW --> VM_OPS["Call vm_ops->mmap()<br/>Filesystem callback<br/>e.g., ext4: register filemap_fault()"]

    VM_OPS --> DEMAND["⚠️ Page table NOT updated!<br/>Demand paging:<br/>Actual allocation deferred to page fault"]

    DEMAND --> RET["Return mapping start address ✅"]

    classDef sys call fill:#e3f2fd,stroke:#1565c0
    classDef step fill:#f3e5f5,stroke:#7b1fa2
    classDef decision fill:#fff3e0,stroke:#ef6c00
    classDef done fill:#e8f5e9,stroke:#2e7d32
    class SYSCALL syscall
    class AREA,TOPDOWN,BOTTOMUP,REGION,MERGE,SPLIT,NEW,VM_OPS,DEMAND step
    class ARCH,CHECK decision
    class RET done

munmap: Destroying a VMA

SYSCALL_DEFINE2(munmap, ...) → do_munmap()

do_munmap():
  ├─ find_vma_intersection()   // Find VMAs covering this range
  ├─ Split VMA (if partial unmapping)
  ├─ detach_vmas_to_be_unmapped()
  │   └─ Detach from the mm's VMA set
  ├─ unmap_region()
  │   └─ unmap_vmas → Iterate VMA list
  │       └─ unmap_page_range()
  │           → Clear corresponding page table entries (zap_pte_range)
  │           → Free physical pages (put_page → drop to page cache if not the last reference)
  │           → TLB shootdown (multi-core)
  └─ remove_vma_list()
      └─ Free vm_area_struct (kmem_cache_free)

mprotect: Changing Permissions

SYSCALL_DEFINE3(mprotect, ...) → do_mprotect_pkey()

// No need to reallocate physical pages; only PTE flags need changing:
//   Change VM_WRITE → PTE R/W bit
//   Change VM_EXEC  → PTE NX bit
//   Requires page table walk → set_pte_at() → flush TLB

mremap: Resizing/Moving

SYSCALL_DEFINE5(mremap, ...) → do_mremap()

// MREMAP_MAYMOVE: Allows moving
//   → If insufficient space after current address:
//     get_unmapped_area() finds a new location
//     move_page_tables() → Copies page table entries to new location (does NOT copy physical pages!)
//     → TLB flush
//
// Interaction with realloc:
//   glibc uses mremap to expand large allocations → avoids copying physical memory

Maple Tree: The New Engine for VMA Management

Why Replace the Red-Black Tree

Old Design (Red-Black Tree + Linked List, 2.6 ~ 6.0):
  VMAs existed in both a Red-Black Tree (O(log n) lookup) and a doubly linked list (O(n) traversal).
  Drawbacks:
    - Two data structures must be kept in sync → Complex
    - All operations require mmap_lock → Lock contention
    - Linked list traversal is O(n) in dense VMA scenarios (e.g., many mmaps)

New Design (Maple Tree, 6.1+):
  VMAs exist only in the Maple Tree.
  Advantages:
    - All operations are O(log n): lookup/insert/delete/range query
    - Supports Lockless read traversal (RCU-protected): future page faults may not need locks
    - Efficient range operations: directly finds all overlapping VMAs
    - B-tree variant: Cache-line friendly, variable node sizes

Maple Tree Structure

// lib/maple_tree.c
// The Maple Tree is a B-tree variant, with up to 16 slots per node

// Node types:
//   MAPLE_NODE_DENSE:  All slots contain data (similar to an array)
//   MAPLE_NODE_RANGE:  Slots carry range information (for sparse storage)

// Each level can encode different key ranges:
//   Node 0: [0, 4096)     (4K)
//   Node 1: [0, 16777216) (16M)
//   Node 2: [0, 68719476736) (64G)
//   ...
//   Up to 8 levels total (for 64-bit keys)

// For VMAs:
//   key = Virtual address (start)
//   value = vm_area_struct *
//   Lookup: mas_find() → Finds the VMA covering a specific address

Lockless Traversal

// RCU-safe design of the Maple Tree:
//   Modifiers: Acquire spinlock → Modify node (if node is full → split + copy)
//   Readers:   Do not acquire lock → Read node via rcu_dereference
//              Nodes are not modified in-place by writers; instead, they are copied and then modified → Old nodes are reclaimed via RCU
//
// This is the biggest value of the Maple Tree:
//   Future do_page_fault() can look up VMAs under an RCU read lock
//   → No need for mmap_lock (for readers) → Eliminates mmap_lock contention

Page Fault and VMA Lookup

// arch/x86/mm/fault.c
// do_page_fault() is the hottest VMA lookup path

static void do_page_fault(struct pt_regs *regs, unsigned long error_code) {
    unsigned long address = read_cr2();  // Get the virtual address that caused the fault

    // 1. Acquire mmap_read_lock(mm)
    //
    // 2. find_vma(mm, address)
    //    Old: find_vma() → Red-Black Tree lookup
    //    New: find_vma() → mas_find(&mas, address, ...) → Maple Tree lookup
    //
    //    Found: Return the VMA covering the address
    //    Not found: SIGSEGV
    //
    // 3. Check VMA permissions (compare vm_flags with error_code)
    //    Read but VM_READ not set? → SIGSEGV
    //    Write but VM_WRITE not set? → SIGSEGV (Critical during Copy-On-Write!)
    //
    // 4. handle_mm_fault() → Allocate physical page + Create PTE
    //    Anonymous: do_anonymous_page() / do_swap_page()
    //    File: do_fault() → filemap_fault()
    //
    // 5. Release mmap_read_lock(mm)
}

VMA Merging

Adjacent VMAs with identical attributes are automatically merged:

// mm/mmap.c
// vma_merge():
//   Compare new mmap request with preceding and succeeding VMAs:
//     Are vm_flags identical?
//     Is vm_file identical? (or both are anonymous)
//     Is vm_pgoff contiguous?
//     Do PROT settings match?
//     Are anon_vmas compatible?
//   → If conditions are met: Merge into a single larger VMA
//
// Why merge?
//   Reduce VMA count → Less lookup time
//   Reduce slab allocations (vm_area_struct)
//   /proc/<pid>/maps displays more cleanly
//
// Classic example:
//   brk() expands heap → Multiple small expansions → Automatically merged into one large [heap] VMA

Debugging

# VMA Layout
cat /proc/<pid>/maps  # Human-readable
cat /proc/<pid>/smaps # Memory statistics per VMA (RSS/PSS/Swap)

# VMA Statistics
cat /proc/<pid>/status | grep Vm
# VmPeak: Historical maximum virtual memory
# VmSize: Current total virtual memory
# VmRSS:  Physical memory usage (Resident Set Size)
# VmData/VmStk/VmExe/VmLib: Data/Stack/Code/Libraries

# Monitor VMA count (excessive VMAs degrade performance)
wc -l /proc/<pid>/maps

References and Further Reading

• Kernel Documentation: Documentation/core-api/maple_tree.rst, Documentation/mm/mmap.rst
• LWN:
  • "Introducing the Maple Tree" (lwn.net/Articles/867525/)
  • "The state of the Maple Tree" (lwn.net/Articles/905317/)
  • "mmap_lock and VMA locking" (lwn.net/Articles/909840/)
• Source Files:
  • lib/maple_tree.c — Maple Tree implementation
  • mm/mmap.c — VMA management (mmap/munmap/mprotect)
  • include/linux/mm_types.h — vm_area_struct definition
  • arch/x86/mm/fault.c — Page fault handler

Keywords: vm_area_struct, VMA, mmap, munmap, Maple Tree, page fault, find_vma, VM_MERGEABLE, mmap_lock