【侯捷】C++内存管理机制

【侯捷】C++内存管理机制

万丈高楼平地起

源码之前 了无密码

0. Overview 0.1 应具备的基础

• 曾经动态分配并使用 memory
• 曾经使用过 C++ 标准库的容器（containers）

0.2 目标

从平地到万丈高楼，从最基础的C++语言构件到高知名度的内存管理器，彻底了解高高低低的方方面面。

0.3 工具

• Dev-C++ 5.11， with GNU 4.9.2
• Visual C++ 6.0

0.4 网络资源

0.5 书籍

1. 第一讲 primitives

本章讲解基础的用于分配内存和销毁内存的”工具“。

1.1 C++ 应用程序

• C++ 应用程序可以通过多种方式调用内存分配的”工具“（即接口）

1.2 C++ memory primitives

1.3 四个层面的基本用法

对上述的 4 个 primitives 的使用示例：

说明：

void* p3 = ::operator new(512); //底层就是调用的malloc
::operator delete(p3); //底层就是调用的free

之所以用了不同的宏来区分，是因为虽然是标准接口，但在不同的环境下不同的使用方式效率不同。

#ifdef __BORLANDC__
	//此处的allocator()是临时对象，该行执行结束后，对象的生命就结束了
	//分配5个整数，而不是5个字节，因为指定了放的单元类型
    int* p4 = allocator().allocate(5); 
    allocator().deallocate(p4,5);
#endif

较新的GNU版本使用allocator：

1.4 new expression

• new 的 *** 作是：分配内存，调用构造函数；
• ::operator new 是全局的函数，而该函数可以重载，如果它被重载了，那么调用的就是重载的函数；而此处的Complex 类并没有重载 operator new，所以调用的就是全局的::operator new；
• 在函数opeartor new中可以看到，调用了malloc；
• 只有编译器才可以直接调用构造函数；如果程序想直接调用构造函数，可以使用 palcement new 的方式：new(p) Complex(1,2);

1.5 delete expression

• 注意：可以直接调用析构函数；
• operator delete 函数底层就是调用的free；

1.6 Ctor & Dtor 直接调用

编写程序测试是否能直接调用构造函数和析构函数：

• 通过指针调用构造函数：pstr->string::string("jjhou"); 编译会失败；
• 第二段和第三段代码是自定义的类
  • pA->A::A(3); 在VC6中执行会成功，而在GCC中则会执行失败，GCC更加严谨；
  • A::A(5); 在 VC6 中也执行成功，在GCC中执行失败
  • 结论：不能直接调用构造函数

1.7 array new, array delete

• 如果使用的是delete pca;，那么编译器会认为 pca 是一个对象，只会调用一次析构函数；
• cookie记录个数；用malloc就会有cookie;
• Complex类中没有指针，所以其实析构函数是没有什么用的，但是好的编程观念或技巧，就是要统一，使用array new 就要用 array delete;
• string 类中有指针，如果使用了array new，就一定要使用array delete，否则类中的指针所指向的空间不会被销毁，就会造成内存泄漏；

• A类一定要写默认构造函数，因为使用array new 的时候是没有办法设置初值的，调用的就是默认构造函数；
• 使用placement new来设置初值：new (tmp++) A(i); 【注：在 tmp 这个地址放置一个对象】

小结：

• array new 和 array delete 如果不配套写的话可能会造成内存泄漏，泄露的不是数组本身，而是类中的指针所指向的内存；
• 编译器在处理array new 的时候是从上往下，而array delete 则是从下往上；
• 注意 placement new 的用法；

1.8 array size，in memory block

下图是VC6的malloc的内存布局：

• 61h 是cookie，记录内存的大小60h，1 表示这块内存使用了；
• 此处的int 的析构函数是无意义的，不重要的，所以是否使用array delete 都可以；

• 而Demo类，使用array new 的时候，内存中会有一个表示分配的对象个数的数，此处的3；
• delete[] p; 的时候，因为有[]，底层执行free 的时候发现对象个数是 3，于是就调用 3 次析构函数；

1.9 placement new

• placement new 允许我们将object 建构于已经分配的内存中，所以首先需要有一个指针指向已经分配的内存

1.10 C++应用程序，分配内存的途径

1.11 C++容器，分配内存的途径

• 将一个元素放到容器中的时候，容器也要 new 一块空间，来构造出来；

1.12 重载 1.12.1 重载::operator new/::operator delete

• 重载全局的operator new/opeartor delete，即类外重载：

1.12.2 重载operator new/operator delete

• 在类中重载：
  

1.12.3 重载operator new[]/operator delete[]

1.12.4 重载示例

如果这样写：

绕过了重载的函数，强制使用全局版本。

1.12.5 重载 new()/delete()

例子：

• 第⑤个Foo* p5 = new(100) Foo(1)调用的是void* operator new(size_t size, long extra) 这个函数；其调用的是带有参数的构造函数Foo(int)，在该构造函数中抛出了异常，只有在这种情况下（构造函数内抛出异常）对应的operator delete才会被调用；

1.12.6 basic_string 使用 new(extra) 扩充申请量

• 每次创建字符串的时候都多带了一包东西，所以需要extra

1.13 allocator

接下来的几个版本是我们自行开发的小型的内存分配器。

1.13.1 per-class allocator 1.13.1.1 v1版本

第一版本的opeartor new 和 operator delete:

• 这就是个小型的分配器（内存池），但是只针对于这个类；
• 针对的是VC6编译器中的内存块，测试：

1.13.1.2 v2版本：加上了embedded pointer

第二版本的operator new:

• 说明

  union {
      AirplaneRep rep;
      Airplane* next; 
  };
  

  其中Airplane* next; 借用同一个东西的前4个字节当成指针来使用，这种方法叫做“embedded pointer”，所有内存管理都用了这种技巧。

  struct AirplaneRep {
      unsigned long miles; //4字节
      char type;//1字节
  };
  

  为了内存对齐，struct AirplaneRep 的大小为 8 字节。

  for (int i = 1; i < BLOCK_SIZE - 1; i++) 
      newBlock[i].next = &newBlock[i+1]; //next每次移动8个字节
  

第二版本的opeartor delete:

• 将收回来的指针放入单向链表的头；但是没有还给 *** 作系统；
• 写了member operator new/delete的间隔是8，从间隔可以看出，对象都是紧紧相连的，没有耗用掉cookie;
• 而使用global opeartor new/delete的，每个对象的前后都有cookie，所以间隔是 16；

第二版本相比于第一版的优点：使用了union ，用前4个字节当成指针来使用，即“embedded pointer”方法。

但是还是有个小缺点：收回来的指针全部累计起来了，如果能还给 *** 作系统就更好了。

#include 
using namespace std;

