空间配置器 allocator

在STL中，所有的元素都是存放在容器中，容器需要配置空间来储存这些数值，因此需要用到空间配置器。

概览

• SGI的空间配置器
  
  • SGI标准的空间配置器是allocator, 只是对基层内存配置/释放行为(对运算符new/delete)进行了一层薄薄的封装，没有考虑到效率上的优化。
  • SGI特殊的空间配置器是alloc，
    SGI以malloc()和free()完成内存的配置和释放。考虑到小型区块可能造成内存破碎问题，SGI设计了双层级配置器。第一层直接用malloc和free，第二级配置器视情况采用不同策略。如果配置区别大于128bytes，选用第一级配置器；当小于128bytes时，采用复杂的memory pool的整理方式。是否同时开放第二级配置器，取决于__USE_MALLOC是否被定义。

精细分工

• STL Allocator的精细分工
  stl_construct.h
  内存配置：allocate();
  内存释放前进行对象的析构：destroy()，调用析构函数;
  stl_alloc.h
  内存配置后进行对象的构造:construct(),placement new调用构造函数;
  内存释放: deallocate();
  stl_uninitialized.h
  定义一些全域函式，用来填充(fill)或者复制(copy)大块的内存内容。

• stl_construct.h
  construct()接收一个指针和一个初始值value，用途是将初值设定到指针所指的空间上
  destroy有两个版本，版本1接受一个指针，准备将该指针所指之物析构掉；版本2是接收first和last两个迭代器，将[first,last)范围内所有对象析构掉

• std::alloc(设置配置器)
  SGI用malloc和free这2个C函数代替完成内存的申请和释放。考虑到内存碎片问题，SGI设计了两级配置器，第一级直接使用malloc和free，包括了内存不足处理机制，需要调用者自己提供。第二级判断配置区超过128字节，调用第一级配置器。小于128字节，采用内存池管理
  
  

双层级配置器

• 第一级配置器
  __malloc_alloc_template
  SGI第一级配置器的allocate()和realloc()使用malloc与free来配置和释放内存。调用不成功后，会调用oom_malloc()和oom_realloc()。后两个函数都有内循环，不断调用“内存不足处理例程”，期待在某次调用后获得足够内存而圆满完成任务。设定“内存不足处理例程”是客端的责任。

• 第二级配置器
  __default_alloc_template
  当区块小于128byte，交由第二级配置器处理。用内存池(memory pool)来管理。也叫次层配置(sub-allocation)

  • 实现方式

    • 每次配置一大块内存，并维护对应的自由链表
    • 如果下次有相同大小的内存需求，就从free-list中拨出
    • 如果客端释放小额区块，就由配置器回收到free-list中
    • SGI第二级配置器会主动将任何小额区块的内存需求量上调至8的倍数。它维护16个free-lists，各自管理大小分别为8,16,24,32，…,128byte的小额区块。
    • 节点结构
      

      //利用union的性质使得链表既是指针又是实际区块
      union obj
      {
          union obj * free_list_link;
          char client_data[1];       //柔性数组
      };

  • 内存池
    chunk_alloc的工作：从内存池中取空间给free-list使用。

    if(内存池水量足够)
        直接调出20个区块给free list
    else if(内存池水量还足够提供至少1个区块)
        调出实际能够供应的区块
    else
        利用malloc()向堆heap中配置内存，为内存池注入源头活水以应付需求。一般申请为需求量的两倍，再加上随着配置次数增加而越来越大的附加量
        if(heap的空间也不够)
            malloc()失败，调用第一级配置器中的out of memory处理机制,或许有机会释放其内存拿来此处使用。如果可以就成功，否则发出bad_alloc异常。

相关问题

• STL里面空间分配是怎么样的？
  STL中用allocator类来实现空间分配，有一级配置器二级配置器,根据一个环境组态来确定使用哪一级的配置器。SGI STL将alloc设置为第二级配置器。

