TinySTL实现项目（三）：具有SGI特色的两级分配器alloc模板类

1 SGI STL 2.91 中空间分配器alloc的设计思想

在上篇文章中，我们实现了使用::operator new和::operator delete来分配、释放内存的空间分配器allocator模板类。但在SGI STL 2.91版的源码实现中，其使用的空间分配器并非如此简单，而是以更底层的malloc()、free()来分配、释放内存，其设计哲学在《STL源码剖析》中总结如下：

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

而其避免内存碎片问题的方法就是设计了两级分配器

第一级分配器：当一次要求的内存超过128bytes时使用，其直接使用malloc()、free()
第二级分配器：当一次要求的内存小于128bytes时使用，采用了内存池memory pool整理方式，维护了16个链表，这些链表分别负责从8bytes、16bytes、24bytes直到128bytes的16种小型内存块的分配。

其中第一级分配器还考虑了OOM(out of memory)时的处理，实现了类似C++中new-handler的机制，使得在内存不足抛出std::bad_alloc异常前，可以调用一个用户自行定义的函数来尝试解决内存不足问题，如果用户没有定义该函数，则直接抛出std::bad_alloc异常。

而在实现中，甚至都没有完全符合STL标准，比如alloc::construct就不存在，这里简单说一下其具体实现。

1.1 SGI 的第一级分配器

第一级分配器：一个名为__malloc_alloc_template<int inst>的模板类，模板参数实际上并没用上；分别基于malloc()、free()、realloc()来实现allocate()、deallocate()、reallocate()这三个public成员函数；另外拥有一个函数指针类型的静态成员malloc_alloc_oom_handler和设定该静态成员的public成员函数set_malloc_handler，这是用于实现上述new-handler机制的；最后还有两个private的函数oom_malloc、oom_realloc来处理OOM情况，这两个函数会先调用之前的那个函数指针静态成员所指向的函数，然后再尝试分配内存，如果用户没有实现设定该静态成员指向的函数，会直接报错cerr << “out of memory”然后exit(1)中止程序。部分实现如下：

template <int inst>
class __malloc_alloc_template {
private:
static void *oom_malloc(size_t);
static void *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 = 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 = 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);
}
};

1.2 SGI 的第二级分配器

第二级分配器：具体实现有点小复杂，由于本项目使用的第二级分配器基本同SGI的一致，所以具体函数实现留待下文讲解，这里只简单总结一下其思路。同上文所述，其将小于128bytes的内存按照8bytes为间隔，划分为16种大小的内存区块，然后用16条链表来维护这些区块。

比如第一条链表管理8bytes的内存块，假设其有10个节点，这10个节点每个都有8bytes的空间可以拨给用户使用，用户用allocate()请求8bytes大小的空间时，就返回给用户1个节点的空间，此时剩9个节点，如果用户用deallocate()释放了8bytes的空间，那么这个节点又会被回收到这条链表上，又变成了10个节点。其他的链表就是如此依次维护16bytes、24bytes、32bytes等等大小的内存块。

那如果用户请求的bytes数目大小不是8的倍数呢？比如30，分配器就会将其自动上调为32，然后找负责32bytes的链表分配空间。需要说明的是，这里的链表节点使用了union类型，而不是常用的struct，这是因为union类型用在这里更节约空间。

union类型比较特殊，其内部成员可以共享内存，每个union对象分配的内存以其最大的成员而定，这里的最大指的是sizeof()后最大。

当多个基本数据类型或复合数据结构要占用同一片内存时，我们要使用联合体；当多种类型，多个对象，多个事物只取其一时（我们姑且通俗地称其为“n 选1”），我们也可以使用联合体来发挥其长处。

这里用union实现的链表，每个节点包含一个指向自身类型的指针next和一个char*类型指针，那么其第一个成员next可以用来连接链表，而第二个成员char*又可以表示为一个指向实际内存区块的指针，可以用来分配给用户使用。

