从 STL 实现角度 看, 
`allocator 是 STL 其他组件实现 的 基础`

allocator 称为 空间配置器, 而不是 内存配置器, 
因为 空间 可以是 内存/磁盘/其他存储介质

1 仿 SGI std::allocator 设计 1个 符合 STL规范 的 allocator

// MyAllocator.h
#ifndef _MYALLOC_
#define _MYALLOC_

#include <new>     // placement new, set_new_handler()
#include <cstddef> // ptrdiff_t size_t
#include <cstdlib> // exit()
#include <climits> // UINT_MAX
#include <iostream>// ceer

namespace MY
{

//(1) 4大 global func: 分配/释放memory 构造/析构 obj
// 用于 被 allocator class 相应 mem func 调用
template <class T>
T* _allocate(ptrdiff_t n, T*)
{
    //set_new_handler(0);

    T* p = (T*)(::operator new((size_t)(n * sizeof(T) ) ) );
    if (p == 0)
    {
        std::cout << "out of memory" << std::endl;
        exit(1);
    }
    return p;
}

template <class T>
void _deallocate(T* p)
{
    ::operator delete(p);
}

template <class T1, class T2>
void _construct(T1* p, const T2& value)
{
    new(p) T1(value); // placement new
}

template <class T>
void _destory(T* p)
{
    p->~T();
}

template <class T>
class allocator
{
public:
    typedef size_t      size_type;
    typedef ptrdiff_t   difference_type;
    typedef T           value_type;
    typedef T* pointer;
    typedef const T* const_pointer;
    typedef T& reference;
    typedef const T& const_reference;

    template <typename U>
    struct rebind
    {
        typedef allocator<U> other;
    };

    // 4大函数: 分配/释放内存 构造/析构对象
    pointer allocate(size_type n)
    {
        return _allocate( (difference_type)n, (pointer)0);
    }

    void deallocate(pointer p, size_type n) // n 没用
    {
        _deallocate(p);
    }

    void construct(pointer p, const T& value)
    {
        _construct(p, value);
    }
    void destory(pointer p)
    {
        _destory(p);
    }

    pointer address(reference x)
    {
        return (pointer)&x;
    }
    const_pointer const_address(const_reference x)
    {
        return (const_pointer)&x;
    }
    size_type max_size() const
    {
        return size_type(UINT_MAX / sizeof(T));
    }
};

} // end of namespace MY

#endif //MYAllocator

#include "MyAllocator.h"
#include <vector>
#include <iostream>
int main()
{
    int a[3] = {0, 1, 2};
    std::vector<int, MY::allocator<int> > vec(a, a+3);

    for(int i = 0; i < vec.size(); i++)
        std::cout << vec[i] << std::endl;
}

Ubuntu 下 g++ 编译 运行正常, gdb调试

image.png

2 SGI 版本 从 标准 std::allocator 到 具有内存池设计 的 std::alloc

1.  P.J. 分配器 和 gcc2.91 标准分配器, 都叫 std::allocator, 
它 没有 独特设计, 底层都是 直接调 malloc / free

