]>
Commit | Line | Data |
---|---|---|
e7c033c3 PB |
1 | /* |
2 | * Hierarchical Bitmap Data Type | |
3 | * | |
4 | * Copyright Red Hat, Inc., 2012 | |
5 | * | |
6 | * Author: Paolo Bonzini <[email protected]> | |
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 | ||
e7c033c3 PB |
12 | #include "qemu/osdep.h" |
13 | #include "qemu/hbitmap.h" | |
14 | #include "qemu/host-utils.h" | |
15 | #include "trace.h" | |
a3b52535 | 16 | #include "crypto/hash.h" |
e7c033c3 PB |
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 { | |
76d570dc VSO |
56 | /* Size of the bitmap, as requested in hbitmap_alloc. */ |
57 | uint64_t orig_size; | |
58 | ||
e7c033c3 PB |
59 | /* Number of total bits in the bottom level. */ |
60 | uint64_t size; | |
61 | ||
62 | /* Number of set bits in the bottom level. */ | |
63 | uint64_t count; | |
64 | ||
65 | /* A scaling factor. Given a granularity of G, each bit in the bitmap will | |
66 | * will actually represent a group of 2^G elements. Each operation on a | |
67 | * range of bits first rounds the bits to determine which group they land | |
68 | * in, and then affect the entire page; iteration will only visit the first | |
69 | * bit of each group. Here is an example of operations in a size-16, | |
70 | * granularity-1 HBitmap: | |
71 | * | |
72 | * initial state 00000000 | |
73 | * set(start=0, count=9) 11111000 (iter: 0, 2, 4, 6, 8) | |
74 | * reset(start=1, count=3) 00111000 (iter: 4, 6, 8) | |
75 | * set(start=9, count=2) 00111100 (iter: 4, 6, 8, 10) | |
76 | * reset(start=5, count=5) 00000000 | |
77 | * | |
78 | * From an implementation point of view, when setting or resetting bits, | |
79 | * the bitmap will scale bit numbers right by this amount of bits. When | |
80 | * iterating, the bitmap will scale bit numbers left by this amount of | |
81 | * bits. | |
82 | */ | |
83 | int granularity; | |
84 | ||
07ac4cdb FZ |
85 | /* A meta dirty bitmap to track the dirtiness of bits in this HBitmap. */ |
86 | HBitmap *meta; | |
87 | ||
e7c033c3 PB |
88 | /* A number of progressively less coarse bitmaps (i.e. level 0 is the |
89 | * coarsest). Each bit in level N represents a word in level N+1 that | |
90 | * has a set bit, except the last level where each bit represents the | |
91 | * actual bitmap. | |
92 | * | |
93 | * Note that all bitmaps have the same number of levels. Even a 1-bit | |
94 | * bitmap will still allocate HBITMAP_LEVELS arrays. | |
95 | */ | |
96 | unsigned long *levels[HBITMAP_LEVELS]; | |
8515efbe JS |
97 | |
98 | /* The length of each levels[] array. */ | |
99 | uint64_t sizes[HBITMAP_LEVELS]; | |
e7c033c3 PB |
100 | }; |
101 | ||
e7c033c3 PB |
102 | /* Advance hbi to the next nonzero word and return it. hbi->pos |
103 | * is updated. Returns zero if we reach the end of the bitmap. | |
104 | */ | |
105 | unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi) | |
106 | { | |
107 | size_t pos = hbi->pos; | |
108 | const HBitmap *hb = hbi->hb; | |
109 | unsigned i = HBITMAP_LEVELS - 1; | |
110 | ||
111 | unsigned long cur; | |
112 | do { | |
f63ea4e9 | 113 | i--; |
e7c033c3 | 114 | pos >>= BITS_PER_LEVEL; |
f63ea4e9 | 115 | cur = hbi->cur[i] & hb->levels[i][pos]; |
e7c033c3 PB |
116 | } while (cur == 0); |
117 | ||
118 | /* Check for end of iteration. We always use fewer than BITS_PER_LONG | |
119 | * bits in the level 0 bitmap; thus we can repurpose the most significant | |
120 | * bit as a sentinel. The sentinel is set in hbitmap_alloc and ensures | |
121 | * that the above loop ends even without an explicit check on i. | |
122 | */ | |
123 | ||
124 | if (i == 0 && cur == (1UL << (BITS_PER_LONG - 1))) { | |
125 | return 0; | |
126 | } | |
127 | for (; i < HBITMAP_LEVELS - 1; i++) { | |
128 | /* Shift back pos to the left, matching the right shifts above. | |
129 | * The index of this word's least significant set bit provides | |
130 | * the low-order bits. | |
131 | */ | |
18331e7c RH |
132 | assert(cur); |
133 | pos = (pos << BITS_PER_LEVEL) + ctzl(cur); | |
e7c033c3 PB |
134 | hbi->cur[i] = cur & (cur - 1); |
135 | ||
136 | /* Set up next level for iteration. */ | |
137 | cur = hb->levels[i + 1][pos]; | |
138 | } | |
139 | ||
140 | hbi->pos = pos; | |
141 | trace_hbitmap_iter_skip_words(hbi->hb, hbi, pos, cur); | |
142 | ||
143 | assert(cur); | |
144 | return cur; | |
145 | } | |
146 | ||
19c021e1 | 147 | int64_t hbitmap_iter_next(HBitmapIter *hbi) |
f63ea4e9 VSO |
148 | { |
149 | unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1] & | |
150 | hbi->hb->levels[HBITMAP_LEVELS - 1][hbi->pos]; | |
151 | int64_t item; | |
152 | ||
153 | if (cur == 0) { | |
154 | cur = hbitmap_iter_skip_words(hbi); | |
155 | if (cur == 0) { | |
156 | return -1; | |
157 | } | |
158 | } | |
159 | ||
19c021e1 VSO |
160 | /* The next call will resume work from the next bit. */ |
161 | hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1); | |
f63ea4e9 VSO |
162 | item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + ctzl(cur); |
163 | ||
164 | return item << hbi->granularity; | |
165 | } | |
166 | ||
e7c033c3 PB |
167 | void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first) |
168 | { | |
169 | unsigned i, bit; | |
170 | uint64_t pos; | |
171 | ||
172 | hbi->hb = hb; | |
173 | pos = first >> hb->granularity; | |
1b095244 | 174 | assert(pos < hb->size); |
e7c033c3 PB |
175 | hbi->pos = pos >> BITS_PER_LEVEL; |
176 | hbi->granularity = hb->granularity; | |
177 | ||
178 | for (i = HBITMAP_LEVELS; i-- > 0; ) { | |
179 | bit = pos & (BITS_PER_LONG - 1); | |
180 | pos >>= BITS_PER_LEVEL; | |
181 | ||
182 | /* Drop bits representing items before first. */ | |
183 | hbi->cur[i] = hb->levels[i][pos] & ~((1UL << bit) - 1); | |
184 | ||
185 | /* We have already added level i+1, so the lowest set bit has | |
186 | * been processed. Clear it. | |
187 | */ | |
188 | if (i != HBITMAP_LEVELS - 1) { | |
189 | hbi->cur[i] &= ~(1UL << bit); | |
190 | } | |
191 | } | |
192 | } | |
193 | ||
76d570dc | 194 | int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t count) |
56207df5 VSO |
195 | { |
196 | size_t pos = (start >> hb->granularity) >> BITS_PER_LEVEL; | |
197 | unsigned long *last_lev = hb->levels[HBITMAP_LEVELS - 1]; | |
56207df5 | 198 | unsigned long cur = last_lev[pos]; |
76d570dc VSO |
199 | unsigned start_bit_offset; |
200 | uint64_t end_bit, sz; | |
56207df5 VSO |
201 | int64_t res; |
202 | ||
76d570dc VSO |
203 | if (start >= hb->orig_size || count == 0) { |
204 | return -1; | |
205 | } | |
206 | ||
207 | end_bit = count > hb->orig_size - start ? | |
208 | hb->size : | |
209 | ((start + count - 1) >> hb->granularity) + 1; | |
210 | sz = (end_bit + BITS_PER_LONG - 1) >> BITS_PER_LEVEL; | |
211 | ||
212 | /* There may be some zero bits in @cur before @start. We are not interested | |
213 | * in them, let's set them. | |
214 | */ | |
215 | start_bit_offset = (start >> hb->granularity) & (BITS_PER_LONG - 1); | |
56207df5 VSO |
216 | cur |= (1UL << start_bit_offset) - 1; |
217 | assert((start >> hb->granularity) < hb->size); | |
218 | ||
219 | if (cur == (unsigned long)-1) { | |
220 | do { | |
221 | pos++; | |
222 | } while (pos < sz && last_lev[pos] == (unsigned long)-1); | |
223 | ||
224 | if (pos >= sz) { | |
225 | return -1; | |
226 | } | |
227 | ||
228 | cur = last_lev[pos]; | |
229 | } | |
230 | ||
231 | res = (pos << BITS_PER_LEVEL) + ctol(cur); | |
76d570dc | 232 | if (res >= end_bit) { |
56207df5 VSO |
233 | return -1; |
234 | } | |
235 | ||
236 | res = res << hb->granularity; | |
237 | if (res < start) { | |
238 | assert(((start - res) >> hb->granularity) == 0); | |
239 | return start; | |
240 | } | |
241 | ||
242 | return res; | |
243 | } | |
244 | ||
a78a1a48 VSO |
245 | bool hbitmap_next_dirty_area(const HBitmap *hb, uint64_t *start, |
246 | uint64_t *count) | |
247 | { | |
248 | HBitmapIter hbi; | |
249 | int64_t firt_dirty_off, area_end; | |
250 | uint32_t granularity = 1UL << hb->granularity; | |
251 | uint64_t end; | |
252 | ||
253 | if (*start >= hb->orig_size || *count == 0) { | |
254 | return false; | |
255 | } | |
256 | ||
257 | end = *count > hb->orig_size - *start ? hb->orig_size : *start + *count; | |
258 | ||
259 | hbitmap_iter_init(&hbi, hb, *start); | |
19c021e1 | 260 | firt_dirty_off = hbitmap_iter_next(&hbi); |
a78a1a48 VSO |
261 | |
262 | if (firt_dirty_off < 0 || firt_dirty_off >= end) { | |
263 | return false; | |
264 | } | |
265 | ||
266 | if (firt_dirty_off + granularity >= end) { | |
267 | area_end = end; | |
268 | } else { | |
269 | area_end = hbitmap_next_zero(hb, firt_dirty_off + granularity, | |
270 | end - firt_dirty_off - granularity); | |
271 | if (area_end < 0) { | |
272 | area_end = end; | |
273 | } | |
274 | } | |
275 | ||
276 | if (firt_dirty_off > *start) { | |
277 | *start = firt_dirty_off; | |
278 | } | |
279 | *count = area_end - *start; | |
280 | ||
281 | return true; | |
282 | } | |
283 | ||
e7c033c3 PB |
284 | bool hbitmap_empty(const HBitmap *hb) |
285 | { | |
286 | return hb->count == 0; | |
287 | } | |
288 | ||
289 | int hbitmap_granularity(const HBitmap *hb) | |
290 | { | |
291 | return hb->granularity; | |
292 | } | |
293 | ||
294 | uint64_t hbitmap_count(const HBitmap *hb) | |
295 | { | |
296 | return hb->count << hb->granularity; | |
297 | } | |
298 | ||
299 | /* Count the number of set bits between start and end, not accounting for | |
300 | * the granularity. Also an example of how to use hbitmap_iter_next_word. | |
301 | */ | |
302 | static uint64_t hb_count_between(HBitmap *hb, uint64_t start, uint64_t last) | |
303 | { | |
304 | HBitmapIter hbi; | |
305 | uint64_t count = 0; | |
306 | uint64_t end = last + 1; | |
307 | unsigned long cur; | |
308 | size_t pos; | |
309 | ||
310 | hbitmap_iter_init(&hbi, hb, start << hb->granularity); | |
311 | for (;;) { | |
312 | pos = hbitmap_iter_next_word(&hbi, &cur); | |
313 | if (pos >= (end >> BITS_PER_LEVEL)) { | |
314 | break; | |
315 | } | |
591b320a | 316 | count += ctpopl(cur); |
e7c033c3 PB |
317 | } |
318 | ||
319 | if (pos == (end >> BITS_PER_LEVEL)) { | |
320 | /* Drop bits representing the END-th and subsequent items. */ | |
321 | int bit = end & (BITS_PER_LONG - 1); | |
322 | cur &= (1UL << bit) - 1; | |
591b320a | 323 | count += ctpopl(cur); |
e7c033c3 PB |
324 | } |
325 | ||
326 | return count; | |
327 | } | |
328 | ||
329 | /* Setting starts at the last layer and propagates up if an element | |
07ac4cdb | 330 | * changes. |
e7c033c3 PB |
331 | */ |
332 | static inline bool hb_set_elem(unsigned long *elem, uint64_t start, uint64_t last) | |
333 | { | |
334 | unsigned long mask; | |
07ac4cdb | 335 | unsigned long old; |
e7c033c3 PB |
336 | |
337 | assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL)); | |
338 | assert(start <= last); | |
339 | ||
340 | mask = 2UL << (last & (BITS_PER_LONG - 1)); | |
341 | mask -= 1UL << (start & (BITS_PER_LONG - 1)); | |
07ac4cdb | 342 | old = *elem; |
e7c033c3 | 343 | *elem |= mask; |
07ac4cdb | 344 | return old != *elem; |
e7c033c3 PB |
345 | } |
346 | ||
07ac4cdb FZ |
347 | /* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)... |
348 | * Returns true if at least one bit is changed. */ | |
349 | static bool hb_set_between(HBitmap *hb, int level, uint64_t start, | |
350 | uint64_t last) | |
e7c033c3 PB |
351 | { |
352 | size_t pos = start >> BITS_PER_LEVEL; | |
353 | size_t lastpos = last >> BITS_PER_LEVEL; | |
354 | bool changed = false; | |
355 | size_t i; | |
356 | ||
357 | i = pos; | |
358 | if (i < lastpos) { | |
359 | uint64_t next = (start | (BITS_PER_LONG - 1)) + 1; | |
360 | changed |= hb_set_elem(&hb->levels[level][i], start, next - 1); | |
361 | for (;;) { | |
362 | start = next; | |
363 | next += BITS_PER_LONG; | |
364 | if (++i == lastpos) { | |
365 | break; | |
366 | } | |
367 | changed |= (hb->levels[level][i] == 0); | |
368 | hb->levels[level][i] = ~0UL; | |
369 | } | |
370 | } | |
371 | changed |= hb_set_elem(&hb->levels[level][i], start, last); | |
372 | ||
373 | /* If there was any change in this layer, we may have to update | |
374 | * the one above. | |
375 | */ | |
376 | if (level > 0 && changed) { | |
377 | hb_set_between(hb, level - 1, pos, lastpos); | |
378 | } | |
07ac4cdb | 379 | return changed; |
e7c033c3 PB |
380 | } |
381 | ||
382 | void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count) | |
383 | { | |
384 | /* Compute range in the last layer. */ | |
07ac4cdb | 385 | uint64_t first, n; |
e7c033c3 PB |
386 | uint64_t last = start + count - 1; |
387 | ||
388 | trace_hbitmap_set(hb, start, count, | |
389 | start >> hb->granularity, last >> hb->granularity); | |
390 | ||
07ac4cdb | 391 | first = start >> hb->granularity; |
e7c033c3 | 392 | last >>= hb->granularity; |
0e321191 | 393 | assert(last < hb->size); |
07ac4cdb | 394 | n = last - first + 1; |
e7c033c3 | 395 | |
07ac4cdb FZ |
396 | hb->count += n - hb_count_between(hb, first, last); |
397 | if (hb_set_between(hb, HBITMAP_LEVELS - 1, first, last) && | |
398 | hb->meta) { | |
399 | hbitmap_set(hb->meta, start, count); | |
400 | } | |
e7c033c3 PB |
401 | } |
402 | ||
403 | /* Resetting works the other way round: propagate up if the new | |
404 | * value is zero. | |
405 | */ | |
406 | static inline bool hb_reset_elem(unsigned long *elem, uint64_t start, uint64_t last) | |
407 | { | |
408 | unsigned long mask; | |
409 | bool blanked; | |
410 | ||
411 | assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL)); | |
412 | assert(start <= last); | |
413 | ||
414 | mask = 2UL << (last & (BITS_PER_LONG - 1)); | |
415 | mask -= 1UL << (start & (BITS_PER_LONG - 1)); | |
416 | blanked = *elem != 0 && ((*elem & ~mask) == 0); | |
417 | *elem &= ~mask; | |
418 | return blanked; | |
419 | } | |
420 | ||
07ac4cdb FZ |
421 | /* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)... |
422 | * Returns true if at least one bit is changed. */ | |
423 | static bool hb_reset_between(HBitmap *hb, int level, uint64_t start, | |
424 | uint64_t last) | |
e7c033c3 PB |
425 | { |
426 | size_t pos = start >> BITS_PER_LEVEL; | |
427 | size_t lastpos = last >> BITS_PER_LEVEL; | |
428 | bool changed = false; | |
429 | size_t i; | |
430 | ||
431 | i = pos; | |
432 | if (i < lastpos) { | |
433 | uint64_t next = (start | (BITS_PER_LONG - 1)) + 1; | |
434 | ||
435 | /* Here we need a more complex test than when setting bits. Even if | |
436 | * something was changed, we must not blank bits in the upper level | |
437 | * unless the lower-level word became entirely zero. So, remove pos | |
438 | * from the upper-level range if bits remain set. | |
439 | */ | |
440 | if (hb_reset_elem(&hb->levels[level][i], start, next - 1)) { | |
441 | changed = true; | |
442 | } else { | |
443 | pos++; | |
444 | } | |
445 | ||
446 | for (;;) { | |
447 | start = next; | |
448 | next += BITS_PER_LONG; | |
449 | if (++i == lastpos) { | |
450 | break; | |
451 | } | |
452 | changed |= (hb->levels[level][i] != 0); | |
453 | hb->levels[level][i] = 0UL; | |
454 | } | |
455 | } | |
456 | ||
457 | /* Same as above, this time for lastpos. */ | |
458 | if (hb_reset_elem(&hb->levels[level][i], start, last)) { | |
459 | changed = true; | |
460 | } else { | |
461 | lastpos--; | |
462 | } | |
463 | ||
464 | if (level > 0 && changed) { | |
465 | hb_reset_between(hb, level - 1, pos, lastpos); | |
466 | } | |
07ac4cdb FZ |
467 | |
468 | return changed; | |
469 | ||
e7c033c3 PB |
470 | } |
471 | ||
472 | void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count) | |
473 | { | |
474 | /* Compute range in the last layer. */ | |
07ac4cdb | 475 | uint64_t first; |
e7c033c3 PB |
476 | uint64_t last = start + count - 1; |
477 | ||
478 | trace_hbitmap_reset(hb, start, count, | |
479 | start >> hb->granularity, last >> hb->granularity); | |
480 | ||
07ac4cdb | 481 | first = start >> hb->granularity; |
e7c033c3 | 482 | last >>= hb->granularity; |
0e321191 | 483 | assert(last < hb->size); |
e7c033c3 | 484 | |
07ac4cdb FZ |
485 | hb->count -= hb_count_between(hb, first, last); |
486 | if (hb_reset_between(hb, HBITMAP_LEVELS - 1, first, last) && | |
487 | hb->meta) { | |
488 | hbitmap_set(hb->meta, start, count); | |
489 | } | |
e7c033c3 PB |
490 | } |
491 | ||
c6a8c328 WC |
492 | void hbitmap_reset_all(HBitmap *hb) |
493 | { | |
494 | unsigned int i; | |
495 | ||
496 | /* Same as hbitmap_alloc() except for memset() instead of malloc() */ | |
497 | for (i = HBITMAP_LEVELS; --i >= 1; ) { | |
498 | memset(hb->levels[i], 0, hb->sizes[i] * sizeof(unsigned long)); | |
499 | } | |
500 | ||
501 | hb->levels[0][0] = 1UL << (BITS_PER_LONG - 1); | |
502 | hb->count = 0; | |
503 | } | |
504 | ||
20a579de HR |
505 | bool hbitmap_is_serializable(const HBitmap *hb) |
506 | { | |
507 | /* Every serialized chunk must be aligned to 64 bits so that endianness | |
508 | * requirements can be fulfilled on both 64 bit and 32 bit hosts. | |
ecbfa281 | 509 | * We have hbitmap_serialization_align() which converts this |
20a579de HR |
510 | * alignment requirement from bitmap bits to items covered (e.g. sectors). |
511 | * That value is: | |
512 | * 64 << hb->granularity | |
513 | * Since this value must not exceed UINT64_MAX, hb->granularity must be | |
514 | * less than 58 (== 64 - 6, where 6 is ld(64), i.e. 1 << 6 == 64). | |
515 | * | |
ecbfa281 | 516 | * In order for hbitmap_serialization_align() to always return a |
20a579de HR |
517 | * meaningful value, bitmaps that are to be serialized must have a |
518 | * granularity of less than 58. */ | |
519 | ||
520 | return hb->granularity < 58; | |
521 | } | |
522 | ||
e7c033c3 PB |
523 | bool hbitmap_get(const HBitmap *hb, uint64_t item) |
524 | { | |
525 | /* Compute position and bit in the last layer. */ | |
526 | uint64_t pos = item >> hb->granularity; | |
527 | unsigned long bit = 1UL << (pos & (BITS_PER_LONG - 1)); | |
0e321191 | 528 | assert(pos < hb->size); |
e7c033c3 PB |
529 | |
530 | return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0; | |
531 | } | |
532 | ||
ecbfa281 | 533 | uint64_t hbitmap_serialization_align(const HBitmap *hb) |
8258888e | 534 | { |
20a579de | 535 | assert(hbitmap_is_serializable(hb)); |
6725f887 | 536 | |
8258888e VSO |
537 | /* Require at least 64 bit granularity to be safe on both 64 bit and 32 bit |
538 | * hosts. */ | |
6725f887 | 539 | return UINT64_C(64) << hb->granularity; |
8258888e VSO |
540 | } |
541 | ||
542 | /* Start should be aligned to serialization granularity, chunk size should be | |
543 | * aligned to serialization granularity too, except for last chunk. | |
544 | */ | |
545 | static void serialization_chunk(const HBitmap *hb, | |
546 | uint64_t start, uint64_t count, | |
547 | unsigned long **first_el, uint64_t *el_count) | |
548 | { | |
549 | uint64_t last = start + count - 1; | |
ecbfa281 | 550 | uint64_t gran = hbitmap_serialization_align(hb); |
8258888e VSO |
551 | |
552 | assert((start & (gran - 1)) == 0); | |
553 | assert((last >> hb->granularity) < hb->size); | |
554 | if ((last >> hb->granularity) != hb->size - 1) { | |
555 | assert((count & (gran - 1)) == 0); | |
556 | } | |
557 | ||
558 | start = (start >> hb->granularity) >> BITS_PER_LEVEL; | |
559 | last = (last >> hb->granularity) >> BITS_PER_LEVEL; | |
560 | ||
561 | *first_el = &hb->levels[HBITMAP_LEVELS - 1][start]; | |
562 | *el_count = last - start + 1; | |
563 | } | |
564 | ||
565 | uint64_t hbitmap_serialization_size(const HBitmap *hb, | |
566 | uint64_t start, uint64_t count) | |
567 | { | |
568 | uint64_t el_count; | |
569 | unsigned long *cur; | |
570 | ||
571 | if (!count) { | |
572 | return 0; | |
573 | } | |
574 | serialization_chunk(hb, start, count, &cur, &el_count); | |
575 | ||
576 | return el_count * sizeof(unsigned long); | |
577 | } | |
578 | ||
579 | void hbitmap_serialize_part(const HBitmap *hb, uint8_t *buf, | |
580 | uint64_t start, uint64_t count) | |
581 | { | |
582 | uint64_t el_count; | |
583 | unsigned long *cur, *end; | |
584 | ||
585 | if (!count) { | |
586 | return; | |
587 | } | |
588 | serialization_chunk(hb, start, count, &cur, &el_count); | |
589 | end = cur + el_count; | |
590 | ||
591 | while (cur != end) { | |
592 | unsigned long el = | |
593 | (BITS_PER_LONG == 32 ? cpu_to_le32(*cur) : cpu_to_le64(*cur)); | |
594 | ||
595 | memcpy(buf, &el, sizeof(el)); | |
596 | buf += sizeof(el); | |
597 | cur++; | |
598 | } | |
599 | } | |
600 | ||
601 | void hbitmap_deserialize_part(HBitmap *hb, uint8_t *buf, | |
602 | uint64_t start, uint64_t count, | |
603 | bool finish) | |
604 | { | |
605 | uint64_t el_count; | |
606 | unsigned long *cur, *end; | |
607 | ||
608 | if (!count) { | |
609 | return; | |
610 | } | |
611 | serialization_chunk(hb, start, count, &cur, &el_count); | |
612 | end = cur + el_count; | |
613 | ||
614 | while (cur != end) { | |
615 | memcpy(cur, buf, sizeof(*cur)); | |
616 | ||
617 | if (BITS_PER_LONG == 32) { | |
618 | le32_to_cpus((uint32_t *)cur); | |
619 | } else { | |
620 | le64_to_cpus((uint64_t *)cur); | |
621 | } | |
622 | ||
623 | buf += sizeof(unsigned long); | |
624 | cur++; | |
625 | } | |
626 | if (finish) { | |
627 | hbitmap_deserialize_finish(hb); | |
628 | } | |
629 | } | |
630 | ||
631 | void hbitmap_deserialize_zeroes(HBitmap *hb, uint64_t start, uint64_t count, | |
632 | bool finish) | |
633 | { | |
634 | uint64_t el_count; | |
635 | unsigned long *first; | |
636 | ||
637 | if (!count) { | |
638 | return; | |
639 | } | |
640 | serialization_chunk(hb, start, count, &first, &el_count); | |
641 | ||
642 | memset(first, 0, el_count * sizeof(unsigned long)); | |
643 | if (finish) { | |
644 | hbitmap_deserialize_finish(hb); | |
645 | } | |
646 | } | |
647 | ||
6bdc8b71 VSO |
648 | void hbitmap_deserialize_ones(HBitmap *hb, uint64_t start, uint64_t count, |
649 | bool finish) | |
650 | { | |
651 | uint64_t el_count; | |
652 | unsigned long *first; | |
653 | ||
654 | if (!count) { | |
655 | return; | |
656 | } | |
657 | serialization_chunk(hb, start, count, &first, &el_count); | |
658 | ||
659 | memset(first, 0xff, el_count * sizeof(unsigned long)); | |
660 | if (finish) { | |
661 | hbitmap_deserialize_finish(hb); | |
662 | } | |
663 | } | |
664 | ||
8258888e VSO |
665 | void hbitmap_deserialize_finish(HBitmap *bitmap) |
666 | { | |
667 | int64_t i, size, prev_size; | |
668 | int lev; | |
669 | ||
670 | /* restore levels starting from penultimate to zero level, assuming | |
671 | * that the last level is ok */ | |
672 | size = MAX((bitmap->size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1); | |
673 | for (lev = HBITMAP_LEVELS - 1; lev-- > 0; ) { | |
674 | prev_size = size; | |
675 | size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1); | |
676 | memset(bitmap->levels[lev], 0, size * sizeof(unsigned long)); | |
677 | ||
678 | for (i = 0; i < prev_size; ++i) { | |
679 | if (bitmap->levels[lev + 1][i]) { | |
680 | bitmap->levels[lev][i >> BITS_PER_LEVEL] |= | |
681 | 1UL << (i & (BITS_PER_LONG - 1)); | |
682 | } | |
683 | } | |
684 | } | |
685 | ||
686 | bitmap->levels[0][0] |= 1UL << (BITS_PER_LONG - 1); | |
3260cdff | 687 | bitmap->count = hb_count_between(bitmap, 0, bitmap->size - 1); |
8258888e VSO |
688 | } |
689 | ||
e7c033c3 PB |
690 | void hbitmap_free(HBitmap *hb) |
691 | { | |
692 | unsigned i; | |
07ac4cdb | 693 | assert(!hb->meta); |
e7c033c3 PB |
694 | for (i = HBITMAP_LEVELS; i-- > 0; ) { |
695 | g_free(hb->levels[i]); | |
696 | } | |
697 | g_free(hb); | |
698 | } | |
699 | ||
700 | HBitmap *hbitmap_alloc(uint64_t size, int granularity) | |
701 | { | |
e1cf5582 | 702 | HBitmap *hb = g_new0(struct HBitmap, 1); |
e7c033c3 PB |
703 | unsigned i; |
704 | ||
76d570dc VSO |
705 | hb->orig_size = size; |
706 | ||
e7c033c3 PB |
707 | assert(granularity >= 0 && granularity < 64); |
708 | size = (size + (1ULL << granularity) - 1) >> granularity; | |
709 | assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE)); | |
710 | ||
711 | hb->size = size; | |
712 | hb->granularity = granularity; | |
713 | for (i = HBITMAP_LEVELS; i-- > 0; ) { | |
714 | size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1); | |
8515efbe | 715 | hb->sizes[i] = size; |
e1cf5582 | 716 | hb->levels[i] = g_new0(unsigned long, size); |
e7c033c3 PB |
717 | } |
718 | ||
719 | /* We necessarily have free bits in level 0 due to the definition | |
720 | * of HBITMAP_LEVELS, so use one for a sentinel. This speeds up | |
721 | * hbitmap_iter_skip_words. | |
722 | */ | |
723 | assert(size == 1); | |
724 | hb->levels[0][0] |= 1UL << (BITS_PER_LONG - 1); | |
725 | return hb; | |
726 | } | |
be58721d | 727 | |
ce1ffea8 JS |
728 | void hbitmap_truncate(HBitmap *hb, uint64_t size) |
729 | { | |
730 | bool shrink; | |
731 | unsigned i; | |
732 | uint64_t num_elements = size; | |
733 | uint64_t old; | |
734 | ||
735 | /* Size comes in as logical elements, adjust for granularity. */ | |
736 | size = (size + (1ULL << hb->granularity) - 1) >> hb->granularity; | |
737 | assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE)); | |
738 | shrink = size < hb->size; | |
739 | ||
740 | /* bit sizes are identical; nothing to do. */ | |
741 | if (size == hb->size) { | |
742 | return; | |
743 | } | |
744 | ||
745 | /* If we're losing bits, let's clear those bits before we invalidate all of | |
746 | * our invariants. This helps keep the bitcount consistent, and will prevent | |
747 | * us from carrying around garbage bits beyond the end of the map. | |
748 | */ | |
749 | if (shrink) { | |
750 | /* Don't clear partial granularity groups; | |
751 | * start at the first full one. */ | |
6725f887 | 752 | uint64_t start = ROUND_UP(num_elements, UINT64_C(1) << hb->granularity); |
ce1ffea8 JS |
753 | uint64_t fix_count = (hb->size << hb->granularity) - start; |
754 | ||
755 | assert(fix_count); | |
756 | hbitmap_reset(hb, start, fix_count); | |
757 | } | |
758 | ||
759 | hb->size = size; | |
760 | for (i = HBITMAP_LEVELS; i-- > 0; ) { | |
761 | size = MAX(BITS_TO_LONGS(size), 1); | |
762 | if (hb->sizes[i] == size) { | |
763 | break; | |
764 | } | |
765 | old = hb->sizes[i]; | |
766 | hb->sizes[i] = size; | |
767 | hb->levels[i] = g_realloc(hb->levels[i], size * sizeof(unsigned long)); | |
768 | if (!shrink) { | |
769 | memset(&hb->levels[i][old], 0x00, | |
770 | (size - old) * sizeof(*hb->levels[i])); | |
771 | } | |
772 | } | |
07ac4cdb FZ |
773 | if (hb->meta) { |
774 | hbitmap_truncate(hb->meta, hb->size << hb->granularity); | |
775 | } | |
ce1ffea8 JS |
776 | } |
777 | ||
fa000f2f VSO |
778 | bool hbitmap_can_merge(const HBitmap *a, const HBitmap *b) |
779 | { | |
780 | return (a->size == b->size) && (a->granularity == b->granularity); | |
781 | } | |
ce1ffea8 | 782 | |
be58721d JS |
783 | /** |
784 | * Given HBitmaps A and B, let A := A (BITOR) B. | |
785 | * Bitmap B will not be modified. | |
786 | * | |
787 | * @return true if the merge was successful, | |
788 | * false if it was not attempted. | |
789 | */ | |
fa000f2f | 790 | bool hbitmap_merge(const HBitmap *a, const HBitmap *b, HBitmap *result) |
be58721d JS |
791 | { |
792 | int i; | |
793 | uint64_t j; | |
794 | ||
fa000f2f | 795 | if (!hbitmap_can_merge(a, b) || !hbitmap_can_merge(a, result)) { |
be58721d JS |
796 | return false; |
797 | } | |
fa000f2f | 798 | assert(hbitmap_can_merge(b, result)); |
be58721d JS |
799 | |
800 | if (hbitmap_count(b) == 0) { | |
801 | return true; | |
802 | } | |
803 | ||
804 | /* This merge is O(size), as BITS_PER_LONG and HBITMAP_LEVELS are constant. | |
805 | * It may be possible to improve running times for sparsely populated maps | |
806 | * by using hbitmap_iter_next, but this is suboptimal for dense maps. | |
807 | */ | |
808 | for (i = HBITMAP_LEVELS - 1; i >= 0; i--) { | |
809 | for (j = 0; j < a->sizes[i]; j++) { | |
fa000f2f | 810 | result->levels[i][j] = a->levels[i][j] | b->levels[i][j]; |
be58721d JS |
811 | } |
812 | } | |
813 | ||
d1dde714 EB |
814 | /* Recompute the dirty count */ |
815 | result->count = hb_count_between(result, 0, result->size - 1); | |
816 | ||
be58721d JS |
817 | return true; |
818 | } | |
07ac4cdb FZ |
819 | |
820 | HBitmap *hbitmap_create_meta(HBitmap *hb, int chunk_size) | |
821 | { | |
822 | assert(!(chunk_size & (chunk_size - 1))); | |
823 | assert(!hb->meta); | |
824 | hb->meta = hbitmap_alloc(hb->size << hb->granularity, | |
825 | hb->granularity + ctz32(chunk_size)); | |
826 | return hb->meta; | |
827 | } | |
828 | ||
829 | void hbitmap_free_meta(HBitmap *hb) | |
830 | { | |
831 | assert(hb->meta); | |
832 | hbitmap_free(hb->meta); | |
833 | hb->meta = NULL; | |
834 | } | |
a3b52535 VSO |
835 | |
836 | char *hbitmap_sha256(const HBitmap *bitmap, Error **errp) | |
837 | { | |
838 | size_t size = bitmap->sizes[HBITMAP_LEVELS - 1] * sizeof(unsigned long); | |
839 | char *data = (char *)bitmap->levels[HBITMAP_LEVELS - 1]; | |
840 | char *hash = NULL; | |
841 | qcrypto_hash_digest(QCRYPTO_HASH_ALG_SHA256, data, size, &hash, errp); | |
842 | ||
843 | return hash; | |
844 | } |