本文分為三個(gè)等級(jí)自頂向下地分析了glibc中內(nèi)存分配與回收的過(guò)程。本文不過(guò)度關(guān)注細(xì)節(jié)，因此只是分別從arena層次、bin層次、chunk層次進(jìn)行圖解，而不涉及有關(guān)指針的具體操作。

前言

在展開(kāi)本文之前，先解釋一下本文中會(huì)提到的三個(gè)重要概念：arena，bin，chunk。三者在邏輯上的蘊(yùn)含關(guān)系一般如下圖所示（圖中的chunk嚴(yán)格來(lái)說(shuō)應(yīng)該是Free Chunk）。

三者概念的解釋如下：

arena：通過(guò)sbrk或mmap系統(tǒng)調(diào)用為線(xiàn)程分配的堆區(qū)，按線(xiàn)程的類(lèi)型可以分為2類(lèi)：

• main arena：主線(xiàn)程建立的arena；

• thread arena：子線(xiàn)程建立的arena；

chunk：邏輯上劃分的一小塊內(nèi)存，根據(jù)作用不同分為4類(lèi)：

• Allocated chunk：即分配給用戶(hù)且未釋放的內(nèi)存塊；

• Free chunk：即用戶(hù)已經(jīng)釋放的內(nèi)存塊；

• Top chunk

• Last Remainder chunk

bin：一個(gè)用以保存Free chunk鏈表的表頭信息的指針數(shù)組，按所懸掛鏈表的類(lèi)型可以分為4類(lèi):

• Fast bin

• Unsorted bin

• Small bin

• Large bin

在這里讀者僅需明白arena的等級(jí)大于bin的等級(jí)大于(free)chunk的等級(jí)即可，即A>B>C。

tips:

實(shí)際內(nèi)存中，main arena和thread arena的圖示如下（單堆段）。

其中malloc_state的數(shù)據(jù)結(jié)構(gòu)描述在源代碼中發(fā)現(xiàn)該數(shù)據(jù)結(jié)構(gòu)中保存著fastbinsY、top、last_remainder、bins這四個(gè)分別表示Fast bin、Top chunk、Last Remainder chunk、bins（Unsorted bin、 Small bin、Large bin）的數(shù)據(jù)。

Arena級(jí)分析

此處從Arena的層次分析內(nèi)存分配與回收的過(guò)程。

main arena中的內(nèi)存申請(qǐng)

main arena中的內(nèi)存申請(qǐng)的流程如下圖所示：

第一次申請(qǐng)

• 根據(jù)申請(qǐng)內(nèi)存空間大小是否達(dá)到mmap這一系統(tǒng)調(diào)用的分配閾值，決定是使用sbrk系統(tǒng)調(diào)用 還是mmap系統(tǒng)調(diào)用申請(qǐng)堆區(qū)。一般分配的空間比申請(qǐng)的要大，這樣可以減少后續(xù)申請(qǐng)中向操作系統(tǒng)申請(qǐng)內(nèi)存的次數(shù)。

• 舉例而言，用戶(hù)申請(qǐng)1000字節(jié)的內(nèi)存，實(shí)際會(huì)通過(guò)sbrk系統(tǒng)調(diào)用產(chǎn)生132KB的連續(xù)堆內(nèi)存區(qū)域。

• 然后將用戶(hù)申請(qǐng)大小的內(nèi)存返回。（本例中將返回1000字節(jié)的內(nèi)存。）

后續(xù)申請(qǐng)

• 根據(jù)arena中剩余空間的大小決定是繼續(xù)分配還是擴(kuò)容，其中包含擴(kuò)容部分的為top chunk。

• 然后將用戶(hù)申請(qǐng)大小的內(nèi)存返回。

tips：top chunk不屬于任何bin！只有free chunk依附于bin！分配閾值具有默認(rèn)值，但會(huì)動(dòng)態(tài)調(diào)整；擴(kuò)容具體過(guò)程見(jiàn)庫(kù)函數(shù)sYSMALLOc 。

thread arena中的申請(qǐng)

thread arena中的內(nèi)存申請(qǐng)的流程如下圖所示：

其流程類(lèi)似于main arena的，區(qū)別在于thread arena的堆內(nèi)存是使用mmap系統(tǒng)調(diào)用產(chǎn)生的，而非同主線(xiàn)程一樣可能會(huì)使用sbrk系統(tǒng)調(diào)用。

