C++ STL:空间配置器源码解析

简介: C++ STL:空间配置器源码解析

Part 6:空间配置器

背景:频繁使用 malloc 分配内存的造成的问题:

  • 系统调用,系统开销较大
  • 产生大量的内存碎片(外部碎片)。

注:内存碎片

  • 内部碎片:页式管理、段式管理、段页式管理,无法避免,可以通过算法优化。
  • 外部碎片:申请堆空间之间的片段空隙,空间配置器优化的是外部碎片。

因此,引入空间配置器 allocator。可以感知类型的空间分配器,用于分配和释放内存,将内存的分配释放与对象的创建销毁分开。

1、allocator 接口层

1.1、接口层源码

针对容器来说,空间的分配 construct 与对象的创建 allocate 是分开的,并不是绑定在一起。提供的接口如下:

// 1、空间分配
 // 1.1、申请未初始化的空间
 pointer allocate( size_type n, const void * hint = 0 );
 T* allocate( std::size_t n, const void * hint);
 T* allocate( std::size_t n );
 // 1.2、释放空间
 void deallocate( T* p, std::size_t n );
 // 2、对象创建
 // 2.1、对象的构建。
 void construct( pointer p, const_reference val );
 // 2.2、对象的销毁
 void destroy( pointer p );

源码位于stl_alloc.h,接口层的源码如下:

// 空间配置器的接口层
 template <class _Tp>
 class allocator {
     typedef alloc _Alloc;
     _Tp* allocate(size_type __n, const void* = 0) {
         return __n != 0 ? static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp))) : 0;
     }
     void deallocate(pointer __p, size_type __n)
     { _Alloc::deallocate(__p, __n * sizeof(_Tp)); }
     void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
     void destroy(pointer __p) { __p->~_Tp(); }
 };

1.2、定位 new 表达式

定位 new 表达式:在 p 指向的未初始化的内存中构造 T 类型对象。

void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }

1.3、实例

例:使用std::allocator实现自定义的Vector

vector 模型

Vector模型
 ______________________________
 |_|_|_|_|_|____________________|
 ↑          ↑                    ↑
 _start   _finish            _end_of_storage

接口形式:

template<typename T>
 class Vector
 {
 public:
     Vector();
     ~Vector();
     void push_back(const T &); 
     void pop_back();    
     int size();
     int capacity();
 private:
     void reallocate();//重新分配内存,动态扩容要用的
 private:    
     static std::allocator<T> _alloc;
     T *_start;                 // 指向数组中的第一个元素
     T *_finish;                // 指向最后一个实际元素之后的那个元素
     T *_end_of_storage;        // 指向数组本身之后的位置
 };

实现代码:

