C++内存管理
C++中有四种内存分配、释放方式：
*的是std::allocator，对应的释放方式是std::deallocate，可以*设计来搭配任何容器；new/delete系列是C++函数，可重载；malloc/free属于C++表达式，不可重载；更低级的内存管理函数是操作系统直接提供的系统调用，通常不会到这个层次来写C++应用程序。接下来的阐述集中在上三层。
现在让我们写一些示例：
// c语言中的malloc/free
void *p1 = malloc(512);
*(int*) p1 = 100;
free(p1);
// c++表达式new/delete
int *p2 = new int(100);// 这里应该是初始化为100，若要声明数组，用new int[n];
delete p2;
// c++函数，等价于malloc和free
void *p3 = ::operator new(512);
*(int *)p3 = 100;
::operator delete(p3);
// c++标准库，通过object调用，以GNU为例
int *p4 = alloctor<int>().allocate(7);// 这里是分配7个int单元而不是7bytes
*p4 = 9;
allocator<int>().deallocate((int *)p4,7);// 7应该与上文匹配
new/delete表达式
new表达式的内部实现是由三个步骤组成的，首先调用operator new分配一定的字节数的内存，此时得到的内存指针是void*类型的，将之用static_cast转换成需要的class类型，然后调用class的构造函数完成初始化。
Complex *pc;
try {
void* mem = operator new(sizeof(Complex)); // 分配内存
pc = static_cast<Complex*>(mem); // cast 转型 以符合对应的类型，这里对应为Complex*
pc->Complex::Complex(1,2); // construct
// 注意：只有编译器才可以像上面那样直接呼叫constructor 欲直接调用constructor可通用placement new: new(p) Complex(1,2);
}
catch(std::bad_alloc) {
// 若allocation失败就不执行constructor
}
从上面的new的实现中，不难发现，new返回的是对象指针，失败是抛出bad_alloc异常，我们应该通过是否抛出异常来判断new执行状况，而不是像malloc一样通过判断返回值是否为nullptr。
对于delete，其具体操作与new相反，先调用对象的析构函数，再释放内存。
// delete pc;
pc->~Complex(); //先析构
operator delete(pc); //然后释放内存
array new和array delete可以获取一组对象，new的时候不能同时初始化，因此通常结合placement new来创建对象。
class A{
public:
int id;
A(): id(0){}
A(int i): id(i){}
~A(){}
};
A* buf = new A[size]; // 调用三次默认构造函数A():id(0)
A* tmp = buf;
// placement new指定位置new
for(int i = 0; i<size; i++)
new(tmp++) A(i); //调用A(int i): id(i)自定义初始化
delete []buf; // 调用三次~A()
new array的构造是从0到size-1依次构造，析构的时候恰恰相反（但这不重要）。new array返回的指针指向第0个对象的起始位置。
数组的new必须和数组的delete联合使用，否则可能发生内存泄漏：若只使用delete而非delete []，则只会将分配的size块内存空间释放，但是不会调用对象的析构函数（可能是因为此处将size块对象视为一个对象之后，找不到合适的析构函数），没有析构就释放内存是很不优雅的，如果对象内部还使用了new指向其他空间，那么这部分空间不会被释放。如果new array分配的是一些析构函数没有意义的对象，比如：
int* pi = new int[10];
delete pi;
那么是完全没有问题的，delete等价于delete[]。
附图：声明了3个对象的时候的内存分布，其中cookie保存着数组大小等信息。
new/delete重载
C++ new的调用链是图中的2，operator new将在全局环境下寻找匹配的函数。如果要重构，则最好在此处将其转为调用类内自定义的Foo::operator new，在Foo::operator new中再调用::operator new。已经定义了重载之后，也可以通过直接调用::operator new来绕过重载。重载的原则是，尽量在高层、部分可见的局部进行重载，使影响尽可能小而且可控。绘制函数调用链可以很好地帮助决定重载层次。除了new之外，new array等也可以重载。
类内自定义allocator（per-class allocator）
本节介绍的是一个类内借助内存池的内存管理。虽然malloc不慢，但减少malloc调用次数总是好的；此外，一次malloc得到的内存块前总是带有一个cookie，它占有8个字节。基于以上两个原因，从时间和空间的角度看，建立内存池都是有必要的。
思考：当每次alloc的时候都alloc固定大小的一大块的时候，应该更难以产生外部碎片（虽然可能更容易产生内部碎片），而且固定大小对于OS的高级分配器来说是十分友好的。
这里直接看per-class allocator3。
- embedded pointer和类型转换
- 链表管理的内存池
- 抽象的思想
- if判断将值放在变量前面,这样可以避免少写等号,编译器不报错问题，例如 if(1!=p){} 。
#include <iostream>
#include <complex>
using namespace std;
class my_allocator{
private:
struct obj{
struct obj* next; // embedded pointer
};
obj* freestore = nullptr;
const int CHUNK = 5;
public:
my_allocator(){};
~my_allocator(){};
void* allocate(size_t);
void deallocate(void*, size_t);
};
void* my_allocator::allocate(size_t size){
// 从内存池分配一个obj对象大小的内存
assert(size>0);
obj* p;
if(!freestore){
freestore = p = static_cast<obj*>(malloc(CHUNK*size));
for(int i = 0;i<CHUNK-1;i++){
p->next = (obj*)((char*)(p+size));
p = p->next;
}
p->next = nullptr;
}
p = freestore;
freestore = freestore->next;
return p;
}
void deallocate(void* p, size_t size){
// 插入到内存池
(static_cast<obj*>(p))->next = freestore;
freestore = static_cast<obj*>(p);
}
// example
class Foo{
public:
long L;
string str;
static my_allocator myAlloc;
Foo(long l): L(l){}
static void* operator new(size_t size){
return myAlloc.allocate(size);
}
static void operator delete(void* dead, size_t size){
return myAlloc.deallocate(dead, size);
}
};
my_allocator Foo::myAlloc; // 静态成员变量一定要在类声明之外定义
以下讨论GNU编译器中的内存管理机制。
allocator是普通的分配器，它通过operator new和operator delete调用malloc和free，没有特殊的设计。
G4.9的__pool_alloc（相当于G2.9的std::alloc）是在容器中使用的分配器，是利用上了内存池的分配器。std::alloc使用一个16个写代指针头的数组来管理内存链表，数组的不同元素管理不同大小的区块，每种区块大小相差8个字节。内存首先由malloc分配到战备池pool中，再从战备池挖适当的空间到链表。假设用户需要32字节的内存，std::alloc首先申请一块区间，大小为32*20*2，用一条链表管理，然后让数组的#3指针管理这条链表，接着将其中一个单元（32字节）分给用户。这32*20*2中，一半是给用户的，后一半预留在战备池中，如果此时用户需要一个64字节的空间，那么剩下的一半将变成64*10（通常是申请64*20），由另一个链表指针指向这里，然后将其中64字节分配给用户，而不用再一次构建链表和申请空间。链表数组维护的链表最大块是128字节，如果申请超过了这个大小，那么直接调用malloc给用户分配，这样每一块都会带上cookie头和尾。
- 战备池，池中内存没有固定块大小
- 多级大小内存池链表
- 两级分配器：超过最大大小直接使用malloc分配
G2.9中的一级配置器主要是对malloc和free进行了一些封装，当申请的内存较大的时候，二级分配器将直接调用一级分配器。一级分配器在G4.9中已经弃用。此处不再过多阐述。
二级配置器执行分配器的主要功能。流程图和部分源码如下。
static const int __ALLGN = 8; // 上调边界
static const int __MAX_BYTES = 8; // 分配Chunk的上限
static const int __NFREELISTS = __MAX_BYTES/__ALLGN; // 链表的条数
template<bool threads, int inst>
class __default_alloc_template{
private:
static size_t ROUND_UP(size_t bytes){ // 向上取整8
return (bytes+__ALLGN-1) & ~(__ALLGN-1);
}
union obj{ // 亦可用struct
union obj* free_list_link; // 链表的next指针，老规矩用了ebedded pointer
}
static obj* volatile free_list[__NFREELISTS]; // 多级大小内存池
static size_t FREELIST_INDEX(size_t bytes){ // 根据大小确定链表index
return ((bytes+ALLGN-1)/__ALLGN-1);
}
static void *refill(size_t size);
static char* chunk_alloc(size_t size, int &nobjs);
// 战备池
static char* start_free; // 指向pool的头
static char* end_free; // 指向pool的尾
static size_t heap_size; // 分配累积量
public:
static void* allocate(size_t size){
obj* volatile *my_free_list; // 链表的链表
obj* result;
if(size > (size_t)__MAX_BYTES) // 大于128改用第一级分配器
return (malloc_alloc::allocate(size));
my_free_list = free_list+FREELIST_INDEX(size);
result = *my_free_list;
if(0==result){
void* t = refill(ROUND_UP(size)); // 对此链表充值
return t;
}
*my_free_list = result->free_list_link;
return result;
}
static deallocate(void* p, size_t size){
obj* q = (obj*)p;
obj* volatile* my_free_list;
if(size > static_cast<size_t>(__MAX_BYTES)){
malloc_alloc::deallocate(p,size); // 大于128改用第一级分配器
return;
}
my_free_list = free_list + FREELIST_INDEX(size);
q->free_list_link = *my_free_list;
*my_free_list = q;
}
static void* reallocate(void* p, size_t old_size,size_t new_size);
}
/*
We allocate memory in large chunks inn order to avoid fragmenting the malloc
heap too much, We assume that size is properly aligned.
We hold the allocation lock.
*/
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 bytees_left = end_free - start_free;
if(bytees_left >= total_bytes) { //pool空间足以满足需求
result = start_free;
start_free += total_bytes; // 【Q1：如果pool中的空间不连续还能直接分配和相加吗？A：虚拟地址是连续的】
return(result);
}else if(bytees_left >= size) { //pool空间只满足一块以上
nobjs = bytees_left / size; //改变需求个数
total_bytes = size * nobjs; //改变需求总量 pass-by-value会改变参数
result = start_free;
start_free += total_bytes;
return (result);
}else { //pool空间不足以满足一块需求 碎片&&0
//打算从system free-store上去这么多来充值
size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
//处理碎片(将其挂到相应的chunk指针端口)
if(bytes_to_get > 0) {
obj* volatile *my_free_list = //重新定位碎片的指针
free_list + FREELIST_INDEX(bytees_left);
((obj*)start_free)->free_list_link = *my_free_list;
*my_free_list = (obj*)start_free;
}
//从system free-store中取
start_free = (char*)malloc(bytes_to_get);
if(0 == start_free) { //如果当前的chunk分配失败，则向上继续找相邻的chunk继续分配
obj* volatile *my_free_list, *p;
for(int i = size; i <= __MAX_BYTES; i += __ALLGN) {
my_free_list = free_list + FREELIST_INDEX(i);
p = *my_free_list;
if(0 != p) { //该free-list有可用区块
*my_free_list = p->free_list_link;
start_free = (char*)p;
end_free = start_free + i;
return (chunk_alloc(size, nobjs)); //结果再试一次
}
}
end_free = 0;
start_free = (char*)malloc_alloc::allocate(bytes_to_get);
}
//至此，表示已经从system free-store成功取得很多memory
heap_size += bytes_to_get;
end_free = start_free + bytes_to_get;
return (chunk_alloc(size, nobjs)); //战备池有内存了，所以递归重新处理分配逻辑
}
}
//静态定义(分配内存)
template<bool threads, int inst>
char* __default_alloc_template<threads, inst>::start_free = 0;
template<bool threads, int inst>
char* __default_alloc_template<threads, inst>::end_free = 0;
template<bool threads, int inst>
size_t __default_alloc_template<threads, inst>::heap_size = 0;
template<bool threads, int inst>
__default_alloc_template<threads, inst>::obj* volatile
__default_alloc_template<threads, inst>::free_list[__NFREELISTS] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
//std::alloc为第二级分配器
typedef __default_alloc_template<false, 0> alloc;
int main(void){
std::vector<int,MyAllocator<int>> v;
}
多线程内存分配器
__pool_alloc：For thread-enabled configurations, the pool is locked with a single big lock.
mt_alloc：使用了全局链表，分配到线程时移动到线程专享链表，在此过程中，只对链表的一个bin加锁。exponentially-increasing allocations。
tips:尽量减小锁的粒度。
malloc/free
malloc/free是 libc实现的库函数，主要实现了一套内存管理机制，当其管理的内存不够时，通过brk/mmap等系统调用向内核申请进程的虚拟地址区间，如果其维护的内存能满足malloc调用，则直接返回，free时会将地址块返回空闲链表。
malloc（size） 的时候，这个函数会多分配一块空间，用于保存size变量，free的时候，直接通过指针前移一定大小，就可以获取malloc时保存的size变量，从而free只需要一个指针作为参数就可以了calloc 库函数相当于 malloc + memset(0)
malloc和free碎片化严重（内存站岗），在高并发下性能低下。除了libc自带的动态内存管理库malloc, 有时候还可以使用其他的内存管理库替换，比如使用google实现的tcmalloc ,只需要编译进程时链接上 tcmalloc的静态库并包含响应头文件，就可以透明地使用tcmalloc 了，与libc 的malloc相比， tcmalloc 在内存管理上有很多改进，效率和安全性更好。
brk和mmap
在Linux下，glibc 的malloc提供了下面两种动态内存管理的方法：堆内存分配和mmap的内存分配，此两种分配方法都是通过相应的Linux 系统调用来进行动态内存管理的。具体使用哪一种方式分配，根据glibc的实现，主要取决于所需分配内存的大小。一般情况中，应用层面的内存从进程堆中分配，当进程堆大小不够时，可以通过系统调用brk来改变堆的大小，但是在以下情况，一般由mmap系统调用来实现应用层面的内存分配：A、应用需要分配大于1M的内存，B、在没有连续的内存空间能满足应用所需大小的内存时。
(1)、调用brk实现进程里堆内存分配
在glibc中，当进程所需要的内存较小时，该内存会从进程的堆中分配，但是堆分配出来的内存空间，系统一般不会回收，只有当进程的堆大小到达最大限额时或者没有足够连续大小的空间来为进程继续分配所需内存时，才会回收不用的堆内存。在这种方式下，glibc会为进程堆维护一些固定大小的内存池以减少内存碎片。
(2)、使用mmap的内存分配（堆和栈中间，称为“文件映射区域”的地方）
在glibc中，一般在比较大的内存分配时使用mmap系统调用，它以页为单位来分配内存的（在Linux中，一般一页大小定义为4K），这不可避免会带来内存浪费，但是当进程调用free释放所分配的内存时，glibc会立即调用unmmap，把所分配的内存空间释放回系统。
注意： 这里我们讨论的都是虚拟内存的分配（即应用层面上的内存分配），主要由glibc来实现，它与内核中实际物理内存的分配是不同的层面，进程所分配到的虚拟内存可能没有对应的物理内存。如果所分配的虚拟内存没有对应的物理内存时，操作系统会利用缺页机制来为进程分配实际的物理内存。
默认情况下，malloc函数分配内存，如果请求内存大于128K（可由M_MMAP_THRESHOLD选项调节），那就不是去推_edata指针了，而是利用mmap系统调用，从堆和栈的中间分配一块虚拟内存。
这样子做主要是因为brk分配的内存需要等到高地址内存释放以后才能释放（例如，在B释放之前，A是不可能释放的，因为只有一个_edata 指针，这就是内存碎片产生的原因）（图2紧缩），而mmap分配的内存可以单独释放。
malloc当最高地址空间的空闲内存超过128K（可由M_TRIM_THRESHOLD选项调节）时，执行内存紧缩操作（trim）
缺页中断
- 陷入内核态
- 检查要访问的虚拟地址是否合法
- 查找/分配一个物理页[......]（buddy+slab）
- 填充物理页内容（读取磁盘，或者直接置0，或者什么都不做）
- 建立映射关系（虚拟地址到物理地址的映射关系）
- 重复执行发生缺页中断的那条指令
补充知识
内存泄漏
内存泄露是很隐蔽的错误，通常少量的内存泄露不会造成什么问题，大量的内存泄露可能会有“out of memory（OOM）”错误。
内存泄露的检测通常借助于内存分析工具；（ valgrind 或 purify ）
一般如果是简单的 new 之后，没有 delete，这种泄漏最容易发现。真实场景可能比这复杂得多。有时候定位了相应的函数，但是代码比较复杂，还是找不到泄漏点，可以参考如下几个地方：
map：c++的map，在下标访问的时候自动构造 value 对象，可能造成 map 无限增长；
unordered_set: 在插入大量的元素之后，再删除，内存占用保持不变，需要手动 rehash；
容器的 size 很大：通过 gcore -o xxx pidof yyy，然后 gdb 去查看有嫌疑的容器的长度；
如果容器的 size 正常，但是还是有泄漏，可能跟智能指针有关，例如 shared ptr，被泄漏；
......
malloc/free和new/delete的比较
RAII规则
RAII是指C++语言中的一个惯用法（idiom），它是“Resource Acquisition Is Initialization”的首字母缩写。中文可将其翻译为“资源获取就是初始化”。
需要动态获取和释放的都可以称为“资源”；
获取资源和释放资源要对应，这里就会面临麻烦：释放的不彻底将会导致memory leak，致使程序臃肿、出错等。
看到这里自然而然的可以想到C++中的一对特殊函数，构造函数和析构函数。在构造函数中申请资源，以及在析构函数中释放资源。
类是C++中的主要抽象工具，那么就将资源抽象为类，用局部对象来表示资源，把管理资源的任务转化为管理局部对象的任务。这就是RAII惯用法，RAII有效地实现了C++资源管理的自动化。