Buddy Allocator

From The Linux Memory Wiki

Frequently the kernel need to allocate dynamic memory for itself to do various tasks such as DMA operations, create descriptors and so on. To do this it have to know which page frame to allocate and which page frame is not free.

[hide]

Fragmentation Problem

Suppose the kernel need to allocate 1MB of contiguous physical memory, that requires 256 page frames of size 4KB. However suppose we have 256MB of contiguous free memory, we cannot simply choose any page frame from this 256 MB free memory. Because suppose if we then need 16MB of memory, then 64MB, then 8MB memory, doing so not carefully would be very messy and we would run out of free contiguous memory to allocate a 128MB memory, even though we still have more than 128MB available non contiguous memory.

The Buddy System Algorithm

The example just now was a simplified problem. We didn't consider about what if we need 95, or 150 page frames. We will consider this problem only when we talk about the Slab Allocator. For now we only consider what the kernel should do when we need 4KB * 2^x of memory.

The buddy system work like this: as initially suppose we have 256 free contiguous page frames, we divide them into smaller blocks half by half. For example, the initial configuration could be a 128-pages block, followed by 64, 32, 16, 8... and so on. So when the kernel needs 16 page frames, the buddy system will first return the 16-pages block if available. Suppose if all 16-pages blocks has already been used, then the buddy system will search if there is a 32-pages block, if so it will split the 32-pages block into two 16-pages blocks and allocate one of those to the kernel. If there is no 32-pages block, the system will try to find a 64-pages block and split it into two 32-pages block for the 16-pages block and so on.

After the kernel finished using the memory, the memory will be freed and the buddy system will attempt to merge smaller blocks back to larger blocks. So suppose if the buddy system found there is 2 consecutive 16MB blocks, it will then merge that to become one 32MB block.

The buddy allocator divide the memory into maximum of 11 different size of blocks, start from 1-page, 2-page, 4-page, up to 1024-pages of block size. Because of this, each zone descriptor has an array of 11 free_area struct to store the information of the free blocks. The 0th free_area will have pointers to all available 1-page blocks, 1st free_area contains pointers of 2-page blocks, and so on. The list of free blocks is stored in a linked list in free_area called the free_list. Each element of the free_list contains the pointer to the page descriptor of the first page frame in the block.

Buddy Allocator Functions

__rmqueue()

struct page * rmqueue(zone_t *zone, unsigned int order));

The __rmqueue() function accept 2 parameters, which is the address of the zone descriptor and the order of page frames required in power of 2. The function will run the buddy algorithm to find a contiguous 2^order of pages and it will return the linear address of the page descriptor of the first page frame. If no free page is found, NULL is returned.

The __rmqueue() function works by first loop through the array of free_area obtained from the given zone descriptor. It given look at the given order of free_area struct to see if any free block is available there. If not, it will go to the next larger free_area struct to search for free block and so on, just as described in the algorithm above.

[linuxkernelnewbies] Buddy Allocator - The Linux Memory Wiki