Physical Memory

Before a kernel can map anything, it needs to know which physical addresses actually correspond to usable RAM, and which of those addresses are currently free versus already claimed by the kernel image, firmware structures, or another allocation. Physical memory management is the layer responsible for tracking this, one page frame at a time (conventionally 4 KB, matching the smallest page size paging supports), and it sits below both paging and any heap allocator built on top of it, neither of which can function without a source of physical frames to work with.

Discovering available memory

A kernel does not have to determine which physical addresses are usable RAM on its own; firmware already knows, since it initialized the memory controller, and reports this information through a memory map the kernel retrieves during early boot. On BIOS-based systems, this comes from the int 0x15, EAX=0xE820 firmware call, executed while still in real mode before entering protected mode, returning a series of entries each describing a contiguous range’s base address, length, and type (usable, reserved, ACPI reclaimable, ACPI NVS, or defective). UEFI systems instead call GetMemoryMap, which returns a conceptually similar list through a different structure and calling convention, without the same real-mode timing constraint. A bootloader following the Multiboot specification retrieves this information on the kernel’s behalf and passes it along in the boot information structure, sparing the kernel from implementing firmware-specific memory detection itself.

Regardless of source, a raw memory map is not immediately safe to treat as “everything marked usable is free”: the kernel’s own image occupies part of what firmware reports as usable memory, since firmware has no way to know in advance where a kernel will be loaded, and the memory map is generated before the kernel exists as a loaded, running entity at all. A kernel must additionally reserve the physical range its own code, data, and any early boot structures (page tables, a Multiboot info structure, an initial ramdisk) occupy before considering the rest of a “usable” region actually free.

Tracking allocation state

Once the set of usable frames is known, something has to track which of them are currently allocated. Several structures are common, trading off memory overhead against allocation speed and the granularity of operations they support efficiently.

A bitmap dedicates one bit per frame, set or clear according to whether that frame is in use; compact (roughly 32 KB of bitmap per gigabyte of physical memory managed) and simple to reason about, but a search for a free frame is a linear scan unless paired with auxiliary structures like a cached “first known-free index” hint to avoid rescanning already-full regions repeatedly.

uint8_t frame_bitmap[MAX_FRAMES / 8];

void mark_used(size_t frame) {
    frame_bitmap[frame / 8] |= (1 << (frame % 8));
}

int find_free_frame(void) {
    for (size_t i = 0; i < MAX_FRAMES; i++) {
        if (!(frame_bitmap[i / 8] & (1 << (i % 8))))
            return i;
    }
    return -1; // out of memory
}

A free list instead threads free frames together directly, storing a pointer to the next free frame inside the free frame itself, since a frame that is free has no other content that needs preserving, using its own space for bookkeeping costs nothing extra. Allocation and freeing are both constant-time, popping or pushing the list’s head, at the cost of needing a separate mechanism (typically a bitmap or a range check) to determine whether an arbitrary address is currently allocated, since walking the free list itself only reveals what is not allocated.

A buddy allocator, covered in more depth as a general technique under Heap Allocators, is also commonly used at the physical-frame level specifically, since page allocations frequently need more than one contiguous frame at a time (for a DMA buffer, or for a chunk large enough to back with a huge page), and a buddy allocator’s power-of-two blocks and fast, address-based coalescing suit that pattern well.

Reserved regions

Beyond the kernel’s own image, several other regions of physical memory are conventionally off-limits regardless of what the firmware memory map reports. The first megabyte of physical memory holds a mix of real-mode interrupt vectors, BIOS data areas, and legacy video memory that older or firmware-dependent code may still expect to find there, and is frequently left permanently reserved even on systems that no longer rely on any of it directly. ACPI tables, wherever firmware placed them, must remain intact for as long as the kernel intends to consult them, which for tables like the MADT (used to configure the APIC) is typically only during early boot, but for others may be indefinitely. Memory-mapped I/O regions, such as a PCI device’s Base Address Register targets, are not RAM at all despite occupying addresses in the same physical space, and must never be allocated as though they were general-purpose memory.

Implementation notes

Frame 0, physical address zero, deserves specific caution: allocating it and mapping it into a process’s address space means a null pointer dereference in that process silently reads or writes real, valid memory instead of faulting, defeating one of the more useful accidental protections a kernel gets for free. Most implementations simply mark frame 0 permanently reserved rather than risk this.

Fragmentation at the physical-frame level behaves differently from fragmentation in a general-purpose heap allocator: because every unit is exactly one frame in size, there is no internal fragmentation from mismatched allocation sizes the way a variable-size heap allocator experiences, but external fragmentation (enough total free frames existing, with none of the required multi-frame contiguous runs available) remains a real concern for anything requesting more than a single frame at once, which is the specific problem a buddy allocator’s structure is aimed at solving.

References

^ ACPI Specification: defines the E820 memory map entry format and its type field values.
^ UEFI Specification, EFI_BOOT_SERVICES.GetMemoryMap(): the corresponding UEFI-native memory discovery interface.

Physical Memory

Discovering available memory

Tracking allocation state

Reserved regions

Implementation notes

References

See also