内存池设计研究与应用

freeeyes

今天在群里看见有人在讨论内存池的问题，呵呵，想到自己也写过一些内存池，在这里抛砖引玉。
其实内存池的作用大家也知道，一般是解决大量的new和delete频繁操作引起的内存碎片，效率是一方面，另外长时间后的安全性也是一个问题。曾经看过《C++应用程序性能优化》里面的内存池结构，也看过ACE自己的自增式内存池结构，感觉每个都有自己的优点。但是大体思路都是一致的，那就是一次new出一大块内存，然后按照2的幂分配内存块。当申请的内存不够的时候，就会再次分配一个新的内存块，并按照指定的方式切割成小块。如此实现内存的申请与释放。
图示如下:
2个字节空间的链表    内存块1->内存块2->内存块3......
4个字节空间的链表    内存块1->内存块2->内存块3......
8个字节空间的链表    内存块1->内存块2->内存块3......
16个字节的空间链表  内存块1->内存块2->内存块3......
.......

当用户申请内存的时候，根据用户申请的大小块去匹配最接近的2的N次幂的链表。然后从中找到标记为"自由"的内存块，并将指针返回给用户使用。如果链表用完了，也就是所有的块都被占用了，会根据不同的策略生成指定新的连续内存块，提供给用户使用。其实这个架构，大概就是ace的内存池所做的事情。其实大部分内存池不同也就在于如何在重新申请新大内存块的策略不同，原理都是一样的。

以前读过网易云风写过的一本书（《我的编程感悟》），关于游戏中内存的申请与释放的内存池架构，并给出了代码，与《C++应用程序性能优化》不同的是，云风针对不同内存块使用了模板，说真的，从写C++到现在，我个人比较讨厌模板的过度使用，虽然云风说模板的应用会给游戏破解者造成很大麻烦，但是我个人认为这样的做法一样会使阅读你代码的人感到晦涩难懂，尤其是一些高阶模板的应用，会让一些C++初学者感觉像看天书一般，我个人而言也很讨厌看这样的代码。
内存池对于那些需要长时间稳定运行的服务程序尤其重要，几乎所有的24*7运行的系统中都多少包含各种内存池缓冲。下面就说说我写的内存池架构。

其实和上面描述的都差不多，只不过，面向我曾经做过的应用而言，如果一个程序中，有大量的等量内存块的申请（等量内存块指的是，内存块申请和释放大小固定），倒是完全可以再简化一下以上的设计。针对初学者，我希望我能写出一篇比较简单的功能，随时随地拿着走，在不改变任何已有代码的请前提下，将内存池替换到你的系统中去。我写的内存池很简单，但是用到了一些微软曾经做过的手段，呵呵，来切实提高内存池的效率。

从初学者的角度，先看看如果要做一个内存池，需要从哪些方面去想。
（1）我的内存池需要能够在不改动原有代码的情况下，接替new和delete。
（2）我的内存池需要在我需要的时候，给我展示内存池内数据使用的情况（查找内存泄露）
（3）我的内存池需要快速的实现内存的回收和再利用。
（4）我的内存池需要对多线程内存申请提供支持。

恩，内存池设计遇到的难点也是存在的。比如：
（1）我如何控制我的内存池有序的增长
（2）在给定一个指针，遍历内存数据的时候，如何做到最为高效。
（3）如何对内存泄露做监控？

其实网上这方面的资料实在是太多了，也有很多很好的例子。我只是贴出我的代码，给大家提供一些参考。

1. struct _MemoryBlock  //内存块的结构,双向链表
2. {
3.         _MemoryBlock* m_pNext;            //向前的指针
4.         _MemoryBlock* m_pPrev;             //向后的指针
5.         void*         m_pBrick;                   //内存块的指针
7.         void Init()
8.         {
9.                 m_pNext   = NULL;
10.                 m_pPrev   = NULL;
11.                 m_pBrick  = NULL;
12.         };
14.         _MemoryBlock()
15.         {
16.                 Init();
17.         };
18. };

复制代码

这是我的一个内存块大小的标记。这里是一个双向链表，便于查找和跟踪。

