第一讲 primitive

1.1 内存分配的每一层面

1.1.1 C++应用程序，课程到CRT为止

1.1.2 C++ memory primitives

1.2 四个层面的基本用法

• 1、1，2行是malloc和free的应用实例；C函数
• 2、**4，5行是new和delete；**C++表达式；
• 3、7，8行是：：operator new()和::operator delete()；它们是全局函数,一种特殊的函数；
• 4、从10行开始，就是第四种用法，使用C++标准库中的分配器allocator
  • （1）因为不同编译器，接口不同，首先ifdef判断当前编译器；
  • （2）在__ BORLANDC __中，allocator（）是创建一个没有名称的临时对象，调用allocate(5)就是创建5个int大小的空间。建立一个对象.调用deallocate(p4,5)进行内存释放；
  • （3）dellocate释放时，不仅需要指针，还有记住每次分配的类型个数；使用者单单使用allocator分配器，就比较麻烦，一般都是容器调用分配器；
• GNUC4.9版本的调用代码；

1.2.1 C++标准库allocator的使用

• 下面是C++标准库中的allocator::allocate()和allocator::deallocate()的使用；在下面示例中，根据不同的编译器有不太一样的接口调用方法，按照C++标准库的标准规格应该完全一致，但是实现商业并未完全遵守，因此需要首先判断是哪个编译器；
• 注意，现在是绕开容器直接使用allocator；看19和20张代码，allocator是类型+()创建临时对象，第19行调用临时对象的allocate，然后这个临时对象就消亡了只存在于第19行，第20行是另一个新建的临时对象；**
• **在第20行调用临时对象的deallocator函数时，**不仅要提供指针（地址信息）而且要提供
• 具体申请的int数量！！！不然会报错；每次allocate还需要记住5这个信息，一般人是不用直接使用allocator的；***
• 注意在第一个版本下，还需要提供第二参数(int)0,无用但是因为第一版本没有设置默认参数，所以需要用户给出；

1.3 基本构件之一new delete expression

1.3.1 new expression

• try catch用来捕获异常；因为设计分配内存，所以需要设置捕获异常处理；

• new做两个动作：

  • 分配内存；
  • 调用构造函数；

• operator new可被重载，右上方是其源代码，可以看到调用了malloc实现；

  • while判断，如果malloc失败==0，那么进入循环，反复调用callnewh（自定义的函数，需要释放内存）；
  • 源代码的第二个参数，std::nothrow是保证不抛出异常；C++2.0有更正规的写法；

• Complex * pc=new Complex(1,2)是我们写的一句new，下面的框，就是编译器实际执行的过程；3就是通过指针调用构造函数；这种动作，只有编译器才可以直接调用构造函数；

1.3.2 delete expression

• delete的两件事：
  • 调用析构函数；（编译器直接调用析构）
  • 释放内存；（operator delete，源码中调用free）
• new和delete调用的operator new 和operator delete实现，而它们又是调用的malloc和free；
• new expression是一个表达式，而operator new是一个函数；

1.3.3 Ctor（构造）&Dtor（析构）直接调用

• 测试方式是new一个指针，指针直接调用构造/析构函数；
• 第一次测试，使用标准库string
  • 99行，是测试通过指针调用构造函数，->报错！编译失败，pstr->~string()是编译通过了，但是没有构造函数对应，标记为crash崩溃；
• 第二次测试，自定义类A，有构造函数与析构函数
  • 注释显示，VC6是成功的，GCC是失败的；VC6表现的不严谨；
• 结果：不能直接调用构造函数；

1.4 Array new，new[]

• 注意，这里delete[]pca会调用三次析构，对应new Complex[3]调用的三次构造；
• cookie用来记录信息，重要的是记录下面的空间长度；所有平台在设计malloc和free的时候，都带有这个cookie;
• 如果delete没有[]，就会造成内存泄漏；如右下角所示；
• 用array new就要对应使用array delete;

• 小的测试：

• 必须要有默认构造函数，调用的是默认构造函数，否则用new会报错；
• 测试中，用tmp代替buf指针，将tmp++，每次移动设置初值，这里用到了replacement new,形式new(tmp++)A(i),调用构造函数，并打印显示结果，
• delete[]buf,析构是次序逆反的；

• 探究cookie的存在及大小

• 左侧int* pi=new int[10]对应右侧，不仅仅有申请的10个Int空间，还有上下部分；
• VC6的空间是16区块，上下cookie完全一样，都是61h；
• 对于new int[10]delete加不加[]都无所谓，10个int没有所谓的析构函数，因为析构函数本身没有或者没有意义（Comlex）；

