最近学习内存管理整理的笔记

参考资料

代码请移步GitHub，链接太多改不过来……

向侯捷老师致敬！

vedio

Libraries:

• STL Allocators
• MFC CPlex+CFixedAlloc
• Boost.Pool
• Loki SmallObjAllocator
• VC malloc/free
• jemalloc
• tcmalloc
• ptmalloc

编译环境

• macOS Mojave/Clang 9.0.0
• Ubuntu 18.04/GCC 7.5.0

主力机器是MAC，必要时为了模拟GNU环境会使用Ubuntu来测试。

如果没有特别标注GCC,则全部使用Clang编译并取得和GNU平台上逻辑相同的输出。需要说明的是LLVM和GCC渐行渐远，为Clang自行开发的lib++已经取代了GCC的标准库libstd++，导致不同的编译器最终的结果会有些许不同。

index

1. primitives

• 绪论
• new/delete探究
• 数组new/delete探究
• placement_new探究
• operator_new重载
• placement_new重载
• class allocator_1.0对象内存池
• GCC: 重载operator new/delete间隔为16Bytes,不重载的间隔32Bytes
• Clang: 都是16Bytes
• class allocator 2.0对象内存池
• static allocator 3.0对象内存池
• macro static allocator 4.0对象内存池
• new handler/default/delete探究

2. sd::allocator

VC6.0和BorlandC5.0这两个著名的编译器标准库内部实现中，每个容器的std::allocater都是通过::operator new/delete来完成的——本质就是直接调用malloc其他什么都没有做。而GNU2.9 C++中使用的版本是std::alloc——使用了诸如pool等高级的分配逻辑，在经过更新迭代后在GNU4.9中改名为__gnu_cxx::__pool_alloc——也是本章的重点关注对象。

各个编译器标准库版本的容器举例如下:

//VC6
template<class _Ty,
class _A= allocator<_Ty>>
class vector{  
  //...
};             


//BC5
template<class T, 
    class Allocator=allocator<T>>
class vector{
  //... 
};


//GNU C++
template<class T, 
    class Alloc = alloc>
class vector{
  //...  
}; 

• GNU2.9-4.9对cookie的优化
• GCC2.9-std::allocator: 连续申请三个8Bytes-double的元素，地址间隔32Bytes
• GCC4.9-__gnu_cxx::__pool_alloc:连续申请三个8Bytes-double的元素，地址间隔16Bytes

GNU2.9中的std::alloc内存分配流程：

• size容器所申请的对象大小；chunk分配器提供的内存单元——共16种。
• 维护16条长度各异(第n条链表一次分配的chunk大小为:8*(n + 1)Bytes，)的自由链表，超过能分配最大的内存单元会申请malloc。所有使用malloc使用的都会带cookie。
• 分配器会将申请的内存size按照分配单元调整到合适的边界(比如std::alloc是8的倍数，malloc也会调整)
• 拿到一个申请的size需要分配的对象，首先定位它在分配器上的指针端口。然后查看是否有战备池的内存可以用，如果有直接使用，这时候一般分配的数量是1~20个chunk。没有则调用malloc分配。第一次分配pool为零，则直接调用malloc。
• 分配器调用malloc分配大小为size * 20 * 2 +ROUNDUP(memory_allocated >> 4);,其中会有20个chunk是为申请的对象准备的，剩下的内存(并不会分割)作为战备池为以后的分配器行为做准备——这是一个很重要的概念，分配全程需要关注战备区pool的容量。 其中ROUNDUP()是对齐函数，memory_allocated是已经分配好的内存总量。随着内存分配操作越来越多，memory_allocated也是越来越大——符合计算机内存分配越来越多的增长趋势。
• 如果战备池剩下的内存小于size，则被看成是碎片——需要重新挂到相应的链表头指针上——寻找相应的chunk端口。
• 如果malloc系统内存分配失败，则需要在最接近size的已分配好的空闲chunk中回填pool，完成分配。如果向上走也无法分配成功，那系统分配才算完全失败。
• 由于一次性分配20个chunk，而每一次分配必须按照其size来选择链表头结点，所以有很大概率某些指针上的空闲chunk就会比较多。而std::alloc对chunk的选择一定是大于等于size的。从技术的角度，将这些空闲的chunk合并在一起难度非常大。
• 分配器面向的用户是容器——元素一样大的集合，如果用户直接使用分配器，就必须记住分配的大小。这是因为自主分配的内存不会带cookie，而容器的第一个目标参数都会是参数类型，只要sizeof一下就可以计算出来所申请的size。
• embedded pointers是成熟的工业级分配器都会使用的Tips。

