【Android】《深入理解 Android 虚拟机 ART》读书笔记(二)——内存分配实现与堆的设计

RosAlloc

ART 虚拟机中默认使用了 RosAllocSpace 来作为 MallocSpace 的实现,另一个实现是 DlMallocSpaceRosAllocSpace 使用了 RosAlloc 来负责具体的内存分配 RosAlloc 会与 ART 虚拟机的其他模块进行配合,因此相比 DlMalloc 的分配效果更好。

RosAlloc 的最小内存分配单元是 Slot ,共有 42 种不同的 Slot ,涵盖了从 8Byte 到 4KB 的不同粒度。

同时 RosAlloc 中有个十分重要的类 Run,它代表了一块供内存分配的内存分配资源池(Slot 资源池),一个Run 中包含了许多相同粒度的 Slot 。对于不同粒度的 SlotRun 的大小也不同,粒度 1KB 的 Slot 对应的 Run 拥有 2 页也就是 8KB 的内存供分配,而 2KB 的 Slot 对应的 Run 拥有 4 页也就是 16KB 的内存供分配。除此之外,Run 中还有 thread_local_free_list_free_list_ 这两个用于管理空闲 Slot 的对象。

RosAlloc 的内存分配首先需要计算出所分配的内存大小应该使用哪种粒度的 Slot 资源池,之后再从对应的 Run 中分配一个空闲的 Slot

RosAlloc 中通过 base_capacity_max_capacity 等成员变量描述了其管理的那一块内存,其中 base_ 是这块内存的基地址,后面两者则分别表示了其目前的大小以及能分配的最大尺寸。

同时,RosAlloc 还会创建一个内存映射对象以及一个单字节的整型数组,这个对象对应了一块内存,保存了所管理的内存中内存资源的分配情况及部分状态。而该整形数组则保存了每个内存页的状态。

创建过程

RosAlloc 创建时,主要有如下的步骤:

  1. 对不同粒度的 Slot 分别创建同步锁,通过对不同粒度的分配进行上锁,比直接对整个内存分配进行上锁的效率更高。

  2. base_ 强转为 FreePageRun 对象,通过其来管理我们的内存。强转后会通过 SetByteSize 方法设定其所能管理的内存大小(capacity),同时会通过 ReleasePages 方法对其所包含的内存区域进行释放。(此过程主要是将 page_map_ 这个数组中记录的内存页状态从 kPageMapEmpty 设置为 kPageMapReleased,表示该内存在系统中还未分配)

分配过程

对于超过 2KB 也就是 Slot 最大分配粒度的分配需求(大内存对象),会通过调用 AllocLargeObject 方法进行对应的内存分配,它会在内部通过 AllocPages 以页为单位进行分配。否则会调用 AllocFromRun 方法进行内存分配。

AllocFromRun 中首先会通过 SizeToIndexAndBracketSize 方法计算出该内存分配应该使用哪种粒度的资源池。之后根据分配粒度是否小于 128Byte 分为了两种情况:

  1. 若该分配的粒度小于 128Byte,则会尝试从线程本地内存资源池ThreadLocalRun)中分配。若该 Run 中没有空余内存,此时就会对该粒度的分配进行加锁,否则不用加锁。之后调用 MergeThreadLocalFreeListToFreeList 方法将 thread_local_free_list_ 中的空闲资源合并到 free_list_。之后会调用 RefillRun 方法创建一个新的 Run 并将其设置为该线程的本地内资源池。最后会调用该 ThreadLocalRunAllocSlot 方法分配 Slot 对象(Thread 专门对 RosAlloc 有单独的支持)
  2. 若所需内存大小大于 128Byte,会从 RosAlloc 内部的资源池分配,此时也会通过同步锁对对应粒度的分配加锁,之后会通过 AllocFromCurrentRunUnlocked 进行分配。

RefillRun 中会调用 AllocRun 去进行 Run 的创建,它首先会通过 AllocPages 分配该 Run 所需要的内存页,之后会调用其 InitFreeListfree_list_ 进行初始化。

AllocPages 是以内存页为单位进行分配的一个函数,RosAlloc 是通过 FreePageRun 来进行的内存分配管理,它在内存页所需内存足够的时候会将自己进行拆分,从而给 Run 分配足够的页内存,内存页所需内存不够时,则会考虑是否进行扩容。

AllocSlot 的过程倒是比较简单,直接从 free_list_ 中取出 head。也就是说 Run 是通过空闲链表的形式对 Slot 进行管理

每个维度维护了一个容器用于存储已满的 Run,分配的过程中,如果出现了分配空间不足的情况,会将该 Run 根据 idx 放入该 full_runs_[idx]容器中,并且将该 Run 剩余的空间并入 free_list_。最后创建新的对应类型的 Run

总结

