numa: add -numa node,memdev= option
[qemu.git] / include / qemu / hbitmap.h
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 1
14
15 #include <limits.h>
16 #include <stdint.h>
17 #include <stdbool.h>
18 #include "bitops.h"
19 #include "host-utils.h"
20
21 typedef struct HBitmap HBitmap;
22 typedef struct HBitmapIter HBitmapIter;
23
24 #define BITS_PER_LEVEL (BITS_PER_LONG == 32 ? 5 : 6)
25
26 /* For 32-bit, the largest that fits in a 4 GiB address space.
27 * For 64-bit, the number of sectors in 1 PiB. Good luck, in
28 * either case... :)
29 */
30 #define HBITMAP_LOG_MAX_SIZE (BITS_PER_LONG == 32 ? 34 : 41)
31
32 /* We need to place a sentinel in level 0 to speed up iteration. Thus,
33 * we do this instead of HBITMAP_LOG_MAX_SIZE / BITS_PER_LEVEL. The
34 * difference is that it allocates an extra level when HBITMAP_LOG_MAX_SIZE
35 * is an exact multiple of BITS_PER_LEVEL.
36 */
37 #define HBITMAP_LEVELS ((HBITMAP_LOG_MAX_SIZE / BITS_PER_LEVEL) + 1)
38
39 struct HBitmapIter {
40 const HBitmap *hb;
41
42 /* Copied from hb for access in the inline functions (hb is opaque). */
43 int granularity;
44
45 /* Entry offset into the last-level array of longs. */
46 size_t pos;
47
48 /* The currently-active path in the tree. Each item of cur[i] stores
49 * the bits (i.e. the subtrees) yet to be processed under that node.
50 */
51 unsigned long cur[HBITMAP_LEVELS];
52 };
53
54 /**
55 * hbitmap_alloc:
56 * @size: Number of bits in the bitmap.
57 * @granularity: Granularity of the bitmap. Aligned groups of 2^@granularity
58 * bits will be represented by a single bit. Each operation on a
59 * range of bits first rounds the bits to determine which group they land
60 * in, and then affect the entire set; iteration will only visit the first
61 * bit of each group.
62 *
63 * Allocate a new HBitmap.
64 */
65 HBitmap *hbitmap_alloc(uint64_t size, int granularity);
66
67 /**
68 * hbitmap_empty:
69 * @hb: HBitmap to operate on.
70 *
71 * Return whether the bitmap is empty.
72 */
73 bool hbitmap_empty(const HBitmap *hb);
74
75 /**
76 * hbitmap_granularity:
77 * @hb: HBitmap to operate on.
78 *
79 * Return the granularity of the HBitmap.
80 */
81 int hbitmap_granularity(const HBitmap *hb);
82
83 /**
84 * hbitmap_count:
85 * @hb: HBitmap to operate on.
86 *
87 * Return the number of bits set in the HBitmap.
88 */
89 uint64_t hbitmap_count(const HBitmap *hb);
90
91 /**
92 * hbitmap_set:
93 * @hb: HBitmap to operate on.
94 * @start: First bit to set (0-based).
95 * @count: Number of bits to set.
96 *
97 * Set a consecutive range of bits in an HBitmap.
98 */
99 void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count);
100
101 /**
102 * hbitmap_reset:
103 * @hb: HBitmap to operate on.
104 * @start: First bit to reset (0-based).
105 * @count: Number of bits to reset.
106 *
107 * Reset a consecutive range of bits in an HBitmap.
108 */
109 void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count);
110
111 /**
112 * hbitmap_get:
113 * @hb: HBitmap to operate on.
114 * @item: Bit to query (0-based).
115 *
116 * Return whether the @item-th bit in an HBitmap is set.
117 */
118 bool hbitmap_get(const HBitmap *hb, uint64_t item);
119
120 /**
121 * hbitmap_free:
122 * @hb: HBitmap to operate on.
123 *
124 * Free an HBitmap and all of its associated memory.
125 */
126 void hbitmap_free(HBitmap *hb);
127
128 /**
129 * hbitmap_iter_init:
130 * @hbi: HBitmapIter to initialize.
131 * @hb: HBitmap to iterate on.
132 * @first: First bit to visit (0-based, must be strictly less than the
133 * size of the bitmap).
134 *
135 * Set up @hbi to iterate on the HBitmap @hb. hbitmap_iter_next will return
136 * the lowest-numbered bit that is set in @hb, starting at @first.
137 *
138 * Concurrent setting of bits is acceptable, and will at worst cause the
139 * iteration to miss some of those bits. Resetting bits before the current
140 * position of the iterator is also okay. However, concurrent resetting of
141 * bits can lead to unexpected behavior if the iterator has not yet reached
142 * those bits.
143 */
144 void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first);
145
146 /* hbitmap_iter_skip_words:
147 * @hbi: HBitmapIter to operate on.
148 *
149 * Internal function used by hbitmap_iter_next and hbitmap_iter_next_word.
150 */
151 unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
152
153 /**
154 * hbitmap_iter_next:
155 * @hbi: HBitmapIter to operate on.
156 *
157 * Return the next bit that is set in @hbi's associated HBitmap,
158 * or -1 if all remaining bits are zero.
159 */
160 static inline int64_t hbitmap_iter_next(HBitmapIter *hbi)
161 {
162 unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1];
163 int64_t item;
164
165 if (cur == 0) {
166 cur = hbitmap_iter_skip_words(hbi);
167 if (cur == 0) {
168 return -1;
169 }
170 }
171
172 /* The next call will resume work from the next bit. */
173 hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1);
174 item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + ctzl(cur);
175
176 return item << hbi->granularity;
177 }
178
179 /**
180 * hbitmap_iter_next_word:
181 * @hbi: HBitmapIter to operate on.
182 * @p_cur: Location where to store the next non-zero word.
183 *
184 * Return the index of the next nonzero word that is set in @hbi's
185 * associated HBitmap, and set *p_cur to the content of that word
186 * (bits before the index that was passed to hbitmap_iter_init are
187 * trimmed on the first call). Return -1, and set *p_cur to zero,
188 * if all remaining words are zero.
189 */
190 static inline size_t hbitmap_iter_next_word(HBitmapIter *hbi, unsigned long *p_cur)
191 {
192 unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1];
193
194 if (cur == 0) {
195 cur = hbitmap_iter_skip_words(hbi);
196 if (cur == 0) {
197 *p_cur = 0;
198 return -1;
199 }
200 }
201
202 /* The next call will resume work from the next word. */
203 hbi->cur[HBITMAP_LEVELS - 1] = 0;
204 *p_cur = cur;
205 return hbi->pos;
206 }
207
208
209 #endif