STL源码剖析笔记<二> 空间配置器

STL源码剖析笔记<二> 空间配置器

1. allocator类

有时候我们需要把内存分配和对象构造分离开来,使用allocator就可以达到这个目的。

当一个allocator对象分配内存时候,就会根据给定的对象类型来确定恰当的内存大小和对齐位置。

1
2
allocator<string> alloc;//用以分配string对象的allocator对象
auto const p=alloc.allocate(n);//分配n个未初始化的对象的内存

STL中allocator类及算法

算法 功能
allocator<T> a 定义一个allocator对象
a.allocate(n) 分配n个未初始化的对象的内存
a.deallocate(p,n) 释放从T*指针p开始的内存,这个指针需要是allocate返回的
a.construct(p,args) p为类型为T*的指针,args是传递给构造函数的参数
a.destroy(p) 对p指向的对象执行析构函数

allocator类还有几个伴随算法,可以在未初始化的内存中创建对象

算法 功能
uninitialized_copy(b,e,b2) 迭代器b到e范围的元素拷贝到b2指向的未构造的原始内存中
uninitialized_copy_n(b,n,b2) 从迭代器B开始的内存中拷贝n个元素到b2开始的地方
uninitialized_fill(b,e,t) 从迭代器b到e范围创建对象,对象为t的拷贝
uninitialized_fill_n(b,n,t) 从迭代器B开始的内存创建n个元素t的拷贝

2.使用new及delete的一些问题

以前我们说过,用户自己是向堆上申请内存,用后自己维护,在实践中,我们不免会因为各种需求。使用很多小块内存。这些内存的动态申请,释放会出现一些问题

  • 出现内存碎片的问题
  • 许多小块内存的存在时候,调用malloc,系统可能会产生性能问题

内碎片,由于内存对齐或者效率产生的问题,例如用户需要三字节,实际会分配4字节(32位)或8字节(64位),其中的内存碎片是浪费掉的。这种碎片又叫内碎片。
外碎片,系统内存总量是足够的,但是不连续,所以无法分配给用户而产生的浪费,见下图

外碎片

由于这两个问题的存在,我们就可以分析STL中空间配置器的具体实现了

3. STL中空间配置器的具体实现

在SGI STL中实现的空间配置器采用两级配置:

  • 第一级配置器处理大于128bytes的内存申请
  • 第二级配置器使用内存池技术处理小于128bytes的内存申请

一级空间配置器直接封装malloc,free进行处理,增加了C++中的set_handler机制(这里其实也就是个略显牵强的装饰/适配模式了),增加内存分配时客户端可选处理机制。二级空间配置由内存池以及伙伴系统:自由链表组成。

二级空间配置器

客户端可以通过宏 __USE_MALLOC进行选择是否使用二级空间配置器

1
2
3
4
5
6
7
8
9
10
# ifdef __USE_MALLOC
...
/*__malloc_alloc_template 就是第一级配置器*/
typedef __malloc_alloc_template<0> malloc_alloc;
typedef malloc_alloc alloc;
#else
...
/*__default_alloc_template 就是第二级配置器*/
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
#endif

最后都定位于 alloc,因为通常我们使用缺省的空间配置器,而SGI的每个容器都已经指定其缺省的空间配置器 alloc。无论 alloc 被定义为第一级或第二级配置器,SGI还为它再封装一个接口如下,使配置器的接口能够符合STL规格:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template<class _Tp, class _Alloc>
class simple_alloc {
public:
static _Tp* allocate(size_t __n)
{
return 0 == __n ? 0 : (_Tp*)_Alloc::allocate(__n * sizeof (_Tp));
}
static _Tp* allocate(void)
{
return (_Tp*)_Alloc::allocate(sizeof (_Tp));
}
static void deallocate(_Tp* __p, size_t __n)
{
if (0 != __n) _Alloc::deallocate(__p, __n * sizeof (_Tp));
}
static void deallocate(_Tp* __p)
{
_Alloc::deallocate(__p, sizeof (_Tp));
}
};

