The function alters bdrv_dirty_iter_next_area(), which is wrong and
less efficient (see further commit
"block/mirror: fix and improve do_sync_target_write" for description).

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

diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
index 1a23c76862..7ad2a1357a 100644
--- a/include/block/dirty-bitmap.h
+++ b/include/block/dirty-bitmap.h
@@ -100,6 +100,8 @@ 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 offset,
                                     uint64_t bytes);
+bool bdrv_dirty_bitmap_next_dirty_area(BdrvDirtyBitmap *bitmap,
+                                       uint64_t *offset, 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 8a399c1c9c..495a99e78e 100644
--- a/include/qemu/hbitmap.h
+++ b/include/qemu/hbitmap.h
@@ -304,6 +304,22 @@ 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
+ * @start: in-out parameter.
+ *         in: the offset to start from
+ *         out: (if area found) start of found area
+ * @count: in-out parameter.
+ *         in: length of requested region
+ *         out: length of found area
+ *
+ * If dirty area found within [@start, @start + @count), returns true and sets
+ * @offset and @bytes appropriately. Otherwise returns false and leaves @offset
+ * and @bytes unchanged.
+ */
+bool hbitmap_next_dirty_area(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.
  * 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..7ee8b27368 100644
--- a/block/dirty-bitmap.c
+++ b/block/dirty-bitmap.c
@@ -791,6 +791,12 @@ 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 *bytes)
+{
+    return hbitmap_next_dirty_area(bitmap->bitmap, offset, bytes);
+}
+
 void bdrv_merge_dirty_bitmap(BdrvDirtyBitmap *dest, const BdrvDirtyBitmap *src,
                              Error **errp)
 {
diff --git a/util/hbitmap.c b/util/hbitmap.c
index a18c68fb2f..5beca86740 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -246,6 +246,45 @@ 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 *start,
+                             uint64_t *count)
+{
+    HBitmapIter hbi;
+    int64_t firt_dirty_off, area_end;
+    uint32_t granularity = 1UL << hb->granularity;
+    uint64_t end;
+
+    if (*start >= hb->orig_size || *count == 0) {
+        return false;
+    }
+
+    end = *count > hb->orig_size - *start ? hb->orig_size : *start + *count;
+
+    hbitmap_iter_init(&hbi, hb, *start);
+    firt_dirty_off = hbitmap_iter_next(&hbi, false);
+
+    if (firt_dirty_off < 0 || firt_dirty_off >= end) {
+        return false;
+    }
+
+    if (firt_dirty_off + granularity >= end) {
+        area_end = end;
+    } else {
+        area_end = hbitmap_next_zero(hb, firt_dirty_off + granularity,
+                                     end - firt_dirty_off - granularity);
+        if (area_end < 0) {
+            area_end = end;
+        }
+    }
+
+    if (firt_dirty_off > *start) {
+        *start = firt_dirty_off;
+    }
+    *count = area_end - *start;
+
+    return true;
+}
+
 bool hbitmap_empty(const HBitmap *hb)
 {
     return hb->count == 0;
-- 
2.18.0

On 09/17/2018 10:57 AM, Vladimir Sementsov-Ogievskiy wrote:
> The function alters bdrv_dirty_iter_next_area(), which is wrong and
> less efficient (see further commit
> "block/mirror: fix and improve do_sync_target_write" for description).
> 
> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> ---
>  include/block/dirty-bitmap.h |  2 ++
>  include/qemu/hbitmap.h       | 16 +++++++++++++++
>  block/dirty-bitmap.c         |  6 ++++++
>  util/hbitmap.c               | 39 ++++++++++++++++++++++++++++++++++++
>  4 files changed, 63 insertions(+)
> 
> diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
> index 1a23c76862..7ad2a1357a 100644
> --- a/include/block/dirty-bitmap.h
> +++ b/include/block/dirty-bitmap.h
> @@ -100,6 +100,8 @@ 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 offset,
>                                      uint64_t bytes);
> +bool bdrv_dirty_bitmap_next_dirty_area(BdrvDirtyBitmap *bitmap,
> +                                       uint64_t *offset, 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 8a399c1c9c..495a99e78e 100644
> --- a/include/qemu/hbitmap.h
> +++ b/include/qemu/hbitmap.h
> @@ -304,6 +304,22 @@ 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
> + * @start: in-out parameter.
> + *         in: the offset to start from
> + *         out: (if area found) start of found area
> + * @count: in-out parameter.
> + *         in: length of requested region
> + *         out: length of found area
> + *
> + * If dirty area found within [@start, @start + @count), returns true and sets
> + * @offset and @bytes appropriately. Otherwise returns false and leaves @offset
> + * and @bytes unchanged.
> + */
> +bool hbitmap_next_dirty_area(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.
>   * 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..7ee8b27368 100644
> --- a/block/dirty-bitmap.c
> +++ b/block/dirty-bitmap.c
> @@ -791,6 +791,12 @@ 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 *bytes)
> +{
> +    return hbitmap_next_dirty_area(bitmap->bitmap, offset, bytes);
> +}
> +
>  void bdrv_merge_dirty_bitmap(BdrvDirtyBitmap *dest, const BdrvDirtyBitmap *src,
>                               Error **errp)
>  {
> diff --git a/util/hbitmap.c b/util/hbitmap.c
> index a18c68fb2f..5beca86740 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -246,6 +246,45 @@ 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 *start,
> +                             uint64_t *count)
> +{
> +    HBitmapIter hbi;
> +    int64_t firt_dirty_off, area_end;

firt? first? please spell this out.

with that:

Reviewed-by: John Snow <jsnow@redhat.com>

> +    uint32_t granularity = 1UL << hb->granularity;
> +    uint64_t end;
> +
> +    if (*start >= hb->orig_size || *count == 0) {
> +        return false;
> +    }
> +
> +    end = *count > hb->orig_size - *start ? hb->orig_size : *start + *count;
> +
> +    hbitmap_iter_init(&hbi, hb, *start);
> +    firt_dirty_off = hbitmap_iter_next(&hbi, false);
> +
> +    if (firt_dirty_off < 0 || firt_dirty_off >= end) {
> +        return false;
> +    }
> +
> +    if (firt_dirty_off + granularity >= end) {
> +        area_end = end;
> +    } else {
> +        area_end = hbitmap_next_zero(hb, firt_dirty_off + granularity,
> +                                     end - firt_dirty_off - granularity);
> +        if (area_end < 0) {
> +            area_end = end;
> +        }
> +    }
> +
> +    if (firt_dirty_off > *start) {
> +        *start = firt_dirty_off;
> +    }
> +    *count = area_end - *start;
> +
> +    return true;
> +}
> +
>  bool hbitmap_empty(const HBitmap *hb)
>  {
>      return hb->count == 0;
>