The Physical Frame Allocator

Kernel code constantly needs memory, and malloc (the next lesson) carves small objects out of pages — but someone has to hand out the pages themselves first. That someone is the physical frame allocator — the layer that owns every 4 KiB frame of RAM in the machine and answers the kernel's most primitive memory question: give me a frame / take this frame back. Every page table, every kernel stack, every page of every process's memory starts life as one of its allocations.

What it manages

After boot, the kernel knows (from the bootloader's memory map — the Boot Process lesson's E820 data) which physical address ranges are usable RAM. Chop those ranges into page-sized frames and number them: frame 0, frame 1, … frame N−1. The allocator's entire state is which frames are in use — and the simplest honest representation is one bit per frame:

bitmap:  1 1 0 1 0 0 0 1 …
frame:   0 1 2 3 4 5 6 7

One bit per 4 KiB frame means the bookkeeping for 4 GiB of RAM fits in 128 KiB — a 0.003% overhead. That efficiency is why the bitmap is the classic first frame allocator in real kernels and hobby kernels alike.

The operations

• Alloc: scan for the first 0 bit, set it, return that frame number. First-fit scanning keeps allocations packed low, which is friendly to the "lowest frame" determinism your tests expect — and to real DMA devices that can only address low memory.
• Free: clear the bit. And check it was set: freeing a free frame means someone's bookkeeping is corrupt — a double free, kernel edition. The C course taught you what that does to a userspace heap; in the kernel, the same bug hands one frame to two owners, and two subsystems proceed to scribble over each other's page. Catching it at the allocator (error, log, panic — anything but silence) is the cheap defense.
• The naive scan is O(n) per alloc. Real implementations remember where the last search ended (next-fit), keep per-region free counters, or use a find-first-zero CPU instruction over words — same semantics, faster search. Your exercise is the semantics.

The bootstrap puzzle

One delicious chicken-and-egg to appreciate: the bitmap itself needs memory — who allocates the allocator? Nobody: early boot code reserves the bitmap's frames by hand (bump-allocator style — the same trick as Linux's early-boot memblock) before the frame allocator comes online, then marks its own frames as used in the map it just built. Every kernel has a moment like this — a structure that must exist before the machinery that manages such structures exists — and recognizing the pattern ("build it manually, then hand it to itself") is a genuine systems instinct.

Where it sits in the stack

Keep the two allocation layers straight, because every later lesson leans on the division:

• Frame allocator (this lesson): whole 4 KiB frames. Callers: the paging code (page tables are frames!), the heap when it needs more raw material, drivers needing DMA buffers.
• Heap allocator (the next lesson): arbitrary-size objects within frames it obtained from this layer.

A kmalloc(48) that finds its slab empty calls down here for a fresh frame; a page fault handler resolving a copy-on-write (a lesson coming shortly) calls down here for the copy's frame. Everything above trusts this layer to never hand out the same frame twice — which is exactly the property your exercise's tests probe.

Your exercise: Bitmap Frame Allocator

FRAMES n sets the world; then ALLOC (lowest free frame, or OOM), FREE f (with OK/ERROR — the double-free check is graded!), and STATE (the bitmap as a 0/1 string). Every rule above becomes a test: lowest-first ordering after frees, exhaustion → OOM, double-free and out-of-range → ERROR, and the bitmap snapshot matching your bookkeeping bit for bit. It's thirty lines — and it's the layer every other memory lesson in this course silently assumed.