9 – Paging
Goal: read the page tables the CPU uses, change them, and use that for the first thing paging buys a kernel: a
stack that cannot overflow silently.
You end up with: translate (what the CPU does on every memory access, in software), map and unmap, kernel
stacks with a guard page, and a real stack overflow (fault=overflow) that ends in the double fault handler of
chapter 5.
Code: course/09-paging/ (chapter 8
plus paging.rs, stack.rs, one more Limine request and a fourth boot check)
What changed: diff -ru course/08-frames course/09-paging (in the repository) shows every line this chapter adds.
Background: four levels of tables
A virtual address on x86-64 has 48 meaningful bits (the 16 above them repeat bit 47). The CPU cuts them into five pieces:
47 39 38 30 29 21 20 12 11 0
+----------+----------+----------+----------+---------------+
| PML4 | PDPT | PD | PT | offset |
+----------+----------+----------+----------+---------------+
9 bits 9 bits 9 bits 9 bits 12 bits
Each 9-bit piece picks one of 512 entries in a table. CR3 holds the physical address of the top table, the PML4. Its entry names the next table (a PDPT), whose entry names a PD, whose entry names a PT, whose entry names the frame. The 12-bit offset is the position inside that frame's 4 KiB. Every table is itself one frame of 512 entries × 8 bytes – which is why chapter 8's allocator comes first: new tables are new frames.
An entry is a physical address plus flags in the bits the address does not need: present (bit 0), writable (bit 1), no execute (bit 63), and a few more. A PD entry can also say huge (bit 7): "I map 2 MiB myself, there is no PT below me" – a PDPT entry the same with 1 GiB. Limine builds the HHDM mostly from 2 MiB pages.
The CPU caches translations in the TLB. Changing an entry does not change the TLB: after removing a mapping we
must tell the CPU with invlpg.
Step 1: entries and tables
An entry is a u64; the address is bits 12–51, everything else is flags. A table is 512 of them, aligned to 4 KiB.
We reach every table through the HHDM – an entry holds a physical address, and PhysAddr::as_mut_ptr from chapter
8 turns it into a pointer:
#![allow(unused)] fn main() { /// The entry numbers of `virt` in the four tables, PML4 first. pub fn indices(virt: u64) -> [usize; 4] { [39, 30, 21, 12].map(|shift| ((virt >> shift) & 0x1FF) as usize) } }
Step 2: translating by hand
translate walks the four levels like the CPU: an entry that is not present ends the walk, a huge entry ends it
early with a bigger page, and the PT entry ends it with a 4 KiB frame:
#![allow(unused)] fn main() { let page_size = match level { 1 if entry.is(Flags::HUGE) => 1 << 30, 2 if entry.is(Flags::HUGE) => 1 << 21, 3 => PAGE_SIZE, _ => { entries = &table(entry.address()).0; continue; } }; }
One trap: in a huge page entry, bit 12 is not part of the address but the PAT bit, which picks the caching type. Limine sets it for the framebuffer. Rounding the address down to the page size removes it:
#![allow(unused)] fn main() { let start = entry.address().0 & !(page_size - 1); }
The reference kernel had exactly this bug until this chapter found it (bug #26).
A new Limine request, EXECUTABLE_ADDRESS, says where the kernel lies physically. It lets a test check translate
against an answer that does not come from our own code.
Step 3: mapping and unmapping
map walks the same way, but a missing table on the way is created – a zeroed frame from chapter 8 (a frame with
old contents would be read as 512 random entries):
#![allow(unused)] fn main() { if !entry.is(Flags::PRESENT) { // a new, empty table: zeroed, or its garbage would be read as entries let new = pmm::alloc_frame_zeroed().ok_or(MapError::OutOfFrames)?; // the tables above allow everything; the last entry decides what the page may do *entry = Entry::new(new, Flags(Flags::PRESENT.0 | Flags::WRITABLE.0)); }
The CPU combines the flags of all four levels: a page is writable only if every entry on the way says so. So
the upper entries allow everything and the last one decides. map refuses an address inside a huge page
(splitting it is possible, but not needed yet), an address that is mapped already, and anything not aligned to
4 KiB.
unmap clears the last entry, flushes the TLB entry, and gives the frame back to the caller:
#![allow(unused)] fn main() { entries[i1] = Entry(0); // the CPU keeps recent translations in its TLB; without this it could go on using the old one unsafe { asm!("invlpg [{}]", in(reg) virt, options(nostack, preserves_flags)) }; }
Empty tables are not freed again – a few frames, and much simpler.
Step 4: a stack with a guard page
Chapter 5 could only fake a stack overflow, by pointing the stack at an unmapped address. Now we can build a stack
whose end really is unmapped. stack::alloc takes a slice of an area reserved for stacks (PML4 entry 510), leaves
its lowest page unmapped – the guard page – and maps the pages above it:
#![allow(unused)] fn main() { for page in 1..=pages { let frame = pmm::alloc_frame_zeroed().ok_or(MapError::OutOfFrames)?; paging::map(guard + page * PAGE_SIZE, frame, Flags::DATA)?; } }
fault=overflow switches to such a stack and calls a function that calls itself forever, 512 bytes deeper each
time:
#![allow(unused)] fn main() { fn deeper(depth: u64) -> u64 { let room = core::hint::black_box([depth; 64]); // 512 bytes of stack per call deeper(depth + 1) + room[0] } }
After 16 KiB the next push lands in the guard page: a page fault. To report it, the CPU would push the exception frame on the same stack – into the guard page again – and that is a double fault, which chapter 4 gave its own stack.
The tests
make test now runs 52 tests in the kernel; seven are new:
an_address_is_four_indices_and_an_offset– the kernel's own address is entries 511, 510, 0, 0;the_kernel_is_where_limine_put_it–translateof a function in the kernel gives the physical address Limine reported;the_hhdm_maps_every_frame_to_itself– and the lower half is empty (chapter 8's page fault at0x62000);a_mapped_frame_appears_at_its_new_address– the first page in an empty 512 GiB region costs exactly three new tables; what is written at the new address is in the frame; mapping twice and unaligned addresses are refused; afterunmapthe address translates to nothing;the_framebuffer_translates_exactly– the PAT bit of bug #26;huge_pages_are_not_split– an HHDM address inside a 2 MiB page;the_stack_is_mapped_and_its_guard_page_is_not– and two stacks do not overlap.
A fourth boot check runs fault=overflow and wants the double fault on its own stack, with the last page fault in
the guard page.
Run it
cd course/09-paging
make run
After the memory lines of chapter 8:
Paging: PML4 at 0x7f7d000; kmain at 0xffffffff800104d0 is physical 0x7de44d0 (the kernel starts at physical 0x7dd4000)
Mapped frame 0x62000 at 0xfffffe0000000000: wrote 0xbeef there, read 0xbeef through the HHDM
Stack: 16 KiB below 0xffffff0000005000, its guard page at 0xffffff0000000000 is mapped: no
The exact physical addresses depend on the firmware and on the size of your kernel. And the real overflow:
KERNEL_CMDLINE=fault=overflow make run
running on the double fault stack: yes (rsp=0xffffffff800240d0)
KERNEL PANIC: panicked at src/interrupts.rs:153:5:
EXCEPTION: DOUBLE FAULT (code 0x0), last page fault at 0xffffff0000000be8
rip=0xffffffff800099e7 cs=0x8 rflags=0x286 rsp=0xffffff0000000bf0 ss=0x10
The page fault was at …0be8, inside the guard page …0000–…0fff; the stack pointer rsp of the interrupted
code was in it too.
What can go wrong
- The guard page is mapped as well: start the loop in
stack::allocat 0, and the overflow does not stop at the end of the stack. Here it ends one page further down, atlast page fault at 0xfffffeffffffff28– below the stack area, where nothing is mapped. A stack allocated before it would have been overwritten without a sound. - The TLB is not flushed: without
invlpginunmap, the old translation survives. Reading the page right afterunmapstill gives0xbeef; withinvlpgthe same read is a page fault (page not present, read). - A new table without the writable flag: the page itself says writable, but one entry above it does not, and
the first write is a
protection violation, write. All four levels count. - A huge page translated with the 4 KiB mask: bug #26 – the result is 4 KiB off wherever the PAT bit is set.
Experiments
- Print the four indices and every entry on the way for
kmain, a stack variable and the framebuffer. Which levels are huge pages? - Map the same frame at two addresses and write through one. Then map a page without
WRITABLEand write to it – what does the page fault's error code say? - Count how deep
deepergets before the fault (storedepthin a static). Does it match 16 KiB / 512 bytes? Why not exactly? - Make
unmapfree the tables that became empty. When is a table empty, and why is the PML4 never freed?
The next chapter puts a heap on top: memory in any size, not just 4 KiB at a time – and with it, Vec and String.