SGI STL二级空间配置器源码剖析

笔者建议配合这两篇博客进行学习

侯捷 | C++ | 内存管理 | 学习笔记（二）:第二章节 std::allocator-CSDN博客

施磊C++ | 项目实战 | 手写移植SGI STL二级空间配置器内存池 项目源码-CSDN博客

大块内存都是malloc和free来进行分配回收。

但是要进行大量频繁的小块内存的分配和释放就要用到内存池的思想，因为频繁调用malloc和free的效率并不高。

（具体可以看侯捷 | C++ | 内存管理 | 学习笔记（二）:第二章节 std::allocator-CSDN博客）

防止小块内存频繁的分配,释放,造成内存很多的碎片出来,内存没有更多的连续的大内存块。所以应用对于小块内存的操作,一般都会使用内存池来进行管理。

1.SGI STL的vector容器源码如何管理对象

C++ STL标准库 => alloctor空间配置器

我们知道new这个操作符有两个操作，第一个是对象内存开辟第二个是调用对象的构造函数

delete是对象的析构和内存的释放（深入了解new，定位new（）placement_address，delete转至侯捷 | C++ | 内存管理 | 学习笔记（一）: 第一章节 primitives-CSDN博客）

而空间配置器的使用

分离了对象的内存开辟和对象构造

分离了对象的析构和内存的释放

举例：vector容器

1
2
3
4
5
6
7
8
9
10
//这四个行为都是封装在alloctor空间配置器里面的
//allocator:负责给容器开辟内存空间=>malloc
//deallocate:负责释放容器内存空间=>free
//construct:负责给容器构造一个对象=>定位new实现
//destroy:负责析构容器的对象=> p->~T()
template<typename T,typename _Alloc=allocator<T>>
class vector
{
...    
};

SGI STL => 两个allocator的实现：一级allcoator 内存管理依旧用的是malloc/free 二级alloctor 内存池的实现

容器：底层存储的对象的构造和析构是通过定义的全局的函数模板Construct和Destroy完成的

但其实也都还是定位new实现的

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;
    }
    else
      _M_insert_aux(end(), __x);
  }
1
2
3
4
5
6
7
8
9
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);
}
1
2
3
4
5
6
7
8
9
10
//找到哩
template <class _T1, class _T2>
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();
}

可以看到也是用定位new实现的

所以应该SGI STL里面的空间配置器区别于C++STL标准库的四个功能，完成的应该是allocate和deallocate功能

2.SGI STL空间配置重要成员

1.空间配置器相关定义

1
2
3
4
5
template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class vector : protected _Vector_base<_Tp, _Alloc> 
{
    ...
};

__STL_DEFAULT_ALLOCATOR(_Tp)这个东西就是vector的空间配置器

ctrl+鼠标左键直接进入这个宏就是allocator<T>

从这里可以看到__STL_DEFAULT_ALLOCATOR通过宏控制有两种实现，一种是allocator< T >，另一种

是alloc，这两种分别就是SGI STL的一级空间配置器和二级空间配置器的实现。

1
2
3
4
5
6
7
# ifndef __STL_DEFAULT_ALLOCATOR
#   ifdef __STL_USE_STD_ALLOCATORS
#     define __STL_DEFAULT_ALLOCATOR(T) allocator< T >//一级空间配置器
#   else
#     define __STL_DEFAULT_ALLOCATOR(T) alloc//二级空间配置器
#   endif
# endif

如果我不指定那就是用alloc（二级的）

1
2
3
4
template <int __inst>
class __malloc_alloc_template // 一级空间配置器内存管理类 -- 通过malloc和free管理内存
template <bool threads, int inst>
class __default_alloc_template   // 二级空间配置器内存管理类 -- 通过自定义内存池实现内存管理

一级空间配置器

底层用的和C++STL一样的，还是malloc和free

image-20241024154808001

2.重要类型和变量定义

1
2
3
4
5
6
// 内存池的粒度信息
enum {_ALIGN = 8 };//对齐 8字节
enum {_MAX_BYTES = 128 };// 最大字节128字节
enum {_NFREELISTS = 16 };//自由链表数 16条

