Skip to contentSkip to conversation

Migrate pages - v0.2

PATCH Zoltan Menyhart 1 participant 1 message Apr 2, 2004

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

Here is my next try.

Version 0.2, 2nd of April 2004:
- Efforts made to make it less architecture dependent
- Two big loops of PGD-PMD-PTE scans merged at the expense of some "if-then-else"-es and some additional function parameters
- Permission check added
- Excessive DEBUG stuff removed
- Some cosmetics

You can find a description in "Documentation/migrate.txt".

I keep on using a single system call in order not too pollute much... Until I have an official system call number I just picked up:

	__NR_page_migrate 1276

I was thinking about reading out statistics via "/proc". Well I do not like converting numbers to strings and making the user program convert them back... In addition we may have up to 256 nodes, up to 256 * 256 migration counters - the result is not much readable.

Notes about the data security:
- The process controlling the migration cannot read nor modify the data of the victim process.
- The data of the victim process cannot be broken. Should the migration fail, a data page will be found intact, in a single example, either on the source or the destination NUMA node.
- He who can kill you is allowed to migrate your pages.

The patch is against: patch-2.6.4.-bk4

TODO: check to see if pulling in pages in to a node is better than pushing them out

Your remarks will be appreciated.

Zoltán Menyhárt

P.S: is the list [email protected] alive ?

