CS 3330: Lecture 2014-11-13: Address Translation

This page does not represent the most current semester of this course; it is present merely as an archive.

Basic View (9.6.1–9.6.2)

An address can be split into it's p low-order bits (the page offset) and the remaining higher-order bits (the page number). A virtual address and it's physical address counterpart have the same page offset (VPO = PPO) but different page numbers (VPN ≠ PPN).

There is something called a page table, one for each user-space process. It stores page table entries: struct PTE { bool valid; PPN pagenum; }. Each PTE takes about as many bytes as a physical address (because it is faster to have values stored in multiples of 4 bytes), and there are 2^n-p of them.

The page table is stored in physical memory (always; it is never paged out to disk while the owning process is running). There is a register in the CPU called the page table base register (PTBR) that tells the memory management unit (MMU) where to find the page table. The PTBR can only be accessed if the CPU is in kernel mode.

Because the page table is in memory, it benefits from the cache hierarchy; however, because it is involved in every single address lookup, we often want it to have an even faster cache than L1. Thus, we have a translation lookaside buffer (usually called just the TLB) which is just a small, highly-associative cache used only for page table accesses. Because of this cache, virtual addresses can be split into a tag, a set index, and a block offset, sometimes called the “TLB tag”, “TLB index” and VPO.

Multi-level Page Tables (9.6.3)

The page table is big. Even with 4K pages and only 32-bit addresses, there are still 2²⁰ PTEs for 4MB of page table. For some processes that is more than the total address space of the running program.

To keep from filling up memory with page tables, we have multi-level page tables. For example, a 2-level page table might split up a 32-bit address with two 10-bit page numbers and a 12-bit page offset, like so: aaaaaaaaaa bbbbbbbbbb oooooooooooo.
The highest-order bits (aaaaaaaaaa) are the page number for a page table in memory; because there are only 10 bits, we only need 1024 page table entries. Those entries, however, do not store physical addresses of the value we want; they store physical addresses of another page table, one indexed by the next ten bits (bbbbbbbbbb). One way of thinking about this is with the following C-like pseudocode:

typedef PPN uint20;

struct PTE { bool valid; PPN pageNum; }
struct midPTE { bool valid; void* tableAddress; }

datum readAddress(void* address) {
    if (TLB.contains(address)) 
        return memory.read(TLB.get(address));
    
    vpn1 = (address>>22)&0x3ff;
    midPTE a = memory.read(CPU.ptbr + sizeof(midPTE) * vpn1);
    if (!a.valid) pageFault(address);

    vpn2 = (address>>12)&0x3ff;
    PTE b = memory.read(a.tableAddress + sizeof(midPTE) * vpn2);
    if (!b.valid) pageFault(address);
    
    void* address = (b.pageNum<<12) | (address & 0xfff);
    
    return memory.get(address);
}