Re: [Qemu-devel] [RFC] Next gen kvm api

[Takuya Yoshikawa]

Avi Kivity <address@hidden> wrote:

> > >  Slot searching is quite fast since there's a small number of slots, and 
> > > we sort the larger ones to be in the front, so positive lookups are fast. 
> > >  We cache negative lookups in the shadow page tables (an spte can be 
> > > either "not mapped", "mapped to RAM", or "not mapped and known to be 
> > > mmio") so we rarely need to walk the entire list.
> >
> > Well, we don't always have shadow page tables. Having hints for unmapped 
> > guest memory like this is pretty tricky.
> > We're currently running into issues with device assignment though, where we 
> > get a lot of small slots mapped to real hardware. I'm sure that will hit us 
> > on x86 sooner or later too.
> 
> For x86 that's not a problem, since once you map a page, it stays mapped 
> (on modern hardware).
> 

I was once thinking about how to search a slot reasonably fast for every case,
even when we do not have mmio-spte cache.

One possible way I thought up was to sort slots according to their base_gfn.
Then the problem would become:  "find the first slot whose base_gfn + npages
is greater than this gfn."

Since we can do binary search, the search cost is O(log(# of slots)).

But I guess that most of the time was wasted on reading many memslots just to
know their base_gfn and npages.

So the most practically effective thing is to make a separate array which holds
just their base_gfn.  This will make the task a simple, and cache friendly,
search on an integer array:  probably faster than using *-tree data structure.

If needed, we should make cmp_memslot() architecture specific in the end?

        Takuya