1/*
2 * Hierarchical Bitmap Data Type
3 *
4 * Copyright Red Hat, Inc., 2012
5 *
6 * Author: Paolo Bonzini <pbonzini@redhat.com>
7 *
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.
10 */
11
12#include "qemu/osdep.h"
13#include "qemu/hbitmap.h"
14#include "qemu/host-utils.h"
15#include "trace.h"
16#include "crypto/hash.h"
17
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.
23 *
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).
30 *
31 * Given an index in the bitmap, it can be split in group of bits like
32 * this (for the 64-bit case):
33 *
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
37 *
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.
43 *
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.
46 *
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).
53 */
54
55struct HBitmap {
56 /*
57 * Size of the bitmap, as requested in hbitmap_alloc or in hbitmap_truncate.
58 */
59 uint64_t orig_size;
60
61 /* Number of total bits in the bottom level. */
62 uint64_t size;
63
64 /* Number of set bits in the bottom level. */
65 uint64_t count;
66
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:
73 *
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
79 *
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
83 * bits.
84 */
85 int granularity;
86
87 /* A meta dirty bitmap to track the dirtiness of bits in this HBitmap. */
88 HBitmap *meta;
89
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
93 * actual bitmap.
94 *
95 * Note that all bitmaps have the same number of levels. Even a 1-bit
96 * bitmap will still allocate HBITMAP_LEVELS arrays.
97 */
98 unsigned long *levels[HBITMAP_LEVELS];
99
100 /* The length of each levels[] array. */
101 uint64_t sizes[HBITMAP_LEVELS];
102};
103
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.
106 */
107unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi)
108{
109 size_t pos = hbi->pos;
110 const HBitmap *hb = hbi->hb;
111 unsigned i = HBITMAP_LEVELS - 1;
112
113 unsigned long cur;
114 do {
115 i--;
116 pos >>= BITS_PER_LEVEL;
117 cur = hbi->cur[i] & hb->levels[i][pos];
118 } while (cur == 0);
119
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.
124 */
125
126 if (i == 0 && cur == (1UL << (BITS_PER_LONG - 1))) {
127 return 0;
128 }
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.
133 */
134 assert(cur);
135 pos = (pos << BITS_PER_LEVEL) + ctzl(cur);
136 hbi->cur[i] = cur & (cur - 1);
137
138 /* Set up next level for iteration. */
139 cur = hb->levels[i + 1][pos];
140 }
141
142 hbi->pos = pos;
143 trace_hbitmap_iter_skip_words(hbi->hb, hbi, pos, cur);
144
145 assert(cur);
146 return cur;
147}
148
149int64_t hbitmap_iter_next(HBitmapIter *hbi)
150{
151 unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1] &
152 hbi->hb->levels[HBITMAP_LEVELS - 1][hbi->pos];
153 int64_t item;
154
155 if (cur == 0) {
156 cur = hbitmap_iter_skip_words(hbi);
157 if (cur == 0) {
158 return -1;
159 }
160 }
161
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);
165
166 return item << hbi->granularity;
167}
168
169void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first)
170{
171 unsigned i, bit;
172 uint64_t pos;
173
174 hbi->hb = hb;
175 pos = first >> hb->granularity;
176 assert(pos < hb->size);
177 hbi->pos = pos >> BITS_PER_LEVEL;
178 hbi->granularity = hb->granularity;
179
180 for (i = HBITMAP_LEVELS; i-- > 0; ) {
181 bit = pos & (BITS_PER_LONG - 1);
182 pos >>= BITS_PER_LEVEL;
183
184 /* Drop bits representing items before first. */
185 hbi->cur[i] = hb->levels[i][pos] & ~((1UL << bit) - 1);
186
187 /* We have already added level i+1, so the lowest set bit has
188 * been processed. Clear it.
189 */
190 if (i != HBITMAP_LEVELS - 1) {
191 hbi->cur[i] &= ~(1UL << bit);
192 }
193 }
194}
195
196int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t count)
197{
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;
203 int64_t res;
204
205 if (start >= hb->orig_size || count == 0) {
206 return -1;
207 }
208
209 end_bit = count > hb->orig_size - start ?
210 hb->size :
211 ((start + count - 1) >> hb->granularity) + 1;
212 sz = (end_bit + BITS_PER_LONG - 1) >> BITS_PER_LEVEL;
213
214 /* There may be some zero bits in @cur before @start. We are not interested
215 * in them, let's set them.
216 */
217 start_bit_offset = (start >> hb->granularity) & (BITS_PER_LONG - 1);
218 cur |= (1UL << start_bit_offset) - 1;
219 assert((start >> hb->granularity) < hb->size);
220
221 if (cur == (unsigned long)-1) {
222 do {
223 pos++;
224 } while (pos < sz && last_lev[pos] == (unsigned long)-1);
225
226 if (pos >= sz) {
227 return -1;
228 }
229
230 cur = last_lev[pos];
231 }
232
233 res = (pos << BITS_PER_LEVEL) + ctol(cur);
234 if (res >= end_bit) {
235 return -1;
236 }
237
238 res = res << hb->granularity;
239 if (res < start) {
240 assert(((start - res) >> hb->granularity) == 0);
241 return start;
242 }
243
244 return res;
245}
246
247bool hbitmap_next_dirty_area(const HBitmap *hb, uint64_t *start,
248 uint64_t *count)
249{
250 HBitmapIter hbi;
251 int64_t firt_dirty_off, area_end;
252 uint32_t granularity = 1UL << hb->granularity;
253 uint64_t end;
254
255 if (*start >= hb->orig_size || *count == 0) {
256 return false;
257 }
258
259 end = *count > hb->orig_size - *start ? hb->orig_size : *start + *count;
260
261 hbitmap_iter_init(&hbi, hb, *start);
262 firt_dirty_off = hbitmap_iter_next(&hbi);
263
264 if (firt_dirty_off < 0 || firt_dirty_off >= end) {
265 return false;
266 }
267
268 if (firt_dirty_off + granularity >= end) {
269 area_end = end;
270 } else {
271 area_end = hbitmap_next_zero(hb, firt_dirty_off + granularity,
272 end - firt_dirty_off - granularity);
273 if (area_end < 0) {
274 area_end = end;
275 }
276 }
277
278 if (firt_dirty_off > *start) {
279 *start = firt_dirty_off;
280 }
281 *count = area_end - *start;
282
283 return true;
284}
285
286bool hbitmap_empty(const HBitmap *hb)
287{
288 return hb->count == 0;
289}
290
291int hbitmap_granularity(const HBitmap *hb)
292{
293 return hb->granularity;
294}
295
296uint64_t hbitmap_count(const HBitmap *hb)
297{
298 return hb->count << hb->granularity;
299}
300
301/* Count the number of set bits between start and end, not accounting for
302 * the granularity. Also an example of how to use hbitmap_iter_next_word.
303 */
304static uint64_t hb_count_between(HBitmap *hb, uint64_t start, uint64_t last)
305{
306 HBitmapIter hbi;
307 uint64_t count = 0;
308 uint64_t end = last + 1;
309 unsigned long cur;
310 size_t pos;
311
312 hbitmap_iter_init(&hbi, hb, start << hb->granularity);
313 for (;;) {
314 pos = hbitmap_iter_next_word(&hbi, &cur);
315 if (pos >= (end >> BITS_PER_LEVEL)) {
316 break;
317 }
318 count += ctpopl(cur);
319 }
320
321 if (pos == (end >> BITS_PER_LEVEL)) {
322 /* Drop bits representing the END-th and subsequent items. */
323 int bit = end & (BITS_PER_LONG - 1);
324 cur &= (1UL << bit) - 1;
325 count += ctpopl(cur);
326 }
327
328 return count;
329}
330
331/* Setting starts at the last layer and propagates up if an element
332 * changes.
333 */
334static inline bool hb_set_elem(unsigned long *elem, uint64_t start, uint64_t last)
335{
336 unsigned long mask;
337 unsigned long old;
338
339 assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL));
340 assert(start <= last);
341
342 mask = 2UL << (last & (BITS_PER_LONG - 1));
343 mask -= 1UL << (start & (BITS_PER_LONG - 1));
344 old = *elem;
345 *elem |= mask;
346 return old != *elem;
347}
348
349/* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)...
350 * Returns true if at least one bit is changed. */
351static bool hb_set_between(HBitmap *hb, int level, uint64_t start,
352 uint64_t last)
353{
354 size_t pos = start >> BITS_PER_LEVEL;
355 size_t lastpos = last >> BITS_PER_LEVEL;
356 bool changed = false;
357 size_t i;
358
359 i = pos;
360 if (i < lastpos) {
361 uint64_t next = (start | (BITS_PER_LONG - 1)) + 1;
362 changed |= hb_set_elem(&hb->levels[level][i], start, next - 1);
363 for (;;) {
364 start = next;
365 next += BITS_PER_LONG;
366 if (++i == lastpos) {
367 break;
368 }
369 changed |= (hb->levels[level][i] == 0);
370 hb->levels[level][i] = ~0UL;
371 }
372 }
373 changed |= hb_set_elem(&hb->levels[level][i], start, last);
374
375 /* If there was any change in this layer, we may have to update
376 * the one above.
377 */
378 if (level > 0 && changed) {
379 hb_set_between(hb, level - 1, pos, lastpos);
380 }
381 return changed;
382}
383
384void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count)
385{
386 /* Compute range in the last layer. */
387 uint64_t first, n;
388 uint64_t last = start + count - 1;
389
390 trace_hbitmap_set(hb, start, count,
391 start >> hb->granularity, last >> hb->granularity);
392
393 first = start >> hb->granularity;
394 last >>= hb->granularity;
395 assert(last < hb->size);
396 n = last - first + 1;
397
398 hb->count += n - hb_count_between(hb, first, last);
399 if (hb_set_between(hb, HBITMAP_LEVELS - 1, first, last) &&
400 hb->meta) {
401 hbitmap_set(hb->meta, start, count);
402 }
403}
404
405/* Resetting works the other way round: propagate up if the new
406 * value is zero.
407 */
408static inline bool hb_reset_elem(unsigned long *elem, uint64_t start, uint64_t last)
409{
410 unsigned long mask;
411 bool blanked;
412
413 assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL));
414 assert(start <= last);
415
416 mask = 2UL << (last & (BITS_PER_LONG - 1));
417 mask -= 1UL << (start & (BITS_PER_LONG - 1));
418 blanked = *elem != 0 && ((*elem & ~mask) == 0);
419 *elem &= ~mask;
420 return blanked;
421}
422
423/* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)...
424 * Returns true if at least one bit is changed. */
425static bool hb_reset_between(HBitmap *hb, int level, uint64_t start,
426 uint64_t last)
427{
428 size_t pos = start >> BITS_PER_LEVEL;
429 size_t lastpos = last >> BITS_PER_LEVEL;
430 bool changed = false;
431 size_t i;
432
433 i = pos;
434 if (i < lastpos) {
435 uint64_t next = (start | (BITS_PER_LONG - 1)) + 1;
436
437 /* Here we need a more complex test than when setting bits. Even if
438 * something was changed, we must not blank bits in the upper level
439 * unless the lower-level word became entirely zero. So, remove pos
440 * from the upper-level range if bits remain set.
441 */
442 if (hb_reset_elem(&hb->levels[level][i], start, next - 1)) {
443 changed = true;
444 } else {
445 pos++;
446 }
447
448 for (;;) {
449 start = next;
450 next += BITS_PER_LONG;
451 if (++i == lastpos) {
452 break;
453 }
454 changed |= (hb->levels[level][i] != 0);
455 hb->levels[level][i] = 0UL;
456 }
457 }
458
459 /* Same as above, this time for lastpos. */
460 if (hb_reset_elem(&hb->levels[level][i], start, last)) {
461 changed = true;
462 } else {
463 lastpos--;
464 }
465
466 if (level > 0 && changed) {
467 hb_reset_between(hb, level - 1, pos, lastpos);
468 }
469
470 return changed;
471
472}
473
474void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count)
475{
476 /* Compute range in the last layer. */
477 uint64_t first;
478 uint64_t last = start + count - 1;
479
480 trace_hbitmap_reset(hb, start, count,
481 start >> hb->granularity, last >> hb->granularity);
482
483 first = start >> hb->granularity;
484 last >>= hb->granularity;
485 assert(last < hb->size);
486
487 hb->count -= hb_count_between(hb, first, last);
488 if (hb_reset_between(hb, HBITMAP_LEVELS - 1, first, last) &&
489 hb->meta) {
490 hbitmap_set(hb->meta, start, count);
491 }
492}
493
494void hbitmap_reset_all(HBitmap *hb)
495{
496 unsigned int i;
497
498 /* Same as hbitmap_alloc() except for memset() instead of malloc() */
499 for (i = HBITMAP_LEVELS; --i >= 1; ) {
500 memset(hb->levels[i], 0, hb->sizes[i] * sizeof(unsigned long));
501 }
502
503 hb->levels[0][0] = 1UL << (BITS_PER_LONG - 1);
504 hb->count = 0;
505}
506
507bool hbitmap_is_serializable(const HBitmap *hb)
508{
509 /* Every serialized chunk must be aligned to 64 bits so that endianness
510 * requirements can be fulfilled on both 64 bit and 32 bit hosts.
511 * We have hbitmap_serialization_align() which converts this
512 * alignment requirement from bitmap bits to items covered (e.g. sectors).
513 * That value is:
514 * 64 << hb->granularity
515 * Since this value must not exceed UINT64_MAX, hb->granularity must be
516 * less than 58 (== 64 - 6, where 6 is ld(64), i.e. 1 << 6 == 64).
517 *
518 * In order for hbitmap_serialization_align() to always return a
519 * meaningful value, bitmaps that are to be serialized must have a
520 * granularity of less than 58. */
521
522 return hb->granularity < 58;
523}
524
525bool hbitmap_get(const HBitmap *hb, uint64_t item)
526{
527 /* Compute position and bit in the last layer. */
528 uint64_t pos = item >> hb->granularity;
529 unsigned long bit = 1UL << (pos & (BITS_PER_LONG - 1));
530 assert(pos < hb->size);
531
532 return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0;
533}
534
535uint64_t hbitmap_serialization_align(const HBitmap *hb)
536{
537 assert(hbitmap_is_serializable(hb));
538
539 /* Require at least 64 bit granularity to be safe on both 64 bit and 32 bit
540 * hosts. */
541 return UINT64_C(64) << hb->granularity;
542}
543
544/* Start should be aligned to serialization granularity, chunk size should be
545 * aligned to serialization granularity too, except for last chunk.
546 */
547static void serialization_chunk(const HBitmap *hb,
548 uint64_t start, uint64_t count,
549 unsigned long **first_el, uint64_t *el_count)
550{
551 uint64_t last = start + count - 1;
552 uint64_t gran = hbitmap_serialization_align(hb);
553
554 assert((start & (gran - 1)) == 0);
555 assert((last >> hb->granularity) < hb->size);
556 if ((last >> hb->granularity) != hb->size - 1) {
557 assert((count & (gran - 1)) == 0);
558 }
559
560 start = (start >> hb->granularity) >> BITS_PER_LEVEL;
561 last = (last >> hb->granularity) >> BITS_PER_LEVEL;
562
563 *first_el = &hb->levels[HBITMAP_LEVELS - 1][start];
564 *el_count = last - start + 1;
565}
566
567uint64_t hbitmap_serialization_size(const HBitmap *hb,
568 uint64_t start, uint64_t count)
569{
570 uint64_t el_count;
571 unsigned long *cur;
572
573 if (!count) {
574 return 0;
575 }
576 serialization_chunk(hb, start, count, &cur, &el_count);
577
578 return el_count * sizeof(unsigned long);
579}
580
581void hbitmap_serialize_part(const HBitmap *hb, uint8_t *buf,
582 uint64_t start, uint64_t count)
583{
584 uint64_t el_count;
585 unsigned long *cur, *end;
586
587 if (!count) {
588 return;
589 }
590 serialization_chunk(hb, start, count, &cur, &el_count);
591 end = cur + el_count;
592
593 while (cur != end) {
594 unsigned long el =
595 (BITS_PER_LONG == 32 ? cpu_to_le32(*cur) : cpu_to_le64(*cur));
596
597 memcpy(buf, &el, sizeof(el));
598 buf += sizeof(el);
599 cur++;
600 }
601}
602
603void hbitmap_deserialize_part(HBitmap *hb, uint8_t *buf,
604 uint64_t start, uint64_t count,
605 bool finish)
606{
607 uint64_t el_count;
608 unsigned long *cur, *end;
609
610 if (!count) {
611 return;
612 }
613 serialization_chunk(hb, start, count, &cur, &el_count);
614 end = cur + el_count;
615
616 while (cur != end) {
617 memcpy(cur, buf, sizeof(*cur));
618
619 if (BITS_PER_LONG == 32) {
620 le32_to_cpus((uint32_t *)cur);
621 } else {
622 le64_to_cpus((uint64_t *)cur);
623 }
624
625 buf += sizeof(unsigned long);
626 cur++;
627 }
628 if (finish) {
629 hbitmap_deserialize_finish(hb);
630 }
631}
632
633void hbitmap_deserialize_zeroes(HBitmap *hb, uint64_t start, uint64_t count,
634 bool finish)
635{
636 uint64_t el_count;
637 unsigned long *first;
638
639 if (!count) {
640 return;
641 }
642 serialization_chunk(hb, start, count, &first, &el_count);
643
644 memset(first, 0, el_count * sizeof(unsigned long));
645 if (finish) {
646 hbitmap_deserialize_finish(hb);
647 }
648}
649
650void hbitmap_deserialize_ones(HBitmap *hb, uint64_t start, uint64_t count,
651 bool finish)
652{
653 uint64_t el_count;
654 unsigned long *first;
655
656 if (!count) {
657 return;
658 }
659 serialization_chunk(hb, start, count, &first, &el_count);
660
661 memset(first, 0xff, el_count * sizeof(unsigned long));
662 if (finish) {
663 hbitmap_deserialize_finish(hb);
664 }
665}
666
667void hbitmap_deserialize_finish(HBitmap *bitmap)
668{
669 int64_t i, size, prev_size;
670 int lev;
671
672 /* restore levels starting from penultimate to zero level, assuming
673 * that the last level is ok */
674 size = MAX((bitmap->size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
675 for (lev = HBITMAP_LEVELS - 1; lev-- > 0; ) {
676 prev_size = size;
677 size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
678 memset(bitmap->levels[lev], 0, size * sizeof(unsigned long));
679
680 for (i = 0; i < prev_size; ++i) {
681 if (bitmap->levels[lev + 1][i]) {
682 bitmap->levels[lev][i >> BITS_PER_LEVEL] |=
683 1UL << (i & (BITS_PER_LONG - 1));
684 }
685 }
686 }
687
688 bitmap->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);
689 bitmap->count = hb_count_between(bitmap, 0, bitmap->size - 1);
690}
691
692void hbitmap_free(HBitmap *hb)
693{
694 unsigned i;
695 assert(!hb->meta);
696 for (i = HBITMAP_LEVELS; i-- > 0; ) {
697 g_free(hb->levels[i]);
698 }
699 g_free(hb);
700}
701
702HBitmap *hbitmap_alloc(uint64_t size, int granularity)
703{
704 HBitmap *hb = g_new0(struct HBitmap, 1);
705 unsigned i;
706
707 hb->orig_size = size;
708
709 assert(granularity >= 0 && granularity < 64);
710 size = (size + (1ULL << granularity) - 1) >> granularity;
711 assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
712
713 hb->size = size;
714 hb->granularity = granularity;
715 for (i = HBITMAP_LEVELS; i-- > 0; ) {
716 size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
717 hb->sizes[i] = size;
718 hb->levels[i] = g_new0(unsigned long, size);
719 }
720
721 /* We necessarily have free bits in level 0 due to the definition
722 * of HBITMAP_LEVELS, so use one for a sentinel. This speeds up
723 * hbitmap_iter_skip_words.
724 */
725 assert(size == 1);
726 hb->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);
727 return hb;
728}
729
730void hbitmap_truncate(HBitmap *hb, uint64_t size)
731{
732 bool shrink;
733 unsigned i;
734 uint64_t num_elements = size;
735 uint64_t old;
736
737 hb->orig_size = size;
738
739 /* Size comes in as logical elements, adjust for granularity. */
740 size = (size + (1ULL << hb->granularity) - 1) >> hb->granularity;
741 assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
742 shrink = size < hb->size;
743
744 /* bit sizes are identical; nothing to do. */
745 if (size == hb->size) {
746 return;
747 }
748
749 /* If we're losing bits, let's clear those bits before we invalidate all of
750 * our invariants. This helps keep the bitcount consistent, and will prevent
751 * us from carrying around garbage bits beyond the end of the map.
752 */
753 if (shrink) {
754 /* Don't clear partial granularity groups;
755 * start at the first full one. */
756 uint64_t start = ROUND_UP(num_elements, UINT64_C(1) << hb->granularity);
757 uint64_t fix_count = (hb->size << hb->granularity) - start;
758
759 assert(fix_count);
760 hbitmap_reset(hb, start, fix_count);
761 }
762
763 hb->size = size;
764 for (i = HBITMAP_LEVELS; i-- > 0; ) {
765 size = MAX(BITS_TO_LONGS(size), 1);
766 if (hb->sizes[i] == size) {
767 break;
768 }
769 old = hb->sizes[i];
770 hb->sizes[i] = size;
771 hb->levels[i] = g_realloc(hb->levels[i], size * sizeof(unsigned long));
772 if (!shrink) {
773 memset(&hb->levels[i][old], 0x00,
774 (size - old) * sizeof(*hb->levels[i]));
775 }
776 }
777 if (hb->meta) {
778 hbitmap_truncate(hb->meta, hb->size << hb->granularity);
779 }
780}
781
782bool hbitmap_can_merge(const HBitmap *a, const HBitmap *b)
783{
784 return (a->orig_size == b->orig_size);
785}
786
787/**
788 * hbitmap_sparse_merge: performs dst = dst | src
789 * works with differing granularities.
790 * best used when src is sparsely populated.
791 */
792static void hbitmap_sparse_merge(HBitmap *dst, const HBitmap *src)
793{
794 uint64_t offset = 0;
795 uint64_t count = src->orig_size;
796
797 while (hbitmap_next_dirty_area(src, &offset, &count)) {
798 hbitmap_set(dst, offset, count);
799 offset += count;
800 if (offset >= src->orig_size) {
801 break;
802 }
803 count = src->orig_size - offset;
804 }
805}
806
807/**
808 * Given HBitmaps A and B, let R := A (BITOR) B.
809 * Bitmaps A and B will not be modified,
810 * except when bitmap R is an alias of A or B.
811 *
812 * @return true if the merge was successful,
813 * false if it was not attempted.
814 */
815bool hbitmap_merge(const HBitmap *a, const HBitmap *b, HBitmap *result)
816{
817 int i;
818 uint64_t j;
819
820 if (!hbitmap_can_merge(a, b) || !hbitmap_can_merge(a, result)) {
821 return false;
822 }
823 assert(hbitmap_can_merge(b, result));
824
825 if ((!hbitmap_count(a) && result == b) ||
826 (!hbitmap_count(b) && result == a)) {
827 return true;
828 }
829
830 if (!hbitmap_count(a) && !hbitmap_count(b)) {
831 hbitmap_reset_all(result);
832 return true;
833 }
834
835 if (a->granularity != b->granularity) {
836 if ((a != result) && (b != result)) {
837 hbitmap_reset_all(result);
838 }
839 if (a != result) {
840 hbitmap_sparse_merge(result, a);
841 }
842 if (b != result) {
843 hbitmap_sparse_merge(result, b);
844 }
845 return true;
846 }
847
848 /* This merge is O(size), as BITS_PER_LONG and HBITMAP_LEVELS are constant.
849 * It may be possible to improve running times for sparsely populated maps
850 * by using hbitmap_iter_next, but this is suboptimal for dense maps.
851 */
852 assert(a->size == b->size);
853 for (i = HBITMAP_LEVELS - 1; i >= 0; i--) {
854 for (j = 0; j < a->sizes[i]; j++) {
855 result->levels[i][j] = a->levels[i][j] | b->levels[i][j];
856 }
857 }
858
859 /* Recompute the dirty count */
860 result->count = hb_count_between(result, 0, result->size - 1);
861
862 return true;
863}
864
865HBitmap *hbitmap_create_meta(HBitmap *hb, int chunk_size)
866{
867 assert(!(chunk_size & (chunk_size - 1)));
868 assert(!hb->meta);
869 hb->meta = hbitmap_alloc(hb->size << hb->granularity,
870 hb->granularity + ctz32(chunk_size));
871 return hb->meta;
872}
873
874void hbitmap_free_meta(HBitmap *hb)
875{
876 assert(hb->meta);
877 hbitmap_free(hb->meta);
878 hb->meta = NULL;
879}
880
881char *hbitmap_sha256(const HBitmap *bitmap, Error **errp)
882{
883 size_t size = bitmap->sizes[HBITMAP_LEVELS - 1] * sizeof(unsigned long);
884 char *data = (char *)bitmap->levels[HBITMAP_LEVELS - 1];
885 char *hash = NULL;
886 qcrypto_hash_digest(QCRYPTO_HASH_ALG_SHA256, data, size, &hash, errp);
887
888 return hash;
889}
890