STL Allocator

Posted on | Edited on

前言

在c++中，可以使用new在堆上构建一个新的对象，其实new包含两个步骤

  • 分配内存
  • 使用constructor在内存中构建对象内容

而delete也是如此

  • 调用deconstructor将对象析构
  • 释放内存

知道了new和delete的原理，可以手动模拟一下

1
2
3
4
5
6
7
8
9
10
11
12
class Test {
public:
    Test(int i) {};
};

int main() {
    Test *k = (Test *) malloc (sizeof(Test)); //分配内存
    new (k) Test(3); //构建对象 ，placement new(placement有放置的意思，可以理解为将对象内容放置在内存中)
    k->~k(); //析构
    free(k); //释放内存
    return 0;
}

STL中的空间配置器

在STL中，为了妥善地管理内存，有专门的STL allocator，这个是为STL中的各种容器服务的

然后关于分配内存和构造STL allocator决定将这两个阶段分开，内存配置器定义在<memory>之中，<memory>包含

  • : 负责内存分配
  • : 负责对象构造，析构
  • : 常用的工具

stl_construct.h

如上提到的，此头文件包含的函数负责对象的构造与析构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//构造
template <class _T1, class _T2>
inline void construct(_T1* __p, const _T2& __value) {
  _Construct(__p, __value);
}

template <class _T1>
inline void construct(_T1* __p) {
  _Construct(__p);
}

//析构
template <class _Tp>
inline void destroy(_Tp* __pointer) {
  _Destroy(__pointer);
}
//批量析构
template <class _ForwardIterator>
inline void destroy(_ForwardIterator __first, _ForwardIterator __last) {
  _Destroy(__first, __last);
}

构造

1
2
3
4
5
6
7
8
inline void _Construct(_T1* __p, const _T2& __value) {
  new ((void*) __p) _T1(__value); 
}

template <class _T1>
inline void _Construct(_T1* __p) {
  new ((void*) __p) _T1();
}

可以看到，使用的都是placement new,和上文我们所做的一样，那么构造函数是用在哪里的呢？答案是用在STL容器里面的，例如vector的push_back里就有

1
2
3
4
5
6
7
8
void push_back(const _Tp& __x) {
    if (_M_finish != _M_end_of_storage) {
      construct(_M_finish, __x); //_M_finish是指向尾端的指针，__x就是要放入的值
      ++_M_finish;
    }
    else
      _M_insert_aux(end(), __x);
  }

析构

想象一下，如何对vector中的内容进行析构

首先，要给出范围 【1】，传入first和last两个Iterator,假设类型是vector<Test>::iterator=Test*

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template <class _ForwardIterator>
inline void _Destroy(_ForwardIterator __first, _ForwardIterator __last) {
  __destroy(__first, __last, //【1】
  			__VALUE_TYPE(__first)); //【2】
}

------------------------------value_type//【3】
template <class _Iter>
inline typename iterator_traits<_Iter>::value_type*
__value_type(const _Iter&)//【4】
{
  return static_cast<typename iterator_traits<_Iter>::value_type*>(0);//【5】
}
------------------------------Iter_tarits//【6】
template <class _Tp>
struct iterator_traits<_Tp*> {
  typedef random_access_iterator_tag iterator_category;
  typedef _Tp                         value_type;
  typedef ptrdiff_t                   difference_type;
  typedef _Tp*                        pointer;
  typedef _Tp&                        reference;
};

可以看到上面的函数对迭代器进行【2】VALUE_TYPE(__value_type的宏)取value_type, __value_type如【3】所示，此时，【4】_Iter = Test *

然后对其进行【5】iterator_traits，匹配到【6】的特化版本，返回的value_type是Test

然后对其进行【7】type_traits看看有没有trivial（无用的，可忽略的）析构函数

type_traits只对POD类型进行了特化，因此Test匹配到了泛化版本，如【8】所示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <class _ForwardIterator, class _Tp>
inline void 
__destroy(_ForwardIterator __first, _ForwardIterator __last, _Tp*)
{
  typedef typename __type_traits<_Tp>::has_trivial_destructor
          _Trivial_destructor;//【7】
  __destroy_aux(__first, __last, _Trivial_destructor());
}
----------------------------------------------type_traits//【8】
template <class _Tp>
struct __type_traits { 
   typedef __true_type     this_dummy_member_must_be_first;
   typedef __false_type    has_trivial_default_constructor;
   typedef __false_type    has_trivial_copy_constructor;
   typedef __false_type    has_trivial_assignment_operator;
   typedef __false_type    has_trivial_destructor;
   typedef __false_type    is_POD_type;
};

可以看到，STL取最保守的值，也就是说，除非有特化，不然都会认为构造函数是no-trivial(重要的)

例如Test *没有经过特化，那么得到的结果就是has_trivial_destructor = __false_type

然后，就会开始选择析构的方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <class _ForwardIterator>
void
__destroy_aux(_ForwardIterator __first, _ForwardIterator __last, __false_type) //有重要的析构函数，调用，Test选择的是这个
{
  for ( ; __first != __last; ++__first)
    destroy(&*__first);
}