class Airplane {
private:
    struct AirplaneRep {
        unsigned long miles;
        char type;
    };
private:
    union {
        AirplaneRep rep;
        Airplane* next;
    };
public:
    unsigned long getMiles() { return rep.miles; }
    char getType() { return rep.type; }
    void set(unsigned long m, char t) {
        rep.miles = m;
        rep.type = t;
    }
public:
    static void* operator new(size_t size);
    static void operator delete(void* deadObject, size_t size);
private:
    static const int BLOCK_SIZE;
    static Airplane* headOfFreeList;
};

Airplane* Airplane::headOfFreeList;
const int Airplane::BLOCK_SIZE = 512;

void* Airplane::operator new(size_t size) {
    //如果大小有误，转交给::opeartor new(). 在继承的时候可能发现大小有误
    if (size != sizeof(Airplane)) 
        return ::operator new(size);

    Airplane* p = headOfFreeList;
    if (p) //若p有效，将list头部下移一个元素
        headOfFreeList = p->next;
    else {
        //free list已空，申请（分配）一大块
        Airplane* newBlock = static_cast(::operator new(BLOCK_SIZE * sizeof(Airplane)));
        
        //将小块串成一个free list，但跳过 #0，因它将被传回作为本次成果
        for (int i = 1; i < BLOCK_SIZE - 1; i++) 
            newBlock[i].next = &newBlock[i + 1];
        newBlock[BLOCK_SIZE - 1].next = 0; //结束list
        p = newBlock;
        headOfFreeList = &newBlock[1];
    }
    return p;
}

//opeartor delete接获一个内存块
//如果大小正确，就把它加到free list前端
void Airplane::operator delete(void* deadObject, size_t size) {
    if (deadObject == 0) return ;
    if (size != sizeof(Airplane)) {
        ::operator delete(deadObject);
        return ;
    }

    Airplane* carcass = static_cast(deadObject);

    carcass->next = headOfFreeList;
    headOfFreeList = carcass;
}

int main() {
    cout << sizeof(Airplane) << endl;
    size_t const N = 100;
    Airplane* p[N];

    for (int i = 0; i < N; ++i) 
        p[i] = new Airplane;
    
    //随机测试object是否正常
    p[1]->set(1000, 'A');
    p[5]->set(2000, 'B');
    p[9]->set(500000, 'C');

    //输出前10个pointers，用于比较其间隔
    for (int i = 0; i < 10; ++i) 
        cout << p[i] << endl;

    for (int i = 0; i < N; ++i) 
        delete p[i];

    return 0;
}
//测试环境非侯捷的测试环境，所以结果有很大区别

1.13.2 static allocator

特点：将内存的动作抽取到单一的class——allocator 中；

• 每次开辟的 5 个元素在内存中都是相邻的，但是这一组元素与另外开辟的 5 个元素不一定是相邻的；

1.13.2.1 static allocator 示例与结果

#include 
using namespace std;

class allocator {
private:
    //单向链表的节点
    struct obj {
        struct obj* next; //embedded pointer
    };

public:
    void* allocate(size_t);
    void deallocate(void*, size_t);
private:
    obj* freeStore = nullptr;
    const int CHUNK = 5;
};

void* allocator::allocate(size_t size) {
    obj* p;

    if (!freeStore) {
        //linked list为空，于是申请一大块
        size_t chunk = CHUNK * size;
        freeStore = p = (obj*)malloc(chunk);

        //将分配得来的一大块当做linked list般，小块小块串接起来
        for (int i = 0; i < (CHUNK - 1); ++i) {
            p->next = (obj*)((char*)p + size);
            p = p->next;
        }
        p->next = nullptr; //last
    }
    p = freeStore;
    freeStore = freeStore->next;
    return p;
}

void allocator::deallocate(void* p, size_t) {
    //将 *p 收回插入 free list前端
    ((obj*)p)->next = freeStore;
    freeStore = (obj*)p;
}

class Foo {
public:
    long L;
    string str;
    static allocator myAlloc;
public:
    Foo(long l): L(l) {  }
    static void* operator new(size_t size) { 
        return myAlloc.allocate(size); 
    }
    static void operator delete(void* phead, size_t size) { 
        return myAlloc.deallocate(phead, size); 
    }
};
allocator Foo::myAlloc;

class Goo {
public:
    complex c;
    string str;
    static allocator myAlloc;
public:
    Goo(const complex& x): c(x) {  }
    static void* operator new(size_t size) {
        return myAlloc.allocate(size);
    }
    static void operator delete(void* phead, size_t size) {
        return myAlloc.deallocate(phead, size);
    }
};
allocator Goo::myAlloc;

int main() {
    Foo* p[100];
    cout << "sizeof(Foo) = " << sizeof(Foo) << endl;
    for (int i = 0; i < 23; ++i) {
        p[i] = new Foo(i);
        cout << p[i] << " " << p[i]->L << endl;
    }

    for (int i = 0; i < 23; ++i) {
        delete p[i];
    }
    
	//============
    
    Goo* p[100];
    cout << "sizeof(Goo) = " << sizeof(Goo) << endl;
    for (int i = 0; i < 17; ++i) {
        p[i] = new Goo(complext(i, i));
        cout << p[i] << " " << p[i]->c << endl;
    }

    for (int i = 0; i < 17; ++i) {
        delete p[i];
    }

    return 0;
}

1.13.2.2 marco for static allocator

因为每个使用allocator 的类的几处写法是固定的，于是将它们写成宏：

示例与结果：

代码：

• 宏

//DECLARE_POOL_ALLOC -- used in class definition
#define DECLARE_POOL_ALLOC()
public:
    void* operator new(size_t size) { return myAlloc.allocate(size); }
    void operator delete(void* p) { myAlloc.deallocate(p, 0); }
protected:
    static allocator myAlloc;

//IMPLEMENT_POOL_ALLOC -- used in class implementation
#define IMPLEMENT_POOL_ALLOC(class_name)
allocator class_name::myAlloc

• Foo

class Foo {
    DECLARE_POOL_ALLOC()
public:
    long L;
    string str;
public:
    Foo(long l): L(l) {  }
};
IMPLEMENT_POOL_ALLOC(Foo)

• Goo

class Goo {
    DECLARE_POOL_ALLOC()
public:
    complex c;
    string str;
public:
    Goo(const complex& x): c(x) {  }
};
IMPLEMENT_POOL_ALLOC(Goo)

1.13.3 global allocator（with multiple free-lists)

是static allocator的进阶版，针对所有的class，而非针对单一的class。不是用static变量的方式使用allocator，而是全局的。

1.13.4 小结

• per-class allocator v1：一般
• per-class allocator v2：加上了embedded pointer
• static allocator：将内存的动作抽取到了单一的class——allocator中
• marco for static allocator：设计一个 marco 宏，简化书写
• global allocator：是static allocator的进阶版，是一个全局的allocator

1.14 new handler

