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