]> git.proxmox.com Git - qemu.git/blob - tests/test-hbitmap.c
target-openrisc: Remove executable flag for every page
[qemu.git] / tests / test-hbitmap.c
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 }