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

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

[Hiroyuki KAMEZAWA]

[-- Attachment #1: Type: text/plain, Size: 1291 bytes --]

Hi

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

Currently, Linux's page allocator uses bitmaps to record an order
of a free page.
This patch removes bitmap from buddy allocator, and uses
page->private field to record an order of a page.

My purpose is to reduce complexity of buddy allocator, when we want to
hotplug memory. For memory hotplug, we have to resize memory management
structures. Major two of them are mem_map and bitmap.If this patch removes
bitmap from buddy allocator, resizeing bitmap will be needless.

I tested this patch on my small PC box(Celeron900MHz,256MB memory)
and a server machine(Xeon x 2, 4GB memory).

Patch is divided into 4 parts
p01 .....  for include files
p02 .....  for initialization of zone
p03 .....  for alloc_pages()
p04 .....  for free_pages()

Note:
This patch records an order of a page in page->private field, in
page->private = ~order manner.
This is because there are pages which is not in buddy allocator and is its
page_count(page)==0.

I'm not convinced that page->private is not used while page_count(page) == 0.
If used, this patch will have a problem.

Thanks
KAME

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


[-- Attachment #2: eliminate-bitmap-p01.patch --]
[-- Type: text/x-patch, Size: 1991 bytes --]


Eliminate free_area_t bitmap patches.
p01 is for include files.


---

 linux-2.6.8.1-kame-kamezawa/include/linux/mm.h     |   16 ++++++++++++++--
 linux-2.6.8.1-kame-kamezawa/include/linux/mmzone.h |    1 -
 2 files changed, 14 insertions(+), 3 deletions(-)

diff -puN include/linux/mmzone.h~eliminate-bitmap-p01 include/linux/mmzone.h
--- linux-2.6.8.1-kame/include/linux/mmzone.h~eliminate-bitmap-p01	2004-08-19 13:16:05.000000000 +0900
+++ linux-2.6.8.1-kame-kamezawa/include/linux/mmzone.h	2004-08-19 13:34:34.000000000 +0900
@@ -34,7 +34,6 @@
 
 struct free_area {
 	struct list_head	free_list;
-	unsigned long		*map;
 };
 
 struct pglist_data;
diff -puN include/linux/mm.h~eliminate-bitmap-p01 include/linux/mm.h
--- linux-2.6.8.1-kame/include/linux/mm.h~eliminate-bitmap-p01	2004-08-19 13:22:24.000000000 +0900
+++ linux-2.6.8.1-kame-kamezawa/include/linux/mm.h	2004-08-21 08:52:59.137598728 +0900
@@ -203,8 +203,9 @@ struct page {
 	unsigned long private;		/* Mapping-private opaque data:
 					 * usually used for buffer_heads
 					 * if PagePrivate set; used for
-					 * swp_entry_t if PageSwapCache
-					 */
+					 * swp_entry_t if PageSwapCache.
+					 * when page is free, this field
+					 * keeps order of page. */
 	struct address_space *mapping;	/* If PG_anon clear, points to
 					 * inode address_space, or NULL.
 					 * If page mapped as anonymous
@@ -313,9 +314,20 @@ static inline void put_page(struct page 
 		__page_cache_release(page);
 }
 
+
+
+
 #endif		/* CONFIG_HUGETLB_PAGE */
 
 /*
+ *	indicates page's order in freelist
+ *      order is recorded in inveterd manner.
+ */
+#define page_order(page)	(~((page)->private))
+#define set_page_order(page,order)	((page)->private = ~order)
+#define invalidate_page_order(page) ((page)->private = 0)
+
+/*
  * Multiple processes may "see" the same page. E.g. for untouched
  * mappings of /dev/null, all processes see the same page full of
  * zeroes, and text pages of executables and shared libraries have

_

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

[William Lee Irwin III]

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.
> Currently, Linux's page allocator uses bitmaps to record an order
> of a free page.
> This patch removes bitmap from buddy allocator, and uses
> page->private field to record an order of a page.
> My purpose is to reduce complexity of buddy allocator, when we want to
> hotplug memory. For memory hotplug, we have to resize memory management
> structures. Major two of them are mem_map and bitmap.If this patch removes
> bitmap from buddy allocator, resizeing bitmap will be needless.
> I tested this patch on my small PC box(Celeron900MHz,256MB memory)
> and a server machine(Xeon x 2, 4GB memory).

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.


-- wli
--
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>

Re: [Lhms-devel] Re: [RFC] free_area[] bitmap elimination [0/3]

[Hirokazu Takahashi]

Hello,

I also impressed by your patch.

In my understanding, the patch assumes that size of mem_map[] in each
zone must be multiple of 2^MAX_ORDER, right?
But it doesn't seem it's a big problem, as we can just allocate extra
mem_map[] to round up if it isn't.

> 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.
> > Currently, Linux's page allocator uses bitmaps to record an order
> > of a free page.
> > This patch removes bitmap from buddy allocator, and uses
> > page->private field to record an order of a page.
> > My purpose is to reduce complexity of buddy allocator, when we want to
> > hotplug memory. For memory hotplug, we have to resize memory management
> > structures. Major two of them are mem_map and bitmap.If this patch removes
> > bitmap from buddy allocator, resizeing bitmap will be needless.
> > I tested this patch on my small PC box(Celeron900MHz,256MB memory)
> > and a server machine(Xeon x 2, 4GB memory).
> 
> 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.

Agreed.

> 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.

--
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>

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

[Hiroyuki KAMEZAWA]

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>

--
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>

Re: [Lhms-devel] Re: [RFC] free_area[] bitmap elimination [0/3]

[Hirokazu Takahashi]

Hi,

> 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_ivs_valid(buddy1) before
> accessing buddy1.

What do you think about my idea I just posted.

> In my understanding, the patch assumes that size of mem_map[] in each
> zone must be multiple of 2^MAX_ORDER, right?
> But it doesn't seem it's a big problem, as we can just allocate extra
> mem_map[] to round up if it isn't.

I think this may help the buddy allocator to work withtout adding
page_ivs_valid(buddy1).


Thank you,
Hirokazu Takahashi.
--
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>

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

[William Lee Irwin III]

William Lee Irwin III wrote:
>> 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.

On Sat, Aug 21, 2004 at 02:00:21PM +0900, Hiroyuki KAMEZAWA wrote:
> 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?

This description is enough for me to understand it fully, thank you much.


-- wli
--
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>

Re: [Lhms-devel] Re: [RFC] free_area[] bitmap elimination [0/3]

[William Lee Irwin III]

On Sat, Aug 21, 2004 at 01:56:24PM +0900, Hirokazu Takahashi wrote:
> I also impressed by your patch.
> In my understanding, the patch assumes that size of mem_map[] in each
> zone must be multiple of 2^MAX_ORDER, right?
> But it doesn't seem it's a big problem, as we can just allocate extra
> mem_map[] to round up if it isn't.

In __free_pages_bulk() changing BUG_ON(bad_range(zone, buddy1)) to
if (bad_range(zone, buddy1)) break; should fix this. The start of
the zone must be aligned to MAX_ORDER so buddy2 doesn't need checks.
It may be worthwhile to make a distinction the bounds checks and the
zone check and to BUG_ON() the zone check in isolation and not repeat
the bounds check for the validity check.


-- wli
--
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>

Re: [Lhms-devel] Re: [RFC] free_area[] bitmap elimination [0/3]

[Hiroyuki KAMEZAWA]

Hi,
Hirokazu Takahashi wrote:

> Hi,
> 
> 
>>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>
>>In my understanding, the patch assumes that size of mem_map[] in each
>>zone must be multiple of 2^MAX_ORDER, right?
>>But it doesn't seem it's a big problem, as we can just allocate extra
>>mem_map[] to round up if it isn't.
> 
> 
> I think this may help the buddy allocator to work withtout adding
> page_ivs_valid(buddy1).
> 
> 
As you say, I expects the size of zone is multiple of MAX_ORDER.
But IA64 kernel's MAX_ORDER is 4 Giga bytes :(
A Tiger4, an IA64 machine, I use has physical  memory map like this:

0-2G  :
4-8G  :
10-12G:

contiguous mem_map is smaller than MAX_ORDER.

So I think page_is_valid(buddy1) is needed only for a few pages,
which is top of big buddy, in this case.

Hmm.... :(

Thank you,
KAME

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

--
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>

Re: [Lhms-devel] Re: [RFC] free_area[] bitmap elimination [0/3]

[William Lee Irwin III]

William Lee Irwin III wrote:
>> In __free_pages_bulk() changing BUG_ON(bad_range(zone, buddy1)) to
>> if (bad_range(zone, buddy1)) break; should fix this. The start of
>> the zone must be aligned to MAX_ORDER so buddy2 doesn't need checks.
>> It may be worthwhile to make a distinction the bounds checks and the
>> zone check and to BUG_ON() the zone check in isolation and not repeat
>> the bounds check for the validity check.

On Sat, Aug 21, 2004 at 02:37:56PM +0900, Hiroyuki KAMEZAWA wrote:
> Okay, I understand several BUG_ON() are needless.
> I'll be more carefull to recognize what is checked.

It's not that it's needless, it's that beforehand the bitmap rounding
up to an even number ensured the __test_and_change_bit() check would
prevent the bounds check from ever failing, but after the bitmap is
eliminated, the bounds check is needed to see if we're even examining
a valid page structure for whether the page can be merged.


-- wli
--
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>

Re: [Lhms-devel] Re: [RFC] free_area[] bitmap elimination [0/3]

[Hiroyuki KAMEZAWA]

William Lee Irwin III wrote:

> On Sat, Aug 21, 2004 at 01:56:24PM +0900, Hirokazu Takahashi wrote:
> 
>>I also impressed by your patch.
>>In my understanding, the patch assumes that size of mem_map[] in each
>>zone must be multiple of 2^MAX_ORDER, right?
>>But it doesn't seem it's a big problem, as we can just allocate extra
>>mem_map[] to round up if it isn't.
> 
> 
> In __free_pages_bulk() changing BUG_ON(bad_range(zone, buddy1)) to
> if (bad_range(zone, buddy1)) break; should fix this. The start of
> the zone must be aligned to MAX_ORDER so buddy2 doesn't need checks.
> It may be worthwhile to make a distinction the bounds checks and the
> zone check and to BUG_ON() the zone check in isolation and not repeat
> the bounds check for the validity check.
> 
> 
Okay, I understand several BUG_ON() are needless.
I'll be more carefull to recognize what is checked.

Thank you.
KAME

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

--
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>

Re: [Lhms-devel] Re: [RFC] free_area[] bitmap elimination [0/3]

[Hiroyuki KAMEZAWA]

Hi,

William Lee Irwin III wrote:

> William Lee Irwin III wrote:
> 
>>>In __free_pages_bulk() changing BUG_ON(bad_range(zone, buddy1)) to
>>>if (bad_range(zone, buddy1)) break; should fix this. The start of
>>>the zone must be aligned to MAX_ORDER so buddy2 doesn't need checks.
>>>It may be worthwhile to make a distinction the bounds checks and the
>>>zone check and to BUG_ON() the zone check in isolation and not repeat
>>>the bounds check for the validity check.
> 
> 
> On Sat, Aug 21, 2004 at 02:37:56PM +0900, Hiroyuki KAMEZAWA wrote:
> 
>>Okay, I understand several BUG_ON() are needless.
>>I'll be more carefull to recognize what is checked.
> 
> 
> It's not that it's needless, it's that beforehand the bitmap rounding
> up to an even number ensured the __test_and_change_bit() check would
> prevent the bounds check from ever failing, but after the bitmap is
> eliminated, the bounds check is needed to see if we're even examining
> a valid page structure for whether the page can be merged.
> 
> 
Oh, I said these 2 lines are needless ;) ,sorry for my vagueness.
     buddy2 = base + page_idx;
(*) BUG_ON(bad_range(zone, buddy1));
(*) BUG_ON(bad_range(zone, buddy2));

I understand a test before accessing "buddy1" is necessary.

But as I mentioned in other mail, I'm afraid of memory hole in zone.
This cannot be detected by simple range check.
Is this special case of IA64 ? (I don't know other archs than i386 and IA64)

I think
+ if (!pfn_valid(buddy1))
+     break;
will work enough if pfn_valid() works correctly fot zone with hole.

If ZONE is not MAX_ORDER aligned,
if (bad_range(zone,buddy1))
     break;
will be needed too.


-- KAME

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

--
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>

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

[Nigel Cunningham]

Hi.

On Sat, 2004-08-21 at 12:31, Hiroyuki KAMEZAWA wrote:
> Hi
> 
> This patch removes bitmap from buddy allocator used in
> alloc_pages()/free_pages() in the kernel 2.6.8.1.

For what it's worth, I like the concept. Suspend 2 currently builds a
bitmap of free pages precisely because iterating through these lists is
slow. Getting the data directly from page structs will allow me to
remove some code.

Nigel
-- 
Nigel Cunningham
Christian Reformed Church of Tuggeranong
PO Box 1004, Tuggeranong, ACT 2901

Many today claim to be tolerant. But true tolerance can cope with others
being intolerant.

--
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>

Re: [Lhms-devel] Re: [RFC] free_area[] bitmap elimination [0/3]

[William Lee Irwin III]

On Sat, Aug 21, 2004 at 03:10:54PM +0900, Hiroyuki KAMEZAWA wrote:
> Oh, I said these 2 lines are needless ;) ,sorry for my vagueness.
>     buddy2 = base + page_idx;
> (*) BUG_ON(bad_range(zone, buddy1));
> (*) BUG_ON(bad_range(zone, buddy2));
> I understand a test before accessing "buddy1" is necessary.

Well, the only reason a test before accessing buddy2 isn't necessary
is because of the assumption that the start of a zone is MAX_ORDER
aligned.


On Sat, Aug 21, 2004 at 03:10:54PM +0900, Hiroyuki KAMEZAWA wrote:
> But as I mentioned in other mail, I'm afraid of memory hole in zone.
> This cannot be detected by simple range check.
> Is this special case of IA64 ? (I don't know other archs than i386 and IA64)
> I think
> + if (!pfn_valid(buddy1))
> +     break;
> will work enough if pfn_valid() works correctly fot zone with hole.

On most architectures the pfn_valid() will do something much like
bad_range() but less efficiently. My understanding is that MAP_NR_DENSE()
and analogues aren't supported in 2.6, so to avoid the overhead for
machines not needing it some kind of conditional check would be good. My
current understanding is that the mem_map setup in arch/ia64 now will not
make these kinds of bounds checks fail, but I'm willing to be corrected.
ia64_pfn_valid() is highly unusual and probably extremely inefficient.


On Sat, Aug 21, 2004 at 03:10:54PM +0900, Hiroyuki KAMEZAWA wrote:
> If ZONE is not MAX_ORDER aligned,
> if (bad_range(zone,buddy1))
>     break;
> will be needed too.

We've usually assumed the start of the zone MAX_ORDER -aligned, but
adding if (bad_range(zone, buddy2)) break; or similar would relax that
restriction, assuming that above you meant buddy2.


-- wli
--
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>

Re: [Lhms-devel] [RFC] free_area[] bitmap elimination [0/3]

[Dave Hansen]

On Fri, 2004-08-20 at 19:31, Hiroyuki KAMEZAWA wrote: 
> This patch removes bitmap from buddy allocator used in
> alloc_pages()/free_pages() in the kernel 2.6.8.1.

Looks very interesting.  The most mysterious thing about it that I can
think of right now would be its cache behavior.  Since struct pages are
at least 1/2 a cacheline on most architectures, you're going to dirty
quite a few more cachelines than if you were accessing a quick bitmap. 
However, if the page was recently accessed you might get *better*
cacheline performance because the struct page itself may have been
hotter than its bitmap.  

The use of page_count()==0 is a little worrisome.  There's almost
certainly some race conditions where a page can be mistaken for free
while it's page_count()==0, but before it's reached free_pages_bulk().

BTW, even if page_count()==0 isn't a valid check like you fear, you
could always steal a bit in the page->flags.  Check out 
free_pages_check() in mm/page_alloc.c for a nice summary of what state
pages have to be in before they're freed.  

I'll try and give these patches a run on a NUMA-Q today.  Those machines
are very cache-sensitive and should magnify any positive or negative
effects.  

-- Dave

--
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>

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

[Dave Hansen]

On Mon, 2004-08-23 at 07:36, Dave Hansen wrote:
> I'll try and give these patches a run on a NUMA-Q today.  Those machines
> are very cache-sensitive and should magnify any positive or negative
> effects.  

DISCLAIMER: SPEC(tm) and the benchmark name SDET(tm) are registered 
trademarks of the Standard Performance Evaluation Corporation. This 
benchmarking was performed for research purposes only, and the run
results are non-compliant and not-comparable with any published results.

Scripts: 32     
Iterations: 40
                      2.6.8.1- | 2.6.8.1-
                      vanilla  | nofreemap
                    -----------+-----------
Average Throughput:   18836.68 |  18839.37
Standard Deviation:    1538.89 |   1791.29

No statistically different results.  Very cool.

-- Dave

--
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>

Re: [Lhms-devel] [RFC] free_area[] bitmap elimination [0/3]

[Dave Hansen]

A few tiny, cosmetic comments on the patch itself:

>  }
>  
> +
> +
> +
>  #endif         /* CONFIG_HUGETLB_PAGE */
>  

Be careful about adding whitespace like that

>  /*
> + *     indicates page's order in freelist
> + *      order is recorded in inveterd manner.
> + */

The comments around there tend to use a space instead of a tab in
comments like this:
/*
 * foo
 */

patch 2:
>                 area = zone->free_area + current_order;
>                 if (list_empty(&area->free_list))
>                         continue;
> -
>                 page = list_entry(area->free_list.next, struct page, lru);
>                 list_del(&page->lru);

More whitespace .

-- Dave

--
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>

Re: [Lhms-devel] [RFC] free_area[] bitmap elimination [0/3]

[Hiroyuki KAMEZAWA]

Dave Hansen wrote:
> On Fri, 2004-08-20 at 19:31, Hiroyuki KAMEZAWA wrote: 
> 
>>This patch removes bitmap from buddy allocator used in
>>alloc_pages()/free_pages() in the kernel 2.6.8.1.
> 
> 
> Looks very interesting.  The most mysterious thing about it that I can
> think of right now would be its cache behavior.  Since struct pages are
> at least 1/2 a cacheline on most architectures, you're going to dirty
> quite a few more cachelines than if you were accessing a quick bitmap. 
> However, if the page was recently accessed you might get *better*
> cacheline performance because the struct page itself may have been
> hotter than its bitmap.  
> 

> The use of page_count()==0 is a little worrisome.  There's almost
> certainly some race conditions where a page can be mistaken for free
> while it's page_count()==0, but before it's reached free_pages_bulk().
> 
> BTW, even if page_count()==0 isn't a valid check like you fear, you
> could always steal a bit in the page->flags.  Check out 
> free_pages_check() in mm/page_alloc.c for a nice summary of what state
> pages have to be in before they're freed.  
> 
Thanks for your comment.

In this patch, "whether a page is free and in buddy allocator ?" is confirmed by
page_count(page) == 0 and  page_order(page) == valid_order.
A valid_order is a value between (unsigned long)~0 - (unsigned long)~(MAX_ORDER)

But there may be pages which have vague page->private and conflict with my
buddy page checking.
I'd like to read free_pages_check() more and take page->flags into account.

-- KAME


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

--
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>

Re: [Lhms-devel] Re: [RFC] free_area[] bitmap elimination [0/3]

[Hiroyuki KAMEZAWA]

Dave Hansen wrote:
> On Mon, 2004-08-23 at 07:36, Dave Hansen wrote:
> 
>>I'll try and give these patches a run on a NUMA-Q today.  Those machines
>>are very cache-sensitive and should magnify any positive or negative
>>effects.  
> 
> 
> DISCLAIMER: SPEC(tm) and the benchmark name SDET(tm) are registered 
> trademarks of the Standard Performance Evaluation Corporation. This 
> benchmarking was performed for research purposes only, and the run
> results are non-compliant and not-comparable with any published results.
> 
> Scripts: 32     
> Iterations: 40
>                       2.6.8.1- | 2.6.8.1-
>                       vanilla  | nofreemap
>                     -----------+-----------
> Average Throughput:   18836.68 |  18839.37
> Standard Deviation:    1538.89 |   1791.29
> 
> No statistically different results.  Very cool.
> 

Thank you for trying and testing.
This results looks  good and encourages me :)

-- Kame


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

--
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>

Re: [Lhms-devel] [RFC] free_area[] bitmap elimination [0/3]

[Hiroyuki KAMEZAWA]

Hi

Thanks for comments.
I'd like to be more carefull about white spaces.

I'm now writing a new patch with detailed descriptions and
a few of additional range checks on 2.6.8.1-mm4.
This new one is running on both i386 and IA64 now.
(The previous patch cannot run on my IA64 ;( )

Thanks
Kame


Dave Hansen wrote:

> A few tiny, cosmetic comments on the patch itself:
> 
> 
>> }
>> 
>>+
>>+
>>+
>> #endif         /* CONFIG_HUGETLB_PAGE */
>> 
> 
> 
> Be careful about adding whitespace like that
> 
> 
>> /*
>>+ *     indicates page's order in freelist
>>+ *      order is recorded in inveterd manner.
>>+ */
> 
> 
> The comments around there tend to use a space instead of a tab in
> comments like this:
> /*
>  * foo
>  */
> 
> patch 2:
> 
>>                area = zone->free_area + current_order;
>>                if (list_empty(&area->free_list))
>>                        continue;
>>-
>>                page = list_entry(area->free_list.next, struct page, lru);
>>                list_del(&page->lru);
> 
> 
> More whitespace .
> 
> -- Dave
> 
> 


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

--
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>

Re: [Lhms-devel] [RFC] free_area[] bitmap elimination [0/3]

[Hirokazu Takahashi]

Hi,

Your approach seems much better than mine for hotplug-memory.

> > The use of page_count()==0 is a little worrisome.  There's almost
> > certainly some race conditions where a page can be mistaken for free
> > while it's page_count()==0, but before it's reached free_pages_bulk().
> > 
> > BTW, even if page_count()==0 isn't a valid check like you fear, you
> > could always steal a bit in the page->flags.  Check out 
> > free_pages_check() in mm/page_alloc.c for a nice summary of what state
> > pages have to be in before they're freed.  
> > 
> Thanks for your comment.
> 
> In this patch, "whether a page is free and in buddy allocator ?" is confirmed by
> page_count(page) == 0 and  page_order(page) == valid_order.
> A valid_order is a value between (unsigned long)~0 - (unsigned long)~(MAX_ORDER)
> 
> But there may be pages which have vague page->private and conflict with my
> buddy page checking.
> I'd like to read free_pages_check() more and take page->flags into account.

This may have a good side effect.

If we can distinguish pages in the free_area lists from others precisely
and we can know order of the pages, we could capture pages without
traversing all pages in the free_area lists when removing a memory-section.
remove_page_freearea() Bradley Christiansen wrote would work more 
effectively.


Thank you,
Hirokazu Takahashi.
--
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>

Re: [Lhms-devel] [RFC] free_area[] bitmap elimination [0/3]

[Dave Hansen]

On Mon, 2004-08-23 at 17:00, Hiroyuki KAMEZAWA wrote:
> In this patch, "whether a page is free and in buddy allocator ?" is confirmed by
> page_count(page) == 0 and  page_order(page) == valid_order.
> A valid_order is a value between (unsigned long)~0 - (unsigned long)~(MAX_ORDER)
> 
> But there may be pages which have vague page->private and conflict with my
> buddy page checking.
> I'd like to read free_pages_check() more and take page->flags into account.

I'm not saying that there *is* a bug with your code, just that
page->private has no *guarantees* about its contents, and there *can* be
a bug under certain conditions.  You rely on it not having particular
values but, since there are no checks and no zeroing, you really can't
assume anything.  Try setting page->private to random values just before
the free pages check, and I bet you'll eventually get some oopses.  

So, either don't rely on page->private for page_order(), or zero out
page->private before you zero the count.  Also, since you might
effectively be using one of these fields as a pseudo lock, make sure to
take memory ordering into account.  Unless it's an atomic function with
a test, things can get reordered quite easily.  

-- Dave

--
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>

Re: [Lhms-devel] [RFC] free_area[] bitmap elimination [0/3]

[Hiroyuki KAMEZAWA]

Dave Hansen wrote:

>>But there may be pages which have vague page->private and conflict with my
>>buddy page checking.
>>I'd like to read free_pages_check() more and take page->flags into account.
> 
> 
> I'm not saying that there *is* a bug with your code, just that
> page->private has no *guarantees* about its contents, and there *can* be
> a bug under certain conditions.  You rely on it not having particular
> values but, since there are no checks and no zeroing, you really can't
> assume anything.  Try setting page->private to random values just before
> the free pages check, and I bet you'll eventually get some oopses.  
>
you are right.
my patches doesn't check and clear page->private before calling
free_pages_bulk().

> So, either don't rely on page->private for page_order(), or zero out
> page->private before you zero the count.  Also, since you might
> effectively be using one of these fields as a pseudo lock, make sure to
> take memory ordering into account.  Unless it's an atomic function with
> a test, things can get reordered quite easily.  
> 

I'd like to fix problems in the next patch, thank you for your advise :).


--Kame

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

--
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>