/* * Hierarchical bitmap unit-tests. * * Copyright (C) 2012 Red Hat Inc. * * Author: Paolo Bonzini * * This work is licensed under the terms of the GNU GPL, version 2 or later. * See the COPYING file in the top-level directory. */ #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) #define L1 BITS_PER_LONG #define L2 (BITS_PER_LONG * L1) #define L3 (BITS_PER_LONG * L2) typedef struct TestHBitmapData { HBitmap *hb; unsigned long *bits; size_t size; size_t old_size; int granularity; } TestHBitmapData; /* Check that the HBitmap and the shadow bitmap contain the same data, * ignoring the same "first" bits. */ static void hbitmap_test_check(TestHBitmapData *data, uint64_t first) { uint64_t count = 0; size_t pos; int bit; HBitmapIter hbi; int64_t i, next; hbitmap_iter_init(&hbi, data->hb, first); i = first; for (;;) { next = hbitmap_iter_next(&hbi); if (next < 0) { next = data->size; } while (i < next) { pos = i >> LOG_BITS_PER_LONG; bit = i & (BITS_PER_LONG - 1); i++; g_assert_cmpint(data->bits[pos] & (1UL << bit), ==, 0); } if (next == data->size) { break; } pos = i >> LOG_BITS_PER_LONG; bit = i & (BITS_PER_LONG - 1); i++; count++; g_assert_cmpint(data->bits[pos] & (1UL << bit), !=, 0); } if (first == 0) { g_assert_cmpint(count << data->granularity, ==, hbitmap_count(data->hb)); } } /* This is provided instead of a test setup function so that the sizes are kept in the test functions (and not in main()) */ static void hbitmap_test_init(TestHBitmapData *data, uint64_t size, int granularity) { size_t n; data->hb = hbitmap_alloc(size, granularity); n = DIV_ROUND_UP(size, BITS_PER_LONG); if (n == 0) { n = 1; } data->bits = g_new0(unsigned long, n); data->size = size; data->granularity = granularity; if (size) { hbitmap_test_check(data, 0); } } static inline size_t hbitmap_test_array_size(size_t bits) { size_t n = DIV_ROUND_UP(bits, BITS_PER_LONG); return n ? n : 1; } static void hbitmap_test_truncate_impl(TestHBitmapData *data, size_t size) { size_t n; size_t m; data->old_size = data->size; data->size = size; if (data->size == data->old_size) { return; } n = hbitmap_test_array_size(size); m = hbitmap_test_array_size(data->old_size); data->bits = g_realloc(data->bits, sizeof(unsigned long) * n); if (n > m) { memset(&data->bits[m], 0x00, sizeof(unsigned long) * (n - m)); } /* If we shrink to an uneven multiple of sizeof(unsigned long), * scrub the leftover memory. */ if (data->size < data->old_size) { m = size % (sizeof(unsigned long) * 8); if (m) { unsigned long mask = (1ULL << m) - 1; data->bits[n-1] &= mask; } } hbitmap_truncate(data->hb, size); } static void hbitmap_test_teardown(TestHBitmapData *data, const void *unused) { if (data->hb) { hbitmap_free(data->hb); data->hb = NULL; } g_free(data->bits); data->bits = NULL; } /* Set a range in the HBitmap and in the shadow "simple" bitmap. * The two bitmaps are then tested against each other. */ static void hbitmap_test_set(TestHBitmapData *data, uint64_t first, uint64_t count) { hbitmap_set(data->hb, first, count); while (count-- != 0) { size_t pos = first >> LOG_BITS_PER_LONG; int bit = first & (BITS_PER_LONG - 1); first++; data->bits[pos] |= 1UL << bit; } if (data->granularity == 0) { hbitmap_test_check(data, 0); } } /* Reset a range in the HBitmap and in the shadow "simple" bitmap. */ static void hbitmap_test_reset(TestHBitmapData *data, uint64_t first, uint64_t count) { hbitmap_reset(data->hb, first, count); while (count-- != 0) { size_t pos = first >> LOG_BITS_PER_LONG; int bit = first & (BITS_PER_LONG - 1); first++; data->bits[pos] &= ~(1UL << bit); } if (data->granularity == 0) { hbitmap_test_check(data, 0); } } static void hbitmap_test_reset_all(TestHBitmapData *data) { size_t n; hbitmap_reset_all(data->hb); n = DIV_ROUND_UP(data->size, BITS_PER_LONG); if (n == 0) { n = 1; } memset(data->bits, 0, n * sizeof(unsigned long)); if (data->granularity == 0) { hbitmap_test_check(data, 0); } } static void hbitmap_test_check_get(TestHBitmapData *data) { uint64_t count = 0; uint64_t i; for (i = 0; i < data->size; i++) { size_t pos = i >> LOG_BITS_PER_LONG; int bit = i & (BITS_PER_LONG - 1); unsigned long val = data->bits[pos] & (1UL << bit); count += hbitmap_get(data->hb, i); g_assert_cmpint(hbitmap_get(data->hb, i), ==, val != 0); } g_assert_cmpint(count, ==, hbitmap_count(data->hb)); } static void test_hbitmap_zero(TestHBitmapData *data, const void *unused) { hbitmap_test_init(data, 0, 0); } static void test_hbitmap_unaligned(TestHBitmapData *data, const void *unused) { hbitmap_test_init(data, L3 + 23, 0); hbitmap_test_set(data, 0, 1); hbitmap_test_set(data, L3 + 22, 1); } static void test_hbitmap_iter_empty(TestHBitmapData *data, const void *unused) { hbitmap_test_init(data, L1, 0); } static void test_hbitmap_iter_partial(TestHBitmapData *data, const void *unused) { hbitmap_test_init(data, L3, 0); hbitmap_test_set(data, 0, L3); hbitmap_test_check(data, 1); hbitmap_test_check(data, L1 - 1); hbitmap_test_check(data, L1); hbitmap_test_check(data, L1 * 2 - 1); hbitmap_test_check(data, L2 - 1); hbitmap_test_check(data, L2); hbitmap_test_check(data, L2 + 1); hbitmap_test_check(data, L2 + L1); hbitmap_test_check(data, L2 + L1 * 2 - 1); hbitmap_test_check(data, L2 * 2 - 1); hbitmap_test_check(data, L2 * 2); hbitmap_test_check(data, L2 * 2 + 1); hbitmap_test_check(data, L2 * 2 + L1); hbitmap_test_check(data, L2 * 2 + L1 * 2 - 1); hbitmap_test_check(data, L3 / 2); } static void test_hbitmap_set_all(TestHBitmapData *data, const void *unused) { hbitmap_test_init(data, L3, 0); hbitmap_test_set(data, 0, L3); } static void test_hbitmap_get_all(TestHBitmapData *data, const void *unused) { hbitmap_test_init(data, L3, 0); hbitmap_test_set(data, 0, L3); hbitmap_test_check_get(data); } static void test_hbitmap_get_some(TestHBitmapData *data, const void *unused) { hbitmap_test_init(data, 2 * L2, 0); hbitmap_test_set(data, 10, 1); hbitmap_test_check_get(data); hbitmap_test_set(data, L1 - 1, 1); hbitmap_test_check_get(data); hbitmap_test_set(data, L1, 1); hbitmap_test_check_get(data); hbitmap_test_set(data, L2 - 1, 1); hbitmap_test_check_get(data); hbitmap_test_set(data, L2, 1); hbitmap_test_check_get(data); } static void test_hbitmap_set_one(TestHBitmapData *data, const void *unused) { hbitmap_test_init(data, 2 * L2, 0); hbitmap_test_set(data, 10, 1); hbitmap_test_set(data, L1 - 1, 1); hbitmap_test_set(data, L1, 1); hbitmap_test_set(data, L2 - 1, 1); hbitmap_test_set(data, L2, 1); } static void test_hbitmap_set_two_elem(TestHBitmapData *data, const void *unused) { hbitmap_test_init(data, 2 * L2, 0); hbitmap_test_set(data, L1 - 1, 2); hbitmap_test_set(data, L1 * 2 - 1, 4); hbitmap_test_set(data, L1 * 4, L1 + 1); hbitmap_test_set(data, L1 * 8 - 1, L1 + 1); hbitmap_test_set(data, L2 - 1, 2); hbitmap_test_set(data, L2 + L1 - 1, 8); hbitmap_test_set(data, L2 + L1 * 4, L1 + 1); hbitmap_test_set(data, L2 + L1 * 8 - 1, L1 + 1); } static void test_hbitmap_set(TestHBitmapData *data, const void *unused) { hbitmap_test_init(data, L3 * 2, 0); hbitmap_test_set(data, L1 - 1, L1 + 2); hbitmap_test_set(data, L1 * 3 - 1, L1 + 2); hbitmap_test_set(data, L1 * 5, L1 * 2 + 1); hbitmap_test_set(data, L1 * 8 - 1, L1 * 2 + 1); hbitmap_test_set(data, L2 - 1, L1 + 2); hbitmap_test_set(data, L2 + L1 * 2 - 1, L1 + 2); hbitmap_test_set(data, L2 + L1 * 4, L1 * 2 + 1); hbitmap_test_set(data, L2 + L1 * 7 - 1, L1 * 2 + 1); hbitmap_test_set(data, L2 * 2 - 1, L3 * 2 - L2 * 2); } static void test_hbitmap_set_twice(TestHBitmapData *data, const void *unused) { hbitmap_test_init(data, L1 * 3, 0); hbitmap_test_set(data, 0, L1 * 3); hbitmap_test_set(data, L1, 1); } static void test_hbitmap_set_overlap(TestHBitmapData *data, const void *unused) { hbitmap_test_init(data, L3 * 2, 0); hbitmap_test_set(data, L1 - 1, L1 + 2); hbitmap_test_set(data, L1 * 2 - 1, L1 * 2 + 2); hbitmap_test_set(data, 0, L1 * 3); hbitmap_test_set(data, L1 * 8 - 1, L2); hbitmap_test_set(data, L2, L1); hbitmap_test_set(data, L2 - L1 - 1, L1 * 8 + 2); hbitmap_test_set(data, L2, L3 - L2 + 1); hbitmap_test_set(data, L3 - L1, L1 * 3); hbitmap_test_set(data, L3 - 1, 3); hbitmap_test_set(data, L3 - 1, L2); } static void test_hbitmap_reset_empty(TestHBitmapData *data, const void *unused) { hbitmap_test_init(data, L3, 0); hbitmap_test_reset(data, 0, L3); } static void test_hbitmap_reset(TestHBitmapData *data, const void *unused) { hbitmap_test_init(data, L3 * 2, 0); hbitmap_test_set(data, L1 - 1, L1 + 2); hbitmap_test_reset(data, L1 * 2 - 1, L1 * 2 + 2); hbitmap_test_set(data, 0, L1 * 3); hbitmap_test_reset(data, L1 * 8 - 1, L2); hbitmap_test_set(data, L2, L1); hbitmap_test_reset(data, L2 - L1 - 1, L1 * 8 + 2); hbitmap_test_set(data, L2, L3 - L2 + 1); hbitmap_test_reset(data, L3 - L1, L1 * 3); hbitmap_test_set(data, L3 - 1, 3); hbitmap_test_reset(data, L3 - 1, L2); hbitmap_test_set(data, 0, L3 * 2); hbitmap_test_reset(data, 0, L1); hbitmap_test_reset(data, 0, L2); hbitmap_test_reset(data, L3, L3); hbitmap_test_set(data, L3 / 2, L3); } static void test_hbitmap_reset_all(TestHBitmapData *data, const void *unused) { hbitmap_test_init(data, L3 * 2, 0); hbitmap_test_set(data, L1 - 1, L1 + 2); hbitmap_test_reset_all(data); hbitmap_test_set(data, 0, L1 * 3); hbitmap_test_reset_all(data); hbitmap_test_set(data, L2, L1); hbitmap_test_reset_all(data); hbitmap_test_set(data, L2, L3 - L2 + 1); hbitmap_test_reset_all(data); hbitmap_test_set(data, L3 - 1, 3); hbitmap_test_reset_all(data); hbitmap_test_set(data, 0, L3 * 2); hbitmap_test_reset_all(data); hbitmap_test_set(data, L3 / 2, L3); hbitmap_test_reset_all(data); } static void test_hbitmap_granularity(TestHBitmapData *data, const void *unused) { /* Note that hbitmap_test_check has to be invoked manually in this test. */ hbitmap_test_init(data, L1, 1); hbitmap_test_set(data, 0, 1); g_assert_cmpint(hbitmap_count(data->hb), ==, 2); hbitmap_test_check(data, 0); hbitmap_test_set(data, 2, 1); g_assert_cmpint(hbitmap_count(data->hb), ==, 4); hbitmap_test_check(data, 0); hbitmap_test_set(data, 0, 3); g_assert_cmpint(hbitmap_count(data->hb), ==, 4); hbitmap_test_reset(data, 0, 2); g_assert_cmpint(hbitmap_count(data->hb), ==, 2); } static void test_hbitmap_iter_granularity(TestHBitmapData *data, const void *unused) { HBitmapIter hbi; /* 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), <, 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), ==, (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), <, 0); hbitmap_test_set(data, (131072 << 7) - 8, 8); hbitmap_iter_init(&hbi, data->hb, 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), ==, 131071 << 7); g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0); } static void hbitmap_test_set_boundary_bits(TestHBitmapData *data, ssize_t diff) { size_t size = data->size; /* First bit */ hbitmap_test_set(data, 0, 1); if (diff < 0) { /* Last bit in new, shortened map */ hbitmap_test_set(data, size + diff - 1, 1); /* First bit to be truncated away */ hbitmap_test_set(data, size + diff, 1); } /* Last bit */ hbitmap_test_set(data, size - 1, 1); if (data->granularity == 0) { hbitmap_test_check_get(data); } } static void hbitmap_test_check_boundary_bits(TestHBitmapData *data) { size_t size = MIN(data->size, data->old_size); if (data->granularity == 0) { hbitmap_test_check_get(data); hbitmap_test_check(data, 0); } else { /* If a granularity was set, note that every distinct * (bit >> granularity) value that was set will increase * the bit pop count by 2^granularity, not just 1. * * The hbitmap_test_check facility does not currently tolerate * non-zero granularities, so test the boundaries and the population * count manually. */ g_assert(hbitmap_get(data->hb, 0)); g_assert(hbitmap_get(data->hb, size - 1)); g_assert_cmpint(2 << data->granularity, ==, hbitmap_count(data->hb)); } } /* Generic truncate test. */ static void hbitmap_test_truncate(TestHBitmapData *data, size_t size, ssize_t diff, int granularity) { hbitmap_test_init(data, size, granularity); hbitmap_test_set_boundary_bits(data, diff); hbitmap_test_truncate_impl(data, size + diff); hbitmap_test_check_boundary_bits(data); } static void test_hbitmap_truncate_nop(TestHBitmapData *data, const void *unused) { hbitmap_test_truncate(data, L2, 0, 0); } /** * Grow by an amount smaller than the granularity, without crossing * a granularity alignment boundary. Effectively a NOP. */ static void test_hbitmap_truncate_grow_negligible(TestHBitmapData *data, const void *unused) { size_t size = L2 - 1; size_t diff = 1; int granularity = 1; hbitmap_test_truncate(data, size, diff, granularity); } /** * Shrink by an amount smaller than the granularity, without crossing * a granularity alignment boundary. Effectively a NOP. */ static void test_hbitmap_truncate_shrink_negligible(TestHBitmapData *data, const void *unused) { size_t size = L2; ssize_t diff = -1; int granularity = 1; hbitmap_test_truncate(data, size, diff, granularity); } /** * Grow by an amount smaller than the granularity, but crossing over * a granularity alignment boundary. */ static void test_hbitmap_truncate_grow_tiny(TestHBitmapData *data, const void *unused) { size_t size = L2 - 2; ssize_t diff = 1; int granularity = 1; hbitmap_test_truncate(data, size, diff, granularity); } /** * Shrink by an amount smaller than the granularity, but crossing over * a granularity alignment boundary. */ static void test_hbitmap_truncate_shrink_tiny(TestHBitmapData *data, const void *unused) { size_t size = L2 - 1; ssize_t diff = -1; int granularity = 1; hbitmap_test_truncate(data, size, diff, granularity); } /** * Grow by an amount smaller than sizeof(long), and not crossing over * a sizeof(long) alignment boundary. */ static void test_hbitmap_truncate_grow_small(TestHBitmapData *data, const void *unused) { size_t size = L2 + 1; size_t diff = sizeof(long) / 2; hbitmap_test_truncate(data, size, diff, 0); } /** * Shrink by an amount smaller than sizeof(long), and not crossing over * a sizeof(long) alignment boundary. */ static void test_hbitmap_truncate_shrink_small(TestHBitmapData *data, const void *unused) { size_t size = L2; size_t diff = sizeof(long) / 2; hbitmap_test_truncate(data, size, -diff, 0); } /** * Grow by an amount smaller than sizeof(long), while crossing over * a sizeof(long) alignment boundary. */ static void test_hbitmap_truncate_grow_medium(TestHBitmapData *data, const void *unused) { size_t size = L2 - 1; size_t diff = sizeof(long) / 2; hbitmap_test_truncate(data, size, diff, 0); } /** * Shrink by an amount smaller than sizeof(long), while crossing over * a sizeof(long) alignment boundary. */ static void test_hbitmap_truncate_shrink_medium(TestHBitmapData *data, const void *unused) { size_t size = L2 + 1; size_t diff = sizeof(long) / 2; hbitmap_test_truncate(data, size, -diff, 0); } /** * Grow by an amount larger than sizeof(long). */ static void test_hbitmap_truncate_grow_large(TestHBitmapData *data, const void *unused) { size_t size = L2; size_t diff = 8 * sizeof(long); hbitmap_test_truncate(data, size, diff, 0); } /** * Shrink by an amount larger than sizeof(long). */ static void test_hbitmap_truncate_shrink_large(TestHBitmapData *data, const void *unused) { size_t size = L2; size_t diff = 8 * sizeof(long); hbitmap_test_truncate(data, size, -diff, 0); } static void test_hbitmap_serialize_align(TestHBitmapData *data, const void *unused) { int r; hbitmap_test_init(data, L3 * 2, 3); g_assert(hbitmap_is_serializable(data->hb)); r = hbitmap_serialization_align(data->hb); g_assert_cmpint(r, ==, 64 << 3); } 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); } g_assert(hbitmap_is_serializable(data->hb)); 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); g_assert(hbitmap_is_serializable(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 = ARRAY_SIZE(positions); hbitmap_test_init(data, L3, 0); g_assert(hbitmap_is_serializable(data->hb)); 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 = ARRAY_SIZE(positions); 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); } g_assert(hbitmap_is_serializable(data->hb)); 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 = ARRAY_SIZE(positions); hbitmap_test_init(data, L3, 0); for (i = 0; i < num_positions; i++) { hbitmap_set(data->hb, positions[i], L1); } g_assert(hbitmap_is_serializable(data->hb)); 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)) { g_test_add(testpath, TestHBitmapData, NULL, NULL, test_func, hbitmap_test_teardown); } static void test_hbitmap_iter_and_reset(TestHBitmapData *data, const void *unused) { HBitmapIter hbi; hbitmap_test_init(data, L1 * 2, 0); hbitmap_set(data->hb, 0, data->size); hbitmap_iter_init(&hbi, data->hb, BITS_PER_LONG - 1); hbitmap_iter_next(&hbi); hbitmap_reset_all(data->hb); hbitmap_iter_next(&hbi); } static void test_hbitmap_next_x_check_range(TestHBitmapData *data, int64_t start, int64_t count) { 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 (next = start; next < end && hbitmap_get(data->hb, next) == first_bit; next++) { ; } if (next == end) { next = -1; } g_assert_cmpint(next_dirty, ==, first_bit ? start : next); g_assert_cmpint(next_zero, ==, first_bit ? next : start); } static void test_hbitmap_next_x_check(TestHBitmapData *data, int64_t start) { test_hbitmap_next_x_check_range(data, start, INT64_MAX); } static void test_hbitmap_next_x_do(TestHBitmapData *data, int granularity) { hbitmap_test_init(data, L3, granularity); 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_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_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_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_x_check(data, 0); } static void test_hbitmap_next_x_0(TestHBitmapData *data, const void *unused) { test_hbitmap_next_x_do(data, 0); } static void test_hbitmap_next_x_4(TestHBitmapData *data, const void *unused) { test_hbitmap_next_x_do(data, 4); } 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_x_check(data, 0); } static void test_hbitmap_next_dirty_area_check_limited(TestHBitmapData *data, int64_t offset, int64_t count, int64_t max_dirty) { int64_t off1, off2; int64_t len1 = 0, len2; bool ret1, ret2; int64_t end; ret1 = hbitmap_next_dirty_area(data->hb, offset, count == INT64_MAX ? INT64_MAX : offset + count, max_dirty, &off1, &len1); end = offset > data->size || data->size - offset < count ? data->size : offset + count; for (off2 = offset; off2 < end && !hbitmap_get(data->hb, off2); off2++) { ; } for (len2 = 1; (off2 + len2 < end && len2 < max_dirty && hbitmap_get(data->hb, off2 + len2)); len2++) { ; } ret2 = off2 < end; g_assert_cmpint(ret1, ==, ret2); if (ret2) { g_assert_cmpint(off1, ==, off2); g_assert_cmpint(len1, ==, len2); } } static void test_hbitmap_next_dirty_area_check(TestHBitmapData *data, int64_t offset, int64_t count) { test_hbitmap_next_dirty_area_check_limited(data, offset, count, INT64_MAX); } 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, INT64_MAX); test_hbitmap_next_dirty_area_check(data, 0, 1); test_hbitmap_next_dirty_area_check(data, L3 - 1, 1); test_hbitmap_next_dirty_area_check_limited(data, 0, INT64_MAX, 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, INT64_MAX); test_hbitmap_next_dirty_area_check(data, L2 - 1, INT64_MAX); 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, INT64_MAX); test_hbitmap_next_dirty_area_check(data, L2, 1); test_hbitmap_next_dirty_area_check(data, L2 + 1, 1); test_hbitmap_next_dirty_area_check_limited(data, 0, INT64_MAX, 1); test_hbitmap_next_dirty_area_check_limited(data, L2 - 1, 2, 1); hbitmap_set(data->hb, L2 + 5, L1); test_hbitmap_next_dirty_area_check(data, 0, INT64_MAX); 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); test_hbitmap_next_dirty_area_check_limited(data, L2 + 3, INT64_MAX, 3); test_hbitmap_next_dirty_area_check_limited(data, L2 + 3, 7, 10); hbitmap_set(data->hb, L2 * 2, L3 - L2 * 2); test_hbitmap_next_dirty_area_check(data, 0, INT64_MAX); test_hbitmap_next_dirty_area_check(data, L2, INT64_MAX); test_hbitmap_next_dirty_area_check(data, L2 + 1, INT64_MAX); test_hbitmap_next_dirty_area_check(data, L2 + 5 + L1 - 1, INT64_MAX); 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); test_hbitmap_next_dirty_area_check_limited(data, L2 * 2 + 1, INT64_MAX, 5); test_hbitmap_next_dirty_area_check_limited(data, L2 * 2 + 1, 10, 5); test_hbitmap_next_dirty_area_check_limited(data, L2 * 2 + 1, 2, 5); hbitmap_set(data->hb, 0, L3); test_hbitmap_next_dirty_area_check(data, 0, INT64_MAX); } 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); } static void test_hbitmap_next_dirty_area_after_truncate(TestHBitmapData *data, const void *unused) { hbitmap_test_init(data, L1, 0); hbitmap_test_truncate_impl(data, L1 * 2); hbitmap_set(data->hb, L1 + 1, 1); test_hbitmap_next_dirty_area_check(data, 0, INT64_MAX); } int main(int argc, char **argv) { g_test_init(&argc, &argv, NULL); hbitmap_test_add("/hbitmap/size/0", test_hbitmap_zero); hbitmap_test_add("/hbitmap/size/unaligned", test_hbitmap_unaligned); hbitmap_test_add("/hbitmap/iter/empty", test_hbitmap_iter_empty); hbitmap_test_add("/hbitmap/iter/partial", test_hbitmap_iter_partial); hbitmap_test_add("/hbitmap/iter/granularity", test_hbitmap_iter_granularity); hbitmap_test_add("/hbitmap/get/all", test_hbitmap_get_all); hbitmap_test_add("/hbitmap/get/some", test_hbitmap_get_some); hbitmap_test_add("/hbitmap/set/all", test_hbitmap_set_all); hbitmap_test_add("/hbitmap/set/one", test_hbitmap_set_one); hbitmap_test_add("/hbitmap/set/two-elem", test_hbitmap_set_two_elem); hbitmap_test_add("/hbitmap/set/general", test_hbitmap_set); hbitmap_test_add("/hbitmap/set/twice", test_hbitmap_set_twice); hbitmap_test_add("/hbitmap/set/overlap", test_hbitmap_set_overlap); hbitmap_test_add("/hbitmap/reset/empty", test_hbitmap_reset_empty); hbitmap_test_add("/hbitmap/reset/general", test_hbitmap_reset); hbitmap_test_add("/hbitmap/reset/all", test_hbitmap_reset_all); hbitmap_test_add("/hbitmap/granularity", test_hbitmap_granularity); hbitmap_test_add("/hbitmap/truncate/nop", test_hbitmap_truncate_nop); hbitmap_test_add("/hbitmap/truncate/grow/negligible", test_hbitmap_truncate_grow_negligible); hbitmap_test_add("/hbitmap/truncate/shrink/negligible", test_hbitmap_truncate_shrink_negligible); hbitmap_test_add("/hbitmap/truncate/grow/tiny", test_hbitmap_truncate_grow_tiny); hbitmap_test_add("/hbitmap/truncate/shrink/tiny", test_hbitmap_truncate_shrink_tiny); hbitmap_test_add("/hbitmap/truncate/grow/small", test_hbitmap_truncate_grow_small); hbitmap_test_add("/hbitmap/truncate/shrink/small", test_hbitmap_truncate_shrink_small); hbitmap_test_add("/hbitmap/truncate/grow/medium", test_hbitmap_truncate_grow_medium); hbitmap_test_add("/hbitmap/truncate/shrink/medium", test_hbitmap_truncate_shrink_medium); hbitmap_test_add("/hbitmap/truncate/grow/large", test_hbitmap_truncate_grow_large); hbitmap_test_add("/hbitmap/truncate/shrink/large", test_hbitmap_truncate_shrink_large); hbitmap_test_add("/hbitmap/serialize/align", test_hbitmap_serialize_align); 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); hbitmap_test_add("/hbitmap/iter/iter_and_reset", test_hbitmap_iter_and_reset); 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); 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); hbitmap_test_add("/hbitmap/next_dirty_area/next_dirty_area_after_truncate", test_hbitmap_next_dirty_area_after_truncate); g_test_run(); return 0; }