對內(nèi)存分配器透徹理解是編程高手的標志之一。

如果你不能理解malloc之類內(nèi)存分配器實現(xiàn)原理的話，那你可能寫不出高性能程序，寫不出高性能程序就很難參與核心項目，參與不了核心項目那么很難升職加薪，很難升級加薪就無法走向人生巔峰，沒想到內(nèi)存分配竟如此關鍵，為了走上人生巔峰你也要勢必讀完本文。

現(xiàn)在我們知道了，對內(nèi)存分配器透徹的理解是寫出高性能程序的關鍵所在，那么我們該怎樣透徹理解內(nèi)存分配器呢？

還有什么能比你自己動手實現(xiàn)一個理解的更透徹嗎？

接下來，我們就自己實現(xiàn)一個malloc內(nèi)存分配器。讀完本文后內(nèi)存分配對你將不再是一個神秘的黑盒。在講解實現(xiàn)原理之前，我們需要回答一個基本問題，那就是我們?yōu)槭裁匆l(fā)明內(nèi)存分配器這種東西。

內(nèi)存申請與釋放

程序員經(jīng)常使用的內(nèi)存申請方式被稱為動態(tài)內(nèi)存分配，Dynamic Memory Allocation。我們?yōu)槭裁葱枰獎討B(tài)的去進行內(nèi)存分配與釋放呢？答案很簡單，因為我們不能提前知道程序到底需要使用多少內(nèi)存。那我們什么時候才能知道呢？答案是只有當程序真的運行起來后我們才知道。

這就是為什么程序員需要動態(tài)的去申請內(nèi)存的原因，如果能提前知道我們的程序到底需要多少內(nèi)存，那么直接知道告訴編譯器就好了，這樣也不必發(fā)明malloc等內(nèi)存分配器了。知道了為什么要發(fā)明內(nèi)存分配器的原因后，接下來我們著手實現(xiàn)一個。

【文章福利】小編推薦自己的Linux內(nèi)核技術交流群:【891587639】整理了一些個人覺得比較好的學習書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦！?。。ê曨l教程、電子書、實戰(zhàn)項目及代碼)? ?

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

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

作為程序員我們應該知道，內(nèi)存動態(tài)申請和釋放都發(fā)生在堆區(qū)，heap。我們使用的malloc或者C++中的new申請內(nèi)存時，就是從堆區(qū)這個區(qū)域中申請的。接下來我們就要自己管理堆區(qū)這個內(nèi)存區(qū)域。堆區(qū)這個區(qū)域?qū)嶋H上非常簡單，真的是非常簡單，你可以將其看做一大數(shù)組，就像這樣：

從內(nèi)存分配器的角度看，內(nèi)存分配器根本不關心你是整數(shù)、浮點數(shù)、鏈表、二叉樹等數(shù)據(jù)結構、還是對象、結構體等這些花哨的概念，在內(nèi)存分配器眼里不過就是一個內(nèi)存塊，這些內(nèi)存塊中可以裝入原生的字節(jié)序列，申請者拿到該內(nèi)存塊后可以塑造成整數(shù)、浮點數(shù)、鏈表、二叉樹等數(shù)據(jù)結構以及對象、結構體等，這是使用者的事情，和內(nèi)存分配器無關。我們要在這片內(nèi)存上解決兩個問題：

• 實現(xiàn)一個malloc函數(shù)，也就是如果有人向我申請一塊內(nèi)存，我該怎樣從堆區(qū)這片區(qū)域中找到一塊返回給申請者。

• 實現(xiàn)一個free函數(shù)，也就是當某一塊內(nèi)存使用完畢后，我該怎樣還給堆區(qū)這片區(qū)域。

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

從停車場到內(nèi)存管理

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

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

• 快速找到停車位，在內(nèi)存申請中，這涉及到以最大速度找到一塊滿足要求的空閑內(nèi)存

• 盡最大程度利用停車場，我們的停車場應該能停盡可能多的車，在內(nèi)存申請中，這涉及到在給定條件下盡可能多的滿足內(nèi)存申請需求

現(xiàn)在，我們已經(jīng)清楚的理解任務了，那么該怎么實現(xiàn)呢？

任務拆分

現(xiàn)在我們已經(jīng)明確要實現(xiàn)什么以及衡量其好壞的標準，接下來我們就要去設計實現(xiàn)細節(jié)了，讓我們把任務拆分一下，怎么拆分呢？我們可以自己想一下從內(nèi)存的申請到釋放需要哪些細節(jié)。申請內(nèi)存時，我們需要在內(nèi)存中找到一塊大小合適的空閑內(nèi)存分配出去，那么我們怎么知道有哪些內(nèi)存塊是空閑的呢？

