Re: [patch 09/13] KVM: MMU: out of sync shadow core

[Marcelo Tosatti <mtosatti@redhat.com>]

On Mon, Sep 08, 2008 at 05:51:26PM +0300, Avi Kivity wrote:
> Marcelo Tosatti wrote:
>>> I'm worried about the complexity this (and the rest) introduces.
>>>
>>> A possible alternative is:
>>>
>>> - for non-leaf pages, including roots, add a 'unsync_children' flag.
>>> - when marking a page unsync, set the flag recursively on all parents
>>> - when switching cr3, recursively descend to locate unsynced leaves,  
>>> clearing flags along the way
>>> - to speed this up, put a bitmap with 1 bit per pte in the pages (512 
>>>  bits = 64 bytes)
>>> - the bitmap can be externally allocated to save space, or not
>>>
>>> This means we no longer have to worry about multiple roots, when a 
>>> page  acquires another root while it is unsynced, etc.
>>>     
>>
>> I thought about that when you first mentioned it, but it seems more
>> complex than the current structure. Remember you have to clean the
>> unsynced flag on resync, which means walking up the parents verifying if
>> this is the last unsynced children.
>>   
>
> No, if you have a false positive you can simply ignore it.
>
>> Other than the bitmap space.
>>   
>
> The bitmap space could be stored in a separate structure.   
> Alternatively, put a few u16s with indexes into the page header.  Would  
> be faster to walk as well, though less general.
>
>> And see comments about multiple roles below.
>>
>>   
>>>> @@ -963,8 +1112,24 @@ static struct kvm_mmu_page *kvm_mmu_get_
>>>>  		 gfn, role.word);
>>>>  	index = kvm_page_table_hashfn(gfn);
>>>>  	bucket = &vcpu->kvm->arch.mmu_page_hash[index];
>>>> -	hlist_for_each_entry(sp, node, bucket, hash_link)
>>>> -		if (sp->gfn == gfn && sp->role.word == role.word) {
>>>> +	hlist_for_each_entry_safe(sp, node, tmp, bucket, hash_link)
>>>> +		if (sp->gfn == gfn) {
>>>> +			/*
>>>> + 			 * If a pagetable becomes referenced by more than one
>>>> + 			 * root, or has multiple roles, unsync it and disable
>>>> + 			 * oos. For higher level pgtables the entire tree
>>>> + 			 * has to be synced.
>>>> + 			 */
>>>> +			if (sp->root_gfn != root_gfn) {
>>>> +				kvm_set_pg_inuse(sp);
>>>>         
>>> What does inuse mean exactly?
>>>     
>>
>> That we're going to access struct kvm_mmu_page, so kvm_sync_page won't
>> free it (also used for global->nonglobal resync).
>>
>>   
>
> Couldn't it be passed as a parameter?

Yes it could.

>>> I became a little unsynced myself reading the patch.  It's very complex.
>>>     
>>
>> Can you go into detail? Worrying about multiple roots is more about
>> code change (passing root_gfn down to mmu_get_page etc) than structural
>> complexity I think. It boils down to
>>
>>                     if (sp->root_gfn != root_gfn) {
>>                         kvm_set_pg_inuse(sp);
>>                         if (set_shared_mmu_page(vcpu, sp))
>>                             tmp = bucket->first;
>>                         kvm_clear_pg_inuse(sp);
>>                     }
>>
>> And this also deals with the pagetable with shadows in different
>> modes/roles case. You'd still have to deal with that by keeping unsync
>> information all the way up to root.
>>
>>   
>
> I'm worried about the amount of state we add.  Whether a page is  
> single-root or multi-root, if it's in the same mode or multiple modes.   

You need similar complexity to handle pagetables with multiple roles
under unsync-info-on-tree approach:

@@ -993,8 +1049,15 @@ static struct kvm_mmu_page *kvm_mmu_get_
                 gfn, role.word);
        index = kvm_page_table_hashfn(gfn);
        bucket = &vcpu->kvm->arch.mmu_page_hash[index];
-       hlist_for_each_entry(sp, node, bucket, hash_link)
-               if (sp->gfn == gfn && sp->role.word == role.word) {
+       hlist_for_each_entry_safe(sp, node, tmp, bucket, hash_link)
+               if (sp->gfn == gfn) {
+                       if (sp->role.word != role.word) {
+                               if (kvm_page_unsync(sp))
+                                       mmu_invalidate_unsync_page(vcpu, sp);
+                               unsyncable = 1;
+                               continue;
+                       }
+
                        mmu_page_add_parent_pte(vcpu, sp, parent_pte);
                        pgprintk("%s: found\n", __func__);
                        return sp;

And such pagetables with multiple shadows will have to be marked as
"unsyncable". Which is pretty similar to what the current patchset does,
except that it accounts for multi-root other than multiple shadows.

The other option, which is to keep the multiple shadow unsync, and have
them synced by their respective users, seems much more complex than
this.

> The problems with the large amount of state is that the number of  
> possible state transitions increases rapidly.
>
> So far we treat each page completely independently of other pages (apart  
> from the connectivity pointers), so we avoid the combinatorial  
> explosion.  The tree walk approach keeps that (at the expense of some  
> efficiency, unfortunately).
>
>>> or disallowing a parent to be zapped while any of its  children are 
>>> alive.
>>>     
>>
>> What is the problem with that? 
>
> It reduces the mmu flexibility.  If we (say) introduce an lru algorithm,  
> it is orthogonal to everything else in the mmu.  If we have a root/child  
> dependency, the lru has to know.
>
>> And what the alternative would be, to zap all children first?
>>   
>
> That has the disadvantage of allowing very bad corner cases if we are  
> forced to zap a root.
>
> I'd really like to avoid bad worst cases.
>
>> So more details please, what exactly is annoying you:
>>
>> - Awareness of multiple roots in the current form ? I agree its
>>   not very elegant.
>>   
>
> Yes.
>
>> - The fact that hash table bucket and active_mmu_page
>>   for_each_entry_safe walks are unsafe because several list
>>   entries (the unsynced leafs) can be deleted ?
>>
>>   
>
> Hadn't even considered that...
>
> What worries me most is that everything is interconnected: multiple  
> modes, cr3 switch, out-of-sync, zapping via the inuse flag.  It's very  
> difficult for me to understand, what about someone new?
>
> We need to make this fit better.  We need to morph some mmu  
> infrastructure to something else, but we can't keep adding complexity.

Another point that came to mind is that, with the unsync-info-on-tree
approach, whenever a higher level pagetable is zapped all of its
unsynced children need to be zapped.

Since at the moment resync on atomic context is not an option, the only
option is to zap the children, potentially wasting a lot of shadowed
entries. This is not an issue with the current approach since unsync
children are tied to roots, not every parents all the way to root.

I'll measure how often that happens, but seems a bad side effect.