First-Touch Costs in Demand-Paged Memory

Allocating memory and using memory are two separate costs, and only the second one is large. The allocator hands out virtual address space immediately; physical memory arrives later, one fault at a time, as the program touches the space. Measured across a run, the faults dominate. A program that allocates a large buffer and writes to each page pays a per-page cost that can exceed everything else it does with the buffer, and that cost is charged to the code performing the first write rather than to the allocation that made it necessary.

The mechanism that produces this split is demand paging with a shared zero page, and its details determine how expensive the first touch is, how much of the cost can be amortised, and why the same code can show very different costs depending on whether transparent huge pages are active.

The zero page and the copy-on-write fault

Anonymous memory obtained through mmap with MAP_ANONYMOUS | MAP_PRIVATE, or through a heap grown by brk, is not backed by physical frames at the time of the call. The kernel records a virtual memory area describing the range and returns. The page tables for the range contain either no entries or entries pointing at a single read-only zero page shared by every process on the system.

A read of an untouched page is answered from the zero page. The page table entry delivers 4 KiB of zeroes, no frame is allocated, and the fault is handled quickly because nothing needs to be written. This is why calloc and fresh mappings can appear free when they are read rather than written: reading zeroes is cheap, and large regions of zeroes are the common case for freshly mapped memory.

A write is different. The page table entry is read-only, so the write faults. The kernel allocates a frame, zeroes it, copies nothing, and installs a writable entry pointing at the new frame. This is the copy-on-write path that anonymous memory shares with process forks. From the program’s point of view the write completes and the instruction retries; from the kernel’s point of view a frame allocation, a 4 KiB zeroing, a page table update, and possibly a TLB invalidation have occurred.

The accounting is revealing: the kernel reports these as minor faults, and getrusage exposes the count as ru_minflt. A minor fault is one that does not require I/O. It is still expensive. Frame allocation touches the per-CPU page lists and the zone allocator; zeroing writes 4 KiB, which is 64 cache lines of stores; the page table update may require allocating intermediate levels. The total is commonly in the low thousands of cycles per page on current hardware, and it also evicts useful cache and TLB content.

Why the fault is charged to the wrong place

The cost lands on the first store, which is frequently an initialisation loop that looks trivial. Zeroing a 1 GiB buffer appears to be a memcpy of zeroes; in fact it is a quarter of a million faults, each with its own overhead. A profiler that samples the instruction pointer will attribute the time to the store instruction, not to the allocation, and a developer reading the profile will see an unexpectedly hot loop that writes zeros.

The reverse attribution is equally misleading in the other direction. Code that allocates memory and never touches it appears cheap, and does consume address space, page table pages, and kernel bookkeeping in proportion to the range size. A long-running program that leaks unmapped-but-mapped regions eventually exhausts vm.max_map_count, whose default on many Linux systems is 65530 mappings, and starts failing allocations with ENOMEM despite free memory.

There is no way to make the kernel account the fault to the allocating call, because the allocation and the touch can be arbitrarily far apart and can occur on different threads. The practical consequence is that measurement must count faults explicitly rather than infer them from profiles.

Amortising the cost across a buffer

Given a per-page fixed cost, total first-touch cost is proportional to the number of pages touched, not to the number of bytes used inside each page. Several strategies follow.

Touching one byte per page and spreading the real work over the pages that have already been faulted does not help unless the program avoids touching the rest. The relevant strategy is to make each fault cover more memory, which is what huge pages do, or to reuse memory that has already been faulted, which is what pooling does.

Reuse is the cheaper fix when it applies. A buffer pool that allocates once and hands the same regions back repeatedly pays the fault cost once per region for the lifetime of the process. The allocator tier structure described in The Cost Tiers of a Single Allocation Request already provides reuse of small chunks; pool reuse extends the idea to buffers large enough that each one would otherwise be a fresh mapping. The catch is that reuse moves the cost elsewhere: a pool whose total footprint exceeds what the program actually needs pays memory for capacity it does not use, which is a footprint decision made against a fault-count decision.

