c++ 内存管理——从平地到万丈高楼

1. 基础知识 - primitives

1.1 分配内存的四个方面

• 

• 

• 分配内存实例

• GNU2.9版本下

  • 

• GNU4.9版本

  • 

1.2 new 表达式

• 有的书籍会介绍为new operator ，为了避免引起混淆，这里介绍为new expression 。

• new 操作符调用 operator new 函数，该函数有全局静态函数，也可自定义。

• operator new 函数会调用 malloc 函数分配内存。

• new 操作符分三步分配内存，如下图，注意只能编译器这样直接调用对象的构造函数。

  • ①调用operator new 函数，内部调用malloc，分配内存。
  • ②静态转换指针类型。
  • ③调用类的构造函数（只能编译器调用，不能主动调用）

• 

• 要直接调用构造函数而省去分配内存的步骤（内存自己分配），则需要 placement new 函数。

• 参考博客

1.3 delete 表达式

• 分两步进行

  • ①调用析构函数。
  • ②调用delete operator 函数，内部调用free函数，释放内存。

• 

1.4 直接调用构造/析构函数

• 构造函数是不允许直接调用的，析构函数允许。

• 以 string 类为例子。

• 1 2 3 4 5 6 7 8 9 10 11 12 13

  #include <bits/stdc++.h> using namespace std; int main() { string *a = new string; cout << "a = " << *a << endl; // error: 'class std::__cxx11::basic_string<char>' has no member named 'string' // a->string::string("aa"); // 析构函数可以调用 a->~string(); return 0; }

• 以自定义类为例子。

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

  #include <bits/stdc++.h> using namespace std; class A { public: A(int a) { cout << "this ctor " << a << endl; } ~A() { cout << "this dtor" << endl; } }; int main() { A *a = new A(1); // cannot call constructor 'A::A' directly // a->A::A(5); // 析构函数可以直接调用 a->~A(); return 0; } /*输出： this ctor 1 this dtor */

• 

1.5 array new 和 array delete

• 括号配套使用。如果没有，而申请内存的类有指针成员，会造成内存泄漏。

• 

• 以下示例包含了placement new 的用法

  • 前提已经开辟了内存空间
  • 可以手动调用构造函数
  • new(地址)构造函数 ——new(tmp++) A(i)

• 

1.6 分配的内存空间大小（包含Cookie）探索

• 参考文章

• 通过 malloc 分配的内存，会在内存前后加上 cookie，以记录内存分配的总大小。

• 以下的橙色部分是debug环境下的必要信息，浅蓝色部分是为了满足16的倍数的额外空间，上下均有一个cookie，分别为上cookie和下cookie，一个cookie在32位编译器下是4个字节。

• 如果分配对象没有必要的析构函数（trivial dtor），则不会记录分配个数。此时delete不加[] 一般也不会有内存泄漏问题。

• 

• 如果分配对象有重载必要的析构函数（trivial dtor），则会记录分配个数。此时delete不加[] 一定有内存泄漏问题。

• 

• 上面 61h 存储的就是内存块的大小，其中**最低位用于表示是否已分配（1表示已分配，0表示已回收），**其中的 3 记录了分配对象的数量。

• 当申请内存后，返回的指针指向数据开始处（00481c34），而使用 delete[] 释放时，指针会指向00481c30，从而可以根据对象的数量调用相应次数的析构函数。

• 而如果使用 delete 释放的话，它不会去00481c30地址获取对象的长度，而是直接释放00481c34位置处的对象，因此会报错。

1.7 placement new

• 也可以翻译为定点 new 。
• placement new 允许在已分配非内存上我们手动调用构造函数。他并不分配内存。
• 

1.8 对象和容器分配内存的途径

• 对象通过new和delete表达式分配内存。一般自定义的都是成员函数的operator new 函数，来进行重载。

• 

• 容器通过分配器进行内存管理。

• 

1.9 全局 new、delete 函数重载

• 重载格式

• 1 2 3 4 5 6 7

  最一般的形式 void* operator new(size_t sz) ; void operator delete(void* ptr) ; 数组形式: void* operator new[](size_t sz); void operator delete[](void* p) ;

• GCC和MSVC编译器的处理不一样，分开验证。

• GCC不会调用自定义的全局delete函数，而MSVC会调用。

• 

• 示例一

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74

  #include <iostream> using namespace std; void *my_new(size_t sz) { cout << "run my new" << endl; return malloc(sz); } void my_delete(void *ptr) { cout << "run my delete" << endl; return free(ptr); } //重载全局函数 inline void *operator new(size_t size) { cout << "tyc global new()" << endl; return my_new(size); } inline void *operator new[](size_t size) { cout << "tyc global new() []" << endl; return my_new(size); } inline void operator delete(void *ptr) { cout << "tyc global delete()" << endl; my_delete(ptr); } inline void operator delete[](void *ptr) { cout << "tyc global delete() []" << endl; my_delete(ptr); } class person { public: person() { age = 0; sex = 1; cout << "默认构造函数" << endl; } person(int a, int sex) : age(a), sex(sex) { cout << "构造函数" << endl; } ~person() { cout << "析构函数" << endl; } private: int age; int sex; }; int main() { cout << "test p1------" << endl; person *p1 = new person(5, 5); delete p1; cout << "test p2------" << endl; person *p2 = new person[5]; delete[] p2; return 0; }

• MSVC 编译器输出

• 

• GCC 编译器输出

• 

• 示例二

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

  #include <stdio.h> #include <stdlib.h> inline void *operator new(size_t sz) { printf("operator new:%d Bytes\n", sz); void *m = malloc(sz); if (!m) puts("out of memory"); return m; } inline void operator delete(void *m) { puts("operator delete"); free(m); } inline void *operator new[](size_t sz) { printf("operator new[]:%d Bytes\n", sz); void *m = malloc(sz); if (!m) puts("out of memory"); return m; } inline void operator delete[](void *ptr) { puts("operator delete[]"); free(ptr); } class S { int i[100]; public: S() { puts("S:S()"); } ~S() { puts("~S::S()"); } }; int main() { puts("(1)Creating & Destroying an int"); int *p = new int(47); delete p; //------------ puts("(2)Creating & Destroying an S"); S *s = new S; delete s; //------------ puts("(3)Creating & Destroying S[3]"); S *sa = new S[3]; delete[] sa; return 0; }

• MSVC 编译器输出

• 

• GCC 编译器输出

• 

• 总结：从以上两个示例可以看出，GCC 编译器不会调用重载的全局delete和delete[]，但是MSVC编译器会。

• 而且从字节数量看，第二个示例第三个1208，为什么不是1200，是因为多出来8个字节记录分配内存的类的个数，测试机器为64位，即8个字节。

1.10 类内 new、delete 函数重载

• 因为类内的 operator new，调用的时候是在对象创建的时候。因此此时还不存在对象，也不能调用对象的一般成员函数。因此类内的 new、delete 成员函数必然是 static 静态成员函数。

• 但是因为编译器很友好，c++很善良，默认这种成员函数即是static函数，因此即使不在成员函数前面添加static关键词也没什么关系。

• 

• 

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112

  #include <iostream> using namespace std; void *my_new(size_t sz) { cout << "run my new" << endl; return malloc(sz); } void my_delete(void *ptr) { cout << "run my delete" << endl; return free(ptr); } //重载全局函数 inline void *operator new(size_t size) { cout << "tyc global new()" << endl; return my_new(size); } inline void *operator new[](size_t size) { cout << "tyc global new() []" << endl; return my_new(size); } inline void operator delete(void *ptr) { cout << "tyc global delete()" << endl; my_delete(ptr); } inline void operator delete[](void *ptr) { cout << "tyc global delete() []" << endl; my_delete(ptr); } class person { public: person() { age = 0; sex = 1; cout << "默认构造函数" << endl; } person(int a, int sex) : age(a), sex(sex) { cout << "构造函数" << endl; } ~person() { cout << "析构函数" << endl; } static void *operator new(size_t sz); static void *operator new[](size_t sz); static void operator delete(void *ptr); static void operator delete[](void *ptr); private: int age; int sex; }; void *person::operator new(size_t sz) { person *p = (person *)malloc(sz); cout << "类内new" << sz << "字节内存" << endl; return p; } void *person::operator new[](size_t sz) { person *p = (person *)malloc(sz); cout << "类内new [] " << sz << "字节内存" << endl; return p; } void person::operator delete(void *ptr) { cout << "类内删除delete" << endl; free(ptr); return; } void person::operator delete[](void *ptr) { cout << "类内删除delete[]" << endl; free(ptr); return; } int main() { cout << "====调用成员函数的new和delete====" << endl; person *p1 = new person(5, 5); delete p1; cout << "====调用成员函数的new[]和delete[]====" << endl; person *p2 = new person[5]; delete[] p2; cout << "====显式调用全局函数的new和delete====" << endl; person *p3 = ::new person(7, 7); ::delete p3; cout << "====显式调用全局函数的new[]和delete[]====" << endl; person *p4 = ::new person[5]; ::delete[](p4); return 0; }

• 

• 以上是 MSVC 编译器的输出结果，GCC输出结果除了全局delete没有输出外，其他相同。

• 这里着重说明以下为什么是48个字节。

• 一个类的大小为8个字节（两个int类型），因此5个类的总大小为40字节，加上记录类个数的8个字节，即为48个字节。

• GCC 输出结果如下图所示。（采用的是MinGW，其中G++版本为8.1）

• 

• 以下是侯捷老师的示例，以图片展示，四个分配对应的四个输出，很直观。至于Foo一个设计为有虚函数，是为了比较不同大小的类来得出共同点。

• 

• 

• 

1.11 placement new/delete 重载

• 标准的placement new调用方式为

• A* pt = new(address...) A(...) 括号内为已分配内存首地址，栈区和堆区的都可以。

• 

• placement new 的重载函数第一个参数必须是size_t，第二个参数如果是指针就是标准的重载，否则是其他形式的重载。

• 示例一：测试placement new的重载

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

  #include <iostream> using namespace std; class Foo { public: Foo() : _id(0) { cout << "default constructor. id = " << _id << endl; } Foo(int i) : _id(i) { cout << "constructor. id = " << _id << endl; } ~Foo() { cout << "destructor. id = " << _id << endl; } //一般的 operator new 重载 void *operator new(size_t size) { cout << "normal operator new." << endl; return malloc(size); } //按照标准库源码标准的 placement new() 的重载形式 //不需要分配内存，直接返回指针 void *operator new(size_t size, void *start) { cout << "normal placement new" << endl; return start; } //新的 placement new() 重载形式1 void *operator new(size_t size, long extra) { cout << "overloading operator new 1st." << endl; return malloc(size); } //新的 placement new() 重载形式2 void *operator new(size_t size, long extra, char init) { cout << "overloading operator new 2nd." << endl; return malloc(size); } private: int _id; long _data; string _str; }; int main() { //一般的 operator new 重载 cout << "----一般的 operator new 重载------" << endl; Foo *pfs = new Foo(5); delete pfs; //一般的 placement new()，先分配内存，然后构造 Obj cout << "----一般的 placement new 重载------" << endl; char *pt = new char[sizeof(Foo)]; Foo *pf = new (pt) Foo; delete pf; // placement new 重载形式1 cout << "---- placement new 重载1------" << endl; Foo *pf1 = new (1) Foo(10); delete pf1; // placement new 重载形式2 cout << "---- placement new 重载2------" << endl; Foo *pf2 = new (2, 'c') Foo(20); delete pf2; // start的内容都变了，所以析构函数的输出也变了,一般的 placement new() cout << "-----在栈区定点构造对象必须显式析构---------" << endl; char mem[100]; Foo *pf3 = new (mem) Foo(100); pf3->~Foo(); return 0; }

• MSVC 输出结果

• 

• 示例二：说明在栈区内存的 placement new 具体用法。

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

  #include <iostream> using namespace std; class A { public: A() { cout << "A's constructor" << endl; } ~A() { cout << "A's destructor" << endl; } void show() { cout << "num:" << num << endl; } private: int num; }; int main() { char mem[100]; mem[0] = 'A'; mem[1] = '\0'; cout << "预分配的栈区内存地址为 " << (void *)mem << endl; A *p = new (mem) A; cout << "通过 placement new 构造的对象地址为 " << p << endl; p->show(); p->~A(); return 0; }

