侯捷内存管理学习笔记

第一章节 primitives

零.new和delete概述

C++中的new和delete是用于动态内存分配和释放的操作符，它们的底层机制和工作原理相对复杂，但也可以简单清晰地解释。

new的底层机制和工作原理

  1. 内存分配：
    • 当使用new操作符时，它首先会调用底层的内存分配函数（如operator new），这个函数通常是对malloc的封装。malloc会从堆中分配足够的内存空间。
    • 如果内存分配失败，operator new会抛出一个std::bad_alloc异常，而不是像malloc那样返回NULL。
  2. 对象构造：
    • 内存分配成功后，new会调用对象的构造函数来初始化分配的内存区域。对于内置类型（如int、char等），这一步可能只是简单地设置值；而对于自定义类型，则会调用其构造函数。
  3. 返回指针：
    • 最后，new返回一个指向已分配并初始化对象的指针。

delete的底层机制和工作原理

  1. 对象析构：
    • 当使用delete操作符时，它首先会调用对象的析构函数来清理对象中的资源。这一步对于自定义类型尤其重要，因为析构函数通常包含释放动态分配资源（如内存、文件句柄等）的代码。
  2. 内存释放：
    • 析构函数调用完成后，delete会调用底层的内存释放函数（如operator delete），这个函数通常是对free的封装。free会将之前分配的内存空间归还给堆管理器。
  3. 指针置空（可选）：
    • 虽然delete本身不会将指针置为空（nullptr），但这是一个良好的编程习惯。在释放内存后，将指针置为空可以避免悬空指针（dangling pointer）问题，即指针仍然指向已释放的内存区域。

注意事项

  • 匹配使用：确保使用new分配的内存使用delete释放，使用new[]分配的内存使用delete[]释放。不匹配使用会导致未定义行为。
  • 不要重复释放：不要对同一个内存块调用delete（或delete[]）多次。
  • 避免使用已释放的内存：一旦内存被delete释放，就不要再尝试访问它。

在C++内存分配当中分为四个阶层：

  1.调用容器
  2.使用new关键词
  3.直接调用malloc和free
  4.调用与系统绑定的内存分配函数

这四个阶层有层层包含的关系：
在这里插入图片描述
从::operateor new()开始，可以进行重载。同理，delete也可以进行重载。

new会调用operator new，然后operator new调用malloc进行内存分配

在第四个，你可以自己设计一个分配器搭配一个容器。

在这里插入图片描述

一、new()和delete()

1. new()

在这里插入图片描述
new关键词相当于进行两个步骤：

  1.调用operator new，分配所创建对象需要的内存（其内部就是对malloc()的封装）
  2.调用对象的构造函数

如果某个步骤发生错误，则抛出异常。

注意：在一些版本中，只有编译器可以直接调用构造函数，如果在程序中自己调用则会出错。

1
2
3
4
5
A* pA = new A(1);//正确
	
pA->A::A(3);//错误
	
A::A(5);//错误

2.delete()

在这里插入图片描述
相应的，delete关键词也相当于两个步骤：

  1.先对需要delete的对象进行析构，调用其析构函数
  2.再释放该对象所使用的内存空间（内部是封装了free()函数）

3.new[ ]和delete[ ]

在这里插入图片描述
  使用new[ ]时，顺序分配对象所需空间，指针指向第一个内存空间，但不调用构造函数进行初始化（如果对象内不包含指针成员则无影响，包含则有影响）,后续可以通过指针对各个对象进行初始化。同时在空间开头会有一个cookie，记录了这个空间共有几个对象。
  使用delete[ ]时会读取cookie，倒序析构对象，并释放对应的空间；如果直接使用delete则不会读取cookie，会导致空间错位，程序报错，所以new[ ]必须要跟delet[]对应。
在这里插入图片描述

4.placement new（定位new）

定位new（Placement new）是C++中的一个高级特性，它允许在已分配的内存上构造对象，而不会进行新的内存分配。以下是对定位new的详细解释：

一、定义与原理

  • 定义：定位new就是在已分配好的内存空间中调用构造函数对象进行初始化。它不会申请新的内存空间，而是利用已经分配好的空间来构造对象。
  • 原理：使用定位new时，程序员需要指定一个已经分配好的内存区域，然后在这个区域中调用对象的构造函数来构造对象。由于对象的空间是预先分配好的，因此定位new不会进行额外的内存分配操作。

二、使用方法

定位new的使用语法通常如下：

1
2
3
cpp复制代码

new (placement_address) type (initializer_list);
  • placement_address：这是一个指向已分配内存的指针，表示对象将要被构造的位置。
  • type：这是要构造的对象的类型。
  • initializer_list：这是传递给对象构造函数的初始化列表（可选）。

例如，假设有一个已经分配好的内存区域mem，并且想要在这个区域中构造一个类型为A的对象，可以使用以下代码：