tips：Arena的數(shù)量與線(xiàn)程之間并不一定是一一映射的關(guān)系。如，在32位系統(tǒng)中有著“ Number of arena = 2 * number of cores + 1”的限制。

內(nèi)存回收

線(xiàn)程釋放的內(nèi)存不會(huì)直接返還給操作系統(tǒng)，而是返還給’glibc malloc’。

bin級(jí)分析

此處從bin的層次分析內(nèi)存分配與回收的過(guò)程。考慮到內(nèi)存回收的過(guò)程比內(nèi)存分配的過(guò)程要復(fù)雜，因此這里先分析內(nèi)存回收的過(guò)程，再分析內(nèi)存分配的過(guò)程。

內(nèi)存回收

內(nèi)存回收的流程如下圖所示：

bin可以分為4類(lèi)：Fast bin、Unsorted bin、Small bin和 Large bin。保存這些bin的數(shù)據(jù)結(jié)構(gòu)為fastbinsY以及bins：

fastbinsY：用以保存fast bins。（可索引大小16~64B的內(nèi)存塊）

bins：用以保存unsorted、small以及l(fā)arge bins，共計(jì)可容納126個(gè)：

• Bin 1 – unsorted bin

• Bin 2 to Bin 63 – small bin(可索引大小<512B的內(nèi)存塊)

• Bin 64 to Bin 126 – large bin（可索引大小≥512B的內(nèi)存塊）

在內(nèi)存被釋放的時(shí)候，被釋放內(nèi)存塊會(huì)根據(jù)其大小而被添加入對(duì)應(yīng)的bin中：

• 16~64B的內(nèi)存塊會(huì)被添加入fastbinY中

• samll及l(fā)arge的會(huì)添加在bins中的unsorted bins中。

tips：small bins和large bins中索引的內(nèi)存塊是在內(nèi)存分配的過(guò)程中被添加在相應(yīng)的bin中的。

內(nèi)存分配

內(nèi)存分配的流程如下圖所示：

我們知道，內(nèi)存分配的最終目的在于分配出合適大小的內(nèi)存塊返回給用戶(hù)。在實(shí)現(xiàn)中即為在bin或top chunk中找到（并分割出）所需內(nèi)存塊，其檢索的優(yōu)先級(jí)從高到低分別是：

1. fastbinY

2. small bins

3. unsorted bins

4. large bins

5. top bins

tips：?Fast bin、Unsorted bin、Small bin和 Large bin中保存的都是用戶(hù)曾經(jīng)釋放的內(nèi)存塊（可能經(jīng)過(guò)合并）；top chunk包含Arena擴(kuò)容的部分，不屬于任何bin！

chunk級(jí)分析

本文不過(guò)度關(guān)注操作細(xì)節(jié)，因此有關(guān)內(nèi)存回收的過(guò)程就不贅述了。下圖即內(nèi)存分配的詳細(xì)過(guò)程圖：

tips：保存或新窗口打開(kāi)圖片可以查看原圖。

具體分配說(shuō)明參見(jiàn)下列引用內(nèi)容：

1、獲取分配區(qū)的鎖，為了防止多個(gè)線(xiàn)程同時(shí)訪(fǎng)問(wèn)同一個(gè)分配區(qū)，在進(jìn)行分配之前需要取得分配區(qū)域的鎖。線(xiàn)程先查看線(xiàn)程私有實(shí)例中是否已經(jīng)存在一個(gè)分配區(qū)，如果存在嘗試對(duì)該分配區(qū)加鎖，如果加鎖成功，使用該分配區(qū)分配內(nèi)存，否則，該線(xiàn)程搜索分配區(qū)循環(huán)鏈表試圖獲得一個(gè)空閑（沒(méi)有加鎖）的分配區(qū)。如果所有的分配區(qū)都已經(jīng)加鎖，那么ptmalloc會(huì)開(kāi)辟一個(gè)新的分配區(qū)，把該分配區(qū)加入到全局分配區(qū)循環(huán)鏈表和線(xiàn)程的私有實(shí)例中并加鎖，然后使用該分配區(qū)進(jìn)行分配操作。開(kāi)辟出來(lái)的新分配區(qū)一定為非主分配區(qū)，因?yàn)橹鞣峙鋮^(qū)是從父進(jìn)程那里繼承來(lái)的。開(kāi)辟非主分配區(qū)時(shí)會(huì)調(diào)用mmap()創(chuàng)建一個(gè)sub-heap，并設(shè)置好top chunk。

