* [Qemu-devel] [PATCH v3 0/8] dirty-bitmap: rewrite bdrv_dirty_iter_next_area
@ 2018-08-14 12:14 Vladimir Sementsov-Ogievskiy
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 1/8] dirty-bitmap: improve bdrv_dirty_bitmap_next_zero Vladimir Sementsov-Ogievskiy
` (8 more replies)
0 siblings, 9 replies; 25+ messages in thread
From: Vladimir Sementsov-Ogievskiy @ 2018-08-14 12:14 UTC (permalink / raw)
To: qemu-devel, qemu-block
Cc: pbonzini, eblake, jsnow, famz, mreitz, kwolf, jcody, vsementsov, den
Hi all.
1. bdrv_dirty_iter_next_area don't use hbitmap_next_zero and uses
inefficient loop instead. Let's improve it.
2. bdrv_dirty_iter_next_area don't handle unaligned offset and
max_offset correctly. I'm not sure that it is a real bug. But if it is,
we need these series in 3.0.
Details are in 05 commit message.
v3:
01: - change interface to start/end, and -1 as special end-marker instead of 0
- "not found" for invalid regions instead of assert
02: rebase on 01 changes
03: - fix mistake in hbitmap_iter_init arguments (mistake in
hbitmap_next_zero arguments is fixed automatically due to 01 changes)
04: new
v2:
01: - improve comment
- s/bytes/count/
- fix forgotten function call in test
- introduce orig_size field here for HBitmap,
make checking in hbitmap_next_zero more effective and safe
02: new
03: - orig_size already introduced in 01
- fix hbitmap_next_dirty_area to not return value less than
offset on unaligned requests
Vladimir Sementsov-Ogievskiy (8):
dirty-bitmap: improve bdrv_dirty_bitmap_next_zero
tests: add tests for hbitmap_next_zero with specified end parameter
dirty-bitmap: add bdrv_dirty_bitmap_next_dirty_area
tests: add tests for hbitmap_next_dirty_area
block/mirror: fix and improve do_sync_target_write
Revert "block/dirty-bitmap: Add bdrv_dirty_iter_next_area"
Revert "test-hbitmap: Add non-advancing iter_next tests"
Revert "hbitmap: Add @advance param to hbitmap_iter_next()"
include/block/dirty-bitmap.h | 8 +-
include/qemu/hbitmap.h | 30 ++++++--
block/backup.c | 4 +-
block/dirty-bitmap.c | 69 +++--------------
block/mirror.c | 16 ++--
nbd/server.c | 2 +-
tests/test-hbitmap.c | 176 ++++++++++++++++++++++++++++++++++++-------
util/hbitmap.c | 73 +++++++++++++++---
8 files changed, 258 insertions(+), 120 deletions(-)
--
2.11.1
^ permalink raw reply [flat|nested] 25+ messages in thread
* [Qemu-devel] [PATCH v3 1/8] dirty-bitmap: improve bdrv_dirty_bitmap_next_zero
2018-08-14 12:14 [Qemu-devel] [PATCH v3 0/8] dirty-bitmap: rewrite bdrv_dirty_iter_next_area Vladimir Sementsov-Ogievskiy
@ 2018-08-14 12:14 ` Vladimir Sementsov-Ogievskiy
2018-09-07 21:49 ` John Snow
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 2/8] tests: add tests for hbitmap_next_zero with specified end parameter Vladimir Sementsov-Ogievskiy
` (7 subsequent siblings)
8 siblings, 1 reply; 25+ messages in thread
From: Vladimir Sementsov-Ogievskiy @ 2018-08-14 12:14 UTC (permalink / raw)
To: qemu-devel, qemu-block
Cc: pbonzini, eblake, jsnow, famz, mreitz, kwolf, jcody, vsementsov, den
Add bytes parameter to the function, to limit searched range.
Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
include/block/dirty-bitmap.h | 3 ++-
include/qemu/hbitmap.h | 10 ++++++++--
block/backup.c | 2 +-
block/dirty-bitmap.c | 5 +++--
nbd/server.c | 2 +-
tests/test-hbitmap.c | 2 +-
util/hbitmap.c | 25 ++++++++++++++++++++-----
7 files changed, 36 insertions(+), 13 deletions(-)
diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
index 259bd27c40..27f5299c4e 100644
--- a/include/block/dirty-bitmap.h
+++ b/include/block/dirty-bitmap.h
@@ -98,7 +98,8 @@ bool bdrv_has_changed_persistent_bitmaps(BlockDriverState *bs);
BdrvDirtyBitmap *bdrv_dirty_bitmap_next(BlockDriverState *bs,
BdrvDirtyBitmap *bitmap);
char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp);
-int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start);
+int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start,
+ int64_t end);
BdrvDirtyBitmap *bdrv_reclaim_dirty_bitmap_locked(BlockDriverState *bs,
BdrvDirtyBitmap *bitmap,
Error **errp);
diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
index ddca52c48e..fe4dfde27a 100644
--- a/include/qemu/hbitmap.h
+++ b/include/qemu/hbitmap.h
@@ -295,10 +295,16 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
/* hbitmap_next_zero:
* @hb: The HBitmap to operate on
* @start: The bit to start from.
+ * @end: End of range to search in. If @end is -1, search up to the bitmap
+ * end.
*
- * Find next not dirty bit.
+ * Find next not dirty bit within range [@start, @end), or from
+ * @start to the bitmap end if @end is -1. If not found, return -1.
+ *
+ * @end may be greater than original bitmap size, in this case, search up to
+ * the bitmap end.
*/
-int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start);
+int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t end);
/* hbitmap_create_meta:
* Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap.
diff --git a/block/backup.c b/block/backup.c
index 8630d32926..9bfd3f7189 100644
--- a/block/backup.c
+++ b/block/backup.c
@@ -458,7 +458,7 @@ static void backup_incremental_init_copy_bitmap(BackupBlockJob *job)
break;
}
- offset = bdrv_dirty_bitmap_next_zero(job->sync_bitmap, offset);
+ offset = bdrv_dirty_bitmap_next_zero(job->sync_bitmap, offset, -1);
if (offset == -1) {
hbitmap_set(job->copy_bitmap, cluster, end - cluster);
break;
diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
index c9b8a6fd52..037ae62726 100644
--- a/block/dirty-bitmap.c
+++ b/block/dirty-bitmap.c
@@ -785,9 +785,10 @@ char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp)
return hbitmap_sha256(bitmap->bitmap, errp);
}
-int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset)
+int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset,
+ int64_t end)
{
- return hbitmap_next_zero(bitmap->bitmap, offset);
+ return hbitmap_next_zero(bitmap->bitmap, offset, end);
}
void bdrv_merge_dirty_bitmap(BdrvDirtyBitmap *dest, const BdrvDirtyBitmap *src,
diff --git a/nbd/server.c b/nbd/server.c
index ea5fe0eb33..07920d123b 100644
--- a/nbd/server.c
+++ b/nbd/server.c
@@ -1952,7 +1952,7 @@ static unsigned int bitmap_to_extents(BdrvDirtyBitmap *bitmap, uint64_t offset,
assert(begin < overall_end && nb_extents);
while (begin < overall_end && i < nb_extents) {
if (dirty) {
- end = bdrv_dirty_bitmap_next_zero(bitmap, begin);
+ end = bdrv_dirty_bitmap_next_zero(bitmap, begin, -1);
} else {
bdrv_set_dirty_iter(it, begin);
end = bdrv_dirty_iter_next(it);
diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
index 5e67ac1d3a..6b6a40bddd 100644
--- a/tests/test-hbitmap.c
+++ b/tests/test-hbitmap.c
@@ -939,7 +939,7 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data,
static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start)
{
- int64_t ret1 = hbitmap_next_zero(data->hb, start);
+ int64_t ret1 = hbitmap_next_zero(data->hb, start, -1);
int64_t ret2 = start;
for ( ; ret2 < data->size && hbitmap_get(data->hb, ret2); ret2++) {
;
diff --git a/util/hbitmap.c b/util/hbitmap.c
index bcd304041a..1687372504 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -53,6 +53,9 @@
*/
struct HBitmap {
+ /* Size of the bitmap, as requested in hbitmap_alloc. */
+ uint64_t orig_size;
+
/* Number of total bits in the bottom level. */
uint64_t size;
@@ -192,16 +195,26 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first)
}
}
-int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start)
+int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t end)
{
size_t pos = (start >> hb->granularity) >> BITS_PER_LEVEL;
unsigned long *last_lev = hb->levels[HBITMAP_LEVELS - 1];
- uint64_t sz = hb->sizes[HBITMAP_LEVELS - 1];
unsigned long cur = last_lev[pos];
- unsigned start_bit_offset =
- (start >> hb->granularity) & (BITS_PER_LONG - 1);
+ unsigned start_bit_offset;
+ uint64_t end_bit, sz;
int64_t res;
+ if (start >= hb->orig_size || (end != -1 && end <= start)) {
+ return -1;
+ }
+
+ end_bit = end == -1 ? hb->size : ((end - 1) >> hb->granularity) + 1;
+ sz = (end_bit + BITS_PER_LONG - 1) >> BITS_PER_LEVEL;
+
+ /* There may be some zero bits in @cur before @start. We are not interested
+ * in them, let's set them.
+ */
+ start_bit_offset = (start >> hb->granularity) & (BITS_PER_LONG - 1);
cur |= (1UL << start_bit_offset) - 1;
assert((start >> hb->granularity) < hb->size);
@@ -218,7 +231,7 @@ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start)
}
res = (pos << BITS_PER_LEVEL) + ctol(cur);
- if (res >= hb->size) {
+ if (res >= end_bit) {
return -1;
}
@@ -652,6 +665,8 @@ HBitmap *hbitmap_alloc(uint64_t size, int granularity)
HBitmap *hb = g_new0(struct HBitmap, 1);
unsigned i;
+ hb->orig_size = size;
+
assert(granularity >= 0 && granularity < 64);
size = (size + (1ULL << granularity) - 1) >> granularity;
assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
--
2.11.1
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [Qemu-devel] [PATCH v3 2/8] tests: add tests for hbitmap_next_zero with specified end parameter
2018-08-14 12:14 [Qemu-devel] [PATCH v3 0/8] dirty-bitmap: rewrite bdrv_dirty_iter_next_area Vladimir Sementsov-Ogievskiy
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 1/8] dirty-bitmap: improve bdrv_dirty_bitmap_next_zero Vladimir Sementsov-Ogievskiy
@ 2018-08-14 12:14 ` Vladimir Sementsov-Ogievskiy
2018-09-07 21:55 ` John Snow
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 3/8] dirty-bitmap: add bdrv_dirty_bitmap_next_dirty_area Vladimir Sementsov-Ogievskiy
` (6 subsequent siblings)
8 siblings, 1 reply; 25+ messages in thread
From: Vladimir Sementsov-Ogievskiy @ 2018-08-14 12:14 UTC (permalink / raw)
To: qemu-devel, qemu-block
Cc: pbonzini, eblake, jsnow, famz, mreitz, kwolf, jcody, vsementsov, den
Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
tests/test-hbitmap.c | 32 ++++++++++++++++++++++++++++----
1 file changed, 28 insertions(+), 4 deletions(-)
diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
index 6b6a40bddd..dddb67c3c5 100644
--- a/tests/test-hbitmap.c
+++ b/tests/test-hbitmap.c
@@ -937,31 +937,49 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data,
check_hbitmap_iter_next(&hbi);
}
-static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start)
+static void test_hbitmap_next_zero_check_range(TestHBitmapData *data,
+ int64_t start,
+ int64_t count)
{
- int64_t ret1 = hbitmap_next_zero(data->hb, start, -1);
+ int64_t ret1 = hbitmap_next_zero(data->hb, start,
+ count == -1 ? -1 : start + count);
int64_t ret2 = start;
- for ( ; ret2 < data->size && hbitmap_get(data->hb, ret2); ret2++) {
+ int64_t end = count == -1 ? data->size : start + count;
+
+ for ( ; ret2 < end && hbitmap_get(data->hb, ret2); ret2++) {
;
}
- if (ret2 == data->size) {
+ if (ret2 == end) {
ret2 = -1;
}
g_assert_cmpint(ret1, ==, ret2);
}
+static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start)
+{
+ test_hbitmap_next_zero_check_range(data, start, 0);
+}
+
static void test_hbitmap_next_zero_do(TestHBitmapData *data, int granularity)
{
hbitmap_test_init(data, L3, granularity);
test_hbitmap_next_zero_check(data, 0);
test_hbitmap_next_zero_check(data, L3 - 1);
+ test_hbitmap_next_zero_check_range(data, 0, 1);
+ test_hbitmap_next_zero_check_range(data, L3 - 1, 1);
hbitmap_set(data->hb, L2, 1);
test_hbitmap_next_zero_check(data, 0);
test_hbitmap_next_zero_check(data, L2 - 1);
test_hbitmap_next_zero_check(data, L2);
test_hbitmap_next_zero_check(data, L2 + 1);
+ test_hbitmap_next_zero_check_range(data, 0, 1);
+ test_hbitmap_next_zero_check_range(data, 0, L2);
+ test_hbitmap_next_zero_check_range(data, L2 - 1, 1);
+ test_hbitmap_next_zero_check_range(data, L2 - 1, 2);
+ test_hbitmap_next_zero_check_range(data, L2, 1);
+ test_hbitmap_next_zero_check_range(data, L2 + 1, 1);
hbitmap_set(data->hb, L2 + 5, L1);
test_hbitmap_next_zero_check(data, 0);
@@ -970,6 +988,10 @@ static void test_hbitmap_next_zero_do(TestHBitmapData *data, int granularity)
test_hbitmap_next_zero_check(data, L2 + 5);
test_hbitmap_next_zero_check(data, L2 + L1 - 1);
test_hbitmap_next_zero_check(data, L2 + L1);
+ test_hbitmap_next_zero_check_range(data, L2, 6);
+ test_hbitmap_next_zero_check_range(data, L2 + 1, 3);
+ test_hbitmap_next_zero_check_range(data, L2 + 4, L1);
+ test_hbitmap_next_zero_check_range(data, L2 + 5, L1);
hbitmap_set(data->hb, L2 * 2, L3 - L2 * 2);
test_hbitmap_next_zero_check(data, L2 * 2 - L1);
@@ -977,6 +999,8 @@ static void test_hbitmap_next_zero_do(TestHBitmapData *data, int granularity)
test_hbitmap_next_zero_check(data, L2 * 2 - 1);
test_hbitmap_next_zero_check(data, L2 * 2);
test_hbitmap_next_zero_check(data, L3 - 1);
+ test_hbitmap_next_zero_check_range(data, L2 * 2 - L1, L1 + 1);
+ test_hbitmap_next_zero_check_range(data, L2 * 2, L2);
hbitmap_set(data->hb, 0, L3);
test_hbitmap_next_zero_check(data, 0);
--
2.11.1
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [Qemu-devel] [PATCH v3 3/8] dirty-bitmap: add bdrv_dirty_bitmap_next_dirty_area
2018-08-14 12:14 [Qemu-devel] [PATCH v3 0/8] dirty-bitmap: rewrite bdrv_dirty_iter_next_area Vladimir Sementsov-Ogievskiy
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 1/8] dirty-bitmap: improve bdrv_dirty_bitmap_next_zero Vladimir Sementsov-Ogievskiy
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 2/8] tests: add tests for hbitmap_next_zero with specified end parameter Vladimir Sementsov-Ogievskiy
@ 2018-08-14 12:14 ` Vladimir Sementsov-Ogievskiy
2018-09-10 20:42 ` John Snow
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 4/8] tests: add tests for hbitmap_next_dirty_area Vladimir Sementsov-Ogievskiy
` (5 subsequent siblings)
8 siblings, 1 reply; 25+ messages in thread
From: Vladimir Sementsov-Ogievskiy @ 2018-08-14 12:14 UTC (permalink / raw)
To: qemu-devel, qemu-block
Cc: pbonzini, eblake, jsnow, famz, mreitz, kwolf, jcody, vsementsov, den
The function alters bdrv_dirty_iter_next_area(), which is wrong and
less efficient (see further commit
"block/mirror: fix and improve do_sync_target_write" for description).
Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
include/block/dirty-bitmap.h | 3 +++
include/qemu/hbitmap.h | 15 +++++++++++++++
block/dirty-bitmap.c | 7 +++++++
util/hbitmap.c | 38 ++++++++++++++++++++++++++++++++++++++
4 files changed, 63 insertions(+)
diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
index 27f5299c4e..cb9162fa7e 100644
--- a/include/block/dirty-bitmap.h
+++ b/include/block/dirty-bitmap.h
@@ -100,6 +100,9 @@ BdrvDirtyBitmap *bdrv_dirty_bitmap_next(BlockDriverState *bs,
char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp);
int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start,
int64_t end);
+bool bdrv_dirty_bitmap_next_dirty_area(BdrvDirtyBitmap *bitmap,
+ uint64_t *offset, uint64_t end,
+ uint64_t *length);
BdrvDirtyBitmap *bdrv_reclaim_dirty_bitmap_locked(BlockDriverState *bs,
BdrvDirtyBitmap *bitmap,
Error **errp);
diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
index fe4dfde27a..7800317bf3 100644
--- a/include/qemu/hbitmap.h
+++ b/include/qemu/hbitmap.h
@@ -306,6 +306,21 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
*/
int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t end);
+/* hbitmap_next_dirty_area:
+ * @hb: The HBitmap to operate on
+ * @offset: in-out parameter.
+ * in: the offset to start from
+ * out: (if area found) start of found area
+ * @end: end of requested region. (*@offset + *@length) will be <= @end
+ * @length: length of found area
+ *
+ * If dirty area found within [@offset, @end), returns true and sets @offset
+ * and @length appropriately. Otherwise returns true and leaves @offset and
+ * @length unchanged.
+ */
+bool hbitmap_next_dirty_area(const HBitmap *hb, uint64_t *offset,
+ uint64_t end, uint64_t *length);
+
/* hbitmap_create_meta:
* Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap.
* The caller owns the created bitmap and must call hbitmap_free_meta(hb) to
diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
index 037ae62726..4af20a1beb 100644
--- a/block/dirty-bitmap.c
+++ b/block/dirty-bitmap.c
@@ -791,6 +791,13 @@ int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset,
return hbitmap_next_zero(bitmap->bitmap, offset, end);
}
+bool bdrv_dirty_bitmap_next_dirty_area(BdrvDirtyBitmap *bitmap,
+ uint64_t *offset, uint64_t end,
+ uint64_t *length)
+{
+ return hbitmap_next_dirty_area(bitmap->bitmap, offset, end, length);
+}
+
void bdrv_merge_dirty_bitmap(BdrvDirtyBitmap *dest, const BdrvDirtyBitmap *src,
Error **errp)
{
diff --git a/util/hbitmap.c b/util/hbitmap.c
index 1687372504..bf88c1223e 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -244,6 +244,44 @@ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t end)
return res;
}
+bool hbitmap_next_dirty_area(const HBitmap *hb, uint64_t *offset,
+ uint64_t end, uint64_t *length)
+{
+ HBitmapIter hbi;
+ int64_t off1, off0;
+ uint32_t granularity = 1UL << hb->granularity;
+
+ if (end == 0) {
+ end = hb->orig_size;
+ }
+
+ hbitmap_iter_init(&hbi, hb, *offset);
+ off1 = hbitmap_iter_next(&hbi, true);
+
+ if (off1 < 0 || off1 >= end) {
+ return false;
+ }
+
+ if (off1 + granularity >= end) {
+ if (off1 > *offset) {
+ *offset = off1;
+ }
+ *length = end - *offset;
+ return true;
+ }
+
+ off0 = hbitmap_next_zero(hb, off1 + granularity, end);
+ if (off0 < 0) {
+ off0 = end;
+ }
+
+ if (off1 > *offset) {
+ *offset = off1;
+ }
+ *length = off0 - *offset;
+ return true;
+}
+
bool hbitmap_empty(const HBitmap *hb)
{
return hb->count == 0;
--
2.11.1
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [Qemu-devel] [PATCH v3 4/8] tests: add tests for hbitmap_next_dirty_area
2018-08-14 12:14 [Qemu-devel] [PATCH v3 0/8] dirty-bitmap: rewrite bdrv_dirty_iter_next_area Vladimir Sementsov-Ogievskiy
` (2 preceding siblings ...)
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 3/8] dirty-bitmap: add bdrv_dirty_bitmap_next_dirty_area Vladimir Sementsov-Ogievskiy
@ 2018-08-14 12:14 ` Vladimir Sementsov-Ogievskiy
2018-09-10 20:45 ` John Snow
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 5/8] block/mirror: fix and improve do_sync_target_write Vladimir Sementsov-Ogievskiy
` (4 subsequent siblings)
8 siblings, 1 reply; 25+ messages in thread
From: Vladimir Sementsov-Ogievskiy @ 2018-08-14 12:14 UTC (permalink / raw)
To: qemu-devel, qemu-block
Cc: pbonzini, eblake, jsnow, famz, mreitz, kwolf, jcody, vsementsov, den
Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
tests/test-hbitmap.c | 106 +++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 106 insertions(+)
diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
index dddb67c3c5..af5142b481 100644
--- a/tests/test-hbitmap.c
+++ b/tests/test-hbitmap.c
@@ -1016,6 +1016,105 @@ static void test_hbitmap_next_zero_4(TestHBitmapData *data, const void *unused)
test_hbitmap_next_zero_do(data, 4);
}
+static void test_hbitmap_next_dirty_area_check(TestHBitmapData *data,
+ uint64_t offset,
+ uint64_t count)
+{
+ uint64_t off1, off2;
+ uint64_t len1 = 0, len2 = 0;
+ bool ret1, ret2;
+ int64_t end;
+
+ off1 = offset;
+ end = count ? offset + count : 0;
+ ret1 = hbitmap_next_dirty_area(data->hb, &off1, end, &len1);
+
+ end = count ? offset + count : data->size;
+
+ for (off2 = offset; off2 < end && !hbitmap_get(data->hb, off2); off2++) {
+ ;
+ }
+
+ for (len2 = 1; off2 + len2 < end && hbitmap_get(data->hb, off2 + len2);
+ len2++)
+ {
+ }
+
+ ret2 = off2 < end;
+ if (!ret2) {
+ /* leave unchanged */
+ off2 = offset;
+ len2 = 0;
+ }
+
+ g_assert_cmpint(ret1, ==, ret2);
+ g_assert_cmpint(off1, ==, off2);
+ g_assert_cmpint(len1, ==, len2);
+}
+
+static void test_hbitmap_next_dirty_area_do(TestHBitmapData *data,
+ int granularity)
+{
+ hbitmap_test_init(data, L3, granularity);
+ test_hbitmap_next_dirty_area_check(data, 0, 0);
+ test_hbitmap_next_dirty_area_check(data, 0, 1);
+ test_hbitmap_next_dirty_area_check(data, L3 - 1, 1);
+
+ hbitmap_set(data->hb, L2, 1);
+ test_hbitmap_next_dirty_area_check(data, 0, 1);
+ test_hbitmap_next_dirty_area_check(data, 0, L2);
+ test_hbitmap_next_dirty_area_check(data, 0, 0);
+ test_hbitmap_next_dirty_area_check(data, L2 - 1, 0);
+ test_hbitmap_next_dirty_area_check(data, L2 - 1, 1);
+ test_hbitmap_next_dirty_area_check(data, L2 - 1, 2);
+ test_hbitmap_next_dirty_area_check(data, L2 - 1, 3);
+ test_hbitmap_next_dirty_area_check(data, L2, 0);
+ test_hbitmap_next_dirty_area_check(data, L2, 1);
+ test_hbitmap_next_dirty_area_check(data, L2 + 1, 1);
+
+ hbitmap_set(data->hb, L2 + 5, L1);
+ test_hbitmap_next_dirty_area_check(data, 0, 0);
+ test_hbitmap_next_dirty_area_check(data, L2 - 2, 8);
+ test_hbitmap_next_dirty_area_check(data, L2 + 1, 5);
+ test_hbitmap_next_dirty_area_check(data, L2 + 1, 3);
+ test_hbitmap_next_dirty_area_check(data, L2 + 4, L1);
+ test_hbitmap_next_dirty_area_check(data, L2 + 5, L1);
+ test_hbitmap_next_dirty_area_check(data, L2 + 7, L1);
+ test_hbitmap_next_dirty_area_check(data, L2 + L1, L1);
+ test_hbitmap_next_dirty_area_check(data, L2, 0);
+ test_hbitmap_next_dirty_area_check(data, L2 + 1, 0);
+
+ hbitmap_set(data->hb, L2 * 2, L3 - L2 * 2);
+ test_hbitmap_next_dirty_area_check(data, 0, 0);
+ test_hbitmap_next_dirty_area_check(data, L2, 0);
+ test_hbitmap_next_dirty_area_check(data, L2 + 1, 0);
+ test_hbitmap_next_dirty_area_check(data, L2 + 5 + L1 - 1, 0);
+ test_hbitmap_next_dirty_area_check(data, L2 + 5 + L1, 5);
+ test_hbitmap_next_dirty_area_check(data, L2 * 2 - L1, L1 + 1);
+ test_hbitmap_next_dirty_area_check(data, L2 * 2, L2);
+
+ hbitmap_set(data->hb, 0, L3);
+ test_hbitmap_next_dirty_area_check(data, 0, 0);
+}
+
+static void test_hbitmap_next_dirty_area_0(TestHBitmapData *data,
+ const void *unused)
+{
+ test_hbitmap_next_dirty_area_do(data, 0);
+}
+
+static void test_hbitmap_next_dirty_area_1(TestHBitmapData *data,
+ const void *unused)
+{
+ test_hbitmap_next_dirty_area_do(data, 1);
+}
+
+static void test_hbitmap_next_dirty_area_4(TestHBitmapData *data,
+ const void *unused)
+{
+ test_hbitmap_next_dirty_area_do(data, 4);
+}
+
int main(int argc, char **argv)
{
g_test_init(&argc, &argv, NULL);
@@ -1082,6 +1181,13 @@ int main(int argc, char **argv)
hbitmap_test_add("/hbitmap/next_zero/next_zero_4",
test_hbitmap_next_zero_4);
+ hbitmap_test_add("/hbitmap/next_dirty_area/next_dirty_area_0",
+ test_hbitmap_next_dirty_area_0);
+ hbitmap_test_add("/hbitmap/next_dirty_area/next_dirty_area_1",
+ test_hbitmap_next_dirty_area_1);
+ hbitmap_test_add("/hbitmap/next_dirty_area/next_dirty_area_4",
+ test_hbitmap_next_dirty_area_4);
+
g_test_run();
return 0;
--
2.11.1
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [Qemu-devel] [PATCH v3 5/8] block/mirror: fix and improve do_sync_target_write
2018-08-14 12:14 [Qemu-devel] [PATCH v3 0/8] dirty-bitmap: rewrite bdrv_dirty_iter_next_area Vladimir Sementsov-Ogievskiy
` (3 preceding siblings ...)
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 4/8] tests: add tests for hbitmap_next_dirty_area Vladimir Sementsov-Ogievskiy
@ 2018-08-14 12:14 ` Vladimir Sementsov-Ogievskiy
2018-09-10 20:51 ` John Snow
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 6/8] Revert "block/dirty-bitmap: Add bdrv_dirty_iter_next_area" Vladimir Sementsov-Ogievskiy
` (3 subsequent siblings)
8 siblings, 1 reply; 25+ messages in thread
From: Vladimir Sementsov-Ogievskiy @ 2018-08-14 12:14 UTC (permalink / raw)
To: qemu-devel, qemu-block
Cc: pbonzini, eblake, jsnow, famz, mreitz, kwolf, jcody, vsementsov, den
Use bdrv_dirty_bitmap_next_dirty_area() instead of
bdrv_dirty_iter_next_area(), because of the following problems of
bdrv_dirty_iter_next_area():
1. Using HBitmap iterators we should carefully handle unaligned offset,
as first call to hbitmap_iter_next() may return a value less than
original offset (actually, it will be original offset rounded down to
bitmap granularity). This handling is not done in
do_sync_target_write().
2. bdrv_dirty_iter_next_area() handles unaligned max_offset
incorrectly:
look at the code:
if (max_offset == iter->bitmap->size) {
/* If max_offset points to the image end, round it up by the
* bitmap granularity */
gran_max_offset = ROUND_UP(max_offset, granularity);
} else {
gran_max_offset = max_offset;
}
ret = hbitmap_iter_next(&iter->hbi, false);
if (ret < 0 || ret + granularity > gran_max_offset) {
return false;
}
and assume that max_offset != iter->bitmap->size but still unaligned.
if 0 < ret < max_offset we found dirty area, but the function can
return false in this case (if ret + granularity > max_offset).
3. bdrv_dirty_iter_next_area() uses inefficient loop to find the end of
the dirty area. Let's use more efficient hbitmap_next_zero instead
(bdrv_dirty_bitmap_next_dirty_area() do so)
Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
block/mirror.c | 16 +++++++---------
1 file changed, 7 insertions(+), 9 deletions(-)
diff --git a/block/mirror.c b/block/mirror.c
index b48c3f8cf5..d2806812c8 100644
--- a/block/mirror.c
+++ b/block/mirror.c
@@ -1167,25 +1167,22 @@ static void do_sync_target_write(MirrorBlockJob *job, MirrorMethod method,
uint64_t offset, uint64_t bytes,
QEMUIOVector *qiov, int flags)
{
- BdrvDirtyBitmapIter *iter;
QEMUIOVector target_qiov;
- uint64_t dirty_offset;
- int dirty_bytes;
+ uint64_t dirty_offset = offset;
+ uint64_t dirty_bytes;
if (qiov) {
qemu_iovec_init(&target_qiov, qiov->niov);
}
- iter = bdrv_dirty_iter_new(job->dirty_bitmap);
- bdrv_set_dirty_iter(iter, offset);
-
while (true) {
bool valid_area;
int ret;
bdrv_dirty_bitmap_lock(job->dirty_bitmap);
- valid_area = bdrv_dirty_iter_next_area(iter, offset + bytes,
- &dirty_offset, &dirty_bytes);
+ valid_area = bdrv_dirty_bitmap_next_dirty_area(
+ job->dirty_bitmap, &dirty_offset,
+ MIN(offset + bytes, dirty_offset + INT_MAX), &dirty_bytes);
if (!valid_area) {
bdrv_dirty_bitmap_unlock(job->dirty_bitmap);
break;
@@ -1241,9 +1238,10 @@ static void do_sync_target_write(MirrorBlockJob *job, MirrorMethod method,
break;
}
}
+
+ dirty_offset += dirty_bytes;
}
- bdrv_dirty_iter_free(iter);
if (qiov) {
qemu_iovec_destroy(&target_qiov);
}
--
2.11.1
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [Qemu-devel] [PATCH v3 6/8] Revert "block/dirty-bitmap: Add bdrv_dirty_iter_next_area"
2018-08-14 12:14 [Qemu-devel] [PATCH v3 0/8] dirty-bitmap: rewrite bdrv_dirty_iter_next_area Vladimir Sementsov-Ogievskiy
` (4 preceding siblings ...)
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 5/8] block/mirror: fix and improve do_sync_target_write Vladimir Sementsov-Ogievskiy
@ 2018-08-14 12:14 ` Vladimir Sementsov-Ogievskiy
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 7/8] Revert "test-hbitmap: Add non-advancing iter_next tests" Vladimir Sementsov-Ogievskiy
` (2 subsequent siblings)
8 siblings, 0 replies; 25+ messages in thread
From: Vladimir Sementsov-Ogievskiy @ 2018-08-14 12:14 UTC (permalink / raw)
To: qemu-devel, qemu-block
Cc: pbonzini, eblake, jsnow, famz, mreitz, kwolf, jcody, vsementsov, den
This reverts commit 72d10a94213a954ad569095cb4491f2ae0853c40.
The function is unused now.
Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
include/block/dirty-bitmap.h | 2 --
block/dirty-bitmap.c | 55 --------------------------------------------
2 files changed, 57 deletions(-)
diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
index cb9162fa7e..20e1d86cb1 100644
--- a/include/block/dirty-bitmap.h
+++ b/include/block/dirty-bitmap.h
@@ -83,8 +83,6 @@ void bdrv_set_dirty_bitmap_locked(BdrvDirtyBitmap *bitmap,
void bdrv_reset_dirty_bitmap_locked(BdrvDirtyBitmap *bitmap,
int64_t offset, int64_t bytes);
int64_t bdrv_dirty_iter_next(BdrvDirtyBitmapIter *iter);
-bool bdrv_dirty_iter_next_area(BdrvDirtyBitmapIter *iter, uint64_t max_offset,
- uint64_t *offset, int *bytes);
void bdrv_set_dirty_iter(BdrvDirtyBitmapIter *hbi, int64_t offset);
int64_t bdrv_get_dirty_count(BdrvDirtyBitmap *bitmap);
int64_t bdrv_get_meta_dirty_count(BdrvDirtyBitmap *bitmap);
diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
index 4af20a1beb..d9333175b3 100644
--- a/block/dirty-bitmap.c
+++ b/block/dirty-bitmap.c
@@ -528,61 +528,6 @@ int64_t bdrv_dirty_iter_next(BdrvDirtyBitmapIter *iter)
return hbitmap_iter_next(&iter->hbi, true);
}
-/**
- * Return the next consecutively dirty area in the dirty bitmap
- * belonging to the given iterator @iter.
- *
- * @max_offset: Maximum value that may be returned for
- * *offset + *bytes
- * @offset: Will contain the start offset of the next dirty area
- * @bytes: Will contain the length of the next dirty area
- *
- * Returns: True if a dirty area could be found before max_offset
- * (which means that *offset and *bytes then contain valid
- * values), false otherwise.
- *
- * Note that @iter is never advanced if false is returned. If an area
- * is found (which means that true is returned), it will be advanced
- * past that area.
- */
-bool bdrv_dirty_iter_next_area(BdrvDirtyBitmapIter *iter, uint64_t max_offset,
- uint64_t *offset, int *bytes)
-{
- uint32_t granularity = bdrv_dirty_bitmap_granularity(iter->bitmap);
- uint64_t gran_max_offset;
- int64_t ret;
- int size;
-
- if (max_offset == iter->bitmap->size) {
- /* If max_offset points to the image end, round it up by the
- * bitmap granularity */
- gran_max_offset = ROUND_UP(max_offset, granularity);
- } else {
- gran_max_offset = max_offset;
- }
-
- ret = hbitmap_iter_next(&iter->hbi, false);
- if (ret < 0 || ret + granularity > gran_max_offset) {
- return false;
- }
-
- *offset = ret;
- size = 0;
-
- assert(granularity <= INT_MAX);
-
- do {
- /* Advance iterator */
- ret = hbitmap_iter_next(&iter->hbi, true);
- size += granularity;
- } while (ret + granularity <= gran_max_offset &&
- hbitmap_iter_next(&iter->hbi, false) == ret + granularity &&
- size <= INT_MAX - granularity);
-
- *bytes = MIN(size, max_offset - *offset);
- return true;
-}
-
/* Called within bdrv_dirty_bitmap_lock..unlock */
void bdrv_set_dirty_bitmap_locked(BdrvDirtyBitmap *bitmap,
int64_t offset, int64_t bytes)
--
2.11.1
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [Qemu-devel] [PATCH v3 7/8] Revert "test-hbitmap: Add non-advancing iter_next tests"
2018-08-14 12:14 [Qemu-devel] [PATCH v3 0/8] dirty-bitmap: rewrite bdrv_dirty_iter_next_area Vladimir Sementsov-Ogievskiy
` (5 preceding siblings ...)
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 6/8] Revert "block/dirty-bitmap: Add bdrv_dirty_iter_next_area" Vladimir Sementsov-Ogievskiy
@ 2018-08-14 12:14 ` Vladimir Sementsov-Ogievskiy
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 8/8] Revert "hbitmap: Add @advance param to hbitmap_iter_next()" Vladimir Sementsov-Ogievskiy
2018-08-16 7:35 ` [Qemu-devel] [PATCH v3 0/8] dirty-bitmap: rewrite bdrv_dirty_iter_next_area no-reply
8 siblings, 0 replies; 25+ messages in thread
From: Vladimir Sementsov-Ogievskiy @ 2018-08-14 12:14 UTC (permalink / raw)
To: qemu-devel, qemu-block
Cc: pbonzini, eblake, jsnow, famz, mreitz, kwolf, jcody, vsementsov, den
This reverts commit 269576848ec3d57d2d958cf5ac69b08c44adf816.
The functionality is unused. Drop tests.
Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
tests/test-hbitmap.c | 36 ++++++++++++------------------------
1 file changed, 12 insertions(+), 24 deletions(-)
diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
index af5142b481..5e43056970 100644
--- a/tests/test-hbitmap.c
+++ b/tests/test-hbitmap.c
@@ -30,18 +30,6 @@ typedef struct TestHBitmapData {
} TestHBitmapData;
-static int64_t check_hbitmap_iter_next(HBitmapIter *hbi)
-{
- int next0, next1;
-
- next0 = hbitmap_iter_next(hbi, false);
- next1 = hbitmap_iter_next(hbi, true);
-
- g_assert_cmpint(next0, ==, next1);
-
- return next0;
-}
-
/* Check that the HBitmap and the shadow bitmap contain the same data,
* ignoring the same "first" bits.
*/
@@ -58,7 +46,7 @@ static void hbitmap_test_check(TestHBitmapData *data,
i = first;
for (;;) {
- next = check_hbitmap_iter_next(&hbi);
+ next = hbitmap_iter_next(&hbi, true);
if (next < 0) {
next = data->size;
}
@@ -447,25 +435,25 @@ static void test_hbitmap_iter_granularity(TestHBitmapData *data,
/* Note that hbitmap_test_check has to be invoked manually in this test. */
hbitmap_test_init(data, 131072 << 7, 7);
hbitmap_iter_init(&hbi, data->hb, 0);
- g_assert_cmpint(check_hbitmap_iter_next(&hbi), <, 0);
+ g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
hbitmap_test_set(data, ((L2 + L1 + 1) << 7) + 8, 8);
hbitmap_iter_init(&hbi, data->hb, 0);
- g_assert_cmpint(check_hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
- g_assert_cmpint(check_hbitmap_iter_next(&hbi), <, 0);
+ g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, (L2 + L1 + 1) << 7);
+ g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
hbitmap_test_set(data, (131072 << 7) - 8, 8);
hbitmap_iter_init(&hbi, data->hb, 0);
- g_assert_cmpint(check_hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
- g_assert_cmpint(check_hbitmap_iter_next(&hbi), ==, 131071 << 7);
- g_assert_cmpint(check_hbitmap_iter_next(&hbi), <, 0);
+ g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, (L2 + L1 + 1) << 7);
+ g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, 131071 << 7);
+ g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
- g_assert_cmpint(check_hbitmap_iter_next(&hbi), ==, 131071 << 7);
- g_assert_cmpint(check_hbitmap_iter_next(&hbi), <, 0);
+ g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, 131071 << 7);
+ g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
}
static void hbitmap_test_set_boundary_bits(TestHBitmapData *data, ssize_t diff)
@@ -905,7 +893,7 @@ static void test_hbitmap_serialize_zeroes(TestHBitmapData *data,
for (i = 0; i < num_positions; i++) {
hbitmap_deserialize_zeroes(data->hb, positions[i], min_l1, true);
hbitmap_iter_init(&iter, data->hb, 0);
- next = check_hbitmap_iter_next(&iter);
+ next = hbitmap_iter_next(&iter, true);
if (i == num_positions - 1) {
g_assert_cmpint(next, ==, -1);
} else {
@@ -931,10 +919,10 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data,
hbitmap_iter_init(&hbi, data->hb, BITS_PER_LONG - 1);
- check_hbitmap_iter_next(&hbi);
+ hbitmap_iter_next(&hbi, true);
hbitmap_reset_all(data->hb);
- check_hbitmap_iter_next(&hbi);
+ hbitmap_iter_next(&hbi, true);
}
static void test_hbitmap_next_zero_check_range(TestHBitmapData *data,
--
2.11.1
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [Qemu-devel] [PATCH v3 8/8] Revert "hbitmap: Add @advance param to hbitmap_iter_next()"
2018-08-14 12:14 [Qemu-devel] [PATCH v3 0/8] dirty-bitmap: rewrite bdrv_dirty_iter_next_area Vladimir Sementsov-Ogievskiy
` (6 preceding siblings ...)
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 7/8] Revert "test-hbitmap: Add non-advancing iter_next tests" Vladimir Sementsov-Ogievskiy
@ 2018-08-14 12:14 ` Vladimir Sementsov-Ogievskiy
2018-09-10 20:53 ` John Snow
2018-08-16 7:35 ` [Qemu-devel] [PATCH v3 0/8] dirty-bitmap: rewrite bdrv_dirty_iter_next_area no-reply
8 siblings, 1 reply; 25+ messages in thread
From: Vladimir Sementsov-Ogievskiy @ 2018-08-14 12:14 UTC (permalink / raw)
To: qemu-devel, qemu-block
Cc: pbonzini, eblake, jsnow, famz, mreitz, kwolf, jcody, vsementsov, den
This reverts commit a33fbb4f8b64226becf502a123733776ce319b24.
The functionality is unused.
Note: in addition to automatic revert, drop second parameter in
hbitmap_iter_next() call from hbitmap_next_dirty_area() too.
Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
include/qemu/hbitmap.h | 5 +----
block/backup.c | 2 +-
block/dirty-bitmap.c | 2 +-
tests/test-hbitmap.c | 26 +++++++++++++-------------
util/hbitmap.c | 12 ++++--------
5 files changed, 20 insertions(+), 27 deletions(-)
diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
index 7800317bf3..6d205167ce 100644
--- a/include/qemu/hbitmap.h
+++ b/include/qemu/hbitmap.h
@@ -345,14 +345,11 @@ void hbitmap_free_meta(HBitmap *hb);
/**
* hbitmap_iter_next:
* @hbi: HBitmapIter to operate on.
- * @advance: If true, advance the iterator. Otherwise, the next call
- * of this function will return the same result (if that
- * position is still dirty).
*
* Return the next bit that is set in @hbi's associated HBitmap,
* or -1 if all remaining bits are zero.
*/
-int64_t hbitmap_iter_next(HBitmapIter *hbi, bool advance);
+int64_t hbitmap_iter_next(HBitmapIter *hbi);
/**
* hbitmap_iter_next_word:
diff --git a/block/backup.c b/block/backup.c
index 9bfd3f7189..f033148f21 100644
--- a/block/backup.c
+++ b/block/backup.c
@@ -421,7 +421,7 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
HBitmapIter hbi;
hbitmap_iter_init(&hbi, job->copy_bitmap, 0);
- while ((cluster = hbitmap_iter_next(&hbi, true)) != -1) {
+ while ((cluster = hbitmap_iter_next(&hbi)) != -1) {
do {
if (yield_and_check(job)) {
return 0;
diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
index d9333175b3..d0d602ff52 100644
--- a/block/dirty-bitmap.c
+++ b/block/dirty-bitmap.c
@@ -525,7 +525,7 @@ void bdrv_dirty_iter_free(BdrvDirtyBitmapIter *iter)
int64_t bdrv_dirty_iter_next(BdrvDirtyBitmapIter *iter)
{
- return hbitmap_iter_next(&iter->hbi, true);
+ return hbitmap_iter_next(&iter->hbi);
}
/* Called within bdrv_dirty_bitmap_lock..unlock */
diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
index 5e43056970..17a3c807de 100644
--- a/tests/test-hbitmap.c
+++ b/tests/test-hbitmap.c
@@ -46,7 +46,7 @@ static void hbitmap_test_check(TestHBitmapData *data,
i = first;
for (;;) {
- next = hbitmap_iter_next(&hbi, true);
+ next = hbitmap_iter_next(&hbi);
if (next < 0) {
next = data->size;
}
@@ -435,25 +435,25 @@ static void test_hbitmap_iter_granularity(TestHBitmapData *data,
/* Note that hbitmap_test_check has to be invoked manually in this test. */
hbitmap_test_init(data, 131072 << 7, 7);
hbitmap_iter_init(&hbi, data->hb, 0);
- g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
+ g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
hbitmap_test_set(data, ((L2 + L1 + 1) << 7) + 8, 8);
hbitmap_iter_init(&hbi, data->hb, 0);
- g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, (L2 + L1 + 1) << 7);
- g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
+ g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
+ g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
- g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
+ g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
hbitmap_test_set(data, (131072 << 7) - 8, 8);
hbitmap_iter_init(&hbi, data->hb, 0);
- g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, (L2 + L1 + 1) << 7);
- g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, 131071 << 7);
- g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
+ g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
+ g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
+ g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
- g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, 131071 << 7);
- g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
+ g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
+ g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
}
static void hbitmap_test_set_boundary_bits(TestHBitmapData *data, ssize_t diff)
@@ -893,7 +893,7 @@ static void test_hbitmap_serialize_zeroes(TestHBitmapData *data,
for (i = 0; i < num_positions; i++) {
hbitmap_deserialize_zeroes(data->hb, positions[i], min_l1, true);
hbitmap_iter_init(&iter, data->hb, 0);
- next = hbitmap_iter_next(&iter, true);
+ next = hbitmap_iter_next(&iter);
if (i == num_positions - 1) {
g_assert_cmpint(next, ==, -1);
} else {
@@ -919,10 +919,10 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data,
hbitmap_iter_init(&hbi, data->hb, BITS_PER_LONG - 1);
- hbitmap_iter_next(&hbi, true);
+ hbitmap_iter_next(&hbi);
hbitmap_reset_all(data->hb);
- hbitmap_iter_next(&hbi, true);
+ hbitmap_iter_next(&hbi);
}
static void test_hbitmap_next_zero_check_range(TestHBitmapData *data,
diff --git a/util/hbitmap.c b/util/hbitmap.c
index bf88c1223e..b00e05a85b 100644
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -144,7 +144,7 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi)
return cur;
}
-int64_t hbitmap_iter_next(HBitmapIter *hbi, bool advance)
+int64_t hbitmap_iter_next(HBitmapIter *hbi)
{
unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1] &
hbi->hb->levels[HBITMAP_LEVELS - 1][hbi->pos];
@@ -157,12 +157,8 @@ int64_t hbitmap_iter_next(HBitmapIter *hbi, bool advance)
}
}
- if (advance) {
- /* The next call will resume work from the next bit. */
- hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1);
- } else {
- hbi->cur[HBITMAP_LEVELS - 1] = cur;
- }
+ /* The next call will resume work from the next bit. */
+ hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1);
item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + ctzl(cur);
return item << hbi->granularity;
@@ -256,7 +252,7 @@ bool hbitmap_next_dirty_area(const HBitmap *hb, uint64_t *offset,
}
hbitmap_iter_init(&hbi, hb, *offset);
- off1 = hbitmap_iter_next(&hbi, true);
+ off1 = hbitmap_iter_next(&hbi);
if (off1 < 0 || off1 >= end) {
return false;
--
2.11.1
^ permalink raw reply related [flat|nested] 25+ messages in thread
* Re: [Qemu-devel] [PATCH v3 0/8] dirty-bitmap: rewrite bdrv_dirty_iter_next_area
2018-08-14 12:14 [Qemu-devel] [PATCH v3 0/8] dirty-bitmap: rewrite bdrv_dirty_iter_next_area Vladimir Sementsov-Ogievskiy
` (7 preceding siblings ...)
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 8/8] Revert "hbitmap: Add @advance param to hbitmap_iter_next()" Vladimir Sementsov-Ogievskiy
@ 2018-08-16 7:35 ` no-reply
8 siblings, 0 replies; 25+ messages in thread
From: no-reply @ 2018-08-16 7:35 UTC (permalink / raw)
To: vsementsov; +Cc: famz, qemu-devel, qemu-block, kwolf
Hi,
This series seems to have some coding style problems. See output below for
more information:
Type: series
Message-id: 20180814121443.33114-1-vsementsov@virtuozzo.com
Subject: [Qemu-devel] [PATCH v3 0/8] dirty-bitmap: rewrite bdrv_dirty_iter_next_area
=== TEST SCRIPT BEGIN ===
#!/bin/bash
BASE=base
n=1
total=$(git log --oneline $BASE.. | wc -l)
failed=0
git config --local diff.renamelimit 0
git config --local diff.renames True
git config --local diff.algorithm histogram
commits="$(git log --format=%H --reverse $BASE..)"
for c in $commits; do
echo "Checking PATCH $n/$total: $(git log -n 1 --format=%s $c)..."
if ! git show $c --format=email | ./scripts/checkpatch.pl --mailback -; then
failed=1
echo
fi
n=$((n+1))
done
exit $failed
=== TEST SCRIPT END ===
Updating 3c8cf5a9c21ff8782164d1def7f44bd888713384
Switched to a new branch 'test'
e8d4951adf Revert "hbitmap: Add @advance param to hbitmap_iter_next()"
f69ec3244d Revert "test-hbitmap: Add non-advancing iter_next tests"
c924e13bbe Revert "block/dirty-bitmap: Add bdrv_dirty_iter_next_area"
da911f4201 block/mirror: fix and improve do_sync_target_write
e4699ed90e tests: add tests for hbitmap_next_dirty_area
ad2af3fae8 dirty-bitmap: add bdrv_dirty_bitmap_next_dirty_area
b85dbbed91 tests: add tests for hbitmap_next_zero with specified end parameter
78a802d4d3 dirty-bitmap: improve bdrv_dirty_bitmap_next_zero
=== OUTPUT BEGIN ===
Checking PATCH 1/8: dirty-bitmap: improve bdrv_dirty_bitmap_next_zero...
Checking PATCH 2/8: tests: add tests for hbitmap_next_zero with specified end parameter...
Checking PATCH 3/8: dirty-bitmap: add bdrv_dirty_bitmap_next_dirty_area...
Checking PATCH 4/8: tests: add tests for hbitmap_next_dirty_area...
ERROR: suspect code indent for conditional statements (4, 4)
#36: FILE: tests/test-hbitmap.c:1038:
+ for (len2 = 1; off2 + len2 < end && hbitmap_get(data->hb, off2 + len2);
[...]
+ {
total: 1 errors, 0 warnings, 118 lines checked
Your patch has style problems, please review. If any of these errors
are false positives report them to the maintainer, see
CHECKPATCH in MAINTAINERS.
Checking PATCH 5/8: block/mirror: fix and improve do_sync_target_write...
Checking PATCH 6/8: Revert "block/dirty-bitmap: Add bdrv_dirty_iter_next_area"...
Checking PATCH 7/8: Revert "test-hbitmap: Add non-advancing iter_next tests"...
Checking PATCH 8/8: Revert "hbitmap: Add @advance param to hbitmap_iter_next()"...
=== OUTPUT END ===
Test command exited with code: 1
---
Email generated automatically by Patchew [http://patchew.org/].
Please send your feedback to patchew-devel@redhat.com
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [Qemu-devel] [PATCH v3 1/8] dirty-bitmap: improve bdrv_dirty_bitmap_next_zero
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 1/8] dirty-bitmap: improve bdrv_dirty_bitmap_next_zero Vladimir Sementsov-Ogievskiy
@ 2018-09-07 21:49 ` John Snow
2018-09-10 14:59 ` Eric Blake
2018-09-10 16:49 ` Vladimir Sementsov-Ogievskiy
0 siblings, 2 replies; 25+ messages in thread
From: John Snow @ 2018-09-07 21:49 UTC (permalink / raw)
To: Vladimir Sementsov-Ogievskiy, qemu-devel, qemu-block
Cc: kwolf, famz, jcody, mreitz, den, pbonzini
On 08/14/2018 08:14 AM, Vladimir Sementsov-Ogievskiy wrote:
> Add bytes parameter to the function, to limit searched range.
>
I'm going to assume that Eric Blake has been through here and commented
on the interface itself.
> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> ---
> include/block/dirty-bitmap.h | 3 ++-
> include/qemu/hbitmap.h | 10 ++++++++--
> block/backup.c | 2 +-
> block/dirty-bitmap.c | 5 +++--
> nbd/server.c | 2 +-
> tests/test-hbitmap.c | 2 +-
> util/hbitmap.c | 25 ++++++++++++++++++++-----
> 7 files changed, 36 insertions(+), 13 deletions(-)
>
> diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
> index 259bd27c40..27f5299c4e 100644
> --- a/include/block/dirty-bitmap.h
> +++ b/include/block/dirty-bitmap.h
> @@ -98,7 +98,8 @@ bool bdrv_has_changed_persistent_bitmaps(BlockDriverState *bs);
> BdrvDirtyBitmap *bdrv_dirty_bitmap_next(BlockDriverState *bs,
> BdrvDirtyBitmap *bitmap);
> char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp);
> -int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start);
> +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start,
> + int64_t end);
> BdrvDirtyBitmap *bdrv_reclaim_dirty_bitmap_locked(BlockDriverState *bs,
> BdrvDirtyBitmap *bitmap,
> Error **errp);
> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
> index ddca52c48e..fe4dfde27a 100644
> --- a/include/qemu/hbitmap.h
> +++ b/include/qemu/hbitmap.h
> @@ -295,10 +295,16 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
> /* hbitmap_next_zero:
> * @hb: The HBitmap to operate on
> * @start: The bit to start from.
> + * @end: End of range to search in. If @end is -1, search up to the bitmap
> + * end.
> *
> - * Find next not dirty bit.
> + * Find next not dirty bit within range [@start, @end), or from
> + * @start to the bitmap end if @end is -1. If not found, return -1.
> + *
> + * @end may be greater than original bitmap size, in this case, search up to
"original" bitmap size? I think that's just an implementation detail, we
can drop 'original' here, yes?
> + * the bitmap end.
> */
> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start);
> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t end);
>
The interface looks weird because we can define a 'start' that's beyond
the 'end'.
I realize that you need a signed integer for 'end' to signify EOF...
should we do a 'bytes' parameter instead? (Did you already do that in an
earlier version and we changed it?)
Well, it's not a big deal to me personally.
> /* hbitmap_create_meta:
> * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap.
> diff --git a/block/backup.c b/block/backup.c
> index 8630d32926..9bfd3f7189 100644
> --- a/block/backup.c
> +++ b/block/backup.c
> @@ -458,7 +458,7 @@ static void backup_incremental_init_copy_bitmap(BackupBlockJob *job)
> break;
> }
>
> - offset = bdrv_dirty_bitmap_next_zero(job->sync_bitmap, offset);
> + offset = bdrv_dirty_bitmap_next_zero(job->sync_bitmap, offset, -1);
> if (offset == -1) {
> hbitmap_set(job->copy_bitmap, cluster, end - cluster);
> break;
> diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
> index c9b8a6fd52..037ae62726 100644
> --- a/block/dirty-bitmap.c
> +++ b/block/dirty-bitmap.c
> @@ -785,9 +785,10 @@ char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp)
> return hbitmap_sha256(bitmap->bitmap, errp);
> }
>
> -int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset)
> +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset,
> + int64_t end)
> {
> - return hbitmap_next_zero(bitmap->bitmap, offset);
> + return hbitmap_next_zero(bitmap->bitmap, offset, end);
> }
>
> void bdrv_merge_dirty_bitmap(BdrvDirtyBitmap *dest, const BdrvDirtyBitmap *src,
> diff --git a/nbd/server.c b/nbd/server.c
> index ea5fe0eb33..07920d123b 100644
> --- a/nbd/server.c
> +++ b/nbd/server.c
> @@ -1952,7 +1952,7 @@ static unsigned int bitmap_to_extents(BdrvDirtyBitmap *bitmap, uint64_t offset,
> assert(begin < overall_end && nb_extents);
> while (begin < overall_end && i < nb_extents) {
> if (dirty) {
> - end = bdrv_dirty_bitmap_next_zero(bitmap, begin);
> + end = bdrv_dirty_bitmap_next_zero(bitmap, begin, -1);
> } else {
> bdrv_set_dirty_iter(it, begin);
> end = bdrv_dirty_iter_next(it);
> diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
> index 5e67ac1d3a..6b6a40bddd 100644
> --- a/tests/test-hbitmap.c
> +++ b/tests/test-hbitmap.c
> @@ -939,7 +939,7 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data,
>
> static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start)
> {
> - int64_t ret1 = hbitmap_next_zero(data->hb, start);
> + int64_t ret1 = hbitmap_next_zero(data->hb, start, -1);
> int64_t ret2 = start;
> for ( ; ret2 < data->size && hbitmap_get(data->hb, ret2); ret2++) {
> ;
> diff --git a/util/hbitmap.c b/util/hbitmap.c
> index bcd304041a..1687372504 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -53,6 +53,9 @@
> */
>
> struct HBitmap {
> + /* Size of the bitmap, as requested in hbitmap_alloc. */
> + uint64_t orig_size;
> +
> /* Number of total bits in the bottom level. */
> uint64_t size;
>
> @@ -192,16 +195,26 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first)
> }
> }
>
> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start)
> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t end)
> {
> size_t pos = (start >> hb->granularity) >> BITS_PER_LEVEL;
> unsigned long *last_lev = hb->levels[HBITMAP_LEVELS - 1];
> - uint64_t sz = hb->sizes[HBITMAP_LEVELS - 1];
> unsigned long cur = last_lev[pos];
> - unsigned start_bit_offset =
> - (start >> hb->granularity) & (BITS_PER_LONG - 1);
> + unsigned start_bit_offset;
> + uint64_t end_bit, sz;
> int64_t res;
>
> + if (start >= hb->orig_size || (end != -1 && end <= start)) {
> + return -1;
> + }
> +
> + end_bit = end == -1 ? hb->size : ((end - 1) >> hb->granularity) + 1;
> + sz = (end_bit + BITS_PER_LONG - 1) >> BITS_PER_LEVEL;
> +
> + /* There may be some zero bits in @cur before @start. We are not interested
> + * in them, let's set them.
> + */
> + start_bit_offset = (start >> hb->granularity) & (BITS_PER_LONG - 1);
> cur |= (1UL << start_bit_offset) - 1;
> assert((start >> hb->granularity) < hb->size);
>
> @@ -218,7 +231,7 @@ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start)
> }
>
> res = (pos << BITS_PER_LEVEL) + ctol(cur);
> - if (res >= hb->size) {
> + if (res >= end_bit) {
> return -1;
> }
>
> @@ -652,6 +665,8 @@ HBitmap *hbitmap_alloc(uint64_t size, int granularity)
> HBitmap *hb = g_new0(struct HBitmap, 1);
> unsigned i;
>
> + hb->orig_size = size;
> +
> assert(granularity >= 0 && granularity < 64);
> size = (size + (1ULL << granularity) - 1) >> granularity;
> assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
>
Despite my comments, I'm OK with or without changes.
Reviewed-by: John Snow <jsnow@redhat.com>
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [Qemu-devel] [PATCH v3 2/8] tests: add tests for hbitmap_next_zero with specified end parameter
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 2/8] tests: add tests for hbitmap_next_zero with specified end parameter Vladimir Sementsov-Ogievskiy
@ 2018-09-07 21:55 ` John Snow
0 siblings, 0 replies; 25+ messages in thread
From: John Snow @ 2018-09-07 21:55 UTC (permalink / raw)
To: Vladimir Sementsov-Ogievskiy, qemu-devel, qemu-block
Cc: kwolf, famz, jcody, mreitz, den, pbonzini, Eric Blake
On 08/14/2018 08:14 AM, Vladimir Sementsov-Ogievskiy wrote:
> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> ---
> tests/test-hbitmap.c | 32 ++++++++++++++++++++++++++++----
> 1 file changed, 28 insertions(+), 4 deletions(-)
>
> diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
> index 6b6a40bddd..dddb67c3c5 100644
> --- a/tests/test-hbitmap.c
> +++ b/tests/test-hbitmap.c
> @@ -937,31 +937,49 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data,
> check_hbitmap_iter_next(&hbi);
> }
>
> -static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start)
> +static void test_hbitmap_next_zero_check_range(TestHBitmapData *data,
> + int64_t start,
> + int64_t count)
Should this interface match the implementation? Because ...
> {
> - int64_t ret1 = hbitmap_next_zero(data->hb, start, -1);
> + int64_t ret1 = hbitmap_next_zero(data->hb, start,
> + count == -1 ? -1 : start + count);
I find it confusing that we use 0 as a sentinel value here and have to
swap it out with -1. If the interfaces matched this would read a little
cleaner, wouldn't it?
> int64_t ret2 = start;
> - for ( ; ret2 < data->size && hbitmap_get(data->hb, ret2); ret2++) {
> + int64_t end = count == -1 ? data->size : start + count;
> +
> + for ( ; ret2 < end && hbitmap_get(data->hb, ret2); ret2++) {
> ;
> }
> - if (ret2 == data->size) {
> + if (ret2 == end) {
> ret2 = -1;
> }
>
> g_assert_cmpint(ret1, ==, ret2);
> }
>
> +static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start)
> +{
> + test_hbitmap_next_zero_check_range(data, start, 0);
> +}
> +
> static void test_hbitmap_next_zero_do(TestHBitmapData *data, int granularity)
> {
> hbitmap_test_init(data, L3, granularity);
> test_hbitmap_next_zero_check(data, 0);
> test_hbitmap_next_zero_check(data, L3 - 1);
> + test_hbitmap_next_zero_check_range(data, 0, 1);
> + test_hbitmap_next_zero_check_range(data, L3 - 1, 1);
>
> hbitmap_set(data->hb, L2, 1);
> test_hbitmap_next_zero_check(data, 0);
> test_hbitmap_next_zero_check(data, L2 - 1);
> test_hbitmap_next_zero_check(data, L2);
> test_hbitmap_next_zero_check(data, L2 + 1);
> + test_hbitmap_next_zero_check_range(data, 0, 1);
> + test_hbitmap_next_zero_check_range(data, 0, L2);
> + test_hbitmap_next_zero_check_range(data, L2 - 1, 1);
> + test_hbitmap_next_zero_check_range(data, L2 - 1, 2);
> + test_hbitmap_next_zero_check_range(data, L2, 1);
> + test_hbitmap_next_zero_check_range(data, L2 + 1, 1);
>
> hbitmap_set(data->hb, L2 + 5, L1);
> test_hbitmap_next_zero_check(data, 0);
> @@ -970,6 +988,10 @@ static void test_hbitmap_next_zero_do(TestHBitmapData *data, int granularity)
> test_hbitmap_next_zero_check(data, L2 + 5);
> test_hbitmap_next_zero_check(data, L2 + L1 - 1);
> test_hbitmap_next_zero_check(data, L2 + L1);
> + test_hbitmap_next_zero_check_range(data, L2, 6);
> + test_hbitmap_next_zero_check_range(data, L2 + 1, 3);
> + test_hbitmap_next_zero_check_range(data, L2 + 4, L1);
> + test_hbitmap_next_zero_check_range(data, L2 + 5, L1);
>
> hbitmap_set(data->hb, L2 * 2, L3 - L2 * 2);
> test_hbitmap_next_zero_check(data, L2 * 2 - L1);
> @@ -977,6 +999,8 @@ static void test_hbitmap_next_zero_do(TestHBitmapData *data, int granularity)
> test_hbitmap_next_zero_check(data, L2 * 2 - 1);
> test_hbitmap_next_zero_check(data, L2 * 2);
> test_hbitmap_next_zero_check(data, L3 - 1);
> + test_hbitmap_next_zero_check_range(data, L2 * 2 - L1, L1 + 1);
> + test_hbitmap_next_zero_check_range(data, L2 * 2, L2);
>
> hbitmap_set(data->hb, 0, L3);
> test_hbitmap_next_zero_check(data, 0);
>
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [Qemu-devel] [PATCH v3 1/8] dirty-bitmap: improve bdrv_dirty_bitmap_next_zero
2018-09-07 21:49 ` John Snow
@ 2018-09-10 14:59 ` Eric Blake
2018-09-10 15:49 ` John Snow
2018-09-10 16:49 ` Vladimir Sementsov-Ogievskiy
1 sibling, 1 reply; 25+ messages in thread
From: Eric Blake @ 2018-09-10 14:59 UTC (permalink / raw)
To: John Snow, Vladimir Sementsov-Ogievskiy, qemu-devel, qemu-block
Cc: kwolf, famz, jcody, mreitz, pbonzini, den
On 9/7/18 4:49 PM, John Snow wrote:
>
>
> On 08/14/2018 08:14 AM, Vladimir Sementsov-Ogievskiy wrote:
>> Add bytes parameter to the function, to limit searched range.
>>
>
> I'm going to assume that Eric Blake has been through here and commented
> on the interface itself.
Actually, I haven't had time to look at this series in depth. Do you
need me to?
>
>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>> ---
>> include/block/dirty-bitmap.h | 3 ++-
>> include/qemu/hbitmap.h | 10 ++++++++--
>> block/backup.c | 2 +-
>> block/dirty-bitmap.c | 5 +++--
>> nbd/server.c | 2 +-
>> tests/test-hbitmap.c | 2 +-
>> util/hbitmap.c | 25 ++++++++++++++++++++-----
>> 7 files changed, 36 insertions(+), 13 deletions(-)
>>
>> diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
>> index 259bd27c40..27f5299c4e 100644
>> --- a/include/block/dirty-bitmap.h
>> +++ b/include/block/dirty-bitmap.h
>> @@ -98,7 +98,8 @@ bool bdrv_has_changed_persistent_bitmaps(BlockDriverState *bs);
>> BdrvDirtyBitmap *bdrv_dirty_bitmap_next(BlockDriverState *bs,
>> BdrvDirtyBitmap *bitmap);
>> char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp);
>> -int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start);
>> +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start,
>> + int64_t end);
It's already seeming a bit odd to mix uint64_t AND int64_t for the two
parameters. Is the intent to allow -1 to mean "end of the bitmap
instead of a specific end range"? But you can get that with UINT64_MAX
just as easily, and still get away with spelling it -1 in the source.
>> + * the bitmap end.
>> */
>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start);
>> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t end);
>>
>
> The interface looks weird because we can define a 'start' that's beyond
> the 'end'.
>
> I realize that you need a signed integer for 'end' to signify EOF...
> should we do a 'bytes' parameter instead? (Did you already do that in an
> earlier version and we changed it?)
>
> Well, it's not a big deal to me personally.
It should always be possible to convert in either direction between
[start,end) and [start,start+bytes); it boils down to a question of
convenience (which form is easier for the majority of callers) and
consistency (which form do we use more frequently in the block layer). I
haven't checked closely, but I think start+bytes is more common than end
in our public block layer APIs.
--
Eric Blake, Principal Software Engineer
Red Hat, Inc. +1-919-301-3266
Virtualization: qemu.org | libvirt.org
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [Qemu-devel] [PATCH v3 1/8] dirty-bitmap: improve bdrv_dirty_bitmap_next_zero
2018-09-10 14:59 ` Eric Blake
@ 2018-09-10 15:49 ` John Snow
0 siblings, 0 replies; 25+ messages in thread
From: John Snow @ 2018-09-10 15:49 UTC (permalink / raw)
To: Eric Blake, Vladimir Sementsov-Ogievskiy, qemu-devel, qemu-block
Cc: kwolf, famz, jcody, mreitz, pbonzini, den
On 09/10/2018 10:59 AM, Eric Blake wrote:
> On 9/7/18 4:49 PM, John Snow wrote:
>>
>>
>> On 08/14/2018 08:14 AM, Vladimir Sementsov-Ogievskiy wrote:
>>> Add bytes parameter to the function, to limit searched range.
>>>
>>
>> I'm going to assume that Eric Blake has been through here and commented
>> on the interface itself.
>
> Actually, I haven't had time to look at this series in depth. Do you
> need me to?
>
Not necessarily, it's just that I didn't read v1 or v2 so I was just
being cautious against recommending changes that maybe we already
recommended against in a different direction.
Historically you've cared the most about start/end/offset/bytes naming
and conventions, so I just made an assumption.
--js
>>
>>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>>> ---
>>> include/block/dirty-bitmap.h | 3 ++-
>>> include/qemu/hbitmap.h | 10 ++++++++--
>>> block/backup.c | 2 +-
>>> block/dirty-bitmap.c | 5 +++--
>>> nbd/server.c | 2 +-
>>> tests/test-hbitmap.c | 2 +-
>>> util/hbitmap.c | 25 ++++++++++++++++++++-----
>>> 7 files changed, 36 insertions(+), 13 deletions(-)
>>>
>>> diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
>>> index 259bd27c40..27f5299c4e 100644
>>> --- a/include/block/dirty-bitmap.h
>>> +++ b/include/block/dirty-bitmap.h
>>> @@ -98,7 +98,8 @@ bool
>>> bdrv_has_changed_persistent_bitmaps(BlockDriverState *bs);
>>> BdrvDirtyBitmap *bdrv_dirty_bitmap_next(BlockDriverState *bs,
>>> BdrvDirtyBitmap *bitmap);
>>> char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error
>>> **errp);
>>> -int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap,
>>> uint64_t start);
>>> +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap,
>>> uint64_t start,
>>> + int64_t end);
>
> It's already seeming a bit odd to mix uint64_t AND int64_t for the two
> parameters. Is the intent to allow -1 to mean "end of the bitmap
> instead of a specific end range"? But you can get that with UINT64_MAX
> just as easily, and still get away with spelling it -1 in the source.
>
>
>>> + * the bitmap end.
>>> */
>>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start);
>>> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t
>>> end);
>>>
>>
>> The interface looks weird because we can define a 'start' that's beyond
>> the 'end'.
>>
>> I realize that you need a signed integer for 'end' to signify EOF...
>> should we do a 'bytes' parameter instead? (Did you already do that in an
>> earlier version and we changed it?)
>>
>> Well, it's not a big deal to me personally.
>
> It should always be possible to convert in either direction between
> [start,end) and [start,start+bytes); it boils down to a question of
> convenience (which form is easier for the majority of callers) and
> consistency (which form do we use more frequently in the block layer). I
> haven't checked closely, but I think start+bytes is more common than end
> in our public block layer APIs.
>
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [Qemu-devel] [PATCH v3 1/8] dirty-bitmap: improve bdrv_dirty_bitmap_next_zero
2018-09-07 21:49 ` John Snow
2018-09-10 14:59 ` Eric Blake
@ 2018-09-10 16:49 ` Vladimir Sementsov-Ogievskiy
2018-09-10 16:55 ` Eric Blake
1 sibling, 1 reply; 25+ messages in thread
From: Vladimir Sementsov-Ogievskiy @ 2018-09-10 16:49 UTC (permalink / raw)
To: John Snow, qemu-devel, qemu-block
Cc: kwolf, famz, jcody, mreitz, den, pbonzini
08.09.2018 00:49, John Snow wrote:
>
> On 08/14/2018 08:14 AM, Vladimir Sementsov-Ogievskiy wrote:
>> Add bytes parameter to the function, to limit searched range.
>>
> I'm going to assume that Eric Blake has been through here and commented
> on the interface itself.
>
>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>> ---
>> include/block/dirty-bitmap.h | 3 ++-
>> include/qemu/hbitmap.h | 10 ++++++++--
>> block/backup.c | 2 +-
>> block/dirty-bitmap.c | 5 +++--
>> nbd/server.c | 2 +-
>> tests/test-hbitmap.c | 2 +-
>> util/hbitmap.c | 25 ++++++++++++++++++++-----
>> 7 files changed, 36 insertions(+), 13 deletions(-)
>>
>> diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
>> index 259bd27c40..27f5299c4e 100644
>> --- a/include/block/dirty-bitmap.h
>> +++ b/include/block/dirty-bitmap.h
>> @@ -98,7 +98,8 @@ bool bdrv_has_changed_persistent_bitmaps(BlockDriverState *bs);
>> BdrvDirtyBitmap *bdrv_dirty_bitmap_next(BlockDriverState *bs,
>> BdrvDirtyBitmap *bitmap);
>> char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp);
>> -int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start);
>> +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start,
>> + int64_t end);
>> BdrvDirtyBitmap *bdrv_reclaim_dirty_bitmap_locked(BlockDriverState *bs,
>> BdrvDirtyBitmap *bitmap,
>> Error **errp);
>> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
>> index ddca52c48e..fe4dfde27a 100644
>> --- a/include/qemu/hbitmap.h
>> +++ b/include/qemu/hbitmap.h
>> @@ -295,10 +295,16 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
>> /* hbitmap_next_zero:
>> * @hb: The HBitmap to operate on
>> * @start: The bit to start from.
>> + * @end: End of range to search in. If @end is -1, search up to the bitmap
>> + * end.
>> *
>> - * Find next not dirty bit.
>> + * Find next not dirty bit within range [@start, @end), or from
>> + * @start to the bitmap end if @end is -1. If not found, return -1.
>> + *
>> + * @end may be greater than original bitmap size, in this case, search up to
> "original" bitmap size? I think that's just an implementation detail, we
> can drop 'original' here, yes?
hm, no. we have field "size", which is not "original". But it all means
that this place needs a bit more refactoring.
>
>> + * the bitmap end.
>> */
>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start);
>> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t end);
>>
> The interface looks weird because we can define a 'start' that's beyond
> the 'end'.
>
> I realize that you need a signed integer for 'end' to signify EOF...
> should we do a 'bytes' parameter instead? (Did you already do that in an
> earlier version and we changed it?)
>
> Well, it's not a big deal to me personally.
interface with constant end parameter is more comfortable for loop: we
don't need to update 'bytes' parameter on each iteration
>
>> /* hbitmap_create_meta:
>> * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap.
>> diff --git a/block/backup.c b/block/backup.c
>> index 8630d32926..9bfd3f7189 100644
>> --- a/block/backup.c
>> +++ b/block/backup.c
>> @@ -458,7 +458,7 @@ static void backup_incremental_init_copy_bitmap(BackupBlockJob *job)
>> break;
>> }
>>
>> - offset = bdrv_dirty_bitmap_next_zero(job->sync_bitmap, offset);
>> + offset = bdrv_dirty_bitmap_next_zero(job->sync_bitmap, offset, -1);
>> if (offset == -1) {
>> hbitmap_set(job->copy_bitmap, cluster, end - cluster);
>> break;
>> diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
>> index c9b8a6fd52..037ae62726 100644
>> --- a/block/dirty-bitmap.c
>> +++ b/block/dirty-bitmap.c
>> @@ -785,9 +785,10 @@ char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp)
>> return hbitmap_sha256(bitmap->bitmap, errp);
>> }
>>
>> -int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset)
>> +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset,
>> + int64_t end)
>> {
>> - return hbitmap_next_zero(bitmap->bitmap, offset);
>> + return hbitmap_next_zero(bitmap->bitmap, offset, end);
>> }
>>
>> void bdrv_merge_dirty_bitmap(BdrvDirtyBitmap *dest, const BdrvDirtyBitmap *src,
>> diff --git a/nbd/server.c b/nbd/server.c
>> index ea5fe0eb33..07920d123b 100644
>> --- a/nbd/server.c
>> +++ b/nbd/server.c
>> @@ -1952,7 +1952,7 @@ static unsigned int bitmap_to_extents(BdrvDirtyBitmap *bitmap, uint64_t offset,
>> assert(begin < overall_end && nb_extents);
>> while (begin < overall_end && i < nb_extents) {
>> if (dirty) {
>> - end = bdrv_dirty_bitmap_next_zero(bitmap, begin);
>> + end = bdrv_dirty_bitmap_next_zero(bitmap, begin, -1);
>> } else {
>> bdrv_set_dirty_iter(it, begin);
>> end = bdrv_dirty_iter_next(it);
>> diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
>> index 5e67ac1d3a..6b6a40bddd 100644
>> --- a/tests/test-hbitmap.c
>> +++ b/tests/test-hbitmap.c
>> @@ -939,7 +939,7 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data,
>>
>> static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start)
>> {
>> - int64_t ret1 = hbitmap_next_zero(data->hb, start);
>> + int64_t ret1 = hbitmap_next_zero(data->hb, start, -1);
>> int64_t ret2 = start;
>> for ( ; ret2 < data->size && hbitmap_get(data->hb, ret2); ret2++) {
>> ;
>> diff --git a/util/hbitmap.c b/util/hbitmap.c
>> index bcd304041a..1687372504 100644
>> --- a/util/hbitmap.c
>> +++ b/util/hbitmap.c
>> @@ -53,6 +53,9 @@
>> */
>>
>> struct HBitmap {
>> + /* Size of the bitmap, as requested in hbitmap_alloc. */
>> + uint64_t orig_size;
>> +
>> /* Number of total bits in the bottom level. */
>> uint64_t size;
>>
>> @@ -192,16 +195,26 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first)
>> }
>> }
>>
>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start)
>> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t end)
>> {
>> size_t pos = (start >> hb->granularity) >> BITS_PER_LEVEL;
>> unsigned long *last_lev = hb->levels[HBITMAP_LEVELS - 1];
>> - uint64_t sz = hb->sizes[HBITMAP_LEVELS - 1];
>> unsigned long cur = last_lev[pos];
>> - unsigned start_bit_offset =
>> - (start >> hb->granularity) & (BITS_PER_LONG - 1);
>> + unsigned start_bit_offset;
>> + uint64_t end_bit, sz;
>> int64_t res;
>>
>> + if (start >= hb->orig_size || (end != -1 && end <= start)) {
>> + return -1;
>> + }
>> +
>> + end_bit = end == -1 ? hb->size : ((end - 1) >> hb->granularity) + 1;
>> + sz = (end_bit + BITS_PER_LONG - 1) >> BITS_PER_LEVEL;
>> +
>> + /* There may be some zero bits in @cur before @start. We are not interested
>> + * in them, let's set them.
>> + */
>> + start_bit_offset = (start >> hb->granularity) & (BITS_PER_LONG - 1);
>> cur |= (1UL << start_bit_offset) - 1;
>> assert((start >> hb->granularity) < hb->size);
>>
>> @@ -218,7 +231,7 @@ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start)
>> }
>>
>> res = (pos << BITS_PER_LEVEL) + ctol(cur);
>> - if (res >= hb->size) {
>> + if (res >= end_bit) {
>> return -1;
>> }
>>
>> @@ -652,6 +665,8 @@ HBitmap *hbitmap_alloc(uint64_t size, int granularity)
>> HBitmap *hb = g_new0(struct HBitmap, 1);
>> unsigned i;
>>
>> + hb->orig_size = size;
>> +
>> assert(granularity >= 0 && granularity < 64);
>> size = (size + (1ULL << granularity) - 1) >> granularity;
>> assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
>>
> Despite my comments, I'm OK with or without changes.
>
> Reviewed-by: John Snow <jsnow@redhat.com>
--
Best regards,
Vladimir
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [Qemu-devel] [PATCH v3 1/8] dirty-bitmap: improve bdrv_dirty_bitmap_next_zero
2018-09-10 16:49 ` Vladimir Sementsov-Ogievskiy
@ 2018-09-10 16:55 ` Eric Blake
2018-09-10 17:00 ` Vladimir Sementsov-Ogievskiy
0 siblings, 1 reply; 25+ messages in thread
From: Eric Blake @ 2018-09-10 16:55 UTC (permalink / raw)
To: Vladimir Sementsov-Ogievskiy, John Snow, qemu-devel, qemu-block
Cc: kwolf, famz, jcody, mreitz, pbonzini, den
On 9/10/18 11:49 AM, Vladimir Sementsov-Ogievskiy wrote:
>>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start);
>>> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t
>>> end);
>> The interface looks weird because we can define a 'start' that's beyond
>> the 'end'.
>>
>> I realize that you need a signed integer for 'end' to signify EOF...
>> should we do a 'bytes' parameter instead? (Did you already do that in an
>> earlier version and we changed it?)
>>
>> Well, it's not a big deal to me personally.
>
> interface with constant end parameter is more comfortable for loop: we
> don't need to update 'bytes' parameter on each iteration
But there's still the question of WHO should be calculating end. Your
interface argues for the caller:
hbitmap_next_zero(start, start + bytes)
int64_t hbitmap_next_zero(...)
{
while (offset != end) ...
}
while we're asking about a consistent interface for the caller (if most
callers already have a 'bytes' rather than an 'end' computed):
hbitmap_next_zero(start, bytes)
int64_t hbitmap_next_zero(...)
{
int64_t end = start + bytes;
while (offset != end) ...
}
--
Eric Blake, Principal Software Engineer
Red Hat, Inc. +1-919-301-3266
Virtualization: qemu.org | libvirt.org
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [Qemu-devel] [PATCH v3 1/8] dirty-bitmap: improve bdrv_dirty_bitmap_next_zero
2018-09-10 16:55 ` Eric Blake
@ 2018-09-10 17:00 ` Vladimir Sementsov-Ogievskiy
2018-09-14 17:39 ` John Snow
0 siblings, 1 reply; 25+ messages in thread
From: Vladimir Sementsov-Ogievskiy @ 2018-09-10 17:00 UTC (permalink / raw)
To: Eric Blake, John Snow, qemu-devel, qemu-block
Cc: kwolf, famz, jcody, mreitz, pbonzini, den
10.09.2018 19:55, Eric Blake wrote:
> On 9/10/18 11:49 AM, Vladimir Sementsov-Ogievskiy wrote:
>
>>>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start);
>>>> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start,
>>>> int64_t end);
>>> The interface looks weird because we can define a 'start' that's beyond
>>> the 'end'.
>>>
>>> I realize that you need a signed integer for 'end' to signify EOF...
>>> should we do a 'bytes' parameter instead? (Did you already do that
>>> in an
>>> earlier version and we changed it?)
>>>
>>> Well, it's not a big deal to me personally.
>>
>> interface with constant end parameter is more comfortable for loop:
>> we don't need to update 'bytes' parameter on each iteration
>
> But there's still the question of WHO should be calculating end. Your
> interface argues for the caller:
>
> hbitmap_next_zero(start, start + bytes)
>
> int64_t hbitmap_next_zero(...)
> {
> while (offset != end) ...
> }
>
> while we're asking about a consistent interface for the caller (if
> most callers already have a 'bytes' rather than an 'end' computed):
>
> hbitmap_next_zero(start, bytes)
>
> int64_t hbitmap_next_zero(...)
> {
> int64_t end = start + bytes;
> while (offset != end) ...
> }
>
Yes, that's an issue. Ok, if you are not comfortable with start,end, I
can switch to start,bytes.
--
Best regards,
Vladimir
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [Qemu-devel] [PATCH v3 3/8] dirty-bitmap: add bdrv_dirty_bitmap_next_dirty_area
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 3/8] dirty-bitmap: add bdrv_dirty_bitmap_next_dirty_area Vladimir Sementsov-Ogievskiy
@ 2018-09-10 20:42 ` John Snow
0 siblings, 0 replies; 25+ messages in thread
From: John Snow @ 2018-09-10 20:42 UTC (permalink / raw)
To: Vladimir Sementsov-Ogievskiy, qemu-devel, qemu-block
Cc: kwolf, famz, jcody, mreitz, den, pbonzini, Eric Blake
On 08/14/2018 08:14 AM, Vladimir Sementsov-Ogievskiy wrote:
> The function alters bdrv_dirty_iter_next_area(), which is wrong and
> less efficient (see further commit
> "block/mirror: fix and improve do_sync_target_write" for description).
>
> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> ---
> include/block/dirty-bitmap.h | 3 +++
> include/qemu/hbitmap.h | 15 +++++++++++++++
> block/dirty-bitmap.c | 7 +++++++
> util/hbitmap.c | 38 ++++++++++++++++++++++++++++++++++++++
> 4 files changed, 63 insertions(+)
>
> diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h
> index 27f5299c4e..cb9162fa7e 100644
> --- a/include/block/dirty-bitmap.h
> +++ b/include/block/dirty-bitmap.h
> @@ -100,6 +100,9 @@ BdrvDirtyBitmap *bdrv_dirty_bitmap_next(BlockDriverState *bs,
> char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp);
> int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start,
> int64_t end);
> +bool bdrv_dirty_bitmap_next_dirty_area(BdrvDirtyBitmap *bitmap,
> + uint64_t *offset, uint64_t end,
> + uint64_t *length);
> BdrvDirtyBitmap *bdrv_reclaim_dirty_bitmap_locked(BlockDriverState *bs,
> BdrvDirtyBitmap *bitmap,
> Error **errp);
> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
> index fe4dfde27a..7800317bf3 100644
> --- a/include/qemu/hbitmap.h
> +++ b/include/qemu/hbitmap.h
> @@ -306,6 +306,21 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
> */
> int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t end);
>
> +/* hbitmap_next_dirty_area:
> + * @hb: The HBitmap to operate on
> + * @offset: in-out parameter.
> + * in: the offset to start from
> + * out: (if area found) start of found area
> + * @end: end of requested region. (*@offset + *@length) will be <= @end
> + * @length: length of found area
> + *
> + * If dirty area found within [@offset, @end), returns true and sets @offset
> + * and @length appropriately. Otherwise returns true and leaves @offset and
> + * @length unchanged.
It returns true in both cases? I think you mean 'false' the second time.
> + */
> +bool hbitmap_next_dirty_area(const HBitmap *hb, uint64_t *offset,
> + uint64_t end, uint64_t *length);
> +
> /* hbitmap_create_meta:
> * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap.
> * The caller owns the created bitmap and must call hbitmap_free_meta(hb) to
> diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
> index 037ae62726..4af20a1beb 100644
> --- a/block/dirty-bitmap.c
> +++ b/block/dirty-bitmap.c
> @@ -791,6 +791,13 @@ int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset,
> return hbitmap_next_zero(bitmap->bitmap, offset, end);
> }
>
> +bool bdrv_dirty_bitmap_next_dirty_area(BdrvDirtyBitmap *bitmap,
> + uint64_t *offset, uint64_t end,
> + uint64_t *length)
> +{
> + return hbitmap_next_dirty_area(bitmap->bitmap, offset, end, length);
> +}
> +
> void bdrv_merge_dirty_bitmap(BdrvDirtyBitmap *dest, const BdrvDirtyBitmap *src,
> Error **errp)
> {
> diff --git a/util/hbitmap.c b/util/hbitmap.c
> index 1687372504..bf88c1223e 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -244,6 +244,44 @@ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, int64_t end)
> return res;
> }
>
> +bool hbitmap_next_dirty_area(const HBitmap *hb, uint64_t *offset,
> + uint64_t end, uint64_t *length)
> +{
> + HBitmapIter hbi;
> + int64_t off1, off0;
Can we have more descriptive names for these?
> + uint32_t granularity = 1UL << hb->granularity;
> +
> + if (end == 0) {
> + end = hb->orig_size;
> + }
> +
> + hbitmap_iter_init(&hbi, hb, *offset);
Even with a new iterator in every call, this is still faster than the
old one? ... I guess the old one uses a new iterator for every call, too.
Well, this does look more straightforward and we don't loop as much, so
it seems right.
> + off1 = hbitmap_iter_next(&hbi, true);
> +
> + if (off1 < 0 || off1 >= end) {
> + return false;
> + }
> +
> + if (off1 + granularity >= end) {
> + if (off1 > *offset) {
> + *offset = off1;
> + }
> + *length = end - *offset;
> + return true;
> + }
> +
> + off0 = hbitmap_next_zero(hb, off1 + granularity, end);
> + if (off0 < 0) {
> + off0 = end;
> + }
> +
> + if (off1 > *offset) {
> + *offset = off1;
> + }
> + *length = off0 - *offset;
> + return true;
> +}
> +
I might have consolidated setting the output parameters to one block
instead of two, but that's only stylistic.
> bool hbitmap_empty(const HBitmap *hb)
> {
> return hb->count == 0;
>
If you fix your docstring:
Reviewed-by: John Snow <jsnow@redhat.com>
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [Qemu-devel] [PATCH v3 4/8] tests: add tests for hbitmap_next_dirty_area
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 4/8] tests: add tests for hbitmap_next_dirty_area Vladimir Sementsov-Ogievskiy
@ 2018-09-10 20:45 ` John Snow
0 siblings, 0 replies; 25+ messages in thread
From: John Snow @ 2018-09-10 20:45 UTC (permalink / raw)
To: Vladimir Sementsov-Ogievskiy, qemu-devel, qemu-block
Cc: kwolf, famz, jcody, mreitz, den, pbonzini
On 08/14/2018 08:14 AM, Vladimir Sementsov-Ogievskiy wrote:
> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
ACK, and
Tested-by: John Snow <jsnow@redhat.com>
> ---
> tests/test-hbitmap.c | 106 +++++++++++++++++++++++++++++++++++++++++++++++++++
> 1 file changed, 106 insertions(+)
>
> diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
> index dddb67c3c5..af5142b481 100644
> --- a/tests/test-hbitmap.c
> +++ b/tests/test-hbitmap.c
> @@ -1016,6 +1016,105 @@ static void test_hbitmap_next_zero_4(TestHBitmapData *data, const void *unused)
> test_hbitmap_next_zero_do(data, 4);
> }
>
> +static void test_hbitmap_next_dirty_area_check(TestHBitmapData *data,
> + uint64_t offset,
> + uint64_t count)
> +{
> + uint64_t off1, off2;
> + uint64_t len1 = 0, len2 = 0;
> + bool ret1, ret2;
> + int64_t end;
> +
> + off1 = offset;
> + end = count ? offset + count : 0;
> + ret1 = hbitmap_next_dirty_area(data->hb, &off1, end, &len1);
> +
> + end = count ? offset + count : data->size;
> +
> + for (off2 = offset; off2 < end && !hbitmap_get(data->hb, off2); off2++) {
> + ;
> + }
> +
> + for (len2 = 1; off2 + len2 < end && hbitmap_get(data->hb, off2 + len2);
> + len2++)
> + {
> + }
> +
> + ret2 = off2 < end;
> + if (!ret2) {
> + /* leave unchanged */
> + off2 = offset;
> + len2 = 0;
> + }
> +
> + g_assert_cmpint(ret1, ==, ret2);
> + g_assert_cmpint(off1, ==, off2);
> + g_assert_cmpint(len1, ==, len2);
> +}
> +
> +static void test_hbitmap_next_dirty_area_do(TestHBitmapData *data,
> + int granularity)
> +{
> + hbitmap_test_init(data, L3, granularity);
> + test_hbitmap_next_dirty_area_check(data, 0, 0);
> + test_hbitmap_next_dirty_area_check(data, 0, 1);
> + test_hbitmap_next_dirty_area_check(data, L3 - 1, 1);
> +
> + hbitmap_set(data->hb, L2, 1);
> + test_hbitmap_next_dirty_area_check(data, 0, 1);
> + test_hbitmap_next_dirty_area_check(data, 0, L2);
> + test_hbitmap_next_dirty_area_check(data, 0, 0);
> + test_hbitmap_next_dirty_area_check(data, L2 - 1, 0);
> + test_hbitmap_next_dirty_area_check(data, L2 - 1, 1);
> + test_hbitmap_next_dirty_area_check(data, L2 - 1, 2);
> + test_hbitmap_next_dirty_area_check(data, L2 - 1, 3);
> + test_hbitmap_next_dirty_area_check(data, L2, 0);
> + test_hbitmap_next_dirty_area_check(data, L2, 1);
> + test_hbitmap_next_dirty_area_check(data, L2 + 1, 1);
> +
> + hbitmap_set(data->hb, L2 + 5, L1);
> + test_hbitmap_next_dirty_area_check(data, 0, 0);
> + test_hbitmap_next_dirty_area_check(data, L2 - 2, 8);
> + test_hbitmap_next_dirty_area_check(data, L2 + 1, 5);
> + test_hbitmap_next_dirty_area_check(data, L2 + 1, 3);
> + test_hbitmap_next_dirty_area_check(data, L2 + 4, L1);
> + test_hbitmap_next_dirty_area_check(data, L2 + 5, L1);
> + test_hbitmap_next_dirty_area_check(data, L2 + 7, L1);
> + test_hbitmap_next_dirty_area_check(data, L2 + L1, L1);
> + test_hbitmap_next_dirty_area_check(data, L2, 0);
> + test_hbitmap_next_dirty_area_check(data, L2 + 1, 0);
> +
> + hbitmap_set(data->hb, L2 * 2, L3 - L2 * 2);
> + test_hbitmap_next_dirty_area_check(data, 0, 0);
> + test_hbitmap_next_dirty_area_check(data, L2, 0);
> + test_hbitmap_next_dirty_area_check(data, L2 + 1, 0);
> + test_hbitmap_next_dirty_area_check(data, L2 + 5 + L1 - 1, 0);
> + test_hbitmap_next_dirty_area_check(data, L2 + 5 + L1, 5);
> + test_hbitmap_next_dirty_area_check(data, L2 * 2 - L1, L1 + 1);
> + test_hbitmap_next_dirty_area_check(data, L2 * 2, L2);
> +
> + hbitmap_set(data->hb, 0, L3);
> + test_hbitmap_next_dirty_area_check(data, 0, 0);
> +}
> +
> +static void test_hbitmap_next_dirty_area_0(TestHBitmapData *data,
> + const void *unused)
> +{
> + test_hbitmap_next_dirty_area_do(data, 0);
> +}
> +
> +static void test_hbitmap_next_dirty_area_1(TestHBitmapData *data,
> + const void *unused)
> +{
> + test_hbitmap_next_dirty_area_do(data, 1);
> +}
> +
> +static void test_hbitmap_next_dirty_area_4(TestHBitmapData *data,
> + const void *unused)
> +{
> + test_hbitmap_next_dirty_area_do(data, 4);
> +}
> +
> int main(int argc, char **argv)
> {
> g_test_init(&argc, &argv, NULL);
> @@ -1082,6 +1181,13 @@ int main(int argc, char **argv)
> hbitmap_test_add("/hbitmap/next_zero/next_zero_4",
> test_hbitmap_next_zero_4);
>
> + hbitmap_test_add("/hbitmap/next_dirty_area/next_dirty_area_0",
> + test_hbitmap_next_dirty_area_0);
> + hbitmap_test_add("/hbitmap/next_dirty_area/next_dirty_area_1",
> + test_hbitmap_next_dirty_area_1);
> + hbitmap_test_add("/hbitmap/next_dirty_area/next_dirty_area_4",
> + test_hbitmap_next_dirty_area_4);
> +
> g_test_run();
>
> return 0;
>
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [Qemu-devel] [PATCH v3 5/8] block/mirror: fix and improve do_sync_target_write
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 5/8] block/mirror: fix and improve do_sync_target_write Vladimir Sementsov-Ogievskiy
@ 2018-09-10 20:51 ` John Snow
0 siblings, 0 replies; 25+ messages in thread
From: John Snow @ 2018-09-10 20:51 UTC (permalink / raw)
To: Vladimir Sementsov-Ogievskiy, qemu-devel, qemu-block
Cc: kwolf, famz, jcody, mreitz, den, pbonzini
On 08/14/2018 08:14 AM, Vladimir Sementsov-Ogievskiy wrote:
> Use bdrv_dirty_bitmap_next_dirty_area() instead of
> bdrv_dirty_iter_next_area(), because of the following problems of
> bdrv_dirty_iter_next_area():
>
> 1. Using HBitmap iterators we should carefully handle unaligned offset,
> as first call to hbitmap_iter_next() may return a value less than
> original offset (actually, it will be original offset rounded down to
> bitmap granularity). This handling is not done in
> do_sync_target_write().
>
> 2. bdrv_dirty_iter_next_area() handles unaligned max_offset
> incorrectly:
>
> look at the code:
> if (max_offset == iter->bitmap->size) {
> /* If max_offset points to the image end, round it up by the
> * bitmap granularity */
> gran_max_offset = ROUND_UP(max_offset, granularity);
> } else {
> gran_max_offset = max_offset;
> }
>
> ret = hbitmap_iter_next(&iter->hbi, false);
> if (ret < 0 || ret + granularity > gran_max_offset) {
> return false;
> }
>
> and assume that max_offset != iter->bitmap->size but still unaligned.
> if 0 < ret < max_offset we found dirty area, but the function can
> return false in this case (if ret + granularity > max_offset).
>
> 3. bdrv_dirty_iter_next_area() uses inefficient loop to find the end of
> the dirty area. Let's use more efficient hbitmap_next_zero instead
> (bdrv_dirty_bitmap_next_dirty_area() do so)
>
> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> ---
> block/mirror.c | 16 +++++++---------
> 1 file changed, 7 insertions(+), 9 deletions(-)
>
> diff --git a/block/mirror.c b/block/mirror.c
> index b48c3f8cf5..d2806812c8 100644
> --- a/block/mirror.c
> +++ b/block/mirror.c
> @@ -1167,25 +1167,22 @@ static void do_sync_target_write(MirrorBlockJob *job, MirrorMethod method,
> uint64_t offset, uint64_t bytes,
> QEMUIOVector *qiov, int flags)
> {
> - BdrvDirtyBitmapIter *iter;
> QEMUIOVector target_qiov;
> - uint64_t dirty_offset;
> - int dirty_bytes;
> + uint64_t dirty_offset = offset;
> + uint64_t dirty_bytes;
>
> if (qiov) {
> qemu_iovec_init(&target_qiov, qiov->niov);
> }
>
> - iter = bdrv_dirty_iter_new(job->dirty_bitmap);
> - bdrv_set_dirty_iter(iter, offset);
> -
> while (true) {
> bool valid_area;
> int ret;
>
> bdrv_dirty_bitmap_lock(job->dirty_bitmap);
> - valid_area = bdrv_dirty_iter_next_area(iter, offset + bytes,
> - &dirty_offset, &dirty_bytes);
> + valid_area = bdrv_dirty_bitmap_next_dirty_area(
> + job->dirty_bitmap, &dirty_offset,
> + MIN(offset + bytes, dirty_offset + INT_MAX), &dirty_bytes);
Looks correct, though the invocation looks harder to read now. Might be
a sign that changing the signature is a good idea.... which I think
you're planning to do.
ACK.
> if (!valid_area) {
> bdrv_dirty_bitmap_unlock(job->dirty_bitmap);
> break;
> @@ -1241,9 +1238,10 @@ static void do_sync_target_write(MirrorBlockJob *job, MirrorMethod method,
> break;
> }
> }
> +
> + dirty_offset += dirty_bytes;
> }
>
> - bdrv_dirty_iter_free(iter);
> if (qiov) {
> qemu_iovec_destroy(&target_qiov);
> }
>
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [Qemu-devel] [PATCH v3 8/8] Revert "hbitmap: Add @advance param to hbitmap_iter_next()"
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 8/8] Revert "hbitmap: Add @advance param to hbitmap_iter_next()" Vladimir Sementsov-Ogievskiy
@ 2018-09-10 20:53 ` John Snow
0 siblings, 0 replies; 25+ messages in thread
From: John Snow @ 2018-09-10 20:53 UTC (permalink / raw)
To: Vladimir Sementsov-Ogievskiy, qemu-devel, qemu-block
Cc: kwolf, famz, jcody, mreitz, den, pbonzini
On 08/14/2018 08:14 AM, Vladimir Sementsov-Ogievskiy wrote:
> This reverts commit a33fbb4f8b64226becf502a123733776ce319b24.
>
> The functionality is unused.
>
> Note: in addition to automatic revert, drop second parameter in
> hbitmap_iter_next() call from hbitmap_next_dirty_area() too.
>
Hm, it's not really a "revert" in the revision control sense then, but I
don't think I care about that kind of pedantic distinction personally.
6,7,8: Reviewed-by: John Snow <jsnow@redhat.com>
> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> ---
> include/qemu/hbitmap.h | 5 +----
> block/backup.c | 2 +-
> block/dirty-bitmap.c | 2 +-
> tests/test-hbitmap.c | 26 +++++++++++++-------------
> util/hbitmap.c | 12 ++++--------
> 5 files changed, 20 insertions(+), 27 deletions(-)
>
> diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h
> index 7800317bf3..6d205167ce 100644
> --- a/include/qemu/hbitmap.h
> +++ b/include/qemu/hbitmap.h
> @@ -345,14 +345,11 @@ void hbitmap_free_meta(HBitmap *hb);
> /**
> * hbitmap_iter_next:
> * @hbi: HBitmapIter to operate on.
> - * @advance: If true, advance the iterator. Otherwise, the next call
> - * of this function will return the same result (if that
> - * position is still dirty).
> *
> * Return the next bit that is set in @hbi's associated HBitmap,
> * or -1 if all remaining bits are zero.
> */
> -int64_t hbitmap_iter_next(HBitmapIter *hbi, bool advance);
> +int64_t hbitmap_iter_next(HBitmapIter *hbi);
>
> /**
> * hbitmap_iter_next_word:
> diff --git a/block/backup.c b/block/backup.c
> index 9bfd3f7189..f033148f21 100644
> --- a/block/backup.c
> +++ b/block/backup.c
> @@ -421,7 +421,7 @@ static int coroutine_fn backup_run_incremental(BackupBlockJob *job)
> HBitmapIter hbi;
>
> hbitmap_iter_init(&hbi, job->copy_bitmap, 0);
> - while ((cluster = hbitmap_iter_next(&hbi, true)) != -1) {
> + while ((cluster = hbitmap_iter_next(&hbi)) != -1) {
> do {
> if (yield_and_check(job)) {
> return 0;
> diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c
> index d9333175b3..d0d602ff52 100644
> --- a/block/dirty-bitmap.c
> +++ b/block/dirty-bitmap.c
> @@ -525,7 +525,7 @@ void bdrv_dirty_iter_free(BdrvDirtyBitmapIter *iter)
>
> int64_t bdrv_dirty_iter_next(BdrvDirtyBitmapIter *iter)
> {
> - return hbitmap_iter_next(&iter->hbi, true);
> + return hbitmap_iter_next(&iter->hbi);
> }
>
> /* Called within bdrv_dirty_bitmap_lock..unlock */
> diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
> index 5e43056970..17a3c807de 100644
> --- a/tests/test-hbitmap.c
> +++ b/tests/test-hbitmap.c
> @@ -46,7 +46,7 @@ static void hbitmap_test_check(TestHBitmapData *data,
>
> i = first;
> for (;;) {
> - next = hbitmap_iter_next(&hbi, true);
> + next = hbitmap_iter_next(&hbi);
> if (next < 0) {
> next = data->size;
> }
> @@ -435,25 +435,25 @@ static void test_hbitmap_iter_granularity(TestHBitmapData *data,
> /* Note that hbitmap_test_check has to be invoked manually in this test. */
> hbitmap_test_init(data, 131072 << 7, 7);
> hbitmap_iter_init(&hbi, data->hb, 0);
> - g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
> + g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
>
> hbitmap_test_set(data, ((L2 + L1 + 1) << 7) + 8, 8);
> hbitmap_iter_init(&hbi, data->hb, 0);
> - g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, (L2 + L1 + 1) << 7);
> - g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
> + g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
> + g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
>
> hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
> - g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
> + g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
>
> hbitmap_test_set(data, (131072 << 7) - 8, 8);
> hbitmap_iter_init(&hbi, data->hb, 0);
> - g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, (L2 + L1 + 1) << 7);
> - g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, 131071 << 7);
> - g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
> + g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
> + g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
> + g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
>
> hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
> - g_assert_cmpint(hbitmap_iter_next(&hbi, true), ==, 131071 << 7);
> - g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
> + g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
> + g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
> }
>
> static void hbitmap_test_set_boundary_bits(TestHBitmapData *data, ssize_t diff)
> @@ -893,7 +893,7 @@ static void test_hbitmap_serialize_zeroes(TestHBitmapData *data,
> for (i = 0; i < num_positions; i++) {
> hbitmap_deserialize_zeroes(data->hb, positions[i], min_l1, true);
> hbitmap_iter_init(&iter, data->hb, 0);
> - next = hbitmap_iter_next(&iter, true);
> + next = hbitmap_iter_next(&iter);
> if (i == num_positions - 1) {
> g_assert_cmpint(next, ==, -1);
> } else {
> @@ -919,10 +919,10 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data,
>
> hbitmap_iter_init(&hbi, data->hb, BITS_PER_LONG - 1);
>
> - hbitmap_iter_next(&hbi, true);
> + hbitmap_iter_next(&hbi);
>
> hbitmap_reset_all(data->hb);
> - hbitmap_iter_next(&hbi, true);
> + hbitmap_iter_next(&hbi);
> }
>
> static void test_hbitmap_next_zero_check_range(TestHBitmapData *data,
> diff --git a/util/hbitmap.c b/util/hbitmap.c
> index bf88c1223e..b00e05a85b 100644
> --- a/util/hbitmap.c
> +++ b/util/hbitmap.c
> @@ -144,7 +144,7 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi)
> return cur;
> }
>
> -int64_t hbitmap_iter_next(HBitmapIter *hbi, bool advance)
> +int64_t hbitmap_iter_next(HBitmapIter *hbi)
> {
> unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1] &
> hbi->hb->levels[HBITMAP_LEVELS - 1][hbi->pos];
> @@ -157,12 +157,8 @@ int64_t hbitmap_iter_next(HBitmapIter *hbi, bool advance)
> }
> }
>
> - if (advance) {
> - /* The next call will resume work from the next bit. */
> - hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1);
> - } else {
> - hbi->cur[HBITMAP_LEVELS - 1] = cur;
> - }
> + /* The next call will resume work from the next bit. */
> + hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1);
> item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + ctzl(cur);
>
> return item << hbi->granularity;
> @@ -256,7 +252,7 @@ bool hbitmap_next_dirty_area(const HBitmap *hb, uint64_t *offset,
> }
>
> hbitmap_iter_init(&hbi, hb, *offset);
> - off1 = hbitmap_iter_next(&hbi, true);
> + off1 = hbitmap_iter_next(&hbi);
>
> if (off1 < 0 || off1 >= end) {
> return false;
>
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [Qemu-devel] [PATCH v3 1/8] dirty-bitmap: improve bdrv_dirty_bitmap_next_zero
2018-09-10 17:00 ` Vladimir Sementsov-Ogievskiy
@ 2018-09-14 17:39 ` John Snow
2018-09-14 17:51 ` Vladimir Sementsov-Ogievskiy
0 siblings, 1 reply; 25+ messages in thread
From: John Snow @ 2018-09-14 17:39 UTC (permalink / raw)
To: Vladimir Sementsov-Ogievskiy, Eric Blake, qemu-devel, qemu-block
Cc: kwolf, famz, jcody, mreitz, pbonzini, den
On 09/10/2018 01:00 PM, Vladimir Sementsov-Ogievskiy wrote:
> 10.09.2018 19:55, Eric Blake wrote:
>> On 9/10/18 11:49 AM, Vladimir Sementsov-Ogievskiy wrote:
>>
>>>>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start);
>>>>> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start,
>>>>> int64_t end);
>>>> The interface looks weird because we can define a 'start' that's beyond
>>>> the 'end'.
>>>>
>>>> I realize that you need a signed integer for 'end' to signify EOF...
>>>> should we do a 'bytes' parameter instead? (Did you already do that
>>>> in an
>>>> earlier version and we changed it?)
>>>>
>>>> Well, it's not a big deal to me personally.
>>>
>>> interface with constant end parameter is more comfortable for loop:
>>> we don't need to update 'bytes' parameter on each iteration
>>
>> But there's still the question of WHO should be calculating end. Your
>> interface argues for the caller:
>>
>> hbitmap_next_zero(start, start + bytes)
>>
>> int64_t hbitmap_next_zero(...)
>> {
>> while (offset != end) ...
>> }
>>
>> while we're asking about a consistent interface for the caller (if
>> most callers already have a 'bytes' rather than an 'end' computed):
>>
>> hbitmap_next_zero(start, bytes)
>>
>> int64_t hbitmap_next_zero(...)
>> {
>> int64_t end = start + bytes;
>> while (offset != end) ...
>> }
>>
>
> Yes, that's an issue. Ok, if you are not comfortable with start,end, I
> can switch to start,bytes.
>
The series looks pretty close, I can merge the next version if you think
it's worth changing the interface.
--js
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [Qemu-devel] [PATCH v3 1/8] dirty-bitmap: improve bdrv_dirty_bitmap_next_zero
2018-09-14 17:39 ` John Snow
@ 2018-09-14 17:51 ` Vladimir Sementsov-Ogievskiy
2018-09-14 17:52 ` John Snow
2018-09-14 20:03 ` John Snow
0 siblings, 2 replies; 25+ messages in thread
From: Vladimir Sementsov-Ogievskiy @ 2018-09-14 17:51 UTC (permalink / raw)
To: John Snow, Eric Blake, qemu-devel, qemu-block
Cc: kwolf, famz, jcody, mreitz, pbonzini, den
14.09.2018 20:39, John Snow wrote:
>
> On 09/10/2018 01:00 PM, Vladimir Sementsov-Ogievskiy wrote:
>> 10.09.2018 19:55, Eric Blake wrote:
>>> On 9/10/18 11:49 AM, Vladimir Sementsov-Ogievskiy wrote:
>>>
>>>>>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start);
>>>>>> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start,
>>>>>> int64_t end);
>>>>> The interface looks weird because we can define a 'start' that's beyond
>>>>> the 'end'.
>>>>>
>>>>> I realize that you need a signed integer for 'end' to signify EOF...
>>>>> should we do a 'bytes' parameter instead? (Did you already do that
>>>>> in an
>>>>> earlier version and we changed it?)
>>>>>
>>>>> Well, it's not a big deal to me personally.
>>>> interface with constant end parameter is more comfortable for loop:
>>>> we don't need to update 'bytes' parameter on each iteration
>>> But there's still the question of WHO should be calculating end. Your
>>> interface argues for the caller:
>>>
>>> hbitmap_next_zero(start, start + bytes)
>>>
>>> int64_t hbitmap_next_zero(...)
>>> {
>>> while (offset != end) ...
>>> }
>>>
>>> while we're asking about a consistent interface for the caller (if
>>> most callers already have a 'bytes' rather than an 'end' computed):
>>>
>>> hbitmap_next_zero(start, bytes)
>>>
>>> int64_t hbitmap_next_zero(...)
>>> {
>>> int64_t end = start + bytes;
>>> while (offset != end) ...
>>> }
>>>
>> Yes, that's an issue. Ok, if you are not comfortable with start,end, I
>> can switch to start,bytes.
>>
> The series looks pretty close, I can merge the next version if you think
> it's worth changing the interface.
>
> --js
I've started to change interface and found a bug in bitmap_to_extents
(patch sent
https://lists.gnu.org/archive/html/qemu-devel/2018-09/msg01804.html).
So, next version will be based on this patch, which will go through
Eric's tree..
--
Best regards,
Vladimir
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [Qemu-devel] [PATCH v3 1/8] dirty-bitmap: improve bdrv_dirty_bitmap_next_zero
2018-09-14 17:51 ` Vladimir Sementsov-Ogievskiy
@ 2018-09-14 17:52 ` John Snow
2018-09-14 20:03 ` John Snow
1 sibling, 0 replies; 25+ messages in thread
From: John Snow @ 2018-09-14 17:52 UTC (permalink / raw)
To: Vladimir Sementsov-Ogievskiy, Eric Blake, qemu-devel, qemu-block
Cc: kwolf, famz, jcody, mreitz, pbonzini, den
On 09/14/2018 01:51 PM, Vladimir Sementsov-Ogievskiy wrote:
> 14.09.2018 20:39, John Snow wrote:
>>
>> On 09/10/2018 01:00 PM, Vladimir Sementsov-Ogievskiy wrote:
>>> 10.09.2018 19:55, Eric Blake wrote:
>>>> On 9/10/18 11:49 AM, Vladimir Sementsov-Ogievskiy wrote:
>>>>
>>>>>>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start);
>>>>>>> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start,
>>>>>>> int64_t end);
>>>>>> The interface looks weird because we can define a 'start' that's
>>>>>> beyond
>>>>>> the 'end'.
>>>>>>
>>>>>> I realize that you need a signed integer for 'end' to signify EOF...
>>>>>> should we do a 'bytes' parameter instead? (Did you already do that
>>>>>> in an
>>>>>> earlier version and we changed it?)
>>>>>>
>>>>>> Well, it's not a big deal to me personally.
>>>>> interface with constant end parameter is more comfortable for loop:
>>>>> we don't need to update 'bytes' parameter on each iteration
>>>> But there's still the question of WHO should be calculating end. Your
>>>> interface argues for the caller:
>>>>
>>>> hbitmap_next_zero(start, start + bytes)
>>>>
>>>> int64_t hbitmap_next_zero(...)
>>>> {
>>>> while (offset != end) ...
>>>> }
>>>>
>>>> while we're asking about a consistent interface for the caller (if
>>>> most callers already have a 'bytes' rather than an 'end' computed):
>>>>
>>>> hbitmap_next_zero(start, bytes)
>>>>
>>>> int64_t hbitmap_next_zero(...)
>>>> {
>>>> int64_t end = start + bytes;
>>>> while (offset != end) ...
>>>> }
>>>>
>>> Yes, that's an issue. Ok, if you are not comfortable with start,end, I
>>> can switch to start,bytes.
>>>
>> The series looks pretty close, I can merge the next version if you think
>> it's worth changing the interface.
>>
>> --js
>
> I've started to change interface and found a bug in bitmap_to_extents
> (patch sent
> https://lists.gnu.org/archive/html/qemu-devel/2018-09/msg01804.html).
> So, next version will be based on this patch, which will go through
> Eric's tree..
>
ah, I see. you can send it to the list anyway with the requires: header
and I can have Eric stage it to make the eventual merge easier for Peter.
--js
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [Qemu-devel] [PATCH v3 1/8] dirty-bitmap: improve bdrv_dirty_bitmap_next_zero
2018-09-14 17:51 ` Vladimir Sementsov-Ogievskiy
2018-09-14 17:52 ` John Snow
@ 2018-09-14 20:03 ` John Snow
1 sibling, 0 replies; 25+ messages in thread
From: John Snow @ 2018-09-14 20:03 UTC (permalink / raw)
To: Vladimir Sementsov-Ogievskiy, Eric Blake, qemu-devel, qemu-block
Cc: kwolf, famz, jcody, mreitz, pbonzini, den
On 09/14/2018 01:51 PM, Vladimir Sementsov-Ogievskiy wrote:
> 14.09.2018 20:39, John Snow wrote:
>>
>> On 09/10/2018 01:00 PM, Vladimir Sementsov-Ogievskiy wrote:
>>> 10.09.2018 19:55, Eric Blake wrote:
>>>> On 9/10/18 11:49 AM, Vladimir Sementsov-Ogievskiy wrote:
>>>>
>>>>>>> -int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start);
>>>>>>> +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start,
>>>>>>> int64_t end);
>>>>>> The interface looks weird because we can define a 'start' that's
>>>>>> beyond
>>>>>> the 'end'.
>>>>>>
>>>>>> I realize that you need a signed integer for 'end' to signify EOF...
>>>>>> should we do a 'bytes' parameter instead? (Did you already do that
>>>>>> in an
>>>>>> earlier version and we changed it?)
>>>>>>
>>>>>> Well, it's not a big deal to me personally.
>>>>> interface with constant end parameter is more comfortable for loop:
>>>>> we don't need to update 'bytes' parameter on each iteration
>>>> But there's still the question of WHO should be calculating end. Your
>>>> interface argues for the caller:
>>>>
>>>> hbitmap_next_zero(start, start + bytes)
>>>>
>>>> int64_t hbitmap_next_zero(...)
>>>> {
>>>> while (offset != end) ...
>>>> }
>>>>
>>>> while we're asking about a consistent interface for the caller (if
>>>> most callers already have a 'bytes' rather than an 'end' computed):
>>>>
>>>> hbitmap_next_zero(start, bytes)
>>>>
>>>> int64_t hbitmap_next_zero(...)
>>>> {
>>>> int64_t end = start + bytes;
>>>> while (offset != end) ...
>>>> }
>>>>
>>> Yes, that's an issue. Ok, if you are not comfortable with start,end, I
>>> can switch to start,bytes.
>>>
>> The series looks pretty close, I can merge the next version if you think
>> it's worth changing the interface.
>>
>> --js
>
> I've started to change interface and found a bug in bitmap_to_extents
> (patch sent
> https://lists.gnu.org/archive/html/qemu-devel/2018-09/msg01804.html).
> So, next version will be based on this patch, which will go through
> Eric's tree..
>
OK, I spoke with Eric and if you resend and I R-B & ACK the patches,
he'll stage them through NBD.
Thanks,
--js
^ permalink raw reply [flat|nested] 25+ messages in thread
end of thread, other threads:[~2018-09-14 20:03 UTC | newest]
Thread overview: 25+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-08-14 12:14 [Qemu-devel] [PATCH v3 0/8] dirty-bitmap: rewrite bdrv_dirty_iter_next_area Vladimir Sementsov-Ogievskiy
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 1/8] dirty-bitmap: improve bdrv_dirty_bitmap_next_zero Vladimir Sementsov-Ogievskiy
2018-09-07 21:49 ` John Snow
2018-09-10 14:59 ` Eric Blake
2018-09-10 15:49 ` John Snow
2018-09-10 16:49 ` Vladimir Sementsov-Ogievskiy
2018-09-10 16:55 ` Eric Blake
2018-09-10 17:00 ` Vladimir Sementsov-Ogievskiy
2018-09-14 17:39 ` John Snow
2018-09-14 17:51 ` Vladimir Sementsov-Ogievskiy
2018-09-14 17:52 ` John Snow
2018-09-14 20:03 ` John Snow
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 2/8] tests: add tests for hbitmap_next_zero with specified end parameter Vladimir Sementsov-Ogievskiy
2018-09-07 21:55 ` John Snow
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 3/8] dirty-bitmap: add bdrv_dirty_bitmap_next_dirty_area Vladimir Sementsov-Ogievskiy
2018-09-10 20:42 ` John Snow
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 4/8] tests: add tests for hbitmap_next_dirty_area Vladimir Sementsov-Ogievskiy
2018-09-10 20:45 ` John Snow
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 5/8] block/mirror: fix and improve do_sync_target_write Vladimir Sementsov-Ogievskiy
2018-09-10 20:51 ` John Snow
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 6/8] Revert "block/dirty-bitmap: Add bdrv_dirty_iter_next_area" Vladimir Sementsov-Ogievskiy
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 7/8] Revert "test-hbitmap: Add non-advancing iter_next tests" Vladimir Sementsov-Ogievskiy
2018-08-14 12:14 ` [Qemu-devel] [PATCH v3 8/8] Revert "hbitmap: Add @advance param to hbitmap_iter_next()" Vladimir Sementsov-Ogievskiy
2018-09-10 20:53 ` John Snow
2018-08-16 7:35 ` [Qemu-devel] [PATCH v3 0/8] dirty-bitmap: rewrite bdrv_dirty_iter_next_area no-reply
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.