complete comment regarding inner workings of buddy system

[William Lee Irwin III <wli@holomorphy.com>]

The comment about buddy system allocators has a TODO item for
explanation of buddy system allocators in general. The following patch
removes the TODO item in favor of an actual explanation.

Against 2.5.19.


Cheers,
Bill



===== mm/page_alloc.c 1.71 vs edited =====
--- 1.71/mm/page_alloc.c	Sun Jun  2 15:41:24 2002
+++ edited/mm/page_alloc.c	Sun Jun  2 15:45:27 2002
@@ -69,10 +69,22 @@
  * at the bottom level available, and propagating the changes upward
  * as necessary, plus some accounting needed to play nicely with other
  * parts of the VM system.
- *
- * TODO: give references to descriptions of buddy system allocators,
- * describe precisely the silly trick buddy allocators use to avoid
- * storing an extra bit, utilizing entry point information.
+ * More precisely, a buddy system for a given level maintains one bit
+ * for each pair of blocks, which is the xor of the "virtual bits"
+ * describing whether or not the individual blocks are available.
+ * While freeing, the block of pages being examined is known to be
+ * already allocated, so its "virtual bit" is 0 and its buddy's bit
+ * may be recovered by xor'ing with 0 (or just checking it). While
+ * allocating, the block of pages to be handed back is chosen from
+ * lists of free pages, and so the page's "virtual bit" is 1 and its
+ * buddy's bit may be recovered by xor'ing with 1 (or just inverting it).
+ * These virtual bits, when recovered, are used only to determine when
+ * to split or coalesce blocks of free pages and do the corresponding
+ * list manipulations. That is, if both were free and a smaller block
+ * is allocated from a free region then the remainder of the region
+ * must be split into blocks, or if a free block's buddy is freed then
+ * this triggers coalescing of blocks on the queues into a block of
+ * larger size.
  *
  * -- wli
  */