Библиотека сайта rus-linux.net
The book is available and called simply "Understanding The Linux Virtual Memory Manager". There is a lot of additional material in the book that is not available here, including details on later 2.4 kernels, introductions to 2.6, a whole new chapter on the shared memory filesystem, coverage of TLB management, a lot more code commentary, countless other additions and clarifications and a CD with lots of cool stuff on it. This material (although now dated and lacking in comparison to the book) will remain available although I obviously encourge you to buy the book from your favourite book store :-) . As the book is under the Bruce Perens Open Book Series, it will be available 90 days after appearing on the book shelves which means it is not available right now. When it is available, it will be downloadable from http://www.phptr.com/perens so check there for more information.
To be fully clear, this webpage is not the actual book.
Next: 7.4 Get Free Page Up: 7. Physical Page Allocation Previous: 7.2 Allocating Pages   Contents   Index
The API for the freeing of pages is a lot simpler and exists to help remember the order of the block to free. One disadvantage of a buddy allocator is that the caller has to remember the size of the original allocation. The API for freeing is listed in Table 7.2.
The principal function for freeing pages is
and it should not be called directly. Instead the function
__free_pages() is provided which performs simple checks first as
indicated in Figure 7.4.
When a buddy is freed, Linux tries to coalesce the buddies together immediately if possible. This is not optimal as the worst case scenario will have many coalitions followed by the immediate splitting of the same blocks [#!vahalia96!#] although it is worth noting later development kernels have implemented a lazy buddy system [#!barkley89!#] which delays the coalescing of buddies until it is necessary.
To detect if the buddies can be merged or not, Linux checks
the bit corresponding to the affected pair of buddies in
map. As one buddy has just been freed by this
function, it is obviously known that at least one buddy is free. If the bit
in the map is 0 after toggling, we know that the other buddy must also be
free because if the bit is 0, it means both buddies are either both free or
both allocated. If both are free, they may be merged.
Calculating the address is a well known concept [#!knuth68!#]. As the
allocations are always in blocks of size 2, the address of the block,
or at least its offset within
zone_mem_map will also be a
power of 2. The end result is that there will always be at least k
number of zeros to the right of the address. To get the address of the buddy,
the kth bit from the right is examined. If it is 0, then the buddy
will have this bit flipped. To get this bit, Linux creates a
which is calculated as
The mask we are interested in is
Linux takes a shortcut in calculating this by noting that
Once the buddy is merged, it is removed for the free list and the newly coalesced pair moves to the next higher order to see if it may also be merged.
Next: 7.4 Get Free Page Up: 7. Physical Page Allocation Previous: 7.2 Allocating Pages   Contents   Index Mel 2004-02-15