STL空间分配器源码分析（二）mt_allocator

一、简介

mt allocator 是一种以2的幂次方字节大小为分配单位的空间配置器，支持多线程和单线程。该配置器灵活可调，性能高。

分配器有三个通用组件：一个描述内存池特性的数据，一个包含该池的策略类，该池将实例化类型链接到公共或单个池，以及一个从策略类继承的类，该类是实际的分配器。

描述内存池特性的数据：template class __pool；
内存池的策略类：mt allocator提供了两种策略，一种公共内存池，一种专用内存池；
实际的分配器：class __mt_alloc

二、内存池特性描述

struct _Tune
{
    // Compile time constants for the default _Tune values.
    enum { _S_align = 8 };
    enum { _S_max_bytes = 128 };
    enum { _S_min_bin = 8 };
    enum { _S_chunk_size = 4096 - 4 * sizeof(void*) };
    enum { _S_max_threads = 4096 };
    enum { _S_freelist_headroom = 10 };

    size_t    _M_align;         //对齐大小，在任何情况下，必须大于等于sizeof（_Block_record），即在32位机器上为4，在64位机器上为8。
    size_t    _M_max_bytes;     //能分配的最大内存块大小，必须远小于_M_chunk_size的大小且必须小于32768
    size_t    _M_min_bin;       //能分配的最小内存块大小，2的幂次方，必须大于等于_M_align且远小于_M_max_bytes
    size_t    _M_chunk_size;    //预先申请的内存块大小，为避免内存碎片和频繁调用new申请小内存，所以先提前申请好大块内存，该值需远大于_M_max_bytes
    size_t     _M_max_threads;  //支持的最大线程数
    size_t     _M_freelist_headroom;    //多线程下，当回收的内存数超过其空闲链表的_M_freelist_headroom %，将内存块直接回收到全局链表中
    bool     _M_force_new;      //是否强制使用new申请

    //如下两个构造函数，一个默认构造函数，使用默认值初始化上述控制信息，一个根据入参确定控制信息
    explicit
    _Tune()
    : _M_align(_S_align), _M_max_bytes(_S_max_bytes), _M_min_bin(_S_min_bin),
    _M_chunk_size(_S_chunk_size), _M_max_threads(_S_max_threads), 
    _M_freelist_headroom(_S_freelist_headroom), 
    _M_force_new(std::getenv("GLIBCXX_FORCE_NEW") ? true : false)
    { }

    explicit
    _Tune(size_t __align, size_t __maxb, size_t __minbin, size_t __chunk, 
    size_t __maxthreads, size_t __headroom, bool __force) 
    : _M_align(__align), _M_max_bytes(__maxb), _M_min_bin(__minbin),
    _M_chunk_size(__chunk), _M_max_threads(__maxthreads),
    _M_freelist_headroom(__headroom), _M_force_new(__force)
    { }
};

三、内存池实现

struct __pool_base
{
    typedef unsigned short int _Binmap_type;    
    typedef std::size_t size_t;

    struct _Block_address
    {
        void*             _M_initial;
        _Block_address*         _M_next;
    };

    const _Tune& _M_get_options() const
    { return _M_options; }

    void _M_set_options(_Tune __t)
    { 
        if (!_M_init)
        _M_options = __t;
    }

    bool _M_check_threshold(size_t __bytes)
    { return __bytes > _M_options._M_max_bytes || _M_options._M_force_new; }

    size_t _M_get_binmap(size_t __bytes)
    { return _M_binmap[__bytes]; }

    size_t _M_get_align()
    { return _M_options._M_align; }

    explicit __pool_base() 
    : _M_options(_Tune()), _M_binmap(0), _M_init(false) { }

    explicit  __pool_base(const _Tune& __options)
    : _M_options(__options), _M_binmap(0), _M_init(false) { }

    private:
    explicit  __pool_base(const __pool_base&);

    __pool_base& operator=(const __pool_base&);

