C++ STL源码个人学习与分析记录 ——空间配置器（allocator）

STL源码个人学习与分析记录 ——空间配置器（allocator）

• 1. 为什么需要空间配置器？
• 2. SGI-STL空间配置器的实现
• • 2.1 一级空间配置器：malloc_alloc_template
  • 2.2 二级空间配置器：default_alloc_template
  • • 2.2.1 .内存池技术
    • 2.2.2 .自由链表（free-list）
    • 2.2.3 Union
  • 2.3 二级空间配置器的具体实现
  • • 2.3.1 空间配置函数 allocate（）
    • 2.3.2 空间配置函数 deallocate（）
    • 2.3.3 其他函数

  上一篇博客中浅浅分析了一下GCC编译器中的关于对象的析构与构建的基本工具Construct（）与Destory（）的定义，并比较了与SGI STL之间具体实现的区别(文章链接)。接下来就是最重要的一块内容，即负责对象构造前和析构后的空间配置与空间释放的工具——空间配置器

1. 为什么需要空间配置器？

  正如上述方框中加粗字体所述的那样，空间配置器主要用来完成对象构建与析构前后的一些空间准备工作。同样的工作可以通过直接调用new来进行内存空间的申请或者调用delete来实现内存的释放，为何还需要使用空间配置器这个工具呢？原因我个人认为有以下几点：

• 1）. 根据墨菲定律，任何事务只要存在出现错误的可能，即使几率再低那它也必然会发生。如果希望用户自己去申请和释放内存空间来存储容器，那么用户很有可能忘记使用结束之后释放内存，造成内存泄漏。
• 2）.内存碎片与效率问题：向系统多次申请体积较小的内存块，容易造成内存碎片化，不容易管理和解决。其次，频繁向系统申请内存也会降低程序运行效率。
• 3）.使用malloc（）申请内存失败了怎么办？
• 4）.多线程安全问题。

2. SGI-STL空间配置器的实现

  为了尽可能地避免申请小区块内存所导致的内存碎片问题，SGI-STL空间配置器采用了两级空间配置器的设计方案，并以配置区块为128 Bytes为界限，决定调用一级空间配置器或者二级空间配置器。

2.1 一级空间配置器：malloc_alloc_template

  SGI-STL的一级空间配置器十分简单，仅仅是对malloc（）函数与free（）函数的调用，当然，对这俩个函数做了一定的封装处理。除此之外，SGI-STL还提供了一种用于模范C++的set_new_handler()手法的函数：set_malloc_oom_handler（）。

	 static void (* set_malloc_handler(void (*f)()))()
	 {
		 void (* old)() = __malloc_alloc_oom_handler; //此处的__malloc_alloc_oom_handler是一个静态函数指针
		 __malloc_alloc_oom_handler = f;//使得__malloc_alloc_oom_handler指向f所指向的自定义处理内存不足的函数
		 return(old);
	}
//至于真正用于处理内存不足情况的函数oom_malloc()与oom_realloc()，书中已经讲述的十分详细，此处就不再赘述了。

  SGI-STL中将该一级空间配置器定义在了<stl_alloc.h>文件之中。而在GCC编译器中，使用malloc（）与free（）函数的配置器是存在的，它定义在了<malloc_allocator.h>文件中（相对位置为：…\MinGW\include\c++\13.2.0\ext）。以下是该配置器的部分定义：

namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

  /**
   *  @brief  An allocator that uses malloc.
   *  @ingroup allocators
   *
   *  This is precisely the allocator defined in the C++ Standard. 
   *    - all allocation calls malloc
   *    - all deallocation calls free
   */
  template<typename _Tp>
    class malloc_allocator
    {
    public:
    //此处利用typedef定义一系列的类型别名，主要是用于traits编程，用于在编译器期间便能确定调用那个重载的算法，等等
      typedef _Tp        value_type;
      typedef std::size_t     size_type;
      typedef std::ptrdiff_t  difference_type;
#if __cplusplus <= 201703L
      typedef _Tp*       pointer;
      typedef const _Tp* const_pointer;
      typedef _Tp&       reference;
      typedef const _Tp& const_reference;

      template<typename _Tp1>
        struct rebind
        { typedef malloc_allocator<_Tp1> other; };
#endif

#if __cplusplus >= 201103L
      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 2103. propagate_on_container_move_assignment
      typedef std::true_type propagate_on_container_move_assignment;
#endif
//定义了一系列的构造函数
      _GLIBCXX20_CONSTEXPR
      malloc_allocator() _GLIBCXX_USE_NOEXCEPT { }

      _GLIBCXX20_CONSTEXPR
      malloc_allocator(const malloc_allocator&) _GLIBCXX_USE_NOEXCEPT { }

      template<typename _Tp1>
	_GLIBCXX20_CONSTEXPR
        malloc_allocator(const malloc_allocator<_Tp1>&)
	_GLIBCXX_USE_NOEXCEPT { }
//定义了析构函数
#if __cplusplus <= 201703L
      ~malloc_allocator() _GLIBCXX_USE_NOEXCEPT { }
//定义了两个用于取出参数__x的地址的函数，针对__x的引用对象是否是常量重载了一下函数。
      pointer
      address(reference __x) const _GLIBCXX_NOEXCEPT
      { return std::__addressof(__x); }

      const_pointer
      address(const_reference __x) const _GLIBCXX_NOEXCEPT
      { return std::__addressof(__x); }
#endif


//接下来便是最关心的地方，allocate（）的定义
      // NB: __n is permitted to be 0.  The C++ standard says nothing
      // about what the return value is when __n == 0.
      _GLIBCXX_NODISCARD _Tp*
      allocate(size_type __n, const void* = 0)
      {
#if __cplusplus >= 201103L
	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	// 3308. std::allocator<void>().allocate(n)
	static_assert(sizeof(_Tp) != 0, "cannot allocate incomplete types"); //首先检查被分配对象是否拥有完整定义
#endif

	if (__builtin_expect(__n > this->_M_max_size(), false)) //检查所需分配对象的数量__n是否超过上限,_M_max_size()的定义在最下方
	  {
	    // _GLIBCXX_RESOLVE_LIB_DEFECTS
	    // 3190. allocator::allocate sometimes returns too little storage
	    if (__n > (std::size_t(-1) / sizeof(_Tp)))
	      std::__throw_bad_array_new_length();
	    std::__throw_bad_alloc();
	  }

	_Tp* __ret = 0; //定义了指针__ret,它指向所分配空间的起始位置，也就是该allocate（）函数的返回对象
#if __cpp_aligned_new
#if __cplusplus > 201402L && _GLIBCXX_HAVE_ALIGNED_ALLOC //GCC编译器中并未定义_GLIBCXX_HAVE_ALIGNED_ALLOC该组态，所以该if else范围内的代码不会运行
	if (alignof(_Tp) > alignof(std::max_align_t))
	  {
	    __ret = static_cast<_Tp*>(::aligned_alloc(alignof(_Tp),
						      __n * sizeof(_Tp)));
	  }
#else
# define _GLIBCXX_CHECK_MALLOC_RESULT
#endif
#endif
	if (!__ret) //如果没有使用上面的全局函数aligned_alloc（）进行内存申请，那么就使用malloc()函数完成相同操作
	  __ret = static_cast<_Tp*>(std::malloc(__n * sizeof(_Tp)));
	if (!__ret) 
	  std::__throw_bad_alloc();
//如果__ret == nullptr，说明没有申请到内存，那么就只能报错。
//此处与SGI_STL的allocate版本不同，它并未提供一个接口供给用户来自定义handler来处理异常情况。
#ifdef _GLIBCXX_CHECK_MALLOC_RESULT
#undef _GLIBCXX_CHECK_MALLOC_RESULT //字面意思，检查malloc（）返回的结果
	  if (reinterpret_cast<std::size_t>(__ret) % alignof(_Tp)) 
	  //如果取余非0，说明所分配的空间并未很好的与被分配对象对其，alignof（）函数返回对象所需要的最小内存边界大小，
	  //例如int对象的最小内存边界大小为4，因此它所存储的内存空间边界应当是4的倍数。
	    {
	      // Memory returned by malloc is not suitably aligned for _Tp.
	      deallocate(__ret, __n); //申请的内存不符合要求？？那我就直接不要了！！！
	      std::__throw_bad_alloc();
	    }
#endif
	return __ret; //最后返回所分配内存空间的起始地址
      }

      // __p is not permitted to be a null pointer.
      void
      deallocate(_Tp* __p, size_type)
      { std::free(static_cast<void*>(__p)); } 
      //deallocate（）直接调用free进行内存释放，static_cast<>是现代C++的强制类型转换的实现手法，在《effective C++》中也鼓励用户使用static_cast<>，而不是C手法的（typename T）variable。

private:
      _GLIBCXX_CONSTEXPR size_type
      _M_max_size() const _GLIBCXX_USE_NOEXCEPT
      {
#if __PTRDIFF_MAX__ < __SIZE_MAX__
	return std::size_t(__PTRDIFF_MAX__) / sizeof(_Tp);
#else
	return std::size_t(-1) / sizeof(_Tp);
#endif
      }

2.2 二级空间配置器：default_alloc_template

  SGI-STL的二级空间配置器采用了内存池技术和自由链表（free-list）数据结构来实现。当所需要的区块大小超过128 Bytes时，采用上述的一级空间配置器，当区块大小小于128 Bytes时，采用二级空间配置器。

2.2.1 .内存池技术

  程序运行开始后，首先向内存中索要一定大小的内存块作为一种“备用水源”，当用户需要“用水”时，直接向内存池（“水池”）中去取用，当所取用的水（小内存区块）不再需要的时候，直接将水倒还给内存池中，而不是系统内存中。通过这样的设计机制，避免了频繁使用malloc（）和free（）操作向系统申请和退还内存的操作，以及内存碎片问题等等。

2.2.2 .自由链表（free-list）

  内存池中采用的是自由链表实现对内存的管理，从本质上看，自由链表就是哈希桶，每个桶管理着相应尺寸的内存区块。由于用户申请的空间大小基本上都是4的倍数，因此将任何申请的内存区块都上调至8的倍数，因此，总共有16个哈希桶（即16条free-list），各自管理字节数为8,16,24…………128的区块。

  由于哈希桶的每个节点都需要一个指针来指向下一个节点，那意味着是不是需要再设立一个数据成员或者利用其他方法来对链表进行管理？为了解决这个问题，链表中的节点采用的是union，而不是寻常的struct。以下是GCC编译器中对于该Union类型节点的定义（作为二级空间配置的嵌套类型，定义在<pool_allocator.h>中）：

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

  很多人可能就会问了，为什么在此处非要使用union而不使用常见的struct呢？而且这个Union里不也定义了一个指针“_M_free_list_link”么？最开始我也不理解，特地去问了一问ChatGpt关于union的定义,才理解了缘故。

2.2.3 Union

以下是ChatGpt的回答结果：

In C++, a union is a special data structure that allows you to store different types of data in the same memory location. Unlike a struct, where each member has its own storage space, all members of a union share the same memory location. This means that only one member of a union can hold a value at any given time, and the size of the union is determined by the size of its largest member.

特征：

• 1）.共享内存： Union的所有成员共享同一内存位置。向Union中的一个成员写入内容将覆盖其他成员的值。

• 2）.大小： Union的大小即为其最大成员的大小。这是因为Union需要能够存储可能分配给它的最大值。

• 3）.访问成员： 可以访问 union 的任何成员，但是只有最后写入的成员才具有有效值。
  示例代码：

union Example {
    int integerValue;
    float floatValue;
    char charValue;
};

int main() {
    Example example;
    std::cout<<"The size of int: "<<sizeof(int)<<"\nThe size of float: "<<sizeof(float)<<"\nThe size of char: "<<sizeof(char)<<std::endl;
    
    example.integerValue = 42;
    std::cout << "Integer value: " << example.integerValue <<"\tThe current size of this Union is "<<sizeof(example)<< std::endl;
    
    example.floatValue = 3.14f;
    std::cout << "Float value: " << example.floatValue <<"\tThe current size of this Union is "<<sizeof(example)<< std::endl;
    example.charValue = 'A';
    std::cout << "Char value: " << example.charValue <<"\tThe current size of this Union is "<<sizeof(example)<< std::endl;
    
    // Note: At this point, only charValue has a valid value
    std::cout << "Integer value (after char assignment): " << example.integerValue <<"\tThe current size of this Union is "<<sizeof(example)<< std::endl;
    return 0;
}

//输出结果为：
The size of int: 4
The size of float: 4
The size of char: 1
Integer value: 42                                       The current size of this Union is 4
Float value: 3.14                                       The current size of this Union is 4
Char value: A                                           The current size of this Union is 4
Integer value (after char assignment): 1078523201       The current size of this Union is 4

  经过上述的描述和示例代码，应该能够明白此处为什么使用Union了吧？Union在这里起到了“一物二用”的功能。

• 1）.第一用：作为指针，指向同类型的下一个Union实例，此时Union中的_M_free_list_link发挥作用，节点中剩下的内存未被使用。
• 2）.第二用：作为存储节点，存储相应的用户数据，此时Union中的_M_client_data则为用户数据中的第一个字节的数据，即该成员作为用户数据的起始处。

  通过上述的解释，空间配置器使用一种Union结构就可以实现两种功能的内存块，避免为了管理节点之间的指针以及用户元数据而造成不必要的开支，毕竟，C++最为重视的不就是效率与节约么，更不用说在管理底层内存的时候。

2.3 二级空间配置器的具体实现

  GCC编译器中采用内存池技术和自由链表技术的分配器定义在一个名为<pool_allocator.h>的头文件中，其具体位置为：…\MinGW\include\c++\13.2.0\ext的目录中。与SGI-STL不同，GCC编译器对STL容器的实现时设计了两个类，一个为base类，声明或者定义实现一些底层函数等等工作，第二个即为真正投入使用的STL类，并public继承base类，实现对base类定义的函数进行进一步的封装和完善等工作。以下是base类的定义：

    class __pool_alloc_base
    {
      typedef std::size_t size_t;
    protected:

      enum { _S_align = 8 };
      enum { _S_max_bytes = 128 };
      enum { _S_free_list_size = (size_t)_S_max_bytes / (size_t)_S_align };
      
      union _Obj
      {
	union _Obj* _M_free_list_link;
	char        _M_client_data[1];    // The client sees this.
      };
      
      static _Obj* volatile         _S_free_list[_S_free_list_size];

      // Chunk allocation state.
      static char*                  _S_start_free;
      static char*                  _S_end_free;
      static size_t                 _S_heap_size;     
     
      size_t
      _M_round_up(size_t __bytes)
      { return ((__bytes + (size_t)_S_align - 1) & ~((size_t)_S_align - 1)); }
      
      _GLIBCXX_CONST _Obj* volatile*
      _M_get_free_list(size_t __bytes) throw ();
    
      __mutex&
      _M_get_mutex() throw ();

      // Returns an object of size __n, and optionally adds to size __n
      // free list.
      void*
      _M_refill(size_t __n);
      
      // Allocates a chunk for nobjs of size size.  nobjs may be reduced
      // if it is inconvenient to allocate the requested number.
      char*
      _M_allocate_chunk(size_t __n, int& __nobjs);
    };

  观察代码，所定义的枚举类型、static类型变量以及用到的各个函数基本与SGI-STL版本的保持一致，仅仅只是名字上存在一定的变动。因此我也就不再写任何注释啦（偷个懒，哈哈哈），至于那三个比较关键的函数（get_free_list（），_M_refill（）和_M_allocate_chunk（）稍后再来讨论）
  接下来看看GCC编译器中真正的内存池空间配置器的实际定义：

  /**
   * @brief  Allocator using a memory pool with a single lock.
   * @ingroup allocators
   */
  template<typename _Tp>
    class __pool_alloc : private __pool_alloc_base
    {
    //老样子，定义了一系列类型别名，主要用于trait编程
    private:
      static _Atomic_word	    _S_force_new;
    public:
      typedef std::size_t     size_type;
      typedef std::ptrdiff_t  difference_type;
      typedef _Tp*       pointer;
      typedef const _Tp* const_pointer;
      typedef _Tp&       reference;
      typedef const _Tp& const_reference;
      typedef _Tp        value_type;

      template<typename _Tp1>
        struct rebind
        { typedef __pool_alloc<_Tp1> other; };

#if __cplusplus >= 201103L
      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 2103. propagate_on_container_move_assignment
      typedef std::true_type propagate_on_container_move_assignment;
#endif
//定义了一些构造函数
      __pool_alloc() _GLIBCXX_USE_NOEXCEPT { }

      __pool_alloc(const __pool_alloc&) _GLIBCXX_USE_NOEXCEPT { }

      template<typename _Tp1>
        __pool_alloc(const __pool_alloc<_Tp1>&) _GLIBCXX_USE_NOEXCEPT { }
//定义了析构函数
      ~__pool_alloc() _GLIBCXX_USE_NOEXCEPT { }

      pointer
      address(reference __x) const _GLIBCXX_NOEXCEPT
      { return std::__addressof(__x); }

      const_pointer
      address(const_reference __x) const _GLIBCXX_NOEXCEPT
      { return std::__addressof(__x); }

      size_type
      max_size() const _GLIBCXX_USE_NOEXCEPT 
      { return std::size_t(-1) / sizeof(_Tp); }

#if __cplusplus >= 201103L
//自行定义了自己的construct（）函数与destory（）函数，与在<stl_construct.h>中定义的函数的底层机理一致
      template<typename _Up, typename... _Args>
        void
        construct(_Up* __p, _Args&&... __args)
	{ ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }

      template<typename _Up>
        void 
        destroy(_Up* __p) { __p->~_Up(); }
#else
      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 402. wrong new expression in [some_] allocator::construct
      void 
      construct(pointer __p, const _Tp& __val) 
      { ::new((void *)__p) _Tp(__val); }

      void 
      destroy(pointer __p) { __p->~_Tp(); }
#endif
//关键点！！配置内存空间和释放内存空间的核心实现，此处只是提供了声明，真正的定义在类外。
      _GLIBCXX_NODISCARD pointer
      allocate(size_type __n, const void* = 0);

      void
      deallocate(pointer __p, size_type __n);      
    };

2.3.1 空间配置函数 allocate（）

 template<typename _Tp>
    _GLIBCXX_NODISCARD _Tp*
    __pool_alloc<_Tp>::allocate(size_type __n, const void*)
    {
      using std::size_t;
      pointer __ret = 0;
      //惯例，检查所需要分配的区块数是否超过上限
      if (__builtin_expect(__n != 0, true))
	{
	  if (__n > this->max_size())
	    std::__throw_bad_alloc();

	  const size_t __bytes = __n * sizeof(_Tp); //计算所需要分配的总内存大小

#if __cpp_aligned_new
	  if (alignof(_Tp) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)
	    {
	      std::align_val_t __al = std::align_val_t(alignof(_Tp));
	      return static_cast<_Tp*>(::operator new(__bytes, __al));
	    }
#endif
		//这里涉及了多进程之间竞速问题，就先暂时不考虑这个问题了
	  // If there is a race through here, assume answer from getenv
	  // will resolve in same direction.  Inspired by techniques
	  // to efficiently support threading found in basic_string.h.
	  if (_S_force_new == 0)
	    {
	      if (std::getenv("GLIBCXX_FORCE_NEW"))
		__atomic_add_dispatch(&_S_force_new, 1);
	      else
		__atomic_add_dispatch(&_S_force_new, -1);
	    }
	  //如果需要分配的总内存大小超过了128 Bytes，那么直接调用全局new函数进行内存申请，然后将结果赋值给指针__ret.
	  if (__bytes > size_t(_S_max_bytes) || _S_force_new > 0)
	    __ret = static_cast<_Tp*>(::operator new(__bytes));
	  else
	    {
	      _Obj* volatile* __free_list = _M_get_free_list(__bytes); //与SGI-STL不同，_M_get_free_list（）直接返回区块大小最合适的哈希桶的头节点
	      
	      __scoped_lock sentry(_M_get_mutex()); //进程锁
	      _Obj* __restrict__ __result = *__free_list;
	      if (__builtin_expect(__result == 0, 0)) //若返回结果为nullptr，说明对应的哈希桶没有空的区块了，只能refill（重新填充了）
		__ret = static_cast<_Tp*>(_M_refill(_M_round_up(__bytes)));
	      else
		{
		//兄弟们，要到饭了！！！之后需要对该哈希桶进行适当调整
		  *__free_list = __result->_M_free_list_link;
		  __ret = reinterpret_cast<_Tp*>(__result);
		}
	      if (__ret == 0)
		std::__throw_bad_alloc();
	    }
	}
      return __ret;
    }

2.3.2 空间配置函数 deallocate（）

  template<typename _Tp>
    void
    __pool_alloc<_Tp>::deallocate(pointer __p, size_type __n)
    {
      using std::size_t;
      if (__builtin_expect(__n != 0 && __p != 0, true))
	{
#if __cpp_aligned_new
	  if (alignof(_Tp) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)
	    {
	      ::operator delete(__p, std::align_val_t(alignof(_Tp)));
	      return;
	    }
#endif
	  const size_t __bytes = __n * sizeof(_Tp);
	  //如果所分配的区块字节数大于128 Bytes，则直接调用全局delete函数进行内存释放。
	  if (__bytes > static_cast<size_t>(_S_max_bytes) || _S_force_new > 0)
	    ::operator delete(__p);
	  else
	    {
	      _Obj* volatile* __free_list = _M_get_free_list(__bytes);
	      _Obj* __q = reinterpret_cast<_Obj*>(__p);

	      __scoped_lock sentry(_M_get_mutex());
	      __q ->_M_free_list_link = *__free_list;
	      *__free_list = __q;
	    }
	}
    }

2.3.3 其他函数

  上述的两个allocate（）与deallocate（）函数中，直接或者间接地调用了另外三个函数_M_refill（），_M_allocate_chunk（）,_M_get_free_list（），这三个函数的定义可不好找，费了一番功夫，终于在GCC的github镜像库中找到了它们的定义。GitHub链接
例如以下是_M_refill（）函数的具体定义：

  void*
  __pool_alloc_base::_M_refill(size_t __n)
  {
    int __nobjs = 20;
    char* __chunk = _M_allocate_chunk(__n, __nobjs);
    _Obj* volatile* __free_list;
    _Obj* __result;
    _Obj* __current_obj;
    _Obj* __next_obj;

    if (__nobjs == 1)
      return __chunk;
    __free_list = _M_get_free_list(__n);

    // Build free list in chunk.
    __result = (_Obj*)(void*)__chunk;
    *__free_list = __next_obj = (_Obj*)(void*)(__chunk + __n);
    for (int __i = 1; ; __i++)
      {
	__current_obj = __next_obj;
	__next_obj = (_Obj*)(void*)((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;
  }

  观察代码可以看出，与SGI-STL版本的不能说是毫不相干，可以说是一模一样，其他两个函数的定义也大差不差。限于篇幅问题（写累了），以及CSDN上已经有很多大佬详细地介绍过空间配置器，就不再花时间过多介绍了。当然，如果有同学希望看到完整的解析的话，欢迎在评论区留言，哈哈。