残局

不过在等杀死希望的最后一刀

0%

STL源码-分配器

发表于 更新于
本文字数： 13k 阅读时长 ≈ 12 分钟

本文是阅读SGI STL源码中关于allocator部分的笔记

同样，本文仍然是建立在已经观看过侯捷老师STL源码剖析课程的基础上。是在阅读源码过程中，对其中的内容进行补充、修饰。

Allocator

从实现的角度来看，配置器是一个实现了动态空间配置、空间管理、空间释放的 class template。

defalloc.h

标准的空间分配器。只是实现了基层的分配、释放行为（operator new 和 operator delete封装），并没有进行优化

allocate/deallocate

基础的分配、释放函数，只是简单的封装了一下operator new 和 operator delete。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <class T>
inline T* allocate(ptrdiff_t size, T*) {
    set_new_handler(0);   // 为了卸载目前的内存分配异常处理函数，强制C++在内存不够的时候抛出std:bad_alloc。
    // 申请size个T类型大小的空间
    T* tmp = (T*)(::operator new((size_t)(size * sizeof(T))));
    if (tmp == 0) {
        cerr << "out of memory" << endl; 
        exit(1);
    }
    return tmp;
}
template <class T>
inline void deallocate(T* buffer) {
    ::operator delete(buffer);
}

class allocator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
pointer allocate(size_type n) { 
    return ::allocate((difference_type)n, (pointer)0);
}//分配空间，调用上面封装后的函数
void deallocate(pointer p) { ::deallocate(p); }
pointer address(reference x) { return (pointer)&x; }	//获取地址
const_pointer const_address(const_reference x) { 
    return (const_pointer)&x; 
}
size_type init_page_size() { 
    return max(size_type(1), size_type(4096/sizeof(T))); 
}
size_type max_size() const { 
    return max(size_type(1), size_type(UINT_MAX/sizeof(T))); 
}

stl_construct.h

在上述基础上，对对象的构造和析构进行了一定的封装。

construct

构造函数除基本的调用外无重要的点。基本调用的函数为inline void _Construct(_T1* __p, const _T2& __value) { new ((void*) __p) _T1(__value); }

destroy

首先调用萃取机判断是否有析构函数，然后根据反馈分别调用相应的函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef typename __type_traits<_Tp>::has_trivial_destructor _Trivial_destructor;
// 若是 __true_type，什么都不做；这是 trivial destructor。
template <class _ForwardIterator> 
inline void __destroy_aux(_ForwardIterator, _ForwardIterator, __true_type) {}

// 若是 __false_type，这才以循环的方式遍历整个范围，并在循环中每经历一个对象就调用其destory()。（内部调用析构函数）
// 这是 non-trivial destructor
template <class _ForwardIterator>
void __destroy_aux(_ForwardIterator __first, _ForwardIterator __last, __false_type)
{
    for ( ; __first != __last; ++__first)
        destroy(&*__first);
}

此外，还有一些特化版本（非类，无需过多特殊处理）：

1
2
3
4
5
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*) {}

stl_uninitialized.h

该部分用于copy、fill大块内存中存储的数据。同样的

uninitialized_copy

该函数实现copy功能，首先调用萃取机判断是否是POD（传统 旧 数据）数据类型 typedef typename __type_traits<_Tp>::is_POD_type _Is_POD;，然后根据返回的结果调用不同的函数 return __uninitialized_copy_aux(__first, __last, __result, _Is_POD());。传统旧数据无需过多操作，直接复制即可。否则，循环调用相应的函数进行构造。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <class _InputIter, class _ForwardIter>
inline _ForwardIter __uninitialized_copy_aux(_InputIter __first, _InputIter __last,
                         _ForwardIter __result,
                         __true_type)
{
    return copy(__first, __last, __result);
}

template <class _InputIter, class _ForwardIter>
_ForwardIter  __uninitialized_copy_aux(_InputIter __first, _InputIter __last,
                         _ForwardIter __result,
                         __false_type)
{
    _ForwardIter __cur = __result;
    __STL_TRY {
        for ( ; __first != __last; ++__first, ++__cur)
            _Construct(&*__cur, *__first);
        return __cur;
    }
    __STL_UNWIND(_Destroy(__result, __cur));
}

uninitialized_fill

该函数与上述函数同理，所使用的is_POS_type及相关处理策略也相同，再此不赘述。

__uninitialized_copy_copy

