[Qemu-devel] [PATCH v2] bitmap: Update count after a merge

[Qemu-devel] [PATCH v2] bitmap: Update count after a merge

[John Snow]

From: Eric Blake <eblake@redhat.com>

We need an accurate count of the number of bits set in a bitmap
after a merge. In particular, since the merge operation short-circuits
a merge from an empty source, if you have bitmaps A, B, and C where
B started empty, then merge C into B, and B into A, an inaccurate
count meant that A did not get the contents of C.

In the worst case, we may falsely regard the bitmap as empty when
it has had new writes merged into it.

Fixes: be58721db
CC: qemu-stable@nongnu.org
Signed-off-by: Eric Blake <eblake@redhat.com>
Signed-off-by: John Snow <jsnow@redhat.com>
---

v2: based off of Eric's cover letter, now rebased properly
    on top of the jsnow/bitmaps staging branch to use the
    correct bitmap target (result).


 util/hbitmap.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/util/hbitmap.c b/util/hbitmap.c
index d5aca5159f..8d402c59d9 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -759,6 +759,9 @@ bool hbitmap_merge(const HBitmap *a, const HBitmap *b, HBitmap *result)
         }
     }
 
+    /* Recompute the dirty count */
+    result->count = hb_count_between(result, 0, result->size - 1);
+
     return true;
 }
 
-- 
2.14.4

Re: [Qemu-devel] [PATCH v2] bitmap: Update count after a merge

[Vladimir Sementsov-Ogievskiy]

03.10.2018 02:33, John Snow wrote:
> From: Eric Blake <eblake@redhat.com>
>
> We need an accurate count of the number of bits set in a bitmap
> after a merge. In particular, since the merge operation short-circuits
> a merge from an empty source, if you have bitmaps A, B, and C where
> B started empty, then merge C into B, and B into A, an inaccurate
> count meant that A did not get the contents of C.
>
> In the worst case, we may falsely regard the bitmap as empty when
> it has had new writes merged into it.
>
> Fixes: be58721db
> CC: qemu-stable@nongnu.org
> Signed-off-by: Eric Blake <eblake@redhat.com>
> Signed-off-by: John Snow <jsnow@redhat.com>

Reviewed-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>

Hm, I rememberd:
commit 3260cdfffbf00f33923f5f9f6bef45932d7ac28b
Author: Liang Li <liliangleo@didichuxing.com>
Date:   Wed Feb 7 11:35:49 2018 -0500

     hbitmap: fix missing restore count when finish deserialization

     The .count of HBitmap is forgot to set in function
     hbitmap_deserialize_finish, let's set it to the right value.


  - I always forget to update this field.. We definitely should add some 
generic check on it somewhere, at least in tests.

> ---
>
> v2: based off of Eric's cover letter, now rebased properly
>      on top of the jsnow/bitmaps staging branch to use the
>      correct bitmap target (result).
>
>
>   util/hbitmap.c | 3 +++
>   1 file changed, 3 insertions(+)
>
> diff --git a/util/hbitmap.c b/util/hbitmap.c
> index d5aca5159f..8d402c59d9 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -759,6 +759,9 @@ bool hbitmap_merge(const HBitmap *a, const HBitmap *b, HBitmap *result)
>           }
>       }
>   
> +    /* Recompute the dirty count */
> +    result->count = hb_count_between(result, 0, result->size - 1);
> +
>       return true;
>   }
>   


-- 
Best regards,
Vladimir

Re: [Qemu-devel] [PATCH v2] bitmap: Update count after a merge

[Eric Blake]

On 10/3/18 9:32 AM, Vladimir Sementsov-Ogievskiy wrote:
> 03.10.2018 02:33, John Snow wrote:
>> From: Eric Blake <eblake@redhat.com>
>>
>> We need an accurate count of the number of bits set in a bitmap
>> after a merge. In particular, since the merge operation short-circuits
>> a merge from an empty source, if you have bitmaps A, B, and C where
>> B started empty, then merge C into B, and B into A, an inaccurate
>> count meant that A did not get the contents of C.
>>
>> In the worst case, we may falsely regard the bitmap as empty when
>> it has had new writes merged into it.
>>
>> Fixes: be58721db
>> CC: qemu-stable@nongnu.org
>> Signed-off-by: Eric Blake <eblake@redhat.com>
>> Signed-off-by: John Snow <jsnow@redhat.com>
> 
> Reviewed-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> 
> Hm, I rememberd:
> commit 3260cdfffbf00f33923f5f9f6bef45932d7ac28b
> Author: Liang Li <liliangleo@didichuxing.com>
> Date:   Wed Feb 7 11:35:49 2018 -0500
> 
>       hbitmap: fix missing restore count when finish deserialization
> 
>       The .count of HBitmap is forgot to set in function
>       hbitmap_deserialize_finish, let's set it to the right value.
> 
> 
>    - I always forget to update this field.. We definitely should add some
> generic check on it somewhere, at least in tests.

My suggestion (in another thread) was to enhance 
x-debug-block-dirty-bitmap-sha256 to include 'count' alongside the 
checksum, to make it easier to write such tests.

-- 
Eric Blake, Principal Software Engineer
Red Hat, Inc.           +1-919-301-3266
Virtualization:  qemu.org | libvirt.org

Re: [Qemu-devel] [PATCH v2] bitmap: Update count after a merge

[John Snow]

