Physical Allocator — kmalloc

Status: Not yet implemented. This chapter documents the design and what needs to be built.

The Gap Between Frame Allocator and kmalloc

The frame allocator hands out 4KB blocks. But most allocations are much smaller — a few bytes, a struct, maybe a kilobyte. Giving out an entire 4KB frame for a 64-byte struct wastes 4032 bytes.

kmalloc sits between the caller and the frame allocator:

Caller wants 256 bytes
    ↓
kmalloc(256)
    ↓
Find or create a region with a free 256-byte block
    ↓
Return pointer to that block

(Only calls allocate_frame() when it needs a new 4KB slab to carve up)

Where the Heap Lives

The kernel heap starts just after the kernel binary and initial page tables, within the identity-mapped 4MB region:

0x00400000  ← End of identity-mapped region
            ← Heap upper bound (can grow up to here)
   (heap)   ← kmalloc manages this region
~0x00200000 ← Heap start (approximate, after page tables)

The heap is a fixed region reserved at init time. We’re not doing dynamic expansion (kbrk) in the first pass — just a fixed-size heap.

Design: Free-List Allocator

The classic approach. Every allocation is preceded by a small header:

┌──────────────────────┐ ← What kmalloc returns (pointer to here)
│    User Data         │
│    (requested size)  │
├──────────────────────┤ ← Header (hidden from user)
│ size: u32            │ ← Total size of this block (header + data)
│ used: bool           │ ← Is this block allocated?
│ next: *mut Header    │ ← Next block in the heap (for walking)
└──────────────────────┘

The header is stored before the user data. kmalloc returns a pointer to the user data region; the header is at ptr - sizeof(Header).

First-Fit Allocation

Walk the block list from the start
    For each block:
        If block.used == false AND block.size >= requested_size:
            Mark block as used
            Split if block is much larger than needed
            Return pointer to user data
    If no block found:
        Out of memory → return null

Freeing

Given ptr:
    Header = ptr - sizeof(Header)
    Mark header.used = false
    Try to merge with adjacent free blocks (coalescing)

Coalescing

Without coalescing, repeated alloc/free cycles produce a heap full of tiny unusable gaps:

Before:   [used:100][free:50][used:200][free:50][free:100]
After free of used:200:
          [used:100][free:50][free:200][free:50][free:100]

Without coalescing: 4 free blocks, largest is 200 bytes
With coalescing:    [used:100][free:400]  ← one big usable block

Functions to Implement

#![allow(unused)]
fn main() {
// memory/physical_mem.rs

pub unsafe fn init_heap(start: u32, size: u32);
// Set up the initial free block spanning the heap region

pub unsafe fn kmalloc(size: usize) -> *mut u8;
// Allocate `size` bytes of physical memory
// Returns null on failure

pub unsafe fn kfree(ptr: *mut u8);
// Free memory previously returned by kmalloc

pub unsafe fn ksize(ptr: *mut u8) -> usize;
// Return the usable size of an allocation
}

Key Design Decisions

Alignment: Return pointers aligned to at least 4 bytes (or 8). Misaligned access is slow on x86 and illegal on some architectures.

Minimum block size: Set a floor (e.g. 16 or 32 bytes) to avoid splitting blocks into unusable fragments.

Split threshold: Only split a block if the remainder is large enough to be useful. Splitting a 100-byte block to satisfy a 96-byte request leaves a 4-byte remainder that can’t hold anything.

Header size: Keep it small. If the header is 12 bytes and you’re allocating 8-byte structs, you’re spending more on metadata than data.

Testing

The shell will get a memtest command:

> memtest
Allocating 64 bytes...  ptr = 0x00201010  OK
Allocating 1024 bytes... ptr = 0x00201060  OK
Freeing 64 bytes...     OK
Reallocating 64 bytes... ptr = 0x00201010  OK (reused!)
Allocating 100 * 256 bytes... OK
Freeing every other block... OK
Stats: 25KB used, 975KB free

KFS - Kernel From Scratch