C++ membery primitives

• 第四种方法在不同的编译版本上有着不同的使用方法

#ifdef _MSC_VER
    int *p4 = allocator<int>().allocate(3, (int*)0);
    allocator<int>().deallocate(p4, 3);
#endif

#ifdef __BORLANDC__
    int *p4 = allocator<int>().allocate(5);
    allocator<int>().deallocate(p4, 5);
#endif

#ifdef __GNUC__
    // 在早期的 GUNC 中使用这种调用方法
    void *p4 = alloc::allocate(512);
    alloc::deallocate(p4, 512);
    // 在后期的 GUNC 中进行了进一步的优化和区分
    int *p4 = allocator<int>().allocate(7);
    allocator<int>().deallocate((int*)p4, 7);
    // 而早期的 alloc 仍然十分重要，于是换成了这种写法
    void *p5 = __gnuc_cxx::__pool_alloc<int>().allocate(9);
    __gnuc_cxx::__pool_alloc<int>().deallocate((int*)p5, 9);
#endif

new/delete expression

new 会先分配内存，然后调用构造函数，所以 new 的具体实现如下，而平时重载的 new，都是重载了 ::operator new

Complex *pc = new Complex(1, 2);
            ↓↓
try {
    void *mem = operator new(sizeof(Complex));// operator new 的实现调用了 malloc
    pc = static_cast<Complex*>(mem);
    pc->Complex::Complex(1, 2);
    // 在 GCC 中用户无法直接使用构造函数
} catch(std::bad_alloc) {
}

delete pc;
    ↓↓
pc->Complex::~Complex();
operator delete(pc);    // operaotr delete 的实现调用了 free

array new/delete

通过 new 开辟一个数组，在数组的起始位置会分配一个 4 字节的 cookie，在 cookie 里面记录了这次分配数组的长度。如果使用 delete 释放，只会释放其中的一块，其他块就发生内存泄漏，而使用 delete[] 释放，就可以保证申请的内存完全被释放了。

对于数组的构建和删除的过程中，按 0、1、2 下标顺序调用构造函数，按 2、1、0 下表顺序调用析构函数。

placement new

placement new 允许我们将对象构造于一个已经分配的内存中

char *buf = new char[sizeof(Complex)*3];
Complex *pc= new(buf)Complex(1, 2);
            ↓↓
try {
    void *mem = operator new(sizeof(Complex), buf);
    // 和 new 不同的地方在于多传了 buf 参数，于是 operator new 什么也不做直接返回 buf
    pc = static_cast<Complex*>(mem);
    pc->Complex::Complex(1, 2);
} catch(std::bad_alloc) {
}

class allocate

malloc 在分配内存的首尾分别会有 4 个字节的 cookie，记录了分配的内存的大小。所以频繁的 malloc 会造成很大一部分的内存浪费。

解决这种方法的技术是通过内存池技术，我可以一次性分配一大块的内存，在后续程序分配内存过程中，从这一大块中分配出一部分以供程序使用。

• 第一版的内存管理技术如下

class Screen{
public:
    static void* operator new(size_t size) {
        Screen *p;
        if(!freeStore){ // 如果没有可以用的内存空间，则再分配一次
            size_t chunk = screenChunk * size;
            freeStore = p = reinterpret_cast<Screen*> (new char[chunk]);  // char 字节为 1
            for(; p != &freeStore[screenChunk - 1]; ++ p){
                p -> next = p + 1; // 将得到的内存串成链表
            }
            p -> next = NULL;
        }
        p = freeStore;
        freeStore = freeStore -> next;
        return p;
    }
    static void operator delete(void *p) {
        (static_cast<Screen*>(p))->next = freeStore;
        // 显然，把 delete 掉的内存空间直接插入到头部，是最快的插入方式
        freeStore = static_cast<Screen*>(p);
    }
private:
    Screen *next;
    static Screen *freeStore;   // 将可用内存用链表形式存储，存下链表头指针
    static const int screenChunk;   // 选择一次性分配的内存空间
private:
    int i;
    /* 在第二版中，使用如下方法
    union {
        int i;
        Screen *next;
    }
        因为 next 只有在没有使用的时候才有意义，i 只有在被使用的时候才有意义，所以可以使用 union 来节省内存的消耗
    */
};
Screen* Screen::freeStore = NULL;
const int Screen::screenChunk = 24;
int main() {
    // freopen("in", "r", stdin);
    Screen *p[100];
    for(int i=0; i<100; i++) {
        p[i] = new Screen;
    }
    cout << "size of Screen " << sizeof(Screen) << endl;
    for(int i=0; i<10; i++) {
        cout << "address of p[" << i << "] " << p[i] << endl;
    }
    return 0;
}