• GNU2.9的std::alloc源码实现

如果只是为了理解内存分配，其实很多代码都没有用。

• GNU2.9的std::alloc源码实现简易版

• __pool_alloc新型的分配器测试程序

• GCC： 测试样例1000个元素。

  • 标准分配器: 分配1000次，得到24000个字节
  • 新型分配器: 分配16次，得到25224个字节

3. malloc

Windows下VC6.0中C++程序的流程(简化版)——伪码中的API都是Windows平台下的。执行流程是前一个函数调用后一个函数。需要有OS-虚拟内存的基础。

• KERNEL32! bff89f5b()... 内核函数

• mainCRTStartup() 由C Runtime Library

​ 系统启动最初由HeapAlloc分配4096字节并传给指针_crtheap，并建立16个Header。接着第一个Header的一个指针利用VirtualAlloc(0, 1Mb, MEM_RESERVE)函数向操作系统直接申请了1MB的虚拟地址空间(并不分配内存)，另外一个指针从_crtheap中又分配了sizeof(region)大小的内存用来建立管理中心。

​ 总结一下，最开始进行了两种操作，一个操作是真正的向OS要了4KB的物理内存_crtheap，用来建立region控制中心和16个Header——这里用的是API是HeapAlloc()；而另一个操作是作为控制中心的region申请了1MB的虚拟地址空间(注意这里并没有直接分配内存)——用的API是VirtualAlloc()。这一切操作都是在ioinit函数真正申请内存之前就完成了。

• _heap_init()

  _heap_init部分代码

  • __sbh_heap_init()

  __sbh_heap_init部分代码

• _ioinit() 第一次尝试申请内存共100h

  _ioinit部分代码

  • _heap_alloc_dbg() 调试模式下

  _heap_alloc_dbg部分代码

  • _heap_alloc_base() 确定小于1024采用SBH小区块分配器

  _heap_alloc_base部分代码

  • _sbh_alloc_block() 计算好总共需要分配的内存字节 130h

  _sbh_alloc_block部分代码

  程序第一次申请内存分配是ioinit()共申请了100h字节，加上调试器模式下结构体大小，以及两个cookie(上下cookie是为了回收的时候上下合并)：

  0x100 + 0x24 + 4 * 2 = 0x12C ——> 0x130(aligned)——>0x131(使用最后一位标记分配)

  但其实只是计算，系统并没有实际开始分配内存。

  • heap_alloc_new_region() 第一个Header的指针申请region——由HeapAlloc(_crtheap, sizeof(region))分配

  内存分配原理： 16个Header(有一个头指针为其定位)。每一个Header负责管理1MB——申请虚拟地址空间调用Windows API——VirtualAlloc()。每一个Header有两根指针——其中一根指向其管理中心——region。
  

     //region结构
     typedef struct tagRegion{
       int indGroupUse;    //整数   
       char cntRegionSize[64];    //64个character
        //unsigned int 32位    高位和低位合并之后——>32组数据，每组64bits   
       BITVEC bitvGroupHi[32]; 
       BITVEC bitvGroupLo[32];
       //32个group  每一个group管理32KB
       struct tagGroup grpHeadList[32];
     }REGION,&PREGION;

     //group结构
     typedef struct tagGroup{
       int cntEntries;
        // 64对双向链表  
       struct tagListHead ListHead[64];   
     }GROUP, *PGROUP;

     //双向链表
     typedef struct tagListHead{
       struct tagEntry* pEntryNext;
       struct tagEntry* pEntryPrev;
     }LISTHEAD, *PLISTHEAD;

     typedef struct tagEntry{
       int sizeFront;       //记录4080Bytes
       struct tagEntry* pEntryNext;
       struct tagEntry* pEntryPrev;
     }ENTRY *PENTRY;

