STL空间配置器剖析学习

关于STL的学习,选择从侯捷的《STL源码剖析》开始,认真研究,提高自己代码水平。

之所以选择空间配置器来作为第一个入手学习的方面的原因,就是因为空间配置器太关键,一直默默无闻的在其他容器后提供支持,这种做“地基”的东西正是自己学习生活中需要进行理解的。

在书中,作者给出的定语是“具备次配置能力的SGI空间配置器”,为什么这样说呢,研究研究源码不就知道了嘛:laughing:。

已经知道,SGI STL的配置器的写法是vector<int,std::alloc> iv,而不是标准写法vector<int,std::allocator<int>> iv。而且在SGI STL中每个容器都缺省的指定其空间配置器为alloc,如在vector的声明中就有template <class T,class Alloc = alloc>

在学习alloc之前,提一下,SGI中还有一个标准的空间配置器std::allocator。包含在头文件defalloc.h中,SGI并没有使用过它,并且不建议我们使用,只是把::operator new 与::operaotr delete包装了一下而已。而重点要学习的是std::alloc这个特殊空间配置器。

SGI特殊空间配置器

先来看一下C++中内存配置操作和释放的通常操作:

1
2
3
class Foo {...}
Foo* pf = new Foo; //分配内存,构造对象
delete pf; //析构对象,释放内存

就像注释的那样,在new时先进行的是内存的分配,再调用构造函数构造对象。而delete时同样,就有了对应的析构与释放。所以,作为一个空间配置器,以上四个基本操作必须要进行。

在alloc中,alloc::allocate和alloc::deallocate分别对应内存的分配与释放,对于对象则有::construct()与::destroy(),所以在定义配置器的\中,包含有\与\两个头文件,所以有下图\结构:

memory

construct&&destory

PS:源码剖析这本书中的示意图都很清晰所以就拿来直接用了,下图是construct()与destroy()的示意图,参考代码更方便。

construct

部分源码剖析如下:

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
#include <new.h> //使用placement new(创建对象,分配到已有内存上不重新分配,适用于反复创建并删除的对象)
//construct()..
//接收两个类型
template <class _T1, class _T2>
inline void _Construct(_T1* __p, const _T2& __value) {
new ((void*) __p) _T1(__value); //placement new
}
//接收一个类型
template <class _T1>
inline void _Construct(_T1* __p) {
new ((void*) __p) _T1();
}
//destroy()..
//接受一个指针的destroy(),调用~T()
template <class _Tp>
inline void _Destroy(_Tp* __pointer) {
__pointer->~_Tp();
}
//接收两个迭代器的destroy(),并且通过_type_traits<>判断析构函数类型
template <class _ForwardIterator>
inline void _Destroy(_ForwardIterator __first, _ForwardIterator __last) {
__destroy(__first, __last, __VALUE_TYPE(__first));
}
//value_type是否有_trival_destructor
template <class _ForwardIterator, class _Tp>
inline void
__destroy(_ForwardIterator __first, _ForwardIterator __last, _Tp*)
{
typedef typename __type_traits<_Tp>::has_trivial_destructor
_Trivial_destructor;
__destroy_aux(__first, __last, _Trivial_destructor());
}
//没有_trival_destructor
template <class _ForwardIterator>
void
__destroy_aux(_ForwardIterator __first, _ForwardIterator __last, __false_type)
{
for ( ; __first != __last; ++__first)
destroy(&*__first);
}
//有_trival_destructor
template <class _ForwardIterator>
inline void __destroy_aux(_ForwardIterator, _ForwardIterator, __true_type) {}
//特化
inline void _Destroy(char*, char*) {}
inline void _Destroy(int*, int*) {}
inline void _Destroy(long*, long*) {}
inline void _Destroy(float*, float*) {}
inline void _Destroy(double*, double*) {}
#ifdef __STL_HAS_WCHAR_T
inline void _Destroy(wchar_t*, wchar_t*) {}
#endif