//16是128/8得出的
1
2
3
4
5
// 每一个内存chunk块（结点）的头信息
union _Obj {
union _Obj* _M_free_list_link;//保存下一个结点的地址
char _M_client_data[1];  /* The client sees this. */
};
1
2
3
// 组织所有自由链表的数组，数组的每一个元素的类型是_Obj*，全部初始化为 0
//多线程环境下防止线程自己拷贝一个副本，会加一个volatile关键字，使得在数据段或者堆上的数据改变了每个线程都可以立马看到，防止多个线程看到的数据版本不一致
static _Obj* __STL_VOLATILE _S_free_list[_NFREELISTS];//这是个数组名，大小就是上面的16

image-20241024162626812

每个boj其实可以看做自由链表头结点，下面都挂着内存块。方便大家理解（记得看看union的使用方便理解）

第一个从8字节开始，后面16,24依次类推

1
2
3
4
5
6
7
8
9
10
// Chunk allocation state. 记录内存chunk块的分配情况 初始化全为0
static char* _S_start_free;
static char* _S_end_free;
static size_t _S_heap_size;
template <bool __threads, int __inst>
char* __default_alloc_template<__threads, __inst>::_S_start_free = 0 ;
template <bool __threads, int __inst>
char* __default_alloc_template<__threads, __inst>::_S_end_free = 0 ;
template <bool __threads, int __inst>
size_t __default_alloc_template<__threads, __inst>::_S_heap_size = 0 ;

3.两个重要的辅助接口函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*将 __bytes 上调至最邻近的 8 的倍数 _ALIGN==8
1-8 全都映射（对齐）到8
9-16 全都映射（对齐）到16
*/
static size_t _S_round_up(size_t __bytes)
{ return (((__bytes) + (size_t) _ALIGN- 1 ) & ~((size_t) _ALIGN - 1 )); }


/*返回 __bytes 大小的chunk块位于 free-list 中的编号
作用就是，如果申请的字节在1-8之间，就挂到内存块大小为8的那个链表下面
如果申请的字节在9-16之间，就挂到内存块大小为16的那个链表下面
*/
static size_t _S_freelist_index(size_t __bytes) {
return (((__bytes) + (size_t)_ALIGN- 1 )/(size_t)_ALIGN - 1 ); }

3.内存池管理函数

1.allocate函数

1
2
// 分配内存的入口函数
static void* allocate(size_t __n)

内存池有chunk块就去相应大小的链表下面拿给程序，没有的话就看_S_refill如何进行chunk的分配了

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
 static void* allocate(size_t __n)
  {
    void* __ret = 0;
	//大于128字节，直接malloc
    if (__n > (size_t) _MAX_BYTES) {
      __ret = malloc_alloc::allocate(__n);
    }
     //小于128字节
    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
      /*线程安全*/
      _Lock __lock_instance;
#     endif
      _Obj* __RESTRICT __result = *__my_free_list;
      //内存池有chunk块就去相应大小的链表下面拿，没有的话就看如何进行分配了
      if (__result == 0)//没有相应大小chunk块，下面解释如何分配
        __ret = _S_refill(_S_round_up(__n));
      else {//有相应大小chunk块,就从内存池里面拿出相应的块分配给程序
        *__my_free_list = __result -> _M_free_list_link;
        __ret = __result;
      }
    }
	//返回我们从内存池申请的chunk块
    return __ret;
  }

2._S_refill函数

refill函数的主要功能是在内存池中的空闲内存不足时，从操作系统中申请更多的内存来补充内存池。

1
2
3
template <bool __threads, int __inst>
void*
__default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
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
template <bool __threads, int __inst>
void*
__default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
{
    int __nobjs = 20;
    //chunk_alloc主要负责内存开辟
    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和chunk都指向chunk_alloc分配的内存的首地址 chunk指针用来遍历chunk块，result指针指向开头的地方做一个保存
      __result = (_Obj*)__chunk;
    //把头指针的位置指向下一chunk块，因为当前的情形是已经要把当前自由链表头指针的位置分配出去了，而头指针的后面才是剩下的空闲的chunk块，再次分配是分配空闲的，分配出去的就没关系了
      *__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
      for (__i = 1; ; __i++) {
        __current_obj = __next_obj;
          //这行描述的就是遍历过程 先转成char*，这样每次加减都是以字节为单位，chunk指针每一次加8字节到下一个chunk块（不一定是8，这里只是说明，具体多少要看内存块的大小，反正就是到下一个chunk内存块了）
        __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;
        }
      }
    //返回第一个空闲的chunk结点给容器使用
    return(__result);
}