#include <algorithm>
 #include <iostream>
 #include <memory>
 using std::cout;
 using std::endl;
 template<typename T>
 class Vector {
 public:
     Vector()
     : _start(nullptr)
     , _finish(nullptr)
     , _end_of_storage(nullptr)
     {}
     ~Vector();
     void push_back(const T &); 
     void pop_back();    
     int size() const {  return _finish - _start;    }
     int capacity() const {  return _end_of_storage - _start;    }
     // 定义迭代器
     typedef T * iterator;
     typedef const T * const_iterator;
     const_iterator begin() const { return _start; }
     const_iterator end() const { return _finish; }
 private:
     void reallocate(); // 重新分配内存,动态扩容
 private:
     // 定义空间配置器,静态共享 
     static std::allocator<T> _alloc;
     T *_start;                 //指向数组中的第一个元素
     T *_finish;                //指向最后一个实际元素之后的那个元素
     T *_end_of_storage;        //指向数组本身之后的位置
 };
 // 初始化 allocator
 template <class T>
 std::allocator<T> Vector<T>::_alloc;
 template <typename T>
 void Vector<T>::push_back(const T & t)
 {
     // 数组扩容
     if(size() == capacity()) {
         reallocate();
     }
     // 在 finish 所指位置构造对象
     if(size() < capacity()) {
         _alloc.construct(_finish++, t);
     }
 }
 template <typename T>
 void Vector<T>::pop_back()    
 {
     if(size() > 0) {
         _alloc.destroy(--_finish);
     }
 }
 template <typename  T>
 Vector<T>::~Vector()
 {
     // 1. 先析构对象
     while(_finish != _start) {
         _alloc.destroy(--_finish);
     }
     // 2. 回收空间
     if(_start) {
         _alloc.deallocate(_start, capacity());
     }
 }
 template <typename T>
 void Vector<T>::reallocate() // 重新分配内存,动态扩容
 {
     // 当 size == capacity,需要动态扩容
     int oldCapacity = capacity();
     int newCapacity = (oldCapacity == 0 ? 1 : 2 * oldCapacity); // 2 倍扩容
     // 1、开辟新的空间
     T * ptmp = _alloc.allocate(newCapacity);
     if(_start) {
         // 2、将原来空间上的对象复制到新空间
          // 新开辟的空间上没有对象,无法使用 copy, memcpy 等算法
         std::uninitialized_copy(_start, _finish, ptmp);
          // 3、释放原来的空间
         // 3.1、销毁原来空间上的对象
         while(_finish != _start) {
             _alloc.destroy(--_finish);
         }
         // 3.2、释放原来的空间
         _alloc.deallocate(_start, oldCapacity);
     }
     // 5. 重置3个指针, 指向新的空间
     _start = ptmp;
     _finish = _start + oldCapacity;
     _end_of_storage = _start + newCapacity;
 }
 template <class Container>
 void print(const Container & c)
 {
     // for 循环需要迭代器,自定义 vector 需要提供迭代器
      for( auto & elem : c) {
         cout << elem << " ";
      }
      cout << endl;
 }
 void test0 () {
     Vector<int> vec;
     vec.push_back(1);
     cout << "vec's size:" << vec.size() << endl;
     cout << "vec's capa:" << vec.capacity() << endl;
     vec.push_back(2);
     cout << "vec's size:" << vec.size() << endl;
     cout << "vec's capa:" << vec.capacity() << endl;
     vec.push_back(3);
     cout << "vec's size:" << vec.size() << endl;
     cout << "vec's capa:" << vec.capacity() << endl;
     vec.push_back(4);
     cout << "vec's size:" << vec.size() << endl;
     cout << "vec's capa:" << vec.capacity() << endl;
     vec.push_back(5);
     cout << "vec's size:" << vec.size() << endl;
     cout << "vec's capa:" << vec.capacity() << endl;
     print(vec);
 }
 int main(void) {
     test0();
     return 0;
 }

2、allocator 实现层

真正进行分配空间的是std::alloc,见源码:

template <class _Tp>
 class allocator {
     typedef alloc _Alloc;
     _Tp* allocate(size_type __n, const void* = 0) {
         return __n != 0 ? static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp))) : 0;
     }
 };

使用两级空间配置器。在分配空间的时候,若申请的空间大小:

  • 大于 128 字节,调用一级配置器,使用 malloc / free
  • 小于等于 128 字节,调用二级配置器(默认空间配置器),使用内存池 + 16个自由链表。
// 空间配置器的实现层
 // 1、一级配置器,使用 malloc 进行空间分配
 # ifdef __USE_MALLOC 
 typedef malloc_alloc alloc;
 // 2、二级配置器,默认的空间分配器,使用内存 + 16个自由链表
 # else              
 typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
 # endif

2.1、一级空间配置器

对于大块内存(大于 128 字节),第一级空间配置器使用 malloc / free 分配和释放内存,对应的源码:

