How Virtual Memory Works and What Your OS Is Hiding From Your Program

How Virtual Memory Works and What Your OS Is Hiding From Your Program

Every program you have ever written has been lied to. Not maliciously, and not in a way that causes you harm. But from the moment your program starts running to the moment it exits, the operating system is maintaining an elaborate fiction about the nature of memory, and your program has no idea.

The fiction is this: your program believes it has access to a large, flat, contiguous address space that belongs entirely to it. On a 64-bit system, that address space is theoretically 16 exabytes. Your program can read from address 0x1000, write to address 0x7fffffffe000, and jump to code at address 0x400000, and it does so with the complete confidence that those addresses are real, that the memory at those addresses is yours, and that nothing else is touching it.

None of that is true in the way your program thinks it is. The addresses are not real physical memory addresses. The memory is not necessarily yours in the sense of being physically reserved. Other programs are running in what appears to be the same address space but is not. The OS is intercepting every single memory access and translating it, in hardware, before your program sees the result.

Understanding how this works is not just an academic exercise. It explains behavior that is otherwise confusing: why processes are isolated from each other, how memory mapped files work, what a page fault actually is, why malloc does not immediately consume RAM, how copy-on-write makes fork fast, what a segmentation fault really means at the hardware level, and why certain access patterns are dramatically slower than they should be.

The problem virtual memory solves

To understand why virtual memory exists, you need to understand the world before it. In the early days of computing, programs ran directly on physical memory. A program was loaded at some physical address, and it used physical addresses to access its data. This created several serious problems.

The first was relocation. If your program was written to run at physical address 0x1000, and something else was already loaded there, your program could not run. Every program had to be written to run at a specific location, or it had to be compiled with relocation in mind and then adjusted at load time, which was complex.

The second was isolation. If two programs were running simultaneously and sharing physical memory, there was nothing preventing one program from reading or writing the memory of the other. A bug in one program could corrupt another. A malicious program could read passwords out of another program's memory. The only security was trusting that programs were well-behaved.

The third was fragmentation. As programs were loaded and unloaded, physical memory developed holes. You might have 100 megabytes of free physical memory but no contiguous 50-megabyte region to load a program that needed 50 megabytes. The memory existed but was not usable.

The fourth was the mismatch between program needs and available RAM. A program might need more memory than the machine physically had. Without some mechanism to handle this, programs were simply limited to what physically existed.

Virtual memory was designed to solve all of these problems simultaneously. It does so by inserting an indirection layer between the addresses a program uses and the physical memory those addresses correspond to.

Pages and page tables

The fundamental unit of virtual memory is the page. A page is a fixed-size block of memory, typically 4096 bytes (4 kilobytes) on most systems, though some architectures support larger page sizes. All memory management in a virtual memory system happens at page granularity. You never map a single byte. You map a page, which means 4096 bytes all mapped together.

The data structure that records the mapping from virtual pages to physical pages is the page table. Every process has its own page table. The page table is a structure in physical memory, maintained by the operating system, that the hardware uses to translate virtual addresses to physical addresses.

When your program accesses a virtual address, the hardware does not use that address directly. Instead, it looks up the virtual page number (derived from the address) in the page table, finds the corresponding physical page number, combines that with the offset within the page, and produces the physical address that actually goes onto the memory bus.

A virtual address on a 64-bit system with 4KB pages breaks down like this: the bottom 12 bits are the page offset (since 2^12 = 4096, these bits index into the page). The remaining bits above that identify the virtual page number. The translation hardware looks up the virtual page number in the page table, retrieves the physical page number, and appends the original offset bits to form the physical address.

This translation happens for every single memory access. Every instruction fetch, every data load, every data store. The hardware does this transparently, in a few nanoseconds, without any involvement from your program. Your program issues a virtual address, and the physical address is what actually happens.

The translation lookaside buffer

If every memory access required looking up the page table, and the page table itself is in memory, every memory access would require at least one additional memory access just for the translation. That would roughly halve memory throughput. For most programs it would be far worse than halving, because page tables are hierarchical structures that require multiple lookups.

The solution is the Translation Lookaside Buffer, or TLB. The TLB is a small, fast cache built into the CPU that stores recent virtual-to-physical page mappings. When the hardware needs to translate a virtual address, it checks the TLB first. If the mapping is there (a TLB hit), the translation is done in a single cycle or two. If the mapping is not there (a TLB miss), the hardware has to walk the page table in memory, which takes many cycles, and then cache the result in the TLB for future use.

TLBs are small. A typical L1 TLB might hold 64 entries. An L2 TLB might hold a few hundred to a few thousand. Each entry covers one page, which is 4KB. A 64-entry TLB covers 256KB of address space with zero-cost translations. Code and data that fits within 256KB will have excellent TLB behavior. Code and data that is scattered across many pages will cause TLB misses and pay the page table walk cost repeatedly.

This is why TLB pressure is a real concern for performance-sensitive code. A program with a large working set, data scattered across thousands of pages accessed in no particular order, will spend significant time on TLB misses. Large pages (2MB or 1GB on x86-64, configured through huge pages on Linux) are one mitigation: each TLB entry covers far more memory, so the same TLB can cover a much larger working set without misses.

Hierarchical page tables

A flat page table would be straightforward but impractical. On a 64-bit system with 4KB pages, the virtual address space has 2^52 pages (ignoring the bits that are not used in practice). A flat array with one entry per page would itself be enormous, larger than the physical memory of most machines. And each process would need its own copy.

The solution is a hierarchical page table, also called a multi-level page table. Instead of a single flat array, the page table is a tree structure. The virtual page number is split into multiple parts, and each part indexes into a different level of the tree. Only the parts of the tree that are actually needed are allocated.

