1 /* 2 * Copyright (C) 2009 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 /* 18 * Test the indirect reference table implementation. 19 */ 20 #include "Dalvik.h" 21 22 #include <stdlib.h> 23 24 #ifndef NDEBUG 25 26 #define DBUG_MSG LOGV 27 28 /* 29 * Basic add/get/delete tests in an unsegmented table. 30 */ 31 static bool basicTest(void) 32 { 33 static const int kTableMax = 20; 34 IndirectRefTable irt; 35 IndirectRef iref0, iref1, iref2, iref3; 36 IndirectRef manyRefs[kTableMax]; 37 ClassObject* clazz = dvmFindClass("Ljava/lang/Object;", NULL); 38 Object* obj0 = dvmAllocObject(clazz, ALLOC_DONT_TRACK); 39 Object* obj1 = dvmAllocObject(clazz, ALLOC_DONT_TRACK); 40 Object* obj2 = dvmAllocObject(clazz, ALLOC_DONT_TRACK); 41 Object* obj3 = dvmAllocObject(clazz, ALLOC_DONT_TRACK); 42 const u4 cookie = IRT_FIRST_SEGMENT; 43 bool result = false; 44 45 if (!dvmInitIndirectRefTable(&irt, kTableMax/2, kTableMax, 46 kIndirectKindGlobal)) 47 { 48 return false; 49 } 50 51 iref0 = (IndirectRef) 0x11110; 52 if (dvmRemoveFromIndirectRefTable(&irt, cookie, iref0)) { 53 LOGE("unexpectedly successful removal\n"); 54 goto bail; 55 } 56 57 /* 58 * Add three, check, remove in the order in which they were added. 59 */ 60 DBUG_MSG("+++ START fifo\n"); 61 iref0 = dvmAddToIndirectRefTable(&irt, cookie, obj0); 62 iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj1); 63 iref2 = dvmAddToIndirectRefTable(&irt, cookie, obj2); 64 if (iref0 == NULL || iref1 == NULL || iref2 == NULL) { 65 LOGE("trivial add1 failed\n"); 66 goto bail; 67 } 68 69 if (dvmGetFromIndirectRefTable(&irt, iref0) != obj0 || 70 dvmGetFromIndirectRefTable(&irt, iref1) != obj1 || 71 dvmGetFromIndirectRefTable(&irt, iref2) != obj2) 72 { 73 LOGE("objects don't match expected values %p %p %p vs. %p %p %p\n", 74 dvmGetFromIndirectRefTable(&irt, iref0), 75 dvmGetFromIndirectRefTable(&irt, iref1), 76 dvmGetFromIndirectRefTable(&irt, iref2), 77 obj0, obj1, obj2); 78 goto bail; 79 } else { 80 DBUG_MSG("+++ obj1=%p --> iref1=%p\n", obj1, iref1); 81 } 82 83 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref0) || 84 !dvmRemoveFromIndirectRefTable(&irt, cookie, iref1) || 85 !dvmRemoveFromIndirectRefTable(&irt, cookie, iref2)) 86 { 87 LOGE("fifo deletion failed\n"); 88 goto bail; 89 } 90 91 /* table should be empty now */ 92 if (dvmIndirectRefTableEntries(&irt) != 0) { 93 LOGE("fifo del not empty\n"); 94 goto bail; 95 } 96 97 /* get invalid entry (off the end of the list) */ 98 if (dvmGetFromIndirectRefTable(&irt, iref0) != NULL) { 99 LOGE("stale entry get succeeded unexpectedly\n"); 100 goto bail; 101 } 102 103 /* 104 * Add three, remove in the opposite order. 105 */ 106 DBUG_MSG("+++ START lifo\n"); 107 iref0 = dvmAddToIndirectRefTable(&irt, cookie, obj0); 108 iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj1); 109 iref2 = dvmAddToIndirectRefTable(&irt, cookie, obj2); 110 if (iref0 == NULL || iref1 == NULL || iref2 == NULL) { 111 LOGE("trivial add2 failed\n"); 112 goto bail; 113 } 114 115 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref2) || 116 !dvmRemoveFromIndirectRefTable(&irt, cookie, iref1) || 117 !dvmRemoveFromIndirectRefTable(&irt, cookie, iref0)) 118 { 119 LOGE("lifo deletion failed\n"); 120 goto bail; 121 } 122 123 /* table should be empty now */ 124 if (dvmIndirectRefTableEntries(&irt) != 0) { 125 LOGE("lifo del not empty\n"); 126 goto bail; 127 } 128 129 /* 130 * Add three, remove middle / middle / bottom / top. (Second attempt 131 * to remove middle should fail.) 132 */ 133 DBUG_MSG("+++ START unorder\n"); 134 iref0 = dvmAddToIndirectRefTable(&irt, cookie, obj0); 135 iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj1); 136 iref2 = dvmAddToIndirectRefTable(&irt, cookie, obj2); 137 if (iref0 == NULL || iref1 == NULL || iref2 == NULL) { 138 LOGE("trivial add3 failed\n"); 139 goto bail; 140 } 141 142 if (dvmIndirectRefTableEntries(&irt) != 3) { 143 LOGE("expected 3 entries, found %d\n", 144 dvmIndirectRefTableEntries(&irt)); 145 goto bail; 146 } 147 148 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref1) || 149 dvmRemoveFromIndirectRefTable(&irt, cookie, iref1)) 150 { 151 LOGE("unorder deletion1 failed\n"); 152 goto bail; 153 } 154 155 /* get invalid entry (from hole) */ 156 if (dvmGetFromIndirectRefTable(&irt, iref1) != NULL) { 157 LOGE("hole get succeeded unexpectedly\n"); 158 goto bail; 159 } 160 161 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref2) || 162 !dvmRemoveFromIndirectRefTable(&irt, cookie, iref0)) 163 { 164 LOGE("unorder deletion2 failed\n"); 165 goto bail; 166 } 167 168 /* table should be empty now */ 169 if (dvmIndirectRefTableEntries(&irt) != 0) { 170 LOGE("unorder del not empty\n"); 171 goto bail; 172 } 173 174 /* 175 * Add four entries. Remove #1, add new entry, verify that table size 176 * is still 4 (i.e. holes are getting filled). Remove #1 and #3, verify 177 * that we delete one and don't hole-compact the other. 178 */ 179 DBUG_MSG("+++ START hole fill\n"); 180 iref0 = dvmAddToIndirectRefTable(&irt, cookie, obj0); 181 iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj1); 182 iref2 = dvmAddToIndirectRefTable(&irt, cookie, obj2); 183 iref3 = dvmAddToIndirectRefTable(&irt, cookie, obj3); 184 if (iref0 == NULL || iref1 == NULL || iref2 == NULL || iref3 == NULL) { 185 LOGE("trivial add4 failed\n"); 186 goto bail; 187 } 188 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref1)) { 189 LOGE("remove 1 of 4 failed\n"); 190 goto bail; 191 } 192 iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj1); 193 if (dvmIndirectRefTableEntries(&irt) != 4) { 194 LOGE("hole not filled\n"); 195 goto bail; 196 } 197 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref1) || 198 !dvmRemoveFromIndirectRefTable(&irt, cookie, iref3)) 199 { 200 LOGE("remove 1/3 failed\n"); 201 goto bail; 202 } 203 if (dvmIndirectRefTableEntries(&irt) != 3) { 204 LOGE("should be 3 after two deletions\n"); 205 goto bail; 206 } 207 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref2) || 208 !dvmRemoveFromIndirectRefTable(&irt, cookie, iref0)) 209 { 210 LOGE("remove 2/0 failed\n"); 211 goto bail; 212 } 213 if (dvmIndirectRefTableEntries(&irt) != 0) { 214 LOGE("not empty after split remove\n"); 215 goto bail; 216 } 217 218 /* 219 * Add an entry, remove it, add a new entry, and try to use the original 220 * iref. They have the same slot number but are for different objects. 221 * With the extended checks in place, this should fail. 222 */ 223 DBUG_MSG("+++ START switched\n"); 224 iref0 = dvmAddToIndirectRefTable(&irt, cookie, obj0); 225 dvmRemoveFromIndirectRefTable(&irt, cookie, iref0); 226 iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj1); 227 if (dvmRemoveFromIndirectRefTable(&irt, cookie, iref0)) { 228 LOGE("mismatched del succeeded (%p vs %p)\n", iref0, iref1); 229 goto bail; 230 } 231 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref1)) { 232 LOGE("switched del failed\n"); 233 goto bail; 234 } 235 if (dvmIndirectRefTableEntries(&irt) != 0) { 236 LOGE("switching del not empty\n"); 237 goto bail; 238 } 239 240 /* 241 * Same as above, but with the same object. A more rigorous checker 242 * (e.g. with slot serialization) will catch this. 243 */ 244 iref0 = dvmAddToIndirectRefTable(&irt, cookie, obj0); 245 dvmRemoveFromIndirectRefTable(&irt, cookie, iref0); 246 iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj0); 247 if (iref0 != iref1) { 248 /* try 0, should not work */ 249 if (dvmRemoveFromIndirectRefTable(&irt, cookie, iref0)) { 250 LOGE("temporal del succeeded (%p vs %p)\n", iref0, iref1); 251 goto bail; 252 } 253 } 254 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref1)) { 255 LOGE("temporal cleanup failed\n"); 256 goto bail; 257 } 258 if (dvmIndirectRefTableEntries(&irt) != 0) { 259 LOGE("temporal del not empty\n"); 260 goto bail; 261 } 262 263 /* 264 * Test table overflow. 265 */ 266 DBUG_MSG("+++ START overflow\n"); 267 int i; 268 for (i = 0; i < kTableMax; i++) { 269 manyRefs[i] = dvmAddToIndirectRefTable(&irt, cookie, obj0); 270 if (manyRefs[i] == NULL) { 271 LOGE("Failed adding %d of %d\n", i, kTableMax); 272 goto bail; 273 } 274 } 275 if (dvmAddToIndirectRefTable(&irt, cookie, obj0) != NULL) { 276 LOGE("Table overflow succeeded\n"); 277 goto bail; 278 } 279 if (dvmIndirectRefTableEntries(&irt) != (size_t)kTableMax) { 280 LOGE("Expected %d entries, found %d\n", 281 kTableMax, dvmIndirectRefTableEntries(&irt)); 282 goto bail; 283 } 284 for (i = 0; i < kTableMax-1; i++) { 285 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, manyRefs[i])) { 286 LOGE("multi-remove failed at %d\n", i); 287 goto bail; 288 } 289 } 290 /* because of removal order, should have 20 entries, 19 of them holes */ 291 if (dvmIndirectRefTableEntries(&irt) != (size_t)kTableMax) { 292 LOGE("Expected %d entries (with holes), found %d\n", 293 kTableMax, dvmIndirectRefTableEntries(&irt)); 294 goto bail; 295 } 296 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, manyRefs[kTableMax-1])) { 297 LOGE("multi-remove final failed\n"); 298 goto bail; 299 } 300 if (dvmIndirectRefTableEntries(&irt) != 0) { 301 LOGE("multi-del not empty\n"); 302 goto bail; 303 } 304 305 DBUG_MSG("+++ basic test complete\n"); 306 result = true; 307 308 bail: 309 dvmClearIndirectRefTable(&irt); 310 return result; 311 } 312 313 /* 314 * Test operations on a segmented table. 315 */ 316 static bool segmentTest(void) 317 { 318 static const int kTableMax = 20; 319 IndirectRefTable irt; 320 IndirectRef iref0, iref1, iref2, iref3; 321 ClassObject* clazz = dvmFindClass("Ljava/lang/Object;", NULL); 322 Object* obj0 = dvmAllocObject(clazz, ALLOC_DONT_TRACK); 323 Object* obj1 = dvmAllocObject(clazz, ALLOC_DONT_TRACK); 324 Object* obj2 = dvmAllocObject(clazz, ALLOC_DONT_TRACK); 325 Object* obj3 = dvmAllocObject(clazz, ALLOC_DONT_TRACK); 326 u4 cookie; 327 u4 segmentState[4]; 328 bool result = false; 329 330 if (!dvmInitIndirectRefTable(&irt, kTableMax, kTableMax, 331 kIndirectKindLocal)) 332 { 333 return false; 334 } 335 cookie = segmentState[0] = IRT_FIRST_SEGMENT; 336 DBUG_MSG("+++ objs %p %p %p %p\n", obj0, obj1, obj2, obj3); 337 338 /* 339 * Push two, create new segment, push two more, try to get all four, 340 * try to delete all 4. All four should be accessible, but only the 341 * last two should be deletable. 342 */ 343 DBUG_MSG("+++ START basic segment\n"); 344 iref0 = dvmAddToIndirectRefTable(&irt, cookie, obj0); 345 iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj1); 346 cookie = segmentState[1] = dvmPushIndirectRefTableSegment(&irt); 347 DBUG_MSG("+++ pushed, cookie is 0x%08x\n", cookie); 348 iref2 = dvmAddToIndirectRefTable(&irt, cookie, obj2); 349 iref3 = dvmAddToIndirectRefTable(&irt, cookie, obj3); 350 351 if (dvmRemoveFromIndirectRefTable(&irt, cookie, iref0) || 352 dvmRemoveFromIndirectRefTable(&irt, cookie, iref1)) 353 { 354 LOGE("removed values from earlier segment\n"); 355 goto bail; 356 } 357 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref2) || 358 !dvmRemoveFromIndirectRefTable(&irt, cookie, iref3)) 359 { 360 LOGE("unable to remove values from current segment\n"); 361 goto bail; 362 } 363 if (dvmIndirectRefTableEntries(&irt) != 2) { 364 LOGE("wrong total entries\n"); 365 goto bail; 366 } 367 dvmPopIndirectRefTableSegment(&irt, segmentState[1]); 368 cookie = segmentState[0]; 369 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref0) || 370 !dvmRemoveFromIndirectRefTable(&irt, cookie, iref1)) 371 { 372 LOGE("unable to remove values from first segment\n"); 373 goto bail; 374 } 375 if (dvmIndirectRefTableEntries(&irt) != 0) { 376 LOGE("basic push/pop not empty\n"); 377 goto bail; 378 } 379 380 /* 381 * Push two, delete first, segment, push two more, pop segment, verify 382 * the last two are no longer present and hole count is right. The 383 * adds after the segment pop should not be filling in the hole. 384 */ 385 DBUG_MSG("+++ START segment pop\n"); 386 iref0 = dvmAddToIndirectRefTable(&irt, cookie, obj0); 387 iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj1); 388 dvmRemoveFromIndirectRefTable(&irt, cookie, iref0); 389 cookie = segmentState[1] = dvmPushIndirectRefTableSegment(&irt); 390 iref2 = dvmAddToIndirectRefTable(&irt, cookie, obj2); 391 iref3 = dvmAddToIndirectRefTable(&irt, cookie, obj3); 392 dvmPopIndirectRefTableSegment(&irt, segmentState[1]); 393 cookie = segmentState[0]; 394 if (dvmIndirectRefTableEntries(&irt) != 2) { 395 LOGE("wrong total entries after pop\n"); 396 goto bail; 397 } 398 dvmRemoveFromIndirectRefTable(&irt, cookie, iref1); 399 if (dvmIndirectRefTableEntries(&irt) != 0) { 400 LOGE("not back to zero after pop + del\n"); 401 goto bail; 402 } 403 404 /* 405 * Multiple segments, some empty. 406 */ 407 DBUG_MSG("+++ START multiseg\n"); 408 iref0 = dvmAppendToIndirectRefTable(&irt, cookie, obj0); 409 iref1 = dvmAppendToIndirectRefTable(&irt, cookie, obj1); 410 cookie = segmentState[1] = dvmPushIndirectRefTableSegment(&irt); 411 cookie = segmentState[2] = dvmPushIndirectRefTableSegment(&irt); 412 iref3 = dvmAppendToIndirectRefTable(&irt, cookie, obj3); 413 iref2 = dvmAppendToIndirectRefTable(&irt, cookie, obj2); 414 dvmRemoveFromIndirectRefTable(&irt, cookie, iref3); 415 cookie = segmentState[3] = dvmPushIndirectRefTableSegment(&irt); 416 iref3 = dvmAppendToIndirectRefTable(&irt, cookie, obj3); 417 418 if (dvmGetFromIndirectRefTable(&irt, iref0) != obj0 || 419 dvmGetFromIndirectRefTable(&irt, iref1) != obj1 || 420 dvmGetFromIndirectRefTable(&irt, iref2) != obj2 || 421 dvmGetFromIndirectRefTable(&irt, iref3) != obj3) 422 { 423 LOGE("Unable to retrieve all multiseg objects\n"); 424 goto bail; 425 } 426 427 dvmDumpIndirectRefTable(&irt, "test"); 428 429 //int i; 430 //for (i = 0; i < sizeof(segmentState) / sizeof(segmentState[0]); i++) { 431 // DBUG_MSG("+++ segment %d = 0x%08x\n", i, segmentState[i]); 432 //} 433 434 dvmRemoveFromIndirectRefTable(&irt, cookie, iref3); 435 if (dvmRemoveFromIndirectRefTable(&irt, cookie, iref2)) { 436 LOGE("multiseg del2 worked\n"); 437 goto bail; 438 } 439 dvmPopIndirectRefTableSegment(&irt, segmentState[3]); 440 cookie = segmentState[2]; 441 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref2)) { 442 LOGE("multiseg del2b failed (cookie=0x%08x ref=%p)\n", cookie, iref2); 443 goto bail; 444 } 445 iref2 = dvmAddToIndirectRefTable(&irt, cookie, obj2); 446 447 /* pop two off at once */ 448 dvmPopIndirectRefTableSegment(&irt, segmentState[1]); 449 cookie = segmentState[0]; 450 451 if (dvmIndirectRefTableEntries(&irt) != 2) { 452 LOGE("Unexpected entry count in multiseg\n"); 453 goto bail; 454 } 455 dvmRemoveFromIndirectRefTable(&irt, cookie, iref0); 456 dvmRemoveFromIndirectRefTable(&irt, cookie, iref1); 457 if (dvmIndirectRefTableEntries(&irt) != 0) { 458 LOGE("Unexpected entry count at multiseg end\n"); 459 goto bail; 460 } 461 462 DBUG_MSG("+++ segment test complete\n"); 463 result = true; 464 465 bail: 466 dvmClearIndirectRefTable(&irt); 467 return result; 468 } 469 470 471 /* 472 * Some quick tests. 473 */ 474 bool dvmTestIndirectRefTable(void) 475 { 476 if (!basicTest()) { 477 LOGE("IRT basic test failed\n"); 478 return false; 479 } 480 if (!segmentTest()) { 481 LOGE("IRT segment test failed\n"); 482 return false; 483 } 484 485 return true; 486 } 487 488 #endif /*NDEBUG*/ 489
