Memory Management: Allocation, Paging, Segmentation

Before any software abstraction exists, physical memory (DRAM) is a flat, numbered array of bytes. The CPU has an address bus of a certain width — on a 64-bit machine, theoretically up to 2^64 addresses, though in practice x86-64 uses 52 physical address bits today. Each address points to one byte.

The BIOS/UEFI firmware tells the kernel (via structures like the E820 memory map) exactly which ranges of physical addresses contain usable RAM, which are reserved for hardware (like the PCI bus or BIOS ROM), and which might be faulty. When Linux boots, one of its first jobs is to walk this map and build a data structure representing all available physical memory.

The fundamental unit the kernel works with is a page frame: a fixed-size, power-of-two-aligned chunk of physical memory. On almost all architectures, the default page size is 4 KiB (4096 bytes). The kernel maintains a struct page for every single page frame in the system. On a machine with 8 GiB of RAM that's 2,097,152 page frames, and therefore over 2 million struct page objects. These are stored in a flat array called mem_map.

Think of physical memory as a giant parking lot. Each parking space (page frame) is 4 KiB. The kernel is the parking attendant, keeping a ledger of which spaces are occupied and by whom. The attendant doesn't care what the car looks like — a 'parking space' is a 'parking space'. This indifference to content is what gives paging its power.

/* Simplified view of what the kernel learns at boot from UEFI/BIOS.
   Real code is in arch/x86/kernel/e820.c */

struct e820_entry {
    uint64_t addr;   /* start of region (bytes) */
    uint64_t size;   /* size of region (bytes) */
    uint32_t type;   /* 1=usable, 2=reserved, 3=ACPI, ... */
};

/* Example memory map on a typical PC:
   [0x00000000 - 0x0009FFFF]  640 KiB  usable
   [0x000A0000 - 0x000FFFFF]  384 KiB  reserved (VGA/BIOS)
   [0x00100000 - 0x7FFFFFFF]  ~2 GiB   usable
   [0x80000000 - 0xFFFFFFFF]  2 GiB    reserved (PCI, APIC)  */

Imagine you manage physical memory with the simplest possible scheme: a free list of contiguous free regions, and you hand out memory by finding a region big enough for each request (first-fit, best-fit, worst-fit strategies). This is essentially what early systems and simple embedded allocators do.

Two kinds of fragmentation will destroy you:

External fragmentation: You have 100 MiB free total, but no single contiguous 64-MiB region — the free memory is split into dozens of small holes between allocated blocks. A request for 64 MiB fails even though you technically have enough free RAM. Imagine a hotel with 200 empty rooms but no block of 64 adjacent rooms — you can't house a conference group even though the hotel isn't full.

Internal fragmentation: You allocate in fixed-size units. A request for 5 bytes gets a 4096-byte page, wasting 4091 bytes. The allocated block is larger than needed.

External fragmentation is the killer for the physical allocator. The kernel often needs large physically contiguous regions: for DMA (Direct Memory Access) transfers to hardware, for huge pages (2 MiB or 1 GiB), for the kernel's own internal data structures. If physical memory is fragmented, these allocations fail even when free reports plenty of available memory.

This is why the Linux kernel uses the buddy allocator for physical pages — it is specifically designed to minimize external fragmentation and make coalescing (merging adjacent free blocks) fast and deterministic.

/* Illustration of external fragmentation.
   After a series of alloc/free operations: */

/*  Physical address space (each cell = 1 MiB):

    [USED][FREE][USED][FREE][USED][FREE][FREE][USED]

    Total free: 4 MiB across 3 holes.
    A request for 3 MiB contiguous FAILS — largest hole is 2 MiB.
    This is external fragmentation.
*/

The buddy allocator is the primary physical page allocator in the Linux kernel (mm/page_alloc.c). Its genius is that it allocates memory in powers of two, and it always knows the exact address of a block's 'buddy' — the adjacent block of the same size that would merge with it to form a larger block.

How it works: Memory is divided into zones (ZONE_DMA, ZONE_NORMAL, ZONE_HIGHMEM on 32-bit). Each zone maintains 11 free lists (on Linux, MAX_ORDER=11), one for each order from 0 (single page, 4 KiB) to 10 (1024 pages, 4 MiB).

