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

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

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

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

其大概來說是這么個經(jīng)過：

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

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

3.根據(jù)中斷號找到相應的處理函數(shù)

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

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

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

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

ptmalloc的設計概念

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

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

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

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

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

因為與ptmalloc分配策略息息相關(guān)。

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

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

分配區(qū)

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

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

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

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

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

chunk塊是什么？

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

bins又是什么？

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

Fast Bins

一般情況下，程序其實對小塊內(nèi)存是十分熱衷的。當分配其剛剛合并了幾塊小的chunk之后，也許又有一個小塊內(nèi)存的需求，那么這個時候我又需要去切割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數(shù)組的第一個，如果是釋放的chunk大于64B，這個chunk就會被放在這里。

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

top chunk

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

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

mmaped chunk

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

ptmalloc 的分配策略

1. 獲取分配區(qū)鎖，加鎖成功則使用該分配區(qū)分配內(nèi)存，否則就遍歷分配區(qū)的環(huán)形鏈表。如果鏈表中沒有空閑的，就開辟一個新的分配區(qū)，把其加入線程私有實例并且加入到環(huán)形鏈表。
2. 將用戶請求的字節(jié)向上對齊到bins中的最近字節(jié)。
3. 如果小于64B就在fast bin中分配內(nèi)存，如果大于再去判斷是否小于512B，如果小于就去small bin中分配大小，如果大于就說明此時分配的是大內(nèi)存。
4. 首先會將fast bin中的chunk進行合并，然后鏈接至unsorted bin，再將其鏈接到相應的bin中
5. 然后去large bins中進行尋找，如果夠用結(jié)束，不夠下一步。
6. 這個時候就需要判斷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. 判斷前一個塊是否空閑，空閑則合并
6. 判斷下一個是否空閑，空閑則合并放入unsorted bin，然后放入相應的bin中
7. 判讀合并后是否大于64kb，如果大于fast bin中chunk進行合并，放入unsorted bin，然后下一步。
8. 判讀top chunk是否大于128kb，如果大于就會歸還給操作系統(tǒng)。注意：如果為非主分配區(qū)，就只會歸還一部部分。

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

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

SGI STL 二級空間配置器

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

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

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

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