STL容器默认的内存分配器（std::alloc）

STL中的容器类的class templates，最后一个template parameter就是alloc，而默认值便是std::alloc。对象构造前的空间配置与对象析构后的空间释放，由<bits/stl_alloc.h>负责，SGI设计此库时，主要有以下几个考虑因素：

1. 向heap申请空间
2. 考虑线程安全
3. 内存不足时的应变措施
4. 考虑因“小内存区块”的释放后可能造成的内存碎片（fragment）问题

考虑到当前目标是要了解std::alloc的功能逻辑与实现结构，所以为了简单明了一些，（2.）线程安全先排除不做考虑。

 

针对（1.）C++有以下两种方式可以配置内存空间。

1. ::operator new() 与 ::operator delete();
2. malloc() 与 free()；

所以，SGI分别声明了使用方式（1）的new_alloc类和使用方式（2）的malloc_alloc_template模板类。

1. new_alloc

/**
   *  A new-based allocator, as required by the standard.  Allocation and
   *  deallocation forward to global new and delete.  "SGI" style, minus
   *  reallocate().
   *  @endmaint
   *  (See @link Allocators allocators info @endlink for more.)
  */
  class __new_alloc 
  {
  public:
    static void* 
    allocate(size_t __n)
    { return ::operator new(__n); }
    
    static void 
    deallocate(void* __p, size_t)
    { ::operator delete(__p); }
  };

 2. template<int __inst> class malloc_alloc_template.

 
/**
   *  @maint
   *  A malloc-based allocator. 
   */

template <int __inst>
    class __malloc_alloc_template 
    {
    private:
      static void* _S_oom_malloc(size_t);
      static void* _S_oom_realloc(void*, size_t);
      static void (* __malloc_alloc_oom_handler)();
      
    public:
      static void* 
      allocate(size_t __n)
      {
	void* __result = malloc(__n);
	if (0 == __result) __result = _S_oom_malloc(__n);
	return __result;
      }

      static void 
      deallocate(void* __p, size_t /* __n */)
      { free(__p); }

      static void* 
      reallocate(void* __p, size_t /* old_sz */, size_t __new_sz)
      {
	void* __result = realloc(__p, __new_sz);
	if (0 == __result) __result = _S_oom_realloc(__p, __new_sz);
	return __result;
      }
      
      static void (* __set_malloc_handler(void (*__f)()))()
      {
	void (* __old)() = __malloc_alloc_oom_handler;
	__malloc_alloc_oom_handler = __f;
	return(__old);
      }
    };

针对内存碎片的考虑，SGI设计了双层内存配置器，一级配置器就是上述定义两个类中的一个（取决于系统是否定义了宏USE_MALLOC，如果定义了那么使用malloc_alloc_template，否则使用new_alloc。 二级配置器，逻辑上是一个内存池。如果申请的内存大于128字节的话，那么这样申请由一级配置器处理。只有小于128字节的请求会有二级配置器处理。

 

二级内存配置器（memory pool）的数据结构采用的是freelist的数组，其实这个数据结构实际上就是一个邻接表（表示‘图’的数据结构之一），只是组成数据结构的数据类型所表示的实际意义发生了一些变化。

 

数组的长度是16（128÷8=16），每个数组元素指向一个freelist头节点，所以memory pool实际上就是16个freelists。每个freelist是一个单链表，单链表中的每个结点代表固定字节数的内存块。比如第一个freelist（数组的头元素指向的freelist），表示由表示容量为8字节的内存块结点组成的单链表。那么按照数组顺序，依次代表的是16，24，32，40，48，56，64，72，80，88，96，104，112，120，128字节的freelist。freelist的节点数据类型是一个union，如下声明。

union obj {
    union obj *free_list_link;
    char client_data[1];
}; 

union数据类型具有多面性，按照上述的声明，自然具有两面性了。当节点所代表的内存块属于memory pool中的空闲内存块时，就是free_list_link，指向下一个内存块（像单链表一样）；当节点所代表的内存块已经分配给用户时，就是client_data啦。

 

memory pool还有两个指针（s_start_free 和 s_end_free) 用于计算空闲内存块的大小，还有size_t的变量heap_size用于记录当前memory pool总容量。memory pool可提供的操作主要是如何根据实际内存请求从memory pool中拨出内存(s_chunk_alloc(size_t size, int& nobjs); )，以及根据内存释放请求归还内存块到memory pool中。

 