Allocation: Request for 2^k pages → look in the order-k free list. If empty, split an order-(k+1) block: give one half to the requester, put the other half ('buddy') on the order-k list. Recurse upward if needed.

Freeing: When a block is freed, check if its buddy is also free. If so, coalesce them into a block of order k+1 and repeat the check upward. This coalescing is O(log N) and very cache-friendly.

Finding the buddy: For a block at physical address P with order k, its buddy is at address P XOR (1 << (k + PAGE_SHIFT)). This XOR trick is why power-of-two sizes matter so much — you can compute the buddy's address with a single XOR instruction, no lookup needed.

The kernel exposes current buddy state via /proc/buddyinfo. Each number is the count of free blocks at that order. A healthy system will have entries at many orders; a fragmented system will have most counts at order 0.

/* Toy buddy allocator in C — demonstrates the core idea.
   Real kernel code is in mm/page_alloc.c */
#include <stdint.h>
#include <string.h>
#include <stdio.h>

#define MAX_ORDER 5       /* orders 0..4, max block = 2^4 = 16 pages */
#define TOTAL_PAGES 32    /* must be 2^MAX_ORDER */

static uint8_t used[TOTAL_PAGES]; /* 1 = page is allocated */
static int free_list[MAX_ORDER + 1][TOTAL_PAGES]; /* free block start pages */
static int free_count[MAX_ORDER + 1];

void buddy_init(void) {
    memset(used, 0, sizeof(used));
    memset(free_count, 0, sizeof(free_count));
    /* One free block at highest order covers all pages */
    free_list[MAX_ORDER][0] = 0;
    free_count[MAX_ORDER] = 1;
}

/* Returns start page index, or -1 on failure */
int buddy_alloc(int order) {
    for (int o = order; o <= MAX_ORDER; o++) {
        if (free_count[o] == 0) continue;
        /* Take first free block at order o */
        int page = free_list[o][--free_count[o]];
        /* Split down to requested order */
        while (o > order) {
            o--;
            int buddy = page + (1 << o); /* buddy starts here */
            free_list[o][free_count[o]++] = buddy;
        }
        for (int i = 0; i < (1 << order); i++) used[page + i] = 1;
        return page;
    }
    return -1; /* OOM */
}

void buddy_free(int page, int order) {
    for (int i = 0; i < (1 << order); i++) used[page + i] = 0;
    /* Coalesce with buddy while possible */
    while (order < MAX_ORDER) {
        int buddy = page ^ (1 << order); /* XOR to find buddy */
        /* Check if buddy is entirely free at this order */
        int buddy_free = 1;
        for (int i = 0; i < (1 << order); i++)
            if (used[buddy + i]) { buddy_free = 0; break; }
        if (!buddy_free) break;
        /* Remove buddy from its free list (simplified: just coalesce) */
        page = page < buddy ? page : buddy; /* lower address is new block start */
        order++;
    }
    free_list[order][free_count[order]++] = page;
}

int main(void) {
    buddy_init();
    int a = buddy_alloc(2); /* 4 pages */
    int b = buddy_alloc(1); /* 2 pages */
    printf("Allocated: a=%d b=%d\n", a, b);
    buddy_free(a, 2);
    buddy_free(b, 1);
    printf("After free, order-5 free count: %d\n", free_count[MAX_ORDER]);
    return 0;
}

Before paging dominated, segmentation was a major memory management strategy — and it is still present in x86 hardware today, albeit mostly vestigially in 64-bit mode.

The idea: instead of dividing memory into fixed-size pages, divide it into variable-sized segments that match logical program structure. A program naturally has a code segment, a data segment, a stack segment, a heap segment. Each segment has a base address (where it starts in physical memory) and a limit (its maximum size). The hardware uses a segment descriptor table (the GDT/LDT on x86) to translate logical addresses (segment:offset) to physical addresses.

The appeal: Segments map directly to programmer intent. Sharing a library is easy: point multiple programs' code segment selectors at the same physical region. Setting permissions per segment (code = read+execute, stack = read+write) is natural.

The fatal flaw: External fragmentation. Because segments are variable-size, fitting them into physical memory is the bin-packing problem — NP-hard in general. As processes start and stop, physical memory becomes a Swiss cheese of holes. Compaction (moving segments around) is expensive and requires updating all pointers.

