导言

在深入探索今天的内容前，你可以在心中思考思考下列问题：

当你调用new与delete时编译器底层的做了什么事情?
STL 各大容器底层空间配置器是什么样子的?
STL 的到底需要做什么样的实现?
什么是内存池及它的实现是怎样的？
…

STL六大组件

在深入空间配置器前，我觉得我们还是有必要先了解一下STL的基础知识
STL仅仅是一个标准，内部实现是没有任何要求的。因此导致STL存在许多的实现版本,PJ STL(被Visual C++)所采用。我们所学习的SGI STL版本注释丰富、结构清晰、可读性最强，所以最后被GCC所采用，同时也是最流行的版本。STL主要有六大组件来支撑着，它们是：

配置器(allocator): 为容器提供空间配置与释放，对象的构造与析构的服务,也是一个class template。
容器(containers): 常用的数据结构，大致分为两种序列容器与关联容器。在实现上是类模板。
迭代器(iterator): 一套访问容器的接口，行为类似于指针。它为不同的算法提供相对统一的容器访问方式，便利设计算法时无需过多关心数据。
算法(algorithms): 提供一套常用的算法，如sort、search、copy、erase ...。在实现上，可以认为是一种函数模板。
仿函数(functor): 作为函数使用的对象，用于泛化算法中的操作。
配接器(adapter): 将一种容器修饰为不同的另一种容器。
大致关系如下图所示

空间配置器

从STL使用的角度来说，空间配置器是最不需要介绍的东西。因为它们早已被容器封装好了，在一切组件后默默付出。但是从实用角度来说，若是不了解STL的空间配置器，无异于空中楼阁，在阅读其它STL实现时都会遇到困难。

专属配置器

对于SGI STL来说，很多的项目早已脱离了STL标准规格。因此，SGI STL使用了一个专属的、拥有次层配置(sub-allocation)能力的、效率卓越的特殊配置器的alloc。当然SGI STL也提供了一个默认的内存配置器为allocator,只不过在大部分情况下，我们很少使用这个效率不佳且仅做内存分配与释放的配置器。
alloc不同于allocator，它不接受任何参数，以vector为例，它的的标准写法如下：

1 2	template <class T, class Alloc = alloc> // 缺省使用alloc为配置器 class vector {...};

对象与内存

回到上面的问题，对于C++中new/delete的操作是怎样的？在日常使用中，我们所习惯的操作大致如下：

1
2
3

class Foo {...};
Foo* pf = new Foo;    // 配置内存，然后构造对象
delete pf;            // 将对象析构，然后释放内存

对于这里的new/delete算式都内含了两步的操作
new :调用::operator new 配置内存;调用Foo::Foo() 构造对象内容。
delete:调用对象Foo::~Foo()将对象析构;调用::operator delete 释放内存

为了精密分工，STL allocator 决定将这两个阶段分开
对于内存:分配时使用 alloc::allocate();释放时使用 alloc::deallocate()。
对于对象:构造时使用::construct();析构时使用::destroy();

大家可以通过下图来帮助理解与记忆

构造与析构

通过上图的理解，知道这两个函数是如何完成对象的构造与析构。接下来我们通过对其源码的剖析，对其作用加深理解。

源码阅读


#include <new.h>

template <class t1, class t2>
inline void construct(t1* p,const t2&value) {
  new (p) t1(value);    //placement new;调用t1::t1(value);
}

// destory()第一版本,仅接受一个指针
template <class t>
inline void destroy(t* pointer) {
  pointer->~t();     //调用destroy ~t(0)
}

// 以下都是destroy() 第二个版本以及它的特化
template<class forwarditerator>
inline void destory(forwarditerator first,forwarditerator last) {
  __destroy(first,last,value_type(first));
}

// 判断元素的数值类别(value type)是否有trivial destructor
template <class forwarditerator,class t>
inline void __destroy(forwarditerator first, forwarditerator last,t*) {
  typedef typename __type_traits::has_trival_destructor trivial_destructor;
  __destroy_aux(first,last,trivial_destructor());
}

//如果元素的数值类型有non-trival destructor...
template <class forwarditerator>
inline void
__destroy_aux(forwarditerator first,forwarditerator last,__false_type) {
  for (; first < last; ++first) 
    destroy(&*first);
}

