---
title: VMA and Maple Tree
url: https://doc.liz6.com/en/linux-kernel/02-memory-management/02-vma-and-maple-tree
locale: en
area: linux-kernel
tags:
- linux-kernel
- memory-management
date: 2026-06-30
modified: 2026-07-16
description: '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'
---

# 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

```c
// 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

| Flag | Meaning |
|------|---------|
| `VM_READ` / `VM_WRITE` / `VM_EXEC` | Access permissions |
| `VM_SHARED` | MAP_SHARED mapping (writes visible to others) |
| `VM_MAYSHARE` | Allowed to be converted to SHARED |
| `VM_GROWSDOWN` / `VM_GROWSUP` | Stack auto-growth (downward/upward) |
| `VM_HUGETLB` | HugeTLB mapping |
| `VM_LOCKED` | Memory locked by mlock() (not swappable) |
| `VM_IO` | MMIO mapping |
| `VM_PFNMAP` | Device mapping without page structs |

### 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

```mermaid
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

```c
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

```c
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

```c
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

```c
// 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

```c
// 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

```c
// 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:

```c
// 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

```bash
# 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*