]>
Commit | Line | Data |
---|---|---|
e7c033c3 PB |
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 | |
175de524 | 13 | #define HBITMAP_H |
e7c033c3 | 14 | |
e7c033c3 | 15 | #include "bitops.h" |
18331e7c | 16 | #include "host-utils.h" |
e7c033c3 PB |
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 | ||
ce1ffea8 JS |
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 | ||
be58721d JS |
74 | /** |
75 | * hbitmap_merge: | |
be58721d | 76 | * |
fa000f2f VSO |
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 | * | |
be58721d | 91 | */ |
fa000f2f | 92 | bool hbitmap_can_merge(const HBitmap *a, const HBitmap *b); |
be58721d | 93 | |
e7c033c3 PB |
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 | ||
c6a8c328 WC |
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 | ||
e7c033c3 PB |
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 | ||
20a579de HR |
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 | ||
8258888e | 168 | /** |
ecbfa281 | 169 | * hbitmap_serialization_align: |
8258888e VSO |
170 | * @hb: HBitmap to operate on. |
171 | * | |
ecbfa281 EB |
172 | * Required alignment of serialization chunks, used by other serialization |
173 | * functions. For every chunk: | |
8258888e VSO |
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 | */ | |
ecbfa281 | 178 | uint64_t hbitmap_serialization_align(const HBitmap *hb); |
8258888e VSO |
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 | ||
6bdc8b71 VSO |
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 | ||
8258888e VSO |
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 | ||
a3b52535 VSO |
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 | ||
e7c033c3 PB |
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. | |
1b095244 PB |
282 | * @first: First bit to visit (0-based, must be strictly less than the |
283 | * size of the bitmap). | |
e7c033c3 PB |
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 | |
f63ea4e9 VSO |
289 | * iteration to miss some of those bits. |
290 | * | |
291 | * The concurrent resetting of bits is OK. | |
e7c033c3 PB |
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 | ||
56207df5 | 302 | /* hbitmap_next_zero: |
76d570dc VSO |
303 | * |
304 | * Find next not dirty bit within selected range. If not found, return -1. | |
305 | * | |
56207df5 VSO |
306 | * @hb: The HBitmap to operate on |
307 | * @start: The bit to start from. | |
76d570dc VSO |
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. | |
56207df5 | 311 | */ |
76d570dc | 312 | int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t count); |
56207df5 | 313 | |
a78a1a48 VSO |
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 | ||
07ac4cdb FZ |
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 | ||
e7c033c3 PB |
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 | */ | |
19c021e1 | 358 | int64_t hbitmap_iter_next(HBitmapIter *hbi); |
e7c033c3 PB |
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 |