大家好，我是島主小風哥，今天聊聊malloc內存分配器是怎樣實現的。

在此之前我們需要回答一個基本問題，那就是我們為什么要發明內存分配器這種東西。

程序員經常使用的內存申請方式被稱為動態內存分配，Dynamic Memory Allocation。我們為什么需要動態的去進行內存分配與釋放呢？

答案很簡單，因為我們不能提前知道程序到底需要使用多少內存。那我們什么時候才能知道呢？答案是只有當程序真的運行起來后我們才知道。

圖片

這就是為什么程序員需要動態的去申請內存的原因，如果能提前知道我們的程序到底需要多少內存，那么直接知道告訴編譯器就好了，這樣也不必發明malloc等內存分配器了。

知道了為什么要發明內存分配器的原因后，接下來我們著手實現一個。

程序員應如何看待內存

實際上，現代程序員是很幸福的，程序員很少去關心內存分配的問題。作為程序員，可以簡單的認為我們的程序獨占內存，注意，是獨占哦。

圖片

寫程序時你從來沒有關心過如果我們的程序占用過多內存會不會影響到其它程序，我們可以簡單的認為每個程序(進程)獨占4G內存(32位操作系統)，即使我們的物理內存512M。不信你可以去試試，在即使只有512M大小的內存上你依然可以申請到2G內存來使用，可這是為什么呢？關于這個問題我們會在《深入理解操作系統》系列中詳細闡述。

總之，程序員可以放心的認為我們的程序運行起來后在內存中是這樣的：

圖片

作為程序員我們應該知道，內存動態申請和釋放都發生在堆區，heap。

我們使用的malloc或者C++中的new申請內存時，就是從堆區這個區域中申請的。

接下來我們就要自己管理堆區這個內存區域。

堆區這個區域實際上非常簡單，真的是非常簡單，你可以將其看做一大數組，就像這樣：

圖片

從內存分配器的角度看，內存分配器根本不關心你是整數、浮點數、鏈表、二叉樹等數據結構、還是對象、結構體等這些花哨的概念，在內存分配器眼里不過就是一個內存塊，這些內存塊中可以裝入原生的字節序列，申請者拿到該內存塊后可以塑造成整數、浮點數、鏈表、二叉樹等數據結構以及對象、結構體等，這是使用者的事情，和內存分配器無關。

我們要在這片內存上解決兩個問題：

• 實現一個malloc函數，也就是如果有人向我申請一塊內存，我該怎樣從堆區這片區域中找到一塊返回給申請者。
• 實現一個free函數，也就是當某一塊內存使用完畢后，我該怎樣還給堆區這片區域。

這是內存分配器要解決的兩個最核心的問題，接下來我們先去停車場看看能找到什么啟示。

從停車場到內存管理

實際上你可以把內存看做一條長長的停車場，我們申請內存就是要找到一塊停車位，釋放內存就是把車開走讓出停車位。

只不過這個停車場比較特殊，我們不止可以停小汽車、也可以停占地面積很小的自行車以及占地面積很大的卡車，重點就是申請的內存是大小不一的，在這樣的條件下你該怎樣實現以下兩個目標呢？

• 快速找到停車位，在內存申請中，這涉及到以最大速度找到一塊滿足要求的空閑內存
• 盡最大程度利用停車場，我們的停車場應該能停盡可能多的車，在內存申請中，這涉及到在給定條件下盡可能多的滿足內存申請需求

現在，我們已經清楚的理解任務了，那么該怎么實現呢？

任務拆分

現在我們已經明確要實現什么以及衡量其好壞的標準，接下來我們就要去設計實現細節了，讓我們把任務拆分一下，怎么拆分呢？

我們可以自己想一下從內存的申請到釋放需要哪些細節。

申請內存時，我們需要在內存中找到一塊大小合適的空閑內存分配出去，那么我們怎么知道有哪些內存塊是空閑的呢？

圖片

因此，第一個實現細節出現了，我們需要把內存塊用某種方式組織起來，這樣我們才能追蹤到每一塊內存的分配狀態。

現在空閑內存塊組織好了，那么一次內存申請可能有很多空閑內存塊滿足要求，那么我們該選擇哪一個空閑內存塊分配給用戶呢？