Documentation/migrate.txt +352 -0
diff -Nur 2.6.4.ref/Documentation/migrate.txt 2.6.4.mig2-tmp/Documentation/migrate.txt
@@ -0,0 +1,352 @@
+Migrate pages from a ccNUMA node to another.
+============================================
+
+Version 0.2, 2nd of April 2004
+By Zoltan Menyhart, Bull S.A. <[email protected]>
+The usual GPL applies.
+
+What is it all about ?
+----------------------
+
+The old golden days of the Symmetrical Multi-Processor systems are over.
+Gone forever.
+We are left with (cache coherent) Non Uniform Memory Architectures.
+I can see the future.
+I can see systems with hundreds, thousands of processors, with less and less
+uniform memory architectures.
+The "closeness" of a processor to its working set of memory will have the most
+important effect on the performance.
+
+You can make use of the forthcoming NUMA APIs to set up your NUMA environment:
+to bind processes to (groups of ) processors, to define the memory placement
+policy, etc.
+
+Yes, the initial placement is very much important. It affects tremendously the
+performance you obtain.
+
+Yet, what if
+- the application changes its behavior over time ?
+ (which processor uses which part of the memory)
+- you have not got the source of the application ?
+- you cannot add the NUMA services to it ?
+- you are not authorized to touch it ? (e.g. it is a reference benchmark)
+
+Page migration tries to help you out in these situations.
+
+What can this service do ?
+--------------------------
+
+- Migrate pages identified by their physical addresses to another NUMA node
+- Migrate pages of a virtual user address range to another NUMA node
+
+How can it be used ?
+--------------------
+
+1. Hardware assisted migration
+..............................
+
+As you can guess, it is very much platform dependent.
+I can only give you an example:
+
+We've got an Intel IA64 based machine for development / testing.
+It consists of 4 "Tiger boxes" connected together by a pair of Scalability Port
+Switches. A "Tiger box" is built around a Scalable Node Controller (SNC), and
+includes 4 Itanium-2 processors and some Gbytes of memory.
+The NUMA factor is 1 : 2.25.
+The SNC contains 2048 counters which allow us to count how many times these 2048
+zones of memory are touched from each node in a given observation period.
+An "artificial intelligence" can make predictions from these usage statistics
+and decide what pages are to be migrated and where.
+
+(Unfortunately, the SNCs are buggy - even the version C.1 is - we've got to use
+a couple of work-arounds, much of the work has to be done in software.
+This wastes about 10 seconds of CPU time while executing a benchmark of
+2 minutes. I hope, one day...)
+
+2. Application driven migration
+...............................
+
+An application can exploit the forthcoming NUMA APIs to specify its initial
+memory placement policy.
+Yet what if the application wants to change its behavior ?
+
+Allocating room on the destination node, copying the data by the application
+itself, and finally freeing the original room of the data is not very efficient.
+
+An application can ask the migration service to move a range of its virtual
+address space to the destination node.
+
+Example:
+A process of an application prepares a huge amount of data and hands it over to
+Its fellow processes (which happen to be bound to another NUMA node) for their
+(almost) exclusive usage.
+Migrating a page costs 128 remote accesses (assuming a page size of 16 Kbytes
+and a bus transaction size of 128 bytes) + some administration.
+Assuming the consumers of the data will frequently touch the page (cache misses)
+a considerable number of times, say more that 1000 times, then the migration
+becomes largely profitable.
+
+3. NUMA aware scheduler
+.......................
+
+A NUMA aware scheduler tries to keep processes on their "home" node where they
+have allocated (most of) their memory. What if the processors in this node are
+overloaded while several processors in the other nodes are largely in idle ?
+
+Should the scheduler select some other processors in the other nodes to execute
+these processes, at the expense of considerable number of extra node
+transactions ?
+Or should the scheduler leave the processors in the other nodes doing nothing ?
+Or should it move some processes with their memory working set to another node ?
+Let's leave this dilemma for the NUMA aware scheduler for the moment.
+
+Once the scheduler has made up its mind, the migration service can move the
+working set of memory of the selected processes to their new "home" node.
+
+User mode interface
+-------------------
+
+This prototype of the page migration service is implemented as a system call,
+the different forms of which are wrapped by use of some small,
+static, inline functions.
+
+NAME
+        migrate_ph_pages        - migrate pages to another NUMA node
+        migrate_virt_addr_range - migrate virtual address range to another node
+
+SYNOPSIS
+
+        #include <sys/types.h>
+        #include "page_migrate.h"
+
+        int migrate_ph_pages(
+                const phaddr_t * const table,
+                const size_t length,
+                const int node,
+                struct _un_success_count_ * const p,
+                const pid_t pid);
+
+        int migrate_virt_addr_range(
+                const caddr_t address,
+                const size_t length,
+                const int node,
+                struct _un_success_count_ * const p,
+                const pid_t pid);
+
+DESCRIPTION
+
+        The "migrate_ph_pages()" system call is used to migrate pages - their
+        physical addresses of "phaddr_t" type are given in "table" - to "node".
+        "length" indicates the number of the physical addresses in "table" and
+        should not be greater than "PAGE_SIZE / sizeof(phaddr_t)".
+        Only the pages belonging to the process indicated by "pid" and its
+        child processes cloned via "clone2(CLONEVM)" are treated, the other
+        processes' pages are silently ignored.
+
+        The "migrate_virt_addr_range()" system call is used to migrate pages of
+        a virtual address range of "length" starting at "address" to "node".
+        The virtual address range belongs to the process indicated by "pid" and
+        to its cloned children. If "pid" is zero then the current
+        process's virtual address range is moved.
+
+        Some statistics are returned via "p":
+
+        struct _un_success_count_ {
+                unsigned int    successful;     // Pages successfully migrated
+                unsigned int    failed;         // Minor failures
+        };
+
+RETURN VALUE
+
+        "migrate_ph_pages()" and "migrate_virt_addr_range()" return 0 on
+        success, or -1 if a major error occurred (in which case, "errno" is set
+        appropriately). Minor errors are silently ignored (migration continues
+        with the rest of the pages).
+
+ERRORS
+
+        ENODEV:         illegal destination node
+        ESRCH:          no process of "pid" can be found
+        EPERM:          no permission
+        EINVAL:         invalid system call parameters
+        EFAULT:         illegal virtual user address
+        ENOMEM:         cannot allocate memory
+
+RESTRICTIONS
+
+        We can migrate a page if it belongs to a single "mm_struct" / PGD,
+        i.e. it is private to a process or shared with its child processes
+        cloned via "clone2(CLONEVM)".
+
+Notes:
+
+- A "major error" prevents us from carrying on the migration, but it is not a
+  real error for the "victim" application that can continue (it is guaranteed
+  not to be broken). The pages already migrated are left in their new node.
+
+- Migrating a page shared among other than child processes cloned via
+  "clone2(CLONEVM)" would require locking all the page owners' PGDs.
+  I've got serious concerns about locking more than one PGDs:
+  + It is not foreseen in the design of the virtual memory management.
+  + Obviously, the PGDs have to be "trylock()"-ed in order to avoid dead locks.
+    However, "trylock()"-ing lots of PGDs, possibly thousands of them, would
+    lead to starvation problems. A performance enhancement tool consuming so
+    much in the event of not concluding...
+
+Some figures
+------------
+
+One of our customers has an OpenMP benchmark which was used to measure the
+machine described above. It uses 1 Gbytes of memory and runs on 16 processors,
+on 4 NUMA nodes.
+
+If the benchmark is adapted to our NUMA architecture, then it takes 86 seconds
+to complete.
+
+As results are not accepted if obtained by modifying the benchmark in any
+way, the best we can do is to use a random or round robin memory allocation
+policy. We end up with a locality rate of 25 % and the benchmark executes in 121
+seconds.
+
+If we had a zero-overhead migration tool, then - I estimate - it would complete
+In 92 seconds (the benchmark starts in a "pessimized" environment, and it takes
+time for the locality ramp up from 25 % to almost 100 %).
+
+Actually it takes 2 to 3 seconds to move 750 Mbytes of memory (on a heavily
+loaded machine), reading out the counters of the SNCs and making some quick
+decisions take 1 to 2 seconds, and we lose about 10 seconds due to the buggy
+SNCs. We end up with 106 seconds.
+
+Some if's
+---------
+
+- if the benchmark used more memory, then it would be more expensive to migrate
+  all of it's pages
+- if the benchmark ran for longer without changing its memory usage
+  pattern, then it could spend a greater percentage of its lifetime in a well
+  localized environment
+- if you had a NUMA factor higher than ours, then obviously, you would gain
+  more in performance by use of the migration service
+- if we used Madison processors with 6 Mbytes of cache (twice as much we have
+  right now), then the NUMA factor would be masked more efficiently
+- if the clock frequency of the processors increases, then you run out of cached
+  data more quickly and the NUMA factor becomes a higher performance cut factor
+
+Notes about the data security
+-----------------------------
+
+- The process controlling the migration cannot read nor modify the data of the
+  victim process.
+- The data of the victim process cannot be broken. Should the migration fail,
+  a data page will be found intact, in a single example, either on the source
+  or the destination NUMA node.
+- He who can kill you is allowed to migrate your pages.
+
+Porting guide
+-------------
+
+include/asm-.../page_migrate.h:
+...............................
+
+	Copy "include/asm-ia64/page_migrate.h" into the directory
+	"include/asm-<your architecture>
+
+Define "return_t":
+
+	Type of the return value for the system call. Should be able to hold
+	negative values, that of "phaddr_t" and we will cast the structures
+	"_un_success_count_" and "_statistics_size_" to this type.
+
+Define "phaddr_t":
+
+	Type of a physical address.
+
+Define "struct _un_success_count_":
+
+	Number of the pages successfully migrated / minor failures.
+
+Define "_statistics_size_":
+
+	Holds sizes of "struct _statistics_" are.
+
+Define "struct _statistics_":
+
+	The counters should not overflow.
+
+include/asm-.../delay.h:
+........................
+
+Define "GET_TIMER()":
+
+	This macro / function should return the current clock ticks.
+	It can simply return zero => no timing info will be available.
+
+include/linux/pagemap.h:
+........................
+
+Define "__IS_VADDR_ALIAS(address, length)":
+
+	Some architectures do not decode all the MSB-s of virtual
+	addresses for the PGD, PMD and PTE indices, i.e. they have
+	got holes or aliases in the virtual user address space.
+	This macro / function should return TRUE if "length" spans over
+	virtual address holes or it creates an illegal alias to an
+	otherwise valid address.
+
+	IA64 example (assuming a page size of 16 Kbytes):
+	There are 5 user regions, starting at addresses "i << 61" (where "i"
+	goes from 0 to 4). Only the first 16 Tbytes of each region is valid.
+	We count as:
+
+	0, 1, 2, ... 0x000fffffffffffff,
+	0x2000000000000, 0x2000000000001, ... 0x200fffffffffffff,
+	0x4000000000000, etc.
+
+Define "__VA(pgd_i, pmd_i, pte_i)":
+
+	This macro / function converts PGD, PMD and PTE indices into a
+	virtual address. Beware of the illegal virtual address aliases.
+	Not absolutely necessary if not testing. However, as it is the
+	counterpart of "pgd_index()", "pmd_index()" and "pte_index()"...
+
+include/asm-.../unistd.h:
+.........................
+
+	Add "#define __NR_page_migrate 1276"
+
+arch/.../Kconfig:
+.................
+
+Add:
+
+config PAGE_MIGRATE
+	bool "Support for migrating pages from a NUMA node to another"
+	depends on DISCONTIGMEM && NUMA
+	default n
+	help
+	  Say Y to compile the kernel to support migrating either pages
+	  identified by their physical addresses or a user mode virtual
+	  address range from a NUMA node to another.
+	  This option is for optimizing memory allocation pattern for
+	  high-end NUMA server systems.
+	  If in doubt, say N.
+
+To activate page migration, select:
+	Processor type and features
+	  NUMA support
+	    Support for migrating pages from a NUMA node to another
+
+Revision history:
+-----------------
+
+Version 0.1, 25th of March 2004:
+	- Initial version
+
+Version 0.2, 2nd of April 2004:
+	- Efforts made to make it less architecture dependent
+	- Two big loops of PGD-PMD-PTE scans merged at the expense of
+	  some "if-then-else"-es and some additional function parameters
+	- Permission check added
+	- Excessive DEBUG stuff removed
+	- Some cosmetics :-)
+
arch/ia64/Kconfig +12 -0
diff -Nur 2.6.4.ref/arch/ia64/Kconfig 2.6.4.mig2-tmp/arch/ia64/Kconfig
@@ -218,6 +218,18 @@
 	  Access).  This option is for configuring high-end multiprocessor
 	  server systems.  If in doubt, say N.
 