// 如果元素的数值类型有trival destructor..
template <class forwarditerator>
inline void __destroy_aux(forwarditerator,forwarditerator,__true_type) {}

// 以下是destory()第二版本针对迭代器为char*与wchar_t*的特化版本
inline void destroy(char* ,char**) {}
inline void destroy(wchar_t*,wchar_t*) {}

源码分析

在STL源码中，construct()仅接受一个指针p与一个初值value。它的使用是将初值设定到指针所指向空间上。在C++中placement new运算子也可完成这一操作。

对于析构destroy则存在两个版本。第一个版本仅接受一个指针，准备将该指针所指向之物析构掉；第二个版本则是接受[first,last)两个迭代器，将范围内的对象析构掉。为了效率的考虑，调用类型萃取防止无效析构拖慢性能。在检查结束后，就会调用第一版本的destroy来析构对象。

空间配置核心

剖析完对象构造与析构的源码后，接下来我们一起深入内存的配置与释放之旅，了解空间配置器核心————alloc。

前言

对象构造前的空间配置与对象析构后的空间释放，全由<stl_alloc.h>负责，SGI对此的设计哲学如下：

向system heap要求空间
考虑多线程(multi-threads)状态
考虑内存不足的应变措施
考虑过多”小型区块”可能造成的内存碎片(fragment)问题

考虑到小型区块可能造成的内存破碎问题，SGI设计了双层级配置器。当配置区块>128bytes时，则采用一级配置器。当配置区块<128bytes时，则调用二级配置的memory pool来处理。
之前提及过，alloc这个次层配置、效率卓越的特殊配置器逸脱了STL标准。SGI为其包装了一个接口从而符合STL规格。下面是它们的定义与包装后的代码：


# ifdef __USER_MALLOC
...
typedef __malloc_alloc_template<0> malloc_alloc;
typedef malloc_alloc alloc;
# else
...

// 令 alloc 为二级配置器
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
#endif /* ! __USER_MALLOC */


template <class T,class Alloc>
class simple_alloc {
  public:
    static T *allocate(size_t n) 
    {return 0 == n ? 0 : (T*)  Alloc::allocate(n * sizeof(T));}
    static T *allocate(void) 
    {return (T*) Alloc::allocate(sizeof (T));}
    static void deallocate(T *p, size_t n) 
    {if (0 != n) Alloc::deallocate(p, n * sizeof(T));}
    static void deallocate (T *p) 
    {Alloc::deallocate(p,sizeof(T));}
};

一二级配置器关系

一二级配置器的包装接口与运用方式

一级配置器剖析

结合上图，让我们看看一级配置器是如何仿真C++ set_malloc_handler的。

// 定义部分

template <int inst>
class __malloc_alloc_template {
  private:
    // 以下是用来处理内存不足情况的
    // oom： out of memory;
    static void *oom_malloc(size_t);
    static void *oom_realloc(void* ,size_t);
    static void (* __malloc_alloc_oom_bandler) ();
  public:
    static void *allocate(size_t n) {
      void *result = malloc(n)  //一级配置器直接使用malloc()
      // 以下情况无法满足时，才会改用oom_malloc()
      if (0 == result) result = com_malloc(n);
      return result;
    }

    static void deallocate(void *p, size_t) {
      free(p) // 一级配置器直接使用free()
    }

    static void *reallocate(void *p,size_t ,size_t new_sz) {
      void *result = reallocate(p, new_sz);  // 一级配置器直接使用reallocate() 
      // 以下情况无法满足时，才会改用oom_realloc()
      if (0 == result) result = oom_realloc(p, new_sz);
      return result;
    }

    // 接下来就是仿真C++ new handler()
    // 你可以通过这个来设定你的的out-of-memory handler
    static void (* set_malloc_handler(void (*f)())) () {
      void (* old)() = __malloc_alloc_oom_bandler;
      __malloc_alloc_oom_bandler = f;
      return (old);
    }
}

