Re: [RFC] free_area[] bitmap elimination [0/3]

Hiroyuki KAMEZAWA
2004-08-21T04:55:15Z

William Lee Irwin III wrote:

> On Sat, Aug 21, 2004 at 11:31:21AM +0900, Hiroyuki KAMEZAWA wrote:
>
>>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 <kamezawa.hiroyu@jp.fujitsu.com>