[Qemu-devel] [PATCH v2 0/7] dirty-bitmap: rewrite bdrv_dirty_iter_next_area

[Qemu-devel] [PATCH v2 0/7] dirty-bitmap: rewrite bdrv_dirty_iter_next_area

[Vladimir Sementsov-Ogievskiy]

Hi all.

1. bdrv_dirty_iter_next_area don't use hbitmap_next_zero and uses
inefficient loop instead. Let's improve it.

2. bdrv_dirty_iter_next_area don't handle unaligned offset and
max_offset correctly. I'm not sure that it is a real bug. But if it is,
we need these series in 3.0.

Details are in 04 commit message.

v2:

01: - improve comment
    - s/bytes/count/
    - fix forgotten function call in test
    - introduce orig_size field here for HBitmap,
      make checking in hbitmap_next_zero more effective and safe
02: new
03: - orig_size already introduced in 01
    - fix hbitmap_next_dirty_area to not return value less than
      offset on unaligned requests

Vladimir Sementsov-Ogievskiy (7):
  dirty-bitmap: improve bdrv_dirty_bitmap_next_zero
  tests: add tests for hbitmap_next_zero with non-zero count parameter
  dirty-bitmap: add bdrv_dirty_bitmap_next_dirty_area
  block/mirror: fix and improve do_sync_target_write
  Revert "block/dirty-bitmap: Add bdrv_dirty_iter_next_area"
  Revert "test-hbitmap: Add non-advancing iter_next tests"
  Revert "hbitmap: Add @advance param to hbitmap_iter_next()"

 include/block/dirty-bitmap.h |  8 +++--
 include/qemu/hbitmap.h       | 30 ++++++++++++++----
 block/backup.c               |  4 +--
 block/dirty-bitmap.c         | 69 +++++++----------------------------------
 block/mirror.c               | 16 +++++-----
 nbd/server.c                 |  2 +-
 tests/test-hbitmap.c         | 69 +++++++++++++++++++++++------------------
 util/hbitmap.c               | 73 ++++++++++++++++++++++++++++++++++++--------
 8 files changed, 151 insertions(+), 120 deletions(-)

-- 
2.11.1

[Qemu-devel] [PATCH v2 1/7] dirty-bitmap: improve bdrv_dirty_bitmap_next_zero

[Vladimir Sementsov-Ogievskiy]

Add bytes parameter to the function, to limit searched range.

Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
 include/block/dirty-bitmap.h |  3 ++-
 include/qemu/hbitmap.h       | 10 ++++++++--
 block/backup.c               |  2 +-
 block/dirty-bitmap.c         |  5 +++--
 nbd/server.c                 |  2 +-
 tests/test-hbitmap.c         |  2 +-
 util/hbitmap.c               | 25 ++++++++++++++++++++-----
 7 files changed, 36 insertions(+), 13 deletions(-)

diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
index 259bd27c40..5dc146abf3 100644
--- a/include/block/dirty-bitmap.h
+++ b/include/block/dirty-bitmap.h
@@ -98,7 +98,8 @@ bool bdrv_has_changed_persistent_bitmaps(BlockDriverState *bs);
 BdrvDirtyBitmap *bdrv_dirty_bitmap_next(BlockDriverState *bs,
                                         BdrvDirtyBitmap *bitmap);
 char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp);
-int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start);
+int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start,
+                                    uint64_t bytes);
 BdrvDirtyBitmap *bdrv_reclaim_dirty_bitmap_locked(BlockDriverState *bs,
                                                   BdrvDirtyBitmap *bitmap,
                                                   Error **errp);
diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
index ddca52c48e..cd091f6134 100644
--- a/include/qemu/hbitmap.h
+++ b/include/qemu/hbitmap.h
@@ -295,10 +295,16 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
 /* hbitmap_next_zero:
  * @hb: The HBitmap to operate on
  * @start: The bit to start from.
+ * @count: Range length to search in. If @count is zero, search up to the bitmap
+ *         end.
  *
- * Find next not dirty bit.
+ * Find next not dirty bit within range [@start, @start + @count), or from
+ * @start to the bitmap end if @count is zero. If not found, return -1.
+ *
+ * @start + @count must not be greater than original bitmap size
+ * (hbitmap_alloc parameter)
  */
-int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start);
+int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t count);
 
 /* hbitmap_create_meta:
  * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap.
diff --git a/block/backup.c b/block/backup.c
index 8630d32926..3c8b054587 100644
--- a/block/backup.c
+++ b/block/backup.c
@@ -458,7 +458,7 @@ static void backup_incremental_init_copy_bitmap(BackupBlockJob *job)
             break;
         }
 
-        offset = bdrv_dirty_bitmap_next_zero(job->sync_bitmap, offset);
+        offset = bdrv_dirty_bitmap_next_zero(job->sync_bitmap, offset, 0);
         if (offset == -1) {
             hbitmap_set(job->copy_bitmap, cluster, end - cluster);
             break;
diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
index c9b8a6fd52..a9ee814da7 100644
--- a/block/dirty-bitmap.c
+++ b/block/dirty-bitmap.c
@@ -785,9 +785,10 @@ char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp)
     return hbitmap_sha256(bitmap->bitmap, errp);
 }
 
-int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset)
+int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset,
+                                    uint64_t bytes)
 {
-    return hbitmap_next_zero(bitmap->bitmap, offset);
+    return hbitmap_next_zero(bitmap->bitmap, offset, bytes);
 }
 
 void bdrv_merge_dirty_bitmap(BdrvDirtyBitmap *dest, const BdrvDirtyBitmap *src,
diff --git a/nbd/server.c b/nbd/server.c
index ea5fe0eb33..92a5651ba9 100644
--- a/nbd/server.c
+++ b/nbd/server.c
@@ -1952,7 +1952,7 @@ static unsigned int bitmap_to_extents(BdrvDirtyBitmap *bitmap, uint64_t offset,
     assert(begin < overall_end && nb_extents);
     while (begin < overall_end && i < nb_extents) {
         if (dirty) {
-            end = bdrv_dirty_bitmap_next_zero(bitmap, begin);
+            end = bdrv_dirty_bitmap_next_zero(bitmap, begin, 0);
         } else {
             bdrv_set_dirty_iter(it, begin);
             end = bdrv_dirty_iter_next(it);
diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
index 5e67ac1d3a..888515b3bb 100644
--- a/tests/test-hbitmap.c
+++ b/tests/test-hbitmap.c
@@ -939,7 +939,7 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data,
 
 static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start)
 {
-    int64_t ret1 = hbitmap_next_zero(data->hb, start);
+    int64_t ret1 = hbitmap_next_zero(data->hb, start, 0);
     int64_t ret2 = start;
     for ( ; ret2 < data->size && hbitmap_get(data->hb, ret2); ret2++) {
         ;
diff --git a/util/hbitmap.c b/util/hbitmap.c
index bcd304041a..8dbcd80a3d 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -53,6 +53,9 @@
  */
 
 struct HBitmap {
+    /* Size of the bitmap, as requested in hbitmap_alloc. */
+    uint64_t orig_size;
+
     /* Number of total bits in the bottom level.  */
     uint64_t size;
 
@@ -192,16 +195,26 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first)
     }
 }
 
