STL源码解析-空间配置器

STL中非常重要的一个模块就是空间配置器，用来管理程序内存的。

空间配置器

template <class _Tp, _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Tp>) >
class vector : protected _STLP_PRIV _Vector_base<_Tp, _Alloc>

这是stl源码中的vector的定义，实际上使用者是可以通过模板来指定空间配置器的

空间配置器源码解析

本文中的源码均是以stlport的代码为准

默认的空间配置器

  STLport默认提供的空间配置器是std::allocator，定义在_alloc.h中

#if defined (_STLP_USE_PERTHREAD_ALLOC)

_STLP_END_NAMESPACE
// include additional header here
#  include <stl/_pthread_alloc.h>
_STLP_BEGIN_NAMESPACE

typedef __pthread_alloc __alloc_type;
#elif defined (_STLP_USE_NEWALLOC)
typedef __new_alloc __alloc_type;
#elif defined (_STLP_USE_MALLOC)
typedef __malloc_alloc __alloc_type;
#else
typedef __node_alloc __alloc_type;
#endif

#if defined (_STLP_DEBUG_ALLOC)
typedef __debug_alloc<__alloc_type> __sgi_alloc;
#else
typedef __alloc_type __sgi_alloc;
#endif

_Tp* allocate(size_type __n, const void* = 0) {
  if (__n > max_size()) {
    _STLP_THROW_BAD_ALLOC;
  }
  if (__n != 0) {
    size_type __buf_size = __n * sizeof(value_type);
    _Tp* __ret = __REINTERPRET_CAST(_Tp*, __sgi_alloc::allocate(__buf_size));
#if defined (_STLP_DEBUG_UNINITIALIZED) && !defined (_STLP_DEBUG_ALLOC)
    memset((char*)__ret, _STLP_SHRED_BYTE, __buf_size);
#endif
    return __ret;
  }

  return 0;
}

在_alloc.h中通过宏定义的方式来区分，在mac电脑上看了一下没有相关的宏定义，所以最终的实现应该是在__node_alloc中

_STLP_USE_MALLOC

这个宏定义是最简单的空间配置器，虽然编译不是这个，但是先从这个来分析

class _STLP_CLASS_DECLSPEC __malloc_alloc {
public:
  // this one is needed for proper simple_alloc wrapping
  typedef char value_type;
  static void* _STLP_CALL allocate(size_t __n)
#if !defined (_STLP_USE_NO_IOSTREAMS)
  ;
#else
  {
    void *__result = malloc(__n);
    if (__result == 0) {
      _STLP_THROW_BAD_ALLOC;
    }
    return __result;
  }
#endif

  static void _STLP_CALL deallocate(void* __p, size_t /* __n */) { free((char*)__p); }
#if !defined (_STLP_USE_NO_IOSTREAMS)
  static __oom_handler_type _STLP_CALL set_malloc_handler(__oom_handler_type __f);
#endif
};

最简单的空间配置器实现就是基于malloc和free来实现的

__node_alloc

这应当是在macbook上编译真正用到的空间配置器

第一层配置器

#  if defined (__OS400__)
// dums 02/05/2007: is it really necessary ?
enum { _MAX_BYTES = 256 };
#  else
enum { _MAX_BYTES = 32 * sizeof(void*) };
#  endif

#if ((defined (__IBMCPP__) || defined (__OS400__) || defined (__xlC__) || defined (qTidyHeap)) && defined (_STLP_DEBUG_ALLOC))
inline void* _STLP_CALL __stl_new(size_t __n)   { _STLP_CHECK_NULL_ALLOC(::operator new(__n, __FILE__, __LINE__)); }
inline void  _STLP_CALL __stl_delete(void* __p) { ::operator delete(__p, __FILE__, __LINE__); }
#else
inline void* _STLP_CALL __stl_new(size_t __n)   { _STLP_CHECK_NULL_ALLOC(::operator new(__n)); }
inline void  _STLP_CALL __stl_delete(void* __p) { ::operator delete(__p); }
#endif


class _STLP_CLASS_DECLSPEC __node_alloc {
  static void * _STLP_CALL _M_allocate(size_t& __n);
  /* __p may not be 0 */
  static void _STLP_CALL _M_deallocate(void *__p, size_t __n);

public:
  // this one is needed for proper simple_alloc wrapping
  typedef char value_type;
  /* __n must be > 0      */
  static void* _STLP_CALL allocate(size_t& __n)
  { return (__n > (size_t)_MAX_BYTES) ? __stl_new(__n) : _M_allocate(__n); }
  /* __p may not be 0 */
  static void _STLP_CALL deallocate(void *__p, size_t __n)
  { if (__n > (size_t)_MAX_BYTES) __stl_delete(__p); else _M_deallocate(__p, __n); }
};

