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

一、概述

GEEK TALK

ptmalloc是開(kāi)源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ù)申請(qǐng)和釋放內(nèi)存，ptmalloc提供對(duì)內(nèi)存的集中管理，以盡可能達(dá)到：

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

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

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

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

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

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

二、內(nèi)存管理

GEEK TALK

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

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

main_arena與non_main_arena

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

對(duì)于不同arena的管理策略大致如下：

分配內(nèi)存

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

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

釋放內(nèi)存

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

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

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

fastbinsY:用以保存fast bins

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

malloc_chunk與bins

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

mchunk_prev_size: 前一個(gè)空閑chunk的大小

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

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

前一個(gè)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塊空閑時(shí)存在，用于將空閑chunk塊加入到空閑chunk塊鏈表中統(tǒng)一管理

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

fast bins

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

unsorted bin

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

small bins

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

large bins

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

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

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

當(dāng)top chunk > 用戶(hù)請(qǐng)求大小，top chunk會(huì)分為兩個(gè)部分：用戶(hù)請(qǐng)求大小(user chunk)和剩余top chunk大小(remainder chunk)

當(dāng)top chunk < 用戶(hù)所請(qǐng)求大小，top chunk就通過(guò)sbrk（main_arena）或mmap（non_main_arena）系統(tǒng)調(diào)用來(lái)擴(kuò)容

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

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

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

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

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

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中查找，反向遍歷鏈表，直到找到第一個(gè)大小大于待分配的chunk進(jìn)行切割，余下放入unsorted bin，分配結(jié)束

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

8、top chunk不能滿(mǎn)足需求，需要擴(kuò)大top chunk：

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

b.非主分區(qū)上，使用mmap來(lái)分配一塊內(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.沒(méi)有合并情況則free

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

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

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

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

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

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

三、優(yōu)缺點(diǎn)

GEEK TALK

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

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

審核編輯 ：李倩