template <class _ForwardIterator> 
inline void __destroy_aux(_ForwardIterator, _ForwardIterator, __true_type) {} //析构函数是不重要的，所以不调用

//开始析构	
template <class _Tp>
inline void destroy(_Tp* __pointer) {
  _Destroy(__pointer);
}

template <class _Tp>
inline void _Destroy(_Tp* __pointer) {
  __pointer->~_Tp();
}

std_alloc.h

此文件包含内存的配置与释放，设计如下

  • 向system heap索取空间
  • 考虑多线程状态
  • 考虑内存不足的应变措施
  • 考虑内存碎片问题

以下讨论排除多线程状态

SGI以malloc和free完成内存的配置和释放，但是考虑到内存碎片问题，SGI设计了双层配置器

  • 一级配置器使用malloc和free
  • 二级配置器使用复杂的内存池

当申请内存超过128byte，使用一级配置器，小于则使用二级配置器，然而整个设计是否采用二级配置器，取决于__USE_MALLOC具体可以看下面，展示了什么情况使用二级配置器

1
2
3
4
5
6
7
8
9
10
---------stl_alloc.h
#ifdef __STL_STATIC_TEMPLATE_MEMBER_BUG
#  define __USE_MALLOC //使用二级配置器
#endif
---------stl_config.h
# ifdef __GNUC__ //gcc的版本
#   if __GNUC__ == 2 && __GNUC_MINOR__ <= 7
#     define __STL_STATIC_TEMPLATE_MEMBER_BUG
#   endif
# endif

一级配置器

一级配置器为template <int __inst> class __malloc_alloc_template

首先定义所抛出的异常bad_alloc

1
2
3
4
5
6
7
8
9
10
#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

然后是分配和释放的接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static void* allocate(size_t __n)
{
  void* __result = malloc(__n); //分配内存
  if (0 == __result) __result = _S_oom_malloc(__n); //失败则调用处理内存不足的函数
  return __result;
}

static void deallocate(void* __p, size_t /* __n */)
{
  free(__p);
}

static void* reallocate(void* __p, size_t /* old_sz */, size_t __new_sz)
{
  void* __result = realloc(__p, __new_sz); //更改已经配置的内存空间，即更改由malloc()函数分配的内存空间的大小。
  if (0 == __result) __result = _S_oom_realloc(__p, __new_sz);//失败则调用
  return __result;
}

下面是处理失败的函数，当然你也可以自己指定处理方式

1
2
3
4
5
6
static void (* __set_malloc_handler(void (*__f)()))()
  {
    void (* __old)() = __malloc_alloc_oom_handler;
    __malloc_alloc_oom_handler = __f; //设置处理函数，默认为0
    return(__old);
  }

默认的处理方式

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;

    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; //定义一级配置器

也就是说，默认内存不够就会抛出异常，当然如果你设置了处理函数，就会用处理函数去处理

设计内存不足的处理方式是你的责任

二级配置器

二级配置器为

template <bool threads, int inst>class __default_alloc_template

二级配置器使用内存池，每次配置一大块内存，然后将其分成分成16个链表，各自管理的大小为8的倍数

也就是说每一个链表管理一种大小的内存块，16个链表管理{8,16,….,128}byte的小型内存块链

1
2
3
enum {_ALIGN = 8};
enum {_MAX_BYTES = 128};
enum {_NFREELISTS = 16}; // _MAX_BYTES/_ALIGN

其中内存块链的节点为_Obj_，链表采用线性表+链表的方式管理，其中链的初始化为

1
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };
1
2
3
4
5
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];

根据索取的内存块大小决定从哪一条链上索取内存块

例如索取128byte的块，则定位到 index = (128+7)/8 - 1 = 15的链

1
2
3
static  size_t _S_freelist_index(size_t __bytes) {
        return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);
 }

关于内存池的管理

1
2
3
4
5
6
7
8
9
10
// 发现链上没有可用块，就重新填充
  static void* _S_refill(size_t __n);
//配置一大块空间，能够容纳nodejs个大小为size的内存块
//如果失败，则会减少索要的个数，也就是nodjs
  static char* _S_chunk_alloc(size_t __size, int& __nobjs);

  // 内存池的状态
  static char* _S_start_free; 
  static char* _S_end_free;
  static size_t _S_heap_size;

内存配置函数

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

    if (__n > (size_t) _MAX_BYTES) { //大于128就使用一级配置器
      __ret = malloc_alloc::allocate(__n);
    }
    else {
      _Obj* __STL_VOLATILE* __my_free_list
          = _S_free_list + _S_freelist_index(__n); //找到合适的内存链
      _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;
  };

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;
      __q -> _M_free_list_link = *__my_free_list;
      *__my_free_list = __q;
      // lock is released here
    }
  }

重新填充

如果在分配的时候发现链上没有可用块了，就调用该函数重现填充链表

