SGI空间配置器源码分析。

说明：空间配置器一直在各个容器背后默默付出，为他们分配内存，并可以有效地解决内存碎片的问题。

SGI STL的默认配置器为alloc，SGI设计了双层配置器。
第一层为所分配内存大于128时使用的，直接调用malloc和free来分配与释放，并且可以设定一个set_new_handler来处理内存不足的情况。
第二层则是小于128时使用的，为防止内存碎片利用一个free lists来控制内存，内存不足时转回第一层方法（因为里面有set_new_handler）。

下面来分析stl中alloc的源码。
1.第一层：

template <int inst>
class __malloc_alloc_template {

private:

static void *oom_malloc(size_t);//oom即out of memory,当内存不足时用它来处理

static void *oom_realloc(void *, size_t);

public:

static void * allocate(size_t n)
{
    void *result = malloc(n);//可以看到第一层直接调用了malloc
    if (0 == result) result = oom_malloc(n);//内存不足时用了oom来处理
    return result;
}

static void deallocate(void *p, size_t /* n */)
{
    free(p);//第一层释放直接是free
}

static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz)
{
    void * result = realloc(p, new_sz);
    if (0 == result) result = oom_realloc(p, new_sz);
    return result;
}

//指定自己的out_of_memory_handler，看到前面已经定义了void (* __malloc_alloc_oom_handler)() = 0，我们可以改变它写成自己的处理方法。
static void (* set_malloc_handler(void (*f)()))()
{
    void (* old)() = __malloc_alloc_oom_handler;
    __malloc_alloc_oom_handler = f;
    return(old);
}

};

然后来分析一下当我们内存不足时alloc是怎么做的：

template <int inst>
void * __malloc_alloc_template<inst>::oom_malloc(size_t n)
{
    void (* my_malloc_handler)();
    void *result;

    for (;;) {
        my_malloc_handler = __malloc_alloc_oom_handler;//这里写了一个死循环来不断的获取内存，直到得到之后就返回
        if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; }//当我们没有定义自己的handler时直接抛出异常
        (*my_malloc_handler)();//调用之前定义的处理机制，企图释放内存
        result = malloc(n);//再次获取一下
        if (result) return(result);
    }
}

template <int inst>
void * __malloc_alloc_template<inst>::oom_realloc(void *p, size_t n)//realloc和malloc是一样的道理
{
    void (* my_malloc_handler)();
    void *result;

    for (;;) {
        my_malloc_handler = __malloc_alloc_oom_handler;
        if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; }
        (*my_malloc_handler)();
        result = realloc(p, n);
        if (result) return(result);
    }
}

2.第二层。
第二层的做法是，维护一个free-list，每次分配一个大块内存（内存池），当有内存需求时，直接从free-list中取，整体是这样的：

当内存池里内存不够时是，在调用refill填充内存，具体代码分析如下：

template <bool threads, int inst>
class __default_alloc_template {

private:

    enum {__ALIGN = 8};//第二层分配的里最小内存块
    enum {__MAX_BYTES = 128};//第二层里分配的最大内存块
    enum {__NFREELISTS = __MAX_BYTES/__ALIGN};//free-list的个数

  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]; /* The client sees this. */
  };
private:
  static obj * __VOLATILE free_list[__NFREELISTS]; //16个free-list
  static  size_t FREELIST_INDEX(size_t bytes) {
        return (((bytes) + __ALIGN-1)/__ALIGN - 1);//算对应free-list的下标
  }
  static void *refill(size_t n);//填充内存
  static char *chunk_alloc(size_t size, int &nobjs);//从内存里取nobjs个大小为size区块，若内存不够可以少于nobjs

  // Chunk allocation state.
  static char *start_free;//内存池起始位置
  static char *end_free;//内存池结束为止
  static size_t heap_size;