• _callnewh就会调用到由用户指定的handler；
• 如果调用到了用户指定的handler，说明没有内存可用了，就要在这个handler里让更多的内存可用：查看哪些内存可以释放；

例子：

1.15 =default，=delete

• 有默认版本的函数才可以被设置为default，C++中有默认版本的函数

  • 拷贝构造函数

  • 拷贝赋值函数

  • 析构函数

• 验证operator new 和 operator delete 是否也能 default 和 delete：

​ 说明：operator new 和 operator delte 都不能设置为default

2. 第二讲 std::allocator

西北有高楼

上与浮云齐

2.1 VC6 malloc()

• cookie 主要记录当前分配的内存块的大小；
• VC6下cookie 占用的大小是 8 个字节；
• 假设对象很小，但是对象很多，那么就会有大量的cookie，消耗了大量的内存；
• 内存管理的目标：提高效率，精简空间
• 是否有办法将cookie 去除呢？

2.2 不同编译器的标准分配器的实现 2.2.1 VC6 标准分配器之实现

• 调用流程：allocate->_Allocate-> operator new-> malloc
• VC6编译器里面的allocator 并没有做任何内存管理，只是将malloc以allocate 的样子呈现出来；
• VC6的 allocator 只是以 ::operator new 和 ::operator delete 完成 allocate() 和 deallocate() ，没有任何特殊设计；
• VC下的容器的第二个模板参数都是allocator，所以VC6下使用容器，则最终内存分配都是靠malloc 获得的，而malloc 所分配的内存块中带着 cookie；
• 此处的分配是以指定的元素的类型为单位

2.2.2 BC5 标准分配器之实现

• 调用流程：allocate->::operator new-> malloc
• BC5 的 allocator 只是以 ::operator new 和 ::operator delete 完成 allocate() 和 deallocate() ，没有任何特殊设计；
• 容器里使用的分配器就是allocator，即获取到的内存块也是通过malloc分配的，该内存块是带着cookie 的；

我们的目标是要去除cookie，而去除cookie 有个先决条件，内存块的大小一样。

2.2.3 G2.9 标准分配器之实现 2.2.3.1 std::allocator的实现

• 调用流程：allocate-> ::allocate->::operator new->malloc
• G2.9 的 allocator 只是以 ::operator new 和 ::operator delete 完成 allocate() 和 deallocate() ，没有任何特殊设计；
• STL 中使用的不是这个分配器，这个文件并没有被包含到任何的STL头文件中；

2.2.3.2 G2.9 容器使用的分配器，不是 std::allocator 而是 std::alloc

• G2.9 容器使用的分配器是std::alloc；
• alloc 是个类，alloc::allocate说明allocate是alloc这个类的静态函数；
• 分配单位是字节

2.2.3.2 (G2.9) std::alloc vs. (G4.9)__pool_alloc

• 使用方法

  • G2.9版本的std::alloc，写法：

  vector> vec;
  

  • G4.9版本的__pool_alloc，写法：

  vector> vec;
  

• G4.9 标准库中有很多扩充的allocator

2.2.4 G4.9 标准分配器之实现 2.2.4.1 std::allocator的实现

• ”标准分配器“说的就是std::allocator；
• 调用流程：allocate->::operator new->malloc；
• G4.9 的 allocator 只是以 ::operator new 和 ::operator delete 完成 allocate() 和 deallocate()，没有任何特殊设计；

2.2.4.2 pool allocator使用示例

• 使用__pool_alloc去除了 cookie，如果 100 万个元素，去除cookie，就省掉了 800 万个字节，这个数据量很大了；
• 可以看到使用std::allocator的时候，每个元素之间相差10h，即16个字节，元素本身的大小为8字节，因为头尾带了cookie，所以元素之间相距 16 字节，符合我们看到的内存块；
• 某一次使用__gun_cxx::__pool_alloc的结果，指针之间相差不是 08h，并不能推翻分配的内存块不带 cookie 这个结论，因为是进行了 3 次分配，可能分配的内存块并不连续；

#include 
#include 
#include  //mac使用的编译器是clang，找不到这个文件
using namespace std;

template 
void cookie_test(Alloc alloc, size_t n) {
    typename Alloc::value_type *p1, *p2, *p3;

    p1 = alloc.allocate(n);
    p2 = alloc.allocate(n);
    p3 = alloc.allocate(n);

    cout << "p1 = " << p1 << 't' << "p2 = " << p2 << 't' << "p3 = " << p3 << 'n';

    alloc.deallocate(p1, sizeof(typename Alloc::value_type));
    alloc.deallocate(p2, sizeof(typename Alloc::value_type));
    alloc.deallocate(p3, sizeof(typename Alloc::value_type));
}

int main() {
    cout << sizeof(__gnu_cxx::__pool_alloc) << endl; //1，本来应该是0，但是因为一些限制，只能是1
    vector> vecPool;
    cookie_test(__gnu_cxx::__pool_alloc(), 1);


    vector> vec;
    cookie_test(std::allocator(), 1);
    return 0;
}

2.2.5 小结

各种编译器的标准分配器底层都是使用的malloc进行内存分配，分配的内存块是带着cookie 的，G2.9 和 G4.9 存在着比标准分配器更优秀的 extended allocator。

2.3 G2.9 std::alloc 运行模式

G4.9版本和G2.9版本是一样的，只是G4.9的写法更为复杂一些，所以为了方便，看G2.9版本足以。

• G2.9的容器使用的分配器是std::alloc；
• 分配器一定要提供两个重要的函数：
  • allocate （分配）
  • deallocate （回收）
• 16条链表，超过这个链表最大管理的内存块大小范围（128bytes）的内存分配不再受std::alloc管理，而是通过malloc进行分配；
• #0 串联 8 字节的内存块，#1 串联 16 字节的内存块，#2 串联 24 字节的内存块… 链表间的内存块相差 8 字节；
• 如果容器中的每个元素需求的内存块的大小不是8的倍数，比如需要6，则进入std::alloc这个系统后，会被调成8；这个设计在所有的分配器上都一样，malloc也是这样的设计；
• 如果使用容器1，每个元素的大小都是 32 字节，#3 是管理32字节的内存块的，一开始#3 是空的，它就会去挖一块 20 * 32 大小的内存以备使用（20应该是开发std::alloc的人员的经验值）；当这 20块 32字节的内存使用完之后，又会再要 20 * 32 字节大小的内存，以此类推；
• 实际上挖的大小是 20 * 2 * 32字节，而一半拿来切 32 字节的内存块，另一半空置等待使用。若此时使用另一个容器2，每个元素的大小是 64 字节，则需要 #7 链表来管理 64 字节的内存块，当 #7 链表需要的时候，将剩余的 20 * 32 切割成每个内存块 64 字节的大小，可以切出 10 个，可以看到它们 #3 和 #7 的内存块是相连的；至此，分配的内存都使用完了；
• 如果此时再使用一个容器3，每个元素大小为 96，容器向分配器要 96 个字节，这个大小的内存块由 #11 管理，当前 #11 是空的，且没有可以切割的内存，于是向系统要 20 * 2 * 96 字节的内存，同样地，一半用于切割成 20 个 96 字节的内存块，一半空闲以备使用，即图中的start_free ~ end_free这一段内存；
• 容器不再需要元素的时候，要归还内存，根据内存大小就回收到负责该大小的内存块的链表上；
• 如果容器中的每个元素的大小为 256bytes，超出了链表的内存块的范围，则这些内存的分配就不再归std::alloc 管理，而是调用malloc 进行分配，将分配得到的空间传回给容器；
• 容器每次通过动态分配得到指针，容器本身是不知道分配得到的内存是否带cookie；
• std::alloc里管理的内存块都是没有cookie的；当然链表为空时，向系统申请的 20 * 2 * x 字节是通过malloc申请的，

