cirrus: fix off-by-one in cirrus_bitblt_rop_bkwd_transp_*_16
[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 HBitmap *meta;
26 unsigned long *bits;
27 size_t size;
28 size_t old_size;
29 int granularity;
30 } TestHBitmapData;
31
32
33 /* Check that the HBitmap and the shadow bitmap contain the same data,
34 * ignoring the same "first" bits.
35 */
36 static void hbitmap_test_check(TestHBitmapData *data,
37 uint64_t first)
38 {
39 uint64_t count = 0;
40 size_t pos;
41 int bit;
42 HBitmapIter hbi;
43 int64_t i, next;
44
45 hbitmap_iter_init(&hbi, data->hb, first);
46
47 i = first;
48 for (;;) {
49 next = hbitmap_iter_next(&hbi);
50 if (next < 0) {
51 next = data->size;
52 }
53
54 while (i < next) {
55 pos = i >> LOG_BITS_PER_LONG;
56 bit = i & (BITS_PER_LONG - 1);
57 i++;
58 g_assert_cmpint(data->bits[pos] & (1UL << bit), ==, 0);
59 }
60
61 if (next == data->size) {
62 break;
63 }
64
65 pos = i >> LOG_BITS_PER_LONG;
66 bit = i & (BITS_PER_LONG - 1);
67 i++;
68 count++;
69 g_assert_cmpint(data->bits[pos] & (1UL << bit), !=, 0);
70 }
71
72 if (first == 0) {
73 g_assert_cmpint(count << data->granularity, ==, hbitmap_count(data->hb));
74 }
75 }
76
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)
81 {
82 size_t n;
83 data->hb = hbitmap_alloc(size, granularity);
84
85 n = DIV_ROUND_UP(size, BITS_PER_LONG);
86 if (n == 0) {
87 n = 1;
88 }
89 data->bits = g_new0(unsigned long, n);
90 data->size = size;
91 data->granularity = granularity;
92 if (size) {
93 hbitmap_test_check(data, 0);
94 }
95 }
96
97 static void hbitmap_test_init_meta(TestHBitmapData *data,
98 uint64_t size, int granularity,
99 int meta_chunk)
100 {
101 hbitmap_test_init(data, size, granularity);
102 data->meta = hbitmap_create_meta(data->hb, meta_chunk);
103 }
104
105 static inline size_t hbitmap_test_array_size(size_t bits)
106 {
107 size_t n = DIV_ROUND_UP(bits, BITS_PER_LONG);
108 return n ? n : 1;
109 }
110
111 static void hbitmap_test_truncate_impl(TestHBitmapData *data,
112 size_t size)
113 {
114 size_t n;
115 size_t m;
116 data->old_size = data->size;
117 data->size = size;
118
119 if (data->size == data->old_size) {
120 return;
121 }
122
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);
126 if (n > m) {
127 memset(&data->bits[m], 0x00, sizeof(unsigned long) * (n - m));
128 }
129
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);
134 if (m) {
135 unsigned long mask = (1ULL << m) - 1;
136 data->bits[n-1] &= mask;
137 }
138 }
139
140 hbitmap_truncate(data->hb, size);
141 }
142
143 static void hbitmap_test_teardown(TestHBitmapData *data,
144 const void *unused)
145 {
146 if (data->hb) {
147 if (data->meta) {
148 hbitmap_free_meta(data->hb);
149 }
150 hbitmap_free(data->hb);
151 data->hb = NULL;
152 }
153 g_free(data->bits);
154 data->bits = NULL;
155 }
156
157 /* Set a range in the HBitmap and in the shadow "simple" bitmap.
158 * The two bitmaps are then tested against each other.
159 */
160 static void hbitmap_test_set(TestHBitmapData *data,
161 uint64_t first, uint64_t count)
162 {
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);
167 first++;
168
169 data->bits[pos] |= 1UL << bit;
170 }
171
172 if (data->granularity == 0) {
173 hbitmap_test_check(data, 0);
174 }
175 }
176
177 /* Reset a range in the HBitmap and in the shadow "simple" bitmap.
178 */
179 static void hbitmap_test_reset(TestHBitmapData *data,
180 uint64_t first, uint64_t count)
181 {
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);
186 first++;
187
188 data->bits[pos] &= ~(1UL << bit);
189 }
190
191 if (data->granularity == 0) {
192 hbitmap_test_check(data, 0);
193 }
194 }
195
196 static void hbitmap_test_reset_all(TestHBitmapData *data)
197 {
198 size_t n;
199
200 hbitmap_reset_all(data->hb);
201
202 n = DIV_ROUND_UP(data->size, BITS_PER_LONG);
203 if (n == 0) {
204 n = 1;
205 }
206 memset(data->bits, 0, n * sizeof(unsigned long));
207
208 if (data->granularity == 0) {
209 hbitmap_test_check(data, 0);
210 }
211 }
212
213 static void hbitmap_test_check_get(TestHBitmapData *data)
214 {
215 uint64_t count = 0;
216 uint64_t i;
217
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);
224 }
225 g_assert_cmpint(count, ==, hbitmap_count(data->hb));
226 }
227
228 static void test_hbitmap_zero(TestHBitmapData *data,
229 const void *unused)
230 {
231 hbitmap_test_init(data, 0, 0);
232 }
233
234 static void test_hbitmap_unaligned(TestHBitmapData *data,
235 const void *unused)
236 {
237 hbitmap_test_init(data, L3 + 23, 0);
238 hbitmap_test_set(data, 0, 1);
239 hbitmap_test_set(data, L3 + 22, 1);
240 }
241
242 static void test_hbitmap_iter_empty(TestHBitmapData *data,
243 const void *unused)
244 {
245 hbitmap_test_init(data, L1, 0);
246 }
247
248 static void test_hbitmap_iter_partial(TestHBitmapData *data,
249 const void *unused)
250 {
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);
268 }
269
270 static void test_hbitmap_set_all(TestHBitmapData *data,
271 const void *unused)
272 {
273 hbitmap_test_init(data, L3, 0);
274 hbitmap_test_set(data, 0, L3);
275 }
276
277 static void test_hbitmap_get_all(TestHBitmapData *data,
278 const void *unused)
279 {
280 hbitmap_test_init(data, L3, 0);
281 hbitmap_test_set(data, 0, L3);
282 hbitmap_test_check_get(data);
283 }
284
285 static void test_hbitmap_get_some(TestHBitmapData *data,
286 const void *unused)
287 {
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);
299 }
300
301 static void test_hbitmap_set_one(TestHBitmapData *data,
302 const void *unused)
303 {
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);
310 }
311
312 static void test_hbitmap_set_two_elem(TestHBitmapData *data,
313 const void *unused)
314 {
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);
324 }
325
326 static void test_hbitmap_set(TestHBitmapData *data,
327 const void *unused)
328 {
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);
339 }
340
341 static void test_hbitmap_set_twice(TestHBitmapData *data,
342 const void *unused)
343 {
344 hbitmap_test_init(data, L1 * 3, 0);
345 hbitmap_test_set(data, 0, L1 * 3);
346 hbitmap_test_set(data, L1, 1);
347 }
348
349 static void test_hbitmap_set_overlap(TestHBitmapData *data,
350 const void *unused)
351 {
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);
363 }
364
365 static void test_hbitmap_reset_empty(TestHBitmapData *data,
366 const void *unused)
367 {
368 hbitmap_test_init(data, L3, 0);
369 hbitmap_test_reset(data, 0, L3);
370 }
371
372 static void test_hbitmap_reset(TestHBitmapData *data,
373 const void *unused)
374 {
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);
391 }
392
393 static void test_hbitmap_reset_all(TestHBitmapData *data,
394 const void *unused)
395 {
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);
411 }
412
413 static void test_hbitmap_granularity(TestHBitmapData *data,
414 const void *unused)
415 {
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);
428 }
429
430 static void test_hbitmap_iter_granularity(TestHBitmapData *data,
431 const void *unused)
432 {
433 HBitmapIter hbi;
434
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);
439
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);
444
445 hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
446 g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
447
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);
453
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);
457 }
458
459 static void hbitmap_test_set_boundary_bits(TestHBitmapData *data, ssize_t diff)
460 {
461 size_t size = data->size;
462
463 /* First bit */
464 hbitmap_test_set(data, 0, 1);
465 if (diff < 0) {
466 /* Last bit in new, shortened map */
467 hbitmap_test_set(data, size + diff - 1, 1);
468
469 /* First bit to be truncated away */
470 hbitmap_test_set(data, size + diff, 1);
471 }
472 /* Last bit */
473 hbitmap_test_set(data, size - 1, 1);
474 if (data->granularity == 0) {
475 hbitmap_test_check_get(data);
476 }
477 }
478
479 static void hbitmap_test_check_boundary_bits(TestHBitmapData *data)
480 {
481 size_t size = MIN(data->size, data->old_size);
482
483 if (data->granularity == 0) {
484 hbitmap_test_check_get(data);
485 hbitmap_test_check(data, 0);
486 } else {
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.
490 *
491 * The hbitmap_test_check facility does not currently tolerate
492 * non-zero granularities, so test the boundaries and the population
493 * count manually.
494 */
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));
498 }
499 }
500
501 /* Generic truncate test. */
502 static void hbitmap_test_truncate(TestHBitmapData *data,
503 size_t size,
504 ssize_t diff,
505 int granularity)
506 {
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);
511 }
512
513 static void test_hbitmap_truncate_nop(TestHBitmapData *data,
514 const void *unused)
515 {
516 hbitmap_test_truncate(data, L2, 0, 0);
517 }
518
519 /**
520 * Grow by an amount smaller than the granularity, without crossing
521 * a granularity alignment boundary. Effectively a NOP.
522 */
523 static void test_hbitmap_truncate_grow_negligible(TestHBitmapData *data,
524 const void *unused)
525 {
526 size_t size = L2 - 1;
527 size_t diff = 1;
528 int granularity = 1;
529
530 hbitmap_test_truncate(data, size, diff, granularity);
531 }
532
533 /**
534 * Shrink by an amount smaller than the granularity, without crossing
535 * a granularity alignment boundary. Effectively a NOP.
536 */
537 static void test_hbitmap_truncate_shrink_negligible(TestHBitmapData *data,
538 const void *unused)
539 {
540 size_t size = L2;
541 ssize_t diff = -1;
542 int granularity = 1;
543
544 hbitmap_test_truncate(data, size, diff, granularity);
545 }
546
547 /**
548 * Grow by an amount smaller than the granularity, but crossing over
549 * a granularity alignment boundary.
550 */
551 static void test_hbitmap_truncate_grow_tiny(TestHBitmapData *data,
552 const void *unused)
553 {
554 size_t size = L2 - 2;
555 ssize_t diff = 1;
556 int granularity = 1;
557
558 hbitmap_test_truncate(data, size, diff, granularity);
559 }
560
561 /**
562 * Shrink by an amount smaller than the granularity, but crossing over
563 * a granularity alignment boundary.
564 */
565 static void test_hbitmap_truncate_shrink_tiny(TestHBitmapData *data,
566 const void *unused)
567 {
568 size_t size = L2 - 1;
569 ssize_t diff = -1;
570 int granularity = 1;
571
572 hbitmap_test_truncate(data, size, diff, granularity);
573 }
574
575 /**
576 * Grow by an amount smaller than sizeof(long), and not crossing over
577 * a sizeof(long) alignment boundary.
578 */
579 static void test_hbitmap_truncate_grow_small(TestHBitmapData *data,
580 const void *unused)
581 {
582 size_t size = L2 + 1;
583 size_t diff = sizeof(long) / 2;
584
585 hbitmap_test_truncate(data, size, diff, 0);
586 }
587
588 /**
589 * Shrink by an amount smaller than sizeof(long), and not crossing over
590 * a sizeof(long) alignment boundary.
591 */
592 static void test_hbitmap_truncate_shrink_small(TestHBitmapData *data,
593 const void *unused)
594 {
595 size_t size = L2;
596 size_t diff = sizeof(long) / 2;
597
598 hbitmap_test_truncate(data, size, -diff, 0);
599 }
600
601 /**
602 * Grow by an amount smaller than sizeof(long), while crossing over
603 * a sizeof(long) alignment boundary.
604 */
605 static void test_hbitmap_truncate_grow_medium(TestHBitmapData *data,
606 const void *unused)
607 {
608 size_t size = L2 - 1;
609 size_t diff = sizeof(long) / 2;
610
611 hbitmap_test_truncate(data, size, diff, 0);
612 }
613
614 /**
615 * Shrink by an amount smaller than sizeof(long), while crossing over
616 * a sizeof(long) alignment boundary.
617 */
618 static void test_hbitmap_truncate_shrink_medium(TestHBitmapData *data,
619 const void *unused)
620 {
621 size_t size = L2 + 1;
622 size_t diff = sizeof(long) / 2;
623
624 hbitmap_test_truncate(data, size, -diff, 0);
625 }
626
627 /**
628 * Grow by an amount larger than sizeof(long).
629 */
630 static void test_hbitmap_truncate_grow_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 /**
640 * Shrink by an amount larger than sizeof(long).
641 */
642 static void test_hbitmap_truncate_shrink_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 static void hbitmap_check_meta(TestHBitmapData *data,
652 int64_t start, int count)
653 {
654 int64_t i;
655
656 for (i = 0; i < data->size; i++) {
657 if (i >= start && i < start + count) {
658 g_assert(hbitmap_get(data->meta, i));
659 } else {
660 g_assert(!hbitmap_get(data->meta, i));
661 }
662 }
663 }
664
665 static void hbitmap_test_meta(TestHBitmapData *data,
666 int64_t start, int count,
667 int64_t check_start, int check_count)
668 {
669 hbitmap_reset_all(data->hb);
670 hbitmap_reset_all(data->meta);
671
672 /* Test "unset" -> "unset" will not update meta. */
673 hbitmap_reset(data->hb, start, count);
674 hbitmap_check_meta(data, 0, 0);
675
676 /* Test "unset" -> "set" will update meta */
677 hbitmap_set(data->hb, start, count);
678 hbitmap_check_meta(data, check_start, check_count);
679
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);
684
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);
689 }
690
691 static void hbitmap_test_meta_do(TestHBitmapData *data, int chunk_size)
692 {
693 uint64_t size = chunk_size * 100;
694 hbitmap_test_init_meta(data, size, 0, chunk_size);
695
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);
706 }
707
708 static void test_hbitmap_meta_byte(TestHBitmapData *data, const void *unused)
709 {
710 hbitmap_test_meta_do(data, BITS_PER_BYTE);
711 }
712
713 static void test_hbitmap_meta_word(TestHBitmapData *data, const void *unused)
714 {
715 hbitmap_test_meta_do(data, BITS_PER_LONG);
716 }
717
718 static void test_hbitmap_meta_sector(TestHBitmapData *data, const void *unused)
719 {
720 hbitmap_test_meta_do(data, BDRV_SECTOR_SIZE * BITS_PER_BYTE);
721 }
722
723 /**
724 * Create an HBitmap and test set/unset.
725 */
726 static void test_hbitmap_meta_one(TestHBitmapData *data, const void *unused)
727 {
728 int i;
729 int64_t offsets[] = {
730 0, 1, L1 - 1, L1, L1 + 1, L2 - 1, L2, L2 + 1, L3 - 1, L3, L3 + 1
731 };
732
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);
738 }
739 }
740
741 static void test_hbitmap_serialize_granularity(TestHBitmapData *data,
742 const void *unused)
743 {
744 int r;
745
746 hbitmap_test_init(data, L3 * 2, 3);
747 g_assert(hbitmap_is_serializable(data->hb));
748
749 r = hbitmap_serialization_granularity(data->hb);
750 g_assert_cmpint(r, ==, 64 << 3);
751 }
752
753 static void test_hbitmap_meta_zero(TestHBitmapData *data, const void *unused)
754 {
755 hbitmap_test_init_meta(data, 0, 0, 1);
756
757 hbitmap_check_meta(data, 0, 0);
758 }
759
760 static void hbitmap_test_serialize_range(TestHBitmapData *data,
761 uint8_t *buf, size_t buf_size,
762 uint64_t pos, uint64_t count)
763 {
764 size_t i;
765 unsigned long *el = (unsigned long *)buf;
766
767 assert(hbitmap_granularity(data->hb) == 0);
768 hbitmap_reset_all(data->hb);
769 memset(buf, 0, buf_size);
770 if (count) {
771 hbitmap_set(data->hb, pos, count);
772 }
773
774 g_assert(hbitmap_is_serializable(data->hb));
775 hbitmap_serialize_part(data->hb, buf, 0, data->size);
776
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]));
780 }
781
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) {
785 g_assert(is_set);
786 } else {
787 g_assert(!is_set);
788 }
789 }
790
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);
795
796 g_assert(hbitmap_is_serializable(data->hb));
797 hbitmap_deserialize_part(data->hb, buf, 0, data->size, true);
798
799 for (i = 0; i < data->size; i++) {
800 int is_set = hbitmap_get(data->hb, i);
801 if (i >= pos && i < pos + count) {
802 g_assert(is_set);
803 } else {
804 g_assert(!is_set);
805 }
806 }
807 }
808
809 static void test_hbitmap_serialize_basic(TestHBitmapData *data,
810 const void *unused)
811 {
812 int i, j;
813 size_t buf_size;
814 uint8_t *buf;
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]);
817
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);
822
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,
826 positions[i],
827 MIN(positions[j], L3 - positions[i]));
828 }
829 }
830
831 g_free(buf);
832 }
833
834 static void test_hbitmap_serialize_part(TestHBitmapData *data,
835 const void *unused)
836 {
837 int i, j, k;
838 size_t buf_size;
839 uint8_t *buf;
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]);
842
843 hbitmap_test_init(data, L3, 0);
844 buf_size = L2;
845 buf = g_malloc0(buf_size);
846
847 for (i = 0; i < num_positions; i++) {
848 hbitmap_set(data->hb, positions[i], 1);
849 }
850
851 g_assert(hbitmap_is_serializable(data->hb));
852
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]));
858 }
859
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) {
864 should_set = true;
865 break;
866 }
867 }
868 g_assert_cmpint(should_set, ==, test_bit(j, (unsigned long *)buf));
869 }
870 }
871
872 g_free(buf);
873 }
874
875 static void test_hbitmap_serialize_zeroes(TestHBitmapData *data,
876 const void *unused)
877 {
878 int i;
879 HBitmapIter iter;
880 int64_t next;
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]);
884
885 hbitmap_test_init(data, L3, 0);
886
887 for (i = 0; i < num_positions; i++) {
888 hbitmap_set(data->hb, positions[i], L1);
889 }
890
891 g_assert(hbitmap_is_serializable(data->hb));
892
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);
899 } else {
900 g_assert_cmpint(next, ==, positions[i + 1]);
901 }
902 }
903 }
904
905 static void hbitmap_test_add(const char *testpath,
906 void (*test_func)(TestHBitmapData *data, const void *user_data))
907 {
908 g_test_add(testpath, TestHBitmapData, NULL, NULL, test_func,
909 hbitmap_test_teardown);
910 }
911
912 int main(int argc, char **argv)
913 {
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);
932
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);
954
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);
960
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);
969 g_test_run();
970
971 return 0;
972 }