该函数实现两个范围的拷贝，即为调用两次uninitialized_copy函数。函数源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
template <class _InputIter1, class _InputIter2, class _ForwardIter>
    inline _ForwardIter
    __uninitialized_copy_copy(_InputIter1 __first1, _InputIter1 __last1,
                              _InputIter2 __first2, _InputIter2 __last2,
                              _ForwardIter __result)
{
    _ForwardIter __mid = uninitialized_copy(__first1, __last1, __result);
    __STL_TRY {
        return uninitialized_copy(__first2, __last2, __mid);
    }
    __STL_UNWIND(_Destroy(__result, __mid));
}

所实现的功能为拷贝两次。在result位置，先插入第一个范围，再在新的位置继续插第二个范围。即:

  1. 首先将[first1,last1)数据拷贝到[result,result+last1−first1)
  2. 然后，再将[first2,last2)数据拷贝到[result+last1−first1,result+last1−first1+last2−first2)

stl_alloc.h

定义了一、二级配置器，配置器名为 alloc。设计宗旨：

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

class __malloc_alloc_template

第一级配置器，没有模板参数。

allocate deallocate reallocate直接调用malloc free realloc。当可用空间不足时，调用相应的函数处理。

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
template <int __inst>
class __malloc_alloc_template {

private:

    // 以下函数将用来处理内存不足的情况
    static void* _S_oom_malloc(size_t);
    static void* _S_oom_realloc(void*, size_t);
    
    static void (* __malloc_alloc_oom_handler)();

public:

    // 第一级配置器直接调用 malloc()
    static void* allocate(size_t __n)
    {
        void* __result = malloc(__n);
        // 以下无法满足需求时，改用 _S_oom_malloc()
        if (0 == __result) __result = _S_oom_malloc(__n);
        return __result;
    }
    // 第一级配置器直接调用 free()
    static void deallocate(void* __p, size_t /* __n */)
    {
        free(__p);
    }
    // 第一级配置器直接调用 realloc()
    static void* reallocate(void* __p, size_t /* old_sz */, size_t __new_sz)
    {
        void* __result = realloc(__p, __new_sz);
        // 以下无法满足需求时，改用 _S_oom_realloc()
        if (0 == __result) __result = _S_oom_realloc(__p, __new_sz);
        return __result;
    }
    // 以下仿真 C++ 的 set_new_handler()，可以通过它指定自己的 out-of-memory handler
    // 为什么不使用 C++ new-handler 机制，因为第一级配置器并没有 ::operator new 来配置内存
    static void (* __set_malloc_handler(void (*__f)()))()
    {
        void (* __old)() = __malloc_alloc_oom_handler;
        __malloc_alloc_oom_handler = __f;
        return(__old);
    }

};
_S_oom_malloc & _S_oom_realloc

这两个函数在一级分配器可用空间不足时调用。

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
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;

    //  给一个已经分配了地址的指针重新分配空间，参数 __p 为原有的空间地址，__n 是重新申请的地址长度
    for (;;) {
        // 当 "内存不足处理例程" 并未被客户设定，便调用 __THROW_BAD_ALLOC，丢出 bad_alloc 异常信息
        __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);
    }
}

在代码中我们可以看出，当内存不足时抛出异常__THROW_BAD_ALLOC。

__malloc_alloc_oom_handler
1
2
template <int __inst>
void (* __malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0;

simple_alloc

该类附加了0 nullptr的检查，主要是为上述实现的功能提供对外接口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<class _Tp, class _Alloc>
class simple_alloc {

public:
        // 配置 n 个元素
        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)); }
};

debug_alloc

为方便调试，每次分配多分配8Bytes空间，用来存储当前所分配的空间大小。

多分配的空间在头部存储，返回的是数据的首部，而非从_S_extra开始。故，需要注意的是，当调用deallocate reallocate时，需要前移找到真正的头部。

1
enum {_S_extra = 8};

__default_alloc_template

第二级配置器，GCC 默认使用第二级配置器，其作用是避免太多小额区块造成内存的碎片。

第二级配置器使用 memory pool 内存池管理。

第二级配置器的原理：

  • 当配置区块超过 128 bytes，就使用第一级配置器
  • 当配置区块小于 128 bytes，使用内存池管理
1
2
3
enum {_ALIGN = 8};  // 小型区块的上调边界
enum {_MAX_BYTES = 128}; // 小区区块的上限
enum {_NFREELISTS = 16}; // _MAX_BYTES/_ALIGN  free-list 的个数

关于使用enum去定义一些常量，源码中给出的解释：

Really we should use static const int x = N instead of enum { x = N }, but few compilers accept the former.

内存对齐

将小额区块内存需求量调至8的倍数。