// 一级空间配置器(对 malloc/free 的封装)
 template <int __inst>
 class __malloc_alloc_template {
 public:
   // allocate 接口:封装 malloc
   static void* allocate(size_t __n)
   {
     void* __result = malloc(__n);
     if (0 == __result) __result = _S_oom_malloc(__n);
     return __result;
   }
   // deallocate 接口:封装 free
   static void deallocate(void* __p, size_t /* __n */)
   {
     free(__p);
   }
   ...
 };
 // 定义 alloc 类
 typedef __malloc_alloc_template<0> malloc_alloc
 typedef malloc_alloc alloc

2.2、二级空间配置器

默认空间配置器,所有的容器最终调用它完成空间的分配和释放。由内存池 + 16 个自由空闲链表组成。

简单来说,allocator根据用户申请的空间大小(8 的整数倍,向上取整),先向堆申请大块内存,然后拿出其中一部分将其分割成固定大小的内存块,并组织成空闲链表;另一部分作为内存池备用。此后,每次申请内存先向空闲链表申请空间,对应的空闲链表不存在则向内存池申请空间,否则向堆申请大块内存。

二级空间配置器源码部分如下:

typedef __default_alloc_template alloc
 template <bool threads, int inst>
 class __default_alloc_template {   
 public:
     static void* allocate(size_t __n);
     static void deallocate(void* __p, size_t __n)
 private:
     // 内存分配
     // 1、填充自由空闲链表
     static void* _S_refill(size_t __n);
     // 2、申请内存
     static char* _S_chunk_alloc(size_t __size, int& __nobjs);
     // 通过申请的字节数,得到自由空闲链表的下标
     // 例如申请 25~32 个字节,对应的链表下标就是 3
     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)); }
 private:
     enum {_ALIGN = 8};
     enum {_MAX_BYTES = 128};
     enum {_NFREELISTS = 16}; 
     // 链表结点(指针)
     union _Obj {
         union _Obj* _M_free_list_link;
         char _M_client_data[1];
     };
     // 16 个自由空闲链表
     static _Obj* _S_free_list[_NFREELISTS]; 
     // 内存池,一次申请大空间,之后只需要在内存池上进行切割
     static char* _S_start_free;  // 内存池的起始位置
     static char* _S_end_free;    // 内存池的结束位置
     static size_t _S_heap_size;  // 16个自由空闲链表 + 内存池,即堆上申请的总空间
 };

allocate

static void* allocate(size_t __n) // __n 要申请的字节数
 {
     void* __ret = 0;
     // 1、当__n > 128 字节时,使用一级空间配置器完成空间的申请
     if (__n > (size_t) _MAX_BYTES) {
         __ret = malloc_alloc::allocate(__n);
     }
     // 2、当 __n <= 128 字节时,使用二级空间配置器完成空间的申请
     else {
         // 通过 __n 的值获取对应的到自由的空闲链表。
         // _S_freelist_index 函数根据 __n 的值获得链表下标
         _Obj** __my_free_list = _S_free_list + _S_freelist_index(__n);
         _Obj* __result = *__my_free_list;
         // 第一次申请 __n 空间,链表结点地址是 0,堆上还未申请这条自由链表
         if (__result == 0)
             // 从堆空间中去找内存块,填充该自由空闲链表。
             // _S_round_up 函数申请的空间大小向上取整,是 8 的倍数
             __ret = _S_refill(_S_round_up(__n));
         else {
             // 当再次申请 __n 空间,直接从已经申请的链表头部取下链表结点,时间复杂度 O(1)
             *__my_free_list = __result -> _M_free_list_link;
             __ret = __result;
         }
     }
     return __ret;
 }

空间分配的核心函数在于:_S_refill_S_chunk_alloc函数

_S_refill函数:填充__nobjs个结点大小为 __n的自由空闲链表。其中__nobjs默认是 20,若内存池不够分割,则重新计算。

// _S_refill 函数:填充自由空闲链表
 template <bool __threads, int __inst>
 void*
 __default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
 {
     int __nobjs = 20;
     // 申请 20 个 __n 字节大小的大块内存
     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);
     // 根据 __n 获取对应的空闲链表下标
     __my_free_list = _S_free_list + _S_freelist_index(__n);
     /* Build free list in chunk */
     // 将申请的大块内存 chunk 切分 __nobjs 个空间大小为 __n 的链表结点,并组织成一条自由空闲链表
     __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);
 }

