From mboxrd@z Thu Jan  1 00:00:00 1970
From: Vitaly Kuznetsov <vkuznets@redhat.com>
Subject: Re: [PATCH v4 RESEND 3/5] KVM: x86: hyperv: use get_vcpu_by_vpidx() in kvm_hv_flush_tlb()
Date: Mon, 17 Sep 2018 10:32:55 +0200
Message-ID: <87r2hs7cco.fsf@vitty.brq.redhat.com>
References: <20180822101832.31763-1-vkuznets@redhat.com>
        <20180822101832.31763-4-vkuznets@redhat.com>
        <8da03d2a-5405-f363-f081-e4bc46b106e3@redhat.com>
Mime-Version: 1.0
Content-Type: text/plain
Cc: kvm@vger.kernel.org,
        Radim =?utf-8?B?S3LEjW3DocWZ?= <rkrcmar@redhat.com>,
        Roman Kagan <rkagan@virtuozzo.com>,
        "K. Y. Srinivasan" <kys@microsoft.com>,
        Haiyang Zhang <haiyangz@microsoft.com>,
        Stephen Hemminger <sthemmin@microsoft.com>,
        "Michael Kelley \(EOSG\)" <Michael.H.Kelley@microsoft.com>,
        Wanpeng Li <wanpeng.li@hotmail.com>,
        linux-kernel@vger.kernel.org
To: Paolo Bonzini <pbonzini@redhat.com>
Return-path: <linux-kernel-owner@vger.kernel.org>
In-Reply-To: <8da03d2a-5405-f363-f081-e4bc46b106e3@redhat.com> (Paolo
        Bonzini's message of "Fri, 14 Sep 2018 19:33:34 +0200")
Sender: linux-kernel-owner@vger.kernel.org
List-Id: kvm.vger.kernel.org

Paolo Bonzini <pbonzini@redhat.com> writes:

> On 22/08/2018 12:18, Vitaly Kuznetsov wrote:
>> VP_INDEX almost always matches VCPU id and get_vcpu_by_vpidx() is fast,
>> use it instead of traversing full vCPU list every time.
>
> ... but if it doesn't, the algorithm is now quadratic, isn't i?

Yes,

I even had an implementation with a logarythmic search back in v2 but
we had a discussion with Roman and he convinced me this is an overkill
and not currently required. It seems that with Qemu this is true indeed,
vp_index always matches vcpu is but in case some other userspace decides
to break this unwritten rule users may experience significant slowdown.

-- 
  Vitaly