malloc底層為什么是內存池

malloc大家都用過，其是庫函數。我們都知道庫函數在不同的操作系統中其實執行的是系統調用，那么malloc在Linux上執行的是哪個系統調用呢？

brk()和mmap()，至于為什么是兩個，這跟ptmalloc內存池的分配策略有關，稍后介紹。

既然是系統調用，那么就必須處于內核態去處理，而系統內核態的進入往往又經過中斷機制。

其大概來說是這么個經過：

1.保存用戶當前棧esp和頁ss

2.切換到內核態

3.根據中斷號找到相應的處理函數

4.執行完后恢復棧esp和頁ss

所以說，這個系統調用的開銷是比較大的。看一下以下代碼：

for(int i=0;i< 100000;i++)
{
	int* p = (int*)malloc(sizeof(int)); 
}

如果不采用內存池的設計，這個代碼就會執行10w次系統調用，這無疑是非常大的開銷。

ptmalloc的設計概念

Linux下的內存分配

剛剛說了malloc執行的是兩個系統調用，分別是brk和mmap，那么這兩個又有什么區別呢？

先來看看Linux下內存的一個布局：

在這里我們可以著重關注兩個區：heap（堆區） memory mapping（內存映射區）

為什么著重說他們兩個呢？

因為與ptmalloc分配策略息息相關。

brk函數其實就是在heap分配空間，在ptmalloc的設計中有start_brk和brk兩個標志，他們兩個的差值標記著堆區的大小。一開始這兩個值是相同的，但是隨著ptmalloc去調用brk函數，brk標記不斷向高地址區域偏移，標記著heap堆區被分配出去了。

mmap函數則是在memory mapping區域分配空間，memory mapping區域除了我們常知道的映射動態庫對象或者文件，其空間還可以被mmap映射至物理內存。

分配區

分配區的概念是針對多線程來說的，當在多線程的條件下，一個進程會有一個一個主分配區和0至多個從分配區。為什么要這么設計呢？

主分配區和從分配區：
主分配區一個進程只能有一個，其是調用brk，從堆區去分配內存。
從分配區一個線程可以擁有多個從分配區，其調用mmap從memory mapping區域去分配一個sub-heap

因為內存是存在競爭的，為了線程安全，當一個線程在使用這個分配區的時候，其他線程不可訪問，這個時候又不可能給這個線程掛起，掛起多線程存在的意義何在？

所以，ptmalloc這里的策略就是開辟一個新的分配區，這個新的分配區一定是從分配區。一般來說，從分配區的數量不會超過線程數。

而所有的分配區會被指針相連，形成一個環形鏈表，保證每個分配區都盡可能的被用到。

chunk塊是什么？

chunk塊是ptmalloc中最基本的內存單元，ptmalloc把它組織成一個雙向鏈表，每次分配都是從這個鏈表的尾部去取chunk塊，用完了再把它插入到鏈表的頭部。

bins又是什么？

bins是ptmalloc用來維護chunk的一個數據結構，其和哈希思想十分相似。bins本身可以看成一個數組，這個數組總共有128個整型數據，每個整型數據叫bin，其中第1個整型數據表示unsorted bin，其是用來chunk復用或者釋放策略實施的。從第2個bin到第64個bin統稱為small bins，每個相鄰的samll bin相差8，這個bin上代表的數據就是其維護的chunk中可用給用戶的字節大小。從第65個開始到127個就屬于large bins了，每個相鄰的large bin相差64。

Fast Bins

一般情況下，程序其實對小塊內存是十分熱衷的。當分配其剛剛合并了幾塊小的chunk之后，也許又有一個小塊內存的需求，那么這個時候我又需要去切割chunk塊，這想想就挺低效的。

所以ptmalloc的策略是維護一個Fast Bin，這個bin中維護小于等于64B的chunk。

