小编：本文由 WebInfra 团队姚忠孝、杨文明、张地编写。意在经过深化剖析常用的内存分配器的要害完成，以了解虚拟机动态内存办理的规划哲学，并为完成虚拟机高效的内存办理供给指引。

在现代计算机体系结构中，内存是体系中心资源之一。虚拟机( VM )作为运行程序的抽象”计算机”，内存办理是其不行或缺的才能，其间首要包括如内存分配、垃圾收回等，而其间内存分配器又是决议”计算机”内存模型，以及高效内存分配和收回的要害组件。

虚拟机内存管理之内存分配器

如上图所示，各种编程都供给了动态分配内存目标的才能，例如创立浏览器 Dom 目标，创立 Javascript 的内存数组目标( Array Buffer 等)，以及面向体系编程的 C / C++ 中的动态分配的内存等。在运用开发者视点看，经过言语或许库供给的动态内存办理(分配，开释)的接口便是完成目标内存的分配和收回，而不需求关心底层的详细完成，例如，所分配目标的实践内存巨细，目标在内存中的方位排布(目标地址)，能够用于分配的内存区域，目标何时被收回，怎么处理多线程状况下的内存分配等等；而关于虚拟机或许 Runtime 的开发者来说，高效的内存分配和收回办理是其间心使命之一，而且内存分配器的首要目标包括如下几方面：

1. 削减内存碎片，包括内部碎片和外部碎片

  • 内部碎片：分配出去的但没有运用到的内存，比如需求32字节，分配了40字节，剩下的8字节便是内部碎片。
  • 外部碎片：巨细不合适导致无法分配出去的内存，比如一直恳求16字节的内存，但是内存分配器中保存着部分8字节的内存，一直分配不出去。

2. 进步功用

内存分配需求经过内核分配虚拟地址空间和物理内存，频繁的体系调用和多线程竞赛显著的下降了内存分配的功用。内存分配器经过接收内存的分配和收回，无论在单线程仍是多线程场景下都能够很好的起到进步功用的作用。

3. 进步安全性

跟着体系和运用对安全性的关注度进步，默认的内存分配机制无论在内存数据布局，仍是对硬件安全机制的运用上都无法最大化的满意运用诉求，因而自定义内存分配器能够针对特定的体系和运用充分的运用硬件安全机制( MTE )等，一起也能够在实践体系中引入内存安全性检测机制来进一步进步安全性。

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

因而，本文经过深化剖析常用的内存分配器的要害完成( dlmalloc , jemalloc ， scudo ， partition-alloc )，来更好的了解背面的规划考量和规划哲学，认为咱们完成高效，轻量的运行时和虚拟机内存分配器，内存办理模型供给指引。

1. dlmalloc [1]

* Key Points ( salient points )

  • 从操作体系分配( 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 )

小内存经过闲暇链表办理闲暇内存的运用状况；下图是某一时刻或许的内存快照状况，每个内存巨细( size )都可作为闲暇链表数组的下标拜访对应巨细的闲暇链表。

虚拟机内存管理之内存分配器

依据闲暇链表保护的闲暇内存状况，选用如下的分配次序和分配战略进行实践内存分配。

虚拟机内存管理之内存分配器

  • 大内存( Large )

大内存不选用闲暇链表数组进行办理(虚拟机地址空间方范围大，时刻和空间功率均低)，选用 trie-tree 作为大内存的状况保护结构，每次内存分配和开释在 trie-tree 上进行高效的搜索和插入。

大内存选用如下的分配次序和分配战略进行实践内存分配。

虚拟机内存管理之内存分配器

  • 超大内存( Huge ) > 64 kb

关于超大内存，直接经过 mmap 从操作体系分配内存。

* Weaknessd

  • lmalloc 不是线程安全的，因而 bionic 现已切换到更现代的堆完成计划
  • 典型的 Buddy memory allocation 算法，这种算法能够有用削减外部碎片，但内部碎片严重。

2. jemalloc ( Android 5.0.0 ~ )