image-20241024182145143

蓝色的就是上面的union联合体，里面有一个指针就把它当成链表的next指针域，这里的第一个if是遍历到链表链接的chunk的末尾了，就把它置为0（nullptr）就是一个到了结尾的标志。而else就是给其他不在末尾的chunk块的next指针域写下一个空闲chunk的地址（其实就是把这条链表给连接起来）。

因为refill是申请内存，申请到内存块需要这么一个过程串成一个链表，不然就是散乱的块，也没办法管理。

3._S_chunk_alloc

这是refill函数里要负责内存开辟函数

1
2
3
4
5
//传入要申请的内存大小（注意是一个块的）和块数
template <bool __threads, int __inst>
char*
__default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size, 
                                                            int& __nobjs)

内存开辟的具体过程

就是开辟size * 块数 *2 这么大的内存空间，多出来留着备用，备用的也分配完就重新申请，重新申请会在块数*2的基础上再加上已经申请的字节总数/16这么多的块（完全按照经验来的）

1.举个例子，我们开8字节，10块，实际上内存池会申请20块8字节的chunk，多的10块作为备用内存空间。如果开头那10块用完了在申请分配，那就用后面备用的这10块。要是这10个也用完，那就再次申请，这次申请就会申请20+追加量，追加量就是累计分配的字节数除以16，我们累计分配8*20=160,160/16=10，也就是这次会分配30块，累加量就会变成 50*8=400字节了。

2.诶，假如我们用了申请了20块8字节的，实际会给40个，前面20个给申请的程序，后面20个留着备用。如果此时我们再次申请16个字节的chunk块2个，那么用的就是备用内存空间，把20个8字节换成10个16字节的chunk块了，然后把这10个连接一下，然后16个字节大小的那个自由链表的头指针就连接到这10个16字节大小的chunk了。

3.还是申请20 *8字节的，完了以后要申请一个128的chunk块。那备用内存160只能放一个128了，剩下32字节，直接就把这一个chunk返回回去就行，不用做链表的连接了，因为只有一个块，不需要连接

把申请的chunk块指针返回给refill的__chunk指针

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>
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);
        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) {
                    *__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));
    }
}

内存开辟失败的处理

上面代码第20行else之后的部分

1.接着上面的3，我们备用内存还剩下32字节

而此时我们申请分配40字节大小的chunk块，而20*40=800,32小于800，并且32也小于40，说明备用内存不够申请的chunk块，甚至一块40字节的也不够，那就进入else

然后申请分配20个再加累积量/16这么多个40字节的chunk块

剩下的32字节的chunk就直接归到32字节大小的obj链表里面去了，就是剩下的也别浪费，能归到哪里就和哪里接上，这个地方给的时候也是当做空闲块用头插法

2.如果备用的内存池也不够用了，那就只能通过malloc进行开辟了。如果malloc也失败了，那就会去遍历obj数组，去看看我已经分配过的但是你还没用的内存chunk，因为这些都在链表上面挂着，看看这里的空闲块能不能满足我的需求。

总结一下，就是如果40没有了，备用的也不够，malloc也失败了。那就往后遍历obj数组，找到下一个下面还有chunk块的比如48，把他下面的块切一块40的挂到40的下面，剩下的8可以挂到8下面

malloc失败了，遍历obj数组也没找到，那就进入

1
_S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);

进入这个这个类的allocate（15-20行）之后，里面主要的是_S_oom_realloc（18行），下面在进入这个函数调用

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