embedded pointers

• 链表借用每个内存块的前 4 个字节，作为一个指针；

• 当将内存块给到客户时，前面的 4 个字节是会被容器中的数据填充的；当内存块被归还的时候，又会将前 4 个字节作为一个指针；

• 所有的有商业价值的、设计好的内存管理一定是使用了embedded pointer；

• 借用4个字节作为embedded pointer在源代码中的设计：

  union obj { //也可以该用struct，就是链表的节点
    union obj* free_list_link;
    char client_data[1]; //没有使用到
  }; 
  

• 对象本身大于等于4bytes才能被借用，如果内存块的size小于4bytes，则不能借用了；虽然工业级存在海量的小区块，但是这些小区块多半都是大于4bytes的，所以多半可以借用；

G2.9 std::alloc 运行一瞥.01

• 定义了 16 个指针，一开始全部为空；

G2.9 std::alloc 运行一瞥.02

• 此处的申请 32 bytes，是应用端使用了容器，容器向分配器申请了 32bytes；
• 分配器的客户是容器，而不是程序员写的程序，如果程序员向直接使用分配器，必须记住申请的内存的大小，归还的时候将大小进行告知。而容器中的元素大小是相同的，容器的第一个模板参数是类型，sizeof(类型) 就可以知道元素的大小；
• RoundUp是个函数，将数字调到16的倍数，该值是个追加量：RoundUp(0>>4) 中的 0 > > 4 0>>4 0>>4 就是0除以16；
• 图中的这一整块是用malloc分配的，所以头尾都有cookie；
• pool 就是依靠 start_free 和 end_free 这两个指针围起来的；

G2.9 std::alloc运行一瞥.03

• 接上页，此时容器申请64bytes，使用上页中的 pool 进行切割；

G2.9 std::alloc运行一瞥.04

• 容器申请 96个字节，#11 链表是空的，而且pool 此时是空的，所以用malloc分配 90 × 20 × 2 + R o u n d U p ( 1280 > > 4 ) 90 times 20 times 2 + RoundUp(1280>>4) 90×20×2+RoundUp(1280>>4) 大小的内存，分配的内存前后都有cookie，注意RoundUp 后面的参数就是 累 计 申 请 量 > > 4 = 累 计 申 请 量   /   16 累计申请量 >> 4 = 累计申请量 / 16 累计申请量>>4=累计申请量 / 16，追加量会越来越大；

G2.9 std::alloc运行一瞥.05

• 在代码中又创建了一个容器，申请88字节，#10号链表管理的内存块大小，此时#10 为空，但是pool 中还有余量，于是从pool 中进行划分；

G2.9 std::alloc运行一瞥.06

• 不在应用端再创建容器，而是某个容器连续三次申请 88，直接从 #10 链表里取出

G2.9 std::alloc运行一瞥.07

• 在客户端又建立一个容器，申请8，#0 为空，但是 pool 中还余 240，由于最多切 20 个，所以 pool 中还剩 240 − 20 × 8 = 80 240 - 20 times 8 = 80 240−20×8=80；

G2.9 std::alloc运行一瞥.08

• 如果不同的容器申请的内存块大小相同，那么它们就会共用同一个链表；
• 此时再创建一个新的容器，申请 104，由 #12 链表管理，此时#12 为空，且 pool 中只有 80，不够；
• 先处理这80bytes的余量，80bytes应该归 list#9 管理，所以将 pool 中的 80 拨给 list #9；
• 然后再通过malloc分配 104 × 20 × 2 + R o u n d U p ( 5200 > > 4 ) 104 times 20 times 2 + RoundUp(5200>>4) 104×20×2+RoundUp(5200>>4) 的内存大小；划分出 20 个 104，将最开头的那个给容器；

G2.9 std::alloc运行一瞥.09

G2.9 std::alloc运行一瞥.10

G2.9 std::alloc运行一瞥.11

• 此处修改了系统源码将系统内存大小设置为了 10000；
• 因为系统内存边界是10000，此次申请的内存大小为 72 × 20 × 2 + R o u n d U p ( 9688 > > 4 ) 72 times 20 times 2 + RoundUp(9688>>4) 72×20×2+RoundUp(9688>>4) ，无法满足，于是找到距离 72bytes 最近的 80bytes，即 list#9管理的内存块，可以发现 list#9 中有一个 80bytes 的内存块，于是将其回填到 pool 中，list #9变为空，再从80bytes这个内存块中切出 72 给客户，剩余 8；

G2.9 std::alloc运行一瞥.12

G2.9 std::alloc运行一瞥.13

• 申请 120，索取 120 ∗ 20 ∗ 2 + R o u n d U p ( 9688 > > 4 ) 120*20*2+RoundUp(9688>>4) 120∗20∗2+RoundUp(9688>>4) 失败，于是找最近接它的list#5看是否有可用的区块，结果发现list#5是空的，越是找不到可用的内存，此次 *** 作失败，申请不到120bytes的区块给客户；

2.4 G2.9 std::alloc 源码剖析 G2.9 std::alloc源码剖析，1

• 之前讲的核心的都在“第二级分配器”中，如果第二级分配器分配失败就会到第一级分配器中再试一次；
• 第一级分配器模拟 new handler，通过一个循环不断地给你机会去分配；
• G4.9中已经没有这个第一级分配了，所以此处跳过这个讲解；

G2.9 std::alloc源码剖析，2

G2.9 std::alloc源码剖析，3

• 到 #74 行，第一级分配器代码完毕；

G2.9 std::alloc源码剖析，4

• 第二级分配器从 #90 行开始；

• ROUND_UP为上调函数，调整为 8 的倍数；

• 嵌入式指针：

  union obj {
      union obj* free_list_link;
  };
  

• 所有的数据和函数都是静态的；

• FREELIST_INDEX 函数计算出申请的内存块应该由第几号链表提供；

• refill 函数就是当链表为空的时候，要进行充值（即申请一大块内存）；

