1 /* 2 * Copyright (C) 2015 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 "mod_union_table-inl.h" 18 19 #include "class_linker-inl.h" 20 #include "common_runtime_test.h" 21 #include "gc/space/space-inl.h" 22 #include "mirror/array-inl.h" 23 #include "space_bitmap-inl.h" 24 #include "thread-inl.h" 25 #include "thread_list.h" 26 27 namespace art { 28 namespace gc { 29 namespace accounting { 30 31 class ModUnionTableFactory { 32 public: 33 enum TableType { 34 kTableTypeCardCache, 35 kTableTypeReferenceCache, 36 kTableTypeCount, // Number of values in the enum. 37 }; 38 39 // Target space is ignored for the card cache implementation. 40 static ModUnionTable* Create( 41 TableType type, space::ContinuousSpace* space, space::ContinuousSpace* target_space); 42 }; 43 44 class ModUnionTableTest : public CommonRuntimeTest { 45 public: 46 ModUnionTableTest() : java_lang_object_array_(nullptr) { 47 } 48 mirror::ObjectArray<mirror::Object>* AllocObjectArray( 49 Thread* self, space::ContinuousMemMapAllocSpace* space, size_t component_count) 50 SHARED_REQUIRES(Locks::mutator_lock_) { 51 auto* klass = GetObjectArrayClass(self, space); 52 const size_t size = mirror::ComputeArraySize(component_count, 2); 53 size_t bytes_allocated = 0, bytes_tl_bulk_allocated; 54 auto* obj = down_cast<mirror::ObjectArray<mirror::Object>*>( 55 space->Alloc(self, size, &bytes_allocated, nullptr, &bytes_tl_bulk_allocated)); 56 if (obj != nullptr) { 57 obj->SetClass(klass); 58 obj->SetLength(static_cast<int32_t>(component_count)); 59 space->GetLiveBitmap()->Set(obj); 60 EXPECT_GE(bytes_allocated, size); 61 } 62 return obj; 63 } 64 void ResetClass() { 65 java_lang_object_array_ = nullptr; 66 } 67 void RunTest(ModUnionTableFactory::TableType type); 68 69 private: 70 mirror::Class* GetObjectArrayClass(Thread* self, space::ContinuousMemMapAllocSpace* space) 71 SHARED_REQUIRES(Locks::mutator_lock_) { 72 if (java_lang_object_array_ == nullptr) { 73 java_lang_object_array_ = 74 Runtime::Current()->GetClassLinker()->GetClassRoot(ClassLinker::kObjectArrayClass); 75 // Since the test doesn't have an image, the class of the object array keeps cards live 76 // inside the card cache mod-union table and causes the check 77 // ASSERT_FALSE(table->ContainsCardFor(reinterpret_cast<uintptr_t>(obj3))); 78 // to fail since the class ends up keeping the card dirty. To get around this, we make a fake 79 // copy of the class in the same space that we are allocating in. 80 DCHECK(java_lang_object_array_ != nullptr); 81 const size_t class_size = java_lang_object_array_->GetClassSize(); 82 size_t bytes_allocated = 0, bytes_tl_bulk_allocated; 83 auto* klass = down_cast<mirror::Class*>(space->Alloc(self, class_size, &bytes_allocated, 84 nullptr, 85 &bytes_tl_bulk_allocated)); 86 DCHECK(klass != nullptr); 87 memcpy(klass, java_lang_object_array_, class_size); 88 Runtime::Current()->GetHeap()->GetCardTable()->MarkCard(klass); 89 java_lang_object_array_ = klass; 90 } 91 return java_lang_object_array_; 92 } 93 mirror::Class* java_lang_object_array_; 94 }; 95 96 // Collect visited objects into container. 97 class CollectVisitedVisitor : public MarkObjectVisitor { 98 public: 99 explicit CollectVisitedVisitor(std::set<mirror::Object*>* out) : out_(out) {} 100 virtual void MarkHeapReference(mirror::HeapReference<mirror::Object>* ref) OVERRIDE 101 SHARED_REQUIRES(Locks::mutator_lock_) { 102 DCHECK(ref != nullptr); 103 MarkObject(ref->AsMirrorPtr()); 104 } 105 virtual mirror::Object* MarkObject(mirror::Object* obj) OVERRIDE 106 SHARED_REQUIRES(Locks::mutator_lock_) { 107 DCHECK(obj != nullptr); 108 out_->insert(obj); 109 return obj; 110 } 111 112 private: 113 std::set<mirror::Object*>* const out_; 114 }; 115 116 // A mod union table that only holds references to a specified target space. 117 class ModUnionTableRefCacheToSpace : public ModUnionTableReferenceCache { 118 public: 119 explicit ModUnionTableRefCacheToSpace( 120 const std::string& name, Heap* heap, space::ContinuousSpace* space, 121 space::ContinuousSpace* target_space) 122 : ModUnionTableReferenceCache(name, heap, space), target_space_(target_space) {} 123 124 bool ShouldAddReference(const mirror::Object* ref) const OVERRIDE { 125 return target_space_->HasAddress(ref); 126 } 127 128 private: 129 space::ContinuousSpace* const target_space_; 130 }; 131 132 std::ostream& operator<<(std::ostream& oss, ModUnionTableFactory::TableType type) { 133 switch (type) { 134 case ModUnionTableFactory::kTableTypeCardCache: { 135 oss << "CardCache"; 136 break; 137 } 138 case ModUnionTableFactory::kTableTypeReferenceCache: { 139 oss << "ReferenceCache"; 140 break; 141 } 142 default: { 143 UNIMPLEMENTED(FATAL) << static_cast<size_t>(type); 144 } 145 } 146 return oss; 147 } 148 149 ModUnionTable* ModUnionTableFactory::Create( 150 TableType type, space::ContinuousSpace* space, space::ContinuousSpace* target_space) { 151 std::ostringstream name; 152 name << "Mod union table: " << type; 153 switch (type) { 154 case kTableTypeCardCache: { 155 return new ModUnionTableCardCache(name.str(), Runtime::Current()->GetHeap(), space); 156 } 157 case kTableTypeReferenceCache: { 158 return new ModUnionTableRefCacheToSpace(name.str(), Runtime::Current()->GetHeap(), space, 159 target_space); 160 } 161 default: { 162 UNIMPLEMENTED(FATAL) << "Invalid type " << type; 163 } 164 } 165 return nullptr; 166 } 167 168 TEST_F(ModUnionTableTest, TestCardCache) { 169 RunTest(ModUnionTableFactory::kTableTypeCardCache); 170 } 171 172 TEST_F(ModUnionTableTest, TestReferenceCache) { 173 RunTest(ModUnionTableFactory::kTableTypeReferenceCache); 174 } 175 176 void ModUnionTableTest::RunTest(ModUnionTableFactory::TableType type) { 177 Thread* const self = Thread::Current(); 178 ScopedObjectAccess soa(self); 179 Runtime* const runtime = Runtime::Current(); 180 gc::Heap* const heap = runtime->GetHeap(); 181 // Use non moving space since moving GC don't necessarily have a primary free list space. 182 auto* space = heap->GetNonMovingSpace(); 183 ResetClass(); 184 // Create another space that we can put references in. 185 std::unique_ptr<space::DlMallocSpace> other_space(space::DlMallocSpace::Create( 186 "other space", 128 * KB, 4 * MB, 4 * MB, nullptr, false)); 187 ASSERT_TRUE(other_space.get() != nullptr); 188 { 189 ScopedThreadSuspension sts(self, kSuspended); 190 ScopedSuspendAll ssa("Add image space"); 191 heap->AddSpace(other_space.get()); 192 } 193 std::unique_ptr<ModUnionTable> table(ModUnionTableFactory::Create( 194 type, space, other_space.get())); 195 ASSERT_TRUE(table.get() != nullptr); 196 // Create some fake objects and put the main space and dirty cards in the non moving space. 197 auto* obj1 = AllocObjectArray(self, space, CardTable::kCardSize); 198 ASSERT_TRUE(obj1 != nullptr); 199 auto* obj2 = AllocObjectArray(self, space, CardTable::kCardSize); 200 ASSERT_TRUE(obj2 != nullptr); 201 auto* obj3 = AllocObjectArray(self, space, CardTable::kCardSize); 202 ASSERT_TRUE(obj3 != nullptr); 203 auto* obj4 = AllocObjectArray(self, space, CardTable::kCardSize); 204 ASSERT_TRUE(obj4 != nullptr); 205 // Dirty some cards. 206 obj1->Set(0, obj2); 207 obj2->Set(0, obj3); 208 obj3->Set(0, obj4); 209 obj4->Set(0, obj1); 210 // Dirty some more cards to objects in another space. 211 auto* other_space_ref1 = AllocObjectArray(self, other_space.get(), CardTable::kCardSize); 212 ASSERT_TRUE(other_space_ref1 != nullptr); 213 auto* other_space_ref2 = AllocObjectArray(self, other_space.get(), CardTable::kCardSize); 214 ASSERT_TRUE(other_space_ref2 != nullptr); 215 obj1->Set(1, other_space_ref1); 216 obj2->Set(3, other_space_ref2); 217 table->ClearCards(); 218 std::set<mirror::Object*> visited_before; 219 CollectVisitedVisitor collector_before(&visited_before); 220 table->UpdateAndMarkReferences(&collector_before); 221 // Check that we visited all the references in other spaces only. 222 ASSERT_GE(visited_before.size(), 2u); 223 ASSERT_TRUE(visited_before.find(other_space_ref1) != visited_before.end()); 224 ASSERT_TRUE(visited_before.find(other_space_ref2) != visited_before.end()); 225 // Verify that all the other references were visited. 226 // obj1, obj2 cards should still be in mod union table since they have references to other 227 // spaces. 228 ASSERT_TRUE(table->ContainsCardFor(reinterpret_cast<uintptr_t>(obj1))); 229 ASSERT_TRUE(table->ContainsCardFor(reinterpret_cast<uintptr_t>(obj2))); 230 // obj3, obj4 don't have a reference to any object in the other space, their cards should have 231 // been removed from the mod union table during UpdateAndMarkReferences. 232 ASSERT_FALSE(table->ContainsCardFor(reinterpret_cast<uintptr_t>(obj3))); 233 ASSERT_FALSE(table->ContainsCardFor(reinterpret_cast<uintptr_t>(obj4))); 234 { 235 // Currently no-op, make sure it still works however. 236 ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_); 237 table->Verify(); 238 } 239 // Verify that dump doesn't crash. 240 std::ostringstream oss; 241 table->Dump(oss); 242 // Set all the cards, then verify. 243 table->SetCards(); 244 // TODO: Check that the cards are actually set. 245 for (auto* ptr = space->Begin(); ptr < AlignUp(space->End(), CardTable::kCardSize); 246 ptr += CardTable::kCardSize) { 247 ASSERT_TRUE(table->ContainsCardFor(reinterpret_cast<uintptr_t>(ptr))); 248 } 249 // Visit again and make sure the cards got cleared back to their sane state. 250 std::set<mirror::Object*> visited_after; 251 CollectVisitedVisitor collector_after(&visited_after); 252 table->UpdateAndMarkReferences(&collector_after); 253 // Check that we visited a superset after. 254 for (auto* obj : visited_before) { 255 ASSERT_TRUE(visited_after.find(obj) != visited_after.end()) << obj; 256 } 257 // Verify that the dump still works. 258 std::ostringstream oss2; 259 table->Dump(oss2); 260 // Remove the space we added so it doesn't persist to the next test. 261 ScopedThreadSuspension sts(self, kSuspended); 262 ScopedSuspendAll ssa("Add image space"); 263 heap->RemoveSpace(other_space.get()); 264 } 265 266 } // namespace accounting 267 } // namespace gc 268 } // namespace art 269