Signed-off-by: John Snow <jsnow@redhat.com>
---
 util/hbitmap.c | 22 +++++++++++++++++++++-
 1 file changed, 21 insertions(+), 1 deletion(-)

diff --git a/util/hbitmap.c b/util/hbitmap.c
index 45d1725daf..0d6724b7bc 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -777,7 +777,17 @@ void hbitmap_truncate(HBitmap *hb, uint64_t size)
 
 bool hbitmap_can_merge(const HBitmap *a, const HBitmap *b)
 {
-    return (a->size == b->size) && (a->granularity == b->granularity);
+    return (a->size == b->size);
+}
+
+static void hbitmap_sparse_merge(HBitmap *dst, const HBitmap *src)
+{
+    uint64_t offset = 0;
+    uint64_t count = src->orig_size;
+
+    while (hbitmap_next_dirty_area(src, &offset, &count)) {
+        hbitmap_set(dst, offset, count);
+    }
 }
 
 /**
@@ -804,6 +814,16 @@ bool hbitmap_merge(const HBitmap *a, const HBitmap *b, HBitmap *result)
         return true;
     }
 
+    if (a->size != b->size) {
+        if (a != result) {
+            hbitmap_sparse_merge(result, a);
+        }
+        if (b != result) {
+            hbitmap_sparse_merge(result, b);
+        }
+        return true;
+    }
+
     /* This merge is O(size), as BITS_PER_LONG and HBITMAP_LEVELS are constant.
      * It may be possible to improve running times for sparsely populated maps
      * by using hbitmap_iter_next, but this is suboptimal for dense maps.
-- 
2.21.0

On 20.06.19 03:03, John Snow wrote:
> Signed-off-by: John Snow <jsnow@redhat.com>
> ---
>  util/hbitmap.c | 22 +++++++++++++++++++++-
>  1 file changed, 21 insertions(+), 1 deletion(-)

I wonder whether this could be used in
backup_incremental_init_copy_bitmap().  The sync_bitmap must have the
same length as the source BDS, right?

Max

20.06.2019 19:47, Max Reitz wrote:
> On 20.06.19 03:03, John Snow wrote:
>> Signed-off-by: John Snow <jsnow@redhat.com>
>> ---
>>   util/hbitmap.c | 22 +++++++++++++++++++++-
>>   1 file changed, 21 insertions(+), 1 deletion(-)
> 
> I wonder whether this could be used in
> backup_incremental_init_copy_bitmap().  The sync_bitmap must have the
> same length as the source BDS, right?
> 

A little problem here is that in backup code we merge BdrvDirtyBitmap into
HBitmap, so hbitmap API can't be directly used here, and to avoid code
duplication we need to create a bit strange interface of merging exactly
BdrvDirtyBitmap into HBitmap.. But, anyway it's better than code duplication.

Yes, they should have the same length.

But we may allow at least merging smaller bitmap into larger, why not?

-- 
Best regards,
Vladimir

20.06.2019 4:03, John Snow wrote:
> Signed-off-by: John Snow <jsnow@redhat.com>
> ---
>   util/hbitmap.c | 22 +++++++++++++++++++++-
>   1 file changed, 21 insertions(+), 1 deletion(-)
> 
> diff --git a/util/hbitmap.c b/util/hbitmap.c
> index 45d1725daf..0d6724b7bc 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -777,7 +777,17 @@ void hbitmap_truncate(HBitmap *hb, uint64_t size)
>   
>   bool hbitmap_can_merge(const HBitmap *a, const HBitmap *b)
>   {
> -    return (a->size == b->size) && (a->granularity == b->granularity);
> +    return (a->size == b->size);
> +}
> +
> +static void hbitmap_sparse_merge(HBitmap *dst, const HBitmap *src)
> +{
> +    uint64_t offset = 0;
> +    uint64_t count = src->orig_size;
> +
> +    while (hbitmap_next_dirty_area(src, &offset, &count)) {
> +        hbitmap_set(dst, offset, count);

This will not work, as hbitmap_next_dirty_area will return the same answer all the time I think.
You need to update offset and count in a loop, like it is done in backup_incremental_init_copy_bitmap.


> +    }
>   }
>   
>   /**
> @@ -804,6 +814,16 @@ bool hbitmap_merge(const HBitmap *a, const HBitmap *b, HBitmap *result)
>           return true;
>       }
>   
> +    if (a->size != b->size) {
> +        if (a != result) {
> +            hbitmap_sparse_merge(result, a);
> +        }
> +        if (b != result) {
> +            hbitmap_sparse_merge(result, b);
> +        }
> +        return true;
> +    }
> +
>       /* This merge is O(size), as BITS_PER_LONG and HBITMAP_LEVELS are constant.
>        * It may be possible to improve running times for sparsely populated maps
>        * by using hbitmap_iter_next, but this is suboptimal for dense maps.
> 


-- 
Best regards,
Vladimir

On 20.06.19 03:03, John Snow wrote:
> Signed-off-by: John Snow <jsnow@redhat.com>
> ---
>  util/hbitmap.c | 22 +++++++++++++++++++++-
>  1 file changed, 21 insertions(+), 1 deletion(-)
> 
> diff --git a/util/hbitmap.c b/util/hbitmap.c
> index 45d1725daf..0d6724b7bc 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -777,7 +777,17 @@ void hbitmap_truncate(HBitmap *hb, uint64_t size)
>  
>  bool hbitmap_can_merge(const HBitmap *a, const HBitmap *b)
>  {
> -    return (a->size == b->size) && (a->granularity == b->granularity);
> +    return (a->size == b->size);
> +}
> +
> +static void hbitmap_sparse_merge(HBitmap *dst, const HBitmap *src)
> +{
> +    uint64_t offset = 0;
> +    uint64_t count = src->orig_size;
> +
> +    while (hbitmap_next_dirty_area(src, &offset, &count)) {
> +        hbitmap_set(dst, offset, count);
> +    }
>  }
>  
>  /**
> @@ -804,6 +814,16 @@ bool hbitmap_merge(const HBitmap *a, const HBitmap *b, HBitmap *result)
>          return true;
>      }
>  
> +    if (a->size != b->size) {

Don’t you mean s/size/granularity/?

Right now, this is dead code, which leads me to asking for a test.
(Well, no, I would’ve asked anyway.)

Max

> +        if (a != result) {
> +            hbitmap_sparse_merge(result, a);
> +        }
> +        if (b != result) {
> +            hbitmap_sparse_merge(result, b);
> +        }
> +        return true;
> +    }
> +
>      /* This merge is O(size), as BITS_PER_LONG and HBITMAP_LEVELS are constant.
>       * It may be possible to improve running times for sparsely populated maps
>       * by using hbitmap_iter_next, but this is suboptimal for dense maps.
> 

On 6/20/19 11:47 AM, Max Reitz wrote:
> On 20.06.19 03:03, John Snow wrote:
>> Signed-off-by: John Snow <jsnow@redhat.com>
>> ---
>>  util/hbitmap.c | 22 +++++++++++++++++++++-
>>  1 file changed, 21 insertions(+), 1 deletion(-)
>>
>> diff --git a/util/hbitmap.c b/util/hbitmap.c
>> index 45d1725daf..0d6724b7bc 100644
>> --- a/util/hbitmap.c
>> +++ b/util/hbitmap.c
>> @@ -777,7 +777,17 @@ void hbitmap_truncate(HBitmap *hb, uint64_t size)
>>  
>>  bool hbitmap_can_merge(const HBitmap *a, const HBitmap *b)
>>  {
>> -    return (a->size == b->size) && (a->granularity == b->granularity);
>> +    return (a->size == b->size);
>> +}
>> +
>> +static void hbitmap_sparse_merge(HBitmap *dst, const HBitmap *src)
>> +{
>> +    uint64_t offset = 0;
>> +    uint64_t count = src->orig_size;
>> +
>> +    while (hbitmap_next_dirty_area(src, &offset, &count)) {
>> +        hbitmap_set(dst, offset, count);
>> +    }
>>  }
>>  
>>  /**
>> @@ -804,6 +814,16 @@ bool hbitmap_merge(const HBitmap *a, const HBitmap *b, HBitmap *result)
>>          return true;
>>      }
>>  
>> +    if (a->size != b->size) {
> 
> Don’t you mean s/size/granularity/?
> 
> Right now, this is dead code, which leads me to asking for a test.
> (Well, no, I would’ve asked anyway.)
> 
> Max
> 

Ah, crud. Caught red-handed. Yes and Yes.

As to your later question: Can we use this for backup initialization?
Also yes; but it might be the case that we want the copy bitmap to
become a full-fledged "bdrv dirty bitmap" instead of an hbitmap, which
will actually make this easier and probably eliminate the need for the
"_take" or "_claim" function I added, too.