diff options
| -rw-r--r-- | tests/test-hbitmap.c | 255 |
1 files changed, 255 insertions, 0 deletions
diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c index 8c902f2055..9f41b5fd2e 100644 --- a/tests/test-hbitmap.c +++ b/tests/test-hbitmap.c @@ -11,6 +11,8 @@ #include <glib.h> #include <stdarg.h> +#include <string.h> +#include <sys/types.h> #include "qemu/hbitmap.h" #define LOG_BITS_PER_LONG (BITS_PER_LONG == 32 ? 5 : 6) @@ -23,6 +25,7 @@ typedef struct TestHBitmapData { HBitmap *hb; unsigned long *bits; size_t size; + size_t old_size; int granularity; } TestHBitmapData; @@ -91,6 +94,44 @@ static void hbitmap_test_init(TestHBitmapData *data, } } +static inline size_t hbitmap_test_array_size(size_t bits) +{ + size_t n = (bits + BITS_PER_LONG - 1) / 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) { @@ -369,6 +410,198 @@ static void test_hbitmap_iter_granularity(TestHBitmapData *data, 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 hbitmap_test_add(const char *testpath, void (*test_func)(TestHBitmapData *data, const void *user_data)) { @@ -395,6 +628,28 @@ int main(int argc, char **argv) hbitmap_test_add("/hbitmap/reset/empty", test_hbitmap_reset_empty); hbitmap_test_add("/hbitmap/reset/general", test_hbitmap_reset); 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); g_test_run(); return 0; |