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