Thanks for many comments on previous RFC.

This is an updated version of free_area[] bitmap elimination patch.
Many advices are reflected.
I tested this on Xeon x 2 server and Itanium2 x 2 server.

This removes bitmaps from the buddy allocator.
Instead of using bitmap, this patch records a free page's order to
page struct itself.

Most important point I changed in this version is that tricky usage of
page->private is removed.Instead of doing so,I use PG_private bit now.

If a page is page_count(page)== 0 && PagePrivate(page), it is a head of
contiguous free page on the buddy allocator and its order is page->private.

Propriety of using PG_private is guaranteed by these facts:
(1) Before calling free_pages(), PG_private must be cleared.(see free_pages_check())
(2) Swap calls, which directly call put_page_testzero(), does not uses PG_private bit.
    Because they calls free_hot_cold_page() directly, PG_private bit is not set when
    page_count(page) becomes zero.
(3) All operation of set and clear PG_private bit of a free page for buddy allocator
    is done only while zone->lock() is acquired.

I added zone->aligned_order member in zone struct for avoiding range check to some extent.
This member guarantees a page has a buddy in an order <= zone->aligned_order and
we can skip some checks.

In this version, a problem of pfn_valid() for ia64 is not fixed.
I think I'll need some different kind of patch to fix this.

I added detailed description but complexity is unchaned.

How to patch :
1) patch -p1 < eliminate-bitmap-includes.patch
2) patch -p1 < eliminate-bitmap-init.patch
3) patch -p1 < eliminate-bitmap-alloc.patch
4) patch -p1 < eliminate-bitmap-free.patch


Thanks
--Kame

-- 
--the clue is these footmarks leading to the door.--
KAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com>