这内部四个成员函数其实都是单纯的转调用,调用传递给配置器的成员函数。SGI容器全部使用这个simple_alloc接口。

###3.1 实现第一级配置器__malloc_alloc_template

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
#define __THROW_BAD_ALLOC fprintf(stderr, "out of memory\n"); exit(1)
static void* allocate(size_t __n)
{
void* __result = malloc(__n); //调用malloc()分配内存,向 system heap 要求空间
if (0 == __result) __result = _S_oom_malloc(__n); //malloc分配失败,调用_S_oom_malloc()
return __result; //oom means "out of memory"
}
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
template <int __inst>
void(*__malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0;
#endif
//内存不足处理例程,初值为0,待用户自定义,考虑内存不足时的应变措施。
template <int __inst>
void*
__malloc_alloc_template<__inst>::_S_oom_malloc(size_t __n)
{
void(*__my_malloc_handler)(); //函数指针
void* __result;
for (;;) { //不断的尝试释放、配置、再释放、再配置……
__my_malloc_handler = __malloc_alloc_oom_handler;
/*由于初值设定为0,如果用户没有自定义相应的内存不足处理例程,那么还是抛出异常*/
if (0 == __my_malloc_handler) { __THROW_BAD_ALLOC; }
(*__my_malloc_handler)(); //用户有自定义(释放内存),则进入相应的处理程序
__result = malloc(__n);
if (__result) return(__result);
}
//不断的尝试释放和配置是因为用户不知道还需要释放多少内存来满足分配需求,只能逐步的释放配置
}

上面并非死循环,它有两个退出条件:1.用户没有定义相应的内存不足处理例程,即没有通过释放内存来解决现有内存分配不足的问题,结果抛出异常,直接退出(宏定义);2.在用户定义了释放内存程序例程后,成功分配指定大小内存,返回指向该内存区域的首地址。

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
//reallocate的实现
static void* reallocate(void* __p, size_t /* old_sz */, size_t __new_sz)
{
void* __result = realloc(__p, __new_sz);
if (0 == __result) __result = _S_oom_realloc(__p, __new_sz);
return __result;
}
template <int __inst>
void* __malloc_alloc_template<__inst>::_S_oom_realloc(void* __p, size_t __n)
{
void (* __my_malloc_handler)();
void* __result;
for (;;) {
__my_malloc_handler = __malloc_alloc_oom_handler;
if (0 == __my_malloc_handler) { __THROW_BAD_ALLOC; }
(*__my_malloc_handler)();
__result = realloc(__p, __n);
if (__result) return(__result);
}
}
//第一级空间配置器的释放就简单了
static void deallocate(void* __p, size_t /* __n */)
{
free(__p); //第一级配置器直接使用free()
}

SGI 第一级配置器的 allocate() 和 reallocate() 都是在调用 malloc() 和 realloc() 不成功后,改调用 _S_oom_malloc() 和 _S_oom_realloc()。后两者都有内循环,不断调用 “内存不足处理例程”,期望在某次调用之后,可以获得足够的内存来完成所需求的内存分配,如果 “内存不足处理例程” 并未被客端设定,_S_oom_malloc() 和 _S_oom_realloc() 便会调用 __THROW_BAD_ALLOC,丢出 bad_alloc 异常信息,而后直接利用 exit(1) 中止程序。

所以可以看出,设计 “内存不足处理例程” 是客端的责任,设定 “内存不足处理例程” 也是客端的责任。也就是说 SGI STL 不为你设定。

3.2 实现第二级空间配置器

在第二级配置器中,小额区块内存需求大小都被上调至8的倍数,比如需要分配的大小是30bytes,就自动调整为32bytes。系统中总共维护16个free-lists,各自管理大小为8,16,…,128bytes的小额区块。
为了维护链表,需要额外的指针,为了避免造成另外一种额外的负担,这里采用了一种技术:用union表示链表节点结构:

1
2
3
4
union obj {
union obj * free_list_link;//指向下一个节点
char client_data[1]; /* The client sees this. */
};

union能够实现一物二用的效果,当节点所指的内存块是空闲块时,obj被视为一个指针,指向另一个节点。当节点已被分配时,被视为一个指针,指向实际区块。

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
template <bool threads, int inst>
class __default_alloc_template {
private:
# ifndef __SUNPRO_CC
enum {__ALIGN = 8};
enum {__MAX_BYTES = 128};
enum {__NFREELISTS = __MAX_BYTES/__ALIGN};
# endif
static size_t ROUND_UP(size_t bytes) {
return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1));
}
__PRIVATE:
union obj {
union obj * free_list_link;
char client_data[1]; /* The client sees this. */
};
private:
# ifdef __SUNPRO_CC
static obj * __VOLATILE free_list[];
// Specifying a size results in duplicate def for 4.1
# else
static obj * __VOLATILE free_list[__NFREELISTS];
# endif
static size_t FREELIST_INDEX(size_t bytes) {
return (((bytes) + __ALIGN-1)/__ALIGN - 1);
}
// Returns an object of size n, and optionally adds to size n free list.
static void *refill(size_t n);
// Allocates a chunk for nobjs of size "size". nobjs may be reduced
// if it is inconvenient to allocate the requested number.
static char *chunk_alloc(size_t size, int &nobjs);
// Chunk allocation state.
static char *start_free;
static char *end_free;
static size_t heap_size;
/* n must be > 0 */
static void * allocate(size_t n){...}
/* p may not be 0 */
static void deallocate(void *p, size_t n){...}
static void * reallocate(void *p, size_t old_sz, size_t new_sz);
template <bool threads, int inst>
char *__default_alloc_template<threads, inst>::start_free = 0;//内存池起始位置
template <bool threads, int inst>
char *__default_alloc_template<threads, inst>::end_free = 0;//内存池结束位置
template <bool threads, int inst>
size_t __default_alloc_template<threads, inst>::heap_size = 0;
template <bool threads, int inst>
__default_alloc_template<threads, inst>::obj * __VOLATILE
__default_alloc_template<threads, inst> ::free_list[
# ifdef __SUNPRO_CC
__NFREELISTS
# else
__default_alloc_template<threads, inst>::__NFREELISTS
# endif
] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };

二级配置器分配内存时,自由链表变化示意图

二级空间配置1

二级配置器释放内存时,自由链表变化示意图:

二级空间配置2

第二级配置器分配内存时,其具体步骤如下:

1).判断内存块大小,是否大于128bytes,若大于,则调用第一级配置器.若小于,进行步骤2).

2).从16个自由链表中,根据内存块大小选择合适的自由链表.

3).判断自由链表是否为空,若为空,则重新真充自由链表,否则,进行步骤4).

4).调整当前自由链表指向一块内存块,并返回当前的内存块.(类似于链表的删除操作)

第二级配置器释放内存时,其具体步骤如下:

1).判断内存块大小,是否大于128bytes,若大于,则调用第一级配置器.若小于,进行步骤2).

2).从16个自由链表中,根据内存块大小选择合适的自由链表.

3).调整当前自由链表回收当前的内存块.(类似于链表的插入操作)

内存池

内存池管理:

1).三个变量来标识内存池的使用情况和大小,start_free,end_free,heap_size.

2).从内存池中取空间给自由链表时,主要分三种情况进行.

a).内存池剩余空间完全满足需求量,则直接修改start_free的值,返回对应的区块.

b).内存池剩余空间不能完全满足需求量,但足够供应一个(含)以上的区块,则减少分配的区块数目,然后分配.

c).内存池剩余空间连一个区块的大小都无法提供,则利用malloc增加内存空间.

若malloc成功,则修改start_free,end_free,heap_size,然后递归调用自身,重新分配区块.

若malloc不成功,则寻找自由链表中,看是否存在足够大的区块.

若存在,则将对应区块作为内存池,调整start_free,end_free,递归调用自身,重新分配区块.

若不存,则调用第一级配置器.

my_free_list始终指向的是没使用的内存块,所以即使重新填充也是指向重填充的内存块