该内存办理器的首要目标是进步多线程内存运用的功用( efficiency 、 locality )和较少内存碎片(最大优势是强大的多线程分配才能)

* Key Points ( salient points )

虚拟机内存管理之内存分配器

  • 调用 mmap 从操作体系分配一整块大内存 ” Chunk “， Chunk 为固定巨细( 512k )，能够被分割成两部分：头信息区域和数据区域。数据区域被分割成若干个 Run 。
  • 在 Chunk 的数据区中一个或许多个页会被分成一个组，用于供给特定巨细的内存分配，被称为” Run “(相同巨细内存所在的页组)，相同巨细 Region 对应的 Run 归于同一个 Bin ( bucket )进行办理(如下图所示)。
  • ” Run “中的内存会被切分为固定小的内存块” Region “，作为最小的内存分配单元，作为实践内存地址回来给内存分配恳求。

虚拟机内存管理之内存分配器

上图展现了内存分配的首要流程及数据结构。jemalloc经过 areans 进行内存统一内存分配和收回， 因为两个arena在地址空间上简直不存在任何联络, 就能够在无锁的状况下完成分配。相同因为空间不接连, 落到同一个 cache-line 中的几率也很小, 确保了各自独立。抱负状况下每个线程由一个arena担任其内存的分配和收回，因为 arena 的数量有限, 因而不能确保一切线程都能独占 arena , Android 体系中默认选用两个 arena ，因而会选用负载均衡算法( round-robin )完成线程到 arena 的均衡分配并经过内部的 lock 坚持同步。

多个线程或许同享同一个 arena ，jemalloc为了进一步避免分配内存时呈现多线程竞赛锁，因而为每个线程创立一个 ” tcache “，专门用于当时线程的内存恳求。每次恳求开释内存时，jemalloc会运用对应的线程从 tcache 中进行内存分配(其实便是 Thread Local 闲暇链表)。