• chunk_alloc 函数申请一大块内存；

G2.9 std::alloc源码剖析，5

• my_free_list变量为指针的指针；
• 当申请的内存的大小大于 128 bytes的时候，就改用第一级分配器；
• 其中my_free_list = free_list + FREELIST_INDEX(n); 表示定位到是第几号链表；
• *my_free_list = result->free_list_link; 表示将第一块内存块给到客户，并向下移动指针；
• 如果result == 0 ，即链表为空，则要申请一大块内存；
• deallocate没有将内存还给 *** 作系统，而是将申请到的内存全部掌握在自己手中，这不是内存泄漏，但是这种做法是有争议的；

G2.9 std::alloc源码剖析，6

• chunk_alloc分配一大块内存；

G2.9 std::alloc源码剖析，7

• G4.9 中start_free是通过operator new进行分配的，所以可以重载operator new接管内存分配，而G2.9中的malloc是不可以进行重载的；

G2.9 std::alloc源码剖析，8

G2.9 std::alloc源码剖析，9

G2.9 std::alloc观念大整理

c.push_back(Foo(1)); //执行完这行，临时对象就是消失了

此处的Foo(1) 是个临时对象，非动态分配的，存在于stack，容器c的内存是通过std::alloc分配的，所以不带cookie;

Foo* p = new Foo(2); 
c.push_back(*p);

• 此处的对象是在heap上建立的，new底层就是通过malloc进行内存分配的，所以分配的内存块是带cookie的（客户端不知道是否带cookie）；

• c.push_back(*p); 容器向分配器发出请求，申请内存，分配器给容器分配它所需要的内存块大小用于存储分配的Foo对象，这个内存块是不带cookie的；

G2.9 std::alloc批斗大会

• 说明：

obj* volatile *my_free_list, *p; //定义的是obj** my_free_list和obj* p这两个变量

if (0 == start_free) //推荐这种写法，因为如果不小心写成=号，编译器会出错，而如果写成start_free = 0，则是会编译通过的，这种Bug找起来就很困难了

• 变量尽量在使用的附近定义，否则中间做了很多其他 *** 作，在使用的时候是不知道的；
• 当要申请一大块内存而系统内存不够时，不进行减半的尝试，因为在多进程的机器上可能会导致大灾难，这个大灾难是针对的其它的进程；
• deallocate()没有调用free() 或delete，源于其设计上的先天缺陷：交给客户的内存块没有指针一直记录着其地址，所以归还的时候不知道地址，就无法回收；

2.5 G4.9 pool allocator运行观察

• list 1st; 默认使用的是标准分配器，底层使用malloc进行分配，分配的每个元素的内存都是带cookie的；
• double占8个字节，而list本身也带两个指针，所以一个元素的大小是16字节；
• 使用标准分配器的时候，总共进行了1000000次malloc分配，每次分配都带着cookie；而使用__pool_alloc只进行了 122 次malloc分配，每次分配也带着cookie；
• 不能观察到malloc真正分配出去的总量（含所有overhead），因为malloc不能重载，除非你有很高的技巧，清楚地理解了malloc的行为模式，理解了它管理的每个区块其实是个链表，链表有个头，知道了链表的头，遍历一遍，就能得到内存块的大小；

2.6 G2.9 std::alloc移植至C

3. 第三讲 malloc/free

胸中自有丘壑

触类旁通

3.1 VC6和VC10的malloc比较

• 左边的图就是core stack，调用栈；
• CRT: C run time，即C的标准库；
• heap_alloc_base函数进行了小区块的阈值判断，小于等于1016使用__sbh_alloc_block函数进行内存分配，否则使用系统函数HeapAlloc进行内存分配；

• 划掉的是VC10中不存在的部分；
• heap_alloc_base函数没有对小区块的阈值判断了，而是统一使用系统函数HeapAlloc进行内存分配；
• VC10中没有SBH相关的 *** 作了；

3.2 SBH之始— _heap_init()和__sbh_heap_init()

• 调用的是win32的API；
• 初始化一大块向CRT要的Heap；
• 分配了 16 个头，即HEADER：

• pHeadData指向内存；
• pRegion指向管理中心；

3.3 VC6内存分配 ioinit函数

• ioinit函数发出了第一次内存分配请求；
• heap_init只是分配 16 个头，头里面（即HEADER) 是什么东西是不清楚的；
• 注意此处的申请 32 ∗ 8 = 256 B y t e s 32 * 8 = 256Bytes 32∗8=256Bytes 大小的内存；

_heap_alloc_dbg函数

• Debug模式下，heap_alloc_dbg函数是在调整内存块的大小，此处的nSize 就是上面提到的 256Bytes;
• 也即是说，在Debug模式下，你需要的大小会被调整得更大一些（如右侧的图所示）；
• 此时还没分配，只是在调整（扩大空间），调整好之后分配就要分配这些东西；
• _CrtMemBlockHeader结构体变量说明：
  • szFileName：记录是文件的哪一行发出来的申请；
  • nDataSize: 对象实际的大小；
  • 1Request: 流水号；

• heap_alloc_dbg函数此时是在调整指针；
• 所有经过malloc分配的内存块都用链表串起来了，即使这块内存块已经给用户了，仍然在它(sbh)的掌控之中，这是在调试模式下；
• 之所以在调试器能追踪内存，因为在调试模式下，多了很多东西，反映到图上就是多了深灰色之外的东西；
• 此处调用了memset给特定位置设置初值，以便观察后续的内存块变化情况；

_heap_alloc_base函数

• 此处的size是经过扩充调整后的大小，将这个大小与阈值进行比较；
• 这个size目前还没加cookie（8bytes），如果加上cookie后这个size小于1024，它就是小区块，而现在还没加cookie，所以此处是小于 1016；

__sbh_alloc_block函数

• intSize 就是之前得到的内存块大小；
• 2 * sizeof(int)就是加 2 个cookie；
• 最后的部分是在做RoundUp，调整到 16 的倍数；
• 也就是说通过malloc分配的内存的实际大小，也是真正消耗掉的内存大小，是：要分配的大小经过调整补充（32bytes，给调试器使用的）再加上cookie，最后调整为16的倍数；
• 图中cookie记录的值是实际内存大小（图中一整块的大小），本来是0x130，但是记录的却是0x131，结尾的 1 表示这块内存已经被占用了，一旦被sbh回收，就会变成 0x130；
• 从ioinit->_malloc_dbg->_nh_malloc_dbg->_heap_alloc_dbg->_heap_alloc_base->__sbh_alloc_block都是在计算内存的大小，还没真正进行内存分配，图中的那些值都还没设置；

__sbh_alloc_new_region函数