    protected:
    _Tune                    _M_options;
    _Binmap_type*         _M_binmap;
    bool             _M_init;    //内存池对象的特性配置（Tune）可以在构造之后，但必须在初始化之前。初始化完成后，该标志置为true
};

上述为内存池的基类实现，类成员包括描述内存池特性的Tune结构，内存块索引的表结构指针（_M_binmap）和初始化标志_M_init，以及部分简单接口。

_M_get_options和_M_set_options用于查设内存池特性参数；

_M_check_threshold用于内存块大小校验，以此判断是否需要调用关键字new申请内存；

_M_get_binmap用于根据申请的内存块大小映射到对应的内存块下标（即子类_M_bin数组下标，下面详细介绍）；

_M_get_align获取内存池特性参数之对齐大小；

mt_allocator配置器基于__pool_base实现了单一线程和多线程两种场景使用下的内存池（实际是指定了两种全特化的内存池模板），如下

template<bool _Thread>
class __pool;

/*单线程*/
template<>
class __pool<false> : public __pool_base{...}；
/*多线程*/
template<>
class __pool<true> : public __pool_base{...}；

四、单一线程场景下内存池的实现 

template<>
class __pool<false> : public __pool_base
{
public:
    /* 表示内存块节点，用来构成内存链表结构 */
    union _Block_record
    {
        _Block_record*             _M_next;    // 指向下一个内存块的节点
    };

    /* 用来记录内存单元信息，每个内存单元存储着同一大小的数个内存块 */
    struct _Bin_record
    {
        _Block_record**            _M_first;    // 指针数组，数组中的每个指针指向第一个空闲块节点，数组的大小等于线程的个数，每个线程占一个数组元素，单线程情况下仅为一个
        _Block_address*            _M_address;  // 内存单元的地址
    };
  
    //内存池初始化，内部防止多次初始化
    void _M_initialize_once()
    {
        if (__builtin_expect(_M_init == false, false))
            _M_initialize();
    }

    //内存池资源回收
    void _M_destroy() throw();

    //内存块分配
    char* _M_reserve_block(size_t __bytes, const size_t __thread_id);

    //内存块回收
    void _M_reclaim_block(char* __p, size_t __bytes) throw ();

    size_t _M_get_thread_id() { return 0; }
  
    const _Bin_record& _M_get_bin(size_t __which)
    { return _M_bin[__which]; }

    void _M_adjust_freelist(const _Bin_record&, _Block_record*, size_t) { }

    explicit __pool() 
    : _M_bin(0), _M_bin_size(1) { }

    explicit __pool(const __pool_base::_Tune& __tune) 
    : __pool_base(__tune), _M_bin(0), _M_bin_size(1) { }

private:
    _Bin_record*         _M_bin;    //指向内存单元数组的首地址，数组中每个成员代表着不同内存块大小的内存单元信息
    size_t                     _M_bin_size;     //_M_bin数组的大小
    void _M_initialize();
};
 

 其中重点在于内存池的结构建立、内存块的申请和回收。

内存池的初始化

先讲讲内存池的建立，前面已经讲到，基类__pool_base定义了一个_M_binmap指针变量，指向一个_Binmap_type数组，这个数组主要用来建立申请的内存块大小和_M_bin数组下标的映射关系，

数组的范围从0到_S_max_bytes（默认128），数组的值 为_M_bin数组的下标（从0到_M_bin_size-1）。_M_bin_size的值也是在这个映射关系建立的过程中计算出来的，而当_M_bin_size计算出后，

即可构建_M_bin数组。_M_binmap和_M_bin的建立都在_M_initialize()函数内实现。

