2 * Hierarchical bitmap unit-tests.
4 * Copyright (C) 2012 Red Hat Inc.
6 * Author: Paolo Bonzini <pbonzini@redhat.com>
8 * This work is licensed under the terms of the GNU GPL, version 2 or later.
9 * See the COPYING file in the top-level directory.
15 #include <sys/types.h>
16 #include "qemu/hbitmap.h"
18 #define LOG_BITS_PER_LONG (BITS_PER_LONG == 32 ? 5 : 6)
20 #define L1 BITS_PER_LONG
21 #define L2 (BITS_PER_LONG * L1)
22 #define L3 (BITS_PER_LONG * L2)
24 typedef struct TestHBitmapData {
33 /* Check that the HBitmap and the shadow bitmap contain the same data,
34 * ignoring the same "first" bits.
36 static void hbitmap_test_check(TestHBitmapData *data,
45 hbitmap_iter_init(&hbi, data->hb, first);
49 next = hbitmap_iter_next(&hbi);
55 pos = i >> LOG_BITS_PER_LONG;
56 bit = i & (BITS_PER_LONG - 1);
58 g_assert_cmpint(data->bits[pos] & (1UL << bit), ==, 0);
61 if (next == data->size) {
65 pos = i >> LOG_BITS_PER_LONG;
66 bit = i & (BITS_PER_LONG - 1);
69 g_assert_cmpint(data->bits[pos] & (1UL << bit), !=, 0);
73 g_assert_cmpint(count << data->granularity, ==, hbitmap_count(data->hb));
77 /* This is provided instead of a test setup function so that the sizes
78 are kept in the test functions (and not in main()) */
79 static void hbitmap_test_init(TestHBitmapData *data,
80 uint64_t size, int granularity)
83 data->hb = hbitmap_alloc(size, granularity);
85 n = (size + BITS_PER_LONG - 1) / BITS_PER_LONG;
89 data->bits = g_new0(unsigned long, n);
91 data->granularity = granularity;
93 hbitmap_test_check(data, 0);
97 static inline size_t hbitmap_test_array_size(size_t bits)
99 size_t n = (bits + BITS_PER_LONG - 1) / BITS_PER_LONG;
103 static void hbitmap_test_truncate_impl(TestHBitmapData *data,
108 data->old_size = data->size;
111 if (data->size == data->old_size) {
115 n = hbitmap_test_array_size(size);
116 m = hbitmap_test_array_size(data->old_size);
117 data->bits = g_realloc(data->bits, sizeof(unsigned long) * n);
119 memset(&data->bits[m], 0x00, sizeof(unsigned long) * (n - m));
122 /* If we shrink to an uneven multiple of sizeof(unsigned long),
123 * scrub the leftover memory. */
124 if (data->size < data->old_size) {
125 m = size % (sizeof(unsigned long) * 8);
127 unsigned long mask = (1ULL << m) - 1;
128 data->bits[n-1] &= mask;
132 hbitmap_truncate(data->hb, size);
135 static void hbitmap_test_teardown(TestHBitmapData *data,
139 hbitmap_free(data->hb);
148 /* Set a range in the HBitmap and in the shadow "simple" bitmap.
149 * The two bitmaps are then tested against each other.
151 static void hbitmap_test_set(TestHBitmapData *data,
152 uint64_t first, uint64_t count)
154 hbitmap_set(data->hb, first, count);
155 while (count-- != 0) {
156 size_t pos = first >> LOG_BITS_PER_LONG;
157 int bit = first & (BITS_PER_LONG - 1);
160 data->bits[pos] |= 1UL << bit;
163 if (data->granularity == 0) {
164 hbitmap_test_check(data, 0);
168 /* Reset a range in the HBitmap and in the shadow "simple" bitmap.
170 static void hbitmap_test_reset(TestHBitmapData *data,
171 uint64_t first, uint64_t count)
173 hbitmap_reset(data->hb, first, count);
174 while (count-- != 0) {
175 size_t pos = first >> LOG_BITS_PER_LONG;
176 int bit = first & (BITS_PER_LONG - 1);
179 data->bits[pos] &= ~(1UL << bit);
182 if (data->granularity == 0) {
183 hbitmap_test_check(data, 0);
187 static void hbitmap_test_reset_all(TestHBitmapData *data)
191 hbitmap_reset_all(data->hb);
193 n = (data->size + BITS_PER_LONG - 1) / BITS_PER_LONG;
197 memset(data->bits, 0, n * sizeof(unsigned long));
199 if (data->granularity == 0) {
200 hbitmap_test_check(data, 0);
204 static void hbitmap_test_check_get(TestHBitmapData *data)
209 for (i = 0; i < data->size; i++) {
210 size_t pos = i >> LOG_BITS_PER_LONG;
211 int bit = i & (BITS_PER_LONG - 1);
212 unsigned long val = data->bits[pos] & (1UL << bit);
213 count += hbitmap_get(data->hb, i);
214 g_assert_cmpint(hbitmap_get(data->hb, i), ==, val != 0);
216 g_assert_cmpint(count, ==, hbitmap_count(data->hb));
219 static void test_hbitmap_zero(TestHBitmapData *data,
222 hbitmap_test_init(data, 0, 0);
225 static void test_hbitmap_unaligned(TestHBitmapData *data,
228 hbitmap_test_init(data, L3 + 23, 0);
229 hbitmap_test_set(data, 0, 1);
230 hbitmap_test_set(data, L3 + 22, 1);
233 static void test_hbitmap_iter_empty(TestHBitmapData *data,
236 hbitmap_test_init(data, L1, 0);
239 static void test_hbitmap_iter_partial(TestHBitmapData *data,
242 hbitmap_test_init(data, L3, 0);
243 hbitmap_test_set(data, 0, L3);
244 hbitmap_test_check(data, 1);
245 hbitmap_test_check(data, L1 - 1);
246 hbitmap_test_check(data, L1);
247 hbitmap_test_check(data, L1 * 2 - 1);
248 hbitmap_test_check(data, L2 - 1);
249 hbitmap_test_check(data, L2);
250 hbitmap_test_check(data, L2 + 1);
251 hbitmap_test_check(data, L2 + L1);
252 hbitmap_test_check(data, L2 + L1 * 2 - 1);
253 hbitmap_test_check(data, L2 * 2 - 1);
254 hbitmap_test_check(data, L2 * 2);
255 hbitmap_test_check(data, L2 * 2 + 1);
256 hbitmap_test_check(data, L2 * 2 + L1);
257 hbitmap_test_check(data, L2 * 2 + L1 * 2 - 1);
258 hbitmap_test_check(data, L3 / 2);
261 static void test_hbitmap_set_all(TestHBitmapData *data,
264 hbitmap_test_init(data, L3, 0);
265 hbitmap_test_set(data, 0, L3);
268 static void test_hbitmap_get_all(TestHBitmapData *data,
271 hbitmap_test_init(data, L3, 0);
272 hbitmap_test_set(data, 0, L3);
273 hbitmap_test_check_get(data);
276 static void test_hbitmap_get_some(TestHBitmapData *data,
279 hbitmap_test_init(data, 2 * L2, 0);
280 hbitmap_test_set(data, 10, 1);
281 hbitmap_test_check_get(data);
282 hbitmap_test_set(data, L1 - 1, 1);
283 hbitmap_test_check_get(data);
284 hbitmap_test_set(data, L1, 1);
285 hbitmap_test_check_get(data);
286 hbitmap_test_set(data, L2 - 1, 1);
287 hbitmap_test_check_get(data);
288 hbitmap_test_set(data, L2, 1);
289 hbitmap_test_check_get(data);
292 static void test_hbitmap_set_one(TestHBitmapData *data,
295 hbitmap_test_init(data, 2 * L2, 0);
296 hbitmap_test_set(data, 10, 1);
297 hbitmap_test_set(data, L1 - 1, 1);
298 hbitmap_test_set(data, L1, 1);
299 hbitmap_test_set(data, L2 - 1, 1);
300 hbitmap_test_set(data, L2, 1);
303 static void test_hbitmap_set_two_elem(TestHBitmapData *data,
306 hbitmap_test_init(data, 2 * L2, 0);
307 hbitmap_test_set(data, L1 - 1, 2);
308 hbitmap_test_set(data, L1 * 2 - 1, 4);
309 hbitmap_test_set(data, L1 * 4, L1 + 1);
310 hbitmap_test_set(data, L1 * 8 - 1, L1 + 1);
311 hbitmap_test_set(data, L2 - 1, 2);
312 hbitmap_test_set(data, L2 + L1 - 1, 8);
313 hbitmap_test_set(data, L2 + L1 * 4, L1 + 1);
314 hbitmap_test_set(data, L2 + L1 * 8 - 1, L1 + 1);
317 static void test_hbitmap_set(TestHBitmapData *data,
320 hbitmap_test_init(data, L3 * 2, 0);
321 hbitmap_test_set(data, L1 - 1, L1 + 2);
322 hbitmap_test_set(data, L1 * 3 - 1, L1 + 2);
323 hbitmap_test_set(data, L1 * 5, L1 * 2 + 1);
324 hbitmap_test_set(data, L1 * 8 - 1, L1 * 2 + 1);
325 hbitmap_test_set(data, L2 - 1, L1 + 2);
326 hbitmap_test_set(data, L2 + L1 * 2 - 1, L1 + 2);
327 hbitmap_test_set(data, L2 + L1 * 4, L1 * 2 + 1);
328 hbitmap_test_set(data, L2 + L1 * 7 - 1, L1 * 2 + 1);
329 hbitmap_test_set(data, L2 * 2 - 1, L3 * 2 - L2 * 2);
332 static void test_hbitmap_set_twice(TestHBitmapData *data,
335 hbitmap_test_init(data, L1 * 3, 0);
336 hbitmap_test_set(data, 0, L1 * 3);
337 hbitmap_test_set(data, L1, 1);
340 static void test_hbitmap_set_overlap(TestHBitmapData *data,
343 hbitmap_test_init(data, L3 * 2, 0);
344 hbitmap_test_set(data, L1 - 1, L1 + 2);
345 hbitmap_test_set(data, L1 * 2 - 1, L1 * 2 + 2);
346 hbitmap_test_set(data, 0, L1 * 3);
347 hbitmap_test_set(data, L1 * 8 - 1, L2);
348 hbitmap_test_set(data, L2, L1);
349 hbitmap_test_set(data, L2 - L1 - 1, L1 * 8 + 2);
350 hbitmap_test_set(data, L2, L3 - L2 + 1);
351 hbitmap_test_set(data, L3 - L1, L1 * 3);
352 hbitmap_test_set(data, L3 - 1, 3);
353 hbitmap_test_set(data, L3 - 1, L2);
356 static void test_hbitmap_reset_empty(TestHBitmapData *data,
359 hbitmap_test_init(data, L3, 0);
360 hbitmap_test_reset(data, 0, L3);
363 static void test_hbitmap_reset(TestHBitmapData *data,
366 hbitmap_test_init(data, L3 * 2, 0);
367 hbitmap_test_set(data, L1 - 1, L1 + 2);
368 hbitmap_test_reset(data, L1 * 2 - 1, L1 * 2 + 2);
369 hbitmap_test_set(data, 0, L1 * 3);
370 hbitmap_test_reset(data, L1 * 8 - 1, L2);
371 hbitmap_test_set(data, L2, L1);
372 hbitmap_test_reset(data, L2 - L1 - 1, L1 * 8 + 2);
373 hbitmap_test_set(data, L2, L3 - L2 + 1);
374 hbitmap_test_reset(data, L3 - L1, L1 * 3);
375 hbitmap_test_set(data, L3 - 1, 3);
376 hbitmap_test_reset(data, L3 - 1, L2);
377 hbitmap_test_set(data, 0, L3 * 2);
378 hbitmap_test_reset(data, 0, L1);
379 hbitmap_test_reset(data, 0, L2);
380 hbitmap_test_reset(data, L3, L3);
381 hbitmap_test_set(data, L3 / 2, L3);
384 static void test_hbitmap_reset_all(TestHBitmapData *data,
387 hbitmap_test_init(data, L3 * 2, 0);
388 hbitmap_test_set(data, L1 - 1, L1 + 2);
389 hbitmap_test_reset_all(data);
390 hbitmap_test_set(data, 0, L1 * 3);
391 hbitmap_test_reset_all(data);
392 hbitmap_test_set(data, L2, L1);
393 hbitmap_test_reset_all(data);
394 hbitmap_test_set(data, L2, L3 - L2 + 1);
395 hbitmap_test_reset_all(data);
396 hbitmap_test_set(data, L3 - 1, 3);
397 hbitmap_test_reset_all(data);
398 hbitmap_test_set(data, 0, L3 * 2);
399 hbitmap_test_reset_all(data);
400 hbitmap_test_set(data, L3 / 2, L3);
401 hbitmap_test_reset_all(data);
404 static void test_hbitmap_granularity(TestHBitmapData *data,
407 /* Note that hbitmap_test_check has to be invoked manually in this test. */
408 hbitmap_test_init(data, L1, 1);
409 hbitmap_test_set(data, 0, 1);
410 g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
411 hbitmap_test_check(data, 0);
412 hbitmap_test_set(data, 2, 1);
413 g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
414 hbitmap_test_check(data, 0);
415 hbitmap_test_set(data, 0, 3);
416 g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
417 hbitmap_test_reset(data, 0, 1);
418 g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
421 static void test_hbitmap_iter_granularity(TestHBitmapData *data,
426 /* Note that hbitmap_test_check has to be invoked manually in this test. */
427 hbitmap_test_init(data, 131072 << 7, 7);
428 hbitmap_iter_init(&hbi, data->hb, 0);
429 g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
431 hbitmap_test_set(data, ((L2 + L1 + 1) << 7) + 8, 8);
432 hbitmap_iter_init(&hbi, data->hb, 0);
433 g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
434 g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
436 hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
437 g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
439 hbitmap_test_set(data, (131072 << 7) - 8, 8);
440 hbitmap_iter_init(&hbi, data->hb, 0);
441 g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
442 g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
443 g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
445 hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
446 g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
447 g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
450 static void hbitmap_test_set_boundary_bits(TestHBitmapData *data, ssize_t diff)
452 size_t size = data->size;
455 hbitmap_test_set(data, 0, 1);
457 /* Last bit in new, shortened map */
458 hbitmap_test_set(data, size + diff - 1, 1);
460 /* First bit to be truncated away */
461 hbitmap_test_set(data, size + diff, 1);
464 hbitmap_test_set(data, size - 1, 1);
465 if (data->granularity == 0) {
466 hbitmap_test_check_get(data);
470 static void hbitmap_test_check_boundary_bits(TestHBitmapData *data)
472 size_t size = MIN(data->size, data->old_size);
474 if (data->granularity == 0) {
475 hbitmap_test_check_get(data);
476 hbitmap_test_check(data, 0);
478 /* If a granularity was set, note that every distinct
479 * (bit >> granularity) value that was set will increase
480 * the bit pop count by 2^granularity, not just 1.
482 * The hbitmap_test_check facility does not currently tolerate
483 * non-zero granularities, so test the boundaries and the population
486 g_assert(hbitmap_get(data->hb, 0));
487 g_assert(hbitmap_get(data->hb, size - 1));
488 g_assert_cmpint(2 << data->granularity, ==, hbitmap_count(data->hb));
492 /* Generic truncate test. */
493 static void hbitmap_test_truncate(TestHBitmapData *data,
498 hbitmap_test_init(data, size, granularity);
499 hbitmap_test_set_boundary_bits(data, diff);
500 hbitmap_test_truncate_impl(data, size + diff);
501 hbitmap_test_check_boundary_bits(data);
504 static void test_hbitmap_truncate_nop(TestHBitmapData *data,
507 hbitmap_test_truncate(data, L2, 0, 0);
511 * Grow by an amount smaller than the granularity, without crossing
512 * a granularity alignment boundary. Effectively a NOP.
514 static void test_hbitmap_truncate_grow_negligible(TestHBitmapData *data,
517 size_t size = L2 - 1;
521 hbitmap_test_truncate(data, size, diff, granularity);
525 * Shrink by an amount smaller than the granularity, without crossing
526 * a granularity alignment boundary. Effectively a NOP.
528 static void test_hbitmap_truncate_shrink_negligible(TestHBitmapData *data,
535 hbitmap_test_truncate(data, size, diff, granularity);
539 * Grow by an amount smaller than the granularity, but crossing over
540 * a granularity alignment boundary.
542 static void test_hbitmap_truncate_grow_tiny(TestHBitmapData *data,
545 size_t size = L2 - 2;
549 hbitmap_test_truncate(data, size, diff, granularity);
553 * Shrink by an amount smaller than the granularity, but crossing over
554 * a granularity alignment boundary.
556 static void test_hbitmap_truncate_shrink_tiny(TestHBitmapData *data,
559 size_t size = L2 - 1;
563 hbitmap_test_truncate(data, size, diff, granularity);
567 * Grow by an amount smaller than sizeof(long), and not crossing over
568 * a sizeof(long) alignment boundary.
570 static void test_hbitmap_truncate_grow_small(TestHBitmapData *data,
573 size_t size = L2 + 1;
574 size_t diff = sizeof(long) / 2;
576 hbitmap_test_truncate(data, size, diff, 0);
580 * Shrink by an amount smaller than sizeof(long), and not crossing over
581 * a sizeof(long) alignment boundary.
583 static void test_hbitmap_truncate_shrink_small(TestHBitmapData *data,
587 size_t diff = sizeof(long) / 2;
589 hbitmap_test_truncate(data, size, -diff, 0);
593 * Grow by an amount smaller than sizeof(long), while crossing over
594 * a sizeof(long) alignment boundary.
596 static void test_hbitmap_truncate_grow_medium(TestHBitmapData *data,
599 size_t size = L2 - 1;
600 size_t diff = sizeof(long) / 2;
602 hbitmap_test_truncate(data, size, diff, 0);
606 * Shrink by an amount smaller than sizeof(long), while crossing over
607 * a sizeof(long) alignment boundary.
609 static void test_hbitmap_truncate_shrink_medium(TestHBitmapData *data,
612 size_t size = L2 + 1;
613 size_t diff = sizeof(long) / 2;
615 hbitmap_test_truncate(data, size, -diff, 0);
619 * Grow by an amount larger than sizeof(long).
621 static void test_hbitmap_truncate_grow_large(TestHBitmapData *data,
625 size_t diff = 8 * sizeof(long);
627 hbitmap_test_truncate(data, size, diff, 0);
631 * Shrink by an amount larger than sizeof(long).
633 static void test_hbitmap_truncate_shrink_large(TestHBitmapData *data,
637 size_t diff = 8 * sizeof(long);
639 hbitmap_test_truncate(data, size, -diff, 0);
642 static void hbitmap_test_add(const char *testpath,
643 void (*test_func)(TestHBitmapData *data, const void *user_data))
645 g_test_add(testpath, TestHBitmapData, NULL, NULL, test_func,
646 hbitmap_test_teardown);
649 int main(int argc, char **argv)
651 g_test_init(&argc, &argv, NULL);
652 hbitmap_test_add("/hbitmap/size/0", test_hbitmap_zero);
653 hbitmap_test_add("/hbitmap/size/unaligned", test_hbitmap_unaligned);
654 hbitmap_test_add("/hbitmap/iter/empty", test_hbitmap_iter_empty);
655 hbitmap_test_add("/hbitmap/iter/partial", test_hbitmap_iter_partial);
656 hbitmap_test_add("/hbitmap/iter/granularity", test_hbitmap_iter_granularity);
657 hbitmap_test_add("/hbitmap/get/all", test_hbitmap_get_all);
658 hbitmap_test_add("/hbitmap/get/some", test_hbitmap_get_some);
659 hbitmap_test_add("/hbitmap/set/all", test_hbitmap_set_all);
660 hbitmap_test_add("/hbitmap/set/one", test_hbitmap_set_one);
661 hbitmap_test_add("/hbitmap/set/two-elem", test_hbitmap_set_two_elem);
662 hbitmap_test_add("/hbitmap/set/general", test_hbitmap_set);
663 hbitmap_test_add("/hbitmap/set/twice", test_hbitmap_set_twice);
664 hbitmap_test_add("/hbitmap/set/overlap", test_hbitmap_set_overlap);
665 hbitmap_test_add("/hbitmap/reset/empty", test_hbitmap_reset_empty);
666 hbitmap_test_add("/hbitmap/reset/general", test_hbitmap_reset);
667 hbitmap_test_add("/hbitmap/reset/all", test_hbitmap_reset_all);
668 hbitmap_test_add("/hbitmap/granularity", test_hbitmap_granularity);
670 hbitmap_test_add("/hbitmap/truncate/nop", test_hbitmap_truncate_nop);
671 hbitmap_test_add("/hbitmap/truncate/grow/negligible",
672 test_hbitmap_truncate_grow_negligible);
673 hbitmap_test_add("/hbitmap/truncate/shrink/negligible",
674 test_hbitmap_truncate_shrink_negligible);
675 hbitmap_test_add("/hbitmap/truncate/grow/tiny",
676 test_hbitmap_truncate_grow_tiny);
677 hbitmap_test_add("/hbitmap/truncate/shrink/tiny",
678 test_hbitmap_truncate_shrink_tiny);
679 hbitmap_test_add("/hbitmap/truncate/grow/small",
680 test_hbitmap_truncate_grow_small);
681 hbitmap_test_add("/hbitmap/truncate/shrink/small",
682 test_hbitmap_truncate_shrink_small);
683 hbitmap_test_add("/hbitmap/truncate/grow/medium",
684 test_hbitmap_truncate_grow_medium);
685 hbitmap_test_add("/hbitmap/truncate/shrink/medium",
686 test_hbitmap_truncate_shrink_medium);
687 hbitmap_test_add("/hbitmap/truncate/grow/large",
688 test_hbitmap_truncate_grow_large);
689 hbitmap_test_add("/hbitmap/truncate/shrink/large",
690 test_hbitmap_truncate_shrink_large);