From: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> The function is definitely internal (it's not used by third party and it has complicated interface). Move it to .c file. Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Reviewed-by: Max Reitz <mreitz@redhat.com> Reviewed-by: John Snow <jsnow@redhat.com> Message-id: 20200205112041.6003-3-vsementsov@virtuozzo.com Signed-off-by: John Snow <jsnow@redhat.com> --- include/qemu/hbitmap.h | 30 ------------------------------ util/hbitmap.c | 29 +++++++++++++++++++++++++++++ 2 files changed, 29 insertions(+), 30 deletions(-) diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h index 1bf944ca3d..ab227b117f 100644 --- a/include/qemu/hbitmap.h +++ b/include/qemu/hbitmap.h @@ -362,34 +362,4 @@ void hbitmap_free_meta(HBitmap *hb); */ int64_t hbitmap_iter_next(HBitmapIter *hbi); -/** - * hbitmap_iter_next_word: - * @hbi: HBitmapIter to operate on. - * @p_cur: Location where to store the next non-zero word. - * - * Return the index of the next nonzero word that is set in @hbi's - * associated HBitmap, and set *p_cur to the content of that word - * (bits before the index that was passed to hbitmap_iter_init are - * trimmed on the first call). Return -1, and set *p_cur to zero, - * if all remaining words are zero. - */ -static inline size_t hbitmap_iter_next_word(HBitmapIter *hbi, unsigned long *p_cur) -{ - unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1]; - - if (cur == 0) { - cur = hbitmap_iter_skip_words(hbi); - if (cur == 0) { - *p_cur = 0; - return -1; - } - } - - /* The next call will resume work from the next word. */ - hbi->cur[HBITMAP_LEVELS - 1] = 0; - *p_cur = cur; - return hbi->pos; -} - - #endif diff --git a/util/hbitmap.c b/util/hbitmap.c index 7f9b3e0cd7..a368dc5ef7 100644 --- a/util/hbitmap.c +++ b/util/hbitmap.c @@ -298,6 +298,35 @@ uint64_t hbitmap_count(const HBitmap *hb) return hb->count << hb->granularity; } +/** + * hbitmap_iter_next_word: + * @hbi: HBitmapIter to operate on. + * @p_cur: Location where to store the next non-zero word. + * + * Return the index of the next nonzero word that is set in @hbi's + * associated HBitmap, and set *p_cur to the content of that word + * (bits before the index that was passed to hbitmap_iter_init are + * trimmed on the first call). Return -1, and set *p_cur to zero, + * if all remaining words are zero. + */ +static size_t hbitmap_iter_next_word(HBitmapIter *hbi, unsigned long *p_cur) +{ + unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1]; + + if (cur == 0) { + cur = hbitmap_iter_skip_words(hbi); + if (cur == 0) { + *p_cur = 0; + return -1; + } + } + + /* The next call will resume work from the next word. */ + hbi->cur[HBITMAP_LEVELS - 1] = 0; + *p_cur = cur; + return hbi->pos; +} + /* Count the number of set bits between start and end, not accounting for * the granularity. Also an example of how to use hbitmap_iter_next_word. */ -- 2.21.1