• 但是对于下图中，Demo是有析构函数的,重要且有意义的：

• Demo* p=new Demo[3]要求的3是会存储的，因此在free的时候会调用3次析构对应；
• 如果delete没有[],就会默认按照普通解析右侧灰色布局，就会报错发生左侧问题；
• delete和delete[]布局是不一样的；

1.5 Replacement new

• 我们有三个工具：分别是new、array new(new[])、replacement new
• 接下来就是replacement new:

• replacement new作用：
  • 将对象建造在已经分配的内存中；
• 因此，使用replacement new首先要有一个指针，代表已经分配好的内存空间；
• replacement new并不会再新的分配空间，new(buf)Complex(1,2)编译器执行过程如下图123；
  • 比之前多了一个buf,之前分配的内存空间；步骤1就不做事（不分配新的）就是直接return loc;
  • 123：内存分配（直接返回）+用返回的指针调用构造函数；

1.6 重载new,new[],placement new

• 重载上述三种：new,new[],placement new

1.6.1 术语，框架

• 之前讲解的是，下面绿色路径，而我们要实现的重载就是上面路径，我们可以通过重载建立内存池，再进行分割等操作；（比如，可以去除cookie等额外开销）
  • 但是不管怎么样，最终还是要使用malloc和free进行实现；
  • 两个黄色团都可以重载；但是一般都是重载上面黄色团；
• 也可以左下角，直接malloc和free实现；

• 在容器中，分配内存的动作都被划分到allocator分配器中进行；

1.6.2 重载

• 两种重载，这里是重载的全局函数，之前的下面的黄色团
  

右侧为源码（while调用malloc)；左侧为自己的重载

• 下图是类内函数重载，之前的上面的黄色团

size_t可有可无；必须是一个静态static;(可以不通过对象就调用起来)

1.6.3 重载示例（类内operator new…)

• 这个测试就是自定义一个类Foo，然后重载类内的operator new等四个函数（不重载全局函数，下面的黄色团，牵扯多，不容易）；
  • 具体重载的就是右边框所示；右侧没有什么特殊处理，就是使用malloc和free；
  • 会有一些输出，验证确实重载成功；如下图

• 如果左侧有::就会绕过上述的重载函数，如下图所示

1.6.4 重载new()/delete()

• 可以重载出new()的多个版本，根据（）中参数的不同，之前的replacement new只是编译器之前先写好的一个重载版本，被称为定点new/replacement new；
• 但其中第一个参数必须是size_t;

• （1）是一般的operator new的重载，（2）是标准库已经写的定点new；（3）（4）就是自定义的operator new；（5）没有遵循第一参数是size_t，重载就会报错；
• 接着对应的operator delete如下图所示。

• 右上角的测试案例，前4个都是默认构造函数，第5个是带有参数的构造函数；
• 故意在有参数的构造函数中抛出一个异常（throw Bad()),观察反应，
  • G4.9没有调用delete；
  • VC6会报出警告；
• 标准库中basic_string中有一个对于operator new的重载；

• 标准库basic_string实现operator new重载时，有第二参数size_t，是一个extra，最后申请的空间就是string内容（“hello”）+extra;

1.7 内存管理四个版本

1.7.1 版本一：Per-class allocator

• 针对一个类，写出它的内存管理
  • 1、降低mallo调用次数，一次malloc一大块内存；
  • 2、提高内存利用率，减少cookie，一大块内存就只有一套cookie;
• malloc其实并不慢；但是减少调用malloc次数是好的；使用一次malloc拿到一个大块内存，之后在从这一块内存中分割小内存给需求，就不用多次调用malloc；

• 目标：对Screen类，进行内存管理；
• 这种会多增加一个next指针，同等于数据int i都是4字节，会多消耗了一个指针内存；第一版确实如此，但是后面这个next指针将会有更大作用；
• 对operator new 和opretor delete的重载，如右侧所示；
  • operator new申请malloc一大块内存，就是大小为常量左下角const int Screen :: screenChunk = 24,一次性拿到24个int,然后切割用链表连接，之后将第一个指针传回去，return p;freeStore是记录的；
  • operator delete还回到链表头部，单向链表的基本操作；
  • 这个就是针对class Screen的内存池；

• 测试使用如下

• 左边间隔8，右边间隔16，每个多了cookie;cookie是全平台都是这么设计的；
• 如果多进程/多线程有打断这个分配内存的过程，也是存在这10个内存不是连续的情况；

1.7.2 版本二：union

