剖析 STL 内存分配器设计

本期主要讲解C++ STL中的内存分配器std::allocator及其特性萃取器__gnu_cxx::__alloc_traits。

为防止混淆，规定如下：

  • allocator：泛指内存分配器，仅仅是一个术语。
  • std::allocator：是STL实现的内存分配器类std::allocator。

__gnu_cxx::new_allocator

C++的默认的内存分配器std::allocator，继承至__gnu_cxx::new_allocator。而 __gnu_cxx::new_allocator 主要完成两个任务：

  • 分配对象内存、初始化对象
  • 析构对象、释放对象内存

__gnu_cxx::new_allocator 是个空类，没有成员变量，主要有四种成员函数完成上述任务：

  • allocate 函数，用于分配内存
  • construct函数，调用已分配内存对象的构造函数
  • destroy函数，调用析构函数
  • deallocate函数，用于释放内存

__gnu_cxx::new_allocator 的整体框架大致如下：

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 <typename _Tp>
class new_allocator
{
public:
  typedef size_t      size_type;
  typedef 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 new_allocator<_Tp1> other;
  };

  new_allocator() _GLIBCXX_USE_NOEXCEPT {}
  new_allocator(const new_allocator &) noexcept {}
  template <typename _Tp1>
  new_allocator(const new_allocator<_Tp1> &) noexcept {}
  ~new_allocator() noexcept {}
 
  pointer allocate(size_type __n, const void * = static_cast<const void *>(0));
    
  void deallocate(pointer __p, size_type);
    
  size_type max_size() const noexcept;

  template <typename _Up, typename... _Args>
  void construct(_Up *__p, _Args &&...__args) 
    				noexcept(noexcept(::new ((void *)__p)_Up(std::forward<_Args>(__args)...)));
  template <typename _Up>
  void destroy(_Up *__p) noexcept(noexcept(__p->~_Up()));
  //...
};

allocate

allocate函数，用于分配大小为__n个字节内存，返回值是分配所得内存的地址。

  • 如果待分配内存大小__n大于当前进程最大可用内存，那么就会抛出bad_alloc异常。
  • 再调用operator new来分配内存。operator new对malloc作了一层简单的封装，等效于malloc
  • 将指向operator new的返回值类型转换为此次分配对象_Tp的指针类型。

整个过程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
    pointer allocate(size_type __n, const void * = static_cast<const void *>(0))
    {
      if (__n > this->max_size())
        std::__throw_bad_alloc();

#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(__n * sizeof(_Tp), __al));
      }
#endif
      return static_cast<_Tp *>(::operator new(__n * sizeof(_Tp)));
    }

deallocate

deallocate函数，使用operator delete来释放地址__p指向的内存。

1
2
3
4
5
6
7
8
9
10
11
    void deallocate(pointer __p, size_type)
    {
#if __cpp_aligned_new
      if (alignof(_Tp) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)
      {
        ::operator delete(__p, std::align_val_t(alignof(_Tp)));
        return;
      }
#endif
      ::operator delete(__p);
    }

construct

上面的allocate函数相当于malloc函数，只是分配__n个字节的内存，但是并未对这片内存进行初始化。对allocate 函数分配的内存__p进行初始化的任务，交给construct函数来完成。

constuct函数，使用了new表达式的另一种形式，叫做placement new，使用方式如下注释：

1
2
3
4
5
6
7
8
template <typename _Up, typename... _Args>
void construct(_Up *__p, _Args &&...__args) 
  				noexcept(noexcept(::new ((void *)__p)_Up(std::forward<_Args>(__args)...)))
{
    // 表示在 地址 _p 上调用对象 _Up的构造函数
    // 其中，__args是构造函数的参数
    ::new ((void *)__p) _Up(std::forward<_Args>(__args)...);
}

destroy

deallocate函数，是完成了释放内存，但是在释放内存之前一般需要先调用对象的析构函数，完成相关的资源的释放、关闭操作。因此在destoy函数中，直接调用了类型_Up的析构函数。

