include/qemu/hbitmap.h

   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 #ifndef HBITMAP_H
  13 #define HBITMAP_H
  14
  15 #include "bitops.h"
  16 #include "host-utils.h"
  17
  18 typedef struct HBitmap HBitmap;
  19 typedef struct HBitmapIter HBitmapIter;
  20
  21 #define BITS_PER_LEVEL         (BITS_PER_LONG == 32 ? 5 : 6)
  22
  23 /* For 32-bit, the largest that fits in a 4 GiB address space.
  24  * For 64-bit, the number of sectors in 1 PiB.  Good luck, in
  25  * either case... :)
  26  */
  27 #define HBITMAP_LOG_MAX_SIZE   (BITS_PER_LONG == 32 ? 34 : 41)
  28
  29 /* We need to place a sentinel in level 0 to speed up iteration.  Thus,
  30  * we do this instead of HBITMAP_LOG_MAX_SIZE / BITS_PER_LEVEL.  The
  31  * difference is that it allocates an extra level when HBITMAP_LOG_MAX_SIZE
  32  * is an exact multiple of BITS_PER_LEVEL.
  33  */
  34 #define HBITMAP_LEVELS         ((HBITMAP_LOG_MAX_SIZE / BITS_PER_LEVEL) + 1)
  35
  36 struct HBitmapIter {
  37     const HBitmap *hb;
  38
  39     /* Copied from hb for access in the inline functions (hb is opaque).  */
  40     int granularity;
  41
  42     /* Entry offset into the last-level array of longs.  */
  43     size_t pos;
  44
  45     /* The currently-active path in the tree.  Each item of cur[i] stores
  46      * the bits (i.e. the subtrees) yet to be processed under that node.
  47      */
  48     unsigned long cur[HBITMAP_LEVELS];
  49 };
  50
  51 /**
  52  * hbitmap_alloc:
  53  * @size: Number of bits in the bitmap.
  54  * @granularity: Granularity of the bitmap.  Aligned groups of 2^@granularity
  55  * bits will be represented by a single bit.  Each operation on a
  56  * range of bits first rounds the bits to determine which group they land
  57  * in, and then affect the entire set; iteration will only visit the first
  58  * bit of each group.
  59  *
  60  * Allocate a new HBitmap.
  61  */
  62 HBitmap *hbitmap_alloc(uint64_t size, int granularity);
  63
  64 /**
  65  * hbitmap_truncate:
  66  * @hb: The bitmap to change the size of.
  67  * @size: The number of elements to change the bitmap to accommodate.
  68  *
  69  * truncate or grow an existing bitmap to accommodate a new number of elements.
  70  * This may invalidate existing HBitmapIterators.
  71  */
  72 void hbitmap_truncate(HBitmap *hb, uint64_t size);
  73
  74 /**
  75  * hbitmap_merge:
  76  * @a: The bitmap to store the result in.
  77  * @b: The bitmap to merge into @a.
  78  * @return true if the merge was successful,
  79  *         false if it was not attempted.
  80  *
  81  * Merge two bitmaps together.
  82  * A := A (BITOR) B.
  83  * B is left unmodified.
  84  */
  85 bool hbitmap_merge(HBitmap *a, const HBitmap *b);
  86
  87 /**
  88  * hbitmap_empty:
  89  * @hb: HBitmap to operate on.
  90  *
  91  * Return whether the bitmap is empty.
  92  */
  93 bool hbitmap_empty(const HBitmap *hb);
  94
  95 /**
  96  * hbitmap_granularity:
  97  * @hb: HBitmap to operate on.
  98  *
  99  * Return the granularity of the HBitmap.
 100  */
 101 int hbitmap_granularity(const HBitmap *hb);
 102
 103 /**
 104  * hbitmap_count:
 105  * @hb: HBitmap to operate on.
 106  *
 107  * Return the number of bits set in the HBitmap.
 108  */
 109 uint64_t hbitmap_count(const HBitmap *hb);
 110
 111 /**
 112  * hbitmap_set:
 113  * @hb: HBitmap to operate on.
 114  * @start: First bit to set (0-based).
 115  * @count: Number of bits to set.
 116  *
 117  * Set a consecutive range of bits in an HBitmap.
 118  */
 119 void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count);
 120
 121 /**
 122  * hbitmap_reset:
 123  * @hb: HBitmap to operate on.
 124  * @start: First bit to reset (0-based).
 125  * @count: Number of bits to reset.
 126  *
 127  * Reset a consecutive range of bits in an HBitmap.
 128  */
 129 void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count);
 130
 131 /**
 132  * hbitmap_reset_all:
 133  * @hb: HBitmap to operate on.
 134  *
 135  * Reset all bits in an HBitmap.
 136  */
 137 void hbitmap_reset_all(HBitmap *hb);
 138
 139 /**
 140  * hbitmap_get:
 141  * @hb: HBitmap to operate on.
 142  * @item: Bit to query (0-based).
 143  *
 144  * Return whether the @item-th bit in an HBitmap is set.
 145  */
 146 bool hbitmap_get(const HBitmap *hb, uint64_t item);
 147
 148 /**
 149  * hbitmap_is_serializable:
 150  * @hb: HBitmap which should be (de-)serialized.
 151  *
 152  * Returns whether the bitmap can actually be (de-)serialized. Other
 153  * (de-)serialization functions may only be invoked if this function returns
 154  * true.
 155  *
 156  * Calling (de-)serialization functions does not affect a bitmap's
 157  * (de-)serializability.
 158  */
 159 bool hbitmap_is_serializable(const HBitmap *hb);
 160
 161 /**
 162  * hbitmap_serialization_granularity:
 163  * @hb: HBitmap to operate on.
 164  *
 165  * Granularity of serialization chunks, used by other serialization functions.
 166  * For every chunk:
 167  * 1. Chunk start should be aligned to this granularity.
 168  * 2. Chunk size should be aligned too, except for last chunk (for which
 169  *      start + count == hb->size)
 170  */
 171 uint64_t hbitmap_serialization_granularity(const HBitmap *hb);
 172
 173 /**
 174  * hbitmap_serialization_size:
 175  * @hb: HBitmap to operate on.
 176  * @start: Starting bit
 177  * @count: Number of bits
 178  *
 179  * Return number of bytes hbitmap_(de)serialize_part needs
 180  */
 181 uint64_t hbitmap_serialization_size(const HBitmap *hb,
 182                                     uint64_t start, uint64_t count);
 183
 184 /**
 185  * hbitmap_serialize_part
 186  * @hb: HBitmap to operate on.
 187  * @buf: Buffer to store serialized bitmap.
 188  * @start: First bit to store.
 189  * @count: Number of bits to store.
 190  *
 191  * Stores HBitmap data corresponding to given region. The format of saved data
 192  * is linear sequence of bits, so it can be used by hbitmap_deserialize_part
 193  * independently of endianness and size of HBitmap level array elements
 194  */
 195 void hbitmap_serialize_part(const HBitmap *hb, uint8_t *buf,
 196                             uint64_t start, uint64_t count);
 197
 198 /**
 199  * hbitmap_deserialize_part
 200  * @hb: HBitmap to operate on.
 201  * @buf: Buffer to restore bitmap data from.
 202  * @start: First bit to restore.
 203  * @count: Number of bits to restore.
 204  * @finish: Whether to call hbitmap_deserialize_finish automatically.
 205  *
 206  * Restores HBitmap data corresponding to given region. The format is the same
 207  * as for hbitmap_serialize_part.
 208  *
 209  * If @finish is false, caller must call hbitmap_serialize_finish before using
 210  * the bitmap.
 211  */
 212 void hbitmap_deserialize_part(HBitmap *hb, uint8_t *buf,
 213                               uint64_t start, uint64_t count,
 214                               bool finish);
 215
 216 /**
 217  * hbitmap_deserialize_zeroes
 218  * @hb: HBitmap to operate on.
 219  * @start: First bit to restore.
 220  * @count: Number of bits to restore.
 221  * @finish: Whether to call hbitmap_deserialize_finish automatically.
 222  *
 223  * Fills the bitmap with zeroes.
 224  *
 225  * If @finish is false, caller must call hbitmap_serialize_finish before using
 226  * the bitmap.
 227  */
 228 void hbitmap_deserialize_zeroes(HBitmap *hb, uint64_t start, uint64_t count,
 229                                 bool finish);
 230
 231 /**
 232  * hbitmap_deserialize_finish
 233  * @hb: HBitmap to operate on.
 234  *
 235  * Repair HBitmap after calling hbitmap_deserialize_data. Actually, all HBitmap
 236  * layers are restored here.
 237  */
 238 void hbitmap_deserialize_finish(HBitmap *hb);
 239
 240 /**
 241  * hbitmap_free:
 242  * @hb: HBitmap to operate on.
 243  *
 244  * Free an HBitmap and all of its associated memory.
 245  */
 246 void hbitmap_free(HBitmap *hb);
 247
 248 /**
 249  * hbitmap_iter_init:
 250  * @hbi: HBitmapIter to initialize.
 251  * @hb: HBitmap to iterate on.
 252  * @first: First bit to visit (0-based, must be strictly less than the
 253  * size of the bitmap).
 254  *
 255  * Set up @hbi to iterate on the HBitmap @hb.  hbitmap_iter_next will return
 256  * the lowest-numbered bit that is set in @hb, starting at @first.
 257  *
 258  * Concurrent setting of bits is acceptable, and will at worst cause the
 259  * iteration to miss some of those bits.  Resetting bits before the current
 260  * position of the iterator is also okay.  However, concurrent resetting of
 261  * bits can lead to unexpected behavior if the iterator has not yet reached
 262  * those bits.
 263  */
 264 void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first);
 265
 266 /* hbitmap_iter_skip_words:
 267  * @hbi: HBitmapIter to operate on.
 268  *
 269  * Internal function used by hbitmap_iter_next and hbitmap_iter_next_word.
 270  */
 271 unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
 272
 273 /* hbitmap_create_meta:
 274  * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap.
 275  * The caller owns the created bitmap and must call hbitmap_free_meta(hb) to
 276  * free it.
 277  *
 278  * Currently, we only guarantee that if a bit in the hbitmap is changed it
 279  * will be reflected in the meta bitmap, but we do not yet guarantee the
 280  * opposite.
 281  *
 282  * @hb: The HBitmap to operate on.
 283  * @chunk_size: How many bits in @hb does one bit in the meta track.
 284  */
 285 HBitmap *hbitmap_create_meta(HBitmap *hb, int chunk_size);
 286
 287 /* hbitmap_free_meta:
 288  * Free the meta bitmap of @hb.
 289  *
 290  * @hb: The HBitmap whose meta bitmap should be freed.
 291  */
 292 void hbitmap_free_meta(HBitmap *hb);
 293
 294 /**
 295  * hbitmap_iter_next:
 296  * @hbi: HBitmapIter to operate on.
 297  *
 298  * Return the next bit that is set in @hbi's associated HBitmap,
 299  * or -1 if all remaining bits are zero.
 300  */
 301 static inline int64_t hbitmap_iter_next(HBitmapIter *hbi)
 302 {
 303     unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1];
 304     int64_t item;
 305
 306     if (cur == 0) {
 307         cur = hbitmap_iter_skip_words(hbi);
 308         if (cur == 0) {
 309             return -1;
 310         }
 311     }
 312
 313     /* The next call will resume work from the next bit.  */
 314     hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1);
 315     item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + ctzl(cur);
 316
 317     return item << hbi->granularity;
 318 }
 319
 320 /**
 321  * hbitmap_iter_next_word:
 322  * @hbi: HBitmapIter to operate on.
 323  * @p_cur: Location where to store the next non-zero word.
 324  *
 325  * Return the index of the next nonzero word that is set in @hbi's
 326  * associated HBitmap, and set *p_cur to the content of that word
 327  * (bits before the index that was passed to hbitmap_iter_init are
 328  * trimmed on the first call).  Return -1, and set *p_cur to zero,
 329  * if all remaining words are zero.
 330  */
 331 static inline size_t hbitmap_iter_next_word(HBitmapIter *hbi, unsigned long *p_cur)
 332 {
 333     unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1];
 334
 335     if (cur == 0) {
 336         cur = hbitmap_iter_skip_words(hbi);
 337         if (cur == 0) {
 338             *p_cur = 0;
 339             return -1;
 340         }
 341     }
 342
 343     /* The next call will resume work from the next word.  */
 344     hbi->cur[HBITMAP_LEVELS - 1] = 0;
 345     *p_cur = cur;
 346     return hbi->pos;
 347 }
 348
 349
 350 #endif