s_chunk_alloc函数是二级内存配置器的核心函数，因为二级配置器default_alloc_template的allocate接口实现都是高度依赖此函数的实现。s_chunk_alloc也是default_alloc_template的业务逻辑核心。

 

  // We allocate memory in large chunks in order to avoid fragmenting the
  // malloc heap (or whatever __mem_interface is using) too much.  We assume
  // that __size is properly aligned. （内存对齐） We hold the allocation lock.

    template<bool __threads, int __inst>
    char*
    __default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size, 
								int& __nobjs)
    {
       char* __result; // 预返回的内存块儿首址
       size_t __total_bytes = __size * __nobjs; 
      
       /* 预分配的内存块总大小，通常情况下nojbs的大小为20,
        * nobjs的大小由s_refill函数传进。
        */ 

      size_t __bytes_left = _S_end_free - _S_start_free; 
      //memory pool剩余内存块大小
      
      if (__bytes_left >= __total_bytes)  
      /* I: 如果memory pool剩余内存块完全满足需求量 */
      {
           __result = _S_start_free; 
           //则将剩余内存块儿的首地址作为结果返回
           _S_start_free += __total_bytes; 
           //将剩余内存块儿的首地址变为增加需求量之后的地址
           return(__result); 
      } 
      else if (__bytes_left >= __size) 
      /* II:如果剩余内存空间不足需求量，但是足够供应一个size大小的内存块 */
      {
           __nobjs = (int)(__bytes_left/__size); 
           //重新计算nobjs
           __total_bytes = __size * __nobjs; 
           //改变整体预分配内存的大小
           __result = _S_start_free; 
          // 返回分配的内存地址为当前剩余内存的首址
           _S_start_free += __total_bytes; 
          //改变剩余内存的首址为增加了分配内存块后的地址
          return(__result);
       } 
      else 
      /* III：memory pool剩余的空间连一个区块的大小也无法提供 */
      {
            size_t __bytes_to_get = 
            2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
	    /* 扩大需要量， 新需求量是原需求量的二倍与现有内存池大小的四分之一之和 */
            if (__bytes_left > 0) 
            /* 如果内存池还有残余的零头内存，处理零头内存 */
           {
                _Obj* volatile* __my_free_list =
                _S_free_list + _S_freelist_index(__bytes_left); 
                //寻找监管残余内存的freelist
	      
                ((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list; 
                	      
                *__my_free_list = (_Obj*)_S_start_free; 
                /* 归还那些因不足实际需求大小的内存块到监管的freelist中 */
             }

           _S_start_free = (char*) __mem_interface::allocate(__bytes_to_get); 
           // 请求一级内存配置器分配空间
           if (0 == _S_start_free) 
          //如果一级配置器分配失败
          {
              size_t __i;
              _Obj* volatile* __my_free_list;
              _Obj* __p;
              __i = __size;
              
              for (; __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_free_list_link;

                      /* 以下三行比较巧妙，__bytes_left = __i; 
                       * 通过递归调用s_chunk_alloc(size， nobjs)后走II分支
                       * 找到freelist中未必使用的内存区块，且这个区块足以大于client的实际需求。
                       */ 
                      _S_start_free = (char*)__p;  
                      _S_end_free = _S_start_free + __i;
                      return(_S_chunk_alloc(__size, __nobjs));
                  }
              }
             
             /*以上for循环顺次查找每个freelist，看是否还有freelist监管的内存区块未被使用且足够大*/
              _S_end_free = 0;
              _S_start_free = (char*)__mem_interface::allocate(__bytes_to_get); 
             /*上述尝试若失败，通过一级配置器抛出bad_alloc异常 */  
           }
          _S_heap_size += __bytes_to_get; 
          //修改memory pool的总容量
          _S_end_free = _S_start_free + __bytes_to_get; 
          //修改内存池剩余空间大小
          return(_S_chunk_alloc(__size, __nobjs)); 
           /* 在一级内存分配器分配了申请的内存后，
            * 递归调用s_chunk_alloc后通过I分支处理分配内存。
            */
          }
     }

 

根据上述代码，s_chunk_alloc的主要逻辑实际上是处理三种情况：

I:    内存池剩余空间足以满足内存的分配请求（注意此时的接收到的内存分配请求是client需求量的20倍）；

       处理方法：直接从剩余空间中拨出需求量大小的内存区块。

II:   内存池剩余空间不足满足需求量，但是大于一个区块（client实际需求量）；

       处理方法：缩小需求量至内存池剩余空间按照client实际需求量的最大倍数，然后按照新需求量分配内存块返回；

III:  内存池剩余空间既不能满足需求量，也不能满足实际client需求量；

       处理方法：

1. 先调整内存池中零头的内存块，使其归为到对应的freelist中。
2. 请求一级内存配置器分配扩大后需求量。注意，扩大后的需求量是原始需求量的二倍与内存池大小的四分之一的和那么大。
3. 如果一级内存配置器分配新需求量失败，试图在已分配但未使用的内存块（freelist）中寻找足以大于实际client需求的内存分配内存块返回给客户。
4. 如果步骤3失败，再向一级内存配置器请求帮助，如果帮助未果则利用一级内存配置器抛出异常bad_alloc。
5. 如果一级内存配置器分配请求成功后，递归调用自己走I情况分配内存块。

在了解上述memory pool分配内存块的基本逻辑后，还需要进一步了解s_refill函数。因为二级内存配置器的allocate函数实现是s_refill与s_chunk_alloc两个实现的协作实现。

 

s_refill模板函数的实现

  // Returns an object of size __n, and optionally adds to "size
  // __n"'s free list.  We assume that __n is properly aligned.  We
  // hold the allocation lock.
  
 template<bool __threads, int __inst>
    void*
    __default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
   {
      int __nobjs = 20; 
      //默认20个，实际client需求的20倍
      char* __chunk = _S_chunk_alloc(__n, __nobjs);
      //请求memory pool分配内存块，实际需求的20倍
      _Obj* volatile* __my_free_list;
      _Obj* __result;
      _Obj* __current_obj;
      _Obj* __next_obj;
      int __i;
      
     if (1 == __nobjs) return(__chunk);
    
     __my_free_list = _S_free_list + _S_freelist_index(__n);
      
     __result = (_Obj*)__chunk; 
     //将返回给客户20块内存区块的第一块地址
    *__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
     //修改监管freelist的首地址为第一个空闲内存块的地址

    for (__i = 1; ; __i++) {
        __current_obj = __next_obj;
        __next_obj = (_Obj*)((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;
        }
    }

    //上述for循环，是将freelist中的各结点串接起来。

     return(__result);
 }

  最后我们看看二级内存配置器是如何完成内存配置服务的。

 static void* 
    allocate(size_t __n)
    {
      void* __ret = 0;
      
      if (__n > (size_t) _MAX_BYTES) 
      // 如果请求大于128字节，由一级内存配置器分配内存
	__ret = __mem_interface::allocate(__n);
      else 
      // 当内存请求小于等于128字节时
	{
           _Obj* volatile* __my_free_list = _S_free_list 
             + _S_freelist_index(__n);
	  //定位监管的freelist

          _Obj* __restrict__ __result = *__my_free_list;
          if (__result == 0)
          //如果freelist是空的，则通过调用s_refill分配freelist
	    __ret = _S_refill(_S_round_up(__n));
	  else 
          //如果freelist有空闲内存块，则返回一个空闲块给客户
          //同时监管freelist的头指针后移一个空闲块
          {
              *__my_free_list = __result -> _M_free_list_link;
              __ret = __result;
          }
      }
      return __ret;
};

 

下面举个例子，假设程序一开始，二级内存配置器相继收到如下内存请求：

 256字节， 32字节， 32字节，64字节，48字节， 48字节；

1. 256字节：因为其大小大于128字节，则由一级内存配置器直接分配大块内存256字节给客户。

2. 32字节：小于128字节，二级配置器接管请求；找到监管freelist是第4个，数组下标#3， 发现freelist是空；则进一步调用s_refill申请内存；此时s_refill（32）接收到请求后，调用s_chunk_alloc(32, 20)先完成内存池中第四个freelist的分配；

      2.1. s_chunk_alloc(32,20)被调用后，内存池是空的，于是直接请求一级内存配置器分配640字节的内存块给内存池。

      2.2 一级内存配置器完成分配后，返回给内存池，内存池将此640字节大小的内存块首地址记录到s_start_free指针，同时修改内存池大小，并记录空闲内存块的尾指到s_end_free指针。

      2.3 递归调用s_chunk_alloc(32, 20), 此时内存池的空闲内存块是640字节，大于320字节，所以程序处理流程进入I分支。I分支会将这640字节的内存块分成320字节的两大块，前320字节那块作为结果返回，后320字节作为内存池的空闲内存块，s_start_free的地址修改指向后320字节内存块的首地址。

      2.4 s_refill此时接收到调用s_chunk_alloc(32, 20)返回的结果后，将320字节内存块分成20块，第一个32字节内存块作为客户请求返回，其余的19个32字节内存块依次串接起来作为第4个freelist监管起来。

3. 32字节：小于128字节，二级配置器接管请求；找到监管freelist是第4个，数组下标#3，发现freelist已分配；此时，直接将freelist中的第一个32字节的内存块（余下19个32字节内存块中的第一个，相当于初始分配的20个内存块中的第二个）返回给客户，同时监管的freelist指向余下的18个内存块。

4. 64字节：小于128字节，二级配置器接管请求。定位监管freelist是第8个，数组下标#7，为空。调用s_refill（64）。同样，s_refill调用s_chunk(64, 20);

      4.1. s_chunk_alloc(64, 20)被调用后，内存池的空闲内存块大小是320字节，注意此时需求量是1280字节。

      4.2. 因为320字节小于1280字节，但又大于64字节，所以满足II分支的条件。

      4.3. II分支先在内存池中修改需求量到320字节，nobjs由原来的20变为5. 将空闲的320字节内存块首址作为结果返回，同时内存池已经没有空闲内存块了。

      4.4. 同样，s_refill得到结果后，将320字节的内存块分成5块，第一个64字节内存块作为响应客户的64字节请求返回，而余下的4块串接起来作为第8个freelist监管起来。

5. 48字节：小于128字节，二级配置器接管请求。定位监管freelist是第6个，数组下标#5，为空。调用s_refill(48)。

同样，s_refill调用s_chunk(48,20)。

      5.1. s_chunk_alloc(48,20)被调用后，内存池空闲内存块是0字节，需求量是960字节，实际需求是48字节。

      5.2. 因为空闲内存块是0字节，所以进入分支III。

      5.3. 分支III，请求一级配置器帮助分配1920字节的内存块，但是我们假定现在一级内存配置器分配内存失败。

          5.4.1. 此时，分支III从监管48字节的freelist开始，循环随后每一个freelist，略过第8个freelist之前2个空freelist。

          5.4.2. 第8个freelist不空，将内存池的空闲内存块设置成freelist监管的4个64字节内存块中的第一个，然后递归调用s_chunk_alloc(48, 20);

          5.4.3. 此时内存池空闲内存大小是64字节，走分支II。

          5.4.4. 分支II，重新计算nobjs=1。此64字节的内存块的起始地址将作为结果返回，同时修改内存池空闲内存的起始地址到返回结果偏移48字节的地址。所以此时内存池的空闲地址是64-48=16字节。（注意此16字节就是零碎内存块了，这16字节的空闲内存，只有下次内存请求的时候会被归还。）

      5.4. s_refill得到结果后，直接将结果再返回给客户。

6. 48字节： 小于128字节，二级配置器接管请求。定位监管freelist是第6个，数组下标#5，为空。调用s_refill(48)。

同样，s_refill调用s_chunk(48,20)。

      6.1. s_chunk_alloc(48,20)被调用后，内存池空闲内存是16字节，需求量是960字节，实际需求是48字节。

      6.2. 所以走分支III。

      6.3. 分支III。

         6.3.1. 先将16字节的空闲内存归并到第2个freelist中。（相当于将空闲内存快作为freelist的头元素插入）

         6.3.2. 然后请求一级配置器帮助分配1920字节的内存块，但是仍然无功而返

         6.3.3. 从第6个freelist开始遍历，略过空freelist，直至第8个freelist。

         6.3.4. 第8个freelist不空，将内存池的空闲内存块设置成freelist监管的3个64字节内存块中的第一个，然后递归调用s_chunk_alloc(48, 20);

         6.3.5. 此时内存池空闲内存大小是64字节，走分支II。

         6.3.6. 分支II，重新计算nobjs=1。此64字节的内存块的起始地址将作为结果返回，同时修改内存池空闲内存的起始地址到返回结果偏移48字节的地址。所以此时内存池的空闲地址是64-48=16字节。

static void 
    deallocate(void* __p, size_t __n)
    {
      if (__n > (size_t) _MAX_BYTES)
	__mem_interface::deallocate(__p, __n);
      else 
	{
	  _Obj* volatile*  __my_free_list
	    = _S_free_list + _S_freelist_index(__n);
	  _Obj* __q = (_Obj*)__p;
	  
	  __q -> _M_free_list_link = *__my_free_list;
	  *__my_free_list = __q;
	}
    }

 

         6.3.7. s_refill得到结果后，直接将结果再返回给客户。

 

以上便是二级内存配置器的内存分配请求逻辑；下面的deallocate相对来说，就简单至极了。寻找的监管的freelist，然后通过修改指针，归并释放的内存块到监管的freelist即可。注意归还的时候，都是作为freelist的头元素插入到freelist中的。

 

小结：

       感觉freelist的内存分配方式，内存利用率不高。

       不知道通过什么方式可以比较一下std::alloc的执行效率 。