STL 内存池实现

STL 里的内存池实现

内存池的目的是什么?

  1. 通过 new 表达式动态分配一个对象时,会调用 operator new 进行内存分配,这一步是直接和操作系统打交道的, 操作系统可能需要经过相对繁琐的过程才能将一块指向空闲内存的指针返回给用户, 所以这也是 new 比较耗时的一部分, 而第二步就是使用构造函数进行初始化。既然内存分配耗时, 那我们很容易想到的就是一次性分配一大块内存, 然后在用户需要的时候再划分其中一部分给用户, 这样的话, 一次分配, 多次使用, 自然而然提高了效率, 而用来管理这所谓的一大块内存的内存结构, 也就是今天我们要说的内存池。
  2. 内存池带来的另外一个好处在于,频繁地使用new将导致系统内存空间碎片化严重, 容易导致的后果就是很难找到一块连续的大块内存, 空间利用率低,而内存池是一次性分配一大块内存空间,就缓解了内存碎片的问题。

一、STL中的内存管理

当我们 new 一个对象时:

  1. 使用 operator new 申请了一块内存。
  2. 执行构造函数。
    在SGI中,这两步独立出了两个函数:allocate申请内存,construct调用构造函数。这两个函数分别在<stl_alloc.h><stl_construct.h>中。

二、第一级配置器

第一级配置器以 malloc(),free(),realloc()等C函数执行实际的内存配置、释放、重新配置等操作,并且能在内存需求不被满足的时候,调用一个指定的函数。

三、第二级配置器

第二级配置器维护着16个空闲链表(free list),各自管理大小分别为8、16、24、32、40、48、56、64、72、80、88、96、104、112、120、128 bytes的小内存块。
如果要分配的内存大于 128bytes,则移交给第一级配置器处理,直接用malloc。
如果要分配的内存小于 128bytes,则以内存池管理(memory pool),使用第二级配置器,找出适合的空闲链表, 从其上摘下一个节点将其头指针返回给用户,这就完成了对用户的内存分配。
释放过程则正好与分配相对应,如果用户分配的内存大于128bytes,直接用free,否则找出适当的空闲链表, 将指针所指的该段内存重新连接到空闲链表中(注意此时并不把内存返回给操作系统, 如此可以重复利用)。

1. 空闲链表(free list)的设计

空闲链表节点的设计十分巧妙,用了一个联合体既可以记录下一个空闲内存块(存在于空闲链表中)的地址,也可以给出分配给用户使用内存块的地址。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
template <bool threads, int inst>
class __default_alloc_template
{
private:
//将bytes上调至8的倍数
static size_t ROUND_UP(size_t bytes)
{
return (((bytes) + __ALIGN - 1) & ~(__ALIGN - 1));//等价于(bytes + 7) / 8
}
//空闲链表的节点构造
union obj
{
union obj * free_list_link;
char client_data[1];
};
private:
//16个空闲链表,初始化为0,即每个链表中都没有空闲内存块
static obj * volatile free_list[__NFREELISTS];
//根据申请内存块的大小找到相应空闲链表的下标
static size_t FREELIST_INDEX(size_t bytes)
{
return (((bytes) + __ALIGN - 1)/__ALIGN - 1);
}
......
}

2. 从空闲列表中取内存块

首先先要检查申请空间的大小,如果大于128字节就调用第一级配置器,小于128字节就检查对应的空闲链表,如果该空闲链表中有可用内存块,则直接拿来用(拿取空闲链表中的第一个可用内存块,然后把该空闲链表的地址设置为该内存块指向的下一个地址),如果没有可用内存块,则调用 refill 为该空闲链表填充新的空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//申请大小为 n 的内存块,返回该内存块的起始地址
static void * allocate(size_t n)
{
obj * __VOLATILE * my_free_list;
obj * __RESTRICT result;
if (n > (size_t) __MAX_BYTES)//大于128字节调用第一级配置器
{
return(malloc_alloc::allocate(n));
}
my_free_list = free_list + FREELIST_INDEX(n);//根据申请空间的大小寻找相应的空闲链表(16个空闲链表中的一个)
result = *my_free_list;
if (result == 0)//如果该空闲链表没有空闲的内存块
{
void *r = refill(ROUND_UP(n));//为该空闲链表填充新的空间
return r;
}
*my_free_list = result -> free_list_link;//如果空闲链表中有空闲内存块,则取出一个,并把空闲链表的指针指向下一个内存块
return (result);
};

