1
2
3
4
5
6
7
8
9
10
11
12#include "qemu/osdep.h"
13#include "qemu/hbitmap.h"
14#include "qemu/bitmap.h"
15#include "block/block.h"
16
17#define LOG_BITS_PER_LONG (BITS_PER_LONG == 32 ? 5 : 6)
18
19#define L1 BITS_PER_LONG
20#define L2 (BITS_PER_LONG * L1)
21#define L3 (BITS_PER_LONG * L2)
22
23typedef struct TestHBitmapData {
24 HBitmap *hb;
25 HBitmap *meta;
26 unsigned long *bits;
27 size_t size;
28 size_t old_size;
29 int granularity;
30} TestHBitmapData;
31
32
33static int64_t check_hbitmap_iter_next(HBitmapIter *hbi)
34{
35 int next0, next1;
36
37 next0 = hbitmap_iter_next(hbi, false);
38 next1 = hbitmap_iter_next(hbi, true);
39
40 g_assert_cmpint(next0, ==, next1);
41
42 return next0;
43}
44
45
46
47
48static void hbitmap_test_check(TestHBitmapData *data,
49 uint64_t first)
50{
51 uint64_t count = 0;
52 size_t pos;
53 int bit;
54 HBitmapIter hbi;
55 int64_t i, next;
56
57 hbitmap_iter_init(&hbi, data->hb, first);
58
59 i = first;
60 for (;;) {
61 next = check_hbitmap_iter_next(&hbi);
62 if (next < 0) {
63 next = data->size;
64 }
65
66 while (i < next) {
67 pos = i >> LOG_BITS_PER_LONG;
68 bit = i & (BITS_PER_LONG - 1);
69 i++;
70 g_assert_cmpint(data->bits[pos] & (1UL << bit), ==, 0);
71 }
72
73 if (next == data->size) {
74 break;
75 }
76
77 pos = i >> LOG_BITS_PER_LONG;
78 bit = i & (BITS_PER_LONG - 1);
79 i++;
80 count++;
81 g_assert_cmpint(data->bits[pos] & (1UL << bit), !=, 0);
82 }
83
84 if (first == 0) {
85 g_assert_cmpint(count << data->granularity, ==, hbitmap_count(data->hb));
86 }
87}
88
89
90
91static void hbitmap_test_init(TestHBitmapData *data,
92 uint64_t size, int granularity)
93{
94 size_t n;
95 data->hb = hbitmap_alloc(size, granularity);
96
97 n = DIV_ROUND_UP(size, BITS_PER_LONG);
98 if (n == 0) {
99 n = 1;
100 }
101 data->bits = g_new0(unsigned long, n);
102 data->size = size;
103 data->granularity = granularity;
104 if (size) {
105 hbitmap_test_check(data, 0);
106 }
107}
108
109static void hbitmap_test_init_meta(TestHBitmapData *data,
110 uint64_t size, int granularity,
111 int meta_chunk)
112{
113 hbitmap_test_init(data, size, granularity);
114 data->meta = hbitmap_create_meta(data->hb, meta_chunk);
115}
116
117static inline size_t hbitmap_test_array_size(size_t bits)
118{
119 size_t n = DIV_ROUND_UP(bits, BITS_PER_LONG);
120 return n ? n : 1;
121}
122
123static void hbitmap_test_truncate_impl(TestHBitmapData *data,
124 size_t size)
125{
126 size_t n;
127 size_t m;
128 data->old_size = data->size;
129 data->size = size;
130
131 if (data->size == data->old_size) {
132 return;
133 }
134
135 n = hbitmap_test_array_size(size);
136 m = hbitmap_test_array_size(data->old_size);
137 data->bits = g_realloc(data->bits, sizeof(unsigned long) * n);
138 if (n > m) {
139 memset(&data->bits[m], 0x00, sizeof(unsigned long) * (n - m));
140 }
141
142
143
144 if (data->size < data->old_size) {
145 m = size % (sizeof(unsigned long) * 8);
146 if (m) {
147 unsigned long mask = (1ULL << m) - 1;
148 data->bits[n-1] &= mask;
149 }
150 }
151
152 hbitmap_truncate(data->hb, size);
153}
154
155static void hbitmap_test_teardown(TestHBitmapData *data,
156 const void *unused)
157{
158 if (data->hb) {
159 if (data->meta) {
160 hbitmap_free_meta(data->hb);
161 }
162 hbitmap_free(data->hb);
163 data->hb = NULL;
164 }
165 g_free(data->bits);
166 data->bits = NULL;
167}
168
169
170
171
172static void hbitmap_test_set(TestHBitmapData *data,
173 uint64_t first, uint64_t count)
174{
175 hbitmap_set(data->hb, first, count);
176 while (count-- != 0) {
177 size_t pos = first >> LOG_BITS_PER_LONG;
178 int bit = first & (BITS_PER_LONG - 1);
179 first++;
180
181 data->bits[pos] |= 1UL << bit;
182 }
183
184 if (data->granularity == 0) {
185 hbitmap_test_check(data, 0);
186 }
187}
188
189
190
191static void hbitmap_test_reset(TestHBitmapData *data,
192 uint64_t first, uint64_t count)
193{
194 hbitmap_reset(data->hb, first, count);
195 while (count-- != 0) {
196 size_t pos = first >> LOG_BITS_PER_LONG;
197 int bit = first & (BITS_PER_LONG - 1);
198 first++;
199
200 data->bits[pos] &= ~(1UL << bit);
201 }
202
203 if (data->granularity == 0) {
204 hbitmap_test_check(data, 0);
205 }
206}
207
208static void hbitmap_test_reset_all(TestHBitmapData *data)
209{
210 size_t n;
211
212 hbitmap_reset_all(data->hb);
213
214 n = DIV_ROUND_UP(data->size, BITS_PER_LONG);
215 if (n == 0) {
216 n = 1;
217 }
218 memset(data->bits, 0, n * sizeof(unsigned long));
219
220 if (data->granularity == 0) {
221 hbitmap_test_check(data, 0);
222 }
223}
224
225static void hbitmap_test_check_get(TestHBitmapData *data)
226{
227 uint64_t count = 0;
228 uint64_t i;
229
230 for (i = 0; i < data->size; i++) {
231 size_t pos = i >> LOG_BITS_PER_LONG;
232 int bit = i & (BITS_PER_LONG - 1);
233 unsigned long val = data->bits[pos] & (1UL << bit);
234 count += hbitmap_get(data->hb, i);
235 g_assert_cmpint(hbitmap_get(data->hb, i), ==, val != 0);
236 }
237 g_assert_cmpint(count, ==, hbitmap_count(data->hb));
238}
239
240static void test_hbitmap_zero(TestHBitmapData *data,
241 const void *unused)
242{
243 hbitmap_test_init(data, 0, 0);
244}
245
246static void test_hbitmap_unaligned(TestHBitmapData *data,
247 const void *unused)
248{
249 hbitmap_test_init(data, L3 + 23, 0);
250 hbitmap_test_set(data, 0, 1);
251 hbitmap_test_set(data, L3 + 22, 1);
252}
253
254static void test_hbitmap_iter_empty(TestHBitmapData *data,
255 const void *unused)
256{
257 hbitmap_test_init(data, L1, 0);
258}
259
260static void test_hbitmap_iter_partial(TestHBitmapData *data,
261 const void *unused)
262{
263 hbitmap_test_init(data, L3, 0);
264 hbitmap_test_set(data, 0, L3);
265 hbitmap_test_check(data, 1);
266 hbitmap_test_check(data, L1 - 1);
267 hbitmap_test_check(data, L1);
268 hbitmap_test_check(data, L1 * 2 - 1);
269 hbitmap_test_check(data, L2 - 1);
270 hbitmap_test_check(data, L2);
271 hbitmap_test_check(data, L2 + 1);
272 hbitmap_test_check(data, L2 + L1);
273 hbitmap_test_check(data, L2 + L1 * 2 - 1);
274 hbitmap_test_check(data, L2 * 2 - 1);
275 hbitmap_test_check(data, L2 * 2);
276 hbitmap_test_check(data, L2 * 2 + 1);
277 hbitmap_test_check(data, L2 * 2 + L1);
278 hbitmap_test_check(data, L2 * 2 + L1 * 2 - 1);
279 hbitmap_test_check(data, L3 / 2);
280}
281
282static void test_hbitmap_set_all(TestHBitmapData *data,
283 const void *unused)
284{
285 hbitmap_test_init(data, L3, 0);
286 hbitmap_test_set(data, 0, L3);
287}
288
289static void test_hbitmap_get_all(TestHBitmapData *data,
290 const void *unused)
291{
292 hbitmap_test_init(data, L3, 0);
293 hbitmap_test_set(data, 0, L3);
294 hbitmap_test_check_get(data);
295}
296
297static void test_hbitmap_get_some(TestHBitmapData *data,
298 const void *unused)
299{
300 hbitmap_test_init(data, 2 * L2, 0);
301 hbitmap_test_set(data, 10, 1);
302 hbitmap_test_check_get(data);
303 hbitmap_test_set(data, L1 - 1, 1);
304 hbitmap_test_check_get(data);
305 hbitmap_test_set(data, L1, 1);
306 hbitmap_test_check_get(data);
307 hbitmap_test_set(data, L2 - 1, 1);
308 hbitmap_test_check_get(data);
309 hbitmap_test_set(data, L2, 1);
310 hbitmap_test_check_get(data);
311}
312
313static void test_hbitmap_set_one(TestHBitmapData *data,
314 const void *unused)
315{
316 hbitmap_test_init(data, 2 * L2, 0);
317 hbitmap_test_set(data, 10, 1);
318 hbitmap_test_set(data, L1 - 1, 1);
319 hbitmap_test_set(data, L1, 1);
320 hbitmap_test_set(data, L2 - 1, 1);
321 hbitmap_test_set(data, L2, 1);
322}
323
324static void test_hbitmap_set_two_elem(TestHBitmapData *data,
325 const void *unused)
326{
327 hbitmap_test_init(data, 2 * L2, 0);
328 hbitmap_test_set(data, L1 - 1, 2);
329 hbitmap_test_set(data, L1 * 2 - 1, 4);
330 hbitmap_test_set(data, L1 * 4, L1 + 1);
331 hbitmap_test_set(data, L1 * 8 - 1, L1 + 1);
332 hbitmap_test_set(data, L2 - 1, 2);
333 hbitmap_test_set(data, L2 + L1 - 1, 8);
334 hbitmap_test_set(data, L2 + L1 * 4, L1 + 1);
335 hbitmap_test_set(data, L2 + L1 * 8 - 1, L1 + 1);
336}
337
338static void test_hbitmap_set(TestHBitmapData *data,
339 const void *unused)
340{
341 hbitmap_test_init(data, L3 * 2, 0);
342 hbitmap_test_set(data, L1 - 1, L1 + 2);
343 hbitmap_test_set(data, L1 * 3 - 1, L1 + 2);
344 hbitmap_test_set(data, L1 * 5, L1 * 2 + 1);
345 hbitmap_test_set(data, L1 * 8 - 1, L1 * 2 + 1);
346 hbitmap_test_set(data, L2 - 1, L1 + 2);
347 hbitmap_test_set(data, L2 + L1 * 2 - 1, L1 + 2);
348 hbitmap_test_set(data, L2 + L1 * 4, L1 * 2 + 1);
349 hbitmap_test_set(data, L2 + L1 * 7 - 1, L1 * 2 + 1);
350 hbitmap_test_set(data, L2 * 2 - 1, L3 * 2 - L2 * 2);
351}
352
353static void test_hbitmap_set_twice(TestHBitmapData *data,
354 const void *unused)
355{
356 hbitmap_test_init(data, L1 * 3, 0);
357 hbitmap_test_set(data, 0, L1 * 3);
358 hbitmap_test_set(data, L1, 1);
359}
360
361static void test_hbitmap_set_overlap(TestHBitmapData *data,
362 const void *unused)
363{
364 hbitmap_test_init(data, L3 * 2, 0);
365 hbitmap_test_set(data, L1 - 1, L1 + 2);
366 hbitmap_test_set(data, L1 * 2 - 1, L1 * 2 + 2);
367 hbitmap_test_set(data, 0, L1 * 3);
368 hbitmap_test_set(data, L1 * 8 - 1, L2);
369 hbitmap_test_set(data, L2, L1);
370 hbitmap_test_set(data, L2 - L1 - 1, L1 * 8 + 2);
371 hbitmap_test_set(data, L2, L3 - L2 + 1);
372 hbitmap_test_set(data, L3 - L1, L1 * 3);
373 hbitmap_test_set(data, L3 - 1, 3);
374 hbitmap_test_set(data, L3 - 1, L2);
375}
376
377static void test_hbitmap_reset_empty(TestHBitmapData *data,
378 const void *unused)
379{
380 hbitmap_test_init(data, L3, 0);
381 hbitmap_test_reset(data, 0, L3);
382}
383
384static void test_hbitmap_reset(TestHBitmapData *data,
385 const void *unused)
386{
387 hbitmap_test_init(data, L3 * 2, 0);
388 hbitmap_test_set(data, L1 - 1, L1 + 2);
389 hbitmap_test_reset(data, L1 * 2 - 1, L1 * 2 + 2);
390 hbitmap_test_set(data, 0, L1 * 3);
391 hbitmap_test_reset(data, L1 * 8 - 1, L2);
392 hbitmap_test_set(data, L2, L1);
393 hbitmap_test_reset(data, L2 - L1 - 1, L1 * 8 + 2);
394 hbitmap_test_set(data, L2, L3 - L2 + 1);
395 hbitmap_test_reset(data, L3 - L1, L1 * 3);
396 hbitmap_test_set(data, L3 - 1, 3);
397 hbitmap_test_reset(data, L3 - 1, L2);
398 hbitmap_test_set(data, 0, L3 * 2);
399 hbitmap_test_reset(data, 0, L1);
400 hbitmap_test_reset(data, 0, L2);
401 hbitmap_test_reset(data, L3, L3);
402 hbitmap_test_set(data, L3 / 2, L3);
403}
404
405static void test_hbitmap_reset_all(TestHBitmapData *data,
406 const void *unused)
407{
408 hbitmap_test_init(data, L3 * 2, 0);
409 hbitmap_test_set(data, L1 - 1, L1 + 2);
410 hbitmap_test_reset_all(data);
411 hbitmap_test_set(data, 0, L1 * 3);
412 hbitmap_test_reset_all(data);
413 hbitmap_test_set(data, L2, L1);
414 hbitmap_test_reset_all(data);
415 hbitmap_test_set(data, L2, L3 - L2 + 1);
416 hbitmap_test_reset_all(data);
417 hbitmap_test_set(data, L3 - 1, 3);
418 hbitmap_test_reset_all(data);
419 hbitmap_test_set(data, 0, L3 * 2);
420 hbitmap_test_reset_all(data);
421 hbitmap_test_set(data, L3 / 2, L3);
422 hbitmap_test_reset_all(data);
423}
424
425static void test_hbitmap_granularity(TestHBitmapData *data,
426 const void *unused)
427{
428
429 hbitmap_test_init(data, L1, 1);
430 hbitmap_test_set(data, 0, 1);
431 g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
432 hbitmap_test_check(data, 0);
433 hbitmap_test_set(data, 2, 1);
434 g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
435 hbitmap_test_check(data, 0);
436 hbitmap_test_set(data, 0, 3);
437 g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
438 hbitmap_test_reset(data, 0, 1);
439 g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
440}
441
442static void test_hbitmap_iter_granularity(TestHBitmapData *data,
443 const void *unused)
444{
445 HBitmapIter hbi;
446
447
448 hbitmap_test_init(data, 131072 << 7, 7);
449 hbitmap_iter_init(&hbi, data->hb, 0);
450 g_assert_cmpint(check_hbitmap_iter_next(&hbi), <, 0);
451
452 hbitmap_test_set(data, ((L2 + L1 + 1) << 7) + 8, 8);
453 hbitmap_iter_init(&hbi, data->hb, 0);
454 g_assert_cmpint(check_hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
455 g_assert_cmpint(check_hbitmap_iter_next(&hbi), <, 0);
456
457 hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
458 g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
459
460 hbitmap_test_set(data, (131072 << 7) - 8, 8);
461 hbitmap_iter_init(&hbi, data->hb, 0);
462 g_assert_cmpint(check_hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
463 g_assert_cmpint(check_hbitmap_iter_next(&hbi), ==, 131071 << 7);
464 g_assert_cmpint(check_hbitmap_iter_next(&hbi), <, 0);
465
466 hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
467 g_assert_cmpint(check_hbitmap_iter_next(&hbi), ==, 131071 << 7);
468 g_assert_cmpint(check_hbitmap_iter_next(&hbi), <, 0);
469}
470
471static void hbitmap_test_set_boundary_bits(TestHBitmapData *data, ssize_t diff)
472{
473 size_t size = data->size;
474
475
476 hbitmap_test_set(data, 0, 1);
477 if (diff < 0) {
478
479 hbitmap_test_set(data, size + diff - 1, 1);
480
481
482 hbitmap_test_set(data, size + diff, 1);
483 }
484
485 hbitmap_test_set(data, size - 1, 1);
486 if (data->granularity == 0) {
487 hbitmap_test_check_get(data);
488 }
489}
490
491static void hbitmap_test_check_boundary_bits(TestHBitmapData *data)
492{
493 size_t size = MIN(data->size, data->old_size);
494
495 if (data->granularity == 0) {
496 hbitmap_test_check_get(data);
497 hbitmap_test_check(data, 0);
498 } else {
499
500
501
502
503
504
505
506
507 g_assert(hbitmap_get(data->hb, 0));
508 g_assert(hbitmap_get(data->hb, size - 1));
509 g_assert_cmpint(2 << data->granularity, ==, hbitmap_count(data->hb));
510 }
511}
512
513
514static void hbitmap_test_truncate(TestHBitmapData *data,
515 size_t size,
516 ssize_t diff,
517 int granularity)
518{
519 hbitmap_test_init(data, size, granularity);
520 hbitmap_test_set_boundary_bits(data, diff);
521 hbitmap_test_truncate_impl(data, size + diff);
522 hbitmap_test_check_boundary_bits(data);
523}
524
525static void test_hbitmap_truncate_nop(TestHBitmapData *data,
526 const void *unused)
527{
528 hbitmap_test_truncate(data, L2, 0, 0);
529}
530
531
532
533
534
535static void test_hbitmap_truncate_grow_negligible(TestHBitmapData *data,
536 const void *unused)
537{
538 size_t size = L2 - 1;
539 size_t diff = 1;
540 int granularity = 1;
541
542 hbitmap_test_truncate(data, size, diff, granularity);
543}
544
545
546
547
548
549static void test_hbitmap_truncate_shrink_negligible(TestHBitmapData *data,
550 const void *unused)
551{
552 size_t size = L2;
553 ssize_t diff = -1;
554 int granularity = 1;
555
556 hbitmap_test_truncate(data, size, diff, granularity);
557}
558
559
560
561
562
563static void test_hbitmap_truncate_grow_tiny(TestHBitmapData *data,
564 const void *unused)
565{
566 size_t size = L2 - 2;
567 ssize_t diff = 1;
568 int granularity = 1;
569
570 hbitmap_test_truncate(data, size, diff, granularity);
571}
572
573
574
575
576
577static void test_hbitmap_truncate_shrink_tiny(TestHBitmapData *data,
578 const void *unused)
579{
580 size_t size = L2 - 1;
581 ssize_t diff = -1;
582 int granularity = 1;
583
584 hbitmap_test_truncate(data, size, diff, granularity);
585}
586
587
588
589
590
591static void test_hbitmap_truncate_grow_small(TestHBitmapData *data,
592 const void *unused)
593{
594 size_t size = L2 + 1;
595 size_t diff = sizeof(long) / 2;
596
597 hbitmap_test_truncate(data, size, diff, 0);
598}
599
600
601
602
603
604static void test_hbitmap_truncate_shrink_small(TestHBitmapData *data,
605 const void *unused)
606{
607 size_t size = L2;
608 size_t diff = sizeof(long) / 2;
609
610 hbitmap_test_truncate(data, size, -diff, 0);
611}
612
613
614
615
616
617static void test_hbitmap_truncate_grow_medium(TestHBitmapData *data,
618 const void *unused)
619{
620 size_t size = L2 - 1;
621 size_t diff = sizeof(long) / 2;
622
623 hbitmap_test_truncate(data, size, diff, 0);
624}
625
626
627
628
629
630static void test_hbitmap_truncate_shrink_medium(TestHBitmapData *data,
631 const void *unused)
632{
633 size_t size = L2 + 1;
634 size_t diff = sizeof(long) / 2;
635
636 hbitmap_test_truncate(data, size, -diff, 0);
637}
638
639
640
641
642static void test_hbitmap_truncate_grow_large(TestHBitmapData *data,
643 const void *unused)
644{
645 size_t size = L2;
646 size_t diff = 8 * sizeof(long);
647
648 hbitmap_test_truncate(data, size, diff, 0);
649}
650
651
652
653
654static void test_hbitmap_truncate_shrink_large(TestHBitmapData *data,
655 const void *unused)
656{
657 size_t size = L2;
658 size_t diff = 8 * sizeof(long);
659
660 hbitmap_test_truncate(data, size, -diff, 0);
661}
662
663static void hbitmap_check_meta(TestHBitmapData *data,
664 int64_t start, int count)
665{
666 int64_t i;
667
668 for (i = 0; i < data->size; i++) {
669 if (i >= start && i < start + count) {
670 g_assert(hbitmap_get(data->meta, i));
671 } else {
672 g_assert(!hbitmap_get(data->meta, i));
673 }
674 }
675}
676
677static void hbitmap_test_meta(TestHBitmapData *data,
678 int64_t start, int count,
679 int64_t check_start, int check_count)
680{
681 hbitmap_reset_all(data->hb);
682 hbitmap_reset_all(data->meta);
683
684
685 hbitmap_reset(data->hb, start, count);
686 hbitmap_check_meta(data, 0, 0);
687
688
689 hbitmap_set(data->hb, start, count);
690 hbitmap_check_meta(data, check_start, check_count);
691
692
693 hbitmap_reset_all(data->meta);
694 hbitmap_set(data->hb, start, count);
695 hbitmap_check_meta(data, 0, 0);
696
697
698 hbitmap_reset_all(data->meta);
699 hbitmap_reset(data->hb, start, count);
700 hbitmap_check_meta(data, check_start, check_count);
701}
702
703static void hbitmap_test_meta_do(TestHBitmapData *data, int chunk_size)
704{
705 uint64_t size = chunk_size * 100;
706 hbitmap_test_init_meta(data, size, 0, chunk_size);
707
708 hbitmap_test_meta(data, 0, 1, 0, chunk_size);
709 hbitmap_test_meta(data, 0, chunk_size, 0, chunk_size);
710 hbitmap_test_meta(data, chunk_size - 1, 1, 0, chunk_size);
711 hbitmap_test_meta(data, chunk_size - 1, 2, 0, chunk_size * 2);
712 hbitmap_test_meta(data, chunk_size - 1, chunk_size + 1, 0, chunk_size * 2);
713 hbitmap_test_meta(data, chunk_size - 1, chunk_size + 2, 0, chunk_size * 3);
714 hbitmap_test_meta(data, 7 * chunk_size - 1, chunk_size + 2,
715 6 * chunk_size, chunk_size * 3);
716 hbitmap_test_meta(data, size - 1, 1, size - chunk_size, chunk_size);
717 hbitmap_test_meta(data, 0, size, 0, size);
718}
719
720static void test_hbitmap_meta_byte(TestHBitmapData *data, const void *unused)
721{
722 hbitmap_test_meta_do(data, BITS_PER_BYTE);
723}
724
725static void test_hbitmap_meta_word(TestHBitmapData *data, const void *unused)
726{
727 hbitmap_test_meta_do(data, BITS_PER_LONG);
728}
729
730static void test_hbitmap_meta_sector(TestHBitmapData *data, const void *unused)
731{
732 hbitmap_test_meta_do(data, BDRV_SECTOR_SIZE * BITS_PER_BYTE);
733}
734
735
736
737
738static void test_hbitmap_meta_one(TestHBitmapData *data, const void *unused)
739{
740 int i;
741 int64_t offsets[] = {
742 0, 1, L1 - 1, L1, L1 + 1, L2 - 1, L2, L2 + 1, L3 - 1, L3, L3 + 1
743 };
744
745 hbitmap_test_init_meta(data, L3 * 2, 0, 1);
746 for (i = 0; i < ARRAY_SIZE(offsets); i++) {
747 hbitmap_test_meta(data, offsets[i], 1, offsets[i], 1);
748 hbitmap_test_meta(data, offsets[i], L1, offsets[i], L1);
749 hbitmap_test_meta(data, offsets[i], L2, offsets[i], L2);
750 }
751}
752
753static void test_hbitmap_serialize_align(TestHBitmapData *data,
754 const void *unused)
755{
756 int r;
757
758 hbitmap_test_init(data, L3 * 2, 3);
759 g_assert(hbitmap_is_serializable(data->hb));
760
761 r = hbitmap_serialization_align(data->hb);
762 g_assert_cmpint(r, ==, 64 << 3);
763}
764
765static void test_hbitmap_meta_zero(TestHBitmapData *data, const void *unused)
766{
767 hbitmap_test_init_meta(data, 0, 0, 1);
768
769 hbitmap_check_meta(data, 0, 0);
770}
771
772static void hbitmap_test_serialize_range(TestHBitmapData *data,
773 uint8_t *buf, size_t buf_size,
774 uint64_t pos, uint64_t count)
775{
776 size_t i;
777 unsigned long *el = (unsigned long *)buf;
778
779 assert(hbitmap_granularity(data->hb) == 0);
780 hbitmap_reset_all(data->hb);
781 memset(buf, 0, buf_size);
782 if (count) {
783 hbitmap_set(data->hb, pos, count);
784 }
785
786 g_assert(hbitmap_is_serializable(data->hb));
787 hbitmap_serialize_part(data->hb, buf, 0, data->size);
788
789
790 for (i = 0; i < buf_size / sizeof(unsigned long); i++) {
791 el[i] = (BITS_PER_LONG == 32 ? le32_to_cpu(el[i]) : le64_to_cpu(el[i]));
792 }
793
794 for (i = 0; i < data->size; i++) {
795 int is_set = test_bit(i, (unsigned long *)buf);
796 if (i >= pos && i < pos + count) {
797 g_assert(is_set);
798 } else {
799 g_assert(!is_set);
800 }
801 }
802
803
804 memset(buf, 0, buf_size);
805 hbitmap_serialize_part(data->hb, buf, 0, data->size);
806 hbitmap_reset_all(data->hb);
807
808 g_assert(hbitmap_is_serializable(data->hb));
809 hbitmap_deserialize_part(data->hb, buf, 0, data->size, true);
810
811 for (i = 0; i < data->size; i++) {
812 int is_set = hbitmap_get(data->hb, i);
813 if (i >= pos && i < pos + count) {
814 g_assert(is_set);
815 } else {
816 g_assert(!is_set);
817 }
818 }
819}
820
821static void test_hbitmap_serialize_basic(TestHBitmapData *data,
822 const void *unused)
823{
824 int i, j;
825 size_t buf_size;
826 uint8_t *buf;
827 uint64_t positions[] = { 0, 1, L1 - 1, L1, L2 - 1, L2, L2 + 1, L3 - 1 };
828 int num_positions = ARRAY_SIZE(positions);
829
830 hbitmap_test_init(data, L3, 0);
831 g_assert(hbitmap_is_serializable(data->hb));
832 buf_size = hbitmap_serialization_size(data->hb, 0, data->size);
833 buf = g_malloc0(buf_size);
834
835 for (i = 0; i < num_positions; i++) {
836 for (j = 0; j < num_positions; j++) {
837 hbitmap_test_serialize_range(data, buf, buf_size,
838 positions[i],
839 MIN(positions[j], L3 - positions[i]));
840 }
841 }
842
843 g_free(buf);
844}
845
846static void test_hbitmap_serialize_part(TestHBitmapData *data,
847 const void *unused)
848{
849 int i, j, k;
850 size_t buf_size;
851 uint8_t *buf;
852 uint64_t positions[] = { 0, 1, L1 - 1, L1, L2 - 1, L2, L2 + 1, L3 - 1 };
853 int num_positions = ARRAY_SIZE(positions);
854
855 hbitmap_test_init(data, L3, 0);
856 buf_size = L2;
857 buf = g_malloc0(buf_size);
858
859 for (i = 0; i < num_positions; i++) {
860 hbitmap_set(data->hb, positions[i], 1);
861 }
862
863 g_assert(hbitmap_is_serializable(data->hb));
864
865 for (i = 0; i < data->size; i += buf_size) {
866 unsigned long *el = (unsigned long *)buf;
867 hbitmap_serialize_part(data->hb, buf, i, buf_size);
868 for (j = 0; j < buf_size / sizeof(unsigned long); j++) {
869 el[j] = (BITS_PER_LONG == 32 ? le32_to_cpu(el[j]) : le64_to_cpu(el[j]));
870 }
871
872 for (j = 0; j < buf_size; j++) {
873 bool should_set = false;
874 for (k = 0; k < num_positions; k++) {
875 if (positions[k] == j + i) {
876 should_set = true;
877 break;
878 }
879 }
880 g_assert_cmpint(should_set, ==, test_bit(j, (unsigned long *)buf));
881 }
882 }
883
884 g_free(buf);
885}
886
887static void test_hbitmap_serialize_zeroes(TestHBitmapData *data,
888 const void *unused)
889{
890 int i;
891 HBitmapIter iter;
892 int64_t next;
893 uint64_t min_l1 = MAX(L1, 64);
894 uint64_t positions[] = { 0, min_l1, L2, L3 - min_l1};
895 int num_positions = ARRAY_SIZE(positions);
896
897 hbitmap_test_init(data, L3, 0);
898
899 for (i = 0; i < num_positions; i++) {
900 hbitmap_set(data->hb, positions[i], L1);
901 }
902
903 g_assert(hbitmap_is_serializable(data->hb));
904
905 for (i = 0; i < num_positions; i++) {
906 hbitmap_deserialize_zeroes(data->hb, positions[i], min_l1, true);
907 hbitmap_iter_init(&iter, data->hb, 0);
908 next = check_hbitmap_iter_next(&iter);
909 if (i == num_positions - 1) {
910 g_assert_cmpint(next, ==, -1);
911 } else {
912 g_assert_cmpint(next, ==, positions[i + 1]);
913 }
914 }
915}
916
917static void hbitmap_test_add(const char *testpath,
918 void (*test_func)(TestHBitmapData *data, const void *user_data))
919{
920 g_test_add(testpath, TestHBitmapData, NULL, NULL, test_func,
921 hbitmap_test_teardown);
922}
923
924static void test_hbitmap_iter_and_reset(TestHBitmapData *data,
925 const void *unused)
926{
927 HBitmapIter hbi;
928
929 hbitmap_test_init(data, L1 * 2, 0);
930 hbitmap_set(data->hb, 0, data->size);
931
932 hbitmap_iter_init(&hbi, data->hb, BITS_PER_LONG - 1);
933
934 check_hbitmap_iter_next(&hbi);
935
936 hbitmap_reset_all(data->hb);
937 check_hbitmap_iter_next(&hbi);
938}
939
940static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start)
941{
942 int64_t ret1 = hbitmap_next_zero(data->hb, start);
943 int64_t ret2 = start;
944 for ( ; ret2 < data->size && hbitmap_get(data->hb, ret2); ret2++) {
945 ;
946 }
947 if (ret2 == data->size) {
948 ret2 = -1;
949 }
950
951 g_assert_cmpint(ret1, ==, ret2);
952}
953
954static void test_hbitmap_next_zero_do(TestHBitmapData *data, int granularity)
955{
956 hbitmap_test_init(data, L3, granularity);
957 test_hbitmap_next_zero_check(data, 0);
958 test_hbitmap_next_zero_check(data, L3 - 1);
959
960 hbitmap_set(data->hb, L2, 1);
961 test_hbitmap_next_zero_check(data, 0);
962 test_hbitmap_next_zero_check(data, L2 - 1);
963 test_hbitmap_next_zero_check(data, L2);
964 test_hbitmap_next_zero_check(data, L2 + 1);
965
966 hbitmap_set(data->hb, L2 + 5, L1);
967 test_hbitmap_next_zero_check(data, 0);
968 test_hbitmap_next_zero_check(data, L2 + 1);
969 test_hbitmap_next_zero_check(data, L2 + 2);
970 test_hbitmap_next_zero_check(data, L2 + 5);
971 test_hbitmap_next_zero_check(data, L2 + L1 - 1);
972 test_hbitmap_next_zero_check(data, L2 + L1);
973
974 hbitmap_set(data->hb, L2 * 2, L3 - L2 * 2);
975 test_hbitmap_next_zero_check(data, L2 * 2 - L1);
976 test_hbitmap_next_zero_check(data, L2 * 2 - 2);
977 test_hbitmap_next_zero_check(data, L2 * 2 - 1);
978 test_hbitmap_next_zero_check(data, L2 * 2);
979 test_hbitmap_next_zero_check(data, L3 - 1);
980
981 hbitmap_set(data->hb, 0, L3);
982 test_hbitmap_next_zero_check(data, 0);
983}
984
985static void test_hbitmap_next_zero_0(TestHBitmapData *data, const void *unused)
986{
987 test_hbitmap_next_zero_do(data, 0);
988}
989
990static void test_hbitmap_next_zero_4(TestHBitmapData *data, const void *unused)
991{
992 test_hbitmap_next_zero_do(data, 4);
993}
994
995int main(int argc, char **argv)
996{
997 g_test_init(&argc, &argv, NULL);
998 hbitmap_test_add("/hbitmap/size/0", test_hbitmap_zero);
999 hbitmap_test_add("/hbitmap/size/unaligned", test_hbitmap_unaligned);
1000 hbitmap_test_add("/hbitmap/iter/empty", test_hbitmap_iter_empty);
1001 hbitmap_test_add("/hbitmap/iter/partial", test_hbitmap_iter_partial);
1002 hbitmap_test_add("/hbitmap/iter/granularity", test_hbitmap_iter_granularity);
1003 hbitmap_test_add("/hbitmap/get/all", test_hbitmap_get_all);
1004 hbitmap_test_add("/hbitmap/get/some", test_hbitmap_get_some);
1005 hbitmap_test_add("/hbitmap/set/all", test_hbitmap_set_all);
1006 hbitmap_test_add("/hbitmap/set/one", test_hbitmap_set_one);
1007 hbitmap_test_add("/hbitmap/set/two-elem", test_hbitmap_set_two_elem);
1008 hbitmap_test_add("/hbitmap/set/general", test_hbitmap_set);
1009 hbitmap_test_add("/hbitmap/set/twice", test_hbitmap_set_twice);
1010 hbitmap_test_add("/hbitmap/set/overlap", test_hbitmap_set_overlap);
1011 hbitmap_test_add("/hbitmap/reset/empty", test_hbitmap_reset_empty);
1012 hbitmap_test_add("/hbitmap/reset/general", test_hbitmap_reset);
1013 hbitmap_test_add("/hbitmap/reset/all", test_hbitmap_reset_all);
1014 hbitmap_test_add("/hbitmap/granularity", test_hbitmap_granularity);
1015
1016 hbitmap_test_add("/hbitmap/truncate/nop", test_hbitmap_truncate_nop);
1017 hbitmap_test_add("/hbitmap/truncate/grow/negligible",
1018 test_hbitmap_truncate_grow_negligible);
1019 hbitmap_test_add("/hbitmap/truncate/shrink/negligible",
1020 test_hbitmap_truncate_shrink_negligible);
1021 hbitmap_test_add("/hbitmap/truncate/grow/tiny",
1022 test_hbitmap_truncate_grow_tiny);
1023 hbitmap_test_add("/hbitmap/truncate/shrink/tiny",
1024 test_hbitmap_truncate_shrink_tiny);
1025 hbitmap_test_add("/hbitmap/truncate/grow/small",
1026 test_hbitmap_truncate_grow_small);
1027 hbitmap_test_add("/hbitmap/truncate/shrink/small",
1028 test_hbitmap_truncate_shrink_small);
1029 hbitmap_test_add("/hbitmap/truncate/grow/medium",
1030 test_hbitmap_truncate_grow_medium);
1031 hbitmap_test_add("/hbitmap/truncate/shrink/medium",
1032 test_hbitmap_truncate_shrink_medium);
1033 hbitmap_test_add("/hbitmap/truncate/grow/large",
1034 test_hbitmap_truncate_grow_large);
1035 hbitmap_test_add("/hbitmap/truncate/shrink/large",
1036 test_hbitmap_truncate_shrink_large);
1037
1038 hbitmap_test_add("/hbitmap/meta/zero", test_hbitmap_meta_zero);
1039 hbitmap_test_add("/hbitmap/meta/one", test_hbitmap_meta_one);
1040 hbitmap_test_add("/hbitmap/meta/byte", test_hbitmap_meta_byte);
1041 hbitmap_test_add("/hbitmap/meta/word", test_hbitmap_meta_word);
1042 hbitmap_test_add("/hbitmap/meta/sector", test_hbitmap_meta_sector);
1043
1044 hbitmap_test_add("/hbitmap/serialize/align",
1045 test_hbitmap_serialize_align);
1046 hbitmap_test_add("/hbitmap/serialize/basic",
1047 test_hbitmap_serialize_basic);
1048 hbitmap_test_add("/hbitmap/serialize/part",
1049 test_hbitmap_serialize_part);
1050 hbitmap_test_add("/hbitmap/serialize/zeroes",
1051 test_hbitmap_serialize_zeroes);
1052
1053 hbitmap_test_add("/hbitmap/iter/iter_and_reset",
1054 test_hbitmap_iter_and_reset);
1055
1056 hbitmap_test_add("/hbitmap/next_zero/next_zero_0",
1057 test_hbitmap_next_zero_0);
1058 hbitmap_test_add("/hbitmap/next_zero/next_zero_4",
1059 test_hbitmap_next_zero_4);
1060
1061 g_test_run();
1062
1063 return 0;
1064}
1065