On x86-64, the current standard uses a four-level page table structure, with a fifth level available on newer processors for even larger address spaces. A virtual address is split into four 9-bit indices and a 12-bit page offset. The four indices index into four levels of page table directories. Each level of directory contains 512 entries (2^9). An entry at each level either points to the next level's directory or marks itself as absent.

The tree is sparse. For a typical process, most of the address space is unmapped. Only the regions that have been mapped (code, data, stack, heap, memory-mapped files) have entries in the tree. The directories covering unmapped regions do not need to exist. The kernel only allocates page table memory for the address space regions that actually exist.

When a process terminates, the kernel walks its page table and frees all the allocated directories. When a process forks, the kernel can share page table entries between parent and child (with modifications to support copy-on-write, which we will get to). The hierarchical structure makes both of these operations practical.

What happens when you access unmapped memory

Your program's address space contains many virtual addresses that are not mapped to any physical page. The stack has a bottom. The heap has a current limit. There are gaps between the code segment, the data segment, and the stack. Most of the theoretical 128 terabytes of usable virtual address space (on current x86-64 implementations) is unmapped.

What happens when your program attempts to access an unmapped address? The hardware attempts the page table walk and finds either a missing entry in one of the page table levels, or a page table entry marked as not present. The hardware raises an exception: a page fault. Control transfers from your program to the operating system's page fault handler.

The page fault handler examines the faulting address and the context of the access. It has several possible responses:

• If the address is simply invalid, not in any region that the process has legitimately mapped, the kernel sends a signal to the process. On Unix-like systems, this is SIGSEGV, the segmentation fault signal. By default this terminates the process and optionally produces a core dump. The error message "Segmentation fault (core dumped)" that every C programmer has seen is the result of this sequence: invalid memory access, page fault, kernel sends SIGSEGV, process terminates.

• If the address is in a legitimate region but the page is not currently in physical memory (because it was never loaded, or because it was swapped out), the kernel fetches the page from wherever it lives (disk, a file, a swap partition), allocates a physical page to hold it, updates the page table entry to point to that physical page and mark it present, and resumes the process from the faulting instruction. The process never knew anything happened. From its perspective, it issued a memory access and got back a result. The fact that the OS intervened and fetched data from disk is invisible.

• If the address is in a legitimate region and the page is present but the access violated the permissions on the page (for example, writing to a read-only page), the kernel again sends a signal. This is the basis for detecting certain bugs and for implementing copy-on-write, which we will discuss shortly.

Page faults are the mechanism through which the operating system maintains control over memory. Every unmapped or missing or protected page gives the kernel an opportunity to intervene, manage resources, enforce isolation, and implement features transparently.

Demand paging: memory that does not exist until you use it

When you call malloc and allocate a hundred megabytes, the C library might ask the kernel for that memory via the brk or mmap system call. The kernel grants the request and marks a hundred megabytes of virtual address space as belonging to your process. But it does not immediately allocate a hundred megabytes of physical RAM. The pages in that region are marked as reserved but not present. Physical memory is not assigned until your program actually touches a page.

When your program writes to the first byte of that region, a page fault occurs. The kernel sees that the fault is in a valid region, allocates one physical page (4KB), zeros it out, maps the virtual page to the physical page, and resumes your program. That one page is now in RAM. The other 99,999 pages in the hundred-megabyte allocation are still not in RAM, because you have not touched them yet.

This is demand paging. Memory is paged in on demand, as it is accessed. It is the reason that allocating a large buffer does not immediately consume RAM. It is the reason that a program can start up fast even if it has a large initialized data segment: the initialization happens lazily as pages are first touched.

Demand paging also means that the amount of physical RAM a process actually uses can be much less than the virtual address space it has mapped. A program that allocates a hundred-megabyte buffer but only uses ten megabytes of it consumes roughly ten megabytes of RAM, not a hundred. The kernel only has physical pages for what was actually touched.

The trade-off is that the first access to each new page incurs a page fault, which involves a kernel mode switch and some amount of work. For programs that allocate and then sequentially use large buffers, this is usually fine: the faults are amortized over a lot of useful work, and the kernel may even prefault pages when it can predict access patterns. For programs that have performance requirements and cannot tolerate unpredictable latency spikes, demand paging can be a problem, which is why there are system calls like mlock that force pages to be faulted in and pinned in physical memory.

Copy-on-write: how fork is not as expensive as it sounds

On Unix-like systems, the primary way to create a new process is fork. Fork creates a copy of the current process: same code, same data, same heap, same stack, same file descriptors. On a process with a gigabyte of resident memory, you might expect fork to take a while and consume another gigabyte of RAM. In practice, fork is fast and does not immediately consume the memory you expect.

The mechanism is copy-on-write. When fork is called, the kernel creates a new process with its own page table, but instead of copying all the physical pages from the parent, it makes the parent's page table entries read-only and shares the physical pages between parent and child. Both processes see the same physical memory, but neither can write to it. If either process tries to write, the hardware triggers a page fault because the page is marked read-only. The kernel's fault handler sees that this is a copy-on-write page, allocates a new physical page, copies the data from the shared page into the new page, updates the faulting process's page table to point to the new page with read-write permissions, and resumes execution. The other process still sees the original page, still read-only.

This means that fork is essentially free in terms of memory: it only copies page table entries and marks them read-only. The actual copying of physical pages happens lazily, only for pages that are actually modified. If the child process immediately calls exec to load a new program, none of the parent's pages ever get copied. The child's address space is replaced entirely, and the shared pages are simply discarded. This is why the fork + exec pattern, which is the standard way to launch programs on Unix, is efficient despite the apparent cost of copying an entire process.