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 #include <sys/time.h> 24 25 #ifndef NDEBUG 26 27 #define DBUG_MSG ALOGI 28 29 class Stopwatch { 30 public: 31 Stopwatch() { 32 reset(); 33 } 34 35 void reset() { 36 start_ = now(); 37 } 38 39 float elapsedSeconds() { 40 return (now() - start_) * 0.000001f; 41 } 42 43 private: 44 u8 start_; 45 46 static u8 now() { 47 #ifdef HAVE_POSIX_CLOCKS 48 struct timespec tm; 49 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &tm); 50 return tm.tv_sec * 1000000LL + tm.tv_nsec / 1000; 51 #else 52 struct timeval tv; 53 gettimeofday(&tv, NULL); 54 return tv.tv_sec * 1000000LL + tv.tv_usec; 55 #endif 56 } 57 }; 58 59 /* 60 * Basic add/get/delete tests in an unsegmented table. 61 */ 62 static bool basicTest() 63 { 64 static const int kTableMax = 20; 65 IndirectRefTable irt; 66 IndirectRef iref0, iref1, iref2, iref3; 67 IndirectRef manyRefs[kTableMax]; 68 ClassObject* clazz = dvmFindClass("Ljava/lang/Object;", NULL); 69 Object* obj0 = dvmAllocObject(clazz, ALLOC_DONT_TRACK); 70 Object* obj1 = dvmAllocObject(clazz, ALLOC_DONT_TRACK); 71 Object* obj2 = dvmAllocObject(clazz, ALLOC_DONT_TRACK); 72 Object* obj3 = dvmAllocObject(clazz, ALLOC_DONT_TRACK); 73 const u4 cookie = IRT_FIRST_SEGMENT; 74 bool result = false; 75 76 if (!irt.init(kTableMax/2, kTableMax, kIndirectKindGlobal)) { 77 return false; 78 } 79 80 iref0 = (IndirectRef) 0x11110; 81 if (irt.remove(cookie, iref0)) { 82 ALOGE("unexpectedly successful removal"); 83 goto bail; 84 } 85 86 /* 87 * Add three, check, remove in the order in which they were added. 88 */ 89 DBUG_MSG("+++ START fifo\n"); 90 iref0 = irt.add(cookie, obj0); 91 iref1 = irt.add(cookie, obj1); 92 iref2 = irt.add(cookie, obj2); 93 if (iref0 == NULL || iref1 == NULL || iref2 == NULL) { 94 ALOGE("trivial add1 failed"); 95 goto bail; 96 } 97 98 if (irt.get(iref0) != obj0 || 99 irt.get(iref1) != obj1 || 100 irt.get(iref2) != obj2) { 101 ALOGE("objects don't match expected values %p %p %p vs. %p %p %p", 102 irt.get(iref0), irt.get(iref1), irt.get(iref2), 103 obj0, obj1, obj2); 104 goto bail; 105 } else { 106 DBUG_MSG("+++ obj1=%p --> iref1=%p\n", obj1, iref1); 107 } 108 109 if (!irt.remove(cookie, iref0) || 110 !irt.remove(cookie, iref1) || 111 !irt.remove(cookie, iref2)) 112 { 113 ALOGE("fifo deletion failed"); 114 goto bail; 115 } 116 117 /* table should be empty now */ 118 if (irt.capacity() != 0) { 119 ALOGE("fifo del not empty"); 120 goto bail; 121 } 122 123 /* get invalid entry (off the end of the list) */ 124 if (irt.get(iref0) != kInvalidIndirectRefObject) { 125 ALOGE("stale entry get succeeded unexpectedly"); 126 goto bail; 127 } 128 129 /* 130 * Add three, remove in the opposite order. 131 */ 132 DBUG_MSG("+++ START lifo\n"); 133 iref0 = irt.add(cookie, obj0); 134 iref1 = irt.add(cookie, obj1); 135 iref2 = irt.add(cookie, obj2); 136 if (iref0 == NULL || iref1 == NULL || iref2 == NULL) { 137 ALOGE("trivial add2 failed"); 138 goto bail; 139 } 140 141 if (!irt.remove(cookie, iref2) || 142 !irt.remove(cookie, iref1) || 143 !irt.remove(cookie, iref0)) 144 { 145 ALOGE("lifo deletion failed"); 146 goto bail; 147 } 148 149 /* table should be empty now */ 150 if (irt.capacity() != 0) { 151 ALOGE("lifo del not empty"); 152 goto bail; 153 } 154 155 /* 156 * Add three, remove middle / middle / bottom / top. (Second attempt 157 * to remove middle should fail.) 158 */ 159 DBUG_MSG("+++ START unorder\n"); 160 iref0 = irt.add(cookie, obj0); 161 iref1 = irt.add(cookie, obj1); 162 iref2 = irt.add(cookie, obj2); 163 if (iref0 == NULL || iref1 == NULL || iref2 == NULL) { 164 ALOGE("trivial add3 failed"); 165 goto bail; 166 } 167 168 if (irt.capacity() != 3) { 169 ALOGE("expected 3 entries, found %d", irt.capacity()); 170 goto bail; 171 } 172 173 if (!irt.remove(cookie, iref1) || irt.remove(cookie, iref1)) { 174 ALOGE("unorder deletion1 failed"); 175 goto bail; 176 } 177 178 /* get invalid entry (from hole) */ 179 if (irt.get(iref1) != kInvalidIndirectRefObject) { 180 ALOGE("hole get succeeded unexpectedly"); 181 goto bail; 182 } 183 184 if (!irt.remove(cookie, iref2) || !irt.remove(cookie, iref0)) { 185 ALOGE("unorder deletion2 failed"); 186 goto bail; 187 } 188 189 /* table should be empty now */ 190 if (irt.capacity() != 0) { 191 ALOGE("unorder del not empty"); 192 goto bail; 193 } 194 195 /* 196 * Add four entries. Remove #1, add new entry, verify that table size 197 * is still 4 (i.e. holes are getting filled). Remove #1 and #3, verify 198 * that we delete one and don't hole-compact the other. 199 */ 200 DBUG_MSG("+++ START hole fill\n"); 201 iref0 = irt.add(cookie, obj0); 202 iref1 = irt.add(cookie, obj1); 203 iref2 = irt.add(cookie, obj2); 204 iref3 = irt.add(cookie, obj3); 205 if (iref0 == NULL || iref1 == NULL || iref2 == NULL || iref3 == NULL) { 206 ALOGE("trivial add4 failed"); 207 goto bail; 208 } 209 if (!irt.remove(cookie, iref1)) { 210 ALOGE("remove 1 of 4 failed"); 211 goto bail; 212 } 213 iref1 = irt.add(cookie, obj1); 214 if (irt.capacity() != 4) { 215 ALOGE("hole not filled"); 216 goto bail; 217 } 218 if (!irt.remove(cookie, iref1) || !irt.remove(cookie, iref3)) { 219 ALOGE("remove 1/3 failed"); 220 goto bail; 221 } 222 if (irt.capacity() != 3) { 223 ALOGE("should be 3 after two deletions"); 224 goto bail; 225 } 226 if (!irt.remove(cookie, iref2) || !irt.remove(cookie, iref0)) { 227 ALOGE("remove 2/0 failed"); 228 goto bail; 229 } 230 if (irt.capacity() != 0) { 231 ALOGE("not empty after split remove"); 232 goto bail; 233 } 234 235 /* 236 * Add an entry, remove it, add a new entry, and try to use the original 237 * iref. They have the same slot number but are for different objects. 238 * With the extended checks in place, this should fail. 239 */ 240 DBUG_MSG("+++ START switched\n"); 241 iref0 = irt.add(cookie, obj0); 242 irt.remove(cookie, iref0); 243 iref1 = irt.add(cookie, obj1); 244 if (irt.remove(cookie, iref0)) { 245 ALOGE("mismatched del succeeded (%p vs %p)", iref0, iref1); 246 goto bail; 247 } 248 if (!irt.remove(cookie, iref1)) { 249 ALOGE("switched del failed"); 250 goto bail; 251 } 252 if (irt.capacity() != 0) { 253 ALOGE("switching del not empty"); 254 goto bail; 255 } 256 257 /* 258 * Same as above, but with the same object. A more rigorous checker 259 * (e.g. with slot serialization) will catch this. 260 */ 261 DBUG_MSG("+++ START switched same object\n"); 262 iref0 = irt.add(cookie, obj0); 263 irt.remove(cookie, iref0); 264 iref1 = irt.add(cookie, obj0); 265 if (iref0 != iref1) { 266 /* try 0, should not work */ 267 if (irt.remove(cookie, iref0)) { 268 ALOGE("temporal del succeeded (%p vs %p)", iref0, iref1); 269 goto bail; 270 } 271 } 272 if (!irt.remove(cookie, iref1)) { 273 ALOGE("temporal cleanup failed"); 274 goto bail; 275 } 276 if (irt.capacity() != 0) { 277 ALOGE("temporal del not empty"); 278 goto bail; 279 } 280 281 DBUG_MSG("+++ START null lookup\n"); 282 if (irt.get(NULL) != kInvalidIndirectRefObject) { 283 ALOGE("null lookup succeeded"); 284 goto bail; 285 } 286 287 DBUG_MSG("+++ START stale lookup\n"); 288 iref0 = irt.add(cookie, obj0); 289 irt.remove(cookie, iref0); 290 if (irt.get(iref0) != kInvalidIndirectRefObject) { 291 ALOGE("stale lookup succeeded"); 292 goto bail; 293 } 294 295 /* 296 * Test table overflow. 297 */ 298 DBUG_MSG("+++ START overflow\n"); 299 int i; 300 for (i = 0; i < kTableMax; i++) { 301 manyRefs[i] = irt.add(cookie, obj0); 302 if (manyRefs[i] == NULL) { 303 ALOGE("Failed adding %d of %d", i, kTableMax); 304 goto bail; 305 } 306 } 307 if (irt.add(cookie, obj0) != NULL) { 308 ALOGE("Table overflow succeeded"); 309 goto bail; 310 } 311 if (irt.capacity() != (size_t)kTableMax) { 312 ALOGE("Expected %d entries, found %d", kTableMax, irt.capacity()); 313 goto bail; 314 } 315 irt.dump("table with 20 entries, all filled"); 316 for (i = 0; i < kTableMax-1; i++) { 317 if (!irt.remove(cookie, manyRefs[i])) { 318 ALOGE("multi-remove failed at %d", i); 319 goto bail; 320 } 321 } 322 irt.dump("table with 20 entries, 19 of them holes"); 323 /* because of removal order, should have 20 entries, 19 of them holes */ 324 if (irt.capacity() != (size_t)kTableMax) { 325 ALOGE("Expected %d entries (with holes), found %d", 326 kTableMax, irt.capacity()); 327 goto bail; 328 } 329 if (!irt.remove(cookie, manyRefs[kTableMax-1])) { 330 ALOGE("multi-remove final failed"); 331 goto bail; 332 } 333 if (irt.capacity() != 0) { 334 ALOGE("multi-del not empty"); 335 goto bail; 336 } 337 338 /* Done */ 339 DBUG_MSG("+++ basic test complete\n"); 340 result = true; 341 342 bail: 343 irt.destroy(); 344 return result; 345 } 346 347 static bool performanceTest() 348 { 349 static const int kTableMax = 100; 350 IndirectRefTable irt; 351 IndirectRef manyRefs[kTableMax]; 352 ClassObject* clazz = dvmFindClass("Ljava/lang/Object;", NULL); 353 Object* obj0 = dvmAllocObject(clazz, ALLOC_DONT_TRACK); 354 const u4 cookie = IRT_FIRST_SEGMENT; 355 const int kLoops = 100000; 356 Stopwatch stopwatch; 357 358 DBUG_MSG("+++ START performance\n"); 359 360 if (!irt.init(kTableMax, kTableMax, kIndirectKindGlobal)) { 361 return false; 362 } 363 364 stopwatch.reset(); 365 for (int loop = 0; loop < kLoops; loop++) { 366 for (int i = 0; i < kTableMax; i++) { 367 manyRefs[i] = irt.add(cookie, obj0); 368 } 369 for (int i = 0; i < kTableMax; i++) { 370 irt.remove(cookie, manyRefs[i]); 371 } 372 } 373 DBUG_MSG("Add/remove %d objects FIFO order, %d iterations, %0.3fms / iteration", 374 kTableMax, kLoops, stopwatch.elapsedSeconds() * 1000 / kLoops); 375 376 stopwatch.reset(); 377 for (int loop = 0; loop < kLoops; loop++) { 378 for (int i = 0; i < kTableMax; i++) { 379 manyRefs[i] = irt.add(cookie, obj0); 380 } 381 for (int i = kTableMax; i-- > 0; ) { 382 irt.remove(cookie, manyRefs[i]); 383 } 384 } 385 DBUG_MSG("Add/remove %d objects LIFO order, %d iterations, %0.3fms / iteration", 386 kTableMax, kLoops, stopwatch.elapsedSeconds() * 1000 / kLoops); 387 388 for (int i = 0; i < kTableMax; i++) { 389 manyRefs[i] = irt.add(cookie, obj0); 390 } 391 stopwatch.reset(); 392 for (int loop = 0; loop < kLoops; loop++) { 393 for (int i = 0; i < kTableMax; i++) { 394 irt.get(manyRefs[i]); 395 } 396 } 397 DBUG_MSG("Get %d objects, %d iterations, %0.3fms / iteration", 398 kTableMax, kLoops, stopwatch.elapsedSeconds() * 1000 / kLoops); 399 for (int i = kTableMax; i-- > 0; ) { 400 irt.remove(cookie, manyRefs[i]); 401 } 402 403 irt.destroy(); 404 return true; 405 } 406 407 /* 408 * Some quick tests. 409 */ 410 bool dvmTestIndirectRefTable() 411 { 412 if (!basicTest()) { 413 ALOGE("IRT basic test failed"); 414 return false; 415 } 416 417 if (!performanceTest()) { 418 ALOGE("IRT performance test failed"); 419 return false; 420 } 421 422 return true; 423 } 424 425 #endif /*NDEBUG*/ 426
