[PATCH 0/2] Simplify RCU freeing of shadow pages

[PATCH 0/2] Simplify RCU freeing of shadow pages

[Avi Kivity]

This patchset simplifies the freeing by RCU of mmu pages.

Xiao, I'm sure you thought of always freeing by RCU.  Why didn't you choose
this way?  I saves a couple of atomics in the fast path.

Avi Kivity (2):
  KVM: MMU: Always free shadow pages using RCU
  KVM: MMU: Recover space used by rcu_head in struct kvm_mmu_page

 arch/x86/include/asm/kvm_host.h |    9 +++---
 arch/x86/kvm/mmu.c              |   58 ++++++++-------------------------------
 2 files changed, 15 insertions(+), 52 deletions(-)

-- 
1.7.10

[PATCH 1/2] KVM: MMU: Always free shadow pages using RCU

[Avi Kivity]

The non-RCU path costs us two atomic operations, as well as extra
code complexity.

Signed-off-by: Avi Kivity <avi@redhat.com>
---
 arch/x86/include/asm/kvm_host.h |    2 --
 arch/x86/kvm/mmu.c              |   46 ++++++++-------------------------------
 2 files changed, 9 insertions(+), 39 deletions(-)

diff --git a/arch/x86/include/asm/kvm_host.h b/arch/x86/include/asm/kvm_host.h
index f624ca7..b885445 100644
--- a/arch/x86/include/asm/kvm_host.h
+++ b/arch/x86/include/asm/kvm_host.h
@@ -536,8 +536,6 @@ struct kvm_arch {
 	u64 hv_guest_os_id;
 	u64 hv_hypercall;
 
-	atomic_t reader_counter;
-
 	#ifdef CONFIG_KVM_MMU_AUDIT
 	int audit_point;
 	#endif
diff --git a/arch/x86/kvm/mmu.c b/arch/x86/kvm/mmu.c
index 29ad6f9..c10f60b 100644
--- a/arch/x86/kvm/mmu.c
+++ b/arch/x86/kvm/mmu.c
@@ -549,23 +549,6 @@ static u64 mmu_spte_get_lockless(u64 *sptep)
 	return __get_spte_lockless(sptep);
 }
 