由上,construct()接受一个指针和一个初值,就是讲初值设定到指定的空间上。

而destroy就有点绕了,第一种是只接受一个指针的,直接调用该对象的析构函数。第二种接受的是两个迭代器frist和last,将范围内的所有对象析构掉。由于范围不确定,所以有两种情况,范围很大,那么相对于来说,每个对象的析构就会“无关痛痒”(_trival_destructor),就不用每个对象都调用析构;所以value_type获取的是对象的类别,再利用_type_traits\判断其析构,如果是就什么都不做,不是则就循环调用析构(第一个版本的destroy)。

std::alloc

理解源码剖析作者指出alloc的配置释放要遵从的设计理念,对理解alloc有很大帮助:

  • 向system heap要求空间
  • 考虑多线程状态
  • 考虑内存不足的应变措施
  • 考虑过多“小型区块”可能造成的内存碎片问题。

也因为时间有限,在这篇剖析中不会讨论多线程的问题。。

关于这个双层级配置器,第一层直接使用的是malloc与free,而第二层则是根据要分配的区块大小来决定分配策略,要分配的区块大于128b时调用第一层配置器。小于128b时采用memorypool

见下图:

alloc

PS:alloc并不接受任何template型别参数。

一级空间配置器

第一级配置器内存分配失败一般是由于内存不足out-of-memory(oom),处理异常时,首先用户自己设计异常处理例程,若用户没有定义,仅仅是打印错误信息并强制退出。总的来说,就是留给用户异常处理接口和默认强制退出处理。

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#ifndef __THROW_BAD_ALLOC
# if defined(__STL_NO_BAD_ALLOC) || !defined(__STL_USE_EXCEPTIONS)
# include <stdio.h>
# include <stdlib.h>
# define __THROW_BAD_ALLOC fprintf(stderr, "out of memory\n"); exit(1)
# else /* Standard conforming out-of-memory handling */
# include <new>
# define __THROW_BAD_ALLOC throw std::bad_alloc()
# endif
#endif
template <int __inst>
class __malloc_alloc_template {
private:
//以下三个函数用来处理oom的情况
static void* _S_oom_malloc(size_t);
static void* _S_oom_realloc(void*, size_t);
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
static void (* __malloc_alloc_oom_handler)();
#endif
public:
static void* allocate(size_t __n)
{
//直接malloc
void* __result = malloc(__n);
if (0 == __result) __result = _S_oom_malloc(__n);//oom
return __result;
}
static void deallocate(void* __p, size_t /* __n */)
{
free(__p); //直接free
}
static void* reallocate(void* __p, size_t /* old_sz */, size_t __new_sz)
{
void* __result = realloc(__p, __new_sz); //relloc
if (0 == __result) __result = _S_oom_realloc(__p, __new_sz); //oom
return __result;
}
//指定自己的异常处理
static void (* __set_malloc_handler(void (*__f)()))()
{
void (* __old)() = __malloc_alloc_oom_handler;
__malloc_alloc_oom_handler = __f;
return(__old);
}
};
// malloc_alloc out-of-memory handling
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
template <int __inst>
//初值为0
void (* __malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0;
#endif
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;
if (0 == __my_malloc_handler) { __THROW_BAD_ALLOC; }
(*__my_malloc_handler)();//调用处理程序,尝试释放内存
__result = malloc(__n);//尝试申请
if (__result) 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);
}
}
typedef __malloc_alloc_template<0> malloc_alloc;

以上,可以看出,在调用malloc与realloc不成功后,该调用的oom相应处理都是在不断地调用异常处理,希望的是在调用后,有内存可以去申请成功。如果异常处理没有被设定,那么直接throw异常。

二级空间配置器

看源码之前先看一下其维护的16个自由链表。

1
2
3
4
union obj{
union obj *free_list_link;
char client_data[1];
};