通过观察一级配置器可以得知，一级配置器是以malloc()、free()、realloc()等C函数执行实际的内存的配置、释放、重配置等操作，并实现出类似C++ new handler的操作。
SGI一级配置器的顺序是先使用allocate()与realloc()(allocate 调用malloc，realloc调用realloc())。若是分配没有成功，就会改而调用oom_malloc()与oom_realloc()。它们会不断的循环调用内存不足处理例程，去解决问题。倘若没有设定内存不足处理例程，编程器则会调 _ _ THROW_BAD_ALLOC,丢出bac_alloc异常，或是直接调用exit(1)强制中止程序。
一级配置器的malloc-based allocator 相对于二级配置器的default alloc 会慢一些。但是对于线程安全和空间的运用上来说，malloc-base allocator会显得更加高效。


// 实现部分
template <int inst>
class __malloc_alloc_template {
  private:
    // 以下是用来处理内存不足情况的
    // oom： out of memory;
    static void *oom_malloc(size_t);
    static void *oom_realloc(void* ,size_t);
    static void (* __malloc_alloc_oom_bandler) ();
  public:
    static void *allocate(size_t n) {
      void *result = malloc(n)  //一级配置器直接使用malloc()
      // 以下情况无法满足时，才会改用oom_malloc()
      if (0 == result) result = com_malloc(n);
      return result;
    }

    static void deallocate(void *p, size_t) {
      free(p) // 一级配置器直接使用free()
    }

    static void *reallocate(void *p,size_t ,size_t new_sz) {
      void *result = reallocate(p, new_sz);  // 一级配置器直接使用reallocate() 
      // 以下情况无法满足时，才会改用oom_realloc()
      if (0 == result) result = oom_realloc(p, new_sz);
      return result;
    }

    // 接下来就是仿真C++ new handler()
    // 你可以通过这个来设定你的的out-of-memory handler
    static void (* set_malloc_handler(void (*f)())) () {
      void (* old)() = __malloc_alloc_oom_bandler;
      __malloc_alloc_oom_bandler = f;
      return (old);
    }
}

二级配置器剖析

二级配置器对于一级来说又多了一些机制，专门针对于内存碎片的处理。内存的碎片化不仅是增加了回收的难度，对于配置来说也是一个负担。并且这种负担是无法避免的，因为不管任何程序向system heap申请内存，都必须缴税。这个税也就是用来记录内存大小的信息，系统也正是依赖这些税才可以更好的管理内存。

那么对于这些浩如烟海的税，我们的系统又是如何去管理的呢？二级配置器提供了一个很好的方法即使用自由链表去管理。大家肯定好奇自由链表为何是自由的？首先，自由链表每次都是直接配置一大块内存，客户端需要时直接分配给它，也就是从free-list中拔出。若客户端释还小额区块，则依旧还给free-list即重新插入free-list中。
既然使用链表，那我们又该如何去维护它呢？在这里大师提供了一个绝妙的方法，在了解这个方法之前，我们先了解一个概念————union(共用体)。如果了解过了可跳过这部分，不了解的同学可以学习回顾一下。

共用体是一种特殊的类，也是一种构造类型的数据结构
共用体表示几个变量共用一个内存位置，在不同的时间保存不同的数据类型与不同长度的变量。
所有的共用借机成员共用一个空间，并且同一时间只能存放一个成员变量的值
1
2
3
4
5
6
7
union test {
size_t a;
int b;
double c;
long d;
char e;
}

对于test来说，这里的数据大小就是long的大小。在C++中union主要用来压缩空间的。
在了解union之后，我们就可以来学习自由链表节点设计的精妙了

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

为了防止需要额外指针去指向下一个，因而union的第一个字段可以当做一个指针指向下一个。对于第二个区块，也可作为一个指针，不过此时指向的是实际的内存区。这样的一物两用，既实现了维护的目标又达到了避免浪费的目的。

底下是二级配置器中的free_list的部分实现代码

enum {__ALIGN = 8}; // 小型区块的上调边界
enum {__MAX_BYTES = 128}; // 小型区块的上限
enum {__NFRELISTS = __MAX_BYTES / __ALIGN};  // free-lists 个数

template <bool threads,int inst>
class __default_alloc_template {
  private:
    // ROUND_UP() 将bytes 上调至8的倍数
    static size_t ROUND_UP (size_t bytes) {
      return (((bytes)+__ALIGN-1) & ~(__ALIGN-1));
    }
  private:
    union obj {  // free-list 节点构造
      union obj * free_list_link;
      char client_data[1];
    }
  private:
    static obj * volatile free_list[__NFRELISTS];
    // 以下函数根据区块大小、决定使用第n号free-list。n从0开始
    static size_t FREELIST_INDEX(size_t bytes) {
      return (((bytes)+__ALIGN-1) & ~(__ALIGN-1)); 
    }

