remembered_set.cc revision eb837eb7c27e789bc7b05f474be9aa119f2fd99f
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 4413735955f39b3b304c37d2b2840663c131262c18Ian Rogers void operator()(uint8_t* card, uint8_t expected_value, uint8_t new_value) const { 456a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan Rogers UNUSED(new_value); 4638e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi if (expected_value == CardTable::kCardDirty) { 4738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi dirty_cards_->insert(card); 4838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi } 4938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi } 5038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 5138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi private: 5238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi RememberedSet::CardSet* const dirty_cards_; 5338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi}; 5438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 5538e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchivoid RememberedSet::ClearCards() { 5638e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi CardTable* card_table = GetHeap()->GetCardTable(); 5738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi RememberedSetCardVisitor card_visitor(&dirty_cards_); 5838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi // Clear dirty cards in the space and insert them into the dirty card set. 5938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi card_table->ModifyCardsAtomic(space_->Begin(), space_->End(), AgeCardVisitor(), card_visitor); 6038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi} 6138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 6238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchiclass RememberedSetReferenceVisitor { 6338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi public: 6497509954404d031594b2ecbda607314d169d512eMathieu Chartier RememberedSetReferenceVisitor(space::ContinuousSpace* target_space, 6597509954404d031594b2ecbda607314d169d512eMathieu Chartier bool* const contains_reference_to_target_space, 6697509954404d031594b2ecbda607314d169d512eMathieu Chartier collector::GarbageCollector* collector) 6797509954404d031594b2ecbda607314d169d512eMathieu Chartier : collector_(collector), target_space_(target_space), 6838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi contains_reference_to_target_space_(contains_reference_to_target_space) {} 6938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 70da7c650022a974be10e2f00fa07d5109e3d8826fMathieu Chartier void operator()(mirror::Object* obj, MemberOffset offset, bool is_static ATTRIBUTE_UNUSED) const 7190443477f9a0061581c420775ce3b7eeae7468bcMathieu Chartier SHARED_REQUIRES(Locks::mutator_lock_) { 723b05e9ba874449dbff65b01b8781001f7d93eea6Mathieu Chartier DCHECK(obj != nullptr); 73407f702da4f867c074fc3c8c688b8f8c32279effMathieu Chartier mirror::HeapReference<mirror::Object>* ref_ptr = obj->GetFieldObjectReferenceAddr(offset); 74407f702da4f867c074fc3c8c688b8f8c32279effMathieu Chartier if (target_space_->HasAddress(ref_ptr->AsMirrorPtr())) { 75407f702da4f867c074fc3c8c688b8f8c32279effMathieu Chartier *contains_reference_to_target_space_ = true; 7697509954404d031594b2ecbda607314d169d512eMathieu Chartier collector_->MarkHeapReference(ref_ptr); 77407f702da4f867c074fc3c8c688b8f8c32279effMathieu Chartier DCHECK(!target_space_->HasAddress(ref_ptr->AsMirrorPtr())); 7838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi } 7938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi } 8038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 814db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi void operator()(mirror::Class* klass, mirror::Reference* ref) const 82da7c650022a974be10e2f00fa07d5109e3d8826fMathieu Chartier SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::heap_bitmap_lock_) { 834db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi if (target_space_->HasAddress(ref->GetReferent())) { 844db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi *contains_reference_to_target_space_ = true; 8597509954404d031594b2ecbda607314d169d512eMathieu Chartier collector_->DelayReferenceReferent(klass, ref); 864db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi } 874db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi } 884db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi 89da7c650022a974be10e2f00fa07d5109e3d8826fMathieu Chartier void VisitRootIfNonNull(mirror::CompressedReference<mirror::Object>* root) const 90da7c650022a974be10e2f00fa07d5109e3d8826fMathieu Chartier SHARED_REQUIRES(Locks::mutator_lock_) { 91eb837eb7c27e789bc7b05f474be9aa119f2fd99fMathieu Chartier if (!root->IsNull()) { 92da7c650022a974be10e2f00fa07d5109e3d8826fMathieu Chartier VisitRoot(root); 93da7c650022a974be10e2f00fa07d5109e3d8826fMathieu Chartier } 94da7c650022a974be10e2f00fa07d5109e3d8826fMathieu Chartier } 95da7c650022a974be10e2f00fa07d5109e3d8826fMathieu Chartier 96da7c650022a974be10e2f00fa07d5109e3d8826fMathieu Chartier void VisitRoot(mirror::CompressedReference<mirror::Object>* root) const 97da7c650022a974be10e2f00fa07d5109e3d8826fMathieu Chartier SHARED_REQUIRES(Locks::mutator_lock_) { 9839089124ceac46a45f17b8261a09b88a9606bb97Mathieu Chartier if (target_space_->HasAddress(root->AsMirrorPtr())) { 9939089124ceac46a45f17b8261a09b88a9606bb97Mathieu Chartier *contains_reference_to_target_space_ = true; 10039089124ceac46a45f17b8261a09b88a9606bb97Mathieu Chartier root->Assign(collector_->MarkObject(root->AsMirrorPtr())); 10139089124ceac46a45f17b8261a09b88a9606bb97Mathieu Chartier DCHECK(!target_space_->HasAddress(root->AsMirrorPtr())); 10239089124ceac46a45f17b8261a09b88a9606bb97Mathieu Chartier } 103da7c650022a974be10e2f00fa07d5109e3d8826fMathieu Chartier } 104da7c650022a974be10e2f00fa07d5109e3d8826fMathieu Chartier 10538e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi private: 10697509954404d031594b2ecbda607314d169d512eMathieu Chartier collector::GarbageCollector* const collector_; 10738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi space::ContinuousSpace* const target_space_; 10838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi bool* const contains_reference_to_target_space_; 10938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi}; 11038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 11138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchiclass RememberedSetObjectVisitor { 11238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi public: 11397509954404d031594b2ecbda607314d169d512eMathieu Chartier RememberedSetObjectVisitor(space::ContinuousSpace* target_space, 11497509954404d031594b2ecbda607314d169d512eMathieu Chartier bool* const contains_reference_to_target_space, 11597509954404d031594b2ecbda607314d169d512eMathieu Chartier collector::GarbageCollector* collector) 11697509954404d031594b2ecbda607314d169d512eMathieu Chartier : collector_(collector), target_space_(target_space), 11738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi contains_reference_to_target_space_(contains_reference_to_target_space) {} 11838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 11990443477f9a0061581c420775ce3b7eeae7468bcMathieu Chartier void operator()(mirror::Object* obj) const REQUIRES(Locks::heap_bitmap_lock_) 12090443477f9a0061581c420775ce3b7eeae7468bcMathieu Chartier SHARED_REQUIRES(Locks::mutator_lock_) { 12197509954404d031594b2ecbda607314d169d512eMathieu Chartier RememberedSetReferenceVisitor visitor(target_space_, contains_reference_to_target_space_, 12297509954404d031594b2ecbda607314d169d512eMathieu Chartier collector_); 1234db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi obj->VisitReferences<kMovingClasses>(visitor, visitor); 12438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi } 12538e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 12638e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi private: 12797509954404d031594b2ecbda607314d169d512eMathieu Chartier collector::GarbageCollector* const collector_; 12838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi space::ContinuousSpace* const target_space_; 12938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi bool* const contains_reference_to_target_space_; 13038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi}; 13138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 13297509954404d031594b2ecbda607314d169d512eMathieu Chartiervoid RememberedSet::UpdateAndMarkReferences(space::ContinuousSpace* target_space, 13397509954404d031594b2ecbda607314d169d512eMathieu Chartier collector::GarbageCollector* collector) { 13438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi CardTable* card_table = heap_->GetCardTable(); 13538e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi bool contains_reference_to_target_space = false; 13697509954404d031594b2ecbda607314d169d512eMathieu Chartier RememberedSetObjectVisitor obj_visitor(target_space, &contains_reference_to_target_space, 13797509954404d031594b2ecbda607314d169d512eMathieu Chartier collector); 138a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier ContinuousSpaceBitmap* bitmap = space_->GetLiveBitmap(); 13938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi CardSet remove_card_set; 14013735955f39b3b304c37d2b2840663c131262c18Ian Rogers for (uint8_t* const card_addr : dirty_cards_) { 14138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi contains_reference_to_target_space = false; 14238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi uintptr_t start = reinterpret_cast<uintptr_t>(card_table->AddrFromCard(card_addr)); 14338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi DCHECK(space_->HasAddress(reinterpret_cast<mirror::Object*>(start))); 14438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi bitmap->VisitMarkedRange(start, start + CardTable::kCardSize, obj_visitor); 14538e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi if (!contains_reference_to_target_space) { 14638e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi // It was in the dirty card set, but it didn't actually contain 14738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi // a reference to the target space. So, remove it from the dirty 14838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi // card set so we won't have to scan it again (unless it gets 14938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi // dirty again.) 15038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi remove_card_set.insert(card_addr); 15138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi } 15238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi } 15338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 15438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi // Remove the cards that didn't contain a reference to the target 15538e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi // space from the dirty card set. 15613735955f39b3b304c37d2b2840663c131262c18Ian Rogers for (uint8_t* const card_addr : remove_card_set) { 15738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi DCHECK(dirty_cards_.find(card_addr) != dirty_cards_.end()); 15838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi dirty_cards_.erase(card_addr); 15938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi } 16038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi} 16138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 16238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchivoid RememberedSet::Dump(std::ostream& os) { 16338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi CardTable* card_table = heap_->GetCardTable(); 16438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi os << "RememberedSet dirty cards: ["; 16513735955f39b3b304c37d2b2840663c131262c18Ian Rogers for (const uint8_t* card_addr : dirty_cards_) { 16638e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi auto start = reinterpret_cast<uintptr_t>(card_table->AddrFromCard(card_addr)); 16738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi auto end = start + CardTable::kCardSize; 16838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi os << reinterpret_cast<void*>(start) << "-" << reinterpret_cast<void*>(end) << "\n"; 16938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi } 17038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi os << "]"; 17138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi} 17238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 17338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchivoid RememberedSet::AssertAllDirtyCardsAreWithinSpace() const { 17438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi CardTable* card_table = heap_->GetCardTable(); 17513735955f39b3b304c37d2b2840663c131262c18Ian Rogers for (const uint8_t* card_addr : dirty_cards_) { 17613735955f39b3b304c37d2b2840663c131262c18Ian Rogers auto start = reinterpret_cast<uint8_t*>(card_table->AddrFromCard(card_addr)); 17738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi auto end = start + CardTable::kCardSize; 178c93c530efc175954160c3834c93961a1a946a35aHiroshi Yamauchi DCHECK_LE(space_->Begin(), start); 179c93c530efc175954160c3834c93961a1a946a35aHiroshi Yamauchi DCHECK_LE(end, space_->Limit()); 18038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi } 18138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi} 18238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 18338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi} // namespace accounting 18438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi} // namespace gc 18538e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi} // namespace art 186