From 38e68e9978236db87c9008bbe47db80525d2fa16 Mon Sep 17 00:00:00 2001 From: Hiroshi Yamauchi Date: Fri, 7 Mar 2014 13:59:08 -0800 Subject: [PATCH] Use the card table to speed up the GSS collector. Scan only dirty cards, as opposed to the whole space, to find references from the non-moving spaces to the bump pointer spaces at bump pointer space only collections. With this change, the Ritz MemAllocTest speeds up by 8-10% on host and 2-3% on N4. The Ritz EvaluateFibonacci speeds up by 8% and its average pause time is reduced by 43% on N4. Bug: 11650816 Change-Id: I1eefe75776bc37e24673b301ffa65a25f9bd4cde --- runtime/Android.mk | 1 + runtime/gc/accounting/remembered_set.cc | 164 ++++++++++++++++++++++++++++++++ runtime/gc/accounting/remembered_set.h | 85 +++++++++++++++++ runtime/gc/collector/immune_region.cc | 7 +- runtime/gc/collector/mark_sweep.cc | 4 +- runtime/gc/collector/semi_space.cc | 91 ++++++++++++++++-- runtime/gc/collector/semi_space.h | 6 ++ runtime/gc/heap-inl.h | 14 +++ runtime/gc/heap.cc | 77 ++++++++++++++- runtime/gc/heap.h | 10 +- 10 files changed, 444 insertions(+), 15 deletions(-) create mode 100644 runtime/gc/accounting/remembered_set.cc create mode 100644 runtime/gc/accounting/remembered_set.h diff --git a/runtime/Android.mk b/runtime/Android.mk index 115363478..cca7d0303 100644 --- a/runtime/Android.mk +++ b/runtime/Android.mk @@ -50,6 +50,7 @@ LIBART_COMMON_SRC_FILES := \ gc/accounting/gc_allocator.cc \ gc/accounting/heap_bitmap.cc \ gc/accounting/mod_union_table.cc \ + gc/accounting/remembered_set.cc \ gc/accounting/space_bitmap.cc \ gc/collector/garbage_collector.cc \ gc/collector/immune_region.cc \ diff --git a/runtime/gc/accounting/remembered_set.cc b/runtime/gc/accounting/remembered_set.cc new file mode 100644 index 000000000..e6508dc1c --- /dev/null +++ b/runtime/gc/accounting/remembered_set.cc @@ -0,0 +1,164 @@ +/* + * Copyright (C) 2014 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "remembered_set.h" + +#include "base/stl_util.h" +#include "card_table-inl.h" +#include "heap_bitmap.h" +#include "gc/collector/mark_sweep.h" +#include "gc/collector/mark_sweep-inl.h" +#include "gc/collector/semi_space.h" +#include "gc/heap.h" +#include "gc/space/space.h" +#include "mirror/art_field-inl.h" +#include "mirror/object-inl.h" +#include "mirror/class-inl.h" +#include "mirror/object_array-inl.h" +#include "space_bitmap-inl.h" +#include "thread.h" +#include "UniquePtr.h" + +namespace art { +namespace gc { +namespace accounting { + +class RememberedSetCardVisitor { + public: + explicit RememberedSetCardVisitor(RememberedSet::CardSet* const dirty_cards) + : dirty_cards_(dirty_cards) {} + + void operator()(byte* card, byte expected_value, byte new_value) const { + if (expected_value == CardTable::kCardDirty) { + dirty_cards_->insert(card); + } + } + + private: + RememberedSet::CardSet* const dirty_cards_; +}; + +void RememberedSet::ClearCards() { + CardTable* card_table = GetHeap()->GetCardTable(); + RememberedSetCardVisitor card_visitor(&dirty_cards_); + // Clear dirty cards in the space and insert them into the dirty card set. + card_table->ModifyCardsAtomic(space_->Begin(), space_->End(), AgeCardVisitor(), card_visitor); +} + +class RememberedSetReferenceVisitor { + public: + RememberedSetReferenceVisitor(MarkObjectCallback* callback, space::ContinuousSpace* target_space, + bool* const contains_reference_to_target_space, void* arg) + : callback_(callback), target_space_(target_space), arg_(arg), + contains_reference_to_target_space_(contains_reference_to_target_space) {} + + void operator()(mirror::Object* obj, mirror::Object* ref, + const MemberOffset& offset, bool /* is_static */) const + SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { + if (ref != nullptr) { + if (target_space_->HasAddress(ref)) { + *contains_reference_to_target_space_ = true; + mirror::Object* new_ref = callback_(ref, arg_); + DCHECK(!target_space_->HasAddress(new_ref)); + if (new_ref != ref) { + obj->SetFieldObjectWithoutWriteBarrier(offset, new_ref, false); + } + } + } + } + + private: + MarkObjectCallback* const callback_; + space::ContinuousSpace* const target_space_; + void* const arg_; + bool* const contains_reference_to_target_space_; +}; + +class RememberedSetObjectVisitor { + public: + RememberedSetObjectVisitor(MarkObjectCallback* callback, space::ContinuousSpace* target_space, + bool* const contains_reference_to_target_space, void* arg) + : callback_(callback), target_space_(target_space), arg_(arg), + contains_reference_to_target_space_(contains_reference_to_target_space) {} + + void operator()(mirror::Object* obj) const EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) + SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { + DCHECK(obj != NULL); + RememberedSetReferenceVisitor ref_visitor(callback_, target_space_, + contains_reference_to_target_space_, arg_); + collector::MarkSweep::VisitObjectReferences(obj, ref_visitor, true); + } + + private: + MarkObjectCallback* const callback_; + space::ContinuousSpace* const target_space_; + void* const arg_; + bool* const contains_reference_to_target_space_; +}; + +void RememberedSet::UpdateAndMarkReferences(MarkObjectCallback* callback, + space::ContinuousSpace* target_space, void* arg) { + CardTable* card_table = heap_->GetCardTable(); + bool contains_reference_to_target_space = false; + RememberedSetObjectVisitor obj_visitor(callback, target_space, + &contains_reference_to_target_space, arg); + SpaceBitmap* bitmap = space_->GetLiveBitmap(); + CardSet remove_card_set; + for (byte* const card_addr : dirty_cards_) { + contains_reference_to_target_space = false; + uintptr_t start = reinterpret_cast(card_table->AddrFromCard(card_addr)); + DCHECK(space_->HasAddress(reinterpret_cast(start))); + bitmap->VisitMarkedRange(start, start + CardTable::kCardSize, obj_visitor); + if (!contains_reference_to_target_space) { + // It was in the dirty card set, but it didn't actually contain + // a reference to the target space. So, remove it from the dirty + // card set so we won't have to scan it again (unless it gets + // dirty again.) + remove_card_set.insert(card_addr); + } + } + + // Remove the cards that didn't contain a reference to the target + // space from the dirty card set. + for (byte* const card_addr : remove_card_set) { + DCHECK(dirty_cards_.find(card_addr) != dirty_cards_.end()); + dirty_cards_.erase(card_addr); + } +} + +void RememberedSet::Dump(std::ostream& os) { + CardTable* card_table = heap_->GetCardTable(); + os << "RememberedSet dirty cards: ["; + for (const byte* card_addr : dirty_cards_) { + auto start = reinterpret_cast(card_table->AddrFromCard(card_addr)); + auto end = start + CardTable::kCardSize; + os << reinterpret_cast(start) << "-" << reinterpret_cast(end) << "\n"; + } + os << "]"; +} + +void RememberedSet::AssertAllDirtyCardsAreWithinSpace() const { + CardTable* card_table = heap_->GetCardTable(); + for (const byte* card_addr : dirty_cards_) { + auto start = reinterpret_cast(card_table->AddrFromCard(card_addr)); + auto end = start + CardTable::kCardSize; + DCHECK(space_->Begin() <= start && end <= space_->End()); + } +} + +} // namespace accounting +} // namespace gc +} // namespace art diff --git a/runtime/gc/accounting/remembered_set.h b/runtime/gc/accounting/remembered_set.h new file mode 100644 index 000000000..92feeb1f0 --- /dev/null +++ b/runtime/gc/accounting/remembered_set.h @@ -0,0 +1,85 @@ +/* + * Copyright (C) 2014 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef ART_RUNTIME_GC_ACCOUNTING_REMEMBERED_SET_H_ +#define ART_RUNTIME_GC_ACCOUNTING_REMEMBERED_SET_H_ + +#include "gc_allocator.h" +#include "globals.h" +#include "object_callbacks.h" +#include "safe_map.h" + +#include +#include + +namespace art { +namespace gc { + +namespace collector { + class MarkSweep; +} // namespace collector +namespace space { + class ContinuousSpace; +} // namespace space + +class Heap; + +namespace accounting { + +// The remembered set keeps track of cards that may contain references +// from the free list spaces to the bump pointer spaces. +class RememberedSet { + public: + typedef std::set, GcAllocator > CardSet; + + explicit RememberedSet(const std::string& name, Heap* heap, space::ContinuousSpace* space) + : name_(name), heap_(heap), space_(space) {} + + // Clear dirty cards and add them to the dirty card set. + void ClearCards(); + + // Mark through all references to the target space. + void UpdateAndMarkReferences(MarkObjectCallback* callback, + space::ContinuousSpace* target_space, void* arg) + EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) + SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); + + void Dump(std::ostream& os); + + space::ContinuousSpace* GetSpace() { + return space_; + } + Heap* GetHeap() const { + return heap_; + } + const std::string& GetName() const { + return name_; + } + void AssertAllDirtyCardsAreWithinSpace() const; + + private: + const std::string name_; + Heap* const heap_; + space::ContinuousSpace* const space_; + + CardSet dirty_cards_; +}; + +} // namespace accounting +} // namespace gc +} // namespace art + +#endif // ART_RUNTIME_GC_ACCOUNTING_REMEMBERED_SET_H_ diff --git a/runtime/gc/collector/immune_region.cc b/runtime/gc/collector/immune_region.cc index 9e6538456..70a62133a 100644 --- a/runtime/gc/collector/immune_region.cc +++ b/runtime/gc/collector/immune_region.cc @@ -56,9 +56,14 @@ bool ImmuneRegion::AddContinuousSpace(space::ContinuousSpace* space) { } bool ImmuneRegion::ContainsSpace(const space::ContinuousSpace* space) const { - return + bool contains = begin_ <= reinterpret_cast(space->Begin()) && end_ >= reinterpret_cast(space->Limit()); + if (kIsDebugBuild && contains) { + // A bump pointer space shoult not be in the immune region. + DCHECK(space->GetType() != space::kSpaceTypeBumpPointerSpace); + } + return contains; } } // namespace collector diff --git a/runtime/gc/collector/mark_sweep.cc b/runtime/gc/collector/mark_sweep.cc index 4f3ad3254..fe5a75f40 100644 --- a/runtime/gc/collector/mark_sweep.cc +++ b/runtime/gc/collector/mark_sweep.cc @@ -201,7 +201,7 @@ void MarkSweep::PreCleanCards() { Thread* self = Thread::Current(); CHECK(!Locks::mutator_lock_->IsExclusiveHeld(self)); // Process dirty cards and add dirty cards to mod union tables, also ages cards. - heap_->ProcessCards(timings_); + heap_->ProcessCards(timings_, false); // The checkpoint root marking is required to avoid a race condition which occurs if the // following happens during a reference write: // 1. mutator dirties the card (write barrier) @@ -241,7 +241,7 @@ void MarkSweep::MarkingPhase() { FindDefaultMarkBitmap(); // Process dirty cards and add dirty cards to mod union tables. - heap_->ProcessCards(timings_); + heap_->ProcessCards(timings_, false); // Need to do this before the checkpoint since we don't want any threads to add references to // the live stack during the recursive mark. diff --git a/runtime/gc/collector/semi_space.cc b/runtime/gc/collector/semi_space.cc index 23b155cff..5b9c39795 100644 --- a/runtime/gc/collector/semi_space.cc +++ b/runtime/gc/collector/semi_space.cc @@ -27,6 +27,7 @@ #include "base/timing_logger.h" #include "gc/accounting/heap_bitmap.h" #include "gc/accounting/mod_union_table.h" +#include "gc/accounting/remembered_set.h" #include "gc/accounting/space_bitmap-inl.h" #include "gc/heap.h" #include "gc/space/bump_pointer_space.h" @@ -182,7 +183,7 @@ void SemiSpace::MarkingPhase() { // Assume the cleared space is already empty. BindBitmaps(); // Process dirty cards and add dirty cards to mod-union tables. - heap_->ProcessCards(timings_); + heap_->ProcessCards(timings_, kUseRememberedSet && generational_); // Clear the whole card table since we can not get any additional dirty cards during the // paused GC. This saves memory but only works for pause the world collectors. timings_.NewSplit("ClearCardTable"); @@ -214,13 +215,29 @@ void SemiSpace::UpdateAndMarkModUnion() { "UpdateAndMarkImageModUnionTable", &timings_); table->UpdateAndMarkReferences(MarkObjectCallback, this); + } else if (heap_->FindRememberedSetFromSpace(space) != nullptr) { + DCHECK(kUseRememberedSet); + // If a bump pointer space only collection, the non-moving + // space is added to the immune space. The non-moving space + // doesn't have a mod union table, but has a remembered + // set. Its dirty cards will be scanned later in + // MarkReachableObjects(). + DCHECK(generational_ && !whole_heap_collection_ && + (space == heap_->GetNonMovingSpace() || space == heap_->GetPrimaryFreeListSpace())) + << "Space " << space->GetName() << " " + << "generational_=" << generational_ << " " + << "whole_heap_collection_=" << whole_heap_collection_ << " "; } else { + DCHECK(!kUseRememberedSet); // If a bump pointer space only collection, the non-moving // space is added to the immune space. But the non-moving // space doesn't have a mod union table. Instead, its live // bitmap will be scanned later in MarkReachableObjects(). DCHECK(generational_ && !whole_heap_collection_ && - (space == heap_->GetNonMovingSpace() || space == heap_->GetPrimaryFreeListSpace())); + (space == heap_->GetNonMovingSpace() || space == heap_->GetPrimaryFreeListSpace())) + << "Space " << space->GetName() << " " + << "generational_=" << generational_ << " " + << "whole_heap_collection_=" << whole_heap_collection_ << " "; } } } @@ -240,6 +257,42 @@ class SemiSpaceScanObjectVisitor { SemiSpace* const semi_space_; }; +// Used to verify that there's no references to the from-space. +class SemiSpaceVerifyNoFromSpaceReferencesVisitor { + public: + explicit SemiSpaceVerifyNoFromSpaceReferencesVisitor(space::ContinuousMemMapAllocSpace* from_space) : + from_space_(from_space) {} + + void operator()(Object* obj, Object* ref, const MemberOffset& offset, bool /* is_static */) + const ALWAYS_INLINE { + if (from_space_->HasAddress(ref)) { + Runtime::Current()->GetHeap()->DumpObject(LOG(INFO), obj); + } + DCHECK(!from_space_->HasAddress(ref)); + } + private: + space::ContinuousMemMapAllocSpace* from_space_; +}; + +void SemiSpace::VerifyNoFromSpaceReferences(Object* obj) { + DCHECK(obj != NULL); + DCHECK(!from_space_->HasAddress(obj)) << "Scanning object " << obj << " in from space"; + SemiSpaceVerifyNoFromSpaceReferencesVisitor visitor(from_space_); + MarkSweep::VisitObjectReferences(obj, visitor, kMovingClasses); +} + +class SemiSpaceVerifyNoFromSpaceReferencesObjectVisitor { + public: + explicit SemiSpaceVerifyNoFromSpaceReferencesObjectVisitor(SemiSpace* ss) : semi_space_(ss) {} + void operator()(Object* obj) const + SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_) { + DCHECK(obj != nullptr); + semi_space_->VerifyNoFromSpaceReferences(obj); + } + private: + SemiSpace* const semi_space_; +}; + void SemiSpace::MarkReachableObjects() { timings_.StartSplit("MarkStackAsLive"); accounting::ObjectStack* live_stack = heap_->GetLiveStack(); @@ -250,18 +303,36 @@ void SemiSpace::MarkReachableObjects() { for (auto& space : heap_->GetContinuousSpaces()) { // If the space is immune and has no mod union table (the // non-moving space when the bump pointer space only collection is - // enabled,) then we need to scan its live bitmap as roots + // enabled,) then we need to scan its live bitmap or dirty cards as roots // (including the objects on the live stack which have just marked // in the live bitmap above in MarkAllocStackAsLive().) if (immune_region_.ContainsSpace(space) && heap_->FindModUnionTableFromSpace(space) == nullptr) { DCHECK(generational_ && !whole_heap_collection_ && (space == GetHeap()->GetNonMovingSpace() || space == GetHeap()->GetPrimaryFreeListSpace())); - accounting::SpaceBitmap* live_bitmap = space->GetLiveBitmap(); - SemiSpaceScanObjectVisitor visitor(this); - live_bitmap->VisitMarkedRange(reinterpret_cast(space->Begin()), - reinterpret_cast(space->End()), - visitor); + accounting::RememberedSet* rem_set = heap_->FindRememberedSetFromSpace(space); + if (kUseRememberedSet) { + DCHECK(rem_set != nullptr); + rem_set->UpdateAndMarkReferences(MarkObjectCallback, from_space_, this); + if (kIsDebugBuild) { + // Verify that there are no from-space references that + // remain in the space, that is, the remembered set (and the + // card table) didn't miss any from-space references in the + // space. + accounting::SpaceBitmap* live_bitmap = space->GetLiveBitmap(); + SemiSpaceVerifyNoFromSpaceReferencesObjectVisitor visitor(this); + live_bitmap->VisitMarkedRange(reinterpret_cast(space->Begin()), + reinterpret_cast(space->End()), + visitor); + } + } else { + DCHECK(rem_set == nullptr); + accounting::SpaceBitmap* live_bitmap = space->GetLiveBitmap(); + SemiSpaceScanObjectVisitor visitor(this); + live_bitmap->VisitMarkedRange(reinterpret_cast(space->Begin()), + reinterpret_cast(space->End()), + visitor); + } } } @@ -447,6 +518,10 @@ mirror::Object* SemiSpace::MarkNonForwardedObject(mirror::Object* obj) { } else { GetHeap()->num_bytes_allocated_.FetchAndAdd(bytes_promoted); bytes_promoted_ += bytes_promoted; + // Dirty the card at the destionation as it may contain + // references (including the class pointer) to the bump pointer + // space. + GetHeap()->WriteBarrierEveryFieldOf(forward_address); // Handle the bitmaps marking. accounting::SpaceBitmap* live_bitmap = promo_dest_space->GetLiveBitmap(); DCHECK(live_bitmap != nullptr); diff --git a/runtime/gc/collector/semi_space.h b/runtime/gc/collector/semi_space.h index be7ec05f2..08bfbc485 100644 --- a/runtime/gc/collector/semi_space.h +++ b/runtime/gc/collector/semi_space.h @@ -63,6 +63,9 @@ namespace collector { class SemiSpace : public GarbageCollector { public: + // If true, use remembered sets in the generational mode. + static constexpr bool kUseRememberedSet = true; + explicit SemiSpace(Heap* heap, bool generational = false, const std::string& name_prefix = ""); @@ -100,6 +103,9 @@ class SemiSpace : public GarbageCollector { void ScanObject(mirror::Object* obj) EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_); + void VerifyNoFromSpaceReferences(mirror::Object* obj) + SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_); + // Marks the root set at the start of a garbage collection. void MarkRoots() EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_); diff --git a/runtime/gc/heap-inl.h b/runtime/gc/heap-inl.h index 533e5dfed..6cc44c9e8 100644 --- a/runtime/gc/heap-inl.h +++ b/runtime/gc/heap-inl.h @@ -20,6 +20,8 @@ #include "heap.h" #include "debugger.h" +#include "gc/accounting/card_table-inl.h" +#include "gc/collector/semi_space.h" #include "gc/space/bump_pointer_space-inl.h" #include "gc/space/dlmalloc_space-inl.h" #include "gc/space/large_object_space.h" @@ -75,6 +77,18 @@ inline mirror::Object* Heap::AllocObjectWithAllocator(Thread* self, mirror::Clas obj->SetBrooksPointer(obj); obj->AssertSelfBrooksPointer(); } + if (collector::SemiSpace::kUseRememberedSet && UNLIKELY(allocator == kAllocatorTypeNonMoving)) { + // (Note this if statement will be constant folded away for the + // fast-path quick entry points.) Because SetClass() has no write + // barrier, if a non-moving space allocation, we need a write + // barrier as the class pointer may point to the bump pointer + // space (where the class pointer is an "old-to-young" reference, + // though rare) under the GSS collector with the remembered set + // enabled. We don't need this for kAllocatorTypeRosAlloc/DlMalloc + // cases because we don't directly allocate into the main alloc + // space (besides promotions) under the SS/GSS collector. + WriteBarrierField(obj, mirror::Object::ClassOffset(), klass); + } pre_fence_visitor(obj, usable_size); if (kIsDebugBuild && Runtime::Current()->IsStarted()) { CHECK_LE(obj->SizeOf(), usable_size); diff --git a/runtime/gc/heap.cc b/runtime/gc/heap.cc index 45904ffca..e8ee62f1d 100644 --- a/runtime/gc/heap.cc +++ b/runtime/gc/heap.cc @@ -33,6 +33,7 @@ #include "gc/accounting/heap_bitmap-inl.h" #include "gc/accounting/mod_union_table.h" #include "gc/accounting/mod_union_table-inl.h" +#include "gc/accounting/remembered_set.h" #include "gc/accounting/space_bitmap-inl.h" #include "gc/collector/mark_sweep-inl.h" #include "gc/collector/partial_mark_sweep.h" @@ -161,7 +162,8 @@ Heap::Heap(size_t initial_size, size_t growth_limit, size_t min_free, size_t max } else { if (kMovingCollector) { // We are the zygote, use bump pointer allocation + semi space collector. - desired_collector_type_ = kCollectorTypeSS; + bool generational = post_zygote_collector_type_ == kCollectorTypeGSS; + desired_collector_type_ = generational ? kCollectorTypeGSS : kCollectorTypeSS; } else { desired_collector_type_ = post_zygote_collector_type_; } @@ -279,6 +281,13 @@ Heap::Heap(size_t initial_size, size_t growth_limit, size_t min_free, size_t max CHECK(mod_union_table != nullptr) << "Failed to create image mod-union table"; AddModUnionTable(mod_union_table); + if (collector::SemiSpace::kUseRememberedSet) { + accounting::RememberedSet* non_moving_space_rem_set = + new accounting::RememberedSet("Non-moving space remembered set", this, non_moving_space_); + CHECK(non_moving_space_rem_set != nullptr) << "Failed to create non-moving space remembered set"; + AddRememberedSet(non_moving_space_rem_set); + } + // TODO: Count objects in the image space here. num_bytes_allocated_ = 0; @@ -1469,7 +1478,7 @@ void Heap::ChangeCollector(CollectorType collector_type) { // Special compacting collector which uses sub-optimal bin packing to reduce zygote space size. class ZygoteCompactingCollector FINAL : public collector::SemiSpace { public: - explicit ZygoteCompactingCollector(gc::Heap* heap) : SemiSpace(heap, "zygote collector"), + explicit ZygoteCompactingCollector(gc::Heap* heap) : SemiSpace(heap, false, "zygote collector"), bin_live_bitmap_(nullptr), bin_mark_bitmap_(nullptr) { } @@ -1618,6 +1627,16 @@ void Heap::PreZygoteFork() { // Remove the old space before creating the zygote space since creating the zygote space sets // the old alloc space's bitmaps to nullptr. RemoveSpace(old_alloc_space); + if (collector::SemiSpace::kUseRememberedSet) { + // Sanity bound check. + FindRememberedSetFromSpace(old_alloc_space)->AssertAllDirtyCardsAreWithinSpace(); + // Remove the remembered set for the now zygote space (the old + // non-moving space). Note now that we have compacted objects into + // the zygote space, the data in the remembered set is no longer + // needed. The zygote space will instead have a mod-union table + // from this point on. + RemoveRememberedSet(old_alloc_space); + } space::ZygoteSpace* zygote_space = old_alloc_space->CreateZygoteSpace("alloc space", low_memory_mode_, &main_space_); @@ -1640,6 +1659,13 @@ void Heap::PreZygoteFork() { new accounting::ModUnionTableCardCache("zygote space mod-union table", this, zygote_space); CHECK(mod_union_table != nullptr) << "Failed to create zygote space mod-union table"; AddModUnionTable(mod_union_table); + if (collector::SemiSpace::kUseRememberedSet) { + // Add a new remembered set for the new main space. + accounting::RememberedSet* main_space_rem_set = + new accounting::RememberedSet("Main space remembered set", this, main_space_); + CHECK(main_space_rem_set != nullptr) << "Failed to create main space remembered set"; + AddRememberedSet(main_space_rem_set); + } // Can't use RosAlloc for non moving space due to thread local buffers. // TODO: Non limited space for non-movable objects? MemMap* mem_map = post_zygote_non_moving_space_mem_map_.release(); @@ -1650,6 +1676,15 @@ void Heap::PreZygoteFork() { CHECK(new_non_moving_space != nullptr) << "Failed to create new non-moving space"; new_non_moving_space->SetFootprintLimit(new_non_moving_space->Capacity()); non_moving_space_ = new_non_moving_space; + if (collector::SemiSpace::kUseRememberedSet) { + // Add a new remembered set for the post-zygote non-moving space. + accounting::RememberedSet* post_zygote_non_moving_space_rem_set = + new accounting::RememberedSet("Post-zygote non-moving space remembered set", this, + non_moving_space_); + CHECK(post_zygote_non_moving_space_rem_set != nullptr) + << "Failed to create post-zygote non-moving space remembered set"; + AddRememberedSet(post_zygote_non_moving_space_rem_set); + } } void Heap::FlushAllocStack() { @@ -2034,6 +2069,11 @@ bool Heap::VerifyHeapReferences() { accounting::ModUnionTable* mod_union_table = table_pair.second; mod_union_table->Dump(LOG(ERROR) << mod_union_table->GetName() << ": "); } + // Dump remembered sets. + for (const auto& table_pair : remembered_sets_) { + accounting::RememberedSet* remembered_set = table_pair.second; + remembered_set->Dump(LOG(ERROR) << remembered_set->GetName() << ": "); + } DumpSpaces(); return false; } @@ -2185,15 +2225,29 @@ accounting::ModUnionTable* Heap::FindModUnionTableFromSpace(space::Space* space) return it->second; } -void Heap::ProcessCards(TimingLogger& timings) { +accounting::RememberedSet* Heap::FindRememberedSetFromSpace(space::Space* space) { + auto it = remembered_sets_.find(space); + if (it == remembered_sets_.end()) { + return nullptr; + } + return it->second; +} + +void Heap::ProcessCards(TimingLogger& timings, bool use_rem_sets) { // Clear cards and keep track of cards cleared in the mod-union table. for (const auto& space : continuous_spaces_) { accounting::ModUnionTable* table = FindModUnionTableFromSpace(space); + accounting::RememberedSet* rem_set = FindRememberedSetFromSpace(space); if (table != nullptr) { const char* name = space->IsZygoteSpace() ? "ZygoteModUnionClearCards" : "ImageModUnionClearCards"; TimingLogger::ScopedSplit split(name, &timings); table->ClearCards(); + } else if (use_rem_sets && rem_set != nullptr) { + DCHECK(collector::SemiSpace::kUseRememberedSet && collector_type_ == kCollectorTypeGSS) + << static_cast(collector_type_); + TimingLogger::ScopedSplit split("AllocSpaceRemSetClearCards", &timings); + rem_set->ClearCards(); } else if (space->GetType() != space::kSpaceTypeBumpPointerSpace) { TimingLogger::ScopedSplit split("AllocSpaceClearCards", &timings); // No mod union table for the AllocSpace. Age the cards so that the GC knows that these cards @@ -2694,5 +2748,22 @@ void Heap::CheckPreconditionsForAllocObject(mirror::Class* c, size_t byte_count) CHECK_GE(byte_count, sizeof(mirror::Object)); } +void Heap::AddRememberedSet(accounting::RememberedSet* remembered_set) { + CHECK(remembered_set != nullptr); + space::Space* space = remembered_set->GetSpace(); + CHECK(space != nullptr); + CHECK(remembered_sets_.find(space) == remembered_sets_.end()); + remembered_sets_.Put(space, remembered_set); + CHECK(remembered_sets_.find(space) != remembered_sets_.end()); +} + +void Heap::RemoveRememberedSet(space::Space* space) { + CHECK(space != nullptr); + auto it = remembered_sets_.find(space); + CHECK(it != remembered_sets_.end()); + remembered_sets_.erase(it); + CHECK(remembered_sets_.find(space) == remembered_sets_.end()); +} + } // namespace gc } // namespace art diff --git a/runtime/gc/heap.h b/runtime/gc/heap.h index 1e0a59649..de20a4ecb 100644 --- a/runtime/gc/heap.h +++ b/runtime/gc/heap.h @@ -56,6 +56,7 @@ namespace accounting { class HeapBitmap; class ModUnionTable; class ObjectSet; + class RememberedSet; } // namespace accounting namespace collector { @@ -541,6 +542,10 @@ class Heap { accounting::ModUnionTable* FindModUnionTableFromSpace(space::Space* space); void AddModUnionTable(accounting::ModUnionTable* mod_union_table); + accounting::RememberedSet* FindRememberedSetFromSpace(space::Space* space); + void AddRememberedSet(accounting::RememberedSet* remembered_set); + void RemoveRememberedSet(space::Space* space); + bool IsCompilingBoot() const; bool HasImageSpace() const; @@ -660,7 +665,7 @@ class Heap { void SwapStacks(Thread* self); // Clear cards and update the mod union table. - void ProcessCards(TimingLogger& timings); + void ProcessCards(TimingLogger& timings, bool use_rem_sets); // Signal the heap trim daemon that there is something to do, either a heap transition or heap // trim. @@ -701,6 +706,9 @@ class Heap { // A mod-union table remembers all of the references from the it's space to other spaces. SafeMap mod_union_tables_; + // A remembered set remembers all of the references from the it's space to the target space. + SafeMap remembered_sets_; + // Keep the free list allocator mem map lying around when we transition to background so that we // don't have to worry about virtual address space fragmentation. UniquePtr allocator_mem_map_; -- 2.11.0