Topic 03: 4-Level Paging & Physical Frame Allocation

Overview: How the kernel translates virtual addresses to physical RAM, accesses page tables using a physical memory offset, and tracks available 4 KiB RAM frames.


1. High-Level Summary

Component Source Link What It Does Why It Is Needed
L4 Page Table Pointer src/memory.rs:207 Reads CR3 and adds physical memory offset Turns the CPU's physical page table address into a virtual pointer the kernel can access.
Physical Memory Offset src/main.rs:97 Maps all physical RAM at a fixed virtual offset Allows the kernel to access any physical memory address by simple addition: Virt = Phys + Offset.
Frame Allocator src/memory.rs:34 Tracks and hands out free 4 KiB physical frames Provides fresh physical memory pages when creating page tables or expanding the kernel heap.
Memory Map Filter src/memory.rs:81 Filters for Usable RAM regions only Prevents the kernel from overwriting hardware registers, ACPI tables, or BIOS memory.

2. Spoken Interview Answer (Simple & Direct)

"Virtual memory on 64-bit x86 translates virtual addresses into physical addresses through a 4-level page table hierarchy: Level 4, Level 3, Level 2, and Level 1.

One classic problem when writing a kernel is: How does the kernel read or edit page tables? The CPU's CR3 register gives the physical address of the root page table, but in 64-bit mode, the CPU can only read and write virtual addresses.

In RustOS, I used complete physical memory offset mapping. The bootloader maps all physical RAM linearly into a high virtual address range. To access any physical memory frame—including page tables—the kernel simply adds this offset to the physical address. In memory.rs, I implemented active_level_4_table to read CR3, add the offset, and return a safe Rust reference to the top-level page table.

On top of this, I built the BootInfoFrameAllocator. It reads the memory map provided by the bootloader, filters out reserved and ACPI regions, and hands out free 4 KiB physical memory frames one by one. This gave us the foundation needed to map pages for the kernel heap."


3. Architecture & Mechanics

3.1 How 4-Level Paging Works

In 64-bit mode, each virtual address is 48 bits long. The CPU translates it into a physical address in 4 steps using 9-bit indices at each level:

Virtual Address (48 bits):
  Bits 47..39  --> Index into Level 4 Table (PML4)
  Bits 38..30  --> Index into Level 3 Table (PDPT)
  Bits 29..21  --> Index into Level 2 Table (Page Directory)
  Bits 20..12  --> Index into Level 1 Table (Page Table)
  Bits 11..0   --> Offset inside the 4 KiB physical page frame (0 to 4095)

Each table has 512 entries, and each entry is 8 bytes ($512 \times 8 = 4096$ bytes = exactly 1 page). Each entry contains the physical address of the next table down, plus permission bits like PRESENT, WRITABLE, and NO_EXECUTE.

3.2 How the Kernel Accesses Page Tables (Physical Offset Mapping)

Because the CPU only understands virtual addresses once paging is enabled, the kernel cannot directly dereference the physical address stored in CR3.

The bootloader solves this by mapping all physical RAM at a fixed virtual base address (physical_memory_offset):

Physical Address (e.g. 0x1000)
             ↓
Add physical_memory_offset
             ↓
Kernel Virtual Address (e.g. 0xFFFF_8000_0000_1000)

In src/memory.rs:207, active_level_4_table() reads CR3, adds the offset, and casts the address to a mutable Rust reference to the root page table.

3.3 Allocating Physical Memory Frames

When creating a new virtual memory mapping or expanding heap space, the kernel needs fresh physical frames of RAM.

In src/memory.rs:34, BootInfoFrameAllocator manages physical memory:

  1. It reads the memory map provided by the BIOS/bootloader.
  2. It uses usable_frames() to filter out hardware-reserved, ACPI, and bootloader-reserved regions, leaving only genuine free RAM.
  3. It divides those usable areas into 4096-byte frames and hands them out sequentially using a simple counter.

4. Edge Cases & Debugging

⚠️ Edge Case: Overwriting Motherboard & ACPI Reserved Memory
Problem: If a frame allocator naively treats all memory above 1 MiB as usable RAM, it will allocate physical frames reserved by the hardware for ACPI power tables or PCI devices. Writing to these frames causes device malfunctions and system crashes.
Fix: In src/memory.rs:81, the frame allocator strictly checks the memory region type and only accepts regions marked as Usable, completely ignoring reserved areas.

5. Quick Interview Q&A

Q: How does the kernel access physical memory when paging is active?
"The bootloader sets up a complete physical memory offset mapping. This maps all physical RAM linearly into a high virtual address range. The kernel can access any physical address simply by adding that offset."
Q: What happens if code accesses an invalid or unmapped virtual address?
"The CPU triggers a Page Fault exception (Vector 14). The hardware automatically stores the faulting virtual address into the CR2 register and pushes an error code to the stack indicating whether it was a missing page or a permission violation."
Q: How does your physical frame allocator know which memory is safe to use?
"It inspects the memory map handed over by the bootloader. It filters each region and only allocates from sections marked as Usable, skipping hardware-reserved and ACPI memory."