Linux: Why is the buddy system needed? - To prevent fragmentation

The buddy system is a mechanism for page management in Linux. It is needed to make sure that the free memory does not get fragmented and unusable. For an overview of the buddy system including a simple example of how it works, see this page [2]. From the same page, "In comparison to other simpler techniques such as dynamic allocation, the buddy memory system has little external fragmentation, and allows for compaction of memory with little overhead. The buddy method of freeing memory is fast, with the maximal number of compactions required equal to log2(highest order). Typically the buddy memory allocation system is implemented with the use of a binary tree to represent used or unused split memory blocks. The "buddy" of each block can be found with an exclusive OR of the block's address and the block's size."

An alternative to the buddy system would be to use the memory management unit (MMU) support to rewire or re-arrange blobs of free pages together to construct larger contiguous pages. However, this will not work for DMA systems which bypass the MMU. Also, modifying the virtual address on a continual basis would make the paging process slow.

Debugging on the buddy system can be done by printing the current stats. This is supported under the /proc/buddyinfo file. As described in the guide from centos.org, fragmentation issues can be debugged. A sample output from the same site is as shown below:

cat /proc/buddyinfo

Node 0, zone      DMA     90      6      2      1      1      ... 
Node 0, zone   Normal   1650    310      5      0      0      ... 
Node 0, zone  HighMem      2      0      0      1      1      ...

Explanation from the website(1):

Each column represents the number of pages of a certain order (a certain size) that are available at any given time. For example, for zone DMA (direct memory access), there are 90 of 2^(0*PAGE_SIZE) chunks of memory. Similarly, there are 6 of 2^(1*PAGE_SIZE) chunks, and 2 of 2^(2*PAGE_SIZE) chunks of memory available.

The DMA row references the first 16 MB on a system, the HighMem row references all memory greater than 4 GB on a system, and the Normal row references all memory in between.

 Hope this was useful.

Reference:
(1) http://www.centos.org/docs/5/html/5.2/Deployment_Guide/s2-proc-buddyinfo.html
(2) Wikipeia Buddy system https://en.wikipedia.org/wiki/Buddy_memory_allocation