bootmem2: a memory block-oriented boot time allocator

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

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.

---

Index: 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 [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>

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.

---

Index: 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/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
===================================================================
@@ -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
===================================================================
@@ -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
===================================================================
@@ -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 [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>

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

---

Index: 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
===================================================================
@@ -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
===================================================================
@@ -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 [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>

Hi,

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

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

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

Hi,

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

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

Hi,

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

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

Yes, that one sounds fairly sane.

Linus

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