free_area[] bitmap elimination[0/3]
Subsystems (3)
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
Signature · 2 lines
--the clue is these footmarks leading to the door.-- KAMEZAWA Hiroyuki <[email protected]>
This patch removes bitmap from buddy allocator, removes free_area_t's bitmap in include/linux/mmzone.h and adds some definition in include/linux/mm.h
Currently,Linux's page allocator uses buddy algorithm and codes for buddy allocator uses bitmap. For what is bitmap is used ?
(*) for recording "a page is free" and its order.
If a page is free and is a head of contiguous free pages of order 'X', we can record it byset_bit(free_area[X]->bitmap, index_of_page)
For coalescing, when there is a chunk of free pages of order 'X', we can test whether we can coalesce or not by, test_bit(free_aera[X]->bitmap,index_of_buddy) index_of_buddy can be calculated by (index_of_page ^ (1 << order))
This patch removes bitmap and recording a free page's order in its page->private field. If a page is free and it is a head of a free memory chunk, page->private indicates the order of the page. and PG_private bit is used to show propriety of information.
For coalescing, when there is a page which is a chunk of free pages of order 'X', we can test whether we can coalesce or not by
(page_is_free(buddy) && PagePrivate(buddy) && page_order(buddy) == 'X') address of buddy can be calculated by the same way in bitmap case.
If page is free and on the buddy system, PG_private bit is set and has its order in page->private. This scheme is safe because...
(a) when page is being freed, PG_private is not set. (see free_pages_check())
(b) when page is free and on the buddy system, PG_private is set. These facts are guaranteed by zone->lock.
Only one thread can change a free page's PG_private bit and private field at anytime.
in mmzone.h, zone->aligned_order is added. this is explained in next patch.
-- Kame
---
linux-2.6.8.1-mm4-kame-kamezawa/include/linux/mm.h | 20 +++++++++++++++++ linux-2.6.8.1-mm4-kame-kamezawa/include/linux/mmzone.h | 4 ++- 2 files changed, 23 insertions(+), 1 deletion(-)
include/linux/mm.h renamed from include/linux/mm.h~eliminate-bitmap-includes +20 -0
@@ -209,6 +209,9 @@ struct page {* usually used for buffer_heads * if PagePrivate set; used for * swp_entry_t if PageSwapCache +* When page is free: +* this indicates order of page +* in buddy allocator. */ struct address_space *mapping;/* If low bit clear, points to * inode address_space, or NULL.
@@ -322,6 +325,23 @@ static inline void put_page(struct page#endif /* CONFIG_HUGETLB_PAGE */ /* +* These macros are used in alloc_pages()/free_pages(), buddy allocator. +* page_order(page) returns an order of a free page in buddy allocator. +* set_page_order(page, order) sets an order of a free page in buddy allocator. +* Invalidate_page_order() invalidates order information for avoiding +* conflicts of pages in transition state. +* +* this is used with PG_private flag +*/ +#define set_page_order (page,order)\ + do {\ + (page)->private = (order);\ + SetPagePrivate((page));\ + } while(0) +#define invalidate_page_order (page) ClearPagePrivate((page)) +#define page_order (page) ((page)->private) + +/* * 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
include/linux/mmzone.h renamed from include/linux/mmzone.h~eliminate-bitmap-includes +3 -1
@@ -22,7 +22,6 @@struct free_area {struct list_head free_list; -unsigned long *map; };struct pglist_data ;
@@ -163,7 +162,10 @@ struct zone {/* * free areas of different sizes +* aligned_order shows the upper bound of aligned order, +* aligned_order means every page below it has a buddy. */ +int aligned_order;struct free_area free_area[MAX_ORDER ];/*
_
Quoted 9 lines · Hiroyuki KAMEZAWA
/*
+ * These macros are used in alloc_pages()/free_pages(), buddy allocator.
+ *page_order(page)returns an order of a free page in buddy allocator.
+ *set_page_order(page, order)sets an order of a free page in buddy allocator.
+ *Invalidate_page_order()invalidates order information for avoiding
+ * conflicts of pages in transition state.
+ *
+ * this is used withPG_privateflag
+ */
include/linux/mm.h static inline void put_page(struct page · line 344
Quoted 9 lines
include/linux/mm.h renamed from include/linux/mm.h~eliminate-bitmap-includes +9
-0+#define set_page_order (page,order)\ + do {\ + (page)->private = (order);\ + SetPagePrivate((page));\ + } while(0) +#define invalidate_page_order (page) ClearPagePrivate((page)) +#define page_order (page) ((page)->private) + +/*
Can these be made into static inline functions instead of macros?
-- Dave
--
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>
Quoted 4 lines · Dave Hansen
Quoted 4 lines
include/linux/mm.h renamed from include/linux/mm.h~eliminate-bitmap-includes +4
-0+#define set_page_order (page,order)\ + do {\ + (page)->private = (order);\ + SetPagePrivate((page));\
Quoted 8 lines
include/linux/mm.h static inline void put_page(struct page · line 344
Quoted 5 lines
include/linux/mm.h renamed from include/linux/mm.h~eliminate-bitmap-includes +5
-0+ } while(0) +#define invalidate_page_order (page) ClearPagePrivate((page)) +#define page_order (page) ((page)->private) + +/* Can these be made into static inline functions instead of macros?
Okay, I'd like to change these macros to static inline functions.
-- 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>