[PHP] 虚拟机内存管理之内存分配器

• 内部碎片：分配出去的但没有使用到的内存，比如需要32字节，分配了40字节，多余的8字节就是内部碎片。
• 外部碎片：大小不合适导致无法分配出去的内存，比如一直申请16 字节的内存，但是内存分配器中保存着部分8字节的内存，一直分配不出去。
  

• 检测线性溢出， UAF 等多种内存非法访问异常
• 内存加固(地址随机化， MTE , etc .)
  

• 从操作系统分配( sbrk , mmap )一大块内存 " Segment " ( N * page_size )，多个 Segment 通过链表相互连接，" Segment "可以为不同大小。
• 每次申请内存，从 Segment 中分配一块内存" chunk "的内存地址(如果当前 Segment 不满足分配需求，进入步骤 a. 从操作系统分配 Segment )，" chunk "可以为不同大小。
• dlmalloc 中切分出的各中大小的 chunk 需要通过" bin "来统一管理，" Bin "用于记录最近释放的可重复使用的块(缓存)。有两种类型的 Bin ：" small bin "和“ tee bin ”。Small bins 用于小于 0x100 字节的块。每个 small bin 都包含相同大小的块。" tree bin "用于较大的块，并包含给定大小范围的块。" small bin "被实现为简单的双向链表，" tree bin "被实现 chunk 大小为 key 的 tries 树。
  

• 小内存( Small < 0x100 bytes )
  

• 大内存( Large )
  

• 超大内存( Huge ) > 64 kb
  

• dlmalloc 不是线程安全的，因此 bionic 已经切换到更现代的堆实现方案
• 典型的 Buddy memory allocation 算法，这种算法能够有效减少外部碎片，但内部碎片严重。
  

• 调用 mmap 从操作系统分配一整块大内存 " Chunk "， Chunk 为固定大小( 512k )，可以被分割成两部分：头信息区域和数据区域。数据区域被分割成若干个 Run 。
• 在 Chunk 的数据区中一个或者多个页会被分成一个组，用于提供特定大小的内存分配，被称为" Run "(相同大小内存所在的页组)，相同大小 Region 对应的 Run 属于同一个 Bin ( bucket )进行管理(如下图所示)。
• " Run "中的内存会被切分为固定小的内存块" Region "，作为最小的内存分配单元，作为实际内存地址返回给内存分配申请。
  

• 小对象( Small Object )    根据 Small Object 对象大小，从 Run 中的指定 " region " 返回。
• 大对象( Large Object )    Large Object 大小比 chunk 小，比 page 大，会单独返回一个 " Run "(1或多个 page 组成)。
• 超大对象( Huge Object ) > 4 MB    huge object 的内存直接采用 mmap 从 system memory 中申请(独立" Chunk ")，并由一棵与 arena 独立的红黑树进行管理。
  

• jemalloc 的核心是一个基于桶分配器( bin )。每个 arena 都有一组逻辑 bin ，每个 bin 都服务于特定的尺寸等级。分配是从具有足够大以适应分配请求的最小尺寸的 bin 进行的，它们之间的步长很小，可以减少碎片。
• 每个 arena 都有自己的锁，所以不同 arena 上的操作不会争抢锁。
• 临界区很短，仅当从 arena 中分配内存(共享 arena 线程间内部锁)，或者分配 runs 的时候才需要保持锁定。
• 线程特定的内存缓存进一步减小数据竞争。
  

struct AndroidConfig {
  using SizeClassMap = AndroidSizeClassMap;
#if SCUDO_CAN_USE_PRIMARY64
  // 256MB regions
  typedef SizeClassAllocator64<SizeClassMap, 28U, 1000, 1000,
                 /*MaySupportMemoryTagging=*/true>
    Primary;
#else
  // 256KB regions
  typedef SizeClassAllocator32<SizeClassMap, 18U, 1000, 1000> Primary;
#endif
  // Cache blocks up to 2MB
  typedef MapAllocator<MapAllocatorCache<32U, 2UL << 20, 0, 1000>> Secondary;
  template <class A>
  using TSDRegistryT = TSDRegistrySharedT<A, 2U>; // Shared, max 2 TSDs.
};

struct UnpackedHeader {
  uptr ClassId : 8;
  u8 State : 2;
  u8 Origin : 2;
  uptr SizeOrUnusedBytes : 20;
  uptr Offset : 16;
  uptr Checksum : 16;
  };

struct AndroidSizeClassConfig {
  static const uptr NumBits = 7;
  static const uptr MinSizeLog = 4;
  static const uptr MidSizeLog = 6;
  static const uptr MaxSizeLog = 16;
  static const u32 MaxNumCachedHint = 14;
  static const uptr MaxBytesCachedLog = 13;

  static constexpr u32 Classes[] = {
    0x00020, 0x00030, 0x00040, 0x00050, 0x00060, 0x00070, 0x00090, 0x000b0,
    0x000c0, 0x000e0, 0x00120, 0x00160, 0x001c0, 0x00250, 0x00320, 0x00450,
    0x00670, 0x00830, 0x00a10, 0x00c30, 0x01010, 0x01210, 0x01bd0, 0x02210,
    0x02d90, 0x03790, 0x04010, 0x04810, 0x05a10, 0x07310, 0x08210, 0x10010,
  };
  static const uptr SizeDelta = 16;
};

• 在 LargeBlock 的前后都增加了保护页以检测 heap-overflow 错误;
• LargeBlock Header 域主要记录了 LargeBlock 的内存布局信息以便于数据存取和管理；
• 剩余内存结构和 small block 布局一致，安全性考量和设计也一致(统一性)。
  

NOINLINE void *allocate(uptr Size, Chunk::Origin Origin,
              uptr Alignment = MinAlignment,
              bool ZeroContents = false) {
  initThreadMaybe();  // 初始化TSD Array 和 Primary SizeClass地址空间

  // skip trivials.......

  // If the requested size happens to be 0 (more common than you might think),
  // allocate MinAlignment bytes on top of the header. Then add the extra
  // bytes required to fulfill the alignment requirements: we allocate enough
  // to be sure that there will be an address in the block that will satisfy
  // the alignment.
  const uptr NeededSize =
    roundUpTo(Size, MinAlignment) +
    ((Alignment > MinAlignment) ? Alignment : Chunk::getHeaderSize());

  // skip trivials.......
  
  void *Block = nullptr;
  uptr ClassId = 0;
  uptr SecondaryBlockEnd;
  if (LIKELY(PrimaryT::canAllocate(NeededSize))) {
    // 从 Primary Allocator分配small object
    ClassId = SizeClassMap::getClassIdBySize(NeededSize);
    DCHECK_NE(ClassId, 0U);
    bool UnlockRequired;
    auto *TSD = TSDRegistry.getTSDAndLock(&UnlockRequired);
    Block = TSD->Cache.allocate(ClassId);
    // If the allocation failed, the most likely reason with a 32-bit primary
    // is the region being full. In that event, retry in each successively
    // larger class until it fits. If it fails to fit in the largest class,
    // fallback to the Secondary.
    if (UNLIKELY(!Block)) {
    while (ClassId < SizeClassMap::LargestClassId) {
      Block = TSD->Cache.allocate(++ClassId);
      if (LIKELY(Block)) {
      break;
      }
    }
    if (UNLIKELY(!Block)) {
      ClassId = 0;
    }
    }
    if (UnlockRequired)
    TSD->unlock();
  }
  // 如果分配的是大内存，或者Primary 无法分配小内存，
  // 则直接在Secondary Allocator进行分配
  if (UNLIKELY(ClassId == 0))
    Block = Secondary.allocate(NeededSize, Alignment, &SecondaryBlockEnd,
                 ZeroContents);

    // skip trivials.......

  const uptr BlockUptr = reinterpret_cast<uptr>(Block);
  const uptr UnalignedUserPtr = BlockUptr + Chunk::getHeaderSize();
  const uptr UserPtr = roundUpTo(UnalignedUserPtr, Alignment);

  void *Ptr = reinterpret_cast<void *>(UserPtr);
  void *TaggedPtr = Ptr;
  
  // skip trivials.......

  // 根据返回内存地址，设置chunk-header对象数据
  Chunk::UnpackedHeader Header = {};
  if (UNLIKELY(UnalignedUserPtr != UserPtr)) {
    const uptr Offset = UserPtr - UnalignedUserPtr;
    DCHECK_GE(Offset, 2 * sizeof(u32));
    // The BlockMarker has no security purpose, but is specifically meant for
    // the chunk iteration function that can be used in debugging situations.
    // It is the only situation where we have to locate the start of a chunk
    // based on its block address.
    reinterpret_cast<u32 *>(Block)[0] = BlockMarker;
    reinterpret_cast<u32 *>(Block)[1] = static_cast<u32>(Offset);
    Header.Offset = (Offset >> MinAlignmentLog) & Chunk::OffsetMask;
  }
  Header.ClassId = ClassId & Chunk::ClassIdMask;
  Header.State = Chunk::State::Allocated;
  Header.Origin = Origin & Chunk::OriginMask;
  Header.SizeOrUnusedBytes =
    (ClassId ? Size : SecondaryBlockEnd - (UserPtr + Size)) &
    Chunk::SizeOrUnusedBytesMask;

  // 设置chunk-header，CheckSum用于完整性校验
  Chunk::storeHeader(Cookie, Ptr, &Header);

  // skip trivials.......

  return TaggedPtr;
  }

• 当有线程通过 malloc 请求内存分配时，会通过符号重定向调用 scudo::allocator 的 allocate 函数。
• 进入 allocate 函数后，首先调用初始化函数，以完成 TSD 和 Primary 虚拟地址空间初始化。
• 根据 malloc 内存 size 判定是否可以通过 Primary Allocator 进行分配。
  

• 如果 Primary Allocator 分配的内存符合要求，计算 malloc size 对应的 SizeClass ,当前线程采用 TSD 的 Allocator::Cache 分配内存， Allocator::Cache 为每个 SizeClass 维护了一个 TransferBatch 链表，其中 TransferBatch 中是指向实际 Block 区域的指针。
• 如果 Allocator::Cache 无法分配内存，那么请求 Allocator 从对应 SizeClass 的 FreeList 中获取内存并 refill 到 Allocator::Cache 中。
• 如果 FreeList 中没有可用的内存， Allocator 需要从对应 SizeClass 的 class region 扩充空闲区域(调整MappedUser)，并将内存区域切分为固定的 Block 大小，将可用的 Block 内存组织成 TransferBatch 添加到 FreeList ，并进一步 refill 到 Allocator::Cache 中供分配使用。
• 当我们分配小内存时，首先会检查最合适区域中是否有空闲位置，如果没有，则会去高一级区域中分配。例如在32 Bytes SizeClass Region 无法内存出内存，那么会逐步尝试从48 Bytes ，64 Bytes SizeClass Region 中进行分配(小内存区域耗尽)。
  

• 如果内存尚未分配成功，则采用 Secondary Allocator 继续尝试分配内存。
• 如果获取了有效的内存地址，则根据返回内存地址，计算 CheckSum 并设置 chunk-header 对象数据。
• 将返回内存地址通过 malloc 返回。
  

• 内存
  
  • Primary Allocator 会在独立划分的一块虚拟地址空间( RegionSize* ClassNums ~ 2G )中采用随机化策略分配，为了安全性的同时引入了内存碎片。
  • Primary 分配的内存中， chunk header 记录用于内存检查的信息，有效数据比例较低(特别是小内存对象，32 bytes 有效数据为 50% )。
  • Secondary 分配的内存区前后都有保护页，内存空间使用率较低。
    
• 性能
  
  • 运行期需要进行安全性检测( heap-overflow etc .)，完整性检测( CheckSum )等安全策略，存在性能损失。
  • 
    

• 统一跨平台的内存分配，增强安全性。
• 在不影响安全性和性能的前提下，降低碎片，减少内存占用。
• 定制分配器以优化 Chrome 的性能。
  

• Per-thread cache
  

• Slot span free-list
  

• Slot span management
  

• Buffer 分区：主要分配变长对象或者是内容可能会被用户脚本篡改的对象，如 Vector 、 HashTable 、 ArrayBufferContent 、 String 等容器类对象；
• Node分区（之前版本叫 model object 分区）：主要分配 dom 节点对象，通过重写 Noded 的 new / delete 运算符实现；
• LayoutObject 分区：主要分配 layou 相关对象，如 LayoutObject 、 PaintLayer 、双向字体 BidiCharacterRun 等对象；
• FastMalloc 分区：主要分配除其他三种类型之外的对象(通用对象分配器)，大量功能逻辑的内部对象都归于此分区；
  

• 线性溢出不会破坏分区 - guard page。
• 元数据记录在专用区域（不是每个对象旁边）。线性上溢或下溢不会破坏元数据。
• 大内存分配在开始和结束时被保护分页 - guard page。
• 桶有助于在不同地址上分配不同大小的对象。一页只能包含类似大小的对象。
  

• 调用者可以根据需要创建任意数量的分区。分区的直接内存成本是最小的，但碎片导致的隐含成本不可低估。
• PartitionAlloc 保证不同的分区存在于进程地址空间的不同区域。当调用者释放了一个分区中一个页面中包含的所有对象时， PartitionAlloc 将物理内存返回给操作系统，但继续保留地址空间区域。PartitionAlloc 只会为同一个分区重用一个地址空间区域。但在一定程度上，它会浪费虚拟空间( virtual address space )。