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  *
  77  * Store result of merging @a and @b into @result.
  78  * @result is allowed to be equal to @a or @b.
  79  *
  80  * Return true if the merge was successful,
  81  *        false if it was not attempted.
  82  */
  83 bool hbitmap_merge(const HBitmap *a, const HBitmap *b, HBitmap *result);
  84
  85 /**
  86  * hbitmap_can_merge:
  87  *
  88  * hbitmap_can_merge(a, b) && hbitmap_can_merge(a, result) is sufficient and
  89  * necessary for hbitmap_merge will not fail.
  90  *
  91  */
  92 bool hbitmap_can_merge(const HBitmap *a, const HBitmap *b);
  93
  94 /**
  95  * hbitmap_empty:
  96  * @hb: HBitmap to operate on.
  97  *
  98  * Return whether the bitmap is empty.
  99  */
 100 bool hbitmap_empty(const HBitmap *hb);
 101
 102 /**
 103  * hbitmap_granularity:
 104  * @hb: HBitmap to operate on.
 105  *
 106  * Return the granularity of the HBitmap.
 107  */
 108 int hbitmap_granularity(const HBitmap *hb);
 109
 110 /**
 111  * hbitmap_count:
 112  * @hb: HBitmap to operate on.
 113  *
 114  * Return the number of bits set in the HBitmap.
 115  */
 116 uint64_t hbitmap_count(const HBitmap *hb);
 117
 118 /**
 119  * hbitmap_set:
 120  * @hb: HBitmap to operate on.
 121  * @start: First bit to set (0-based).
 122  * @count: Number of bits to set.
 123  *
 124  * Set a consecutive range of bits in an HBitmap.
 125  */
 126 void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count);
 127
 128 /**
 129  * hbitmap_reset:
 130  * @hb: HBitmap to operate on.
 131  * @start: First bit to reset (0-based).
 132  * @count: Number of bits to reset.
 133  *
 134  * Reset a consecutive range of bits in an HBitmap.
 135  * @start and @count must be aligned to bitmap granularity. The only exception
 136  * is resetting the tail of the bitmap: @count may be equal to hb->orig_size -
 137  * @start, in this case @count may be not aligned. The sum of @start + @count is
 138  * allowed to be greater than hb->orig_size, but only if @start < hb->orig_size
 139  * and @start + @count = ALIGN_UP(hb->orig_size, granularity).
 140  */
 141 void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count);
 142
 143 /**
 144  * hbitmap_reset_all:
 145  * @hb: HBitmap to operate on.
 146  *
 147  * Reset all bits in an HBitmap.
 148  */
 149 void hbitmap_reset_all(HBitmap *hb);
 150
 151 /**
 152  * hbitmap_get:
 153  * @hb: HBitmap to operate on.
 154  * @item: Bit to query (0-based).
 155  *
 156  * Return whether the @item-th bit in an HBitmap is set.
 157  */
 158 bool hbitmap_get(const HBitmap *hb, uint64_t item);
 159
 160 /**
 161  * hbitmap_is_serializable:
 162  * @hb: HBitmap which should be (de-)serialized.
 163  *
 164  * Returns whether the bitmap can actually be (de-)serialized. Other
 165  * (de-)serialization functions may only be invoked if this function returns
 166  * true.
 167  *
 168  * Calling (de-)serialization functions does not affect a bitmap's
 169  * (de-)serializability.
 170  */
 171 bool hbitmap_is_serializable(const HBitmap *hb);
 172
 173 /**
 174  * hbitmap_serialization_align:
 175  * @hb: HBitmap to operate on.
 176  *
 177  * Required alignment of serialization chunks, used by other serialization
 178  * functions. For every chunk:
 179  * 1. Chunk start should be aligned to this granularity.
 180  * 2. Chunk size should be aligned too, except for last chunk (for which
 181  *      start + count == hb->size)
 182  */
 183 uint64_t hbitmap_serialization_align(const HBitmap *hb);
 184
 185 /**
 186  * hbitmap_serialization_size:
 187  * @hb: HBitmap to operate on.
 188  * @start: Starting bit
 189  * @count: Number of bits
 190  *
 191  * Return number of bytes hbitmap_(de)serialize_part needs
 192  */
 193 uint64_t hbitmap_serialization_size(const HBitmap *hb,
 194                                     uint64_t start, uint64_t count);
 195
 196 /**
 197  * hbitmap_serialize_part
 198  * @hb: HBitmap to operate on.
 199  * @buf: Buffer to store serialized bitmap.
 200  * @start: First bit to store.
 201  * @count: Number of bits to store.
 202  *
 203  * Stores HBitmap data corresponding to given region. The format of saved data
 204  * is linear sequence of bits, so it can be used by hbitmap_deserialize_part
 205  * independently of endianness and size of HBitmap level array elements
 206  */
 207 void hbitmap_serialize_part(const HBitmap *hb, uint8_t *buf,
 208                             uint64_t start, uint64_t count);
 209
 210 /**
 211  * hbitmap_deserialize_part
 212  * @hb: HBitmap to operate on.
 213  * @buf: Buffer to restore bitmap data from.
 214  * @start: First bit to restore.
 215  * @count: Number of bits to restore.
 216  * @finish: Whether to call hbitmap_deserialize_finish automatically.
 217  *
 218  * Restores HBitmap data corresponding to given region. The format is the same
 219  * as for hbitmap_serialize_part.
 220  *
 221  * If @finish is false, caller must call hbitmap_serialize_finish before using
 222  * the bitmap.
 223  */
 224 void hbitmap_deserialize_part(HBitmap *hb, uint8_t *buf,
 225                               uint64_t start, uint64_t count,
 226                               bool finish);
 227
 228 /**
 229  * hbitmap_deserialize_zeroes
 230  * @hb: HBitmap to operate on.
 231  * @start: First bit to restore.
 232  * @count: Number of bits to restore.
 233  * @finish: Whether to call hbitmap_deserialize_finish automatically.
 234  *
 235  * Fills the bitmap with zeroes.
 236  *
 237  * If @finish is false, caller must call hbitmap_serialize_finish before using
 238  * the bitmap.
 239  */
 240 void hbitmap_deserialize_zeroes(HBitmap *hb, uint64_t start, uint64_t count,
 241                                 bool finish);
 242
 243 /**
 244  * hbitmap_deserialize_ones
 245  * @hb: HBitmap to operate on.
 246  * @start: First bit to restore.
 247  * @count: Number of bits to restore.
 248  * @finish: Whether to call hbitmap_deserialize_finish automatically.
 249  *
 250  * Fills the bitmap with ones.
 251  *
 252  * If @finish is false, caller must call hbitmap_serialize_finish before using
 253  * the bitmap.
 254  */
 255 void hbitmap_deserialize_ones(HBitmap *hb, uint64_t start, uint64_t count,
 256                               bool finish);
 257
 258 /**
 259  * hbitmap_deserialize_finish
 260  * @hb: HBitmap to operate on.
 261  *
 262  * Repair HBitmap after calling hbitmap_deserialize_data. Actually, all HBitmap
 263  * layers are restored here.
 264  */
 265 void hbitmap_deserialize_finish(HBitmap *hb);
 266
 267 /**
 268  * hbitmap_sha256:
 269  * @bitmap: HBitmap to operate on.
 270  *
 271  * Returns SHA256 hash of the last level.
 272  */
 273 char *hbitmap_sha256(const HBitmap *bitmap, Error **errp);
 274
 275 /**
 276  * hbitmap_free:
 277  * @hb: HBitmap to operate on.
 278  *
 279  * Free an HBitmap and all of its associated memory.
 280  */
 281 void hbitmap_free(HBitmap *hb);
 282
 283 /**
 284  * hbitmap_iter_init:
 285  * @hbi: HBitmapIter to initialize.
 286  * @hb: HBitmap to iterate on.
 287  * @first: First bit to visit (0-based, must be strictly less than the
 288  * size of the bitmap).
 289  *
 290  * Set up @hbi to iterate on the HBitmap @hb.  hbitmap_iter_next will return
 291  * the lowest-numbered bit that is set in @hb, starting at @first.
 292  *
 293  * Concurrent setting of bits is acceptable, and will at worst cause the
 294  * iteration to miss some of those bits.
 295  *
 296  * The concurrent resetting of bits is OK.
 297  */
 298 void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first);
 299
 300 /* hbitmap_iter_skip_words:
 301  * @hbi: HBitmapIter to operate on.
 302  *
 303  * Internal function used by hbitmap_iter_next and hbitmap_iter_next_word.
 304  */
 305 unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
 306
 307 /* hbitmap_next_zero:
 308  *
 309  * Find next not dirty bit within selected range. If not found, return -1.
 310  *
 311  * @hb: The HBitmap to operate on
 312  * @start: The bit to start from.
 313  * @count: Number of bits to proceed. If @start+@count > bitmap size, the whole
 314  * bitmap is looked through. You can use UINT64_MAX as @count to search up to
 315  * the bitmap end.
 316  */
 317 int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t count);
 318
 319 /* hbitmap_next_dirty_area:
 320  * @hb: The HBitmap to operate on
 321  * @start: in-out parameter.
 322  *         in: the offset to start from
 323  *         out: (if area found) start of found area
 324  * @count: in-out parameter.
 325  *         in: length of requested region
 326  *         out: length of found area
 327  *
 328  * If dirty area found within [@start, @start + @count), returns true and sets
 329  * @offset and @bytes appropriately. Otherwise returns false and leaves @offset
 330  * and @bytes unchanged.
 331  */
 332 bool hbitmap_next_dirty_area(const HBitmap *hb, uint64_t *start,
 333                              uint64_t *count);
 334
 335 /* hbitmap_create_meta:
 336  * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap.
 337  * The caller owns the created bitmap and must call hbitmap_free_meta(hb) to
 338  * free it.
 339  *
 340  * Currently, we only guarantee that if a bit in the hbitmap is changed it
 341  * will be reflected in the meta bitmap, but we do not yet guarantee the
 342  * opposite.
 343  *
 344  * @hb: The HBitmap to operate on.
 345  * @chunk_size: How many bits in @hb does one bit in the meta track.
 346  */
 347 HBitmap *hbitmap_create_meta(HBitmap *hb, int chunk_size);
 348
 349 /* hbitmap_free_meta:
 350  * Free the meta bitmap of @hb.
 351  *
 352  * @hb: The HBitmap whose meta bitmap should be freed.
 353  */
 354 void hbitmap_free_meta(HBitmap *hb);
 355
 356 /**
 357  * hbitmap_iter_next:
 358  * @hbi: HBitmapIter to operate on.
 359  *
 360  * Return the next bit that is set in @hbi's associated HBitmap,
 361  * or -1 if all remaining bits are zero.
 362  */
 363 int64_t hbitmap_iter_next(HBitmapIter *hbi);
 364
 365 /**
 366  * hbitmap_iter_next_word:
 367  * @hbi: HBitmapIter to operate on.
 368  * @p_cur: Location where to store the next non-zero word.
 369  *
 370  * Return the index of the next nonzero word that is set in @hbi's
 371  * associated HBitmap, and set *p_cur to the content of that word
 372  * (bits before the index that was passed to hbitmap_iter_init are
 373  * trimmed on the first call).  Return -1, and set *p_cur to zero,
 374  * if all remaining words are zero.
 375  */
 376 static inline size_t hbitmap_iter_next_word(HBitmapIter *hbi, unsigned long *p_cur)
 377 {
 378     unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1];
 379
 380     if (cur == 0) {
 381         cur = hbitmap_iter_skip_words(hbi);
 382         if (cur == 0) {
 383             *p_cur = 0;
 384             return -1;
 385         }
 386     }
 387
 388     /* The next call will resume work from the next word.  */
 389     hbi->cur[HBITMAP_LEVELS - 1] = 0;
 390     *p_cur = cur;
 391     return hbi->pos;
 392 }
 393
 394
 395 #endif