編輯

因此，第一個實現(xiàn)細節(jié)出現(xiàn)了，我們需要把內(nèi)存塊用某種方式組織起來，這樣我們才能追蹤到每一塊內(nèi)存的分配狀態(tài)?，F(xiàn)在空閑內(nèi)存塊組織好了，那么一次內(nèi)存申請可能有很多空閑內(nèi)存塊滿足要求，那么我們該選擇哪一個空閑內(nèi)存塊分配給用戶呢？

因此，第二個實現(xiàn)細節(jié)出現(xiàn)了，我們該選擇什么樣的空閑內(nèi)存塊給到用戶。接下來我們找到了一塊大小合適的內(nèi)存塊，假設用戶需要16個字節(jié)，而我們找到的這塊空閑內(nèi)存塊大小為32字節(jié)，那么將16字節(jié)分配給用戶后還剩下16字節(jié)，這剩下的內(nèi)存該怎么處理呢？因此，第三個實現(xiàn)細節(jié)出現(xiàn)了，分配出去內(nèi)存后，空閑內(nèi)存塊剩余的空間該怎么處理？

最后，分配給用戶的內(nèi)存使用完畢，這是第四個細節(jié)出現(xiàn)了，我們該怎么處理用戶還給我們的內(nèi)存呢？以上四個問題是任何一個內(nèi)存分配器必須要回答的，接下來我們就一一解決這些問題，解決完這些問題后一個嶄新的內(nèi)存分配器就誕生啦。

管理空閑內(nèi)存塊

空閑內(nèi)存塊的本質(zhì)是需要某種辦法來來區(qū)分哪些是空閑內(nèi)存哪些是已經(jīng)分配出去的內(nèi)存。有的同學可能會說，這還不簡單嗎，用一個鏈表之類的結構記錄下每個空閑內(nèi)存塊的開始和結尾不就可以了，這句話也對也不對。

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

說對也對，我們確實需要一個類似鏈表這樣的結構來維護空閑內(nèi)存塊，但這個鏈表并不是我們常見的那種。因為我們無法將空閑內(nèi)存塊的信息保存在其它地方，那么沒有辦法，我們只能將維護內(nèi)存塊的分配信息保存在內(nèi)存塊本身中，這也是大多數(shù)內(nèi)存分配器的實現(xiàn)方法。那么，為了維護內(nèi)存塊分配狀態(tài)，我們需要知道哪些信息呢？很簡單：

• 一個標記，用來標識該內(nèi)存塊是否空閑

• 一個數(shù)字，用來記錄該內(nèi)存塊的大小

為了簡單起見，我們的內(nèi)存分配器不對內(nèi)存對齊有要求，同時一次內(nèi)存申請允許的最大內(nèi)存塊為2G，注意，這些假設是為了方便講解內(nèi)存分配器的實現(xiàn)而屏蔽一些細節(jié)，我們常用的malloc等不會有這樣的限制。因為我們的內(nèi)存塊大小上限為2G，因此我們可以使用31個比特位來記錄塊大小，剩下的一個比特位用來標識該內(nèi)存塊是空閑的還是已經(jīng)被分配出去了，下圖中的f/a是free/allocate，也就是標記是已經(jīng)分配出去還是空閑的。這32個比特位就是header，用來存儲塊信息。

剩下的灰色部分才是真正可以分配給用戶的內(nèi)存，這一部分也被稱為負載，payload，我們調(diào)用malloc返回的內(nèi)存起始地址正是這塊內(nèi)存的起始地址?，F(xiàn)在你應該知道了吧，不是說堆上有10G內(nèi)存，這里面就可以全部用來存儲數(shù)據(jù)的，這里面必然有一部分要拿出來維護內(nèi)存塊的一些信息，就像這里的header一樣。

跟蹤內(nèi)存分配狀態(tài)

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