-int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start)
+int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t count)
 {
     size_t pos = (start >> hb->granularity) >> BITS_PER_LEVEL;
     unsigned long *last_lev = hb->levels[HBITMAP_LEVELS - 1];
-    uint64_t sz = hb->sizes[HBITMAP_LEVELS - 1];
     unsigned long cur = last_lev[pos];
-    unsigned start_bit_offset =
-            (start >> hb->granularity) & (BITS_PER_LONG - 1);
+    unsigned start_bit_offset;
+    uint64_t end_bit, sz;
     int64_t res;
 
+    assert(start < hb->orig_size);
+    assert(!count ||
+           (count <= hb->orig_size && start <= hb->orig_size - count));
+
+    end_bit = count ? ((start + count - 1) >> hb->granularity) + 1 : hb->size;
+    sz = (end_bit + BITS_PER_LONG - 1) >> BITS_PER_LEVEL;
+
+    /* There may be some zero bits in @cur before @start. We are not interested
+     * in them, let's set them.
+     */
+    start_bit_offset = (start >> hb->granularity) & (BITS_PER_LONG - 1);
     cur |= (1UL << start_bit_offset) - 1;
     assert((start >> hb->granularity) < hb->size);
 
@@ -218,7 +231,7 @@ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start)
     }
 
     res = (pos << BITS_PER_LEVEL) + ctol(cur);
-    if (res >= hb->size) {
+    if (res >= end_bit) {
         return -1;
     }
 
@@ -652,6 +665,8 @@ HBitmap *hbitmap_alloc(uint64_t size, int granularity)
     HBitmap *hb = g_new0(struct HBitmap, 1);
     unsigned i;
 
+    hb->orig_size = size;
+
     assert(granularity >= 0 && granularity < 64);
     size = (size + (1ULL << granularity) - 1) >> granularity;
     assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
-- 
2.11.1

[Qemu-devel] [PATCH v2 2/7] tests: add tests for hbitmap_next_zero with non-zero count parameter

[Vladimir Sementsov-Ogievskiy]

Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
 tests/test-hbitmap.c | 31 +++++++++++++++++++++++++++----
 1 file changed, 27 insertions(+), 4 deletions(-)

diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
index 888515b3bb..c11d160633 100644
--- a/tests/test-hbitmap.c
+++ b/tests/test-hbitmap.c
@@ -937,31 +937,48 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data,
     check_hbitmap_iter_next(&hbi);
 }
 
