qemu/util/hbitmap.c

   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
  12 #include <string.h>
  13 #include <glib.h>
  14 #include <assert.h>
  15 #include "qemu/osdep.h"
  16 #include "qemu/hbitmap.h"
  17 #include "qemu/host-utils.h"
  18 #include "trace.h"
  19
  20 /* HBitmaps provides an array of bits.  The bits are stored as usual in an
  21  * array of unsigned longs, but HBitmap is also optimized to provide fast
  22  * iteration over set bits; going from one bit to the next is O(logB n)
  23  * worst case, with B = sizeof(long) * CHAR_BIT: the result is low enough
  24  * that the number of levels is in fact fixed.
  25  *
  26  * In order to do this, it stacks multiple bitmaps with progressively coarser
  27  * granularity; in all levels except the last, bit N is set iff the N-th
  28  * unsigned long is nonzero in the immediately next level.  When iteration
  29  * completes on the last level it can examine the 2nd-last level to quickly
  30  * skip entire words, and even do so recursively to skip blocks of 64 words or
  31  * powers thereof (32 on 32-bit machines).
  32  *
  33  * Given an index in the bitmap, it can be split in group of bits like
  34  * this (for the 64-bit case):
  35  *
  36  *   bits 0-57 => word in the last bitmap     | bits 58-63 => bit in the word
  37  *   bits 0-51 => word in the 2nd-last bitmap | bits 52-57 => bit in the word
  38  *   bits 0-45 => word in the 3rd-last bitmap | bits 46-51 => bit in the word
  39  *
  40  * So it is easy to move up simply by shifting the index right by
  41  * log2(BITS_PER_LONG) bits.  To move down, you shift the index left
  42  * similarly, and add the word index within the group.  Iteration uses
  43  * ffs (find first set bit) to find the next word to examine; this
  44  * operation can be done in constant time in most current architectures.
  45  *
  46  * Setting or clearing a range of m bits on all levels, the work to perform
  47  * is O(m + m/W + m/W^2 + ...), which is O(m) like on a regular bitmap.
  48  *
  49  * When iterating on a bitmap, each bit (on any level) is only visited
  50  * once.  Hence, The total cost of visiting a bitmap with m bits in it is
  51  * the number of bits that are set in all bitmaps.  Unless the bitmap is
  52  * extremely sparse, this is also O(m + m/W + m/W^2 + ...), so the amortized
  53  * cost of advancing from one bit to the next is usually constant (worst case
  54  * O(logB n) as in the non-amortized complexity).
  55  */
  56
  57 struct HBitmap {
  58     /* Number of total bits in the bottom level.  */
  59     uint64_t size;
  60
  61     /* Number of set bits in the bottom level.  */
  62     uint64_t count;
  63
  64     /* A scaling factor.  Given a granularity of G, each bit in the bitmap will
  65      * will actually represent a group of 2^G elements.  Each operation on a
  66      * range of bits first rounds the bits to determine which group they land
  67      * in, and then affect the entire page; iteration will only visit the first
  68      * bit of each group.  Here is an example of operations in a size-16,
  69      * granularity-1 HBitmap:
  70      *
  71      *    initial state            00000000
  72      *    set(start=0, count=9)    11111000 (iter: 0, 2, 4, 6, 8)
  73      *    reset(start=1, count=3)  00111000 (iter: 4, 6, 8)
  74      *    set(start=9, count=2)    00111100 (iter: 4, 6, 8, 10)
  75      *    reset(start=5, count=5)  00000000
  76      *
  77      * From an implementation point of view, when setting or resetting bits,
  78      * the bitmap will scale bit numbers right by this amount of bits.  When
  79      * iterating, the bitmap will scale bit numbers left by this amount of
  80      * bits.
  81      */
  82     int granularity;
  83
  84     /* A number of progressively less coarse bitmaps (i.e. level 0 is the
  85      * coarsest).  Each bit in level N represents a word in level N+1 that
  86      * has a set bit, except the last level where each bit represents the
  87      * actual bitmap.
  88      *
  89      * Note that all bitmaps have the same number of levels.  Even a 1-bit
  90      * bitmap will still allocate HBITMAP_LEVELS arrays.
  91      */
  92     unsigned long *levels[HBITMAP_LEVELS];
  93
  94     /* The length of each levels[] array. */
  95     uint64_t sizes[HBITMAP_LEVELS];
  96 };
  97
  98 /* Advance hbi to the next nonzero word and return it.  hbi->pos
  99  * is updated.  Returns zero if we reach the end of the bitmap.
 100  */
 101 unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi)
 102 {
 103     size_t pos = hbi->pos;
 104     const HBitmap *hb = hbi->hb;
 105     unsigned i = HBITMAP_LEVELS - 1;
 106
 107     unsigned long cur;
 108     do {
 109         cur = hbi->cur[--i];
 110         pos >>= BITS_PER_LEVEL;
 111     } while (cur == 0);
 112
 113     /* Check for end of iteration.  We always use fewer than BITS_PER_LONG
 114      * bits in the level 0 bitmap; thus we can repurpose the most significant
 115      * bit as a sentinel.  The sentinel is set in hbitmap_alloc and ensures
 116      * that the above loop ends even without an explicit check on i.
 117      */
 118
 119     if (i == 0 && cur == (1UL << (BITS_PER_LONG - 1))) {
 120         return 0;
 121     }
 122     for (; i < HBITMAP_LEVELS - 1; i++) {
 123         /* Shift back pos to the left, matching the right shifts above.
 124          * The index of this word's least significant set bit provides
 125          * the low-order bits.
 126          */
 127         assert(cur);
 128         pos = (pos << BITS_PER_LEVEL) + ctzl(cur);
 129         hbi->cur[i] = cur & (cur - 1);
 130
 131         /* Set up next level for iteration.  */
 132         cur = hb->levels[i + 1][pos];
 133     }
 134
 135     hbi->pos = pos;
 136     trace_hbitmap_iter_skip_words(hbi->hb, hbi, pos, cur);
 137
 138     assert(cur);
 139     return cur;
 140 }
 141
 142 void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first)
 143 {
 144     unsigned i, bit;
 145     uint64_t pos;
 146
 147     hbi->hb = hb;
 148     pos = first >> hb->granularity;
 149     assert(pos < hb->size);
 150     hbi->pos = pos >> BITS_PER_LEVEL;
 151     hbi->granularity = hb->granularity;
 152
 153     for (i = HBITMAP_LEVELS; i-- > 0; ) {
 154         bit = pos & (BITS_PER_LONG - 1);
 155         pos >>= BITS_PER_LEVEL;
 156
 157         /* Drop bits representing items before first.  */
 158         hbi->cur[i] = hb->levels[i][pos] & ~((1UL << bit) - 1);
 159
 160         /* We have already added level i+1, so the lowest set bit has
 161          * been processed.  Clear it.
 162          */
 163         if (i != HBITMAP_LEVELS - 1) {
 164             hbi->cur[i] &= ~(1UL << bit);
 165         }
 166     }
 167 }
 168
 169 bool hbitmap_empty(const HBitmap *hb)
 170 {
 171     return hb->count == 0;
 172 }
 173
 174 int hbitmap_granularity(const HBitmap *hb)
 175 {
 176     return hb->granularity;
 177 }
 178
 179 uint64_t hbitmap_count(const HBitmap *hb)
 180 {
 181     return hb->count << hb->granularity;
 182 }
 183
 184 /* Count the number of set bits between start and end, not accounting for
 185  * the granularity.  Also an example of how to use hbitmap_iter_next_word.
 186  */
 187 static uint64_t hb_count_between(HBitmap *hb, uint64_t start, uint64_t last)
 188 {
 189     HBitmapIter hbi;
 190     uint64_t count = 0;
 191     uint64_t end = last + 1;
 192     unsigned long cur;
 193     size_t pos;
 194
 195     hbitmap_iter_init(&hbi, hb, start << hb->granularity);
 196     for (;;) {
 197         pos = hbitmap_iter_next_word(&hbi, &cur);
 198         if (pos >= (end >> BITS_PER_LEVEL)) {
 199             break;
 200         }
 201         count += ctpopl(cur);
 202     }
 203
 204     if (pos == (end >> BITS_PER_LEVEL)) {
 205         /* Drop bits representing the END-th and subsequent items.  */
 206         int bit = end & (BITS_PER_LONG - 1);
 207         cur &= (1UL << bit) - 1;
 208         count += ctpopl(cur);
 209     }
 210
 211     return count;
 212 }
 213
 214 /* Setting starts at the last layer and propagates up if an element
 215  * changes from zero to non-zero.
 216  */
 217 static inline bool hb_set_elem(unsigned long *elem, uint64_t start, uint64_t last)
 218 {
 219     unsigned long mask;
 220     bool changed;
 221
 222     assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL));
 223     assert(start <= last);
 224
 225     mask = 2UL << (last & (BITS_PER_LONG - 1));
 226     mask -= 1UL << (start & (BITS_PER_LONG - 1));
 227     changed = (*elem == 0);
 228     *elem |= mask;
 229     return changed;
 230 }
 231
 232 /* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)... */
 233 static void hb_set_between(HBitmap *hb, int level, uint64_t start, uint64_t last)
 234 {
 235     size_t pos = start >> BITS_PER_LEVEL;
 236     size_t lastpos = last >> BITS_PER_LEVEL;
 237     bool changed = false;
 238     size_t i;
 239
 240     i = pos;
 241     if (i < lastpos) {
 242         uint64_t next = (start | (BITS_PER_LONG - 1)) + 1;
 243         changed |= hb_set_elem(&hb->levels[level][i], start, next - 1);
 244         for (;;) {
 245             start = next;
 246             next += BITS_PER_LONG;
 247             if (++i == lastpos) {
 248                 break;
 249             }
 250             changed |= (hb->levels[level][i] == 0);
 251             hb->levels[level][i] = ~0UL;
 252         }
 253     }
 254     changed |= hb_set_elem(&hb->levels[level][i], start, last);
 255
 256     /* If there was any change in this layer, we may have to update
 257      * the one above.
 258      */
 259     if (level > 0 && changed) {
 260         hb_set_between(hb, level - 1, pos, lastpos);
 261     }
 262 }
 263
 264 void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count)
 265 {
 266     /* Compute range in the last layer.  */
 267     uint64_t last = start + count - 1;
 268
 269     trace_hbitmap_set(hb, start, count,
 270                       start >> hb->granularity, last >> hb->granularity);
 271
 272     start >>= hb->granularity;
 273     last >>= hb->granularity;
 274     count = last - start + 1;
 275
 276     hb->count += count - hb_count_between(hb, start, last);
 277     hb_set_between(hb, HBITMAP_LEVELS - 1, start, last);
 278 }
 279
 280 /* Resetting works the other way round: propagate up if the new
 281  * value is zero.
 282  */
 283 static inline bool hb_reset_elem(unsigned long *elem, uint64_t start, uint64_t last)
 284 {
 285     unsigned long mask;
 286     bool blanked;
 287
 288     assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL));
 289     assert(start <= last);
 290
 291     mask = 2UL << (last & (BITS_PER_LONG - 1));
 292     mask -= 1UL << (start & (BITS_PER_LONG - 1));
 293     blanked = *elem != 0 && ((*elem & ~mask) == 0);
 294     *elem &= ~mask;
 295     return blanked;
 296 }
 297
 298 /* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)... */
 299 static void hb_reset_between(HBitmap *hb, int level, uint64_t start, uint64_t last)
 300 {
 301     size_t pos = start >> BITS_PER_LEVEL;
 302     size_t lastpos = last >> BITS_PER_LEVEL;
 303     bool changed = false;
 304     size_t i;
 305
 306     i = pos;
 307     if (i < lastpos) {
 308         uint64_t next = (start | (BITS_PER_LONG - 1)) + 1;
 309
 310         /* Here we need a more complex test than when setting bits.  Even if
 311          * something was changed, we must not blank bits in the upper level
 312          * unless the lower-level word became entirely zero.  So, remove pos
 313          * from the upper-level range if bits remain set.
 314          */
 315         if (hb_reset_elem(&hb->levels[level][i], start, next - 1)) {
 316             changed = true;
 317         } else {
 318             pos++;
 319         }
 320
 321         for (;;) {
 322             start = next;
 323             next += BITS_PER_LONG;
 324             if (++i == lastpos) {
 325                 break;
 326             }
 327             changed |= (hb->levels[level][i] != 0);
 328             hb->levels[level][i] = 0UL;
 329         }
 330     }
 331
 332     /* Same as above, this time for lastpos.  */
 333     if (hb_reset_elem(&hb->levels[level][i], start, last)) {
 334         changed = true;
 335     } else {
 336         lastpos--;
 337     }
 338
 339     if (level > 0 && changed) {
 340         hb_reset_between(hb, level - 1, pos, lastpos);
 341     }
 342 }
 343
 344 void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count)
 345 {
 346     /* Compute range in the last layer.  */
 347     uint64_t last = start + count - 1;
 348
 349     trace_hbitmap_reset(hb, start, count,
 350                         start >> hb->granularity, last >> hb->granularity);
 351
 352     start >>= hb->granularity;
 353     last >>= hb->granularity;
 354
 355     hb->count -= hb_count_between(hb, start, last);
 356     hb_reset_between(hb, HBITMAP_LEVELS - 1, start, last);
 357 }
 358
 359 void hbitmap_reset_all(HBitmap *hb)
 360 {
 361     unsigned int i;
 362
 363     /* Same as hbitmap_alloc() except for memset() instead of malloc() */
 364     for (i = HBITMAP_LEVELS; --i >= 1; ) {
 365         memset(hb->levels[i], 0, hb->sizes[i] * sizeof(unsigned long));
 366     }
 367
 368     hb->levels[0][0] = 1UL << (BITS_PER_LONG - 1);
 369     hb->count = 0;
 370 }
 371
 372 bool hbitmap_get(const HBitmap *hb, uint64_t item)
 373 {
 374     /* Compute position and bit in the last layer.  */
 375     uint64_t pos = item >> hb->granularity;
 376     unsigned long bit = 1UL << (pos & (BITS_PER_LONG - 1));
 377
 378     return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0;
 379 }
 380
 381 void hbitmap_free(HBitmap *hb)
 382 {
 383     unsigned i;
 384     for (i = HBITMAP_LEVELS; i-- > 0; ) {
 385         g_free(hb->levels[i]);
 386     }
 387     g_free(hb);
 388 }
 389
 390 HBitmap *hbitmap_alloc(uint64_t size, int granularity)
 391 {
 392     HBitmap *hb = g_new0(struct HBitmap, 1);
 393     unsigned i;
 394
 395     assert(granularity >= 0 && granularity < 64);
 396     size = (size + (1ULL << granularity) - 1) >> granularity;
 397     assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
 398
 399     hb->size = size;
 400     hb->granularity = granularity;
 401     for (i = HBITMAP_LEVELS; i-- > 0; ) {
 402         size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
 403         hb->sizes[i] = size;
 404         hb->levels[i] = g_new0(unsigned long, size);
 405     }
 406
 407     /* We necessarily have free bits in level 0 due to the definition
 408      * of HBITMAP_LEVELS, so use one for a sentinel.  This speeds up
 409      * hbitmap_iter_skip_words.
 410      */
 411     assert(size == 1);
 412     hb->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);
 413     return hb;
 414 }
 415
 416 void hbitmap_truncate(HBitmap *hb, uint64_t size)
 417 {
 418     bool shrink;
 419     unsigned i;
 420     uint64_t num_elements = size;
 421     uint64_t old;
 422
 423     /* Size comes in as logical elements, adjust for granularity. */
 424     size = (size + (1ULL << hb->granularity) - 1) >> hb->granularity;
 425     assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
 426     shrink = size < hb->size;
 427
 428     /* bit sizes are identical; nothing to do. */
 429     if (size == hb->size) {
 430         return;
 431     }
 432
 433     /* If we're losing bits, let's clear those bits before we invalidate all of
 434      * our invariants. This helps keep the bitcount consistent, and will prevent
 435      * us from carrying around garbage bits beyond the end of the map.
 436      */
 437     if (shrink) {
 438         /* Don't clear partial granularity groups;
 439          * start at the first full one. */
 440         uint64_t start = QEMU_ALIGN_UP(num_elements, 1 << hb->granularity);
 441         uint64_t fix_count = (hb->size << hb->granularity) - start;
 442
 443         assert(fix_count);
 444         hbitmap_reset(hb, start, fix_count);
 445     }
 446
 447     hb->size = size;
 448     for (i = HBITMAP_LEVELS; i-- > 0; ) {
 449         size = MAX(BITS_TO_LONGS(size), 1);
 450         if (hb->sizes[i] == size) {
 451             break;
 452         }
 453         old = hb->sizes[i];
 454         hb->sizes[i] = size;
 455         hb->levels[i] = g_realloc(hb->levels[i], size * sizeof(unsigned long));
 456         if (!shrink) {
 457             memset(&hb->levels[i][old], 0x00,
 458                    (size - old) * sizeof(*hb->levels[i]));
 459         }
 460     }
 461 }
 462
 463
 464 /**
 465  * Given HBitmaps A and B, let A := A (BITOR) B.
 466  * Bitmap B will not be modified.
 467  *
 468  * @return true if the merge was successful,
 469  *         false if it was not attempted.
 470  */
 471 bool hbitmap_merge(HBitmap *a, const HBitmap *b)
 472 {
 473     int i;
 474     uint64_t j;
 475
 476     if ((a->size != b->size) || (a->granularity != b->granularity)) {
 477         return false;
 478     }
 479
 480     if (hbitmap_count(b) == 0) {
 481         return true;
 482     }
 483
 484     /* This merge is O(size), as BITS_PER_LONG and HBITMAP_LEVELS are constant.
 485      * It may be possible to improve running times for sparsely populated maps
 486      * by using hbitmap_iter_next, but this is suboptimal for dense maps.
 487      */
 488     for (i = HBITMAP_LEVELS - 1; i >= 0; i--) {
 489         for (j = 0; j < a->sizes[i]; j++) {
 490             a->levels[i][j] |= b->levels[i][j];
 491         }
 492     }
 493
 494     return true;
 495 }