malloc底層為什么是內(nèi)存池

malloc大家都用過(guò)，其是庫(kù)函數(shù)。我們都知道庫(kù)函數(shù)在不同的操作系統(tǒng)中其實(shí)執(zhí)行的是系統(tǒng)調(diào)用，那么malloc在Linux上執(zhí)行的是哪個(gè)系統(tǒng)調(diào)用呢？

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

既然是系統(tǒng)調(diào)用，那么就必須處于內(nèi)核態(tài)去處理，而系統(tǒng)內(nèi)核態(tài)的進(jìn)入往往又經(jīng)過(guò)中斷機(jī)制。

其大概來(lái)說(shuō)是這么個(gè)經(jīng)過(guò)：

1.保存用戶當(dāng)前棧esp和頁(yè)ss

2.切換到內(nèi)核態(tài)

3.根據(jù)中斷號(hào)找到相應(yīng)的處理函數(shù)

4.執(zhí)行完后恢復(fù)棧esp和頁(yè)ss

所以說(shuō)，這個(gè)系統(tǒng)調(diào)用的開(kāi)銷是比較大的?？匆幌乱韵麓a：

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

如果不采用內(nèi)存池的設(shè)計(jì)，這個(gè)代碼就會(huì)執(zhí)行10w次系統(tǒng)調(diào)用，這無(wú)疑是非常大的開(kāi)銷。

ptmalloc的設(shè)計(jì)概念

Linux下的內(nèi)存分配

剛剛說(shuō)了malloc執(zhí)行的是兩個(gè)系統(tǒng)調(diào)用，分別是brk和mmap，那么這兩個(gè)又有什么區(qū)別呢？

先來(lái)看看Linux下內(nèi)存的一個(gè)布局：

在這里我們可以著重關(guān)注兩個(gè)區(qū)：heap（堆區(qū)） memory mapping（內(nèi)存映射區(qū)）

為什么著重說(shuō)他們兩個(gè)呢？

因?yàn)榕cptmalloc分配策略息息相關(guān)。

brk函數(shù)其實(shí)就是在heap分配空間，在ptmalloc的設(shè)計(jì)中有start_brk和brk兩個(gè)標(biāo)志，他們兩個(gè)的差值標(biāo)記著堆區(qū)的大小。一開(kāi)始這兩個(gè)值是相同的，但是隨著ptmalloc去調(diào)用brk函數(shù)，brk標(biāo)記不斷向高地址區(qū)域偏移，標(biāo)記著heap堆區(qū)被分配出去了。

mmap函數(shù)則是在memory mapping區(qū)域分配空間，memory mapping區(qū)域除了我們常知道的映射動(dòng)態(tài)庫(kù)對(duì)象或者文件，其空間還可以被mmap映射至物理內(nèi)存。

分配區(qū)

分配區(qū)的概念是針對(duì)多線程來(lái)說(shuō)的，當(dāng)在多線程的條件下，一個(gè)進(jìn)程會(huì)有一個(gè)一個(gè)主分配區(qū)和0至多個(gè)從分配區(qū)。為什么要這么設(shè)計(jì)呢？

主分配區(qū)和從分配區(qū)：
主分配區(qū)一個(gè)進(jìn)程只能有一個(gè)，其是調(diào)用brk，從堆區(qū)去分配內(nèi)存。
從分配區(qū)一個(gè)線程可以擁有多個(gè)從分配區(qū)，其調(diào)用mmap從memory mapping區(qū)域去分配一個(gè)sub-heap

因?yàn)閮?nèi)存是存在競(jìng)爭(zhēng)的，為了線程安全，當(dāng)一個(gè)線程在使用這個(gè)分配區(qū)的時(shí)候，其他線程不可訪問(wèn)，這個(gè)時(shí)候又不可能給這個(gè)線程掛起，掛起多線程存在的意義何在？

所以，ptmalloc這里的策略就是開(kāi)辟一個(gè)新的分配區(qū)，這個(gè)新的分配區(qū)一定是從分配區(qū)。一般來(lái)說(shuō)，從分配區(qū)的數(shù)量不會(huì)超過(guò)線程數(shù)。

而所有的分配區(qū)會(huì)被指針相連，形成一個(gè)環(huán)形鏈表，保證每個(gè)分配區(qū)都盡可能的被用到。

chunk塊是什么？

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

bins又是什么？

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

Fast Bins

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

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

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

