From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-16.8 required=3.0 tests=BAYES_00, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=unavailable autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 620BBC4320A for ; Fri, 13 Aug 2021 20:01:27 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 49DA961042 for ; Fri, 13 Aug 2021 20:01:27 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234331AbhHMUBx (ORCPT ); Fri, 13 Aug 2021 16:01:53 -0400 Received: from vps-vb.mhejs.net ([37.28.154.113]:50324 "EHLO vps-vb.mhejs.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234308AbhHMUBm (ORCPT ); Fri, 13 Aug 2021 16:01:42 -0400 Received: from MUA by vps-vb.mhejs.net with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1mEcwz-00047P-1v; Fri, 13 Aug 2021 21:34:41 +0200 From: "Maciej S. Szmigiero" To: Paolo Bonzini , Vitaly Kuznetsov Cc: Sean Christopherson , Wanpeng Li , Jim Mattson , Igor Mammedov , Marc Zyngier , James Morse , Julien Thierry , Suzuki K Poulose , Huacai Chen , Aleksandar Markovic , Paul Mackerras , Christian Borntraeger , Janosch Frank , David Hildenbrand , Cornelia Huck , Claudio Imbrenda , Joerg Roedel , kvm@vger.kernel.org, linux-kernel@vger.kernel.org Subject: [PATCH v4 13/13] KVM: Optimize overlapping memslots check Date: Fri, 13 Aug 2021 21:33:26 +0200 Message-Id: X-Mailer: git-send-email 2.32.0 In-Reply-To: References: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org From: "Maciej S. Szmigiero" Do a quick lookup for possibly overlapping gfns when creating or moving a memslot instead of performing a linear scan of the whole memslot set. Signed-off-by: Maciej S. Szmigiero --- virt/kvm/kvm_main.c | 36 +++++++++++++++++++++++++++--------- 1 file changed, 27 insertions(+), 9 deletions(-) diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c index 26aa3690b172..91304edb00e9 100644 --- a/virt/kvm/kvm_main.c +++ b/virt/kvm/kvm_main.c @@ -1679,6 +1679,30 @@ static int kvm_delete_memslot(struct kvm *kvm, return kvm_set_memslot(kvm, mem, old, &new, as_id, KVM_MR_DELETE); } +static bool kvm_check_memslot_overlap(struct kvm_memslots *slots, + struct kvm_memory_slot *nslot) +{ + int idx = slots->node_idx; + gfn_t nend = nslot->base_gfn + nslot->npages; + struct rb_node *node; + + kvm_for_each_memslot_in_gfn_range(node, slots, nslot->base_gfn, nend) { + struct kvm_memory_slot *cslot; + gfn_t cend; + + cslot = container_of(node, struct kvm_memory_slot, gfn_node[idx]); + cend = cslot->base_gfn + cslot->npages; + if (cslot->id == nslot->id) + continue; + + /* kvm_for_each_in_gfn_no_more() guarantees that cslot->base_gfn < nend */ + if (cend > nslot->base_gfn) + return true; + } + + return false; +} + /* * Allocate some memory and give it an address in the guest physical address * space. @@ -1764,16 +1788,10 @@ int __kvm_set_memory_region(struct kvm *kvm, } if ((change == KVM_MR_CREATE) || (change == KVM_MR_MOVE)) { - int bkt; - /* Check for overlaps */ - kvm_for_each_memslot(tmp, bkt, __kvm_memslots(kvm, as_id)) { - if (tmp->id == id) - continue; - if (!((new.base_gfn + new.npages <= tmp->base_gfn) || - (new.base_gfn >= tmp->base_gfn + tmp->npages))) - return -EEXIST; - } + if (kvm_check_memslot_overlap(__kvm_memslots(kvm, as_id), + &new)) + return -EEXIST; } /* Allocate/free page dirty bitmap as needed */