ART虚拟机 | Large Object Space

本文分析基于Android 12(s)

在Android中，Java heap分为几个不同的空间，其中LOS(Large Object Space)用于管理≥12KB的基本类型数组（譬如int[]）和字符串对象（java.lang.String）。Android中的LOS有两种实现，一种是FreeList的方式，另一种是Map的方式。当前Android中默认采取的是第一种方式，因此本文着重分析Free List Large Object Space内部的实现和设计背后的思考。

1. 对象的申请

当我们调用new申请新的Java对象时，最终会进入Heap::AllocObjectWithAllocator函数。其中会根据对象的类型和大小来判断是否需要走LOS申请的路径。

[art/runtime/gc/heap-inl.h]

if (kCheckLargeObject && UNLIKELY(ShouldAllocLargeObject(klass, byte_count))) {
  // AllocLargeObject can suspend and will recall PreObjectAllocated if needed.
  obj = AllocLargeObject<kInstrumented, PreFenceVisitor>(self, &klass, byte_count, pre_fence_visitor);

[art/runtime/gc/heap-inl.h]

inline bool Heap::ShouldAllocLargeObject(ObjPtr<mirror::Class> c, size_t byte_count) const {
  // We need to have a zygote space or else our newly allocated large object can end up in the
  // Zygote resulting in it being prematurely freed.
  // We can only do this for primitive objects since large objects will not be within the card table
  // range. This also means that we rely on SetClass not dirtying the object's card.
  return byte_count >= large_object_threshold_ && (c->IsPrimitiveArray() || c->IsStringClass());
}

[art/runtime/gc/heap.h]

// Primitive arrays larger than this size are put in the large object space.
static constexpr size_t kMinLargeObjectThreshold = 3 * kPageSize;
static constexpr size_t kDefaultLargeObjectThreshold = kMinLargeObjectThreshold;

large_object_threshold_默认为3页，也即12KB。当对象大小超过12KB，且类型为基础类型数组或字符串时，系统将采用AllocLargeObject的方式从LOS中申请对象。

在进入到具体的分配算法之前，我们有必要考虑一个问题：为什么Android需要对这些大对象做单独的管理？而不是将它们放到Region Space中做统一的管理？

从Concurrent Copying Collector的回收算法中我们或许能够知道答案。这些LOS中的对象不会引用其他对象，因此是引用关系链的末端。作为末端的节点，它们在三色标记中不会出现灰色的状态，因此可以省去一些中间辅助的数据和环节。那既然如此，为什么不将所有的字符串和基础类型数组都放到LOS中呢？原因是那些小对象放到LOS中会产生严重的碎片化(fragmentation)，而LOS内部是没有压缩/拷贝之类的整理算法的，因此碎片化问题无法得到解决。规避的方案就是只将大对象放入LOS中，且按页对齐，这样就不会存在因碎片化而无法释放整页物理内存的情况。

下图展示的是LOS内部的结构。名为”[anon:dalvik-free list large object space]”的内存块(vma)在Heap初始化时占用512M的虚拟内存，用于存放实际的对象。其中每一页对应一个AllocationInfo对象，该对象存放在名为”[anon:dalvik-large object free list space allocation info map]”的vma中。AllocationInfo对象含有2个uint32_t的字段，大小为8个字节。每一页都需要一个AllocationInfo对象，因此”[anon:dalvik-large object free list space allocation info map]”的vma大小为1M。

AllocationInfo中有两个字段，prev_free_表示该页之前有多少空闲页，alloc_size_表示分配的对象占用几页。通常而言，只有分配对象和空闲对象的第一页的AllocationInfo才有意义，至于中间页的AllocationInfo，分配和释放时都不会用到其中的数据。

概念上来说，分配的动作其实很简单：第一步是找到合适的空闲区域，第二步是把对象塞进去。那么如何找到合适的空闲区域呢？

回过头来看看vma的名称”[anon:dalvik-free list large object space]”，”free list”意味着LOS中维护了一个列表，记录了所有空闲区域的信息。

下图便是”free list”的具体实现。free_blocks的类型为std::set，插入其中的元素为AllocationInfo*。不太符合直觉的是，我们插入的AllocationInfo*通常属于已分配页，而不是空闲页。通过已分配页AllocationInfo的prev_free_字段，我们可以间接获取空闲区域的信息。至于为什么这么设计，我们等到释放那一节再详细阐述。因为按照直觉理解，我们插入空闲页的AllocationInfo似乎更方便，而且可以省去prev_free_字段。

std::set内部其实是有序的，它通常采用红黑树的数据结构。

inline bool FreeListSpace::SortByPrevFree::operator()(const AllocationInfo* a,
                                                      const AllocationInfo* b) const {
  if (a->GetPrevFree() < b->GetPrevFree()) return true;
  if (a->GetPrevFree() > b->GetPrevFree()) return false;
  if (a->AlignSize() < b->AlignSize()) return true;
  if (a->AlignSize() > b->AlignSize()) return false;
  return reinterpret_cast<uintptr_t>(a) < reinterpret_cast<uintptr_t>(b);
}

决定排序的标准有三个：

1. 本页之前的空闲页数量
2. 本对象所占用的页数量
3. AllocationInfo对象的地址

前面两个标准都是数量信息，因此可能遇到相同的情况。增加第三个标准就可以保证每一次插入时位置的唯一性。我们可以总结出如下排序规律：

1. 前方空闲页数量较少的AllocationInfo*排在前面
2. 当前方空闲页数量相等时，本对象所占用页数较少的AllocationInfo*排在前面
3. 当本对象所占用的页也相等时，AllocationInfo地址较小的排在前面

介绍完free_blocks的组成后，我们进入具体的分配流程。

2. 对象的释放

由于LOS的对象按页对齐，所以一旦释放，其所占用的物理内存也可以被释放，如下所示。当madvise系统调用执行后，该进程的RSS会立即下降（取决于释放了几页）。

[art/runtime/gc/space/large_object_space.cc]

  // madvise the pages without lock
  madvise(obj, allocation_size, MADV_DONTNEED);

当对象前后存在空闲块时，释放时还需将不同的空闲块合并起来。回到我们上面遗留的那个问题：为什么AllocationInfo需要prev_free_字段？

因为在一个对象前后都是空闲块的情况下，我们需要根据自身的AllocationInfo分别找到它们。根据alloc_size_我们可以找到位于后方的空闲块，而前方的空闲块只能通过prev_free_找到。因此，prev_free_这个字段必不可少。至于加入到free_blocks中的AllocationInfo*为什么属于已分配区域，我认为从更新prev_free_的角度来说它更方便，且free_blocks中可以减少一个元素的开销（相较于将空闲区域的AllocationInfo*存入free_blocks）。

3. 总结

本文作为Android Heap的开篇之作，内容较为简单。不过既然开了头，希望后续能保持连贯的输出吧😁！