Merge remote-tracking branch 'remotes/stefanberger/tags/pull-tpm-2021-01-25-1' into...
[qemu.git] / tests / test-hbitmap.c
1 /*
2 * Hierarchical bitmap unit-tests.
3 *
4 * Copyright (C) 2012 Red Hat Inc.
5 *
6 * Author: Paolo Bonzini <pbonzini@redhat.com>
7 *
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.
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
23 typedef struct TestHBitmapData {
24 HBitmap *hb;
25 unsigned long *bits;
26 size_t size;
27 size_t old_size;
28 int granularity;
29 } TestHBitmapData;
30
31
32 /* Check that the HBitmap and the shadow bitmap contain the same data,
33 * ignoring the same "first" bits.
34 */
35 static void hbitmap_test_check(TestHBitmapData *data,
36 uint64_t first)
37 {
38 uint64_t count = 0;
39 size_t pos;
40 int bit;
41 HBitmapIter hbi;
42 int64_t i, next;
43
44 hbitmap_iter_init(&hbi, data->hb, first);
45
46 i = first;
47 for (;;) {
48 next = hbitmap_iter_next(&hbi);
49 if (next < 0) {
50 next = data->size;
51 }
52
53 while (i < next) {
54 pos = i >> LOG_BITS_PER_LONG;
55 bit = i & (BITS_PER_LONG - 1);
56 i++;
57 g_assert_cmpint(data->bits[pos] & (1UL << bit), ==, 0);
58 }
59
60 if (next == data->size) {
61 break;
62 }
63
64 pos = i >> LOG_BITS_PER_LONG;
65 bit = i & (BITS_PER_LONG - 1);
66 i++;
67 count++;
68 g_assert_cmpint(data->bits[pos] & (1UL << bit), !=, 0);
69 }
70
71 if (first == 0) {
72 g_assert_cmpint(count << data->granularity, ==, hbitmap_count(data->hb));
73 }
74 }
75
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)
80 {
81 size_t n;
82 data->hb = hbitmap_alloc(size, granularity);
83
84 n = DIV_ROUND_UP(size, BITS_PER_LONG);
85 if (n == 0) {
86 n = 1;
87 }
88 data->bits = g_new0(unsigned long, n);
89 data->size = size;
90 data->granularity = granularity;
91 if (size) {
92 hbitmap_test_check(data, 0);
93 }
94 }
95
96 static inline size_t hbitmap_test_array_size(size_t bits)
97 {
98 size_t n = DIV_ROUND_UP(bits, BITS_PER_LONG);
99 return n ? n : 1;
100 }
101
102 static void hbitmap_test_truncate_impl(TestHBitmapData *data,
103 size_t size)
104 {
105 size_t n;
106 size_t m;
107 data->old_size = data->size;
108 data->size = size;
109
110 if (data->size == data->old_size) {
111 return;
112 }
113
114 n = hbitmap_test_array_size(size);
115 m = hbitmap_test_array_size(data->old_size);
116 data->bits = g_realloc(data->bits, sizeof(unsigned long) * n);
117 if (n > m) {
118 memset(&data->bits[m], 0x00, sizeof(unsigned long) * (n - m));
119 }
120
121 /* If we shrink to an uneven multiple of sizeof(unsigned long),
122 * scrub the leftover memory. */
123 if (data->size < data->old_size) {
124 m = size % (sizeof(unsigned long) * 8);
125 if (m) {
126 unsigned long mask = (1ULL << m) - 1;
127 data->bits[n-1] &= mask;
128 }
129 }
130
131 hbitmap_truncate(data->hb, size);
132 }
133
134 static void hbitmap_test_teardown(TestHBitmapData *data,
135 const void *unused)
136 {
137 if (data->hb) {
138 hbitmap_free(data->hb);
139 data->hb = NULL;
140 }
141 g_free(data->bits);
142 data->bits = NULL;
143 }
144
145 /* Set a range in the HBitmap and in the shadow "simple" bitmap.
146 * The two bitmaps are then tested against each other.
147 */
148 static void hbitmap_test_set(TestHBitmapData *data,
149 uint64_t first, uint64_t count)
150 {
151 hbitmap_set(data->hb, first, count);
152 while (count-- != 0) {
153 size_t pos = first >> LOG_BITS_PER_LONG;
154 int bit = first & (BITS_PER_LONG - 1);
155 first++;
156
157 data->bits[pos] |= 1UL << bit;
158 }
159
160 if (data->granularity == 0) {
161 hbitmap_test_check(data, 0);
162 }
163 }
164
165 /* Reset a range in the HBitmap and in the shadow "simple" bitmap.
166 */
167 static void hbitmap_test_reset(TestHBitmapData *data,
168 uint64_t first, uint64_t count)
169 {
170 hbitmap_reset(data->hb, first, count);
171 while (count-- != 0) {
172 size_t pos = first >> LOG_BITS_PER_LONG;
173 int bit = first & (BITS_PER_LONG - 1);
174 first++;
175
176 data->bits[pos] &= ~(1UL << bit);
177 }
178
179 if (data->granularity == 0) {
180 hbitmap_test_check(data, 0);
181 }
182 }
183
184 static void hbitmap_test_reset_all(TestHBitmapData *data)
185 {
186 size_t n;
187
188 hbitmap_reset_all(data->hb);
189
190 n = DIV_ROUND_UP(data->size, BITS_PER_LONG);
191 if (n == 0) {
192 n = 1;
193 }
194 memset(data->bits, 0, n * sizeof(unsigned long));
195
196 if (data->granularity == 0) {
197 hbitmap_test_check(data, 0);
198 }
199 }
200
201 static void hbitmap_test_check_get(TestHBitmapData *data)
202 {
203 uint64_t count = 0;
204 uint64_t i;
205
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);
212 }
213 g_assert_cmpint(count, ==, hbitmap_count(data->hb));
214 }
215
216 static void test_hbitmap_zero(TestHBitmapData *data,
217 const void *unused)
218 {
219 hbitmap_test_init(data, 0, 0);
220 }
221
222 static void test_hbitmap_unaligned(TestHBitmapData *data,
223 const void *unused)
224 {
225 hbitmap_test_init(data, L3 + 23, 0);
226 hbitmap_test_set(data, 0, 1);
227 hbitmap_test_set(data, L3 + 22, 1);
228 }
229
230 static void test_hbitmap_iter_empty(TestHBitmapData *data,
231 const void *unused)
232 {
233 hbitmap_test_init(data, L1, 0);
234 }
235
236 static void test_hbitmap_iter_partial(TestHBitmapData *data,
237 const void *unused)
238 {
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);
256 }
257
258 static void test_hbitmap_set_all(TestHBitmapData *data,
259 const void *unused)
260 {
261 hbitmap_test_init(data, L3, 0);
262 hbitmap_test_set(data, 0, L3);
263 }
264
265 static void test_hbitmap_get_all(TestHBitmapData *data,
266 const void *unused)
267 {
268 hbitmap_test_init(data, L3, 0);
269 hbitmap_test_set(data, 0, L3);
270 hbitmap_test_check_get(data);
271 }
272
273 static void test_hbitmap_get_some(TestHBitmapData *data,
274 const void *unused)
275 {
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);
287 }
288
289 static void test_hbitmap_set_one(TestHBitmapData *data,
290 const void *unused)
291 {
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);
298 }
299
300 static void test_hbitmap_set_two_elem(TestHBitmapData *data,
301 const void *unused)
302 {
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);
312 }
313
314 static void test_hbitmap_set(TestHBitmapData *data,
315 const void *unused)
316 {
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);
327 }
328
329 static void test_hbitmap_set_twice(TestHBitmapData *data,
330 const void *unused)
331 {
332 hbitmap_test_init(data, L1 * 3, 0);
333 hbitmap_test_set(data, 0, L1 * 3);
334 hbitmap_test_set(data, L1, 1);
335 }
336
337 static void test_hbitmap_set_overlap(TestHBitmapData *data,
338 const void *unused)
339 {
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);
351 }
352
353 static void test_hbitmap_reset_empty(TestHBitmapData *data,
354 const void *unused)
355 {
356 hbitmap_test_init(data, L3, 0);
357 hbitmap_test_reset(data, 0, L3);
358 }
359
360 static void test_hbitmap_reset(TestHBitmapData *data,
361 const void *unused)
362 {
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);
379 }
380
381 static void test_hbitmap_reset_all(TestHBitmapData *data,
382 const void *unused)
383 {
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);
399 }
400
401 static void test_hbitmap_granularity(TestHBitmapData *data,
402 const void *unused)
403 {
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);
416 }
417
418 static void test_hbitmap_iter_granularity(TestHBitmapData *data,
419 const void *unused)
420 {
421 HBitmapIter hbi;
422
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);
427
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);
432
433 hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
434 g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
435
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);
441
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);
445 }
446
447 static void hbitmap_test_set_boundary_bits(TestHBitmapData *data, ssize_t diff)
448 {
449 size_t size = data->size;
450
451 /* First bit */
452 hbitmap_test_set(data, 0, 1);
453 if (diff < 0) {
454 /* Last bit in new, shortened map */
455 hbitmap_test_set(data, size + diff - 1, 1);
456
457 /* First bit to be truncated away */
458 hbitmap_test_set(data, size + diff, 1);
459 }
460 /* Last bit */
461 hbitmap_test_set(data, size - 1, 1);
462 if (data->granularity == 0) {
463 hbitmap_test_check_get(data);
464 }
465 }
466
467 static void hbitmap_test_check_boundary_bits(TestHBitmapData *data)
468 {
469 size_t size = MIN(data->size, data->old_size);
470
471 if (data->granularity == 0) {
472 hbitmap_test_check_get(data);
473 hbitmap_test_check(data, 0);
474 } else {
475 /* If a granularity was set, note that every distinct
476 * (bit >> granularity) value that was set will increase
477 * the bit pop count by 2^granularity, not just 1.
478 *
479 * The hbitmap_test_check facility does not currently tolerate
480 * non-zero granularities, so test the boundaries and the population
481 * count manually.
482 */
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));
486 }
487 }
488
489 /* Generic truncate test. */
490 static void hbitmap_test_truncate(TestHBitmapData *data,
491 size_t size,
492 ssize_t diff,
493 int granularity)
494 {
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);
499 }
500
501 static void test_hbitmap_truncate_nop(TestHBitmapData *data,
502 const void *unused)
503 {
504 hbitmap_test_truncate(data, L2, 0, 0);
505 }
506
507 /**
508 * Grow by an amount smaller than the granularity, without crossing
509 * a granularity alignment boundary. Effectively a NOP.
510 */
511 static void test_hbitmap_truncate_grow_negligible(TestHBitmapData *data,
512 const void *unused)
513 {
514 size_t size = L2 - 1;
515 size_t diff = 1;
516 int granularity = 1;
517
518 hbitmap_test_truncate(data, size, diff, granularity);
519 }
520
521 /**
522 * Shrink by an amount smaller than the granularity, without crossing
523 * a granularity alignment boundary. Effectively a NOP.
524 */
525 static void test_hbitmap_truncate_shrink_negligible(TestHBitmapData *data,
526 const void *unused)
527 {
528 size_t size = L2;
529 ssize_t diff = -1;
530 int granularity = 1;
531
532 hbitmap_test_truncate(data, size, diff, granularity);
533 }
534
535 /**
536 * Grow by an amount smaller than the granularity, but crossing over
537 * a granularity alignment boundary.
538 */
539 static void test_hbitmap_truncate_grow_tiny(TestHBitmapData *data,
540 const void *unused)
541 {
542 size_t size = L2 - 2;
543 ssize_t diff = 1;
544 int granularity = 1;
545
546 hbitmap_test_truncate(data, size, diff, granularity);
547 }
548
549 /**
550 * Shrink by an amount smaller than the granularity, but crossing over
551 * a granularity alignment boundary.
552 */
553 static void test_hbitmap_truncate_shrink_tiny(TestHBitmapData *data,
554 const void *unused)
555 {
556 size_t size = L2 - 1;
557 ssize_t diff = -1;
558 int granularity = 1;
559
560 hbitmap_test_truncate(data, size, diff, granularity);
561 }
562
563 /**
564 * Grow by an amount smaller than sizeof(long), and not crossing over
565 * a sizeof(long) alignment boundary.
566 */
567 static void test_hbitmap_truncate_grow_small(TestHBitmapData *data,
568 const void *unused)
569 {
570 size_t size = L2 + 1;
571 size_t diff = sizeof(long) / 2;
572
573 hbitmap_test_truncate(data, size, diff, 0);
574 }
575
576 /**
577 * Shrink by an amount smaller than sizeof(long), and not crossing over
578 * a sizeof(long) alignment boundary.
579 */
580 static void test_hbitmap_truncate_shrink_small(TestHBitmapData *data,
581 const void *unused)
582 {
583 size_t size = L2;
584 size_t diff = sizeof(long) / 2;
585
586 hbitmap_test_truncate(data, size, -diff, 0);
587 }
588
589 /**
590 * Grow by an amount smaller than sizeof(long), while crossing over
591 * a sizeof(long) alignment boundary.
592 */
593 static void test_hbitmap_truncate_grow_medium(TestHBitmapData *data,
594 const void *unused)
595 {
596 size_t size = L2 - 1;
597 size_t diff = sizeof(long) / 2;
598
599 hbitmap_test_truncate(data, size, diff, 0);
600 }
601
602 /**
603 * Shrink by an amount smaller than sizeof(long), while crossing over
604 * a sizeof(long) alignment boundary.
605 */
606 static void test_hbitmap_truncate_shrink_medium(TestHBitmapData *data,
607 const void *unused)
608 {
609 size_t size = L2 + 1;
610 size_t diff = sizeof(long) / 2;
611
612 hbitmap_test_truncate(data, size, -diff, 0);
613 }
614
615 /**
616 * Grow by an amount larger than sizeof(long).
617 */
618 static void test_hbitmap_truncate_grow_large(TestHBitmapData *data,
619 const void *unused)
620 {
621 size_t size = L2;
622 size_t diff = 8 * sizeof(long);
623
624 hbitmap_test_truncate(data, size, diff, 0);
625 }
626
627 /**
628 * Shrink by an amount larger than sizeof(long).
629 */
630 static void test_hbitmap_truncate_shrink_large(TestHBitmapData *data,
631 const void *unused)
632 {
633 size_t size = L2;
634 size_t diff = 8 * sizeof(long);
635
636 hbitmap_test_truncate(data, size, -diff, 0);
637 }
638
639 static void test_hbitmap_serialize_align(TestHBitmapData *data,
640 const void *unused)
641 {
642 int r;
643
644 hbitmap_test_init(data, L3 * 2, 3);
645 g_assert(hbitmap_is_serializable(data->hb));
646
647 r = hbitmap_serialization_align(data->hb);
648 g_assert_cmpint(r, ==, 64 << 3);
649 }
650
651 static void hbitmap_test_serialize_range(TestHBitmapData *data,
652 uint8_t *buf, size_t buf_size,
653 uint64_t pos, uint64_t count)
654 {
655 size_t i;
656 unsigned long *el = (unsigned long *)buf;
657
658 assert(hbitmap_granularity(data->hb) == 0);
659 hbitmap_reset_all(data->hb);
660 memset(buf, 0, buf_size);
661 if (count) {
662 hbitmap_set(data->hb, pos, count);
663 }
664
665 g_assert(hbitmap_is_serializable(data->hb));
666 hbitmap_serialize_part(data->hb, buf, 0, data->size);
667
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]));
671 }
672
673 for (i = 0; i < data->size; i++) {
674 int is_set = test_bit(i, (unsigned long *)buf);
675 if (i >= pos && i < pos + count) {
676 g_assert(is_set);
677 } else {
678 g_assert(!is_set);
679 }
680 }
681
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);
686
687 g_assert(hbitmap_is_serializable(data->hb));
688 hbitmap_deserialize_part(data->hb, buf, 0, data->size, true);
689
690 for (i = 0; i < data->size; i++) {
691 int is_set = hbitmap_get(data->hb, i);
692 if (i >= pos && i < pos + count) {
693 g_assert(is_set);
694 } else {
695 g_assert(!is_set);
696 }
697 }
698 }
699
700 static void test_hbitmap_serialize_basic(TestHBitmapData *data,
701 const void *unused)
702 {
703 int i, j;
704 size_t buf_size;
705 uint8_t *buf;
706 uint64_t positions[] = { 0, 1, L1 - 1, L1, L2 - 1, L2, L2 + 1, L3 - 1 };
707 int num_positions = ARRAY_SIZE(positions);
708
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);
713
714 for (i = 0; i < num_positions; i++) {
715 for (j = 0; j < num_positions; j++) {
716 hbitmap_test_serialize_range(data, buf, buf_size,
717 positions[i],
718 MIN(positions[j], L3 - positions[i]));
719 }
720 }
721
722 g_free(buf);
723 }
724
725 static void test_hbitmap_serialize_part(TestHBitmapData *data,
726 const void *unused)
727 {
728 int i, j, k;
729 size_t buf_size;
730 uint8_t *buf;
731 uint64_t positions[] = { 0, 1, L1 - 1, L1, L2 - 1, L2, L2 + 1, L3 - 1 };
732 int num_positions = ARRAY_SIZE(positions);
733
734 hbitmap_test_init(data, L3, 0);
735 buf_size = L2;
736 buf = g_malloc0(buf_size);
737
738 for (i = 0; i < num_positions; i++) {
739 hbitmap_set(data->hb, positions[i], 1);
740 }
741
742 g_assert(hbitmap_is_serializable(data->hb));
743
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]));
749 }
750
751 for (j = 0; j < buf_size; j++) {
752 bool should_set = false;
753 for (k = 0; k < num_positions; k++) {
754 if (positions[k] == j + i) {
755 should_set = true;
756 break;
757 }
758 }
759 g_assert_cmpint(should_set, ==, test_bit(j, (unsigned long *)buf));
760 }
761 }
762
763 g_free(buf);
764 }
765
766 static void test_hbitmap_serialize_zeroes(TestHBitmapData *data,
767 const void *unused)
768 {
769 int i;
770 HBitmapIter iter;
771 int64_t next;
772 uint64_t min_l1 = MAX(L1, 64);
773 uint64_t positions[] = { 0, min_l1, L2, L3 - min_l1};
774 int num_positions = ARRAY_SIZE(positions);
775
776 hbitmap_test_init(data, L3, 0);
777
778 for (i = 0; i < num_positions; i++) {
779 hbitmap_set(data->hb, positions[i], L1);
780 }
781
782 g_assert(hbitmap_is_serializable(data->hb));
783
784 for (i = 0; i < num_positions; i++) {
785 hbitmap_deserialize_zeroes(data->hb, positions[i], min_l1, true);
786 hbitmap_iter_init(&iter, data->hb, 0);
787 next = hbitmap_iter_next(&iter);
788 if (i == num_positions - 1) {
789 g_assert_cmpint(next, ==, -1);
790 } else {
791 g_assert_cmpint(next, ==, positions[i + 1]);
792 }
793 }
794 }
795
796 static void hbitmap_test_add(const char *testpath,
797 void (*test_func)(TestHBitmapData *data, const void *user_data))
798 {
799 g_test_add(testpath, TestHBitmapData, NULL, NULL, test_func,
800 hbitmap_test_teardown);
801 }
802
803 static void test_hbitmap_iter_and_reset(TestHBitmapData *data,
804 const void *unused)
805 {
806 HBitmapIter hbi;
807
808 hbitmap_test_init(data, L1 * 2, 0);
809 hbitmap_set(data->hb, 0, data->size);
810
811 hbitmap_iter_init(&hbi, data->hb, BITS_PER_LONG - 1);
812
813 hbitmap_iter_next(&hbi);
814
815 hbitmap_reset_all(data->hb);
816 hbitmap_iter_next(&hbi);
817 }
818
819 static void test_hbitmap_next_x_check_range(TestHBitmapData *data,
820 int64_t start,
821 int64_t count)
822 {
823 int64_t next_zero = hbitmap_next_zero(data->hb, start, count);
824 int64_t next_dirty = hbitmap_next_dirty(data->hb, start, count);
825 int64_t next;
826 int64_t end = start >= data->size || data->size - start < count ?
827 data->size : start + count;
828 bool first_bit = hbitmap_get(data->hb, start);
829
830 for (next = start;
831 next < end && hbitmap_get(data->hb, next) == first_bit;
832 next++)
833 {
834 ;
835 }
836
837 if (next == end) {
838 next = -1;
839 }
840
841 g_assert_cmpint(next_dirty, ==, first_bit ? start : next);
842 g_assert_cmpint(next_zero, ==, first_bit ? next : start);
843 }
844
845 static void test_hbitmap_next_x_check(TestHBitmapData *data, int64_t start)
846 {
847 test_hbitmap_next_x_check_range(data, start, INT64_MAX);
848 }
849
850 static void test_hbitmap_next_x_do(TestHBitmapData *data, int granularity)
851 {
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);
857
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);
869
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);
888
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);
899
900 hbitmap_set(data->hb, 0, L3);
901 test_hbitmap_next_x_check(data, 0);
902 }
903
904 static void test_hbitmap_next_x_0(TestHBitmapData *data, const void *unused)
905 {
906 test_hbitmap_next_x_do(data, 0);
907 }
908
909 static void test_hbitmap_next_x_4(TestHBitmapData *data, const void *unused)
910 {
911 test_hbitmap_next_x_do(data, 4);
912 }
913
914 static void test_hbitmap_next_x_after_truncate(TestHBitmapData *data,
915 const void *unused)
916 {
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);
921 }
922
923 static void test_hbitmap_next_dirty_area_check_limited(TestHBitmapData *data,
924 int64_t offset,
925 int64_t count,
926 int64_t max_dirty)
927 {
928 int64_t off1, off2;
929 int64_t len1 = 0, len2;
930 bool ret1, ret2;
931 int64_t end;
932
933 ret1 = hbitmap_next_dirty_area(data->hb,
934 offset, count == INT64_MAX ? INT64_MAX : offset + count, max_dirty,
935 &off1, &len1);
936
937 end = offset > data->size || data->size - offset < count ? data->size :
938 offset + count;
939
940 for (off2 = offset; off2 < end && !hbitmap_get(data->hb, off2); off2++) {
941 ;
942 }
943
944 for (len2 = 1; (off2 + len2 < end && len2 < max_dirty &&
945 hbitmap_get(data->hb, off2 + len2)); len2++)
946 {
947 ;
948 }
949
950 ret2 = off2 < end;
951 g_assert_cmpint(ret1, ==, ret2);
952
953 if (ret2) {
954 g_assert_cmpint(off1, ==, off2);
955 g_assert_cmpint(len1, ==, len2);
956 }
957 }
958
959 static void test_hbitmap_next_dirty_area_check(TestHBitmapData *data,
960 int64_t offset, int64_t count)
961 {
962 test_hbitmap_next_dirty_area_check_limited(data, offset, count, INT64_MAX);
963 }
964
965 static void test_hbitmap_next_dirty_area_do(TestHBitmapData *data,
966 int granularity)
967 {
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);
973
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);
987
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);
1001
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);
1013
1014 hbitmap_set(data->hb, 0, L3);
1015 test_hbitmap_next_dirty_area_check(data, 0, INT64_MAX);
1016 }
1017
1018 static void test_hbitmap_next_dirty_area_0(TestHBitmapData *data,
1019 const void *unused)
1020 {
1021 test_hbitmap_next_dirty_area_do(data, 0);
1022 }
1023
1024 static void test_hbitmap_next_dirty_area_1(TestHBitmapData *data,
1025 const void *unused)
1026 {
1027 test_hbitmap_next_dirty_area_do(data, 1);
1028 }
1029
1030 static void test_hbitmap_next_dirty_area_4(TestHBitmapData *data,
1031 const void *unused)
1032 {
1033 test_hbitmap_next_dirty_area_do(data, 4);
1034 }
1035
1036 static void test_hbitmap_next_dirty_area_after_truncate(TestHBitmapData *data,
1037 const void *unused)
1038 {
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);
1043 }
1044
1045 int main(int argc, char **argv)
1046 {
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);
1065
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);
1087
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);
1096
1097 hbitmap_test_add("/hbitmap/iter/iter_and_reset",
1098 test_hbitmap_iter_and_reset);
1099
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);
1106
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);
1115
1116 g_test_run();
1117
1118 return 0;
1119 }