aboutsummaryrefslogtreecommitdiff
path: root/tests/test-hbitmap.c
diff options
context:
space:
mode:
Diffstat (limited to 'tests/test-hbitmap.c')
-rw-r--r--tests/test-hbitmap.c255
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;
generated by cgit v1.2.3 (git 2.26.2) at 2024-12-22 03:09:39 +0000