1/*
2 * Copyright (C) 2012 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.h"
18
19#include <memory>
20
21#include "base/stl_util.h"
22#include "bitmap-inl.h"
23#include "card_table-inl.h"
24#include "gc/accounting/space_bitmap-inl.h"
25#include "gc/heap.h"
26#include "gc/space/image_space.h"
27#include "gc/space/space.h"
28#include "mirror/object-inl.h"
29#include "space_bitmap-inl.h"
30#include "thread-inl.h"
31
32namespace art {
33namespace gc {
34namespace accounting {
35
36class ModUnionAddToCardSetVisitor {
37 public:
38  explicit ModUnionAddToCardSetVisitor(ModUnionTable::CardSet* const cleared_cards)
39      : cleared_cards_(cleared_cards) {}
40
41  inline void operator()(uint8_t* card,
42                         uint8_t expected_value,
43                         uint8_t new_value ATTRIBUTE_UNUSED) const {
44    if (expected_value == CardTable::kCardDirty) {
45      cleared_cards_->insert(card);
46    }
47  }
48
49 private:
50  ModUnionTable::CardSet* const cleared_cards_;
51};
52
53class ModUnionAddToCardBitmapVisitor {
54 public:
55  ModUnionAddToCardBitmapVisitor(ModUnionTable::CardBitmap* bitmap, CardTable* card_table)
56      : bitmap_(bitmap), card_table_(card_table) {}
57
58  inline void operator()(uint8_t* card,
59                         uint8_t expected_value,
60                         uint8_t new_value ATTRIBUTE_UNUSED) const {
61    if (expected_value == CardTable::kCardDirty) {
62      // We want the address the card represents, not the address of the card.
63      bitmap_->Set(reinterpret_cast<uintptr_t>(card_table_->AddrFromCard(card)));
64    }
65  }
66
67 private:
68  ModUnionTable::CardBitmap* const bitmap_;
69  CardTable* const card_table_;
70};
71
72class ModUnionAddToCardVectorVisitor {
73 public:
74  explicit ModUnionAddToCardVectorVisitor(std::vector<uint8_t*>* cleared_cards)
75      : cleared_cards_(cleared_cards) {
76  }
77
78  void operator()(uint8_t* card, uint8_t expected_card, uint8_t new_card ATTRIBUTE_UNUSED) const {
79    if (expected_card == CardTable::kCardDirty) {
80      cleared_cards_->push_back(card);
81    }
82  }
83
84 private:
85  std::vector<uint8_t*>* const cleared_cards_;
86};
87
88class ModUnionUpdateObjectReferencesVisitor {
89 public:
90  ModUnionUpdateObjectReferencesVisitor(MarkObjectVisitor* visitor,
91                                        space::ContinuousSpace* from_space,
92                                        space::ContinuousSpace* immune_space,
93                                        bool* contains_reference_to_other_space)
94    : visitor_(visitor),
95      from_space_(from_space),
96      immune_space_(immune_space),
97      contains_reference_to_other_space_(contains_reference_to_other_space) {}
98
99  // Extra parameters are required since we use this same visitor signature for checking objects.
100  void operator()(mirror::Object* obj, MemberOffset offset, bool is_static ATTRIBUTE_UNUSED) const
101      SHARED_REQUIRES(Locks::mutator_lock_) {
102    MarkReference(obj->GetFieldObjectReferenceAddr(offset));
103  }
104
105  void VisitRootIfNonNull(mirror::CompressedReference<mirror::Object>* root) const
106      SHARED_REQUIRES(Locks::mutator_lock_) {
107    VisitRoot(root);
108  }
109
110  void VisitRoot(mirror::CompressedReference<mirror::Object>* root) const
111      SHARED_REQUIRES(Locks::mutator_lock_) {
112    MarkReference(root);
113  }
114
115 private:
116  template<bool kPoisonReferences>
117  void MarkReference(mirror::ObjectReference<kPoisonReferences, mirror::Object>* obj_ptr) const
118      SHARED_REQUIRES(Locks::mutator_lock_) {
119    // Only add the reference if it is non null and fits our criteria.
120    mirror::Object* ref = obj_ptr->AsMirrorPtr();
121    if (ref != nullptr && !from_space_->HasAddress(ref) && !immune_space_->HasAddress(ref)) {
122      *contains_reference_to_other_space_ = true;
123      mirror::Object* new_object = visitor_->MarkObject(ref);
124      if (ref != new_object) {
125        obj_ptr->Assign(new_object);
126      }
127    }
128  }
129
130  MarkObjectVisitor* const visitor_;
131  // Space which we are scanning
132  space::ContinuousSpace* const from_space_;
133  space::ContinuousSpace* const immune_space_;
134  // Set if we have any references to another space.
135  bool* const contains_reference_to_other_space_;
136};
137
138class ModUnionScanImageRootVisitor {
139 public:
140  // Immune space is any other space which we don't care about references to. Currently this is
141  // the image space in the case of the zygote mod union table.
142  ModUnionScanImageRootVisitor(MarkObjectVisitor* visitor,
143                               space::ContinuousSpace* from_space,
144                               space::ContinuousSpace* immune_space,
145                               bool* contains_reference_to_other_space)
146      : visitor_(visitor),
147        from_space_(from_space),
148        immune_space_(immune_space),
149        contains_reference_to_other_space_(contains_reference_to_other_space) {}
150
151  void operator()(mirror::Object* root) const
152      REQUIRES(Locks::heap_bitmap_lock_)
153      SHARED_REQUIRES(Locks::mutator_lock_) {
154    DCHECK(root != nullptr);
155    ModUnionUpdateObjectReferencesVisitor ref_visitor(visitor_,
156                                                      from_space_,
157                                                      immune_space_,
158                                                      contains_reference_to_other_space_);
159    root->VisitReferences(ref_visitor, VoidFunctor());
160  }
161
162 private:
163  MarkObjectVisitor* const visitor_;
164  // Space which we are scanning
165  space::ContinuousSpace* const from_space_;
166  space::ContinuousSpace* const immune_space_;
167  // Set if we have any references to another space.
168  bool* const contains_reference_to_other_space_;
169};
170
171void ModUnionTableReferenceCache::ClearCards() {
172  CardTable* card_table = GetHeap()->GetCardTable();
173  ModUnionAddToCardSetVisitor visitor(&cleared_cards_);
174  // Clear dirty cards in the this space and update the corresponding mod-union bits.
175  card_table->ModifyCardsAtomic(space_->Begin(), space_->End(), AgeCardVisitor(), visitor);
176}
177
178class AddToReferenceArrayVisitor {
179 public:
180  AddToReferenceArrayVisitor(ModUnionTableReferenceCache* mod_union_table,
181                             MarkObjectVisitor* visitor,
182                             std::vector<mirror::HeapReference<mirror::Object>*>* references,
183                             bool* has_target_reference)
184      : mod_union_table_(mod_union_table),
185        visitor_(visitor),
186        references_(references),
187        has_target_reference_(has_target_reference) {}
188
189  // Extra parameters are required since we use this same visitor signature for checking objects.
190  void operator()(mirror::Object* obj, MemberOffset offset, bool is_static ATTRIBUTE_UNUSED) const
191      SHARED_REQUIRES(Locks::mutator_lock_) {
192    mirror::HeapReference<mirror::Object>* ref_ptr = obj->GetFieldObjectReferenceAddr(offset);
193    mirror::Object* ref = ref_ptr->AsMirrorPtr();
194    // Only add the reference if it is non null and fits our criteria.
195    if (ref != nullptr && mod_union_table_->ShouldAddReference(ref)) {
196      // Push the adddress of the reference.
197      references_->push_back(ref_ptr);
198    }
199  }
200
201  void VisitRootIfNonNull(mirror::CompressedReference<mirror::Object>* root) const
202      SHARED_REQUIRES(Locks::mutator_lock_) {
203    if (!root->IsNull()) {
204      VisitRoot(root);
205    }
206  }
207
208  void VisitRoot(mirror::CompressedReference<mirror::Object>* root) const
209      SHARED_REQUIRES(Locks::mutator_lock_) {
210    if (mod_union_table_->ShouldAddReference(root->AsMirrorPtr())) {
211      *has_target_reference_ = true;
212      // TODO: Add MarkCompressedReference callback here.
213      mirror::Object* old_ref = root->AsMirrorPtr();
214      mirror::Object* new_ref = visitor_->MarkObject(old_ref);
215      if (old_ref != new_ref) {
216        root->Assign(new_ref);
217      }
218    }
219  }
220
221 private:
222  ModUnionTableReferenceCache* const mod_union_table_;
223  MarkObjectVisitor* const visitor_;
224  std::vector<mirror::HeapReference<mirror::Object>*>* const references_;
225  bool* const has_target_reference_;
226};
227
228class ModUnionReferenceVisitor {
229 public:
230  ModUnionReferenceVisitor(ModUnionTableReferenceCache* const mod_union_table,
231                           MarkObjectVisitor* visitor,
232                           std::vector<mirror::HeapReference<mirror::Object>*>* references,
233                           bool* has_target_reference)
234      : mod_union_table_(mod_union_table),
235        visitor_(visitor),
236        references_(references),
237        has_target_reference_(has_target_reference) {}
238
239  void operator()(mirror::Object* obj) const
240      SHARED_REQUIRES(Locks::heap_bitmap_lock_, Locks::mutator_lock_) {
241    // We don't have an early exit since we use the visitor pattern, an early
242    // exit should significantly speed this up.
243    AddToReferenceArrayVisitor visitor(mod_union_table_,
244                                       visitor_,
245                                       references_,
246                                       has_target_reference_);
247    obj->VisitReferences(visitor, VoidFunctor());
248  }
249
250 private:
251  ModUnionTableReferenceCache* const mod_union_table_;
252  MarkObjectVisitor* const visitor_;
253  std::vector<mirror::HeapReference<mirror::Object>*>* const references_;
254  bool* const has_target_reference_;
255};
256
257class CheckReferenceVisitor {
258 public:
259  CheckReferenceVisitor(ModUnionTableReferenceCache* mod_union_table,
260                        const std::set<mirror::Object*>& references)
261      : mod_union_table_(mod_union_table),
262        references_(references) {}
263
264  // Extra parameters are required since we use this same visitor signature for checking objects.
265  void operator()(mirror::Object* obj, MemberOffset offset, bool is_static ATTRIBUTE_UNUSED) const
266      SHARED_REQUIRES(Locks::heap_bitmap_lock_, Locks::mutator_lock_) {
267    mirror::Object* ref = obj->GetFieldObject<mirror::Object>(offset);
268    if (ref != nullptr &&
269        mod_union_table_->ShouldAddReference(ref) &&
270        references_.find(ref) == references_.end()) {
271      Heap* heap = mod_union_table_->GetHeap();
272      space::ContinuousSpace* from_space = heap->FindContinuousSpaceFromObject(obj, false);
273      space::ContinuousSpace* to_space = heap->FindContinuousSpaceFromObject(ref, false);
274      LOG(INFO) << "Object " << reinterpret_cast<const void*>(obj) << "(" << PrettyTypeOf(obj)
275          << ")" << "References " << reinterpret_cast<const void*>(ref) << "(" << PrettyTypeOf(ref)
276          << ") without being in mod-union table";
277      LOG(INFO) << "FromSpace " << from_space->GetName() << " type "
278          << from_space->GetGcRetentionPolicy();
279      LOG(INFO) << "ToSpace " << to_space->GetName() << " type "
280          << to_space->GetGcRetentionPolicy();
281      heap->DumpSpaces(LOG(INFO));
282      LOG(FATAL) << "FATAL ERROR";
283    }
284  }
285
286  void VisitRootIfNonNull(mirror::CompressedReference<mirror::Object>* root) const
287      SHARED_REQUIRES(Locks::mutator_lock_) {
288    if (kIsDebugBuild && !root->IsNull()) {
289      VisitRoot(root);
290    }
291  }
292
293  void VisitRoot(mirror::CompressedReference<mirror::Object>* root) const
294      SHARED_REQUIRES(Locks::mutator_lock_) {
295    DCHECK(!mod_union_table_->ShouldAddReference(root->AsMirrorPtr()));
296  }
297
298 private:
299  ModUnionTableReferenceCache* const mod_union_table_;
300  const std::set<mirror::Object*>& references_;
301};
302
303class ModUnionCheckReferences {
304 public:
305  ModUnionCheckReferences(ModUnionTableReferenceCache* mod_union_table,
306                          const std::set<mirror::Object*>& references)
307      REQUIRES(Locks::heap_bitmap_lock_)
308      : mod_union_table_(mod_union_table), references_(references) {}
309
310  void operator()(mirror::Object* obj) const NO_THREAD_SAFETY_ANALYSIS {
311    Locks::heap_bitmap_lock_->AssertSharedHeld(Thread::Current());
312    CheckReferenceVisitor visitor(mod_union_table_, references_);
313    obj->VisitReferences(visitor, VoidFunctor());
314  }
315
316 private:
317  ModUnionTableReferenceCache* const mod_union_table_;
318  const std::set<mirror::Object*>& references_;
319};
320
321void ModUnionTableReferenceCache::Verify() {
322  // Start by checking that everything in the mod union table is marked.
323  for (const auto& ref_pair : references_) {
324    for (mirror::HeapReference<mirror::Object>* ref : ref_pair.second) {
325      CHECK(heap_->IsLiveObjectLocked(ref->AsMirrorPtr()));
326    }
327  }
328
329  // Check the references of each clean card which is also in the mod union table.
330  CardTable* card_table = heap_->GetCardTable();
331  ContinuousSpaceBitmap* live_bitmap = space_->GetLiveBitmap();
332  for (const auto& ref_pair : references_) {
333    const uint8_t* card = ref_pair.first;
334    if (*card == CardTable::kCardClean) {
335      std::set<mirror::Object*> reference_set;
336      for (mirror::HeapReference<mirror::Object>* obj_ptr : ref_pair.second) {
337        reference_set.insert(obj_ptr->AsMirrorPtr());
338      }
339      ModUnionCheckReferences visitor(this, reference_set);
340      uintptr_t start = reinterpret_cast<uintptr_t>(card_table->AddrFromCard(card));
341      live_bitmap->VisitMarkedRange(start, start + CardTable::kCardSize, visitor);
342    }
343  }
344}
345
346void ModUnionTableReferenceCache::Dump(std::ostream& os) {
347  CardTable* card_table = heap_->GetCardTable();
348  os << "ModUnionTable cleared cards: [";
349  for (uint8_t* card_addr : cleared_cards_) {
350    uintptr_t start = reinterpret_cast<uintptr_t>(card_table->AddrFromCard(card_addr));
351    uintptr_t end = start + CardTable::kCardSize;
352    os << reinterpret_cast<void*>(start) << "-" << reinterpret_cast<void*>(end) << ",";
353  }
354  os << "]\nModUnionTable references: [";
355  for (const auto& ref_pair : references_) {
356    const uint8_t* card_addr = ref_pair.first;
357    uintptr_t start = reinterpret_cast<uintptr_t>(card_table->AddrFromCard(card_addr));
358    uintptr_t end = start + CardTable::kCardSize;
359    os << reinterpret_cast<void*>(start) << "-" << reinterpret_cast<void*>(end) << "->{";
360    for (mirror::HeapReference<mirror::Object>* ref : ref_pair.second) {
361      os << reinterpret_cast<const void*>(ref->AsMirrorPtr()) << ",";
362    }
363    os << "},";
364  }
365}
366
367void ModUnionTableReferenceCache::UpdateAndMarkReferences(MarkObjectVisitor* visitor) {
368  CardTable* const card_table = heap_->GetCardTable();
369  std::vector<mirror::HeapReference<mirror::Object>*> cards_references;
370  // If has_target_reference is true then there was a GcRoot compressed reference which wasn't
371  // added. In this case we need to keep the card dirty.
372  // We don't know if the GcRoot addresses will remain constant, for example, classloaders have a
373  // hash set of GcRoot which may be resized or modified.
374  bool has_target_reference;
375  ModUnionReferenceVisitor add_visitor(this, visitor, &cards_references, &has_target_reference);
376  CardSet new_cleared_cards;
377  for (uint8_t* card : cleared_cards_) {
378    // Clear and re-compute alloc space references associated with this card.
379    cards_references.clear();
380    has_target_reference = false;
381    uintptr_t start = reinterpret_cast<uintptr_t>(card_table->AddrFromCard(card));
382    uintptr_t end = start + CardTable::kCardSize;
383    space::ContinuousSpace* space =
384        heap_->FindContinuousSpaceFromObject(reinterpret_cast<mirror::Object*>(start), false);
385    DCHECK(space != nullptr);
386    ContinuousSpaceBitmap* live_bitmap = space->GetLiveBitmap();
387    live_bitmap->VisitMarkedRange(start, end, add_visitor);
388    // Update the corresponding references for the card.
389    auto found = references_.find(card);
390    if (found == references_.end()) {
391      // Don't add card for an empty reference array.
392      if (!cards_references.empty()) {
393        references_.Put(card, cards_references);
394      }
395    } else {
396      if (cards_references.empty()) {
397        references_.erase(found);
398      } else {
399        found->second = cards_references;
400      }
401    }
402    if (has_target_reference) {
403      // Keep this card for next time since it contains a GcRoot which matches the
404      // ShouldAddReference criteria. This usually occurs for class loaders.
405      new_cleared_cards.insert(card);
406    }
407  }
408  cleared_cards_ = std::move(new_cleared_cards);
409  size_t count = 0;
410  for (auto it = references_.begin(); it != references_.end();) {
411    std::vector<mirror::HeapReference<mirror::Object>*>& references = it->second;
412    // Since there is no card mark for setting a reference to null, we check each reference.
413    // If all of the references of a card are null then we can remove that card. This is racy
414    // with the mutators, but handled by rescanning dirty cards.
415    bool all_null = true;
416    for (mirror::HeapReference<mirror::Object>* obj_ptr : references) {
417      if (obj_ptr->AsMirrorPtr() != nullptr) {
418        all_null = false;
419        visitor->MarkHeapReference(obj_ptr);
420      }
421    }
422    count += references.size();
423    if (!all_null) {
424      ++it;
425    } else {
426      // All null references, erase the array from the set.
427      it = references_.erase(it);
428    }
429  }
430  if (VLOG_IS_ON(heap)) {
431    VLOG(gc) << "Marked " << count << " references in mod union table";
432  }
433}
434
435ModUnionTableCardCache::ModUnionTableCardCache(const std::string& name,
436                                               Heap* heap,
437                                               space::ContinuousSpace* space)
438    : ModUnionTable(name, heap, space) {
439  // Normally here we could use End() instead of Limit(), but for testing we may want to have a
440  // mod-union table for a space which can still grow.
441  if (!space->IsImageSpace()) {
442    CHECK_ALIGNED(reinterpret_cast<uintptr_t>(space->Limit()), CardTable::kCardSize);
443  }
444  card_bitmap_.reset(CardBitmap::Create(
445      "mod union bitmap", reinterpret_cast<uintptr_t>(space->Begin()),
446      RoundUp(reinterpret_cast<uintptr_t>(space->Limit()), CardTable::kCardSize)));
447}
448
449class CardBitVisitor {
450 public:
451  CardBitVisitor(MarkObjectVisitor* visitor,
452                 space::ContinuousSpace* space,
453                 space::ContinuousSpace* immune_space,
454                 ModUnionTable::CardBitmap* card_bitmap)
455      : visitor_(visitor),
456        space_(space),
457        immune_space_(immune_space),
458        bitmap_(space->GetLiveBitmap()),
459        card_bitmap_(card_bitmap) {
460    DCHECK(immune_space_ != nullptr);
461  }
462
463  void operator()(size_t bit_index) const {
464    const uintptr_t start = card_bitmap_->AddrFromBitIndex(bit_index);
465    DCHECK(space_->HasAddress(reinterpret_cast<mirror::Object*>(start)))
466        << start << " " << *space_;
467    bool reference_to_other_space = false;
468    ModUnionScanImageRootVisitor scan_visitor(visitor_, space_, immune_space_,
469                                              &reference_to_other_space);
470    bitmap_->VisitMarkedRange(start, start + CardTable::kCardSize, scan_visitor);
471    if (!reference_to_other_space) {
472      // No non null reference to another space, clear the bit.
473      card_bitmap_->ClearBit(bit_index);
474    }
475  }
476
477 private:
478  MarkObjectVisitor* const visitor_;
479  space::ContinuousSpace* const space_;
480  space::ContinuousSpace* const immune_space_;
481  ContinuousSpaceBitmap* const bitmap_;
482  ModUnionTable::CardBitmap* const card_bitmap_;
483};
484
485void ModUnionTableCardCache::ClearCards() {
486  CardTable* const card_table = GetHeap()->GetCardTable();
487  ModUnionAddToCardBitmapVisitor visitor(card_bitmap_.get(), card_table);
488  // Clear dirty cards in the this space and update the corresponding mod-union bits.
489  card_table->ModifyCardsAtomic(space_->Begin(), space_->End(), AgeCardVisitor(), visitor);
490}
491
492// Mark all references to the alloc space(s).
493void ModUnionTableCardCache::UpdateAndMarkReferences(MarkObjectVisitor* visitor) {
494  // TODO: Needs better support for multi-images? b/26317072
495  space::ImageSpace* image_space =
496      heap_->GetBootImageSpaces().empty() ? nullptr : heap_->GetBootImageSpaces()[0];
497  // If we don't have an image space, just pass in space_ as the immune space. Pass in the same
498  // space_ instead of image_space to avoid a null check in ModUnionUpdateObjectReferencesVisitor.
499  CardBitVisitor bit_visitor(visitor, space_, image_space != nullptr ? image_space : space_,
500      card_bitmap_.get());
501  card_bitmap_->VisitSetBits(
502      0, RoundUp(space_->Size(), CardTable::kCardSize) / CardTable::kCardSize, bit_visitor);
503}
504
505void ModUnionTableCardCache::Dump(std::ostream& os) {
506  os << "ModUnionTable dirty cards: [";
507  // TODO: Find cleaner way of doing this.
508  for (uint8_t* addr = space_->Begin(); addr < AlignUp(space_->End(), CardTable::kCardSize);
509      addr += CardTable::kCardSize) {
510    if (card_bitmap_->Test(reinterpret_cast<uintptr_t>(addr))) {
511      os << reinterpret_cast<void*>(addr) << "-"
512         << reinterpret_cast<void*>(addr + CardTable::kCardSize) << "\n";
513    }
514  }
515  os << "]";
516}
517
518void ModUnionTableCardCache::SetCards() {
519  // Only clean up to the end since there cannot be any objects past the End() of the space.
520  for (uint8_t* addr = space_->Begin(); addr < AlignUp(space_->End(), CardTable::kCardSize);
521       addr += CardTable::kCardSize) {
522    card_bitmap_->Set(reinterpret_cast<uintptr_t>(addr));
523  }
524}
525
526bool ModUnionTableCardCache::ContainsCardFor(uintptr_t addr) {
527  return card_bitmap_->Test(addr);
528}
529
530void ModUnionTableReferenceCache::SetCards() {
531  for (uint8_t* addr = space_->Begin(); addr < AlignUp(space_->End(), CardTable::kCardSize);
532       addr += CardTable::kCardSize) {
533    cleared_cards_.insert(heap_->GetCardTable()->CardFromAddr(reinterpret_cast<void*>(addr)));
534  }
535}
536
537bool ModUnionTableReferenceCache::ContainsCardFor(uintptr_t addr) {
538  auto* card_ptr = heap_->GetCardTable()->CardFromAddr(reinterpret_cast<void*>(addr));
539  return cleared_cards_.find(card_ptr) != cleared_cards_.end() ||
540      references_.find(card_ptr) != references_.end();
541}
542
543}  // namespace accounting
544}  // namespace gc
545}  // namespace art
546