From mboxrd@z Thu Jan 1 00:00:00 1970 From: Marc Zyngier Subject: Re: [PATCH v4 15/22] KVM: arm64: ITS: Sort the device and ITE lists Date: Sun, 09 Apr 2017 11:18:52 +0100 Message-ID: <868tn9c29f.fsf@arm.com> References: <1490607072-21610-1-git-send-email-eric.auger@redhat.com> <1490607072-21610-16-git-send-email-eric.auger@redhat.com> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Return-path: Received: from localhost (localhost [127.0.0.1]) by mm01.cs.columbia.edu (Postfix) with ESMTP id 5A5A740C54 for ; Sun, 9 Apr 2017 06:17:02 -0400 (EDT) Received: from mm01.cs.columbia.edu ([127.0.0.1]) by localhost (mm01.cs.columbia.edu [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 3E1PtJNrfIlK for ; Sun, 9 Apr 2017 06:17:01 -0400 (EDT) Received: from foss.arm.com (foss.arm.com [217.140.101.70]) by mm01.cs.columbia.edu (Postfix) with ESMTP id 179BE40C50 for ; Sun, 9 Apr 2017 06:17:00 -0400 (EDT) In-Reply-To: <1490607072-21610-16-git-send-email-eric.auger@redhat.com> (Eric Auger's message of "Mon, 27 Mar 2017 11:31:05 +0200") List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: kvmarm-bounces@lists.cs.columbia.edu Sender: kvmarm-bounces@lists.cs.columbia.edu To: Eric Auger Cc: kvm@vger.kernel.org, Prasun.Kapoor@cavium.com, vijayak@caviumnetworks.com, andre.przywara@arm.com, quintela@redhat.com, dgilbert@redhat.com, Vijaya.Kumar@cavium.com, linux-arm-kernel@lists.infradead.org, pbonzini@redhat.com, kvmarm@lists.cs.columbia.edu, eric.auger.pro@gmail.com List-Id: kvmarm@lists.cs.columbia.edu On Mon, Mar 27 2017 at 10:31:05 AM, Eric Auger wrote: > 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; What is the actual gain for sorting the list at runtime, vs sorting it at save time? A save/restore operation is a very rare event compared to the normal use of the ITS, so I'd rather put the overhead on the rarest event if possible. Thanks, M. -- Jazz is not dead. It just smells funny.