1
2
3
cpp复制代码

A* p = new (mem) A;

此时，指针p和数组名mem指向同一片存储区，对象A将在mem指向的内存区域中被构造。

三、注意事项

  • 内存管理：由于定位new不会进行内存分配，因此程序员需要手动管理内存。在对象不再需要时，需要显式地调用析构函数来释放对象占用的内存。
  • 对象生命周期：使用定位new构造的对象，其生命周期由程序员负责管理。程序员需要确保在对象不再需要时正确地调用析构函数，以避免内存泄漏和悬空指针等问题。
  • 使用场景：定位new通常用于内存池或自定义内存管理等场景，在这些场景中，程序员需要精确地控制内存的使用和对象的构造与析构。

四、示例

以下是一个使用定位new的示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <new> // 包含定位new所需的头文件  
#include <iostream>  
  
class A {  
public:  
    A() { std::cout << "A's constructor called" << std::endl; }  
    ~A() { std::cout << "A's destructor called" << std::endl; }  
};  
  
int main() {  
    char mem[sizeof(A)]; // 分配一块足够大的内存区域来存储对象A  
    A* p = new (mem) A; // 在指定的内存区域中构造对象A  
    // ... 使用对象p ...  
    p->~A(); // 显式地调用析构函数来释放对象占用的内存  
    return 0;  
}

在这个示例中，我们首先分配了一块足够大的内存区域mem来存储对象A，然后使用定位new在mem指向的内存区域中构造了一个对象A。最后，我们显式地调用了析构函数来释放对象占用的内存。

综上所述，定位new是C++中的一个高级特性，它允许在已分配的内存上构造对象而不会进行新的内存分配。在使用时需要谨慎处理内存管理和对象生命周期的问题以确保程序的正确性和稳定性。

课程中：

在这里插入图片描述
  形式就相当于new ( p ) ,是将一块已经分配好了的内存用于构建对象，new则是当场分配一块内存用于构建对象，并没有特定的placement delete。

其中buf是已经分配好的内存

上面第二行这一行会被编译器解释为这三行

image-20241022174140625

1.给一块已经分配好的内存，这一步其实什么都不会做，因为内存已经分配好了

2.转型

3.调用对象的构造函数

其实就相当于调用了一次构造函数

二、重载

1.new()和delete()

  new()表达式本身不可重载，表示operator new()，但operator new()可以重载，分为全局和类内，通常重载类内的。
在这里插入图片描述
  类内对operator new()和operator delete()进行重载，operator new()重载的第一参数必须是size_t，其大小足以保证存储内存中对象的大小，否则将抛出异常。
在这里插入图片描述
  如果在创建对象时，直接调用new()和delete()，则调用的是类内重载的new()和delete()，是编译器调用的，并且重载的new和delete这两个函数一定得是静态的，因为调用的时候还没有实例对象
在这里插入图片描述
  如果调用::new()和::delete()，则调用的是全局的new()和delete()
在这里插入图片描述
  注意：

这里说的是placement operator delete不是operator delete

前者是下图说的抛异常的时候用，后者是和operator new配对的

在这里插入图片描述

很好的例子：

这是我们平常用的string，它的new会多出来一个extra，所以要重载

image-20241022201812108

重载全局的operator new和operator delete的接口的格式

new一定要写参数size，delete写ptr指针，而size可写可不写是一个选项

image-20241023221714126

2.allocator()和deallocator()

  进行类内operator new()和operator delete()的重载，主要是为了减少::operator new()和::operator delete()的调用。因为::operator new()是对malloc()适配，每调用一次malloc(),就会产生头尾两个cookie共8个字节，既造成了空间浪费，速度上也更慢。

  但对每一个不同的类进行重载，并且每次重载的内容都差不多，会造成大量重复劳动，会有很多的重复代码，所以设计一个概念把之前重载中共同的部分抽象出来，作为一个类来使用，即为allocator()和deallocator()。

  设计一个allocator的类，在类里面定义allocator()和deallocator()。allocator()使用内存池模式，每次申请一大块内存，然后将这块内存切割小块，大小等同于对象的大小，并串成一个链表。这样只有在申请一大块内存的时候会调用malloc()，生成两个cookie，创建对象时不使用malloc()，而是从链表中取出一块分给对象，调用deallocator()也不将释放的内存free()给系统，而且将这块内存重新插入链表顶端。

重载operator new和delete的版本

image-20241022202556920

测试结果会有cookie的空间占用

现在这样就不需要上面又是struct又是union的

在这里插入图片描述

static allocator（用allocator的版本）

对象需要重载new和delete时，直接在类内创建一个allocator对象，调用allocator的类方法，即上面那张图。

使用static使得每个类有一个自己的内存池，进行内存管理，而不是一个对象一个内存池

测试结果没有cookie的空间占用

在这里插入图片描述

