内存池的设计方案（C语言）

一、前言概述

本人在转发的博文《内存池的设计和实现》中，详细阐述了系统默认内存分配函数malloc/free的缺点，以及进行内存池设计的原因，在此不再赘述。通过对Nginx内存池以及《内存池的设计和实现》的分析后，现提出一种性能更优（申请/释放内存时间复杂度为O(1)）的内存池的设计方案。如有不妥之处，欢迎指正！如有其他的内存池的设计方案，欢迎共同分享和探讨。

二、结构设计

2.1 内存池结构

// 内存池结构体typedef struct{    int unitsize;             // 内存单元大小，即unit的大小    int initnum;             // 初始内存单元的数目    int grownum;           // 每次新增内存单元的数目    int totalnum;            // 内存单元总数    memblock_t *block;     // memblock_t链表头    char *idleunit;          // 空闲内存单元链表头#if defined(__MEMPOOL_THREAD_SUPPORT__)    pthread_mutex_t lock;     // 多线程加锁（支持多线程）#endif /*__MEMPOOL_THREAD_SUPPORT__*/}mempool_t;

// 内存块结构体typdef struct{    int unitnum;           // 内存块总数    int idlenum;            // 空闲内存块数    mempool_t *pool;      // 宿主：所属mempool_t    char *lastunit;         // 结束块地址(此变量可删除)    memblock_t *next;      // 下一个memblock_t}memblock_t;

// 内存单元信息typedefstruct{    memblock_t *block;      // 属主：内存单元所属memblock_t    char *next;             // 下一块内存块地址}memunit_info_t;

2.2 总体结构

内存池的总体结构图为：

图1 总体结构图

2.3 运行机制

此内存池的运行机制如下：

1）将每一个内存单元的大小固定化，可提高内存分配效率。比如：内存单元分别为：{4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, …}（单位：byte, 大小为4byte的整数倍）。Mempool_t之间是通过数组形式组织的，其大体结构如下：（注：为了明确Mempool_t之间的关系，未标出其他变量之间的关系）

图2 Mempool_t数组

注：为提高效率，通过数组存储Mempool_t，在申请内存空间时，可通过偏移量快速定位使用哪个大小的内存池。

2）内存池实际可供分配的内存单元是在Memblock_t中，当所有Memblock_t中的内存单元被使用完后，则需申请开辟一个新的Memblock_t，并加入到Memblock_t链表之中。Memblock_t的组织方式为：（注：为了明确Memblock_t之间的关系，未标出其他变量之间的关系）

图3 Memblock_t链表

3）使用链表组织空闲内存单元，可大大提高内存分配/释放时的效率（时间复杂度为O(1)）。Mempool_t中的idleunit是空闲内存单元的链表头。空闲内存单元的组织形式如下：（注：为明确空闲内存单元之间的关系，未标明其他变量之间的关系）

图4 空闲内存单元链表

说明：Memblock_t中的用红色数字标记的内存单元代表已被分配内存单元，用绿色数字标记的内存单元代表空闲内存单元。

4）当申请内存时，将idleunit指向的内存单元踢出空闲内存单元链表，并idleunit指向内存单元的后继，再返回该内存单元的地址。以图4为例，申请内存块后，空闲内存单元链表如图所示：（注：请对比与图4之间的变化）

图5 内存申请图

注：当申请的内存空间size比所有的内存单元都大时，则通过malloc（）向OS申请size+sizeof(memunit_info_t)的内存空间。

5）当释放内存单元unitn时，将unitn的后继改为idleunit的指向，同时将idleunit指向要释放的内存单元unitn。以图4为例，释红色数字标记的内存单元3后，空闲内存单元链表如图所示：（注：请对比与图4之间的变化）

图6 内存释放图

6）内存单元是通过链表形式进行组织管理的，因此，每个内存单元有额外的空间用来存放组织链表的信息。将图4进一步展开：（注：请结合图4一起看）

图7 内存单元内部结构

说明：

1. 每个内存单元的内部结构：memunit_info_t结构+unitsize大小的空间。每个内存单元的大小为：sizeof(memunit_info_t)+unitsize；

2. idleunit指向的是内存单元的data；空闲内存单元的next指向的是后继内存单元的data，无后继则为NULL；已分配的内存单元的next始终为NULL。

3. 内存单元的block指向宿主Memblock_t，这可快速的确定对当前内存单元属于哪个Memblock_t，再通过Memblock_t中的pool，可快速获知属于哪个Mempool_t。

4. 在分配内存时，返回给用户的是data的地址，而不是内存单元的地址。

7）在释放内存单元时，为使被释放内存单元加入空闲内存单元链表，可通过内存单元的block获知所属Memblock_t，再通过pool获知所属Mempool_t，因此，便可知空闲内存单元链表头idleunit，此时便可将被释放的内存单元加入空闲链表。

图8 所属Mempool_t

2.4 优缺点

通过对以上几点的分析，可知此内存池有以下优缺点：

优点：

1. 定位内存池的时间复杂度为O(1)

内存单元可申请使用的空间大小为4的整数倍，并依次递增。因此，定位内存池的算法:(n为内存池数组下标)

n = size>>2;

if(0 != size&(4-1)) n++;

2. 申请和释放内存的时间复杂度为O(1)

3. 内存碎片较小

4. 支持多线程：开启宏__MEMPOOL_THREAD_SUPPORT__便可支持多线程

5. 互斥量的粒度较小：只锁住一个内存池，其他size的内存池依然可以操作。

缺点：

1. 内存单元的实际大小要比unitsize大sizeof(memunit_info_t)

2. 空闲内存单元绝大部分情况下，分布在不同的Memblock_t中。因此会造成即使空闲内存单元个数超过单个Memblock_t内存单元总数时，可能依然无法释放任何一个Memblock_t。

——邹祁峰

2012.11.18 凌晨2点

2楼sxcong昨天 14:41

tcmalloc很不错

Re: RoyalApex昨天 21:01

回复sxcongn多谢你的提醒，我现在对原有的设计进行了优化，时间复杂度在O(1)。如果仅从性能（时间复杂度）考虑的话，不可能比tcmalloc的差了。

Re: RoyalApex昨天 22:13

回复sxcongn好的。我去看看tcmalloc的设计思路！Thanks！

1楼woaiguzi昨天 10:36

good, 可以考虑下多线程环境下的应用环境。n我这个也是和差不多的实现：nhttp://blog.csdn.net/woaiguzi/article/details/7769061

Re: RoyalApex昨天 10:56

回复woaiguzin嗯！看了一下你的设计思路，我现在也在mempool_t中加入了互斥量。Thanks！