[v3,2/2] vhost: binary search address mapping table
Checks
Commit Message
If Tx zero copy enabled, gpa to hpa mapping table is updated one by
one. This will harm performance when guest memory backend using 2M
hugepages. Now utilize binary search to find the entry in mapping
table, meanwhile set threshold to 256 entries for linear search.
Signed-off-by: Marvin Liu <yong.liu@intel.com>
Comments
On 4/28/20 11:13 AM, Marvin Liu wrote:
> If Tx zero copy enabled, gpa to hpa mapping table is updated one by
> one. This will harm performance when guest memory backend using 2M
> hugepages. Now utilize binary search to find the entry in mapping
> table, meanwhile set threshold to 256 entries for linear search.
>
> Signed-off-by: Marvin Liu <yong.liu@intel.com>
>
> diff --git a/lib/librte_vhost/Makefile b/lib/librte_vhost/Makefile
> index e592795f2..8769afaad 100644
> --- a/lib/librte_vhost/Makefile
> +++ b/lib/librte_vhost/Makefile
> @@ -10,7 +10,7 @@ EXPORT_MAP := rte_vhost_version.map
>
> CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR) -O3
> CFLAGS += -I vhost_user
> -CFLAGS += -fno-strict-aliasing
> +CFLAGS += -fno-strict-aliasing -Wno-maybe-uninitialized
> LDLIBS += -lpthread
>
> ifeq ($(RTE_TOOLCHAIN), gcc)
> diff --git a/lib/librte_vhost/vhost.h b/lib/librte_vhost/vhost.h
> index 507dbf214..a0fee39d5 100644
> --- a/lib/librte_vhost/vhost.h
> +++ b/lib/librte_vhost/vhost.h
> @@ -546,20 +546,46 @@ extern int vhost_data_log_level;
> #define MAX_VHOST_DEVICE 1024
> extern struct virtio_net *vhost_devices[MAX_VHOST_DEVICE];
>
> +#define VHOST_BINARY_SEARCH_THRESH 256
> +static int guest_page_addrcmp(const void *p1, const void *p2)
> +{
> + const struct guest_page *page1 = (const struct guest_page *)p1;
> + const struct guest_page *page2 = (const struct guest_page *)p2;
> +
> + if (page1->guest_phys_addr > page2->guest_phys_addr)
> + return 1;
> + if (page1->guest_phys_addr < page2->guest_phys_addr)
> + return -1;
> +
> + return 0;
> +}
> +
> /* Convert guest physical address to host physical address */
> static __rte_always_inline rte_iova_t
> gpa_to_hpa(struct virtio_net *dev, uint64_t gpa, uint64_t size)
> {
> uint32_t i;
> struct guest_page *page;
> -
> - for (i = 0; i < dev->nr_guest_pages; i++) {
> - page = &dev->guest_pages[i];
> -
> - if (gpa >= page->guest_phys_addr &&
> - gpa + size < page->guest_phys_addr + page->size) {
> - return gpa - page->guest_phys_addr +
> - page->host_phys_addr;
> + struct guest_page key;
> +
> + if (dev->nr_guest_pages >= VHOST_BINARY_SEARCH_THRESH) {
I would have expected the binary search to be more efficient for much
smaller number of pages. Have you done some tests to define this
threshold value?
> + key.guest_phys_addr = gpa;
> + page = bsearch(&key, dev->guest_pages, dev->nr_guest_pages,
> + sizeof(struct guest_page), guest_page_addrcmp);
> + if (page) {
> + if (gpa + size < page->guest_phys_addr + page->size)
> + return gpa - page->guest_phys_addr +
> + page->host_phys_addr;
> + }
Is all the generated code inlined?
I see that in the elf file:
2386: 0000000000874f70 16 FUNC LOCAL DEFAULT 13 guest_page_addrcmp
> + } else {
> + for (i = 0; i < dev->nr_guest_pages; i++) {
> + page = &dev->guest_pages[i];
> +
> + if (gpa >= page->guest_phys_addr &&
> + gpa + size < page->guest_phys_addr +
> + page->size)
> + return gpa - page->guest_phys_addr +
> + page->host_phys_addr;
> }
> }
>
> diff --git a/lib/librte_vhost/vhost_user.c b/lib/librte_vhost/vhost_user.c
> index 79fcb9d19..15e50d27d 100644
> --- a/lib/librte_vhost/vhost_user.c
> +++ b/lib/librte_vhost/vhost_user.c
> @@ -965,6 +965,12 @@ add_guest_pages(struct virtio_net *dev, struct rte_vhost_mem_region *reg,
> reg_size -= size;
> }
>
> + /* sort guest page array if over binary search threshold */
> + if (dev->nr_guest_pages >= VHOST_BINARY_SEARCH_THRESH) {
> + qsort((void *)dev->guest_pages, dev->nr_guest_pages,
> + sizeof(struct guest_page), guest_page_addrcmp);
> + }
> +
> return 0;
> }
>
>
> -----Original Message-----
> From: Maxime Coquelin <maxime.coquelin@redhat.com>
> Sent: Tuesday, April 28, 2020 11:28 PM
> To: Liu, Yong <yong.liu@intel.com>; Ye, Xiaolong <xiaolong.ye@intel.com>;
> Wang, Zhihong <zhihong.wang@intel.com>
> Cc: dev@dpdk.org
> Subject: Re: [PATCH v3 2/2] vhost: binary search address mapping table
>
>
>
> On 4/28/20 11:13 AM, Marvin Liu wrote:
> > If Tx zero copy enabled, gpa to hpa mapping table is updated one by
> > one. This will harm performance when guest memory backend using 2M
> > hugepages. Now utilize binary search to find the entry in mapping
> > table, meanwhile set threshold to 256 entries for linear search.
> >
> > Signed-off-by: Marvin Liu <yong.liu@intel.com>
> >
> > diff --git a/lib/librte_vhost/Makefile b/lib/librte_vhost/Makefile
> > index e592795f2..8769afaad 100644
> > --- a/lib/librte_vhost/Makefile
> > +++ b/lib/librte_vhost/Makefile
> > @@ -10,7 +10,7 @@ EXPORT_MAP := rte_vhost_version.map
> >
> > CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR) -O3
> > CFLAGS += -I vhost_user
> > -CFLAGS += -fno-strict-aliasing
> > +CFLAGS += -fno-strict-aliasing -Wno-maybe-uninitialized
> > LDLIBS += -lpthread
> >
> > ifeq ($(RTE_TOOLCHAIN), gcc)
> > diff --git a/lib/librte_vhost/vhost.h b/lib/librte_vhost/vhost.h
> > index 507dbf214..a0fee39d5 100644
> > --- a/lib/librte_vhost/vhost.h
> > +++ b/lib/librte_vhost/vhost.h
> > @@ -546,20 +546,46 @@ extern int vhost_data_log_level;
> > #define MAX_VHOST_DEVICE 1024
> > extern struct virtio_net *vhost_devices[MAX_VHOST_DEVICE];
> >
> > +#define VHOST_BINARY_SEARCH_THRESH 256
> > +static int guest_page_addrcmp(const void *p1, const void *p2)
> > +{
> > + const struct guest_page *page1 = (const struct guest_page *)p1;
> > + const struct guest_page *page2 = (const struct guest_page *)p2;
> > +
> > + if (page1->guest_phys_addr > page2->guest_phys_addr)
> > + return 1;
> > + if (page1->guest_phys_addr < page2->guest_phys_addr)
> > + return -1;
> > +
> > + return 0;
> > +}
> > +
> > /* Convert guest physical address to host physical address */
> > static __rte_always_inline rte_iova_t
> > gpa_to_hpa(struct virtio_net *dev, uint64_t gpa, uint64_t size)
> > {
> > uint32_t i;
> > struct guest_page *page;
> > -
> > - for (i = 0; i < dev->nr_guest_pages; i++) {
> > - page = &dev->guest_pages[i];
> > -
> > - if (gpa >= page->guest_phys_addr &&
> > - gpa + size < page->guest_phys_addr + page->size) {
> > - return gpa - page->guest_phys_addr +
> > - page->host_phys_addr;
> > + struct guest_page key;
> > +
> > + if (dev->nr_guest_pages >= VHOST_BINARY_SEARCH_THRESH) {
>
> I would have expected the binary search to be more efficient for much
> smaller number of pages. Have you done some tests to define this
> threshold value?
>
Maxime,
In my unit test, binary search will be better when size over 16. But it won't be the case with real VM.
I have tested around 128 to 1024 pages, the benefit can be seen around 256. So threshold is set to it.
Thanks,
Marvin
> > + key.guest_phys_addr = gpa;
> > + page = bsearch(&key, dev->guest_pages, dev-
> >nr_guest_pages,
> > + sizeof(struct guest_page), guest_page_addrcmp);
> > + if (page) {
> > + if (gpa + size < page->guest_phys_addr + page->size)
> > + return gpa - page->guest_phys_addr +
> > + page->host_phys_addr;
> > + }
>
> Is all the generated code inlined?
>
The compare function hasn't been inlined. Will inline it in next version.
> I see that in the elf file:
> 2386: 0000000000874f70 16 FUNC LOCAL DEFAULT 13
> guest_page_addrcmp
>
> > + } else {
> > + for (i = 0; i < dev->nr_guest_pages; i++) {
> > + page = &dev->guest_pages[i];
> > +
> > + if (gpa >= page->guest_phys_addr &&
> > + gpa + size < page->guest_phys_addr +
> > + page->size)
> > + return gpa - page->guest_phys_addr +
> > + page->host_phys_addr;
> > }
> > }
> >
> > diff --git a/lib/librte_vhost/vhost_user.c b/lib/librte_vhost/vhost_user.c
> > index 79fcb9d19..15e50d27d 100644
> > --- a/lib/librte_vhost/vhost_user.c
> > +++ b/lib/librte_vhost/vhost_user.c
> > @@ -965,6 +965,12 @@ add_guest_pages(struct virtio_net *dev, struct
> rte_vhost_mem_region *reg,
> > reg_size -= size;
> > }
> >
> > + /* sort guest page array if over binary search threshold */
> > + if (dev->nr_guest_pages >= VHOST_BINARY_SEARCH_THRESH) {
> > + qsort((void *)dev->guest_pages, dev->nr_guest_pages,
> > + sizeof(struct guest_page), guest_page_addrcmp);
> > + }
> > +
> > return 0;
> > }
> >
> >
@@ -10,7 +10,7 @@ EXPORT_MAP := rte_vhost_version.map
CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR) -O3
CFLAGS += -I vhost_user
-CFLAGS += -fno-strict-aliasing
+CFLAGS += -fno-strict-aliasing -Wno-maybe-uninitialized
LDLIBS += -lpthread
ifeq ($(RTE_TOOLCHAIN), gcc)
@@ -546,20 +546,46 @@ extern int vhost_data_log_level;
#define MAX_VHOST_DEVICE 1024
extern struct virtio_net *vhost_devices[MAX_VHOST_DEVICE];
+#define VHOST_BINARY_SEARCH_THRESH 256
+static int guest_page_addrcmp(const void *p1, const void *p2)
+{
+ const struct guest_page *page1 = (const struct guest_page *)p1;
+ const struct guest_page *page2 = (const struct guest_page *)p2;
+
+ if (page1->guest_phys_addr > page2->guest_phys_addr)
+ return 1;
+ if (page1->guest_phys_addr < page2->guest_phys_addr)
+ return -1;
+
+ return 0;
+}
+
/* Convert guest physical address to host physical address */
static __rte_always_inline rte_iova_t
gpa_to_hpa(struct virtio_net *dev, uint64_t gpa, uint64_t size)
{
uint32_t i;
struct guest_page *page;
-
- for (i = 0; i < dev->nr_guest_pages; i++) {
- page = &dev->guest_pages[i];
-
- if (gpa >= page->guest_phys_addr &&
- gpa + size < page->guest_phys_addr + page->size) {
- return gpa - page->guest_phys_addr +
- page->host_phys_addr;
+ struct guest_page key;
+
+ if (dev->nr_guest_pages >= VHOST_BINARY_SEARCH_THRESH) {
+ key.guest_phys_addr = gpa;
+ page = bsearch(&key, dev->guest_pages, dev->nr_guest_pages,
+ sizeof(struct guest_page), guest_page_addrcmp);
+ if (page) {
+ if (gpa + size < page->guest_phys_addr + page->size)
+ return gpa - page->guest_phys_addr +
+ page->host_phys_addr;
+ }
+ } else {
+ for (i = 0; i < dev->nr_guest_pages; i++) {
+ page = &dev->guest_pages[i];
+
+ if (gpa >= page->guest_phys_addr &&
+ gpa + size < page->guest_phys_addr +
+ page->size)
+ return gpa - page->guest_phys_addr +
+ page->host_phys_addr;
}
}
@@ -965,6 +965,12 @@ add_guest_pages(struct virtio_net *dev, struct rte_vhost_mem_region *reg,
reg_size -= size;
}
+ /* sort guest page array if over binary search threshold */
+ if (dev->nr_guest_pages >= VHOST_BINARY_SEARCH_THRESH) {
+ qsort((void *)dev->guest_pages, dev->nr_guest_pages,
+ sizeof(struct guest_page), guest_page_addrcmp);
+ }
+
return 0;
}