1
2
3
4
5
template <typename _Up>
 void destroy(_Up *__p) noexcept(noexcept(__p->~_Up()))
 {
   __p->~_Up();
 }

std::allocator

类std::allocator 继承__gnu_cxx::new_allocator。

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<typename _Tp>
using __allocator_base = __gnu_cxx::new_allocator<_Tp>;


  template <typename _Tp>
  class allocator : public __allocator_base<_Tp>
  {
  public:
    typedef size_t      size_type;
    typedef 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 allocator<_Tp1> other;
    };

    allocator() noexcept {}
    allocator(const allocator &__a) noexcept : __allocator_base<_Tp>(__a) {}
    allocator &operator=(const allocator &) = default;

    template <typename _Tp1>
    allocator(const allocator<_Tp1> &) _GLIBCXX_NOTHROW
    { }

    ~allocator() _GLIBCXX_NOTHROW {}

	//...
    // Inherit everything else.
  };

rebind

在__gnu_cxx::new_allocator、std::allocator中都有一个rebind函数，其主要作用：获得类型_Tp1的内存分配器allocator<_Tp1>。

1
2
3
4
5
template <typename _Tp1>
 struct rebind
 {
   typedef allocator<_Tp1> other;
 };

这个函数在容器中被STL中被广泛使用。比如，在std::list<_Tp, std::allocator<_Tp>>中，std::allocator不仅要为_Tp类型的对象分配内存，还要为存储_Tp对象的节点list_node<_Tp>分配内存。但是std::list<_Tp, std::allocator<_Tp>>的类模板参数中只是传入了用于分配_Tp类型的内存分配器std::allocator<_Tp>，那么怎么获得list_node<_Tp>类型的内存分配器呢？

答案就是依靠rebind函数：allocator<_Tp>::rebind<list_node<_Tp>>::other，获得的就是用于分配list_node<_Tp>类型的内存分配器 allocator<list_node<_Tp>>。

在list中的实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template<typename _Tp, typename _Alloc>
class _List_base
{
protected:
  // 用于分配 _Tp 类型的内存分配器: _Tp_alloc_type
  // _Tp_alloc_type 实际上就是 std::allocator
  typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template rebind<_Tp>::other _Tp_alloc_type;
  // 用于分配 List_node<_Tp> 类型的内存分配器：_Node_alloc_type
  typedef typename _Tp_alloc_traits::template rebind<_List_node<_Tp> >::other _Node_alloc_type;        
  //...
};

template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
class list : protected _List_base<_Tp, _Alloc>
{
protected:
  typedef _List_node<_Tp>				 _Node;
  //...
};

std::__allocator_traits_base

上面的list中使用到了用于萃取内存分配器属性的类__gnu_cxx::__alloc_traits。

1
2
__gnu_cxx::__alloc_traits 继承自 std::allocator_traits
std::allocator_traits 	  继承自 std::__allocator_traits_base

类__allocator_traits_base，用于获取内存分配器_Alloc的属性，这个分配器_Alloc不一定是上面所述的std::allocator，可以是自定义的。

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

struct __allocator_traits_base
{
  template <typename _Tp,
            typename _Up,
            typename = void>
  struct __rebind : __replace_first_arg<_Tp, _Up>
  { };  

  // __rebind 特化版本：当分配器 _Tp 有成员函数 rebind 时调用此特化版本
  template <typename _Tp, typename _Up>
  struct __rebind<_Tp,
                  _Up,
                  __void_t<typename _Tp::template rebind<_Up>::other>>
  {
    using type = typename _Tp::template rebind<_Up>::other;
  };

protected:
  template <typename _Tp> using __pointer 	= typename _Tp::pointer;
  template <typename _Tp> using __c_pointer 	= typename _Tp::const_pointer;
  template <typename _Tp> using __v_pointer 	= typename _Tp::void_pointer;
  template <typename _Tp> using __cv_pointer 	= typename _Tp::const_void_pointer;
  template <typename _Tp> using __pocca = typename _Tp::propagate_on_container_copy_assignment;
  template <typename _Tp> using __pocma = typename _Tp::propagate_on_container_move_assignment;
  template <typename _Tp> using __pocs  = typename _Tp::propagate_on_container_swap;
  template <typename _Tp> using __equal = typename _Tp::is_always_equal;
};

