Skip to contentSkip to conversation

Migrate pages from a ccNUMA node to another - patch

PATCH Zoltan Menyhart 4 participants 17 messages Mar 26, 2004 – Apr 8, 2004

Subsystems (3)
lore
Share & tools
lore
#0 lore raw
arch/ia64/kernel/acpi.c +1 -0
diff -Nru 2.6.4.ref/arch/ia64/kernel/acpi.c 2.6.4.mig4/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 +4 -0
diff -Nru 2.6.4.ref/arch/ia64/kernel/entry.S 2.6.4.mig4/arch/ia64/kernel/entry.S
@@ -1518,7 +1518,11 @@
 	data8 sys_ni_syscall
 	data8 sys_ni_syscall
 	data8 sys_ni_syscall			// 1275
+#if defined(CONFIG_NUMA)
+	data8 sys_page_migrate			// 1276: Migrate pages to another NUMA node
+#else
 	data8 sys_ni_syscall
+#endif
 	data8 sys_ni_syscall
 	data8 sys_ni_syscall
 	data8 sys_ni_syscall
arch/ia64/mm/Makefile +1 -1
diff -Nru 2.6.4.ref/arch/ia64/mm/Makefile 2.6.4.mig4/arch/ia64/mm/Makefile
@@ -5,7 +5,7 @@
 obj-y := init.o fault.o tlb.o extable.o
 
 obj-$(CONFIG_HUGETLB_PAGE) += hugetlbpage.o
-obj-$(CONFIG_NUMA)	   += numa.o
+obj-$(CONFIG_NUMA)	   += numa.o migrate.o
 obj-$(CONFIG_DISCONTIGMEM) += discontig.o
 ifndef CONFIG_DISCONTIGMEM
 obj-y += contig.o
arch/ia64/mm/migrate.c +1274 -0

1,274 lines not on this page · raw message

include/asm-generic/rmap.h +41 -0

45 lines not on this page · raw message

include/asm-ia64/page_migrate.h +245 -0

245 lines not on this page · raw message

include/asm-ia64/pgtable.h +26 -2
diff -Nru 2.6.4.ref/include/asm-ia64/pgtable.h 2.6.4.mig4/include/asm-ia64/pgtable.h
@@ -112,6 +112,28 @@
 #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 only.)