• 如果用让你写一个STL的空间配置器，这个配置器需要经常分配大量的小内存，但大量的分配小内存会造成内存碎片，你会怎么解决这个问题？那如果用你实现的配置器分配的空间是怎么释放的？
  参考：可以说一些二级配置器是怎么实现的，可以参照STL特有的空间配置器alloc的设计

  1. 针对于小内存的问题，可以像第二级配置器一样来实现，用内存池来管理。每次配置一大块内存，然后维护16个自由链表free-lists。每个链表会维护若干个小额区块，每个小额区块的大小是8的倍数。
  2. 如果自由链表里的小额区块不够了，利用chunk_alloc(size,num)，从内存池中取空间给free-list使用（参考上面的内存池内容）
  3. 如果客端申请需求量小于128byte，会将申请的内存需求量上调至8的倍数，然后再查找对应的自由链表中的小额区块。如果大于128byte，就用第一级配置器的allocate()函数，直接用malloc来配置内存。
  4. 释放内存时，如果释放量小于128byte，配置器会将它归还到对应的自由链表中。如果大于128byte，就用第一级配置器的deallocate()函数，直接用free来释放内存。

SGI空间配置器

SGI STL的每一容器都已经指定其缺省的空间配置器为alloc。例如：
vector的声明：
template<class T,class Alloc = alloc> //缺省
class vector {...};

我们所习惯的new/delete内存配置：

class Foo{...};
Foo* pf = new Foo; //配置内存然后分配对象
delete pf;//将对象析构然后释放
这其中包含两个阶段，调用::operator new配置内存，Foo::Foo()构造对象

为了精密分工，STL allocator决定将这俩个阶段操作分开来，alloc::allocate()/alloc::deallocate()/:construct()/:destory()/。并将配置器定义与memory头文件内。

construct

上述construct()接受一个指针p和一个value，该函数的用途就是将初值设定到指定的空间上去，用C++中的placement new来完成。

destroy

两个版本，第一个版本接受一个指针，然后将该指针指向之物析构掉。第二个版本接受范围的迭代器，将[first，last)范围内的所有对象全部析构掉，这里先用value_type()获得迭代器所指对象的类别，再用type_traits《T》判断该类别的析构函数是否无关痛痒。

当operator new申请一个内存失败的时候，它会进行如下的处理步骤：
1、如果存在客户指定的处理函数，则调用处理函数（new_handler），如果不存在则抛出一个异常。
2、继续申请内存分配请求。
3、判断申请内存是否成功，如果成功则返回内存指针，如果失败转向处理步骤1
一个设计良好的new_handler必须做以下事情：
1、删除其它无用的内存，使系统具有可以更多的内存可以使用，为下一步的内存申请作准备。
实现此策略的办法是：程序一开始执行就分配一大块内存，当new_handler被调用时，将它们释放还给程序使用。
2、设置另外一个new_handler。
如果当前的new_handler不能够做到更多的内存申请操作，或者它知道另外一个new_handler可以做到，则可以调用set_new_handler函数设置另外一个new_handler，这样在operator new下一次调用的时候，可以使用这个新的new_handler。
3、卸载new_handler，使operator new在下一次调用的时候，因为new_handler为空抛出内存申请异常。
4、new_handler抛出自定义的异常
5、不再返回，调用abort或者exit退出程序

第一级配置器源码剖析

重新填充Refill_Freelist

在allocate()分配内存发现freelist没有可用内存时，需要调用refill函数重新填充freelist,这些新的空间将从内存池中获得，一次分配20个节点或区块，当然如果内存池内存不足很有可能区块会小于20个。

//假设n已经上调至8的倍数
template<bool threads,int inst>
void* _default_alloc_template<threads,inst>::refill(size_t n){
      int nobjs = 20;
      char* chunk = chunk_alloc(n,nobjs);//nobjs传引用
      obj* volatile *my_free_list;
      if(1==nobjs) retrun(chunk);
      my_free_list = free_list + FREELIST_INDEX(n);
      obj* result;
      obj* current_obj, * next_obj;
      result = (obj*) chunk;//第一块给客端
      *my_free_list = next_obj = (obj*)(chunk+n);//剩下的串起来 
      for(int i=1;;i++){
          currnt_obj = next_obj;
            next_obj = (obj*)((char*)next_obj+n);
          if(nobj-1 == i){
             currnt_obj->free_list_link = 0;
             break;
          }else{
             currnt_obj->free_list_link = next_obj;
           } 
      }
      return (result);
}