Intel tried to rescue segmentation with protected mode in the 286 and enhanced it in the 386. But by the 1990s, OSes like Linux ran in 'flat mode' — all segment bases set to 0, all limits set to 4 GiB — effectively disabling segmentation and relying entirely on paging. x86-64 (64-bit mode) goes further: CS/DS/ES/SS segment bases are forced to 0 by the hardware. Only FS and GS retain non-zero base support, used by Linux for per-CPU and per-thread data (gs:0 in kernel, fs:0 in userspace TLS).

Segmentation survives in modern systems as a concept in the sense that every process's virtual address space is divided into VMA regions (Virtual Memory Areas in Linux) with different permissions — but these are managed by the kernel in software, not enforced by hardware segment registers.

/* x86 segment descriptor format (historical/educational).
   On x86-64, base is forced to 0 for most segments. */

struct segment_descriptor {
    uint16_t limit_low;     /* bits 0..15 of segment limit */
    uint16_t base_low;      /* bits 0..15 of base address */
    uint8_t  base_mid;      /* bits 16..23 of base */
    uint8_t  access;        /* P|DPL|S|type: present, privilege, type */
    uint8_t  flags_limit;   /* G|D/B|L|AVL | limit bits 16..19 */
    uint8_t  base_high;     /* bits 24..31 of base */
} __attribute__((packed));

/* Physical address = base + offset, if offset <= limit.
   On x86-64: base=0 for CS/DS/ES/SS, so physical = virtual = offset.
   Only FS/GS can have non-zero base (set via WRFSBASE/WRGSBASE or MSRs). */

Paging is the mechanism that lets every process believe it owns the entire address space. It is the most important concept in this module.

The core idea: Both virtual (logical) addresses used by programs and physical addresses are divided into fixed-size pages (virtual) and page frames (physical), both the same size (typically 4 KiB). A per-process data structure called the page table maps virtual page numbers to physical frame numbers.

The CPU has a special unit called the MMU (Memory Management Unit) that intercepts every memory access and performs the translation: take the virtual address, look up the page table, get the physical address, proceed. This happens in hardware, on every single load and store, transparently.

Why this is a 'beautiful lie':

• Process A's virtual address 0x1000 maps to physical frame 42.
• Process B's virtual address 0x1000 maps to physical frame 7.
• Neither process knows about the other's mapping.
• The kernel can map the same physical frame into two processes (shared memory).
• The kernel can refuse to map a virtual address (NULL pointer access → page fault → SIGSEGV).
• The kernel can mark pages as read-only (copy-on-write after fork).
• The kernel can 'not map' a page at all and only bring it in from disk when needed (demand paging, swap).

Permission bits: Each page table entry stores not just the physical frame number but also permission bits: Present (P), Read/Write (R/W), User/Supervisor (U/S), Execute Disable (XD/NX). The hardware enforces these on every access.

The result: complete isolation between processes, flexible placement of physical memory, and the ability to run programs larger than physical RAM — all enforced transparently in hardware at full CPU speed.

/* Conceptual page table entry (x86-64 simplified).
   The real struct is in arch/x86/include/asm/pgtable_types.h */

typedef uint64_t pte_t;

/* Bits in a 64-bit page table entry:
   Bits  0     : Present (P)          — 1 if page is in RAM
   Bit   1     : Read/Write (R/W)     — 0=read-only, 1=writable
   Bit   2     : User/Supervisor      — 0=kernel only, 1=user accessible
   Bit   3     : Write-Through        — cache write policy
   Bit   4     : Cache Disable        — bypass CPU cache
   Bit   5     : Accessed (A)         — set by hardware on any read
   Bit   6     : Dirty (D)            — set by hardware on write
   Bit   7     : Page Size (PS)       — 1 = huge page (2 MiB at level 2)
   Bits  11: 8 : available to OS
   Bits  51:12 : Physical Frame Number — bits 51..12 of physical addr
   Bits  62:52 : available to OS
   Bit   63    : Execute Disable (XD/NX) — 1 = no instruction fetch
*/

#define PTE_PRESENT  (1ULL << 0)
#define PTE_WRITE    (1ULL << 1)
#define PTE_USER     (1ULL << 2)
#define PTE_NX       (1ULL << 63)
#define PTE_PFN_MASK 0x000FFFFFFFFFF000ULL

static inline pte_t make_pte(uint64_t phys_addr, uint64_t flags) {
    return (phys_addr & PTE_PFN_MASK) | flags;
}