public:

  /* n must be > 0 */
  static void * allocate(size_t n)
  {
    obj * __VOLATILE * my_free_list;
    obj * __RESTRICT result;

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

    my_free_list = free_list + FREELIST_INDEX(n);//寻找16个free-list中合适的一个
    result = *my_free_list;
    if (result == 0) {
        void *r = refill(ROUND_UP(n));//没找到可用的就去填充
        return r;
    }
    *my_free_list = result -> free_list_link;
    return (result);
  };

  /* p may not be 0 */
  static void deallocate(void *p, size_t n)
  {
    obj *q = (obj *)p;
    obj * __VOLATILE * my_free_list;

    if (n > (size_t) __MAX_BYTES) {
        malloc_alloc::deallocate(p, n);//大于128就调用第一层配置器
        return;
    }
    my_free_list = free_list + FREELIST_INDEX(n);//寻找16个free-list中对应的一个

    q -> free_list_link = *my_free_list;//回收区块
    *my_free_list = q;
    // lock is released here
  }

  static void * reallocate(void *p, size_t old_sz, size_t new_sz);

} ;

  具体函数实现：

template <bool threads, int inst>
char*
__default_alloc_template<threads, inst>::chunk_alloc(size_t size, int& nobjs)
{
    char * result;
    size_t total_bytes = size * nobjs;
    size_t bytes_left = end_free - start_free;//内存池剩余空间

    if (bytes_left >= total_bytes) {//内存池剩完全的够用
        result = start_free;
        start_free += total_bytes;
        return(result);
    } else if (bytes_left >= size) {//内存池剩的不够nobjs个，但是还有几个
        nobjs = bytes_left/size;
        total_bytes = size * nobjs;
        result = start_free;
        start_free += total_bytes;
        return(result);
    } else {
        //内存池连一个都无法提供了
        size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
        // Try to make use of the left-over piece.让剩余的残余内存有些价值
        if (bytes_left > 0) {
            //把剩余的零头凑起来分配给合适的free-list

            //首先找适合的ree-list
            obj * __VOLATILE * my_free_list =
                        free_list + FREELIST_INDEX(bytes_left);
            //调整，将零头放进去
            ((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) {
            int i;
            obj * __VOLATILE * my_free_list, *p;
            // Try to make do with what we have. That can't
            // hurt. We do not try smaller requests, since that tends
            // to result in disaster on multi-process（多进程） machines.
            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还有没有用的区块，调整并释放
                    *my_free_list = p -> free_list_link;
                    start_free = (char *)p;
                    end_free = start_free + i;

                    //递归调整自己来修正nobjs
                    return(chunk_alloc(size, nobjs));
                    // Any leftover piece will eventually make it to the
                    // right free list.
                }
            }
        end_free = 0;    // In case of exception.啥都没了，又用第一层，靠他的out_of_memory_handler了
            start_free = (char *)malloc_alloc::allocate(bytes_to_get);
            // This should either throw an
            // exception or remedy the situation. Thus we assume it
            // succeeded.
        }
        heap_size += bytes_to_get;
        end_free = start_free + bytes_to_get;
        return(chunk_alloc(size, nobjs));//递归调整自己来修正nobjs
    }
}


/* Returns an object of size n, and optionally adds to size n 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>::refill(size_t n)
{
    int nobjs = 20;
    //尝试获得20个内存区块
    char * chunk = chunk_alloc(n, nobjs);
    obj * __VOLATILE * my_free_list;
    obj * result;
    obj * current_obj, * next_obj;
    int i;

    //只获得了一个，那就用那个吧，没有新的再进去
    if (1 == nobjs) return(chunk);
    my_free_list = free_list + FREELIST_INDEX(n);

    /* Build free list in chunk *///在chunk空间里建立free-list
      result = (obj *)chunk;//这块给客户端用

      *my_free_list = next_obj = (obj *)(chunk + n);
     //将free-list各节点穿起来
      for (i = 1; ; i++) {
         //i从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);
}

template <bool threads, int inst>
void*
__default_alloc_template<threads, inst>::reallocate(void *p,
                                                    size_t old_sz,
                                                    size_t new_sz)
{
    void * result;
    size_t copy_sz;

    if (old_sz > (size_t) __MAX_BYTES && new_sz > (size_t) __MAX_BYTES) {
        return(realloc(p, new_sz));
    }
    if (ROUND_UP(old_sz) == ROUND_UP(new_sz)) return(p);
    result = allocate(new_sz);
    copy_sz = new_sz > old_sz? old_sz : new_sz;
    memcpy(result, p, copy_sz);
    deallocate(p, old_sz);
    return(result);
}

 以上把关于加锁的代码都剔除了。只看实现方式。