Buddy Memory Allocator

#os/linux/memory

Linux kernel uses the buddy algorithm[1][2][3][4] as a page allocator, which is simple and efficient. The buddy algorithm is organize physical memory into blocks of various sizes, all of which are powers of two (order 1 means 2^1). These blocks can be split into two "buddies" or combined with a buddy to form a large block.

how buddy allocator works ? For example:

  1. when kernel needs a 16k sized memory, but there's no available 16k chunks
  2. the allocator will go to 32k size chunk
  3. 32k will be split into 16k + 16k. one 16k will be used and another 16k will be put in 16k sized chuck
A page size in linux is 4KB

The benefit from buddy allocator is that it will keep the contiguous, reduce the fragmentation and fast allocation and deallocation of memory blocks. However, it can lead to be inefficient for allocating small amounts of memory

We can see available page numbers in each order (e.g. 0, 1, 2, 3, ...., 11) using :

cat /proc/buddyinfo

chester@chester-desktop:~$ cat /proc/buddyinfo
Node 0, zone      DMA      0      0      0      0      0      0      0      0      0      1      3
Node 0, zone    DMA32   6407   5061   3363   2415   1379    510    142     26      6      3      5
Node 0, zone   Normal  85846  51111  13170   3747    988    324    138    106     42    130    236
What we learn from the buddyinfo ?

The presence of larger blocks suggests lower memory fragmentation, as it indicates there are contiguous pages available for allocation. If the system run low on larger blocks, it may indicate memory fragmentation or high memory usage, which could lead to performance issues.

  1. https://hackmd.io/@RinHizakura/rJTl9K5tv ↩︎

  2. https://blog.csdn.net/lickylin/article/details/50726847 ↩︎

  3. https://ithelp.ithome.com.tw/articles/10101823?sc=rss.iron ↩︎

  4. https://www.kernel.org/doc/gorman/html/understand/understand009.html ↩︎