Early-boot Memory Allocation

Early in the initialisation of the kernel, there is a period of time in which the kernel needs access to memory allocations, however the primary memory allocators (such as the buddy allocator and the slab allocator) are not yet initialised. The memory allocators themselves will also require memory in which they can store their own data (such as data structures tracking page allocations), and the amount of space required for this data will not be known until runtime.

To enable these components to access the dynamic memory allocations they need, a relatively simple early-boot memory allocator is provided, or “bootmem” for short. The bootmem allocator keeps track of memory regions that are available for use, and can issue allocations from those memory regions to kernel components that require them.

As the bootmem allocator is only needed for a handful of tasks, it does not feature any advanced functionality such as merging and splitting operations intended to reduce external fragmentation. Memory allocations are made in a simple manner - when an early-boot kernel component needs memory, they request an amount from the bootmem allocator, which then removes a space of the requested size from one of the regions of memory marked available.

The allocator does support issuing memory at requested alignments. This is useful for components that require alignment in their data structures, such as the paging system which will require early page tables to be page aligned.

The allocator does not support de-allocation of memory, as this is not required by its users, and would significantly increase complexity unnecessarily.

The bootmem allocator expects to be provided with information on which regions of memory are available, and which regions should be avoided (for example, memory reserved for device I/O). In the x86 implementation, the Multiboot parser extracts memory availability data from the Multiboot header and passes it to bootmem.

In summary, bootmem ensures that early-boot kernel components can access the memory allocations they need to initialise critical systems in a consistent and managed fashion.

Key Functions

• bootmem_add_mem_region() - Registers a region of memory (usable or unusable) with the bootmem allocator. To be called by components which enumerate available memory regions, such as the Multiboot parser.
• bootmem_alloc() - Returns a region of usable memory of the requested size and alignment. The alignment parameter can be used to ensure that page tables constructed before primary memory allocators are available can be correctly page aligned.

Example Usage

Requesting memory from bootmem is very simple - the below example shows a sample request:

void * mem = bootmem_alloc(4096, BM_NO_ALIGN);
if(!mem) {
	klog("Failed to retrieve memory from bootmem!\n");
	return;
}
klog("Memory allocated at 0x%x\n", mem);

Bootmem will return NULL if no suitable memory can be found - in the majority of kernel components that request memory from bootmem, this will cause a kernel panic, as these data structures are generally critical. The next example uses bootmem to retrieve page-aligned memory for the construction of a new page table:

pgd_t * pgd = bootmem_alloc(PAGE_SIZE, PAGE_SIZE);
if(!pgd) {
    klog("Failed to retrieve page-aligned memory from bootmem!\n");
    return;
}
klog("Page-aligned memory allocated at 0x%x\n", pgd);

Relevant Source

• kernel/mm/bootmem.c - Contains the full implementation of the allocator.
• include/rotary/mm/bootmem.h - Contains function prototypes and definitions for the allocator.

Additional Reading

I’ve also written a blog post discussing my implementation of a bootmem allocator that may (or may not) be of interest. This post explains more of the reasoning behind my implementation choices.