Page Allocation and Deallocation
There are many demands on the physical pages in the system.
For example, when an image is loaded into memory the operating system
needs to allocate pages.
These will be freed when the image has finished executing and is
Another use for physical pages is to hold kernel specific data structures
such as the page tables themselves.
The mechanisms and data structures used for page allocation and
deallocation are perhaps the most critical in maintaining the efficiency
of the virtual memory subsystem.
All of the physical pages in the system are described by the
mem_map data structure which is a list of mem_map_t**
structures which is initialized at boot time.
Each mem_map_t describes a single physical page in the system.
Important fields (so far as memory management is concerned) are:
- This is a count of the number of users of this page.
The count is greater than one when the page is shared between many
- This field describes the age of the page and is used
to decide if the page is a good candidate for discarding or
- This is the physical page frame number that this mem_map_t describes.
The free_area vector is used by the page allocation code
to find and free pages.
The whole buffer management scheme is supported by this mechanism and, as
far as the code is concerned, the size of the page and physical paging
mechanisms used by the processor are irrelevant.
Each element of free_area contains information about blocks of
pages. The first element in the array describes single pages, the next blocks of 2 pages, the next
blocks of 4 pages and so on upwards in powers of two.
The list element is used as a queue head and has pointers to the
page data structures in the mem_map array. Free blocks of pages are queued here.
map is a pointer to a bitmap which keeps track of allocated groups of
pages of this size.
Bit N of the bitmap is set if the Nth block of pages is free.
The figure below, shows the free_area structure.
Element 0 has one free page (page frame number 0) and element 2 has 2 free blocks of 4 pages, the
first starting at page frame number 4 and the second at page frame number 56.
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
(nr_free_pages > min_free_pages) 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
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 the Figure above if a block of 2 pages
was requested, the first block of 4 pages (starting at page frame number 4) would
be broken into two 2 page blocks.
The first, starting at page frame number 4 would be returned to the caller as the
allocated pages and the second block, starting at page frame number 6 would be queued
as a free block of 2 pages onto element 1 of the free_area array.
Allocating blocks of pages tends to fragment memory with larger
blocks of free pages being broken down into smaller ones.
The page deallocation code
recombines pages into larger blocks of free pages whenever it can.
In fact the page block size is important as it allows for easy
combination of blocks into larger blocks.
Whenever a block of pages is freed, the adjacent or buddy block of the
same size is checked to see if it is free.
If it is, then it is combined with the newly freed block of pages to form
a new free block of pages for the next size block of pages.
Each time two blocks of pages are recombined into a bigger block of free
pages the page deallocation code attempts to recombine that block into a yet
In this way the blocks of free pages are as large as memory usage will allow.
For example, in the Figure above, if page frame number 1 were to be
freed, then that would be combined with the already free page frame number 0 and
queued onto element 1 of the free_area as a free block of size 2 pages.