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
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
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_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
215
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
302
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
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
332
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
350
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
376
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
387 uint64_t first, n;
388 uint64_t last = start + count - 1;
389
390 if (count == 0) {
391 return;
392 }
393
394 trace_hbitmap_set(hb, start, count,
395 start >> hb->granularity, last >> hb->granularity);
396
397 first = start >> hb->granularity;
398 last >>= hb->granularity;
399 assert(last < hb->size);
400 n = last - first + 1;
401
402 hb->count += n - hb_count_between(hb, first, last);
403 if (hb_set_between(hb, HBITMAP_LEVELS - 1, first, last) &&
404 hb->meta) {
405 hbitmap_set(hb->meta, start, count);
406 }
407}
408
409
410
411
412static inline bool hb_reset_elem(unsigned long *elem, uint64_t start, uint64_t last)
413{
414 unsigned long mask;
415 bool blanked;
416
417 assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL));
418 assert(start <= last);
419
420 mask = 2UL << (last & (BITS_PER_LONG - 1));
421 mask -= 1UL << (start & (BITS_PER_LONG - 1));
422 blanked = *elem != 0 && ((*elem & ~mask) == 0);
423 *elem &= ~mask;
424 return blanked;
425}
426
427
428
429static bool hb_reset_between(HBitmap *hb, int level, uint64_t start,
430 uint64_t last)
431{
432 size_t pos = start >> BITS_PER_LEVEL;
433 size_t lastpos = last >> BITS_PER_LEVEL;
434 bool changed = false;
435 size_t i;
436
437 i = pos;
438 if (i < lastpos) {
439 uint64_t next = (start | (BITS_PER_LONG - 1)) + 1;
440
441
442
443
444
445
446 if (hb_reset_elem(&hb->levels[level][i], start, next - 1)) {
447 changed = true;
448 } else {
449 pos++;
450 }
451
452 for (;;) {
453 start = next;
454 next += BITS_PER_LONG;
455 if (++i == lastpos) {
456 break;
457 }
458 changed |= (hb->levels[level][i] != 0);
459 hb->levels[level][i] = 0UL;
460 }
461 }
462
463
464 if (hb_reset_elem(&hb->levels[level][i], start, last)) {
465 changed = true;
466 } else {
467 lastpos--;
468 }
469
470 if (level > 0 && changed) {
471 hb_reset_between(hb, level - 1, pos, lastpos);
472 }
473
474 return changed;
475
476}
477
478void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count)
479{
480
481 uint64_t first;
482 uint64_t last = start + count - 1;
483 uint64_t gran = 1ULL << hb->granularity;
484
485 if (count == 0) {
486 return;
487 }
488
489 assert(QEMU_IS_ALIGNED(start, gran));
490 assert(QEMU_IS_ALIGNED(count, gran) || (start + count == hb->orig_size));
491
492 trace_hbitmap_reset(hb, start, count,
493 start >> hb->granularity, last >> hb->granularity);
494
495 first = start >> hb->granularity;
496 last >>= hb->granularity;
497 assert(last < hb->size);
498
499 hb->count -= hb_count_between(hb, first, last);
500 if (hb_reset_between(hb, HBITMAP_LEVELS - 1, first, last) &&
501 hb->meta) {
502 hbitmap_set(hb->meta, start, count);
503 }
504}
505
506void hbitmap_reset_all(HBitmap *hb)
507{
508 unsigned int i;
509
510
511 for (i = HBITMAP_LEVELS; --i >= 1; ) {
512 memset(hb->levels[i], 0, hb->sizes[i] * sizeof(unsigned long));
513 }
514
515 hb->levels[0][0] = 1UL << (BITS_PER_LONG - 1);
516 hb->count = 0;
517}
518
519bool hbitmap_is_serializable(const HBitmap *hb)
520{
521
522
523
524
525
526
527
528
529
530
531
532
533
534 return hb->granularity < 58;
535}
536
537bool hbitmap_get(const HBitmap *hb, uint64_t item)
538{
539
540 uint64_t pos = item >> hb->granularity;
541 unsigned long bit = 1UL << (pos & (BITS_PER_LONG - 1));
542 assert(pos < hb->size);
543
544 return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0;
545}
546
547uint64_t hbitmap_serialization_align(const HBitmap *hb)
548{
549 assert(hbitmap_is_serializable(hb));
550
551
552
553 return UINT64_C(64) << hb->granularity;
554}
555
556
557
558
559static void serialization_chunk(const HBitmap *hb,
560 uint64_t start, uint64_t count,
561 unsigned long **first_el, uint64_t *el_count)
562{
563 uint64_t last = start + count - 1;
564 uint64_t gran = hbitmap_serialization_align(hb);
565
566 assert((start & (gran - 1)) == 0);
567 assert((last >> hb->granularity) < hb->size);
568 if ((last >> hb->granularity) != hb->size - 1) {
569 assert((count & (gran - 1)) == 0);
570 }
571
572 start = (start >> hb->granularity) >> BITS_PER_LEVEL;
573 last = (last >> hb->granularity) >> BITS_PER_LEVEL;
574
575 *first_el = &hb->levels[HBITMAP_LEVELS - 1][start];
576 *el_count = last - start + 1;
577}
578
579uint64_t hbitmap_serialization_size(const HBitmap *hb,
580 uint64_t start, uint64_t count)
581{
582 uint64_t el_count;
583 unsigned long *cur;
584
585 if (!count) {
586 return 0;
587 }
588 serialization_chunk(hb, start, count, &cur, &el_count);
589
590 return el_count * sizeof(unsigned long);
591}
592
593void hbitmap_serialize_part(const HBitmap *hb, uint8_t *buf,
594 uint64_t start, uint64_t count)
595{
596 uint64_t el_count;
597 unsigned long *cur, *end;
598
599 if (!count) {
600 return;
601 }
602 serialization_chunk(hb, start, count, &cur, &el_count);
603 end = cur + el_count;
604
605 while (cur != end) {
606 unsigned long el =
607 (BITS_PER_LONG == 32 ? cpu_to_le32(*cur) : cpu_to_le64(*cur));
608
609 memcpy(buf, &el, sizeof(el));
610 buf += sizeof(el);
611 cur++;
612 }
613}
614
615void hbitmap_deserialize_part(HBitmap *hb, uint8_t *buf,
616 uint64_t start, uint64_t count,
617 bool finish)
618{
619 uint64_t el_count;
620 unsigned long *cur, *end;
621
622 if (!count) {
623 return;
624 }
625 serialization_chunk(hb, start, count, &cur, &el_count);
626 end = cur + el_count;
627
628 while (cur != end) {
629 memcpy(cur, buf, sizeof(*cur));
630
631 if (BITS_PER_LONG == 32) {
632 le32_to_cpus((uint32_t *)cur);
633 } else {
634 le64_to_cpus((uint64_t *)cur);
635 }
636
637 buf += sizeof(unsigned long);
638 cur++;
639 }
640 if (finish) {
641 hbitmap_deserialize_finish(hb);
642 }
643}
644
645void hbitmap_deserialize_zeroes(HBitmap *hb, uint64_t start, uint64_t count,
646 bool finish)
647{
648 uint64_t el_count;
649 unsigned long *first;
650
651 if (!count) {
652 return;
653 }
654 serialization_chunk(hb, start, count, &first, &el_count);
655
656 memset(first, 0, el_count * sizeof(unsigned long));
657 if (finish) {
658 hbitmap_deserialize_finish(hb);
659 }
660}
661
662void hbitmap_deserialize_ones(HBitmap *hb, uint64_t start, uint64_t count,
663 bool finish)
664{
665 uint64_t el_count;
666 unsigned long *first;
667
668 if (!count) {
669 return;
670 }
671 serialization_chunk(hb, start, count, &first, &el_count);
672
673 memset(first, 0xff, el_count * sizeof(unsigned long));
674 if (finish) {
675 hbitmap_deserialize_finish(hb);
676 }
677}
678
679void hbitmap_deserialize_finish(HBitmap *bitmap)
680{
681 int64_t i, size, prev_size;
682 int lev;
683
684
685
686 size = MAX((bitmap->size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
687 for (lev = HBITMAP_LEVELS - 1; lev-- > 0; ) {
688 prev_size = size;
689 size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
690 memset(bitmap->levels[lev], 0, size * sizeof(unsigned long));
691
692 for (i = 0; i < prev_size; ++i) {
693 if (bitmap->levels[lev + 1][i]) {
694 bitmap->levels[lev][i >> BITS_PER_LEVEL] |=
695 1UL << (i & (BITS_PER_LONG - 1));
696 }
697 }
698 }
699
700 bitmap->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);
701 bitmap->count = hb_count_between(bitmap, 0, bitmap->size - 1);
702}
703
704void hbitmap_free(HBitmap *hb)
705{
706 unsigned i;
707 assert(!hb->meta);
708 for (i = HBITMAP_LEVELS; i-- > 0; ) {
709 g_free(hb->levels[i]);
710 }
711 g_free(hb);
712}
713
714HBitmap *hbitmap_alloc(uint64_t size, int granularity)
715{
716 HBitmap *hb = g_new0(struct HBitmap, 1);
717 unsigned i;
718
719 hb->orig_size = size;
720
721 assert(granularity >= 0 && granularity < 64);
722 size = (size + (1ULL << granularity) - 1) >> granularity;
723 assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
724
725 hb->size = size;
726 hb->granularity = granularity;
727 for (i = HBITMAP_LEVELS; i-- > 0; ) {
728 size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
729 hb->sizes[i] = size;
730 hb->levels[i] = g_new0(unsigned long, size);
731 }
732
733
734
735
736
737 assert(size == 1);
738 hb->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);
739 return hb;
740}
741
742void hbitmap_truncate(HBitmap *hb, uint64_t size)
743{
744 bool shrink;
745 unsigned i;
746 uint64_t num_elements = size;
747 uint64_t old;
748
749 hb->orig_size = size;
750
751
752 size = (size + (1ULL << hb->granularity) - 1) >> hb->granularity;
753 assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
754 shrink = size < hb->size;
755
756
757 if (size == hb->size) {
758 return;
759 }
760
761
762
763
764
765 if (shrink) {
766
767
768 uint64_t start = ROUND_UP(num_elements, UINT64_C(1) << hb->granularity);
769 uint64_t fix_count = (hb->size << hb->granularity) - start;
770
771 assert(fix_count);
772 hbitmap_reset(hb, start, fix_count);
773 }
774
775 hb->size = size;
776 for (i = HBITMAP_LEVELS; i-- > 0; ) {
777 size = MAX(BITS_TO_LONGS(size), 1);
778 if (hb->sizes[i] == size) {
779 break;
780 }
781 old = hb->sizes[i];
782 hb->sizes[i] = size;
783 hb->levels[i] = g_realloc(hb->levels[i], size * sizeof(unsigned long));
784 if (!shrink) {
785 memset(&hb->levels[i][old], 0x00,
786 (size - old) * sizeof(*hb->levels[i]));
787 }
788 }
789 if (hb->meta) {
790 hbitmap_truncate(hb->meta, hb->size << hb->granularity);
791 }
792}
793
794bool hbitmap_can_merge(const HBitmap *a, const HBitmap *b)
795{
796 return (a->size == b->size) && (a->granularity == b->granularity);
797}
798
799
800
801
802
803
804
805
806bool hbitmap_merge(const HBitmap *a, const HBitmap *b, HBitmap *result)
807{
808 int i;
809 uint64_t j;
810
811 if (!hbitmap_can_merge(a, b) || !hbitmap_can_merge(a, result)) {
812 return false;
813 }
814 assert(hbitmap_can_merge(b, result));
815
816 if (hbitmap_count(b) == 0) {
817 return true;
818 }
819
820
821
822
823
824 for (i = HBITMAP_LEVELS - 1; i >= 0; i--) {
825 for (j = 0; j < a->sizes[i]; j++) {
826 result->levels[i][j] = a->levels[i][j] | b->levels[i][j];
827 }
828 }
829
830
831 result->count = hb_count_between(result, 0, result->size - 1);
832
833 return true;
834}
835
836HBitmap *hbitmap_create_meta(HBitmap *hb, int chunk_size)
837{
838 assert(!(chunk_size & (chunk_size - 1)));
839 assert(!hb->meta);
840 hb->meta = hbitmap_alloc(hb->size << hb->granularity,
841 hb->granularity + ctz32(chunk_size));
842 return hb->meta;
843}
844
845void hbitmap_free_meta(HBitmap *hb)
846{
847 assert(hb->meta);
848 hbitmap_free(hb->meta);
849 hb->meta = NULL;
850}
851
852char *hbitmap_sha256(const HBitmap *bitmap, Error **errp)
853{
854 size_t size = bitmap->sizes[HBITMAP_LEVELS - 1] * sizeof(unsigned long);
855 char *data = (char *)bitmap->levels[HBITMAP_LEVELS - 1];
856 char *hash = NULL;
857 qcrypto_hash_digest(QCRYPTO_HASH_ALG_SHA256, data, size, &hash, errp);
858
859 return hash;
860}
861