Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
From:   Vitaly Kuznetsov <vkuznets@redhat.com>
To:     "Maciej S. Szmigiero" <mail@maciej.szmigiero.name>,
        Sean Christopherson <seanjc@google.com>
Cc:     Paolo Bonzini <pbonzini@redhat.com>,
        Wanpeng Li <wanpengli@tencent.com>,
        Jim Mattson <jmattson@google.com>,
        Igor Mammedov <imammedo@redhat.com>,
        Marc Zyngier <maz@kernel.org>,
        James Morse <james.morse@arm.com>,
        Julien Thierry <julien.thierry.kdev@gmail.com>,
        Suzuki K Poulose <suzuki.poulose@arm.com>,
        Huacai Chen <chenhuacai@kernel.org>,
        Aleksandar Markovic <aleksandar.qemu.devel@gmail.com>,
        Paul Mackerras <paulus@ozlabs.org>,
        Christian Borntraeger <borntraeger@de.ibm.com>,
        Janosch Frank <frankja@linux.ibm.com>,
        David Hildenbrand <david@redhat.com>,
        Cornelia Huck <cohuck@redhat.com>,
        Claudio Imbrenda <imbrenda@linux.ibm.com>,
        Joerg Roedel <joro@8bytes.org>, kvm@vger.kernel.org,
        linux-kernel@vger.kernel.org
Subject: Re: [PATCH 2/2] KVM: Scalable memslots implementation
In-Reply-To: <dd76955e-710a-61b0-9739-28623f985508@maciej.szmigiero.name>
References: <ceb96527b6f7bb662eec813f05b897a551ebd0b2.1612140117.git.maciej.szmigiero@oracle.com>
 <4d748e0fd50bac68ece6952129aed319502b6853.1612140117.git.maciej.szmigiero@oracle.com>
 <YBisBkSYPoaOM42F@google.com>
 <9e6ca093-35c3-7cca-443b-9f635df4891d@maciej.szmigiero.name>
 <YBnjso2OeX1/r3Ls@google.com>
 <dd76955e-710a-61b0-9739-28623f985508@maciej.szmigiero.name>
Date:   Wed, 03 Feb 2021 15:21:38 +0100
Message-ID: <875z39p6z1.fsf@vitty.brq.redhat.com>
MIME-Version: 1.0
Content-Type: text/plain
Precedence: bulk

"Maciej S. Szmigiero" <mail@maciej.szmigiero.name> 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