• union就是多个类型在同一个内存地方的；
• next每次移动8个字节，拉成一个链表；
• **与第一版最大的不同，是将union中的next指针，使用Union将本身rep的前四个字节，作为指针来用；**所有的内存管理都用到了这个技巧

• operator delete，如下

• 版本一和版本二的delete都没有真正释放内放，只是还给内存池（链表）中了；
• 左侧是重载的，间隔8，右侧是原始的，间隔为16；
• 如果能还给内存给操作系统会更好；

1.7.3 版本三：Static allocator

• 版本二，代码重用高，因为针对每一个类都要重新写一遍；
• 版本三，就是抽出来，统一代码复用；用全局函数，或者用一个抽象类，因为面向对象不喜欢全局函数，因此用抽象类allocator；

• 设计一个类为allocator来完成这个内存分配的过程，其中定义两个函数分别是allocate和deallocate;
• 类allocator的内存大小=size*CHUNK，标准库中一次申请20；
• 类allocator进行简化，只有一个struct obj* next代表单向链表的一种常用写法；
• 其他类Foo/Goo，就可以使用allocator来实现内存分配管理；设置为static静态；allocator里有一个内存链表；第三版如下：

• 测试如下：

• 预期设计的是5个，那么每5个是内存连接的；

1.7.4 版本四：macro for static allocator

• 更偷懒一点：设计macro宏
  • 将左侧黄色部分，写为右侧蓝色部分；然后再新建类的时候，就只需要写下面的两行蓝色字体；

• 测试结果如下：

• global allocator

• 标准库中有一个global allocator，有16个自由链表，如下所示；
  • 是一个全局的，可以对待16种不同大小的size类型；
  • 不是针对于某一个类的

1.8 补充

1.8.1 New Handler

• 当operator new失败时，会抛出exception异常，编译器在抛出这个异常之前，会不止一次调用handler,我们可以设定这个new handler;
• 右侧，operator new源码就可以看到，malloc失败，会重复调用callnewh，
• new_handler的两个作用：
  • 让更多的memory可用；
  • 调用abort()或exit();

1.8.2 =default,=delete

• =default就是使用默认版本，=delete就是不用，删除；
• C++中只有构造函数，拷贝构造函数，拷贝赋值函数，析构函数有默认版本；
• 右侧话，说operator new和new[]也会有默认版本，测试如下图：

第二讲 std::allocator

2.1 VC6 malloc()

• VC6中cookie就是一定会占用8个字节；
• 工业中，小内存中cookie的使用会浪费内存；
• 目标：想要去除cookie，提高空间利用率；

2.2 不同编译器下体制内外的分配器

2.2.1 VC6 标准分配器之实现

• 首先allocator最重要的两个函数：
  • allocate；对应绿色下拉箭头，执行operator_new函数，实际是调用malloc；
  • deallocate；
• 总结：VC6中的alloctor只是用operator new和operator delete完成allocate和deallocate操作，并没有任何特殊设计，
• 如右侧容器的第二个默认参数，都是allocator<>;

2.2.2 BC5标准分配器之实现

• BC5中的alloctor只是用operator new和operator delete完成allocate和deallocate操作，并没有任何特殊设计，(就是都带着cookie)，
• 针对相同类型才可以去除cookie，因为cookie就是记录类型大小的，不同类型的话不可以去除cookie;
• 而针对于容器，就可以去除cookie;

2.2.3 G2.9标准分配器之实现

• 还是先看两个重要函数，allocate与deallocate；同样调用的operator new与operator delete；
• 但是，容器使用的分配器不是std::allocator而是std::alloc

• 对其使用，如右侧所示；右侧在释放deallocate还是记住（指针，大小（字节为单位））alloc :: deallocate(p,512);

2.2.4 G2.9std::alloc VS G4.9 pool_alloc

• 对比用例中，可以看到使用名称变复杂了；（灰色框）
• G4.9有很多扩充的allocator，其中__ pool _ alloc就是G2.9的alloc的化身；

2.2.5 G4.9 标准分配器之实现allocator

• 说道标准分配器，指的就是class allocator,之前的是编制外的

• 那么就用__ pool _alloc，编制外的，可以去除cookie;

• 测试程序是灰色，主体一般为白色；
• 可以看出，上方测试编制外的__ pool _alloc是不带cookie的，相距8个字节，
• 下方测试标准分配器allocator，带有cookie,相距10个字节；

• std:: alloc源码如下（运行模式）：

2.3 G2.9 std::alloc图解

2.3.1 G2.9 STD::alloc的总体运行模式

• 总的框架图如下：