最终第一级分配器和第二级分配器的实现也并未完全符合STL的标准，比如allocate()的参数就和STL要求的不一样，reallocate()也不是STL要求的，另外allocate::construct()等函数也没有实现。所以SGI还将其包装了一个接口，使分配器的allocate()和deallocate()符合STL标准，如下

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)); }
};

实际上，SGI STL的源码中，第二级分配器还考虑了多线程情况，而我们的项目是以学习为目的，自然对复杂程度要有所取舍，故而在我们的实现中只考虑单线程的普通情况。

接下来即是根据SGI STL源码来实现的一个不使用多线程的alloc模板类。在代码上仅做了极小的修改，看完了本项目的实现，也就明白了SGI的实现。

为什么本节标题要强调2.91的SGI实现版本呢？因为在部分后续版本的实现中，SGI就去掉了两级分配器和memory poll的实现思想。去掉原因目前我还不知道。。。

2 部分考虑和相应改动

本项目的这部分的实现思路将基本参照 SGI，仅做小部分的改动。

考虑1：在SGI 的实现中，第一级分配器是一个类模板，但是却没有用到模板参数，第二级分配器也是一个类模板，第一个模板参数考虑多线程，第二个模板参数依然没用上。而在我们的实现中，不考虑多线程情况，就没有必要使用多余的模板参数了，甚至没必要使用模板。

改动1：直接将两级分配器设计为两个普通类。

考虑2：如上文所述，SGI 对两级分配器的包装是一个带两个参数的模板类simple_alloc，使用时还需要根据宏定义在第二模板参数上确定仅使用第一级分配器还是同时使用两级分配器，然后再将分配器作为模板参数放入，由于命名问题还需要为具化后的simple_alloc定义别名。

改动2：本项目中将其包装的模板改动为一个参数的模板类，在该模板的成员函数中直接调用第二级分配器，并且为该模板补充alloc::construct等 STL 要求的标准接口。另外由于本项目已实现名为allocator的分配器，故而将本部分的分配器包装接口命名为alloc。

3 TinySTL 第一级分配器的实现

3.1 接口总览

因为第一级分配器直接使用malloc()来分配内存，这里将其取名为malloc_alloc。在 SGI 的实现中，其是一个类模板，但却并没有使用到其模板参数，所以这里直接将其设计为普通的类。先确定要实现的相应函数和成员，代码如下：

alloc.h

// 使用 malloc 和 free 实现的一级分配器
// 可以由客端设置 OOM 时的 new_handler
class malloc_alloc {
private:
	// 一个函数指针类型
    using FunPtr = void (*)();

public:
    static void* allocate(size_t);
    static void deallocate(void* ptr) { free(ptr); }
    static void* reallocate(void*, size_t, size_t new_sz);
    static FunPtr set_malloc_handler(FunPtr f);

private:
	// 用于处理OOM时的辅助函数
    static void* oom_malloc(size_t);
    static void* oom_realloc(void*, size_t);
    // 函数指针类型的静态成员。也可以写成 FunPtr malloc_alloc_oom_handler
    static void (*malloc_alloc_oom_handler)();
};

可以看到allocate()的返回类型是void指针类型，这里依然是参照 SGI 的设计，让第一级和第二级分配器所分配的空间都用void指针类型，最后在外层包装的模板类接口上统一转换，既简单也不会影响效率。

3.2 allocate和deallocate的实现

先直接来看allocate()的代码实现：

alloc.h

void* malloc_alloc::allocate(size_t n) {
    void* result = malloc(n);
    if (result == 0)
        result = malloc_alloc::oom_malloc(n);
    return result;
}

注意其仅接受一个size_t类型的参数n，先调用malloc来分配大小为n个字节（byte）的内存块。这和上篇文章中实现的allocator<T>::allocate(size_t n)不一样，其分配的是大小为n * sizeof(T)个字节的内存块。如果分配空间失败，则调用内部辅助函数oom_malloc()来继续尝试分配空间。

void* malloc(size_t n_bytes)分配长度为n_bytes字节的内存块。分配成功则返回类型为void指向被分配内存的指针，否则返回空指针NULL。释放malloc分配的内存应使用free()。

