target-cris/helper.c: Update Coding Style
[qemu/ar7.git] / util / hbitmap.c
blobd93683128bd4f654f098bbebdf499bdb2bdb0edf
1 /*
2 * Hierarchical Bitmap Data Type
4 * Copyright Red Hat, Inc., 2012
6 * Author: Paolo Bonzini <pbonzini@redhat.com>
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.
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"
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.
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).
33 * Given an index in the bitmap, it can be split in group of bits like
34 * this (for the 64-bit case):
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
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.
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.
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).
57 struct HBitmap {
58 /* Number of total bits in the bottom level. */
59 uint64_t size;
61 /* Number of set bits in the bottom level. */
62 uint64_t count;
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:
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
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.
82 int granularity;
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.
89 * Note that all bitmaps have the same number of levels. Even a 1-bit
90 * bitmap will still allocate HBITMAP_LEVELS arrays.
92 unsigned long *levels[HBITMAP_LEVELS];
95 static inline int popcountl(unsigned long l)
97 return BITS_PER_LONG == 32 ? ctpop32(l) : ctpop64(l);
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.
103 unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi)
105 size_t pos = hbi->pos;
106 const HBitmap *hb = hbi->hb;
107 unsigned i = HBITMAP_LEVELS - 1;
109 unsigned long cur;
110 do {
111 cur = hbi->cur[--i];
112 pos >>= BITS_PER_LEVEL;
113 } while (cur == 0);
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.
121 if (i == 0 && cur == (1UL << (BITS_PER_LONG - 1))) {
122 return 0;
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.
129 assert(cur);
130 pos = (pos << BITS_PER_LEVEL) + ctzl(cur);
131 hbi->cur[i] = cur & (cur - 1);
133 /* Set up next level for iteration. */
134 cur = hb->levels[i + 1][pos];
137 hbi->pos = pos;
138 trace_hbitmap_iter_skip_words(hbi->hb, hbi, pos, cur);
140 assert(cur);
141 return cur;
144 void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first)
146 unsigned i, bit;
147 uint64_t pos;
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;
155 for (i = HBITMAP_LEVELS; i-- > 0; ) {
156 bit = pos & (BITS_PER_LONG - 1);
157 pos >>= BITS_PER_LEVEL;
159 /* Drop bits representing items before first. */
160 hbi->cur[i] = hb->levels[i][pos] & ~((1UL << bit) - 1);
162 /* We have already added level i+1, so the lowest set bit has
163 * been processed. Clear it.
165 if (i != HBITMAP_LEVELS - 1) {
166 hbi->cur[i] &= ~(1UL << bit);
171 bool hbitmap_empty(const HBitmap *hb)
173 return hb->count == 0;
176 int hbitmap_granularity(const HBitmap *hb)
178 return hb->granularity;
181 uint64_t hbitmap_count(const HBitmap *hb)
183 return hb->count << hb->granularity;
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.
189 static uint64_t hb_count_between(HBitmap *hb, uint64_t start, uint64_t last)
191 HBitmapIter hbi;
192 uint64_t count = 0;
193 uint64_t end = last + 1;
194 unsigned long cur;
195 size_t pos;
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;
203 count += popcountl(cur);
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);
213 return count;
216 /* Setting starts at the last layer and propagates up if an element
217 * changes from zero to non-zero.
219 static inline bool hb_set_elem(unsigned long *elem, uint64_t start, uint64_t last)
221 unsigned long mask;
222 bool changed;
224 assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL));
225 assert(start <= last);
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;
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)
237 size_t pos = start >> BITS_PER_LEVEL;
238 size_t lastpos = last >> BITS_PER_LEVEL;
239 bool changed = false;
240 size_t i;
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;
252 changed |= (hb->levels[level][i] == 0);
253 hb->levels[level][i] = ~0UL;
256 changed |= hb_set_elem(&hb->levels[level][i], start, last);
258 /* If there was any change in this layer, we may have to update
259 * the one above.
261 if (level > 0 && changed) {
262 hb_set_between(hb, level - 1, pos, lastpos);
266 void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count)
268 /* Compute range in the last layer. */
269 uint64_t last = start + count - 1;
271 trace_hbitmap_set(hb, start, count,
272 start >> hb->granularity, last >> hb->granularity);
274 start >>= hb->granularity;
275 last >>= hb->granularity;
276 count = last - start + 1;
278 hb->count += count - hb_count_between(hb, start, last);
279 hb_set_between(hb, HBITMAP_LEVELS - 1, start, last);
282 /* Resetting works the other way round: propagate up if the new
283 * value is zero.
285 static inline bool hb_reset_elem(unsigned long *elem, uint64_t start, uint64_t last)
287 unsigned long mask;
288 bool blanked;
290 assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL));
291 assert(start <= last);
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;
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)
303 size_t pos = start >> BITS_PER_LEVEL;
304 size_t lastpos = last >> BITS_PER_LEVEL;
305 bool changed = false;
306 size_t i;
308 i = pos;
309 if (i < lastpos) {
310 uint64_t next = (start | (BITS_PER_LONG - 1)) + 1;
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.
317 if (hb_reset_elem(&hb->levels[level][i], start, next - 1)) {
318 changed = true;
319 } else {
320 pos++;
323 for (;;) {
324 start = next;
325 next += BITS_PER_LONG;
326 if (++i == lastpos) {
327 break;
329 changed |= (hb->levels[level][i] != 0);
330 hb->levels[level][i] = 0UL;
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--;
341 if (level > 0 && changed) {
342 hb_reset_between(hb, level - 1, pos, lastpos);
346 void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count)
348 /* Compute range in the last layer. */
349 uint64_t last = start + count - 1;
351 trace_hbitmap_reset(hb, start, count,
352 start >> hb->granularity, last >> hb->granularity);
354 start >>= hb->granularity;
355 last >>= hb->granularity;
357 hb->count -= hb_count_between(hb, start, last);
358 hb_reset_between(hb, HBITMAP_LEVELS - 1, start, last);
361 bool hbitmap_get(const HBitmap *hb, uint64_t item)
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));
367 return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0;
370 void hbitmap_free(HBitmap *hb)
372 unsigned i;
373 for (i = HBITMAP_LEVELS; i-- > 0; ) {
374 g_free(hb->levels[i]);
376 g_free(hb);
379 HBitmap *hbitmap_alloc(uint64_t size, int granularity)
381 HBitmap *hb = g_malloc0(sizeof (struct HBitmap));
382 unsigned i;
384 assert(granularity >= 0 && granularity < 64);
385 size = (size + (1ULL << granularity) - 1) >> granularity;
386 assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
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));
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.
399 assert(size == 1);
400 hb->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);
401 return hb;