[RFC] buddy allocator without bitmap(2) [1/3]

[Hiroyuki KAMEZAWA <kamezawa.hiroyu@jp.fujitsu.com>]

This is 2nd file.
Implements initialization code for buddy allocator.


- Kame

------------

This patch removes bitmap allocation in zone_init_free_lists() and
page_to_bitmap_size();

calculate_aligned_end() works
(a) detects mem_map is aligned or not.
(b) if start of mem_map is not aligned, add PG_buddyend flags to pages
     which has no lower address buddy.
(c) if end of mem_map is not aligned, reserve it by reserve_bootmem()



-- Kame


---

  linux-2.6.9-rc1-mm1-k-kamezawa/mm/page_alloc.c |  112 ++++++++++++++++---------
  1 files changed, 73 insertions(+), 39 deletions(-)

diff -puN mm/page_alloc.c~eliminate-bitmap-init mm/page_alloc.c
--- linux-2.6.9-rc1-mm1-k/mm/page_alloc.c~eliminate-bitmap-init	2004-08-31 18:37:14.596519040 +0900
+++ linux-2.6.9-rc1-mm1-k-kamezawa/mm/page_alloc.c	2004-08-31 18:43:30.723339072 +0900
@@ -1499,6 +1499,70 @@ static void __init calculate_zone_totalp
  	printk(KERN_DEBUG "On node %d totalpages: %lu\n", pgdat->node_id, realtotalpages);
  }

+/*
+ * (1) checks a mem_map is aligned to max_order or not.
+ * (2) if mem_map is not aligned in its start address, find pages which are
+ * lower-end of buddy.
+ * (3) if mem_map is not aligned in end addres,, find a page which is higher
+ * end of buddy and remove it from buddy allocator.
+ * All found pages are marked as PG_buddyend. These marked page has speccial
+ * meaning in free_pages().
+ */
+
+
+static void __init calculate_aligned_end(struct zone *zone,
+					 unsigned long start_pfn,
+					 int nr_pages)
+{
+	struct page *base;
+	unsigned long mask;
+	long start_idx, end_idx;
+	
+	start_idx = start_pfn - zone->zone_start_pfn;
+	end_idx = start_idx + nr_pages - 1;
+	mask = (1 << MAX_ORDER) - 1;
+	base = zone->zone_mem_map;
+	
+	if (start_idx & mask) {
+		long edge_idx, buddy_idx;
+		int order;
+		edge_idx = start_idx;
+		/*
+		 * Mark all pages which can be  higher half of buddy in
+		 * its index, but its lower half is never available.
+		 */
+		for (edge_idx = start_idx,order = 0;
+		     order < MAX_ORDER;
+		     order++) {
+			if (edge_idx > end_idx)
+				break;
+			buddy_idx = edge_idx ^ (1 << order);
+			if (buddy_idx < edge_idx) {
+				SetPageBuddyend(base + edge_idx);
+				edge_idx += (1 << order);
+			}
+		}
+	}
+	if ((end_idx & mask) != mask) {
+		unsigned long end_address;
+		/*
+		 * Reserve the last page as the stopper for buddy allocator.
+		 * This page is a victim to make buddy allocator work fine.
+		 *
+		 * Note:
+                 * We are using reserve_bootmem() here, is this correct ?
+		 */
+		SetPageBuddyend(base + end_idx);
+		SetPagePrivate(base + end_idx);
+		end_address = (zone->zone_start_pfn + end_idx) << PAGE_SHIFT;
+#ifndef CONFIG_DISCONTIGMEM
+		reserve_bootmem(end_address,PAGE_SIZE);
+#else
+		reserve_bootmem_node(zone->zone_pgdat,end_address,PAGE_SIZE);
+#endif
+	}
+	return;
+}

  /*
   * Initially all pages are reserved - free ones are freed
@@ -1510,7 +1574,9 @@ void __init memmap_init_zone(unsigned lo
  {
  	struct page *start = pfn_to_page(start_pfn);
  	struct page *page;
-
+	unsigned long saved_start_pfn = start_pfn;
+	struct zone *zonep = zone_table[NODEZONE(nid, zone)];
+	
  	for (page = start; page < (start + size); page++) {
  		set_page_zone(page, NODEZONE(nid, zone));
  		set_page_count(page, 0);
@@ -1524,51 +1590,19 @@ void __init memmap_init_zone(unsigned lo
  #endif
  		start_pfn++;
  	}
-}
-
-/*
- * Page buddy system uses "index >> (i+1)", where "index" is
- * at most "size-1".
- *
- * The extra "+3" is to round down to byte size (8 bits per byte
- * assumption). Thus we get "(size-1) >> (i+4)" as the last byte
- * we can access.
- *
- * The "+1" is because we want to round the byte allocation up
- * rather than down. So we should have had a "+7" before we shifted
- * down by three. Also, we have to add one as we actually _use_ the
- * last bit (it's [0,n] inclusive, not [0,n[).
- *
- * So we actually had +7+1 before we shift down by 3. But
- * (n+8) >> 3 == (n >> 3) + 1 (modulo overflows, which we do not have).
- *
- * Finally, we LONG_ALIGN because all bitmap operations are on longs.
- */
-unsigned long pages_to_bitmap_size(unsigned long order, unsigned long nr_pages)
-{
-	unsigned long bitmap_size;
-
-	bitmap_size = (nr_pages-1) >> (order+4);
-	bitmap_size = LONG_ALIGN(bitmap_size+1);
+	/* Because memmap_init_zone() is called in suitable way
+	 * even if zone has memory holes,
+	 * calling calculate_aligned_end(zone) here is reasonable
+	 */
+	calculate_aligned_end(zonep, saved_start_pfn, size);

-	return bitmap_size;
  }

  void zone_init_free_lists(struct pglist_data *pgdat, struct zone *zone, unsigned long size)
  {
  	int order;
-	for (order = 0; ; order++) {
-		unsigned long bitmap_size;
-
+	for (order = 0 ; order < MAX_ORDER ; order++) {
  		INIT_LIST_HEAD(&zone->free_area[order].free_list);
-		if (order == MAX_ORDER-1) {
-			zone->free_area[order].map = NULL;
-			break;
-		}
-
-		bitmap_size = pages_to_bitmap_size(order, size);
-		zone->free_area[order].map =
-		  (unsigned long *) alloc_bootmem_node(pgdat, bitmap_size);
  	}
  }


_