ART运行时垃圾收集过程分析.doc

ART运行时垃圾收集（GC）过程分析ART运行时与Dalvik虚拟机一样，都使用了Mark-Sweep算法进行垃圾回收，因此它们的垃圾回收流程在总体上是一致的。但是ART运行时对堆的划分更加细致，因而在此基础上实现了更多样的回收策略。不同的策略有不同的回收力度，力度越大的回收策略，每次回收的内存就越多，并且它们都有各自的使用情景。这样就可以使得每次执行GC时，可以最大限度地减少应用程序停顿。本文就详细分析ART运行时的垃圾收集过程。ART运行时的垃圾收集收集过程如图1所示：图1的最上面三个箭头描述触发GC的三种情况，左边的流程图描述非并行GC的执行过程，右边的流程图描述并行GC的执行流程，接下来我们就详细图中涉及到的所有细节。 在前面一文中，我们提到了两种可能会触发GC的情况。第一种情况是没有足够内存分配请求的分存时，会调用Heap类的成员函数CollectGarbageInternal触发一个原因为kGcCauseForAlloc的GC。第二种情况下分配出请求的内存之后，堆剩下的内存超过一定的阀值，就会调用Heap类的成员函数RequestConcurrentGC请求执行一个并行GC。 Heap类的成员函数RequestConcurrentGC的实现如下所示：cpp view plain copy 在CODE上查看代码片派生到我的代码片void Heap:RequestConcurrentGC(Thread* self) / Make sure that we can do a concurrent GC. Runtime* runtime = Runtime:Current(); DCHECK(concurrent_gc_); if (runtime = NULL | !runtime-IsFinishedStarting() | !runtime-IsConcurrentGcEnabled() return; MutexLock mu(self, *Locks:runtime_shutdown_lock_); if (runtime-IsShuttingDown() return; if (self-IsHandlingStackOverflow() return; / We already have a request pending, no reason to start more until we update / concurrent_start_bytes_. concurrent_start_bytes_ = std:numeric_limits:max(); JNIEnv* env = self-GetJniEnv(); DCHECK(WellKnownClasses:java_lang_Daemons != NULL); DCHECK(WellKnownClasses:java_lang_Daemons_requestGC != NULL); env-CallStaticVoidMethod(WellKnownClasses:java_lang_Daemons, WellKnownClasses:java_lang_Daemons_requestGC); CHECK(!env-ExceptionCheck(); 这个函数定义在文件art/runtime/gc/heap.cc。 只有满足以下四个条件，Heap类的成员函数RequestConcurrentGC才会触发一个并行GC： 1. ART运行时已经启动完毕。 2. ART运行时支持并行GC。ART运行时默认是支持并行GC的，但是可以通过启动选项-Xgc来关闭。 3. ART运行时不是正在关闭。 4. 当前线程没有发生栈溢出。 上述4个条件都满足之后，Heap类的成员函数RequestConcurrentGC就将成员变量concurrent_start_bytes_的值设置为类型size_t的最大值，表示目前正有一个并行GC在等待执行，以阻止触发另外一个并行GC。 最后，Heap类的成员函数RequestConcurrentGC调用Java层的java.lang.Daemons类的静态成员函数requestGC请求执行一次并行GC。Java层的java.lang.Daemons类在加载的时候，会启动五个与堆或者GC相关的守护线程，如下所示：java view plain copy 在CODE上查看代码片派生到我的代码片public final class Daemons . public static void start() ReferenceQueueDaemon.INSTANCE.start(); FinalizerDaemon.INSTANCE.start(); FinalizerWatchdogDaemon.INSTANCE.start(); HeapTrimmerDaemon.INSTANCE.start(); GCDaemon.INSTANCE.start(); . 这个类定义在文件libcore/libart/src/main/java/java/lang/Daemons.java中。 这五个守护线程分别是： 1. ReferenceQueueDaemon：引用队列守护线程。我们知道，在创建引用对象的时候，可以关联一个队列。当被引用对象引用的对象被GC回收的时候，被引用对象就会被加入到其创建时关联的队列去。这个加入队列的操作就是由ReferenceQueueDaemon守护线程来完成的。这样应用程序就可以知道那些被引用对象引用的对象已经被回收了。 2. FinalizerDaemon：析构守护线程。对于重写了成员函数finalize的对象，它们被GC决定回收时，并没有马上被回收，而是被放入到一个队列中，等待FinalizerDaemon守护线程去调用它们的成员函数finalize，然后再被回收。 3. FinalizerWatchdogDaemon：析构监护守护线程。用来监控FinalizerDaemon线程的执行。一旦检测那些重定了成员函数finalize的对象在执行成员函数finalize时超出一定的时候，那么就会退出VM。 4. HeapTrimmerDaemon：堆裁剪守护线程。用来执行裁剪堆的操作，也就是用来将那些空闲的堆内存归还给系统。 5. GCDaemon：并行GC线程。用来执行并行GC。 Java层的java.lang.Daemons类的静态成员函数requestGC被调用时，就会唤醒上述的并行GC线程，然后这个并行GC线程就会通过JNI调用Heap类的成员函数ConcurrentGC，它的实现如下所示：cpp view plain copy 在CODE上查看代码片派生到我的代码片void Heap:ConcurrentGC(Thread* self) MutexLock mu(self, *Locks:runtime_shutdown_lock_); if (Runtime:Current()-IsShuttingDown() return; / Wait for any GCs currently running to finish. if (WaitForConcurrentGcToComplete(self) = collector:kGcTypeNone) CollectGarbageInternal(next_gc_type_, kGcCauseBackground, false); 这个函数定义在文件art/runtime/gc/heap.cc中。 只要ART运行时当前不是处于正在关闭的状态，那么Heap类的成员函数ConcurrentGC就会检查当前是否正在执行GC。如果是的话，那么就等待它执行完成，然后再调用Heap类的成员函数CollectGarbageInternal触发一个原因为kGcCauseBackground的GC。否则的话，就直接调用Heap类的成员函数CollectGarbageInternal触发一个原因为kGcCauseBackground的GC。 从这里就可以看到，无论是触发GC的原因是kGcCauseForAlloc，还是kGcCauseBackground，最终都是通过调用Heap类的成员函数CollectGarbageInternal来执行GC的。此外，还有第三种情况会触发GC，如下所示：cpp view plain copy 在CODE上查看代码片派生到我的代码片void Heap:CollectGarbage(bool clear_soft_references) / Even if we waited for a GC we still need to do another GC since weaks allocated during the / last GC will not have necessarily been cleared. Thread* self = Thread:Current(); WaitForConcurrentGcToComplete(self); CollectGarbageInternal(collector:kGcTypeFull, kGcCauseExplicit, clear_soft_references); 这个函数定义在文件art/runtime/gc/heap.cc。 当我们调用Java层的java.lang.System的静态成员函数gc时，如果ART运行时支持显式GC，那么就它就会通过JNI调用Heap类的成员函数CollectGarbageInternal来触发一个原因为kGcCauseExplicit的GC。ART运行时默认是支持显式GC的，但是可以通过启动选项-XX:+DisableExplicitGC来关闭。 从上面的分析就可以看出，ART运行时在三种情况下会触发GC，这三种情况通过三个枚举kGcCauseForAlloc、kGcCauseBackground和kGcCauseExplicitk来描述。这三人枚举的定义如下所示：cpp view plain copy 在CODE上查看代码片派生到我的代码片/ What caused the GC? enum GcCause / GC triggered by a failed allocation. Thread doing allocation is blocked waiting for GC before / retrying allocation. kGcCauseForAlloc, / A background GC trying to ensure there is free memory ahead of allocations. kGcCauseBackground, / An explicit System.gc() call. kGcCauseExplicit, ; 这三个枚举定义在文件art/runtime/gc/heap.h中。 从上面的分析还可以看出，ART运行时的所有GC都是以Heap类的成员函数CollectGarbageInternal为入口，它的实现如下所示：cpp view plain copy 在CODE上查看代码片派生到我的代码片collector:GcType Heap:CollectGarbageInternal(collector:GcType gc_type, GcCause gc_cause, bool clear_soft_references) Thread* self = Thread:Current(); . / Ensure there is only one GC at a time. bool start_collect = false; while (!start_collect) MutexLock mu(self, *gc_complete_lock_); if (!is_gc_running_) is_gc_running_ = true; start_collect = true; if (!start_collect) / TODO: timinglog this. WaitForConcurrentGcToComplete(self); . . if (gc_type = collector:kGcTypeSticky & alloc_space_-Size() IsConcurrent() = concurrent_gc_ & cur_collector-GetGcType() = gc_type) collector = cur_collector; break; . collector-clear_soft_references_ = clear_soft_references; collector-Run(); . MutexLock mu(self, *gc_complete_lock_); is_gc_running_ = false; last_gc_type_ = gc_type; / Wake anyone who may have been waiting for the GC to complete. gc_complete_cond_-Broadcast(self); . return gc_type; 这个函数定义在文件art/runtime/gc/heap.cc。 参数gc_type和gc_cause分别用来描述要执行的GC的类型和原因，而参数clear_soft_references用来描述是否要回收被软引用对象引用的对象。 Heap类的成员函数CollectGarbageInternal的执行逻辑如下所示： 1. 通过一个while循环不断地检查Heap类的成员变量is_gc_running_，直到它的值等于false为止，这表示当前没有其它线程正在执行GC。当它的值等于true时，就表示在其它线程正在执行GC，这时候就要调用Heap类的成员函数WaitForConcurrentGcToComplete等待其执行完成。注意，在当前GC执行之前，Heap类的成员变量is_gc_running_会被设置为true。 2. 如果当前请求执行的GC的类型为kGcTypeSticky，但是当前Allocation Space的大小小于Heap类的成员变量min_alloc_space_size_for_sticky_gc_指定的阀值，那么就改为执行类型为kGcTypePartial。关于类型为kGcTypeSticky的GC的执行限制，可以参数前面一文。 3. 从Heap类的成员变量mark_sweep_collectors_指向的一个垃圾收集器列表找到一个合适的垃圾收集器来执行GC。从前面一文可以知道，ART运行时在内部创建了六个垃圾收集器。这六个垃圾收集器分为两组，一组支持并行GC，另一组不支持。每一组都是由三个类型分别为kGcTypeSticky、kGcTypePartial和kGcTypeFull的垃垃圾收集器组成。这里说的合适的垃圾收集器，是指并行性与Heap类的成员变量concurrent_gc_一致，并且类型也与参数gc_type一致的垃圾收集器。 4. 找到合适的垃圾收集器之后，就将参数clear_soft_references的值保存它的成员变量clear_soft_references_中，以便可以告诉它要不要回收被软引用对象引用的对象，然后再调用它的成员函数Run来执行GC。 5. GC执行完毕，将Heap类的成员变量is_gc_running_设置为false，以表示当前GC已经执行完毕，下一次请求的GC可以执行了。此外，也会将Heap类的成员变量last_gc_type_设置为当前执行的GC的类型。这样下一次执行GC时，就可以执行另外一个不同类型的GC。例如，如果上一次执行的GC的类型为kGcTypeSticky，那么接下来的两次GC的类型就可以设置为kGcTypePartial和kGcTypeFull，这样可以使得每次都能执行有效的GC。 6. 通过Heap类的成员变量gc_complete_cond_唤醒那些正在等待GC执行完成的线程。 在上面的六个步骤中，最重要的就是第四步了。从前面一文可以知道，所有的垃圾收集器都是从GarbageCollector类继承下来的，因此上面的第四步实际上执行的是GarbageCollector类的成员函数Run，它的实现如下所示：cpp view plain copy 在CODE上查看代码片派生到我的代码片void GarbageCollector:Run() ThreadList* thread_list = Runtime:Current()-GetThreadList(); uint64_t start_time = NanoTime(); pause_times_.clear(); duration_ns_ = 0; InitializePhase(); if (!IsConcurrent() / Pause is the entire length of the GC. uint64_t pause_start = NanoTime(); ATRACE_BEGIN(Application threads suspended); thread_list-SuspendAll(); MarkingPhase(); ReclaimPhase(); thread_list-ResumeAll(); ATRACE_END(); uint64_t pause_end = NanoTime(); pause_times_.push_back(pause_end - pause_start); else Thread* self = Thread:Current(); ReaderMutexLock mu(self, *Locks:mutator_lock_); MarkingPhase(); bool done = false; while (!done) uint64_t pause_start = NanoTime(); ATRACE_BEGIN(Suspending mutator threads); thread_list-SuspendAll(); ATRACE_END(); ATRACE_BEGIN(All mutator threads suspended); done = HandleDirtyObjectsPhase(); ATRACE_END(); uint64_t pause_end = NanoTime(); ATRACE_BEGIN(Resuming mutator threads); thread_list-ResumeAll(); ATRACE_END(); pause_times_.push_back(pause_end - pause_start); ReaderMutexLock mu(self, *Locks:mutator_lock_); ReclaimPhase(); uint64_t end_time = NanoTime(); duration_ns_ = end_time - start_time; FinishPhase(); 这个函数定义在文件art/runtime/gc/collector/garbage_collector.cc中。 GarbageCollector类的成员函数Run的实现就对应于图1所示的左边和右边的两个流程。 图1所示的左边流程是用来执行非并行GC的，过程如下所示： 1. 调用子类实现的成员函数InitializePhase执行GC初始化阶段。 2. 挂起所有的ART运行时线程。 3. 调用子类实现的成员函数MarkingPhase执行GC标记阶段。 4. 调用子类实现的成员函数ReclaimPhase执行GC回收阶段。 5. 恢复第2步挂起的ART运行时线程。 6. 调用子类实现的成员函数FinishPhase执行GC结束阶段。 图1所示的右边流程是用来执行并行GC的，过程如下所示： 1. 调用子类实现的成员函数InitializePhase执行GC初始化阶段。 2. 获取用于访问Java堆的锁。 3. 调用子类实现的成员函数MarkingPhase执行GC并行标记阶段。 4. 释放用于访问Java堆的锁。 5. 挂起所有的ART运行时线程。 6. 调用子类实现的成员函数HandleDirtyObjectsPhase处理在GC并行标记阶段被修改的对象。 7. 恢复第4步挂起的ART运行时线程。 8. 重复第5到第7步，直到所有在GC并行阶段被修改的对象都处理完成。 9. 获取用于访问Java堆的锁。 10. 调用子类实现的成员函数ReclaimPhase执行GC回收阶段。 11. 释放用于访问Java堆的锁。 12. 调用子类实现的成员函数FinishPhase执行GC结束阶段。 从上面的分析就可以看出，并行GC和非并行GC的区别在于： 1. 非并行GC的标记阶段和回收阶段是在挂住所有的ART运行时线程的前提下进行的，因此，只需要执行一次标记即可。 2. 并行GC的标记阶段只锁住了Java堆，因此它不能阻止那些不是正在分配对象的ART运行时线程同时运行，而这些同进运行的ART运行时线程可能会引用了一些在之前的标记阶段没有被标记的对象。如果不对这些对象进行重新标记的话，那么就会导致它们被GC回收，造成错误。因此，与非并行GC相比，并行GC多了一个处理脏对象的阶段。所谓的脏对象就是我们前面说的在GC标记阶段同时运行的ART运行时线程访问或者修改过的对象。 3. 并行GC并不是自始至终都是并行的，例如，处理脏对象的阶段就是需要挂起除GC线程以外的其它ART运行时线程，这样才可以保证标记阶段可以结束。 从前面一文可以知道，GarbageCollector类有三个直接或者间接的子类MarkSweep、PartialMarkSweep和StickyMarkSweep都可以用来执行垃圾回收，其中，PartialMarkSweep类又是从MarkSweep类直接继承下来的，而StickyMarkSweep类是从PartialMarkSweep类直接继承下来的。MarkSweep类用来回收Zygote Space和Allocation Space的垃圾，PartialMarkSweep类用来回收Allocation Space的垃圾，StickyMarkSweep类用来回收上次GC以来在Allcation Space上分配的最终又没有被引用的垃圾。 接下来，我们就主要分析ART运行时线程的挂起和恢复过程，以及MarkSweep、PartialMarkSweep和StickyMarkSweep这三个类是执行InitializePhase、MarkingPhase、HandleDirtyObjectsPhase、ReclaimPhase和FinishPhase的五个GC阶段的过程。 1. ART运行时线程的挂起 从上面的分析可以知道，ART运行时线程的挂起是通过调用ThreadList类的成员函数SuspendAll实现的，如下所示：cpp view plain copy 在CODE上查看代码片派生到我的代码片void ThreadList:SuspendAll() Thread* self = Thread:Current(); . MutexLock mu(self, *Locks:thread_list_lock_); MutexLock mu2(self, *Locks:thread_suspend_count_lock_); / Update global suspend all state for attaching threads. +suspend_all_count_; / Increment everybodys suspend count (except our own). for (const auto& thread : list_) if (thread = self) continue; . thread-ModifySuspendCount(self, +1, false); / Block on the mutator lock until all Runnable threads release their share of access. #if HAVE_TIMED_RWLOCK / Timeout if we wait more than 30 seconds. if (UNLIKELY(!Locks:mutator_lock_-ExclusiveLockWithTimeout(self, 30 * 1000, 0) UnsafeLogFatalForThreadSuspendAllTimeout(self); #else Locks:mutator_lock_-ExclusiveLock(self); #endif . 这个函数定义在文件art/runtime/thread_list.cc中。 所有的ART运行时线程都保存在ThreadList类的成员变量list_描述的一个列表，遍历这个列表时，需要获取Lock类的成员变量thread_list_lock_描述的一个互斥锁。 ThreadList类有一个成员变量suspend_all_count_，用来描述全局的线程挂起计数器。在所有的ART运行时线程挂起期间，如果有新的线程将自己注册为ART运行时线程，那么它也会将自己挂起来，而判断所有的ART运行时线程是不是处于挂起期间，就是通过ThreadList类的成员变量suspend_all_count_的值是否大于0进行的。因此，ThreadList类的成员函数SuspendAll在挂起所有的ART运行时线程之前，会将ThreadList类的成员变量suspend_all_count_的值增加1。 接下来，ThreadList类的成员函数SuspendAll遍历所有的ART运行时线程，并且调用Thread类的成员函数ModifySuspendCount将它内部的线程计算数器增加1，如下所示：cpp view plain copy 在CODE上查看代码片派生到我的代码片void Thread:AtomicSetFlag(ThreadFlag flag) android_atomic_or(flag, &state_and_flags_.as_int); void Thread:AtomicClearFlag(ThreadFlag flag) android_atomic_and(-1 flag, &state_and_flags_.as_int); . void Thread:ModifySuspendCount(Thread* self, int delta, bool for_debugger) . suspend_count_ += delta; . if (suspend_count_ = 0) AtomicClearFlag(kSuspendRequest); else AtomicSetFlag(kSuspendRequest); 这三个函数定义在文件art/runtime/thread.cc中。 Thread类的成员函数ModifySuspendCount的实现很简单，它主要就是将成员变量suspend_count_的值增加delta，并且判断增加后的值是否等于0。如果等于0，就调用成员函数AtomicClearFlag将另外一个成员变量state_and_flags_的int值的kSuspendRequest位清0，表示线程没有挂起请求。否则的话，就调用成员函数AtomicSetFlag将成员变量state_and_flags_的int值的kSuspendRequest位置1，表示线程有挂起请求。 回到前面ThreadList类的成员函数SuspendAll中，全局ART运行时线程挂起计数器和每一个ART运行时线程内部的线程挂起计数器的操作都是需要在获取Locks类的静态成员变量thread_suspend_count_lock_描述的一个互斥锁的前提下进行的。 最后，ThreadList类的成员函数SuspendAll通过获取Locks类的静态成员变量mutator_lock_描述的一个读写锁的写访问来等待所有的ART运行时线程挂起的。这是如何做到的呢？在前面一文中，我们提到，ART运行时提供给由DEX字节码翻译而来的本地机器代码使用的一个函数表中，包含了一个pCheckSuspend函数指针，该函数指针指向了函数CheckSuspendFromCode。于是，每一个ART运行时线程在执行本地机器代码的过程中，就会周期性地通过调用函数CheckSuspendFromCode来检查自己是否需要挂起。这一点与前面一文分析的Dalvik虚拟机线程挂起的过程是类似的。 函数CheckSuspendFromCode的实现如下所示：cpp view plain copy 在CODE上查看代码片派生到我的代码片void CheckSuspendFromCode(Thread* thread) SHARED_LOCKS_REQUIRED(Locks:mutator_lock_) . CheckSuspend(thread); 这个函数定义在文件art/runtime/entrypoints/quick/quick_thread_entrypoints.cc中。 函数CheckSuspendFromCode调用另外一个函数CheckSuspend检查当前线程是否需要挂起，后者的实现如下所示：cpp view plain copy 在CODE上查看代码片派生到我的代码片static inline void CheckSuspend(Thread* thread) SHARED_LOCKS_REQUIRED(Locks:mutator_lock_) for (;) if (thread-ReadFlag(kCheckpointRequest) thread-RunCheckpointFunction(); thread-AtomicClearFlag(kCheckpointRequest); else if (thread-ReadFlag(kSuspendRequest) thread-FullSuspendCheck(); else break; 这个函数定义在文件art/runtime/entrypoints/entrypoint_utils.h中。 从上面的分析可以知道，如果当前线程的线程挂起计数器不等于0，那么它内部的一个标记位kSuspendRequest被设置为1。这时候函数CheckSuspend就会调用Thread类的成员函数FullSuspendCheck来将自己挂起。此外，函数CheckSuspend还会检查线程内部的另外一个标记位kCheckpointRequest是否被设置为1。如果被设置为1的话，那么就说明线程有一个Check Point需要执行，这时候就会先调用Thread类的成员函数RunCheckpointFunction运行该Check Point，接着再将线程内部的标记位kCheckpointRequest清0。关于线程的Check Point，我们后面再分析。 Thread类的成员函数FullSuspendCheck的实现如下所示：cpp view plain copy 在CODE上查看代码片派生到我的代码片void Thread:FullSuspendCheck() . / Make thread appear suspended to other threads, release mutator_lock_. TransitionFromRunnableToSuspended(kSuspended); / Transition back to runnable noting requests to suspend, re-acquire share on mutator_lock_. TransitionFromSuspendedToRunnable(); . 这个函数定义在文件art/runtime/thread.cc中。 Thread类的成员函数FullSuspendCheck首先是调用成员函数TransitionFromRunnableToSuspended将自己从运行状态修改为挂起状态，接着再调用成员函数TransitionFromSuspendedToRunnable将自己从挂起状态修改为运行状态。通过Thread类的这两个神奇的成员函数，就实现了将当前线程挂起的功能。接下来我们就继续分析它们是怎么实现的。 Thread类的成员函数TransitionFromRunnableToSuspended的实现如下所示：cpp view plain copy 在CODE上查看代码片派生到我的代码片inline void Thread:TransitionFromRunnableToSuspended(ThreadState new_state) . union StateAndFlags old_state_and_flags; union StateAndFlags new_state_and_flags; do old_state_and_flags = state_and_flags_; / Copy over flags and try to clear the checkpoint bit if it is set. new_state_and_flags.as_struct.flags = old_state_and_flags.as_struct.flags & kCheckpointRequest; new_state_and_flags.as_struct.state = new_state; / CAS the value without a memory barrier, that will occur in the unlock below. while (UNLIKELY(android_atomic_cas(old_state_and_flags.as_int, new_state_and_flags.as_int, &state_and_flags_.as_int) != 0); / If we toggled the checkpoint flag we must have cleared it. uint16_t flag_change = new_state_and_flags.as_struct.flags old_state_and_flags.as_struct.fla