每个线程内部的内存分配按如下3种不同巨细的内存恳求别离处理：

  • 小目标( 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 独立的红黑树进行办理。

依据以上的中心数据结构，内存分配流程大致流程如下图所示:

虚拟机内存管理之内存分配器

* Summary

  • jemalloc 的中心是一个依据桶分配器( bin )。每个 arena 都有一组逻辑 bin ，每个 bin 都服务于特定的尺度等级。分配是从具有足够大以习惯分配恳求的最小尺度的 bin 进行的，它们之间的步长很小，能够削减碎片。
  • 每个 arena 都有自己的锁，所以不同 arena 上的操作不会争抢锁。
  • 临界区很短，仅当从 arena 中分配内存(同享 arena 线程间内部锁)，或许分配 runs 的时候才需求坚持确定。
  • 线程特定的内存缓存进一步减小数据竞赛。

3. scudo ( Android 11 ~)

Scudo 这个名字源自 Escudo ，在西班牙语和葡萄牙语中表示“盾牌”。为了安全性考虑，从 Android 11 版本开端，Scudo 会用于一切原生代码（低内存设备除外，其仍运用 jemalloc ）。在运行时，一切可执行文件及其库依赖项的一切原生堆分配和取消分配操作均由 Scudo 完成；假如在堆中检测到损坏状况或可疑行为，该进程会间断。(以下内容以 Android-11 64位体系完成为剖析目标)

* Key Points ( salient points )

Scudo 定义了 Primary 和 Secondary 两种类型分配器[4]，当需求小于 max_class_size ( 64 k )时运用 Primary Allocator ，大于 max_class_size 时运用 Secondary Allocator 。

structAndroidConfig{
usingSizeClassMap=AndroidSizeClassMap;
#ifSCUDO_CAN_USE_PRIMARY64
//256MBregions
typedefSizeClassAllocator64<SizeClassMap,28U,1000,1000,
/*MaySupportMemoryTagging=*/true>
Primary;
#else
//256KBregions
typedefSizeClassAllocator32<SizeClassMap,18U,1000,1000>Primary;
#endif
//Cacheblocksupto2MB
typedefMapAllocator<MapAllocatorCache<32U,2UL<<20,0,1000>>Secondary;
template<classA>
usingTSDRegistryT=TSDRegistrySharedT<A,2U>;//Shared,max2TSDs.
};
  • Primary Allocator

Primary Allocator [5]首先会依据 AndroidSizeClassConfig [6]中的配置恳求一个完整的虚拟内存空间，并将虚拟内存空间分成不同的区域( sizeClass )，每块区域只能分配出固定空间，区域1只能分配32 bytes (包括 header )，区域2只能分配48 bytes 。

虚拟机内存管理之内存分配器

Primary Allocator 从操作体系恳求” PrimaryBase “指向的虚拟内存区域后，依照如下的配置为虚拟内存区域区分为 32 个 256 M 的内存区域( SizeClass )。

每个 SizeClass 供给特定巨细的内存分配，其内存区域依照 RegionInfo 结构布局，其间” randon offset “是0~16页的随机值，以使随机化 ReginBeg 地址下降定向进犯的危险。

每个 SizeClass 区域初始分配内存为 MAP_NOACCESS ，当收到内存分配恳求时， ClassSize 会分配出一块可用的内存区域( MappedUser )，并以 SizeClass 指定的 block 巨细切分成可用运用的 Regions 。当进行 Regions 的分配的一起，每个可用的 Region 均经过 TranferBatch 进行办理( TBatch ), 这样 TBatch 的链表就能够作为 FreeList 供内存分配运用。

为了安全性的考虑，最终回来的内存依照上图” block “所示的内存布局组织。其间” chunk-header “[7]是为了确保每一个 chunk 区域的完整性， Checksum 用的是较为简略的CRC算法，此外，内存开释过程中 Scudo 增加了 header 检测机制，一方面能够检测内存踩踏和多次开释，另一方面也阻挠了野指针的拜访。

structUnpackedHeader{
uptrClassId:8;
u8State:2;
u8Origin:2;
uptrSizeOrUnusedBytes:20;
uptrOffset:16;
uptrChecksum:16;
};

structAndroidSizeClassConfig{
staticconstuptrNumBits=7;
staticconstuptrMinSizeLog=4;
staticconstuptrMidSizeLog=6;
staticconstuptrMaxSizeLog=16;
staticconstu32MaxNumCachedHint=14;
staticconstuptrMaxBytesCachedLog=13;
staticconstexpru32Classes[]={
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,
};
staticconstuptrSizeDelta=16;
};
  • Thread Local Cache

Scudo Primary Allocator 运用了 Thread Local Cache 机制来加速多线程下内存的分配，如下图所示。当一个线程需求分配内存时，它会经过各自对应的 TSD ( Thead Specific Data )来发起目标的恳求，每个 TSD 目标经过各自的 Allocator::Cache 及其 TransferBatch 来寻觅合适的闲暇内存。但 TransferBatch 的巨细是有限的，假如没有可用的内存会进一步运用 Primary Allocator 进行分配。

抱负状况下每个线程由一个 TSD 担任其内存的分配和收回，因为 TSD 的数量有限, 因而不能确保一切线程都能独占 TSD , Android 体系中默认选用两个 TSD ，因而会选用负载均衡算法( round-robin )完成线程到 arean 的均衡分配并经过内部的 lock 坚持同步。

虚拟机内存管理之内存分配器

  • Secondary Allocator

Secondary Allocator [8]首要用于大内存的分配(> max_size_class )，直接选用 mmap 分配出一块满意要求的内存并依照 LargeBlock::Header 进行组织, 并统一在 InUseBlocks 链表中统一办理，如下图所示。

为了安全性考虑， LargeBlock 选用如下图 LargeBlock Layout 进行组织，其间：

  • 在 LargeBlock 的前后都增加了保护页以检测 heap-overflow 过错;
  • LargeBlock Header 域首要记载了 LargeBlock 的内存布局信息以便于数据存取和办理；
  • 剩下内存结构和 small block 布局共同，安全性考量和规划也共同(统一性)。

此外，为了进步功率功率， LargeBlock 在开释的时候会经过 MapAllocatorCache 将可被复用的闲暇内存进行缓存，在大内存分配中优先从 Cache 中进行分配。其间 CachedBlock 和 LargeBlock::Header 根本共同，都是对 LargeBlock 内存布局信息的记载和办理。

虚拟机内存管理之内存分配器

  • Scudo内存分配和收回

Scudo Android R 内存分配中心流程如下所示。

NOINLINEvoid*allocate(uptrSize,Chunk::OriginOrigin,
uptrAlignment=MinAlignment,
boolZeroContents=false){
initThreadMaybe();//初始化TSDArray和PrimarySizeClass地址空间
//skiptrivials.......
//Iftherequestedsizehappenstobe0(morecommonthanyoumightthink),
//allocateMinAlignmentbytesontopoftheheader.Thenaddtheextra
//bytesrequiredtofulfillthealignmentrequirements:weallocateenough
//tobesurethattherewillbeanaddressintheblockthatwillsatisfy
//thealignment.
constuptrNeededSize=
roundUpTo(Size,MinAlignment)+
((Alignment>MinAlignment)?Alignment:Chunk::getHeaderSize());
//skiptrivials.......

void*Block=nullptr;
uptrClassId=0;
uptrSecondaryBlockEnd;
if(LIKELY(PrimaryT::canAllocate(NeededSize))){
//从PrimaryAllocator分配smallobject
ClassId=SizeClassMap::getClassIdBySize(NeededSize);
DCHECK_NE(ClassId,0U);
boolUnlockRequired;
auto*TSD=TSDRegistry.getTSDAndLock(&UnlockRequired);
Block=TSD->Cache.allocate(ClassId);
//Iftheallocationfailed,themostlikelyreasonwitha32-bitprimary
//istheregionbeingfull.Inthatevent,retryineachsuccessively
//largerclassuntilitfits.Ifitfailstofitinthelargestclass,
//fallbacktotheSecondary.
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无法分配小内存，
//则直接在SecondaryAllocator进行分配
if(UNLIKELY(ClassId==0))
Block=Secondary.allocate(NeededSize,Alignment,&SecondaryBlockEnd,
ZeroContents);
//skiptrivials.......
constuptrBlockUptr=reinterpret_cast<uptr>(Block);
constuptrUnalignedUserPtr=BlockUptr+Chunk::getHeaderSize();
constuptrUserPtr=roundUpTo(UnalignedUserPtr,Alignment);
void*Ptr=reinterpret_cast<void*>(UserPtr);
void*TaggedPtr=Ptr;

//skiptrivials.......
//依据回来内存地址，设置chunk-header目标数据
Chunk::UnpackedHeaderHeader={};
if(UNLIKELY(UnalignedUserPtr!=UserPtr)){
constuptrOffset=UserPtr-UnalignedUserPtr;
DCHECK_GE(Offset,2*sizeof(u32));
//TheBlockMarkerhasnosecuritypurpose,butisspecificallymeantfor
//thechunkiterationfunctionthatcanbeusedindebuggingsituations.
//Itistheonlysituationwherewehavetolocatethestartofachunk
//basedonitsblockaddress.
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);
//skiptrivials.......
returnTaggedPtr;
}

以上代码包括的中心流程如下图所示：

  • 当有线程经过 malloc 恳求内存分配时，会经过符号重定向调用 scudo::allocator 的 allocate 函数。
  • 进入 allocate 函数后，首先调用初始化函数，以完成 TSD 和 Primary 虚拟地址空间初始化。
  • 依据 malloc 内存 size 判定是否能够经过 Primary Allocator 进行分配。
    1. 假如 Primary Allocator 分配的内存符合要求，计算 malloc size 对应的 SizeClass ,当时线程选用 TSD 的 Allocator::Cache 分配内存， Allocator::Cache 为每个 SizeClass 保护了一个 TransferBatch 链表，其间 TransferBatch 中是指向实践 Block 区域的指针。
    2. 假如 Allocator::Cache 无法分配内存，那么恳求 Allocator 从对应 SizeClass 的 FreeList 中获取内存并 refill 到 Allocator::Cache 中。
    3. 假如 FreeList 中没有可用的内存， Allocator 需求从对应 SizeClass 的 class region 扩充闲暇区域(调整MappedUser)，并将内存区域切分为固定的 Block 巨细，将可用的 Block 内存组织成 TransferBatch 添加到 FreeList ，并进一步 refill 到 Allocator::Cache 中供分配运用。
    4. 当咱们分配小内存时，首先会检查最合适区域中是否有闲暇方位，假如没有，则会去高一级区域中分配。例如在32 Bytes SizeClass Region 无法内存出内存，那么会逐步测验从48 Bytes ，64 Bytes SizeClass Region 中进行分配(小内存区域耗尽)。
  • 假如内存没有分配成功，则选用 Secondary Allocator 持续测验分配内存。
  • 假如获取了有用的内存地址，则依据回来内存地址，计算 CheckSum 并设置 chunk-header 目标数据。
  • 将回来内存地址经过 malloc 回来。

虚拟机内存管理之内存分配器

以上介绍了内存分配的大致流程，内存开释能够依照上述流程做反向数据流推演，不再详细打开(对Quarantine的延迟开释机制能够自行剖析)。

* Summary

Scudo尽管它的分配战略更加简化，安全性上得到了很大的改进，但为了安全性引入 chunk header 等元数据办理，内存随机化和对齐引入内存碎片必定程度上下降了内存的运用功率；此外，依据 chunk header 的内存校验以及内存安全性保障也必定程度上下降了功率(功用)。

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

以上的剖析首要参照了 Android R 中的完成，最初来源于 LLVM 中 scudo 的完成， LLVM 中有 scudo_allocator [9] 和 standalone [10] 2份完成，详细内容能够从[9][10]作为进口进行源码的剖析。

4. PartitionAlloc

PartitionAlloc 是 Chromium 的跨渠道分配器，优化客户端而不是服务器工作负载的内存运用，并专注于有意义的最终用户活动，而不是在实践运用中并不重要的微基准[16]。

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

* Key Points ( salient points )

  • Central Partition Allocator [16]

PartitionAlloc 经过分区( Partition )来阻隔各内存区域。其间每个分区都运用依据 slab 的分配器来分配内存， PartitionAlloc 预先保存” Super Page “作为分区虚拟地址空间( Slab )。每个”Super Page”( Slab )依照实践可分配的最小内存单元巨细( Slot )分成各自独立的” Slot Span “，每个 Slot Span 包括多个 Partition Page 并归归于特定的桶( Partiton Bucket )用于供给中小内存的分配。

PartitionAlloc 针对大内存分配（> kMaxBucketed ）是经过直接内存映射（ direct map ）完成的(特殊的 bucket 办理)，为了确保和小内存分配结构上的统一性，直接内存映射内存结构选用(伪装)和小内存分配相似的 Super Page 进行办理，而且保存了相似的内存布局布局(如下图所示)。

虚拟机内存管理之内存分配器

如上图所示， PartitionAlloc 中每个分区的内存经过一个 PartitionRoot 进行办理，” PartitionRoot “中保护了一个 Bucket 数组；每个 Bucket 保护了” slot span “的集合；跟着分配恳求的到来， slot span 逐步得到物理内存( Commit )，并依照所关联桶的可分配内存的巨细，将物理内存切分为 slot 的接连内存区域。PartitionAlloc 除了支撑多个独立的分区来进步安全性外；每个” Super Page “被分割成多个” Partition Page “，其间第一个和最终一个” Partition-Page “首要作为保护页运用( PROT_NONE )。( Super Page 挑选 2 MB 是因为PTE在 ARM 、 ia 32 和 x 64上对应的虚拟地址是2 M )。

  • Partition Layer

PartitionAlloc 尽管经过分区来阻隔各区域，但在同一分区内多线程拜访受单个分区锁的保护。为了缓解多线程的数据竞赛和扩展性问题，选用如下三层架构来进步功用：

  • Per-thread cache为了缓解多线程内存分配的数据竞赛问题，每个线程的数据缓存区( TLS )保存了少数用于常用中小内存分配的 Slots 。因为这些 Slots 是按线程存储的，所以能够在没有锁的状况下分配它们，而且只需求更快的线程本地存储查找，从而进步进程中的缓存局部性。每个线程的缓存现已过定制以满意大多数恳求，经过批量分配和开释第二层的内存，分期锁获取，并在不捕获过多内存的状况下进一步改进局部性。
  • Slot span free-listSlot span free-lists 在每线程缓存未命中时调用。关于每个对应的 bucket size，PartitionAlloc 保护与该巨细相关联的 Slot Span ，并从 Slot Span 的闲暇列表中获取一个闲暇 Slot 。这仍然是一条快速途径( fast path )，但比每线程缓存慢，因为它需求确定。但是，此部分仅适用于每个线程缓存不支撑的较大分配，或许作为填充每个线程缓存的批处理。
  • Slot span management最终，假如桶中没有闲暇的 slot ，那么 Slot span management 要么从 Super Page ( slab )中挖出空间用于新的slot span，要么从操作体系分配一个全新的Super Page ( slab )。这是一条慢速途径( slow path )，很慢但十分不经常操作。

虚拟机内存管理之内存分配器

以上简略介绍了 PartitionAlloc 中分区的要害结构， PartitionAlloc 在 Chromium 中首要保护了四个分区，针对每种分配器的用处采纳不同的优化计划，并依据实践目标的类型在四个分区中任意一个上分配目标。

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

PartitionAlloc 在 Node 分区和 LayoutObject 分区上分配时不会获取锁，因为它确保 Node 和 LayoutObject 仅由主线程分配。PartitionAlloc 在 Buffer 分区和 FastMalloc 分区上分配时获取锁。PartitionAlloc 运用自旋锁以进步功用。

  • 安全性

安全因素的考虑也是PartitionAlloc最重要的目标之一，这里运用虚拟地址空间来到达安全加固的意图：不同的分区存在于阻隔的地址空间；当某个分区内存页上一切目标都被开释掉之后，其物理内存归还于体系后，但其地址空间仍被此分区保存，这样就确保了此地址空间只能被此分区重用，从而避免了信息泄露；PartitionAlloc的内存布局，供给了以下安全属性：

  • 线性溢出不会损坏分区 – guard page。
  • 元数据记载在专用区域（不是每个目标周围）。线性上溢或下溢不会损坏元数据。
  • 大内存分配在开端和结束时被保护分页 – guard page。
  • 桶有助于在不同地址上分配不同巨细的目标。一页只能包括相似巨细的目标。

* Summary

传统内存分配器( jemalloc , etc.)调用 malloc 为目标分配内存时，无法指定分配器将在哪里存储什么样的数据，而且无法指定要存储它的方位。C++ 类目标或许紧挨着包括密钥的字符串，该密钥或许与函数指针的结构相邻。在一切这些数据之间是分配器用来办理堆的元数据（一般为双向链表和标志存储的指针），这为漏洞寻觅要掩盖的数据目标时为他供给了更多挑选。例如，当运用开释后运用漏洞时，咱们期望将类型 B 的目标放置在先前分配类型 A 的目标的方位。然后咱们能够触发类型 A 的过时指针的取消引证，该指针反过来运用类型 B 目标中的位。这一般是或许的，因为两个目标都分配在同一个堆中[43]，而 PartitionAlloc 具有如下特功用够满意分配需求。

  • 调用者能够依据需求创立任意数量的分区。分区的直接内存成本是最小的，但碎片导致的隐含成本不行轻视。
  • PartitionAlloc 确保不同的分区存在于进程地址空间的不同区域。当调用者开释了一个分区中一个页面中包括的一切目标时， PartitionAlloc 将物理内存回来给操作体系，但持续保存地址空间区域。PartitionAlloc 只会为同一个分区重用一个地址空间区域。但在必定程度上，它会糟蹋虚拟空间( virtual address space )。

因为 PartitionAlloc 是面向 Chromium 特定运用场景的高效内存分配器，为特定内存运用场景的定制化才能能够供给高效的内存分配和收回(例如， layout 分区， node 分区)，但面向通用的内存分配场景及高安全场景假如能够和 jemalloc, secudo 才能进行有用的融合( porting )，或许会是一个可行的途径和方向( MTE 等)。

5. Overview

从如上的剖析能够看出，分配器的全体功用和空间功率取决于各种因素之间的权衡，例如缓存多少、内存分配/收回战略等，实践的时刻和空间功率需求依据详细场景衡量并针对性的优化。如下从功用，空间功率，以及 benchmark 方面供给一些总结和参考。

内存分配器 说明
dlmalloc github.com/ARMmbed/dlm… 非线程安全，多线程分配功率低 内存运用率较低(内存碎片多) 分配功率低 安全性低
jemlloc github.com/jemalloc/je… ** **代码体积较大，元数据占有内存大 内存分配功率高(依据run(桶) + region) 内存运用率高 安全性中
scudo android.googlesource.com/platform/ex… 更注重安全性，内存运用功率和功用上存在必定的丢失 内存分配功率偏高(sizeclass + region, 安全性+checksum校验) 内存运用率低(元数据，安全区，地址随机化内存占用多) 安全性高( 安全性+checksum校验，地址随机化，保护区)
partition-alloc source.chromium.org/chromium/ch… 代码体积小 内存运用率偏高(比较于jemalloc多保护区，依据range的分配) 安全性偏高(比较sudo少安全性，完整性校验，地址随机化) 内存分配功率高(依据bucket + slot，分区特定优化) 支撑”全”渠道 PartitionAlloc Everywhere (BlinkOn 14) : www.youtube.com/watch?v=QfY…

Benchmark alternate malloc implementations:

  • expertmiami.blogspot.com/2019/05/wha…
Allocator QPS (higher is better) Max RSS (lower is better)
tcmalloc (internal) 410K 357MB
jemalloc 356K 1359MB
dlmalloc (glibc) 295K 333MB
mesh 142K 710MB
portableumem 24K 393MB
hardened_malloc* 18K 458MB
guarder FATALERROR**
freeguard SIGSEGV***
scudo (standalone) 400K 318MB

6. Rererence

*[1]. A Tale of Two Mallocs: On Android libc Allocators – Part 1–dlmalloc blog.nsogroup.com/a-tale-of-t…

[2]. jemalloc: github.com/jemalloc/je…

[3]. A Tale of Two Mallocs: On Android libc Allocators – Part 2–jemalloc: blog.nsogroup.com/a-tale-of-t…

[4] AndroidConfig: android.googlesource.com/platform/ex…

[5].SizeClassAllocator64: android.googlesource.com/platform/ex…

[6]. AndroidSizeClassConfig:
android.googlesource.com/platform/ex…

[7]. Chunk: android.googlesource.com/platform/ex…

[8] MapAllocator : android.googlesource.com/platform/ex…

[9] scudo_allocator :github.com/llvm/llvm-p…

[10] standalone: github.com/llvm/llvm-p…

[11]. Scudo : source.android.com/devices/tec…

[12]. Scudo Hardened Allocator: llvm.org/docs/ScudoH…

[13]. System hardening in Android 11: android-developers.googleblog.com/2020/06/sys…

[14]. Android Native | Scudo内存分配器: /post/691455…

[15]. Scudo Allocator : zhuanlan.zhihu.com/p/235620563

[16]. Efficient And Safe Allocations Everywhere! : blog.chromium.org/2021/04/eff…

[17]. PartitionAlloc Design: chromium.googlesource.com/chromium/sr…

[18]. partition_alloc_constants: source.chromium.org/chromium/ch…

[19]. Unified allocator shim: chromium.googlesource.com/chromium/sr…

[20]. Porting PartitionAlloc To PDFium: struct.github.io/pdfiu