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中。扫描结束后,对比两张位图AB:所有A中置位的位置,却没有B中被置位,被视为垃圾。并根据位图中的索引检索得到对象,然后释放该对象占用的内存。

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


Mark-Sweep Collector

要了解Android的垃圾回收策略,需要首先弄清楚对于每一个AndroidHeap,有哪些Space.对于普通的Android VM进程来说,其Heap都是从Zygote继承过来。所以,每一个VM 进程Heap的虚拟地址区间基本上都是一样的(区间的末端范围会有些不同)。对于一个普通的VM进程Heap的区间一般是这样划分的。
1.  Heap中的空间
Image Space的容量取决于boot.artboot.oat的容量大小(具体可以到/data/dalvik-cache/下查看这两个文件的大小)。在Image Space后面紧接着的就是Zygote Space。顾名思义,由于Zygote是所有VM进程的祖先,因此在普通的VM进程孵化出之前,Zygote是需要一些object的,这些object都被压缩放在Zygote Space中(为什么是压缩,后面讲Semi-Space时会有涉及)。紧挨着Zygote Space的是Main Space, Main Spacelimit被设置为了176MB. 其实从Zygote Space的起始到Non Moving Space的结束位置是有512MB大小的。

Mark-Sweep Collector只针对Heap中的Zygote SpaceMain SpaceNon Moving Space做垃圾回收处理. Temp SpaceBump pointer Space的垃圾回收归属于Semi-Space Collector来处理。

Mark-Sweep Collector根据轻重程度不同,可以分为三类:Sticky, Partial, Full. 又根据做GC的过程中是否暂停所有的mutator线程分为ConCurrentNon-Concurrent. 所以,ART系统一共定义了6MS的垃圾回收器。即,
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没有其他的引用,弹出FF没有其他的引用。弹出B
c). 标记B的引用D,压入D. 标记B的引用E,压入E。弹出E
d). E没有任何引用。弹出DD没有任何引用。栈空。结束。
1.1.2  immune_region是做什么的?
在一个Heap中有几个Space区,这些space的用途是不一样的,比如Image Space, 其中放的是boot.artboot.oat的代码段数据段。对于Image Space,其中的数据是不经常更改的,因此,GC是不会完整地扫描该区域。还有Zygote Space, 该区放的是ZygoteFork该进程之前的Zygote内容,因此也是不经常改变的。根据当前系统的内存短缺情况,采取不同程度的GC扫描策略,于是凡将某个space指定给immune_region的,GC便不会去扫描。可是,不扫描的话,如果该Space中有object的引用修改了,怎么办呢,比如Image Space有个对象A本来引用了B,但后来更改,A引用C了,于是在GC的时候,需要把B当作垃圾,而CMark。这就需要额外的数据结构ModUnionTable以及CardTable了。
1.1.3  ModUnionTableCardTable
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有更改。
在做GCMark时,凡是CardTable中属于immune_region的值为0x70Card, 被记录到ModUnionTable 中有一个类似于setc++数据结构中,同时将该Card的值减去1,即0x6F
1.1.4  RememberedSetCardTable
RememberedSetModUnionTable的作用是一样的,不同的是ModUnionTable记录Image Space, Zygote Space对其他space的引用的修改。而RememberedSet记录的是Non Moving SpaceMain SpaceSemi Space引用的修改。RememberedSet虽然只在Semi-Space Collector中起作用,但在CMS的ProcessCards中也会对CardTable中属于Non Moving Space和Main Space的Dirty Card 在RememberedSet中做备份。
1.1.5  Live_BitmapMark_Bitmap
如前所述,Mark Sweep垃圾回收策略采取的是标记跟踪法。Live_BitmapMark_Bitmap便是用来做标记的。他们都是位图的数据结构,每一位代表8个字节的空间。Live_Bitmap记录了当前存在于VM进程中所有的未标记的object和标记过的objectMark_Bitmap经过了Mark 的过程,记录了当前VM进程中所有被引用的object. Live_BitmapMark_Bitmap中间的差集,便是所有为被系统引用的object,即是可以回收的垃圾了。
1.1.6  allocation_stacklive_stack
所有新分配的object会被allocation_stack来记录,然后在Marking的时候,再在Live_Bitmap中打上live的标记。allocation_stacklive_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,选择Concurrentmark-sweep的垃圾收集器。


