Understanding Garbage Collector in ART of Android

大纲

• 前言
• Mark-Sweep Collector
• Mark Stage
• Sweep Stage
• Finish Stage
• Semi-Space Collector

前言

ART目前采取了垃圾追踪的回收策略，即若某个对象没有被引用，则被认为是可以回收的垃圾，释放垃圾占用的内存。ART实现了两种垃圾回收技术，一种是Mark-Sweep, 另一种是Semi-Space.

Mark-Sweep：它的大致思想是，将所有的对象在内存中的位置记录在位图A中。然后，从所有对象的根出发，扫描根对象的所有引用，扫描根对象的所有引用的引用，一层层逐级扫描，直到叶子节点的对象。在这个逐级扫描的过程中，将涉及到的对象的位置都记录在位图B中。扫描结束后，对比两张位图A和B：所有A中置位的位置，却没有B中被置位，被视为垃圾。并根据位图中的索引检索得到对象，然后释放该对象占用的内存。

Semi-Space： 它的特色是，有两个space空间，其中一个备用。另一个被系统拿来分配对象。在做垃圾扫描的时候，将所有在空间A中被有效引用的对象移动到空间B中。那么在空间A中剩余的对象就是垃圾了，直接释放垃圾对象所在的整个空间就可以了。这个回收速度很快。

Mark-Sweep Collector

要了解Android的垃圾回收策略，需要首先弄清楚对于每一个Android的Heap，有哪些Space.对于普通的Android VM进程来说，其Heap都是从Zygote继承过来。所以，每一个VM 进程Heap的虚拟地址区间基本上都是一样的（区间的末端范围会有些不同）。对于一个普通的VM进程Heap的区间一般是这样划分的。

图1.  Heap中的空间

Image Space的容量取决于boot.art和boot.oat的容量大小（具体可以到/data/dalvik-cache/下查看这两个文件的大小）。在Image Space后面紧接着的就是Zygote Space。顾名思义，由于Zygote是所有VM进程的祖先，因此在普通的VM进程孵化出之前，Zygote是需要一些object的，这些object都被压缩放在Zygote Space中（为什么是压缩，后面讲Semi-Space时会有涉及）。紧挨着Zygote Space的是Main Space, Main Space的limit被设置为了176MB. 其实从Zygote Space的起始到Non Moving Space的结束位置是有512MB大小的。

Mark-Sweep Collector只针对Heap中的Zygote Space、Main Space和Non Moving Space做垃圾回收处理. Temp Space和Bump pointer Space的垃圾回收归属于Semi-Space Collector来处理。

Mark-Sweep Collector根据轻重程度不同，可以分为三类：Sticky, Partial, Full. 又根据做GC的过程中是否暂停所有的mutator线程分为ConCurrent和Non-Concurrent. 所以，ART系统一共定义了6中MS的垃圾回收器。即，

333   // Create our garbage collectors.

334   for (size_t i = 0; i < 2; ++i) {

335     const bool concurrent = i != 0;

336     garbage_collectors_.push_back(new collector::MarkSweep(this, concurrent));

337     garbage_collectors_.push_back(new collector::PartialMarkSweep(this, concurrent));

338     garbage_collectors_.push_back(new collector::StickyMarkSweep(this, concurrent));

339   }

根据情况的不同，系统选择不同的垃圾回收器进行垃圾回收工作。当然，对系统的工作线程影响最小的应该是Concurrent Sticky Mark Sweep Collector了。影响最大的就是Full Mark Sweep Collector。而最复杂的属于Concurrent Mark Sweep Collector。如果理解了最繁琐的Concurrent Mark Sweep（下文成为CMS）算法，其他5中垃圾回收器的工作原理就也理解了。CMS工作从整体上可以划分两个大的阶段：Mark 和 Sweep。

1） Mark阶段

