[rfc][patch 0/3] bootmem2: a memory block-oriented boot time allocator

[rfc][patch 0/3] bootmem2: a memory block-oriented boot time allocator

[Johannes Weiner]

Hi,

here is a bootmem allocator replacement that uses one bitmap for all
available pages and works with a model of contiguous memory blocks
that reside on nodes instead of nodes only as the current allocator
does.

The problem is that memory nodes are not anymore garuanteed to be
linear on certain configurations, they may overlap each other and a
node might span page ranges that are not physically residing on it.

Note that this is in no way theoretical only, bootmem suffers from
this fact right now: A pfn range has to be operated on on every node
that holds it (because a PFN is not unique anymore) and bootmem can
not garuantee that the memory allocated from a specific node actually
resides on that node.

For example:

	node 0: 0-2G, 4-6G
	node 1: 2-4G, 6-8G

Bootmem currently sees the 2-4G range twice (and has to operate on
both node's bitmaps) and if memory is allocated on node 1, it may
return memory that is between the 2-4G range and actually resides on
node 0.

Bootmem2 tries to fix these fundamental design issues by using one
bitmap for all pfns and therefor garuantees that a PFN stays unique as
it should.  Nodes are divided into contiguous memory blocks that are
certain to reside on one node.  A node-specific allocation request
must fit completely into one block of the the node to garuantee
locality.

For example:

	node 0: block 0: 0-2G, block 1: 4-6G
	node 1: block 2: 2-4G, block 3: 6-8G

The global bitmap represents 0-8G and every pfn is still unique.  An
allocation request on node 1 must fit into block 2 or block 3 and the
memory is therefor garuanteed to be reside on that node.

The important change in arch-code is that on setups with multiple
blocks per node, every block must be registered on its own to make
bootmem2 aware of them.  And the allocator setup in general changes to
a two-step process: register all blocks/nodes first, then enable it by
providing memory that is big enough to hold the bitmap for all pfns in
the system.

The implementation is similar to bootmem but the code is shorter (and
clearer, IMHO):

$ sloc.awk < mm/bootmem.c
455 lines of code, 65 lines of comments (520 lines total)

$ sloc.awk < mm/bootmem2.c
325 lines of code, 120 lines of comments (445 lines total)

bootmem is meant to stay until all users are migrated to bootmem2, it
can be dropped completely after that.

Note that this is in no way production code yet, but I would like to
have some comments on it since the core is essentially ready and
running on my machine (and I might be already caught in a deep forest
without seeing the trees).

Sparsemem hotplug is not supported, I have not yet looked deep enough
into its bootmem interface.  Yasunori, any suggestions?

Also, it would be a stupid idea if I'd migrate arch-code I can not
test at all, right now only x86_32 has been migrated, sorry :/

	Hannes

 arch/x86/Kconfig           |    1
 arch/x86/kernel/setup_32.c |    4
 arch/x86/mm/init_32.c      |    2
 include/linux/bootmem.h    |    6
 include/linux/bootmem2.h   |  207 +++++++++++++++++
 include/linux/numa.h       |   12 -
 mm/Kconfig                 |    3
 mm/Makefile                |    7
 mm/bootmem2.c              |  534 +++++++++++++++++++++++++++++++++++++++++++++
 mm/page_alloc.c            |    4
 10 files changed, 772 insertions(+), 8 deletions(-)

--
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:"dont@kvack.org"> email@kvack.org </a>

[rfc][patch 1/3] mm: Define NR_NODE_MEMBLKS unconditionally

[Johannes Weiner]

[-- Attachment #1: nr_node_memblks.patch --]
[-- Type: text/plain, Size: 1196 bytes --]

Bootmem needs to work on contiguous memory block quantities rather
than whole nodes, for the latter may overlap.  So make this maxium
number and the resulting number of blocks per node available to
generic code like bootmem.

Signed-off-by: Johannes Weiner <hannes@saeurebad.de>
---

Index: linux-2.6/include/linux/numa.h
===================================================================
--- linux-2.6.orig/include/linux/numa.h
+++ linux-2.6/include/linux/numa.h
@@ -1,13 +1,17 @@
 #ifndef _LINUX_NUMA_H
 #define _LINUX_NUMA_H
 
-
 #ifdef CONFIG_NODES_SHIFT
-#define NODES_SHIFT     CONFIG_NODES_SHIFT
+#define NODES_SHIFT		CONFIG_NODES_SHIFT
 #else
-#define NODES_SHIFT     0
+#define NODES_SHIFT		0
 #endif
 
-#define MAX_NUMNODES    (1 << NODES_SHIFT)
+#define MAX_NUMNODES		(1 << NODES_SHIFT)
+
+#ifndef NR_NODE_MEMBLKS
+#define NR_NODE_MEMBLKS		MAX_NUMNODES
+#endif
+#define NR_MEMBLKS_PER_NODE	(NR_NODE_MEMBLKS / MAX_NUMNODES)
 
 #endif /* _LINUX_NUMA_H */

-- 

--
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:"dont@kvack.org"> email@kvack.org </a>

[rfc][patch 2/3] mm: bootmem2 - memory block oriented boot time allocator

[Johannes Weiner]

[-- Attachment #1: bootmem2.patch --]
[-- Type: text/plain, Size: 22123 bytes --]

A boot time allocator that uses a bitmap for all pages in the system,
merges subsequent partial-page allocations, and uses a memory block
model instead of nodes to fit the reality that nodes are no contiguous
memory holders anymore.

Signed-off-by: Johannes Weiner <hannes@saeurebad.de>
---

Index: linux-2.6/include/linux/bootmem2.h
===================================================================
--- /dev/null
+++ linux-2.6/include/linux/bootmem2.h
@@ -0,0 +1,207 @@
+#ifndef _LINUX_BOOTMEM2_H
+#define _LINUX_BOOTMEM2_H
+
+#include <linux/mmzone.h>
+#include <asm/dma.h>
+
+extern void bootmem_register_block(int bid, unsigned long start,
+				unsigned long end);
+
+extern unsigned long bootmem_map_pages(void);
+
+extern void bootmem_setup(unsigned long mapstart);
+
+extern unsigned long bootmem_release_block(int bid);
+
+extern void bootmem_free(unsigned long addr, unsigned long size);
+extern int bootmem_reserve(unsigned long addr, unsigned long size,
+			int exclusive);
+
+extern void *bootmem_alloc_block(int bid, unsigned long size,
+				unsigned long align, unsigned long goal,
+				unsigned long limit);
+
+/*
+ * Multiple nodes
+ */
+
+static inline int bootmem_node_block(int nid)
+{
+	if (nid == -1)
+		return nid;
+	return nid * NR_MEMBLKS_PER_NODE;
+}
+
+static inline int bootmem_block_node(int bid)
+{
+	return bid / NR_MEMBLKS_PER_NODE;
+}
+
+static inline void bootmem_register_node(int nid, unsigned long start,
+					unsigned long end)
+{
+#if NR_MEMBLKS_PER_NODE > 1
+	extern void __multiple_memblocks_per_node(void);
+	__multiple_memblocks_per_node();
+#endif
+	return bootmem_register_block(nid, start, end);
+}
+
+extern unsigned long bootmem_release_node(int nid);
+
+extern void *bootmem_alloc_node(int nid, unsigned long size,
+				unsigned long align, unsigned long goal,
+				unsigned long limit);
+
+extern void *bootmem_alloc_low_node(int nid, unsigned long size,
+				unsigned long align, unsigned long goal);
+
+
+#ifdef CONFIG_SPARSEMEM
+extern void *bootmem_alloc_section(unsigned long size, unsigned long sec_nr);
+#endif
+
+/*
+ * Single node
+ */
+
+static inline void bootmem_register(unsigned long start, unsigned long end)
+{
+	bootmem_register_node(0, start, end);
+}
+static inline unsigned long bootmem_release(void)
+{
+	return bootmem_release_node(0);
+}
+
+/*
+ * Node agnostic
+ */
+
+#ifndef CONFIG_HAVE_ARCH_BOOTMEM_NODE
+static inline void *bootmem_alloc(unsigned long size)
+{
+	return bootmem_alloc_node(-1, size, SMP_CACHE_BYTES,
+				__pa(MAX_DMA_ADDRESS), 0);
+}
+static inline void *bootmem_alloc_low(unsigned long size)
+{
+	return bootmem_alloc_low_node(-1, size, SMP_CACHE_BYTES, 0);
+}
+static inline void *bootmem_alloc_pages(unsigned long size)
+{
+	return bootmem_alloc_node(-1, size, PAGE_SIZE,
+				__pa(MAX_DMA_ADDRESS), 0);
+}
+static inline void *bootmem_alloc_low_pages(unsigned long size)
+{
+	return bootmem_alloc_low_node(-1, size, PAGE_SIZE, 0);
+}
+#endif /* !CONFIG_HAVE_ARCH_BOOTMEM_NODE */
+
+/*
+ * bootmem legacy
+ */
+
+/* XXX: Can this go somewhere else? */
+extern unsigned long min_low_pfn, max_low_pfn, max_pfn;
+#ifdef CONFIG_CRASH_DUMP
+extern unsigned long saved_max_pfn;
+#endif
+/* Catch those... */
+typedef void *bootmem_data_t;
+/* !XXX */
+
+#define BOOTMEM_DEFAULT		0
+#define BOOTMEM_EXCLUSIVE	1
+
+static inline unsigned long bootmem_bootmap_pages(unsigned long pages)
+{
+	return bootmem_map_pages();
+}
+static inline void free_bootmem(unsigned long addr, unsigned long size)
+{
+	bootmem_free(addr, size);
+}
+static inline void free_bootmem_node(pg_data_t *pgdat, unsigned long addr,
+				unsigned long size)
+{
+	bootmem_free(addr, size);
+}
+static inline int reserve_bootmem_node(pg_data_t *pgdat, unsigned long addr,
+				unsigned long size, int flags)
+{
+	return bootmem_reserve(addr, size, flags & BOOTMEM_EXCLUSIVE);
+}
+static inline void *__alloc_bootmem_low(unsigned long size, unsigned long align,
+					unsigned long goal)
+{
+	return bootmem_alloc_low_node(-1, size, align, goal);
+}
+
+#ifndef CONFIG_HAVE_ARCH_BOOTMEM_NODE
+static inline int reserve_bootmem(unsigned long addr, unsigned long size,
+				int flags)
+{
+	return bootmem_reserve(addr, size, flags & BOOTMEM_EXCLUSIVE);
+}
+static inline void *alloc_bootmem(unsigned long size)
+{
+	return bootmem_alloc(size);
+}
+static inline void *alloc_bootmem_low(unsigned long size)
+{
+	return bootmem_alloc_low(size);
+}
+static inline void *alloc_bootmem_pages(unsigned long nr)
+{
+	return bootmem_alloc_pages(nr);
+}
+static inline void *alloc_bootmem_low_pages(unsigned long nr)
+{
+	return bootmem_alloc_low_pages(nr);
+}
+static inline void *alloc_bootmem_node(pg_data_t *pgdat, unsigned long size)
+{
+	return bootmem_alloc_node(pgdat->node_id, size, SMP_CACHE_BYTES,
+				__pa(MAX_DMA_ADDRESS), 0);
+}
+static inline void *alloc_bootmem_pages_node(pg_data_t *pgdat,
+						unsigned long size)
+{
+	return bootmem_alloc_node(pgdat->node_id, size, PAGE_SIZE,
+				__pa(MAX_DMA_ADDRESS), 0);
+}
+static inline void *alloc_bootmem_low_pages_node(pg_data_t *pgdat,
+						unsigned long size)
+{
+	return bootmem_alloc_low_node(pgdat->node_id, size, PAGE_SIZE, 0);
+}
+#endif /* !CONFIG_HAVE_ARCH_BOOTMEM_NODE */
+
+/*
+ * XXX: Can this go somewhere else?
+ */
+#ifdef CONFIG_HAVE_ARCH_ALLOC_REMAP
+extern void *alloc_remap(int nid, unsigned long size);
+#else
+static inline void *alloc_remap(int n, unsigned long s) { return NULL; }
+#endif
+extern unsigned long __meminitdata nr_kernel_pages;
+extern unsigned long __meminitdata nr_all_pages;
+extern void *alloc_large_system_hash(const char *tablename,
+				unsigned long bucketsize,
+				unsigned long numentries,
+				int scale, int flags,
+				unsigned int *_hash_shift,
+				unsigned int *_hash_mask,
+				unsigned long limit);
+#define HASH_EARLY 0x00000001
+#if defined(CONFIGU_NUMA) && (defined(CONFIG_IA64) || defined(CONFIG_X86_64))
+#define HASHDIST_DEFAULT 1
+#else
+#define HASHDIST_DEFAULT 0
+#endif
+extern int hashdist;
+
+#endif /* _LINUX_BOOTMEM2_H */
Index: linux-2.6/mm/bootmem2.c
===================================================================
--- /dev/null
+++ linux-2.6/mm/bootmem2.c
@@ -0,0 +1,539 @@
+/*
+ * bootmem2
+ *
+ * A memory block oriented boot-time allocator.
+ *
+ * Copyright (C) 2008 Johannes Weiner
+ * Based on the original bootmem allocator, (C) 1999 Ingo Molnar
+ *
+ */
+
+#include <linux/kernel.h>
+#include <linux/init.h>
+#include <linux/pfn.h>
+#include <linux/io.h>
+
+#include <linux/bootmem2.h>
+
+#include "internal.h"
+
+/******** bootmem legacy */
+unsigned long min_low_pfn, max_low_pfn, max_pfn;
+#ifdef CONFIG_CRASH_DUMP
+unsigned long saved_max_pfn;
+#endif
+/******** !bootmem legacy */
+
+/* Global memory state */
+static void *bootmem_map __initdata;
+static unsigned long bootmem_min_pfn __initdata = ~0UL;
+static unsigned long bootmem_max_pfn __initdata;
+
+/* Allocator state */
+static int bootmem_functional __initdata;
+
+/* Registered memory blocks */
+static int bootmem_nr_blocks __initdata;
+
+/* Block sizes */
+static unsigned long bootmem_block_pages[NR_NODE_MEMBLKS] __initdata;
+
+/* Block offsets within bootmem_map */
+static unsigned long bootmem_block_offsets[NR_NODE_MEMBLKS] __initdata;
+
+/* Last allocation ending address on each block */
+static unsigned long bootmem_block_last[NR_NODE_MEMBLKS] __initdata;
+
+/*
+ * bootmem_register_block - register a memory block to bootmem
+ * @nid: id of the memory block
+ * @start: first pfn on the block
+ * @end: first pfn after the block
+ *
+ * This function must not be called anymore if the allocator
+ * is already up and running (bootmem_setup() has been called).
+ */
+void __init bootmem_register_block(int bid, unsigned long start,
+				unsigned long end)
+{
+	BUG_ON(bootmem_functional);
+
+	if (start < bootmem_min_pfn)
+		bootmem_min_pfn = start;
+	if (end > bootmem_max_pfn)
+		bootmem_max_pfn = end;
+
+	bootmem_block_offsets[bid] = start;
+	bootmem_block_pages[bid] = end - start;
+	bootmem_nr_blocks++;
+}
+
+static unsigned long __init bootmem_map_bytes(void)
+{
+	unsigned long bytes;
+
+	bytes = (bootmem_max_pfn - bootmem_min_pfn + 7) / 8;
+
+	/*
+	 * The alignment is needed to operate on
+	 * full wordsize vectors in bootmem_release_block().
+	 */
+	return ALIGN(bytes, sizeof(long));
+}
+
+/*
+ * bootmem_map_pages - pages needed to hold the bitmap
+ */
+unsigned long __init bootmem_map_pages(void)
+{
+	unsigned long bytes;
+
+	bytes = PAGE_ALIGN(bootmem_map_bytes());
+	return bytes / PAGE_SIZE;
+}
+
+/*
+ * bootmem_setup - activate the bootmem allocator
+ * @map: pfn where bitmap should be placed
+ *
+ * The bitmap must be at least bootmem_map_pages() big.
+ *
+ * After a call to this function, the bootmem allocator
+ * is enabled and no further blocks must be registered.
+ */
+void __init bootmem_setup(unsigned long mapstart)
+{
+	bootmem_map = phys_to_virt(PFN_PHYS(mapstart));
+	memset(bootmem_map, 0xff, bootmem_map_bytes());
+	bootmem_functional = 1;
+
+	printk(KERN_INFO "bootmem: %lu pages on %d block(s) - map @ pfn %lx\n",
+		bootmem_max_pfn - bootmem_min_pfn, bootmem_nr_blocks,
+		mapstart);
+
+	/* XXX: bootmem legacy */
+	min_low_pfn = mapstart;
+	max_low_pfn = bootmem_max_pfn;
+}
+
+/*
+ * bootmem_release_block - release a memory block from the allocator
+ * @bid: id of the block to be released
+ *
+ * All unreserved memory of the block @bid will be released
+ * to the buddy allocator.  If it was the last block registered
+ * to bootmem, the bitmap will be released too.
+ *
+ * After a call to this function, the bootmem allocator is
+ * disabled.
+ *
+ * The number of released pages is returned.
+ *
+ */
+unsigned long __init bootmem_release_block(int bid)
+{
+	int aligned;
+	unsigned long start, end, count = 0;
+
+	/* XXX */
+#ifdef CONFIG_MEMORY_HOTPLUG_SPARSE
+#ifndef CONFIG_SPARSEMEM_VMEMMAP
+	/* register_page_bootmem_info_node() */
+#error beat me
+#endif
+#endif
+
+	bootmem_functional = 0;
+	BUG_ON(!bootmem_nr_blocks);
+
+	start = bootmem_block_offsets[bid];
+	end = start + bootmem_block_pages[bid];
+
+	/*
+	 * If the starting pfn is aligned to the machines
+	 * wordsize, we might be able to release pages in
+	 * orders of that size.
+	 */
+	aligned = !(start & (BITS_PER_LONG - 1));
+
+	while (start < end) {
+		unsigned long pfn = start;
+		unsigned long *map = bootmem_map;
+		unsigned long vec = ~map[start / BITS_PER_LONG];
+
+		/*
+		 * Release wordsize pages at once to the buddy allocator
+		 * if we are properly aligned, the full vector is
+		 * unreserved and the block would not go beyond the end
+		 * of this block's memory.
+		 */
+		if (aligned && vec == ~0UL && start + BITS_PER_LONG < end) {
+			int order = ilog2(BITS_PER_LONG);
+
+			__free_pages_bootmem(pfn_to_page(pfn), order);
+			count += BITS_PER_LONG;
+		/*
+		 * Bad luck. If there are still unreserved pages in the
+		 * vector, free them one by one.
+		 */
+		} else {
+			while (vec && pfn < end) {
+				if (vec & 1) {
+					struct page *page = pfn_to_page(pfn);
+
+					__free_pages_bootmem(page, 0);
+					count++;
+				}
+				pfn++;
+				vec >>= 1;
+			}
+		}
+		start += BITS_PER_LONG;
+	}
+
+	/* This was the last block, drop the bitmap too */
+	if (!--bootmem_nr_blocks) {
+		unsigned long pages = bootmem_map_pages();
+		struct page *page = virt_to_page(bootmem_map);
+
+		count += pages;
+		while (pages--)
+			__free_pages_bootmem(page++, 0);
+	}
+
+	printk(KERN_INFO "bootmem: %lu pages released on block %i\n",
+		count, bid);
+
+	return count;
+}
+
+/*
+ * bootmem_release_node - release a node from the allocator
+ * @nid: id of the node to be released
+ *
+ * All unreserved memory of the node @nid will be released
+ * to the buddy allocator.  If it was the last node registered
+ * to bootmem, the bitmap will be released too.
+ *
+ * After a call to this function, the bootmem allocator is
+ * disabled.
+ *
+ * The number of released pages is returned.
+ */
+unsigned long __init bootmem_release_node(int nid)
+{
+	int i;
+	unsigned long count = 0;
+
+	for (i = 0; i < NR_MEMBLKS_PER_NODE; i++) {
+		int bid = bootmem_node_block(nid) + i;
+
+		count += bootmem_release_block(bid);
+	}
+
+	return count;
+}
+
+static void __init check_bootmem_parms(unsigned long start, unsigned long end)
+{
+	BUG_ON(!bootmem_functional);
+
+	if (start < bootmem_min_pfn || end > bootmem_max_pfn) {
+		printk(KERN_ERR "bootmem request out of range: %lx-%lx, "
+			"usable: %lx-%lx\n", start, end, bootmem_min_pfn,
+			bootmem_max_pfn);
+		BUG();
+	}
+}
+
+static void __init __bootmem_free(unsigned long start, unsigned long end)
+{
+	unsigned long pfn;
+
+	check_bootmem_parms(start, end);
+	for (pfn = start; pfn < end; pfn++)
+		if (!test_and_clear_bit(pfn, bootmem_map)) {
+			printk(KERN_ERR "bootmem: double free of pfn %lx\n",
+				pfn);
+			BUG();
+		}
+}
+
+static int __init __bootmem_reserve(unsigned long start, unsigned long end,
+				int exclusive)
+{
+	unsigned long pfn;
+
+	check_bootmem_parms(start, end);
+	for (pfn = start; pfn < end; pfn++)
+		if (test_and_set_bit(pfn, bootmem_map))
+			if (exclusive) {
+				__bootmem_free(start, pfn);
+				return -EBUSY;
+			}
+
+	return 0;
+}
+
+/*
+ * bootmem_free - mark a memory region as free
+ * @addr: starting address
+ * @size: size of region in bytes
+ *
+ * Only pages completely within the bounds of the region
+ * are marked free.
+ */
+void __init bootmem_free(unsigned long addr, unsigned long size)
+{
+	unsigned long start, end;
+
+	start = PFN_UP(addr);
+	end = PFN_DOWN(addr + size);
+	__bootmem_free(start, end);
+}
+
+/*
+ * bootmem_reserve - mark a memory region as reserved
+ * @addr: starting address
+ * @size: size of region in bytes
+ * @exclusive: reserve region exclusively
+ *
+ * All pages (even incomplete ones) within the bounds of the region
+ * are marked reserved.
+ *
+ * If @exclusive is !0, this function returns -EBUSY if the
+ * region or parts of it are already reserved.
+ */
+int __init bootmem_reserve(unsigned long addr, unsigned long size,
+			int exclusive)
+{
+	unsigned long start, end;
+
+	start = PFN_DOWN(addr);
+	end = PFN_UP(addr + size);
+	return __bootmem_reserve(start, end, exclusive);
+}
+
+static void * __init __bootmem_alloc_block(int bid, int align,
+				unsigned long start_pfn, unsigned long bytes)
+{
+	void *region;
+	int merge = 0;
+	unsigned long last_end, last_pfn, new_start, new_end;
+
+	/* XXX: Find a more appropriate slot */
+	if (bid == -1)
+		bid = 0;
+
+	/*
+	 * If the allocation is subsequent to a prior allocation that did not
+	 * use all of its last page, the new block might use it or even fit
+	 * completely into it.
+	 */
+	last_end = bootmem_block_last[bid];
+	last_pfn = PFN_DOWN(last_end);
+
+	if (last_pfn + 1 == start_pfn)
+		new_start = ALIGN(last_end, align);
+	else
+		new_start = PFN_PHYS(start_pfn);
+
+	merge = PFN_DOWN(new_start) < start_pfn;
+
+	new_end = new_start + bytes;
+	bootmem_block_last[bid] = new_end;
+
+	/*
+	 * Since we checked the area in advance, a failed reservation
+	 * is clearly a BUG.
+	 */
+	if (__bootmem_reserve(PFN_DOWN(new_start) + merge, PFN_UP(new_end), 1))
+		BUG();
+
+	region = phys_to_virt(new_start);
+	memset(region, 0, bytes);
+	return region;
+}
+
+/*
+ * bootmem_alloc_block - allocate a memory region
+ * @bid: memory block to allocate from
+ * @size: size of the region in bytes
+ * @align: alignment of the region
+ * @goal: preferred starting address of the region
+ * @limit: first address after the region
+ */
+void * __init bootmem_alloc_block(int bid, unsigned long size,
+				unsigned long align, unsigned long goal,
+				unsigned long limit)
+{
+	unsigned long min_idx, max_idx, sidx, step;
+
+	/*
+	 * If a block was specified, crossing its boundaries is
+	 * not allowed.  Otherwise we are agnostic to block
+	 * sizes and work with the whole range of pages available.
+	 */
+	if (bid == -1) {
+		min_idx = bootmem_min_pfn;
+		max_idx = bootmem_max_pfn;
+	} else {
+		min_idx = bootmem_block_offsets[bid];
+		max_idx = min_idx + bootmem_block_pages[bid];
+	}
+
+	BUG_ON(align & (align - 1));
+	BUG_ON(limit && goal + size > limit);
+
+	if (limit && max_idx > limit)
+		max_idx = limit;
+
+	if (!(max_idx - min_idx))
+		return NULL;
+
+	goal >>= PAGE_SHIFT;
+	limit >>= PAGE_SHIFT;
+
+	/*
+	 * We walk the bitmap in page steps, so align does only have an
+	 * impact for the block searching if it's bigger than the
+	 * page size.  It must be preserved, however, for the allocation
+	 * merging at a finer granularity than whole pages.
+	 */
+	step = max_t(unsigned long, align >> PAGE_SHIFT, 1);
+
+	if (goal && goal < max_idx)
+		sidx = ALIGN(goal, step);
+	else
+		sidx = ALIGN(min_idx, step);
+
+restart:
+	while (1) {
+		unsigned long eidx, idx;
+
+		sidx = find_next_zero_bit(bootmem_map, max_idx, sidx);
+		sidx = ALIGN(sidx, step);
+		eidx = sidx + PFN_UP(size);
+
+		if (sidx > max_idx)
+			break;
+		if (eidx > max_idx)
+			break;
+
+		/*
+		 * XXX: The last page may be dropped due to merging
+		 * but it is required to be free!
+		 */
+		for (idx = sidx; idx < eidx; idx++)
+			if (test_bit(idx, bootmem_map)) {
+				sidx = ALIGN(idx, step);
+				if (sidx == idx)
+					sidx += step;
+				continue;
+			}
+
+		return __bootmem_alloc_block(bid, align, sidx, size);
+	}
+
+	if (goal) {
+		sidx = ALIGN(min_idx, step);
+		goal = 0;
+		goto restart;
+	}
+
+	return NULL;
+}
+
+/*
+ * bootmem_alloc_node - allocate a memory region
+ * @nid: id of the node to allocate from
+ * @size: size of the region in bytes
+ * @align: alignment of the region
+ * @goal: preferred starting address of the region
+ * @limit: first address after the region
+ */
+void * __init bootmem_alloc_node(int nid, unsigned long size,
+				unsigned long align, unsigned long goal,
+				unsigned long limit)
+{
+	int i, goal_block;
+	unsigned long goal_pfn;
+
+	if (nid == -1)
+		return bootmem_alloc_block(nid, size, align, goal, limit);
+
+	/*
+	 * Find a block on the requested node that is able to
+	 * satisfy the goal.  Fall back if it's impossible.
+	 */
+	goal_block = -1;
+	goal_pfn = PFN_DOWN(goal);
+
+	for (i = 0; i < NR_MEMBLKS_PER_NODE; i++) {
+		int bid = bootmem_node_block(nid) + i;
+		unsigned long start = bootmem_block_offsets[bid];
+		unsigned long end = start + bootmem_block_pages[bid];
+
+		if (!(end - start))
+			continue;
+
+		if (goal_pfn >= start && goal_pfn < end) {
+			goal_block = i;
+			break;
+		}
+	}
+
+	if (goal_block == -1)
+		goal = goal_block = 0;
+
+	for (i = goal_block; i < NR_MEMBLKS_PER_NODE; i++) {
+		void *region;
+		int bid = bootmem_node_block(nid) + i;
+
+		region = bootmem_alloc_block(bid, size, align, goal, limit);
+		if (region)
+			return region;
+	}
+
+	return NULL;
+}
+
+#ifndef ARCH_LOW_ADDRESS_LIMIT
+#define ARCH_LOW_ADDRESS_LIMIT	0xffffffffUL
+#endif
+
+void * __init bootmem_alloc_low_node(int nid, unsigned long size,
+				unsigned long align, unsigned long goal)
+{
+	return bootmem_alloc_node(nid, size, align, goal,
+				ARCH_LOW_ADDRESS_LIMIT);
+}
+
+#ifdef CONFIG_SPARSEMEM
+void * __init bootmem_alloc_section(unsigned long size, unsigned long sec_nr)
+{
+	int nid;
+	void *region;
+	unsigned long goal, limit, start, end;
+
+	start = section_nr_to_pfn(sec_nr);
+	goal = PFN_PHYS(start);
+	limit = PFN_PHYS(section_nr_to_pfn(sec_nr + 1));
+	nid = early_pfn_to_nid(start);
+
+	region = bootmem_alloc_node(nid, size, SMP_CACHE_BYTES, goal, limit);
+	if (!region)
+		return NULL;
+
+	start = pfn_to_section_nr(PFN_DOWN(__pa(region)));
+	end = pfn_to_section_nr(PFN_DOWN(__pa(region) + size));
+	if (start != sec_nr || end != sec_nr) {
+		printk(KERN_WARNING "bootmem_alloc_section(%lu, %lu)\n",
+			section_nr);
+		bootmem_free(__pa(region), size);
+		region = NULL;
+	}
+
+	return region;
+}
+#endif
Index: linux-2.6/mm/Kconfig
===================================================================
--- linux-2.6.orig/mm/Kconfig
+++ linux-2.6/mm/Kconfig
@@ -205,3 +205,6 @@ config NR_QUICK
 config VIRT_TO_BUS
 	def_bool y
 	depends on !ARCH_NO_VIRT_TO_BUS
+
+config HAVE_BOOTMEM2
+	def_bool n
Index: linux-2.6/mm/Makefile
===================================================================
--- linux-2.6.orig/mm/Makefile
+++ linux-2.6/mm/Makefile
@@ -7,7 +7,7 @@ mmu-$(CONFIG_MMU)	:= fremap.o highmem.o 
 			   mlock.o mmap.o mprotect.o mremap.o msync.o rmap.o \
 			   vmalloc.o
 
-obj-y			:= bootmem.o filemap.o mempool.o oom_kill.o fadvise.o \
+obj-y			:= filemap.o mempool.o oom_kill.o fadvise.o \
 			   maccess.o page_alloc.o page-writeback.o pdflush.o \
 			   readahead.o swap.o truncate.o vmscan.o \
 			   prio_tree.o util.o mmzone.o vmstat.o backing-dev.o \
@@ -34,3 +34,8 @@ obj-$(CONFIG_SMP) += allocpercpu.o
 obj-$(CONFIG_QUICKLIST) += quicklist.o
 obj-$(CONFIG_CGROUP_MEM_RES_CTLR) += memcontrol.o
 
+ifeq ($(CONFIG_HAVE_BOOTMEM2),y)
+obj-y += bootmem2.o
+else
+obj-y += bootmem.o
+endif
Index: linux-2.6/include/linux/bootmem.h
===================================================================
--- linux-2.6.orig/include/linux/bootmem.h
+++ linux-2.6/include/linux/bootmem.h
@@ -4,6 +4,10 @@
 #ifndef _LINUX_BOOTMEM_H
 #define _LINUX_BOOTMEM_H
 
+#ifdef CONFIG_HAVE_BOOTMEM2
+#include <linux/bootmem2.h>
+#else
+
 #include <linux/mmzone.h>
 #include <asm/dma.h>
 
@@ -146,5 +150,5 @@ extern void *alloc_large_system_hash(con
 #endif
 extern int hashdist;		/* Distribute hashes across NUMA nodes? */
 
-
+#endif /* !CONFIG_HAVE_BOOTMEM2 */
 #endif /* _LINUX_BOOTMEM_H */
Index: linux-2.6/mm/page_alloc.c
===================================================================
--- linux-2.6.orig/mm/page_alloc.c
+++ linux-2.6/mm/page_alloc.c
@@ -3993,8 +3993,12 @@ void __init set_dma_reserve(unsigned lon
 }
 
 #ifndef CONFIG_NEED_MULTIPLE_NODES
+#ifndef CONFIG_HAVE_BOOTMEM2
 static bootmem_data_t contig_bootmem_data;
 struct pglist_data contig_page_data = { .bdata = &contig_bootmem_data };
+#else
+struct pglist_data contig_page_data;
+#endif
 
 EXPORT_SYMBOL(contig_page_data);
 #endif

-- 

--
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:"dont@kvack.org"> email@kvack.org </a>

[rfc][patch 3/3] x86: Use bootmem2 on x86_32

[Johannes Weiner]

[-- Attachment #1: bootmem2-migrate-x86_32.patch --]
[-- Type: text/plain, Size: 1775 bytes --]

Straight-forward migration to use bootmem2 on the author's computer.

Signed-off-by: Johannes Weiner <hannes@saeurebad.de>
---

Index: linux-2.6/arch/x86/kernel/setup_32.c
===================================================================
--- linux-2.6.orig/arch/x86/kernel/setup_32.c
+++ linux-2.6/arch/x86/kernel/setup_32.c
@@ -641,7 +641,9 @@ void __init setup_bootmem_allocator(void
 	/*
 	 * Initialize the boot-time allocator (with low memory only):
 	 */
-	bootmap_size = init_bootmem(min_low_pfn, max_low_pfn);
+	bootmem_register(0, max_low_pfn);
+	bootmap_size = bootmem_map_pages() << PAGE_SHIFT;
+	bootmem_setup(min_low_pfn);
 
 	register_bootmem_low_pages(max_low_pfn);
 
Index: linux-2.6/arch/x86/mm/init_32.c
===================================================================
--- linux-2.6.orig/arch/x86/mm/init_32.c
+++ linux-2.6/arch/x86/mm/init_32.c
@@ -585,7 +585,7 @@ void __init mem_init(void)
 	}
 #endif
 	/* this will put all low memory onto the freelists */
-	totalram_pages += free_all_bootmem();
+	totalram_pages += bootmem_release();
 
 	reservedpages = 0;
 	for (tmp = 0; tmp < max_low_pfn; tmp++)
Index: linux-2.6/arch/x86/Kconfig
===================================================================
--- linux-2.6.orig/arch/x86/Kconfig
+++ linux-2.6/arch/x86/Kconfig
@@ -24,6 +24,7 @@ config X86
 	select HAVE_KRETPROBES
 	select HAVE_KVM if ((X86_32 && !X86_VOYAGER && !X86_VISWS && !X86_NUMAQ) || X86_64)
 	select HAVE_ARCH_KGDB if !X86_VOYAGER
+	select HAVE_BOOTMEM2 if X86_32
 
 config DEFCONFIG_LIST
 	string

-- 

--
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:"dont@kvack.org"> email@kvack.org </a>

Re: [rfc][patch 0/3] bootmem2: a memory block-oriented boot time allocator

[Johannes Weiner]

Hi,

Johannes Weiner <hannes@saeurebad.de> writes:

> The problem is that memory nodes are not anymore garuanteed to be
> linear on certain configurations, they may overlap each other and a
> node might span page ranges that are not physically residing on it.
>
> Note that this is in no way theoretical only, bootmem suffers from
> this fact right now: A pfn range has to be operated on on every node
> that holds it (because a PFN is not unique anymore) and bootmem can
> not garuantee that the memory allocated from a specific node actually
> resides on that node.
>
> For example:
>
> 	node 0: 0-2G, 4-6G
> 	node 1: 2-4G, 6-8G
>
> Bootmem currently sees the 2-4G range twice (and has to operate on
> both node's bitmaps) and if memory is allocated on node 1, it may
> return memory that is between the 2-4G range and actually resides on
> node 0.

Uh, mixup.  The memory resides on node 1 but may get allocated from
node 0.

	Hannes

--
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:"dont@kvack.org"> email@kvack.org </a>

Re: [rfc][patch 0/3] bootmem2: a memory block-oriented boot time allocator

[Linus Torvalds]

On Mon, 5 May 2008, Johannes Weiner wrote:
> 
> here is a bootmem allocator replacement that uses one bitmap for all
> available pages and works with a model of contiguous memory blocks
> that reside on nodes instead of nodes only as the current allocator
> does.

Won't this have problems with huge non-contiguous areas?

Some setups have traditionally had node memory separated in physical space 
by the high bits of the memory address, and using a single bitmap for such 
things would potentially be basically impossible - even with a single bit 
per page, the "span" of possible pages is potentially just too high, even 
if the nodes themselves don't have tons of memory, because the memory is 
just very spread out - and allocating the initial bitmap may not work 
reliably.

Now, admittedly I don't know if we even support that kind of thing or if 
people really do things that way any more, so maybe it's not an issue.

		Linus

--
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:"dont@kvack.org"> email@kvack.org </a>

Re: [rfc][patch 0/3] bootmem2: a memory block-oriented boot time allocator

[Robin Holt]

On Mon, May 05, 2008 at 08:23:34AM -0700, Linus Torvalds wrote:
> 
> 
> On Mon, 5 May 2008, Johannes Weiner wrote:
> > 
> > here is a bootmem allocator replacement that uses one bitmap for all
> > available pages and works with a model of contiguous memory blocks
> > that reside on nodes instead of nodes only as the current allocator
> > does.
> 
> Won't this have problems with huge non-contiguous areas?
> 
> Some setups have traditionally had node memory separated in physical space 
> by the high bits of the memory address, and using a single bitmap for such 
> things would potentially be basically impossible - even with a single bit 
> per page, the "span" of possible pages is potentially just too high, even 
> if the nodes themselves don't have tons of memory, because the memory is 
> just very spread out - and allocating the initial bitmap may not work 
> reliably.
> 
> Now, admittedly I don't know if we even support that kind of thing or if 
> people really do things that way any more, so maybe it's not an issue.

SGI sn2 architecture does.  Each DIMM bank is allocated a 16GB range
of physical addresses.  There are up to four banks per node.  The node
number is stuck into higher portions of the address, giving a gap between
nodes of 256GB.  With a potential of 1024 nodes, you would have a very
large array.

Additionally on our upcoming UV systems, there will potentially be a
hole between the bulk of memory and a small amount addressable at the
high end of the address range (slightly short of 16TB) with the typical
gap being on the order of 15TB.

Thanks,
Robin Holt

--
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:"dont@kvack.org"> email@kvack.org </a>

Re: [rfc][patch 0/3] bootmem2: a memory block-oriented boot time allocator

[Johannes Weiner]

Hi,

Robin Holt <holt@sgi.com> writes:

> On Mon, May 05, 2008 at 08:23:34AM -0700, Linus Torvalds wrote:
>> 
>> 
>> On Mon, 5 May 2008, Johannes Weiner wrote:
>> > 
>> > here is a bootmem allocator replacement that uses one bitmap for all
>> > available pages and works with a model of contiguous memory blocks
>> > that reside on nodes instead of nodes only as the current allocator
>> > does.
>> 
>> Won't this have problems with huge non-contiguous areas?
>> 
>> Some setups have traditionally had node memory separated in physical space 
>> by the high bits of the memory address, and using a single bitmap for such 
>> things would potentially be basically impossible - even with a single bit 
>> per page, the "span" of possible pages is potentially just too high, even 
>> if the nodes themselves don't have tons of memory, because the memory is 
>> just very spread out - and allocating the initial bitmap may not work 
>> reliably.
>> 
>> Now, admittedly I don't know if we even support that kind of thing or if 
>> people really do things that way any more, so maybe it's not an issue.
>
> SGI sn2 architecture does.  Each DIMM bank is allocated a 16GB range
> of physical addresses.  There are up to four banks per node.  The node
> number is stuck into higher portions of the address, giving a gap between
> nodes of 256GB.  With a potential of 1024 nodes, you would have a very
> large array.
>
> Additionally on our upcoming UV systems, there will potentially be a
> hole between the bulk of memory and a small amount addressable at the
> high end of the address range (slightly short of 16TB) with the typical
> gap being on the order of 15TB.

Okay, that defeats the single-bitmap approach completely.

Thanks for clarifying.

	Hannes

--
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:"dont@kvack.org"> email@kvack.org </a>

Re: [rfc][patch 0/3] bootmem2: a memory block-oriented boot time allocator

[Andi Kleen]

> (because a PFN is not unique anymore)

That doesn't make sense. If a PFN is not uniquely mapping to a single
memory page anymore the VM and lots of other code in the kernel will
just not work. And each memory page can be only in a single node.

-Andi

--
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:"dont@kvack.org"> email@kvack.org </a>

Re: [rfc][patch 0/3] bootmem2: a memory block-oriented boot time allocator

[Johannes Weiner]

Hi,

Andi Kleen <andi@firstfloor.org> writes:

>> (because a PFN is not unique anymore)
>
> That doesn't make sense. If a PFN is not uniquely mapping to a single
> memory page anymore the VM and lots of other code in the kernel will
> just not work. And each memory page can be only in a single node.

I meant it is not unique to the bootmem allocator because two bitmaps
might partially represent the same page range.

	Hannes

--
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:"dont@kvack.org"> email@kvack.org </a>

[RFC no patch yet] bootmem2: Another try

[Johannes Weiner]

Hi,

my idea is now as follows:

Bootmem2 is block-oriented where a block represents a contiguous range
of physical memory.  Every block has a bitmap that keeps track of the
pages on it.

On top of this block interface, bootmem2 implements the node model
where a node can provide one or more memory blocks.

On configurations with multiple blocks per node, the arch code has to
register each block on its own.

free_bootmem and reserve_bootmem require that the requested range is
contiguous but they might go across node boundaries (two blocks on two
nodes can be contiguous).  For example:

node 0: block 0 = 0-2G, block 1 = 4-6G
node 1: block 2 = 2-4G, block 3 = 6-8G

free_bootmem(1.5G, 3G) is valid here, the range spans two nodes and two
blocks but is contiguous.

free_bootmem_node and reserve_bootmem_node are more strict, the ranges
have to be completely within one block of the specified node (two
blocks on one node are never contiguous).

alloc_bootmem_node tries to get memory between goal and limit from a
specific node and falls back to any free memory range on that node on
failure.

alloc_bootmem tries to get memory from between goal and limit and
falls back to any free memory range in the system on failure.

What do you say?

	Hannes

--
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:"dont@kvack.org"> email@kvack.org </a>

Re: [RFC no patch yet] bootmem2: Another try

[Linus Torvalds]

On Wed, 7 May 2008, Johannes Weiner wrote:
> 
> Bootmem2 is block-oriented where a block represents a contiguous range
> of physical memory.  Every block has a bitmap that keeps track of the
> pages on it.

Yes, that one sounds fairly sane.

		Linus

--
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:"dont@kvack.org"> email@kvack.org </a>