From: Eric Auger <eric.auger@redhat.com> 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 Cc: Prasun.Kapoor@cavium.com, quintela@redhat.com, dgilbert@redhat.com, pbonzini@redhat.com Subject: [PATCH v4 15/22] KVM: arm64: ITS: Sort the device and ITE lists Date: Mon, 27 Mar 2017 11:31:05 +0200 [thread overview] Message-ID: <1490607072-21610-16-git-send-email-eric.auger@redhat.com> (raw) In-Reply-To: <1490607072-21610-1-git-send-email-eric.auger@redhat.com> 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 <eric.auger@redhat.com> Reviewed-by: Andre Przywara <andre.przywara@arm.com> --- 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; -- 2.5.5
WARNING: multiple messages have this Message-ID (diff)
From: eric.auger@redhat.com (Eric Auger) To: linux-arm-kernel@lists.infradead.org Subject: [PATCH v4 15/22] KVM: arm64: ITS: Sort the device and ITE lists Date: Mon, 27 Mar 2017 11:31:05 +0200 [thread overview] Message-ID: <1490607072-21610-16-git-send-email-eric.auger@redhat.com> (raw) In-Reply-To: <1490607072-21610-1-git-send-email-eric.auger@redhat.com> 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 <eric.auger@redhat.com> Reviewed-by: Andre Przywara <andre.przywara@arm.com> --- 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; -- 2.5.5
next prev parent reply other threads:[~2017-03-27 9:31 UTC|newest] Thread overview: 144+ messages / expand[flat|nested] mbox.gz Atom feed top 2017-03-27 9:30 [PATCH v4 00/22] vITS save/restore Eric Auger 2017-03-27 9:30 ` Eric Auger 2017-03-27 9:30 ` [PATCH v4 01/22] KVM: arm/arm64: Add vITS save/restore API documentation Eric Auger 2017-03-27 9:30 ` Eric Auger 2017-04-08 10:03 ` Marc Zyngier 2017-04-08 10:03 ` Marc Zyngier 2017-04-08 13:15 ` Christoffer Dall 2017-04-08 13:15 ` Christoffer Dall 2017-04-08 17:31 ` Marc Zyngier 2017-04-08 17:31 ` Marc Zyngier 2017-04-10 10:18 ` Auger Eric 2017-04-10 10:18 ` Auger Eric 2017-04-10 10:42 ` Marc Zyngier 2017-04-10 10:42 ` Marc Zyngier 2017-04-08 18:17 ` Christoffer Dall 2017-04-08 18:17 ` Christoffer Dall 2017-04-10 14:26 ` Auger Eric 2017-04-10 14:26 ` Auger Eric 2017-04-21 9:12 ` Christoffer Dall 2017-04-21 9:12 ` Christoffer Dall 2017-03-27 9:30 ` [PATCH v4 02/22] KVM: arm/arm64: rename itte into ite Eric Auger 2017-03-27 9:30 ` Eric Auger 2017-04-08 10:04 ` Marc Zyngier 2017-04-08 10:04 ` Marc Zyngier 2017-03-27 9:30 ` [PATCH v4 03/22] arm/arm64: vgic: turn vgic_find_mmio_region into public Eric Auger 2017-03-27 9:30 ` Eric Auger 2017-04-08 10:06 ` Marc Zyngier 2017-04-08 10:06 ` Marc Zyngier 2017-04-08 10:06 ` Marc Zyngier 2017-03-27 9:30 ` [PATCH v4 04/22] KVM: arm64: ITS: KVM_DEV_ARM_VGIC_GRP_ITS_REGS group Eric Auger 2017-03-27 9:30 ` Eric Auger 2017-04-08 10:07 ` Marc Zyngier 2017-04-08 10:07 ` Marc Zyngier 2017-03-27 9:30 ` [PATCH v4 05/22] KVM: arm/arm64: vgic: expose (un)lock_all_vcpus Eric Auger 2017-03-27 9:30 ` Eric Auger 2017-04-08 10:09 ` Marc Zyngier 2017-04-08 10:09 ` Marc Zyngier 2017-03-27 9:30 ` [PATCH v4 06/22] KVM: arm64: ITS: Implement vgic_its_has_attr_regs and attr_regs_access Eric Auger 2017-03-27 9:30 ` Eric Auger 2017-04-08 10:24 ` Marc Zyngier 2017-04-08 10:24 ` Marc Zyngier 2017-04-08 10:24 ` Marc Zyngier 2017-03-27 9:30 ` [PATCH v4 07/22] KVM: arm64: ITS: Implement vgic_mmio_uaccess_write_its_creadr Eric Auger 2017-03-27 9:30 ` Eric Auger 2017-04-08 10:36 ` Marc Zyngier 2017-04-08 10:36 ` Marc Zyngier 2017-04-08 10:36 ` Marc Zyngier 2017-03-27 9:30 ` [PATCH v4 08/22] KVM: arm64: ITS: Implement vgic_mmio_uaccess_write_its_iidr Eric Auger 2017-03-27 9:30 ` Eric Auger 2017-04-08 10:42 ` Marc Zyngier 2017-04-08 10:42 ` Marc Zyngier 2017-04-08 10:42 ` Marc Zyngier 2017-04-10 14:32 ` Auger Eric 2017-04-10 14:32 ` Auger Eric 2017-04-10 14:57 ` Marc Zyngier 2017-04-10 14:57 ` Marc Zyngier 2017-04-10 15:07 ` Peter Maydell 2017-04-10 15:07 ` Peter Maydell 2017-04-10 15:17 ` Auger Eric 2017-04-10 15:17 ` Auger Eric 2017-04-11 10:05 ` Marc Zyngier 2017-04-11 10:05 ` Marc Zyngier 2017-04-11 10:08 ` Auger Eric 2017-04-11 10:08 ` Auger Eric 2017-04-11 10:16 ` Peter Maydell 2017-04-11 10:16 ` Peter Maydell 2017-04-11 10:29 ` Marc Zyngier 2017-04-11 10:29 ` Marc Zyngier 2017-04-11 10:43 ` Peter Maydell 2017-04-11 10:43 ` Peter Maydell 2017-04-11 10:56 ` Auger Eric 2017-04-11 10:56 ` Auger Eric 2017-03-27 9:30 ` [PATCH v4 09/22] KVM: arm64: ITS: Report the ITE size in GITS_TYPER Eric Auger 2017-03-27 9:30 ` Eric Auger 2017-04-08 17:42 ` Marc Zyngier 2017-04-08 17:42 ` Marc Zyngier 2017-03-27 9:31 ` [PATCH v4 10/22] KVM: arm64: ITS: Interpret MAPD Size field and check related errors Eric Auger 2017-03-27 9:31 ` Eric Auger 2017-04-08 17:59 ` Marc Zyngier 2017-04-08 17:59 ` Marc Zyngier 2017-04-08 17:59 ` Marc Zyngier 2017-03-27 9:31 ` [PATCH v4 11/22] KVM: arm64: ITS: Interpret MAPD ITT_addr field Eric Auger 2017-03-27 9:31 ` Eric Auger 2017-04-08 18:58 ` Marc Zyngier 2017-04-08 18:58 ` Marc Zyngier 2017-04-08 18:58 ` Marc Zyngier 2017-03-27 9:31 ` [PATCH v4 12/22] KVM: arm64: ITS: Check the device id matches TYPER DEVBITS range Eric Auger 2017-03-27 9:31 ` Eric Auger 2017-03-27 9:31 ` [PATCH v4 13/22] KVM: arm64: ITS: KVM_DEV_ARM_VGIC_GRP_ITS_TABLES group Eric Auger 2017-03-27 9:31 ` Eric Auger 2017-03-27 15:04 ` kbuild test robot 2017-03-27 15:04 ` kbuild test robot 2017-03-27 18:29 ` Auger Eric 2017-03-27 18:29 ` Auger Eric 2017-03-30 2:21 ` [kbuild-all] " Ye Xiaolong 2017-03-30 2:21 ` Ye Xiaolong 2017-03-30 6:46 ` Auger Eric 2017-03-30 6:46 ` Auger Eric 2017-03-30 7:29 ` Ye Xiaolong 2017-03-30 7:29 ` Ye Xiaolong 2017-03-30 8:29 ` Auger Eric 2017-03-30 8:29 ` Auger Eric 2017-04-09 10:09 ` Marc Zyngier 2017-04-09 10:09 ` Marc Zyngier 2017-03-27 9:31 ` [PATCH v4 14/22] KVM: arm64: ITS: vgic_its_alloc_ite/device Eric Auger 2017-03-27 9:31 ` Eric Auger 2017-04-09 10:13 ` Marc Zyngier 2017-04-09 10:13 ` Marc Zyngier 2017-03-27 9:31 ` Eric Auger [this message] 2017-03-27 9:31 ` [PATCH v4 15/22] KVM: arm64: ITS: Sort the device and ITE lists Eric Auger 2017-04-09 10:18 ` Marc Zyngier 2017-04-09 10:18 ` Marc Zyngier 2017-03-27 9:31 ` [PATCH v4 16/22] KVM: expose next_segment() Eric Auger 2017-03-27 9:31 ` Eric Auger 2017-03-27 9:31 ` [PATCH v4 17/22] KVM: arm64: ITS: Add infrastructure for table lookup Eric Auger 2017-03-27 9:31 ` Eric Auger 2017-04-09 10:36 ` Marc Zyngier 2017-04-09 10:36 ` Marc Zyngier 2017-03-27 9:31 ` [PATCH v4 18/22] KVM: arm64: ITS: Collection table save/restore Eric Auger 2017-03-27 9:31 ` Eric Auger 2017-04-10 9:55 ` Marc Zyngier 2017-04-10 9:55 ` Marc Zyngier 2017-04-11 9:57 ` Auger Eric 2017-04-11 9:57 ` Auger Eric 2017-04-11 10:03 ` Marc Zyngier 2017-04-11 10:03 ` Marc Zyngier 2017-03-27 9:31 ` [PATCH v4 19/22] KVM: arm64: ITS: vgic_its_check_id returns the entry's GPA Eric Auger 2017-03-27 9:31 ` Eric Auger 2017-03-27 9:31 ` [PATCH v4 20/22] KVM: arm64: ITS: ITT flush and restore Eric Auger 2017-03-27 9:31 ` Eric Auger 2017-04-10 12:39 ` Marc Zyngier 2017-04-10 12:39 ` Marc Zyngier 2017-04-11 10:19 ` Auger Eric 2017-04-11 10:19 ` Auger Eric 2017-03-27 9:31 ` [PATCH v4 21/22] KVM: arm64: ITS: Device table save/restore Eric Auger 2017-03-27 9:31 ` Eric Auger 2017-04-10 12:42 ` Marc Zyngier 2017-04-10 12:42 ` Marc Zyngier 2017-03-27 9:31 ` [PATCH v4 22/22] KVM: arm64: ITS: Pending " Eric Auger 2017-03-27 9:31 ` Eric Auger 2017-04-10 12:50 ` Marc Zyngier 2017-04-10 12:50 ` Marc Zyngier 2017-04-10 12:54 ` [PATCH v4 00/22] vITS save/restore Marc Zyngier 2017-04-10 12:54 ` Marc Zyngier
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=1490607072-21610-16-git-send-email-eric.auger@redhat.com \ --to=eric.auger@redhat.com \ --cc=Prasun.Kapoor@cavium.com \ --cc=Vijaya.Kumar@cavium.com \ --cc=andre.przywara@arm.com \ --cc=christoffer.dall@linaro.org \ --cc=dgilbert@redhat.com \ --cc=eric.auger.pro@gmail.com \ --cc=kvm@vger.kernel.org \ --cc=kvmarm@lists.cs.columbia.edu \ --cc=linux-arm-kernel@lists.infradead.org \ --cc=marc.zyngier@arm.com \ --cc=pbonzini@redhat.com \ --cc=peter.maydell@linaro.org \ --cc=quintela@redhat.com \ --cc=vijayak@caviumnetworks.com \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.