root / tests / test-hbitmap.c @ f8ce0403
History | View | Annotate | Download (12.6 kB)
1 |
/*
|
---|---|
2 |
* Hierarchical bitmap unit-tests.
|
3 |
*
|
4 |
* Copyright (C) 2012 Red Hat Inc.
|
5 |
*
|
6 |
* Author: Paolo Bonzini <pbonzini@redhat.com>
|
7 |
*
|
8 |
* This work is licensed under the terms of the GNU GPL, version 2 or later.
|
9 |
* See the COPYING file in the top-level directory.
|
10 |
*/
|
11 |
|
12 |
#include <glib.h> |
13 |
#include <stdarg.h> |
14 |
#include "qemu/hbitmap.h" |
15 |
|
16 |
#define LOG_BITS_PER_LONG (BITS_PER_LONG == 32 ? 5 : 6) |
17 |
|
18 |
#define L1 BITS_PER_LONG
|
19 |
#define L2 (BITS_PER_LONG * L1)
|
20 |
#define L3 (BITS_PER_LONG * L2)
|
21 |
|
22 |
typedef struct TestHBitmapData { |
23 |
HBitmap *hb; |
24 |
unsigned long *bits; |
25 |
size_t size; |
26 |
int granularity;
|
27 |
} TestHBitmapData; |
28 |
|
29 |
|
30 |
/* Check that the HBitmap and the shadow bitmap contain the same data,
|
31 |
* ignoring the same "first" bits.
|
32 |
*/
|
33 |
static void hbitmap_test_check(TestHBitmapData *data, |
34 |
uint64_t first) |
35 |
{ |
36 |
uint64_t count = 0;
|
37 |
size_t pos; |
38 |
int bit;
|
39 |
HBitmapIter hbi; |
40 |
int64_t i, next; |
41 |
|
42 |
hbitmap_iter_init(&hbi, data->hb, first); |
43 |
|
44 |
i = first; |
45 |
for (;;) {
|
46 |
next = hbitmap_iter_next(&hbi); |
47 |
if (next < 0) { |
48 |
next = data->size; |
49 |
} |
50 |
|
51 |
while (i < next) {
|
52 |
pos = i >> LOG_BITS_PER_LONG; |
53 |
bit = i & (BITS_PER_LONG - 1);
|
54 |
i++; |
55 |
g_assert_cmpint(data->bits[pos] & (1UL << bit), ==, 0); |
56 |
} |
57 |
|
58 |
if (next == data->size) {
|
59 |
break;
|
60 |
} |
61 |
|
62 |
pos = i >> LOG_BITS_PER_LONG; |
63 |
bit = i & (BITS_PER_LONG - 1);
|
64 |
i++; |
65 |
count++; |
66 |
g_assert_cmpint(data->bits[pos] & (1UL << bit), !=, 0); |
67 |
} |
68 |
|
69 |
if (first == 0) { |
70 |
g_assert_cmpint(count << data->granularity, ==, hbitmap_count(data->hb)); |
71 |
} |
72 |
} |
73 |
|
74 |
/* This is provided instead of a test setup function so that the sizes
|
75 |
are kept in the test functions (and not in main()) */
|
76 |
static void hbitmap_test_init(TestHBitmapData *data, |
77 |
uint64_t size, int granularity)
|
78 |
{ |
79 |
size_t n; |
80 |
data->hb = hbitmap_alloc(size, granularity); |
81 |
|
82 |
n = (size + BITS_PER_LONG - 1) / BITS_PER_LONG;
|
83 |
if (n == 0) { |
84 |
n = 1;
|
85 |
} |
86 |
data->bits = g_new0(unsigned long, n); |
87 |
data->size = size; |
88 |
data->granularity = granularity; |
89 |
if (size) {
|
90 |
hbitmap_test_check(data, 0);
|
91 |
} |
92 |
} |
93 |
|
94 |
static void hbitmap_test_teardown(TestHBitmapData *data, |
95 |
const void *unused) |
96 |
{ |
97 |
if (data->hb) {
|
98 |
hbitmap_free(data->hb); |
99 |
data->hb = NULL;
|
100 |
} |
101 |
if (data->bits) {
|
102 |
g_free(data->bits); |
103 |
data->bits = NULL;
|
104 |
} |
105 |
} |
106 |
|
107 |
/* Set a range in the HBitmap and in the shadow "simple" bitmap.
|
108 |
* The two bitmaps are then tested against each other.
|
109 |
*/
|
110 |
static void hbitmap_test_set(TestHBitmapData *data, |
111 |
uint64_t first, uint64_t count) |
112 |
{ |
113 |
hbitmap_set(data->hb, first, count); |
114 |
while (count-- != 0) { |
115 |
size_t pos = first >> LOG_BITS_PER_LONG; |
116 |
int bit = first & (BITS_PER_LONG - 1); |
117 |
first++; |
118 |
|
119 |
data->bits[pos] |= 1UL << bit;
|
120 |
} |
121 |
|
122 |
if (data->granularity == 0) { |
123 |
hbitmap_test_check(data, 0);
|
124 |
} |
125 |
} |
126 |
|
127 |
/* Reset a range in the HBitmap and in the shadow "simple" bitmap.
|
128 |
*/
|
129 |
static void hbitmap_test_reset(TestHBitmapData *data, |
130 |
uint64_t first, uint64_t count) |
131 |
{ |
132 |
hbitmap_reset(data->hb, first, count); |
133 |
while (count-- != 0) { |
134 |
size_t pos = first >> LOG_BITS_PER_LONG; |
135 |
int bit = first & (BITS_PER_LONG - 1); |
136 |
first++; |
137 |
|
138 |
data->bits[pos] &= ~(1UL << bit);
|
139 |
} |
140 |
|
141 |
if (data->granularity == 0) { |
142 |
hbitmap_test_check(data, 0);
|
143 |
} |
144 |
} |
145 |
|
146 |
static void hbitmap_test_check_get(TestHBitmapData *data) |
147 |
{ |
148 |
uint64_t count = 0;
|
149 |
uint64_t i; |
150 |
|
151 |
for (i = 0; i < data->size; i++) { |
152 |
size_t pos = i >> LOG_BITS_PER_LONG; |
153 |
int bit = i & (BITS_PER_LONG - 1); |
154 |
unsigned long val = data->bits[pos] & (1UL << bit); |
155 |
count += hbitmap_get(data->hb, i); |
156 |
g_assert_cmpint(hbitmap_get(data->hb, i), ==, val != 0);
|
157 |
} |
158 |
g_assert_cmpint(count, ==, hbitmap_count(data->hb)); |
159 |
} |
160 |
|
161 |
static void test_hbitmap_zero(TestHBitmapData *data, |
162 |
const void *unused) |
163 |
{ |
164 |
hbitmap_test_init(data, 0, 0); |
165 |
} |
166 |
|
167 |
static void test_hbitmap_unaligned(TestHBitmapData *data, |
168 |
const void *unused) |
169 |
{ |
170 |
hbitmap_test_init(data, L3 + 23, 0); |
171 |
hbitmap_test_set(data, 0, 1); |
172 |
hbitmap_test_set(data, L3 + 22, 1); |
173 |
} |
174 |
|
175 |
static void test_hbitmap_iter_empty(TestHBitmapData *data, |
176 |
const void *unused) |
177 |
{ |
178 |
hbitmap_test_init(data, L1, 0);
|
179 |
} |
180 |
|
181 |
static void test_hbitmap_iter_partial(TestHBitmapData *data, |
182 |
const void *unused) |
183 |
{ |
184 |
hbitmap_test_init(data, L3, 0);
|
185 |
hbitmap_test_set(data, 0, L3);
|
186 |
hbitmap_test_check(data, 1);
|
187 |
hbitmap_test_check(data, L1 - 1);
|
188 |
hbitmap_test_check(data, L1); |
189 |
hbitmap_test_check(data, L1 * 2 - 1); |
190 |
hbitmap_test_check(data, L2 - 1);
|
191 |
hbitmap_test_check(data, L2); |
192 |
hbitmap_test_check(data, L2 + 1);
|
193 |
hbitmap_test_check(data, L2 + L1); |
194 |
hbitmap_test_check(data, L2 + L1 * 2 - 1); |
195 |
hbitmap_test_check(data, L2 * 2 - 1); |
196 |
hbitmap_test_check(data, L2 * 2);
|
197 |
hbitmap_test_check(data, L2 * 2 + 1); |
198 |
hbitmap_test_check(data, L2 * 2 + L1);
|
199 |
hbitmap_test_check(data, L2 * 2 + L1 * 2 - 1); |
200 |
hbitmap_test_check(data, L3 / 2);
|
201 |
} |
202 |
|
203 |
static void test_hbitmap_set_all(TestHBitmapData *data, |
204 |
const void *unused) |
205 |
{ |
206 |
hbitmap_test_init(data, L3, 0);
|
207 |
hbitmap_test_set(data, 0, L3);
|
208 |
} |
209 |
|
210 |
static void test_hbitmap_get_all(TestHBitmapData *data, |
211 |
const void *unused) |
212 |
{ |
213 |
hbitmap_test_init(data, L3, 0);
|
214 |
hbitmap_test_set(data, 0, L3);
|
215 |
hbitmap_test_check_get(data); |
216 |
} |
217 |
|
218 |
static void test_hbitmap_get_some(TestHBitmapData *data, |
219 |
const void *unused) |
220 |
{ |
221 |
hbitmap_test_init(data, 2 * L2, 0); |
222 |
hbitmap_test_set(data, 10, 1); |
223 |
hbitmap_test_check_get(data); |
224 |
hbitmap_test_set(data, L1 - 1, 1); |
225 |
hbitmap_test_check_get(data); |
226 |
hbitmap_test_set(data, L1, 1);
|
227 |
hbitmap_test_check_get(data); |
228 |
hbitmap_test_set(data, L2 - 1, 1); |
229 |
hbitmap_test_check_get(data); |
230 |
hbitmap_test_set(data, L2, 1);
|
231 |
hbitmap_test_check_get(data); |
232 |
} |
233 |
|
234 |
static void test_hbitmap_set_one(TestHBitmapData *data, |
235 |
const void *unused) |
236 |
{ |
237 |
hbitmap_test_init(data, 2 * L2, 0); |
238 |
hbitmap_test_set(data, 10, 1); |
239 |
hbitmap_test_set(data, L1 - 1, 1); |
240 |
hbitmap_test_set(data, L1, 1);
|
241 |
hbitmap_test_set(data, L2 - 1, 1); |
242 |
hbitmap_test_set(data, L2, 1);
|
243 |
} |
244 |
|
245 |
static void test_hbitmap_set_two_elem(TestHBitmapData *data, |
246 |
const void *unused) |
247 |
{ |
248 |
hbitmap_test_init(data, 2 * L2, 0); |
249 |
hbitmap_test_set(data, L1 - 1, 2); |
250 |
hbitmap_test_set(data, L1 * 2 - 1, 4); |
251 |
hbitmap_test_set(data, L1 * 4, L1 + 1); |
252 |
hbitmap_test_set(data, L1 * 8 - 1, L1 + 1); |
253 |
hbitmap_test_set(data, L2 - 1, 2); |
254 |
hbitmap_test_set(data, L2 + L1 - 1, 8); |
255 |
hbitmap_test_set(data, L2 + L1 * 4, L1 + 1); |
256 |
hbitmap_test_set(data, L2 + L1 * 8 - 1, L1 + 1); |
257 |
} |
258 |
|
259 |
static void test_hbitmap_set(TestHBitmapData *data, |
260 |
const void *unused) |
261 |
{ |
262 |
hbitmap_test_init(data, L3 * 2, 0); |
263 |
hbitmap_test_set(data, L1 - 1, L1 + 2); |
264 |
hbitmap_test_set(data, L1 * 3 - 1, L1 + 2); |
265 |
hbitmap_test_set(data, L1 * 5, L1 * 2 + 1); |
266 |
hbitmap_test_set(data, L1 * 8 - 1, L1 * 2 + 1); |
267 |
hbitmap_test_set(data, L2 - 1, L1 + 2); |
268 |
hbitmap_test_set(data, L2 + L1 * 2 - 1, L1 + 2); |
269 |
hbitmap_test_set(data, L2 + L1 * 4, L1 * 2 + 1); |
270 |
hbitmap_test_set(data, L2 + L1 * 7 - 1, L1 * 2 + 1); |
271 |
hbitmap_test_set(data, L2 * 2 - 1, L3 * 2 - L2 * 2); |
272 |
} |
273 |
|
274 |
static void test_hbitmap_set_twice(TestHBitmapData *data, |
275 |
const void *unused) |
276 |
{ |
277 |
hbitmap_test_init(data, L1 * 3, 0); |
278 |
hbitmap_test_set(data, 0, L1 * 3); |
279 |
hbitmap_test_set(data, L1, 1);
|
280 |
} |
281 |
|
282 |
static void test_hbitmap_set_overlap(TestHBitmapData *data, |
283 |
const void *unused) |
284 |
{ |
285 |
hbitmap_test_init(data, L3 * 2, 0); |
286 |
hbitmap_test_set(data, L1 - 1, L1 + 2); |
287 |
hbitmap_test_set(data, L1 * 2 - 1, L1 * 2 + 2); |
288 |
hbitmap_test_set(data, 0, L1 * 3); |
289 |
hbitmap_test_set(data, L1 * 8 - 1, L2); |
290 |
hbitmap_test_set(data, L2, L1); |
291 |
hbitmap_test_set(data, L2 - L1 - 1, L1 * 8 + 2); |
292 |
hbitmap_test_set(data, L2, L3 - L2 + 1);
|
293 |
hbitmap_test_set(data, L3 - L1, L1 * 3);
|
294 |
hbitmap_test_set(data, L3 - 1, 3); |
295 |
hbitmap_test_set(data, L3 - 1, L2);
|
296 |
} |
297 |
|
298 |
static void test_hbitmap_reset_empty(TestHBitmapData *data, |
299 |
const void *unused) |
300 |
{ |
301 |
hbitmap_test_init(data, L3, 0);
|
302 |
hbitmap_test_reset(data, 0, L3);
|
303 |
} |
304 |
|
305 |
static void test_hbitmap_reset(TestHBitmapData *data, |
306 |
const void *unused) |
307 |
{ |
308 |
hbitmap_test_init(data, L3 * 2, 0); |
309 |
hbitmap_test_set(data, L1 - 1, L1 + 2); |
310 |
hbitmap_test_reset(data, L1 * 2 - 1, L1 * 2 + 2); |
311 |
hbitmap_test_set(data, 0, L1 * 3); |
312 |
hbitmap_test_reset(data, L1 * 8 - 1, L2); |
313 |
hbitmap_test_set(data, L2, L1); |
314 |
hbitmap_test_reset(data, L2 - L1 - 1, L1 * 8 + 2); |
315 |
hbitmap_test_set(data, L2, L3 - L2 + 1);
|
316 |
hbitmap_test_reset(data, L3 - L1, L1 * 3);
|
317 |
hbitmap_test_set(data, L3 - 1, 3); |
318 |
hbitmap_test_reset(data, L3 - 1, L2);
|
319 |
hbitmap_test_set(data, 0, L3 * 2); |
320 |
hbitmap_test_reset(data, 0, L1);
|
321 |
hbitmap_test_reset(data, 0, L2);
|
322 |
hbitmap_test_reset(data, L3, L3); |
323 |
hbitmap_test_set(data, L3 / 2, L3);
|
324 |
} |
325 |
|
326 |
static void test_hbitmap_granularity(TestHBitmapData *data, |
327 |
const void *unused) |
328 |
{ |
329 |
/* Note that hbitmap_test_check has to be invoked manually in this test. */
|
330 |
hbitmap_test_init(data, L1, 1);
|
331 |
hbitmap_test_set(data, 0, 1); |
332 |
g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
|
333 |
hbitmap_test_check(data, 0);
|
334 |
hbitmap_test_set(data, 2, 1); |
335 |
g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
|
336 |
hbitmap_test_check(data, 0);
|
337 |
hbitmap_test_set(data, 0, 3); |
338 |
g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
|
339 |
hbitmap_test_reset(data, 0, 1); |
340 |
g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
|
341 |
} |
342 |
|
343 |
static void test_hbitmap_iter_granularity(TestHBitmapData *data, |
344 |
const void *unused) |
345 |
{ |
346 |
HBitmapIter hbi; |
347 |
|
348 |
/* Note that hbitmap_test_check has to be invoked manually in this test. */
|
349 |
hbitmap_test_init(data, 131072 << 7, 7); |
350 |
hbitmap_iter_init(&hbi, data->hb, 0);
|
351 |
g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
|
352 |
|
353 |
hbitmap_test_set(data, ((L2 + L1 + 1) << 7) + 8, 8); |
354 |
hbitmap_iter_init(&hbi, data->hb, 0);
|
355 |
g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7); |
356 |
g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
|
357 |
|
358 |
hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7); |
359 |
g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
|
360 |
|
361 |
hbitmap_test_set(data, (131072 << 7) - 8, 8); |
362 |
hbitmap_iter_init(&hbi, data->hb, 0);
|
363 |
g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7); |
364 |
g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7); |
365 |
g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
|
366 |
|
367 |
hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7); |
368 |
g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7); |
369 |
g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
|
370 |
} |
371 |
|
372 |
static void hbitmap_test_add(const char *testpath, |
373 |
void (*test_func)(TestHBitmapData *data, const void *user_data)) |
374 |
{ |
375 |
g_test_add(testpath, TestHBitmapData, NULL, NULL, test_func, |
376 |
hbitmap_test_teardown); |
377 |
} |
378 |
|
379 |
int main(int argc, char **argv) |
380 |
{ |
381 |
g_test_init(&argc, &argv, NULL);
|
382 |
hbitmap_test_add("/hbitmap/size/0", test_hbitmap_zero);
|
383 |
hbitmap_test_add("/hbitmap/size/unaligned", test_hbitmap_unaligned);
|
384 |
hbitmap_test_add("/hbitmap/iter/empty", test_hbitmap_iter_empty);
|
385 |
hbitmap_test_add("/hbitmap/iter/partial", test_hbitmap_iter_partial);
|
386 |
hbitmap_test_add("/hbitmap/iter/granularity", test_hbitmap_iter_granularity);
|
387 |
hbitmap_test_add("/hbitmap/get/all", test_hbitmap_get_all);
|
388 |
hbitmap_test_add("/hbitmap/get/some", test_hbitmap_get_some);
|
389 |
hbitmap_test_add("/hbitmap/set/all", test_hbitmap_set_all);
|
390 |
hbitmap_test_add("/hbitmap/set/one", test_hbitmap_set_one);
|
391 |
hbitmap_test_add("/hbitmap/set/two-elem", test_hbitmap_set_two_elem);
|
392 |
hbitmap_test_add("/hbitmap/set/general", test_hbitmap_set);
|
393 |
hbitmap_test_add("/hbitmap/set/twice", test_hbitmap_set_twice);
|
394 |
hbitmap_test_add("/hbitmap/set/overlap", test_hbitmap_set_overlap);
|
395 |
hbitmap_test_add("/hbitmap/reset/empty", test_hbitmap_reset_empty);
|
396 |
hbitmap_test_add("/hbitmap/reset/general", test_hbitmap_reset);
|
397 |
hbitmap_test_add("/hbitmap/granularity", test_hbitmap_granularity);
|
398 |
g_test_run(); |
399 |
|
400 |
return 0; |
401 |
} |