26 Virtual Memory, Multi-Table-VM, Translation-Lookaside-Buffer, Memory Protection

Lecture from: 02.06.2023 | Video: YT

Virtual Memory

This lecture continues the discussion on virtual memory, focusing on the challenges of page table management and the mechanisms used to address them, such as Translation Lookaside Buffers (TLBs). It also explores the crucial role of virtual memory in providing memory protection and the interaction between virtual memory and caching systems.

Recall: Virtual Memory Fundamentals

Virtual memory provides each process with the illusion of a large, private address space, much larger than the physical memory available. This is achieved through indirection and mapping, where virtual addresses generated by the program are translated to physical addresses. Key components include:

• Pages and Frames: Virtual address space is divided into pages; physical address space into frames.
• Page Table: An OS-managed data structure that stores the mapping between virtual pages and physical frames.
• Page Fault: An exception triggered when a program accesses a virtual page not currently resident in physical memory. The OS then typically loads the page from disk (demand paging).

Address Translation Recall

A virtual address is split into a Virtual Page Number (VPN) and a Page Offset. The VPN is used to find a Page Table Entry (PTE) in the page table. The PTE, if valid, provides the Physical Page Number (PPN). The PPN is then combined with the original Page Offset to form the physical address.

Page Table Size Issue & Multi-Level Page Tables

As discussed, a single-level page table for a large virtual address space (e.g., 64-bit) would be impractically enormous (e.g., 16 Petabytes).

The solution is multi-level (hierarchical) page tables. The VPN is further divided to index through several levels of page tables. Only the top-level page table and actively used portions of lower-level tables need to reside in physical memory, significantly reducing the memory footprint of page table structures.

While solving the size problem, multi-level page tables introduce a new performance challenge: multiple memory accesses are now needed for a single address translation.

Page Table Challenges

1. Page Table Size: Addressed by multi-level page tables.
2. Translation Speed: Each instruction fetch or load/store potentially requires multiple memory accesses just for address translation (one per page table level if all intermediate PTEs are in memory, plus page faults if they are not). This significantly degrades performance.

Speeding Up Translation: The Translation Lookaside Buffer (TLB) (= Mapping Cache)

To mitigate the performance overhead of page table walks:

• Idea: Cache recently used Page Table Entries (PTEs) in a specialized hardware structure within the processor.
• This cache is called the Translation Lookaside Buffer (TLB).
• The TLB is a small, fast cache (typically 16-512 entries for L1 TLB, highly associative) that stores recent virtual-to-physical address translations.
• Operation:
  1. When a virtual address is generated, the MMU first checks the TLB for the VPN.
  2. TLB Hit: If the VPN is found in the TLB (a TLB hit), the corresponding PPN is retrieved directly from the TLB. Address translation is fast (e.g., 1 cycle), and no page table walk (memory accesses) is needed.
  3. TLB Miss: If the VPN is not in the TLB, a page table walk must be performed to fetch the PTE from the page table in memory. Once fetched, the PTE is typically installed in the TLB (replacing an existing entry if the TLB is full).
• Locality: Page table accesses exhibit temporal and spatial locality, similar to data/instruction accesses, making TLBs effective.
  • Temporal Locality: Recently accessed pages (and their translations) are likely to be accessed again soon.
  • Spatial Locality: Consecutive instructions or data accesses are often within the same page, reusing the same translation. Large page sizes enhance this.

TLB as a Cache for PTEs

All standard caching concepts apply to TLBs:

• Split TLBs: Separate Instruction TLBs (I-TLBs) and Data TLBs (D-TLBs).
• Multi-level TLBs: L1 TLB, L2 TLB, etc., forming a hierarchy of translation caches.
• Associativity, Size, Replacement Policies: These are key design choices for TLBs.
• Prefetching: PTEs can be prefetched into TLBs.
• Coherence: If PTEs are modified (e.g., by the OS), TLBs in different cores holding stale copies must be invalidated (TLB shootdown).

Handling TLB Misses

• Hardware-Managed TLB (e.g., x86):
  • The hardware (a dedicated “page walker” state machine in the MMU) automatically performs the page table walk to find the PTE in memory.
  • The fetched PTE is then inserted into the TLB by hardware.
  • Pros: No OS intervention (exception) on a TLB miss, allowing instruction execution to stall but potentially overlap with other independent instructions. Specialized hardware like page walk caches can speed up the walk.
  • Cons: Page table structure is rigidly defined by the hardware (ISA). OS has little flexibility.