• 输出结果为

• 

• 从示例二我们可以看出：

  • 1）用定位放置new操作，既可以在栈(stack)上生成对象，也可以在堆（heap）上生成对象。如示例二就是在栈上生成一个对象。
  • 2）使用语句A* p=new (mem) A 定位生成对象时，指针p和数组名mem指向同一片存储区。所以，与其说定位放置new操作是申请空间，还不如说是利用已经请好的空间，真正的申请空间的工作是在此之前完成的。
  • 3）使用语句A *p=new (mem) A 定位生成对象时，会自动调用类A的构造函数，但是由于对象的空间不会自动释放（对象实际上是借用别人的空间），所以必须显示地调用类的析构函数，如本例中的p->~A() 。

• 示例三：侯捷老师关于 placement delete 的重载讲述。

• 我们也可以重载 operator delete ，写出相应的 operator delete 版本。但是，它们绝对不会被 delete 调用，只有当 new 所调用的 constructor函数 抛出 exception 时，才会调用这些重载版本的 operator delete，它们只在这种情况下才会被调用，主要是用来归还未能成功创建 object 的所占用内存，也就是分配内存之后，没有成功创建 object 的那块内存。

• 同样的， placement delete 的重载的第一个参数必须是 void * 。

• 

• 

• 抛出异常后会调用对应的 placement delete 重载。

• 添加其他形参可以方便我们私自开辟多点内存。一个很好的例子就是basic_string，即我们常用的string。因为string这个类需要增加extra的空间描述字符串内容。以下就是重载 placement new 扩充申请量的例子。

• 

1.12 单个 class 的小型内存管理

• 迈向分配器的第一步。

• 内存管理的两个目标

  • 提升速度——降低malloc的调用次数
  • 减少空间——减少cookie的个数

• 一个类的内存管理，减少cookie的数量减少空间，固定一部分内存减少申请内存的时间，即简易版内存池。

• 侯捷老师的示例，从有无重载函数看内存的分配间隔，因为侯老师的实验机器为32位，因此类大小为8字节，cookie大小为4字节，上下一共8字节，所以间隔由原来的8字节变为8+4+4=16字节。

• 

• 

• 可以看到，以上类主要就是调用重载operator new 来进行内存池的创建，内存池的大小为24，超过这个大小的类的new需要重新创建内存池。

• delete的过程描述，可见next指针的变量是在变化的，并没有利用原本的next指针内容。

• 

• 需要说明以下，最后的delete只是把指针转到链表头，而没有把内存释放回操作系统，内存没有泄漏，但本质上这块内存被申请出去了，没有泄露，还在class的手上，但只能class使用。因为存在静态指针。

• 这里采用侯老师的思路进行验证，编译器为GCC，测试机器为64位。

• 重载了operator new 的程序。

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78

  #include <iostream> using namespace std; class Screen { public: Screen(int x) : i(x){}; int get() { return i; } void *operator new(size_t); void operator delete(void *, size_t); private: Screen *next; static Screen *freeStore; static const int screenChunk; private: int i; }; Screen *Screen::freeStore = 0; const int Screen::screenChunk = 24; void *Screen::operator new(size_t size) { Screen *p; if (!freeStore) { // linked list 是空的，所以攫取一大塊 memory //以下呼叫的是 global operator new size_t chunk = screenChunk * size; // 指针转型 freeStore = p = reinterpret_cast<Screen *>(new char[chunk]); //將分配得來的一大塊 memory 當做 linked list 般小塊小塊串接起來 for (; p != (&freeStore[screenChunk - 1]); ++p) p->next = p + 1; p->next = 0; } // p保存为第一个链表，freeStore为下一个链表 p = freeStore; freeStore = freeStore->next; return p; } void Screen::operator delete(void *p, size_t) { //將 deleted object 收回插入 free list 前端 (static_cast<Screen *>(p))->next = freeStore; freeStore = static_cast<Screen *>(p); } //------------- void test_per_class_allocator_1() { cout << "\ntest_per_class_allocator_1() with overload.......... \n"; cout << sizeof(Screen) << endl; // 16 size_t const N = 100; Screen *p[N]; for (int i = 0; i < N; ++i) p[i] = new Screen(i); //輸出前 10 個 pointers, 用以比較其間隔，如果没有cookie大小，说明确实有内存池 for (int i = 0; i < 10; ++i) cout << p[i] << endl; for (int i = 0; i < N; ++i) delete p[i]; } int main() { test_per_class_allocator_1(); return 0; }

• 输出结果为：

• 

• 可以看到，前10个类的内存间隔为16个字节，满足类大小16，从侧面可以反映，两个类的new之间是没有cookie记录的。

• 这里着重说明一下，为什么类的大小为16个字节，按照实际计算，int（4字节）+指针（8字节）=12字节。但是内存对齐，需要满足8的倍数，因此调整为16字节。

• 没有重载 operator new 函数而调用默认全局的new函数的代码

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

  #include <iostream> using namespace std; class Screen { public: Screen(int x) : i(x){}; int get() { return i; } private: Screen *next; static Screen *freeStore; static const int screenChunk; private: int i; }; Screen *Screen::freeStore = 0; const int Screen::screenChunk = 24; //------------- void test_per_class_allocator_1() { cout << "\ntest_per_class_allocator_1() without overload.......... \n"; cout << sizeof(Screen) << endl; // 16 size_t const N = 100; Screen *p[N]; for (int i = 0; i < N; ++i) p[i] = new Screen(i); //輸出前 10 個 pointers, 用以比較其間隔，如果没有cookie大小，说明确实有内存池 for (int i = 0; i < 10; ++i) cout << p[i] << endl; for (int i = 0; i < N; ++i) delete p[i]; } int main() { test_per_class_allocator_1(); return 0; }

• 输出结果为

• 

• 可以看到，每个类之间的间隔为4*16=64字节，出去本身的类大小16，还有48字节，而需要上下cookie，可以猜测一个cookie大小为24字节，也许还有其他的分配，具体存疑。

1.13 单个 class 的小型内存管理——去掉单独的next指针版本

• 1.12 里面的单独的next指针版本多占了内存，这里考虑如何释放这部分内存空间。

• 以下采用union 结构，把next指针和class的data结合在一起，为什么可以这样。

  • 构造对象的时候，只需要next指针
  • 使用对象的时候，next指针没用可变化
  • 析构对象释放内存的时候，可改变next指针回复原始位置。

• 因此，可以把两者联合起来。

• 注意delete的重载是把释放的那部分内存块放到链表的前端，切记这个要点，这也是为什么next可变化的原因所在。

• 

• 

• 个人测试，以下是重载了operator new 的代码。

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127

  #include <iostream> using namespace std; class Airplane { //支援 customized memory management private: struct AirplaneRep { unsigned long miles; char type; }; private: union { AirplaneRep rep; //此針對 used object Airplane *next; //此針對 free list }; 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 = 0; const int Airplane::BLOCK_SIZE = 512; void *Airplane::operator new(size_t size) { //如果大小錯誤，轉交給 ::operator new() if (size != sizeof(Airplane)) return ::operator new(size); Airplane *p = headOfFreeList; //如果 p 有效，就把list頭部移往下一個元素 if (p) headOfFreeList = p->next; else { // free list 已空。配置一塊夠大記憶體， //令足夠容納 BLOCK_SIZE 個 Airplanes Airplane *newBlock = static_cast<Airplane *>(::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; //以null結束 // 將 p 設至頭部，將 headOfFreeList 設至 // 下一個可被運用的小區塊。 p = newBlock; headOfFreeList = &newBlock[1]; } return p; } // operator delete，把内存块添加到链表的最前面 // 如果它的大小正確，就把它加到 free list 的前端 // 因为next是允许变化的，所以可以采用union结构，把next和数据合二为一提高效率 // 开辟内存的时候 next 固定，构造对象后next可变， // delete对象的时候next可变，然后就不变了等待下一次分配 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<Airplane *>(deadObject); carcass->next = headOfFreeList; headOfFreeList = carcass; } //------------- void test_per_class_allocator_2() { cout << "\ntest_per_class_allocator_2().......... \n"; cout << sizeof(Airplane) << endl; // 8 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'); cout << p[1] << ' ' << p[1]->getType() << ' ' << p[1]->getMiles() << endl; cout << p[5] << ' ' << p[5]->getType() << ' ' << p[5]->getMiles() << endl; cout << p[9] << ' ' << p[9]->getType() << ' ' << p[9]->getMiles() << endl; //輸出前 10 個 pointers, 用以比較其間隔 for (int i = 0; i < 10; ++i) cout << p[i] << endl; for (int i = 0; i < N; ++i) delete p[i]; } int main() { test_per_class_allocator_2(); return 0; }

• 输出结果为

• 

• 这里说明为什么是8字节，指针大小8字节，struct大小因为对齐原则也是8字节，因此union取最大值为8字节。可以看到内存间隔为8，满足内存池的设计要求。

• 以下代码是没用重载使用全局函数的示例。

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70

  #include <iostream> using namespace std; class Airplane { //支援 customized memory management private: struct AirplaneRep { unsigned long miles; char type; }; private: union { AirplaneRep rep; //此針對 used object Airplane *next; //此針對 free list }; 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: private: static const int BLOCK_SIZE; static Airplane *headOfFreeList; }; Airplane *Airplane::headOfFreeList = 0; const int Airplane::BLOCK_SIZE = 512; void test_per_class_allocator_2() { cout << "\ntest_per_class_allocator_2().......... \n"; cout << sizeof(Airplane) << endl; // 8 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'); cout << p[1] << ' ' << p[1]->getType() << ' ' << p[1]->getMiles() << endl; cout << p[5] << ' ' << p[5]->getType() << ' ' << p[5]->getMiles() << endl; cout << p[9] << ' ' << p[9]->getType() << ' ' << p[9]->getMiles() << endl; //輸出前 10 個 pointers, 用以比較其間隔 for (int i = 0; i < 10; ++i) cout << p[i] << endl; for (int i = 0; i < N; ++i) delete p[i]; } int main() { test_per_class_allocator_2(); return 0; }

• 输出结果为

• 

• 可以看到，除前3个内存块，后面的内存间隔都是64字节，除了8字节本身，需要56字节的cookie，造成很多的空间浪费。

1.14 单个 class 的小型内存管理——分配器 allocator 初版

• 

• 

• 可以看到，对于其他类，我们仅需要重写以上黄色部分的代码即可。

• 

• 在64位机器上的实验代码如下。

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163

  #include <iostream> #include <complex> using namespace std; //必须在命名空间内，才不会和std冲突 namespace tycMemo { class allocator { private: struct obj { struct obj *next; // embedded pointer }; public: void *allocate(size_t); void deallocate(void *, size_t); void check(); private: obj *freeStore = nullptr; const int CHUNK = 5; //小一點方便觀察 }; void *allocator::allocate(size_t size) { obj *p; if (!freeStore) { // linked list 是空的，所以攫取一大塊 memory size_t chunk = CHUNK * size; freeStore = p = (obj *)malloc(chunk); // cout << "empty. malloc: " << chunk << " " << p << endl; //將分配得來的一大塊當做 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; // cout << "p= " << p << " freeStore= " << freeStore << endl; return p; } void allocator::deallocate(void *p, size_t) { //將 deleted object 收回插入 free list 前端 ((obj *)p)->next = freeStore; freeStore = (obj *)p; } void allocator::check() { obj *p = freeStore; int count = 0; while (p) { cout << p << endl; p = p->next; count++; } cout << count << endl; } //-------------- class Foo { public: //因为要内存对齐，对齐系数为8，因此总类的大小为40字节。 string str; // 32字节 long L; // 4字节 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 *pdead, size_t size) { return myAlloc.deallocate(pdead, size); } }; allocator Foo::myAlloc; class Goo { public: complex<double> c; // 16 string str; // 32 static allocator myAlloc; public: Goo(const complex<double> &x) : c(x) {} static void *operator new(size_t size) { return myAlloc.allocate(size); } static void operator delete(void *pdead, size_t size) { return myAlloc.deallocate(pdead, size); } }; // 静态成员对象初始化 allocator Goo::myAlloc; //------------- void test_static_allocator_3() { cout << "\n\n\ntest_static_allocator().......... \n"; { Foo *p[100]; cout << "sizeof(Foo)= " << sizeof(Foo) << endl; for (int i = 0; i < 9; ++i) { // 23,任意數, 隨意看看結果 p[i] = new Foo(i); cout << p[i] << ' ' << p[i]->L << endl; } // Foo::myAlloc.check(); for (int i = 0; i < 9; ++i) { delete p[i]; } // Foo::myAlloc.check(); } cout << endl; { Goo *p[100]; cout << "sizeof(Goo)= " << sizeof(Goo) << endl; for (int i = 0; i < 9; ++i) { // 17,任意數, 隨意看看結果 p[i] = new Goo(complex<double>(i, i)); cout << p[i] << ' ' << p[i]->c << endl; } // Goo::myAlloc.check(); for (int i = 0; i < 9; ++i) { delete p[i]; } // Goo::myAlloc.check(); } } } int main() { tycMemo::test_static_allocator_3(); return 0; }

