Re: [dpdk-dev] [PATCH v3 2/2] vhost: binary search address mapping table

["Liu, Yong" <yong.liu@intel.com>]

> -----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;
> >  }
> >
> >