std 源码剖析及 C 内存管理(二)
时间：2021-09-16 14:03:45
[导读]大家好，我是唐唐！本文关于C内存管理学习笔记自侯捷，上次笔记见 C内存管理（一）。1.各个标准分配器实现1.1VC6.0malloc在第一节中提到，malloc的内存块布局如上，其中cookie(记录区块大小)小，浪费率高，因为cookie始终占8字节。cookie是我们不需...
大家好，我是唐唐！本文关于 C 内存管理学习笔记自侯捷，上次笔记见 C 内存管理（一）。
结论：同 vc6.0。
而 g2.9 容器使用的分配器，不是 std::allocator,而是std::alloc。对于前面提到的 malloc 设计，如果想要优化,可以减少malloc次数，同时减少cookie。而去除 cookie 的先决条件是你的 cookie 大小一致。容器里面的元素是一样的大小，这就满足了先决条件！分配器的客户不是给你应用程序用，而是给容器用。
1.5 G4.9结构
g4.9 的 __pool_alloc 是我们在容器中使用的分配器。而普通的 allocator，则是通过 operator new 与 operator delete 调用 malloca 与 free。其实没有什么特殊设计。最后，来个测试用例,通过对比 allocator 与 __pool_alloc 来看看连续地址相差字节，来判断是否携带 cookie。
2.2 std::alloc运行过程
申请32bytes图32 字节对应 #3 指针所指向的链表,此时由于战备池为空,故向战备池中充值
申请 96bytes 图由于战备池中没有余量，此时向战备池中注入
山穷水尽了，怎么办,此时给出了两种办法，但是在 GCC 中没有采纳任何作法！
定义了 union free_list_link，嵌入式指针，在上一章中我们构建的一个小的分配器中也定义了该联合体，作用类似，该联合体只有一个成员,因此可以使用 struct 代替。free_list 是一个有 16个obj* 元素的数组，在前面讲过，GCC 2.9 的分配器用一个16 字节数组管理 16 条链表，free_list 便是该管理数组。refill 和 chunk_alloc 在后面再介绍。start_free 和 end_free 分别指向该内存池的头和尾。中间管理的就是战备池！这一块对应到 G4.9 中，代码如下：
大家好，我是唐唐！本文关于 C 内存管理学习笔记自侯捷，上次笔记见 C 内存管理（一）。
1.各个标准分配器实现
1.1 VC6.0 malloc
在第一节中提到，malloc 的内存块布局如上，其中 cookie (记录区块大小)小，浪费率高，因为 cookie 始终占 8 字节。cookie 是我们不需要的，如果大量调用 malloc 的话 cookie 总和会增多，这会造成较大的浪费，因此减少 malloc 调用次数，去掉 cookie 总是好的。1.2 VC6.0标准分配器
结论：VC6.0 的 allocate() 函数只是对 malloc 的二次封装，并没有做什么很特殊的操作，它是以类型字节长度为单位分配内存的，上图就分配了512个int类型空间。结论：同 vc6.0。
1.3 G2.9 malloc
GCC 2.9 版本的 allocator 如上图所示,同样这里的 allocator 同前面提到的几个标准分配器一样。而 g2.9 容器使用的分配器，不是 std::allocator,而是std::alloc。对于前面提到的 malloc 设计，如果想要优化,可以减少malloc次数，同时减少cookie。而去除 cookie 的先决条件是你的 cookie 大小一致。容器里面的元素是一样的大小，这就满足了先决条件！分配器的客户不是给你应用程序用，而是给容器用。
1.4 G4.9 malloc
在 GCC 4.9 版本，2.9 版本的 alloc 变成了 __pool_alloc。从上面两张图可以对比看出，2.9 版本的 allocate 和 4.9 版本的 __pool_alloc 做的事是一样的，只是修改了变量名和一些细小操作而已。1.5 G4.9结构
g4.9 的 __pool_alloc 是我们在容器中使用的分配器。而普通的 allocator，则是通过 operator new 与 operator delete 调用 malloca 与 free。其实没有什么特殊设计。最后，来个测试用例,通过对比 allocator 与 __pool_alloc 来看看连续地址相差字节，来判断是否携带 cookie。#include #include #include
using namespace std;
templatevoid 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));}
int main(void){ cout << sizeof(__gnu_cxx::__pool_alloc) << endl; vector > vecPool; cookie_test(__gnu_cxx::__pool_alloc(), 1);
cout << "----------------------" << endl;
cout << sizeof(std::allocator) << endl; vector > vecPool2; cookie_test(std::allocator(), 1);
return 0;}输出：1p1= 0x5557fc0f1280p2= 0x5557fc0f1288p3= 0x5557fc0f1290----------------------1p1= 0x5557fc0f13d0p2= 0x5557fc0f13f0p3= 0x5557fc0f1410可以发现容器使用的 __pool_alloc 后，连续地址相差 8 字节,而一个 double 类型变量的大小也是 8 个字节，说明这连续几块内存之间是不带 cookie 的（即使这几块内存在物理上也是不连续的）。而后面那个则相差更多(相差 32 字节，携带了 cookie )。2.std::alloc
2.1 G2.9 运作模式
G2.9 std::alloc 运作模式使用一个 16 个携带指针头的数组来管理内存链表，而我们上一章只是用了一条链表。数组不同的元素管理不同的区块，每个元素之间相差 8 字节,例如 #3 号元素负责管理 32bytes 为一小块的链表。途中 pool 就是战备池( start_free 与 end_free 中间部分)，所以总是把分配的东西放到战备池中，再从战备池挖适当的空间到链表来。这样构思，代码写起来特别漂亮。假设现在用户需要 32 字节的内存，std::allloc 先申请一块区间，为32*20*2 大小，用一条链表管理，然后让数组的#3链表指针管理这条链表。接着讲该以 32 为一个单元的链表的中的一个单元（ 32 字节）分给用户。(对应图中绿色部分).为什么是 32*20*2？前面 32*20 空间是分配给用户的，但是后面的 32*20 空间是预留的，如图所示,如果这时用户需要一个 64 字节的空间，那么剩下的 32*20 空间将变成 64*10，然后将其中 64 字节分配给用户，而不用再一次地构建链表和申请空间。其中 20 是开发团队设计的一个值。如果该链表组维护的链表最大的一个小块为 128byte，但是用户申请内存块超过了 128byte，那么 std::alloc 将调用 malloc 给用户分配空间，然后该块将带上 cookie头和尾。前面一节提到内存管理的核心设计:嵌入式指针.在真正的商业级的内存分配器中，一般都会使用嵌入式指针，将每一个小块的前四个字节用作指针连接下一块可用的内存块。这样不需要多分配额外空间,就可以完成任务。2.2 std::alloc运行过程
申请32bytes图32 字节对应 #3 指针所指向的链表,此时由于战备池为空,故向战备池中充值 32*20*2 RoundUp(0>>4=1280) ,从中切出一块返回给客户,剩余 19 块,累计申请量有 1280 字节,战备池有 640 字节.RoundUp 实现 8 字节对齐.例如传入 13,传出的就是 16. 0>>4 表示右移 4 位,每次除以 16.申请 64bytes 图上次的战备池有 640 字节，下次的分配就会从战备池中取，这次申请 64 字节，对应到#7链表指针，此时使用战备池中的字节做区块,可以得到 10 个，从中切出一块返回给用户，剩余 9，此时累计申请量：1280 ，战备池大小此时为 0。申请 96bytes 图由于战备池中没有余量，此时向战备池中注入
96*20*2 RoundUp(1280>>4) 其余原理同上。后面的申请图同上原理。战备池不够了，碎片状态如何处理：在前面的战备池中还有 24 字节，此时需要 72 字节，战备池中 1 个区块都不能够满足，因此要先解决 24 区字节碎片，再重新往 #8 中充值。碎片处理，24 字节对应的是 #2，那么把刚才的 24 字节块拉到 #2 即可。此时要重新往 #8 中充值,同事此时假设系统的 heap 大小为 10000，此时分配的72*20*2 RoundUp(9688>>4 再加上之前的累计申请量，更新后就超过了 10000，资源不够了，那此时就需要从后面最近的链表元素借。在上一个图中我们发现 #9 满足,此时 80 - 72=8，也就是战备池为 8。切除了 72 返回给用户。再申请 72 字节原理结合了碎片处理与上面的资源限制处理：此时申请 120 字节,对应 #14，根据上述原理,此时已经山穷水尽！山穷水尽了，怎么办,此时给出了两种办法，但是在 GCC 中没有采纳任何作法！
3.std::allloc 源码剖析
3.1 G2.9 与 G4.9 简要对比
侯老师的 ppt 讲解源码是 G2.9，这里我将以 G4.9 自学方式对比课上 G2.9 内容。在 G2.9 中有 std::alloc 的第一级分配器与第二级分配器,在 G4.9 中只有前面的第二级分配器，因此侯老师在讲解过程中先从第二级分配器讲解，只提及第一级分配器中的设计注意点，下面一起来学习。上面是 G2.9 的源码,其中分配器为 __default_alloc_template，一开始默认使用的分配器，在该类中定义了 ROUND_UP 函数，用来将申请内存数量做 8 字节对齐。定义了 union free_list_link，嵌入式指针，在上一章中我们构建的一个小的分配器中也定义了该联合体，作用类似，该联合体只有一个成员,因此可以使用 struct 代替。free_list 是一个有 16个obj* 元素的数组，在前面讲过，GCC 2.9 的分配器用一个16 字节数组管理 16 条链表，free_list 便是该管理数组。refill 和 chunk_alloc 在后面再介绍。start_free 和 end_free 分别指向该内存池的头和尾。中间管理的就是战备池！这一块对应到 G4.9 中，代码如下：
class __pool_alloc_base{protected:
enum { _S_align = 8 }; enum { _S_max_bytes = 128 }; enum { _S_free_list_size = (size_t)_S_max_bytes / (size_t)_S_align };
union _Obj{union _Obj* _M_free_list_link;char _M_client_data[1]; // The client sees this.};
static _Obj* volatile _S_free_list[_S_free_list_size];
// Chunk allocation state. static char* _S_start_free; static char* _S_end_free; static size_t _S_heap_size;
size_t _M_round_up(size_t __bytes){ return ((__bytes (size_t)_S_align - 1) 
下载文档