3. 从内存池取空间,重新填充空闲链表

在用 allocate 配置空间时,如果空闲链表中没有可用内存块,就会调用refill来为该空闲链表填充新的空间,新的空间取自内存池。缺省取20个内存块,如果内存池空间不足,那么能取多少个节点就取多少个。
这里有两种情况会导致没有可用的内存块, 第一种是用光了, 第二种是这是该内存池初始化以来第一次使用这个大小的空闲链表, 所以还未为空闲链表分配过空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
template <bool threads, int inst>
void* refill(size_t n)
{
int nobjs = 20;
//从内存池里取出nobjs个大小为n的内存块,返回值nobjs为真实申请到的内存块个数,注意这里nobjs个大小为n的内存块所在的空间是连续的
char * chunk = chunk_alloc(n, nobjs);
obj * __VOLATILE * my_free_list;
obj * result;
obj * current_obj, * next_obj;
int i;
if (1 == nobjs) return(chunk);//如果只获得一个内存块,那么这个内存块就直接分给调用者,空闲链表中不会增加新节点
my_free_list = free_list + FREELIST_INDEX(n);//否则根据申请内存块的大小找到相应空闲链表
result = (obj *)chunk;
*my_free_list = next_obj = (obj *)(chunk + n);//第0个内存块给调用者,地址访问即chunk~chunk + n - 1
for (i = 1; ; i++)//1~nobjs-1的内存块插入到空闲链表
{
current_obj = next_obj;
next_obj = (obj *)((char *)next_obj + n);//由于之前内存池里申请到的空间连续,所以这里需要人工划分成小块一次插入到空闲链表
if (nobjs - 1 == i)
{
current_obj -> free_list_link = 0;
break;
}
else
{
current_obj -> free_list_link = next_obj;
}
}
return(result);
}

4. 从系统内存取空间给内存池

首先根据end_free-start_free来判断内存池中的剩余空间是否足以调出nobjs个大小为size的内存块出去,如果内存连一个内存块的空间都无法供应,需要用malloc取堆中申请内存。

申请内存后,如果要拨出去20个大小为8字节的内存块。

