tbox中內存池架構
TBOX的內存管理模型，參考了linux kernel的內存管理機制，并在其基礎上做了一些改進和優化。
內存整體架構
large_pool
整個內存分配的最底層，都是基于large_pool的大塊內存分配池，類似于linux的基于page的分配管理，不過有所不同的是，large_pool并沒有像linux那樣使用buddy算法進行(2^N)*page進行分配，這樣如果需要2.1m的內存，需要分配4m的內存塊，這樣力度太大，非常浪費。
因此large_pool內部采用N*page的基于page_size為最小粒度進行分配，因此每次分配頂多浪費不到一頁的空間。
而且如果需要的內存不到整頁，剩下的內存也會一并返回給上層，如果上層需要（比如small_pool），可以充分利用這多余的部分內存空間，使得內存利用率達到最優化。
而且根據tb_init實際傳入的參數需求，large_pool有兩種模式：
-
直接使用系統內存分配接口將進行大塊內存的分配，并用雙鏈維護，這種比較簡單，就不多說了。
-
在一大塊連續內存上進行統一管理，實現內存分配。
具體使用哪種方式，根據應用需求，一般的應用只需要使用方式1就行了，這個時候tb_init傳tb_null就行了，如果是嵌入式應用，需要管理有限的一塊內存空間，這個時候可以使用方式2， tb_init傳入指定內存空間地址和大小。
這里就主要看下方式2的large_pool的內存結構（假設頁大小是4KB）：
--------------------------------------------------------------------------
| data |
--------------------------------------------------------------------------
|
--------------------------------------------------------------------------
| head | 4KB | 16KB | 8KB | 128KB | ... | 32KB | ... | 4KB*N |
-------------------------------------------------------------------------- 由于large_pool主要用于大塊分配，而超小塊的分配在上層small_pool中已經被分流掉了，所以這個應用中，large_pool不會太過頻繁的分配，所以碎片量不會太大，為了進一步減少碎片的產生，在free時候都會對下一個鄰近的空閑塊進行合并。而malloc在分配當前空閑塊空間不夠的情況下，也會嘗試對下一個鄰近空閑塊進行合并。
由于每個內存塊都是鄰近挨著的，也沒用雙鏈維護，沒有內存塊，都有個塊頭，合并過程僅僅只是改動內存塊頭部的size字段，這樣的合并不會影響效率。
由于沒像buddy算法那樣，用雙鏈維護空閑內存，雖然節省了鏈表維護的空間和時間，但是每次分配內存都要順序遍歷所有塊，來查找空閑的內存，這樣的效率實在太低了，為了解決這個問題，large_pool內部針對不同級別的塊，進行了預測，每次free或者malloc的時候，如果都會把當前和鄰近的空閑快，緩存到對應級別的預測池里面去，具體的分級如下：
-------------------------------------- | >0KB : 4KB | > 0*page | |-----------------------|-------------- | >4KB : 8KB | > 1*page | |-----------------------|-------------- | >8KB : 12-16KB | > 2*page | |-----------------------|-------------- | >16KB : 20-32KB | > 4*page | |-----------------------|-------------- | >32KB : 36-64KB | > 8*page | |-----------------------|-------------- | >64KB : 68-128KB | > 16*page | |-----------------------|-------------- | >128KB : 132-256KB | > 32*page | |-----------------------|-------------- | >256KB : 260-512KB | > 64*page | |-----------------------|-------------- | >512KB : 516-1024KB | > 128*page | |-----------------------|-------------- | >1024KB : 1028-...KB | > 256*page | --------------------------------------
由于通常不會分配太大塊的內存，因此只要能夠預測1m內存，就足夠，而對于>1m的內存，這里也單獨加了一個預測，來應對偶爾的超大塊分配，并且使得整體分配流程更加的統一。
如果當前級別的預測塊不存在，則會到下一級別的預測塊中查找，如果都找不到，才回去遍歷整個內存池。
實際測試下，每個塊的預測成功基本都在95%以上，也就說大部分情況下，分配效率都是維持在O(1)級別的。
small_pool
小塊內存分配池
在上層每次調用malloc進行內存分配的時候，回去判斷需要多大的內存，如果這個內存超過或者等于一頁，則會直接從large_pool進行分配，如果小于一頁，則會優先通過small_pool進行分配，small_pool針對小塊的內存進行了高速緩存，并優化了空間管理和分配效率。
由于程序大部分情況下，都在使用小塊內存，因此small_pool對內存的分配做了很大的分流，使得large_pool承受的壓力減小，碎片量減少很多，而small_pool內部由于都是由fixed_pool來對固定大小的內存進行管理，是不會存在外部碎片的。而小塊內存的粒度本身就很小，所以內部碎片量也相當少。
small_pool中的fixed_pool，就像是linux kernel中的slub，在small_pool中總共有12級別的fixed_pool，每個級別分別管理一種固定大小的內存塊，具體級別如下：
-------------------------------------- | fixed pool: 16B | 1-16B | |--------------------------------------| | fixed pool: 32B | 17-32B | |--------------------------------------| | fixed pool: 64B | 33-64B | |--------------------------------------| | fixed pool: 96B* | 65-96B* | |--------------------------------------| | fixed pool: 128B | 97-128B | |--------------------------------------| | fixed pool: 192B* | 129-192B* | |--------------------------------------| | fixed pool: 256B | 193-256B | |--------------------------------------| | fixed pool: 384B* | 257-384B* | |--------------------------------------| | fixed pool: 512B | 385-512B | |--------------------------------------| | fixed pool: 1024B | 513-1024B | |--------------------------------------| | fixed pool: 2048B | 1025-2048B | |--------------------------------------| | fixed pool: 3072B* | 2049-3072B* | --------------------------------------
其中 96B, 192B，384B，3072B并不是按2的整數冪大小，這么做主要是為了更加有效的利用小塊內存的空間減少內部碎片。
fixed_pool
顧名思義，fixed_pool就是用來管理固定大小的內存分配的，相當于linux中slub，而fixed_pool中又由多個slot組成，每個slot負責一塊連續的內存空間，管理部分內存塊的管理，類似linux中的slab， 每個slot由雙鏈維護，并且參考linux的管理機制，分為三種slot管理方式：
-
當前正在分配的slot
-
部分空閑slots鏈表
-
完全full的slots鏈表
具體結構如下：
current:
--------------
| |
-------------- |
| slot |<--
|--------------|
||||||||||||||||
|--------------|
| |
|--------------|
| |
|--------------|
||||||||||||||||
|--------------|
||||||||||||||||
|--------------|
| |
--------------
partial:
-------------- -------------- --------------
| slot | <=> | slot | <=> ... <=> | slot |
|--------------| |--------------| |--------------|
|||||||||||||||| | | | |
|--------------| |--------------| |--------------|
| | |||||||||||||||| | |
|--------------| |--------------| |--------------|
| | |||||||||||||||| ||||||||||||||||
|--------------| |--------------| |--------------|
|||||||||||||||| |||||||||||||||| | |
|--------------| |--------------| |--------------|
|||||||||||||||| | | | |
|--------------| |--------------| |--------------|
| | | | ||||||||||||||||
-------------- -------------- --------------
full:
-------------- -------------- --------------
| slot | <=> | slot | <=> ... <=> | slot |
|--------------| |--------------| |--------------|
|||||||||||||||| |||||||||||||||| ||||||||||||||||
|--------------| |--------------| |--------------|
|||||||||||||||| |||||||||||||||| ||||||||||||||||
|--------------| |--------------| |--------------|
|||||||||||||||| |||||||||||||||| ||||||||||||||||
|--------------| |--------------| |--------------|
|||||||||||||||| |||||||||||||||| ||||||||||||||||
|--------------| |--------------| |--------------|
|||||||||||||||| |||||||||||||||| ||||||||||||||||
|--------------| |--------------| |--------------|
|||||||||||||||| |||||||||||||||| ||||||||||||||||
-------------- -------------- -------------- 具體的分配算法
-
如果當前slot中還有空閑的塊，優先從當前slot進行分配
-
如果當前slot中沒有空閑塊，則把這個slot放到full鏈表中去
-
從部分空閑slot鏈表中，挑一個空閑的slot進行分配，并把它設為當前分配狀態。
具體的釋放算法
-
釋放后如果這個slot完全空閑了，并且不是正在分配的slot，則把整個slot釋放掉，這樣既可以保證有一個可以分配的slot之外，還極大的降低了內存使用，也避免某些情況下頻繁的釋放分配slot。
-
如果釋放的slot屬于full鏈表并且變為了部分空閑，則把這個slot移到部分空閑slot鏈表中去。
額外要提一下的是：
large_pool每次分配一塊空間給一個slot的時候，殘留下來的部分剩余空間(<1*page)， 也能直接返回給slot，讓slot充分利用這部分數據，這樣可以可以切分出更多地內存塊。
例如：
fixed_pool每次增長一個包含256個32B內存塊的slot（需要8192B大小+16B內部數據維護大小），其實在用large_pool分配的時候，需要8208B的大小，由于需要按頁對齊（4KB），實際分配確占用了 8192+4096: 12288B 的大小的空間。
但是large_pool支持把所有空間數據一并返回給上層，這樣slot其實獲取到了一個12288B大小的內存，并且也知道其實際大小為：12288B，因此實際切分了 (12288-(32B的slot內部維護數據))/32 也就是383個內存塊。
多維護了127個內存塊，充分把large_pool的內部碎片也利用上了，進一步增加了內存利用率。
fixed_pool中的slot
雖然類比與linux中的slab，但是其數據結構確跟slab不太一樣，它并沒有像slab那樣，對每個空閑小塊都用鏈表維護，而是直接用位段來維護是否空閑的信息，這樣更加節省內存，而且通過優化算法，其分配效率和slab幾乎一樣。
在fixed_pool的slot的頭部，專門有一小塊獨立的數據，用于維護每個小塊的空閑信息，每個塊只暫用一比特位的信息，來判斷這個塊是否空閑，由于沒有內存塊都是固定大小的，所以比特位的位置定位，完全可以通過索引計算得到。
而且每次釋放和分配，都會去緩存一個雙字大小的位信息端，來預測下一次的分配，由于是雙字大小，總共有32個比特位，所以每次緩存，最多可以預測鄰近32個內存塊。因此大部分情況下，預測成功率一直都是>98%的，分配效率都維持在O(1)，比起large_pool的預測率還高很多，所以small_pool對large_pool的分流，還在一定程度上，進一步提高了內存分配效率。
而就算很倒霉，沒預測成功，slot的順序遍歷來查找空閑快的算法，也相當高效，完全是高度優化的，下面就詳細描述下。
slot的順序遍歷分配算法優化
我們這里主要用到了gcc的幾個內置函數：
-
__builtin_clz：計算32位整數前導0的個數
-
__builtin_ctz：計算32位整數后置0的個數
-
__builtin_clzll：計算64位整數前導0的個數
-
__builtin_ctzll：計算64位整數后置0的個數
其實這四個類似，我們這里就拿第一說明好了，為什么要使用__builtin_clz呢？其實就是為了在一個32位端里面，快速查找某個空閑位的索引，這樣就能快速定位某個空閑塊的位置了。
比如有一個32位的位段信息整數：x，計算對應空閑位0的索引，主需要： __builtin_clz(~x)
簡單吧，由于__builtin_clz這些內置函數，gcc用匯編針對不同平臺高度優化過的，計算起來相當的快，那如果不是gcc的編譯器怎么辦呢？
沒關系，我們可以自己用c實現個優化版本的，當然完全可以匯編繼續優化，這里就先給個c的實現：
<!--lang:cpp-->
static __tb_inline__ tb_size_t tb_bits_cl0_u32_be_inline(tb_uint32_t x)
{
// check
tb_check_return_val(x, 32);
// done
tb_size_t n = 31;
if (x & 0xffff0000) { n -= 16; x >>= 16; }
if (x & 0xff00) { n -= 8; x >>= 8; }
if (x & 0xf0) { n -= 4; x >>= 4; }
if (x & 0xc) { n -= 2; x >>= 2; }
if (x & 0x2) { n--; }
return n;
} 說白了，就是每次對半開，來減少判斷次數，比起每次一位一位的枚舉遍歷，這種已經是相當高效了，更何況還有__builtin_clz呢。
接下來就看下具體的遍歷過程：
-
按4/8字節對齊位段的起始地址
-
每次按4/8字節遍歷位段數據，遍歷過程利用cpu cache的大小，針對性的做循環展開，來優化性能。
-
通過判斷 !(x + 1) 來快速過濾 0xffffffff 這些已經滿了的位段，進一步提高遍歷效率。
-
如果某個位段不是0xffffffff，則通過__builtin_clz(~x)計算實際的空閑塊索引，并進行實際的分配。
-
最后如果這個的32位的位段沒有被分配滿，可以把它進行緩存，來為下次分配做預測。
string_pool
講到這，TBOX的內存池管理模型，基本算是大概講完了，這里就簡單提下string_pool，即：字符串池
string_pool主要針對上層應用而言的，針對某些頻繁使用小型字符串，并且重復率很高的模塊，就可以通過string_pool進行優化，進一步減少內存使用，string_pool內部通過引用計數+哈希表維護，針對相同的字符串只保存一份。
例如可以用于cookies中字符串維護、http中header部分的字符串維護等等。。