vt82c686: Set user_creatable=false for VT82C686B_PM
[qemu/ar7.git] / tests / test-hbitmap.c
blobb6726cf76b793826d8684c7a74d9608b7c67d3cf
1 /*
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.
12 #include "qemu/osdep.h"
13 #include "qemu/hbitmap.h"
14 #include "qemu/bitmap.h"
15 #include "block/block.h"
17 #define LOG_BITS_PER_LONG (BITS_PER_LONG == 32 ? 5 : 6)
19 #define L1 BITS_PER_LONG
20 #define L2 (BITS_PER_LONG * L1)
21 #define L3 (BITS_PER_LONG * L2)
23 typedef struct TestHBitmapData {
24 HBitmap *hb;
25 unsigned long *bits;
26 size_t size;
27 size_t old_size;
28 int granularity;
29 } TestHBitmapData;
32 /* Check that the HBitmap and the shadow bitmap contain the same data,
33 * ignoring the same "first" bits.
35 static void hbitmap_test_check(TestHBitmapData *data,
36 uint64_t first)
38 uint64_t count = 0;
39 size_t pos;
40 int bit;
41 HBitmapIter hbi;
42 int64_t i, next;
44 hbitmap_iter_init(&hbi, data->hb, first);
46 i = first;
47 for (;;) {
48 next = hbitmap_iter_next(&hbi);
49 if (next < 0) {
50 next = data->size;
53 while (i < next) {
54 pos = i >> LOG_BITS_PER_LONG;
55 bit = i & (BITS_PER_LONG - 1);
56 i++;
57 g_assert_cmpint(data->bits[pos] & (1UL << bit), ==, 0);
60 if (next == data->size) {
61 break;
64 pos = i >> LOG_BITS_PER_LONG;
65 bit = i & (BITS_PER_LONG - 1);
66 i++;
67 count++;
68 g_assert_cmpint(data->bits[pos] & (1UL << bit), !=, 0);
71 if (first == 0) {
72 g_assert_cmpint(count << data->granularity, ==, hbitmap_count(data->hb));
76 /* This is provided instead of a test setup function so that the sizes
77 are kept in the test functions (and not in main()) */
78 static void hbitmap_test_init(TestHBitmapData *data,
79 uint64_t size, int granularity)
81 size_t n;
82 data->hb = hbitmap_alloc(size, granularity);
84 n = DIV_ROUND_UP(size, BITS_PER_LONG);
85 if (n == 0) {
86 n = 1;
88 data->bits = g_new0(unsigned long, n);
89 data->size = size;
90 data->granularity = granularity;
91 if (size) {
92 hbitmap_test_check(data, 0);
96 static inline size_t hbitmap_test_array_size(size_t bits)
98 size_t n = DIV_ROUND_UP(bits, BITS_PER_LONG);
99 return n ? n : 1;
102 static void hbitmap_test_truncate_impl(TestHBitmapData *data,
103 size_t size)
105 size_t n;
106 size_t m;
107 data->old_size = data->size;
108 data->size = size;
110 if (data->size == data->old_size) {
111 return;
114 n = hbitmap_test_array_size(size);
115 m = hbitmap_test_array_size(data->old_size);
116 data->bits = g_realloc(data->bits, sizeof(unsigned long) * n);
117 if (n > m) {
118 memset(&data->bits[m], 0x00, sizeof(unsigned long) * (n - m));
121 /* If we shrink to an uneven multiple of sizeof(unsigned long),
122 * scrub the leftover memory. */
123 if (data->size < data->old_size) {
124 m = size % (sizeof(unsigned long) * 8);
125 if (m) {
126 unsigned long mask = (1ULL << m) - 1;
127 data->bits[n-1] &= mask;
131 hbitmap_truncate(data->hb, size);
134 static void hbitmap_test_teardown(TestHBitmapData *data,
135 const void *unused)
137 if (data->hb) {
138 hbitmap_free(data->hb);
139 data->hb = NULL;
141 g_free(data->bits);
142 data->bits = NULL;
145 /* Set a range in the HBitmap and in the shadow "simple" bitmap.
146 * The two bitmaps are then tested against each other.
148 static void hbitmap_test_set(TestHBitmapData *data,
149 uint64_t first, uint64_t count)
151 hbitmap_set(data->hb, first, count);
152 while (count-- != 0) {
153 size_t pos = first >> LOG_BITS_PER_LONG;
154 int bit = first & (BITS_PER_LONG - 1);
155 first++;
157 data->bits[pos] |= 1UL << bit;
160 if (data->granularity == 0) {
161 hbitmap_test_check(data, 0);
165 /* Reset a range in the HBitmap and in the shadow "simple" bitmap.
167 static void hbitmap_test_reset(TestHBitmapData *data,
168 uint64_t first, uint64_t count)
170 hbitmap_reset(data->hb, first, count);
171 while (count-- != 0) {
172 size_t pos = first >> LOG_BITS_PER_LONG;
173 int bit = first & (BITS_PER_LONG - 1);
174 first++;
176 data->bits[pos] &= ~(1UL << bit);
179 if (data->granularity == 0) {
180 hbitmap_test_check(data, 0);
184 static void hbitmap_test_reset_all(TestHBitmapData *data)
186 size_t n;
188 hbitmap_reset_all(data->hb);
190 n = DIV_ROUND_UP(data->size, BITS_PER_LONG);
191 if (n == 0) {
192 n = 1;
194 memset(data->bits, 0, n * sizeof(unsigned long));
196 if (data->granularity == 0) {
197 hbitmap_test_check(data, 0);
201 static void hbitmap_test_check_get(TestHBitmapData *data)
203 uint64_t count = 0;
204 uint64_t i;
206 for (i = 0; i < data->size; i++) {
207 size_t pos = i >> LOG_BITS_PER_LONG;
208 int bit = i & (BITS_PER_LONG - 1);
209 unsigned long val = data->bits[pos] & (1UL << bit);
210 count += hbitmap_get(data->hb, i);
211 g_assert_cmpint(hbitmap_get(data->hb, i), ==, val != 0);
213 g_assert_cmpint(count, ==, hbitmap_count(data->hb));
216 static void test_hbitmap_zero(TestHBitmapData *data,
217 const void *unused)
219 hbitmap_test_init(data, 0, 0);
222 static void test_hbitmap_unaligned(TestHBitmapData *data,
223 const void *unused)
225 hbitmap_test_init(data, L3 + 23, 0);
226 hbitmap_test_set(data, 0, 1);
227 hbitmap_test_set(data, L3 + 22, 1);
230 static void test_hbitmap_iter_empty(TestHBitmapData *data,
231 const void *unused)
233 hbitmap_test_init(data, L1, 0);
236 static void test_hbitmap_iter_partial(TestHBitmapData *data,
237 const void *unused)
239 hbitmap_test_init(data, L3, 0);
240 hbitmap_test_set(data, 0, L3);
241 hbitmap_test_check(data, 1);
242 hbitmap_test_check(data, L1 - 1);
243 hbitmap_test_check(data, L1);
244 hbitmap_test_check(data, L1 * 2 - 1);
245 hbitmap_test_check(data, L2 - 1);
246 hbitmap_test_check(data, L2);
247 hbitmap_test_check(data, L2 + 1);
248 hbitmap_test_check(data, L2 + L1);
249 hbitmap_test_check(data, L2 + L1 * 2 - 1);
250 hbitmap_test_check(data, L2 * 2 - 1);
251 hbitmap_test_check(data, L2 * 2);
252 hbitmap_test_check(data, L2 * 2 + 1);
253 hbitmap_test_check(data, L2 * 2 + L1);
254 hbitmap_test_check(data, L2 * 2 + L1 * 2 - 1);
255 hbitmap_test_check(data, L3 / 2);
258 static void test_hbitmap_set_all(TestHBitmapData *data,
259 const void *unused)
261 hbitmap_test_init(data, L3, 0);
262 hbitmap_test_set(data, 0, L3);
265 static void test_hbitmap_get_all(TestHBitmapData *data,
266 const void *unused)
268 hbitmap_test_init(data, L3, 0);
269 hbitmap_test_set(data, 0, L3);
270 hbitmap_test_check_get(data);
273 static void test_hbitmap_get_some(TestHBitmapData *data,
274 const void *unused)
276 hbitmap_test_init(data, 2 * L2, 0);
277 hbitmap_test_set(data, 10, 1);
278 hbitmap_test_check_get(data);
279 hbitmap_test_set(data, L1 - 1, 1);
280 hbitmap_test_check_get(data);
281 hbitmap_test_set(data, L1, 1);
282 hbitmap_test_check_get(data);
283 hbitmap_test_set(data, L2 - 1, 1);
284 hbitmap_test_check_get(data);
285 hbitmap_test_set(data, L2, 1);
286 hbitmap_test_check_get(data);
289 static void test_hbitmap_set_one(TestHBitmapData *data,
290 const void *unused)
292 hbitmap_test_init(data, 2 * L2, 0);
293 hbitmap_test_set(data, 10, 1);
294 hbitmap_test_set(data, L1 - 1, 1);
295 hbitmap_test_set(data, L1, 1);
296 hbitmap_test_set(data, L2 - 1, 1);
297 hbitmap_test_set(data, L2, 1);
300 static void test_hbitmap_set_two_elem(TestHBitmapData *data,
301 const void *unused)
303 hbitmap_test_init(data, 2 * L2, 0);
304 hbitmap_test_set(data, L1 - 1, 2);
305 hbitmap_test_set(data, L1 * 2 - 1, 4);
306 hbitmap_test_set(data, L1 * 4, L1 + 1);
307 hbitmap_test_set(data, L1 * 8 - 1, L1 + 1);
308 hbitmap_test_set(data, L2 - 1, 2);
309 hbitmap_test_set(data, L2 + L1 - 1, 8);
310 hbitmap_test_set(data, L2 + L1 * 4, L1 + 1);
311 hbitmap_test_set(data, L2 + L1 * 8 - 1, L1 + 1);
314 static void test_hbitmap_set(TestHBitmapData *data,
315 const void *unused)
317 hbitmap_test_init(data, L3 * 2, 0);
318 hbitmap_test_set(data, L1 - 1, L1 + 2);
319 hbitmap_test_set(data, L1 * 3 - 1, L1 + 2);
320 hbitmap_test_set(data, L1 * 5, L1 * 2 + 1);
321 hbitmap_test_set(data, L1 * 8 - 1, L1 * 2 + 1);
322 hbitmap_test_set(data, L2 - 1, L1 + 2);
323 hbitmap_test_set(data, L2 + L1 * 2 - 1, L1 + 2);
324 hbitmap_test_set(data, L2 + L1 * 4, L1 * 2 + 1);
325 hbitmap_test_set(data, L2 + L1 * 7 - 1, L1 * 2 + 1);
326 hbitmap_test_set(data, L2 * 2 - 1, L3 * 2 - L2 * 2);
329 static void test_hbitmap_set_twice(TestHBitmapData *data,
330 const void *unused)
332 hbitmap_test_init(data, L1 * 3, 0);
333 hbitmap_test_set(data, 0, L1 * 3);
334 hbitmap_test_set(data, L1, 1);
337 static void test_hbitmap_set_overlap(TestHBitmapData *data,
338 const void *unused)
340 hbitmap_test_init(data, L3 * 2, 0);
341 hbitmap_test_set(data, L1 - 1, L1 + 2);
342 hbitmap_test_set(data, L1 * 2 - 1, L1 * 2 + 2);
343 hbitmap_test_set(data, 0, L1 * 3);
344 hbitmap_test_set(data, L1 * 8 - 1, L2);
345 hbitmap_test_set(data, L2, L1);
346 hbitmap_test_set(data, L2 - L1 - 1, L1 * 8 + 2);
347 hbitmap_test_set(data, L2, L3 - L2 + 1);
348 hbitmap_test_set(data, L3 - L1, L1 * 3);
349 hbitmap_test_set(data, L3 - 1, 3);
350 hbitmap_test_set(data, L3 - 1, L2);
353 static void test_hbitmap_reset_empty(TestHBitmapData *data,
354 const void *unused)
356 hbitmap_test_init(data, L3, 0);
357 hbitmap_test_reset(data, 0, L3);
360 static void test_hbitmap_reset(TestHBitmapData *data,
361 const void *unused)
363 hbitmap_test_init(data, L3 * 2, 0);
364 hbitmap_test_set(data, L1 - 1, L1 + 2);
365 hbitmap_test_reset(data, L1 * 2 - 1, L1 * 2 + 2);
366 hbitmap_test_set(data, 0, L1 * 3);
367 hbitmap_test_reset(data, L1 * 8 - 1, L2);
368 hbitmap_test_set(data, L2, L1);
369 hbitmap_test_reset(data, L2 - L1 - 1, L1 * 8 + 2);
370 hbitmap_test_set(data, L2, L3 - L2 + 1);
371 hbitmap_test_reset(data, L3 - L1, L1 * 3);
372 hbitmap_test_set(data, L3 - 1, 3);
373 hbitmap_test_reset(data, L3 - 1, L2);
374 hbitmap_test_set(data, 0, L3 * 2);
375 hbitmap_test_reset(data, 0, L1);
376 hbitmap_test_reset(data, 0, L2);
377 hbitmap_test_reset(data, L3, L3);
378 hbitmap_test_set(data, L3 / 2, L3);
381 static void test_hbitmap_reset_all(TestHBitmapData *data,
382 const void *unused)
384 hbitmap_test_init(data, L3 * 2, 0);
385 hbitmap_test_set(data, L1 - 1, L1 + 2);
386 hbitmap_test_reset_all(data);
387 hbitmap_test_set(data, 0, L1 * 3);
388 hbitmap_test_reset_all(data);
389 hbitmap_test_set(data, L2, L1);
390 hbitmap_test_reset_all(data);
391 hbitmap_test_set(data, L2, L3 - L2 + 1);
392 hbitmap_test_reset_all(data);
393 hbitmap_test_set(data, L3 - 1, 3);
394 hbitmap_test_reset_all(data);
395 hbitmap_test_set(data, 0, L3 * 2);
396 hbitmap_test_reset_all(data);
397 hbitmap_test_set(data, L3 / 2, L3);
398 hbitmap_test_reset_all(data);
401 static void test_hbitmap_granularity(TestHBitmapData *data,
402 const void *unused)
404 /* Note that hbitmap_test_check has to be invoked manually in this test. */
405 hbitmap_test_init(data, L1, 1);
406 hbitmap_test_set(data, 0, 1);
407 g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
408 hbitmap_test_check(data, 0);
409 hbitmap_test_set(data, 2, 1);
410 g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
411 hbitmap_test_check(data, 0);
412 hbitmap_test_set(data, 0, 3);
413 g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
414 hbitmap_test_reset(data, 0, 2);
415 g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
418 static void test_hbitmap_iter_granularity(TestHBitmapData *data,
419 const void *unused)
421 HBitmapIter hbi;
423 /* Note that hbitmap_test_check has to be invoked manually in this test. */
424 hbitmap_test_init(data, 131072 << 7, 7);
425 hbitmap_iter_init(&hbi, data->hb, 0);
426 g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
428 hbitmap_test_set(data, ((L2 + L1 + 1) << 7) + 8, 8);
429 hbitmap_iter_init(&hbi, data->hb, 0);
430 g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
431 g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
433 hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
434 g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
436 hbitmap_test_set(data, (131072 << 7) - 8, 8);
437 hbitmap_iter_init(&hbi, data->hb, 0);
438 g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
439 g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
440 g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
442 hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
443 g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
444 g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
447 static void hbitmap_test_set_boundary_bits(TestHBitmapData *data, ssize_t diff)
449 size_t size = data->size;
451 /* First bit */
452 hbitmap_test_set(data, 0, 1);
453 if (diff < 0) {
454 /* Last bit in new, shortened map */
455 hbitmap_test_set(data, size + diff - 1, 1);
457 /* First bit to be truncated away */
458 hbitmap_test_set(data, size + diff, 1);
460 /* Last bit */
461 hbitmap_test_set(data, size - 1, 1);
462 if (data->granularity == 0) {
463 hbitmap_test_check_get(data);
467 static void hbitmap_test_check_boundary_bits(TestHBitmapData *data)
469 size_t size = MIN(data->size, data->old_size);
471 if (data->granularity == 0) {
472 hbitmap_test_check_get(data);
473 hbitmap_test_check(data, 0);
474 } else {
475 /* If a granularity was set, note that every distinct
476 * (bit >> granularity) value that was set will increase
477 * the bit pop count by 2^granularity, not just 1.
479 * The hbitmap_test_check facility does not currently tolerate
480 * non-zero granularities, so test the boundaries and the population
481 * count manually.
483 g_assert(hbitmap_get(data->hb, 0));
484 g_assert(hbitmap_get(data->hb, size - 1));
485 g_assert_cmpint(2 << data->granularity, ==, hbitmap_count(data->hb));
489 /* Generic truncate test. */
490 static void hbitmap_test_truncate(TestHBitmapData *data,
491 size_t size,
492 ssize_t diff,
493 int granularity)
495 hbitmap_test_init(data, size, granularity);
496 hbitmap_test_set_boundary_bits(data, diff);
497 hbitmap_test_truncate_impl(data, size + diff);
498 hbitmap_test_check_boundary_bits(data);
501 static void test_hbitmap_truncate_nop(TestHBitmapData *data,
502 const void *unused)
504 hbitmap_test_truncate(data, L2, 0, 0);
508 * Grow by an amount smaller than the granularity, without crossing
509 * a granularity alignment boundary. Effectively a NOP.
511 static void test_hbitmap_truncate_grow_negligible(TestHBitmapData *data,
512 const void *unused)
514 size_t size = L2 - 1;
515 size_t diff = 1;
516 int granularity = 1;
518 hbitmap_test_truncate(data, size, diff, granularity);
522 * Shrink by an amount smaller than the granularity, without crossing
523 * a granularity alignment boundary. Effectively a NOP.
525 static void test_hbitmap_truncate_shrink_negligible(TestHBitmapData *data,
526 const void *unused)
528 size_t size = L2;
529 ssize_t diff = -1;
530 int granularity = 1;
532 hbitmap_test_truncate(data, size, diff, granularity);
536 * Grow by an amount smaller than the granularity, but crossing over
537 * a granularity alignment boundary.
539 static void test_hbitmap_truncate_grow_tiny(TestHBitmapData *data,
540 const void *unused)
542 size_t size = L2 - 2;
543 ssize_t diff = 1;
544 int granularity = 1;
546 hbitmap_test_truncate(data, size, diff, granularity);
550 * Shrink by an amount smaller than the granularity, but crossing over
551 * a granularity alignment boundary.
553 static void test_hbitmap_truncate_shrink_tiny(TestHBitmapData *data,
554 const void *unused)
556 size_t size = L2 - 1;
557 ssize_t diff = -1;
558 int granularity = 1;
560 hbitmap_test_truncate(data, size, diff, granularity);
564 * Grow by an amount smaller than sizeof(long), and not crossing over
565 * a sizeof(long) alignment boundary.
567 static void test_hbitmap_truncate_grow_small(TestHBitmapData *data,
568 const void *unused)
570 size_t size = L2 + 1;
571 size_t diff = sizeof(long) / 2;
573 hbitmap_test_truncate(data, size, diff, 0);
577 * Shrink by an amount smaller than sizeof(long), and not crossing over
578 * a sizeof(long) alignment boundary.
580 static void test_hbitmap_truncate_shrink_small(TestHBitmapData *data,
581 const void *unused)
583 size_t size = L2;
584 size_t diff = sizeof(long) / 2;
586 hbitmap_test_truncate(data, size, -diff, 0);
590 * Grow by an amount smaller than sizeof(long), while crossing over
591 * a sizeof(long) alignment boundary.
593 static void test_hbitmap_truncate_grow_medium(TestHBitmapData *data,
594 const void *unused)
596 size_t size = L2 - 1;
597 size_t diff = sizeof(long) / 2;
599 hbitmap_test_truncate(data, size, diff, 0);
603 * Shrink by an amount smaller than sizeof(long), while crossing over
604 * a sizeof(long) alignment boundary.
606 static void test_hbitmap_truncate_shrink_medium(TestHBitmapData *data,
607 const void *unused)
609 size_t size = L2 + 1;
610 size_t diff = sizeof(long) / 2;
612 hbitmap_test_truncate(data, size, -diff, 0);
616 * Grow by an amount larger than sizeof(long).
618 static void test_hbitmap_truncate_grow_large(TestHBitmapData *data,
619 const void *unused)
621 size_t size = L2;
622 size_t diff = 8 * sizeof(long);
624 hbitmap_test_truncate(data, size, diff, 0);
628 * Shrink by an amount larger than sizeof(long).
630 static void test_hbitmap_truncate_shrink_large(TestHBitmapData *data,
631 const void *unused)
633 size_t size = L2;
634 size_t diff = 8 * sizeof(long);
636 hbitmap_test_truncate(data, size, -diff, 0);
639 static void test_hbitmap_serialize_align(TestHBitmapData *data,
640 const void *unused)
642 int r;
644 hbitmap_test_init(data, L3 * 2, 3);
645 g_assert(hbitmap_is_serializable(data->hb));
647 r = hbitmap_serialization_align(data->hb);
648 g_assert_cmpint(r, ==, 64 << 3);
651 static void hbitmap_test_serialize_range(TestHBitmapData *data,
652 uint8_t *buf, size_t buf_size,
653 uint64_t pos, uint64_t count)
655 size_t i;
656 unsigned long *el = (unsigned long *)buf;
658 assert(hbitmap_granularity(data->hb) == 0);
659 hbitmap_reset_all(data->hb);
660 memset(buf, 0, buf_size);
661 if (count) {
662 hbitmap_set(data->hb, pos, count);
665 g_assert(hbitmap_is_serializable(data->hb));
666 hbitmap_serialize_part(data->hb, buf, 0, data->size);
668 /* Serialized buffer is inherently LE, convert it back manually to test */
669 for (i = 0; i < buf_size / sizeof(unsigned long); i++) {
670 el[i] = (BITS_PER_LONG == 32 ? le32_to_cpu(el[i]) : le64_to_cpu(el[i]));
673 for (i = 0; i < data->size; i++) {
674 int is_set = test_bit(i, (unsigned long *)buf);
675 if (i >= pos && i < pos + count) {
676 g_assert(is_set);
677 } else {
678 g_assert(!is_set);
682 /* Re-serialize for deserialization testing */
683 memset(buf, 0, buf_size);
684 hbitmap_serialize_part(data->hb, buf, 0, data->size);
685 hbitmap_reset_all(data->hb);
687 g_assert(hbitmap_is_serializable(data->hb));
688 hbitmap_deserialize_part(data->hb, buf, 0, data->size, true);
690 for (i = 0; i < data->size; i++) {
691 int is_set = hbitmap_get(data->hb, i);
692 if (i >= pos && i < pos + count) {
693 g_assert(is_set);
694 } else {
695 g_assert(!is_set);
700 static void test_hbitmap_serialize_basic(TestHBitmapData *data,
701 const void *unused)
703 int i, j;
704 size_t buf_size;
705 uint8_t *buf;
706 uint64_t positions[] = { 0, 1, L1 - 1, L1, L2 - 1, L2, L2 + 1, L3 - 1 };
707 int num_positions = ARRAY_SIZE(positions);
709 hbitmap_test_init(data, L3, 0);
710 g_assert(hbitmap_is_serializable(data->hb));
711 buf_size = hbitmap_serialization_size(data->hb, 0, data->size);
712 buf = g_malloc0(buf_size);
714 for (i = 0; i < num_positions; i++) {
715 for (j = 0; j < num_positions; j++) {
716 hbitmap_test_serialize_range(data, buf, buf_size,
717 positions[i],
718 MIN(positions[j], L3 - positions[i]));
722 g_free(buf);
725 static void test_hbitmap_serialize_part(TestHBitmapData *data,
726 const void *unused)
728 int i, j, k;
729 size_t buf_size;
730 uint8_t *buf;
731 uint64_t positions[] = { 0, 1, L1 - 1, L1, L2 - 1, L2, L2 + 1, L3 - 1 };
732 int num_positions = ARRAY_SIZE(positions);
734 hbitmap_test_init(data, L3, 0);
735 buf_size = L2;
736 buf = g_malloc0(buf_size);
738 for (i = 0; i < num_positions; i++) {
739 hbitmap_set(data->hb, positions[i], 1);
742 g_assert(hbitmap_is_serializable(data->hb));
744 for (i = 0; i < data->size; i += buf_size) {
745 unsigned long *el = (unsigned long *)buf;
746 hbitmap_serialize_part(data->hb, buf, i, buf_size);
747 for (j = 0; j < buf_size / sizeof(unsigned long); j++) {
748 el[j] = (BITS_PER_LONG == 32 ? le32_to_cpu(el[j]) : le64_to_cpu(el[j]));
751 for (j = 0; j < buf_size; j++) {
752 bool should_set = false;
753 for (k = 0; k < num_positions; k++) {
754 if (positions[k] == j + i) {
755 should_set = true;
756 break;
759 g_assert_cmpint(should_set, ==, test_bit(j, (unsigned long *)buf));
763 g_free(buf);
766 static void test_hbitmap_serialize_zeroes(TestHBitmapData *data,
767 const void *unused)
769 int i;
770 HBitmapIter iter;
771 int64_t next;
772 uint64_t min_l1 = MAX(L1, 64);
773 uint64_t positions[] = { 0, min_l1, L2, L3 - min_l1};
774 int num_positions = ARRAY_SIZE(positions);
776 hbitmap_test_init(data, L3, 0);
778 for (i = 0; i < num_positions; i++) {
779 hbitmap_set(data->hb, positions[i], L1);
782 g_assert(hbitmap_is_serializable(data->hb));
784 for (i = 0; i < num_positions; i++) {
785 hbitmap_deserialize_zeroes(data->hb, positions[i], min_l1, true);
786 hbitmap_iter_init(&iter, data->hb, 0);
787 next = hbitmap_iter_next(&iter);
788 if (i == num_positions - 1) {
789 g_assert_cmpint(next, ==, -1);
790 } else {
791 g_assert_cmpint(next, ==, positions[i + 1]);
796 static void hbitmap_test_add(const char *testpath,
797 void (*test_func)(TestHBitmapData *data, const void *user_data))
799 g_test_add(testpath, TestHBitmapData, NULL, NULL, test_func,
800 hbitmap_test_teardown);
803 static void test_hbitmap_iter_and_reset(TestHBitmapData *data,
804 const void *unused)
806 HBitmapIter hbi;
808 hbitmap_test_init(data, L1 * 2, 0);
809 hbitmap_set(data->hb, 0, data->size);
811 hbitmap_iter_init(&hbi, data->hb, BITS_PER_LONG - 1);
813 hbitmap_iter_next(&hbi);
815 hbitmap_reset_all(data->hb);
816 hbitmap_iter_next(&hbi);
819 static void test_hbitmap_next_x_check_range(TestHBitmapData *data,
820 int64_t start,
821 int64_t count)
823 int64_t next_zero = hbitmap_next_zero(data->hb, start, count);
824 int64_t next_dirty = hbitmap_next_dirty(data->hb, start, count);
825 int64_t next;
826 int64_t end = start >= data->size || data->size - start < count ?
827 data->size : start + count;
828 bool first_bit = hbitmap_get(data->hb, start);
830 for (next = start;
831 next < end && hbitmap_get(data->hb, next) == first_bit;
832 next++)
837 if (next == end) {
838 next = -1;
841 g_assert_cmpint(next_dirty, ==, first_bit ? start : next);
842 g_assert_cmpint(next_zero, ==, first_bit ? next : start);
845 static void test_hbitmap_next_x_check(TestHBitmapData *data, int64_t start)
847 test_hbitmap_next_x_check_range(data, start, INT64_MAX);
850 static void test_hbitmap_next_x_do(TestHBitmapData *data, int granularity)
852 hbitmap_test_init(data, L3, granularity);
853 test_hbitmap_next_x_check(data, 0);
854 test_hbitmap_next_x_check(data, L3 - 1);
855 test_hbitmap_next_x_check_range(data, 0, 1);
856 test_hbitmap_next_x_check_range(data, L3 - 1, 1);
858 hbitmap_set(data->hb, L2, 1);
859 test_hbitmap_next_x_check(data, 0);
860 test_hbitmap_next_x_check(data, L2 - 1);
861 test_hbitmap_next_x_check(data, L2);
862 test_hbitmap_next_x_check(data, L2 + 1);
863 test_hbitmap_next_x_check_range(data, 0, 1);
864 test_hbitmap_next_x_check_range(data, 0, L2);
865 test_hbitmap_next_x_check_range(data, L2 - 1, 1);
866 test_hbitmap_next_x_check_range(data, L2 - 1, 2);
867 test_hbitmap_next_x_check_range(data, L2, 1);
868 test_hbitmap_next_x_check_range(data, L2 + 1, 1);
870 hbitmap_set(data->hb, L2 + 5, L1);
871 test_hbitmap_next_x_check(data, 0);
872 test_hbitmap_next_x_check(data, L2 - L1);
873 test_hbitmap_next_x_check(data, L2 + 1);
874 test_hbitmap_next_x_check(data, L2 + 2);
875 test_hbitmap_next_x_check(data, L2 + 5);
876 test_hbitmap_next_x_check(data, L2 + L1 - 1);
877 test_hbitmap_next_x_check(data, L2 + L1);
878 test_hbitmap_next_x_check(data, L2 + L1 + 1);
879 test_hbitmap_next_x_check_range(data, L2 - 2, L1);
880 test_hbitmap_next_x_check_range(data, L2, 4);
881 test_hbitmap_next_x_check_range(data, L2, 6);
882 test_hbitmap_next_x_check_range(data, L2 + 1, 3);
883 test_hbitmap_next_x_check_range(data, L2 + 4, L1);
884 test_hbitmap_next_x_check_range(data, L2 + 5, L1);
885 test_hbitmap_next_x_check_range(data, L2 + 5 + L1 - 1, 1);
886 test_hbitmap_next_x_check_range(data, L2 + 5 + L1, 1);
887 test_hbitmap_next_x_check_range(data, L2 + 5 + L1 + 1, 1);
889 hbitmap_set(data->hb, L2 * 2, L3 - L2 * 2);
890 test_hbitmap_next_x_check(data, L2 * 2 - L1);
891 test_hbitmap_next_x_check(data, L2 * 2 - 2);
892 test_hbitmap_next_x_check(data, L2 * 2 - 1);
893 test_hbitmap_next_x_check(data, L2 * 2);
894 test_hbitmap_next_x_check(data, L2 * 2 + 1);
895 test_hbitmap_next_x_check(data, L2 * 2 + L1);
896 test_hbitmap_next_x_check(data, L3 - 1);
897 test_hbitmap_next_x_check_range(data, L2 * 2 - L1, L1 + 1);
898 test_hbitmap_next_x_check_range(data, L2 * 2, L2);
900 hbitmap_set(data->hb, 0, L3);
901 test_hbitmap_next_x_check(data, 0);
904 static void test_hbitmap_next_x_0(TestHBitmapData *data, const void *unused)
906 test_hbitmap_next_x_do(data, 0);
909 static void test_hbitmap_next_x_4(TestHBitmapData *data, const void *unused)
911 test_hbitmap_next_x_do(data, 4);
914 static void test_hbitmap_next_x_after_truncate(TestHBitmapData *data,
915 const void *unused)
917 hbitmap_test_init(data, L1, 0);
918 hbitmap_test_truncate_impl(data, L1 * 2);
919 hbitmap_set(data->hb, 0, L1);
920 test_hbitmap_next_x_check(data, 0);
923 static void test_hbitmap_next_dirty_area_check_limited(TestHBitmapData *data,
924 int64_t offset,
925 int64_t count,
926 int64_t max_dirty)
928 int64_t off1, off2;
929 int64_t len1 = 0, len2;
930 bool ret1, ret2;
931 int64_t end;
933 ret1 = hbitmap_next_dirty_area(data->hb,
934 offset, count == INT64_MAX ? INT64_MAX : offset + count, max_dirty,
935 &off1, &len1);
937 end = offset > data->size || data->size - offset < count ? data->size :
938 offset + count;
940 for (off2 = offset; off2 < end && !hbitmap_get(data->hb, off2); off2++) {
944 for (len2 = 1; (off2 + len2 < end && len2 < max_dirty &&
945 hbitmap_get(data->hb, off2 + len2)); len2++)
950 ret2 = off2 < end;
951 g_assert_cmpint(ret1, ==, ret2);
953 if (ret2) {
954 g_assert_cmpint(off1, ==, off2);
955 g_assert_cmpint(len1, ==, len2);
959 static void test_hbitmap_next_dirty_area_check(TestHBitmapData *data,
960 int64_t offset, int64_t count)
962 test_hbitmap_next_dirty_area_check_limited(data, offset, count, INT64_MAX);
965 static void test_hbitmap_next_dirty_area_do(TestHBitmapData *data,
966 int granularity)
968 hbitmap_test_init(data, L3, granularity);
969 test_hbitmap_next_dirty_area_check(data, 0, INT64_MAX);
970 test_hbitmap_next_dirty_area_check(data, 0, 1);
971 test_hbitmap_next_dirty_area_check(data, L3 - 1, 1);
972 test_hbitmap_next_dirty_area_check_limited(data, 0, INT64_MAX, 1);
974 hbitmap_set(data->hb, L2, 1);
975 test_hbitmap_next_dirty_area_check(data, 0, 1);
976 test_hbitmap_next_dirty_area_check(data, 0, L2);
977 test_hbitmap_next_dirty_area_check(data, 0, INT64_MAX);
978 test_hbitmap_next_dirty_area_check(data, L2 - 1, INT64_MAX);
979 test_hbitmap_next_dirty_area_check(data, L2 - 1, 1);
980 test_hbitmap_next_dirty_area_check(data, L2 - 1, 2);
981 test_hbitmap_next_dirty_area_check(data, L2 - 1, 3);
982 test_hbitmap_next_dirty_area_check(data, L2, INT64_MAX);
983 test_hbitmap_next_dirty_area_check(data, L2, 1);
984 test_hbitmap_next_dirty_area_check(data, L2 + 1, 1);
985 test_hbitmap_next_dirty_area_check_limited(data, 0, INT64_MAX, 1);
986 test_hbitmap_next_dirty_area_check_limited(data, L2 - 1, 2, 1);
988 hbitmap_set(data->hb, L2 + 5, L1);
989 test_hbitmap_next_dirty_area_check(data, 0, INT64_MAX);
990 test_hbitmap_next_dirty_area_check(data, L2 - 2, 8);
991 test_hbitmap_next_dirty_area_check(data, L2 + 1, 5);
992 test_hbitmap_next_dirty_area_check(data, L2 + 1, 3);
993 test_hbitmap_next_dirty_area_check(data, L2 + 4, L1);
994 test_hbitmap_next_dirty_area_check(data, L2 + 5, L1);
995 test_hbitmap_next_dirty_area_check(data, L2 + 7, L1);
996 test_hbitmap_next_dirty_area_check(data, L2 + L1, L1);
997 test_hbitmap_next_dirty_area_check(data, L2, 0);
998 test_hbitmap_next_dirty_area_check(data, L2 + 1, 0);
999 test_hbitmap_next_dirty_area_check_limited(data, L2 + 3, INT64_MAX, 3);
1000 test_hbitmap_next_dirty_area_check_limited(data, L2 + 3, 7, 10);
1002 hbitmap_set(data->hb, L2 * 2, L3 - L2 * 2);
1003 test_hbitmap_next_dirty_area_check(data, 0, INT64_MAX);
1004 test_hbitmap_next_dirty_area_check(data, L2, INT64_MAX);
1005 test_hbitmap_next_dirty_area_check(data, L2 + 1, INT64_MAX);
1006 test_hbitmap_next_dirty_area_check(data, L2 + 5 + L1 - 1, INT64_MAX);
1007 test_hbitmap_next_dirty_area_check(data, L2 + 5 + L1, 5);
1008 test_hbitmap_next_dirty_area_check(data, L2 * 2 - L1, L1 + 1);
1009 test_hbitmap_next_dirty_area_check(data, L2 * 2, L2);
1010 test_hbitmap_next_dirty_area_check_limited(data, L2 * 2 + 1, INT64_MAX, 5);
1011 test_hbitmap_next_dirty_area_check_limited(data, L2 * 2 + 1, 10, 5);
1012 test_hbitmap_next_dirty_area_check_limited(data, L2 * 2 + 1, 2, 5);
1014 hbitmap_set(data->hb, 0, L3);
1015 test_hbitmap_next_dirty_area_check(data, 0, INT64_MAX);
1018 static void test_hbitmap_next_dirty_area_0(TestHBitmapData *data,
1019 const void *unused)
1021 test_hbitmap_next_dirty_area_do(data, 0);
1024 static void test_hbitmap_next_dirty_area_1(TestHBitmapData *data,
1025 const void *unused)
1027 test_hbitmap_next_dirty_area_do(data, 1);
1030 static void test_hbitmap_next_dirty_area_4(TestHBitmapData *data,
1031 const void *unused)
1033 test_hbitmap_next_dirty_area_do(data, 4);
1036 static void test_hbitmap_next_dirty_area_after_truncate(TestHBitmapData *data,
1037 const void *unused)
1039 hbitmap_test_init(data, L1, 0);
1040 hbitmap_test_truncate_impl(data, L1 * 2);
1041 hbitmap_set(data->hb, L1 + 1, 1);
1042 test_hbitmap_next_dirty_area_check(data, 0, INT64_MAX);
1045 int main(int argc, char **argv)
1047 g_test_init(&argc, &argv, NULL);
1048 hbitmap_test_add("/hbitmap/size/0", test_hbitmap_zero);
1049 hbitmap_test_add("/hbitmap/size/unaligned", test_hbitmap_unaligned);
1050 hbitmap_test_add("/hbitmap/iter/empty", test_hbitmap_iter_empty);
1051 hbitmap_test_add("/hbitmap/iter/partial", test_hbitmap_iter_partial);
1052 hbitmap_test_add("/hbitmap/iter/granularity", test_hbitmap_iter_granularity);
1053 hbitmap_test_add("/hbitmap/get/all", test_hbitmap_get_all);
1054 hbitmap_test_add("/hbitmap/get/some", test_hbitmap_get_some);
1055 hbitmap_test_add("/hbitmap/set/all", test_hbitmap_set_all);
1056 hbitmap_test_add("/hbitmap/set/one", test_hbitmap_set_one);
1057 hbitmap_test_add("/hbitmap/set/two-elem", test_hbitmap_set_two_elem);
1058 hbitmap_test_add("/hbitmap/set/general", test_hbitmap_set);
1059 hbitmap_test_add("/hbitmap/set/twice", test_hbitmap_set_twice);
1060 hbitmap_test_add("/hbitmap/set/overlap", test_hbitmap_set_overlap);
1061 hbitmap_test_add("/hbitmap/reset/empty", test_hbitmap_reset_empty);
1062 hbitmap_test_add("/hbitmap/reset/general", test_hbitmap_reset);
1063 hbitmap_test_add("/hbitmap/reset/all", test_hbitmap_reset_all);
1064 hbitmap_test_add("/hbitmap/granularity", test_hbitmap_granularity);
1066 hbitmap_test_add("/hbitmap/truncate/nop", test_hbitmap_truncate_nop);
1067 hbitmap_test_add("/hbitmap/truncate/grow/negligible",
1068 test_hbitmap_truncate_grow_negligible);
1069 hbitmap_test_add("/hbitmap/truncate/shrink/negligible",
1070 test_hbitmap_truncate_shrink_negligible);
1071 hbitmap_test_add("/hbitmap/truncate/grow/tiny",
1072 test_hbitmap_truncate_grow_tiny);
1073 hbitmap_test_add("/hbitmap/truncate/shrink/tiny",
1074 test_hbitmap_truncate_shrink_tiny);
1075 hbitmap_test_add("/hbitmap/truncate/grow/small",
1076 test_hbitmap_truncate_grow_small);
1077 hbitmap_test_add("/hbitmap/truncate/shrink/small",
1078 test_hbitmap_truncate_shrink_small);
1079 hbitmap_test_add("/hbitmap/truncate/grow/medium",
1080 test_hbitmap_truncate_grow_medium);
1081 hbitmap_test_add("/hbitmap/truncate/shrink/medium",
1082 test_hbitmap_truncate_shrink_medium);
1083 hbitmap_test_add("/hbitmap/truncate/grow/large",
1084 test_hbitmap_truncate_grow_large);
1085 hbitmap_test_add("/hbitmap/truncate/shrink/large",
1086 test_hbitmap_truncate_shrink_large);
1088 hbitmap_test_add("/hbitmap/serialize/align",
1089 test_hbitmap_serialize_align);
1090 hbitmap_test_add("/hbitmap/serialize/basic",
1091 test_hbitmap_serialize_basic);
1092 hbitmap_test_add("/hbitmap/serialize/part",
1093 test_hbitmap_serialize_part);
1094 hbitmap_test_add("/hbitmap/serialize/zeroes",
1095 test_hbitmap_serialize_zeroes);
1097 hbitmap_test_add("/hbitmap/iter/iter_and_reset",
1098 test_hbitmap_iter_and_reset);
1100 hbitmap_test_add("/hbitmap/next_zero/next_x_0",
1101 test_hbitmap_next_x_0);
1102 hbitmap_test_add("/hbitmap/next_zero/next_x_4",
1103 test_hbitmap_next_x_4);
1104 hbitmap_test_add("/hbitmap/next_zero/next_x_after_truncate",
1105 test_hbitmap_next_x_after_truncate);
1107 hbitmap_test_add("/hbitmap/next_dirty_area/next_dirty_area_0",
1108 test_hbitmap_next_dirty_area_0);
1109 hbitmap_test_add("/hbitmap/next_dirty_area/next_dirty_area_1",
1110 test_hbitmap_next_dirty_area_1);
1111 hbitmap_test_add("/hbitmap/next_dirty_area/next_dirty_area_4",
1112 test_hbitmap_next_dirty_area_4);
1113 hbitmap_test_add("/hbitmap/next_dirty_area/next_dirty_area_after_truncate",
1114 test_hbitmap_next_dirty_area_after_truncate);
1116 g_test_run();
1118 return 0;