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 uint64_t size;
58
59
60 uint64_t count;
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80 int granularity;
81
82
83 HBitmap *meta;
84
85
86
87
88
89
90
91
92
93 unsigned long *levels[HBITMAP_LEVELS];
94
95
96 uint64_t sizes[HBITMAP_LEVELS];
97};
98
99
100
101
102unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi)
103{
104 size_t pos = hbi->pos;
105 const HBitmap *hb = hbi->hb;
106 unsigned i = HBITMAP_LEVELS - 1;
107
108 unsigned long cur;
109 do {
110 i--;
111 pos >>= BITS_PER_LEVEL;
112 cur = hbi->cur[i] & hb->levels[i][pos];
113 } while (cur == 0);
114
115
116
117
118
119
120
121 if (i == 0 && cur == (1UL << (BITS_PER_LONG - 1))) {
122 return 0;
123 }
124 for (; i < HBITMAP_LEVELS - 1; i++) {
125
126
127
128
129 assert(cur);
130 pos = (pos << BITS_PER_LEVEL) + ctzl(cur);
131 hbi->cur[i] = cur & (cur - 1);
132
133
134 cur = hb->levels[i + 1][pos];
135 }
136
137 hbi->pos = pos;
138 trace_hbitmap_iter_skip_words(hbi->hb, hbi, pos, cur);
139
140 assert(cur);
141 return cur;
142}
143
144int64_t hbitmap_iter_next(HBitmapIter *hbi, bool advance)
145{
146 unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1] &
147 hbi->hb->levels[HBITMAP_LEVELS - 1][hbi->pos];
148 int64_t item;
149
150 if (cur == 0) {
151 cur = hbitmap_iter_skip_words(hbi);
152 if (cur == 0) {
153 return -1;
154 }
155 }
156
157 if (advance) {
158
159 hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1);
160 } else {
161 hbi->cur[HBITMAP_LEVELS - 1] = cur;
162 }
163 item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + ctzl(cur);
164
165 return item << hbi->granularity;
166}
167
168void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first)
169{
170 unsigned i, bit;
171 uint64_t pos;
172
173 hbi->hb = hb;
174 pos = first >> hb->granularity;
175 assert(pos < hb->size);
176 hbi->pos = pos >> BITS_PER_LEVEL;
177 hbi->granularity = hb->granularity;
178
179 for (i = HBITMAP_LEVELS; i-- > 0; ) {
180 bit = pos & (BITS_PER_LONG - 1);
181 pos >>= BITS_PER_LEVEL;
182
183
184 hbi->cur[i] = hb->levels[i][pos] & ~((1UL << bit) - 1);
185
186
187
188
189 if (i != HBITMAP_LEVELS - 1) {
190 hbi->cur[i] &= ~(1UL << bit);
191 }
192 }
193}
194
195int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start)
196{
197 size_t pos = (start >> hb->granularity) >> BITS_PER_LEVEL;
198 unsigned long *last_lev = hb->levels[HBITMAP_LEVELS - 1];
199 uint64_t sz = hb->sizes[HBITMAP_LEVELS - 1];
200 unsigned long cur = last_lev[pos];
201 unsigned start_bit_offset =
202 (start >> hb->granularity) & (BITS_PER_LONG - 1);
203 int64_t res;
204
205 cur |= (1UL << start_bit_offset) - 1;
206 assert((start >> hb->granularity) < hb->size);
207
208 if (cur == (unsigned long)-1) {
209 do {
210 pos++;
211 } while (pos < sz && last_lev[pos] == (unsigned long)-1);
212
213 if (pos >= sz) {
214 return -1;
215 }
216
217 cur = last_lev[pos];
218 }
219
220 res = (pos << BITS_PER_LEVEL) + ctol(cur);
221 if (res >= hb->size) {
222 return -1;
223 }
224
225 res = res << hb->granularity;
226 if (res < start) {
227 assert(((start - res) >> hb->granularity) == 0);
228 return start;
229 }
230
231 return res;
232}
233
234bool hbitmap_empty(const HBitmap *hb)
235{
236 return hb->count == 0;
237}
238
239int hbitmap_granularity(const HBitmap *hb)
240{
241 return hb->granularity;
242}
243
244uint64_t hbitmap_count(const HBitmap *hb)
245{
246 return hb->count << hb->granularity;
247}
248
249
250
251
252static uint64_t hb_count_between(HBitmap *hb, uint64_t start, uint64_t last)
253{
254 HBitmapIter hbi;
255 uint64_t count = 0;
256 uint64_t end = last + 1;
257 unsigned long cur;
258 size_t pos;
259
260 hbitmap_iter_init(&hbi, hb, start << hb->granularity);
261 for (;;) {
262 pos = hbitmap_iter_next_word(&hbi, &cur);
263 if (pos >= (end >> BITS_PER_LEVEL)) {
264 break;
265 }
266 count += ctpopl(cur);
267 }
268
269 if (pos == (end >> BITS_PER_LEVEL)) {
270
271 int bit = end & (BITS_PER_LONG - 1);
272 cur &= (1UL << bit) - 1;
273 count += ctpopl(cur);
274 }
275
276 return count;
277}
278
279
280
281
282static inline bool hb_set_elem(unsigned long *elem, uint64_t start, uint64_t last)
283{
284 unsigned long mask;
285 unsigned long old;
286
287 assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL));
288 assert(start <= last);
289
290 mask = 2UL << (last & (BITS_PER_LONG - 1));
291 mask -= 1UL << (start & (BITS_PER_LONG - 1));
292 old = *elem;
293 *elem |= mask;
294 return old != *elem;
295}
296
297
298
299static bool hb_set_between(HBitmap *hb, int level, uint64_t start,
300 uint64_t last)
301{
302 size_t pos = start >> BITS_PER_LEVEL;
303 size_t lastpos = last >> BITS_PER_LEVEL;
304 bool changed = false;
305 size_t i;
306
307 i = pos;
308 if (i < lastpos) {
309 uint64_t next = (start | (BITS_PER_LONG - 1)) + 1;
310 changed |= hb_set_elem(&hb->levels[level][i], start, next - 1);
311 for (;;) {
312 start = next;
313 next += BITS_PER_LONG;
314 if (++i == lastpos) {
315 break;
316 }
317 changed |= (hb->levels[level][i] == 0);
318 hb->levels[level][i] = ~0UL;
319 }
320 }
321 changed |= hb_set_elem(&hb->levels[level][i], start, last);
322
323
324
325
326 if (level > 0 && changed) {
327 hb_set_between(hb, level - 1, pos, lastpos);
328 }
329 return changed;
330}
331
332void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count)
333{
334
335 uint64_t first, n;
336 uint64_t last = start + count - 1;
337
338 trace_hbitmap_set(hb, start, count,
339 start >> hb->granularity, last >> hb->granularity);
340
341 first = start >> hb->granularity;
342 last >>= hb->granularity;
343 assert(last < hb->size);
344 n = last - first + 1;
345
346 hb->count += n - hb_count_between(hb, first, last);
347 if (hb_set_between(hb, HBITMAP_LEVELS - 1, first, last) &&
348 hb->meta) {
349 hbitmap_set(hb->meta, start, count);
350 }
351}
352
353
354
355
356static inline bool hb_reset_elem(unsigned long *elem, uint64_t start, uint64_t last)
357{
358 unsigned long mask;
359 bool blanked;
360
361 assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL));
362 assert(start <= last);
363
364 mask = 2UL << (last & (BITS_PER_LONG - 1));
365 mask -= 1UL << (start & (BITS_PER_LONG - 1));
366 blanked = *elem != 0 && ((*elem & ~mask) == 0);
367 *elem &= ~mask;
368 return blanked;
369}
370
371
372
373static bool hb_reset_between(HBitmap *hb, int level, uint64_t start,
374 uint64_t last)
375{
376 size_t pos = start >> BITS_PER_LEVEL;
377 size_t lastpos = last >> BITS_PER_LEVEL;
378 bool changed = false;
379 size_t i;
380
381 i = pos;
382 if (i < lastpos) {
383 uint64_t next = (start | (BITS_PER_LONG - 1)) + 1;
384
385
386
387
388
389
390 if (hb_reset_elem(&hb->levels[level][i], start, next - 1)) {
391 changed = true;
392 } else {
393 pos++;
394 }
395
396 for (;;) {
397 start = next;
398 next += BITS_PER_LONG;
399 if (++i == lastpos) {
400 break;
401 }
402 changed |= (hb->levels[level][i] != 0);
403 hb->levels[level][i] = 0UL;
404 }
405 }
406
407
408 if (hb_reset_elem(&hb->levels[level][i], start, last)) {
409 changed = true;
410 } else {
411 lastpos--;
412 }
413
414 if (level > 0 && changed) {
415 hb_reset_between(hb, level - 1, pos, lastpos);
416 }
417
418 return changed;
419
420}
421
422void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count)
423{
424
425 uint64_t first;
426 uint64_t last = start + count - 1;
427
428 trace_hbitmap_reset(hb, start, count,
429 start >> hb->granularity, last >> hb->granularity);
430
431 first = start >> hb->granularity;
432 last >>= hb->granularity;
433 assert(last < hb->size);
434
435 hb->count -= hb_count_between(hb, first, last);
436 if (hb_reset_between(hb, HBITMAP_LEVELS - 1, first, last) &&
437 hb->meta) {
438 hbitmap_set(hb->meta, start, count);
439 }
440}
441
442void hbitmap_reset_all(HBitmap *hb)
443{
444 unsigned int i;
445
446
447 for (i = HBITMAP_LEVELS; --i >= 1; ) {
448 memset(hb->levels[i], 0, hb->sizes[i] * sizeof(unsigned long));
449 }
450
451 hb->levels[0][0] = 1UL << (BITS_PER_LONG - 1);
452 hb->count = 0;
453}
454
455bool hbitmap_is_serializable(const HBitmap *hb)
456{
457
458
459
460
461
462
463
464
465
466
467
468
469
470 return hb->granularity < 58;
471}
472
473bool hbitmap_get(const HBitmap *hb, uint64_t item)
474{
475
476 uint64_t pos = item >> hb->granularity;
477 unsigned long bit = 1UL << (pos & (BITS_PER_LONG - 1));
478 assert(pos < hb->size);
479
480 return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0;
481}
482
483uint64_t hbitmap_serialization_align(const HBitmap *hb)
484{
485 assert(hbitmap_is_serializable(hb));
486
487
488
489 return UINT64_C(64) << hb->granularity;
490}
491
492
493
494
495static void serialization_chunk(const HBitmap *hb,
496 uint64_t start, uint64_t count,
497 unsigned long **first_el, uint64_t *el_count)
498{
499 uint64_t last = start + count - 1;
500 uint64_t gran = hbitmap_serialization_align(hb);
501
502 assert((start & (gran - 1)) == 0);
503 assert((last >> hb->granularity) < hb->size);
504 if ((last >> hb->granularity) != hb->size - 1) {
505 assert((count & (gran - 1)) == 0);
506 }
507
508 start = (start >> hb->granularity) >> BITS_PER_LEVEL;
509 last = (last >> hb->granularity) >> BITS_PER_LEVEL;
510
511 *first_el = &hb->levels[HBITMAP_LEVELS - 1][start];
512 *el_count = last - start + 1;
513}
514
515uint64_t hbitmap_serialization_size(const HBitmap *hb,
516 uint64_t start, uint64_t count)
517{
518 uint64_t el_count;
519 unsigned long *cur;
520
521 if (!count) {
522 return 0;
523 }
524 serialization_chunk(hb, start, count, &cur, &el_count);
525
526 return el_count * sizeof(unsigned long);
527}
528
529void hbitmap_serialize_part(const HBitmap *hb, uint8_t *buf,
530 uint64_t start, uint64_t count)
531{
532 uint64_t el_count;
533 unsigned long *cur, *end;
534
535 if (!count) {
536 return;
537 }
538 serialization_chunk(hb, start, count, &cur, &el_count);
539 end = cur + el_count;
540
541 while (cur != end) {
542 unsigned long el =
543 (BITS_PER_LONG == 32 ? cpu_to_le32(*cur) : cpu_to_le64(*cur));
544
545 memcpy(buf, &el, sizeof(el));
546 buf += sizeof(el);
547 cur++;
548 }
549}
550
551void hbitmap_deserialize_part(HBitmap *hb, uint8_t *buf,
552 uint64_t start, uint64_t count,
553 bool finish)
554{
555 uint64_t el_count;
556 unsigned long *cur, *end;
557
558 if (!count) {
559 return;
560 }
561 serialization_chunk(hb, start, count, &cur, &el_count);
562 end = cur + el_count;
563
564 while (cur != end) {
565 memcpy(cur, buf, sizeof(*cur));
566
567 if (BITS_PER_LONG == 32) {
568 le32_to_cpus((uint32_t *)cur);
569 } else {
570 le64_to_cpus((uint64_t *)cur);
571 }
572
573 buf += sizeof(unsigned long);
574 cur++;
575 }
576 if (finish) {
577 hbitmap_deserialize_finish(hb);
578 }
579}
580
581void hbitmap_deserialize_zeroes(HBitmap *hb, uint64_t start, uint64_t count,
582 bool finish)
583{
584 uint64_t el_count;
585 unsigned long *first;
586
587 if (!count) {
588 return;
589 }
590 serialization_chunk(hb, start, count, &first, &el_count);
591
592 memset(first, 0, el_count * sizeof(unsigned long));
593 if (finish) {
594 hbitmap_deserialize_finish(hb);
595 }
596}
597
598void hbitmap_deserialize_ones(HBitmap *hb, uint64_t start, uint64_t count,
599 bool finish)
600{
601 uint64_t el_count;
602 unsigned long *first;
603
604 if (!count) {
605 return;
606 }
607 serialization_chunk(hb, start, count, &first, &el_count);
608
609 memset(first, 0xff, el_count * sizeof(unsigned long));
610 if (finish) {
611 hbitmap_deserialize_finish(hb);
612 }
613}
614
615void hbitmap_deserialize_finish(HBitmap *bitmap)
616{
617 int64_t i, size, prev_size;
618 int lev;
619
620
621
622 size = MAX((bitmap->size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
623 for (lev = HBITMAP_LEVELS - 1; lev-- > 0; ) {
624 prev_size = size;
625 size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
626 memset(bitmap->levels[lev], 0, size * sizeof(unsigned long));
627
628 for (i = 0; i < prev_size; ++i) {
629 if (bitmap->levels[lev + 1][i]) {
630 bitmap->levels[lev][i >> BITS_PER_LEVEL] |=
631 1UL << (i & (BITS_PER_LONG - 1));
632 }
633 }
634 }
635
636 bitmap->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);
637 bitmap->count = hb_count_between(bitmap, 0, bitmap->size - 1);
638}
639
640void hbitmap_free(HBitmap *hb)
641{
642 unsigned i;
643 assert(!hb->meta);
644 for (i = HBITMAP_LEVELS; i-- > 0; ) {
645 g_free(hb->levels[i]);
646 }
647 g_free(hb);
648}
649
650HBitmap *hbitmap_alloc(uint64_t size, int granularity)
651{
652 HBitmap *hb = g_new0(struct HBitmap, 1);
653 unsigned i;
654
655 assert(granularity >= 0 && granularity < 64);
656 size = (size + (1ULL << granularity) - 1) >> granularity;
657 assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
658
659 hb->size = size;
660 hb->granularity = granularity;
661 for (i = HBITMAP_LEVELS; i-- > 0; ) {
662 size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
663 hb->sizes[i] = size;
664 hb->levels[i] = g_new0(unsigned long, size);
665 }
666
667
668
669
670
671 assert(size == 1);
672 hb->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);
673 return hb;
674}
675
676void hbitmap_truncate(HBitmap *hb, uint64_t size)
677{
678 bool shrink;
679 unsigned i;
680 uint64_t num_elements = size;
681 uint64_t old;
682
683
684 size = (size + (1ULL << hb->granularity) - 1) >> hb->granularity;
685 assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
686 shrink = size < hb->size;
687
688
689 if (size == hb->size) {
690 return;
691 }
692
693
694
695
696
697 if (shrink) {
698
699
700 uint64_t start = ROUND_UP(num_elements, UINT64_C(1) << hb->granularity);
701 uint64_t fix_count = (hb->size << hb->granularity) - start;
702
703 assert(fix_count);
704 hbitmap_reset(hb, start, fix_count);
705 }
706
707 hb->size = size;
708 for (i = HBITMAP_LEVELS; i-- > 0; ) {
709 size = MAX(BITS_TO_LONGS(size), 1);
710 if (hb->sizes[i] == size) {
711 break;
712 }
713 old = hb->sizes[i];
714 hb->sizes[i] = size;
715 hb->levels[i] = g_realloc(hb->levels[i], size * sizeof(unsigned long));
716 if (!shrink) {
717 memset(&hb->levels[i][old], 0x00,
718 (size - old) * sizeof(*hb->levels[i]));
719 }
720 }
721 if (hb->meta) {
722 hbitmap_truncate(hb->meta, hb->size << hb->granularity);
723 }
724}
725
726bool hbitmap_can_merge(const HBitmap *a, const HBitmap *b)
727{
728 return (a->size == b->size) && (a->granularity == b->granularity);
729}
730
731
732
733
734
735
736
737
738bool hbitmap_merge(const HBitmap *a, const HBitmap *b, HBitmap *result)
739{
740 int i;
741 uint64_t j;
742
743 if (!hbitmap_can_merge(a, b) || !hbitmap_can_merge(a, result)) {
744 return false;
745 }
746 assert(hbitmap_can_merge(b, result));
747
748 if (hbitmap_count(b) == 0) {
749 return true;
750 }
751
752
753
754
755
756 for (i = HBITMAP_LEVELS - 1; i >= 0; i--) {
757 for (j = 0; j < a->sizes[i]; j++) {
758 result->levels[i][j] = a->levels[i][j] | b->levels[i][j];
759 }
760 }
761
762
763 result->count = hb_count_between(result, 0, result->size - 1);
764
765 return true;
766}
767
768HBitmap *hbitmap_create_meta(HBitmap *hb, int chunk_size)
769{
770 assert(!(chunk_size & (chunk_size - 1)));
771 assert(!hb->meta);
772 hb->meta = hbitmap_alloc(hb->size << hb->granularity,
773 hb->granularity + ctz32(chunk_size));
774 return hb->meta;
775}
776
777void hbitmap_free_meta(HBitmap *hb)
778{
779 assert(hb->meta);
780 hbitmap_free(hb->meta);
781 hb->meta = NULL;
782}
783
784char *hbitmap_sha256(const HBitmap *bitmap, Error **errp)
785{
786 size_t size = bitmap->sizes[HBITMAP_LEVELS - 1] * sizeof(unsigned long);
787 char *data = (char *)bitmap->levels[HBITMAP_LEVELS - 1];
788 char *hash = NULL;
789 qcrypto_hash_digest(QCRYPTO_HASH_ALG_SHA256, data, size, &hash, errp);
790
791 return hash;
792}
793