////////////////////////////////////////////////////////////////////////
转载须知：
本文作者：张中庆，网名，flydish
最早出处：http://blog.csdn.net/tingya
作者联系地址：flydish1234#sina.com.cn,请把其中的#替换为@，防止Spam收集
请保留上述信息，欢迎共同探讨关于Apache源代码的一切
关键词:Apache，Memory Pool，内存池, APR
//////////////////////////////////////////////////////////////////////
2.3 内存池分配子allocator
2.3.1分配子概述
尽管我们可以通过malloc函数直接分配apr_memnode_t类型的结点，不过Apache中并不推荐这种做法。事实上Apache中的大部分的内存的分配都是由内存分配子allocator完成的。它隐藏了内部的实际的分配细节，对外提供了几个简单的接口供内存池函数调用。内存分配子属于内部数据结构，外部程序不能直接调用。内存分配子(以后简称为分配子)在文件apr_pools.c中进行定义如下：
struct apr_allocator_t {
apr_uint32_t max_index;
apr_uint32_t max_free_index;
apr_uint32_t current_free_index;
#if APR_HAS_THREADS
apr_thread_mutex_t *mutex;
#endif /* APR_HAS_THREADS */
apr_pool_t *owner;
apr_memnode_t *free[MAX_INDEX];
};
该结构中最重要的无非就是free数组，数组的每个元素都是apr_memnode_t类型的地址，指向一个apr_memnode_t类型的结点链表。内存分配的时候则从实际的结点中进行分配，使用完毕后同时返回给分配子。
不过free中的链表中结点的大小并不完全相同，其取决于当前链表在free数组中的索引。此处free数组的索引index具有两层次的含义：第一层，该结点链表在数组中的实际索引，这是最表层的含义；另外，它还标记了当前链表中结点的大小。索引越大，结点也就越大。同一个链表中的所有结点大小都完全相等，结点的大小与结点所在链表的索引存在如下的关系：
结点大小 = 8K + 4K*(index-1)
因此如果链表索引为2，则该链表中所有的结点大小都是12K；如果索引为MAX_INDEX，即20，则结点大小应该为8K+4K*(MAX_INDEX-1)=84K，这也是Apache中能够支持的“规则结点”的最大数目。不过这个公式仅仅适用于数组中1到MAX_INDEX的索引，对于索引0则不适合。当且仅当用户申请的内存块太大以至于超过了规则结点所能承受的84K的时候，它才会到索引为0的链表中去查找。该链表中的结点通常都大于84K，而且每个结点的大小也不完全相同。
在后面的部分，我们将索引1到MAX_INDEX所对应的链表统称为“规则链表”，而每一个链表则分开称之为“索引n链表”，与之对应，规则链表中的结点则统称为“规则结点”，或者称则为“索引n结点”，这是因为它们的大小有一定的规律可遵循；而索引0对应的链表则称之为“索引0链表”，结点则称之为“索引0结点”。
根据上面的描述，我们可以给出分配子的内存结构如图3.2所示。
图3.2 分配子内存结构示意
理论上，分配子中的最大的结点大小应该为8K+4K*(MAX_INDEX-1)，但实际却未必如此，如果从来没有分配过8K+4K*(MAX_INDEX-1)大小的内存，那么MAX_INDEX索引对应的链表很可能是空的。此时在分配子中我们用变量max_index表示实际的最大结点。另外如果结点过大，则占用内存过多，此时有必要将该结点返回给操作系统，分配子将max_free_index作为内存回收的最低门槛。如果该结点小于max_free_index，则不做任何处理，否则使用后必须进行释放给操作系统。current_free_index则是…。除此之外，mutex用户保证多线程访问时候的互斥，而owner则记录了当前分配子所属于的内存池。
针对分配子，Apache中提供了几个相关的函数，函数名称和作用简要概述如表格3.1。
表3.1 Apache中提供了分配子相关函数
分配子操作
函数名称
函数功能简单描述
创建
apr_allocator_create
创建一个新的分配子
销毁
apr_allocator_destroy
销毁一个已经存在的分配子
空间分配
apr_allocator_alloc
调用分配子分配一定的空间
空间释放
apr_allocator_free
释放分配子已经分配的空间，将它返回给分配子
其余设置
apr_allocator_owner_set
apr_allocator_owner_get
设置和获取分配子所属的内存池
apr_allocator_max_free_set
apr_allocator_set_max_free
设置和获取分配子内部的互斥变量
2.3.2分配子创建与销毁
分配子的创建是所有的分配子操作的前提，正所谓“毛之不存，皮将焉附”。分配子创建使用函数apr_allocator_create实现：
APR_DECLARE(apr_status_t) apr_allocator_create(apr_allocator_t **allocator)
{
apr_allocator_t *new_allocator;
*allocator = NULL;
if ((new_allocator = malloc(SIZEOF_ALLOCATOR_T)) == NULL)
return APR_ENOMEM;
memset(new_allocator, 0, SIZEOF_ALLOCATOR_T);
new_allocator-max_free_index = APR_ALLOCATOR_MAX_FREE_UNLIMITED;
*allocator = new_allocator;
return APR_SUCCESS;
}
分配子的创建非常的简单，它使用的函数则是最通常的malloc，分配大小为SIZEOF_ALLOCATOR_T即APR_ALIGN_DEFAULT(sizeof(apr_allocator_t))大小。当然这块分配的空间也包括了MAX_INDEX个指针变量数组。一旦分配完毕，函数将max_free_index初始化为APR_ALLOCATOR_MAX_FREE_UNLIMITED，该值实际为0，表明分配子对于回收空闲结点的大小并不设门槛，意味着即使结点再大，系统也不会回收。
创建后，结构中的max_inde，current_free_index都被初始化为0，这实际上是由memset函数隐式初始化的。一旦创建完毕，函数将返回创建的分配子。只不过此时返回的分配子中的free数组中不包含任何的实际的内存结点链表。
对分配子使用的正常的下一步就应该是对结构成员进行初始化。主要的初始化工作就是设置系统资源归还给操作系统的门槛max_free_index。在后面我们会看到，对于使用malloc分配的内存，如果其大小小于该门槛值，那么这些资源并不释放，而是归还给内存池，当内存池本身被释放的时候，这些内存才真正释放给操作系统；如果内存的大小大于这个门槛值，那么内存将直接释放给操作系统。这个门槛值的设置由函数apr_allocator_max_free_set完成：
APR_DECLARE(void) apr_allocator_max_free_set(apr_allocator_t *allocator,
apr_size_t in_size)
{
apr_uint32_t max_free_index;
apr_uint32_t size = (APR_UINT32_TRUNC_CAST)in_size;
max_free_index = APR_ALIGN(size, BOUNDARY_SIZE) BOUNDARY_INDEX;
allocator-current_free_index += max_free_index;
allocator-current_free_index -= allocator-max_free_index;
allocator-max_free_index = max_free_index;
if (allocator-current_free_index max_free_index)
allocator-current_free_index = max_free_index;
}
参数中的size经过适当的对齐调整赋值给分配子结构中的max_free_index。除了max_free_index之外，另外一个重要的成员就是current_free_index，该成员记录当前内存池中实际的最大的内存块大小。当然，它的值不允许超出max_free_index的范围。
与分配子的创建对应的则是分配子的销毁，销毁使用的是函数apr_allocator_destroy。当分配子被销毁的时候，我们需要确保下面两方面的内容都被正确的销毁：
(1)、分配子本身的内存被释放，这个可以直接调用free处理
(2)、由于分配子中内嵌的free数组都指向一个实际的结点链表，因此必须保证这些链表都被正确的释放。在释放链表的时候，通过一旦得到头结点，就可以沿着next遍历释放链表中的所有结点。
必须需要注意的是两种释放之前的释放顺序问题。正确的释放顺序应该是链表释放最早；其次才是分配子本身内存的释放。Apache中对应该部分是释放代码如下：
APR_DECLARE(void) apr_allocator_destroy(apr_allocator_t *allocator)
{
apr_uint32_t index;
apr_memnode_t *node, **ref;
for (index = 0; index free[index];
while ((node = *ref) != NULL) {
*ref = node-next;
free(node);
}
}
free(allocator);
}
2.3.3分配子内存分配
使用分配子分配内存是最终的目的。Apache对外提供的使用分配子分配内存的函数是apr_allocator_alloc，然而实际在内部，该接口函数调用的则是allocator_alloc。
allocator_alloc函数原型声明如下：
apr_memnode_t *allocator_alloc(apr_allocator_t *allocator, apr_size_t size)
函数的参数非常简单，allocator则是内存分配的时候调用的分配子，而size则是需要进行分配的大小。如果分配成功，则返回分配后的apr_memnode_t结构。
{
apr_memnode_t *node, **ref;
apr_uint32_t max_index;
apr_size_t i, index;
size = APR_ALIGN(size + APR_MEMNODE_T_SIZE, BOUNDARY_SIZE);
if (size BOUNDARY_INDEX) - 1;
if (index APR_UINT32_MAX) {
return NULL;
}
函数所做的第一件事情就是按照我们前面所说的分配原则调整实际分配的空间大小：如果不满8K，则以8K计算；否则调整为4K的整数倍。同时函数还将计算该与该结点对应的索引大小。一旦得到索引大小，也就知道了结点链表。至此Apache可以去寻找合适的结点进行内存分配了。
从分配子中分配内存必须考虑下面三种情况：
(1)、如果需要分配的结点大小分配子中的“规则结点”能够满足，即indexmax_index。此时，能够满足分配的最小结点就是index索引对应的链表结点，但此时该索引对应的链表可能为空，因此函数将沿着数组往后查找直到找到第一个可用的不为空结点或者直到数组末尾。同时程序代码中还给出了另外一种策略以及不使用的原因：
NOTE: an optimization would be to check allocator-free[index] first and if no node is present, directly use allocator-free[max_index]. This seems like overkill though and could cause memory waste.
另外一种方案就是首先直接检查allocator-free[index]，一旦发现不可用，直接使用最大的索引allocator-free[max_index]，不过这种策略可能导致内存的浪费。Apache采用的则是“最合适”原则，按照这种原则，找到的第一个内存肯定是最合适的。下面的斜体代码所作的无非如此：
if (index max_index) {
max_index = allocator-max_index;
ref = &allocator-free[index];
i = index;
while (*ref == NULL && i next) == NULL && i = max_index) {
do {
ref--;
max_index--;
}
while (*ref == NULL && max_index 0);
allocator-max_index = max_index;
}
allocator-current_free_index += node-index;
if (allocator-current_free_index allocator-max_free_index)
allocator-current_free_index = allocator-max_free_index;
node-next = NULL;
node-first_avail = (char *)node + APR_MEMNODE_T_SIZE;
return node;
}
(2)、如果分配的结点大小超过了 “规则结点”中的最大结点，函数将考虑索引0链表。索引0链表中的结点的实际大小通过成员变量index进行标记。
在通过next遍历索引0链表的时候，函数将需要的大小index和实际的结点的大小node-index进行比较。如果indexnode-index，则明显该结点无法满足分配要求，此时必须继续遍历。一旦找到合适的可供分配的结点大小，函数将调整node-first_avail指针指向实际可用的空闲空间。另外还需要调整分配子中的current_free_index为新的分配后的值。
(3)、如果在free[0]链表中都找不到合适的空间供分配，那么此时只能“另起炉灶”了。函数能做的事情无非就是调用malloc分配实际大小的空间，并初始化结点的各个变量，并返回，代码如下：
if ((node = malloc(size)) == NULL)
return NULL;
node-next = NULL;
node-index = index;
node-first_avail = (char *)node + APR_MEMNODE_T_SIZE;
node-endp = (char *)node + size;
下面我们来看一个Apache中典型的调用分配子分配空间的情况，下面的代码你可以在worker.c中找到：
apr_allocator_t *allocator;
apr_allocator_create(&allocator);
apr_allocator_max_free_set(allocator, ap_max_mem_free);
apr_pool_create_ex(&ptrans, NULL, NULL, allocator);
apr_allocator_owner_set(allocator, ptrans);
当我顺着这段代码往下阅读的时候，我曾经感觉到很困惑。当一个分配子创建初始，内部的free数组中的索引链表都为空，因此当我们在apr_pool_create_ex中调用node = allocator_alloc(allocator, MIN_ALLOC - APR_MEMNODE_T_SIZE)) == NULL的时候，所需要的内存就不可能来自索引链表内的结点中，而只能就地分配，这些结点一旦分配后，它们就作为内存池的结点而被使用，但是分配后的结点却并没有立即与free数组进行关联，即并没有对free数组中的元素进行赋值。这样，如果不将结点与free数组进行“挂接”，那么将永远都不可能形成图一所示链表结构。
那么它们什么时候才挂接到free数组中的呢？原来所有的挂接过程都是在结点释放的时候才进行的。
2.3.4分配子内存释放
正如前面所描述的，在分配内存的时候，Apache首先尝试到现有的链表中去查找适合的空间，如果没有适合的内存区域的话，Apache必须按照上述的分配原则进行实际的内存分配并使用。但是实际的内存块并不会立即挂接到链表中去，只有释放的时候，这些区域才挂接到内存中。所以从这个角度而言，分配子内存的释放并不是真正的将内存调用free释放，而将其回收到分配链表池中。
Apache中提供的内存释放函数是apr_allocator_free。不过该函数仅仅是对外提供的接口而已，在函数内存调用的则实际上是allocator_free。allocator_free函数的原型如下：
static APR_INLINE void allocator_free(apr_allocator_t *allocator, apr_memnode_t *node)
函数中，node是需要释放的内存结点，其最终归还给分配子allocator。
{
apr_memnode_t *next, *freelist = NULL;
apr_uint32_t index, max_index;
apr_uint32_t max_free_index, current_free_index;
max_index = allocator-max_index;
max_free_index = allocator-max_free_index;
current_free_index = allocator-current_free_index;
由于node不仅仅可能是一个结点，而且可能是一个结点链表，因此如果需要完全释放该链表中的结点，则必须通过结点中的next进行依次遍历，因此下面的循环就是整个释放过程的框架结构：
do {
next = node-next;
index = node-index;
……
} while ((node = next) != NULL);
对于每个结点，我们将根据它的索引大小（即内存大小）采取不同的处理策略：
(1)、如果结点的大小超过了完全释放的阙值max_free_index，那么我们就不能将其简单的归还到索引链表中，而必须将其完全归还给操作系统。函数将所有的这样的需要完全释放的结点保存在链表freelist中，待所有的结点遍历完毕后，只需要释放freelist就可以释放所有的必须释放的结点，如下所示：
if (max_free_index != APR_ALLOCATOR_MAX_FREE_UNLIMITED
&& index current_free_index) {
node-next = freelist;
freelist = node;
}
如果max_free_index为APR_ALLOCATOR_MAX_FREE_UNLIMITED则意味着没有回收门槛。任何内存，不管它有多大，APR都不会将其归还给操作系统。
(2)、如果indexmax_index，则必须重新更新max_index的大小，同时将该结点插入链表的首部，作为首结点，代码可以描述如下：
else if (index next = allocator-free[index]) == NULL
&& index max_index) {
max_index = index;
}
allocator-free[index] = node;
current_free_index -= index;
}
(3)、如果结点超过了“规则结点”的范围，但是并没有超出回收结点的范围，此时我们则可以将其置于“索引0”链表的首部中。代码如下：
else {
node-next = allocator-free[0];
allocator-free[0] = node;
current_free_index -= index;
}
待所有的结点处理完毕后，我们还必须调整分配子中的各个成员变量，包括max_index和current_free_index。同时不要忘记释放freelist链表。
allocator-max_index = max_index;
allocator-current_free_index = current_free_index;
while (freelist != NULL) {
node = freelist;
freelist = node-next;
free(node);
}
当上面的工作都完成后，整个结点的释放也就完毕了。事实上整个内存池中的内存就是通过上面的不断地释放而构建起来的。一旦构建了内存池，下一次的时候则可以直接去内存池中获取了。
2.3.5分配子内存管理流程
根据上面的描述，我们现在来串起来看一些整个分配子工作的流程。假如存在下面一段代码：
1. apr_allocator_t *allocator;
2. apr_allocator_create(&allocator);
3. apr_allocator_max_free_set(allocator, 0);//简单起见，不进行任何回收
4. apr_memnode_t *memnode1 = apr_allocator_alloc(allocator, 3000);
5. apr_allocator_free(memnode1);
6. apr_memnode_t *memnode2 = apr_allocator_alloc(allocator, 3000);
7. apr_allocator_free(memnode2);
8. apr_memnode_t *memnode3 = apr_allocator_alloc(allocator, 3000);
9. apr_allocator_free(memnode3);
当第一行执行完毕后，创建的分配子示意图如下图所以，该图中尚未有任何的内存块可供分配：
在第四行中，系统需要内存分配子分配2000字节的空间，但此时没有任何空间可供分配(index allocator-max_index，同时allocator-free[0]==NULL)，因此分配子将直接向操作系统索取8K的空间，剔除结构头的大小，实际可用的内存大小为8k-APR_MEMNODE_T_SIZE。
当执行完第五行的时候，该内存将被归还给分配子，同时保存在索引1链表中。下图中的虚线剔除后为释放前的状态，反之为释放后的状态。结果如下图：
现在我们来考虑第六行和第七行的执行结果。当再次向分配子申请3000K的内存的时候，经过计算发现，该内存必须到索引为1链表中去获取。如果索引1链表为NULL，则重复前面的步骤；
