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
22void
23test_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
66bool 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
78void 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
104void
105test_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
181void
182test_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
206void
207test_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
308static void *gCallbackArg = NULL;
309
310#define NUM_XOR_PTRS  128
311static size_t gNumPtrs;
312static void *gXorPtrs[NUM_XOR_PTRS];
313static bool gClearedPtrs[NUM_XOR_PTRS];
314static bool gSeenPtrs[NUM_XOR_PTRS];
315
316bool
317xorCallback(size_t numPtrs, void **ptrs, const void *finger, void *arg)
318{
319    assert(numPtrs > 0);
320    assert(ptrs != NULL);
321    assert(arg == gCallbackArg);
322
323size_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
333bool
334seenAndClearedMatch()
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
345void
346run_xor(ssize_t offset, size_t step)
347{
348    assert(step != 0);
349    assert(step < HEAP_SIZE);
350
351    /* Figure out the range.
352     */
353uintptr_t base;
354uintptr_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
380uintptr_t addr;
381void **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     */
390HeapBitmap hb1, hb2;
391bool 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     */
400TRACE("walk 0\n");
401    ok = dvmHeapBitmapXorWalk(&hb1, &hb2, xorCallback, gCallbackArg);
402    assert(ok);
403    assert(seenAndClearedMatch());
404
405    /* Walk one empty bitmap.
406     */
407TRACE("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     */
414TRACE("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     */
429size_t i;
430    for (i = 0; i < gNumPtrs; i++) {
431        dvmHeapBitmapSetObjectBit(&hb1, gXorPtrs[i]);
432    }
433TRACE("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    }
442TRACE("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    }
451TRACE("walk 5\n");
452    ok = dvmHeapBitmapXorWalk(&hb1, &hb2, xorCallback, gCallbackArg);
453    assert(ok);
454
455    /* Walk just one bitmap.
456     */
457TRACE("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
470void
471test_xor()
472{
473    run_xor(0, 1);
474    run_xor(100, 34);
475}
476
477int 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