memory pool 介绍
C/C++下内存管理是让几乎每一个程序员头疼的问题，分配足够的内存、追踪内存的分配、在不需要的时候释放内存——这个任务相当复杂。而直接使用系统调用malloc/free、new/delete进行内存分配和释放，有以下弊端：
1.调用malloc/new,系统需要根据“最先匹配”、“最优匹配”或其他算法在内存空闲块表中查找一块空闲内存，调用free/delete,系统可能需要合并空闲内存块，这些会产生额外开销;
2.频繁使用时会产生大量内存碎片，从而降低程序运行效率;
3.容易造成内存泄漏;
内存池（memory pool)是代替直接调用malloc/free、new/delete进行内存管理的常用方法，当我们申请内存空间时，首先到我们的内存池中查找合适的内存块，而不是直接向操作系统申请，优势在于：
1.比malloc/free进行内存申请/释放的方式快;
2.不会产生或很少产生堆碎片;
3.可避免内存泄漏;
内存池(memory)作为进程内存的管理方式之一，含有必要弄清楚它的工作原理。内存池的一个简单应用就是c++的二级配置器：
首先我们来看看union obj联合体：
union obj {
union obj *free_list_link;
char client_data[1];
};
在内存池中所有的空闲块都以这样的方式连接起来，我们知道这个联合体的大小为4Byte，书中描述为这样：由于union之故，从其第一字段观之，obj可被视为一个指针，指向相同
形式的另一个obj。从其第二字段观之，obj可被视为一个指针，指向实际区块。也就是说如果我们用下面的方式取出内存池中的可用内存：
// 使用时将其取出，指向下一个区块的free_list_link此时就被我们当做空闲区域来使用了，因而不会额外占用空间
obj *myBlock = free_list;
free_list = free_list->free_list_link;
// 之后直接使用myBlock->client_data来访问该内存区域
也就是说：
printf("%x\n", myblock);
printf("%x\n", myblock->client_data);
它们的地址是一样的，但是为什么要这样呢？在一般情况下，假设我们利用malloc申请了一块内存，那么它返回的是void*的指针，如果我们要使用这块内存，假设我们要让它
存放char型的数据，要进行(char *)myblock的转换。但是这里我们不需要转换，直接使用myblock-client_data进行，就可以以char*类型获得这块内存的首地址！！这这使得
操作更加方便！！！
在内存池中取空闲块：
回收内存块：
第一段源码
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include<iostream>
#include <string>
using namespace std;
template <bool threads, int inst>
class __default_alloc_template {
private:
# ifndef __SUNPRO_CC
enum { __ALIGN = 8 };//最小内存块，其它都是align的倍数，直到128Byte为止
enum { __MAX_BYTES = 128 };
enum { __NFREELISTS = __MAX_BYTES / __ALIGN };//链表大小为16
# endif
static size_t ROUND_UP(size_t bytes) { //将bytes上调至8的整数倍
return (((bytes)+__ALIGN - 1) & ~(__ALIGN - 1));
}
private:
union obj {
union obj * free_list_link;
char client_data[1]; /* The client sees this. */
};
private:
# ifdef __SUNPRO_CC
static obj * __VOLATILE free_list[];
// Specifying a size results in duplicate def for 4.1
# else
//__NFREELISTS值为16，对应链表维护内存大小为8、16、…、128
static obj * __VOLATILE free_list[__NFREELISTS];
# endif
//根据bytes大小，在16个链表中选取合适的那个
static size_t FREELIST_INDEX(size_t bytes) {
return (((bytes)+__ALIGN - 1) / __ALIGN - 1);
}
static void *refill(size_t n);
/*
配置一大块空间，可容纳nobjs个size大小的区块，如果配置
nobjs个区块有所不便，nobjs可能会降低。
*/
static char *chunk_alloc(size_t size, int &nobjs);
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) {//如果配置内存大于__MAX_BYTES，使用第一级配置器
return(malloc_alloc::allocate(n));
}
my_free_list = free_list + FREELIST_INDEX(n);//在16个free lists中找到对应的那个
result = *my_free_list;//将对应第一个空闲块的地址赋值给result
if (result == 0) {//如果没找可用的free list，那么重新填充free list
void *r = refill(ROUND_UP(n));//如果result没有满足，就新建20个这样块
return r;
}
//调整free list
*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);
return;
}
//在16个free lists中找到对应的那个
my_free_list = free_list + FREELIST_INDEX(n);
q->free_list_link = *my_free_list;
*my_free_list = q;
}
static void * reallocate(void *p, size_t old_sz, size_t new_sz);
};
/*
扩展现有内存，重新分配内存，要把旧内存内容拷贝到新内存
*/
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;
//如果就内存和新内存都大于_MAX_BYTES，直接调用realloc
if (old_sz > (size_t)__MAX_BYTES && new_sz > (size_t)__MAX_BYTES) {
return(realloc(p, new_sz));
}
//内存大小没变化（没变化是指经过上调为8的整数倍后没变化），直接返回
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);
}
第二段源码：
template <bool threads, int inst>
void* __default_alloc_template<threads, inst>::refill(size_t n){
int nobjs = 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);
for (i = 1;; i++) {//从1开始，第0个返回给客户端
current_obj = next_obj;
next_obj = (obj *)((char *)next_obj + n);
if (nobjs - 1 == i) {
current_obj->free_list_link = 0;//最后一个块的指针设为NULL
break;
}
else {
current_obj->free_list_link = next_obj;
}
}
return(result);
}
第三段源码(核心)：
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include<iostream>
#include <string>
using namespace std;
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) {//内存池空间满足需求,可以一次分配20个size的大小
result = start_free;
start_free += total_bytes;
return(result);
}
else 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);
//尝试内存池中的参与零头还有利用价值
if (bytes_left > 0) {//
obj * __VOLATILE * my_free_list =//找到对应的free list
free_list + FREELIST_INDEX(bytes_left);
//调整free list，将内存池空间编入
((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) {//如果配置失败，就在free_list其它空闲内存中抽取利用
int i;
obj * __VOLATILE * my_free_list, *p;
/*尝试用现有的，这不会造成破坏。我们不尝试配置较小的区块，因为这样做将会在多线程机器上造成灾难*/
//搜索适当free list，适当是指“尚未用区块，且足够大”的free list
for (i = size; i <= __MAX_BYTES; i += __ALIGN) {
my_free_list = free_list + FREELIST_INDEX(i);
p = *my_free_list;
if (0 != p) {//free内有尚未用区块
//调整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.
//任何参与的零头将会被编入适当地free list中备用
}
}
//如果出现意外，到处无可用内存
end_free = 0; // In case of exception.
//调用第一级配置器，看看out-of-memory机制能否尽点力
start_free = (char *)malloc_alloc::allocate(bytes_to_get);
//这里可能会抛出异常，或内存不足情况得到改善。
}
//到这里表示调用malloc成功
heap_size += bytes_to_get;
end_free = start_free + bytes_to_get;
//递归调用自己，修正nobjs
return(chunk_alloc(size, nobjs));
}
}
最后梳理一下整个内存池在内存分配中的逻辑：
https://blog.csdn.net/caoyan_12727/article/details/52081679