[RFC] buddy allocator without bitmap [2/4]

[RFC] buddy allocator without bitmap [2/4]

[Hiroyuki KAMEZAWA]

This is 3rd part, for page allocation.

PG_private is used for indicating
"This page is a head of contiguous free pages,whose length is 2^(page->private)"


-- Kame

========================

This patch removes bitmap operation from alloc_pages().

Instead of using MARK_USED() bitmap operation,
this patch records page's order in page struct itself, page->private field.

During locking zone->lock, a returned page's PG_private is cleared and
new heads of contiguous pages of 2^n length are connected to free_area[].
they are all marked with PG_private and their page->private keep their order.

example) 1 page allocation from 8 pages chunk


start ) before calling alloc_pages()
         free_area[3] -> page[0],order=3
         free_area[2] ->
         free_area[1] ->
         free_area[0] ->
	
	8 pages of chunk, starting from page[0] is connected to free_area[3].list
	here, free_area[2],free_area[1],free_area[0] is empty.	

step1 ) before calling expand()
         free_area[3] ->
         free_area[2] ->
         free_area[1] ->
         free_area[0] ->
         return page  -> page[0],order=invalid
	
	Because free_area[2],free_area[1],free_area[0] are empty,
	page[0] in free_area[3] is selected.
	expand() is called to divide page[0-7] into suitable chunks.

step2 ) expand loop 1st
         free_area[3] ->
	free_area[2] -> page[4],order = 2
	free_area[1] ->
	free_area[0] ->
         return page  -> page[0],order=invalid
	
	bottom half of pages[0-7], page[4-7] are free and have an order of 2.
	page[4] is connected to free_list[2].	
	
step3 ) expand loop 2nd
         free_area[3] ->
	free_area[2] -> page[4],order = 2
	free_area[1] -> page[2],order = 1
	free_area[0] ->
         return page  -> page[0],order=invalid
	
	bottom half of pages[0-3], page[2-3] are free and have an order of 1.
	page[2] is connected to free_list[1].
	
step4 ) expand loop 3rd
         free_area[3] ->
	free_area[2] -> page[4],order = 2
	free_area[1] -> page[2],order = 1
	free_area[0] -> page[1],order = 0
         return page  -> page[0],order=invalid
	
	bottom half of pages[0-1], page[1] is free and has an order of 0.
	page[1] is connected to free_list[0].

end )
         chunks of page[0 -7] is divided into
	page[4-7] of order 2
	page[2-3] of order 1
	page[1]   of order 0
         page[0]   is allocated.



---

  linux-2.6.8.1-mm4-kame-kamezawa/mm/page_alloc.c |   16 ++++++----------
  1 files changed, 6 insertions(+), 10 deletions(-)

diff -puN mm/page_alloc.c~eliminate-bitmap-alloc mm/page_alloc.c
--- linux-2.6.8.1-mm4-kame/mm/page_alloc.c~eliminate-bitmap-alloc	2004-08-26 08:43:16.000000000 +0900
+++ linux-2.6.8.1-mm4-kame-kamezawa/mm/page_alloc.c	2004-08-26 11:40:29.461979560 +0900
@@ -288,9 +288,6 @@ void __free_pages_ok(struct page *page,
  	free_pages_bulk(page_zone(page), 1, &list, order);
  }

-#define MARK_USED(index, order, area) \
-	__change_bit((index) >> (1+(order)), (area)->map)
-
  /*
   * The order of subdivision here is critical for the IO subsystem.
   * Please do not alter this order without good reasons and regression
@@ -307,7 +304,7 @@ void __free_pages_ok(struct page *page,
   */
  static inline struct page *
  expand(struct zone *zone, struct page *page,
-	 unsigned long index, int low, int high, struct free_area *area)
+       int low, int high, struct free_area *area)
  {
  	unsigned long size = 1 << high;

@@ -317,7 +314,8 @@ expand(struct zone *zone, struct page *p
  		size >>= 1;
  		BUG_ON(bad_range(zone, &page[size]));
  		list_add(&page[size].lru, &area->free_list);
-		MARK_USED(index + size, high, area);
+		page[size].flags |= (1 << PG_private);
+		page[size].private = high;
  	}
  	return page;
  }
@@ -371,7 +369,6 @@ static struct page *__rmqueue(struct zon
  	struct free_area * area;
  	unsigned int current_order;
  	struct page *page;
-	unsigned int index;

  	for (current_order = order; current_order < MAX_ORDER; ++current_order) {
  		area = zone->free_area + current_order;
@@ -380,11 +377,10 @@ static struct page *__rmqueue(struct zon

  		page = list_entry(area->free_list.next, struct page, lru);
  		list_del(&page->lru);
-		index = page - zone->zone_mem_map;
-		if (current_order != MAX_ORDER-1)
-			MARK_USED(index, current_order, area);
+		/* Atomic operation is needless here */
+		page->flags &= ~(1 << PG_private);
  		zone->free_pages -= 1UL << order;
-		return expand(zone, page, index, order, current_order, area);
+		return expand(zone, page, order, current_order, area);
  	}

  	return NULL;

_

Re: [Lhms-devel] [RFC] buddy allocator without bitmap [2/4]

[Dave Hansen]

On Thu, 2004-08-26 at 05:03, Hiroyuki KAMEZAWA wrote:
> -		MARK_USED(index + size, high, area);
> +		page[size].flags |= (1 << PG_private);
> +		page[size].private = high;
>   	}
>   	return page;
>   }
...
> +		/* Atomic operation is needless here */
> +		page->flags &= ~(1 << PG_private);

