Copy-on-write fork

Deep dive

How it works

In: a process with private writable mappings · Out: a second process whose memory equals the first at that instant · State: per-frame reference counts and write-protected page-table entries · Cost: fork copies one entry per resident mapped page; each later first write costs a fault, plus a 4 KiB copy if the frame is still shared.

1. fork() creates a task structure and copies the page-table entries of the process's mappings. Each frame's reference count goes up by one, and the write bit is cleared in parent and child. No data moves.
2. Both processes read the shared frames at full speed.
3. A write to a read-only entry raises a protection fault.
4. Reference count above 1: allocate a frame, copy 4 KiB, point the writer's entry at it (writable), drop one reference on the old frame. Count equal to 1: the other side already left, so set the write bit with no copy.
5. Clearing write bits invalidates cached translations, so a multithreaded parent pays inter-CPU TLB flushes (see Virtual memory and the TLB).
6. exit or exec drops the references, and frames reaching zero are freed.
7. vfork and posix_spawn skip steps 1-5: the child runs in the parent's memory (CLONE_VM) and the calling thread is suspended until the child calls execve or _exit.

Rules from the man pages and POSIX: the child has a single thread; the state of mutexes in the copied memory is replicated; after fork() in a multithreaded program the child may call only async-signal-safe functions until execve. MADV_DONTFORK leaves a mapping out of the child, MADV_WIPEONFORK zeroes it there.

Code

A model of steps 1-6, not a kernel: one word stands in for a 4 KiB frame, no TLB, no huge pages, one private writable mapping. Compiled and run (asserts pass, output ok: faults=1010 copies=10 frames=1000).

// Model of copy-on-write fork: frames, refcounts, page-table entries.
// Not a kernel: no TLB, no huge pages, no locking, one private writable mapping.
#[derive(Clone, Copy)]
struct Pte {
    frame: usize,
    writable: bool,
}

#[derive(Default)]
struct Mem {
    data: Vec<u64>, // frame contents (one word stands in for 4 KiB)
    refs: Vec<u32>, // how many page tables map each frame
    free: Vec<usize>,
    faults: u64,
    copies: u64,
    ptes_copied: u64,
}

type Space = Vec<Pte>; // virtual page number -> entry

impl Mem {
    fn alloc_frame(&mut self, v: u64) -> usize {
        let f = self.free.pop().unwrap_or_else(|| {
            self.data.push(0);
            self.refs.push(0);
            self.data.len() - 1
        });
        (self.data[f], self.refs[f]) = (v, 1);
        f
    }
    fn new_space(&mut self, pages: usize) -> Space {
        (0..pages).map(|i| Pte { frame: self.alloc_frame(i as u64), writable: true }).collect()
    }
    /// fork(): copy every PTE (cost ~ mapped pages), share frames, write-protect both sides.
    fn fork(&mut self, parent: &mut Space) -> Space {
        for pte in parent.iter_mut() {
            self.refs[pte.frame] += 1;
            pte.writable = false;
        }
        self.ptes_copied += parent.len() as u64;
        parent.clone()
    }
    fn read(&self, s: &Space, vpn: usize) -> u64 {
        self.data[s[vpn].frame]
    }
    fn write(&mut self, s: &mut Space, vpn: usize, v: u64) {
        if !s[vpn].writable {
            self.faults += 1; // write-protection fault
            let old = s[vpn].frame;
            if self.refs[old] > 1 {
                self.refs[old] -= 1; // still shared: copy into a private frame
                let new = self.alloc_frame(self.data[old]);
                s[vpn].frame = new;
                self.copies += 1;
            }
            s[vpn].writable = true; // sole owner: just upgrade the entry
        }
        let f = s[vpn].frame;
        self.data[f] = v;
    }
    /// exit(): drop one reference per mapping; free frames nobody maps.
    fn exit(&mut self, s: Space) {
        for pte in s {
            self.refs[pte.frame] -= 1;
            if self.refs[pte.frame] == 0 {
                self.free.push(pte.frame);
            }
        }
    }
    fn in_use(&self) -> usize {
        self.refs.iter().filter(|&&r| r > 0).count()
    }
}

