]> git.proxmox.com Git - mirror_qemu.git/blame - tests/test-hbitmap.c
projects / mirror_qemu.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
dirty-bitmap: improve bdrv_dirty_bitmap_next_zero
[mirror_qemu.git] / tests / test-hbitmap.c
CommitLineData
e7c033c3
PB		 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
681c28a3 12#include "qemu/osdep.h"
e7c033c3 13#include "qemu/hbitmap.h"
2071f26e 14#include "qemu/bitmap.h"
4b62818a 15#include "block/block.h"
e7c033c3
PB		 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;
4b62818a 25 HBitmap *meta;
e7c033c3
PB		 26 unsigned long *bits;
27 size_t size;
a94e87c0 28 size_t old_size;
e7c033c3
PB		 29 int granularity;
30} TestHBitmapData;
31
32
26957684
HR		 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
e7c033c3
PB		 45/* Check that the HBitmap and the shadow bitmap contain the same data,
46 * ignoring the same "first" bits.
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 (;;) {
26957684 61 next = check_hbitmap_iter_next(&hbi);
e7c033c3
PB		 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/* This is provided instead of a test setup function so that the sizes
90 are kept in the test functions (and not in main()) */
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
30f549c2 97 n = DIV_ROUND_UP(size, BITS_PER_LONG);
e7c033c3
PB		 98 if (n == 0) {
99 n = 1;
100 }
101 data->bits = g_new0(unsigned long, n);
102 data->size = size;
103 data->granularity = granularity;
1b095244
PB		 104 if (size) {
105 hbitmap_test_check(data, 0);
106 }
e7c033c3
PB		 107}
108
4b62818a
FZ		 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
a94e87c0
JS		 117static inline size_t hbitmap_test_array_size(size_t bits)
118{
30f549c2 119 size_t n = DIV_ROUND_UP(bits, BITS_PER_LONG);
a94e87c0
JS		 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 /* If we shrink to an uneven multiple of sizeof(unsigned long),
143 * scrub the leftover memory. */
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
e7c033c3
PB		 155static void hbitmap_test_teardown(TestHBitmapData *data,
156 const void *unused)
157{
158 if (data->hb) {
4b62818a
FZ		 159 if (data->meta) {
160 hbitmap_free_meta(data->hb);
161 }
e7c033c3
PB		 162 hbitmap_free(data->hb);
163 data->hb = NULL;
164 }
012aef07
MA		 165 g_free(data->bits);
166 data->bits = NULL;
e7c033c3
PB		 167}
168
169/* Set a range in the HBitmap and in the shadow "simple" bitmap.
170 * The two bitmaps are then tested against each other.
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/* Reset a range in the HBitmap and in the shadow "simple" bitmap.
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
c6a8c328
WC		 208static void hbitmap_test_reset_all(TestHBitmapData *data)
209{
210 size_t n;
211
212 hbitmap_reset_all(data->hb);
213
30f549c2 214 n = DIV_ROUND_UP(data->size, BITS_PER_LONG);
c6a8c328
WC		 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
e7c033c3
PB		 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
e7c033c3
PB		 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
c6a8c328
WC		 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
e7c033c3
PB		 425static void test_hbitmap_granularity(TestHBitmapData *data,
426 const void *unused)
427{
428 /* Note that hbitmap_test_check has to be invoked manually in this test. */
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 /* Note that hbitmap_test_check has to be invoked manually in this test. */
448 hbitmap_test_init(data, 131072 << 7, 7);
449 hbitmap_iter_init(&hbi, data->hb, 0);
26957684 450 g_assert_cmpint(check_hbitmap_iter_next(&hbi), <, 0);
e7c033c3
PB		 451
452 hbitmap_test_set(data, ((L2 + L1 + 1) << 7) + 8, 8);
453 hbitmap_iter_init(&hbi, data->hb, 0);
26957684
HR		 454 g_assert_cmpint(check_hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
455 g_assert_cmpint(check_hbitmap_iter_next(&hbi), <, 0);
e7c033c3
PB		 456
457 hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
a33fbb4f 458 g_assert_cmpint(hbitmap_iter_next(&hbi, true), <, 0);
e7c033c3
PB		 459
460 hbitmap_test_set(data, (131072 << 7) - 8, 8);
461 hbitmap_iter_init(&hbi, data->hb, 0);
26957684
HR		 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);
e7c033c3
PB		 465
466 hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
26957684
HR		 467 g_assert_cmpint(check_hbitmap_iter_next(&hbi), ==, 131071 << 7);
468 g_assert_cmpint(check_hbitmap_iter_next(&hbi), <, 0);
e7c033c3
PB		 469}
470
a94e87c0
JS		 471static void hbitmap_test_set_boundary_bits(TestHBitmapData *data, ssize_t diff)
472{
473 size_t size = data->size;
474
475 /* First bit */
476 hbitmap_test_set(data, 0, 1);
477 if (diff < 0) {
478 /* Last bit in new, shortened map */
479 hbitmap_test_set(data, size + diff - 1, 1);
480
481 /* First bit to be truncated away */
482 hbitmap_test_set(data, size + diff, 1);
483 }
484 /* Last bit */
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 /* If a granularity was set, note that every distinct
500 * (bit >> granularity) value that was set will increase
501 * the bit pop count by 2^granularity, not just 1.
502 *
503 * The hbitmap_test_check facility does not currently tolerate
504 * non-zero granularities, so test the boundaries and the population
505 * count manually.
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/* Generic truncate test. */
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 * Grow by an amount smaller than the granularity, without crossing
533 * a granularity alignment boundary. Effectively a NOP.
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 * Shrink by an amount smaller than the granularity, without crossing
547 * a granularity alignment boundary. Effectively a NOP.
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 * Grow by an amount smaller than the granularity, but crossing over
561 * a granularity alignment boundary.
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 * Shrink by an amount smaller than the granularity, but crossing over
575 * a granularity alignment boundary.
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 * Grow by an amount smaller than sizeof(long), and not crossing over
589 * a sizeof(long) alignment boundary.
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 * Shrink by an amount smaller than sizeof(long), and not crossing over
602 * a sizeof(long) alignment boundary.
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 * Grow by an amount smaller than sizeof(long), while crossing over
615 * a sizeof(long) alignment boundary.
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 * Shrink by an amount smaller than sizeof(long), while crossing over
628 * a sizeof(long) alignment boundary.
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 * Grow by an amount larger than sizeof(long).
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 * Shrink by an amount larger than sizeof(long).
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
4b62818a
FZ		 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 /* Test "unset" -> "unset" will not update meta. */
685 hbitmap_reset(data->hb, start, count);
686 hbitmap_check_meta(data, 0, 0);
687
688 /* Test "unset" -> "set" will update meta */
689 hbitmap_set(data->hb, start, count);
690 hbitmap_check_meta(data, check_start, check_count);
691
692 /* Test "set" -> "set" will not update meta */
693 hbitmap_reset_all(data->meta);
694 hbitmap_set(data->hb, start, count);
695 hbitmap_check_meta(data, 0, 0);
696
697 /* Test "set" -> "unset" will update meta */
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 * Create an HBitmap and test set/unset.
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
ecbfa281
EB		 753static void test_hbitmap_serialize_align(TestHBitmapData *data,
754 const void *unused)
2071f26e
FZ		 755{
756 int r;
757
758 hbitmap_test_init(data, L3 * 2, 3);
7cdc49b9
HR		 759 g_assert(hbitmap_is_serializable(data->hb));
760
ecbfa281 761 r = hbitmap_serialization_align(data->hb);
2071f26e
FZ		 762 g_assert_cmpint(r, ==, 64 << 3);
763}
764
4b62818a
FZ		 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
2071f26e
FZ		 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 }
7cdc49b9
HR		 785
786 g_assert(hbitmap_is_serializable(data->hb));
2071f26e
FZ		 787 hbitmap_serialize_part(data->hb, buf, 0, data->size);
788
789 /* Serialized buffer is inherently LE, convert it back manually to test */
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 /* Re-serialize for deserialization testing */
804 memset(buf, 0, buf_size);
805 hbitmap_serialize_part(data->hb, buf, 0, data->size);
806 hbitmap_reset_all(data->hb);
7cdc49b9
HR		 807
808 g_assert(hbitmap_is_serializable(data->hb));
2071f26e
FZ		 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 };
f96c1896 828 int num_positions = ARRAY_SIZE(positions);
2071f26e
FZ		 829
830 hbitmap_test_init(data, L3, 0);
7cdc49b9 831 g_assert(hbitmap_is_serializable(data->hb));
2071f26e
FZ		 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 };
f96c1896 853 int num_positions = ARRAY_SIZE(positions);
2071f26e
FZ		 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
7cdc49b9
HR		 863 g_assert(hbitmap_is_serializable(data->hb));
864
2071f26e
FZ		 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};
f96c1896 895 int num_positions = ARRAY_SIZE(positions);
2071f26e
FZ		 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
7cdc49b9
HR		 903 g_assert(hbitmap_is_serializable(data->hb));
904
2071f26e
FZ		 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);
26957684 908 next = check_hbitmap_iter_next(&iter);
2071f26e
FZ		 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
e7c033c3
PB		 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
eedc4b6d
VSO		 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
26957684 934 check_hbitmap_iter_next(&hbi);
eedc4b6d
VSO		 935
936 hbitmap_reset_all(data->hb);
26957684 937 check_hbitmap_iter_next(&hbi);
eedc4b6d
VSO		 938}
939
56207df5
VSO		 940static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start)
941{
76d570dc 942 int64_t ret1 = hbitmap_next_zero(data->hb, start, UINT64_MAX);
56207df5
VSO		 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
e7c033c3
PB		 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);
e7c033c3
PB		 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);
c6a8c328 1013 hbitmap_test_add("/hbitmap/reset/all", test_hbitmap_reset_all);
e7c033c3 1014 hbitmap_test_add("/hbitmap/granularity", test_hbitmap_granularity);
a94e87c0
JS		 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);
4b62818a
FZ		 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);
2071f26e 1043
ecbfa281
EB		 1044 hbitmap_test_add("/hbitmap/serialize/align",
1045 test_hbitmap_serialize_align);
2071f26e
FZ		 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);
eedc4b6d
VSO		 1052
1053 hbitmap_test_add("/hbitmap/iter/iter_and_reset",
1054 test_hbitmap_iter_and_reset);
56207df5
VSO		 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
e7c033c3
PB		 1061 g_test_run();
1062
1063 return 0;
1064}
QEMU mirror