Inverted Page Tables

A standard (forward) page table, whether single-level or a multilevel radix tree, is indexed by virtual page number (VPN). Its size is proportional to the number of virtual pages a process's address space could span — for a 64-bit address space this is astronomically large, and multilevel structures only help by lazily allocating unused subtrees, not by changing the worst-case bound. Crucially, forward tables are per-process: each process gets its own table (or its own top-level structure), so total system table memory scales with both address-space size and process count. An inverted page table (IPT) instead keeps a single, system-wide table with exactly one entry per physical frame. Entry `i` describes whatever is currently resident in frame `i`. Since a machine has a fixed, comparatively small number of physical frames — determined by installed RAM divided by frame size — the table's total size is fixed and modest, shared across all processes, regardless of how many processes exist or how sparse their address spaces are. Formally, if physical memory holds `F` frames, the IPT has exactly `F` entries; it is never larger than that, by construction. Each entry typically stores:

• Process identifier (PID) — since frames are shared across processes, you need to know whose page this is.
• Virtual page number (VPN) — which page of that process's address space maps here.
• Control/status bits — valid, protection, dirty, referenced, and so on, just as in a forward entry.

The price of this compression is that translation direction is reversed. A forward table lets you index directly: `frame = table[vpn]`, an O(1) array access. An inverted table only tells you, for a known frame, what's in it — it does not let you index by VPN, because VPN is not the table's index; frame number is. To translate `(pid, vpn) → frame`, you must search every entry for a match, unless you build an auxiliary lookup structure. That auxiliary structure — almost universally a hash table — is what makes inverted page tables practical rather than merely elegant on paper.

Step 1 — Address generation. The CPU generates a virtual address, split into a virtual page number (VPN) and page offset, exactly as with any paging scheme. The running process's PID is known from context (e.g., a hardware process ID register or the current Process Control Block).

Step 2 — TLB check. As always, the hardware first probes the Translation Lookaside Buffer with `(pid, vpn)` (or an address-space-ID–tagged VPN). A TLB hit skips everything below — this is the common case and the reason the IPT's search cost rarely matters in practice.

Step 3 — Hash the key. On a TLB miss, the pair `(pid, vpn)` is hashed: ``` index = hash(pid, vpn) mod hash_table_size ``` The hash table is a separate, smaller structure of anchor slots, each pointing to a chain (or open-addressing probe sequence) of candidate frame numbers whose `(pid, vpn)` might hash to that slot.

Step 4 — Chain walk and verify. The hardware/software walks the chain at that hash slot, and for each candidate frame `f`, checks whether `IPT[f].pid == pid` and `IPT[f].vpn == vpn`. Because of possible hash collisions, this equality check is mandatory — the hash only narrows the search, it does not guarantee a unique match.

