那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

服务器公共库开发-内存池管理模块

这个内存池之前已经介绍过了,在这里

这次整理自己的服务器公共库,没有忘记这个好东西,算法没有改变,但是有两个变化:
1) 我认为这个模块对于一个服务器而言, 应该是一个单件, 所以它继承自前面说过的singleton基类.
2) 加入了线程锁, 同样是可以配置的, 因为我基本不写多线程的服务器, 不过, 还是把接口保留在那里吧, 如果需要可以打开以支持多线程.

mempool.h:
/********************************************************************
    created:    2008/08/03
    filename:   mempool.h    
    author:        Lichuang
                
    purpose:    仿SGI STL内存池的实现
********************************************************************
*/

#ifndef __MEM_POOL_H__
#define __MEM_POOL_H__

#include 
"singleton.h"
#include 
"threadmutex.h"
#include 
<stdio.h>

// 字节对齐数
#define ALIGN                512
// 最大BLOCK的尺寸
#define MAX_BLOCK_SIZE        20 * 1024
// HASH表的数量
#define BLOCK_LIST_NUM        (MAX_BLOCK_SIZE) / (ALIGN)
// HASH表中每次初始化时LIST中元素的数量
#define LIST_NODE_NUM        20

class CMemPool
    : CSingleton
<CMemPool>
{
public:
    
void* Allocate(size_t nSize);
    
void* Reallocate(void* p, size_t nOldSize, size_t nNewSize);
    
void  Deallocate(void* p, size_t nSize);
    
int   GetMemSize();

private:
    CMemPool();
    
virtual ~CMemPool();

    
char* AllocChunk(size_t nSize, int& nObjs);
    
void* Refill(size_t n);
    size_t RoundUp(size_t nBytes);
    
int GetFreeListIndex(size_t nBytes);

private:
    DECLARE_SINGLETON_CLASS(CMemPool)

private:        
    union Obj
    {
        union Obj
* pFreeListLink;
        
char szData[1];
    };

    Obj
* m_szFreeList[BLOCK_LIST_NUM];

    
char* m_pStartFree;
    
char* m_pEndFree;
    size_t m_nHeapSize;
    CThreadMutex m_tThreadMutex;
};

#endif /* __MEM_POOL_H__ */


mempool.cpp:
/********************************************************************
    created:    2008/08/01
    filename:     mempool.h
    author:        Lichuang
                
    purpose:    模拟SGI STL内存池的实现, 可以配置是否支持多线程
********************************************************************
*/

#include 
"mempool.h"
#include 
<string.h>

CMemPool::CMemPool()
    : m_pStartFree(NULL)
    , m_pEndFree(NULL)
    , m_nHeapSize(
0)                      
{
    ::memset(m_szFreeList, 
0sizeof(m_szFreeList));
}

CMemPool::
~CMemPool()
{
}

// 从内存池中分配尺寸为n的内存
void* CMemPool::Allocate(size_t nSize)
{
    
if (nSize > MAX_BLOCK_SIZE)
    {
        
return ::malloc(nSize);
    }
    
if (0 >= nSize)
    {
        
return NULL;
    }

    Obj
** ppFreeList;
    Obj
*  pResult;

    THREAD_LOCK;

    
// 获得尺寸n的HASH表地址
    ppFreeList = m_szFreeList + GetFreeListIndex(nSize);
    pResult 
= *ppFreeList;
    
if (NULL == pResult)
    {
        
// 如果之前没有分配, 或者已经分配完毕了, 就调用refill函数重新分配
        
// 需要注意的是, 传入refill的参数是经过对齐处理的
        pResult = (Obj*)Refill(RoundUp(nSize));
    }
    
else
    {
        
// 否则就更新该HASH表的LIST头节点指向下一个LIST的节点, 当分配完毕时, 头结点为NULL
        *ppFreeList = pResult->pFreeListLink;
    }

    THREAD_UNLOCK;

    
return pResult;
}

