From 76d570dc495c56bbdcc4574bfc6d512dcb8e9aa9 Mon Sep 17 00:00:00 2001 From: Vladimir Sementsov-Ogievskiy Date: Tue, 15 Jan 2019 18:26:49 -0500 Subject: dirty-bitmap: improve bdrv_dirty_bitmap_next_zero Add bytes parameter to the function, to limit searched range. Signed-off-by: Vladimir Sementsov-Ogievskiy --- include/block/dirty-bitmap.h | 3 ++- include/qemu/hbitmap.h | 10 +++++++--- 2 files changed, 9 insertions(+), 4 deletions(-) (limited to 'include') diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h index 8f38a3dec1..102ccdda32 100644 --- a/include/block/dirty-bitmap.h +++ b/include/block/dirty-bitmap.h @@ -99,7 +99,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 offset, + uint64_t bytes); 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 a7cb780592..135975530f 100644 --- a/include/qemu/hbitmap.h +++ b/include/qemu/hbitmap.h @@ -300,12 +300,16 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first); unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi); /* hbitmap_next_zero: + * + * Find next not dirty bit within selected range. If not found, return -1. + * * @hb: The HBitmap to operate on * @start: The bit to start from. - * - * Find next not dirty bit. + * @count: Number of bits to proceed. If @start+@count > bitmap size, the whole + * bitmap is looked through. You can use UINT64_MAX as @count to 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, uint64_t count); /* hbitmap_create_meta: * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap. -- cgit v1.2.3-55-g7522 From a78a1a48cd1a2e86f23f113bb05e2d3dd8ae0bf6 Mon Sep 17 00:00:00 2001 From: Vladimir Sementsov-Ogievskiy Date: Tue, 15 Jan 2019 18:26:50 -0500 Subject: dirty-bitmap: add bdrv_dirty_bitmap_next_dirty_area 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 --- block/dirty-bitmap.c | 6 ++++++ include/block/dirty-bitmap.h | 2 ++ include/qemu/hbitmap.h | 16 ++++++++++++++++ util/hbitmap.c | 39 +++++++++++++++++++++++++++++++++++++++ 4 files changed, 63 insertions(+) (limited to 'include') diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c index b162f4ac22..c1518373f9 100644 --- a/block/dirty-bitmap.c +++ b/block/dirty-bitmap.c @@ -787,6 +787,12 @@ int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t offset, return hbitmap_next_zero(bitmap->bitmap, offset, bytes); } +bool bdrv_dirty_bitmap_next_dirty_area(BdrvDirtyBitmap *bitmap, + uint64_t *offset, uint64_t *bytes) +{ + return hbitmap_next_dirty_area(bitmap->bitmap, offset, bytes); +} + void bdrv_merge_dirty_bitmap(BdrvDirtyBitmap *dest, const BdrvDirtyBitmap *src, HBitmap **backup, Error **errp) { diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h index 102ccdda32..4ef00ca6ba 100644 --- a/include/block/dirty-bitmap.h +++ b/include/block/dirty-bitmap.h @@ -101,6 +101,8 @@ 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 offset, uint64_t bytes); +bool bdrv_dirty_bitmap_next_dirty_area(BdrvDirtyBitmap *bitmap, + uint64_t *offset, uint64_t *bytes); 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 135975530f..097dce31ee 100644 --- a/include/qemu/hbitmap.h +++ b/include/qemu/hbitmap.h @@ -311,6 +311,22 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi); */ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t count); +/* hbitmap_next_dirty_area: + * @hb: The HBitmap to operate on + * @start: in-out parameter. + * in: the offset to start from + * out: (if area found) start of found area + * @count: in-out parameter. + * in: length of requested region + * out: length of found area + * + * If dirty area found within [@start, @start + @count), returns true and sets + * @offset and @bytes appropriately. Otherwise returns false and leaves @offset + * and @bytes unchanged. + */ +bool hbitmap_next_dirty_area(const HBitmap *hb, uint64_t *start, + uint64_t *count); + /* 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/util/hbitmap.c b/util/hbitmap.c index 09b3719e44..fa356522c4 100644 --- a/util/hbitmap.c +++ b/util/hbitmap.c @@ -246,6 +246,45 @@ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t count) return res; } +bool hbitmap_next_dirty_area(const HBitmap *hb, uint64_t *start, + uint64_t *count) +{ + HBitmapIter hbi; + int64_t firt_dirty_off, area_end; + uint32_t granularity = 1UL << hb->granularity; + uint64_t end; + + if (*start >= hb->orig_size || *count == 0) { + return false; + } + + end = *count > hb->orig_size - *start ? hb->orig_size : *start + *count; + + hbitmap_iter_init(&hbi, hb, *start); + firt_dirty_off = hbitmap_iter_next(&hbi, false); + + if (firt_dirty_off < 0 || firt_dirty_off >= end) { + return false; + } + + if (firt_dirty_off + granularity >= end) { + area_end = end; + } else { + area_end = hbitmap_next_zero(hb, firt_dirty_off + granularity, + end - firt_dirty_off - granularity); + if (area_end < 0) { + area_end = end; + } + } + + if (firt_dirty_off > *start) { + *start = firt_dirty_off; + } + *count = area_end - *start; + + return true; +} + bool hbitmap_empty(const HBitmap *hb) { return hb->count == 0; -- cgit v1.2.3-55-g7522 From 166cd551254f4ea6226d7e687b19928747247500 Mon Sep 17 00:00:00 2001 From: Vladimir Sementsov-Ogievskiy Date: Tue, 15 Jan 2019 18:26:50 -0500 Subject: Revert "block/dirty-bitmap: Add bdrv_dirty_iter_next_area" This reverts commit 72d10a94213a954ad569095cb4491f2ae0853c40. The function is unused now. Signed-off-by: Vladimir Sementsov-Ogievskiy Reviewed-by: John Snow --- block/dirty-bitmap.c | 55 -------------------------------------------- include/block/dirty-bitmap.h | 2 -- 2 files changed, 57 deletions(-) (limited to 'include') diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c index c1518373f9..4d9a8af17d 100644 --- a/block/dirty-bitmap.c +++ b/block/dirty-bitmap.c @@ -518,61 +518,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) diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h index 4ef00ca6ba..04a117fc81 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); -- cgit v1.2.3-55-g7522 From 19c021e1948a81c4ba19b3ff735432b45b6aebee Mon Sep 17 00:00:00 2001 From: Vladimir Sementsov-Ogievskiy Date: Tue, 15 Jan 2019 18:26:50 -0500 Subject: Revert "hbitmap: Add @advance param to hbitmap_iter_next()" 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 Reviewed-by: John Snow --- block/backup.c | 2 +- block/dirty-bitmap.c | 2 +- include/qemu/hbitmap.h | 5 +---- tests/test-hbitmap.c | 26 +++++++++++++------------- util/hbitmap.c | 12 ++++-------- 5 files changed, 20 insertions(+), 27 deletions(-) (limited to 'include') diff --git a/block/backup.c b/block/backup.c index 9ffce5c183..435414e964 100644 --- a/block/backup.c +++ b/block/backup.c @@ -385,7 +385,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 4d9a8af17d..00ea36f554 100644 --- a/block/dirty-bitmap.c +++ b/block/dirty-bitmap.c @@ -515,7 +515,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/include/qemu/hbitmap.h b/include/qemu/hbitmap.h index 097dce31ee..4afbe6292e 100644 --- a/include/qemu/hbitmap.h +++ b/include/qemu/hbitmap.h @@ -351,14 +351,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/tests/test-hbitmap.c b/tests/test-hbitmap.c index 6358f35359..592d8219db 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 fa356522c4..7905212a8b 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; @@ -261,7 +257,7 @@ bool hbitmap_next_dirty_area(const HBitmap *hb, uint64_t *start, end = *count > hb->orig_size - *start ? hb->orig_size : *start + *count; hbitmap_iter_init(&hbi, hb, *start); - firt_dirty_off = hbitmap_iter_next(&hbi, false); + firt_dirty_off = hbitmap_iter_next(&hbi); if (firt_dirty_off < 0 || firt_dirty_off >= end) { return false; -- cgit v1.2.3-55-g7522