-static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start)
+static void test_hbitmap_next_zero_check_range(TestHBitmapData *data,
+                                               int64_t start,
+                                               int64_t count)
 {
-    int64_t ret1 = hbitmap_next_zero(data->hb, start, 0);
+    int64_t ret1 = hbitmap_next_zero(data->hb, start, count);
     int64_t ret2 = start;
-    for ( ; ret2 < data->size && hbitmap_get(data->hb, ret2); ret2++) {
+    int64_t end = count ? start + count : data->size;
+
+    for ( ; ret2 < end && hbitmap_get(data->hb, ret2); ret2++) {
         ;
     }
-    if (ret2 == data->size) {
+    if (ret2 == end) {
         ret2 = -1;
     }
 
     g_assert_cmpint(ret1, ==, ret2);
 }
 
+static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start)
+{
+    test_hbitmap_next_zero_check_range(data, start, 0);
+}
+
 static void test_hbitmap_next_zero_do(TestHBitmapData *data, int granularity)
 {
     hbitmap_test_init(data, L3, granularity);
     test_hbitmap_next_zero_check(data, 0);
     test_hbitmap_next_zero_check(data, L3 - 1);
+    test_hbitmap_next_zero_check_range(data, 0, 1);
+    test_hbitmap_next_zero_check_range(data, L3 - 1, 1);
 
     hbitmap_set(data->hb, L2, 1);
     test_hbitmap_next_zero_check(data, 0);
     test_hbitmap_next_zero_check(data, L2 - 1);
     test_hbitmap_next_zero_check(data, L2);
     test_hbitmap_next_zero_check(data, L2 + 1);
+    test_hbitmap_next_zero_check_range(data, 0, 1);
+    test_hbitmap_next_zero_check_range(data, 0, L2);
+    test_hbitmap_next_zero_check_range(data, L2 - 1, 1);
+    test_hbitmap_next_zero_check_range(data, L2 - 1, 2);
+    test_hbitmap_next_zero_check_range(data, L2, 1);
+    test_hbitmap_next_zero_check_range(data, L2 + 1, 1);
 
     hbitmap_set(data->hb, L2 + 5, L1);
     test_hbitmap_next_zero_check(data, 0);
@@ -970,6 +987,10 @@ static void test_hbitmap_next_zero_do(TestHBitmapData *data, int granularity)
     test_hbitmap_next_zero_check(data, L2 + 5);
     test_hbitmap_next_zero_check(data, L2 + L1 - 1);
     test_hbitmap_next_zero_check(data, L2 + L1);
+    test_hbitmap_next_zero_check_range(data, L2, 6);
+    test_hbitmap_next_zero_check_range(data, L2 + 1, 3);
+    test_hbitmap_next_zero_check_range(data, L2 + 4, L1);
+    test_hbitmap_next_zero_check_range(data, L2 + 5, L1);
 
     hbitmap_set(data->hb, L2 * 2, L3 - L2 * 2);
     test_hbitmap_next_zero_check(data, L2 * 2 - L1);
@@ -977,6 +998,8 @@ static void test_hbitmap_next_zero_do(TestHBitmapData *data, int granularity)
     test_hbitmap_next_zero_check(data, L2 * 2 - 1);
     test_hbitmap_next_zero_check(data, L2 * 2);
     test_hbitmap_next_zero_check(data, L3 - 1);
+    test_hbitmap_next_zero_check_range(data, L2 * 2 - L1, L1 + 1);
+    test_hbitmap_next_zero_check_range(data, L2 * 2, L2);
 
     hbitmap_set(data->hb, 0, L3);
     test_hbitmap_next_zero_check(data, 0);
-- 
2.11.1

[Qemu-devel] [PATCH v2 3/7] dirty-bitmap: add bdrv_dirty_bitmap_next_dirty_area

[Vladimir Sementsov-Ogievskiy]

The function alters bdrv_dirty_iter_next_area(), which is wrong and
less efficient (see next commit for description).

Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
 include/block/dirty-bitmap.h |  3 +++
 include/qemu/hbitmap.h       | 15 +++++++++++++++
 block/dirty-bitmap.c         |  7 +++++++
 util/hbitmap.c               | 38 ++++++++++++++++++++++++++++++++++++++
 4 files changed, 63 insertions(+)

diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
index 5dc146abf3..c02be67564 100644
--- a/include/block/dirty-bitmap.h
+++ b/include/block/dirty-bitmap.h
@@ -100,6 +100,9 @@ BdrvDirtyBitmap *bdrv_dirty_bitmap_next(BlockDriverState *bs,
 char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp);
 int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start,
                                     uint64_t bytes);
+bool bdrv_dirty_bitmap_next_dirty_area(BdrvDirtyBitmap *bitmap,
+                                       uint64_t *offset, uint64_t end,
+                                       uint64_t *length);
 BdrvDirtyBitmap *bdrv_reclaim_dirty_bitmap_locked(BlockDriverState *bs,
                                                   BdrvDirtyBitmap *bitmap,
                                                   Error **errp);
diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
index cd091f6134..b1e897af28 100644
--- a/include/qemu/hbitmap.h
+++ b/include/qemu/hbitmap.h
@@ -306,6 +306,21 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
  */
 int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t count);
 
+/* hbitmap_next_dirty_area:
+ * @hb: The HBitmap to operate on
+ * @offset: in-out parameter.
+ *          in: the offset to start from
+ *          out: (if area found) start of found area
+ * @end: end of requested region. (*@offset + *@length) will be <= @end
+ * @length: length of found area
+ *
+ * If dirty area found within [@offset, @end), returns true and sets @offset
+ * and @length appropriately. Otherwise returns true and leaves @offset and
+ * @length unchanged.
+ */
+bool hbitmap_next_dirty_area(const HBitmap *hb, uint64_t *offset,
+                             uint64_t end, uint64_t *length);
+
 /* hbitmap_create_meta:
  * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap.
  * The caller owns the created bitmap and must call hbitmap_free_meta(hb) to
diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
index a9ee814da7..c24aa0e229 100644
--- a/block/dirty-bitmap.c
+++ b/block/dirty-bitmap.c
@@ -791,6 +791,13 @@ int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset,
     return hbitmap_next_zero(bitmap->bitmap, offset, bytes);
 }
 
+bool bdrv_dirty_bitmap_next_dirty_area(BdrvDirtyBitmap *bitmap,
+                                       uint64_t *offset, uint64_t end,
+                                       uint64_t *length)
+{
+    return hbitmap_next_dirty_area(bitmap->bitmap, offset, end, length);
+}
+
 void bdrv_merge_dirty_bitmap(BdrvDirtyBitmap *dest, const BdrvDirtyBitmap *src,
                              Error **errp)
 {
diff --git a/util/hbitmap.c b/util/hbitmap.c
index 8dbcd80a3d..9de0d7bf2d 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -244,6 +244,44 @@ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t count)
     return res;
 }
 
+bool hbitmap_next_dirty_area(const HBitmap *hb, uint64_t *offset,
+                             uint64_t end, uint64_t *length)
+{
+    HBitmapIter hbi;
+    int64_t off1, off0;
+    uint32_t granularity = 1UL << hb->granularity;
+
+    if (end == 0) {
+        end = hb->orig_size;
+    }
+
+    hbitmap_iter_init(&hbi, hb, *offset << hb->granularity);
+    off1 = hbitmap_iter_next(&hbi, true);
+
+    if (off1 < 0 || off1 >= end) {
+        return false;
+    }
+
+    if (off1 + granularity >= end) {
+        if (off1 > *offset) {
+            *offset = off1;
+        }
+        *length = end - *offset;
+        return true;
+    }
+
+    off0 = hbitmap_next_zero(hb, off1 + granularity, end);
+    if (off0 < 0) {
+        off0 = end;
+    }
+
+    if (off1 > *offset) {
+        *offset = off1;
+    }
+    *length = off0 - *offset;
+    return true;
+}
+
 bool hbitmap_empty(const HBitmap *hb)
 {
     return hb->count == 0;
-- 
2.11.1

[Qemu-devel] [PATCH v2 4/7] block/mirror: fix and improve do_sync_target_write

[Vladimir Sementsov-Ogievskiy]

Use bdrv_dirty_bitmap_next_dirty_area() instead of
bdrv_dirty_iter_next_area(), because of the following problems of
bdrv_dirty_iter_next_area():

1. Using HBitmap iterators we should carefully handle unaligned offset,
as first call to hbitmap_iter_next() may return a value less than
original offset (actually, it will be original offset rounded down to
bitmap granularity). This handling is not done in
do_sync_target_write().

2. bdrv_dirty_iter_next_area() handles unaligned max_offset
incorrectly:

look at the code:
    if (max_offset == iter->bitmap->size) {
        /* If max_offset points to the image end, round it up by the
         * bitmap granularity */
        gran_max_offset = ROUND_UP(max_offset, granularity);
    } else {
        gran_max_offset = max_offset;
    }

    ret = hbitmap_iter_next(&iter->hbi, false);
    if (ret < 0 || ret + granularity > gran_max_offset) {
        return false;
    }