• 此处真正进行内存分配；
• 1个HEADER负责管理1MB，通过管理中心进行管理；
• 通过LISTHEAD知道，每个GROUP一共有64条双向链表；
• 总结：1个HEADER将会申请真正的内存1MB，将来要分割出去的时候就从这块内存中进行分割；为了对这块内存切割后的内存块进行管理，又建立了REGION；REGION的大小是16k；

__sbh_alloc_new_group函数

• 从HEADER指向的内存从中分割内存块；
• 32个Group逻辑上对应HEADER指向的内存（虚拟空间），将该内存切分为32个单元，每个单元就是32k；每个单元又细分为8个page，每个page的大小为4k（计算机中通常将4k称为1个page）；sbh设置一些指针，将这些page串起来；

• 这8个page在内存中是连续的；
• 64条链表，管理的最大的区块是1k，那么每条链表负责的任务是什么呢？ 类比于GNU编译器，每条链表负责的是8的倍数的内存大小，这里的最后一条链表负责 1kB，通过计算可得第一条链表负责 16B，第二条链表负责 32B，…；
• 当切割的内存块的大小大于1k的时候，就归最后一条链表管理，小于1k的时候就计算应该归哪条链表管理；

• 这就是从page中切割内存块的 *** 作；
• 图中 0 x 130 0x130 0x130 的就是切割出去的，红色的地址 007 d 0 f f 8 007d0ff8 007d0ff8 是传出去的地址，但是这是在debug模式下，所以这个地址还会继续调整，扣除debug header，只将真正需要的内存地址传出去，这才是使用者真正拿到的地址，这个长度(100h)就是当初使用者申请的大小，这里的使用者就是当初的ioinit；
• 这个page还剩 e c 0 = f f 0 − 130 ec0 = ff0 - 130 ec0=ff0−130，其中 f f 0 ff0 ff0 就是4080；
• 切割只是cookie的调整；
• 展开的切割好的内存块中，前两个数据有错误，此处不是0了，而是对应的两个指针；第三个数据( 0042 e e 08 0042ee08 0042ee08)指向发出内存申请的文件名ioinit.c；第4个数据( 00000081 00000081 00000081)是文件的哪一行发出的内存申请；第5个数据( 0000100 0000100 0000100) 表示使用者真正需要的数据大小；第6个数据( 00000002 00000002 00000002)表示_CRT_BLOCK，表示这一块是给 CRT 用的；
• main执行结束后，可能还有区块，这并不一定是内存泄漏，因为这可能是CRT在使用，查看nBlockUse变量是否为_CRT_BLOCK，那么这就是合理的；
• 在main结束之前的一刻，发现有_NORMAL_BLOCK 的内存块，才说明存在内存泄漏；
• 像130h 这一个区块应该由第 304 / 16 - 1 = 18号链表供应；

3.4 SBH行为分析 分配 首次分配

1. 需求：ioinit.c的 line#81 申请 100h，经过调整区块大小为130h；

2. sbh面对这样的内存申请，在初始化的时候已经有16个HEADER，现在第0个HEADER，先通过VirtualAlloc(0, 1Mb, MEM_RESERVE,...)分配1Mb的空间（从 *** 作系统海量的内存中获得的空间）；

   • 0：表示don’t care，不在意从什么地方分配的空间；

   • 1Mb：表示需要的大小；

   • MEM_RESERVE: 保留，保留这个地址空间，不需要真的有内存在这个地址；

3. 另一个指针通过HeapAlloc 函数从_crtheap中获取到一块大小为sizeof(REGION)的内存空间；REGION中包含的东西在之前已经看过其结构体了，其中还包含了32个Group，每个Group包含64对指针；

4. 从1Mb中通过VirtualAlloc(addr, 32Kb, MEM_COMMIT)真正地划分出32K的内存（此处的MEM_COMMIT表示真的给我，可以想象1Mb的空间里除了32K有内存,其它的都是空的、虚的，没有内存，只有号码），1Mb空间中划分出了32个32K，对应于32个Group；将32K切成更小的单元即8个page，放大了看就是上图中最下面的8个page，这8个page各有两个指针，通过指针将这些page串起来，最后串回到64个链表的最后一个（之所以串回到最后一个链表，是因为每个page的大小为4080，大于1k；64条链表分别管理的区块大小为16B、32B、48B、…，而最后一个链表管理所有1k以上的区块，而目前这些page都是1k以上的，所以全部都归第64条链表管理）；

5. 以上就是为了第一次分配准备的内存；

6. 接下来开始切割，为了应付第一次的内存申请，8个page，从第一个page开始切，图中第二个大图就是page放大后的图，第一个图就是切割后给出去的130h大小的内存的具体内容，其中包含debug header以及无人区，而客户实际得到的地址是指向实际需要的大小100h的地址；在实际需要的内存大小100h的前后都有fdfdfdfd，当用户获得指向100h的地址后，会往下写，可能会写到后面的fdfdfdfd中，而在回收的时候，调试器会检测fdfdfdfd是否被修改，如果被修改了，就会发出警告⚠️，这就是无人区，有隐患存在，是绝对不可以被改的内容；

7. 申请100h，调整后为130h，理应由Group0的#18 list供应，但是现在只有 #63 list链接着内存块，其他链表都是自己链接到自己（为空），当用户发出申请的时候，供应端会将自己的状况告诉用户端 ，REGION中的64bits变量，对应于64条链表，哪条链表有链接着区块，对应的bit就会被设置为1，否则为0；当前的情况只有最后一条链表挂着区块，所以只有最后一个bit是1，其他都是0；每一行bits变量表示一个Group，所以有32行bits变量；

第2次分配

1. 某个申请x字节的内存，经过添加Debug header、cookie，以及调整为16的倍数后需要的内存大小为240h；通过计算得到应该由#35 list供应，接着就去检查Group0的64bit变量中的第35号对应的bit是0还是1，目前只有最后一个bit对应的值为1，其他都是0，也就是说应该供应的#35 list为空，只能退而求其次，找比较大的，目前只有最后一条链表，从之前的page1中剩余的内存中切割；
2. Group结构体中的cntEntries变量，当需要分配的时候+1，回收的时候-1；当值为0的时候，表示8个page可以全部收回来，还给 *** 作系统；
3. 图中Region区域的红色的0表示正在使用Group0；如果Group0的8个page都使用完后，就继续往下使用Group1，…；

第3次分配

1. 申请的70h，在sbh先检查应该由第几号链表供应刚刚好，结果发现其对应的链表的bit是0，于是只好找最靠近的有区块链接的链表，找到了最后一个链表；
2. 从最后一个链表中找到page1，从剩下的内存中划分70h；

第15次分配，释放

1. 并不是每个应用程序都是在第15次，这里只是作为观察选取的一次；
2. 14->13，释放，要先减一；
3. 这次还的是第2次分配的 240h，调用free进行释放，归还到#35 list，挂到35号链表上；回收的方式就是将这块内存的cookie里的241修改成240，就表示进行了回收，相关的数字进行修改（可能会做）；
4. 修改64bit变量中对应的第 36 个bit（表示35号链表）的数字为 1；（00000000 10000001，其中每一位表示4bit）；

