NUMA emulation update

CONFIG_NUMA_EMU - new and improved!

These patches update the current x86_64 NUMA emulation code by adding support for dividing real NUMA nodes into several smaller emulated nodes. The good old x86_64 implementation of NUMA emulation written by Andi Kleen has worked well since 2.6.9, but it lacks support for dividing multiple real NUMA nodes.

The patches also break out the NUMA emulation code into some simple generic functions that could be used by several platforms. Only x86_64 gets modified by this patch set, but I've planned to convert my i386 NUMA emulation code to use these generic functions later on. I know that some kind of NUMA emulation code also exists for ia64, and maybe it is possible to build that code on top of the generic functions too.

Patches on top of 2.6.14-mm1:

[PATCH 01/05] NUMA: Generic code
[PATCH 02/05] x86_64: NUMA cleanup
[PATCH 03/05] x86_64: NUMA emulation
[PATCH 04/05] x86_64: NUMA without SMP
[PATCH 05/05] NUMA: find_next_best_node fix

About NUMA emulation:

NUMA emulation could be used to provide coarse-grained memory resource control using CPUSETS. Another use is as a test environment for NUMA memory code or CPUSETS using an system emulator such as QEMU.

Feedback is very appreciated.

Thanks,

/ magnus

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

Generic CONFIG_NUMA_EMU code.

This patch adds generic NUMA emulation code to the kernel. The code provides the architectures with functions that calculate the size of emulated nodes, together with configuration stuff such as Kconfig and kernel command line code.

---

 include/linux/numa.h  |   25 +++++++++-
 mm/Kconfig            |   17 +++++++
 mm/Makefile           |    1
 mm/numa_emu.c         |  118 ++++++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 159 insertions(+), 2 deletions(-)

@@ -2,15 +2,36 @@
 #define _LINUX_NUMA_H
 
 #include <linux/config.h>
+#include <linux/init.h>
 
 #ifndef CONFIG_FLATMEM
 #include <asm/numnodes.h>
 #endif
 
-#ifndef NODES_SHIFT
-#define NODES_SHIFT     0
+#ifndef NODES_SHIFT_HW
+#define NODES_SHIFT_HW     0
 #endif
 
+#ifdef CONFIG_NUMA_EMU
+#define NODES_SHIFT_EMU CONFIG_NUMA_EMU_SHIFT
+/* in mm/numa_emu.c */
+void numa_emu_setup(char *opt);
+int __init numa_emu_new(int nid, 
+			unsigned long real_start, unsigned long real_end, 
+			unsigned long *emu_start, unsigned long *emu_end);
+int __init numa_emu_shrink(int nid, int new_nodes, 
+			   unsigned long real_start, unsigned long real_end,
+			   unsigned long *emu_start, unsigned long *emu_end);
+/* arch-specific */
+void __init numa_emu_setup_nid(int real_nid);
+#else
+#define NODES_SHIFT_EMU 0
+static inline void numa_emu_setup_nid(int real_nid) {}
+static inline void numa_emu_setup(char *opt) {}
+#endif
+
+#define NODES_SHIFT     (NODES_SHIFT_HW + NODES_SHIFT_EMU)
+
 #define MAX_NUMNODES    (1 << NODES_SHIFT)
 
 #endif /* _LINUX_NUMA_H */

@@ -77,6 +77,23 @@ config FLAT_NODE_MEM_MAP
 	def_bool y
 	depends on !SPARSEMEM
 
+config NUMA_EMU
+	bool "NUMA Memory Nodes Emulation"
+	select NUMA
+	depends on ARCH_NUMA_EMU_ENABLE
+	default n
+	help
+	  Enable NUMA emulation. Each node will be split into several virtual
+	  nodes when booted with "numa=fake=N", where N is the number of nodes.
+
+config NUMA_EMU_SHIFT
+	int "Maximum shift number of emulated nodes, per real node (1-8)"
+	range 1 8
+	depends on NUMA_EMU
+	default "3"
+	help
+	  This value controls the maximum number of emulated NUMA nodes.
+
 #
 # Both the NUMA code and DISCONTIGMEM use arrays of pg_data_t's
 # to represent different areas of memory.  This variable allows