void __pool<false>::_M_initialize()
{
    // _M_force_new在首次调用allocate后不能再修改，当_M_force_new为true时，不需建立下面的binMap映射和_M_bin
    if (_M_options._M_force_new)
    {
        _M_init = true;
        return;
    }

    // 要点1，根据 _M_max_bytes计算bin的个数，_M_bin_size 静态初始化为1.
    size_t __bin_size = _M_options._M_min_bin;
    while (_M_options._M_max_bytes > __bin_size)
    {
        __bin_size <<= 1;
        ++_M_bin_size;
    }

    // 要点2，建立binMap映射，以便快速定位到bin结构.
    const size_t __j = (_M_options._M_max_bytes + 1) * sizeof(_Binmap_type);
    _M_binmap = static_cast<_Binmap_type*>(::operator new(__j));
    _Binmap_type* __bp = _M_binmap;
    _Binmap_type __bin_max = _M_options._M_min_bin;
    _Binmap_type __bint = 0;
    for (_Binmap_type __ct = 0; __ct <= _M_options._M_max_bytes; ++__ct)
    {
        if (__ct > __bin_max)
        {
            __bin_max <<= 1;
            ++__bint;
        }
        *__bp++ = __bint;
    }

    // 要点3，初始化 _M_bin及其成员结构
    void* __v = ::operator new(sizeof(_Bin_record) * _M_bin_size);
    _M_bin = static_cast<_Bin_record*>(__v);
    for (size_t __n = 0; __n < _M_bin_size; ++__n)
    {
        _Bin_record& __bin = _M_bin[__n];
        __v = ::operator new(sizeof(_Block_record*));
        __bin._M_first = static_cast<_Block_record**>(__v);
        __bin._M_first[0] = 0;
        __bin._M_address = 0;
    }
    _M_init = true;
}

 现为方便理解代码，假定_M_options均为默认值，即_M_options._M_min_bin = 8，_M_options._M_max_bytes = 128，经过要点1的代码，循环遍历后，计算出_M_bin_size = 5。经过要点2的代码，_M_binmap数组的大小为129，得出如下映射：

_M_binmap[0]~_M_binmap[8] = 0;　　_M_binmap[9]~_M_binmap[16] = 1;　　_M_binmap[17]~_M_binmap[32] = 2;　　_M_binmap[33]~_M_binmap[64] = 3;　　_M_binmap[65]~_M_binmap[128] = 4; 其值对应着_M_bin数组的下标索引。

可清晰可见，当申请的内存块大小在2^(n-1) + 1 ~ 2^n，均能坐落在同一下标，即同一_M_bin。

当经过要点3的代码，可建立_M_bin数组，数组大小为5。由于是单线程，__bin._M_first数组大小仅为一个，故这里仅new了一个_Block_record*的大小的内存，并让__bin._M_first指向new出来的内存。

 内存块的分配

_M_initialize()函数仅建立_M_binmap映射和_M_bin内存单元结构，真正的内存块（分配给上层应用的）并未在这里申请，而是在_M_reserve_block()函数调用的时侯。allocate()会检查_M_binmap._M_first[0]，判断是否调用_M_reserve_block()。

allocate()函数内部会调用_M_initialize()和_M_reserve_block()函数。_M_reserve_block()函数的实现如下

char* __pool<false>::_M_reserve_block(size_t __bytes, const size_t __thread_id)
{
    // 通过binMap映射和申请的内存块大小__bytes，快速定位到bin结构（__bytes会向上取整，找到对应的2的幂次大小的内存块）
    const size_t __which = _M_binmap[__bytes];
    _Bin_record& __bin = _M_bin[__which];
    
    //计算可分割的内存块个数，由下可见是将大块内存chunk分割为若干小块block，每块长度为__bytes对应的2的幂次大小
    const _Tune& __options = _M_get_options();
    const size_t __bin_size = (__options._M_min_bin << __which) + __options._M_align;
    size_t __block_count = __options._M_chunk_size - sizeof(_Block_address);
    __block_count /= __bin_size;

    // 动态申请内存大块chunk，chunk前预留一个_Block_address结构，用来存放内存大块的地址信息，
    // _Block_address结构内的_M_Next指针用来建立链表结构，此处是将新申请的内存大块插入链表头
    void* __v = ::operator new(__options._M_chunk_size);
    _Block_address* __address = static_cast<_Block_address*>(__v);
    __address->_M_initial = __v;
    __address->_M_next = __bin._M_address;
    __bin._M_address = __address;

    //建立内存块的链表结构，链表的头节点为__bin._M_first[__thread_id]
    char* __c = static_cast<char*>(__v) + sizeof(_Block_address);
    _Block_record* __block = reinterpret_cast<_Block_record*>(__c);
    __bin._M_first[__thread_id] = __block;
    while (--__block_count > 0)
    {
        __c += __bin_size;
        __block->_M_next = reinterpret_cast<_Block_record*>(__c);
        __block = __block->_M_next;
    }
    __block->_M_next = 0;

    //这里从链表中取出头节点，作为用户申请的内存返回
    __block = __bin._M_first[__thread_id];
    __bin._M_first[__thread_id] = __block->_M_next;

    // 返回内存块的实际可用地址，出于内存对齐要求，内存块首部的align部分不可用，即使sizeof(_Block_record) < _M_align.
    return reinterpret_cast<char*>(__block) + __options._M_align;
}