application class的所有内存分配的细节都让allocator去操心，我们的工作是让application class正常工作

使用宏把重复的代码定义一下来使用的版本

image-20241022205628521

测试结果没有cookie的空间占用，和static版本相同

技术的演进

new delete针对一个对象->static alloctor针对一个类->globa allocator针对一个标准库，里面有16个链表（static alloctor只有一个链表）

3.new_handler

  在调用内存失败，抛出异常之前，会调用一个由自己设计的一个补救函数，即new_handler()。若new_handler()中没有abort()或者exit()，或者没有让更多内存可用，则会一直调用new_handler()直至满足内存需求。
image-20241022210612589

1
2
3
//调用：
//在main中写
set_new_handler(自己写的补救函数名);

注：

new delete的重载不可以是=default的，但可以是=delete的

第二章节 std::allocator（为小区块服务）

西北有高楼，上与浮云齐。

在工业级别，可能会用malloc上百万次，即使是有内存池的存在，cookie占用的额外内存还是不容小觑，同时malloc也挺慢的，所以这部分的目标就是去掉malloc，使得效率提高，空间率精简

去除cookie的先决条件是申请的块是一样的大小，如果块有大有小那就不能去掉，因为要标识块的大小，如果是一样的大小，那就可以去掉。而一个类的对象实例大小肯定是一样的。

1.占用内存的计算方式

image-20241022215936337

0xC是block size,是咱们申请分配的内存大小，实际给咱的是计算后的结果即0x40

2.不同版本的allocator设计

1. VC6、BC5、G2.9和G4.9的allocator

VC6的标准分配器

这个编译器的allocator没有任何特殊设计，单纯是调用malloc和free，分配是以对象元素为单位。

在这里插入图片描述

BC5的标准分配器

和VC6相同，没有任何特殊设计。

在这里插入图片描述

GNU4.9的标准分配器

同样，没有任何特殊设计，和VC6，BC5一样。这个文件中已经说明，这个分配器没有用，容器的分配器不使用它！

在这里插入图片描述

GUN 2.9d的标准分配器

同样，没有任何特殊设计

image-20241023093804151

这些版本下的allocator()本质上都是malloc()
在这里插入图片描述
在这些版本下，所有的容器都是直接调用allocator(),即第二个模板参数都是allocator。
在这里插入图片描述

2. G2.9的alloc流程解析

这个和G4.9 pool allocator就消除了大部分cookie的额外空间，因为只要用malloc就会有cookie，所以不可能完全没有，只是尽可能去回收已经分配过得内存来减少malloc从而减少cookie。两者实现方式差不多所以看2.9版的

1.内存池配置器概述：

  1. 一级配置器：直接对malloc和free（或new和delete）进行封装，提供预申请内存接口，减少内存分配的上下文切换。当申请的内存区块大于一定阈值（如128bytes）时，一级配置器会处理这些大块内存的分配和释放。
  2. 二级配置器：是真正的内存池实现，主要针对小块内存的频繁申请和释放。它采用内存块分级管理策略，将内存划分为多个不同大小的区块（如8, 16, 24, …, 120, 128 bytes等），并使用自由链表（free-lists）来管理这些区块。当需要小块内存时，二级配置器会尝试从自由链表中找到合适大小的区块进行分配；当释放小块内存时，也会将其回收到对应的自由链表中。

2.具体流程

在这里插入图片描述
  原始的allocator()只维护一个内存链表，链表中每个节点的内存块大小根据创建allocator的对象来决定。现在的alloc通过free-list维护16条链表,节点的内存块大小从8byte到128byte共16种。

  内存申请过程：程序申请一块32bytes大小的空间，alloc会先通过malloc申请一块32*40bytes的空间，分一块给程序，32*19挂到free-list上维护为一条大小为32bytes，个数为19的链表.剩下32*20交给备用空间，暂时不进行处理。若程序继续要申请一块64bytes大小的空间，则直接将刚刚剩余的32*20的空间挂到free-list变为64*10的链表，并把第一个节点内的内存分配给程序。

下一次申请就没有备用空间了，就得重新和malloc申请

PS：加入追加量概念和每次除以16都是经验所得，不用太纠结

注意点：
  1.每一个区块采用union结构，前四个字节表示为指向下一个区块的指针，好处是减少了额外的指针开销。有元素的时候就放元素了，用完了归还的时候又变成了指针。
  2.每条链表的长度为1-20，即使空间足够，长度也不会超过20。
  3.申请的空间如果很大，那还是会到一级配置器调用malloc。若当前需要申请一块104bytes的空间，而备用空间只剩下80bytes，则先将备用空间的80bytes挂到#9号链表下，再进行内存申请，若空间剩余不为8的倍数，则向上补齐为8的倍数再放入链表。
  4.若当前要申请一块72bytes的空间，备用空间不够，系统内存也不够无法通过malloc()额外申请。则将80bytes的链表（即最靠近72bytes，且比72bytes大的链表）中切下一块放入备用空间，再从备用空间中切下72bytes，交给程序。若80bytes的链表也没有空间，则依次向后继续找，若找到128bytes仍然没有足够的空间，则报错内存分配失败。
  5.备用空间是通过一头一尾两个指针来界定。