其中利用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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
template <bool threads, int inst>
class __default_alloc_template {
private:
// Really we should use static const int x = N
// instead of enum { x = N }, but few compilers accept the former.
#if ! (defined(__SUNPRO_CC) || defined(__GNUC__))
enum {_ALIGN = 8}; //小型区块上调边界
enum {_MAX_BYTES = 128}; //小型区块的上限
enum {_NFREELISTS = 16}; // 自由链表个数
# endif
//为了方便管理,直接将小区块的b调为8的倍数
static size_t _S_round_up(size_t __bytes)
{ return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); }
__PRIVATE:
//自由链表
union _Obj {
union _Obj* _M_free_list_link;
char _M_client_data[1]; /* The client sees this. */
};
private:
# if defined(__SUNPRO_CC) || defined(__GNUC__) || defined(__HP_aCC)
static _Obj* __STL_VOLATILE _S_free_list[];
// Specifying a size results in duplicate def for 4.1
# else
static _Obj* __STL_VOLATILE _S_free_list[_NFREELISTS]; //链表
# endif
//根据区块大小,决定使用几号自由链表
static size_t _S_freelist_index(size_t __bytes) {
return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);
}
// Returns an object of size __n, and optionally adds to size __n free list.
//填充空间,把大小为n的内存空间加到自由链表
static void* _S_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.
//从内存池中分配空间,该空间可容纳__nobjs大小为__size的区块,可能会少于__nobjs个
static char* _S_chunk_alloc(size_t __size, int& __nobjs);
// Chunk allocation state.
static char* _S_start_free;//内存池起始位置,只在chunk_alloc中变化
static char* _S_end_free;//内存池结束位置,只在chunk_alloc中变化
static size_t _S_heap_size;
# ifdef __STL_THREADS
static _STL_mutex_lock _S_node_allocator_lock;
# endif
// It would be nice to use _STL_auto_lock here. But we
// don't need the NULL check. And we do need a test whether
// threads have actually been started.
class _Lock;
friend class _Lock;
class _Lock {
public:
_Lock() { __NODE_ALLOCATOR_LOCK; }
~_Lock() { __NODE_ALLOCATOR_UNLOCK; }
};
public:
/* __n must be > 0 */
static void* allocate(size_t __n)
{
void* __ret = 0;
if (__n > (size_t) _MAX_BYTES) {
__ret = malloc_alloc::allocate(__n);
}
else {
_Obj* __STL_VOLATILE* __my_free_list
= _S_free_list + _S_freelist_index(__n);
// Acquire the lock here with a constructor call.
// This ensures that it is released in exit or during stack
// unwinding.
# ifndef _NOTHREADS
/*REFERENCED*/
_Lock __lock_instance;
# endif
_Obj* __RESTRICT __result = *__my_free_list;
if (__result == 0)
__ret = _S_refill(_S_round_up(__n));
else {
*__my_free_list = __result -> _M_free_list_link;
__ret = __result;
}
}
return __ret;
};
/* __p may not be 0 */
static void deallocate(void* __p, size_t __n)
{
if (__n > (size_t) _MAX_BYTES)
malloc_alloc::deallocate(__p, __n);
else {
_Obj* __STL_VOLATILE* __my_free_list
= _S_free_list + _S_freelist_index(__n);
_Obj* __q = (_Obj*)__p;
// acquire lock
# ifndef _NOTHREADS
/*REFERENCED*/
_Lock __lock_instance;
# endif /* _NOTHREADS */
__q -> _M_free_list_link = *__my_free_list;
*__my_free_list = __q;
// lock is released here
}
}
static void* reallocate(void* __p, size_t __old_sz, size_t __new_sz);
} ;
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
typedef __default_alloc_template<false, 0> single_client_alloc;
template <bool __threads, int __inst>
inline bool operator==(const __default_alloc_template<__threads, __inst>&,
const __default_alloc_template<__threads, __inst>&)
{
return true;
}
# ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
template <bool __threads, int __inst>
inline bool operator!=(const __default_alloc_template<__threads, __inst>&,
const __default_alloc_template<__threads, __inst>&)
{
return false;
}
# endif