RosAlloc 的内存分配分为了两级:

  1. 第一级是对于 Run 的内存分配,它是以页为单位,根据所存放的 Slot 类型进行分配的,其被分配的页是被 FreePageRun 所管理的。

  2. 第二级是对于 Slot 分配,主要是通过 Run 中的 FreeList 进行分配。

RosAlloc 将内存分配的大小分为了 42 种粒度的 Slot ,涵盖了从 8Byte 到 2KB 的各种分配大小,每种粒度的内存分配由对应的内存分配资源池(Run)进行管理。在分配时不是对整个分配流程加锁,而是针对对应的分配粒度加锁,提高了内存分配的效率。

RosAlloc 对每个线程设置了 16 种(8Byte 到 128Byte)的本地线程内存分配池(它与 TLAB 不同)。若本地内存资源足够,则无需同步锁的保护,进一步提高了效率。(这也是为什么要使用本地的内存资源池的原因。主要是为了减小加锁所带来的性能损耗)

在分配时,分为了三种情况:

  1. 8Byte - 128Byte:尝试从本地线程内存资源池进行分配,由于是线程私有的,不存在并发问题,因此不需要加锁从而提高分配效率。(我猜测只设定 16 个池的原因是因为这个范围的内存分配比较频繁,因此有着更高的性能需求)

  2. 128Byte - 2KB:从 RosAlloc 内部对应的内存分配池进行分配,由于存在并发问题,因此需要加锁。

  3. 2KB以上:通过 AllocLargeObject 方法进行分配,其内部也是通过 AllocPages 方法以页为单位进行的内存分配。

LargeObjectSpace

对于一个超过了指定阈值(默认 3 页也就是 12KB)的基本数据类型数组或 String 的内存分配,会使用 LargeObjectSpace 进行内存的分配。

LargeObjectSpace 有两个派生类:LargeObjectMapSpace 以及 FreeListSpace。具体使用取决于 Runtime 的运行参数,根据 CPU 平台而定。

LargeObjectMapSpace 会为每一次分配都通过 mmap 映射一块内存空间,之后以映射得到的 Object 为 Key,根据映射出的 MemMap 创建的 LargeObject 类为 Value,放入一个 Map 中进行管理。LargeObject 是一个用于保存内存映射 MemMap 对象的类。

因此其内存分配算法很简单,直接从操作系统映射一块内存即可。

new-instance / new-array

我们创建 Java 对象/数组时会使用 new-instance/array 方法进行创建。这与我们的内存分配器的类型有关,而内存分配器的类型则与垃圾收集器类型有关。

Heap::ChangeCollector 用于设置垃圾收集器,传入参数为垃圾收集器类型,如 kCollectorTypeCMS(ConcurrentMarkSweep 算法简称 CMS)

不同的垃圾收集器对应了不同的内存分配器,通过 ChangeAllocator 方法进行指定,如 CMS 垃圾收集器就对应了 RosAlloc 的内存分配器,对应使用 RosAllocSpace 作为提供内存资源的空间。

ChangeAllocator 方法中,会调用 SetQuickAllocEntryPointsAllocator 方法,这个方法会对内存分配有关的入口地址进行修改。当执行 new-instance/array 时,就会跳转到对应的入口进行执行。

指令的执行是通过一个基于 switch-case 的解释执行模式来实现。

  • 对于 new-instance,它会根据创建的对象是否是 String 调用不同的方法。
    • 对于 String,其会调用 String::Alloc 方法。
    • 而对于非 String 方法,其会调用 AllocObjectFromCode 方法。
  • 对于 new-array,它会调用 AllocArrayFromCode 方法。

  • String::Alloc 中,会首先根据编码等信息计算出最终所需要的内存大小,之后通过 heap->AllocObjectWithAllocator 方法进行内存的分配。

  • 对于 AllocObjectFromCode 方法,它会转调到类对应的 Alloc 方法中,其中也会调用 heap->AllocObjectWithAllocator 方法进行内存的分配。

  • 而对于 AllocArrayFromCode 方法,它会调用到 Array 的 mirror 对象的 Alloc 方法,在 Alloc 方法中会计算出数组所需要的内存大小,之后通过 heap->AllocObjectWithAllocator 方法进行内存的分配。

可以看出来,不论是对象的创建或是数组的创建,都会通过 heap->AllocObjectWithAllocator 方法进行内存的分配。它首先会判断其要分配的内存大小是否大于 12KB,若大于则说明其是大内存对象,会通过 AllocLargeObject 方法进行分配,最后会由 LargeObjectSpace 对分配的内存进行管理。

若不为大内存对象,首先会按 8Byte 对所需内存大小向上取整。

