Skip to contentSkip to conversation

util/hbitmap: fix unaligned reset

PATCH In review Vladimir Sementsov-Ogievskiy 5 participants 17 messages Aug 2, 2019 – Aug 6, 2019

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 util/hbitmap: fix unaligned reset

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.

---

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(-)
tests/test-hbitmap.c +1 -1
index 592d8219db..0008025a9f 100644
@@ -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,
util/hbitmap.c +19 -5
index 7905212a8b..61a813994a 100644
@@ -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) {
Signature · 1 line
2.18.0
#1 lore raw
Quoted 14 lines · 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.

Quoted 8 lines

Fix this, aligning bound correctly.

---

Hi all!

Hmm, is it a bug or feature? :)

Very, very good question.

Quoted 3 lines

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

Quoted 57 lines
 tests/test-hbitmap.c |  2 +-
 util/hbitmap.c       | 24 +++++++++++++++++++-----
 2 files changed, 20 insertions(+), 6 deletions(-)
tests/test-hbitmap.c +1 -1
index 592d8219db..0008025a9f 100644
@@ -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,
util/hbitmap.c +19 -5
index 7905212a8b..61a813994a 100644
@@ -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 lore raw
Quoted 56 lines · John Snow
Quoted 14 lines · 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.

Quoted 8 lines

Fix this, aligning bound correctly.

---

Hi all!

Hmm, is it a bug or feature? :)

Very, very good question.

Quoted 3 lines

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.

Quoted 4 lines

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

Quoted 10 lines

- 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)..

Quoted 60 lines

--js

Quoted 57 lines
  tests/test-hbitmap.c |  2 +-
  util/hbitmap.c       | 24 +++++++++++++++++++-----
  2 files changed, 20 insertions(+), 6 deletions(-)
tests/test-hbitmap.c +1 -1
index 592d8219db..0008025a9f 100644
@@ -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,
util/hbitmap.c +19 -5
index 7905212a8b..61a813994a 100644
@@ -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) {
Signature · 2 lines
Best regards,
Vladimir
#3 lore raw
Quoted 57 lines · Vladimir Sementsov-Ogievskiy
Quoted 56 lines · John Snow
Quoted 14 lines · 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.

Quoted 8 lines

Fix this, aligning bound correctly.

---

Hi all!

Hmm, is it a bug or feature? :)

Very, very good question.

Quoted 3 lines

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.

Quoted 6 lines
Quoted 4 lines

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

Quoted 10 lines
Quoted 10 lines

- 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.)

Quoted 8 lines
Quoted 1 line

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.

Quoted 59 lines
Quoted 57 lines

--js

Quoted 53 lines

  tests/test-hbitmap.c |  2 +- util/hbitmap.c       | 24 +++++++++++++++++++-----

  2 files changed, 20 insertions(+), 6 deletions(-)
tests/test-hbitmap.c +1 -1
index 592d8219db..0008025a9f 100644
@@ -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,
util/hbitmap.c +19 -5
index 7905212a8b..61a813994a 100644
@@ -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) {

Signature · 2 lines
Best regards,
Vladimir
#4 lore raw
Quoted 58 lines · Vladimir Sementsov-Ogievskiy
Quoted 57 lines · Vladimir Sementsov-Ogievskiy
Quoted 56 lines · John Snow
Quoted 14 lines · 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.

Quoted 8 lines

Fix this, aligning bound correctly.

---

Hi all!

Hmm, is it a bug or feature? :)

Very, very good question.

Quoted 3 lines

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.

Quoted 9 lines
Quoted 6 lines
Quoted 4 lines

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.

Quoted 12 lines
Quoted 12 lines
Quoted 11 lines

- 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.

Quoted 9 lines
Quoted 6 lines

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

#5 lore raw
In reply to Vladimir Sementsov-Ogievskiy
Quoted 16 lines · 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.

Quoted 8 lines

---

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

