]>
git.proxmox.com Git - mirror_qemu.git/blob - util/hbitmap.c
2 * Hierarchical Bitmap Data Type
4 * Copyright Red Hat, Inc., 2012
6 * Author: Paolo Bonzini <pbonzini@redhat.com>
8 * This work is licensed under the terms of the GNU GPL, version 2 or
9 * later. See the COPYING file in the top-level directory.
12 #include "qemu/osdep.h"
13 #include "qemu/hbitmap.h"
14 #include "qemu/host-utils.h"
16 #include "crypto/hash.h"
18 /* HBitmaps provides an array of bits. The bits are stored as usual in an
19 * array of unsigned longs, but HBitmap is also optimized to provide fast
20 * iteration over set bits; going from one bit to the next is O(logB n)
21 * worst case, with B = sizeof(long) * CHAR_BIT: the result is low enough
22 * that the number of levels is in fact fixed.
24 * In order to do this, it stacks multiple bitmaps with progressively coarser
25 * granularity; in all levels except the last, bit N is set iff the N-th
26 * unsigned long is nonzero in the immediately next level. When iteration
27 * completes on the last level it can examine the 2nd-last level to quickly
28 * skip entire words, and even do so recursively to skip blocks of 64 words or
29 * powers thereof (32 on 32-bit machines).
31 * Given an index in the bitmap, it can be split in group of bits like
32 * this (for the 64-bit case):
34 * bits 0-57 => word in the last bitmap | bits 58-63 => bit in the word
35 * bits 0-51 => word in the 2nd-last bitmap | bits 52-57 => bit in the word
36 * bits 0-45 => word in the 3rd-last bitmap | bits 46-51 => bit in the word
38 * So it is easy to move up simply by shifting the index right by
39 * log2(BITS_PER_LONG) bits. To move down, you shift the index left
40 * similarly, and add the word index within the group. Iteration uses
41 * ffs (find first set bit) to find the next word to examine; this
42 * operation can be done in constant time in most current architectures.
44 * Setting or clearing a range of m bits on all levels, the work to perform
45 * is O(m + m/W + m/W^2 + ...), which is O(m) like on a regular bitmap.
47 * When iterating on a bitmap, each bit (on any level) is only visited
48 * once. Hence, The total cost of visiting a bitmap with m bits in it is
49 * the number of bits that are set in all bitmaps. Unless the bitmap is
50 * extremely sparse, this is also O(m + m/W + m/W^2 + ...), so the amortized
51 * cost of advancing from one bit to the next is usually constant (worst case
52 * O(logB n) as in the non-amortized complexity).
57 * Size of the bitmap, as requested in hbitmap_alloc or in hbitmap_truncate.
61 /* Number of total bits in the bottom level. */
64 /* Number of set bits in the bottom level. */
67 /* A scaling factor. Given a granularity of G, each bit in the bitmap will
68 * will actually represent a group of 2^G elements. Each operation on a
69 * range of bits first rounds the bits to determine which group they land
70 * in, and then affect the entire page; iteration will only visit the first
71 * bit of each group. Here is an example of operations in a size-16,
72 * granularity-1 HBitmap:
74 * initial state 00000000
75 * set(start=0, count=9) 11111000 (iter: 0, 2, 4, 6, 8)
76 * reset(start=1, count=3) 00111000 (iter: 4, 6, 8)
77 * set(start=9, count=2) 00111100 (iter: 4, 6, 8, 10)
78 * reset(start=5, count=5) 00000000
80 * From an implementation point of view, when setting or resetting bits,
81 * the bitmap will scale bit numbers right by this amount of bits. When
82 * iterating, the bitmap will scale bit numbers left by this amount of
87 /* A meta dirty bitmap to track the dirtiness of bits in this HBitmap. */
90 /* A number of progressively less coarse bitmaps (i.e. level 0 is the
91 * coarsest). Each bit in level N represents a word in level N+1 that
92 * has a set bit, except the last level where each bit represents the
95 * Note that all bitmaps have the same number of levels. Even a 1-bit
96 * bitmap will still allocate HBITMAP_LEVELS arrays.
98 unsigned long *levels
[HBITMAP_LEVELS
];
100 /* The length of each levels[] array. */
101 uint64_t sizes
[HBITMAP_LEVELS
];
104 /* Advance hbi to the next nonzero word and return it. hbi->pos
105 * is updated. Returns zero if we reach the end of the bitmap.
107 static unsigned long hbitmap_iter_skip_words(HBitmapIter
*hbi
)
109 size_t pos
= hbi
->pos
;
110 const HBitmap
*hb
= hbi
->hb
;
111 unsigned i
= HBITMAP_LEVELS
- 1;
116 pos
>>= BITS_PER_LEVEL
;
117 cur
= hbi
->cur
[i
] & hb
->levels
[i
][pos
];
120 /* Check for end of iteration. We always use fewer than BITS_PER_LONG
121 * bits in the level 0 bitmap; thus we can repurpose the most significant
122 * bit as a sentinel. The sentinel is set in hbitmap_alloc and ensures
123 * that the above loop ends even without an explicit check on i.
126 if (i
== 0 && cur
== (1UL << (BITS_PER_LONG
- 1))) {
129 for (; i
< HBITMAP_LEVELS
- 1; i
++) {
130 /* Shift back pos to the left, matching the right shifts above.
131 * The index of this word's least significant set bit provides
132 * the low-order bits.
135 pos
= (pos
<< BITS_PER_LEVEL
) + ctzl(cur
);
136 hbi
->cur
[i
] = cur
& (cur
- 1);
138 /* Set up next level for iteration. */
139 cur
= hb
->levels
[i
+ 1][pos
];
143 trace_hbitmap_iter_skip_words(hbi
->hb
, hbi
, pos
, cur
);
149 int64_t hbitmap_iter_next(HBitmapIter
*hbi
)
151 unsigned long cur
= hbi
->cur
[HBITMAP_LEVELS
- 1] &
152 hbi
->hb
->levels
[HBITMAP_LEVELS
- 1][hbi
->pos
];
156 cur
= hbitmap_iter_skip_words(hbi
);
162 /* The next call will resume work from the next bit. */
163 hbi
->cur
[HBITMAP_LEVELS
- 1] = cur
& (cur
- 1);
164 item
= ((uint64_t)hbi
->pos
<< BITS_PER_LEVEL
) + ctzl(cur
);
166 return item
<< hbi
->granularity
;
169 void hbitmap_iter_init(HBitmapIter
*hbi
, const HBitmap
*hb
, uint64_t first
)
175 pos
= first
>> hb
->granularity
;
176 assert(pos
< hb
->size
);
177 hbi
->pos
= pos
>> BITS_PER_LEVEL
;
178 hbi
->granularity
= hb
->granularity
;
180 for (i
= HBITMAP_LEVELS
; i
-- > 0; ) {
181 bit
= pos
& (BITS_PER_LONG
- 1);
182 pos
>>= BITS_PER_LEVEL
;
184 /* Drop bits representing items before first. */
185 hbi
->cur
[i
] = hb
->levels
[i
][pos
] & ~((1UL << bit
) - 1);
187 /* We have already added level i+1, so the lowest set bit has
188 * been processed. Clear it.
190 if (i
!= HBITMAP_LEVELS
- 1) {
191 hbi
->cur
[i
] &= ~(1UL << bit
);
196 int64_t hbitmap_next_zero(const HBitmap
*hb
, int64_t start
, int64_t count
)
198 size_t pos
= (start
>> hb
->granularity
) >> BITS_PER_LEVEL
;
199 unsigned long *last_lev
= hb
->levels
[HBITMAP_LEVELS
- 1];
200 unsigned long cur
= last_lev
[pos
];
201 unsigned start_bit_offset
;
202 uint64_t end_bit
, sz
;
205 assert(start
>= 0 && count
>= 0);
207 if (start
>= hb
->orig_size
|| count
== 0) {
211 end_bit
= count
> hb
->orig_size
- start
?
213 ((start
+ count
- 1) >> hb
->granularity
) + 1;
214 sz
= (end_bit
+ BITS_PER_LONG
- 1) >> BITS_PER_LEVEL
;
216 /* There may be some zero bits in @cur before @start. We are not interested
217 * in them, let's set them.
219 start_bit_offset
= (start
>> hb
->granularity
) & (BITS_PER_LONG
- 1);
220 cur
|= (1UL << start_bit_offset
) - 1;
221 assert((start
>> hb
->granularity
) < hb
->size
);
223 if (cur
== (unsigned long)-1) {
226 } while (pos
< sz
&& last_lev
[pos
] == (unsigned long)-1);
235 res
= (pos
<< BITS_PER_LEVEL
) + ctol(cur
);
236 if (res
>= end_bit
) {
240 res
= res
<< hb
->granularity
;
242 assert(((start
- res
) >> hb
->granularity
) == 0);
249 bool hbitmap_next_dirty_area(const HBitmap
*hb
, int64_t *start
, int64_t *count
)
252 int64_t firt_dirty_off
, area_end
;
253 uint32_t granularity
= 1UL << hb
->granularity
;
256 assert(*start
>= 0 && *count
>= 0);
258 if (*start
>= hb
->orig_size
|| *count
== 0) {
262 end
= *count
> hb
->orig_size
- *start
? hb
->orig_size
: *start
+ *count
;
264 hbitmap_iter_init(&hbi
, hb
, *start
);
265 firt_dirty_off
= hbitmap_iter_next(&hbi
);
267 if (firt_dirty_off
< 0 || firt_dirty_off
>= end
) {
271 if (firt_dirty_off
+ granularity
>= end
) {
274 area_end
= hbitmap_next_zero(hb
, firt_dirty_off
+ granularity
,
275 end
- firt_dirty_off
- granularity
);
281 if (firt_dirty_off
> *start
) {
282 *start
= firt_dirty_off
;
284 *count
= area_end
- *start
;
289 bool hbitmap_empty(const HBitmap
*hb
)
291 return hb
->count
== 0;
294 int hbitmap_granularity(const HBitmap
*hb
)
296 return hb
->granularity
;
299 uint64_t hbitmap_count(const HBitmap
*hb
)
301 return hb
->count
<< hb
->granularity
;
305 * hbitmap_iter_next_word:
306 * @hbi: HBitmapIter to operate on.
307 * @p_cur: Location where to store the next non-zero word.
309 * Return the index of the next nonzero word that is set in @hbi's
310 * associated HBitmap, and set *p_cur to the content of that word
311 * (bits before the index that was passed to hbitmap_iter_init are
312 * trimmed on the first call). Return -1, and set *p_cur to zero,
313 * if all remaining words are zero.
315 static size_t hbitmap_iter_next_word(HBitmapIter
*hbi
, unsigned long *p_cur
)
317 unsigned long cur
= hbi
->cur
[HBITMAP_LEVELS
- 1];
320 cur
= hbitmap_iter_skip_words(hbi
);
327 /* The next call will resume work from the next word. */
328 hbi
->cur
[HBITMAP_LEVELS
- 1] = 0;
333 /* Count the number of set bits between start and end, not accounting for
334 * the granularity. Also an example of how to use hbitmap_iter_next_word.
336 static uint64_t hb_count_between(HBitmap
*hb
, uint64_t start
, uint64_t last
)
340 uint64_t end
= last
+ 1;
344 hbitmap_iter_init(&hbi
, hb
, start
<< hb
->granularity
);
346 pos
= hbitmap_iter_next_word(&hbi
, &cur
);
347 if (pos
>= (end
>> BITS_PER_LEVEL
)) {
350 count
+= ctpopl(cur
);
353 if (pos
== (end
>> BITS_PER_LEVEL
)) {
354 /* Drop bits representing the END-th and subsequent items. */
355 int bit
= end
& (BITS_PER_LONG
- 1);
356 cur
&= (1UL << bit
) - 1;
357 count
+= ctpopl(cur
);
363 /* Setting starts at the last layer and propagates up if an element
366 static inline bool hb_set_elem(unsigned long *elem
, uint64_t start
, uint64_t last
)
371 assert((last
>> BITS_PER_LEVEL
) == (start
>> BITS_PER_LEVEL
));
372 assert(start
<= last
);
374 mask
= 2UL << (last
& (BITS_PER_LONG
- 1));
375 mask
-= 1UL << (start
& (BITS_PER_LONG
- 1));
381 /* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)...
382 * Returns true if at least one bit is changed. */
383 static bool hb_set_between(HBitmap
*hb
, int level
, uint64_t start
,
386 size_t pos
= start
>> BITS_PER_LEVEL
;
387 size_t lastpos
= last
>> BITS_PER_LEVEL
;
388 bool changed
= false;
393 uint64_t next
= (start
| (BITS_PER_LONG
- 1)) + 1;
394 changed
|= hb_set_elem(&hb
->levels
[level
][i
], start
, next
- 1);
397 next
+= BITS_PER_LONG
;
398 if (++i
== lastpos
) {
401 changed
|= (hb
->levels
[level
][i
] == 0);
402 hb
->levels
[level
][i
] = ~0UL;
405 changed
|= hb_set_elem(&hb
->levels
[level
][i
], start
, last
);
407 /* If there was any change in this layer, we may have to update
410 if (level
> 0 && changed
) {
411 hb_set_between(hb
, level
- 1, pos
, lastpos
);
416 void hbitmap_set(HBitmap
*hb
, uint64_t start
, uint64_t count
)
418 /* Compute range in the last layer. */
420 uint64_t last
= start
+ count
- 1;
426 trace_hbitmap_set(hb
, start
, count
,
427 start
>> hb
->granularity
, last
>> hb
->granularity
);
429 first
= start
>> hb
->granularity
;
430 last
>>= hb
->granularity
;
431 assert(last
< hb
->size
);
432 n
= last
- first
+ 1;
434 hb
->count
+= n
- hb_count_between(hb
, first
, last
);
435 if (hb_set_between(hb
, HBITMAP_LEVELS
- 1, first
, last
) &&
437 hbitmap_set(hb
->meta
, start
, count
);
441 /* Resetting works the other way round: propagate up if the new
444 static inline bool hb_reset_elem(unsigned long *elem
, uint64_t start
, uint64_t last
)
449 assert((last
>> BITS_PER_LEVEL
) == (start
>> BITS_PER_LEVEL
));
450 assert(start
<= last
);
452 mask
= 2UL << (last
& (BITS_PER_LONG
- 1));
453 mask
-= 1UL << (start
& (BITS_PER_LONG
- 1));
454 blanked
= *elem
!= 0 && ((*elem
& ~mask
) == 0);
459 /* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)...
460 * Returns true if at least one bit is changed. */
461 static bool hb_reset_between(HBitmap
*hb
, int level
, uint64_t start
,
464 size_t pos
= start
>> BITS_PER_LEVEL
;
465 size_t lastpos
= last
>> BITS_PER_LEVEL
;
466 bool changed
= false;
471 uint64_t next
= (start
| (BITS_PER_LONG
- 1)) + 1;
473 /* Here we need a more complex test than when setting bits. Even if
474 * something was changed, we must not blank bits in the upper level
475 * unless the lower-level word became entirely zero. So, remove pos
476 * from the upper-level range if bits remain set.
478 if (hb_reset_elem(&hb
->levels
[level
][i
], start
, next
- 1)) {
486 next
+= BITS_PER_LONG
;
487 if (++i
== lastpos
) {
490 changed
|= (hb
->levels
[level
][i
] != 0);
491 hb
->levels
[level
][i
] = 0UL;
495 /* Same as above, this time for lastpos. */
496 if (hb_reset_elem(&hb
->levels
[level
][i
], start
, last
)) {
502 if (level
> 0 && changed
) {
503 hb_reset_between(hb
, level
- 1, pos
, lastpos
);
510 void hbitmap_reset(HBitmap
*hb
, uint64_t start
, uint64_t count
)
512 /* Compute range in the last layer. */
514 uint64_t last
= start
+ count
- 1;
515 uint64_t gran
= 1ULL << hb
->granularity
;
521 assert(QEMU_IS_ALIGNED(start
, gran
));
522 assert(QEMU_IS_ALIGNED(count
, gran
) || (start
+ count
== hb
->orig_size
));
524 trace_hbitmap_reset(hb
, start
, count
,
525 start
>> hb
->granularity
, last
>> hb
->granularity
);
527 first
= start
>> hb
->granularity
;
528 last
>>= hb
->granularity
;
529 assert(last
< hb
->size
);
531 hb
->count
-= hb_count_between(hb
, first
, last
);
532 if (hb_reset_between(hb
, HBITMAP_LEVELS
- 1, first
, last
) &&
534 hbitmap_set(hb
->meta
, start
, count
);
538 void hbitmap_reset_all(HBitmap
*hb
)
542 /* Same as hbitmap_alloc() except for memset() instead of malloc() */
543 for (i
= HBITMAP_LEVELS
; --i
>= 1; ) {
544 memset(hb
->levels
[i
], 0, hb
->sizes
[i
] * sizeof(unsigned long));
547 hb
->levels
[0][0] = 1UL << (BITS_PER_LONG
- 1);
551 bool hbitmap_is_serializable(const HBitmap
*hb
)
553 /* Every serialized chunk must be aligned to 64 bits so that endianness
554 * requirements can be fulfilled on both 64 bit and 32 bit hosts.
555 * We have hbitmap_serialization_align() which converts this
556 * alignment requirement from bitmap bits to items covered (e.g. sectors).
558 * 64 << hb->granularity
559 * Since this value must not exceed UINT64_MAX, hb->granularity must be
560 * less than 58 (== 64 - 6, where 6 is ld(64), i.e. 1 << 6 == 64).
562 * In order for hbitmap_serialization_align() to always return a
563 * meaningful value, bitmaps that are to be serialized must have a
564 * granularity of less than 58. */
566 return hb
->granularity
< 58;
569 bool hbitmap_get(const HBitmap
*hb
, uint64_t item
)
571 /* Compute position and bit in the last layer. */
572 uint64_t pos
= item
>> hb
->granularity
;
573 unsigned long bit
= 1UL << (pos
& (BITS_PER_LONG
- 1));
574 assert(pos
< hb
->size
);
576 return (hb
->levels
[HBITMAP_LEVELS
- 1][pos
>> BITS_PER_LEVEL
] & bit
) != 0;
579 uint64_t hbitmap_serialization_align(const HBitmap
*hb
)
581 assert(hbitmap_is_serializable(hb
));
583 /* Require at least 64 bit granularity to be safe on both 64 bit and 32 bit
585 return UINT64_C(64) << hb
->granularity
;
588 /* Start should be aligned to serialization granularity, chunk size should be
589 * aligned to serialization granularity too, except for last chunk.
591 static void serialization_chunk(const HBitmap
*hb
,
592 uint64_t start
, uint64_t count
,
593 unsigned long **first_el
, uint64_t *el_count
)
595 uint64_t last
= start
+ count
- 1;
596 uint64_t gran
= hbitmap_serialization_align(hb
);
598 assert((start
& (gran
- 1)) == 0);
599 assert((last
>> hb
->granularity
) < hb
->size
);
600 if ((last
>> hb
->granularity
) != hb
->size
- 1) {
601 assert((count
& (gran
- 1)) == 0);
604 start
= (start
>> hb
->granularity
) >> BITS_PER_LEVEL
;
605 last
= (last
>> hb
->granularity
) >> BITS_PER_LEVEL
;
607 *first_el
= &hb
->levels
[HBITMAP_LEVELS
- 1][start
];
608 *el_count
= last
- start
+ 1;
611 uint64_t hbitmap_serialization_size(const HBitmap
*hb
,
612 uint64_t start
, uint64_t count
)
620 serialization_chunk(hb
, start
, count
, &cur
, &el_count
);
622 return el_count
* sizeof(unsigned long);
625 void hbitmap_serialize_part(const HBitmap
*hb
, uint8_t *buf
,
626 uint64_t start
, uint64_t count
)
629 unsigned long *cur
, *end
;
634 serialization_chunk(hb
, start
, count
, &cur
, &el_count
);
635 end
= cur
+ el_count
;
639 (BITS_PER_LONG
== 32 ? cpu_to_le32(*cur
) : cpu_to_le64(*cur
));
641 memcpy(buf
, &el
, sizeof(el
));
647 void hbitmap_deserialize_part(HBitmap
*hb
, uint8_t *buf
,
648 uint64_t start
, uint64_t count
,
652 unsigned long *cur
, *end
;
657 serialization_chunk(hb
, start
, count
, &cur
, &el_count
);
658 end
= cur
+ el_count
;
661 memcpy(cur
, buf
, sizeof(*cur
));
663 if (BITS_PER_LONG
== 32) {
664 le32_to_cpus((uint32_t *)cur
);
666 le64_to_cpus((uint64_t *)cur
);
669 buf
+= sizeof(unsigned long);
673 hbitmap_deserialize_finish(hb
);
677 void hbitmap_deserialize_zeroes(HBitmap
*hb
, uint64_t start
, uint64_t count
,
681 unsigned long *first
;
686 serialization_chunk(hb
, start
, count
, &first
, &el_count
);
688 memset(first
, 0, el_count
* sizeof(unsigned long));
690 hbitmap_deserialize_finish(hb
);
694 void hbitmap_deserialize_ones(HBitmap
*hb
, uint64_t start
, uint64_t count
,
698 unsigned long *first
;
703 serialization_chunk(hb
, start
, count
, &first
, &el_count
);
705 memset(first
, 0xff, el_count
* sizeof(unsigned long));
707 hbitmap_deserialize_finish(hb
);
711 void hbitmap_deserialize_finish(HBitmap
*bitmap
)
713 int64_t i
, size
, prev_size
;
716 /* restore levels starting from penultimate to zero level, assuming
717 * that the last level is ok */
718 size
= MAX((bitmap
->size
+ BITS_PER_LONG
- 1) >> BITS_PER_LEVEL
, 1);
719 for (lev
= HBITMAP_LEVELS
- 1; lev
-- > 0; ) {
721 size
= MAX((size
+ BITS_PER_LONG
- 1) >> BITS_PER_LEVEL
, 1);
722 memset(bitmap
->levels
[lev
], 0, size
* sizeof(unsigned long));
724 for (i
= 0; i
< prev_size
; ++i
) {
725 if (bitmap
->levels
[lev
+ 1][i
]) {
726 bitmap
->levels
[lev
][i
>> BITS_PER_LEVEL
] |=
727 1UL << (i
& (BITS_PER_LONG
- 1));
732 bitmap
->levels
[0][0] |= 1UL << (BITS_PER_LONG
- 1);
733 bitmap
->count
= hb_count_between(bitmap
, 0, bitmap
->size
- 1);
736 void hbitmap_free(HBitmap
*hb
)
740 for (i
= HBITMAP_LEVELS
; i
-- > 0; ) {
741 g_free(hb
->levels
[i
]);
746 HBitmap
*hbitmap_alloc(uint64_t size
, int granularity
)
748 HBitmap
*hb
= g_new0(struct HBitmap
, 1);
751 assert(size
<= INT64_MAX
);
752 hb
->orig_size
= size
;
754 assert(granularity
>= 0 && granularity
< 64);
755 size
= (size
+ (1ULL << granularity
) - 1) >> granularity
;
756 assert(size
<= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE
));
759 hb
->granularity
= granularity
;
760 for (i
= HBITMAP_LEVELS
; i
-- > 0; ) {
761 size
= MAX((size
+ BITS_PER_LONG
- 1) >> BITS_PER_LEVEL
, 1);
763 hb
->levels
[i
] = g_new0(unsigned long, size
);
766 /* We necessarily have free bits in level 0 due to the definition
767 * of HBITMAP_LEVELS, so use one for a sentinel. This speeds up
768 * hbitmap_iter_skip_words.
771 hb
->levels
[0][0] |= 1UL << (BITS_PER_LONG
- 1);
775 void hbitmap_truncate(HBitmap
*hb
, uint64_t size
)
779 uint64_t num_elements
= size
;
782 assert(size
<= INT64_MAX
);
783 hb
->orig_size
= size
;
785 /* Size comes in as logical elements, adjust for granularity. */
786 size
= (size
+ (1ULL << hb
->granularity
) - 1) >> hb
->granularity
;
787 assert(size
<= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE
));
788 shrink
= size
< hb
->size
;
790 /* bit sizes are identical; nothing to do. */
791 if (size
== hb
->size
) {
795 /* If we're losing bits, let's clear those bits before we invalidate all of
796 * our invariants. This helps keep the bitcount consistent, and will prevent
797 * us from carrying around garbage bits beyond the end of the map.
800 /* Don't clear partial granularity groups;
801 * start at the first full one. */
802 uint64_t start
= ROUND_UP(num_elements
, UINT64_C(1) << hb
->granularity
);
803 uint64_t fix_count
= (hb
->size
<< hb
->granularity
) - start
;
806 hbitmap_reset(hb
, start
, fix_count
);
810 for (i
= HBITMAP_LEVELS
; i
-- > 0; ) {
811 size
= MAX(BITS_TO_LONGS(size
), 1);
812 if (hb
->sizes
[i
] == size
) {
817 hb
->levels
[i
] = g_realloc(hb
->levels
[i
], size
* sizeof(unsigned long));
819 memset(&hb
->levels
[i
][old
], 0x00,
820 (size
- old
) * sizeof(*hb
->levels
[i
]));
824 hbitmap_truncate(hb
->meta
, hb
->size
<< hb
->granularity
);
828 bool hbitmap_can_merge(const HBitmap
*a
, const HBitmap
*b
)
830 return (a
->orig_size
== b
->orig_size
);
834 * hbitmap_sparse_merge: performs dst = dst | src
835 * works with differing granularities.
836 * best used when src is sparsely populated.
838 static void hbitmap_sparse_merge(HBitmap
*dst
, const HBitmap
*src
)
841 int64_t count
= src
->orig_size
;
843 while (hbitmap_next_dirty_area(src
, &offset
, &count
)) {
844 hbitmap_set(dst
, offset
, count
);
846 if (offset
>= src
->orig_size
) {
849 count
= src
->orig_size
- offset
;
854 * Given HBitmaps A and B, let R := A (BITOR) B.
855 * Bitmaps A and B will not be modified,
856 * except when bitmap R is an alias of A or B.
858 * @return true if the merge was successful,
859 * false if it was not attempted.
861 bool hbitmap_merge(const HBitmap
*a
, const HBitmap
*b
, HBitmap
*result
)
866 if (!hbitmap_can_merge(a
, b
) || !hbitmap_can_merge(a
, result
)) {
869 assert(hbitmap_can_merge(b
, result
));
871 if ((!hbitmap_count(a
) && result
== b
) ||
872 (!hbitmap_count(b
) && result
== a
)) {
876 if (!hbitmap_count(a
) && !hbitmap_count(b
)) {
877 hbitmap_reset_all(result
);
881 if (a
->granularity
!= b
->granularity
) {
882 if ((a
!= result
) && (b
!= result
)) {
883 hbitmap_reset_all(result
);
886 hbitmap_sparse_merge(result
, a
);
889 hbitmap_sparse_merge(result
, b
);
894 /* This merge is O(size), as BITS_PER_LONG and HBITMAP_LEVELS are constant.
895 * It may be possible to improve running times for sparsely populated maps
896 * by using hbitmap_iter_next, but this is suboptimal for dense maps.
898 assert(a
->size
== b
->size
);
899 for (i
= HBITMAP_LEVELS
- 1; i
>= 0; i
--) {
900 for (j
= 0; j
< a
->sizes
[i
]; j
++) {
901 result
->levels
[i
][j
] = a
->levels
[i
][j
] | b
->levels
[i
][j
];
905 /* Recompute the dirty count */
906 result
->count
= hb_count_between(result
, 0, result
->size
- 1);
911 char *hbitmap_sha256(const HBitmap
*bitmap
, Error
**errp
)
913 size_t size
= bitmap
->sizes
[HBITMAP_LEVELS
- 1] * sizeof(unsigned long);
914 char *data
= (char *)bitmap
->levels
[HBITMAP_LEVELS
- 1];
916 qcrypto_hash_digest(QCRYPTO_HASH_ALG_SHA256
, data
, size
, &hash
, errp
);