C++内存管理总结

前言

之前看完学习了侯捷老师《内存管理》这门视频课程，为了加深印象以及日后回顾复习，特此做个总结。

本文会分成四部分内容：

• 第一部分介绍C++ 内存管理中的 memory primitives（一些基本知识点），对应对应《内存管理》视频课程第一讲；
• 第二部分介绍SGI STL中分配器的实现，对应《内存管理》视频课程第二讲，并且主要内容将参考文章 5 千字长文+ 30 张图解 | 陪你手撕 STL 空间配置器源码^[1]；
• 第三部分介绍 VC6 malloc底层实现，对应《内存管理》课程内容第三讲；
• 第四部分介绍 Loki （《Modern C++ Design》配套发行的一个 C++ 代码库）中的内存管理实现，对应《内存管理》课程第四讲。

说明：文中会有不少图片和内容摘自课程课件或者参考文章，如果有造成侵权请告知删除。

Memory Primitives（基本知识点）

1.使用memory的途经

对于C++ 应用程序，使用memory的途经如下图所示，可以使用最上层的 C++ Library（比如STL中的allocator分配器），也可以直接使用C++ primitives（主要指new表达式，array new，operator new和对应的delete等），再往下就是 CRT（C语言运行库，包含malloc/free的实现），最底层就是操作系统层面提供的API（图中给出的是Windows提供的API）。

---

进一步的，自底向上可以将内存管理分为三个层次^[2]：

1. 操作系统内核的内存管理

   • 例如虚存页式存储，地址映射等知识，可以参考 操作系统之内存管理。

2. glibc层使用系统调用维护的内存管理算法

   • 这里的内存管理算法主要是指malloc的实现算法，例如Linux中采用的ptmalloc算法，其实现通过使用brk、sbrk、mmap等系统调用；而在Windows中，其malloc实现为，依据申请的空间大小，大空间调用os API（HeapAlloc()），小空间使用SBH(小于等于1K)，这也是后文 VC6 malloc底层实现 要具体介绍的内容。

   • 注意这里的malloc只是分配一个虚拟地址，并没有分配实际物理地址，只有当用户使用内存时，操作系统内核才会分配具体的物理地址给用户使用^[3]。

3. 应用程序从glibc动态分配内存后，根据应用程序本身的程序特性进行优化

   • 比如使用引用计数std::shared_ptr，内存池方式等等。

   • 下一章节介绍的STL分配器就采用了内存池的方式， 就属于这一层次的内存管理。

2.C++ memory primitives（内存相关的基本组件/原语）

3.new expression 与 delete expression

• new expression 的操作可以拆解为三步：第一步通过 operator new函数申请内存空间，第二步对返回的指针进行转型，第三步调用构造函数 。（如果简化的话，也可以认为是两步，第一步申请内存空间，第二步在申请到的内存空间上执行构造函数）

  • 在operator new 函数中，实际上会去调用malloc函数申请内存空间；operator new 的第二个参数，用于保证不抛出异常
  • _callnewh：当malloc失败之后，就会调用用户设定的new handler函数（通过set_new_handler进行设置）。所以应该在new_handler函数中去尝试释放内存，以便下次进入循环时，malloc可以分配成功。

• delete expression 的操作也可以拆解为两步，第一步先是调用析构函数，第二步是释放对应的内存空间（实际上失去调用free函数）

4.array new 与 delete[]

需要注意的是new [] 和 delete[] 应该配合使用。如下图给出的例子，Demo是一个包含三个int变量的类，new Demo[3] 的内存结构如右侧所示：

• 最上方和最下方的 61h 表示的是cookie（malloc在申请内存会附加的信息，用来记录此次申请内存空间的大小，正是因为有这个cookie的信息，所以在调用free的时候才不需要传入“释放空间大小”这一参数）。
• 中间橙色部分，表示的是在Debug调试模式下，malloc在申请时附加的一些数据信息（比如记录这是从哪个文件的哪一行发出的请求）；如果不是debug模式下，应该是不会包含这部分额外信息
• 下面的数字“3”就是记录此次分配数组元素的个数，用来指示应该调用多少次构造/析构
  • 如果申请元素的类型没有 non-trivial dtor（重要的析构函数），双重否定句，也就是当元素类型的析构函数是trivial（不重要的）时候，就不会记录“3”，比如说申请的是 int 基本类型，该类型没有对应的析构函数，直接回收内存即可
