1 /*
2  * Copyright (C) 2014 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 "remembered_set.h"
18 
19 #include <memory>
20 
21 #include "base/stl_util.h"
22 #include "card_table-inl.h"
23 #include "gc/collector/mark_sweep-inl.h"
24 #include "gc/collector/mark_sweep.h"
25 #include "gc/collector/semi_space.h"
26 #include "gc/heap.h"
27 #include "gc/space/space.h"
28 #include "heap_bitmap.h"
29 #include "mirror/class-inl.h"
30 #include "mirror/object-inl.h"
31 #include "mirror/object-refvisitor-inl.h"
32 #include "mirror/object_array-inl.h"
33 #include "space_bitmap-inl.h"
34 #include "thread.h"
35 
36 namespace art HIDDEN {
37 namespace gc {
38 namespace accounting {
39 
40 class RememberedSetCardVisitor {
41  public:
RememberedSetCardVisitor(RememberedSet::CardSet * const dirty_cards)42   explicit RememberedSetCardVisitor(RememberedSet::CardSet* const dirty_cards)
43       : dirty_cards_(dirty_cards) {}
44 
operator ()(uint8_t * card,uint8_t expected_value,uint8_t new_value) const45   void operator()(uint8_t* card, uint8_t expected_value, [[maybe_unused]] uint8_t new_value) const {
46     if (expected_value == CardTable::kCardDirty) {
47       dirty_cards_->insert(card);
48     }
49   }
50 
51  private:
52   RememberedSet::CardSet* const dirty_cards_;
53 };
54 
ClearCards()55 void RememberedSet::ClearCards() {
56   CardTable* card_table = GetHeap()->GetCardTable();
57   RememberedSetCardVisitor card_visitor(&dirty_cards_);
58   // Clear dirty cards in the space and insert them into the dirty card set.
59   card_table->ModifyCardsAtomic(space_->Begin(), space_->End(), AgeCardVisitor(), card_visitor);
60 }
61 
62 class RememberedSetReferenceVisitor {
63  public:
RememberedSetReferenceVisitor(space::ContinuousSpace * target_space,bool * const contains_reference_to_target_space,collector::GarbageCollector * collector)64   RememberedSetReferenceVisitor(space::ContinuousSpace* target_space,
65                                 bool* const contains_reference_to_target_space,
66                                 collector::GarbageCollector* collector)
67       : collector_(collector), target_space_(target_space),
68         contains_reference_to_target_space_(contains_reference_to_target_space) {}
69 
operator ()(ObjPtr<mirror::Object> obj,MemberOffset offset,bool is_static) const70   void operator()(ObjPtr<mirror::Object> obj,
71                   MemberOffset offset,
72                   [[maybe_unused]] bool is_static) const REQUIRES_SHARED(Locks::mutator_lock_) {
73     DCHECK(obj != nullptr);
74     mirror::HeapReference<mirror::Object>* ref_ptr = obj->GetFieldObjectReferenceAddr(offset);
75     if (target_space_->HasAddress(ref_ptr->AsMirrorPtr())) {
76       *contains_reference_to_target_space_ = true;
77       collector_->MarkHeapReference(ref_ptr, /*do_atomic_update=*/ false);
78       DCHECK(!target_space_->HasAddress(ref_ptr->AsMirrorPtr()));
79     }
80   }
81 
operator ()(ObjPtr<mirror::Class> klass,ObjPtr<mirror::Reference> ref) const82   void operator()(ObjPtr<mirror::Class> klass, ObjPtr<mirror::Reference> ref) const
83       REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::heap_bitmap_lock_) {
84     if (target_space_->HasAddress(ref->GetReferent())) {
85       *contains_reference_to_target_space_ = true;
86       collector_->DelayReferenceReferent(klass, ref);
87     }
88   }
89 
VisitRootIfNonNull(mirror::CompressedReference<mirror::Object> * root) const90   void VisitRootIfNonNull(mirror::CompressedReference<mirror::Object>* root) const
91       REQUIRES_SHARED(Locks::mutator_lock_) {
92     if (!root->IsNull()) {
93       VisitRoot(root);
94     }
95   }
96 
VisitRoot(mirror::CompressedReference<mirror::Object> * root) const97   void VisitRoot(mirror::CompressedReference<mirror::Object>* root) const
98       REQUIRES_SHARED(Locks::mutator_lock_) {
99     if (target_space_->HasAddress(root->AsMirrorPtr())) {
100       *contains_reference_to_target_space_ = true;
101       root->Assign(collector_->MarkObject(root->AsMirrorPtr()));
102       DCHECK(!target_space_->HasAddress(root->AsMirrorPtr()));
103     }
104   }
105 
106  private:
107   collector::GarbageCollector* const collector_;
108   space::ContinuousSpace* const target_space_;
109   bool* const contains_reference_to_target_space_;
110 };
111 
112 class RememberedSetObjectVisitor {
113  public:
RememberedSetObjectVisitor(space::ContinuousSpace * target_space,bool * const contains_reference_to_target_space,collector::GarbageCollector * collector)114   RememberedSetObjectVisitor(space::ContinuousSpace* target_space,
115                              bool* const contains_reference_to_target_space,
116                              collector::GarbageCollector* collector)
117       : collector_(collector), target_space_(target_space),
118         contains_reference_to_target_space_(contains_reference_to_target_space) {}
119 
operator ()(ObjPtr<mirror::Object> obj) const120   void operator()(ObjPtr<mirror::Object> obj) const REQUIRES(Locks::heap_bitmap_lock_)
121       REQUIRES_SHARED(Locks::mutator_lock_) {
122     RememberedSetReferenceVisitor visitor(target_space_, contains_reference_to_target_space_,
123                                           collector_);
124     obj->VisitReferences(visitor, visitor);
125   }
126 
127  private:
128   collector::GarbageCollector* const collector_;
129   space::ContinuousSpace* const target_space_;
130   bool* const contains_reference_to_target_space_;
131 };
132 
UpdateAndMarkReferences(space::ContinuousSpace * target_space,collector::GarbageCollector * collector)133 void RememberedSet::UpdateAndMarkReferences(space::ContinuousSpace* target_space,
134                                             collector::GarbageCollector* collector) {
135   CardTable* card_table = heap_->GetCardTable();
136   bool contains_reference_to_target_space = false;
137   RememberedSetObjectVisitor obj_visitor(target_space, &contains_reference_to_target_space,
138                                          collector);
139   ContinuousSpaceBitmap* bitmap = space_->GetLiveBitmap();
140   CardSet remove_card_set;
141   for (uint8_t* const card_addr : dirty_cards_) {
142     contains_reference_to_target_space = false;
143     uintptr_t start = reinterpret_cast<uintptr_t>(card_table->AddrFromCard(card_addr));
144     DCHECK(space_->HasAddress(reinterpret_cast<mirror::Object*>(start)));
145     bitmap->VisitMarkedRange(start, start + CardTable::kCardSize, obj_visitor);
146     if (!contains_reference_to_target_space) {
147       // It was in the dirty card set, but it didn't actually contain
148       // a reference to the target space. So, remove it from the dirty
149       // card set so we won't have to scan it again (unless it gets
150       // dirty again.)
151       remove_card_set.insert(card_addr);
152     }
153   }
154 
155   // Remove the cards that didn't contain a reference to the target
156   // space from the dirty card set.
157   for (uint8_t* const card_addr : remove_card_set) {
158     DCHECK(dirty_cards_.find(card_addr) != dirty_cards_.end());
159     dirty_cards_.erase(card_addr);
160   }
161 }
162 
Dump(std::ostream & os)163 void RememberedSet::Dump(std::ostream& os) {
164   CardTable* card_table = heap_->GetCardTable();
165   os << "RememberedSet dirty cards: [";
166   for (const uint8_t* card_addr : dirty_cards_) {
167     auto start = reinterpret_cast<uintptr_t>(card_table->AddrFromCard(card_addr));
168     auto end = start + CardTable::kCardSize;
169     os << reinterpret_cast<void*>(start) << "-" << reinterpret_cast<void*>(end) << "\n";
170   }
171   os << "]";
172 }
173 
AssertAllDirtyCardsAreWithinSpace() const174 void RememberedSet::AssertAllDirtyCardsAreWithinSpace() const {
175   CardTable* card_table = heap_->GetCardTable();
176   for (const uint8_t* card_addr : dirty_cards_) {
177     auto start = reinterpret_cast<uint8_t*>(card_table->AddrFromCard(card_addr));
178     auto end = start + CardTable::kCardSize;
179     DCHECK_LE(space_->Begin(), start);
180     DCHECK_LE(end, space_->Limit());
181   }
182 }
183 
184 }  // namespace accounting
185 }  // namespace gc
186 }  // namespace art
187