• heap_alloc_new_group()

  1MB分为32个单元，每单元32KB的大小。然后每一个单元又分为8个page，每部分4KB——对应操作系统的page。而管理中心region一共有32个group,所以每一个group管理8x4KB的内存资源。

  从上面的代码中可以知道:一个group共有64个双向指针，这些指针所管理的内存按照16的倍数递增(即1st—16字节，2nd—32字节…64th—>=1024字节)。 因此一个group实际上可以管理的大小是16*(1 + 2 + ...+ 64) = 32KB + 512Bytes。符合最开始的设定。

  根据ioinit申请的内存大小110h，加上debug模块和cookie，再进行16字节的对齐。最后需要向每> > 一个page申请130h字节的内存。最后还剩下ec0h = ff0h - > > > 130h。那一个page便会被切割成为两部分——一部分是分配的130h内存，这一部分需要将130h改为131h>代表脱离了SBH系统的控制分离出去。 另一部分是剩下的ec0h。双方的结构都是heap_alloc_dbg::struce > _CrtMemBlockHeader并且都需要更新cookie。以后每一次分配都需要根据分配的size计算所挂的链表——如果该链表上没有区块，则向上移动直到最后一条链表上再分配。

至此，malloc函数的整个分配过程基本结束了。侯捷老师的PPT和课程中的讲解非常精彩，建议反复听直到能够自行画出内存图。

4. free

    free(p)   //将p回收到相应的链表上

• 落在哪个Header上
• 落在哪个Group上
• 落在哪个free-list上

整个系统的主要结构就是:Header/Region——Group——free-list上述各个数据结构的大小都知道，所以很容易定位p指针。

Group回收: (p - 头指针)/32K

Header回收: 使用头指针__sbh_pHeaderList从第一个Header开始索引判断。

free-list回收: 将区块size/16 - 1然后判断回收需要挂在group上的哪一个链表上面。

合并：每一个区块都有上下的cookie，根据cookie的最后一位是不是1判断是否可以合并。

Defering：当出现两个Group全回收(Counter判断)的时候，则将Defer指针指向第一个准备释放给OS，如果只有一个全回收的Group则不释放。

5. Loki::allocator

Loki Library中的分配器。 省略…

6. Other issues

主要介绍GNU-C下其他的7个分配器。

分配器负责为标准库的容器分配内存。总的来说有两种方式:直接分配(调用malloc)和智能型。

所谓智能型分配的方式，就是将所分配得到的内存加以缓存(Cache)——即内存池。这种方式不仅可以适当的提升分配的速度，而且降低了cookie的空间浪费。 相关的分配器比如：

• __gnu_cxx::bitmap_allocator 重点
• __gnu_xx::pool_allocator 第二讲重点——缺点是分配的内存不回收给OS
• __gnu_cxx::__mt_alloc

另外还有四种分配器:

• __gnu_cxx::new_allocator 调用::operator new/delete

• __gnu_cxx::malloc_allocator 直接调用malloc/free

• __gnu_cxx::array_allocator 部分源代码

• __gnu_cxx::debug_allocator 部分源代码

bitmap_allocator

blocks,super-blocks,bitmap,mini-vector

分配：

容器分配一个blocks，每个区块8个字节。加上bitmap以及一些区块叫super-blocks。假设有64个blocks，则需要的bitmap是64bits——两个unsigned int。bitmap每一个bit为1表示还未分配。use-count表示用掉的区块计数(整数)。size-super-block表示super-block的大小——64 * 8(block size) +4(use-count) + 4*2(bitmap) = 524Bytes。

__mini_vector: 自行实现的小型结构管理bitmap——成倍增长

• _M_start, 指向头结点
• _M_finish, 指向尾节点的后一个结点
• _M_end_of_storage

super-block是基本单元。当启动第二个super-block的时候，首先区块数量会加倍——从64Bytes变成128Bytes。接着bitmap会变成4个unsigned int。这时候size-super-block为128 * 8(block size) + 4 * 4(bitmap) + 4(use-count)= 1044bytes。由于需要有两个控制中心——所以__mini_vector也需要增加，因为是类vector所以有时成倍增长。

释放：

会再增加一个__mini_vector，最多64个entry，如果超过了区块就会被还给操作系统。

• 其他分配器测试程序
• GCC