[PATCH v3 13/19] KVM: arm64: ITS: Sort the device and ITE lists

[Eric Auger]

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 at redhat.com>
---
 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;
-- 
2.5.5