圖片

因此，第二個實現細節出現了，我們該選擇什么樣的空閑內存塊給到用戶。

接下來我們找到了一塊大小合適的內存塊，假設用戶需要16個字節，而我們找到的這塊空閑內存塊大小為32字節，那么將16字節分配給用戶后還剩下16字節，這剩下的內存該怎么處理呢？

因此，第三個實現細節出現了，分配出去內存后，空閑內存塊剩余的空間該怎么處理？

圖片

最后，分配給用戶的內存使用完畢，這是第四個細節出現了，我們該怎么處理用戶還給我們的內存呢？

以上四個問題是任何一個內存分配器必須要回答的，接下來我們就一一解決這些問題，解決完這些問題后一個嶄新的內存分配器就誕生啦。

管理空閑內存塊

空閑內存塊的本質是需要某種辦法來來區分哪些是空閑內存哪些是已經分配出去的內存。

有的同學可能會說，這還不簡單嗎，用一個鏈表之類的結構記錄下每個空閑內存塊的開始和結尾不就可以了，這句話也對也不對。

圖片

說不對，是因為如果要申請內存來創建這個鏈表那么這就是不對的，原因很簡單，因為創建鏈表不可避免的要申請內存，申請內存就需要通過內存分配器，可是你要實現的就是一個內存分配器，你沒有辦法向一個還沒有實現的內存分配器申請內存。

圖片

說對也對，我們確實需要一個類似鏈表這樣的結構來維護空閑內存塊，但這個鏈表并不是我們常見的那種。

因為我們無法將空閑內存塊的信息保存在其它地方，那么沒有辦法，我們只能將維護內存塊的分配信息保存在內存塊本身中，這也是大多數內存分配器的實現方法。

那么，為了維護內存塊分配狀態，我們需要知道哪些信息呢？很簡單：

• 一個標記，用來標識該內存塊是否空閑
• 一個數字，用來記錄該內存塊的大小

為了簡單起見，我們的內存分配器不對內存對齊有要求，同時一次內存申請允許的最大內存塊為2G，注意，這些假設是為了方便講解內存分配器的實現而屏蔽一些細節，我們常用的malloc等不會有這樣的限制。

因為我們的內存塊大小上限為2G，因此我們可以使用31個比特位來記錄塊大小，剩下的一個比特位用來標識該內存塊是空閑的還是已經被分配出去了，下圖中的f/a是free/allocate，也就是標記是已經分配出去還是空閑的。這32個比特位就是header，用來存儲塊信息。

圖片

剩下的灰色部分才是真正可以分配給用戶的內存，這一部分也被稱為負載，payload，我們調用malloc返回的內存起始地址正是這塊內存的起始地址。

現在你應該知道了吧，不是說堆上有10G內存，這里面就可以全部用來存儲數據的，這里面必然有一部分要拿出來維護內存塊的一些信息，就像這里的header一樣。

跟蹤內存分配狀態

有了上圖，我們就可以將堆這塊內存區域組織起來并進行內存分配與釋放了，如圖所示：

圖片

在這里我們的堆區還很小，每一方框代表4字節，其中紅色區域表示已經分配出去的，灰色區域表示空閑內存，每一塊內存都有一個header，用帶斜線的方框表示，比如16/1，就表示該內存塊大小是16字節，1表示已經分配出去了；而32/0表示該內存塊大小是32字節，0表示該內存塊當前空閑。

細心的同學可能會問，那最后一個方框0/1表示什么呢？原來，我們需要某種特殊標記來告訴我們的內存分配器是不是已經到末尾了，這就是最后4字節的作用。

通過引入header我們就能知道每一個內存塊的大小，從而可以很方便的遍歷整個堆區。遍歷方法很簡單，因為我們知道每一塊的大小，那么從當前的位置加上當前塊的大小就是下一個內存塊的起始位置，如圖所示：

圖片

通過每一個header的最后一個bit位就能知道每一塊內存是空閑的還是已經分配出去了，這樣我們就能追蹤到每一個內存塊的分配信息，因此上文提到的第一個問題解決了。

接下來我們看第二個問題。

怎樣選擇空閑內存塊