malloc 分配的内存 = 申请的内存 + 上/下 cookie
若频繁申请 小型区块, 比如 8Bytes, 
则 cookie 就占了 一半内存
-> `空间利用率低, 且易造成 内存碎片 
-> 解决: 内存池 设计

2. gcc2.91 有 标准分配器 std::allocator 却不用, 
而是用 special allocator std::alloc

其设计思维为:

(1) 多线程: 本节不讨论
(2) 模拟 C++ set_new_handler, 以处理 内存不足 状况

(3) 内存池 设计: 以应对 频繁申请 小型区块 时, 空间利用率低 与 内存碎片 问题

两级 配置器:

第1级 处理 >128 Bytes 区块: 仿 set_new_handler

第2级 处理 8*n (n = 1,...,16) <= 128 Bytes 区块: 
    16 个 free-list + 内存池

3. 16 个 free-list + 内存池

申请 n <= 128 Bytes 时, 多分配若干 Bytes, 存于

两级缓存

第 1 / 2 级放 free-list / 内存池, 使得 

下次申请 ( 的 区块大小 前面已申请过 ) 时, 可能 直接/间接 从 free-list / 内存池 中 取, 而不是 又 让 OS 分配

// request memory block 的 process strategy:
if (memory pool 完全满足需求: <= 20 个 区块. 
        若 modify internal_req_obj_num, 则 取 < )
    (1) 提供 所需
else if (memory pool 不完全满足需求, 但能提供 n >=1 个 区块)
    (2) 提供 n 个区块
        modify internal_req_obj_num
else // memory pool 连 1个 区块 也 提供不了                 
    (3) 先将 memory pool 所有剩余 space 配给 相应 free_list[i]
    (4) 再向 OS 申请 -> malloc 分配 heap memory: bytes_to_get
    若 heap memory 不足 -> malloc 失败 
        (5) 循环遍历 free_list[i, i+1, ...] 中 
        larger( => 必为 req_mem_blk_size_8_align 整数倍 
                => 必 在 更后面的 free_list[j>i] )
        且 unused 区块 
        若有 
            (6) 拨出 1 个 mem_blk 放 memory pool(当前已 empty)
                
            (7) 递归 调 chunk_alloc 自身, 再次 从 memory pool 申请
                modify internal_req_obj_num             

4. free-list + 内存池 分配 的 例子

(1) 初次申请 32 Bytes
free-list[32/8 -1= 3] 和 内存池 均 empty,  

-> malloc 分配 2 * 20 * 32 Bytes + 
    随 分配次数增大而增大的 附加量 ( 初始 为 0 ) 
= 40 * 32 Bytes:
1) 第   1 个 32 Bytes return 给 client
2) 随后 19 * 32 Bytes 放 free-list ( 第 1 级 缓存 )
3) 随后 20 * 32 Bytes 放 内存池 ( 第 2 级 缓存 )

(2) 第 2 次 申请 64 Bytes
free-list[64/8 - 1] = free-list[7] empty
-> 尝试 从 内存池 取, 取 20*32/64 = 10 个 64 Bytes 区块:
    第 1 个 return 给 client /
    随后 (只剩) 9 个放 free-list[7] /
    内存池 become empty /

(3) 第 3 次 申请 96 Bytes
free-list[11] 和 内存池 均 empty
-> malloc 分配 2 * 20 * 96 + n (余量) Bytes:
    第   1 个 96 Bytes return 给 client /
    随后 19 * 96 Bytes 放 free-list[11] /
    其余放 内存池

image.png

5. 1/2 级 allocator + wrapper class template simple_alloc + vector 容器 -> framework

下图中 第1级 配置器 type 别名 不对, 应该为 malloc_alloc

image.png

两级 allocator 本身 均为 class template: 
    但无 template para, 都 只是 普通参数
    inst 完全没用 + 第 2 级 allocator 多线程参数 本节不考虑 
-> 本文 source code 中 allocator name 中不带 template

// 第 1 级 allocator
template <int inst>
class __malloc_alloc_template;

// 第 2 级 allocator
template <bool threads, int inst>
class __default_alloc_template;

别名:
__malloc_alloc / malloc_alloc

__default_alloc_template / alloc

simple_alloc<...> / data_allocator

#include <cstddef> // std::size_t

//------ 1. 第 1 级 allocator
class __malloc_alloc
{
public:
    static void* allocate(size_t n)
    {
        //(1)
        set_new_handler(handler); //<=> set_new_handler(&handler);

        void* result = malloc(n);

        // malloc 失败时, 调 oom_malloc()
        if (0 == result)
            result = oom_malloc(n);
        return result;
    }
        
    // ...
    
    static void deallocate(void* p, size_t)
    {
        free(p);
    }   
};
typedef __malloc_alloc malloc_alloc;


//------ 2. 第 2 级 allocator
class __default_alloc
{
public
    static void* 
    allocate(size_t req_blk_size)
    {   // client 请求: req_blk_size
        if( req_blk_size > (size_t)MAX_BYTE )
        {
            return ( malloc_alloc::allocate(req_blk_size) );
        }
        
        // ...
        
        void *result_prev = refill( ROUND_UP(req_blk_size) );
    }
    
    void* refill(size_t req_blk_size_align)
    {
        //(1) req_blk_num: allocator 内部 (欲) 请求
        // 1) 尝试 向 memory pool 请求 20 个 memory block 
        //   放 相应 free_list:
        // 2) pass by reference to chunk_alloc to be modified
        int req_blk_num = 20; 
        
        //(2) request memory_block from memory pool
        // 1) memory pool 能提供 几(>= 1) 个 memory block,
        //    就 分配 几个 
        // 2) 若 连 1 个 也 提供不了, 
        //    则 剩余 space 先配给 相应 free_list[i]
        //       再 向 OS 申请: malloc 分配   
        char* chunk = 
            chunk_alloc(req_blk_size_align, req_obj_num);
            
        //(3) 将 分配的 chunk memory:
        // 1) return to client 
        // 2) 放 相应 free_list[i]
        // 3) 放 memory pool (maybe)
            
    }
    
    // request memory_block from memory pool
    // memory_block 用 union obj 表示
    char* chunk_alloc(size_t req_blk_size_align, int& req_obj_num)
    {
        if ( memory pool 完全满足需求: <= 20 个 区块. 若 modify req_obj_num, 则 取 < )
            提供 所需
        else if (memory pool 不完全满足需求, 但能提供 n >=1 个 区块)
            提供 n 个区块
                modify req_obj_num
        else // memory pool 连 1个 区块 也 提供不了
        {    
            bytes_to_get = 2 * half_blks_bytes_to_get  
                           + ROUND_UP(heap_size >> 4); 
                           
            (4) 先将 memory pool 所有剩余 space 配给 相应 free_list[i]
            
            
            (5) 再向 OS 申请 -> malloc 分配 heap memory: bytes_to_get
            若 heap memory 不足 -> malloc 失败
            {   
                (6) 从 req_blk_size_align 相应 free_list[i] 
                    下一 free_list 开始,
                循环遍历 后面 free_list[ j > i ]: 可能含 `unused larger 区块`
                {   
                    若 free_list[j] 有 `unused larger 区块(必为 req_blk_size_align 整数倍)`
                    {
                        (7) 从 free_list[j] 拨出 1 个 mem_blk 
                        放 memory pool(当前已 empty),
                        即 adjust 3 个 pointer:
                            相应 *my_free_list 指向 原先 list 下一 obj
                            memory pool start/end pinter 指向 拨出的 mem_blk 首/尾
                        
                        (8) return ( chunk_alloc(req_blk_size_align, req_obj_num) );
                        递归 调 chunk_alloc 自身, 再次 从 memory pool 申请,
                        以 modify req_obj_num
                            只 递归 1次 就结束 
                            因为 从 相应 free_list[i]
                            拨到 memory pool 的 mem_blk 
                            必然 是 req_blk_size_align 的 整数倍
                    }
                }
                (9) 若执行到 该行 => free_list 也没 空间了
                 1) memory pool 尾 pointer 先置 空: end_free = 0;
                 2) 调 第 1 级 allocator, 看 out-of-memory 机制 是否能 分配
                star_free = (char*)malloc_alloc::allocate(bytes_to_get);
            }
            (8) update heap_size: 
            每次 向 memory pool 请求 memory 时, 
            若 走 case3 向 OS 请求,
            则 要 增加 heap_size +=  byte_to_get
            使得 下次 再向 OS 申请 时, 再多申请些
                
            (10) return ( chunk_alloc(req_blk_size_align, req_obj_num) );
            递归 调 chunk_alloc 自身, 再次 从 memory pool 申请,
        }
    }
};

// default value of template para in vector
typedef __default_alloc alloc; 


//------ 3. wrapper class template: simple_alloc
//(1) 意义: 两级 allocator 分配/释放 memory 的 
//       interface func para 是 req_blk_size_align
//    => directly call 时, 要 指定 req_blk_size_align
//       而 对 client 而言, 更方便的 interface 是
//       只指定 要 分配/释放 的 elem_type 及 elem_num
//    -> solution: 加 1 层 中介层
//       1) 据 elem_type 及 elem_num -> 求 req_blk_size_align 
//       2) call allocate/deallocate
//    -> implememt: wrapper class template

//(2) 分配/释放 memory 的 strategy:
// directly call 第 2 级 allocator 的 allocate/deallocate func
// -> 据 memory size > 128 Bytes 时, 
//    再 转调 第 1 级 allocator 的 allocate/deallocate func
template<class T, class Alloc>
class simple_alloc
{
public:
    static T* 
    allocate(size_t elem_num)
    {
        return 0 == elem_num ? 0 : 
            T * Alloc::allocate(elem_num * sizeof(T) );
    }

    static void 
    deallocate(T* p, size_t elem_num)
    {
        if( elem_num != 0)
            Alloc::deallocate(p, elem_num * sizeof(T) );
    }
};

//------ 4. 容器: 直接 用 wrapper class
// 容器 的 2 个 template para 绑定 在一起
template <class T, class Alloc = alloc >
class vector
{
    // ...
protected:
    typedef simple_alloc<T, Alloc> data_allocator;
    
    iterator // T*
    allocate_and_fill(size_type elem_num, const T& x)
    {
        iterator result = data_allocator::allocate(elem_num);
        
        std::uninitialized_fill_n(result, elem_num, x);
        
        return result;
    }
    
    void deallocate()
    {
        if(start)
            data_allocator::deallocate(start, 
                            end_of_storage - start);
    }
};

//------ heap_size
请求次序 req_blk_size      req_obj_num  是否向 OS 请求
1          32                20                  是 
2          64                20->10              否 
3          96                20->                是 
                                                
请求次序  bytes_to_get                heap_size
1         2*(20*32)=1280+0            0 -> += 1280 = 1280
2         不计算                     不计算
3         2*(20*96)+1280>>4 -> 8倍数  1280 -> += 3920 = 5200
          = 3840 + 80 = 3920                        
                    
(1) client 请求的 memory block: 
    req_blk_size

(2) allocator 内部 欲请求 byte 数: 分 2 部分
1) 多请求 的 若干块: internal_req_obj_num

2) 每次向 OS 请求, 会 将 
allocator 内部 欲请求 byte 数
累加 到 1个 static 累加量 heap_size 中,
下次 再 OS 请求 时, 在 `多请求的 若干块 之外`,
再 附加 该 累加量 heap_size 除 16 -> 上调到 8 的 倍数 
使得 再多分配些 

allocator 内部 欲请求 byte 数
= bytes_to_get 
= 2 * half_blks_bytes_to_get  + ROUND_UP(heap_size >> 4)
maybe 不等于 最终分配的 byte 数

half_blks_bytes_to_get 
= req_blk_num_unmodified * req_blk_size_align 
= 20 * req_blk_size_align = 8 的 倍数
          
ROUND_UP(heap_size >> 4) 
= 除 16 result -> 上调到 8 的 倍数 

3 第 1 级 allocator 设计

3.1 std::set_new_handler: <new>

typedef void (* new_handler)();

std::new_handler 
set_new_handler (std::new_handler new_p) throw();

std::set_new_handler is called by the default allocation functions ( operator new and operator new[] ) when they fail to allocate storage

Para:
new_p: pointer to function of type std::new_handler, or null pointer

Return value:
previously-installed new handler, or a null pointer value if none was installed.

用途:
1) make more memory available
2) terminate the program (e.g. by calling std::terminate)
3) throw exception of type std::bad_alloc or ...

#include <iostream>
#include <new>

void handler()
{
    std::cout << "Memory allocation failed, terminating\n";
    std::set_new_handler(nullptr);
}

int main()
{
    std::set_new_handler(handler);

    try
    {
        while (true) 
        {
            new int[100000000ul];
        }
    }
    catch (const std::bad_alloc& e)
    {
        std::cout << e.what() << '\n';
    }
}

3.2 第 1 级 allocator: malloc_alloc

模拟 C++ 中 std::set_new_handler, 以处理 memory 不足 的 case

// 模拟 std::set_new_handler implement
typedef void (* new_handler)();

// 2 者 等价: 用 typedef 的 别名 最 simple
new_handler set_new_handler(new_handler pf) 
void (* set_new_handler( void (* pf)() ) ) ()

typedef 优势在此十分明显, 清楚的指出 
set_new_handler return value 为 function pointer type,
the pointed func taking no arguments and returning no value

4 第 2 级 allocator: std::alloc 设计

image.png

5 第1/2 级 allocator source code

1. std::alloc 管理 free_list 的 设计思路

(1) list node 的 pointer 域 不独占 memory 的 设计

通常, list 的 每个 node 要设一 额外 pointer 域 next, 
以 指向 the next node

节省 该 pointer 域 memory space 的 方法:

1) 第 i 条 free_list[ i = 0-15 ] 管理 最多 20 个  node
`每个 node  表示 1个 大小为 8*(i+1) Bytes 的 memory block` 

2) `pointer 域 只占 4 Bytes (32 位 OS)`

3) memory block is `uninitialized` 

设 node 最前面的 4 Bytes memory 的 data structure 为 1 个 名为 obj 的 union

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

从 第 1 / 2 字段 观之, obj is a pointer to the next obj union / the first char memory of the current memory block

the requested req_blk_num 个 mem_blk 是 连续 memory

用 union 实现 一物二用

使得 管理 list 时, 无需 为 每个 node 单独分配 pointer 域,
提高了 memory 空间利用率

Java 中 无法实现 该 技巧

(2) free_list[ FREE_LIST_NUM ] array

1) 放 private: 只 std::alloc 内部用 

2) array elem: free_list[i = 0-15] 
is the head pointer to the first obj of the ith list
type: obj* 

3) array name: free_list
type: obj**

2. volatile

(1) volatile 
tell compiler 其 修饰的 variable 随时可变,
编译后的 code 每次 read/write 该 variable 时,
`直接 对 variable memory read/write`

若无 volatile, 则 compiler 可能 
借助 register/高速cache 优化 read/store(write)

(2) 含义:
1) volatile `总是 与 compiler 优化 相关`

2) volatile 字面含义是 易变的

(3) 作用:
1) 告诉 compiler 不要 cache variable 到 register/高速cache 

`多任务 / 中断` 下, variable 可能被 other program(如 thread) 改变, 
compiler 无法感知到, volatile 就是 告诉 compiler 
不要 在 两个操作 之间 缓存 variable 到 register/高速cache

2) 对 volatile variable 的 read/write 不会被 优化掉

(4) note: volatile 并不保证 对 内存操作 的 原子性

#include <iostream>

//------ 1. 第 1 级 allocator
class __malloc_alloc
{
private:
    // note: func name 本身就是 func address:
    //  即 func <=> &func

    //(1) new_handler :    为 func pointer type 
    // new_handler pf : pf 为 func pointer
    // void (* pf)()  : pf 为 func pointer
    typedef void (*new_handler)();

    //(2) global handler : record the current func pointer
    static new_handler global_handler;

public:
    static void* allocate(size_t n)
    {
        //(3)
        set_new_handler(handler); //<=> set_new_handler(&handler);

        void* chunk = malloc(n);

        // malloc 失败时, 调 oom_malloc()
        if (0 == chunk)
            chunk = oom_malloc(n);
        return chunk;
    }

    //(4) set_new_handler: 仿 std::set_new_handler
    static new_handler set_new_handler(new_handler pf)
    {
        new_handler previous_handler = global_handler;

        // update global handler to be specified func's pointer
        global_handler = pf;

        return previous_handler;
    }

    //(5) handler func
    static void handler()
    {       // 企图 释放 memory
        std::cout << "make more memory available\n";
        std::set_new_handler(nullptr);
    }

    //(6)
    static void* oom_malloc(size_t n)
    {
        new_handler local_handler = 0;
        void* mem;

        // 不断尝试(这里限制次数) 释放, 配置, 释放, 配置
        for (int i = 0; i < 3; i++)
        {
            // 1) 取 the recorded handler func pointer from global_handler
            local_handler = global_handler;

            if (0 == local_handler)
                continue;

            // 2) 调 specified handler func
            (*local_handler)();

            // 3) malloc again
            mem = malloc(n);
            if (mem)
                return mem;
        }
    }

    static void deallocate(void* p, size_t)
    {
        free(p);
    }
};
typedef __malloc_alloc malloc_alloc;
malloc_alloc::new_handler malloc_alloc::global_handler = 0;


//------ 2. 第 2 级 allocator
//--- 3个 enum
enum
{
    ALIGN = 8 // 最小 memory block
};
enum { MAX_BYTES = 128 };
enum { FREE_LIST_NUM = MAX_BYTES / ALIGN }; // 16 条 free_list 

class __default_alloc
{
private:
    // union 一物二用: 实现 节省 list node 的 pointer 域 空间
    union obj 
    {
        union obj* next;
        char client_data[1];      
    };

    // --- 4 static mem
    // free_list[16] array: 16 free-list
    static obj* volatile 
        free_list[FREE_LIST_NUM];

    // memory pool management: 2 pointer 
    static char* start_free;
    static char* end_free;
    
    // accumulate var: request memory from OS 时, 
    // 用于 下次再 request from OS 时, 附加 request 的量
    static size_t heap_size;


    // request_mem_blk_bytes -> which free_list: free_list[i]
    static size_t freelist_index(size_t request_mem_blk_bytes)
    {
        return (request_mem_blk_bytes + ALIGN - 1) / ALIGN - 1;
    }

    // request_mem_blk_bytes 上调至 8(= b1000) 的倍数:
    // & 1111 1000 = & ~(ALIGN - 1)
    static size_t ROUND_UP(size_t request_mem_blk_bytes)
    {
        return (request_mem_blk_bytes + ALIGN - 1) & ~(ALIGN - 1); 
    }

    static void* refill(size_t n);
    static char* chunk_alloc(size_t n, int& req_blk_num );

public: // 2 interface func
    static void* allocate(size_t req_blk_size);
    static void deallocate(void* p, size_t n);
};

typedef __default_alloc alloc;


//--- 4 static mem data initialize
alloc::obj* volatile 
alloc::free_list[FREE_LIST_NUM] = { 0 };

char* alloc::start_free = 0;
char* alloc::end_free = 0;
size_t alloc::heap_size = 0;

void* alloc::allocate(size_t req_blk_size)
{   // client 请求: req_blk_size, 只 请求 1 个 memory blk
    obj* volatile* my_free_list;
    
    obj* target_free_list_pobj;
 
    if( req_blk_size > (size_t)MAX_BYTES )
    {
        // 转向 调 第 1 级 allocator
        return ( malloc_alloc::allocate(req_blk_size) );
    }

    my_free_list = free_list + freelist_index(req_blk_size);
    target_free_list_pobj = *my_free_list;
    
    if (target_free_list_pobj == 0) // list empty
    {
        // request mem-blk from memory pool
        void *res = refill( ROUND_UP(req_blk_size) );
        return res;
    }

    // seperate the first mem_blk from target_free_list
    *my_free_list = target_free_list_pobj->next;
    
    // void* p = pobj => pobj implicitly converted to void*
    return target_free_list_pobj;
}

void* __default_alloc::refill(size_t req_blk_size_align)
{
    int req_blk_num  = 20;

    //(1) allocator 内部 尝试 / 实际 request 
    // req_blk_num < / = 20 个 区块 from memory pool
    // req_blk_num pass by reference to be modified
    char* chunk = chunk_alloc(req_blk_size_align, req_blk_num );

    obj* volatile* my_free_list;
    obj* return_pobj, * current_pobj, * next_pobj;
    
    //(2) 只请求到 1 个 mem_blk
    if (0 == req_blk_num || 1 == req_blk_num  ) // else >= 2
        return chunk;
    
    //(3) the first mem_blk to be returned to client
    return_pobj = (obj*)chunk; 

    //(4) other req_blk_num -1 个 mem_blks linked to free_list
    my_free_list = free_list 
                 + freelist_index(req_blk_size_align);

    *my_free_list 
        = next_pobj 
        = (obj*)(chunk + req_blk_size_align); 
    
    // 第 2th ~ req_blk_num th mem_blk linked to list
    // the requested req_blk_num 个 mem_blk 是 连续 memory
    // loop every mem_blk: 
    // 1) initialize next_head point to the start 
    // 2) current_head point to next_head
    // 3) next_head updated to point to the real next blk
    //    => [current_head, next_head) 为 the current blk
    // 4) link
    for (int i = 0; ; i++)
    {
        current_pobj = next_pobj;                  
        next_pobj = (obj*)( (char*)next_pobj 
                            + req_blk_size_align ); 
                            
        // 第 2 ~ req_blk_num - 1 个 blk         
        if (i < req_blk_num  - 2) 
        {
            current_pobj->next = next_pobj; 
        }
        else // 第 req_blk_num 个 blk
        {
            current_pobj->next = 0;
            break;
        }
    }
    return return_pobj;
}

char* __default_alloc::
chunk_alloc(size_t req_blk_size_align, int& req_blk_num )
{
    char* chunk;
    size_t half_blks_bytes_to_get = req_blk_num * req_blk_size_align;
    size_t mem_pool_left = end_free - start_free;

    //(1) mem_pool_left 够 req_blk_num 个 blk -> 分配 req_blk_num 个
    if (mem_pool_left >= half_blks_bytes_to_get)
    {
        chunk = start_free;      
        start_free += half_blks_bytes_to_get;
        return chunk; // 递归出口            
    }
    else if (mem_pool_left > req_blk_size_align) 
    { //(2) 够 n >=1 个 blk => 分配 n 个 
        req_blk_num  = mem_pool_left / req_blk_size_align;   
        half_blks_bytes_to_get = req_blk_num * req_blk_size_align;
        
        chunk = start_free; 
        start_free += half_blks_bytes_to_get;
        return chunk; // 递归出口
    }
    else // (3) 不够 1 个 blk: request from OS, molloc will allocate
    {
        //(4) mem_pool 余量 全 配给 适当 free_list[i]
        if (mem_pool_left > 0)
        {
            // mem_pool 不足 1 个 req_blk:
            // 必然有 刚好能 store 该 req_blk 的 某个 free_list
            // 头插法 insert into 该 free_list
            obj* volatile* my_free_list
                = free_list + freelist_index(mem_pool_left);
                
            ( (obj*)start_free )->next = *my_free_list;
            *my_free_list = (obj*)start_free;
        }
        
        //(5) 向 OS 请求
        size_t bytes_to_get = 2 * half_blks_bytes_to_get 
                            + ROUND_UP( heap_size>>4 );
        start_free = (char*)malloc(bytes_to_get);
        
        if (start_free == 0) 
        {   // heap memory 不足 -> malloc 失败
            // (6) 从 req_blk_size_align 相应 free_list[i] 下一 free_list 开始,
            // 循环遍历 后面 free_list[ j > i ]: 可能含 `unused larger 区块`
            //      larger_blk 必为 req_blk_size_align 整数倍大小
            // 若 有 
            //    (7) 拨 1 个 mem_blk 放 mem_pool
            //    (8) 再 调 自身 chunk_alloc, 向 mem_pool 申请
            obj* volatile * my_free_list, *p;
            for(size_t size = req_blk_size_align;
                size <= MAX_BYTES;
                size+= ALIGN)
            {
                my_free_list
                    = free_list + freelist_index(mem_pool_left);
                p = *my_free_list;
                
                if(p)
                {
                    //(7)
                    *my_free_list = p->next;
                    
                    start_free = (char*)p;
                    end_free = start_free + size;
                    
                    //(8)
                    return ( chunk_alloc(size, req_blk_num) );
                }
            }
            
            //(9)
            end_free = 0; // execute here => there are no memory anywhere
            // 看 第 1级 allocator 的 out_of_memory 是否 有作用
            start_free = (char*)malloc_alloc::allocate(bytes_to_get);   
        }

        //(10) update heap_size
        heap_size += bytes_to_get;

        //(11) update mem_pool tail
        //     head 在 前面已 modify
        end_free = start_free + bytes_to_get;

        //(12) 递归调自己, 以修正 req_blk_num 
        return chunk_alloc(req_blk_size_align, req_blk_num );
    }
}

void __default_alloc::deallocate(void* p, size_t req_blk_size)
{
    if (req_blk_size > (size_t)MAX_BYTES)
    {
        //(1) 调 第1级 allocator
        malloc_alloc::deallocate(p, req_blk_size);
        return;
    }
    
    obj* q = (obj*)p;
    obj* volatile* my_free_list;
    
    my_free_list = free_list 
                 + freelist_index(req_blk_size);

    //(2) recycle the freed mem_blk to free-list
    q->next = *my_free_list;
    *my_free_list = q;
}

//------ 3. wrapper class template: simple_alloc
template<class T, class Alloc>
class simple_alloc
{
public:
    static T*
        allocate(size_t elem_num)
    {
        return 0 == elem_num ? 0 :
            (T *) Alloc::allocate(elem_num * sizeof(T));
    }

    static void
        deallocate(T* p, size_t elem_num)
    {
        if (elem_num != 0)
            Alloc::deallocate(p, elem_num * sizeof(T));
    }
};

// --- data
typedef struct data_32
{
    char mem[32];
}Data_32;

int main()
{
    typedef simple_alloc<Data_32, alloc> data_allocator;
   
    Data_32* p1= data_allocator::allocate(1); // 32 Bytes
    p1 = data_allocator::allocate(2); // 64 Bytes
    p1 = data_allocator::allocate(3); // 96 Bytes
}

4. std::allocator 和 std::alloc 用法

std::vector<int, std::allocator<int> > vec;

// 容器 的 2 个 template para 绑定 在一起
std::vector<int, std::alloc > vec;