+ */
+#define	__VA_BITS_PER_REGION	(PAGE_SHIFT - 3 - 3 +	/* PGD low index */		\
+				2 * (PAGE_SHIFT - 3) +	/* PMD and PTE indices */	\
+				PAGE_SHIFT)		/* The page itself */
+#define	__VA_ALIAS_MASK		((1UL << __VA_BITS_PER_REGION) - 1)
+#define	__IS_VA_ALIAS(address, length)							\
+				((~__VA_ALIAS_MASK & (address)) !=			\
+					(~__VA_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 +347,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/rmap-locking.h +25 -0
diff -Nru 2.6.4.ref/include/asm-ia64/rmap-locking.h 2.6.4.mig4/include/asm-ia64/rmap-locking.h
@@ -0,0 +1,25 @@
+/*
+ * include/linux/rmap-locking.h
+ *
+ * Locking primitives for exclusive access to a page's reverse-mapping
+ * pte chain.
+ */
+
+#include <linux/slab.h>
+
+struct pte_chain;
+extern kmem_cache_t *pte_chain_cache;
+
+#define pte_chain_lock(page)	bit_spin_lock(PG_chainlock, &page->flags)
+#define pte_chain_trylock(page)	bit_spin_trylock(PG_chainlock, &page->flags)
+#define pte_chain_unlock(page)	bit_spin_unlock(PG_chainlock, &page->flags)
+
+struct pte_chain *pte_chain_alloc(int gfp_flags);
+void __pte_chain_free(struct pte_chain *pte_chain);
+
+static inline void pte_chain_free(struct pte_chain *pte_chain)
+{
+	if (pte_chain)
+		__pte_chain_free(pte_chain);
+}
+
include/linux/rmap-locking.h +1 -0
diff -Nru 2.6.4.ref/include/linux/rmap-locking.h 2.6.4.mig4/include/linux/rmap-locking.h
@@ -11,6 +11,7 @@
 extern kmem_cache_t *pte_chain_cache;
 
 #define pte_chain_lock(page)	bit_spin_lock(PG_chainlock, &page->flags)
+#define pte_chain_trylock(page)	bit_spin_trylock(PG_chainlock, &page->flags)
 #define pte_chain_unlock(page)	bit_spin_unlock(PG_chainlock, &page->flags)
 
 struct pte_chain *pte_chain_alloc(int gfp_flags);
mm/rmap.c +0 -31
diff -Nru 2.6.4.ref/mm/rmap.c 2.6.4.mig4/mm/rmap.c
@@ -46,40 +46,9 @@
  * We use an array of pte pointers in this structure to minimise cache misses
  * while traversing reverse maps.
  */
-#define NRPTE ((L1_CACHE_BYTES - sizeof(unsigned long))/sizeof(pte_addr_t))
-
-/*
- * next_and_idx encodes both the address of the next pte_chain and the
- * offset of the highest-index used pte in ptes[].
- */
-struct pte_chain {
-	unsigned long next_and_idx;
-	pte_addr_t ptes[NRPTE];
-} ____cacheline_aligned;
 
 kmem_cache_t	*pte_chain_cache;
 
-static inline struct pte_chain *pte_chain_next(struct pte_chain *pte_chain)
-{
-	return (struct pte_chain *)(pte_chain->next_and_idx & ~NRPTE);
-}
-
-static inline struct pte_chain *pte_chain_ptr(unsigned long pte_chain_addr)
-{
-	return (struct pte_chain *)(pte_chain_addr & ~NRPTE);
-}
-
-static inline int pte_chain_idx(struct pte_chain *pte_chain)
-{
-	return pte_chain->next_and_idx & NRPTE;
-}
-
-static inline unsigned long
-pte_chain_encode(struct pte_chain *pte_chain, int idx)
-{
-	return (unsigned long)pte_chain | idx;
-}
-
 /*
  * pte_chain list management policy:
  *
test/migstat.c +130 -0

130 lines not on this page · raw message

test/ph.c +94 -0

94 lines not on this page · raw message

test/v.c +78 -0

78 lines not on this page · raw message

test/victim.c +36 -0
diff -Nru 2.6.4.ref/test/victim.c 2.6.4.mig4/test/victim.c
@@ -0,0 +1,36 @@
+/*
+ * Victim process for "vmig".
+ */
+
+
+#include <stdio.h>
+#include <errno.h>
+#include <stdlib.h>
+#include <sys/mman.h>
+
+#define	MMAPSIZE	(1024 * 1024 * 1024L)
+#define	N		MMAPSIZE / sizeof(long)
+
+
+main()
+{
+	int		i;
+	volatile long	*p0, *p;
+	long		sum0, sum;
+
+	printf("victim: pid = %d\n", getpid());
+	p0 = p = mmap(NULL, MMAPSIZE, PROT_READ | PROT_WRITE,
+					MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
+	if (p == MAP_FAILED){
+		perror("\nmmap()");
+		return 1;
+	}
+	printf("address: %p, size: 0x%lx\n", p, MMAPSIZE);
+	for (i = 0, sum0 = 0; i < N; i++)
+		sum0 += *p++ = random();
+	do {
+		for (i = 0, sum = 0, p = p0; i < N; i++)
+			sum += *p++;
+		printf("\nvictim: pid = %d, sum: %ld\n", getpid(), sum);
+	} while (sum0 == sum);
+}
test/vmig.c +36 -0
diff -Nru 2.6.4.ref/test/vmig.c 2.6.4.mig4/test/vmig.c
@@ -0,0 +1,36 @@
+/*
+ * Migrate the victim process by hand.
+ */
+
+
+#include <stdio.h>
+#include <errno.h>
+#include <sys/types.h>
+#include <sys/mman.h>
+#include "page_migrate.h"
+
+// Who cares for the SH library ?
+#define	SH_ADDRESS	(2UL << 60)
+#define	SH_SIZE		(16UL * 1024 * 1024 * 1024 * 1024)
+
+struct _un_success_count_ u_s;
+
+main(const int argc, const char * const argv[])
+{
+	int	node;
+	pid_t	pid;
+	int	rc;
+
+	if (argc != 3){
+		fprintf(stderr, "usage: vmig <pid> <node>\n");
+		return 1;
+	}
+	pid = atoi(argv[1]);
+	node = atoi(argv[2]);
+	rc = migrate_virt_addr_range((caddr_t) SH_ADDRESS, SH_SIZE, node, &u_s, pid);
+	if (rc < 0)
+		perror("migrate_virt_addr_range()");
+	else
+		printf("successful: %d failed: %d\n", u_s.successful, u_s.failed);
+	return 0;
+}
#1 lore raw

Have you considered any common ground your patch might share with the people doing memory hotplug?

http://people.valinux.co.jp/~iwamoto/mh.html

They have a similar problem to your migration that occurs when a user wants to remove a whole or partial NUMA node. [email protected]

Is your code something that you'd like to see go into the mainline 2.6 or 2.7 kernel?

Also, please don't spam-encode your address when sending to the list. It just makes it harder for people to send feedback.

-- Dave

#2 lore raw

Hi Zoltan,

At Fri, 26 Mar 2004 09:20:46 -0800,

Quoted 9 lines · Dave Hansen

Have you considered any common ground your patch might share with the people doing memory hotplug?

http://people.valinux.co.jp/~iwamoto/mh.html

They have a similar problem to your migration that occurs when a user wants to remove a whole or partial NUMA node. [email protected]

Processes must be migrated to other nodes when a node is being removed. Conversely, processes may be migrated from other nodes when a node is added. I'm not familiar with NUMA things, and I think our team doesn't have a particular solution. If you have some idea, that's great.

BTW, it seems page migration can use my remap_onepage function. Our code can move most kinds of pages including hugetlbfs pages and page caches.

--
IWAMOTO Toshihiro

#3 lore raw

Hello,

Quoted 15 lines
Quoted 8 lines

Have you considered any common ground your patch might share with the people doing memory hotplug?

http://people.valinux.co.jp/~iwamoto/mh.html

They have a similar problem to your migration that occurs when a user wants to remove a whole or partial NUMA node. [email protected]

Processes must be migrated to other nodes when a node is being removed. Conversely, processes may be migrated from other nodes when a node is added. I'm not familiar with NUMA things, and I think our team doesn't have a particular solution. If you have some idea, that's great.

Quoted 3 lines

BTW, it seems page migration can use my remap_onepage function. Our code can move most kinds of pages including hugetlbfs pages and page caches.

I believe his patch will interest you since most of the code is independent of cpu architecture and it also covers mmaped files, shmem, ramdisk, mlocked pages and so on.

We will post new version of the memory hotplug patches in a week.

Thank you,
Hirokazu Takahashi.

#4 lore raw
Quoted 22 lines · Hirokazu Takahashi

Hello,

Quoted 15 lines
Quoted 8 lines

Have you considered any common ground your patch might share with the people doing memory hotplug?

http://people.valinux.co.jp/~iwamoto/mh.html

They have a similar problem to your migration that occurs when a user wants to remove a whole or partial NUMA node. [email protected]

Processes must be migrated to other nodes when a node is being removed. Conversely, processes may be migrated from other nodes when a node is added. I'm not familiar with NUMA things, and I think our team doesn't have a particular solution. If you have some idea, that's great.

Quoted 3 lines

BTW, it seems page migration can use my remap_onepage function. Our code can move most kinds of pages including hugetlbfs pages and page caches.

Quoted 8 lines

I believe his patch will interest you since most of the code is independent of cpu architecture and it also covers mmaped files, shmem, ramdisk, mlocked pages and so on.

We will post new version of the memory hotplug patches in a week.

Thank you,
Hirokazu Takahashi.

I am afraid the "remap_onepage()" function + the modifications necessary at some other places are too much for me :-)

You do a couple of retries, waits. I cannot afford spending so much as overhead due to some performance optimization.

I can understand that if you want to remove a node / memory module, then you have to succeed by all means, you have to handle all kinds of pages, the performance is not at a premium.

Regards,

Zoltán Menyhárt

#5 lore raw

Hello,

Quoted 25 lines · Zoltán Menyhárt
Quoted 25 lines
Quoted 15 lines
Quoted 8 lines

Have you considered any common ground your patch might share with the people doing memory hotplug?

http://people.valinux.co.jp/~iwamoto/mh.html

They have a similar problem to your migration that occurs when a user wants to remove a whole or partial NUMA node. [email protected]

Processes must be migrated to other nodes when a node is being removed. Conversely, processes may be migrated from other nodes when a node is added. I'm not familiar with NUMA things, and I think our team doesn't have a particular solution. If you have some idea, that's great.

Quoted 3 lines

BTW, it seems page migration can use my remap_onepage function. Our code can move most kinds of pages including hugetlbfs pages and page caches.

I believe his patch will interest you since most of the code is independent of cpu architecture and it also covers mmaped files, shmem, ramdisk, mlocked pages and so on.

We will post new version of the memory hotplug patches in a week.

Quoted 8 lines
Quoted 2 lines

Thank you,
Hirokazu Takahashi.

I am afraid the "remap_onepage()" function + the modifications necessary at some other places are too much for me :-)

You do a couple of retries, waits. I cannot afford spending so much as overhead due to some performance optimization.

I understand what you want to do. Page migration is meaningless if the cost of it is high.

Quoted 7 lines

I can understand that if you want to remove a node / memory module, then you have to succeed by all means, you have to handle all kinds of pages, the performance is not at a premium.

Regards,

Zoltán Menyhárt

It's not hard to add "no-retry-mode" to "remap_onepage()" function if you want. It may skip to migrate some pages if they are accessed heavily. In paticular if you only want to care about anonymous pages, they will be handled very well.

Thank you,
Hirokazu Takahashi.

#6 lore raw

Hirokazu Takahashi wrote:

[...]

Quoted 5 lines

It's not hard to add "no-retry-mode" to "remap_onepage()" function if you want. It may skip to migrate some pages if they are accessed heavily. In paticular if you only want to care about anonymous pages, they will be handled very well.

Well, why not to give it a try ?
Yet your code is not really easy to read. :-)
I do not dare to adapt it on my own, I am afraid of breaking something. Could you please provide me a modified version of your "remap_onepage()" ? Can we move to 2.6.4 ?

