From patchwork Mon Dec 1 17:29:26 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Igor Mammedov X-Patchwork-Id: 5414541 Return-Path: X-Original-To: patchwork-kvm@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork1.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.19.201]) by patchwork1.web.kernel.org (Postfix) with ESMTP id 9FA0E9F319 for ; Mon, 1 Dec 2014 17:30:42 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id B31472026F for ; Mon, 1 Dec 2014 17:30:41 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id DF02620266 for ; Mon, 1 Dec 2014 17:30:40 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753486AbaLARaN (ORCPT ); Mon, 1 Dec 2014 12:30:13 -0500 Received: from mx1.redhat.com ([209.132.183.28]:33577 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754034AbaLAR3j (ORCPT ); Mon, 1 Dec 2014 12:29:39 -0500 Received: from int-mx11.intmail.prod.int.phx2.redhat.com (int-mx11.intmail.prod.int.phx2.redhat.com [10.5.11.24]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id sB1HTdMc022589 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=FAIL); Mon, 1 Dec 2014 12:29:39 -0500 Received: from dell-pet610-01.lab.eng.brq.redhat.com (dell-pet610-01.lab.eng.brq.redhat.com [10.34.42.20]) by int-mx11.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id sB1HTXB0025856; Mon, 1 Dec 2014 12:29:38 -0500 From: Igor Mammedov To: linux-kernel@vger.kernel.org Cc: pbonzini@redhat.com, kvm@vger.kernel.org Subject: [PATCH 4/5] kvm: change memslot sorting rule from size to GFN Date: Mon, 1 Dec 2014 17:29:26 +0000 Message-Id: <1417454967-4465-5-git-send-email-imammedo@redhat.com> In-Reply-To: <1417454967-4465-1-git-send-email-imammedo@redhat.com> References: <1417454967-4465-1-git-send-email-imammedo@redhat.com> X-Scanned-By: MIMEDefang 2.68 on 10.5.11.24 Sender: kvm-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: kvm@vger.kernel.org X-Spam-Status: No, score=-6.9 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_HI, T_RP_MATCHES_RCVD, UNPARSEABLE_RELAY autolearn=unavailable version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on mail.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP it will allow to use binary search for GFN -> memslot lookups, reducing lookup cost with large slots amount. Signed-off-by: Igor Mammedov --- virt/kvm/kvm_main.c | 17 +++++++++++------ 1 file changed, 11 insertions(+), 6 deletions(-) diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c index 278ed65..162817f 100644 --- a/virt/kvm/kvm_main.c +++ b/virt/kvm/kvm_main.c @@ -666,10 +666,10 @@ static int kvm_create_dirty_bitmap(struct kvm_memory_slot *memslot) } /* - * Insert memslot and re-sort memslots based on their size, - * so the larger slots will get better fit. Sorting algorithm - * takes advantage of having initially sorted array and - * known changed memslot position. + * Insert memslot and re-sort memslots based on their GFN, + * so binary search could be used to lookup GFN. + * Sorting algorithm takes advantage of having initially + * sorted array and known changed memslot position. */ static void update_memslots(struct kvm_memslots *slots, struct kvm_memory_slot *new) @@ -679,14 +679,19 @@ static void update_memslots(struct kvm_memslots *slots, struct kvm_memory_slot *mslots = slots->memslots; WARN_ON(mslots[i].id != id); + if (!new->npages) + new->base_gfn = 0; + while (i < KVM_MEM_SLOTS_NUM - 1 && - new->npages < mslots[i + 1].npages) { + new->base_gfn <= mslots[i + 1].base_gfn) { + if (!mslots[i + 1].npages) + break; mslots[i] = mslots[i + 1]; slots->id_to_index[mslots[i].id] = i; i++; } while (i > 0 && - new->npages > mslots[i - 1].npages) { + new->base_gfn > mslots[i - 1].base_gfn) { mslots[i] = mslots[i - 1]; slots->id_to_index[mslots[i].id] = i; i--;