序言
近期看《STL源码剖析》，诚然颇有所得，但仍不太满足于看这十几年前的例子，因而颇起了一些豪情，打算跟随书中的讲解，亲眼看一看当前最新的源码是怎样的。这一道阻且长的探索将成为本博客中的一个不小的系列，不过我的好奇能否保持、能否坚持写作，总是要留待后话了。好的地方是，这序言是在Allocator篇写完后才补上的，至少这第一步是已迈了出去。
GCC
侯捷老师在书中提到的基础版 allocator 和SGI特殊实现版 std::alloc 的区别，现在已经没有了（应该是基础版被干掉了）。现在统一叫 std::allocator ，很符合直觉。
为了佐证这里的信息，我们看 std::vector 里默认使用的Allocator是什么：
// /usr/include/c++/4.8.5/bits/stl_vector.h
template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
class vector : protected _Vector_base<_Tp, _Alloc>
// ===== snip =====
直接考察GCC对 std::allocator 的实现（删除了一些与本节相关性不大的注释/宏/函数）：
// /usr/include/c++/4.8.5/bits/allocator.h
#ifndef _ALLOCATOR_H
#define _ALLOCATOR_H 1
#include <bits/c++allocator.h> // Define the base class to std::allocator.
#include <bits/memoryfwd.h>
#include <type_traits>
namespace std _GLIBCXX_VISIBILITY(default)
{
template<>
class allocator<void>
{
public:
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef void* pointer;
typedef const void* const_pointer;
typedef void value_type;
template<typename _Tp1>
struct rebind
{ typedef allocator<_Tp1> other; };
typedef true_type propagate_on_container_move_assignment;
};
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; };
typedef true_type propagate_on_container_move_assignment;
allocator() throw() { }
allocator(const allocator& __a) throw()
: __allocator_base<_Tp>(__a) { }
template<typename _Tp1>
allocator(const allocator<_Tp1>&) throw() { }
~allocator() throw() { }
};
// ===== snip =====
} // namespace std
#endif
我们看到 std::allocator 继承了 __allocator_base 这个类，继续找到它的定义：
// /usr/include/c++/4.8.5/x86_64-redhat-linux/bits/c++allocator.h
#ifndef _GLIBCXX_CXX_ALLOCATOR_H
#define _GLIBCXX_CXX_ALLOCATOR_H 1
#include <ext/new_allocator.h>
namespace std
{
template<typename _Tp>
using __allocator_base = __gnu_cxx::new_allocator<_Tp>;
}
#endif
// /usr/include/c++/4.8.5/ext/new_allocator.h
#ifndef _NEW_ALLOCATOR_H
#define _NEW_ALLOCATOR_H 1
#include <bits/c++config.h>
#include <new>
#include <bits/functexcept.h>
#include <bits/move.h>
#include <type_traits>
namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
using std::size_t;
using std::ptrdiff_t;
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; };
typedef std::true_type propagate_on_container_move_assignment;
new_allocator() _GLIBCXX_USE_NOEXCEPT { }
new_allocator(const new_allocator&) _GLIBCXX_USE_NOEXCEPT { }
template<typename _Tp1>
new_allocator(const new_allocator<_Tp1>&) _GLIBCXX_USE_NOEXCEPT { }
~new_allocator() _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); }
// NB: __n is permitted to be 0. The C++ standard says nothing
// about what the return value is when __n == 0.
pointer
allocate(size_type __n, const void* = 0)
{
if (__n > this->max_size())
std::__throw_bad_alloc();
return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
}
// __p is not permitted to be a null pointer.
void
deallocate(pointer __p, size_type)
{ ::operator delete(__p); }
size_type
max_size() const _GLIBCXX_USE_NOEXCEPT
{ return size_t(-1) / sizeof(_Tp); }
#if __cplusplus >= 201103L
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
};
template<typename _Tp>
inline bool
operator==(const new_allocator<_Tp>&, const new_allocator<_Tp>&)
{ return true; }
template<typename _Tp>
inline bool
operator!=(const new_allocator<_Tp>&, const new_allocator<_Tp>&)
{ return false; }
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace
#endif
详细分析，GCC 4.8.5版本的Allocator实现了几个能力：
-
申请内存。对
operator new进行了简单封装，实现了成员allocate，这里允许申请0字节空间； -
释放内存。对
operator delete进行了简单封装，实现了成员deallocate，这里不允许传入空指针； -
获取可用的最大空间。这里的实现极其骚气，用
size_t(-1) / sizeof(_Tp)来取到可申请的最大空间，注意-1强转为无符号数就是全F，是最大无符号数； -
构造 & 析构。注意上面的代码片段里没有删除宏，因为C++11有大的特性升级，直接用 placement new + variadic template 实现了原地构造；而C++11以前的
construct实现，则只能拷贝构造一个新的成员（虽然也用了 placement new ，但类的构造本身还是存在拷贝的）。析构就是直接调指针指向的对象的析构函数。这里需要注意的是，C++11以后的Allocator版本，construct/destruct本身就是模板，相当于可以直接用来干自己的事情，与Allocator的模板参数类型解耦了。 -
比较运算符。比较好奇为啥需要实现这种东西，可以看到Allocator直接是恒等的。
至此，实际上已经看过了《STL源码剖析》中 2.2.1 （SGI标准的空间配置器 std::allocator ）和 2.2.3 （建构和解构基本工具：construct和destroy）这两节的内容在GCC 4.8.5 中的实现。令我比较奇怪的是，文中介绍的 construct/destroy 这两个函数对不同类型的重载，似乎是更高效的内存分配手段，在当前的 new_allocator 里面却被回退为原始的 new/delete 简单封装了。
至于书中花了大篇幅介绍的 SGI alloc 的实现，至少在我所阅读的GCC版本上已经不受默认选用了（不过仍作为 pool_allocator 存在）。看完书 2.2.4 ~ 2.2.10 节，会惊叹SGI内存池设计的精巧和复杂，两级配置器的设定充分体现出这版实现在内存管理方面粒度的精细。不过由于这部分内容现今已不作为默认Allocator存在，第二级配置器（书中指出这是默认 SGI alloc ）的一些实现细节，我放到 附录 无限风光在险峰 中再详谈。
Clang
Clang对allocator的实现不涉及多个文件中类的继承关系，比GCC简单些。 节选 如下：
#ifndef _LIBCPP___MEMORY_ALLOCATOR_H
#define _LIBCPP___MEMORY_ALLOCATOR_H
_LIBCPP_PUSH_MACROS
_LIBCPP_BEGIN_NAMESPACE_STD
template <class _Tp> class allocator;
#if _LIBCPP_STD_VER <= 17
template <>
class _LIBCPP_TEMPLATE_VIS allocator<void>
{
public:
_LIBCPP_DEPRECATED_IN_CXX17 typedef void* pointer;
_LIBCPP_DEPRECATED_IN_CXX17 typedef const void* const_pointer;
_LIBCPP_DEPRECATED_IN_CXX17 typedef void value_type;
template <class _Up> struct _LIBCPP_DEPRECATED_IN_CXX17 rebind {typedef allocator<_Up> other;};
};
template <>
class _LIBCPP_TEMPLATE_VIS allocator<const void>
{
public:
_LIBCPP_DEPRECATED_IN_CXX17 typedef const void* pointer;
_LIBCPP_DEPRECATED_IN_CXX17 typedef const void* const_pointer;
_LIBCPP_DEPRECATED_IN_CXX17 typedef const void value_type;
template <class _Up> struct _LIBCPP_DEPRECATED_IN_CXX17 rebind {typedef allocator<_Up> other;};
};
#endif
// This class provides a non-trivial default constructor to the class that derives from it
// if the condition is satisfied.
//
// The second template parameter exists to allow giving a unique type to __non_trivial_if,
// which makes it possible to avoid breaking the ABI when making this a base class of an
// existing class. Without that, imagine we have classes D1 and D2, both of which used to
// have no base classes, but which now derive from __non_trivial_if. The layout of a class
// that inherits from both D1 and D2 will change because the two __non_trivial_if base
// classes are not allowed to share the same address.
//
// By making those __non_trivial_if base classes unique, we work around this problem and
// it is safe to start deriving from __non_trivial_if in existing classes.
template <bool _Cond, class _Unique>
struct __non_trivial_if { };
template <class _Unique>
struct __non_trivial_if<true, _Unique> {
_LIBCPP_INLINE_VISIBILITY
_LIBCPP_CONSTEXPR __non_trivial_if() _NOEXCEPT { }
};
// allocator
//
// Note: For ABI compatibility between C++20 and previous standards, we make
// allocator<void> trivial in C++20.
template <class _Tp>
class _LIBCPP_TEMPLATE_VIS allocator
: private __non_trivial_if<!is_void<_Tp>::value, allocator<_Tp> >
{
public:
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef _Tp value_type;
typedef true_type propagate_on_container_move_assignment;
typedef true_type is_always_equal;
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
allocator() _NOEXCEPT _LIBCPP_DEFAULT
template <class _Up>
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
allocator(const allocator<_Up>&) _NOEXCEPT { }
_LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
_Tp* allocate(size_t __n) {
if (__n > allocator_traits<allocator>::max_size(*this))
__throw_length_error("allocator<T>::allocate(size_t n)"
" 'n' exceeds maximum supported size");
if (__libcpp_is_constant_evaluated()) {
return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
} else {
return static_cast<_Tp*>(_VSTD::__libcpp_allocate(__n * sizeof(_Tp), _LIBCPP_ALIGNOF(_Tp)));
}
}
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
void deallocate(_Tp* __p, size_t __n) _NOEXCEPT {
if (__libcpp_is_constant_evaluated()) {
::operator delete(__p);
} else {
_VSTD::__libcpp_deallocate((void*)__p, __n * sizeof(_Tp), _LIBCPP_ALIGNOF(_Tp));
}
}
// C++20 Removed members
#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_ALLOCATOR_MEMBERS)
_LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp* pointer;
_LIBCPP_DEPRECATED_IN_CXX17 typedef const _Tp* const_pointer;
_LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp& reference;
_LIBCPP_DEPRECATED_IN_CXX17 typedef const _Tp& const_reference;
template <class _Up>
struct _LIBCPP_DEPRECATED_IN_CXX17 rebind {
typedef allocator<_Up> other;
};
_LIBCPP_DEPRECATED_IN_CXX17 _LIBCPP_INLINE_VISIBILITY
pointer address(reference __x) const _NOEXCEPT {
return _VSTD::addressof(__x);
}
_LIBCPP_DEPRECATED_IN_CXX17 _LIBCPP_INLINE_VISIBILITY
const_pointer address(const_reference __x) const _NOEXCEPT {
return _VSTD::addressof(__x);
}
_LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY _LIBCPP_DEPRECATED_IN_CXX17
_Tp* allocate(size_t __n, const void*) {
return allocate(__n);
}
_LIBCPP_DEPRECATED_IN_CXX17 _LIBCPP_INLINE_VISIBILITY size_type max_size() const _NOEXCEPT {
return size_type(~0) / sizeof(_Tp);
}
template <class _Up, class... _Args>
_LIBCPP_DEPRECATED_IN_CXX17 _LIBCPP_INLINE_VISIBILITY
void construct(_Up* __p, _Args&&... __args) {
::new ((void*)__p) _Up(_VSTD::forward<_Args>(__args)...);
}
_LIBCPP_DEPRECATED_IN_CXX17 _LIBCPP_INLINE_VISIBILITY
void destroy(pointer __p) {
__p->~_Tp();
}
#endif
};
// ===== snip =====
// 省略了 const TP_ 的版本，因为大体相同
// 省略了无关紧要的比较运算符
_LIBCPP_END_NAMESPACE_STD
_LIBCPP_POP_MACROS
#endif // _LIBCPP___MEMORY_ALLOCATOR_H
有几点感想：
-
Allocator对
non_trival_if的继承，没有看明白，即使有那段那么长的注释，也看不懂这波继承的意义，留待将来考量吧。 -
这个版本的
allocate / deallocate也接近于对operator new的封装，在非 constant-evaluated 的场景下，会继续调用内部函数来申请/释放内存，否则直接调用operator new返回。后面继续分析内部的内存申请释放函数并解释为啥要多这么个流程。 -
这里对
construct / destroy的实现也是简单的 placement new ，并指出当前已经不建议使用Allocator里面的这两个成员，并将在C++ 20上彻底移除它们。查了一些资料 1 2 3 发现目前标准的做法是不直接使用std::allocator，而使用std::allocator_traits，而construct / destroy已经在allocator_traits里有了重复实现，没必要在allocator中保留了。 -
看完Clang的实现才发现刚才看的GCC 4.x太老了，这些新标准的特性等等都没有体现出来。Whatever，精髓仍在，也不把前文推倒重写了…… 另外，实际上我还是回过头看了下GCC 11.x，好家伙，满地的宏，根据各种版本选用不同实现，读上去有点崩溃，反而不如早期版本简洁明了……
果然项目开展到后期代码就会变成屎山。
本篇不会考察 allocator_traits 的实现，这个需要等到后面实际在容器中去用Allocator的时候再研究。继续看Allocator自身的部分，内存的申请/释放：
// new
inline _LIBCPP_INLINE_VISIBILITY
void *__libcpp_allocate(size_t __size, size_t __align) {
#ifndef _LIBCPP_HAS_NO_ALIGNED_ALLOCATION
if (__is_overaligned_for_new(__align)) {
const align_val_t __align_val = static_cast<align_val_t>(__align);
return __libcpp_operator_new(__size, __align_val);
}
#endif
(void)__align;
return __libcpp_operator_new(__size);
}
inline _LIBCPP_INLINE_VISIBILITY
void __libcpp_deallocate(void* __ptr, size_t __size, size_t __align) {
#if defined(_LIBCPP_HAS_NO_ALIGNED_ALLOCATION)
(void)__align;
return __do_deallocate_handle_size(__ptr, __size);
#else
if (__is_overaligned_for_new(__align)) {
const align_val_t __align_val = static_cast<align_val_t>(__align);
return __do_deallocate_handle_size(__ptr, __size, __align_val);
} else {
return __do_deallocate_handle_size(__ptr, __size);
}
#endif
}
template <class ..._Args>
_LIBCPP_INLINE_VISIBILITY
void* __libcpp_operator_new(_Args ...__args) {
#if __has_builtin(__builtin_operator_new) && __has_builtin(__builtin_operator_delete)
return __builtin_operator_new(__args...);
#else
return ::operator new(__args...);
#endif
}
template <class ..._Args>
_LIBCPP_INLINE_VISIBILITY
void __do_deallocate_handle_size(void *__ptr, size_t __size, _Args ...__args) {
#ifdef _LIBCPP_HAS_NO_SIZED_DEALLOCATION
(void)__size;
return __libcpp_operator_delete(__ptr, __args...);
#else
return __libcpp_operator_delete(__ptr, __size, __args...);
#endif
}
我们对内存申请/释放的探究只能深入到 __builtin_operator_new/delete 了，再往后的区域，已是编译器的领域。
Clang自己的资料 4 向我们指出，这里的封装本质上跟 operator new 没太大区别，不过是编译器希望内部继续对 operator new 进行优化而规范不允许，因而进行了一层封装以此解除限制。资料并指出了两种优化场景，比如移除 new/delete 对（我理解就是把A处释放的内存不归还系统而直接让B处申请走）、合并内存申请动作等。
附录 无限风光在险峰
如正文中所讲，侯捷老师在书中花了大篇幅介绍的两级配置器，在当前的GCC版本中实际已非首选。但我看完了相关的内容后，觉得这才是大师之作，非细读之不能一览Allocator之妙，乃有此录。
二级配置器
书中的两级配置器，实际上在当前GCC版本里面叫做 pool_allocator ，首先看到其基类：
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);
};
这个类体现书 2.2.6 节介绍的内容，有几个要点：
-
空闲内存链表节点和用户申请到的空间，本质上是同一块内存（union）。对用户来说，申请到手后就是一块随便读写的内存，对
free_list来说，反正这块内存现在不在用户手上，直接拿来记载下一块空闲内存的位置，物尽其用。这样的策略带来的好处是不必花费任何额外的专门结构来记录下一块空闲内存信息了。 -
这里的
_M_round_up实现非常帅，实际上就是把传入的数向上对齐为_S_align的倍数（这里是8），相比于常见的取模运算，这里的位运算就是大师带来的小小震撼了，至少我是震撼的。
后面的一些成员就没有实现了，继续看：
template<typename _Tp>
class __pool_alloc : private __pool_alloc_base
{
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
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);
};
template<typename _Tp>
inline bool
operator==(const __pool_alloc<_Tp>&, const __pool_alloc<_Tp>&)
{ return true; }
#if __cpp_impl_three_way_comparison < 201907L
template<typename _Tp>
inline bool
operator!=(const __pool_alloc<_Tp>&, const __pool_alloc<_Tp>&)
{ return false; }
#endif
template<typename _Tp>
_Atomic_word
__pool_alloc<_Tp>::_S_force_new;
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);
}
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);
__scoped_lock sentry(_M_get_mutex());
_Obj* __restrict__ __result = *__free_list;
if (__builtin_expect(__result == 0, 0))
__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;
}
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);
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;
}
}
}
这里的 __pool_alloc 还能依稀见到书中的样式，但具体的一些实现已经没有了。就此处能看到的内存申请/分配仍分析一二。
-
首先重申这里对应的是书中的二级配置器，那么一级配置器在这里是啥呢？实际上是
operator new。对于大块内存（超出_S_max_bytes的情况）和强制new（GLIBCXX_FORCE_NEW）的情况，__pool_alloc直接调用一级配置器operator new。 -
对于小块内存的情况，会从
free_list里面取一块合适的内存，当然，分配出去的大小其实是经过了round_up的。当free_list没有余粮时，会调用_M_refill来分配内存并顺便补充对应的空闲链表。
__pool_alloc 的总体分配逻辑大概是这样的：
归还逻辑无非是把空间还给链表，不做叙述了。
重填free_list
比较可惜的是， refill 逻辑在当前的GCC版本似乎是被屏蔽掉了（或者是我没找到），这里只好回头看侯捷老师的摘录和讲解。
//傳回一個大小為n的物件，並且有時候會f為適當的ree list增加節點.
// 假設 n 已經適當上調至 8 的倍數。
template <bool threads, int inst>
void* __default_alloc_template<threads, inst>::refill(size_t n)
{
int nobjs = 20;
// 呼叫 chunk_alloc()，嘗試取得 nobjs 個區塊做為 free list 的新節點。
// 注意參數 nobjs 是 pass by reference。
char * chunk = chunk_alloc(n, nobjs); // 下節詳述
obj * volatile * my_free_list;
obj * result;
obj * current_obj, * next_obj;
int i;
// 如果只獲得一個區塊，這個區塊就撥給呼叫者用，free list 無新節點。
if (1 == nobjs) return(chunk);
// 否則準備調整 free list，納入新節點。
my_free_list = free_list + FREELIST_INDEX(n);
//以下在chunk空間內建立free list
result = (obj *)chunk; // 這一塊準備傳回給客端
// 以下導引 free list 指向新配置的空間(取自記憶池)
*my_free_list = next_obj = (obj *)(chunk + n);
// 以下將 free list 的各節點串接起來。
for (i = 1; ; i++) { // 從1開始，因為第0個將傳回給客端
current_obj = next_obj;
next_obj = (obj *)((char *)next_obj + n);
if (nobjs - 1 == i) {
current_obj -> free_list_link = 0;
break;
} else {
current_obj -> free_list_link = next_obj;
}
}
return(result);
}
这里实际上完成了我刚才说的 分配内存并填充 free_list 的动作，预设 20 个节点，分配给客户端一个，实际上往 free_list 填充了 19 个节点。
内存池管理
// 假設 size 已經適當上調至 8 的倍數。
// 注意參數 nobjs 是 pass by reference。
template <bool threads, int inst>
char*
__default_alloc_template<threads, inst>:: chunk_alloc(size_t size, int& nobjs)
{
char * result;
size_t total_bytes = size * nobjs;
size_t bytes_left = end_free - start_free; // 記憶池剩餘空間
if (bytes_left >= total_bytes) {
// 記憶池剩餘空間完全滿足需求量。
result = start_free;
start_free += total_bytes;
return(result);
} else if (bytes_left >= size) {
// 記憶池剩餘空間不能完全滿足需求量，但足夠供應一個(含)以上的區塊。
nobjs = bytes_left/size;
total_bytes = size * nobjs;
result = start_free;
start_free += total_bytes;
return(result);
} else {
// 記憶池剩餘空間連一個區塊的大小都無法提供。
size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
// 以下試著讓記憶池中的殘餘零頭還有利用價值。
if (bytes_left > 0) {
// 記憶池內還有一些零頭，先配給適當的 free list。
// 首先尋找適當的 free list。
obj * volatile * my_free_list =
free_list + FREELIST_INDEX(bytes_left);
// 調整 free list，將記憶池中的殘餘空間編入。
((obj *)start_free) -> free_list_link = *my_free_list;
*my_free_list = (obj *)start_free;
}
// 配置 heap 空間，用來挹注記憶池。
start_free = (char *)malloc(bytes_to_get);
if (0 == start_free) {
// heap 空間不足，malloc() 失敗。
int i;
obj * volatile * my_free_list, *p;
// 試著檢視我們手上擁有的東西。這不會造成傷害。我們不打算嘗試配置
// 較小的區塊，因為那在多行程(multi-process)機器上容易導致災難
// 以下搜尋適當的 free list，
// 所謂適當是指「尚有未用區塊，且區塊夠大」之 free list。
for (i = size; i <= __MAX_BYTES; i += __ALIGN) {
my_free_list = free_list + FREELIST_INDEX(i);
p = *my_free_list;
if (0 != p) { // free list 內尚有未用區塊。
// 調整 free list 以釋出未用區塊
*my_free_list = p -> free_list_link;
start_free = (char *)p;
end_free = start_free + i;
// 遞迴呼叫自己，為了修正 nobjs。
return(chunk_alloc(size, nobjs));
// 注意，任何殘餘零頭終將被編入適當的 free-list 中備用。
}
}
end_free = 0; // 如果出現意外(山窮水盡，到處都沒記憶體可用了)
// 呼叫第一級配置器，看看 out-of-memory 機制能否盡點力
start_free = (char *)malloc_alloc::allocate(bytes_to_get);
// 這會導致擲出異常(exception)，或記憶體不足的情況獲得改善。
}
heap_size += bytes_to_get;
end_free = start_free + bytes_to_get;
// 遞迴呼叫自己，為了修正 nobjs。
return(chunk_alloc(size, nobjs));
}
}
chunk_alloc 有几个点是需要揣摩的：
-
先收编池内内存（
start_free~end_free的部分），再向系统堆申请新的大块内存，这样做的好处显然是减少了碎片； -
向系统申请内存失败后，会去找
free_list当中更大的内存，若找到，会取出一块作为新的内存池，然后回调自身，基于这块大内存完成chunk_alloc动作。这个操作可行的原因是我们此前的alloc动作一直都是去看 恰到好处 的那块free_list，而没有去惦记更大块的内存；现在当小块内存不够用而大块free_list尚有时，就会把大块内存在这里进行分割（拿去作为池子并分割了后，就会被refill填充到小块内存的free_list里了）。
此外，我阅读时一直觉得整个体系有点违和，根本上是因为没有搞懂内存分配的对齐机制。总觉得不管是这里的内存池转移到 free_list ，或者是从 free_list 里面摘出新的大块内存分成小内存，都有种随时随地产生碎片的风险。实际上，只要注意到不管是客户面的内存分配/释放，或者是内部的内存申请/分割，都是以 对齐后 的单位来进行的，就不会出现内存碎片的疑虑。
至此，整个内存池的机制终于是看完了，当真不易也。
参考资料
-
https://blog.csdn.net/weixin_43705457/article/details/104085176 ↩︎
-
StackOverflow–Why are are std::allocator’s construct and destroy functions deprecated in c++17? ↩︎
-
https://en.cppreference.com/w/cpp/memory/allocator_traits ↩︎
-
https://clang.llvm.org/docs/LanguageExtensions.html#builtin-operator-new-and-builtin-operator-delete ↩︎