做标记工作，即从根对象出发，递归广度优先标记所有引用的对象。一个被引用的对象在标记的过程中，先被标记，然后放在栈中，等该对象的父对象全部被标记完成后，依次弹出栈中的每一个对象，并标记其引用，然后把其引用再丢到栈中…。在整个Mark的过程中，把处于不同状态的对象可以形象的用颜色：黑、灰、白来描述。未进行标记前，所有的对象都是白色的，那些进过栈并出栈的对象又被称之为被标记过的对象称之为黑色的，而在栈中的对象被称之为灰色的。当Mark阶段完成后，所有的对象要不是黑色的，要不是白色的。白色的就是可以被回收的垃圾了。

Mark是从所有对象的根出发，这些根会有很多，最简单的根比如在当前函数栈里面的对象对其他对象的引用。由于是Concurrent，因此Mark的线程是和当前进程中的工作mutator线程^[1]一起工作的，因此在Mark的过程中，mutator线程也会新分配对象或者修改对象的引用。因此，必须有一个阶段是需要Stop-The-World，暂停所有的mutator线程，以方便GC进行mark操作。如果整个Mark阶段都Stop-The-World，显然对mutator工作线程的影响太大了。ART的做法是，先Concurrent标记两遍，然后再Non-Concurrent标记一遍。两遍的原因是尽可能多的把需要标记的对象都在不暂停mutator的情况下标记了。具体的标记过程和代码罗列如下：

1.1   Initialize Phase

118 void MarkSweep::InitializePhase() {

…

121   mark_stack_ = heap_->mark_stack_.get();

…

123   immune_region_.Reset();

140 }

在初始预备阶段，为后面的mark准备好mark_stack_和immune_region.

1.1.1  Mark_stack_是做什么呢？mark_stack_是一个FIFO的栈。由于标记是按照深度优先递归标记的，mark_stack_栈来进行配合进行深度递归。理论上，递归是不需要辅助栈的，利用函数本身的栈就可以实现深度递归。但是，采用了mark_stack_栈的好处是：1. 可以并行多线程来做，当mark_stack_栈中数量达到一定数目的时候（128个）就可以用多线程，将栈进行分段，多个线程共同将栈中的数据递归标记。2. 另外一个显而易见的好处是，可以避免函数栈的深度过深。

例如根据上图，假设在栈中存在B,C。

a). 弹出C，标记C的引用F并压入F，标记G压入G。然后弹出G

b). G没有其他的引用，弹出F，F没有其他的引用。弹出B

c). 标记B的引用D，压入D. 标记B的引用E，压入E。弹出E

d). E没有任何引用。弹出D，D没有任何引用。栈空。结束。

1.1.2  immune_region是做什么的？

在一个Heap中有几个Space区，这些space的用途是不一样的，比如Image Space, 其中放的是boot.art和boot.oat的代码段数据段。对于Image Space，其中的数据是不经常更改的，因此，GC是不会完整地扫描该区域。还有Zygote Space, 该区放的是Zygote在Fork该进程之前的Zygote内容，因此也是不经常改变的。根据当前系统的内存短缺情况，采取不同程度的GC扫描策略，于是凡将某个space指定给immune_region的，GC便不会去扫描。可是，不扫描的话，如果该Space中有object的引用修改了，怎么办呢，比如Image Space有个对象A本来引用了B，但后来更改，A引用C了，于是在GC的时候，需要把B当作垃圾，而C被Mark。这就需要额外的数据结构ModUnionTable以及CardTable了。

1.1.3  ModUnionTable与CardTable

ModUnionTable是需要和CardTable配合使用的。CardTable可以看作是一个数组，每一项被称作Card，占用一个字节的空间。代表Heap中连续的128个字节的内存是否有更改。第0个字节（0号索引）对应Heap起始的128个字节，第1个字节（1号索引）对应Heap中后续的128个字节，以此类推。因此CardTable要覆盖这个Heap的所有连续Space区间(包括Bumper Space)。CardTable中的Card可以有3个值，分别是0, 0x70,0x6F. 非0代表该项对应的Heap中相应的object有更改。

在做GC的Mark时，凡是CardTable中属于immune_region的值为0x70的Card, 被记录到ModUnionTable 中有一个类似于set的c++数据结构中，同时将该Card的值减去1，即0x6F。

1.1.4  RememberedSet与CardTable