在這里我們的堆區(qū)還很小，每一方框代表4字節(jié)，其中紅色區(qū)域表示已經(jīng)分配出去的，灰色區(qū)域表示空閑內(nèi)存，每一塊內(nèi)存都有一個header，用帶斜線的方框表示，比如16/1，就表示該內(nèi)存塊大小是16字節(jié)，1表示已經(jīng)分配出去了；而32/0表示該內(nèi)存塊大小是32字節(jié)，0表示該內(nèi)存塊當前空閑。細心的同學可能會問，那最后一個方框0/1表示什么呢？原來，我們需要某種特殊標記來告訴我們的內(nèi)存分配器是不是已經(jīng)到末尾了，這就是最后4字節(jié)的作用。通過引入header我們就能知道每一個內(nèi)存塊的大小，從而可以很方便的遍歷整個堆區(qū)。遍歷方法很簡單，因為我們知道每一塊的大小，那么從當前的位置加上當前塊的大小就是下一個內(nèi)存塊的起始位置，如圖所示：

通過每一個header的最后一個bit位就能知道每一塊內(nèi)存是空閑的還是已經(jīng)分配出去了，這樣我們就能追蹤到每一個內(nèi)存塊的分配信息，因此上文提到的第一個問題解決了。接下來我們看第二個問題。

怎樣選擇空閑內(nèi)存塊

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

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

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

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

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

這就是更加大名鼎鼎的《計算機程序設計藝術》，這本書就是Donald Knuth寫的，如果你沒有聽過這本書請面壁思過一分鐘，比爾蓋茨曾經(jīng)說過，如果你看懂了這本書就去給微軟投簡歷吧，這本書也是很多程序員買回來后從來不會翻一眼只是拿來當做鎮(zhèn)宅之寶用的。不止比爾蓋茨，有一次喬布斯見到Knuth老爺子后。。算了，扯遠了，有機會再和大家講這個故事，拉回來。Next Fit說的是什么呢？這個策略和First Fit很相似，是說我們別總是從頭開始找了，而是從上一次找到合適的空閑內(nèi)存塊的位置找起，老爺子觀察到上一次找到某個合適的內(nèi)存塊的地方很有可能剩下的內(nèi)存塊能滿足接下來的內(nèi)存分配請求，由于不需要從頭開始搜索，因此Next Fit將遠快于First Fit。

然而也有研究表明Next Fit方法內(nèi)存使用率不及First Fit，也就是同樣的停車場面積，F(xiàn)irst Fit方法能停更多的車。

Best FitFirst Fit和Next Fit都是找到第一個滿足要求的內(nèi)存塊就返回，但Best Fit不是這樣。Best Fit算法會找到所有的空閑內(nèi)存塊，然后將所有滿足要求的并且大小為最小的那個空閑內(nèi)存塊返回，這樣的空閑內(nèi)存塊才是最Best的，因此被稱為Best Fit。就像下圖雖然有三個空閑內(nèi)存塊滿足要求，但是Best Fit會選擇大小為8字節(jié)的空閑內(nèi)存塊。

顯然，從直覺上我們就能得出Best Fit會比前兩種方法能更合理利用內(nèi)存的結論，各項研究也證實了這一點。然而Best Fit最大的缺點就是分配內(nèi)存時需要遍歷堆上所有的空閑內(nèi)存塊，在速度上顯然不及前面兩種方法。以上介紹的這三種策略在各種內(nèi)存分配器中非常常見，當然分配策略遠不止這幾種，但這些算法不是該主題下關注的重點，因此就不在這里詳細闡述了，假設在這里我們選擇First Fit算法。

沒有銀彈

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

其實不止內(nèi)存分配器，在設計其它軟件系統(tǒng)時我們也沒有銀彈。

分配內(nèi)存

現(xiàn)在我們找到合適的空閑內(nèi)存塊了，接下來我們又將面臨一個新的問題。如果用戶需要12字節(jié)，而我們的空閑內(nèi)存塊也恰好是12字節(jié)，那么很好，直接返回就可以了。但是，如果用戶申請12字節(jié)內(nèi)存，而我們找到的空閑內(nèi)存塊大小為32字節(jié)，那么我們是要將這32字節(jié)的整個空閑內(nèi)存塊標記為已分配嗎？就像這樣：

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

一種顯而易見的方法就是將空閑內(nèi)存塊進行劃分，前一部分設置為已分配，返回給內(nèi)存申請者使用，后一部分變?yōu)橐粋€新的空閑內(nèi)存塊，只不過大小會更小而已，就像這樣：

我們需要將空閑內(nèi)存塊大小從32修改為16，其中消息頭header占據(jù)4字節(jié)，剩下的12字節(jié)分配出去，并將標記為置為1，表示該內(nèi)存塊已分配。分配出16字節(jié)后，還剩下16字節(jié)，我們需要拿出4字節(jié)作為新的header并將其標記為空閑內(nèi)存塊。

