ART运行时Mark-Compact( MC)GC执行过程分析.doc

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的执行过程。从前面一文可以知道，Mark-Compact GC主要是针对ART运行时正在使用的Bump Pointer Space进行压缩，如图1所示：从图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运行时内部，所有的GC都是通过Heap类的成员函数CollectGarbageInternal开始执行的，并且当决定要执行Mark-Compact GC时，最终会以MarkCompact类的成员函数RunPhases作为入口点，如下所示：cpp view plain copyvoid 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实现，如下所示：cpp view plain copyvoid MarkCompact:InitializePhase() TimingLogger:ScopedTiming t(_FUNCTION_, GetTimings(); mark_stack_ = heap_-GetMarkStack(); . immune_region_.Reset(); . / TODO: I dont 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实现，如下所示：cpp view plain copyvoid 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 dont 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_with_lockword_。其中，前者用来记录当前要进行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引用的对象可达的对象。 10. 调用MarkCompact类的成员函数ProcessReferences处理引用类型的对象，即Soft Reference、Weak Reference、Phantom Reference和Finalizer Reference对象。 11. 调用MarkCompact类的成员函数SweepSystemWeaks处理那些没有被标记的常量字符串、Monitor对象和在JNI创建的全局弱引用对象等。 12. 调用MarkCompact类的成员函数RevokeAllThreadLocalBuffers回收各个ART运行时线程的局部分配缓冲区。 在上述的操作中，我们主要是分析第2、7、8和9操作，即MarkCompact类的成员函数BindBitmaps、MarkRoots、UpdateAndMarkModUnion和MarkReachableObjects的实现、其它的操作可以参考或者一文。 MarkCompact类的成员函数BindBitmaps的实现如下所示：cpp view plain copyvoid 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 VisitRoots(MarkRootCallback, this); 这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。 MarkCompact类的成员函数MarkRoots调用Runtime类的成员函数VisitRoots遍历当前的根集对象，并且对于每一个根集对象，都调用MarkCompact类的静态成员函数MarkRootCallback进行标记处理。 MarkCompact类的静态成员函数MarkRootCallback的实现如下所示：cpp view plain copy 在CODE上查看代码片派生到我的代码片void MarkCompact:MarkRootCallback(Object* root, void* arg, uint32_t /*thread_id*/, RootType /*root_type*/) reinterpret_cast(arg)-MarkObject(*root); 这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。 MarkCompact类的静态成员函数MarkRootCallback又是通过调用另外一个成员函数MarkObject来标记根集对象，如下所示：cpp view plain copy 在CODE上查看代码片派生到我的代码片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实现的，如下所示：cpp view plain copy 在CODE上查看代码片派生到我的代码片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是不需要进行垃圾回收的，因此这里就仅仅对它们进行处理。在前面这篇文章提到，Image Space和Zygote Space都是有一个关联的Mod Union Table，并且通过调用这个Mod Union Table的成员函数UpdateAndMarkReferences来处理Dirty Card引用的对象。 对于Dirty Card引用的每一个对象，即Dirty Card记录的上次GC以来有修改过引用类型的成员变量的对象，都会被MarkCompact类的静态成员函数MarkHeapReferenceCallback进行标记，如下所示：cpp view plain copy 在CODE上查看代码片派生到我的代码片void MarkCompact:MarkHeapReferenceCallback(mirror:HeapReference* obj_ptr, void* arg) reinterpret_cast(arg)-MarkObject(obj_ptr-AsMirrorPtr(); 这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。 从这里就可以看出，Dirty Card引用的对象与根集对象一样，都是通过MarkCompact类的成员函数MarkObject进行标记的。 Dirty Card引用的对象与根集对象都标记完成之后，就开始标记它们可达的对象了，这是通过调用MarkCompact类的成员函数MarkReachableObjects来实现的，如下所示：cpp view plain copy 在CODE上查看代码片派生到我的代码片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引用的对象的可达对象，后者的实现如下所示：cpp view plain copy 在CODE上查看代码片派生到我的代码片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的实现如下所示：cpp view plain copy 在CODE上查看代码片派生到我的代码片void MarkCompact:ScanObject(Object* obj) MarkCompactMarkObjectVisitor visitor(this); obj-VisitReferences(visitor, visitor); 这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。 从这里可以看到，对象obj的引用类型的成员变量引用的对象是通过MarkCompactMarkObjectVisitor类来进行标记的，如下所示：cpp view plain copy 在CODE上查看代码片派生到我的代码片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(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的实现，如下所示：cpp view plain copy 在CODE上查看代码片派生到我的代码片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的存活对象进行移动压缩，并且修改引用了这些被移动对象的引用，它的实现如下所示：cpp view plain copy 在CODE上查看代码片派生到我的代码片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(space_-End() - reinterpret_cast(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计算每一个将要被移动的对象要被移动到的新地址。 2. 调用MarkCompact类的成员函数UpdateReferences引用那些引用了被移动对象的引用，因为这时候被移动对象的新地址已经确定了。 3. 调用MarkCompact类的成员函数MoveObjects将要被移动的对象移动到前面计算好的新地址中。 为了更好地理解Mark-Compact GC，接下来我们继续对上述提到的MarkCompact类的三个成员函数的实现进行分析。 MarkCompact类的成员函数CalculateObjectForwardingAddresses的实现如下所示：cpp view plain copy 在CODE上查看代码片派生到我的代码片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(space_-Begin(); / Visit all the marked objects in the bitmap. CalculateObjectForwardingAddressVisitor visitor(this); objects_before_forwarding_-VisitMarkedRange(reinterpret_cast(space_-Begin(), reinterpret_cast(space_-End(), visitor); 这个函数定义在文件art/runtime/gc/collector/mark_compact.cc中。 MarkCompact类的成员函数CalculateObjectForwardingAddresses首先是获得当前正在处理的Bump Pointer Space的起始地址，并且保存在成员变量bump_pointer_中，接下来再通过CalculateObjectForwardingAddressVisitor类的操作符重载函数()来处理每一个在当前正在处理的Bump Pointer Space上分配的、并且仍然存活的对象。 CalculateObjectForwardingAddressVisitor类的操作符重载函数()的实现如下所示：cpp view plain copy 在CODE上查看代码片派生到我的代码片class CalculateObjectForwardingAddressVisitor public: explicit CalculateObjectForward