    // 返回一个大小n的对象，并可能加入大小为n的其它区块到free list
    static void *refill(size_t n);
    

    // 配置一大块空间，可容纳nobjs个大小为"size"的区块
    // 如果配置nobjs个区块有所不便，nobjs可能会降低
    static char* chunk_alloc(size_t size,int &nobjs);

    // chunk allocation state
    static char* start_free; // 内存池起始位置,仅在chunk_alloc()中变化
    static char* end_free; // 内存池结束位置，只在chunk_alloc()中变化
    static size_t heap_size;

  public:
    static void* allocate(size_t n);
    static void deallocate(void* p,size_t n);
    static void* reallocate(void *p,size_t old_sz,size_t new_sz);
};

// 以下是static data member 的定义与初值设定
template <bool threads,int inst>
char *__default_alloc_template<threads,inst>::start_free = 0;

template<bool threads, int inst>
char *__default_alloc_template<threads, inst>::end_free = 0;

template<bool threads,int inst>
size_t __default_alloc_template<threads, inst>::heap_size = 0;

template<bool threads, int inst>
__default_alloc_template<threads,inst>::obj * volatile
__default_alloc_template<threads, inst>::free_list[__NFRELISTS]=
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

allocate源码剖析

在了解free-list这样一个二级配置器的密钥后，我们就带着这个钥匙打开allocate()的大门。


static void *allocate(size_t n) {
  obj * volatile * my_free_list;
  obj * result;

  // 大于128就调用一级配置器
  if (n > (size_t) __MAX_BYTES) {
    return (malloc_alloc::allocate(n));
  }

  // 寻找16个free list 中适当的一个
  my_free_list = free_list + FREELIST_INDEX(n);
  result = * my_free_list;
  if (result == 0) {
    // 没有找到可用的free list，准备重新填充free list
    void *r = refill(ROUND_UP(n));
    return r;
  }
  
  //调整 free list
  *my_free_list = result -> free_list_link;
  return (result);
};

作为二级配置器，( _ _ default_alloc_templat)同样也拥有配置的标准接口函数allocate()。函数的作用：首先判断区块大小，超过128就调用一级配置器。小于就检查对应的free-list，如果free list有可用区块，就直接拿来使用。如果没有可用的，就将区块大小上调至8的倍数，然后调用refill()，为free list重新填充空间。
allocate函数实现示意图

deallocate()源码剖析

在了解完alloate的空间配置，我们同时也应该明白，空间的释放是如何进行的。

static void deallocate(void *p,size_t n) {
  obj *q = (obj*) p;
  obj * volatile * my_free_list;

  //大于128则调用一级配置器
  if (n > (size_t) __MAX_BYTES) {
    malloc_alloc::deallocate(p, n);
    return;
  }

  // 寻找对应的free list
  my_free_list = free_list + FREELIST_INDEX(n);
  // 调整free list，回收区块
  q->free_list_link = *my_free_list;
  *my_free_list = 0;
}

作为二级配置器的标准接口函数deallocate()。它的使用是：首先判断区块大小，大于128调用一级，小于128就找到对应的free list，将其回收。
deallocate函数作用示意图

refill()源码剖析

作为品尝内存池的餐前小点，你确定不看看吗？

// 返回一个大小为n的对象，并且有时候会为适当的free list 增加节点
// 假设n已经适当上调至8的倍数
template <bool threads, int inst>
void *__default_alloc_template<threads, inst>::refill(size_t n) {
  int nobjs = 20;
  // 调用chunk_alloc(),尝试取得nobjs个区块作为free list的新节点
  // 注意参数nobjs是psss by reference
  char* chunk = chunk_alloc(n, nobjs);
  obj* volatile * my_free_list;

  obj * result;
  obj * current_obj, * next_obj;
  int i;

  // 如果只获得一个区块，这个区块就分配给调用者使用,free list无新节点
  if (i == nobjs) return (chunk);
  // 否则准备调整free list,纳入新节点
  my_free_list = free_lis + FREELIST_INDEX(n);

  // 以下在chunk空间内建立free list
  result = (obj*) chunk;  //这一块准备返回给客户端
  // 以下导引free list指向新配置的空间(取自内存池)
  *my_free_list = next_obj = (*obj *)(chunk + n);
  // 以下将free list各节点串接起来
  for (i = 1; ;i++) { // 从1开始，因为第0个将返回给客端
    current_obj = next_obj;
    next_obj = (obj*)((char *)next_obj + n);
    if (nobjs - 1 == i) {
      current_obj -> free_list_link = 0;
      break;
    } else {
      current_obj -> free_list_link = next_obj;
    }
  }
  return (result);
}

