learnbytes.dev
← Back to Blog

The vmalloc Deep Dive: Trees, Tables, and Per-CPU Tricks

By
The vmalloc Deep Dive: Trees, Tables, and Per-CPU Tricks

For an aspiring Linux kernel developer, understanding the internal mechanics of vmalloc is a crucial milestone. While kmalloc maps physically contiguous memory directly, vmalloc allows the kernel to stitch together disparate physical pages into a contiguous virtual address space.

In this post, we will explore the core functions and structures in mm/vmalloc.c that power this mechanism. Specifically, we will dive into three key operations:

  1. Finding Free Virtual Space via the augmented Red-Black Tree in alloc_vmap_area.
  2. Setting Up the Page Tables via the nested multi-level page table walk in vmap_pages_range.
  3. Allocating Per-CPU Virtual Memory via the top-down congruent offset model in pcpu_get_vm_areas.

1. Finding Free Virtual Space: alloc_vmap_area

Before the kernel can map physical pages into a virtual address block, it must find an available region of virtual memory within the VMALLOC_START to VMALLOC_END range. This is the job of alloc_vmap_area [1].

The Core Mechanism

The kernel tracks free chunks of virtual memory address space using a Red-Black Tree (RB-Tree) and an augmented doubly linked list. This allows the memory manager to quickly find free address ranges that satisfy the size and alignment requirements.

Loading diagram...
Note

Why an RB-Tree? The virtual address space for vmalloc is huge. Searching a simple linked list for a contiguous hole would be O(N)O(N). An augmented RB-Tree allows the kernel to find a suitable gap (first-fit or best-fit) in O(log⁡N)O(\log N) time, significantly improving performance.

What is a "Block" in vmalloc?

When the codebase or documentation refers to a "block" (or a free virtual memory block), it is talking about a struct vmap_area. This structure represents a contiguous range of virtual memory (defined by a va_start and va_end).

In the context of the Red-Black Tree, every node in the tree is one of these vmap_area structs representing a hole (a free block) in the virtual address space. When you request memory, you are asking the kernel to find a free "block" large enough to fit your request, and then carve your requested size out of it.

Step-by-Step Explanation

  1. Searching the Tree (find_vmap_lowest_match) The search begins at the root of the free RB-Tree (free_vmap_area_root). Because the tree is augmented, every node knows the max_size of the largest free block in its subtrees. find_vmap_lowest_match uses get_subtree_max_size() to instantly skip entire branches of the tree that do not contain a block large enough to satisfy the requested size and alignment. It traverses leftward whenever possible to ensure it grabs the lowest available memory address.

  2. Carving the Memory (va_clip) Once a suitable free vmap_area block is found, va_alloc is called to reserve the space, which in turn calls va_clip. The free block must be trimmed to exactly match the requested allocation. The way the tree is modified depends on how the allocation "fits" into the free block:

    • FL_FIT_TYPE (Full Fit): The allocation exactly matches the size of the free block. unlink_va_augment() is called to completely remove the node from the RB-Tree using rb_erase_augmented().
    • LE_FIT_TYPE or RE_FIT_TYPE (Edge Fit): The allocation sits at the exact start or end of the free block. The free block's boundary is simply shrunk. augment_tree_propagate_from() is then called to walk up the tree and update the augmented "max size" values for parent nodes.
    • NE_FIT_TYPE (No Edge Fit): The allocation sits right in the middle of a larger free block. The free block is split into two remainders (left and right). The original node is resized to become the right remainder, and a brand new vmap_area is allocated and inserted into the RB-Tree using insert_vmap_area_augment() to represent the left remainder.

2. Setting Up the Page Tables: vmap_pages_range

Once a virtual area is secured by alloc_vmap_area and physical pages are allocated (e.g., via the Buddy Allocator), the kernel must update the page tables so the CPU's MMU can translate the virtual addresses to physical ones.

Figure 1: Page Table translation mapping virtual page table entries (PTEs) to disparate physical pages in main memory.
Figure 1: Page Table translation mapping virtual page table entries (PTEs) to disparate physical pages in main memory.

The Page Table Manipulation

The function vmap_pages_range (historically map_vm_area) [2] iterates over the requested virtual address range and updates the page table entries step-by-step:

  1. PGD / P4D: Updates the Page Global Directory and Page 4th-level Directory.
  2. PUD: Updates the Page Upper Directory.
  3. PMD: Updates the Page Middle Directory.
  4. PTE: Writes the physical page frame numbers into the Page Table Entries and marks them as PRESENT.
Loading diagram...

