Re: [PATCH 3/6] KVM: Dirty memory tracking for performant checkpointing and improved live migration

["Radim Krčmář" <rkrcmar@redhat.com>]

2016-05-04 17:15+0000, Cao, Lei:
> On 5/4/2016 9:13 AM, Radim Krčmář wrote:
>> Good designs so far seem to be:
>>  memslot -> lockless radix tree
>> and
>>  vcpu -> memslot -> list  (memslot -> vcpu -> list)
>>
> 
> There is no need for lookup, the dirty log is fetched in sequence, so why use
> radix tree with added complexity but no benefit?
> 
> List can be designed to be lockless, so memslot -> lockless fixed list?

It can, but lockless list for concurrent writers is harder than lockless
list for a concurrent writer and reader.
The difference is in starvation -- it's possible that VCPU would never
get to write an entry unless you implemented a queueing mechanism.
A queueing mechanism means that you basically have a spinlock, so I
wouldn't bother with a lockless list and just try spinlock directly.

A spinlock with very short critical section might actually work well for
< 256 VCPU and is definitely the easiest option.  Worth experimenting
with, IMO.

Lockless radix tree doesn't starve.  Every entry has a well defined
place in the tree.  The entry just might not be fully allocated yet.
If another VCPU is faster and expands the tree, then other VCPUs use
that extended tree until they all get to their leaf nodes, VCPUs
basically cooperate on growing the tree.

And I completely forgot that we can preallocate the whole tree and use a
effective packed storage thanks to that.  My first guess is that it
would be make sense with double the memory of our bitmap.  Scans and
insertion would be slower than for a per-vcpu list, but much faster than
with a dynamically allocated structure.  I'll think a bit about that.

The main reason why I'd like something that can contain all dirty pages
is overflow -- the userspace has to treat *all* pages as dirty if we
lose a dirty page, so overflow must never happen -- we have to either
grow the dirty log or suspend the writer until userspace frees space ...