之后,在使用 TLAB 进行内存分配的情况下,若 TLAB 内存足够,会直接从 TLAB 中进行内存分配(只有 BumpPointerSpaceRegionSpace 支持 TLAB

之后,若是使用 RosAlloc,则会使用 RosAllocSpaceAllocThreadLocal 方法进行内存的分配。

前面若都不满足或 RosAlloc 分配不成功(TLAB 分配确认了大小足够,不会内存分配失败),则会调用 TryToAllocate 方法进行内存的分配,TryToAllocate 方法会根据内存分配器的类型选择不同的内存分配器进行内存分配。若分配失败则会调用 AllocateInternalWithGc 方法,这个方法会加大垃圾回收的力度,之后继续尝试分配内存。

最后在存在 AllocationStack 的情况下,会将分配的 Object 的引用 push 到 AllocationStack 栈上。(BumpPointerRegionTLABRegionTLAB 四种分配器不存在 AllocationStack)该栈存储于 Thread 中,它存储了指向分配对象的引用。

Heap

前台 / 后台垃圾收集器

在堆创建时,会指定一个前台垃圾收集器及一个后台垃圾收集器。

  • 前台垃圾收集器会在应用处于前台时进行垃圾收集,因为用户能够感知,因此该收集器不应当太耗时。

  • 后台垃圾收集器一般需要较长时间暂停程序运行,可能在这个过程中对空间进行压缩减少内存碎片,因此需要在用户感知不到时使用。

Space 管理

堆中有一个 Space 的管理模块,对各类 Space 进行统一管理。创建 Space 后,可以通过 AddSpace 方法存入。

HeapSpace 分为了三个数组进行管理:

  1. continuous_spaces_:用于存储连续内存地址的 Space

  2. discontinuous_spaces_:用于存储内存地址不连续的 Space

  3. alloc_spaces:用于存储可分配内存的 Space,并且 alloc_spaces 中的元素可以与前面两个数组中的元素重叠。

分代 GC

image-20191108142720523

我们首先了解一下分代 GC 的概念,分代 GC 将内存空间分为了三部分:空闲区域新生代老年代。其中新生代与老年代都属于 Allocated Space,里面包含了一个个的 Java Object 对象。

新生代的对象是更容易被垃圾回收的对象,而老年代的对象则是在前几轮垃圾回收后剩下的对象,可能是需要长期存在的对象。而分代 GC 的核心思想就是对不同区域做针对性的 GC,例如有的极端情况下只对新生代做 GC,而老年代则不做。

跨代引用问题

如果只对新生代作垃圾收集,可能导致一个问题:如果有老年代的对象持有了新生代对象的引用,此时如果只扫描新生代,可能这个被引用的新生代引用就会被错误地回收,但同时扫描老年代对象又失去了分代 GC 的意义。因此我们需要一种方式来记录引用了新生代的老年代对象,在垃圾收集器进行扫描时额外地扫描这些对象。记录方式主要有下面两种方式:

  • RememberedSet 机制:它是一个集合,记录了所有引用了新生代对象的老年代对象。在垃圾收集器进行扫描时除了对新生代进行扫描之外,还会去扫描这个集合中的老年代对象,从而避免错误的垃圾收集。RememberedSet 的优点就是定位精确,能准确的定位哪些老年代对象引用了新生代对象,但需要耗费额外的内存空间进行记录。

  • CardTable 机制,它是一个元素大小为 1Byte 的数组,每个元素称为一个 Card。之后对 AllocatedSpace 按 128 字节为单位进行区域划分,每个区域都对于了一个 Card。若一个 Card 对应区域中有引用了新生代的对象,该 Card 都会被标记为脏 Card。

也就是说 RememberedSet 是以单个对象为单位进行管理,而 CardTable 是以 Card 为单位进行管理。

WriteBarrier

在 ART 虚拟机中,不再区分新生代几老年代对象。虚拟机每执行一次 iput-object 指令,也就是给引用型变量赋值时,就会进行一次记录。这种记录点就是 WriteBarrier,此时就会将该对象所在的 Card 标志为 Dirty。

关于前面跨代引用的问题,在 ART 虚拟机中变为了跨 Space 进行引用的问题。在 ART 虚拟机中,采用了两种结合的方式进行处理,RememberedSet 管理的不再是单个对象,而是以 Card 为单位进行管理

对于一个 MallocSpace 对象,它会按 128Byte 进行划分,每个单元可以映射到 CardTable 的一个 Card,而一个 RememberedSet 会关联一个 MallocSpace,用于记录该 Space 中的对象是否引用了其他 Space 中的对象等信息,通过一个 MallocSpace 所关联的 RememberedSet,我们可以操作该 Space 与其他 Space 中对象的引用关系。

而还有一种特殊的 ModUnionTable,它的作用与 RememberedSet 差不多,不过它只用于 ImageSpace 以及 ZygoteSpace

参考资料

《深入理解 Android 虚拟机 ART》第 13 章

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注

%d 博主赞过: