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 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 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 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 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 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 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 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 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 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 471 test_xor() 472 { 473 run_xor(0, 1); 474 run_xor(100, 34); 475 } 476 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