_S_chunk_alloc函数:申请空间。比较内存池剩余空间与本次申请的内存空间大小:

  • 内存池剩余空间足够,则内存池一次分配相应大小的内存
  • 内存池剩余空间不足,则判断剩余空间能否分割,若不能分割,则向堆上申请大块内存
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;
     // 1、内存池剩余空间大小 > 本次申请的内存块大小,
     // 给它一次分配本次要申请的内存块大小
     if (__bytes_left >= __total_bytes) {
         __result = _S_start_free;
         _S_start_free += __total_bytes;
         return(__result);
     } 
     // 2、内存池剩余空间大小 < 本次申请的内存块大小,则判断内存池剩余空间大小是否足够分割
     // 2.1、内存池剩余空间够分割,将内存池剩余空间分割成固定大小的内存块(用户指定大小__size )
     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);
     } 
     // 3、剩余的堆空间不够切分:__bytes_left = 0 < __size
     // 重新向堆上申请空间
     else {
         // 计算需要申请的空间大小
         size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
         // 内存池开始申请空间
         _S_start_free = (char*)malloc(__bytes_to_get);
         _S_heap_size += __bytes_to_get;
         _S_end_free = _S_start_free + __bytes_to_get;
         // 递归调用
         return(_S_chunk_alloc(__size, __nobjs));
     }
 }

deallocate

  • 回收的空间大于 128 字节,直接使用 free 回收空间
  • 回收的空间小于等于 128 字节,直接链回自由空闲链表
static void deallocate(void* __p, size_t __n)
 {
     // 回收的空间大于 128 字节,直接使用 free 回收空间 
     if (__n > (size_t) _MAX_BYTES)
         malloc_alloc::deallocate(__p, __n);
     // 回收的空间小于等于 128 字节,采用链表头插法,将空闲链表结点重新挂回到空闲链表
     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;
     }
 }

源码流程分析

第一次申请 32 字节的空间

// 1、调用 _S_refill 函数
     int __nobjs = 20;
     // 向 _S_chunk_alloc 申请 20 * 32 = 640 空间
     char* __chunk = _S_chunk_alloc(__n, __nobjs);
 // 2、调用 _S_chunk_alloc 函数
     size_t __total_bytes = __size * __nobjs;          // __total_bytes = 32 * 20 = 640
     size_t __bytes_left = _S_end_free - _S_start_free; // __bytes_left = 0
 // 第一次申请空间 __bytes_left = 0 < __size
 else {
     // __bytes_to_get = 2 * 640 + 0 = 1280
     size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
     // 向内存池申请 1280 个字节的空间
     _S_start_free = (char*)malloc(__bytes_to_get);
     // _S_heap_size = 1280
     _S_heap_size += __bytes_to_get;     
     // _S_end_free = 1280
     _S_end_free = _S_start_free + __bytes_to_get; 
     // 递归调用自身
     return(_S_chunk_alloc(__size, __nobjs));
 }
 // 3、递归调用 _S_chunk_alloc 函数
 char* __result;
 size_t __total_bytes = __size * __nobjs;          // 32 * 20 = 640;
 size_t __bytes_left = _S_end_free - _S_start_free; // 1280 - 0 = 1280;
 // 1280 > 640
 if (__bytes_left >= __total_bytes) {
     __result = _S_start_free;       // __result = 640
     _S_start_free += __total_bytes;  // _S_start_free = 640
     return(__result);
 } 
 // 5、返回 _S_refill 函数
       __result = (_Obj*)__chunk;
       *__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
       // 将 640 空间大小切分成 20 个空间大小为 32 字节的链表结点,并组织成一条链表 
       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);

