Implement Demand Paging: Allocate on First Access

Topic Overview

Pay for What You Touch

Demand paging defers physical allocation until a page is accessed. The kernel marks PTEs not-present; the first load or store traps, the fault handler finds a free frame, and returns to user code transparently.

Fault Handler Duties

On a demand fault:

• Validate address against VMA permissions
• Allocate physical page (zero or read from backing store)
• Install PTE with correct flags
• Invalidate TLB entry if needed

For example, malloc returning a 16 KB arena might only consume 1 physical page until the program writes past the first 4096 bytes.

Why This Matters in Production

Demand paging is why touching one byte of a 1GB anonymous mmap doesn't cost 1GB of resident memory up front , Linux's memory overcommit accounting and every sparse-array workload depend on exactly this lazy-allocation behavior. Get the present-bit check backwards and every access becomes an unnecessary page fault, or worse, a real fault is silently skipped and you read unallocated memory.

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 hook page faults to allocate backing storage lazily. The exercise requires a counter proving physical pages grow only as the program touches virtual ranges.

Your Task

Implement demand paging. Reserving memory (malloc, mmap) only creates page-table entries with the present bit clear. A physical frame is allocated at the first access to a page, by the page-fault handler. A program that reserves 1 GiB but touches 10 MiB therefore uses only 10 MiB of RAM. Simulate the page tables, a pool of physical frames and the fault handler, and report how much memory demand paging saved compared with allocating everything up front.

Commands

Rules

• A page fault allocates the lowest-numbered free frame. With no free frame, the access fails with out of memory and the page stays not-present.
• Frames returned by release become free again.

Output

• region NAME: P pages reserved, 0 resident
• a single touch: touch NAME P: fault -> frame F, touch NAME P: hit (frame F) or touch NAME P: out of memory.
• a range: touch NAME A-B: N faults, H hits, O out of memory (the step isn't echoed).
• pt NAME: P->F ... in page order, or pt NAME: nothing present.
• release NAME: R frames freed.
• stats: reserved R pages, resident P pages (X.X%), faults F, free frames Z, then eager allocation would need R frames; demand paging saved S, where S = R − P counts all live regions.
• Errors: CMD NAME: no such region, touch NAME P: page out of range, and region NAME: already exists.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. A per-region page table of {present, frame} entries (all not-present at first) and a free-frame bitmap.
2. Only the fault handler allocates frames; region never does.

Hidden tests cover running out of frames partway through a range, reusing frames after release, two regions competing for frames, and every error.