On Sun, Feb 4, 2024 at 9:51 AM David Hildenbrand <da...@redhat.com> wrote:
>
> On 04.02.24 03:10, Raphael Norwitz wrote:
> > One comment on this one.
> >
> > On Fri, Feb 2, 2024 at 4:56 PM David Hildenbrand <da...@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 <da...@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.:
>
> That check should cover all cases of overlaps, not just fully contained.
>
> See the QEMU implementation of range_overlaps_rang() that contains a
> similar logic:
>
> return !(range2->upb < range1->lob || range1->upb < range2->lob);
>
> !(range2->upb < range1->lob || range1->upb < range2->lob);
> = !(range2->upb < range1->lob) && !(range1->upb < range2->lob)
> = range2->upb >= range1->lob && range1->upb >= range2->lob
> = range1->lob <= range2->upb && range2->lob <= range1->upb
>
> In QEMU, upb is inclusive, if it were exclusive (like we have here):
>
> = range1->lob < range2->upb && range2->lob < range1->upb
>
> Which is what we have here with:
>
> range1->lob = start_gpa
> range1->upb = end_gpa
> range2->lob = cur->gpa
> range2->upb = cur->gpa + cur->size
>
> Also if you are interested, see
>
> https://stackoverflow.com/questions/3269434/whats-the-most-efficient-way-to-test-if-two-ranges-overlap
>
> Thanks!
Got it, thanks for the full explanation. With that:
Reviewed-by: Raphael Norwitz <raph...@enfabrica.net>
>
> --
> Cheers,
>
> David / dhildenb
>