void* CMemPool::Reallocate(void* p, size_t nOldSize, size_t nNewSize)
{
    
void* pResult;
    size_t nCopySize;

    
// 如果超过内存池所能承受的最大尺寸, 调用系统API重新分配内存
    if (nOldSize > (size_t)MAX_BLOCK_SIZE && nNewSize > (size_t)MAX_BLOCK_SIZE)
    {
        
return ::realloc(p, nNewSize);
    }

    
// 如果新老内存尺寸在对齐之后相同, 那么直接返回
    if (RoundUp(nOldSize) == RoundUp(nNewSize))
        
return p;

    
// 首先按照新的尺寸分配内存
    pResult = Allocate(nNewSize);
    
if (NULL == pResult)
    {
        
return NULL;
    }
    
// copy旧内存的数据到新的内存区域
    nCopySize = nNewSize > nOldSize ? nOldSize : nNewSize;
    ::memcpy(pResult, p, nCopySize);
    
// 释放旧内存区域
    Deallocate(p, nOldSize);

    
return pResult;
}

// 将尺寸为n的内存回收到内存池中
void CMemPool::Deallocate(void* p, size_t nSize)
{
    Obj
* pObj = (Obj *)p;
    Obj 
**ppFreeList;

    
if (0 >= nSize)
    {
        
return;
    }
    
// 如果要回收的内存大于MAX_BLOCK_SIZE, 直接调用free回收内存
    if (nSize > MAX_BLOCK_SIZE)
    {
        ::free(p);
        
return;
    }

    
// 将回收的内存作为链表的头回收
    ppFreeList = m_szFreeList + GetFreeListIndex(nSize);

    THREAD_LOCK;

    pObj
->pFreeListLink = *ppFreeList;
    
*ppFreeList = pObj;

    THREAD_UNLOCK;
}

int CMemPool::GetMemSize()
{
    
return m_nHeapSize;
}