蓝色背景内容所述，在3.1节的代码中可以看到deallocte()接受一个指针，直接使用free()来释放内存。

3.3 reallocate的实现

其实最终对外包装的模板类中并没有使用到reallocate()，本着学习的态度，就顺便照着 SGI 的敲了一遍。代码实现如下：

alloc.h

void* malloc_alloc::reallocate(void* ptr, size_t old_sz, size_t new_sz) {
    void* result = realloc(ptr, new_sz);
    if (result == 0)
        result = malloc_alloc::oom_realloc(ptr, new_sz);
    return result;
}

可以看到跟allocate()相比，仅仅是换成了使用realloc实现

void* realloc (void* ptr, size_t size)，ptr 为需要重新分配的内存空间指针，size 为新的内存空间的大小。realloc() 对 ptr 指向的内存重新分配 size 大小的空间，size 可比原来的大或者小，还可以不变。当 malloc()、calloc() 分配的内存空间不够用时，就可以用 realloc() 来调整已分配的内存。

如果 ptr 为 NULL，它的效果和 malloc() 相同；如果 size 的值为 0，那么 ptr 指向的内存空间就会被释放，但是由于没有开辟新的内存空间，所以会返回空指针，类似于调用 free()。

realloc接受的指针必须是动态内存空间分配成功的指针。比如不能使用int* p、int arr[2]这样的指针，会直接报错。可以说只有malloc()、calloc()、realloc()分配成功成功的指针才能用realloc。

使用new_ptr=realloc(prt,n)分配内存成功后，ptr绝不能再被使用，只能使用new_ptr。

扩大内存会复制原来内存到新地址，缩小内存会先被复制再被截取新长度。

3.4 new_handler机制的实现

new_handler机制就是，当使用::operator new分配内存不满足需求时，可以在抛出异常之前，调用一个用户实现指定的函数来进行错误处理，这个函数就是所谓的new_handle。而指定这个函数的方法就是使用set_new_handler()，这个函数接受一个函数指针类型，返回的也是函数指针类型。

由于在这里，我们使用malloc而不是::operator new来实现allocate()，所以我们不能直接使用C++现有的new_handler机制，需要我们手动来实现。

实现方法也很简单，如3.1节中的代码所示，我们先在类中声明一个函数指针类型的静态成员，用来指向用户设定的函数。然后在类中声明一个成员函数，用来设定该静态成员。如代码所示。

alloc.h

class malloc_alloc {
private:
	// 一个函数指针类型
    using FunPtr = void (*)();
public:
    ...
    static FunPtr set_malloc_handler(FunPtr f);
	...
private:
    // 函数指针类型的静态成员。也可以写成 FunPtr malloc_alloc_oom_handler
    static void (*malloc_alloc_oom_handler)();
};

这个设定静态成员的函数即是set_malloc_handler，实现如下

alloc.h

typename malloc_alloc::FunPtr malloc_alloc::set_malloc_handler(FunPtr fptr) {
    FunPtr old = malloc_alloc_oom_handler;
    malloc_alloc_oom_handler = fptr;
    return old;
}

该函数接受一个函数指针类型的参数，返回值也是一个函数指针类型。功能就是将代表handler的静态成员设为用户传进来的函数，最后返回原来的handler函数。

显然上述这个代表handler的函数指针静态成员应该初始化为0或者nullptr

alloc.h

1	void (*malloc_alloc::malloc_alloc_oom_handler)() = 0;

3.5 OOM时的处理

3.4节中我们已经实现了new_handler机制，OOM(out of memory)时就会使用到该机制，调用用户设定的函数来处理，期待可以解决内存不足的问题、或者直接输出提示信息中断程序等。

在allocate和reallocate的实现可以中我们看到了，在请求分配内存失败时，也就是OOM时，将会调用两个辅助函数oom_malloc和oom_realloc。这两个函数的实现大同小异，这里先看oom_malloc如何实现：