• 再下面每3个 int 组成一个 Demo 对象
• no man land：无人区，用于隔离数据，如果这一块内存被修改了，表示越界访问出错了
• Pad：这个是malloc申请内存时对齐需要填充的空间

注意，new之后得到的p指向的地址上元素首地址0x00481c34，而delete []p传入p的地址指向的起始位置是“3”对应的地址0x00481c30，以便于知道需要析构多少次。因此如果不写[ ]，调用的是 delete p 就会在运行时报错，因为这样会按照没有“3”的情况去解读空间布局，而这就可能导致解析得到的要释放的内存地址和大小不正确。

5.placement new

placement new 实际上没有分配内存，会去执行重载的operator new(size_t, void*)，只是把传进来的指针直接返回，所以相当于只是调用了构造函数。

注意，可以自己再重载operator new，引入更多的参数，比如下面这样：

class Complex{
    // 类的其他一些变量或函数 ...
    // 重载 operator new
    void* operator new(size_t, void* p, int num) {
        // do something...
        return p;
    }
};

// 使用形式
char* buf = new char[sizeof(Complex)*3];
Complex* pc = new(buf,3) Complex(1,2);        // new() 传入了两个参数

6.分配内存的途径

下面两张图分别展示了C++普通程序和STL容器里分配内存的途径：

• 对于C++普通程序来说，最多还是使用 new expression 来动态分配内存，而 new expression 是不可改变的，不可重载的，会被编译器转换成去调用 operator new

  和 placement new 两步

  • 如果该类自身有重载operator new函数，则会去调用重载的函数

  • 如果类自身没有重载，就会去调用全局的 operator new函数，该全局函数的实现就是再去调用malloc函数。

    • 注意：全局的operator new 也是能够重载的，但是会影响全局的内存分配，因为所有没有重载类成员函数operator new的类，都会调用该全局operator new来分配内存。

• 对于C++ STL 容器来说，容器内元素的内存分配是通过分配器allocator来实现，allocator有多种实现方式，像是new_allocator 就是简单对全局operator new 进行封装，而pool_alloc则是采用了内存池管理的模式，这也是后文要重点介绍的内容。

STL之分配器

5 千字长文+ 30 张图解 | 陪你手撕 STL 空间配置器源码

原文其实已经介绍得很详细了，因此这里将配合《内存管理》视频课程对这这部分的讲解，对原文做一定的补充，凝练出最核心的部分。

注意：参考的这篇文章是讲解SGI STL中分配器实现，而《内存管理》中介绍的是 G2.9 std::alloc的实现，但其实原理是类似的，标准库的实现也是参考了SGI STL的实现， G2.9 std::alloc 就对应于 SGI STL中的第二级分配器，都是运用内存池的思想。

上文也有提到， new 和 delete 都包含两阶段操作：

• 对于 new 来说，编译器会先调用 ::operator new 分配内存；然后调用 Obj::Obj() 构造对象内容。
• 对于 delete 来说，编译器会先调用 Obj::~Obj() 析构对象；然后调用 ::operator delete 释放空间。

同样，STL allocator 也将这两个阶段操作区分开来：

• 内存配置由 alloc::allocate() 负责；内存释放由 alloc::deallocate() 负责；
• 对象构造由 ::construct() 负责；对象释放由 ::destroy() 负责。

SGI STL中定义的框架结构如下图所示（图片来源参考文章^[1]）。

对象构造和析构之后的内存管理诸项事宜，由 <stl_alloc.h> 一律负责。SGI 对此的设计原则如下：

• 向 system heap 要求空间
• 考虑多线程 (multi-threads) 状态
• 考虑内存不足时的应变措施
• 考虑过多“小型区块”可能造成的内存碎片 (fragment) 问题

