深度剖析SGI STL二级空间配置器内存池源码

深度剖析SGI STL二级空间配置器内存池源码

文章目录

​​一、SGI STL二级空间配置器重要成员解读​​​​二. 二级空间配置器内存池的结构​​​​三、 两个重要的函数​​

​​1. _S_round_up​​​​2. _S_freelist_index​​

​​四、 内存池allocate分配过程​​​​五、分配内存池_S_refill源码分析​​​​六、实际分配内存池_S_chunk_alloc源码分析​​​​七、内存归还dealloacte​​​​八、reallocate​​​​九、总结​​

一、SGI STL二级空间配置器重要成员解读

为了防止小块内存频繁分配、释放，造成系统内很多内存碎片，没有更多的连续大内存块。所以对于小块内存的分配回收通常使用内存池进行管理。

SGI STL包含了一级空间配置器和二级空间配置器

其中一级空间配置器allocator采用malloc和free来管理内存，和C++标准库中提供的allocator是一样的 但其二级空间配置器allocator采用了基于freelist自由链表原理的 内存池机制 实现内存管理

template class vector : protected _Vector_base<_Tp, _Alloc>

空间配置器的使用

# ifndef __STL_DEFAULT_ALLOCATOR# ifdef __STL_USE_STD_ALLOCATORS# define __STL_DEFAULT_ALLOCATOR(T) allocator< T ># else# define __STL_DEFAULT_ALLOCATOR(T)# endif# endif

从上面可以看到​​__STL_DEFAULT_ALLOCATOR​​​通过宏控制有两种实现，一种是​​allocator< T >​​​，另一种 是​​​alloc​​，这两种就是SGI STL的一级空间配置器和二级空间配置器的实现

二. 二级空间配置器内存池的结构

// 对齐字节数enum {_ALIGN = 8}; // 数组对应位置挂的内存池最大的__chunk块的的大小为128B//如果大于128字节就相当于是大块内存，不通过内存池管理，还是用一级空间配置器malloc、free管理enum {_MAX_BYTES = 128}; // 自由链表的个数enum {_NFREELISTS = 16};

_S_free_list数组

// 多线程环境中，堆或者数据段的数据都会加上__STL_VOLATILE，防止各个线程对数据进行缓存static _Obj* __STL_VOLATILE _S_free_list[_NFREELISTS]; // 会初始化为0// 记录内存块的分配状态，Chunk allocation state.// 全部会初始化为0static char* _S_start_free; static char* _S_end_free;static size_t _S_heap_size; // 向OS申请的所有内存大小

​​_Obj​​ 的结构

union _Obj { union _Obj* _M_free_list_link; char _M_client_data[1]; /* The client sees this. */};

三、 两个重要的函数

1. _S_round_up

作用： 容器空间配置器申请内存的时候，会用​​_S_round_up​​​把所申请的字节​​__bytes​​大小上调至8的整数倍

static size_t _S_round_up(size_t __bytes) { return (((__bytes) + (size_t) _ALIGN - 1) & ~((size_t) _ALIGN - 1)); }

原理就是一个数加上+7，然后去掉%8后多余的部分 通过和​​​~((size_t) _ALIGN - 1)​​​相与去掉%8多余的部分，这就使得与的结果一定是8的整数倍，而且得到的结果不小于原始的​​__bytes​​​​~((size_t) _ALIGN - 1)​​表达式的值为：​​11111111 11111111 11111111 11111000​​

: 00000000 00000000 00000000 00000100 (size_t)_ALIGN - 1: 00000000 00000000 00000000 00000111 ~((size_t)_ALIGN - 1) : 11111111 11111111 11111111 11111000 __bytes + (size_t)_ALIGN - 1 : 00000000 00000000 00000000 00001011

2. _S_freelist_index

作用： 返回 __bytes 大小的chunk块位于 free-list 中的编号

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

