Virtual memory, TLBs and protection

Virtual memory gives each program the illusion of a large, private, contiguous address space, while the hardware and operating system map that space onto physical memory, which is shared, fragmented and smaller. It does three jobs at once. It protects programs from one another and the operating system from programs, because a program can reach only the physical pages its mappings allow. It simplifies memory management, because a program can be loaded anywhere and grow without moving. And it lets memory act as a cache for storage, keeping only the pages in use in DRAM. Architecturally, virtual memory is another level of the hierarchy, with its own blocks, called pages, its own tag lookup, the page table, and its own cache of translations, the translation lookaside buffer.

CMP-229 introduced the idea. This lesson looks at how RISC-V implements it and what it costs. The question is live for the NS-5: Core A has no memory management unit, only physical memory protection, while Core B supports page-based virtual memory. Northway's security review wants the network stack, which talks to the outside world, isolated from the classifier and the bootloader, so that a flaw in one cannot corrupt the others. Maren needs to know what each core can offer.

Pages and page tables

Virtual and physical memory are divided into fixed-size pages, commonly 4 KiB. A virtual address consists of a virtual page number and a page offset; translation replaces the virtual page number with a physical page number and keeps the offset. The mapping for each process is held in a page table in memory, maintained by the operating system. Each page table entry holds a physical page number and flag bits: valid, readable, writable, executable, user-accessible, and bits the hardware sets when the page is accessed or written, which the operating system uses to choose pages to evict and to know which must be written back to storage.

A single flat table would be enormous: a 32-bit address space of 4 KiB pages needs a million entries per process, most of them unused. Real systems use multilevel, or hierarchical, page tables. RISC-V's Sv32 scheme for 32-bit systems splits the 20-bit virtual page number into two 10-bit fields. The first indexes a 4 KiB root table of 1,024 entries; the chosen entry points to a second-level table, which the second field indexes to find the leaf entry. Second-level tables exist only for regions actually in use, so a small program needs only a root table and a few leaves. The 64-bit schemes, Sv39, Sv48 and Sv57, use three, four and five levels of 512-entry tables. A non-leaf entry may also be marked as a leaf itself, mapping a large page of 4 MiB in Sv32 or 2 MiB and 1 GiB in Sv39, which cuts translation overhead for big regions.

The translation lookaside buffer

Walking a two-level table needs two extra memory reads for every access, three or four for 64-bit schemes, which would multiply memory traffic. The translation lookaside buffer, TLB, is a small cache of recent translations, typically holding 16 to 64 entries in the first level, often fully associative, with larger second-level TLBs of hundreds to a few thousand entries in high-end cores. On a TLB hit, translation costs nothing extra; on a miss, a hardware page table walker, or in some architectures a software handler, reads the page table and refills the TLB. RISC-V specifies the page table format so that hardware can walk it, and most implementations do.

TLB reach, the amount of memory the TLB can map at once, is the number of entries times the page size: 64 entries of 4 KiB pages cover only 256 KiB. Programs whose working set exceeds the TLB reach suffer a steady stream of TLB misses even if their data fit in the cache. Large pages are the main cure: one 2 MiB page entry covers as much as 512 small ones. Database and scientific servers often use large pages for exactly this reason, and Dana finds that enabling them on the aggregation servers cuts TLB misses by more than ninety percent.

Page faults

If the walk finds an entry that is invalid, or whose permissions forbid the access, the processor raises a page fault, a precise exception of the kind described in lesson 3. The operating system's handler decides what it means. The page may be valid but not yet in memory, in which case the handler reads it from storage, updates the entry and resumes the faulting instruction. The page may be one the program is allowed to write but which is currently shared and marked read-only, the copy-on-write technique used when processes fork; the handler copies it and resumes. Or the access may be a genuine error, in which case the program is terminated. Because a page fault that reaches storage costs millions of cycles, page replacement policies in the operating system work hard to keep each process's working set in memory.

Protection and privilege

Translation provides protection only if programs cannot change their own mappings. RISC-V defines privilege modes: machine mode, the most privileged, for firmware; supervisor mode for the operating system kernel; and user mode for applications. Only supervisor or machine mode can write the satp register that points to the page table, and page table entries carry a user bit, so that user code cannot touch kernel pages and, by default, the kernel does not accidentally execute or access user pages. Executable and writable permissions are separate, so a system can enforce that no page is both writable and executable, which blocks a common class of code-injection attacks. Environment calls and exceptions are the controlled doors through which user code enters the kernel.