alloc.h

void* malloc_alloc::oom_malloc(size_t n) {
	// 若用户并未设定 handler 函数，则输出报错信息
    if (malloc_alloc_oom_handler == 0) {
        std::cerr << "out of memory" << std::endl;
        exit(1);
    }
    // 否则不断尝试调用 handler 函数，然后用malloc再次请求分配内存，直到分配成功
    void* result;
    for (;;) {
        malloc_alloc_oom_handler();
        result = malloc(n);
        if (result)
            return result;
    }
}

可以看到函数比较简单，看注释应该就够了。下面看oom_realloc的实现：

alloc.h

void* malloc_alloc::oom_realloc(void* ptr, size_t new_sz) {
	// 若用户未设定 handler 函数，则输出报错信息
    if (malloc_alloc_oom_handler == 0) {
        std::cerr << "out of memory" << std::endl;
        exit(1);
    }
    // 否则不断尝试调用 handler 函数，然后用realloc请求重新分配内存，直到分配成功
    void* result;
    for (;;) {
        malloc_alloc_oom_handler();
        result = realloc(ptr, new_sz);
        if (result)
            return result;
    }
}

4 TinySTL 第二级分配器的实现

由于在实际使用中是默认调用第二级分配器，然后第二级分配器会根据所需要的内存块大小，来决定是否调用第一级分配器，所以此处将第二级分配器命名为default_alloc。

如1.2节所述，这里使用了内存池(memory pool)机制，用16条链表来维护16种大小的内存块，这些内存块大小是从最小8 bytes，以 8 bytes 为间隔，到最大128 bytes ；当请求的内存小于128 bytes 时，就从相应的链表里，将内存分配出去，若大于128 bytes 就调用第一级分配器。

使用内存池机制的目的主要有两个：

减少malloc的调用次数，因为每次调用malloc的时候，其实都需要时间开销去寻找可使用的内存块
减少实际内存开销，因为malloc来分配内存的开销会比实际所需要内存更大，因为需要额外的空间来管理这一块内存；如下图所示，实际需要size大小的内存和最终开销的内存

内存管理

而这些通过链表来管理的不同大小的内存块从何而来呢？难道需要每次malloc这些大小不一的内存块了吗？这就是内存池存在的意义了。

我们可以一次malloc一大块内存，作为内存池，然后每次需要特定大小的内存时，从内存池中划拨到相应的链表，然后通过链表去分配。比如我一次malloc了512 bytes，然后这个时候用户请求分配 8 bytes，那我就一次划拨160 个bytes 到管理8 bytes大小内存块的链表上，此时链表有160 / 8 = 20 个节点；然后从这个20 个节点里分一个节点给用户使用。

虽然第一次分配的时候看起来比较麻烦，但之后用户再要求分配 8 bytes时，我就可以直接从链表剩下的19个节点里分给他，没有必要再使用malloc；而用户释放 8 bytes 大小时，我就可以将这 8bytes 回收到管理的链表上。这样我只malloc了一次，却可以满足20次用户要求分配 8 bytes的需求，而释放内存的时候也无须调用free，更改指针指向让其回到链表即可。

所以我们可以这么理解，实际上第二级分配器管理的内存也有两部分，一部分是链表维护的各种大小不一的小内存，另一部分则是由`malloc`得来的**内存池**，负责为链表“输血”。

4.1 接口总览

下面是内存实现的总览：

alloc.h

class default_alloc {
private:
    enum { ALIGN = 8 };
    enum { MAX_BYTES = 128 };
    enum { NFREELISTS = MAX_BYTES / ALIGN };

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

    static char* start_free;
    static char* end_free;
    static size_t heap_size;
    static obj* volatile free_list[NFREELISTS];

private:
    static size_t round_up(size_t bytes) {
        return ((bytes + ALIGN - 1) & ~(ALIGN - 1));
    }
    static size_t freelist_index(size_t bytes) {
        return ((bytes + ALIGN - 1) / ALIGN - 1);
    }
    static void* refill(size_t n);
    static char* chunk_alloc(size_t size, int& nobjs);

public:
    static void* allocate(size_t n);
    static void deallocate(void* ptr, size_t n);
    static void* reallocate(void* ptr, size_t old_size, size_t new_size);
};

