Migrate pages - v0.2
Subsystems (4)
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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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