Messages in this thread Patch in this message | | | Date | Sun, 2 Jun 2002 15:48:48 -0700 | From | William Lee Irwin III <> | Subject | complete comment regarding inner workings of buddy system |
| |
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 */ - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |