Systems Research and Architecture SRA
a SRA Theses AMD64 SW-controlled TLB

Demystifying the TLB: Software-Controlled Address Translation on AMD64

image

Manual insertion of entries into the TLB [Generated with AI].

Context

Nearly all modern computer system implement some kind of virtual memory to isolate processes from each other. The most common implementation is paging, where both the physical address space ("the actual memory addresses") and virtual address spaces are divided into equally sized blocks, called page frames and pages (typically 4 KiB). A virtual address space is then defined as mapping from pages to page frames. Memory accesses are resolved transparently for the running application by the memory management unit (MMU) as part of the CPU.

Caused by the huge scale and the sparsity of virtual address spaces, multi-level page tables (basically a tree structure) are used to describe the mapping. The most recent AMD64 implementation provides virtual memory as wide as 57 bits, backed by 5 levels of page tables. As a result, each memory access would require 5 additional memory accesses to look up the physical memory address before performing the actual memory access. To make this actually usable, the translation lookaside buffer (TLB) caches recently used translations (page→page frame). The insertion and eviction of entries to/from the TLB happens entirely in hardware and is treated as a black box in modern architectures.

Historically, certain MIPS processors featured a SW-managed TLB, which gives full address translation control to the operating system. On a TLB miss, the CPU invokes a corresponding handler, which has to manually insert an entry to the TLB. Due to the high overhead, this approach was never widely adopted, despite its flexibility to use alternative data structures to describe the virtual address space instead of page tables.

Problem

Things have changed since the times of MIPS: The amount of memory per system has increased, page tables have become deeper, CPUs have become significantly faster, but memory latency has not kept pace. Additionally, with the emerging trend of memory disaggregation (where memory is physically separated from compute nodes), the amount of memory per machine becomes even bigger but the latencies increase. These changes motivate revisiting alternative TLB management approaches.

Better control and understanding of the TLB can help keep the costs of memory virtualization under control. The use of alternative mapping data structures for "higher latency" remote memory may be beneficial, e.g., hash tables or inverted page tables. Also, it would be helpful to know which entries are currently cached inside the TLB. With knowledge of the eviction policy, costly TLB shootdowns could be reduced.

Goal

The goal of this thesis is to develop an evaluation platform for SW-based TLB management on recent AMD64 hardware. Because the microarchitecture does not support this kind of TLB management natively, we have to use a trick: During normal execution, the CPU core operates without an active page table mapping. All address translations are served exclusively from the TLB. In the case of a TLB miss, this will lead to page fault, which transfers control to the operating system. The fault handler assembles a temporary page table with only the mapping we want to insert, issues a read/write to load the entry into the TLB, and removes the mapping again.

To reduce initial complexity, we restrict our implementation to the user space half of the address space. We retain the existing page tables as a backing data structure, but they no longer directly drive address translation. This makes the changes less intrusive, and we do not need to update all places that interact with the page tables.

The thesis could follow these key steps:

  1. Getting started: Reproduce an existing proof-of-concept for manual insertion and set up a suitable development environment in qemu and on physical hardware (low-level hardware behavior, such as TLB characteristics, may differ between emulation and real hardware).
  2. Efficient insertion: What is the best way to bring an entry into the TLB? How to deal with Supervisor Mode Access Prevention (SMAP)? Is a prefetch instruction sufficient?
  3. Implementation: Separate the user-space page tables from actual address translation. Install a handler that performs TLB insertion when a fault occurs.
  4. Threading: Extend the implementation to multi-threading applications, which will require a separate set of faked page tables per thread to prevent interferences.
  5. Evaluation: Evaluate the functional properties of your implementation using suitable test applications and benchmarks.

Topics: C, Linux kernel, virtual memory, TLB

References