On 5/6/2016 12:04 PM, Radim Krčmář wrote: > 2016-05-06 15:13+0000, Cao, Lei: >> On 5/6/2016 8:09 AM, Radim Krčmář wrote: >>> 2016-05-06 21:46+1200, Kai Huang: >>>> On Thu, May 5, 2016 at 6:57 AM, Radim Krčmář <rkrcmar@xxxxxxxxxx> wrote: >>>>> 2016-05-04 18:33+0000, Cao, Lei: >>>>>> On 5/4/2016 1:15 PM, Cao, Lei wrote: >>>>>>> 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? >>>>>> >>>>>> Never mind, lookup is needed to avoid duplicates. We can use >>>>>> list+bitmap, but >>>>>> it's obviously not as efficient as radix tree. >>>>> >>>>> Are duplicates a significant problem? >>>>> >>>>> (The dirtied page is marked as dirty, so we should have zero to very few >>>>> duplicates, depending on how dirtying and vm-exit on write to clean >>>>> page >>>>> cooperate. Duplicates don't introduce any bugs and we could also check >>>>> last few entries in the list to weed out most likely cases.) >>>> >>>> I don't think duplicated pages are significant problem. The point is we >>>> don't lose pages. >>>> >>>> I actually don't quite follow why there will be duplicated pages. Is it >>>> because lockless thing? >>> >>> Not really. The ugly bitmap to avoid duplicates in this series makes me >>> think that hardware does force an exit on multiple VCPUs if they >>> concurrently write to the same clear page. A list, or any per-vcpu >>> structure, will have multiple dirty entries if that happens. >>> >> >> We do see tons of duplicates. Majority are from kvm updating guest time, >> steal time, and setting/clearing PV EOI. >> >> Duplicates don't introduce bugs, but are undesirable, given a fixed-size >> dirty log. > > Absolutely. I didn't realize there were this many duplicates and no > method of filtering seems better than the bitmap. > Looking forward to performance comparison with a tree! > > Thanks. > A couple of issues with the tree. It doesn't work well if new entries are inserted after a scan. Rescan picks up everything, not just the new entries. We acquire and preprocess dirty pages before the guest is quiesced, and do a final pass after the guest is paused. It's difficult to divide the tree up so that multiple threads can work on it at the same time. It comes into play when resetting all the write traps after the guest is paused. A list can be divided up and multiple threads can work its part of the list. It's difficult to do that with a tree. -- To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