#6 lore raw
Quoted 29 lines · Max Reitz
Quoted 16 lines · 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.

Quoted 8 lines

---

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.

Quoted 8 lines

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

Quoted 26 lines

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.)

Quoted 8 lines

(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.

Quoted 3 lines

(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.

Quoted 11 lines

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

Signature · 2 lines
Best regards,
Vladimir
#7 lore raw
Quoted 80 lines · Vladimir Sementsov-Ogievskiy
Quoted 29 lines · Max Reitz
Quoted 16 lines · 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.

Quoted 8 lines

---

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.

Quoted 8 lines

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

Quoted 26 lines

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.)

Quoted 8 lines

(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.

Quoted 1 line
Quoted 6 lines
Quoted 2 lines

(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

Quoted 12 lines
Quoted 10 lines

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

#8 lore raw
In reply to Vladimir Sementsov-Ogievskiy
Quoted 80 lines · Vladimir Sementsov-Ogievskiy
Quoted 29 lines · Max Reitz
Quoted 16 lines · 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.

Quoted 8 lines

---

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.

Quoted 8 lines

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

Quoted 26 lines

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.)

Quoted 8 lines

(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.

Quoted 1 line
Quoted 6 lines
Quoted 2 lines

(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)

#9 lore raw
In reply to Max Reitz

Am 02.08.2019 um 23:19 hat Max Reitz geschrieben:

Quoted 45 lines · Vladimir Sementsov-Ogievskiy
Quoted 16 lines

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.

Quoted 8 lines

---

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:

Quoted 8 lines

(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

#10 lore raw
Quoted 55 lines · Kevin Wolf

Am 02.08.2019 um 23:19 hat Max Reitz geschrieben:

Quoted 45 lines · Vladimir Sementsov-Ogievskiy
Quoted 16 lines

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.

Quoted 8 lines

---

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:

Quoted 8 lines

(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.)

Quoted 8 lines

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

#11 lore raw
In reply to Max Reitz
Quoted 6 lines · Max Reitz

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

#12 lore raw
In reply to Max Reitz
Quoted 29 lines · Max Reitz
Quoted 16 lines · 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.

Quoted 8 lines

---

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.

Quoted 7 lines

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?

Signature · 2 lines
Best regards,
Vladimir
#13 lore raw
Quoted 33 lines · Vladimir Sementsov-Ogievskiy
Quoted 32 lines · Max Reitz
Quoted 16 lines · 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.

Quoted 8 lines

---

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.

Quoted 7 lines
Quoted 4 lines

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

#14 lore raw
Quoted 41 lines · John Snow
Quoted 38 lines · Vladimir Sementsov-Ogievskiy
Quoted 36 lines · Max Reitz
Quoted 16 lines · 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.

Quoted 8 lines

---

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,

Quoted 9 lines
Quoted 2 lines

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.

Signature · 2 lines
Best regards,
Vladimir
#15 lore raw
In reply to Vladimir Sementsov-Ogievskiy
Quoted 56 lines · 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.

---

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(-)
tests/test-hbitmap.c +1 -1
index 592d8219db..0008025a9f 100644
@@ -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,
util/hbitmap.c +3 -2
index 7905212a8b..61a813994a 100644
@@ -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,

util/hbitmap.c void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count) · line 486

Quoted 10 lines
util/hbitmap.c +6 -3
-                        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

Quoted 16 lines
util/hbitmap.c +10 -0
+        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) {
#16 lore raw
Quoted 70 lines · Max Reitz
Quoted 56 lines · 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.

---

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(-)
tests/test-hbitmap.c +1 -1
index 592d8219db..0008025a9f 100644
@@ -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,
util/hbitmap.c +3 -2
index 7905212a8b..61a813994a 100644
@@ -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,

util/hbitmap.c void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count) · line 486

Quoted 10 lines
util/hbitmap.c +6 -3
-                        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 “>=”.

Quoted 6 lines

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..

Signature · 2 lines
Best regards,
Vladimir