首先是三个枚举类型，分别表示链表中内存块大小的间隔、最大内存块的大小、以及所需要的维护的链表数量。声明成枚举类型主要是为了方便以后对这些值进行修改。

接着一个是union类型，用来作为链表的节点，使用union的原因上文已有解释，主要是利用其成员共享内存的特点来节约内存的开销。

然后是四个静态成员。start_free和end_free就是用来管理malloc得到的内存池，分别表示内存池的头和尾。heap_size是一个和用户请求分配内存大小相关的值，用户请求的内存越多，该值就会越大，然后在每次内存池用尽，需要重新malloc的时候，会附加上heap_size的一个加权值；这样的结果就是，用户目前使用第二级分配器分配的内存块越多，下次malloc的时候就会分配得更多，其目的还是尽量减少malloc的次数。最后一个成员free_list就是存放16条链表的数组。

注意静态成员需要初始化：

alloc.h

char* default_alloc::start_free = 0;
char* default_alloc::end_free = 0;
size_t default_alloc::heap_size = 0;
default_alloc::obj* volatile default_alloc::free_list[NFREELISTS] = {
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
};

还需要介绍两个辅助函数round_up和freelist_index。前一个是用来将传入的参数补为8的倍数，比如请求分配30 bytes 的大小时，就将30补成32。后一个参数用来确定管理内存块的链表在数组free_list中的索引，如传入8，就返回索引0。

其余函数的作用和实现见下文。

4.1 allocate 的实现

allocate的作用我们已经说过多次，这里不同的只是，根据请求空间的大小，找到相应的链表，然后返回链表的一个节点供用户使用。如果发现相应的链表空了，就调用refill来填充链表。直接看实现

alloc.h

void* default_alloc::allocate(size_t n) {
    // 如果请求的大小超过 128 bytes就调用第一级分配器
    if (n > 128)
        return malloc_alloc::allocate(n);
    // 否则找到相应链表，注意这是一个指向链表头指针的指针
    obj* volatile* my_free_list = free_list + freelist_index(n);
    obj* result = *my_free_list;
    // 如果链表为空，就调用 refill 填充链表，refill会直接返回一个相应大小的空间供用户使用
    if (result == 0)
        return refill(n);
    // 不为空则调整链表，使表头变更到下一个节点
    *my_free_list = (*my_free_list)->next;
    return static_cast<void*>(result);
}

实现比较简单，应该看上面注释就足够了，最后不进行静态转换也是可以通过编译的。

4.2 deallocate 的实现

这里的deallocate和第一级分配器中直接free有所不同，也考虑两种情况：如果需要释放的内存大于128 bytes 则调用第一级分配器，否则就将其回收到相应的链表。这样的设计在最优情况下，自然可以物尽其用，链表达到“收支平衡”，不需要多次调用malloc。下面是实现

alloc.h

void default_alloc::deallocate(void* ptr, size_t n) {
    // 释放空间大于128bytes调用第一级分配器
    if (n > 128) {
        malloc_alloc::deallocate(ptr);
        return;
    }
    // 否则将其回收到相应链表
    obj* p = static_cast<obj*>(ptr);
    obj* volatile* my_free_list = free_list + freelist_index(n);
    p->next = *my_free_list;
    *my_free_list = p;
}

实现比较简单，无非是回收到链表时，将其插到链表表头。

4.3 reallocate 的实现

第一级分配器中的reallocate是直接通过realloc实现，关于realloc的介绍可以看3.3节中带颜色的字体。下面直接看实现：

alloc.h

