Demand Paging and the First-Touch Fault

mmap of a hundred megabytes returns in microseconds. No frames are allocated, no data is read from disk, and no page-table entries below the top level are necessarily created. The mapping is a promise: the address range is now valid, and the kernel has recorded what should happen when each page in it is touched. Keeping that promise is the job of the fault handler, and the handler’s work is where the cost of memory actually lands.

The Fault Path

A page fault is an exception raised by the processor when a translation cannot be completed or when the access violates the permissions recorded in a completed translation. The processor pushes the faulting address into a register and the faulting instruction’s address onto the stack, then transfers control to a handler the kernel registered at boot. The handler runs with the faulting process’s address space still active, which is what allows it to inspect and modify that address space directly.

The handler’s first job is classification, and there are three outcomes it must distinguish.

A minor fault means the page is not mapped but its contents are available without I/O. The canonical case is anonymous memory that has never been written: the kernel installs a mapping to a shared zero-filled frame, marks it read-only, and returns. The read succeeds, the write faults again, and this second fault allocates a private frame, copies the zero page into it, and restores write permission. This two-step dance is why the first write to a fresh page is more expensive than the first read, and why a program that only reads its fresh anonymous memory never consumes physical memory at all.

A major fault means the contents must be fetched from backing storage. For a file-backed mapping the kernel locates the page in the page cache; if it is absent, it issues a read and blocks the faulting thread until the read completes. The fault latency is then a storage latency, which is why the first pass over a large file-backed mapping is dominated by I/O and subsequent passes are not.

A permission fault means a valid translation exists but the access is not allowed. Write to a read-only mapping, execute from a non-executable one, or access from user mode a page whose entry is marked supervisor-only. The handler decides whether the condition is legitimate: a copy-on-write write becomes a private copy, while a write to a genuinely read-only file mapping raises SIGSEGV.

/* Sketch of the classification a handler performs; helper names are local. */
enum fault_result handle_fault(uintptr_t addr, int write, int exec)
{
    struct vma *v = find_vma(current->mm, addr);
    if (!v)
        return FAULT_SIGSEGV;              /* no mapping covers this address */

    if (exec && !(v->prot & PROT_EXEC))
        return FAULT_SIGSEGV;

    pte_t *pte = walk_to_leaf(current->mm, addr);
    if (pte && pte_present(*pte)) {
        if (write && !pte_writable(*pte))
            return is_cow(*pte) ? FAULT_BREAK_COW : FAULT_SIGSEGV;
        return FAULT_SIGSEGV;             /* protection violation, not a hole */
    }
    return v->file ? FAULT_FILE : FAULT_ANON;
}

The two non-fatal results are starting points, not final answers. A FAULT_FILE fault may still be served without I/O if the page is already in the page cache, and a FAULT_ANON fault on a page that was previously swapped out requires a read from swap. The major/minor distinction is decided after this classification, not by it.

The distinction between “no mapping” and “mapping exists but page absent” is the one that a naive implementation gets wrong. Without it, a wild pointer and a legitimate first touch are indistinguishable, and the kernel cannot decide between delivering a signal and allocating a frame.

The Zero Page and Why Anonymous Memory Is Cheap Until Written

Every process’s fresh anonymous memory initially maps to one physical frame filled with zeros, shared read-only across the system. Reading a hundred megabytes of freshly allocated buffers therefore consumes one frame of physical memory, not a hundred megabytes. This is not an optimization bolted on afterwards; it falls out of the combination of demand paging and copy-on-write, and it changes the economics of programs that allocate generously and use sparsely.

The zero page has a security role as well. A frame handed to a process must not contain data from a previous owner. Zeroing every frame at allocation is a cost proportional to the memory handed out; mapping a pre-zeroed frame and copying only on write makes the cost proportional to the memory actually written. The second is cheaper and equally safe, provided the copy is made before the write becomes visible, which the fault mechanism guarantees because the write cannot complete until the handler returns.

There is a limit to the trick. A process that writes every page it allocates pays a fault and a copy per page, which is more work than an eager allocation would have been. The trade is favourable for the common pattern of allocate-large, use-small, and unfavourable for the pattern of allocate-and-fill, where the fault overhead is pure loss. Allocators that hand out large blocks sometimes touch the pages themselves to move the cost to a predictable point, which trades latency at an unpredictable moment for latency at a chosen one.

Prefaulting and the Cost of Being Wrong

Because faults are expensive relative to ordinary accesses, mechanisms exist to populate mappings ahead of use. MAP_POPULATE asks the kernel to fill in the page tables at mmap time, turning a series of later faults into a single call. Explicit advice calls let a program tell the kernel that a range will be needed soon. Read-ahead in the file-backed case does the same thing implicitly, fetching several pages per fault because the access pattern suggests sequential use.

All of these are predictions, and predictions can be wrong. Prefaulting a range that is never touched converts a free mapping into allocated memory and, for file-backed pages, into I/O that delays the call. Read-ahead past the end of a useful region wastes bandwidth and pollutes the page cache with pages that will be evicted unused. The readahead window is therefore adaptive in most kernels: it grows while accesses remain sequential and collapses on the first non-sequential access, which keeps the cost of a wrong guess bounded to a few pages rather than a few megabytes.

The interaction with the translation cache matters here. A prefaulted range still has to be translated on first access, and each distinct page costs a translation-cache miss regardless of whether the frame was already resident. Prefaulting removes the fault but not the walk, so the benefit is the difference between a fault plus a walk and a walk alone. That difference is large but not the whole cost, which is why prefaulting alone does not make a large sequential scan cheap; the mapping granularity has to change too, as described in large pages and TLB coverage.

What the Handler Must Not Do

The fault handler runs in a context where blocking is possible but expensive, and where re-entering the fault path is a hazard. A handler that takes a lock protecting the address space and then faults on the lock’s own memory deadlocks. A handler that copies data to or from a user buffer using ordinary user-space accesses can fault recursively. Kernels therefore use non-faulting copy routines in the fault path, and the address-space lock is designed so that the fault path can acquire it without touching memory that might itself be unmapped.

Signals add a second layer. When a fault is fatal, the kernel must deliver SIGSEGV to the faulting thread, which requires building a signal frame on the thread’s stack. If the stack itself is unmapped or the fault occurred while the stack pointer was invalid, the delivery cannot proceed and the kernel must terminate the process without a handler. The same problem appears with stack growth: an access below the current stack limit is a legitimate growth request, but only within a bounded distance, and a program that jumps far past the guard page gets a signal rather than a grown stack. The rules that decide where the stack ends are part of the mapping bookkeeping rather than the fault mechanism itself.

Finally, the handler must be idempotent with respect to concurrent faults. Two threads touching the same unmapped page at once both fault; the first to acquire the lock allocates and installs the entry, and the second must observe the installed entry and return without duplicating the work. Kernels handle this by re-checking the entry after taking the lock, which is why the classification in the sketch above happens twice: once optimistically, once under the lock.

Fault Counts as a Diagnostic

The kernel exposes per-process counts of minor and major faults, and the two numbers tell different stories. A high minor count with a low major count means the process is growing its resident set from memory-resident data: allocation, copy-on-write, and stack growth. A high major count means it is waiting on storage, and the ratio of major faults to elapsed time is a direct measure of how much of the run was spent in I/O.

Neither number is a defect on its own. A program that touches a large file once will have a major fault per page and that is the intended behaviour. The diagnostic value comes from the comparison against expectation: a process that maps a file and reads it repeatedly should show major faults only on the first pass, and a process that shows them on every pass is either re-mapping the file or losing its pages to eviction, which is the subject of the clock algorithm and second-chance replacement.