文章目錄
- 棧記憶體空間是否夠用
- 系統調用申請記憶體
- 最簡單的記憶體配置設定器實作 -- 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_startproc
pushq %rbp # 入棧
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq %rsp, %rbp # 添加棧底指針
.cfi_def_cfa_register 6
movl $10, -4(%rbp) # 變量a
movl $20, -8(%rbp) # 變量b
movl -4(%rbp), %edx
movl -8(%rbp), %eax
addl %edx, %eax
movl %eax, -12(%rbp) # 變量c
movl $0, %eax
popq %rbp # 出棧
.cfi_def_cfa 7, 8
ret
.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 – 運作庫檔案不能過大，它隻是一個記憶體配置設定庫
- …