Sunday, January 5, 2020

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, fragmentation issues can be debugged. A sample output from the same site is as shown below:
cat /proc/buddyinfo

Different ways to print Linux kernel symbols instead of addresses


%pF versatile_init+0x0/0x110
%pf versatile_init
%pS versatile_init+0x0/0x110
%pSR versatile_init+0x9/0x110
(with __builtin_extract_return_addr() translation)
%ps versatile_init
%pB prev_fn_of_versatile_init+0x88/0x88

Saturday, January 4, 2020

Interesting Math Tutorials - Refreshers

Map of Mathematics