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

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

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