diff options
Diffstat (limited to 'tests/test-hbitmap.c')
| -rw-r--r-- | tests/test-hbitmap.c | 272 |
1 files changed, 272 insertions, 0 deletions
diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c index c0e9895fb9..9b7495cc32 100644 --- a/tests/test-hbitmap.c +++ b/tests/test-hbitmap.c @@ -11,6 +11,8 @@ #include "qemu/osdep.h" #include "qemu/hbitmap.h" +#include "qemu/bitmap.h" +#include "block/block.h" #define LOG_BITS_PER_LONG (BITS_PER_LONG == 32 ? 5 : 6) @@ -20,6 +22,7 @@ typedef struct TestHBitmapData { HBitmap *hb; + HBitmap *meta; unsigned long *bits; size_t size; size_t old_size; @@ -91,6 +94,14 @@ 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); @@ -133,6 +144,9 @@ 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; } @@ -634,6 +648,249 @@ 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_granularity(TestHBitmapData *data, + const void *unused) +{ + int r; + + hbitmap_test_init(data, L3 * 2, 3); + r = hbitmap_serialization_granularity(data->hb); + 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) +{ + size_t i; + unsigned long *el = (unsigned long *)buf; + + assert(hbitmap_granularity(data->hb) == 0); + hbitmap_reset_all(data->hb); + memset(buf, 0, buf_size); + if (count) { + hbitmap_set(data->hb, pos, count); + } + hbitmap_serialize_part(data->hb, buf, 0, data->size); + + /* Serialized buffer is inherently LE, convert it back manually to test */ + for (i = 0; i < buf_size / sizeof(unsigned long); i++) { + el[i] = (BITS_PER_LONG == 32 ? le32_to_cpu(el[i]) : le64_to_cpu(el[i])); + } + + for (i = 0; i < data->size; i++) { + int is_set = test_bit(i, (unsigned long *)buf); + if (i >= pos && i < pos + count) { + g_assert(is_set); + } else { + g_assert(!is_set); + } + } + + /* Re-serialize for deserialization testing */ + memset(buf, 0, buf_size); + hbitmap_serialize_part(data->hb, buf, 0, data->size); + hbitmap_reset_all(data->hb); + hbitmap_deserialize_part(data->hb, buf, 0, data->size, true); + + for (i = 0; i < data->size; i++) { + int is_set = hbitmap_get(data->hb, i); + if (i >= pos && i < pos + count) { + g_assert(is_set); + } else { + g_assert(!is_set); + } + } +} + +static void test_hbitmap_serialize_basic(TestHBitmapData *data, + const void *unused) +{ + int i, j; + size_t buf_size; + uint8_t *buf; + uint64_t positions[] = { 0, 1, L1 - 1, L1, L2 - 1, L2, L2 + 1, L3 - 1 }; + int num_positions = sizeof(positions) / sizeof(positions[0]); + + hbitmap_test_init(data, L3, 0); + buf_size = hbitmap_serialization_size(data->hb, 0, data->size); + buf = g_malloc0(buf_size); + + for (i = 0; i < num_positions; i++) { + for (j = 0; j < num_positions; j++) { + hbitmap_test_serialize_range(data, buf, buf_size, + positions[i], + MIN(positions[j], L3 - positions[i])); + } + } + + g_free(buf); +} + +static void test_hbitmap_serialize_part(TestHBitmapData *data, + const void *unused) +{ + int i, j, k; + size_t buf_size; + uint8_t *buf; + uint64_t positions[] = { 0, 1, L1 - 1, L1, L2 - 1, L2, L2 + 1, L3 - 1 }; + int num_positions = sizeof(positions) / sizeof(positions[0]); + + hbitmap_test_init(data, L3, 0); + buf_size = L2; + buf = g_malloc0(buf_size); + + for (i = 0; i < num_positions; i++) { + hbitmap_set(data->hb, positions[i], 1); + } + + for (i = 0; i < data->size; i += buf_size) { + unsigned long *el = (unsigned long *)buf; + hbitmap_serialize_part(data->hb, buf, i, buf_size); + for (j = 0; j < buf_size / sizeof(unsigned long); j++) { + el[j] = (BITS_PER_LONG == 32 ? le32_to_cpu(el[j]) : le64_to_cpu(el[j])); + } + + for (j = 0; j < buf_size; j++) { + bool should_set = false; + for (k = 0; k < num_positions; k++) { + if (positions[k] == j + i) { + should_set = true; + break; + } + } + g_assert_cmpint(should_set, ==, test_bit(j, (unsigned long *)buf)); + } + } + + g_free(buf); +} + +static void test_hbitmap_serialize_zeroes(TestHBitmapData *data, + const void *unused) +{ + int i; + HBitmapIter iter; + int64_t next; + uint64_t min_l1 = MAX(L1, 64); + uint64_t positions[] = { 0, min_l1, L2, L3 - min_l1}; + int num_positions = sizeof(positions) / sizeof(positions[0]); + + hbitmap_test_init(data, L3, 0); + + for (i = 0; i < num_positions; i++) { + hbitmap_set(data->hb, positions[i], L1); + } + + 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); + if (i == num_positions - 1) { + g_assert_cmpint(next, ==, -1); + } else { + g_assert_cmpint(next, ==, positions[i + 1]); + } + } +} + static void hbitmap_test_add(const char *testpath, void (*test_func)(TestHBitmapData *data, const void *user_data)) { @@ -683,6 +940,21 @@ int main(int argc, char **argv) test_hbitmap_truncate_grow_large); 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/granularity", + test_hbitmap_serialize_granularity); + hbitmap_test_add("/hbitmap/serialize/basic", + test_hbitmap_serialize_basic); + hbitmap_test_add("/hbitmap/serialize/part", + test_hbitmap_serialize_part); + hbitmap_test_add("/hbitmap/serialize/zeroes", + test_hbitmap_serialize_zeroes); g_test_run(); return 0; |