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  */
hbitmap_test_check(TestHBitmapData * data,uint64_t first)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()) */
hbitmap_test_init(TestHBitmapData * data,uint64_t size,int granularity)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 
hbitmap_test_init_meta(TestHBitmapData * data,uint64_t size,int granularity,int meta_chunk)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 
hbitmap_test_array_size(size_t bits)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 
hbitmap_test_truncate_impl(TestHBitmapData * data,size_t size)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 
hbitmap_test_teardown(TestHBitmapData * data,const void * unused)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  */
hbitmap_test_set(TestHBitmapData * data,uint64_t first,uint64_t count)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  */
hbitmap_test_reset(TestHBitmapData * data,uint64_t first,uint64_t count)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 
hbitmap_test_reset_all(TestHBitmapData * data)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 
hbitmap_test_check_get(TestHBitmapData * data)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 
test_hbitmap_zero(TestHBitmapData * data,const void * unused)228 static void test_hbitmap_zero(TestHBitmapData *data,
229                                const void *unused)
230 {
231     hbitmap_test_init(data, 0, 0);
232 }
233 
test_hbitmap_unaligned(TestHBitmapData * data,const void * unused)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 
test_hbitmap_iter_empty(TestHBitmapData * data,const void * unused)242 static void test_hbitmap_iter_empty(TestHBitmapData *data,
243                                     const void *unused)
244 {
245     hbitmap_test_init(data, L1, 0);
246 }
247 
test_hbitmap_iter_partial(TestHBitmapData * data,const void * unused)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 
test_hbitmap_set_all(TestHBitmapData * data,const void * unused)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 
test_hbitmap_get_all(TestHBitmapData * data,const void * unused)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 
test_hbitmap_get_some(TestHBitmapData * data,const void * unused)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 
test_hbitmap_set_one(TestHBitmapData * data,const void * unused)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 
test_hbitmap_set_two_elem(TestHBitmapData * data,const void * unused)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 
test_hbitmap_set(TestHBitmapData * data,const void * unused)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 
test_hbitmap_set_twice(TestHBitmapData * data,const void * unused)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 
test_hbitmap_set_overlap(TestHBitmapData * data,const void * unused)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 
test_hbitmap_reset_empty(TestHBitmapData * data,const void * unused)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 
test_hbitmap_reset(TestHBitmapData * data,const void * unused)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 
test_hbitmap_reset_all(TestHBitmapData * data,const void * unused)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 
test_hbitmap_granularity(TestHBitmapData * data,const void * unused)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, 2);
427     g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
428 }
429 
test_hbitmap_iter_granularity(TestHBitmapData * data,const void * unused)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 
hbitmap_test_set_boundary_bits(TestHBitmapData * data,ssize_t diff)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 
hbitmap_test_check_boundary_bits(TestHBitmapData * data)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. */
hbitmap_test_truncate(TestHBitmapData * data,size_t size,ssize_t diff,int granularity)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 
test_hbitmap_truncate_nop(TestHBitmapData * data,const void * unused)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  */
test_hbitmap_truncate_grow_negligible(TestHBitmapData * data,const void * unused)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  */
test_hbitmap_truncate_shrink_negligible(TestHBitmapData * data,const void * unused)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  */
test_hbitmap_truncate_grow_tiny(TestHBitmapData * data,const void * unused)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  */
test_hbitmap_truncate_shrink_tiny(TestHBitmapData * data,const void * unused)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  */
test_hbitmap_truncate_grow_small(TestHBitmapData * data,const void * unused)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  */
test_hbitmap_truncate_shrink_small(TestHBitmapData * data,const void * unused)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  */
test_hbitmap_truncate_grow_medium(TestHBitmapData * data,const void * unused)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  */
test_hbitmap_truncate_shrink_medium(TestHBitmapData * data,const void * unused)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  */
test_hbitmap_truncate_grow_large(TestHBitmapData * data,const void * unused)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  */
test_hbitmap_truncate_shrink_large(TestHBitmapData * data,const void * unused)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 
hbitmap_check_meta(TestHBitmapData * data,int64_t start,int count)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 
hbitmap_test_meta(TestHBitmapData * data,int64_t start,int count,int64_t check_start,int check_count)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 
hbitmap_test_meta_do(TestHBitmapData * data,int chunk_size)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 
test_hbitmap_meta_byte(TestHBitmapData * data,const void * unused)708 static void test_hbitmap_meta_byte(TestHBitmapData *data, const void *unused)
709 {
710     hbitmap_test_meta_do(data, BITS_PER_BYTE);
711 }
712 
test_hbitmap_meta_word(TestHBitmapData * data,const void * unused)713 static void test_hbitmap_meta_word(TestHBitmapData *data, const void *unused)
714 {
715     hbitmap_test_meta_do(data, BITS_PER_LONG);
716 }
717 
test_hbitmap_meta_sector(TestHBitmapData * data,const void * unused)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  */
test_hbitmap_meta_one(TestHBitmapData * data,const void * unused)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 
test_hbitmap_serialize_align(TestHBitmapData * data,const void * unused)741 static void test_hbitmap_serialize_align(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_align(data->hb);
750     g_assert_cmpint(r, ==, 64 << 3);
751 }
752 
test_hbitmap_meta_zero(TestHBitmapData * data,const void * unused)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 
hbitmap_test_serialize_range(TestHBitmapData * data,uint8_t * buf,size_t buf_size,uint64_t pos,uint64_t count)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 
test_hbitmap_serialize_basic(TestHBitmapData * data,const void * unused)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 = ARRAY_SIZE(positions);
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 
test_hbitmap_serialize_part(TestHBitmapData * data,const void * unused)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 = ARRAY_SIZE(positions);
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 
test_hbitmap_serialize_zeroes(TestHBitmapData * data,const void * unused)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 = ARRAY_SIZE(positions);
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 
hbitmap_test_add(const char * testpath,void (* test_func)(TestHBitmapData * data,const void * user_data))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 
test_hbitmap_iter_and_reset(TestHBitmapData * data,const void * unused)912 static void test_hbitmap_iter_and_reset(TestHBitmapData *data,
913                                         const void *unused)
914 {
915     HBitmapIter hbi;
916 
917     hbitmap_test_init(data, L1 * 2, 0);
918     hbitmap_set(data->hb, 0, data->size);
919 
920     hbitmap_iter_init(&hbi, data->hb, BITS_PER_LONG - 1);
921 
922     hbitmap_iter_next(&hbi);
923 
924     hbitmap_reset_all(data->hb);
925     hbitmap_iter_next(&hbi);
926 }
927 
test_hbitmap_next_zero_check_range(TestHBitmapData * data,uint64_t start,uint64_t count)928 static void test_hbitmap_next_zero_check_range(TestHBitmapData *data,
929                                                uint64_t start,
930                                                uint64_t count)
931 {
932     int64_t ret1 = hbitmap_next_zero(data->hb, start, count);
933     int64_t ret2 = start;
934     int64_t end = start >= data->size || data->size - start < count ?
935                 data->size : start + count;
936 
937     for ( ; ret2 < end && hbitmap_get(data->hb, ret2); ret2++) {
938         ;
939     }
940     if (ret2 == end) {
941         ret2 = -1;
942     }
943 
944     g_assert_cmpint(ret1, ==, ret2);
945 }
946 
test_hbitmap_next_zero_check(TestHBitmapData * data,int64_t start)947 static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start)
948 {
949     test_hbitmap_next_zero_check_range(data, start, UINT64_MAX);
950 }
951 
test_hbitmap_next_zero_do(TestHBitmapData * data,int granularity)952 static void test_hbitmap_next_zero_do(TestHBitmapData *data, int granularity)
953 {
954     hbitmap_test_init(data, L3, granularity);
955     test_hbitmap_next_zero_check(data, 0);
956     test_hbitmap_next_zero_check(data, L3 - 1);
957     test_hbitmap_next_zero_check_range(data, 0, 1);
958     test_hbitmap_next_zero_check_range(data, L3 - 1, 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     test_hbitmap_next_zero_check_range(data, 0, 1);
966     test_hbitmap_next_zero_check_range(data, 0, L2);
967     test_hbitmap_next_zero_check_range(data, L2 - 1, 1);
968     test_hbitmap_next_zero_check_range(data, L2 - 1, 2);
969     test_hbitmap_next_zero_check_range(data, L2, 1);
970     test_hbitmap_next_zero_check_range(data, L2 + 1, 1);
971 
972     hbitmap_set(data->hb, L2 + 5, L1);
973     test_hbitmap_next_zero_check(data, 0);
974     test_hbitmap_next_zero_check(data, L2 + 1);
975     test_hbitmap_next_zero_check(data, L2 + 2);
976     test_hbitmap_next_zero_check(data, L2 + 5);
977     test_hbitmap_next_zero_check(data, L2 + L1 - 1);
978     test_hbitmap_next_zero_check(data, L2 + L1);
979     test_hbitmap_next_zero_check_range(data, L2, 6);
980     test_hbitmap_next_zero_check_range(data, L2 + 1, 3);
981     test_hbitmap_next_zero_check_range(data, L2 + 4, L1);
982     test_hbitmap_next_zero_check_range(data, L2 + 5, L1);
983 
984     hbitmap_set(data->hb, L2 * 2, L3 - L2 * 2);
985     test_hbitmap_next_zero_check(data, L2 * 2 - L1);
986     test_hbitmap_next_zero_check(data, L2 * 2 - 2);
987     test_hbitmap_next_zero_check(data, L2 * 2 - 1);
988     test_hbitmap_next_zero_check(data, L2 * 2);
989     test_hbitmap_next_zero_check(data, L3 - 1);
990     test_hbitmap_next_zero_check_range(data, L2 * 2 - L1, L1 + 1);
991     test_hbitmap_next_zero_check_range(data, L2 * 2, L2);
992 
993     hbitmap_set(data->hb, 0, L3);
994     test_hbitmap_next_zero_check(data, 0);
995 }
996 
test_hbitmap_next_zero_0(TestHBitmapData * data,const void * unused)997 static void test_hbitmap_next_zero_0(TestHBitmapData *data, const void *unused)
998 {
999     test_hbitmap_next_zero_do(data, 0);
1000 }
1001 
test_hbitmap_next_zero_4(TestHBitmapData * data,const void * unused)1002 static void test_hbitmap_next_zero_4(TestHBitmapData *data, const void *unused)
1003 {
1004     test_hbitmap_next_zero_do(data, 4);
1005 }
1006 
test_hbitmap_next_zero_after_truncate(TestHBitmapData * data,const void * unused)1007 static void test_hbitmap_next_zero_after_truncate(TestHBitmapData *data,
1008                                                   const void *unused)
1009 {
1010     hbitmap_test_init(data, L1, 0);
1011     hbitmap_test_truncate_impl(data, L1 * 2);
1012     hbitmap_set(data->hb, 0, L1);
1013     test_hbitmap_next_zero_check(data, 0);
1014 }
1015 
test_hbitmap_next_dirty_area_check(TestHBitmapData * data,uint64_t offset,uint64_t count)1016 static void test_hbitmap_next_dirty_area_check(TestHBitmapData *data,
1017                                                uint64_t offset,
1018                                                uint64_t count)
1019 {
1020     uint64_t off1, off2;
1021     uint64_t len1 = 0, len2;
1022     bool ret1, ret2;
1023     int64_t end;
1024 
1025     off1 = offset;
1026     len1 = count;
1027     ret1 = hbitmap_next_dirty_area(data->hb, &off1, &len1);
1028 
1029     end = offset > data->size || data->size - offset < count ? data->size :
1030                                                                offset + count;
1031 
1032     for (off2 = offset; off2 < end && !hbitmap_get(data->hb, off2); off2++) {
1033         ;
1034     }
1035 
1036     for (len2 = 1; off2 + len2 < end && hbitmap_get(data->hb, off2 + len2);
1037          len2++) {
1038         ;
1039     }
1040 
1041     ret2 = off2 < end;
1042     if (!ret2) {
1043         /* leave unchanged */
1044         off2 = offset;
1045         len2 = count;
1046     }
1047 
1048     g_assert_cmpint(ret1, ==, ret2);
1049     g_assert_cmpint(off1, ==, off2);
1050     g_assert_cmpint(len1, ==, len2);
1051 }
1052 
test_hbitmap_next_dirty_area_do(TestHBitmapData * data,int granularity)1053 static void test_hbitmap_next_dirty_area_do(TestHBitmapData *data,
1054                                             int granularity)
1055 {
1056     hbitmap_test_init(data, L3, granularity);
1057     test_hbitmap_next_dirty_area_check(data, 0, UINT64_MAX);
1058     test_hbitmap_next_dirty_area_check(data, 0, 1);
1059     test_hbitmap_next_dirty_area_check(data, L3 - 1, 1);
1060 
1061     hbitmap_set(data->hb, L2, 1);
1062     test_hbitmap_next_dirty_area_check(data, 0, 1);
1063     test_hbitmap_next_dirty_area_check(data, 0, L2);
1064     test_hbitmap_next_dirty_area_check(data, 0, UINT64_MAX);
1065     test_hbitmap_next_dirty_area_check(data, L2 - 1, UINT64_MAX);
1066     test_hbitmap_next_dirty_area_check(data, L2 - 1, 1);
1067     test_hbitmap_next_dirty_area_check(data, L2 - 1, 2);
1068     test_hbitmap_next_dirty_area_check(data, L2 - 1, 3);
1069     test_hbitmap_next_dirty_area_check(data, L2, UINT64_MAX);
1070     test_hbitmap_next_dirty_area_check(data, L2, 1);
1071     test_hbitmap_next_dirty_area_check(data, L2 + 1, 1);
1072 
1073     hbitmap_set(data->hb, L2 + 5, L1);
1074     test_hbitmap_next_dirty_area_check(data, 0, UINT64_MAX);
1075     test_hbitmap_next_dirty_area_check(data, L2 - 2, 8);
1076     test_hbitmap_next_dirty_area_check(data, L2 + 1, 5);
1077     test_hbitmap_next_dirty_area_check(data, L2 + 1, 3);
1078     test_hbitmap_next_dirty_area_check(data, L2 + 4, L1);
1079     test_hbitmap_next_dirty_area_check(data, L2 + 5, L1);
1080     test_hbitmap_next_dirty_area_check(data, L2 + 7, L1);
1081     test_hbitmap_next_dirty_area_check(data, L2 + L1, L1);
1082     test_hbitmap_next_dirty_area_check(data, L2, 0);
1083     test_hbitmap_next_dirty_area_check(data, L2 + 1, 0);
1084 
1085     hbitmap_set(data->hb, L2 * 2, L3 - L2 * 2);
1086     test_hbitmap_next_dirty_area_check(data, 0, UINT64_MAX);
1087     test_hbitmap_next_dirty_area_check(data, L2, UINT64_MAX);
1088     test_hbitmap_next_dirty_area_check(data, L2 + 1, UINT64_MAX);
1089     test_hbitmap_next_dirty_area_check(data, L2 + 5 + L1 - 1, UINT64_MAX);
1090     test_hbitmap_next_dirty_area_check(data, L2 + 5 + L1, 5);
1091     test_hbitmap_next_dirty_area_check(data, L2 * 2 - L1, L1 + 1);
1092     test_hbitmap_next_dirty_area_check(data, L2 * 2, L2);
1093 
1094     hbitmap_set(data->hb, 0, L3);
1095     test_hbitmap_next_dirty_area_check(data, 0, UINT64_MAX);
1096 }
1097 
test_hbitmap_next_dirty_area_0(TestHBitmapData * data,const void * unused)1098 static void test_hbitmap_next_dirty_area_0(TestHBitmapData *data,
1099                                            const void *unused)
1100 {
1101     test_hbitmap_next_dirty_area_do(data, 0);
1102 }
1103 
test_hbitmap_next_dirty_area_1(TestHBitmapData * data,const void * unused)1104 static void test_hbitmap_next_dirty_area_1(TestHBitmapData *data,
1105                                            const void *unused)
1106 {
1107     test_hbitmap_next_dirty_area_do(data, 1);
1108 }
1109 
test_hbitmap_next_dirty_area_4(TestHBitmapData * data,const void * unused)1110 static void test_hbitmap_next_dirty_area_4(TestHBitmapData *data,
1111                                            const void *unused)
1112 {
1113     test_hbitmap_next_dirty_area_do(data, 4);
1114 }
1115 
test_hbitmap_next_dirty_area_after_truncate(TestHBitmapData * data,const void * unused)1116 static void test_hbitmap_next_dirty_area_after_truncate(TestHBitmapData *data,
1117                                                         const void *unused)
1118 {
1119     hbitmap_test_init(data, L1, 0);
1120     hbitmap_test_truncate_impl(data, L1 * 2);
1121     hbitmap_set(data->hb, L1 + 1, 1);
1122     test_hbitmap_next_dirty_area_check(data, 0, UINT64_MAX);
1123 }
1124 
main(int argc,char ** argv)1125 int main(int argc, char **argv)
1126 {
1127     g_test_init(&argc, &argv, NULL);
1128     hbitmap_test_add("/hbitmap/size/0", test_hbitmap_zero);
1129     hbitmap_test_add("/hbitmap/size/unaligned", test_hbitmap_unaligned);
1130     hbitmap_test_add("/hbitmap/iter/empty", test_hbitmap_iter_empty);
1131     hbitmap_test_add("/hbitmap/iter/partial", test_hbitmap_iter_partial);
1132     hbitmap_test_add("/hbitmap/iter/granularity", test_hbitmap_iter_granularity);
1133     hbitmap_test_add("/hbitmap/get/all", test_hbitmap_get_all);
1134     hbitmap_test_add("/hbitmap/get/some", test_hbitmap_get_some);
1135     hbitmap_test_add("/hbitmap/set/all", test_hbitmap_set_all);
1136     hbitmap_test_add("/hbitmap/set/one", test_hbitmap_set_one);
1137     hbitmap_test_add("/hbitmap/set/two-elem", test_hbitmap_set_two_elem);
1138     hbitmap_test_add("/hbitmap/set/general", test_hbitmap_set);
1139     hbitmap_test_add("/hbitmap/set/twice", test_hbitmap_set_twice);
1140     hbitmap_test_add("/hbitmap/set/overlap", test_hbitmap_set_overlap);
1141     hbitmap_test_add("/hbitmap/reset/empty", test_hbitmap_reset_empty);
1142     hbitmap_test_add("/hbitmap/reset/general", test_hbitmap_reset);
1143     hbitmap_test_add("/hbitmap/reset/all", test_hbitmap_reset_all);
1144     hbitmap_test_add("/hbitmap/granularity", test_hbitmap_granularity);
1145 
1146     hbitmap_test_add("/hbitmap/truncate/nop", test_hbitmap_truncate_nop);
1147     hbitmap_test_add("/hbitmap/truncate/grow/negligible",
1148                      test_hbitmap_truncate_grow_negligible);
1149     hbitmap_test_add("/hbitmap/truncate/shrink/negligible",
1150                      test_hbitmap_truncate_shrink_negligible);
1151     hbitmap_test_add("/hbitmap/truncate/grow/tiny",
1152                      test_hbitmap_truncate_grow_tiny);
1153     hbitmap_test_add("/hbitmap/truncate/shrink/tiny",
1154                      test_hbitmap_truncate_shrink_tiny);
1155     hbitmap_test_add("/hbitmap/truncate/grow/small",
1156                      test_hbitmap_truncate_grow_small);
1157     hbitmap_test_add("/hbitmap/truncate/shrink/small",
1158                      test_hbitmap_truncate_shrink_small);
1159     hbitmap_test_add("/hbitmap/truncate/grow/medium",
1160                      test_hbitmap_truncate_grow_medium);
1161     hbitmap_test_add("/hbitmap/truncate/shrink/medium",
1162                      test_hbitmap_truncate_shrink_medium);
1163     hbitmap_test_add("/hbitmap/truncate/grow/large",
1164                      test_hbitmap_truncate_grow_large);
1165     hbitmap_test_add("/hbitmap/truncate/shrink/large",
1166                      test_hbitmap_truncate_shrink_large);
1167 
1168     hbitmap_test_add("/hbitmap/meta/zero", test_hbitmap_meta_zero);
1169     hbitmap_test_add("/hbitmap/meta/one", test_hbitmap_meta_one);
1170     hbitmap_test_add("/hbitmap/meta/byte", test_hbitmap_meta_byte);
1171     hbitmap_test_add("/hbitmap/meta/word", test_hbitmap_meta_word);
1172     hbitmap_test_add("/hbitmap/meta/sector", test_hbitmap_meta_sector);
1173 
1174     hbitmap_test_add("/hbitmap/serialize/align",
1175                      test_hbitmap_serialize_align);
1176     hbitmap_test_add("/hbitmap/serialize/basic",
1177                      test_hbitmap_serialize_basic);
1178     hbitmap_test_add("/hbitmap/serialize/part",
1179                      test_hbitmap_serialize_part);
1180     hbitmap_test_add("/hbitmap/serialize/zeroes",
1181                      test_hbitmap_serialize_zeroes);
1182 
1183     hbitmap_test_add("/hbitmap/iter/iter_and_reset",
1184                      test_hbitmap_iter_and_reset);
1185 
1186     hbitmap_test_add("/hbitmap/next_zero/next_zero_0",
1187                      test_hbitmap_next_zero_0);
1188     hbitmap_test_add("/hbitmap/next_zero/next_zero_4",
1189                      test_hbitmap_next_zero_4);
1190     hbitmap_test_add("/hbitmap/next_zero/next_zero_after_truncate",
1191                      test_hbitmap_next_zero_after_truncate);
1192 
1193     hbitmap_test_add("/hbitmap/next_dirty_area/next_dirty_area_0",
1194                      test_hbitmap_next_dirty_area_0);
1195     hbitmap_test_add("/hbitmap/next_dirty_area/next_dirty_area_1",
1196                      test_hbitmap_next_dirty_area_1);
1197     hbitmap_test_add("/hbitmap/next_dirty_area/next_dirty_area_4",
1198                      test_hbitmap_next_dirty_area_4);
1199     hbitmap_test_add("/hbitmap/next_dirty_area/next_dirty_area_after_truncate",
1200                      test_hbitmap_next_dirty_area_after_truncate);
1201 
1202     g_test_run();
1203 
1204     return 0;
1205 }
1206