前面讲到内存池特性的时候，结构体Tune内_M_align大小必须大于sizeof(_Block_record)，原因便在于此，最后返回给用户的内存需要加上_M_align的偏移，才不会破坏_Block_record建立的链表结构。

_M_reserve_block()函数在当空闲链表为空时调用，会一次申请足够大小的内存块（_M_options._M_chunk_size），分割内存小块，建立好链表结构，并把头节点内存块返回。

当空闲链表的最后一块内存小块取出后，__bin._M_first[__thread_id]重新指向NULL，后面若用户需要重新申请内存，会再一次调用_M_reserve_block()函数执行如上操作，将新申请的内存大块（chunk）

地址信息插入_Block_address构建的链表头。

每一个内存大块（chunk）首部都会预留一个_Block_address结构，其_M_Next指针将每个内存大块地址信息串联起来形成链表。后续内存池的销毁操作_M_destroy()也是依靠此链表逐一来释放内存。

内存块的回收

与_M_reserve_block()函数相对的是_M_reclaim_block()函数，负责内存块的回收，实现如下

void __pool<false>::_M_reclaim_block(char* __p, size_t __bytes) throw ()
{
    // 通过binMap映射和申请的内存块大小__bytes，快速定位到bin结构
    const size_t __which = _M_binmap[__bytes];
    _Bin_record& __bin = _M_bin[__which];

    // 申请的时候加上_M_align偏移，这里回收自然要减去
    char* __c = __p - _M_get_align();
    _Block_record* __block = reinterpret_cast<_Block_record*>(__c);

    // 单线程对应的链表头节点为__bin._M_first[0]，这里将回收的内存块放回链表头
    __block->_M_next = __bin._M_first[0];
    __bin._M_first[0] = __block;
}

内存池资源回收

与_M_initialize()相对的是_M_destroy()函数，负责整个内存池资源的回收（包括映射表的回收和内存单元结构的回收，内存块的回收等）。

void __pool<false>::_M_destroy() throw()
{
    if (_M_init && !_M_options._M_force_new)
    {
        for (size_t __n = 0; __n < _M_bin_size; ++__n)
        {
            //循环遍历，释放内存块
            _Bin_record& __bin = _M_bin[__n];
            while (__bin._M_address)
            {
                _Block_address* __tmp = __bin._M_address->_M_next;
                ::operator delete(__bin._M_address->_M_initial);
                __bin._M_address = __tmp;
            }
            ::operator delete(__bin._M_first);
        }
        //释放_M_binmap和_M_bin结构
        ::operator delete(_M_bin);
        ::operator delete(_M_binmap);
    }
}

 五、内存池的策略类实现

在分析多线程场景内存池实现前，先看看mt_allocator空间配置器的另一组件，内存池的策略类。

mt_allocator空间配置器提供了两个不同的策略类，每一个都可以与任何类型的基础池数据一起使用。

第一个策略_common_pool_policy实现了一个公共池。这意味着使用不同类型（比如char和long）实例化的分配器将使用同一个池。这是默认策略。

template