当发现free list中没有可用区块时，就会调用refill()为free list注入新空间。新的空间皆是取自内存池(经由chunk_alloc()完成)。当内存池水够时，缺省会获得20个新区块。如果水不够，获得的节点可能少于20。
形象一点的说法就是：refill()就相当于水杯，free list里没有水了，它就会从内存池子里面舀水并灌到free list中。当内存池水不够了，那么杯子就是能舀多少舀多少水灌到free list中。

二级配置器核心——内存池

在有了前面的基础下，我们终于来到memory pool这里了。其实内存池的意思很简单，就像下图表示的一样

让我们再通过源码来深入了解了解内存池


// 假设size 已经上调至8的倍数
// 注意参数nobjs 是 pass by reference

template <bool threads, inst>
char* __default_alloc_template<threads,inst>::
chunk_alloc(size_t size,int& nobjs) {
  char * result;
  size_t total_types = size * nobjs;
  size_t bytes_left = end_free - start_free; // 内存池剩余空间
  
  if ( bytes_left >= total_types) {
    result = start_free;
    start_free += total_types;
    return(result);
  } else if (bytes_left >= size) {
    // 内存池剩余空间不能完全满足需要量，但是足够供应一个(含)以上的区块
    nobjs = bytes_left /size;
    total_types = size * nobjs;
    result = start_free;
    start_free += total_types;
    return (result);
  } else {
    // 内存池剩余空间边一个区块的大小都无法提供
    size_t types_to_get = 2 * total_types + ROUND_UP(heap_size >> 4);
    // 以下都是尝试让内存池中的残余还有利用价值
    if (bytes_left > 0) {
      // 内存池中还有一些零头，先配给给适当的free list
      // 首先寻找适当的 free list
      obj * volatile * my_free_list = 
        free_list + FREELIST_INDEX(bytes_left);
      //调整feee list,将内存池中的残余编入
      ((*obj)start_free)-> free_list_link = *my_free_list;
      *my_free_list  = (obj*)start_free;
    }

    // 配置heap 空间,用来补充内存池
    start_free = (char*)malloc(bytes_to_get);
    if (0 == start_free) {
      // heap 空间不足，malloc()失败
      int i;
      obj * volatile * my_free_list *p;
      // 试着检视我们手上拥有的东西，这不会造成伤害，我们不打算尝试配置
      // 较小的区块，因为在多进程机器上容易导致灾难
      // 以下搜寻适当的free list，适当就是“还有可用区块，且够大"的free list
      for (i = size; i< __MAX_BYTES; i += __ALIGN) {
        my_free_list = free_list + FREELIST_INDEX(i);
        p = *my_free_list;
        if (0 != p) {  // free list 还有没有的区块
          // 调整free list以释放出未用区块
          *my_free_list = p->free_list_link;
          start_free = (char*) p;
          end_free = start_free + i;
          // 递归调用自己，为了修正nobjs
          return (chunk_alloc(size, nobjs));
          // 注意，任何残余零头终将被编入适当的free list中备用
        }
      }

      end_free = 0 // 如果出现意外(山穷水尽,没有内存可用)
        // 没用一级配置器，看看out-of-memory机制能否尽点力
        start_free = (char*) malloc_alloc::allocate(bytes_to_get);
      // 这会导致抛出异常，或内存不足的情况改善
    }
    heap_size += bytes_to_get;
    end_free = start_free + bytes_to_get;
    // 递归调用自己，为了修正nobjs
    return (chunk_alloc(size,nobjs));
  }
}

结合书上的例子与下图，对内存池理解进一步加深

总结

空间配置器作为STL六大组件的基础，我们之后学习新的内容时。要时常的复习这部分，要结合新的内容，进行全面开拓。

Rabbet

The Annotated STL Sources-1

导言