RememberedSet与ModUnionTable的作用是一样的，不同的是ModUnionTable记录Image Space, Zygote Space对其他space的引用的修改。而RememberedSet记录的是Non Moving Space和Main Space对Semi Space引用的修改。RememberedSet虽然只在Semi-Space Collector中起作用，但在CMS的ProcessCards中也会对CardTable中属于Non Moving Space和Main Space的Dirty Card 在RememberedSet中做备份。

1.1.5  Live_Bitmap和Mark_Bitmap

如前所述，Mark Sweep垃圾回收策略采取的是标记跟踪法。Live_Bitmap和Mark_Bitmap便是用来做标记的。他们都是位图的数据结构，每一位代表8个字节的空间。Live_Bitmap记录了当前存在于VM进程中所有的未标记的object和标记过的object。Mark_Bitmap经过了Mark 的过程，记录了当前VM进程中所有被引用的object. Live_Bitmap和Mark_Bitmap中间的差集，便是所有为被系统引用的object，即是可以回收的垃圾了。

1.1.6  allocation_stack和live_stack

所有新分配的object会被allocation_stack来记录，然后在Marking的时候，再在Live_Bitmap中打上live的标记。allocation_stack和live_stack其实是一个工作栈和备份栈。当在GC的时候，需要处理allocation_stack，那么会把两个stack互换。Mutator线程新分配的object会压倒备份栈中（备份栈就当作新的工作栈了）。

1.1.7  Concurrent
系统在什么情况下用concurrent，什么时候不用呢？系统定义了6中垃圾收集器，那么具体在做垃圾回收的时候，选择哪一种垃圾收集器呢？在系统初始化的时候，会定义一个collector_type_，一个collector_type_可以选择为：kCollectorTypeSS/kCollectorTypeGSS/kCollectorTypeMS/kCollectorTypeCMS. 对于前三种，都是NonConcurrent的，只有后一种是Concurrent. 目前系统默认选择的是最后一种kCollectorTypeCMS.于是在做垃圾回收的时候，根据sticky/partial/full，选择Concurrent的mark-sweep的垃圾收集器。

1.2 Marking Phase

1.2.1 在Marking阶段，如果是sticky/partial的CMS, 会把Image Space和Zygote Space都加入到Immune_region中。并且，对于sticky的CMS，还会将Main Space和Non moving Space的mark_bitmap和live_bitmap绑定（绑定的意思是mark_bitmap和live_bitmap指向同样的bitmap,这样做的目的是在mark的时候直接把live_bitmap和mark_bitmap都标记了，就不会对这两个space做垃圾回收处理了）。Sticky CMS是为了处理新分配出来的对象中的垃圾而不会处理其他Space中的垃圾，因此采用了绑定的方法。而Partial Space把Zygote Space放在immune_region的原因是，Partial CMS不会把Zygote Space完整得扫描一遍，只会扫描在card table上有修改的部分。对于Full CMS，只会把Image Space加入到Immune_region中。可以看出无论是哪一种的CMS都会把Image Space加入到Immune_region中，他们都不会完整的扫描Image Space，因为Image Space里面存放的是boot.art和boot.oat，VM进程对其更改的可能性比较小，完整地对这个60+MB的Space扫描一遍性价比太低了。

1.2.2  处理CardTable。扫描CardTable，凡是对应于Image Space和Zygote Space的值为0x70(kCardDirty)的Card都被插入到ModUnionTableCardCache中，并在CardTable中对该Card进行Aged, Aged的做法就是其值为0x70的减去1，非0x70且非0的设置为0；凡是对应于Main Space和Non Moving Space的更改的card，都存储在RememberedSet中。其他非Semi Space在CardTable中有对应的修改的Card, 只进行Aged(好像没有其他的Space了L).