1.2 Marking Phase

1.2.1 Marking阶段,如果是sticky/partialCMS, 会把Image SpaceZygote Space都加入到Immune_region中。并且,对于stickyCMS,还会将Main SpaceNon moving Spacemark_bitmaplive_bitmap绑定(绑定的意思是mark_bitmaplive_bitmap指向同样的bitmap,这样做的目的是在mark的时候直接把live_bitmapmark_bitmap都标记了,就不会对这两个space做垃圾回收处理了)。Sticky CMS是为了处理新分配出来的对象中的垃圾而不会处理其他Space中的垃圾,因此采用了绑定的方法。而Partial SpaceZygote 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.artboot.oatVM进程对其更改的可能性比较小,完整地对这个60+MBSpace扫描一遍性价比太低了。

1.2.2  处理CardTable。扫描CardTable,凡是对应于Image SpaceZygote Space的值为0x70(kCardDirty)Card都被插入到ModUnionTableCardCache中,并在CardTable中对该Card进行Aged, Aged的做法就是其值为0x70的减去1,非0x70且非0的设置为0;凡是对应于Main SpaceNon Moving Space的更改的card,都存储在RememberedSet中。其他非Semi SpaceCardTable中有对应的修改的Card, 只进行Aged(好像没有其他的SpaceL).
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中,所有的Space22302242行都已经涉及到了,因此2251行似乎很多余。2232行处理的是Image SpaceZygote Space,2237行处理的是Non Moving SpaceMain 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.21.2.4的过程中新产生的对象或者被修改的对象引用了。
(2)从各个入口开始Mark操作,在操作的过程中对于遇到的没有在mark_bitmapmark过的,在mark_bitmap上做Mark标记。
(3)扫描card table1.2.5刚开始时aged过的card以及在这个过程中dirtycard对应的对象都进行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外,还需要扫描cardtableDirty 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中置位的对象当作垃圾。157170行就是把垃圾占用的空间给释放掉。
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_bitmaplive_bitmap的一个子集,mark_bitmap中包含了所有的存活的非垃圾对象,因此交换mark_bitmaplive_bitmap的指针,使mark_bitmap作为下一次GClive_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_SpaceTo_Space. 以及一个promoted_space. 凡是在mark的过程中位于From_Space的对象就会被moveTo_Space中。当mark结束后,From_Space留下来的全是需要清除的垃圾,而To_Space就是mark后存活的对象,并且这些对象都紧凑排列,达到了"压缩"的效果。为了达到generation promotion的效果,在一次Mark结束后,to_space的最后一个对象的边界记录为last_gc_end. 然后to_spacefrom_space交换指针,之前的to_space就作为GC之后的From_space使用,即新的在Bumper Space对象都会在心的From_space中分配,并且分配的位置会在last_gc_end之后。等到下一次Semi-Space Collector来临后,凡是在From_Spacelast_gc_end位置之前存活下来的对象就不再moveto_space了,而是movepromoted_space了,一般promoted_space会指定为main_space. 这就是SSpromotion generation的概念。

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

正如前言所述,Semi-Space Collector会根据情况不同来做GSS还是whole heap collectionSSGSS只会对Bump Pointer Space采用Semi-Space Collector的方法进行垃圾回收。而whole heap collection的方法除了Bump pointer Space外,还会扫描main space, non moving SpaceLarge Object Space.(见下面的代码片段,重点是8588行以及9295行)
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 }
8588行,可见,若generational_true, whole_heap_collection_false的情况下,会把non moving spacemain space都会加入到immune_region中。而若whole_heap_collectiontrue,则non moving spacemain space不会加入到immune_region中,并且也会扫描lage object space94行)。Whole_heap_collection除了对bumper pointer spaceSS之外,还会对non moving spacemain spacemark sweep garbage collector.

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

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

评论

此博客中的热门博文

Linux/ARM Page Table Entry 属性设置分析

ARM Linux 如何模拟X86 PTE中的Present Young和Dirty标志位

提交了30次才AC ---【附】POJ 2488解题报告