1
2
3
4
5
6
7
8
9
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
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55struct HBitmap {
56
57
58
59 uint64_t orig_size;
60
61
62 uint64_t size;
63
64
65 uint64_t count;
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85 int granularity;
86
87
88 HBitmap *meta;
89
90
91
92
93
94
95
96
97
98 unsigned long *levels[HBITMAP_LEVELS];
99
100
101 uint64_t sizes[HBITMAP_LEVELS];
102};
103
104
105
106
107static 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
121
122
123
124
125
126 if (i == 0 && cur == (1UL << (BITS_PER_LONG - 1))) {
127 return 0;
128 }
129 for (; i < HBITMAP_LEVELS - 1; i++) {
130
131
132
133
134 assert(cur);
135 pos = (pos << BITS_PER_LEVEL) + ctzl(cur);
136 hbi->cur[i] = cur & (cur - 1);
137
138
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
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
185 hbi->cur[i] = hb->levels[i][pos] & ~((1UL << bit) - 1);
186
187
188
189
190 if (i != HBITMAP_LEVELS - 1) {
191 hbi->cur[i] &= ~(1UL << bit);
192 }
193 }
194}
195
196int64_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
220int64_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
241
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
273bool 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
304bool hbitmap_empty(const HBitmap *hb)
305{
306 return hb->count == 0;
307}
308
309int hbitmap_granularity(const HBitmap *hb)
310{
311 return hb->granularity;
312}
313
314uint64_t hbitmap_count(const HBitmap *hb)
315{
316 return hb->count << hb->granularity;
317}
318
319
320
321
322
323
324
325
326
327
328
329
330static size_t hbitmap_iter_next_word(HBitmapIter *hbi, unsigned long *p_cur)
331{
332 unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1];
333
334 if (cur == 0) {
335 cur = hbitmap_iter_skip_words(hbi);
336 if (cur == 0) {
337 *p_cur = 0;
338 return -1;
339 }
340 }
341
342
343 hbi->cur[HBITMAP_LEVELS - 1] = 0;
344 *p_cur = cur;
345 return hbi->pos;
346}
347
348
349
350
351static uint64_t hb_count_between(HBitmap *hb, uint64_t start, uint64_t last)
352{
353 HBitmapIter hbi;
354 uint64_t count = 0;
355 uint64_t end = last + 1;
356 unsigned long cur;
357 size_t pos;
358
359 hbitmap_iter_init(&hbi, hb, start << hb->granularity);
360 for (;;) {
361 pos = hbitmap_iter_next_word(&hbi, &cur);
362 if (pos >= (end >> BITS_PER_LEVEL)) {
363 break;
364 }
365 count += ctpopl(cur);
366 }
367
368 if (pos == (end >> BITS_PER_LEVEL)) {
369
370 int bit = end & (BITS_PER_LONG - 1);
371 cur &= (1UL << bit) - 1;
372 count += ctpopl(cur);
373 }
374
375 return count;
376}
377
378
379
380
381static inline bool hb_set_elem(unsigned long *elem, uint64_t start, uint64_t last)
382{
383 unsigned long mask;
384 unsigned long old;
385
386 assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL));
387 assert(start <= last);
388
389 mask = 2UL << (last & (BITS_PER_LONG - 1));
390 mask -= 1UL << (start & (BITS_PER_LONG - 1));
391 old = *elem;
392 *elem |= mask;
393 return old != *elem;
394}
395
396
397
398static bool hb_set_between(HBitmap *hb, int level, uint64_t start,
399 uint64_t last)
400{
401 size_t pos = start >> BITS_PER_LEVEL;
402 size_t lastpos = last >> BITS_PER_LEVEL;
403 bool changed = false;
404 size_t i;
405
406 i = pos;
407 if (i < lastpos) {
408 uint64_t next = (start | (BITS_PER_LONG - 1)) + 1;
409 changed |= hb_set_elem(&hb->levels[level][i], start, next - 1);
410 for (;;) {
411 start = next;
412 next += BITS_PER_LONG;
413 if (++i == lastpos) {
414 break;
415 }
416 changed |= (hb->levels[level][i] == 0);
417 hb->levels[level][i] = ~0UL;
418 }
419 }
420 changed |= hb_set_elem(&hb->levels[level][i], start, last);
421
422
423
424
425 if (level > 0 && changed) {
426 hb_set_between(hb, level - 1, pos, lastpos);
427 }
428 return changed;
429}
430
431void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count)
432{
433
434 uint64_t first, n;
435 uint64_t last = start + count - 1;
436
437 if (count == 0) {
438 return;
439 }
440
441 trace_hbitmap_set(hb, start, count,
442 start >> hb->granularity, last >> hb->granularity);
443
444 first = start >> hb->granularity;
445 last >>= hb->granularity;
446 assert(last < hb->size);
447 n = last - first + 1;
448
449 hb->count += n - hb_count_between(hb, first, last);
450 if (hb_set_between(hb, HBITMAP_LEVELS - 1, first, last) &&
451 hb->meta) {
452 hbitmap_set(hb->meta, start, count);
453 }
454}
455
456
457
458
459static inline bool hb_reset_elem(unsigned long *elem, uint64_t start, uint64_t last)
460{
461 unsigned long mask;
462 bool blanked;
463
464 assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL));
465 assert(start <= last);
466
467 mask = 2UL << (last & (BITS_PER_LONG - 1));
468 mask -= 1UL << (start & (BITS_PER_LONG - 1));
469 blanked = *elem != 0 && ((*elem & ~mask) == 0);
470 *elem &= ~mask;
471 return blanked;
472}
473
474
475
476static bool hb_reset_between(HBitmap *hb, int level, uint64_t start,
477 uint64_t last)
478{
479 size_t pos = start >> BITS_PER_LEVEL;
480 size_t lastpos = last >> BITS_PER_LEVEL;
481 bool changed = false;
482 size_t i;
483
484 i = pos;
485 if (i < lastpos) {
486 uint64_t next = (start | (BITS_PER_LONG - 1)) + 1;
487
488
489
490
491
492
493 if (hb_reset_elem(&hb->levels[level][i], start, next - 1)) {
494 changed = true;
495 } else {
496 pos++;
497 }
498
499 for (;;) {
500 start = next;
501 next += BITS_PER_LONG;
502 if (++i == lastpos) {
503 break;
504 }
505 changed |= (hb->levels[level][i] != 0);
506 hb->levels[level][i] = 0UL;
507 }
508 }
509
510
511 if (hb_reset_elem(&hb->levels[level][i], start, last)) {
512 changed = true;
513 } else {
514 lastpos--;
515 }
516
517 if (level > 0 && changed) {
518 hb_reset_between(hb, level - 1, pos, lastpos);
519 }
520
521 return changed;
522
523}
524
525void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count)
526{
527
528 uint64_t first;
529 uint64_t last = start + count - 1;
530 uint64_t gran = 1ULL << hb->granularity;
531
532 if (count == 0) {
533 return;
534 }
535
536 assert(QEMU_IS_ALIGNED(start, gran));
537 assert(QEMU_IS_ALIGNED(count, gran) || (start + count == hb->orig_size));
538
539 trace_hbitmap_reset(hb, start, count,
540 start >> hb->granularity, last >> hb->granularity);
541
542 first = start >> hb->granularity;
543 last >>= hb->granularity;
544 assert(last < hb->size);
545
546 hb->count -= hb_count_between(hb, first, last);
547 if (hb_reset_between(hb, HBITMAP_LEVELS - 1, first, last) &&
548 hb->meta) {
549 hbitmap_set(hb->meta, start, count);
550 }
551}
552
553void hbitmap_reset_all(HBitmap *hb)
554{
555 unsigned int i;
556
557
558 for (i = HBITMAP_LEVELS; --i >= 1; ) {
559 memset(hb->levels[i], 0, hb->sizes[i] * sizeof(unsigned long));
560 }
561
562 hb->levels[0][0] = 1UL << (BITS_PER_LONG - 1);
563 hb->count = 0;
564}
565
566bool hbitmap_is_serializable(const HBitmap *hb)
567{
568
569
570
571
572
573
574
575
576
577
578
579
580
581 return hb->granularity < 58;
582}
583
584bool hbitmap_get(const HBitmap *hb, uint64_t item)
585{
586
587 uint64_t pos = item >> hb->granularity;
588 unsigned long bit = 1UL << (pos & (BITS_PER_LONG - 1));
589 assert(pos < hb->size);
590
591 return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0;
592}
593
594uint64_t hbitmap_serialization_align(const HBitmap *hb)
595{
596 assert(hbitmap_is_serializable(hb));
597
598
599
600 return UINT64_C(64) << hb->granularity;
601}
602
603
604
605
606static void serialization_chunk(const HBitmap *hb,
607 uint64_t start, uint64_t count,
608 unsigned long **first_el, uint64_t *el_count)
609{
610 uint64_t last = start + count - 1;
611 uint64_t gran = hbitmap_serialization_align(hb);
612
613 assert((start & (gran - 1)) == 0);
614 assert((last >> hb->granularity) < hb->size);
615 if ((last >> hb->granularity) != hb->size - 1) {
616 assert((count & (gran - 1)) == 0);
617 }
618
619 start = (start >> hb->granularity) >> BITS_PER_LEVEL;
620 last = (last >> hb->granularity) >> BITS_PER_LEVEL;
621
622 *first_el = &hb->levels[HBITMAP_LEVELS - 1][start];
623 *el_count = last - start + 1;
624}
625
626uint64_t hbitmap_serialization_size(const HBitmap *hb,
627 uint64_t start, uint64_t count)
628{
629 uint64_t el_count;
630 unsigned long *cur;
631
632 if (!count) {
633 return 0;
634 }
635 serialization_chunk(hb, start, count, &cur, &el_count);
636
637 return el_count * sizeof(unsigned long);
638}
639
640void hbitmap_serialize_part(const HBitmap *hb, uint8_t *buf,
641 uint64_t start, uint64_t count)
642{
643 uint64_t el_count;
644 unsigned long *cur, *end;
645
646 if (!count) {
647 return;
648 }
649 serialization_chunk(hb, start, count, &cur, &el_count);
650 end = cur + el_count;
651
652 while (cur != end) {
653 unsigned long el =
654 (BITS_PER_LONG == 32 ? cpu_to_le32(*cur) : cpu_to_le64(*cur));
655
656 memcpy(buf, &el, sizeof(el));
657 buf += sizeof(el);
658 cur++;
659 }
660}
661
662void hbitmap_deserialize_part(HBitmap *hb, uint8_t *buf,
663 uint64_t start, uint64_t count,
664 bool finish)
665{
666 uint64_t el_count;
667 unsigned long *cur, *end;
668
669 if (!count) {
670 return;
671 }
672 serialization_chunk(hb, start, count, &cur, &el_count);
673 end = cur + el_count;
674
675 while (cur != end) {
676 memcpy(cur, buf, sizeof(*cur));
677
678 if (BITS_PER_LONG == 32) {
679 le32_to_cpus((uint32_t *)cur);
680 } else {
681 le64_to_cpus((uint64_t *)cur);
682 }
683
684 buf += sizeof(unsigned long);
685 cur++;
686 }
687 if (finish) {
688 hbitmap_deserialize_finish(hb);
689 }
690}
691
692void hbitmap_deserialize_zeroes(HBitmap *hb, uint64_t start, uint64_t count,
693 bool finish)
694{
695 uint64_t el_count;
696 unsigned long *first;
697
698 if (!count) {
699 return;
700 }
701 serialization_chunk(hb, start, count, &first, &el_count);
702
703 memset(first, 0, el_count * sizeof(unsigned long));
704 if (finish) {
705 hbitmap_deserialize_finish(hb);
706 }
707}
708
709void hbitmap_deserialize_ones(HBitmap *hb, uint64_t start, uint64_t count,
710 bool finish)
711{
712 uint64_t el_count;
713 unsigned long *first;
714
715 if (!count) {
716 return;
717 }
718 serialization_chunk(hb, start, count, &first, &el_count);
719
720 memset(first, 0xff, el_count * sizeof(unsigned long));
721 if (finish) {
722 hbitmap_deserialize_finish(hb);
723 }
724}
725
726void hbitmap_deserialize_finish(HBitmap *bitmap)
727{
728 int64_t i, size, prev_size;
729 int lev;
730
731
732
733 size = MAX((bitmap->size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
734 for (lev = HBITMAP_LEVELS - 1; lev-- > 0; ) {
735 prev_size = size;
736 size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
737 memset(bitmap->levels[lev], 0, size * sizeof(unsigned long));
738
739 for (i = 0; i < prev_size; ++i) {
740 if (bitmap->levels[lev + 1][i]) {
741 bitmap->levels[lev][i >> BITS_PER_LEVEL] |=
742 1UL << (i & (BITS_PER_LONG - 1));
743 }
744 }
745 }
746
747 bitmap->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);
748 bitmap->count = hb_count_between(bitmap, 0, bitmap->size - 1);
749}
750
751void hbitmap_free(HBitmap *hb)
752{
753 unsigned i;
754 assert(!hb->meta);
755 for (i = HBITMAP_LEVELS; i-- > 0; ) {
756 g_free(hb->levels[i]);
757 }
758 g_free(hb);
759}
760
761HBitmap *hbitmap_alloc(uint64_t size, int granularity)
762{
763 HBitmap *hb = g_new0(struct HBitmap, 1);
764 unsigned i;
765
766 assert(size <= INT64_MAX);
767 hb->orig_size = size;
768
769 assert(granularity >= 0 && granularity < 64);
770 size = (size + (1ULL << granularity) - 1) >> granularity;
771 assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
772
773 hb->size = size;
774 hb->granularity = granularity;
775 for (i = HBITMAP_LEVELS; i-- > 0; ) {
776 size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
777 hb->sizes[i] = size;
778 hb->levels[i] = g_new0(unsigned long, size);
779 }
780
781
782
783
784
785 assert(size == 1);
786 hb->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);
787 return hb;
788}
789
790void hbitmap_truncate(HBitmap *hb, uint64_t size)
791{
792 bool shrink;
793 unsigned i;
794 uint64_t num_elements = size;
795 uint64_t old;
796
797 assert(size <= INT64_MAX);
798 hb->orig_size = size;
799
800
801 size = (size + (1ULL << hb->granularity) - 1) >> hb->granularity;
802 assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
803 shrink = size < hb->size;
804
805
806 if (size == hb->size) {
807 return;
808 }
809
810
811
812
813
814 if (shrink) {
815
816
817 uint64_t start = ROUND_UP(num_elements, UINT64_C(1) << hb->granularity);
818 uint64_t fix_count = (hb->size << hb->granularity) - start;
819
820 assert(fix_count);
821 hbitmap_reset(hb, start, fix_count);
822 }
823
824 hb->size = size;
825 for (i = HBITMAP_LEVELS; i-- > 0; ) {
826 size = MAX(BITS_TO_LONGS(size), 1);
827 if (hb->sizes[i] == size) {
828 break;
829 }
830 old = hb->sizes[i];
831 hb->sizes[i] = size;
832 hb->levels[i] = g_realloc(hb->levels[i], size * sizeof(unsigned long));
833 if (!shrink) {
834 memset(&hb->levels[i][old], 0x00,
835 (size - old) * sizeof(*hb->levels[i]));
836 }
837 }
838 if (hb->meta) {
839 hbitmap_truncate(hb->meta, hb->size << hb->granularity);
840 }
841}
842
843bool hbitmap_can_merge(const HBitmap *a, const HBitmap *b)
844{
845 return (a->orig_size == b->orig_size);
846}
847
848
849
850
851
852
853static void hbitmap_sparse_merge(HBitmap *dst, const HBitmap *src)
854{
855 int64_t offset;
856 int64_t count;
857
858 for (offset = 0;
859 hbitmap_next_dirty_area(src, offset, src->orig_size, INT64_MAX,
860 &offset, &count);
861 offset += count)
862 {
863 hbitmap_set(dst, offset, count);
864 }
865}
866
867
868
869
870
871
872
873
874
875bool hbitmap_merge(const HBitmap *a, const HBitmap *b, HBitmap *result)
876{
877 int i;
878 uint64_t j;
879
880 if (!hbitmap_can_merge(a, b) || !hbitmap_can_merge(a, result)) {
881 return false;
882 }
883 assert(hbitmap_can_merge(b, result));
884
885 if ((!hbitmap_count(a) && result == b) ||
886 (!hbitmap_count(b) && result == a)) {
887 return true;
888 }
889
890 if (!hbitmap_count(a) && !hbitmap_count(b)) {
891 hbitmap_reset_all(result);
892 return true;
893 }
894
895 if (a->granularity != b->granularity) {
896 if ((a != result) && (b != result)) {
897 hbitmap_reset_all(result);
898 }
899 if (a != result) {
900 hbitmap_sparse_merge(result, a);
901 }
902 if (b != result) {
903 hbitmap_sparse_merge(result, b);
904 }
905 return true;
906 }
907
908
909
910
911
912 assert(a->size == b->size);
913 for (i = HBITMAP_LEVELS - 1; i >= 0; i--) {
914 for (j = 0; j < a->sizes[i]; j++) {
915 result->levels[i][j] = a->levels[i][j] | b->levels[i][j];
916 }
917 }
918
919
920 result->count = hb_count_between(result, 0, result->size - 1);
921
922 return true;
923}
924
925char *hbitmap_sha256(const HBitmap *bitmap, Error **errp)
926{
927 size_t size = bitmap->sizes[HBITMAP_LEVELS - 1] * sizeof(unsigned long);
928 char *data = (char *)bitmap->levels[HBITMAP_LEVELS - 1];
929 char *hash = NULL;
930 qcrypto_hash_digest(QCRYPTO_HASH_ALG_SHA256, data, size, &hash, errp);
931
932 return hash;
933}
934