In addition to "no-retry-mode", I need to specify where the new page should be allocated from.

Here is my interface I need to implement with "remap_onepage()":

/*
* Common part of checking & migrating the pages one by one.
*
* Arguments: src_node: Source NUMA node
* old_p: -> old page structure
* node: Destination NUMA node
* mm: -> victim "mm_struct"
* pte: -> PTE of the page to be moved
*
* Returns: 1: Migration O. K.
* 0: Minor error, no actual migration has been done
* -Exxx: Catastrophic error
*
* Notes: - "mm->page_table_lock" and "mm->mmap_sem" have to be held.
* - The old page is "get_page()"-ed on entry to make sure it does not go
* away in the mean time - on return it gets "put_page()"-ed.
*/
int
common_check_migrate_1_page(const int src_node, struct page * const old_p,
const int node, struct mm_struct * const mm, pte_t * const pte)

Notes: "pte" can be NULL if I do not know it apriori

       I cannot release "mm->page_table_lock" otherwise I have to re-scan the "mm->pgd".

Thanks,

Zoltán Menyhárt

#7 lore raw

Hello,

Quoted 10 lines
Quoted 4 lines

It's not hard to add "no-retry-mode" to "remap_onepage()" function if you want. It may skip to migrate some pages if they are accessed heavily. In paticular if you only want to care about anonymous pages, they will be handled very well.

Well, why not to give it a try ?
Yet your code is not really easy to read. :-)
I do not dare to adapt it on my own, I am afraid of breaking something. Could you please provide me a modified version of your "remap_onepage()" ? Can we move to 2.6.4 ?

Iwamot and I are working on this. We'll post it soon.

