xref: /openbmc/qemu/util/hbitmap.c (revision a4d5224c)
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 
55 struct 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  */
hbitmap_iter_skip_words(HBitmapIter * hbi)107 static unsigned 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 
hbitmap_iter_next(HBitmapIter * hbi)149 int64_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 
hbitmap_iter_init(HBitmapIter * hbi,const HBitmap * hb,uint64_t first)169 void 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 
hbitmap_next_dirty(const HBitmap * hb,int64_t start,int64_t count)196 int64_t hbitmap_next_dirty(const HBitmap *hb, int64_t start, int64_t count)
197 {
198     HBitmapIter hbi;
199     int64_t first_dirty_off;
200     uint64_t end;
201 
202     assert(start >= 0 && count >= 0);
203 
204     if (start >= hb->orig_size || count == 0) {
205         return -1;
206     }
207 
208     end = count > hb->orig_size - start ? hb->orig_size : start + count;
209 
210     hbitmap_iter_init(&hbi, hb, start);
211     first_dirty_off = hbitmap_iter_next(&hbi);
212 
213     if (first_dirty_off < 0 || first_dirty_off >= end) {
214         return -1;
215     }
216 
217     return MAX(start, first_dirty_off);
218 }
219 
hbitmap_next_zero(const HBitmap * hb,int64_t start,int64_t count)220 int64_t hbitmap_next_zero(const HBitmap *hb, int64_t start, int64_t count)
221 {
222     size_t pos = (start >> hb->granularity) >> BITS_PER_LEVEL;
223     unsigned long *last_lev = hb->levels[HBITMAP_LEVELS - 1];
224     unsigned long cur = last_lev[pos];
225     unsigned start_bit_offset;
226     uint64_t end_bit, sz;
227     int64_t res;
228 
229     assert(start >= 0 && count >= 0);
230 
231     if (start >= hb->orig_size || count == 0) {
232         return -1;
233     }
234 
235     end_bit = count > hb->orig_size - start ?
236                 hb->size :
237                 ((start + count - 1) >> hb->granularity) + 1;
238     sz = (end_bit + BITS_PER_LONG - 1) >> BITS_PER_LEVEL;
239 
240     /* There may be some zero bits in @cur before @start. We are not interested
241      * in them, let's set them.
242      */
243     start_bit_offset = (start >> hb->granularity) & (BITS_PER_LONG - 1);
244     cur |= (1UL << start_bit_offset) - 1;
245     assert((start >> hb->granularity) < hb->size);
246 
247     if (cur == (unsigned long)-1) {
248         do {
249             pos++;
250         } while (pos < sz && last_lev[pos] == (unsigned long)-1);
251 
252         if (pos >= sz) {
253             return -1;
254         }
255 
256         cur = last_lev[pos];
257     }
258 
259     res = (pos << BITS_PER_LEVEL) + ctol(cur);
260     if (res >= end_bit) {
261         return -1;
262     }
263 
264     res = res << hb->granularity;
265     if (res < start) {
266         assert(((start - res) >> hb->granularity) == 0);
267         return start;
268     }
269 
270     return res;
271 }
272 
hbitmap_next_dirty_area(const HBitmap * hb,int64_t start,int64_t end,int64_t max_dirty_count,int64_t * dirty_start,int64_t * dirty_count)273 bool hbitmap_next_dirty_area(const HBitmap *hb, int64_t start, int64_t end,
274                              int64_t max_dirty_count,
275                              int64_t *dirty_start, int64_t *dirty_count)
276 {
277     int64_t next_zero;
278 
279     assert(start >= 0 && end >= 0 && max_dirty_count > 0);
280 
281     end = MIN(end, hb->orig_size);
282     if (start >= end) {
283         return false;
284     }
285 
286     start = hbitmap_next_dirty(hb, start, end - start);
287     if (start < 0) {
288         return false;
289     }
290 
291     end = start + MIN(end - start, max_dirty_count);
292 
293     next_zero = hbitmap_next_zero(hb, start, end - start);
294     if (next_zero >= 0) {
295         end = next_zero;
296     }
297 
298     *dirty_start = start;
299     *dirty_count = end - start;
300 
301     return true;
302 }
303 
hbitmap_status(const HBitmap * hb,int64_t start,int64_t count,int64_t * pnum)304 bool hbitmap_status(const HBitmap *hb, int64_t start, int64_t count,
305                     int64_t *pnum)
306 {
307     int64_t next_dirty, next_zero;
308 
309     assert(start >= 0);
310     assert(count > 0);
311     assert(start + count <= hb->orig_size);
312 
313     next_dirty = hbitmap_next_dirty(hb, start, count);
314     if (next_dirty == -1) {
315         *pnum = count;
316         return false;
317     }
318 
319     if (next_dirty > start) {
320         *pnum = next_dirty - start;
321         return false;
322     }
323 
324     assert(next_dirty == start);
325 
326     next_zero = hbitmap_next_zero(hb, start, count);
327     if (next_zero == -1) {
328         *pnum = count;
329         return true;
330     }
331 
332     assert(next_zero > start);
333     *pnum = next_zero - start;
334     return true;
335 }
336 
hbitmap_empty(const HBitmap * hb)337 bool hbitmap_empty(const HBitmap *hb)
338 {
339     return hb->count == 0;
340 }
341 
hbitmap_granularity(const HBitmap * hb)342 int hbitmap_granularity(const HBitmap *hb)
343 {
344     return hb->granularity;
345 }
346 
hbitmap_count(const HBitmap * hb)347 uint64_t hbitmap_count(const HBitmap *hb)
348 {
349     return hb->count << hb->granularity;
350 }
351 
352 /**
353  * hbitmap_iter_next_word:
354  * @hbi: HBitmapIter to operate on.
355  * @p_cur: Location where to store the next non-zero word.
356  *
357  * Return the index of the next nonzero word that is set in @hbi's
358  * associated HBitmap, and set *p_cur to the content of that word
359  * (bits before the index that was passed to hbitmap_iter_init are
360  * trimmed on the first call).  Return -1, and set *p_cur to zero,
361  * if all remaining words are zero.
362  */
hbitmap_iter_next_word(HBitmapIter * hbi,unsigned long * p_cur)363 static size_t hbitmap_iter_next_word(HBitmapIter *hbi, unsigned long *p_cur)
364 {
365     unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1];
366 
367     if (cur == 0) {
368         cur = hbitmap_iter_skip_words(hbi);
369         if (cur == 0) {
370             *p_cur = 0;
371             return -1;
372         }
373     }
374 
375     /* The next call will resume work from the next word.  */
376     hbi->cur[HBITMAP_LEVELS - 1] = 0;
377     *p_cur = cur;
378     return hbi->pos;
379 }
380 
381 /* Count the number of set bits between start and end, not accounting for
382  * the granularity.  Also an example of how to use hbitmap_iter_next_word.
383  */
hb_count_between(HBitmap * hb,uint64_t start,uint64_t last)384 static uint64_t hb_count_between(HBitmap *hb, uint64_t start, uint64_t last)
385 {
386     HBitmapIter hbi;
387     uint64_t count = 0;
388     uint64_t end = last + 1;
389     unsigned long cur;
390     size_t pos;
391 
392     hbitmap_iter_init(&hbi, hb, start << hb->granularity);
393     for (;;) {
394         pos = hbitmap_iter_next_word(&hbi, &cur);
395         if (pos >= (end >> BITS_PER_LEVEL)) {
396             break;
397         }
398         count += ctpopl(cur);
399     }
400 
401     if (pos == (end >> BITS_PER_LEVEL)) {
402         /* Drop bits representing the END-th and subsequent items.  */
403         int bit = end & (BITS_PER_LONG - 1);
404         cur &= (1UL << bit) - 1;
405         count += ctpopl(cur);
406     }
407 
408     return count;
409 }
410 
411 /* Setting starts at the last layer and propagates up if an element
412  * changes.
413  */
hb_set_elem(unsigned long * elem,uint64_t start,uint64_t last)414 static inline bool hb_set_elem(unsigned long *elem, uint64_t start, uint64_t last)
415 {
416     unsigned long mask;
417     unsigned long old;
418 
419     assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL));
420     assert(start <= last);
421 
422     mask = 2UL << (last & (BITS_PER_LONG - 1));
423     mask -= 1UL << (start & (BITS_PER_LONG - 1));
424     old = *elem;
425     *elem |= mask;
426     return old != *elem;
427 }
428 
429 /* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)...
430  * Returns true if at least one bit is changed. */
hb_set_between(HBitmap * hb,int level,uint64_t start,uint64_t last)431 static bool hb_set_between(HBitmap *hb, int level, uint64_t start,
432                            uint64_t last)
433 {
434     size_t pos = start >> BITS_PER_LEVEL;
435     size_t lastpos = last >> BITS_PER_LEVEL;
436     bool changed = false;
437     size_t i;
438 
439     i = pos;
440     if (i < lastpos) {
441         uint64_t next = (start | (BITS_PER_LONG - 1)) + 1;
442         changed |= hb_set_elem(&hb->levels[level][i], start, next - 1);
443         for (;;) {
444             start = next;
445             next += BITS_PER_LONG;
446             if (++i == lastpos) {
447                 break;
448             }
449             changed |= (hb->levels[level][i] == 0);
450             hb->levels[level][i] = ~0UL;
451         }
452     }
453     changed |= hb_set_elem(&hb->levels[level][i], start, last);
454 
455     /* If there was any change in this layer, we may have to update
456      * the one above.
457      */
458     if (level > 0 && changed) {
459         hb_set_between(hb, level - 1, pos, lastpos);
460     }
461     return changed;
462 }
463 
hbitmap_set(HBitmap * hb,uint64_t start,uint64_t count)464 void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count)
465 {
466     /* Compute range in the last layer.  */
467     uint64_t first, n;
468     uint64_t last = start + count - 1;
469 
470     if (count == 0) {
471         return;
472     }
473 
474     trace_hbitmap_set(hb, start, count,
475                       start >> hb->granularity, last >> hb->granularity);
476 
477     first = start >> hb->granularity;
478     last >>= hb->granularity;
479     assert(last < hb->size);
480     n = last - first + 1;
481 
482     hb->count += n - hb_count_between(hb, first, last);
483     if (hb_set_between(hb, HBITMAP_LEVELS - 1, first, last) &&
484         hb->meta) {
485         hbitmap_set(hb->meta, start, count);
486     }
487 }
488 
489 /* Resetting works the other way round: propagate up if the new
490  * value is zero.
491  */
hb_reset_elem(unsigned long * elem,uint64_t start,uint64_t last)492 static inline bool hb_reset_elem(unsigned long *elem, uint64_t start, uint64_t last)
493 {
494     unsigned long mask;
495     bool blanked;
496 
497     assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL));
498     assert(start <= last);
499 
500     mask = 2UL << (last & (BITS_PER_LONG - 1));
501     mask -= 1UL << (start & (BITS_PER_LONG - 1));
502     blanked = *elem != 0 && ((*elem & ~mask) == 0);
503     *elem &= ~mask;
504     return blanked;
505 }
506 
507 /* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)...
508  * Returns true if at least one bit is changed. */
hb_reset_between(HBitmap * hb,int level,uint64_t start,uint64_t last)509 static bool hb_reset_between(HBitmap *hb, int level, uint64_t start,
510                              uint64_t last)
511 {
512     size_t pos = start >> BITS_PER_LEVEL;
513     size_t lastpos = last >> BITS_PER_LEVEL;
514     bool changed = false;
515     size_t i;
516 
517     i = pos;
518     if (i < lastpos) {
519         uint64_t next = (start | (BITS_PER_LONG - 1)) + 1;
520 
521         /* Here we need a more complex test than when setting bits.  Even if
522          * something was changed, we must not blank bits in the upper level
523          * unless the lower-level word became entirely zero.  So, remove pos
524          * from the upper-level range if bits remain set.
525          */
526         if (hb_reset_elem(&hb->levels[level][i], start, next - 1)) {
527             changed = true;
528         } else {
529             pos++;
530         }
531 
532         for (;;) {
533             start = next;
534             next += BITS_PER_LONG;
535             if (++i == lastpos) {
536                 break;
537             }
538             changed |= (hb->levels[level][i] != 0);
539             hb->levels[level][i] = 0UL;
540         }
541     }
542 
543     /* Same as above, this time for lastpos.  */
544     if (hb_reset_elem(&hb->levels[level][i], start, last)) {
545         changed = true;
546     } else {
547         lastpos--;
548     }
549 
550     if (level > 0 && changed) {
551         hb_reset_between(hb, level - 1, pos, lastpos);
552     }
553 
554     return changed;
555 
556 }
557 
hbitmap_reset(HBitmap * hb,uint64_t start,uint64_t count)558 void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count)
559 {
560     /* Compute range in the last layer.  */
561     uint64_t first;
562     uint64_t last = start + count - 1;
563     uint64_t gran = 1ULL << hb->granularity;
564 
565     if (count == 0) {
566         return;
567     }
568 
569     assert(QEMU_IS_ALIGNED(start, gran));
570     assert(QEMU_IS_ALIGNED(count, gran) || (start + count == hb->orig_size));
571 
572     trace_hbitmap_reset(hb, start, count,
573                         start >> hb->granularity, last >> hb->granularity);
574 
575     first = start >> hb->granularity;
576     last >>= hb->granularity;
577     assert(last < hb->size);
578 
579     hb->count -= hb_count_between(hb, first, last);
580     if (hb_reset_between(hb, HBITMAP_LEVELS - 1, first, last) &&
581         hb->meta) {
582         hbitmap_set(hb->meta, start, count);
583     }
584 }
585 
hbitmap_reset_all(HBitmap * hb)586 void hbitmap_reset_all(HBitmap *hb)
587 {
588     unsigned int i;
589 
590     /* Same as hbitmap_alloc() except for memset() instead of malloc() */
591     for (i = HBITMAP_LEVELS; --i >= 1; ) {
592         memset(hb->levels[i], 0, hb->sizes[i] * sizeof(unsigned long));
593     }
594 
595     hb->levels[0][0] = 1UL << (BITS_PER_LONG - 1);
596     hb->count = 0;
597 }
598 
hbitmap_is_serializable(const HBitmap * hb)599 bool hbitmap_is_serializable(const HBitmap *hb)
600 {
601     /* Every serialized chunk must be aligned to 64 bits so that endianness
602      * requirements can be fulfilled on both 64 bit and 32 bit hosts.
603      * We have hbitmap_serialization_align() which converts this
604      * alignment requirement from bitmap bits to items covered (e.g. sectors).
605      * That value is:
606      *    64 << hb->granularity
607      * Since this value must not exceed UINT64_MAX, hb->granularity must be
608      * less than 58 (== 64 - 6, where 6 is ld(64), i.e. 1 << 6 == 64).
609      *
610      * In order for hbitmap_serialization_align() to always return a
611      * meaningful value, bitmaps that are to be serialized must have a
612      * granularity of less than 58. */
613 
614     return hb->granularity < 58;
615 }
616 
hbitmap_get(const HBitmap * hb,uint64_t item)617 bool hbitmap_get(const HBitmap *hb, uint64_t item)
618 {
619     /* Compute position and bit in the last layer.  */
620     uint64_t pos = item >> hb->granularity;
621     unsigned long bit = 1UL << (pos & (BITS_PER_LONG - 1));
622     assert(pos < hb->size);
623 
624     return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0;
625 }
626 
hbitmap_serialization_align(const HBitmap * hb)627 uint64_t hbitmap_serialization_align(const HBitmap *hb)
628 {
629     assert(hbitmap_is_serializable(hb));
630 
631     /* Require at least 64 bit granularity to be safe on both 64 bit and 32 bit
632      * hosts. */
633     return UINT64_C(64) << hb->granularity;
634 }
635 
636 /* Start should be aligned to serialization granularity, chunk size should be
637  * aligned to serialization granularity too, except for last chunk.
638  */
serialization_chunk(const HBitmap * hb,uint64_t start,uint64_t count,unsigned long ** first_el,uint64_t * el_count)639 static void serialization_chunk(const HBitmap *hb,
640                                 uint64_t start, uint64_t count,
641                                 unsigned long **first_el, uint64_t *el_count)
642 {
643     uint64_t last = start + count - 1;
644     uint64_t gran = hbitmap_serialization_align(hb);
645 
646     assert((start & (gran - 1)) == 0);
647     assert((last >> hb->granularity) < hb->size);
648     if ((last >> hb->granularity) != hb->size - 1) {
649         assert((count & (gran - 1)) == 0);
650     }
651 
652     start = (start >> hb->granularity) >> BITS_PER_LEVEL;
653     last = (last >> hb->granularity) >> BITS_PER_LEVEL;
654 
655     *first_el = &hb->levels[HBITMAP_LEVELS - 1][start];
656     *el_count = last - start + 1;
657 }
658 
hbitmap_serialization_size(const HBitmap * hb,uint64_t start,uint64_t count)659 uint64_t hbitmap_serialization_size(const HBitmap *hb,
660                                     uint64_t start, uint64_t count)
661 {
662     uint64_t el_count;
663     unsigned long *cur;
664 
665     if (!count) {
666         return 0;
667     }
668     serialization_chunk(hb, start, count, &cur, &el_count);
669 
670     return el_count * sizeof(unsigned long);
671 }
672 
hbitmap_serialize_part(const HBitmap * hb,uint8_t * buf,uint64_t start,uint64_t count)673 void hbitmap_serialize_part(const HBitmap *hb, uint8_t *buf,
674                             uint64_t start, uint64_t count)
675 {
676     uint64_t el_count;
677     unsigned long *cur, *end;
678 
679     if (!count) {
680         return;
681     }
682     serialization_chunk(hb, start, count, &cur, &el_count);
683     end = cur + el_count;
684 
685     while (cur != end) {
686         unsigned long el =
687             (BITS_PER_LONG == 32 ? cpu_to_le32(*cur) : cpu_to_le64(*cur));
688 
689         memcpy(buf, &el, sizeof(el));
690         buf += sizeof(el);
691         cur++;
692     }
693 }
694 
hbitmap_deserialize_part(HBitmap * hb,uint8_t * buf,uint64_t start,uint64_t count,bool finish)695 void hbitmap_deserialize_part(HBitmap *hb, uint8_t *buf,
696                               uint64_t start, uint64_t count,
697                               bool finish)
698 {
699     uint64_t el_count;
700     unsigned long *cur, *end;
701 
702     if (!count) {
703         return;
704     }
705     serialization_chunk(hb, start, count, &cur, &el_count);
706     end = cur + el_count;
707 
708     while (cur != end) {
709         memcpy(cur, buf, sizeof(*cur));
710 
711         if (BITS_PER_LONG == 32) {
712             le32_to_cpus((uint32_t *)cur);
713         } else {
714             le64_to_cpus((uint64_t *)cur);
715         }
716 
717         buf += sizeof(unsigned long);
718         cur++;
719     }
720     if (finish) {
721         hbitmap_deserialize_finish(hb);
722     }
723 }
724 
hbitmap_deserialize_zeroes(HBitmap * hb,uint64_t start,uint64_t count,bool finish)725 void hbitmap_deserialize_zeroes(HBitmap *hb, uint64_t start, uint64_t count,
726                                 bool finish)
727 {
728     uint64_t el_count;
729     unsigned long *first;
730 
731     if (!count) {
732         return;
733     }
734     serialization_chunk(hb, start, count, &first, &el_count);
735 
736     memset(first, 0, el_count * sizeof(unsigned long));
737     if (finish) {
738         hbitmap_deserialize_finish(hb);
739     }
740 }
741 
hbitmap_deserialize_ones(HBitmap * hb,uint64_t start,uint64_t count,bool finish)742 void hbitmap_deserialize_ones(HBitmap *hb, uint64_t start, uint64_t count,
743                               bool finish)
744 {
745     uint64_t el_count;
746     unsigned long *first;
747 
748     if (!count) {
749         return;
750     }
751     serialization_chunk(hb, start, count, &first, &el_count);
752 
753     memset(first, 0xff, el_count * sizeof(unsigned long));
754     if (finish) {
755         hbitmap_deserialize_finish(hb);
756     }
757 }
758 
hbitmap_deserialize_finish(HBitmap * bitmap)759 void hbitmap_deserialize_finish(HBitmap *bitmap)
760 {
761     int64_t i, size, prev_size;
762     int lev;
763 
764     /* restore levels starting from penultimate to zero level, assuming
765      * that the last level is ok */
766     size = MAX((bitmap->size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
767     for (lev = HBITMAP_LEVELS - 1; lev-- > 0; ) {
768         prev_size = size;
769         size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
770         memset(bitmap->levels[lev], 0, size * sizeof(unsigned long));
771 
772         for (i = 0; i < prev_size; ++i) {
773             if (bitmap->levels[lev + 1][i]) {
774                 bitmap->levels[lev][i >> BITS_PER_LEVEL] |=
775                     1UL << (i & (BITS_PER_LONG - 1));
776             }
777         }
778     }
779 
780     bitmap->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);
781     bitmap->count = hb_count_between(bitmap, 0, bitmap->size - 1);
782 }
783 
hbitmap_free(HBitmap * hb)784 void hbitmap_free(HBitmap *hb)
785 {
786     unsigned i;
787     assert(!hb->meta);
788     for (i = HBITMAP_LEVELS; i-- > 0; ) {
789         g_free(hb->levels[i]);
790     }
791     g_free(hb);
792 }
793 
hbitmap_alloc(uint64_t size,int granularity)794 HBitmap *hbitmap_alloc(uint64_t size, int granularity)
795 {
796     HBitmap *hb = g_new0(struct HBitmap, 1);
797     unsigned i;
798 
799     assert(size <= INT64_MAX);
800     hb->orig_size = size;
801 
802     assert(granularity >= 0 && granularity < 64);
803     size = (size + (1ULL << granularity) - 1) >> granularity;
804     assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
805 
806     hb->size = size;
807     hb->granularity = granularity;
808     for (i = HBITMAP_LEVELS; i-- > 0; ) {
809         size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
810         hb->sizes[i] = size;
811         hb->levels[i] = g_new0(unsigned long, size);
812     }
813 
814     /* We necessarily have free bits in level 0 due to the definition
815      * of HBITMAP_LEVELS, so use one for a sentinel.  This speeds up
816      * hbitmap_iter_skip_words.
817      */
818     assert(size == 1);
819     hb->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);
820     return hb;
821 }
822 
hbitmap_truncate(HBitmap * hb,uint64_t size)823 void hbitmap_truncate(HBitmap *hb, uint64_t size)
824 {
825     bool shrink;
826     unsigned i;
827     uint64_t num_elements = size;
828     uint64_t old;
829 
830     assert(size <= INT64_MAX);
831     hb->orig_size = size;
832 
833     /* Size comes in as logical elements, adjust for granularity. */
834     size = (size + (1ULL << hb->granularity) - 1) >> hb->granularity;
835     assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
836     shrink = size < hb->size;
837 
838     /* bit sizes are identical; nothing to do. */
839     if (size == hb->size) {
840         return;
841     }
842 
843     /* If we're losing bits, let's clear those bits before we invalidate all of
844      * our invariants. This helps keep the bitcount consistent, and will prevent
845      * us from carrying around garbage bits beyond the end of the map.
846      */
847     if (shrink) {
848         /* Don't clear partial granularity groups;
849          * start at the first full one. */
850         uint64_t start = ROUND_UP(num_elements, UINT64_C(1) << hb->granularity);
851         uint64_t fix_count = (hb->size << hb->granularity) - start;
852 
853         assert(fix_count);
854         hbitmap_reset(hb, start, fix_count);
855     }
856 
857     hb->size = size;
858     for (i = HBITMAP_LEVELS; i-- > 0; ) {
859         size = MAX(BITS_TO_LONGS(size), 1);
860         if (hb->sizes[i] == size) {
861             break;
862         }
863         old = hb->sizes[i];
864         hb->sizes[i] = size;
865         hb->levels[i] = g_renew(unsigned long, hb->levels[i], size);
866         if (!shrink) {
867             memset(&hb->levels[i][old], 0x00,
868                    (size - old) * sizeof(*hb->levels[i]));
869         }
870     }
871     if (hb->meta) {
872         hbitmap_truncate(hb->meta, hb->size << hb->granularity);
873     }
874 }
875 
876 /**
877  * hbitmap_sparse_merge: performs dst = dst | src
878  * works with differing granularities.
879  * best used when src is sparsely populated.
880  */
hbitmap_sparse_merge(HBitmap * dst,const HBitmap * src)881 static void hbitmap_sparse_merge(HBitmap *dst, const HBitmap *src)
882 {
883     int64_t offset;
884     int64_t count;
885 
886     for (offset = 0;
887          hbitmap_next_dirty_area(src, offset, src->orig_size, INT64_MAX,
888                                  &offset, &count);
889          offset += count)
890     {
891         hbitmap_set(dst, offset, count);
892     }
893 }
894 
895 /**
896  * Given HBitmaps A and B, let R := A (BITOR) B.
897  * Bitmaps A and B will not be modified,
898  *     except when bitmap R is an alias of A or B.
899  * Bitmaps must have same size.
900  */
hbitmap_merge(const HBitmap * a,const HBitmap * b,HBitmap * result)901 void hbitmap_merge(const HBitmap *a, const HBitmap *b, HBitmap *result)
902 {
903     int i;
904     uint64_t j;
905 
906     assert(a->orig_size == result->orig_size);
907     assert(b->orig_size == result->orig_size);
908 
909     if ((!hbitmap_count(a) && result == b) ||
910         (!hbitmap_count(b) && result == a)) {
911         return;
912     }
913 
914     if (!hbitmap_count(a) && !hbitmap_count(b)) {
915         hbitmap_reset_all(result);
916         return;
917     }
918 
919     if (a->granularity != b->granularity) {
920         if ((a != result) && (b != result)) {
921             hbitmap_reset_all(result);
922         }
923         if (a != result) {
924             hbitmap_sparse_merge(result, a);
925         }
926         if (b != result) {
927             hbitmap_sparse_merge(result, b);
928         }
929         return;
930     }
931 
932     /* This merge is O(size), as BITS_PER_LONG and HBITMAP_LEVELS are constant.
933      * It may be possible to improve running times for sparsely populated maps
934      * by using hbitmap_iter_next, but this is suboptimal for dense maps.
935      */
936     assert(a->size == b->size);
937     for (i = HBITMAP_LEVELS - 1; i >= 0; i--) {
938         for (j = 0; j < a->sizes[i]; j++) {
939             result->levels[i][j] = a->levels[i][j] | b->levels[i][j];
940         }
941     }
942 
943     /* Recompute the dirty count */
944     result->count = hb_count_between(result, 0, result->size - 1);
945 }
946 
hbitmap_sha256(const HBitmap * bitmap,Error ** errp)947 char *hbitmap_sha256(const HBitmap *bitmap, Error **errp)
948 {
949     size_t size = bitmap->sizes[HBITMAP_LEVELS - 1] * sizeof(unsigned long);
950     char *data = (char *)bitmap->levels[HBITMAP_LEVELS - 1];
951     char *hash = NULL;
952     qcrypto_hash_digest(QCRYPTO_HASH_ALG_SHA256, data, size, &hash, errp);
953 
954     return hash;
955 }
956