0/4 Migration Cache Overview

RFC Lee Schermerhorn 4 participants 9 messages Feb 17, 2006 – Feb 21, 2006 Memory management

Share & tools

Lee Schermerhorn

author

2006-02-17 15:36 UTC #0 lore raw

Migration Cache "V8" 0/4 -- Overview

Now that Christoph's direct migration work is in Linus' tree, I thought I'd attempt to restart the Migration Cache discussion with this set of patches. They work, to the extent that I've tested them, but are still a bit rough around the edges.

Background:

Marcello Tosatti introduced the migration cache back in Oct04 to obviate use of swap space for anon pages during page migration. He posted the original migration patch [let's call this V0] to the linux-mm list:

	http://marc.theaimsgroup.com/?l=linux-mm&m=109779128211239&w=4

with an update on 250ct04 [V1]

	http://marc.theaimsgroup.com/?l=linux-mm&m=109874962629347&w=4

Hirokazu Takahashi and Ray Bryant tested and updated the patch in Nov/Dec04 and through Jan/Feb'05. Let's call these V2 and V3.

Note: there was quite a bit of chatter in the mailing lists regarding the migration cache during this time frame. I don't mean to slight anyone by failing to credit them with additional updates. I just didn't reread all of the messages in preparing this overview. But, I'll skip over V4 in case I forgot someone...

Marcello posted a final [?] updated patch [V5] to the lhms-devel list in April'05:

	http://marc.theaimsgroup.com/?l=lhms-devel&m=111273117528472&w=4

I started working with the migration cache in August'05 and got it working with Ray Bryant's "manual page migration" patches layered on the memory hotplug migration patches. I posted this version [V6] in a series of 4 patches on 1Sep05:

	http://marc.theaimsgroup.com/?l=lhms-devel&m=112558724708190&w=4

After a brief exchange with Marcello, I reworked the migration cache to hide it, to the extent possible, behind the existing swap cache APIs. I posted this work [V7] to lhms-devel on 20Sep05:

	http://marc.theaimsgroup.com/?l=lhms-devel&m=112724852823727&w=4

In mid Oct'05, Christoph Lameter began work on a new memory migration implementation and the community effectively abandoned the previous memory hotplug and manual page migration patches. Now that Christoph's migration work has been submitted upstream, I have ported the migration cache patches to work with his direct migration in 2.6.16-rc3-mm1. I'm calling this "V8".

How it works:

The migration cache is a pseudo-swap device which steals the maximum swap device id. It implements the pseudo-swap space using the kernel lib 'idr' facility. Anonymous pages that are not already in swap space are moved to the migration cache during migration. The ptes referencing the pages are replaced with migration cache ptes consisting of the migration swap type and the "offset" into the migration cache. The offset is generated by "idr_get_new_above()".

After a page is migrated, 'remove_from_swap()' will walk the anon vma vma list and replace the cache pte entry with a real pte for the new page. Because migration cache ptes look like swap cache ptes, this "just works".

The migration cache differs from the swap cache in another way: The cache itself does not hold a reference on the entry. Thus, when the last migration pte is replaced by a real [or swap pte--more on this below] and the reference held by that pte is removed, the migration cache entry is removed. That is, pages do not hang around in the migration cache when there are no ptes referencing the cache entry as they can do with the swap cache.

One complication in all of this is when direct migration of an anon page falls back to swapping out the pages. If the page had not already been in the swap cache, it will have been added to the migration cache. To swap the page out, we need to move if from the migration cache to the swap cache. Note that this would also be required if shrink_list() encounters a page in the migration cache. Both the page migration code and shrink_list() have been modified to call a new function "migration_move_to_swap()" in these cases. Marcello mentions the need to do this in his first migration cache post linked above.

Moving a migration cache page to the swap cache involves allocating a swap entry and replacing all of the migration ptes referencing the entry with swap ptes. This works similar to 'remove_from_swap()' mentioned above and, in fact, uses the same underlying mechanism [the "unuse_vma()..." stack in mm/swapfile.c] that has been updated for this purpose.

A word about testing:

I have done some simple sanity testing of these patches against 2.6.16-rc3-mm1. The test results appear to be the same with and without the migration cache patches applied. However, I have not tested any error paths--specifically, the "fall back to swap" and moving of migration cache pages to the swap cache. Much work remains.

The Patches:

migration-cache-01-core-implementation.patch

As the name indicates, this is the core implementation of the migration cache. In the V1-V7 patches, the migration cache resided in mm/mmigrate.c. That file does not exist in the new migration implementation, so I've moved the migration cache to mm/swap_state.c with many of the other swap cache functions.

I have had to do some rework of the basic implementation to support the move from migration to swap cache, and to be able to call migration cache functions from swap cache functions with proper locking. I have also removed some [not all?] functions that were used by the previous hotplug/manual migration effort that are not needed in this implementation. Some cleanup still required.

migration-cache-02-add-mm-checks.patch

This patch add the necessary checks for whether a page that appears to be in the swap cache is really in the migration cache. Most of these checks are hidden behind the normal swap interfaces, and are, thus, limited to the swap sources. However, a couple of them spill over into mm/memory.c and vmscan.c.

I could have avoided patching mm/memory.c if swapin_readahead() were in mm/swap_state.c along with its cousin read_swap_cache_async() instead of in mm/memory.c. Anyone know why this is the case?

migration-cache-03-move-to-swap.patch

This patch modifies the swapfile.c "unuse_*" stack to support moving pages from migration cache to swap cache in case we have to "fall back to swap". This also allows vmscan.c:shrink_list() to move migration cache pages to swap cache when/if it wants to swap them out. shrink_list() should only find anon pages in the migration cache when/if we implement lazy page migration.

Because this path is untested and because it wreaks minor havoc on the "unuse_*" stack, you should pay special attention to this patch, if you're paying attention at all...

QUESTION: what does this mean for tasks that fault on the migration cache pte while we're moving the page to the swap cache? I think that if they manage to look up the page in the migration cache and get a reference on it, the current test in do_swap_page() will work OK. However, is there a potential race between the time __handle_mm_fault() fetches the pte from the page table and when do_swap_page() does the cache lookup? [in a preemptible kernel?]

migration-cache-04-use-for-direct-migration.patch

This patch hooks the migration cache up to direct page migration. If a destination page exists, and the old page is not already in the swap cache, we place it in the migration cache instead. If we need to fall back to swap(), we must move the page from the migration cache to the swap cache.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Christoph Lameter

2006-02-17 16:22 UTC #1 lore raw

Quoted 3 lines · Lee Schermerhorn

Marcello Tosatti introduced the migration cache back in Oct04 to obviate use of swap space for anon pages during page migration. He posted the original migration patch [let's call this V0] to the linux-mm list:

Could add a justification of this feature? What is the benefit of having a migration cache instead of using swap pte (current migration is not really using swap space per se)?

Quoted 3 lines

migration work has been submitted upstream, I have ported the migration cache patches to work with his direct migration in 2.6.16-rc3-mm1. I'm calling this "V8".

Direct migration is in Linus' tree and I am not aware of anything necessary in mm.

Quoted 10 lines

One complication in all of this is when direct migration of an anon page falls back to swapping out the pages. If the page had not already been in the swap cache, it will have been added to the migration cache. To swap the page out, we need to move if from the migration cache to the swap cache. Note that this would also be required if shrink_list() encounters a page in the migration cache. Both the page migration code and shrink_list() have been modified to call a new function "migration_move_to_swap()" in these cases. Marcello mentions the need to do this in his first migration cache post linked above.

We could potentially remove the ability to fall back to swap or add an option to disallow the fallback. This is also necessary if we want to migration mlocked memory. Maybe this could simplify the code?

Quoted 8 lines

QUESTION: what does this mean for tasks that fault on the migration cache pte while we're moving the page to the swap cache? I think that if they manage to look up the page in the migration cache and get a reference on it, the current test in do_swap_page() will work OK. However, is there a potential race between the time __handle_mm_fault() fetches the pte from the page table and when do_swap_page() does the cache lookup? [in a preemptible kernel?]

Yes there is since handle_mm_fault accesses the pte without locking. do_swap_page acquires the lock and will then recheck if the pte is the same. If anything happened in between it should redo the page fault.

Lee Schermerhorn

author

2006-02-17 16:59 UTC #2 lore raw

Quoted 9 lines · Christoph Lameter

Quoted 3 lines · Lee Schermerhorn
Marcello Tosatti introduced the migration cache back in Oct04 to obviate use of swap space for anon pages during page migration. He posted the original migration patch [let's call this V0] to the linux-mm list:
Could add a justification of this feature? What is the benefit of having a migration cache instead of using swap pte (current migration is not really using swap space per se)?

I think Marcello covered that in his original posts, which I linked. I can go back and extract his arguments. My primary interest is for "lazy page migration" where anon pages can hang around the the cache until the task faults them in [possibly migrating] or exits, if ever. I think the desire to avoid using swap for this case is even stronger.

Quoted 7 lines

Quoted 4 lines
migration work has been submitted upstream, I have ported the migration cache patches to work with his direct migration in 2.6.16-rc3-mm1. I'm calling this "V8".
Direct migration is in Linus' tree and I am not aware of anything necessary in mm.

Correct. But, I figured if any testing were going to be done, it would be against the mm tree, so I diffed against that. I don't know how much the mm tree differs from the corresponding 16-rc? tree in the areas touched
by these patches.

Quoted 12 lines

Quoted 11 lines
One complication in all of this is when direct migration of an anon page falls back to swapping out the pages. If the page had not already been in the swap cache, it will have been added to the migration cache. To swap the page out, we need to move if from the migration cache to the swap cache. Note that this would also be required if shrink_list() encounters a page in the migration cache. Both the page migration code and shrink_list() have been modified to call a new function "migration_move_to_swap()" in these cases. Marcello mentions the need to do this in his first migration cache post linked above.

Quoted 3 lines

We could potentially remove the ability to fall back to swap or add an option to disallow the fallback. This is also necessary if we want to migration mlocked memory. Maybe this could simplify the code?

Possibly. I think we'd still want to be able to do this for vmscan. Again, because anon pages could languish in the migration cache indefinitely.

Quoted 10 lines

Quoted 9 lines
QUESTION: what does this mean for tasks that fault on the migration cache pte while we're moving the page to the swap cache? I think that if they manage to look up the page in the migration cache and get a reference on it, the current test in do_swap_page() will work OK. However, is there a potential race between the time __handle_mm_fault() fetches the pte from the page table and when do_swap_page() does the cache lookup? [in a preemptible kernel?]

Quoted 4 lines

Yes there is since handle_mm_fault accesses the pte without locking. do_swap_page acquires the lock and will then recheck if the pte is the same. If anything happened in between it should redo the page fault.

I thought so, but hadn't thought of an efficient check for the fault handlers. I'm thinking that if the fault handler doesn't find the page in the cache and the page's private data doesn't match the pte [after appropriate conversion], the handler could return -EAGAIN causing handle_mm_fault to refetch the pte. I guess if the handler doesn't find the page in the cache, this is the slow path anyway, so maybe efficiency isn't such a concern. It will require converion of the pte to swp_entry or vice versa, right?

Christoph Lameter

2006-02-17 17:12 UTC #3 lore raw

Quoted 9 lines · Lee Schermerhorn

Quoted 3 lines
Could add a justification of this feature? What is the benefit of having a migration cache instead of using swap pte (current migration is not really using swap space per se)?
I think Marcello covered that in his original posts, which I linked. I can go back and extract his arguments. My primary interest is for "lazy page migration" where anon pages can hang around the the cache until the task faults them in [possibly migrating] or exits, if ever. I think the desire to avoid using swap for this case is even stronger.

I am bit confused. A task faults in a page from the migration cache? Isnt this swap behavior? I thought the migration cache was just to avoid using swap page numbers for the intermediate pte values during migration?

You are moving the page when it is faulted in?

Including Marcelo's rationale may help understanding here. I read it a while back but I do not remember the details. Please give us an overview.

Quoted 11 lines

Quoted 3 lines
Yes there is since handle_mm_fault accesses the pte without locking. do_swap_page acquires the lock and will then recheck if the pte is the same. If anything happened in between it should redo the page fault.
I thought so, but hadn't thought of an efficient check for the fault handlers. I'm thinking that if the fault handler doesn't find the page in the cache and the page's private data doesn't match the pte [after appropriate conversion], the handler could return -EAGAIN causing handle_mm_fault to refetch the pte. I guess if the handler doesn't find the page in the cache, this is the slow path anyway, so maybe efficiency isn't such a concern. It will require converion of the pte to swp_entry or vice versa, right?

If the migration cache is only used for intermediary pte values then the fault handler should wait until the migration of the page is complete. do_swap_page acquired the page lock after checking the pte. Thus the process should block until migration is complete.

It seems to me that what you are trying to accomplish here is already provided for by the current swap based code. You just need to control the swap in behavior in order to make lazy migration work right. But then I guess I am missing something.

Nick Piggin

2006-02-21 03:18 UTC #4 lore raw

Quoted 5 lines · Christoph Lameter

Quoted 2 lines · Lee Schermerhorn
Quoted 1 line
Could add a justification of this feature? What is the benefit of having a migration cache instead of using swap pte (current migration is not really using swap space per se)?

Quoted 9 lines

Quoted 4 lines
I think Marcello covered that in his original posts, which I linked. I can go back and extract his arguments. My primary interest is for "lazy page migration" where anon pages can hang around the the cache
until the task faults them in [possibly migrating] or exits, if ever.
I think the desire to avoid using swap for this case is even stronger.
I am bit confused. A task faults in a page from the migration cache? Isnt this swap behavior? I thought the migration cache was just to avoid using swap page numbers for the intermediate pte values during migration?

It really does seem like the swapcache does everything required. The swapcache is just a pagecache mapping for anonymous pages. Adding an extra "somethingcache" for anonymous pages shouldn't add anything. I guess I'm missing something as well.

Quoted 4 lines

You are moving the page when it is faulted in?
Including Marcelo's rationale may help understanding here. I read it a while back but I do not remember the details. Please give us an overview.

Yes, this should always be done in patches themselves rather than linking to other posts (within reason), because it gives you something to reply to and it gets into the changeset history.

Signature · 8 lines

SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Marcelo Tosatti

2006-02-21 18:40 UTC #5 lore raw

Hi,

Quoted 15 lines · Nick Piggin

Quoted 14 lines · Christoph Lameter
Quoted 9 lines · Lee Schermerhorn
Quoted 3 lines
Could add a justification of this feature? What is the benefit of having a migration cache instead of using swap pte (current migration is not really using swap space per se)?
I think Marcello covered that in his original posts, which I linked. I can go back and extract his arguments. My primary interest is for "lazy page migration" where anon pages can hang around the the cache until the task faults them in [possibly migrating] or exits, if ever. I think the desire to avoid using swap for this case is even stronger.

Quoted 3 lines

Quoted 3 lines
I am bit confused. A task faults in a page from the migration cache? Isnt this swap behavior? I thought the migration cache was just to avoid using swap page numbers for the intermediate pte values during migration?

Exactly, the aim of the migration cache is to avoid using swap map entries.

Quoted 4 lines

It really does seem like the swapcache does everything required. The swapcache is just a pagecache mapping for anonymous pages. Adding an extra "somethingcache" for anonymous pages shouldn't add anything. I guess I'm missing something as well.

The idea was to create a "partition" inside the swapcache which allows for mapping+offset->pfn translation _without_ actually occupying space in the swap map (an idr table is used instead).

But apparently Christoph's mechanism adds the PFN number into the page table entry itself, thus fulfilling the requirement for "mapping+offset"->pfn indexing required for removal of pages underneath a living process. Is that right?

Cheers

Christoph Lameter

2006-02-21 18:04 UTC #6 lore raw

Quoted 8 lines · Marcelo Tosatti

The idea was to create a "partition" inside the swapcache which allows for mapping+offset->pfn translation _without_ actually occupying space in the swap map (an idr table is used instead).
But apparently Christoph's mechanism adds the PFN number into the page table entry itself, thus fulfilling the requirement for "mapping+offset"->pfn indexing required for removal of pages underneath a living process. Is that right?

Right. Swap ptes contain the index into swap space which I am using to preserve the information contained in the pte's of anonymous pages. Thus the existing swap ptes couild be used. There were just a few minor modifications to the swap functions required.

Lee Schermerhorn

author

2006-02-21 18:49 UTC #7 lore raw

Quoted 11 lines · Christoph Lameter

Quoted 8 lines · Marcelo Tosatti
The idea was to create a "partition" inside the swapcache which allows for mapping+offset->pfn translation _without_ actually occupying space in the swap map (an idr table is used instead).
But apparently Christoph's mechanism adds the PFN number into the page table entry itself, thus fulfilling the requirement for "mapping+offset"->pfn indexing required for removal of pages underneath a living process. Is that right?

Quoted 5 lines

Right. Swap ptes contain the index into swap space which I am using to preserve the information contained in the pte's of anonymous pages. Thus the existing swap ptes couild be used. There were just a few minor modifications to the swap functions required.

Are the swap ptes used for migrating pages still reserving swap space on real swap devices? I thought this was what the migration cache was trying to avoid. Now each running instance of direct migration limits itself to MIGRATE_CHUNK_SIZE [currently] 256 pages, so if the system has much swap space at all, this shouldn't place too much of a load on swap space. But, it does require that one have SOME swap space to migrate, right?

Lee

Christoph Lameter

2006-02-21 19:19 UTC #8 lore raw

Quoted 7 lines · Lee Schermerhorn

Are the swap ptes used for migrating pages still reserving swap space on real swap devices? I thought this was what the migration cache was trying to avoid. Now each running instance of direct migration limits itself to MIGRATE_CHUNK_SIZE [currently] 256 pages, so if the system has much swap space at all, this shouldn't place too much of a load on swap space. But, it does require that one have SOME swap space to migrate, right?

Right. If the kernel configured to not include swap functionality then the kernel will not include page migration capabilities.