ART运行时Compacting GC简要介绍和学习计划

       在前面一个系列文章中，我们学习了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进行简要介绍以及制定学习计划。

《Android系统源代码情景分析》一书正在进击的程序员网（http://）中连载，点击进入！

       总体来说，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_成员变量，如下所示：

1. // C++ mirror of java.lang.Object
2. class MANAGED LOCKABLE Object {
3. public:
4. ......
6. // Monitor and hash code information.
7. uint32_t monitor_;
9. ......
10. };

       这个类定义在文件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运行时垃圾收集机制简要介绍和学习计划这个系列的文章，对象的分配都是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的执行过程我们在后面的文章中再详细分析，这里主要关注对象的移动过程。首先栈上的根集对象的移动过程，如下所示：

1. void SemiSpace::MarkRootCallback(Object** root, void* arg, uint32_t /*thread_id*/,
2. RootType /*root_type*/) {
3. auto ref = StackReference
4. reinterpret_cast
5. if (*root != ref.AsMirrorPtr()) {
6. *root = ref.AsMirrorPtr();
7. }
8. }
10. // Marks all objects in the root set.
11. void SemiSpace::MarkRoots() {
12. TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
13. Runtime::Current()->VisitRoots(MarkRootCallback, this);
14. }

       这两个函数定义在文件art/runtime/gc/collector/semi_space.cc中。

       SemiSpace类的成员函数MarkRoots调用Runtime类的成员函数VisitRoots来遍历根集对象。对于每一个根集对象，都会回调SemiSpace类的静态成员函数MarkRootCallback进行处理。

       在SemiSpace类的静态成员函数MarkRootCallback中，参数root是一个指向栈上的位置，它所引用的对象的地址值即为*root。首先是将被引用对象的地址*root封装成一个StackReference对象。

       StackReference类继承于ObjectReference类，后者有一个类型为uint32_t的reference_，如下所示：

templatebool 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
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_castuintptr_t>(mirror_ptr);
return static_castuint32_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
}
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判断是否需要移动对象，如下所示：

1. templatebool kPoisonReferences>
2. inline void SemiSpace::MarkObject(
3. mirror::ObjectReference
4. mirror::Object* obj = obj_ptr->AsMirrorPtr();
5. if (obj == nullptr) {
6. return;
7. }
8. ......
9. if (from_space_->HasAddress(obj)) {
10. mirror::Object* forward_address = GetForwardingAddressInFromSpace(obj);
11. // If the object has already been moved, return the new forward address.
12. if (UNLIKELY(forward_address == nullptr)) {
13. forward_address = MarkNonForwardedObject(obj);
14. DCHECK(forward_address != nullptr);
15. // Make sure to only update the forwarding address AFTER you copy the object so that the
16. // monitor word doesn't Get stomped over.
17. obj->SetLockWord(
18. LockWord::FromForwardingAddress(reinterpret_castsize_t>(forward_address)), false);
19. // Push the object onto the mark stack for later processing.
20. MarkStackPush(forward_address);
21. }
22. obj_ptr->Assign(forward_address);
23. } else if (!collect_from_space_only_ && !immune_region_.ContainsObject(obj)) {
24. BitmapSetSlowPathVisitor visitor(this);
25. if (!mark_bitmap_->Set(obj, visitor)) {
26. // This object was not previously marked.
27. MarkStackPush(obj);
28. }
29. }
30. }

       这个函数定义在文件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运行时垃圾收集机制简要介绍和学习计划这个系列的文章。

       Mod Union Table的基类是ModUnionTable，它的子类ModUnionTableReferenceCache用来描述一个具体的Mod Union Table，接下来我们就通过它的成员函数UpdateAndMarkReferences来进一步描述被堆对象引用的对象的移动过程，它的实现如下所示：

