Kernel 3: Page tables

Overview

In lecture, we discuss page tables.

Processor accesses memory through a layer of indirection called virtual memory
Virtual memory is governed by a page table function \mathscr{P} : \textit{VA} \mapsto \textit{PA}
- The addresses used by instructions are virtual addresses in VA
- The contents of memory chips are addressed by physical addresses in PA
- When an instruction accesses virtual address x, the processor accesses physical address \mathscr{P}(x)

Address accesses can cause a fault (a processor exception)
- Really \mathscr{P} : \textit{VA} \mapsto \textit{PA} + 💩
- Fault causes processor to protected control transfer to the kernel
- Uses the same path as timer interrupts
- Kernel can kill process, attempt to patch fault, etc.

How can virtual memory protect kernel data from processes?
- The kernel configures the page table processes use
- Page tables only grant access to the physical memory containing process data
- Only the kernel can change page tables

How can virtual memory protect one process’s data from another process?
- The kernel configures different page tables for each process

The kernel needs access to all memory
It also must query and modify the memory mapping seen by processes (for example, to perform system calls)
- On WeensyOS, the kernel runs with identity mappings: a page table \mathscr{P}_\text{id}(x) = x that grants access to all physical memory
- vmiter helps kernel query and modify memory as seen by a process
- Different operating systems and processor architectures make different choices

Virtual addresses VA range over [0, 2⁶⁴)
- Well, almost (actually [0, 2⁴⁷) ∪ [2⁶⁴−2⁴⁷, 2⁶⁴))
Physical addresses PA range over [0, NUMBER OF BYTES OF MEMORY YOU BOUGHT)
- On my laptop, [0, 2³⁴)
Many many more virtual addresses than physical addresses!
- Potentially complicated to define a mapping function?

x86-64 memory is organized in aligned contiguous ranges called pages
- Mapping functions on x86-64 implemented by a page table
x86-64 page is 2¹² = 4096 contiguous bytes of memory
- Starting at an address that is a multiple of 2¹²
Any virtual page can map onto any physical page
But within a page, addresses map in fixed, piecewise-linear fashion
- All addresses in one virtual page map to the same physical page
- If any address in a virtual page faults, all addresses in the page fault
- Think of pages like fixed bricks—can’t change the mappings within a brick
Mathematically
- \mathscr{P}(p \ll 12) = x \ll 12 for some integer x
- \mathscr{P}((p \ll 12) + o) = \mathscr{P}(p \ll 12) + o whenever 0\leq o <2^{12}

Simplify and speed up hardware
- “Nearby” addresses are translated the same way
Simplify specification of memory mapping functions
- A factor of 2¹² fewer mappings to define
Consequence: Cannot protect memory at finer granularity

x86-64 virtual memory mappings are sensitive to type of access and access privilege
These are specified with permission flags
- PTE_P: The mapping is Present
- PTE_W: The mapping allows Writing (if absent, all accesses must be read)
- PTE_U: The mapping allows Unprivileged/User access (if absent, only kernel can access)
Every process virtual memory mapping function must contain some kernel mappings
- But those mappings should lack PTE_U

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

x86-64 implements virtual memory mappings using four level page table
Data structure: 512-ary tree indexed by parts of the virtual address
Special %cr3 register holds address of current page table
- Changing %cr3 requires privilege
- %cr3 must be a physical address