​​Linux Memory Allocator Implementation Research

​​TODO

  • ​​描述memory allocator對於系統效能的重要性(舉例)
  • ​​Memory allocator設計上的考量指標
  • ​​前人實作過程累積的經驗
  • ​​分析比對幾種常用的allocator，所使用的演算法及資料結構
  • ​​在針對不同效能指標所設計的testbench上執行的實驗結果
​​

​​內容整理

​​Memory Allocator對系統效能的影響

​​記憶體分配表面上看起來是相當簡單的問題，但數十年來的研究卻仍未產出在各方面表現都制霸的單一allocator。尤其自多核心時代來臨後，許多研究致力於提升整體系統的scalibility，使其成為allocator設計上很重要的考量。Memory allocator若無法妥善利用多核環境提升效能，便會成為系統的效能瓶頸。
​​
​​"How Memory Allocation Affects Performance in Multithreaded Programs"這篇文章的作者做了簡單的實驗，想要量化memory allocator在scalibility表現上的差異。他觀察到在Oracle Solaris上，glibc malloc並未具備足夠的scalibility(多執行緒執行測試程式時有嚴重的lock contention)，隨後也比較了libc malloc和Hoard、umem、mtmalloc等allocator的scalibility，證實了效能差距在提高執行緒數量後，可以達到數十甚至上百倍之多。

​​Memory allocator設計上的考量指標

  1. ​​Fast allocation/deallocation
  • ​​快速的記憶體分配/釋出 
  • ​​減少lock contention
  1. ​​Memory layout facilitating fast access
  1. ​​Multicore scalability
  1. ​​Low Memory Consumption(Memory Reuse)
  1. ​​False sharing avoidance
  • ​​“Modern multi-processor systems preserve a coherent view of memory on a per-cache-line basis”
​​
 
User-uploaded image: file.png
​​

​​前人實作過程累積的經驗

​​

​​幾種常用Memory Allocator的設計分析

  1. ​​通常為了增進多執行緒環境中的效能，會使用thread-local allocation buffers(TLABs)，被稱作local frontend；而由global backend負責管理(和重複使用)記憶體
  1. ​​thread-local buffers每次只被分配或釋出一整塊(chunk)的記憶體空間，大小為system page size的整數倍，稱作spans/superblocks/SLABs/superpages
  1. ​​Span size大小的選擇: 越大的span size會降低分配span的頻率(因此增加allocation speed)，但同時也會增加整體記憶體使用量(因為只能將空的span回收至global backend)，面臨的是scalability和memory consumption的tradeoff。
  1. ​​Span size class的選擇: 擁有較多的size classes可以降低internal fragmentation，但在重複使用記憶體上，除了thread synchronization之外，需要付出額外的defragmentation成本(降低external fragmentation)，面臨的是thread coordination overhead和internal fragmentation的tradeoff
  1. ​​記憶體分配/回收通常由span處理，若物件需求空間太大的話會使用mmap/munmap

​​Scalloc

​​[設計理念]
  1. ​​以相同的手法處理large/small sized objects
  • ​​使用大小為2MB的virtual span​，virtual span裡面包含一個real span​(大小由size class決定)
  1. ​​有效率地回收記憶體
  • ​​Span-pool​  : 基於scalable concurrent data structures建立的global backend，在madvise​ 的協助之下回收記憶體（把超過某個大小的記憶體區塊標示為`MADV_DONTNEED` 
  1. ​​synchronization的時間成本為constant time
  1. ​​分為29個size class，前16個呈線性關係（16*1 ~ 16*16 bytes），剩下的以2的倍數成長（512 bytes ~ 1MB）；real span size則有9種
​​
​​[Arena - virtual span - real span的關係]
  • ​​Arena: 一塊極大的虛擬記憶體空間(32 TB = 2 ^ 45 bytes ＝ mmap記憶體量的上限)
  • ​​Virtual span: 在arena中佔有2MB的虛擬記憶體空間，內部含有一個real span
  • ​​Real span: 一段連續的實體記憶體空間，內部被分為多個相同大小(same size class)的區塊
​​
​​[使用virtual span的優點]
  1. ​​unmapped virtual memory不佔physical memory空間（應用了demand paging以及large virtual memory的特點），不會造成physical memory的fragmentation
  1. ​​不必一再以system call和系統要求記憶體空間，因為在一開始就直接mmap 32TB的空間給arena
​​
 
User-uploaded image: file.png
​​
​​[Backend - Span pool]