void* default_alloc::reallocate(void* ptr, size_t old_size, size_t new_size) {
    // 若新旧 size 都大于 128 bytes则使用realloc
    if (old_size > MAX_BYTES && new_size > MAX_BYTES)
        return realloc(ptr, new_size);
    // 若在同一个小内存区间没必要操作
    if (round_up(old_size) == round_up(new_size))
        return ptr;
    // 都不是的话，需要模拟一下ralloc的操作
    // 开辟新内存，复制原来的部分，最后释放原内存
    void* result = allocate(new_size);
    size_t copy_sz = new_size > old_size ? new_size : old_size;
    memcpy(result, ptr, copy_sz);
    deallocate(ptr, old_size);
    return result;
}

内存管理，肯定要秉承谁分配的谁释放的原则。

显然大于128 bytes的话，说明该内存并不是第二级分配器分配的，让他找第一级分配器去。

如果确定是由第二级分配器分配的，就看看新要求的空间大小new_size跟原来的大小old_size在不在一个内存区间上，比如old_size是20 bytes，new_size是24 bytes，都在(16,24]区间里；因为分配的时候，如果要求 20 bytes，实际还是会给24 bytes，所以其实此时内存大小是满足需求的，直接用原来的就行，没必要操作。

排除以上情况以外，就需要新开辟一块大小为new_size，然后将原来的部分复制过来，复制部分肯定是不会超过原来的大小，也不会超过新长度，反正就是谁小取谁；最后还要记得释放原来的内存，调用deallocate即可。

4.4 refill 的实现

在allocate函数中，当对应所需内存大小的链表为空时，需要调用refill来为用户提供内存，除此以外，refill还会为填充对应链表，在下次请求相同大小内存时，就可以直接从链表中取了。下面是其实现：

alloc.h

void* default_alloc::refill(size_t n) {
    // 设定请求相应小内存块节点的个数
    int nobjs = 20;
    // chunk_alloc会从内存池中划拨相应大小的内存供其使用
    // 这里nobjs是传引用，会修改nobjs的值告知实际返回多少个节点
    char* chunk = chunk_alloc(n, nobjs);
    // 如果只返回了1个节点大小的空间，则直接提供给用户使用
    if (nobjs == 1)
        return static_cast<void*>(chunk);
    // 多于1个节点则将剩下节点填充到相应链表
    void* result = static_cast<void*>(chunk);
    obj *next_obj, *current_obj;
    obj* volatile* my_free_list = free_list + freelist_index(n);
    *my_free_list = next_obj = (obj*)(chunk + n);
    for (int i = 1;; ++i) {
        current_obj = next_obj;
        next_obj = (obj*)((char*)next_obj + n);
        if (nobjs - 1 == i) {
            current_obj->next = 0;
            break;
        } else
            current_obj->next = next_obj;
    }
    return result;
}

实际实现并不复杂，可以看到，当对应的链表为空的时候，默认会请求20个节点的大小，比如这个链表管理的是64 bytes的大小，那么就会向内存池请求 20 * 64 bytes的空间，然后将其中的19个放到链表中，留1一个直接返回给用户使用（allocate中对refill的调用）。

值得说明的是，chunk_alloc函数会根据当前内存池的大小，来决定实际返回的个数，并通过传引用objs参数对其修改，达到告知的目的。接上面的例子，比如现在内存池中只有64 bytes的大小了，那么chunk_alloc就会只返回64 bytes，解解燃眉之急，然后修改objs的值为1，当然要是有128 bytes，那就返回2个；但是如果内存池里连64 bytes的大小都没了，就会malloc一次，取得足够大的空间，返回20个。具体实现见下一节。

4.5 chunk_alloc 的实现

如4.4节所述，chunk_alloc函数作用就是在链表的内存需要补充时，从内存池中划拨一部分内存给refill使用，若是内存池不够用了，就malloc一大块内存，保证满足当前的需求之外，还能留着用。先直接看实现：

alloc.h


