Kernel 3: Virtual memory and page tables

Full lecture notes on kernel — Textbook readings

Eve’s memory attack

uint8_t* ip = (uint8_t*) 0x40ed0;   // address of `_Z7syscall...` from `obj/kernel.sym`
ip[0] = 0xeb;
ip[1] = 0xfe;
(void) sys_getpid();

Kernel’s response: use vmiter to isolate the kernel

    for (; it.va() < MEMSIZE_PHYSICAL; it += PAGESIZE) {
        uintptr_t addr = it.va();
        int perm = PTE_P | PTE_W | PTE_U;
        if (addr == 0) {
            // nullptr is inaccessible even to the kernel
            perm = 0;
        /***** NEW CODE HERE *****/
        } else if (addr < PROC_START_ADDR && addr != CONSOLE_ADDR) {
            // prevent unprivileged access
            perm = PTE_P | PTE_W;
        }
        // install identity mapping
        int r = it.try_map(addr, perm);
        assert(r == 0);
    }

Virtual memory

• All memory accesses go through a layer of indirection called virtual memory
• Instructions use virtual addresses
• Memory chips use physical addresses
• The virtual-to-physical translation layer is configured by the kernel

Metaphor: Patch panel

Metaphor: Switchboard

Example: SLIVEGOAT

• 0→4, 1→7, 2→8, 3→6, 4→7, 5→8, 6→0
• 0→4, 1→3, 2→2, 3→1, 4→5, 5→6, 6→7, 7→8
• 0→3, 1→2, 2→1, 3→4, 4→5, 5→2, 6→1, 7→1, 8→0

Function notation

• Virtual memory mapping function
  \mathscr{P} : \textit{VA} \times \textit{Priv} \mapsto \textit{PA} + \textit{Fault}
  • When an instruction reads or writes virtual address a, the processor computes \mathscr{P}(a, \textit{curpriv}())
  • If the result is in \textit{PA}, the processor reads or writes that physical memory
  • If the result is in \textit{Fault}, the access was illegal; the processor takes an exception and transfers control to the kernel

Invisibility cloak via virtual memory

• Start with an identity mapping
  • \forall a: \mathscr{P}(a, \textit{priv}) = a
• Change it to fault if an unprivileged process accesses kernel memory
  • \forall a \in \textit{Kernel}: \mathscr{P}(a, \text{UNPRIV}) = \text{FAULT}

Virtual memory performance

• How would you represent a mapping function?
• Constraint: Every memory access uses the mapping function
  • Performance sensitive!
• Speed up lookups by through caching
  • The results of one lookup should apply to nearby addresses too

Paged virtual memory: Look up once per block

• Divide virtual and physical memory into aligned pages
  • x86-64: size 2¹² = 0x1000 = 4096
• Every address within a page is looked up the same way
• Let v be a page-aligned virtual address (a multiple of 2¹²), and 0 \leq o < 2^{12}
• Then
  \mathscr{P}(v + o, \textit{priv}) = \begin{cases} \mathscr{P}(v, \textit{priv}) + o, & \text{if } \mathscr{P}(v, \textit{priv}) \in \textit{PA} \\ \mathscr{P}(v, \textit{priv}), & \text{if } \mathscr{P}(v, \textit{priv}) \in \textit{Fault} \end{cases}

Example: SLIVEGOAT

• “Page” size: 2 letters?
• “Page” size: 3 letters?

x86-64 page tables

• The \mathscr{P} mapping function is defined in a memory structure called a multi-level page table
• Page tables are tries with branching factor 512
• The virtual address \textit{va} determines a path through the trie
• The result is read from the page table memory at the end of the path

vmiter

• The vmiter class examines and modifies the page table structure that implements virtual memory on x86-64
• vmiter(PAGETABLE, VA) constructs a vmiter pointing at virtual address VA in pagetable PAGETABLE
• it.va() returns the vmiter’s current virtual address (i.e., the key)
• it.pa() and it.perm() retrieve \mathscr{P}(\texttt{it.va()}, \textit{priv})
  • it.pa() is the physical address result (if there is one)
  • it.perm() determines which accesses fault
    • If (it.perm() & PTE_P) == 0, all accesses fault
    • If (it.perm() & PTE_W) == 0, write accesses fault
    • If (it.perm() & PTE_U) == 0, unprivileged accesses fault
• it.find(va) and it += N redirect vmiter to point to a different virtual address

vmiter mappings

• it.try_map(pa, perm) changes the mapping for it.va()
• You may only call it.try_map(pa, perm) if it.va() is page-aligned (a multiple of PAGESIZE)
• If it.try_map(pa, perm) succeeds, then afterwards, it.pa() == pa and it.perm() == perm
• it.try_map(pa, perm) can fail (return -1)
  • Because it.try_map might require allocating kernel memory using kalloc!

Multiple page tables with vmiter