Linux: buddy system free memory

Question

Could anyone explain this code?

page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);

page_to_pfn() have already return the page_idx, so what does '&' use for? Or page_to_pfn() return something else?

Answer 1

You need to know that x & ((1 << n) - 1) is a trick meaning x % ((int) pow(2, n)). Often it's faster (but it's better to leave these kind of optimizations to the compiler).

So in this case what this does it does a modulo by pow(2, MAX_ORDER). This causes a wrap-around; if page_idx is larger than pow(2, MAX_ORDER) it will go back to 0. Here is equivalent, but more readable code:

const int MAX_ORDER_N = (int) pow(2, MAX_ORDER);

page_idx = page_to_pfn(page);

/* wraparound */
while (page_idx > MAX_ORDER_N) {
    page_idx -= MAX_ORDER_N;
}

Answer 2

It's a bit mask that ensures that page_idx does not exceed a certain value (2^MAX_ORDER).

# define MAX_ORDER (8)

(1 << MAX_ORDER) /* 100000000 */
- 1 /* flip bits, same as ~(…) due to two-complement: 11111111 */

So you only have the eight least significant bits left

  1010010101001
& 0000011111111
= 0000010101001

Answer 3

chekck this function will be clear:

static inline struct page * 
__page_find_buddy(struct page *page, unsigned long page_idx, unsigned int order)
    {
            unsigned long buddy_idx = page_idx ^ (1 << order);
    
            return page + (buddy_idx - page_idx);
    }

it just limits page_idx into a range of 8MB, maybe because the maximum block size is 4MB (1024 pages), it can not be merged again, only 2MB blocks can merge into 4MB, and the buddy block can be before or after the page, so the whole range is [page_idx - 2MB, page_idx + 2MB] ??

its absolute size is not important, but offset (buddy_idx - page_idx) is important, add page to get the real buddy address.