[RFC][PATCH] no bitmap buddy allocator: remove free_area->map (0/4)

[RFC][PATCH] no bitmap buddy allocator: remove free_area->map (0/4)

[Hiroyuki KAMEZAWA]

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.


Signed-off-by: KAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com>



---

  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
--- test-kernel/include/linux/mm.h~eliminate-bitmap-includes	2004-09-08 17:31:41.341538896 +0900
+++ test-kernel-kamezawa/include/linux/mm.h	2004-09-08 17:31:41.346538136 +0900
@@ -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
--- test-kernel/include/linux/mmzone.h~eliminate-bitmap-includes	2004-09-08 17:31:41.343538592 +0900
+++ test-kernel-kamezawa/include/linux/mmzone.h	2004-09-08 17:31:41.347537984 +0900
@@ -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 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][PATCH] no bitmap buddy allocator: remove free_area->map (0/4)

[Hiroyuki KAMEZAWA]

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