1 #include <stdio.h>
2 #include <stdbool.h>
3 #include <stdint.h>
4 #include <assert.h>
5 #include <string.h>
6 #include <unistd.h>
7 #define __attribute(x) /* disable inlining */
8 #include "HeapBitmap.h"
9 #undef __attribute
10
11 #define PAGE_SIZE 4096
12 #define HEAP_BASE ((void *)0x10000)
13 #define HEAP_SIZE (5 * PAGE_SIZE + 888)
14
15 #define VERBOSE 1
16 #if VERBOSE
17 #define TRACE(...) printf(__VA_ARGS__)
18 #else
19 #define TRACE(...) /**/
20 #endif
21
22 void
test_init()23 test_init()
24 {
25 HeapBitmap hb;
26 bool ok;
27
28 memset(&hb, 0x55, sizeof(hb));
29
30 ok = dvmHeapBitmapInit(&hb, HEAP_BASE, HEAP_SIZE, "test");
31 assert(ok);
32
33 assert(hb.bits != NULL);
34 assert(hb.bitsLen >= HB_OFFSET_TO_INDEX(HEAP_SIZE));
35 assert(hb.base == (uintptr_t)HEAP_BASE);
36 assert(hb.max < hb.base);
37
38 /* Make sure hb.bits is mapped.
39 */
40 *hb.bits = 0x55;
41 assert(*hb.bits = 0x55);
42 *hb.bits = 0;
43
44 #define TEST_UNMAP 0
45 #if TEST_UNMAP
46 /* Hold onto this to make sure it's unmapped later.
47 */
48 unsigned long int *bits = hb.bits;
49 #endif
50
51 dvmHeapBitmapDelete(&hb);
52
53 assert(hb.bits == NULL);
54 assert(hb.bitsLen == 0);
55 assert(hb.base == 0);
56 assert(hb.max == 0);
57
58 #if TEST_UNMAP
59 /* This pointer shouldn't be mapped anymore.
60 */
61 *bits = 0x55;
62 assert(!"Should have segfaulted");
63 #endif
64 }
65
is_zeroed(const HeapBitmap * hb)66 bool is_zeroed(const HeapBitmap *hb)
67 {
68 int i;
69
70 for (i = 0; i < hb->bitsLen / sizeof (*hb->bits); i++) {
71 if (hb->bits[i] != 0L) {
72 return false;
73 }
74 }
75 return true;
76 }
77
assert_empty(const HeapBitmap * hb)78 void assert_empty(const HeapBitmap *hb)
79 {
80 assert(hb->bits != NULL);
81 assert(hb->bitsLen >= HB_OFFSET_TO_INDEX(HEAP_SIZE));
82 assert(hb->base == (uintptr_t)HEAP_BASE);
83 assert(hb->max < hb->base);
84
85 assert(is_zeroed(hb));
86
87 assert(!dvmHeapBitmapMayContainObject(hb,
88 HEAP_BASE));
89 assert(!dvmHeapBitmapMayContainObject(hb,
90 HEAP_BASE + HB_OBJECT_ALIGNMENT));
91 assert(!dvmHeapBitmapMayContainObject(hb,
92 HEAP_BASE + HEAP_SIZE - HB_OBJECT_ALIGNMENT));
93 assert(!dvmHeapBitmapMayContainObject(hb,
94 HEAP_BASE + HEAP_SIZE));
95
96 assert(!dvmHeapBitmapIsObjectBitSet(hb,
97 HEAP_BASE));
98 assert(!dvmHeapBitmapIsObjectBitSet(hb,
99 HEAP_BASE + HB_OBJECT_ALIGNMENT));
100 assert(!dvmHeapBitmapIsObjectBitSet(hb,
101 HEAP_BASE + HEAP_SIZE - HB_OBJECT_ALIGNMENT));
102 }
103
104 void
test_bits()105 test_bits()
106 {
107 HeapBitmap hb;
108 bool ok;
109
110 ok = dvmHeapBitmapInit(&hb, HEAP_BASE, HEAP_SIZE, "test");
111 assert(ok);
112
113 assert_empty(&hb);
114
115 /* Set the lowest address.
116 */
117 dvmHeapBitmapSetObjectBit(&hb, HEAP_BASE);
118 assert(dvmHeapBitmapMayContainObject(&hb,
119 HEAP_BASE));
120 assert(!dvmHeapBitmapMayContainObject(&hb,
121 HEAP_BASE + HB_OBJECT_ALIGNMENT));
122 assert(!dvmHeapBitmapMayContainObject(&hb,
123 HEAP_BASE + HEAP_SIZE - HB_OBJECT_ALIGNMENT));
124 assert(!dvmHeapBitmapMayContainObject(&hb,
125 HEAP_BASE + HEAP_SIZE));
126
127 assert(dvmHeapBitmapIsObjectBitSet(&hb,
128 HEAP_BASE));
129 assert(!dvmHeapBitmapIsObjectBitSet(&hb,
130 HEAP_BASE + HB_OBJECT_ALIGNMENT));
131 assert(!dvmHeapBitmapIsObjectBitSet(&hb,
132 HEAP_BASE + HEAP_SIZE - HB_OBJECT_ALIGNMENT));
133
134 /* Set the highest address.
135 */
136 dvmHeapBitmapSetObjectBit(&hb, HEAP_BASE + HEAP_SIZE - HB_OBJECT_ALIGNMENT);
137 assert(dvmHeapBitmapMayContainObject(&hb,
138 HEAP_BASE));
139 assert(dvmHeapBitmapMayContainObject(&hb,
140 HEAP_BASE + HB_OBJECT_ALIGNMENT));
141 assert(dvmHeapBitmapMayContainObject(&hb,
142 HEAP_BASE + HEAP_SIZE - HB_OBJECT_ALIGNMENT));
143 assert(!dvmHeapBitmapMayContainObject(&hb,
144 HEAP_BASE + HEAP_SIZE));
145
146 assert(dvmHeapBitmapIsObjectBitSet(&hb,
147 HEAP_BASE));
148 assert(!dvmHeapBitmapIsObjectBitSet(&hb,
149 HEAP_BASE + HB_OBJECT_ALIGNMENT));
150 assert(dvmHeapBitmapIsObjectBitSet(&hb,
151 HEAP_BASE + HEAP_SIZE - HB_OBJECT_ALIGNMENT));
152
153 /* Clear the lowest address.
154 */
155 dvmHeapBitmapClearObjectBit(&hb, HEAP_BASE);
156 assert(!dvmHeapBitmapIsObjectBitSet(&hb,
157 HEAP_BASE));
158 assert(!dvmHeapBitmapIsObjectBitSet(&hb,
159 HEAP_BASE + HB_OBJECT_ALIGNMENT));
160 assert(dvmHeapBitmapIsObjectBitSet(&hb,
161 HEAP_BASE + HEAP_SIZE - HB_OBJECT_ALIGNMENT));
162 assert(!is_zeroed(&hb));
163
164 /* Clear the highest address.
165 */
166 dvmHeapBitmapClearObjectBit(&hb,
167 HEAP_BASE + HEAP_SIZE - HB_OBJECT_ALIGNMENT);
168 assert(!dvmHeapBitmapIsObjectBitSet(&hb,
169 HEAP_BASE));
170 assert(!dvmHeapBitmapIsObjectBitSet(&hb,
171 HEAP_BASE + HB_OBJECT_ALIGNMENT));
172 assert(!dvmHeapBitmapIsObjectBitSet(&hb,
173 HEAP_BASE + HEAP_SIZE - HB_OBJECT_ALIGNMENT));
174 assert(is_zeroed(&hb));
175
176 /* Clean up.
177 */
178 dvmHeapBitmapDelete(&hb);
179 }
180
181 void
test_clear()182 test_clear()
183 {
184 HeapBitmap hb;
185 bool ok;
186
187 ok = dvmHeapBitmapInit(&hb, HEAP_BASE, HEAP_SIZE, "test");
188 assert(ok);
189 assert_empty(&hb);
190
191 /* Set the highest address.
192 */
193 dvmHeapBitmapSetObjectBit(&hb, HEAP_BASE + HEAP_SIZE - HB_OBJECT_ALIGNMENT);
194 assert(!is_zeroed(&hb));
195
196 /* Clear the bitmap.
197 */
198 dvmHeapBitmapZero(&hb);
199 assert_empty(&hb);
200
201 /* Clean up.
202 */
203 dvmHeapBitmapDelete(&hb);
204 }
205
206 void
test_modify()207 test_modify()
208 {
209 HeapBitmap hb;
210 bool ok;
211 unsigned long bit;
212
213 ok = dvmHeapBitmapInit(&hb, HEAP_BASE, HEAP_SIZE, "test");
214 assert(ok);
215 assert_empty(&hb);
216
217 /* Set the lowest address.
218 */
219 bit = dvmHeapBitmapSetAndReturnObjectBit(&hb, HEAP_BASE);
220 assert(bit == 0);
221 assert(dvmHeapBitmapMayContainObject(&hb,
222 HEAP_BASE));
223 assert(!dvmHeapBitmapMayContainObject(&hb,
224 HEAP_BASE + HB_OBJECT_ALIGNMENT));
225 assert(!dvmHeapBitmapMayContainObject(&hb,
226 HEAP_BASE + HEAP_SIZE - HB_OBJECT_ALIGNMENT));
227 assert(!dvmHeapBitmapMayContainObject(&hb,
228 HEAP_BASE + HEAP_SIZE));
229
230 assert(dvmHeapBitmapIsObjectBitSet(&hb,
231 HEAP_BASE));
232 assert(!dvmHeapBitmapIsObjectBitSet(&hb,
233 HEAP_BASE + HB_OBJECT_ALIGNMENT));
234 assert(!dvmHeapBitmapIsObjectBitSet(&hb,
235 HEAP_BASE + HEAP_SIZE - HB_OBJECT_ALIGNMENT));
236
237 /* Set the lowest address again.
238 */
239 bit = dvmHeapBitmapSetAndReturnObjectBit(&hb, HEAP_BASE);
240 assert(bit != 0);
241 assert(dvmHeapBitmapMayContainObject(&hb,
242 HEAP_BASE));
243 assert(!dvmHeapBitmapMayContainObject(&hb,
244 HEAP_BASE + HB_OBJECT_ALIGNMENT));
245 assert(!dvmHeapBitmapMayContainObject(&hb,
246 HEAP_BASE + HEAP_SIZE - HB_OBJECT_ALIGNMENT));
247 assert(!dvmHeapBitmapMayContainObject(&hb,
248 HEAP_BASE + HEAP_SIZE));
249
250 assert(dvmHeapBitmapIsObjectBitSet(&hb,
251 HEAP_BASE));
252 assert(!dvmHeapBitmapIsObjectBitSet(&hb,
253 HEAP_BASE + HB_OBJECT_ALIGNMENT));
254 assert(!dvmHeapBitmapIsObjectBitSet(&hb,
255 HEAP_BASE + HEAP_SIZE - HB_OBJECT_ALIGNMENT));
256
257 /* Set the highest address.
258 */
259 bit = dvmHeapBitmapSetAndReturnObjectBit(&hb,
260 HEAP_BASE + HEAP_SIZE - HB_OBJECT_ALIGNMENT);
261 assert(bit == 0);
262 assert(dvmHeapBitmapMayContainObject(&hb,
263 HEAP_BASE));
264 assert(dvmHeapBitmapMayContainObject(&hb,
265 HEAP_BASE + HB_OBJECT_ALIGNMENT));
266 assert(dvmHeapBitmapMayContainObject(&hb,
267 HEAP_BASE + HEAP_SIZE - HB_OBJECT_ALIGNMENT));
268 assert(!dvmHeapBitmapMayContainObject(&hb,
269 HEAP_BASE + HEAP_SIZE));
270
271 assert(dvmHeapBitmapIsObjectBitSet(&hb,
272 HEAP_BASE));
273 assert(!dvmHeapBitmapIsObjectBitSet(&hb,
274 HEAP_BASE + HB_OBJECT_ALIGNMENT));
275 assert(dvmHeapBitmapIsObjectBitSet(&hb,
276 HEAP_BASE + HEAP_SIZE - HB_OBJECT_ALIGNMENT));
277
278 /* Set the highest address again.
279 */
280 bit = dvmHeapBitmapSetAndReturnObjectBit(&hb,
281 HEAP_BASE + HEAP_SIZE - HB_OBJECT_ALIGNMENT);
282 assert(bit != 0);
283 assert(dvmHeapBitmapMayContainObject(&hb,
284 HEAP_BASE));
285 assert(dvmHeapBitmapMayContainObject(&hb,
286 HEAP_BASE + HB_OBJECT_ALIGNMENT));
287 assert(dvmHeapBitmapMayContainObject(&hb,
288 HEAP_BASE + HEAP_SIZE - HB_OBJECT_ALIGNMENT));
289 assert(!dvmHeapBitmapMayContainObject(&hb,
290 HEAP_BASE + HEAP_SIZE));
291
292 assert(dvmHeapBitmapIsObjectBitSet(&hb,
293 HEAP_BASE));
294 assert(!dvmHeapBitmapIsObjectBitSet(&hb,
295 HEAP_BASE + HB_OBJECT_ALIGNMENT));
296 assert(dvmHeapBitmapIsObjectBitSet(&hb,
297 HEAP_BASE + HEAP_SIZE - HB_OBJECT_ALIGNMENT));
298
299 /* Clean up.
300 */
301 dvmHeapBitmapDelete(&hb);
302 }
303
304 /*
305 * xor test support functions
306 */
307
308 static void *gCallbackArg = NULL;
309
310 #define NUM_XOR_PTRS 128
311 static size_t gNumPtrs;
312 static void *gXorPtrs[NUM_XOR_PTRS];
313 static bool gClearedPtrs[NUM_XOR_PTRS];
314 static bool gSeenPtrs[NUM_XOR_PTRS];
315
316 bool
xorCallback(size_t numPtrs,void ** ptrs,const void * finger,void * arg)317 xorCallback(size_t numPtrs, void **ptrs, const void *finger, void *arg)
318 {
319 assert(numPtrs > 0);
320 assert(ptrs != NULL);
321 assert(arg == gCallbackArg);
322
323 size_t i;
324 for (i = 0; i < numPtrs; i++) {
325 assert(ptrs[i] < finger);
326 printf("callback: 0x%08x ( < 0x%08x )\n",
327 (uintptr_t)ptrs[i], (uintptr_t)finger);
328 }
329
330 return true;
331 }
332
333 bool
seenAndClearedMatch()334 seenAndClearedMatch()
335 {
336 size_t i;
337 for (i = 0; i < gNumPtrs; i++) {
338 if (gClearedPtrs[i] != gSeenPtrs[i]) {
339 return false;
340 }
341 }
342 return true;
343 }
344
345 void
run_xor(ssize_t offset,size_t step)346 run_xor(ssize_t offset, size_t step)
347 {
348 assert(step != 0);
349 assert(step < HEAP_SIZE);
350
351 /* Figure out the range.
352 */
353 uintptr_t base;
354 uintptr_t top;
355 if (offset >= 0) {
356 base = (uintptr_t)HEAP_BASE + offset;
357 } else {
358 base = (uintptr_t)HEAP_BASE + (uintptr_t)HEAP_SIZE + offset;
359 }
360 if (base < (uintptr_t)HEAP_BASE) {
361 base = (uintptr_t)HEAP_BASE;
362 } else if (base > (uintptr_t)(HEAP_BASE + HEAP_SIZE)) {
363 base = (uintptr_t)(HEAP_BASE + HEAP_SIZE);
364 } else {
365 base = (base + HB_OBJECT_ALIGNMENT - 1) & ~(HB_OBJECT_ALIGNMENT - 1);
366 }
367 step *= HB_OBJECT_ALIGNMENT;
368 top = base + step * NUM_XOR_PTRS;
369 if (top > (uintptr_t)(HEAP_BASE + HEAP_SIZE)) {
370 top = (uintptr_t)(HEAP_BASE + HEAP_SIZE);
371 }
372
373 /* Create the pointers.
374 */
375 gNumPtrs = 0;
376 memset(gXorPtrs, 0, sizeof(gXorPtrs));
377 memset(gClearedPtrs, 0, sizeof(gClearedPtrs));
378 memset(gSeenPtrs, 0, sizeof(gSeenPtrs));
379
380 uintptr_t addr;
381 void **p = gXorPtrs;
382 for (addr = base; addr < top; addr += step) {
383 *p++ = (void *)addr;
384 gNumPtrs++;
385 }
386 assert(seenAndClearedMatch());
387
388 /* Set up the bitmaps.
389 */
390 HeapBitmap hb1, hb2;
391 bool ok;
392
393 ok = dvmHeapBitmapInit(&hb1, HEAP_BASE, HEAP_SIZE, "test1");
394 assert(ok);
395 ok = dvmHeapBitmapInitFromTemplate(&hb2, &hb1, "test2");
396 assert(ok);
397
398 /* Walk two empty bitmaps.
399 */
400 TRACE("walk 0\n");
401 ok = dvmHeapBitmapXorWalk(&hb1, &hb2, xorCallback, gCallbackArg);
402 assert(ok);
403 assert(seenAndClearedMatch());
404
405 /* Walk one empty bitmap.
406 */
407 TRACE("walk 1\n");
408 dvmHeapBitmapSetObjectBit(&hb1, (void *)base);
409 ok = dvmHeapBitmapXorWalk(&hb1, &hb2, xorCallback, gCallbackArg);
410 assert(ok);
411
412 /* Make the bitmaps match.
413 */
414 TRACE("walk 2\n");
415 dvmHeapBitmapSetObjectBit(&hb2, (void *)base);
416 ok = dvmHeapBitmapXorWalk(&hb1, &hb2, xorCallback, gCallbackArg);
417 assert(ok);
418
419 /* Clear the bitmaps.
420 */
421 dvmHeapBitmapZero(&hb1);
422 assert_empty(&hb1);
423 dvmHeapBitmapZero(&hb2);
424 assert_empty(&hb2);
425
426 /* Set the pointers we created in one of the bitmaps,
427 * then visit them.
428 */
429 size_t i;
430 for (i = 0; i < gNumPtrs; i++) {
431 dvmHeapBitmapSetObjectBit(&hb1, gXorPtrs[i]);
432 }
433 TRACE("walk 3\n");
434 ok = dvmHeapBitmapXorWalk(&hb1, &hb2, xorCallback, gCallbackArg);
435 assert(ok);
436
437 /* Set every third pointer in the other bitmap, and visit again.
438 */
439 for (i = 0; i < gNumPtrs; i += 3) {
440 dvmHeapBitmapSetObjectBit(&hb2, gXorPtrs[i]);
441 }
442 TRACE("walk 4\n");
443 ok = dvmHeapBitmapXorWalk(&hb1, &hb2, xorCallback, gCallbackArg);
444 assert(ok);
445
446 /* Set every other pointer in the other bitmap, and visit again.
447 */
448 for (i = 0; i < gNumPtrs; i += 2) {
449 dvmHeapBitmapSetObjectBit(&hb2, gXorPtrs[i]);
450 }
451 TRACE("walk 5\n");
452 ok = dvmHeapBitmapXorWalk(&hb1, &hb2, xorCallback, gCallbackArg);
453 assert(ok);
454
455 /* Walk just one bitmap.
456 */
457 TRACE("walk 6\n");
458 ok = dvmHeapBitmapWalk(&hb2, xorCallback, gCallbackArg);
459 assert(ok);
460
461 //xxx build an expect list for the callback
462 //xxx test where max points to beginning, middle, and end of a word
463
464 /* Clean up.
465 */
466 dvmHeapBitmapDelete(&hb1);
467 dvmHeapBitmapDelete(&hb2);
468 }
469
470 void
test_xor()471 test_xor()
472 {
473 run_xor(0, 1);
474 run_xor(100, 34);
475 }
476
main(int argc,char * argv[])477 int main(int argc, char *argv[])
478 {
479 printf("test_init...\n");
480 test_init();
481
482 printf("test_bits...\n");
483 test_bits();
484
485 printf("test_clear...\n");
486 test_clear();
487
488 printf("test_modify...\n");
489 test_modify();
490
491 printf("test_xor...\n");
492 test_xor();
493
494 printf("done.\n");
495 return 0;
496 }
497