Transparent huge pages and the granularity of a fault

On x86-64, a page table entry can map either a 4 KiB page or a 2 MiB huge page, and with a third level, a 1 GiB page. Mapping at 2 MiB moves 18 bits from the page offset into the page number, which shrinks the page table and lets a single TLB entry cover 512 times more memory. For a program with a large contiguous footprint, that reduction in TLB entries is often worth more than the fault amortisation.

Transparent Huge Pages make the kernel attempt this automatically for anonymous memory. The behaviour is controlled by /sys/kernel/mm/transparent_hugepage/enabled, which accepts always, madvise, or never, and by defrag. In always mode, a fault on an anonymous range may be satisfied by allocating a 2 MiB huge page, which requires finding 512 contiguous free 4 KiB frames and may involve compaction. In madvise mode, huge pages are only used in ranges that the program has marked with madvise(MADV_HUGEPAGE), which gives the program control over which allocations are worth the defragmentation cost.

The trade is direct. A huge page turns up to 512 faults into one and removes up to 512 TLB entries, at the cost of allocating and zeroing 2 MiB at once even when the program touches only the first page of it. For a program that allocates a large buffer and fills it, that is a clear win. For a program that allocates many large-ish buffers and touches a small part of each, it is a loss: internal fragmentation of up to 2 MiB per buffer, plus zeroing that no one uses.

The fault count for a touched buffer shows which regime the kernel chose:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/resource.h>

static long flt(void) {
    struct rusage ru;
    getrusage(RUSAGE_SELF, &ru);
    return ru.ru_minflt + ru.ru_majflt;
}

int main(void) {
    const size_t n = 256u << 20;              /* 256 MiB */
    char *p = malloc(n);
    if (!p) return 1;
    long a = flt();
    memset(p, 0, n);                          /* faults here, not in malloc */
    long b = flt();
    free(p);
    /* With 4 KiB pages expect about n / 4096 = 65536 faults;
       with 2 MiB huge pages expect about n / (2 << 20) = 128. */
    printf("faults during fill: %ld\n", b - a);
    return 0;
}

The count distinguishes the two regimes without any special instrumentation, and the two expected values differ by a factor of 512. Note that memset is doing the same work in both cases; only the bookkeeping behind each store differs.

Faults that are not anonymous

The discussion above covers anonymous memory. A mapping of a file with MAP_SHARED or MAP_PRIVATE faults into the page cache instead, and the fault may require reading from the file’s backing store if the page is not cached. Those are major faults, counted separately, and they involve I/O. A MAP_POPULATE flag asks the kernel to fault in the whole mapping at mmap time, which converts many small faults into one larger operation and is useful for a mapping that will be fully traversed immediately.

File-backed faults and the page cache’s role in avoiding them belong to the I/O side of the model rather than the memory side, but the same accounting principle applies: the cost appears where the first access happens, and the number of faults, not the number of bytes, sets the scale.

Reducing faults without adding memory pressure

The cheapest fault is the one never taken, and the cheapest way to avoid one is to write to memory that is already resident. This is why allocation and initialisation should be considered together rather than in isolation: allocating a buffer in one phase and filling it in another guarantees the faults happen in the fill phase, which may be the wrong phase to pay them in. A cache warmup that touches pages ahead of the latency-sensitive path moves the cost out of the path, which is exactly the kind of deliberate placement that Allocation Churn and the Locality of Recycled Memory exploits when reuse comes from the same thread.

The second cheap fault is the one avoided by not shrinking the usable page. A program that allocates a buffer of 4 KiB plus 1 byte touches two pages, and the second page is 4095 bytes of waste that still costs a frame and a fault. Rounding buffer sizes to page multiples that are allocated and released together avoids that class of waste, and it is measurable as a fault count, not as a byte count.