内存池实现与分析

内存池实现与分析

描述

程序中不可避免的因为需要动态分配内存，而大量使用堆上的内存。如果使用系统默认的函数new/delete或malloc/free来分配和释放堆上的内存，效率不高，同时还可能产生大量的内存碎片，导致长时间运行后性能愈发下降。为了提高性能，通常就需要考虑使用一些数据结构和算法来减少动态分配的发生，这也是内存池这个思想的来源。

在我们的服务器里，可以看到大量频繁申请和销魂内存的情况发生在接收处理网络数据的部分里，所以在这一部分的处理中我们就需要考虑使用内存池来优化性能。

算法思想

首先使用的方法是类似 SGI STL 中的 allocator 内存分配器的实现方式。设计了一个数组，负责管理内存页（MemPage）。每一个内存页都可分配连固定大小，范围在 8Bytes 到 64MBytes 之间的内存块。

内存块是在创建MemPage申请的一段连续大小的空间，同时另外用一个数组记录每个块所在的内存地址，分配的时候分配空闲的内存空间，释放的时候通过修改数组指向的位置达到释放的目的。

结构如下：

实现细节

首先定义的结构大小限制如下：

#define _MIN_BLOCK_SIZE_		(8)             //单内存块最小限制为8 Byte
#define _MAX_BLOCK_SIZE_		(1 << 26 )      //单内存块最大限制为64 MByte
#define _PAGE_MIN_SIZE_			(1024 * 1024)	//单页大小最小限制为1 MByte
#define _PAGE_INDEX_COUNT_		(27)			//对应上面的26位大小限制，所以数组定为27
#define _PAGE_COUNT_			(4096)		    //限制分配不超过4096页
#define _PAGE_MIN_BITS_         (20)            //单页大小限制的位数，对应 _PAGE_MIN_SIZE_ 的大小

然后定义的分配器结构如下：

class CAllocator
{
public:
    CAllocator();
    virtual ~CAllocator();
    
    virtual void *malloc (size_t nbytes);
    virtual void free (void *ptr);
    virtual void *realloc( void * pTemp , size_t nSize );
private:

    size_t _lastIndex[_PAGE_INDEX_COUNT_];                      //记录每一位最后用来分配的索引
    size_t _pageCount[_PAGE_INDEX_COUNT_];                      //记录每一位的已分配页数量

    CMemPage* _bitPages[_PAGE_INDEX_COUNT_][_PAGE_COUNT_];      //管理每一位的页mempage
    CMemPage* _pages[_PAGE_COUNT_];                             //管理所有页mempage
};

内存页MemPage设计：

内存页结构如下：

class CMemPage
{    
private:
    size_t _pageSize;		//页大小
    size_t _blockSize;	    //块大小
    size_t _blockCount;	    //块数量
    size_t _freeIndex;	    //空闲索引
    size_t* _freeBlocks;	//块地址数组
};

内存页限制最小大小为1MByte，每次申请的大小都在该大小以上，分配的时候根据2进制位数计算出申请块的大小，再根据该块大小确定页大小并向系统申请内存。如果单块大小小于1MByte，则一个页中存在多个块。

页中额外构建了一个数组，数组中每个元素均为页中的块对应的地址。

static MemPage* mallocPage(size_t blockSize)
{
    size_t size = getBit(blockSize);
    size_t pageSize = _PAGE_MIN_SIZE_ + sizeof(MemPage);
    if(size > _PAGE_MIN_SIZE_)
    {
        pageSize = size + sizeof(MemPage);
    }
    void* buf = ::malloc(pageSize);
    if(NULL == buf) return NULL;

    MemPage page(size, pageSize, buf);
    memcpy(buf, &page, sizeof(page));
    return (MemPage*)buf;
}

MemPage(size_t blockSize, size_t pageSize, void* const start)
			:_pageSize(0),_blockSize(0),_freeIndex(0)
{
    memset(this, 0, sizeof(MemPage));

    _pageSize = pageSize;

    _blockSize = blockSize;
    if(blockSize < _MIN_BLOCK_SIZE_)
    {
        _blockSize = _MIN_BLOCK_SIZE_;
    }

    _blockCount = (_pageSize - sizeof(MemPage)) / blockSize;
    _freeBlocks = (size_t*)::malloc(_blockCount * sizeof(size_t));

    for(size_t i = 0; i < _blockCount; ++i)
    {
        _freeNodes[i] = (size_t)((char*)start + sizeof(MemPage) + i * _blockSize);
    }
    _freeIndex = _blockCount;
}

分配操作：

当需要一段空间时，计算最接近的2次幂向上取整，算出位数，在下直接索引到该位数下的MemPage数组，然后寻找还有空闲位置的MemPage，分配一块空间。

例如需要10Bytes，最接近的是16Bytes，索引到_usedPage[4]，然后获取上一次最后分配的索引和实际分配的页数量:

//malloc函数
//计算出 bit = getBit(10) = 4，以下直接使用4来说明

lastIdx = _lastIndex[4];
pageCount = _pageCount[4];

//在lastIdx~pageCount之间找空余页
for (int i = lastIdx; i < pageCount; ++i)
{
    if (_bitPages[4][i]->isFree())
    {
        //分配内存
        _lastIndex[4] = i;
        return _bitPages[4][i]->malloc(bytes);
    }
}

//如果在lastIdx~pageCount之间都无法找到空余页，寻找0~lastIdx
for (int i = 0; i < lastIdx; ++i)
{
    if (_bitPages[4][i]->isFree())
    {
        //分配内存
        _lastIndex[4] = i;
        return _bitPages[4][i]->malloc(bytes);
    }
}

//如果依然无法分配，新建页
MemPage *memPage = MemPage::mallocPage(bytes);
if( NULL != memPage )
{
    _bitPages[4][ _pageCount[4]++ ] = memPage;
    size_t index = (size_t)memPage >> _PAGE_MIN_BITS_;
    _pages[ index ] = memPage;
    return memPage->malloc(bytes);
}

上面计算index的方法是因为按照规定页大小限制1MB，即内存地址间隔最小也在20位以上，可通过位移操作消除即可得到唯一索引，同时也是在释放内存和重分配的时候直接通过地址计算出该内存块所在内存页。

其中，寻找到适合的页后，在页中取空闲块的方法如下：

void* mallocNode(size_t size)
{
    return (void*)_freeBlocks[--_freeIndex];
}

释放操作：

在释放内存的时候，就可以通过上面使用的计算index方法同样计算出当前内存块所在的index，从而找到对应的页并释放。释放的时候只需要将页中空闲内存索引+1并将空闲内存地址数组中重新记录该块地址即可。

void CAllocator::free(void *ptr)
{
	if(!ptr)
	{
		return;
	}

	size_t index = (size_t)ptr >> (_PAGE_MIN_BITS_);
	MemPage* memPage = _memPages[index];
	if(!memPage || memPage > ptr)
	{
		--index;
	}
	memPage = _memPages[index];
	
	memPage->freeNode(ptr);
}

bool freeNode(void* node)
{
    _freeBlocks[_freeIndex++] = (size_t)node;
    return true;
}