2、將用戶(hù)的請(qǐng)求大小轉(zhuǎn)換為實(shí)際需要分配的chunk空間大小。

3、判斷所需分配chunk的大小是否滿(mǎn)足chunk_size <= max_fast (max_fast 默認(rèn)為 64B)，如果是的話(huà)，則轉(zhuǎn)下一步，否則跳到第5步。

4、首先嘗試在fast bins中取一個(gè)所需大小的chunk分配給用戶(hù)。如果可以找到，則分配結(jié)束。否則轉(zhuǎn)到下一步。

5、判斷所需大小是否處在small bins中，即判斷chunk_size < 512B是否成立。如果chunk大小處在small bins中，則轉(zhuǎn)下一步，否則轉(zhuǎn)到第6步。

6、根據(jù)所需分配的chunk的大小，找到具體所在的某個(gè)small bin，從該bin的尾部摘取一個(gè)恰好滿(mǎn)足大小的chunk。若成功，則分配結(jié)束，否則，轉(zhuǎn)到下一步。

7、到了這一步，說(shuō)明需要分配的是一塊大的內(nèi)存，或者small bins中找不到合適的 chunk。于是，ptmalloc首先會(huì)遍歷fast bins中的chunk，將相鄰的chunk進(jìn)行合并，并鏈接到unsorted bin中，然后遍歷unsorted bin中的chunk，如果unsorted bin只有一個(gè)chunk，并且這個(gè)chunk在上次分配時(shí)被使用過(guò)，并且所需分配的chunk大小屬于small bins，并且chunk的大小大于等于需要分配的大小，這種情況下就直接將該chunk進(jìn)行切割，分配結(jié)束，否則將根據(jù)chunk的空間大小將其放入small bins或是large bins中，遍歷完成后，轉(zhuǎn)入下一步。

8、到了這一步，說(shuō)明需要分配的是一塊大的內(nèi)存，或者small bins和unsorted bin中都找不到合適的 chunk，并且fast bins和unsorted bin中所有的chunk都清除干凈了。從large bins中按照“smallest-first，best-fit”原則，找一個(gè)合適的 chunk，從中劃分一塊所需大小的chunk，并將剩下的部分鏈接回到bins中。若操作成功，則分配結(jié)束，否則轉(zhuǎn)到下一步。

9、如果搜索fast bins和bins都沒(méi)有找到合適的chunk，那么就需要操作top chunk來(lái)進(jìn)行分配了。判斷top chunk大小是否滿(mǎn)足所需chunk的大小，如果是，則從top chunk中分出一塊來(lái)。否則轉(zhuǎn)到下一步。

10、到了這一步，說(shuō)明top chunk也不能滿(mǎn)足分配要求，所以，于是就有了兩個(gè)選擇: 如果是主分配區(qū)，調(diào)用sbrk()，增加top chunk大小；如果是非主分配區(qū)，調(diào)用mmap來(lái)分配一個(gè)新的sub-heap，增加top chunk大小；或者使用mmap()來(lái)直接分配。在這里，需要依靠chunk的大小來(lái)決定到底使用哪種方法。判斷所需分配的chunk大小是否大于等于 mmap分配閾值，如果是的話(huà)，則轉(zhuǎn)下一步，調(diào)用mmap分配，否則跳到第12步，增加top chunk 的大小。

11、使用mmap系統(tǒng)調(diào)用為程序的內(nèi)存空間映射一塊chunk_size align 4kB大小的空間。然后將內(nèi)存指針?lè)祷亟o用戶(hù)。

12、判斷是否為第一次調(diào)用malloc，若是主分配區(qū)，則需要進(jìn)行一次初始化工作，分配一塊大小為(chunk_size + 128KB) align 4KB大小的空間作為初始的heap。若已經(jīng)初始化過(guò)了，主分配區(qū)則調(diào)用sbrk()增加heap空間，分主分配區(qū)則在top chunk中切割出一個(gè)chunk，使之滿(mǎn)足分配需求，并將內(nèi)存指針?lè)祷亟o用戶(hù)。

僅供大家學(xué)習(xí)參考與知識(shí)傳播，版權(quán)歸原作者所有，如有侵權(quán)，麻煩聯(lián)系進(jìn)行刪除，感謝~
???????????????? ?END ?????????????????