no bitmap buddy allocator: remove free_area->map (0/4)

Hi,

This series of patches remove bitmaps from kernel's page allocator, so-called buddy allocator.This is part (0/4) and removes free_area->map.

By removing bitmap, we can reduce a strcuture whose size is depends on installed memory size.
Removing it is good for implementing memory-hotplug and some other codes.

In buddy system, a page's order means size of contiguous free pages. If a free page[x] 's order is Y, there are contiguous free pages from page[X] to page[X + 2^(Y) - 1]

In this patch, when a page is a head of contiguous free pages of order X, it is marked with PG_private and set page->private to X.
A page's buddy in order X is simply calculated by

buddy_idx = page_idx ^ (1 << X).

We can coalece 2 contiguous pages if
let buddy = pfn_to_page(zone->zone_start_pfn + page_idx ^ (1 << X)), (page_is_free(buddy) && PagePrivate(buddy) && page_order(buddy) == 'X')

Although a look of code is changed, this algorithm itself is not different from the original buddy allocator. Only difference is there is no bitmap.

---

 test-kernel-kamezawa/include/linux/mm.h     |   26 ++++++++++++++++++++++++++
 test-kernel-kamezawa/include/linux/mmzone.h |    7 ++++++-
 2 files changed, 32 insertions(+), 1 deletion(-)

diff -puN include/linux/mm.h~eliminate-bitmap-includes include/linux/mm.h
@@ -213,6 +213,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.

@@ -326,6 +329,29 @@ static inline void put_page(struct page
 #endif		/* CONFIG_HUGETLB_PAGE */
 
 /*
+ * These functions are used in alloc_pages()/free_pages(), buddy allocator.
+ * page_order(page) returns an order of a free page in buddy allocator.
+ *
+ * this is used with PG_private flag
+ *
+ * Note : all PG_private operations used in buddy system is done while
+ * zone->lock is acquired. So set and clear PG_private bit operation
+ * does not need to be atomic.
+ */
+
+#define PAGE_INVALID_ORDER (~0UL)
+
+static inline unsigned long page_order(struct page *page)
+{
+	return page->private;
+}
+
+static inline void set_page_order(struct page *page,unsigned long order)
+{
+	page->private = order;
+}
+
+/*
  * 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

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

@@ -207,6 +206,12 @@ struct zone {
 	unsigned long		zone_start_pfn;
 
 	/*
+	 * indicates start_pfn/end_pfn of initialized mem_map
+	 */
+	unsigned long           memmap_start_pfn;
+	unsigned long           memmap_end_pfn;
+
+        /*
 	 * rarely used fields:
 	 */
 	char			*name;

_

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

This is a quick change-log from "previous-version" for comparison.

Big difference from previous one is revival of bad_range() and reduced victim pages.

-- bad_range() is modified and bad_range_pfn() is added.
-- bad_range_pfn() uses zone->memmap_start_pfn/memmap_end_pfn instead of using
zone_start_pfn/spanned_pages. Because IA64's memmap's start is not equal to zone->zone_start_pfn.
-- In most inner loop of __free_pages_bulk(), bad_range_pfn() is used. -- this bad_range_pfn() enables me to reduce victim pages.

     In my IA64,
Sep  8 18:59:38 casares kernel: calculate_buddy_range() 36e 129901
Sep  8 18:59:38 casares kernel: victim end page 1feda
Sep  8 18:59:38 casares kernel: calculate_buddy_range() 1fedc 292
Sep  8 18:59:38 casares kernel: victim top page 1fedc
Sep  8 18:59:38 casares kernel: victim top page 1fee0
Sep  8 18:59:38 casares kernel: victim top page 1ff00
Sep  8 18:59:38 casares kernel: victim end page 1ffff
Sep  8 18:59:38 casares kernel: saved end victim page 1ffff
Sep  8 18:59:38 casares kernel: calculate_buddy_range() 40000 262144
Sep  8 18:59:38 casares kernel: calculate_buddy_range() a0000 131072
Sep  8 18:59:38 casares kernel: victim top page a0000
Sep  8 18:59:38 casares kernel: Built 1 zonelists
      # of victim pages is 5. It was 19 in previous version.

-- ia64's virtual_memmap_init() can call memmap_init() several times for the same
memory range. It was fixed.

-- Kame

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