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
27namespace art {
28namespace gc {
29namespace accounting {
30
31class 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
44class 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.
97class 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.
117class 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
132std::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
149ModUnionTable* 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
168TEST_F(ModUnionTableTest, TestCardCache) {
169  RunTest(ModUnionTableFactory::kTableTypeCardCache);
170}
171
172TEST_F(ModUnionTableTest, TestReferenceCache) {
173  RunTest(ModUnionTableFactory::kTableTypeReferenceCache);
174}
175
176void 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