内存池的实现(一)
引言
C/C++下内存管理是让几乎每一个程序员头疼的问题，分配足够的内存、追踪内存的分配、在不需要的时候释放内存——这个任务相当复杂。而直接使用系统调用malloc/free、new/delete进行内存分配和释放，有以下弊端：
- 调用malloc/new,系统需要根据“最先匹配”、“最优匹配”或其他算法在内存空闲块表中查找一块空闲内存，调用free/delete,系统可能需要合并空闲内存块，这些会产生额外开销
- 频繁使用时会产生大量内存碎片，从而降低程序运行效率
- 容易造成内存泄漏
内存池（memory pool)是代替直接调用malloc/free、new/delete进行内存管理的常用方法，当我们申请内存空间时，首先到我们的内存池中查找合适的内存块，而不是直接向操作系统申请，优势在于：
- 比malloc/free进行内存申请/释放的方式快
- 不会产生或很少产生堆碎片
- 可避免内存泄漏
内存池设计
看到内存池好处这么多，是不是恨不能马上抛弃malloc/free，投奔内存池的怀抱呢？且慢，在我们自己动手实现内存池之前还需要明确以下几个问题：
- 内存池的空间如何获得？是程序启动时分配一大块空间还是程序运行中按需求分配？
- 内存池对到来的内存申请，有没有大小的限制？如果有，最小可申请的内存块为多大，最大的呢？
- 如何合理设计内存块结构，方便我们进行内存的申请、追踪和释放呢？
- 内存池占用越多空间，相对应其他程序能使用的内存就越少，是否要设定内存池空间的上限？设定为多少合适呢？
带着以上问题，我们来看以下一种内存池设计方案。
内存池实现方案一
从这里下载该内存池实现的源码。
首先给出该方案的整体架构，如下：
图1.内存池架构图
结构中主要包含block、list 和pool这三个结构体，block结构包含指向实际内存空间的指针，前向和后向指针让block能够组成双向链表；list结构中free指针指向空闲 内存块组成的链表，used指针指向程序使用中的内存块组成的链表，size值为内存块的大小，list之间组成单向链表；pool结构记录list链表的头和尾。
内存跟踪策略
该方案中，在进行内存分配时，将多申请12个字节，即实际申请的内存大小为所需内存大小+12。在多申请的12个字节中，分别存放对应的list指针（4字节）、used指针（4字节）和校验码（4字节）。通过这样设定，我们很容易得到该块内存所在的list和block，校验码起到粗略检查是否出错的作用。该结构图示如下：
图2.内存块申请示意图
图中箭头指示的位置为内存块真正开始的位置。
内存申请和释放策略
申请：根据所申请内存的大小，遍历list链表，查看是否存在相匹配的size；
存在匹配size：查看free时候为NULL
free为NULL：使用malloc/new申请内存，并将其置于used所指链表的尾部
free不为NULL：将free所指链表的头结点移除，放置于used所指链表的尾部
不存在匹配size：新建list，使用malloc/new申请内存，并将其置于该list的used所指链表尾部
返回内存空间指针
释放：根据内存跟踪策略，获取list指针和used指针，将其从used指针所指的链表中删除，放置于free指针所指向的链表
对方案一的分析
对照“内存池设计”一节中提出的问题，我们的方案一有以下特点：
- 程序启动后内存池并没有内存块，到程序真正进行内存申请和释放的时候才接管内存块管理；
- 该内存池对到来的申请，对申请大小并不做限制，其为每个size值创建链表进行内存管理；
- 该方案没有提供限定内存池大小的功能
结合分析，可以得出该方案应用场景如下：程序所申请的内存块大小比较固定（比如只申请/释放1024bytes或2048bytes的内存），申请和释放的频率基本保持一致（因申请多而释放少会占用过多内存，最终导致系统崩溃）。
这篇文章讲解了内存管理的基本知识，以一个简单的内存池实现例子作为敲门砖，引领大家认识内存池，下一篇为内存池进阶文章，讲解apache服务器中内存池的实现方法。
Reference: 《内存池设计研究与应用》by freeeyes
内存池的实现(二)
《内存池的实现(一)》中，介绍了使用内存池的原因，设计内存池应该考虑的问题，最后给出一个简单的内存池实现例子。使用上一篇文章中介绍的内存池实现方案，要在一定的限定条件下，下面我们来看更通用的内存池实现——Apache服务器的内存池实现。
Apache服务器的开发人员将代码中可移植的部分整理出来，编辑成Apache可移植运行库（Apacheportable Run-timelibraries)，简称APR，该库可从这里下载，其中包含这里要介绍的内存池的实现代码。下面将Apache服务器内存池简称为APR内存池。
APR内存池结构
1.内存分配结点
在了解整个内存池架构前，我们先来了解APR内存池中最基本的单元——内存分配结点。内存分配结点被用来描述每次分配的内存块，对应的结构名为apr_memnode_t，定义在文件apr_allocator.h中，其定义如下：
/*struct apr_memnode_t /**< apr_memnode_t**ref; /**< apr_uint32_t /**< apr_uint32_t /**< char *first_avail; /**< char *endp; /**<}; |
即使结构中的每个字段，源文件中都给出了注释，但对于每个字段的用途，还是很难让人理解。这里先给出每个字段的简略解析：
- next：指向下一个结点的指针；
- ref：指向上一结点的next结点，上一结点的next指向本结点，因此**ref就是本结点自身；
- index：既指示了该结点的大小，同时指示了该结点所在链表的索引下标值；
- free_index：所描述的内存块中未被占用的空间（这里和上面的index和它们字面意思有出入，理解的时候要留意）；
- first_avail：指向可用空间开始位置的指针；
- endp：指向可用空间结尾位置的指针。
该结点示意图如下：
2.内存分配器
在ARP内存池中，使用内存分配器对内存分配结点进行管理，它在apr_pools.c中定义如下：
struct apr_allocator_t apr_uint32_t apr_uint32_t apr_uint32_t apr_pool_t apr_memnode_t free[MAX_INDEX];}; |
- max_index：free指针数组的下标，free[max_index]指向已有的最大内存块链表；
- max_free_index：内存分配器所能容纳的最大内存空间数值；
- current_free_index：内存分配器中还能接收的空间大小，与max_free_index结合使用，解决限制内存池空间大小的问题；
- owner：指示该分配器属于哪个内存池；
- free：指向一组链表的头结点，该链表中每个结点指向内存结点组成的链表，MAX_INDEX为20。
内存分配器及其管理的内存结点图示如下：
从上图我们可以清晰地看出，free数组的下标从1到MAX_INDEX-1，分别指向一条结点大小固定的链表，下标增加1，结点的大小增加4k，因此free[MAX_INDEX]所指向的链表的结点大小为84k，这也是内存池使用者所能申请的最大”规则结点“，超过该大小的结点将下标0指向的链表进行管理。要明白free数组下标和结点大小的关系，我们需要知道宏定义APR_ALIGN：
#defineAPR_ALIGN(size, (((size)+ |
该宏所做的无非就是计算出最接近size的boundary的整数倍的整数。通常情况下size大小为整数即可，而boundary则必须保证为2的倍数。比如APR_ALIGN(7,4)为8；APR_ALIGN(21,8)为24；APR_ALIGN(21,16)则为32。
对于每次空间申请，APR先对齐空间大小：
|