• 此处说明string类型的内存大小。

• 

• 

• 从输出结果可以看到，前5个内存分配连续，然后5-6内存不连续，满足分配器的要求。

1.15 单个 class 的小型内存管理——分配器 allocator 宏定义版本

• 使用宏定义 macro 可以使得代码更加简洁

• 

• 

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149

  #include <iostream> #include <complex> using namespace std; //必须在命名空间内，才不会和std冲突 namespace tycMemo { class allocator { private: struct obj { struct obj *next; // embedded pointer }; public: void *allocate(size_t); void deallocate(void *, size_t); void check(); private: obj *freeStore = nullptr; const int CHUNK = 5; //小一點方便觀察 }; void *allocator::allocate(size_t size) { obj *p; if (!freeStore) { // linked list 是空的，所以攫取一大塊 memory size_t chunk = CHUNK * size; freeStore = p = (obj *)malloc(chunk); // cout << "empty. malloc: " << chunk << " " << p << endl; //將分配得來的一大塊當做 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; // cout << "p= " << p << " freeStore= " << freeStore << endl; return p; } void allocator::deallocate(void *p, size_t) { //將 deleted object 收回插入 free list 前端 ((obj *)p)->next = freeStore; freeStore = (obj *)p; } void allocator::check() { obj *p = freeStore; int count = 0; while (p) { cout << p << endl; p = p->next; count++; } cout << count << endl; } } namespace tyc_macro { using tycMemo::allocator; // 借鉴 MFC macros. 进行宏定义，反斜杠表示换行 // 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 file #define IMPLEMENT_POOL_ALLOC(class_name) \ allocator class_name::myAlloc; // in class definition file class Foo { DECLARE_POOL_ALLOC() public: long L; string str; public: Foo(long l) : L(l) {} }; // in class implementation file IMPLEMENT_POOL_ALLOC(Foo) // in class definition file class Goo { DECLARE_POOL_ALLOC() public: complex<double> c; string str; public: Goo(const complex<double> &x) : c(x) {} }; // in class implementation file IMPLEMENT_POOL_ALLOC(Goo) void test_macros_for_static_allocator() { cout << "\n\n\ntest_macro_for_static_allocator().......... \n"; Foo *pF[100]; Goo *pG[100]; cout << "sizeof(Foo)= " << sizeof(Foo) << endl; cout << "sizeof(Goo)= " << sizeof(Goo) << endl; for (int i = 0; i < 23; ++i) { // 23,任意數, 隨意看看結果 pF[i] = new Foo(i); pG[i] = new Goo(complex<double>(i, i)); cout << pF[i] << ' ' << pF[i]->L << "\t"; cout << pG[i] << ' ' << pG[i]->c << "\n"; } for (int i = 0; i < 23; ++i) { delete pF[i]; delete pG[i]; } } } // namespace int main() { tyc_macro::test_macros_for_static_allocator(); return 0; }

• 输出结果为

• 

• 可见也是可以输出正确结果。

• 以上的allocator针对的是一个类，即per-class allocator ，一个类有一个allocator。

• 但是技术是不断发展的，G2.9的allocator是一个全局的分配器，可以适配16个类的分配。

• 

1.16 new handler

• 

• 

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

  #include <iostream> #include <cassert> //assert using namespace std; void noMoreMemory() { cerr << "out of memory"; abort(); } void test_set_new_handler() { cout << "\n\n\ntest_set_new_handler().......... \n"; // 输入的是函数指针 set_new_handler(noMoreMemory); int *p = new int[100000000000000]; // well, so BIG! assert(p); cout << "get more for test" << endl; p = new int[100000000000000000]; //[Warning] integer constant is too large for its type assert(p); } int main() { test_set_new_handler(); return 0; }

• 输出结果

• 

1.17 default 和 delete 关键词

• c++ 11 新增加的。

• 顾名思义，default表示使用这个函数的默认版本

  • 类里面编译器提供默认函数的只有 默认构造函数 ;拷贝构造函数 ; 拷贝赋值函数 ; 析构函数

• delete 表示不要这个函数。

• 

• 

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

  #include <iostream> using namespace std; class Foo { public: long _x; public: Foo(long x = 0) : _x(x) {} //! static void* operator new(size_t size) = default; //[Error] cannot be defaulted //! static void operator delete(void* pdead, size_t size) = default; //[Error] cannot be defaulted static void *operator new[](size_t size) = delete; static void operator delete[](void *pdead, size_t size) = delete; }; class Goo { public: long _x; public: Goo(long x = 0) : _x(x) {} static void *operator new(size_t size) = delete; static void operator delete(void *pdead, size_t size) = delete; }; void test_delete_and_default_for_new() { cout << "test_delete_and_default_for_new().......... \n"; Foo *p1 = new Foo(5); delete p1; //! Foo* pF = new Foo[10]; //[Error] use of deleted function 'static void* Foo::operator new [](size_t)' //! delete [] pF; //[Error] use of deleted function 'static void Foo::operator delete [](void*, size_t)' //! Goo* p2 = new Goo(7); //[Error] use of deleted function 'static void* Goo::operator new(size_t)' //! delete p2; //[Error] use of deleted function 'static void Goo::operator delete(void*, size_t)' Goo *pG = new Goo[10]; delete[] pG; } int main() { test_delete_and_default_for_new(); return 0; }

2. 关于 std::allocator

2.1 概述

• VC6的内存布局（32位机器，VC6）

• 

• VC6 标准分配器是实现——没有任何的特殊设计

• 

• BC5 标准分配器的实现——没有任何的特殊设计

• 

• G2.9版本的标准分配器的实现——没有任何的特殊设计

• 

• 但是这个标准分配器并没有被实际的容器所采用，而是采用std::alloc 。

• 

2.2 G4.9 设计的分配器

• __pool_alloc 采用的是类似G2.9 的std::alloc 的内存池设计。

• 

• 

• 尽管G4.9仍存在类似G2.9的内存池的分配器设计，但实际上的标准分配器采用回了VC6的老路。即默认是没有任何特殊设计的分配器，如果你要使用内存池的分配器，你要显式说明使用分配器的类型。

• 

• 

• 测试示例，在64位机器上，gcc版本为8.1

• gcc version 8.1.0 (x86_64-win32-seh-rev0, Built by MinGW-W64 project)

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

  #include <iostream> #include <memory> //內含 std::allocator #include <ext\pool_allocator.h> //欲使用 std::allocator 以外的 allocator, 就得自行 #include <ext/...> #include <ext\new_allocator.h> //這其實已被 <memory> included, 它就是 std:allocator 的 base class using namespace std; template <typename Alloc> void cookie_test(Alloc alloc, size_t n) { typename Alloc::value_type *p1, *p2, *p3; //需有 typename p1 = alloc.allocate(n); // allocate() and deallocate() 是 non-static, 需以 object 呼叫之. 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)); //需有 typename alloc.deallocate(p2, sizeof(typename Alloc::value_type)); //有些 allocator 對於 2nd argument 的值無所謂 alloc.deallocate(p3, sizeof(typename Alloc::value_type)); } void test_GNU_allocators() { //測試 cookie cout << "sizeof(int)=" << sizeof(int) << endl; // 4 cout << "sizeof(double)=" << sizeof(double) << endl; // 8 cout << "std::allocator<int>() test:----" << endl; cookie_test(std::allocator<int>(), 1); //相距 40h (表示帶 cookie) cout << "__gnu_cxx::__pool_alloc<int>() test:----" << endl; cookie_test(__gnu_cxx::__pool_alloc<int>(), 1); //相距 08h (表示不帶 cookie) //以下將 int 改為 double 結果不變，意味上述 ints 間隔 8 (而非 4) 乃是因為 alignment 内存对齐. cout << "std::allocator<double>() test:----" << endl; cookie_test(std::allocator<double>(), 1); //相距 40h (表示帶 cookie) cout << "__gnu_cxx::__pool_alloc<double>() test:----" << endl; cookie_test(__gnu_cxx::__pool_alloc<double>(), 1); //相距 08h (表示不帶 cookie) } int main() { test_GNU_allocators(); return 0; }

• 

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

• 如下图所示，假设分为三步骤进行内存分配。std::alloc 分为16级，每级链表分配内存大小为8字节，依次就是8 16 24 ... 8*16。
• 以下步骤依次调用三个容器进行演示。
• （1）首先分配20块，每块大小为32字节的内存，可以看到，应从#3处负责分配。分配的时候分配32*40内存的大小，其中剩余的20块内存空间作为战备空间，留待下次使用（不分块）。
• （2）然后分配10块64字节大小的内存空间，这里从剩下的战备空间进行分配，刚好分完。
• （3）接着分配20块96字节大小的内存空间，因为没有战备空间了，这里重新malloc，同样的需要多一部分相同空间的战备空间待用，就想下图的蓝色区域。
• 

2.4 关于嵌入式指针（embedded pointer)

• 即指向自己本身obj *的指针。

• 嵌入式指针工作原理：借用A对象所占用的内存空间中的前4个字节，这4个字节用来链住指向这些空闲的内存块；但是，一旦某一块内存被分配出去，那么这个块的前4个字节 就不再需要，此时这4个字节可以被正常使用。内存回收的时候再重新定义指针地址。

• 简单理解，就是，把内存块的指针和类的数据内容相互嵌套。

• 在32位机器上，指针大小为4字节，因此分配的类对象A大小也只要也要4字节或以上，不然会造成数据混淆，指针报错。

• 而在64位机器上，类A大小就需要在8字节或以上。

• 

2.5 G2.9 std::alloc 运行小测

• 值得注意的是，要单独使用分配器，你需要记住自己借了多少内存，然后最后才还多少内存。这对于程序员是不可忍受的，因此分配器一般不会手动调用，而是由容器进行调用。

• std::alloc 有16条自由链表freelist进行内存管理。

• 

• 

• 

• 

• 

• 

• 

• 当pool连一个内存块都分配不了时：

• 

• 

• 

• 

• 

• 

• 

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

• 以下是第一级配置器代码，不必深究

• 

• 

• 

• 以下是第二级配置器的源码，内存池的思想。

• 

• 

• 

• 

• 

• 

• 

• 

