深入理解glibcmalloc：malloc()與free()原理圖解

點擊上方“C語言與CPP編程”，選擇“關注/置頂/星標公眾號”

干貨福利，第一時間送達！

你好，我是飛宇。

前言

在展開本文之前，先解釋一下本文中會提到的三個重要概念：arena，bin，chunk。三者在邏輯上的蘊含關系一般如下圖所示（圖中的chunk嚴格來說應該是Free Chunk）。

三者概念的解釋如下：

arena：通過sbrk或mmap系統調用為線程分配的堆區，按線程的類型可以分為2類：

• main arena：主線程建立的arena；

• thread arena：子線程建立的arena；

chunk：邏輯上劃分的一小塊內存，根據作用不同分為4類：

• Allocated chunk：即分配給用戶且未釋放的內存塊；

• Free chunk：即用戶已經釋放的內存塊；

• Top chunk

• Last Remainder chunk

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

• Fast bin

• Unsorted bin

• Small bin

• Large bin

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

tips:

實際內存中，main arena和thread arena的圖示如下（單堆段）。

其中malloc_state的數據結構描述在源代碼中發現該數據結構中保存著fastbinsY、top、last_remainder、bins這四個分別表示Fast bin、Top chunk、Last Remainder chunk、bins（Unsorted bin、 Small bin、Large bin）的數據。

Arena級分析

此處從Arena的層次分析內存分配與回收的過程。

main arena中的內存申請

main arena中的內存申請的流程如下圖所示：

第一次申請

• 根據申請內存空間大小是否達到mmap這一系統調用的分配閾值，決定是使用sbrk系統調用 還是mmap系統調用申請堆區。一般分配的空間比申請的要大，這樣可以減少后續申請中向操作系統申請內存的次數。

• 舉例而言，用戶申請1000字節的內存，實際會通過sbrk系統調用產生132KB的連續堆內存區域。

• 然后將用戶申請大小的內存返回。（本例中將返回1000字節的內存。）

后續申請

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

• 然后將用戶申請大小的內存返回。

tips：top chunk不屬于任何bin！只有free chunk依附于bin！分配閾值具有默認值，但會動態調整；擴容具體過程見庫函數sYSMALLOc 。

thread arena中的申請

thread arena中的內存申請的流程如下圖所示：

其流程類似于main arena的，區別在于thread arena的堆內存是使用mmap系統調用產生的，而非同主線程一樣可能會使用sbrk系統調用。

tips：Arena的數量與線程之間并不一定是一一映射的關系。如，在32位系統中有著“ Number of arena = 2 * number of cores + 1”的限制。

內存回收

線程釋放的內存不會直接返還給操作系統，而是返還給’glibc malloc’。

bin級分析

此處從bin的層次分析內存分配與回收的過程。考慮到內存回收的過程比內存分配的過程要復雜，因此這里先分析內存回收的過程，再分析內存分配的過程。

內存回收

內存回收的流程如下圖所示：

bin可以分為4類：Fast bin、Unsorted bin、Small bin和 Large bin。保存這些bin的數據結構為fastbinsY以及bins：

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

bins：用以保存unsorted、small以及large bins，共計可容納126個：

• Bin 1 – unsorted bin

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

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

在內存被釋放的時候，被釋放內存塊會根據其大小而被添加入對應的bin中：

• 16~64B的內存塊會被添加入fastbinY中

• samll及large的會添加在bins中的unsorted bins中。

tips：small bins和large bins中索引的內存塊是在內存分配的過程中被添加在相應的bin中的。

內存分配

內存分配的流程如下圖所示：

我們知道，內存分配的最終目的在于分配出合適大小的內存塊返回給用戶。在實現中即為在bin或top chunk中找到（并分割出）所需內存塊，其檢索的優先級從高到低分別是：

1. fastbinY

2. small bins

3. unsorted bins

4. large bins

5. top bins

tips：?Fast bin、Unsorted bin、Small bin和 Large bin中保存的都是用戶曾經釋放的內存塊（可能經過合并）；top chunk包含Arena擴容的部分，不屬于任何bin！

chunk級分析

本文不過度關注操作細節，因此有關內存回收的過程就不贅述了。下圖即內存分配的詳細過程圖：

tips：保存或新窗口打開圖片可以查看原圖。

具體分配說明參見下列引用內容：

1、獲取分配區的鎖，為了防止多個線程同時訪問同一個分配區，在進行分配之前需要取得分配區域的鎖。線程先查看線程私有實例中是否已經存在一個分配區，如果存在嘗試對該分配區加鎖，如果加鎖成功，使用該分配區分配內存，否則，該線程搜索分配區循環鏈表試圖獲得一個空閑（沒有加鎖）的分配區。如果所有的分配區都已經加鎖，那么ptmalloc會開辟一個新的分配區，把該分配區加入到全局分配區循環鏈表和線程的私有實例中并加鎖，然后使用該分配區進行分配操作。開辟出來的新分配區一定為非主分配區，因為主分配區是從父進程那里繼承來的。開辟非主分配區時會調用mmap()創建一個sub-heap，并設置好top chunk。

2、將用戶的請求大小轉換為實際需要分配的chunk空間大小。

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

4、首先嘗試在fast bins中取一個所需大小的chunk分配給用戶。如果可以找到，則分配結束。否則轉到下一步。

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

6、根據所需分配的chunk的大小，找到具體所在的某個small bin，從該bin的尾部摘取一個恰好滿足大小的chunk。若成功，則分配結束，否則，轉到下一步。

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

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

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

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

11、使用mmap系統調用為程序的內存空間映射一塊chunk_size align 4kB大小的空間。然后將內存指針返回給用戶。

12、判斷是否為第一次調用malloc，若是主分配區，則需要進行一次初始化工作，分配一塊大小為(chunk_size + 128KB) align 4KB大小的空間作為初始的heap。若已經初始化過了，主分配區則調用sbrk()增加heap空間，分主分配區則在top chunk中切割出一個chunk，使之滿足分配需求，并將內存指針返回給用戶。