138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi/* 238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi * Copyright (C) 2014 The Android Open Source Project 338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi * 438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi * Licensed under the Apache License, Version 2.0 (the "License"); 538e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi * you may not use this file except in compliance with the License. 638e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi * You may obtain a copy of the License at 738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi * 838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi * http://www.apache.org/licenses/LICENSE-2.0 938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi * 1038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi * Unless required by applicable law or agreed to in writing, software 1138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi * distributed under the License is distributed on an "AS IS" BASIS, 1238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi * See the License for the specific language governing permissions and 1438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi * limitations under the License. 1538e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi */ 1638e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 1738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "remembered_set.h" 1838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 19700a402244a1a423da4f3ba8032459f4b65fa18fIan Rogers#include <memory> 20700a402244a1a423da4f3ba8032459f4b65fa18fIan Rogers 2138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "base/stl_util.h" 2238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "card_table-inl.h" 2338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "heap_bitmap.h" 2438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "gc/collector/mark_sweep.h" 2538e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "gc/collector/mark_sweep-inl.h" 2638e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "gc/collector/semi_space.h" 2738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "gc/heap.h" 2838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "gc/space/space.h" 2938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "mirror/object-inl.h" 3038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "mirror/class-inl.h" 3138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "mirror/object_array-inl.h" 3238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "space_bitmap-inl.h" 3338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "thread.h" 3438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 3538e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchinamespace art { 3638e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchinamespace gc { 3738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchinamespace accounting { 3838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 3938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchiclass RememberedSetCardVisitor { 4038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi public: 4138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi explicit RememberedSetCardVisitor(RememberedSet::CardSet* const dirty_cards) 4238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi : dirty_cards_(dirty_cards) {} 4338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 444b8f1ecd3aa5a29ec1463ff88fee9db365f257dcRoland Levillain void operator()(uint8_t* card, uint8_t expected_value, uint8_t new_value ATTRIBUTE_UNUSED) const { 4538e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi if (expected_value == CardTable::kCardDirty) { 4638e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi dirty_cards_->insert(card); 4738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi } 4838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi } 4938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 5038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi private: 5138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi RememberedSet::CardSet* const dirty_cards_; 5238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi}; 5338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 5438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchivoid RememberedSet::ClearCards() { 5538e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi CardTable* card_table = GetHeap()->GetCardTable(); 5638e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi RememberedSetCardVisitor card_visitor(&dirty_cards_); 5738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi // Clear dirty cards in the space and insert them into the dirty card set. 5838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi card_table->ModifyCardsAtomic(space_->Begin(), space_->End(), AgeCardVisitor(), card_visitor); 5938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi} 6038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 6138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchiclass RememberedSetReferenceVisitor { 6238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi public: 6397509954404d031594b2ecbda607314d169d512eMathieu Chartier RememberedSetReferenceVisitor(space::ContinuousSpace* target_space, 6497509954404d031594b2ecbda607314d169d512eMathieu Chartier bool* const contains_reference_to_target_space, 6597509954404d031594b2ecbda607314d169d512eMathieu Chartier collector::GarbageCollector* collector) 6697509954404d031594b2ecbda607314d169d512eMathieu Chartier : collector_(collector), target_space_(target_space), 6738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi contains_reference_to_target_space_(contains_reference_to_target_space) {} 6838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 69da7c650022a974be10e2f00fa07d5109e3d8826fMathieu Chartier void operator()(mirror::Object* obj, MemberOffset offset, bool is_static ATTRIBUTE_UNUSED) const 7090443477f9a0061581c420775ce3b7eeae7468bcMathieu Chartier SHARED_REQUIRES(Locks::mutator_lock_) { 713b05e9ba874449dbff65b01b8781001f7d93eea6Mathieu Chartier DCHECK(obj != nullptr); 72407f702da4f867c074fc3c8c688b8f8c32279effMathieu Chartier mirror::HeapReference<mirror::Object>* ref_ptr = obj->GetFieldObjectReferenceAddr(offset); 73407f702da4f867c074fc3c8c688b8f8c32279effMathieu Chartier if (target_space_->HasAddress(ref_ptr->AsMirrorPtr())) { 74407f702da4f867c074fc3c8c688b8f8c32279effMathieu Chartier *contains_reference_to_target_space_ = true; 7597509954404d031594b2ecbda607314d169d512eMathieu Chartier collector_->MarkHeapReference(ref_ptr); 76407f702da4f867c074fc3c8c688b8f8c32279effMathieu Chartier DCHECK(!target_space_->HasAddress(ref_ptr->AsMirrorPtr())); 7738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi } 7838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi } 7938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 804db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi void operator()(mirror::Class* klass, mirror::Reference* ref) const 81da7c650022a974be10e2f00fa07d5109e3d8826fMathieu Chartier SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::heap_bitmap_lock_) { 824db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi if (target_space_->HasAddress(ref->GetReferent())) { 834db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi *contains_reference_to_target_space_ = true; 8497509954404d031594b2ecbda607314d169d512eMathieu Chartier collector_->DelayReferenceReferent(klass, ref); 854db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi } 864db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi } 874db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi 88da7c650022a974be10e2f00fa07d5109e3d8826fMathieu Chartier void VisitRootIfNonNull(mirror::CompressedReference<mirror::Object>* root) const 89da7c650022a974be10e2f00fa07d5109e3d8826fMathieu Chartier SHARED_REQUIRES(Locks::mutator_lock_) { 90eb837eb7c27e789bc7b05f474be9aa119f2fd99fMathieu Chartier if (!root->IsNull()) { 91da7c650022a974be10e2f00fa07d5109e3d8826fMathieu Chartier VisitRoot(root); 92da7c650022a974be10e2f00fa07d5109e3d8826fMathieu Chartier } 93da7c650022a974be10e2f00fa07d5109e3d8826fMathieu Chartier } 94da7c650022a974be10e2f00fa07d5109e3d8826fMathieu Chartier 95da7c650022a974be10e2f00fa07d5109e3d8826fMathieu Chartier void VisitRoot(mirror::CompressedReference<mirror::Object>* root) const 96da7c650022a974be10e2f00fa07d5109e3d8826fMathieu Chartier SHARED_REQUIRES(Locks::mutator_lock_) { 9739089124ceac46a45f17b8261a09b88a9606bb97Mathieu Chartier if (target_space_->HasAddress(root->AsMirrorPtr())) { 9839089124ceac46a45f17b8261a09b88a9606bb97Mathieu Chartier *contains_reference_to_target_space_ = true; 9939089124ceac46a45f17b8261a09b88a9606bb97Mathieu Chartier root->Assign(collector_->MarkObject(root->AsMirrorPtr())); 10039089124ceac46a45f17b8261a09b88a9606bb97Mathieu Chartier DCHECK(!target_space_->HasAddress(root->AsMirrorPtr())); 10139089124ceac46a45f17b8261a09b88a9606bb97Mathieu Chartier } 102da7c650022a974be10e2f00fa07d5109e3d8826fMathieu Chartier } 103da7c650022a974be10e2f00fa07d5109e3d8826fMathieu Chartier 10438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi private: 10597509954404d031594b2ecbda607314d169d512eMathieu Chartier collector::GarbageCollector* const collector_; 10638e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi space::ContinuousSpace* const target_space_; 10738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi bool* const contains_reference_to_target_space_; 10838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi}; 10938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 11038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchiclass RememberedSetObjectVisitor { 11138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi public: 11297509954404d031594b2ecbda607314d169d512eMathieu Chartier RememberedSetObjectVisitor(space::ContinuousSpace* target_space, 11397509954404d031594b2ecbda607314d169d512eMathieu Chartier bool* const contains_reference_to_target_space, 11497509954404d031594b2ecbda607314d169d512eMathieu Chartier collector::GarbageCollector* collector) 11597509954404d031594b2ecbda607314d169d512eMathieu Chartier : collector_(collector), target_space_(target_space), 11638e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi contains_reference_to_target_space_(contains_reference_to_target_space) {} 11738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 11890443477f9a0061581c420775ce3b7eeae7468bcMathieu Chartier void operator()(mirror::Object* obj) const REQUIRES(Locks::heap_bitmap_lock_) 11990443477f9a0061581c420775ce3b7eeae7468bcMathieu Chartier SHARED_REQUIRES(Locks::mutator_lock_) { 12097509954404d031594b2ecbda607314d169d512eMathieu Chartier RememberedSetReferenceVisitor visitor(target_space_, contains_reference_to_target_space_, 12197509954404d031594b2ecbda607314d169d512eMathieu Chartier collector_); 122059ef3ddb2088f926ac452889e0953fdcd646a5eMathieu Chartier obj->VisitReferences(visitor, visitor); 12338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi } 12438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 12538e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi private: 12697509954404d031594b2ecbda607314d169d512eMathieu Chartier collector::GarbageCollector* const collector_; 12738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi space::ContinuousSpace* const target_space_; 12838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi bool* const contains_reference_to_target_space_; 12938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi}; 13038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 13197509954404d031594b2ecbda607314d169d512eMathieu Chartiervoid RememberedSet::UpdateAndMarkReferences(space::ContinuousSpace* target_space, 13297509954404d031594b2ecbda607314d169d512eMathieu Chartier collector::GarbageCollector* collector) { 13338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi CardTable* card_table = heap_->GetCardTable(); 13438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi bool contains_reference_to_target_space = false; 13597509954404d031594b2ecbda607314d169d512eMathieu Chartier RememberedSetObjectVisitor obj_visitor(target_space, &contains_reference_to_target_space, 13697509954404d031594b2ecbda607314d169d512eMathieu Chartier collector); 137a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier ContinuousSpaceBitmap* bitmap = space_->GetLiveBitmap(); 13838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi CardSet remove_card_set; 13913735955f39b3b304c37d2b2840663c131262c18Ian Rogers for (uint8_t* const card_addr : dirty_cards_) { 14038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi contains_reference_to_target_space = false; 14138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi uintptr_t start = reinterpret_cast<uintptr_t>(card_table->AddrFromCard(card_addr)); 14238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi DCHECK(space_->HasAddress(reinterpret_cast<mirror::Object*>(start))); 14338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi bitmap->VisitMarkedRange(start, start + CardTable::kCardSize, obj_visitor); 14438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi if (!contains_reference_to_target_space) { 14538e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi // It was in the dirty card set, but it didn't actually contain 14638e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi // a reference to the target space. So, remove it from the dirty 14738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi // card set so we won't have to scan it again (unless it gets 14838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi // dirty again.) 14938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi remove_card_set.insert(card_addr); 15038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi } 15138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi } 15238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 15338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi // Remove the cards that didn't contain a reference to the target 15438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi // space from the dirty card set. 15513735955f39b3b304c37d2b2840663c131262c18Ian Rogers for (uint8_t* const card_addr : remove_card_set) { 15638e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi DCHECK(dirty_cards_.find(card_addr) != dirty_cards_.end()); 15738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi dirty_cards_.erase(card_addr); 15838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi } 15938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi} 16038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 16138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchivoid RememberedSet::Dump(std::ostream& os) { 16238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi CardTable* card_table = heap_->GetCardTable(); 16338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi os << "RememberedSet dirty cards: ["; 16413735955f39b3b304c37d2b2840663c131262c18Ian Rogers for (const uint8_t* card_addr : dirty_cards_) { 16538e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi auto start = reinterpret_cast<uintptr_t>(card_table->AddrFromCard(card_addr)); 16638e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi auto end = start + CardTable::kCardSize; 16738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi os << reinterpret_cast<void*>(start) << "-" << reinterpret_cast<void*>(end) << "\n"; 16838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi } 16938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi os << "]"; 17038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi} 17138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 17238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchivoid RememberedSet::AssertAllDirtyCardsAreWithinSpace() const { 17338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi CardTable* card_table = heap_->GetCardTable(); 17413735955f39b3b304c37d2b2840663c131262c18Ian Rogers for (const uint8_t* card_addr : dirty_cards_) { 17513735955f39b3b304c37d2b2840663c131262c18Ian Rogers auto start = reinterpret_cast<uint8_t*>(card_table->AddrFromCard(card_addr)); 17638e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi auto end = start + CardTable::kCardSize; 177c93c530efc175954160c3834c93961a1a946a35aHiroshi Yamauchi DCHECK_LE(space_->Begin(), start); 178c93c530efc175954160c3834c93961a1a946a35aHiroshi Yamauchi DCHECK_LE(end, space_->Limit()); 17938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi } 18038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi} 18138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 18238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi} // namespace accounting 18338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi} // namespace gc 18438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi} // namespace art 185