文章來(lái)源：技術(shù)讓夢(mèng)想更偉大

整理：李肖遙

前言

由于malloc()的源碼十分的繁瑣，并且會(huì)調(diào)用OS所提供的API，所以我不在對(duì)malloc()的源碼進(jìn)行分析了，而只是會(huì)分析malloc()的動(dòng)作，這就已經(jīng)足夠了。

一、malloc()分配出的內(nèi)存空間

在前邊的文章中已經(jīng)提及到了，當(dāng)malloc()分配空間時(shí)，并不是要多少就分配多少，而是會(huì)額外的加上首部和尾部，其中一些較為簡(jiǎn)單的部分我會(huì)在這里進(jìn)行解釋?zhuān)^為重要的部分我會(huì)在本文下面的分析中逐步的完善。圖片取自侯捷C 內(nèi)存分配系列教程講義

這張圖片去除掉了上下兩塊cookie和下邊的填補(bǔ)區(qū)pad。

淺綠色的fill是調(diào)用malloc()時(shí)向系統(tǒng)申請(qǐng)的內(nèi)存，該函數(shù)返回時(shí)，也會(huì)返回這塊區(qū)域開(kāi)頭的指針。這里申請(qǐng)了0x100 byte的內(nèi)存.

fill上下兩塊gap預(yù)先被填充為了0xfdfdfdfd，用來(lái)分隔客戶(hù)可以使用的內(nèi)存區(qū)和不可使用的內(nèi)存區(qū)，同時(shí)，當(dāng)這塊內(nèi)存被歸還時(shí)，編輯器也可以通過(guò)下gap的值區(qū)判斷當(dāng)前內(nèi)存塊是否被越界使用了。

上gap向上連續(xù)的7個(gè)內(nèi)存空間共同組成了debug header，從上向下標(biāo)號(hào)為1-7

• 1、2兩塊空間保存了兩根指針，目的是使多個(gè)內(nèi)存塊連接成鏈表。
• 3空間保存了申請(qǐng)本內(nèi)存塊的文件名
• 4- 空間保存了申請(qǐng)本內(nèi)存塊的代碼行數(shù)
• 5空間記錄了本內(nèi)存塊中實(shí)際可以被用戶(hù)使用的內(nèi)存空間的大小
• 6空間記錄了當(dāng)前內(nèi)存塊的流水號(hào)，即是鏈表中的第幾個(gè)，從1開(kāi)始
• 7空間記錄了當(dāng)前內(nèi)存塊被分配的形式，后邊會(huì)進(jìn)行分析

二、內(nèi)存分配

1.內(nèi)存管理所用到的結(jié)構(gòu)層次

首先，在進(jìn)入程序之前，系統(tǒng)就已經(jīng)分配出了一個(gè)結(jié)構(gòu)去管理內(nèi)存，我們先來(lái)看看這個(gè)結(jié)構(gòu)

代碼比較難看懂，我這里分析一下。

系統(tǒng)首先會(huì)調(diào)用__cdecl_heap_init()函數(shù)去分配一個(gè)堆空間，用在這里分配的堆空間去管理程序中會(huì)產(chǎn)生的動(dòng)態(tài)分配內(nèi)存的請(qǐng)求。而在__cdecl_heap_init()這個(gè)函數(shù)中，回去創(chuàng)建一個(gè)長(zhǎng)度為16的類(lèi)型為HEADER的鏈表，這個(gè)鏈表的每個(gè)節(jié)點(diǎn)將在以后的程序中去管理1MB的內(nèi)存。

我們?nèi)タ聪逻@個(gè)鏈表的節(jié)點(diǎn)的結(jié)構(gòu)：

這里需要重點(diǎn)關(guān)注的是兩根指針：

• 指針pHeapData將被指向這個(gè)header所管理的那1MB的內(nèi)存空間的開(kāi)頭。
• pRegion將會(huì)被指向一個(gè)管理用的結(jié)構(gòu)，這個(gè)結(jié)構(gòu)將會(huì)在下邊展開(kāi)

這張圖對(duì)應(yīng)了上邊的關(guān)系

在這個(gè)圖中顯示的，pHeapData指向的是虛擬地址空間，沒(méi)錯(cuò)，現(xiàn)在還是虛擬的，并沒(méi)有為其分配內(nèi)存，我們可以將他想象成門(mén)牌號(hào)的集合。這里只保存了門(mén)牌號(hào)，但是房子還沒(méi)有建起來(lái)。這里以后將要分配的空間一共是1MB，將被分為32個(gè)32KB的內(nèi)存段。

接下來(lái)我們?cè)敿?xì)去看pRegion所指向的結(jié)構(gòu)，也就是tagRegion；

• indGroupUse表示了當(dāng)前會(huì)提供內(nèi)存的group編號(hào)，從0開(kāi)始

  
  

• cntRegionSize[64]用64個(gè)字節(jié)去對(duì)應(yīng)后邊group所將會(huì)展開(kāi)鏈表，當(dāng)對(duì)應(yīng)鏈表掛在有內(nèi)存時(shí)，將會(huì)變成1.

  
  