當應用程序調用我們實現的malloc時，內存分配器需要遍歷整個空閑內存塊找到一塊能滿足應用程序要求的內存塊返回，就像下圖這樣：

圖片

假設應用程序需要申請4字節內存，從圖中我們可以看到有兩個空閑內存塊滿足要求，第一個大小為8字節的內存塊和第三個大小為32字節的內存塊，那么我們到底該選擇哪一個返回呢？這就涉及到了分配策略的問題，實際上這里有很多的策略可供選擇。

First Fit

最簡單的就是每次從頭開始找起，找到第一個滿足要求的就返回，這就是所謂的First fit方法，教科書中一般稱為首次適應方法，當然我們不需要記住這樣拗口的名字，只需要記住這是什么意思就可以了。

圖片

這種方法的優勢在于簡單，但該策略總是從前面的空閑塊找起，因此很容易在堆區前半部分因分配出內存留下很多小的內存塊，因此下一次內存申請搜索的空閑塊數量將會越來越多。

Next Fit

該方法是大名鼎鼎的Donald Knuth首次提出來的，如果你不知道誰是Donald Knuth，那么數據結構課上折磨的你痛不欲生的字符串匹配KMP算法你一定不會錯過，KMP其中的K就是指Donald Knuth，該算法全稱Knuth–Morris–Pratt string-searching algorithm，如果你也沒聽過KMP算法那么你一定聽過下面這本書：

圖片

這就是更加大名鼎鼎的《計算機程序設計藝術》，這本書就是Donald Knuth寫的，如果你沒有聽過這本書請面壁思過一分鐘，比爾蓋茨曾經說過，如果你看懂了這本書就去給微軟投簡歷吧，這本書也是很多程序員買回來后從來不會翻一眼只是拿來當做鎮宅之寶用的。

不止比爾蓋茨，有一次喬布斯見到Knuth老爺子后。。算了，扯遠了，有機會再和大家講這個故事，拉回來。

Next Fit說的是什么呢？這個策略和First Fit很相似，是說我們別總是從頭開始找了，而是從上一次找到合適的空閑內存塊的位置找起，老爺子觀察到上一次找到某個合適的內存塊的地方很有可能剩下的內存塊能滿足接下來的內存分配請求，由于不需要從頭開始搜索，因此Next Fit將遠快于First Fit。

圖片

然而也有研究表明Next Fit方法內存使用率不及First Fit，也就是同樣的停車場面積，First Fit方法能停更多的車。

Best Fit

First Fit和Next Fit都是找到第一個滿足要求的內存塊就返回，但Best Fit不是這樣。

Best Fit算法會找到所有的空閑內存塊，然后將所有滿足要求的并且大小為最小的那個空閑內存塊返回，這樣的空閑內存塊才是最Best的，因此被稱為Best Fit。就像下圖雖然有三個空閑內存塊滿足要求，但是Best Fit會選擇大小為8字節的空閑內存塊。

圖片

顯然，從直覺上我們就能得出Best Fit會比前兩種方法能更合理利用內存的結論，各項研究也證實了這一點。

然而Best Fit最大的缺點就是分配內存時需要遍歷堆上所有的空閑內存塊，在速度上顯然不及前面兩種方法。

以上介紹的這三種策略在各種內存分配器中非常常見，當然分配策略遠不止這幾種，但這些算法不是該主題下關注的重點，因此就不在這里詳細闡述了，假設在這里我們選擇First Fit算法。

沒有銀彈

重要的是，從上面的介紹中我們能夠看到，沒有一種完美的策略，每一種策略都有其優點和缺點，我們能做到的只有取舍和權衡。因此，要實現一個內存分配器，設計空間其實是非常大的，要想設計出一個通用的內存分配器，就像我們常用的malloc是很不容易的。

其實不止內存分配器，在設計其它軟件系統時我們也沒有銀彈。

分配內存

現在我們找到合適的空閑內存塊了，接下來我們又將面臨一個新的問題。

如果用戶需要12字節，而我們的空閑內存塊也恰好是12字節，那么很好，直接返回就可以了。

但是，如果用戶申請12字節內存，而我們找到的空閑內存塊大小為32字節，那么我們是要將這32字節的整個空閑內存塊標記為已分配嗎？就像這樣：

