Kernel 3: Virtual memory

Overview

In lecture, we discuss virtual memory.

Process isolation says every computer resource is protected
Some resources are protected by hiding them
- Unprivileged processes cannot access them directly
- The kernel provides abstractions of these resources
- For example, only the kernel gets direct access to input/output devices like disk drives and keyboards; processes get access to a file abstraction instead
- Access to the resource requires system calls
- This works best for resources that are slow or rarely accessed
Some resources are protected by adding privilege checks to hardware
- Unprivileged processes do access the processor (CPU instructions) and primary memory directly
- These resources are fast and constantly accessed
- Requiring explicit kernel intervention would slow the computer tremendously

Depends on the resource
Processor time: Process must not monopolize processor indefinitely
- Kernel configures timer interrupt
Primary memory: Process must not access memory outside its isolated domain
- How to give different processes different views of memory?
- How to define a domain?
- How to enforce a domain?

Processor accesses memory through a layer of indirection called virtual memory
Virtual memory mapping 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 mapping function processes use
- Process mapping functions only grant access to the physical memory containing process data
- Only the kernel can change mapping functions

How can virtual memory protect one process’s data from another process?
- The kernel configures different mapping functions 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 an identity mapping function \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