STL源码Allocator学习

内存的分配需要解决的几个问题:

1. 向系统的heap空间请求空间;

2. 考虑多线程的状态问题;

3. 考虑内存空间不足时的应对策略;

4. 考虑过多“小内存块”的碎片问题。

SGI的STL底层使用malloc()和free()完成,分为两层内存分配配置器:

第一级主要处理相对内存大小较大的分配请求size>128B,第二级主要处理内存请求相对较小的分配请求。

第一级直接使用malloc和free函数分配内存,并配有类似C++的set_new_handler()来处理内存分配不足的特殊处理。

例如:

static void* allocate(size_t n)

{

  void * result = malloc(n);

  if (0 == result) 

    result = oom_malloc(n); // 内存不足时的处理函数

  return result;

}

// 内存不足时的处理函数片段

{

  for(;;)

  {

    my_malloc_handler = __malloc_alloc_oom_handler;

    if (0 == my_malloc_handler) {__THROW_BAD_ALLOC;} 

    (*my_molloc_handler)(); // 尝试释放内存操作

    result = malloc(n); // 再次尝试分配内存

    if (result) return result;

  }

}

SGI是用malloc而不是::operator new分配内存,主要可能是由于历史因素,另外,new没有realloc的功能;SGI不能使用C++的set_new_handler(),也是因为他没有使用::operator new,因此需要定义一个类似的功能,如上。

第二级维护16个内存自由链表(free_list),size从8B,16B,24B,...,128B的16个链表free_list,当用户请求内存时,从合适的链表给出内存,以解决小内存块产生的碎片,以防浪费。

free_list节点结构:

union obj

{

  union obj * free_list_link;

  char data[1]; // 实际内存

};  // 使用union定义节点,不至于像struct那样浪费一个指针的空间

内存池:

每个free_list维护一个链表,当链表空间不足时需要向内存池申请,如果内存池有内存,则尽可能的给出内存量给free_list[i],如果内存池已经空了,只能从系统的heap空间申请内存,此时申请的内存量一般为需求量的2倍+随配置次数增大的附加量。

如:free_list[5]没有内存了,需要从内存池中申请,此时内存池如果有标准量(如20),则给出20块;如果不够,则都给出,并返回给出的块数;然后1块交出,其余放入free_list[5]中链表维护.

如:free_list[9]没有内存了,从内存池申请时,内存池也没有了,则内存池向系统申请内存,大小为配置的两倍+x,成功则按上述方法分配;如果失败,则转由第一级配置器处理(可以处理内存不足时策略,如释放内存等)。

SGI的uninitialized_copy和uninitialized_fill:

在容器的构造中,分成两步:1. 分配足够大的内存空间; 2. 在每个位置上进行构造函数. 

uninitialized_copy和uninitialized_fill就是第二个步骤做的事情,将对应位置的内存进行构造,copy构造或用某个x构造。并且他们具有“commit or rollback”语义,即要么全初始化成功,要么就全初始化失败。

原文地址:https://www.cnblogs.com/codefinder/p/stl_source_code_001.html