Re: [PATCH] IO: Intelligent device lookup on bus

[Sasha Levin <levinsasha928@gmail.com>]

On Wed, 2011-07-20 at 16:41 -0300, Marcelo Tosatti wrote:
> On Wed, Jul 20, 2011 at 03:11:58PM +0300, Sasha Levin wrote:
> > Currently the method of dealing with an IO operation on a bus (PIO/MMIO)
> > is to call the read or write callback for each device registered
> > on the bus until we find a device which handles it.
> > 
> > Since the number of devices on a bus can be significant due to ioeventfds
> > and coalesced MMIO zones, this leads to a lot of overhead on each IO
> > operation.
> > 
> > Instead of registering devices, we now register ranges which points to
> > a device. Lookup is done using an efficient bsearch instead of a linear
> > search.
> > 
> > This should speed up all IO operations generated by the guest.
> 
> Some numbers, please.
> 

I'm not sure how to measure performance in this case. You'd need to
measure access times to each device before and after the patch, and
average them.

It replaces a linear lookup with a binary one, it's not an absolute
improvement.

> > +int kvm_io_bus_find_closest_dev_idx(struct kvm_io_bus *bus,
> > +					gpa_t addr, int len)
> > +{
> > +	int start = 0, end = bus->dev_count - 1;
> > +
> > +	if (bus->dev_count == 0)
> > +		return -1;
> > +
> > +	while (start <= end) {
> > +		int mid = (start + end) / 2;
> > +		struct kvm_io_range *range = &bus->range[mid];
> > +
> > +		if (addr > range->addr)
> > +			start = mid + 1;
> > +		else if (addr < range->addr)
> > +			end = mid - 1;
> 
> If mid is zero, this assigns end = -1?
> 

Yes. Next step would be to exit the while ().

-- 

Sasha.