William Lee Irwin III wrote:

On Sat, Aug 21, 2004 at 11:31:21AM +0900, Hiroyuki KAMEZAWA wrote:

quoted

This patch removes bitmap from buddy allocator used in
alloc_pages()/free_pages() in the kernel 2.6.8.1.

<snip>

Complexity maybe. But one serious issue this addresses beyond the needs
of hotplug memory is that the buddy bitmaps are a heavily random-access
data structures not used elsewhere. Consolidating them into the page
structures should improve cache locality and motivate this patch beyond
just the needs of hotplug memory. Furthermore, the patch also reduces
the kernel's overall memory footprint by a small amount.

However, I'm concerned about the effectiveness of this specific
algorithm for coalescing. A more detailed description may help explain
why the effectiveness of coalescing is preserved.

Thanks for your comment, William-san.
I'd like to add detailed description on my patch.
I'm now afraid of the case of memory-hole, I should add page_is_valid(buddy1) before
accessing buddy1.


I wrote a draft of description, does this explain what you want to know?

==
What my patch does is,

1) when expand() is called, there are allocated half of pages and
    not-allocated half of pages.
    The top page of not-allocated half of pages is connected to free_area[order].free_list.
    At the same time, my newly added code record the order into
    page->private of the top page.
    Currently,in 2.6.8.1, this is done by MARK_USED with free_area[order]->bitmap[].

2) when __free_pages_bulk(page,order) is called,the buddy of the page is calclated by
    buddy = page_idx ^ (1 << order) ! this is used in current 2.6.8.1 code.
    For coalessing, we must check the buddy is free and the order of it.
    In 2.6.8.1, those two facts can be checked by
    !__test_and_change_bit(index, area->map)
    only one call.

    In my patch, this check is separated into 2 calls,
    (page_count(page) == 0) && (page_order(page) == order)
    Because expand() records the order of page, when pages are divided,
    __free_page_bulk() can use recorded information.
    In 2.6.8.1, the information "page is free ?" and " order of page? " are both recorded
    in bitmap.

3) why this patch records the page's order by page->private = ~order ?
    Because CPU LOCAL PAGES and some other codes use pages whose page_count(page)== 0,
    on the outside of buddy allocator.
    Mostly, thses pages' page->private is 0.
    This patch has to record order=0 in page->private, so using ~order for avoiding
    to coaless a page which is on the outside of buddy allocator.

   The Algorythm of this patch is not different from using bitmap,
   but "where to record order" is different.
==

Thanks
KAME

-- 
--the clue is these footmarks leading to the door.--
KAMEZAWA Hiroyuki [off-list ref]

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org"> aart@kvack.org </a>