free_area[] bitmap elimination [0/3]

RFC In review Hiroyuki KAMEZAWA 5 participants 22 messages Aug 21, 2004 – Aug 24, 2004

Subsystems (3)

Memory management MM core MGLRU

lore

Share & tools

lore

Hiroyuki KAMEZAWA

author

2004-08-21 02:26 UTC #0 lore raw

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

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

Signature · 2 lines

--the clue is these footmarks leading to the door.--
KAMEZAWA Hiroyuki <[email protected]>

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

include/linux/mmzone.h renamed from include/linux/mmzone.h~eliminate-bitmap-p01 +0 -1

diff -puN include/linux/mmzone.h~eliminate-bitmap-p01 include/linux/mmzone.h
@@ -34,7 +34,6 @@
 
 struct free_area {
 	struct list_head	free_list;
-	unsigned long		*map;
 };
 
 struct pglist_data;

include/linux/mm.h renamed from include/linux/mm.h~eliminate-bitmap-p01 +14 -2

diff -puN include/linux/mm.h~eliminate-bitmap-p01 include/linux/mm.h
@@ -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

William Lee Irwin III

2004-08-21 02:55 UTC #1 lore raw

Quoted 4 lines · Hiroyuki KAMEZAWA

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.

Quoted 8 lines

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 [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Hiroyuki KAMEZAWA

author

2004-08-21 04:55 UTC #2 lore raw

Quoted 4 lines · William Lee Irwin III

Quoted 2 lines · Hiroyuki KAMEZAWA
This patch removes bitmap from buddy allocator used in alloc_pages()/free_pages() in the kernel 2.6.8.1.

<snip>

Quoted 8 lines

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.

Quoted 4 lines

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

Signature · 8 lines

--the clue is these footmarks leading to the door.--
KAMEZAWA Hiroyuki <[email protected]>

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

Hirokazu Takahashi

2004-08-21 05:01 UTC #3 lore raw

Hi,

Quoted 20 lines

Quoted 4 lines · William Lee Irwin III
Quoted 2 lines · Hiroyuki KAMEZAWA
This patch removes bitmap from buddy allocator used in alloc_pages()/free_pages() in the kernel 2.6.8.1.
<snip>
Quoted 8 lines
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.
Quoted 4 lines
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.

Quoted 4 lines

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.

Quoted 4 lines

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 [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Hiroyuki KAMEZAWA

author

2004-08-21 05:21 UTC #4 lore raw

Hi,

Quoted 11 lines · Hirokazu Takahashi

Hi,
Quoted 8 lines
Quoted 5 lines · William Lee Irwin III
Quoted 2 lines · Hiroyuki KAMEZAWA
This patch removes bitmap from buddy allocator used in alloc_pages()/free_pages() in the kernel 2.6.8.1.

<snip>

Quoted 10 lines

Quoted 4 lines
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

Signature · 8 lines

--the clue is these footmarks leading to the door.--
KAMEZAWA Hiroyuki <[email protected]>

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

William Lee Irwin III

2004-08-21 05:01 UTC #5 lore raw

In reply to Hiroyuki KAMEZAWA

Quoted 9 lines · William Lee Irwin III

Quoted 9 lines
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.

Quoted 6 lines · Hiroyuki KAMEZAWA

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.

Hirokazu Takahashi

2004-08-21 04:56 UTC #6 lore raw

In reply to William Lee Irwin III

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.

Quoted 14 lines · Hiroyuki KAMEZAWA

Quoted 4 lines
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.
Quoted 8 lines
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).

Quoted 6 lines

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.

Quoted 3 lines

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 [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

William Lee Irwin III

2004-08-21 05:21 UTC #7 lore raw

Quoted 5 lines · Hirokazu Takahashi

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.

Hiroyuki KAMEZAWA

author

2004-08-21 05:32 UTC #8 lore raw

Quoted 9 lines · William Lee Irwin III

Quoted 5 lines · Hirokazu Takahashi
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.

Quoted 8 lines

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

Signature · 8 lines

--the clue is these footmarks leading to the door.--
KAMEZAWA Hiroyuki <[email protected]>

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

William Lee Irwin III

2004-08-21 05:37 UTC #9 lore raw

Quoted 6 lines · William Lee Irwin III

Quoted 6 lines
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.

Quoted 2 lines · Hiroyuki KAMEZAWA

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.

Hiroyuki KAMEZAWA

author

2004-08-21 06:05 UTC #10 lore raw

Hi,

Quoted 16 lines · William Lee Irwin III

Quoted 6 lines · William Lee Irwin III
Quoted 6 lines
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.
Quoted 2 lines · Hiroyuki KAMEZAWA
Okay, I understand several BUG_ON() are needless. I'll be more carefull to recognize what is checked.

Quoted 7 lines

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

Signature · 8 lines

--the clue is these footmarks leading to the door.--
KAMEZAWA Hiroyuki <[email protected]>

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

William Lee Irwin III

2004-08-21 17:48 UTC #11 lore raw

Quoted 5 lines · Hiroyuki KAMEZAWA

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.

Quoted 7 lines · Hiroyuki KAMEZAWA

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.

Quoted 4 lines · Hiroyuki KAMEZAWA

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.

Nigel Cunningham

2004-08-21 09:43 UTC #12 lore raw

In reply to Hiroyuki KAMEZAWA

Hi.

Quoted 4 lines · Hiroyuki KAMEZAWA

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

Signature · 12 lines

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 [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Dave Hansen

2004-08-23 14:36 UTC #13 lore raw

In reply to Hiroyuki KAMEZAWA

Quoted 2 lines · Hiroyuki KAMEZAWA

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

Dave Hansen

2004-08-23 15:00 UTC #14 lore raw

Quoted 3 lines · Dave Hansen

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

Hiroyuki KAMEZAWA

author

2004-08-24 00:02 UTC #15 lore raw

Quoted 14 lines · Dave Hansen

Quoted 3 lines · Dave Hansen
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

Quoted 8 lines

                      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

Signature · 8 lines

--the clue is these footmarks leading to the door.--
KAMEZAWA Hiroyuki <[email protected]>

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

Hiroyuki KAMEZAWA

author

2004-08-23 23:54 UTC #16 lore raw

In reply to Dave Hansen

Quoted 15 lines · Dave Hansen

Quoted 2 lines · Hiroyuki KAMEZAWA
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.

Quoted 9 lines

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

Signature · 8 lines

--the clue is these footmarks leading to the door.--
KAMEZAWA Hiroyuki <[email protected]>

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

Hirokazu Takahashi

2004-08-24 02:28 UTC #17 lore raw

Hi,

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

Quoted 11 lines

Quoted 9 lines
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.

Quoted 7 lines

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.

Dave Hansen

2004-08-24 02:49 UTC #18 lore raw

In reply to Hiroyuki KAMEZAWA

Quoted 7 lines · Hiroyuki KAMEZAWA

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

Hiroyuki KAMEZAWA

author

2004-08-24 03:26 UTC #19 lore raw

Quoted 5 lines · Dave Hansen

Quoted 3 lines
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.

Quoted 7 lines

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

Quoted 6 lines

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

Signature · 8 lines

--the clue is these footmarks leading to the door.--
KAMEZAWA Hiroyuki <[email protected]>

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

Dave Hansen

2004-08-23 15:43 UTC #20 lore raw

In reply to Hiroyuki KAMEZAWA

A few tiny, cosmetic comments on the patch itself:

include/linux/mm.h static inline void put_page(struct page · line 320

Quoted 7 lines

}
include/linux/mm.h renamed from include/linux/mm.h~eliminate-bitmap-p01 +3 -0
+
+
+
 #endif         /* CONFIG_HUGETLB_PAGE */

Be careful about adding whitespace like that

Quoted 4 lines

/*
+ * 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:

Quoted 6 lines

                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

Hiroyuki KAMEZAWA

author

2004-08-24 00:10 UTC #21 lore raw

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

Quoted 42 lines · Dave Hansen

A few tiny, cosmetic comments on the patch itself:
Quoted 7 lines
}
include/linux/mm.h renamed from include/linux/mm.h~eliminate-bitmap-p01 +3 -0
+
+
+
#endif /* CONFIG_HUGETLB_PAGE */
Be careful about adding whitespace like that
Quoted 4 lines
/*
+ * 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:
Quoted 6 lines
               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

Signature · 8 lines

--the clue is these footmarks leading to the door.--
KAMEZAWA Hiroyuki <[email protected]>

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