在这里插入图片描述
  6.当程序将空间返回时，若大于128bytes，直接通过一级配置器返还给系统，还是会调用free来回收，若小于128bytes，则直接安插到free-list对应链表的头部。
在这里插入图片描述
  7.若程序申请80bytes的内存空间，链表上为空，则先调用备用空间。若备用空间能分配一块以上但不足20块的内存大小，比如备用空间还有248，那就分成3块，给程序一块，然后两块空余，这三块都挂在9号，备用空间只剩8这样子。若备用空间内存足够，则将一块内存分配给程序，剩余19块内存挂载到链表上，并通过指针相连。
在这里插入图片描述
  8.若程序申请80bytes的内存空间，链表上为空且备用空间不足，则free-list会调用refill()函数来填充链表，进行malloc()操作。若系统空间只能分配一块80bytes，则直接将内存分配给程序，不挂到链表上；若系统空间内存足够，则将一块内存分配给程序，剩余19块内存挂载到链表上，并通过指针相连。
在这里插入图片描述
  9.为什么当备用空间不足，且系统空间不足以申请20块内存时，要从更大的内存块链表切下一块放入备用空间，而不是向系统申请一块内存？
  因为链表上挂着的内存，本质上都是由alloc维护，只要是申请过并且分配过的（很大的一块空间但是内存池不知道这个到底有多大，因为链表很长，所以就都拿在手中)就不还给操作系统，如果这样做就相当于不使用alloc现有的内存而去向系统继续申请额外内存，后果是当前程序占有的内存越来越大，对于多任务系统是一种灾难。尽可能使用已经拥有的内存！！！

3.缺陷以及消除cookie后的测试结果

缺陷：

比如3号一开始的指针，这个是一开始用malloc分配的有cookie，在后面分配的时候，没有变量去保存这个指针，所以也导致归还不了内存，在第四讲中会有更好的东西来弥补它

image-20241023110511895

测试结果：

都是一百万个对象

左边用了内存池，分配内存的行为malloc只调用了122次，而右边没有用的调用了一百万次malloc，一个cookie是8字节，相当于多用了8百万字节的额外空间，前面只是122*8个字节而已。

而上面的1675283是new的调用的次数，其实这个没有影响，因为内存池多了一层管理，而右边没人管理，所以左边会比右边多一些new和delete的操作，而这里面的delete其实没办法计数的。

image-20241023111736164

第三章节 malloc/free

先通过概述了解一下大致的工作流程再去看源代码会清晰很多

1.malloc概述

C++中的malloc函数是一个用于动态内存分配的函数，其底层机制和工作原理相对复杂但可以通过以下简单清晰的解释来理解。

底层机制

malloc函数在C++（以及C语言）中用于从堆（heap）中分配一块指定大小的内存空间，并返回该内存空间的起始地址。堆是操作系统管理的一块内存区域，用于动态分配内存。

malloc函数的底层实现依赖于操作系统的内存管理机制。在Linux系统中，malloc通常通过维护一个空闲链表来管理可用的内存块。这个链表将可用的内存块连接起来，当malloc被调用时，它会遍历这个链表以找到第一个足够大的空闲块来满足请求。

工作原理

  1. 内存分配：
    • 当malloc被调用时，它首先计算所需内存的大小（包括一些额外的空间用于管理，如链表指针等）。
    • 然后，它遍历空闲链表以找到第一个足够大的空闲块。
    • 如果找到这样的块，malloc会将其拆分成两部分：一部分是用户请求的大小，另一部分是剩余的大小（如果有的话），并将剩余部分重新链接到空闲链表中。
    • 最后，malloc返回用户请求大小的内存块的起始地址。
  2. 内存释放：
    • 当使用完malloc分配的内存后，应使用free函数来释放它。
    • free函数会接收一个指向要释放内存的指针，并将这块内存重新链接到空闲链表中。
  3. 内存碎片整理：
    • 随着多次的malloc和free调用，空闲链表可能会被切成很多小的内存片段（内存碎片）。
    • 当用户请求一块较大的内存空间时，可能会出现空闲链表中没有满足要求的片段的情况。
    • 在这种情况下，malloc可能会请求延时，并开始检查空闲链表上的各个内存片段，尝试将它们合并成较大的内存块以满足请求。
  4. 系统调用：
    • 对于小块内存分配（通常小于128KB），malloc可能会使用brk()系统调用来调整堆的顶部指针，从而分配新的内存空间。
    • 对于大块内存分配（通常大于128KB），malloc可能会使用mmap()系统调用来在文件映射区域分配内存。