See linux/page_flags.h:

#define SetPagePrivate(page)    set_bit(PG_private, &(page)->flags)
#define ClearPagePrivate(page)  clear_bit(PG_private, &(page)->flags)
#define PagePrivate(page)       test_bit(PG_private, &(page)->flags)

-- Dave

Re: [Lhms-devel] [RFC] buddy allocator without bitmap [2/4]

[Hiroyuki KAMEZAWA]

Hi

I understand using these macros cleans up codes as I used them in my previous
version.

In the previous version, I used SetPagePrivate()/ClearPagePrivate()/PagePrivate().
But these are "atomic" operation and looks very slow.
This is why I doesn't used these macros in this version.

My previous version, which used set_bit/test_bit/clear_bit, shows very bad performance
on my test, and I replaced it.

If I made a mistake on measuring the performance and set_bit/test_bit/clear_bit
is faster than what I think, I'd like to replace them.

-- Kame

Dave Hansen wrote:
> On Thu, 2004-08-26 at 05:03, Hiroyuki KAMEZAWA wrote:
> 
>>-		MARK_USED(index + size, high, area);
>>+		page[size].flags |= (1 << PG_private);
>>+		page[size].private = high;
>>  	}
>>  	return page;
>>  }
> 
> ...
> 
>>+		/* Atomic operation is needless here */
>>+		page->flags &= ~(1 << PG_private);
> 
> 
> See linux/page_flags.h:
> 
> #define SetPagePrivate(page)    set_bit(PG_private, &(page)->flags)
> #define ClearPagePrivate(page)  clear_bit(PG_private, &(page)->flags)
> #define PagePrivate(page)       test_bit(PG_private, &(page)->flags)
> 
> -- Dave
> 
> 


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

Re: [Lhms-devel] [RFC] buddy allocator without bitmap [2/4]

[Dave Hansen]

On Thu, 2004-08-26 at 16:05, Hiroyuki KAMEZAWA wrote:
> I understand using these macros cleans up codes as I used them in my previous
> version.
> 
> In the previous version, I used SetPagePrivate()/ClearPagePrivate()/PagePrivate().
> But these are "atomic" operation and looks very slow.
> This is why I doesn't used these macros in this version.
> 
> My previous version, which used set_bit/test_bit/clear_bit, shows very bad performance
> on my test, and I replaced it.
> 
> If I made a mistake on measuring the performance and set_bit/test_bit/clear_bit
> is faster than what I think, I'd like to replace them.

Sorry, I misread your comment:

/* Atomic operation is needless here */

I read "needless" as "needed".  Would it make any more sense to you to
say "already have lock, don't need atomic ops", instead?

-- Dave

Re: [Lhms-devel] [RFC] buddy allocator without bitmap [2/4]

[Hiroyuki KAMEZAWA]

Dave Hansen wrote:

> On Thu, 2004-08-26 at 16:05, Hiroyuki KAMEZAWA wrote:
> 
>>I understand using these macros cleans up codes as I used them in my previous
>>version.
>>
>>In the previous version, I used SetPagePrivate()/ClearPagePrivate()/PagePrivate().
>>But these are "atomic" operation and looks very slow.
>>This is why I doesn't used these macros in this version.
>>
>>My previous version, which used set_bit/test_bit/clear_bit, shows very bad performance
>>on my test, and I replaced it.
>>
>>If I made a mistake on measuring the performance and set_bit/test_bit/clear_bit
>>is faster than what I think, I'd like to replace them.
> 
> 
> Sorry, I misread your comment:
> 
> /* Atomic operation is needless here */
> 
> I read "needless" as "needed".  Would it make any more sense to you to
> say "already have lock, don't need atomic ops", instead?
> 
Thanks. I'm not so good at writing good comment, as you know :).
I'll rewrite it.


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

Re: [Lhms-devel] [RFC] buddy allocator without bitmap [2/4]

[Andrew Morton]

Hiroyuki KAMEZAWA <kamezawa.hiroyu@jp.fujitsu.com> wrote:
>
> In the previous version, I used SetPagePrivate()/ClearPagePrivate()/PagePrivate().
> But these are "atomic" operation and looks very slow.
> This is why I doesn't used these macros in this version.
> 
> My previous version, which used set_bit/test_bit/clear_bit, shows very bad performance
> on my test, and I replaced it.

That's surprising.  But if you do intend to use non-atomic bitops then
please add __SetPagePrivate() and __ClearPagePrivate()

Re: [Lhms-devel] [RFC] buddy allocator without bitmap [2/4]

[Hiroyuki KAMEZAWA]

Okay, I'll do more test and if I find atomic ops are slow,
I'll add __XXXPagePrivate() macros.

ps. I usually test codes on Xeon 1.8G x 2 server.

-- Kame

Andrew Morton wrote:
> Hiroyuki KAMEZAWA <kamezawa.hiroyu@jp.fujitsu.com> wrote:
> 
>>In the previous version, I used SetPagePrivate()/ClearPagePrivate()/PagePrivate().
>>But these are "atomic" operation and looks very slow.
>>This is why I doesn't used these macros in this version.
>>
>>My previous version, which used set_bit/test_bit/clear_bit, shows very bad performance
>>on my test, and I replaced it.
> 
> 
> That's surprising.  But if you do intend to use non-atomic bitops then
> please add __SetPagePrivate() and __ClearPagePrivate()

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