1
2
static size_t _S_round_up(size_t __bytes) 
{ return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); }
  • & ~((size_t) _ALIGN - 1)。实现取8的倍数 8−1=0000…1112，取反为11111…10002，当与这个数字进行与操作时，原始数字的低三位全部丢弃（剩余位数均为8的整数倍，即为8的倍数。）
  • (__bytes) + (size_t) _ALIGN-1)。为防止取整数倍时，不足以凑成8的部分会被省略，故采取+7后再进行与操作。

free-list结点

1
2
3
4
5
6
union _Obj {
    union _Obj* _M_free_list_link;  // 利用联合体特点
    char _M_client_data[1];    /* The client sees this.        */
};
static _Obj* __STL_VOLATILE _S_free_list[_NFREELISTS];
// 维护 16 个空闲链表(free list)，初始化为0，即每个链表中都没有空闲数据块

每个内存块分别去管理8,16,24,32…,128Bytes

寻找空闲链表
1
2
3
4
//根据申请数据块大小找到相应空闲链表的下标，n 从 0 起算
static  size_t _S_freelist_index(size_t __bytes) {
    return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);
}

allocate

申请内存时，首先判断所申请的内存空间是否超过128 Bytes（链表块中能存放的最大空间）。不超过则在内存池中分配，超过调用一级分配器去分配。

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
static void* allocate(size_t __n)
{
    void* __ret = 0;

    // 如果需求区块大于 128 bytes，就转调用第一级配置
    if (__n > (size_t) _MAX_BYTES) {
        __ret = malloc_alloc::allocate(__n);
    }
    else {
        // 根据申请空间的大小寻找相应的空闲链表（16个空闲链表中的一个）
        _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;
        // 空闲链表没有可用数据块，就将区块大小先调整至 8 倍数边界，然后调用 _S_refill() 重新填充
        if (__result == 0)
            __ret = _S_refill(_S_round_up(__n));
        else {
            // 如果空闲链表中有空闲数据块，则取出一个，并把空闲链表的指针指向下一个数据块  
            *__my_free_list = __result -> _M_free_list_link;
            __ret = __result;
        }
    }

    return __ret;
};

deallocate

同理，根据大小寻找在哪里分配的空间，然后到相应的位置调用并释放空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static void deallocate(void* __p, size_t __n)
{
    if (__n > (size_t) _MAX_BYTES)   
        malloc_alloc::deallocate(__p, __n);   // 大于 128 bytes，就调用第一级配置器的释放
    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
    }
}

各容器中默认使用的分配器alloc为二级分配器

1
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;  // 令 alloc 为第二级配置器

_S_chunk_alloc

该函数是二级分配器__default_alloc_template核心的内存分配函数

1
2
3
4
5
static char* _S_chunk_alloc(size_t __size, int& __nobjs);
// Chunk allocation state.
static char* _S_start_free;  // 内存池起始位置。只在 _S_chunk_alloc() 中变化
static char* _S_end_free;    // 内存池结束位置。只在 _S_chunk_alloc() 中变化
static size_t _S_heap_size;

首先向内存池中申请__nobjs个空间，如果可用空间足够则返回。可用空间不足再判断可否分配1个__size，可以的话就分配一个，如若仍不可以：将剩余空间分配给free list然后配置 heap 空间，用来补充内存池，如果仍不足：则调用一级分配器去分配。

代码如下：

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
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);
    } else if (__bytes_left >= __size) {  // 内存池剩余空间不能满足申请，提供一个以上的区块
        __nobjs = (int)(__bytes_left/__size);
        __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);  // 配置 heap 空间，用来补充内存池
        if (0 == _S_start_free) {  // heap 空间不足，malloc() 失败
            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) {
                    *__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个空间的意义：1个被交给客户端去使用，剩下19个交给 free-list 维护，要的时候再去取即可。(内存池中也会有一部分)

当使用空间时，先向free list申请，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
26
27
28
29
30
31
32
template <bool __threads, int __inst>
void*
__default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
{
    int __nobjs = 20;
    // 调用 _S_chunk_alloc()，缺省取 20 个区块作为 free list 的新节点
    char* __chunk = _S_chunk_alloc(__n, __nobjs);
    _Obj* __STL_VOLATILE* __my_free_list;
    _Obj* __result;
    _Obj* __current_obj;
    _Obj* __next_obj;
    int __i;

    // 如果只获得一个数据块，那么这个数据块就直接分给调用者，空闲链表中不会增加新节点
    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);  // 第0个数据块给调用者，地址访问即chunk~chunk + n - 1  
    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);
}
-------------感谢阅读有缘再见-------------