可以看出在实际上空间配置器是分两层的，256字节以上调用的是stl:delete和stl:new函数，没有做什么特殊的封装

第二层配置器

第二层配置器就是_M_allocate和_M_deallocate两个函数的实现了，就是对__node_alloc_impl的封装

内存池的实现

struct _Node_alloc_obj {
  _Node_alloc_obj * _M_next;
};

_Node_alloc_obj * _STLP_VOLATILE
__node_alloc_impl::_S_free_list[_STLP_NFREELISTS]
= {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

注：以上代码和真正的源码略有不同，因为涉及到一些宏定义的区别，这里不纠结于这些宏定义

_S_free_list是一个长度为16的数组，数组的每个位置上都存放的是一个链表的节点，每一个节点代表一个内存池。

_Node_alloc_obj只有一个指向Next的指针，不过这实际上是把空间块的头部作为链表节点的形式便于存储

void* __node_alloc_impl::_M_allocate(size_t& __n) {
  //将空间向上扩展为16的整数倍
  __n = _S_round_up(__n);
  //_S_FREELIST_INDEX(__n)进行的动作就是除以16
  _Obj * _STLP_VOLATILE * __my_free_list = _S_free_list + _S_FREELIST_INDEX(__n);
  _Obj *__r;

  _Node_Alloc_Lock __lock_instance;

  if ( (__r  = *__my_free_list) != 0 ) {
    *__my_free_list = __r->_M_next;
  } else {
    __r = _S_refill(__n);
  }
#  if defined (_STLP_DO_CLEAN_NODE_ALLOC)
  _S_alloc_call();
#  endif
  // lock is released here
  return __r;
}

• 首先，每次分配空间是会增长到16的整数倍来分配
• 其次，从寻址方式可以看出_S_free_list的16个链表分别负责不同大小空间块的分配：16、32、48、64。。。。。。
• 如果有free_list中还有空间的话直接从中获取，否则就调用_S_refill重新分配空间

_Node_alloc_obj* __node_alloc_impl::_S_refill(size_t __n) {
  int __nobjs = 20;
  //从内存池中获取20个内存块
  char* __chunk = _S_chunk_alloc(__n, __nobjs);

  if (1 == __nobjs) return __REINTERPRET_CAST(_Obj*, __chunk);

  _Obj* _STLP_VOLATILE* __my_free_list = _S_free_list + _S_FREELIST_INDEX(__n);
  _Obj* __result;
  _Obj* __current_obj;
  _Obj* __next_obj;

  __result = __REINTERPRET_CAST(_Obj*, __chunk);
  *__my_free_list = __next_obj = __REINTERPRET_CAST(_Obj*, __chunk + __n);
  for (--__nobjs; --__nobjs; ) {
    __current_obj = __next_obj;
    __next_obj = __REINTERPRET_CAST(_Obj*, __REINTERPRET_CAST(char*, __next_obj) + __n);
    __current_obj->_M_next = __next_obj;
  }
  __next_obj->_M_next = 0;
  return __result;
}

在空间不够的时候，会调用_S_refill新创建20个对应大小的空间放到对应链表上，不过这时调用的也不是malloc接口而是还有一层

内存池空间分配

1. 首次进行空间分配

   char *__node_alloc_impl::_S_start_free = 0;
   char *__node_alloc_impl::_S_end_free = 0;
   
   inline char* __stlp_new_chunk(size_t __bytes)
   { return __STATIC_CAST(char*, _STLP_STD::__stl_new(__bytes)); }
   
   char* __node_alloc_impl::_S_chunk_alloc(size_t _p_size, int& __nobjs) {
     char* __result;
     size_t __total_bytes = _p_size * __nobjs;
   
    ......
     
     //长度其实没变
     size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size) + _STLP_OFFSET;
   
     _STLP_TRY {
       _S_start_free = __stlp_new_chunk(__bytes_to_get);
     }
    //除以16
     _S_heap_size += __bytes_to_get >> 4;
   
     _S_end_free = _S_start_free + __bytes_to_get;
     _S_start_free += _STLP_OFFSET;
     return _S_chunk_alloc(_p_size, __nobjs);
   }
   

   • 从代码可以看到，大块的空间分配最终还是使用基础的new来做；
   • 内存的管理使用_S_start_free和_S_end_free来管理，分别指向空间的开头和结尾

