[PATCH 0/1 v2] KVM: MMU: Optimize guest page table walk

[PATCH 0/1 v2] KVM: MMU: Optimize guest page table walk

[Takuya Yoshikawa]

Changelog v1->v2: dropped slot_hint and wrapper.

As Avi said, get_user() alone achieved most of the improvement.

Before
  2.994 us   |  paging64_walk_addr_generic();
  1.480 us   |  paging64_walk_addr_generic();
  0.996 us   |  paging64_walk_addr_generic();
  1.108 us   |  paging64_walk_addr_generic();
  0.962 us   |  paging64_walk_addr_generic();
  2.063 us   |  paging64_walk_addr_generic();
  1.379 us   |  paging64_walk_addr_generic();
  0.962 us   |  paging64_walk_addr_generic();
  1.085 us   |  paging64_walk_addr_generic();
  2.965 us   |  paging64_walk_addr_generic();

After
  2.264 us   |  paging64_walk_addr_generic();
  1.079 us   |  paging64_walk_addr_generic();
  0.648 us   |  paging64_walk_addr_generic();
  0.703 us   |  paging64_walk_addr_generic();
  0.635 us   |  paging64_walk_addr_generic();
  0.869 us   |  paging64_walk_addr_generic();
  0.529 us   |  paging64_walk_addr_generic();
  0.702 us   |  paging64_walk_addr_generic();
  0.529 us   |  paging64_walk_addr_generic();
  0.691 us   |  paging64_walk_addr_generic();


A little surprise was that the original version itself was
a bit fater than before.

But I tested this with today's latest kvm.git and some parts
had been changed, so it could be.

Anyway, this patch improves by some degree!


Takuya

[PATCH 1/1 v2] KVM: MMU: Optimize guest page table walk

[Takuya Yoshikawa]

From: Takuya Yoshikawa <yoshikawa.takuya@oss.ntt.co.jp>

This patch optimizes the guest page table walk by using get_user()
instead of copy_from_user().

With this patch applied, paging64_walk_addr_generic() has become
about 0.5us to 1.0us faster on my Phenom II machine with NPT on.

Signed-off-by: Takuya Yoshikawa <yoshikawa.takuya@oss.ntt.co.jp>
---
 arch/x86/kvm/paging_tmpl.h |   23 ++++++++++++++++++++---
 1 files changed, 20 insertions(+), 3 deletions(-)