char* default_alloc::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;
    }
    // 若剩下的内存能够提供至少1个节点大小，则尽可能划拨
    else if (bytes_left >= size) {
        nobjs = bytes_left / size;
        result = start_free;
        start_free += nobjs * size;
        return result;
    } 
    // 否则使用malloc请求（当前需求*2+历史需求/16）的大小
    else {
        size_t bytes_to_get = 2 * total_bytes + round_up(heap_size >> 4);
        // 检查目前剩下的空间够不够划拨给其他更小内存块的链表
        if (bytes_left > 0) {
            obj* volatile* my_free_list =
                free_list + freelist_index(bytes_left);
            ((obj*)start_free)->next = *my_free_list;
            *my_free_list = (obj*)start_free;
        }
        start_free = (char*)malloc(bytes_to_get);
        // malloc失败的话，从更内存池的链表寻求空间，并将剩下空间放到内存池中
        if (start_free == 0) {
            obj* volatile* my_free_list;
            obj* ptr = *my_free_list;
            for (size_t i = size; i <= MAX_BYTES; i += ALIGN) {
                my_free_list = free_list + freelist_index(i);
                ptr = *my_free_list;
                if (ptr != 0) {
                    *my_free_list = ptr->next;
                    start_free = (char*)ptr;
                    end_free = start_free + i;
                    return chunk_alloc(size, nobjs);
                }
            }
            // 更大链表也没有空间了，试试第一级分配器的new_handler机制
            end_free = 0;
            start_free = (char*)malloc_alloc::allocate(bytes_to_get);
        }
        heap_size += bytes_to_get;
        end_free = start_free + bytes_to_get;
        // malloc成功,递归调用自己向refill划拨空间
        return chunk_alloc(size, nobjs);
    }
}

实现逻辑并不复杂：当内存池的空间够分配1个以上节点的时候，会尽可能地满足需求，划拨空间；当内存完全不够的时候就malloc一大块。

值得一说的是，当malloc失败的时候设计非常细致，可以做到对已有内存充分利用，没有丝毫浪费。首先使用malloc前就先检查，剩下的空间够不够分配给其他更小的链表，物尽其用；然后如果malloc成功了，皆大欢喜，再次递归地调用自己，向链表(实际为refill函数)划拨空间；如果malloc失败了，先检查其他管理更内存池的链表中有没有空间可以使用，可以的话，先拿一个节点来用，并且这个节点剩下还得放回内存池，如果这些链表都空了，那就调用第一级分配器，毕竟第一级分配器还实现了new_handler机制，也许能派上用场。

5 TinySTL 类模板alloc的包装

在第3节和第4节实现的两级分配器，只是两个普通类，并且接口不符合STL要求。所以需要用一个类模板对其包装，过程也很简单，顺便也为其实现了construct、destroy、address、max_size、rebind接口，其实现与上篇文章中allocator的实现基本一致。下面是其部分实现：

alloc.h

// SGI STL 特色分配器，需要一个模板参数，具有 STL 标准接口
template <typename T>
class alloc {
public:
    // STL 要求的类型别名定义
    using value_type        = T;
    using pointer           = T*;
    using const_pointer     = const T*;
    using reference         = T&;
    using const_reference   = const T&;
    using size_type         = size_t;
    using difference_type   = ptrdiff_t;

public:
    // STL 要求的类接口，使用静态函数实现可以使频繁调用下减小开销
    // 负责分配内存
    static T* allocate();
    static T* allocate(size_type n);
    // 负责释放内存
    static void deallocate(T* ptr);
    static void deallocate(T*, size_type n);
    // 负责构造对象
    static void construct(T* ptr);
    static void construct(T* ptr, const T& value);
    static void construct(T* ptr, T&& value);
    // 负责析构对象
    static void destroy(T* ptr);
    static void destroy(T* first, T* last);
    // 获取某对象的地址
    static T* address(T& val);
    // 获取可配置T类型对象的最大数目
    static size_t max_size();
    // 使T类型的alloctor可以为U类型的对象分配内存
    template <typename U>
    struct rebind {
        using other = alloc<U>;
    };
};

template <typename T>
T* alloc<T>::allocate(size_t n) {
    return n == 0 ? 0 : static_cast<T*>(default_alloc::allocate(n * sizeof(T)));
}