2. 空间分配失败的异常处理

     _STLP_TRY {
       _S_start_free = __stlp_new_chunk(__bytes_to_get);
     }
   #if defined (_STLP_USE_EXCEPTIONS)
     catch (const _STLP_STD::bad_alloc&) {
       _Obj* _STLP_VOLATILE* __my_free_list;
       _Obj* __p;
       
       //从free_list查看是否有比这个大的内存块可以给出来用
       for (size_t __i = _p_size; __i <= (size_t)_MAX_BYTES; __i += (size_t)_ALIGN) {
         __my_free_list = _S_free_list + _S_FREELIST_INDEX(__i);
         __p = *__my_free_list;
         if (0 != __p) {
           *__my_free_list = __p -> _M_next;
           _S_start_free = __REINTERPRET_CAST(char*, __p);
           _S_end_free = _S_start_free + __i;
           return _S_chunk_alloc(_p_size, __nobjs);
         }
       }
       
       //直接再次尝试
       __bytes_to_get = __total_bytes + _STLP_OFFSET;
       _S_start_free = __stlp_new_chunk(__bytes_to_get);
     }
   #endif
   

   • free_list中有16个不同大小的内存块链表，当空间分配失败时会尝试从这之中获取空间来用

3. 从分配好的空间中拿空间

     size_t __bytes_left = _S_end_free - _S_start_free;
     //如果足够分配20个节点的空间直接返回
    if (__bytes_left > 0) {
       if (__bytes_left >= __total_bytes) {
         __result = _S_start_free;
         _S_start_free += __total_bytes;
         return __result;
       }
        //如果至少能够分配一个节点，则有多少分配多少
       if (__bytes_left >= _p_size) {
         __nobjs = (int)(__bytes_left / _p_size);
         __total_bytes = _p_size * __nobjs;
         __result = _S_start_free;
         _S_start_free += __total_bytes;
         return __result;
       }
   
       //如果一个都不够，则将剩下的零头放入free_list中，然后重新调用此函数来真正分配空间
       _Obj* _STLP_VOLATILE* __my_free_list = _S_free_list + _S_FREELIST_INDEX(__bytes_left);
       __REINTERPRET_CAST(_Obj*, _S_start_free)->_M_next = *__my_free_list;
       *__my_free_list = __REINTERPRET_CAST(_Obj*, _S_start_free);
       _S_start_free = _S_end_free = 0;
     }
   

   _S_end_free和_S_start_free存储的是空余空间的大小

   • 如果剩余空间足够，则直接返回即可，同时调整_S_start_free指向的地址
   • 如果剩余空间不够分配20个时，有多少返回多少
   • 如果连一个也不够分配，则将空余的空间放入到_S_free_list当中；然后走重新分配空间的逻辑

内存池空间的回收

void __node_alloc_impl::_M_deallocate(void *__p, size_t __n) {
  _Obj * _STLP_VOLATILE * __my_free_list = _S_free_list + _S_FREELIST_INDEX(__n);
  _Obj * __pobj = __STATIC_CAST(_Obj*, __p);

  //实际就是放入free_list当中去
  _Node_Alloc_Lock __lock_instance;
  __pobj->_M_next = *__my_free_list;
  *__my_free_list = __pobj;

#  if defined (_STLP_DO_CLEAN_NODE_ALLOC)
  _S_dealloc_call();
#  endif
  // lock is released here
}

内存池释放空间时直接放回到指定内存池中

__node_alloc_impl类的定义

class __node_alloc_impl {
  //将数字扩大到16的倍数
  static inline size_t _STLP_CALL _S_round_up(size_t __bytes)
  { return (((__bytes) + (size_t)_ALIGN-1) & ~((size_t)_ALIGN - 1)); }

  typedef _Node_alloc_obj       _Obj;
  typedef _Obj* _STLP_VOLATILE  _Freelist;
  typedef _Obj*                 _ChunkList;

private:
  //free_list不够时即调用此函数
  static _Obj* _S_refill(size_t __n);
  //真正内存池的分配器，调用malloc工作
  static char* _S_chunk_alloc(size_t __p_size, int& __nobjs);
  // 存储16个不同大小内存块的链表，16、32、48。。。。。。
  static _Freelist _S_free_list[_STLP_NFREELISTS];
    
  //暂时不理解意义在哪
  static size_t _S_heap_size;

  // 剩余空间的开头
  static char* _S_start_free;
  // 剩余空间的结尾
  static char* _S_end_free;


public:
  //分配空间
  static void* _M_allocate(size_t& __n);
  //释放空间
  static void _M_deallocate(void *__p, size_t __n);
};