• bitvGroupHi和bitvGroupLo共同構(gòu)成了一個(gè)的byteMap共64個(gè)byte(分為32組)，將來(lái)用于對(duì)應(yīng)每個(gè)group中所掛載的64條雙向鏈表，當(dāng)對(duì)應(yīng)的位置掛載有內(nèi)存時(shí)，會(huì)變成1.

  
  

• grpHeadList就是32個(gè)group，每個(gè)group負(fù)責(zé)32KB

  
  

• 這里的cntEntries代表當(dāng)前鏈表中掛載的內(nèi)存塊被切分的次數(shù)

  
  

• listHead對(duì)應(yīng)64對(duì)指針，也就是形成了64條鏈表，用于掛載不同大小的內(nèi)存塊，間隔為16byte，最后一條鏈表將掛載所有大于等于1K的內(nèi)存塊

  
  

編號(hào)1就是上邊所說(shuō)的每grop中的那64條雙向鏈表現(xiàn)在只有最后一條雙向鏈表中掛載有內(nèi)存頁(yè)。

編號(hào)2是這個(gè)group所對(duì)應(yīng)的那32K的內(nèi)存段，將他分為了8份，每份就是4K，將這8個(gè)內(nèi)存頁(yè)串成鏈表，由于每一個(gè)內(nèi)存頁(yè)都大于1K，所以都將掛載在最后一條鏈表上。

當(dāng)一切準(zhǔn)備好，掛載的對(duì)應(yīng)方式如下圖：

• 編號(hào)1是當(dāng)前header所管理的1MB的空間，將其32等分，每一份的32KB由一個(gè)group去負(fù)責(zé)分配

  
  

• 編號(hào)2是一個(gè)group所管理的32K的空間，將其分為8個(gè)4KB大小的內(nèi)存頁(yè)掛載于最后一條鏈表上

  
  

• 編號(hào)3是分割好的內(nèi)存頁(yè)鏈表，他們被串成一個(gè)雙向鏈表。

  
  

• 編號(hào)4是一個(gè)group中的64條鏈表

  
  

2.內(nèi)存頁(yè)的劃分

下面我們來(lái)看每個(gè)嶄新的內(nèi)存頁(yè)的內(nèi)容

這是一個(gè)4K大小的內(nèi)存頁(yè)：

• 中間的空白區(qū)域代表了可共malloc()索取的4080byte的內(nèi)存空間
• 空白的最下邊和紅色的最上邊，兩個(gè)標(biāo)有4080的空間是用來(lái)記錄剩余可用空間大小的cookie
• 剩余的兩塊紅色部分是兩根指針，指向鏈表中前邊和后邊的內(nèi)存頁(yè)
• 黃色的標(biāo)有0xfdfdfdfd的是兩根分割區(qū)域，具體作用上邊已經(jīng)提及
• 最上邊的保留區(qū)域是為了讓下邊空白區(qū)域成為16byte的整數(shù)倍

內(nèi)存頁(yè)劃分的規(guī)則

當(dāng)申請(qǐng)一個(gè)內(nèi)存空間時(shí)，首先先去符合的鏈表中尋找，如果鏈表中沒(méi)有掛載內(nèi)存塊，就從編號(hào)較大的鏈表中最近的掛有內(nèi)存塊的鏈表中劃分。

內(nèi)存頁(yè)被劃分之后的情況

最左邊原先是一個(gè)嶄新的內(nèi)存頁(yè)(4K = ff0)，然后我們從內(nèi)存頁(yè)中劃分出0x130 byte的空間：

• 編號(hào)為1的是被劃分出的實(shí)際空間
• 編號(hào)2是實(shí)際可以為用戶(hù)所使用的實(shí)際空間，這個(gè)空間應(yīng)該是0x100
• 上下兩根cookie記錄了被劃分出去的實(shí)際空間，至于為什么是0x131，之前的文章有提及
• 內(nèi)存被劃分出去后，malloc()再對(duì)其進(jìn)行復(fù)寫(xiě)，然后將實(shí)際空間交付給客戶(hù)。

當(dāng)這塊內(nèi)存被分配出去之后，原來(lái)內(nèi)存頁(yè)中的cookie = ff0-130 = ec0，此時(shí)仍然大于1KB，所以不用轉(zhuǎn)移掛載的位置。

3.內(nèi)存分配的動(dòng)作

我們剛剛分配出了0x130的空間，我們先看看這個(gè)空間分配出去之后的動(dòng)作

• 編號(hào)1：此時(shí)由group0分配內(nèi)存，所以Region 中的 indGroupUse被設(shè)置為0
• 編號(hào)2：整個(gè)group的內(nèi)存頁(yè)被劃分了一次，所以Group 中的 cntEntries被置為1
• 編號(hào)3：此時(shí)group0只有最后一個(gè)鏈表空間上掛載了鏈表，所以Region 中對(duì)應(yīng)的byte被置為1

此時(shí)page1中剩余空間為ec0 byte;

當(dāng)某一次分配時(shí)，group0中沒(méi)有比當(dāng)前需求大的內(nèi)存塊了，此時(shí)就需要開(kāi)辟另一個(gè)group去服務(wù)了

