Chrome浏览器安全之PartitionAlloc内存分配器分析
PartitionAlloc内存分配器是笔者迄今为止读过的最复杂的内存分配器，大约有3w+行代码。
1 数据结构
1.1 PartitionRoot
PartitionRoot对象是PartitionAlloc内存管理总的对象入口。
partition_allocator/partition_root.h
buckets是个Bucket类型的数组，它的每个元素代表特定的slot大小。
Init函数用于初始化PartitionAddressSpace以及ThreadCache。
1.2 PartitionAddressSpace
partition_allocator/partition_address_space.h
setup_字段保存了每个pool的类型和起始地址，通过GetPoolAndOffset来获取。
1.3 AddressPoolManager
PartitionAlloc通过POOL的概念管理内存池，一个进程有kNumPools个类型的pool，注意内存池是对整个进程共有的，不是线程专有。
enum pool_handle : unsigned {
kBRPPoolHandle用于32位，kPkeyPoolHandle用于x86提供的pkey保护，kRegularPoolHandle和kConfigurablePoolHandle是我们关心的。
Pool依附于AddressPoolManager结构体内：
class PA_COMPONENT_EXPORT(PARTITION_ALLOC) AddressPoolManager {
Reserve函数通过mmap为pool保留一段特定大小的内存。
Add函数初始化一个pool的地址。
void AddressPoolManager::Add(pool_handle handle, uintptr_t ptr, size_t length) {
Add函数通过上面介绍的PartitionAddressSpace:init对所有的pool进行初始化赋值：
void PartitionAddressSpace::Init() {
1.4 PartitionBucket
partition_allocator/partition_bucket.h
一个bucket用于分配一个特定大小的内存块。Bucket由一个个类型为SlotSpanMetadata的slotspan链接起来，active_slot_spans_head链接当前活跃的slotspan，即半满状态的slotspan，empty_slot_spans_head链接为空的slotspan，decommitted_slot_spans_head为一种特殊的空slotspan，它里面的内存页处于decommitted状态，这是典型的slab结构。
1.5 SlotSpanMetadata
partition_allocator/partition_page.h
SlotSpanMetadata是所有slot的管理结构，每个slot是由PartitionFreelistEntry表示。
partition_allocator/partition_freelist_entry.h
SetNext设置下一个next entry。
class EncodedPartitionFreelistEntryPtr {
EncodedPartitionFreelistEntryPtr将entry进行了一些编码转换。
ProvisionMoreSlotsAndAllocOne用来初始化一个slotspan。
PA_ALWAYS_INLINE uintptr_t
需要扩展的slot数目。
uintptr_t slot_span_start =
通过slot_span换算出第一个slot的内存地址。
PartitionFreelistEntry* prev_entry = nullptr;
循环调用SetNext填充下一个entry。
1.6 ThreadCache
每个线程有一个独立的ThreadCache，不需要上锁，以下是笔者提取出来的关键数据结构：
partition_allocator/thread_cache.h
线程通过RegisterThreadCache注册自己的cache结构， 每个线程的cache通过双向链表链接。
GetFromCache函数从线程的当前cache中选取一个slot出来。
PA_ALWAYS_INLINE uintptr_t ThreadCache::GetFromCache(size_t bucket_index,
直接从bucket.freelist_head取出当前空闲的entry地址，并设置下一个空闲的entry。
FillBucket函数填充cache的bucket对象。
void ThreadCache::FillBucket(size_t bucket_index) {
循环调用AllocFromBucket分配内存，调用PutInBucket填充进去。
PutInBucket函数将slot写入cache的buket对象里。
A_ALWAYS_INLINE void ThreadCache::PutInBucket(Bucket& bucket,
如果是x86_64架构，会将slot填充一些固定的posion值，防止UAF漏洞。作者在注释中说明只在cache中加入posion是为了提高性能。那么另一个问题arm64架构不使用cache posion的原因可能是内存大小问题了。
auto* entry = internal::PartitionFreelistEntry::EmplaceAndInitForThreadCache(
将slot写入bucket.freelist_head。
2 内存结构
2.1 DirectMapped
对于buckets数组中的内存块大小，PartitionAlloc根据其大小，可以直接使用叫做DirectMapped的技术，它要求待分配的内存大小不能超过2>>31 - 2mb大小，并且这部分内存直接使用mmap映射，使用ReservationOffsetTable对其进行引用。
partition_allocator/reservation_offset_table.h
offsets数组保存了一个DirectMapped内存块在对应的pool中的偏移。
PA_ALWAYS_INLINE uint16_t* GetReservationOffsetTable(pool_handle handle) {
每个DirectMapped内存块通过双向链表链接，保存在root->direct_map_list。
DirectMapped内存结构如下：
2.2 Normal Map
SlotSpan中的一个slot通过FromAddr函数可以转为对应的SlotSpanMetadata管理结构。
PA_ALWAYS_INLINE PartitionPage<thread_safe>*
3 内存分配算法
话不多说，直接上图：
最终分配好的object在内存中的结构为：
