"Maciej S. Szmigiero" <mail@xxxxxxxxxxxxxxxxxxxxx> writes: > On 03.02.2021 00:43, Sean Christopherson wrote: >> On Tue, Feb 02, 2021, Maciej S. Szmigiero wrote: >>> On 02.02.2021 02:33, Sean Christopherson wrote: ... >>> >>> I guess you mean to still turn id_to_index into a hash table, since >>> otherwise a VMM which uses just two memslots but numbered 0 and 508 >>> will have a 509-entry id_to_index array allocated. >> >> That should be irrelevant for the purposes of optimizing hva lookups, and mostly >> irrelevant for optimizing memslot updates. Using a hash table is almost a pure >> a memory optimization, it really only matters when the max number of memslots >> skyrockets, which is a separate discussion from optimizing hva lookups. > > While I agree this is a separate thing from scalable hva lookups it still > matters for the overall design. > > The current id_to_index array is fundamentally "pay the cost of max > number of memslots possible regardless how many you use". > > And it's not only that it takes more memory it also forces memslot > create / delete / move operations to be O(n) since the indices have to > be updated. FWIW, I don't see a fundamental disagreement between you and Sean here, it's just that we may want to eat this elephant one bite at a time instead of trying to swallow it unchewed :-) E.g. as a first step, we may want to introduce helper functions to not work with id_to_index directly and then suggest a better implementation (using rbtree, bynamically allocated array,...) for these helpers. This is definitely more work but it's likely worth it. > > By the way, I think nobody argues here for a bazillion of memslots. > It is is enough to simply remove the current cap and allow the maximum > number permitted by the existing KVM API, that is 32k as Vitaly's > patches recently did. Yea, there's no immegiate need even for 32k as KVM_MAX_VCPUS is '288', we can get away with e.g. 1000 but id_to_index is the only thing which may make us consider something lower than 32k: if only a few slots are used, there's no penalty (of course slot *modify* operations are O(n) so for 32k it'll take a lot but these configurations are currently illegal and evem 'slow' is better :-) -- Vitaly
