Topic 03: 4-Level Paging, Frame Allocator & Virtual Memory Mapping

Focus: x86_64 4-level paging hierarchy (PML4 to PT), CR3 register inspection, complete physical memory offset mapping, and the BootInfoFrameAllocator physical frame allocator.

1. High-Level Summary Table

2. Spoken Interview Answer (Word-for-Word Script)

"Virtual memory on 64-bit x86 architecture is implemented via a 4-level page table hierarchy that translates 48-bit virtual addresses into 52-bit physical addresses using 9-bit indices at each level: Level 4 Page Map, Level 3 Page Directory Pointer, Level 2 Page Directory, and Level 1 Page Table.

A fundamental dilemma in operating system development is: How can kernel code read or modify page tables when the CPU's CR3 control register only stores the PHYSICAL address of the root table, but the CPU in protected mode can ONLY dereference VIRTUAL addresses?

Historically, kernels solved this using recursive page tables, where an entry in the Level 4 table points back to itself. In RustOS, I adopted the modern, cleaner approach: complete physical memory offset mapping. The bootloader maps all physical RAM linearly starting at a high virtual offset (boot_info.physical_memory_offset). To access any physical memory address—including page table frames—the kernel simply adds this offset to the physical address.

In memory.rs, I implemented active_level_4_table, which reads Cr3::read(), adds the physical memory offset, and wraps the resulting raw pointer into a safe, mutable Rust &'static mut PageTable reference. On top of this, I built the BootInfoFrameAllocator, which inspects the BIOS physical memory map, filters out ACPI and hardware-reserved regions, and hands out free 4 KiB physical frames one page at a time. This provides the memory foundation needed to dynamically map kernel heap pages."

3. Deep-Dive Mechanics & Architecture Walkthrough

3.1 The 4-Level Page Table Translation Walk

A 48-bit virtual address in x86_64 long mode is split into four 9-bit offsets and a 12-bit page offset:

Virtual Address Bit Layout:
+-------------------+---------+---------+---------+---------+---------------+
| Sign Extension    | Level 4 | Level 3 | Level 2 | Level 1 | Page Offset   |
| Bits 63..48 (16b) | 47..39  | 38..30  | 29..21  | 20..12  | 11..0 (4 KiB) |
+-------------------+---------+---------+---------+---------+---------------+
                         |         |         |         |             |
                         v         v         v         v             v
                       PML4  --> PDPT  -->  PD   -->  PT     --> Phys Frame

Each page table consists of 512 entries of 8 bytes each ($512 \times 8 = 4096$ bytes = 1 page). Each entry contains a physical frame address alongside control flags: PRESENT, WRITABLE, USER_ACCESSIBLE, NO_EXECUTE.

3.2 Resolving CR3 via Physical Memory Offset

The core implementation in src/memory.rs retrieves the active Level 4 table:

// src/memory.rs
unsafe fn active_level_4_table(physical_memory_offset: VirtAddr) -> &'static mut PageTable {
    use x86_64::registers::control::Cr3;

    // 1. Read CR3 register to obtain physical address of root L4 page table
    let (level_4_table_frame, _) = Cr3::read();
    let phys = level_4_table_frame.start_address();

    // 2. Add physical_memory_offset to calculate the kernel's virtual pointer
    let virt = physical_memory_offset + phys.as_u64();
    let page_table_ptr: *mut PageTable = virt.as_mut_ptr();

    // 3. Return mutable reference to Level 4 Page Table
    &mut *page_table_ptr
}

Because the bootloader guarantees that all physical RAM is mapped starting at physical_memory_offset, this pointer arithmetic is guaranteed not to cause a page fault.

3.3 Physical Frame Allocator (BootInfoFrameAllocator)

When the kernel maps a new virtual page, intermediate page tables (Level 3, Level 2, or Level 1) may not yet exist. The mapper requires fresh 4 KiB physical frames from the frame allocator:

// src/memory.rs
unsafe impl FrameAllocator for BootInfoFrameAllocator {
    fn allocate_frame(&mut self) -> Option {
        let frame = self.usable_frames().nth(self.next);
        self.next += 1;
        frame
    }
}

The usable_frames() iterator iterates through boot_info.memory_map, filtering only regions where region_type == MemoryRegionType::Usable, converts each region into steps of 4096 bytes, and produces PhysFrame descriptors. self.next acts as a simple monotonic allocator tracking handed-out frames.

4. Real Edge Cases, Pitfalls & Debugging

4.1 Overwriting BIOS/ACPI Reserved Memory

If the frame allocator naively assumes all memory above 1 MiB is usable RAM, it inadvertently hands out physical frames reserved by the motherboard for ACPI tables or PCI memory-mapped I/O. When the kernel or heap writes to those frames, hardware devices malfunction or system power state transitions trigger hard freezes.

Solution: The usable_frames generator in src/memory.rs (L81) strictly enforces r.region_type == MemoryRegionType::Usable, rejecting Reserved, AcpiReclaimable, AcpiNvs, and Bootloader frames.

5. Concrete Verification & Test Traces

Paging and virtual-to-physical address translation are verified during bootloader handoff and heap setup:

// In src/main.rs
let phys_mem_offset = VirtAddr::new(boot_info.physical_memory_offset);
let mut mapper = unsafe { memory::init(phys_mem_offset) };
let mut frame_allocator = unsafe { BootInfoFrameAllocator::init(&boot_info.memory_map) };

We can verify arbitrary virtual translation using the Mapper::translate_page API:

use x86_64::structures::paging::Translate;
let test_virt = VirtAddr::new(0xb8000); // VGA buffer
let phys = mapper.translate_addr(test_virt);
// Output: Some(PhysAddr(0xb8000)) -> Identity mapped by bootloader!

6. Interview Questions & Tactical Answers

Q1: "Why is complete physical memory offset mapping preferred over recursive page tables?"

Tactical Answer: "Recursive paging requires sacrificing one Level 4 entry (512 GiB of virtual address space) and forces complex index manipulation to address lower page table levels. It also creates architectural headaches when switching between different address spaces (e.g. user processes). Linear physical offset mapping keeps translation logic trivial: any physical address is directly accessible by adding the base offset, making page table traversal and frame management clean and fast."

Q2: "What happens when the CPU encounters an unmapped page or a permission violation?"

Tactical Answer: "The CPU generates a Page Fault exception (Vector 14) and stores the faulting virtual address into the CR2 control register. It also pushes an error code onto the stack indicating whether the fault was caused by a non-present page, a write violation on a read-only page, a user-mode privilege violation, or an instruction fetch on an NX-flagged page."