Skip to content

Allocators

There are three distinct allocators in the kernel, each serving a different purpose and lifetime.

1. Kernel Linked-List Heap (mem/heap.rs)

Region: __heap_start – __heap_end (64 KiB, defined in linker.ld, lives in the kernel binary after .bss)

Purpose: General kernel-internal allocations during early init (tested in init/heap.rs). This is the original, hand-written heap; it is present but seldom used now that most kernel subsystems use static arrays.

Block Layout

Each allocation is preceded by an inline HeapNode header (4 pointer-sized fields, ~32 bytes on x86-64):

struct HeapNode {
    size:     usize,           // data bytes available after this header
    status:   HeapNodeStatus,  // Free | Used | Unknown
    previous: *mut HeapNode,   // linked-list predecessor (null for first)
    next:     *mut HeapNode,   // linked-list successor (null for last)
}

At init(), a single free node spanning the entire heap is written at __heap_start. HEAP_PTR tracks the "current" node for scanning.

Allocation (alloc)

  1. Walk the list from HEAP_PTR looking for a free node large enough for alloc_size.
  2. If the found node is significantly larger, split() it: the left node gets exactly alloc_size bytes (minimum MIN_HEAP_NODE_SIZE = 16), the right node gets the remainder. Both are marked Free; the caller immediately marks the left one Used.
  3. Zero the data region of the allocated node.
  4. Return the address of the HeapNode header (callers treat this as the usable address — note: the returned pointer is the header itself, not the data after it).

Deallocation (free)

  1. Mark the node at vaddr as Free.
  2. Call merge(), which walks backwards until it finds a free node and merges it with its free successor by summing sizes and updating the next/prev pointers.

Limitations

  • The allocator has bugs in its merge / alloc walk logic (it can loop indefinitely and has an OOM fallback counter). It should be considered legacy.
  • No thread safety — no lock is held during allocation.
  • Minimum heap node size is MIN_HEAP_NODE_SIZE = 16 bytes; smaller requests are rounded up.
  • Total heap size: 64 KiB, fixed at compile time.

2. Kernel Rust Global Allocator — Bump Allocator (mem/bump.rs)

Region: Configured at runtime via BumpAllocator::init(heap_start, heap_size).

Purpose: Satisfies Rust's #[global_allocator] trait so that Box, Vec, and other alloc crate types can be used inside the kernel. Currently initialised by init_heap_allocator() in init/heap.rs, which points it at the same __heap_start / __heap_end region.

Algorithm

next  ← heap_start  (AtomicUsize, SeqCst)

alloc(layout):
    aligned = (next + align - 1) & !(align - 1)
    new_next = aligned + size
    if new_next > heap_end: return null
    next.store(new_next)
    return aligned

dealloc(_ptr, _layout):
    /* no-op */

Allocation is a single atomic fetch-and-add (effectively). Deallocation does nothing — freed memory is not reclaimed.

Properties

Property Value
Thread safety Yes (SeqCst atomic)
Deallocation No (bump; memory is permanent)
Fragmentation None (monotone)
Max allocation Heap size − alignment padding

The bump allocator is appropriate for the kernel because most kernel-level Rust allocations are long-lived static structures. Any allocation that the kernel makes via Box::new or similar is effectively leaked for the kernel's lifetime.

3. Userland Heap — Free-List Allocator (mem/uheap.rs)

Region: 0xC00_000 – 0xFFF_FFF (4 MiB, virtual == physical, identity-mapped)

Purpose: Dynamic heap for userland processes. Exposed as syscalls 0x0a (malloc), 0x0b (realloc), 0x0f (free). All processes share one physical heap — there is no per-process isolation, but every block records its owner and is reclaimed when the owner dies.

Mapping: uheap::init() is called from init_processes() after save_kernel_cr3(). It sets P2[6] (0xC00_000) and P2[7] (0xE00_000) to USER+WRITE 2 MiB huge pages in the current page table. Because create_user_page_table clones the kernel P2, every subsequent user process inherits these entries automatically.

Block Layout (in-band, 8-byte header)

 ┌─────────────────┬─────────────────┐
 │   data_size: u32 │     flags: u32  │  ← 8-byte header
 └─────────────────┴─────────────────┘
 │           data region              │  ← data_size bytes
 └────────────────────────────────────┘
flags bits Meaning
0 1 = free, 0 = used
8–15 owning scheduler slot + 1 (0 = untagged)

The syscall layer reads the caller's slot (scheduler::get_current_pid()) before entering the heap and passes it as owner, so the scheduler lock is never taken underneath the heap lock. NO_OWNER (0xFF) marks a block that belongs to no process and is never swept. realloc keeps the owner a block was allocated with.

At init(), a single free block spanning HEAP_SIZE − 8 bytes is written at HEAP_START.

Growing: the extension

