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