__rebind

类__allocator_traits_base 中最重要的是成员函数__rebind。 __rebind的模板参数_Tp是分配器类型，根据_Tp来实现重载：

  • 当传入的内存分配器类型_Tp，实现了rebind成员函数时，比如上面的std::allocator，那么就调用__rebind的特化版本：

    1
    2
    3
    4
    5
    6
    7
    template <typename _Tp, typename _Up>
    struct __rebind<_Tp,
                    _Up,
                    __void_t<typename _Tp::template rebind<_Up>::other>>
    {
      using type = typename _Tp::template rebind<_Up>::other;
    };

    以std::allocator<int>为例，获取Node<int>类型的内存分配器：

    1
    2
    3
    __allocator_traits_base::__rebind<std::allocator<int>, Node<int>>::type  
    // 等价于 
    std::allocator<Node<int>>

  • 当传入的分配器_Tp没有实现rebind成员函数时，就调用普通__rebind版本：

    1
    2
    3
    4
    5
    6
    // _Tp需要是分配器
    template <typename _Tp,
              typename _Up,
              typename = void>
    struct __rebind : __replace_first_arg<_Tp, _Up>
    { };

    其中__replace_first_arg实现如下。此时，需要自定义一个内存分配器模板_Template，

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    template <typename _Tp, typename _Up>
    struct __replace_first_arg
    { };
      
    // _Template 是个类模板
    template <template <typename, typename...> class _Template, 
              typename _Up,
              typename _Tp, 
              typename... _Types>
    struct __replace_first_arg<_Template<_Tp, _Types...>, _Up>
    {
      using type = _Template<_Up, _Types...>;
    };

by the way

在此，补充点模板的一点知识：

  1. 模板参数模板

    在__replace_first_arg类中，使用了一个类模板参数模板_Template，这表示模板参数_Template本身就是个类模板。

    1
    template <typename, typename...> class _Template

  2. ::template

    在__rebind函数体中，在::后面有个template关键字，这是用于告诉编译器 template后面的 < 不是比较符号，而是模板参数符号。就是类似于_Tp前面的typename是告诉编译器::后面的是类成员函数，而不是static函数。

    1
    using type = typename _Tp::template rebind<_Up>::other;

__alloc_rebind

全局函数__alloc_rebind，是std::__allocator_traits_base的wrapper，用于获取为_Up类型分配内存的内存分配器_Alloc<_Up>

1
2
template <typename _Alloc, typename _Up>
using __alloc_rebind = typename __allocator_traits_base::template __rebind<_Alloc, _Up>::type;

std::allocator_traits

类std::allocator_traits，继承于std::__allocator_traits_base，用于获取内存分配器allocator的各个属性。

1
2
3
4
5
6
7
 template <typename _Alloc>
 struct allocator_traits : __allocator_traits_base
 {
   typedef _Alloc allocator_type;					  /// The allocator type
   typedef typename _Alloc::value_type value_type;	  /// The allocated type
//...
 };

当_Alloc是std::allocator时，有个特化版本：

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
 template <typename _Tp>
 struct allocator_traits<allocator<_Tp>>
 {
   using allocator_type = allocator<_Tp>;  // 分配器类型
   using value_type = _Tp;                 // 待分配内存的对象类型
   using pointer = _Tp *;                 // 对象指针
   using const_pointer = const _Tp *;
//...  using 
   using is_always_equal = true_type;

   // 使用allocator为_Up分配内存
   template <typename _Up>
   using rebind_alloc = allocator<_Up>;

   template <typename _Up>
   using rebind_traits = allocator_traits<allocator<_Up>>;
     
   // 下面是 std::allocator<_Tp> 成员函数的 wrapper
   static pointer allocate(allocator_type &__a, size_type __n)
   {
     return __a.allocate(__n);
   }

   static pointer allocate(allocator_type &__a, size_type __n, const_void_pointer __hint)
   {
     return __a.allocate(__n, __hint);
   }

   static void deallocate(allocator_type &__a, pointer __p, size_type __n)
   {
     __a.deallocate(__p, __n);
   }

   template <typename _Up, typename... _Args>
   static void construct(allocator_type &__a, _Up *__p, _Args &&...__args) 
               noexcept(noexcept(__a.construct(__p, std::forward<_Args>(__args)...)))
   {
     __a.construct(__p, std::forward<_Args>(__args)...);
   }

   template <typename _Up>
   static void destroy(allocator_type &__a, _Up *__p) noexcept(noexcept(__a.destroy(__p)))
   {
     __a.destroy(__p);
   }

   static size_type max_size(const allocator_type &__a) noexcept
   {
     return __a.max_size();
   }
 };