比如原来的__bytes是​​8n+3​​​，+7后变成​​8(n+1)+2​​​，除以8后变成​​n+1​​，减1是因为下标从0开始

四、 内存池allocate分配过程

根据想分配的内存大小，定位到free-list相应的块

如果从来没有分配过内存池，那直接构造内存池，然后分配空间

如果已经构造了内存池，那就使得free-list相应的块指向内存池下一块内存块，然后把前一块内存分配出去

static void* allocate(size_t __n){ void* __ret = 0; if (__n > (size_t) _MAX_BYTES) { // 申请的空间大于_MAX_BYTES，则不由内存池管理，调用malloc_alloc::allocate分配空间，底层就是malloc __ret = malloc_alloc::allocate(__n); } else { // __my_free_list 指向__n个字节应该在内存池哪个块分配 _Obj* __STL_VOLATILE* __my_free_list = _S_free_list + _S_freelist_index(__n); # ifndef _NOTHREADS _Lock __lock_instance; // 加锁，下方代码操作自由链表属于临界区# endif // 准备在__result 下分配内存 _Obj* __RESTRICT __result = *__my_free_list; if (__result == 0) // 若__result后没有分配空间，直接构造内存池，_S_round_up(__n)指的是内存池每个块的大小 __ret = _S_refill(_S_round_up(__n)); else { //把_M_free_list_link理解成next，__my_free_list指向下一个节点，也就是_S_free_list的元素直接指向后面的节点 *__my_free_list = __result -> _M_free_list_link; // 这时候是要把__result分配出去 __ret = __result; } } return __ret; };

五、分配内存池_S_refill源码分析

作用： 根据__n，在_S_free_list对应位置构造内存池，并且把第一个__chunk块分配出去，并填写剩下所有__chunk块的next域

template void* __default_alloc_template<__threads, __inst>::_S_refill(size_t __n){ int __nobjs = 20; // 局部变量，内存池中开辟__chunk 块的数量 char* __chunk = _S_chunk_alloc(__n, __nobjs); // 在内存池申请__n字节的空间 _Obj* __STL_VOLATILE* __my_free_list; // 二级指针，遍历_S_free_list数组 _Obj* __result; _Obj* __current_obj; _Obj* __next_obj; int __i; // 当内存池最多只能包含1个__n的块的时候，直接返回，不需要进入for循环再填写next域 if (1 == __nobjs) return(__chunk); // _S_freelist_index(__n)返回的是分配的__n字节在_S_free_list的哪个块中分配 // __my_free_list 指向分配__n字节的块 __my_free_list = _S_free_list + _S_freelist_index(__n); /* Build free list in chunk */ // 指向待分配出去的内存块 __result = (_Obj*)__chunk; // __chunk 是char*，实际上+__n就是越过了一个块，指向了第二个块的起始地址 // __next_obj 和*__my_free_list 都指向第二个块 *__my_free_list = __next_obj = (_Obj*)(__chunk + __n); // i从1开始，表示__current_obj 一开始就指向第二个__chunk块 // 整个for循环做的就是把内存是填写剩下所有__chunk块的next域 for (__i = 1; ; __i++) { __current_obj = __next_obj; __next_obj = (_Obj*)((char*)__next_obj + __n); if (__nobjs - 1 == __i) { // next域填写完成，最后一个__chunk块的next域为0地址 __current_obj -> _M_free_list_link = 0; break; } else { __current_obj -> _M_free_list_link = __next_obj; } } return(__result);}

六、实际分配内存池_S_chunk_alloc源码分析

有一个疑问：为什么其他申请的16B的内存可以在_S_free_list 的8B的内存池申请 后来我懂了，源码中用 static char* _S_end_free、_S_start_free变量，标识备用内存池的范围。也就是不管分配多少字节的内存，都是在_S_start_free和_S_end_free区间内给用户分配。_S_free_list的每个元素都是一个指针，保存的是专门为分配对应字节的一大块内存空闲位置的起始地址

再到备用内存给用户分配size字节的时候：

若剩余的内存还够​​20*size​​​个字节，则直接分出去​​20*size​​​专门用来分配​​size​​​字节，既然是专门分配​​size​​​的内存区域，这个区域需要在​​_S_refill​​函数中填写next域若不够分配​​20*size​​​个字节，但是够分配​​size​​​个字节，那将备用的内存尽可能多的分割出完整的​​size​​​内存块。此时也需要在​​_S_refill​​​函数中填写next域，然而当备用内存只能分割出一个​​size​​内存块时，就不用再填写地址域了。其实也没有办法再填写了，因为没内存了。若实在太小，连一个​​size​​内存块也分配不出来。剩余的备用内存就会根据自身的大小被挂在_S_free_list 的对应位置，然后需要重新找OS申请新的内存。向OS申请成功则分配，向OS申请失败则在_S_free_list挂着的内存池分出一个块作为空闲空间，然后再回到之前的分配流程。

进入if中：

进入else中：

template char*__default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size, int& __nobjs){ char* __result; // 实际分配的字节数，8 * 20 size_t __total_bytes = __size * __nobjs; //_S_end_free、_S_start_free都是static char*变量，标识备用内存池的范围，初始值为0 // _S_start_free、_S_end_free分别记录内存池（__size * __nobjs）可用的起始和末尾地址 size_t __bytes_left = _S_end_free - _S_start_free; if (__bytes_left >= __total_bytes) { // 正常的__size在对应的内存池分配，备用的内存池还可以继续分配__size * __nobjs // 可以分配出去一个小的内存池 __result = _S_start_free; // 修改_S_start_free，分配__total_bytes空间出去 _S_start_free += __total_bytes; return(__result); } else if (__bytes_left >= __size) { // 假设我们向内存池申请16字节的时候，我们在_S_free_list向OS申请8字节时备用的内存池进行申请 // 此时会进入else if // 剩余的字节数还能分配出__nobjs个完整的__size的__chunk块 __nobjs = (int)(__bytes_left/__size); // 现在的__total_bytes 肯定不大于 _S_end_free - _S_start_free __total_bytes = __size * __nobjs; // __result 指向空闲内存池的首地址，也就是即将被分配出去的首地址 __result = _S_start_free; // 更新空闲内存池的首地址 _S_start_free += __total_bytes; return(__result); } else { // 没有足够的空间分配了 或者_S_free_list还没有申请过内存池 ，需要申请内存 // _S_heap_siz初始值为0，第一次向OS申请的话__bytes_to_get = 8 * 20 = 320， // _S_heap_size记录了已经向OS申请的所有空间 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) { // 由于之前申请的备用内存太小，甚至无法分出一个size // 这里剩余的内存必然为8的整数倍，且在区间[8,128)内。因为从OS申请空间的时候就是按照8的整数申请的 // 之前申请的备用内存，会被挂在__my_free_list后，专门用于分配指定大小的内存 // 而且只能分配 <指定大小的内存> 一次 _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; } // 用malloc申请__bytes_to_get个字节，也就是一个小的内存池了，_S_start_free 指向小内存池的首地址 _S_start_free = (char*)malloc(__bytes_to_get); if (0 == _S_start_free) { // 向OS申请内存失败 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. // 1. 剩余的备用内存连一个__size的空间都不够，2. 向OS申请__bytes_to_get字节内存失败 // 从__size开始在_S_free_list中从前往后找 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) { // 找到_S_free_list中已经分配内存池的位置 // 修改_S_free_list的对应位置的地址，准备分配出一整个__i块出去 *__my_free_list = __p -> _M_free_list_link; // 在_S_free_list别的地方拿到未分配的内存块后，修改_S_start_free、_S_end_free // 得到新的备用内存，重新给用户分配__nobjs个__size的空间 _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. } } // 若for循环完成，依然找不到空闲的内存块 _S_end_free = 0; // In case of exception. // 重新再次申请__bytes_to_get字节 _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 记录分配的空间大小 _S_heap_size += __bytes_to_get; // _S_end_free 指向空闲小内存池的尾地址 _S_end_free = _S_start_free + __bytes_to_get; // return(_S_chunk_alloc(__size, __nobjs)); }}

malloc_alloc::allocate源码

#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUGtemplate // 可以设置一个回调函数，当OS开辟内存失败的时候，调用此函数。// 此函数可能用于释放某些可以释放的资源void (* __malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0;#endiftemplate 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); }}static void* malloc_alloc::allocate(size_t __n){ // 先尝试一下正常向OS申请空间 void* __result = malloc(__n); // 正常向OS申请空间失败，调用_S_oom_malloc if (0 == __result) __result = _S_oom_malloc(__n); return __result;}

七、内存归还dealloacte

归还分配出去的__chunk块，并修改_S_free_list对应的元素（保存当前还未分配出去__chunk块的首地址），以及归还的__chunk块的next域

// 归还__p指向的__n字节内存空间到内存池static void deallocate(void* __p, size_t __n){ if (__n > (size_t) _MAX_BYTES) malloc_alloc::deallocate(__p, __n); else { // _S_freelist_index(__n):获取__n字节在_S_free_list中哪个小的内存池分配的 // __my_free_list 指向小内存池的起始地址 _Obj* __STL_VOLATILE* __my_free_list = _S_free_list + _S_freelist_index(__n); // __q指向要归还的__chunk块 _Obj* __q = (_Obj*)__p; #ifndef _NOTHREADS _Lock __lock_instance; #endif // 即将归还__chunk块的next被赋值成当前还未分配出去__chunk块的首地址 __q -> _M_free_list_link = *__my_free_list; // 修改_S_free_list的元素，即修改了当前还未分配出去__chunk块的首地址 *__my_free_list = __q; }}

八、reallocate

作用： 对内存池中的__chuck块进行扩容或缩容，一般用的比较少

template void* __default_alloc_template::reallocate(void* __p, size_t __old_sz, size_t __new_sz){ // 参数:chunk块的其实地址、调整前chunk块的大小、调整后chunk块的大小 void* __result; size_t __copy_sz; if (__old_sz > (size_t) _MAX_BYTES && __new_sz > (size_t) _MAX_BYTES) { // __old_sz和__new_sz都大于128字节，并不是从内存池分配的内存，直接调用库函数realloc return(realloc(__p, __new_sz)); } // __old_sz和__new_sz处于同一数量区间，不用扩容或缩容 if (_S_round_up(__old_sz) == _S_round_up(__new_sz)) return(__p); // __result指向重新分配的空间 __result = allocate(__new_sz); // __copy_sz 保存最小值 __copy_sz = __new_sz > __old_sz? __old_sz : __new_sz; // 从__p拷贝到__result，扩容拷贝__old_sz字节，缩容拷贝__new_sz memcpy(__result, __p, __copy_sz); // 归还原来的chunk块到内存池 deallocate(__p, __old_sz); return(__result);}

九、总结

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

对于每一个字节数的chunk块分配，都是给出一部分进行使用，另一部分作为备用，这个备用可以给当前字节数使用，也可以给其它字节数使用对于备用内存池划分完chunk块以后，如果还有剩余的很小的内存块，再次分配的时候，会把这些小的内存块挂到_S_free_list的对应位置，再次分配出去，备用内存池使用的干干净净！当指定字节数内存分配失败以后，有一个异常处理的过程，__size -> 128字节所有的chunk块进行查看，如果哪个字节数有空闲的chunk块，直接借一个出去。如果上面操作失败，还会调用_S_oom_malloc，其内部有一个预先设置好的malloc内存分配失败的回调函数，若分配不成功则会不停地调用次回调函数释放空间。若没设置回调函数，则直接malloc throw bad_alloc。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。