[Qemu-devel] [PATCH] util/hbitmap: fix unaligned reset

[Qemu-devel] [PATCH] util/hbitmap: fix unaligned reset

[Vladimir Sementsov-Ogievskiy]

hbitmap_reset is broken: it rounds up the requested region. It leads to
the following bug, which is shown by fixed test:

assume granularity = 2
set(0, 3) # count becomes 4
reset(0, 1) # count becomes 2

But user of the interface assume that virtual bit 1 should be still
dirty, so hbitmap should report count to be 4!

In other words, because of granularity, when we set one "virtual" bit,
yes, we make all "virtual" bits in same chunk to be dirty. But this
should not be so for reset.

Fix this, aligning bound correctly.

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

Hi all!

Hmm, is it a bug or feature? :)
I don't have a test for mirror yet, but I think that sync mirror may be broken
because of this, as do_sync_target_write() seems to be using unaligned reset.

 tests/test-hbitmap.c |  2 +-
 util/hbitmap.c       | 24 +++++++++++++++++++-----
 2 files changed, 20 insertions(+), 6 deletions(-)

diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
index 592d8219db..0008025a9f 100644
--- a/tests/test-hbitmap.c
+++ b/tests/test-hbitmap.c
@@ -424,7 +424,7 @@ static void test_hbitmap_granularity(TestHBitmapData *data,
     hbitmap_test_set(data, 0, 3);
     g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
     hbitmap_test_reset(data, 0, 1);
-    g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
+    g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
 }
 
 static void test_hbitmap_iter_granularity(TestHBitmapData *data,
diff --git a/util/hbitmap.c b/util/hbitmap.c
index 7905212a8b..61a813994a 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -473,15 +473,29 @@ void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count)
 {
     /* Compute range in the last layer.  */
     uint64_t first;
-    uint64_t last = start + count - 1;
+    uint64_t last;
+    uint64_t end = start + count;
+    uint64_t gran = UINT64_C(1) << hb->granularity;
 
-    trace_hbitmap_reset(hb, start, count,
-                        start >> hb->granularity, last >> hb->granularity);
+    /*
+     * We should clear only bits, fully covered by requested region. Otherwise
+     * we may clear something that is actually still dirty.
+     */
+    first = DIV_ROUND_UP(start, gran);
 
-    first = start >> hb->granularity;
-    last >>= hb->granularity;
+    if (end == hb->orig_size) {
+        end = DIV_ROUND_UP(end, gran);
+    } else {
+        end = end >> hb->granularity;
+    }
+    if (end <= first) {
+        return;
+    }
+    last = end - 1;
     assert(last < hb->size);
 
+    trace_hbitmap_reset(hb, start, count, first, last);
+
     hb->count -= hb_count_between(hb, first, last);
     if (hb_reset_between(hb, HBITMAP_LEVELS - 1, first, last) &&
         hb->meta) {
-- 
2.18.0

Re: [Qemu-devel] [PATCH] util/hbitmap: fix unaligned reset

[John Snow]

On 8/2/19 2:58 PM, Vladimir Sementsov-Ogievskiy wrote:
> hbitmap_reset is broken: it rounds up the requested region. It leads to
> the following bug, which is shown by fixed test:
> 
> assume granularity = 2
> set(0, 3) # count becomes 4
> reset(0, 1) # count becomes 2
> 
> But user of the interface assume that virtual bit 1 should be still
> dirty, so hbitmap should report count to be 4!
> 
> In other words, because of granularity, when we set one "virtual" bit,
> yes, we make all "virtual" bits in same chunk to be dirty. But this
> should not be so for reset.
> 
> Fix this, aligning bound correctly.
> 
> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> ---
> 
> Hi all!
> 
> Hmm, is it a bug or feature? :)

Very, very good question.

> I don't have a test for mirror yet, but I think that sync mirror may be broken
> because of this, as do_sync_target_write() seems to be using unaligned reset.
> 

Honestly I was worried about this -- if you take a look at my patches
where I add new bitmap sync modes, I bent over backwards to align
requests for the sync=top bitmap initialization methods because I was
worried about this possibly being the case.


I'm not sure what the "right" behavior ought to be.

Let's say you have a granularity of 8 bytes:

if you reset 0-3 in one call, and then 4-7 in the next, what happens? If
the caller naively thinks there's a 1:1 relationship, it might actually
expect that to reflect a cleared bit. With alignment protection, we'll
just fail to clear it both times and it remains set.

On the other hand, if you do allow partial clears, the first reset for
0-3 will toggle off 4-7 too, where we might rely on the fact that it's
actually still dirty.

Whether or not that's dangerous depends on the context, and only the
caller knows the context. I think we need to make the semantic effect of
the reset "obvious" to the caller.


I envision this:

- hbitmap_reset(bitmap, start, length)
  returns -EINVAL if the range is not properly aligned

- hbitmap_reset_flags(bitmap, flags, start, length)
  if (flags & HBITMAP_ALIGN_DOWN) align request to only full bits
  if (flags & HBITMAP_ALIGN_UP) align request to cover any bit even
partially touched by the specified range
  otherwise, pass range through as-is to hbitmap_reset (and possibly get
-EINVAL if caller did not align the request.)


That way the semantics are always clear to the caller.

--js

>  tests/test-hbitmap.c |  2 +-
>  util/hbitmap.c       | 24 +++++++++++++++++++-----
>  2 files changed, 20 insertions(+), 6 deletions(-)
> 
> diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
> index 592d8219db..0008025a9f 100644
> --- a/tests/test-hbitmap.c
> +++ b/tests/test-hbitmap.c
> @@ -424,7 +424,7 @@ static void test_hbitmap_granularity(TestHBitmapData *data,
>      hbitmap_test_set(data, 0, 3);
>      g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
>      hbitmap_test_reset(data, 0, 1);
> -    g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
> +    g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
>  }
>  
>  static void test_hbitmap_iter_granularity(TestHBitmapData *data,
> diff --git a/util/hbitmap.c b/util/hbitmap.c
> index 7905212a8b..61a813994a 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -473,15 +473,29 @@ void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count)
>  {
>      /* Compute range in the last layer.  */
>      uint64_t first;
> -    uint64_t last = start + count - 1;
> +    uint64_t last;
> +    uint64_t end = start + count;
> +    uint64_t gran = UINT64_C(1) << hb->granularity;
>  
> -    trace_hbitmap_reset(hb, start, count,
> -                        start >> hb->granularity, last >> hb->granularity);
> +    /*
> +     * We should clear only bits, fully covered by requested region. Otherwise
> +     * we may clear something that is actually still dirty.
> +     */
> +    first = DIV_ROUND_UP(start, gran);
>  
> -    first = start >> hb->granularity;
> -    last >>= hb->granularity;
> +    if (end == hb->orig_size) {
> +        end = DIV_ROUND_UP(end, gran);
> +    } else {
> +        end = end >> hb->granularity;
> +    }
> +    if (end <= first) {
> +        return;
> +    }
> +    last = end - 1;
>      assert(last < hb->size);
>  
> +    trace_hbitmap_reset(hb, start, count, first, last);
> +
>      hb->count -= hb_count_between(hb, first, last);
>      if (hb_reset_between(hb, HBITMAP_LEVELS - 1, first, last) &&
>          hb->meta) {
> 

Re: [Qemu-devel] [PATCH] util/hbitmap: fix unaligned reset

[Vladimir Sementsov-Ogievskiy]

02.08.2019 22:21, John Snow wrote:
> 
> 
> On 8/2/19 2:58 PM, Vladimir Sementsov-Ogievskiy wrote:
>> hbitmap_reset is broken: it rounds up the requested region. It leads to
>> the following bug, which is shown by fixed test:
>>
>> assume granularity = 2
>> set(0, 3) # count becomes 4
>> reset(0, 1) # count becomes 2
>>
>> But user of the interface assume that virtual bit 1 should be still
>> dirty, so hbitmap should report count to be 4!
>>
>> In other words, because of granularity, when we set one "virtual" bit,
>> yes, we make all "virtual" bits in same chunk to be dirty. But this
>> should not be so for reset.
>>
>> Fix this, aligning bound correctly.
>>
>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>> ---
>>
>> Hi all!
>>
>> Hmm, is it a bug or feature? :)
> 
> Very, very good question.
> 
>> I don't have a test for mirror yet, but I think that sync mirror may be broken
>> because of this, as do_sync_target_write() seems to be using unaligned reset.
>>
> 
> Honestly I was worried about this -- if you take a look at my patches
> where I add new bitmap sync modes, I bent over backwards to align
> requests for the sync=top bitmap initialization methods because I was
> worried about this possibly being the case.
> 
> 
> I'm not sure what the "right" behavior ought to be.
> 
> Let's say you have a granularity of 8 bytes:
> 
> if you reset 0-3 in one call, and then 4-7 in the next, what happens? If
> the caller naively thinks there's a 1:1 relationship, it might actually
> expect that to reflect a cleared bit. With alignment protection, we'll
> just fail to clear it both times and it remains set.
> 
> On the other hand, if you do allow partial clears, the first reset for
> 0-3 will toggle off 4-7 too, where we might rely on the fact that it's
> actually still dirty.
> 
> Whether or not that's dangerous depends on the context, and only the
> caller knows the context. I think we need to make the semantic effect of
> the reset "obvious" to the caller.
> 
> 
> I envision this:
> 
> - hbitmap_reset(bitmap, start, length)
>    returns -EINVAL if the range is not properly aligned

hbitmap_reset don't return, I thinks it should be an assertion

> 
> - hbitmap_reset_flags(bitmap, flags, start, length)
>    if (flags & HBITMAP_ALIGN_DOWN) align request to only full bits
>    if (flags & HBITMAP_ALIGN_UP) align request to cover any bit even
> partially touched by the specified range
>    otherwise, pass range through as-is to hbitmap_reset (and possibly get
> -EINVAL if caller did not align the request.)
> 
> 
> That way the semantics are always clear to the caller.

Hmm, I doubt, is there any use of ALIGN_UP? In most cases it's safe to thing that
something clear is dirty (and this is how hbitmap actually works on set/get), but
it seems always unsafe to ALIGN_UP reset..

So, I think that it should be default to ALIGN_DOWN, or just an assertion that request
is aligned (which anyway leads to implementing a helper hbitmap_reset_align_up)..

> 
> --js
> 
>>   tests/test-hbitmap.c |  2 +-
>>   util/hbitmap.c       | 24 +++++++++++++++++++-----
>>   2 files changed, 20 insertions(+), 6 deletions(-)
>>
>> diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
>> index 592d8219db..0008025a9f 100644
>> --- a/tests/test-hbitmap.c
>> +++ b/tests/test-hbitmap.c
>> @@ -424,7 +424,7 @@ static void test_hbitmap_granularity(TestHBitmapData *data,
>>       hbitmap_test_set(data, 0, 3);
>>       g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
>>       hbitmap_test_reset(data, 0, 1);
>> -    g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
>> +    g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
>>   }
>>   
>>   static void test_hbitmap_iter_granularity(TestHBitmapData *data,
>> diff --git a/util/hbitmap.c b/util/hbitmap.c
>> index 7905212a8b..61a813994a 100644
>> --- a/util/hbitmap.c
>> +++ b/util/hbitmap.c
>> @@ -473,15 +473,29 @@ void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count)
>>   {
>>       /* Compute range in the last layer.  */
>>       uint64_t first;
>> -    uint64_t last = start + count - 1;
>> +    uint64_t last;
>> +    uint64_t end = start + count;
>> +    uint64_t gran = UINT64_C(1) << hb->granularity;
>>   
>> -    trace_hbitmap_reset(hb, start, count,
>> -                        start >> hb->granularity, last >> hb->granularity);
>> +    /*
>> +     * We should clear only bits, fully covered by requested region. Otherwise
>> +     * we may clear something that is actually still dirty.
>> +     */
>> +    first = DIV_ROUND_UP(start, gran);
>>   
>> -    first = start >> hb->granularity;
>> -    last >>= hb->granularity;
>> +    if (end == hb->orig_size) {
>> +        end = DIV_ROUND_UP(end, gran);
>> +    } else {
>> +        end = end >> hb->granularity;
>> +    }
>> +    if (end <= first) {
>> +        return;
>> +    }
>> +    last = end - 1;
>>       assert(last < hb->size);
>>   
>> +    trace_hbitmap_reset(hb, start, count, first, last);
>> +
>>       hb->count -= hb_count_between(hb, first, last);
>>       if (hb_reset_between(hb, HBITMAP_LEVELS - 1, first, last) &&
>>           hb->meta) {
>>


-- 
Best regards,
Vladimir

Re: [Qemu-devel] [PATCH] util/hbitmap: fix unaligned reset

[Vladimir Sementsov-Ogievskiy]

05.08.2019 12:26, Vladimir Sementsov-Ogievskiy wrote:
> 02.08.2019 22:21, John Snow wrote:
>>
>>
>> On 8/2/19 2:58 PM, Vladimir Sementsov-Ogievskiy wrote:
>>> hbitmap_reset is broken: it rounds up the requested region. It leads to
>>> the following bug, which is shown by fixed test:
>>>
>>> assume granularity = 2
>>> set(0, 3) # count becomes 4
>>> reset(0, 1) # count becomes 2
>>>
>>> But user of the interface assume that virtual bit 1 should be still
>>> dirty, so hbitmap should report count to be 4!
>>>
>>> In other words, because of granularity, when we set one "virtual" bit,
>>> yes, we make all "virtual" bits in same chunk to be dirty. But this
>>> should not be so for reset.
>>>
>>> Fix this, aligning bound correctly.
>>>
>>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>>> ---
>>>
>>> Hi all!
>>>
>>> Hmm, is it a bug or feature? :)
>>
>> Very, very good question.
>>
>>> I don't have a test for mirror yet, but I think that sync mirror may be broken
>>> because of this, as do_sync_target_write() seems to be using unaligned reset.
>>>
>>
>> Honestly I was worried about this -- if you take a look at my patches
>> where I add new bitmap sync modes, I bent over backwards to align
>> requests for the sync=top bitmap initialization methods because I was
>> worried about this possibly being the case.
>>
>>
>> I'm not sure what the "right" behavior ought to be.
>>
>> Let's say you have a granularity of 8 bytes:
>>
>> if you reset 0-3 in one call, and then 4-7 in the next, what happens? If
>> the caller naively thinks there's a 1:1 relationship, it might actually
>> expect that to reflect a cleared bit. With alignment protection, we'll
>> just fail to clear it both times and it remains set.
>>
>> On the other hand, if you do allow partial clears, the first reset for
>> 0-3 will toggle off 4-7 too, where we might rely on the fact that it's
>> actually still dirty.
>>
>> Whether or not that's dangerous depends on the context, and only the
>> caller knows the context. I think we need to make the semantic effect of
>> the reset "obvious" to the caller.
>>
>>
>> I envision this:
>>
>> - hbitmap_reset(bitmap, start, length)
>>    returns -EINVAL if the range is not properly aligned
> 
> hbitmap_reset don't return, I thinks it should be an assertion

don't return any value

> 
>>
>> - hbitmap_reset_flags(bitmap, flags, start, length)
>>    if (flags & HBITMAP_ALIGN_DOWN) align request to only full bits
>>    if (flags & HBITMAP_ALIGN_UP) align request to cover any bit even
>> partially touched by the specified range
>>    otherwise, pass range through as-is to hbitmap_reset (and possibly get
>> -EINVAL if caller did not align the request.)
>>
>>
>> That way the semantics are always clear to the caller.
> 
> Hmm, I doubt, is there any use of ALIGN_UP? In most cases it's safe to thing that
> something clear is dirty (and this is how hbitmap actually works on set/get), but
> it seems always unsafe to ALIGN_UP reset..
> 
> So, I think that it should be default to ALIGN_DOWN, or just an assertion that request
> is aligned (which anyway leads to implementing a helper hbitmap_reset_align_up)..

hbitmap_reset_align_down I mean.

> 
>>
>> --js
>>
>>>   tests/test-hbitmap.c |  2 +-
>>>   util/hbitmap.c       | 24 +++++++++++++++++++-----
>>>   2 files changed, 20 insertions(+), 6 deletions(-)
>>>
>>> diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
>>> index 592d8219db..0008025a9f 100644
>>> --- a/tests/test-hbitmap.c
>>> +++ b/tests/test-hbitmap.c
>>> @@ -424,7 +424,7 @@ static void test_hbitmap_granularity(TestHBitmapData *data,
>>>       hbitmap_test_set(data, 0, 3);
>>>       g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
>>>       hbitmap_test_reset(data, 0, 1);
>>> -    g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
>>> +    g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
>>>   }
>>>   static void test_hbitmap_iter_granularity(TestHBitmapData *data,
>>> diff --git a/util/hbitmap.c b/util/hbitmap.c
>>> index 7905212a8b..61a813994a 100644
>>> --- a/util/hbitmap.c
>>> +++ b/util/hbitmap.c
>>> @@ -473,15 +473,29 @@ void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count)
>>>   {
>>>       /* Compute range in the last layer.  */
>>>       uint64_t first;
>>> -    uint64_t last = start + count - 1;
>>> +    uint64_t last;
>>> +    uint64_t end = start + count;
>>> +    uint64_t gran = UINT64_C(1) << hb->granularity;
>>> -    trace_hbitmap_reset(hb, start, count,
>>> -                        start >> hb->granularity, last >> hb->granularity);
>>> +    /*
>>> +     * We should clear only bits, fully covered by requested region. Otherwise
>>> +     * we may clear something that is actually still dirty.
>>> +     */
>>> +    first = DIV_ROUND_UP(start, gran);
>>> -    first = start >> hb->granularity;
>>> -    last >>= hb->granularity;
>>> +    if (end == hb->orig_size) {
>>> +        end = DIV_ROUND_UP(end, gran);
>>> +    } else {
>>> +        end = end >> hb->granularity;
>>> +    }
>>> +    if (end <= first) {
>>> +        return;
>>> +    }
>>> +    last = end - 1;
>>>       assert(last < hb->size);
>>> +    trace_hbitmap_reset(hb, start, count, first, last);
>>> +
>>>       hb->count -= hb_count_between(hb, first, last);
>>>       if (hb_reset_between(hb, HBITMAP_LEVELS - 1, first, last) &&
>>>           hb->meta) {
>>>
> 
> 


-- 
Best regards,
Vladimir

Re: [Qemu-devel] [PATCH] util/hbitmap: fix unaligned reset

[John Snow]

On 8/5/19 5:48 AM, Vladimir Sementsov-Ogievskiy wrote:
> 05.08.2019 12:26, Vladimir Sementsov-Ogievskiy wrote:
>> 02.08.2019 22:21, John Snow wrote:
>>>
>>>
>>> On 8/2/19 2:58 PM, Vladimir Sementsov-Ogievskiy wrote:
>>>> hbitmap_reset is broken: it rounds up the requested region. It leads to
>>>> the following bug, which is shown by fixed test:
>>>>
>>>> assume granularity = 2
>>>> set(0, 3) # count becomes 4
>>>> reset(0, 1) # count becomes 2
>>>>
>>>> But user of the interface assume that virtual bit 1 should be still
>>>> dirty, so hbitmap should report count to be 4!
>>>>
>>>> In other words, because of granularity, when we set one "virtual" bit,
>>>> yes, we make all "virtual" bits in same chunk to be dirty. But this
>>>> should not be so for reset.
>>>>
>>>> Fix this, aligning bound correctly.
>>>>
>>>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>>>> ---
>>>>
>>>> Hi all!
>>>>
>>>> Hmm, is it a bug or feature? :)
>>>
>>> Very, very good question.
>>>
>>>> I don't have a test for mirror yet, but I think that sync mirror may be broken
>>>> because of this, as do_sync_target_write() seems to be using unaligned reset.
>>>>
>>>
>>> Honestly I was worried about this -- if you take a look at my patches
>>> where I add new bitmap sync modes, I bent over backwards to align
>>> requests for the sync=top bitmap initialization methods because I was
>>> worried about this possibly being the case.
>>>
>>>
>>> I'm not sure what the "right" behavior ought to be.
>>>
>>> Let's say you have a granularity of 8 bytes:
>>>
>>> if you reset 0-3 in one call, and then 4-7 in the next, what happens? If
>>> the caller naively thinks there's a 1:1 relationship, it might actually
>>> expect that to reflect a cleared bit. With alignment protection, we'll
>>> just fail to clear it both times and it remains set.
>>>
>>> On the other hand, if you do allow partial clears, the first reset for
>>> 0-3 will toggle off 4-7 too, where we might rely on the fact that it's
>>> actually still dirty.
>>>
>>> Whether or not that's dangerous depends on the context, and only the
>>> caller knows the context. I think we need to make the semantic effect of
>>> the reset "obvious" to the caller.
>>>
>>>
>>> I envision this:
>>>
>>> - hbitmap_reset(bitmap, start, length)
>>>    returns -EINVAL if the range is not properly aligned
>>
>> hbitmap_reset don't return, I thinks it should be an assertion
> 
> don't return any value
> 

Works for me.

>>
>>>
>>> - hbitmap_reset_flags(bitmap, flags, start, length)
>>>    if (flags & HBITMAP_ALIGN_DOWN) align request to only full bits
>>>    if (flags & HBITMAP_ALIGN_UP) align request to cover any bit even
>>> partially touched by the specified range
>>>    otherwise, pass range through as-is to hbitmap_reset (and possibly get
>>> -EINVAL if caller did not align the request.)
>>>
>>>
>>> That way the semantics are always clear to the caller.
>>
>> Hmm, I doubt, is there any use of ALIGN_UP? In most cases it's safe to thing that
>> something clear is dirty (and this is how hbitmap actually works on set/get), but
>> it seems always unsafe to ALIGN_UP reset..
>>
>> So, I think that it should be default to ALIGN_DOWN, or just an assertion that request
>> is aligned (which anyway leads to implementing a helper hbitmap_reset_align_up)..
> 
> hbitmap_reset_align_down I mean.
> 
There might not be one at the moment -- it's just the existing behavior
so I catered to it. I'd definitely just omit it if no callers need that
semantic.

So we'd have a "strict aligned" mode and a "clamped down" mode, which
probably gives us what we need in all current cases.

(Still catching up on all of today's emails, though.)

--js

Re: [Qemu-devel] [PATCH] util/hbitmap: fix unaligned reset

[Max Reitz]

[-- Attachment #1.1: Type: text/plain, Size: 3321 bytes --]

On 02.08.19 20:58, Vladimir Sementsov-Ogievskiy wrote:
> hbitmap_reset is broken: it rounds up the requested region. It leads to
> the following bug, which is shown by fixed test:
> 
> assume granularity = 2
> set(0, 3) # count becomes 4
> reset(0, 1) # count becomes 2
> 
> But user of the interface assume that virtual bit 1 should be still
> dirty, so hbitmap should report count to be 4!
> 
> In other words, because of granularity, when we set one "virtual" bit,
> yes, we make all "virtual" bits in same chunk to be dirty. But this
> should not be so for reset.
> 
> Fix this, aligning bound correctly.
> 
> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> ---
> 
> Hi all!
> 
> Hmm, is it a bug or feature? :)
> I don't have a test for mirror yet, but I think that sync mirror may be broken
> because of this, as do_sync_target_write() seems to be using unaligned reset.

Crap.


Yes, you’re right.  This would fix it, and it wouldn’t fix it in the
worst way.

But I don’t know whether this patch is the best way forward still.  I
think call hbitmap_reset() with unaligned boundaries generally calls for
trouble, as John has laid out.  If mirror’s do_sync_target_write() is
the only offender right now, I’d prefer for hbitmap_reset() to assert
that the boundaries are aligned (for 4.2), and for
do_sync_target_write() to be fixed (for 4.1? :-/).

(A practical problem with this patch is that do_sync_target_write() will
still do the write, but it won’t change anything in the bitmap, so the
copy operation was effectively useless.)

I don’t know how to fix mirror exactly, though.  I have four ideas:

(A) Quick fix 1: do_sync_target_write() should shrink [offset, offset +
bytes) such that it is aligned.  This would make it skip writes that
don’t fill one whole chunk.

+: Simple fix.  Could go into 4.1.
-: Makes copy-mode=write-blocking equal to copy-mode=background unless
   you set the granularity to like 512. (Still beats just being
   completely broken.)

(B) Quick fix 2: Setting the request_alignment block limit to the job’s
granularity when in write-blocking mode.

+: Very simple fix.  Could go into 4.1.
+: Every write will trigger a RMW cycle, which copies the whole chunk to
   the target, so write-blocking will do what it’s supposed to do.
-: request_alignment forces everything to have the same granularity, so
   this slows down reads needlessly.  (But only for write-blocking.)

(C) Maybe the right fix 1: Let do_sync_target_write() expand [offset,
offset + bytes) such that it is aligned and read head and tail from the
source node.  (So it would do the RMW itself.)

+ Doesn’t slow reads down.
+ Writes to dirty areas will make them clean – which is what
  write-blocking is for.
- Probably more complicated.  Nothing for 4.1.

(D) Maybe the right fix 2: Split BlockLimits.request_alignment into
read_alignment and write_alignment.  Then do (B).

In effect, this is more or less the same as (C), but probably in a
simpler way.  Still not simple enough for 4.1, though.


So...  I tend to do either (A) or (B) now, and then probably (D) for
4.2?  (And because (D) is an extension to (B), it would make sense to do
(B) now, unless you’d prefer (A).)

Max


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [Qemu-devel] [PATCH] util/hbitmap: fix unaligned reset

[Vladimir Sementsov-Ogievskiy]

03.08.2019 0:19, Max Reitz wrote:
> On 02.08.19 20:58, Vladimir Sementsov-Ogievskiy wrote:
>> hbitmap_reset is broken: it rounds up the requested region. It leads to
>> the following bug, which is shown by fixed test:
>>
>> assume granularity = 2
>> set(0, 3) # count becomes 4
>> reset(0, 1) # count becomes 2
>>
>> But user of the interface assume that virtual bit 1 should be still
>> dirty, so hbitmap should report count to be 4!
>>
>> In other words, because of granularity, when we set one "virtual" bit,
>> yes, we make all "virtual" bits in same chunk to be dirty. But this
>> should not be so for reset.
>>
>> Fix this, aligning bound correctly.
>>
>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>> ---
>>
>> Hi all!
>>
>> Hmm, is it a bug or feature? :)
>> I don't have a test for mirror yet, but I think that sync mirror may be broken
>> because of this, as do_sync_target_write() seems to be using unaligned reset.
> 
> Crap.
> 
> 
> Yes, you’re right.  This would fix it, and it wouldn’t fix it in the
> worst way.
> 
> But I don’t know whether this patch is the best way forward still.  I
> think call hbitmap_reset() with unaligned boundaries generally calls for
> trouble, as John has laid out.  If mirror’s do_sync_target_write() is
> the only offender right now, I’d prefer for hbitmap_reset() to assert
> that the boundaries are aligned (for 4.2),

OK, agree that asserting this is better.

  and for
> do_sync_target_write() to be fixed (for 4.1? :-/).
> 
> (A practical problem with this patch is that do_sync_target_write() will
> still do the write, but it won’t change anything in the bitmap, so the
> copy operation was effectively useless.)
> 
> I don’t know how to fix mirror exactly, though.  I have four ideas:
> 
> (A) Quick fix 1: do_sync_target_write() should shrink [offset, offset +
> bytes) such that it is aligned.  This would make it skip writes that
> don’t fill one whole chunk.
> 
> +: Simple fix.  Could go into 4.1.
> -: Makes copy-mode=write-blocking equal to copy-mode=background unless
>     you set the granularity to like 512. (Still beats just being
>     completely broken.)
> 
> (B) Quick fix 2: Setting the request_alignment block limit to the job’s
> granularity when in write-blocking mode.
> 
> +: Very simple fix.  Could go into 4.1.
> +: Every write will trigger a RMW cycle, which copies the whole chunk to
>     the target, so write-blocking will do what it’s supposed to do.
> -: request_alignment forces everything to have the same granularity, so
>     this slows down reads needlessly.  (But only for write-blocking.)
> 
> (C) Maybe the right fix 1: Let do_sync_target_write() expand [offset,
> offset + bytes) such that it is aligned and read head and tail from the
> source node.  (So it would do the RMW itself.)
> 
> + Doesn’t slow reads down.
> + Writes to dirty areas will make them clean – which is what
>    write-blocking is for.
> - Probably more complicated.  Nothing for 4.1.

This is how backup works.

> 
> (D) Maybe the right fix 2: Split BlockLimits.request_alignment into
> read_alignment and write_alignment.  Then do (B).

Now it's OK, but if we implement bitmap mode for mirror (which is upcoming
anyway, I think), it will slow down all writes, when we are interested only
in which are touching dirty parts.

> 
> In effect, this is more or less the same as (C), but probably in a
> simpler way.  Still not simple enough for 4.1, though.
> 
> 
> So...  I tend to do either (A) or (B) now, and then probably (D) for
> 4.2?  (And because (D) is an extension to (B), it would make sense to do
> (B) now, unless you’d prefer (A).)
> 
> Max
> 


-- 
Best regards,
Vladimir

Re: [Qemu-devel] [PATCH] util/hbitmap: fix unaligned reset

[Max Reitz]

[-- Attachment #1.1: Type: text/plain, Size: 4115 bytes --]

On 05.08.19 11:45, Vladimir Sementsov-Ogievskiy wrote:
> 03.08.2019 0:19, Max Reitz wrote:
>> On 02.08.19 20:58, Vladimir Sementsov-Ogievskiy wrote:
>>> hbitmap_reset is broken: it rounds up the requested region. It leads to
>>> the following bug, which is shown by fixed test:
>>>
>>> assume granularity = 2
>>> set(0, 3) # count becomes 4
>>> reset(0, 1) # count becomes 2
>>>
>>> But user of the interface assume that virtual bit 1 should be still
>>> dirty, so hbitmap should report count to be 4!
>>>
>>> In other words, because of granularity, when we set one "virtual" bit,
>>> yes, we make all "virtual" bits in same chunk to be dirty. But this
>>> should not be so for reset.
>>>
>>> Fix this, aligning bound correctly.
>>>
>>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>>> ---
>>>
>>> Hi all!
>>>
>>> Hmm, is it a bug or feature? :)
>>> I don't have a test for mirror yet, but I think that sync mirror may be broken
>>> because of this, as do_sync_target_write() seems to be using unaligned reset.
>>
>> Crap.
>>
>>
>> Yes, you’re right.  This would fix it, and it wouldn’t fix it in the
>> worst way.
>>
>> But I don’t know whether this patch is the best way forward still.  I
>> think call hbitmap_reset() with unaligned boundaries generally calls for
>> trouble, as John has laid out.  If mirror’s do_sync_target_write() is
>> the only offender right now, I’d prefer for hbitmap_reset() to assert
>> that the boundaries are aligned (for 4.2),
> 
> OK, agree that asserting this is better.
> 
>   and for
>> do_sync_target_write() to be fixed (for 4.1? :-/).
>>
>> (A practical problem with this patch is that do_sync_target_write() will
>> still do the write, but it won’t change anything in the bitmap, so the
>> copy operation was effectively useless.)
>>
>> I don’t know how to fix mirror exactly, though.  I have four ideas:
>>
>> (A) Quick fix 1: do_sync_target_write() should shrink [offset, offset +
>> bytes) such that it is aligned.  This would make it skip writes that
>> don’t fill one whole chunk.
>>
>> +: Simple fix.  Could go into 4.1.
>> -: Makes copy-mode=write-blocking equal to copy-mode=background unless
>>     you set the granularity to like 512. (Still beats just being
>>     completely broken.)
>>
>> (B) Quick fix 2: Setting the request_alignment block limit to the job’s
>> granularity when in write-blocking mode.
>>
>> +: Very simple fix.  Could go into 4.1.
>> +: Every write will trigger a RMW cycle, which copies the whole chunk to
>>     the target, so write-blocking will do what it’s supposed to do.
>> -: request_alignment forces everything to have the same granularity, so
>>     this slows down reads needlessly.  (But only for write-blocking.)
>>
>> (C) Maybe the right fix 1: Let do_sync_target_write() expand [offset,
>> offset + bytes) such that it is aligned and read head and tail from the
>> source node.  (So it would do the RMW itself.)
>>
>> + Doesn’t slow reads down.
>> + Writes to dirty areas will make them clean – which is what
>>    write-blocking is for.
>> - Probably more complicated.  Nothing for 4.1.
> 
> This is how backup works.
> 
>>
>> (D) Maybe the right fix 2: Split BlockLimits.request_alignment into
>> read_alignment and write_alignment.  Then do (B).
> 
> Now it's OK, but if we implement bitmap mode for mirror (which is upcoming
> anyway, I think), it will slow down all writes, when we are interested only
> in which are touching dirty parts.

Ah, yes.  OK, (C) it is, then.  With what Kevin has said, just taking
this patch for now seems good to me; but I can see a small problem still
(will send in a separate mail).

Max

>> In effect, this is more or less the same as (C), but probably in a
>> simpler way.  Still not simple enough for 4.1, though.
>>
>>
>> So...  I tend to do either (A) or (B) now, and then probably (D) for
>> 4.2?  (And because (D) is an extension to (B), it would make sense to do
>> (B) now, unless you’d prefer (A).)
>>
>> Max
>>
> 
> 



[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [Qemu-devel] [PATCH] util/hbitmap: fix unaligned reset

[Max Reitz]

[-- Attachment #1.1: Type: text/plain, Size: 3983 bytes --]

On 05.08.19 11:45, Vladimir Sementsov-Ogievskiy wrote:
> 03.08.2019 0:19, Max Reitz wrote:
>> On 02.08.19 20:58, Vladimir Sementsov-Ogievskiy wrote:
>>> hbitmap_reset is broken: it rounds up the requested region. It leads to
>>> the following bug, which is shown by fixed test:
>>>
>>> assume granularity = 2
>>> set(0, 3) # count becomes 4
>>> reset(0, 1) # count becomes 2
>>>
>>> But user of the interface assume that virtual bit 1 should be still
>>> dirty, so hbitmap should report count to be 4!
>>>
>>> In other words, because of granularity, when we set one "virtual" bit,
>>> yes, we make all "virtual" bits in same chunk to be dirty. But this
>>> should not be so for reset.
>>>
>>> Fix this, aligning bound correctly.
>>>
>>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>>> ---
>>>
>>> Hi all!
>>>
>>> Hmm, is it a bug or feature? :)
>>> I don't have a test for mirror yet, but I think that sync mirror may be broken
>>> because of this, as do_sync_target_write() seems to be using unaligned reset.
>>
>> Crap.
>>
>>
>> Yes, you’re right.  This would fix it, and it wouldn’t fix it in the
>> worst way.
>>
>> But I don’t know whether this patch is the best way forward still.  I
>> think call hbitmap_reset() with unaligned boundaries generally calls for
>> trouble, as John has laid out.  If mirror’s do_sync_target_write() is
>> the only offender right now, I’d prefer for hbitmap_reset() to assert
>> that the boundaries are aligned (for 4.2),
> 
> OK, agree that asserting this is better.
> 
>   and for
>> do_sync_target_write() to be fixed (for 4.1? :-/).
>>
>> (A practical problem with this patch is that do_sync_target_write() will
>> still do the write, but it won’t change anything in the bitmap, so the
>> copy operation was effectively useless.)
>>
>> I don’t know how to fix mirror exactly, though.  I have four ideas:
>>
>> (A) Quick fix 1: do_sync_target_write() should shrink [offset, offset +
>> bytes) such that it is aligned.  This would make it skip writes that
>> don’t fill one whole chunk.
>>
>> +: Simple fix.  Could go into 4.1.
>> -: Makes copy-mode=write-blocking equal to copy-mode=background unless
>>     you set the granularity to like 512. (Still beats just being
>>     completely broken.)
>>
>> (B) Quick fix 2: Setting the request_alignment block limit to the job’s
>> granularity when in write-blocking mode.
>>
>> +: Very simple fix.  Could go into 4.1.
>> +: Every write will trigger a RMW cycle, which copies the whole chunk to
>>     the target, so write-blocking will do what it’s supposed to do.
>> -: request_alignment forces everything to have the same granularity, so
>>     this slows down reads needlessly.  (But only for write-blocking.)
>>
>> (C) Maybe the right fix 1: Let do_sync_target_write() expand [offset,
>> offset + bytes) such that it is aligned and read head and tail from the
>> source node.  (So it would do the RMW itself.)
>>
>> + Doesn’t slow reads down.
>> + Writes to dirty areas will make them clean – which is what
>>    write-blocking is for.
>> - Probably more complicated.  Nothing for 4.1.
> 
> This is how backup works.
> 
>>
>> (D) Maybe the right fix 2: Split BlockLimits.request_alignment into
>> read_alignment and write_alignment.  Then do (B).
> 
> Now it's OK, but if we implement bitmap mode for mirror (which is upcoming
> anyway, I think), it will slow down all writes, when we are interested only
> in which are touching dirty parts.

(By the way, now I remember why I was only thinking about reads: We
always have to copy whole chunks to the target anyway, because when a
write comes in, the whole chunk is marked as dirty.  We don’t know
whether that’s because of this write or not, so we always have to copy
it all.

But I forgot about the source...  Right, we don’t need to align the
write there, just on the target.)

(Max)


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [Qemu-devel] [PATCH] util/hbitmap: fix unaligned reset

[Kevin Wolf]

[-- Attachment #1: Type: text/plain, Size: 2678 bytes --]

Am 02.08.2019 um 23:19 hat Max Reitz geschrieben:
> On 02.08.19 20:58, Vladimir Sementsov-Ogievskiy wrote:
> > hbitmap_reset is broken: it rounds up the requested region. It leads to
> > the following bug, which is shown by fixed test:
> > 
> > assume granularity = 2
> > set(0, 3) # count becomes 4
> > reset(0, 1) # count becomes 2
> > 
> > But user of the interface assume that virtual bit 1 should be still
> > dirty, so hbitmap should report count to be 4!
> > 
> > In other words, because of granularity, when we set one "virtual" bit,
> > yes, we make all "virtual" bits in same chunk to be dirty. But this
> > should not be so for reset.
> > 
> > Fix this, aligning bound correctly.
> > 
> > Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> > ---
> > 
> > Hi all!
> > 
> > Hmm, is it a bug or feature? :)
> > I don't have a test for mirror yet, but I think that sync mirror may be broken
> > because of this, as do_sync_target_write() seems to be using unaligned reset.
> 
> Crap.
> 
> 
> Yes, you’re right.  This would fix it, and it wouldn’t fix it in the
> worst way.
> 
> But I don’t know whether this patch is the best way forward still.  I
> think call hbitmap_reset() with unaligned boundaries generally calls for
> trouble, as John has laid out.  If mirror’s do_sync_target_write() is
> the only offender right now, I’d prefer for hbitmap_reset() to assert
> that the boundaries are aligned (for 4.2), and for
> do_sync_target_write() to be fixed (for 4.1? :-/).
> 
> (A practical problem with this patch is that do_sync_target_write() will
> still do the write, but it won’t change anything in the bitmap, so the
> copy operation was effectively useless.)
> 
> I don’t know how to fix mirror exactly, though.  I have four ideas:
> 
> (A) Quick fix 1: do_sync_target_write() should shrink [offset, offset +
> bytes) such that it is aligned.  This would make it skip writes that
> don’t fill one whole chunk.
> 
> +: Simple fix.  Could go into 4.1.
> -: Makes copy-mode=write-blocking equal to copy-mode=background unless
>    you set the granularity to like 512. (Still beats just being
>    completely broken.)

write-blocking promises that the guest receives request completion only
when the request has also been written to the target. If you completely
skip the write, this promise is broken.

So I think you'd have to keep the write and only align the range for the
purpose of clearing bits in the dirty bitmap. This would result in some
duplicated I/O, which is an efficiency problem, but at least it
shouldn't come with a correctness problem.

Kevin

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 801 bytes --]

Re: [Qemu-devel] [PATCH] util/hbitmap: fix unaligned reset

[Max Reitz]

[-- Attachment #1.1: Type: text/plain, Size: 3420 bytes --]

On 05.08.19 11:56, Kevin Wolf wrote:
> Am 02.08.2019 um 23:19 hat Max Reitz geschrieben:
>> On 02.08.19 20:58, Vladimir Sementsov-Ogievskiy wrote:
>>> hbitmap_reset is broken: it rounds up the requested region. It leads to
>>> the following bug, which is shown by fixed test:
>>>
>>> assume granularity = 2
>>> set(0, 3) # count becomes 4
>>> reset(0, 1) # count becomes 2
>>>
>>> But user of the interface assume that virtual bit 1 should be still
>>> dirty, so hbitmap should report count to be 4!
>>>
>>> In other words, because of granularity, when we set one "virtual" bit,
>>> yes, we make all "virtual" bits in same chunk to be dirty. But this
>>> should not be so for reset.
>>>
>>> Fix this, aligning bound correctly.
>>>
>>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>>> ---
>>>
>>> Hi all!
>>>
>>> Hmm, is it a bug or feature? :)
>>> I don't have a test for mirror yet, but I think that sync mirror may be broken
>>> because of this, as do_sync_target_write() seems to be using unaligned reset.
>>
>> Crap.
>>
>>
>> Yes, you’re right.  This would fix it, and it wouldn’t fix it in the
>> worst way.
>>
>> But I don’t know whether this patch is the best way forward still.  I
>> think call hbitmap_reset() with unaligned boundaries generally calls for
>> trouble, as John has laid out.  If mirror’s do_sync_target_write() is
>> the only offender right now, I’d prefer for hbitmap_reset() to assert
>> that the boundaries are aligned (for 4.2), and for
>> do_sync_target_write() to be fixed (for 4.1? :-/).
>>
>> (A practical problem with this patch is that do_sync_target_write() will
>> still do the write, but it won’t change anything in the bitmap, so the
>> copy operation was effectively useless.)
>>
>> I don’t know how to fix mirror exactly, though.  I have four ideas:
>>
>> (A) Quick fix 1: do_sync_target_write() should shrink [offset, offset +
>> bytes) such that it is aligned.  This would make it skip writes that
>> don’t fill one whole chunk.
>>
>> +: Simple fix.  Could go into 4.1.
>> -: Makes copy-mode=write-blocking equal to copy-mode=background unless
>>    you set the granularity to like 512. (Still beats just being
>>    completely broken.)
> 
> write-blocking promises that the guest receives request completion only
> when the request has also been written to the target. If you completely
> skip the write, this promise is broken.
> 
> So I think you'd have to keep the write and only align the range for the
> purpose of clearing bits in the dirty bitmap. This would result in some
> duplicated I/O, which is an efficiency problem, but at least it
> shouldn't come with a correctness problem.

Hm.  I was thinking that the use case we were mostly thinking about is
people wanting their mirror job to definitely converge.  Doing that
wouldn’t guarantee that.

You’re right that I shouldn’t constrict people in what they might use
write-blocking for; maybe they mostly want to be sure the data is in the
target and don’t care too much about convergence.

In any case, what you describe is fulfilled by this patch here.  So we
may as well just take it, then.

(Unless we decide that we’d rather make write-blocking fully do what
it’s supposed to do, even at the cost of being slow, by announcing a
request_alignment, as described in (B).)

Max


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [Qemu-devel] [PATCH] util/hbitmap: fix unaligned reset

[Paolo Bonzini]

On 02/08/19 23:19, Max Reitz wrote:
> 
> But I don’t know whether this patch is the best way forward still.  I
> think call hbitmap_reset() with unaligned boundaries generally calls for
> trouble, as John has laid out.  If mirror’s do_sync_target_write() is
> the only offender right now, I’d prefer for hbitmap_reset() to assert
> that the boundaries are aligned

I agree (it's not a bug, it's a feature though a nasty one).

Paolo

Re: [Qemu-devel] [PATCH] util/hbitmap: fix unaligned reset

[Vladimir Sementsov-Ogievskiy]

03.08.2019 0:19, Max Reitz wrote:
> On 02.08.19 20:58, Vladimir Sementsov-Ogievskiy wrote:
>> hbitmap_reset is broken: it rounds up the requested region. It leads to
>> the following bug, which is shown by fixed test:
>>
>> assume granularity = 2
>> set(0, 3) # count becomes 4
>> reset(0, 1) # count becomes 2
>>
>> But user of the interface assume that virtual bit 1 should be still
>> dirty, so hbitmap should report count to be 4!
>>
>> In other words, because of granularity, when we set one "virtual" bit,
>> yes, we make all "virtual" bits in same chunk to be dirty. But this
>> should not be so for reset.
>>
>> Fix this, aligning bound correctly.
>>
>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>> ---
>>
>> Hi all!
>>
>> Hmm, is it a bug or feature? :)
>> I don't have a test for mirror yet, but I think that sync mirror may be broken
>> because of this, as do_sync_target_write() seems to be using unaligned reset.
> 
> Crap.
> 
> 
> Yes, you’re right.  This would fix it, and it wouldn’t fix it in the
> worst way.
> 
> But I don’t know whether this patch is the best way forward still.  I
> think call hbitmap_reset() with unaligned boundaries generally calls for
> trouble, as John has laid out.  If mirror’s do_sync_target_write() is
> the only offender right now, 

