Re: [PATCH v1 11/15] libvhost-user: Speedup gpa_to_mem_region() and vu_gpa_to_va()

[Raphael Norwitz]

One comment on this one.

On Fri, Feb 2, 2024 at 4:56 PM David Hildenbrand <david@redhat.com> wrote:
>
> Let's speed up GPA to memory region / virtual address lookup. Store the
> memory regions ordered by guest physical addresses, and use binary
> search for address translation, as well as when adding/removing memory
> regions.
>
> Most importantly, this will speed up GPA->VA address translation when we
> have many memslots.
>
> Signed-off-by: David Hildenbrand <david@redhat.com>
> ---
>  subprojects/libvhost-user/libvhost-user.c | 49 +++++++++++++++++++++--
>  1 file changed, 45 insertions(+), 4 deletions(-)
>
> diff --git a/subprojects/libvhost-user/libvhost-user.c 
> b/subprojects/libvhost-user/libvhost-user.c
> index d036b54ed0..75e47b7bb3 100644
> --- a/subprojects/libvhost-user/libvhost-user.c
> +++ b/subprojects/libvhost-user/libvhost-user.c
> @@ -199,19 +199,30 @@ vu_panic(VuDev *dev, const char *msg, ...)
>  static VuDevRegion *
>  vu_gpa_to_mem_region(VuDev *dev, uint64_t guest_addr)
>  {
> -    unsigned int i;
> +    int low = 0;
> +    int high = dev->nregions - 1;
>
>      /*
>       * Memory regions cannot overlap in guest physical address space. Each
>       * GPA belongs to exactly one memory region, so there can only be one
>       * match.
> +     *
> +     * We store our memory regions ordered by GPA and can simply perform a
> +     * binary search.
>       */
> -    for (i = 0; i < dev->nregions; i++) {
> -        VuDevRegion *cur = &dev->regions[i];
> +    while (low <= high) {
> +        unsigned int mid = low + (high - low) / 2;
> +        VuDevRegion *cur = &dev->regions[mid];
>
>          if (guest_addr >= cur->gpa && guest_addr < cur->gpa + cur->size) {
>              return cur;
>          }
> +        if (guest_addr >= cur->gpa + cur->size) {
> +            low = mid + 1;
> +        }
> +        if (guest_addr < cur->gpa) {
> +            high = mid - 1;
> +        }
>      }
>      return NULL;
>  }
> @@ -273,9 +284,14 @@ vu_remove_all_mem_regs(VuDev *dev)
>  static void
>  _vu_add_mem_reg(VuDev *dev, VhostUserMemoryRegion *msg_region, int fd)
>  {
> +    const uint64_t start_gpa = msg_region->guest_phys_addr;
> +    const uint64_t end_gpa = start_gpa + msg_region->memory_size;
>      int prot = PROT_READ | PROT_WRITE;
>      VuDevRegion *r;
>      void *mmap_addr;
> +    int low = 0;
> +    int high = dev->nregions - 1;
> +    unsigned int idx;
>
>      DPRINT("Adding region %d\n", dev->nregions);
>      DPRINT("    guest_phys_addr: 0x%016"PRIx64"\n",
> @@ -295,6 +311,29 @@ _vu_add_mem_reg(VuDev *dev, VhostUserMemoryRegion 
> *msg_region, int fd)
>          prot = PROT_NONE;
>      }
>
> +    /*
> +     * We will add memory regions into the array sorted by GPA. Perform a
> +     * binary search to locate the insertion point: it will be at the low
> +     * index.
> +     */
> +    while (low <= high) {
> +        unsigned int mid = low + (high - low)  / 2;
> +        VuDevRegion *cur = &dev->regions[mid];
> +
> +        /* Overlap of GPA addresses. */

Looks like this check will only catch if the new region is fully
contained within an existing region. I think we need to check whether
either start or end region are in the range, i.e.:

if ((start_gpa > curr_gpa && start_gpa < cur->gpa + curr_size ) ||
    (end_gpa > currr->gpa && end_gpa < cur->gpa + curr->size)  )


> +        if (start_gpa < cur->gpa + cur->size && cur->gpa < end_gpa) {
> +            vu_panic(dev, "regions with overlapping guest physical 
> addresses");
> +            return;
> +        }
> +        if (start_gpa >= cur->gpa + cur->size) {
> +            low = mid + 1;
> +        }
> +        if (start_gpa < cur->gpa) {
> +            high = mid - 1;
> +        }
> +    }
> +    idx = low;
> +
>      /*
>       * We don't use offset argument of mmap() since the mapped address has
>       * to be page aligned, and we use huge pages.
> @@ -308,7 +347,9 @@ _vu_add_mem_reg(VuDev *dev, VhostUserMemoryRegion 
> *msg_region, int fd)
>      DPRINT("    mmap_addr:       0x%016"PRIx64"\n",
>             (uint64_t)(uintptr_t)mmap_addr);
>
> -    r = &dev->regions[dev->nregions];
> +    /* Shift all affected entries by 1 to open a hole at idx. */
> +    r = &dev->regions[idx];
> +    memmove(r + 1, r, sizeof(VuDevRegion) * (dev->nregions - idx));
>      r->gpa = msg_region->guest_phys_addr;
>      r->size = msg_region->memory_size;
>      r->qva = msg_region->userspace_addr;
> --
> 2.43.0
>
>