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

[Maxime Coquelin]

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