• 第二版本和第一版本类似，只是加上了 union 优化。
• 前两个版本的分配内存操作都是在对象内实现的，然而对于每一个对象都写一个内存分配显然不符合实际，所以第三版本就是将内存分配的过程提取出来，单独封装成一个类 allocate，在每个类内存包含这个 allocate，然后调用 allocate 的函数完成分配过程。

new handler

当 operator new 没有能力分配足够的内存时，会抛出一个 bad_alloc 异常。但在抛出异常之前，其实系统会调用你设定了 new_handler 函数，这是 C++ 平台给程序员提供的一种方式。

typedef void(*new_handler);
new_handler set_new_handler(new_handler p)  throw();

优秀的 new handler 应该完成两件事：

• 让更多的内存可用
• 调用 abort 或 exit 放弃操作，结束程序。

std::allocator

std::allocator 运行模式

allocator 维护 16 个链表 free_list[16]，每个链表维护一个固定大小的内存池，从 free_list[0] 维护 8 字节开始，每个的链表比上一个链表多维护 8 个字节。当应用程序想要分配一个大小的内存，会向上调整到 8 的整数，然后从链表中分配。

allocator 每次会分配 size * 20 * 2 + RoundUp() 的内存，前 20 个块给链表，后面的一半内存称为备用池 pool，就是多分配出的一部分等着给下一次分配使用，从 pool 切出来的数量永远控制在 1-20 之间。RoundUp 是随着轮次的增多，每次多分配的内存，计算方式是 累计申请量>>4，然后调到 8 的倍数。

分配过程通过例子来解释：假设系统内存为 10000

• 分配 32 字节，此时 free_list[3] 为空且 pool 为空，所以会通过 malloc 一次分配 32 * 20 * 2 + RoundUp(0>>4) 字节。然后从中切出第一块给客户，剩下的 19 个块挂到 free_list[3] 上。后面的 *2 操作就是给 pool 的大小。
  • 累计申请量：1280，pool 大小：640
• 分配 64 字节，此时 free_list[7] 为空但存在 pool，所以直接把 pool 分配给它用，切出第一块给客户，剩下 9 块挂到 free_list[7] 上。
  • 累计申请量：1280，pool 大小：0
• 分配 96 字节，此时又重复第一次的过程，分配 96 * 20 * 2 + RoundUp(1280>>4) 字节并拿出前 20 块给 free_list[11] 使用。
  • 累计申请量：5200，pool 大小：2000
• 分配 88 字节，此时 free_list[10] 为空但存在 pool，所以从 pool 分配，因为从 pool 每次分配的块数在 1-20 之间，也就是分配了 20 个出来。
  • 累计申请量：5200，pool 大小：240
• 连续申请 3 个 88 字节，因为 free_list[10] 里面还有 19 个空闲，所以直接分配 3 个给客户
  • 累计申请量：5200，pool 大小：240
• 申请 8 字节，此时 free_list[0] 为空但存在 pool，所以直接从 pool 分配 20 块 8 字节给 free_list[0] 使用
  • 累计申请量：5200，pool 大小：80
• 申请 104 字节，此时 free_list[12] 为空但 pool 不够分配一块，那么把 80 的 pool 分配给 free_list[9]，在通过 malloc 分配 104 * 20 * 2 + RoundUp(5200>>4) 字节
  • 累计申请量：9688，pool 大小：2408
• 申请 112 字节，此时 free_list[13] 为空但存在 pool，所以直接从 pool 分配20 块挂到 free_list[13] 上
  • 累计申请量：9688，pool 大小：168
• 申请 48 字节，此时 free_list[5] 为空但存在 pool，所以直接从 pool 分配 3 个挂到 free_list[5] 上
  • 累计申请量：9688，pool 大小：24
• 申请 72 字节，此时 free_list[8] 为空但 pool 不够分配一块，那么先把 24 字节的 pool 挂到 free_list[2] 上，然后又要通过 malloc 分配。显然此时系统已经没有多余的内存完成分配，那么系统会从已经分配的最接近 72 的资源里面分配一块给客户使用，也就是说此时会从 free_list[9] 分配一块 80 字节的块并切成 72+8 的两部分，第一部分分配给客户，第二部分变成 pool。
  • 累计申请量：9688，pool 大小：8