Quoted 4 lines

In addition to "no-retry-mode", I need to specify where the new page should be allocated from.

Here is my interface I need to implement with "remap_onepage()":

I guess aruguments src_node, mm and pte would be redundant since they can be looked up from old_p with the reverse mapping scheme.

Quoted 21 lines

/*
* Common part of checking & migrating the pages one by one.
*
* Arguments: src_node: Source NUMA node
* old_p: -> old page structure
* node: Destination NUMA node
* mm: -> victim "mm_struct"
* pte: -> PTE of the page to be moved
*
* Returns: 1: Migration O. K.
* 0: Minor error, no actual migration has been done
* -Exxx: Catastrophic error
*
* Notes: - "mm->page_table_lock" and "mm->mmap_sem" have to be held.
* - The old page is "get_page()"-ed on entry to make sure it does not go
* away in the mean time - on return it gets "put_page()"-ed.
*/
int
common_check_migrate_1_page(const int src_node, struct page * const old_p,
const int node, struct mm_struct * const mm, pte_t * const pte)

Quoted 2 lines

Notes: "pte" can be NULL if I do not know it apriori

      I cannot release "mm->page_table_lock" otherwise I have to re-scan the "mm->pgd".

Re-schan plicy would be much better since migrating pages is heavy work. I don't think that holding mm->page_table_lock for long time would be good idea.

How do you think about following algorism:
1. get mm->page_table_lock
2. chose some pages.
3. release mm->page_table_lock
4. call remap_onepage() against each page.
5. goto step1 if there remain pages to be migrated.

#8 lore raw
Quoted 2 lines · Hirokazu Takahashi

I guess aruguments src_node, mm and pte would be redundant since they can be looked up from old_p with the reverse mapping scheme.

In my version 0.2, I can do with only the following arguments:
* node: Destination NUMA node
* mm: -> victim "mm_struct"
* pte: -> PTE of the page to be moved
(If I have "mm" at hand, why not to use it ? Why not to avoid fetching the r-map page struct ?)

Quoted 6 lines
Quoted 2 lines

Notes: "pte" can be NULL if I do not know it apriori

      I cannot release "mm->page_table_lock" otherwise I have to re-scan the "mm->pgd".

Re-schan plicy would be much better since migrating pages is heavy work. I don't think that holding mm->page_table_lock for long time would be good idea.

Re-scanning is "cache killer", at least on IA64 with huge user memory size. I have more than 512 Mbytes user memory and its PTEs do not fit into the L2 cache.

In my current design, I have the outer loops: PGD, PMD and PTE walking; and once I find a valid PTE, I check it against the list of max. 2048 physical addresses as the inner loop.
I reversed them: walking through the list of max. 2048 physical addresses as outer loop and the PGD - PMD - PTE scans as inner loops resulted in 4 to 5 times slower migration.

Quoted 6 lines

How do you think about following algorism:
1. get mm->page_table_lock
2. chose some pages.
3. release mm->page_table_lock
4. call remap_onepage() against each page.
5. goto step1 if there remain pages to be migrated.

I want to move the most frequently used pages - at least with the HW assisted hot page detection.
I take "mm->page_table_lock", I nuke the PTE. We've got a good chance that the CPU using the page observes a page fault almost immediately. It enters the page fault handler and gets blocked by "mm->page_table_lock". If I released the lock, the CPU could continue and realize that there is nothing to do, the page fault has already been repaired. In the mean time, it is me who wait for "mm->page_table_lock". At worst this scenario happens 2048 times.
If I keep the lock, the victim CPU enters only once the page fault handler.

I think what we should do is to "pull in" pages in to a node rather than than "pushing them out" for two reasons:
- the recipient CPU executes the migration instead of busy waiting for the lock
- there is chance that the recipient CPU will find the migrated data useful in its cache

Regards,

Zoltán Menyhárt

#9 lore raw
Quoted 11 lines · Zoltan Menyhart
Quoted 2 lines · Hirokazu Takahashi

I guess aruguments src_node, mm and pte would be redundant since they can be looked up from old_p with the reverse mapping scheme.

In my version 0.2, I can do with only the following arguments:
* node: Destination NUMA node
* mm: -> victim "mm_struct"
* pte: -> PTE of the page to be moved
(If I have "mm" at hand, why not to use it ? Why not to avoid fetching the r-map page struct ?)

That's a good point. There is at least some cost (at least 1 lock) associated with walking the rmap chains. If it can be avoided, it might as well be.

But, if someone needs the "no walk" interface, just wrap the function:

foo(page)

{
	rmap_results = get_rmap_stuff(page);
	__foo(page, rmap_results);
}

__foo(page, rmap_results)
{
...
}

Quoted 10 lines
Quoted 6 lines
Quoted 2 lines

Notes: "pte" can be NULL if I do not know it apriori

      I cannot release "mm->page_table_lock" otherwise I have to re-scan the "mm->pgd".

Re-schan plicy would be much better since migrating pages is heavy work. I don't think that holding mm->page_table_lock for long time would be good idea.

Re-scanning is "cache killer", at least on IA64 with huge user memory size. I have more than 512 Mbytes user memory and its PTEs do not fit into the L2 cache.

Quoted 6 lines

In my current design, I have the outer loops: PGD, PMD and PTE walking; and once I find a valid PTE, I check it against the list of max. 2048 physical addresses as the inner loop.
I reversed them: walking through the list of max. 2048 physical addresses as outer loop and the PGD - PMD - PTE scans as inner loops resulted in 4 to 5 times slower migration.

