VMA and Maple Tree: How Address Ranges Are Established, Changed, and Accessed Concurrently

Changing only the middle page of a three-page mapping to read-only may result in two additional entries in maps; after unmapping the middle page, the resulting hole differs from PROT_NONE. Below, we track how the range changes around the same three-page address space, and then explain how concurrent lookups protect these changes.

1. VMA Describes the Range, Page Tables Describe Current Translations Within the Range

A standard VMA covers a half-open interval [vm_start, vm_end), including the start but excluding the end. Normal VMAs within the same mm_struct do not overlap; threads sharing the address space typically share references to this mm, so one thread's mprotect changes the mapping permissions seen by other threads.

Manual Calculation: Where in the File Does an Address in VMA Map?

Let the base page size be P, the mapping start at address A, and vm_pgoff=8. For address A + 2P + 17, locate it in two steps:

1. The mapping starts at the 8th base page of the file; advancing 2 pages leads to the file's 10th page.
2. Keep the page offset of 17; the file byte offset is 10P + 17.

The unit of vm_pgoff is base pages, not bytes; it does not advance with subsequent read/seek operations on this file descriptor.

A MAP_PRIVATE file VMA can simultaneously cover unmodified file cache pages and already separated anonymous COW pages after a write, so vm_file != NULL does not mean "every dirty page will be written back to this file." Ordinary shared anonymous mappings may also be backed by shmem file objects in the kernel; the user flag MAP_ANONYMOUS and whether the internal vm_file is null do not have a simple one-to-one correspondence.

2. Deducting Four Operations Using a Three-Page Mapping

mmap: Establishing a Commitment in the Address Space First

Ordinary non-fixed mmap can provide address hints. The kernel selects an available range without overwriting existing mappings, performs checks on permissions, file capabilities, offsets, resource limits, etc., and establishes the mapping. If the new region meets merge conditions with neighbors, it may directly expand an existing VMA, so the statement "one mmap creates a permanently identifiable VMA object" is not always true.

MAP_FIXED has a different meaning: it requires using the specified range and can replace existing mappings. It is not a harmless strong version that fails gracefully on ordinary hints. If the goal is "only occupy if this address range is completely free," one should understand MAP_FIXED_NOREPLACE and return address checks; do not read maps to see a hole and then assume no one else occupies it while using MAP_FIXED.

Usually, data pages are created on demand, but paths like MAP_POPULATE, locking/prefetching requirements, and device mappings may perform additional work. File mmap establishment connects via relevant interfaces in file_operations; callbacks like fault in vm_operations_struct are used for subsequent mapping operations; one cannot invent a generic vm_ops->mmap() and claim all files call it. See mmap(2).

mprotect: Why Changing One Page Adds Two Description Objects

Assume [A,A+3P) was originally read-write. After changing [A+P,A+2P) to read-only, these three segments no longer share the same attributes. The original single VMA cannot faithfully describe them, so it needs to be split into front, middle, and back segments. The kernel must also apply permission changes to existing page tables and maintain the TLB as required; parts without resident pages are constrained by the new VMA semantics for future page faults.

This explains an apparently anomalous failure: even if no additional data memory is requested, mprotect may fail due to the need for more VMA metadata or exceeding mapping count limits. Merely "changing one bit in the PTE" cannot explain this phenomenon. After restoring the middle page to read-write, compatible adjacent segments may merge again, but merging also checks backing objects, offset continuity, anonymous reverse mapping relationships, and other attributes; one cannot simply compare the four characters rw-p displayed in maps. See mprotect(2).

munmap: Unmapping Removes the Mapping, Not Necessarily the Data Itself

After unmapping the middle page, the middle becomes a true hole. Compared to simply prohibiting access, it changes the occupation relationship of the address space:

munmap also tears down translations and releases corresponding references; this step does not directly determine the final lifetime of data pages.

If a page is shared by another process, or if ordinary file pages are still in the page cache, unmapping the current process's mapping does not directly turn them into buddy free pages. Conversely, when physical pages have been reclaimed and swapped out, valid VMAs can still exist. VMA lifetime, page table entry lifetime, and data page lifetime must be reasoned about separately.