• 示例代码

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405

  #include <iostream> #include <memory> //內含 std::allocator #include <ext\pool_allocator.h> //欲使用 std::allocator 以外的 allocator, 就得自行 #include <ext/...> #include <ext\new_allocator.h> //這其實已被 <memory> included, 它就是 std:allocator 的 base class using namespace std; //---------------------------------------------------- namespace tyc_alloc { //本處完全模仿 SGI STL, G2.92 的 std::alloc //放在 namespace 中因此和 std 不衝突 //此手法和 G4.92 ext\__pool_alloc.h 也完全相同. #define __THROW_BAD_ALLOC \ cerr << "out of memory" << endl; \ exit(1) //---------------------------------------------- // 第1級配置器。无法使用链表的就用这里的malloc开辟内存 //---------------------------------------------- template <int inst> class __malloc_alloc_template { private: static void *oom_malloc(size_t); static void *oom_realloc(void *, size_t); static void (*__malloc_alloc_oom_handler)(); public: static void *allocate(size_t n) { void *result = malloc(n); //直接使用 malloc() if (0 == result) result = oom_malloc(n); return result; } static void deallocate(void *p, size_t /* n */) { free(p); //直接使用 free() } static void *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; } static void (*set_malloc_handler(void (*f)()))() { //類似 C++ 的 set_new_handler(). void (*old)() = __malloc_alloc_oom_handler; __malloc_alloc_oom_handler = f; return (old); } }; //---------------------------------------------- template <int inst> void (*__malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0; template <int inst> void *__malloc_alloc_template<inst>::oom_malloc(size_t n) { void (*my_malloc_handler)(); void *result; for (;;) { //不斷嘗試釋放、配置、再釋放、再配置… my_malloc_handler = __malloc_alloc_oom_handler; if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; } (*my_malloc_handler)(); //呼叫處理常式，企圖釋放記憶體 result = malloc(n); //再次嘗試配置記憶體 if (result) return (result); } } template <int inst> void *__malloc_alloc_template<inst>::oom_realloc(void *p, size_t n) { void (*my_malloc_handler)(); void *result; for (;;) { //不斷嘗試釋放、配置、再釋放、再配置… my_malloc_handler = __malloc_alloc_oom_handler; if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; } (*my_malloc_handler)(); //呼叫處理常式，企圖釋放記憶體。 result = realloc(p, n); //再次嘗試配置記憶體。 if (result) return (result); } } //---------------------------------------------- typedef __malloc_alloc_template<0> malloc_alloc; template <class T, class Alloc> class simple_alloc { public: static T *allocate(size_t n) { return 0 == n ? 0 : (T *)Alloc::allocate(n * sizeof(T)); } static T *allocate(void) { return (T *)Alloc::allocate(sizeof(T)); } static void deallocate(T *p, size_t n) { if (0 != n) Alloc::deallocate(p, n * sizeof(T)); } static void deallocate(T *p) { Alloc::deallocate(p, sizeof(T)); } }; //---------------------------------------------- //第二級配置器 //---------------------------------------------- enum { __ALIGN = 8 }; //小區塊的上調邊界 enum { __MAX_BYTES = 128 }; //小區塊的上限 enum { __NFREELISTS = __MAX_BYTES / __ALIGN }; // free-lists 個數 //本例中兩個 template 參數完全沒有派上用場 template <bool threads, int inst> class __default_alloc_template { private: // 實際上應使用 static const int x = N // 取代 enum { x = N }, 但目前支援該性質的編譯器不多 // 把bytes转为8的倍数 static size_t ROUND_UP(size_t bytes) { return (((bytes) + __ALIGN - 1) & ~(__ALIGN - 1)); } private: union obj { union obj *free_list_link; //嵌入式指针 }; private: static obj *volatile free_list[__NFREELISTS]; //确定第几号#链表 static size_t FREELIST_INDEX(size_t bytes) { return (((bytes) + __ALIGN - 1) / __ALIGN - 1); } // Returns an object of size n, and optionally adds to size n free list. static void *refill(size_t n); // Allocates a chunk for nobjs of size "size". nobjs may be reduced // if it is inconvenient to allocate the requested number. static char *chunk_alloc(size_t size, int &nobjs); // Chunk allocation state. static char *start_free; static char *end_free; static size_t heap_size; public: // n输入为字节数 static void *allocate(size_t n) // n must be > 0 { obj *volatile *my_free_list; // obj** my_free_list; obj *result; if (n > (size_t)__MAX_BYTES) { return (malloc_alloc::allocate(n)); } my_free_list = free_list + FREELIST_INDEX(n); result = *my_free_list; if (result == 0) { 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) // p may not be 0 { obj *q = (obj *)p; obj *volatile *my_free_list; // obj** my_free_list; if (n > (size_t)__MAX_BYTES) { 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; } static void *reallocate(void *p, size_t old_sz, size_t new_sz); }; //---------------------------------------------- // We allocate memory in large chunks in order to // avoid fragmentingthe 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 bytes_left = end_free - start_free; if (bytes_left >= total_bytes) { 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); // Try to make use of the left-over piece. if (bytes_left > 0) { obj *volatile *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); if (0 == start_free) { int i; obj *volatile *my_free_list, *p; // Try to make do with what we have. That can't // hurt. We do not try smaller requests, since that tends // to result in disaster on multi-process machines. for (i = size; i <= __MAX_BYTES; i += __ALIGN) { my_free_list = free_list + FREELIST_INDEX(i); p = *my_free_list; if (0 != p) { // 每次就分配一个pool，直接就return了 *my_free_list = p->free_list_link; start_free = (char *)p; end_free = start_free + i; return (chunk_alloc(size, nobjs)); // Any leftover piece will eventually make it to the // right free list. } } end_free = 0; // In case of exception. // 这里就是山穷水尽，没有任何内存可分配了，抛出异常 start_free = (char *)malloc_alloc::allocate(bytes_to_get); // This should either throw an exception or // remedy the situation. Thus we assume it // succeeded. } heap_size += bytes_to_get; end_free = start_free + bytes_to_get; return (chunk_alloc(size, nobjs)); } } //---------------------------------------------- // Returns an object of size n, and optionally adds // to size n free list.We assume that n is properly aligned. // We hold the allocation lock. //---------------------------------------------- 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** my_free_list; obj *result; obj *current_obj; obj *next_obj; int i; if (1 == nobjs) return (chunk); my_free_list = free_list + FREELIST_INDEX(n); // Build free list in chunk result = (obj *)chunk; *my_free_list = next_obj = (obj *)(chunk + n); for (i = 1;; ++i) { current_obj = next_obj; next_obj = (obj *)((char *)next_obj + n); if (nobjs - 1 == i) { current_obj->free_list_link = 0; break; } else { current_obj->free_list_link = next_obj; } } return (result); } //---------------------------------------------- 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> typename __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, }; //---------------------------------------------- //令第2級配置器的名稱為 alloc typedef __default_alloc_template<false, 0> alloc; //********************************** void test_G29_alloc() { cout << "\ntest_global_allocator_with_16_freelist().......... \n"; // 输入的是字节数 void *p1 = alloc::allocate(120); void *p2 = alloc::allocate(72); void *p3 = alloc::allocate(60); //不是 8 倍數 void *p4 = alloc::allocate(60); //不是 8 倍數 cout << p1 << ' ' << p2 << ' ' << p3 << ' ' << p4 << endl; alloc::deallocate(p1, 120); alloc::deallocate(p2, 72); alloc::deallocate(p3, 60); //以上, 不能搭配容器來測試, 因為新版 G++ 對於 allocator 有更多要求 (詢問更多 typedef 而 alloc 都無法回答) //它其實就是 G4.9 __pool_alloc，所以讓 G4.9容器使用 __pool_alloc 也就等同於這裡所要的測試 /* vector<int, simple_alloc<int,alloc>> v; for(int i=0; i< 1000; ++i) v.push_back(i); for(int i=700; i< 720; ++i) cout << v[i] << ' '; */ cout << endl; } } // namespace int main() { tyc_alloc::test_G29_alloc(); return 0; }

• 输出结果为

• 

• 可以看到：

  • 2400刚好就是120*20；
  • 1440刚好就是72*20；
  • 因为60字节不满足8的倍数，因此向上取整为64字节间隔。

• 值得说明以下，指针大小都是8字节（64位机器），但是指针++的大小是不一样的。这里以int * 和 char * 为例子。

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

  #include <iostream> using namespace std; int main() { //指针都是8字节 // int*+1是a地址加上一个sizeof(int) // char*+1是b地址加上一个sizeof(char) char c1[] = "123456"; int *p1 = (int *)c1; int *p2 = p1 + 1; //+4字节 cout << *(char *)p2 << endl; cout << *(c1 + 1) << endl; //+1字节 } /*输出 5 2 */

2.7 G2.9 分配器观念整理与检讨

• 

• 示例程序，检测是否包含cookie

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

  #include <iostream> #include <vector> #include <list> using namespace std; class Foo { public: double _y; double _x; double _z; public: Foo() { _y = 0.0; _z = 0; _x = 0; } Foo(double x, double y, double z) { _x = x; _z = z; _y = 0.0; } }; int main() { cout << "\nclass size = " << sizeof(Foo) << endl; Foo *f[7]; for (int i = 0; i < 7; ++i) { double tmp = i; f[i] = new Foo(tmp * 0.2, tmp * 0.5, tmp * 0.6); } cout << "new with cookie------------" << endl; for (int i = 0; i < 7; ++i) { cout << f[i] << " "; } cout << endl; cout << "vector allocator without cookie------------" << endl; vector<Foo> vec; vec.push_back(Foo(2.4, 2.5, 1.6)); vec.push_back(Foo(4.4, 4.2, 4.7)); vec.push_back(Foo(4.4, 4.2, 4.9)); cout << &(vec[0]) << " " << &(vec[1]) << " " << &(vec[2]) << endl; for (int i = 0; i < 7; ++i) { delete f[i]; } return 0; }

• 编译器为GCC8.1.0

• 

• 关于allloc的检讨，没什么大问题，一些语法问题，以及先天缺陷。

• 

2.8 关于函数指针的补充

• 基于个人笔记的 c++ 面向对象开发学习笔记 | TycBlog (tycilyz.top) 中关于函数指针的补充。

• 在ANSI标准中，signal()的声明如下：

  1	void (*signal(int sig,void (*func)(int)))(int)

• signal是一个函数，它返回一个函数指针，该函数指针所指向的函数(signal的返回值)接受一个int参数并返回void。signal函数有两个参数，一个是sig(为int类型)，另一个是func(为void(*)(int) 即函数指针类型)。

  1 2 3 4 5

  void (*func)(int)是一个函数指针，所指向的函数接受一个int参数，返回值是void。 下面用typedef进行简化： typedef void（*ptr_to_func）(int); ptr_to_func signal（int，ptr_to_func）;

• 示例程序

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

  #include <stdio.h> #include <iostream> enum { RED, GREEN, BLUE }; void OutputSignal(int sig) { printf("The signal you have input is: "); switch (sig) { case RED: puts("RED!"); break; case GREEN: puts("GREEN!"); break; case BLUE: puts("BLUE!"); break; } } // 函数声明返回函数指针 void (*signal(int sig, void (*func)(int)))(int) { puts("Hello, world!"); func(sig); return func; } // iostream 才有的关键词typedef，c没有 typedef void (*ret)(int); int main(void) { puts("test for src..."); (*signal(GREEN, &OutputSignal))(RED); puts("test for new..."); ret ff = signal(BLUE, OutputSignal); ff(GREEN); return 0; }

• 输出结果

• 

2.9 __pool_alloc 运行观察

• 侯捷老师在G4.9运行可以看到，确实malloc的调用次数大大减少，同时因为满足累积增大原则，开辟的空间数量比需求的大。而直接安装单个new，则数量刚好，但是malloc调用次数也大大增加。

• 

• 

• 以下是我的测试代码，在minGW8.1上第一部分的__pool_alloc 的输出有问题，转到Linux上的g++9.4则测试成功，确实减少了malloc的调用次数。

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73

  #include <iostream> using namespace std; static long long sizeNew = 0; static long long countNew = 0; void *my_new(size_t sz) { return malloc(sz); } void my_delete(void *ptr) { return free(ptr); } //重载全局函数 inline void *operator new(size_t size) { // cout << "tyc global new()" << endl; sizeNew += size; //累积分配内存 countNew++; //记录malloc的次数 return my_new(size); } inline void *operator new[](size_t size) { cout << "tyc global new() []" << endl; return my_new(size); } inline void operator delete(void *ptr) { // cout << "tyc global delete()" << endl; my_delete(ptr); } inline void operator delete[](void *ptr) { cout << "tyc global delete() []" << endl; my_delete(ptr); } #include <list> #include <memory> #include <ext/pool_allocator.h> int main() { countNew = 0; sizeNew = 0; // listPool<double> lst; list<double, __gnu_cxx::__pool_alloc<double>> lst; for (int i = 0; i < 100000; ++i) { lst.push_back(i); } cout << "test pool_alloc----" << endl; cout << "new size = " << ::sizeNew << endl; cout << "new count = " << ::countNew << endl; countNew = 0; sizeNew = 0; list<double> lst1; for (int i = 0; i < 100000; ++i) { lst1.push_back(i); } cout << "test std_alloc----" << endl; cout << "new size = " << ::sizeNew << endl; cout << "new count = " << ::countNew << endl; return 0; }

