自己擼了一個 malloc 內存分配器~

大家好，我是小北。

**昨天文章中我說內存管理是非常重要的編程基礎，**對內存分配器透徹理解是編程高手的標誌之一。

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

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

還有什麼能比你自己動手實現一個理解的更透徹嗎？

接下來，我們就自己實現一個 malloc 內存分配器。讀完本文後內存分配對你將不再是一個神祕的黑盒。

在講解實現原理之前，我們需要回答一個基本問題，那就是我們爲什麼要發明內存分配器這種東西。

內存申請與釋放

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

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

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

知道了爲什麼要發明內存分配器的原因後，接下來我們着手實現一個。

程序員應如何看待內存

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

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

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

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

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

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

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

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

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

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

從停車場到內存管理

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

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

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

任務拆分

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

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

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

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

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

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

接下來我們找到了一塊大小合適的內存塊，假設用戶需要 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 信息。

這樣，我們自己實現的內存分配就可以運行起來了，可以真正的申請和釋放內存。

總結

本文從 0 到 1 實現了一個簡單的內存分配器，但不希望這裏的闡述給大家留下內存分配器實現很簡單的印象，實際上本文實現的內存分配器還有大量的優化空間，同時我們也沒有考慮線程安全問題，但這些都不是本文的目的。

本文的目的在於把內存分配器的本質告訴大家，對於想理解內存分配器實現原理的同學來說這些已經足夠了，而對於要編寫高性能程序的同學來說實現自己的內存池是必不可少的，內存池實現也離不開這裏的討論。

希望本文對大家理解內存分配器有幫助。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/8PIPY2MUqq01bQf5iEjCcQ

猜你喜歡