注意事项

  • malloc分配的内存空间是未初始化的，可能包含任意值，因此在使用前需要对其进行初始化。
  • 使用完毕后，应通过调用free函数来释放malloc分配的内存空间，以避免内存泄漏。
  • 在多线程环境下，使用malloc分配内存时需要注意线程安全性。

free 函数在 C++（以及 C 语言）中用于释放之前通过 malloc、calloc 或 realloc 等函数动态分配的内存空间。其底层机制和工作原理可以简单而清晰地解释如下：

2.free概述

底层机制

free 函数的底层实现依赖于操作系统的内存管理机制，特别是与堆（heap）管理相关的部分。在大多数操作系统中，堆是一块由操作系统管理的内存区域，用于满足程序的动态内存分配需求。

当 free 被调用时，它接收一个指向要释放内存的指针。这个指针必须是指向之前通过 malloc、calloc 或 realloc 分配的内存块的起始地址。

工作原理

  1. 验证指针
    • free 首先会检查传入的指针是否为 NULL。如果是，free 会立即返回而不执行任何操作，因为释放一个空指针是安全的。
    • 如果指针不是 NULL，free 会继续验证该指针是否指向一个有效的、之前分配的内存块。这通常通过检查指针是否在堆的范围内以及是否指向一个已知的内存块头（包含管理信息，如大小、状态等）来完成。
  2. 更新内存块头
    • 一旦验证了指针的有效性，free 会更新该内存块头的信息，将其标记为“空闲”或“已释放”。
  3. 合并内存块
    • 为了减少内存碎片，free 会尝试将刚刚释放的内存块与其相邻的空闲内存块合并。这通常涉及更新内存块头中的大小和链表指针信息。
    • 如果合并成功，新的空闲内存块将包含合并前两块内存的总大小。
  4. 维护空闲链表
    • 在许多实现中，空闲的内存块会被组织成一个链表（或类似的数据结构），以便快速查找和分配。
    • free 会将刚刚释放（或合并后）的内存块插入到这个链表中，或者更新链表中现有节点的信息。
  5. 系统调用（可选）
    • 在某些情况下，如果释放的内存块非常大或者达到了某个阈值，free 可能会通过系统调用（如 munmap）将内存归还给操作系统。
    • 然而，这通常是可选的，并且取决于具体的内存分配器实现和操作系统的行为。
  6. 返回
    • 最后，free 函数返回，不再对该内存块有任何引用或控制。

注意事项

  • 不要重复释放：不要对同一个内存块调用 free 多次，这会导致未定义行为，可能包括程序崩溃或数据损坏。
  • 避免使用已释放的内存：一旦内存被 free 释放，就不要再尝试访问它。这可能会导致程序崩溃或安全漏洞。
  • 匹配分配和释放：确保使用与分配内存时相同的函数（或函数族）来释放内存。例如，如果内存是通过 malloc 分配的，那么应该使用 free 来释放它；如果内存是通过 new 分配的，那么应该使用 delete（或 delete[] 对于数组）来释放它。

3.VC6的malloc设计

实际上malloc也是内存池的思想，malloc本质上的速度也并不慢

  这是VC6版本下的malloc程序设计，从下往上一次执行。在该版本中有SBH（small block heap）的设计,即对于小块内存会采用特殊的分配方式。
在这里插入图片描述

SBH首次分配内存详细步骤

在这里插入图片描述

总体的malloc如上图。总的来说，就是为了添加debug信息，申请具体的内存，方面内存管理。

  1. _heap_init()做的事是分配16个头，16个头的数据结构如下，使用这个数据结构使得每个header能够管理1M的内存，1M内存能够快速分配，快速回收。一个header包括两个指针，一个指针指向自己管理的内存，一个指针指向管理内存中心。详细见步骤6。这些bit用于存放链表的状态，是否挂载上page。

在这里插入图片描述

2._ioinit()负责第一次分配内存：根据是不是debug的模式，调用不同的内存分配策略。debug直接调用malloc，非debug则给程序分配256字节的内存

img

3._heap_alloc_dbg()负责在debug模式下，加上一些调试信息（debug header），这些调试信息就是下面的数据结构_CrtMemBlockHeader。这些调试信息包括：调试文件名，行号，数据大小，间隔符。绿色的地方就是填充我们最后要申请分配的内存。被分配的内存会被指针串起来形成一条链表。

gap就是把绿色部分包住，不让用户写的超过这个范围(间隔符)

在这里插入图片描述

image-20241023152711137

4._heap-alloc_base()根据申请的大小来判断（是否大于1016，为什么是1016？因为要留给cookie八字节的内存）是要自己提供服务还是交由操作系统来服务。