當一個小于64B的chunk被釋放后，首先會被放在Fast Bin中斌給不改變其標志位P，這樣也就無法去合并這個chunk塊。但是在一個特定的時候，ptmalloc會便利fast bins中的chunk塊，合并相鄰的空閑啊chunk塊，并且將其添加到unsorted bin 中，然后加入到相應的bins中。

unsorted bin

unsorted bin的隊列中使用bins數組的第一個，如果是釋放的chunk大于64B，這個chunk就會被放在這里。

當分配的時候，優先去fast bins中去找，沒有找到就去unsorted bin，如果這里也沒找到，ptmalloc就會將unsorted bin中的代碼加入bins中，然后去bins中找。

top chunk

并不是所有的chunk都是由bin去維護的，有三個例外情況：top chunk，mmaped chunk和last remainder（不講）。

剛剛說了，從分配去會從memory mapping區域去分配一個sub-heap。在這個內存的最高處就會存在一個top chunk，當bins也不能滿足用戶需求的時候，才去這個top chunk去分配空間，如果top chunk也不夠，那么再分配一個sub-heap，合并。

mmaped chunk

如果top chunk也不能滿足要求，那么ptmalloc就會使用mmap直接去將頁映射到內存空間，這個chunk在被free的時候直接解除映射。

ptmalloc 的分配策略

獲取分配區鎖，加鎖成功則使用該分配區分配內存，否則就遍歷分配區的環形鏈表。如果鏈表中沒有空閑的，就開辟一個新的分配區，把其加入線程私有實例并且加入到環形鏈表。
將用戶請求的字節向上對齊到bins中的最近字節。
如果小于64B就在fast bin中分配內存，如果大于再去判斷是否小于512B，如果小于就去small bin中分配大小，如果大于就說明此時分配的是大內存。
首先會將fast bin中的chunk進行合并，然后鏈接至unsorted bin，再將其鏈接到相應的bin中
然后去large bins中進行尋找，如果夠用結束，不夠下一步。
這個時候就需要判斷top chunk是否夠用，不夠用下一步
有兩種選擇，判斷分配的字節大小是否大于等于mmap分配閾值，如果小于根據分配區去選擇brk還是mmap去增加top chunk的大小；如果大于就直接調用mmap去映射。

ptmalloc 的內存釋放策略

獲取分配區的鎖
判斷free參數是否位nullptr，如果為nullptr則什么都不做
如果釋放空間為mmaped chunk，直接使用munmap釋放
如果size < 64B且不和top chunk相鄰，放入fast bin
判斷前一個塊是否空閑，空閑則合并
判斷下一個是否空閑，空閑則合并放入unsorted bin，然后放入相應的bin中
判讀合并后是否大于64kb，如果大于fast bin中chunk進行合并，放入unsorted bin，然后下一步。
判讀top chunk是否大于128kb，如果大于就會歸還給操作系統。注意：如果為非主分配區，就只會歸還一部部分。

可以看到，只有當chunk前后合并之后大于64k才會進行堆收縮策略，但是實際上，這個條件比較難以觸發，ptmalloc管理的內存是越分配越多的。

在這個時候，一般都會給項目配上自己相應的內存池。這個就是二級空間配置器。

SGI STL 二級空間配置器

SGI也實現了自己相應的內存池，稱為二級空間配置器。而malloc所依賴的ptmalloc則是一級空間配置器。

SGI這里的策略是，對于大于128字節的數據，調用malloc進行分配，而小于的，則是在自己實現的內存池中進行分配。

這個自己實現的內存池，基本和ptmalloc中bin的思想一致。

但是這里有一點是要注意的，它不是從尾部分配，其每個bin的指針指向了下一個空閑的chunk，如果歸還了，則使用鏈表的頭插法。而在一開始，以8字節為例，他會分配20個chunk塊，其中10個返回給用戶使用，剩下10個備用。如果下次分配24字節，則會從備用的chunk中分出3*8=24，三個chunk塊。