關注、星標公眾號，直達精彩內(nèi)容
文章來源：技術讓夢想更偉大
整理：李肖遙
由于malloc()的源碼十分的繁瑣，并且會調(diào)用OS所提供的API，所以我不在對malloc()的源碼進行分析了，而只是會分析malloc()的動作，這就已經(jīng)足夠了。
在前邊的文章中已經(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
首先，在進入程序之前，系統(tǒng)就已經(jīng)分配出了一個結(jié)構去管理內(nèi)存，我們先來看看這個結(jié)構
代碼比較難看懂，我這里分析一下。
系統(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é)構：
這里需要重點關注的是兩根指針：
這張圖對應了上邊的關系
在這個圖中顯示的，pHeapData指向的是虛擬地址空間，沒錯，現(xiàn)在還是虛擬的，并沒有為其分配內(nèi)存，我們可以將他想象成門牌號的集合。這里只保存了門牌號，但是房子還沒有建起來。這里以后將要分配的空間一共是1MB，將被分為32個32KB的內(nèi)存段。
接下來我們詳細去看pRegion所指向的結(jié)構，也就是tagRegion；
indGroupUse表示了當前會提供內(nèi)存的group編號，從0開始
cntRegionSize[64]用64個字節(jié)去對應后邊group所將會展開鏈表，當對應鏈表掛在有內(nèi)存時，將會變成1.
bitvGroupHi和bitvGroupLo共同構成了一個的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條鏈表
下面我們來看每個嶄新的內(nèi)存頁的內(nèi)容
這是一個4K大小的內(nèi)存頁：
當申請一個內(nèi)存空間時，首先先去符合的鏈表中尋找，如果鏈表中沒有掛載內(nèi)存塊，就從編號較大的鏈表中最近的掛有內(nèi)存塊的鏈表中劃分。
最左邊原先是一個嶄新的內(nèi)存頁(4K = ff0)，然后我們從內(nèi)存頁中劃分出0x130 byte的空間：
當這塊內(nèi)存被分配出去之后，原來內(nèi)存頁中的cookie = ff0-130 = ec0，此時仍然大于1KB，所以不用轉(zhuǎn)移掛載的位置。
我們剛剛分配出了0x130的空間，我們先看看這個空間分配出去之后的動作
此時page1中剩余空間為ec0 byte;
當某一次分配時，group0中沒有比當前需求大的內(nèi)存塊了，此時就需要開辟另一個group去服務了
此時再分配內(nèi)存就會從group中去分配了
當多次連續(xù)分配之后，出現(xiàn)了一次歸還空間的動作
我們來探討幾個問題：
答案很簡單，夾殺法：我們知道每一個group對應內(nèi)存的起始地址和結(jié)尾地址，我們只需要去判斷被歸還的指針中地址的大小是否在這二者之間，就能判斷出是否屬于當前的group。而去尋找所對應的header的方法也是如此。
這里時malloc和之前講過的分配器本質(zhì)上的區(qū)別，我們能將收回的內(nèi)存還給操作系統(tǒng)，具體步驟如下：
這里我們假設還的的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)整連接位置。
這也很簡單，我們再每個group都記錄了分配出去的次數(shù)，每當我們回收的時候，就將這個值-1，所以當它再次為0的時候，就證明這個group的內(nèi)存全部回收了。
由于有上邊的合并機制，所以當一個group的內(nèi)存全回收之后，他的狀態(tài)就和最開始時一樣，也就是最后一個鏈表上連接著8個4KB大小的內(nèi)存塊，這時我們就可以將他還給操作系統(tǒng)了。
答案肯定是否定的，因為如果我們?nèi)厥找粋€就還一個，那么當下一次在需要分配時，我們還需要重新分配。所以全回收的group不會立刻被還給系統(tǒng)，而是等待下一個全回收的group出現(xiàn)，就會將前一個group對應的內(nèi)存free掉。
參考原文鏈接：https://blog.csdn.net/qq_34269632
???????????????? ?END ?????????????????
關注我的微信公眾號，回復“加群”按規(guī)則加入技術交流群。
點擊“閱讀原文”查看更多分享，歡迎點分享、收藏、點贊、在看。