size_t CMemPool::RoundUp(size_t nBytes)
{
    
return (nBytes + ALIGN - 1& ~(ALIGN - 1);
}

int CMemPool::GetFreeListIndex(size_t nBytes)
{
    
return (nBytes + ALIGN - 1/ ALIGN - 1;
}


char* CMemPool::AllocChunk(size_t nSize, int& nObjs)
{
    
char* pResult;
    
// 总共所需的内存
    size_t nTotalBytes = nSize * nObjs;
    
// 剩余的内存
    size_t nBytesLeft = m_pEndFree - m_pStartFree;

    
// 如果剩余的内存可以满足需求, 就直接返回之, 并且更新内存池的指针
    if (nBytesLeft >= nTotalBytes)
    {
        pResult 
= m_pStartFree;
        m_pStartFree 
+= nTotalBytes;
        
return pResult;
    }

    
// 如果剩余的内存大于单位内存数量, 也就是说至少还可以分配一个单位内存
    
// 计算出最多可以分配多少块单位内存, 保存至nobjs, 返回内存的指针
    if (nBytesLeft >= nSize)
    {
        nObjs 
= (int)(nBytesLeft / nSize);
        nTotalBytes 
= nSize * nObjs;
        pResult 
= m_pStartFree;
        m_pStartFree 
+= nTotalBytes;
        
return pResult;
    }

    
// 如果还有剩余的内存, 将它放到对应的HASH-LIST头部
    if (0 < nBytesLeft)
    {
        Obj
** ppFreeList = m_szFreeList + GetFreeListIndex(nBytesLeft);
        ((Obj
*)m_pStartFree)->pFreeListLink = *ppFreeList;
        
*ppFreeList = (Obj*)m_pStartFree;
    }

    
// 需要获取的内存, 注意第一次分配都要两倍于total_bytes的大小
    
// 同时要加上原有的heap_size / 4的对齐值
    size_t nBytesToGet = 2 * nTotalBytes + RoundUp(m_nHeapSize >> 4);
    m_pStartFree 
= (char*)::malloc(nBytesToGet);

    
// 获取成功 重新调用chunk_alloc函数分配内存
    if (NULL != m_pStartFree)
    {
        m_nHeapSize 
+= nBytesToGet;
        m_pEndFree 
= m_pStartFree + nBytesToGet;
        
return AllocChunk(nSize, nObjs);
    }

    
// 下面是获取不成功的处理.

    
// 从下一个HASH-LIST中寻找可用的内存
    int i = (int)GetFreeListIndex(nSize) + 1;
    Obj 
**ppFreeList, *p;
    
for (; i < BLOCK_LIST_NUM; ++i)
    {
        ppFreeList 
= m_szFreeList + i;
        p 
= *ppFreeList;

        
if (NULL != p)
        {
            
*ppFreeList = p->pFreeListLink;
            m_pStartFree 
= (char*)p;
            m_pEndFree 
= m_pStartFree + (i + 1* ALIGN;
            
return AllocChunk(nSize, nObjs);
        }
    }

    m_pEndFree 
= NULL;

    
return NULL;
}

// 重新分配尺寸为n的内存, 其中n是经过字节对齐处理的数
void* CMemPool::Refill(size_t n)
{
    
// 每个链表每次初始化时最多LIST_NODE_NUM个元素
    int nObjs = LIST_NODE_NUM;
    
char* pChunk = AllocChunk(n, nObjs);
    Obj
** ppFreeList;
    Obj
* pResult;
    Obj 
*pCurrentObj, *pNextObj;
    
int i;

    
// 如果只请求成功了一个元素, 直接返回之
    if (1 == nObjs)
    {
        
return pChunk;
    }
    
// 获得尺寸n的HASH表地址
    ppFreeList = m_szFreeList + GetFreeListIndex(n);

    
// 获得请求的内存地址
    pResult = (Obj*)pChunk;
    
// 请求了一个单位内存, 减少一个计数
    --nObjs;
    
// 从下一个单位开始将剩余的obj连接起来
    *ppFreeList = pNextObj = (Obj*)(pChunk + n);

    
// 将剩余的obj连接起来
    for (i = 1; ; ++i)
    {
        pCurrentObj 
= pNextObj;
        pNextObj 
= (Obj*)((char*)pNextObj + n);

        
// 分配完毕, 下一个节点为NULL, 退出循环
        if (nObjs == i)
        {
            pCurrentObj
->pFreeListLink = NULL;
            
break;
        }

        pCurrentObj
->pFreeListLink = pNextObj;
    }

    
return pResult;
}



posted on 2008-08-11 23:30 那谁 阅读(4646) 评论(14)  编辑 收藏 引用 所属分类: 算法与数据结构服务器设计Linux/Unix

评论

# re: 服务器公共库开发-内存池管理模块  回复  更多评论   

内存池作为单件会严重减小适应范围的
2008-08-12 01:04 | 陈梓瀚(vczh)

# re: 服务器公共库开发-内存池管理模块[未登录]  回复  更多评论   

觉得boost::pool是个不错的东西,没什么必要自已重新造一个没别人好的车轮
2008-08-12 09:08 | ricardo

# re: 服务器公共库开发-内存池管理模块[未登录]  回复  更多评论   

@ricardo
我不用boost,也不会用,谢谢.
2008-08-12 09:54 |

# re: 服务器公共库开发-内存池管理模块[未登录]  回复  更多评论   

最好不要用单件。

可以使用简化的slab来做内存池/对象池——虽然不支持可变长度对象,但其使用范围更广也更灵活。
2008-08-12 10:24 | raof01

# re: 服务器公共库开发-内存池管理模块  回复  更多评论   

“没什么必要自已重新造一个没别人好的车轮”就是因为我们国家太多的程序员有这样的潜意识,导致我们知其然而不知其所以然。自己造车轮是好事,强烈支持造车轮者。
毛主席当年如果没有让我国航天人员自己造车轮,他们现在恐怕又得跟在老美、老英屁股后面拾粪了。开玩笑的说法就是:吃屎都赶不上热的。和航天事业形成鲜明对比的就是航空,我们的大飞机项目今年才启动,开始尝试自己造车轮,强烈感谢胡主席和温总理,感谢他们的独具慧眼,感谢他们给当代航空有志青年带来希望,带来工作机会,虽然慢了几拍。但是我相信再远的目标,只要开始就能实现!中国加油!
有能力造车的人,能够更好的使用别人的车,进而改进自己的造车技术,这是一个良构的循环,是一个具有创新能力和自优化能力的循环;而一味的买别人的车使用,成本大是小事,万一他娘的鬼子们不卖给咱新车、好车呢,咱们只能干瞪眼了!
-------------------- 以上仅代表个人观点、与C++博客无关。
2008-08-12 10:46 | 金哥

# re: 服务器公共库开发-内存池管理模块[未登录]  回复  更多评论   

楼上的朋友别激动,之所以选择自己写这个库,是因为我是阅读过它相关的代码明白其原理的,而且想动手实践一下,以在真正的应用中体会其性能等,诸如boost之类的第三方库,第一我不了解, 第二我不想在封装的库中引入别的库,所以除非必要否则我是不想使用的.

至于为什么这里封装成单件,我说了,这是一个服务器的公共库,而我认为,在一个运行的服务器上,这样的模块应该只有一个, 所有请求分配内存的操作都去找这个模块申请内存.

2008-08-12 10:59 |

# re: 服务器公共库开发-内存池管理模块[未登录]  回复  更多评论   

另外,我认为这个模块也是一个"第三方库", 因为它是从SGI实现的STL代码中提取出来的,并不是完全的"造轮子".
2008-08-12 11:05 |

# re: 服务器公共库开发-内存池管理模块[未登录]  回复  更多评论   

觉得模块划分粒度不够细。可以分成两个类,这样复用程度高一点:
1、m_szFreeList的每个表项可以封装成一个类。策略很多,找一个合适的就行。比如:
|head

-------------------------------------
|size|    |////|size|    |////|size|
|----|free|////|----|free|////|----|free
|next|    |////|next|    |////|next|
-------------------------------------
   |           ︿ |            ︿ |
   |           | |            | v
    -----------   ------------  NULL
当然,复杂性会有很大的增加,比如合并内存碎片。
2、用你的hash表来组织第一个类的对象。
2008-08-12 11:58 | raof01

# re: 服务器公共库开发-内存池管理模块[未登录]  回复  更多评论   

内存池原理很简单,
boost的内存池做的还可以,至少是够用的,
另外Apache下的ARP(貌似叫这个名字)中的内存池实现的也很不错。

其实STL中的Vector就可以当作一个池来用,在实际应用中能够适用我遇到的很多情况。

自己写写挺好的,虽然原理简单,但是还是需要比较扎实的基础知识才能做好的。做出来容易,做好难啊。
2008-08-12 12:28 | 杨粼波

# re: 服务器公共库开发-内存池管理模块[未登录]  回复  更多评论   

@杨粼波
同意。博主牛。
2008-08-12 12:45 | raof01

# re: 服务器公共库开发-内存池管理模块  回复  更多评论   

@创
确实,这个也算不做造轮子。之前我基本上将SGI的内存池翻译成C代码,所以我对那一块比较熟悉。一看你的代码,我就觉得很眼熟。:D

@金哥
同意你的说法。我觉得我们周围有很多程序员都抱着这样的想法。他们总以“不重造轮子”的观点告诫自己,从而不知道很多东西的底层实现原理。就像有些程序员以“盲目的优化只会适得其反”这样观点为理由,而忽视了优化的重要性一样。

不重造轮子,是基于你懂得造轮子的原理基础上的。而如果你自己都不懂,连重造轮子的能力都没有,那基本就比重造轮子的人还差了。
2008-08-13 10:13 | Kevin Lynx

# re: 服务器公共库开发-内存池管理模块  回复  更多评论   

@杨粼波
是apr_pool,是目前最好的内存池之一(其实我认为“之一”可以去掉),是C实现。
不过C++方面我个人更倾向于采用loki的smallobj的算法。loki的编程风格不太习惯,所以通常也是自己实现一次(好吧,是抄袭,哦呵呵)。

@ricardo
个人以为boost pool不怎么好,还是请横向对比一下其他的内存池设计。

国人许式伟有一个AllocFree不错,不过是单线程的。

btw,严重同意金哥,kevinlynx的看法。如果不是很赶时间,越是基础的东西,越是自己写一次的好。
2008-08-14 13:06 | 矩阵操作

# re: 服务器公共库开发-内存池管理模块  回复  更多评论   

内存池要保证一般情况下,在O(1)时间内分配到请求的内存。你这个似乎不可以。
2008-08-15 12:55 | x-matrix

# re: 服务器公共库开发-内存池管理模块  回复  更多评论   

http://www.codeproject.com/KB/cpp/pools.aspx
很精巧,不过是分配定长的
2008-12-05 19:32 | minus

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理