-static void walk_shadow_page_lockless_begin(struct kvm_vcpu *vcpu)
-{
-	rcu_read_lock();
-	atomic_inc(&vcpu->kvm->arch.reader_counter);
-
-	/* Increase the counter before walking shadow page table */
-	smp_mb__after_atomic_inc();
-}
-
-static void walk_shadow_page_lockless_end(struct kvm_vcpu *vcpu)
-{
-	/* Decrease the counter after walking shadow page table finished */
-	smp_mb__before_atomic_dec();
-	atomic_dec(&vcpu->kvm->arch.reader_counter);
-	rcu_read_unlock();
-}
-
 static int mmu_topup_memory_cache(struct kvm_mmu_memory_cache *cache,
 				  struct kmem_cache *base_cache, int min)
 {
@@ -2023,23 +2006,12 @@ static void kvm_mmu_commit_zap_page(struct kvm *kvm,
 
 	kvm_flush_remote_tlbs(kvm);
 
-	if (atomic_read(&kvm->arch.reader_counter)) {
-		kvm_mmu_isolate_pages(invalid_list);
-		sp = list_first_entry(invalid_list, struct kvm_mmu_page, link);
-		list_del_init(invalid_list);
-
-		trace_kvm_mmu_delay_free_pages(sp);
-		call_rcu(&sp->rcu, free_pages_rcu);
-		return;
-	}
-
-	do {
-		sp = list_first_entry(invalid_list, struct kvm_mmu_page, link);
-		WARN_ON(!sp->role.invalid || sp->root_count);
-		kvm_mmu_isolate_page(sp);
-		kvm_mmu_free_page(sp);
-	} while (!list_empty(invalid_list));
+	kvm_mmu_isolate_pages(invalid_list);
+	sp = list_first_entry(invalid_list, struct kvm_mmu_page, link);
+	list_del_init(invalid_list);
 
+	trace_kvm_mmu_delay_free_pages(sp);
+	call_rcu(&sp->rcu, free_pages_rcu);
 }
 
 /*
@@ -2976,11 +2948,11 @@ static u64 walk_shadow_page_get_mmio_spte(struct kvm_vcpu *vcpu, u64 addr)
 	struct kvm_shadow_walk_iterator iterator;
 	u64 spte = 0ull;
 
-	walk_shadow_page_lockless_begin(vcpu);
+	rcu_read_lock();
 	for_each_shadow_entry_lockless(vcpu, addr, iterator, spte)
 		if (!is_shadow_present_pte(spte))
 			break;
-	walk_shadow_page_lockless_end(vcpu);
+	rcu_read_unlock();
 
 	return spte;
 }
@@ -4060,14 +4032,14 @@ int kvm_mmu_get_spte_hierarchy(struct kvm_vcpu *vcpu, u64 addr, u64 sptes[4])
 	u64 spte;
 	int nr_sptes = 0;
 
-	walk_shadow_page_lockless_begin(vcpu);
+	rcu_read_lock();
 	for_each_shadow_entry_lockless(vcpu, addr, iterator, spte) {
 		sptes[iterator.level-1] = spte;
 		nr_sptes++;
 		if (!is_shadow_present_pte(spte))
 			break;
 	}
-	walk_shadow_page_lockless_end(vcpu);
+	rcu_read_unlock();
 
 	return nr_sptes;
 }
-- 
1.7.10

[PATCH 2/2] KVM: MMU: Recover space used by rcu_head in struct kvm_mmu_page

[Avi Kivity]

By overlaying the field with 'link', we reduce the structure size by
16 bytes.

Changing call_rcu() to be per-page is not strictly necessary, but it
can help RCU estimate the amount of work pending.

Signed-off-by: Avi Kivity <avi@redhat.com>
---
 arch/x86/include/asm/kvm_host.h |    7 ++++---
 arch/x86/kvm/mmu.c              |   26 +++++++++-----------------
 2 files changed, 13 insertions(+), 20 deletions(-)

diff --git a/arch/x86/include/asm/kvm_host.h b/arch/x86/include/asm/kvm_host.h
index b885445..ae02ff8 100644
--- a/arch/x86/include/asm/kvm_host.h
+++ b/arch/x86/include/asm/kvm_host.h
@@ -208,7 +208,10 @@ union kvm_mmu_page_role {
 };
 
 struct kvm_mmu_page {
-	struct list_head link;
+	union {
+		struct list_head link;
+		struct rcu_head rcu;
+	};
 	struct hlist_node hash_link;
 
 	/*
@@ -237,8 +240,6 @@ struct kvm_mmu_page {
 #endif
 
 	int write_flooding_count;
-
-	struct rcu_head rcu;
 };
 
 struct kvm_pio_request {
diff --git a/arch/x86/kvm/mmu.c b/arch/x86/kvm/mmu.c
index c10f60b..26257d7 100644
--- a/arch/x86/kvm/mmu.c
+++ b/arch/x86/kvm/mmu.c
@@ -1338,7 +1338,6 @@ static void kvm_mmu_isolate_page(struct kvm_mmu_page *sp)
  */
 static void kvm_mmu_free_page(struct kvm_mmu_page *sp)
 {
-	list_del(&sp->link);
 	free_page((unsigned long)sp->spt);
 	kmem_cache_free(mmu_page_header_cache, sp);
 }
@@ -1980,20 +1979,12 @@ static void kvm_mmu_isolate_pages(struct list_head *invalid_list)
 		kvm_mmu_isolate_page(sp);
 }
 
