Chapter 15: Physical Memory

15.1 Discovering Physical Memory

Before the kernel can manage memory, it must know what physical memory is available. On QEMU virt, the memory map is fixed (1 GB RAM starting at 0x40000000), but on real hardware we must parse the device tree.

The device tree contains memory nodes:

memory@40000000 {
    device_type = "memory";
    reg = <0x00000000 0x40000000  /* base address */
           0x00000000 0x40000000>; /* size (1 GB) */
};

We parse this in C:

struct mem_region {
    uint64_t base;
    uint64_t size;
};

#define MAX_REGIONS 16
static struct mem_region regions[MAX_REGIONS];
static int region_count;

void mem_discover(uint64_t dtb_addr) {
    /* Walk the device tree, find all "memory" nodes */
    /* For each, extract the reg property and add to regions[] */
    /* Exclude the region where our kernel is loaded (0x40000000 + size) */
}

15.2 The Physical Memory Map

Our kernel divides physical memory into regions:

Address         | Region              | Size
----------------+---------------------+--------
0x4000_0000     | Kernel code/data    | ~64 KB
0x4001_0000     | Kernel BSS/stack    | ~16 KB
0x4010_0000     | Page allocator      | varies
0x4020_0000     | Kernel heap         | grows
0x8000_0000     | Free for processes  | ~960 MB

The kernel itself occupies a small portion. Everything else is available for user processes, device mappings, and kernel heap.

15.3 Page Allocator

The simplest physical memory allocator is a page allocator that hands out 4 KB pages. We use a bitmap to track which pages are free:

#define PAGE_SIZE 4096
#define PAGE_SHIFT 12

static uint8_t *page_bitmap;   /* one bit per page */
static uint64_t total_pages;
static uint64_t free_pages;

void page_alloc_init(uint64_t mem_base, uint64_t mem_size) {
    total_pages = mem_size / PAGE_SIZE;
    free_pages = total_pages;

    /* The bitmap itself lives at a fixed address after the kernel */
    page_bitmap = (uint8_t *)(KERNEL_HEAP_START);

    /* Mark kernel memory as used */
    uint64_t kernel_pages = (KERNEL_HEAP_START - KERNEL_BASE) / PAGE_SIZE;
    for (uint64_t i = 0; i < kernel_pages; i++) {
        bitmap_set(page_bitmap, i);
        free_pages--;
    }
}

void *page_alloc(void) {
    for (uint64_t i = 0; i < total_pages; i++) {
        if (!bitmap_test(page_bitmap, i)) {
            bitmap_set(page_bitmap, i);
            free_pages--;
            return (void *)(i * PAGE_SIZE);
        }
    }
    return NULL;  /* out of memory */
}

void page_free(void *addr) {
    uint64_t page = (uint64_t)addr / PAGE_SIZE;
    bitmap_clear(page_bitmap, page);
    free_pages++;
}

15.4 Frame Allocation Strategy

A simple first-fit allocator works for early boot. Later, we may want a more sophisticated allocator (buddy allocator) to reduce fragmentation and support larger allocations. The buddy allocator splits and merges power-of-two page blocks:

/* Buddy allocator (simplified) */
#define MAX_ORDER 10  /* 2^10 = 1024 pages = 4 MB max allocation */

struct free_list {
    struct free_list *next;
};

static struct free_list freelists[MAX_ORDER + 1];
static uint64_t base_addr;

void buddy_init(uint64_t addr, uint64_t size) {
    base_addr = addr;
    uint64_t pages = size / PAGE_SIZE;
    for (int order = MAX_ORDER; order >= 0; order--) {
        uint64_t block_size = 1 << order;
        while (pages >= block_size) {
            /* Add block to freelist[order] */
            pages -= block_size;
        }
    }
}

void *buddy_alloc(int order) {
    /* Find smallest freelist with available blocks */
    for (int o = order; o <= MAX_ORDER; o++) {
        if (freelists[o].next) {
            /* Split if necessary */
            while (o > order) {
                /* Split block: put half back, continue with half */
                o--;
            }
            return remove_from_freelist(o);
        }
    }
    return NULL;
}

15.5 Our Implementation

In our kernel, physical memory management is initialized in kernel_main after the UART and exception handlers are ready:

void kernel_main(uint64_t dtb_addr, uint64_t cpu_id) {
    install_exception_vectors();
    enable_caches();
    uart_init();

    /* Discover physical memory from device tree */
    mem_discover(dtb_addr);

    /* Initialize the page allocator */
    page_alloc_init(regions[0].base, regions[0].size);

    uart_puts("Free pages: ");
    uart_putdec(free_pages);
    uart_puts("\r\n");
}

With physical memory management in place, we can allocate pages for page tables, process control blocks, and kernel heap. This is the foundation for virtual memory (next chapter).

15.6 Exercises

15.7 Summary

Physical memory management is the kernel's lowest-level memory subsystem. It discovers available RAM from the device tree, tracks which pages are free using a bitmap or buddy allocator, and provides page allocation and deallocation. All higher memory structures (page tables, kernel heap, process memory) are built on top of the physical page allocator.