C语言内存池使用模型
在用C语言开发时，特别是在服务器端，内存的使用会成为系统性能的一个瓶颈，如频繁地分配和释放内存，会不断的增加系统的内存碎片，影响内核之后分配内存的效率，这个时候一个比较可行的做法是采用内存池，先分配好比较多的内存，然后在这个已经分配的内存里使用内存，这样就不需要内核过多的参与内存分配和释放的过程。
内存池根据应用不同有多种实现的策略，如有些分配很大的内存，然后将内存分配成大小相等的块，并将每个块链接起来进行管理。
下面对模型介绍的时候，为了简单，不加入用于调试的编写技巧和为之准备的结构，其实主要是省去间接调用，有时为了调试，会将文件及所在行以及主要的变量状态输出。
一.内存池访问接口
创建大小为size的新的内存池。
pool_t _pool_new_heap（int size）；
从指定内存池中分配大小为size的内存空间，这些空间会在内存池释放时，被自动的释放。
void *pool_malloc（pool_t, int size）；
内存池的大小，返回内存池中所有内存块的大小总和
int pool_size（pool_t p）；
释放内存池，这会导致所有内存被释放，同时内存池本身也被释放
void pool_free（pool_t p）；
还有其它的一些接口，但这些是主要的接口。
pool_t _pool_new_heap（int size）；
从指定内存池中分配大小为size的内存空间，这些空间会在内存池释放时，被自动的释放。
void *pool_malloc（pool_t, int size）；
内存池的大小，返回内存池中所有内存块的大小总和
int pool_size（pool_t p）；
释放内存池，这会导致所有内存被释放，同时内存池本身也被释放
void pool_free（pool_t p）；
还有其它的一些接口，但这些是主要的接口。
二. 数据结构
struct pheap
{
void *block;
int size, used;
};
该结构表示内存池中一个内存块的抽象表示，
1、block 用于指向由malloc所分配的内存地址。
2、size 表示block所指向地址的内存大小。
3、used 表示多少处于已经使用的状态。在分配内存时，这个域很重要，它表示内存块可以被分配的偏移值，也就是从used开始的内存都是可以被从内存池中分配出去的。
struct pfree
{
pool_cleanup_t f;
void *arg;
struct pheap *heap;
struct pfree *next;
};
typedef void （*pool_cleanup_t）（void *arg）；
这个结构用于实现一个链表，将所有的内存块链接起来。每一个内存块，对映一个这个结构，也就是每个struct pheap结构，都有一个struct pfree结构将其封装起来，这个结构主要实现下面几个功能：
1、实现内存块的链表，用struct pfree *next连接起来，这是一个单链表。
2、内存块释放的回调。注册在释放内存时，如果释放这个内存块，主要是通过pool_cleanup_t f和void *arg两个域来完成这个功能。
3、pheap域用于指向需要被放入链表的内存块，就是前面的结构。
typedef struct pool_struct
{
int size;
struct pfree *cleanup;
struct pfree *cleanup_tail;
struct pheap *heap;
} _pool, *pool_t;
结构中的域代表如下：
heap:指向内存池中最新申请的内存块，在每次申请内存块时，都会将其指向新的内存块。
cleanup和cleanup_tail:指向链表的头和尾的指针。
size:表示内存池中内存的大小，包括所有的内存块。
这个结构的主要功能如下：
1、管理内存块。通过cleanup和clean_tail两个指针，因为内存块在内存池中是以单链表的形式组织的，这两个指针分别指向链表的头和尾指针。
2、内存池中可用的内存大小。通过size域来统计完成。
3、获取最新的内存块指针。通过heap指针在每次分配内存块时重新赋值来实现。
这个内存池的实现，主要是依靠上面三个数据结构来完成，其实估计已经知道的差不多了。
{
void *block;
int size, used;
};
该结构表示内存池中一个内存块的抽象表示，
1、block 用于指向由malloc所分配的内存地址。
2、size 表示block所指向地址的内存大小。
3、used 表示多少处于已经使用的状态。在分配内存时，这个域很重要，它表示内存块可以被分配的偏移值，也就是从used开始的内存都是可以被从内存池中分配出去的。
struct pfree
{
pool_cleanup_t f;
void *arg;
struct pheap *heap;
struct pfree *next;
};
typedef void （*pool_cleanup_t）（void *arg）；
这个结构用于实现一个链表，将所有的内存块链接起来。每一个内存块，对映一个这个结构，也就是每个struct pheap结构，都有一个struct pfree结构将其封装起来，这个结构主要实现下面几个功能：
1、实现内存块的链表，用struct pfree *next连接起来，这是一个单链表。
2、内存块释放的回调。注册在释放内存时，如果释放这个内存块，主要是通过pool_cleanup_t f和void *arg两个域来完成这个功能。
3、pheap域用于指向需要被放入链表的内存块，就是前面的结构。
typedef struct pool_struct
{
int size;
struct pfree *cleanup;
struct pfree *cleanup_tail;
struct pheap *heap;
} _pool, *pool_t;
结构中的域代表如下：
heap:指向内存池中最新申请的内存块，在每次申请内存块时，都会将其指向新的内存块。
cleanup和cleanup_tail:指向链表的头和尾的指针。
size:表示内存池中内存的大小，包括所有的内存块。
这个结构的主要功能如下：
1、管理内存块。通过cleanup和clean_tail两个指针，因为内存块在内存池中是以单链表的形式组织的，这两个指针分别指向链表的头和尾指针。
2、内存池中可用的内存大小。通过size域来统计完成。
3、获取最新的内存块指针。通过heap指针在每次分配内存块时重新赋值来实现。
这个内存池的实现，主要是依靠上面三个数据结构来完成，其实估计已经知道的差不多了。
三.创建一个空的内存池
创建一个空的内存池比较简单，就是初始化一个内存池结构，也就是pool_t结构，并将其链表置为NULL,大小为0,不包含任何的内存块。
pool_t _pool_new（）
{
pool_t p;
while（（p = malloc（sizeof（_pool））） == NULL） sleep（1）；
p->cleanup = NULL;
p->heap = NULL;
p->size = 0;
return p;
}
pool_t _pool_new（）
{
pool_t p;
while（（p = malloc（sizeof（_pool））） == NULL） sleep（1）；
p->cleanup = NULL;
p->heap = NULL;
p->size = 0;
return p;
}
四.创建指定大小的内存池
创建一个包含大小为size内存块的内存池，这个操作分两步，先创建一个空的内存池，然后再创建一个内存块，并将该内存块加入内存池中，也就是将内存块加到内存池的链表末尾，并重新设定指针。
pool_t _pool_new_heap（int size）
{
pool_t p;
p = _pool_new（）；
p->heap = _pool_heap（p,size）；
return p;
}
pool_t _pool_new_heap（int size）
{
pool_t p;
p = _pool_new（）；
p->heap = _pool_heap（p,size）；
return p;
}
第一步是先调用_pool_new创建一个空的内存池结构，这个前面已经说明了，操作很简单。看第二步是怎么完成的
static struct pheap *_pool_heap（pool_t p, int size）
{
struct pheap *ret;
struct pfree *clean;
while（（ret = _pool__malloc（sizeof（struct pheap））） == NULL） sleep（1）；
while（（ret->block = _pool__malloc（size）） == NULL） sleep（1）；
ret->size = size;
p->size += size;
ret->used = 0;
clean = _pool_free（p, _pool_heap_free, （void *）ret）；
clean->heap = ret; /* for future use in finding used mem for pstrdup */
_pool_cleanup_append（p, clean）；
return ret;
}
第二步包含下面一些操作：
1、申请一个大小为size的内存块，也就是前方中介绍的pheap结构。
2、把这个内存块的大小size,加到内存池上，就是那个p->size += size;
3、将内存块关联到struct pfree结构。这会指示内存释放的方式，也把内存加入到链表元素上。
4、将struct pfree结构关联到内存池，其实就是加到链表的末尾。
下面会讨论第3和第4部是怎么实现的。
static struct pheap *_pool_heap（pool_t p, int size）
{
struct pheap *ret;
struct pfree *clean;
while（（ret = _pool__malloc（sizeof（struct pheap））） == NULL） sleep（1）；
while（（ret->block = _pool__malloc（size）） == NULL） sleep（1）；
ret->size = size;
p->size += size;
ret->used = 0;
clean = _pool_free（p, _pool_heap_free, （void *）ret）；
clean->heap = ret; /* for future use in finding used mem for pstrdup */
_pool_cleanup_append（p, clean）；
return ret;
}
第二步包含下面一些操作：
1、申请一个大小为size的内存块，也就是前方中介绍的pheap结构。
2、把这个内存块的大小size,加到内存池上，就是那个p->size += size;
3、将内存块关联到struct pfree结构。这会指示内存释放的方式，也把内存加入到链表元素上。
4、将struct pfree结构关联到内存池，其实就是加到链表的末尾。
下面会讨论第3和第4部是怎么实现的。
五.内存池管理内存机制(单链表管理结构)
这里主要是讨论，从内存块申请开始，就是申请了一个pheap结构指向内存块，然后内存池以什么形式将内存块组织起来，这一个很重要的结构是struct
pfree结构。
看一下前面申请内存块之后，这时还只是一个pheap结构，没有和内存池关联起来，在前方我们看到，是通过下面代码进行关联的
clean = _pool_free（p, _pool_heap_free, （void *）ret）；
clean->heap = ret; /* for future use in finding used mem for pstrdup */
_pool_cleanup_append（p, clean）；
_pool_free为该内存块定义的一个结构进行初始化，如下调用
static struct pfree *_pool_free（pool_t p, pool_cleanup_t f, void *arg）
{
struct pfree *ret;
while（（ret = malloc（sizeof（struct pfree））） == NULL） sleep（1）；
ret->f = f;
ret->arg = arg;
ret->next = NULL;
return ret;
}
这个函数只是定义了一个sturct pfree结构，基本上是用struct pheap这个结构对其进行初始化的，可以看出这个结构的arg和heap域都是指向struct pheap结构。这是很重要的一步，内存池主要是管理这个结构的。
注意这里的pool_cleanup_t是一个函数指针，在我们这里，它是_pool_heap_free.用于指示如何释放这个内存块，实现很简单，如下：
static void _pool_heap_free（void *arg）
{
struct pheap *h = （struct pheap *）arg;
free（h->block）；
free（h）；
}
这个释放函数就很简单了吧，下面继续我们话题。
前文说了内存池包含链表，管理内存块，那接下来的操作是不是要将这个内存块【struct pfree】加到链表上。看一下_pool_cleanup_append函数做哪些工作：
static void _pool_cleanup_append（pool_t p, struct pfree *pf）
{
struct pfree *cur;
if（p->cleanup == NULL）
{
p->cleanup = pf;
p->cleanup_tail = pf;
return;
}
cur = p->cleanup_tail;
cur->next = pf;
p->cleanup_tail = pf;
}
这个函数很简单，将struct pfree结构加到内存池的cleanup_tail链表的末尾，并将新的cleanup_tail指向刚加入的pfree结构。
到这里，就完成了内存从调用malloc分配至加入到内存池的过程，再回顾一下：
1、调用malloc分配内存块，并赋值给struct pheap结构。
2、将struct pheap结构封装成struct pfree结构，这样struct pheap结构就可以成为链表上的元素。
3、将struct pfree结构加入到struct pool_sturct结构【这是内存池的结构】的链表末尾。
六、内存池的释放
在内存池的使命结束后，我们需要释放内存池，不仅仅是struct pool_struct这个结构，还包括链表上的内存块。
void pool_free（pool_t p）
{
struct pfree *cur, *stub;
if（p == NULL） return;
cur = p->cleanup;
while（cur != NULL）
pfree结构。
看一下前面申请内存块之后，这时还只是一个pheap结构，没有和内存池关联起来，在前方我们看到，是通过下面代码进行关联的
clean = _pool_free（p, _pool_heap_free, （void *）ret）；
clean->heap = ret; /* for future use in finding used mem for pstrdup */
_pool_cleanup_append（p, clean）；
_pool_free为该内存块定义的一个结构进行初始化，如下调用
static struct pfree *_pool_free（pool_t p, pool_cleanup_t f, void *arg）
{
struct pfree *ret;
while（（ret = malloc（sizeof（struct pfree））） == NULL） sleep（1）；
ret->f = f;
ret->arg = arg;
ret->next = NULL;
return ret;
}
这个函数只是定义了一个sturct pfree结构，基本上是用struct pheap这个结构对其进行初始化的，可以看出这个结构的arg和heap域都是指向struct pheap结构。这是很重要的一步，内存池主要是管理这个结构的。
注意这里的pool_cleanup_t是一个函数指针，在我们这里，它是_pool_heap_free.用于指示如何释放这个内存块，实现很简单，如下：
static void _pool_heap_free（void *arg）
{
struct pheap *h = （struct pheap *）arg;
free（h->block）；
free（h）；
}
这个释放函数就很简单了吧，下面继续我们话题。
前文说了内存池包含链表，管理内存块，那接下来的操作是不是要将这个内存块【struct pfree】加到链表上。看一下_pool_cleanup_append函数做哪些工作：
static void _pool_cleanup_append（pool_t p, struct pfree *pf）
{
struct pfree *cur;
if（p->cleanup == NULL）
{
p->cleanup = pf;
p->cleanup_tail = pf;
return;
}
cur = p->cleanup_tail;
cur->next = pf;
p->cleanup_tail = pf;
}
这个函数很简单，将struct pfree结构加到内存池的cleanup_tail链表的末尾，并将新的cleanup_tail指向刚加入的pfree结构。
到这里，就完成了内存从调用malloc分配至加入到内存池的过程，再回顾一下：
1、调用malloc分配内存块，并赋值给struct pheap结构。
2、将struct pheap结构封装成struct pfree结构，这样struct pheap结构就可以成为链表上的元素。
3、将struct pfree结构加入到struct pool_sturct结构【这是内存池的结构】的链表末尾。
六、内存池的释放
在内存池的使命结束后，我们需要释放内存池，不仅仅是struct pool_struct这个结构，还包括链表上的内存块。
void pool_free（pool_t p）
{
struct pfree *cur, *stub;
if（p == NULL） return;
cur = p->cleanup;
while（cur != NULL）
{
（*cur->f）（cur->arg）； // 这会释放用malloc分配的内存块和struct pheap结构所占用的内存。这就是前文的_pool_heap_free函数
stub = cur->next;
free（cur）； // 释放pfree结构。
cur=NULL；
}
free（p）； //释放pool_struct结构所占用的内存。
}
（*cur->f）（cur->arg）； // 这会释放用malloc分配的内存块和struct pheap结构所占用的内存。这就是前文的_pool_heap_free函数
stub = cur->next;
free（cur）； // 释放pfree结构。
cur=NULL；
}
free（p）； //释放pool_struct结构所占用的内存。
}
七、从内存池分配内存
这个才是本文的重点，如何从内存池中分配一个没有被使用的内存，先看代码，表示从内存池中分配size大小的内存，这个机制也是本文的重点。
void *pool_malloc（pool_t p, int size）
{
void *block;
if（p == NULL）
{
fprintf（stderr,“Memory Leak! [pmalloc received NULL pool, unable to track allocation, exiting]\n”）；
abort（）；
}
if（p->heap == NULL || size > （p->heap->size / 2））
{
while（（block = malloc（size）） == NULL） sleep（1）；
p->size += size;
_pool_cleanup_append（p, _pool_free（p, _pool__free, block））；
return block;
}
if（size >= 4）
while（p->heap->used&7） p->heap->used++; // 这一步是个对齐操作，如果已经使用的不是8的倍数，就会跳过，直到为8的倍数。
if（size > （p->heap->size - p->heap->used））
p->heap = _pool_heap（p, p->heap->size）；
block = （char *）p->heap->block + p->heap->used;
p->heap->used += size; //已经使用部分增加，也会使得内存分配的偏移值指针增加。
return block;
}
从上面的代码中，可以看出分配内存的策略如下：
1、如果内存池中没有内存或者将要分配的内存比内存池中总的内存数一半还要大，会调用malloc向系统请求内存。并把分配的内存加入到内存池中。
2、已分配的内存按字对齐，如果没有对齐，就会跳过不对齐部分，不对齐的部分标识为已经使用。
3、如果链表最新的内存块内存剩余的大小不足于分配size字节，会重新请求新的内存块，并加入内存池。
4、从链表的最后内存块分配，p->heap->used,表示内存块中已经使用的一个偏移，从这里开始分配。
这个才是本文的重点，如何从内存池中分配一个没有被使用的内存，先看代码，表示从内存池中分配size大小的内存，这个机制也是本文的重点。
void *pool_malloc（pool_t p, int size）
{
void *block;
if（p == NULL）
{
fprintf（stderr,“Memory Leak! [pmalloc received NULL pool, unable to track allocation, exiting]\n”）；
abort（）；
}
if（p->heap == NULL || size > （p->heap->size / 2））
{
while（（block = malloc（size）） == NULL） sleep（1）；
p->size += size;
_pool_cleanup_append（p, _pool_free（p, _pool__free, block））；
return block;
}
if（size >= 4）
while（p->heap->used&7） p->heap->used++; // 这一步是个对齐操作，如果已经使用的不是8的倍数，就会跳过，直到为8的倍数。
if（size > （p->heap->size - p->heap->used））
p->heap = _pool_heap（p, p->heap->size）；
block = （char *）p->heap->block + p->heap->used;
p->heap->used += size; //已经使用部分增加，也会使得内存分配的偏移值指针增加。
return block;
}
从上面的代码中，可以看出分配内存的策略如下：
1、如果内存池中没有内存或者将要分配的内存比内存池中总的内存数一半还要大，会调用malloc向系统请求内存。并把分配的内存加入到内存池中。
2、已分配的内存按字对齐，如果没有对齐，就会跳过不对齐部分，不对齐的部分标识为已经使用。
3、如果链表最新的内存块内存剩余的大小不足于分配size字节，会重新请求新的内存块，并加入内存池。
4、从链表的最后内存块分配，p->heap->used,表示内存块中已经使用的一个偏移，从这里开始分配。