The Pages Remember

Every task we place needs memory: stacks, queues, buffers, device rings, and later whole address spaces. Until now the lessons have carved those by hand. Today Alquist stops treating memory as empty land and starts treating it as owned territory.

Goal

Introduce the memory manager as a set of layers, not as one toy allocator. At the bottom it owns physical pages. Above that, it serves different kinds of requests: ordinary kernel objects, task stacks, page tables, DMA-safe buffers, and eventually user mappings. The first lesson is ownership: every usable page has a record, every allocation has a reason, and no subsystem gets to invent memory by naming an address.

The layers

A real manager is more than a list of free pages. Alquist needs at least four ideas to live together: a physical page layer that knows which frames exist, a kernel heap for small objects, special regions for DMA and coherent device memory, and the virtual mappings that decide how those physical pages appear once the MMU is on.

// memory manager shape, not a complete header
typedef enum {
    PAGE_FREE,
    PAGE_KERNEL,
    PAGE_TABLE,
    PAGE_STACK,
    PAGE_DMA,
    PAGE_USER,
} page_owner_t;

typedef struct page {
    uintptr_t    phys;
    page_owner_t owner;
    unsigned     order;       // 0 = 4 KB, 1 = 8 KB, 2 = 16 KB, ...
    unsigned     refcount;
    struct page *next;
} page_t;

That small record is already a different thing from a bare bit. A bit can say "free" or "taken". A page descriptor can remember why it is taken, how large the allocation was, whether it is shared, and which free list it belongs to when it returns.

Pages remember

The MMU taught us the hardware's favorite unit: aligned pages. The memory manager keeps a page map, an array of descriptors indexed by physical page number. Once that map exists, the kernel can answer questions it could not answer before: is this page free, is it a page table, can DMA touch it, should it be returned to the heap, or is it pinned for a device?

#define PAGE_SIZE 4096UL

static page_t *page_map;
static uintptr_t managed_base;
static unsigned managed_pages;

static page_t *page_from_phys(uintptr_t phys) {
    return &page_map[(phys - managed_base) / PAGE_SIZE];
}

Free lists, not a long scan

A first draft can scan the page map from the beginning every time. A living kernel quickly outgrows that. The usual next step is to keep free lists by allocation order: one list for single pages, another for two-page runs, another for four-page runs, and so on. Whether the implementation is a strict buddy allocator or a simpler ordered-list variant, the contract is the same: callers ask for an order, and the manager returns a contiguous run of pages or says no.

#define MAX_ORDER 10              // up to 4 MB with 4 KB pages

static page_t *free_area[MAX_ORDER + 1];

void *alloc_pages(unsigned order, page_owner_t owner) {
    spin_lock(&memory_lock);

    page_t *page = remove_suitable_run(order);
    if (page != 0) {
        mark_run(page, order, owner);
        spin_unlock(&memory_lock);
        return (void *)page->phys;
    }

    spin_unlock(&memory_lock);
    return 0;
}

This still fits the spirit of the tutorial: the allocator is understandable. But it also matches the shape of a kernel that has real users: stacks ask for one page, page tables ask for clean pages, network and storage drivers may ask for low or aligned memory, and the heap can refill itself with runs when its small-object pools run dry.

The heap is a customer

kmalloc is not the same thing as alloc_pages. Small kernel objects should not waste a whole 4 KB frame each. The heap takes pages from the physical layer and splits them into smaller blocks or caches. When a cache empties, whole pages can return to the page layer. That keeps the accounting honest: small allocations are convenient, but the page manager still knows where the physical memory went.

void *kmalloc(size_t size) {
    heap_class_t *class = class_for_size(size);

    if (class->free == 0) {
        void *page = alloc_pages(0, PAGE_KERNEL);
        if (page == 0)
            return 0;
        heap_grow(class, page);
    }

    return heap_take(class);
}

Some memory is special

Drivers make the manager more honest. A UART buffer is ordinary. A network descriptor ring, an SD transfer buffer, or a framebuffer is not. Devices may need physical contiguity, cache-line alignment, low addresses, or memory mapped with device/coherent attributes. That is why ownership records matter: PAGE_DMA is not decoration. It is a warning label for cache maintenance and mapping rules.

void *dma_alloc_pages(unsigned order) {
    void *phys = alloc_pages(order, PAGE_DMA);
    if (phys == 0)
        return 0;

    map_device_buffer(phys, order);
    clean_invalidate_range(phys, PAGE_SIZE << order);
    return phys;
}

Let the shell ask

The shell from article ten should be able to ask the manager what it remembers. A useful mem command does not only print "free bytes". It separates free pages, heap use, page tables, stacks, DMA buffers, and anything pinned for devices. That turns memory pressure into something visible.

alquist> mem
pages: total=523488 free=522901 used=587
owners: kernel=64 tables=9 stacks=12 dma=32 user=0
heap: small=18 pages, large=3 pages
dma: coherent=32 pages

What actually happens

Early boot reserves the kernel image, boot stacks, page tables, device windows, and the memory manager's own metadata. Everything left becomes page descriptors in the page map. From that point on, subsystems stop carving random addresses. The scheduler asks for stacks. The heap asks for backing pages. The MMU code asks for page tables. Drivers ask for DMA-safe buffers. Each request leaves a trace in the owner field.

The important shift is not that the manager can hand out memory. The important shift is that memory now has a story. When a page is missing, leaked, shared, pinned, or unsafe for DMA, the kernel has a place to remember why.

Try it

Boot the image, open the shell, and ask for memory before and after creating work. The exact numbers depend on the image size and enabled drivers, but the shape should be clear: stacks, heap growth, page tables, and DMA buffers show up as different owners instead of one anonymous pile.

alquist> mem
    pages: total=523488 free=522913 used=575
    owners: kernel=64 tables=9 stacks=0 dma=32 user=0
    heap: small=16 pages, large=2 pages
alquist> run noisy on core 2
placed 'noisy' on core 2
alquist> mem
    pages: total=523488 free=522912 used=576
    owners: kernel=64 tables=9 stacks=1 dma=32 user=0
    heap: small=16 pages, large=2 pages

This is still not the end of memory management. It is the point where the kernel can finally grow without lying to itself. Later, user address spaces, copy-on-write, file-backed pages, and swapping can all be built on top of the same discipline: every page has an owner, and the owner is recorded.