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
{
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
= DIV_ROUND_UP(size
, BITS_PER_LONG
);
89 data
->bits
= g_new0(unsigned long, n
);
91 data
->granularity
= granularity
;
93 hbitmap_test_check(data
, 0);
97 static void hbitmap_test_init_meta(TestHBitmapData
*data
,
98 uint64_t size
, int granularity
,
101 hbitmap_test_init(data
, size
, granularity
);
102 data
->meta
= hbitmap_create_meta(data
->hb
, meta_chunk
);
105 static inline size_t hbitmap_test_array_size(size_t bits
)
107 size_t n
= DIV_ROUND_UP(bits
, BITS_PER_LONG
);
111 static void hbitmap_test_truncate_impl(TestHBitmapData
*data
,
116 data
->old_size
= data
->size
;
119 if (data
->size
== data
->old_size
) {
123 n
= hbitmap_test_array_size(size
);
124 m
= hbitmap_test_array_size(data
->old_size
);
125 data
->bits
= g_realloc(data
->bits
, sizeof(unsigned long) * n
);
127 memset(&data
->bits
[m
], 0x00, sizeof(unsigned long) * (n
- m
));
130 /* If we shrink to an uneven multiple of sizeof(unsigned long),
131 * scrub the leftover memory. */
132 if (data
->size
< data
->old_size
) {
133 m
= size
% (sizeof(unsigned long) * 8);
135 unsigned long mask
= (1ULL << m
) - 1;
136 data
->bits
[n
-1] &= mask
;
140 hbitmap_truncate(data
->hb
, size
);
143 static void hbitmap_test_teardown(TestHBitmapData
*data
,
148 hbitmap_free_meta(data
->hb
);
150 hbitmap_free(data
->hb
);
157 /* Set a range in the HBitmap and in the shadow "simple" bitmap.
158 * The two bitmaps are then tested against each other.
160 static void hbitmap_test_set(TestHBitmapData
*data
,
161 uint64_t first
, uint64_t count
)
163 hbitmap_set(data
->hb
, first
, count
);
164 while (count
-- != 0) {
165 size_t pos
= first
>> LOG_BITS_PER_LONG
;
166 int bit
= first
& (BITS_PER_LONG
- 1);
169 data
->bits
[pos
] |= 1UL << bit
;
172 if (data
->granularity
== 0) {
173 hbitmap_test_check(data
, 0);
177 /* Reset a range in the HBitmap and in the shadow "simple" bitmap.
179 static void hbitmap_test_reset(TestHBitmapData
*data
,
180 uint64_t first
, uint64_t count
)
182 hbitmap_reset(data
->hb
, first
, count
);
183 while (count
-- != 0) {
184 size_t pos
= first
>> LOG_BITS_PER_LONG
;
185 int bit
= first
& (BITS_PER_LONG
- 1);
188 data
->bits
[pos
] &= ~(1UL << bit
);
191 if (data
->granularity
== 0) {
192 hbitmap_test_check(data
, 0);
196 static void hbitmap_test_reset_all(TestHBitmapData
*data
)
200 hbitmap_reset_all(data
->hb
);
202 n
= DIV_ROUND_UP(data
->size
, BITS_PER_LONG
);
206 memset(data
->bits
, 0, n
* sizeof(unsigned long));
208 if (data
->granularity
== 0) {
209 hbitmap_test_check(data
, 0);
213 static void hbitmap_test_check_get(TestHBitmapData
*data
)
218 for (i
= 0; i
< data
->size
; i
++) {
219 size_t pos
= i
>> LOG_BITS_PER_LONG
;
220 int bit
= i
& (BITS_PER_LONG
- 1);
221 unsigned long val
= data
->bits
[pos
] & (1UL << bit
);
222 count
+= hbitmap_get(data
->hb
, i
);
223 g_assert_cmpint(hbitmap_get(data
->hb
, i
), ==, val
!= 0);
225 g_assert_cmpint(count
, ==, hbitmap_count(data
->hb
));
228 static void test_hbitmap_zero(TestHBitmapData
*data
,
231 hbitmap_test_init(data
, 0, 0);
234 static void test_hbitmap_unaligned(TestHBitmapData
*data
,
237 hbitmap_test_init(data
, L3
+ 23, 0);
238 hbitmap_test_set(data
, 0, 1);
239 hbitmap_test_set(data
, L3
+ 22, 1);
242 static void test_hbitmap_iter_empty(TestHBitmapData
*data
,
245 hbitmap_test_init(data
, L1
, 0);
248 static void test_hbitmap_iter_partial(TestHBitmapData
*data
,
251 hbitmap_test_init(data
, L3
, 0);
252 hbitmap_test_set(data
, 0, L3
);
253 hbitmap_test_check(data
, 1);
254 hbitmap_test_check(data
, L1
- 1);
255 hbitmap_test_check(data
, L1
);
256 hbitmap_test_check(data
, L1
* 2 - 1);
257 hbitmap_test_check(data
, L2
- 1);
258 hbitmap_test_check(data
, L2
);
259 hbitmap_test_check(data
, L2
+ 1);
260 hbitmap_test_check(data
, L2
+ L1
);
261 hbitmap_test_check(data
, L2
+ L1
* 2 - 1);
262 hbitmap_test_check(data
, L2
* 2 - 1);
263 hbitmap_test_check(data
, L2
* 2);
264 hbitmap_test_check(data
, L2
* 2 + 1);
265 hbitmap_test_check(data
, L2
* 2 + L1
);
266 hbitmap_test_check(data
, L2
* 2 + L1
* 2 - 1);
267 hbitmap_test_check(data
, L3
/ 2);
270 static void test_hbitmap_set_all(TestHBitmapData
*data
,
273 hbitmap_test_init(data
, L3
, 0);
274 hbitmap_test_set(data
, 0, L3
);
277 static void test_hbitmap_get_all(TestHBitmapData
*data
,
280 hbitmap_test_init(data
, L3
, 0);
281 hbitmap_test_set(data
, 0, L3
);
282 hbitmap_test_check_get(data
);
285 static void test_hbitmap_get_some(TestHBitmapData
*data
,
288 hbitmap_test_init(data
, 2 * L2
, 0);
289 hbitmap_test_set(data
, 10, 1);
290 hbitmap_test_check_get(data
);
291 hbitmap_test_set(data
, L1
- 1, 1);
292 hbitmap_test_check_get(data
);
293 hbitmap_test_set(data
, L1
, 1);
294 hbitmap_test_check_get(data
);
295 hbitmap_test_set(data
, L2
- 1, 1);
296 hbitmap_test_check_get(data
);
297 hbitmap_test_set(data
, L2
, 1);
298 hbitmap_test_check_get(data
);
301 static void test_hbitmap_set_one(TestHBitmapData
*data
,
304 hbitmap_test_init(data
, 2 * L2
, 0);
305 hbitmap_test_set(data
, 10, 1);
306 hbitmap_test_set(data
, L1
- 1, 1);
307 hbitmap_test_set(data
, L1
, 1);
308 hbitmap_test_set(data
, L2
- 1, 1);
309 hbitmap_test_set(data
, L2
, 1);
312 static void test_hbitmap_set_two_elem(TestHBitmapData
*data
,
315 hbitmap_test_init(data
, 2 * L2
, 0);
316 hbitmap_test_set(data
, L1
- 1, 2);
317 hbitmap_test_set(data
, L1
* 2 - 1, 4);
318 hbitmap_test_set(data
, L1
* 4, L1
+ 1);
319 hbitmap_test_set(data
, L1
* 8 - 1, L1
+ 1);
320 hbitmap_test_set(data
, L2
- 1, 2);
321 hbitmap_test_set(data
, L2
+ L1
- 1, 8);
322 hbitmap_test_set(data
, L2
+ L1
* 4, L1
+ 1);
323 hbitmap_test_set(data
, L2
+ L1
* 8 - 1, L1
+ 1);
326 static void test_hbitmap_set(TestHBitmapData
*data
,
329 hbitmap_test_init(data
, L3
* 2, 0);
330 hbitmap_test_set(data
, L1
- 1, L1
+ 2);
331 hbitmap_test_set(data
, L1
* 3 - 1, L1
+ 2);
332 hbitmap_test_set(data
, L1
* 5, L1
* 2 + 1);
333 hbitmap_test_set(data
, L1
* 8 - 1, L1
* 2 + 1);
334 hbitmap_test_set(data
, L2
- 1, L1
+ 2);
335 hbitmap_test_set(data
, L2
+ L1
* 2 - 1, L1
+ 2);
336 hbitmap_test_set(data
, L2
+ L1
* 4, L1
* 2 + 1);
337 hbitmap_test_set(data
, L2
+ L1
* 7 - 1, L1
* 2 + 1);
338 hbitmap_test_set(data
, L2
* 2 - 1, L3
* 2 - L2
* 2);
341 static void test_hbitmap_set_twice(TestHBitmapData
*data
,
344 hbitmap_test_init(data
, L1
* 3, 0);
345 hbitmap_test_set(data
, 0, L1
* 3);
346 hbitmap_test_set(data
, L1
, 1);
349 static void test_hbitmap_set_overlap(TestHBitmapData
*data
,
352 hbitmap_test_init(data
, L3
* 2, 0);
353 hbitmap_test_set(data
, L1
- 1, L1
+ 2);
354 hbitmap_test_set(data
, L1
* 2 - 1, L1
* 2 + 2);
355 hbitmap_test_set(data
, 0, L1
* 3);
356 hbitmap_test_set(data
, L1
* 8 - 1, L2
);
357 hbitmap_test_set(data
, L2
, L1
);
358 hbitmap_test_set(data
, L2
- L1
- 1, L1
* 8 + 2);
359 hbitmap_test_set(data
, L2
, L3
- L2
+ 1);
360 hbitmap_test_set(data
, L3
- L1
, L1
* 3);
361 hbitmap_test_set(data
, L3
- 1, 3);
362 hbitmap_test_set(data
, L3
- 1, L2
);
365 static void test_hbitmap_reset_empty(TestHBitmapData
*data
,
368 hbitmap_test_init(data
, L3
, 0);
369 hbitmap_test_reset(data
, 0, L3
);
372 static void test_hbitmap_reset(TestHBitmapData
*data
,
375 hbitmap_test_init(data
, L3
* 2, 0);
376 hbitmap_test_set(data
, L1
- 1, L1
+ 2);
377 hbitmap_test_reset(data
, L1
* 2 - 1, L1
* 2 + 2);
378 hbitmap_test_set(data
, 0, L1
* 3);
379 hbitmap_test_reset(data
, L1
* 8 - 1, L2
);
380 hbitmap_test_set(data
, L2
, L1
);
381 hbitmap_test_reset(data
, L2
- L1
- 1, L1
* 8 + 2);
382 hbitmap_test_set(data
, L2
, L3
- L2
+ 1);
383 hbitmap_test_reset(data
, L3
- L1
, L1
* 3);
384 hbitmap_test_set(data
, L3
- 1, 3);
385 hbitmap_test_reset(data
, L3
- 1, L2
);
386 hbitmap_test_set(data
, 0, L3
* 2);
387 hbitmap_test_reset(data
, 0, L1
);
388 hbitmap_test_reset(data
, 0, L2
);
389 hbitmap_test_reset(data
, L3
, L3
);
390 hbitmap_test_set(data
, L3
/ 2, L3
);
393 static void test_hbitmap_reset_all(TestHBitmapData
*data
,
396 hbitmap_test_init(data
, L3
* 2, 0);
397 hbitmap_test_set(data
, L1
- 1, L1
+ 2);
398 hbitmap_test_reset_all(data
);
399 hbitmap_test_set(data
, 0, L1
* 3);
400 hbitmap_test_reset_all(data
);
401 hbitmap_test_set(data
, L2
, L1
);
402 hbitmap_test_reset_all(data
);
403 hbitmap_test_set(data
, L2
, L3
- L2
+ 1);
404 hbitmap_test_reset_all(data
);
405 hbitmap_test_set(data
, L3
- 1, 3);
406 hbitmap_test_reset_all(data
);
407 hbitmap_test_set(data
, 0, L3
* 2);
408 hbitmap_test_reset_all(data
);
409 hbitmap_test_set(data
, L3
/ 2, L3
);
410 hbitmap_test_reset_all(data
);
413 static void test_hbitmap_granularity(TestHBitmapData
*data
,
416 /* Note that hbitmap_test_check has to be invoked manually in this test. */
417 hbitmap_test_init(data
, L1
, 1);
418 hbitmap_test_set(data
, 0, 1);
419 g_assert_cmpint(hbitmap_count(data
->hb
), ==, 2);
420 hbitmap_test_check(data
, 0);
421 hbitmap_test_set(data
, 2, 1);
422 g_assert_cmpint(hbitmap_count(data
->hb
), ==, 4);
423 hbitmap_test_check(data
, 0);
424 hbitmap_test_set(data
, 0, 3);
425 g_assert_cmpint(hbitmap_count(data
->hb
), ==, 4);
426 hbitmap_test_reset(data
, 0, 1);
427 g_assert_cmpint(hbitmap_count(data
->hb
), ==, 2);
430 static void test_hbitmap_iter_granularity(TestHBitmapData
*data
,
435 /* Note that hbitmap_test_check has to be invoked manually in this test. */
436 hbitmap_test_init(data
, 131072 << 7, 7);
437 hbitmap_iter_init(&hbi
, data
->hb
, 0);
438 g_assert_cmpint(hbitmap_iter_next(&hbi
), <, 0);
440 hbitmap_test_set(data
, ((L2
+ L1
+ 1) << 7) + 8, 8);
441 hbitmap_iter_init(&hbi
, data
->hb
, 0);
442 g_assert_cmpint(hbitmap_iter_next(&hbi
), ==, (L2
+ L1
+ 1) << 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
), <, 0);
448 hbitmap_test_set(data
, (131072 << 7) - 8, 8);
449 hbitmap_iter_init(&hbi
, data
->hb
, 0);
450 g_assert_cmpint(hbitmap_iter_next(&hbi
), ==, (L2
+ L1
+ 1) << 7);
451 g_assert_cmpint(hbitmap_iter_next(&hbi
), ==, 131071 << 7);
452 g_assert_cmpint(hbitmap_iter_next(&hbi
), <, 0);
454 hbitmap_iter_init(&hbi
, data
->hb
, (L2
+ L1
+ 2) << 7);
455 g_assert_cmpint(hbitmap_iter_next(&hbi
), ==, 131071 << 7);
456 g_assert_cmpint(hbitmap_iter_next(&hbi
), <, 0);
459 static void hbitmap_test_set_boundary_bits(TestHBitmapData
*data
, ssize_t diff
)
461 size_t size
= data
->size
;
464 hbitmap_test_set(data
, 0, 1);
466 /* Last bit in new, shortened map */
467 hbitmap_test_set(data
, size
+ diff
- 1, 1);
469 /* First bit to be truncated away */
470 hbitmap_test_set(data
, size
+ diff
, 1);
473 hbitmap_test_set(data
, size
- 1, 1);
474 if (data
->granularity
== 0) {
475 hbitmap_test_check_get(data
);
479 static void hbitmap_test_check_boundary_bits(TestHBitmapData
*data
)
481 size_t size
= MIN(data
->size
, data
->old_size
);
483 if (data
->granularity
== 0) {
484 hbitmap_test_check_get(data
);
485 hbitmap_test_check(data
, 0);
487 /* If a granularity was set, note that every distinct
488 * (bit >> granularity) value that was set will increase
489 * the bit pop count by 2^granularity, not just 1.
491 * The hbitmap_test_check facility does not currently tolerate
492 * non-zero granularities, so test the boundaries and the population
495 g_assert(hbitmap_get(data
->hb
, 0));
496 g_assert(hbitmap_get(data
->hb
, size
- 1));
497 g_assert_cmpint(2 << data
->granularity
, ==, hbitmap_count(data
->hb
));
501 /* Generic truncate test. */
502 static void hbitmap_test_truncate(TestHBitmapData
*data
,
507 hbitmap_test_init(data
, size
, granularity
);
508 hbitmap_test_set_boundary_bits(data
, diff
);
509 hbitmap_test_truncate_impl(data
, size
+ diff
);
510 hbitmap_test_check_boundary_bits(data
);
513 static void test_hbitmap_truncate_nop(TestHBitmapData
*data
,
516 hbitmap_test_truncate(data
, L2
, 0, 0);
520 * Grow by an amount smaller than the granularity, without crossing
521 * a granularity alignment boundary. Effectively a NOP.
523 static void test_hbitmap_truncate_grow_negligible(TestHBitmapData
*data
,
526 size_t size
= L2
- 1;
530 hbitmap_test_truncate(data
, size
, diff
, granularity
);
534 * Shrink by an amount smaller than the granularity, without crossing
535 * a granularity alignment boundary. Effectively a NOP.
537 static void test_hbitmap_truncate_shrink_negligible(TestHBitmapData
*data
,
544 hbitmap_test_truncate(data
, size
, diff
, granularity
);
548 * Grow by an amount smaller than the granularity, but crossing over
549 * a granularity alignment boundary.
551 static void test_hbitmap_truncate_grow_tiny(TestHBitmapData
*data
,
554 size_t size
= L2
- 2;
558 hbitmap_test_truncate(data
, size
, diff
, granularity
);
562 * Shrink by an amount smaller than the granularity, but crossing over
563 * a granularity alignment boundary.
565 static void test_hbitmap_truncate_shrink_tiny(TestHBitmapData
*data
,
568 size_t size
= L2
- 1;
572 hbitmap_test_truncate(data
, size
, diff
, granularity
);
576 * Grow by an amount smaller than sizeof(long), and not crossing over
577 * a sizeof(long) alignment boundary.
579 static void test_hbitmap_truncate_grow_small(TestHBitmapData
*data
,
582 size_t size
= L2
+ 1;
583 size_t diff
= sizeof(long) / 2;
585 hbitmap_test_truncate(data
, size
, diff
, 0);
589 * Shrink by an amount smaller than sizeof(long), and not crossing over
590 * a sizeof(long) alignment boundary.
592 static void test_hbitmap_truncate_shrink_small(TestHBitmapData
*data
,
596 size_t diff
= sizeof(long) / 2;
598 hbitmap_test_truncate(data
, size
, -diff
, 0);
602 * Grow by an amount smaller than sizeof(long), while crossing over
603 * a sizeof(long) alignment boundary.
605 static void test_hbitmap_truncate_grow_medium(TestHBitmapData
*data
,
608 size_t size
= L2
- 1;
609 size_t diff
= sizeof(long) / 2;
611 hbitmap_test_truncate(data
, size
, diff
, 0);
615 * Shrink by an amount smaller than sizeof(long), while crossing over
616 * a sizeof(long) alignment boundary.
618 static void test_hbitmap_truncate_shrink_medium(TestHBitmapData
*data
,
621 size_t size
= L2
+ 1;
622 size_t diff
= sizeof(long) / 2;
624 hbitmap_test_truncate(data
, size
, -diff
, 0);
628 * Grow by an amount larger than sizeof(long).
630 static void test_hbitmap_truncate_grow_large(TestHBitmapData
*data
,
634 size_t diff
= 8 * sizeof(long);
636 hbitmap_test_truncate(data
, size
, diff
, 0);
640 * Shrink by an amount larger than sizeof(long).
642 static void test_hbitmap_truncate_shrink_large(TestHBitmapData
*data
,
646 size_t diff
= 8 * sizeof(long);
648 hbitmap_test_truncate(data
, size
, -diff
, 0);
651 static void hbitmap_check_meta(TestHBitmapData
*data
,
652 int64_t start
, int count
)
656 for (i
= 0; i
< data
->size
; i
++) {
657 if (i
>= start
&& i
< start
+ count
) {
658 g_assert(hbitmap_get(data
->meta
, i
));
660 g_assert(!hbitmap_get(data
->meta
, i
));
665 static void hbitmap_test_meta(TestHBitmapData
*data
,
666 int64_t start
, int count
,
667 int64_t check_start
, int check_count
)
669 hbitmap_reset_all(data
->hb
);
670 hbitmap_reset_all(data
->meta
);
672 /* Test "unset" -> "unset" will not update meta. */
673 hbitmap_reset(data
->hb
, start
, count
);
674 hbitmap_check_meta(data
, 0, 0);
676 /* Test "unset" -> "set" will update meta */
677 hbitmap_set(data
->hb
, start
, count
);
678 hbitmap_check_meta(data
, check_start
, check_count
);
680 /* Test "set" -> "set" will not update meta */
681 hbitmap_reset_all(data
->meta
);
682 hbitmap_set(data
->hb
, start
, count
);
683 hbitmap_check_meta(data
, 0, 0);
685 /* Test "set" -> "unset" will update meta */
686 hbitmap_reset_all(data
->meta
);
687 hbitmap_reset(data
->hb
, start
, count
);
688 hbitmap_check_meta(data
, check_start
, check_count
);
691 static void hbitmap_test_meta_do(TestHBitmapData
*data
, int chunk_size
)
693 uint64_t size
= chunk_size
* 100;
694 hbitmap_test_init_meta(data
, size
, 0, chunk_size
);
696 hbitmap_test_meta(data
, 0, 1, 0, chunk_size
);
697 hbitmap_test_meta(data
, 0, chunk_size
, 0, chunk_size
);
698 hbitmap_test_meta(data
, chunk_size
- 1, 1, 0, chunk_size
);
699 hbitmap_test_meta(data
, chunk_size
- 1, 2, 0, chunk_size
* 2);
700 hbitmap_test_meta(data
, chunk_size
- 1, chunk_size
+ 1, 0, chunk_size
* 2);
701 hbitmap_test_meta(data
, chunk_size
- 1, chunk_size
+ 2, 0, chunk_size
* 3);
702 hbitmap_test_meta(data
, 7 * chunk_size
- 1, chunk_size
+ 2,
703 6 * chunk_size
, chunk_size
* 3);
704 hbitmap_test_meta(data
, size
- 1, 1, size
- chunk_size
, chunk_size
);
705 hbitmap_test_meta(data
, 0, size
, 0, size
);
708 static void test_hbitmap_meta_byte(TestHBitmapData
*data
, const void *unused
)
710 hbitmap_test_meta_do(data
, BITS_PER_BYTE
);
713 static void test_hbitmap_meta_word(TestHBitmapData
*data
, const void *unused
)
715 hbitmap_test_meta_do(data
, BITS_PER_LONG
);
718 static void test_hbitmap_meta_sector(TestHBitmapData
*data
, const void *unused
)
720 hbitmap_test_meta_do(data
, BDRV_SECTOR_SIZE
* BITS_PER_BYTE
);
724 * Create an HBitmap and test set/unset.
726 static void test_hbitmap_meta_one(TestHBitmapData
*data
, const void *unused
)
729 int64_t offsets
[] = {
730 0, 1, L1
- 1, L1
, L1
+ 1, L2
- 1, L2
, L2
+ 1, L3
- 1, L3
, L3
+ 1
733 hbitmap_test_init_meta(data
, L3
* 2, 0, 1);
734 for (i
= 0; i
< ARRAY_SIZE(offsets
); i
++) {
735 hbitmap_test_meta(data
, offsets
[i
], 1, offsets
[i
], 1);
736 hbitmap_test_meta(data
, offsets
[i
], L1
, offsets
[i
], L1
);
737 hbitmap_test_meta(data
, offsets
[i
], L2
, offsets
[i
], L2
);
741 static void test_hbitmap_serialize_granularity(TestHBitmapData
*data
,
746 hbitmap_test_init(data
, L3
* 2, 3);
747 g_assert(hbitmap_is_serializable(data
->hb
));
749 r
= hbitmap_serialization_granularity(data
->hb
);
750 g_assert_cmpint(r
, ==, 64 << 3);
753 static void test_hbitmap_meta_zero(TestHBitmapData
*data
, const void *unused
)
755 hbitmap_test_init_meta(data
, 0, 0, 1);
757 hbitmap_check_meta(data
, 0, 0);
760 static void hbitmap_test_serialize_range(TestHBitmapData
*data
,
761 uint8_t *buf
, size_t buf_size
,
762 uint64_t pos
, uint64_t count
)
765 unsigned long *el
= (unsigned long *)buf
;
767 assert(hbitmap_granularity(data
->hb
) == 0);
768 hbitmap_reset_all(data
->hb
);
769 memset(buf
, 0, buf_size
);
771 hbitmap_set(data
->hb
, pos
, count
);
774 g_assert(hbitmap_is_serializable(data
->hb
));
775 hbitmap_serialize_part(data
->hb
, buf
, 0, data
->size
);
777 /* Serialized buffer is inherently LE, convert it back manually to test */
778 for (i
= 0; i
< buf_size
/ sizeof(unsigned long); i
++) {
779 el
[i
] = (BITS_PER_LONG
== 32 ? le32_to_cpu(el
[i
]) : le64_to_cpu(el
[i
]));
782 for (i
= 0; i
< data
->size
; i
++) {
783 int is_set
= test_bit(i
, (unsigned long *)buf
);
784 if (i
>= pos
&& i
< pos
+ count
) {
791 /* Re-serialize for deserialization testing */
792 memset(buf
, 0, buf_size
);
793 hbitmap_serialize_part(data
->hb
, buf
, 0, data
->size
);
794 hbitmap_reset_all(data
->hb
);
796 g_assert(hbitmap_is_serializable(data
->hb
));
797 hbitmap_deserialize_part(data
->hb
, buf
, 0, data
->size
, true);
799 for (i
= 0; i
< data
->size
; i
++) {
800 int is_set
= hbitmap_get(data
->hb
, i
);
801 if (i
>= pos
&& i
< pos
+ count
) {
809 static void test_hbitmap_serialize_basic(TestHBitmapData
*data
,
815 uint64_t positions
[] = { 0, 1, L1
- 1, L1
, L2
- 1, L2
, L2
+ 1, L3
- 1 };
816 int num_positions
= sizeof(positions
) / sizeof(positions
[0]);
818 hbitmap_test_init(data
, L3
, 0);
819 g_assert(hbitmap_is_serializable(data
->hb
));
820 buf_size
= hbitmap_serialization_size(data
->hb
, 0, data
->size
);
821 buf
= g_malloc0(buf_size
);
823 for (i
= 0; i
< num_positions
; i
++) {
824 for (j
= 0; j
< num_positions
; j
++) {
825 hbitmap_test_serialize_range(data
, buf
, buf_size
,
827 MIN(positions
[j
], L3
- positions
[i
]));
834 static void test_hbitmap_serialize_part(TestHBitmapData
*data
,
840 uint64_t positions
[] = { 0, 1, L1
- 1, L1
, L2
- 1, L2
, L2
+ 1, L3
- 1 };
841 int num_positions
= sizeof(positions
) / sizeof(positions
[0]);
843 hbitmap_test_init(data
, L3
, 0);
845 buf
= g_malloc0(buf_size
);
847 for (i
= 0; i
< num_positions
; i
++) {
848 hbitmap_set(data
->hb
, positions
[i
], 1);
851 g_assert(hbitmap_is_serializable(data
->hb
));
853 for (i
= 0; i
< data
->size
; i
+= buf_size
) {
854 unsigned long *el
= (unsigned long *)buf
;
855 hbitmap_serialize_part(data
->hb
, buf
, i
, buf_size
);
856 for (j
= 0; j
< buf_size
/ sizeof(unsigned long); j
++) {
857 el
[j
] = (BITS_PER_LONG
== 32 ? le32_to_cpu(el
[j
]) : le64_to_cpu(el
[j
]));
860 for (j
= 0; j
< buf_size
; j
++) {
861 bool should_set
= false;
862 for (k
= 0; k
< num_positions
; k
++) {
863 if (positions
[k
] == j
+ i
) {
868 g_assert_cmpint(should_set
, ==, test_bit(j
, (unsigned long *)buf
));
875 static void test_hbitmap_serialize_zeroes(TestHBitmapData
*data
,
881 uint64_t min_l1
= MAX(L1
, 64);
882 uint64_t positions
[] = { 0, min_l1
, L2
, L3
- min_l1
};
883 int num_positions
= sizeof(positions
) / sizeof(positions
[0]);
885 hbitmap_test_init(data
, L3
, 0);
887 for (i
= 0; i
< num_positions
; i
++) {
888 hbitmap_set(data
->hb
, positions
[i
], L1
);
891 g_assert(hbitmap_is_serializable(data
->hb
));
893 for (i
= 0; i
< num_positions
; i
++) {
894 hbitmap_deserialize_zeroes(data
->hb
, positions
[i
], min_l1
, true);
895 hbitmap_iter_init(&iter
, data
->hb
, 0);
896 next
= hbitmap_iter_next(&iter
);
897 if (i
== num_positions
- 1) {
898 g_assert_cmpint(next
, ==, -1);
900 g_assert_cmpint(next
, ==, positions
[i
+ 1]);
905 static void hbitmap_test_add(const char *testpath
,
906 void (*test_func
)(TestHBitmapData
*data
, const void *user_data
))
908 g_test_add(testpath
, TestHBitmapData
, NULL
, NULL
, test_func
,
909 hbitmap_test_teardown
);
912 int main(int argc
, char **argv
)
914 g_test_init(&argc
, &argv
, NULL
);
915 hbitmap_test_add("/hbitmap/size/0", test_hbitmap_zero
);
916 hbitmap_test_add("/hbitmap/size/unaligned", test_hbitmap_unaligned
);
917 hbitmap_test_add("/hbitmap/iter/empty", test_hbitmap_iter_empty
);
918 hbitmap_test_add("/hbitmap/iter/partial", test_hbitmap_iter_partial
);
919 hbitmap_test_add("/hbitmap/iter/granularity", test_hbitmap_iter_granularity
);
920 hbitmap_test_add("/hbitmap/get/all", test_hbitmap_get_all
);
921 hbitmap_test_add("/hbitmap/get/some", test_hbitmap_get_some
);
922 hbitmap_test_add("/hbitmap/set/all", test_hbitmap_set_all
);
923 hbitmap_test_add("/hbitmap/set/one", test_hbitmap_set_one
);
924 hbitmap_test_add("/hbitmap/set/two-elem", test_hbitmap_set_two_elem
);
925 hbitmap_test_add("/hbitmap/set/general", test_hbitmap_set
);
926 hbitmap_test_add("/hbitmap/set/twice", test_hbitmap_set_twice
);
927 hbitmap_test_add("/hbitmap/set/overlap", test_hbitmap_set_overlap
);
928 hbitmap_test_add("/hbitmap/reset/empty", test_hbitmap_reset_empty
);
929 hbitmap_test_add("/hbitmap/reset/general", test_hbitmap_reset
);
930 hbitmap_test_add("/hbitmap/reset/all", test_hbitmap_reset_all
);
931 hbitmap_test_add("/hbitmap/granularity", test_hbitmap_granularity
);
933 hbitmap_test_add("/hbitmap/truncate/nop", test_hbitmap_truncate_nop
);
934 hbitmap_test_add("/hbitmap/truncate/grow/negligible",
935 test_hbitmap_truncate_grow_negligible
);
936 hbitmap_test_add("/hbitmap/truncate/shrink/negligible",
937 test_hbitmap_truncate_shrink_negligible
);
938 hbitmap_test_add("/hbitmap/truncate/grow/tiny",
939 test_hbitmap_truncate_grow_tiny
);
940 hbitmap_test_add("/hbitmap/truncate/shrink/tiny",
941 test_hbitmap_truncate_shrink_tiny
);
942 hbitmap_test_add("/hbitmap/truncate/grow/small",
943 test_hbitmap_truncate_grow_small
);
944 hbitmap_test_add("/hbitmap/truncate/shrink/small",
945 test_hbitmap_truncate_shrink_small
);
946 hbitmap_test_add("/hbitmap/truncate/grow/medium",
947 test_hbitmap_truncate_grow_medium
);
948 hbitmap_test_add("/hbitmap/truncate/shrink/medium",
949 test_hbitmap_truncate_shrink_medium
);
950 hbitmap_test_add("/hbitmap/truncate/grow/large",
951 test_hbitmap_truncate_grow_large
);
952 hbitmap_test_add("/hbitmap/truncate/shrink/large",
953 test_hbitmap_truncate_shrink_large
);
955 hbitmap_test_add("/hbitmap/meta/zero", test_hbitmap_meta_zero
);
956 hbitmap_test_add("/hbitmap/meta/one", test_hbitmap_meta_one
);
957 hbitmap_test_add("/hbitmap/meta/byte", test_hbitmap_meta_byte
);
958 hbitmap_test_add("/hbitmap/meta/word", test_hbitmap_meta_word
);
959 hbitmap_test_add("/hbitmap/meta/sector", test_hbitmap_meta_sector
);
961 hbitmap_test_add("/hbitmap/serialize/granularity",
962 test_hbitmap_serialize_granularity
);
963 hbitmap_test_add("/hbitmap/serialize/basic",
964 test_hbitmap_serialize_basic
);
965 hbitmap_test_add("/hbitmap/serialize/part",
966 test_hbitmap_serialize_part
);
967 hbitmap_test_add("/hbitmap/serialize/zeroes",
968 test_hbitmap_serialize_zeroes
);