概述

在我的一篇文章 动态内存分配 里面，我纸上谈兵得说了一下我对于运行时动态内存分配的一些理论知识的总结。对于 CS 的东西，如果只是谈理论未毕太空泛，总要拿一些真实的东西来验证或者实现一番才是有意思的地方。所以，这里我先选择拿 C 语言标准库中的 malloc 和 free 函数作为样例，来分析一下。因为可能有不同的实现，所以我分析的是 GLIBC 的。

一些概念

• Arena：被多个线程共享的数据结构，引用一个到多个 Heap；
• Heap：一段连续的内存，被细分为一个个分配单元：块。一个 Heap 只属于一个 Arena；
• Chunk：一小段范围的内存，可处于被分配/空闲状态，可以和相邻的块组成更大的范围；
• Memory：应用程序地址空间中的一部分（可能是 RAM 和 Swap 分区）

数据结构

Chunk 结构

在 malloc 内部，Chunk 是一段内存，大小不一定，任何时刻，Chunk 可能的状态只有两种：

• 在使用
• 空闲

区分这两个状态的方法就是 Chunk 头部 8 个字节中的最后三位，这三位作为标志位存在，分别为：

• A (0x04)
  • 如果 == 1，这个 chunk 来自于 mmap
  • 如果 == 0，这个 chunk 从 main arena 中的 main heap 中分配而来；
• M (0x02)：这个 Chunk 是通过 mmap 分配的，不归 heap 管；
• P (0x01)：前面的 Chunk 是否在使用
  • 如果 == 1，前面的块正在被应用使用，prev_size 字段是无效的；
  • 如果 == 0，前面的块是空闲的，可以考虑合并；

Heap 和 Arena

在最普通的情况，malloc 只持有一个 Heap（连续的内存），并且这个 Heap 归属于一个 Arena；但是，有时一个 Heap 不够用，所以需要扩展 Heap，这样一个 Arena 就会管理两个 Heap，随着 Heap 的增多，Arena 管理的 Heap 也可能随之增多。

Arena 的数据结构寄托在第一个 Heap 中，结构差不多这样：

为了方便找到最大块的 Chunk，所以在 Arena 中有一个 “Top Chunk” 用于指向最大的 Chunk。

Chunk 在 Heap 中有多种形式，但是根据实际情况，可以笼统分为两类：

• 小块：具有相同大小的 Chunk，都放在一条单向链表中保存
• 大块：可以具有不同大小的 Chunk，由双向链表来组织

因为小块都具有相同大小，所以可以直接放入单向链表中，并且都不需要排序了，因为大家大小都相同，当要分配小块内存的时候，直接从表头拿一块去用就好了（存在内部碎片？）

大块就不行了，因为大块的大小不同，所以需要按照块的大小从大到小排序放置，之所以大的在前面，是因为这样就可以以最快的速度找到满足需要块大小的 Chunk 了。块的组织形式是这样的：

上面是小块，只需要单向链表即可，下面是大块，需要双向链表，同时，在搜索大块内存的时候，如果存在两块不同 Size 的 Chunk 都满足需求，那么就选第二块，所以，大块 Chunk 的结构还更复杂一些：

这里还会有下一个 Size 和前一个 Size 的指针，只为了满足下一块的要求。这里所谓的 bins 就是存放空闲块的链表指针，这里只说空闲块，是因为非空闲块（被分配的块）都不需要 Arena 来管理。

事实上，malloc 的内部链表不只有两条，除了小块和大块之外，还有两条：

• Fast：被分配在不同大小规则的 Chunk，和 Small 链不同的在于这条链的 Chunk 不会被合并，如果有必要，可以移到其他链中；
• Unordered：被使用的 Chunk 被先放置在这里，如果下一次申请 Chunk 合适的话，会优先从这里分配出去，如果都是在释放 Chunk，那么这里的 Chunk 会被排序放回对应的链中；

tcache

假如有多个 Thread 同时在使用 malloc，那么 Arena 就可能会产生瓶颈，所以这里有两个处理方式，一个是允许多个 Arena，但是没法避免多个 Thread 使用同一个 Arena 的问题，所以 Arena 中包含了 mutex，但是，每次每隔 Thread 需要分配内存的时候都去获取一下锁性能也是不行的，所以 glibc 的实现就允许 Thread Local cache 的存在，也就是说，Thread 可以先从 Arena 中预支一部分的 Chunk，然后如果有需要的时候就先用预支的 Chunk，不够了再从 Arena 中再预支。

虽然再 tcache 中也是单向链表，但是，是多条单向链表，每个单向链表维护的 Chunk 的 Size 不同。

malloc 的实现

malloc 的实现和 动态内存分配 这里的理论比较吻合，有很多一致的地方，所以看起来会容易一些，但是，malloc 在实现的时候，会有一些更好的优化组织形式，值得好好学习一个。

根据前面介绍的数据结构，这些总结一下 malloc 的分配流程，当需要申请一块内存时：

1. 先从 tcache 中寻找，如果有合适的，那就拿去用吧；
2. 如果请求的 Chunk 超过一定的大小，那么直接通过 mmap 分配；
3. 在 fast 链中查找，如果有合适的，那么就拿去用；
4. 在 small 链中查找，如果有合适的，就直接拿去用；
5. 将 fast 链中的 chunk 放到 unsorted 中，并且合并他们；之后再从 unsorted 链中拿出元素并且放回到 small/large 链中，并且合并，如果发现有合适大小的，那么拿来用就好了；
6. 在 large 链中查找合适的大小，如果有合适的，那么就拿去用；
7. 如果 fast 链中还有 chunk，重复 5 和 6，如果找到合适的，也拿来用了；
8. 如果还没有，那就得去 “top chunk” 中获取了，如果有必要，可以扩充一下 “top chunk”。

free 实现

free 的操作有几种可能：

• 如果 tcache 有空位，那么可以放进去；
• 如果是足够小的 chunk，那么可以放到 fast 链中；
• 如果是 mmap 的，那么可以 munmap 释放；
• 可以和其他空闲块合并；
• 如果不是 “top chunk” 的话，可以放回到 unsorted 链中；
• 如果是个比较大的 chunk，那么可以考虑和 fast 链中的一些 chunk 合并，然后看和 “top chunk” 比较，如果可以的话，可以将 “top chunk” 还给 OS。

realloc 实现

对于 realloc，也可以分为几种情况：

1. 如果是 NULL 或者是 size 为 0 的 realloc，那么其实就是一个 alloc 的过程
2. 如果是 mmap 的 chunk
   1. 如果系统支持 mremap，那么就调用 mremap，至于指针会不会变，那么就看 Kernel 怎么实现了；
   2. 如果不支持 munmap，并且新的 size 比当前小，那么就直接返回旧指针
   3. 如果比当前大，那么就使用只能扩张，并且malloc-copy-free。
3. 如果是 Arena 管理的 Chunk
   1. 如果是减小的，并且值得做，那么就分割一下块，把前半部分返回，后半部分当作空闲 chunk；
   2. 如果是扩张的，并且判断有足够的空闲块可以合并，那么就合并后返回旧指针；
   3. 如果是扩张的，但是没有足够的 chunk 合并，那么新开一块并 malloc-copy-free。

Ref

• MallocInternals