基于C語言的內(nèi)存池的設(shè)計(jì)與實(shí)現(xiàn)

轉(zhuǎn)自： http://blog.csdn.net/ugg/article/details/1543290

介紹：

       設(shè)計(jì)內(nèi)存池的目標(biāo)是為了保證服務(wù)器長時(shí)間高效的運(yùn)行，通過對(duì)申請(qǐng)空間小而申請(qǐng)頻繁的對(duì)象進(jìn)行有效管理，減少內(nèi)存碎片的產(chǎn)生，合理分配管理用戶內(nèi)存，從而減少系統(tǒng)中出現(xiàn)有效空間足夠，而無法分配大塊連續(xù)內(nèi)存的情況。

目標(biāo)：

    此次設(shè)計(jì)內(nèi)存池的基本目標(biāo)，需要滿足線程安全性（多線程），適量的內(nèi)存泄露越界檢查，運(yùn)行效率不太低于malloc/free方式，實(shí)現(xiàn)對(duì)4-128字節(jié)范圍內(nèi)的內(nèi)存空間申請(qǐng)的內(nèi)存池管理（非單一固定大小對(duì)象管理的內(nèi)存池）。

內(nèi)存池技術(shù)設(shè)計(jì)與實(shí)現(xiàn)

    本內(nèi)存池的設(shè)計(jì)方法主要參考SGI的alloc的設(shè)計(jì)方案，為了適合一般的應(yīng)用，并在alloc的基礎(chǔ)上做一些簡單的修改。

    Mempool的內(nèi)存池設(shè)計(jì)方案如下（也可參考候捷《深入剖析STL》）

    從系統(tǒng)申請(qǐng)大塊heap內(nèi)存，在此內(nèi)存上劃分不同大小的區(qū)塊，并把具有相同大小的區(qū)塊連接起來，組成一個(gè)鏈表。比如A大小的塊，組成鏈表L，當(dāng)申請(qǐng)A大小時(shí)，直接從鏈表L頭部（如果不為空）上取到一塊交給申請(qǐng)者，當(dāng)釋放A大小的塊時(shí)，直接掛接到L的頭部。內(nèi)存池的原理比較簡單，但是在具體實(shí)現(xiàn)過程中大量的細(xì)節(jié)需要注意。

    1：字節(jié)對(duì)齊。

    為了方便內(nèi)存池中對(duì)象的管理，需要對(duì)申請(qǐng)內(nèi)存空間的進(jìn)行調(diào)整，在Mempool中，字節(jié)對(duì)齊的大小為最接近8倍數(shù)的字節(jié)數(shù)。比如，用戶申請(qǐng)5個(gè)字節(jié)，Mempool首先會(huì)把它調(diào)整為8字節(jié)。比如申請(qǐng)22字節(jié)，會(huì)調(diào)整為24，對(duì)比關(guān)系如下

（圖1）

對(duì)于超過128字節(jié)的申請(qǐng)，直接調(diào)用malloc函數(shù)申請(qǐng)內(nèi)存空間。這里設(shè)計(jì)的內(nèi)存池并不是對(duì)所有的對(duì)象進(jìn)行內(nèi)存管理，只是對(duì)申請(qǐng)內(nèi)存空間小，而申請(qǐng)頻繁的對(duì)象進(jìn)行管理，對(duì)于超過128字節(jié)的對(duì)象申請(qǐng)，不予考慮。這個(gè)需要與實(shí)際項(xiàng)目結(jié)合，并不是固定不變的。實(shí)現(xiàn)對(duì)齊操作的函數(shù)如下

static size_t round_up(size_t size)
{
        return (((size)+7) &~ 7);// 按8字節(jié)對(duì)齊
}

2：構(gòu)建索引表

內(nèi)存池中管理的對(duì)象都是固定大小，現(xiàn)在要管理0-128字節(jié)的范圍內(nèi)的對(duì)象申請(qǐng)空間，除了采用上面提到的字節(jié)對(duì)齊外，還需要變通一下，這就是建立索引表，做法如下；
static _obj*  free_list[16];
創(chuàng)建一個(gè)包含16個(gè)_obj*指針的數(shù)組，關(guān)于_obj結(jié)構(gòu)后面詳細(xì)講解。free_list[0]記錄所有空閑空間為8字節(jié)的鏈表的首地址；free_list[1]對(duì)應(yīng)16字節(jié)的鏈表，free_list[2]對(duì)應(yīng)24字節(jié)的列表。free_list中的下標(biāo)和字節(jié)鏈表對(duì)應(yīng)關(guān)系參考圖1中的“序號(hào)”和“對(duì)齊字節(jié)”之間的關(guān)系。這種關(guān)系，我們很容易用算法計(jì)算出來。如下