釋放內(nèi)存

到目前為止，我們的malloc已經(jīng)能夠處理內(nèi)存分配請求了，還差最后的內(nèi)存釋放。內(nèi)存釋放和我們想象的不太一樣，該過程并不比前幾個環(huán)節(jié)簡單。我們要考慮到的關鍵一點就在于，與被釋放的內(nèi)存塊相鄰的內(nèi)存塊可能也是空閑的。如果釋放一塊內(nèi)存后我們僅僅簡單的將其標志位置為空閑，那么可能會出現(xiàn)下面的場景：

從圖中我們可以看到，被釋放內(nèi)存的下一個內(nèi)存塊也是空閑的，如果我們僅僅將這16個字節(jié)的內(nèi)存塊標記為空閑的話，那么當下一次申請20字節(jié)時圖中的這兩個內(nèi)存塊都不能滿足要求，盡管這兩個空閑內(nèi)存塊的總數(shù)要超過20字節(jié)。因此一種更好的方法是當應用程序向我們的malloc釋放內(nèi)存時，我們查看一下相鄰的內(nèi)存塊是否是空閑的，如果是空閑的話我們需要合并空閑內(nèi)存塊，就像這樣：

在這里我們又面臨一個新的決策，那就是釋放內(nèi)存時我們要立即去檢查能否夠合并相鄰空閑內(nèi)存塊嗎？還是說我們可以推遲一段時間，推遲到下一次分配內(nèi)存找不到滿足要的空閑內(nèi)存塊時再合并相鄰空閑內(nèi)存塊。釋放內(nèi)存時立即合并空閑內(nèi)存塊相對簡單，但每次釋放內(nèi)存時將引入合并內(nèi)存塊的開銷，如果應用程序總是釋放12字節(jié)然后申請12字節(jié)，然后在釋放12字節(jié)等等這樣重復的模式：

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

那么這種內(nèi)存使用模式對立即合并空閑內(nèi)存塊這種策略非常不友好，我們的內(nèi)存分配器會有很多的無用功。但這種策略最為簡單，在這里我們依然選擇使用這種簡單的策略。實際上我們需要意識到，實際使用的內(nèi)存分配器都會有某種推遲合并空閑內(nèi)存塊的策略。

高效合并空閑內(nèi)存塊

合并空閑內(nèi)存塊的故事到這里就完了嗎？問題沒有那么簡單。讓我們來看這樣一個場景：

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

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

Knuth老爺子的設計是這樣的，我們不是有一個信息頭header嗎，那么我們就在該內(nèi)存塊的末尾再加一個信息尾，footer，footer一詞用的很形象，header和footer的內(nèi)容是一樣的。因為上一內(nèi)存塊的footer和下一個內(nèi)存塊的header是相鄰的，因此我們只需要在當前內(nèi)存塊的位置向上移動4直接就可以等到上一個內(nèi)存塊的信息，這樣當我們釋放內(nèi)存時就可以快速的進行相鄰空閑內(nèi)存塊的合并了。

收工

至此，我們的內(nèi)存分配器就已經(jīng)設計完畢了。我們的簡單內(nèi)存分配器采用了First Fit分配算法；找到一個滿足要求的內(nèi)存塊后會進行切分，剩下的作為新的內(nèi)存塊；同時當釋放內(nèi)存時會立即合并相鄰的空閑內(nèi)存塊，同時為加快合并速度，我們引入了Donald Knuth的設計方法，為每個內(nèi)存塊增加footer信息。這樣，我們自己實現(xiàn)的內(nèi)存分配就可以運行起來了，可以真正的申請和釋放內(nèi)存。

總結

本文從0到1實現(xiàn)了一個簡單的內(nèi)存分配器，但不希望這里的闡述給大家留下內(nèi)存分配器實現(xiàn)很簡單的印象，實際上本文實現(xiàn)的內(nèi)存分配器還有大量的優(yōu)化空間，同時我們也沒有考慮線程安全問題，但這些都不是本文的目的。本文的目的在于把內(nèi)存分配器的本質(zhì)告訴大家，對于想理解內(nèi)存分配器實現(xiàn)原理的同學來說這些已經(jīng)足夠了，而對于要編寫高性能程序的同學來說實現(xiàn)自己的內(nèi)存池是必不可少的，內(nèi)存池實現(xiàn)也離不開這里的討論。希望本文對大家理解內(nèi)存分配器有幫助。