前篇《探秘C++內(nèi)存管理（理論篇）》主要介紹了Linux C++程序內(nèi)存管理的理論基礎(chǔ)，本文作為系列文章《探秘C++內(nèi)存管理》的第二篇，將會探討經(jīng)典內(nèi)存管理器ptmalloc如何管理C++程序的內(nèi)存。借助剖析ptmalloc解決問題的著重點和設(shè)計實現(xiàn)成本的權(quán)衡，更具體的呈現(xiàn)c++內(nèi)存管理面臨的問題和工程落地中的巧思。

一、概述

GEEK TALK

ptmalloc是開源GNU C Library(glibc)默認(rèn)的內(nèi)存管理器，當(dāng)前大部分Linux服務(wù)端程序使用的是ptmalloc提供的malloc/free系列函數(shù)，而它在性能上遠(yuǎn)差于Meta的jemalloc和Google的tcmalloc。服務(wù)端程序調(diào)用ptmalloc提供的malloc/free函數(shù)申請和釋放內(nèi)存，ptmalloc提供對內(nèi)存的集中管理，以盡可能達(dá)到：

用戶申請和釋放內(nèi)存更加高效，避免多線程申請內(nèi)存并發(fā)和加鎖

尋求與操作系統(tǒng)交互過程中內(nèi)存占用和malloc/free性能消耗的平衡點，降低內(nèi)存碎片化，不頻繁調(diào)用系統(tǒng)調(diào)用函數(shù)

簡單概括ptmalloc的內(nèi)存管理策略：

預(yù)先向操作系統(tǒng)申請并持有一塊內(nèi)存供用戶malloc，同時管理已使用和空閑的內(nèi)存

用戶執(zhí)行free，會將回收的內(nèi)存管理起來，并執(zhí)行管理策略決定是否交還給操作系統(tǒng)

接下來，將從ptmalloc數(shù)據(jù)結(jié)構(gòu)、內(nèi)存分配及優(yōu)缺點介紹最經(jīng)典的c++內(nèi)存管理器的實現(xiàn)和使用（以32位機為例）。

二、內(nèi)存管理

GEEK TALK

2.1 數(shù)據(jù)結(jié)構(gòu)

為了解決多線程鎖爭奪問題，將內(nèi)存分配區(qū)分為主分配區(qū)(main_area)和非主分配區(qū)(no_main_area)。同時，為了便于管理內(nèi)存，對預(yù)申請的內(nèi)存采用邊界標(biāo)記法劃分成很多塊(chunk)；ptmalloc內(nèi)存分配器中，malloc_chunk是基本組織單元，用于管理不同類型的chunk，功能和大小相近的chunk串聯(lián)成鏈表，被稱為一個bin。

main_arena與non_main_arena

主分配區(qū)和非主分配區(qū)形成一個環(huán)形鏈表進行管理， 每一個分配區(qū)利用互斥鎖實現(xiàn)線程對該分配區(qū)的訪問互斥。每個進程只有一個主分配區(qū)，但允許有多個非主分配區(qū)，且非主分配區(qū)的數(shù)量只增加不減少。主分配區(qū)可以訪問進程的heap區(qū)域和mmap映射區(qū)域，即主分配區(qū)可以使用sbrk()和mmap()分配內(nèi)存；非主分配區(qū)只能使用mmap()分配內(nèi)存。

對于不同arena的管理策略大致如下：

分配內(nèi)存

查看該線程的私有變量中是否已經(jīng)存在一個分配區(qū)并對其進行加鎖操作，如果加鎖成功，則使用該分配區(qū)分配內(nèi)存；如果未找到該分區(qū)或加鎖失敗，遍歷環(huán)形鏈表中獲取一個未加鎖的分配區(qū)

如果整個環(huán)形鏈表中沒有未加鎖的分配區(qū)，開辟一個新的分配區(qū)，將其加入循環(huán)鏈表并加鎖，使用該分配區(qū)滿足當(dāng)前線程的內(nèi)存分配

釋放內(nèi)存

先獲取待釋放內(nèi)存塊所在的分配區(qū)的鎖，如果有其他線程正在使用該分配區(qū)，等待其他線程釋放該分配區(qū)互斥鎖后，再釋放內(nèi)存

主分配區(qū)和非主分配區(qū)的結(jié)構(gòu)如下：

其中fastbinsY和bins是對實際內(nèi)存塊的管理和操作結(jié)構(gòu)：

fastbinsY:用以保存fast bins

bins[NBINS * 2 - 2]:unsorted bin（1個，bin[1]）、small bins（62 個，bin[2]~bin[63]）、large bins（63 個，bin[64]~bin[126]）的集合，一共有 126 個表項(NBINS = 128)，bin[0] 和 bin[127] 沒有被使用

malloc_chunk與bins

ptmalloc統(tǒng)一管理heap和mmap映射區(qū)域中空閑的chunk，當(dāng)用戶進行分配請求時，會先試圖在空閑的chunk中查找和分割，從而避免頻繁的系統(tǒng)調(diào)用，降低內(nèi)存分配的開銷。為了更好的管理和查找空閑chunk，在預(yù)分配的空間的前后添加了必要的控制信息，內(nèi)存管理結(jié)構(gòu)malloc_chunk的成員及作用如下：

mchunk_prev_size: 前一個空閑chunk的大小

mchunk_size: 當(dāng)前chunk的大小

必要的屬性標(biāo)志位：

前一個chunk在使用中(P = 1)

當(dāng)前chunk是mmap映射區(qū)域分配(M = 1)或是heap區(qū)域分配(M = 0)

