In the previous post, we laid the hardware foundation for our virtual memory subsystem: configuring the MMU, setting up MAIR attributes, and establishing an identity mapping to ensure our kernel survived the transition to address translation. While we successfully enabled translation without crashing, our current translation tables are backed by statically reserved storage. To build a proper kernel address space, we need to construct new tables dynamically, which in turn requires a way to allocate the physical page frames backing our virtual mappings.
This brings us to a bootstrapping problem: before we can build the kernel’s higher-half mapping, we need to allocate the physical memory required for its page tables. While more sophisticated allocation strategies, such as the buddy system, are commonly used in production kernels, our current requirements are more focused. Every physical memory consumer in our immediate scope (including the page tables used for dynamic mappings) needs individual page frames rather than variable-sized, contiguous regions. A fixed-granularity allocator is therefore a natural fit for this stage of development.
In this post, we’ll explore the design space of physical frame allocation, examine how Linux uses memblock to manage physical memory during early boot, and look at why its region-based approach doesn’t map directly onto the allocator we’re building. Finally, we’ll implement a page-based free-list allocator inspired by xv6, adapting it to our kernel’s memory layout and using it to lay the groundwork for the transition to the higher half.
The Bootstrapping Problem
Our next milestone is to move the kernel into the higher half of the address space. Unlike the identity mapping we established in the previous post, this requires building a new set of page tables to map the kernel’s physical memory into its intended virtual address range.
Until now, our page-table storage has been explicitly reserved in the linker script. The identity-mapping code uses these predefined regions to construct the translation tables, which is sufficient for our current setup. However, as we move towards a more flexible address space, we can no longer rely on a fixed amount of statically reserved memory for every new mapping.
Page tables are themselves stored in physical memory, and building a new translation hierarchy requires us to allocate physical frames to hold them. Before we can construct the higher-half mapping, we therefore need a mechanism that allows the kernel to obtain physical memory on demand.
This is the bootstrapping problem: we need a way to manage physical memory before we can use that memory to build a more flexible virtual memory subsystem. The first step towards resolving this dependency is to introduce a physical frame allocator.
Physical Frame Allocation
A physical frame allocator manages physical memory in units of page frames. A page refers to a fixed-size block of virtual memory, while a frame refers to the corresponding block of physical memory. In our kernel, the native page size is 4 KiB, so the allocator operates on 4 KiB physical frames.
Its interface is deliberately simple:
- Allocate: provide a free physical frame when requested.
- Free: mark a previously allocated frame as available again.
The allocator does not manage virtual addresses or establish mappings. It only manages the availability of physical frames. The virtual memory subsystem is responsible for mapping those frames into the address space.
There are several ways to implement a physical frame allocator. The most common approaches include bitmaps, free lists, and buddy allocators.
Bitmap Allocator
A bitmap allocator maintains one bit for each physical frame. The bit indicates whether the corresponding frame is free or allocated.
To allocate a frame, the allocator searches for a bit representing a free frame and marks it as allocated. To release a frame, it clears the corresponding bit.
A bitmap requires relatively little metadata and makes it straightforward to determine whether a particular frame is free. However, finding a free frame may require scanning the bitmap. This can become expensive as the amount of physical memory increases, although techniques such as maintaining a search cursor or scanning multiple bits at once can improve performance.
Free-List Allocator
A free-list allocator maintains a collection of currently available frames. One way to implement it is to store a pointer to the next free frame inside each free frame itself.
The allocator only needs to maintain a pointer to the head of the list. Allocating a frame removes it from the list, while freeing a frame adds it back.
This approach has very little metadata overhead and allows allocation and deallocation to be performed in constant time. However, it is not well suited to finding specific frames or allocating contiguous runs of multiple frames.
Buddy Allocator
A buddy allocator manages physical memory in blocks whose sizes are powers of two. When a sufficiently large block is requested, the allocator can split it into smaller blocks. When two adjacent blocks, known as buddies, become free, they can be merged back together.
This allows the allocator to support both individual frames and larger contiguous memory allocations while limiting external fragmentation. The trade-off is increased implementation complexity and additional metadata compared with a simple free list.
Choosing an Approach
The immediate consumers of our allocator need individual physical frames. In particular, the page tables required for dynamic mappings are allocated one frame at a time. We do not currently need to allocate variable-sized or physically contiguous memory regions.
A page-based free-list allocator is therefore sufficient for our current requirements. Its implementation is straightforward, its metadata requirements are minimal, and its allocation and deallocation operations are simple.
For the implementation, we will use an approach inspired by xv6: free physical frames will be linked together through their own memory, with the allocator maintaining a pointer to the first available frame.
Before implementing this allocator, it is useful to examine how physical memory is managed during the early boot process of a production kernel such as Linux.
Early-Boot Memory Management in Linux
When I first started looking into physical memory allocation, I was unsure which approach would be appropriate for the kernel. I explored several resources, including the xv6 kernel, the OSDev Page Frame Allocation article, and the way Linux manages physical memory during early boot.
My initial conclusion was that I needed something similar to Linux’s memblock allocator.
What Is memblock?
Linux uses memblock during early boot to keep track of physical memory regions. At this stage, the regular page allocator is not yet available, so the kernel needs an intermediate mechanism for recording which parts of physical memory are available and which parts are reserved.
Rather than managing memory one page at a time, memblock maintains lists of memory regions. During device tree parsing, Linux discovers the available RAM and adds those regions to its internal memory map. It can then reserve portions of that memory for specific purposes, such as the kernel image or memory explicitly marked as reserved in the device tree.
This approach is useful when the physical memory layout is complex. The available RAM may be divided into multiple regions, and several areas may need to be excluded before the remaining memory can be handed over to the regular physical page allocator.
Why I Did Not Use memblock?
After looking more closely at my kernel’s current requirements, I realized that a memblock-like allocator would be more general than I needed.
At this point, the kernel has a very simple memory layout. There is only one RAM region, and the two areas that must be excluded from allocation are:
- The device tree blob.
- The kernel image.
I am not currently parsing or handling reserved-memory nodes in the device tree, nor do I have to account for the more complex memory layouts that a production kernel such as Linux must support.
A region-based allocator would certainly be capable of managing this situation, but it would introduce additional bookkeeping that is not necessary at this stage of development. I therefore decided to use a simpler free-list allocator, inspired by the approach used in xv6.
The goal is not to build the most general physical memory manager immediately. Instead, it is to introduce the minimum mechanism required to allocate and release individual physical frames while keeping the implementation easy to understand and extend.
With that decision made, we can now look at how the allocator is implemented and how it is integrated into the kernel’s boot sequence.
Implementing the Frame Allocator in Rust
With the allocator design settled, we can now implement it in the kernel. The implementation follows the same basic approach used by xv6: free physical frames are linked together in a singly linked list, with the list itself stored inside the free frames.
Discovering Physical Memory
The first piece of information the frame allocator needs is the range of physical memory available to the kernel. This information is already available during device tree parsing.
As part of extending the DTB parser to handle memory nodes, I also had to slightly generalize the mechanism used to match device nodes with their initialization functions. Previously, devices were matched exclusively through their compatible property. However, the memory node in the device tree is identified through its device_type property rather than compatible.
The device matching code was therefore extended to support both types of criteria:
#[derive(Clone, Copy)]
pub enum MatchCriteria {
Compatible(&'static str),
DeviceType(&'static str),
}
fn node_matches(dev: &device::PlatformDevice, criteria: device::MatchCriteria) -> bool {
let (prop_name, target) = match criteria {
device::MatchCriteria::Compatible(target) => ("compatible", target),
device::MatchCriteria::DeviceType(target) => ("device_type", target),
};
dev.find_property(prop_name)
.is_some_and(|prop| compatible_matches(prop, target))
}
This allows the memory node to be handled by the same device initialization mechanism as the other devices, while using the property that actually identifies that type of node.
The memory setup function then extracts the physical base address and size from the node’s reg property and stores the resulting RAM range in the meminfo module. The range can later be retrieved through meminfo::ram_range(), which provides the allocator with the physical start address and total RAM size. The details of parsing the reg property were covered in the previous post, so we can treat that information as an input to the frame allocator here.
During kernel initialization, the RAM range and DTB boundaries are passed to frame_alloc::init():
let (ram_start, ram_size) = meminfo::ram_range();
frame_alloc::init(
ram_start,
ram_size,
dtb_addr,
dtb_addr + dtb::dtb_size(dtb_addr) as u64,
);
This keeps the responsibilities separated. The DTB subsystem discovers the physical memory layout; the frame allocator uses that information to determine which individual frames can be added to the free list.
Representing the Free List
The free list is implemented as a stack. Each free frame contains a pointer to the next free frame:
#[repr(C)]
#[derive(Copy, Clone)]
struct Frame {
pub next: *mut Frame,
}
The allocator only needs to maintain a pointer to the first free frame:
static FREE_LIST: Mutex<*mut Frame> = Mutex::new(core::ptr::null_mut());
This is the same basic technique used by xv6. Because a free frame is not being used by the kernel for any other purpose, its memory can be reused to store the allocator’s metadata.
The result is a very small amount of allocator state: the head of the free list, plus the next pointer stored in each free frame.
Initializing the Free List
The allocator’s init() function receives the RAM range and the DTB range. The kernel boundaries are obtained directly from symbols exported by the linker script:
let kernel_start = PhysAddr::new(core::ptr::addr_of!(__kernel_start) as u64);
let kernel_end = PhysAddr::new(core::ptr::addr_of!(__stack_top) as u64);
At this point, the allocator knows the two occupied ranges that must be excluded from the RAM region:
- The device tree blob.
- The kernel image.
These occupied ranges divide the RAM into three usable regions. The two occupied ranges are reordered by physical address so that they can be printed in a consistent order for debugging. The allocator then frees the regions surrounding them:
let mut occupied_ranges = [(kernel_start, kernel_end), (start_dtb, end_dtb)];
if occupied_ranges[0].0 > occupied_ranges[1].0 {
occupied_ranges.swap(0, 1);
}
println!("Occupied range 0: [{:#X}-{:#X}]", occupied_ranges[0].0, occupied_ranges[0].1);
println!("Occupied range 1: [{:#X}-{:#X}]", occupied_ranges[1].0, occupied_ranges[1].1);
free_range(start_ram, occupied_ranges[0].0);
free_range(occupied_ranges[0].1, occupied_ranges[1].0);
free_range(occupied_ranges[1].1, ram_end);
This is deliberately simpler than maintaining a generic collection of reserved regions. As discussed earlier, the current kernel only has these two exclusions, so there is no need to introduce additional bookkeeping for memory reservations that the kernel does not yet support.
free_range() then walks through each usable region one page at a time:
fn free_range(start: PhysAddr, end: PhysAddr) {
let page_size = PAGE_SIZE as u64;
let mut page = start.align_up(page_size);
let end = end.align_down(page_size);
while page < end {
free(page);
page = page + page_size;
}
}
The boundaries are aligned to the 4 KiB page size before frames are added to the allocator. Each resulting frame is passed to free(), which inserts it into the free list.
This means initialization does not require a separate mechanism for constructing the list. The same operation used to return a frame to the allocator is also used to populate the allocator for the first time.
Allocating a Frame
Allocation simply removes the first frame from the stack:
FREE_LIST.lock_irqsafe(|head| {
frame = *head;
if !frame.is_null() {
*head = (*frame).next;
}
});
If the list is empty, frame remains null. Otherwise, the current head becomes the returned frame and the list head advances to the next frame.
The operation is protected by the IRQ-safe mutex so that access to the free-list state remains synchronized with interrupt handling.
After removing a frame from the list, the implementation fills the frame with a known byte pattern before returning its physical address:
core::ptr::write_bytes(frame as *mut u8, 0x3E, PAGE_SIZE);
This is not part of the allocator's core allocation mechanism; it provides a predictable memory pattern when a frame is allocated, which can also make memory-related bugs easier to identify during debugging.
Freeing a Frame
Returning a frame is the reverse operation. The frame is first filled with another known pattern and then inserted at the head of the free list:
let frame = addr.as_mut_ptr::<Frame>();
FREE_LIST.lock_irqsafe(|head| {
(*frame).next = *head;
*head = frame;
});
The frame therefore becomes the new head of the stack, with its next pointer referring to the frame that was previously at the head.
Both allocation and deallocation are consequently constant-time operations. No bitmap needs to be searched and no additional metadata needs to be maintained outside the free frames themselves.
Next Steps
With the physical frame allocator in place, the kernel now has the primitive required to construct page tables dynamically. In the next post, we will use it to replace the current identity mapping with a full four-level translation hierarchy, enabling 4 KiB page granularity and the move to the "high half" of the virtual address space.
The complete implementation of the concepts discussed in this post can be found in the project's GitHub repository.