root / util / hbitmap.c @ 834574ea
History | View | Annotate | Download (12.5 kB)
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 |
#include <string.h> |
13 |
#include <glib.h> |
14 |
#include <assert.h> |
15 |
#include "qemu/osdep.h" |
16 |
#include "qemu/hbitmap.h" |
17 |
#include "qemu/host-utils.h" |
18 |
#include "trace.h" |
19 |
|
20 |
/* HBitmaps provides an array of bits. The bits are stored as usual in an
|
21 |
* array of unsigned longs, but HBitmap is also optimized to provide fast
|
22 |
* iteration over set bits; going from one bit to the next is O(logB n)
|
23 |
* worst case, with B = sizeof(long) * CHAR_BIT: the result is low enough
|
24 |
* that the number of levels is in fact fixed.
|
25 |
*
|
26 |
* In order to do this, it stacks multiple bitmaps with progressively coarser
|
27 |
* granularity; in all levels except the last, bit N is set iff the N-th
|
28 |
* unsigned long is nonzero in the immediately next level. When iteration
|
29 |
* completes on the last level it can examine the 2nd-last level to quickly
|
30 |
* skip entire words, and even do so recursively to skip blocks of 64 words or
|
31 |
* powers thereof (32 on 32-bit machines).
|
32 |
*
|
33 |
* Given an index in the bitmap, it can be split in group of bits like
|
34 |
* this (for the 64-bit case):
|
35 |
*
|
36 |
* bits 0-57 => word in the last bitmap | bits 58-63 => bit in the word
|
37 |
* bits 0-51 => word in the 2nd-last bitmap | bits 52-57 => bit in the word
|
38 |
* bits 0-45 => word in the 3rd-last bitmap | bits 46-51 => bit in the word
|
39 |
*
|
40 |
* So it is easy to move up simply by shifting the index right by
|
41 |
* log2(BITS_PER_LONG) bits. To move down, you shift the index left
|
42 |
* similarly, and add the word index within the group. Iteration uses
|
43 |
* ffs (find first set bit) to find the next word to examine; this
|
44 |
* operation can be done in constant time in most current architectures.
|
45 |
*
|
46 |
* Setting or clearing a range of m bits on all levels, the work to perform
|
47 |
* is O(m + m/W + m/W^2 + ...), which is O(m) like on a regular bitmap.
|
48 |
*
|
49 |
* When iterating on a bitmap, each bit (on any level) is only visited
|
50 |
* once. Hence, The total cost of visiting a bitmap with m bits in it is
|
51 |
* the number of bits that are set in all bitmaps. Unless the bitmap is
|
52 |
* extremely sparse, this is also O(m + m/W + m/W^2 + ...), so the amortized
|
53 |
* cost of advancing from one bit to the next is usually constant (worst case
|
54 |
* O(logB n) as in the non-amortized complexity).
|
55 |
*/
|
56 |
|
57 |
struct HBitmap {
|
58 |
/* Number of total bits in the bottom level. */
|
59 |
uint64_t size; |
60 |
|
61 |
/* Number of set bits in the bottom level. */
|
62 |
uint64_t count; |
63 |
|
64 |
/* A scaling factor. Given a granularity of G, each bit in the bitmap will
|
65 |
* will actually represent a group of 2^G elements. Each operation on a
|
66 |
* range of bits first rounds the bits to determine which group they land
|
67 |
* in, and then affect the entire page; iteration will only visit the first
|
68 |
* bit of each group. Here is an example of operations in a size-16,
|
69 |
* granularity-1 HBitmap:
|
70 |
*
|
71 |
* initial state 00000000
|
72 |
* set(start=0, count=9) 11111000 (iter: 0, 2, 4, 6, 8)
|
73 |
* reset(start=1, count=3) 00111000 (iter: 4, 6, 8)
|
74 |
* set(start=9, count=2) 00111100 (iter: 4, 6, 8, 10)
|
75 |
* reset(start=5, count=5) 00000000
|
76 |
*
|
77 |
* From an implementation point of view, when setting or resetting bits,
|
78 |
* the bitmap will scale bit numbers right by this amount of bits. When
|
79 |
* iterating, the bitmap will scale bit numbers left by this amount of
|
80 |
* bits.
|
81 |
*/
|
82 |
int granularity;
|
83 |
|
84 |
/* A number of progressively less coarse bitmaps (i.e. level 0 is the
|
85 |
* coarsest). Each bit in level N represents a word in level N+1 that
|
86 |
* has a set bit, except the last level where each bit represents the
|
87 |
* actual bitmap.
|
88 |
*
|
89 |
* Note that all bitmaps have the same number of levels. Even a 1-bit
|
90 |
* bitmap will still allocate HBITMAP_LEVELS arrays.
|
91 |
*/
|
92 |
unsigned long *levels[HBITMAP_LEVELS]; |
93 |
}; |
94 |
|
95 |
static inline int popcountl(unsigned long l) |
96 |
{ |
97 |
return BITS_PER_LONG == 32 ? ctpop32(l) : ctpop64(l); |
98 |
} |
99 |
|
100 |
/* Advance hbi to the next nonzero word and return it. hbi->pos
|
101 |
* is updated. Returns zero if we reach the end of the bitmap.
|
102 |
*/
|
103 |
unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi) |
104 |
{ |
105 |
size_t pos = hbi->pos; |
106 |
const HBitmap *hb = hbi->hb;
|
107 |
unsigned i = HBITMAP_LEVELS - 1; |
108 |
|
109 |
unsigned long cur; |
110 |
do {
|
111 |
cur = hbi->cur[--i]; |
112 |
pos >>= BITS_PER_LEVEL; |
113 |
} while (cur == 0); |
114 |
|
115 |
/* Check for end of iteration. We always use fewer than BITS_PER_LONG
|
116 |
* bits in the level 0 bitmap; thus we can repurpose the most significant
|
117 |
* bit as a sentinel. The sentinel is set in hbitmap_alloc and ensures
|
118 |
* that the above loop ends even without an explicit check on i.
|
119 |
*/
|
120 |
|
121 |
if (i == 0 && cur == (1UL << (BITS_PER_LONG - 1))) { |
122 |
return 0; |
123 |
} |
124 |
for (; i < HBITMAP_LEVELS - 1; i++) { |
125 |
/* Shift back pos to the left, matching the right shifts above.
|
126 |
* The index of this word's least significant set bit provides
|
127 |
* the low-order bits.
|
128 |
*/
|
129 |
assert(cur); |
130 |
pos = (pos << BITS_PER_LEVEL) + ctzl(cur); |
131 |
hbi->cur[i] = cur & (cur - 1);
|
132 |
|
133 |
/* Set up next level for iteration. */
|
134 |
cur = hb->levels[i + 1][pos];
|
135 |
} |
136 |
|
137 |
hbi->pos = pos; |
138 |
trace_hbitmap_iter_skip_words(hbi->hb, hbi, pos, cur); |
139 |
|
140 |
assert(cur); |
141 |
return cur;
|
142 |
} |
143 |
|
144 |
void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first) |
145 |
{ |
146 |
unsigned i, bit;
|
147 |
uint64_t pos; |
148 |
|
149 |
hbi->hb = hb; |
150 |
pos = first >> hb->granularity; |
151 |
assert(pos < hb->size); |
152 |
hbi->pos = pos >> BITS_PER_LEVEL; |
153 |
hbi->granularity = hb->granularity; |
154 |
|
155 |
for (i = HBITMAP_LEVELS; i-- > 0; ) { |
156 |
bit = pos & (BITS_PER_LONG - 1);
|
157 |
pos >>= BITS_PER_LEVEL; |
158 |
|
159 |
/* Drop bits representing items before first. */
|
160 |
hbi->cur[i] = hb->levels[i][pos] & ~((1UL << bit) - 1); |
161 |
|
162 |
/* We have already added level i+1, so the lowest set bit has
|
163 |
* been processed. Clear it.
|
164 |
*/
|
165 |
if (i != HBITMAP_LEVELS - 1) { |
166 |
hbi->cur[i] &= ~(1UL << bit);
|
167 |
} |
168 |
} |
169 |
} |
170 |
|
171 |
bool hbitmap_empty(const HBitmap *hb) |
172 |
{ |
173 |
return hb->count == 0; |
174 |
} |
175 |
|
176 |
int hbitmap_granularity(const HBitmap *hb) |
177 |
{ |
178 |
return hb->granularity;
|
179 |
} |
180 |
|
181 |
uint64_t hbitmap_count(const HBitmap *hb)
|
182 |
{ |
183 |
return hb->count << hb->granularity;
|
184 |
} |
185 |
|
186 |
/* Count the number of set bits between start and end, not accounting for
|
187 |
* the granularity. Also an example of how to use hbitmap_iter_next_word.
|
188 |
*/
|
189 |
static uint64_t hb_count_between(HBitmap *hb, uint64_t start, uint64_t last)
|
190 |
{ |
191 |
HBitmapIter hbi; |
192 |
uint64_t count = 0;
|
193 |
uint64_t end = last + 1;
|
194 |
unsigned long cur; |
195 |
size_t pos; |
196 |
|
197 |
hbitmap_iter_init(&hbi, hb, start << hb->granularity); |
198 |
for (;;) {
|
199 |
pos = hbitmap_iter_next_word(&hbi, &cur); |
200 |
if (pos >= (end >> BITS_PER_LEVEL)) {
|
201 |
break;
|
202 |
} |
203 |
count += popcountl(cur); |
204 |
} |
205 |
|
206 |
if (pos == (end >> BITS_PER_LEVEL)) {
|
207 |
/* Drop bits representing the END-th and subsequent items. */
|
208 |
int bit = end & (BITS_PER_LONG - 1); |
209 |
cur &= (1UL << bit) - 1; |
210 |
count += popcountl(cur); |
211 |
} |
212 |
|
213 |
return count;
|
214 |
} |
215 |
|
216 |
/* Setting starts at the last layer and propagates up if an element
|
217 |
* changes from zero to non-zero.
|
218 |
*/
|
219 |
static inline bool hb_set_elem(unsigned long *elem, uint64_t start, uint64_t last) |
220 |
{ |
221 |
unsigned long mask; |
222 |
bool changed;
|
223 |
|
224 |
assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL)); |
225 |
assert(start <= last); |
226 |
|
227 |
mask = 2UL << (last & (BITS_PER_LONG - 1)); |
228 |
mask -= 1UL << (start & (BITS_PER_LONG - 1)); |
229 |
changed = (*elem == 0);
|
230 |
*elem |= mask; |
231 |
return changed;
|
232 |
} |
233 |
|
234 |
/* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)... */
|
235 |
static void hb_set_between(HBitmap *hb, int level, uint64_t start, uint64_t last) |
236 |
{ |
237 |
size_t pos = start >> BITS_PER_LEVEL; |
238 |
size_t lastpos = last >> BITS_PER_LEVEL; |
239 |
bool changed = false; |
240 |
size_t i; |
241 |
|
242 |
i = pos; |
243 |
if (i < lastpos) {
|
244 |
uint64_t next = (start | (BITS_PER_LONG - 1)) + 1; |
245 |
changed |= hb_set_elem(&hb->levels[level][i], start, next - 1);
|
246 |
for (;;) {
|
247 |
start = next; |
248 |
next += BITS_PER_LONG; |
249 |
if (++i == lastpos) {
|
250 |
break;
|
251 |
} |
252 |
changed |= (hb->levels[level][i] == 0);
|
253 |
hb->levels[level][i] = ~0UL;
|
254 |
} |
255 |
} |
256 |
changed |= hb_set_elem(&hb->levels[level][i], start, last); |
257 |
|
258 |
/* If there was any change in this layer, we may have to update
|
259 |
* the one above.
|
260 |
*/
|
261 |
if (level > 0 && changed) { |
262 |
hb_set_between(hb, level - 1, pos, lastpos);
|
263 |
} |
264 |
} |
265 |
|
266 |
void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count)
|
267 |
{ |
268 |
/* Compute range in the last layer. */
|
269 |
uint64_t last = start + count - 1;
|
270 |
|
271 |
trace_hbitmap_set(hb, start, count, |
272 |
start >> hb->granularity, last >> hb->granularity); |
273 |
|
274 |
start >>= hb->granularity; |
275 |
last >>= hb->granularity; |
276 |
count = last - start + 1;
|
277 |
|
278 |
hb->count += count - hb_count_between(hb, start, last); |
279 |
hb_set_between(hb, HBITMAP_LEVELS - 1, start, last);
|
280 |
} |
281 |
|
282 |
/* Resetting works the other way round: propagate up if the new
|
283 |
* value is zero.
|
284 |
*/
|
285 |
static inline bool hb_reset_elem(unsigned long *elem, uint64_t start, uint64_t last) |
286 |
{ |
287 |
unsigned long mask; |
288 |
bool blanked;
|
289 |
|
290 |
assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL)); |
291 |
assert(start <= last); |
292 |
|
293 |
mask = 2UL << (last & (BITS_PER_LONG - 1)); |
294 |
mask -= 1UL << (start & (BITS_PER_LONG - 1)); |
295 |
blanked = *elem != 0 && ((*elem & ~mask) == 0); |
296 |
*elem &= ~mask; |
297 |
return blanked;
|
298 |
} |
299 |
|
300 |
/* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)... */
|
301 |
static void hb_reset_between(HBitmap *hb, int level, uint64_t start, uint64_t last) |
302 |
{ |
303 |
size_t pos = start >> BITS_PER_LEVEL; |
304 |
size_t lastpos = last >> BITS_PER_LEVEL; |
305 |
bool changed = false; |
306 |
size_t i; |
307 |
|
308 |
i = pos; |
309 |
if (i < lastpos) {
|
310 |
uint64_t next = (start | (BITS_PER_LONG - 1)) + 1; |
311 |
|
312 |
/* Here we need a more complex test than when setting bits. Even if
|
313 |
* something was changed, we must not blank bits in the upper level
|
314 |
* unless the lower-level word became entirely zero. So, remove pos
|
315 |
* from the upper-level range if bits remain set.
|
316 |
*/
|
317 |
if (hb_reset_elem(&hb->levels[level][i], start, next - 1)) { |
318 |
changed = true;
|
319 |
} else {
|
320 |
pos++; |
321 |
} |
322 |
|
323 |
for (;;) {
|
324 |
start = next; |
325 |
next += BITS_PER_LONG; |
326 |
if (++i == lastpos) {
|
327 |
break;
|
328 |
} |
329 |
changed |= (hb->levels[level][i] != 0);
|
330 |
hb->levels[level][i] = 0UL;
|
331 |
} |
332 |
} |
333 |
|
334 |
/* Same as above, this time for lastpos. */
|
335 |
if (hb_reset_elem(&hb->levels[level][i], start, last)) {
|
336 |
changed = true;
|
337 |
} else {
|
338 |
lastpos--; |
339 |
} |
340 |
|
341 |
if (level > 0 && changed) { |
342 |
hb_reset_between(hb, level - 1, pos, lastpos);
|
343 |
} |
344 |
} |
345 |
|
346 |
void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count)
|
347 |
{ |
348 |
/* Compute range in the last layer. */
|
349 |
uint64_t last = start + count - 1;
|
350 |
|
351 |
trace_hbitmap_reset(hb, start, count, |
352 |
start >> hb->granularity, last >> hb->granularity); |
353 |
|
354 |
start >>= hb->granularity; |
355 |
last >>= hb->granularity; |
356 |
|
357 |
hb->count -= hb_count_between(hb, start, last); |
358 |
hb_reset_between(hb, HBITMAP_LEVELS - 1, start, last);
|
359 |
} |
360 |
|
361 |
bool hbitmap_get(const HBitmap *hb, uint64_t item) |
362 |
{ |
363 |
/* Compute position and bit in the last layer. */
|
364 |
uint64_t pos = item >> hb->granularity; |
365 |
unsigned long bit = 1UL << (pos & (BITS_PER_LONG - 1)); |
366 |
|
367 |
return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0; |
368 |
} |
369 |
|
370 |
void hbitmap_free(HBitmap *hb)
|
371 |
{ |
372 |
unsigned i;
|
373 |
for (i = HBITMAP_LEVELS; i-- > 0; ) { |
374 |
g_free(hb->levels[i]); |
375 |
} |
376 |
g_free(hb); |
377 |
} |
378 |
|
379 |
HBitmap *hbitmap_alloc(uint64_t size, int granularity)
|
380 |
{ |
381 |
HBitmap *hb = g_malloc0(sizeof (struct HBitmap)); |
382 |
unsigned i;
|
383 |
|
384 |
assert(granularity >= 0 && granularity < 64); |
385 |
size = (size + (1ULL << granularity) - 1) >> granularity; |
386 |
assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
|
387 |
|
388 |
hb->size = size; |
389 |
hb->granularity = granularity; |
390 |
for (i = HBITMAP_LEVELS; i-- > 0; ) { |
391 |
size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1); |
392 |
hb->levels[i] = g_malloc0(size * sizeof(unsigned long)); |
393 |
} |
394 |
|
395 |
/* We necessarily have free bits in level 0 due to the definition
|
396 |
* of HBITMAP_LEVELS, so use one for a sentinel. This speeds up
|
397 |
* hbitmap_iter_skip_words.
|
398 |
*/
|
399 |
assert(size == 1);
|
400 |
hb->levels[0][0] |= 1UL << (BITS_PER_LONG - 1); |
401 |
return hb;
|
402 |
} |