Phase 33

Kernel Memory Improvements

The kernel heap allocator is robust, efficient, and recoverable. Out-of-memory conditions no longer panic the kernel — the allocator grows on demand and retries failed allocations. Buddy allocation, working `munmap()`, userspace-heap coalescing, and slab-cache infrastructure all land. Broad migration of hot kernel object families onto slab caches remains later work.

Complete

Learning goal

Understand the trade-offs between allocator designs: linked-list, buddy, slab.

Why this phase matters

The kernel heap allocator is robust, efficient, and recoverable. Out-of-memory conditions no longer panic the kernel — the allocator grows on demand and retries failed allocations. Buddy allocation, working munmap(), userspace-heap coalescing, and slab-cache infrastructure all land. Broad migration of hot kernel object families onto slab caches remains later work.

How it works in m3OS

The roadmap entry defines the learning scope for this phase; a deeper implementation doc has not been matched yet.

How it builds on earlier phases

This phase builds on Build Tools and turns that foundation into Kernel Memory Improvements.

Implementation outline

Implement OOM retry wrapper around the global allocator.
Verify: allocation-heavy workloads no longer panic (heap grows and retries).
Implement buddy allocator for page-granularity allocations.
Implement slab allocator caches for Task, FD, endpoint, pipe, and socket-sized objects, and validate them in direct cache tests.
Implement working munmap() with frame reclamation and TLB invalidation.
Add free-block coalescing to userspace BrkAllocator.
Add heap_stats() and verify with a stress-test program.
Run existing test suite to verify no regressions.

Task progress snapshot

56 of 67 tracked tasks are complete.

Documentation targets

Documentation deliverables have not been listed yet.

Deferred follow-on work

OOM killer (kill processes instead of failing allocations)
Memory compaction and defragmentation
Transparent Huge Pages
NUMA-aware allocation
Kernel memory accounting and cgroups
vmalloc for large virtually-contiguous allocations
Memory pressure notifications
Broad migration of hot kernel object families onto slab caches

Source materials

Important code

Code spotlight cards

Create `RetryAllocator` wrapper struct. Why it matters: This wrapper replaces the old direct global allocator so kernel allocations can retry after heap growth instead of immediately failing. Focus on `RetryAllocator` and `LockedHeap` in `kernel/src/mm/heap.rs` while you trace the snippet.

/// OOM-retrying allocator wrapper around `LockedHeap`.
///
/// On allocation failure, attempts to grow the kernel heap with escalating
/// sizes before retrying. This avoids the limitations of `alloc_error_handler`
/// which cannot retry the failed allocation.
struct RetryAllocator {
    inner: LockedHeap,
}

View on GitHub

Remove diverging `alloc_error_handler` retry path. Why it matters: Keeping the error handler panic-only makes the retry path live entirely in RetryAllocator, where allocation can still return and retry safely. Focus on `alloc_error_handler` and `RetryAllocator` in `kernel/src/main.rs` while you trace the snippet.

#[alloc_error_handler]
fn alloc_error_handler(layout: alloc::alloc::Layout) -> ! {
    // The RetryAllocator already attempted heap growth and retry before this
    // handler is reached. If we get here, all growth attempts failed.
    panic!(
        "kernel OOM: failed to allocate {:?} after heap growth retry",
        layout
    );
}

View on GitHub

Implement buddy allocator data structure in `kernel-core`. Why it matters: The host-testable buddy allocator provides split-and-merge frame management that the earlier free-list design could not do. Focus on `kernel-core` and `BuddyAllocator` in `kernel-core/src/buddy.rs` while you trace the snippet.

/// Buddy frame allocator.
///
/// Each order level maintains:
/// - A bitmap where bit *i* is set when block *i* at that order is free.
/// - A free list (Vec used as a stack) of free block start PFNs.
///
/// Free list push/pop within a single order is O(1). Overall allocation and
/// free may traverse/split/merge across orders up to MAX_ORDER, giving
/// O(log n) behavior bounded by MAX_ORDER + 1 levels. The bitmap enables
/// O(1) buddy-merge checks without scanning the free list.
pub struct BuddyAllocator {
    /// Per-order free lists: each entry is a PFN of a free block at that order.
    free_lists: [Vec<usize>; MAX_ORDER + 1],
    /// Per-order bitmaps: bit at `block_index(pfn, order)` is set iff that block
    /// is free.  Stored as Vec<u64> for efficient bit manipulation.
    bitmaps: [Vec<u64>; MAX_ORDER + 1],
    /// Per-order free block counts.
    free_counts: [usize; MAX_ORDER + 1],
    /// Total number of page frames managed.
    total_pages: usize,
}

View on GitHub

Key files

kernel-core/src/buddy.rs — Implements a binary buddy system for physical frame allocation. Free lists are
kernel-core/src/slab.rs — allocator is host-testable via kernel-core.
kernel/src/mm/heap.rs — RetryAllocator wrapper, heap_stats()
kernel/src/mm/frame_allocator.rs — Buddy integration, contiguous alloc, frame_stats()
kernel/src/mm/slab.rs — New: kernel slab cache instances
kernel/src/mm/mod.rs — Init sequence: buddy + slab after heap
kernel/src/arch/x86_64/syscall.rs — Real munmap, meminfo syscall
kernel/src/process/mod.rs — MemoryMapping tracking
userspace/syscall-lib/src/heap.rs — Sorted free list, coalescing dealloc
userspace/syscall-lib/src/lib.rs — meminfo() syscall wrapper
userspace/coreutils-rs/src/meminfo.rs — New: meminfo command

How real OSes differ

**Buddy allocator** manages physical pages (zone allocator with ZONE_DMA, ZONE_NORMAL, ZONE_HIGHMEM).
**SLAB/SLUB/SLOB** provides object-level caching on top of the buddy allocator.
**vmalloc** handles virtually contiguous but physically discontiguous allocations.
**OOM killer** selects and kills processes when memory is exhausted rather than panicking.
**Memory compaction** moves pages to create larger contiguous blocks.
**Transparent Huge Pages (THP)** opportunistically uses 2 MiB pages.

Success criteria

Allocation-heavy workloads (many fork/exec cycles) no longer panic with OOM.
The kernel heap grows on demand and the retry path works.
Slab-cache infrastructure for hot kernel object sizes allocates and frees in O(1) in direct cache tests; broad object-family migration is deferred.
`munmap()` returns physical frames; a program that maps and unmaps in a loop does not exhaust memory.
Userspace programs that allocate and free many small objects do not fragment the heap excessively (coalescing verified).
`heap_stats()` shows reasonable utilization under load.
All existing tests pass without regression.

Related phases

Keep exploring the roadmap

Build Tools

Multi-file C projects can be built inside the OS using a `make`-compatible build tool and shell scripts. This transforms the OS from a "compile one file" environment into one where real software projects can be developed.

Real Time Clock

The OS knows what time it is. A CMOS RTC driver reads the hardware clock at boot to establish the current wall-clock time. `clock_gettime(CLOCK_REALTIME)` returns actual Unix timestamps, distinct from `CLOCK_MONOTONIC` which tracks time since boot. The `date` command displays the current date and time.