private:

  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)
  {
    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);
    if (0 == __result) __result = _S_oom_realloc(__p, __new_sz);
    return __result;
  }

  static void (* __set_malloc_handler(void (*__f)()))()
  {
    void (* __old)() = __malloc_alloc_oom_handler;
    __malloc_alloc_oom_handler = __f;
    return(__old);
  }

};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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);
    }
}

*__my_malloc_handler这是一个函数指针，用户可以通过这个释放一些内存资源供malloc使用

下面if==0说明用户自己也没什么补救措施，那就抛出异常了，开辟内存失败

如果没进if那就说明用户有补救措施，就通过这个函数释放一些内存资源，然后再使用malloc开辟内存，如果还是失败，那继续进行for循环，调用当前这个函数，一直失败一直调用，直到开辟成功或者抛出异常内存终止

4.deallocate

内存chunk块归还，释放的函数

传入的是要归还的chunk指针和要归还的大小

1
static void deallocate(void* __p, size_t __n)

要归还的块采用头插法插入到头结点obj*和第一个空闲chunk结点之间，成为新的第一个空闲块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
  static void deallocate(void* __p, size_t __n)
  {
      //回收的过大 直接用free
    if (__n > (size_t) _MAX_BYTES)
      malloc_alloc::deallocate(__p, __n);
    else {
        //定位到要回收的chunk块的地址
      _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 */
       //这里就是链表的头插法
        //要归还的块是要插入的块，要插入到头结点和头结点的next域指的节点（这个节点是第一个空闲块），而我们归还的这个块就接到头结点的next域，然后要回收的块再接着原来的第一个空闲块，成为新的第一个空闲块，就类比一下链表的头插法就行
      __q -> _M_free_list_link = *__my_free_list;
      *__my_free_list = __q;
      // lock is released here
    }
  }

5.reallocate

重新扩容或者缩容

传入内存起始地址，旧的大小，新的大小

如果旧的比新的大，那就缩容，新的比旧的大，那就是扩容

1
2
3
4
5
6
template <bool threads, int inst>
void*
__default_alloc_template<threads, inst>::reallocate(void* __p,
                                                    size_t __old_sz,
                                                    size_t __new_sz)
//内存起始地址，旧的大小，新的大小
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
template <bool threads, int inst>
void*
__default_alloc_template<threads, inst>::reallocate(void* __p,
                                                    size_t __old_sz,
                                                    size_t __new_sz)
{
    void* __result;
    size_t __copy_sz;
//如果旧的和新的全都比128字节大，那说明这就不是从我内存池里面出去的，那就直接调用c的realloc函数
    if (__old_sz > (size_t) _MAX_BYTES && __new_sz > (size_t) _MAX_BYTES) {
        return(realloc(__p, __new_sz));
    }
    //如果新的和旧的对齐以后一样，那就不用扩容，直接返回 比如一个12，扩容到15，但是这两个的round_up都是16 那就没必要扩容了
    if (_S_round_up(__old_sz) == _S_round_up(__new_sz)) return(__p);
    //分配一块新的大小的内存空间
    __result = allocate(__new_sz);
    //比较大小，就选个比较小的
    __copy_sz = __new_sz > __old_sz? __old_sz : __new_sz;
    //把内容copy到新开辟的内存空间
    memcpy(__result, __p, __copy_sz);
    //把旧的内存空间给释放掉
    deallocate(__p, __old_sz);
    //最后把新的内存地址返回
    return(__result);
}

4.SGI STL二级空间配置器内存池的实现优点

1.对于每一个字节数的chunk块分配,都是给出一部分进行使用,另一部分作为备用,这个备用可以给当前字节数使用,也可以给其它字节数使用
2.对于备用内存池划分完chunk块以后,如果还有剩余的很小的内存块,再次分配的时候,会把这些小的内存块再次分配出去,备用内存池使用的干干净净!

3.当指定字节数内存分配失败以后,有一个异常处理的过程,bytes-128字节所有的chunk块进行查看,如果哪个字节数有空闲的chunk块,直接借一个出去

如果上面操作失败，还会调用oom_malloc这么一个预先设置好的malloc内存分配失败以后的回调函数。

如果没设置回调函数，throw bad_alloc

设置了那就for( ;; )，调用 (*oom_malloc_handler) ();释放一部分资源