x86-64 uses a four-level tree: PML4, PDPT, PD, PT. Each non-leaf entry points at the next table; leaf PTEs hold the physical frame plus permission bits (present, writable, user).
c
Loading…
Page Fault Paths
Present bit 0: demand paging or guard page
Writable 0 on store: copy-on-write or protection fault
User 0 in ring 3: kernel-only mapping
For example, virtual 0x00401000 splits into indices that index each table level; a missing present bit stops the walk and raises #PF.
For this exercise, you will simulate a walk that returns a physical address or fault code. This task asks you to model PTE bits explicitly, matching what the OS track's memory manager will install when mapping heap pages.
Working Through the Exercise
Keep the relevant datasheet, ISA manual, or architecture textbook chapter open while you implement. When your output disagrees with the reference trace on the same program, the bug is usually a mis-decoded opcode, a stale register read, or a flag bit left unchanged after arithmetic.
Trace first: walk one failing input by hand before changing random lines
Read the manual: skim the official doc for the mechanism named in this task
Compare baselines: save measurements from the prior step so speedups are honest
For this exercise, you will use those habits while implementing the requirement in the starter code. Microarchitectural product names change across CPU generations, but the control ideas (fetch, bypass, cache lines, vector lanes) stay stable enough to debug from first principles.
Simulate a two-level page table walk (simplified 32-bit x86 paging, 4 KiB pages) for a batch of virtual addresses.
Fixed machine model (simplified from Intel SDM Vol. 3, 32-bit paging):
Page directory: 4 entries, index 0..3. PDEs 1 and 3 are PRESENT (point at page tables PT1 and PT3); PDEs 0 and 2 are ABSENT.
PT1 installs (PTE index -> frame): 1 -> 0x5, 2 -> 0x7, 4 -> 0x9, all present.
PT3 installs: 0 -> 0x10, 3 -> 0x12, all present.
Every other PTE in PT1/PT3 is not present. A PTE present bit 0 means PAGE_FAULT at level 2; an absent PDE means PAGE_FAULT at level 1.
Input (stdin):
First line: N, the number of virtual addresses (1 <= N <= 64).
Next N lines: one 32-bit virtual address in hex, with or without the 0x prefix (scanf %x accepts both).
Behavior per address, in input order:
4-entry fully associative TLB with LRU replacement. Hit -> pa from the cached frame, steps=0. Miss -> walk: absent PDE faults at level 1, not-present PTE faults at level 2; a successful walk costs steps=2 and installs the translation in the TLB (evicting the LRU entry when full). Faulting walks do NOT install a TLB entry.
walk_steps accumulates one step per level visited on every miss (2 for a successful walk, 1 for a level-1 fault, 2 for a level-2 fault).