lkml.org 
[lkml]   [2002]   [Jun]   [2]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    Date
    From
    Subjectcomplete 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/
    \
     
     \ /
      Last update: 2005-03-22 13:26    [W:2.277 / U:0.132 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site