Could you explain where you're getting these "magic numbers?" I don't quite understand the significance of 2048 physical addresses or 512 MB of memory.

Zoltan, it appears that we have a bit of an inherent conflict with how much CPU each of you is expecting to use in the removal and migration cases. You're coming from a HPC environment where each CPU cycle is valuable, while the people trying to remove memory are probably going to be taking CPUs offline soon anyway, and care a bit less about how efficient they're being with CPU and cache resources.

Could you be a bit more explicit about how expensive (cpu-wise) these migrate operations can be?

-- Dave

#10 lore raw

Re: Migrate pages from a ccNUMA node to another

Quoted 17 lines · Dave Hansen
Quoted 10 lines
Quoted 6 lines
Quoted 2 lines

Notes: "pte" can be NULL if I do not know it apriori

      I cannot release "mm->page_table_lock" otherwise I have to re-scan the "mm->pgd".

Re-schan plicy would be much better since migrating pages is heavy work. I don't think that holding mm->page_table_lock for long time would be good idea.

Re-scanning is "cache killer", at least on IA64 with huge user memory size. I have more than 512 Mbytes user memory and its PTEs do not fit into the L2 cache.

Quoted 6 lines

In my current design, I have the outer loops: PGD, PMD and PTE walking; and once I find a valid PTE, I check it against the list of max. 2048 physical addresses as the inner loop.
I reversed them: walking through the list of max. 2048 physical addresses as outer loop and the PGD - PMD - PTE scans as inner loops resulted in 4 to 5 times slower migration.

Quoted 3 lines

Could you explain where you're getting these "magic numbers?" I don't quite understand the significance of 2048 physical addresses or 512 MB of memory.

I use an IA64 machine with page size of 16 Kbytes.

I allocate a single page (for simplicity) when I copy in from user space the list of the addresses (2048 of them fit in a page).

One page of PTEs maps 32 Mbytes.
16 pages (which map 512 Mbytes) eat up my L2 cache of 256 Kbytes (and the other data, the stack, the code, etc...).

Sure I have an L3 cache of at least 3 Mbytes (new CPUs have bigger L3 caches) but it is much slower than the L2.

Quoted 6 lines

Zoltan, it appears that we have a bit of an inherent conflict with how much CPU each of you is expecting to use in the removal and migration cases. You're coming from a HPC environment where each CPU cycle is valuable, while the people trying to remove memory are probably going to be taking CPUs offline soon anyway, and care a bit less about how efficient they're being with CPU and cache resources.

Yes I see.

Quoted 2 lines

Could you be a bit more explicit about how expensive (cpu-wise) these migrate operations can be?

My machine 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 CPU clock runs at 1.3 GHz. Local memory access costs 200 nanosec. The NUMA factor is 1 : 2.25.

An OpenMP benchmark uses 1 Gbytes of memory and runs on 16 processors, on 4 NUMA nodes.

If the benchmark is adapted to our NUMA architecture (local allocations by hand), 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.
(I keep holding the PGD lock, no re-scan while moving the max. 2048 pages.)

Inverting the inner - extern loops, i.e. for each page, I scan the PGD-PMD-PTE, and the PGD lock is released between the scans, I have 10 to 12 seconds spent on the migration (not counting the 1 to 2 seconds of the "AI" + ~10 seconds due to the buggy SNCs.)

Thanks,

Zoltán

#11 lore raw
In reply to Zoltan Menyhart

Hello,

Quoted 20 lines
Quoted 2 lines

I guess aruguments src_node, mm and pte would be redundant since they can be looked up from old_p with the reverse mapping scheme.

In my version 0.2, I can do with only the following arguments:
* node: Destination NUMA node
* mm: -> victim "mm_struct"
* pte: -> PTE of the page to be moved
(If I have "mm" at hand, why not to use it ? Why not to avoid fetching the r-map page struct ?)

Quoted 6 lines
Quoted 2 lines

Notes: "pte" can be NULL if I do not know it apriori

      I cannot release "mm->page_table_lock" otherwise I have to re-scan the "mm->pgd".

Re-schan plicy would be much better since migrating pages is heavy work. I don't think that holding mm->page_table_lock for long time would be good idea.

Re-scanning is "cache killer", at least on IA64 with huge user memory size. I have more than 512 Mbytes user memory and its PTEs do not fit into the L2 cache.

Quoted 6 lines

In my current design, I have the outer loops: PGD, PMD and PTE walking; and once I find a valid PTE, I check it against the list of max. 2048 physical addresses as the inner loop.
I reversed them: walking through the list of max. 2048 physical addresses as outer loop and the PGD - PMD - PTE scans as inner loops resulted in 4 to 5 times slower migration.

I've been thinking about it.

I guess our page remap patches would be overkill for your purpose. Point of our patches is that:
1. Blocks new access to a specified page.
2. Waits for the page going into quiescent state.
3. Copies data from the page to a new page and exchanges them.

In my understanding you want to handle only anonymous pages which don't have backing store yet. This means that you only need step 3.

Quoted 7 lines
Quoted 6 lines

How do you think about following algorism:
1. get mm->page_table_lock
2. chose some pages.
3. release mm->page_table_lock
4. call remap_onepage() against each page.
5. goto step1 if there remain pages to be migrated.

Quoted 7 lines

