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