• 右侧是容器，使用的分配器就是std::alloc
• 参照第四个版本，使用一个通用的适用于16个不同类型的分配器链表；#0=8字节，#1=16字节；#3=24字节
• 假设是32字节，对应#3处有一个链表，会一次性申请一大块（源码中是20个，可能是经验值）；
  • 两个绿色之间的，就是申请的20个size（32字节）；
  • 其实，在申请时，会有另一个20个size，一起申请，作为战略准备空间；
  • 如果又来一个新申请，那么#7就会连接到刚刚申请的地址处，之间是紧密连接的；
  • 第三个申请在#11处，就是96个字节处，之前的战略准备空间被第二个申请占据之后，就会重新申请空间链表，连接到#11处，也会有对应的*2的战略准备空间；

• 嵌入式指针，用原来的前4个字节作为指针使用

2.3.2 G2.9 std::alloc运行一瞥1-5

• 一开始的16个指针，链表free_list；
• 一直称为alloc其实是一个typedef __default_alloc_template<flase,0> alloc

• 因为没有cookie记录大小，因此单独使用分配器allocator的话，就需要记住申请了多少；
• 对于容器，本身可以通过容器类型记录size；
• 整个系统，总是把分配到的内存先放在战备池，如此构思，代码会写起来特别漂亮；

• 注意，从战备池中切出来的数量，一直都在1-20之间，即使有空余可以切20以上，也最多给20个；
• 第二次申请，#7=64字节时，先使用上一次的640个字节的站备池，没有额外malloc申请，就是使用的战备池，对应10个size的链表，之后就没有战备池（pool=0），且这一块没有cookie；

• 此次申请，pool=0，就Malloc一次，并*2的战备池；
• 注意，这里有一个RoundUp，每次的追加量，会越来越大；

之前的战备池有2000，但是最多置给20个，因此战备池2000-88*20=240字节；

2.3.3 G2.9 std::alloc运行一瞥6-10

• 这一张是#10申请了3个size，绿色格子，没有什么变化；

• 新的申请为#0，可以切出240-20*8=80；永远从战备池开始切，最多切20个；
• 两个特定的指针一指，就是战备池空间；

• 目前已经使用了多个不同类型大小的链表，不经常发生，对于vector或者list等，如果申请的都是int，那么就是会在同一个链表上。
• 新的申请，#12=104字节，
  • 首先从战备池有80<104，因此一个都切不出来，变成内存碎片，
  • 这个时候将80（内存碎片）给#9=80专门处理80字节的链表处，完成碎片处理；
  • 然后malloc需要的，104202+追加量（累计申请量/16）；
  • 累计申请量和pool大小都会对应增加；

• 新的申请，#13=112，从战备池足够取20个；

• 新的申请#5=48，就从战备池中168-48*3=24，那么就只给#5链表3个size；
• 24不一定会成为内存碎片，那么此时先留着；

2.3.4 G2.9 std::alloc运行一瞥11-13

• 通过修改源代码，将内存总量改为10000，观察分配器内存分配失败时的行为；
  

• 新的申请#8=72处，进行链表，此时24<72不足一个成为内存碎片，挂到#2处，内存碎片处理完之后，
• 申请会失败，那么就会利用之前申请的但还没有利用（空白的）的资源，使用最接近的#9回填pool，#9有一个就被拿来给#8，80-72=pool=8个字节；

• 此时，#9已经空了，看#10，从#10中切出一个，88-72=16，成为战备池；

• 如果申请#14，往后边找，发现没有，那么就会申请失败，到此为止；

• 检讨：
  • 还有白色资源；（操作难度很高）；
  • 还有10000-9688=312可以使用，

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

• 第一级分配器
  
  
  

• 一直到74行，都是第一级分配器的内容；class是到40,40-74是一些对应函数；
• 从77行开始，就是第二级分配器，77行开始是一个换肤函数，将其从字节转化为元素个数，/每个元素的大小；

• 右侧小框，是三个常用参数。历史原因使用了enum；
• template <bool threads,int inst>两个参数，分别是多进程，两个参数这里没有用，不提；
• ROUNG_UP(size_t types)用来上调至8的倍数；
• start_free和end_free就是指向战备池的两个指针，heap_size就是分配累计量；

• 两个最重要的函数allocate、deallocate
  

• allocate:

• my_free_list就是指向指针的指针，因为16个元素本身就是指针，而指向指针就是**；
• if n>(size_list)
  • 就第二级分配器失败，转向执行第一级分配器；