diff --git a/arch/x86/kvm/paging_tmpl.h b/arch/x86/kvm/paging_tmpl.h
index 74f8567..825d953 100644
--- a/arch/x86/kvm/paging_tmpl.h
+++ b/arch/x86/kvm/paging_tmpl.h
@@ -117,6 +117,7 @@ static int FNAME(walk_addr_generic)(struct guest_walker *walker,
 				    gva_t addr, u32 access)
 {
 	pt_element_t pte;
+	pt_element_t __user *ptep_user;
 	gfn_t table_gfn;
 	unsigned index, pt_access, uninitialized_var(pte_access);
 	gpa_t pte_gpa;
@@ -152,6 +153,9 @@ walk:
 	pt_access = ACC_ALL;
 
 	for (;;) {
+		gfn_t real_gfn;
+		unsigned long host_addr;
+
 		index = PT_INDEX(addr, walker->level);
 
 		table_gfn = gpte_to_gfn(pte);
@@ -160,9 +164,22 @@ walk:
 		walker->table_gfn[walker->level - 1] = table_gfn;
 		walker->pte_gpa[walker->level - 1] = pte_gpa;
 
-		if (kvm_read_guest_page_mmu(vcpu, mmu, table_gfn, &pte,
-					    offset, sizeof(pte),
-					    PFERR_USER_MASK|PFERR_WRITE_MASK)) {
+		real_gfn = mmu->translate_gpa(vcpu, gfn_to_gpa(table_gfn),
+					      PFERR_USER_MASK|PFERR_WRITE_MASK);
+		if (real_gfn == UNMAPPED_GVA) {
+			present = false;
+			break;
+		}
+		real_gfn = gpa_to_gfn(real_gfn);
+
+		host_addr = gfn_to_hva(vcpu->kvm, real_gfn);
+		if (kvm_is_error_hva(host_addr)) {
+			present = false;
+			break;
+		}
+
+		ptep_user = (pt_element_t __user *)((void *)host_addr + offset);
+		if (get_user(pte, ptep_user)) {
 			present = false;
 			break;
 		}
-- 
1.7.1

Re: [PATCH 1/1 v2] KVM: MMU: Optimize guest page table walk

[Avi Kivity]

On 04/21/2011 06:34 PM, Takuya Yoshikawa wrote:
> From: Takuya Yoshikawa<yoshikawa.takuya@oss.ntt.co.jp>
>
> This patch optimizes the guest page table walk by using get_user()
> instead of copy_from_user().
>
> With this patch applied, paging64_walk_addr_generic() has become
> about 0.5us to 1.0us faster on my Phenom II machine with NPT on.

Applied, thanks.  Care to send a follow-on patch that makes 
cmpxchg_gpte() use ptep_user instead of calculating it by itself?

-- 
I have a truly marvellous patch that fixes the bug which this
signature is too narrow to contain.

Re: [PATCH 1/1 v2] KVM: MMU: Optimize guest page table walk

[Takuya Yoshikawa]

On Sun, 24 Apr 2011 10:27:06 +0300
Avi Kivity <avi@redhat.com> wrote:

> On 04/21/2011 06:34 PM, Takuya Yoshikawa wrote:
> > From: Takuya Yoshikawa<yoshikawa.takuya@oss.ntt.co.jp>
> >
> > This patch optimizes the guest page table walk by using get_user()
> > instead of copy_from_user().
> >
> > With this patch applied, paging64_walk_addr_generic() has become
> > about 0.5us to 1.0us faster on my Phenom II machine with NPT on.
> 
> Applied, thanks.  Care to send a follow-on patch that makes 
> cmpxchg_gpte() use ptep_user instead of calculating it by itself?

I'll send the patch soon!
  I was not sure if others might be preparing it.

Takuya

Re: [PATCH 1/1 v2] KVM: MMU: Optimize guest page table walk

[Jan Kiszka]

[-- Attachment #1: Type: text/plain, Size: 2222 bytes --]

On 2011-04-21 17:34, Takuya Yoshikawa wrote:
> From: Takuya Yoshikawa <yoshikawa.takuya@oss.ntt.co.jp>
> 
> This patch optimizes the guest page table walk by using get_user()
> instead of copy_from_user().
> 
> With this patch applied, paging64_walk_addr_generic() has become
> about 0.5us to 1.0us faster on my Phenom II machine with NPT on.
> 
> Signed-off-by: Takuya Yoshikawa <yoshikawa.takuya@oss.ntt.co.jp>
> ---
>  arch/x86/kvm/paging_tmpl.h |   23 ++++++++++++++++++++---
>  1 files changed, 20 insertions(+), 3 deletions(-)
> 
> diff --git a/arch/x86/kvm/paging_tmpl.h b/arch/x86/kvm/paging_tmpl.h
> index 74f8567..825d953 100644
> --- a/arch/x86/kvm/paging_tmpl.h
> +++ b/arch/x86/kvm/paging_tmpl.h
> @@ -117,6 +117,7 @@ static int FNAME(walk_addr_generic)(struct guest_walker *walker,
>  				    gva_t addr, u32 access)
>  {
>  	pt_element_t pte;
> +	pt_element_t __user *ptep_user;
>  	gfn_t table_gfn;
>  	unsigned index, pt_access, uninitialized_var(pte_access);
>  	gpa_t pte_gpa;
> @@ -152,6 +153,9 @@ walk:
>  	pt_access = ACC_ALL;
>  
>  	for (;;) {
> +		gfn_t real_gfn;
> +		unsigned long host_addr;
> +
>  		index = PT_INDEX(addr, walker->level);
>  
>  		table_gfn = gpte_to_gfn(pte);
> @@ -160,9 +164,22 @@ walk:
>  		walker->table_gfn[walker->level - 1] = table_gfn;
>  		walker->pte_gpa[walker->level - 1] = pte_gpa;
>  
> -		if (kvm_read_guest_page_mmu(vcpu, mmu, table_gfn, &pte,
> -					    offset, sizeof(pte),
> -					    PFERR_USER_MASK|PFERR_WRITE_MASK)) {
> +		real_gfn = mmu->translate_gpa(vcpu, gfn_to_gpa(table_gfn),
> +					      PFERR_USER_MASK|PFERR_WRITE_MASK);
> +		if (real_gfn == UNMAPPED_GVA) {
> +			present = false;
> +			break;
> +		}
> +		real_gfn = gpa_to_gfn(real_gfn);
> +
> +		host_addr = gfn_to_hva(vcpu->kvm, real_gfn);
> +		if (kvm_is_error_hva(host_addr)) {
> +			present = false;
> +			break;
> +		}
> +
> +		ptep_user = (pt_element_t __user *)((void *)host_addr + offset);
> +		if (get_user(pte, ptep_user)) {
                    ^^^^^^^^^^^^
This doesn't work for x86-32: pte is 64 bit, but get_user is only
defined up to 32 bit on that platform.

Avi, what's your 32-bit buildbot doing? :)

Jan


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 259 bytes --]

Re: [PATCH 1/1 v2] KVM: MMU: Optimize guest page table walk

[Takuya Yoshikawa]

On Mon, 25 Apr 2011 10:04:43 +0200
Jan Kiszka <jan.kiszka@web.de> wrote:

> > +
> > +		ptep_user = (pt_element_t __user *)((void *)host_addr + offset);
> > +		if (get_user(pte, ptep_user)) {
>                     ^^^^^^^^^^^^
> This doesn't work for x86-32: pte is 64 bit, but get_user is only
> defined up to 32 bit on that platform.
> 
> Avi, what's your 32-bit buildbot doing? :)
> 
> Jan
> 

Sorry, I did not test on x86_32.

Introducing a wrapper function with ifdef would be the best way?


Takuya

Re: [PATCH 1/1 v2] KVM: MMU: Optimize guest page table walk

[Jan Kiszka]

[-- Attachment #1: Type: text/plain, Size: 746 bytes --]

On 2011-04-25 10:32, Takuya Yoshikawa wrote:
> On Mon, 25 Apr 2011 10:04:43 +0200
> Jan Kiszka <jan.kiszka@web.de> wrote:
> 
>>> +
>>> +		ptep_user = (pt_element_t __user *)((void *)host_addr + offset);
>>> +		if (get_user(pte, ptep_user)) {
>>                     ^^^^^^^^^^^^
>> This doesn't work for x86-32: pte is 64 bit, but get_user is only
>> defined up to 32 bit on that platform.
>>
>> Avi, what's your 32-bit buildbot doing? :)
>>
>> Jan
>>
> 
> Sorry, I did not test on x86_32.
> 
> Introducing a wrapper function with ifdef would be the best way?
> 

Maybe you could also add the missing 64-bit get_user for x86-32. Given
that we have a corresponding put_user, I wonder why the get_user was
left out.

Jan


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 259 bytes --]

Re: [PATCH 1/1 v2] KVM: MMU: Optimize guest page table walk

[Takuya Yoshikawa]

On Mon, 25 Apr 2011 11:15:20 +0200
Jan Kiszka <jan.kiszka@web.de> wrote:

> > Sorry, I did not test on x86_32.
> > 
> > Introducing a wrapper function with ifdef would be the best way?
> > 
> 
> Maybe you could also add the missing 64-bit get_user for x86-32. Given
> that we have a corresponding put_user, I wonder why the get_user was
> left out.
> 
> Jan
> 

Google said that there was a similar talk on LKML in 2004.

On that threads, Linus explained how to tackle on the 64-bit get_user
implementation.  But I could not see what happened after that.

Takuya

Re: [PATCH 1/1 v2] KVM: MMU: Optimize guest page table walk

[Jan Kiszka]

[-- Attachment #1: Type: text/plain, Size: 843 bytes --]

On 2011-04-26 06:50, Takuya Yoshikawa wrote:
> On Mon, 25 Apr 2011 11:15:20 +0200
> Jan Kiszka <jan.kiszka@web.de> wrote:
> 
>>> Sorry, I did not test on x86_32.
>>>
>>> Introducing a wrapper function with ifdef would be the best way?
>>>
>>
>> Maybe you could also add the missing 64-bit get_user for x86-32. Given
>> that we have a corresponding put_user, I wonder why the get_user was
>> left out.
>>
>> Jan
>>
> 
> Google said that there was a similar talk on LKML in 2004.
> 
> On that threads, Linus explained how to tackle on the 64-bit get_user
> implementation.  But I could not see what happened after that.

Mmh, maybe the kernel was lacking a real use case, so no one seriously
cared.

I don't see a fundamental blocker for an x86-32 __get_user_8 version
based on two mov. I would give it a try.

Jan


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 259 bytes --]

Re: [PATCH 1/1 v2] KVM: MMU: Optimize guest page table walk

[Avi Kivity]

On 04/25/2011 11:04 AM, Jan Kiszka wrote:
> >  +
> >  +		ptep_user = (pt_element_t __user *)((void *)host_addr + offset);
> >  +		if (get_user(pte, ptep_user)) {
>                      ^^^^^^^^^^^^
> This doesn't work for x86-32: pte is 64 bit, but get_user is only
> defined up to 32 bit on that platform.
>

I actually considered this, and saw:

#ifdef CONFIG_X86_32
#define __get_user_8(__ret_gu, __val_gu, ptr)                \
         __get_user_x(X, __ret_gu, __val_gu, ptr)
#else
#define __get_user_8(__ret_gu, __val_gu, ptr)                \
         __get_user_x(8, __ret_gu, __val_gu, ptr)
#endif

#define get_user(x, ptr)                        \
({                                    \
     int __ret_gu;                            \
     unsigned long __val_gu;                        \
     __chk_user_ptr(ptr);                        \
     might_fault();                            \
     switch (sizeof(*(ptr))) {                    \

...

     case 8:                                \
         __get_user_8(__ret_gu, __val_gu, ptr);            \
         break;                            \

...

     }                                \
     (x) = (__typeof__(*(ptr)))__val_gu;                \
     __ret_gu;                            \
})

so it should work.  How does it fail?

> Avi, what's your 32-bit buildbot doing? :)

I regularly autotest on x86_64, not on i386, sorry.

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

Re: [PATCH 1/1 v2] KVM: MMU: Optimize guest page table walk

[Jan Kiszka]

[-- Attachment #1: Type: text/plain, Size: 1710 bytes --]

On 2011-04-26 09:42, Avi Kivity wrote:
> On 04/25/2011 11:04 AM, Jan Kiszka wrote:
>> >  +
>> >  +        ptep_user = (pt_element_t __user *)((void *)host_addr +
>> offset);
>> >  +        if (get_user(pte, ptep_user)) {
>>                      ^^^^^^^^^^^^
>> This doesn't work for x86-32: pte is 64 bit, but get_user is only
>> defined up to 32 bit on that platform.
>>
> 
> I actually considered this, and saw:
> 
> #ifdef CONFIG_X86_32
> #define __get_user_8(__ret_gu, __val_gu, ptr)                \
>         __get_user_x(X, __ret_gu, __val_gu, ptr)
> #else
> #define __get_user_8(__ret_gu, __val_gu, ptr)                \
>         __get_user_x(8, __ret_gu, __val_gu, ptr)
> #endif
> 
> #define get_user(x, ptr)                        \
> ({                                    \
>     int __ret_gu;                            \
>     unsigned long __val_gu;                        \
>     __chk_user_ptr(ptr);                        \
>     might_fault();                            \
>     switch (sizeof(*(ptr))) {                    \
> 
> ...
> 
>     case 8:                                \
>         __get_user_8(__ret_gu, __val_gu, ptr);            \
>         break;                            \
> 
> ...
> 
>     }                                \
>     (x) = (__typeof__(*(ptr)))__val_gu;                \
>     __ret_gu;                            \
> })
> 
> so it should work.  How does it fail?

On x86-32, the above macro resolves to __get_user_X, an undefined symbol.

> 
>> Avi, what's your 32-bit buildbot doing? :)
> 
> I regularly autotest on x86_64, not on i386, sorry.

Good that it's included in my kvm-kmod buildbot.

Jan


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 259 bytes --]

Re: [PATCH 1/1 v2] KVM: MMU: Optimize guest page table walk

[Avi Kivity]

On 04/26/2011 10:45 AM, Jan Kiszka wrote:
> On 2011-04-26 09:42, Avi Kivity wrote:
> >  On 04/25/2011 11:04 AM, Jan Kiszka wrote:
> >>  >   +
> >>  >   +        ptep_user = (pt_element_t __user *)((void *)host_addr +
> >>  offset);
> >>  >   +        if (get_user(pte, ptep_user)) {
> >>                       ^^^^^^^^^^^^
> >>  This doesn't work for x86-32: pte is 64 bit, but get_user is only
> >>  defined up to 32 bit on that platform.
> >>
> >
> >  I actually considered this, and saw:
> >
> >  #ifdef CONFIG_X86_32
> >  #define __get_user_8(__ret_gu, __val_gu, ptr)                \
> >          __get_user_x(X, __ret_gu, __val_gu, ptr)
> >  #else
> >  #define __get_user_8(__ret_gu, __val_gu, ptr)                \
> >          __get_user_x(8, __ret_gu, __val_gu, ptr)
> >  #endif
> >
> >  #define get_user(x, ptr)                        \
> >  ({                                    \
> >      int __ret_gu;                            \
> >      unsigned long __val_gu;                        \
> >      __chk_user_ptr(ptr);                        \
> >      might_fault();                            \
> >      switch (sizeof(*(ptr))) {                    \
> >
> >  ...
> >
> >      case 8:                                \
> >          __get_user_8(__ret_gu, __val_gu, ptr);            \
> >          break;                            \
> >
> >  ...
> >
> >      }                                \
> >      (x) = (__typeof__(*(ptr)))__val_gu;                \
> >      __ret_gu;                            \
> >  })
> >
> >  so it should work.  How does it fail?
>
> On x86-32, the above macro resolves to __get_user_X, an undefined symbol.
>

Tricky stuff.

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

Re: [PATCH 1/1 v2] KVM: MMU: Optimize guest page table walk

[Takuya Yoshikawa]

On Tue, 26 Apr 2011 08:34:57 +0200
Jan Kiszka <jan.kiszka@web.de> wrote:

> > Google said that there was a similar talk on LKML in 2004.
> > 
> > On that threads, Linus explained how to tackle on the 64-bit get_user
> > implementation.  But I could not see what happened after that.
> 
> Mmh, maybe the kernel was lacking a real use case, so no one seriously
> cared.
> 
> I don't see a fundamental blocker for an x86-32 __get_user_8 version
> based on two mov. I would give it a try.
> 
> Jan
> 

Thank you!

Avi, do we revert the patch now, or ...?

Takuya

Re: [PATCH 1/1 v2] KVM: MMU: Optimize guest page table walk

[Avi Kivity]

On 04/26/2011 05:40 PM, Takuya Yoshikawa wrote:
> On Tue, 26 Apr 2011 08:34:57 +0200
> Jan Kiszka<jan.kiszka@web.de>  wrote:
>
> >  >  Google said that there was a similar talk on LKML in 2004.
> >  >
> >  >  On that threads, Linus explained how to tackle on the 64-bit get_user
> >  >  implementation.  But I could not see what happened after that.
> >
> >  Mmh, maybe the kernel was lacking a real use case, so no one seriously
> >  cared.
> >
> >  I don't see a fundamental blocker for an x86-32 __get_user_8 version
> >  based on two mov. I would give it a try.
> >
> >  Jan
> >
>
> Thank you!
>
> Avi, do we revert the patch now, or ...?

Please post a simple patch that uses two get_user()s for that case 
(64-bit pte on 32-bit host).  Then work with the x86 tree to see if 
they'll accept 64-bit get_user(), and once they do, we can go back to a 
simple get_user() again.

btw, I think we can use __get_user() here since the address must have 
been already validated.

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

Re: [PATCH 1/1 v2] KVM: MMU: Optimize guest page table walk

[Takuya Yoshikawa]

> Please post a simple patch that uses two get_user()s for that case 
> (64-bit pte on 32-bit host).  Then work with the x86 tree to see if 
> they'll accept 64-bit get_user(), and once they do, we can go back to a 
> simple get_user() again.
> 
> btw, I think we can use __get_user() here since the address must have 
> been already validated.

Yes, I thought that at first.

But don't we need to care KVM's address translation bugs?

Takuya

Re: [PATCH 1/1 v2] KVM: MMU: Optimize guest page table walk

[Takuya Yoshikawa]

On Tue, 26 Apr 2011 17:54:24 +0300
Avi Kivity <avi@redhat.com> wrote:

> Please post a simple patch that uses two get_user()s for that case 
> (64-bit pte on 32-bit host).  Then work with the x86 tree to see if 
> they'll accept 64-bit get_user(), and once they do, we can go back to a 
> simple get_user() again.
> 

I made a patch which seems to reflect what you said!
If this kind of fix is OK with you, I'll test on both x86_32 and x86_64,
and send the patch with some changelog tomorrow.

Thanks,
  Takuya

---
 arch/x86/kvm/paging_tmpl.h |   16 +++++++++++++++-
 1 files changed, 15 insertions(+), 1 deletions(-)

diff --git a/arch/x86/kvm/paging_tmpl.h b/arch/x86/kvm/paging_tmpl.h
index a32a1c8..1e44969 100644
--- a/arch/x86/kvm/paging_tmpl.h
+++ b/arch/x86/kvm/paging_tmpl.h
@@ -115,6 +115,20 @@ static unsigned FNAME(gpte_access)(struct kvm_vcpu *vcpu, pt_element_t gpte)
 	return access;
 }
 
+static int FNAME(read_gpte)(pt_element_t *pte, pt_element_t __user *ptep_user)
+{
+#if defined(CONFIG_X86_32) && (PTTYPE == 64)
+	u32 *p = (u32 *)pte;
+	u32 __user *p_user = (u32 __user *)ptep_user;
+
+	if (get_user(*p, p_user))
+		return -EFAULT;
+	return get_user(*(p + 1), p_user + 1);
+#else
+	return get_user(*pte, ptep_user);
+#endif
+}
+
 /*
  * Fetch a guest pte for a guest virtual address
  */
@@ -185,7 +199,7 @@ walk:
 		}
 
 		ptep_user = (pt_element_t __user *)((void *)host_addr + offset);
-		if (get_user(pte, ptep_user)) {
+		if (FNAME(read_gpte)(&pte, ptep_user)) {
 			present = false;
 			break;
 		}
-- 
1.7.1

Re: [PATCH 1/1 v2] KVM: MMU: Optimize guest page table walk

[Avi Kivity]

On 04/26/2011 06:13 PM, Takuya Yoshikawa wrote:
> >  Please post a simple patch that uses two get_user()s for that case
> >  (64-bit pte on 32-bit host).  Then work with the x86 tree to see if
> >  they'll accept 64-bit get_user(), and once they do, we can go back to a
> >  simple get_user() again.
> >
> >  btw, I think we can use __get_user() here since the address must have
> >  been already validated.
>
> Yes, I thought that at first.
>
> But don't we need to care KVM's address translation bugs?

It's a pity to do a runtime check when we can do a setup time check 
instead.  So let's review the setup code and then use __get_user().

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

Re: [PATCH 1/1 v2] KVM: MMU: Optimize guest page table walk

[Avi Kivity]

On 04/26/2011 07:26 PM, Takuya Yoshikawa wrote:
> On Tue, 26 Apr 2011 17:54:24 +0300
> Avi Kivity<avi@redhat.com>  wrote:
>
> >  Please post a simple patch that uses two get_user()s for that case
> >  (64-bit pte on 32-bit host).  Then work with the x86 tree to see if
> >  they'll accept 64-bit get_user(), and once they do, we can go back to a
> >  simple get_user() again.
> >
>
> I made a patch which seems to reflect what you said!
> If this kind of fix is OK with you, I'll test on both x86_32 and x86_64,
> and send the patch with some changelog tomorrow.
>

Yes, that looks right.

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