mremap: Addresses Can Change, Data Need Not Be Byte-for-Byte Copied

When expanding a mapping, if adjacent ranges are unavailable, a movable mremap can choose a new location and move page table mappings and other states. It can avoid copying some user data, but there are still metadata, page table, and invalidation costs, and not all mappings can be moved arbitrarily. After a successful move, old addresses and any absolute self-referencing pointers stored within them need to be handled according to application design; "content is still there" does not mean "all original pointers remain valid."

Putting the three lifetimes in the same view: read the central page first, then unmapping it, and see which ranges, PTEs, and caches truly disappear. Restoring mappings and restoring access permissions can also be done separately.

$$file\_offset=Pvm\_pgoff+(a-vm\_start)$$

This formula is used for file addresses within this VMA; a must first satisfy range and access conditions; holes do not participate in calculation.

3. Runnable Experiment: Directly Observing These Boundaries

Below, we reserve five pages of PROT_NONE space, use the middle three pages for experiments, and use the sides as address boundaries. At each step, read /proc/self/maps to verify the attributes of the specified address; do not write to read-only pages' addresses, nor cause process crashes.

#define _GNU_SOURCE
#include <assert.h>
#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <sys/mman.h>
#include <unistd.h>

static int permission(uintptr_t address, char output[5]) {
    FILE *file = fopen("/proc/self/maps", "r");
    assert(file != NULL);
    char line[1024];
    int found = 0;
    while (fgets(line, sizeof(line), file)) {
        uintptr_t start, end;
        char mode[5];
        if (sscanf(line, "%" SCNxPTR "-%" SCNxPTR " %4s",
                   &start, &end, mode) == 3 &&
            start <= address && address < end) {
            memcpy(output, mode, 5);
            found = 1;
            break;
        }
    }
    assert(fclose(file) == 0);
    return found;
}
static void check(unsigned char *base, size_t page,
                  const char *middle) {
    for (size_t i = 0; i < 3; ++i) {
        char mode[5] = "";
        int found = permission((uintptr_t)(base + i * page), mode);
        const char *expected = i == 1 ? middle : "rw-p";
        if (expected) {
            assert(found && strcmp(mode, expected) == 0);
        } else {
            assert(!found);
        }
        printf("page %zu: %s\n", i, found ? mode : "hole");
    }
}
int main(void) {
    long size = sysconf(_SC_PAGESIZE);
    assert(size > 0);
    size_t page = (size_t)size;
    unsigned char *whole = mmap(NULL, 5 * page, PROT_NONE,
                               MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    assert(whole != MAP_FAILED);
    unsigned char *base = whole + page;
    assert(mprotect(base, 3 * page, PROT_READ | PROT_WRITE) == 0);
    puts("Initial:"); check(base, page, "rw-p");
    assert(mprotect(base + page, page, PROT_READ) == 0);
    puts("Middle page read-only:"); check(base, page, "r--p");
    assert(mprotect(base + page, page, PROT_READ | PROT_WRITE) == 0);
    puts("Permissions restored:"); check(base, page, "rw-p");
    assert(munmap(base + page, page) == 0);
    puts("Middle page unmapped:"); check(base, page, NULL);
    assert(munmap(whole, 2 * page) == 0);
    assert(munmap(whole + 3 * page, 2 * page) == 0);
}

Compile with cc -std=c11 -Wall -Wextra -Werror vma-demo.c -o vma-demo, without -DNDEBUG. Checks are location-based by address; do not assume actual VMA boundaries exactly equal mmap request boundaries, nor force-assert that the kernel chooses a specific merge layout after restoring permissions. maps presents VMA attributes; one cannot assert that the middle three pages have actually allocated physical pages based on this.

4. Maple Tree Solves the Range Organization Problem

Address spaces need to answer various queries: which mapping does this address fall into, where is the next mapping, which VMAs intersect with a certain interval, and where are there large enough holes to place new mappings. The old implementation used a collaboration of red-black trees and linked lists; Maple Tree uses a range-oriented multi-branch structure and iteration interfaces to undertake this work, providing benefits in reducing tree height, improving locality, and maintaining range information.

First clarify how many results a query needs to return, then discuss the tree's benefits:

Maple Tree improves tree height, locality, and range organization; deletions and traversals spanning many mappings still incur work proportional to the scale of involved objects.

VMAs use half-open intervals. When Maple Tree range interfaces use inclusive end index ranges, they are correspondingly expressed as [vm_start, vm_end-1]. The values are VMA pointers; range boundaries are used to determine search direction. Node types, slot counts, and pivot layouts are implementation details; the tree does not consume a fixed 9 bits of the address at each level like a page table, nor can one invent a fixed address coverage table for Maple Tree based on page table hierarchy.

Storing hole information allows allocation searches to skip subtrees that cannot possibly accommodate the request, without trying every byte sequentially. For example, when 4P of contiguous virtual space is needed, 8P of total free space may still consist of multiple 1P holes; the range index needs to find a single segment long enough. This is virtual address fragmentation, which is a different problem from buddy system fragmentation where no contiguous physical pages are found. See Maple Tree Design and API.

"Finding the Successor" Does Not Equal "Address is Covered"

Some lookup interfaces allow returning the next VMA within a hole. Taking the common contract of find_vma(mm, address) as an example, the result can be the first VMA with vm_end > address; if address < vm_start, the address is still in a hole. The caller must judge coverage according to interface semantics and cannot simply judge based on non-null return. When only exact coverage is needed, choose the corresponding interface and adhere to its locking requirements.

Stop the probe at the interval end and in the hole, comparing "which candidate is returned" with "whether the candidate covers." The end boundary does not belong to the original range.

5. Why Reading the Tree, Locking VMA, and Locking Page Tables Cannot Be Combined into One Lock

Consider thread R faulting at address A, while thread W simultaneously executes munmap on A. After R obtains the VMA pointer from the tree, if W removes the range and reclaims the object, R accessing fields later may cause use-after-free. Even if RCU delays object reclamation, the start, end, and backing object R reads must still form a stable state allowing current page fault processing.

Three Layers of Protection, Each Stabilizing Different Objects

rmap-related locks also serve reverse lookup of mappings from pages. Supported page fault paths can try per-VMA schemes; if guarantees cannot be established, fall back to broader coordination paths; obtaining a read lock on one layer does not automatically grant write permissions on another.

When Contention Occurs: Retry on Validation Failure

Reader R first finds the candidate, attempts to stabilize the VMA and validate the address; writer W obtains exclusive rights according to protocol before revoking the range. If R cannot establish the required guarantees, it retries or adopts the more conservative mm-level lock path.

Time-consuming I/O may also require releasing and re-acquiring locks and re-validating. During the wait, the previously established "address is still within this VMA" may have changed; old lookup results cannot be directly continued.

Maple Tree's RCU capabilities only solve part of this: concurrent safety of traversing nodes does not automatically prove data objects remain unchanged long-term, nor does it mean all writers copy the entire tree before replacing. Currently supported architectures already have per-VMA page fault paths; it cannot be written off as a distant future; but one also cannot claim mmap_lock has disappeared. Lock contracts can be found in Process Addresses; target kernels can locate entry points such as lock_vma_under_rcu().

6. Finally, Connecting Page Fault Handling Back to This Model

For the same write protection exception, the handling result depends on software semantics:

Hardware reports phenomena; VMA and backing state determine interpretation. handle_mm_fault() is therefore not a unified action of "finding a range and allocating a page."

Even if the VMA is legal, file mapping access beyond the backend file's valid range may generate SIGBUS; allocation failures, special mappings, and swapping in have their own handling results. handle_mm_fault() therefore cannot be generalized as "finding a VMA and allocating a new page." It may reuse page cache, handle swapping in, separate private pages, or refuse access according to operation contracts.

When troubleshooting, first use maps to judge ranges and permissions, then use smaps/smaps_rollup to distinguish resident and shared usage, and finally combine faults, I/O, and memory pressure to locate costs. A large number of mmap/mprotect calls may increase VMA count and metadata overhead; but a long maps file does not independently prove it is a performance bottleneck. Issues on the physical allocation side connect to Physical Memory Management; how resident pages are reclaimed connects to Page Reclaim and Swap.