-static void free_pages_rcu(struct rcu_head *head)
+static void free_page_rcu(struct rcu_head *head)
 {
-	struct kvm_mmu_page *next, *sp;
+	struct kvm_mmu_page *sp;
 
 	sp = container_of(head, struct kvm_mmu_page, rcu);
-	while (sp) {
-		if (!list_empty(&sp->link))
-			next = list_first_entry(&sp->link,
-				      struct kvm_mmu_page, link);
-		else
-			next = NULL;
-		kvm_mmu_free_page(sp);
-		sp = next;
-	}
+	kvm_mmu_free_page(sp);
 }
 
 static void kvm_mmu_commit_zap_page(struct kvm *kvm,
@@ -2007,11 +1998,12 @@ static void kvm_mmu_commit_zap_page(struct kvm *kvm,
 	kvm_flush_remote_tlbs(kvm);
 
 	kvm_mmu_isolate_pages(invalid_list);
-	sp = list_first_entry(invalid_list, struct kvm_mmu_page, link);
-	list_del_init(invalid_list);
-
-	trace_kvm_mmu_delay_free_pages(sp);
-	call_rcu(&sp->rcu, free_pages_rcu);
+	while (!list_empty(invalid_list)) {
+		sp = list_first_entry(invalid_list, struct kvm_mmu_page, link);
+		list_del(&sp->link);
+		trace_kvm_mmu_delay_free_pages(sp);
+		call_rcu(&sp->rcu, free_page_rcu);
+	}
 }
 
 /*
-- 
1.7.10

Re: [PATCH 0/2] Simplify RCU freeing of shadow pages

[Xiao Guangrong]

On 04/20/2012 12:26 AM, Avi Kivity wrote:

> This patchset simplifies the freeing by RCU of mmu pages.
> 
> Xiao, I'm sure you thought of always freeing by RCU.  Why didn't you choose
> this way?  I saves a couple of atomics in the fast path.
> 


Avi, we have discussed it last year:

https://lkml.org/lkml/2011/6/29/177

I have optimized/simplified for "write flood" a lot, but, unfortunately,
the zapping sp is still frequently.

Maybe we can cache the zapped sp in a invalid_sp_list to reduce the
frequency.

Or, we may use SLAB_DESTROY_BY_RCU to free the shadow page.

Re: [PATCH 0/2] Simplify RCU freeing of shadow pages

[Avi Kivity]

On 04/20/2012 07:05 AM, Xiao Guangrong wrote:
> On 04/20/2012 12:26 AM, Avi Kivity wrote:
>
> > This patchset simplifies the freeing by RCU of mmu pages.
> > 
> > Xiao, I'm sure you thought of always freeing by RCU.  Why didn't you choose
> > this way?  I saves a couple of atomics in the fast path.
> > 
>
>
> Avi, we have discussed it last year:
>
> https://lkml.org/lkml/2011/6/29/177

Here are my own measurements (4 way guest on 24-way host):

time make -j8

ept=0, with patch

real    3m54.526s
user    11m7.074s
sys    3m29.678s

real    3m53.806s
user    11m13.654s
sys    3m26.577s

real    3m53.578s
user    11m13.491s
sys    3m26.095s

real    3m53.956s
user    11m14.866s
sys    3m25.075s

ept=1, with patch


real    2m36.510s
user    8m18.905s
sys    1m31.712s

real    2m36.642s
user    8m18.706s
sys    1m31.898s

real    2m36.952s
user    8m20.041s
sys    1m31.929s

real    2m37.036s
user    8m20.204s
sys    1m31.947s

ept=0, unpatched

real    3m51.299s
user    11m23.770s
sys    3m28.049s

real    3m52.982s
user    11m28.419s
sys    3m29.645s

real    3m52.634s
user    11m27.325s
sys    3m29.752s

real    3m53.696s
user    11m30.215s
sys    3m30.146s

ept=1, unpatched

real    2m37.134s
user    8m26.707s
sys    1m33.152s

real    2m36.838s
user    8m26.255s
sys    1m33.078s

real    2m36.826s
user    8m26.917s
sys    1m32.449s

real    2m36.877s
user    8m26.226s
sys    1m32.074s


So there is a small degradation with ept=0 and an even smaller
improvement with ept=1.  But certainly we should give more weight to
ept=1, and also factor in the code simplification.

> I have optimized/simplified for "write flood" a lot, but, unfortunately,
> the zapping sp is still frequently.
>
> Maybe we can cache the zapped sp in a invalid_sp_list to reduce the
> frequency.

To recover the time for re-initializing sp->spt?

> Or, we may use SLAB_DESTROY_BY_RCU to free the shadow page.

IIUC a kmem_cache_alloc() can reuse an allocation freed using
SLAB_DESTROY_BY_RCU before a grace period has elapsed.

-- 
error compiling committee.c: too many arguments to function

Re: [PATCH 0/2] Simplify RCU freeing of shadow pages

[Xiao Guangrong]

On 04/22/2012 09:24 PM, Avi Kivity wrote:

> On 04/20/2012 07:05 AM, Xiao Guangrong wrote:
>> On 04/20/2012 12:26 AM, Avi Kivity wrote:
>>
>>> This patchset simplifies the freeing by RCU of mmu pages.
>>>
>>> Xiao, I'm sure you thought of always freeing by RCU.  Why didn't you choose
>>> this way?  I saves a couple of atomics in the fast path.
>>>
>>
>>
>> Avi, we have discussed it last year:
>>
>> https://lkml.org/lkml/2011/6/29/177
> 
> Here are my own measurements (4 way guest on 24-way host):
> 
> time make -j8
> 
> ept=0, with patch
> 
> real    3m54.526s
> user    11m7.074s
> sys    3m29.678s
> 
> real    3m53.806s
> user    11m13.654s
> sys    3m26.577s
> 
> real    3m53.578s
> user    11m13.491s
> sys    3m26.095s
> 
> real    3m53.956s
> user    11m14.866s
> sys    3m25.075s
> 
> ept=1, with patch
> 
> 
> real    2m36.510s
> user    8m18.905s
> sys    1m31.712s
> 
> real    2m36.642s
> user    8m18.706s
> sys    1m31.898s
> 
> real    2m36.952s
> user    8m20.041s
> sys    1m31.929s
> 
> real    2m37.036s
> user    8m20.204s
> sys    1m31.947s
> 
> ept=0, unpatched
> 
> real    3m51.299s
> user    11m23.770s
> sys    3m28.049s
> 
> real    3m52.982s
> user    11m28.419s
> sys    3m29.645s
> 
> real    3m52.634s
> user    11m27.325s
> sys    3m29.752s
> 
> real    3m53.696s
> user    11m30.215s
> sys    3m30.146s
> 
> ept=1, unpatched
> 
> real    2m37.134s
> user    8m26.707s
> sys    1m33.152s
> 
> real    2m36.838s
> user    8m26.255s
> sys    1m33.078s
> 
> real    2m36.826s
> user    8m26.917s
> sys    1m32.449s
> 
> real    2m36.877s
> user    8m26.226s
> sys    1m32.074s
> 
> 
> So there is a small degradation with ept=0 and an even smaller
> improvement with ept=1.  But certainly we should give more weight to
> ept=1, and also factor in the code simplification.
> 


I agree.

>> I have optimized/simplified for "write flood" a lot, but, unfortunately,
>> the zapping sp is still frequently.
>>
>> Maybe we can cache the zapped sp in a invalid_sp_list to reduce the
>> frequency.
> 
> To recover the time for re-initializing sp->spt?


Batch free shadow page, for example, list 10 sp in the invalid_list, then
just need one rcu_free to free them.

> 
>> Or, we may use SLAB_DESTROY_BY_RCU to free the shadow page.
> 
> IIUC a kmem_cache_alloc() can reuse an allocation freed using
> SLAB_DESTROY_BY_RCU before a grace period has elapsed.
> 


Yes. So we need a refcount out of mmu-lock, and see the shadow page
is stil pointed the upper level (prevent not re-alloced). This way
may make code more complex.

Re: [PATCH 0/2] Simplify RCU freeing of shadow pages

[Marcelo Tosatti]

On Thu, Apr 19, 2012 at 07:26:35PM +0300, Avi Kivity wrote:
> This patchset simplifies the freeing by RCU of mmu pages.
> 
> Xiao, I'm sure you thought of always freeing by RCU.  Why didn't you choose
> this way?  I saves a couple of atomics in the fast path.
> 
> Avi Kivity (2):
>   KVM: MMU: Always free shadow pages using RCU
>   KVM: MMU: Recover space used by rcu_head in struct kvm_mmu_page
> 
>  arch/x86/include/asm/kvm_host.h |    9 +++---
>  arch/x86/kvm/mmu.c              |   58 ++++++++-------------------------------
>  2 files changed, 15 insertions(+), 52 deletions(-)

Check Documentation/RCU/checklist.txt item 8.

        a.      Keeping a count of the number of data-structure elements
                used by the RCU-protected data structure, including
                those waiting for a grace period to elapse.  Enforce a
                limit on this number, stalling updates as needed to allow
                previously deferred frees to complete.  Alternatively,
                limit only the number awaiting deferred free rather than
                the total number of elements.

Re: [PATCH 0/2] Simplify RCU freeing of shadow pages

[Avi Kivity]

On 04/21/2012 05:31 AM, Marcelo Tosatti wrote:
> On Thu, Apr 19, 2012 at 07:26:35PM +0300, Avi Kivity wrote:
> > This patchset simplifies the freeing by RCU of mmu pages.
> > 
> > Xiao, I'm sure you thought of always freeing by RCU.  Why didn't you choose
> > this way?  I saves a couple of atomics in the fast path.
> > 
> > Avi Kivity (2):
> >   KVM: MMU: Always free shadow pages using RCU
> >   KVM: MMU: Recover space used by rcu_head in struct kvm_mmu_page
> > 
> >  arch/x86/include/asm/kvm_host.h |    9 +++---
> >  arch/x86/kvm/mmu.c              |   58 ++++++++-------------------------------
> >  2 files changed, 15 insertions(+), 52 deletions(-)
>
> Check Documentation/RCU/checklist.txt item 8.
>
>         a.      Keeping a count of the number of data-structure elements
>                 used by the RCU-protected data structure, including
>                 those waiting for a grace period to elapse.  Enforce a
>                 limit on this number, stalling updates as needed to allow
>                 previously deferred frees to complete.  Alternatively,
>                 limit only the number awaiting deferred free rather than
>                 the total number of elements.
>

That's true before and after the patch.  Currently the amount of memory
that depends on rcu for freeing is unbounded.

Maybe we should protect the fast path using local_irq_disable() instead
of rcu_read_lock(), like x86 page tables.  That means that
kvm_flush_remote_tlbs() needs to ignore OUTSIDE_GUEST_MODE when IPIing
vcpu threads.

-- 
error compiling committee.c: too many arguments to function

Re: [PATCH 0/2] Simplify RCU freeing of shadow pages

[Xiao Guangrong]

On 04/22/2012 07:39 PM, Avi Kivity wrote:

> On 04/21/2012 05:31 AM, Marcelo Tosatti wrote:
>> On Thu, Apr 19, 2012 at 07:26:35PM +0300, Avi Kivity wrote:
>>> This patchset simplifies the freeing by RCU of mmu pages.
>>>
>>> Xiao, I'm sure you thought of always freeing by RCU.  Why didn't you choose
>>> this way?  I saves a couple of atomics in the fast path.
>>>
>>> Avi Kivity (2):
>>>   KVM: MMU: Always free shadow pages using RCU
>>>   KVM: MMU: Recover space used by rcu_head in struct kvm_mmu_page
>>>
>>>  arch/x86/include/asm/kvm_host.h |    9 +++---
>>>  arch/x86/kvm/mmu.c              |   58 ++++++++-------------------------------
>>>  2 files changed, 15 insertions(+), 52 deletions(-)
>>
>> Check Documentation/RCU/checklist.txt item 8.
>>
>>         a.      Keeping a count of the number of data-structure elements
>>                 used by the RCU-protected data structure, including
>>                 those waiting for a grace period to elapse.  Enforce a
>>                 limit on this number, stalling updates as needed to allow
>>                 previously deferred frees to complete.  Alternatively,
>>                 limit only the number awaiting deferred free rather than
>>                 the total number of elements.
>>
> 
> That's true before and after the patch.  Currently the amount of memory
> that depends on rcu for freeing is unbounded.
> 
> Maybe we should protect the fast path using local_irq_disable() instead
> of rcu_read_lock(), like x86 page tables.  That means that
> kvm_flush_remote_tlbs() needs to ignore OUTSIDE_GUEST_MODE when IPIing
> vcpu threads.

So, IPI is unconditionally sent, do we need introduce a new MODE (say
STOP_SP_FREE) to reduce IPI?

Re: [PATCH 0/2] Simplify RCU freeing of shadow pages

[Avi Kivity]

On 04/23/2012 10:39 AM, Xiao Guangrong wrote:
> On 04/22/2012 07:39 PM, Avi Kivity wrote:
>
> > On 04/21/2012 05:31 AM, Marcelo Tosatti wrote:
> >> On Thu, Apr 19, 2012 at 07:26:35PM +0300, Avi Kivity wrote:
> >>> This patchset simplifies the freeing by RCU of mmu pages.
> >>>
> >>> Xiao, I'm sure you thought of always freeing by RCU.  Why didn't you choose
> >>> this way?  I saves a couple of atomics in the fast path.
> >>>
> >>> Avi Kivity (2):
> >>>   KVM: MMU: Always free shadow pages using RCU
> >>>   KVM: MMU: Recover space used by rcu_head in struct kvm_mmu_page
> >>>
> >>>  arch/x86/include/asm/kvm_host.h |    9 +++---
> >>>  arch/x86/kvm/mmu.c              |   58 ++++++++-------------------------------
> >>>  2 files changed, 15 insertions(+), 52 deletions(-)
> >>
> >> Check Documentation/RCU/checklist.txt item 8.
> >>
> >>         a.      Keeping a count of the number of data-structure elements
> >>                 used by the RCU-protected data structure, including
> >>                 those waiting for a grace period to elapse.  Enforce a
> >>                 limit on this number, stalling updates as needed to allow
> >>                 previously deferred frees to complete.  Alternatively,
> >>                 limit only the number awaiting deferred free rather than
> >>                 the total number of elements.
> >>
> > 
> > That's true before and after the patch.  Currently the amount of memory
> > that depends on rcu for freeing is unbounded.
> > 
> > Maybe we should protect the fast path using local_irq_disable() instead
> > of rcu_read_lock(), like x86 page tables.  That means that
> > kvm_flush_remote_tlbs() needs to ignore OUTSIDE_GUEST_MODE when IPIing
> > vcpu threads.
>
> So, IPI is unconditionally sent, do we need introduce a new MODE (say
> STOP_SP_FREE) to reduce IPI?

We can just reuse IN_GUEST_MODE for this (with a comment explaining why).

-- 
error compiling committee.c: too many arguments to function