RFC: shadow page table reclaim
Hello,
it seems to me that the reclaim mechanism for shadow page table pages is sub- optimal. The arch.active_mmu_pages list that is used for reclaiming does not move up parent shadow page tables when a child is added so when we need a new shadow page we zap the oldest - which can well be a directory level page holding a just added table level page.
Attached is a proof-of-concept diff and two plots before and after. The plots show referenced guest pages over time. As you can see there is less saw- toothing in the after plot and also fewer changes overall (because we don't zap mappings that are still in use as often). This is with a limit of 64 for the shadow page table to increase the effect and vmx/ept.
I realize that the list_move and parent walk are quite expensive and that kvm_mmu_alloc_page is only half the story. It should really be done every time a new guest page table is mapped - maybe via rmap_add. This would obviously completely kill performance-wise, though.
Another idea would be to improve the reclaim logic in a way that it prefers "old" PT_PAGE_TABLE_LEVEL over directories. Though I'm not sure how to code that up sensibly, either.
As I said, this is proof-of-concept and RFC. So any comments welcome. For my use case the proof-of-concept diff seems to do well enough, though.
Thanks,
Signature · 4 lines
/"\ Best regards, | [email protected] \ / Max Laier | ICQ #67774661 X http://pf4freebsd.love2party.net/ | mlaier@EFnet / \ ASCII Ribbon Campaign | Against HTML Mail and News
arch/x86/kvm/mmu.c +12 -0
@@ -190,6 +190,8 @@ struct kvm_unsync_walk { };typedef int (*mmu_parent_walk_fn ) (struct kvm_vcpu *vcpu,struct kvm_mmu_page *sp); +static void mmu_parent_walk (struct kvm_vcpu *vcpu,struct kvm_mmu_page *sp, +mmu_parent_walk_fn fn);static struct kmem_cache *pte_chain_cache;static struct kmem_cache *rmap_desc_cache;
@@ -900,6 +902,12 @@ static unsigned kvm_page_table_hashfn(gfn_t gfn)return gfn & ((1 <<KVM_MMU_HASH_SHIFT ) -1 ); } +static int move_up_walk_fn (struct kvm_vcpu *vcpu,struct kvm_mmu_page *sp) +{ +list_move (&sp->link, &vcpu->kvm->arch.active_mmu_pages); +return 1 ; +} +static struct kvm_mmu_page *kvm_mmu_alloc_page (struct kvm_vcpu *vcpu,u64 *parent_pte) {
@@ -918,6 +926,10 @@ static struct kvm_mmu_page *kvm_mmu_alloc_page(struct kvm_vcpu *vcpu,bitmap_zero (sp->slot_bitmap,KVM_MEMORY_SLOTS +KVM_PRIVATE_MEM_SLOTS ); sp->multimapped =0 ; sp->parent_pte = parent_pte; +#if 1 +if (parent_pte) +mmu_parent_walk (vcpu, sp, move_up_walk_fn); +#endif --vcpu->kvm->arch.n_free_mmu_pages;return sp; }
Quoted 10 lines · Max Laier
Hello,
it seems to me that the reclaim mechanism for shadow page table pages is sub- optimal. The arch.active_mmu_pages list that is used for reclaiming does not move up parent shadow page tables when a child is added so when we need a new shadow page we zap the oldest - which can well be a directory level page holding a just added table level page.
Attached is a proof-of-concept diff and two plots before and after. The plots show referenced guest pages over time.
What do you mean by referenced guest pages? Total number of populated sptes?
Quoted 10 lines
As you can see there is less saw-
toothing in the after plot and also fewer changes overall (because we don't zap mappings that are still in use as often). This is with a limit of 64 for the shadow page table to increase the effect and vmx/ept.I realize that the
list_moveand parent walk are quite expensive and thatkvm_mmu_alloc_pageis only half the story. It should really be done every time a new guest page table is mapped - maybe viarmap_add. This would obviously completely kill performance-wise, though.
Quoted 7 lines
Another idea would be to improve the reclaim logic in a way that it prefers "old"
PT_PAGE_TABLE_LEVELover directories. Though I'm not sure how to code that up sensibly, either.As I said, this is proof-of-concept and RFC. So any comments welcome. For my use case the proof-of-concept diff seems to do well enough, though.
Given that reclaim is fairly rare, we should try to move the cost there. So how about this:
- add an 'accessed' flag to struct kvm_mmu_page
- when reclaiming, try to evict pages that were not recently accessed (but don't overscan - if you scan many recently accessed pages, evict some of them anyway)
- when scanning, update the accessed flag with the accessed bit of all parent_ptes
- when dropping an spte, update the accessed flag of the kvm_mmu_page it points to
- when reloading cr3, mark the page as accessed (since it has no parent_ptes)
This should introduce some LRU-ness that depends not only on fault behaviour but also on long-term guest access behaviour (which is important for long-running processes and kernel pages).
Signature · 1 line
error compiling committee.c: too many arguments to function
Quoted 9 lines · On Monday 31 August 2009 11:55:24 Avi Kivity wrote:
Quoted 8 lines · Max Laier
Hello,
it seems to me that the reclaim mechanism for shadow page table pages is sub- optimal. The arch.active_mmu_pages list that is used for reclaiming does not move up parent shadow page tables when a child is added so when we need a new shadow page we zap the oldest - which can well be a directory level page holding a just added table level page.
Quoted 5 lines
Quoted 2 lines
Attached is a proof-of-concept diff and two plots before and after. The plots show referenced guest pages over time.
What do you mean by referenced guest pages? Total number of populated sptes?
Yes.
Quoted 18 lines
Quoted 10 lines
As you can see there is less saw-
toothing in the after plot and also fewer changes overall (because we don't zap mappings that are still in use as often). This is with a limit of 64 for the shadow page table to increase the effect and vmx/ept.I realize that the
list_moveand parent walk are quite expensive and thatkvm_mmu_alloc_pageis only half the story. It should really be done every time a new guest page table is mapped - maybe viarmap_add. This would obviously completely kill performance-wise, though.Quoted 7 lines
Another idea would be to improve the reclaim logic in a way that it prefers "old"
PT_PAGE_TABLE_LEVELover directories. Though I'm not sure how to code that up sensibly, either.As I said, this is proof-of-concept and RFC. So any comments welcome. For my use case the proof-of-concept diff seems to do well enough, though.
Quoted 7 lines
Given that reclaim is fairly rare, we should try to move the cost there. So how about this:
- add an 'accessed' flag to struct
kvm_mmu_page
- when reclaiming, try to evict pages that were not recently accessed (but don't overscan - if you scan many recently accessed pages, evict some of them anyway)
- prefer page table level pages over directory level pages in the face of overscan.
Quoted 2 lines
- when scanning, update the accessed flag with the accessed bit of all
parent_ptes
I might be misunderstanding, but I think it should be the other way 'round. i.e. a page is accessed if any of it's children have been accessed.
Quoted 8 lines
- when dropping an spte, update the accessed flag of the
kvm_mmu_pageit points to
- when reloading cr3, mark the page as accessed (since it has noparent_ptes)This should introduce some LRU-ness that depends not only on fault behaviour but also on long-term guest access behaviour (which is important for long-running processes and kernel pages).
I'll try to come up with a patch for this, later tonight. Unless you already have something in the making. Thanks.
Signature · 4 lines
/"\ Best regards, | [email protected] \ / Max Laier | ICQ #67774661 X http://pf4freebsd.love2party.net/ | mlaier@EFnet / \ ASCII Ribbon Campaign | Against HTML Mail and News
Quoted 22 lines · Max Laier
Quoted 22 lines
Quoted 11 lines
As you can see there is less saw-
toothing in the after plot and also fewer changes overall (because we don't zap mappings that are still in use as often). This is with a limit of 64 for the shadow page table to increase the effect and vmx/ept.I realize that the
list_moveand parent walk are quite expensive and thatkvm_mmu_alloc_pageis only half the story. It should really be done every time a new guest page table is mapped - maybe viarmap_add. This would obviously completely kill performance-wise, though.Quoted 8 lines
Another idea would be to improve the reclaim logic in a way that it prefers "old"
PT_PAGE_TABLE_LEVELover directories. Though I'm not sure how to code that up sensibly, either.As I said, this is proof-of-concept and RFC. So any comments welcome. For my use case the proof-of-concept diff seems to do well enough, though.
Given that reclaim is fairly rare, we should try to move the cost there. So how about this:
Quoted 8 lines
Quoted 5 lines
- add an 'accessed' flag to struct
kvm_mmu_page
- when reclaiming, try to evict pages that were not recently accessed (but don't overscan - if you scan many recently accessed pages, evict some of them anyway)- prefer page table level pages over directory level pages in the face of overscan.
I'm hoping that overscan will only occur when we start to feel memory pressure, and that once we do a full scan we'll get accurate recency information.
Quoted 6 lines
Quoted 3 lines
- when scanning, update the accessed flag with the accessed bit of all
parent_ptesI might be misunderstanding, but I think it should be the other way 'round. i.e. a page is accessed if any of it's children have been accessed.
They're both true, but looking at the parents is much more efficient. Note we need to look at the accessed bit of the parent_ptes, not parent kvm_mmu_pages.
Quoted 5 lines
Quoted 5 lines
- when dropping an spte, update the accessed flag of the
kvm_mmu_pageit points to
- when reloading cr3, mark the page as accessed (since it has noparent_ptes)
Quoted 7 lines
Quoted 4 lines
This should introduce some LRU-ness that depends not only on fault behaviour but also on long-term guest access behaviour (which is important for long-running processes and kernel pages).
I'll try to come up with a patch for this, later tonight. Unless you already have something in the making. Thanks.
Please do, it's an area that need attention.
Signature · 1 line
error compiling committee.c: too many arguments to function
Quoted 51 lines · On Monday 31 August 2009 14:40:29 Avi Kivity wrote:
Quoted 22 lines · Max Laier
Quoted 22 lines
Quoted 11 lines
As you can see there is less saw-
toothing in the after plot and also fewer changes overall (because we don't zap mappings that are still in use as often). This is with a limit of 64 for the shadow page table to increase the effect and vmx/ept.I realize that the
list_moveand parent walk are quite expensive and thatkvm_mmu_alloc_pageis only half the story. It should really be done every time a new guest page table is mapped - maybe viarmap_add. This would obviously completely kill performance-wise, though.Quoted 7 lines
Another idea would be to improve the reclaim logic in a way that it prefers "old"
PT_PAGE_TABLE_LEVELover directories. Though I'm not sure how to code that up sensibly, either.As I said, this is proof-of-concept and RFC. So any comments welcome. For my use case the proof-of-concept diff seems to do well enough, though.
Given that reclaim is fairly rare, we should try to move the cost there. So how about this:
Quoted 7 lines
Quoted 4 lines
- add an 'accessed' flag to struct
kvm_mmu_page
- when reclaiming, try to evict pages that were not recently accessed (but don't overscan - if you scan many recently accessed pages, evict some of them anyway)- prefer page table level pages over directory level pages in the face of overscan.
I'm hoping that overscan will only occur when we start to feel memory pressure, and that once we do a full scan we'll get accurate recency information.
Quoted 6 lines
Quoted 2 lines
- when scanning, update the accessed flag with the accessed bit of all
parent_ptesI might be misunderstanding, but I think it should be the other way 'round. i.e. a page is accessed if any of it's children have been accessed.
They're both true, but looking at the parents is much more efficient. Note we need to look at the accessed bit of the
parent_ptes, not parentkvm_mmu_pages.Quoted 5 lines
Quoted 5 lines
- when dropping an spte, update the accessed flag of the
kvm_mmu_pageit points to
- when reloading cr3, mark the page as accessed (since it has noparent_ptes)
Quoted 8 lines
Quoted 6 lines
Quoted 3 lines
This should introduce some LRU-ness that depends not only on fault behaviour but also on long-term guest access behaviour (which is important for long-running processes and kernel pages).
I'll try to come up with a patch for this, later tonight. Unless you already have something in the making. Thanks.
Please do, it's an area that need attention.
Okay ... I have /something/, but I'm certainly not there yet as I have to admit that I don't understand your idea completely. In addition it seems that EPT doesn't have an accessed bit :-\ Any idea for this?
Regardless, testing the attached with EPT, it turns out that not zapping shadow pages with root_count != 0 already makes much difference. After all we don't really zap these pages anyways, but just mark them invalid after zapping the children. So this could be a first improvement.
In any case, I clearly don't have the right idea here, yet. Plus I don't really have time to look into this further right now. And my hack is "good enough"[tm] for my testing ... so if anyone more knowledgeable would like to continue - much appreciated. Maybe some of this can at least serve as food for thoughts. Sorry.
Signature · 4 lines
/"\ Best regards, | [email protected] \ / Max Laier | ICQ #67774661 X http://pf4freebsd.love2party.net/ | mlaier@EFnet / \ ASCII Ribbon Campaign | Against HTML Mail and News
arch/x86/include/asm/kvm_host.h +1 -0
@@ -394,6 +394,7 @@ struct kvm_arch{* Hash table of struct kvm_mmu_page. */ struct list_head active_mmu_pages; +struct kvm_mmu_page *scan_hand;struct list_head assigned_dev_head;struct iommu_domain *iommu_domain;int iommu_flags;
arch/x86/kvm/mmu.c +70 -6
106 lines not on this page · raw message
arch/x86/kvm/x86.c +1 -0
@@ -4782,6 +4782,7 @@ struct kvm *kvm_arch_create_vm(void)return ERR_PTR (-ENOMEM );INIT_LIST_HEAD (&kvm->arch.active_mmu_pages); + kvm->arch.scan_hand =NULL ;INIT_LIST_HEAD (&kvm->arch.assigned_dev_head);/* Reserve bit 0 of irq_sources_bitmap for userspace irq source */
Quoted 4 lines · Max Laier
Okay ... I have/something/, but I'm certainly not there yet as I have to admit that I don't understand your idea completely. In addition it seems that EPT doesn't have an accessed bit :-\ Any idea for this?
Use the rwx bits as an approximation. If the pages are needed they'll be faulted back in, which is a lot cheaper than reconstructing them.
But why do you see reclaim with ept? The pages ought to be constructed once and then left alone, unless there is severe memory pressure.
Quoted 11 lines
Regardless, testing the attached with EPT, it turns out that not zapping shadow pages with
root_count!= 0 already makes much difference. After all we don't really zap these pages anyways, but just mark them invalid after zapping the children. So this could be a first improvement.In any case, I clearly don't have the right idea here, yet. Plus I don't really have time to look into this further right now. And my hack is "good enough"[tm] for my testing ... so if anyone more knowledgeable would like to continue - much appreciated. Maybe some of this can at least serve as food for thoughts. Sorry.
Sure.
arch/x86/include/asm/kvm_host.h struct kvm_arch{ · line 400
Quoted 13 lines
arch/x86/include/asm/kvm_host.h +1
-0@@ -394,6 +394,7 @@ struct kvm_arch{* Hash table of struct kvm_mmu_page. */ struct list_head active_mmu_pages; +struct kvm_mmu_page *scan_hand;struct list_head assigned_dev_head;struct iommu_domain *iommu_domain;int iommu_flags;
Why is a scan hand needed? I though you could just clear the accessed bits and requeue the page.
If you drop a page, all the accessed bits in the ptes are lost with it, so you need to transfer them to the pointed-to pages before you dropped it. Other than that, this seems pretty complete.
Signature · 1 line
error compiling committee.c: too many arguments to function