在第二层配置器中,每当配置一大块内存,就维护对应的自由链表。下一次是相同大小的内存请求,就直接使用这个就行。又由于自由链表还负责回收小额的区块,所以为了方便管理,所有小额的区块都被分配8的倍数的大小。

allocate&&deallocate

看图:

allocate

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
//找到对应编号的节点
static size_t _S_freelist_index(size_t __bytes) {
return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);
}
//将申请的空间大小变为8的倍数
static size_t _S_round_up(size_t __bytes)
{ return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); }
static void* allocate(size_t __n)
{
void* __ret = 0;
//大于128调用第一级
if (__n > (size_t) _MAX_BYTES) {
__ret = malloc_alloc::allocate(__n);
}
else {
//1.开始找,找到对应节点
_Obj* __STL_VOLATILE* __my_free_list
= _S_free_list + _S_freelist_index(__n);
// Acquire the lock here with a constructor call.
// This ensures that it is released in exit or during stack
// unwinding.
# ifndef _NOTHREADS
/*REFERENCED*/
_Lock __lock_instance;
# endif
_Obj* __RESTRICT __result = *__my_free_list; //2
if (__result == 0)//没找到,就refill,即现在对应节点上没有可以用的空间
__ret = _S_refill(_S_round_up(__n));
else {
//3.调整链表
*__my_free_list = __result -> _M_free_list_link;
__ret = __result;
}
}
return __ret;
}
//deallocate的示意图见下图
static void deallocate(void* __p, size_t __n)
{
//大于128
if (__n > (size_t) _MAX_BYTES)
malloc_alloc::deallocate(__p, __n);
else {
//寻找对应的链表
_Obj* __STL_VOLATILE* __my_free_list
= _S_free_list + _S_freelist_index(__n);//2.
_Obj* __q = (_Obj*)__p;//1.
// acquire lock
# ifndef _NOTHREADS
/*REFERENCED*/
_Lock __lock_instance;
# endif /* _NOTHREADS */
//3.调整进行回收
__q -> _M_free_list_link = *__my_free_list;
*__my_free_list = __q;//4.
// lock is released here
}
}

deallocate

refill

当allocate()发现链表中没有可用区块时,调用refill,重新填充freelist。

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
template <bool __threads, int __inst>
void*
__default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
{
int __nobjs = 20;
//调用chunk_alloc尝试取得nobjs个区块。
char* __chunk = _S_chunk_alloc(__n, __nobjs);
_Obj* __STL_VOLATILE* __my_free_list;
_Obj* __result;
_Obj* __current_obj;
_Obj* __next_obj;
int __i;
//只获得了一个区块,分配给调用者,freelist并没有得到新节点
if (1 == __nobjs) return(__chunk);
//不是一个,分配给链表
__my_free_list = _S_free_list + _S_freelist_index(__n);
/* Build free list in chunk */
__result = (_Obj*)__chunk;
*__my_free_list = __next_obj = (_Obj*)(__chunk + __n);//指向新分配的空间
//将链表各节点串起来
for (__i = 1; ; __i++) {
__current_obj = __next_obj;
__next_obj = (_Obj*)((char*)__next_obj + __n);
if (__nobjs - 1 == __i) {
__current_obj -> _M_free_list_link = 0;
break;
} else {
__current_obj -> _M_free_list_link = __next_obj;
}
}
return(__result);
}

chunk_alloc