1. void ModUnionTableReferenceCache::UpdateAndMarkReferences(MarkHeapReferenceCallback* callback,
2. void* arg) {
3. CardTable* card_table = heap_->GetCardTable();
5. std::vector<>
6. ModUnionReferenceVisitor add_visitor(this, &cards_references);
8. for (const auto& card : cleared_cards_) {
9. // Clear and re-compute alloc space references associated with this card.
10. cards_references.clear();
11. uintptr_t start = reinterpret_castuintptr_t>(card_table->AddrFromCard(card));
12. uintptr_t end = start + CardTable::kCardSize;
13. auto* space = heap_->FindContinuousSpaceFromObject(reinterpret_cast
14. DCHECK(space != nullptr);
15. ContinuousSpaceBitmap* live_bitmap = space->GetLiveBitmap();
16. live_bitmap->VisitMarkedRange(start, end, add_visitor);
18. // Update the corresponding references for the card.
19. auto found = references_.find(card);
20. if (found == references_.end()) {
21. if (cards_references.empty()) {
22. // No reason to add empty array.
23. continue;
24. }
25. references_.Put(card, cards_references);
26. } else {
27. found->second = cards_references;
28. }
29. }
30. cleared_cards_.clear();
31. size_t count = 0;
32. for (const auto& ref : references_) {
33. for (mirror::HeapReference
34. callback(obj_ptr, arg);
35. }
36. count += ref.second.size();
37. }
38. ......
39. }

       这个函数定义在文件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<>
: 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
}
private:
ModUnionTableReferenceCache* const mod_union_table_;
std::vector<>
};

       这个类定义在文件art/runtime/gc/accounting/mod_union_table.cc中。

       被Clear Card引用的每一个对象都会被ModUnionReferenceVisitor类的重载操作符函数()进行处理。ModUnionReferenceVisitor类的重载操作符函数()对被Clear Card引用的对象的处理就是遍历它的引用类型的成员变量，并且通过AddToReferenceArrayVisitor类的重载操作符函数()进行处理，如下所示：

1. class AddToReferenceArrayVisitor {
2. public:
3. explicit AddToReferenceArrayVisitor(ModUnionTableReferenceCache* mod_union_table,
4. std::vector<>
5. : mod_union_table_(mod_union_table), references_(references) {
6. }
8. // Extra parameters are required since we use this same visitor signature for checking objects.
9. void operator()(Object* obj, MemberOffset offset, bool /*is_static*/) const
10. SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
11. mirror::HeapReference
12. mirror::Object* ref = ref_ptr->AsMirrorPtr();
13. // Only add the reference if it is non null and fits our criteria.
14. if (ref != nullptr && mod_union_table_->ShouldAddReference(ref)) {
15. // Push the adddress of the reference.
16. references_->push_back(ref_ptr);
17. }
18. }
20. private:
21. ModUnionTableReferenceCache* const mod_union_table_;
22. std::vector<>
23. };

      这个类定义在文件art/runtime/gc/accounting/mod_union_table.cc中。

      参数obj是被遍历的对象，参数offset是其引用类型的成员变量的偏移值，AddToReferenceArrayVisitor类的重载操作符函数()会通过Object类的成员函数GetFieldObjectReferenceAddr获得该偏移的实际地址值，并且将其封装成一个HeapReference对象，并且保存在成员变量references_描述的一个map中，也就是我们前面说的ModUnionTableReferenceCache类的成员变量references_描述的那个map。

      上面提到的Object类的成员函数GetFieldObjectReferenceAddr的实现如下所示：

template
inline HeapReference
if (kVerifyFlags & kVerifyThis) {
VerifyObject(this);
}
return reinterpret_cast<>
field_offset.Int32Value());
}

      这个函数定义在文件art/runtime/mirror/object-inl.h中

      从这里就可以看出，Object类的成员函数GetFieldObjectReferenceAddr直接将偏移地址cast成一个HeapReference对象返回给调用者。

      回到ModUnionTableReferenceCache类的成员函数UpdateAndMarkReferences中，那些保存在其成员变量references_描述的一个map中的HeapReference对象将被参数callback描述的函数，即SemiSpace类的静态成员函数MarkHeapReferenceCallback进行处理，如下所示：

1. void SemiSpace::MarkHeapReferenceCallback(mirror::HeapReference
2. void* arg) {
3. reinterpret_cast
4. }

       这个函数定义在文件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运行时垃圾收集机制简要介绍和学习计划这个系列的文章中，我们提到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运行时垃圾收集机制简要介绍和学习计划这个系列的文章中提到的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运行时垃圾收集机制简要介绍和学习计划这个系列文章分析的ART运行时Mark-Sweep GC，接下来我们就按照以下五个情景来详细分析ART运行时Compacting GC：

      1. ART运行时Compacting GC的堆创建过程；

      2. ART运行时Compacting GC的对象分配过程；

      3. ART运行时Semi-Space（SS）和Generational Semi-Space（GSS）GC执行过程；

      4. ART运行时Mark-Compact（ MC）GC执行过程；

      5. ART运行时Foreground GC和Background GC切换过程分析。

      通过这五个情景的学习，我们就可以对ART运行时的Mark-Sweep GC和Compacting GC有一个更好的理解和认识了，敬请关注！更多的信息也可以关注老罗的新浪微博：http://weibo.com/shengyangluo。