内存分配器设计的演进
文章目錄
- 棧內存空間是否夠用
- 系統調用申請內存
- 最簡單的內存分配器實現 -- bump allocator
- 可擴容的 Bump alloactor
- 通過free-list 管理的 allocator
- 通過size-buckets 維護多個free-list 的 allocator
- Cache friendly allocator
- 需要考慮更多問題的allocator
- 性能
- 易用性
本文希望描述一個基本的內存分配器的設計演進，包括基于ptmalloc 實現的glibc-malloc ，jemalloc 以及 tcmalloc 為什么會被設計成如今的樣子（他們的基本形態都是非常接近的，無非tcmalloc 比 jemalloc和glibc-malloc 多了一些內存高效利用上的設計）
在沒有內存分配器的時候，我們os系統最開始的時候擁有自己的棧空間，用來保存函數棧以及內部的變量，大家先拋開我們習慣用的malloc/free 以及 new/delete，來整體看看內存分配器的演進過程，本文更多的是一些設計上的思考。
棧內存空間是否夠用
如下代碼提就是一個棧空間的基本數據存儲。
#include <stdio.h>int main() {int a = 10;int b = 20;int c = a + b;return 0;
}
在編譯生成的匯編代碼中，我們可以看到對于變量 a 和 b的處理，其所占用的內存大小已經被分配好。10這個數值被填充到了代表a的棧底指針減去4字節之后的地址-4%(rbp)，同理20 被填充到了棧底指針減去 8字節之后的地址-8(%rbp)。
可以看到，編譯期間，變量a,b 以及最后的c 都已經明確了具體的存儲空間的大小以及存儲對應的虛擬地址。
.file "stack.c".text.globl main.type main, @function
main:
.LFB0:.cfi_startprocpushq %rbp # 入棧.cfi_def_cfa_offset 16.cfi_offset 6, -16movq %rsp, %rbp # 添加棧底指針.cfi_def_cfa_register 6movl $10, -4(%rbp) # 變量amovl $20, -8(%rbp) # 變量bmovl -4(%rbp), %edxmovl -8(%rbp), %eaxaddl %edx, %eaxmovl %eax, -12(%rbp) # 變量cmovl $0, %eaxpopq %rbp # 出棧.cfi_def_cfa 7, 8ret.cfi_endproc
.LFE0:.size main, .-main.ident "GCC: (GNU) 7.3.1 20180303 (Red Hat 7.3.1-5)".section .note.GNU-stack,"",@progbits棧內存分配基本優劣如下：
優勢:
- Automacitcally handled by the compiler，編譯器會編譯期間分配好對應的棧內存
- very fast allocation 擁有對應的cpu指令來專門處理棧內存的分配
- very fast cleanup 釋放的時候也擁有對應的指令（函數棧彈棧）
劣勢:
- fixed sizes，內存大小需要是已知的，內存大小有限，比如x86_64 系統下默認的棧空間只有10M(
ulimit -s) - fixed lifetimes : 作用域僅僅被限制在了當前函數內部。比如，想要在一個函數內部創建一個鏈表并返回，是完全不可能的。
棧內存對于我們應用程序的使用場景來說顯然還是不夠，那有沒有可以直接分配內存的系統調用？
系統調用申請內存
mmap ： 設置內存protection(mmap的內存區域可以被當前進程的其他程序更改)，頻繁的中斷 以及 會陷入內核；釋放的時候unmap即可。
Mmap 解決了 棧方式分配內存的 fixed-sizes 的問題，用戶可以不限制內存大小來分配內存。
- 整體非常慢，頻繁得觸發page fault 中斷并使當前進程陷入內核。
- 浪費內存較為嚴重。因為申請內存的粒度只能是4K的page，在一些應用場景中對內存浪費較為嚴重(申請8byte的區域，創建一個鏈表節點，需要消耗4k的內存)。
Mmap 并不能作為構造一個高效可靠的內存分配器的雛形，接下來還需要做更多的工作來對內存進行管理。
那我們想像這樣一個簡單的內存分配器，就是先模擬棧空間進行內存分配，取一個定長的內存區域被用來存儲數據，分配的過程可以根據用戶的需求來分配。
最簡單的內存分配器實現 – bump allocator
bump allocator，類似一個用戶棧空間（不用 os 自己的進程棧空間）。
用戶申請一個內存區域，則將申請的這個內存對象入棧。這個棧空間管理的內存能夠控制變量的生存周期，只有當你從棧中移除這個內存對象的時候，這個內存對象的生命周期才算結束。
優勢：
- 高性能，fast allocation
- 變量的存儲生命周期可控
缺點：
- fixed total memory，需要開辟一段固定大小的內存。
- cannot free memory： 這個含義其實是說，因為使用的是棧空間管理的內存，想要釋放最開始申請額8 bytes 的存儲空間，需要先釋放掉在 8之上的其他內存對象，這個時候其他的內存對象對于應用程序來說并不一定想要釋放。
問題很明顯，還是和傳統的函數棧空間一樣 fixed total memory 以及 無法快速釋放內存。
可擴容的 Bump alloactor
那我們先來通過expandable memory 來解決 fixed total memory的問題。
當用戶程序耗盡了第一次申請的內存區域，則分配一個新的 內存區域用于用戶申請（內存管理的arena機制），已經滿的內存區域則保留，直到用戶想要從棧頂釋放內存。
優勢：
- Fast allocation
- expandable total memory
- manual lifetime
劣勢：
- cannot free memory，仍然無法有效釋放內存，需要先彈棧，才能找到需要釋放的內存對象。
通過free-list 管理的 allocator
free-list，通過一些元數據來管理內存空間，比如使用鏈表，將應用程序申請的內存對象通過鏈表串聯起來， 如果用戶想要釋放一個變量，則釋放這個變量對應內存的單鏈表節點即可。
現在free memory終于可以隨意進行了，能夠隨意申請，隨意釋放，不會受內存大小的限制，這樣看起來功能確實沒有問題了。
可是我們還需要性能 以及 成本，，，
劣勢：
- allocations have minium sizes，一個鏈表指針在64位系統下需要8byte的存儲空間，表示每次申請至少需要8byte的存儲空間 管理free-list 的節點。
- very slow (釋放的時候，可以隨意釋放任何一個節點，只是需要從頭順序掃描整個鏈表，代價很高）
- memory fragmentation 內存碎片，整個內存空間在大內存和小內存對象混合在一起的時候無法有效管理小內存。比如一個鏈表節點大小最小是8bytes，用戶申請了一個1byte 和 一個 7bytes的存儲空間，這個時候需要至少16bytes的存儲，1byte 對應的存儲區域會有一個7bytes的內存碎片一直無法被使用。
這樣的性能 以及 對成本這樣的浪費，簡直不能忍，繼續向下看。
通過size-buckets 維護多個free-list 的 allocator
每一個size（不太可能每一個size 一個free-list，不易維護） 或者 一批 size 維護一個自己的free-list，這樣當前free-list 只需要存儲大小接近的內存對象就可以了，內存碎片問題會被極大的降低。
且釋放內存的時候不需要掃描整個混合在一起的大鏈表，掃描被均分到不同的size buckets。
優勢：
- 在前面的基礎上能夠正常釋放內存
- 解決了掃描慢的問題（釋放時不需要掃描整個大鏈表，只需要掃描對應的size-buckets 的鏈表即可）
- 內存碎片問題（通過按照size 來劃分free list，有效得降低了內存碎片）
劣勢：
- Cache pressure ；在高并發下分配內存的過程中頻繁的cache-miss 會導致cpu 的負載較高。cpu 需要頻繁得在不同的size-buckets 下進行切換，無法保持良好的cache命中（每次遍歷都需要重新load 內存到cpu-cache，鏈表的訪問本身是隨機訪問，加上不同的size-buckets 的訪問，都會導致cpu cache-miss較高）。
Cache friendly allocator
slab allocator，每一個size維護一個slab，這個 slab只需要管理當前size 的內存分配即可。
解決了cpu 對鏈表數據的隨機訪問的影響， 每一個slab 內部使用數組來管理內存對象，數組對cpu-cache 更友好。
每一個slab 能夠管理一批連續的內存空間，內存在slab上的分布連續性較強。
這個連續性肯定是相比于鏈表的隨機訪問來說的，在slab上盡可能連續的分配當前size，釋放的時候能夠盡可能得降低cache miss，減少cpu-cache 的壓力。
到此，我們有了一個功能齊全，性能還不錯的內存分配器的概要設計，但這只是單線程場景的內存分配器。想要實現一個工業級的內存分配器，還有更多的問題需要去考慮。
需要考慮更多問題的allocator
性能
- Alignment。盡可能對齊cache-line，來保證cpu 訪問的性能
- Multi-Thread / Multi-core 下的性能，比如jemalloc 和 tcmalloc 設計的 thread-cache / per-cpu cache等
易用性
- C compatibility – 兼容c語言的malloc/free等，想要支持 C++，這需要支持 operator new/delete
- Debugging，需要能夠暴露內部狀態，方便debug或者用戶查看內存占用情況
- Binary size – 運行庫文件不能過大，它只是一個內存分配庫
- …
這也就是jemalloc/tcmalloc/glibc-malloc 為什么如此通用的原因，因為其實現過程是在功能/性能/成本之間的trade-off，且這個trade-off 達到了極致，被工業界認可。
總結
以上是生活随笔為你收集整理的内存分配器设计的演进的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： TCMalloc(Thread-Cach
- 下一篇： 上海欢乐谷万圣节化妆在哪