ART运行时Semi-Space(SS)和Generational Semi-Space(GSS)GC执行过程分析.doc

ART运行时Semi-Space（SS）和Generational Semi-Space（GSS）GC执行过程分析Semi-Space（SS）GC和Generational Semi-Space（GSS）GC是ART运行时引进的两个Compacting GC。它们的共同特点是都具有一个From Space和一个To Space。在GC执行期间，在From Space分配的还存活的对象会被依次拷贝到To Space中，这样就可以达到消除内存碎片的目的。本文就将SS GC和GSS GC的执行过程分析进行详细分析。与SS GC相比，GSS GC还多了一个Promote Space。当一个对象是在上一次GC之前分配的，并且在当前GC中仍然是存活的，那么它就会被拷贝到Promote Space中，而不是To Space中。这相当于是简单地将对象划分为新生代和老生代的，即在上一次GC之前分配的对象属于老生代的，而在上一次GC之后分配的对象属于新生代的。一般来说，老生代对象的存活性要比新生代的久，因此将它们拷贝到Promote Space中去，可以避免每次执行SS GC或者GSS GC时，都需要对它们进行无用的处理。 总结来说，SS GC和GSS GC的执行过程就如图1和图2所示：在图1和图2中，Bump Pointer Space 1和Bump Pointer Space 2就是我们前面说的From Space和To Space。接下来我们就结合源码来详细分析它们的执行过程。 从前面一文可以知道，在ART运行时内部，都是通过调用Heap类的成员函数CollectGarbageInternal开始执行GC的，因此，我们就从它开始分析SS GC和GSS GC的执行过程。 Heap类的成员函数CollectGarbageInternal的实现如下所示：cpp view plain copycollector:GcType Heap:CollectGarbageInternal(collector:GcType gc_type, GcCause gc_cause, bool clear_soft_references) Thread* self = Thread:Current(); Runtime* runtime = Runtime:Current(); . bool compacting_gc; . MutexLock mu(self, *gc_complete_lock_); / Ensure there is only one GC at a time. WaitForGcToCompleteLocked(gc_cause, self); compacting_gc = IsMovingGc(collector_type_); / GC can be disabled if someone has a used GetPrimitiveArrayCritical. if (compacting_gc & disable_moving_gc_count_ != 0) . return collector:kGcTypeNone; collector_type_running_ = collector_type_; . collector:GarbageCollector* collector = nullptr; / TODO: Clean this up. if (compacting_gc) . switch (collector_type_) case kCollectorTypeSS: / Fall-through. case kCollectorTypeGSS: semi_space_collector_-SetFromSpace(bump_pointer_space_); semi_space_collector_-SetToSpace(temp_space_); semi_space_collector_-SetSwapSemiSpaces(true); collector = semi_space_collector_; break; case kCollectorTypeCC: collector = concurrent_copying_collector_; break; case kCollectorTypeMC: mark_compact_collector_-SetSpace(bump_pointer_space_); collector = mark_compact_collector_; break; default: LOG(FATAL) Invalid collector type static_cast(collector_type_); . gc_type = collector:kGcTypeFull; / TODO: Not hard code this in. . collector-Run(gc_cause, clear_soft_references | runtime-IsZygote(); . RequestHeapTrim(); / Enqueue cleared references. reference_processor_.EnqueueClearedReferences(self); / Grow the heap so that we know when to perform the next GC. GrowForUtilization(collector); . FinishGC(self, gc_type); . return gc_type; 这个函数定义在文件art/runtime/gc/heap.cc中。 Heap类的成员函数CollectGarbageInternal首先是调用成员函数WaitForGcToCompleteLocked确保当前没有GC正在执行。如果有的话，那么就等待它执行完成。接下来再调用成员函数IsMovingGc判断当前要执行的GC是否是一个Compacting GC，即判断Heap类的成员变量collector_type_指向的一个垃圾收集器是否是一个Compacting GC类型的垃圾收集器。如果是一个Compacting GC，但是当前又被禁止执行Compacting GC，即Heap类的成员变量disable_moving_gc_count_不等于0，那么当前GC就是禁止执行的。因此在这种情况下，Heap类的成员函数CollectGarbageInternal就什么也不做就直接返回collector:kGcTypeNone给调用者了。 我们只关注Compacting GC的情况，即变量compacting_gc等于true的情况。在ART运行时中，Compacting GC有四种，分别是Semi-Space GC、Generational Semi-Space GC、Mark-Compact GC和Concurrent Copying GC。其中，Semi-Space GC和Generational Semi-Space GC使用的是同一个垃圾收集器，保存在Heap类的成员变量semi_space_collector_中，区别只在于前者不支持分代而后者支持；Mark-Compact GC和Concurrent Copying GC使用的垃圾收集器保存在Heap类的成员变量mark_compact_collector_和concurrent_copying_collector_中。但是，Concurrent Copying GC在Android 5.0中还没有具体实现，因此实际上就只有前面三种Compacting GC。 Heap类的成员变量semi_space_collector_、mark_compact_collector_和concurrent_copying_collector_的初始化发生在Heap类的构造函数中，如下所示：cpp view plain copyHeap:Heap(size_t initial_size, size_t growth_limit, size_t min_free, size_t max_free, double target_utilization, double foreground_heap_growth_multiplier, size_t capacity, size_t non_moving_space_capacity, const std:string& image_file_name, const InstructionSet image_instruction_set, CollectorType foreground_collector_type, CollectorType background_collector_type, size_t parallel_gc_threads, size_t conc_gc_threads, bool low_memory_mode, size_t long_pause_log_threshold, size_t long_gc_log_threshold, bool ignore_max_footprint, bool use_tlab, bool verify_pre_gc_heap, bool verify_pre_sweeping_heap, bool verify_post_gc_heap, bool verify_pre_gc_rosalloc, bool verify_pre_sweeping_rosalloc, bool verify_post_gc_rosalloc, bool use_homogeneous_space_compaction_for_oom, uint64_t min_interval_homogeneous_space_compaction_by_oom) . if (kMovingCollector) / TODO: Clean this up. const bool generational = foreground_collector_type_ = kCollectorTypeGSS; semi_space_collector_ = new collector:SemiSpace(this, generational, generational ? generational : ); garbage_collectors_.push_back(semi_space_collector_); concurrent_copying_collector_ = new collector:ConcurrentCopying(this); garbage_collectors_.push_back(concurrent_copying_collector_); mark_compact_collector_ = new collector:MarkCompact(this); garbage_collectors_.push_back(mark_compact_collector_); . 这个函数定义在文件art/runtime/gc/heap.cc中。 从这里就可以看出，Heap类的成员变量semi_space_collector_、mark_compact_collector_和concurrent_copying_collector_指向的对象分别是SemiSpace、MarkCompact和ConcurrentCopying。 这里需要注意的是Heap类的成员变量semi_space_collector_，当ART运行时启动时指定的Foreground GC为Generational Semi-Space GC时，它所指向的SemiSpace就是支持分代的；否则的话，就不支持。 回到Heap类的成员函数CollectGarbageInternal中，当当前执行的GC是Semi-Space GC或者Generational Semi-Space GC时，From Space和To Space分别被设置为Heap类的成员变量bump_pointer_space_和temp_space_描述的Space。从前面一文可以知道，这两个成员变量描述的Space均为Bump Pointer Space。此外，此时使用的SemiSpace被告知，当GC执行完毕，需要交换From Space和To Space，也就是交换Heap类的成员变量bump_pointer_space_和temp_space_描述的两个Bump Pointer Space。另外，当当前执行的GC是Mark-Compact GC时，只需要指定一个Bump Pointer Space，也就是Heap类的成员变量bump_pointer_space_所指向的Bump Pointer Space。由于Concurrent Copying GC还没有具体的实现，因此我们忽略与它相关的逻辑。 确定好当前Compacting GC所使用的垃圾收集器之后，需要将参数gc_type设置为collector:kGcTypeFull。这表示Compacting类型的GC垃圾收集器只能执行类型为collector:kGcTypeFull。这有区别是Mark-Sweep类型的GC，它们能够执行collector:kGcTypeSticky、collector:kGcTypePartial和collector:kGcTypeFull三种类型的GC。 无论当前的GC使用的是什么样的垃圾收集器，都是从调用它们的成员函数Run开始执行的。在ART运行时中，所有的垃圾收集器都是从GarbageCollector类继承下来的，并且也继承了GarbageCollector类的成员函数Run。因此，在ART运行时中，所有的GC都是从GarbageCollector类的成员函数Run开始的。 GC执行完毕，Heap类的成员函数CollectGarbageInternal还会做以下四件主要的事情： 1. 调用Heap类的成员函数RequestHeapTrim请求对堆内存进行裁剪，也就是将没有使用到的内存归还给内核。 2. 调用Heap类的成员变量reference_processor_指向的一个ReferenceProcessor对象的成员函数EnqueueClearedReferences将那些目标对象已经被回收了的引用对象增加到它们创建时指定的列表中，以便使得应用程序知道有哪些被引用对象引用的目标对象被回收了。 3. 调用Heap类的成员函数GrowForUtilization根据预先设置的堆利用率相应地设置堆的大小。 4. 调用Heap类的成员函数FinishGC通知其它等待当前GC执行完成的ART运行时线程，以便它们可以继续往下执行自己的逻辑。 这四件事情的具体执行过程可以参考前面一文，这里不再复述。这里我们只关注GC的执行过程，也就是GarbageCollector类的成员函数Run的实现，如下所示：cpp view plain copyvoid GarbageCollector:Run(GcCause gc_cause, bool clear_soft_references) ATRACE_BEGIN(StringPrintf(%s %s GC, PrettyCause(gc_cause), GetName().c_str(); Thread* self = Thread:Current(); uint64_t start_time = NanoTime(); Iteration* current_iteration = GetCurrentIteration(); current_iteration-Reset(gc_cause, clear_soft_references); RunPhases(); / Run all the GC phases. / Add the current timings to the cumulative timings. cumulative_timings_.AddLogger(*GetTimings(); / Update cumulative statistics with how many bytes the GC iteration freed. total_freed_objects_ += current_iteration-GetFreedObjects() + current_iteration-GetFreedLargeObjects(); total_freed_bytes_ += current_iteration-GetFreedBytes() + current_iteration-GetFreedLargeObjectBytes(); uint64_t end_time = NanoTime(); current_iteration-SetDurationNs(end_time - start_time); if (Locks:mutator_lock_-IsExclusiveHeld(self) / The entire GC was paused, clear the fake pauses which might be in the pause times and add / the whole GC duration. current_iteration-pause_times_.clear(); RegisterPause(current_iteration-GetDurationNs(); total_time_ns_ += current_iteration-GetDurationNs(); for (uint64_t pause_time : current_iteration-GetPauseTimes() pause_histogram_.AddValue(pause_time / 1000); ATRACE_END(); 这个函数定义在文件art/runtime/gc/collector/garbage_collector.cc中。 GarbageCollector类的成员函数Run最主要的工作就是调用由子类实现的成员函数RunPhases来执行具体的GC过程，其它的额外工作就是统计GC执行完成后释放的对象数和内存字节数，以及统计GC执行过程中的停顿时间等。这些统计数据有利于我们分析不同GC的执行性能。 这篇文章我们只关注Semi-Space GC和Generational Semi-Space GC的执行过程中，因此，接下来我们就继续分析SemiSpace类的成员函数RunPhases的实现，如下所示：cpp view plain copyvoid SemiSpace:RunPhases() Thread* self = Thread:Current(); InitializePhase(); / Semi-space collector is special since it is sometimes called with the mutators suspended / during the zygote creation and collector transitions. If we already exclusively hold the / mutator lock, then we cant lock it again since it will cause a deadlock. if (Locks:mutator_lock_-IsExclusiveHeld(self) . MarkingPhase(); ReclaimPhase(); . else Locks:mutator_lock_-AssertNotHeld(self); ScopedPause pause(this); . MarkingPhase(); ReaderMutexLock mu(self, *Locks:mutator_lock_); ReclaimPhase(); . FinishPhase(); 这个函数定义在文件art/runtime/gc/collector/semi_space.cc中。 从这里就可以看出，Semi-Space GC和Generational Semi-Space GC的执行过程可以分为四个阶段： 1. 初始化阶段； 2. 标记阶段； 3. 回收阶段； 4. 结束阶段。 其中，标记阶段需要在挂起除当前线程之外的其它所有ART运行时线程的前提下执行，回收阶段则需要在获得Locks:mutator_lock_锁的前提下执行。但是由于在执行同构空间压缩和Foreground/Background GC切换时，会使用到Semi-Space GC或者Generational Semi-Space GC，并且这两个操作均是在挂起除当前线程之外的其它所有ART运行时线程的前提下执行的，而这个挂起操作同时也会获取Locks:mutator_lock_锁，因此，SemiSpace类的成员函数RunPhases在执行回收阶段时，就需要作出决定需不需要执行获取Locks:mutator_lock_锁的操作。这个决定是必要的，因为Locks:mutator_lock_不是一个递归锁，也就是不允许同一个线程重复获得，否则的话就会进入死锁状态。关于锁要不要支持递归获取，技术是没有任何问题的，但是需要考虑的是对程序逻辑的影响。一般来说，支持递归锁不是一个好主意，详细说明可以参考这篇文章：。 基于上述原因，SemiSpace类的成员函数RunPhases在执行标记阶段和回收阶段之前，先判断一下当前线程是否已经获得了Locks:mutator_lock_锁。如果已经获得，那么就说明除当前线程之外的其它所有ART运行时线程均已被挂起，因此这里就可以直接执行它们。否则的话，就是要在执行标记阶段之前，挂起除当前线程之外的其它所有ART运行时线程，并且在执行回收阶段之前，先获取Locks:mutator_lock_锁。 其中，挂起除当前线程之外的其它所有ART运行时线程是通过ScopedPause类来实现。ScopedPause类对象在构造的时候，会挂起除当前线程之外的其它所有ART运行时线程，并且在析构时，自动唤醒这些被挂起的ART运行时线程，如下所示：cpp view plain copyGarbageCollector:ScopedPause:ScopedPause(GarbageCollector* collector) : start_time_(NanoTime(), collector_(collector) Runtime:Current()-GetThreadList()-SuspendAll(); GarbageCollector:ScopedPause:ScopedPause() collector_-RegisterPause(NanoTime() - start_time_); Runtime:Current()-GetThreadList()-ResumeAll(); 这两个函数定义在文件art/runtime/gc/collector/garbage_collector.cc。 其中，ScopedPause类的构造函数和析构函数还会记录由挂起线程而引发的程序停顿时间。 回到SemiSpace类的成员函数RunPhases，接下来我们就分别分析上述的Semi-Space GC和Generational Semi-Space GC的四个阶段的执行过程。 初始化阶段由SemiSpace类的成员函数InitializePhase来执行，它的实现如下所示：cpp view plain copy 在CODE上查看代码片派生到我的代码片void SemiSpace:InitializePhase() TimingLogger:ScopedTiming t(_FUNCTION_, GetTimings(); mark_stack_ = heap_-GetMarkStack(); DCHECK(mark_stack_ != nullptr); immune_region_.Reset(); is_large_object_space_immune_ = false; saved_bytes_ = 0; bytes_moved_ = 0; objects_moved_ = 0; self_ = Thread:Current(); CHECK(from_space_-CanMoveObjects() Attempting to move from GetLiveBitmap(); / 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(); if (generational_) promo_dest_space_ = GetHeap()-GetPrimaryFreeListSpace(); fallback_space_ = GetHeap()-GetNonMovingSpace(); 这个函数定义在文件art/runtime/gc/collector/semi_space.cc中。 SemiSpace类的成员函数InitializePhase除了初始化一些成员变量之外，最重要的就是获得ART运行时堆的两个Space： 1. Promote Space。如果当前执行的是Generational Semi-Space GC，那么就需要获取Promote Space，这是通过调用Heap类的成员函数GetPrimaryFreeListSpace获得的。前面提到，Promote Space是用来保存那些老生代对象的。 2. Fallback Space。无论当前执行的是Semi-Space GC还是Generational Semi-Space GC，都需要获取这个Space，这是通过Heap类的成员函数GetNonMovingSpace获得的，也就是ART运行时堆的Non Moving Space。Fallback Space的作用是To Space空间已满时，可以将From Space的对象移动到Fallback Space上去。 Heap类的成员函数GetPrimaryFreeListSpace返回来的实际上是ART运行时堆的Main Space，如下所示：cpp view plain copy 在CODE上查看代码片派生到我的代码片class Heap public: . space:MallocSpace* GetPrimaryFreeListSpace() if (kUseRosAlloc) DCHECK(rosalloc_space_ != nullptr); / reinterpret_cast is necessary as the space class hierarchy / isnt known (#included) yet here. return reinterpret_cast(rosalloc_space_); else DCHECK(dlmalloc_space_ != nullptr); return reinterpret_cast(dlmalloc_space_); . ; 这个函数定义在文件art/runtime/gc/heap.h中。 从前面一文可以知道，Heap类的成员变量rosalloc_space_和dlmalloc_space_描述的就是ART运行时堆的Main Space。取决于常量kUseRosAlloc的值。它由Heap类的成员变量rosalloc_space_或者dlmalloc_space_指向。 从前面一文也可以知道，对于Generational Semi-Space GC来说，它的Main Space其实也是Non Moving Space，这意味着Generational Semi-Space GC使用的Promote Space和Fallback Space均为ART运行时堆的Non Moving Space。 标记阶段由SemiSpace类的成员函数MarkingPhase来执行，它的实现如下所示：cpp view plain copy 在CODE上查看代码片派生到我的代码片void SemiSpace:MarkingPhase() . / Revoke the thread local buffers since the GC may allocate into a RosAllocSpace and this helps / to prevent fragmentation. RevokeAllThreadLocalBuffers(); if (generational_) if (GetCurrentIteration()-GetGcCause() = kGcCauseExplicit | GetCurrentIteration()-GetGcCause() = kGcCauseForNativeAlloc | GetCurrentIteration()-GetClearSoftReferences() / If an explicit, native allocation-triggered, or last attempt / collection, collect the whole heap. collect_from_space_only_ = false; . if (!collect_from_space_only_) / If non-generational, always clear soft references. / If generational, clear soft references if a whole heap collection. GetCurrentIteration()-SetClearSoftReferences(true); Locks:mutator_lock_-AssertExclusiveHeld(self_); if (generational_) / If last_gc_to_space_end_ is out of the bounds of the from-space / (the to-space from last GC), then point it to the beginning of / the from-space. For example, the very first GC or the / pre-zygote compaction. if (!from_space_-HasAddress(reinterpret_cast(last_gc_to_space_end_) last_gc_to_space_end_ = from_space_-Begin(); / Reset this before the marking starts below. bytes_promoted_ = 0; / Assume the cleared space is already empty. BindBitmaps(); / Process dirty cards and add dirty cards to mod-union tables. heap_-ProcessCards(GetTimings(), kUseRememberedSet & generational_); . 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) . heap_-RevokeAllThreadLocalAllocationStacks(self_); heap_-SwapStacks(self_); WriterMutexLock mu(self_, *Locks:heap_bitmap_lock_); MarkRoots(); / 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(); / Record freed memory. const int64_t from_bytes = from_space_-GetBytesAllocated(); const int64_t to_bytes = bytes_moved_; const uint64_t from_objects = from_space_-GetObjectsAllocated(); const uint64_t to_objects = objects_moved_; . / Note: Freed bytes can be negative if we copy form a compacted space to a free-list backed / space. RecordFree(ObjectBytePair(from_objects - to_objects, from_bytes - to_bytes); / Clear and protect the from space. from_space_-Clear(); . from_space_-GetMemMap()-Protect(kProtectFromSpace ? PROT_NONE : PROT_READ); . if (swap_semi_spaces_) heap_-SwapSemiSpaces(); 这个函数定义在文件art/runtime/gc/collector/semi_space.cc中。 SemiSpace类的成员函数MarkingPhase的执行过程如下所示： 1. 调用SemiSpace类的成员函数RevokeAllThreadLocalBuffers回收各个ART运行时线程的局部分配缓冲区。从前面这篇文章可以知道，ART运行时线程的局部分配缓冲区是来自Bump Pointer Space或者Ros Alloc Space的。由于现在要对Bump Pointer Space进行GC处理了，因此就需要把它作为ART运行时线程局部分配缓冲区的那部内存回收回来。避免GC处理完毕后，ART运行时线程的局部分配缓冲区引用到不正确内存。 2. Generational Semi-Space GC在执行时，默认只对From Space进行处理，即当SemiSpace类的成员变量generational_与collect_from_space_only_的值是相同的。但是如果当前的Generational S