圖片

這樣雖然速度最快，但顯然會浪費內存，形成內部碎片，也就是說該內存塊剩下的空間將無法被利用到。

圖片

一種顯而易見的方法就是將空閑內存塊進行劃分，前一部分設置為已分配，返回給內存申請者使用，后一部分變為一個新的空閑內存塊，只不過大小會更小而已，就像這樣：

圖片

我們需要將空閑內存塊大小從32修改為16，其中消息頭header占據4字節，剩下的12字節分配出去，并將標記為置為1，表示該內存塊已分配。

分配出16字節后，還剩下16字節，我們需要拿出4字節作為新的header并將其標記為空閑內存塊。

釋放內存

到目前為止，我們的malloc已經能夠處理內存分配請求了，還差最后的內存釋放。

內存釋放和我們想象的不太一樣，該過程并不比前幾個環節簡單。我們要考慮到的關鍵一點就在于，與被釋放的內存塊相鄰的內存塊可能也是空閑的。如果釋放一塊內存后我們僅僅簡單的將其標志位置為空閑，那么可能會出現下面的場景：

從圖中我們可以看到，被釋放內存的下一個內存塊也是空閑的，如果我們僅僅將這16個字節的內存塊標記為空閑的話，那么當下一次申請20字節時圖中的這兩個內存塊都不能滿足要求，盡管這兩個空閑內存塊的總數要超過20字節。

因此一種更好的方法是當應用程序向我們的malloc釋放內存時，我們查看一下相鄰的內存塊是否是空閑的，如果是空閑的話我們需要合并空閑內存塊，就像這樣：

在這里我們又面臨一個新的決策，那就是釋放內存時我們要立即去檢查能否夠合并相鄰空閑內存塊嗎？還是說我們可以推遲一段時間，推遲到下一次分配內存找不到滿足要的空閑內存塊時再合并相鄰空閑內存塊。

釋放內存時立即合并空閑內存塊相對簡單，但每次釋放內存時將引入合并內存塊的開銷，如果應用程序總是釋放12字節然后申請12字節，然后在釋放12字節等等這樣重復的模式：

free(ptr);
obj* ptr = malloc(12);
free(ptr);
obj* ptr = malloc(12);
...

圖片

那么這種內存使用模式對立即合并空閑內存塊這種策略非常不友好，我們的內存分配器會有很多的無用功。但這種策略最為簡單，在這里我們依然選擇使用這種簡單的策略。

實際上我們需要意識到，實際使用的內存分配器都會有某種推遲合并空閑內存塊的策略。

高效合并空閑內存塊

合并空閑內存塊的故事到這里就完了嗎？問題沒有那么簡單。

讓我們來看這樣一個場景：

圖片

使用的內存塊其前和其后都是空閑的，在當前的設計中我們可以很容易的知道后一個內存塊是空閑的，因為我們只需要從當前位置向下移動16字節就是下一個內存塊，但我們怎么能知道上一個內存塊是不是空閑的呢？

圖片

我們之所以能向后跳是因為當前內存塊的大小是知道的，那么我們該怎么向前跳找到上一個內存塊呢？

還是我們上文提到的Donald Knuth，老爺子提出了一個很聰明的設計，我們之所以不能往前跳是因為不知道前一個內存塊的信息，那么我們該怎么快速知道前一個內存塊的信息呢？

圖片

Knuth老爺子的設計是這樣的，我們不是有一個信息頭header嗎，那么我們就在該內存塊的末尾再加一個信息尾，footer，footer一詞用的很形象，header和footer的內容是一樣的。

因為上一內存塊的footer和下一個內存塊的header是相鄰的，因此我們只需要在當前內存塊的位置向上移動4直接就可以等到上一個內存塊的信息，這樣當我們釋放內存時就可以快速的進行相鄰空閑內存塊的合并了。

圖片

至此，我們的內存分配器就已經設計完畢了。

我們的簡單內存分配器采用了First Fit分配算法；找到一個滿足要求的內存塊后會進行切分，剩下的作為新的內存塊；同時當釋放內存時會立即合并相鄰的空閑內存塊，同時為加快合并速度，我們引入了Donald Knuth的設計方法，為每個內存塊增加footer信息。