ART学习笔记(三)Heap
# Heap中的关键类
位图
位图是ART中的一种数据结构，主要的目的是为了将对象的指针转换成一个位图里的索引，而指针中的地址值借助位图索引来进行计算：base + pos*sizeof(指针)，用这种方式减少指针本身所占用的内存空间
- HeapBitmap：HeapBitmap是一个辅助类，内部包含continuous_space_bitmaps和large_object_bitmaps_这两个成员变量，而这两个成员变量都是SpaceBitmap数组，分别存放ContinousSpaceBitmap和LargeObjectBitmap，这样其实也就涵盖了ART虚拟机里面用到的各种Space了
- SpaceBitmap：实际实现位图功能的类，对象存储规则为：
- 根据对象计算出该对象与位图基地址的偏移量
- 计算这个偏移量落在哪个字节
- 再计算这个偏移量落在字节的哪个比特位，记为mask
- 取出改偏移量所在的字节
- 如果mask所对应的比特位已经标记，则不处理，否则，设置mask比特位
- 注意点：位图储存空间是以字节为单位，而不是以比特位为单位
Space相关
Heap中有Space管理模块，对各类Space进行管理，创建Space之后通过AddSpace方式添加到Heap中
Heap将Space分为3个数组进行管理：
- continuous_spaces_：用于存放连续内存地址的Space对象
- discontinue_spaces_：用于存放内存地址不连续的Space对象
- alloc_spaces_：用于存放可分配内存的Space对象
- 注意点：
- 添加Space到Heap中的同时，需要把Space中存在的live_bitmap_和mark_bitmap_加入到Heap的live_bitmap_和mark_bitmap_中进行管理
- alloc_spaces中的元素可以和continuous_spaces_和discontinue_spaces_重叠
GC相关
紧接上文，Heap存在2个Heap Bitmap对象分别为live_bitmap_和mark_bitmap，以默认的CMS收集器为例，这两个Heap Bitmap中的取值情况为：
除此之外，Heap中还包含了三个ObjectStack，它的类型为AtomicStack，这三个ObjectStack分别为：Allocation Stack、Live Stack、Mark Stack，同样以默认的CMS收集器为例，三个Stack的取值情况为：
而在GC过程中这些stack会和bitmap结合使用，以Mark Sweep为例：
- live_bitmap_代表集合Live，也就是存活的对象
- mark_bitmap_代表集合Mark，也就是在GC过程中被标记的对象
- 而垃圾对象 = live_bitmap_ - mark_bitmap，也就是live_bitmap存在而mark_bitmap不存在的对象
- allocation_stack_是提供给各个线程用于存储该线程创建的对象
- live_stack的作用就是用于提供部分live_bitmap的内容，为什么是部分？这是因为其实在标记GC STW的过程中，allocation_stack_中的内容会被拷贝到live_stack中，然后allcation_stack_将被清空，用这种方式保证live_stack_中保存的是从上一次GC到本次GC过程中新分配的对象，应用于kGcTypeSticky这种垃圾回收策略
- mark_stack_的作用则是保存那些被标记的对象，以表后面可以执行递归标记
分代GC相关
- 分代GC的大体概念会把Heap划分为三个部分，新生代，老年代，空闲区(与Survivor区类似)，而其中新生代和老年代都被包含在Allocated Space中
- 分代GC通过将Allocated Space划分为多个区域，针对这些区域有针对性的GC，比如只针对新生代做GC，而老年代不做GC
而在分代GC还存在一个问题就是跨代引用，如图所示，如果老年代的对象持有新生代对象的引用，此时如果对新生代进行扫描，可能这个被引用的新生代对象就会被错误的回收，而此时如果对新生代与老年代进行一并扫描，又失去了分代GC的意义，而这个问题的解决思路就是在虚拟机中主动记录哪些老年代引用了新生代对象，然后分代GC不仅要扫描新生代对应的root，还需要扫描这些纳入记录的老年代对象，记录方式方法分为两种：
- RememberedSet：保存每一个引用新生代对象的老年代对象，优点精确，缺点是需要额外内存空间保存这些老年代对象
- CardTable：元素大小为1字节的数组，元素为Card，对应AllocatedSpace中一个128字节区域，若一个Card对应区域中有引用了新生代的对象，该Card都会被标记为脏Card
ART中：
- CardTable：针对整个Heap，每128字划分为一个Card
- RememberedSet：异于上文的RememberedSet，针对，ART中的RememberedSet以Card为单位，管理跨Space的引用关系，使用者为RosAllocSpace、DlMallocSpace
- ModUnionTable：与ART中的RememberedSet作用一致，使用者为ImageSpace、ZygoteSpace
- 注意点：
- ART 虚拟机中，不再区分新生代几老年代对象
- 虚拟机每执行一次iput-object指令，也就是给引用型变量赋值时，就会进行一次记录。这种记录点就是WriteBarrier，此时就会将该对象所在的Card标志为Dirty。
而在ART中，Heap根据垃圾收集器的类型决定内存分配器的类型，然后划分为多个Space，ModUnionTable和RememberedSet用来处理跨Space引用的问题
小结
# Heap对象/数组分配
创建Java 对象/数组时会使用new-instanc/array指令进行创建。这与我们的内存分配器的类型有关，而内存分配器的类型又与垃圾收集器类型有关
当使用Heap::ChangeCollector函数设置垃圾收集器时，函数调用过程为：
- Heap::ChangeCollector：根据不同的垃圾收集器对应不同的内存分配器，如CMS对应RosAlloc、Concurrent Copy对应Regin
- Heap::ChangeAllocator：修改内存分配器的类型，即修改堆的成员变量current_allocator_
- SetQuickAllocEntryPointsAllocator：对内存分配有关的入口地址进行修改。当执行new-instance
/array时，就会跳转到对应的入口进行执行
new-instanc/array指令的执行过程：
- 创建对象：
- 如果这个对象类型为String，则调用String::Alloc创建对象
- 如果这个对象类型不是String，则调用AllocObjectFromCode创建对象
- 创建数组：
- 调用AllocArrayFromCode创建数组
string.inl-> String::Alloc
基于编码信息计算出需要进行内存分配的大小，然后调用AllocObjectFromCode函数进行内存分配
entrypoint_utils-inl.h->AllocObjectFromCode
如果分配的是对象：转到对应kclass，也就是对应类的Alloc函数进行内存分配
如果分配的是数组：转到Array的Alloc函数进行内存分配
class-inl.h->Class::Alloc
转到Heap的AllocObjectWithAllocator进行内存分配
Array->Alloc
计算数组对象需要的内存大小，然后同样是调用Heap的AllocObjectWithAllocator进行内存分配
所以结论就是不管是数组分配还是对象分配，最后都会走到Heap的AllocObjectWithAllocator函数，只不过针对String和Array需要在此之前先计算好所需要的实际字节数
Heap::AllocObjectWithAllocator
- 如果分配的内存大于Heap中的largeObjec阀值(默认12KB)，并且创建的对象类型为基础数据类型或String，会通过AllocLargeObject函数进行内存分配，最终由LargeObjectSpace对分配的内存进行管理
- 如果分配的非大对象，则先进行8字节向上对齐，然后判断是否使用TLAB进行内存分配，如果TLAB内存足够，则直接从 TLAB 中进行内存分配（只有 BumpPointerSpace 及 RegionSpace 支持 TLAB）
- 如果使用RosAlloc，则会使用RosAllocSpace的AllocThreadLocal方法进行内存的分配，如果分配不成功，则会调用TryToAllocate方法进行内存的分配，TryToAllocate方法会根据内存分配器的类型选择不同的内存分配器进行内存分配。若分配失败则会调用 AllocateInternalWithGc 方法，这个方法会加大垃圾回收的力度，之后继续尝试分配内存
- 最后判断如果存在AllocationStack的情况下，会将分配的Object的引用push到AllocationStack栈上。（BumpPointer、Region、TLAB、RegionTLAB 四种分配器不存在 AllocationStack），AllocationStack是Heap的成员变量，而每个线程使用AllocationStack提供的控件来存储该线程上锁创建的对象
- AllocationStack的作用主要也是与GC有关：
- ART通过在对象分配时会将新分配的对象压入到Heap类的成员变量allocation_stack_描述的Allocation Stack中去，从而可以一定程度缩减对象遍历范围，这种情况出现在ART中的严苛GC
- 对于标记Allocation Stack的内存时，会预读取接下来要遍历的对象，同时再取出来该对象后又会将该对象引用的其他对象压入栈中，直至遍历完毕
# Heap内存回收及整理
Heap在创建的时候会指定前台及后台垃圾收集器的类型
- 前台垃圾收集器会在应用处于前台时进行垃圾收集，应用程序在前台运行时，响应性是最重要的，因此也要求执行的GC是高效的，而ART默认的前台收集器为CMS，所以采取的垃圾回收算法就是Mark Sweep
- 后台垃圾收集器一般需要较长时间暂停程序运行，应用程序在后台运行时，响应性不是最重要的，这时候就适合用来解决堆的内存碎片问题，而ART默认的后台收集器为HSC，所以采取的垃圾回收算法就是Mark Compact
而在Mark Sweep的FinishPhase收尾工作中会主动调用Heap::trim函数对堆进行裁剪，目的就是为了将空闲内存归还给操作系统，而Heap::trim函数最终会转交给RosAllocSpace或者DlMallocSpace执行trim函数，而最终会通过madvise系统调用通知操作系统哪些内存不再需要
而Mark Sweep存在最大的问题就是会造成内存碎片，ART在解决这个问题上并没有提出新的垃圾回收算法，而是在进程退到后台(处于用户不可感知的状态)的时候触发一次内存回收，这次内存回收将通过SemiSpace解决内存碎片问题
参考资料：《深入理解Android虚拟机ART》