+config PAGE_MIGRATE
+	bool "Support for migrating pages from a NUMA node to another"
+	depends on DISCONTIGMEM && NUMA
+	default n
+	help
+	  Say Y to compile the kernel to support migrating either pages
+	  identified by their physical addresses or a user mode virtual
+	  address range from a NUMA node to another.
+	  This option is for optimizing memory allocation pattern for
+	  high-end NUMA server systems.
+	  If in doubt, say N.
+
 config VIRTUAL_MEM_MAP
 	bool "Virtual mem map"
 	default y if !IA64_HP_SIM
arch/ia64/kernel/acpi.c +1 -0
diff -Nur 2.6.4.ref/arch/ia64/kernel/acpi.c 2.6.4.mig2-tmp/arch/ia64/kernel/acpi.c
@@ -457,6 +457,7 @@
 	for (i = 0; i < MAX_PXM_DOMAINS; i++) {
 		if (pxm_bit_test(i)) {
 			pxm_to_nid_map[i] = numnodes;
+			node_set_online(numnodes);
 			nid_to_pxm_map[numnodes++] = i;
 		}
 	}
arch/ia64/kernel/entry.S +1 -1
diff -Nur 2.6.4.ref/arch/ia64/kernel/entry.S 2.6.4.mig2-tmp/arch/ia64/kernel/entry.S
@@ -1518,7 +1518,7 @@
 	data8 sys_ni_syscall
 	data8 sys_ni_syscall
 	data8 sys_ni_syscall			// 1275