• 申请 120 字节，此时 free_list[14] 为空但 pool 不够分配一块，那么先把 8 字节的 pool 挂到 free_list[0] 上，显然此时 malloc 仍然不够内存使用，但 free_list[14] 和 free_list[15] 都是空的，那么就办法分配了。
  • 累计申请量：9688，pool 大小：0

allocator 第二级配置器源码

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

class alloc {
private:
    union obj{
        union obj* free_list_link;
    };
    static char* start_free;                // 指向 pool 的头
    static char* end_free;                  // 指向 pool 的尾
    static size_t heap_size;                // 累计分配量
    static obj* free_list[__NFREELISTS];    // free_list 数组

    static size_t ROUND_UP(size_t bytes) {  // 将 bytes 向上调整到 8 的倍数
        return ((bytes + __ALIGN-1)) & ~(__ALIGN-1);
    }
    static size_t FREELIST_INDEX(size_t bytes) {    // 获得应该从哪个 free_list 分配内存
        return (bytes+__ALIGN-1)/__ALIGN -1;
    } 
    static void* refill(size_t n) {         // 为链表填充内存，此时的 n 已经是 8 的倍数
        int nobjs = 20;
        char *chunk = chunk_alloc(n, nobjs);
        obj **my_free_list;
        obj *result;
        obj *current_obj;
        obj *next_obj;
        if(1 == nobjs)  return chunk;
        my_free_list = free_list + FREELIST_INDEX(n);
        result = (obj*)chunk;
        *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->free_list_link = NULL;
                break;
            } else {
                current_obj->free_list_link = next_obj;
            }
        }
        return result;
    }
    static char* 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) {      // 先从 pool 池分配，如果能够满足分配 20 个块
            result = start_free;
            start_free += total_bytes;
            return result;
        } else if(bytes_left >= size) {      // 如果不够 20 个但至少能分配一个
            nobjs = bytes_left/size;
            total_bytes = size*nobjs;
            result = start_free;
            start_free += total_bytes;
            return result;
        } else {                            // pool 池不够用
            size_t bytes_to_get = 2*total_bytes+ROUND_UP(heap_size>>4);
            if(bytes_left > 0) {         // 处理 pool 池碎片
                obj **my_free_list = free_list + FREELIST_INDEX(bytes_left);
                ((obj*)start_free)->free_list_link = *my_free_list;
                *my_free_list = (obj*)start_free;
            }
            start_free = (char*)malloc(bytes_to_get);   // 先分配到 pool 池中
            if(0 == start_free) {           // 如果系统内存不够分配
                obj **my_free_list;
                obj *p;
                for(int i=size; i<=__MAX_BYTES; i += __ALIGN) {  // 往后找一块可以拿来用的内存
                    my_free_list = free_list + FREELIST_INDEX(i);
                    p = *my_free_list;
                    if(0 != p) {            // 如果找到一块可以用的
                        *my_free_list = p->free_list_link;
                        start_free = (char*)p;
                        end_free = start_free+i;
                        return chunk_alloc(size, nobjs);// 扩充的 pool，所以在分配一次一定可以分配到
                    }
                }
                // 尝试利用一级配置器分配内存
                end_free = 0;
//              start_free = (char*)malloc_alloc::allocate(bytes_to_get);
            }
            heap_size += bytes_to_get;
            end_free = start_free + bytes_to_get;
            return chunk_alloc(size, nobjs);            // 扩充的 pool，所以在分配一次一定可以分配到
        }
    }

public:
    static void* allocate(size_t n) {
        obj **my_free_list;                 // obj**
        obj *result;
        if(n > (size_t)__MAX_BYTES) {        // 改用第一级p配置器
//          return malloc_alloc::allocate(n);
        }
        my_free_list = free_list + FREELIST_INDEX(n);
        result = *my_free_list;             // 获得对应的链表指针
        if(result == NULL) {                // 如果链表为空
            void *r = refill(ROUND_UP(n));
            return r;
        }
        *my_free_list = result->free_list_link;
        return result;
    }
    static void deallocate(void *p, size_t n) {
        obj *q = (obj*) p;
        obj **my_free_list;                 // obj**
        if(n > (size_t)__MAX_BYTES) {        // 改用第一级p配置器
//          malloc_alloc::deallocate(p, n);
            return ;
        }
        my_free_list = free_list + FREELIST_INDEX(n);
        q->free_list_link = *my_free_list;
        *my_free_list = q;
    }
};
char* alloc::start_free = NULL;
char* alloc::end_free = NULL;
size_t alloc::heap_size = 0;
alloc::obj* alloc::free_list[__NFREELISTS] = {0};