• 

• 

2.10 G2.9 std::alloc 移植到 C 语言上

• 

• alloccc.h 头文件

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295

  #include <stdlib.h> //for malloc(),realloc() #include <stddef.h> //for size_t #include <memory.h> //for memcpy() //#define __THROW_BAD_ALLOC cerr << "out of memory" << endl; exit(1) #define __THROW_BAD_ALLOC exit(1) //---------------------------------------------- // 第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 個數 // union obj { //G291[o],CB5[x],VC6[x] // union obj* free_list_link; //這麼寫在 VC6 和 CB5 中也可以， // }; //但以後就得使用 "union obj" 而不能只寫 "obj" typedef struct __obj { struct __obj *free_list_link; } obj; char *start_free = 0; char *end_free = 0; size_t heap_size = 0; obj *free_list[__NFREELISTS] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; size_t ROUND_UP(size_t bytes) { return (((bytes) + __ALIGN - 1) & ~(__ALIGN - 1)); } size_t FREELIST_INDEX(size_t bytes) { return (((bytes) + __ALIGN - 1) / __ALIGN - 1); } //---------------------------------------------- // We allocate memory in large chunks in order to // avoid fragmentingthe malloc heap too much. // We assume that size is properly aligned. // // Allocates a chunk for nobjs of size "size". // nobjs may be reduced if it is inconvenient to // allocate the requested number. //---------------------------------------------- // char* chunk_alloc(size_t size, int& nobjs) //G291[o],VC6[x],CB5[x] char *chunk_alloc(size_t size, int *nobjs) { char *result; size_t total_bytes = size * (*nobjs); //原 nobjs 改為 (*nobjs) size_t bytes_left = end_free - start_free; if (bytes_left >= total_bytes) { result = start_free; start_free += total_bytes; return (result); } else if (bytes_left >= size) { *nobjs = bytes_left / size; //原 nobjs 改為 (*nobjs) total_bytes = size * (*nobjs); //原 nobjs 改為 (*nobjs) result = start_free; start_free += total_bytes; return (result); } else { size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4); // Try to make use of the left-over piece. if (bytes_left > 0) { obj *volatile *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); if (0 == start_free) { int i; obj *volatile *my_free_list, *p; // Try to make do with what we have. That can't // hurt. We do not try smaller requests, since that tends // to result in disaster on multi-process machines. for (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)); // Any leftover piece will eventually make it to the // right free list. } } end_free = 0; // In case of exception. start_free = (char *)malloc_allocate(bytes_to_get); // This should either throw an exception or // remedy the situation. Thus we assume it // succeeded. } heap_size += bytes_to_get; end_free = start_free + bytes_to_get; return (chunk_alloc(size, nobjs)); } } //---------------------------------------------- // Returns an object of size n, and optionally adds // to size n free list. We assume that n is properly aligned. // We hold the allocation lock. //---------------------------------------------- void *refill(size_t n) { int nobjs = 20; char *chunk = chunk_alloc(n, &nobjs); obj *volatile *my_free_list; // obj** my_free_list; obj *result; obj *current_obj; obj *next_obj; int i; if (1 == nobjs) return (chunk); my_free_list = free_list + FREELIST_INDEX(n); // Build free list in chunk result = (obj *)chunk; *my_free_list = next_obj = (obj *)(chunk + n); for (i = 1;; ++i) { current_obj = next_obj; next_obj = (obj *)((char *)next_obj + n); if (nobjs - 1 == i) { current_obj->free_list_link = 0; break; } else { current_obj->free_list_link = next_obj; } } return (result); } //---------------------------------------------- // //---------------------------------------------- void *allocate(size_t n) // n must be > 0 { obj *volatile *my_free_list; // obj** my_free_list; obj *result; if (n > (size_t)__MAX_BYTES) { return (malloc_allocate(n)); } my_free_list = free_list + FREELIST_INDEX(n); result = *my_free_list; if (result == 0) { void *r = refill(ROUND_UP(n)); return r; } *my_free_list = result->free_list_link; return (result); } //---------------------------------------------- // //---------------------------------------------- void deallocate(void *p, size_t n) // p may not be 0 { obj *q = (obj *)p; obj *volatile *my_free_list; // obj** my_free_list; if (n > (size_t)__MAX_BYTES) { malloc_deallocate(p, n); return; } my_free_list = free_list + FREELIST_INDEX(n); q->free_list_link = *my_free_list; *my_free_list = q; } //---------------------------------------------- // //---------------------------------------------- void *reallocate(void *p, size_t old_sz, size_t new_sz) { void *result; size_t copy_sz; if (old_sz > (size_t)__MAX_BYTES && new_sz > (size_t)__MAX_BYTES) { return (realloc(p, new_sz)); } 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); } //----------------------------------------------

• 测试程序main

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90

  #include <iostream> #include "allocc.h" #include "stdio.h" //printf() #include "stdlib.h" //malloc(),free() //---------------------------------------------- void test_G29_alloc_C_version() { std::cout << "\ntest_G29_alloc_C_version.......... \n"; //刻意使用 printf() 模擬 C 環境下. printf("\n"); { void *p1 = malloc(16); void *p2 = malloc(16); void *p3 = malloc(16); void *p4 = malloc(16); printf("%p \n", p1); printf("%p \n", p2); printf("%p \n", p3); printf("%p \n", p4); free(p1); free(p2); free(p3); free(p4); } printf("\n"); { // 二级配置器 void *p1 = allocate(16); void *p2 = allocate(16); void *p3 = allocate(16); void *p4 = allocate(16); printf("%p \n", p1); printf("%p \n", p2); printf("%p \n", p3); printf("%p \n", p4); deallocate(p1, 16); deallocate(p2, 16); deallocate(p3, 16); deallocate(p4, 16); } printf("\n"); { // 一级配置器 void *p1 = malloc_allocate(100); void *p2 = malloc_allocate(128); void *p3 = malloc_allocate(128); void *p4 = malloc_allocate(128); printf("%p \n", p1); printf("%p \n", p2); printf("%p \n", p3); printf("%p \n", p4); malloc_deallocate(p1, 100); malloc_deallocate(p2, 128); malloc_deallocate(p3, 128); malloc_deallocate(p4, 128); } printf("\n"); { void *p1 = allocate(100); void *p2 = allocate(128); void *p3 = allocate(128); void *p4 = allocate(128); printf("%p \n", p1); printf("%p \n", p2); printf("%p \n", p3); printf("%p \n", p4); deallocate(p1, 100); deallocate(p2, 128); deallocate(p3, 128); deallocate(p4, 128); } printf("\n"); } int main() { test_G29_alloc_C_version(); return 0; }

• 输出结果为

• 

3. 关于 malloc / free

3.1 VC6 和 VC10 的malloc比较

• 对于VC6而言，可以看到如下的系统调用栈图（call stack）可以看到其调用顺序，依次从下往上调用函数。

• 可以看到，对于VC6而言，若是请求的内存空间 size > threshold 则使用OS 内存分配API函数 HeapAlloc() 从 _crtheap 当中取用内存，若 size < threshold（1016 = 1024-8，SBH负责1KB及以下大小内存区块的分配请求，同时1KB内存大小又有固定的两个4Bytes的cookie开销，所以实际大小为1016Bytes），则从 SBH 当中取。

• CRT ：C Run Time Libaray，C运行时库。 是C 而非 C++ 语言世界的概念：取这个名字就是因为C 程序运行时需要这些库中的函数.

• 

• 对于VC10而言，可以看到如下的系统调用栈图（call stack）可以看到其调用顺序，依次从下往上调用函数。

• 图示可以看出，VC10不再对小区块内存进行管理，全都调用OS 内存分配API函数 HeapAlloc() 从 _crtheap 当中取用内存。这是因为windows和VC都是微软自家的，其把对小区块的内存分配深入到操作系统层面去了（Windows Heap），其仍然存在，只是进入了OS层面。

• 

• 因此以下介绍基于VC6。纵观SBH的创建与管理，学习VC关于内存管理的知识。

3.2 SBH 之始 _heap_init() 和 __sbh_heap_init()

• 无论是VC6还是VC10，首先进入的函数就是 _heap_init() 。
• 
• 该函数从_crtheap 分配16个HEADER 结构，一个header管理1M总内存，通过分段管理，进一步管理SBH分配的小于1kb的内存块，如下图所示：
• 
• struct tagHeader 里面：
  • bitvEntryHi和bitvEntryLo：一共64位，作用是标记下面的32组group的任意一组，只要其中的64对链表的某对被分配了，bitvGroupHi和bitvGroupLo的那一位就会被置1。
  • bitvCommit：32位，初始化时是 0xffffffff。也就是二进制所有位都是1，每次分配完一个group时bitvCommit对应的位会被清0，32位的bitvCommit标记着32个groups那些分配了内存块。若bitvCommit为0，即表示32个group都被分配完了。
  • pHeapData：将被指向这个header所管理的那1MB的内存空间的开头。
  • pRegion：将会被指向一个管理用的结构，这个结构将会在下边展开。

3.3 第一次内存分配 _ioinit()

• 所有程序第一次进入都是进入ioinit() 函数，分配32*8=256个字节，16进制就是100h 。

• 

• ioinit() 函数又调用_malloc_crt() 函数，如上面的call stack所示，然后里面有调用到_heap_alloc_dbg() 函数。

• 

• 结构体_CrtMenBlockHeader (==这块是附加上去给debug时用的东西==) 的大小如上图所示：

  1.pBlockHeaderNext, 指向链表后内存块； 2.pBlockHeaderPre, 指向链表前内存块； 3.szFileName, 记录申请使用该内存空间所在的文件； 4.nLine, 记录申请使用该内存空间所在文件的行号； 5.nDataSize, 实际数据区的空间大小(应用程序实际使用到的内存块)，上图的100h，不包括debug信息和cookie； 6.nBlockUse, 表示当前内存块的类型, 如 _CRT_BLOCK 给crt用的、_NORMAL_BLOCK 正常申请的内存块等...； 7.IRequest, 操作流水号； 8.gap[nNoMansLandSize]， 上下两处“栏杆”，保护应用程序实际使用到的内存，到发生内存越界的情况，调试器可以检查到。

• 

• 而_heap_alloc_dbg() 函数又会调用到 heap_alloc_base() 函数。

• 

• heap_alloc_base() 函数里面会调用 __sbh_alloc_block() 函数。

• 

• 而 __sbh_alloc_block() 函数里面又会调用__sbh_alloc_new_region() 和__sbh_alloc_new_group() 函数。

