Inverted Page Tables & Translation

1. The Scaling Problem in 64-Bit Systems

Traditional multilevel page tables scale with the size of the virtual address space. While hierarchical paging successfully eliminates unallocated gaps in 32-bit systems, expanding to 64-bit architectures requires 4, 5, or even 6 levels of page directory walking, introducing heavy memory latency overhead.

Furthermore, every active process requires its own independent page table hierarchy. If a system runs 100 concurrent processes, the collective RAM consumed by page table structures becomes massive.

2. Deep Dive: Understanding RAM Frames vs. Virtual Pages

To understand why inverted page tables exist, we must contrast physical hardware memory against the logical memory abstraction:

• Virtual Pages (VPN): The blocks seen by a running program. A process views memory as a vast, private, contiguous address space (e.g., from address 0x00000000 up to hundreds of gigabytes), but these addresses are purely virtual references.
• Physical Frames (PFN): The actual physical silicon storage blocks in the RAM modules on the motherboard. If a system has 16 GB of physical RAM divided into 4 KB chunks, physical memory consists of exactly 4,194,304 frames (numbered sequentially from Frame 0 to 4,194,303).

In traditional forward-mapped paging, the table is indexed by the Virtual Page Number. Because every process has its own private virtual space, every process must maintain its own private page table. Conversely, an Inverted Page Table indexes memory strictly by Physical Frame Number. Because physical RAM size never changes during runtime, the inverted page table size remains strictly fixed.

3. The Inverted Page Table Solution

Instead of maintaining one page table per process mapping virtual pages to physical frames, the operating system maintains exactly one global page table for the entire machine, containing one entry per physical RAM frame.

4. Why x86-64 Doesn't Use It (And Who Does)

If Inverted Page Tables save so much physical memory, why does standard x86_64 hardware rely on 4-level and 5-level trees instead?

• Predictable Hardware Tree Walks: In x86_64, the CPU MMU walks multi-level directories using deterministic pointer dereferencing in silicon. While it requires 4 memory accesses on a TLB miss, each lookup step is fixed and predictable.
• Hash Collisions Add Latency: In an IPT, because rows are sorted by frame number rather than virtual address, the MMU cannot index the table directly. It must calculate a hash of (PID, VPN). If hash collisions occur, the hardware must chase linked collision chains through memory, introducing variable latency.
• Architectures That Used Inverted Tables:
  • IBM PowerPC (Power Architecture): Uses a hardware-managed Hashed Page Table (HPT). Every memory reference hashes virtual segment identifiers directly to Page Table Entry Groups (PTEGs).
  • Intel Itanium (IA-64): Implemented a Virtual Hash Page Table (VHPT) backed by software TLB miss handling routines.
  • UltraSPARC (Solaris): Relied on software-managed TLBs backed by Translation Storage Buffers (TSBs) structured like inverted hash tables.

5. Can Processes Share Pages?

Yes, but page sharing highlights the biggest trade-off between the two architectures:

• In Multi-Level Paging (Trivial): Sharing is natural. Process A and Process B each have their own independent page tables. Process A points its Level-1 entry to Physical Frame 105, and Process B points its own entry to Physical Frame 105. They can even use different virtual addresses and different protection bits (e.g., Process A is Read-Only, Process B is Read-Write).
• In Inverted Page Tables (Difficult): Because each physical frame has exactly one slot in the global table, that slot can only store one owner tag: [PID | VPN]. If two processes share Frame 105, the table cannot hold both tags simultaneously. To resolve this, systems using IPTs must employ global shared segment IDs (like PowerPC), alias collision lists, or maintain secondary software translation tables in kernel memory.