虛擬機內存管理之內存分配器

小編：本文由 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 。

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.
};

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 檢測機制，一方面可以檢測內存踩踏和多次釋放，另一方面也阻止了野指針的訪問。

 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;
};

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 內存分配核心流程如下所示。

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 返回。

以上介紹了內存分配的大致流程，內存釋放可以按照上述流程做反向數據流推演，不再詳細展開 (對 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-list

Slot 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 方面提供一些總結和參考。

FRr08M

Benchmark alternate malloc implementations:

https://expertmiami.blogspot.com/2019/05/what-is-scudo-hardened-allocator_10.html

KdqE4B

6. Rererence

[1]. A Tale of Two Mallocs: On Android libc Allocators – Part 1–dlmalloc https://blog.nsogroup.com/a-tale-of-two-mallocs-on-android-libc-allocators-part-1-dlmalloc/

[2]. jemalloc: https://github.com/jemalloc/jemalloc/blob/dev/INSTALL.md

[3]. A Tale of Two Mallocs: On Android libc Allocators – Part 2–jemalloc: https://blog.nsogroup.com/a-tale-of-two-mallocs-on-android-libc-allocators-part-2-jemalloc/

[4] AndroidConfig: https://android.googlesource.com/platform/external/scudo/+/refs/tags/android-11.0.0_r3/standalone/allocator_config.h#39

[5]. SizeClassAllocator64_: https://android.googlesource.com/platform/external/scudo/+/refs/tags/android-11.0.0_r3/standalone/primary64.h#46_

[6]. AndroidSizeClassConfig:
https://android.googlesource.com/platform/external/scudo/+/refs/tags/android-11.0.0_r3/standalone/size_class_map.h#171

[7]. Chunk: https://android.googlesource.com/platform/external/scudo/+/refs/tags/android-11.0.0_r3/standalone/chunk.h#65

[8] MapAllocator : https://android.googlesource.com/platform/external/scudo/+/refs/tags/android-11.0.0_r3/standalone/secondary.h#225

[9] scudo_allocator :https://github.com/llvm/llvm-project/blob/main/compiler-rt/lib/scudo/scudo_allocator.h

[10] standalone: https://github.com/llvm/llvm-project/blob/main/compiler-rt/lib/scudo/standalone/combined.h

[11]. Scudo : https://source.android.com/devices/tech/debug/scudo

[12]. Scudo Hardened Allocator: https://llvm.org/docs/ScudoHardenedAllocator.html

[13]. System hardening in Android 11: https://android-developers.googleblog.com/2020/06/system-hardening-in-android-11.html

[14]. Android Native | Scudo 內存分配器: https://juejin.cn/post/6914550038140026887

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

[16]. Efficient And Safe Allocations Everywhere! : https://blog.chromium.org/2021/04/efficient-and-safe-allocations-everywhere.html

[17]. PartitionAlloc Design: https://chromium.googlesource.com/chromium/src/+/master/base/allocator/partition_allocator/PartitionAlloc.md

[18]. partition_alloc_constants: https://source.chromium.org/chromium/chromium/src/+/main:base/allocator/partition_allocator/partition_alloc_constants.h

[19]. Unified allocator shim: https://chromium.googlesource.com/chromium/src/base/+/refs/heads/main/allocator/README.md

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

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/u2e4ZPfJf3fxbn8ufjRl8Q

1. dlmalloc [1]

* Key Points (salient points)

* Weaknessd

2. jemalloc (Android 5.0.0 ~)

* Key Points (salient points)

* Summary

3. scudo (Android 11 ~)

* Key Points (salient points)

* Summary

4. PartitionAlloc

* Key Points (salient points)

* Summary

5. Overview

6. Rererence

猜你喜歡