static inline uint64_t pte_to_phys(pte_t pte) {
    return pte & PTE_PFN_MASK;
}

A naive single-level page table for a 64-bit virtual address space would need 2^52 entries (one per 4 KiB virtual page) × 8 bytes each = 32 PiB of memory just for the page table. That's larger than any RAM that exists. We need a smarter structure.

The solution is a multi-level (hierarchical) page table. Instead of one huge flat array, the virtual address is split into several fields, each indexing one level of a tree.

x86-64 uses 4 levels (5 in recent CPUs for even larger address spaces):

• Bits 47..39: PML4 index (512 entries, the 'page global directory')
• Bits 38..30: PDP index (512 entries per PML4 entry)
• Bits 29..21: PD index (512 entries, can point to 2 MiB huge page)
• Bits 20..12: PT index (512 entries, points to 4 KiB physical frame)
• Bits 11..0: offset within the final page

The CR3 register holds the physical address of the top-level table. On every context switch, the kernel writes the new process's top-level page table address into CR3 (this also flushes most TLB entries, which is expensive — hence PCID optimization).

Why this saves memory: A process that only uses a small amount of virtual space (say, a few hundred MiB) will only have a few populated entries at each level. Entire branches of the tree that point to unmapped virtual ranges simply have the Present bit clear — you don't allocate sub-tables for those branches at all. A typical process might only need a handful of actual page table pages despite nominally having a 128 TiB virtual address space.

ARM64 uses a similar scheme. RISC-V uses an identical concept called Sv39 (3 levels, 39-bit VA) or Sv48 (4 levels, 48-bit VA), described in the RISC-V Privileged ISA spec.

/* Manually walk a 4-level x86-64 page table.
   This is conceptually what the MMU does in hardware,
   and what the kernel does in software for page faults. */

#include <stdint.h>
#define PAGE_SHIFT 12
#define PAGE_SIZE  (1UL << PAGE_SHIFT)
#define PT_ENTRIES 512
#define PRESENT    (1ULL << 0)

typedef uint64_t pgentry_t;

/* Read one entry from a page table at a given physical address. */
static pgentry_t read_entry(uint64_t table_phys, int index) {
    /* In a real kernel: phys_to_virt(table_phys)[index]
       Here we just illustrate the indexing logic. */
    pgentry_t *table = (pgentry_t *)table_phys; /* pretend 1:1 mapping */
    return table[index];
}

/* Translate virtual address -> physical address using CR3 value. */
uint64_t walk_page_table(uint64_t cr3, uint64_t va) {
    /* Each level uses 9 bits of the VA */
    int pml4_idx = (va >> 39) & 0x1FF;
    int pdp_idx  = (va >> 30) & 0x1FF;
    int pd_idx   = (va >> 21) & 0x1FF;
    int pt_idx   = (va >> 12) & 0x1FF;
    uint64_t offset = va & 0xFFF;

    pgentry_t pml4e = read_entry(cr3 & ~0xFFFULL, pml4_idx);
    if (!(pml4e & PRESENT)) return (uint64_t)-1; /* page fault */

    pgentry_t pdpe = read_entry(pml4e & ~0xFFFULL, pdp_idx);
    if (!(pdpe & PRESENT)) return (uint64_t)-1;
    /* Check for 1 GiB huge page (bit 7 set) — omitted for brevity */

    pgentry_t pde = read_entry(pdpe & ~0xFFFULL, pd_idx);
    if (!(pde & PRESENT)) return (uint64_t)-1;
    /* Check for 2 MiB huge page (bit 7 set) — omitted for brevity */

    pgentry_t pte = read_entry(pde & ~0xFFFULL, pt_idx);
    if (!(pte & PRESENT)) return (uint64_t)-1;

    return (pte & ~0xFFFULL) | offset; /* physical address */
}

Walking a 4-level page table for every memory access would require 4 additional memory reads per actual memory read — a 5x slowdown minimum. This is unacceptable. The CPU solves this with the TLB (Translation Lookaside Buffer): a small, extremely fast, fully-associative cache of recent virtual-to-physical translations.

The TLB stores (virtual page number → physical frame number + permissions) entries. On every memory access the MMU first checks the TLB. On a TLB hit (the common case for code in a tight loop) the translation is free — one cycle. On a TLB miss the hardware (or software, on MIPS/RISC-V SBI) walks the page table and installs the new entry, taking tens to hundreds of cycles.

