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 #include "indirect_reference_table-inl.h" 18 19 #include "android-base/stringprintf.h" 20 21 #include "class_linker-inl.h" 22 #include "common_runtime_test.h" 23 #include "mirror/object-inl.h" 24 #include "scoped_thread_state_change-inl.h" 25 26 namespace art { 27 28 using android::base::StringPrintf; 29 30 class IndirectReferenceTableTest : public CommonRuntimeTest {}; 31 32 static void CheckDump(IndirectReferenceTable* irt, size_t num_objects, size_t num_unique) 33 REQUIRES_SHARED(Locks::mutator_lock_) { 34 std::ostringstream oss; 35 irt->Dump(oss); 36 if (num_objects == 0) { 37 EXPECT_EQ(oss.str().find("java.lang.Object"), std::string::npos) << oss.str(); 38 } else if (num_objects == 1) { 39 EXPECT_NE(oss.str().find("1 of java.lang.Object"), std::string::npos) << oss.str(); 40 } else { 41 EXPECT_NE(oss.str().find(StringPrintf("%zd of java.lang.Object (%zd unique instances)", 42 num_objects, num_unique)), 43 std::string::npos) 44 << "\n Expected number of objects: " << num_objects 45 << "\n Expected unique objects: " << num_unique << "\n" 46 << oss.str(); 47 } 48 } 49 50 TEST_F(IndirectReferenceTableTest, BasicTest) { 51 // This will lead to error messages in the log. 52 ScopedLogSeverity sls(LogSeverity::FATAL); 53 54 ScopedObjectAccess soa(Thread::Current()); 55 static const size_t kTableMax = 20; 56 std::string error_msg; 57 IndirectReferenceTable irt(kTableMax, 58 kGlobal, 59 IndirectReferenceTable::ResizableCapacity::kNo, 60 &error_msg); 61 ASSERT_TRUE(irt.IsValid()) << error_msg; 62 63 mirror::Class* c = class_linker_->FindSystemClass(soa.Self(), "Ljava/lang/Object;"); 64 StackHandleScope<4> hs(soa.Self()); 65 ASSERT_TRUE(c != nullptr); 66 Handle<mirror::Object> obj0 = hs.NewHandle(c->AllocObject(soa.Self())); 67 ASSERT_TRUE(obj0 != nullptr); 68 Handle<mirror::Object> obj1 = hs.NewHandle(c->AllocObject(soa.Self())); 69 ASSERT_TRUE(obj1 != nullptr); 70 Handle<mirror::Object> obj2 = hs.NewHandle(c->AllocObject(soa.Self())); 71 ASSERT_TRUE(obj2 != nullptr); 72 Handle<mirror::Object> obj3 = hs.NewHandle(c->AllocObject(soa.Self())); 73 ASSERT_TRUE(obj3 != nullptr); 74 75 const IRTSegmentState cookie = kIRTFirstSegment; 76 77 CheckDump(&irt, 0, 0); 78 79 IndirectRef iref0 = (IndirectRef) 0x11110; 80 EXPECT_FALSE(irt.Remove(cookie, iref0)) << "unexpectedly successful removal"; 81 82 // Add three, check, remove in the order in which they were added. 83 iref0 = irt.Add(cookie, obj0.Get()); 84 EXPECT_TRUE(iref0 != nullptr); 85 CheckDump(&irt, 1, 1); 86 IndirectRef iref1 = irt.Add(cookie, obj1.Get()); 87 EXPECT_TRUE(iref1 != nullptr); 88 CheckDump(&irt, 2, 2); 89 IndirectRef iref2 = irt.Add(cookie, obj2.Get()); 90 EXPECT_TRUE(iref2 != nullptr); 91 CheckDump(&irt, 3, 3); 92 93 EXPECT_OBJ_PTR_EQ(obj0.Get(), irt.Get(iref0)); 94 EXPECT_OBJ_PTR_EQ(obj1.Get(), irt.Get(iref1)); 95 EXPECT_OBJ_PTR_EQ(obj2.Get(), irt.Get(iref2)); 96 97 EXPECT_TRUE(irt.Remove(cookie, iref0)); 98 CheckDump(&irt, 2, 2); 99 EXPECT_TRUE(irt.Remove(cookie, iref1)); 100 CheckDump(&irt, 1, 1); 101 EXPECT_TRUE(irt.Remove(cookie, iref2)); 102 CheckDump(&irt, 0, 0); 103 104 // Table should be empty now. 105 EXPECT_EQ(0U, irt.Capacity()); 106 107 // Get invalid entry (off the end of the list). 108 EXPECT_TRUE(irt.Get(iref0) == nullptr); 109 110 // Add three, remove in the opposite order. 111 iref0 = irt.Add(cookie, obj0.Get()); 112 EXPECT_TRUE(iref0 != nullptr); 113 iref1 = irt.Add(cookie, obj1.Get()); 114 EXPECT_TRUE(iref1 != nullptr); 115 iref2 = irt.Add(cookie, obj2.Get()); 116 EXPECT_TRUE(iref2 != nullptr); 117 CheckDump(&irt, 3, 3); 118 119 ASSERT_TRUE(irt.Remove(cookie, iref2)); 120 CheckDump(&irt, 2, 2); 121 ASSERT_TRUE(irt.Remove(cookie, iref1)); 122 CheckDump(&irt, 1, 1); 123 ASSERT_TRUE(irt.Remove(cookie, iref0)); 124 CheckDump(&irt, 0, 0); 125 126 // Table should be empty now. 127 ASSERT_EQ(0U, irt.Capacity()); 128 129 // Add three, remove middle / middle / bottom / top. (Second attempt 130 // to remove middle should fail.) 131 iref0 = irt.Add(cookie, obj0.Get()); 132 EXPECT_TRUE(iref0 != nullptr); 133 iref1 = irt.Add(cookie, obj1.Get()); 134 EXPECT_TRUE(iref1 != nullptr); 135 iref2 = irt.Add(cookie, obj2.Get()); 136 EXPECT_TRUE(iref2 != nullptr); 137 CheckDump(&irt, 3, 3); 138 139 ASSERT_EQ(3U, irt.Capacity()); 140 141 ASSERT_TRUE(irt.Remove(cookie, iref1)); 142 CheckDump(&irt, 2, 2); 143 ASSERT_FALSE(irt.Remove(cookie, iref1)); 144 CheckDump(&irt, 2, 2); 145 146 // Get invalid entry (from hole). 147 EXPECT_TRUE(irt.Get(iref1) == nullptr); 148 149 ASSERT_TRUE(irt.Remove(cookie, iref2)); 150 CheckDump(&irt, 1, 1); 151 ASSERT_TRUE(irt.Remove(cookie, iref0)); 152 CheckDump(&irt, 0, 0); 153 154 // Table should be empty now. 155 ASSERT_EQ(0U, irt.Capacity()); 156 157 // Add four entries. Remove #1, add new entry, verify that table size 158 // is still 4 (i.e. holes are getting filled). Remove #1 and #3, verify 159 // that we delete one and don't hole-compact the other. 160 iref0 = irt.Add(cookie, obj0.Get()); 161 EXPECT_TRUE(iref0 != nullptr); 162 iref1 = irt.Add(cookie, obj1.Get()); 163 EXPECT_TRUE(iref1 != nullptr); 164 iref2 = irt.Add(cookie, obj2.Get()); 165 EXPECT_TRUE(iref2 != nullptr); 166 IndirectRef iref3 = irt.Add(cookie, obj3.Get()); 167 EXPECT_TRUE(iref3 != nullptr); 168 CheckDump(&irt, 4, 4); 169 170 ASSERT_TRUE(irt.Remove(cookie, iref1)); 171 CheckDump(&irt, 3, 3); 172 173 iref1 = irt.Add(cookie, obj1.Get()); 174 EXPECT_TRUE(iref1 != nullptr); 175 176 ASSERT_EQ(4U, irt.Capacity()) << "hole not filled"; 177 CheckDump(&irt, 4, 4); 178 179 ASSERT_TRUE(irt.Remove(cookie, iref1)); 180 CheckDump(&irt, 3, 3); 181 ASSERT_TRUE(irt.Remove(cookie, iref3)); 182 CheckDump(&irt, 2, 2); 183 184 ASSERT_EQ(3U, irt.Capacity()) << "should be 3 after two deletions"; 185 186 ASSERT_TRUE(irt.Remove(cookie, iref2)); 187 CheckDump(&irt, 1, 1); 188 ASSERT_TRUE(irt.Remove(cookie, iref0)); 189 CheckDump(&irt, 0, 0); 190 191 ASSERT_EQ(0U, irt.Capacity()) << "not empty after split remove"; 192 193 // Add an entry, remove it, add a new entry, and try to use the original 194 // iref. They have the same slot number but are for different objects. 195 // With the extended checks in place, this should fail. 196 iref0 = irt.Add(cookie, obj0.Get()); 197 EXPECT_TRUE(iref0 != nullptr); 198 CheckDump(&irt, 1, 1); 199 ASSERT_TRUE(irt.Remove(cookie, iref0)); 200 CheckDump(&irt, 0, 0); 201 iref1 = irt.Add(cookie, obj1.Get()); 202 EXPECT_TRUE(iref1 != nullptr); 203 CheckDump(&irt, 1, 1); 204 ASSERT_FALSE(irt.Remove(cookie, iref0)) << "mismatched del succeeded"; 205 CheckDump(&irt, 1, 1); 206 ASSERT_TRUE(irt.Remove(cookie, iref1)) << "switched del failed"; 207 ASSERT_EQ(0U, irt.Capacity()) << "switching del not empty"; 208 CheckDump(&irt, 0, 0); 209 210 // Same as above, but with the same object. A more rigorous checker 211 // (e.g. with slot serialization) will catch this. 212 iref0 = irt.Add(cookie, obj0.Get()); 213 EXPECT_TRUE(iref0 != nullptr); 214 CheckDump(&irt, 1, 1); 215 ASSERT_TRUE(irt.Remove(cookie, iref0)); 216 CheckDump(&irt, 0, 0); 217 iref1 = irt.Add(cookie, obj0.Get()); 218 EXPECT_TRUE(iref1 != nullptr); 219 CheckDump(&irt, 1, 1); 220 if (iref0 != iref1) { 221 // Try 0, should not work. 222 ASSERT_FALSE(irt.Remove(cookie, iref0)) << "temporal del succeeded"; 223 } 224 ASSERT_TRUE(irt.Remove(cookie, iref1)) << "temporal cleanup failed"; 225 ASSERT_EQ(0U, irt.Capacity()) << "temporal del not empty"; 226 CheckDump(&irt, 0, 0); 227 228 // null isn't a valid iref. 229 ASSERT_TRUE(irt.Get(nullptr) == nullptr); 230 231 // Stale lookup. 232 iref0 = irt.Add(cookie, obj0.Get()); 233 EXPECT_TRUE(iref0 != nullptr); 234 CheckDump(&irt, 1, 1); 235 ASSERT_TRUE(irt.Remove(cookie, iref0)); 236 EXPECT_TRUE(irt.Get(iref0) == nullptr) << "stale lookup succeeded"; 237 CheckDump(&irt, 0, 0); 238 239 // Test table resizing. 240 // These ones fit... 241 static const size_t kTableInitial = kTableMax / 2; 242 IndirectRef manyRefs[kTableInitial]; 243 for (size_t i = 0; i < kTableInitial; i++) { 244 manyRefs[i] = irt.Add(cookie, obj0.Get()); 245 ASSERT_TRUE(manyRefs[i] != nullptr) << "Failed adding " << i; 246 CheckDump(&irt, i + 1, 1); 247 } 248 // ...this one causes overflow. 249 iref0 = irt.Add(cookie, obj0.Get()); 250 ASSERT_TRUE(iref0 != nullptr); 251 ASSERT_EQ(kTableInitial + 1, irt.Capacity()); 252 CheckDump(&irt, kTableInitial + 1, 1); 253 254 for (size_t i = 0; i < kTableInitial; i++) { 255 ASSERT_TRUE(irt.Remove(cookie, manyRefs[i])) << "failed removing " << i; 256 CheckDump(&irt, kTableInitial - i, 1); 257 } 258 // Because of removal order, should have 11 entries, 10 of them holes. 259 ASSERT_EQ(kTableInitial + 1, irt.Capacity()); 260 261 ASSERT_TRUE(irt.Remove(cookie, iref0)) << "multi-remove final failed"; 262 263 ASSERT_EQ(0U, irt.Capacity()) << "multi-del not empty"; 264 CheckDump(&irt, 0, 0); 265 } 266 267 TEST_F(IndirectReferenceTableTest, Holes) { 268 // Test the explicitly named cases from the IRT implementation: 269 // 270 // 1) Segment with holes (current_num_holes_ > 0), push new segment, add/remove reference 271 // 2) Segment with holes (current_num_holes_ > 0), pop segment, add/remove reference 272 // 3) Segment with holes (current_num_holes_ > 0), push new segment, pop segment, add/remove 273 // reference 274 // 4) Empty segment, push new segment, create a hole, pop a segment, add/remove a reference 275 // 5) Base segment, push new segment, create a hole, pop a segment, push new segment, add/remove 276 // reference 277 278 ScopedObjectAccess soa(Thread::Current()); 279 static const size_t kTableMax = 10; 280 281 mirror::Class* c = class_linker_->FindSystemClass(soa.Self(), "Ljava/lang/Object;"); 282 StackHandleScope<5> hs(soa.Self()); 283 ASSERT_TRUE(c != nullptr); 284 Handle<mirror::Object> obj0 = hs.NewHandle(c->AllocObject(soa.Self())); 285 ASSERT_TRUE(obj0 != nullptr); 286 Handle<mirror::Object> obj1 = hs.NewHandle(c->AllocObject(soa.Self())); 287 ASSERT_TRUE(obj1 != nullptr); 288 Handle<mirror::Object> obj2 = hs.NewHandle(c->AllocObject(soa.Self())); 289 ASSERT_TRUE(obj2 != nullptr); 290 Handle<mirror::Object> obj3 = hs.NewHandle(c->AllocObject(soa.Self())); 291 ASSERT_TRUE(obj3 != nullptr); 292 Handle<mirror::Object> obj4 = hs.NewHandle(c->AllocObject(soa.Self())); 293 ASSERT_TRUE(obj4 != nullptr); 294 295 std::string error_msg; 296 297 // 1) Segment with holes (current_num_holes_ > 0), push new segment, add/remove reference. 298 { 299 IndirectReferenceTable irt(kTableMax, 300 kGlobal, 301 IndirectReferenceTable::ResizableCapacity::kNo, 302 &error_msg); 303 ASSERT_TRUE(irt.IsValid()) << error_msg; 304 305 const IRTSegmentState cookie0 = kIRTFirstSegment; 306 307 CheckDump(&irt, 0, 0); 308 309 IndirectRef iref0 = irt.Add(cookie0, obj0.Get()); 310 IndirectRef iref1 = irt.Add(cookie0, obj1.Get()); 311 IndirectRef iref2 = irt.Add(cookie0, obj2.Get()); 312 313 EXPECT_TRUE(irt.Remove(cookie0, iref1)); 314 315 // New segment. 316 const IRTSegmentState cookie1 = irt.GetSegmentState(); 317 318 IndirectRef iref3 = irt.Add(cookie1, obj3.Get()); 319 320 // Must not have filled the previous hole. 321 EXPECT_EQ(irt.Capacity(), 4u); 322 EXPECT_TRUE(irt.Get(iref1) == nullptr); 323 CheckDump(&irt, 3, 3); 324 325 UNUSED(iref0, iref1, iref2, iref3); 326 } 327 328 // 2) Segment with holes (current_num_holes_ > 0), pop segment, add/remove reference 329 { 330 IndirectReferenceTable irt(kTableMax, 331 kGlobal, 332 IndirectReferenceTable::ResizableCapacity::kNo, 333 &error_msg); 334 ASSERT_TRUE(irt.IsValid()) << error_msg; 335 336 const IRTSegmentState cookie0 = kIRTFirstSegment; 337 338 CheckDump(&irt, 0, 0); 339 340 IndirectRef iref0 = irt.Add(cookie0, obj0.Get()); 341 342 // New segment. 343 const IRTSegmentState cookie1 = irt.GetSegmentState(); 344 345 IndirectRef iref1 = irt.Add(cookie1, obj1.Get()); 346 IndirectRef iref2 = irt.Add(cookie1, obj2.Get()); 347 IndirectRef iref3 = irt.Add(cookie1, obj3.Get()); 348 349 EXPECT_TRUE(irt.Remove(cookie1, iref2)); 350 351 // Pop segment. 352 irt.SetSegmentState(cookie1); 353 354 IndirectRef iref4 = irt.Add(cookie1, obj4.Get()); 355 356 EXPECT_EQ(irt.Capacity(), 2u); 357 EXPECT_TRUE(irt.Get(iref2) == nullptr); 358 CheckDump(&irt, 2, 2); 359 360 UNUSED(iref0, iref1, iref2, iref3, iref4); 361 } 362 363 // 3) Segment with holes (current_num_holes_ > 0), push new segment, pop segment, add/remove 364 // reference. 365 { 366 IndirectReferenceTable irt(kTableMax, 367 kGlobal, 368 IndirectReferenceTable::ResizableCapacity::kNo, 369 &error_msg); 370 ASSERT_TRUE(irt.IsValid()) << error_msg; 371 372 const IRTSegmentState cookie0 = kIRTFirstSegment; 373 374 CheckDump(&irt, 0, 0); 375 376 IndirectRef iref0 = irt.Add(cookie0, obj0.Get()); 377 378 // New segment. 379 const IRTSegmentState cookie1 = irt.GetSegmentState(); 380 381 IndirectRef iref1 = irt.Add(cookie1, obj1.Get()); 382 IndirectRef iref2 = irt.Add(cookie1, obj2.Get()); 383 384 EXPECT_TRUE(irt.Remove(cookie1, iref1)); 385 386 // New segment. 387 const IRTSegmentState cookie2 = irt.GetSegmentState(); 388 389 IndirectRef iref3 = irt.Add(cookie2, obj3.Get()); 390 391 // Pop segment. 392 irt.SetSegmentState(cookie2); 393 394 IndirectRef iref4 = irt.Add(cookie1, obj4.Get()); 395 396 EXPECT_EQ(irt.Capacity(), 3u); 397 EXPECT_TRUE(irt.Get(iref1) == nullptr); 398 CheckDump(&irt, 3, 3); 399 400 UNUSED(iref0, iref1, iref2, iref3, iref4); 401 } 402 403 // 4) Empty segment, push new segment, create a hole, pop a segment, add/remove a reference. 404 { 405 IndirectReferenceTable irt(kTableMax, 406 kGlobal, 407 IndirectReferenceTable::ResizableCapacity::kNo, 408 &error_msg); 409 ASSERT_TRUE(irt.IsValid()) << error_msg; 410 411 const IRTSegmentState cookie0 = kIRTFirstSegment; 412 413 CheckDump(&irt, 0, 0); 414 415 IndirectRef iref0 = irt.Add(cookie0, obj0.Get()); 416 417 // New segment. 418 const IRTSegmentState cookie1 = irt.GetSegmentState(); 419 420 IndirectRef iref1 = irt.Add(cookie1, obj1.Get()); 421 EXPECT_TRUE(irt.Remove(cookie1, iref1)); 422 423 // Emptied segment, push new one. 424 const IRTSegmentState cookie2 = irt.GetSegmentState(); 425 426 IndirectRef iref2 = irt.Add(cookie1, obj1.Get()); 427 IndirectRef iref3 = irt.Add(cookie1, obj2.Get()); 428 IndirectRef iref4 = irt.Add(cookie1, obj3.Get()); 429 430 EXPECT_TRUE(irt.Remove(cookie1, iref3)); 431 432 // Pop segment. 433 UNUSED(cookie2); 434 irt.SetSegmentState(cookie1); 435 436 IndirectRef iref5 = irt.Add(cookie1, obj4.Get()); 437 438 EXPECT_EQ(irt.Capacity(), 2u); 439 EXPECT_TRUE(irt.Get(iref3) == nullptr); 440 CheckDump(&irt, 2, 2); 441 442 UNUSED(iref0, iref1, iref2, iref3, iref4, iref5); 443 } 444 445 // 5) Base segment, push new segment, create a hole, pop a segment, push new segment, add/remove 446 // reference 447 { 448 IndirectReferenceTable irt(kTableMax, 449 kGlobal, 450 IndirectReferenceTable::ResizableCapacity::kNo, 451 &error_msg); 452 ASSERT_TRUE(irt.IsValid()) << error_msg; 453 454 const IRTSegmentState cookie0 = kIRTFirstSegment; 455 456 CheckDump(&irt, 0, 0); 457 458 IndirectRef iref0 = irt.Add(cookie0, obj0.Get()); 459 460 // New segment. 461 const IRTSegmentState cookie1 = irt.GetSegmentState(); 462 463 IndirectRef iref1 = irt.Add(cookie1, obj1.Get()); 464 IndirectRef iref2 = irt.Add(cookie1, obj1.Get()); 465 IndirectRef iref3 = irt.Add(cookie1, obj2.Get()); 466 467 EXPECT_TRUE(irt.Remove(cookie1, iref2)); 468 469 // Pop segment. 470 irt.SetSegmentState(cookie1); 471 472 // Push segment. 473 const IRTSegmentState cookie1_second = irt.GetSegmentState(); 474 UNUSED(cookie1_second); 475 476 IndirectRef iref4 = irt.Add(cookie1, obj3.Get()); 477 478 EXPECT_EQ(irt.Capacity(), 2u); 479 EXPECT_TRUE(irt.Get(iref3) == nullptr); 480 CheckDump(&irt, 2, 2); 481 482 UNUSED(iref0, iref1, iref2, iref3, iref4); 483 } 484 } 485 486 TEST_F(IndirectReferenceTableTest, Resize) { 487 ScopedObjectAccess soa(Thread::Current()); 488 static const size_t kTableMax = 512; 489 490 mirror::Class* c = class_linker_->FindSystemClass(soa.Self(), "Ljava/lang/Object;"); 491 StackHandleScope<1> hs(soa.Self()); 492 ASSERT_TRUE(c != nullptr); 493 Handle<mirror::Object> obj0 = hs.NewHandle(c->AllocObject(soa.Self())); 494 ASSERT_TRUE(obj0 != nullptr); 495 496 std::string error_msg; 497 IndirectReferenceTable irt(kTableMax, 498 kLocal, 499 IndirectReferenceTable::ResizableCapacity::kYes, 500 &error_msg); 501 ASSERT_TRUE(irt.IsValid()) << error_msg; 502 503 CheckDump(&irt, 0, 0); 504 const IRTSegmentState cookie = kIRTFirstSegment; 505 506 for (size_t i = 0; i != kTableMax + 1; ++i) { 507 irt.Add(cookie, obj0.Get()); 508 } 509 510 EXPECT_EQ(irt.Capacity(), kTableMax + 1); 511 } 512 513 } // namespace art 514
