Migration cache

Hi MM fellows,

So as I've said before in my opinion moving pages to the swapcache to migrate them is unnacceptable for several reasons. Not to mention live memory defragmentation.

So the following patch, on top of the v2.6 -memoryhotplug tree, creates a migration cache - which is basically a swapcache without using the swap map - it instead uses a on-memory idr structure.

So as I've said before in my opinion moving pages to the swapcache to migrate them is unnacceptable for several reasons. Not to mention live memory defragmentation.

So the following patch, on top of the v2.6 -memoryhotplug tree, creates a migration cache - which is basically a swapcache without using the swap map - it instead uses a on-memory idr structure.

For that we decrease SWP_TYPE_SHIFT from 5 to 4, and use that now-free bit to indicate pte's which point to pages on the migration cache.

Comments are very welcome

mm/memory.c +7 -0

@@ -1442,6 +1449,13 @@
 		page_cache_release(page);
 		goto again;
 	}
+	}
+
+
+	if (pte_is_migration(orig_pte)) {
+		mark_page_accessed(page);
+		lock_page(page);
+	}
 
 	/*
 	 * Back out if somebody else faulted in this pte while we

diff -Nur linux-2.6.9-rc2-mm4.mhp.orig/mm/mmigrate.c linux-2.6.9-rc2-mm4.build/mm/mmigrate.c

mm/mmigrate.c +14 -0

+
+
+	if (printk_ratelimit())
+		printk(KERN_ERR "remove_from_migration_cache!!\n");
+
+
+	if (page) {
+		migration_remove_reference(page);
+		unlock_page(page);
+		page_cache_release(page);
+	}
+
+}
 
 
+int add_to_migration_cache(struct page *page, int gfp_mask) 

mm/mmigrate.c +28 -0

+
+	counter->i = 0;
+	counter->magic = 0xdeadbeef;
+
+	if (!error) {
+		write_lock_irq(&migration_space.tree_lock);
+	        error = idr_get_new_above(&migration_idr, counter, 1, &offset);
+
+		if (error < 0)
+			BUG();
+
+		error = radix_tree_insert(&migration_space.page_tree, offset,
+							page);
+
+		if (!error) {
+			page_cache_get(page);
+			SetPageLocked(page);
+			page->private = offset;
+//			page->mapping = &migration_space;
+			SetPageMigration(page);
+		}
+		write_unlock_irq(&migration_space.tree_lock);
+                radix_tree_preload_end();
+
+	}
+
+	return error;
+}

mm/mmigrate.c +5 -0

+		if (!add_to_migration_cache(page, GFP_KERNEL)) {
 			unlock_page(page);
 			return ERR_PTR(-ENOSPC);
 		}
+/*		if (!add_to_swap(page, GFP_KERNEL)) {
+			unlock_page(page);
+			return ERR_PTR(-ENOSPC);
+		} */
 #endif /* CONFIG_SWAP */
 	if ((mapping = page_mapping(page)) == NULL) {
 		/* truncation is in progress */

diff -Nur linux-2.6.9-rc2-mm4.mhp.orig/mm/vmscan.c linux-2.6.9-rc2-mm4.build/mm/vmscan.c

Hi, Marcelo,

Quoted 8 lines

So as I've said before in my opinion moving pages to the swapcache to migrate them is unnacceptable for several reasons. Not to mention live memory defragmentation.

So the following patch, on top of the v2.6 -memoryhotplug tree, creates a migration cache - which is basically a swapcache without using the swap map - it instead uses a on-memory idr structure.

Quoted 2 lines

For that we decrease SWP_TYPE_SHIFT from 5 to 4, and use that now-free bit to indicate pte's which point to pages on the migration cache.

I guess it would be better to reserve one swap type for the migration cache instead of reserving the bit to reduce the impact of the maximum number of swap types.
However, I think your approach is good enough for the first implementation.

Quoted 1 line

Comments are very welcome

I'll continue to check the code.

Quoted 7 lines

diff -Nur linux-2.6.9-rc2-mm4.mhp.orig/include/linux/swapops.h linux-2.6.9-rc2-mm4.build/include/linux/swapops.h

include/linux/swapops.h +0 -0

@@ -19,7 +19,7 @@
 {
 	swp_entry_t ret;
 

include/linux/swapops.h line 22

Quoted 2 lines

include/linux/swapops.h +1 -1

-	ret.val = (type << SWP_TYPE_SHIFT(ret)) |
+	ret.val = type << SWP_TYPE_SHIFT(ret) |

I guess it's just for cleanups to remove the brackets, right?

mm/memory.c line 1446

Quoted 11 lines

diff -Nur linux-2.6.9-rc2-mm4.mhp.orig/mm/memory.c linux-2.6.9-rc2-mm4.build/mm/memory.c

mm/memory.c +0 -1

@@ -1433,7 +1441,6 @@
 		inc_page_state(pgmajfault);
 		grab_swap_token();
 	}
-
 	mark_page_accessed(page);
 	lock_page(page);
 	if (!PageSwapCache(page)) {

I think the previous line should be
if (!PageSwapCache(page) && !PageMigration(page)) {

This line means to redo everything from the beginning if the page is not either in the swap-cache or in the migration-cache.

Quoted 18 lines

mm/memory.c +7 -0

@@ -1442,6 +1449,13 @@
 		page_cache_release(page);
 		goto again;
 	}
+	}
+
+
+	if (pte_is_migration(orig_pte)) {
+		mark_page_accessed(page);
+		lock_page(page);
+	}
 
 	/*
 	 * Back out if somebody else faulted in this pte while we

diff -Nur linux-2.6.9-rc2-mm4.mhp.orig/mm/mmigrate.c linux-2.6.9-rc2-mm4.build/mm/mmigrate.c

mm/mmigrate.c line 121

Quoted 6 lines

mm/mmigrate.c +5 -0

 
+int migration_remove_entry(swp_entry_t entry)
+{
+	struct page *page;
+	
+	page = find_trylock_page(&migration_space, entry.val);

I guess there exits a race condition here.
If the page is locked unfortunately at this moment, who release it? Another process on another CPU may be handling page-fault against the page if it is shared with other processes.

The following code would be better?

	page = find_get_page(&migration_space, entry.val);
	if (page)
		lock_page(page);

Quoted 24 lines

mm/mmigrate.c +22 -0

+
+
+	if (printk_ratelimit())
+		printk(KERN_ERR "remove_from_migration_cache!!\n");
+
+
+	if (page) {
+		migration_remove_reference(page);
+		unlock_page(page);
+		page_cache_release(page);
+	}
+
+}
 
 
+int add_to_migration_cache(struct page *page, int gfp_mask) 
+{
+	int error, offset;
+	struct counter *counter;
+
+	BUG_ON(PageSwapCache(page));
+	BUG_ON(PagePrivate(page));
+	BUG_ON(PageMigration(page));
+

mm/mmigrate.c line 169

Quoted 2 lines

mm/mmigrate.c +2 -0

+        if (idr_pre_get(&migration_idr, GFP_ATOMIC) == 0)
+                return -ENOMEM;

GFP_KERNEL would be appropriate for the memory migration code, because the swap-code will make free pages in case of low memory. This is one of the different points from the swap-code, which can't specify such gfp_mask, as no one can prepare free pages for it.

mm/mmigrate.c line 173

Quoted 5 lines

mm/mmigrate.c +4 -0

+
+	error = radix_tree_preload(gfp_mask);
+
+	counter = kmalloc(sizeof(struct counter), GFP_KERNEL);

kmalloc() should be called before radix_tree_preload() because radix_tree_preload() disables preemption not to switch other processes during handling radix trees. However kmalloc() with GFP_KERNEL may be blocked to break this assumption.

Quoted 28 lines

mm/mmigrate.c +28 -0

+
+	counter->i = 0;
+	counter->magic = 0xdeadbeef;
+
+	if (!error) {
+		write_lock_irq(&migration_space.tree_lock);
+	        error = idr_get_new_above(&migration_idr, counter, 1, &offset);
+
+		if (error < 0)
+			BUG();
+
+		error = radix_tree_insert(&migration_space.page_tree, offset,
+							page);
+
+		if (!error) {
+			page_cache_get(page);
+			SetPageLocked(page);
+			page->private = offset;
+//			page->mapping = &migration_space;
+			SetPageMigration(page);
+		}
+		write_unlock_irq(&migration_space.tree_lock);
+                radix_tree_preload_end();
+
+	}
+
+	return error;
+}

mm/mmigrate.c line 574

Quoted 7 lines

mm/mmigrate.c +1 -2

@@ -399,11 +571,15 @@
 	 * Put the page in a radix tree if it isn't in the tree yet.
 	 */
 #ifdef CONFIG_SWAP
-	if (PageAnon(page) && !PageSwapCache(page))
-		if (!add_to_swap(page, GFP_KERNEL)) {
+	if (PageAnon(page) && !PageSwapCache(page) && !PageMigration(page))

I guess calling BUG() would be good if the page is already in the migration cache.

Quoted 12 lines

mm/mmigrate.c +5 -0

+		if (!add_to_migration_cache(page, GFP_KERNEL)) {
 			unlock_page(page);
 			return ERR_PTR(-ENOSPC);
 		}
+/*		if (!add_to_swap(page, GFP_KERNEL)) {
+			unlock_page(page);
+			return ERR_PTR(-ENOSPC);
+		} */
 #endif /* CONFIG_SWAP */
 	if ((mapping = page_mapping(page)) == NULL) {
 		/* truncation is in progress */

mm/vmscan.c line 357

Quoted 9 lines

diff -Nur linux-2.6.9-rc2-mm4.mhp.orig/mm/vmscan.c linux-2.6.9-rc2-mm4.build/mm/vmscan.c

mm/vmscan.c +1 -1

@@ -354,7 +354,7 @@
 		 * Anonymous process memory has backing store?
 		 * Try to allocate it some swap space here.
 		 */
-		if (PageAnon(page) && !PageSwapCache(page)) {
+		if (PageAnon(page) && !PageSwapCache(page) && !PageMigration(page)) {

BUG_ON(PageMigration(page)) would be better, because it must not exist in the LRU. Target pages to migrate must have been removed from the LRU lists in advance, so that the swap code never grabs them.

mm/vmscan.c line 360

Quoted 3 lines

mm/vmscan.c +0 -0

 			if (!add_to_swap(page, GFP_ATOMIC))
 				goto activate_locked;
 		}

Quoted 4 lines · Hirokazu Takahashi

I guess it would be better to reserve one swap type for the migration cache instead of reserving the bit to reduce the impact of the maximum number of swap types.

By reserving one swap type we would also use a bit. Using a swap type is the same thing as using a bit in the swap pagetableentry. (the swap type has 5 bits reserved for swap devices, 2^5 = 32 swap devices).

Quoted 5 lines · Marcelo Tosatti

Quoted 4 lines · Hirokazu Takahashi

I guess it would be better to reserve one swap type for the migration cache instead of reserving the bit to reduce the impact of the maximum number of swap types.

I thought the same ...

Quoted 3 lines

By reserving one swap type we would also use a bit. Using a swap type is the same thing as using a bit in the swap pagetableentry. (the swap type has 5 bits reserved for swap devices, 2^5 = 32 swap devices).

... and don't understand your response.

Reserving a swap type leaves 31 swap devices for normal use, okay; but reserving a bit leaves only 16 swap devices for normal use.

Quoted 9 lines · Marcelo Tosatti

Quoted 5 lines · Hirokazu Takahashi

Quoted 4 lines

I guess it would be better to reserve one swap type for the migration cache instead of reserving the bit to reduce the impact of the maximum number of swap types.

I thought the same ...

Quoted 8 lines

Quoted 3 lines

By reserving one swap type we would also use a bit. Using a swap type is the same thing as using a bit in the swap pagetableentry. (the swap type has 5 bits reserved for swap devices, 2^5 = 32 swap devices).

... and don't understand your response.

Reserving a swap type leaves 31 swap devices for normal use, okay; but reserving a bit leaves only 16 swap devices for normal use.

Oh stupid idiot I am! Of course, we can then remove "pte_is_migration" (and all the related pte handling code).

Added to TODO list.

If anyone wants to contribute that it would be cool cause I'm quite busy with other stuff right now.

Hi,

Quoted 19 lines · Hugh Dickins

Quoted 9 lines · Marcelo Tosatti

Quoted 5 lines · Hirokazu Takahashi

Quoted 4 lines

I guess it would be better to reserve one swap type for the migration cache instead of reserving the bit to reduce the impact of the maximum number of swap types.

I thought the same ...

Quoted 8 lines

Quoted 3 lines

By reserving one swap type we would also use a bit. Using a swap type is the same thing as using a bit in the swap pagetableentry. (the swap type has 5 bits reserved for swap devices, 2^5 = 32 swap devices).

... and don't understand your response.

Reserving a swap type leaves 31 swap devices for normal use, okay; but reserving a bit leaves only 16 swap devices for normal use.

Quoted 7 lines

Oh stupid idiot I am! Of course, we can then remove "pte_is_migration" (and all the related pte handling code).

Added to TODO list.

If anyone wants to contribute that it would be cool cause I'm quite busy with other stuff right now.

The following code is my simple idea, which might help you.

#define MIGRATION_TYPE (MAX_SWAPFILES - 1)

static inline int pte_is_migration(pte_t pte)

{
	unsigned long swp_type;
	swp_entry_t arch_entry;

	arch_entry = __pte_to_swp_entry(pte);

	swp_type = __swp_type(arch_entry);

	return swp_type == MIGRATION_TYPE;
}

static inline int PageMigration(page)

{ 
      swp_entry_t entry = { .val = page->private,};
      return (PageSwapCache(page) && swp_type(entry) == MIGRATION_TYPE);
}

Oh and with that we no longer need PG_migration bit, but, page->private does not contain swp_type information (MIGRATION_TYPE bit) in it. Its simply an offset counting from 0 increasing sequentially.

ANDing migration type bit into the offset should work.

Quoted 6 lines · Marcelo Tosatti

Oh and with that we no longer need PG_migration bit, but, page->private does not contain swp_type information (MIGRATION_TYPE bit) in it. Its simply an offset counting from 0 increasing sequentially.

ANDing migration type bit into the offset should work.

I haven't looked, but wouldn't it be a lot easier to use the normal swap allocation code rather than going such a different idr way here?

BTW, while I was reading the code, I wondered:

struct swap_info_struct swap_info[MAX_SWAPFILES];

This array should be created dynamically. Worth
the trouble?