glibc 内存分配与回收过程图解

Question

本文分为三个等级自顶向下地分析了 glibc 中内存分配与回收的过程。本文不过度关注细节，因此只是分别从 arena 层次、bin 层次、chunk 层次进行图解，而不涉及有关指针的具体操作。

前言

在展开本文之前，先解释一下本文中会提到的三个重要概念：arena，bin，chunk。三者在逻辑上的蕴含关系一般如下图所示（图中的 chunk 严格来说应该是 Free Chunk）。

三者概念的解释如下：

• arena：通过 sbrk 或 mmap 系统调用为线程分配的堆区，按线程的类型可以分为2类：
  • main arena：主线程建立的 arena；
  • thread arena：子线程建立的 arena；
• chunk：逻辑上划分的一小块内存，根据作用不同分为4类：
  • Allocated chunk：即分配给用户且未释放的内存块；
  • Free chunk：即用户已经释放的内存块；
  • Top chunk
  • Last Remainder chunk
• bin：一个用以保存 Free chunk 链表的表头信息的指针数组，按所悬挂链表的类型可以分为4类:
  • Fast bin
  • Unsorted bin
  • Small bin
  • Large bin

在这里读者仅需明白 arena 的等级大于 bin 的等级大于（free）chunk 的等级即可，即 A>B>C。

tips：实际内存中，main arena 和 thread arena 的图示如下（单堆段）。

其中 malloc_state 的 数据结构 描述在源代码中的位置请点 这里，可以发现该数据结构中保存着 fastbinsY、top、last_remainder、bins 这四个分别表示 Fast bin、Top chunk、Last Remainder chunk、bins（Unsorted bin、 Small bin、Large bin）的数据。

Arena 级分析

此处从 Arena 的层次分析内存分配与回收的过程。

main arena 中的内存申请

main arena 中的内存申请的流程如下图所示：

第一次申请

• 根据申请内存空间大小是否达到 mmap 这一系统调用的分配阈值，决定是使用 sbrk 系统调用 还是 mmap 系统调用申请堆区。一般分配的空间比申请的要大（详见此处），这样可以减少后续申请中向操作系统申请内存的次数。
• 举例而言，用户申请 1000 字节的内存，实际会通过sbrk系统调用产生 132KB 的连续堆内存区域。
• 然后将用户申请大小的内存返回。（本例中将返回1000字节的内存。）

后续申请

• 根据 arena 中剩余空间的大小决定是继续分配还是扩容，其中包含扩容部分的为 top chunk。
• 然后将用户申请大小的内存返回。

tips：

• top chunk 不属于任何 bin！只有 free chunk 依附于 bin！
• 分配阈值具有默认值，但会动态调整；
• 扩容具体过程见库函数 sYSMALLOc 。

thread arena 中的申请

thread arena 中的内存申请的流程如下图所示：

其流程类似于 main arena 的，区别在于 thread arena 的堆内存是使用 mmap 系统调用产生的，而非同主线程一样可能会使用sbrk系统调用。

tips：Arena 的数量与线程之间并不一定是一一映射的关系。在32位系统中有着 Number of arena = 2 * number of cores + 1 的限制。有关多线程控制详见之前的文章中第二章第三节的 Multiple Heaps。

内存回收

线程释放的内存不会直接返还给操作系统，而是返还给 glibc malloc。

bin 级分析

此处从 bin 的层次分析内存分配与回收的过程。考虑到内存回收的过程比内存分配的过程要复杂，因此这里先分析内存回收的过程，再分析内存分配的过程。

内存回收

内存回收的流程如下图所示：

在第一章中我们已经对 bin 有了最基本的了解，我们提到了 bin 可以分为4类：Fast bin、Unsorted bin、Small bin 和 Large bin。保存这些 bin 的数据结构为 fastbinsY 以及 bins：

• fastbinsY：用以保存 fast bins。（可索引大小16~64B的内存块）
• bins：用以保存 unsorted、small 以及 large bins，共计可容纳126个：
  • Bin 1 – unsorted bin
  • Bin 2 to Bin 63 – small bin(可索引大小<512B的内存块)
  • Bin 64 to Bin 126 – large bin（可索引大小≥512B的内存块）

在内存被释放的时候，被释放内存块会根据其大小而被添加入对应的 bin 中：

• 16~64B的内存块会被添加入fastbinY中
• samll及large的会添加在bins中的unsorted bins中。

tips：small bins 和 large bins 中索引的内存块是在内存分配的过程中被添加在相应的 bin 中的。

内存分配

内存分配的流程如下图所示：

我们知道，内存分配的最终目的在于分配出合适大小的内存块返回给用户。在实现中即为在 bin 或 top chunk 中找到（并分割出）所需内存块，其检索的优先级从高到低分别是：

