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 18typedef struct HBitmap HBitmap; 19typedef 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 36struct 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 */ 62HBitmap *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 */ 72void 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 */ 85bool 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 */ 93bool 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 */ 101int 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 */ 109uint64_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 */ 119void 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 */ 129void 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 */ 137void 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 */ 146bool 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 */ 159bool hbitmap_is_serializable(const HBitmap *hb); 160 161/** 162 * hbitmap_serialization_align: 163 * @hb: HBitmap to operate on. 164 * 165 * Required alignment of serialization chunks, used by other serialization 166 * functions. 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 */ 171uint64_t hbitmap_serialization_align(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 */ 181uint64_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 */ 195void 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 */ 212void 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 */ 228void hbitmap_deserialize_zeroes(HBitmap *hb, uint64_t start, uint64_t count, 229 bool finish); 230 231/** 232 * hbitmap_deserialize_ones 233 * @hb: HBitmap to operate on. 234 * @start: First bit to restore. 235 * @count: Number of bits to restore. 236 * @finish: Whether to call hbitmap_deserialize_finish automatically. 237 * 238 * Fills the bitmap with ones. 239 * 240 * If @finish is false, caller must call hbitmap_serialize_finish before using 241 * the bitmap. 242 */ 243void hbitmap_deserialize_ones(HBitmap *hb, uint64_t start, uint64_t count, 244 bool finish); 245 246/** 247 * hbitmap_deserialize_finish 248 * @hb: HBitmap to operate on. 249 * 250 * Repair HBitmap after calling hbitmap_deserialize_data. Actually, all HBitmap 251 * layers are restored here. 252 */ 253void hbitmap_deserialize_finish(HBitmap *hb); 254 255/** 256 * hbitmap_sha256: 257 * @bitmap: HBitmap to operate on. 258 * 259 * Returns SHA256 hash of the last level. 260 */ 261char *hbitmap_sha256(const HBitmap *bitmap, Error **errp); 262 263/** 264 * hbitmap_free: 265 * @hb: HBitmap to operate on. 266 * 267 * Free an HBitmap and all of its associated memory. 268 */ 269void hbitmap_free(HBitmap *hb); 270 271/** 272 * hbitmap_iter_init: 273 * @hbi: HBitmapIter to initialize. 274 * @hb: HBitmap to iterate on. 275 * @first: First bit to visit (0-based, must be strictly less than the 276 * size of the bitmap). 277 * 278 * Set up @hbi to iterate on the HBitmap @hb. hbitmap_iter_next will return 279 * the lowest-numbered bit that is set in @hb, starting at @first. 280 * 281 * Concurrent setting of bits is acceptable, and will at worst cause the 282 * iteration to miss some of those bits. 283 * 284 * The concurrent resetting of bits is OK. 285 */ 286void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first); 287 288/* hbitmap_iter_skip_words: 289 * @hbi: HBitmapIter to operate on. 290 * 291 * Internal function used by hbitmap_iter_next and hbitmap_iter_next_word. 292 */ 293unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi); 294 295/* hbitmap_next_zero: 296 * @hb: The HBitmap to operate on 297 * @start: The bit to start from. 298 * 299 * Find next not dirty bit. 300 */ 301int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start); 302 303/* hbitmap_create_meta: 304 * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap. 305 * The caller owns the created bitmap and must call hbitmap_free_meta(hb) to 306 * free it. 307 * 308 * Currently, we only guarantee that if a bit in the hbitmap is changed it 309 * will be reflected in the meta bitmap, but we do not yet guarantee the 310 * opposite. 311 * 312 * @hb: The HBitmap to operate on. 313 * @chunk_size: How many bits in @hb does one bit in the meta track. 314 */ 315HBitmap *hbitmap_create_meta(HBitmap *hb, int chunk_size); 316 317/* hbitmap_free_meta: 318 * Free the meta bitmap of @hb. 319 * 320 * @hb: The HBitmap whose meta bitmap should be freed. 321 */ 322void hbitmap_free_meta(HBitmap *hb); 323 324/** 325 * hbitmap_iter_next: 326 * @hbi: HBitmapIter to operate on. 327 * 328 * Return the next bit that is set in @hbi's associated HBitmap, 329 * or -1 if all remaining bits are zero. 330 */ 331int64_t hbitmap_iter_next(HBitmapIter *hbi); 332 333/** 334 * hbitmap_iter_next_word: 335 * @hbi: HBitmapIter to operate on. 336 * @p_cur: Location where to store the next non-zero word. 337 * 338 * Return the index of the next nonzero word that is set in @hbi's 339 * associated HBitmap, and set *p_cur to the content of that word 340 * (bits before the index that was passed to hbitmap_iter_init are 341 * trimmed on the first call). Return -1, and set *p_cur to zero, 342 * if all remaining words are zero. 343 */ 344static inline size_t hbitmap_iter_next_word(HBitmapIter *hbi, unsigned long *p_cur) 345{ 346 unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1]; 347 348 if (cur == 0) { 349 cur = hbitmap_iter_skip_words(hbi); 350 if (cur == 0) { 351 *p_cur = 0; 352 return -1; 353 } 354 } 355 356 /* The next call will resume work from the next word. */ 357 hbi->cur[HBITMAP_LEVELS - 1] = 0; 358 *p_cur = cur; 359 return hbi->pos; 360} 361 362 363#endif 364