Page Tables
As we've seen before, the goal of this unit is to provide a layer of indirection between addresses and physical memory, which lets each process (which is an unprivileged entity) have a different view of memory. We achieve this goal by mapping virtual pages to physical pages.
Page tables are what let us actually convert a virtual address to physical address. A page table is like an array of pointers.
Single level page table
Let's first consider a single level page table. Here, a virtual address contains one index into the page table and an offset that is always 12 bits. When we use that index to find the corresponding entry in the page table page, we get a physical page address. The offset from the virtual address tells us the offset into the physical page.
Question: Why is the offset 12 bits?
Answer: We define the size of a page to be 4096 = 2^12 bytes. We want to be able to index into any byte of a destination physical page. So, we need 12 bits to represent every possible offset.
Question: Why is a single level not good enough?
Answer: Because we would need 2^39 bytes of data, which is too much memory! 2^39 = 2^36 * 2^3. The 2^36 comes from the maximum value the index can represent (an address is 64 bits and we reserve 12 bits for the offset, so we have 36 bits remaining for the index). The 2^3 comes from an address being 2^3 = 8 bytes.
x86-64 page tables
As we just saw, a single level page table takes up a lot of space! We can save some space by using multiple levels. We can think of a multi-level page table structure as a tree. Multiple levels leads to less space because when we look up the physical page for a given virtual address, we may visit a branch of the tree that tells us there's actually no valid physical page for us to access. In that case, we just stop searching. So, multiple levels means we can have a sparse tree.
Consequences for virtual addresses
The x86-64 architecture uses 4 levels. This is reflected in the structure of a virtual address:
| 63-48 | 47-39 | 38-29 | 29-21 | 20-12 | 11-0 |
|---|---|---|---|---|---|
| L4 | L3 | L2 | L1 | OFFSET |
In x86-64 virtual address has 64 bits, but only the first 48 bits are meaningful. We have 9 bits to index into each page table level, and 12 bits for the offset. This means 16 bits are left over and unused.
Question: Why does each index get 9 bits?
Answer: Because the size of one page is 2^12 bytes, and each page table page entry is an address which has 2^3 bytes. 212/23 = 2^9 entries per page. We want to be able to index into any given entry, which means we need 9 bits.
%cr3
We store the physical address of the top level (L4) page table in a special register: %cr3.
Question: Why does %cr3 store a physical address, when every other register stores a virtual address?
Answer: Page tables are used to convert virtual addresses to physical addresses, so if we stored our top level page table address as a virtual address then we wouldn't know how to convert it to a physical address!
The lookup process
A successful lookup (finding a physical address from a virtual address) goes as follows:
- Use
%cr3and the L4 index from the virtual address to get the L3 page table address - Use the L3 page table address and the L3 index to get a L2 page table address
- Use the L2 page table address and the L2 index to get a L1 page table address
- Use the L1 page table address and the L1 index to get the destination physical page
- Use the destination physical page and the offset to get actual physical address within that destination physical page
Flags
Each entry in a page table is an address with the following structure:
| 63 | 62-48 | 47-12 | 11-3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|
| NX | Physical address | U | W | P |
Bits 0-2 contain the P (present), W (writable), and U (user-accessible) flags. However, we can also have other flags, like the NX (non-executable stack) bit, which prevents us from executing instructions on the stack. This is important for preventing buffer overflows!
Again, page table entries don't have an offset because we used the physical addresses they store to find the start of another page table page or a destination physical page. We use the bits in a virtual address to access specific locations in those pages.
WeensyOS
The goals of pset 4 are to add process isolation, and implement the fork and exit system calls. In the handout code, there is no process isolation because each process has the same page table!
We run WeensyOS in QEMU, which emulates hardware for an x86-64 architecture.
Kernel and user addresses
The kernel (designated as K) lives in addresses that start with 0x40000, while processes live in the upper addresses of virtual memory, starting at 0x10000.
We also have hardware pages (designated as R) in the middle of the physical address space. This is because Bill Gates once said "no one should ever need more than 640K of memory", and processors would give us 1 MB of memory. The hardware lives in the upper portion of that memory (between 640 K and 1 MB).
The hardware includes one page marked as C for the CGA console. The console is an instance of memory mapped I/O. The console is not memory, but behaves like it; we can write output to the console by writing values in memory
Control transfer
We want to be able to switch into the kernel from user space and vice versa. All of these entry/exit points are defined in k-exception.s. You won't need to modify this file, but you should understand what it does.
When we have an exception (e.g. a timer interrupt or a segfault), or the user makes a syscall, we need to switch into the kernel. First, we save processor state by saving each register. The process's %rsp is pre-saved on the kernel stack. Then, we jump into a specific place in the kernel, which is determined by the entry code in k-exception.s.
When we want to give control back to the user process, we simply restore the registers we already saved.