Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 1 | /* |
| 2 | * Hierarchical Bitmap Data Type |
| 3 | * |
| 4 | * Copyright Red Hat, Inc., 2012 |
| 5 | * |
| 6 | * Author: Paolo Bonzini <pbonzini@redhat.com> |
| 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 | |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 12 | #include "qemu/osdep.h" |
| 13 | #include "qemu/hbitmap.h" |
| 14 | #include "qemu/host-utils.h" |
| 15 | #include "trace.h" |
Vladimir Sementsov-Ogievskiy | a3b5253 | 2017-06-28 15:05:25 +0300 | [diff] [blame] | 16 | #include "crypto/hash.h" |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 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 { |
Vladimir Sementsov-Ogievskiy | 4e4de22 | 2019-08-05 15:01:20 +0300 | [diff] [blame] | 56 | /* |
| 57 | * Size of the bitmap, as requested in hbitmap_alloc or in hbitmap_truncate. |
| 58 | */ |
Vladimir Sementsov-Ogievskiy | 76d570d | 2019-01-15 18:26:49 -0500 | [diff] [blame] | 59 | uint64_t orig_size; |
| 60 | |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 61 | /* Number of total bits in the bottom level. */ |
| 62 | uint64_t size; |
| 63 | |
| 64 | /* Number of set bits in the bottom level. */ |
| 65 | uint64_t count; |
| 66 | |
| 67 | /* A scaling factor. Given a granularity of G, each bit in the bitmap will |
| 68 | * will actually represent a group of 2^G elements. Each operation on a |
| 69 | * range of bits first rounds the bits to determine which group they land |
| 70 | * in, and then affect the entire page; iteration will only visit the first |
| 71 | * bit of each group. Here is an example of operations in a size-16, |
| 72 | * granularity-1 HBitmap: |
| 73 | * |
| 74 | * initial state 00000000 |
| 75 | * set(start=0, count=9) 11111000 (iter: 0, 2, 4, 6, 8) |
| 76 | * reset(start=1, count=3) 00111000 (iter: 4, 6, 8) |
| 77 | * set(start=9, count=2) 00111100 (iter: 4, 6, 8, 10) |
| 78 | * reset(start=5, count=5) 00000000 |
| 79 | * |
| 80 | * From an implementation point of view, when setting or resetting bits, |
| 81 | * the bitmap will scale bit numbers right by this amount of bits. When |
| 82 | * iterating, the bitmap will scale bit numbers left by this amount of |
| 83 | * bits. |
| 84 | */ |
| 85 | int granularity; |
| 86 | |
Fam Zheng | 07ac4cd | 2016-10-13 17:58:22 -0400 | [diff] [blame] | 87 | /* A meta dirty bitmap to track the dirtiness of bits in this HBitmap. */ |
| 88 | HBitmap *meta; |
| 89 | |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 90 | /* A number of progressively less coarse bitmaps (i.e. level 0 is the |
| 91 | * coarsest). Each bit in level N represents a word in level N+1 that |
| 92 | * has a set bit, except the last level where each bit represents the |
| 93 | * actual bitmap. |
| 94 | * |
| 95 | * Note that all bitmaps have the same number of levels. Even a 1-bit |
| 96 | * bitmap will still allocate HBITMAP_LEVELS arrays. |
| 97 | */ |
| 98 | unsigned long *levels[HBITMAP_LEVELS]; |
John Snow | 8515efb | 2015-04-17 19:49:54 -0400 | [diff] [blame] | 99 | |
| 100 | /* The length of each levels[] array. */ |
| 101 | uint64_t sizes[HBITMAP_LEVELS]; |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 102 | }; |
| 103 | |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 104 | /* Advance hbi to the next nonzero word and return it. hbi->pos |
| 105 | * is updated. Returns zero if we reach the end of the bitmap. |
| 106 | */ |
Vladimir Sementsov-Ogievskiy | 30b8346 | 2020-02-05 14:20:34 +0300 | [diff] [blame] | 107 | static unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi) |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 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 { |
Vladimir Sementsov-Ogievskiy | f63ea4e | 2017-06-28 15:05:03 +0300 | [diff] [blame] | 115 | i--; |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 116 | pos >>= BITS_PER_LEVEL; |
Vladimir Sementsov-Ogievskiy | f63ea4e | 2017-06-28 15:05:03 +0300 | [diff] [blame] | 117 | cur = hbi->cur[i] & hb->levels[i][pos]; |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 118 | } while (cur == 0); |
| 119 | |
| 120 | /* Check for end of iteration. We always use fewer than BITS_PER_LONG |
| 121 | * bits in the level 0 bitmap; thus we can repurpose the most significant |
| 122 | * bit as a sentinel. The sentinel is set in hbitmap_alloc and ensures |
| 123 | * that the above loop ends even without an explicit check on i. |
| 124 | */ |
| 125 | |
| 126 | if (i == 0 && cur == (1UL << (BITS_PER_LONG - 1))) { |
| 127 | return 0; |
| 128 | } |
| 129 | for (; i < HBITMAP_LEVELS - 1; i++) { |
| 130 | /* Shift back pos to the left, matching the right shifts above. |
| 131 | * The index of this word's least significant set bit provides |
| 132 | * the low-order bits. |
| 133 | */ |
Richard Henderson | 18331e7 | 2013-02-13 17:47:36 -0800 | [diff] [blame] | 134 | assert(cur); |
| 135 | pos = (pos << BITS_PER_LEVEL) + ctzl(cur); |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 136 | hbi->cur[i] = cur & (cur - 1); |
| 137 | |
| 138 | /* Set up next level for iteration. */ |
| 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 | |
Vladimir Sementsov-Ogievskiy | 19c021e | 2019-01-15 18:26:50 -0500 | [diff] [blame] | 149 | int64_t hbitmap_iter_next(HBitmapIter *hbi) |
Vladimir Sementsov-Ogievskiy | f63ea4e | 2017-06-28 15:05:03 +0300 | [diff] [blame] | 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 | |
Vladimir Sementsov-Ogievskiy | 19c021e | 2019-01-15 18:26:50 -0500 | [diff] [blame] | 162 | /* The next call will resume work from the next bit. */ |
| 163 | hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1); |
Vladimir Sementsov-Ogievskiy | f63ea4e | 2017-06-28 15:05:03 +0300 | [diff] [blame] | 164 | item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + ctzl(cur); |
| 165 | |
| 166 | return item << hbi->granularity; |
| 167 | } |
| 168 | |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 169 | void 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; |
Paolo Bonzini | 1b09524 | 2013-01-22 15:01:12 +0100 | [diff] [blame] | 176 | assert(pos < hb->size); |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 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 | /* Drop bits representing items before first. */ |
| 185 | hbi->cur[i] = hb->levels[i][pos] & ~((1UL << bit) - 1); |
| 186 | |
| 187 | /* We have already added level i+1, so the lowest set bit has |
| 188 | * been processed. Clear it. |
| 189 | */ |
| 190 | if (i != HBITMAP_LEVELS - 1) { |
| 191 | hbi->cur[i] &= ~(1UL << bit); |
| 192 | } |
| 193 | } |
| 194 | } |
| 195 | |
Vladimir Sementsov-Ogievskiy | 9399c54 | 2020-02-05 14:20:37 +0300 | [diff] [blame] | 196 | int64_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 | |
Vladimir Sementsov-Ogievskiy | 642700f | 2020-02-05 14:20:36 +0300 | [diff] [blame] | 220 | int64_t hbitmap_next_zero(const HBitmap *hb, int64_t start, int64_t count) |
Vladimir Sementsov-Ogievskiy | 56207df | 2017-10-12 16:53:09 +0300 | [diff] [blame] | 221 | { |
| 222 | size_t pos = (start >> hb->granularity) >> BITS_PER_LEVEL; |
| 223 | unsigned long *last_lev = hb->levels[HBITMAP_LEVELS - 1]; |
Vladimir Sementsov-Ogievskiy | 56207df | 2017-10-12 16:53:09 +0300 | [diff] [blame] | 224 | unsigned long cur = last_lev[pos]; |
Vladimir Sementsov-Ogievskiy | 76d570d | 2019-01-15 18:26:49 -0500 | [diff] [blame] | 225 | unsigned start_bit_offset; |
| 226 | uint64_t end_bit, sz; |
Vladimir Sementsov-Ogievskiy | 56207df | 2017-10-12 16:53:09 +0300 | [diff] [blame] | 227 | int64_t res; |
| 228 | |
Vladimir Sementsov-Ogievskiy | 642700f | 2020-02-05 14:20:36 +0300 | [diff] [blame] | 229 | assert(start >= 0 && count >= 0); |
| 230 | |
Vladimir Sementsov-Ogievskiy | 76d570d | 2019-01-15 18:26:49 -0500 | [diff] [blame] | 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 | /* There may be some zero bits in @cur before @start. We are not interested |
| 241 | * in them, let's set them. |
| 242 | */ |
| 243 | start_bit_offset = (start >> hb->granularity) & (BITS_PER_LONG - 1); |
Vladimir Sementsov-Ogievskiy | 56207df | 2017-10-12 16:53:09 +0300 | [diff] [blame] | 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); |
Vladimir Sementsov-Ogievskiy | 76d570d | 2019-01-15 18:26:49 -0500 | [diff] [blame] | 260 | if (res >= end_bit) { |
Vladimir Sementsov-Ogievskiy | 56207df | 2017-10-12 16:53:09 +0300 | [diff] [blame] | 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 | |
Vladimir Sementsov-Ogievskiy | 299ea9f | 2020-02-05 14:20:38 +0300 | [diff] [blame] | 273 | bool 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) |
Vladimir Sementsov-Ogievskiy | a78a1a4 | 2019-01-15 18:26:50 -0500 | [diff] [blame] | 276 | { |
Vladimir Sementsov-Ogievskiy | 299ea9f | 2020-02-05 14:20:38 +0300 | [diff] [blame] | 277 | int64_t next_zero; |
Vladimir Sementsov-Ogievskiy | a78a1a4 | 2019-01-15 18:26:50 -0500 | [diff] [blame] | 278 | |
Vladimir Sementsov-Ogievskiy | 299ea9f | 2020-02-05 14:20:38 +0300 | [diff] [blame] | 279 | assert(start >= 0 && end >= 0 && max_dirty_count > 0); |
| 280 | |
| 281 | end = MIN(end, hb->orig_size); |
| 282 | if (start >= end) { |
Vladimir Sementsov-Ogievskiy | a78a1a4 | 2019-01-15 18:26:50 -0500 | [diff] [blame] | 283 | return false; |
| 284 | } |
| 285 | |
Vladimir Sementsov-Ogievskiy | 299ea9f | 2020-02-05 14:20:38 +0300 | [diff] [blame] | 286 | start = hbitmap_next_dirty(hb, start, end - start); |
| 287 | if (start < 0) { |
| 288 | return false; |
Vladimir Sementsov-Ogievskiy | a78a1a4 | 2019-01-15 18:26:50 -0500 | [diff] [blame] | 289 | } |
| 290 | |
Vladimir Sementsov-Ogievskiy | 299ea9f | 2020-02-05 14:20:38 +0300 | [diff] [blame] | 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; |
Vladimir Sementsov-Ogievskiy | a78a1a4 | 2019-01-15 18:26:50 -0500 | [diff] [blame] | 300 | |
| 301 | return true; |
| 302 | } |
| 303 | |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 304 | bool hbitmap_empty(const HBitmap *hb) |
| 305 | { |
| 306 | return hb->count == 0; |
| 307 | } |
| 308 | |
| 309 | int hbitmap_granularity(const HBitmap *hb) |
| 310 | { |
| 311 | return hb->granularity; |
| 312 | } |
| 313 | |
| 314 | uint64_t hbitmap_count(const HBitmap *hb) |
| 315 | { |
| 316 | return hb->count << hb->granularity; |
| 317 | } |
| 318 | |
Vladimir Sementsov-Ogievskiy | be24c71 | 2020-02-05 14:20:33 +0300 | [diff] [blame] | 319 | /** |
| 320 | * hbitmap_iter_next_word: |
| 321 | * @hbi: HBitmapIter to operate on. |
| 322 | * @p_cur: Location where to store the next non-zero word. |
| 323 | * |
| 324 | * Return the index of the next nonzero word that is set in @hbi's |
| 325 | * associated HBitmap, and set *p_cur to the content of that word |
| 326 | * (bits before the index that was passed to hbitmap_iter_init are |
| 327 | * trimmed on the first call). Return -1, and set *p_cur to zero, |
| 328 | * if all remaining words are zero. |
| 329 | */ |
| 330 | static 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 | /* The next call will resume work from the next word. */ |
| 343 | hbi->cur[HBITMAP_LEVELS - 1] = 0; |
| 344 | *p_cur = cur; |
| 345 | return hbi->pos; |
| 346 | } |
| 347 | |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 348 | /* Count the number of set bits between start and end, not accounting for |
| 349 | * the granularity. Also an example of how to use hbitmap_iter_next_word. |
| 350 | */ |
| 351 | static 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 | } |
Peter Maydell | 591b320 | 2014-06-04 00:07:20 +0100 | [diff] [blame] | 365 | count += ctpopl(cur); |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 366 | } |
| 367 | |
| 368 | if (pos == (end >> BITS_PER_LEVEL)) { |
| 369 | /* Drop bits representing the END-th and subsequent items. */ |
| 370 | int bit = end & (BITS_PER_LONG - 1); |
| 371 | cur &= (1UL << bit) - 1; |
Peter Maydell | 591b320 | 2014-06-04 00:07:20 +0100 | [diff] [blame] | 372 | count += ctpopl(cur); |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 373 | } |
| 374 | |
| 375 | return count; |
| 376 | } |
| 377 | |
| 378 | /* Setting starts at the last layer and propagates up if an element |
Fam Zheng | 07ac4cd | 2016-10-13 17:58:22 -0400 | [diff] [blame] | 379 | * changes. |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 380 | */ |
| 381 | static inline bool hb_set_elem(unsigned long *elem, uint64_t start, uint64_t last) |
| 382 | { |
| 383 | unsigned long mask; |
Fam Zheng | 07ac4cd | 2016-10-13 17:58:22 -0400 | [diff] [blame] | 384 | unsigned long old; |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 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)); |
Fam Zheng | 07ac4cd | 2016-10-13 17:58:22 -0400 | [diff] [blame] | 391 | old = *elem; |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 392 | *elem |= mask; |
Fam Zheng | 07ac4cd | 2016-10-13 17:58:22 -0400 | [diff] [blame] | 393 | return old != *elem; |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 394 | } |
| 395 | |
Fam Zheng | 07ac4cd | 2016-10-13 17:58:22 -0400 | [diff] [blame] | 396 | /* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)... |
| 397 | * Returns true if at least one bit is changed. */ |
| 398 | static bool hb_set_between(HBitmap *hb, int level, uint64_t start, |
| 399 | uint64_t last) |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 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 | /* If there was any change in this layer, we may have to update |
| 423 | * the one above. |
| 424 | */ |
| 425 | if (level > 0 && changed) { |
| 426 | hb_set_between(hb, level - 1, pos, lastpos); |
| 427 | } |
Fam Zheng | 07ac4cd | 2016-10-13 17:58:22 -0400 | [diff] [blame] | 428 | return changed; |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 429 | } |
| 430 | |
| 431 | void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count) |
| 432 | { |
| 433 | /* Compute range in the last layer. */ |
Fam Zheng | 07ac4cd | 2016-10-13 17:58:22 -0400 | [diff] [blame] | 434 | uint64_t first, n; |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 435 | uint64_t last = start + count - 1; |
| 436 | |
Vladimir Sementsov-Ogievskiy | fed33bd | 2019-10-11 12:07:07 +0300 | [diff] [blame] | 437 | if (count == 0) { |
| 438 | return; |
| 439 | } |
| 440 | |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 441 | trace_hbitmap_set(hb, start, count, |
| 442 | start >> hb->granularity, last >> hb->granularity); |
| 443 | |
Fam Zheng | 07ac4cd | 2016-10-13 17:58:22 -0400 | [diff] [blame] | 444 | first = start >> hb->granularity; |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 445 | last >>= hb->granularity; |
Vladimir Sementsov-Ogievskiy | 0e32119 | 2016-06-14 20:08:12 +0300 | [diff] [blame] | 446 | assert(last < hb->size); |
Fam Zheng | 07ac4cd | 2016-10-13 17:58:22 -0400 | [diff] [blame] | 447 | n = last - first + 1; |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 448 | |
Fam Zheng | 07ac4cd | 2016-10-13 17:58:22 -0400 | [diff] [blame] | 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 | } |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 454 | } |
| 455 | |
| 456 | /* Resetting works the other way round: propagate up if the new |
| 457 | * value is zero. |
| 458 | */ |
| 459 | static 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 | |
Fam Zheng | 07ac4cd | 2016-10-13 17:58:22 -0400 | [diff] [blame] | 474 | /* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)... |
| 475 | * Returns true if at least one bit is changed. */ |
| 476 | static bool hb_reset_between(HBitmap *hb, int level, uint64_t start, |
| 477 | uint64_t last) |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 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 | /* Here we need a more complex test than when setting bits. Even if |
| 489 | * something was changed, we must not blank bits in the upper level |
| 490 | * unless the lower-level word became entirely zero. So, remove pos |
| 491 | * from the upper-level range if bits remain set. |
| 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 | /* Same as above, this time for lastpos. */ |
| 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 | } |
Fam Zheng | 07ac4cd | 2016-10-13 17:58:22 -0400 | [diff] [blame] | 520 | |
| 521 | return changed; |
| 522 | |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 523 | } |
| 524 | |
| 525 | void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count) |
| 526 | { |
| 527 | /* Compute range in the last layer. */ |
Fam Zheng | 07ac4cd | 2016-10-13 17:58:22 -0400 | [diff] [blame] | 528 | uint64_t first; |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 529 | uint64_t last = start + count - 1; |
Vladimir Sementsov-Ogievskiy | 48557b1 | 2019-08-06 18:26:11 +0300 | [diff] [blame] | 530 | uint64_t gran = 1ULL << hb->granularity; |
| 531 | |
Vladimir Sementsov-Ogievskiy | fed33bd | 2019-10-11 12:07:07 +0300 | [diff] [blame] | 532 | if (count == 0) { |
| 533 | return; |
| 534 | } |
| 535 | |
Vladimir Sementsov-Ogievskiy | 48557b1 | 2019-08-06 18:26:11 +0300 | [diff] [blame] | 536 | assert(QEMU_IS_ALIGNED(start, gran)); |
| 537 | assert(QEMU_IS_ALIGNED(count, gran) || (start + count == hb->orig_size)); |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 538 | |
| 539 | trace_hbitmap_reset(hb, start, count, |
| 540 | start >> hb->granularity, last >> hb->granularity); |
| 541 | |
Fam Zheng | 07ac4cd | 2016-10-13 17:58:22 -0400 | [diff] [blame] | 542 | first = start >> hb->granularity; |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 543 | last >>= hb->granularity; |
Vladimir Sementsov-Ogievskiy | 0e32119 | 2016-06-14 20:08:12 +0300 | [diff] [blame] | 544 | assert(last < hb->size); |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 545 | |
Fam Zheng | 07ac4cd | 2016-10-13 17:58:22 -0400 | [diff] [blame] | 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 | } |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 551 | } |
| 552 | |
Wen Congyang | c6a8c32 | 2015-05-22 09:29:46 +0800 | [diff] [blame] | 553 | void hbitmap_reset_all(HBitmap *hb) |
| 554 | { |
| 555 | unsigned int i; |
| 556 | |
| 557 | /* Same as hbitmap_alloc() except for memset() instead of malloc() */ |
| 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 | |
Max Reitz | 20a579d | 2016-11-15 23:57:45 +0100 | [diff] [blame] | 566 | bool hbitmap_is_serializable(const HBitmap *hb) |
| 567 | { |
| 568 | /* Every serialized chunk must be aligned to 64 bits so that endianness |
| 569 | * requirements can be fulfilled on both 64 bit and 32 bit hosts. |
Eric Blake | ecbfa28 | 2017-09-25 09:55:08 -0500 | [diff] [blame] | 570 | * We have hbitmap_serialization_align() which converts this |
Max Reitz | 20a579d | 2016-11-15 23:57:45 +0100 | [diff] [blame] | 571 | * alignment requirement from bitmap bits to items covered (e.g. sectors). |
| 572 | * That value is: |
| 573 | * 64 << hb->granularity |
| 574 | * Since this value must not exceed UINT64_MAX, hb->granularity must be |
| 575 | * less than 58 (== 64 - 6, where 6 is ld(64), i.e. 1 << 6 == 64). |
| 576 | * |
Eric Blake | ecbfa28 | 2017-09-25 09:55:08 -0500 | [diff] [blame] | 577 | * In order for hbitmap_serialization_align() to always return a |
Max Reitz | 20a579d | 2016-11-15 23:57:45 +0100 | [diff] [blame] | 578 | * meaningful value, bitmaps that are to be serialized must have a |
| 579 | * granularity of less than 58. */ |
| 580 | |
| 581 | return hb->granularity < 58; |
| 582 | } |
| 583 | |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 584 | bool hbitmap_get(const HBitmap *hb, uint64_t item) |
| 585 | { |
| 586 | /* Compute position and bit in the last layer. */ |
| 587 | uint64_t pos = item >> hb->granularity; |
| 588 | unsigned long bit = 1UL << (pos & (BITS_PER_LONG - 1)); |
Vladimir Sementsov-Ogievskiy | 0e32119 | 2016-06-14 20:08:12 +0300 | [diff] [blame] | 589 | assert(pos < hb->size); |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 590 | |
| 591 | return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0; |
| 592 | } |
| 593 | |
Eric Blake | ecbfa28 | 2017-09-25 09:55:08 -0500 | [diff] [blame] | 594 | uint64_t hbitmap_serialization_align(const HBitmap *hb) |
Vladimir Sementsov-Ogievskiy | 8258888 | 2016-10-13 17:58:27 -0400 | [diff] [blame] | 595 | { |
Max Reitz | 20a579d | 2016-11-15 23:57:45 +0100 | [diff] [blame] | 596 | assert(hbitmap_is_serializable(hb)); |
Max Reitz | 6725f88 | 2016-11-15 23:47:32 +0100 | [diff] [blame] | 597 | |
Vladimir Sementsov-Ogievskiy | 8258888 | 2016-10-13 17:58:27 -0400 | [diff] [blame] | 598 | /* Require at least 64 bit granularity to be safe on both 64 bit and 32 bit |
| 599 | * hosts. */ |
Max Reitz | 6725f88 | 2016-11-15 23:47:32 +0100 | [diff] [blame] | 600 | return UINT64_C(64) << hb->granularity; |
Vladimir Sementsov-Ogievskiy | 8258888 | 2016-10-13 17:58:27 -0400 | [diff] [blame] | 601 | } |
| 602 | |
| 603 | /* Start should be aligned to serialization granularity, chunk size should be |
| 604 | * aligned to serialization granularity too, except for last chunk. |
| 605 | */ |
| 606 | static 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; |
Eric Blake | ecbfa28 | 2017-09-25 09:55:08 -0500 | [diff] [blame] | 611 | uint64_t gran = hbitmap_serialization_align(hb); |
Vladimir Sementsov-Ogievskiy | 8258888 | 2016-10-13 17:58:27 -0400 | [diff] [blame] | 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 | |
| 626 | uint64_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 | |
| 640 | void 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 | |
| 662 | void 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 | |
| 692 | void 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 | |
Vladimir Sementsov-Ogievskiy | 6bdc8b7 | 2017-06-28 15:05:06 +0300 | [diff] [blame] | 709 | void 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 | |
Vladimir Sementsov-Ogievskiy | 8258888 | 2016-10-13 17:58:27 -0400 | [diff] [blame] | 726 | void hbitmap_deserialize_finish(HBitmap *bitmap) |
| 727 | { |
| 728 | int64_t i, size, prev_size; |
| 729 | int lev; |
| 730 | |
| 731 | /* restore levels starting from penultimate to zero level, assuming |
| 732 | * that the last level is ok */ |
| 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); |
Liang Li | 3260cdf | 2018-02-07 11:35:49 -0500 | [diff] [blame] | 748 | bitmap->count = hb_count_between(bitmap, 0, bitmap->size - 1); |
Vladimir Sementsov-Ogievskiy | 8258888 | 2016-10-13 17:58:27 -0400 | [diff] [blame] | 749 | } |
| 750 | |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 751 | void hbitmap_free(HBitmap *hb) |
| 752 | { |
| 753 | unsigned i; |
Fam Zheng | 07ac4cd | 2016-10-13 17:58:22 -0400 | [diff] [blame] | 754 | assert(!hb->meta); |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 755 | for (i = HBITMAP_LEVELS; i-- > 0; ) { |
| 756 | g_free(hb->levels[i]); |
| 757 | } |
| 758 | g_free(hb); |
| 759 | } |
| 760 | |
| 761 | HBitmap *hbitmap_alloc(uint64_t size, int granularity) |
| 762 | { |
Markus Armbruster | e1cf558 | 2014-12-04 15:00:03 +0100 | [diff] [blame] | 763 | HBitmap *hb = g_new0(struct HBitmap, 1); |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 764 | unsigned i; |
| 765 | |
Vladimir Sementsov-Ogievskiy | 6a15099 | 2020-02-05 14:20:32 +0300 | [diff] [blame] | 766 | assert(size <= INT64_MAX); |
Vladimir Sementsov-Ogievskiy | 76d570d | 2019-01-15 18:26:49 -0500 | [diff] [blame] | 767 | hb->orig_size = size; |
| 768 | |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 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); |
John Snow | 8515efb | 2015-04-17 19:49:54 -0400 | [diff] [blame] | 777 | hb->sizes[i] = size; |
Markus Armbruster | e1cf558 | 2014-12-04 15:00:03 +0100 | [diff] [blame] | 778 | hb->levels[i] = g_new0(unsigned long, size); |
Paolo Bonzini | e7c033c | 2013-01-21 17:09:40 +0100 | [diff] [blame] | 779 | } |
| 780 | |
| 781 | /* We necessarily have free bits in level 0 due to the definition |
| 782 | * of HBITMAP_LEVELS, so use one for a sentinel. This speeds up |
| 783 | * hbitmap_iter_skip_words. |
| 784 | */ |
| 785 | assert(size == 1); |
| 786 | hb->levels[0][0] |= 1UL << (BITS_PER_LONG - 1); |
| 787 | return hb; |
| 788 | } |
John Snow | be58721 | 2015-04-17 19:49:55 -0400 | [diff] [blame] | 789 | |
John Snow | ce1ffea | 2015-04-17 19:50:03 -0400 | [diff] [blame] | 790 | void 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 | |
Vladimir Sementsov-Ogievskiy | 6a15099 | 2020-02-05 14:20:32 +0300 | [diff] [blame] | 797 | assert(size <= INT64_MAX); |
Vladimir Sementsov-Ogievskiy | 4e4de22 | 2019-08-05 15:01:20 +0300 | [diff] [blame] | 798 | hb->orig_size = size; |
| 799 | |
John Snow | ce1ffea | 2015-04-17 19:50:03 -0400 | [diff] [blame] | 800 | /* Size comes in as logical elements, adjust for granularity. */ |
| 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 | /* bit sizes are identical; nothing to do. */ |
| 806 | if (size == hb->size) { |
| 807 | return; |
| 808 | } |
| 809 | |
| 810 | /* If we're losing bits, let's clear those bits before we invalidate all of |
| 811 | * our invariants. This helps keep the bitcount consistent, and will prevent |
| 812 | * us from carrying around garbage bits beyond the end of the map. |
| 813 | */ |
| 814 | if (shrink) { |
| 815 | /* Don't clear partial granularity groups; |
| 816 | * start at the first full one. */ |
Max Reitz | 6725f88 | 2016-11-15 23:47:32 +0100 | [diff] [blame] | 817 | uint64_t start = ROUND_UP(num_elements, UINT64_C(1) << hb->granularity); |
John Snow | ce1ffea | 2015-04-17 19:50:03 -0400 | [diff] [blame] | 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 | } |
Fam Zheng | 07ac4cd | 2016-10-13 17:58:22 -0400 | [diff] [blame] | 838 | if (hb->meta) { |
| 839 | hbitmap_truncate(hb->meta, hb->size << hb->granularity); |
| 840 | } |
John Snow | ce1ffea | 2015-04-17 19:50:03 -0400 | [diff] [blame] | 841 | } |
| 842 | |
Vladimir Sementsov-Ogievskiy | fa000f2 | 2018-10-29 16:23:15 -0400 | [diff] [blame] | 843 | bool hbitmap_can_merge(const HBitmap *a, const HBitmap *b) |
| 844 | { |
John Snow | c5b40c1 | 2019-07-29 16:35:53 -0400 | [diff] [blame] | 845 | return (a->orig_size == b->orig_size); |
| 846 | } |
| 847 | |
| 848 | /** |
| 849 | * hbitmap_sparse_merge: performs dst = dst | src |
| 850 | * works with differing granularities. |
| 851 | * best used when src is sparsely populated. |
| 852 | */ |
| 853 | static void hbitmap_sparse_merge(HBitmap *dst, const HBitmap *src) |
| 854 | { |
Vladimir Sementsov-Ogievskiy | 299ea9f | 2020-02-05 14:20:38 +0300 | [diff] [blame] | 855 | int64_t offset; |
| 856 | int64_t count; |
John Snow | c5b40c1 | 2019-07-29 16:35:53 -0400 | [diff] [blame] | 857 | |
Vladimir Sementsov-Ogievskiy | 299ea9f | 2020-02-05 14:20:38 +0300 | [diff] [blame] | 858 | for (offset = 0; |
| 859 | hbitmap_next_dirty_area(src, offset, src->orig_size, INT64_MAX, |
| 860 | &offset, &count); |
| 861 | offset += count) |
| 862 | { |
John Snow | c5b40c1 | 2019-07-29 16:35:53 -0400 | [diff] [blame] | 863 | hbitmap_set(dst, offset, count); |
John Snow | c5b40c1 | 2019-07-29 16:35:53 -0400 | [diff] [blame] | 864 | } |
Vladimir Sementsov-Ogievskiy | fa000f2 | 2018-10-29 16:23:15 -0400 | [diff] [blame] | 865 | } |
John Snow | ce1ffea | 2015-04-17 19:50:03 -0400 | [diff] [blame] | 866 | |
John Snow | be58721 | 2015-04-17 19:49:55 -0400 | [diff] [blame] | 867 | /** |
John Snow | 3bde4b0 | 2019-07-29 16:35:53 -0400 | [diff] [blame] | 868 | * Given HBitmaps A and B, let R := A (BITOR) B. |
| 869 | * Bitmaps A and B will not be modified, |
| 870 | * except when bitmap R is an alias of A or B. |
John Snow | be58721 | 2015-04-17 19:49:55 -0400 | [diff] [blame] | 871 | * |
| 872 | * @return true if the merge was successful, |
| 873 | * false if it was not attempted. |
| 874 | */ |
Vladimir Sementsov-Ogievskiy | fa000f2 | 2018-10-29 16:23:15 -0400 | [diff] [blame] | 875 | bool hbitmap_merge(const HBitmap *a, const HBitmap *b, HBitmap *result) |
John Snow | be58721 | 2015-04-17 19:49:55 -0400 | [diff] [blame] | 876 | { |
| 877 | int i; |
| 878 | uint64_t j; |
| 879 | |
Vladimir Sementsov-Ogievskiy | fa000f2 | 2018-10-29 16:23:15 -0400 | [diff] [blame] | 880 | if (!hbitmap_can_merge(a, b) || !hbitmap_can_merge(a, result)) { |
John Snow | be58721 | 2015-04-17 19:49:55 -0400 | [diff] [blame] | 881 | return false; |
| 882 | } |
Vladimir Sementsov-Ogievskiy | fa000f2 | 2018-10-29 16:23:15 -0400 | [diff] [blame] | 883 | assert(hbitmap_can_merge(b, result)); |
John Snow | be58721 | 2015-04-17 19:49:55 -0400 | [diff] [blame] | 884 | |
John Snow | 3bde4b0 | 2019-07-29 16:35:53 -0400 | [diff] [blame] | 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); |
John Snow | be58721 | 2015-04-17 19:49:55 -0400 | [diff] [blame] | 892 | return true; |
| 893 | } |
| 894 | |
John Snow | c5b40c1 | 2019-07-29 16:35:53 -0400 | [diff] [blame] | 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 | |
John Snow | be58721 | 2015-04-17 19:49:55 -0400 | [diff] [blame] | 908 | /* This merge is O(size), as BITS_PER_LONG and HBITMAP_LEVELS are constant. |
| 909 | * It may be possible to improve running times for sparsely populated maps |
| 910 | * by using hbitmap_iter_next, but this is suboptimal for dense maps. |
| 911 | */ |
John Snow | c5b40c1 | 2019-07-29 16:35:53 -0400 | [diff] [blame] | 912 | assert(a->size == b->size); |
John Snow | be58721 | 2015-04-17 19:49:55 -0400 | [diff] [blame] | 913 | for (i = HBITMAP_LEVELS - 1; i >= 0; i--) { |
| 914 | for (j = 0; j < a->sizes[i]; j++) { |
Vladimir Sementsov-Ogievskiy | fa000f2 | 2018-10-29 16:23:15 -0400 | [diff] [blame] | 915 | result->levels[i][j] = a->levels[i][j] | b->levels[i][j]; |
John Snow | be58721 | 2015-04-17 19:49:55 -0400 | [diff] [blame] | 916 | } |
| 917 | } |
| 918 | |
Eric Blake | d1dde71 | 2018-10-29 16:23:17 -0400 | [diff] [blame] | 919 | /* Recompute the dirty count */ |
| 920 | result->count = hb_count_between(result, 0, result->size - 1); |
| 921 | |
John Snow | be58721 | 2015-04-17 19:49:55 -0400 | [diff] [blame] | 922 | return true; |
| 923 | } |
Fam Zheng | 07ac4cd | 2016-10-13 17:58:22 -0400 | [diff] [blame] | 924 | |
Vladimir Sementsov-Ogievskiy | a3b5253 | 2017-06-28 15:05:25 +0300 | [diff] [blame] | 925 | char *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 | } |