[Qemu-devel] [PATCH for-2.5 0/4] vhost: cleanups and switching to sorted memory map

[Qemu-devel] [PATCH for-2.5 0/4] vhost: cleanups and switching to sorted memory map

[Igor Mammedov]

making memory map a sorted array helps to simplify
and speed up lookup/insertion and deletion ops on it.
It also makes insertion/deteletion code easier to read.

Igor Mammedov (4):
  vhost: codding style fix tab indents
  vhost: simplify/speedify vhost_dev_assign_memory()
  vhost: switch region lookup from linear to bsearch
  vhost: simplify/speedify vhost_dev_unassign_memory()

 hw/virtio/vhost.c | 252 ++++++++++++++++++++++++++----------------------------
 1 file changed, 123 insertions(+), 129 deletions(-)

-- 
1.8.3.1

[Qemu-devel] [PATCH for-2.5 1/4] vhost: codding style fix tab indents

[Igor Mammedov]

Signed-off-by: Igor Mammedov <imammedo@redhat.com>
---
 hw/virtio/vhost.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/hw/virtio/vhost.c b/hw/virtio/vhost.c
index e964004..2be269f 100644
--- a/hw/virtio/vhost.c
+++ b/hw/virtio/vhost.c
@@ -384,8 +384,8 @@ static int vhost_verify_ring_mappings(struct vhost_dev *dev,
 }
 
 static struct vhost_memory_region *vhost_dev_find_reg(struct vhost_dev *dev,
-						      uint64_t start_addr,
-						      uint64_t size)
+                                                      uint64_t start_addr,
+                                                      uint64_t size)
 {
     int i, n = dev->mem->nregions;
     for (i = 0; i < n; ++i) {
-- 
1.8.3.1

[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 <imammedo@redhat.com>
---
 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

[Qemu-devel] [PATCH for-2.5 3/4] vhost: switch region lookup from linear to bsearch

[Igor Mammedov]

Signed-off-by: Igor Mammedov <imammedo@redhat.com>
---
 hw/virtio/vhost.c | 12 +++++-------
 1 file changed, 5 insertions(+), 7 deletions(-)

diff --git a/hw/virtio/vhost.c b/hw/virtio/vhost.c
index 8bef43e..5b8598b 100644
--- a/hw/virtio/vhost.c
+++ b/hw/virtio/vhost.c
@@ -420,13 +420,11 @@ static struct vhost_memory_region *vhost_dev_find_reg(struct vhost_dev *dev,
                                                       uint64_t start_addr,
                                                       uint64_t size)
 {
-    int i, n = dev->mem->nregions;
-    for (i = 0; i < n; ++i) {
-        struct vhost_memory_region *reg = dev->mem->regions + i;
-        if (ranges_overlap(reg->guest_phys_addr, reg->memory_size,
-                           start_addr, size)) {
-            return reg;
-        }
+    int i = memory_range_bsearch(dev, start_addr), n = dev->mem->nregions;
+    struct vhost_memory_region *reg = dev->mem->regions + i;
+    if (i < n && ranges_overlap(reg->guest_phys_addr, reg->memory_size,
+                                start_addr, size)) {
+        return reg;
     }
     return NULL;
 }
-- 
1.8.3.1

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

[Igor Mammedov]

beside reducing code size 2x times, it also makes
function faster and easier to read.

Signed-off-by: Igor Mammedov <imammedo@redhat.com>
---
 hw/virtio/vhost.c | 111 ++++++++++++++++++------------------------------------
 1 file changed, 37 insertions(+), 74 deletions(-)

diff --git a/hw/virtio/vhost.c b/hw/virtio/vhost.c
index 5b8598b..e2585e3 100644
--- a/hw/virtio/vhost.c
+++ b/hw/virtio/vhost.c
@@ -160,91 +160,54 @@ static int memory_range_bsearch(const struct vhost_dev *dev,
     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,
                                       uint64_t start_addr,
                                       uint64_t size)
 {
-    int from, to, n = dev->mem->nregions;
-    /* Track overlapping/split regions for sanity checking. */
-    int overlap_start = 0, overlap_end = 0, overlap_middle = 0, split = 0;
-
-    for (from = 0, to = 0; from < n; ++from, ++to) {
-        struct vhost_memory_region *reg = dev->mem->regions + to;
-        uint64_t reglast;
-        uint64_t memlast;
-        uint64_t change;
-
-        /* clone old region */
-        if (to != from) {
-            memcpy(reg, dev->mem->regions + from, sizeof *reg);
-        }
-
-        /* No overlap is simple */
-        if (!ranges_overlap(reg->guest_phys_addr, reg->memory_size,
-                            start_addr, size)) {
-            continue;
-        }
-
-        /* Split only happens if supplied region
-         * is in the middle of an existing one. Thus it can not
-         * overlap with any other existing region. */
-        assert(!split);
+    uint64_t reglast, memlast;
+    struct vhost_memory_region *reg;
+    int idx = memory_range_bsearch(dev, start_addr);
 
-        reglast = range_get_last(reg->guest_phys_addr, reg->memory_size);
-        memlast = range_get_last(start_addr, size);
+    if (idx == dev->mem->nregions) { /* not found any range */
+        return;
+    }
 
-        /* Remove whole region */
-        if (start_addr <= reg->guest_phys_addr && memlast >= reglast) {
-            --dev->mem->nregions;
-            --to;
-            ++overlap_middle;
-            continue;
-        }
+    reg = dev->mem->regions + idx;
+    reglast = range_get_last(reg->guest_phys_addr, reg->memory_size);
+    memlast = range_get_last(start_addr, size);
 
-        /* Shrink region */
-        if (memlast >= reglast) {
-            reg->memory_size = start_addr - reg->guest_phys_addr;
-            assert(reg->memory_size);
-            assert(!overlap_end);
-            ++overlap_end;
-            continue;
-        }
+    /* Remove whole region */
+    if (start_addr == reg->guest_phys_addr && memlast == reglast) {
+        memmove(reg, reg + 1, (dev->mem->nregions - idx - 1) *
+                               sizeof dev->mem->regions[0]);
+        dev->mem->nregions--;
+        return;
+    }
 
-        /* Shift region */
-        if (start_addr <= reg->guest_phys_addr) {
-            change = memlast + 1 - reg->guest_phys_addr;
-            reg->memory_size -= change;
-            reg->guest_phys_addr += change;
-            reg->userspace_addr += change;
-            assert(reg->memory_size);
-            assert(!overlap_start);
-            ++overlap_start;
-            continue;
-        }
+    /* Split region */
+    if (start_addr > reg->guest_phys_addr && memlast < reglast) {
+        memmove(reg + 1, reg, (dev->mem->nregions - idx) *
+                               sizeof dev->mem->regions[0]);
+        reg->guest_phys_addr = memlast + 1;
+        reg->memory_size = reglast - reg->guest_phys_addr + 1;
+        reg++;
+        reg->memory_size = start_addr - reg->guest_phys_addr;
+        dev->mem->nregions++;
+        return;
+    }
 
-        /* This only happens if supplied region
-         * is in the middle of an existing one. Thus it can not
-         * overlap with any other existing region. */
-        assert(!overlap_start);
-        assert(!overlap_end);
-        assert(!overlap_middle);
-        /* Split region: shrink first part, shift second part. */
-        memcpy(dev->mem->regions + n, reg, sizeof *reg);
+    /* Shrink region */
+    if (memlast == reglast) { /* shrink end side */
         reg->memory_size = start_addr - reg->guest_phys_addr;
-        assert(reg->memory_size);
-        change = memlast + 1 - reg->guest_phys_addr;
-        reg = dev->mem->regions + n;
-        reg->memory_size -= change;
-        assert(reg->memory_size);
-        reg->guest_phys_addr += change;
-        reg->userspace_addr += change;
-        /* Never add more than 1 region */
-        assert(dev->mem->nregions == n);
-        ++dev->mem->nregions;
-        ++split;
+        return;
+    } else if (start_addr == reg->guest_phys_addr) { /* shrink start side */
+        reg->guest_phys_addr = memlast + 1;
+        reg->memory_size = reglast - reg->guest_phys_addr + 1;
+        return;
     }
+    /* there shouldn't be any overlapped ranges by now */
+    assert(!ranges_overlap(reg->guest_phys_addr, reg->memory_size,
+                           start_addr, size));
 }
 
 /* Called after unassign, so no regions overlap the given range. */
-- 
1.8.3.1

Re: [Qemu-devel] [PATCH for-2.5 1/4] vhost: codding style fix tab indents

[Peter Maydell]

On 28 July 2015 at 15:52, Igor Mammedov <imammedo@redhat.com> wrote:
> Signed-off-by: Igor Mammedov <imammedo@redhat.com>
> ---
>  hw/virtio/vhost.c | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)

Typo in subject line...

-- PMM

Re: [Qemu-devel] [PATCH for-2.5 0/4] vhost: cleanups and switching to sorted memory map

[Michael S. Tsirkin]

On Tue, Jul 28, 2015 at 04:52:49PM +0200, Igor Mammedov wrote:
> making memory map a sorted array helps to simplify
> and speed up lookup/insertion and deletion ops on it.
> It also makes insertion/deteletion code easier to read.

I'm a bit confused by all the vhost patches you sent.
Is this series still something you want me to merge?
Or was it the one that caused memory corruptions with
mem hotplug?

> Igor Mammedov (4):
>   vhost: codding style fix tab indents
>   vhost: simplify/speedify vhost_dev_assign_memory()
>   vhost: switch region lookup from linear to bsearch
>   vhost: simplify/speedify vhost_dev_unassign_memory()
> 
>  hw/virtio/vhost.c | 252 ++++++++++++++++++++++++++----------------------------
>  1 file changed, 123 insertions(+), 129 deletions(-)
> 
> -- 
> 1.8.3.1

Re: [Qemu-devel] [PATCH for-2.5 0/4] vhost: cleanups and switching to sorted memory map

[Igor Mammedov]

On Wed, 12 Aug 2015 10:33:47 +0300
"Michael S. Tsirkin" <mst@redhat.com> wrote:

> On Tue, Jul 28, 2015 at 04:52:49PM +0200, Igor Mammedov wrote:
> > making memory map a sorted array helps to simplify
> > and speed up lookup/insertion and deletion ops on it.
> > It also makes insertion/deteletion code easier to read.
> 
> I'm a bit confused by all the vhost patches you sent.
> Is this series still something you want me to merge?
Yes, I'd like it to be merged.
There is no functional change, it's just self sufficient
cleanups/optimizations and a base for follow up:

patches that try to make initial memory not fragmented
in vhost view assuming that vhost won't use RAM in places
where it's overlapped by other MemoryRegions (PAM/VGA ..etc),
(i.e. borrowing continuous HVA idea).

That would make vhost more migration friendly since
number of entries in its memap will stay constant during
host boot compared to number of entries at startup time.


> Or was it the one that caused memory corruptions with
> mem hotplug?
> 
> > Igor Mammedov (4):
> >   vhost: codding style fix tab indents
> >   vhost: simplify/speedify vhost_dev_assign_memory()
> >   vhost: switch region lookup from linear to bsearch
> >   vhost: simplify/speedify vhost_dev_unassign_memory()
> > 
> >  hw/virtio/vhost.c | 252 ++++++++++++++++++++++++++----------------------------
> >  1 file changed, 123 insertions(+), 129 deletions(-)
> > 
> > -- 
> > 1.8.3.1