static size_t freelist_index(size_t size)
{
        return  (((size)+7)/8-1); // 按8字節(jié)對(duì)齊
}

    所以，這樣當(dāng)用戶申請(qǐng)空間A時(shí)，我們只是通過上面簡單的轉(zhuǎn)換，就可以跳轉(zhuǎn)到包含A字節(jié)大小的空閑鏈表上,如下；
_obj** p = free_list[freelist_index(A)];

3:構(gòu)建空閑鏈表

通過索引表，我們知道m(xù)empool中維持著16條空閑鏈表，這些空閑鏈表中管理的空閑對(duì)象大小分別為8，16，24，32，40…128。這些空閑鏈表鏈接起來的方式完全相同。一般情況下我們構(gòu)建單鏈表時(shí)需要?jiǎng)?chuàng)建如下的一個(gè)結(jié)構(gòu)體。

struct Obj
{
    Obj *next;
    Char* p;
    Int iSize;
}

next指針指向下一個(gè)這樣的結(jié)構(gòu)，p指向真正可用空間,iSize用于只是可用空間的大小，在其他的一些內(nèi)存池實(shí)現(xiàn)中，還有更復(fù)雜的結(jié)構(gòu)體，比如還包括記錄此結(jié)構(gòu)體的上級(jí)結(jié)構(gòu)體的指針，結(jié)構(gòu)體中當(dāng)前使用空間的變量等，當(dāng)用戶申請(qǐng)空間時(shí)，把此結(jié)構(gòu)體添加的用戶申請(qǐng)空間中去，比如用戶申請(qǐng)12字節(jié)的空間，可以這樣做

Obj *p = (Obj*)malloc(12+sizeof(Obj));
p->next = NULL;
p->p = (char*)p+sizeof(Obj);
p->iSize = 12;

但是，我們并沒有采用這種方式，這種方式的一個(gè)缺點(diǎn)就是，用戶申請(qǐng)小空間時(shí)，內(nèi)存池加料太多了。比如用戶申請(qǐng)12字節(jié)時(shí)，而真實(shí)情況是內(nèi)存池向內(nèi)存申請(qǐng)了12+ sizeof(Obj)=12+12=24字節(jié)的內(nèi)存空間，這樣浪費(fèi)大量內(nèi)存用在標(biāo)記內(nèi)存空間上去，并且也沒有體現(xiàn)索引表的優(yōu)勢(shì)。Mempool采用的是union方式

union Obj
{
    Obj *next;
    char client_data[1];
}

這里除了把上面的struct修改為union，并把int iSize去掉，同時(shí)把char*p，修改為char client_data[1]，并沒有做太多的修改。而優(yōu)勢(shì)也恰恰體現(xiàn)在這里。如果采用struct方式，我們需要維護(hù)兩條鏈表，一條鏈表是，已分配內(nèi)存空間鏈表，另一條是未分配（空閑）空間鏈表。而我們使用索引表和union結(jié)構(gòu)體，只需要維護(hù)一條鏈表，即未分配空間鏈表。具體如下

索引表的作用有兩條1：如上所說，維護(hù)16條空閑鏈表2：變相記錄每條鏈表上空間的大小，比如下標(biāo)為3的索引表內(nèi)維持著是大小為24字節(jié)的空閑鏈表。這樣我們通過索引表減少在結(jié)構(gòu)體內(nèi)記錄p所指向空間大小的iSize變量。從而減少4個(gè)字節(jié)。

Union的特性是，結(jié)構(gòu)內(nèi)的變量是互斥存在的。再運(yùn)行狀態(tài)下，只是存在一種變量類型。所以在這里sizeof(Obj)的大小為4，難道這里我們也需要把這4字節(jié)也加到用戶申請(qǐng)空間中去嘛？其實(shí)不是，如果這樣，我們又抹殺了union的特性。

當(dāng)我們構(gòu)建空閑分配鏈表時(shí)，我們通過next指向下一個(gè)union結(jié)構(gòu)體，這樣我們不使用p指針。當(dāng)把這個(gè)結(jié)構(gòu)體分配出去時(shí)，我們直接返回client_data的地址，此時(shí)client_data正好指向申請(qǐng)空間的首字節(jié)。所以這樣，我們就不用在用戶申請(qǐng)空間上添加任何東西。

圖2

    Obj的連接方式如上所示，這樣我們無需為用戶申請(qǐng)空間添加任何內(nèi)容。   

4：記錄申請(qǐng)空間字節(jié)數(shù)