假如山穷水尽,整个系统的堆空间都不够用了,malloc失败,那么chunk_alloc会从空闲链表中找是否有大的内存块,然后将该内存块的空间分给内存池(这个内存块会从链表中去除)。即内存池强制回收空闲链表的内存空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
template <bool threads, int inst>
class __default_alloc_template
{
private:
......
static char *start_free;//内存池可用空间的起始位置,初始化为0
static char *end_free;//内存池可用空间的结束位置,初始化为0
static size_t heap_size;//内存池的总大小
public:
// 申请 nobjs 个大小为size的内存块,
// nobjs传进去的是引用,因为可能会出现内存池空间不够的情况,nobjs最终为最后真实申请到的内存块个数
static char *chunk_alloc(size_t size, int &nobjs)
{
char * result;
size_t total_bytes = size * nobjs;//需要申请空间的大小
size_t bytes_left = end_free - start_free;//计算内存池剩余空间
//如果内存池剩余空间完全满足需求量
if (bytes_left >= total_bytes)
{
result = start_free;
start_free += total_bytes;
return(result);
}
//内存池剩余空间不满足需求量,但是至少能够提供一个以上内存块
else if (bytes_left >= size)
{
nobjs = bytes_left / size;
total_bytes = size * nobjs;
result = start_free;
start_free += total_bytes;
return(result);
}
//剩余空间连一个内存块(大小为size)也无法提供
else
{
size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
//内存池的剩余空间分给合适的空闲链表
if (bytes_left > 0)
{
obj * __VOLATILE * my_free_list = free_list + FREELIST_INDEX(bytes_left);
((obj *)start_free) -> free_list_link = *my_free_list;
*my_free_list = (obj *)start_free;
}
start_free = (char *)malloc(bytes_to_get);//配置heap空间,用来补充内存池
if (0 == start_free)
{
int i;
obj * __VOLATILE * my_free_list, *p;
//从空闲链表中找出一个比较大的空闲内存块还给内存池(之后会将这个大的空闲内存块切成多个小的空闲内存块再次加入到空闲链表)
for (i = size; i <= __MAX_BYTES; i += __ALIGN)
{
my_free_list = free_list + FREELIST_INDEX(i);
p = *my_free_list;
if (0 != p)
{
*my_free_list = p -> free_list_link;
start_free = (char *)p;
end_free = start_free + i;
return(chunk_alloc(size, nobjs));//递归调用自己,为了修正nobjs
}
}
end_free = 0;
start_free = (char *)malloc_alloc::allocate(bytes_to_get);//如果连这个大的内存块都找不出来则调用第一级配置器
}
//如果分配成功
heap_size += bytes_to_get;//内存池大小增加
end_free = start_free + bytes_to_get;//修改内存池可用空间的结束位置
return(chunk_alloc(size, nobjs));//递归调用自己,为了修正nobjs
}
}
};

5. 空间释放函数deallocate

首先先要检查释放内存块的大小,如果大于128字节就调用第一级配置器,小于128字节则根据内存块的大小来判断回收后的空间会被插入到哪个空闲链表。
例如回收下面指定位置大小为16字节的内存块,首先内存块的大小判断回收后的内存块应该插入到第二个空闲链表,把该节点指向的下一个地址修改为原链表指向的地址(这里是NULL),然后将原链表指向该节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//释放地址为p,释放大小为n
static void deallocate(void *p, size_t n)
{
obj *q = (obj *)p;
obj * __VOLATILE * my_free_list;
if (n > (size_t) __MAX_BYTES)//如果空间大于128字节,采用普通的方法析构
{
malloc_alloc::deallocate(p, n);
return;
}
my_free_list = free_list + FREELIST_INDEX(n);//否则将空间回收到相应空闲链表(由释放块的大小决定)中
q -> free_list_link = *my_free_list;
*my_free_list = q;
}

流程总结

  1. 使用 allocate 请求size大小的内存空间, 如果需要请求的内存大小大于128bytes, 直接使用malloc.
  2. 如果需要的内存大小小于128bytes, allocate根据size找到最适合的空闲链表.
     a. 如果链表不为空, 返回第一个内存块, 链表头改为第二个内存块。
     b. 如果链表为空, 使用refill为该空闲链表填充新的空间。
      x. 如果内存池中有大于一个内存块的空间, 分配尽可能多的内存块(但是最多20个), 将一个内存块返回, 其他的内存块添加到链表中。
      y. 如果内存池只有一个内存块的空间, 直接返回给用户.
      z. 如果内存池连一个内存块的空间都没有, 再次向操作系统请求分配内存.
       I 系统内存足够,分配成功,再次进行b过程
       II 分配失败, 循环各个空闲链表, 寻找空间
        A. 找到空间, 再次进行过程b
        B. 找不到空间, 抛出异常
  3. 用户调用deallocate释放内存空间, 如果要求释放的内存空间大于128bytes, 直接调用free。
  4. 否则按照其大小找到合适的空闲链表, 并将其插入。

特点其实是这样的:

  1. 刚开始初始化内存池的时候, 其实内存池中并没有内存, 同时所有的空闲链表都为空链表.
  2. 只有用户第一次向内存池请求内存时, 内存池会依次执行上述过程的 1->2->b->z来完成内存池以及链表的首次填充, 而此时, 其他未使用链表仍然是空的.