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
{
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
,
44 hbitmap_iter_init(&hbi
, data
->hb
, first
);
48 next
= hbitmap_iter_next(&hbi
);
54 pos
= i
>> LOG_BITS_PER_LONG
;
55 bit
= i
& (BITS_PER_LONG
- 1);
57 g_assert_cmpint(data
->bits
[pos
] & (1UL << bit
), ==, 0);
60 if (next
== data
->size
) {
64 pos
= i
>> LOG_BITS_PER_LONG
;
65 bit
= i
& (BITS_PER_LONG
- 1);
68 g_assert_cmpint(data
->bits
[pos
] & (1UL << bit
), !=, 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
)
82 data
->hb
= hbitmap_alloc(size
, granularity
);
84 n
= DIV_ROUND_UP(size
, BITS_PER_LONG
);
88 data
->bits
= g_new0(unsigned long, n
);
90 data
->granularity
= granularity
;
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
);
102 static void hbitmap_test_truncate_impl(TestHBitmapData
*data
,
107 data
->old_size
= data
->size
;
110 if (data
->size
== data
->old_size
) {
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
);
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);
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
,
138 hbitmap_free(data
->hb
);
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);
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);
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
)
188 hbitmap_reset_all(data
->hb
);
190 n
= DIV_ROUND_UP(data
->size
, BITS_PER_LONG
);
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
)
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
,
219 hbitmap_test_init(data
, 0, 0);
222 static void test_hbitmap_unaligned(TestHBitmapData
*data
,
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
,
233 hbitmap_test_init(data
, L1
, 0);
236 static void test_hbitmap_iter_partial(TestHBitmapData
*data
,
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
,
261 hbitmap_test_init(data
, L3
, 0);
262 hbitmap_test_set(data
, 0, L3
);
265 static void test_hbitmap_get_all(TestHBitmapData
*data
,
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
,
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
,
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
,
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
,
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
,
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
,
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
,
356 hbitmap_test_init(data
, L3
, 0);
357 hbitmap_test_reset(data
, 0, L3
);
360 static void test_hbitmap_reset(TestHBitmapData
*data
,
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
,
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
,
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
,
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
;
452 hbitmap_test_set(data
, 0, 1);
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);
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);
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
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
,
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
,
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
,
514 size_t size
= L2
- 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
,
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
,
542 size_t size
= L2
- 2;
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
,
556 size_t size
= L2
- 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
,
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
,
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
,
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
,
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
,
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
,
634 size_t diff
= 8 * sizeof(long);
636 hbitmap_test_truncate(data
, size
, -diff
, 0);
639 static void test_hbitmap_serialize_align(TestHBitmapData
*data
,
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
)
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
);
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
) {
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
) {
700 static void test_hbitmap_serialize_basic(TestHBitmapData
*data
,
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
,
718 MIN(positions
[j
], L3
- positions
[i
]));
725 static void test_hbitmap_serialize_part(TestHBitmapData
*data
,
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);
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
) {
759 g_assert_cmpint(should_set
, ==, test_bit(j
, (unsigned long *)buf
));
766 static void test_hbitmap_serialize_zeroes(TestHBitmapData
*data
,
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);
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
,
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
,
823 int64_t next_zero
= hbitmap_next_zero(data
->hb
, start
, count
);
824 int64_t next_dirty
= hbitmap_next_dirty(data
->hb
, start
, count
);
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
);
831 next
< end
&& hbitmap_get(data
->hb
, next
) == first_bit
;
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
,
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
,
929 int64_t len1
= 0, len2
;
933 ret1
= hbitmap_next_dirty_area(data
->hb
,
934 offset
, count
== INT64_MAX
? INT64_MAX
: offset
+ count
, max_dirty
,
937 end
= offset
> data
->size
|| data
->size
- offset
< count
? data
->size
:
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
++)
951 g_assert_cmpint(ret1
, ==, 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
,
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
,
1021 test_hbitmap_next_dirty_area_do(data
, 0);
1024 static void test_hbitmap_next_dirty_area_1(TestHBitmapData
*data
,
1027 test_hbitmap_next_dirty_area_do(data
, 1);
1030 static void test_hbitmap_next_dirty_area_4(TestHBitmapData
*data
,
1033 test_hbitmap_next_dirty_area_do(data
, 4);
1036 static void test_hbitmap_next_dirty_area_after_truncate(TestHBitmapData
*data
,
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
);