• 关于__sbh_alloc_new_region() 函数

  • 

  • 由上知，有16个HEADER，而HEADER中的两个指针如图，一个指向region，一个指向1MB的系统虚拟地址空间【调用VirtualAlloc 这个Windows API函数】。

  • struct tagRegion里面：

    • indGroupUse：表示了当前会提供内存的group编号，从0开始，0-31group，每个group管理32kb。

    • cntRegionSize[64]：char类型的数组，容量有64个，每个char成员是记录，下面所有32个Group所有的分配总数。比如group0和group2的#24链表挂载了内存，则cntRegionSize[24]=2。

    • bitvGroupHi[32]和bitvGroupLo[32]：每两个元素共同构成了一个的byteMap，共8个字节64个bit（分为32组，每组64bit），将来用于对应每个group中所挂载的64条双向链表，当对应的位置挂载有可用内存时，会变成1。bitvGroupHi, bitvGroupLo 对应 32 * （32 * 2） = 32 * 64bit 的空间，对应下面32个Group中的64个双向循环链表，记录其中每个链表是否已有空闲节点【内存是否可以使用】（1表示有，0表示无）

    • grpHeadList[32]：就是32个tagGroup，每个group负责32KB（1MB/32 = 32kb）

  • struct tagGroup 里面：

    • cntEntries：一个累积量，表示当前group中进行了分配或释放空间的次数【+1则代表分配操作，-1则代表释放回收操作，0则表示系统已经将分配的空间全部回收或没有任何空间被分配使用】.
    • listHead[64]：对应64对指针，也就是形成了64条链表，用于挂载不同大小的内存块，间隔为16byte，最后一条链表将挂载所有大于等于1K的内存块。即依次为16、32、48...1024。

  • struct tagListHead 里面：

    • pEntryNext 和 pEntryPrev：两个tagEntry类型的指针对象【即为上面Group表中的那64对指针】。tagEntry类型下面会进一步介绍。

  • 总结：上面region的这些东西的大小为4*5(header)+4+64+64 * 4 +32 * (4 + 64 * 8)(tagRegion) = 16856 byte， 而16856 / 1024 = 16.46KB，即需要创建一个region消耗约16KB的空间去管理系统分配出来的1MB的空间。

• 关于 __sbh_alloc_new_group() 函数

  • 
  • 32k更细分一下，分为8页（page），一个page大小为4k（在计算机里面，一个page表示4k，一个para（段落）表示16）。
  • sbh设定一些指针，链接上面8页，并链接到64对链表的最后一条上面去。
  • 
  • struct tagEntry 里面：
    • sizeFront：表示链表所指剩余内存的大小，为了节省内存 ，64对链表在连接上下块内存的时候，sizeFront 借用了上一个 tagEntry 的pEntryPrev。所以在每个gropu中的64对链表指针在没被投入使用时，一般都是往上指向前一个pEntryprev指针的地址从而向下包含3个的。（只是借用，没有修改，为了减少内存使用，设计很漂亮自信）。
    • pEntryNext和pEntryPrev：表示类似双向链表的指针。用来链接没被分配使用的，在sbh手上的内存块，每个内存块被链接的都是tagEntry（3部分）。
  • 
  • 上图黄色标注 0xffffffff (-1) 可理解为“阻隔器”，在内存回收合并时使用，保证相邻的page总是被分离的（不会合并）。
  • 空白的最下边和红色的最上边，两个标有4080的空间是用来记录剩余可用空间大小的cookie。

• 使用者ioinit申请分配130h空间时的切分空间操作：

• 

3.4 SBH 分配-释放内存流程

• 第1次分配 130h 内存

• 由ioinit.c，line#81申请大小为100h的内存空间，通过加上head和tail等控制信息后大小为130h，因为是第一次分配，所以从#63链表进行分配，实际上应当由#18链表进行分配(130h=若该序号的链表上有空闲空间的话，130h=304,304/16-1=18)，如果没有，就从比18大的其他有分配内存的其他链表进行分配，所以这里就是#63。

• 因为是第一次分配，之前所进行的虚拟地址分配(MEM_RESERVE)就需要进行实际分配物理地址了(MEM_COMMIT)了(注意到每次申请1MB的内存空间)，分配完毕并将内存交给客户之前，还须把对应的group当中的cntEntries字段+1。同时给交给客户的内存空间两端建立区隔（即cookie最后四位置1表示被分配了）。

• 同时region的cntRegionSize[64]和bitvGroupHi[32]、bitvGroupLo[32] 也要对应的进行增加。

• 

• 第2次分配 240h 内存

• 值得注意的是，这里给出去的指针是嵌入式指针，分配出去后客户可以覆盖该内存，回收的时候又会被当做指针。

• 

• 第15次释放 240h 内存

• 调用free函数，会释放，首先计算回归到哪一个指针，为#35list，可能还会把里面内存清除，变为特殊符号。

• 

• 第16次分配 b0h 内存

• b0/16 = 11-1 = 10，本应由#10号链表提供内存，但#10list没有挂载，故从右边最接近的提供，即#35list

• 而此时#35挂载240h内存，240h-b0h = 190h，剩余190h，该往哪个链表挂载呢？

• 190h/16-1 = 24，故需要重新挂载到#24号链表上。

• 

• 第n次分配 230h 内存

• 此时第一个group的8个page已经被用完了（有三个链表挂有区块，但是内存无法满足分配需求），因此需要去到第二个group取内存。

• 

3.5 内存区块的合并

• 连续区块的合并，利用的是上下cookie进行识别

• 

• 这里我们假设还的的1号空间，我们能看到 2、3两个空间的cookie结尾都是0，所以也是空闲的，也就是说这三块连续的空间可以合并。

  • 向下合并：我们首先有一个指向1号空间的指针，他通过cookie可以知道自己有多大，所以下调对应的大小就可以到达2号空间的开头，查看2号空间的cookie可以知道他的大小，也可以知道它是空闲的，所以可以将他们两个合并。

  • 向上合并：我们首先有一个指向1号空间的指针，他向上调整两个int的长度，可以到达3号空间的cookie，通过3号空间的cookie可以知道3号空间的大小，也可以知道3号空间是空闲的，所以就可以将他们两个合并。重复上边两个步骤，我们可以将相连的N块空闲内存全部合并，并计算大小调整连接位置。

• 这里可以看到 0xffffffff 的作用了，避免区块合并。

3.6 free(p) 的指针花落谁家

• 

• 首先需要知道哪个Mega里面，即哪一个Header，因为 __sbh_pHeaderList 已经知道了，大小已经知道了，夹杀法，进而找到具有属于哪个header。

• 然后需要确定在哪个Group里面，通过指针减掉头再除以32k，也许再减一（从0开始），即为哪个group。

• 最后确定在64对链表的哪一对，指针往上看通过cookie得出内存总大小，通过内存除以16即为哪个链表。

3.7 分段管理之妙

• 从1M->32k->4k->1k->16bytes

• 可以看到SBH的分段管理内存的做法，是为了更好的归还内存到操作系统。

• 

• SBH在每个group都记录了分配出去的次数，每当我们回收的时候，就将这个值-1，所以当它再次为0的时候，就证明这个group的内存全部回收了。

• 当group内存全回收之后的状态：由于有上边的合并机制，所以当一个group的内存全回收之后，他的状态就和最开始时一样，也就是最后一个链表上连接着8个4KB大小的内存块，这时我们就可以将他还给操作系统了（但是因为存在defering，暂时保留着）。

• 

• 因为如果我们全回收一个group就还一个group，那么当下一次在需要分配时，我们还需要重新分配。所以全回收的group不会立刻被还给系统，而是等待下一个全回收的group出现，就会将前一个group对应的内存free掉。

• 具体做法就是利用上图的 __sbh_pHeaderDefer 指针和 __sbh_indGroupDefer 索引。

• 全回收完毕会回复初始状态，如下图所示。

• 

• 以下是VC6跟踪CRT内存分配的函数，可用于查看是否存在内存泄漏。

• 

4. 关于 loki::allocator

4.1 Loki Library

• 一个技术上比较前沿的C++设计模式类库 Loki，但是并不是很成熟，因为仅仅只维护到0.1.7版本，且最后更新维护时间是2013年。
• loki 是书籍 《Modern C++ Design》配套发行的一个 C++ 代码库，里面对模板的使用发挥到了极致，对设计模式进行了代码实现。这里是 loki 库的源码。
• 该库广泛使用C++模板元编程，并实现了几种常用工具：类型列表、函子、单例、智能指针、对象工厂、访问者和多方法。
• 
• 最初，该库仅与两个最符合标准的C++编译器（CodeWarrior和Comeau C/C++）兼容；后来的努力使其可用于多种编译器（包括较旧的Visual C++6.0、Borland C++Builder 6.0、Clang和GCC）。编译器供应商使用Loki作为兼容性基准，进一步增加了兼容编译器的数量。
• Loki的维护和进一步开发通过Peter Kümmel和Richard Sposato领导的开源社区作为SourceForge项目继续进行。许多人的持续贡献提高了图书馆的整体稳定性和功能性。Loki不再与这本书挂钩，因为它已经有了很多新组件（例如StrongPtr、Printf和Scopeguard）。Loki启发了类似的工具和功能，现在也出现在Boost库集合中。
• 软件文档
• 软件首页
• 下载地址
• GNU的allocator比较霸道，内存拿到之后释放仍然在自己手上，进而可能影响其他的进程，在多任务操作系统上不太好。
• Loki的allocator可以把内存还回去。
• Loki::allocator 在 SmallObj.h 以及 SmallObj.cpp 源文件里面有说明。
• Loki的实现颇有暴力美学的味道，但是又能够较好的实现功能，相比于std::alloc，其能够对所管理的内存进行 delete[] 操作(即进行内存回收，交给os)，同时由于版本迭代很少，0.0.2版本的代码（新版已修正）还存在一定数量的 bug， 也会在下面的内容中予以指出。

4.2 Loki::allcator 源码分析

• Loki的分配器的源代码为 SmallObj.h 以及 SmallObj.cpp 。

• loki::allocator 可分为三个嵌套结构，自下而上分别为 Chunk，FixedAllocator，SmallObjAllocator。其主要数据成员如下所示。表示复合关系（下图中的箭头）。

• 

4.2.1 chunk

• 首先是初始化函数 Chunk::Init

• 

• 传入参数为分割的 block 的大小和数量。

• 首先用 new operator 分配出一大块内存 chunk，并用指针 pData_ 指向 chunk。

• Reset() 函数对这块内存进行分割。利用嵌入式指针的思想，每一块 block 的第一个 byte 存放的是 下一个可用的 block 距离起始位置 pData_ 的偏移量（以 block 大小为单位），以这种形式将 block 串成 “链表”。注意是下一个可用索引，切记！

• firstAvailableBlock_ 表示当前可用的 block 的偏移量；blocksAvailable_ 表示当前 chunk 中剩余的 block 数量。

• 初始化的chunk状态应如下：

• 

• 然后是内存分配函数 Chunk::Allocate

• 

• 可以结合下图进行理解，指向下一个区块分配并修改是关键。

• 

• 然后是内存回收函数 Chunk::Deallocate

• 回收的时候类似 std::alloc ，把内存块插入到链表头部

