From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1757005AbbFPVNr (ORCPT ); Tue, 16 Jun 2015 17:13:47 -0400 Received: from mx1.redhat.com ([209.132.183.28]:38248 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752798AbbFPVNk (ORCPT ); Tue, 16 Jun 2015 17:13:40 -0400 Date: Tue, 16 Jun 2015 23:13:33 +0200 From: Igor Mammedov To: "Michael S. Tsirkin" Cc: linux-kernel@vger.kernel.org, kvm@vger.kernel.org, pbonzini@redhat.com Subject: Re: [PATCH 1/5] vhost: use binary search instead of linear in find_region() Message-ID: <20150616231333.7f0cfb3d@igors-macbook-pro.local> In-Reply-To: <20150616230700-mutt-send-email-mst@redhat.com> References: <1434472419-148742-1-git-send-email-imammedo@redhat.com> <1434472419-148742-2-git-send-email-imammedo@redhat.com> <20150616230700-mutt-send-email-mst@redhat.com> MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Tue, 16 Jun 2015 23:07:24 +0200 "Michael S. Tsirkin" 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 > > --- > > 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 > > #include > > #include > > +#include > > > > #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