-	data8 sys_ni_syscall
+	data8 sys_page_migrate
 	data8 sys_ni_syscall
 	data8 sys_ni_syscall
 	data8 sys_ni_syscall
include/asm-ia64/delay.h +5 -0
diff -Nur 2.6.4.ref/include/asm-ia64/delay.h 2.6.4.mig2-tmp/include/asm-ia64/delay.h
@@ -20,6 +20,11 @@
 #include <asm/intrinsics.h>
 #include <asm/processor.h>
 
+/*
+ * Architecture independent macro name for reading the timer.
+ */
+#define	GET_TIMER()	ia64_get_itc()
+
 static __inline__ void
 ia64_set_itm (unsigned long val)
 {
include/asm-ia64/page_migrate.h +218 -0

218 lines not on this page · raw message

include/asm-ia64/pgtable.h +28 -2
diff -Nur 2.6.4.ref/include/asm-ia64/pgtable.h 2.6.4.mig2-tmp/include/asm-ia64/pgtable.h
@@ -112,6 +112,30 @@
 #define PTRS_PER_PTE	(__IA64_UL(1) << (PAGE_SHIFT-3))
 
 /*
+ * The IA64 architecture does not decode all the MSB-s of virtual addresses for
+ * PGD, PMD and PTE indices, i.e. IA64 has got holes or aliases in the virtual
+ * address space.
+ * These def's are provided to check to see if an "address" -- "length" pair
+ * spans over virtual address holes or it creates illegal alias to an otherwise
+ * valid address. (User mode virtual addresses only.)
+ */
+#define	__VADDR_BITS_PER_REGION	(PAGE_SHIFT - 3 - 3 +	/* PGD low index */	\
+				2 * (PAGE_SHIFT - 3) +	/* PMD & PTE indices */	\
+				PAGE_SHIFT)		/* The page itself */
+#define	__VADDR_ALIAS_MASK		((1UL << __VADDR_BITS_PER_REGION) - 1)
+#define	__IS_VADDR_ALIAS(address, length)					\
+			((~__VADDR_ALIAS_MASK & (address)) !=			\
+			(~__VADDR_ALIAS_MASK & ((address) + (length) - 1)))
+
+/*
+ * Virtual address composed by use of PGD, PMD and PTE indices:
+ */
+#define	__VA(pgdi, pmdi, ptei)							\
+			(((pgdi) >> (PAGE_SHIFT - 6)) << 61 |			\
+			((pgdi) & ((PTRS_PER_PGD >> 3) - 1)) << PGDIR_SHIFT |	\
+			(pmdi) << PMD_SHIFT | (ptei) << PAGE_SHIFT)
+
+/*
  * All the normal masks have the "page accessed" bits on, as any time
  * they are used, the page is accessed. They are cleared only by the
  * page-out routines.
@@ -325,8 +349,10 @@
 	(init_mm.pgd + (((addr) >> PGDIR_SHIFT) & (PTRS_PER_PGD - 1)))
 
 /* Find an entry in the second-level page table.. */