1. struct _MemoryList    //内存管理列表
2. {
3.         _MemoryList*  m_pMemLNext;         
4.         _MemoryBlock* m_pMemoryFree;       //自由的内存块
5.         _MemoryBlock* m_pMemoryFreeLast;   //自由的内存块链表末尾
6.         _MemoryBlock* m_pMemoryUsed;       //使用的内存块
7.         _MemoryBlock* m_pMemoryUsedLast;   //使用的内存块链表末尾
9.         int m_nSize;
11.         void Init()
12.         {
13.                 m_pMemLNext       = NULL;
14.                 m_pMemoryFree     = NULL;
15.                 m_pMemoryUsed     = NULL;
16.                 m_pMemoryUsedLast = NULL;
17.                 m_pMemoryFreeLast = NULL;
18.                 m_nSize           = 0;
19.         };
21.         _MemoryList()
22.         {
23.                 Init();
24.         };
25. };

复制代码

既然是基于链表的内存管理，就要有链表，我这里设计了一个链表，m_pMemoryUsed和m_pMemoryUsedLast分别代表正在使用中的内存（被用户申请，还没有释放）链表和当前使用中的内存最后一个对象的地址，m_pMemoryFree和m_pMemoryFreeLast则相反，对应的是自由的内存（被用户释放，却没有申请）的内存链表以及链表最后一个内存地址。之所以这么设计，是为了让系统可以随时知道谁在哪个对象列表中，对反复申请的内存，我只是简单的实现链表中的转移，这样就能比较清晰的看到内存中的数据对象。对于同一个大小的内存块，我会生成一个这样的内存。（我并不像按照2的幂对内存进行分割，因为我个人看来，重复大小的内存块申请要远远多于不定大小的内存块申请频率，考虑到如此，我觉得这部分多于的冗余内存换来的效率是有限的，我个人更倾向于，用到的时候第一次new出来，此后只要有相同的内存块申请，我就用我的内存链去解决，如果链中没有多余的内存，执行一次new，这样做虽然看似一开始很慢，但是运行一段时间以后，内存会趋于稳定，如果在一段时间后内存仍在增长，就要多注意内存泄露的问题了！）

1. class CMemoryPools
2. {
3. public:
4.         static CMemoryPools& Instance()
5.         {
6.                 if(m_pMemoryPools == NULL)
7.                 {
8.                         m_pMemoryPools = (CMemoryPools* )malloc(sizeof(CMemoryPools));
9.                         m_pMemoryPools->Init();
10.                 }
12.                 return *m_pMemoryPools;
13.         }
15. public:
16.         ~CMemoryPools(void);
18.         void* GetBuff(size_t szBuffSize);
19.         bool DelBuff(size_t szBuffSize, void* pBuff);
20.         bool DelBuff(void* pBuff);
21.         void DisplayMemoryList();
23. private:
24.         CMemoryPools(void);
25.         void Close();
26.         void Init();
27.         void* SetMemoryHead(void* pBuff, _MemoryList* pList, _MemoryBlock* pBlock);
28.         void* GetMemoryHead(void* pBuff);
29.         bool GetHeadMemoryBlock(void* pBuff, _MemoryList*& pList, _MemoryBlock*& pBlock);
30.         
32. private:
33.         static CMemoryPools* m_pMemoryPools;
34.         _MemoryList*         m_pMemoryList;
35.         _MemoryList*         m_pMemoryListLast;    //最后一个内存管理链表指针
36.         CThreadLock          m_ThreadLock;
37. };

复制代码

这就是我的内存池类，他公开的方法只有三个，对应着new，delete的重载。还有一个DisplayMemoryList();这个是对应着打印出内存池此时此刻正在使用的内存链表个数，每个链表中有多少内存块在使用，有多少是自由内存，用于内存泄露的跟踪。一般情况下，内存泄露都会出现在某一个或者几个内存链中存在超大正在使用的内存个数的现象，比较好追踪，对于这个内存是谁申请的，我有我的方法，下面会做描述。因为考虑到代码的跨平台使用，所以有些部分自己手动加了一些代码。而没有用__FILE__这样的宏。

