Linux Kernel Architecture

Chapter3:MemoryManagement

The routine tries to free a page group of orderorder. Because it is possible not only that the current group
can be merged with its direct buddy, but also that higher-order buddies can be merged, the kernel needs
to find the maximal allocation order for which this is possible.

The action of the code is best understood by means of an example. Imagine that an order 0 allocation, that
is, a single page, is freed, and let this page have the page index 10. The required calculations are found in
Table 3-8, and Figure 3-36 visualizes the process step-by-step. We assume that page 10 is the last missing
link that allows for coalescing two buddies of order 3 to form a new range of order 4.

order 4

0781015

pi = 0

ci = 0

order 3 pi = 8 buddy = 0

order 2

order 1

order

empty page used page returned page

0

ci = 8

pi = 8 buddy = 12

ci = 8

pi = 10 buddy = 8

pi = 10

ci = 10

buddy = 11

pi = 10

Figure 3-36: Returning a page into the buddy system can cause

higher-order allocations to be coalesced. pi stands forpage_index,

while ci denotescombined_index.

The first loop pass finds page number 11 as the buddy for page 10. Since not the page number of the
buddy, but a pointer to the correspondingpageinstance is required, the differencebuddy_idx - page_idx
is of relevance: It denotes the difference between the current page and its buddy, and adding it to thepage
pointer will deliver a pointer to thepageinstance of the buddy.

This pointer is required bypage_is_buddyto check if the buddy is free. As per Figure 3-36, this is
luckily the case, so the buddies can be combined. This requires that page number 11 is temporarily
removed from the buddy system because it will be reintegrated as part of a larger block later.
Thepageinstance is taken off the free list, andrmv_page_orderclears thePG_buddyflag and the
private data.

Computing the index of the combined group in__find_combined_indexdelivers 10, because the
2-page buddy block starts at this page number. At the end of each loop step, thepagepointer
is set to point to the first page in the new buddy group, but in this case, nothing needs to be
modified.

The next loop pass works similarly, but now fororder=1; that is, the kernel tries to combine two 2-
page buddies into a 4-page group. The buddy of the [10, 11] page group starts at page number 8, so the
differencebuddy_index - page_indexis negative. Naturally, there’s nothing preventing a buddy from
being on the left-hand side of the current page group. The combined index of the merged group is 8, so
thepagepointer has to be updated accordingly afterpage_is_buddyhas ensured that all pages of the
new buddy (i.e., pages 8 and 9) are contained in the buddy system.