本文分為三個等級自頂向下地分析了glibc中內存分配與回收的過程。本文不過度關注細節，因此只是分別從arena層次、bin層次、chunk層次進行圖解，而不涉及有關指針的具體操作。
在展開本文之前，先解釋一下本文中會提到的三個重要概念：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的層次分析內存分配與回收的過程。
main arena中的內存申請的流程如下圖所示：
第一次申請
根據申請內存空間大小是否達到mmap這一系統調用的分配閾值，決定是使用sbrk系統調用 還是mmap系統調用申請堆區。一般分配的空間比申請的要大，這樣可以減少后續申請中向操作系統申請內存的次數。
舉例而言，用戶申請1000字節的內存，實際會通過sbrk系統調用產生132KB的連續堆內存區域。
然后將用戶申請大小的內存返回。（本例中將返回1000字節的內存。）
后續申請
根據arena中剩余空間的大小決定是繼續分配還是擴容，其中包含擴容部分的為top chunk。
然后將用戶申請大小的內存返回。
tips：top chunk不屬于任何bin！只有free chunk依附于bin！分配閾值具有默認值，但會動態調整；擴容具體過程見庫函數sYSMALLOc 。
thread arena中的內存申請的流程如下圖所示：
其流程類似于main arena的，區別在于thread arena的堆內存是使用mmap系統調用產生的，而非同主線程一樣可能會使用sbrk系統調用。
tips：Arena的數量與線程之間并不一定是一一映射的關系。如，在32位系統中有著“ Number of arena = 2 * number of cores + 1”的限制。
內存回收
線程釋放的內存不會直接返還給操作系統，而是返還給’glibc malloc’。
此處從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中找到（并分割出）所需內存塊，其檢索的優先級從高到低分別是：
fastbinY
small bins
unsorted bins
large bins
top bins
tips：?Fast bin、Unsorted bin、Small bin和 Large bin中保存的都是用戶曾經釋放的內存塊（可能經過合并）；top chunk包含Arena擴容的部分，不屬于任何bin！
本文不過度關注操作細節，因此有關內存回收的過程就不贅述了。下圖即內存分配的詳細過程圖：
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，使之滿足分配需求，并將內存指針返回給用戶。
end
一口Linux?
關注，回復【1024】海量Linux資料贈送
精彩文章合集
文章推薦
點擊“閱讀原文”查看更多分享，歡迎點分享、收藏、點贊、在看
