From patchwork Mon Mar 6 11:34:28 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eric Auger X-Patchwork-Id: 9605831 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 E1156602B4 for ; Mon, 6 Mar 2017 11:42:49 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id BB319281C3 for ; Mon, 6 Mar 2017 11:42:49 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id AE9B328249; Mon, 6 Mar 2017 11:42:49 +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=-6.9 required=2.0 tests=BAYES_00,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 5E303281C3 for ; Mon, 6 Mar 2017 11:42:49 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754138AbdCFLms (ORCPT ); Mon, 6 Mar 2017 06:42:48 -0500 Received: from mx1.redhat.com ([209.132.183.28]:39140 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753237AbdCFLmo (ORCPT ); Mon, 6 Mar 2017 06:42:44 -0500 Received: from int-mx10.intmail.prod.int.phx2.redhat.com (int-mx10.intmail.prod.int.phx2.redhat.com [10.5.11.23]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id CF85F3B70C; Mon, 6 Mar 2017 11:35:35 +0000 (UTC) Received: from localhost.localdomain.com (ovpn-116-100.ams2.redhat.com [10.36.116.100]) by int-mx10.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id v26BYbnc002618; Mon, 6 Mar 2017 06:35:32 -0500 From: Eric Auger To: eric.auger.pro@gmail.com, eric.auger@redhat.com, marc.zyngier@arm.com, christoffer.dall@linaro.org, vijayak@caviumnetworks.com, Vijaya.Kumar@cavium.com, peter.maydell@linaro.org, linux-arm-kernel@lists.infradead.org, drjones@redhat.com, kvmarm@lists.cs.columbia.edu, kvm@vger.kernel.org Cc: andre.przywara@arm.com, Prasun.Kapoor@cavium.com, pbonzini@redhat.com, dgilbert@redhat.com, quintela@redhat.com Subject: [PATCH v3 13/19] KVM: arm64: ITS: Sort the device and ITE lists Date: Mon, 6 Mar 2017 12:34:28 +0100 Message-Id: <1488800074-21991-14-git-send-email-eric.auger@redhat.com> In-Reply-To: <1488800074-21991-1-git-send-email-eric.auger@redhat.com> References: <1488800074-21991-1-git-send-email-eric.auger@redhat.com> X-Scanned-By: MIMEDefang 2.68 on 10.5.11.23 X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.5.16 (mx1.redhat.com [10.5.110.30]); Mon, 06 Mar 2017 11:35:35 +0000 (UTC) Sender: kvm-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: kvm@vger.kernel.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 --- 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 9792110..1cd6ae6 100644 --- a/virt/kvm/arm/vgic/vgic-its.c +++ b/virt/kvm/arm/vgic/vgic-its.c @@ -734,6 +734,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); +} + static int vgic_its_alloc_ite(struct its_device *device, struct its_ite **itep, struct its_collection *collection, @@ -749,7 +764,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; } @@ -842,6 +857,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); +} + static int vgic_its_alloc_device(struct vgic_its *its, struct its_device **devp, u32 device_id, gpa_t itt_addr_field, @@ -858,7 +889,8 @@ static int vgic_its_alloc_device(struct vgic_its *its, device->nb_eventid_bits = size_field + 1; 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;