考虑到小型区块可能造成的内存破碎问题，SGI 为此设计了双层级配置器。当配置区块超过 128bytes 时，称为足够大，使用第一级配置器，直接使用 malloc() 和 free()。

当配置区块不大于 128bytes 时，为了降低额外负担，直接使用第二级配置器，采用复杂的 memory pool 处理方式。

无论使用第一级配接器（__malloc_alloc_template）或是第二级配接器（__default_alloc_template），alloc 都为其包装了接口，使其能够符合 STL 标准。

可以参考下图的说明（图片来源参考文章^[1]）。

alloc 第一级分配器

（1）第一级配置器以 malloc(), free(), realloc() 等 C 函数执行实际的内存配置、释放和重配置操作，并实现类似 C++ new-handler 的机制（因为它并非使用 ::operator new 来配置内存，所以不能直接使用C++ new-handler 机制）。

（2）SGI 第一级配置器的 allocate() 和 reallocate() 都是在调用malloc() 和 realloc() 不成功后，改调用 oom_malloc() 和oom_realloc()。

（3）oom_malloc() 和 oom_realloc() 的实现跟C++ new_handler的实现是类似的，下图是实现源码，都是在不断循环调用“内存不足处理例程”，期望某次调用后，获得足够的内存而圆满完成任务，但如果用户并没有指定“内存不足处理程序”，这个时候便无力乏天，真的是没内存了，STL 便抛出异常，或调用exit(1) 终止程序。

下图则是operator new中的实现，可以看到new_handler机制的实现跟第一级分配器的实现是很相近的。

alloc 第二级分配器

首先来谈谈为什么划分出第二级分配器，并用复杂的内存池机制来进行管理。这是因为malloc实际分配的空间是大于申请的空间大小的，即会有cookie信息来记录此次分配的内存大小（用户对此无感知），正是因为携带了这份cookie信息，所以在free回收的时候才不需要显式传入需要回收的大小。

那么这就容易导致内存额外开销的问题，例如每次malloc我只需要申请4字节大小，但实际上却因为带有cookie信息，实际占用了12个字节（上下都记录4字节数据），显然空间利用率很低。因此才有了内存池的管理手段，一次分配大量的空间，然后再切割成一个个小份给用户使用，这样空间利用率就提高了。

---

接下来谈谈内存池的运作模式，如下图所示。简单描述一下就是有16条空闲链表，每条链表负责分配以8字节为倍数的内存大小，例如下标为0负责8字节大小，下标为3的负责32字节大小。每条链表上挂着多个空闲区块，每个空闲区块用embeded pointer的方式连接起来（就是把空闲区块的前4个字节用来记录下一个空闲区块的位置，这样就避免申请额外的指针空间。进行内存区块的分配和回收，也就是对链表进行相应的操作，例如请求25~32字节大小的区块，就由下标为3的链表负责分配，拿出链表的第一个空闲区块给用户，空闲链表再指向下一个空闲区块；回收的时候，再挂到对应链表上，作为第一个空闲区块。

大致了解运行模式后，再来看看关键的数据结构：

• union _Obj就是用来实现嵌入式指针，_M_free_list_link指向下一个空闲区块的地址，_M_client_data则表示当前_Obj的内存地址。
• _S_free_list就是需要维护的空闲链表
• _S_start_free和_S_end_free两个指针维护的是当前内存池的大小，但某条空闲链表上没有空闲区块的时候，就会从内存池中获取区块。而内存池的内存是通过malloc分配得到的。_S_heap_size变量维护的是当前已经累计申请的内存大小，用于malloc申请空间。

---

继续深入，来看看核心函数的源码实现。内存分配主要由allocate函数负责，内存回收主要是deallocate函数负责。deallocate的实现比较简单，就是将回收的内存块根据其大小，放到对应的空闲链表上。所以这里将主要介绍allocate函数实现。

下面是allocate函数的源码，可以看到，如果申请的内存大小大于128字节，就会转去调用第一级分配器，也就是直接调用malloc。如果小于等于128字节，则根据其大小找到对应合适大小的空闲链表，如果对应空闲链表有空闲的内存块则可直接分配，如果没有，则调用_S_refill函数进行获取。