I want to move the most frequently used pages - at least with the HW assisted hot page detection.
I take "mm->page_table_lock", I nuke the PTE. We've got a good chance that the CPU using the page observes a page fault almost immediately. It enters the page fault handler and gets blocked by "mm->page_table_lock". If I released the lock, the CPU could continue and realize that there is nothing to do, the page fault has already been repaired. In the mean time, it is me who wait for "mm->page_table_lock".

If you use the HW assisted hot page detection, just notify our remapping functions of hot pages directly. Everything would be handled well and pagefault handler would be blocked by PG_lock bit.

#12 lore raw
In reply to Dave Hansen
Quoted 9 lines · Dave Hansen

Have you considered any common ground your patch might share with the people doing memory hotplug?

http://people.valinux.co.jp/~iwamoto/mh.html

They have a similar problem to your migration that occurs when a user wants to remove a whole or partial NUMA node. [email protected]

Comparing my stuff to their work, I just do some small performance enhancements:

- I do not modify a single line on the existing VM paths - if my stuff has no improvement for you, then yo will not be obliged to pay any overhead
- I do not insist on :-)) ... that would block the execution of the application while the resources are not available
- I handle only the simplest case: private anonymous pages (...a singe PTE...)

- IWAMOTO Toshihiro provides a complete "fool proof" solution with obligation to cussed in the migration

Quoted 2 lines

Is your code something that you'd like to see go into the mainline 2.6 or 2.7 kernel?

Since someone is asking...

Thanks,

Zoltán

#13 lore raw
Quoted 9 lines · Zoltan Menyhart
Quoted 3 lines · Dave Hansen

Have you considered any common ground your patch might share with the people doing memory hotplug?

Comparing my stuff to their work, I just do some small performance enhancements:

- I do not modify a single line on the existing VM paths - if my stuff has no improvement for you, then yo will not be obliged to pay any overhead

...

Quoted 1 line

- I handle only the simplest case: private anonymous pages (...a singe PTE...)

By not modifying a single line in the existing VM path, your patch simply duplicates functionality from that existing code, which I'm not sure is any better.

I think there's a lot of commonality with what the swap code, NUMA page migration, and memory removal have to do. However, none of them share any code today. I think all of the implementations could benefit from making them a bit more generic.

-- Dave

#14 lore raw
In reply to Zoltan Menyhart
Quoted 5 lines · Zoltan Menyhart
Quoted 2 lines · Dave Hansen

Is your code something that you'd like to see go into the mainline 2.6 or 2.7 kernel?

Since someone is asking...

Before anything else, please take a long look at Documentation/CodingStyle. Pay particular attention to the column width, indenting, and function sections.

One of the best things about your code is that it uses a lot of architecture-independent functions and data structures. The page table walks in your patch, for instance, would work on any Linux architecture. However, all of this code is in the ia64 arc. Why? Will other NUMA architectures not need this page migration functionality?

It's great that you are commenting so many things, but normal Linux style is to use C-style comments, not C++. Also, although it's great while you're developing a patch, it's best to try and refrain from documenting things in comments things that are already a non-tricky part of the way that things already work:
//
// "pte_page->mapping" points at the victim process'es "mm_struct" //
These comments really just take up space and reduce readability.

I find the comments inside of function and macro calls a bit hard to read:
STORE_DELAY(/* in */ unlock_time, /* out */ new_page_unlock);