如果采用面向?qū)ο蠓绞剑蛘呶覀冊(cè)卺尫艃?nèi)存池的空間時(shí)能夠明確知道釋放空間的大小，無需采用這種方式。

圖3

在C語言中的free沒有傳遞釋放空間大小，而可以正確釋放，在這里也是模仿這種方式，采用這種記錄申請(qǐng)空間大小的方式去釋放內(nèi)存。用戶申請(qǐng)空間+1操作將在字節(jié)對(duì)齊之前執(zhí)行，找到合適空間后，把首字節(jié)改寫為申請(qǐng)空間的大小，當(dāng)然1個(gè)字節(jié)最多紀(jì)錄256個(gè)數(shù)，如果項(xiàng)目需要，可以設(shè)置為short類型或者int類型，不過這樣就需要占用用戶比較大的空間。當(dāng)釋放內(nèi)存空間時(shí)，首先讀取這個(gè)字節(jié)，獲取空間大小，進(jìn)行釋放。為了便于對(duì)大于128字節(jié)對(duì)象的大小進(jìn)行合適的釋放，同時(shí)也對(duì)大于128字節(jié)的內(nèi)存申請(qǐng)，添加1字節(jié)記錄大小。所以現(xiàn)在這里限制了用戶內(nèi)存申請(qǐng)空間不得大于255字節(jié)，不過現(xiàn)在已經(jīng)滿足項(xiàng)目要求。當(dāng)然也可以修改為用short類型記錄申請(qǐng)空間的大小。

    // 申請(qǐng)
    *(( 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：內(nèi)存池的分配原理

在內(nèi)存池的設(shè)計(jì)中，有兩個(gè)重要的操作過程1：chunk_alloc，申請(qǐng)大塊內(nèi)存，2：refill回填操作，內(nèi)存池初始化化時(shí)并不是為索引表中的每一項(xiàng)都創(chuàng)建空閑分配鏈表，這個(gè)過程會(huì)推遲到，只有用戶提取請(qǐng)求時(shí)才會(huì)創(chuàng)建這樣的分配鏈表。詳細(xì)參考如下代碼（在sgi中stl_alloc.h文件中你也可以看到這兩個(gè)函數(shù)），主要步驟在注釋中已經(jīng)說明。

/**
* @bri: 申請(qǐng)大塊內(nèi)存，并返回size*(*nobjs)大小的內(nèi)存塊
* @param: size,round_up對(duì)齊后的大小,nobjs
* @return: 返回指向第一個(gè)對(duì)象內(nèi)存指針
*/
static char* chunk_alloc(size_t size, int *nobjs)
{
     /**< 返回指針 */
     char* __result;
     /**< 申請(qǐng)內(nèi)存塊大小 */
     size_t __total_bytes = size *(*nobjs);
     /**< 當(dāng)前內(nèi)存可用空間 */
     size_t __bytes_left = _end_free - _start_free;

     /**< 內(nèi)存池中還有大片可用內(nèi)存 */
     if (__bytes_left >= __total_bytes)
     {
         __result = _start_free;
         _start_free += __total_bytes;
         return (__result);
     }
     /**< 至少還有一個(gè)對(duì)象大小的內(nèi)存空間 */
     else if (__bytes_left >= size)
     {
         *nobjs = (int)(__bytes_left/size);
         __total_bytes = size * (*nobjs);
         __result = _start_free;
         _start_free += __total_bytes;
         return (__result);
     }
     /**< 內(nèi)存池中沒有任何空間 */
     else
     {
         /**< 重新申請(qǐng)內(nèi)存池的大小 */
         size_t __bytes_to_get = 2 * __total_bytes + round_up(_heap_size >> 4);
         /**< 把內(nèi)存中剩余的空間添加到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;
         }
         // 申請(qǐng)新的大塊空間
         _start_free = (char*)malloc(__bytes_to_get);
         /*=======================================================================*/
         memset(_start_free,0,__bytes_to_get);
         /*=======================================================================*/
         // 系統(tǒng)內(nèi)存已經(jīng)無可用內(nèi)存，那么從內(nèi)存池中壓縮內(nèi)存
         if(0 == _start_free)
         {
              size_t __i;
              _obj *VOLATILE* __my_free_list;
              _obj *__p;
              /**< 從freelist中逐項(xiàng)檢查可用空間(此時(shí)只收集比size對(duì)象大的內(nèi)存空間) */
              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;
              /**< 再次申請(qǐng)內(nèi)存，可能觸發(fā)一個(gè)異常 */
              _start_free = (char*)malloc(__bytes_to_get);
         }
         /**< 記錄當(dāng)前內(nèi)存池的容量 */
         _heap_size += __bytes_to_get;
         _end_free = _start_free + __bytes_to_get;
         return (chunk_alloc(size,nobjs));
     }
}

/*=======================================================================*/
/**
 * @bri: 填充freelist的連接，默認(rèn)填充20個(gè)
 * @param: __n，填充對(duì)象的大小，8字節(jié)對(duì)齊后的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;
     // 如果內(nèi)存池中僅有一個(gè)對(duì)象
     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)過上面操作后，內(nèi)存池可能會(huì)成為如下的一種狀態(tài)。從圖上我們可以看到，已經(jīng)構(gòu)建了8，24，88，128字節(jié)的空閑分配鏈表，而其他沒有分配空閑分配鏈表的他們的指針都指向NULL。我們通過判斷索引表中的指針是否為NULL，知道是否已經(jīng)構(gòu)建空閑分配表或者空閑分配表是否用完，如果此處指針為NULL，我們調(diào)用refill函數(shù)，重新申請(qǐng)20個(gè)這樣大小的內(nèi)存空間，并把他們連接起來。在refill函數(shù)內(nèi)，我們要查看大內(nèi)存中是否有可用內(nèi)存，如果有，并且大小合適，就返回給refill函數(shù)。

圖4

    6：線程安全
    采用互斥體，保證線程安全。

內(nèi)存池測(cè)試

    內(nèi)存池的測(cè)試主要分兩部分測(cè)試1：單線程下malloc與mempool的分配速度對(duì)比2：多線程下malloc和mempool的分配速度對(duì)比，我們分為4，10，16個(gè)線程進(jìn)行測(cè)試了。
    測(cè)試環(huán)境：操作系統(tǒng)：windows2003+sp1，VC7.1+sp1，硬件環(huán)境：intel(R) Celeron(R) CPU 2.53GHz,512M物理內(nèi)存。

    申請(qǐng)內(nèi)存空間設(shè)定如下
#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ù)進(jìn)行內(nèi)存空間的申請(qǐng)和釋放。申請(qǐng)過程，每次循環(huán)申請(qǐng)釋放上述數(shù)據(jù)20次
    我們對(duì)malloc和mempool，分別進(jìn)行了如下申請(qǐng)次數(shù)的測(cè)試（單位為萬）

圖5

可以看到mempool無論在多線程還是在單線程情況下，mempool的速度都優(yōu)于malloc方式的直接分配。

    Malloc方式debug模式下，在不同的線程下，運(yùn)行時(shí)間如下，通過圖片可知，malloc方式，在debug模式下，申請(qǐng)空間的速度和多線程的關(guān)系不大。多線程方式，要略快于單線程的運(yùn)行實(shí)現(xiàn)。

圖6

    Malloc方式release模式測(cè)試結(jié)果如下。

圖7

多線程的優(yōu)勢(shì)，逐漸體現(xiàn)出來。當(dāng)執(zhí)行200w次申請(qǐng)和釋放時(shí)，多線程要比單線程快1500ms左右，而4，10，16個(gè)線程之間的差別并不是特別大。不過整體感覺4個(gè)線程的運(yùn)行時(shí)間要稍微高于10，16個(gè)線程的情況下，意味著進(jìn)程中線程越多用在線程切換上的時(shí)間就越多。

下面是mempool在debug測(cè)試結(jié)果

圖8

    下面是mempool在release模式下的測(cè)試結(jié)果

圖9

    以上所有統(tǒng)計(jì)圖中所用到的數(shù)據(jù)，是我們測(cè)試三次后平均值。

通過上面的測(cè)試，可以知道m(xù)empool的性能基本上超過直接malloc方式，在200w次申請(qǐng)和釋放的情況下，單線程release版情況下，mempool比直接malloc快110倍。而在4個(gè)線程情況下，mempool要比直接malloc快7倍左右。以上測(cè)試只是申請(qǐng)速度的測(cè)試，在不同的壓力情況下，測(cè)試結(jié)果可能會(huì)不同，測(cè)試結(jié)果也不能說明mempool方式比malloc方式穩(wěn)定。

    小結(jié)：內(nèi)存池基本上滿足初期設(shè)計(jì)目標(biāo)，但是她并不是完美的，有缺陷，比如,不能申請(qǐng)大于256字節(jié)的內(nèi)存空間，無內(nèi)存越界檢查，無內(nèi)存自動(dòng)回縮功能等。只是這些對(duì)我們的影響還不是那么重要。

由于這是一個(gè)公司項(xiàng)目，代碼涉及版權(quán)，所以不能發(fā)布出來。如果你想做自己的內(nèi)存池，可以與我聯(lián)系