[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [PATCH v2 2/2] migration: savevm_state_handler_insert: constant-time
From: |
Laurent Vivier |
Subject: |
Re: [PATCH v2 2/2] migration: savevm_state_handler_insert: constant-time element insertion |
Date: |
Fri, 18 Oct 2019 10:34:47 +0200 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.1.1 |
On 18/10/2019 10:16, Dr. David Alan Gilbert wrote:
> * Scott Cheloha (address@hidden) wrote:
>> savevm_state's SaveStateEntry TAILQ is a priority queue. Priority
>> sorting is maintained by searching from head to tail for a suitable
>> insertion spot. Insertion is thus an O(n) operation.
>>
>> If we instead keep track of the head of each priority's subqueue
>> within that larger queue we can reduce this operation to O(1) time.
>>
>> savevm_state_handler_remove() becomes slightly more complex to
>> accomodate these gains: we need to replace the head of a priority's
>> subqueue when removing it.
>>
>> With O(1) insertion, booting VMs with many SaveStateEntry objects is
>> more plausible. For example, a ppc64 VM with maxmem=8T has 40000 such
>> objects to insert.
>
> Separate from reviewing this patch, I'd like to understand why you've
> got 40000 objects. This feels very very wrong and is likely to cause
> problems to random other bits of qemu as well.
I think the 40000 objects are the "dr-connectors" that are used to plug
peripherals (memory, pci card, cpus, ...).
https://github.com/qemu/qemu/blob/master/hw/ppc/spapr_drc.c
They are part of SPAPR specification.
https://raw.githubusercontent.com/qemu/qemu/master/docs/specs/ppc-spapr-hotplug.txt
CC Michael Roth
Thanks,
Laurent