@@ -16,6 +16,7 @@ obj-$(CONFIG_SWAP)	+= page_io.o swap_sta
 obj-$(CONFIG_SWAP_PREFETCH) += swap_prefetch.o
 obj-$(CONFIG_HUGETLBFS)	+= hugetlb.o
 obj-$(CONFIG_NUMA) 	+= mempolicy.o
+obj-$(CONFIG_NUMA_EMU) 	+= numa_emu.o
 obj-$(CONFIG_SPARSEMEM)	+= sparse.o
 obj-$(CONFIG_SHMEM) += shmem.o
 obj-$(CONFIG_TINY_SHMEM) += tiny-shmem.o

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

IMHO making it generic and bloated like this is total overkill for this simple debugginghack. I think it is better to keep
it simple and hiden it in a architecture specific dark corners, not expose it like this.

I think the patch shouldn't be applied.

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

My plan with breaking out the NUMA emulation code was to merge my i386 stuff with the x86_64 code, but as you say - it might be overkill.

What do you think about the fact that real NUMA nodes now can be divided into several smaller nodes?

/ magnus

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

Is it really needed? I never needed it. Normally numa emulation is just for basic numa testing, and for that just an independent split is good enough.

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

For testing, your NUMA emulation code is perfect IMO. But for memory resource control your NUMA emulation code may be too simple.

With my patch, CONFIG_NUMA_EMU provides a way to partition a machine into several smaller nodes, regardless if the machine is using NUMA or not.

This NUMA emulation code together with CPUSETS could be seen as a simple alternative to the memory resource control provided by CKRM.

/ magnus

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

I believe Werner tried to use it at some point for that and it just didn't work very well. So it doesn't seem to be very useful for that usecase.

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

Sorry, but which one did not work very well? CKRM memory controller or NUMA emulation + CPUSETS?

Thanks,

/ magnus

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

Using simulated nodes for controlling memory.

-Andi

We tried to partition our memory using the NUMA emulation, such that timing-critical processes would allocate from one node, while all the rest of the system would allocate from the other node.

The idea was that the timing-critical processes, with a fairly "calm" allocation behaviour (read file data into the page cache, then evict it again), would never or almost never trigger memory reclaim this way, and thus have better worst-case latency.

Unfortunately, our benchmarks didn't show any improvements in latency. In fact, the results were slightly worse, perhaps because of processes on the "regular" node holding shared resources while in memory reclaim.

I'm not entirely sure why this didn't work better. At least in theory, it should have.

We did this in the ABISS project, about one year ago in response to quite nasty reclaim latency suddenly appearing in an earlier 2.6 kernel. When we asked various MM developers, but none of them was aware of any change that would make reclaims all of a sudden very intrusive, and they attributed it to the "butterfly effect". After a while (i.e., in later kernels), the butterflies must have chosen a different victim, and the latency got better on its own.

So, in the end, we didn't need that NUMA hack to control reclaims. But if they should rear their ugly heads again, it may be worth having a second look.

- Werner

  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina     [email protected] /
/_http://www.almesberger.net/____________________________________________/

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

Rearrange the x86_64 NUMA code to make room for the new NUMA emulation code.

This patch rearranges the code and cleans it up a bit by moving duplicated common code from srat.c and k8topology.c into numa.c.

---

 arch/x86_64/kernel/setup.c  |    7 ------
 arch/x86_64/mm/k8topology.c |   13 -----------
 arch/x86_64/mm/numa.c       |   51 +++++++++++++++++++++++++++++++-------------
 arch/x86_64/mm/srat.c       |   14 +-----------
 include/asm-x86_64/mmzone.h |    1
 5 files changed, 41 insertions(+), 45 deletions(-)

@@ -581,13 +581,6 @@ void __init setup_arch(char **cmdline_p)
 	acpi_boot_table_init();
 #endif
 
-#ifdef CONFIG_ACPI_NUMA
-	/*
-	 * Parse SRAT to discover nodes.
-	 */
-	acpi_numa_init();
-#endif
-
 #ifdef CONFIG_NUMA
 	numa_initmem_init(0, end_pfn); 
 #else

