----- Original Message -----
> From: "Wanpeng Li" <kernellwp@xxxxxxxxx>
> To: "Gal Hammer" <ghammer@xxxxxxxxxx>
> Cc: "kvm" <kvm@xxxxxxxxxxxxxxx>, "Radim Krcmar" <rkrcmar@xxxxxxxxxx>, "Paolo Bonzini" <pbonzini@xxxxxxxxxx>
> Sent: Thursday, January 25, 2018 8:48:14 AM
> Subject: Re: [PATCH] kvm: use insert sort in kvm_io_bus_register_dev function
>
> 2018-01-16 21:34 GMT+08:00 Gal Hammer <ghammer@xxxxxxxxxx>:
> > The loading time of a VM is quite significant with a CPU usage
> > reaching 100% when loading a VM that its virtio devices use a
> > large amount of virt-queues (e.g. a virtio-serial device with
> > max_ports=511). Most of the time is spend in re-sorting the
> > kvm_io_bus kvm_io_range array when a new eventfd is registered.
> >
> > The patch replaces the existing method with an insert sort.
>
> If we should stop to use bsearch when searching io bus later?
There is an important difference between the two cases. In Gal's
case, sort() is always O(n log n) and so you get O(n^2 log n) vs
O(n^2) for insertion sort. Also, heap sort is pretty expensive,
so there is a lot of overhead even before you take into account
indirect calls.
For bsearch(), switching to an open-coded binary search would keep
the same complexity O(log n), only saving the indirect calls. It
may save a few clock cycles, but it's probably even more effective
to keep a simple one-element cache for the most recently used item,
and then fall back to bsearch().
Paolo
>
> Regards,
> Wanpeng Li
>
> >
> > Reviewed-by: Marcel Apfelbaum <marcel@xxxxxxxxxx>
> > Reviewed-by: Uri Lublin <ulublin@xxxxxxxxxx>
> > Signed-off-by: Gal Hammer <ghammer@xxxxxxxxxx>
> > ---
> > virt/kvm/kvm_main.c | 36 ++++++++++++++++++------------------
> > 1 file changed, 18 insertions(+), 18 deletions(-)
> >
> > diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c
> > index 210bf82..1e467fc 100644
> > --- a/virt/kvm/kvm_main.c
> > +++ b/virt/kvm/kvm_main.c
> > @@ -3419,21 +3419,6 @@ static int kvm_io_bus_sort_cmp(const void *p1, const
> > void *p2)
> > return kvm_io_bus_cmp(p1, p2);
> > }
> >
> > -static int kvm_io_bus_insert_dev(struct kvm_io_bus *bus, struct
> > kvm_io_device *dev,
> > - gpa_t addr, int len)
> > -{
> > - bus->range[bus->dev_count++] = (struct kvm_io_range) {
> > - .addr = addr,
> > - .len = len,
> > - .dev = dev,
> > - };
> > -
> > - sort(bus->range, bus->dev_count, sizeof(struct kvm_io_range),
> > - kvm_io_bus_sort_cmp, NULL);
> > -
> > - return 0;
> > -}
> > -
> > static int kvm_io_bus_get_first_dev(struct kvm_io_bus *bus,
> > gpa_t addr, int len)
> > {
> > @@ -3574,7 +3559,9 @@ int kvm_io_bus_read(struct kvm_vcpu *vcpu, enum
> > kvm_bus bus_idx, gpa_t addr,
> > int kvm_io_bus_register_dev(struct kvm *kvm, enum kvm_bus bus_idx, gpa_t
> > addr,
> > int len, struct kvm_io_device *dev)
> > {
> > + int i;
> > struct kvm_io_bus *new_bus, *bus;
> > + struct kvm_io_range range;
> >
> > bus = kvm_get_bus(kvm, bus_idx);
> > if (!bus)
> > @@ -3588,9 +3575,22 @@ int kvm_io_bus_register_dev(struct kvm *kvm, enum
> > kvm_bus bus_idx, gpa_t addr,
> > sizeof(struct kvm_io_range)), GFP_KERNEL);
> > if (!new_bus)
> > return -ENOMEM;
> > - memcpy(new_bus, bus, sizeof(*bus) + (bus->dev_count *
> > - sizeof(struct kvm_io_range)));
> > - kvm_io_bus_insert_dev(new_bus, dev, addr, len);
> > +
> > + range = (struct kvm_io_range) {
> > + .addr = addr,
> > + .len = len,
> > + .dev = dev,
> > + };
> > +
> > + for (i = 0; i < bus->dev_count; i++)
> > + if (kvm_io_bus_cmp(&bus->range[i], &range) > 0)
> > + break;
> > +
> > + memcpy(new_bus, bus, sizeof(*bus) + i * sizeof(struct
> > kvm_io_range));
> > + new_bus->dev_count++;
> > + new_bus->range[i] = range;
> > + memcpy(new_bus->range + i + 1, bus->range + i,
> > + (bus->dev_count - i) * sizeof(struct kvm_io_range));
> > rcu_assign_pointer(kvm->buses[bus_idx], new_bus);
> > synchronize_srcu_expedited(&kvm->srcu);
> > kfree(bus);
> > --
> > 2.7.5
> >
>
