适配器

在视频的案例中说道内存分有两级适配器，一级适配器就是直接用malloc()和free()去分配和回收内存。
而二级适配器是自定义分配(连续)内存,和释放内存。可以减少内存碎片化和提高内存的利用率。

一级适配器

//----------------------------------------------
// 第1級配置器。
//----------------------------------------------void (*oom_handler)() = 0;void* oom_malloc(size_t n)
{void (*my_malloc_handler)();void* result;for (;;) {    //不斷嘗試釋放、配置、再釋放、再配置…my_malloc_handler = oom_handler;if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; }(*my_malloc_handler)();    //呼叫處理常式，企圖釋放記憶體result = malloc(n);        //再次嘗試配置記憶體if (result) return(result);}
}void* oom_realloc(void *p, size_t n)
{void (*my_malloc_handler)();void* result;for (;;) {    //不斷嘗試釋放、配置、再釋放、再配置…my_malloc_handler = oom_handler;if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; }(*my_malloc_handler)();    //呼叫處理常式，企圖釋放記憶體。result = realloc(p, n);    //再次嘗試配置記憶體。if (result) return(result);}
}void* malloc_allocate(size_t n)
{void *result = malloc(n);   //直接使用 malloc()if (0 == result) result = oom_malloc(n);return result;
}void malloc_deallocate(void* p, size_t n)
{free(p);  //直接使用 free()
}void* malloc_reallocate(void *p, size_t old_sz, size_t new_sz)
{void* result = realloc(p, new_sz); //直接使用 realloc()if (0 == result) result = oom_realloc(p, new_sz);return result;
}void (*set_malloc_handler(void (*f)()))()
{ //類似 C++ 的 set_new_handler().void (*old)() = oom_handler;oom_handler = f;return(old);
}

二级适配器

我们将二级适配器拆分成多个部分查看。

常量定义

enum {__ALIGN = 8};                        //小區塊的上調邊界
enum {__MAX_BYTES = 128};                  //小區塊的上限
enum {__NFREELISTS = __MAX_BYTES/__ALIGN}; //free-lists 個數

类的结构

//模板类，第一个参数与线程有关，这里不做讨论
//第二个参数与分配器也没有关系
template<bool thread, int inst> 
class __default_alloc_template
{
private://字节对齐，向上取整static size_t ROUND_UP(size_t bytes);union obj{union *free_list_link;};//embaded pointer，这里也可以用 strut//free_list 数组，每一个位置上挂载不同长度 block 的链表static obj* volatile free_list[__NFREELISTS];//根据字节数，求在 free_list 数组中的编号。//比如说传入 bytes = 20,则对应于 free_list 数组中的 #2 位置，返回2。static size_t FREELIST_INDEX(size_t bytes);//向操作系统索取新的内存块static void* refill(size_t n);static char* chunk_alloc(size_t size, int& nobjs);//指向 memory pool 的开始位置static char* start_free;//指向 memory pool 的结束位置static char* end_free;//总共分配的内存块的字节数static size_t heap_size;public:static void* allocate(size_t n);static void deallocate(void *p, size_t n);
};typedef __default_alloc_template<false, 0> alloc;

• 所有的成员函数和成员变量都是静态的
• std::alloc 就是 __default_alloc_template<false, 0> 的别名

工具函数

template<bool thread, int inst>
size_t __default_alloc_template<thread, inst>::ROUND_UP(size_t bytes)
{return (bytes + __ALIGN - 1) & ~(__ALIGN - 1);
}

template<bool thread, int inst>
size_t __default_alloc_template<thread, inst>::FREELIST_INDEX(size_t bytes) {return (((bytes) + __ALIGN-1)/__ALIGN - 1);
}

• 这个函数就是对 bytes 长度的 block 求取它对应的在 free_list 数组中的位置。结合上面的 ROUND_UP，应该也很好理解。比如说，传入 bytes = 20，那么它对应的就是在 #2 链表上。

allocate函数

分配内存块

template<bool thread, int inst>
void * __default_alloc_template<thread, inst>::allocate(size_t n)
{//当用户需要获得的内存块大小大于最大的 block 大小，即 128 时，//这种内存管理方式就会失效，转而调用另外一个接口，该接口可为用户提供//类似的 new_handler 机制。这里不做过多讨论if (n > (size_t)__MAX_BYTES){return malloc_allocate(n);}// 获得 n 对应的 block 所在链表的头指针的指针obj **my_free_list = free_list + FREELIST_INDEX(n);//头指针obj *result = *my_free_list;//所在链表没有空的 block 可以使用，需要重新分配内存if (result == nullptr){return refill(ROUND_UP(n));}*my_free_list = result->free_list_link;return result;
}

• 在 std::alloc 中其实有两种内存分配方式。当 传入的字节数 n 大于 free_list 数组中的最大 block 数，比如这里的 128，当前的内存分配方式就会失效，就会转而调用一级适配器的内存分配方式这里不做过多讨论。
• 如果 n 对应的链表不为空，证明该链表还有空闲 block 可供使用，直接返回链表头指针即可，并让头指针指向下一个 block 位置。
• 如果链表为空，表明需要为这一条链表重新分配内存，由函数 refill 完成。

deallocate函数

释放内存（虽然说是释放内存，但是没有free()操作，意味着这个应用程序使用过的内存块在该程序关闭之前是不会释放的，在deallocate()中操作一下链表指针就不会造成Memory Leak)

template<bool thread, int inst>
void __default_alloc_template<thread, inst>::deallocate(void * p, size_t n)
{//传入的这一块内存并不是由当前的内存分配机制分配出去的if (n > (size_t)__MAX_BYTES){malloc_deallocate(p, n);return;}// 获得 n 对应的 block 所在链表的头指针的指针obj **my_free_list = free_list + FREELIST_INDEX(n);obj *q = (obj*)p;//插入到所在链表的头节点位置q->free_list_link = *my_free_list;*my_free_list = q;
}

• 先要判断传入的这一块内存是不是由当前的这种内存分配机制分配出去的。也就是判断传入的字节大小是不是不大于最大的 block 大小，即 __MAX_BYTES，如果不是，说明传入的这一块内存是由第一种内存分配方式分配出去的，就转而调用第一种内存分配方式相对应的内存释放函数。
• 其他的动作就很简单的。把传入的内存块插入到对应链表的头节点位置就可以了。

refill函数

• 在 allocate 函数中，如果索要的对应 block 的链表为空，就需要调用 refill 函数，为该 block 所在链表重新分配内存块。看看 refill 函数执行了哪些动作：
  

//传入的已经是对齐之后的字节大小
template<bool thread, int inst>
void * __default_alloc_template<thread, inst>::refill(size_t n)
{//表示链表所能链接的最长长度int nobjs = 20;//获取一块内存 chunk,注意 nobj 是 pass by referencechar *chunk = chunk_alloc(n, nobjs);//返回的内存块只有一个 block 大小，则可以直接作为结果返回//不需要进行后续的链接动作if (nobjs == 1)return chunk;obj **my_free_list = free_list + FREELIST_INDEX(n);//将获得的内存块的头指针直接作为结果返回obj	*result = (obj*)chunk;//把链表挂在数组 free_list 上*my_free_list = (obj*)(chunk + n);obj *next_obj = *my_free_list;obj* current_obj;//将这一块内存链接为 block 链表for (int i = 1; ; ++i){current_obj = next_obj;//链表最后一个if (i == nobjs - 1){current_obj->free_list_link = nullptr;break;}else{next_obj = (obj*)((char*)current_obj + n);current_obj->free_list_link = next_obj;}}return result;
}

• 这里应该将 20 设置为一个 const 常量更好
• 调用了 chunk_alloc 函数，用来获取一块内存。如果这块内存的大小刚好只有一个 block 的大小，就可以直接将这块内存返回，而不需要进行后续的链接动作。注意 nobjs 是以 pass by reference 的方式传递，表明获得的内存块的实际的 block size (<= 20)。
• 将获得的内存块的第一块 block 直接返回给客户，从第二块 block 开始链接，所以代码中从 i = 1 开始。

chunk_alloc函数

template<bool thread, int inst>
char * __default_alloc_template<thread, inst>::chunk_alloc(size_t size, int & nobjs)
{//所需要的内存块大小size_t total_bytes = size * nobjs;//memory pool 剩余的内存块大小size_t bytes_left = end_free - start_free;char* result;//memory pool 足够分配 nobjs 个 size 大小的 blockif (bytes_left >= total_bytes){result = start_free;start_free += total_bytes;return result;}//可以分至少一个 blockelse if (bytes_left >= size){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);//如果存在内存碎片，以该内存碎片大小为 一个 block 大小，插入到对应的链表头节点位置if (bytes_left > 0){//找到内存碎片大小对应的 free_list 中的位置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);//如果说，此时操作系统内存耗尽，无法成功分配 bytes_to_get 大小的内存，//向比 size 大的，最近的链表上索取一个 block ，进行切割if (0 == start_free){obj *p;for (i = size; i <= __MAX_BYTES; i += __ALIGN){obj **my_free_list = free_list + FREELIST_INDEX(i);p = *my_free_list;if (p != nullptr){//相当于切了一块 block 出去了*my_free_list = p->free_list_link;//把切出来的这一块作为 memory poolstart_free = (char*)p;end_free = start_free + i;//再一次调用 chunk_alloc，这个时候，一定可以调用成功，分出一个 size 大小的 blockreturn(chunk_alloc(size, nobjs));}}//右侧的链表也没有空闲 block 可用，此时调用第一种内存分配方式end_free = 0;start_free = (char*)malloc_allocate(bytes_to_get);}heap_size += bytes_to_get;end_free = start_free + bytes_to_get;//递归调用一次， 进入第一个 if 判断条件内return(chunk_alloc(size, nobjs));}
}

• 这个函数里面，包含了向操作系统索取新的内存块，memory pool 的处理，内存碎片的处理，当系统内存耗尽，无法获取新的内存块时的处理这样几个重要的功能，可以结合上一篇 的运行模式分析，比较好懂。

• 为什么在无法申请更多内存块的情况下，不建议向低字节的索引列表去拿空闲内存块呢：例如，我已经申请了9866大小的内存块，该应用上限为10000大小，我在编号为#3（即内存块单位大小为16B）的链表无法再过多申请内存块。只好向#4，#5…靠后的链表去取空闲内存块，而不向#0，#1，#2链表进行竭泽而渔呢？作者是考虑到多线程的情况下，如果其他线程去向低字节的列表拿内存块，将会是一个大灾难。