Another thing is migration/block. Should we care of it, is it supported at all?


-- 
Best regards,
Vladimir

Re: [Qemu-devel] [PATCH] util/hbitmap: fix unaligned reset

[John Snow]

On 8/6/19 8:39 AM, Vladimir Sementsov-Ogievskiy wrote:
> 03.08.2019 0:19, Max Reitz wrote:
>> On 02.08.19 20:58, Vladimir Sementsov-Ogievskiy wrote:
>>> hbitmap_reset is broken: it rounds up the requested region. It leads to
>>> the following bug, which is shown by fixed test:
>>>
>>> assume granularity = 2
>>> set(0, 3) # count becomes 4
>>> reset(0, 1) # count becomes 2
>>>
>>> But user of the interface assume that virtual bit 1 should be still
>>> dirty, so hbitmap should report count to be 4!
>>>
>>> In other words, because of granularity, when we set one "virtual" bit,
>>> yes, we make all "virtual" bits in same chunk to be dirty. But this
>>> should not be so for reset.
>>>
>>> Fix this, aligning bound correctly.
>>>
>>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>>> ---
>>>
>>> Hi all!
>>>
>>> Hmm, is it a bug or feature? :)
>>> I don't have a test for mirror yet, but I think that sync mirror may be broken
>>> because of this, as do_sync_target_write() seems to be using unaligned reset.
>>
>> Crap.
>>
>>
>> Yes, you’re right.  This would fix it, and it wouldn’t fix it in the
>> worst way.
>>
>> But I don’t know whether this patch is the best way forward still.  I
>> think call hbitmap_reset() with unaligned boundaries generally calls for
>> trouble, as John has laid out.  If mirror’s do_sync_target_write() is
>> the only offender right now, 
> 
> Another thing is migration/block. Should we care of it, is it supported at all?
> 

