Page Frame Allocation

Rotary uses a buddy allocator to efficiently allocate and free physical page frames, minimizing external fragmentation. It ensures that memory remains available for large allocations even after multiple allocation/deallocation cycles. The buddy allocator is the sole mechanism for allocating physical pages in the kernel.

All physical pages present in a system are represented by a struct page. These structures maintain information about the page such as its Page Frame Number (PFN), use count, and a node linking it to its relevant buddy allocator list. All physical pages are tracked using their corresponding struct page, which serves as the metadata for allocation and management.

An array containing all struct page entries for all present pages is initialised at start-up by the buddy allocator (buddy_init()). The buddy allocator uses information provided by bootmem to know how many struct page entries will be needed to cover the entirety of the system’s physical memory.

Buddy Allocation

The buddy allocator works by dividing physical memory into blocks, where each block contains a number of pages equal to a power of two. When a request is made for a block of pages, the allocator searches its lists of blocks to find a block of an appropriate size. If no suitable block is found, the allocator splits a larger block into two equal parts: one fulfills the request, while the other (the buddy) remains available for future allocations.

When a request to free a block is made, the allocator will attempt to merge, or “coalesce” the block with its buddy. If the buddy block is free, the two blocks will be merged back into a single block of a higher order. This proactive merging ensures that memory does not become fragmented with small, scattered allocations, making large contiguous allocations easier to satisfy.

As this page intends to provide a high-level overview of the buddy allocator and its place within rotary, for more detailed implementation information I recommend my blog post, which discusses the concept of the buddy allocator in far greater detail.

Allocator Initialisation

Before the buddy allocator can allocate memory, it must set up data structures to track and manage all available physical pages and their corresponding block lists.

The allocator first creates an array of struct page, sized dynamically based on the number of physical pages reported by the bootmem subsystem. This array is allocated using bootmem_alloc() and is one of the primary consumers of the bootmem allocator.

Each struct page is assigned its Page Frame Number (PFN) and initialized with its order and buddy list node. However, at this stage, pages do not yet belong to any block list.

buddy_init() creates the page metadata but does not determine which regions are usable. To handle this, bootmem_mark_free() is called, which iterates through all pages and marks usable ones as free by calling page_initial_free().

When page_initial_free() is called on a page, the allocator recursively merges it into larger blocks (higher-order blocks) whenever possible. This continues until the highest possible order is reached for that block, at which point it is added to the appropriate free list.

Relevant Source

Implementations

  • arch/<arch>/kernel/paging.c - Handles architecture-specific paging setup, such as the creation of the kernel’s page directory.
  • kernel/mm/palloc.c - Contains the buddy allocator implementation.
  • kernel/mm/ptable.c - Contains architecture-independent functions to create, manipulate, and destroy page tables. Invokes functions and macros from architecture-specific implementations.

Headers

Additional Reading

For a deeper dive into my implementation decisions, see my blog post covering the development of my allocator.