在这里我使用了一个小技巧，当用户申请内存的时候，我返回给用户内存地址不是我内存块一开始的地址，而是向后偏移了12个字节（当然，new的时候会是 实际大小 + 12个字节），这多出来的12个字节，就是内存头，记录用户申请内存时这块内存的一些参数，因为当用户delete的时候，如果我有一个无比庞大的内存列表，我一个个去遍历这样的效率我是无法接受的。所以我在这里存储了12个字节的内存快大小，这样做我能很快的定位这个内存地址在我的哪一个链表下，在什么位置，这样做完全可以在不做循环的接触上，在海量的内存里迅速定位自己的位置。并完成内存块使用和非使用之间的数据转移。其实，对于用户而言，偏移的这个内存位置它完全不用知道，微软当年就是这么干的，只不过内存头记录的东西比我还多。当释放内存的时候，找到内存头只需要向前获取4个字节的指针位置即可。其实，如果你喜欢，完全可以继续扩展增加这四个字节，比如记录何时申请的等等。。。这一招我觉得真的很有效果。

1. void* CMemoryPools::SetMemoryHead(void* pBuff, _MemoryList* pList, _MemoryBlock* pBlock)
2. {
3.         //组成内存包头
4.         if(NULL == pBuff)
5.         {
6.                 return NULL;
7.         }
9.         //因为一个long是4个字节，在linux和windows下都是一样的。所以加起来是12个
10.         UINT32* plData = (UINT32*)pBuff;
12.         plData[0] = (UINT32)pList;         //内存链表首地址
13.         plData[1] = (UINT32)pBlock;        //所在链表的地址
14.         plData[2] = (UINT32)MAGIC_CODE;    //验证码
16.         return &plData[3];
17. }

复制代码

这里我加了一个验证码，为了防止给别的内存造成破坏，在创造内存的时候，我会加一段特殊标记，而我释放内存的时候，会检验这个标记，如果有就证明是我的内存池的内存成员，否则我就会丢弃不去操作这段内存。最大限度的保证内存的稳定性。

1. bool CMemoryPools::DelBuff(void* pBuff)
2. {
3.         //添加线程安全
4.         CAutoLock autolock(&m_ThreadLock);
6.         _MemoryBlock* pMemoryUsed     = NULL;
7.         _MemoryList*  pCurrMemoryList = NULL;
9.         if(false == GetHeadMemoryBlock(pBuff, pCurrMemoryList, pMemoryUsed))
10.         {
11.                 return false;
12.         }
14.         if(NULL != pMemoryUsed && NULL != pCurrMemoryList)
15.         {
16.                 //如果是列表的第一个，则直接把下一个链表的地址复制到前一个
17.                 if(pCurrMemoryList->m_pMemoryUsed == pMemoryUsed)
18.                 {
19.                         pCurrMemoryList->m_pMemoryUsed = pMemoryUsed->m_pNext;
20.                 }
21.                 else
22.                 {
23.                         pMemoryUsed->m_pPrev->m_pNext = pMemoryUsed->m_pNext;
24.                 }
26.                 if(NULL != pMemoryUsed->m_pNext)
27.                 {
28.                         pMemoryUsed->m_pNext->m_pPrev = pMemoryUsed->m_pPrev;
29.                 }
31.                 if(pMemoryUsed == pCurrMemoryList->m_pMemoryUsedLast)
32.                 {
33.                         pCurrMemoryList->m_pMemoryUsedLast = pCurrMemoryList->m_pMemoryUsedLast->m_pPrev;
34.                 }
36.                 if(pCurrMemoryList->m_pMemoryFree == NULL)
37.                 {
38.                         //printf_s("[CMemoryPools::DelBuff] pBuff = 0x%08x.\n", pBuff);
39.                         pMemoryUsed->m_pPrev               = NULL;
40.                         pMemoryUsed->m_pNext               = NULL;
41.                         pCurrMemoryList->m_pMemoryFree     = pMemoryUsed;
42.                         pCurrMemoryList->m_pMemoryFreeLast = pMemoryUsed;
43.                         //printf_s("[CMemoryPools::DelBuff] 内存列表为空 m_pMemoryFree.m_pBrick = 0x%08x.\n", pCurrMemoryList->m_pMemoryFreeLast->m_pBrick);
44.                 }
45.                 else
46.                 {
47.                         //printf_s("[CMemoryPools::DelBuff] pBuff = 0x%08x.\n", pBuff);
48.                         pMemoryUsed->m_pPrev                        = pCurrMemoryList->m_pMemoryFreeLast;
49.                         pMemoryUsed->m_pNext                        = NULL;
50.                         pCurrMemoryList->m_pMemoryFreeLast->m_pNext = pMemoryUsed;
51.                         pCurrMemoryList->m_pMemoryFreeLast          = pMemoryUsed;
52.                         //printf_s("[CMemoryPools::DelBuff] 内存列表非空 m_pMemoryFree.m_pBrick = 0x%08x.\n", pCurrMemoryList->m_pMemoryFreeLast->m_pBrick);
53.                 }
55.                 return true;
56.         }
57.         else
58.         {
59.                 //printf_s("[CMemoryPools::DelBuff] pBuff = 0x%08x pMemoryUsedProv is NULL.\n", pBuff);
60.                 return false;
61.         }
64.         //printf_s("[CMemoryPools::DelBuff] pBuff = 0x%08x is not memoryPool.\n", pBuff);
65.         return false;
66. }