-#define pmd_offset(dir,addr) \
-	((pmd_t *) pgd_page(*(dir)) + (((addr) >> PMD_SHIFT) & (PTRS_PER_PMD - 1)))
+#define pmd_index(addr) \
+	(((addr) >> PMD_SHIFT) & (PTRS_PER_PMD - 1))
+#define pmd_offset(dir, addr) \
+	((pmd_t *) pgd_page(*(dir)) + pmd_index(addr))
 
 /*
  * Find an entry in the third-level page table.  This looks more complicated than it
include/asm-ia64/unistd.h +1 -0
diff -Nur 2.6.4.ref/include/asm-ia64/unistd.h 2.6.4.mig2-tmp/include/asm-ia64/unistd.h
@@ -251,6 +251,7 @@
 #define __NR_reserved1			1259	/* reserved for NUMA interface */
 #define __NR_reserved2			1260	/* reserved for NUMA interface */
 #define __NR_reserved3			1261	/* reserved for NUMA interface */
+#define __NR_page_migrate		1276
 
 #ifdef __KERNEL__
 
include/linux/page_migrate.h +81 -0

81 lines not on this page · raw message

kernel/sys.c +1 -0
diff -Nur 2.6.4.ref/kernel/sys.c 2.6.4.mig2-tmp/kernel/sys.c
@@ -260,6 +260,7 @@
 cond_syscall(sys_shmget)
 cond_syscall(sys_shmdt)
 cond_syscall(sys_shmctl)
+cond_syscall(sys_page_migrate)
 
 /* arch-specific weak syscall entries */
 cond_syscall(sys_pciconfig_read)
mm/Makefile +2 -0
diff -Nur 2.6.4.ref/mm/Makefile 2.6.4.mig2-tmp/mm/Makefile
@@ -11,4 +11,6 @@
 			   page_alloc.o page-writeback.o pdflush.o readahead.o \
 			   slab.o swap.o truncate.o vmscan.o $(mmu-y)
 
+obj-$(CONFIG_PAGE_MIGRATE) += migrate.o
+
 obj-$(CONFIG_SWAP)	+= page_io.o swap_state.o swapfile.o
mm/migrate.c +888 -0

888 lines not on this page · raw message