ART运行时Mark-Compact（ MC）GC执行过程分析
除了Semi-Space（SS）GC和Generational Semi-Space（GSS）GC，ART运行时还引入了第三种Compacting GC：Mark-Compact（MC）GC。这三种GC虽然都是Compacting GC，不过它们的实现方式却有很大不同。SS GC和GSS GC需两个Space来压缩内存，而MC GC只需一个Space来压缩内存。本文就详细分析MC GC的执行过程。
从前面ART运行时Semi-Space（SS）和Generational Semi-Space（GSS）GC执行过程分析一文可以知道，Mark-Compact GC主要是针对ART运行时正在使用的Bump Pointer Space进行压缩，如图1所示：
图1 Mark-Compact GC的执行过程
从图1可以看出，当Mark-Compact GC执行完成之后，原来位于Bump Pointer Space上的仍然存活的对象会被依次移动至原Bump Pointer Space的左侧，并且按地址从小到大紧凑地排列在一起。这个过程不需要借助于额外的Space来完成。这一点是Mark-Compact GC与Semi-Space GC、Generational Semi-Space GC的显著区别。
不过，Mark-Compact GC与Semi-Space GC、Generational Semi-Space GC一样，除了需要对ART运行时当前使用的Bump Pointer Space进行内在压缩之外，还需要修改其它Space对Bump Pointer Space的引用，因为Bump Pointer Space的对象发生了移动。此外，ART运行时堆的Non Moving Space和Large Object Space也会进行像Mark-Sweep GC一样的垃圾回收。
从前面ART运行时Semi-Space（SS）和Generational Semi-Space（GSS）GC执行过程分析一文还可以知道，在ART运行时内部，所有的GC都是通过Heap类的成员函数CollectGarbageInternal开始执行的，并且当决定要执行Mark-Compact GC时，最终会以MarkCompact类的成员函数RunPhases作为入口点，如下所示：
void MarkCompact::RunPhases() {
Thread* self = Thread::Current();
InitializePhase();
CHECK(!Locks::mutator_lock_->IsExclusiveHeld(self));
{
ScopedPause pause(this);
......
MarkingPhase();
ReclaimPhase();
}
......
FinishPhase();
}这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
与Semi-Space GC、Generational Semi-Space GC一样，Mark-Compact GC的执行过程也分为初始化、标记、回收和结束四个阶段，对应的函数分别为MarkCompact类的成员函数InitializePhase、MarkingPhase、ReclaimPhase和FinishPhase。其中，标记和回收阶段是在挂起其它的ART运行时线程的前提下进行的。注意，挂起其它的ART运行时线程的操作通过ScopedPause类的构造函数实现的。当标记和回收阶段结束，ScopedPause类的析构函数就会自动恢复之前被挂起的ART运行时线程。
接下来，我们就分别分析Mark-Compact GC的四个阶段的执行过程，即MarkCompact类的成员函数InitializePhase、MarkingPhase、ReclaimPhase和FinishPhase的实现。
Mark-Compact GC的初始化阶段由MarkCompact类的成员函数InitializePhase实现，如下所示：
void MarkCompact::InitializePhase() {
TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
mark_stack_ = heap_->GetMarkStack();
......
immune_region_.Reset();
......
// TODO: I don't think we should need heap bitmap lock to Get the mark bitmap.
ReaderMutexLock mu(Thread::Current(), *Locks::heap_bitmap_lock_);
mark_bitmap_ = heap_->GetMarkBitmap();
live_objects_in_space_ = 0;
}这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
MarkCompact类的成员函数InitializePhase主要就是执行一些初始化工作，例如获得ART运行时堆的Mark Stack、Mark Bitmap，保存在成员变量mark_stack_和mark_bitmap_中，并且重置MarkCompact类的成员变量immune_region_描述的一个不进行垃圾回收的Space区间为空，以及将成员变量live_objects_in_space_的值置为0。MarkCompact类的成员变量live_objects_in_space_用来描述Mark-Compact GC执先完成后，Bump Pointer Space还有多少对象是存活的。
Mark-Compact GC的标记阶段来MarkCompact类的成员函数MarkingPhase实现，如下所示：
void MarkCompact::MarkingPhase() {
TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
Thread* self = Thread::Current();
// Bitmap which describes which objects we have to move.
objects_before_forwarding_.reset(accounting::ContinuousSpaceBitmap::Create(
"objects before forwarding", space_->Begin(), space_->Size()));
// Bitmap which describes which lock words we need to restore.
objects_with_lockword_.reset(accounting::ContinuousSpaceBitmap::Create(
"objects with lock words", space_->Begin(), space_->Size()));
CHECK(Locks::mutator_lock_->IsExclusiveHeld(self));
// Assume the cleared space is already empty.
BindBitmaps();
t.NewTiming("ProcessCards");
// Process dirty cards and add dirty cards to mod-union tables.
heap_->ProcessCards(GetTimings(), false);
// 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.
t.NewTiming("ClearCardTable");
heap_->GetCardTable()->ClearCardTable();
// 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.
if (kUseThreadLocalAllocationStack) {
t.NewTiming("RevokeAllThreadLocalAllocationStacks");
heap_->RevokeAllThreadLocalAllocationStacks(self);
}
t.NewTiming("SwapStacks");
heap_->SwapStacks(self);
{
WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
MarkRoots();
// Mark roots of immune spaces.
UpdateAndMarkModUnion();
// Recursively mark remaining objects.
MarkReachableObjects();
}
ProcessReferences(self);
{
ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_);
SweepSystemWeaks();
}
// Revoke buffers before measuring how many objects were moved since the TLABs need to be revoked
// before they are properly counted.
RevokeAllThreadLocalBuffers();
......
}这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
MarkCompact类的成员函数MarkingPhase的执行过程如下所示：
1. 针对当前要进行Mark-Compact的Bump Pointer Space，创建两个ContinuousSpaceBitmap，分别保存在MarkCompact类的成员变量objects_before_forwarding_和objects_withlockword。其中，前者用来记录当前要进行Mark-Compact的Bump Pointer Space的存活对象，而后者用来记录上述的存活对象在移动前它们的LockWord有没有被覆盖。如果被覆盖了，那么在它们移动之后，需要恢复它们之前的LockWord。后面我们就可以看到，Mark-Compact GC在移动对象的时候，会先计算出每一个需要移动的对象的新地址，并且将该新地址作为一个Forwarding Address记录它的LockWord中。因此，当对象移动到新地址后，就需要恢复它们之前的LockWord值。
2. 调用MarkCompact类的成员函数BindBitmaps确定哪些Space是不需要进行垃圾回收的。
3. 调用Heap类的成员函数ProcessCards处理Dirty Card，即将它们记录在对应的Mod Union Table中，以便后面可以找到上次GC以来，不需要进行垃圾回收的Space对需要垃圾回收的Space的引用情况。
4. 调用CardTable类的成员函数ClearCardTable清零Dirty Card。因为Dirty Card在经过上一步的操作之后，已经记录在了对应的Mod Union Table，因此现在不需要它们了。
5. 如果ART运行时堆使用了线程局部Allocation Stack，即在常量kUseThreadLocalAllocationStack等于true的情况下，调用Heap类的成员函数RevokeAllThreadLocalAllocationStacks对它们进行回收。
6. 调用Heap类的成员函数SwapStacks交换ART运行时堆的Allocation Stack和Live Stack。
7. 调用MarkCompact类的成员函数MarkRoots标记根集对象。
8. 调用MarkCompact类的成员函数UpdateAndMarkModUnion标记Dirty Card引用的对象。
9. 调用MarkCompact类的成员函数MarkReachableObjects标记可达对象，即递归标记根集对象和Dirty Card引用的对象可达的对象。
-
调用MarkCompact类的成员函数ProcessReferences处理引用类型的对象，即Soft Reference、Weak Reference、Phantom Reference和Finalizer Reference对象。
- 调用MarkCompact类的成员函数SweepSystemWeaks处理那些没有被标记的常量字符串、Monitor对象和在JNI创建的全局弱引用对象等。
12. 调用MarkCompact类的成员函数RevokeAllThreadLocalBuffers回收各个ART运行时线程的局部分配缓冲区。
在上述的操作中，我们主要是分析第2、7、8和9操作，即MarkCompact类的成员函数BindBitmaps、MarkRoots、UpdateAndMarkModUnion和MarkReachableObjects的实现、其它的操作可以参考ART运行时垃圾收集（GC）过程分析或者ART运行时Semi-Space（SS）和Generational Semi-Space（GSS）GC执行过程分析一文。
MarkCompact类的成员函数BindBitmaps的实现如下所示：
void MarkCompact::BindBitmaps() {
TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
WriterMutexLock mu(Thread::Current(), *Locks::heap_bitmap_lock_);
// Mark all of the spaces we never collect as immune.
for (const auto& space : GetHeap()->GetContinuousSpaces()) {
if (space->GetGcRetentionPolicy() == space::kGcRetentionPolicyNeverCollect ||
space->GetGcRetentionPolicy() == space::kGcRetentionPolicyFullCollect) {
CHECK(immune_region_.AddContinuousSpace(space)) << "Failed to add space " << *space;
}
}
}这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
在前面ART运行时Semi-Space（SS）和Generational Semi-Space（GSS）GC执行过程分析这篇文章提到，在ART运行时中，回收策略为kGcRetentionPolicyNeverCollect和kGcRetentionPolicyFullCollect的Space是Image Space和Zygote Space，因此，从这里可以看出，在Mark-Compact GC中，Image Space和Zygote Space是不进行垃圾回收的，同时也意味着Non Moving Space、Bump Pointer Space和Large Object Space需要进行垃圾回收。
MarkCompact类的成员函数MarkRoots的实现如下所示：
void MarkCompact::MarkRoots() {
TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
Runtime::Current()->VisitRoots(MarkRootCallback, this);
}这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
MarkCompact类的成员函数MarkRoots调用Runtime类的成员函数VisitRoots遍历当前的根集对象，并且对于每一个根集对象，都调用MarkCompact类的静态成员函数MarkRootCallback进行标记处理。
MarkCompact类的静态成员函数MarkRootCallback的实现如下所示：
void MarkCompact::MarkRootCallback(Object** root, void* arg, uint32_t /*thread_id*/,
RootType /*root_type*/) {
reinterpret_cast<MarkCompact*>(arg)->MarkObject(*root);
}这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
MarkCompact类的静态成员函数MarkRootCallback又是通过调用另外一个成员函数MarkObject来标记根集对象，如下所示：
inline void MarkCompact::MarkObject(mirror::Object* obj) {
......
if (immune_region_.ContainsObject(obj)) {
return;
}
if (objects_before_forwarding_->HasAddress(obj)) {
if (!objects_before_forwarding_->Set(obj)) {
MarkStackPush(obj); // This object was not previously marked.
}
} else {
......
BitmapSetSlowPathVisitor visitor;
if (!mark_bitmap_->Set(obj, visitor)) {
// This object was not previously marked.
MarkStackPush(obj);
}
}
}这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
MarkCompact类的成员函数MarkObject首先判断对象obj是否位于非垃圾回收空间中。如果是的话，那么不用对它进行处理了。
MarkCompact类的成员函数MarkObject接着通过成员变量objects_before_forwarding_指向的一个ContinuousSpaceBitmap来判断对象obj是否位于要进行垃圾回收和对象压缩的Bump Pointer Space中。如果是的话，再将其在上述的ContinuousSpaceBitmap的对应位设置为1。此外，如果对象obj是第一次被标记，那么它还被压入到Mark Stack中去，以便后面可以继续对它引用的其它对象进行递归标记处理。
如果对象obj不是位于要行垃圾回收和对象压缩的Bump Pointer Space，那么这时候它肯定就是在Non Moving Space和Large Object Space中，这时候就直接对象在Mark Bitmap上对应的位设置为1。同样，如果对象是第一次被标记，那么也会被压入到Mark Stack中。
根集对象标记完成之后，接下来再标记Dirty Card引用的对象，这是通过调用MarkCompact类的成员函数UpdateAndMarkModUnion实现的，如下所示：
void MarkCompact::UpdateAndMarkModUnion() {
TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
for (auto& space : heap_->GetContinuousSpaces()) {
// If the space is immune then we need to mark the references to other spaces.
if (immune_region_.ContainsSpace(space)) {
accounting::ModUnionTable* table = heap_->FindModUnionTableFromSpace(space);
if (table != nullptr) {
// TODO: Improve naming.
TimingLogger::ScopedTiming t(
space->IsZygoteSpace() ? "UpdateAndMarkZygoteModUnionTable" :
"UpdateAndMarkImageModUnionTable", GetTimings());
table->UpdateAndMarkReferences(MarkHeapReferenceCallback, this);
}
}
}
}这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
由于在Mark-Compact GC中，只有Image Space和Zygote Space是不需要进行垃圾回收的，因此这里就仅仅对它们进行处理。在前面ART运行时Semi-Space（SS）和Generational Semi-Space（GSS）GC执行过程分析这篇文章提到，Image Space和Zygote Space都是有一个关联的Mod Union Table，并且通过调用这个Mod Union Table的成员函数UpdateAndMarkReferences来处理Dirty Card引用的对象。
对于Dirty Card引用的每一个对象，即Dirty Card记录的上次GC以来有修改过引用类型的成员变量的对象，都会被MarkCompact类的静态成员函数MarkHeapReferenceCallback进行标记，如下所示：
void MarkCompact::MarkHeapReferenceCallback(mirror::HeapReference<mirror::Object>* obj_ptr,
void* arg) {
reinterpret_cast<MarkCompact*>(arg)->MarkObject(obj_ptr->AsMirrorPtr());
}这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
从这里就可以看出，Dirty Card引用的对象与根集对象一样，都是通过MarkCompact类的成员函数MarkObject进行标记的。
Dirty Card引用的对象与根集对象都标记完成之后，就开始标记它们可达的对象了，这是通过调用MarkCompact类的成员函数MarkReachableObjects来实现的，如下所示：
void MarkCompact::MarkReachableObjects() {
TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
accounting::ObjectStack* live_stack = heap_->GetLiveStack();
{
TimingLogger::ScopedTiming t2("MarkAllocStackAsLive", GetTimings());
heap_->MarkAllocStackAsLive(live_stack);
}
live_stack->Reset();
// Recursively process the mark stack.
ProcessMarkStack();
}这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
与Semi-Space GC和Generational Semi-Space GC一样，在递归标记根集对象和Dirty Card引用的对象的可达对象之前，首先会将保存在Allocation Stack里面的对象的Live Bitmap位设置为1。
接下来，MarkCompact类的成员函数MarkReachableObjects调用另外一个成员函数ProcessMarkStack来递归标记根集对象和Dirty Card引用的对象的可达对象，后者的实现如下所示：
void MarkCompact::ProcessMarkStack() {
TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
while (!mark_stack_->IsEmpty()) {
Object* obj = mark_stack_->PopBack();
DCHECK(obj != nullptr);
ScanObject(obj);
}
}这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
MarkCompact类的成员函数ProcessMarkStack逐个地将Mark Stack的对象弹出来，并且调用另外一个成员函数ScanObject对它们的引用类型的成员变量进行标记。注意， MarkCompact类的成员函数ScanObject在标记对象的过程中，也会可能压入新的对象到Mark Stack中，因此这是一个递归标记的过程。
MarkCompact类的成员函数ScanObject的实现如下所示：
void MarkCompact::ScanObject(Object* obj) {
MarkCompactMarkObjectVisitor visitor(this);
obj->VisitReferences<kMovingClasses>(visitor, visitor);
}这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
从这里可以看到，对象obj的引用类型的成员变量引用的对象是通过MarkCompactMarkObjectVisitor类来进行标记的，如下所示：
class MarkCompactMarkObjectVisitor {
public:
explicit MarkCompactMarkObjectVisitor(MarkCompact* collector) : collector_(collector) {
}
void operator()(Object* obj, MemberOffset offset, bool /*is_static*/) const ALWAYS_INLINE
EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_, Locks::heap_bitmap_lock_) {
// Object was already verified when we scanned it.
collector_->MarkObject(obj->GetFieldObject<mirror::Object, kVerifyNone>(offset));
}
void operator()(mirror::Class* klass, mirror::Reference* ref) const
SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) {
collector_->DelayReferenceReferent(klass, ref);
}
private:
MarkCompact* const collector_;
};这个类定义在文件art/runtime/gc/collector/mark_compact.cc中。
MarkCompactMarkObjectVisitor类有两个版本的符号重载成员函数()。其中，上面一个用来处理那些指向了普通对象的成员变量，而下面一个用来处理指向了引用对象的成员变量。其中，普通对象通过前面分析过的MarkCompact类的成员函数MarkObject进行标记，而引用对象则通过MarkCompact类的成员函数DelayReferenceReferent延迟进行处理。注意，从前面分析的MarkCompact类的成员函数MarkingPhase可以知道，上述的引用对象在递归标记可达对象结束之后，会通过MarkCompact类的成员函数ProcessReferences进行处理。
这一步完成之后，Mark-Compact GC的标记阶段就执行完成了。注意，与Semi-Space GC和Generational Semi-Space GC不一样，Mark-Compact GC在标记阶段并没有对象Bump Pointer Space的存活对象进行移动，而是在接下来的回收阶段再执行此操作。
前面提到，Mark-Compact GC的回收阶段是通过调用MarkCompact类的成员函数ReclaimPhase来执行的。因此，接下来我们就继续分析MarkCompact类的成员函数ReclaimPhase的实现，如下所示：
void MarkCompact::ReclaimPhase() {
TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
WriterMutexLock mu(Thread::Current(), *Locks::heap_bitmap_lock_);
// Reclaim unmarked objects.
Sweep(false);
// Swap the live and mark bitmaps for each space which we modified space. This is an
// optimization that enables us to not clear live bits inside of the sweep. Only swaps unbound
// bitmaps.
SwapBitmaps();
GetHeap()->UnBindBitmaps(); // Unbind the live and mark bitmaps.
Compact();
}这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
MarkCompact类的成员函数ReclaimPhase首先调用成员函数Sweep回收Non Moving Space和Large Object Space的垃圾，接着再调用成员函数SwapBitmaps交换ART运行时的Live Bitmap和Mark Bitmap。由于在回收垃圾之后，Live Bitmap和Mark Bitmap就没有什么用了，因此这时候MarkCompact类的成员函数ReclaimPhase还会调用Heap类的成员函数UnBindBitmaps清零各个Space的Live Bitmap和Mark Bitmap，以便下次GC时可以直接使用。
最后，MarkCompact类的成员函数ReclaimPhase调用成员函数Compact对Bump Pointer Space的存活对象进行移动压缩，并且修改引用了这些被移动对象的引用，它的实现如下所示：
void MarkCompact::Compact() {
TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
CalculateObjectForwardingAddresses();
UpdateReferences();
MoveObjects();
// Space
int64_t objects_freed = space_->GetObjectsAllocated() - live_objects_in_space_;
int64_t bytes_freed = reinterpret_cast<int64_t>(space_->End()) -
reinterpret_cast<int64_t>(bump_pointer_);
t.NewTiming("RecordFree");
space_->RecordFree(objects_freed, bytes_freed);
RecordFree(ObjectBytePair(objects_freed, bytes_freed));
space_->SetEnd(bump_pointer_);
// Need to zero out the memory we freed. TODO: Use madvise for pages.
memset(bump_pointer_, 0, bytes_freed);
}这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
MarkCompact类的成员函数Compact完成了以下三个重要的操作之后，再统计Mark-Compact GC释放的对象数和内存字节数：
1. 调用MarkCompact类的成员函数CalculateObjectForwardingAddresses计算每一个将要被移动的对象要被移动到的新地址。
- 调用MarkCompact类的成员函数UpdateReferences引用那些引用了被移动对象的引用，因为这时候被移动对象的新地址已经确定了。
3. 调用MarkCompact类的成员函数MoveObjects将要被移动的对象移动到前面计算好的新地址中。
为了更好地理解Mark-Compact GC，接下来我们继续对上述提到的MarkCompact类的三个成员函数的实现进行分析。
MarkCompact类的成员函数CalculateObjectForwardingAddresses的实现如下所示：
void MarkCompact::CalculateObjectForwardingAddresses() {
TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
// The bump pointer in the space where the next forwarding address will be.
bump_pointer_ = reinterpret_cast<byte*>(space_->Begin());
// Visit all the marked objects in the bitmap.
CalculateObjectForwardingAddressVisitor visitor(this);
objects_before_forwarding_->VisitMarkedRange(reinterpret_cast<uintptr_t>(space_->Begin()),
reinterpret_cast<uintptr_t>(space_->End()),
visitor);
}这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
MarkCompact类的成员函数CalculateObjectForwardingAddresses首先是获得当前正在处理的Bump Pointer Space的起始地址，并且保存在成员变量bump_pointer_中，接下来再通过CalculateObjectForwardingAddressVisitor类的操作符重载函数()来处理每一个在当前正在处理的Bump Pointer Space上分配的、并且仍然存活的对象。
CalculateObjectForwardingAddressVisitor类的操作符重载函数()的实现如下所示：
class CalculateObjectForwardingAddressVisitor {
public:
explicit CalculateObjectForwardingAddressVisitor(MarkCompact* collector)
: collector_(collector) {}
void operator()(mirror::Object* obj) const EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_,
Locks::heap_bitmap_lock_) {
......
collector_->ForwardObject(obj);
}
private:
MarkCompact* const collector_;
};这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
CalculateObjectForwardingAddressVisitor类的操作符重载函数()调用MarkCompact类的成员函数ForwardObject来计算对象obj移动后的新地址，它的实现如下所示：
void MarkCompact::ForwardObject(mirror::Object* obj) {
const size_t alloc_size = RoundUp(obj->SizeOf(), space::BumpPointerSpace::kAlignment);
LockWord lock_word = obj->GetLockWord(false);
// If we have a non empty lock word, store it and restore it later.
if (lock_word.GetValue() != LockWord().GetValue()) {
// Set the bit in the bitmap so that we know to restore it later.
objects_with_lockword_->Set(obj);
lock_words_to_restore_.push_back(lock_word);
}
obj->SetLockWord(LockWord::FromForwardingAddress(reinterpret_cast<size_t>(bump_pointer_)),
false);
bump_pointer_ += alloc_size;
++live_objects_in_space_;
}这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
MarkCompact类的成员函数ForwardObject首先是获得对象obj的大小alloc_size，接着再判断它的LockWord是否不等于空。如果不等于空的话，就将其在MarkCompact类的成员变量objects_with_lockword_描述的一个ContinuousSpaceBitmap的对应位设置为1，并且将该LockWord保存在MarkCompact类的成员变量lock_words_to_restore_描述的一个队列中。
从前面ART运行时Compacting GC简要介绍和学习计划一文可以知道，一个对象的LockWord描述了该对象的状态信息，例如锁状态、Hash值以及Forwarding Address等。由于接下来我们要将对象obj移动后的新地址记录在它的LockWord中，也就是要借它的LockWord来用，因此当对象obj原来的LockWord不等于空的情况下，就需要先将它保存起来，以便对象obj移动完成之后，可以恢复原来的LockWord。
在Mark-Compact GC中，下一个对象要移动至的地址永远记录在MarkCompact类的成员变量bump_pointer_中，因此通过MarkCompact类的成员变量bump_pointer_就可以得到对象obj要移动至的地址。由于对象obj使用了当前MarkCompact类的成员变量bump_pointer_的值，因此我们需要更新它的值，即需要加上对象obj的大小，这样就可以使得它永远指向下一个要移动的对象的新地址。
回到MarkCompact类的成员函数CalculateObjectForwardingAddresses中，当它执行完成之后，在当前正在处理的Bump Pointer Space上分配的、并且仍然活着的对象的新地址就计算完毕，即都已经保存在它们自己的LockWord中，接下来就可以调用MarkCompact类的成员函数UpdateReferences来更新其它Space对当前正在处理的Bump Pointer Space的引用了。
MarkCompact类的成员函数UpdateReferences的实现如下所示：
void MarkCompact::UpdateReferences() {
TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
Runtime* runtime = Runtime::Current();
// Update roots.
runtime->VisitRoots(UpdateRootCallback, this);
// Update object references in mod union tables and spaces.
for (const 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) {
// TODO: Improve naming.
TimingLogger::ScopedTiming t(
space->IsZygoteSpace() ? "UpdateZygoteModUnionTableReferences" :
"UpdateImageModUnionTableReferences",
GetTimings());
table->UpdateAndMarkReferences(&UpdateHeapReferenceCallback, this);
} else {
// No mod union table, so we need to scan the space using bitmap visit.
// Scan the space using bitmap visit.
accounting::ContinuousSpaceBitmap* bitmap = space->GetLiveBitmap();
if (bitmap != nullptr) {
UpdateObjectReferencesVisitor visitor(this);
bitmap->VisitMarkedRange(reinterpret_cast<uintptr_t>(space->Begin()),
reinterpret_cast<uintptr_t>(space->End()),
visitor);
}
}
}
CHECK(!kMovingClasses)
<< "Didn't update large object classes since they are assumed to not move.";
// Update the system weaks, these should already have been swept.
runtime->SweepSystemWeaks(&MarkedForwardingAddressCallback, this);
// Update the objects in the bump pointer space last, these objects don't have a bitmap.
UpdateObjectReferencesVisitor visitor(this);
objects_before_forwarding_->VisitMarkedRange(reinterpret_cast<uintptr_t>(space_->Begin()),
reinterpret_cast<uintptr_t>(space_->End()),
visitor);
// Update the reference processor cleared list.
heap_->GetReferenceProcessor()->UpdateRoots(&MarkedForwardingAddressCallback, this);
}这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
在分析MarkCompact类的成员函数UpdateReferences的实现之前，我们首先要明确有哪些Space的对象引用了当前正在处理的Bump Pointer Space的对象。从前面ART运行时Compacting GC堆创建过程分析一文可以知道，Mark-Compact GC使用的Space有Image Space、Zygote Space、Non-Moving Space、Bump Pointer Space和Large Object Space。因此，在这些Space上分配的对象都有可能对当前正在处理的Bump Pointer Space的对象产生引用。此外，还有三类对象可能会对当前正在处理的Bump Pointer Space产生引用，那就是根集对象、ART运行时内部分配的对象以及那些特殊处理的引用对象。
对于根集对象，我们只需要调用Runtime类的成员函数VisitRoots重新遍历一下它们，并且对于每一个根集对象，都调用MarkCompact类的静态成员函数UpdateRootCallback来修改它们对当前正在处理的Bump Pointer Space的引用，如下所示：
void MarkCompact::UpdateRootCallback(Object** root, void* arg, uint32_t /*thread_id*/,
RootType /*root_type*/) {
mirror::Object* obj = *root;
mirror::Object* new_obj = reinterpret_cast<MarkCompact*>(arg)->GetMarkedForwardAddress(obj);
if (obj != new_obj) {
*root = new_obj;
DCHECK(new_obj != nullptr);
}
}这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
参数root描述的就是在当前调用栈上的、引用了根集对象的一个Slot。MarkCompact类的静态成员函数UpdateRootCallback首先是调用成员函数GetMarkedForwardAddress检查被引用的根集对象是否设置有Forward Address。如果设置有的话，就说明对应的调用栈Slot引用了当前正在处理的Bump Pointer Space的对象，因此这时候就需要修改该调用栈Slot的值，使得它引用的是移动后的根集对象。
MarkCompact类的成员函数GetMarkedForwardAddress的实现如下所示：
inline mirror::Object* MarkCompact::GetMarkedForwardAddress(mirror::Object* obj) const {
......
if (objects_before_forwarding_->HasAddress(obj)) {
......
mirror::Object* ret =
reinterpret_cast<mirror::Object*>(obj->GetLockWord(false).ForwardingAddress());
......
return ret;
}
......
return obj;
}这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
如果对象obj位于MarkCompact类的成员变量objects_before_forwarding_描述的一个ContinuousSpaceBitmap中，那么就说明它是一个位于当前正在处理的Bump Pointer Space的对象。又由于对象obj是一个根集对象，也就是它肯定是活着的，因此就可以从它的LockWord中获取到它的Forwarding Address，也就是它移动后的地址。这个地址是在前面分析的MarkCompact类的成员函数ForwardObject计算并且设置的。
回到MarkCompact类的成员函数UpdateReferences中，更新完成根集对象对正在处理的Bump Pointer Space的引用之后，接下来继续更新Image Space、Zygote Space和Non Moving Space对正在处理的Bump Pointer Space的引用。这三个Space均是保存在ART运行时堆的Continuous Space列表中。同时，保存在这个Continuous Space列表中的Space还包含当前正在处理的Bump Pointer Space，但是由于这个Bump Pointer Space既没有关联有Mod Union Table，也没有关联有Live Bitmap，因此，中间的for循环只是用来更新Image Space、Zygote Space和Non Moving Space对正在处理的Bump Pointer Space的引用。
对于Image Space和Zygote Space，它们都关联有Mod Union Table，因此，我们就可以通过调用这个Mod Union Table的成员函数UpdateAndMarkReferences来遍历上次GC以来发生过修改的对象。并且对于每一个这样的对象，都调用MarkCompact类的静态成员函数UpdateHeapReferenceCallback更新它们对当前正在处理的Bump Pointer Space的引用。
MarkCompact类的静态成员函数UpdateHeapReferenceCallback实现如下所示：
void MarkCompact::UpdateHeapReferenceCallback(mirror::HeapReference<mirror::Object>* reference,
void* arg) {
reinterpret_cast<MarkCompact*>(arg)->UpdateHeapReference(reference);
}这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
MarkCompact类的静态成员函数UpdateHeapReferenceCallback通过调用另外一个成员函数UpdateHeapReference来更新参数reference描述的位置（位于Image Space和Zygote Space上的某个对象的某个成员变量）对当前正在处理的Bump Pointer Space的引用，如下所示：
inline void MarkCompact::UpdateHeapReference(mirror::HeapReference<mirror::Object>* reference) {
mirror::Object* obj = reference->AsMirrorPtr();
if (obj != nullptr) {
mirror::Object* new_obj = GetMarkedForwardAddress(obj);
if (obj != new_obj) {
DCHECK(new_obj != nullptr);
reference->Assign(new_obj);
}
}
}这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
MarkCompact类的成员函数UpdateHeapReference与前面分析的MarkCompact类的成员函数UpdateRootCallback的实现逻辑基本上是一样的，都是先通过调用MarkCompact类的成员函数GetMarkedForwardAddress判断参数reference描述的位置引用的对象是否设置有Forwarding Address。如果设置有的话，就需要修改该位置的值。
回到MarkCompact类的成员函数UpdateReferences中，对于Non Moving Space，它没有关联有Mod Union Table，但是它关联有Live Bitmap。因此，通过这个Live Bitmap，也可以逐个地检查当前Non Moving Space的存活对象是否引用了当前正在处理的Bump Pointer Space的对象。如果有引用，那么就通过UpdateObjectReferencesVisitor类的操作符重载函数()对它们的引用位置进行修改。
UpdateObjectReferencesVisitor类的操作符重载函数()的实现如下所示：
class UpdateObjectReferencesVisitor {
public:
explicit UpdateObjectReferencesVisitor(MarkCompact* collector) : collector_(collector) {
}
void operator()(mirror::Object* obj) const SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_) ALWAYS_INLINE {
collector_->UpdateObjectReferences(obj);
}
private:
MarkCompact* const collector_;
};这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
从这里就可以看到，在Non Moving Space上分配的对象，是通过调用MarkCompact类的成员函数UpdateObjectReferences来修改它们对当前正在处理的Bump Pointer Space的引用的。
MarkCompact类的成员函数UpdateObjectReferences的实现如下所示：
void MarkCompact::UpdateObjectReferences(mirror::Object* obj) {
UpdateReferenceVisitor visitor(this);
obj->VisitReferences<kMovingClasses>(visitor, visitor);
}这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
MarkCompact类的成员函数UpdateObjectReferences通过调用Object类的成员函数VisitReferences来遍历对象obj每一个类型为引用的成员变量，并且通过UpdateReferenceVisitor类的操作符重载函数()来更新它们对当前正在处理的Bump Pointer Space的引用。
UpdateReferenceVisitor类的操作符重载函数()有两个版本的实现，如下所示：
class UpdateReferenceVisitor {
public:
explicit UpdateReferenceVisitor(MarkCompact* collector) : collector_(collector) {
}
void operator()(Object* obj, MemberOffset offset, bool /*is_static*/) const
ALWAYS_INLINE EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_, Locks::heap_bitmap_lock_) {
collector_->UpdateHeapReference(obj->GetFieldObjectReferenceAddr<kVerifyNone>(offset));
}
void operator()(mirror::Class* /*klass*/, mirror::Reference* ref) const
EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_, Locks::heap_bitmap_lock_) {
collector_->UpdateHeapReference(
ref->GetFieldObjectReferenceAddr<kVerifyNone>(mirror::Reference::ReferentOffset()));
}
private:
MarkCompact* const collector_;
};这两个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
如果对象obj有一个引用类型的成员变量，那么这个成员变量要么是一个普通的引用，即是一个强引用，要么是一个弱引用，即Soft Reference、Weak Reference、Phantom Rerference或者Finalizer Reference。对于前者，通过上面版本的操作符重载函数()进行处理；而对于后者，通过下面版本的操作符重载函数()进行处理。这两者唯一的区别就是获得被引用对象的方式不同。一旦获得了被引用对象，就可以调用前面分析过的MarkCompact类的成员函数UpdateHeapReference来更新对应的成员变量的值了。
回到MarkCompact类的成员函数UpdateReferences中，这时候Image Space、Zygote Space和Non Moving Space的对象对当前正在处理的Bump Pointer Space的对象的引用就更新完毕，接下来需要继续对Large Object Space和Bump Pointer Space进行同样的处理。
首先看对Large Object Space的处理。从前面ART运行时Compacting GC为新创建对象分配内存的过程分析一文可以知道，在Large Object Space上分配的对象都是属于原子类数组对象。原子类数组对象只有一个引用类型的成员变量，它引用的是一个Class对象，该Class对象描述原子类数组对象的类型。除此之外，原子类数组对象就没有其它引用类型的成员变量了。
ART运行时定义了一个常量kMovingClasses，当ART运行时支持Mark-Compact GC时，它的值就等于false，如下所示：
// True if we allow moving classes.
static constexpr bool kMovingClasses = !kMarkCompactSupport;这个常量定义在文件art/runtime/globals.h中。
又当常量kMovingClasses的值等于false时，ART运行时在分配Class对象时，都会在Non Moving Space进行分配，如下所示：
mirror::Class* ClassLinker::AllocClass(Thread* self, mirror::Class* java_lang_Class,
uint32_t class_size) {
......
gc::Heap* heap = Runtime::Current()->GetHeap();
mirror::Class::InitializeClassVisitor visitor(class_size);
mirror::Object* k = kMovingClasses ?
heap->AllocObject<true>(self, java_lang_Class, class_size, visitor) :
heap->AllocNonMovableObject<true>(self, java_lang_Class, class_size, visitor);
......
return k->AsClass();
}这个函数定义在文件art/runtime/class_linker.cc。
这意味着在Large Object Space上分配的对象，不可能会引用在Bump Pointer Space分配的对象，因此MarkCompact类的成员函数UpdateReferences就不需要对Large Object Space作任何的处理。
我们再来看MarkCompact类的成员函数UpdateReferences对Bump Pointer Space的处理。这个Bump Pointer Space实际上就是正在处理的Bump Pointer Space，在上面分配的对象是可能发生相互引用的情况的，因此MarkCompact类的成员函数UpdateReferences就需要对它进行处理。
虽然Bump Pointer Space既没有关联有Mod Union Table，也没有关联有Live Bitmap，不过MarkCompact类的成员变量objects_before_forwarding_描述的ContinuousSpaceBitmap起到的作用与Live Bitmap是一样的，因此MarkCompact类的成员函数UpdateReferences就可以像处理Non Moving Space的方式一样处理Bump Pointer Space。
现在，就剩下ART运行时内部分配的对象以及那些特殊处理的引用对象没有处理了。ART运行时内部分配的对象指的就是那些常量字符串池的字符串对象、Monitor对象和在JNI创建的全局弱引用对象等。对于这一类存活的对象，通过调用Runtime类的成员函数SweepSystemWeaks进行遍历。Runtime类的成员函数SweepSystemWeaks在遍历这些对象的过程中，会调用MarkCompact类的静态成员函数MarkedForwardingAddressCallback来判断它们是否引用了当前正在处理的Bump Pointer Space的对象。如果引用了的话，那么就会更新相应的位置的引用值。
MarkCompact类的静态成员函数MarkedForwardingAddressCallback的实现如下所示：
mirror::Object* MarkCompact::MarkedForwardingAddressCallback(mirror::Object* obj, void* arg) {
return reinterpret_cast<MarkCompact*>(arg)->GetMarkedForwardAddress(obj);
}这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
从这里就可以看到，MarkCompact类的静态成员函数MarkedForwardingAddressCallback是调用前面分析过的MarkCompact类的成员函数GetMarkedForwardAddress来决断对象obj是否设置有Forwarding Address的。如果设置有Forwarding Address，那么就说明对象obj是位于当前正在处理的Bump Pointer Space中的，因此就会把该Forwarding Address返回给调用者，以便调用者更新对应位置的引用值。
最后，就剩下引用对象没有处理没有处理了。引用对象，即Soft Reference、Weak Reference、Phantom Rerference和Finalizer Reference这些类型的对象，它们都是通过ReferenceProcessor类来进行处理的。ReferenceProcessor类内部维护有了一个目标对象已经被回收了的引用对象列表。这些引用对象有可能是在当前正在处理的Bump Pointer Space中分配的，因此就需要对该列表进行更新。这是通过调用ReferenceProcessor类的成员函数UpdateRoots进行处理的，并且也是通过MarkCompact类的静态成员函数MarkedForwardingAddressCallback来获得是在当前正在处理的Bump Pointer Space中分配的对象的Forwarding Address的。
这样，当MarkCompact类的成员函数UpdateReferences执行完毕，所有引用了位于当前正在处理的Bump Pointer Space上的对象的位置均已得到了更新。回到MarkCompact类的成员函数Compact中，它接下来要做的一件事情就是调用另外一个成员函数MoveObjects对当前正在处理的Bump Pointer Space的对象进行移动，也就是将存活的对象按地址值从小到大的顺序依次排列在Bump Pointer Space的前半部分，以便解决内存碎片问题。
MarkCompact类的成员函数MoveObjects的实现如下所示：
void MarkCompact::MoveObjects() {
TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
// Move the objects in the before forwarding bitmap.
MoveObjectVisitor visitor(this);
objects_before_forwarding_->VisitMarkedRange(reinterpret_cast<uintptr_t>(space_->Begin()),
reinterpret_cast<uintptr_t>(space_->End()),
visitor);
CHECK(lock_words_to_restore_.empty());
}这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
由于前面已经将当前正在处理的Bump Pointer Space上每一个存活对象的新地址都已经计算好了，因此现在只需要将它们从原地址拷贝过去即可。其中，当前正在处理的Bump Pointer Space上的存活对象可以通过MarkCompact类的成员变量objects_before_forwarding_指向的一个ContinuousSpaceBitmap对象获得，而这些存活对象的移动是通过MoveObjectVisitor类的操作符重载函数()来实现的，如下所示：
class MoveObjectVisitor {
public:
explicit MoveObjectVisitor(MarkCompact* collector) : collector_(collector) {
}
void operator()(mirror::Object* obj) const SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_) ALWAYS_INLINE {
collector_->MoveObject(obj, obj->SizeOf());
}
private:
MarkCompact* const collector_;
};这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
从这里可以看到，MoveObjectVisitor类的操作符重载函数()是通过调用MarkCompact类的成员函数MoveObject来移动参数obj描述的对象的，后者的实现如下所示：
void MarkCompact::MoveObject(mirror::Object* obj, size_t len) {
// Look at the forwarding address stored in the lock word to know where to copy.
DCHECK(space_->HasAddress(obj)) << obj;
uintptr_t dest_addr = obj->GetLockWord(false).ForwardingAddress();
mirror::Object* dest_obj = reinterpret_cast<mirror::Object*>(dest_addr);
DCHECK(space_->HasAddress(dest_obj)) << dest_obj;
// Use memmove since there may be overlap.
memmove(reinterpret_cast<void*>(dest_addr), reinterpret_cast<const void*>(obj), len);
// Restore the saved lock word if needed.
LockWord lock_word;
if (UNLIKELY(objects_with_lockword_->Test(obj))) {
lock_word = lock_words_to_restore_.front();
lock_words_to_restore_.pop_front();
}
dest_obj->SetLockWord(lock_word, false);
}这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
这里首先需要明确，参数obj是位于正在处理的Bump Pointer Space的，因此，我们就可以通过它的LockWord获得它的Forwarding Address，也就是它要移动至的新地址。有了这个新地址之后，就可以通过memmove将它的内容从旧地址拷贝到新地址了。
由于对象obj的LockWord被借用了来保存新地址，因此，当它被移动至新地址之后，需要恢复它原先的LockWord值。当然，并不是所有要移动的对象的LockWord值都需要恢复，因为有些对象的LockWord值本来就是空的。对于原来的LockWord值为空的对象，只需要将移动后得到的对象的LockWord值也设置为空即可。而对于原来的LockWord值不空的对象，可以通过MarkCompact类的成员变量lock_words_to_restore_指向的一个队列获得。并且判断对象obj原来的LockWord值不为空可以通过MarkCompact类的成员变量objects_with_lockword_指向的一个ContinuousSpaceBitmap对象判断。
最后一点还需要注意的是，在计算正在处理的Bump Pointer Space上的存活对象的新对象时，是按照地址值从小到大的顺序进行的。也就是说，对于原来LockWord值不为空的对象，它们原来的LockWord值也是按照对象地址从小到大的顺序保存在MarkCompact类的成员变量lock_words_to_restore_指向的一个队列中的。现在执行移动对象的操作时，也是按照对象地址从小到大的顺序进行的，因此就可以依次从上述队列中准确地获得对象原先的LockWord值。
这样，Mark-Compact GC的回收阶段也执行完成了，最后剩下的结束阶段是通过调用MarkCompact类的成员函数FinishPhase实现的，如下所示：
void MarkCompact::FinishPhase() {
TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
space_ = nullptr;
CHECK(mark_stack_->IsEmpty());
mark_stack_->Reset();
// Clear all of the spaces' mark bitmaps.
WriterMutexLock mu(Thread::Current(), *Locks::heap_bitmap_lock_);
heap_->ClearMarkedObjects();
// Release our bitmaps.
objects_before_forwarding_.reset(nullptr);
objects_with_lockword_.reset(nullptr);
}这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。
Mark-Comapctt GC的结束阶段主要是执行一些清理工作，包括：
1. 将MarkCompact类的成员变量space_置空。这个成员变量用来指定当前要进压缩处理的Bump Pointer Space。每次在执行Mark-Compact GC之前，会首先对它进行初始化。
2. 重置ART运行时堆的Mark Stack。这个Mark Stack保存在MarkCompact类的成员变量markstack。在每次Mark-Compact GC的初始化阶段，都会对该成员变量进行初始化。
3. 调用Heap类的成员函数ClearMarkedObjects对ART运行时堆的各个Space的Mark Bitmap进行清零的操作，以便下次可以使用。
4. 将MarkCompact类的成员变量objects_before_forwarding_和objects_with_lockword_置空。它们在每次Mark-Compact GC的标记阶段会被重新创建和初始化，并且在回收阶段进行使用。
至此，Mark-Compact GC的执行过程就分析完成了。与前面ART运行时Semi-Space（SS）和Generational Semi-Space（GSS）GC执行过程分析一文分析的Semi-Space GC和Generational Semi-Space GC相比，它们的共同特点都是在Stop-the-word前提下进行的，并且都是通过移动对象来实现垃圾回收和内存压缩的目的。不过前者的对象移动操作是就地进行的，而后两者的对象移动操作是要通过一个额外的Space来进行的。当然，Mark-Compact GC的对象移动操作可以就地进行并不是免费的午餐，它要付出的代价在回收阶段执行一个额外的新地址计算操作。这又是一个计算机世界以时间换空间或者说以空间换时间的例子。
现在，我们就对ART运行时的Mark-Sweep GC和Compacting GC都做了分析，也知道了它们的优缺点。如果我们能够扬长避短，那么就可以既解决GC的效率问题，又能解决内存的碎片问题。在接下来的一篇文章中，我们就会重点分析ART运行时是如何最大限度地发挥Mark-Sweep GC和Compacting GC的长处的，敬请关注！更多的信息也可以关注老罗的新浪微博：http://weibo.com/shengyangluo/home。