Implement Copy-on-Write (COW) for fork() Efficiency

Topic Overview

fork() Without Copying Everything

Copy-on-write (COW) lets fork() mark writable pages read-only in parent and child. The first writer faults, the kernel duplicates the frame, and updates both page tables. Most pages never get written after fork, so memory use stays low.

COW Fault Flow

Steps on write to shared page:

• CPU traps with write to read-only PTE
• Kernel allocates new frame, copies old contents
• Remaps writer's PTE writable; other may stay shared read-only

For example, after fork(), a 1 GB heap mapped but barely modified might share 99% of frames until specific objects mutate.

Why This Matters in Production

Every fork() on Linux relies on copy-on-write to make process creation cheap, and Redis's BGSAVE forks its entire dataset to get a consistent snapshot using this exact mechanism. The 2016 Dirty COW vulnerability (CVE-2016-5195) exploited a race in this very write-fault path to let unprivileged users gain root, showing COW correctness is a security property, not just a performance one.

Debugging Checklist

Before you call the implementation done, walk failure modes on purpose. Test empty structures, single-element edge cases, maximum concurrency, and errno paths that must not crash the program. OS code usually fails in production when happy-path tests pass but invariants break under contention or memory pressure.

Implementation Notes

Keep structures small and name fields after kernel counterparts when possible. That lets you read man pages and kernel source side by side while you work. Print observable events during development; remove noisy logs once tests pass reliably.

For This Exercise

You will implement COW bits on fork() simulation and duplicate frames on write faults. This task ties directly to why Linux can spawn processes faster than eager duplication would allow.

Your Task

Implement copy-on-write fork(). Copying a parent's memory at fork time would be slow and wasteful (the child often calls exec straight away), so the kernel copies only the page table. Both processes point at the same physical frames, every entry becomes read-only, and each frame's reference count is incremented. The first write by either side causes a page fault. The fault handler copies the frame if it's still shared, or simply makes it writable again if the writer is the last user.

Commands

New frames take the lowest free frame number, and frames whose count drops to 0 become free.

Output

• spawn P: N pages, frames A..B (or frames A when there's just one; the frames are consecutive only if they happen to be free).
• read P K = V (frame F)
• write P K = V followed by one of:
  • : in place (frame F): the entry is writable;
  • : cow fault, copied frame F -> G: read-only and shared (refcount > 1): copy the value to a new frame, drop one reference to the old one, make the entry writable;
  • : cow fault, last reference, frame F now writable: read-only but refcount 1: no copy.
• fork P C: N pages shared, 0 copied
• exit P: freed N frames
• show P: 0->F(rw) 1->G(ro) ... (page -> frame, with the entry's writability)
• stats: frames in use U, cow copies C, copies avoided A, where A = (total pages shared by all forks) − C: the page copies an eager fork would have made that COW never needed.

Errors: CMD P: no such process, CMD P: already exists (spawn/fork of an existing name), read/write P K: bad page (also for a write with no value).

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Note that shell's page 0 stays read-only with a refcount of 1. Its next write will just flip it writable without copying.

Requirements

1. A per-process page table of {frame, writable} and a global refcount[frame] and value[frame].
2. fork copies no frame data; every copy happens in the write-fault handler.

Hidden tests cover a chain of forks (grandchildren sharing with grandparents), the last-reference case that needs no copy, exit freeing only unshared frames, frame reuse after exit, and every error.