Shadow page table questions

Shadow page table questions

[Marek Olszewski]

Hello,

I was wondering if someone could point me to some documentation that 
explains the basic non-nested-paging shadow page table 
algorithm/strategy used by KVM.  I understand that KVM caches shadow 
page tables across context switches and that there is a reverse mapping 
and page protection to help zap shadow page tables when the guest page 
tables change.  However, I'm not entirely sure how the actual caching is 
done.  At first I assumed that KVM would change the host CR3 on every 
guest context switch such that it would point to a cached shadow page 
table for the currently running guest user thread, however, as far as I 
can tell, the host CR3 does not change so I'm a little lost.  If indeed 
it doesn't change the CR3, how does KVM solve the problem that arises 
when two processes in the guest OS share the same guest logical addresses?

I'm also interested in figuring out what KVM does when running with 
multiple virtual CPUs.  Looking at the code, I can see that each VCPU 
has its own root pointer to a shadow page table graph, but I have yet to 
figure out if this graph has node's shared between VCPUs, or whether 
they are all private.

Any help would be greatly appreciated.  Thanks!

Marek

Re: Shadow page table questions

[Avi Kivity]

On 03/10/2010 06:57 AM, Marek Olszewski wrote:
> Hello,
>
> I was wondering if someone could point me to some documentation that 
> explains the basic non-nested-paging shadow page table 
> algorithm/strategy used by KVM.  I understand that KVM caches shadow 
> page tables across context switches and that there is a reverse 
> mapping and page protection to help zap shadow page tables when the 
> guest page tables change.  However, I'm not entirely sure how the 
> actual caching is done.  At first I assumed that KVM would change the 
> host CR3 on every guest context switch such that it would point to a 
> cached shadow page table for the currently running guest user thread, 
> however, as far as I can tell, the host CR3 does not change so I'm a 
> little lost.  If indeed it doesn't change the CR3, how does KVM solve 
> the problem that arises when two processes in the guest OS share the 
> same guest logical addresses?

The host cr3 does change, though not by using the 'mov cr3' instruction 
(that would cause the host to immediately switch to the guest address 
space, which would be bad).

See the calls to kvm_x86_ops->set_cr3().

>
> I'm also interested in figuring out what KVM does when running with 
> multiple virtual CPUs.  Looking at the code, I can see that each VCPU 
> has its own root pointer to a shadow page table graph, but I have yet 
> to figure out if this graph has node's shared between VCPUs, or 
> whether they are all private.

Everything is shared.  If the guest is running with identical cr3s, kvm 
will load identical cr3s in guest mode.

An exception is when we use 32-bit pae mode.  In that case, the guest 
cr3s will be different (but guest PDPTRs will be identical).  Instead of 
dealing with the pae cr3, we deal with the four PDPTRs.

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

Re: Shadow page table questions

[Marek Olszewski]

Thanks for the response.  I've looked through the code some more and 
think I have figured it out now.   I finally see that the root_hpa 
variable gets switched before entering the guest in mmu_alloc_roots, to 
correspond with the new cr3.  Thanks again.

Perhaps you can help me with one more question.  I was hoping to try out 
a certain change for a research project.   I would like to "privatize" 
kvm_mmu_page's and their spe's for each guest thread running in certain 
designated guest processes.  The goal is to give each thread its own 
shadow page table graphs that map the same guest logical addresses to 
guest physical addresses (with some changes to be introduced later).   
Are there any assumptions that KVM makes that will break if I do 
something like this?  I understand that I will have to add some code 
throughout the mmu to make sure that these structures are synchronized 
when a guest thread makes a change, but I'm wondering if there is 
anything else.  Does the reverse mapping data structure you have assume 
that there is only one shadow page per guest page?

Thanks!

Marek


