介紹：
?????? 設計內存池的目標是為了保證服務器長時間高效的運行，通過對申請空間小而申請頻繁的對象進行有效管理，減少內存碎片的產(chǎn)生，合理分配管理用戶內存，從而減少系統(tǒng)中出現(xiàn)有效空間足夠，而無法分配大塊連續(xù)內存的情況。
目標：
??? 此次設計內存池的基本目標，需要滿足線程安全性（多線程），適量的內存泄露越界檢查，運行效率不太低于malloc/free方式，實現(xiàn)對4-128字節(jié)范圍內的內存空間申請的內存池管理（非單一固定大小對象管理的內存池）。
內存池技術設計與實現(xiàn)
??? 本內存池的設計方法主要參考SGI的alloc的設計方案，為了適合一般的應用，并在alloc的基礎上做一些簡單的修改。
??? Mempool的內存池設計方案如下（也可參考候捷《深入剖析STL》）
??? 從系統(tǒng)申請大塊heap內存，在此內存上劃分不同大小的區(qū)塊，并把具有相同大小的區(qū)塊連接起來，組成一個鏈表。比如A大小的塊，組成鏈表L，當申請A大小時，直接從鏈表L頭部（如果不為空）上取到一塊交給申請者，當釋放A大小的塊時，直接掛接到L的頭部。內存池的原理比較簡單，但是在具體實現(xiàn)過程中大量的細節(jié)需要注意。
??? 1：字節(jié)對齊。
??? 為了方便內存池中對象的管理，需要對申請內存空間的進行調整，在Mempool中，字節(jié)對齊的大小為最接近8倍數(shù)的字節(jié)數(shù)。比如，用戶申請5個字節(jié)，Mempool首先會把它調整為8字節(jié)。比如申請22字節(jié)，會調整為24，對比關系如下
|
序號
|
對齊字節(jié)
|
范圍
|
|
0
|
8
|
1-8
|
|
1
|
16
|
9-16
|
|
2
|
24
|
17-24
|
|
3
|
32
|
25-32
|
|
4
|
40
|
33-40
|
|
5
|
48
|
41-48
|
|
6
|
56
|
49-56
|
|
7
|
64
|
57-64
|
|
8
|
72
|
65-72
|
|
9
|
80
|
73-80
|
|
10
|
88
|
81-88
|
|
11
|
96
|
89-96
|
|
12
|
104
|
97-104
|
|
13
|
112
|
105-112
|
|
14
|
120
|
113-120
|
|
15
|
128
|
121-128
|
（圖1）
對于超過128字節(jié)的申請，直接調用malloc函數(shù)申請內存空間。這里設計的內存池并不是對所有的對象進行內存管理，只是對申請內存空間小，而申請頻繁的對象進行管理，對于超過128字節(jié)的對象申請，不予考慮。這個需要與實際項目結合，并不是固定不變的。實現(xiàn)對齊操作的函數(shù)如下
static size_t round_up(size_t size)
{
??????? return (((size)+7) &~ 7);// 按8字節(jié)對齊
}
2：構建索引表
內存池中管理的對象都是固定大小，現(xiàn)在要管理0-128字節(jié)的范圍內的對象申請空間，除了采用上面提到的字節(jié)對齊外，還需要變通一下，這就是建立索引表，做法如下；
static _obj* ?free_list[16];
創(chuàng)建一個包含16個_obj*指針的數(shù)組，關于_obj結構后面詳細講解。free_list[0]記錄所有空閑空間為8字節(jié)的鏈表的首地址；free_list[1]對應16字節(jié)的鏈表，free_list[2]對應24字節(jié)的列表。free_list中的下標和字節(jié)鏈表對應關系參考圖1中的“序號”和“對齊字節(jié)”之間的關系。這種關系，我們很容易用算法計算出來。如下
static size_t freelist_index(size_t size)
{
??????? return (((size)+7)/7-1);// 按8字節(jié)對齊
}
??? 所以，這樣當用戶申請空間A時，我們只是通過上面簡單的轉換，就可以跳轉到包含A字節(jié)大小的空閑鏈表上,如下；
_obj** p = free_list[freelist_index(A)];
3:構建空閑鏈表
通過索引表，我們知道m(xù)empool中維持著16條空閑鏈表，這些空閑鏈表中管理的空閑對象大小分別為8，16，24，32，40…128。這些空閑鏈表鏈接起來的方式完全相同。一般情況下我們構建單鏈表時需要創(chuàng)建如下的一個結構體。
struct Obj
{
??? Obj *next;
??? Char* p;
??? Int iSize;
}
next指針指向下一個這樣的結構，p指向真正可用空間,iSize用于只是可用空間的大小，在其他的一些內存池實現(xiàn)中，還有更復雜的結構體，比如還包括記錄此結構體的上級結構體的指針，結構體中當前使用空間的變量等，當用戶申請空間時，把此結構體添加的用戶申請空間中去，比如用戶申請12字節(jié)的空間，可以這樣做
Obj *p = (Obj*)malloc(12+sizeof(Obj));
p->next = NULL;
p->p = (char*)p+sizeof(Obj);
p->iSize = 12;
但是，我們并沒有采用這種方式，這種方式的一個缺點就是，用戶申請小空間時，內存池加料太多了。比如用戶申請12字節(jié)時，而真實情況是內存池向內存申請了12+ sizeof(Obj)=12+12=24字節(jié)的內存空間，這樣浪費大量內存用在標記內存空間上去，并且也沒有體現(xiàn)索引表的優(yōu)勢。Mempool采用的是union方式
union Obj
{
??? Obj *next;
??? char client_data[1];
}
這里除了把上面的struct修改為union，并把int iSize去掉，同時把char*p，修改為char client_data[1]，并沒有做太多的修改。而優(yōu)勢也恰恰體現(xiàn)在這里。如果采用struct方式，我們需要維護兩條鏈表，一條鏈表是，已分配內存空間鏈表，另一條是未分配（空閑）空間鏈表。而我們使用索引表和union結構體，只需要維護一條鏈表，即未分配空間鏈表。具體如下
索引表的作用有兩條1：如上所說，維護16條空閑鏈表2：變相記錄每條鏈表上空間的大小，比如下標為3的索引表內維持著是大小為24字節(jié)的空閑鏈表。這樣我們通過索引表減少在結構體內記錄p所指向空間大小的iSize變量。從而減少4個字節(jié)。
Union的特性是，結構內的變量是互斥存在的。再運行狀態(tài)下，只是存在一種變量類型。所以在這里sizeof(Obj)的大小為4，難道這里我們也需要把這4字節(jié)也加到用戶申請空間中去嘛？其實不是，如果這樣，我們又抹殺了union的特性。
當我們構建空閑分配鏈表時，我們通過next指向下一個union結構體，這樣我們不使用p指針。當把這個結構體分配出去時，我們直接返回client_data的地址，此時client_data正好指向申請空間的首字節(jié)。所以這樣，我們就不用在用戶申請空間上添加任何東西。
圖2
??? Obj的連接方式如上所示，這樣我們無需為用戶申請空間添加任何內容。???
4：記錄申請空間字節(jié)數(shù)
如果采用面向對象方式，或者我們在釋放內存池的空間時能夠明確知道釋放空間的大小，無需采用這種方式。
圖3
在C語言中的free沒有傳遞釋放空間大小，而可以正確釋放，在這里也是模仿這種方式，采用這種記錄申請空間大小的方式去釋放內存。用戶申請空間+1操作將在字節(jié)對齊之前執(zhí)行，找到合適空間后，把首字節(jié)改寫為申請空間的大小，當然1個字節(jié)最多紀錄256個數(shù)，如果項目需要，可以設置為short類型或者int類型，不過這樣就需要占用用戶比較大的空間。當釋放內存空間時，首先讀取這個字節(jié)，獲取空間大小，進行釋放。為了便于對大于128字節(jié)對象的大小進行合適的釋放，同時也對大于128字節(jié)的內存申請，添加1字節(jié)記錄大小。所以現(xiàn)在這里限制了用戶內存申請空間不得大于255字節(jié)，不過現(xiàn)在已經(jīng)滿足項目要求。當然也可以修改為用short類型記錄申請空間的大小。
??? // 申請
??? *(( unsigned char *)result) = (size_t)n;
????unsigned char * pTemp = (unsigned char*)result;
????++pTemp;
??? result = (_obj*)pTemp;
??? return result;
??? // 釋放
????unsigned char * pTemp = (unsigned char *)ptr;
????--pTemp;
????ptr = (void*)pTemp;
????n = (size_t)(*( unsigned char *)ptr);
5：內存池的分配原理
在內存池的設計中，有兩個重要的操作過程1：chunk_alloc，申請大塊內存，2：refill回填操作，內存池初始化化時并不是為索引表中的每一項都創(chuàng)建空閑分配鏈表，這個過程會推遲到，只有用戶提取請求時才會創(chuàng)建這樣的分配鏈表。詳細參考如下代碼（在sgi中stl_alloc.h文件中你也可以看到這兩個函數(shù)），主要步驟在注釋中已經(jīng)說明。
/**
* @bri: 申請大塊內存，并返回size*(*nobjs)大小的內存塊
* @param: size,round_up對齊后的大小,nobjs
* @return: 返回指向第一個對象內存指針
*/
static char* chunk_alloc(size_t size, int *nobjs)
{
???? /**< 返回指針 */
???? char* __result;
???? /**< 申請內存塊大小 */
???? size_t __total_bytes = size *(*nobjs);
???? /**< 當前內存可用空間 */
???? size_t __bytes_left = _end_free - _start_free;
???? /**< 內存池中還有大片可用內存 */
???? if (__bytes_left >= __total_bytes)
???? {
???????? __result = _start_free;
???????? _start_free += __total_bytes;
???????? return (__result);
???? }
???? /**< 至少還有一個對象大小的內存空間 */
???? else if (__bytes_left >= size)
???? {
???????? *nobjs = (int)(__bytes_left/size);
???????? __total_bytes = size * (*nobjs);
???????? __result = _start_free;
???????? _start_free += __total_bytes;
???????? return (__result);
???? }
???? /**< 內存池中沒有任何空間 */
???? else
???? {
???????? /**< 重新申請內存池的大小 */
???????? size_t __bytes_to_get = 2 * __total_bytes + round_up(_heap_size >> 4);
???????? /**< 把內存中剩余的空間添加到freelist中 */
???????? if(__bytes_left > 0)
???????? {
????????????? _obj *VOLATILE* __my_free_list =?
?????????????????? _free_list + freelist_index(__bytes_left);
????????????? ((_obj*)_start_free)->free_list_link =
*__my_free_list;
????????????? *__my_free_list = (_obj*)_start_free;
???????? }
???????? // 申請新的大塊空間
???????? _start_free = (char*)malloc(__bytes_to_get);
???????? /*=======================================================================*/
???????? memset(_start_free,0,__bytes_to_get);
???????? /*=======================================================================*/
???????? // 系統(tǒng)內存已經(jīng)無可用內存，那么從內存池中壓縮內存
???????? if(0 == _start_free)
???????? {
????????????? size_t __i;
????????????? _obj *VOLATILE* __my_free_list;
????????????? _obj *__p;
????????????? /**< 從freelist中逐項檢查可用空間(此時只收集比size對象大的內存空間) */
????????????? for (__i = size; __i <= (size_t)__MAX_BYTES; __i += __ALIGN)
????????????? {
?????????????????? __my_free_list = _free_list + freelist_index(__i);
?????????????????? __p = *__my_free_list;
?????????????????? /**< 找到空閑塊 */
?????????????????? if (__p != 0)
?????????????????? {
?????????????????????? *__my_free_list = __p->free_list_link;
?????????????????????? _start_free = (char*)__p;
?????????????????????? _end_free = _start_free + __i;
?????????????????????? return (chunk_alloc(size,nobjs));
?????????????????? }
????????????? }
????????????? _end_free = 0;
????????????? /**< 再次申請內存，可能觸發(fā)一個異常 */
????????????? _start_free = (char*)malloc(__bytes_to_get);
???????? }
???????? /**< 記錄當前內存池的容量 */
???????? _heap_size += __bytes_to_get;
???????? _end_free = _start_free + __bytes_to_get;
???????? return (chunk_alloc(size,nobjs));
???? }
}
/*=======================================================================*/
/**
?* @bri: 填充freelist的連接，默認填充20個
?* @param: __n，填充對象的大小，8字節(jié)對齊后的value
?* @return: 空閑
?*/
static void* refill(size_t n)
{
???? int __nobjs = 20;
???? char* __chunk = (char*)chunk_alloc(n, &__nobjs);
???? _obj *VOLATILE* __my_free_list;
???? _obj *VOLATILE* __my_free_list1;
???? _obj * __result;
???? _obj * __current_obj;
???? _obj * __next_obj;
???? int __i;
???? // 如果內存池中僅有一個對象
???? if (1 == __nobjs)?
???????? return(__chunk);
???? __my_free_list = _free_list + freelist_index(n);
???? /* Build free list in chunk */
???? __result = (_obj*)__chunk;
???? *__my_free_list = __next_obj = (_obj*)(__chunk + n);
???? __my_free_list1 = _free_list + freelist_index(n);
???? for (__i = 1;; ++__i)
???? {
???????? __current_obj = __next_obj;
???????? __next_obj = (_obj*)((char*)__next_obj+n);
???????? if(__nobjs - 1 == __i)
???????? {
????????????? __current_obj->free_list_link = 0;
????????????? break;
???????? }else{
????????????? __current_obj->free_list_link = __next_obj;
???????? }
???? }
???? return(__result);
}
經(jīng)過上面操作后，內存池可能會成為如下的一種狀態(tài)。從圖上我們可以看到，已經(jīng)構建了8，24，88，128字節(jié)的空閑分配鏈表，而其他沒有分配空閑分配鏈表的他們的指針都指向NULL。我們通過判斷索引表中的指針是否為NULL，知道是否已經(jīng)構建空閑分配表或者空閑分配表是否用完，如果此處指針為NULL，我們調用refill函數(shù)，重新申請20個這樣大小的內存空間，并把他們連接起來。在refill函數(shù)內，我們要查看大內存中是否有可用內存，如果有，并且大小合適，就返回給refill函數(shù)。
圖4
?
??? 6：線程安全
??? 采用互斥體，保證線程安全。
內存池測試
??? 內存池的測試主要分兩部分測試1：單線程下malloc與mempool的分配速度對比2：多線程下malloc和mempool的分配速度對比，我們分為4，10，16個線程進行測試了。
??? 測試環(huán)境：操作系統(tǒng)：windows2003+sp1，VC7.1+sp1，硬件環(huán)境：intel(R) Celeron(R) CPU 2.53GHz,512M物理內存。
??? 申請內存空間設定如下
#define ALLOCNUMBER0 4
#define ALLOCNUMBER1 7
#define ALLOCNUMBER2 23
#define ALLOCNUMBER3 56
#define ALLOCNUMBER4 10
#define ALLOCNUMBER5 60
#define ALLOCNUMBER6 5
#define ALLOCNUMBER7 80
#define ALLOCNUMBER8 9
#define ALLOCNUMBER9 100
??? Malloc方式和mempool方式均使用如上數(shù)據(jù)進行內存空間的申請和釋放。申請過程，每次循環(huán)申請釋放上述數(shù)據(jù)20次
??? 我們對malloc和mempool，分別進行了如下申請次數(shù)的測試（單位為萬）
|
2
|
10
|
20
|
30
|
40
|
50
|
80
|
100
|
150
|
200
|
malloc和mempool在單線程，多線程，release，debug版的各種測試數(shù)據(jù)，形成如下的統(tǒng)計圖
圖5
可以看到mempool無論在多線程還是在單線程情況下，mempool的速度都優(yōu)于malloc方式的直接分配。
??? Malloc方式debug模式下，在不同的線程下，運行時間如下，通過圖片可知，malloc方式，在debug模式下，申請空間的速度和多線程的關系不大。多線程方式，要略快于單線程的運行實現(xiàn)。
圖6
??? Malloc方式release模式測試結果如下。
圖7
多線程的優(yōu)勢，逐漸體現(xiàn)出來。當執(zhí)行200w次申請和釋放時，多線程要比單線程快1500ms左右，而4，10，16個線程之間的差別并不是特別大。不過整體感覺4個線程的運行時間要稍微高于10，16個線程的情況下，意味著進程中線程越多用在線程切換上的時間就越多。
下面是mempool在debug測試結果
圖8
??? 下面是mempool在release模式下的測試結果
圖9
??? 以上所有統(tǒng)計圖中所用到的數(shù)據(jù)，是我們測試三次后平均值。
通過上面的測試，可以知道m(xù)empool的性能基本上超過直接malloc方式，在200w次申請和釋放的情況下，單線程release版情況下，mempool比直接malloc快110倍。而在4個線程情況下，mempool要比直接malloc快7倍左右。以上測試只是申請速度的測試，在不同的壓力情況下，測試結果可能會不同，測試結果也不能說明mempool方式比malloc方式穩(wěn)定。
??? 小結：內存池基本上滿足初期設計目標，但是她并不是完美的，有缺陷，比如,不能申請大于256字節(jié)的內存空間，無內存越界檢查，無內存自動回縮功能等。只是這些對我們的影響還不是那么重要。
由于這是一個公司項目，代碼涉及版權，所以不能發(fā)布出來。如果你想做自己的內存池，可以與我聯(lián)系ugg_xchj#hotmail.com.