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