• else：
  • 首先判断应该的链表编号FRELIST_INDEX(n)；
  • 判断对应链表是否为空，
    • 如果不空，就移动指针；
    • 如果空，就refill充值，并且调用ROUN_UP来上8的倍数向上取整；

• deallocate:

• 回收就是移动链表；
• 首先有一个判断，大于128说明不是从这个系统中出去的，那么就执行第一级分配器；

• 疑惑，问题

• 1、deallocate没有释放free，只一直malloc，没有还给操作系统；
• 2、deallocate没有检查传入参数void *p是否是这个系统分配出去的，就使用并入alloc分配器，存在问题；

• 一些辅助代码
  
  
• 重要函数refill—将一大块内存分割成链表
  

• nobjs是传入引用，如果没有取到20个，取到几个就将nobjs设置为几个；
• 判断nobjs是否==1，如果不是1就可以切割，挂在链表上，for循环完成，每个指针跳跃n；for循环从1开始，第0个直接返回了，不需要进行切割；
• (onj*)(char*)next obj+n是指针先转化为字节，再+n再转型为(obj*)，是union的指针；

• 重要函数chunk_alloc----负责申请一大块内存
  

• 分配内存，首先从战备池开始，根据战备池的大小来判断下面操作；
• 首先计算战备池目前大小end_free-start_free将其跟需要的内存大小total_bytes作对比
  • 1）pool满足20个size；
  • 2）pool满足部分个size（不足20个）；
  • 3）pool一个也不够满足；下面方框就是将内存碎片充分利用；先处理完内存碎片，然后进行重新申请malloc对应内存要求；接上页：

• 接上页，malloc分配内存成功，就睡跳过方框，执行下面代码，最后用一个递归return (chunk_alloc(size,nobjs))递归重新调用一次这个函数，调整好pool两个指针的位置，并返回分配好的内存头指针；
• 如果内存失败（方框中），开始找右边的部分找空白资源，就释放出一块，将这一块放在战备池中，又一次递归调用，都是将内存充值到战备池中；代码漂亮！！针对战备池来处理操作；

• 小片段，已经在分配器class之外的一段
  

• 新的变量定义顺便赋初值；
• 然后有一个typedef alloc;

• G2.9 std::alloc 观念大整理
  

• 这里的Foo(1)是临时对象要内存，是在stack栈区，跟刚刚的heap堆区没有一点关系；当往list容器中插入发生copy时，才是运用了分配器alloc,不带cookie;
• 第二种，是通过new出的空间，是带有cookie的，将Push_back的时候，是没有cookie的，copy过来；

• G2.9 std:: alloc批斗大会
  

• 1）左侧的==将0/1常数写在左边，可以避免少些一个=的bug;
• 2）34行，就是将set_malloc_handler传入一个H，返回一个H；

• 3）213行注释，不利用小块空白，因为对于多进程会造成灾难；
• 4）deallocate没有free内存；先天性缺陷导致的；因为free需要cookie，而cookie的指针在前面的操作中，已经丢失，因此无法进行free；

2.5 G4.9 pool allocator运行观察

• 右上角是之前讲过的global operator new当时不重载，因为其影响较多，不易修改；
• 这个测试，就是使用全局的operator new来统计累计的分配量与释放量；
• 左侧的operator· new中使用全局变量countNew和 timesNew变量进行记录；
• 右侧的operator delete有两个版本，第二个参数我们通常不用，编译器会使用，而且在类成员中必须二选一；
  • 但是在测试中，（1）(2)版本可以并存，并且是（2）实际执行；
• 前面讲的都是G2.9，G4.9几乎一样，但是有不同：
  • G2.9分配内存是使用malloc,并且没有free；malloc是不可以被重载的，因此不能接管；
  • G4.9分配内存的是operator new，可以接管这个过程，如上图所示；

• 右侧测试容器是List，double8个字节，链表节点要带有指针，因此每次申请要16个字节，运行一百万次，结果如右侧注释所示，注意这里是标准分配器，都带有cookie;
• 左侧就是用的编制外的“好的”分配器就是__ gnu_cxx::__pool_alloc，进行测试，
  • 注意，左侧上方使用了模板化名，将其替代为listPool;
  • 对比结果，左侧只调用malloc了122次，申请空间稍稍大一点；左侧因为有内存的管理；
• 总结，左侧就有122个cookie=120*8字节，而右侧则有100,0000 * 8字节；差距很大！

• 第二讲相对于第一讲中分配器，最重要在于去除了cookie;
• G2.9 std::alloc移植到C
  • 有自己的命名空间，并不会和标准库中的发生冲突！好习惯；