Re: [PATCH 1/5] vhost: use binary search instead of linear in find_region()

[Igor Mammedov <imammedo@redhat.com>]

On Tue, 16 Jun 2015 23:07:24 +0200
"Michael S. Tsirkin" <mst@redhat.com> wrote:

> On Tue, Jun 16, 2015 at 06:33:35PM +0200, Igor Mammedov wrote:
> > For default region layouts performance stays the same
> > as linear search i.e. it takes around 210ns average for
> > translate_desc() that inlines find_region().
> > 
> > But it scales better with larger amount of regions,
> > 235ns BS vs 300ns LS with 55 memory regions
> > and it will be about the same values when allowed number
> > of slots is increased to 509 like it has been done in kvm.
> > 
> > Signed-off-by: Igor Mammedov <imammedo@redhat.com>
> > ---
> >  drivers/vhost/vhost.c | 38 ++++++++++++++++++++++++++++----------
> >  1 file changed, 28 insertions(+), 10 deletions(-)
> > 
> > diff --git a/drivers/vhost/vhost.c b/drivers/vhost/vhost.c
> > index 2ee2826..a22f8c3 100644
> > --- a/drivers/vhost/vhost.c
> > +++ b/drivers/vhost/vhost.c
> > @@ -25,6 +25,7 @@
> >  #include <linux/kthread.h>
> >  #include <linux/cgroup.h>
> >  #include <linux/module.h>
> > +#include <linux/sort.h>
> >  
> >  #include "vhost.h"
> >  
> > @@ -590,6 +591,16 @@ int vhost_vq_access_ok(struct vhost_virtqueue
> > *vq) }
> >  EXPORT_SYMBOL_GPL(vhost_vq_access_ok);
> >  
> > +static int vhost_memory_reg_sort_cmp(const void *p1, const void
> > *p2) +{
> > +	const struct vhost_memory_region *r1 = p1, *r2 = p2;
> > +	if (r1->guest_phys_addr < r2->guest_phys_addr)
> > +		return 1;
> > +	if (r1->guest_phys_addr > r2->guest_phys_addr)
> > +		return -1;
> > +	return 0;
> > +}
> > +
> >  static long vhost_set_memory(struct vhost_dev *d, struct
> > vhost_memory __user *m) {
> >  	struct vhost_memory mem, *newmem, *oldmem;
> > @@ -609,9 +620,11 @@ static long vhost_set_memory(struct vhost_dev
> > *d, struct vhost_memory __user *m) memcpy(newmem, &mem, size);
> >  	if (copy_from_user(newmem->regions, m->regions,
> >  			   mem.nregions * sizeof *m->regions)) {
> > -		kfree(newmem);
> > +		kvfree(newmem);
> >  		return -EFAULT;
> >  	}
> 
> What's this doing here?
ops, it sneaked in from 2/5 when I was splitting patches.
I'll fix it up.

> 
> > +	sort(newmem->regions, newmem->nregions,
> > sizeof(*newmem->regions),
> > +		vhost_memory_reg_sort_cmp, NULL);
> >  
> >  	if (!memory_access_ok(d, newmem, 0)) {
> >  		kfree(newmem);
> > @@ -913,17 +926,22 @@ EXPORT_SYMBOL_GPL(vhost_dev_ioctl);
> >  static const struct vhost_memory_region *find_region(struct
> > vhost_memory *mem, __u64 addr, __u32 len)
> >  {
> > -	struct vhost_memory_region *reg;
> > -	int i;
> > +	const struct vhost_memory_region *reg;
> > +	int start = 0, end = mem->nregions;
> >  
> > -	/* linear search is not brilliant, but we really have on
> > the order of 6
> > -	 * regions in practice */
> > -	for (i = 0; i < mem->nregions; ++i) {
> > -		reg = mem->regions + i;
> > -		if (reg->guest_phys_addr <= addr &&
> > -		    reg->guest_phys_addr + reg->memory_size - 1 >=
> > addr)
> > -			return reg;
> > +	while (start < end) {
> > +		int slot = start + (end - start) / 2;
> > +		reg = mem->regions + slot;
> > +		if (addr >= reg->guest_phys_addr)
> > +			end = slot;
> > +		else
> > +			start = slot + 1;
> >  	}
> > +
> > +	reg = mem->regions + start;
> > +	if (addr >= reg->guest_phys_addr &&
> > +		reg->guest_phys_addr + reg->memory_size > addr)
> > +		return reg;
> >  	return NULL;
> >  }
> >  
> > -- 
> > 1.8.3.1