Frame Allocator

What Is a Frame?

A frame is a 4KB-aligned chunk of physical memory — the physical counterpart to a virtual page. The frame allocator tracks which physical frames are in use and hands them out when needed.

Our Implementation: Bump Allocator

The simplest possible allocator. A pointer starts just after the kernel and moves forward with each allocation. No free list, no recycling.

#![allow(unused)]
fn main() {
static mut FREE_FRAME_HEAD: u32 = 0;   // Head of free list (not currently used by allocate_frame)
static mut NEXT_FREE_FRAME: u32 = 0;   // Bump pointer
static mut MAX_FRAMES: u32 = 0;        // Total frames available
}

Initialization

#![allow(unused)]
fn main() {
unsafe fn init_frame_allocator(start: u32, mem_size: u32) {
    // Align start to 4KB boundary
    NEXT_FREE_FRAME = align_up(start);

    // Total frames = total memory / frame size
    MAX_FRAMES = mem_size / PAGE_SIZE;
}
}

start is _kernel_end aligned up to 4KB — the first byte after the kernel’s compiled code and data.

Allocation

#![allow(unused)]
fn main() {
unsafe fn allocate_frame() -> Option<u32> {
    if NEXT_FREE_FRAME < MAX_FRAMES * PAGE_SIZE {
        let frame = NEXT_FREE_FRAME;
        NEXT_FREE_FRAME += PAGE_SIZE;   // Advance bump pointer

        // Zero out the frame before returning it
        let ptr = frame as *mut u8;
        for i in 0..PAGE_SIZE {
            *ptr.add(i as usize) = 0;
        }

        Some(frame)
    } else {
        None  // Out of physical memory
    }
}
}

Returns None if we’ve exhausted available memory. Callers use .expect() which triggers kernel_panic — there’s no recovery from running out of frames.

Why zero the frame? Security (prevent data leakage between allocations) and stability (avoid random data causing subtle bugs).

Freeing

#![allow(unused)]
fn main() {
pub unsafe fn free_frame(addr: u32) {
    *(addr as *mut u32) = FREE_FRAME_HEAD;
    FREE_FRAME_HEAD = addr;
}
}

This pushes the frame onto a linked list using the frame’s own memory to store the next pointer. However, allocate_frame() currently uses the bump pointer and does not check FREE_FRAME_HEAD. This means freed frames are not currently reused.

Known Issue: The free list (FREE_FRAME_HEAD) and the bump allocator (NEXT_FREE_FRAME) are disconnected. free_frame correctly records freed frames, but allocate_frame never draws from that list. This is acceptable for the current stage — the frame allocator is primarily used to set up the page tables at boot, not for repeated alloc/free cycles. A proper frame allocator that recycles freed frames is on the roadmap.

Address Alignment

#![allow(unused)]
fn main() {
fn align_up(addr: u32) -> u32 {
    (addr + PAGE_SIZE - 1) & !(PAGE_SIZE - 1)
}
}

How it works:

addr = 0x00100500 (not page-aligned)

Step 1: Add (PAGE_SIZE - 1)
0x00100500 + 0x00000FFF = 0x001014FF

Step 2: AND with bitmask that zeros the lower 12 bits
!(PAGE_SIZE - 1) = !(0x00000FFF) = 0xFFFFF000

0x001014FF & 0xFFFFF000 = 0x00101000

Result: Next 4KB boundary after 0x00100500

Memory State After Initialization

Physical Memory:
┌────────────────────────┐  ← 16MB (mem_size)
│                        │
│   Available for        │
│   frame allocation     │  ← NEXT_FREE_FRAME walks up from here
│                        │
├────────────────────────┤  ← start (kernel_end aligned up)
│   Page Table 0 (4KB)  │  ← allocate_frame() call 2
├────────────────────────┤
│   Page Directory (4KB) │  ← allocate_frame() call 1
├────────────────────────┤
│   Kernel code + data   │  ← _kernel_start to _kernel_end
└────────────────────────┘  ← 0x00100000

Limitations of the Bump Allocator

For setting up the initial page tables at boot, a bump allocator is perfectly sufficient. For kmalloc/kfree where blocks are repeatedly allocated and freed, we need a proper heap allocator on top.