osdev-memory-management

name	osdev-memory-management
description	Physical and virtual memory allocators for OS kernels. Bitmap, stack, buddy frame allocators, slab allocator, kernel heap. Use when implementing memory allocation, page frame management, or kernel heap.
origin	MCC

Physical and Virtual Memory Allocation

Complete reference for implementing memory allocation in OS kernels: memory map parsing, physical frame allocators, virtual address space layout, and kernel heap design.

When to Use

• Building a physical page frame allocator from scratch
• Implementing a kernel heap (kmalloc/kfree)
• Parsing memory maps from Multiboot or UEFI to find usable RAM
• Choosing between bitmap, stack, and buddy allocator designs
• Adding a slab allocator for fixed-size kernel objects
• Debugging memory corruption, double-free, or fragmentation issues

Memory Map

Before you can allocate anything, you need to know which physical memory regions are usable. The firmware provides this information, and you must parse it before your first allocation.

Why this matters: Physical RAM is not a contiguous usable block. BIOS data, ACPI tables, memory-mapped I/O, and the kernel itself occupy fixed regions. Allocating from reserved memory corrupts firmware structures or hardware registers silently.

Multiboot (BIOS boot)

Multiboot provides a memory map via the mmap_* fields in the Multiboot info structure. Each entry describes a region with a base address, length, and type:

Type	Meaning
1	Available RAM (safe to use)
2	Reserved (do not touch)
3	ACPI reclaimable (usable after parsing ACPI tables)
4	ACPI NVS (do not touch)
5	Bad memory

UEFI Boot

UEFI provides EFI_MEMORY_DESCRIPTOR entries via GetMemoryMap(). Key types:

Type	Meaning
EfiConventionalMemory	Available RAM
EfiBootServicesCode/Data	Usable after ExitBootServices()
EfiRuntimeServicesCode/Data	Reserved for UEFI runtime (do not touch)
EfiACPIReclaimMemory	Usable after ACPI parsing
EfiReservedMemoryType	Do not touch

Practical Steps

1. Iterate the memory map entries from the bootloader
2. Mark all type-1 (available) regions as free in your allocator
3. Mark everything else as reserved (including gaps between entries)
4. Additionally reserve: the kernel's own physical pages, the page tables you are currently using, and the memory map data itself
5. Align all region boundaries to page size (4KB) -- round start up, round end down

Physical Frame Allocator

The frame allocator hands out 4KB-aligned physical page frames. Its clients (the virtual memory manager, DMA setup) do not care which specific frame they get -- they just need one that is free.

Approach Comparison

Allocator	Alloc	Free	Memory Overhead	Contiguous Alloc	Best For
Bitmap	O(n)	O(1)	1 bit per frame (128KB for 4GB)	Scan required	Simple kernels, learning
Stack	O(1)	O(1)	4/8 bytes per free frame	Not supported	Fast single-page alloc
Buddy	O(log n)	O(log n)	~2x bitmap	Native (power-of-2)	Production kernels, DMA

Bitmap Allocator

One bit per physical frame. Bit 0 = free, bit 1 = used (or vice versa). The simplest correct allocator.

#define FRAME_SIZE 4096
#define BITMAP_SIZE(mem_bytes) ((mem_bytes) / FRAME_SIZE / 8)

static uint8_t bitmap[BITMAP_SIZE(MAX_PHYS_MEM)];

/* Mark a frame as used */
void frame_set(uint64_t phys_addr) {
    uint64_t frame = phys_addr / FRAME_SIZE;
    bitmap[frame / 8] |= (1 << (frame % 8));
}

/* Mark a frame as free */
void frame_clear(uint64_t phys_addr) {
    uint64_t frame = phys_addr / FRAME_SIZE;
    bitmap[frame / 8] &= ~(1 << (frame % 8));
}

/* Allocate one frame -- returns physical address or 0 on failure */
uint64_t frame_alloc(void) {
    for (uint64_t i = 0; i < sizeof(bitmap); i++) {
        if (bitmap[i] == 0xFF) continue;  /* all 8 frames used */
        for (int bit = 0; bit < 8; bit++) {
            if (!(bitmap[i] & (1 << bit))) {
                bitmap[i] |= (1 << bit);
                return (i * 8 + bit) * FRAME_SIZE;
            }
        }
    }
    return 0;  /* out of memory */
}

Optimization: Test 32 or 64 bits at once with uint32_t/uint64_t comparisons. A word that equals ~0 has no free frames -- skip it. Keep a hint pointer to the last successful allocation position to avoid rescanning from zero.

Stack Allocator

Push free frame addresses onto a stack. Alloc = pop, free = push. O(1) for both, but cannot allocate contiguous ranges and uses more memory (one pointer per free frame).

Buddy Allocator

Maintains free lists for power-of-2 sized blocks (4KB, 8KB, 16KB, ..., up to some maximum). When a block of size 2^k is requested and none is available, a block of size 2^(k+1) is split into two "buddies." When both buddies are free, they coalesce back into the larger block.

Why buddy matters: DMA controllers often need physically contiguous buffers larger than one page. The buddy system finds contiguous regions in O(log n) time and prevents external fragmentation through coalescing.

See references/physical-allocators.md for detailed implementations of all three allocators.

Virtual Address Space