---

_S_refill 函数源码实现如下图，其中又主要调用_S_chunk_alloc来获取空闲内存块，默认会申请20块空闲区块，但如果只取得了一个，则直接返回给用户使用。如果返回的块数大于1，除了需要分配1块个用户使用，剩余的空闲区块要挂到管理对应大小的空闲链表上，在实现就利用了embedded pointer。

---

最后来看_S_chunk_alloc 的源码实现，长图警告！

依照代码逻辑来看，结构为3个if else：

• 如果当前内存池剩余空间满足申请的空间大小，那么直接从内存池中进行分配，然后减小内存池大小（调整相应的指针）
• 如果当前内存池剩余空间不能够申请的空间大小，但是至少可以提供一个以上的区块，那么能够提供多少块就返回多少块，然后减小内存池大小
• 如果当前内存池剩余空间连一个区块的大小都无法提供，那么首先将当前内存池剩余空间分配给管理对应大小的空闲链表上，然后使用malloc申请大块空间。
  • 这里新申请的空间大小的计算特别注意一下，size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size >> 4); 是2倍原有的需求量再加上一个_S_round_up追加量，除了分配给用户的20个区块，剩余作为内存池容量，以供下次分配。可以推测是因为计算机在申请分配的所需的空间总是越要越大，为了加快分配就有了个追加量，而其中的数值可能是对应团队的经验值
  • 如果malloc申请成功，那就递归的调用自身，再次分配，因此此时有足够的内存池大小了。
  • 如果malloc分配失败了，表明当前系统已经没有多余的内存，那就从较大的空闲链表里分配一块作为内存池容量（从左往右找，找到最小能够满足分配的空闲区块大小），然后再递归调用自身进行分配。。
  • 如果空闲链表里也没有能够分配的空闲区块，那么转去调用第一级分配器进行分配。第一级分配器还是回去调用malloc，而它malloc失败的话，会有oom_malloc() 处理机制，会尝试去解决内存不足的问题（例如释放一些内存），如果无法解决，那就真的山穷水尽，程序终止退出。

小结

在侯捷老师的视频课程中，还提到了两点：

• 第二级分配器持有的内存池是越来越大的，并且在程序运行时不会归还给操作系统，也就是说如果高峰期分配了100MB内存，那么该内存池含有的空闲区块总和就一直是100MB，就算用户归还了，分配器还会一直持有以供下次分配，这就可能造成内存浪费的问题。那么为什么不为分配器设计内存归还的相关机制呢？
  • 这主要是因为实现难度极高，跟分配实现的机制相关，因为是以链表的形式连接空闲区块，当多次分配和归还之后，就很难找到相邻的内存块。并且链表的长度也不是固定的，在使用高峰期可能会变得很长。
• 另一点是在_S_chunk_alloc函数实现中，当内存池大小不够，去使用malloc申请内存，而如果malloc申请内存失败了，就会去找其它较大空闲链表上的区块。这里有可能是因为申请的内存过大导致的，如果能够减小申请量，就可以进行分配了，例如当前需要的一块大小是8B，那么计算得到需要申请2 * 20 * 8=320B（假设当前没有RoundUp追加量），而当前空闲内存只有200B，所以malloc分配失败，当如果我们申请160B 就能成功，仍然可以为用户提供空闲区块。那么，为什么不这么做呢？
  • 这主要是考虑到在多程序环境下，需要给其他程序预留内存。如果采用刚刚说的那种做法，相当于当前程序会最大程度的占用内存，那么留给其他程序的可用内存就变少了，就可能会给其他程序的运行造成麻烦。

最后再来一张SGI STL分配器进行内存分配的完整流程图，更多细节逻辑大家可以再去看源码，或者再看看提供的参考文章和侯捷老师的视频课程。

VC6 malloc底层实现

Loki内存管理

备注/参考

1. 5 千字长文+ 30 张图解 | 陪你手撕 STL 空间配置器源码 ↩
2. C++性能优化（八）——内存分配机制 ↩
3. malloc背后的系统知识 ↩