Avi Kivity wrote:
> On 03/10/2010 06:57 AM, Marek Olszewski wrote:
>> Hello,
>>
>> I was wondering if someone could point me to some documentation that 
>> explains the basic non-nested-paging shadow page table 
>> algorithm/strategy used by KVM.  I understand that KVM caches shadow 
>> page tables across context switches and that there is a reverse 
>> mapping and page protection to help zap shadow page tables when the 
>> guest page tables change.  However, I'm not entirely sure how the 
>> actual caching is done.  At first I assumed that KVM would change the 
>> host CR3 on every guest context switch such that it would point to a 
>> cached shadow page table for the currently running guest user thread, 
>> however, as far as I can tell, the host CR3 does not change so I'm a 
>> little lost.  If indeed it doesn't change the CR3, how does KVM solve 
>> the problem that arises when two processes in the guest OS share the 
>> same guest logical addresses?
>
> The host cr3 does change, though not by using the 'mov cr3' 
> instruction (that would cause the host to immediately switch to the 
> guest address space, which would be bad).
>
> See the calls to kvm_x86_ops->set_cr3().
>
>>
>> I'm also interested in figuring out what KVM does when running with 
>> multiple virtual CPUs.  Looking at the code, I can see that each VCPU 
>> has its own root pointer to a shadow page table graph, but I have yet 
>> to figure out if this graph has node's shared between VCPUs, or 
>> whether they are all private.
>
> Everything is shared.  If the guest is running with identical cr3s, 
> kvm will load identical cr3s in guest mode.
>
> An exception is when we use 32-bit pae mode.  In that case, the guest 
> cr3s will be different (but guest PDPTRs will be identical).  Instead 
> of dealing with the pae cr3, we deal with the four PDPTRs.
>

Re: Shadow page table questions

[Avi Kivity]

On 03/11/2010 02:06 AM, Marek Olszewski wrote:
> Thanks for the response.  I've looked through the code some more and 
> think I have figured it out now.   I finally see that the root_hpa 
> variable gets switched before entering the guest in mmu_alloc_roots, 
> to correspond with the new cr3.  Thanks again.
>
> Perhaps you can help me with one more question.  I was hoping to try 
> out a certain change for a research project.   I would like to 
> "privatize" kvm_mmu_page's and their spe's for each guest thread 
> running in certain designated guest processes.  The goal is to give 
> each thread its own shadow page table graphs that map the same guest 
> logical addresses to guest physical addresses (with some changes to be 
> introduced later).   Are there any assumptions that KVM makes that 
> will break if I do something like this?  I understand that I will have 
> to add some code throughout the mmu to make sure that these structures 
> are synchronized when a guest thread makes a change, but I'm wondering 
> if there is anything else.  Does the reverse mapping data structure 
> you have assume that there is only one shadow page per guest page?

It doesn't, and there are often multiple shadow pages per guest page, 
distinguished by their sp->role field.

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

Re: Shadow page table questions

[Marek Olszewski]

> It doesn't, and there are often multiple shadow pages per guest page, 
> distinguished by their sp->role field. 
Oh, great!  Does this mean that there is already a mechanism for 
synchronizing all shadow pages shadowing the same guest when such a 
guest page changes?

Marek

Re: Shadow page table questions

[Avi Kivity]

On 03/11/2010 06:14 PM, Marek Olszewski wrote:
>> It doesn't, and there are often multiple shadow pages per guest page, 
>> distinguished by their sp->role field. 
> Oh, great!  Does this mean that there is already a mechanism for 
> synchronizing all shadow pages shadowing the same guest when such a 
> guest page changes?

Yes, kvm_mmu_pte_write().

-- 
Do not meddle in the internals of kernels, for they are subtle and quick to panic.

KVM Page Fault Question

[Marek Olszewski]

When using VMX without EPT, is it ever possible for a guest to receive a 
page fault without it first appearing (and being reinjected) in KVM?  
I'm seeing some strange behavior where accesses to mprotected (but yet 
to be accessed) memory causes a fault in the guest OS, that I cannot see 
KVM intercepting.

Thanks!

Marek

Re: KVM Page Fault Question

[Avi Kivity]

On 03/19/2010 01:50 AM, Marek Olszewski wrote:
> When using VMX without EPT, is it ever possible for a guest to receive 
> a page fault without it first appearing (and being reinjected) in KVM? 

Yes.  On Intel hosts only, and controlled by bypass_guest_pf.

> I'm seeing some strange behavior where accesses to mprotected (but yet 
> to be accessed) memory causes a fault in the guest OS, that I cannot 
> see KVM intercepting.
>