如图所示,可以看到 stl::allocator 内存空间消耗较大,只需要一个 32 字节的空间,就一次性申请了 1280 个字节,此时 640 字节的空间作为空闲链表,640 空间作为内存池备用。

第二次申请 64 字节的空间

// 1、调用 _S_refill 函数
     int __nobjs = 20;
     // 向 _S_chunk_alloc 申请 20 * 64 = 1280 空间
     char* __chunk = _S_chunk_alloc(__n, __nobjs);
 // 2、调用 _S_chunk_alloc 函数
     size_t __total_bytes = __size * __nobjs;          // __total_bytes = 64 * 20 = 1280
     size_t __bytes_left = _S_end_free - _S_start_free; // __bytes_left = 1280 - 640 = 640
     // __bytes_left: 640 > __size: 64
     else if (__bytes_left >= __size) {
         // 剩余空间可以被分割为 640 / 64 = 10 个节点
         __nobjs = (int)(__bytes_left/__size); 
         __total_bytes = __size * __nobjs;
         __result = _S_start_free;
         _S_start_free += __total_bytes;
         return(__result);
     }
 // 3、返回 _S_refill 函数
       __result = (_Obj*)__chunk;
       *__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
       // 将 640 空间大小切分成 10 个空间大小为 64 字节的链表结点,并组织成一条链表 
       // 此时申请的堆空间全部分配完毕
       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);

如图所示,内存池全部用于分配内存,申请的堆空间耗尽。生成的空闲链表,分配一个 64 字节的结点,剩余 9 个结点。

第三次申请 96 字节的空间

// 1、调用 _S_refill 函数
     int __nobjs = 20;
     // 向 _S_chunk_alloc 申请 96 * 20 = 1920 空间
     char* __chunk = _S_chunk_alloc(__n, __nobjs);
 // 2、调用 _S_chunk_alloc 函数
     size_t __total_bytes = __size * __nobjs;          // __total_bytes = 96 * 20 = 1920
     size_t __bytes_left = _S_end_free - _S_start_free; // __bytes_left = 0
 // 第一次申请空间 __bytes_left = 0 < __size
 else {
     // __bytes_to_get = 2 * 1920 + 80 = 3920
     size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
     // 向内存池申请 3920 个字节的空间
     _S_start_free = (char*)malloc(__bytes_to_get);
     // _S_heap_size = 1280 + 3920 = 5200 
     _S_heap_size += __bytes_to_get;     
     _S_end_free = _S_start_free + __bytes_to_get; 
     // 递归调用自身
     return(_S_chunk_alloc(__size, __nobjs));
 }
 // 3、递归调用 _S_chunk_alloc 函数
 char* __result;
 size_t __total_bytes = __size * __nobjs;          // 96 * 20 = 1920;
 size_t __bytes_left = _S_end_free - _S_start_free; // 3920;
 // 3920 > 1920
 if (__bytes_left >= __total_bytes) {
     __result = _S_start_free;       
     _S_start_free += __total_bytes; 
     return(__result);
 } 
 // 5、返回 _S_refill 函数
       __result = (_Obj*)__chunk;
       *__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
       // 将 1920 空间大小切分成 20 个空间大小为 96 字节的链表结点,并组织成一条链表 
       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);

第四次申请 72 字节的空间,堆空间耗尽,内存池耗尽

向后面大于 72 字节的链表借用结点,例如 96,将其分割为 24 + 72。

if (0 == _S_start_free) {
     size_t __i;
     _Obj* __STL_VOLATILE* __my_free_list;
     _Obj* __p;
     // if (i = 72; i <= 128; i += 8)
     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;
         // 找到了链表结点(96 > 72)
         // 将该 96 字节的结点分配给它
         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));
         }
     }

3、allocator 问题

内存空间消耗比较大,内存不可控。如果硬件的性能不支持,例如嵌入式系统,则不能使用 std::allocator做内存的分配。

相关文章

热门文章

最新文章

推荐镜像

更多