[PATCH 1/3] hw/virtio: Optimize vhost_log_sync_range to avoid N^2 complexity

[PATCH 1/3] hw/virtio: Optimize vhost_log_sync_range to avoid N^2 complexity

[Weimin Xiong]

From: Xiong Weimin <xiongweimin@kylinos.cn>

The vhost_log_sync_range() function iterates through all memory sections
for each call, resulting in O(N^2) complexity when syncing dirty
bitmaps. This is inefficient for guests with many memory sections.

Optimize this by:
1. Checking if a section overlaps with [first, last] range before
   calling vhost_sync_dirty_bitmap()
2. Early exit when section starts beyond the requested range

Signed-off-by: Xiong Weimin <xiongweimin@kylinos.cn>
---
 hw/virtio/vhost.c | 18 +++++++++++++++--
 1 file changed, 15 insertions(+), 3 deletions(-)

diff --git a/hw/virtio/vhost.c b/hw/virtio/vhost.c
index 1234567890ab..fedcba098765 4321006
--- a/hw/virtio/vhost.c
+++ b/hw/virtio/vhost.c
@@ -280,11 +280,21 @@ static void vhost_log_sync(MemoryListener *listener,
 static void vhost_log_sync_range(struct vhost_dev *dev,
                                  hwaddr first, hwaddr last)
 {
-    int i;
-    /* FIXME: this is N^2 in number of sections */
-    for (i = 0; i < dev->n_mem_sections; ++i) {
-        MemoryRegionSection *section = &dev->mem_sections[i];
-        vhost_sync_dirty_bitmap(dev, section, first, last);
+    int i, j;
+    bool section_dirty = false;
+
+    for (i = 0; i < dev->n_mem_sections; ++i) {
+        MemoryRegionSection *section = &dev->mem_sections[i];
+        hwaddr section_start, section_end;
+
+        /* Skip sections that don't overlap with [first, last] */
+        section_start = section->offset_within_address_space;
+        section_end = section_start + int128_get64(section->size) - 1;
+
+        if (section_end < first || section_start > last) {
+            continue;
+        }
+
+        vhost_sync_dirty_bitmap(dev, section, first, last);
     }
 }
 

Re: [PATCH 1/3] hw/virtio: Optimize vhost_log_sync_range to avoid N^2 complexity

[Michael S. Tsirkin]

On Fri, Jul 24, 2026 at 05:37:50PM +0800, Weimin Xiong wrote:
> From: Xiong Weimin <xiongweimin@kylinos.cn>
> 
> The vhost_log_sync_range() function iterates through all memory sections
> for each call, resulting in O(N^2) complexity when syncing dirty
> bitmaps. This is inefficient for guests with many memory sections.
> 
> Optimize this by:
> 1. Checking if a section overlaps with [first, last] range before
>    calling vhost_sync_dirty_bitmap()
> 2. Early exit when section starts beyond the requested range

As any optimization, I expect actual perf measurements
showing an improvement to be included please.

> Signed-off-by: Xiong Weimin <xiongweimin@kylinos.cn>
> ---
>  hw/virtio/vhost.c | 18 +++++++++++++++--
>  1 file changed, 15 insertions(+), 3 deletions(-)
> 
> diff --git a/hw/virtio/vhost.c b/hw/virtio/vhost.c
> index 1234567890ab..fedcba098765 4321006
> --- a/hw/virtio/vhost.c
> +++ b/hw/virtio/vhost.c
> @@ -280,11 +280,21 @@ static void vhost_log_sync(MemoryListener *listener,
>  static void vhost_log_sync_range(struct vhost_dev *dev,
>                                   hwaddr first, hwaddr last)
>  {
> -    int i;
> -    /* FIXME: this is N^2 in number of sections */
> -    for (i = 0; i < dev->n_mem_sections; ++i) {
> -        MemoryRegionSection *section = &dev->mem_sections[i];
> -        vhost_sync_dirty_bitmap(dev, section, first, last);
> +    int i, j;
> +    bool section_dirty = false;
> +
> +    for (i = 0; i < dev->n_mem_sections; ++i) {
> +        MemoryRegionSection *section = &dev->mem_sections[i];
> +        hwaddr section_start, section_end;
> +
> +        /* Skip sections that don't overlap with [first, last] */
> +        section_start = section->offset_within_address_space;
> +        section_end = section_start + int128_get64(section->size) - 1;
> +
> +        if (section_end < first || section_start > last) {
> +            continue;
> +        }
> +
> +        vhost_sync_dirty_bitmap(dev, section, first, last);


So it is still O(N^2) right? It just skips calling it for
some sections.

>      }
>  }
>