TLB invalidation is a major source of kernel performance complexity. When the kernel changes a page table entry — remapping a page, changing permissions, freeing a mapping — it must tell the CPU to invalidate the corresponding TLB entries. If it doesn't, the CPU will use a stale cached translation. This is done with INVLPG (x86, invalidate one entry) or by reloading CR3 (flushes all non-global entries — expensive). On a multi-processor system, each CPU has its own TLB, so the kernel must send TLB shootdown IPIs (Inter-Processor Interrupts) to remote CPUs, which is one of the most expensive operations in kernel memory management.

Global pages: Kernel mappings that are present in all processes (the kernel half of the virtual address space) can be marked 'global' (PTE_GLOBAL), so they are not flushed on CR3 reload during context switches. This saves enormous time since the kernel's own page tables don't need to be reloaded on every syscall.

Note: KPTI (Kernel Page Table Isolation), introduced to mitigate Meltdown, removed kernel mappings from user-space page tables entirely. This means every syscall now requires a CR3 switch — a significant performance cost on workloads with many syscalls.

/* Force TLB flush for one virtual address on x86-64.
   Used internally by kernel after updating a PTE. */
static inline void flush_tlb_one(unsigned long addr) {
    asm volatile("invlpg (%0)" : : "r"(addr) : "memory");
}

/* Flush entire TLB (all non-global entries) by reloading CR3. */
static inline void flush_tlb_full(void) {
    unsigned long cr3;
    asm volatile(
        "mov %%cr3, %0\n"
        "mov %0, %%cr3"
        : "=r"(cr3) : : "memory"
    );
}

/* See also: arch/x86/mm/tlb.c in the kernel for the real implementation,
   including SMP TLB shootdown via CALL_FUNCTION IPIs. */

The buddy allocator is great at handing out whole pages (4 KiB units), but the kernel constantly needs to allocate small objects: a struct task_struct (a few KiB), a struct inode (hundreds of bytes), a struct sk_buff (network buffer, variable). Calling the buddy allocator for each of these would waste enormous amounts of memory due to internal fragmentation and would be slow.

The solution is the slab allocator (originally by Jeff Bonwick for Solaris, adopted by Linux). The idea:

1. For each frequently-allocated object type, maintain a dedicated cache (struct kmem_cache).
2. Each cache consists of slabs: one or more pages obtained from the buddy allocator, divided into slots of exactly the right size for that object.
3. Free objects in a slab sit on a free list. Allocation is just list_pop() — O(1). Freeing is list_push() — O(1).
4. When a slab is fully empty (all objects freed), the pages can be returned to the buddy allocator.

Benefits beyond speed: Because each cache only holds one type of object, slab coloring (padding to reduce cache-line aliasing), constructor/destructor functions per type, and per-CPU caches for lock-free fast paths all become possible. The kmalloc() function (kernel's general allocator) is implemented on top of a set of size-based slab caches (32B, 64B, 128B, ..., 8 KiB).

Linux has gone through three slab implementations: the original SLAB, SLUB (the current default, simpler and faster, by Christoph Lameter), and SLOB (for tiny embedded systems). You can see which caches exist and their statistics at /proc/slabinfo or sudo slabtop.

/* Kernel API for slab allocation (real kernel headers):
   #include <linux/slab.h> */

/* Create a dedicated cache for a specific struct: */
struct kmem_cache *task_cache = kmem_cache_create(
    "my_task",          /* name shown in /proc/slabinfo */
    sizeof(struct my_task),  /* object size */
    __alignof__(struct my_task), /* alignment */
    SLAB_HWCACHE_ALIGN, /* flags: align to hardware cache line */
    NULL                /* constructor (optional) */
);

/* Allocate one object: */
struct my_task *t = kmem_cache_alloc(task_cache, GFP_KERNEL);

/* Free it: */
kmem_cache_free(task_cache, t);

/* General-purpose kernel allocation (backed by size caches): */
void *buf = kmalloc(128, GFP_KERNEL);  /* like malloc in kernel */
kfree(buf);

/* GFP flags control behavior:
   GFP_KERNEL  — may sleep/block waiting for memory (process context)
   GFP_ATOMIC  — must not sleep (interrupt context)
   GFP_DMA     — must come from ZONE_DMA (< 16 MiB on x86)
   GFP_HIGHUSER — for userspace pages, can use ZONE_HIGHMEM */

In the kernel, a process's virtual address space is not described as a full page table (that's the hardware view). It is described as a collection of VMAs (Virtual Memory Areas), each represented by struct vm_area_struct in Linux.

