| Message ID | 20240202215332.118728-12-david@redhat.com |
|---|---|
| State | New |
| Headers | show |
| Series | libvhost-user: support more memslots and cleanup memslot handling code | expand |
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 > >
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 <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.: 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!
On Sun, Feb 4, 2024 at 9:51 AM David Hildenbrand <david@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 <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.: > > 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 <raphael@enfabrica.net> > > -- > Cheers, > > David / dhildenb >
On 04.02.24 23:07, Raphael Norwitz wrote: > On Sun, Feb 4, 2024 at 9:51 AM David Hildenbrand <david@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 <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.: >> >> 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 <raphael@enfabrica.net> Thanks!
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. */ + 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;
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(-)