and assume that max_offset != iter->bitmap->size but still unaligned.
if 0 < ret < max_offset we found dirty area, but the function can
return false in this case (if ret + granularity > max_offset).

3. bdrv_dirty_iter_next_area() uses inefficient loop to find the end of
the dirty area. Let's use more efficient hbitmap_next_zero instead
(bdrv_dirty_bitmap_next_dirty_area() do so)

Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
 block/mirror.c | 16 +++++++---------
 1 file changed, 7 insertions(+), 9 deletions(-)

diff --git a/block/mirror.c b/block/mirror.c
index b48c3f8cf5..d2806812c8 100644
--- a/block/mirror.c
+++ b/block/mirror.c
@@ -1167,25 +1167,22 @@ static void do_sync_target_write(MirrorBlockJob *job, MirrorMethod method,
                                  uint64_t offset, uint64_t bytes,
                                  QEMUIOVector *qiov, int flags)
 {
-    BdrvDirtyBitmapIter *iter;
     QEMUIOVector target_qiov;
-    uint64_t dirty_offset;
-    int dirty_bytes;
+    uint64_t dirty_offset = offset;
+    uint64_t dirty_bytes;
 
     if (qiov) {
         qemu_iovec_init(&target_qiov, qiov->niov);
     }
 
-    iter = bdrv_dirty_iter_new(job->dirty_bitmap);
-    bdrv_set_dirty_iter(iter, offset);
-
     while (true) {
         bool valid_area;
         int ret;
 
         bdrv_dirty_bitmap_lock(job->dirty_bitmap);
-        valid_area = bdrv_dirty_iter_next_area(iter, offset + bytes,
-                                               &dirty_offset, &dirty_bytes);
+        valid_area = bdrv_dirty_bitmap_next_dirty_area(
+            job->dirty_bitmap, &dirty_offset,
+            MIN(offset + bytes, dirty_offset + INT_MAX), &dirty_bytes);
         if (!valid_area) {
             bdrv_dirty_bitmap_unlock(job->dirty_bitmap);
             break;
@@ -1241,9 +1238,10 @@ static void do_sync_target_write(MirrorBlockJob *job, MirrorMethod method,
                 break;
             }
         }
+
+        dirty_offset += dirty_bytes;
     }
 
-    bdrv_dirty_iter_free(iter);
     if (qiov) {
         qemu_iovec_destroy(&target_qiov);
     }
-- 
2.11.1

[Qemu-devel] [PATCH v2 5/7] Revert "block/dirty-bitmap: Add bdrv_dirty_iter_next_area"

[Vladimir Sementsov-Ogievskiy]

This reverts commit 72d10a94213a954ad569095cb4491f2ae0853c40.

The function is unused now.

Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
 include/block/dirty-bitmap.h |  2 --
 block/dirty-bitmap.c         | 55 --------------------------------------------
 2 files changed, 57 deletions(-)

diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
index c02be67564..3cab01eb4c 100644
--- a/include/block/dirty-bitmap.h
+++ b/include/block/dirty-bitmap.h
@@ -83,8 +83,6 @@ void bdrv_set_dirty_bitmap_locked(BdrvDirtyBitmap *bitmap,
 void bdrv_reset_dirty_bitmap_locked(BdrvDirtyBitmap *bitmap,
                                     int64_t offset, int64_t bytes);
 int64_t bdrv_dirty_iter_next(BdrvDirtyBitmapIter *iter);
-bool bdrv_dirty_iter_next_area(BdrvDirtyBitmapIter *iter, uint64_t max_offset,
-                               uint64_t *offset, int *bytes);
 void bdrv_set_dirty_iter(BdrvDirtyBitmapIter *hbi, int64_t offset);
 int64_t bdrv_get_dirty_count(BdrvDirtyBitmap *bitmap);
 int64_t bdrv_get_meta_dirty_count(BdrvDirtyBitmap *bitmap);
diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
index c24aa0e229..35987e66a8 100644
--- a/block/dirty-bitmap.c
+++ b/block/dirty-bitmap.c
@@ -528,61 +528,6 @@ int64_t bdrv_dirty_iter_next(BdrvDirtyBitmapIter *iter)
     return hbitmap_iter_next(&iter->hbi, true);
 }
 
-/**
- * Return the next consecutively dirty area in the dirty bitmap
- * belonging to the given iterator @iter.
- *
- * @max_offset: Maximum value that may be returned for
- *              *offset + *bytes
- * @offset:     Will contain the start offset of the next dirty area
- * @bytes:      Will contain the length of the next dirty area
- *
- * Returns: True if a dirty area could be found before max_offset
- *          (which means that *offset and *bytes then contain valid
- *          values), false otherwise.
- *
- * Note that @iter is never advanced if false is returned.  If an area
- * is found (which means that true is returned), it will be advanced
- * past that area.
- */
-bool bdrv_dirty_iter_next_area(BdrvDirtyBitmapIter *iter, uint64_t max_offset,
-                               uint64_t *offset, int *bytes)
-{
-    uint32_t granularity = bdrv_dirty_bitmap_granularity(iter->bitmap);
-    uint64_t gran_max_offset;
-    int64_t ret;
-    int size;
-
-    if (max_offset == iter->bitmap->size) {
-        /* If max_offset points to the image end, round it up by the
-         * bitmap granularity */
-        gran_max_offset = ROUND_UP(max_offset, granularity);
-    } else {
-        gran_max_offset = max_offset;
-    }
-
-    ret = hbitmap_iter_next(&iter->hbi, false);
-    if (ret < 0 || ret + granularity > gran_max_offset) {
-        return false;
-    }
-
-    *offset = ret;
-    size = 0;
-
-    assert(granularity <= INT_MAX);
-
-    do {
-        /* Advance iterator */
-        ret = hbitmap_iter_next(&iter->hbi, true);
-        size += granularity;
-    } while (ret + granularity <= gran_max_offset &&
-             hbitmap_iter_next(&iter->hbi, false) == ret + granularity &&
-             size <= INT_MAX - granularity);
-
-    *bytes = MIN(size, max_offset - *offset);
-    return true;
-}
-
 /* Called within bdrv_dirty_bitmap_lock..unlock */
 void bdrv_set_dirty_bitmap_locked(BdrvDirtyBitmap *bitmap,
                                   int64_t offset, int64_t bytes)
-- 
2.11.1

[Qemu-devel] [PATCH v2 6/7] Revert "test-hbitmap: Add non-advancing iter_next tests"

[Vladimir Sementsov-Ogievskiy]

This reverts commit 269576848ec3d57d2d958cf5ac69b08c44adf816.

The functionality is unused. Drop tests.

Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
 tests/test-hbitmap.c | 36 ++++++++++++------------------------
 1 file changed, 12 insertions(+), 24 deletions(-)

diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
index c11d160633..957caa27ae 100644
--- a/tests/test-hbitmap.c
+++ b/tests/test-hbitmap.c
@@ -30,18 +30,6 @@ typedef struct TestHBitmapData {
 } TestHBitmapData;
 
 
-static int64_t check_hbitmap_iter_next(HBitmapIter *hbi)
-{
-    int next0, next1;
-
-    next0 = hbitmap_iter_next(hbi, false);
-    next1 = hbitmap_iter_next(hbi, true);
-
-    g_assert_cmpint(next0, ==, next1);
-
-    return next0;
-}
-
 /* Check that the HBitmap and the shadow bitmap contain the same data,
  * ignoring the same "first" bits.
  */
@@ -58,7 +46,7 @@ static void hbitmap_test_check(TestHBitmapData *data,
 
     i = first;
     for (;;) {
-        next = check_hbitmap_iter_next(&hbi);
+        next = hbitmap_iter_next(&hbi, true);
         if (next < 0) {
             next = data->size;
         }
@@ -447,25 +435,25 @@ static void test_hbitmap_iter_granularity(TestHBitmapData *data,
     /* Note that hbitmap_test_check has to be invoked manually in this test.  */
     hbitmap_test_init(data, 131072 << 7, 7);
     hbitmap_iter_init(&hbi, data->hb, 0);
-    g_assert_cmpint(check_hbitmap_iter_next(&hbi), <, 0);
+    g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
 
     hbitmap_test_set(data, ((L2 + L1 + 1) << 7) + 8, 8);
     hbitmap_iter_init(&hbi, data->hb, 0);
-    g_assert_cmpint(check_hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
-    g_assert_cmpint(check_hbitmap_iter_next(&hbi), <, 0);
+    g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, (L2 + L1 + 1) << 7);
+    g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
 
     hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
     g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
 
     hbitmap_test_set(data, (131072 << 7) - 8, 8);
     hbitmap_iter_init(&hbi, data->hb, 0);
-    g_assert_cmpint(check_hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
-    g_assert_cmpint(check_hbitmap_iter_next(&hbi), ==, 131071 << 7);
-    g_assert_cmpint(check_hbitmap_iter_next(&hbi), <, 0);
+    g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, (L2 + L1 + 1) << 7);
+    g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, 131071 << 7);
+    g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
 
     hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
-    g_assert_cmpint(check_hbitmap_iter_next(&hbi), ==, 131071 << 7);
-    g_assert_cmpint(check_hbitmap_iter_next(&hbi), <, 0);
+    g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, 131071 << 7);
+    g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
 }
 
 static void hbitmap_test_set_boundary_bits(TestHBitmapData *data, ssize_t diff)
@@ -905,7 +893,7 @@ static void test_hbitmap_serialize_zeroes(TestHBitmapData *data,
     for (i = 0; i < num_positions; i++) {
         hbitmap_deserialize_zeroes(data->hb, positions[i], min_l1, true);
         hbitmap_iter_init(&iter, data->hb, 0);
-        next = check_hbitmap_iter_next(&iter);
+        next = hbitmap_iter_next(&iter, true);
         if (i == num_positions - 1) {
             g_assert_cmpint(next, ==, -1);
         } else {
@@ -931,10 +919,10 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data,
 
     hbitmap_iter_init(&hbi, data->hb, BITS_PER_LONG - 1);
 
-    check_hbitmap_iter_next(&hbi);
+    hbitmap_iter_next(&hbi, true);
 
     hbitmap_reset_all(data->hb);
-    check_hbitmap_iter_next(&hbi);
+    hbitmap_iter_next(&hbi, true);
 }
 
 static void test_hbitmap_next_zero_check_range(TestHBitmapData *data,
-- 
2.11.1

[Qemu-devel] [PATCH v2 7/7] Revert "hbitmap: Add @advance param to hbitmap_iter_next()"

[Vladimir Sementsov-Ogievskiy]

This reverts commit a33fbb4f8b64226becf502a123733776ce319b24.

The functionality is unused.

Note: in addition to automatic revert, drop second parameter in
hbitmap_iter_next() call from hbitmap_next_dirty_area() too.

Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
 include/qemu/hbitmap.h |  5 +----
 block/backup.c         |  2 +-
 block/dirty-bitmap.c   |  2 +-
 tests/test-hbitmap.c   | 26 +++++++++++++-------------
 util/hbitmap.c         | 12 ++++--------
 5 files changed, 20 insertions(+), 27 deletions(-)

diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
index b1e897af28..958a6ebf03 100644
--- a/include/qemu/hbitmap.h
+++ b/include/qemu/hbitmap.h
@@ -345,14 +345,11 @@ void hbitmap_free_meta(HBitmap *hb);
 /**
  * hbitmap_iter_next:
  * @hbi: HBitmapIter to operate on.
- * @advance: If true, advance the iterator.  Otherwise, the next call
- *           of this function will return the same result (if that
- *           position is still dirty).
  *
  * Return the next bit that is set in @hbi's associated HBitmap,
  * or -1 if all remaining bits are zero.
  */
-int64_t hbitmap_iter_next(HBitmapIter *hbi, bool advance);
+int64_t hbitmap_iter_next(HBitmapIter *hbi);
 
 /**
  * hbitmap_iter_next_word:
diff --git a/block/backup.c b/block/backup.c
index 3c8b054587..5ee80e58a3 100644
--- a/block/backup.c
+++ b/block/backup.c
@@ -421,7 +421,7 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
     HBitmapIter hbi;
 
     hbitmap_iter_init(&hbi, job->copy_bitmap, 0);
-    while ((cluster = hbitmap_iter_next(&hbi, true)) != -1) {
+    while ((cluster = hbitmap_iter_next(&hbi)) != -1) {
         do {
             if (yield_and_check(job)) {
                 return 0;
diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
index 35987e66a8..c9a7887885 100644
--- a/block/dirty-bitmap.c
+++ b/block/dirty-bitmap.c
@@ -525,7 +525,7 @@ void bdrv_dirty_iter_free(BdrvDirtyBitmapIter *iter)
 
 int64_t bdrv_dirty_iter_next(BdrvDirtyBitmapIter *iter)
 {
-    return hbitmap_iter_next(&iter->hbi, true);
+    return hbitmap_iter_next(&iter->hbi);
 }
 
 /* Called within bdrv_dirty_bitmap_lock..unlock */
diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
index 957caa27ae..44a79d696d 100644
--- a/tests/test-hbitmap.c
+++ b/tests/test-hbitmap.c
@@ -46,7 +46,7 @@ static void hbitmap_test_check(TestHBitmapData *data,
 
     i = first;
     for (;;) {
-        next = hbitmap_iter_next(&hbi, true);
+        next = hbitmap_iter_next(&hbi);
         if (next < 0) {
             next = data->size;
         }
@@ -435,25 +435,25 @@ static void test_hbitmap_iter_granularity(TestHBitmapData *data,
     /* Note that hbitmap_test_check has to be invoked manually in this test.  */
     hbitmap_test_init(data, 131072 << 7, 7);
     hbitmap_iter_init(&hbi, data->hb, 0);
-    g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
+    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
 
     hbitmap_test_set(data, ((L2 + L1 + 1) << 7) + 8, 8);
     hbitmap_iter_init(&hbi, data->hb, 0);
-    g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, (L2 + L1 + 1) << 7);
-    g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
+    g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
+    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
 
     hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
-    g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
+    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
 
     hbitmap_test_set(data, (131072 << 7) - 8, 8);
     hbitmap_iter_init(&hbi, data->hb, 0);
-    g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, (L2 + L1 + 1) << 7);
-    g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, 131071 << 7);
-    g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
+    g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
+    g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
+    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
 
     hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
-    g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, 131071 << 7);
-    g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
+    g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
+    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
 }
 
 static void hbitmap_test_set_boundary_bits(TestHBitmapData *data, ssize_t diff)
@@ -893,7 +893,7 @@ static void test_hbitmap_serialize_zeroes(TestHBitmapData *data,
     for (i = 0; i < num_positions; i++) {
         hbitmap_deserialize_zeroes(data->hb, positions[i], min_l1, true);
         hbitmap_iter_init(&iter, data->hb, 0);
-        next = hbitmap_iter_next(&iter, true);
+        next = hbitmap_iter_next(&iter);
         if (i == num_positions - 1) {
             g_assert_cmpint(next, ==, -1);
         } else {
@@ -919,10 +919,10 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data,
 
     hbitmap_iter_init(&hbi, data->hb, BITS_PER_LONG - 1);
 
-    hbitmap_iter_next(&hbi, true);
+    hbitmap_iter_next(&hbi);
 
     hbitmap_reset_all(data->hb);
-    hbitmap_iter_next(&hbi, true);
+    hbitmap_iter_next(&hbi);
 }
 
 static void test_hbitmap_next_zero_check_range(TestHBitmapData *data,
diff --git a/util/hbitmap.c b/util/hbitmap.c
index 9de0d7bf2d..5c2c4deef1 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -144,7 +144,7 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi)
     return cur;
 }
 
-int64_t hbitmap_iter_next(HBitmapIter *hbi, bool advance)
+int64_t hbitmap_iter_next(HBitmapIter *hbi)
 {
     unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1] &
             hbi->hb->levels[HBITMAP_LEVELS - 1][hbi->pos];
@@ -157,12 +157,8 @@ int64_t hbitmap_iter_next(HBitmapIter *hbi, bool advance)
         }
     }
 
-    if (advance) {
-        /* The next call will resume work from the next bit.  */
-        hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1);
-    } else {
-        hbi->cur[HBITMAP_LEVELS - 1] = cur;
-    }
+    /* The next call will resume work from the next bit.  */
+    hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1);
     item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + ctzl(cur);
 
     return item << hbi->granularity;
