介绍：
设计内存池的目标是为了保证服务器长时间高效的运行，通过对申请空间小而申请频繁的对象进行有效管理，减少内存碎片的产生，合理分配管理用户内存，从而减少系统中出现有效空间足够，而无法分配大块连续内存的情况。
目标：
此次设计内存池的基本目标，需要满足线程安全性（多线程），适量的内存泄露越界检查，运行效率不太低于malloc/free方式，实现对4-128字节范围内的内存空间申请的内存池管理（非单一固定大小对象管理的内存池）。
内存池技术设计与实现
本内存池的设计方法主要参考SGI的alloc的设计方案，为了适合一般的应用，并在alloc的基础上做一些简单的修改。
Mempool的内存池设计方案如下（也可参考候捷《深入剖析STL》）
从系统申请大块heap内存，在此内存上划分不同大小的区块，并把具有相同大小的区块连接起来，组成一个链表。比如A大小的块，组成链表L，当申请A大小时，直接从链表L头部（如果不为空）上取到一块交给申请者，当释放A大小的块时，直接挂接到L的头部。内存池的原理比较简单，但是在具体实现过程中大量的细节需要注意。
1：字节对齐。
为了方便内存池中对象的管理，需要对申请内存空间的进行调整，在Mempool中，字节对齐的大小为最接近8倍数的字节数。比如，用户申请5个字节，Mempool首先会把它调整为8字节。比如申请22字节，会调整为24，对比关系如下
|
序号 |
对齐字节 |
范围 |
|
0 |
8 |
1-8 |
|
1 |
16 |
9-16 |
|
2 |
24 |
17-24 |
|
3 |
32 |
25-32 |
|
4 |
40 |
33-40 |
|
5 |
48 |
41-48 |
|
6 |
56 |
49-56 |
|
7 |
64 |
57-64 |
|
8 |
72 |
65-72 |
|
9 |
80 |
73-80 |
|
10 |
88 |
81-88 |
|
11 |
96 |
89-96 |
|
12 |
104 |
97-104 |
|
13 |
112 |
105-112 |
|
14 |
120 |
113-120 |
|
15 |
128 |
121-128 |
（图1）
对于超过128字节的申请，直接调用malloc函数申请内存空间。这里设计的内存池并不是对所有的对象进行内存管理，只是对申请内存空间小，而申请频繁的对象进行管理，对于超过128字节的对象申请，不予考虑。这个需要与实际项目结合，并不是固定不变的。实现对齐操作的函数如下
static size_t round_up(size_t size)
{
return (((size)+7) &~ 7);// 按8字节对齐
}
2：构建索引表
内存池中管理的对象都是固定大小，现在要管理0-128字节的范围内的对象申请空间，除了采用上面提到的字节对齐外，还需要变通一下，这就是建立索引表，做法如下；
static _obj* free_list[16];
创建一个包含16个_obj*指针的数组，关于_obj结构后面详细讲解。free_list[0]记录所有空闲空间为8字节的链表的首地址；free_list[1]对应16字节的链表，free_list[2]对应24字节的列表。free_list中的下标和字节链表对应关系参考图1中的“序号”和“对齐字节”之间的关系。这种关系，我们很容易用算法计算出来。如下
static size_t freelist_index(size_t size)
{
return (((size)+7)/7-1);// 按8字节对齐
}
所以，这样当用户申请空间A时，我们只是通过上面简单的转换，就可以跳转到包含A字节大小的空闲链表上,如下；
_obj** p = free_list[freelist_index(A)];
3:构建空闲链表
通过索引表，我们知道mempool中维持着16条空闲链表，这些空闲链表中管理的空闲对象大小分别为8，16，24，32，40…128。这些空闲链表链接起来的方式完全相同。一般情况下我们构建单链表时需要创建如下的一个结构体。
struct Obj
{
Obj *next;
Char* p;
Int iSize;
}
next指针指向下一个这样的结构，p指向真正可用空间,iSize用于只是可用空间的大小，在其他的一些内存池实现中，还有更复杂的结构体，比如还包括记录此结构体的上级结构体的指针，结构体中当前使用空间的变量等，当用户申请空间时，把此结构体添加的用户申请空间中去，比如用户申请12字节的空间，可以这样做
Obj *p = (Obj*)malloc(12+sizeof(Obj));
p->next = NULL;
p->p = (char*)p+sizeof(Obj);
p->iSize = 12;
但是，我们并没有采用这种方式，这种方式的一个缺点就是，用户申请小空间时，内存池加料太多了。比如用户申请12字节时，而真实情况是内存池向内存申请了12+ sizeof(Obj)=12+12=24字节的内存空间，这样浪费大量内存用在标记内存空间上去，并且也没有体现索引表的优势。Mempool采用的是union方式
union Obj
{
Obj *next;
char client_data[1];
}
这里除了把上面的struct修改为union，并把int iSize去掉，同时把char*p，修改为char client_data[1]，并没有做太多的修改。而优势也恰恰体现在这里。如果采用struct方式，我们需要维护两条链表，一条链表是，已分配内存空间链表，另一条是未分配（空闲）空间链表。而我们使用索引表和union结构体，只需要维护一条链表，即未分配空间链表。具体如下
索引表的作用有两条1：如上所说，维护16条空闲链表2：变相记录每条链表上空间的大小，比如下标为3的索引表内维持着是大小为24字节的空闲链表。这样我们通过索引表减少在结构体内记录p所指向空间大小的iSize变量。从而减少4个字节。
Union的特性是，结构内的变量是互斥存在的。再运行状态下，只是存在一种变量类型。所以在这里sizeof(Obj)的大小为4，难道这里我们也需要把这4字节也加到用户申请空间中去嘛？其实不是，如果这样，我们又抹杀了union的特性。
当我们构建空闲分配链表时，我们通过next指向下一个union结构体，这样我们不使用p指针。当把这个结构体分配出去时，我们直接返回client_data的地址，此时client_data正好指向申请空间的首字节。所以这样，我们就不用在用户申请空间上添加任何东西。
图2
Obj的连接方式如上所示，这样我们无需为用户申请空间添加任何内容。
4：记录申请空间字节数
如果采用面向对象方式，或者我们在释放内存池的空间时能够明确知道释放空间的大小，无需采用这种方式。
图3
在C语言中的free没有传递释放空间大小，而可以正确释放，在这里也是模仿这种方式，采用这种记录申请空间大小的方式去释放内存。用户申请空间+1操作将在字节对齐之前执行，找到合适空间后，把首字节改写为申请空间的大小，当然1个字节最多纪录256个数，如果项目需要，可以设置为short类型或者int类型，不过这样就需要占用用户比较大的空间。当释放内存空间时，首先读取这个字节，获取空间大小，进行释放。为了便于对大于128字节对象的大小进行合适的释放，同时也对大于128字节的内存申请，添加1字节记录大小。所以现在这里限制了用户内存申请空间不得大于255字节，不过现在已经满足项目要求。当然也可以修改为用short类型记录申请空间的大小。
// 申请
*(( unsigned char *)result) = (size_t)n;
unsigned char * pTemp = (unsigned char*)result;
++pTemp;
result = (_obj*)pTemp;
return result;
// 释放
unsigned char * pTemp = (unsigned char *)ptr;
--pTemp;
ptr = (void*)pTemp;
n = (size_t)(*( unsigned char *)ptr);
发表评论 
打印本文
推荐本文
加入收藏
返回顶部
关闭窗口