@@ -43,7 +43,6 @@ static __init int find_northbridge(void)
 int __init k8_scan_nodes(unsigned long start, unsigned long end)
 { 
 	unsigned long prevbase;
-	struct node nodes[8];
 	int nodeid, i, nb; 
 	unsigned char nodeids[8];
 	int found = 0;

@@ -65,7 +64,6 @@ int __init k8_scan_nodes(unsigned long s
 
 	printk(KERN_INFO "Number of nodes %d\n", numnodes);
 
-	memset(&nodes,0,sizeof(nodes)); 
 	prevbase = 0;
 	for (i = 0; i < 8; i++) { 
 		unsigned long base,limit; 

@@ -155,22 +153,13 @@ int __init k8_scan_nodes(unsigned long s
 	if (!found)
 		return -1; 
 
-	memnode_shift = compute_hash_shift(nodes, numnodes);
-	if (memnode_shift < 0) { 
-		printk(KERN_ERR "No NUMA node hash function found. Contact maintainer\n"); 
-		return -1; 
-	} 
-	printk(KERN_INFO "Using node hash shift of %d\n", memnode_shift); 
-
 	for (i = 0; i < 8; i++) {
 		if (nodes[i].start != nodes[i].end) { 
 			nodeid = nodeids[i];
 			apicid_to_node[nodeid << dualcore] = i;
 			apicid_to_node[(nodeid << dualcore) + dualcore] = i;
-			setup_node_bootmem(i, nodes[i].start, nodes[i].end); 
+			node_set_online(i);
 		} 
 	}
-
-	numa_init_array();
 	return 0;
 } 

@@ -22,7 +22,6 @@ static struct acpi_table_slit *acpi_slit
 
 static nodemask_t nodes_parsed __initdata;
 static nodemask_t nodes_found __initdata;
-static struct node nodes[MAX_NUMNODES] __initdata;
 static __u8  pxm2node[256] = { [0 ... 255] = 0xff };
 
 static int node_to_pxm(int n);

@@ -182,26 +181,17 @@ int __init acpi_scan_nodes(unsigned long
 		cutoff_node(i, start, end);
 		if (nodes[i].start == nodes[i].end)
 			node_clear(i, nodes_parsed);
-	}
-
-	memnode_shift = compute_hash_shift(nodes, nodes_weight(nodes_parsed));
-	if (memnode_shift < 0) {
-		printk(KERN_ERR
-		     "SRAT: No NUMA node hash function found. Contact maintainer\n");
-		bad_srat();
-		return -1;
+		else
+			node_set_online(i);
 	}
 
 	/* Finally register nodes */
-	for_each_node_mask(i, nodes_parsed)
-		setup_node_bootmem(i, nodes[i].start, nodes[i].end);
 	for (i = 0; i < NR_CPUS; i++) { 
 		if (cpu_to_node[i] == NUMA_NO_NODE)
 			continue;
 		if (!node_isset(cpu_to_node[i], nodes_parsed))
 			numa_set_node(i, NUMA_NO_NODE);
 	}
-	numa_init_array();
 	return 0;
 }
 

@@ -17,6 +17,7 @@
 /* Simple perfect hash to map physical addresses to node numbers */
 extern int memnode_shift; 
 extern u8  memnodemap[NODEMAPSIZE]; 
+extern struct node nodes[MAX_NUMNODES] __initdata;
 
 extern struct pglist_data *node_data[];
 

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

Improve the x86_64 NUMA emulation code to use the generic NUMA emulation code.

This patch replaces the current x86_64 CONFIG_NUMA_EMU code with a more advanced implementation that uses the generic NUMA emulation code. The x86_64 NUMA emulation today only supports dividing of nodes on single node systems, but this implementation supports both single node systems and larger systems with multiple NUMA nodes. With the patch, each real NUMA node will be divided into several smaller nodes during boot if requested on the kernel command line.

---

 arch/x86_64/Kconfig           |   11 +--
 arch/x86_64/mm/numa.c         |  119 +++++++++++++++++++++---------------------
 include/asm-x86_64/numa.h     |    1
 include/asm-x86_64/numnodes.h |    6 +-
 4 files changed, 68 insertions(+), 69 deletions(-)

@@ -258,14 +258,6 @@ config X86_64_ACPI_NUMA
        help
 	 Enable ACPI SRAT based node topology detection.
 
-config NUMA_EMU
-	bool "NUMA emulation"
-	depends on NUMA
-	help
-	  Enable NUMA emulation. A flat machine will be split
-	  into virtual nodes when booted with "numa=fake=N", where N is the
-	  number of nodes. This is only useful for debugging.
-
 config ARCH_DISCONTIGMEM_ENABLE
        bool
        depends on NUMA

@@ -288,6 +280,9 @@ config ARCH_FLATMEM_ENABLE
 	def_bool y
 	depends on !NUMA
 
+config ARCH_NUMA_EMU_ENABLE
+	def_bool y
+
 source "mm/Kconfig"
 
 config HAVE_ARCH_EARLY_PFN_TO_NID

@@ -8,7 +8,6 @@ struct node { 
 	u64 start,end; 
 };
 
-extern int compute_hash_shift(struct node *nodes, int numnodes);
 extern int pxm_to_node(int nid);
 
 #define ZONE_ALIGN (1UL << (MAX_ORDER+PAGE_SHIFT))

@@ -3,10 +3,10 @@
 
 #include <linux/config.h>
 
-#ifdef CONFIG_NUMA
-#define NODES_SHIFT	6
+#if defined(CONFIG_K8_NUMA) || defined(CONFIG_ACPI_NUMA)
+#define NODES_SHIFT_HW	3
 #else
-#define NODES_SHIFT	0
+#define NODES_SHIFT_HW	0
 #endif
 
 #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>

Remove the SMP dependency from NUMA on x86_64.

This simple change is boot tested on real x86_64 NUMA hardware and in QEMU. Works with CONFIG_NUMA_EMU, CONFIG_K8_NUMA and CONFIG_ACPI_NUMA. This change has earlier been discussed with Andi Kleen and rejected, but it is included in this patch set for completeness.

---

 Kconfig |    1 -
 1 files changed, 1 deletion(-)

@@ -228,7 +228,6 @@ source "kernel/Kconfig.preempt"
 
 config NUMA
        bool "Non Uniform Memory Access (NUMA) Support"
-       depends on SMP
        help
 	 Enable NUMA (Non Uniform Memory Access) support. The kernel 
 	 will try to allocate memory used by a CPU on the local memory 

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

Fix find_next_best_node() to support node masks with holes.

find_next_best_node() does currently not support node masks with holes. For instance, a node mask with nodes 1, 8 and 16 online will not work correctly. The use of % num_online_nodes() in the code below hints that only a single contiguous range of nodes is supported without this patch.

---

 page_alloc.c |   25 +++++++++++++++----------
 1 files changed, 15 insertions(+), 10 deletions(-)

@@ -1554,26 +1554,31 @@ static int __initdata node_load[MAX_NUMN
  */
 static int __init find_next_best_node(int node, nodemask_t *used_node_mask)
 {
-	int i, n, val;
+	int n, val;
 	int min_val = INT_MAX;
 	int best_node = -1;
+	int first_node = node;
 
-	for_each_online_node(i) {
+	/* Use the local node if we haven't already */
+	if (node_isset(node, *used_node_mask))
+		n = !first_node;
+	else {
+		n = first_node;
+		best_node = node;
+	}
+
+	for (; n != first_node; node = n) {
 		cpumask_t tmp;
 
-		/* Start from local node */
-		n = (node+i) % num_online_nodes();
+		n = next_node(node, node_online_map);
+
+		if (n == MAX_NUMNODES)
+			n = first_node(node_online_map);
 
 		/* Don't want a node to appear more than once */
 		if (node_isset(n, *used_node_mask))
 			continue;
 
-		/* Use the local node if we haven't already */
-		if (!node_isset(node, *used_node_mask)) {
-			best_node = node;
-			break;
-		}
-
 		/* Use the distance array to find the distance */
 		val = node_distance(node, n);
 

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