Small embedded processors often lack a memory management unit altogether. RISC-V's physical memory protection, PMP, gives machine-mode firmware a handful of region registers, typically 8 or 16, each specifying an address range and read, write and execute permissions that apply to lower privilege modes. PMP cannot translate addresses or give each task its own address space, but it can confine an untrusted task to its own code and data regions. For the NS-5, Core A could run the network stack in user mode inside a PMP region, with machine-mode firmware switching region settings on each task switch; Core B could give each task a full virtual address space with per-page permissions. The security reviewers accept either design, but prefer the finer granularity of pages.

Translation and caches together

The cache and the TLB must cooperate. If the cache is indexed and tagged with physical addresses, every access must wait for translation before the cache lookup, adding the TLB's latency to the hit time. Most first-level caches therefore use virtual indexing with physical tagging: the index bits are taken from the page offset, which is the same in virtual and physical addresses, so the cache set can be read in parallel with the TLB lookup, and the physical tag from the TLB is compared at the end. This works only if the index and block offset fit within the page offset, which limits a cache to the page size times its associativity: with 4 KiB pages, a 32 KiB first-level cache must be at least eight-way set-associative. That constraint is one reason first-level caches have stayed small and highly associative.

The program below performs the same walk on a simulated page table, shows a fault for an unmapped page, and then measures a 16-entry TLB on two reference streams: the classifier's, which touches a handful of pages repeatedly, and a pathological stream that cycles through 24 pages, more than the TLB can hold.

# Sv32 address translation with a two-level page table and a small TLB
PAGE = 4096
mem = {}                                   # physical word address -> 32-bit page table entry

def pte(ppn, flags): return (ppn << 10) | flags
V, R, W, X, U = 1, 2, 4, 8, 16

root = 0x80000                             # physical page number of the root table
mem[root * PAGE + 4 * 0x001] = pte(0x80001, V)                  # VPN[1] = 1 -> second-level table
mem[0x80001 * PAGE + 4 * 0x023] = pte(0x9ABCD, V | R | W | U)   # VPN[0] = 0x23 -> data page

def walk(va):
    vpn1, vpn0, off = va >> 22, (va >> 12) & 0x3FF, va & 0xFFF
    e1 = mem.get(root * PAGE + 4 * vpn1, 0)
    if not e1 & V: return None, 1
    e0 = mem.get((e1 >> 10) * PAGE + 4 * vpn0, 0)
    if not e0 & V: return None, 2
    return ((e0 >> 10) << 12) | off, 2       # two memory reads for the walk

va = 0x00423A44
pa, reads = walk(va)
print(f"VA 0x{va:08x}: VPN[1]=0x{va>>22:x} VPN[0]=0x{(va>>12)&0x3FF:x} offset=0x{va&0xFFF:x} -> PA 0x{pa:09x} ({reads} table reads)")
print("VA 0x00424000:", "page fault" if walk(0x00424000)[0] is None else "mapped")

# TLB: 16 entries, fully associative, LRU, on the classifier's page reference stream
def tlb_hit_rate(pages, entries=16):
    tlb, hits = [], 0
    for p in pages:
        if p in tlb: hits += 1; tlb.remove(p)
        elif len(tlb) == entries: tlb.pop(0)
        tlb.append(p)
    return hits / len(pages)

stream = []
for frame in range(50):
    for i in range(2048):                   # code page, two data pages per 1024 samples, stack page
        stream += [0x400, 0x500 + i // 1024, 0x520 + i // 1024, 0x7FF]
walk_cost = 2 * 10                          # two table reads at 10 cycles each
for name, s in (("classifier", stream), ("24-page round robin", [0x600 + k % 24 for k in range(100000)])):
    h = tlb_hit_rate(s)
    print(f"{name:20s} TLB miss rate {1 - h:.5f}; translation adds {(1 - h) * walk_cost:.3f} cycles per access")

VA 0x00423a44: VPN[1]=0x1 VPN[0]=0x23 offset=0xa44 -> PA 0x09abcda44 (2 table reads)
VA 0x00424000: page fault
classifier           TLB miss rate 0.00001; translation adds 0.000 cycles per access
24-page round robin  TLB miss rate 1.00000; translation adds 20.000 cycles per access

The classifier's working set is a code page, two input pages, two output pages and a stack page, so after a few compulsory misses the TLB almost never misses and translation costs essentially nothing. The round-robin stream is the worst case for an LRU TLB: with 24 pages cycling through 16 entries, each page is evicted just before it is needed again, every access misses and translation adds 20 cycles to each one. Real server workloads fall between these extremes, which is why TLB misses can account for a noticeable share of their cycles and why large pages help.