承德网站推广,WordPress摘要文字字数,济南网站seo技术,ftp上安装wordpressC内存管理机制#xff08;侯捷#xff09;
本文是学习笔记#xff0c;仅供个人学习使用。如有侵权#xff0c;请联系删除。
参考链接
Youtube: 侯捷-C内存管理机制
Github课程视频、PPT和源代码: https://github.com/ZachL1/Bilibili-plus
下面是第二讲allocator具体实…C内存管理机制侯捷
本文是学习笔记仅供个人学习使用。如有侵权请联系删除。
参考链接
Youtube: 侯捷-C内存管理机制
Github课程视频、PPT和源代码: https://github.com/ZachL1/Bilibili-plus
下面是第二讲allocator具体实现的笔记。 文章目录 C内存管理机制侯捷17 VC6 malloc18 VC6标准分配器之实现19 BC5标准分配器之实现20 G2 9标准分配器之实现21 G2.9 std::alloc VS G4.9 __pull_alloc22 G4.9 __pull_alloc用例23 G2.9 std::alloc24 G2.9 std::alloc运行一瞥01-0525 G2.9 std::alloc运行一瞥06-1026 G2.9 std::alloc运行一瞥11-1327 G2.9 std::alloc源码剖析上28 G2.9 std::alloc源码剖析中29 G2.9 std::alloc源码剖析下30 G2.9 std::alloc观念大整理31 G4.9 pull allocator运行观察后记 17 VC6 malloc
VC6下的malloc内存块布局从上往下分别是cookiedebug header, 实际数据的block, debug tail, pad, cookie对应于下图。 在VC6Visual C 6.0下malloc 函数分配的内存块的布局包含以下部分 Cookie饼干 Cookie 是一小段额外的标识信息用于在边界检查中检测缓冲区溢出。它通常是一个特殊的值放置在分配的内存块的开始位置。 Debug Header调试头部 Debug Header 包含一些调试信息例如分配的文件名、行号等。这些信息用于调试和跟踪内存分配的源。 实际数据的 Block 这是分配的实际数据块用于存储程序员请求的数据。 Debug Tail调试尾部 Debug Tail 包含与调试信息相关的尾部数据。类似于 Debug Header它包含一些额外的调试信息。 Pad填充 填充是为了确保分配的内存块满足特定的对齐要求。它可能包含一些额外的字节使得整个内存块的大小满足特定的对齐条件。 Cookie饼干 与开头的 Cookie 相对应是分配的内存块的结束位置。
这样的内存布局在 VC6 中用于调试和检测内存溢出等问题。Cookie 和调试信息是为了帮助调试过程检测潜在的内存错误。在实际的发布版本中这些额外的调试信息通常会被省略以减小内存开销。 VC6 是相对较老的版本现代的 Visual C 版本可能采用了更高效和精简的内存分配方案。
18 VC6标准分配器之实现
VC6标准分配器allocator的实现里面的allocate和deallocate的实现只是调用::operator new 和::operator delete, 没有任何特殊设计。我们知道它们底层是malloc和free所以具体分配的时候是带有cookie的存在内存浪费的现象。
这里分配的单位是具体的类型比如allocatorint().allocate(512,(int*)0);分配的就是512个int类型的大小。而后面讲到的一个分配器是以字节为单位不是以具体类型的大小为单位。 19 BC5标准分配器之实现
Borland5 编译器的allocator的实现里面的allocate和deallocate的实现只是调用::operator new 和::operator delete, 没有任何特殊设计。 20 G2 9标准分配器之实现
GNU C2.9标准分配器std::allocator的实现里面的allocate和deallocate的实现只是调用::operator new 和::operator delete, 没有任何特殊设计。 GNU C2.9容器使用的分配器不是std::allocator,而是std::alloc
void* p alloc::allocate(512); // 分配512bytes不是512个int或者512个double类型等等21 G2.9 std::alloc VS G4.9 __pull_alloc
G2.9 std::alloc在G4.9中是 __pull_alloc G4.9版本中标准分配器std::allocator的实现里面的allocate和deallocate的实现只是调用::operator new 和::operator delete, 没有任何特殊设计。 22 G4.9 __pull_alloc用例
这里的allocG2.9的叫法, G4.9叫做__pull_alloc用法, 它在__gnu_cxx这个命名空间内。
vectorint, __gnu_cxx::__pool_allocint vecPool;这个分配器是去除了cookie一个元素带有上下两个cookie共8B可以省很多的内存空间。 23 G2.9 std::alloc
alloc的运作模式
上文C内存管理机制侯捷笔记1介绍的是Per class allocator,每个类里面重载了 operator new和operator delete每个类都单独维护一个链表。
下面如下图所示是std::alloc为所有的类维护16个链表每个链表负责不同大小的区块分配从小到大分别负责8B, 16B, 24B, 32B,…, 按8的倍数增长最大是16 x 8 128B。当大小不为8的倍数的时候分配器会自动将其对齐到8的倍数。当大小超过128B时就交给malloc来单独处理。
当一个vector里面存了一个“stone”类型的对象它的大小是32B那么就会启用下面的#3的链表它负责32B区块的分配。每次分一大块里面有20个小块每个都是32但是实际分配的时候是20个小块的两倍大小剩余的部分暂且不用), 指定一个小块给stone即可。 嵌入式指针embedded pointers 嵌入式指针工作原理借用A对象所占用的内存空间中的前4个字节这4个字节用来 链住这些空闲的内存块 但是一旦某一块被分配出去那么这个块的 前4个字节 就不再需要此时这4个字节可以被正常使用 参考:https://blog.csdn.net/qq_42604176/article/details/113871565 内存的使用方法是,使用的时候看成对象实例,空闲的时候会看成next指针. 参考https://github.com/KinWaiYuen/KinWaiYuen.github.io/blob/master/c%2B%2B/%E4%BE%AF%E6%8D%B7%E5%86%85%E5%AD%98.md 24 G2.9 std::alloc运行一瞥01-05
下面的free_list大小__NFREELISTS为16 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 };
# enum {__ALIGN 8};
size_t ROUND_UP(size_t bytes) {return (((bytes) __ALIGN-1) ~(__ALIGN - 1));
}解释ROUND_UP
这段代码定义了一个常量 __ALIGN它表示内存分配时的对齐边界设定为 8 字节。然后定义了一个函数 ROUND_UP该函数接受一个大小bytes作为参数然后将其上调到对齐边界。
具体来说ROUND_UP 函数的作用是将传入的大小 bytes 上调到 __ALIGN 的倍数。这是通过以下步骤实现的
将 bytes 加上 __ALIGN-1即将 bytes 7。对结果进行按位与操作通过 ~(__ALIGN - 1) 将最低的 3 位清零确保结果是 __ALIGN 的倍数。
这样做的目的是为了满足内存对齐的要求。在一些硬件体系结构中访问未对齐的内存可能会导致性能问题或者错误因此内存分配时通常需要对齐到某个特定的边界。这个函数就提供了一种简单的方法来确保分配的内存大小是对齐的。 当一个容器里面存储的元素大小是32B时它的运作过程如下
挂在几号链表呢32 / 8 - 1 3号链表
刚开始的时候pool为空此时要分配32 * 20 *2 RoundUp(0 4) 1280B大小的空间为pool然后从pool里面切割20个小块共640B挂在#3链表上剩下的640B放在pool里面备用。RoundUp是追加量里面的大小是把上次的累计申请量右移4位(除以16)由于这里是刚开始没有累计申请量故为04。 此时又创建了新的容器它里面的元素大小为64B对应#7链表此时链表为空。由于上页的pool里面还剩640B现在将其切分为640/64 10个区块第一个给容器剩下的9个挂在list #7. 此时pool的大小为0因为被切分挂到链表上了。 在上面的基础上现在新建容器它的元素大小为96B对应96 / 8 - 1 11号链表先检查pool时候有余量由于pool为空此时调用malloc分配一大块作为pool总共大小为96x 20 x 2 RoundUp(1280 4) 3840 80 3920B其中20个区块拿出来用1个区块返回给容器另外19个区块挂在#11链表上剩下的就是pool的容量那么pool为多大呢3920−(96×20)3920−19202000 B。另外累计申请量多大呢上次是1280这次申请的总共是3920 加起来共5200.单位都是bytes。如下图所示。 再次新建容器里面元素大小是88B现在是挂在几号链表呢? 88 / 8 - 1 10号链表。现在要看pool中的余量为2000将2000切分为20个区块每个区块88B第一个区块给容器剩下的19个区块挂在#10链表上。pool剩下的余量2000 - 88 x 20 240B 25 G2.9 std::alloc运行一瞥06-10
下面这张图表示容器连续申请3次88B大小的空间由于上面已经在#10 链表上挂了19个大小为88B的区块这时候直接从该链表上拿下来3个区块返回给容器即可。pool大小还是240没变。 又来新的容器它的元素大小为8B该挂在几号链表呢8 / 8 - 1 0号链表上面的pool容量为240从pool里面切分出20个区块共8B x 20 160B大小第一个返回给容器其余19个区块挂在#0链表上。pool剩余多少呢240 - 160 80B。 又来新的容器它的元素大小为104B该挂在几号链表呢104 / 8 - 1 12号链表。但是pool余量为80B一个大小为104B的区块都切分不了。此时这个80B大小的空间就是碎片需要将其挂在某一个链表上该挂在几号呢80 / 8 - 1 9号链表。碎片处理完之后 再来应付现在的需求104B的分配。
现在再调用malloc分配一大块大小为104 x 20 x 2 RoundUp(5200 4) 4160 RoundUp(325) 4160 328 4488
pool容量为4488 - 104 x 20 2408B
把第一个区块分配给容器切出的19个挂在#12 list上。pool的余量为2408B。累计申请量为5200 4488 9688B 现在申请112B挂在112 / 8 - 1 13号链表上上面pool容量为2408从里面取出112 * 20 2240第一个区块返回给容器留下19个区块挂在13号链表上。
pool余量为2408 - 2240 168B。 现在的新需求是申请48B(48 / 8 - 1 5号链表)上面的pool余量是168B可以分配几个区块呢 168 / 48 3 … 24, 所以可以分配3个大小为48的区块pool余量为24B。
3个区块中第一个返回给容器后面两个挂在5号链表上。 26 G2.9 std::alloc运行一瞥11-13
下面看一下内存分配失败的动作
新的容器请求72B的大小挂在几号链表呢72 / 8 - 1 8号链表pool容量为24B不足以分配一个大小为72B的区块于是这个大小为24B的pool就成为碎片需要挂在某一个链表上24 / 8 - 1 2号链表所以把这个pool余额挂在list #2, 然后调用malloc分配一大块
72 x 20 x 2 RoundUP(9688 4) 3488B , 在实验过程中把系统heap大小设置为10000前面已经累计分配了9688B因此无法满足本次内存分配。
alloc从手中资源取最接近72B的大小回填pool这里最接近的是80B(9号链表有1个空的可用)然后从80B中切72B给容器pool剩下80 - 72 8B。 容器再申请72B,list #8没有区块可用pool余量为8不足以供应1个先将pool余额挂在list #0上然后想要调用malloc分配72 x 20 x 2 RoundUP(9688 4) 3488B的空间依然无法满足分配。
于是alloc从手中资源取最接近72B的88Blist #10回填pool,因为上面的80Blist #9已经用完了从88B中切出72B返回给容器pool余额88 - 72 16B。 新的容器申请120B应该挂在几号链表呢120 / 8 - 1 14号链表同样的pool供应不足先将上面的16B挂在1号链表上再想要malloc分配一大块也分配不出无法满足需求。
于是alloc从手中资源中取最接近120B的区块回填pool但是14号链表和15号链表都是空的于是无法分配。 检讨
但是system heap大小为10000累计分配的总共为9688还剩下312B可用这部分内存不可以分配了吗
另外一个问题上图中白色区块都是可用资源能不能将小区块合并为大区块分配给客户呢合并技术难度极高。 27 G2.9 std::alloc源码剖析上
GNU C2.9 分配器的设计分为两级分配器分别是第一级分配器和第二级分配器其中第一级分配器不重要主要模拟new handler的作用处理一下内存分配的情况。下图便是第一级分配器的代码。
第一级分配器的代码1侯捷老师没讲。 第一级分配器的代码2侯捷老师没讲。 第一级分配器的代码3侯捷老师没讲。 现在是第二级分配器的介绍
ROUND_UP是将分配的大小变成8的倍数
size_t ROUND_UP(size_t bytes) {return (((bytes) __ALIGN-1) ~(__ALIGN - 1));
}FREELIST_INDEX的作用
size_t FREELIST_INDEX(size_t bytes) {return (((bytes) __ALIGN-1)/__ALIGN - 1);
}这个函数的作用是根据bytes大小指定到是哪个链表。不同的bytes分配到上面16个链表之一。
下面几个变量的作用
char* start_free 0; // 指向战备池pool的头
char* end_free 0; // 指向战备池pool的尾
size_t heap_size 0; // 累计分配大小重要的两个函数allocate和deallocate allocate
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) { // 大于128B交给第一级分配器来分配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)); // 链表充值从pool中去拿区块链表有了可用区块return r;}// 指针指向下一个可用区块*my_free_list result-free_list_link;return (result);
}辅助理解allocate的图 deallocate将指针p指向的空间回收到单向链表中
下面的free_list_link就是next指针
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) { // 大于128B改用第一级分配器进行回收malloc_deallocate(p, n);return;}// 回收过来的p指针指向的区块挂在单向链表的头my_free_list free_list FREELIST_INDEX(n); // 指向16个链表中的一个比如list #6,如下图所示q-free_list_link *my_free_list; // q的next指向单向链表的头就是list #6指向的具体区块的单向链表*my_free_list q; // my_free_list重新指向新的单向链表q因为头指针被换成新的了
}辅助理解deallocate的图 28 G2.9 std::alloc源码剖析中
chunk_alloc函数 主要作用是分配一大块内存。
做法要先看战备池pool看可以分配多少个小区块如果存在碎片也要处理。如果pool是空的还需要调用malloc给pool分配内存。
下面是具体的逻辑
第一张ppt展示3大块逻辑if else
首先看pool空间满足20个区块的需求其次是看pool空间只能满足1到19个区块的需求最后是pool不能满足1块pool碎片或者pool空间为0. 下面的ppt展示的是对3的处理具体调用malloc分配内存或者是往更大区块的链表请求支援分配一个区块。 chunk_alloc的源代码给予了清晰的注解根据侯捷老师的讲解
//----------------------------------------------
// 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;// 调用chunk_alloc的时候nobjs为20所以默认total_bytes为20个区块的大小size_t total_bytes size * (*nobjs); //原 nobjs 改為 (*nobjs)size_t bytes_left end_free - start_free; // pool中剩余的字节个数if (bytes_left total_bytes) { // 1. pool空间足以满足20块需求result start_free;start_free total_bytes; // 调整pool水位下降战备池pool变小return(result);} else if (bytes_left size) { // 2. pool空间只能满足1个区块的需求但不足20块*nobjs bytes_left / size; //原 nobjs 改為 (*nobjs) // 改变需求数看看可以切成几个区块total_bytes size * (*nobjs); //原 nobjs 改為 (*nobjs) // 改变需求总量result start_free;start_free total_bytes;return(result);} else { // 3. pool空间不足以满足1块需求pool空间可能是碎片也可能表示pool大小为0size_t bytes_to_get // 需要请求的一大块的大小2 * total_bytes ROUND_UP(heap_size 4);// Try to make use of the left-over piece.// pool池的碎片挂到对应大小的链表上if (bytes_left 0) {obj* volatile *my_free_list // 找出应转移到第#号链表free_list FREELIST_INDEX(bytes_left);// 将pool空间编入第#号链表next指针指向链表的头节点编入链表的第一个节点((obj*)start_free)-free_list_link *my_free_list;*my_free_list (obj*)start_free;}// 上面处理完pool的碎片pool为空开始用malloc为pool分配内存start_free (char*)malloc(bytes_to_get); // pool的起点if (0 start_free) { // 分配失败从free list中找区块向右边更大的区块去找int i;obj* volatile *my_free_list, *p;//Try to make do with what we have. That cant//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) { // 向右侧的链表去找区块例如88B96B104B 112B等等my_free_list free_list FREELIST_INDEX(i);p *my_free_list;if (0 ! p) { // 找到右边的list中的可用区块只释放一块给pool*my_free_list p - free_list_link;// start_free 和 end_free是战备池pool的头尾指针指向这一块空间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.} // if结束heap_size bytes_to_get; // 累计总分配量end_free start_free bytes_to_get; // 调整pool水位pool空间变大pool的终点return(chunk_alloc(size, nobjs)); //递归再调用一次}
}refill函数
当第n条链表来服务时却发现其为空此时就调用refill函数来创建链表分配区块。
下面的int nobjs 20;表示默认分配20个区块可能比20小。调用chunk_alloc函数来挖一大块内存。
当分配的区块为1时就直接交给客户我们上文用的容器。
chunk指的是一大块然后将其切割建立free list。refill的参数n表示一小个区块的大小。
refill是充值在一大块内存中切割成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 chunkresult (obj*)chunk;*my_free_list next_obj (obj*)(chunk n);for (i1; ; 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);
}在这段代码中next_obj 的计算是为了在内存块chunk上构建一个链表以形成一个自由链表free list。这个链表将被用于分配对象。让我们解释一下这行代码的目的
next_obj (obj*)((char*)next_obj n);next_obj 是一个指向当前空闲块的指针它一开始指向 chunk n即第一个可用的内存块。(char*)next_obj 将 next_obj 强制类型转换为 char* 类型这是因为我们希望按字节递增而不是按对象递增。((char*)next_obj n) 表示将指针移动到下一个内存块的起始位置即当前内存块的末尾加上一个对象的大小 n。(obj*)((char*)next_obj n) 将移动后的指针重新转换为 obj* 类型以便正确指向下一个空闲块的起始位置。
这样通过不断地按对象大小 n 的步长在内存块上移动构建了一个包含多个空闲块的链表。这个链表可以有效地用于分配对象。这种处理方式是为了确保链表中相邻的空闲块之间的间隔是 n 字节从而满足对象的对齐需求。
在上述代码中for 循环的第二个条件 ; 是一个空语句表示没有额外的条件来控制循环的执行。这意味着 for 循环会一直执行直到执行到 break 语句为止。
在这个具体的代码中循环的目的是为了在内存块上构建一个链表将多个空闲块连接在一起。循环体中的 if 语句用于判断是否已经遍历了 nobjs-1 个空闲块。如果是则最后一个空闲块的 free_list_link 设置为 0表示链表的结束。此时break 语句被执行跳出循环。
因此循环终止的条件是遍历了 nobjs-1 个空闲块确保链表的正确构建并在最后一个空闲块处设置了结束标志。循环的终止是由 break 语句触发的而不是由循环条件控制的。
29 G2.9 std::alloc源码剖析下
分析chunk_alloc函数本笔记将其放到了28 G2.9 std::alloc源码剖析中进行。
具体一些数据的初始定义 30 G2.9 std::alloc观念大整理
alloc观念大整理
listFoo c;
c.push_back(Foo(1)); // Foo(1)临时对象创建在栈stack中
//容器c使用alloc分配空间看16条链表中哪一条可以提供区块分配给它。所以它不带cookieFoo* p new Foo(2); // 采用new创建在heap中
// new是调用operator new底层是调用malloc它带有cookie
c.push_back(*p); // 容器c push_back的时候不带cookie
delete p; GNU C2.9的alloc批斗大会
需要学习的地方
比较判断的时候把具体的值写在前面防止出现将写成赋值的情况。
if(0 start_free)
if(0 ! p)
if(1 nobjs) 不好的地方
变量定义的地方不要和使用的地方间隔太远尤其是指针的使用。
第一级分配器使用的一个函数炫技没有人看得懂
void (*set_malloc_handler(void (*f)()))()
{ //類似 C 的 set_new_handler().void (*old)() oom_handler;oom_handler f;return(old);
}等价于
typedef void (*H)();
H set_malloc_handler(H f);还有deallocate的时候并没有free掉这是由设计的先天缺陷造成的。 31 G4.9 pull allocator运行观察
在GNU C4.9版本下的测试由于2.9版本分配内存都是调用malloc无法重载即无法接管到我们用户手中无法记录总分配量和总释放量。而在4.9版本中它的内存分配动作是调用operator new这样我们就可以接管operator new对其进行重载。 下面测试两个分配器使用情况分别对list容器进行100万次分配。
由于GNU C4.9版本标准分配器是allocator并不是2.9版本alloc所以容器客户分配内存的时候每个元素100万个都带cookie每个cookie占8B。这个如下图右侧所示。
下图左侧使用4.9版本好的分配器__pool_alloc这个是2.9版本的alloc显示分配的次数timesNew为122次调用malloc的次数这比右侧标准分配器好上不少。 后记
截至2024年1月11日19点39分完成《C内存管理》第二讲allocator的学习主要涉及GNU C2.9版本alloc分配器的具体实现与源码剖析。功力提升不少希望更进一步。