• 編號(hào)1：由于當(dāng)前是group1再分配內(nèi)存，所以Region 中的 indGroupUse設(shè)置為1
• 編號(hào)2：將group1中最后一條鏈表再bitMap中對(duì)應(yīng)的位設(shè)置為1
• 編號(hào)3：group1整個(gè)的內(nèi)存頁(yè)被劃分了一次，所以Group 中的 cntEntries被置為1

此時(shí)再分配內(nèi)存就會(huì)從group中去分配了

4.內(nèi)存歸還的動(dòng)作

當(dāng)多次連續(xù)分配之后，出現(xiàn)了一次歸還空間的動(dòng)作

• 編號(hào)1：當(dāng)前group分配出的內(nèi)存塊-1
• 編號(hào)2：由于此次歸還的內(nèi)存大小為0x240應(yīng)該掛載于第35號(hào)鏈表，所以將第35號(hào)鏈表對(duì)應(yīng)的bite設(shè)為1(這里將byteMap中每四個(gè)byte寫(xiě)成了一個(gè)16進(jìn)制數(shù))
• 編號(hào)3：當(dāng)前還是group所分配內(nèi)存，所以所以Region 中的 indGroupUse仍為0
• 編號(hào)4：這時(shí)被歸還的內(nèi)存被復(fù)寫(xiě)，兩個(gè)cookie從0x241變回0x240，表示沒(méi)有被使用,兩根指針連入35號(hào)鏈表。

三、將內(nèi)存歸還給OS

我們來(lái)探討幾個(gè)問(wèn)題：

Q1、當(dāng)多個(gè)group被啟用時(shí)，怎么去尋找歸還的內(nèi)存屬于哪個(gè)group？

答案很簡(jiǎn)單，夾殺法：我們知道每一個(gè)group對(duì)應(yīng)內(nèi)存的起始地址和結(jié)尾地址，我們只需要去判斷被歸還的指針中地址的大小是否在這二者之間，就能判斷出是否屬于當(dāng)前的group。而去尋找所對(duì)應(yīng)的header的方法也是如此。

Q2、怎么將內(nèi)存還給操作系統(tǒng)？`

這里時(shí)malloc和之前講過(guò)的分配器本質(zhì)上的區(qū)別，我們能將收回的內(nèi)存還給操作系統(tǒng)，具體步驟如下：

1. 對(duì)于回收的連續(xù)的內(nèi)存空間進(jìn)行合并 這個(gè)實(shí)現(xiàn)時(shí)基于上下兩個(gè)cookie的實(shí)現(xiàn)完成的

這里我們假設(shè)還的的1號(hào)空間，我們能看到 2、3兩個(gè)空間的cookie結(jié)尾都是0，所以也是空閑的，也就是說(shuō)這三塊連續(xù)的空間可以合并。

向下合并：我們首先有一個(gè)指向1號(hào)空間的指針，他通過(guò)cookie可以知道自己有多大，所以下調(diào)對(duì)應(yīng)的大小就可以到達(dá)2號(hào)空間的開(kāi)頭，查看2號(hào)空間的cookie可以知道他的大小，也可以知道它是空閑的，所以可以將他們兩個(gè)合并。

向上合并：我們首先有一個(gè)指向1號(hào)空間的指針，他向上調(diào)整兩個(gè)int的長(zhǎng)度，可以到達(dá)3號(hào)空間的cookie，通過(guò)三號(hào)空間的cookie可以知道3號(hào)空間的大小，也可以知道3號(hào)空間是空閑的，所以就可以將他們兩個(gè)合并。重復(fù)上邊兩個(gè)步驟，我們可以將相連的N塊空閑內(nèi)存全部合并，并計(jì)算大小調(diào)整連接位置。

1. 判斷分配的空間的全回收

這也很簡(jiǎn)單，我們?cè)倜總€(gè)group都記錄了分配出去的次數(shù)，每當(dāng)我們回收的時(shí)候，就將這個(gè)值-1，所以當(dāng)它再次為0的時(shí)候，就證明這個(gè)group的內(nèi)存全部回收了。

1. 當(dāng)內(nèi)存全回收之后的狀態(tài)

由于有上邊的合并機(jī)制，所以當(dāng)一個(gè)group的內(nèi)存全回收之后，他的狀態(tài)就和最開(kāi)始時(shí)一樣，也就是最后一個(gè)鏈表上連接著8個(gè)4KB大小的內(nèi)存塊，這時(shí)我們就可以將他還給操作系統(tǒng)了。

Q3：當(dāng)一個(gè)group全回收之后，我們需要將他立刻還給系統(tǒng)么？

答案肯定是否定的，因?yàn)槿绻覀內(nèi)厥找粋€(gè)就還一個(gè)，那么當(dāng)下一次在需要分配時(shí)，我們還需要重新分配。所以全回收的group不會(huì)立刻被還給系統(tǒng)，而是等待下一個(gè)全回收的group出現(xiàn)，就會(huì)將前一個(gè)group對(duì)應(yīng)的內(nèi)存free掉。

????????????????  END  ????????????????