Hi Eric,
On 06/03/17 11:34, 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 <eric.auger@xxxxxxxxxx>
Looks correct to me.
Reviewed-by: Andre Przywara <andre.przywara@xxxxxxx>
> ---
> 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;
>
