介紹:
設計記憶體池的目标是為了保證伺服器長時間高效的運作,通過對申請空間小而申請頻繁的對象進行有效管理,減少記憶體碎片的産生,合理配置設定管理使用者記憶體,進而減少系統中出現有效空間足夠,而無法配置設定大塊連續記憶體的情況。
目标:
此次設計記憶體池的基本目标,需要滿足線程安全性(多線程),适量的記憶體洩露越界檢查,運作效率不太低于malloc/free方式,實作對4-128位元組範圍内的記憶體空間申請的記憶體池管理(非單一固定大小對象管理的記憶體池)。
記憶體池技術設計與實作
本記憶體池的設計方法主要參考SGI的alloc的設計方案,為了适合一般的應用,并在alloc的基礎上做一些簡單的修改。
Mempool的記憶體池設計方案如下(也可參考候捷《深入剖析STL》)
從系統申請大塊heap記憶體,在此記憶體上劃分不同大小的區塊,并把具有相同大小的區塊連接配接起來,組成一個連結清單。比如A大小的塊,組成連結清單L,當申請A大小 時,直接從連結清單L頭部(如果不為空)上取到一塊交給申請者,當釋放A大小的塊時,直接挂接到L的頭部。記憶體池的原理比較簡單,但是在具體實作過程中大量的 細節需要注意。
1:位元組對齊。
為了友善記憶體池中對象的管理,需要對申請記憶體空間的進行調整,在Mempool中,位元組對齊的大小為最接近8倍數的位元組數。比如,使用者申請5個位元組,Mempool首先會把它調整為8位元組。比如申請22位元組,會調整為24,對比關系如下
序号
對齊位元組
範圍
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
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位元組的申請,直接調用malloc函數申請記憶體空間。這裡設計的記憶體池并不是對所有的對象進行記憶體管理,隻是對申請記憶體空間小,而申 請頻繁的對象進行管理,對于超過128位元組的對象申請,不予考慮。這個需要與實際項目結合,并不是固定不變的。實作對齊操作的函數如下
static size_t round_up(size_t size)
{
return (((size)+7) &~ 7);// 按8位元組對齊
}
2:建構索引表
記憶體池中管理的對象都是固定大小,現在要管理0-128位元組的範圍内的對象申請空間,除了采用上面提到的位元組對齊外,還需要變通一下,這就是建立索引表,做法如下;
static _obj* free_list[16];
建立一個包含16個_obj*指針的數組,關于_obj結構後面詳細講解。free_list[0]記錄所有空閑空間為8位元組的連結清單的首地 址;free_list[1]對應16位元組的連結清單,free_list[2]對應24位元組的清單。free_list中的下标和位元組連結清單對應關系參考圖1 中的“序号”和“對齊位元組”之間的關系。這種關系,我們很容易用算法計算出來。如下
static size_t freelist_index(size_t size)
return (((size)+7)/7-1);// 按8位元組對齊
是以,這樣當使用者申請空間A時,我們隻是通過上面簡單的轉換,就可以跳轉到包含A位元組大小的空閑連結清單上,如下;
_obj** p = free_list[freelist_index(A)];
3:建構空閑連結清單
通過索引表,我們知道mempool中維持着16條空閑連結清單,這些空閑連結清單中管理的空閑對象大小分别為8,16,24,32,40…128。這些空閑連結清單連結起來的方式完全相同。一般情況下我們建構單連結清單時需要建立如下的一個結構體。
struct Obj
Obj *next;
Char* p;
Int iSize;
next指針指向下一個這樣的結構,p指向真正可用空間,iSize用于隻是可用空間的大小,在其他的一些記憶體池實作中,還有更複雜的結構體,比如 還包括記錄此結構體的上級結構體的指針,結構體中目前使用空間的變量等,當使用者申請空間時,把此結構體添加的使用者申請空間中去,比如使用者申請12位元組的空 間,可以這樣做
Obj *p = (Obj*)malloc(12+sizeof(Obj));
p->next = NULL;
p->p = (char*)p+sizeof(Obj);
p->iSize = 12;
但是,我們并沒有采用這種方式,這種方式的一個缺點就是,使用者申請小空間時,記憶體池加料太多了。比如使用者申請12位元組時,而真實情況是記憶體池向記憶體 申請了12+ sizeof(Obj)=12+12=24位元組的記憶體空間,這樣浪費大量記憶體用在标記記憶體空間上去,并且也沒有展現索引表的優勢。Mempool采用的是 union方式
union Obj
char client_data[1];
這裡除了把上面的struct修改為union,并把int iSize去掉,同時把char*p,修改為char client_data[1],并沒有做太多的修改。而優勢也恰恰展現在這裡。如果采用struct方式,我們需要維護兩條連結清單,一條連結清單是,已配置設定記憶體 空間連結清單,另一條是未配置設定(空閑)空間連結清單。而我們使用索引表和union結構體,隻需要維護一條連結清單,即未配置設定空間連結清單。具體如下
索引表的作用有兩條1:如上所說,維護16條空閑連結清單2:變相記錄每條連結清單上空間的大小,比如下标為3的索引表内維持着是大小為24位元組的空閑連結清單。這樣我們通過索引表減少在結構體内記錄p所指向空間大小的iSize變量。進而減少4個位元組。
Union的特性是,結構内的變量是互斥存在的。再運作狀态下,隻是存在一種變量類型。是以在這裡sizeof(Obj)的大小為4,難道這裡我們也需要把這4位元組也加到使用者申請空間中去嘛?其實不是,如果這樣,我們又抹殺了union的特性。
當我們建構空閑配置設定連結清單時,我們通過next指向下一個union結構體,這樣我們不使用p指針。當把這個結構體配置設定出去時,我們直接傳回 client_data的位址,此時client_data正好指向申請空間的首位元組。是以這樣,我們就不用在使用者申請空間上添加任何東西。
圖2
Obj的連接配接方式如上所示,這樣我們無需為使用者申請空間添加任何内容。
4:記錄申請空間位元組數
如果采用面向對象方式,或者我們在釋放記憶體池的空間時能夠明确知道釋放空間的大小,無需采用這種方式。
圖3
在C語言中的free沒有傳遞釋放空間大小,而可以正确釋放,在這裡也是模仿這種方式,采用這種記錄申請空間大小的方式去釋放記憶體。使用者申請空 間+1操作将在位元組對齊之前執行,找到合适空間後,把首位元組改寫為申請空間的大小,當然1個位元組最多紀錄256個數,如果項目需要,可以設定為short 類型或者int類型,不過這樣就需要占用使用者比較大的空間。當釋放記憶體空間時,首先讀取這個位元組,擷取空間大小,進行釋放。為了便于對大于128位元組對象 的大小進行合适的釋放,同時也對大于128位元組的記憶體申請,添加1位元組記錄大小。是以現在這裡限制了使用者記憶體申請空間不得大于255位元組,不過現在已經滿 足項目要求。當然也可以修改為用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回填操作,記憶體池初始化化時并不是為索引表中 的每一項都建立空閑配置設定連結清單,這個過程會推遲到,隻有使用者提取請求時才會建立這樣的配置設定連結清單。詳細參考如下代碼(在sgi中stl_alloc.h檔案中 你也可以看到這兩個函數),主要步驟在注釋中已經說明。
/**
* @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);
/**< 記憶體池中沒有任何空間 */
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);
// 系統記憶體已經無可用記憶體,那麼從記憶體池中壓縮記憶體
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;
/**< 再次申請記憶體,可能觸發一個異常 */
_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位元組對齊後的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);
經過上面操作後,記憶體池可能會成為如下的一種狀态。從圖上我們可以看到,已經建構了8,24,88,128位元組的空閑配置設定連結清單,而其他沒有配置設定空閑 配置設定連結清單的他們的指針都指向NULL。我們通過判斷索引表中的指針是否為NULL,知道是否已經建構空閑配置設定表或者空閑配置設定表是否用完,如果此處指針為 NULL,我們調用refill函數,重新申請20個這樣大小的記憶體空間,并把他們連接配接起來。在refill函數内,我們要檢視大記憶體中是否有可用記憶體, 如果有,并且大小合适,就傳回給refill函數。
圖4
6:線程安全
采用互斥體,保證線程安全。
記憶體池測試
記憶體池的測試主要分兩部分測試1:單線程下malloc與mempool的配置設定速度對比2:多線程下malloc和mempool的配置設定速度對比,我們分為4,10,16個線程進行測試了。
測試環境:作業系統:windows2003+sp1,VC7.1+sp1,硬體環境: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方式均使用如上資料進行記憶體空間的申請和釋放。申請過程,每次循環申請釋放上述資料20次
我們對malloc和mempool,分别進行了如下申請次數的測試(機關為萬)
20
30
50
100
150
200
malloc和mempool在單線程,多線程,release,debug版的各種測試資料,形成如下的統計圖
圖5
可以看到mempool無論在多線程還是在單線程情況下,mempool的速度都優于malloc方式的直接配置設定。
Malloc方式debug模式下,在不同的線程下,運作時間如下,通過圖檔可知,malloc方式,在debug模式下,申請空間的速度和多線程的關系不大。多線程方式,要略快于單線程的運作實作。
圖6
Malloc方式release模式測試結果如下。
圖7
多線程的優勢,逐漸展現出來。當執行200w次申請和釋放時,多線程要比單線程快1500ms左右,而4,10,16個線程之間的差别并不是特别大。不過整體感覺4個線程的運作時間要稍微高于10,16個線程的情況下,意味着程序中線程越多用線上程切換上的時間就越多。
下面是mempool在debug測試結果
圖8
下面是mempool在release模式下的測試結果
圖9
以上所有統計圖中所用到的資料,是我們測試三次後平均值。
通過上面的測試,可以知道mempool的性能基本上超過直接malloc方式,在200w次申請和釋放的情況下,單線程release版情況 下,mempool比直接malloc快110倍。而在4個線程情況下,mempool要比直接malloc快7倍左右。以上測試隻是申請速度的測試,在 不同的壓力情況下,測試結果可能會不同,測試結果也不能說明mempool方式比malloc方式穩定。
小結:記憶體池基本上滿足初期設計目标,但是她并不是完美的,有缺陷,比如,不能申請大于256位元組的記憶體空間,無記憶體越界檢查,無記憶體自動回縮功能等。隻是這些對我們的影響還不是那麼重要。
由于這是一個公司項目,代碼涉及版權,是以不能釋出出來。如果你想做自己的記憶體池,可以與我聯系ugg_xchj#hotmail.com.
來源:http://blog.csdn.net/yangzhongxuan/article/details/8017629
本文轉自夏雪冬日部落格園部落格,原文連結:http://www.cnblogs.com/heyonggang/archive/2012/12/11/2813792.html,如需轉載請自行聯系原作者