A VMA is a contiguous range of virtual pages that all share the same properties: same permissions (read/write/execute), same backing store (anonymous memory, a file, shared memory), same flags. When you call mmap() to map a file or malloc() internally calls brk() or mmap(MAP_ANONYMOUS), you are creating or extending VMAs.

The kernel keeps VMAs in two data structures for a process:

1. A red-black tree (mm_struct.mm_rb) for O(log n) lookup by address.
2. A linked list (mm_struct.mmap) for sequential scanning.

Demand paging and page faults: When a VMA is created, the kernel does NOT immediately allocate physical pages or populate page table entries. Physical memory is allocated lazily, on the first access. When the CPU tries to access a virtual address with no PTE (Present bit = 0), the hardware raises a page fault exception. The kernel's page fault handler (do_page_fault on x86, do_fault in mm/memory.c) looks up which VMA covers the faulting address, determines what should be there (file data, zero page, copy-on-write copy), allocates a physical page, fills it, installs the PTE, and returns. The faulting instruction is retried transparently.

This lazy allocation is why malloc(1_000_000_000) returns instantly — no physical RAM is committed yet. Only when you write to each page does physical memory get consumed.

You can inspect a process's VMAs in /proc/<pid>/maps (human-readable) or /proc/<pid>/smaps (with RSS/PSS statistics per VMA).

/* See what VMAs a process has:
   $ cat /proc/self/maps

   Typical output:
   55a3b0e00000-55a3b0e01000 r--p 00000000 fd:01 1234567  /bin/cat
   55a3b0e01000-55a3b0e03000 r-xp 00001000 fd:01 1234567  /bin/cat
   55a3b0e03000-55a3b0e04000 r--p 00003000 fd:01 1234567  /bin/cat
   55a3b0e04000-55a3b0e05000 r--p 00003000 fd:01 1234567  /bin/cat (COW)
   55a3b0e05000-55a3b0e06000 rw-p 00004000 fd:01 1234567  /bin/cat
   55a3b0f2a000-55a3b0f4b000 rw-p 00000000 00:00 0        [heap]
   7f8a23c00000-7f8a23c28000 r--p 00000000 fd:01 789012   /lib/libc.so.6
   ...                       r-xp ...                     /lib/libc.so.6
   7fff12340000-7fff12361000 rw-p 00000000 00:00 0        [stack]
   7fff12399000-7fff1239d000 r--p 00000000 00:00 0        [vvar]
   7fff1239d000-7fff1239f000 r-xp 00000000 00:00 0        [vdso]

   Columns: start-end  perms  offset  dev  inode  name
   perms: r=read, w=write, x=execute, p=private(COW), s=shared */

/* Kernel struct (simplified from include/linux/mm_types.h): */
struct vm_area_struct {
    unsigned long vm_start;   /* first byte of VMA */
    unsigned long vm_end;     /* first byte AFTER VMA */
    unsigned long vm_flags;   /* VM_READ, VM_WRITE, VM_EXEC, ... */
    struct file  *vm_file;    /* backing file, or NULL for anonymous */
    pgoff_t       vm_pgoff;   /* offset into file (in pages) */
    /* ... plus rb_tree links, mm pointer, ops vtable, etc. */
};

When a process calls fork(), the kernel creates a new process that is an exact copy of the parent. A naive implementation would copy every page of the parent's address space — potentially hundreds of megabytes — before the child even runs. Since most fork() calls are immediately followed by exec() (the parent's data is thrown away), this would be catastrophically wasteful.

Linux uses Copy-on-Write (COW):

1. fork() creates a new process with its own mm_struct and page tables, but both parent and child page tables point to the same physical page frames.
2. All previously-writable PTEs in both parent and child are marked read-only in both page tables.
3. Both processes run happily, reading from the shared pages. No copying needed yet.
4. The moment either process tries to write to one of these shared pages, the MMU sees the read-only PTE and raises a page fault.
5. The kernel's COW fault handler allocates a new physical page, copies the contents of the original page into it, updates the faulting process's PTE to point to the new page (with write permission restored), decrements the reference count on the original page, and resumes the write.

