util/hbitmap: fix unaligned reset
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 = 2set(0, 3) # count becomes 4reset(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
@@ -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
@@ -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
Quoted 14 lines · Vladimir Sementsov-Ogievskiy
hbitmap_resetis 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 4reset(0, 1)# count becomes 2But 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.
Signed-off-by Vladimir Sementsov-Ogievskiy <[email protected]>---
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@@ -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@@ -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) {
Quoted 56 lines · John Snow
Quoted 14 lines · Vladimir Sementsov-Ogievskiy
hbitmap_resetis 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 4reset(0, 1)# count becomes 2But 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.
Signed-off-by Vladimir Sementsov-Ogievskiy <[email protected]>---
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-EINVALif 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 tohbitmap_reset(and possibly get-EINVALif 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@@ -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@@ -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
Quoted 57 lines · Vladimir Sementsov-Ogievskiy
Quoted 56 lines · John Snow
Quoted 14 lines · Vladimir Sementsov-Ogievskiy
hbitmap_resetis 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 4reset(0, 1)# count becomes 2But 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.
Signed-off-by Vladimir Sementsov-Ogievskiy <[email protected]>---
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-EINVALif the range is not properly aligned
hbitmap_resetdon'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 tohbitmap_reset(and possibly get-EINVALif 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 toALIGN_UPreset..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 helperhbitmap_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@@ -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@@ -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
Quoted 58 lines · Vladimir Sementsov-Ogievskiy
Quoted 57 lines · Vladimir Sementsov-Ogievskiy
Quoted 56 lines · John Snow
Quoted 14 lines · Vladimir Sementsov-Ogievskiy
hbitmap_resetis 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 4reset(0, 1)# count becomes 2But 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.
Signed-off-by Vladimir Sementsov-Ogievskiy <[email protected]>---
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-EINVALif the range is not properly aligned
hbitmap_resetdon't return, I thinks it should be an assertiondon'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 tohbitmap_reset(and possibly get-EINVALif 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 toALIGN_UPreset..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 helperhbitmap_reset_align_up)..
hbitmap_reset_align_downI 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
Quoted 16 lines · Vladimir Sementsov-Ogievskiy
hbitmap_resetis 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 4reset(0, 1)# count becomes 2But 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
Signed-off-by Vladimir Sementsov-Ogievskiy <[email protected]>---
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, asdo_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
Quoted 29 lines · Max Reitz
Quoted 16 lines · Vladimir Sementsov-Ogievskiy
hbitmap_resetis 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 4reset(0, 1)# count becomes 2But 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
Signed-off-by Vladimir Sementsov-Ogievskiy <[email protected]>---
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, asdo_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’sdo_sync_target_write()is the only offender right now, I’d prefer forhbitmap_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_alignmentblock 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_alignmentforces 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_alignmentandwrite_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
Quoted 80 lines · Vladimir Sementsov-Ogievskiy
Quoted 29 lines · Max Reitz
Quoted 16 lines · Vladimir Sementsov-Ogievskiy
hbitmap_resetis 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 4reset(0, 1)# count becomes 2But 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
Signed-off-by Vladimir Sementsov-Ogievskiy <[email protected]>---
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, asdo_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’sdo_sync_target_write()is the only offender right now, I’d prefer forhbitmap_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_alignmentblock 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_alignmentforces 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_alignmentandwrite_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
Quoted 80 lines · Vladimir Sementsov-Ogievskiy
Quoted 29 lines · Max Reitz
Quoted 16 lines · Vladimir Sementsov-Ogievskiy
hbitmap_resetis 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 4reset(0, 1)# count becomes 2But 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
Signed-off-by Vladimir Sementsov-Ogievskiy <[email protected]>---
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, asdo_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’sdo_sync_target_write()is the only offender right now, I’d prefer forhbitmap_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_alignmentblock 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_alignmentforces 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_alignmentandwrite_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)
Am 02.08.2019 um 23:19 hat Max Reitz geschrieben:
Quoted 45 lines · Vladimir Sementsov-Ogievskiy
Quoted 16 lines
hbitmap_resetis 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 4reset(0, 1)# count becomes 2But 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
Signed-off-by Vladimir Sementsov-Ogievskiy <[email protected]>---
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, asdo_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’sdo_sync_target_write()is the only offender right now, I’d prefer forhbitmap_reset()to assert that the boundaries are aligned (for 4.2), and fordo_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
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_resetis 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 4reset(0, 1)# count becomes 2But 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
Signed-off-by Vladimir Sementsov-Ogievskiy <[email protected]>---
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, asdo_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’sdo_sync_target_write()is the only offender right now, I’d prefer forhbitmap_reset()to assert that the boundaries are aligned (for 4.2), and fordo_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
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’sdo_sync_target_write()is the only offender right now, I’d prefer forhbitmap_reset()to assert that the boundaries are aligned
I agree (it's not a bug, it's a feature though a nasty one).
Paolo
Quoted 29 lines · Max Reitz
Quoted 16 lines · Vladimir Sementsov-Ogievskiy
hbitmap_resetis 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 4reset(0, 1)# count becomes 2But 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
Signed-off-by Vladimir Sementsov-Ogievskiy <[email protected]>---
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, asdo_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’sdo_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
Quoted 33 lines · Vladimir Sementsov-Ogievskiy
Quoted 32 lines · Max Reitz
Quoted 16 lines · Vladimir Sementsov-Ogievskiy
hbitmap_resetis 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 4reset(0, 1)# count becomes 2But 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
Signed-off-by Vladimir Sementsov-Ogievskiy <[email protected]>---
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, asdo_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’sdo_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
Quoted 41 lines · John Snow
Quoted 38 lines · Vladimir Sementsov-Ogievskiy
Quoted 36 lines · Max Reitz
Quoted 16 lines · Vladimir Sementsov-Ogievskiy
hbitmap_resetis 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 4reset(0, 1)# count becomes 2But 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
Signed-off-by Vladimir Sementsov-Ogievskiy <[email protected]>---
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, asdo_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’sdo_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
Quoted 56 lines · Vladimir Sementsov-Ogievskiy
hbitmap_resetis 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 4reset(0, 1)# count becomes 2But 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 <[email protected]>---
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, asdo_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@@ -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@@ -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) {
Quoted 70 lines · Max Reitz
Quoted 56 lines · Vladimir Sementsov-Ogievskiy
hbitmap_resetis 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 4reset(0, 1)# count becomes 2But 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 <[email protected]>---
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, asdo_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@@ -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@@ -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 ofcluster_size, which may or may not end up at the image end; andhbitmap_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