Take the 2-minute tour ×
Unix & Linux Stack Exchange is a question and answer site for users of Linux, FreeBSD and other Un*x-like operating systems.. It's 100% free, no registration required.

I have a conceptual doubt in understanding the way Linux Kernel manages Free blocks. Here is what I interpreted through reading so far. The Buddy Allocator implementation is allocation scheme that combines a normal power-of-2 allocation. At times when we need a block of size which is not available, it divides the large block into two. Those two blocks are Buddies, probably hence it is called the Buddy Allocator. Through a source I learnt that an array of free_area_t structs are maintained for each order that points to a linked list of blocks of pages that are free. Which I found in <linux/mm.h>

typedef struct free_area_struct {  
  struct list_head free_list;  
  unsigned long *map;  
} free_area_t;  

The free_list appear to be a linked-list of page blocks? My question is, whether it is a list of Free pages or Used pages?

And map appears to be a bitmap that represents the state of a pair of buddies.

My question is How can it be a single-bit that holds the state bit for a pair of buddies? Because if, I use one of the block in a Buddy-pair to allocats, and the other left free, what would be the state then, and how is that managed to be stored in a single bit? Does it represent the entire block of the size of power-of-two, which can be divided in two parts when we need a block size which is not available, so the allocated half is Buddy of the other half which is free? If this is the case that half is being allocated and half remains free, then what will be status of map ? What if both are free? and what if both are allocated? How can be a binary value representing 3 states of a block?

Edit: After further reading, the first doubt is cleared. Which says: If a free block cannot be found of the requested order, a higher order block is split into two buddies. One is allocated and the other is placed on the free list for the lower order. So it is linked list of free pages.

share|improve this question
Whenever you're concerned about how particular data structures are used, usually you can just look up any old use of said data structure and infer from that. It looks like it runs the bitmask through test_and_change_bit() and if it's a zero then that means the page is allocated. So from my reading it doesn't look like it represents the buddy zone as much as the pages therein, which are either allocated or are free (two states). –  Joel Davis Jun 28 '13 at 17:12
add comment

closed as off-topic by Gilles, jasonwryan, slm, Hauke Laging, Anthon Jun 29 '13 at 3:14

  • This question does not appear to be about Unix or Linux within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.