Understanding glibc malloc

日志：

1. [2019-10-10] 經(jīng)評(píng)論 @kwdecsdn 提醒，新增對(duì)「Unsorted Bin 中的 chunks 何時(shí)移至 small/large chunk 中」的補(bǔ)充解釋。

2. [2019-02-06] 勘誤與代碼著色優(yōu)化；

3. [2018-05-22] 內(nèi)容優(yōu)化與排版優(yōu)化；

4. [2017-03-17] 優(yōu)化排版.

譯者言:

1. [2018-05-22] 在寫(xiě)完這篇博客之后，我抽空將 glibc malloc 的源碼閱讀了一遍，并參與編撰了一篇有關(guān)分配器的綜述文獻(xiàn)1，最后我動(dòng)手實(shí)現(xiàn)了自己的分配器。當(dāng)然，這都是 17 年暑期之前的工作了。一年后的今天，我打開(kāi)這篇藏在記憶角落里的文章，看著它驚人的點(diǎn)擊量，我覺(jué)得我有必要認(rèn)真地校準(zhǔn)一下本文，從而盡量為大家提供一篇內(nèi)容正確、閱讀舒適的博文，這樣才對(duì)得起大家的厚望。在修訂過(guò)程中，為了避免令人尷尬的翻譯腔，我會(huì)盡量意譯與技術(shù)無(wú)關(guān)的文本，希望大家喜歡！

2. [2016-07-21] 本篇文章主要完成了「Understanding glibc malloc」的翻譯工作。限于本人翻譯水平與專(zhuān)業(yè)技術(shù)水平（純粹為了了解內(nèi)存分配而翻），本文章必定會(huì)有很多不足之處，請(qǐng)大家見(jiàn)諒，也歡迎大家的指正！

文章目錄

• Understanding glibc malloc

• 5.1. Fast Bin

• 5.2. Unsorted Bin

• 5.3. Small Bin

• 5.4. Large Bin

• 5.5. Top Chunk

• 5.6. Last Remainder Chunk

• 4.1. Allocated chunk

• 4.2. Free chunk

• 3.1. Arena 的數(shù)量

• 3.2. Multiple Arena

• 3.3. Multiple Heaps

• 2.1. 案例代碼

• 2.2. 案例輸出

• 2.2.1. 在主線(xiàn)程 malloc 之前

• 2.2.2. 在主線(xiàn)程 malloc 之后

• 2.2.3. 在主線(xiàn)程 free 之后

• 2.2.4. 在 thread1 malloc 之前

• 2.2.5. 在 thread1 malloc 之后

• 2.2.6. 在 thread1 free 之后

• 前言

• 1. 申請(qǐng)堆的系統(tǒng)調(diào)用

• 2. 多線(xiàn)程支持

• 3. Arena

• 4. Chunk

• 5. Bins

• 
  

前言

堆內(nèi)存（Heap Memory）是一個(gè)很有意思的領(lǐng)域。你可能和我一樣，也困惑于下述問(wèn)題很久了：

• 如何從內(nèi)核申請(qǐng)堆內(nèi)存？

• 誰(shuí)管理它？?jī)?nèi)核、庫(kù)函數(shù)，還是應(yīng)用本身？

• 內(nèi)存管理效率怎么這么高？！

• 堆內(nèi)存的管理效率可以進(jìn)一步提高嗎？