When an allocation (or a realloc) finds no room in the 4 MiB, the heap grows once, and the allocation is tried again:

  • Size: an eighth of the usable RAM the Multiboot2 map reported (boot::total_ram_bytes), in whole 2 MiB pages, at least 2 MiB — 32 MiB with 256 MiB of RAM, 256 MiB with 2 GiB.
  • Place: 0xA00_0000 (160 MiB), or the first 2 MiB boundary past the tar archive (ustar::archive_base/len) when the archive is in the way. The whole range has to lie inside one usable region of the memory map (boot::usable_covers) and below 1 GiB, the part of the identity map processes copy; if it does not, the size is halved down to 2 MiB before giving up. A machine without that RAM keeps the 4 MiB, and says so once on the serial log.
  • Mapping: pages::set_user_range makes those P2 entries USER+WRITE in the kernel's P2 and in every live process's copy of it. Each process has its own P2 (see create_user_page_table), so patching the kernel's alone would reach only processes started later; pages.rs keeps a registry of the live copies for this. The copy and its registration happen with interrupts off, as does the patching, so a process being created either copies the patched table or is registered in time to be patched.
  • Blocks: the extension is a second region with its own chain of the same 8-byte headers. alloc, free, realloc, coalesce, the owner sweep and stats walk both regions; uheap::extension() says where it is and uheap::contains(addr, len) whether a buffer lies in either.
  • Syscalls: user_room/user_buf_ok in abi/syscall.rs accept a buffer in the extension like one in the 4 MiB, so heap memory from either can be handed to any syscall.

The heap shell command prints the extension when there is one. ktest fills the 4 MiB and checks the growth (test_heap_grow).

Allocation (malloc)

  1. Acquire LOCK (see Locking) and drain any pending owner sweeps.
  2. Linear scan from HEAP_START: skip blocks where flags & FLAG_FREE == 0 or data_size < size.
  3. On finding a suitable free block:
  4. If remainder = data_size − size ≥ HDR + MIN_SPLIT (16): split — write a new free header at addr + HDR + size, mark the found block used with data_size = size.
  5. Otherwise: use the whole block (no split), mark used.
  6. Zero the data region.
  7. Return addr + HDR (pointer to data, not header).

All sizes are rounded up to 8-byte alignment (align8) before the scan.

Reallocation (realloc)

Tries three strategies in order, under the lock:

  1. Shrink / same size: If new_size ≤ old_size, optionally split the tail into a new free block if the remainder is large enough. Return the same pointer.
  2. In-place expansion: If the immediately adjacent next block is free and old_size + HDR + next_size ≥ new_size, absorb it. Split the remainder if large enough. Return the same pointer.
  3. Allocate + copy + free: alloc_inner(new_size), copy_nonoverlapping, set_free(old_hdr), coalesce(). Returns the new pointer (old pointer is invalid after this).

Special cases: ptr == 0 → malloc(new_size); new_size == 0 → free(ptr).

Deallocation (free)

  1. Validate ptr ∈ [HEAP_START + HDR, HEAP_END).
  2. Acquire LOCK.
  3. set_free(ptr − HDR): write FLAG_FREE to the header flags field.
  4. coalesce(): single linear pass that merges any pair of adjacent free blocks by summing [size + HDR + next_size] into the left block's header.

Reclaiming a dead process's blocks (free_owned)

When the scheduler kills a process or marks it crashed, it calls free_owned(slot) after releasing its own lock. The slot's bit is first published in PENDING; if the heap lock can be taken, every used block tagged with that slot is freed and coalesced, otherwise the next malloc performs the sweep. A busy lock therefore delays reclamation instead of leaking the blocks.

Locking

static LOCK: Mutex<()> (spin). All public functions acquire it through lock_heap():

  • The lock is spun for with interrupts on, so its holder can still be scheduled and release it.
  • Once taken, interrupts are turned off for as long as it is held, so the holder cannot be preempted — and then killed — inside the allocator.
  • The holder's slot is recorded in LOCK_HOLDER (lock_holder() reads it without the lock).
  • On release the lock is dropped first, then the holder is forgotten, then interrupts are restored.

If a process dies holding the lock anyway, free_owned takes it back (reclaim_from) before sweeping, since a killed or crashed process never returns to the allocator.

Statistics

stats() reports used and free bytes, the largest free block (what decides whether a large malloc can succeed), block counts, and used bytes per owning slot. The shell's heap command prints it, or the slot holding the lock when the heap is busy.

Constants

Constant Value Description
HEAP_START 0xC00_000 First byte of the heap region
HEAP_END 0x1000_000 One past the last byte (exclusive)
HDR 8 Header size in bytes
FLAG_FREE 1 Free flag in the flags field
MIN_SPLIT 16 Minimum data size for a remainder block to be split off

Pointer Validation in Syscalls

Syscall handlers accept a buffer that lies wholly inside the program image (USERLAND_START 0x600_000 to USERLAND_END 0xA00_000) or wholly inside this heap (user_buf_ok in src/abi/syscall.rs). Heap memory can therefore be passed straight to syscalls such as 0x10 print or 0x17 blit, with no copy into image buffers first.

The malloc/realloc/free syscalls themselves (0x0a, 0x0b, 0x0f) do not check pointers against the userland range — uheap::free validates against HEAP_START/HEAP_END instead.