Look for 'shadow_trap_nonpresent_pte' (which will trap into kvm) and 
'shadow_notrap_nonpresent_pte' (which will not) in the code.

-- 
Do not meddle in the internals of kernels, for they are subtle and quick to panic.

Re: KVM Page Fault Question

[Marek Olszewski]

When a guest OS writes to a shadowed (and therefore page protected) 
guest page table, does the resulting page fault get handled in 
paging_tmpl.h:xxx_page_fault or does it call some rmap related code 
directly?  Also, what does the "direct" mmu page role mean?

Thanks!

Marek


Avi Kivity wrote:
> On 03/19/2010 01:50 AM, Marek Olszewski wrote:
>> When using VMX without EPT, is it ever possible for a guest to 
>> receive a page fault without it first appearing (and being 
>> reinjected) in KVM? 
>
> Yes.  On Intel hosts only, and controlled by bypass_guest_pf.
>
>> I'm seeing some strange behavior where accesses to mprotected (but 
>> yet to be accessed) memory causes a fault in the guest OS, that I 
>> cannot see KVM intercepting.
>>
>
> Look for 'shadow_trap_nonpresent_pte' (which will trap into kvm) and 
> 'shadow_notrap_nonpresent_pte' (which will not) in the code.
>

Re: KVM Page Fault Question

[Avi Kivity]

On 04/02/2010 07:41 AM, Marek Olszewski wrote:
> When a guest OS writes to a shadowed (and therefore page protected) 
> guest page table, does the resulting page fault get handled in 
> paging_tmpl.h:xxx_page_fault or does it call some rmap related code 
> directly? 

page faults are dispatched to the page_fault callback.

> Also, what does the "direct" mmu page role mean?
>

It means that the page maps the linear range (gfn << 12)..(((gfn + (1 << 
level*9))) << 12) instead of shadowing a guest page table at gfn.  
Useful for real mode, large pages, and tdp.

-- 
Do not meddle in the internals of kernels, for they are subtle and quick to panic.

Re: KVM Page Fault Question

[Avi Kivity]

(re-adding list)


