9  * later.  See the COPYING file in the top-level directory.
14 #include "qemu/host-utils.h"
25  * granularity; in all levels except the last, bit N is set iff the N-th
27  * completes on the last level it can examine the 2nd-last level to quickly
29  * powers thereof (32 on 32-bit machines).
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
52  * O(logB n) as in the non-amortized complexity).
71      * bit of each group.  Here is an example of operations in a size-16,
72      * granularity-1 HBitmap:
95      * Note that all bitmaps have the same number of levels.  Even a 1-bit
104 /* Advance hbi to the next nonzero word and return it.  hbi->pos
109     size_t pos = hbi->pos;  in hbitmap_iter_skip_words()
110     const HBitmap *hb = hbi->hb;  in hbitmap_iter_skip_words()
111     unsigned i = HBITMAP_LEVELS - 1;  in hbitmap_iter_skip_words()
115         i--;  in hbitmap_iter_skip_words()
117         cur = hbi->cur[i] & hb->levels[i][pos];  in hbitmap_iter_skip_words()
126     if (i == 0 && cur == (1UL << (BITS_PER_LONG - 1))) {  in hbitmap_iter_skip_words()
129     for (; i < HBITMAP_LEVELS - 1; i++) {  in hbitmap_iter_skip_words()
132          * the low-order bits.  in hbitmap_iter_skip_words()
136         hbi->cur[i] = cur & (cur - 1);  in hbitmap_iter_skip_words()
139         cur = hb->levels[i + 1][pos];  in hbitmap_iter_skip_words()
142     hbi->pos = pos;  in hbitmap_iter_skip_words()
143     trace_hbitmap_iter_skip_words(hbi->hb, hbi, pos, cur);  in hbitmap_iter_skip_words()
151     unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1] &  in hbitmap_iter_next()
152             hbi->hb->levels[HBITMAP_LEVELS - 1][hbi->pos];  in hbitmap_iter_next()
153     int64_t item;  in hbitmap_iter_next()  local
158             return -1;  in hbitmap_iter_next()
163     hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1);  in hbitmap_iter_next()
164     item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + ctzl(cur);  in hbitmap_iter_next()
166     return item << hbi->granularity;  in hbitmap_iter_next()
174     hbi->hb = hb;  in hbitmap_iter_init()
175     pos = first >> hb->granularity;  in hbitmap_iter_init()
176     assert(pos < hb->size);  in hbitmap_iter_init()
177     hbi->pos = pos >> BITS_PER_LEVEL;  in hbitmap_iter_init()
178     hbi->granularity = hb->granularity;  in hbitmap_iter_init()
180     for (i = HBITMAP_LEVELS; i-- > 0; ) {  in hbitmap_iter_init()
181         bit = pos & (BITS_PER_LONG - 1);  in hbitmap_iter_init()
185         hbi->cur[i] = hb->levels[i][pos] & ~((1UL << bit) - 1);  in hbitmap_iter_init()
190         if (i != HBITMAP_LEVELS - 1) {  in hbitmap_iter_init()
191             hbi->cur[i] &= ~(1UL << bit);  in hbitmap_iter_init()
204     if (start >= hb->orig_size || count == 0) {  in hbitmap_next_dirty()
205         return -1;  in hbitmap_next_dirty()
208     end = count > hb->orig_size - start ? hb->orig_size : start + count;  in hbitmap_next_dirty()
214         return -1;  in hbitmap_next_dirty()
222     size_t pos = (start >> hb->granularity) >> BITS_PER_LEVEL;  in hbitmap_next_zero()
223     unsigned long *last_lev = hb->levels[HBITMAP_LEVELS - 1];  in hbitmap_next_zero()
231     if (start >= hb->orig_size || count == 0) {  in hbitmap_next_zero()
232         return -1;  in hbitmap_next_zero()
235     end_bit = count > hb->orig_size - start ?  in hbitmap_next_zero()
236                 hb->size :  in hbitmap_next_zero()
237                 ((start + count - 1) >> hb->granularity) + 1;  in hbitmap_next_zero()
238     sz = (end_bit + BITS_PER_LONG - 1) >> BITS_PER_LEVEL;  in hbitmap_next_zero()
243     start_bit_offset = (start >> hb->granularity) & (BITS_PER_LONG - 1);  in hbitmap_next_zero()
244     cur |= (1UL << start_bit_offset) - 1;  in hbitmap_next_zero()
245     assert((start >> hb->granularity) < hb->size);  in hbitmap_next_zero()
247     if (cur == (unsigned long)-1) {  in hbitmap_next_zero()
250         } while (pos < sz && last_lev[pos] == (unsigned long)-1);  in hbitmap_next_zero()
253             return -1;  in hbitmap_next_zero()
261         return -1;  in hbitmap_next_zero()
264     res = res << hb->granularity;  in hbitmap_next_zero()
266         assert(((start - res) >> hb->granularity) == 0);  in hbitmap_next_zero()
281     end = MIN(end, hb->orig_size);  in hbitmap_next_dirty_area()
286     start = hbitmap_next_dirty(hb, start, end - start);  in hbitmap_next_dirty_area()
291     end = start + MIN(end - start, max_dirty_count);  in hbitmap_next_dirty_area()
293     next_zero = hbitmap_next_zero(hb, start, end - start);  in hbitmap_next_dirty_area()
299     *dirty_count = end - start;  in hbitmap_next_dirty_area()
311     assert(start + count <= hb->orig_size);  in hbitmap_status()
314     if (next_dirty == -1) {  in hbitmap_status()
320         *pnum = next_dirty - start;  in hbitmap_status()
327     if (next_zero == -1) {  in hbitmap_status()
333     *pnum = next_zero - start;  in hbitmap_status()
339     return hb->count == 0;  in hbitmap_empty()
344     return hb->granularity;  in hbitmap_granularity()
349     return hb->count << hb->granularity;  in hbitmap_count()
355  * @p_cur: Location where to store the next non-zero word.
360  * trimmed on the first call).  Return -1, and set *p_cur to zero,
365     unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1];  in hbitmap_iter_next_word()
371             return -1;  in hbitmap_iter_next_word()
376     hbi->cur[HBITMAP_LEVELS - 1] = 0;  in hbitmap_iter_next_word()
378     return hbi->pos;  in hbitmap_iter_next_word()
392     hbitmap_iter_init(&hbi, hb, start << hb->granularity);  in hb_count_between()
402         /* Drop bits representing the END-th and subsequent items.  */  in hb_count_between()
403         int bit = end & (BITS_PER_LONG - 1);  in hb_count_between()
404         cur &= (1UL << bit) - 1;  in hb_count_between()
422     mask = 2UL << (last & (BITS_PER_LONG - 1));  in hb_set_elem()
423     mask -= 1UL << (start & (BITS_PER_LONG - 1));  in hb_set_elem()
441         uint64_t next = (start | (BITS_PER_LONG - 1)) + 1;  in hb_set_between()
442         changed |= hb_set_elem(&hb->levels[level][i], start, next - 1);  in hb_set_between()
449             changed |= (hb->levels[level][i] == 0);  in hb_set_between()
450             hb->levels[level][i] = ~0UL;  in hb_set_between()
453     changed |= hb_set_elem(&hb->levels[level][i], start, last);  in hb_set_between()
459         hb_set_between(hb, level - 1, pos, lastpos);  in hb_set_between()
468     uint64_t last = start + count - 1;  in hbitmap_set()
475                       start >> hb->granularity, last >> hb->granularity);  in hbitmap_set()
477     first = start >> hb->granularity;  in hbitmap_set()
478     last >>= hb->granularity;  in hbitmap_set()
479     assert(last < hb->size);  in hbitmap_set()
480     n = last - first + 1;  in hbitmap_set()
482     hb->count += n - hb_count_between(hb, first, last);  in hbitmap_set()
483     if (hb_set_between(hb, HBITMAP_LEVELS - 1, first, last) &&  in hbitmap_set()
484         hb->meta) {  in hbitmap_set()
485         hbitmap_set(hb->meta, start, count);  in hbitmap_set()
500     mask = 2UL << (last & (BITS_PER_LONG - 1));  in hb_reset_elem()
501     mask -= 1UL << (start & (BITS_PER_LONG - 1));  in hb_reset_elem()
519         uint64_t next = (start | (BITS_PER_LONG - 1)) + 1;  in hb_reset_between()
523          * unless the lower-level word became entirely zero.  So, remove pos  in hb_reset_between()
524          * from the upper-level range if bits remain set.  in hb_reset_between()
526         if (hb_reset_elem(&hb->levels[level][i], start, next - 1)) {  in hb_reset_between()
538             changed |= (hb->levels[level][i] != 0);  in hb_reset_between()
539             hb->levels[level][i] = 0UL;  in hb_reset_between()
544     if (hb_reset_elem(&hb->levels[level][i], start, last)) {  in hb_reset_between()
547         lastpos--;  in hb_reset_between()
551         hb_reset_between(hb, level - 1, pos, lastpos);  in hb_reset_between()
562     uint64_t last = start + count - 1;  in hbitmap_reset()
563     uint64_t gran = 1ULL << hb->granularity;  in hbitmap_reset()
570     assert(QEMU_IS_ALIGNED(count, gran) || (start + count == hb->orig_size));  in hbitmap_reset()
573                         start >> hb->granularity, last >> hb->granularity);  in hbitmap_reset()
575     first = start >> hb->granularity;  in hbitmap_reset()
576     last >>= hb->granularity;  in hbitmap_reset()
577     assert(last < hb->size);  in hbitmap_reset()
579     hb->count -= hb_count_between(hb, first, last);  in hbitmap_reset()
580     if (hb_reset_between(hb, HBITMAP_LEVELS - 1, first, last) &&  in hbitmap_reset()
581         hb->meta) {  in hbitmap_reset()
582         hbitmap_set(hb->meta, start, count);  in hbitmap_reset()
591     for (i = HBITMAP_LEVELS; --i >= 1; ) {  in hbitmap_reset_all()
592         memset(hb->levels[i], 0, hb->sizes[i] * sizeof(unsigned long));  in hbitmap_reset_all()
595     hb->levels[0][0] = 1UL << (BITS_PER_LONG - 1);  in hbitmap_reset_all()
596     hb->count = 0;  in hbitmap_reset_all()
606      *    64 << hb->granularity  in hbitmap_is_serializable()
607      * Since this value must not exceed UINT64_MAX, hb->granularity must be  in hbitmap_is_serializable()
608      * less than 58 (== 64 - 6, where 6 is ld(64), i.e. 1 << 6 == 64).  in hbitmap_is_serializable()
614     return hb->granularity < 58;  in hbitmap_is_serializable()
617 bool hbitmap_get(const HBitmap *hb, uint64_t item)  in hbitmap_get()  argument
620     uint64_t pos = item >> hb->granularity;  in hbitmap_get()
621     unsigned long bit = 1UL << (pos & (BITS_PER_LONG - 1));  in hbitmap_get()
622     assert(pos < hb->size);  in hbitmap_get()
624     return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0;  in hbitmap_get()
633     return UINT64_C(64) << hb->granularity;  in hbitmap_serialization_align()
643     uint64_t last = start + count - 1;  in serialization_chunk()
646     assert((start & (gran - 1)) == 0);  in serialization_chunk()
647     assert((last >> hb->granularity) < hb->size);  in serialization_chunk()
648     if ((last >> hb->granularity) != hb->size - 1) {  in serialization_chunk()
649         assert((count & (gran - 1)) == 0);  in serialization_chunk()
652     start = (start >> hb->granularity) >> BITS_PER_LEVEL;  in serialization_chunk()
653     last = (last >> hb->granularity) >> BITS_PER_LEVEL;  in serialization_chunk()
655     *first_el = &hb->levels[HBITMAP_LEVELS - 1][start];  in serialization_chunk()
656     *el_count = last - start + 1;  in serialization_chunk()
766     size = MAX((bitmap->size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);  in hbitmap_deserialize_finish()
767     for (lev = HBITMAP_LEVELS - 1; lev-- > 0; ) {  in hbitmap_deserialize_finish()
769         size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);  in hbitmap_deserialize_finish()
770         memset(bitmap->levels[lev], 0, size * sizeof(unsigned long));  in hbitmap_deserialize_finish()
773             if (bitmap->levels[lev + 1][i]) {  in hbitmap_deserialize_finish()
774                 bitmap->levels[lev][i >> BITS_PER_LEVEL] |=  in hbitmap_deserialize_finish()
775                     1UL << (i & (BITS_PER_LONG - 1));  in hbitmap_deserialize_finish()
780     bitmap->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);  in hbitmap_deserialize_finish()
781     bitmap->count = hb_count_between(bitmap, 0, bitmap->size - 1);  in hbitmap_deserialize_finish()
787     assert(!hb->meta);  in hbitmap_free()
788     for (i = HBITMAP_LEVELS; i-- > 0; ) {  in hbitmap_free()
789         g_free(hb->levels[i]);  in hbitmap_free()
800     hb->orig_size = size;  in hbitmap_alloc()
803     size = (size + (1ULL << granularity) - 1) >> granularity;  in hbitmap_alloc()
806     hb->size = size;  in hbitmap_alloc()
807     hb->granularity = granularity;  in hbitmap_alloc()
808     for (i = HBITMAP_LEVELS; i-- > 0; ) {  in hbitmap_alloc()
809         size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);  in hbitmap_alloc()
810         hb->sizes[i] = size;  in hbitmap_alloc()
811         hb->levels[i] = g_new0(unsigned long, size);  in hbitmap_alloc()
819     hb->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);  in hbitmap_alloc()
831     hb->orig_size = size;  in hbitmap_truncate()
834     size = (size + (1ULL << hb->granularity) - 1) >> hb->granularity;  in hbitmap_truncate()
836     shrink = size < hb->size;  in hbitmap_truncate()
839     if (size == hb->size) {  in hbitmap_truncate()
850         uint64_t start = ROUND_UP(num_elements, UINT64_C(1) << hb->granularity);  in hbitmap_truncate()
851         uint64_t fix_count = (hb->size << hb->granularity) - start;  in hbitmap_truncate()
857     hb->size = size;  in hbitmap_truncate()
858     for (i = HBITMAP_LEVELS; i-- > 0; ) {  in hbitmap_truncate()
860         if (hb->sizes[i] == size) {  in hbitmap_truncate()
863         old = hb->sizes[i];  in hbitmap_truncate()
864         hb->sizes[i] = size;  in hbitmap_truncate()
865         hb->levels[i] = g_renew(unsigned long, hb->levels[i], size);  in hbitmap_truncate()
867             memset(&hb->levels[i][old], 0x00,  in hbitmap_truncate()
868                    (size - old) * sizeof(*hb->levels[i]));  in hbitmap_truncate()
871     if (hb->meta) {  in hbitmap_truncate()
872         hbitmap_truncate(hb->meta, hb->size << hb->granularity);  in hbitmap_truncate()
887          hbitmap_next_dirty_area(src, offset, src->orig_size, INT64_MAX,  in hbitmap_sparse_merge()
906     assert(a->orig_size == result->orig_size);  in hbitmap_merge()
907     assert(b->orig_size == result->orig_size);  in hbitmap_merge()
919     if (a->granularity != b->granularity) {  in hbitmap_merge()
936     assert(a->size == b->size);  in hbitmap_merge()
937     for (i = HBITMAP_LEVELS - 1; i >= 0; i--) {  in hbitmap_merge()
938         for (j = 0; j < a->sizes[i]; j++) {  in hbitmap_merge()
939             result->levels[i][j] = a->levels[i][j] | b->levels[i][j];  in hbitmap_merge()
944     result->count = hb_count_between(result, 0, result->size - 1);  in hbitmap_merge()
949     size_t size = bitmap->sizes[HBITMAP_LEVELS - 1] * sizeof(unsigned long);  in hbitmap_sha256()
950     char *data = (char *)bitmap->levels[HBITMAP_LEVELS - 1];  in hbitmap_sha256()