复制代码

这段代码就是我释放内存操作所做的事情，和网上的例子有些不同，无论我的内存链表是如何海量，都不会影响到我的使用效率，因为我完全没有用循环。只是一次操作，所以delete时候的效率归还数据是稳定的。我曾经在某一个大型网络游戏中使用了这部分代码，效果很不错。

呵呵，其实，我的内存池很简单，最复杂的就是对内存链表的位移操作，其实这部分想清楚就行了，相对于云风和《C++性能优化》的内存池不同，有了一些自己的想法。对于内存池，稳定性是很不错的，优秀的搜索算法更能帮助我们提升自己的效率。站在他们的肩膀上，进一步优化了一下内存池的架构。

当然，你们要使用它很简单。只需要重载new和delete。

附件是我这个内存池的代码原本，在windows下和linux下都测试通过，并且现在还运行在一些项目中，比较稳定。希望能够帮助大家。
在这里，我加了一点数据锁，为了保持对内存申请和释放的线程安全，这部分见仁见智。
另外，声明一点，我的内存池不适于那种dll里面new，然后在程序里delete的操作，因为dll和exe有可能有不同的副本。我曾经把我的内存池移植到ACE中，后来发现在ConnectHandle的时候有这样的现象，只好使用ACE的内存池。这点要注意，当然，大家有对这个问题的好的解决方法，请告诉我，谢谢。

[ 本帖最后由 freeeyes 于 2010-4-6 12:29 编辑 ]

wishel

支持下楼主，等我有时间的时候仔细看一下代码。
最近看过loki的小型内存分配器，设计的很巧妙，推荐大家参考。

iq50

牛X，好好看看，学习下

dce163

感谢楼主！支持楼主多发精品贴！

xiaohonghong

谢谢楼主，好好研究下，测试过了么？

11201231

不错，研究下

dongmingyi

版主是好人

djoin

刚下了楼主的代码，在VC6.0下测试了，有内存泄露
不知道是我用的不错还是什么。
1，static CMemoryPools& Instance() 出来，但是代码好像没有释放m_pMemoryPools这个指针
2. m_ThreadLock.Init();但是确没有找到地方m_ThreadLock.Close()。。

freeeyes

1. CMemoryPools& Instance()是一个单件，进程结束后，会被释放内存，这里不会被调用析构。具体这里可以查看单件的说明文档。
2.你说的CThreadLock的init只是在于初始化锁对象对象而已，在析构中会自动调用Close()方法，Close()方法只在于清除使用过的锁对象，在使用中，CAutoLock autolock(&m_ThreadLock);，会在构造和析构中调用CThreadLock的lock和unlock达到自动加解锁的目的。

djoin

我明白你说的意思，刚从。net到vc，所以还是有些不懂！
但是在VC6.0,vc10下，创建对话框项目下就是有内存泄露，而且进程退出也不调用close()，不信你试试。
我改了下，如下：
#ifdef _DEBUG
inline void* operator new(size_t nSize, LPCSTR lpszFileName, int nLine)
#else
inline void* operator new(size_t szBuff)
inline void operator delete(void* p)
inline void operator  delete[]( void * p )
#endif

我怀疑是不是在重写new和delete有问题，可是我一直看不出问题所在。
麻烦楼主帮我看下，谢谢啦