前言

自從今年四月初參與ARRC的火箭開發計畫(見: http://www.arrc.tw/),和jserv、哲綱、東儒等人開始研究Realtime memory allocation之後也過了幾個月,覺得自己需要將累積的研究結果以更清楚的文字做個整理,一方面在過程中能夠消化、反芻收集到的資訊和實驗數據,另一方面也能給從事相關研究的人一點參考(建議可以先讀這篇Memory Allocators 101)。

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 allocation

在這邊提到的memory allocation指的是動態記憶體分配(例如C語言的malloc)。一般而言,在開發即時應用時,會盡量避免要求系統分配動態記憶體,NASA甚至在Rules for Developing Safety Critical Code第三點直接提到"開發者不得使用動態記憶體分配",理由是malloc和garbage collector可能產生未預期的行為而嚴重影響系統效能。然而因為某些開發上的因素,ARRC的火箭控制系統不得已必須使用動態記憶體分配。為了不讓它成為即時系統效能的拖油瓶,我們決定自己研究realtime memory allocation(另一個因素是找不到太多可以應用的研究)。預期能夠達到的目標有以下幾點:

  1. 避免out-of-memory (OOM)情況發生
  2. 達到thread safety
  3. 空間的運用更有效率
  4. 能夠即時記錄分析程式記憶體的分配情況
  5. 利用像是madvise()的方法提示Linux virtual memory 做出對應的回應

Memory allocator設計上的考量指標

在研讀各種memory allocator的紀錄文件時,可以發現不同的實作具有許多相同的設計目標,在此歸納做個整理:

1. Fast allocation/deallocation

第一點要求自然是能夠達到快速的記憶體分配/釋出,常見的作法有使用per-thread heap減少lock contention等。

2. Memory layout facilitating fast access

除了要能快速分配動態記憶體以外,分配出去的記憶體在使用上也要能快速地被存取(例如具有spatial locality)。

3. Multicore scalability

發揮多核心的優勢,在多執行緒環境下執行具有良好效能,並且減少協調的成本。

4. Low memory consumption (memory reuse)

降低記憶體的總使用量(增加所分配記憶體之使用率,等同於減低fragmentation),並且避免因為記憶體無法被回收利用,使得記憶體使用量不斷增長而造成的memory blowup [1]

5. False sharing avoidance

當多個核心同時存取同一個cache line裡面的資料時[2],即使使用的資料彼此並沒有重疊,為了確保cache line資料的一致性,當其中一個CPU上的thread修改它的資料時,另外一個CPU的cache也要被更新。此現象被稱作false sharing (可見以下示意圖),allocator設計上應減少此種情況發生。

幾種常見的Memory Allocator設計準則

  1. 通常為了增進多執行緒環境中的效能,memory allocator會使用thread-local allocation buffers(TLABs)分散處理記憶體的分配/回收,這部分被稱作local frontend;此外再經由global backend向系統要求記憶體,並分配給frontend。
  2. thread-local buffers每次只被分配或釋出一整塊的記憶體空間,大小為system page size的整數倍,稱作spans/superblocks/SLABs/superpages
  3. Span size大小的選擇: 越大的span size會降低分配span的頻率(因此增加allocation speed),但同時也會增加整體記憶體使用量(因為只能將空的span回收至global backend),面臨的是scalability和memory consumption的tradeoff。
  4. Span size class的選擇: 擁有較多的size classes可以降低internal fragmentation(因為切得比較細),但在重複使用記憶體上,除了thread synchronization之外,需要付出額外的defragmentation成本(降低external fragmentation),面臨的是thread coordination overhead和internal fragmentation的tradeoff
  5. 記憶體分配/回收通常以span作為單位,若需求空間太大的話才會使用mmap/munmap

Memory Allocator實作分析

以下介紹幾種比較常用的malloc implementation,主要會針對以下五個設計的重點進行說明:

  1. 如何依照memory request的大小用不同的方式分配/回收記憶體;size classes的大小及間隔
  2. Global backend: 如何向系統要記憶體空間,以及如何和前端互動
  3. Frontend: thread-local allocation buffers如何處理memory request
  4. Span的大小以及metadata如何紀錄以供管理
  5. 如何管理(再利用)被釋放的記憶體以及freelist的結構

此外也會對比較特殊的設計想法另作闡述。

ptmalloc (ptmalloc2)

ptmalloc為目前glibc malloc的實作,雖然表現比起許多其他的實作遜色不少,但是部分設計概念還是可在其他實作中見到,像是

  1. 將memory request依照大小區分成幾種不同的case處理
  2. 提供多個thread local buffers(稱作per-thread arena)
  3. 一次向系統要求一至多個固定大小記憶體空間(稱作chunk)
  4. 藉由freelist data structure管理可被分配的記憶體區塊

[Chunks & bins]
Chunk是ptmalloc中直接用來分配或正在使用中的記憶體區塊,其狀態可分為allocated與free兩種

Bin則是紀錄free chunks的資料結構(freelist),依據其大小和特性分成四種 :Fast bin / unsorted bin / small bin / large bin。

 

[Main arena & thread arenas]

ptmalloc以brk()或者mmap()系統呼叫替backend從系統取得大塊的記憶體區域,稱為arena。
Arena再被分割成多個chunks來滿足memory request,並分為main arena與thread arena兩種。
 
Main thread一開始所使用的arena被稱為main arena。為了增加scalibility,ptmalloc在多執行緒時提供數個thread arenas,每個thread在呼叫malloc()時會分配到一個arena,但是thread arena有數量限制,超過限制時threads會開始共用arena。
[Memory request size]

ptmallocc有幾種分配記憶體方式,依照malloc()記憶體需求參數的大小決定使用哪種

  • Fast chucks(<= 64 bytes) : caching allocation,保留一系列固定大小區塊的list以利迅速回收再使用 no coalescing
  • Large chunks(>= 512 bytes) : 使用best-fit的策略,在一個range(bin)的list中尋找
  • Small chunks
  • 在兩者之間 : 試著結合兩種方法,有每個size的list(小的特性),也有合併(coalesce)機制、double linked list(大)
  • Huge chunks(>= 128KB by default) : 直接使用mmap(),讓memory management解決

Hoard

Hoard是2000年左右開發出來的memory allocator,當時memory allocation經常是多處理器系統的效能瓶頸。Hoard設計上的重點如下:

  1. 使用一個global heap和多個per-processor heap,每個thread只能直接使用自己per-processor heap上面的記憶體;當 per-processor heap 空間不夠再從global heap獲取一個superblock的空間。
  2. 紀錄記憶體的使用情況(per-processor heap使用的記憶體量和per-processor heap被分配的記憶體量),作為記憶體分配/收回的決策參考
  3. 因為fragmentation和記憶體的(再)使用率有正向關係,因此將其操作型定義為”使用的記憶體空間”和”分配到的記憶體空間”之比值
  4. 在每次執行free() 的時候會檢查per-processor heap沒有被使用的記憶體空間比例和總量是否超過特定值(empty fraction f和K*S),若有則將使用率最低的superblock歸還給global heap,如此一來可確保

Hoard藉由使用per-processor heap能夠增加scalability以及降低cache line false sharing的情況發生;此外其回收記憶體的策略(在論文中以數學證明)讓worst-case memory consumption只比所需空間多出constant factor overhead。

TCMalloc

Google使用的malloc實作,它讓每個thread擁有自己的thread caches,以lockless的方式處理小物件的分配,讓lock contention降低至近乎不發生。此外也解決ptmalloc無法將物件在per-thread arena之間移動的問題,並且在小物件的處理上,具有比較小的spatial overhead。

[small object allocation]

TCMalloc將空間的分配以small/large object size作區分: 對於small request(小於32kB,TCMalloc擁有86個size classes),一般直接從thread cache中相對應size class的freelist分配(稱作fastpath)。若thread cache沒有可用的block,再向central cache要空間;假如連central cache都沒有可分配空間的話,再向page heap一次要求多個page的空間。


[Large object allocation]

大於32kB的記憶體分配則交由page heap處理。Page heap實際上是個freelist陣列,大小為256,每個entry連結到某個freelist的開頭,其中的block size為k pages(1 <= k <= 255),最後一個entry指向剩餘比256-page block還大的記憶體區塊。

TCMalloc在分配大空間時會到大小最適當的freelist搜尋,若此freelist為空則找下一個freelist,直到找到足夠大小的記憶體區塊(此區塊剩餘的空間會被加入另一個freelist)。假如連page heap第256個entry都沒有足夠的空間,會使用系統呼叫要求記憶體。

 

jemalloc

為FreeBSD和NetBSD預設的malloc實作,並且被使用在Mozilla Firefox和Facebook上。它和TCMalloc類似,也採用了thread-local buffer,並且將分配出去的空間以大小分成三類,每一類底下再細分成多個size classes:

Small:[8], [16, 32, 48, …, 128], [192, 256, 320, …, 512], [768, 1024, 1280, …, 3840]

Large:[4 KiB, 8 KiB, 12 KiB, …, 4072 KiB]

Huge:[4 MiB, 8 MiB, 12 MiB, …]

jemalloc把arena當中的每個chunk切割成多個run,分配到各size class的bin(freelist)裡面。每個run裡面會以bitmap紀錄分配狀態(節省空間);每個bin內部則使用兩個紅黑樹(clean: 未被分配過,dirty: 被回收的區塊) 來管理可被分配的空閒區塊。

Scalloc

Scalloc是來自奧地利的cksystemsgroup,在2015年OOPSLA conference發表的研究成果。除了承襲以往allocator設計的概念如thread-local allocation buffer、size classes等等,也引入virtual span的想法: 利用demand paging以及64-bit virtual memory夠大的特點 [3],以相同的手法處理large/small sized objects [4] ,簡化設計的複雜度。除此之外,它在backend使用concurrent data structure以及madvise來有效地管理記憶體,而frontend則積極歸還被釋放的記憶體以提升效能。以下針對virtual span、backend/frontend的設計,再做更進一步的解說。

[Arena – virtual span – real span的關係]
  • Arena: scalloc初始化時,會進行一次32TB的mmap,這塊極大的虛擬記憶體空間
  • Virtual span: 在arena中佔有2MB的虛擬記憶體空間,內部含有一個real span
  • Real span: 一段連續的實體記憶體空間,內部被分為多個相同大小(same size class)的區塊

[Global backend: spanpool]

Span-pool  : 基於scalable concurrent data structures建立的global backend,在madvise 的協助之下回收記憶體(把超過某個大小的記憶體區塊標示為MADV_DONTNEED)

[Constant-time frontend: allocation & deallocation]

span可以有幾種不同的狀態 :

span可以是以下其中之一 : expected, free, hot, floating, reusable。
  • expected : 仍在arena,不占任何實體記憶體的狀態
  • free : 在span-pool中等待使用的狀態
其他3種狀態皆在frontend,且span此時有所屬的span size
  • hot : 正在用來malloc的span,在local buffer內每size class一個
  • floating : 內含free block在reusability threshold以下者
  • reusable : 內含free block在reusability threshold以上,可以在hot填滿時替換

結論

這篇文章只是將我們要處理的問題以及幾個memory allocator做個簡短介紹。之後可能會將所收集的benchmark suites以及實驗結果等做個整理。

 

研究紀錄

[hackpad] Real-time Linux 研究: Memory Allocation
[Dropbox paper] Linux Memory Allocator Implementation Research

參考資料

How Memory Allocation Affects Performance in Multithreaded Programs

Scalloc (2015)
TCMalloc (2007)
jemalloc (2006)
TLSF

註解

[1] 在某些情況下,在thread A被分配的空間會由thread B釋放(稱作remotely-freed objects),而有些memory allocator無法回收這些空間。Paul Larson將此種分配-釋放模式稱作producer-consumer pattern,也設計了相對應的benchmark
[2] “Modern multi-processor systems preserve a coherent view of memory on a per-cache-line basis”, page 2, A Scalable Concurrent malloc (3) Implementation for FreeBSD
[3] Unmapped virtual memory不佔physical memory空間,不會造成physical memory的fragmentation。
[4] 通常memory allocator會將分配出去的object分成small/large/huge三種等級,small和large objects的分配由allocator的演算法決定,huge objects則直接呼叫mmap()系統呼叫。
[5] 32-bit system: 2 * number of cores; 64-bit system: 8 * number of cores
[6] 可參考Linux system programming第八章memory management
Advertisements

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s