[Qemu-devel] [PATCH for-2.5 2/4] vhost: simplify/speedify vhost_dev_assign_memory()

[Igor Mammedov]

simplify memory map region insertion by making
memory map a sorted array. That allows replace
linear array scan with binary search to find
an insertion position and simplifies code when
new memory region merges into adjacent regions.

It will also allow to simplify vhost_dev_unassign_memory()
in following commit as well make kernel side
do less work since it stores memap in similar
sorted array.

Signed-off-by: Igor Mammedov <address@hidden>
---
 hw/virtio/vhost.c | 119 ++++++++++++++++++++++++++++++++++--------------------
 1 file changed, 76 insertions(+), 43 deletions(-)

diff --git a/hw/virtio/vhost.c b/hw/virtio/vhost.c
index 2be269f..8bef43e 100644
--- a/hw/virtio/vhost.c
+++ b/hw/virtio/vhost.c
@@ -134,6 +134,32 @@ static void vhost_log_sync_range(struct vhost_dev *dev,
     }
 }
 
+/* find a memory range whose GPA base is less than @start_addr
+ * memory range array must be array sorted in decreasing order.
+ * returns:
+ *     - if found, index in array of found range
+ *     - if not found,
+ *         - index of range whose GPA base is less then @start_addr or
+ *         - index beyond array if @start_addr is greater than GPA base
+ *           of the last range in array
+ */
+static int memory_range_bsearch(const struct vhost_dev *dev,
+                                uint64_t start_addr)
+{
+    int start = 0, end = dev->mem->nregions;
+
+    while (start < end) {
+        int slot = start + (end - start) / 2;
+        const struct vhost_memory_region *reg = dev->mem->regions + slot;
+        if (start_addr >= reg->guest_phys_addr) {
+            end = slot;
+        } else {
+            start = slot + 1;
+        }
+    }
+    return start;
+}
+
 /* Assign/unassign. Keep an unsorted array of non-overlapping
  * memory regions in dev->mem. */
 static void vhost_dev_unassign_memory(struct vhost_dev *dev,
@@ -227,58 +253,65 @@ static void vhost_dev_assign_memory(struct vhost_dev *dev,
                                     uint64_t size,
                                     uint64_t uaddr)
 {
-    int from, to;
-    struct vhost_memory_region *merged = NULL;
-    for (from = 0, to = 0; from < dev->mem->nregions; ++from, ++to) {
-        struct vhost_memory_region *reg = dev->mem->regions + to;
-        uint64_t prlast, urlast;
-        uint64_t pmlast, umlast;
-        uint64_t s, e, u;
-
-        /* clone old region */
-        if (to != from) {
-            memcpy(reg, dev->mem->regions + from, sizeof *reg);
+    struct vhost_memory_region *reg;
+    uint64_t prlast, urlast;
+    int idx;
+    int merged = 0;
+
+    idx = memory_range_bsearch(dev, start_addr);
+
+    /* merge at start of region with bigger GPA */
+    if (idx - 1 >= 0) {
+        reg = dev->mem->regions + idx - 1;
+        uint64_t pmlast = range_get_last(start_addr, size);
+        uint64_t umlast = range_get_last(uaddr, size);
+        if (pmlast + 1 == reg->guest_phys_addr &&
+            umlast + 1 == reg->userspace_addr) {
+            reg->memory_size = reg->guest_phys_addr + reg->memory_size -
+                               start_addr;
+            reg->guest_phys_addr = start_addr;
+            reg->userspace_addr = uaddr;
+            merged++;
         }
+    }
+
+    reg = dev->mem->regions + idx;
+    /* merge at end of region with smaller GPA */
+    if (idx < dev->mem->nregions) {
         prlast = range_get_last(reg->guest_phys_addr, reg->memory_size);
-        pmlast = range_get_last(start_addr, size);
         urlast = range_get_last(reg->userspace_addr, reg->memory_size);
-        umlast = range_get_last(uaddr, size);
-
-        /* check for overlapping regions: should never happen. */
-        assert(prlast < start_addr || pmlast < reg->guest_phys_addr);
-        /* Not an adjacent or overlapping region - do not merge. */
-        if ((prlast + 1 != start_addr || urlast + 1 != uaddr) &&
-            (pmlast + 1 != reg->guest_phys_addr ||
-             umlast + 1 != reg->userspace_addr)) {
-            continue;
+        if (prlast + 1 == start_addr && urlast + 1 == uaddr) {
+            reg->memory_size = start_addr + size - reg->guest_phys_addr;
+            merged++;
         }
+    }
 
-        if (merged) {
-            --to;
-            assert(to >= 0);
-        } else {
-            merged = reg;
+    /* merge 2 adjacent ranges in case previous merges closed gaps */
+    if (merged == 2) {
+        prlast = range_get_last(reg->guest_phys_addr, reg->memory_size);
+        urlast = range_get_last(reg->userspace_addr, reg->memory_size);
+        if (prlast + 1 == start_addr && urlast + 1 == uaddr) {
+            struct vhost_memory_region *regprev = dev->mem->regions + idx - 1;
+            reg->memory_size = regprev->guest_phys_addr + regprev->memory_size 
-
+                               reg->guest_phys_addr;
+            memmove(reg - 1, reg,
+                    (dev->mem->nregions - idx) * sizeof dev->mem->regions[0]);
+            dev->mem->nregions--;
         }
-        u = MIN(uaddr, reg->userspace_addr);
-        s = MIN(start_addr, reg->guest_phys_addr);
-        e = MAX(pmlast, prlast);
-        uaddr = merged->userspace_addr = u;
-        start_addr = merged->guest_phys_addr = s;
-        size = merged->memory_size = e - s + 1;
-        assert(merged->memory_size);
     }
 
-    if (!merged) {
-        struct vhost_memory_region *reg = dev->mem->regions + to;
-        memset(reg, 0, sizeof *reg);
-        reg->memory_size = size;
-        assert(reg->memory_size);
-        reg->guest_phys_addr = start_addr;
-        reg->userspace_addr = uaddr;
-        ++to;
+    if (merged) {
+        return;
     }
-    assert(to <= dev->mem->nregions + 1);
-    dev->mem->nregions = to;
+
+    /* insert a new region */
+    memmove(reg + 1, reg,
+            (dev->mem->nregions - idx) * sizeof dev->mem->regions[0]);
+    memset(reg, 0, sizeof *reg);
+    reg->memory_size = size;
+    reg->guest_phys_addr = start_addr;
+    reg->userspace_addr = uaddr;
+    dev->mem->nregions++;
 }
 
 static uint64_t vhost_get_log_size(struct vhost_dev *dev)
-- 
1.8.3.1