Once you have a frame allocator and paging set up (see osdev-paging), you need to decide how to lay out virtual memory.

Typical Layout (x86-64, Higher-Half Kernel)

0x0000000000000000 -- 0x00007FFFFFFFFFFF   User space (128 TB)
    Text, data, heap (grows up), mmap region, stack (grows down)

--- canonical hole (non-addressable) ---

0xFFFF800000000000 -- 0xFFFF80FFFFFFFFFF   Direct physical map (all RAM mapped 1:1)
0xFFFF810000000000 -- 0xFFFF8FFFFFFFFFFF   vmalloc / ioremap region
0xFFFFFF0000000000 -- 0xFFFFFFFFFFFFFFFF   Kernel text, data, heap
0xFFFFFFFF80000000 -- 0xFFFFFFFFFFFFFFFF   Kernel image (common -2GB mapping)

Direct physical map: Many kernels map all physical RAM at a fixed offset in kernel space. This lets you convert any physical address to a virtual one by adding the offset, which is essential for accessing page table entries, DMA buffers, and frame metadata without temporary mappings.

Demand Paging

Do not map all of a process's memory upfront. Instead:

1. Mark pages as not-present in the page tables
2. When the process accesses them, a page fault fires
3. The fault handler allocates a frame, maps it, and resumes execution

This lets processes have large virtual address spaces while only consuming physical RAM for pages they actually touch.

Kernel Heap

The frame allocator gives you 4KB pages. The kernel also needs to allocate small, variable-size objects (a 48-byte task struct, a 128-byte file descriptor, a 16-byte list node). That is what the kernel heap provides.

Why You Need One

Without a heap, every kernel data structure must either be statically allocated or consume an entire 4KB page. A linked list node using a full page wastes 99.6% of the frame. The heap carves pages into smaller allocations efficiently.

Slab Allocator

The slab allocator creates caches for fixed-size objects. Each cache manages a pool of pre-allocated objects of one specific size.

Why slab exists: Kernel objects like task structs, inodes, and socket buffers are allocated and freed thousands of times per second, always the same size. A general-purpose allocator wastes time on splitting, coalescing, and searching. Slab eliminates this overhead by recycling fixed-size slots.

How it works:

1. Create a cache: struct kmem_cache *task_cache = slab_create("task", sizeof(struct task), 0);
2. Allocate: struct task *t = slab_alloc(task_cache); -- returns a pre-initialized slot in O(1)
3. Free: slab_free(task_cache, t); -- returns slot to the free list, no coalescing needed

Each cache holds one or more slabs -- contiguous pages divided into equal-sized slots with a free list threading through them. When all slots in all slabs are used, the cache requests new pages from the frame allocator.

General-Purpose Heap (kmalloc/kfree)

For variable-size allocations that do not fit a dedicated slab cache, provide a general-purpose allocator. Common approaches:

Approach	Description	Trade-off
Size-class bins	Maintain free lists for power-of-2 sizes (8, 16, 32, ..., 4096)	Fast, some internal fragmentation
Linked-list first-fit	Free blocks in a linked list, scan for first fit	Simple, O(n) allocation, fragments over time
Slab-backed buckets	Create slab caches for common sizes, fall back to page allocator for large	Best of both worlds, more complex

Minimal kmalloc interface:

/* Allocate at least 'size' bytes of kernel memory */
void *kmalloc(size_t size);

/* Free memory previously returned by kmalloc */
void kfree(void *ptr);

/* Allocate and zero-initialize */
void *kzalloc(size_t size);

The allocator typically stores a small header before each allocation containing the block size (so kfree does not need a size argument) and metadata for the free list.

See references/heap-algorithms.md for slab internals and general-purpose allocator implementation details.

Common Pitfalls

1. Using memory before parsing the memory map. Your kernel image, stack, and page tables occupy physical memory. If you do not reserve them in the frame allocator, you will allocate over your own kernel.

2. Off-by-one in bitmap indexing. Frame N corresponds to bit N, not byte N. Mixing up frame / 8 (byte index) and frame % 8 (bit index) corrupts adjacent frames' state.

3. Forgetting to align slab objects. Kernel objects often contain pointers that require natural alignment (8 bytes on x86-64). Misaligned allocations cause performance penalties or faults on strict-alignment architectures.

4. No overflow protection on the heap. Without guard pages or canaries between allocations, a buffer overflow in one kernel object silently corrupts the next. At minimum, add magic values to block headers and check them on free.

5. Allocating in interrupt context. If your allocator takes a lock, allocating inside an interrupt handler can deadlock if the interrupted code already holds that lock. Either use lock-free allocation paths for interrupt context or disable interrupts around allocator locks.

6. Ignoring fragmentation. A linked-list heap that never coalesces adjacent free blocks will eventually fail to satisfy large allocations even when total free memory is sufficient. Always merge neighboring free blocks on free.

7. Returning physical addresses from kmalloc. The heap returns virtual addresses. If you need a physical address (for DMA), convert explicitly using your virtual-to-physical mapping, or use a dedicated DMA allocation path.

Related Skills

• osdev-paging -- virtual memory and page tables (prerequisite for virtual address space management)
• osdev-toolchain -- cross-compiler setup, linker scripts, QEMU debugging
• osdev-interrupts -- page fault handler (needed for demand paging)
• osdev-process-scheduling -- process address spaces and context switching