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 * bdrv_dirty_bitmap_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 354