5.__sbh_alloc_block()用于字节对齐，加首尾cookie。处理完之后的内存块如下图右上角的图。cookie利用最后的一个bit来代表这个内存块是否被分配出去，1表示已分配，0表示未分配。

在这里插入图片描述

6.__sbh_alloc_new_region()：内存管理中心数据结构就是tagRegion，管理区块是不是被分配，在不在内存分配链表上。为了管理好1M的内存空间，花了16K的内存（tagRegion数据结构）。

在这里插入图片描述

7.__sbh_alloc_new_group()：4K一个page。一个header管理1M内存，这个1M内存会被分成32块（组，每个组由32对指针组成，即双向链表），32块分别由内存管理中心的数据结构来管理，每一个块又会被分成8个page，一个page占4K，使用链表将这些page连起来，连起来之后首尾接到绿箭头指向的双向链表中。完成这些工作之后，申请一块内存，得到内存，初始化，内存申请就成功了。
在这里插入图片描述

8.最后将__sbh_alloc_new_region组好的内存填充到组中去。层层return会让用户拿到指向绿色开头的指针。

在这里插入图片描述

SBH第二（n）次分配内存

在一个page上继续进行切分，当前page不够用，去其他page找。header负责维护的状态应该发生变化。

在这里插入图片描述

内存释放

将一个内存块的cookie中的状态置为未分配，将内存变为两个指针，指向负责管理内存的链表，header中的bit也发生变化，表示未分配。

回收相邻的内存。应该有个合并策略（这就是为什么要有下cookie的原因），要不然会出现内存碎片的问题。

在这里插入图片描述

free( p )

p属于哪个header？
p属于哪个group？
p属于哪个free-list？

内存分配总结

上述的分配策略，总的思想是一个分段管理。至于为什么有16个头，32个组，1个头管理1M内存，这些都是经验值，有利于操作系统。

全回收的动作会被延缓，并不会只要归还所有内存之后就把这么多段的内存整合还给操作体统（defer）。当第二个全回收出现的时候才会把内存归还操作系统。

第四章节 loki::allocator

0.概述

loki::allocator 是 Loki 库中的一个内存分配器组件，但需要注意的是，Loki 库并非 C++ 标准库的一部分，而是一个提供设计模式、编程惯用法等实现的第三方库。由于 Loki 库的具体实现和版本可能有所不同，以下对 loki::allocator 的底层原理和工作机制的描述将基于一般性的理解和假设。

底层原理

loki::allocator 的底层原理主要涉及到内存的分配和释放策略，旨在优化性能和减少内存碎片。它可能采用了以下一些技术：

  1. 内存池（Memory Pool）
    • 内存池是一种预先分配大块内存并在需要时从中分配小块内存的技术。loki::allocator 可能实现了一个或多个内存池，用于存储不同类型的对象。
    • 内存池的好处是减少了向操作系统请求内存的次数，从而提高了性能。此外，它还允许分配器更好地控制内存碎片。
  2. 对象对齐（Object Alignment）
    • 为了满足特定硬件或编译器的要求，loki::allocator 可能支持对象对齐。这意味着对象在内存中的位置将满足特定的对齐条件。
    • 对齐通常是为了提高内存访问速度或满足特定数据结构的布局要求。
  3. 自定义分配策略
    • loki::allocator 可能允许用户定义自己的分配策略，如分配大小、对齐要求、是否使用内存池等。
    • 这提供了灵活性，使得分配器可以根据特定的应用场景进行优化。
  4. 缓存友好性（Cache Friendliness）
    • 为了提高内存访问效率，loki::allocator 可能会尝试将对象分配在缓存友好的位置。
    • 这可能涉及到对象的布局、内存池的组织方式以及分配策略的选择。

工作机制

loki::allocator 的工作机制通常包括以下几个步骤：

  1. 内存分配
    • 当需要分配内存时，loki::allocator 首先会检查内存池中是否有足够的空闲空间。
    • 如果有，它会从内存池中分配一块适当大小的内存给对象。
    • 如果没有足够的空闲空间，它可能会向操作系统请求更多的内存，并扩展内存池。
  2. 对象构造
    • 在分配内存之后，loki::allocator 可能会调用对象的构造函数来初始化对象（对于类类型对象而言）。
    • 这一步是可选的，取决于分配器的设计和使用场景。
  3. 内存释放
    • 当对象不再需要时，loki::allocator 会负责释放对象所占用的内存。
    • 它可能会将这块内存归还给内存池，以便将来重新分配。
    • 如果内存池已满或不再需要，它可能会将部分或全部内存归还给操作系统。
  4. 对象析构
    • 在释放内存之前，loki::allocator 可能会调用对象的析构函数来清理对象（对于类类型对象而言）。
    • 这一步同样是可选的，取决于分配器的设计和使用场景。