1. 需要分配b0h，应该由#10 list供应，但是检查bit位发现第11个bit值为0，就要往比较大的区块进行查找，#35 list有区块，所以应该由 #35 list供应，#35 list刚刚回收了240h的内存，所以从这块内存里切；
2. 240h切出去b0h，还剩 190h，这个内存块变小了，就要进行移动，通过计算 190 h / 10 h − 1 = 24 190h/10h - 1= 24 190h/10h−1=24，应该挂在 #24 list上，所以第 25 个bit应该从0 修改为 1；
3. 这个过程就是第15次的时候刚刚回收了 240h 的内存，第16次分配的时候就要从刚刚回收的内存中进行切割，剩下的内存块（190h） 比较小，就进行移动，对应的bit也要进行调整；

1. 第 n 次分配设计的是Group1的区块不足够，相对应的要划分一块32k的内存，将它划分为8个page，这是一个新的Group，之前的Group1中的32k的使用状态是 02000014 00000000，里面有3个链表挂了区块，有几块不知道；
2. 第 n 次分配需要 230h的内存大小，之前 Group1上的链表挂的区块不能满足这个要求，于是新启动一个Group2（图中的数字变成了1），其他的 *** 作都是一样的；

区块合并

如果回收的内存是相邻的，是不是应该合并呢？好的设计应该是要合并的。

图中空白的区块表示已经回收了的，阴影部分表示可以进行回收的区块。

目前图一中的待回收的内存块前后都是已经回收的300h大小的内存块，这两个内存块都落在#(300h/10h - 1) 这条链表上，要归还目前这个阴影内存块，就要去判断上面和下面是不是都是已经是回收的内存块，这就谈到为什么要有上下cookie。直观地想，cookie是记录整个内存块的大小，应该只需要一个就好了，为什么上下都有一个一模一样的cookie呢？

回收的步骤：

1. 先将待回收的内存块的cookie中的 1 修改为 0；
2. 图中弓箭所在的地方的指针往上4个字节，知道了长度为300h，从这个地址开始加上300h到达了下一块内存的起点，即cookie，能够去检查最后一个bit，发现是0，所以这两块内存可以合并，得到了如图二所示的样子；
3. 因为上下都有cookie，所以从图一的弓箭处的位置往上4个字节，再往上4个字节，就到达了上一个内存块的cookie，知道了上一个内存块的大小，且知道了最后一个bit是0，于是可以继续往上调 300h到达了上一个内存块的上cookie位置，将它们进行合并，就得到了图三的样子；
4. sbh 系统计算 900h 应该链到哪条链表上；

所以，如果没有下cookie的设计，就无法管理上方区块的合并。

free(p)

首先要知道落在哪一个1Mb之中（一个Header对应一个1Mb的内存），在这1Mb中又要知道落在32段的哪一段之中，知道是哪一段就知道了对应于哪一个Group，然后才能去除以16再减一，确定链在哪个链表上。

指针p如何知道是哪个Header？最开始有 16 个Header，__sbh_pHeaderList指向这16个Header，每个Header的大小是固定的。回收的时候知道内存块的大小，通过p+内存块的大小，计算属于哪个Header，如果找不到，则说明当初不是从这里分配出去的，找到属于哪个Header后，将该指针减去这个1Mb的头指针再除以32k，计算得到位于1Mb的哪个段（如果从0算起，还要减1）；

p 花落谁家？

Q：落在哪个 Header 内？

A：每个Header都有指针指向1Mb的内存块，且这个内存块的大小也知道了，于是通过计算头+内存块大小，可以知道 p 是落在哪个Header内了。

Q：落在哪个 Group 内？

A：p 减去 1Mb的头指针，除以32k，就知道落在第几段，也就落在哪个Group内。

Q：落在哪个 free-list 内？（被哪个 free-list 链住？）

A：指针往上看就是cookie，通过cookie知道了内存块的大小，然后除以10h再减去1，就知道落在哪个链表；

分段管理之妙

一段是32k，切成8大块。

1. 如何判断全回收？

如果链表全部变成0就表示全部给出去了，那么如何判断全回收呢？Group中有cntEntries变量，只要这个值变成0，就表示全回收。

2. 不要躁进！

全回收的时候回到了初始的状态（首次分配），8个page不能再进行合并，因为并不急着还给os，方便下一次的分配，等到下一次全回收才会归还给os。只有手上有两个全回收的时候才会归还给系统。

defer是延缓的意思，通过defer来完成不要躁进的目标。图中已经说明了Defer。

恢复到初始状态。图中的8个page是不会合并的。

3.5 VC6,Heap State Reporting Functions

调试模式下才有Debug Header，才可以去追踪，图中的函数就是可以利用的。

3.6 VC malloc + GCC allocator

GCC的allocator的原理和VC 的 malloc 是相似的，allocator中有16条链表，管理的区块最高到128B，每次需要的时候向malloc要内存，allocator中的16条链表的设计不是为了速度快，因为malloc已经很快了，目的是为了去除cookie。

3.7 叠床架屋，有必要吗？

浪费，但是有必要。

CRT(malloc/free) 是 C 的层次，是跨平台的，并不依附于哪个 *** 作系统，所以它并不能预设下面的 *** 作系统有没有做内存管理，同样的道理，C++ Library(std::allocator) 最终要调用到 CRT(malloc/free)，它也不能去预设 malloc 有没有做内存管理，因为它是C++的标准库，不能依赖于底层C的东西。

每个层次都不敢去依赖下面，所以自己来做内存管理。

4. 第四讲 loki::allocator

成竹在胸

4.1 上中下三个classes分析

Loki Library是一个在业界很前沿的库，但是不成熟，作者对这个库的维护只到0.1.7版本。

之前讲过GNU C的编译器不会将内存归还给OS，在多进程的时候会有影响。但是loki会将内存进行归还。

三个class，从下往上就是从底层到上层。

4.2 loki allocator行为图解 Chunk

Chunk::Allocate()

数组代替链表，索引代替指针。

Chunk::Deallocate()

FixedAllocator::Allocate()

其中#line 20中的allocChunk = &*i;，*i得到Chunk，&*i得到了Chunk的首地址；

此处的分配动作中之所以有deallocChunk = &chunks_.front()是因为往vector中添加新的Chunk的时候可能会出现数据的移动，如果出现了数据移动，那之前的iterator就会失效，所以对这些值进行重新设定。

逻辑整理：假设现在有1w个Chunk，有人来申请，先找出被标识的区块，否则从头找起哪个Chunk有区块，否则创建新的Chunk。

FixedAllocator::VicinityFind()

VicinityFind()：临近查找。夹杀法找到地址。