當(dāng)前chunk屬于非主分配區(qū)(A = 0)或非主分配區(qū)(A = 1)

fd和bk: chunk塊空閑時存在，用于將空閑chunk塊加入到空閑chunk塊鏈表中統(tǒng)一管理

基于chunk的大小和使用方法，劃分出以下幾種bins：

fast bins

fast bins僅保存很小的堆，采用單鏈表串聯(lián)，增刪chunk都發(fā)生在鏈表的頭部，進一步提高小內(nèi)存的分配效率。fast bins記錄著大小以8字節(jié)遞增的bin鏈表，一般不會和其他堆塊合并。

unsorted bin

small bins和large bins的緩沖區(qū)，用于加快分配的速度，chunk大小無尺寸限制，用戶釋放的堆塊，會先進入unsorted bin。分配堆塊時，會優(yōu)先檢查unsorted bin鏈表中是否存在合適的堆塊，并進行切割并返回。

small bins

保存大小 < 512B的chunk的bin被稱為small bins。small bins每個bin之間相差8個字節(jié)，同一個small bin中的chunk具有相同大小，采用雙向循環(huán)鏈表串聯(lián)。

large bins

保存大小 >= 512B的chunk的bin被稱為large bins。large bins中的每一個bin分別包含了一個給定范圍內(nèi)的chunk，其中的chunk按大小降序，相同大小按時間降序。

當(dāng)然，并不是所有chunk都按上述的方式來組織，其他常用的chunk，如：

top chunk: 分配區(qū)的頂部空閑內(nèi)存，當(dāng)bins不能滿足內(nèi)存分配要求的時候，會嘗試在top chunk分配。

當(dāng)top chunk > 用戶請求大小，top chunk會分為兩個部分：用戶請求大小(user chunk)和剩余top chunk大小(remainder chunk)

當(dāng)top chunk < 用戶所請求大小，top chunk就通過sbrk（main_arena）或mmap（non_main_arena）系統(tǒng)調(diào)用來擴容

2.2內(nèi)存分配與釋放

概括內(nèi)存malloc和free的流程大致如下：

內(nèi)存分配malloc流程

1、獲取分配區(qū)的鎖

2、計算出需要分配的內(nèi)存的chunk實際大小

3、如果chunk的大小 < max_fast，在fast bins上查找適合的chunk；如果不存在，轉(zhuǎn)到5

4、如果chunk大小 < 512B，從small bins上去查找chunk，如果存在，分配結(jié)束

5、需要分配的是一塊大的內(nèi)存，或者small bins中找不到chunk：

a.遍歷fast bins，合并相鄰的chunk，并鏈接到unsorted bin中

b.遍歷unsorted bin中的chunk：

-能夠切割chunk直接分配，分配結(jié)束

-根據(jù)chunk的空間大小將其放入small bins或是large bins中，遍歷完成后，轉(zhuǎn)到6

6、需要分配的是一塊大的內(nèi)存，或者small bins和unsorted bin中都找不到合適的 chunk，且fast bins和unsorted bin中所有的chunk已清除：

從large bins中查找，反向遍歷鏈表，直到找到第一個大小大于待分配的chunk進行切割，余下放入unsorted bin，分配結(jié)束

7、檢索fast bins和bins沒有找到合適的chunk，判斷top chunk大小是否滿足所需chunk的大小，從top chunk中分配

8、top chunk不能滿足需求，需要擴大top chunk：

a.主分區(qū)上，如果分配的內(nèi)存 < 分配閾值（默認(rèn)128KB），使用brk()分配；如果分配的內(nèi)存 > 分配閾值，使用mmap分配

b.非主分區(qū)上，使用mmap來分配一塊內(nèi)存

內(nèi)存釋放free流程

1、獲取分配區(qū)的鎖

2、如果free的是空指針，返回

3、如果當(dāng)前chunk是mmap映射區(qū)域映射的內(nèi)存，調(diào)用munmap()釋放內(nèi)存

4、如果chunk與top chunk相鄰，直接與top chunk合并，轉(zhuǎn)到8

5、如果chunk的大小 > max_fast，放入unsorted bin，并且檢查是否有合并：

a.沒有合并情況則free

b.有合并情況并且和top chunk相鄰，轉(zhuǎn)到8

6、如果chunk的大小 < max_fast，放入fast bin，并且檢查是否有合并：

a.fast bin并沒有改變chunk的狀態(tài)，沒有合并情況則free

b.有合并情況，轉(zhuǎn)到7

7、在fast bin，如果相鄰chunk空閑，則將這兩個chunk合并，放入unsorted bin。如果合并后的大小 > 64KB，會觸發(fā)進行fast bins的合并操作，fast bins中的chunk將被遍歷合并，合并后的chunk會被放到unsorted bin中。合并后的chunk和top chunk相鄰，則會合并到top chunk中，轉(zhuǎn)到8

8.如果top chunk的大小 > mmap收縮閾值（默認(rèn)為128KB），對于主分配區(qū)，會試圖歸還top chunk中的一部分給操作系統(tǒng)

三、優(yōu)缺點

GEEK TALK

ptmalloc作為glibc默認(rèn)的內(nèi)存管理器，已經(jīng)廣泛的滿足大多數(shù)大型項目的內(nèi)存管理，同時它的實現(xiàn)思路也對后來的內(nèi)存管理器提供了借鑒。

ptmalloc的介紹暫告一段落，接下來的幾篇文章將繼續(xù)探討高性能內(nèi)存管理庫的集大成者——jemalloc、tcmalloc內(nèi)存管理庫。

審核編輯 ：李倩