最近，我終于有時(shí)間去深入了解這些問(wèn)題。下面就讓我來(lái)談?wù)勎业恼{(diào)研成果。

開(kāi)源社區(qū)公開(kāi)了很多現(xiàn)成的內(nèi)存分配器（Memory Allocators，以下簡(jiǎn)稱(chēng)為分配器）：

• dlmalloc – 第一個(gè)被廣泛使用的通用動(dòng)態(tài)內(nèi)存分配器；

• ptmalloc2 – glibc 內(nèi)置分配器的原型；

• jemalloc – FreeBSD ＆ Firefox 所用分配器；

• tcmalloc – Google 貢獻(xiàn)的分配器；

• libumem – Solaris 所用分配器；

• …

每一種分配器都宣稱(chēng)自己快（fast）、可拓展（scalable）、效率高（memory efficient）！但是并非所有的分配器都適用于我們的應(yīng)用。內(nèi)存吞吐量大（memory hungry）的應(yīng)用程序，其性能很大程度上取決于分配器的性能。

在這篇文章中，我只談「glibc malloc」分配器。為了方便大家理解「glibc malloc」，我會(huì)聯(lián)系最新的源代碼。

歷史：ptmalloc2 基于 dlmalloc 開(kāi)發(fā)，其引入了多線(xiàn)程支持，于 2006 年發(fā)布。發(fā)布之后，ptmalloc2 整合進(jìn)了 glibc 源碼，此后其所有修改都直接提交到了 glibc malloc 里。因此，ptmalloc2 的源碼和 glibc malloc 的源碼有很多不一致的地方。（譯者注：1996 年出現(xiàn)的 dlmalloc 只有一個(gè)主分配區(qū)，該分配區(qū)為所有線(xiàn)程所爭(zhēng)用，1997 年發(fā)布的 ptmalloc 在 dlmalloc 的基礎(chǔ)上引入了非主分配區(qū)的概念。）

1. 申請(qǐng)堆的系統(tǒng)調(diào)用

我在之前的文章中提到過(guò)，malloc?內(nèi)部通過(guò)?brk?或?mmap?系統(tǒng)調(diào)用向內(nèi)核申請(qǐng)堆區(qū)。

譯者注：在內(nèi)存管理領(lǐng)域，我們一般用「堆」指代用于分配動(dòng)態(tài)內(nèi)存的虛擬地址空間，而用「棧」指代用于分配靜態(tài)內(nèi)存的虛擬地址空間。具體到虛擬內(nèi)存布局（Memory Layout），堆維護(hù)在通過(guò)?brk?系統(tǒng)調(diào)用申請(qǐng)的「Heap」及通過(guò)?mmap?系統(tǒng)調(diào)用申請(qǐng)的「Memory Mapping Segment」中；而棧維護(hù)在通過(guò)匯編棧指令動(dòng)態(tài)調(diào)整的「Stack」中。在 Glibc 里，「Heap」用于分配較小的內(nèi)存及主線(xiàn)程使用的內(nèi)存。

下圖為 Linux 內(nèi)核 v2.6.7 之后，32 位模式下的虛擬內(nèi)存布局方式。

2. 多線(xiàn)程支持

Linux 的早期版本采用 dlmalloc 作為它的默認(rèn)分配器，但是因?yàn)?ptmalloc2 提供了多線(xiàn)程支持，所以 后來(lái) Linux 就轉(zhuǎn)而采用 ptmalloc2 了。多線(xiàn)程支持可以提升分配器的性能，進(jìn)而間接提升應(yīng)用的性能。

在 dlmalloc 中，當(dāng)兩個(gè)線(xiàn)程同時(shí)?malloc?時(shí)，只有一個(gè)線(xiàn)程能夠訪(fǎng)問(wèn)臨界區(qū)（critical section）——這是因?yàn)樗芯€(xiàn)程共享用以緩存已釋放內(nèi)存的「空閑列表數(shù)據(jù)結(jié)構(gòu)」（freelist data structure），所以使用 dlmalloc 的多線(xiàn)程應(yīng)用會(huì)在?malloc?上耗費(fèi)過(guò)多時(shí)間，從而導(dǎo)致整個(gè)應(yīng)用性能的下降。

在 ptmalloc2 中，當(dāng)兩個(gè)線(xiàn)程同時(shí)調(diào)用?malloc?時(shí)，內(nèi)存均會(huì)得以立即分配——每個(gè)線(xiàn)程都維護(hù)著單獨(dú)的堆，各個(gè)堆被獨(dú)立的空閑列表數(shù)據(jù)結(jié)構(gòu)管理，因此各個(gè)線(xiàn)程可以并發(fā)地從空閑列表數(shù)據(jù)結(jié)構(gòu)中申請(qǐng)內(nèi)存。這種為每個(gè)線(xiàn)程維護(hù)獨(dú)立堆與空閑列表數(shù)據(jù)結(jié)構(gòu)的行為就「per thread arena」。

2.1. 案例代碼

/* Per thread arena example. */#include #include #include #include #include
void* threadFunc(void* arg) { printf("Before malloc in thread 1\n"); getchar(); char* addr = (char*) malloc(1000); printf("After malloc and before free in thread 1\n"); getchar(); free(addr); printf("After free in thread 1\n"); getchar();}
int main() { pthread_t t1; void* s; int ret; char* addr;
printf("Welcome to per thread arena example::%d\n",getpid()); printf("Before malloc in main thread\n"); getchar(); addr = (char*) malloc(1000); printf("After malloc and before free in main thread\n"); getchar(); free(addr); printf("After free in main thread\n"); getchar(); ret = pthread_create(