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

[David Hildenbrand <david@redhat.com>]

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!

-- 
Cheers,

David / dhildenb