All of lore.kernel.org
 help / color / mirror / Atom feed
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

  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: link
Be 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.