remembered_set.cc revision 4db7449c0065971ec3a64ca04aeb64cfd2e802f0
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 1938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "base/stl_util.h" 2038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "card_table-inl.h" 2138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "heap_bitmap.h" 2238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "gc/collector/mark_sweep.h" 2338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "gc/collector/mark_sweep-inl.h" 2438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "gc/collector/semi_space.h" 2538e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "gc/heap.h" 2638e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "gc/space/space.h" 2738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "mirror/art_field-inl.h" 2838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "mirror/object-inl.h" 2938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "mirror/class-inl.h" 3038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "mirror/object_array-inl.h" 3138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "space_bitmap-inl.h" 3238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "thread.h" 3338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi#include "UniquePtr.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 4438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi void operator()(byte* card, byte expected_value, byte new_value) 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: 63407f702da4f867c074fc3c8c688b8f8c32279effMathieu Chartier RememberedSetReferenceVisitor(MarkHeapReferenceCallback* callback, 644db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi DelayReferenceReferentCallback* ref_callback, 65407f702da4f867c074fc3c8c688b8f8c32279effMathieu Chartier space::ContinuousSpace* target_space, 6638e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi bool* const contains_reference_to_target_space, void* arg) 674db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi : callback_(callback), ref_callback_(ref_callback), target_space_(target_space), arg_(arg), 6838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi contains_reference_to_target_space_(contains_reference_to_target_space) {} 6938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 70407f702da4f867c074fc3c8c688b8f8c32279effMathieu Chartier void operator()(mirror::Object* obj, MemberOffset offset, bool /* is_static */) const 7138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi SHARED_LOCKS_REQUIRED(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; 76407f702da4f867c074fc3c8c688b8f8c32279effMathieu Chartier callback_(ref_ptr, arg_); 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 824db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) 834db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) { 844db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi if (target_space_->HasAddress(ref->GetReferent())) { 854db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi *contains_reference_to_target_space_ = true; 864db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi ref_callback_(klass, ref, arg_); 874db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi } 884db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi } 894db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi 9038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi private: 91407f702da4f867c074fc3c8c688b8f8c32279effMathieu Chartier MarkHeapReferenceCallback* const callback_; 924db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi DelayReferenceReferentCallback* const ref_callback_; 9338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi space::ContinuousSpace* const target_space_; 9438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi void* const arg_; 9538e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi bool* const contains_reference_to_target_space_; 9638e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi}; 9738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 9838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchiclass RememberedSetObjectVisitor { 9938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi public: 100407f702da4f867c074fc3c8c688b8f8c32279effMathieu Chartier RememberedSetObjectVisitor(MarkHeapReferenceCallback* callback, 1014db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi DelayReferenceReferentCallback* ref_callback, 102407f702da4f867c074fc3c8c688b8f8c32279effMathieu Chartier space::ContinuousSpace* target_space, 10338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi bool* const contains_reference_to_target_space, void* arg) 1044db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi : callback_(callback), ref_callback_(ref_callback), target_space_(target_space), arg_(arg), 10538e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi contains_reference_to_target_space_(contains_reference_to_target_space) {} 10638e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 10738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi void operator()(mirror::Object* obj) const EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) 10838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 1094db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi RememberedSetReferenceVisitor visitor(callback_, ref_callback_, target_space_, 1104db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi contains_reference_to_target_space_, arg_); 1114db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi obj->VisitReferences<kMovingClasses>(visitor, visitor); 11238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi } 11338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 11438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi private: 115407f702da4f867c074fc3c8c688b8f8c32279effMathieu Chartier MarkHeapReferenceCallback* const callback_; 1164db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi DelayReferenceReferentCallback* const ref_callback_; 11738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi space::ContinuousSpace* const target_space_; 11838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi void* const arg_; 11938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi bool* const contains_reference_to_target_space_; 12038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi}; 12138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 122407f702da4f867c074fc3c8c688b8f8c32279effMathieu Chartiervoid RememberedSet::UpdateAndMarkReferences(MarkHeapReferenceCallback* callback, 1234db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi DelayReferenceReferentCallback* ref_callback, 12438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi space::ContinuousSpace* target_space, void* arg) { 12538e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi CardTable* card_table = heap_->GetCardTable(); 12638e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi bool contains_reference_to_target_space = false; 1274db7449c0065971ec3a64ca04aeb64cfd2e802f0Hiroshi Yamauchi RememberedSetObjectVisitor obj_visitor(callback, ref_callback, target_space, 12838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi &contains_reference_to_target_space, arg); 129a8e8f9c0a8e259a807d7b99a148d14104c24209dMathieu Chartier ContinuousSpaceBitmap* bitmap = space_->GetLiveBitmap(); 13038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi CardSet remove_card_set; 13138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi for (byte* const card_addr : dirty_cards_) { 13238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi contains_reference_to_target_space = false; 13338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi uintptr_t start = reinterpret_cast<uintptr_t>(card_table->AddrFromCard(card_addr)); 13438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi DCHECK(space_->HasAddress(reinterpret_cast<mirror::Object*>(start))); 13538e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi bitmap->VisitMarkedRange(start, start + CardTable::kCardSize, obj_visitor); 13638e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi if (!contains_reference_to_target_space) { 13738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi // It was in the dirty card set, but it didn't actually contain 13838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi // a reference to the target space. So, remove it from the dirty 13938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi // card set so we won't have to scan it again (unless it gets 14038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi // dirty again.) 14138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi remove_card_set.insert(card_addr); 14238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi } 14338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi } 14438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 14538e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi // Remove the cards that didn't contain a reference to the target 14638e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi // space from the dirty card set. 14738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi for (byte* const card_addr : remove_card_set) { 14838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi DCHECK(dirty_cards_.find(card_addr) != dirty_cards_.end()); 14938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi dirty_cards_.erase(card_addr); 15038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi } 15138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi} 15238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 15338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchivoid RememberedSet::Dump(std::ostream& os) { 15438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi CardTable* card_table = heap_->GetCardTable(); 15538e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi os << "RememberedSet dirty cards: ["; 15638e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi for (const byte* card_addr : dirty_cards_) { 15738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi auto start = reinterpret_cast<uintptr_t>(card_table->AddrFromCard(card_addr)); 15838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi auto end = start + CardTable::kCardSize; 15938e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi os << reinterpret_cast<void*>(start) << "-" << reinterpret_cast<void*>(end) << "\n"; 16038e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi } 16138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi os << "]"; 16238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi} 16338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 16438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchivoid RememberedSet::AssertAllDirtyCardsAreWithinSpace() const { 16538e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi CardTable* card_table = heap_->GetCardTable(); 16638e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi for (const byte* card_addr : dirty_cards_) { 16738e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi auto start = reinterpret_cast<byte*>(card_table->AddrFromCard(card_addr)); 16838e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi auto end = start + CardTable::kCardSize; 169c93c530efc175954160c3834c93961a1a946a35aHiroshi Yamauchi DCHECK_LE(space_->Begin(), start); 170c93c530efc175954160c3834c93961a1a946a35aHiroshi Yamauchi DCHECK_LE(end, space_->Limit()); 17138e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi } 17238e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi} 17338e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi 17438e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi} // namespace accounting 17538e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi} // namespace gc 17638e68e9978236db87c9008bbe47db80525d2fa16Hiroshi Yamauchi} // namespace art 177