@@ -256,7 +252,7 @@ bool hbitmap_next_dirty_area(const HBitmap *hb, uint64_t *offset,
     }
 
     hbitmap_iter_init(&hbi, hb, *offset << hb->granularity);
-    off1 = hbitmap_iter_next(&hbi, true);
+    off1 = hbitmap_iter_next(&hbi);
 
     if (off1 < 0 || off1 >= end) {
         return false;
-- 
2.11.1

Re: [Qemu-devel] [PATCH v2 3/7] dirty-bitmap: add bdrv_dirty_bitmap_next_dirty_area

[Vladimir Sementsov-Ogievskiy]

08.08.2018 15:49, Vladimir Sementsov-Ogievskiy wrote:
> The function alters bdrv_dirty_iter_next_area(), which is wrong and
> less efficient (see next commit for description).
>
> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> ---
>   include/block/dirty-bitmap.h |  3 +++
>   include/qemu/hbitmap.h       | 15 +++++++++++++++
>   block/dirty-bitmap.c         |  7 +++++++
>   util/hbitmap.c               | 38 ++++++++++++++++++++++++++++++++++++++
>   4 files changed, 63 insertions(+)
>
> diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
> index 5dc146abf3..c02be67564 100644
> --- a/include/block/dirty-bitmap.h
> +++ b/include/block/dirty-bitmap.h
> @@ -100,6 +100,9 @@ BdrvDirtyBitmap *bdrv_dirty_bitmap_next(BlockDriverState *bs,
>   char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp);
>   int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start,
>                                       uint64_t bytes);
> +bool bdrv_dirty_bitmap_next_dirty_area(BdrvDirtyBitmap *bitmap,
> +                                       uint64_t *offset, uint64_t end,
> +                                       uint64_t *length);
>   BdrvDirtyBitmap *bdrv_reclaim_dirty_bitmap_locked(BlockDriverState *bs,
>                                                     BdrvDirtyBitmap *bitmap,
>                                                     Error **errp);
> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
> index cd091f6134..b1e897af28 100644
> --- a/include/qemu/hbitmap.h
> +++ b/include/qemu/hbitmap.h
> @@ -306,6 +306,21 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
>    */
>   int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t count);
>   
> +/* hbitmap_next_dirty_area:
> + * @hb: The HBitmap to operate on
> + * @offset: in-out parameter.
> + *          in: the offset to start from
> + *          out: (if area found) start of found area
> + * @end: end of requested region. (*@offset + *@length) will be <= @end
> + * @length: length of found area
> + *
> + * If dirty area found within [@offset, @end), returns true and sets @offset
> + * and @length appropriately. Otherwise returns true and leaves @offset and
> + * @length unchanged.
> + */
> +bool hbitmap_next_dirty_area(const HBitmap *hb, uint64_t *offset,
> +                             uint64_t end, uint64_t *length);
> +
>   /* hbitmap_create_meta:
>    * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap.
>    * The caller owns the created bitmap and must call hbitmap_free_meta(hb) to
> diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
> index a9ee814da7..c24aa0e229 100644
> --- a/block/dirty-bitmap.c
> +++ b/block/dirty-bitmap.c
> @@ -791,6 +791,13 @@ int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset,
>       return hbitmap_next_zero(bitmap->bitmap, offset, bytes);
>   }
>   
> +bool bdrv_dirty_bitmap_next_dirty_area(BdrvDirtyBitmap *bitmap,
> +                                       uint64_t *offset, uint64_t end,
> +                                       uint64_t *length)
> +{
> +    return hbitmap_next_dirty_area(bitmap->bitmap, offset, end, length);
> +}
> +
>   void bdrv_merge_dirty_bitmap(BdrvDirtyBitmap *dest, const BdrvDirtyBitmap *src,
>                                Error **errp)
>   {
> diff --git a/util/hbitmap.c b/util/hbitmap.c
> index 8dbcd80a3d..9de0d7bf2d 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -244,6 +244,44 @@ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t count)
>       return res;
>   }
>   
> +bool hbitmap_next_dirty_area(const HBitmap *hb, uint64_t *offset,
> +                             uint64_t end, uint64_t *length)
> +{
> +    HBitmapIter hbi;
> +    int64_t off1, off0;
> +    uint32_t granularity = 1UL << hb->granularity;
> +
> +    if (end == 0) {
> +        end = hb->orig_size;
> +    }
> +
> +    hbitmap_iter_init(&hbi, hb, *offset << hb->granularity);

"<< hb->granularity" should be dropped. Hmm, this patch needs tests.

> +    off1 = hbitmap_iter_next(&hbi, true);
> +
> +    if (off1 < 0 || off1 >= end) {
> +        return false;
> +    }
> +
> +    if (off1 + granularity >= end) {
> +        if (off1 > *offset) {
> +            *offset = off1;
> +        }
> +        *length = end - *offset;
> +        return true;
> +    }
> +
> +    off0 = hbitmap_next_zero(hb, off1 + granularity, end);
> +    if (off0 < 0) {
> +        off0 = end;
> +    }
> +
> +    if (off1 > *offset) {
> +        *offset = off1;
> +    }
> +    *length = off0 - *offset;
> +    return true;
> +}
> +
>   bool hbitmap_empty(const HBitmap *hb)
>   {
>       return hb->count == 0;


-- 
Best regards,
Vladimir

Re: [Qemu-devel] [PATCH v2 3/7] dirty-bitmap: add bdrv_dirty_bitmap_next_dirty_area

[Vladimir Sementsov-Ogievskiy]

10.08.2018 20:05, Vladimir Sementsov-Ogievskiy wrote:
> 08.08.2018 15:49, Vladimir Sementsov-Ogievskiy wrote:
>> The function alters bdrv_dirty_iter_next_area(), which is wrong and
>> less efficient (see next commit for description).
>>
>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>> ---
>>   include/block/dirty-bitmap.h |  3 +++
>>   include/qemu/hbitmap.h       | 15 +++++++++++++++
>>   block/dirty-bitmap.c         |  7 +++++++
>>   util/hbitmap.c               | 38 
>> ++++++++++++++++++++++++++++++++++++++
>>   4 files changed, 63 insertions(+)
>>
>> diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
>> index 5dc146abf3..c02be67564 100644
>> --- a/include/block/dirty-bitmap.h
>> +++ b/include/block/dirty-bitmap.h
>> @@ -100,6 +100,9 @@ BdrvDirtyBitmap 
>> *bdrv_dirty_bitmap_next(BlockDriverState *bs,
>>   char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error 
>> **errp);
>>   int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, 
>> uint64_t start,
>>                                       uint64_t bytes);
>> +bool bdrv_dirty_bitmap_next_dirty_area(BdrvDirtyBitmap *bitmap,
>> +                                       uint64_t *offset, uint64_t end,
>> +                                       uint64_t *length);
>>   BdrvDirtyBitmap *bdrv_reclaim_dirty_bitmap_locked(BlockDriverState 
>> *bs,
>> BdrvDirtyBitmap *bitmap,
>>                                                     Error **errp);
>> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
>> index cd091f6134..b1e897af28 100644
>> --- a/include/qemu/hbitmap.h
>> +++ b/include/qemu/hbitmap.h
>> @@ -306,6 +306,21 @@ unsigned long 
>> hbitmap_iter_skip_words(HBitmapIter *hbi);
>>    */
>>   int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, 
>> uint64_t count);
>>   +/* hbitmap_next_dirty_area:
>> + * @hb: The HBitmap to operate on
>> + * @offset: in-out parameter.
>> + *          in: the offset to start from
>> + *          out: (if area found) start of found area
>> + * @end: end of requested region. (*@offset + *@length) will be <= @end
>> + * @length: length of found area
>> + *
>> + * If dirty area found within [@offset, @end), returns true and sets 
>> @offset
>> + * and @length appropriately. Otherwise returns true and leaves 
>> @offset and
>> + * @length unchanged.
>> + */
>> +bool hbitmap_next_dirty_area(const HBitmap *hb, uint64_t *offset,
>> +                             uint64_t end, uint64_t *length);
>> +
>>   /* hbitmap_create_meta:
>>    * Create a "meta" hbitmap to track dirtiness of the bits in this 
>> HBitmap.
>>    * The caller owns the created bitmap and must call 
>> hbitmap_free_meta(hb) to
>> diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
>> index a9ee814da7..c24aa0e229 100644
>> --- a/block/dirty-bitmap.c
>> +++ b/block/dirty-bitmap.c
>> @@ -791,6 +791,13 @@ int64_t 
>> bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset,
>>       return hbitmap_next_zero(bitmap->bitmap, offset, bytes);
>>   }
>>   +bool bdrv_dirty_bitmap_next_dirty_area(BdrvDirtyBitmap *bitmap,
>> +                                       uint64_t *offset, uint64_t end,
>> +                                       uint64_t *length)
>> +{
>> +    return hbitmap_next_dirty_area(bitmap->bitmap, offset, end, 
>> length);
>> +}
>> +
>>   void bdrv_merge_dirty_bitmap(BdrvDirtyBitmap *dest, const 
>> BdrvDirtyBitmap *src,
>>                                Error **errp)
>>   {
>> diff --git a/util/hbitmap.c b/util/hbitmap.c
>> index 8dbcd80a3d..9de0d7bf2d 100644
>> --- a/util/hbitmap.c
>> +++ b/util/hbitmap.c
>> @@ -244,6 +244,44 @@ int64_t hbitmap_next_zero(const HBitmap *hb, 
>> uint64_t start, uint64_t count)
>>       return res;
>>   }
>>   +bool hbitmap_next_dirty_area(const HBitmap *hb, uint64_t *offset,
>> +                             uint64_t end, uint64_t *length)
>> +{
>> +    HBitmapIter hbi;
>> +    int64_t off1, off0;
>> +    uint32_t granularity = 1UL << hb->granularity;
>> +
>> +    if (end == 0) {
>> +        end = hb->orig_size;
>> +    }
>> +
>> +    hbitmap_iter_init(&hbi, hb, *offset << hb->granularity);
>
> "<< hb->granularity" should be dropped. Hmm, this patch needs tests.
>
>> +    off1 = hbitmap_iter_next(&hbi, true);
>> +
>> +    if (off1 < 0 || off1 >= end) {
>> +        return false;
>> +    }
>> +
>> +    if (off1 + granularity >= end) {
>> +        if (off1 > *offset) {
>> +            *offset = off1;
>> +        }
>> +        *length = end - *offset;
>> +        return true;
>> +    }
>> +
>> +    off0 = hbitmap_next_zero(hb, off1 + granularity, end);

-    off0 = hbitmap_next_zero(hb, off1 + granularity, end);
+    off0 = hbitmap_next_zero(hb, off1 + granularity, end - off1 - 
granularity);


>> +    if (off0 < 0) {
>> +        off0 = end;
>> +    }
>> +
>> +    if (off1 > *offset) {
>> +        *offset = off1;
>> +    }
>> +    *length = off0 - *offset;
>> +    return true;
>> +}
>> +
>>   bool hbitmap_empty(const HBitmap *hb)
>>   {
>>       return hb->count == 0;
>
>


-- 
Best regards,
Vladimir