unsorted bin

unsorted bin的隊(duì)列中使用bins數(shù)組的第一個(gè)，如果是釋放的chunk大于64B，這個(gè)chunk就會(huì)被放在這里。

當(dāng)分配的時(shí)候，優(yōu)先去fast bins中去找，沒(méi)有找到就去unsorted bin，如果這里也沒(méi)找到，ptmalloc就會(huì)將unsorted bin中的代碼加入bins中，然后去bins中找。

top chunk

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

剛剛說(shuō)了，從分配去會(huì)從memory mapping區(qū)域去分配一個(gè)sub-heap。在這個(gè)內(nèi)存的最高處就會(huì)存在一個(gè)top chunk，當(dāng)bins也不能滿足用戶需求的時(shí)候，才去這個(gè)top chunk去分配空間，如果top chunk也不夠，那么再分配一個(gè)sub-heap，合并。

mmaped chunk

如果top chunk也不能滿足要求，那么ptmalloc就會(huì)使用mmap直接去將頁(yè)映射到內(nèi)存空間，這個(gè)chunk在被free的時(shí)候直接解除映射。

ptmalloc 的分配策略

1. 獲取分配區(qū)鎖，加鎖成功則使用該分配區(qū)分配內(nèi)存，否則就遍歷分配區(qū)的環(huán)形鏈表。如果鏈表中沒(méi)有空閑的，就開(kāi)辟一個(gè)新的分配區(qū)，把其加入線程私有實(shí)例并且加入到環(huán)形鏈表。
2. 將用戶請(qǐng)求的字節(jié)向上對(duì)齊到bins中的最近字節(jié)。
3. 如果小于64B就在fast bin中分配內(nèi)存，如果大于再去判斷是否小于512B，如果小于就去small bin中分配大小，如果大于就說(shuō)明此時(shí)分配的是大內(nèi)存。
4. 首先會(huì)將fast bin中的chunk進(jìn)行合并，然后鏈接至unsorted bin，再將其鏈接到相應(yīng)的bin中
5. 然后去large bins中進(jìn)行尋找，如果夠用結(jié)束，不夠下一步。
6. 這個(gè)時(shí)候就需要判斷top chunk是否夠用，不夠用下一步
7. 有兩種選擇，判斷分配的字節(jié)大小是否大于等于mmap分配閾值，如果小于根據(jù)分配區(qū)去選擇brk還是mmap去增加top chunk的大??；如果大于就直接調(diào)用mmap去映射。

ptmalloc 的內(nèi)存釋放策略

1. 獲取分配區(qū)的鎖
2. 判斷free參數(shù)是否位nullptr，如果為nullptr則什么都不做
3. 如果釋放空間為mmaped chunk，直接使用munmap釋放
4. 如果size < 64B且不和top chunk相鄰，放入fast bin
5. 判斷前一個(gè)塊是否空閑，空閑則合并
6. 判斷下一個(gè)是否空閑，空閑則合并放入unsorted bin，然后放入相應(yīng)的bin中
7. 判讀合并后是否大于64kb，如果大于fast bin中chunk進(jìn)行合并，放入unsorted bin，然后下一步。
8. 判讀top chunk是否大于128kb，如果大于就會(huì)歸還給操作系統(tǒng)。注意：如果為非主分配區(qū)，就只會(huì)歸還一部部分。

可以看到，只有當(dāng)chunk前后合并之后大于64k才會(huì)進(jìn)行堆收縮策略，但是實(shí)際上，這個(gè)條件比較難以觸發(fā)，ptmalloc管理的內(nèi)存是越分配越多的。

在這個(gè)時(shí)候，一般都會(huì)給項(xiàng)目配上自己相應(yīng)的內(nèi)存池。這個(gè)就是二級(jí)空間配置器。

SGI STL 二級(jí)空間配置器

SGI也實(shí)現(xiàn)了自己相應(yīng)的內(nèi)存池，稱為二級(jí)空間配置器。而malloc所依賴的ptmalloc則是一級(jí)空間配置器。

SGI這里的策略是，對(duì)于大于128字節(jié)的數(shù)據(jù)，調(diào)用malloc進(jìn)行分配，而小于的，則是在自己實(shí)現(xiàn)的內(nèi)存池中進(jìn)行分配。

這個(gè)自己實(shí)現(xiàn)的內(nèi)存池，基本和ptmalloc中bin的思想一致。

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