fn main() {
    let (n, k) = (1000, 10);
    let mut m = Mem::default();
    let mut parent = m.new_space(n);
    let mut child = m.fork(&mut parent);
    assert_eq!((m.in_use(), m.ptes_copied), (n, n as u64)); // no data copied by fork

    for i in 0..k {
        m.write(&mut child, i, 100 + i as u64);
        m.write(&mut child, i, 200 + i as u64); // second write: already private, no fault
    }
    assert_eq!((m.faults, m.copies, m.in_use()), (k as u64, k as u64, n + k));
    assert!((0..n).all(|i| m.read(&parent, i) == i as u64)); // parent unchanged
    assert_eq!(m.read(&child, 3), 203);

    m.exit(child);
    assert_eq!(m.in_use(), n); // the k private copies were freed
    for i in 0..n {
        m.write(&mut parent, i, 7);
    }
    assert_eq!((m.faults, m.copies), (k as u64 + n as u64, k as u64)); // n faults, 0 new copies
    println!("ok: faults={} copies={} frames={}", m.faults, m.copies, m.in_use());
}

Complexity and constants

• fork: table copy grows with resident mapped memory, independent of how many pages are later written.
• Per first-written shared page: one fault plus a 4 KiB copy; no copy if the frame is already sole-owned.
• Extra memory: up to one copy of every page both sides write, zero if nobody writes.
• vfork/posix_spawn: no table copy, but the caller blocks until exec.

Efficiency

Cost: measured on this Mac (Apple M4 Pro, macOS 27.0.1, 16 KiB pages, other work running, so noisy): fork()+_exit+waitpid took a minimum of 0.52-0.72 ms over 40 runs for parents with 1 MiB to 8 GiB of touched memory; medians were 0.8-2.8 ms with no clear trend in size. Why it does not grow was not investigated; do not carry this to Linux, where the man page says table duplication is the cost. Bound: page-table walk and, for threads, IPIs. Published (Baumann et al.): fork+exec time grows with parent size on Ubuntu 16.04, posix_spawn stays near 0.5 ms; they cite Chrome stalls of up to 100 ms in fork.

Levers

• posix_spawn/vfork instead of fork+exec: no table copy (about 0.5 ms flat, Baumann et al.) when the child immediately execs.
• Fork server: initialise once, fork per task — AFL docs: 1.5-2x on fast targets, 10x+ in deferred mode on some — when startup dominates.
• MADV_DONTFORK on big regions — not inherited (fork(2)) — when the child never reads them.
• Disable transparent huge pages — Redis admin docs advise it for memory and latency; whether that is a fork effect is not verified here — when writes are scattered.
• Size memory for the worst case (Redis docs: up to 2x during a save) — when the child lives long.

Naive → standard → state of the art

• Eager copy of the data space (historic, vfork(2)) · O(resident bytes) per fork
• COW fork · O(mapped pages) table copy + fault per first write
• posix_spawn, or a pre-initialised fork server · constant in parent size (spawn); startup paid once (server)

Implementation notes

• clone3 is a superset of clone, with more flag bits and, since Linux 5.5/5.7, CLONE_CLEAR_SIGHAND and CLONE_INTO_CGROUP (clone(2)). glibc has no wrapper.
• Overcommit: with vm.overcommit_memory=0 (heuristic) Redis documents that fork can fail unless free RAM could hold a full duplicate, and tells operators to set 1; mode 2 charges private writable mappings in full (kernel overcommit-accounting docs). Baumann et al. note this makes large fork+exec parents fail needlessly; see also memory pressure.
• A COW fault under a huge page either copies 2 MiB or splits it first; this depends on kernel version and mapping type, and is not verified here (see Huge pages).

Pitfalls

• Multithreaded parent: another thread holds the allocator lock at fork, the child inherits it locked and deadlocks on malloc. Call only async-signal-safe functions before exec (POSIX).
• macOS: system libraries may start threads, so Python made spawn its default there since 3.8 and says fork should be considered unsafe.
• Buffered stdio is duplicated: flush before fork or output appears twice. Descriptors share offsets with the parent.
• The child inherits secrets and the same address-space layout; MADV_WIPEONFORK zeroes chosen ranges.

Variants and alternatives

In production

Redis (RDB snapshots and AOF rewrite fork a child), PostgreSQL (postmaster starts one backend per connection), Apache prefork MPM, Android Zygote, AFL and AFL++ fork servers, Python multiprocessing.

Implementations

Sources

• Andrew Baumann, Jonathan Appavoo, Orran Krieger, Timothy Roscoe, A fork() in the road, HotOS 2019. paper · DOI
• fork(2), vfork(2), clone(2), posix_spawn(3), Linux man-pages.
• POSIX fork(), The Open Group.
• Overcommit accounting, Linux kernel docs.
• Redis persistence, Redis FAQ, Redis admin.
• About the Zygote processes, Android Open Source Project.
• multiprocessing, Python docs. AFL technical details. PostgreSQL architecture. Apache MPM prefork.