1
2
3
4
5
6
7
8
9
10
11
12#include "qemu/osdep.h"
13#include "qemu/hbitmap.h"
14
15#define LOG_BITS_PER_LONG (BITS_PER_LONG == 32 ? 5 : 6)
16
17#define L1 BITS_PER_LONG
18#define L2 (BITS_PER_LONG * L1)
19#define L3 (BITS_PER_LONG * L2)
20
21typedef struct TestHBitmapData {
22 HBitmap *hb;
23 unsigned long *bits;
24 size_t size;
25 size_t old_size;
26 int granularity;
27} TestHBitmapData;
28
29
30
31
32
33static void hbitmap_test_check(TestHBitmapData *data,
34 uint64_t first)
35{
36 uint64_t count = 0;
37 size_t pos;
38 int bit;
39 HBitmapIter hbi;
40 int64_t i, next;
41
42 hbitmap_iter_init(&hbi, data->hb, first);
43
44 i = first;
45 for (;;) {
46 next = hbitmap_iter_next(&hbi);
47 if (next < 0) {
48 next = data->size;
49 }
50
51 while (i < next) {
52 pos = i >> LOG_BITS_PER_LONG;
53 bit = i & (BITS_PER_LONG - 1);
54 i++;
55 g_assert_cmpint(data->bits[pos] & (1UL << bit), ==, 0);
56 }
57
58 if (next == data->size) {
59 break;
60 }
61
62 pos = i >> LOG_BITS_PER_LONG;
63 bit = i & (BITS_PER_LONG - 1);
64 i++;
65 count++;
66 g_assert_cmpint(data->bits[pos] & (1UL << bit), !=, 0);
67 }
68
69 if (first == 0) {
70 g_assert_cmpint(count << data->granularity, ==, hbitmap_count(data->hb));
71 }
72}
73
74
75
76static void hbitmap_test_init(TestHBitmapData *data,
77 uint64_t size, int granularity)
78{
79 size_t n;
80 data->hb = hbitmap_alloc(size, granularity);
81
82 n = DIV_ROUND_UP(size, BITS_PER_LONG);
83 if (n == 0) {
84 n = 1;
85 }
86 data->bits = g_new0(unsigned long, n);
87 data->size = size;
88 data->granularity = granularity;
89 if (size) {
90 hbitmap_test_check(data, 0);
91 }
92}
93
94static inline size_t hbitmap_test_array_size(size_t bits)
95{
96 size_t n = DIV_ROUND_UP(bits, BITS_PER_LONG);
97 return n ? n : 1;
98}
99
100static void hbitmap_test_truncate_impl(TestHBitmapData *data,
101 size_t size)
102{
103 size_t n;
104 size_t m;
105 data->old_size = data->size;
106 data->size = size;
107
108 if (data->size == data->old_size) {
109 return;
110 }
111
112 n = hbitmap_test_array_size(size);
113 m = hbitmap_test_array_size(data->old_size);
114 data->bits = g_realloc(data->bits, sizeof(unsigned long) * n);
115 if (n > m) {
116 memset(&data->bits[m], 0x00, sizeof(unsigned long) * (n - m));
117 }
118
119
120
121 if (data->size < data->old_size) {
122 m = size % (sizeof(unsigned long) * 8);
123 if (m) {
124 unsigned long mask = (1ULL << m) - 1;
125 data->bits[n-1] &= mask;
126 }
127 }
128
129 hbitmap_truncate(data->hb, size);
130}
131
132static void hbitmap_test_teardown(TestHBitmapData *data,
133 const void *unused)
134{
135 if (data->hb) {
136 hbitmap_free(data->hb);
137 data->hb = NULL;
138 }
139 g_free(data->bits);
140 data->bits = NULL;
141}
142
143
144
145
146static void hbitmap_test_set(TestHBitmapData *data,
147 uint64_t first, uint64_t count)
148{
149 hbitmap_set(data->hb, first, count);
150 while (count-- != 0) {
151 size_t pos = first >> LOG_BITS_PER_LONG;
152 int bit = first & (BITS_PER_LONG - 1);
153 first++;
154
155 data->bits[pos] |= 1UL << bit;
156 }
157
158 if (data->granularity == 0) {
159 hbitmap_test_check(data, 0);
160 }
161}
162
163
164
165static void hbitmap_test_reset(TestHBitmapData *data,
166 uint64_t first, uint64_t count)
167{
168 hbitmap_reset(data->hb, first, count);
169 while (count-- != 0) {
170 size_t pos = first >> LOG_BITS_PER_LONG;
171 int bit = first & (BITS_PER_LONG - 1);
172 first++;
173
174 data->bits[pos] &= ~(1UL << bit);
175 }
176
177 if (data->granularity == 0) {
178 hbitmap_test_check(data, 0);
179 }
180}
181
182static void hbitmap_test_reset_all(TestHBitmapData *data)
183{
184 size_t n;
185
186 hbitmap_reset_all(data->hb);
187
188 n = DIV_ROUND_UP(data->size, BITS_PER_LONG);
189 if (n == 0) {
190 n = 1;
191 }
192 memset(data->bits, 0, n * sizeof(unsigned long));
193
194 if (data->granularity == 0) {
195 hbitmap_test_check(data, 0);
196 }
197}
198
199static void hbitmap_test_check_get(TestHBitmapData *data)
200{
201 uint64_t count = 0;
202 uint64_t i;
203
204 for (i = 0; i < data->size; i++) {
205 size_t pos = i >> LOG_BITS_PER_LONG;
206 int bit = i & (BITS_PER_LONG - 1);
207 unsigned long val = data->bits[pos] & (1UL << bit);
208 count += hbitmap_get(data->hb, i);
209 g_assert_cmpint(hbitmap_get(data->hb, i), ==, val != 0);
210 }
211 g_assert_cmpint(count, ==, hbitmap_count(data->hb));
212}
213
214static void test_hbitmap_zero(TestHBitmapData *data,
215 const void *unused)
216{
217 hbitmap_test_init(data, 0, 0);
218}
219
220static void test_hbitmap_unaligned(TestHBitmapData *data,
221 const void *unused)
222{
223 hbitmap_test_init(data, L3 + 23, 0);
224 hbitmap_test_set(data, 0, 1);
225 hbitmap_test_set(data, L3 + 22, 1);
226}
227
228static void test_hbitmap_iter_empty(TestHBitmapData *data,
229 const void *unused)
230{
231 hbitmap_test_init(data, L1, 0);
232}
233
234static void test_hbitmap_iter_partial(TestHBitmapData *data,
235 const void *unused)
236{
237 hbitmap_test_init(data, L3, 0);
238 hbitmap_test_set(data, 0, L3);
239 hbitmap_test_check(data, 1);
240 hbitmap_test_check(data, L1 - 1);
241 hbitmap_test_check(data, L1);
242 hbitmap_test_check(data, L1 * 2 - 1);
243 hbitmap_test_check(data, L2 - 1);
244 hbitmap_test_check(data, L2);
245 hbitmap_test_check(data, L2 + 1);
246 hbitmap_test_check(data, L2 + L1);
247 hbitmap_test_check(data, L2 + L1 * 2 - 1);
248 hbitmap_test_check(data, L2 * 2 - 1);
249 hbitmap_test_check(data, L2 * 2);
250 hbitmap_test_check(data, L2 * 2 + 1);
251 hbitmap_test_check(data, L2 * 2 + L1);
252 hbitmap_test_check(data, L2 * 2 + L1 * 2 - 1);
253 hbitmap_test_check(data, L3 / 2);
254}
255
256static void test_hbitmap_set_all(TestHBitmapData *data,
257 const void *unused)
258{
259 hbitmap_test_init(data, L3, 0);
260 hbitmap_test_set(data, 0, L3);
261}
262
263static void test_hbitmap_get_all(TestHBitmapData *data,
264 const void *unused)
265{
266 hbitmap_test_init(data, L3, 0);
267 hbitmap_test_set(data, 0, L3);
268 hbitmap_test_check_get(data);
269}
270
271static void test_hbitmap_get_some(TestHBitmapData *data,
272 const void *unused)
273{
274 hbitmap_test_init(data, 2 * L2, 0);
275 hbitmap_test_set(data, 10, 1);
276 hbitmap_test_check_get(data);
277 hbitmap_test_set(data, L1 - 1, 1);
278 hbitmap_test_check_get(data);
279 hbitmap_test_set(data, L1, 1);
280 hbitmap_test_check_get(data);
281 hbitmap_test_set(data, L2 - 1, 1);
282 hbitmap_test_check_get(data);
283 hbitmap_test_set(data, L2, 1);
284 hbitmap_test_check_get(data);
285}
286
287static void test_hbitmap_set_one(TestHBitmapData *data,
288 const void *unused)
289{
290 hbitmap_test_init(data, 2 * L2, 0);
291 hbitmap_test_set(data, 10, 1);
292 hbitmap_test_set(data, L1 - 1, 1);
293 hbitmap_test_set(data, L1, 1);
294 hbitmap_test_set(data, L2 - 1, 1);
295 hbitmap_test_set(data, L2, 1);
296}
297
298static void test_hbitmap_set_two_elem(TestHBitmapData *data,
299 const void *unused)
300{
301 hbitmap_test_init(data, 2 * L2, 0);
302 hbitmap_test_set(data, L1 - 1, 2);
303 hbitmap_test_set(data, L1 * 2 - 1, 4);
304 hbitmap_test_set(data, L1 * 4, L1 + 1);
305 hbitmap_test_set(data, L1 * 8 - 1, L1 + 1);
306 hbitmap_test_set(data, L2 - 1, 2);
307 hbitmap_test_set(data, L2 + L1 - 1, 8);
308 hbitmap_test_set(data, L2 + L1 * 4, L1 + 1);
309 hbitmap_test_set(data, L2 + L1 * 8 - 1, L1 + 1);
310}
311
312static void test_hbitmap_set(TestHBitmapData *data,
313 const void *unused)
314{
315 hbitmap_test_init(data, L3 * 2, 0);
316 hbitmap_test_set(data, L1 - 1, L1 + 2);
317 hbitmap_test_set(data, L1 * 3 - 1, L1 + 2);
318 hbitmap_test_set(data, L1 * 5, L1 * 2 + 1);
319 hbitmap_test_set(data, L1 * 8 - 1, L1 * 2 + 1);
320 hbitmap_test_set(data, L2 - 1, L1 + 2);
321 hbitmap_test_set(data, L2 + L1 * 2 - 1, L1 + 2);
322 hbitmap_test_set(data, L2 + L1 * 4, L1 * 2 + 1);
323 hbitmap_test_set(data, L2 + L1 * 7 - 1, L1 * 2 + 1);
324 hbitmap_test_set(data, L2 * 2 - 1, L3 * 2 - L2 * 2);
325}
326
327static void test_hbitmap_set_twice(TestHBitmapData *data,
328 const void *unused)
329{
330 hbitmap_test_init(data, L1 * 3, 0);
331 hbitmap_test_set(data, 0, L1 * 3);
332 hbitmap_test_set(data, L1, 1);
333}
334
335static void test_hbitmap_set_overlap(TestHBitmapData *data,
336 const void *unused)
337{
338 hbitmap_test_init(data, L3 * 2, 0);
339 hbitmap_test_set(data, L1 - 1, L1 + 2);
340 hbitmap_test_set(data, L1 * 2 - 1, L1 * 2 + 2);
341 hbitmap_test_set(data, 0, L1 * 3);
342 hbitmap_test_set(data, L1 * 8 - 1, L2);
343 hbitmap_test_set(data, L2, L1);
344 hbitmap_test_set(data, L2 - L1 - 1, L1 * 8 + 2);
345 hbitmap_test_set(data, L2, L3 - L2 + 1);
346 hbitmap_test_set(data, L3 - L1, L1 * 3);
347 hbitmap_test_set(data, L3 - 1, 3);
348 hbitmap_test_set(data, L3 - 1, L2);
349}
350
351static void test_hbitmap_reset_empty(TestHBitmapData *data,
352 const void *unused)
353{
354 hbitmap_test_init(data, L3, 0);
355 hbitmap_test_reset(data, 0, L3);
356}
357
358static void test_hbitmap_reset(TestHBitmapData *data,
359 const void *unused)
360{
361 hbitmap_test_init(data, L3 * 2, 0);
362 hbitmap_test_set(data, L1 - 1, L1 + 2);
363 hbitmap_test_reset(data, L1 * 2 - 1, L1 * 2 + 2);
364 hbitmap_test_set(data, 0, L1 * 3);
365 hbitmap_test_reset(data, L1 * 8 - 1, L2);
366 hbitmap_test_set(data, L2, L1);
367 hbitmap_test_reset(data, L2 - L1 - 1, L1 * 8 + 2);
368 hbitmap_test_set(data, L2, L3 - L2 + 1);
369 hbitmap_test_reset(data, L3 - L1, L1 * 3);
370 hbitmap_test_set(data, L3 - 1, 3);
371 hbitmap_test_reset(data, L3 - 1, L2);
372 hbitmap_test_set(data, 0, L3 * 2);
373 hbitmap_test_reset(data, 0, L1);
374 hbitmap_test_reset(data, 0, L2);
375 hbitmap_test_reset(data, L3, L3);
376 hbitmap_test_set(data, L3 / 2, L3);
377}
378
379static void test_hbitmap_reset_all(TestHBitmapData *data,
380 const void *unused)
381{
382 hbitmap_test_init(data, L3 * 2, 0);
383 hbitmap_test_set(data, L1 - 1, L1 + 2);
384 hbitmap_test_reset_all(data);
385 hbitmap_test_set(data, 0, L1 * 3);
386 hbitmap_test_reset_all(data);
387 hbitmap_test_set(data, L2, L1);
388 hbitmap_test_reset_all(data);
389 hbitmap_test_set(data, L2, L3 - L2 + 1);
390 hbitmap_test_reset_all(data);
391 hbitmap_test_set(data, L3 - 1, 3);
392 hbitmap_test_reset_all(data);
393 hbitmap_test_set(data, 0, L3 * 2);
394 hbitmap_test_reset_all(data);
395 hbitmap_test_set(data, L3 / 2, L3);
396 hbitmap_test_reset_all(data);
397}
398
399static void test_hbitmap_granularity(TestHBitmapData *data,
400 const void *unused)
401{
402
403 hbitmap_test_init(data, L1, 1);
404 hbitmap_test_set(data, 0, 1);
405 g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
406 hbitmap_test_check(data, 0);
407 hbitmap_test_set(data, 2, 1);
408 g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
409 hbitmap_test_check(data, 0);
410 hbitmap_test_set(data, 0, 3);
411 g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
412 hbitmap_test_reset(data, 0, 1);
413 g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
414}
415
416static void test_hbitmap_iter_granularity(TestHBitmapData *data,
417 const void *unused)
418{
419 HBitmapIter hbi;
420
421
422 hbitmap_test_init(data, 131072 << 7, 7);
423 hbitmap_iter_init(&hbi, data->hb, 0);
424 g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
425
426 hbitmap_test_set(data, ((L2 + L1 + 1) << 7) + 8, 8);
427 hbitmap_iter_init(&hbi, data->hb, 0);
428 g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
429 g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
430
431 hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
432 g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
433
434 hbitmap_test_set(data, (131072 << 7) - 8, 8);
435 hbitmap_iter_init(&hbi, data->hb, 0);
436 g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
437 g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
438 g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
439
440 hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
441 g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
442 g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
443}
444
445static void hbitmap_test_set_boundary_bits(TestHBitmapData *data, ssize_t diff)
446{
447 size_t size = data->size;
448
449
450 hbitmap_test_set(data, 0, 1);
451 if (diff < 0) {
452
453 hbitmap_test_set(data, size + diff - 1, 1);
454
455
456 hbitmap_test_set(data, size + diff, 1);
457 }
458
459 hbitmap_test_set(data, size - 1, 1);
460 if (data->granularity == 0) {
461 hbitmap_test_check_get(data);
462 }
463}
464
465static void hbitmap_test_check_boundary_bits(TestHBitmapData *data)
466{
467 size_t size = MIN(data->size, data->old_size);
468
469 if (data->granularity == 0) {
470 hbitmap_test_check_get(data);
471 hbitmap_test_check(data, 0);
472 } else {
473
474
475
476
477
478
479
480
481 g_assert(hbitmap_get(data->hb, 0));
482 g_assert(hbitmap_get(data->hb, size - 1));
483 g_assert_cmpint(2 << data->granularity, ==, hbitmap_count(data->hb));
484 }
485}
486
487
488static void hbitmap_test_truncate(TestHBitmapData *data,
489 size_t size,
490 ssize_t diff,
491 int granularity)
492{
493 hbitmap_test_init(data, size, granularity);
494 hbitmap_test_set_boundary_bits(data, diff);
495 hbitmap_test_truncate_impl(data, size + diff);
496 hbitmap_test_check_boundary_bits(data);
497}
498
499static void test_hbitmap_truncate_nop(TestHBitmapData *data,
500 const void *unused)
501{
502 hbitmap_test_truncate(data, L2, 0, 0);
503}
504
505
506
507
508
509static void test_hbitmap_truncate_grow_negligible(TestHBitmapData *data,
510 const void *unused)
511{
512 size_t size = L2 - 1;
513 size_t diff = 1;
514 int granularity = 1;
515
516 hbitmap_test_truncate(data, size, diff, granularity);
517}
518
519
520
521
522
523static void test_hbitmap_truncate_shrink_negligible(TestHBitmapData *data,
524 const void *unused)
525{
526 size_t size = L2;
527 ssize_t diff = -1;
528 int granularity = 1;
529
530 hbitmap_test_truncate(data, size, diff, granularity);
531}
532
533
534
535
536
537static void test_hbitmap_truncate_grow_tiny(TestHBitmapData *data,
538 const void *unused)
539{
540 size_t size = L2 - 2;
541 ssize_t diff = 1;
542 int granularity = 1;
543
544 hbitmap_test_truncate(data, size, diff, granularity);
545}
546
547
548
549
550
551static void test_hbitmap_truncate_shrink_tiny(TestHBitmapData *data,
552 const void *unused)
553{
554 size_t size = L2 - 1;
555 ssize_t diff = -1;
556 int granularity = 1;
557
558 hbitmap_test_truncate(data, size, diff, granularity);
559}
560
561
562
563
564
565static void test_hbitmap_truncate_grow_small(TestHBitmapData *data,
566 const void *unused)
567{
568 size_t size = L2 + 1;
569 size_t diff = sizeof(long) / 2;
570
571 hbitmap_test_truncate(data, size, diff, 0);
572}
573
574
575
576
577
578static void test_hbitmap_truncate_shrink_small(TestHBitmapData *data,
579 const void *unused)
580{
581 size_t size = L2;
582 size_t diff = sizeof(long) / 2;
583
584 hbitmap_test_truncate(data, size, -diff, 0);
585}
586
587
588
589
590
591static void test_hbitmap_truncate_grow_medium(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_medium(TestHBitmapData *data,
605 const void *unused)
606{
607 size_t size = L2 + 1;
608 size_t diff = sizeof(long) / 2;
609
610 hbitmap_test_truncate(data, size, -diff, 0);
611}
612
613
614
615
616static void test_hbitmap_truncate_grow_large(TestHBitmapData *data,
617 const void *unused)
618{
619 size_t size = L2;
620 size_t diff = 8 * sizeof(long);
621
622 hbitmap_test_truncate(data, size, diff, 0);
623}
624
625
626
627
628static void test_hbitmap_truncate_shrink_large(TestHBitmapData *data,
629 const void *unused)
630{
631 size_t size = L2;
632 size_t diff = 8 * sizeof(long);
633
634 hbitmap_test_truncate(data, size, -diff, 0);
635}
636
637static void hbitmap_test_add(const char *testpath,
638 void (*test_func)(TestHBitmapData *data, const void *user_data))
639{
640 g_test_add(testpath, TestHBitmapData, NULL, NULL, test_func,
641 hbitmap_test_teardown);
642}
643
644int main(int argc, char **argv)
645{
646 g_test_init(&argc, &argv, NULL);
647 hbitmap_test_add("/hbitmap/size/0", test_hbitmap_zero);
648 hbitmap_test_add("/hbitmap/size/unaligned", test_hbitmap_unaligned);
649 hbitmap_test_add("/hbitmap/iter/empty", test_hbitmap_iter_empty);
650 hbitmap_test_add("/hbitmap/iter/partial", test_hbitmap_iter_partial);
651 hbitmap_test_add("/hbitmap/iter/granularity", test_hbitmap_iter_granularity);
652 hbitmap_test_add("/hbitmap/get/all", test_hbitmap_get_all);
653 hbitmap_test_add("/hbitmap/get/some", test_hbitmap_get_some);
654 hbitmap_test_add("/hbitmap/set/all", test_hbitmap_set_all);
655 hbitmap_test_add("/hbitmap/set/one", test_hbitmap_set_one);
656 hbitmap_test_add("/hbitmap/set/two-elem", test_hbitmap_set_two_elem);
657 hbitmap_test_add("/hbitmap/set/general", test_hbitmap_set);
658 hbitmap_test_add("/hbitmap/set/twice", test_hbitmap_set_twice);
659 hbitmap_test_add("/hbitmap/set/overlap", test_hbitmap_set_overlap);
660 hbitmap_test_add("/hbitmap/reset/empty", test_hbitmap_reset_empty);
661 hbitmap_test_add("/hbitmap/reset/general", test_hbitmap_reset);
662 hbitmap_test_add("/hbitmap/reset/all", test_hbitmap_reset_all);
663 hbitmap_test_add("/hbitmap/granularity", test_hbitmap_granularity);
664
665 hbitmap_test_add("/hbitmap/truncate/nop", test_hbitmap_truncate_nop);
666 hbitmap_test_add("/hbitmap/truncate/grow/negligible",
667 test_hbitmap_truncate_grow_negligible);
668 hbitmap_test_add("/hbitmap/truncate/shrink/negligible",
669 test_hbitmap_truncate_shrink_negligible);
670 hbitmap_test_add("/hbitmap/truncate/grow/tiny",
671 test_hbitmap_truncate_grow_tiny);
672 hbitmap_test_add("/hbitmap/truncate/shrink/tiny",
673 test_hbitmap_truncate_shrink_tiny);
674 hbitmap_test_add("/hbitmap/truncate/grow/small",
675 test_hbitmap_truncate_grow_small);
676 hbitmap_test_add("/hbitmap/truncate/shrink/small",
677 test_hbitmap_truncate_shrink_small);
678 hbitmap_test_add("/hbitmap/truncate/grow/medium",
679 test_hbitmap_truncate_grow_medium);
680 hbitmap_test_add("/hbitmap/truncate/shrink/medium",
681 test_hbitmap_truncate_shrink_medium);
682 hbitmap_test_add("/hbitmap/truncate/grow/large",
683 test_hbitmap_truncate_grow_large);
684 hbitmap_test_add("/hbitmap/truncate/shrink/large",
685 test_hbitmap_truncate_shrink_large);
686 g_test_run();
687
688 return 0;
689}
690