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