Re: [Qemu-devel] Memory use with >100 virtio devices

[Paolo Bonzini]

On 24/08/2017 14:30, David Gibson wrote:
>>
>> Ideas what to tweak or what valgrind tool to try?
> valgrind probably isn't that useful at this point.  I think we need to
> instrument bits of the code to find what the O(n^2) algo is and fix it.
> 
> Seems to me checking if the address_spaces list is growing to O(n^2)
> entries would be a good place to start.


The address spaces are O(n) (and so are the FlatView and the dispatch
tries), but each of them has O(n) size.

Eventually we use O(n^2) memory, but we build them O(n) times---which is
expensive and also means, due to RCU, that there can be a short amount
of time where it is between O(n^2) and O(n^3).

The scheme I suggested elsewhere in the thread should cut one "n", by
sharing one FlatViews and dispatch trie across all AddressSpaces.

Paolo