注意事项

  • 由于 loki::allocator 不是标准库的一部分，你需要确保你的项目中包含了 Loki 库，并且正确地配置了编译环境。
  • 在使用 loki::allocator 之前，你应该仔细阅读相关的文档和源代码，以了解它的具体实现和用法。
  • 考虑到 Loki 库的使用可能不太广泛，如果你在维护一个长期的项目或与其他开发者合作，使用标准库中的 std::allocator 或其他广泛使用的第三方库可能是更安全、更可维护的选择。

1、loki的allocator设计

0.总体上

loki::allocator由三个类构成，用户直接操纵SmallObjAllocator。

上面两个类都带有两个指针指向vector对象的类型

在这里插入图片描述

1. Chunk

（1）Chunk的结构和初始化

Chunk包含三个部分：一个指针和2个unsigned char。
在这里插入图片描述
  在chunk初始化时会申请一块内存，然后根据Blocksize将内存切成若干块，由一个指针指向该内存。然后遍历这些内存块，把每个内存块的第一个字节按顺序编号，用这种方式（类似索引）实现嵌入式指针的效果。firstAvailableBlock用于记录下一个可以分配的内存块编号，blocksAvailable_用于记录总共还剩多少个内存块可以分配。
在这里插入图片描述

（2）Chunk的内存分配过程

  找到firstAvailableBlock记录的可分配内存块，该编号为相对于内存开头的偏移量，这块内存的第一位记录的是下一块优先分配的内存编号，在给出这块内存之前，将firstAvailableBlock指针指向次优先级的内存块，同时blocksAvailable_的值-1。

就是图中的4->3（这个是索引，表示从开头到这块是第几块，3是第四块）就是数字3的块给出去了，如果程序还要继续申请内存那给出去的就会是索引号3，数字块2，再下一个就是索引号2，数字块1。每给出去一块可用的块数就会减一。

在这里插入图片描述

（3）Chunk的内存释放过程

回收的块号是回收指针减去头指针再除以块数得到的

  先将firstAvailableBlock写入返回内存块的第一位，即最高优先权的位置（在链表里面其实就是个头插法，只不过这里没有虚拟头结点罢了），再根据返回指针的位置，计算出当前内存块的具体位置编号，赋给firstAvailableBlock，最后将blocksAvailable_的值+1。
image-20241023195252839

所以就明白为什么顺序是乱的，因为分配出去的块的顺序和重新回收插入到头部的顺序大多数情况下都不会相同

2. FixedAllocator

（1）FixedAllocator的结构

  FixedAllocator包含一个vector< Chunk >，allocChunk指针指向的是上一个进行内存分配的chunk，deallocChunk指针指向的是上一个进行内存归还的chunk（根据经验设计的，局部性原理）。
在这里插入图片描述

（2）Allocator

  首先对allocChunk进行判断，若指针为空或者所指的chunk已经满了，则开始从头遍历chunk。
  若遍历结束没找到可用的chunk，则再尾部新增加一个chunk，将allocChunk指向新增的chunk，deallocChunk指向第一个chunk（因为vector可能会搬运move，move之后，原来的指针可能就失效了，所以要重新搞一个值，那索性就第一个好了）。
  若遍历过程中找到了可用的chunk，然后直接从该chunk进行内存分配，将allocChunk指向该chunk。还要标记一个哨兵，下次直接从这里开始找Chunk
在这里插入图片描述

（2）Deallocator

Deallocator函数进行两个操作，先找到可以归还内存的chunk，再进行chunk全回收判断。
在这里插入图片描述

① VicinityFind

  定义两个指针分别指向deallocChunk和deallocChunk + 1的chunk，然后从deallocChunk往front找，deallocChunk + 1往back找，交叉寻找（往上找一个chunk，往下找一个chunk），如果找到内存块所属chunk则进入chunk内存返还，若找不到则一直循环！（新版已经改了）
在这里插入图片描述

② DoDeallocator

  先调用Deallocator进行内存回收，回收完了进行判断，若当前chunk可用空间与初始状态不同，则说明还未全回收，直接跳出程序。若相同，则确认全回收，进行返还判断，分为三种情况：
  1.若全回收的chunk为vector的最后一块，并且前一块也是全回收的，则将最后一块chunk释放给系统。
  2.若全回收的chunk不为vector的最后一块，但最后一块chunk是全回收的，则将最后一块chunk释放给系统，当前chunk不释放。
在这里插入图片描述
在这里插入图片描述

3. SmallObjAllocator

  SmallObjAllocator是由一系列内存块大小不同的vector< Chunk >组成，主要功能是将程序的内存申请分配到合适大小的vector< Chunk >进行处理。
在这里插入图片描述
在这里插入图片描述

2、loki::allocator的特点

