2014年6月12日星期四

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/
参考

2014年4月15日星期二

Understanding ROS Memory Allocator in ART Virtual Machine

Agenda

1. Run基本结构
2. 主要算法
a)    Allocate
b)    Free

正文

ROS memory allocator Android ART virtual machine GC的一个内存分配器。 ROS Run-of-Slots的缩写。 ROS allocator中,分配的都是虚拟地址区间(具体的物理内存什么时候分配是由kernel中的page fault来负责的)。ROS allocator的基本分配单元是slotslot大小16Bytes2048Bytes,分别是16,32,48,… n*16,512,1024,2048. 不同大小的slot对应不同种类的Run,换句话说,一种Run提供大小相同的slot. 一共有34Run.

, Run的基本结构
一个Run,可以分为两大部分,分别是Run headerData Area。如下所示:

Run header里面包含了
            Magic number: Debug相关
            Size_bracket_idx_: 表示了该Run中的slotsize是多大。比如Size_bracket_idx_10,那么该Run中的slotsize是(10+1*16=176 Bytes.
            Is_thread_local:表示了该Run是否是Thread local area. ROS allocator规定每个线程都会持有一组Thread local Run,该组Runslot size最大为176Bytes. 即,如果某个线程需要分配一个space,若该space不大于176Bytes,那么就从该线程的Run中获得虚拟内存,而不会从ART runtime中获取。
           to_be_bulk_freed_: 该字段是一个flag,用来辅助处理一次释放多个对象的情况。若该标志置位,说明该Run有多个slot正在被释放。若该Runthread local的,那么bulk_free_bitmap的置位信息将会更新到thread_local_free_bitmap中。thread_local_free_bitmap_的信息会在分配thread local slot的时候存在失败的情况下,会更新thread_local_free_bitmap_中的信息到alloc_bitmap_中。若该Run不是thread local的,那么在bulk free的时候,会同步到alloc_bit_map_字段中。alloc_bit_map_是用来在分配slot的时候指示哪些slot已经被分配出去了。
            top_slot_idx_: 一个Run在分配slot的时候,slotRunData Area中的分配顺序是从小到大的。因此该字段表示当前slot分配到哪里了。若需要分配新的slot,只需要在该字段的基础上+1就可以了。可是,在Run分配slot的时候,也会有某些被分配过的slot又被释放的情形。因此若top_slot_idx_到头的情况下,会根据alloc_bit_map_看一下该Run中是否还有空闲的slot可供分配。若有,那么就分配出去。
            alloc_bit_map_[]: Run中的每一个slot在该字段代表一位。若为1,说明slot被分配出去了。若为0,说明该slot还是空闲的。
            bulk_free_bit_map_[]: 每一个slot在该字段中代表1位。若free,置1,该字段会在适当的时候,更新到thread_local_free_bit_map_[]然后在适当的时候更新到alloc_bit_map[]或者直接更新到alloc_bit_map_[],前者对应于该Runthread_local的情况,后者对应于该Run是非thread_local的情况。至于为什么要有这个bulk_free_bit_map_[]字段,是为了性能的考虑,可以减少锁冲突。
            thread_local_free_bit_map_[]: 若该Runthread local的,那么该字段会在slot free的时候置1,当在适当的时候会更新到alloc_bit_map_[]字段中(具体的时机见前面to_be_bulk_freed_的说明)。
            padding 是为了对齐的需要。由于每种Run占用的空间不同(占用的空间包含Run headerData Area),slot的大小,slot的数量都不同,因此三个bitmap(alloc_bit_map_[],bulk_free_bit_map_[],thread_local_free_bit_map_[])所占用的空间大小也不同。而last slot是需要页对其的,因此Data area部分是需要n*slot_size页对其,所以这个padding的空间大小也是每种Run都是不一样的。

slot0,slot 1,…,last slot,是真正的数据区。若没有被分配出去,就是空闲的,若分配出去了,就是已经被使用了。

二,主要算法
1.      分配
当系统向garbage collection请求为一个object分配空间的时候,首先计算该object所占用的空间大小request_size, request_size大于2048Bytes,则直接申请页。否则,根据request_size,查找对应的Run. 系统正在被分配的Run都组织为数组,这些Run数组分为两类,一类是用于分配大于176Bytes的数据块的,另一类是用于分配小于176Bytes的数据块,这类是thread local的。如开头所述,每一slot大小的Run对应于一个索引,slot大小为16Run对应数组中的第0个,数组第n个对应于slot大小为(n+1)*16Run. 找到Run后,
(1)     若该Run为空,表示,该Run还没有向系统申请空间。不过这种情况下并不会立即向系统申请空间,而是会查一下,是否有该种类的Run之前已经全部被分配出去后,又因为有些slot被释放,而又可以被复用的情况。如果有,就用可以复用的Run. 否则,就像系统申请若干虚拟页,每一类的Run在一次填充的时候,需要的页数都是不一样的,具体的页数存放在numOfPages[]数组中。所有slot用完的Run都存放在full_runs_hash_set中。而由于有slot被释放而又有可用的slotRun则存放在non_full_runs_Set中。
(2)     若该Run非空,先查一下top_slot_idx_字段,若该字段并没有到达结尾,就返回一个slot,并把top_slot_idx_字段加1。若top_slot_idx_字段已经到达结尾,那么会搜索一下有没有在该Run中已经分配出去的slot由释放的情况,如果有,分配出去。若该Runslot都用满了,那就看看该Run是不是thread local的,如果是的话,将thread_local_free_bit_map_[]中的信息同步过来,看是否有用的slot. 若至此仍然没有找到一个可用的slot,那把该Run加入到full_runs_hash_set中。重新分配一个Run,向系统申请页. 然后在从该Run中分配slot. 每分配一个slot 就会将alloc_bit_map_中对应的bit1,表示该slot被分配出去了。
2.     释放
若某个object被释放后,根据该object的地址,rundown成页地址,根据页地址去查询该页的用途。对于一个ROS系统所拥有的虚拟页都是连续的,事先通过mmap的方式分配得到。ROS系统维护了一个page_map_的数组。每一页对应一个Byte. 如果该页用于slot分配的Run,Run占用的第一页在page_map_中对应的byte设置为枚举常量kPageMapRun, 剩余页被设置为枚举kPageMapRun。因此当释放某个object的时候,根据地址以及page_map_可以得到Run在内存中的地址。 如果该object属于Largeobjectpage_map_中对应的byte的值为kPageMapLargeObject),那就直接释放该页。
若该页在page_map_中对应的byte的值为kPageMapRun,就在对应的Run中将alloc_bit_map slot的对应位清0.说明该slot空闲了。若该slot对应的Run并非系统正在使用的Run(Run因为slot被用完后,系统又分配了新的slot),那么就将该Runfull_runs_中移到non_full_runs中。如果该Run此时全部为free了,就会将该Run分解掉,其占用的pages退回到free_pages_set中。而如果该Runthread local的,那么该Run是不会被退回的,因为若该Runthread local的情况下,该Run一定属于当前正在使用的Run。如果thread localRun中的slot全部被消耗完了,会被扔到full_runs_中,其thread local的属性也会被去掉。

三,参考