下面主要分析的是chunk_alloc这个函数,从上面的allocate和refill已经可以知道,在SGISTL中对于空间配置器来说,申请的空间资源如果大于128b则就去第一级配置器,小于128则就是第二级配置器,由维护有对应从8~128b的16个自由链表节点进行分配。如果在调用第二级配置器时链表维护的相应节点上的空间不够时就refill,然后利用chunk_alloc来获取预先设定好的一定大小和数目的区块。

所以,我个人认为chunk_alloc可以说是整个配置器技巧体现的淋漓尽致。

  • 首先,如果可以申请到需要的区块则万事大吉,
  • 如果不够,则是能申请多少就申请多少,
  • 如果只能满足一个,那也就申请一个。
  • 如果连一个都满足不了,先把内存池里的剩余零头给freelist,在扩大内存池空间,成功了就申请指定的,或者判断情况(又满足递归子条件,所以可以返回第一步进行判断调整nobjs),
  • 如果不成功,则检查freelist上维护的空间有没有被释放的,有就立马拿过来,再递归修正nobjs。
  • 如果还没有,那就调用第一级配置器,开始尝试用oom_allocate,如果还是没有那就会调用BAD_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
77
/* We allocate memory in large chunks in order to avoid fragmenting */
/* the malloc heap too much. */
/* We assume that size is properly aligned. */
/* We hold the allocation lock. */
template <bool __threads, int __inst>
char*
__default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size,
int& __nobjs)
{
char* __result;
size_t __total_bytes = __size * __nobjs;//节点个数
size_t __bytes_left = _S_end_free - _S_start_free;//内存池剩余空间
//内存池剩余量可以满足需求
if (__bytes_left >= __total_bytes) {
__result = _S_start_free;
_S_start_free += __total_bytes;
return(__result);
}
//不能满足需求,但可以提供1个区块以上,更新nobjs,返回申请到的区块
else if (__bytes_left >= __size) {
__nobjs = (int)(__bytes_left/__size);//更新了nobjs
__total_bytes = __size * __nobjs;
__result = _S_start_free;
_S_start_free += __total_bytes;
return(__result);
}
//连一个都申请不到
else {
size_t __bytes_to_get =
2 * __total_bytes + _S_round_up(_S_heap_size >> 4);//记录下要申请的总大小,如果成功,就申请这么大
// Try to make use of the left-over piece.
//内存池中还有些可以利用的,直接拿过来
if (__bytes_left > 0) {
_Obj* __STL_VOLATILE* __my_free_list =
_S_free_list + _S_freelist_index(__bytes_left);
((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;
*__my_free_list = (_Obj*)_S_start_free;
}
//尝试扩大内存池到总需求大小
_S_start_free = (char*)malloc(__bytes_to_get);
//尝试失败
if (0 == _S_start_free) {
size_t __i;
_Obj* __STL_VOLATILE* __my_free_list;
_Obj* __p;
// Try to make do with what we have. That can't
// hurt. We do not try smaller requests, since that tends
// to result in disaster on multi-process machines.
//上面自带的注释解释的很棒,“尽我们所能,不再尝试配置小区块”
for (__i = __size;
__i <= (size_t) _MAX_BYTES;
__i += (size_t) _ALIGN) {
__my_free_list = _S_free_list + _S_freelist_index(__i);
__p = *__my_free_list;
if (0 != __p) {//freelist有可用的
*__my_free_list = __p -> _M_free_list_link;
_S_start_free = (char*)__p;
_S_end_free = _S_start_free + __i;
return(_S_chunk_alloc(__size, __nobjs));
// Any leftover piece will eventually make it to the
// right free list.
}
}
//上面的尝试失败啦。。调用一级配置器再试试
_S_end_free = 0; // In case of exception.
_S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);
// This should either throw an
// exception or remedy the situation. Thus we assume it
// succeeded.
}
//成功申请到了,调整内存池大小
_S_heap_size += __bytes_to_get;
_S_end_free = _S_start_free + __bytes_to_get;
return(_S_chunk_alloc(__size, __nobjs));//调整nobjs(区块个数)
}
}