void
dump_mm(const struct mm_struct * const mm)
{
...

void
dump_vma(const struct vm_area_struct * const vma)
{

I think every VM hacker has a couple of these functions stashed around in various patches for debugging, but they're not really something that belongs in the kernel. In general, you should try to remove debugging code before posting a patch.

+ case _SIZEOF_STATISTICS_:
+ rc = *(long long *) &_statistics_sizes;
+ break;

I'm sure the statistics are very important, but they're a bit intrusive. Can you separate that code out into a file by itself? Are they even something that a user would want when they're running normally, or is it another debugging feature?

+#if defined(CONFIG_NUMA)
+ data8 sys_page_migrate // 1276: Migrate pages
to another NUMA node
+#else
data8 sys_ni_syscall
+#endif

See cond_syscall. Basically you declare a weak symbol and override it later if necessary.

+obj-$(CONFIG_NUMA) += numa.o migrate.o

Can you separate this out under its own config option?

+asmlinkage long long
+sys_page_migrate(const int cmd, const caddr_t address, const size_t.
...
+ switch (cmd){
...
+ case _PHADDR_BATCH_MIGRATE_:
...
+ case _VA_RANGE_MIGRATE_:
...
+ case _STATISTICS_:
...
+ case _GIMME_AN_ADDRESS_:

This smells strongly of an ioctl. If there really are 2 distinct kinds of memory removal operations, then go ahead and make 2 different syscalls. As for the _STATISTICS_ and _GIMME_AN_ADDRESS_, they really shouldn't be there at all. They're just abusing the syscall.

+migrate_virt_addr_range(
...
+ u.ll = syscall(__NR_page_migrate, _VA_RANGE_MIGRATE_,
+ address, length, node, pid);
...
+}

Making syscalls from inside of the kernel is strongly discouraged. I'm not sure what you're trying to do there. You might want to look at some existing code like sys_mmap() vs do_mmap().

+#define __VA(pgdi, pmdi, ptei) (((pgdi) >> (PAGE_SHIFT - 6)) << 61 | \
+ ((pgdi) & ((PTRS_PER_PGD >> 3) - 1)) << PGDIR_SHIFT | \
+ (pmdi) << PMD_SHIFT | (ptei) << PAGE_SHIFT)

There are magic numbers galore in this macro. Would this work?

#define __VA(pgdi, pmdi, ptei)	((pgdi)*PGDIR_SIZE + \
				 (pmdi)*PMD_SIZE +   \
				 (ptei)*PAGE_SIZE)

If ia64 doesn't have the _SIZE macros, you can just copy them from include/asm-i386/pgtable*.h

-- 2.6.4.ref/mm/rmap.c Tue Mar 16 10:18:17 2004
+++ 2.6.4.mig4/mm/rmap.c Thu Mar 25 09:00:13 2004
...
-struct pte_chain {
- unsigned long next_and_idx;
- pte_addr_t ptes[NRPTE];
-} ____cacheline_aligned;-- 2.6.4.ref/include/asm-ia64/rmap-locking.h

Exposing the VM internals like that probably isn't going to be acceptable. Why was this necessary?

--- 2.6.4.ref/test/vmig.c Thu Jan 1 01:00:00 1970
+++ 2.6.4.mig4/test/vmig.c Thu Mar 25 09:02:00 2004

If you need userspace code to demonstrate how to use your patch, it's probably best to post it separately instead of including it in the patch. Someone might mistake it for kernel code.

I'm sure I missed some things, but I it's hard to look at the patch in depth functionally before it is cleaned up a bit.

I look forward to seeing an updated version.

-- Dave

#15 lore raw
Quoted 2 lines · Dave Hansen

I'm sure I missed some things, but I it's hard to look at the patch in depth functionally before it is cleaned up a bit.

One thing I forgot...

There don't appear to be any security checks in your syscall. Should all users be allowed to migrate memory around at will from any pid?

-- Dave

#16 lore raw

Re: Migrate pages from a ccNUMA node to another

In reply to Dave Hansen

Dave,

Thank you for your remarks.

Sure, I'll do my best to comply with the coding style of the community.

Quoted 3 lines · Dave Hansen

Before anything else, please take a long look at Documentation/CodingStyle. Pay particular attention to the column width, indenting, and function sections.

Shell I really stick to the width of 80 characters ? I have got 89, yet several other files already are much wider.

By the indenting issues, do you mean (not) breaking lines like these below ?

			if ((pte_val(*pte) & _PFN_MASK) !							(*p & _PFN_MASK))

(I do have TABs = 8 spaces.)

Cutting the functions into smaller pieces - I'll try to do my best.

Quoted 5 lines

One of the best things about your code is that it uses a lot of architecture-independent functions and data structures. The page table walks in your patch, for instance, would work on any Linux architecture. However, all of this code is in the ia64 arc. Why? Will other NUMA architectures not need this page migration functionality?

I made an effort to write it as architecture independent as possible (I guess only the SAVE_ITC - STORE_DELAY macro pair is to be re-written.) As I have not even seen any other NUMA machine - I would not post a code that no one ever tried on the other architectures.

Quoted 8 lines

Also, although it's great
while you're developing a patch, it's best to try and refrain from documenting things in comments things that are already a non-tricky part of the way that things already work:
//
// "pte_page->mapping" points at the victim process'es "mm_struct" //
These comments really just take up space and reduce readability.

This one was for myself :-)

It is difficult to find the golden mean. E.g. if I have not inserted a comment here:

	mm = current->mm;
	//
	// Actually, there is no need to grab "mm" because it is ours, wont go
	// away in the mean time. As we do not want to ask questions when
	// releasing it...
	// It is safe just to increment the counter: it is ours.
	//
	atomic_inc(&mm->mm_users);

I think people could have asked why on the Earth I incremented "current->mm->mm_users". Or another example:

	//
	// "get_task_mm()" includes "task_lock()" that "nests both inside and outside of
	// read_lock(&tasklist_lock)" - as a note in "sched.h" states.
	//

As there is no "locking guide", at least I make a note why I think I'm safe.

(I think the main goals are efficiency and quality: how much effort it takes to add a new functionality, to correct a bug or simply to understand the code; how much chance we've got not to crash the system.
In the old golden ages, there were some few gurus who knew the code by hart. It was efficient for them not to waste time on "useless stuff". Now as the Linux community becomes larger and larger, the meaning what the efficiency is has changed. I think the efficiency should mean how easily people can understand, add, change, correct things. How can I be efficient if need to resolve puzzles ? No problem with solving puzzles, it's an intellectual challenge. But how can I know if some "stuff" is there intentionally or by chance ? Or I just misunderstood the puzzle ? The quality requirement is against solving puzzles.

Most of my comments are "synchronization points" for those who want to understand my code and "statements" for those who want to double check if I've missed a point.

Another OS that "must not be named" includes thousands of ASSERT()-s and assert()-s (see also the JFS of Linux) and the lower case assert()-s are kept even for non debug mode. Should not include Linux lost of similar "statements" ?)

Quoted 3 lines

I find the comments inside of function and macro calls a bit hard to read:
STORE_DELAY(/* in */ unlock_time, /* out */ new_page_unlock);

I think there is a conceptual problem here, e.g.:

	a = 1; b = 2;
	Foo(a); Foo_2(&b);
	c = a + b;		// Is still a = 1 and b = 2 ?

I just read through the code: o.k. we call a "functionality" Foo(a) - assuming it is a speaking name - I can see more or less what it does; but is "a" sill equal to 1 at the 3rd line ?
Don't know. If Foo() is a function, then "a" has not been changed, if Foo() is a macro - who knows ? As far as "b" and Foo_2() are concerned, "&" is
a more than warning that "b" gets modified.
I have to warn the reader "by hand" that an argument gets modified. It is more "space efficient" as I wrote than writing as:

	/* Warning: "new_page_unlock" is going to be changed */
	STORE_DELAY(unlock_time, new_page_unlock);
Quoted 4 lines

I think every VM hacker has a couple of these functions stashed around in various patches for debugging, but they're not really something that belongs in the kernel. In general, you should try to remove debugging code before posting a patch.

If you want to print out a VMA, where is the debug service ?
I agree this is not best place in my code. As the print out routines should be kept coherent with the definitions of the respective structures, they should be some static functions in the .h files.
I'll remove them but we still need some official stuff.

I stopped my source navigator after it has dug up the 1000th "...DEBUG..." :-)