The result: fork() is O(number of VMAs), not O(size of address space). Only modified pages are ever copied. Most fork()+exec() sequences copy almost nothing.

COW is also used for the mmap(MAP_PRIVATE) system call when mapping files: multiple processes can map the same file read-only; writes trigger COW faults that create private copies.

The kernel tracks physical page reference counts in struct page.refcount. A page with refcount > 1 is shared and must be COW'd on write. A page with refcount = 1 is private and can be written directly.

/* Demonstrate COW semantics: */
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int main(void) {
    int *shared = malloc(4096); /* one page */
    *shared = 42;

    printf("Before fork: value=%d, addr=%p\n", *shared, shared);

    pid_t pid = fork();
    if (pid == 0) {
        /* Child: same virtual address, same physical page (COW) */
        printf("Child before write: value=%d, addr=%p\n", *shared, shared);
        /* This write triggers a COW page fault.
           Child gets its own private copy of the page. */
        *shared = 99;
        printf("Child after write:  value=%d, addr=%p\n", *shared, shared);
        /* Virtual address 'shared' is the same, but it now maps
           to a DIFFERENT physical frame than the parent's copy. */
        exit(0);
    } else {
        wait(NULL);
        /* Parent's copy is unchanged: */
        printf("Parent after child exit: value=%d\n", *shared);
        free(shared);
    }
    return 0;
}
/* Output:
   Before fork: value=42, addr=0x...
   Child before write: value=42, addr=0x...   (same vaddr!)
   Child after write:  value=99, addr=0x...   (new physical page)
   Parent after child exit: value=42           (original unchanged) */

One of the most powerful capabilities paging enables is over-commitment: the kernel can promise more memory than is physically available. When physical RAM runs low, the kernel can swap (evict) pages that haven't been used recently to a swap partition or swap file on disk, freeing up their physical frames for more urgent use. When the evicted page is needed again, a page fault occurs, the kernel reads the page back from disk, and execution continues.

The page replacement problem: Which pages should be evicted? The theoretically optimal algorithm (Belady's OPT) evicts the page that will be needed farthest in the future — but this requires seeing the future. Real algorithms approximate it:

• LRU (Least Recently Used): evict the page not accessed for the longest time. Expensive to implement exactly (requires updating a timestamp on every access).
• Clock / Second-Chance: approximate LRU using the hardware Accessed bit (bit 5 in the PTE). The kernel scans PTEs in a circular fashion; if the Accessed bit is 1, clear it and move on ('giving it a second chance'); if it's 0, evict the page. This is the basis of Linux's page replacement.
• Linux's two-list LRU: Pages are on either the 'active' or 'inactive' list. Newly faulted pages go to inactive. Repeatedly accessed inactive pages are promoted to active. The inactive list is the eviction candidate pool.

Swap introduces a new PTE state: a PTE with Present=0 but non-zero content stores a swap entry (which swap device + which slot on that device). The page fault handler checks: if Present=0 and swapped, read the page back from disk (major fault). If Present=0 and anonymous with no swap entry, it's a fresh page — fill with zeros (minor fault, fast).

You can inspect swap usage with swapon --show, vmstat, or /proc/meminfo. The kernel's LRU lists can be seen indirectly through smaps (the Inactive field per VMA).

/* Check swap and memory stats from shell:

   $ cat /proc/meminfo | grep -E 'MemTotal|MemFree|SwapTotal|SwapFree'
   MemTotal:       16302076 kB
   MemFree:          284312 kB
   SwapTotal:       2097148 kB
   SwapFree:        1843200 kB

   $ vmstat 1 3
   procs -----------memory---------- ---swap-- -----io---- -system-- ------cpu-----
    r  b   swpd   free   buff  cache   si   so    bi    bo   in   cs us sy id wa
    2  0 253948 284312  12345 8765432    0    1     2     5  450 900  5  2 92  1

   si = pages swapped IN per second (from disk to RAM)
   so = pages swapped OUT per second (from RAM to disk)

   High 'so' means memory pressure.
   High 'si' with high 'wa' (wait) means thrashing: the system is
   spending more time swapping than doing real work. */