template <typename T>
T* alloc<T>::allocate() {
    return static_cast<T*>(default_alloc::allocate(sizeof(T)));
}

template <typename T>
void alloc<T>::deallocate(T* ptr, size_t n) {
    if (n != 0)
        default_alloc::deallocate((void*)ptr, n * sizeof(T));
}

template <typename T>
void alloc<T>::deallocate(T* ptr) {
    if (ptr)
        default_alloc::deallocate((void*)ptr, sizeof(T));
}

由于其他接口的函数实现与上篇文章中的完全一致，所以就不放上来了，完整代码可以参见我的github项目里的alloc.h。

6 简单的性能分析和测试

包括上篇文章中的allocator，目前在 TinySTL 项目中我们已经实现了两种分配器，但尚未实现容器，所以我们可以先使用 STL 库中现有的容器对两种分配器做个小测试，对其性能做个对比。

由于vector容器每次使用分配器请求空间的时候，会请求现在长度的两倍，比如vector<int>，一个int在一般的机器上面长度是4B，即32bytes，当vector<int>原来长度等于5时，再次扩容长度就会变成10，一次就请求了5*32=160bytes，这之后再插入数据已经不会再调用第二级分配器了。

因此，如果向vector<int>中插入1000000个数，无非就是operator new和malloc的差距，然而实际上operator new就是用malloc实现的，所以性能差别不大。

所以，我们可以使用list<int>来对两种分配器进行测试，因为list内部就是个双向链表，每插一个int类型就会调用分配器请求一个32bytes的大小。测试代码如下

test_alloc.h

enum { NUMBERS = 10000000 };

void test_alloc() {
    // test of list
    // test of push_back
    std::list<int> list1; // std 默认分配器
    std::list<int, mystl::allocator<int>> list2;
    std::list<int, mystl::alloc<int>> list3;
    clock_t start = clock();
    // srand(time(NULL));
    for(size_t i = 0; i < NUMBERS; ++i)
        list1.push_back(1);
    clock_t end = clock();
    std::cout << "Time to insert " << NUMBERS
         << " numbers in list with STL alloctor: "
         << end - start << std::endl;
    start = clock();
    for(size_t i = 0; i < NUMBERS; ++i)
        list2.push_back(1);
    end = clock();
    std::cout << "Time to insert " << NUMBERS
         << " numbers in list with mystl alloctor: "
         << end - start << std::endl;
    start = clock();
    for(size_t i = 0; i < NUMBERS; ++i)
        list3.push_back(1);
    end = clock();
    std::cout << "Time to insert " << NUMBERS
         << " numbers in list with mystl SGI alloc: "
         << end - start << std::endl;
}

本来打算插入随机数的，想了想觉得没必要，还浪费调用rand()的时间，万一每次rand()的计算时间还不一样就不够客观了。所以直接插入1。在我的环境下跑了3次的结果如下：

Time to insert 10000000 numbers in list with STL alloctor: 1093750
Time to insert 10000000 numbers in list with mystl alloctor: 1078125
Time to insert 10000000 numbers in list with mystl SGI alloc: 921875

Time to insert 10000000 numbers in list with STL alloctor: 1140625
Time to insert 10000000 numbers in list with mystl alloctor: 1109375
Time to insert 10000000 numbers in list with mystl SGI alloc: 921875

Time to insert 10000000 numbers in list with STL alloctor: 1187500
Time to insert 10000000 numbers in list with mystl alloctor: 1359375
Time to insert 10000000 numbers in list with mystl SGI alloc: 1140625

可以看到，在以上的测试用例中，本篇文章中实现的alloc分配器性能不仅比上篇文章中的allocator强，甚至比STL默认的分配器表现得还要好。这其实也很正常，毕竟人家STL默认的分配器需要考虑各种情况下的性能，其覆盖的测试用例和测试场景海了去了，平均性能必然是没法比的，毕竟我们参照的是20年前的代码了。。。