Downstream products always have time and room to get additional fixes; I
think this is supported from an upstream POV so we should investigate this.

I assume migration/block has the same problem that it fully clears
unaligned blocks?

(I can look shortly but can't just yet.)

--js

Re: [Qemu-devel] [PATCH] util/hbitmap: fix unaligned reset

[Vladimir Sementsov-Ogievskiy]

06.08.2019 16:30, John Snow wrote:
> 
> 
> On 8/6/19 8:39 AM, Vladimir Sementsov-Ogievskiy wrote:
>> 03.08.2019 0:19, Max Reitz wrote:
>>> On 02.08.19 20:58, Vladimir Sementsov-Ogievskiy wrote:
>>>> hbitmap_reset is broken: it rounds up the requested region. It leads to
>>>> the following bug, which is shown by fixed test:
>>>>
>>>> assume granularity = 2
>>>> set(0, 3) # count becomes 4
>>>> reset(0, 1) # count becomes 2
>>>>
>>>> But user of the interface assume that virtual bit 1 should be still
>>>> dirty, so hbitmap should report count to be 4!
>>>>
>>>> In other words, because of granularity, when we set one "virtual" bit,
>>>> yes, we make all "virtual" bits in same chunk to be dirty. But this
>>>> should not be so for reset.
>>>>
>>>> Fix this, aligning bound correctly.
>>>>
>>>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>>>> ---
>>>>
>>>> Hi all!
>>>>
>>>> Hmm, is it a bug or feature? :)
>>>> I don't have a test for mirror yet, but I think that sync mirror may be broken
>>>> because of this, as do_sync_target_write() seems to be using unaligned reset.
>>>
>>> Crap.
>>>
>>>
>>> Yes, you’re right.  This would fix it, and it wouldn’t fix it in the
>>> worst way.
>>>
>>> But I don’t know whether this patch is the best way forward still.  I
>>> think call hbitmap_reset() with unaligned boundaries generally calls for
>>> trouble, as John has laid out.  If mirror’s do_sync_target_write() is
>>> the only offender right now,
>>
>> Another thing is migration/block. Should we care of it, is it supported at all?
>>
> 
> Downstream products always have time and room to get additional fixes; I
> think this is supported from an upstream POV so we should investigate this.
> 
> I assume migration/block has the same problem that it fully clears
> unaligned blocks?
> 