Explanation

  1. Initiation (vmalloc to vmap_pages_range) The vmalloc() function, having already secured the virtual address block and allocated physical pages, calls vmap_pages_range(). It passes the starting virtual address and the array of allocated physical pages to begin linking them in the hardware page tables.

  2. The Nested Multi-Level Page Table Walk The kernel uses a nested set of loops to traverse the hardware page table hierarchy top-to-bottom. Each function resolves its respective directory level and calls the next function down the chain:

    • PGD Walk: The walk begins at the Page Global Directory and calls vmap_pages_p4d_range() to handle the Page 4th-level Directory.
    • P4D Walk: vmap_pages_p4d_range() steps through the P4D entries and calls vmap_pages_pud_range().
    • PUD Walk: vmap_pages_pud_range() steps through the Page Upper Directory and calls vmap_pages_pmd_range().
    • PMD Walk: vmap_pages_pmd_range() steps through the Page Middle Directory and calls vmap_pages_pte_range().
    Note

    Why the nested loops? The hardware page table is not a single flat array, but a sparse, hierarchical tree (e.g., a 4-level or 5-level tree on x86_64). This tree design saves massive amounts of physical memory because the kernel only allocates intermediate directory tables for virtual address ranges that are actively being used. The nested loops ensure that as a large virtual address range is mapped, the kernel correctly traverses this structure. If an allocation crosses a directory boundary (for example, spilling over a 2MB PMD boundary into the next PMD), the loops gracefully step back up, shift into the next directory, allocate any missing intermediate tables (pud_alloc, pmd_alloc, etc.), and seamlessly continue populating the leaf PTEs.

  3. Writing the Physical Frames (vmap_pages_pte_range) At the lowest level of the page tables, vmap_pages_pte_range() performs the actual mapping. It takes the physical page frame numbers (PFNs) from the allocated physical pages and writes them directly into the Page Table Entries (PTEs). These entries are marked with the appropriate protections and flagged as PRESENT so the CPU's MMU can translate them.

  4. TLB Flushing and Completion After the PTEs are updated across the requested virtual range, a TLB flush might be necessary to invalidate any stale cached translations for these virtual addresses across the system's CPUs. Once complete, vmap_pages_range() returns 0 (Success) back up the call chain to vmalloc().

Important

Performance Hit: Because vmalloc requires altering page tables and potentially flushing the Translation Lookaside Buffer (TLB) globally, it is considerably slower than kmalloc. It must only be used when large allocations are necessary, or when physical contiguity isn't strictly required.

3. Per-CPU Virtual Memory: pcpu_get_vm_areas

The per-CPU allocator heavily relies on the vmalloc subsystem to ensure each CPU gets its own distinct memory chunks.

How it works

When the per-CPU allocator initializes or expands, it needs to map identical virtual chunks backed by different physical pages for each CPU.

The function pcpu_get_vm_areas [3] is used to allocate multiple, disjoint vmalloc areas simultaneously. This ensures that the per-CPU areas for all processors remain aligned and share identical characteristics within the virtual address space.

CharacteristicExplanation
Who uses itThe per-CPU allocator (mm/percpu.c / mm/percpu-vm.c)
Why is it neededTo allocate an array of synchronized virtual memory blocks across all CPU nodes
How it searchesIt finds a large enough gap in the RB-Tree and carves out exactly matched slices for every CPU in the system.

The Congruent Offset Model

Unlike a regular vmalloc allocation which reserves a single contiguous virtual region, pcpu_get_vm_areas must reserve multiple virtual regions simultaneously - one for each CPU group - such that the relative offsets between them are identical. This is critical: the per-CPU allocator computes a per-CPU variable's address by adding a fixed offset to a per-CPU base pointer. If the virtual regions were placed at arbitrary locations, these offsets would break.

The caller passes in two arrays - offsets[] and sizes[] - that describe the layout template. Each entry represents one CPU group's virtual region. For example, on a 2-group NUMA system:

ParameterGroup 0Group 1
offsets[i]0x00000x8000
sizes[i]0x40000x4000

The allocator's job is to find a single base address such that base + offsets[0] through base + offsets[0] + sizes[0] and base + offsets[1] through base + offsets[1] + sizes[1] all fall within free virtual address space.

Note

Why allocate from the top? Regular vmalloc allocations grow upward from VMALLOC_START. Per-CPU areas are allocated from the top of the vmalloc space (near VMALLOC_END) downward. This deliberate separation avoids fragmentation conflicts between the two subsystems - they grow toward each other from opposite ends.

Loading diagram...

Design Insights

After validation (alignment, no overlaps, last_end fits within VMALLOC_START–VMALLOC_END), the algorithm pre-allocates vas[] (vmap_area pointers) and vms[] (vm_struct pointers) from their respective caches. The core challenge is then finding a single base address where every area fits in free space simultaneously.

The top-down scan solves this with a reverse circular loop: starting from the highest free block (pvm_find_va_enclose_addr(vmalloc_end)), it iterates through all areas in reverse order, pulling the candidate base downward (pvm_determine_end_from_reverse() / rb_prev()) whenever an area overflows or underflows its enclosing free block. A term_area bookmark is reset on every base adjustment - when the loop completes a full cycle back to term_area without any adjustment, all areas fit and the scan succeeds.

Once a valid base is found, the algorithm reuses the same va_clip() function from Section 1 (under the free_vmap_area_lock spinlock) to carve each area out of the free RB-Tree. After carving, each vmap_area is inserted into the busy tree of its vmap_node via addr_to_node(), and setup_vmalloc_vm() initializes the corresponding vm_struct with the area's address, size, and VM_ALLOC flags.

alloc_vmap_area vs pcpu_get_vm_areas

Both functions operate on the same global free RB-Tree (free_vmap_area_root) and share va_clip() for carving, but they differ in fundamental ways:

alloc_vmap_areapcpu_get_vm_areas
Search directionBottom-up (from VMALLOC_START)Top-down (from VMALLOC_END)
Blocks allocatedSingle contiguous blockMultiple congruent blocks
Commit conditionOne block fitsAll blocks fit simultaneously
Tree functionfind_vmap_lowest_match()pvm_find_va_enclose_addr() + reverse scan
Carvingva_clip()va_clip() (identical)
Note

Error recovery: If the scan underflows below VMALLOC_START, the overflow path calls reclaim_and_purge_vmap_areas() to flush lazily freed regions back into the free tree, re-allocates consumed vas[] entries, and retries the scan. A second failure returns NULL. If va_clip fails mid-carve, the recovery path rolls back already-carved areas via merge_or_add_vmap_area_augment().

References

Newsletter

Subscribe

I'll send you an email whenever I publish a new post. Unsubscribe at any time.