[原文出處--------------ART運行時Compacting GC簡要介紹和學習計劃](http://blog.csdn.net/luoshengyang/article/details/44513977) 在前面一個系列文章中，我們學習了Android 4.4 ART的Mark-Sweep（MS）GC。到了Android 5.0，ART增加了對Compacting GC的支持，包括Semi-Space（SS）、Generational Semi-Space（GSS）和Mark-Compact （MC）三種。本文對Android 5.0 ART的Compacting GC進行簡要介紹以及制定學習計劃。 總體來說，Compacting GC和Mark-Sweep GC各有優劣。所謂Compacting GC，就是在進行GC的時候，同時對堆空間進行壓縮，以消除碎片，因此它的堆空間利用率就更高。但是也正因為要對堆空間進行壓縮，導致Compacting GC的GC效率不如Mark-Sweep GC。不過，只要我們使用得到恰當，是能夠同時發揮Compacting GC和Mark-Sweep GC的長處的。例如，當Android應用程序被激活在前臺運行時，就使用Mark-Sweep GC，而當Android應用程序回退到后臺運行時，就使用Compacting GC。 為了達到上述目的，ART運行時內部有Foreground和Background兩種GC之分。在ART運行時啟動的時候，可以通過-Xgc和-XX:BackgroundGC來指定Foreground GC和Background GC的類型，即具體是哪一種Mark-Sweep GC或者Compacting GC。由于Mark-Sweep GC和Compacting GC所需要的堆空間結構是不一樣的，因此，當發生Foreground GC和Background GC切換時，ART運行時需要提供支持，以維護堆空間的正確性。 除了適合后臺運行時之外，Compacting GC還適合用在內存分配時。在以往的Mark-Sweep GC時，由于碎片而產生的內存不足問題，是解決不了的，只能讓應用程序OOM。但是有了Compacting GC之后，就可以在應用程序OOM之前，再作一次努力，那就是對原來的堆空間進行壓縮一下，再嘗試進行分配，這樣就可以提高成功分配內存的概率。 從上面的分析可以看出，Compacting GC的最大特點就是會對堆空間進行壓縮。這意味著對象在堆空間的位置是會發生變化的。但是對應用程序來說，這種對象位置的變化是要透明的。因此，Compacting GC的最核心挑戰就是在保持應用程序邏輯不變和正確的前提下，在需要的時候對對象的位置進行移動。所以在這篇文章里面，我們第一個要介紹的技術就是對象移動技術，接著再在此基礎之上，展開對其它技術的介紹。 一個對象被移動了，要保持它的使用者的正確性，無非就是兩種方案。 第一種方案是使用者不是直接引用對象，而是間接引用。這就類似于操作系統里面的文件描述符（fd）。我們在調用操作系統接口open打開一個文件的時候，獲得的是一個整型的文件描述符。這個文件描述符其實就是一個索引，它索引到內核為每一個進程都創建的一個打開文件表。這個打開文件表里面的每一個項保存的都是一個指向一個打開文件結構體的指針。我們可以把這個打文件結構體看作就一個對象。當這個對象移動時，也就是在另外一個地方重新分配時，只需要將新分配得到的地址重新填入對應的打開文件表的表項就可以了。這對應用程序來說，是完全透明的，因為它是通過打開文件表來間接訪問得到對應的打開文件結構體的。 我們可以輕易看出，上述方案的最大缺點就是每次訪問對象都需要有額外的開銷，也就是影響效率。但是如果我們可以忽略在執行Compacting GC時的這個開銷，是不是就可以使用了呢？答案是否定的。由于Foreground和Background兩種GC的同時存在，ART內部可能同時存在著Mark-Sweep和Compacting兩種類型的GC。如果我們在Compacting GC中使用了該方案，那么也意味著Mark-Sweep GC也必須是要間接地去訪問對象。但是這完全是沒有必要的，因此ART使用的是第二種對象移動技術，也就是修改對象使用者的引用，使得它無論何時何地，總是直接指向對象的真實地址。 在ART運行時中，對象使用者無非就是位于兩個位置，一個是堆，一個棧。因此，當一個對象被移動時，我們只需要找到它在堆和棧上的使用者的位置，那就可以將它們的值修改為對象被移動后的新地址，那就達到目的了。這個對象移動及其使用者引用者修改的過程示意圖如圖1所示：  圖1 ART運行時Compacting GC對象移動技術 在圖1中，被移動的對象是Object-1，它從Source Space移動到Destination Space，并且同時被堆上的對象Object-2和堆上的一個slot引用。這里我們需要解決兩個問題。第一個問題是上面提到的，我們要修改Object-2中對Object-1的引用，實際上就是某一個成員變量的值，以及棧上顯示的slot位置。第二個問題是要保證Object-1只被移動一次，也就是Object-2中對Object-1的引用和棧上的slot位置指向的是同一個地方。 這是如何實現的呢？我們需要先看一下Object類的定義。這個Object類是ART運行時里面的所有對象的基類，它有一個monitor_成員變量，如下所示： ~~~ // C++ mirror of java.lang.Object class MANAGED LOCKABLE Object { public: ...... // Monitor and hash code information. uint32_t monitor_; ...... }; ~~~ 這個類定義在文件art/runtime/mirror/object.h。 這個32位的monitor_成員變量的責任重大，除了用來描述對象的Monitor和Hash Code信息之外，還包括對象的移動信息。這個monitor_成員變量通過封裝成一個LockWord對象來描述，如下所示： ~~~ class LockWord { public: enum { // Number of bits to encode the state, currently just fat or thin/unlocked or hash code. kStateSize = 2, // Number of bits to encode the thin lock owner. kThinLockOwnerSize = 16, // Remaining bits are the recursive lock count. kThinLockCountSize = 32 - kThinLockOwnerSize - kStateSize, // Thin lock bits. Owner in lowest bits. kThinLockOwnerShift = 0, kThinLockOwnerMask = (1 << kThinLockOwnerSize) - 1, // Count in higher bits. kThinLockCountShift = kThinLockOwnerSize + kThinLockOwnerShift, kThinLockCountMask = (1 << kThinLockCountSize) - 1, kThinLockMaxCount = kThinLockCountMask, // State in the highest bits. kStateShift = kThinLockCountSize + kThinLockCountShift, kStateMask = (1 << kStateSize) - 1, kStateThinOrUnlocked = 0, kStateFat = 1, kStateHash = 2, kStateForwardingAddress = 3, // When the state is kHashCode, the non-state bits hold the hashcode. kHashShift = 0, kHashSize = 32 - kStateSize, kHashMask = (1 << kHashSize) - 1, }; ...... enum LockState { kUnlocked, // No lock owners. kThinLocked, // Single uncontended owner. kFatLocked, // See associated monitor. kHashCode, // Lock word contains an identity hash. kForwardingAddress, // Lock word contains the forwarding address of an object. }; ...... private: ...... // The encoded value holding all the state. uint32_t value_; }; ~~~ 這個類定義在文件art/runtime/lock_word.h中。 通過這個LockWord類的定義我們就可以知道，Object對象的成員變量monitor_的高2位描述的是狀態，包括kUnlocked、kThinLocked、kFatLocked、kHashCode和kForwardingAddress五種狀態。處于不同狀態時，低30位有不同的描述，這里我們只關心kForwardingAddress這種狀態。 當一個對象處于kForwardingAddress狀態時，即它的成員變量monitor_的高2位值等于0x11時，表示它已經被移動過了，這時候它的位30位描述的就是對象移動后的新地址。有同學可能會說，30位夠表示一個對象的地址嗎？因為32位的體系架構中，內存的地址是32位的啊。答案是夠的，回憶前面[ART運行時垃圾收集機制簡要介紹和學習計劃](http://blog.csdn.net/luoshengyang/article/details/42072975)這個系列的文章，對象的分配都是8字節對齊的，這意味著低3位都是0，因此這里用30位來描述對象的地址是足夠的。 有了這個背景知識后，我們來回過頭來看圖1。我們首先需要明確，對象移動是發生在GC的過程中的，并且只有可達對象才需要移動，而可達對象都是從根集對象開始遍歷的。我們假設Object-1是根集對象，并且是被棧上的slot引用。因此，當遍歷到棧上的slot時，需要移動對象Object-1。這時候除了要將棧上的slot位置修改為Object-1在Destination Space上的位置之外，還需要將舊的Object-1（位于Source Space上）的成員變量monitor_的高2位設置為0x11，以及將低30位設置為新的Object-1（位于Destination Space上）的地址。 我們再假設Object-2是一個可達對象，也就是說在棧上的slot被遍歷之后的某一個時候，Object-2也會被遍歷。在遍歷Object-2的時候，我們會檢查它的每一個引用類型的成員變量。當檢查到其引用了Object-1的成員變量的時候，會發現它Object-1（位于Source Space上）的成員變量monitor_的高2位已經被設置為kForwardingAddress狀態，因此就直接將其低30位的值取出來，并且設置為Object-2對應的成員變量的值。這樣就可以保證Object-2和棧上的slot位置引用的都是新的Object-1了。 以此類推，不管還有多少個可達對象引用了Object-1，按照上面的算法，都能保證它們能夠正確地引用移動后的Object-1。 接下來我們就以Semi-Space GC標記對象的過程來說明上述的對象移動過程。Semi-Space GC的執行過程我們在后面的文章中再詳細分析，這里主要關注對象的移動過程。首先棧上的根集對象的移動過程，如下所示： ~~~ void SemiSpace::MarkRootCallback(Object** root, void* arg, uint32_t /*thread_id*/, RootType /*root_type*/) { auto ref = StackReference<mirror::Object>::FromMirrorPtr(*root); reinterpret_cast<SemiSpace*>(arg)->MarkObject(&ref); if (*root != ref.AsMirrorPtr()) { *root = ref.AsMirrorPtr(); } } // Marks all objects in the root set. void SemiSpace::MarkRoots() { TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings()); Runtime::Current()->VisitRoots(MarkRootCallback, this); } ~~~ 這兩個函數定義在文件art/runtime/gc/collector/semi_space.cc中。 SemiSpace類的成員函數MarkRoots調用Runtime類的成員函數VisitRoots來遍歷根集對象。對于每一個根集對象，都會回調SemiSpace類的靜態成員函數MarkRootCallback進行處理。 在SemiSpace類的靜態成員函數MarkRootCallback中，參數root是一個指向棧上的位置，它所引用的對象的地址值即為*root。首先是將被引用對象的地址*root封裝成一個StackReference對象。 StackReference類繼承于ObjectReference類，后者有一個類型為uint32_t的reference_，如下所示： ~~~ template<bool kPoisonReferences, class MirrorType> class MANAGED ObjectReference { public: MirrorType* AsMirrorPtr() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { return UnCompress(); } void Assign(MirrorType* other) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { reference_ = Compress(other); } void Clear() { reference_ = 0; } uint32_t AsVRegValue() const { return reference_; } protected: ObjectReference<kPoisonReferences, MirrorType>(MirrorType* mirror_ptr) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) : reference_(Compress(mirror_ptr)) { } // Compress reference to its bit representation. static uint32_t Compress(MirrorType* mirror_ptr) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { uintptr_t as_bits = reinterpret_cast<uintptr_t>(mirror_ptr); return static_cast<uint32_t>(kPoisonReferences ? -as_bits : as_bits); } // Uncompress an encoded reference from its bit representation. MirrorType* UnCompress() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { uintptr_t as_bits = kPoisonReferences ? -reference_ : reference_; return reinterpret_cast<MirrorType*>(as_bits); } friend class Object; // The encoded reference to a mirror::Object. uint32_t reference_; }; ~~~ 這個類定義在文件art/runtime/mirror/object_reference.h中。 kPoisonReferences是一個模板參數，表示是否要對ObjectReference的成員變量reference_進行壓縮。這里所謂的壓縮，也只不過是將成員變量reference_的值進行取負而已。 結合ObjectReference類的定義，回到SemiSpace類的靜態成員函數MarkRootCallback中，就意味著本地變量ref指向的StackReference對象的成員變量reference_的值就等于*root的值，也就是被引用對象的地址值。接下來再調用SemiSpace類的成員函數MarkObejct判斷是否需要移動對象，如下所示： ~~~ template<bool kPoisonReferences> inline void SemiSpace::MarkObject( mirror::ObjectReference<kPoisonReferences, mirror::Object>* obj_ptr) { mirror::Object* obj = obj_ptr->AsMirrorPtr(); if (obj == nullptr) { return; } ...... if (from_space_->HasAddress(obj)) { mirror::Object* forward_address = GetForwardingAddressInFromSpace(obj); // If the object has already been moved, return the new forward address. if (UNLIKELY(forward_address == nullptr)) { forward_address = MarkNonForwardedObject(obj); DCHECK(forward_address != nullptr); // Make sure to only update the forwarding address AFTER you copy the object so that the // monitor word doesn't Get stomped over. obj->SetLockWord( LockWord::FromForwardingAddress(reinterpret_cast<size_t>(forward_address)), false); // Push the object onto the mark stack for later processing. MarkStackPush(forward_address); } obj_ptr->Assign(forward_address); } else if (!collect_from_space_only_ && !immune_region_.ContainsObject(obj)) { BitmapSetSlowPathVisitor visitor(this); if (!mark_bitmap_->Set(obj, visitor)) { // This object was not previously marked. MarkStackPush(obj); } } } ~~~ 這個函數定義在文件art/runtime/gc/collector/semi_space-inl.h中。 這里我們先明確一下各個參數、本地變量以及成員變量的含義。參數obj_ptr指向的是前面SemiSpace類的靜態成員函數MarkRootCallback構造的一個局部StackReferece對象，本地變量obj指向的是一個被引用的根集對象，成員變量from_space_描述的是當前Semi-Space GC的From Space，也就是相當于圖1所示的Source Space。 只有當對象obj是屬于From Space時，才需要對它進行移動。在其它情況下，不需要對對象obj進行處理，除非成員變量collect_from_space_only_的值被設置為false，也就是非From Space的對象也要進行處理，并且對象obj不屬于成員變量immune_region_描述的非回收區域中。對這類對象的處理也比較簡單，只是將對在Mark Bitmap的對應位設置為1，并且如果是第一次被設置，那么就將它壓入到Mark Stack去等待遞歸處理它直接或者間接引用的其它對象。 現在我們就主要關注對象obj屬于From Space的情況，SemiSpace類的成員函數MarkObejct首先是調用另外一個成員函數GetForwardingAddressInFromSpace檢查對象obj是否已經被移動過了。如果已經被移動過，那么得到的forward_address就不等于nullptr，這時候只要修改參數obj_ptr指向的是前面StackReferece對象的成員變量reference_的值為forward_address即可。 另一方面，如果得到的forward_address就等于nullptr，那么就說沒有對象obj還沒有被移動過，這時候就需要調用另外一個成員函數MarkNonForwardedObject對對象obj進行移動，移動后得到的新地址即為forward_address。這時候首先要做的就是設置舊的obj對象的forwarding address，以便以后遍歷其它引用了舊的obj對象的對象時，可以獲得新的obj的地址。接下來再移動后的對象壓入到Mark Stack中去等待遞歸遍歷。最后一步同樣是要修改參數obj_ptr指向的是前面StackReferece對象的成員變量reference_的值為forward_address。 至此，對象移動完畢，再回到SemiSpace類的靜態成員函數MarkRootCallback中。注意，這時候我們修改的僅僅是本地變量ref指向的一個StackReference對象的成員變量reference_的值，而棧上引用了對象*root的slot還沒有被修改，因此，最后就需要繼續修改該slot的值，這個slot的位置就是通過*root來描述的。 分析完成棧位置引用的修改過程之后，我們再來看堆位置引用的修改過程。我們依然是以Semi-Space標記對象的過程為例。Semi-Space GC標記完成根集對象后，就開始標記可達對象，如下所示： ~~~ void SemiSpace::MarkReachableObjects() { ...... for (auto& space : heap_->GetContinuousSpaces()) { // If the space is immune then we need to mark the references to other spaces. accounting::ModUnionTable* table = heap_->FindModUnionTableFromSpace(space); if (table != nullptr) { ...... table->UpdateAndMarkReferences(MarkHeapReferenceCallback, this); ...... } ...... } ...... } ~~~ 這個函數定義在文件art/runtime/gc/collector/semi_space.cc中。 SemiSpace類的成員函數MarkReachableObjects依次遍歷組成當前堆的各個Space。如果一個Space有對應的Mod Union Table，那么就調用它的成員函數UpdateAndMarkReferences來標記那些自上次GC以來被修改的對象。對于每一個這樣的對象，都回調SemiSpace類的靜態成員函數MarkHeapReferenceCallback進行處理。關于Mod Union Table在GC過程中的作用，可以參考前面[ART運行時垃圾收集機制簡要介紹和學習計劃](http://blog.csdn.net/luoshengyang/article/details/42072975)這個系列的文章。 Mod Union Table的基類是ModUnionTable，它的子類ModUnionTableReferenceCache用來描述一個具體的Mod Union Table，接下來我們就通過它的成員函數UpdateAndMarkReferences來進一步描述被堆對象引用的對象的移動過程，它的實現如下所示： ~~~ void ModUnionTableReferenceCache::UpdateAndMarkReferences(MarkHeapReferenceCallback* callback, void* arg) { CardTable* card_table = heap_->GetCardTable(); std::vector<mirror::HeapReference<Object>*> cards_references; ModUnionReferenceVisitor add_visitor(this, &cards_references); for (const auto& card : cleared_cards_) { // Clear and re-compute alloc space references associated with this card. cards_references.clear(); uintptr_t start = reinterpret_cast<uintptr_t>(card_table->AddrFromCard(card)); uintptr_t end = start + CardTable::kCardSize; auto* space = heap_->FindContinuousSpaceFromObject(reinterpret_cast<Object*>(start), false); DCHECK(space != nullptr); ContinuousSpaceBitmap* live_bitmap = space->GetLiveBitmap(); live_bitmap->VisitMarkedRange(start, end, add_visitor); // Update the corresponding references for the card. auto found = references_.find(card); if (found == references_.end()) { if (cards_references.empty()) { // No reason to add empty array. continue; } references_.Put(card, cards_references); } else { found->second = cards_references; } } cleared_cards_.clear(); size_t count = 0; for (const auto& ref : references_) { for (mirror::HeapReference<Object>* obj_ptr : ref.second) { callback(obj_ptr, arg); } count += ref.second.size(); } ...... } ~~~ 這個函數定義在文件art/runtime/gc/accounting/mod_union_table.cc中。 ModUnionTableReferenceCache類的成員函數UpdateAndMarkReferences首先是通過類ModUnionReferenceVisitor來收集被Clear Card引用的對象到成員變量references_描述的一個map中，接著再調用參數callback指向的回調函數，即SemiSpace類的靜態成員函數MarkHeapReferenceCallback，對每一個被Clear Card引用到的對象進行處理。 注意，ModUnionTableReferenceCache類的成員變量references_保存的不是直接被引用的對象，而是一個HeapReference對象。這個HeapReference對象與我們前面分析的StackReference對象類似，都是用來封裝被引用對象的，并且它們也同樣是繼承于ObjectReference類。 接下來，我們繼續分析ModUnionReferenceVisitor類將Clear Card引用的對象保存到ModUnionTableReferenceCache類的成員變量references_描述的一個map的過程，如下所示： ~~~ class ModUnionReferenceVisitor { public: explicit ModUnionReferenceVisitor(ModUnionTableReferenceCache* const mod_union_table, std::vector<mirror::HeapReference<Object>*>* references) : mod_union_table_(mod_union_table), references_(references) { } void operator()(Object* obj) const SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_, Locks::mutator_lock_) { // We don't have an early exit since we use the visitor pattern, an early // exit should significantly speed this up. AddToReferenceArrayVisitor visitor(mod_union_table_, references_); obj->VisitReferences<kMovingClasses>(visitor, VoidFunctor()); } private: ModUnionTableReferenceCache* const mod_union_table_; std::vector<mirror::HeapReference<Object>*>* const references_; }; ~~~ 這個類定義在文件art/runtime/gc/accounting/mod_union_table.cc中。 被Clear Card引用的每一個對象都會被ModUnionReferenceVisitor類的重載操作符函數()進行處理。ModUnionReferenceVisitor類的重載操作符函數()對被Clear Card引用的對象的處理就是遍歷它的引用類型的成員變量，并且通過AddToReferenceArrayVisitor類的重載操作符函數()進行處理，如下所示： ~~~ class AddToReferenceArrayVisitor { public: explicit AddToReferenceArrayVisitor(ModUnionTableReferenceCache* mod_union_table, std::vector<mirror::HeapReference<Object>*>* references) : mod_union_table_(mod_union_table), references_(references) { } // Extra parameters are required since we use this same visitor signature for checking objects. void operator()(Object* obj, MemberOffset offset, bool /*is_static*/) const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { mirror::HeapReference<Object>* ref_ptr = obj->GetFieldObjectReferenceAddr(offset); mirror::Object* ref = ref_ptr->AsMirrorPtr(); // Only add the reference if it is non null and fits our criteria. if (ref != nullptr && mod_union_table_->ShouldAddReference(ref)) { // Push the adddress of the reference. references_->push_back(ref_ptr); } } private: ModUnionTableReferenceCache* const mod_union_table_; std::vector<mirror::HeapReference<Object>*>* const references_; }; ~~~ 這個類定義在文件art/runtime/gc/accounting/mod_union_table.cc中。 參數obj是被遍歷的對象，參數offset是其引用類型的成員變量的偏移值，AddToReferenceArrayVisitor類的重載操作符函數()會通過Object類的成員函數GetFieldObjectReferenceAddr獲得該偏移的實際地址值，并且將其封裝成一個HeapReference對象，并且保存在成員變量references_描述的一個map中，也就是我們前面說的ModUnionTableReferenceCache類的成員變量references_描述的那個map。 上面提到的Object類的成員函數GetFieldObjectReferenceAddr的實現如下所示： ~~~ template <VerifyObjectFlags kVerifyFlags> inline HeapReference<Object>* Object::GetFieldObjectReferenceAddr(MemberOffset field_offset) { if (kVerifyFlags & kVerifyThis) { VerifyObject(this); } return reinterpret_cast<HeapReference<Object>*>(reinterpret_cast<byte*>(this) + field_offset.Int32Value()); } ~~~ 這個函數定義在文件art/runtime/mirror/object-inl.h中 從這里就可以看出，Object類的成員函數GetFieldObjectReferenceAddr直接將偏移地址cast成一個HeapReference對象返回給調用者。 回到ModUnionTableReferenceCache類的成員函數UpdateAndMarkReferences中，那些保存在其成員變量references_描述的一個map中的HeapReference對象將被參數callback描述的函數，即SemiSpace類的靜態成員函數MarkHeapReferenceCallback進行處理，如下所示： ~~~ void SemiSpace::MarkHeapReferenceCallback(mirror::HeapReference<mirror::Object>* obj_ptr, void* arg) { reinterpret_cast<SemiSpace*>(arg)->MarkObject(obj_ptr); } ~~~ 這個函數定義在文件art/runtime/gc/collector/semi_space.cc中。 對比前面分析棧位置引用的對象的移動過程提到的SemiSpace類的靜態成員函數MarkRootCallback的實現，它們都是通過調用SemiSpace類的成員函數MarkObject來移動對象的，只不過一個將要移動的對象使用StackReference類來封裝，而另一個使用HeapReference類來封裝。 另外還有一個很大的區別。SemiSpace類的靜態成員函數MarkRootCallback傳遞給成員函數MarkObject的StackReference對象是一個局部對象，也就是在當前調用棧上構造上的，對它的成員變量reference_的修改不會影響到位于棧上的引用了相應的根集對象的slot，因此，從SemiSpace類的成員函數MarkObject返回后，需要手動修改棧上對應的slot的值，即*root的值。 傳遞給SemiSpace類的靜態成員函數MarkHeapReferenceCallback的HeapReference對象，也就是接下來傳遞給成員函數MarkObject的HeapReference對象，不是在當前調用棧上構造的，而是通過直接cast堆對象對應的成員變量的地址得到的，因此在調用SemiSpace類的成員函數MarkObject的時候，直接就修改了堆對象對應的成員變量的值，于是就不需要在調用SemiSpace類的成員函數MarkObject返回后再手動修改。 以上就是ART運行時使用的對象移動技術，它們是發生在兩個都稱為Bump Pointer的Space里面的，也就是圖1所示的From Space和Destination Space均為Bump Pointer Space。在前面[ART運行時垃圾收集機制簡要介紹和學習計劃](http://blog.csdn.net/luoshengyang/article/details/42072975)這個系列的文章中，我們提到Android 4.4 ART運行時用來分配對象的Space稱為Dl Malloc Space，這是一個使用C庫內存管理接口來分配和釋放內存的Space。Android 5.0 ART運行時引入的Bump Pointer Space不是通過C庫內存管理接口來分配和釋放內存的，這是由于在它上面分配的對象具有可移動的特性，因此，就使用了另外一種更加合適的內存管理方法。 接下來，我們就從對象分配、對象移動和Compacting GC三個角度來簡要介紹一下Bump Pointer Space。不同的Compacting GC對Bump Pointer Space的使用是略有不同的，因此，我們又分為Semi-Space GC、Generational Semi-Space GC和Mark-Compact GC三種情況來介紹Bump Pointer Space。 首先看Semi-Space GC。它由兩個Bump Pointer Space組成，如圖2所示：  圖2 Bump Pointer Space in Semi-Space GC 在圖2中，Bump Pointer Space 1和Bump Pointer Space 2分別稱為From Space和To Space。其中，對象的分配發生在From Space中。在Bump Pointer Space中，有一個指針end_，始終指向下一次要分配的內存塊的起始地址。因此，在Bump Pointer Space上分配內存的邏輯是很簡單的，只要前指針end_向前移動指定的大小即可。這也是Bump Pointer的由來。 當From Space不能滿足內存分配要求時，就會觸發一次Semi-Space GC，結果就是From Space和To Space互換了位置，并且原來在From Space上的Live Object按地址值從小到大的順序移動到了原來的To Space上去。 再來看Generational Semi-Space GC。Generational Semi-Space GC與Semi-Space GC是基本相同的，只不過前者在移動對象時，會考慮到對象的年齡。如果一個對象在多次GC中都能存活下來，那么就會將它移動到一個Promote Space中去。這是因為時間局部性原理，一個對象如果在前面幾次GC中都能存活下來，那么它在下一次GC中也很有可能是存活的。因此，就把它移動到一個Promote Space中去。由于Promote Space是一個Non-Moving Space，因此以后在這個Space上的對象不會再被移動。通過這種方式，就可以有效地減少在Generational Semi-Space GC中要移動的對象的個數，從而提高GC效率。 因此，Generational Semi-Space GC會涉及到三個Space，其中兩個是Bump Pointer Space，另外一個是Promote Space，如圖3所示：  圖3 Bump Pointer Space in Generational Semi-Space GC 在圖3中，Obj-1是一個在多次GC中存活下來的對象，因此，在下一次Generational Semi-Space中，它就被移動到了Promote Space中，而Obj-3就像Semi-Space GC中的Live Object一樣，被移動到了To Space中。 最后看Mark-Compact GC。從上面的圖2和圖3可以看出，Semi-Space和Generational Semi-Space需要用到兩個Bump Pointer Space，這也是Semi-Space的由來，然而Mark-Compact GC只用到了一個Bump Pointer Space，如圖4所示：  圖4 Bump Pointer Space in Mark-Compact GC 在執行Mark-Compact GC時，所有存活的對象都被移動到了另外一端，通過這種方式就達到壓縮的效果。 以上就是Android 5.0 ART運行時引入的Bump Pointer Space。此外，Android 5.0 ART運行時還引進了另外一種稱為Ros Alloc的Space。 Ros Alloc Space與在前面[ART運行時垃圾收集機制簡要介紹和學習計劃](http://blog.csdn.net/luoshengyang/article/details/42072975)這個系列的文章中提到的Dl Malloc Space類似，都是用來分配不可移動對象的。但是Ros Alloc Space不像Dl Malloc Space一樣使用C庫內存管理接口來分配和釋放內存，而是采用一種稱為Ros（Runs-of-slots）的接口來進行內存分配和釋放。 Ros算法其實與Linux內核使用的SLAB算法類似，它們的核心思想都是將內存分為若干個Bucket，每一個Bucket都管理著相同大小的內存塊。這樣在分配內存時，就會先根據要分配的內存大小找到最合適的Bucket，然后再從這個Bucket找到一塊空閑的內存進行分配。這是一種Best Fit分配策略，好處是可以將大小相同的對象集中在一起分配，這樣可以有效地減少內存碎片。 這個系列的文章主要致力于分析Compacting GC，因此，就沒有計劃詳細分析Ros算法的實現，有興趣的同學可以先學習一下SLAB算法，然后就會對Ros算法有一個很好的了解了。這里我們只是簡要地介紹一下相關的數據結構，以便后面我們可以更好地學習Compacting GC，如圖5所示：  圖5 Runs-of-slots 在Runs-of-slots中，每一個Bucket用一個Run來描述，每一個Run里面的內存塊用一個Slot來描述。每一個Run都包括以下信息： * **magic_num**：一個值等于42的魔數，在debug版本才會設置該值，用來標記這是一個Run。 * **size_bracket_idx**：一個Run數組索引，同時也用來描述對應的Run的slot大小。當等于（size_bracket_idx + 1）x 16。例如，假設size_bracket_idx的值等于1，那么對應的Run的slot大小即為（1 + 1）x 16 = 32個字節。 * **is_thread_local**：描述一個Run是否作為線程局部存儲使用。每一個ART運行時線程都有一組Run，用來分配內存，這樣可以避免分配內存時要對堆進行加鎖。當一個線程請求分配的內存小于等于176個字節時，就會嘗試從線程局部的那組Run去分配，也就是說，線程局部那組Run的最大size_bracket_idx值等于10。 * **top_bitmap_index**：用來記錄一個Run下一個可分配的slot，這樣可以提高內存分配效率。 * **alloc bit map**：每一個已經被分配出去的slot在alloc bit map中對應的位都會被設置為1。 * **bulk free bit map**：每一個將要釋放的slot都不會馬上被回收，而是先記錄起來，等到一個Run的所有slot全部都釋放時，才會執行真正的內存回收操作，因此，就需要在釋放slot的時候用一個bulk free bit map中的位來記錄那些slot是需要釋放的。這樣可以避免每釋放一個slot，就執行一次內存回收操作。同時，該bulk free bit map的信息也會被同步到alloc bit map中。 * **thread local bit map**：當一個Run是一個線程局部Run時，那么當它的slot被釋放時，釋放信息會從bulk free bit map同步到thread local bit map，但是不會馬上同步到alloc bitmap中，而是等到從該Run分配內存出現失敗時，才會將該thread local bit map的信息同步到alloc bit map中去。 * **to_be_bulk_freed**：用來標記一個Run有多個slot等待釋放。 * **padding due to alignment**：用來對齊后面的slot。 * **slot 1/slot2/.../last slot**：數據區，真正分配出去的內存塊。 在一個Ros Alloc Space中，最多可以擁有34個Run，其中： * 第0到第3個Run占據1個內存頁； * 第4到第7個Run占據2個內存頁； * 第8到第15個Run占據4個內存頁； * 第16到第31個Run占據8個內存頁； * 第32個Run占據16個內存頁； * 第33個Run占據32個內存頁。 第0個到第31個Run的大小等于（size_bracket_idx + 1）x 16，第32個Run大小等于1024個字節，第33個Run的大小等于2048個字節。對于大于2048字節的內存塊，則直接按內存頁進行分配，當這些頁被釋放時，就會使用一個FreePageRun來描述，以便可以復用。在FreePageRun，只有一個描述域magic_num，它的值等于43，并且在debug版本才會設置，用來標志這是一個FreePageRun。 從上面對Runs-of-slots數據結構的分析就可以知道，一個Ros Alloc Space會將自己的一部分Run作為ART運行時線程的線程局部Run，這樣在分配內存時，就可以考慮先在線程局部Run分配，失敗后再從非線程局部Run分配，最大限度減小鎖競爭。同樣的，Bump Pointer Space也會將自己的一部分內存作為ART運行時線程的線程局部存儲（tlab），這樣也可以使得分在Bump Pointer Space上分配內存時，優先考慮在當前ART運行時線程的tlab中進行分配。 以上分析的內容就構成了ART運行時Compacting GC的基礎知識，結合前面[ART運行時垃圾收集機制簡要介紹和學習計劃](http://blog.csdn.net/luoshengyang/article/details/42072975)這個系列文章分析的ART運行時Mark-Sweep GC，接下來我們就按照以下五個情景來詳細分析ART運行時Compacting GC： 1. [ART運行時Compacting GC的堆創建過程](http://blog.csdn.net/luoshengyang/article/details/44789295)； 2. [ART運行時Compacting GC的對象分配過程](http://blog.csdn.net/luoshengyang/article/details/44910271)； 3. [ART運行時Semi-Space（SS）和Generational Semi-Space（GSS）GC執行過程](http://blog.csdn.net/luoshengyang/article/details/45017207)； 4. [ART運行時Mark-Compact（ MC）GC執行過程](http://blog.csdn.net/luoshengyang/article/details/45162589)； 5. [ART運行時Foreground GC和Background GC切換過程分析](http://blog.csdn.net/luoshengyang/article/details/45301715)。 通過這五個情景的學習，我們就可以對ART運行時的Mark-Sweep GC和Compacting GC有一個更好的理解和認識了，