FixedAllocator::DoDeallocate()

Loki allocator检讨

loki 中使用了 vector，而 vector 使用的是标准库的分配器，容器使用 loki 的时候已经和标准库的分配器脱离了关系，所以不存在鸡生蛋和蛋生鸡的问题。所以当你使用loki的时候，其实已经涉及到了标准库的分配器和容器以及loki。

可以自己实现 vector，替代loki中的vector，那么就不会有上面这种问题了。

5. 第五讲 other issues 5.1 GNU C++

5.2 GNU C++对allocators的描述

• 之所以谈到容器，因为分配器就是为容器服务的。

• ::operator new继续往下调用的是malloc。

• __gnu_cxx::new_allocator和__gnu_cxx::malloc_allocator没有什么特殊的设计，没有内存池的设计，这就是最容易满足需求的做法。
• __gnu_cxx::new_allocator相对来说稍微好一些，因为::operator new可重载。

• fixed-size pooling cache固定大小的内存池缓存，就是第二讲中提到的16条链表，每条管理不同大小的内存块，内存块都是8的倍数；
• cache就是之前提到的先准备一大块内存，然后慢慢划分，最大的优势是去除cookie，同时因为减少了malloc 的调用，速度上有一些提升，但这不应该是最大的优势；
• __gnu_cxx::__mt_alloc是多线程的allocator。

• 注意测试分配器的三个指标；

• C++的数组，是静态的，不是动态的，因此避免了"在运行期添乱、增加开销"；
• "甚至在program startup 情况下也可使用"的意思是在进入程序员编写的程序main之前（右侧的core dump）就可以使用__gun_cxx::array_allocator了，也就是说还没有准备好动态分配的时候，就已经有__gun_cxx::array_allocator了。不过在VC6下的startup被写成了一个函数mainCRTStartup()，这个函数里的第一个动作就是_heap_init进行内存管理的初始化，除非是在这个动作之前还要做事情，否则"设置在program startup 情况下也可使用"这句话的意义就不大了，因为内存管理的初始化完成后，其他的分配器也可以使用了；

5.3 VS2013 标准分配器与new_allocator

• 没有做什么额外 *** 作的分配器。

5.4 G4.9 标准分配器与new_allocator

• 标准库中的默认分配器，没有做什么额外 *** 作的分配器。

5.5 G4.9 malloc_allocator

5.6 G4.9 array_allocator

• 第二模板参数不管是使用std::tr1::array 还是std::array都一样，因为本质相同，底部是一个C++的数组；
• C++的数组是静态的，不需要释放，不需要归还，所以array_allocator里面只有allocate() 函数，如果调用deallocate()则是调用的父类的接口，但是这个接口里面do nothing；

• array_allocator> myalloc(&my); 调用构造函数，其中myalloc是对象名称；

其中

typedef ARRAY std::array;
ARRAY* pa = new ARRAY;

这两行代码等同于上一个图中的int my[65536]; 区别在于，int my[65536]; 是静态数组，而这两行是使用动态分配的方式分配的内存；

5.7 G4.9 debug_allocator

• sizeof(size_type)在绝大多数系统中都是4，记录区块的大小；
• _S_extra()函数的结果表示额外的内存相当于几个元素；
• 包裹另一个分配器，让分配的区块还多带extra的空间，用于记录整个区块的大小，扮演的角色类似于cookie；
• 做内存管理的时候，“阳春”型（什么都没做）是没有用的，真正有用的是设计成内存池，设计成内存池的主要用意是去cookie，也提升了一些效率（减少了malloc的调用次数），去除了cookie，又调用debug_allocator，又包装了一层，这样的意义不大；

5.8 G2.9容器使用的分配器不是 std::allocator 而是 std::alloc

• 容器使用的分配器都是std::alloc;

• 特点：只拿内存却不还，不会影响自己，但是可能会影响其他进程；

5.9 G4.9 __pool_alloc 用例

真正有用的分配器是这种智能型的分配器，我们追求的是没有cookie。

5.10 G4.9 bitmap_allocator

• 容器一次都会只要一个元素；

5.10.1 关于blocks，super-blocks，bitmap，mini-vector

• blocks就是客户需要的；
• 一次性申请 64个blocks 用来后续的供应；
• 64个blocks + bitmap + use count = super-blocks；
• bitmap记录了blocks的使用情况，一个bit位表示1个block，1 表示在手中，0表示给出去，当前的状态是全部都在手中；
• use count表示使用了几个block，目前的状态是0个被使用；
• block size 是 8 的倍数，8，16，24… 这样的增长，只允许这样的大小，图中假设每个block的size是8，所以super block size = 524 bytes；
• __mini_vector中的一个元素表示一个super blocks；

• 使用了第1个block；
• bitmap的变化次序和blocks的变化次序相反，blocks从左往右，bitmap从右往左；
• bitmap的最后一个bit变成0；

• 分配了第二个block；
• bitmap的倒数第二个bit变成0；
• use count变成2；

• 使用了63个blocks；
• 只有最后一个block没有使用，所以对应bitmap的第一位为1，其他都为0；

• 将倒数第三个block归还；
• use count变成62；
• 相对应的bit为变成1010；

5.10.2 1st super-block用罄，启动 2nd super-block

• 第二个super-block一共有128个blocks，就需要128个bit，即4个整数（每个整数32位）；
• 第二个super-bloc的第1个block给出去了，所以bitmap[0]的最后1个bit变成了0；
• 标准库中的vector当空间不够的时候会进行 2 倍的增长，此处的_mini_vector就是实现了一个和标准库中的vector相似功能的容器，这里出现了数据的搬动，_M_start此时的值和只有一个元素的时候的_M_start的值是不一样的；

5.10.3 2nd super-block用罄，启动 3rd super-block

• 第三个super-block一共有256个blocks，需要256bit来表示每个block被使用的状态，即 8 个整数；
• 此时_mini_vector需要有第三个单元来控制第三个super-block；
• 因为_mini_vector是成倍增长的，所以此时有4个单元，但是最后一个单元还没被使用；
• 每个super-block只为一种value type服务；
• 图中的蓝色格子，每两格表示一个 entry；

5.10.4 1st super-block 全回收

• 回收的时候使用了另一个_mini_vector，叫做_S_free_list；
• 当前的super-block已经是256blocks，因为回收了1st super block，所以下次再分配的时候，分配规模为 128blocks；
• 回收的vector中只存放64个super-block，如果有第65个super-block回收了，就会归还给O.S；
• 回收了的super-block要将_mini_vector中的这个entry移除，后面的entry元素要往前推；

5.10.5 2nd super-block 全回收

5.10.6 3rd super-block 全回收

5.11 使用G4.9 分配器

• 最精巧的两个分配器：__pool_alloc和bitmap_allocator

• 这是测试程序，列举了每个分配器的使用方式。