默认填充的数目是20，如果内存池内存不够，那么获得的块少于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
template <bool __threads, int __inst>
void*
__default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
{
    int __nobjs = 20; //默认填充数量
    char* __chunk = _S_chunk_alloc(__n, __nobjs); //从内存池取得空间，__nodejs是引用传递，其值会在_S_chunk_alloc中会被改变
    _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; //在chunk上建立链表
    
      *__my_free_list = __next_obj = (_Obj*)(__chunk + __n); //指向链表尾部
    
      for (__i = 1; ; __i++) {
          //从1开始逐渐填充，第0个返回给使用者
        __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);
}

内存池

_S_chunk_alloc是从内存池中获取空间交给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
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
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);//改变__nodejs
        __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.
            
            //遍历16个链表
            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));
    }
}

stl_uninitialized

这里有三个用于为初始化的空间的函数

三者都有一个特点，就是如果过程中产生一次失败(会抛出异常)，则将之前所做的全部撤销

具体是使用

1
define __STL_UNWIND(action) catch(...) { action; throw; }

该宏捕获所有异常，并执行action

uninitialized_copy

可以将某个范围的对象拷贝到未初始化的内存，如果拷贝存在一次失败，那么就不构造任何东西

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
//参数模式类似于前面提到过的析构，同样是去value type
template <class _InputIter, class _ForwardIter>
inline _ForwardIter
  uninitialized_copy(_InputIter __first, _InputIter __last,
                     _ForwardIter __result)
{
  return __uninitialized_copy(__first, __last, __result,
                              __VALUE_TYPE(__result)); //根据value type选择合适的复制函数
}

template <class _InputIter, class _ForwardIter, class _Tp>
inline _ForwardIter
__uninitialized_copy(_InputIter __first, _InputIter __last,
                     _ForwardIter __result, _Tp*)
{
  typedef typename __type_traits<_Tp>::is_POD_type _Is_POD; //又出现了，判断是否是POD类型
  return __uninitialized_copy_aux(__first, __last, __result, _Is_POD());
}

template <class _InputIter, class _ForwardIter>
inline _ForwardIter 
__uninitialized_copy_aux(_InputIter __first, _InputIter __last,
                         _ForwardIter __result,
                         __true_type) //如果是POD类型，就不需要特地调用构造函数
{
  return copy(__first, __last, __result); //调用算法库的copy
}

template <class _InputIter, class _ForwardIter>
_ForwardIter 
__uninitialized_copy_aux(_InputIter __first, _InputIter __last,
                         _ForwardIter __result,
                         __false_type) //如果不是POD，则逐个调用构造函数
{
  _ForwardIter __cur = __result;
  __STL_TRY {
    for ( ; __first != __last; ++__first, ++__cur)
      _Construct(&*__cur, *__first);
    return __cur;
  }
  __STL_UNWIND(_Destroy(__result, __cur)); //捕获异常并将所有已构造的对象全部析构
}

两个特化版本，const char , const wchar_t，对于这两个类型，最有效的方法是直接移动内存内容，使用memmove

1
2
3
4
5
6
7
8
9
10
11
12
13
14

inline char* uninitialized_copy(const char* __first, const char* __last,
                                char* __result) {
  memmove(__result, __first, __last - __first);
  return __result + (__last - __first);
}

inline wchar_t* 
uninitialized_copy(const wchar_t* __first, const wchar_t* __last,
                   wchar_t* __result)
{
  memmove(__result, __first, sizeof(wchar_t) * (__last - __first));
  return __result + (__last - __first);
}

uninitialized_fill

该函数的作用是将某个范围的内存初始化为某个值

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
template <class _ForwardIter, class _Tp>
inline void uninitialized_fill(_ForwardIter __first,
                               _ForwardIter __last, 
                               const _Tp& __x)
{
  __uninitialized_fill(__first, __last, __x, __VALUE_TYPE(__first)); //一样的套路，判断value_type
}

template <class _ForwardIter, class _Tp, class _Tp1>
inline void __uninitialized_fill(_ForwardIter __first, 
                                 _ForwardIter __last, const _Tp& __x, _Tp1*)
{
  typedef typename __type_traits<_Tp1>::is_POD_type _Is_POD;
  __uninitialized_fill_aux(__first, __last, __x, _Is_POD());//判断是否是POD类型
                   
}

template <class _ForwardIter, class _Tp>
inline void
__uninitialized_fill_aux(_ForwardIter __first, _ForwardIter __last, 
                         const _Tp& __x, __true_type)
{
  fill(__first, __last, __x); //调用算法库
}

template <class _ForwardIter, class _Tp>
void
__uninitialized_fill_aux(_ForwardIter __first, _ForwardIter __last, 
                         const _Tp& __x, __false_type)
{
  _ForwardIter __cur = __first;
  __STL_TRY {
    for ( ; __cur != __last; ++__cur)
      _Construct(&*__cur, __x);
  }
  __STL_UNWIND(_Destroy(__first, __cur));//捕获异常，析构
}

uninitialized_fill_n

将从[firs,first+n]全部构造为相同的值，和上面的一样

1
2
3
4
5
6
template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter 
uninitialized_fill_n(_ForwardIter __first, _Size __n, const _Tp& __x)
{
  return __uninitialized_fill_n(__first, __n, __x, __VALUE_TYPE(__first));
}

至此

以上大致分析完了内存构造的三个重要的块，真的是累