The Physical Frame Allocator

Paging needs somewhere to put pages. Before the kernel can build a single page table, grow a stack or run a second process it must know which 4 KiB frames of physical RAM it may hand out. This lesson builds that: your program reads the memory map the firmware reported, works out which frames are really usable, and then allocates and frees them.

Where the truth comes from: the E820 map

RAM is not one clean range. The firmware reports a list of (base, length, type) entries (BIOS call E820, or UEFI's memory map). This is what QEMU reports for a 128 MiB machine:

Types: 1 usable, 2 reserved, 3 ACPI reclaimable, 4 ACPI NVS, 5 bad memory. Only type 1 is yours, and even then the kernel image you were loaded into (say 0x100000 to 0x2A3000) is not free.

From ranges to frames

A frame is usable only if the whole 4 KiB lies inside a type-1 range. So round the start up and the end down: the range 0x1800 to 0x4800 contains only frames 2 and 3 (0x2000 to 0x3FFF). The reverse holds for reservations: anything that merely touches a frame (reserved, or the kernel image) takes the whole frame, so round the start down and the end up. A reservation always wins over a usable range that overlaps it.

The number of frames is the highest end address divided by 4096. In the table above that is 0x100000000 / 0x1000, a million frames, most of them reserved or non-existent.

The bookkeeping

The simplest structure is a bitmap: one bit per frame, 1 meaning not available. Frame f lives in byte f / 8 at mask 1 << (f % 8). The cost is tiny, 128 KiB for 4 GiB, and it supports what kernels need:

• Allocate the lowest free frame (a linear scan; real kernels remember a "next hint").
• Allocate contiguous: DMA buffers and 2 MiB huge pages need k consecutive frames, so find the first run of k free frames. Fragmentation makes this the hard case.
• Free, and check: freeing a frame that is already free, never existed, or was reserved by firmware is a kernel bug. Catch it instead of silently corrupting the allocator. That needs more than one bit, so keep three states per frame: free, allocated, reserved.

The bootstrap puzzle

The bitmap itself needs memory, and the allocator that would provide it does not exist yet. Kernels solve it by carving the bitmap out of the first big usable range after the kernel image (and marking that carve-out reserved), then bringing the allocator up around it. Later subsystems (page tables, kernel stacks, the heap in the next lesson, user pages) all call down to it.

Common mistakes

• Rounding both ends of a usable range the same direction, so a partial frame at the edge is handed out.
• Treating a reserved or kernel frame as freeable. After a bad FREE the allocator would later give out the kernel's own memory.
• An off-by-one in the contiguous scan: the run must be k frames long, and a used frame resets the count.
• Computing the frame count from the usable ranges only, which misses the top of the map.

Your exercise

The program reads the memory map and then a stream of commands (see the exercise). The starter parses everything; you write the map-to-frames construction, alloc and free.