Phase 17

Memory Reclamation

Close the memory leaks that have accumulated since Phase 2. The bump frame allocator is replaced with a free-list allocator that can actually reclaim frames, the kernel heap grows on demand instead of being fixed at 1 MiB, kernel stacks are freed when processes exit, and `fork` switches from eager full-copy to copy-on-write so parent and child share physical pages until one of them writes.

Complete

Learning goal

Understand why a bump allocator leaks and what data structure replaces it.

Why this phase matters

Close the memory leaks that have accumulated since Phase 2. The bump frame allocator is replaced with a free-list allocator that can actually reclaim frames, the kernel heap grows on demand instead of being fixed at 1 MiB, kernel stacks are freed when processes exit, and fork switches from eager full-copy to copy-on-write so parent and child share physical pages until one of them writes.

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 Network and turns that foundation into Memory Reclamation.

Implementation outline

Design the free-list data structure. Each free frame stores a pointer to the next free frame in its first 8 bytes, forming an intrusive linked list. Initialize the list by walking the bootloader memory map and pushing every usable frame. Track the total free count for diagnostics.
Replace BumpFrameAllocator with FreeListFrameAllocator in kernel/src/mm/frame_allocator.rs. Keep the same FrameAllocator trait interface so callers do not change. The new allocator must be Send + Sync behind a spin::Mutex.
Implement free_frame() to push a frame back onto the free list. Add a debug assertion that the frame is not already free (double-free detection via a poisoned magic value written to the first 8 bytes of each free frame).
Add a RefCount table: a Vec<AtomicU16> (or a bitmap plus counter array) sized to the highest physical frame number. Increment on alloc_frame, increment again on CoW clone, decrement on free_frame; actually reclaim only when the count reaches zero.
Update free_process_page_table() in kernel/src/mm/mod.rs to walk all four page-table levels for the user address range, decrement the reference count for each leaf frame, and free the frame when it reaches zero. Free intermediate table frames (L1, L2, L3 tables) as well once all their entries are empty.
Update drain_dead() in the scheduler: after reaping a zombie process, recover the kernel stack base address from the process’s saved state, unmap the stack pages, and return them to the frame allocator.
Make the kernel heap growable. Reserve a large virtual region (e.g., 64 MiB starting at HEAP_START) but only map the initial 1 MiB. When the linked-list allocator returns None, map the next 1 MiB chunk of the reserved region, call allocator.extend(), and retry the allocation. Cap growth at the reserved region size and panic if exceeded.
Implement copy-on-write fork: a. In fork, iterate over every user PTE in the parent. Clear the writable bit in both parent and child entries. Increment the frame’s reference count. b. Register a page-fault handler that checks whether the faulting address maps to a CoW page (present, not writable, refcount > 1). c. On a CoW fault: allocate a new frame, copy the 4 KiB contents, map the new frame writable in the faulting process, decrement the old frame’s reference count. d. If refcount is exactly 1 when the fault fires, the page is the last reference; simply remap it writable without copying.
Add a frame_stats() function that returns the current free count, used count, and CoW-shared count for debugging and acceptance testing.
Stress-test: run a loop that forks and immediately exits many times; verify the free frame count returns to its original value.

Task progress snapshot

No checklist tasks were discovered for this phase yet.

Documentation targets

Documentation deliverables have not been listed yet.

Deferred follow-on work

Buddy allocator with power-of-two coalescing
Slab or SLUB allocator for small kernel objects
Demand paging from disk (swap)
Huge page (2 MiB / 1 GiB) support
NUMA-aware frame allocation
mmap(MAP_PRIVATE) with CoW semantics for file-backed pages
Kernel stack guard pages
Memory pressure notifications and OOM killer

Source materials

Important code

Code spotlight cards

kernel/src/mm/frame_allocator.rs. Keep the same FrameAllocator trait interface

View on GitHub

Update free_process_page_table() in kernel/src/mm/mod.rs to walk all four

/// Free all user-space page table frames for the given PML4 physical address.
///
/// Walks the process's PML4, freeing user-accessible leaf pages and any
/// page-table structure frames that are process-private (not shared with the
/// kernel).  Shared kernel entries (PML4[1..256]) are detected by comparing
/// against the kernel's PML4 and skipped entirely.
///
/// # Safety
///
/// `cr3_phys` must be the physical address of a valid, now-unreachable PML4
/// that is no longer loaded in CR3. No other code may access the page table
/// after this call.
pub fn free_process_page_table(cr3_phys: u64) {
    use alloc::vec::Vec;
    use x86_64::structures::paging::{PageTable, PageTableFlags};
    let phys_off = VirtAddr::new(phys_offset());
    let kernel_pml4_phys = *KERNEL_PML4_PHYS.get().expect("mm not initialized");

    // Helper: read present, non-huge child table addresses from a page table,
    // scoping the &PageTable reference so it drops before any free_frame calls.
    unsafe fn collect_children(
        phys_off: VirtAddr,
        table_phys: u64,
        count: usize,

View on GitHub

Key files

kernel/src/mm/frame_allocator.rs — kernel/src/mm/frame_allocator.rs. Keep the same FrameAllocator trait interface
kernel/src/mm/mod.rs — Update free_process_page_table() in kernel/src/mm/mod.rs to walk all four

How real OSes differ

Production kernels use buddy allocators (Linux's page allocator splits and coalesces power-of-two blocks) or slab allocators on top of page allocators for small objects.
Reference counting in Linux is done with `struct page` metadata rather than a separate table.
CoW is also used for `mmap(MAP_PRIVATE)` and file-backed pages, not just fork.
The kernel heap in Linux is not a single contiguous region; `vmalloc` allocates from a scattered virtual range while `kmalloc` uses slab caches backed by physically contiguous pages.
This phase keeps things simple: one free list, one reference count table, one contiguous heap region.

Success criteria

`free_frame()` returns frames to the allocator; the free count increases after a process exits.
Forking 100 times and exiting each child returns the system to roughly the same free frame count as before the loop.
A parent and child created by `fork` share physical pages until the child writes; writing triggers a page fault that creates a private copy.
The kernel heap successfully grows past 1 MiB when a large allocation is requested.
Kernel stacks of exited processes do not accumulate; `drain_dead()` reclaims them.
Double-free of a frame triggers a kernel panic with a diagnostic message.
All existing tests continue to pass without modification.

Related phases

Keep exploring the roadmap

Network

Add a minimal but real TCP/IP stack so the OS can send and receive packets over a network. A virtio-net NIC in QEMU is the hardware target. The end goal is a working `ping` and a simple TCP connection.

Directory VFS

Make the filesystem navigable. Right now `getdents64` returns ENOSYS, directories cannot be opened as file descriptors, every process thinks its working directory is `/`, and the ramdisk is a flat array with no directory hierarchy. This phase fixes all of that: directories become first-class objects, paths resolve relative to a real per-process working directory, and the ramdisk gains a tree structure so binaries live under `/bin` instead of floating in a flat namespace.