__gnu_cxx::__alloc_traits

__gnu_cxx::__alloc_traits类，也大都是std::allocator_traits的wrapper，

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
template<typename _Alloc, typename = typename _Alloc::value_type>
struct __alloc_traits : std::allocator_traits<_Alloc> { 

    typedef _Alloc 								 allocator_type;
    typedef std::allocator_traits<_Alloc>        _Base_type;

    typedef typename _Base_type::value_type      value_type;
    typedef typename _Base_type::pointer         pointer;
    typedef typename _Base_type::const_pointer   const_pointer;
    typedef typename _Base_type::size_type       size_type;
    typedef typename _Base_type::difference_type difference_type;

    typedef value_type &      					 reference;
    typedef const value_type& 					 const_reference;

    using _Base_type::allocate;
    using _Base_type::construct;
    using _Base_type::deallocate;
    using _Base_type::destroy;
    using _Base_type::max_size;

  private:
    
    // 当 _Ptr 不是个标准指针，但是 _Ptr 和 value_type* 相同
    // __is_custom_pointer 才是 true，即 _Ptr 是个自定义指针
    // 即 _Ptr 可转换为 pointer
    template <typename _Ptr>
    using __is_custom_pointer 
        = std::__and_<std::is_same<pointer, _Ptr>, std::__not_<std::is_pointer<_Ptr>>>;

  public:
    // overload construct for non-standard pointer types
    // 重载非标准类型的指针，调用构造函数
    template <typename _Ptr, typename... _Args>
    static typename std::enable_if<__is_custom_pointer<_Ptr>::value>::type
    construct(_Alloc &__a, _Ptr __p, _Args &&...__args) noexcept(...) // 省略了noexcept中的表达式
    {
      // 使用分配器 __a , 在地址 __p 调用构造函数
      _Base_type::construct(__a, 
                            std::__to_address(__p),
                            std::forward<_Args>(__args)...);
    }

    // overload destroy for non-standard pointer types
    // 重载非标准类型指针，调用析构函数
    template <typename _Ptr>
    static typename std::enable_if<__is_custom_pointer<_Ptr>::value>::type
    destroy(_Alloc &__a, _Ptr __p) noexcept(...) 
    {
      _Base_type::destroy(__a, std::__to_address(__p));
    }
    
    /*** 对于标准的指针，会直接调用父类的constuct、destroy ***/
	
    // wrapper
    template <typename _Tp>
    struct rebind
    {
      typedef typename _Base_type::template rebind_alloc<_Tp> other;
    };
    //...
}

总体来说，__gnu_cxx::__alloc_traits提供了一个顶层的内存分配器萃取器，可以使用 _Alloc 的 allocate、 deallocate、construct 以及 destroy 等函数来完成对象构造和析构等任务。

而类std::allocator_traits 是底层直接获取内存分配器_Alloc属性的类，其中std::allocator_traits有个特化版本，即使_Alloc是std::allocator，因为std::allocator是STL的容器默认的内存分配器。

如果想将自定义的内存分配器Custome_Alloc融入到STL体系中，那么也需要像std::allocator一样完成相应的接口设计、以及rebind函数。这样，容器就能通过__gnu_cxx::__alloc_traits<Custome_Alloc>使用自定义的内存分配器Custome_Alloc。

好嘞，到此完成了本期的目标，即讲解完毕C++ STL内存分配器的设计。