From patchwork Mon Mar 27 09:31:05 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eric Auger X-Patchwork-Id: 9646159 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 285A3602BF for ; Mon, 27 Mar 2017 10:00:23 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 0033F28364 for ; Mon, 27 Mar 2017 10:00:23 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id E8FE5283A6; Mon, 27 Mar 2017 10:00:22 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-1.9 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID autolearn=unavailable version=3.3.1 Received: from bombadil.infradead.org (bombadil.infradead.org [65.50.211.133]) (using TLSv1.2 with cipher AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.wl.linuxfoundation.org (Postfix) with ESMTPS id 6A6AF28375 for ; Mon, 27 Mar 2017 10:00:22 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20170209; h=Sender: Content-Transfer-Encoding:Content-Type:MIME-Version:Cc:List-Subscribe: List-Help:List-Post:List-Archive:List-Unsubscribe:List-Id:References: In-Reply-To:Message-Id:Date:Subject:To:From:Reply-To:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Owner; bh=LhV6/UfSmBZjdwfynDDY5qYrt+tqrUN9epsRCuSJq3Q=; b=Re40XMy0Zqd98cGzDx63HFxqVK 7sVBYXivCyEmLZQ2egHRFW5N+oX/nGSGXucxhD80KUIsM0vPnTAiAiEjql53qnVQD01cxqc8tkAUP YSGvjIU2LttBa8DDqKoLHCBYbbaXQA7fZpLFkhl8JrR1dFGm8cL/3EDtURBA2f2yNJCxSL9XkrmuW I4bITkAZt4Umgu9rIGwy6Fe8o6maZ7b4kzYcDygSBWvkxZiK1lIQvQ1t3HJuIfK3N0/5fIuFf6Xlf 6UyfFICIePBHDC3Aw/AeiXL5i4eemc58lKZkktta/Oj3M2Lzk5SDfii72BGW/+llrGgekIQIP9sbr lrTSB4xQ==; Received: from localhost ([127.0.0.1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.87 #1 (Red Hat Linux)) id 1csRRk-0007Tf-V7; Mon, 27 Mar 2017 10:00:20 +0000 Received: from casper.infradead.org ([85.118.1.10]) by bombadil.infradead.org with esmtps (Exim 4.87 #1 (Red Hat Linux)) id 1csRIi-0005J6-Lg for linux-arm-kernel@bombadil.infradead.org; Mon, 27 Mar 2017 09:51:00 +0000 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=casper.20170209; h=References:In-Reply-To:Message-Id:Date: Subject:Cc:To:From:Sender:Reply-To:MIME-Version:Content-Type: Content-Transfer-Encoding:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Id: List-Help:List-Unsubscribe:List-Subscribe:List-Post:List-Owner:List-Archive; bh=H1/0FXihJP93H6oN6ai2NTiSQ6B206pDgWTLKakTbQE=; b=XERvAnQmbKbR0F1rNT1dtfL9m jfG/W3LU76YM19gMHOIOq1Tb42BkxE8lv5evnJXydY4d4FnrfOtcsFaoqUA72EiJ0YW69Rsb+aJ75 h2lv0f/EbXMtjVLvNB9oSSnKD4q3xh5puwRwNJ9fkJC3DLSrOCTxNmqbFg96oFFc1myoKfQsfR684 NOxj9MTbu69liMQu52pPWyttiRXfKV3ShnYmjrDtQk7b/dme0ApsPK7cucxq+v2R3k0Vh79O3mBqZ Q0VguljfRNEaBhesRmiV/U5fijGO99ECF8dzTq1j72BYpwvuTYtvDuDBRjFGVtmzxTkBh7QJeQJHn E0HvnrOEg==; Received: from mx1.redhat.com ([209.132.183.28]) by casper.infradead.org with esmtps (Exim 4.87 #1 (Red Hat Linux)) id 1csR1D-0002yd-PQ for linux-arm-kernel@lists.infradead.org; Mon, 27 Mar 2017 09:32:58 +0000 Received: from smtp.corp.redhat.com (int-mx05.intmail.prod.int.phx2.redhat.com [10.5.11.15]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 1D8F7C04B938; Mon, 27 Mar 2017 09:32:36 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mx1.redhat.com 1D8F7C04B938 Authentication-Results: ext-mx07.extmail.prod.ext.phx2.redhat.com; dmarc=none (p=none dis=none) header.from=redhat.com Authentication-Results: ext-mx07.extmail.prod.ext.phx2.redhat.com; spf=pass smtp.mailfrom=eric.auger@redhat.com DKIM-Filter: OpenDKIM Filter v2.11.0 mx1.redhat.com 1D8F7C04B938 Received: from localhost.localdomain.com (ovpn-117-27.ams2.redhat.com [10.36.117.27]) by smtp.corp.redhat.com (Postfix) with ESMTP id AB0A317C46; Mon, 27 Mar 2017 09:32:28 +0000 (UTC) From: Eric Auger To: eric.auger.pro@gmail.com, eric.auger@redhat.com, marc.zyngier@arm.com, christoffer.dall@linaro.org, andre.przywara@arm.com, vijayak@caviumnetworks.com, Vijaya.Kumar@cavium.com, peter.maydell@linaro.org, linux-arm-kernel@lists.infradead.org, kvmarm@lists.cs.columbia.edu, kvm@vger.kernel.org Subject: [PATCH v4 15/22] KVM: arm64: ITS: Sort the device and ITE lists Date: Mon, 27 Mar 2017 11:31:05 +0200 Message-Id: <1490607072-21610-16-git-send-email-eric.auger@redhat.com> In-Reply-To: <1490607072-21610-1-git-send-email-eric.auger@redhat.com> References: <1490607072-21610-1-git-send-email-eric.auger@redhat.com> X-Scanned-By: MIMEDefang 2.79 on 10.5.11.15 X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.5.16 (mx1.redhat.com [10.5.110.31]); Mon, 27 Mar 2017 09:32:36 +0000 (UTC) X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20170327_103256_275796_638F5BB2 X-CRM114-Status: GOOD ( 14.62 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Prasun.Kapoor@cavium.com, drjones@redhat.com, quintela@redhat.com, dgilbert@redhat.com, pbonzini@redhat.com MIME-Version: 1.0 Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+patchwork-linux-arm=patchwork.kernel.org@lists.infradead.org X-Virus-Scanned: ClamAV using ClamSMTP Natively sort the device and ITE lists in ascending deviceId/eventid order. This paves the way to optimized DTE and ITE scan in guest RAM table where entries are chained together using a next ID offset. Signed-off-by: Eric Auger Reviewed-by: Andre Przywara --- v3 -> v4: - added Andre's R-b --- virt/kvm/arm/vgic/vgic-its.c | 36 ++++++++++++++++++++++++++++++++++-- 1 file changed, 34 insertions(+), 2 deletions(-) diff --git a/virt/kvm/arm/vgic/vgic-its.c b/virt/kvm/arm/vgic/vgic-its.c index 2a1ccbf..7364b7d 100644 --- a/virt/kvm/arm/vgic/vgic-its.c +++ b/virt/kvm/arm/vgic/vgic-its.c @@ -726,6 +726,21 @@ static void vgic_its_free_collection(struct vgic_its *its, u32 coll_id) kfree(collection); } +static void ite_list_insert_sorted(struct list_head *h, struct its_ite *ite) +{ + struct list_head *pos = h->next; + u32 id = ite->event_id; + + while (pos != h) { + struct its_ite *iter = + list_entry(pos, struct its_ite, ite_list); + if (id < iter->event_id) + break; + pos = pos->next; + } + list_add_tail(&ite->ite_list, pos); +} + /* Must be called with its_lock mutex held */ static int vgic_its_alloc_ite(struct its_device *device, struct its_ite **itep, @@ -742,7 +757,7 @@ static int vgic_its_alloc_ite(struct its_device *device, ite->collection = collection; ite->lpi = lpi_id; - list_add_tail(&ite->ite_list, &device->itt_head); + ite_list_insert_sorted(&device->itt_head, ite); *itep = ite; return 0; } @@ -835,6 +850,22 @@ static void vgic_its_unmap_device(struct kvm *kvm, struct its_device *device) kfree(device); } +static void device_list_insert_sorted(struct list_head *h, + struct its_device *dev) +{ + struct list_head *pos = h->next; + u32 id = dev->device_id; + + while (pos != h) { + struct its_device *iter = + list_entry(pos, struct its_device, dev_list); + if (id < iter->device_id) + break; + pos = pos->next; + } + list_add_tail(&dev->dev_list, pos); +} + /* Must be called with its_lock mutex held */ static int vgic_its_alloc_device(struct vgic_its *its, struct its_device **devp, @@ -852,7 +883,8 @@ static int vgic_its_alloc_device(struct vgic_its *its, device->nb_eventid_bits = nb_eventid_bits; INIT_LIST_HEAD(&device->itt_head); - list_add_tail(&device->dev_list, &its->device_list); + device_list_insert_sorted(&its->device_list, device); + *devp = device; return 0;