The key to the page allocator (buddy system) algorithm is its primary internal metadata structure. It's called the buddy system freelist and consists of an array of pointers to (the oh-so-common!) doubly linked circular lists. The index of this array of pointers is called the order of the list – it's the power to which to raise 2 to. The array length is from 0 to MAX_ORDER-1. The value of MAX_ORDER is arch-dependent. On the x86 and ARM, it's 11, whereas on a large-ish system such as the Itanium, it's 17. Thus, on the x86 and ARM, the order ranges from 20 to 210 ; that is, from 1 to 1,024. What does that mean? Do read on...
Each doubly linked circular list points to free physical contiguous page frames of size 2order. Thus (assuming a 4 KB page size), we end up with lists of the following:
- 20 = 1 page = 4 KB chunks
- 21 = 2 pages = 8 KB chunks
- 22 = 4 pages = 16 KB chunks
- 23 ...