• Software-Managed TLB (e.g., MIPS):
  • On a TLB miss, the hardware raises an exception.
  • The OS exception handler performs the page table walk in software, fetches the PTE, and explicitly loads it into the TLB.
  • Pros: OS can define flexible page table structures. More sophisticated OS-driven TLB replacement policies are possible.
  • Cons: Higher overhead due to exception handling (pipeline flush, handler execution).

Page Table Challenges (III): When to Translate (Cache Interaction)

The third major issue is the timing of address translation relative to cache access:

• Should address translation occur before accessing the L1 cache, or after (or in parallel)?

• This leads to different cache addressing schemes:

  • Physically Indexed, Physically Tagged (PIPT) Cache: Translation happens first. The physical address is used to index and tag the cache. Simplest, avoids aliasing issues.
  • Virtually Indexed, Virtually Tagged (VIVT) Cache: The virtual address is used to both index and tag the cache. Translation (TLB lookup) only needed on a cache miss or for permission checks. Fastest hit time. Prone to synonym/aliasing problems.
  • Virtually Indexed, Physically Tagged (VIPT) Cache: Index with virtual address bits, but store physical address tags. TLB lookup and cache access can happen in parallel. If (index bits + offset bits) ≤ page offset bits, the index comes purely from the page offset (which is the same in VA and PA), avoiding most aliasing. This is common for L1 caches.

• Synonym (Aliasing) Problem: Occurs when two or more different virtual addresses map to the same physical address.

  • In a VIVT or a VIPT cache where index bits come from the VPN, the same physical data could be cached in multiple locations under different virtual tags/indices. This can lead to data inconsistency if one copy is updated and others are not.

• Homonym Problem: The same virtual address in different processes maps to different physical addresses. Handled by using Process IDs (PIDs) as part of the virtual tag in VIVT/VIPT caches or by flushing the cache/TLB on a context switch.

Memory Protection via Virtual Memory

Beyond providing an illusion of large memory, virtual memory is a cornerstone of memory protection.

• Per-Process Page Tables: Each process has its own independent page table and virtual address space.
• Isolation: A process can only access physical pages that are mapped in its own page table. It cannot directly access or overwrite the memory of another process unless explicitly shared.
• Access Control: PTEs contain permission bits (e.g., Read, Write, Execute, User/Supervisor mode). The MMU checks these bits on every access (often in parallel with TLB lookup). An attempted violation (e.g., writing to a read-only page, user code trying to access a supervisor-only page) triggers a protection fault (exception).

Privilege Levels (e.g., x86 Rings)

CPUs often support multiple privilege levels. In x86, Ring 0 (kernel/supervisor) has the highest privilege, while Ring 3 (user applications) has the lowest. Access to certain pages or instructions is restricted based on the current privilege level. PTEs and Page Directory Entries (PDEs) in x86 contain User/Supervisor (U/S) bits and Read/Write (R/W) bits to enforce this.

Food for Thought: Hardware Unreliability and Protection

The RowHammer phenomenon, where repeatedly accessing DRAM rows can cause bit flips in adjacent rows, highlights a critical security concern. If such a bit flip occurs in a PTE, particularly in the permission bits or the PPN field, it could potentially:

• Escalate a user process’s privilege (e.g., flip U/S bit from User to Supervisor).
• Allow a process to gain unauthorized access to arbitrary physical memory by corrupting the PPN to point to another process’s data or even the OS’s page tables. Google Project Zero demonstrated such an attack, where RowHammer-induced bit flips in PTEs were used to gain kernel-level privileges.

This underscores that higher-level security mechanisms like virtual memory rely on the underlying hardware’s integrity. If hardware is unreliable, these protections can be compromised. The root of security and trust extends down to the physical hardware level.

Virtual Memory Summary

• Virtual memory provides the illusion of “infinite” capacity per process.
• A subset of virtual pages resides in physical memory.
• Page tables map virtual pages to physical pages (address translation).
• TLBs cache these translations to speed up access.
• Multi-level page tables manage the size of page tables.
• Per-process page tables and permission bits in PTEs provide memory protection and isolation.

Virtual memory is a highly successful architectural feature, but its complexity and overhead are growing with increasing memory sizes, diverse memory technologies, and virtualization. This motivates ongoing research into rethinking virtual memory for future systems.

The subsequent part of the lecture was an epilogue and discussion on future computing architectures. This was the “last” lecture. However, there are more on YouTube…