From: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Reviewed-by: Max Reitz <mreitz@redhat.com> Reviewed-by: John Snow <jsnow@redhat.com> Message-id: 20200205112041.6003-5-vsementsov@virtuozzo.com Signed-off-by: John Snow <jsnow@redhat.com> --- include/qemu/hbitmap.h | 21 -------- tests/test-hbitmap.c | 115 ----------------------------------------- util/hbitmap.c | 16 ------ 3 files changed, 152 deletions(-) diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h index 15837a0e2d..df922d8517 100644 --- a/include/qemu/hbitmap.h +++ b/include/qemu/hbitmap.h @@ -325,27 +325,6 @@ int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t count); 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 - * free it. - * - * Currently, we only guarantee that if a bit in the hbitmap is changed it - * will be reflected in the meta bitmap, but we do not yet guarantee the - * opposite. - * - * @hb: The HBitmap to operate on. - * @chunk_size: How many bits in @hb does one bit in the meta track. - */ -HBitmap *hbitmap_create_meta(HBitmap *hb, int chunk_size); - -/* hbitmap_free_meta: - * Free the meta bitmap of @hb. - * - * @hb: The HBitmap whose meta bitmap should be freed. - */ -void hbitmap_free_meta(HBitmap *hb); - /** * hbitmap_iter_next: * @hbi: HBitmapIter to operate on. diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c index e1f867085f..aeaa0b3f22 100644 --- a/tests/test-hbitmap.c +++ b/tests/test-hbitmap.c @@ -22,7 +22,6 @@ typedef struct TestHBitmapData { HBitmap *hb; - HBitmap *meta; unsigned long *bits; size_t size; size_t old_size; @@ -94,14 +93,6 @@ static void hbitmap_test_init(TestHBitmapData *data, } } -static void hbitmap_test_init_meta(TestHBitmapData *data, - uint64_t size, int granularity, - int meta_chunk) -{ - hbitmap_test_init(data, size, granularity); - data->meta = hbitmap_create_meta(data->hb, meta_chunk); -} - static inline size_t hbitmap_test_array_size(size_t bits) { size_t n = DIV_ROUND_UP(bits, BITS_PER_LONG); @@ -144,9 +135,6 @@ static void hbitmap_test_teardown(TestHBitmapData *data, const void *unused) { if (data->hb) { - if (data->meta) { - hbitmap_free_meta(data->hb); - } hbitmap_free(data->hb); data->hb = NULL; } @@ -648,96 +636,6 @@ static void test_hbitmap_truncate_shrink_large(TestHBitmapData *data, hbitmap_test_truncate(data, size, -diff, 0); } -static void hbitmap_check_meta(TestHBitmapData *data, - int64_t start, int count) -{ - int64_t i; - - for (i = 0; i < data->size; i++) { - if (i >= start && i < start + count) { - g_assert(hbitmap_get(data->meta, i)); - } else { - g_assert(!hbitmap_get(data->meta, i)); - } - } -} - -static void hbitmap_test_meta(TestHBitmapData *data, - int64_t start, int count, - int64_t check_start, int check_count) -{ - hbitmap_reset_all(data->hb); - hbitmap_reset_all(data->meta); - - /* Test "unset" -> "unset" will not update meta. */ - hbitmap_reset(data->hb, start, count); - hbitmap_check_meta(data, 0, 0); - - /* Test "unset" -> "set" will update meta */ - hbitmap_set(data->hb, start, count); - hbitmap_check_meta(data, check_start, check_count); - - /* Test "set" -> "set" will not update meta */ - hbitmap_reset_all(data->meta); - hbitmap_set(data->hb, start, count); - hbitmap_check_meta(data, 0, 0); - - /* Test "set" -> "unset" will update meta */ - hbitmap_reset_all(data->meta); - hbitmap_reset(data->hb, start, count); - hbitmap_check_meta(data, check_start, check_count); -} - -static void hbitmap_test_meta_do(TestHBitmapData *data, int chunk_size) -{ - uint64_t size = chunk_size * 100; - hbitmap_test_init_meta(data, size, 0, chunk_size); - - hbitmap_test_meta(data, 0, 1, 0, chunk_size); - hbitmap_test_meta(data, 0, chunk_size, 0, chunk_size); - hbitmap_test_meta(data, chunk_size - 1, 1, 0, chunk_size); - hbitmap_test_meta(data, chunk_size - 1, 2, 0, chunk_size * 2); - hbitmap_test_meta(data, chunk_size - 1, chunk_size + 1, 0, chunk_size * 2); - hbitmap_test_meta(data, chunk_size - 1, chunk_size + 2, 0, chunk_size * 3); - hbitmap_test_meta(data, 7 * chunk_size - 1, chunk_size + 2, - 6 * chunk_size, chunk_size * 3); - hbitmap_test_meta(data, size - 1, 1, size - chunk_size, chunk_size); - hbitmap_test_meta(data, 0, size, 0, size); -} - -static void test_hbitmap_meta_byte(TestHBitmapData *data, const void *unused) -{ - hbitmap_test_meta_do(data, BITS_PER_BYTE); -} - -static void test_hbitmap_meta_word(TestHBitmapData *data, const void *unused) -{ - hbitmap_test_meta_do(data, BITS_PER_LONG); -} - -static void test_hbitmap_meta_sector(TestHBitmapData *data, const void *unused) -{ - hbitmap_test_meta_do(data, BDRV_SECTOR_SIZE * BITS_PER_BYTE); -} - -/** - * Create an HBitmap and test set/unset. - */ -static void test_hbitmap_meta_one(TestHBitmapData *data, const void *unused) -{ - int i; - int64_t offsets[] = { - 0, 1, L1 - 1, L1, L1 + 1, L2 - 1, L2, L2 + 1, L3 - 1, L3, L3 + 1 - }; - - hbitmap_test_init_meta(data, L3 * 2, 0, 1); - for (i = 0; i < ARRAY_SIZE(offsets); i++) { - hbitmap_test_meta(data, offsets[i], 1, offsets[i], 1); - hbitmap_test_meta(data, offsets[i], L1, offsets[i], L1); - hbitmap_test_meta(data, offsets[i], L2, offsets[i], L2); - } -} - static void test_hbitmap_serialize_align(TestHBitmapData *data, const void *unused) { @@ -750,13 +648,6 @@ static void test_hbitmap_serialize_align(TestHBitmapData *data, g_assert_cmpint(r, ==, 64 << 3); } -static void test_hbitmap_meta_zero(TestHBitmapData *data, const void *unused) -{ - hbitmap_test_init_meta(data, 0, 0, 1); - - hbitmap_check_meta(data, 0, 0); -} - static void hbitmap_test_serialize_range(TestHBitmapData *data, uint8_t *buf, size_t buf_size, uint64_t pos, uint64_t count) @@ -1165,12 +1056,6 @@ int main(int argc, char **argv) hbitmap_test_add("/hbitmap/truncate/shrink/large", test_hbitmap_truncate_shrink_large); - hbitmap_test_add("/hbitmap/meta/zero", test_hbitmap_meta_zero); - hbitmap_test_add("/hbitmap/meta/one", test_hbitmap_meta_one); - hbitmap_test_add("/hbitmap/meta/byte", test_hbitmap_meta_byte); - hbitmap_test_add("/hbitmap/meta/word", test_hbitmap_meta_word); - hbitmap_test_add("/hbitmap/meta/sector", test_hbitmap_meta_sector); - hbitmap_test_add("/hbitmap/serialize/align", test_hbitmap_serialize_align); hbitmap_test_add("/hbitmap/serialize/basic", diff --git a/util/hbitmap.c b/util/hbitmap.c index 26145d4b9e..b6d4b99a06 100644 --- a/util/hbitmap.c +++ b/util/hbitmap.c @@ -905,22 +905,6 @@ bool hbitmap_merge(const HBitmap *a, const HBitmap *b, HBitmap *result) return true; } -HBitmap *hbitmap_create_meta(HBitmap *hb, int chunk_size) -{ - assert(!(chunk_size & (chunk_size - 1))); - assert(!hb->meta); - hb->meta = hbitmap_alloc(hb->size << hb->granularity, - hb->granularity + ctz32(chunk_size)); - return hb->meta; -} - -void hbitmap_free_meta(HBitmap *hb) -{ - assert(hb->meta); - hbitmap_free(hb->meta); - hb->meta = NULL; -} - char *hbitmap_sha256(const HBitmap *bitmap, Error **errp) { size_t size = bitmap->sizes[HBITMAP_LEVELS - 1] * sizeof(unsigned long); -- 2.21.1

From: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> We have bdrv_dirty_bitmap_next_zero, let's add corresponding bdrv_dirty_bitmap_next_dirty, which is more comfortable to use than bitmap iterators in some cases. For test modify test_hbitmap_next_zero_check_range to check both next_zero and next_dirty and add some new checks. Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Reviewed-by: Max Reitz <mreitz@redhat.com> Reviewed-by: John Snow <jsnow@redhat.com> Message-id: 20200205112041.6003-7-vsementsov@virtuozzo.com Signed-off-by: John Snow <jsnow@redhat.com> --- include/block/dirty-bitmap.h | 2 + include/qemu/hbitmap.h | 13 ++++ block/dirty-bitmap.c | 6 ++ tests/test-hbitmap.c | 130 ++++++++++++++++++++--------------- util/hbitmap.c | 60 ++++++++-------- 5 files changed, 126 insertions(+), 85 deletions(-) diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h index 27c72cc56a..b1f0de12db 100644 --- a/include/block/dirty-bitmap.h +++ b/include/block/dirty-bitmap.h @@ -105,6 +105,8 @@ for (bitmap = bdrv_dirty_bitmap_first(bs); bitmap; \ bitmap = bdrv_dirty_bitmap_next(bitmap)) char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp); +int64_t bdrv_dirty_bitmap_next_dirty(BdrvDirtyBitmap *bitmap, int64_t offset, + int64_t bytes); int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, int64_t offset, int64_t bytes); bool bdrv_dirty_bitmap_next_dirty_area(BdrvDirtyBitmap *bitmap, diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h index b6e85f3d5d..6e9ae51ed3 100644 --- a/include/qemu/hbitmap.h +++ b/include/qemu/hbitmap.h @@ -297,6 +297,19 @@ void hbitmap_free(HBitmap *hb); */ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first); +/* + * hbitmap_next_dirty: + * + * Find next dirty bit within selected range. If not found, return -1. + * + * @hb: The HBitmap to operate on + * @start: The bit to start from. + * @count: Number of bits to proceed. If @start+@count > bitmap size, the whole + * bitmap is looked through. You can use INT64_MAX as @count to search up to + * the bitmap end. + */ +int64_t hbitmap_next_dirty(const HBitmap *hb, int64_t start, int64_t count); + /* hbitmap_next_zero: * * Find next not dirty bit within selected range. If not found, return -1. diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c index af9f5411a6..1b14c8eb26 100644 --- a/block/dirty-bitmap.c +++ b/block/dirty-bitmap.c @@ -860,6 +860,12 @@ char *bdrv_dirty_bitmap_sha256(const BdrvDirtyBitmap *bitmap, Error **errp) return hbitmap_sha256(bitmap->bitmap, errp); } +int64_t bdrv_dirty_bitmap_next_dirty(BdrvDirtyBitmap *bitmap, int64_t offset, + int64_t bytes) +{ + return hbitmap_next_dirty(bitmap->bitmap, offset, bytes); +} + int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, int64_t offset, int64_t bytes) { diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c index 9d210dc18c..8905b8a351 100644 --- a/tests/test-hbitmap.c +++ b/tests/test-hbitmap.c @@ -816,92 +816,108 @@ static void test_hbitmap_iter_and_reset(TestHBitmapData *data, hbitmap_iter_next(&hbi); } -static void test_hbitmap_next_zero_check_range(TestHBitmapData *data, - int64_t start, - int64_t count) +static void test_hbitmap_next_x_check_range(TestHBitmapData *data, + int64_t start, + int64_t count) { - int64_t ret1 = hbitmap_next_zero(data->hb, start, count); - int64_t ret2 = start; + int64_t next_zero = hbitmap_next_zero(data->hb, start, count); + int64_t next_dirty = hbitmap_next_dirty(data->hb, start, count); + int64_t next; int64_t end = start >= data->size || data->size - start < count ? data->size : start + count; + bool first_bit = hbitmap_get(data->hb, start); - for ( ; ret2 < end && hbitmap_get(data->hb, ret2); ret2++) { + for (next = start; + next < end && hbitmap_get(data->hb, next) == first_bit; + next++) + { ; } - if (ret2 == end) { - ret2 = -1; + + if (next == end) { + next = -1; } - g_assert_cmpint(ret1, ==, ret2); + g_assert_cmpint(next_dirty, ==, first_bit ? start : next); + g_assert_cmpint(next_zero, ==, first_bit ? next : start); } -static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start) +static void test_hbitmap_next_x_check(TestHBitmapData *data, int64_t start) { - test_hbitmap_next_zero_check_range(data, start, INT64_MAX); + test_hbitmap_next_x_check_range(data, start, INT64_MAX); } -static void test_hbitmap_next_zero_do(TestHBitmapData *data, int granularity) +static void test_hbitmap_next_x_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); + test_hbitmap_next_x_check(data, 0); + test_hbitmap_next_x_check(data, L3 - 1); + test_hbitmap_next_x_check_range(data, 0, 1); + test_hbitmap_next_x_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); + test_hbitmap_next_x_check(data, 0); + test_hbitmap_next_x_check(data, L2 - 1); + test_hbitmap_next_x_check(data, L2); + test_hbitmap_next_x_check(data, L2 + 1); + test_hbitmap_next_x_check_range(data, 0, 1); + test_hbitmap_next_x_check_range(data, 0, L2); + test_hbitmap_next_x_check_range(data, L2 - 1, 1); + test_hbitmap_next_x_check_range(data, L2 - 1, 2); + test_hbitmap_next_x_check_range(data, L2, 1); + test_hbitmap_next_x_check_range(data, L2 + 1, 1); hbitmap_set(data->hb, L2 + 5, L1); - test_hbitmap_next_zero_check(data, 0); - test_hbitmap_next_zero_check(data, L2 + 1); - test_hbitmap_next_zero_check(data, L2 + 2); - 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); + test_hbitmap_next_x_check(data, 0); + test_hbitmap_next_x_check(data, L2 - L1); + test_hbitmap_next_x_check(data, L2 + 1); + test_hbitmap_next_x_check(data, L2 + 2); + test_hbitmap_next_x_check(data, L2 + 5); + test_hbitmap_next_x_check(data, L2 + L1 - 1); + test_hbitmap_next_x_check(data, L2 + L1); + test_hbitmap_next_x_check(data, L2 + L1 + 1); + test_hbitmap_next_x_check_range(data, L2 - 2, L1); + test_hbitmap_next_x_check_range(data, L2, 4); + test_hbitmap_next_x_check_range(data, L2, 6); + test_hbitmap_next_x_check_range(data, L2 + 1, 3); + test_hbitmap_next_x_check_range(data, L2 + 4, L1); + test_hbitmap_next_x_check_range(data, L2 + 5, L1); + test_hbitmap_next_x_check_range(data, L2 + 5 + L1 - 1, 1); + test_hbitmap_next_x_check_range(data, L2 + 5 + L1, 1); + test_hbitmap_next_x_check_range(data, L2 + 5 + L1 + 1, 1); hbitmap_set(data->hb, L2 * 2, L3 - L2 * 2); - test_hbitmap_next_zero_check(data, L2 * 2 - L1); - test_hbitmap_next_zero_check(data, L2 * 2 - 2); - 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); + test_hbitmap_next_x_check(data, L2 * 2 - L1); + test_hbitmap_next_x_check(data, L2 * 2 - 2); + test_hbitmap_next_x_check(data, L2 * 2 - 1); + test_hbitmap_next_x_check(data, L2 * 2); + test_hbitmap_next_x_check(data, L2 * 2 + 1); + test_hbitmap_next_x_check(data, L2 * 2 + L1); + test_hbitmap_next_x_check(data, L3 - 1); + test_hbitmap_next_x_check_range(data, L2 * 2 - L1, L1 + 1); + test_hbitmap_next_x_check_range(data, L2 * 2, L2); hbitmap_set(data->hb, 0, L3); - test_hbitmap_next_zero_check(data, 0); + test_hbitmap_next_x_check(data, 0); } -static void test_hbitmap_next_zero_0(TestHBitmapData *data, const void *unused) +static void test_hbitmap_next_x_0(TestHBitmapData *data, const void *unused) { - test_hbitmap_next_zero_do(data, 0); + test_hbitmap_next_x_do(data, 0); } -static void test_hbitmap_next_zero_4(TestHBitmapData *data, const void *unused) +static void test_hbitmap_next_x_4(TestHBitmapData *data, const void *unused) { - test_hbitmap_next_zero_do(data, 4); + test_hbitmap_next_x_do(data, 4); } -static void test_hbitmap_next_zero_after_truncate(TestHBitmapData *data, - const void *unused) +static void test_hbitmap_next_x_after_truncate(TestHBitmapData *data, + const void *unused) { hbitmap_test_init(data, L1, 0); hbitmap_test_truncate_impl(data, L1 * 2); hbitmap_set(data->hb, 0, L1); - test_hbitmap_next_zero_check(data, 0); + test_hbitmap_next_x_check(data, 0); } static void test_hbitmap_next_dirty_area_check(TestHBitmapData *data, @@ -1068,12 +1084,12 @@ int main(int argc, char **argv) hbitmap_test_add("/hbitmap/iter/iter_and_reset", test_hbitmap_iter_and_reset); - hbitmap_test_add("/hbitmap/next_zero/next_zero_0", - test_hbitmap_next_zero_0); - hbitmap_test_add("/hbitmap/next_zero/next_zero_4", - test_hbitmap_next_zero_4); - hbitmap_test_add("/hbitmap/next_zero/next_zero_after_truncate", - test_hbitmap_next_zero_after_truncate); + hbitmap_test_add("/hbitmap/next_zero/next_x_0", + test_hbitmap_next_x_0); + hbitmap_test_add("/hbitmap/next_zero/next_x_4", + test_hbitmap_next_x_4); + hbitmap_test_add("/hbitmap/next_zero/next_x_after_truncate", + test_hbitmap_next_x_after_truncate); hbitmap_test_add("/hbitmap/next_dirty_area/next_dirty_area_0", test_hbitmap_next_dirty_area_0); diff --git a/util/hbitmap.c b/util/hbitmap.c index df22f06be6..883ca48fa6 100644 --- a/util/hbitmap.c +++ b/util/hbitmap.c @@ -193,6 +193,30 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first) } } +int64_t hbitmap_next_dirty(const HBitmap *hb, int64_t start, int64_t count) +{ + HBitmapIter hbi; + int64_t first_dirty_off; + uint64_t end; + + assert(start >= 0 && count >= 0); + + if (start >= hb->orig_size || count == 0) { + return -1; + } + + end = count > hb->orig_size - start ? hb->orig_size : start + count; + + hbitmap_iter_init(&hbi, hb, start); + first_dirty_off = hbitmap_iter_next(&hbi); + + if (first_dirty_off < 0 || first_dirty_off >= end) { + return -1; + } + + return MAX(start, first_dirty_off); +} + int64_t hbitmap_next_zero(const HBitmap *hb, int64_t start, int64_t count) { size_t pos = (start >> hb->granularity) >> BITS_PER_LEVEL; @@ -248,40 +272,20 @@ int64_t hbitmap_next_zero(const HBitmap *hb, int64_t start, int64_t count) bool hbitmap_next_dirty_area(const HBitmap *hb, int64_t *start, int64_t *count) { - HBitmapIter hbi; - int64_t firt_dirty_off, area_end; - uint32_t granularity = 1UL << hb->granularity; - uint64_t end; + int64_t area_start, area_end; - assert(*start >= 0 && *count >= 0); - - if (*start >= hb->orig_size || *count == 0) { + area_start = hbitmap_next_dirty(hb, *start, *count); + if (area_start < 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); - - if (firt_dirty_off < 0 || firt_dirty_off >= end) { - return false; + area_end = hbitmap_next_zero(hb, area_start, *start + *count - area_start); + if (area_end < 0) { + area_end = MIN(hb->orig_size, *start + *count); } - 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; + *start = area_start; + *count = area_end - area_start; return true; } -- 2.21.1

From: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Introduce NBDExtentArray class, to handle extents list creation in more controlled way and with fewer OUT parameters in functions. Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Reviewed-by: Eric Blake <eblake@redhat.com> Message-id: 20200205112041.6003-9-vsementsov@virtuozzo.com Signed-off-by: John Snow <jsnow@redhat.com> --- nbd/server.c | 210 +++++++++++++++++++++++++++++---------------------- 1 file changed, 118 insertions(+), 92 deletions(-) diff --git a/nbd/server.c b/nbd/server.c index 3106aaf3b4..f90bb33a75 100644 --- a/nbd/server.c +++ b/nbd/server.c @@ -1909,27 +1909,98 @@ static int coroutine_fn nbd_co_send_sparse_read(NBDClient *client, return ret; } +typedef struct NBDExtentArray { + NBDExtent *extents; + unsigned int nb_alloc; + unsigned int count; + uint64_t total_length; + bool can_add; + bool converted_to_be; +} NBDExtentArray; + +static NBDExtentArray *nbd_extent_array_new(unsigned int nb_alloc) +{ + NBDExtentArray *ea = g_new0(NBDExtentArray, 1); + + ea->nb_alloc = nb_alloc; + ea->extents = g_new(NBDExtent, nb_alloc); + ea->can_add = true; + + return ea; +} + +static void nbd_extent_array_free(NBDExtentArray *ea) +{ + g_free(ea->extents); + g_free(ea); +} +G_DEFINE_AUTOPTR_CLEANUP_FUNC(NBDExtentArray, nbd_extent_array_free); + +/* Further modifications of the array after conversion are abandoned */ +static void nbd_extent_array_convert_to_be(NBDExtentArray *ea) +{ + int i; + + assert(!ea->converted_to_be); + ea->can_add = false; + ea->converted_to_be = true; + + for (i = 0; i < ea->count; i++) { + ea->extents[i].flags = cpu_to_be32(ea->extents[i].flags); + ea->extents[i].length = cpu_to_be32(ea->extents[i].length); + } +} + /* - * Populate @extents from block status. Update @bytes to be the actual - * length encoded (which may be smaller than the original), and update - * @nb_extents to the number of extents used. - * - * Returns zero on success and -errno on bdrv_block_status_above failure. + * Add extent to NBDExtentArray. If extent can't be added (no available space), + * return -1. + * For safety, when returning -1 for the first time, .can_add is set to false, + * further call to nbd_extent_array_add() will crash. + * (to avoid the situation, when after failing to add an extent (returned -1), + * user miss this failure and add another extent, which is successfully added + * (array is full, but new extent may be squashed into the last one), then we + * have invalid array with skipped extent) */ +static int nbd_extent_array_add(NBDExtentArray *ea, + uint32_t length, uint32_t flags) +{ + assert(ea->can_add); + + if (!length) { + return 0; + } + + /* Extend previous extent if flags are the same */ + if (ea->count > 0 && flags == ea->extents[ea->count - 1].flags) { + uint64_t sum = (uint64_t)length + ea->extents[ea->count - 1].length; + + if (sum <= UINT32_MAX) { + ea->extents[ea->count - 1].length = sum; + ea->total_length += length; + return 0; + } + } + + if (ea->count >= ea->nb_alloc) { + ea->can_add = false; + return -1; + } + + ea->total_length += length; + ea->extents[ea->count] = (NBDExtent) {.length = length, .flags = flags}; + ea->count++; + + return 0; +} + static int blockstatus_to_extents(BlockDriverState *bs, uint64_t offset, - uint64_t *bytes, NBDExtent *extents, - unsigned int *nb_extents) + uint64_t bytes, NBDExtentArray *ea) { - uint64_t remaining_bytes = *bytes; - NBDExtent *extent = extents, *extents_end = extents + *nb_extents; - bool first_extent = true; - - assert(*nb_extents); - while (remaining_bytes) { + while (bytes) { uint32_t flags; int64_t num; - int ret = bdrv_block_status_above(bs, NULL, offset, remaining_bytes, - &num, NULL, NULL); + int ret = bdrv_block_status_above(bs, NULL, offset, bytes, &num, + NULL, NULL); if (ret < 0) { return ret; @@ -1938,60 +2009,37 @@ static int blockstatus_to_extents(BlockDriverState *bs, uint64_t offset, flags = (ret & BDRV_BLOCK_ALLOCATED ? 0 : NBD_STATE_HOLE) | (ret & BDRV_BLOCK_ZERO ? NBD_STATE_ZERO : 0); - if (first_extent) { - extent->flags = flags; - extent->length = num; - first_extent = false; - } else if (flags == extent->flags) { - /* extend current extent */ - extent->length += num; - } else { - if (extent + 1 == extents_end) { - break; - } - - /* start new extent */ - extent++; - extent->flags = flags; - extent->length = num; + if (nbd_extent_array_add(ea, num, flags) < 0) { + return 0; } + offset += num; - remaining_bytes -= num; + bytes -= num; } - extents_end = extent + 1; - - for (extent = extents; extent < extents_end; extent++) { - extent->flags = cpu_to_be32(extent->flags); - extent->length = cpu_to_be32(extent->length); - } - - *bytes -= remaining_bytes; - *nb_extents = extents_end - extents; - return 0; } -/* nbd_co_send_extents +/* + * nbd_co_send_extents * - * @length is only for tracing purposes (and may be smaller or larger - * than the client's original request). @last controls whether - * NBD_REPLY_FLAG_DONE is sent. @extents should already be in - * big-endian format. + * @ea is converted to BE by the function + * @last controls whether NBD_REPLY_FLAG_DONE is sent. */ static int nbd_co_send_extents(NBDClient *client, uint64_t handle, - NBDExtent *extents, unsigned int nb_extents, - uint64_t length, bool last, - uint32_t context_id, Error **errp) + NBDExtentArray *ea, + bool last, uint32_t context_id, Error **errp) { NBDStructuredMeta chunk; - struct iovec iov[] = { {.iov_base = &chunk, .iov_len = sizeof(chunk)}, - {.iov_base = extents, .iov_len = nb_extents * sizeof(extents[0])} + {.iov_base = ea->extents, .iov_len = ea->count * sizeof(ea->extents[0])} }; - trace_nbd_co_send_extents(handle, nb_extents, context_id, length, last); + nbd_extent_array_convert_to_be(ea); + + trace_nbd_co_send_extents(handle, ea->count, context_id, ea->total_length, + last); set_be_chunk(&chunk.h, last ? NBD_REPLY_FLAG_DONE : 0, NBD_REPLY_TYPE_BLOCK_STATUS, handle, sizeof(chunk) - sizeof(chunk.h) + iov[1].iov_len); @@ -2009,39 +2057,27 @@ static int nbd_co_send_block_status(NBDClient *client, uint64_t handle, { int ret; unsigned int nb_extents = dont_fragment ? 1 : NBD_MAX_BLOCK_STATUS_EXTENTS; - NBDExtent *extents = g_new(NBDExtent, nb_extents); - uint64_t final_length = length; + g_autoptr(NBDExtentArray) ea = nbd_extent_array_new(nb_extents); - ret = blockstatus_to_extents(bs, offset, &final_length, extents, - &nb_extents); + ret = blockstatus_to_extents(bs, offset, length, ea); if (ret < 0) { - g_free(extents); return nbd_co_send_structured_error( client, handle, -ret, "can't get block status", errp); } - ret = nbd_co_send_extents(client, handle, extents, nb_extents, - final_length, last, context_id, errp); - - g_free(extents); - - return ret; + return nbd_co_send_extents(client, handle, ea, last, context_id, errp); } /* - * Populate @extents from a dirty bitmap. Unless @dont_fragment, the - * final extent may exceed the original @length. Store in @length the - * byte length encoded (which may be smaller or larger than the - * original), and return the number of extents used. + * Populate @ea from a dirty bitmap. Unless @dont_fragment, the + * final extent may exceed the original @length. */ -static unsigned int bitmap_to_extents(BdrvDirtyBitmap *bitmap, uint64_t offset, - uint64_t *length, NBDExtent *extents, - unsigned int nb_extents, - bool dont_fragment) +static void bitmap_to_extents(BdrvDirtyBitmap *bitmap, + uint64_t offset, uint64_t length, + NBDExtentArray *ea, bool dont_fragment) { uint64_t begin = offset, end = offset; - uint64_t overall_end = offset + *length; - unsigned int i = 0; + uint64_t overall_end = offset + length; BdrvDirtyBitmapIter *it; bool dirty; @@ -2050,8 +2086,7 @@ static unsigned int bitmap_to_extents(BdrvDirtyBitmap *bitmap, uint64_t offset, it = bdrv_dirty_iter_new(bitmap); dirty = bdrv_dirty_bitmap_get_locked(bitmap, offset); - assert(begin < overall_end && nb_extents); - while (begin < overall_end && i < nb_extents) { + while (begin < overall_end) { bool next_dirty = !dirty; if (dirty) { @@ -2071,9 +2106,10 @@ static unsigned int bitmap_to_extents(BdrvDirtyBitmap *bitmap, uint64_t offset, end = overall_end; } - extents[i].length = cpu_to_be32(end - begin); - extents[i].flags = cpu_to_be32(dirty ? NBD_STATE_DIRTY : 0); - i++; + if (nbd_extent_array_add(ea, end - begin, + dirty ? NBD_STATE_DIRTY : 0) < 0) { + break; + } begin = end; dirty = next_dirty; } @@ -2083,8 +2119,6 @@ static unsigned int bitmap_to_extents(BdrvDirtyBitmap *bitmap, uint64_t offset, bdrv_dirty_bitmap_unlock(bitmap); assert(offset < end); - *length = end - offset; - return i; } static int nbd_co_send_bitmap(NBDClient *client, uint64_t handle, @@ -2092,20 +2126,12 @@ static int nbd_co_send_bitmap(NBDClient *client, uint64_t handle, uint32_t length, bool dont_fragment, bool last, uint32_t context_id, Error **errp) { - int ret; unsigned int nb_extents = dont_fragment ? 1 : NBD_MAX_BLOCK_STATUS_EXTENTS; - NBDExtent *extents = g_new(NBDExtent, nb_extents); - uint64_t final_length = length; + g_autoptr(NBDExtentArray) ea = nbd_extent_array_new(nb_extents); - nb_extents = bitmap_to_extents(bitmap, offset, &final_length, extents, - nb_extents, dont_fragment); + bitmap_to_extents(bitmap, offset, length, ea, dont_fragment); - ret = nbd_co_send_extents(client, handle, extents, nb_extents, - final_length, last, context_id, errp); - - g_free(extents); - - return ret; + return nbd_co_send_extents(client, handle, ea, last, context_id, errp); } /* nbd_co_receive_request -- 2.21.1

From: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> store_bitmap_data() loop does bdrv_set_dirty_iter() on each iteration, which means that we actually don't need iterator itself and we can use simpler bitmap API. Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Reviewed-by: Max Reitz <mreitz@redhat.com> Reviewed-by: John Snow <jsnow@redhat.com> Message-id: 20200205112041.6003-11-vsementsov@virtuozzo.com Signed-off-by: John Snow <jsnow@redhat.com> --- block/qcow2-bitmap.c | 15 +++++---------- 1 file changed, 5 insertions(+), 10 deletions(-) diff --git a/block/qcow2-bitmap.c b/block/qcow2-bitmap.c index 8cccc2c9f3..cb06954b4a 100644 --- a/block/qcow2-bitmap.c +++ b/block/qcow2-bitmap.c @@ -1288,7 +1288,6 @@ static uint64_t *store_bitmap_data(BlockDriverState *bs, uint64_t bm_size = bdrv_dirty_bitmap_size(bitmap); const char *bm_name = bdrv_dirty_bitmap_name(bitmap); uint8_t *buf = NULL; - BdrvDirtyBitmapIter *dbi; uint64_t *tb; uint64_t tb_size = size_to_clusters(s, @@ -1307,12 +1306,14 @@ static uint64_t *store_bitmap_data(BlockDriverState *bs, return NULL; } - dbi = bdrv_dirty_iter_new(bitmap); buf = g_malloc(s->cluster_size); limit = bytes_covered_by_bitmap_cluster(s, bitmap); assert(DIV_ROUND_UP(bm_size, limit) == tb_size); - while ((offset = bdrv_dirty_iter_next(dbi)) >= 0) { + offset = 0; + while ((offset = bdrv_dirty_bitmap_next_dirty(bitmap, offset, INT64_MAX)) + >= 0) + { uint64_t cluster = offset / limit; uint64_t end, write_size; int64_t off; @@ -1355,23 +1356,17 @@ static uint64_t *store_bitmap_data(BlockDriverState *bs, goto fail; } - if (end >= bm_size) { - break; - } - - bdrv_set_dirty_iter(dbi, end); + offset = end; } *bitmap_table_size = tb_size; g_free(buf); - bdrv_dirty_iter_free(dbi); return tb; fail: clear_bitmap_table(bs, tb, tb_size); g_free(buf); - bdrv_dirty_iter_free(dbi); g_free(tb); return NULL; -- 2.21.1