内存池取空间的CHUNK_ALLOC>

chunk_alloc函数是以end_free-start_free来判断内存池是否还有可用内存，如果有则拨款20个nobjs，如若不足20但仍有超过一个需求大小的内存块，则把这些空间全部拨出去。这时候nobjs就变成了实际得到内存块。如果一个都无法配置，那么内存池将会调用malloc从heap上获取内存，内存量为需求量的2倍加上一个和配置次数成比例的附加量。举个例子：chunk_alloc(32,20)，这是第一次内存池没有内存，便向heap申请32*40的内存，其中1个给客端，19个给free_list维护，剩下的留给自己。这时候chunk_alloc(64,20),内存池还有32*20/64，也就是10个可用内存块，1个给客端，9个给相应的freelist维护。自己空空如也了，下次在申请就是2倍加附加量了。万一山穷水尽了，heap也没了，那么就调用第一级配置器，虽然他也是malloc,但是他有out_of_memory机制可以释放其他内存拿来用，失败了大不了喊一句bad_alloc；

//内存池chunk_alloc的实现，模板省略了
char* chunk_alloc(size_t size,int& nobjs){
      char* result;
      size_t total_bytes = size * nobjs;
      size_t  left_bytes = end_free - start_free;
      if(left_bytes >= total_bytes){
         //内存池完全够用
         result = start_free;
         start_free += total_bytes;
         return (result);
      }else if(left_bytes >= size){
               nobjs = left_bytes / size ;
               result = start_free;
               start_free += nobjs * size;
               return (result);
            }else{
             //内存池一个区块的大小都无法提供
              size_t bytes_to_get = 2 * total_bytes +                        ROUND_UP(heap_size>>4);
              if(left_bytes >0){
                 //内存池还有一点零头，先配置给合适的free_list
                 obj* volatile* my_free_list = free_list + FREELIST_INDEX(left_bytes);
                 ((obj*) start_free) -> free_list_link = *my_free_list;
                 *my_free_list = (obj*) start_free;
              }
              //在heap上配置空间，用来补充内存池
              start_free = (char*)malloc(byte_to_get);
              if(0==start_free){
                //heap空间失败，malloc()失败
                int i;
                obj* volatile* my_free_list,*p;
                //我们检视手上的东西，找到适当大小的未用内存，适当即为区块要足够大。
                for(i = size;i<=_MAX_BYTES;i += _ALLIN){
                    my_free_list = free_list + FREELIST_INDEX(i);
                    p = my_free_list;
                    if(0 != p){
                      //还有货，当然我们就拿1个区块
                       *my_free_list = p -> free_list_link;
                       start_free = (char*)p;
                         end_free = start_free + i;
                         //内存找到了，则递归重新配置修正nobjs
                       return (chunk_alloc(size,nobjs));
                    }
                }
                end_free = 0;
                start_free = (char*)malloc_alloc::allocate(bytes_to_get);
              }
              heap_size += bytes_to_get;
              end_free = start_free + bytes_to_get;
              return (chunk_alloc(size,nobjs));
             }
}

内存处理的基本工具

该函数会调用construct(&*(result + (i-first)),*i);如果你要实现一个容器的全区间构造函数，一般经过两个步骤，第一个配置内存空间，第二个调用copy();

该函数会调用construct(&*i,*i);

这里面value_type()判断迭代器所指是否为POD类型。POD为plane old data,包含标量型或C 里的结构体类型，对于POD类型必然拥有copy/assignment/dtor,因此我有更高效的初值填写手法。否则采用最保险的做法。