x86-64 doesn't map a virtual address to a physical one with a single lookup -- it walks a 4-level tree of page tables: PGD -> PUD -> PMD -> PTE. Each level's entry either points to the next level's table, or (at the PTE level) to the actual physical page frame. If ANY level's entry is missing, the CPU raises a page fault -- there's simply no mapping to follow.

A virtual address is split into 5 fields (a simplified version of the real layout -- x86-64 also supports a 5-level mode and canonical-address sign extension, both skipped here to keep the walk itself the focus):

• bits [47:39] -- PGD index (9 bits)
• bits [38:30] -- PUD index (9 bits)
• bits [29:21] -- PMD index (9 bits)
• bits [20:12] -- PTE index (9 bits)
• bits [11:0] -- page offset (12 bits -- a 4 KiB page)

decompose(vaddr) (given) splits a virtual address into exactly those 5 fields. Each level of the page table is a plain dict: {index: next_level_dict}, except the PTE level, whose dict maps {index: physical_frame_number}.

Implement translate(pgd, vaddr): walk all 4 levels starting from the root pgd dict.

• If any level's index isn't present in that level's dict, raise PageFault(vaddr, level) naming which level was unmapped ("pgd", "pud", "pmd", or "pte").
• On success, return the physical address: the resolved frame number shifted into place, combined with the original page offset.

Example

pgd = {1: {2: {3: {4: 0xABCDE}}}}
vaddr = make_vaddr(pgd_idx=1, pud_idx=2, pmd_idx=3, pte_idx=4, offset=0x123)
translate(pgd, vaddr)   # -> (0xABCDE << 12) | 0x123

The missing link: caching the walk (TLB)

Walking 4 memory-resident tables on EVERY memory access would be far too slow -- real CPUs cache recent translations in a small hardware cache called the TLB (Translation Lookaside Buffer), and only fall back to the full walk on a TLB miss. Implement:

• TLBCache.lookup(vaddr) / .insert(vaddr, frame) / .invalidate(vaddr) -- all keyed on the virtual PAGE number (vaddr >> PAGE_SHIFT), not the full address. Two addresses on the same page must share one cache entry -- that's the entire point of caching at page granularity instead of per-byte.
• translate_cached(pgd, vaddr, tlb) -- consult tlb first; only fall back to a real translate() walk on a miss, then cache the result.

invalidate matters because a TLB is a cache of a mutable structure: if the page table changes (a page gets remapped or unmapped) and the TLB isn't told, it will happily keep serving the OLD, now-wrong translation forever. This exact bug class is why real multi-core CPUs need a "TLB shootdown" -- an interrupt telling every OTHER core to invalidate a translation too, not just the core that made the change.

Constraints

• Stop and raise PageFault at the FIRST unmapped level you encounter -- don't keep walking past it.
• The final physical address is (frame << 12) | offset -- the frame number identifies a 4 KiB-aligned physical page, and the offset locates a specific byte inside it.
• A TLB hit must never consult pgd at all -- not even to double-check.

Real-world grounding

• The actual PGD -> P4D -> PUD -> PMD -> PTE walk used to build the fault message when a real page fault occurs: arch/x86/mm/fault.c (search p4d_offset/pud_offset/pmd_offset/pte_offset_kernel).
• The generic, architecture-independent page table walker used throughout the kernel for things like /proc/pid/pagemap and NUMA migration: mm/pagewalk.c

Real x86-64 also has an optional 5th level (P4D, for a 57-bit address space) inserted between PGD and PUD, transparently collapsed away when 5-level paging isn't in use -- which is exactly why this exercise's 4-level version is still an accurate model of the common case. The kernel's own TLB invalidation logic lives in arch/x86/mm/tlb.c, including the cross-core shootdown this exercise's invalidate() is a single-core model of.