2227 void Heap::ProcessCards(TimingLogger& timings, bool use_rem_sets) {

2228   // Clear cards and keep track of cards cleared in the mod-union table.

2229   for (const auto& space : continuous_spaces_) {

2230     accounting::ModUnionTable* table = FindModUnionTableFromSpace(space);

2231     accounting::RememberedSet* rem_set = FindRememberedSetFromSpace(space);

2232     if (table != nullptr) {

2233       const char* name = space->IsZygoteSpace() ? "ZygoteModUnionClearCards" :

2234           "ImageModUnionClearCards";

2235       TimingLogger::ScopedSplit split(name, &timings);

2236       table->ClearCards();

2237     } else if (use_rem_sets && rem_set != nullptr) {

2238       DCHECK(collector::SemiSpace::kUseRememberedSet && collector_type_ == kCollectorTypeGSS)

2239           << static_cast<int>(collector_type_);

2240       TimingLogger::ScopedSplit split("AllocSpaceRemSetClearCards", &timings);

2241       rem_set->ClearCards();

2242     } else if (space->GetType() != space::kSpaceTypeBumpPointerSpace) {

2243       TimingLogger::ScopedSplit split("AllocSpaceClearCards", &timings);

2244       // No mod union table for the AllocSpace. Age the cards so that the GC knows that these cards

2245       // were dirty before the GC started.

2246       // TODO: Need to use atomic for the case where aged(cleaning thread) -> dirty(other thread)

2247       // -> clean(cleaning thread).

2248       // The races are we either end up with: Aged card, unaged card. Since we have the checkpoint

2249       // roots and then we scan / update mod union tables after. We will always scan either card.

2250       // If we end up with the non aged card, we scan it it in the pause.

2251       card_table_->ModifyCardsAtomic(space->Begin(), space->End(), AgeCardVisitor(), VoidFunctor());

2252     }

2253   }

2254 }

在目前的Heap中，所有的Space在2230～2242行都已经涉及到了，因此2251行似乎很多余。2232行处理的是Image Space和Zygote Space,2237行处理的是Non Moving Space和Main Space. 而card table不包含Large Object Space.

1.2.3  MarkRoots. 从各个入口开始Mark操作（可以看作是每一个入口所引用的对象看作一棵树，这样在ART里面所有的对象组成了一个森林，那些没有挂载在根树上的对象都是被回收的对象）。

1.2.4  MarkReachableObjects. 首先会更新immune_region中的ModUnionTable中记录的dirty Card，对之进行Mark。并压入mark_stack栈中。然后进行RecursiveMark，即递归Mark.

至此，所有在根对象的reference链上的对象都已经标记了，貌似已经可以进行Sweep。可是，不要忘了，之前标记是在ConCurrent的情况下，也就是说由于mutator线程仍然在同步地跑着，他们在GC工作的时候仍然可以allocate新的对象，并修改已经Mark过的对象的引用。例如在之前Mark操作的时候A->B,将A以及B都已经Mark后，mutator线程新分配了对象C，并将A的引用指向C，即A->C。如果对象C不再次被标记，当作垃圾的话，那么下次访问A的引用的时候，就可能造成Segment Fault了。所以，需要在Suspend所有mutator的情况下再进行一遍Mark. 可是，CMS的目的是尽可能的减少mutator线程pause的时间。于是CMS的策略是，再从头再来标记一遍。

1.2.5 PreCleanCards.

(1)首先会重复步骤1.2.2，不过这一次被操作的对象就是在1.2.2～1.2.4的过程中新产生的对象或者被修改的对象引用了。

(2)从各个入口开始Mark操作，在操作的过程中对于遇到的没有在mark_bitmap上mark过的，在mark_bitmap上做Mark标记。

(3)扫描card table中1.2.5刚开始时aged过的card以及在这个过程中dirty的card对应的对象都进行mark操作（即在mark_bitmap上标记，同时丢到mark_stack中）（233行和922行）

(4)递归处理mark_stack中的object并递归处理object的引用。（923行）

233     RecursiveMarkDirtyObjects(false, accounting::CardTable::kCardDirty - 1);

921 void MarkSweep::RecursiveMarkDirtyObjects(bool paused, byte minimum_age) {

922   ScanGrayObjects(paused, minimum_age);

923   ProcessMarkStack(paused);

924 }

1.2.6 前面在ConCurrent的情况下，经过了两轮的扫描，基本上已经扫描的差不多了。但由于mutator是在一直运行的，不可避免地会修改我们之前已经mark过的"地图"。因此，需要第三遍扫描，在Stop-The-World的情况下进行扫描。

62   void PausePhase() EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_);

