Guest page hinting: volatile page cache.
Subsystems (9)
PATCH 3/9 Guest page hinting: volatile page cache.
From: Martin Schwidefsky <[email protected]>
From: Hubertus Franke <[email protected]>
From: Himanshu Raj <[email protected]>
[patch 3/9] Guest page hinting: volatile page cache.
A new page state "volatile" is introduced that is used for clean, uptodate page cache pages. The host can choose to discard volatile pages as part of its vmscan operation instead of writing them to the hosts paging device. This greatly reduces the i/o needed by the host if it gets under memory pressure. The guest system doesn't notice that a volatile page is gone until it tries to access the page or tries to make it stable again. Then the guest needs to remove the page from the cache. A guest access to a discarded page causes the host to deliver a new kind of fault to the guest - the discard fault. After the guest has removed the page it is reloaded from the backing device.
The code added by this patch uses the volatile state for all page cache pages, even for pages which are referenced by writable ptes. The host needs to be able to check the dirty state of the pages. Since the host doesn't know where the page table entries of the guest are located, the volatile state as introduced by this patch is only usable on architectures with per-page dirty bits (s390 only). For per-pte dirty bit architectures some additional code is needed.
The interesting question is where to put the state transitions between the volatile and the stable state. The simple solution is the make a page stable whenever a lookup is done or a page reference is derived from a page table entry. Attempts to make pages volatile are added at strategic points. Now what are the conditions that prevent a page from being made volatile? There are 10 conditions:
1) The page is reserved. Some sort of special page.
2) The page is marked dirty in the struct page. The page content is more recent than the data on the backing device. The host cannot access the linux internal dirty bit so the page needs to be stable.
3) The page is in writeback. The page content is needed for i/o.
4) The page is locked. Someone has exclusive access to the page.
5) The page is anonymous. Swap cache support needs additional code.
6) The page has no mapping. No backing, the page cannot be recreated.
7) The page is not uptodate.
8) The page has private information. try_to_release_page can fail, e.g. in case the private information is journaling data. The discard fault need to be able to remove the page.
9) The page is already discarded.
10) The page map count is not equal to the page reference count - 1. The discard fault handler can remove the page cache reference and all mappers of a page. It cannot remove the page reference for any other user of the page.
The transitions to stable are done by find_get_pages() and its variants, in get_user_pages if called with a pages parameter, by copy-on-write in do_wp_page, and by the early copy-on-write in do_no_page. To make enough pages discardable by the host an attempt to do the transition to volatile state is done when a page gets unlocked (unlock_page), when writeback has finished (test_clear_page_dirty), when the page reference counter is decreased (put_page_testzero), and when the page map counter is increased (page_add_file_rmap).
All page references acquired with find_get_page and friends can be used to access the page frame content. A page reference grabbed from a page table cannot be used to access the page content. A page_make_stable needs to be done first and if that fails the page needs to get discarded. That removes the page table entry as well.
Two new page flags are added. To guard against concurrent page state updates the PG_state_change flag is used. It prevents that a transition to the stable state can "overtake" a transition to volatile state. If page_make_volatile has already done the 10 checks it will issue the state change primitive. If in the meantime on of the conditions has changed the user that requires the page in stable state will have to wait until the make volatile operation has finished. The make volatile operation does not wait for the PG_state_change if make stable has set the bit. Instead the attempt to make the page volatile fails. The reason is that test_clear_page_dirty is called from interrupt context and waiting for the bit might dead-lock.
The second new page flag is the PG_discarded bit. This bit is set for discarded pages. It prevents multiple removes of a page from the page cache due to concurrent discard faults and/or normal page removals. It also prevents the re-add of isolated pages to the lru list in vmscan if the page has been discarded while it was not on the lru list.
Another noticable change is that the first few lines of code in try_to_unmap_one that calculates the address from the page and the vma is moved out of try_to_unmap_one to the callers. This is done to make try_to_unmap_one usable for the removal of discarded pages in page_unmap_all.
---
fs/buffer.c | 1 include/linux/mm.h | 8 + include/linux/page-flags.h | 13 +++ include/linux/page-states.h | 55 +++++++++++++ include/linux/pagemap.h | 1 mm/Makefile | 1 mm/filemap.c | 73 +++++++++++++++++- mm/memory.c | 44 ++++++++++ mm/page-discard.c | 178 ++++++++++++++++++++++++++++++++++++++++++++ mm/page-writeback.c | 3 mm/page_alloc.c | 3 mm/rmap.c | 68 ++++++++++++++-- mm/vmscan.c | 56 +++++++++---- 13 files changed, 471 insertions(+), 33 deletions(-)
fs/buffer.c +1 -0
@@ -105,6 +105,7 @@ __clear_page_buffers(struct page *page) {ClearPagePrivate (page);set_page_private (page,0 ); +page_make_volatile (page,2 );page_cache_release (page); }
include/linux/mm.h +7 -1
@@ -308,11 +308,17 @@ struct page {/* * Drop a ref, return true if the refcount fell to zero (the page has no users) +* put_page_testzero checks if the page can be made volatile if the page +* still has users and guest page hinting is enabled. */ static inline int put_page_testzero (struct page *page) { +int ret;VM_BUG_ON (atomic_read (&page->_count) ==0 ); -return atomic_dec_and_test (&page->_count); + ret =atomic_dec_and_test (&page->_count); +if (!ret) +page_make_volatile (page,1 ); +return ret; }/*
include/linux/page-flags.h +13 -0
@@ -105,6 +105,9 @@#define PG_uncached 31/* Page has been mapped as uncached */ #endif +#define PG_state_change 21/* HV page state is changing. */ +#define PG_discarded 22/* HV page has been discarded. */ +/* * Manipulation of page state flags */
@@ -254,6 +257,16 @@#define SetPageReadahead (page) set_bit(PG_readahead, &(page)->flags)#define TestClearPageReadahead (page) test_and_clear_bit(PG_readahead, &(page)->flags) +#define PageStateChange (page) test_bit(PG_state_change, &(page)->flags) +#define ClearPageStateChange (page) clear_bit(PG_state_change, &(page)->flags) +#define TestSetPageStateChange (page) \ + test_and_set_bit(PG_state_change, &(page)->flags) + +#define PageDiscarded (page) test_bit(PG_discarded, &(page)->flags) +#define ClearPageDiscarded (page) clear_bit(PG_discarded, &(page)->flags) +#define TestSetPageDiscarded (page) \ + test_and_set_bit(PG_discarded, &(page)->flags) +struct page ;/* forward declaration */ int test_clear_page_dirty (struct page *page);
include/linux/pagemap.h +1 -0
@@ -114,6 +114,7 @@ int add_to_page_cache_lru(struct page *p unsigned long index, gfp_t gfp_mask);extern void remove_from_page_cache (struct page *page);extern void __remove_from_page_cache (struct page *page); +extern void __remove_from_page_cache_nocheck (struct page *page);/* * Return byte-offset into filesystem object for page.
include/linux/page-states.h +55 -0
72 lines not on this page · raw message
mm/filemap.c +69 -4
123 lines not on this page · raw message
mm/Makefile +1 -0
@@ -28,3 +28,4 @@ obj-$(CONFIG_MEMORY_HOTPLUG) += memory_h obj-$(CONFIG_FS_XIP) += filemap_xip.o obj-$(CONFIG_MIGRATION) += migrate.o obj-$(CONFIG_SMP) += allocpercpu.o +obj-$(CONFIG_PAGE_STATES) += page-discard.o
mm/memory.c +42 -2
88 lines not on this page · raw message
mm/page_alloc.c +2 -1
@@ -215,7 +215,8 @@ static void bad_page(struct page *page)1 << PG_slab |1 << PG_swapcache |1 << PG_writeback | - 1 << PG_buddy ); +1 << PG_buddy | + 1 << PG_discarded );set_page_count (page,0 );reset_page_mapcount (page); page->mapping =NULL ;
mm/page-discard.c +178 -0
178 lines not on this page · raw message
mm/page-writeback.c +3 -0
@@ -858,6 +858,7 @@ int test_clear_page_dirty(struct page *pradix_tree_tag_clear (&mapping->page_tree,page_index (page),PAGECACHE_TAG_DIRTY ); +page_make_volatile (page,2 );write_unlock_irqrestore (&mapping->tree_lock, flags);/* * We can continue to use `mapping' here because the
@@ -924,6 +925,8 @@ int test_clear_page_writeback(struct pagpage_index (page), PAGECACHE_TAG_WRITEBACK);write_unlock_irqrestore (&mapping->tree_lock, flags); +if (ret) +page_make_volatile (page,2 ); }else { ret =TestClearPageWriteback (page); }
mm/rmap.c +60 -8
114 lines not on this page · raw message
mm/vmscan.c +39 -17
76 lines not on this page · raw message
Are all of the un/likely()s in here really needed?
-- Dave
include/linux/page-flags.h line 109
Quoted 2 lines · Martin Schwidefsky
include/linux/page-flags.h +2
-0+#define PG_state_change 21/* HV page state is changing. */ +#define PG_discarded 22/* HV page has been discarded. */
We're already desperately short on page flags on 32-bit architectures. It seems a wee bit silly to add two arch-generic flags for what is a very specialized arch-specific feature at this point.
I know that there are 32-bit s390 kernels, but would this be a reasonable feature to restrict to only 64-bit kernels? That might be a decent compromise.
-- Dave
Quoted 1 line · Dave Hansen
Are all of the un/likely()s in here really needed?
Well, no un/likely is really needed. But they do help the compiler to generate better code. It IS unlikely that a page is discarded.
Signature · 8 lines
blue skies, Martin. Martin Schwidefsky Linux for zSeries Development & Services IBM Deutschland Entwicklung GmbH "Reality continues to ruin my life." - Calvin.
Quoted 6 lines · Dave Hansen
include/linux/page-flags.h line 109
Quoted 2 lines
include/linux/page-flags.h +2
-0+#define PG_state_change 21/* HV page state is changing. */ +#define PG_discarded 22/* HV page has been discarded. */ We're already desperately short on page flags on 32-bit architectures. It seems a wee bit silly to add two arch-generic flags for what is a very specialized arch-specific feature at this point.
There are even three additional page flags if you apply the full set of patches.
Quoted 3 lines
I know that there are 32-bit s390 kernels, but would this be a reasonable feature to restrict to only 64-bit kernels? That might be a decent compromise.
Yes, it is definitly an option to make this a 64-bit only features. In particular because the ESSA instruction that is used on s390 is only available in zarch mode (=64 bit).
Signature · 8 lines
blue skies, Martin. Martin Schwidefsky Linux for zSeries Development & Services IBM Deutschland Entwicklung GmbH "Reality continues to ruin my life." - Calvin.
Quoted 5 lines · Martin Schwidefsky
Quoted 1 line · Dave Hansen
Are all of the un/likely()s in here really needed?
Well, no un/likely is really needed. But they do help the compiler to generate better code. It IS unlikely that a page is discarded.
I know what they're _for_. ;)
I seem to recall people being poked in the past for sprinkling too many of these things around their code. I just wanted to make sure that there was some tangible reason for doing it, other than speculative performance optimization.
-- Dave
Quoted 10 lines · Martin Schwidefsky
Quoted 5 lines · Dave Hansen
include/linux/page-flags.h line 109
Quoted 2 lines
include/linux/page-flags.h +2
-0+#define PG_state_change 21/* HV page state is changing. */ +#define PG_discarded 22/* HV page has been discarded. */ We're already desperately short on page flags on 32-bit architectures. It seems a wee bit silly to add two arch-generic flags for what is a very specialized arch-specific feature at this point.
There are even three additional page flags if you apply the full set of patches.
Quoted 7 lines
Quoted 3 lines
I know that there are 32-bit s390 kernels, but would this be a reasonable feature to restrict to only 64-bit kernels? That might be a decent compromise.
Yes, it is definitly an option to make this a 64-bit only features. In particular because the ESSA instruction that is used on s390 is only available in zarch mode (=64 bit).
Wow. Well there are only 7 extra bits available in 64 bit mode (the FIELDS area is larger on 64bit machines). Do we really, really need three new bits. What are they being used for here.
-apw
Quoted 11 lines · Andy Whitcroft
Quoted 7 lines
Quoted 3 lines
I know that there are 32-bit s390 kernels, but would this be a reasonable feature to restrict to only 64-bit kernels? That might be a decent compromise.
Yes, it is definitly an option to make this a 64-bit only features. In particular because the ESSA instruction that is used on s390 is only available in zarch mode (=64 bit).
Wow. Well there are only 7 extra bits available in 64 bit mode (the FIELDS area is larger on 64bit machines). Do we really, really need three new bits. What are they being used for here.
I have though about alternatives for the page bits hard and long and I could not find a way how to do it without the bits. Their use is:
1) The page-is-discarded (PG_discarded) bit is set for pages that have been recognized as removed by the host. The page needs to be removed from the page cache while there are still page references floating around. To prevent multiple removals from the page cache the discarded bit is needed.
2) The page-state-change (PG_state_change) bit is required to prevent that an make_stable "overtakes" a make_volatile. In order to make a page volatile a number of conditions are check. After this is done the state change will be done. The critical section is the code that performs the checks up to the instruction that does the state change. No make_stable may be done in between. The granularity is per page, to use a global lock like a spinlock would severly limit the scalability for large smp systems.
3) The page-has-a-writable-mapping (PG_writable) bit is set when the first writable pte for a page is established. The page needs to have a different state if a writable pte exists compared to a read-only page. The alternative without the page bit would be to do the state change every time a writable pte is established or to search all ptes of a given page. Both have performance implications.
Overall I fear that the code really needs three additional bits.
Signature · 8 lines
blue skies, Martin. Martin Schwidefsky Linux for zSeries Development & Services IBM Deutschland Entwicklung GmbH "Reality continues to ruin my life." - Calvin.
Quoted 5 lines · Martin Schwidefsky
1) The page-is-discarded (
PG_discarded) bit is set for pages that have been recognized as removed by the host. The page needs to be removed from the page cache while there are still page references floating around. To prevent multiple removals from the page cache the discarded bit is needed.
OK, so the page has data in it, and is in the page cache. The hypervisor kills the page, gives the notification to the kernel that the page has gone away, and the kernel marks PG_discarded. There still might be active references to the page.
So, is the problem trying to communicate with the reference holders that the page is no longer valid? How is this fundamentally different from page truncating?
Quoted 8 lines
2) The page-state-change (
PG_state_change) bit is required to prevent that anmake_stable"overtakes" amake_volatile. In order to make a page volatile a number of conditions are check. After this is done the state change will be done. The critical section is the code that performs the checks up to the instruction that does the state change. Nomake_stablemay be done in between. The granularity is per page, to use a global lock like a spinlock would severly limit the scalability for large smp systems.
How about doing it in the NUMA node? Or the mem_section? Or, even a bit in the mem_map[] for the area guarding the 'struct page' itself? Even a hashed table of locks based on the page address. You just need something that allows _some_ level of concurrency. You certainly never have a number of CPUs which is anywhere close to the number of 'struct page's in the system.
Let me think more about (3).
-- Dave
Quoted 10 lines · Dave Hansen
Quoted 5 lines
1) The page-is-discarded (
PG_discarded) bit is set for pages that have been recognized as removed by the host. The page needs to be removed from the page cache while there are still page references floating around. To prevent multiple removals from the page cache the discarded bit is needed.OK, so the page has data in it, and is in the page cache. The hypervisor kills the page, gives the notification to the kernel that the page has gone away, and the kernel marks
PG_discarded. There still might be active references to the page.
No, the hypervisor does not give the notification immediatly. A discard fault is delivered to the guest if it tries to access a page that has been removed by the host. That is the fundamental difference between a memory ballooner and the guest page hinting.
Quoted 3 lines
So, is the problem trying to communicate with the reference holders that the page is no longer valid? How is this fundamentally different from page truncating?
Truncating is similar but the reaction is different. A truncated page is gone and will not be recreated. A discarded page can be reloaded.
Quoted 9 lines
Quoted 8 lines
2) The page-state-change (
PG_state_change) bit is required to prevent that anmake_stable"overtakes" amake_volatile. In order to make a page volatile a number of conditions are check. After this is done the state change will be done. The critical section is the code that performs the checks up to the instruction that does the state change. Nomake_stablemay be done in between. The granularity is per page, to use a global lock like a spinlock would severly limit the scalability for large smp systems.
Quoted 6 lines
How about doing it in the NUMA node? Or the
mem_section? Or, even a bit in the mem_map[] for the area guarding the 'struct page' itself? Even a hashed table of locks based on the page address. You just need something that allows _some_ level of concurrency. You certainly never have a number of CPUs which is anywhere close to the number of 'struct page's in the system.
NUMA node is not granular enough, mem_section is probably doable. I do not understand the part about the bit in the mem_map[] area, a bit in the page->flags is exactly that, isn't it?
Signature · 8 lines
blue skies, Martin. Martin Schwidefsky Linux for zSeries Development & Services IBM Deutschland Entwicklung GmbH "Reality continues to ruin my life." - Calvin.
Quoted 6 lines · Martin Schwidefsky
3) The page-has-a-writable-mapping (
PG_writable) bit is set when the first writable pte for a page is established. The page needs to have a different state if a writable pte exists compared to a read-only page. The alternative without the page bit would be to do the state change every time a writable pte is established or to search all ptes of a given page. Both have performance implications.
What are the performance implications? Do they completely erase any performance gains that these patches might have given in the first place? Has there been any evaluation of these other two alternatives? As I understand it, carrying out this performance analysis would be very difficult for most of the kernel community to perform.
Keeping a nice count of the number of writable PTEs sounds like something that might be generally useful. Could we split page->_mapcount to keep track of r/o and r/w ptes separately? Or, perhaps a single bit in it can be utilized to replace PG_writable, instead.
-- Dave
Quoted 17 lines · Martin Schwidefsky
Quoted 10 lines · Dave Hansen
Quoted 5 lines
1) The page-is-discarded (
PG_discarded) bit is set for pages that have been recognized as removed by the host. The page needs to be removed from the page cache while there are still page references floating around. To prevent multiple removals from the page cache the discarded bit is needed.OK, so the page has data in it, and is in the page cache. The hypervisor kills the page, gives the notification to the kernel that the page has gone away, and the kernel marks
PG_discarded. There still might be active references to the page.No, the hypervisor does not give the notification immediatly. A discard fault is delivered to the guest if it tries to access a page that has been removed by the host. That is the fundamental difference between a memory ballooner and the guest page hinting.
Quoted 6 lines
Quoted 3 lines
So, is the problem trying to communicate with the reference holders that the page is no longer valid? How is this fundamentally different from page truncating?
Truncating is similar but the reaction is different. A truncated page is gone and will not be recreated. A discarded page can be reloaded.
Can you give me the sequence of events that occur so that we need to set, then check PG_discarded? I'm not getting it.
1. there is good data in a page
...
50. ... and PG_discarded gets set
...
99. We check PG_discarded and ...
Quoted 16 lines
Quoted 9 lines
Quoted 8 lines
2) The page-state-change (
PG_state_change) bit is required to prevent that anmake_stable"overtakes" amake_volatile. In order to make a page volatile a number of conditions are check. After this is done the state change will be done. The critical section is the code that performs the checks up to the instruction that does the state change. Nomake_stablemay be done in between. The granularity is per page, to use a global lock like a spinlock would severly limit the scalability for large smp systems.Quoted 6 lines
How about doing it in the NUMA node? Or the
mem_section? Or, even a bit in the mem_map[] for the area guarding the 'struct page' itself? Even a hashed table of locks based on the page address. You just need something that allows _some_ level of concurrency. You certainly never have a number of CPUs which is anywhere close to the number of 'struct page's in the system.
Quoted 3 lines
NUMA node is not granular enough,
mem_sectionis probably doable. I do not understand the part about the bit in the mem_map[] area, a bit in thepage->flagsis exactly that, isn't it?
No, I'm being tricky. There are struct pages for all memory, including kernel memory. mem_map[] is in kernel memory. So, the memory for the mem_map[] has struct pages, which themselves are in the mem_map[].
void lock_page_for_state_change(struct page *page)
{
struct pages_backing_page = virt_to_page(page);
lock_page(pages_backing_page)
}We did this for a bit with sparsemem, I think. That is, until Andy came up with something even more clever.
-- Dave
Quoted 8 lines · Dave Hansen
Can you give me the sequence of events that occur so that we need to set, then check
PG_discarded? I'm not getting it.1. there is good data in a page
...
50. ... andPG_discardedgets set
...
99. We checkPG_discardedand ...
Ok, here we go:
0) there is good data in a page
1) the host scans for pages to reclaim and selects a page of a particular guest
2) the host checks the page state and decides to either swap the page or discard it
3) nothing happens for a long time
4) the guest comes around and tries to access the long gone page
5) the host gets a fault because the page is gone from the hosts page table for the guest system
6) the host delivers a discard fault to the guest
7) the architecture dependent fault handler gets a page reference for the discarded page (tricky for s390)
8) page_discard is called which locks the page and does a TestSetPageDiscarded. If the bit has not been set yet the page is removed from the page cache. There can still be page references around.
Concurrent to 5-8 another cpu could be just be removing the page from page cache as well. Without the check for the discarded bit the page would get removed twice. This does nasty things to reference counting, mapping->nrpages, ...
Quoted 8 lines
Quoted 3 lines
NUMA node is not granular enough,
mem_sectionis probably doable. I do not understand the part about the bit in the mem_map[] area, a bit in thepage->flagsis exactly that, isn't it?No, I'm being tricky. There are struct pages for all memory, including kernel memory. mem_map[] is in kernel memory. So, the memory for the mem_map[] has struct pages, which themselves are in the mem_map[].
Quoted 8 lines
void
lock_page_for_state_change(struct page *page){ struct pages_backing_page = virt_to_page(page); lock_page(pages_backing_page) }We did this for a bit with sparsemem, I think. That is, until Andy came up with something even more clever.
Ouch, I understand what you are trying to tell me. The struct page entries that cover the mem_map array itself has free bits we could try to cannibalize.
Signature · 8 lines
blue skies, Martin. Martin Schwidefsky Linux for zSeries Development & Services IBM Deutschland Entwicklung GmbH "Reality continues to ruin my life." - Calvin.
Quoted 7 lines · Dave Hansen
Quoted 6 lines
3) The page-has-a-writable-mapping (
PG_writable) bit is set when the first writable pte for a page is established. The page needs to have a different state if a writable pte exists compared to a read-only page. The alternative without the page bit would be to do the state change every time a writable pte is established or to search all ptes of a given page. Both have performance implications.
Quoted 5 lines
What are the performance implications? Do they completely erase any performance gains that these patches might have given in the first place? Has there been any evaluation of these other two alternatives? As I understand it, carrying out this performance analysis would be very difficult for most of the kernel community to perform.
It seemed obvious to me that anything else than checking a bit is way to expensive. I never implemented nor measured any of the alternatives. The alternative to do the state change every time a writable pte is established can be implemented without too much trouble. Perhaps I will give it a try next week.
Quoted 5 lines
Keeping a nice count of the number of writable PTEs sounds like something that might be generally useful. Could we split
page->_mapcountto keep track of r/o and r/w ptes separately? Or, perhaps a single bit in it can be utilized to replacePG_writable, instead.
Yes, that would be really useful for the writable ptes. But I have the feeling that the actual implementation of it will be tricky.
Signature · 8 lines
blue skies, Martin. Martin Schwidefsky Linux for zSeries Development & Services IBM Deutschland Entwicklung GmbH "Reality continues to ruin my life." - Calvin.
Quoted 2 lines · Martin Schwidefsky
Yes, that would be really useful for the writable ptes. But I have the feeling that the actual implementation of it will be tricky.
I'm confident that anyone able to produce nine patches like what I just saw is capable of producing at least one more tricky one. ;)
-- Dave
Quoted 27 lines · Martin Schwidefsky
Quoted 8 lines · Dave Hansen
Can you give me the sequence of events that occur so that we need to set, then check
PG_discarded? I'm not getting it.1. there is good data in a page
...
50. ... andPG_discardedgets set
...
99. We checkPG_discardedand ...Ok, here we go:
0) there is good data in a page
1) the host scans for pages to reclaim and selects a page of a particular guest
2) the host checks the page state and decides to either swap the page or discard it
3) nothing happens for a long time
4) the guest comes around and tries to access the long gone page
5) the host gets a fault because the page is gone from the hosts page table for the guest system
6) the host delivers a discard fault to the guest
7) the architecture dependent fault handler gets a page reference for the discarded page (tricky for s390)
8)page_discardis called which locks the page and does a TestSetPageDiscarded. If the bit has not been set yet the page is removed from the page cache. There can still be page references around.
Quoted 4 lines
Concurrent to 5-8 another cpu could be just be removing the page from page cache as well. Without the check for the discarded bit the page would get removed twice. This does nasty things to reference counting,
mapping->nrpages, ...
This feels like something that can be done with RCU. The __page_discard() is the write operation, right? So, take an rcu write lock inside of the page discard function, and read locks over the current places where PG_discarded is set.
That should make sure that the discard operation itself can't be done concurrently with one of the __remove_from*() operations. Once the write lock has been acquired, you just check page->mapping to see if the a __remove_from*() operation has occurred while you waited.
Quoted 3 lines
Ouch, I understand what you are trying to tell me. The struct page entries that cover the
mem_maparray itself has free bits we could try to cannibalize.
Right. It is certainly ugly. I'd much rather have some kind of
spin_lock(&lock_array[hash_function(page)]);
thing.
-- Dave
Quoted 9 lines · Dave Hansen
This feels like something that can be done with RCU. The
__page_discard()is the write operation, right? So, take an rcu write lock inside of the page discard function, and read locks over the current places wherePG_discardedis set.That should make sure that the discard operation itself can't be done concurrently with one of the __remove_from*() operations. Once the write lock has been acquired, you just check
page->mappingto see if the a __remove_from*() operation has occurred while you waited.
The problem of page discard vs. normal page remove is that the page can be remove and discarded at the same time. Both sides are writers in the sense that they want to remove the page from page cache. RCU doesn't not help with that kind of race.
Signature · 8 lines
blue skies, Martin. Martin Schwidefsky Linux for zSeries Development & Services IBM Deutschland Entwicklung GmbH "Reality continues to ruin my life." - Calvin.
Quoted 4 lines · Martin Schwidefsky
The problem of page discard vs. normal page remove is that the page can be remove and discarded at the same time. Both sides are writers in the sense that they want to remove the page from page cache. RCU doesn't not help with that kind of race.
OK. It comes down to a race between
__remove_from_page_cache()/__delete_from_swap_cache()
and
__page_discard()
running on the same page at the same time. Right?
-- Dave
Quoted 9 lines · Dave Hansen
OK. It comes down to a race between
__remove_from_page_cache()/__delete_from_swap_cache()and
__page_discard()running on the same page at the same time. Right?
Yes.
Signature · 8 lines
blue skies, Martin. Martin Schwidefsky Linux for zSeries Development & Services IBM Deutschland Entwicklung GmbH "Reality continues to ruin my life." - Calvin.
Quoted 5 lines · Martin Schwidefsky
Quoted 4 lines · Dave Hansen
OK. It comes down to a race between
__remove_from_page_cache()/__delete_from_swap_cache()
Quoted 7 lines
Quoted 5 lines
and
__page_discard()running on the same page at the same time. Right?
Yes.
OK, and there's no other workable solution to exclude each other from running at the same time than a bit in page->flags?
It seems like that hashed lock (or lock in mem_map[]) we were talking about earlier might be applicable here, too.
Do we ever discard pages other than ones that have just recently failed to be made stable? There seems to be a lot of
if (!page_make_stable(page) {
...
page_discard(page);
}Some of these call sites even have mapping->page_lock held when the page_make_stable() occurs, so they would have _already_ excluded __remove_from_page_cache(). At which call sites is it not feasible to acquire mapping->page_lock?
-- Dave
Quoted 5 lines · Dave Hansen
OK, and there's no other workable solution to exclude each other from running at the same time than a bit in
page->flags?It seems like that hashed lock (or lock in mem_map[]) we were talking about earlier might be applicable here, too.
The indication which page has already been removed from the page cache by a discard fault is by definition per-page. The situation is different compared to the one with PG_state_change which is used to protect critical sections. After the cpu left the critical section the bit can be clear again. The discard bit cannot be cleared until the page really has been freed.
Signature · 8 lines
blue skies, Martin. Martin Schwidefsky Linux for zSeries Development & Services IBM Deutschland Entwicklung GmbH "Reality continues to ruin my life." - Calvin.
Quoted 9 lines · Martin Schwidefsky
Quoted 5 lines · Dave Hansen
OK, and there's no other workable solution to exclude each other from running at the same time than a bit in
page->flags?It seems like that hashed lock (or lock in mem_map[]) we were talking about earlier might be applicable here, too.
The indication which page has already been removed from the page cache by a discard fault is by definition per-page.
Right. So having a single bit that was set and cleared wouldn't work because it could get interpreted incorrectly for multiple pages. But, what about a lock?
Quoted 5 lines
The situation is different
compared to the one withPG_state_changewhich is used to protect critical sections. After the cpu left the critical section the bit can be clear again. The discard bit cannot be cleared until the page really has been freed.
While something like the following wouldn't be scalable, it would functionally work, right?
+static void __page_discard(struct page *page)
+{
+ spin_lock(discard_lock);
...
+ spin_unlock(discard_lock);
+}
+void __delete_from_swap_cache(struct page *page)
+{
+ spin_lock(discard_lock);
...
+ spin_unlock(discard_lock);
+}
+void __remove_from_page_cache(struct page *page)
+{
+ spin_lock(discard_lock);
...
+ spin_unlock(discard_lock);
+}
-- Dave
Quoted 13 lines · Dave Hansen
While something like the following wouldn't be scalable, it would functionally work, right?
(quoted diff) +8
-0+static void __page_discard(struct page *page) +{ + spin_lock(discard_lock); + spin_unlock(discard_lock); +} +void __delete_from_swap_cache(struct page *page) +{ + spin_lock(discard_lock);
Review
Quoted 10 lines
(quoted diff) +7
-0+ spin_unlock(discard_lock); +} +void __remove_from_page_cache(struct page *page) +{ + spin_lock(discard_lock); + spin_unlock(discard_lock); +}
Any kind of locking won't work. You need the information that a page has been discarded until the page has been freed. Only then the fact that the page has been discarded may enter nirvana. Any kind of lock needs to be freed again to allow the next discard fault to happen. Since you don't when the last page reference is returned you cannot hold the lock until the page is free.
Signature · 13 lines
blue skies, Martin. Martin Schwidefsky Linux for zSeries Development & Services IBM Deutschland Entwicklung GmbH "Reality continues to ruin my life." - Calvin. -- VGER BF report: H 0
Quoted 6 lines · Martin Schwidefsky
Any kind of locking won't work. You need the information that a page has been discarded until the page has been freed. Only then the fact that the page has been discarded may enter nirvana. Any kind of lock needs to be freed again to allow the next discard fault to happen. Since you don't when the last page reference is returned you cannot hold the lock until the page is free.
First of all, you *CAN* sleep with the BKL held. ;)
Why doesn't the normal lock_page() help? It can sleep, too?
As far as simplifying the patches, I feel like some of the page_make_stable() stuff should be done inside of page_cache_get(). Perhaps the API needs to be changed so that page_cache_get()s can fail.
There are also a ton of "mapping == page->mapping" tests all over. Perhaps you need a page_still_in_mapping(page, mapping) call that also checks the page's discard state.
I also have the feeling that every single page_host_discards() check which is actually placed in the VM code shouldn't be there. The ones in page_make_stable() and friends are OK, but the ones in shrink_inactive_list() seem bogus to me. Looks like they should be covered up in some _other_ function that checks PageDiscarded().
You could even put these things in (what are now) simple functions like lru_to_page(). The logic would be along the lines of, whenever I am looking into the LRU, I need to make sure this page is still actually there.
As for the locking, imagine a seqlock (per-zone, node, section, hash, anon_vma, mapping, whatever...). A write is taken any time that PG_discard would have been set, and the page is placed in to a list so that it can be found (the data structure isn't important now). All of the places that currently check PG_discard would go and take a read on the seqlock. If they fail to acquire it (what is normally now a loop), they would go look in the list to see if the page they are interested in is there. If it is, then they treat it as dicarded, otherwise they proceed normally. So, the operation is normally very cheap (a non-atomic read). It is very expensive _during_ a discard because of the traversal of the list, but these should be rare.
The structure storing the page could be like this:
struct page_list {
struct list_head list;
struct page *page;
};So that it doesn't require any extra space in the struct page, and limits the overhead to only the people actually using the page discard mechanism.
-- Dave
Quoted 9 lines · Dave Hansen
Quoted 6 lines · Martin Schwidefsky
Any kind of locking won't work. You need the information that a page has been discarded until the page has been freed. Only then the fact that the page has been discarded may enter nirvana. Any kind of lock needs to be freed again to allow the next discard fault to happen. Since you don't when the last page reference is returned you cannot hold the lock until the page is free.
First of all, you *CAN* sleep with the BKL held. ;)
You can call schedule with the BKL held. But schedule will release the BKL before the process is put to sleep. To use a lock as mechanism to prevent double frees of discarded pages you'd have to hold it while sleeping.
Quoted 1 line
Why doesn't the normal
lock_page()help? It can sleep, too?
The PG_locked bit which is behind lock_page() is used for a different purpose. Look at the way how e.g. find_lock_page works: the radix tree lookup is made, a reference is acquired with page_cache_get() and then __lock_page() is called. For the discard double page free prevention we need to lock the page, then wait for all referenced to be returned. Only then can we unlock the page again. These two uses are mutual exclusive.
Quoted 3 lines
As far as simplifying the patches, I feel like some of the
page_make_stable()stuff should be done inside ofpage_cache_get(). Perhaps the API needs to be changed so that page_cache_get()s can fail.
Uhh, that is even more invasive than the things we do now. page_cache_get() alias get_page() is just concerned about reference counting. You definitly do not want to do state changes in get_page/put_page. That would increase the number state changes by an order of magnitude.
Quoted 3 lines
There are also a ton of "mapping ==
page->mapping" tests all over. Perhaps you need apage_still_in_mapping(page, mapping)call that also checks the page's discard state.
Where does this help? All places that have "mapping == page->mapping" either don't care about the page state or work on stable pages.
Quoted 5 lines
I also have the feeling that every single
page_host_discards()check which is actually placed in the VM code shouldn't be there. The ones inpage_make_stable()and friends are OK, but the ones inshrink_inactive_list()seem bogus to me. Looks like they should be covered up in some _other_ function that checksPageDiscarded().
Hmm, we can reduce the number of page_host_discards() checks in the VM code if PageDiscarded() and friends are defined conditionally on CONFIG_PAGE_STATES. I'm not sure if all calls to page_host_discards() can be removed but I will take a look at it. It would be a real improvement to get rid of most of these calls.
Quoted 4 lines
You could even put these things in (what are now) simple functions like
lru_to_page(). The logic would be along the lines of, whenever I am looking into the LRU, I need to make sure this page is still actually there.
It would make the code simpler but the cost would be additional state changes. For example whenever you free a page you would do a state transition from volatile to stable shortly followed by a state transition from stable to unused. These states changes have a cost that we want to avoid.
Quoted 14 lines
As for the locking, imagine a seqlock (per-zone, node, section, hash,
anon_vma, mapping, whatever...). A write is taken any time thatPG_discardwould have been set, and the page is placed in to a list so that it can be found (the data structure isn't important now). All of the places that currently checkPG_discardwould go and take a read on the seqlock. If they fail to acquire it (what is normally now a loop), they would go look in the list to see if the page they are interested in is there. If it is, then they treat it as dicarded, otherwise they proceed normally. So, the operation is normally very cheap (a non-atomic read). It is very expensive _during_ a discard because of the traversal of the list, but these should be rare.The structure storing the page could be like this:
Quoted 8 lines
struct page_list { struct list_head list; struct page *page; };So that it doesn't require any extra space in the struct page, and limits the overhead to only the people actually using the page discard mechanism.
I'm a little confused about this suggestion. If I understood it correctly you want to block a number of pages and use a seqlock per block to indicate if there is a discarded page in that block of pages. On discard you do write_seqlock and force the read_seqlock side if the lock could to be acquired to traverse a list before they can conclude that a page is not discarded.
First question: where are the list_heads stored that are used to put pages on the special list? They have to be allocated somewhere, per discarded page. I do not think that you can do it lazy, that is after a discard fault happened. You have to preallocate them and then you are spending 16 byte per discardable page instead of 1 bit. Second question: how do you deal with multiple discards for a block of pages? The first sets the write_seqlock, how is the write_sequnlock done? After a discarded page has been freed you need to check if there is another discarded page in the block, or if a discard is in progress. This sounds racy.
I do not think that the locking with a seqlock will work. But please keep throwing ideas at me. The point about page_host_discards is valid.
Signature · 8 lines
blue skies, Martin. Martin Schwidefsky Linux for zSeries Development & Services IBM Deutschland Entwicklung GmbH "Reality continues to ruin my life." - Calvin.
Quoted 8 lines · Martin Schwidefsky
The code added by this patch uses the volatile state for all page cache pages, even for pages which are referenced by writable ptes. The host needs to be able to check the dirty state of the pages. Since the host doesn't know where the page table entries of the guest are located, the volatile state as introduced by this patch is only usable on architectures with per-page dirty bits (s390 only). For per-pte dirty bit architectures some additional code is needed.
What do you mean by per-page dirty bits. Do you mean per-page dirty bits in hardware (s390), in software (Linux), or maintained by the hypervisor?
Quoted 4 lines
The interesting question is where to put the state transitions between the volatile and the stable state. The simple solution is the make a page stable whenever a lookup is done or a page reference is derived from a page table entry. Attempts to make pages volatile are added at
Quoted 9 lines
strategic points. Now what are the conditions that prevent a page from being made volatile? There are 10 conditions:
1) The page is reserved. Some sort of special page.
2) The page is marked dirty in the struct page. The page content is more recent than the data on the backing device. The host cannot access the linux internal dirty bit so the page needs to be stable.
3) The page is in writeback. The page content is needed for i/o.
4) The page is locked. Someone has exclusive access to the page.
I'll tend to agree from a heuristical performance point of view, but I don't see any reason that a locked page can't be made volatile from a correctness perspective.
Quoted 12 lines
5) The page is anonymous. Swap cache support needs additional code.
6) The page has no mapping. No backing, the page cannot be recreated.
7) The page is not uptodate.
8) The page has private information.try_to_release_pagecan fail, e.g. in case the private information is journaling data. The discard fault need to be able to remove the page.
9) The page is already discarded.
10) The page map count is not equal to the page reference count - 1. The discard fault handler can remove the page cache reference and all mappers of a page. It cannot remove the page reference for any other user of the page.
Does s390 use per physical page permission bits separate from the PTEs? Because I don't see how you can generate a discard fault otherwise unless you know where the page table entries of the guest are located, which you already said you don't. Or perhaps I'm misunderstanding the meaning of discard fault - I'm taking it to mean a fault which happens on access to a volatile page that was discarded by the hypervisor - thus requiring a refresh of all mapping PTEs?
Thanks,
Zach
Quoted 10 lines · Zachary Amsden
Quoted 8 lines · Martin Schwidefsky
The code added by this patch uses the volatile state for all page cache pages, even for pages which are referenced by writable ptes. The host needs to be able to check the dirty state of the pages. Since the host doesn't know where the page table entries of the guest are located, the volatile state as introduced by this patch is only usable on architectures with per-page dirty bits (s390 only). For per-pte dirty bit architectures some additional code is needed.
Quoted 3 lines
What do you mean by per-page dirty bits. Do you mean per-page dirty bits in hardware (s390), in software (Linux), or maintained by the hypervisor?
s390 has something called a storage key. There is one for each page. In a virtualized system there is one for each virtual page. The dirty and referenced bit for each page is kept in the storage key and not in the pte. On s390 the pte has nothing to do with dirty/referenced. If your hardware allows you to have dirty bits per page instead of per pte then you can query the dirty bit from the host without needing access to all the ptes.
Quoted 14 lines
Quoted 4 lines
The interesting question is where to put the state transitions between the volatile and the stable state. The simple solution is the make a page stable whenever a lookup is done or a page reference is derived from a page table entry. Attempts to make pages volatile are added at
Quoted 9 lines
strategic points. Now what are the conditions that prevent a page from being made volatile? There are 10 conditions:
1) The page is reserved. Some sort of special page.
2) The page is marked dirty in the struct page. The page content is more recent than the data on the backing device. The host cannot access the linux internal dirty bit so the page needs to be stable.
3) The page is in writeback. The page content is needed for i/o.
4) The page is locked. Someone has exclusive access to the page.
Quoted 3 lines
I'll tend to agree from a heuristical performance point of view, but I don't see any reason that a locked page can't be made volatile from a correctness perspective.
Interesting. Usually there is an additional page reference for a locked page so it probably won't make a difference. I'm not sure if all "users" of locked pages can deal with volatile pages, I'll have to check.
Quoted 13 lines
Quoted 12 lines
5) The page is anonymous. Swap cache support needs additional code.
6) The page has no mapping. No backing, the page cannot be recreated.
7) The page is not uptodate.
8) The page has private information.try_to_release_pagecan fail, e.g. in case the private information is journaling data. The discard fault need to be able to remove the page.
9) The page is already discarded.
10) The page map count is not equal to the page reference count - 1. The discard fault handler can remove the page cache reference and all mappers of a page. It cannot remove the page reference for any other user of the page.
Quoted 1 line
Does s390 use per physical page permission bits separate from the PTEs?
Yes.
Quoted 6 lines
Because I don't see how you can generate a discard fault otherwise unless you know where the page table entries of the guest are located, which you already said you don't. Or perhaps I'm misunderstanding the meaning of discard fault - I'm taking it to mean a fault which happens on access to a volatile page that was discarded by the hypervisor - thus requiring a refresh of all mapping PTEs?
The discard fault happens on access to a volatile that has been discarded. An important property of the s390 architecture comes into play here: there are two page tables, a guest page table and a host page table. What the guest perceives as its "physical" memory is in virtual storage for the host. An address resolution has to walk two pages tables, if a pte is invalid in either table you get a fault. A guest fault if the invalid pte is in the guest table and a host fault if it is in the host table. That gives s390 a simple method to implement discarded pages: the hypervisor just unmaps the page from the host table and changes the state of the guest page. I can see that you will have a much harder time to implement this on i386.
Signature · 8 lines
blue skies, Martin. Martin Schwidefsky Linux for zSeries Development & Services IBM Deutschland Entwicklung GmbH "Reality continues to ruin my life." - Calvin.
Martin Schwidefsky wrote
Quoted 8 lines
The discard fault happens on access to a volatile that has been discarded. An important property of the s390 architecture comes into play here: there are two page tables, a guest page table and a host page table. What the guest perceives as its "physical" memory is in virtual storage for the host. An address resolution has to walk two pages tables, if a pte is invalid in either table you get a fault. A guest fault if the invalid pte is in the guest table and a host fault if it is
Yes, I'm familiar with that trick. Wasn't sure if you had it in hardware or not.
Quoted 5 lines
in the host table. That gives s390 a simple method to implement discarded pages: the hypervisor just unmaps the page from the host table and changes the state of the guest page. I can see that you will have a much harder time to implement this on i386.
Nah, I think we'll do just fine.
Thanks for the info - based on this, I think we can probably use the volatile page / swap cache changes as well for VMware, also pretty much unchanged. Sorry to take so long to look at these patches, BTW - I was on holiday for two weeks.
Zach
Quoted 10 lines · Zachary Amsden
Martin Schwidefsky wrote
Quoted 8 lines
The discard fault happens on access to a volatile that has been discarded. An important property of the s390 architecture comes into play here: there are two page tables, a guest page table and a host page table. What the guest perceives as its "physical" memory is in virtual storage for the host. An address resolution has to walk two pages tables, if a pte is invalid in either table you get a fault. A guest fault if the invalid pte is in the guest table and a host fault if it is
Quoted 2 lines
Yes, I'm familiar with that trick. Wasn't sure if you had it in hardware or not.
The mainframes have that trick in hardware for about 30 years ..
Quoted 7 lines
Quoted 5 lines
in the host table. That gives s390 a simple method to implement discarded pages: the hypervisor just unmaps the page from the host table and changes the state of the guest page. I can see that you will have a much harder time to implement this on i386.
Nah, I think we'll do just fine.
I wonder which trick you use, since there is only one page table one i386 I can only imagine that you are tracking all page tables of the guest.
Quoted 4 lines
Thanks for the info - based on this, I think we can probably use the volatile page / swap cache changes as well for VMware, also pretty much unchanged. Sorry to take so long to look at these patches, BTW - I was on holiday for two weeks.
I've been sitting on these patches for months now and you are worrying about two weeks..
Signature · 8 lines
blue skies, Martin. Martin Schwidefsky Linux for zSeries Development & Services IBM Deutschland Entwicklung GmbH "Reality continues to ruin my life." - Calvin.