From patchwork Thu Nov 4 00:25:29 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sean Christopherson X-Patchwork-Id: 12602257 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id A2C50C433EF for ; Thu, 4 Nov 2021 00:57:59 +0000 (UTC) Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 6A5E961053 for ; Thu, 4 Nov 2021 00:57:59 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.4.1 mail.kernel.org 6A5E961053 Authentication-Results: mail.kernel.org; dmarc=fail (p=reject dis=none) header.from=google.com Authentication-Results: mail.kernel.org; spf=none smtp.mailfrom=lists.infradead.org DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender: Content-Transfer-Encoding:Content-Type:Reply-To:List-Subscribe:List-Help: List-Post:List-Archive:List-Unsubscribe:List-Id:Cc:To:From:Subject:References :Mime-Version:Message-Id:In-Reply-To:Date:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: List-Owner; bh=YpyQZAGUW9Kc0ZbxnFtjtuco8UqT0DblhU/ZOBimEqg=; b=ukDSTm3PBCqtoX KkVv8GgUTG6oyah8ikJ7FF9iPSvjXLYspxjFpNTBYF5ENkhnbRqRDc2hp1pBHLTeM0VQ5itzFfjU+ bI3jpYGnK2hLwyWaskA4dx5+8wJirfJBWJYX/4HE/xSb7J85A6UIay9ybtok5LtfwZa1ojisamYMs GRLgZYt8oGc5i4ftXS4fax2L6aKyuII2z0opD3pS/ToxB3JnmULt/3UIdB2ToOkMwjQD6GOipHX+G UUo5ZeA5xEwHOXukKIHRnrJW60oQhwTi3ozyQH3vUC0O2FRoqvPmACQZlFxA141Oz5mzf5io9oFPv rsBRlOWqPC4OgmFQoDJw==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.94.2 #2 (Red Hat Linux)) id 1miR2T-007OXd-80; Thu, 04 Nov 2021 00:55:34 +0000 Received: from mail-pf1-x44a.google.com ([2607:f8b0:4864:20::44a]) by bombadil.infradead.org with esmtps (Exim 4.94.2 #2 (Red Hat Linux)) id 1miQae-007D2W-K3 for linux-arm-kernel@lists.infradead.org; Thu, 04 Nov 2021 00:26:53 +0000 Received: by mail-pf1-x44a.google.com with SMTP id b206-20020a621bd7000000b0049461e3b557so169111pfb.13 for ; Wed, 03 Nov 2021 17:26:47 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20210112; h=reply-to:date:in-reply-to:message-id:mime-version:references :subject:from:to:cc; bh=eDJLgTwa4Mq+pfIoYabE+ramu2f6Q5nSW9TL6LbQQsI=; b=AwZyd1OGNd2jGC9KPlXvy0oV+JkIiHs9n78p1LAJEXYu3abpzCJ4C2qjD9WEdimC8h /U06PEKK8296gAr9y+mGJ7YU/AYB7mMLshQmjbfJT2JjYIs1QGfBkPinN0rTDsM0mJ8v y1VXf6q7OT9SnMxtkJVPvG6qnljmv27pg/hk28jYo+otmvhiKA+XTi2uKknvqQboocCi bNfT4/DvRM5KrXSU8LLRMexndgtLytkukMKS+6YJqn2ZlSHrKvNjmLuH6tB44y+OnCgy GssafhzFt1xigLvtK4LdQ29M/UL2+eLN8sYzUERpdj2aCM8q7wJx2XZ+IzRmu3TIf4VS eNLw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:reply-to:date:in-reply-to:message-id :mime-version:references:subject:from:to:cc; bh=eDJLgTwa4Mq+pfIoYabE+ramu2f6Q5nSW9TL6LbQQsI=; b=39PbZ0idvuwvudPvczROdfN/WQOdJcXOMastcbMlfFkKkqFKIDHC/jskIjV9sdE/06 PQdY0ueDTUMrTAshoQ4eUam+vNJQjYb7u3/iJXhH7AVBYMjXhlvfEMTIO+c2P3Vtwyz4 UT8PB7GcBASpFBoyZvY2VroHDGzXAEuiADjT51Llcaz7UknqaWuoqQ5fYJ2GLzYiQqmb 0aSAIhcHptOJMECqQ2Ovsd3P1vJiyY0iiquU1fKyo0Oe5BUn/5XGN1mZETb/BmH5w40+ u9ZiMuuH/Yf8iNFxUy7CX8ZewvKWUKDht2tscdJmpbQz+HS/mm7j6gWFrcBNnXARNG26 cvPw== X-Gm-Message-State: AOAM531JjIC4jdZBIY7uCitth438Go7BrTFBFoYBe9TWTPd0n8N4JknY xeHPgKdLTy7yMzPk+t++iNhMykTZmFA= X-Google-Smtp-Source: ABdhPJyj4rUoqs2915nhSyoqX9YGWRaiikX568lnB/vn8bpIGUoxqu2M9ISziOOEMnXgiMyENpFmkaA/Mco= X-Received: from seanjc.c.googlers.com ([fda3:e722:ac3:cc00:7f:e700:c0a8:3e5]) (user=seanjc job=sendgmr) by 2002:a17:902:ab50:b0:13f:4c70:9322 with SMTP id ij16-20020a170902ab5000b0013f4c709322mr41332797plb.89.1635985607093; Wed, 03 Nov 2021 17:26:47 -0700 (PDT) Date: Thu, 4 Nov 2021 00:25:29 +0000 In-Reply-To: <20211104002531.1176691-1-seanjc@google.com> Message-Id: <20211104002531.1176691-29-seanjc@google.com> Mime-Version: 1.0 References: <20211104002531.1176691-1-seanjc@google.com> X-Mailer: git-send-email 2.33.1.1089.g2158813163f-goog Subject: [PATCH v5.5 28/30] KVM: Optimize overlapping memslots check From: Sean Christopherson To: Marc Zyngier , Huacai Chen , Aleksandar Markovic , Paul Mackerras , Anup Patel , Paul Walmsley , Palmer Dabbelt , Albert Ou , Christian Borntraeger , Janosch Frank , Paolo Bonzini Cc: James Morse , Alexandru Elisei , Suzuki K Poulose , Atish Patra , David Hildenbrand , Cornelia Huck , Claudio Imbrenda , Sean Christopherson , Vitaly Kuznetsov , Wanpeng Li , Jim Mattson , Joerg Roedel , linux-arm-kernel@lists.infradead.org, kvmarm@lists.cs.columbia.edu, linux-mips@vger.kernel.org, kvm@vger.kernel.org, kvm-ppc@vger.kernel.org, kvm-riscv@lists.infradead.org, linux-riscv@lists.infradead.org, linux-kernel@vger.kernel.org, Ben Gardon , "Maciej S . Szmigiero" X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20211103_172648_714245_C21D926C X-CRM114-Status: GOOD ( 14.98 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: Sean Christopherson Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.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 [sean: tweaked params to avoid churn in future cleanup] Signed-off-by: Sean Christopherson --- virt/kvm/kvm_main.c | 46 +++++++++++++++++++++++++++++++-------------- 1 file changed, 32 insertions(+), 14 deletions(-) diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c index d095e01838bf..d22e40225703 100644 --- a/virt/kvm/kvm_main.c +++ b/virt/kvm/kvm_main.c @@ -1800,6 +1800,29 @@ static int kvm_set_memslot(struct kvm *kvm, return 0; } +static bool kvm_check_memslot_overlap(struct kvm_memslots *slots, int id, + gfn_t start, gfn_t end) +{ + int idx = slots->node_idx; + struct rb_node *node; + + kvm_for_each_memslot_in_gfn_range(node, slots, start, end) { + 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 == id) + continue; + + /* kvm_for_each_in_gfn_no_more() guarantees that cslot->base_gfn < nend */ + if (cend > start) + return true; + } + + return false; +} + /* * Allocate some memory and give it an address in the guest physical address * space. @@ -1811,8 +1834,9 @@ static int kvm_set_memslot(struct kvm *kvm, int __kvm_set_memory_region(struct kvm *kvm, const struct kvm_userspace_memory_region *mem) { - struct kvm_memory_slot *old, *tmp; + struct kvm_memory_slot *old; struct kvm_memory_slot new; + struct kvm_memslots *slots; enum kvm_mr_change change; int as_id, id; int r; @@ -1841,11 +1865,13 @@ int __kvm_set_memory_region(struct kvm *kvm, if (mem->guest_phys_addr + mem->memory_size < mem->guest_phys_addr) return -EINVAL; + slots = __kvm_memslots(kvm, as_id); + /* * Note, the old memslot (and the pointer itself!) may be invalidated * and/or destroyed by kvm_set_memslot(). */ - old = id_to_memslot(__kvm_memslots(kvm, as_id), id); + old = id_to_memslot(slots, id); if (!mem->memory_size) { if (!old || !old->npages) @@ -1894,18 +1920,10 @@ int __kvm_set_memory_region(struct kvm *kvm, return 0; } - 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 ((change == KVM_MR_CREATE || change == KVM_MR_MOVE) && + kvm_check_memslot_overlap(slots, id, new.base_gfn, + new.base_gfn + new.npages)) + return -EEXIST; return kvm_set_memslot(kvm, old, &new, change); }