Hmm, after closer look, it seems like it's OK. It just a bit more difficult to
see than in other places with reset.


-- 
Best regards,
Vladimir

Re: [Qemu-devel] [PATCH] util/hbitmap: fix unaligned reset

[Max Reitz]

[-- Attachment #1.1: Type: text/plain, Size: 3392 bytes --]

On 02.08.19 20:58, Vladimir Sementsov-Ogievskiy wrote:
> hbitmap_reset is broken: it rounds up the requested region. It leads to
> the following bug, which is shown by fixed test:
> 
> assume granularity = 2
> set(0, 3) # count becomes 4
> reset(0, 1) # count becomes 2
> 
> But user of the interface assume that virtual bit 1 should be still
> dirty, so hbitmap should report count to be 4!
> 
> In other words, because of granularity, when we set one "virtual" bit,
> yes, we make all "virtual" bits in same chunk to be dirty. But this
> should not be so for reset.
> 
> Fix this, aligning bound correctly.
> 
> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> ---
> 
> Hi all!
> 
> Hmm, is it a bug or feature? :)
> I don't have a test for mirror yet, but I think that sync mirror may be broken
> because of this, as do_sync_target_write() seems to be using unaligned reset.
> 
>  tests/test-hbitmap.c |  2 +-
>  util/hbitmap.c       | 24 +++++++++++++++++++-----
>  2 files changed, 20 insertions(+), 6 deletions(-)
> 
> diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
> index 592d8219db..0008025a9f 100644
> --- a/tests/test-hbitmap.c
> +++ b/tests/test-hbitmap.c
> @@ -424,7 +424,7 @@ static void test_hbitmap_granularity(TestHBitmapData *data,
>      hbitmap_test_set(data, 0, 3);
>      g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
>      hbitmap_test_reset(data, 0, 1);
> -    g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
> +    g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
>  }
>  
>  static void test_hbitmap_iter_granularity(TestHBitmapData *data,
> diff --git a/util/hbitmap.c b/util/hbitmap.c
> index 7905212a8b..61a813994a 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -473,15 +473,29 @@ void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count)
>  {
>      /* Compute range in the last layer.  */
>      uint64_t first;
> -    uint64_t last = start + count - 1;
> +    uint64_t last;
> +    uint64_t end = start + count;
> +    uint64_t gran = UINT64_C(1) << hb->granularity;
>  
> -    trace_hbitmap_reset(hb, start, count,
> -                        start >> hb->granularity, last >> hb->granularity);
> +    /*
> +     * We should clear only bits, fully covered by requested region. Otherwise
> +     * we may clear something that is actually still dirty.
> +     */
> +    first = DIV_ROUND_UP(start, gran);
>  
> -    first = start >> hb->granularity;
> -    last >>= hb->granularity;
> +    if (end == hb->orig_size) {

This should be “>=”.

There are callers that don’t make sure that start + count <=
hb->orig_size (e.g. the backup job just calls it with multiples of
cluster_size, which may or may not end up at the image end; and
hbitmap_truncate() just uses “hb->size << hb->granularity” as the end,
which is arguably not ideal, but that’s how it is).

Max

> +        end = DIV_ROUND_UP(end, gran);
> +    } else {
> +        end = end >> hb->granularity;
> +    }
> +    if (end <= first) {
> +        return;
> +    }
> +    last = end - 1;
>      assert(last < hb->size);
>  
> +    trace_hbitmap_reset(hb, start, count, first, last);
> +
>      hb->count -= hb_count_between(hb, first, last);
>      if (hb_reset_between(hb, HBITMAP_LEVELS - 1, first, last) &&
>          hb->meta) {
> 



[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [Qemu-devel] [PATCH] util/hbitmap: fix unaligned reset

[Vladimir Sementsov-Ogievskiy]

05.08.2019 14:32, Max Reitz wrote:
> On 02.08.19 20:58, Vladimir Sementsov-Ogievskiy wrote:
>> hbitmap_reset is broken: it rounds up the requested region. It leads to
>> the following bug, which is shown by fixed test:
>>
>> assume granularity = 2
>> set(0, 3) # count becomes 4
>> reset(0, 1) # count becomes 2
>>
>> But user of the interface assume that virtual bit 1 should be still
>> dirty, so hbitmap should report count to be 4!
>>
>> In other words, because of granularity, when we set one "virtual" bit,
>> yes, we make all "virtual" bits in same chunk to be dirty. But this
>> should not be so for reset.
>>
>> Fix this, aligning bound correctly.
>>
>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>> ---
>>
>> Hi all!
>>
>> Hmm, is it a bug or feature? :)
>> I don't have a test for mirror yet, but I think that sync mirror may be broken
>> because of this, as do_sync_target_write() seems to be using unaligned reset.
>>
>>   tests/test-hbitmap.c |  2 +-
>>   util/hbitmap.c       | 24 +++++++++++++++++++-----
>>   2 files changed, 20 insertions(+), 6 deletions(-)
>>
>> diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
>> index 592d8219db..0008025a9f 100644
>> --- a/tests/test-hbitmap.c
>> +++ b/tests/test-hbitmap.c
>> @@ -424,7 +424,7 @@ static void test_hbitmap_granularity(TestHBitmapData *data,
>>       hbitmap_test_set(data, 0, 3);
>>       g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
>>       hbitmap_test_reset(data, 0, 1);
>> -    g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
>> +    g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
>>   }
>>   
>>   static void test_hbitmap_iter_granularity(TestHBitmapData *data,
>> diff --git a/util/hbitmap.c b/util/hbitmap.c
>> index 7905212a8b..61a813994a 100644
>> --- a/util/hbitmap.c
>> +++ b/util/hbitmap.c
>> @@ -473,15 +473,29 @@ void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count)
>>   {
>>       /* Compute range in the last layer.  */
>>       uint64_t first;
>> -    uint64_t last = start + count - 1;
>> +    uint64_t last;
>> +    uint64_t end = start + count;
>> +    uint64_t gran = UINT64_C(1) << hb->granularity;
>>   
>> -    trace_hbitmap_reset(hb, start, count,
>> -                        start >> hb->granularity, last >> hb->granularity);
>> +    /*
>> +     * We should clear only bits, fully covered by requested region. Otherwise
>> +     * we may clear something that is actually still dirty.
>> +     */
>> +    first = DIV_ROUND_UP(start, gran);
>>   
>> -    first = start >> hb->granularity;
>> -    last >>= hb->granularity;
>> +    if (end == hb->orig_size) {
> 
> This should be “>=”.
> 
> There are callers that don’t make sure that start + count <=
> hb->orig_size (e.g. the backup job just calls it with multiples of
> cluster_size, which may or may not end up at the image end; and
> hbitmap_truncate() just uses “hb->size << hb->granularity” as the end,
> which is arguably not ideal, but that’s how it is).
> 

Ah, yes, you are right. Originally, I had and assertion that end <= hb->orig_size,
but it failed with test because of these cases. I dropped it and forgot to update
the condition. Ogh, this is how such small huge bugs are appearing..


-- 
Best regards,
Vladimir