From e6e0651c7f0480e18d648200f8958c3463e82a2f Mon Sep 17 00:00:00 2001 From: Mathieu Chartier Date: Tue, 26 Jun 2012 15:00:26 -0700 Subject: Mod-union table implementation: reference caching Implementation which uses a map of card pointers to reference array to keep track of image space references to the alloc space. Speed/memory usage improvements over bitmap implementation. Approximated memory usage is ~4 * number_references compared to the previous 128k due a bitmap spanning the zygote space. For the system server, memory usage is approximately 100k due to ~20000 references to the alloc space. Performance increases since we no longer scan objects in the imagespace when we mark the references of the mod union table. Change-Id: I449b8b3edeba712a535f6a3b14d81743bcd6f5a0 --- src/heap.cc | 6 +-- src/mark_sweep.h | 3 ++ src/mod_union_table.cc | 122 +++++++++++++++++++++++++++++++++++++++++++++---- src/mod_union_table.h | 30 ++++++++++++ 4 files changed, 148 insertions(+), 13 deletions(-) (limited to 'src') diff --git a/src/heap.cc b/src/heap.cc index 144f766746..005609b38f 100644 --- a/src/heap.cc +++ b/src/heap.cc @@ -234,7 +234,7 @@ Heap::Heap(size_t initial_size, size_t growth_limit, size_t capacity, } // Allocate the mod-union table - ModUnionTableBitmap* mod_union_table = new ModUnionTableBitmap(this); + ModUnionTableReferenceCache* mod_union_table = new ModUnionTableReferenceCache(this); mod_union_table->Init(); mod_union_table_ = mod_union_table; @@ -705,11 +705,11 @@ void Heap::CollectGarbageInternal(bool concurrent, bool clear_soft_references) { // Processes the cards we cleared earlier and adds their objects into the mod-union table. mod_union_table_->Update(&mark_sweep); - timings.AddSplit("UpdateModUnionBitmap"); + timings.AddSplit("UpdateModUnionTable"); // Scans all objects in the mod-union table. mod_union_table_->MarkReferences(&mark_sweep); - timings.AddSplit("ProcessModUnionBitmap"); + timings.AddSplit("MarkImageToAllocSpaceReferences"); // Recursively mark all the non-image bits set in the mark bitmap. mark_sweep.RecursiveMark(); diff --git a/src/mark_sweep.h b/src/mark_sweep.h index 28a552369e..5f275a4624 100644 --- a/src/mark_sweep.h +++ b/src/mark_sweep.h @@ -274,12 +274,15 @@ class MarkSweep { size_t array_count_; size_t other_count_; + friend class AddIfReachesAllocSpaceVisitor; // Used by mod-union table. friend class CheckObjectVisitor; friend class InternTableEntryIsUnmarked; friend class MarkIfReachesAllocspaceVisitor; friend class ModUnionClearCardVisitor; + friend class ModUnionReferenceVisitor; friend class ModUnionVisitor; friend class ModUnionTableBitmap; + friend class ModUnionTableReferenceCache; DISALLOW_COPY_AND_ASSIGN(MarkSweep); }; diff --git a/src/mod_union_table.cc b/src/mod_union_table.cc index 58b6a1826e..3b0de40e06 100644 --- a/src/mod_union_table.cc +++ b/src/mod_union_table.cc @@ -32,7 +32,7 @@ class MarkIfReachesAllocspaceVisitor { } // Extra parameters are required since we use this same visitor signature for checking objects. - void operator ()(const Object* obj, const Object* ref, MemberOffset offset, bool is_static) const { + void operator ()(const Object* obj, const Object* ref, const MemberOffset& /* offset */, bool /* is_static */) const { // TODO: Optimize? // TODO: C++0x auto const Spaces& spaces = mark_sweep_->heap_->GetSpaces(); @@ -41,9 +41,6 @@ class MarkIfReachesAllocspaceVisitor { bitmap_->Set(obj); } } - - // Avoid warnings. - (void)obj;(void)offset;(void)is_static; } private: @@ -86,7 +83,7 @@ class ModUnionClearCardVisitor { ModUnionTableBitmap::ModUnionTableBitmap(Heap* heap) : heap_(heap) { // Prevent fragmentation of the heap which is caused by resizing of the vector. // TODO: Make a new vector which uses madvise (basically same as a mark stack). - cleared_cards_.reserve(4 * KB); + cleared_cards_.reserve(32); } ModUnionTableBitmap::~ModUnionTableBitmap() { @@ -94,7 +91,7 @@ ModUnionTableBitmap::~ModUnionTableBitmap() { } void ModUnionTableBitmap::Init() { - const std::vector& spaces = heap_->GetSpaces(); + const Spaces& spaces = heap_->GetSpaces(); // Create one heap bitmap per image space. for (size_t i = 0; i < spaces.size(); ++i) { @@ -113,8 +110,8 @@ void ModUnionTableBitmap::Init() { void ModUnionTableBitmap::ClearCards() { CardTable* card_table = heap_->GetCardTable(); - for (BitmapMap::iterator cur = bitmaps_.begin(); cur != bitmaps_.end(); ++cur) { - const Space* space = cur->first; + for (BitmapMap::iterator it = bitmaps_.begin(); it != bitmaps_.end(); ++it) { + const Space* space = it->first; ModUnionClearCardVisitor visitor(&cleared_cards_); // Clear dirty cards in the this image space and update the corresponding mod-union bits. card_table->VisitClear(space->Begin(), space->End(), visitor); @@ -123,7 +120,6 @@ void ModUnionTableBitmap::ClearCards() { void ModUnionTableBitmap::Update(MarkSweep* mark_sweep) { CardTable* card_table = heap_->GetCardTable(); - while (!cleared_cards_.empty()) { byte* card = cleared_cards_.back(); cleared_cards_.pop_back(); @@ -164,5 +160,111 @@ void ModUnionTableBitmap::MarkReferences(MarkSweep* mark_sweep) { } } -} // namespace art +ModUnionTableReferenceCache::ModUnionTableReferenceCache(Heap* heap) : heap_(heap) { + cleared_cards_.reserve(32); +} + +ModUnionTableReferenceCache::~ModUnionTableReferenceCache() { + +} + +void ModUnionTableReferenceCache::Init() { + +} + +void ModUnionTableReferenceCache::ClearCards() { + const Spaces& spaces = heap_->GetSpaces(); + CardTable* card_table = heap_->GetCardTable(); + + // Create one heap bitmap per image space. + for (size_t i = 0; i < spaces.size(); ++i) { + if (spaces[i]->IsImageSpace()) { + ModUnionClearCardVisitor visitor(&cleared_cards_); + // Clear dirty cards in the this image space and update the corresponding mod-union bits. + card_table->VisitClear(spaces[i]->Begin(), spaces[i]->End(), visitor); + } + } +} + +class AddIfReachesAllocSpaceVisitor { + public: + explicit AddIfReachesAllocSpaceVisitor( + MarkSweep* const mark_sweep, + ModUnionTableReferenceCache::ReferenceArray* references) + : mark_sweep_(mark_sweep), + references_(references) { + } + + // Extra parameters are required since we use this same visitor signature for checking objects. + void operator ()(const Object* /* obj */, const Object* ref, const MemberOffset& /* offset */, bool /* is_static */) const { + if (mark_sweep_->heap_->GetAllocSpace()->Contains(ref)) { + references_->push_back(ref); + } + } + + private: + MarkSweep* const mark_sweep_; + ModUnionTableReferenceCache::ReferenceArray* references_; +}; + +class ModUnionReferenceVisitor { + public: + explicit ModUnionReferenceVisitor( + MarkSweep* const mark_sweep, + ModUnionTableReferenceCache::ReferenceArray* references) + : mark_sweep_(mark_sweep), + references_(references) { + } + + void operator ()(Object* obj) const { + DCHECK(obj != NULL); + // We don't have an early exit since we use the visitor pattern, an early + // exit should significantly speed this up. + AddIfReachesAllocSpaceVisitor visitor(mark_sweep_, references_); + mark_sweep_->VisitObjectReferences(obj, visitor); + } + private: + MarkSweep* const mark_sweep_; + ModUnionTableReferenceCache::ReferenceArray* references_; +}; + +void ModUnionTableReferenceCache::Update(MarkSweep* mark_sweep) { + CardTable* card_table = heap_->GetCardTable(); + while (!cleared_cards_.empty()) { + byte* card = cleared_cards_.back(); + cleared_cards_.pop_back(); + + // Update the corresponding references for the card + // TODO: C++0x auto + ReferenceMap::iterator found = references_.find(card); + if (found == references_.end()) { + references_.Put(card, ReferenceArray()); + found = references_.find(card); + } + + // Clear and re-compute alloc space references associated with this card. + ReferenceArray& cards_references = found->second; + cards_references.clear(); + ModUnionReferenceVisitor visitor(mark_sweep, &cards_references); + uintptr_t start = reinterpret_cast(card_table->AddrFromCard(card)); + uintptr_t end = reinterpret_cast(card_table->AddrFromCard(card + 1)); + SpaceBitmap* live_bitmap = + heap_->FindSpaceFromObject(reinterpret_cast(start))->GetLiveBitmap(); + live_bitmap->VisitMarkedRange(start, end, visitor); + } +} + +void ModUnionTableReferenceCache::MarkReferences(MarkSweep* mark_sweep) { + // TODO: C++0x auto + size_t count = 0; + for (ReferenceMap::const_iterator it = references_.begin(); it != references_.end(); ++it) { + for (ReferenceArray::const_iterator it_ref = it->second.begin(); it_ref != it->second.end(); ++it_ref ) { + mark_sweep->MarkObject(*it_ref); + ++count; + } + } + VLOG(heap) << "Marked " << count << " references in mod union table"; +} + +} // namespace art diff --git a/src/mod_union_table.h b/src/mod_union_table.h index 2d75a0128e..a9111ee982 100644 --- a/src/mod_union_table.h +++ b/src/mod_union_table.h @@ -69,6 +69,36 @@ class ModUnionTableBitmap : public ModUnionTable { Heap* heap_; }; +// Reference caching implementation. Caches references pointing to alloc space(s) +// for each card. +class ModUnionTableReferenceCache : public ModUnionTable { + public: + typedef std::vector ReferenceArray; + typedef SafeMap ReferenceMap; + + ModUnionTableReferenceCache(Heap* heap); + virtual ~ModUnionTableReferenceCache(); + + void Init(); + + // Clear image space cards. + void ClearCards(); + + // Update table based on cleared cards. + void Update(MarkSweep* mark_sweep); + + // Mark all references to the alloc space(s). + void MarkReferences(MarkSweep* mark_sweep); + private: + // Cleared card array, used to update the mod-union table. + std::vector cleared_cards_; + + // Maps from dirty cards to their corresponding alloc space references. + ReferenceMap references_; + + Heap* heap_; +}; + } // namespace art #endif // ART_SRC_MOD_UNION_TABLE_H_ -- cgit v1.2.3-59-g8ed1b