• 1 2 3 4 5 6 7 8 9 10 11 12 13

  void FixedAllocator::Chunk::Deallocate(void* p, std::size_t blockSize) { unsigned char* toRelease = static_cast<unsigned char*>(p); //相当于链接到链表头上，这里使用索引代替链表 *toRelease = firstAvailableBlock_; //修改 “头指针” firstAvailableBlock_ ，通过大小计算即可 //回收的 block 指针距离头指针 pData_ 的距离（以 block 为单位） firstAvailableBlock_ = static_cast<unsigned char>( (toRelease - pData_) / blockSize); //可用区块数+1 ++blocksAvailable_; }

• 

4.2.2 FixedAllocate

• FixedAllocate 则负责管理一个具有相同内存块大小 block size 的 chunk 的集合。它负责根据客户需求，创建特定 block 大小的 chunk ，并放置在容器 vector 中进行管理。

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

  FixedAllocator::FixedAllocator(std::size_t blockSize) : blockSize_(blockSize) , allocChunk_(0) , deallocChunk_(0) { assert(blockSize_ > 0); prev_ = next_ = this; //DEFAULT_CHUNK_SIZE 默认4096bytes，而blockSize是输入参数，即block的大小，也就是obj的大小 std::size_t numBlocks = DEFAULT_CHUNK_SIZE / blockSize; if (numBlocks > UCHAR_MAX) numBlocks = UCHAR_MAX; else if (numBlocks == 0) numBlocks = 8 * blockSize; numBlocks_ = static_cast<unsigned char>(numBlocks); assert(numBlocks_ == numBlocks); }

• 内存分配函数 FixedAllocator::Allocate()

• 通过for loop寻找可用的chunk。

• 

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

  void *FixedAllocator::Allocate() { if (allocChunk_ == 0 || allocChunk_->blocksAvailable_ == 0) { //目前没有标定的 chunk ，或者这个 chunk 已经用完了 //从头找起 Chunks::iterator i = chunks_.begin(); for (;; ++i) { //没找到，则创建一个新的 chunk if (i == chunks_.end()) { // Initialize chunks_.reserve(chunks_.size() + 1); Chunk newChunk; newChunk.Init(blockSize_, numBlocks_); chunks_.push_back(newChunk); allocChunk_ = &chunks_.back(); //因为可能会引起 vetor 的扩容操作，导致原来的元素被搬移到新的地方 //所以这里的 deallocChunk_ 需要重新标定，直接标定为第一个。 //原来可能并不是指向第一个，但已经无法确定原本的位置了 deallocChunk_ = &chunks_.front(); break; } if (i->blocksAvailable_ > 0) { allocChunk_ = &*i; break; } } } return allocChunk_->Allocate(blockSize_); }

• allocChunk_ 指向当前正在使用中的 chunk。如果 allocChunk_ 指向的 chunk 中的 block 已经用完了，那么就在容器中去寻找其他可用的 chunk 。如果没有找到，就新建一个 chunk ，放进容器中，并标定为当前的 allocChunk_。

• chunks_ 扩容会存在地址重新复制迁移的步骤，所以要对 deallocChunk_ 重新标定。它这里直接重新标定为第一个 chunk，因为原来的那个已经无法确定位置了。

• 内存回收函数 FixedAllocator::Deallocate(void* p)

• 1 2 3 4 5 6

  void FixedAllocator::Deallocate(void* p) { //首先找出p所属的chunk*，赋值到deallocChunk_ deallocChunk_ = VicinityFind(p); DoDeallocate(p); }

• 我们知道每一块 chunk 的头指针，以及这一块 chunk 的大小，这样的话，我们就可以计算出每一块 chunk 的地址范围。我们只要找到归还的内存的地址是落在哪一个 chunk 地址范围内，就可以确定 chunk。这一功能由函数 VicinityFind() 实现。

• VicinityFind() 函数采用一种两头渐进式查找的算法，从上一次 deallocChunk_ 的位置出发，在容器中分两头查找。但存在一个bug，如下图所示。新版已经解决了该bug，通过内联成员函数实现判断，如p指针非本系统，会因为无法调用成员函数而报错。

• 

• 新版0.1.7代码如下：

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

  inline bool HasBlock( void * p, std::size_t chunkLength ) const { unsigned char * pc = static_cast< unsigned char * >( p ); return ( pData_ <= pc ) && ( pc < pData_ + chunkLength ); } Chunk * FixedAllocator::VicinityFind( void * p ) const { if ( chunks_.empty() ) return NULL; assert(deallocChunk_); const std::size_t chunkLength = numBlocks_ * blockSize_; Chunk * lo = deallocChunk_; Chunk * hi = deallocChunk_ + 1; const Chunk * loBound = &chunks_.front(); const Chunk * hiBound = &chunks_.back() + 1; // Special case: deallocChunk_ is the last in the array if (hi == hiBound) hi = NULL; for (;;) { if (lo) { //通过调用成员函数 if ( lo->HasBlock( p, chunkLength ) ) return lo; if ( lo == loBound ) { lo = NULL; if ( NULL == hi ) break; } else --lo; } if (hi) { if ( hi->HasBlock( p, chunkLength ) ) return hi; if ( ++hi == hiBound ) { hi = NULL; if ( NULL == lo ) break; } } } return NULL; }

• 最后内存回收的动作由函数 DoDeallocate() 完成。如果当前回收的 chunk 已经将所有的 block 全部回收完了，即 deallocChunk_->blocksAvailable_ == numBlocks_ ，本来这块内存就可以归还给 OS 了的。但是这里采取了一个延迟归还 defering 的动作。把这个空的 chunk 通过 swap 函数放在 vector 的末尾，并且将 allocChunk_ 指向它，供下一次再使用。只有当有两个空 chunk 出现时，才会把上一个空的 chunk 归还给 OS。

• 同时该代码存在一个bug，存在某种情况下不归还chunk给系统的可能。新版已改正。个人认为该bug就是当只有一个block时，始终不会归还内存。

• 

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

  void FixedAllocator::DoDeallocate(void* p) { // call into the chunk, will adjust the inner list but won't release memory deallocChunk_->Deallocate(p, blockSize_); //如果已经全回收了 if (deallocChunk_->blocksAvailable_ == numBlocks_) { // deallocChunk_ is completely free, should we release it? Chunk& lastChunk = chunks_.back(); //最后一个就是当前的 deallocChunk if (&lastChunk == deallocChunk_) { // check if we have two last chunks empty if (chunks_.size() > 1 && deallocChunk_[-1].blocksAvailable_ == numBlocks_) { // Two free chunks, discard the last one lastChunk.Release(); chunks_.pop_back(); allocChunk_ = deallocChunk_ = &chunks_.front(); } return; } if (lastChunk.blocksAvailable_ == numBlocks_) { // Two free blocks, discard one lastChunk.Release(); chunks_.pop_back(); allocChunk_ = deallocChunk_; } else { // move the empty chunk to the end std::swap(*deallocChunk_, lastChunk); allocChunk_ = &chunks_.back(); } } }

• 新版代码通过添加 Chunk * emptyChunk_ 变量来改进上述代码。

• 

4.2.3 SmallObjAllocator

• SmallObjAllocator 则负责管理具有不同 block size 的 FixedAllocate 的 vector 集合。

• 1 2 3 4 5 6 7 8 9 10 11

  // 使用模板的时候，默认变量 #define DEFAULT_CHUNK_SIZE 4096 #define MAX_SMALL_OBJECT_SIZE 64 SmallObjAllocator::SmallObjAllocator( std::size_t chunkSize, std::size_t maxObjectSize) : pLastAlloc_(0), pLastDealloc_(0) , chunkSize_(chunkSize), maxObjectSize_(maxObjectSize) { }

• 内存分配函数 SmallObjAllocator::Allocate

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

  void* SmallObjAllocator::Allocate(std::size_t numBytes) { //大于最大对象大小（默认64bytes），直接用new operator成员重载函数 if (numBytes > maxObjectSize_) return operator new(numBytes); if (pLastAlloc_ && pLastAlloc_->BlockSize() == numBytes) { return pLastAlloc_->Allocate(); } //找到第一个 >= numBytes 的位置 Pool::iterator i = std::lower_bound(pool_.begin(), pool_.end(), numBytes); //没找到相同的，就重新创建一个 FixedAllocator if (i == pool_.end() || i->BlockSize() != numBytes) { i = pool_.insert(i, FixedAllocator(numBytes)); pLastDealloc_ = &*pool_.begin(); } // 注意i是迭代器 pLastAlloc_ = &*i; return pLastAlloc_->Allocate(); }

• SmallObjAllocator 不可能无穷无尽的满足客户不同的 block size 的需求。它设有一个最大的 block size 变量maxObjectSize_ 。如果客户端需求的 block size 大于这个 threshold，就直接交由 operator new 去进行处理。

• pLastAlloc_ 记录上一次分配 block 的 FixedAllocator object 。如果这一次需求的 block size 等于上一次分配的 block size，就直接使用同一个 FixedAllocator object 去分配内存。

• 如果这一次需求的 block size 不等于上一次分配的 block size，就遍历容器寻找不小于需求的 block size 而且最接近的位置，也就是 std::lower_bound() 函数的功能。如果找到 block size 相等的，就直接分配；如果没找到相等的，就在该位置上插入一个新的 FixedAllocator object。同样，为了防止 vector 扩容操作引起重新分配内存，需要对 pLastDealloc_ 进行重定位。

• 内存回收函数 SmallObjAllocator::Deallocate

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

  void SmallObjAllocator::Deallocate(void* p, std::size_t numBytes) { if (numBytes > maxObjectSize_) return operator delete(p); if (pLastDealloc_ && pLastDealloc_->BlockSize() == numBytes) { pLastDealloc_->Deallocate(p); return; } Pool::iterator i = std::lower_bound(pool_.begin(), pool_.end(), numBytes); assert(i != pool_.end()); assert(i->BlockSize() == numBytes); pLastDealloc_ = &*i; pLastDealloc_->Deallocate(p); }

• 具体做法如上所示，和分配思路区别不大。

4.3 运行示例

• 

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

  #include <bits/stdc++.h> #include "Loki/SmallObj.h" using namespace std; int main() { Loki::SmallObjAllocator myalloc(4096, 256); void *p1 = (void *) myalloc.Allocate(20); void *p2 = (void *) myalloc.Allocate(64); void *p3 = (void *) myalloc.Allocate(20); void *p4 = (void *) myalloc.Allocate(300); void *p5 = (void *) myalloc.Allocate(64); void *p6 = (void *) myalloc.Allocate(300); cout << "p1 20 = " << p1 << endl; cout << "p3 20 = " << p3 << endl; cout << "p2 64 = " << p2 << endl; cout << "p5 64 = " << p5<< endl; cout << "p4 300 = " << p4 << endl; cout << "p6 300 = " << p6 << endl; myalloc.Deallocate(p1, 20); myalloc.Deallocate(p2, 64); myalloc.Deallocate(p3, 20); myalloc.Deallocate(p4, 300); myalloc.Deallocate(p5, 64); myalloc.Deallocate(p6, 300); return 0; }

• Loki/SmallObj.h 版本采用0.02版本

• 注意在CMakeList.txt 添加对应的 Loki/SmallObj.cpp

• 输出结果为

• 

4.4 Loki::allocator 总结

• 相比于之前分析的 std::alloc 的内存管理：

• 首先是内存释放方面的优化：

  • std::alloc 一旦向 OS 索取了新的 chunk，就不会还给 OS 了，一直在自己的掌控之中。因为它里面的指针拉扯比较复杂，几乎不可能去判断一块 chunk 中给出去的 block 是否全部归还了。
  • 但是 loki::allocator 通过利用一个 blocksAvailable_ 变量，就很容易的判断出某一块 chunk 中的 block 是否已经全部归还了，这样就可以归还给 OS。

• 然后是服务的对象大小方面的优化：

  • std::alloc 只负责一些特定 block size 的内存管理。如果客户端需要的 block size 它并不支持，那个客户端的 block size 会被取整到最接近的大小 (当然前提是小于它所能够分配的最大的 block size）；
  • 但是 loki::allocator 能够为不大于最大 block size 的所有 block size 服务。

• 

• 最大的优点，使用array代替list，即数组(vector)代替链表，同时使用索引(index)下标代替指针(pointer)，设置可回收变量。

5. 其他问题

5.1 GNU C++ 对于 Allocator的描述

• gcc的额外分配器在 /c++/ext 文件夹里面，在gcc8.1.0，有9种额外的分配器。
• 参考 gcc.gnu 网址
• 
• 
• 关于 __gnu_cxx::new_allocator 和 __gnu_cxx::malloc_allocator 的描述
• 
• 智能型 allocator
• 
• 
• 

5.2 VS2013 与 GCC4.9 版本的标准分配器

• 
• 

5.3 malloc_allocator

• 底部直接调用 malloc 和 free 函数。没有其他特殊操作。
• 没什么大用处。
• 

5.4 array_allocator

• 值得注意的是，在GCC11或以上版本，array_allocator 这种分配器已经被弃用了。

• 可参见官网 https://gcc.gnu.org/

• 

• 

• 

• 

• 测试示例

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

  #include <bits/stdc++.h> #include <iostream> #include <memory> #include <ext/array_allocator.h> typedef std::array<int, 10> ARRAY; using namespace std; int main() { // 以下调用方式会报错 // int my[65536]; // __gnu_cxx::array_allocator<int,array<int,65536>> testall(&my); // 以下调用方式才成功 // 在gcc8.1.0，array_allocator已经被弃用了，gcc11已经不存在array_allocator ARRAY *pt = new ARRAY; __gnu_cxx::array_allocator<int, array<int, 10>> testall(pt); int *p1 = testall.allocate(1); int *p2 = testall.allocate(3); //int *p3 = testall.allocate(8); terminate called after throwing an instance of 'std::bad_alloc' int *p3 = testall.allocate(2); cout << "p1 = " << p1 << endl; cout << "p2 = " << p2 << endl; cout << "p3 = " << p3 << endl; testall.deallocate(p1, 1); testall.deallocate(p2, 3); testall.deallocate(p3, 2); cout<<"-------------------"<<endl; cout << "p1 = " << p1 << endl; cout << "p2 = " << p2 << endl; cout << "p3 = " << p3 << endl; delete pt; return 0; }

• 输出结果

• 

5.5 debug_allocator

• 需要输入一个分配器模板，本身并不分配内存
• 本质就类似cookie
• 

5.6 __pool_alloc

• 即2.9版本的alloc。
• 测试用例看2.2章节。
• 
• 

5.7 bitmap_allocator

5.7.1 概述

• bitmap_allocator 是 gcc 拓展分配器的其中一种，它采用内存池策略，最多存储64条空闲链表（freelist，实际是一块空间连续的内存区，minivector为底层，后面也称为超级块 superblocks），内存池的阈值总是维持在64，任何时刻内存池的链表个数都不会超过64。

• bitmap_allocator空间分配器仅适合分配单一对象，超过一个对象的分配，采用operator new分配内存，回收亦然。该分配器通过位图存储方式，位图中的每一位均记录对应内存块的使用情况，0表示已用，1表示可用。同时，每个空闲链表头部记录了该链表总空间大小，总内存块个数等信息。

• 参考1

• 参考2

• 

• 

• 

• 假设申请的对象为double，即block大小为8字节，size_t（unsigned integer）为4字节大小，那么0号链表 total_size=4+（4*2）+（8*64）= 524，_Alloc_block初始为64个，分配个数视情况而定，每次新申请内存则blocks的个数按2倍递增，若发生回收入内存池则下次分配减半。

5.7.2 __mini_vector 类

• __mini_vector，自定义的一个类似于std::vector容器的类，支持存储空间自动扩充，内存的申请和释放采用调用::operator new 和::operator delete申请一块连续的内存。

• __mini_vector靠三个指针来管理：

• _M_start : 指向 __mini_vector 的第一个元素。

• _M_finish : 指向最后一个元素的下一个位置。

• _M_end_of_storage : 指向容量的末尾。

• 实际使用中，每个元素为 std::pair<_Alloc_block*, _Alloc_block*>，first元素指向super-blocks的第一个 _Alloc_block，second元素指向为最后一个 _Alloc_block 。

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83

  template<typename _Tp> class __mini_vector { __mini_vector(const __mini_vector&); __mini_vector& operator=(const __mini_vector&); public: typedef _Tp value_type; typedef _Tp* pointer; typedef _Tp& reference; typedef const _Tp& const_reference; typedef std::size_t size_type; typedef std::ptrdiff_t difference_type; typedef pointer iterator; private: pointer _M_start; // 指向容器第一个元素 pointer _M_finish; // 指向容器最后一个元素的下一个位置 pointer _M_end_of_storage; // 指向容器末端 size_type _M_space_left() const throw() { return _M_end_of_storage - _M_finish; } _GLIBCXX_NODISCARD pointer allocate(size_type __n) { return static_cast<pointer>(::operator new(__n * sizeof(_Tp))); } void deallocate(pointer __p, size_type) { ::operator delete(__p); } public: __mini_vector() : _M_start(0), _M_finish(0), _M_end_of_storage(0) {} size_type size() const throw() { return _M_finish - _M_start; } iterator begin() const throw() { return this->_M_start; } iterator end() const throw() { return this->_M_finish; } reference back() const throw() { return *(this->end() - 1); } reference operator[](const size_type __pos) const throw() { return this->_M_start[__pos]; } void insert(iterator __pos, const_reference __x); void push_back(const_reference __x) { // 如果容器还有剩余空间，直接向末端插入元素，否则调用insert重新申请空间，所有元素迁移，__x放置末端 if (this->_M_space_left()) { *this->end() = __x; ++this->_M_finish; } else this->insert(this->end(), __x); } void pop_back() throw() { --this->_M_finish; } void erase(iterator __pos) throw(); void clear() throw() { this->_M_finish = this->_M_start; } };

5.7.3 free_list 类

• 是bitmap_allocator 的父类。

• 重点的成员

  • _S_free_list ：类型为 __mini_vector<value_type> ，里面的对象是super-blocks的首地址，即一个指针。

• free_list，即开篇所说的内存池，管理着不超过64条空闲链表（本质是内存空间连续的超级块）的申请和回收，它是bitmap_allocator空间分配器中系统内存申请和释放的直接接口对象。

• free_list 内存池，内部通过使用 __mini_vector容器，存储每个超级块的首地址。同时，超级块的首地址指向的 size_t 字段，记录着超级块的总内存大小，这个大小，也是空间配置器请求的块大小。内存池根据请求的大小，并以该值，作为 __mini_vector 容器元素排序的依据。

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83

  class free_list { public: typedef std::size_t* value_type; typedef __detail::__mini_vector<value_type> vector_type; typedef vector_type::iterator iterator; typedef __mutex __mutex_type; private: struct _LT_pointer_compare { bool operator()(const std::size_t* __pui, const std::size_t __cui) const throw() { return *__pui < __cui; } }; #if defined __GTHREADS __mutex_type& _M_get_mutex() { static __mutex_type _S_mutex; return _S_mutex; } #endif // 获取内存池，返回 __mini_vector vector_type& _M_get_free_list() { static vector_type _S_free_list; return _S_free_list; } // 内存池最大存储64条内存链表，即超级块，且按其大小升序排列，当内存池满时，即达到65，新的超级块请求入内存池， // 判断超级块的total_size大小（__addr指向total_size），若为最大，不回收到内存池，直接还给操作系统， // 否则将内存池最大的超级块还给操作系统，再将该超级块插入内存池。 void _M_validate(std::size_t* __addr) throw() { vector_type& __free_list = _M_get_free_list(); const vector_type::size_type __max_size = 64; if (__free_list.size() >= __max_size) { if (*__addr >= *__free_list.back()) { ::operator delete(static_cast<void*>(__addr)); return; } else { ::operator delete(static_cast<void*>(__free_list.back())); __free_list.pop_back(); } } iterator __temp = __detail::__lower_bound(__free_list.begin(), __free_list.end(), *__addr, _LT_pointer_compare()); __free_list.insert(__temp, __addr); } // 决定当前内存请求的内存损耗是否可接受，这里定的是36%，超过返回false，否则返回true bool _M_should_i_give(std::size_t __block_size, std::size_t __required_size) throw() { const std::size_t __max_wastage_percentage = 36; if (__block_size >= __required_size && (((__block_size - __required_size) * 100 / __block_size) < __max_wastage_percentage)) return true; else return false; } public: // 超级块回收到内存池，_addr指向total_num，记录超级块中block的使用计数 inline void _M_insert(std::size_t* __addr) throw() { #if defined __GTHREADS __scoped_lock __bfl_lock(_M_get_mutex()); #endif // _M_validate参数的指针需指向超级块的total_size字段(内存池根据此值排序超级块)，因此这里指针要往前偏移一个size_t this->_M_validate(reinterpret_cast<std::size_t*>(__addr) - 1); } // 根据申请内存大小（__sz）返回可使用的超级块 std::size_t* _M_get(std::size_t __sz) _GLIBCXX_THROW(std::bad_alloc); // 清空内存池 void _M_clear(); };

• 

5.7.4 bitmap_allocator 类

• 重要成员 static _BPVector _S_mem_blocks ，类型为 __mini_vector ，里面的对象是pair。

• _Bitmap_counter 管理位图的重要类。static __detail::_Bitmap_counter<_Alloc_block*> _S_last_request;

• 每次从_S_mem_blocks 内存池申请超级块则加倍（64-128-256），若发生superblocks全回收，则下去申请内存减一半（256-128-64）。

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131

  template<typename _Tp> class bitmap_allocator : private free_list { public: typedef std::size_t size_type; typedef std::ptrdiff_t difference_type; typedef _Tp* pointer; typedef const _Tp* const_pointer; typedef _Tp& reference; typedef const _Tp& const_reference; typedef _Tp value_type; typedef free_list::__mutex_type __mutex_type; template<typename _Tp1> struct rebind { typedef bitmap_allocator<_Tp1> other; }; #if __cplusplus >= 201103L typedef std::true_type propagate_on_container_move_assignment; #endif private: template<std::size_t _BSize, std::size_t _AlignSize> struct aligned_size { enum { // value为_BSize以_AlignSize对齐后的大小 modulus = _BSize % _AlignSize, value = _BSize + (modulus ? _AlignSize - (modulus) : 0) }; }; // 空间分配器分配的单元，_BALLOC_ALIGN_BYTES是宏定义，定义为8 struct _Alloc_block { char __M_unused[aligned_size<sizeof(value_type), _BALLOC_ALIGN_BYTES>::value]; }; typedef typename std::pair<_Alloc_block*, _Alloc_block*> _Block_pair; // first指向超级块的首个block，second指向超级块最后一个block typedef typename __detail::__mini_vector<_Block_pair> _BPVector; typedef typename _BPVector::iterator _BPiter; // 模板参数_Predicate为仿函数，_S_find主要寻找可用的超级块对应的_Block_pair template<typename _Predicate> static _BPiter _S_find(_Predicate __p) { _BPiter __first = _S_mem_blocks.begin(); while (__first != _S_mem_blocks.end() && !__p(*__first)) ++__first; return __first; } #if defined _GLIBCXX_DEBUG void _S_check_for_free_blocks() throw() { typedef typename __detail::_Ffit_finder<_Alloc_block*> _FFF; _BPiter __bpi = _S_find(_FFF()); _GLIBCXX_DEBUG_ASSERT(__bpi == _S_mem_blocks.end()); } #endif // 复杂度：O（1），但内部取决于free_list::M_get。写入位图头的部分时间复杂度O（X），其中X是获取到的超级块中block的个数。 void _S_refill_pool() _GLIBCXX_THROW(std::bad_alloc); static _BPVector _S_mem_blocks; // 存放空间分配器可用的超级块，以block_pair形式保存 static std::size_t _S_block_size; 　// 超级块中block的个数，每次从内存池申请超级块则加倍，回收减一半 static __detail::_Bitmap_counter<_Alloc_block*> _S_last_request; // 指向上一次访问的位图 static typename _BPVector::size_type _S_last_dealloc_index; // 上一次回收block的超级块对应在_S_mem_blocks的下标 #if defined __GTHREADS static __mutex_type _S_mut; #endif public: // 分配和回收函数 pointer _M_allocate_single_object() _GLIBCXX_THROW(std::bad_alloc); void _M_deallocate_single_object(pointer __p) throw(); public: bitmap_allocator() _GLIBCXX_USE_NOEXCEPT { } bitmap_allocator(const bitmap_allocator&) _GLIBCXX_USE_NOEXCEPT { } template<typename _Tp1> bitmap_allocator(const bitmap_allocator<_Tp1>&) _GLIBCXX_USE_NOEXCEPT { } ~bitmap_allocator() _GLIBCXX_USE_NOEXCEPT { } _GLIBCXX_NODISCARD pointer allocate(size_type __n); _GLIBCXX_NODISCARD pointer allocate(size_type __n, typename bitmap_allocator<void>::const_pointer) { return allocate(__n); } void deallocate(pointer __p, size_type __n) throw(); pointer address(reference __r) const _GLIBCXX_NOEXCEPT { return std::__addressof(__r); } const_pointer address(const_reference __r) const _GLIBCXX_NOEXCEPT { return std::__addressof(__r); } size_type max_size() const _GLIBCXX_USE_NOEXCEPT { return size_type(-1) / sizeof(value_type); } #if __cplusplus >= 201103L template<typename _Up, typename... _Args> void construct(_Up* __p, _Args&&... __args) { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); } template<typename _Up> void destroy(_Up* __p) { __p->~_Up(); } #else void construct(pointer __p, const_reference __data) { ::new((void *)__p) value_type(__data); } void destroy(pointer __p) { __p->~value_type(); } #endif };

• 

5.7.5 分配图解

• 
• 
• 
• 
• 

5.7.6 回收图解

• 
• 
• 

5.8 小测

• 过于简单，以后业务有用到再另添。
•