Quoted 8 lines
arch/ia64/mm/migrate.c +3 -0
+       case _SIZEOF_STATISTICS_:
+               rc =  *(long long *) &_statistics_sizes;
+               break;

I'm sure the statistics are very important, but they're a bit intrusive. Can you separate that code out into a file by itself? Are they even something that a user would want when they're running normally, or is it another debugging feature?

As our "AI" is very much experimental, I really do not know how much this information is useful. Neither the HW assisted nor the application driven version knows how many pages are movable, how many of them cannot be handled at all by my migration mechanism (e.g. you have a SysV SHM). Other error information or knowing how much it costs can be a feed back for the "AI". Probably it is useful wen we tune the profile for an application. We need more experience.

Quoted 9 lines
include/asm-ia64/page_migrate.h +4 -0
+migrate_virt_addr_range(
...
+       u.ll = syscall(__NR_page_migrate, _VA_RANGE_MIGRATE_,
+                      address, length, node, pid);
...
+}

Making syscalls from inside of the kernel is strongly discouraged. I'm not sure what you're trying to do there. You might want to look at some existing code like sys_mmap() vs do_mmap().

The wrapper functions like this are after an "#if !defined(__KERNEL__)"

As "types.h" also contains "#ifdef __KERNEL__"...

Quoted 5 lines
include/asm-ia64/pgtable.h +3 -0
+#define        __VA(pgdi, pmdi, ptei)  (((pgdi) >> (PAGE_SHIFT - 6)) << 61 |           \
+                               ((pgdi) & ((PTRS_PER_PGD >> 3) - 1)) << PGDIR_SHIFT |   \
+                               (pmdi) << PMD_SHIFT | (ptei) << PAGE_SHIFT)

There are magic numbers galore in this macro. Would this work?

Well, I just copied what the offitial "pgd_index()" macro and its fellows do:

pgd_index (unsigned long address)

{
	unsigned long region = address >> 61;
	unsigned long l1index = (address >> PGDIR_SHIFT) & ((PTRS_PER_PGD >> 3) - 1);

	return (region << (PAGE_SHIFT - 6)) | l1index;
}

Me too, I'd like to see more symbolic constants... But I don't want to be more catholic than the Pope :-)

Quoted 5 lines
#define __VA(pgdi, pmdi, ptei)  ((pgdi)*PGDIR_SIZE + \
                                 (pmdi)*PMD_SIZE +   \
                                 (ptei)*PAGE_SIZE)

If ia64 doesn't have the _SIZE macros, you can just copy them from include/asm-i386/pgtable*.h

Unfortunately, it is not so simple like that.
We've got 5 user regions out of 8 regions of size of 0x2000000000000 (don't know how is this called). Only the first 16 Tbytes of each region are mapped bye the PGD-PMD-PTE structure. Then we've got a large hole that cannot be taken into account by your macro. I.e. we count as

0x000fffffffffffff, 0x2000000000000, ... 0x200fffffffffffff, 0x4000000000000

Apart from using some nice macros with speaking names instead of "<< 61", I cannot see any simpler way for the conversion (as far as IA64 is concerned).

Quoted 10 lines

-- 2.6.4.ref/mm/rmap.c Tue Mar 16 10:18:17 2004
+++ 2.6.4.mig4/mm/rmap.c Thu Mar 25 09:00:13 2004
...

mm/rmap.c +0 -4
-struct pte_chain {
-       unsigned long next_and_idx;
-       pte_addr_t ptes[NRPTE];
-} ____cacheline_aligned;-- 2.6.4.ref/include/asm-ia64/rmap-locking.h

Exposing the VM internals like that probably isn't going to be acceptable. Why was this necessary?

Previously, I was more ambitious, and wanted to handle the not direct mapped pages, too. I'll put back where it was.

For the rest: it's YES.

Quoted 2 lines

There don't appear to be any security checks in your syscall. Should all users be allowed to migrate memory around at will from any pid?

Well, who makes migrate someone else, cannot read / write the victim's data, nor can break it. For more security, I can add a something like whoever can kill an application, s/he can migrate it, too.

Quoted 8 lines

By not modifying a single line in the existing VM path, your patch simply duplicates functionality from that existing code, which I'm not sure is any better.

I think there's a lot of commonality with what the swap code, NUMA page migration, and memory removal have to do. However, none of them share any code today. I think all of the implementations could benefit from making them a bit more generic.

I can agree on not doubling code. I can give a try to the code written by Hirokazu Takahashi and see if it is sufficiently efficient for me.

Thanks,

Zoltán