On 04/02/2010 07:01 PM, Marek Olszewski wrote:
> Thanks for the fast response.
>
> I'm trying to find the code that on a write to a guest page table 
> entry, will iterate over all shadow page table entries that map that 
> guest entry to update them.  Can you point me to that code?  I can't 
> seem to find it myself :(

See kvm_mmu_pte_write().

-- 
Do not meddle in the internals of kernels, for they are subtle and quick to panic.

Re: KVM Page Fault Question

[Marek Olszewski]

Under VMX without EPT, I do not seeing any VM Exits due to task 
switches.  Is there a way to enable these?  I'm looking to intercept the 
guest whenever it does a iret.

Thanks!

Marek


Avi Kivity wrote:
> (re-adding list)
>
>
> On 04/02/2010 07:01 PM, Marek Olszewski wrote:
>> Thanks for the fast response.
>>
>> I'm trying to find the code that on a write to a guest page table 
>> entry, will iterate over all shadow page table entries that map that 
>> guest entry to update them.  Can you point me to that code?  I can't 
>> seem to find it myself :(
>
> See kvm_mmu_pte_write().
>

Re: KVM Page Fault Question

[Avi Kivity]

On 04/22/2010 08:26 AM, Marek Olszewski wrote:
> Under VMX without EPT, I do not seeing any VM Exits due to task 
> switches.  Is there a way to enable these?  I'm looking to intercept 
> the guest whenever it does a iret.

See EXIT_REASON_TASK_SWITCH.  However, that won't fire on any iret, only 
irets that generate task switches.  You can ask for exits on irets by 
setting CPU_BASED_VIRTUAL_NMI_PENDING and GUEST_INTR_STATE_NMI, and 
looking for EXIT_REASON_NMI_WINDOW.

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

Re: KVM Page Fault Question

[Marek Olszewski]

Avi,
>
> I guess I only really care about intercepting ring 0 -> ring 3 
> transitions in the guest.  Is there an easier way of intercepting these?
Never mind about this.  I figured out a solution to my problem that 
didn't need to intercept these transitions.

Unfortunately, now I have a new problem.  I'm getting a segfault in 
gfn_to_rmap caused by gfn_to_memslot returning NULL.  Would someone mind 
explaining this code to me?  I don't really understand what it is doing.

Also, does the current code assume that any guest page in any level can 
be shadowed more than once, or are only certain levels allowed to be 
shadowed multiple times?

Thank you!

Marek

>
> Marek
>
>
> Avi Kivity wrote:
>> On 04/22/2010 08:26 AM, Marek Olszewski wrote:
>>> Under VMX without EPT, I do not seeing any VM Exits due to task 
>>> switches.  Is there a way to enable these?  I'm looking to intercept 
>>> the guest whenever it does a iret.
>>
>> See EXIT_REASON_TASK_SWITCH.  However, that won't fire on any iret, 
>> only irets that generate task switches.  You can ask for exits on 
>> irets by setting CPU_BASED_VIRTUAL_NMI_PENDING and 
>> GUEST_INTR_STATE_NMI, and looking for EXIT_REASON_NMI_WINDOW.
>>
>
>

Shadow MMU state preserved across kvm_mmu_zap_all?

[Marek Olszewski]

Hello,

I'm trying to track down a bug I'm observing in a branched version of 
kvm I'm using for research.  I'm hoping someone might be able to point 
me int to the right direction as I haven't had any luck with it on my 
own.  Here are the details:

I have made some changes to kvm that enable guest user applications to 
use duplicate shadow pages to do interesting things (essentially I 
duplicate the shadow page table tree for a process multiple times, once 
for each thread).  During my tests, my guest application enables this 
new feature, completes correctly, and then disables it.  Unfortunately, 
after the test application completes, random programs begin segfaulting 
for unknown reasons.  This is despite the fact that my changes to KVM no 
longer get executed (verified with a kgdb).  At first I thought that I 
corrupted the shadow pages tables somehow, however, calling 
kvm_mmu_zap_all does not solve the problem.  Thus, I figured I corrupted 
the guest OS somehow, however, the problem persists even if I reboot the 
guest OS.  

So my question is this: Are there any other data structures that survive 
both a call to kvm_mmu_zap and a guest reboot?

Thanks!

Marek

Shadow page table questions

[Arne Mejlholm]

Dear All,

I'm trying to understand some of the details of the shadow page table
implementation. In particular I'm interested in the inner workings of
translated mode.

Now as I understand it, the principle behind Shadow Page Tables (SPTs)
is to provide a level of indirection between virtual and machine
addresses. In Xen this is implemented by a P2M table for each domain (at
least in translated mode this address space is reused). Each entry in
this table is indexed by "physical" addresses and point to a given
machine frame number (mfn). As far as I can tell from the code, this
structure is walked much like a normal page table. In translated mode
the guest VM however cannot make use of the two level lookup (first
from virtual to physical and then from physical to machine addresses),
so a hardware specific version (the SPT) of the two mappings is
produced and given to the MMU instead of the ordinary page table.

My first question is have the status bits of each entry in the P2M
table changed semantics (compared to a normal l1 entry) or do they
signify the same flags? If the read/write flag is not set (read only),
will this be propagated to the SPT seen by the MMU?

Normally producing a SPT each time a the cr3 register is updated (as
required per context switch), is considered to be an overhead. One
solution to this is to make use of a cache, where references to old
SPTs are kept. This again involves the overhead in terms of memory
usage and tracking if the cached SPT is valid.

My second question is thus, does the implementation make use of a SPT
cache or are SPTs produced on demand? If a cache is used, can anyone
give me pointers to where I can find this structure?

The implementation makes use of snapshots, how do these fit into big
picture?

Finally some of the terminology used for the implementation seems a
bit un-intuitive to me. Throughout the source, there is the concept of
a hl2 table. As far as I can tell, a l2 table is the PGD in Linux
kernel terminology and a l1 table is the table pointed to by an entry
in the l2 table (PT in Linux). My first guess was that the hl2 table
was the table actually pointed to by the cr3 register, but I cannot
seem to confirm this. What does the h in hl2 stand for and what is it
used for?

Thank you,
Arne Mejlholm