这次扫描的时候，除了remarkroot外，还需要扫描cardtable中Dirty Card的部分.

185     RecursiveMarkDirtyObjects(true, accounting::CardTable::kCardDirty);

1.2.7 经过了前面3次扫描以及Mark，我们的mark"地图"已经完备了。可是，我们需要注意，由于Sweep的操作是对应于live_bitmap，在live_bitmap中标记过，却在mark_bitmap中没有标记的视为垃圾。换句话说，mark_bitmap中标记的对象是live_bitmap中标记对象的子集。但目前为止live_bitmap标记的对象还不全，因为allocation_stack中的对象，我们还没有来得及在live_bitmap中做mark. 因此，allocation_stack先"搁置"起来不让后面的mutator使用，启用备份的的live_stack.

2185 void Heap::SwapStacks(Thread* self) {

2186   if (kUseThreadLocalAllocationStack) {

2187     live_stack_->AssertAllZero();

2188   }

2189   allocation_stack_.swap(live_stack_);

2190 }

2） Sweep阶段

Sweep阶段就是把那些白色的对象所占用的内存回收掉。下面这个代码片段基本上就把Sweep的事情说清楚了。

155   for (size_t i = start; i <= end; i++) {

156     word garbage = live[i] & ~mark[i];

157     if (UNLIKELY(garbage != 0)) {

158       uintptr_t ptr_base = IndexToOffset(i) + live_bitmap.heap_begin_;

159       do {

160         const size_t shift = CLZ(garbage);

161         garbage ^= static_cast<size_t>(kWordHighBitMask) >> shift;

162         *pb++ = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);

163       } while (garbage != 0);

164       // Make sure that there are always enough slots available for an

165       // entire word of one bits.

166       if (pb >= &pointer_buf[buffer_size - kBitsPerWord]) {

167         (*callback)(pb - &pointer_buf[0], &pointer_buf[0], arg);

168         pb = &pointer_buf[0];

169       }

170     }

171   }

156行把live_bitmap中置位的，却没有在mark_bitmap中置位的对象当作垃圾。157～170行就是把垃圾占用的空间给释放掉。

3） Finish 阶段

在1.2.1的时候，说过，有些情况下会bind mark_bitmap to live_bitmap，这样不会回收某个space的垃圾。因此在这个阶段需要unbind。

1541 void Heap::UnBindBitmaps() {

1542   for (const auto& space : GetContinuousSpaces()) {

1543     if (space->IsContinuousMemMapAllocSpace()) {

1544       space::ContinuousMemMapAllocSpace* alloc_space = space->AsContinuousMemMapAllocSpace();

1545       if (alloc_space->HasBoundBitmaps()) {

1546         alloc_space->UnBindBitmaps();

1547       }

1548     }

1549   }

1550 }

另外，之前说过mark_bitmap是live_bitmap的一个子集，mark_bitmap中包含了所有的存活的非垃圾对象，因此交换mark_bitmap和live_bitmap的指针，使mark_bitmap作为下一次GC的live_bitmap. 同时reset 新的mark_bitmap。

300     SwapBitmaps();

2789 void Heap::ClearMarkedObjects() {

2790   // Clear all of the spaces' mark bitmaps.

2791   for (const auto& space : GetContinuousSpaces()) {

2792     accounting::ContinuousSpaceBitmap* mark_bitmap = space->GetMarkBitmap();

2793     if (space->GetLiveBitmap() != mark_bitmap) {

2794       mark_bitmap->Clear();

2795     }

2796   }

2797   // Clear the marked objects in the discontinous space object sets.

2798   for (const auto& space : GetDiscontinuousSpaces()) {

2799     space->GetMarkBitmap()->Clear();

2800   }

2801 }

由于mark_stack的目的是为了mark，所以在Finish阶段，也需要把mark_stack给清掉。

1292   mark_stack_->Reset();

Semi-Space Collector

Semi-Space Collector 在做垃圾回收的步骤和Mark Sweep是相同的。不过Semi-Space 是在NonConcurrent的情况下对Heap进行垃圾回收的。这样看起来好像简单了很多J。

