Katkat
Back

Trace Virtual Address Translation Through TLBs, Page Tables, and Caches

Chicago Trading CompanySoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

This question tests the understanding of memory hierarchy and virtual memory translation, specifically the interactions between TLBs, page tables, and hardware caches.

Scenario

Assume a system with a 48-bit virtual address space, 4KB pages, and a 4-level page table structure (each page table level consumes 9 bits of the virtual address). A physical address is 40 bits.

Task

  1. Describe the structure of the virtual address bits (How many bits for Page Offset, L4 index, L3 index, L2 index, and L1 index?).
  2. Trace the step-by-step process of a CPU executing a load instruction when there is a TLB miss but the data is present in the L1 Data Cache. Explain which component handles the translation and how the physical address is finally formed.
  3. Identify the specific point in this flow where the hardware determines if the process has read permissions for the memory segment.

Constraints & Context

  • Page Table Entry (PTE) size: 8 bytes.
  • Assume a cold TLB and a warm L1 Data Cache.
  • Clearly distinguish between a TLB hit/miss and a Cache hit/miss.

Example

If a virtual address 0x000012345678 is accessed:

  • How does the MMU interpret the bit fields to start the walk?
  • If the PTE at the final level has the 'R' bit set to 0, what exception is raised and at what stage of the hardware cycle?

Hints

Hint 1

Recall that 4KB pages require 12 bits for the offset, and the remaining 36 bits are divided equally among the 4 levels of the page table.

Hint 2

A TLB miss forces a page table walk starting from the CR3 register (or equivalent root table pointer), which uses the high-order bits of the virtual address to index each level.

Hint 3

Data caching happens using physical addresses only after translation is complete; if the TLB miss occurs, the translation must resolve before the L1 data cache can be probed.

Follow-up questions

  • How would the introduction of 'Huge Pages' (e.g., 2MB) change the depth of the page table walk and the contents of the TLB?
  • What information must be cleared or updated in the TLB when the OS performs a context switch between two processes?
  • Explain the 'TLB Shootdown' problem in a multi-core system when one core changes a page table entry.