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-current-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 REQUIRES_SHARED(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 REQUIRES_SHARED(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, 101 bool do_atomic_update ATTRIBUTE_UNUSED) OVERRIDE 102 REQUIRES_SHARED(Locks::mutator_lock_) { 103 DCHECK(ref != nullptr); 104 MarkObject(ref->AsMirrorPtr()); 105 } 106 virtual mirror::Object* MarkObject(mirror::Object* obj) OVERRIDE 107 REQUIRES_SHARED(Locks::mutator_lock_) { 108 DCHECK(obj != nullptr); 109 out_->insert(obj); 110 return obj; 111 } 112 113 private: 114 std::set<mirror::Object*>* const out_; 115 }; 116 117 // A mod union table that only holds references to a specified target space. 118 class ModUnionTableRefCacheToSpace : public ModUnionTableReferenceCache { 119 public: 120 explicit ModUnionTableRefCacheToSpace( 121 const std::string& name, Heap* heap, space::ContinuousSpace* space, 122 space::ContinuousSpace* target_space) 123 : ModUnionTableReferenceCache(name, heap, space), target_space_(target_space) {} 124 125 bool ShouldAddReference(const mirror::Object* ref) const OVERRIDE { 126 return target_space_->HasAddress(ref); 127 } 128 129 private: 130 space::ContinuousSpace* const target_space_; 131 }; 132 133 std::ostream& operator<<(std::ostream& oss, ModUnionTableFactory::TableType type) { 134 switch (type) { 135 case ModUnionTableFactory::kTableTypeCardCache: { 136 oss << "CardCache"; 137 break; 138 } 139 case ModUnionTableFactory::kTableTypeReferenceCache: { 140 oss << "ReferenceCache"; 141 break; 142 } 143 default: { 144 UNIMPLEMENTED(FATAL) << static_cast<size_t>(type); 145 } 146 } 147 return oss; 148 } 149 150 ModUnionTable* ModUnionTableFactory::Create( 151 TableType type, space::ContinuousSpace* space, space::ContinuousSpace* target_space) { 152 std::ostringstream name; 153 name << "Mod union table: " << type; 154 switch (type) { 155 case kTableTypeCardCache: { 156 return new ModUnionTableCardCache(name.str(), Runtime::Current()->GetHeap(), space); 157 } 158 case kTableTypeReferenceCache: { 159 return new ModUnionTableRefCacheToSpace(name.str(), Runtime::Current()->GetHeap(), space, 160 target_space); 161 } 162 default: { 163 UNIMPLEMENTED(FATAL) << "Invalid type " << type; 164 } 165 } 166 return nullptr; 167 } 168 169 TEST_F(ModUnionTableTest, TestCardCache) { 170 RunTest(ModUnionTableFactory::kTableTypeCardCache); 171 } 172 173 TEST_F(ModUnionTableTest, TestReferenceCache) { 174 RunTest(ModUnionTableFactory::kTableTypeReferenceCache); 175 } 176 177 void ModUnionTableTest::RunTest(ModUnionTableFactory::TableType type) { 178 Thread* const self = Thread::Current(); 179 ScopedObjectAccess soa(self); 180 Runtime* const runtime = Runtime::Current(); 181 gc::Heap* const heap = runtime->GetHeap(); 182 // Use non moving space since moving GC don't necessarily have a primary free list space. 183 auto* space = heap->GetNonMovingSpace(); 184 ResetClass(); 185 // Create another space that we can put references in. 186 std::unique_ptr<space::DlMallocSpace> other_space(space::DlMallocSpace::Create( 187 "other space", 128 * KB, 4 * MB, 4 * MB, nullptr, false)); 188 ASSERT_TRUE(other_space.get() != nullptr); 189 { 190 ScopedThreadSuspension sts(self, kSuspended); 191 ScopedSuspendAll ssa("Add image space"); 192 heap->AddSpace(other_space.get()); 193 } 194 std::unique_ptr<ModUnionTable> table(ModUnionTableFactory::Create( 195 type, space, other_space.get())); 196 ASSERT_TRUE(table.get() != nullptr); 197 // Create some fake objects and put the main space and dirty cards in the non moving space. 198 auto* obj1 = AllocObjectArray(self, space, CardTable::kCardSize); 199 ASSERT_TRUE(obj1 != nullptr); 200 auto* obj2 = AllocObjectArray(self, space, CardTable::kCardSize); 201 ASSERT_TRUE(obj2 != nullptr); 202 auto* obj3 = AllocObjectArray(self, space, CardTable::kCardSize); 203 ASSERT_TRUE(obj3 != nullptr); 204 auto* obj4 = AllocObjectArray(self, space, CardTable::kCardSize); 205 ASSERT_TRUE(obj4 != nullptr); 206 // Dirty some cards. 207 obj1->Set(0, obj2); 208 obj2->Set(0, obj3); 209 obj3->Set(0, obj4); 210 obj4->Set(0, obj1); 211 // Dirty some more cards to objects in another space. 212 auto* other_space_ref1 = AllocObjectArray(self, other_space.get(), CardTable::kCardSize); 213 ASSERT_TRUE(other_space_ref1 != nullptr); 214 auto* other_space_ref2 = AllocObjectArray(self, other_space.get(), CardTable::kCardSize); 215 ASSERT_TRUE(other_space_ref2 != nullptr); 216 obj1->Set(1, other_space_ref1); 217 obj2->Set(3, other_space_ref2); 218 table->ProcessCards(); 219 std::set<mirror::Object*> visited_before; 220 CollectVisitedVisitor collector_before(&visited_before); 221 table->UpdateAndMarkReferences(&collector_before); 222 // Check that we visited all the references in other spaces only. 223 ASSERT_GE(visited_before.size(), 2u); 224 ASSERT_TRUE(visited_before.find(other_space_ref1) != visited_before.end()); 225 ASSERT_TRUE(visited_before.find(other_space_ref2) != visited_before.end()); 226 // Verify that all the other references were visited. 227 // obj1, obj2 cards should still be in mod union table since they have references to other 228 // spaces. 229 ASSERT_TRUE(table->ContainsCardFor(reinterpret_cast<uintptr_t>(obj1))); 230 ASSERT_TRUE(table->ContainsCardFor(reinterpret_cast<uintptr_t>(obj2))); 231 // obj3, obj4 don't have a reference to any object in the other space, their cards should have 232 // been removed from the mod union table during UpdateAndMarkReferences. 233 ASSERT_FALSE(table->ContainsCardFor(reinterpret_cast<uintptr_t>(obj3))); 234 ASSERT_FALSE(table->ContainsCardFor(reinterpret_cast<uintptr_t>(obj4))); 235 { 236 // Currently no-op, make sure it still works however. 237 ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_); 238 table->Verify(); 239 } 240 // Verify that dump doesn't crash. 241 std::ostringstream oss; 242 table->Dump(oss); 243 // Set all the cards, then verify. 244 table->SetCards(); 245 // TODO: Check that the cards are actually set. 246 for (auto* ptr = space->Begin(); ptr < AlignUp(space->End(), CardTable::kCardSize); 247 ptr += CardTable::kCardSize) { 248 ASSERT_TRUE(table->ContainsCardFor(reinterpret_cast<uintptr_t>(ptr))); 249 } 250 // Visit again and make sure the cards got cleared back to their sane state. 251 std::set<mirror::Object*> visited_after; 252 CollectVisitedVisitor collector_after(&visited_after); 253 table->UpdateAndMarkReferences(&collector_after); 254 // Check that we visited a superset after. 255 for (auto* obj : visited_before) { 256 ASSERT_TRUE(visited_after.find(obj) != visited_after.end()) << obj; 257 } 258 // Verify that the dump still works. 259 std::ostringstream oss2; 260 table->Dump(oss2); 261 // Remove the space we added so it doesn't persist to the next test. 262 ScopedThreadSuspension sts(self, kSuspended); 263 ScopedSuspendAll ssa("Add image space"); 264 heap->RemoveSpace(other_space.get()); 265 } 266 267 } // namespace accounting 268 } // namespace gc 269 } // namespace art 270