Semi-Space Collector（下文的SS是其简称）在Mark之前，会指定一个From_Space和To_Space. 以及一个promoted_space. 凡是在mark的过程中位于From_Space的对象就会被move到To_Space中。当mark结束后，From_Space留下来的全是需要清除的垃圾，而To_Space就是mark后存活的对象，并且这些对象都紧凑排列，达到了"压缩"的效果。为了达到generation promotion的效果，在一次Mark结束后，to_space的最后一个对象的边界记录为last_gc_end. 然后to_space和from_space交换指针，之前的to_space就作为GC之后的From_space使用，即新的在Bumper Space对象都会在心的From_space中分配，并且分配的位置会在last_gc_end之后。等到下一次Semi-Space Collector来临后，凡是在From_Space中last_gc_end位置之前存活下来的对象就不再move到to_space了，而是move到promoted_space了，一般promoted_space会指定为main_space. 这就是SS的promotion generation的概念。

当位于from_space的object被move到to_space或者promo_dest_space的时候，老的object->monitor会告诉其他引用的object，新的位置。这样就可以便于更新了。比如：对象A和C都引用了对象B，A->B C->B. 如果在A引用B的时候扫描后把B搬移到了to_space中新的位置，那么更新A->B', 同时B->Monitor = 11|B'的地址。这样当C在Marking其引用的时候，发现B的monitor的高两位是11了，就知道B已经被移到新的位置了，只需要改变其引用就好了C->B'.

正如前言所述，Semi-Space Collector会根据情况不同来做GSS还是whole heap collection的SS。GSS只会对Bump Pointer Space采用Semi-Space Collector的方法进行垃圾回收。而whole heap collection的方法除了Bump pointer Space外，还会扫描main space, non moving Space和Large Object Space.（见下面的代码片段，重点是85～88行以及92～95行）

71 void SemiSpace::BindBitmaps() {

72   timings_.StartSplit("BindBitmaps");

73   WriterMutexLock mu(self_, *Locks::heap_bitmap_lock_);

74   // Mark all of the spaces we never collect as immune.

75   for (const auto& space : GetHeap()->GetContinuousSpaces()) {

76     if (space->GetLiveBitmap() != nullptr) {

77       if (space == to_space_) {

78         CHECK(to_space_->IsContinuousMemMapAllocSpace());

79         to_space_->AsContinuousMemMapAllocSpace()->BindLiveToMarkBitmap();

80       } else if (space->GetGcRetentionPolicy() == space::kGcRetentionPolicyNeverCollect

81                  || space->GetGcRetentionPolicy() == space::kGcRetentionPolicyFullCollect

82                  // Add the main free list space and the non-moving

83                  // space to the immune space if a bump pointer space

84                  // only collection.

85                  || (generational_ && !whole_heap_collection_ &&

86                      (space == GetHeap()->GetNonMovingSpace() ||

87                       space == GetHeap()->GetPrimaryFreeListSpace()))) {

88         CHECK(immune_region_.AddContinuousSpace(space)) << "Failed to add space " << *space;

89       }

90     }

91   }

92   if (generational_ && !whole_heap_collection_) {

93     // We won't collect the large object space if a bump pointer space only collection.

94     is_large_object_space_immune_ = true;

95   }

96   timings_.EndSplit();

97 }

从85～88行，可见，若generational_为true, 且whole_heap_collection_为false的情况下，会把non moving space和main space都会加入到immune_region中。而若whole_heap_collection为true，则non moving space和main space不会加入到immune_region中，并且也会扫描lage object space（94行）。Whole_heap_collection除了对bumper pointer space做SS之外，还会对non moving space和main space做mark sweep garbage collector.

那么什么时候需要Whole heap collection呢，SemiSpace刚开始的时候是每5次Generational Semi-Space Collector,做一次Whole heap collection。后来优化的措施是，被promoted的object数量达到一定阈值后，进行一次Whole heap collection. 或者从上一次whole heap collection 至今分配的Large Object bytes超过了阈值16MB（kLargeObjectBytesAllocatedThreshold）

注：

[1]. http://www.ibm.com/developerworks/library/j-ibmjava2/

参考

1.   https://android.googlesource.com/