std 源码剖析及 C 内存管理(二)
扫描二维码
随时随地手机看文章
大家好,我是唐唐!本文关于 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;
template
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));
}
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)