From: Igor Mammedov <imammedo@redhat.com>
To: "Michael S. Tsirkin" <mst@redhat.com>
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()
Date: Tue, 16 Jun 2015 23:13:33 +0200 [thread overview]
Message-ID: <20150616231333.7f0cfb3d@igors-macbook-pro.local> (raw)
In-Reply-To: <20150616230700-mutt-send-email-mst@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
next prev parent reply other threads:[~2015-06-16 21:13 UTC|newest]
Thread overview: 80+ messages / expand[flat|nested] mbox.gz Atom feed top
2015-06-16 16:33 [PATCH 0/5] vhost: support upto 509 memory regions Igor Mammedov
2015-06-16 16:33 ` [PATCH 1/5] vhost: use binary search instead of linear in find_region() Igor Mammedov
2015-06-16 21:07 ` Michael S. Tsirkin
2015-06-16 21:13 ` Igor Mammedov [this message]
2015-06-16 16:33 ` [PATCH 2/5] vhost: extend memory regions allocation to vmalloc Igor Mammedov
2015-06-16 16:33 ` [PATCH 3/5] vhost: support upto 509 memory regions Igor Mammedov
2015-06-16 21:14 ` Michael S. Tsirkin
2015-06-16 22:00 ` Igor Mammedov
2015-06-17 6:34 ` Michael S. Tsirkin
2015-06-17 7:28 ` Igor Mammedov
2015-06-17 7:39 ` Michael S. Tsirkin
2015-06-17 8:54 ` Igor Mammedov
2015-06-17 10:11 ` Michael S. Tsirkin
2015-06-17 10:37 ` Igor Mammedov
2015-06-17 10:46 ` Michael S. Tsirkin
2015-06-17 11:48 ` Igor Mammedov
2015-06-17 11:51 ` Michael S. Tsirkin
2015-06-17 12:23 ` Igor Mammedov
2015-06-17 13:13 ` Michael S. Tsirkin
2015-06-17 13:20 ` Paolo Bonzini
2015-06-17 14:32 ` Michael S. Tsirkin
2015-06-17 15:12 ` Igor Mammedov
2015-06-17 15:38 ` Michael S. Tsirkin
2015-06-17 16:09 ` Igor Mammedov
2015-06-17 16:30 ` Michael S. Tsirkin
2015-06-17 16:31 ` Paolo Bonzini
2015-06-17 16:34 ` Michael S. Tsirkin
2015-06-17 16:38 ` Paolo Bonzini
2015-06-17 16:41 ` Michael S. Tsirkin
2015-06-17 16:47 ` Paolo Bonzini
2015-06-17 17:32 ` Igor Mammedov
2015-06-17 19:11 ` Michael S. Tsirkin
2015-06-17 17:30 ` Igor Mammedov
2015-06-18 9:12 ` Igor Mammedov
2015-06-18 9:50 ` Michael S. Tsirkin
2015-06-18 10:03 ` Paolo Bonzini
2015-06-18 11:39 ` Igor Mammedov
2015-06-18 11:41 ` Michael S. Tsirkin
2015-06-18 11:50 ` Paolo Bonzini
2015-06-18 13:19 ` Michael S. Tsirkin
2015-06-18 13:46 ` Paolo Bonzini
2015-06-18 14:47 ` Michael S. Tsirkin
2015-06-18 15:54 ` Igor Mammedov
2015-06-18 16:02 ` Paolo Bonzini
2015-06-19 7:56 ` Michael S. Tsirkin
2015-06-19 7:57 ` Paolo Bonzini
2015-06-19 8:05 ` Michael S. Tsirkin
2015-06-19 8:52 ` Paolo Bonzini
2015-06-19 10:14 ` Michael S. Tsirkin
2015-06-19 10:44 ` Paolo Bonzini
2015-06-19 13:34 ` Michael S. Tsirkin
2015-06-19 13:34 ` Michael S. Tsirkin
2015-06-19 15:19 ` Paolo Bonzini
2015-06-19 15:19 ` Paolo Bonzini
2015-06-19 16:20 ` Michael S. Tsirkin
2015-06-19 16:20 ` Michael S. Tsirkin
2015-06-19 16:26 ` Paolo Bonzini
2015-06-19 16:26 ` Paolo Bonzini
2015-06-19 16:33 ` Michael S. Tsirkin
2015-06-19 16:33 ` Michael S. Tsirkin
2015-06-19 16:44 ` Paolo Bonzini
2015-06-19 16:44 ` Paolo Bonzini
2015-06-22 7:10 ` Igor Mammedov
2015-06-22 7:10 ` Igor Mammedov
2015-06-22 9:45 ` Paolo Bonzini
2015-06-22 9:45 ` Paolo Bonzini
2015-06-19 16:45 ` Michael S. Tsirkin
2015-06-19 16:45 ` Michael S. Tsirkin
2015-06-19 16:50 ` Paolo Bonzini
2015-06-19 16:50 ` Paolo Bonzini
2015-06-18 12:02 ` Igor Mammedov
2015-06-17 8:53 ` Paolo Bonzini
2015-06-16 16:33 ` [PATCH 4/5] vhost: add per VQ memory region caching Igor Mammedov
2015-06-16 16:33 ` [PATCH 5/5] vhost: translate_desc: optimization for desc.len < region size Igor Mammedov
2015-06-16 21:11 ` Michael S. Tsirkin
2015-06-16 21:16 ` [PATCH 0/5] vhost: support upto 509 memory regions Michael S. Tsirkin
2015-06-16 22:19 ` Igor Mammedov
2015-06-17 6:31 ` Michael S. Tsirkin
2015-06-17 7:33 ` Igor Mammedov
2015-06-17 7:40 ` Michael S. Tsirkin
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20150616231333.7f0cfb3d@igors-macbook-pro.local \
--to=imammedo@redhat.com \
--cc=kvm@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=mst@redhat.com \
--cc=pbonzini@redhat.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.