1. fastbinY
2. small bins
3. unsorted bins
4. large bins
5. top bins

具体分配过程详见下章。本章中读者了解检索的顺序即可。

tips：

• Fast bin、Unsorted bin、Small bin 和 Large bin 中保存的都是用户曾经释放的内存块（可能经过合并）；
• top chunk 包含 Arena 扩容的部分，不属于任何 bin！

chunk 级分析

本文不过度关注操作细节，因此有关内存回收的过程就不赘述了。下图即内存分配的详细过程图：

tips：保存或新窗口打开图片可以查看原图。

具体分配说明参见下列引用内容：

1、获取分配区的锁，为了防止多个线程同时访问同一个分配区，在进行分配之前需要取得分配区域的锁。线程先查看线程私有实例中是否已经存在一个分配区，如果存在尝试对该分配区加锁，如果加锁成功，使用该分配区分配内存，否则，该线程搜索分配区循环链表试图获得一个空闲（没有加锁）的分配区。如果所有的分配区都已经加锁，那么ptmalloc会开辟一个新的分配区，把该分配区加入到全局分配区循环链表和线程的私有实例中并加锁，然后使用该分配区进行分配操作。开辟出来的新分配区一定为非主分配区，因为主分配区是从父进程那里继承来的。开辟非主分配区时会调用mmap()创建一个sub-heap，并设置好top chunk。

2、将用户的请求大小转换为实际需要分配的chunk空间大小。

3、判断所需分配chunk的大小是否满足chunk_size <= max_fast (max_fast 默认为 64B)，如果是的话，则转下一步，否则跳到第5步。

4、首先尝试在 fast bins 中取一个所需大小的chunk分配给用户。如果可以找到，则分配结束。否则转到下一步。

5、判断所需大小是否处在small bins中，即判断chunk_size < 512B是否成立。如果chunk大小处在small bins中，则转下一步，否则转到第6步。

6、根据所需分配的chunk的大小，找到具体所在的某个small bin，从该bin的尾部摘取一个恰好满足大小的chunk。若成功，则分配结束，否则，转到下一步。

7、到了这一步，说明需要分配的是一块大的内存，或者small bins中找不到合适的 chunk。于是，ptmalloc首先会遍历fast bins中的chunk，将相邻的chunk进行合并，并链接到unsorted bin中，然后遍历unsorted bin中的chunk，如果unsorted bin只有一个chunk，并且这个chunk在上次分配时被使用过，并且所需分配的chunk大小属于small bins，并且chunk的大小大于等于需要分配的大小，这种情况下就直接将该chunk进行切割，分配结束，否则将根据chunk的空间大小将其放入small bins或是large bins中，遍历完成后，转入下一步。

8、到了这一步，说明需要分配的是一块大的内存，或者small bins和unsorted bin中都找不到合适的 chunk，并且fast bins和unsorted bin中所有的chunk都清除干净了。从large bins中按照“smallest-first，best-fit”原则，找一个合适的 chunk，从中划分一块所需大小的chunk，并将剩下的部分链接回到bins中。若操作成功，则分配结束，否则转到下一步。

9、如果搜索 fast bins 和 bins 都没有找到合适的 chunk，那么就需要操作 top chunk 来进行分配了。判断 top chunk 大小是否满足所需chunk的大小，如果是，则从top chunk中分出一块来。否则转到下一步。

10、到了这一步，说明 top chunk 也不能满足分配要求，所以，于是就有了两个选择: 如果是主分配区，调用 sbrk()，增加 top chunk 大小；如果是非主分配区，调用 mmap 来分配一个新的sub-heap，增加top chunk大小；或者使用mmap()来直接分配。在这里，需要依靠chunk的大小来决定到底使用哪种方法。判断所需分配的chunk大小是否大于等于 mmap 分配阈值，如果是的话，则转下一步，调用mmap分配，否则跳到第12步，增加top chunk 的大小。

11、使用 mmap 系统调用为程序的内存空间映射一块 chunk_size align 4kB 大小的空间。 然后将内存指针返回给用户。

12、判断是否为第一次调用 malloc，若是主分配区，则需要进行一次初始化工作，分配一块大小为（chunk_size + 128KB）align 4KB 大小的空间作为初始的 heap。若已经初始化过了，主分配区则调用sbrk() 增加 heap 空间，分主分配区则在 top chunk 中切割出一个 chunk，使之满足分配需求，并将内存指针返回给用户。

本篇文章综合了本人对 理解 glibc malloc 翻译时的理解、对源代码的比对，其中有关分配的具体流程主要参考了华庭（庄明强）的 gblic内存管理——ptmalloc2源代码分析 的有关工作。