文章來源：技術讓夢想更偉大

整理：李肖遙

前言

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

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

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

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

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

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

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

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

二、內(nèi)存分配

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

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

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

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

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

這里需要重點關注的是兩根指針：

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

這張圖對應了上邊的關系

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

接下來我們詳細去看pRegion所指向的結(jié)構(gòu)，也就是tagRegion；

• indGroupUse表示了當前會提供內(nèi)存的group編號，從0開始

  
  

• cntRegionSize[64]用64個字節(jié)去對應后邊group所將會展開鏈表，當對應鏈表掛在有內(nèi)存時，將會變成1.

  
  

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

  
  

• grpHeadList就是32個group，每個group負責32KB

  
  

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

  
  

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

  
  

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

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

當一切準備好，掛載的對應方式如下圖：

• 編號1是當前header所管理的1MB的空間，將其32等分，每一份的32KB由一個group去負責分配

  
  

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

  
  

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

  
  

• 編號4是一個group中的64條鏈表

  
  

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

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

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

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

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

當申請一個內(nèi)存空間時，首先先去符合的鏈表中尋找，如果鏈表中沒有掛載內(nèi)存塊，就從編號較大的鏈表中最近的掛有內(nèi)存塊的鏈表中劃分。

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

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

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

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

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

我們剛剛分配出了0x130的空間，我們先看看這個空間分配出去之后的動作

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

此時page1中剩余空間為ec0 byte;

當某一次分配時，group0中沒有比當前需求大的內(nèi)存塊了，此時就需要開辟另一個group去服務了

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

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

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

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

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

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

我們來探討幾個問題：

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

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

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

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

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

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

向下合并：我們首先有一個指向1號空間的指針，他通過cookie可以知道自己有多大，所以下調(diào)對應的大小就可以到達2號空間的開頭，查看2號空間的cookie可以知道他的大小，也可以知道它是空閑的，所以可以將他們兩個合并。

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

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

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

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

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

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

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

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