1.结构简单精简，多使用暴力遍历。
2.使用数组取代链表，索引取代指针的特殊实现。
3.有较为简单的chunk全回收判断，进而归还给系统。
4.有deferring(暂缓归还)功能。
5.本身是个allocator，用于分配不带有cookies的内存块，最适用于容器，但底层却通过vector实现，不太合理，它内部的vector用的分配器还是标准库的那一套而不是他自己这个，要用它自己这个得我们自己写容器的时候指明第二个参数是他这个分配器才行。

第五章节 other issues

就是介绍一下GUN的其他分配器，方便在各种情形下去使用

GNU4.9分配器

分配器各有各的优势。

1.new_allocator和malloc_allocator（最简单的）

new_allocator

实现出简单的operator new和operator delete，这个好处就是能够重载。

malloc_allocator

直接调用malloc和free，没有经过operator new / delete，所以没有重载的机会。

image-20241023203411232

2.智能型的分配器

array_allocator、debug_allocator、__mt_allocator、__pool_allocator、bitmap_allocator都是智能型

1.array_allocator

允许分配一个已知且固定大小（known and fixed size）的内存块，这些内存来自std::array对象。使用这个分配器，大小固定的容器（包括std::string）就不再需要调用operator new和operator delete。这就使我们能够使用STL abstractions，而无需在运行时造成混乱或增加开销。甚至在程序启动时也可以使用这种分配器。

其实就是用C++底部的静态的数组来供应内存，然后如果一开始就知道大小的话，这个就比较好用，速度也快。既不是new也不是malloc。

在这里插入图片描述

array_allocator的使用

image-20241023205844066

arrat_allocator并不会回收已经给出的内存空间。（不能回收其实没有啥用）

静态分配，不需要free。没啥用，因为不free，用过的空间不能再次使用了。

也可以将底部C++的数组换成标准库的array容器。

image-20241023210221463

2.debug_allocator

这是一个包装器（wrapper），可以包装在任何分配器（allocator）之上。它会将用户的请求量增加一些，然后由分配器进行响应，并使用那一小块额外的内存来存储大小信息。一旦deallocate()函数接收到一个指针，它就会检查大小信息，并使用assert()函数来确保匹配。

就是自己是加了点东西，然后分配的活一点不干都外包给它里面那个allocator。

多出来的_M_extra就是记录区块大小，就只是加了个大小，没什么用（不是我说的，是侯捷老师说的，但我也觉得没啥用）

在这里插入图片描述

3.三种使用内存池的分配器

下面的三种分配器实现都是内存池的思想，追求的是不要分配过多的cookie。

1.__pool_allocator

就是GNU2.9中的alloc，这里不再赘述。

2.__mt_allocator

多线程的内存分配器。

3.bitmap_allocator

是个bitmap index，用以索引至一个以2的指数倍成长的篮子

一个高效能的分配器，使用bit-map追踪被使用和未被使用的内存块。

image-20241023211037280

1.内存分配

关于blocks，supper-blocks，bitmap，mini-vector

在这里插入图片描述
1.上图是一个super block

bitmap用于存放后面的block是否被分配出去

use-count表示已经分配了多少个

2.__mini_vector是控制中心，用来管理后面的block，指向block的头尾

bitmap的变化方向和_M_start变化方向相反

start和finish是super block的空闲块的头和尾，end_of_storage指的是容量的尾巴(就那个会扩容两倍那个实际上的容量的尾巴，模仿标准库vector容器写的)

3.如果一个super block用光了，就会新起一个super block，控制中心mini_vector也会增长，而且能够分配的内存会翻倍，如下图：

在这里插入图片描述

用1表示还没分配的block，用0表示已经分配的block，前面的数字会标识还有几块空闲没有被分配的

4.这个vector的entries无限制，每个entry代表一种value type，不用的value type即使大小相同也不混用

就和一个类有一个分配器一样的，这里的entry代表的super block也是每个类型一个，不会混用

image-20241023212639506

2.内存回收

如果发生全回收，便会造成下一次分配的内存规模减半（它自己设计就是这样的，不用纠结）。图中64,128,256全部都回收，那下一次malloc分配的话就是给分配128个blocks。

下面是第一个64blocks的全回收

image-20241023213355765

全回收，使用另外一个__min_vector来登记（free list）全回收的super block。对于原来的两个指针，是用vector的erase来删除的，就相当于删掉了vector的0,1号元素。

问题1的答案其实是0号和2号都可以的。但是测出来是2号，这个是无所谓的。

问题2的答案是唯一的。因为要先用已经分配过得内存，这一点是好的。

发生全回收，则分配内存减半，如下图是三次全回收的情况：

在这里插入图片描述

右上角的_s_free_list就是登记全回收的super block的链表,释放的时候就看这里面哪个super block最长最大，就释放掉谁。

如果free list中已经有64个super block，下一次再free的的super block，直接delete。

如果要这时候要申请一个block，那就从_s_free_list里面恢复一个进行使用

4.这些分配器的使用

image-20241023214741499

image-20241023214815272