Step 5 — Resolve or fault. If a match is found and the entry is valid, the frame number `f` becomes the physical frame; combined with the page offset, this gives the physical address, and the TLB is refilled. If the chain is exhausted with no match, this is a genuine page fault: the page is not resident, and the OS page-fault handler runs (consulting the process's own auxiliary data — such as a backing per-process structure or the disk map — to bring the page in, choose a victim frame via a replacement policy, and update both the IPT entry for the victim frame and the hash table). ```pseudocode // Global, system-wide structures IPT[0 .. F-1] // one entry per physical frame // { valid, pid, vpn, protection, dirty, referenced } HashTable[0 .. H-1] // H hash buckets, each a chain of frame indices function translate(pid, vpn): // Step 2 (TLB) is assumed already missed; we are in the slow path slot = hash(pid, vpn) mod H frame = HashTable[slot] // head of chain, or NIL while frame != NIL: entry = IPT[frame] if entry.valid and entry.pid == pid and entry.vpn == vpn: TLB.insert(pid, vpn, frame) return frame // HIT: translation succeeded frame = entry.next_in_chain // advance to next candidate in this bucket // Chain exhausted: page is not in physical memory return PAGE_FAULT function handle_page_fault(pid, vpn): victim = choose_victim_frame() // e.g. clock / LRU-approx policy if IPT[victim].valid: old = IPT[victim] if old.dirty: write_back_to_backing_store(old.pid, old.vpn, victim) remove_from_chain(hash(old.pid, old.vpn) mod H, victim) load_page_from_backing_store(pid, vpn, victim) // physically populate frame IPT[victim] = { valid: true, pid: pid, vpn: vpn, protection: default_protection(), dirty: false, referenced: true, next_in_chain: NIL } slot = hash(pid, vpn) mod H insert_into_chain(slot, victim) // prepend/append victim to bucket's chain TLB.insert(pid, vpn, victim) return victim ``` Note the two loci of update: the IPT entry (indexed by frame, describing what's there) and the hash chain (indexed by hash of the key, providing the search path). Both must be kept consistent on every eviction and every fault-driven load — this dual bookkeeping is the structural cost of inversion.

Space complexity. The IPT itself has exactly `F` entries, where `F = physical_memory_size / frame_size`, regardless of the number of processes or the size of any process's virtual address space. Each entry needs `O(1)` space (a PID, a VPN, a few control bits, and a chain pointer), so total IPT space is `O(F)`. Contrast this with a forward multilevel table, whose worst case per process is `O(V/page_size)` where `V` is the size of the used portion of virtual address space, summed over all processes — for sparse, large, 64-bit address spaces multiplied across many processes, this can dwarf `O(F)`. The auxiliary hash table adds `O(H)` slot storage plus `O(F)` total chain-pointer overhead (each of the `F` resident pages appears in exactly one chain), so the grand total remains `O(F + H)` — still governed by physical memory, not virtual space.

Time complexity — average case. With a well-designed hash function distributing keys uniformly across `H` buckets, and `F` entries total, the expected chain length is `F/H` (the standard hash-table load-factor argument). Choosing `H = Θ(F)` keeps the expected chain length at `Θ(1)`, so translation on a TLB miss costs `O(1)` expected time: one hash computation plus a constant expected number of chain comparisons. This mirrors the classic guarantee for hash tables with separate chaining under simple uniform hashing — the expected search time for chains is `1 + α` where `α = F/H` is the load factor, which is `O(1)` when `α` is held constant.

Time complexity — worst case. If the hash function is poor, or an adversarial/pathological workload collides many `(pid, vpn)` pairs into one bucket, all `F` entries could land in a single chain, making a lookup `O(F)` — a linear scan in the worst case. This is the mirror image of any hash table's worst case, and it is the honest cost the inverted design pays for its compactness: unlike a forward multilevel table's guaranteed `O(levels) = O(1)`-ish direct indexing (a small constant number of memory accesses, typically 3–5 for a 4-level table), IPT lookup has no structural upper bound better than `O(F)` without further assumptions on the hash function's quality.

Why the TLB dominates in practice. The entire search-cost story is largely academic for the common case because the Translation Lookaside Buffer intercepts the overwhelming majority of translations — typical hit rates exceed 95–99% for well-behaved workloads. Only a TLB miss ever reaches the hash-and-chain path, and TLB misses are themselves rare (bounded by locality of reference). So the amortized, workload-weighted cost of translation is dominated by TLB hit latency (effectively free, built into the pipeline) plus a small tax for the rare miss.

Correctness argument. The key invariant is: > At all times, `IPT[f]` is valid if and only if physical frame `f` currently holds a resident page, and in that case `(IPT[f].pid, IPT[f].vpn)` names exactly the process and virtual page occupying it; and the hash chain for bucket `hash(pid, vpn) mod H` contains frame `f` if and only if `IPT[f]` currently holds that `(pid, vpn)`. This invariant is established at boot (all entries invalid, all chains empty) and preserved by construction on every transition:

• Page-in (fault handling): the pseudocode sets `IPT[victim]` to the new `(pid, vpn)` and inserts `victim` into the corresponding hash bucket in the same atomic critical section, and if the victim frame held a prior page, it is first removed from its old bucket. Both updates happen together, so the invariant is never observed broken between them (under appropriate locking).
• Lookup: the walk over the hash chain examines only frames whose bucket matches `hash(pid, vpn) mod H` — by the invariant, any frame actually holding `(pid, vpn)` must appear in exactly that chain, so the walk cannot miss a true match, and the explicit equality check (`pid` and `vpn` compared, not just the hash) guarantees no false positive is returned despite possible hash collisions.
• Eviction consistency: removing a frame from its chain before repurposing it prevents a stale chain entry from ever pointing to a frame that no longer holds the page the chain implies — this is the classic "unlink before reuse" discipline that keeps a hash-with-chaining structure sound under concurrent mutation.

Together these ensure translation is both sound (never returns a wrong frame) and complete (finds the correct frame whenever one exists) — the two properties any address-translation mechanism must guarantee.

Consider a tiny machine with `F = 8` physical frames and a hash table with `H = 4` buckets, using `hash(pid, vpn) = (pid * 31 + vpn) mod 4`. Two processes, PID 3 and PID 7, are running. Initial IPT state (after some running time):

Bucket contents (chains), computed from `hash`:

• `hash(3,10) = (93+10) mod 4 = 103 mod 4 = 3` … wait — recompute carefully: `3*31=93`, `93+10=103`, `103 mod 4 = 3`. So frame 0 actually belongs in bucket 3, not bucket 2. Let's redo all four honestly:

Interesting — with this particular hash function and these particular keys, everything collides into bucket 3 (since `31 mod 4 = 3` and `pid*31 mod 4 ≡ -pid mod 4`, a poor choice that shows exactly the worst-case risk discussed above). Bucket 3's chain is therefore: `0 → 2 → 3 → 5 → 7 → NIL` (order by insertion time).

Query: translate `(pid=7, vpn=6)`. 1. Compute `hash(7,6) = (7*31+6) mod 4 = 223 mod 4 = 3`. 2. Walk bucket 3's chain: frame 0 → check `IPT[0] = (pid 3, vpn 10)` — no match. 3. Frame 2 → `IPT[2] = (pid 7, vpn 2)` — PID matches, VPN doesn't — no match. 4. Frame 3 → `IPT[3] = (pid 3, vpn 14)` — no match. 5. Frame 5 → `IPT[5] = (pid 7, vpn 6)` — match. Return frame 5. This required 4 comparisons despite there being only 5 valid entries total in an 8-frame table — because the hash function failed to spread keys across buckets, this lookup degraded toward the `O(F)` worst case rather than the `O(F/H) = O(2)` expected case. This is precisely why real systems (e.g., historical PowerPC and PA-RISC IPT implementations) invest in stronger, well-mixed hash functions (often incorporating multiplicative or bit-mixing hashes on the full `(pid, vpn)` bit pattern) — a bad hash silently converts the "cheap search" promise into a linear scan.

Query: translate `(pid=3, vpn=99)` — a page not resident. 1. `hash(3,99) = (93+99) mod 4 = 192 mod 4 = 0`. 2. Bucket 0's chain is empty (`NIL` immediately). 3. Result: PAGE_FAULT — correctly reported with zero wasted chain traversal, since this key hashed to a different, empty bucket. This illustrates that a good hash also speeds up fault detection for genuinely absent pages, by not forcing a full-table scan to conclude absence.

The inverted page table emerged from real engineering pressure: as address spaces grew from 16-bit and 32-bit to 64-bit, forward page-table structures — even multilevel ones — threatened to impose unacceptable per-process metadata overhead on machines with comparatively modest physical RAM. IBM's System/38 (and later AS/400) and Hewlett-Packard's PA-RISC architecture were among the earliest commercial systems to adopt hashed, frame-indexed translation as a core architectural feature rather than an OS-level convenience, followed by IBM's PowerPC family, which offered inverted, hashed page tables as a standard hardware-supported translation mode alongside conventional schemes.

Historically, PowerPC, PA-RISC, and IBM's System/38 and AS/400 lineage used inverted, hashed page tables as their primary or a supported hardware translation mechanism, precisely because these architectures targeted machines where controlling per-process table memory mattered more than guaranteeing worst-case-bounded lookup latency. The design remains conceptually important anywhere the same tension recurs: systems with enormous virtual address spaces (64-bit) but comparatively constrained or cost-sensitive physical memory, including some embedded and specialized server platforms. More broadly, the inverted-page-table idea is a canonical teaching example of a space/time tradeoff via indexing direction: choosing what to index by (physical resource vs. logical/virtual identifier) fundamentally changes both the storage bound and the access pattern, a pattern that recurs in database indexing, cache design, and distributed hash tables. Modern 64-bit commodity systems (x86-64, ARM64) mostly favor multilevel forward tables combined with huge pages and large, multi-level TLBs — because those architectures optimize for guaranteed-bounded lookup depth over minimal table footprint — but understanding the inverted alternative sharpens intuition for why multilevel tables were built the way they were, and for the general principle that a table's index should match the resource you are trying to bound.

Ask the tutor: How would you redesign an inverted page table's hash function to guarantee a provably bounded worst-case chain length, and what would that cost in space or update complexity?