On 10/03/2018 10:49 AM, Eric Blake wrote:
> On 10/3/18 9:32 AM, Vladimir Sementsov-Ogievskiy wrote:
>> 03.10.2018 02:33, John Snow wrote:
>>> From: Eric Blake <eblake@redhat.com>
>>>
>>> We need an accurate count of the number of bits set in a bitmap
>>> after a merge. In particular, since the merge operation short-circuits
>>> a merge from an empty source, if you have bitmaps A, B, and C where
>>> B started empty, then merge C into B, and B into A, an inaccurate
>>> count meant that A did not get the contents of C.
>>>
>>> In the worst case, we may falsely regard the bitmap as empty when
>>> it has had new writes merged into it.
>>>
>>> Fixes: be58721db
>>> CC: qemu-stable@nongnu.org
>>> Signed-off-by: Eric Blake <eblake@redhat.com>
>>> Signed-off-by: John Snow <jsnow@redhat.com>
>>
>> Reviewed-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>>
>> Hm, I rememberd:
>> commit 3260cdfffbf00f33923f5f9f6bef45932d7ac28b
>> Author: Liang Li <liliangleo@didichuxing.com>
>> Date:   Wed Feb 7 11:35:49 2018 -0500
>>
>>       hbitmap: fix missing restore count when finish deserialization
>>
>>       The .count of HBitmap is forgot to set in function
>>       hbitmap_deserialize_finish, let's set it to the right value.
>>
>>
>>    - I always forget to update this field.. We definitely should add some
>> generic check on it somewhere, at least in tests.
> 
> My suggestion (in another thread) was to enhance
> x-debug-block-dirty-bitmap-sha256 to include 'count' alongside the
> checksum, to make it easier to write such tests.
> 

I suppose this is in preference to query-block? It would make it easier.

--js

Re: [Qemu-devel] [PATCH v2] bitmap: Update count after a merge

[Eric Blake]

On 10/3/18 2:57 PM, John Snow wrote:

>>>     - I always forget to update this field.. We definitely should add some
>>> generic check on it somewhere, at least in tests.
>>
>> My suggestion (in another thread) was to enhance
>> x-debug-block-dirty-bitmap-sha256 to include 'count' alongside the
>> checksum, to make it easier to write such tests.
>>
> 
> I suppose this is in preference to query-block? It would make it easier.

Well, query-block remains the canonical way for users to access the 
count, while x-debug-block-dirty-bitmap-sha256 is for debugging only 
(basically, for our unit tests, as no one outside of qemu will get much 
use out of it).  But yes, writing a test that uses bitmaps on an 
unconnected BDS is easier than a test that has to use a named device, 
since query-block won't list nodes that aren't connected to a named 
device, and requires a lot more parsing to get at the actual bitmap 
information in comparison to the debug command directly telling you 
about a single bitmap.

-- 
Eric Blake, Principal Software Engineer
Red Hat, Inc.           +1-919-301-3266
Virtualization:  qemu.org | libvirt.org

Re: [Qemu-devel] [PATCH v2] bitmap: Update count after a merge

[Vladimir Sementsov-Ogievskiy]

03.10.2018 23:01, Eric Blake wrote:
> On 10/3/18 2:57 PM, John Snow wrote:
>
>>>>     - I always forget to update this field.. We definitely should 
>>>> add some
>>>> generic check on it somewhere, at least in tests.
>>>
>>> My suggestion (in another thread) was to enhance
>>> x-debug-block-dirty-bitmap-sha256 to include 'count' alongside the
>>> checksum, to make it easier to write such tests.
>>>
>>
>> I suppose this is in preference to query-block? It would make it easier.
>
> Well, query-block remains the canonical way for users to access the 
> count, while x-debug-block-dirty-bitmap-sha256 is for debugging only 
> (basically, for our unit tests, as no one outside of qemu will get 
> much use out of it).  But yes, writing a test that uses bitmaps on an 
> unconnected BDS is easier than a test that has to use a named device, 
> since query-block won't list nodes that aren't connected to a named 
> device, and requires a lot more parsing to get at the actual bitmap 
> information in comparison to the debug command directly telling you 
> about a single bitmap.
>

I think the best place is bitmap unit test, which is tests/test-bitmaps, 
and we don't need additional api

-- 
Best regards,
Vladimir

Re: [Qemu-devel] [PATCH v2] bitmap: Update count after a merge

[John Snow]

On 10/02/2018 07:33 PM, John Snow wrote:
> From: Eric Blake <eblake@redhat.com>
> 
> We need an accurate count of the number of bits set in a bitmap
> after a merge. In particular, since the merge operation short-circuits
> a merge from an empty source, if you have bitmaps A, B, and C where
> B started empty, then merge C into B, and B into A, an inaccurate
> count meant that A did not get the contents of C.
> 
> In the worst case, we may falsely regard the bitmap as empty when
> it has had new writes merged into it.
> 
> Fixes: be58721db
> CC: qemu-stable@nongnu.org
> Signed-off-by: Eric Blake <eblake@redhat.com>
> Signed-off-by: John Snow <jsnow@redhat.com>
> ---
> 
> v2: based off of Eric's cover letter, now rebased properly
>     on top of the jsnow/bitmaps staging branch to use the
>     correct bitmap target (result).
> 
> 
>  util/hbitmap.c | 3 +++
>  1 file changed, 3 insertions(+)
> 
> diff --git a/util/hbitmap.c b/util/hbitmap.c
> index d5aca5159f..8d402c59d9 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -759,6 +759,9 @@ bool hbitmap_merge(const HBitmap *a, const HBitmap *b, HBitmap *result)
>          }
>      }
>  
> +    /* Recompute the dirty count */
> +    result->count = hb_count_between(result, 0, result->size - 1);
> +
>      return true;
>  }
>  
> 

Tests on the way, but for now...

Thanks, applied to my bitmaps tree:

https://github.com/jnsnow/qemu/commits/bitmaps
https://github.com/jnsnow/qemu.git

--js