Linux uses the Buddy algorithm to effectively allocate and deallocate blocks of pages. The page allocation code
attempts to allocate a block of one or more physical pages. Pages are allocated in blocks which are powers of 2 in size. That means that it can allocate a block 1 page, 2 pages, 4 pages and so on. So long as there are enough free pages in the system to grant this request ( ) the allocation code will search the free_area for a block of pages of the size requested. Each element of the free_area has a map of the allocated and free blocks of pages for that sized block. For example, element 2 of the array has a memory map that describes free and allocated blocks each of 4 pages long.
The allocation algorithm first searches for blocks of pages of the size requested. It follows the chain of free pages that is queued on the list element of the free_area data structure. If no blocks of pages of the requested size are free, blocks of the next size (which is twice that of the size requested) are looked for. This process continues until all of the free_area has been searched or until a block of pages has been found. If the block of pages found is larger than that requested it must be broken down until there is a block of the right size. Because the blocks are each a power of 2 pages big then this breaking down process is easy as you simply break the blocks in half. The free blocks are queued on the appropriate queue and the allocated block of pages is returned to the caller.
Figure: The free_area data structure
For example, in Figure if a block of 2 pages was requested, the first block of 4 pages (starting at PFN 4) would be broken into two 2 page blocks. The first, starting at PFN 4 would be returned to the caller as the allocated pages and the second block, starting at PFN 6 would be queued as a free block of 2 pages onto element 1 of the free_area array.