之前我们讲到线性地址空间按照功能的不同可以分为不同的区域。同时我们还简单介绍了如何使用 sbrk 和 mmap 这两个系统调用向操作系统申请堆内存。其实堆内存是程序员打交道最多的一块区域无论是哪种编程语言正确合理并高效地使用堆内存都是极具挑战的一件事情。对程序调优是系统程序员常见的工作任务而堆内存的管理和分配恰恰是最容易出现性能瓶颈的模块。不过sbrk 和 mmap 这两个系统调用分配内存效率比较低我们在之前讲过进程的内核态和用户态的区别执行系统调用是要进入内核态的运行态的切换会耗费不少时间。为了解决这个问题人们倾向于使用系统调用来分配大块内存然后再把这块内存分割成更小的块以方便程序员使用这样可以提升分配的效率。在 C 语言的运行时库里这个工作是由 malloc 函数负责的。但有时候 C 语言的原生 malloc 实现还是不能满足特定应用的性能要求这就需要程序员来实现符合自己应用要求的内存池以便自己进行内存的分配和释放。这节课我们就一起来学习如何对通过系统调用申请来的大块内存进行更精细化的管理。通过这节课的学习你将了解到堆内存管理的常用方法以及内存泄露、double free 等常见的内存问题产生的原因和排查方法从而提高自己分析和解决内存问题的能力。malloc 的基本功能正如这节课开头讲的向操作系统申请来的大块内存需要分割成合适的大小才能让程序员正常使用其实这个任务是由 glibc 承担的。glibc 是 C 语言的运行时库C 语言中常用的函数例如 printf、scanf、memcpy 和 strcat 等等它们的实现都在 glibc.so 中。通过后缀名你可能也猜到了glibc 是一种动态链接库它的工作原理与之前所讲的动态链接库是一样的与普通的动态库相比它并没有什么特别之处。我们今天要讲的就是 glibc 中用于内存管理的两个重要函数malloc 和 free。我们先展示一下 malloc 和 free 的用法请看下面这段 C 代码#include stdio.h #include malloc.h int main() { void *p malloc(16) printf(%p\n, p); free(p); return 0; }上述代码中应用程序通过 malloc 函数申请了一块内存并把这块内存的起始地址打印了出来然后再通过 free 函数释放这块内存。通过之前的学习我们已经知道打印的结果实际上是申请的内存块的线性地址。更具体一点这块空间位于堆中。malloc 实现的基本原理是先向操作系统申请一块比较大的内存然后再通过各种优化手段让内存分配的效率最大化。在 glibc 的实现里malloc 函数在向操作系统申请堆内存时会使用 mmap以 4K 的整数倍一次申请多个页。这样的话mmap 的区域就会以页对齐页与页之间的排列非常整齐避免了出现内存碎片。从这个角度看glibc 中的 malloc 方法非常像批发商它从供应商操作系统那里一次批发了很大的内存然后以零销的方式一点点分配出去而且它不光负责销售还负责售后分配到的内存可以使用 free 退货。要想又好又快地正确使用堆内存一个很重要的方式就是对内存做精细化管理。malloc 的实现原理内存的精细化管理我们要考虑两个因素一是分配和回收的效率二是内存区域的有效利用率内存区域的有效利用率又包含两个方面一个方面是每一小块内存内部是否被合理利用另一个方面是块与块之间是否存在无法利用的小块内存。你可以用建筑规划来进行类比。我们有一块很平整的地如果一个建筑设计得不合理比如本来只有一千个学生但却修了一个五千人的体育场这就是内部空间的浪费。如果各个建筑都是奇形怪状的不能对齐那么建筑与建筑之间的不可用的地块就会增多这就是外部空间的浪费或者称为碎片。对小块内存进行精细化管理最常用的数据结构就是链表。为了能够方便地进行分配和回收人们把空闲区域记录到链表里这就是空闲链表 (free list)。空闲链表空闲链表里的节点主要是为了记录内存的开始位置和长度如下图所示图中展示了一个总长度为 100 的内存区域已经分割成 16、16、20、16、16、16 六个小的内存块。其中着色部分也就是第一、第三和第五块内存是已经分配出去的正在使用的内存而白色区域则是尚未分配的内存。图的上半部分代表空闲链表每一块未分配的内存都会由一个空闲链表的节点进行管理。结点中记录了这块空闲内存区域的起始位置和长度。当分配内存的请求到达以后我们就通过遍历 free list 来查找可用的空闲内存区域在找到合适的空闲区域以后就将这一块区域从链表中摘下来。比如要请求的大小是 m就将这个结点从链表中取下把起始位置向后移动 m大小也相应的减小 m。将修改后的结点重新挂到链表上。在释放的时候将这块区域按照起始起址的排序放回到链表里并且检查它的前后是否有空闲区域如果有就合并成一个更大的空闲区。这种算法所使用的数据结构比较简单算法也很直接我们把这种算法称为简单算法 (Naive Algorithm)。我们举个例子说明简单算法的运行过程假如在算法开始时内存的情况如下图所示假设对内存的操作序列是这样的void test() { void* p1 malloc(16); void* p2 malloc(16); void* p3 malloc(20); free(p2); void* p4 malloc(16); void* p5 malloc(16); free(p4); }执行完 test 函数以后内存的划分就会和这节课的第一幅图一样了。做为练习请你自己画出每一个步骤 free list 和内存的变化情况这里不再给出。如果此时又到达了一个内存分配请求要申请一个大小为 20 的内存区域虽然所有空闲区域的大小之和是 48是超过 20 的但是由于这三块空闲区域并不连续所以我们已经无法从这 100 字节的内存中再分配出一块 20 字节的内存区域了相对于这次请求这三块 16 字节的空闲区域就是内存碎片。这就是我们所介绍的简单算法的第一个缺陷会产生内存碎片。每一次分配内存时我们都需要遍历 free list最差情况下的时间复杂度显然是 O(n)。如果是多线程同时分配的话free list 会被多线程并发访问为了保护它就必须使用各种同步机制比如锁或者无锁的 concurrent linked list 等。可见上述算法的第二个缺陷是分配效率一般且多线程并发场景下性能还会恶化。为了改进以上两个问题人们想了很多办法我们举几个历史上曾经出现的改进方案。其中一种方案是直接对简单算法进行优化。简单算法中找到第一个可用的区域就返回这个策略被称为 First Fit优化的具体做法是把它改成最佳匹配 (Best Fit)改造后它要找到能满足条件的最小的空闲区域才返回。从直观上说这种分配策略能尽可能地保留大块内存避免它被快速地分割成小块内存这就能更好地对抗内存碎片。严格的理论证明也证明了这一点。但是这种策略需要遍历整个链表时间复杂度反而变差。另一种方案是 Knuth 提出的 Next Fit 策略即每次查找不必从头开始而是从上一次查找的位置继续向后查找。实验也证明这种策略会比从头开始的算法有更高的效率。但它依然不能解决内存碎片的问题。还有一种改进方案名字叫分桶式管理这种改进是一种相对均衡的做法在对抗内存碎片和分配释放的时间复杂度两个方向都有改善。这也是在现实中被使用的最广泛的一种方法。接下来我们就重点分析分桶式管理算法。分桶式内存管理分桶式内存管理采用了多个链表对于单个链表它内部的所有结点所对应的内存区域的大小是相同的。换句话说相同大小的区域会挂载到同一个链表上。最常见的方式是以 4 字节为最小单位把所有 4 字节的区域挂到同一个链表上再把 8 字节的区域挂到一起然后是 16 字节32 字节这样以 2 次幂向上增长。如下图所示采用了新的数据结构以后分配和回收的算法也相应地发生了变化。首先分配的时候我们要只要找到能满足这一次分配请求的最小区域然后去相应的链表里把整块区域都取下来。比如分配一个 7 字节的内存块时我们就可以从 8 字节大小的空闲链表里直接取出链表头上的那块区域分配给应用程序。由于从链表头上删除元素的时间复杂度是 O(1)所以我们分配内存的效率就大大提高了。由于整个大块内存被提前分割成了整齐的小块比如是以 4 字节对齐所以整个区域里不存在块与块之间内存碎片。但是这种做法还是会产生区域内部的空间浪费比如上面举的例子当申请的内存大小是 7 时按当前算法只能分配给它大小为 8 的块这就造成了一个字节的内部浪费或者称之为内部碎片。内部碎片带来的问题是内存使用率没有达到 100%在最差情况下可能只有 50%。但是内部碎片随着这一块区域的释放也就消失了所以不会因为长时间运行而积累成严重的问题。释放时只需要把要释放的内存直接挂载到相应的链表里就可以了。 这个速度和分配是一样的效率非常高。分桶式内存管理比简单算法无论是在算法效率方面还是在碎片控制方面都有很大的提升。但它的缺陷也很明显区域内部的使用率不够高和动态扩展能力不够好。例如4 字节的区域提前消耗完了但 8 字节的空闲区域还有很多此时就会面临两难选择如果直接分配 8 字节的区域则区域内部浪费就比较多如果不分配则明明还有空闲区域却无法成功分配。为了解决上述两个问题人们在分桶的基础上继续改进让内存可以根据需求动态地决定小的内存区域和大的内存区域的比例。这种设计的典型就是伙伴系统我们一起来看下。伙伴系统正如上面的例子所讲的当系统中还有很多 8 字节的空闲块而 4 字节的空闲块却已经耗尽这时再有一个 4 字节的请求则会出现 malloc 失败的情况。为了避免分配失败我们其实还可以考虑将大块的内存做一次拆分。如下图所示。分配一块 4 字节大小的空间在 4 字节的 free list 上找不到空闲区域系统就会往上找假如 8 字节和 16 字节的 free list 中也没有空闲区域就会一直向上找到 32 字节的 free list。伙伴系统不会直接把 32 的空闲区域分配出去因为这样做的话会带来巨大的浪费。它会先把 32 字节分成两个 16 字节把后边一个挂入到 16 字节的 free list 中。然后继续拆分前一半。前一半继续拆成两个 8 字节再把后一半挂入到 8 字节的 free list最后把前一半 8 字节拿去分配当然这里也要继续拆分成两个 4 字节的空闲区域其中一个用于本次 malloc 分配另一个则挂入到 4 字节的 free list。分配后的内存的状态如下所示这种不断地把一块内存分割成更小的两块内存的做法就是伙伴系统这两块更小的内存就是伙伴。 它的好处是可以动态地根据分配请求将大的内存分割成小的内存。当释放内存时如果系统发现与被释放的内存相邻的那个伙伴也是空闲的就会把它们合并成一个更大的连续内存。通过这种拆分系统就变得更加富有弹性。malloc 的实现在历史上先后共有几十种策略这些策略往往就是上述三种算法的组合。具体到 glibc 中的 malloc 实现它就采用了分桶的策略但是它的每个桶里的内存不是固定大小的而是采用了将 1 ~ 4 字节的块挂到第一个链表里将 5 ~ 8 字节的块挂到第二个链表里将 9~16 字节的块挂到第三个链表里依次类推。在单个链表内部则采用 naive 的分配方式比如要分配 5 个字节的内存块我们会先在 5 ~ 8 这个链表里查找如果查找到的内存大小是 8 字节的那就会将这个区域分割成 5 字节和 3 字节两个部分其中 5 字节用于分配剩余的 3 字节的空闲区域则会挂载到 1~4 这个链表里。可见 malloc 的实现策略是比较灵活的针对不同的场景不同的分配策略的性能表现也是不一样的。很多公司的基础平台都选择自己实现内存池来提供 malloc 接口这样可以更好地服务本公司的业务。最著名的例子就是 Google 公司实现的 Tcmalloc 库。Tcmalloc 相比起其他的 malloc 实现最大的改进是在多线程的情况下性能提升。我们知道在多线程并发地分配内存时每次分配都要对 free list 进行加锁以避免并发程序带来的问题这就容易形成性能瓶颈。为了解决这个问题Tcmalloc 引入了线程本地缓存 (Thread Local Cache)每个线程在分配内存的时候都先在自己的本地缓存中寻找如果找到就结束只有找不到的情况才会继续向全局管理器申请一块大的空闲区域然后按照伙伴系统的方式继续添加到本地缓存中去。在实际工作中你可能会遇到这两个问题而束手无策第一个问题是系统所提供的 malloc其性能不足以支撑自己的业务或者自己的业务在分配内存时有其特殊的规律需要为它做专门的订制和优化第二个问题是在 malloc 和 free 里做一些统计动作以排查问题比如打印日志。下面我来带你自己动手实现内存管理库让你更好解决内存问题的同时还可以深入地理解内存管理的更多技术细节。自己动手实现内存管理库第 1 个问题的典型代表就是上面所提到的 Tcmalloc。我们这里举一个第二个问题的例子。比如我曾经遇到过一个 double free 的错误在申请了一段内存以后经过复杂的逻辑有两个指针指向了同一块内存当我对两个指针都调用 free 方法的时候错误就发生了我把这个错误示例进行了简化并把它的代码放在下面#include stdio.h #include stdlib.h int main() { int* p (int*)malloc(sizeof(int)); char* q (char*)p; free(p); free(q); }很明显第 8 行第 9 行释放的是同一块内存运行这个例子我们会看到进程 crash 了并且系统提示为*** Error in ./dfree: double free or corruption (fasttop): 0x000000000196a010 *** Aborted这就是 double free 的错误也就是说一块内存被释放了两次。这个例子比较简单但是在复杂逻辑中我们往往很难判断多个指针是否指向相同的地址。如果我们在所有调用 free 的地方增加日志把要释放的指针记录下来就会比较有助于分析和定位问题。幸运的是我们确实有这种手段那就是 Linux 的 preload 机制。在第 8 节课我们深入地学习了 Loader 的原理我们知道对于未定义的引用动态链接器要先进行解析它会先搜索 LD_PRELOAD 目录下的动态库然后再搜索其他的库所以我们就有办法对 malloc 和 free 函数进行替换。比如自己提供 free 的实现#define _GNU_SOURCE #include stdio.h #include stdlib.h #include dlfcn.h void free(void *ptr) { void(*freep)() NULL; printf(ready to do free: %p\n, ptr); freep dlsym(RTLD_NEXT, free); freep(ptr); printf(free done: %p\n, ptr); }我们先来分析一下上面的代码我要提醒一下你第 1 行的 _GNU_SOURCE 是一定要添加的因为第 10 行的 RTLD_NEXT 宏依赖于这个宏。接着我们定义了一个函数指针第 7 行它可以指向真正的 free 的实现。然后分别在调用 free 前和调用 free 以后打印一次要释放的指针第 9 行和第 12 行再通过 dlsym 打开了 glibc 中的 free 方法第 10 行dlsym 的作用是通过符号名称找到符号对应的地址。标题二你还要注意的是第 10 行使用 RTLD_NEXT 就是告诉 ld-linux.so 不要在当前文件中找 free 这个符号而是要按照动态库的搜索顺序找到下一个动态库并在它里面寻找 free 函数实际上这里找到的就是 glibc 里的 free 函数了。分析完这个代码以后我们发现这里自己定义的 free 方法不过是 glibc 里的 free 方法的一个包装 (wrapper)。接着我们使用以下命令编译 myfree 库并设置 preload 再执行 dfree 用例$ gcc -shared -fpic -o myfree.so myfree.c -ldl $ LD_PRELOAD./myfree.so ./dfree ready to do free: 0x1b44010 free done: 0x1b44010 ready to do free: 0x1b44010 *** Error in ./dfree: double free or corruption (fasttop): 0x0000000001b44010 *** Aborted运行上面的代码你可以看到我们新添加的日志已经可以正确输出了。通过这种方式我们就重载了 free 方法。总结我们这节课深入地介绍了 malloc 方法的实现原理并以一个例子来说明如何设计自己的动态内存管理器。通过这节课的学习我们了解到 sbrk 和 mmap 是操作系统提供的系统调用系统调用性能不够且不能对分配的内存进行有效管理所以必须有人在用户态将大块的内存分割成小块然后进行更精细的分配和回收这个工作通常情况下是由 glibc 承担的。glibc 所提供的 malloc 在管理内存时采用了空闲链表 (free list) 的方式。对 free list 的组织有简单算法、分桶管理和伙伴系统等不同的策略。我们评价一个管理内存算法的因素主要有以下三个维度数据结构如何设计是否存在内存碎片分配的效率释放的效率。我把三种算法按照上面三个维度总结成以下表格你可以参考一下由于动态链接器只识别第一次遇到的符号所以我们就有机会通过重写 glibc 中的方法来实现自己的内存管理库。这主要是为了提升性能或者是为了排查错误。我们以 double free 为例介绍了典型的内存错误并通过覆写 free 函数来解决它。这展示了一个完整的设计内存管理库的过程。
之前我们讲到线性地址空间按照功能的不同可以分为不同的区域。同时我们还简单介绍了如何使用 sbrk 和 mmap 这两个系统调用向操作系统申请堆内存。其实堆内存是程序员打交道最多的一块区域无论是哪种编程语言正确合理并高效地使用堆内存都是极具挑战的一件事情。对程序调优是系统程序员常见的工作任务而堆内存的管理和分配恰恰是最容易出现性能瓶颈的模块。不过sbrk 和 mmap 这两个系统调用分配内存效率比较低我们在之前讲过进程的内核态和用户态的区别执行系统调用是要进入内核态的运行态的切换会耗费不少时间。为了解决这个问题人们倾向于使用系统调用来分配大块内存然后再把这块内存分割成更小的块以方便程序员使用这样可以提升分配的效率。在 C 语言的运行时库里这个工作是由 malloc 函数负责的。但有时候 C 语言的原生 malloc 实现还是不能满足特定应用的性能要求这就需要程序员来实现符合自己应用要求的内存池以便自己进行内存的分配和释放。这节课我们就一起来学习如何对通过系统调用申请来的大块内存进行更精细化的管理。通过这节课的学习你将了解到堆内存管理的常用方法以及内存泄露、double free 等常见的内存问题产生的原因和排查方法从而提高自己分析和解决内存问题的能力。malloc 的基本功能正如这节课开头讲的向操作系统申请来的大块内存需要分割成合适的大小才能让程序员正常使用其实这个任务是由 glibc 承担的。glibc 是 C 语言的运行时库C 语言中常用的函数例如 printf、scanf、memcpy 和 strcat 等等它们的实现都在 glibc.so 中。通过后缀名你可能也猜到了glibc 是一种动态链接库它的工作原理与之前所讲的动态链接库是一样的与普通的动态库相比它并没有什么特别之处。我们今天要讲的就是 glibc 中用于内存管理的两个重要函数malloc 和 free。我们先展示一下 malloc 和 free 的用法请看下面这段 C 代码#include stdio.h #include malloc.h int main() { void *p malloc(16) printf(%p\n, p); free(p); return 0; }上述代码中应用程序通过 malloc 函数申请了一块内存并把这块内存的起始地址打印了出来然后再通过 free 函数释放这块内存。通过之前的学习我们已经知道打印的结果实际上是申请的内存块的线性地址。更具体一点这块空间位于堆中。malloc 实现的基本原理是先向操作系统申请一块比较大的内存然后再通过各种优化手段让内存分配的效率最大化。在 glibc 的实现里malloc 函数在向操作系统申请堆内存时会使用 mmap以 4K 的整数倍一次申请多个页。这样的话mmap 的区域就会以页对齐页与页之间的排列非常整齐避免了出现内存碎片。从这个角度看glibc 中的 malloc 方法非常像批发商它从供应商操作系统那里一次批发了很大的内存然后以零销的方式一点点分配出去而且它不光负责销售还负责售后分配到的内存可以使用 free 退货。要想又好又快地正确使用堆内存一个很重要的方式就是对内存做精细化管理。malloc 的实现原理内存的精细化管理我们要考虑两个因素一是分配和回收的效率二是内存区域的有效利用率内存区域的有效利用率又包含两个方面一个方面是每一小块内存内部是否被合理利用另一个方面是块与块之间是否存在无法利用的小块内存。你可以用建筑规划来进行类比。我们有一块很平整的地如果一个建筑设计得不合理比如本来只有一千个学生但却修了一个五千人的体育场这就是内部空间的浪费。如果各个建筑都是奇形怪状的不能对齐那么建筑与建筑之间的不可用的地块就会增多这就是外部空间的浪费或者称为碎片。对小块内存进行精细化管理最常用的数据结构就是链表。为了能够方便地进行分配和回收人们把空闲区域记录到链表里这就是空闲链表 (free list)。空闲链表空闲链表里的节点主要是为了记录内存的开始位置和长度如下图所示图中展示了一个总长度为 100 的内存区域已经分割成 16、16、20、16、16、16 六个小的内存块。其中着色部分也就是第一、第三和第五块内存是已经分配出去的正在使用的内存而白色区域则是尚未分配的内存。图的上半部分代表空闲链表每一块未分配的内存都会由一个空闲链表的节点进行管理。结点中记录了这块空闲内存区域的起始位置和长度。当分配内存的请求到达以后我们就通过遍历 free list 来查找可用的空闲内存区域在找到合适的空闲区域以后就将这一块区域从链表中摘下来。比如要请求的大小是 m就将这个结点从链表中取下把起始位置向后移动 m大小也相应的减小 m。将修改后的结点重新挂到链表上。在释放的时候将这块区域按照起始起址的排序放回到链表里并且检查它的前后是否有空闲区域如果有就合并成一个更大的空闲区。这种算法所使用的数据结构比较简单算法也很直接我们把这种算法称为简单算法 (Naive Algorithm)。我们举个例子说明简单算法的运行过程假如在算法开始时内存的情况如下图所示假设对内存的操作序列是这样的void test() { void* p1 malloc(16); void* p2 malloc(16); void* p3 malloc(20); free(p2); void* p4 malloc(16); void* p5 malloc(16); free(p4); }执行完 test 函数以后内存的划分就会和这节课的第一幅图一样了。做为练习请你自己画出每一个步骤 free list 和内存的变化情况这里不再给出。如果此时又到达了一个内存分配请求要申请一个大小为 20 的内存区域虽然所有空闲区域的大小之和是 48是超过 20 的但是由于这三块空闲区域并不连续所以我们已经无法从这 100 字节的内存中再分配出一块 20 字节的内存区域了相对于这次请求这三块 16 字节的空闲区域就是内存碎片。这就是我们所介绍的简单算法的第一个缺陷会产生内存碎片。每一次分配内存时我们都需要遍历 free list最差情况下的时间复杂度显然是 O(n)。如果是多线程同时分配的话free list 会被多线程并发访问为了保护它就必须使用各种同步机制比如锁或者无锁的 concurrent linked list 等。可见上述算法的第二个缺陷是分配效率一般且多线程并发场景下性能还会恶化。为了改进以上两个问题人们想了很多办法我们举几个历史上曾经出现的改进方案。其中一种方案是直接对简单算法进行优化。简单算法中找到第一个可用的区域就返回这个策略被称为 First Fit优化的具体做法是把它改成最佳匹配 (Best Fit)改造后它要找到能满足条件的最小的空闲区域才返回。从直观上说这种分配策略能尽可能地保留大块内存避免它被快速地分割成小块内存这就能更好地对抗内存碎片。严格的理论证明也证明了这一点。但是这种策略需要遍历整个链表时间复杂度反而变差。另一种方案是 Knuth 提出的 Next Fit 策略即每次查找不必从头开始而是从上一次查找的位置继续向后查找。实验也证明这种策略会比从头开始的算法有更高的效率。但它依然不能解决内存碎片的问题。还有一种改进方案名字叫分桶式管理这种改进是一种相对均衡的做法在对抗内存碎片和分配释放的时间复杂度两个方向都有改善。这也是在现实中被使用的最广泛的一种方法。接下来我们就重点分析分桶式管理算法。分桶式内存管理分桶式内存管理采用了多个链表对于单个链表它内部的所有结点所对应的内存区域的大小是相同的。换句话说相同大小的区域会挂载到同一个链表上。最常见的方式是以 4 字节为最小单位把所有 4 字节的区域挂到同一个链表上再把 8 字节的区域挂到一起然后是 16 字节32 字节这样以 2 次幂向上增长。如下图所示采用了新的数据结构以后分配和回收的算法也相应地发生了变化。首先分配的时候我们要只要找到能满足这一次分配请求的最小区域然后去相应的链表里把整块区域都取下来。比如分配一个 7 字节的内存块时我们就可以从 8 字节大小的空闲链表里直接取出链表头上的那块区域分配给应用程序。由于从链表头上删除元素的时间复杂度是 O(1)所以我们分配内存的效率就大大提高了。由于整个大块内存被提前分割成了整齐的小块比如是以 4 字节对齐所以整个区域里不存在块与块之间内存碎片。但是这种做法还是会产生区域内部的空间浪费比如上面举的例子当申请的内存大小是 7 时按当前算法只能分配给它大小为 8 的块这就造成了一个字节的内部浪费或者称之为内部碎片。内部碎片带来的问题是内存使用率没有达到 100%在最差情况下可能只有 50%。但是内部碎片随着这一块区域的释放也就消失了所以不会因为长时间运行而积累成严重的问题。释放时只需要把要释放的内存直接挂载到相应的链表里就可以了。 这个速度和分配是一样的效率非常高。分桶式内存管理比简单算法无论是在算法效率方面还是在碎片控制方面都有很大的提升。但它的缺陷也很明显区域内部的使用率不够高和动态扩展能力不够好。例如4 字节的区域提前消耗完了但 8 字节的空闲区域还有很多此时就会面临两难选择如果直接分配 8 字节的区域则区域内部浪费就比较多如果不分配则明明还有空闲区域却无法成功分配。为了解决上述两个问题人们在分桶的基础上继续改进让内存可以根据需求动态地决定小的内存区域和大的内存区域的比例。这种设计的典型就是伙伴系统我们一起来看下。伙伴系统正如上面的例子所讲的当系统中还有很多 8 字节的空闲块而 4 字节的空闲块却已经耗尽这时再有一个 4 字节的请求则会出现 malloc 失败的情况。为了避免分配失败我们其实还可以考虑将大块的内存做一次拆分。如下图所示。分配一块 4 字节大小的空间在 4 字节的 free list 上找不到空闲区域系统就会往上找假如 8 字节和 16 字节的 free list 中也没有空闲区域就会一直向上找到 32 字节的 free list。伙伴系统不会直接把 32 的空闲区域分配出去因为这样做的话会带来巨大的浪费。它会先把 32 字节分成两个 16 字节把后边一个挂入到 16 字节的 free list 中。然后继续拆分前一半。前一半继续拆成两个 8 字节再把后一半挂入到 8 字节的 free list最后把前一半 8 字节拿去分配当然这里也要继续拆分成两个 4 字节的空闲区域其中一个用于本次 malloc 分配另一个则挂入到 4 字节的 free list。分配后的内存的状态如下所示这种不断地把一块内存分割成更小的两块内存的做法就是伙伴系统这两块更小的内存就是伙伴。 它的好处是可以动态地根据分配请求将大的内存分割成小的内存。当释放内存时如果系统发现与被释放的内存相邻的那个伙伴也是空闲的就会把它们合并成一个更大的连续内存。通过这种拆分系统就变得更加富有弹性。malloc 的实现在历史上先后共有几十种策略这些策略往往就是上述三种算法的组合。具体到 glibc 中的 malloc 实现它就采用了分桶的策略但是它的每个桶里的内存不是固定大小的而是采用了将 1 ~ 4 字节的块挂到第一个链表里将 5 ~ 8 字节的块挂到第二个链表里将 9~16 字节的块挂到第三个链表里依次类推。在单个链表内部则采用 naive 的分配方式比如要分配 5 个字节的内存块我们会先在 5 ~ 8 这个链表里查找如果查找到的内存大小是 8 字节的那就会将这个区域分割成 5 字节和 3 字节两个部分其中 5 字节用于分配剩余的 3 字节的空闲区域则会挂载到 1~4 这个链表里。可见 malloc 的实现策略是比较灵活的针对不同的场景不同的分配策略的性能表现也是不一样的。很多公司的基础平台都选择自己实现内存池来提供 malloc 接口这样可以更好地服务本公司的业务。最著名的例子就是 Google 公司实现的 Tcmalloc 库。Tcmalloc 相比起其他的 malloc 实现最大的改进是在多线程的情况下性能提升。我们知道在多线程并发地分配内存时每次分配都要对 free list 进行加锁以避免并发程序带来的问题这就容易形成性能瓶颈。为了解决这个问题Tcmalloc 引入了线程本地缓存 (Thread Local Cache)每个线程在分配内存的时候都先在自己的本地缓存中寻找如果找到就结束只有找不到的情况才会继续向全局管理器申请一块大的空闲区域然后按照伙伴系统的方式继续添加到本地缓存中去。在实际工作中你可能会遇到这两个问题而束手无策第一个问题是系统所提供的 malloc其性能不足以支撑自己的业务或者自己的业务在分配内存时有其特殊的规律需要为它做专门的订制和优化第二个问题是在 malloc 和 free 里做一些统计动作以排查问题比如打印日志。下面我来带你自己动手实现内存管理库让你更好解决内存问题的同时还可以深入地理解内存管理的更多技术细节。自己动手实现内存管理库第 1 个问题的典型代表就是上面所提到的 Tcmalloc。我们这里举一个第二个问题的例子。比如我曾经遇到过一个 double free 的错误在申请了一段内存以后经过复杂的逻辑有两个指针指向了同一块内存当我对两个指针都调用 free 方法的时候错误就发生了我把这个错误示例进行了简化并把它的代码放在下面#include stdio.h #include stdlib.h int main() { int* p (int*)malloc(sizeof(int)); char* q (char*)p; free(p); free(q); }很明显第 8 行第 9 行释放的是同一块内存运行这个例子我们会看到进程 crash 了并且系统提示为*** Error in ./dfree: double free or corruption (fasttop): 0x000000000196a010 *** Aborted这就是 double free 的错误也就是说一块内存被释放了两次。这个例子比较简单但是在复杂逻辑中我们往往很难判断多个指针是否指向相同的地址。如果我们在所有调用 free 的地方增加日志把要释放的指针记录下来就会比较有助于分析和定位问题。幸运的是我们确实有这种手段那就是 Linux 的 preload 机制。在第 8 节课我们深入地学习了 Loader 的原理我们知道对于未定义的引用动态链接器要先进行解析它会先搜索 LD_PRELOAD 目录下的动态库然后再搜索其他的库所以我们就有办法对 malloc 和 free 函数进行替换。比如自己提供 free 的实现#define _GNU_SOURCE #include stdio.h #include stdlib.h #include dlfcn.h void free(void *ptr) { void(*freep)() NULL; printf(ready to do free: %p\n, ptr); freep dlsym(RTLD_NEXT, free); freep(ptr); printf(free done: %p\n, ptr); }我们先来分析一下上面的代码我要提醒一下你第 1 行的 _GNU_SOURCE 是一定要添加的因为第 10 行的 RTLD_NEXT 宏依赖于这个宏。接着我们定义了一个函数指针第 7 行它可以指向真正的 free 的实现。然后分别在调用 free 前和调用 free 以后打印一次要释放的指针第 9 行和第 12 行再通过 dlsym 打开了 glibc 中的 free 方法第 10 行dlsym 的作用是通过符号名称找到符号对应的地址。标题二你还要注意的是第 10 行使用 RTLD_NEXT 就是告诉 ld-linux.so 不要在当前文件中找 free 这个符号而是要按照动态库的搜索顺序找到下一个动态库并在它里面寻找 free 函数实际上这里找到的就是 glibc 里的 free 函数了。分析完这个代码以后我们发现这里自己定义的 free 方法不过是 glibc 里的 free 方法的一个包装 (wrapper)。接着我们使用以下命令编译 myfree 库并设置 preload 再执行 dfree 用例$ gcc -shared -fpic -o myfree.so myfree.c -ldl $ LD_PRELOAD./myfree.so ./dfree ready to do free: 0x1b44010 free done: 0x1b44010 ready to do free: 0x1b44010 *** Error in ./dfree: double free or corruption (fasttop): 0x0000000001b44010 *** Aborted运行上面的代码你可以看到我们新添加的日志已经可以正确输出了。通过这种方式我们就重载了 free 方法。总结我们这节课深入地介绍了 malloc 方法的实现原理并以一个例子来说明如何设计自己的动态内存管理器。通过这节课的学习我们了解到 sbrk 和 mmap 是操作系统提供的系统调用系统调用性能不够且不能对分配的内存进行有效管理所以必须有人在用户态将大块的内存分割成小块然后进行更精细的分配和回收这个工作通常情况下是由 glibc 承担的。glibc 所提供的 malloc 在管理内存时采用了空闲链表 (free list) 的方式。对 free list 的组织有简单算法、分桶管理和伙伴系统等不同的策略。我们评价一个管理内存算法的因素主要有以下三个维度数据结构如何设计是否存在内存碎片分配的效率释放的效率。我把三种算法按照上面三个维度总结成以下表格你可以参考一下由于动态链接器只识别第一次遇到的符号所以我们就有机会通过重写 glibc 中的方法来实现自己的内存管理库。这主要是为了提升性能或者是为了排查错误。我们以 double free 为例介绍了典型的内存错误并通过覆写 free 函数来解决它。这展示了一个完整的设计内存管理库的过程。
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
