malloc/free 是 C 语言编程中最常见的内存分配函数，并且有着 dlmalloc、ptmalloc2、jemalloc 和 tcmalloc 等不同实现。不同的内存分配器由于其实现原理的不同而有着不同的性能表现。本文将从以下问题思考，并介绍 malloc 的基本原理和常见实现。

  • 堆的内存怎样从内核中申请的？
  • 怎样有效地进行内存管理？
  • 堆内存是通过内核，库还是堆本身进行管理？
  • 堆的一些相关问题能被利用吗？

背景介绍

malloc/free

malloc 分配指定大小的内存空间，返回一个指向该空间的指针。大小以字节为单位。返回 void* 指针，需要强制类型转换后才能引用其中的值。

free 释放一个由 malloc 所分配的内存空间。ptr 指向一个要释放内存的内存块，该指针应当是之前调用 malloc 的返回值。

1
2

void *malloc(size_t size)
void free(void *ptr)

使用示例：

1
2
3

int* ptr;
ptr = (int*)malloc(10 * sizeof(int));	/* 进行强制类型转换 */
free(ptr);

ptmalloc2

ptmalloc2来自于 dlmalloc 的分支。在其基础上添加线程支持并于 2006 年发布。正式发布后，patmalloc2 集成到 glibc 源码中。随着源码集成，代码修改便直接在 glibc malloc 源码里进行。因此 ptmalloc2 的实现与 glibc malloc 有很多不同。

在早期的Linux 里，dlmalloc 被用做默认的内存分配器。但之后因为 ptmalloc2 添加了线程支持，ptmalloc2 成为了 Linux 默认内存分配器。线程支持可帮助提升内存分配器以及应用程序的性能。在 dlmalloc 里，当两个线程同时调用 malloc 时，只有一个线程能进入到临界段，因为这里的空闲列表是所有可用线程共用的。因此内存分配器要在多线程应用里耗费时间，从而导致性能降低。然而在 ptmalloc2 里，当两个线程同时调用 malloc 时，会立即分配内存。因为每个线程维护一个单独的堆分段，因此空闲列表维护的这些堆也是独立的。这种维护独立堆以及每一个线程享有空闲列表数据结构的行为被称为 Per Thread Arena。

进程地址空间

如图所示在一个 32 位系统中，可寻址的空间大小是 4G，linux 系统下 0-3G 是用户模式，3-4G 是内核模式。在用户模式下又分为

  • text：代码段主要存放进程的可执行二进制代码，字符串字面值和只读变量
  • data：数据段存放已经初始化且初始值非 0 的全局变量和局部静态变量
  • bss：bss 段则存放未初始化或初始值为 0 的全局变量和局部静态变量
  • heap：堆段则是存放由用户动态分配内存存储的变量
  • stack：栈段则主要存储局部变量、函数参数、返回地址等

bss 段、数据段和代码段是可执行程序编译时的分段，运行时还需要栈和堆。将应用程序加载到内存空间执行时，操作系统负责代码段、数据段和 bss 段的加载，并在内存中为这些段分配空间。栈也由操作系统分配和管理，而堆则是由程序员自己管理。

**内存映射段(mmap)**的作用是：内核将硬盘文件的内容直接映射到内存，任何应用程序都可通过 Linux 的 mmap() 系统调用请求这种映射。

  • 内存映射是一种方便高效的文件 I/O 方式， 因而被用于装载动态共享库。

  • 用户也可创建匿名内存映射，该映射没有对应的文件，可用于存放程序数据。

    在 Linux 中，若通过 malloc() 请求一大块内存，C 运行库将创建一个匿名内存映射，而不使用堆内存。“大块”意味着比阈值 MMAP_THRESHOLD 还大，缺省为 128KB，可通过 mallopt() 调整。

  • mmap 映射区向下扩展，堆向上扩展，两者相对扩展，直到耗尽虚拟地址空间中的剩余区域。

brk/sbrk

Linux 提供了两个系统调用 brk 和 sbrk：

1
2
3

#include <unistd.h>
int brk(void *addr);
void *sbrk(intptr_t increment);
  • brk 函数将 break 指针，也就是 brk 的上界地址，直接设置为某个地址
    • brk 在执行成功时返回 0，否则返回 -1 并设置 errno 为 ENOMEM
  • sbrk 将 break 指针从当前位置移动 increment 所指定的增量，返回 heap 新的上界 brk 地址
    • sbrk 成功时返回 break 指针移动之前所指向的地址，否则返回 (void *)-1。

我们不会直接通过 brk 或 sbrk 来分配堆内存，而是先通过 sbrk 扩展堆，将这部分空闲内存空间作为缓冲池，然后通过 malloc / free 管理缓冲池中的内存。这是一种池化思想，能够避免频繁的系统调用，提高程序性能。

mmap

mmap 函数定义如下，有两种用法：

  • 映射磁盘文件到内存中
  • 匿名映射：匿名映射不映射磁盘文件，而是向映射区申请一块内存
1
2
3

#include <sys/mman.h>
void *mmap(void *addr, size\_t length, int prot, int flags, int fd, off\_t offset);
int munmap(void *addr, size_t length); // 是用于释放内存，第一个参数为内存首地址，第二个参数为内存的长度

基本思路

减少系统调用

操作系统提供了 sbrk 和 mmap 这些系统调用，可以向操作系统申请内存。为了实现 malloc/free，每次申请内存都进行系统调用成本太大，正确的思路是通过系统调用申请内存池 Memory Pool，然后自己管理。这里面的重点不是向操作系统申请内存，而是对于已经申请到的内存如何管理，如何实现高效的分配算法，提高 malloc/free 性能，减少内存碎片。

先系统调用 sbrk 一次，会得到一段较大的并且是连续的空间。进程把系统内核分配给自己的这段空间留着慢慢用。之后调用 malloc 时就从这段空间中分配，free 回收时就再还回来（而不是还给系统内核）。只有当这段空间全部被分配掉时还不够用时，才再次系统调用 sbrk。当然，这一次调用 sbrk 后内核分配给进程的空间和刚才的那块空间一般不会是相邻的。

malloc 如何使用得到动态内存空间？一次 sbrk 之后，malloc 就会保留着一段大的连续空间（称作堆空间）。之后对于堆空间 malloc 不断地分配，free 不断地收回，这段空间里的格局必定是“乱七八糟”，有的已分配，有的未分配。

四个基本问题

实现动态内存分配往往要考虑以下四个问题：

  • 空闲块组织：我们如何记录空闲块？
  • 选择：我们如何选择一个合适的空闲块来作为一个新分配的块？
  • 分割：在我们选了一个空闲块分配出我们需要的大小之后，我们如何处理这个空闲块中的剩余部分？
  • 合并：我们如何处理一个刚刚被释放的块？

隐式空闲链表

隐式空闲链表通过在分配块头部存储长度信息，隐式给出空闲块链表。当需要遍历整个空闲块集合时，分配器需要遍历所有空闲块和已分配块。内存块的结构如下:

  • Block Header
    • 大小为 4 个字节，为了满足对齐要求，最小的内存块也需要为 8 字节。
    • 在用高 29 位来表示存储块大小，剩余 3 位中利用最低位来表示块是否已分配(1 表示已分配，0 表示空闲)
  • Payload：真正给用户使用的内存
  • Padding：为了保证内存字节对齐而需要的填充

分配请求

  • 首次适配: 每次分配均从头开始搜索空闲链表，选择第一个满足要求的空闲块。
    • pro: 较大空闲内存块位于链表尾部
    • con: 链表起始处会有较多碎片，因此增加对较大块的访问时间
  • 下一次适配: 每次分配从上一次分配处开始搜索
    • pro: 相比于首次适配，运行的更快
    • con: 内存利用率低于首次适配，最优适配内存利用率最高
  • 最优适配: 每次分配检查所有空闲块，选择适合所需请求的最小内存块
    • pro: 吞吐量最差
    • con: 内存利用率最高

分割空闲块

如何处理被选空闲块中的剩余部分？一般来讲，是要把剩余的部分再插入回到空闲链表中去的。

要注意一个空闲块分割成两个块时，需要腾出若干字节作为块的头部尾部等部分。

释放请求

我们如何处理一个刚刚被释放的块？有两种方法：

  • 立即合并: 对每个释放请求尝试合并。

  • 推迟合并: 当分配请求无法满足，扫描整个堆，然后合并。或是采用其它启发式的方式。

  • 立即合并的实现

    • 合并下一个空闲块: 注意到上图的结构相当于一个单链表，因此对下一个块是否空闲可以很容易检查
    • 合并上一个空闲块
      • 边界标记: 改变为双链表，即每个内存块增加一个尾部，其值和首部相同
      • 改进: 注意到仅在前一个为空闲的情况下需要合并前一个，因此考虑将前一个的状态维护在当前块的标记内。同时空闲块需要保留尾部，而已分配块不需要维护。

对于隐式空闲链表，合并的具体过程是，

  • 前后块都已分配：直接释放当前块即可；

  • 前块分配、后块空闲：和后块合并；

  • 前块空闲、后块分配：和前块合并；

  • 前后块都已空闲：和前后块合并；

显式空闲链表

显式空闲链表将空闲块的空间组织成显式的链表。例如将空闲块组织成双链表，指向前后空闲块的指针存放在空闲块中，如下。

此时，首次适配的时间为空闲块的数目，而非所有内存块的数目。

释放请求

释放时间则取决于释放策略:

  • 后进先出: 将新释放的块放在链表头
    • 常数时间定位，若使用边界标记，则也是常数时间合并。
  • 按内存顺序: 链表按内存地址顺序存放
    • 释放需要线性时间以找到前驱。
    • 内存利用率较高。

很明显，显式空闲链表的缺点是空闲块的最小大小必须足够大（以装下指针以及相关数据），等价地，这导致最小分配块大小也较大，因为是由空闲块分割获得，因此提高了内部碎片出现的可能。

分离的空闲链表

上面的两种分配方法，分配时间都和空闲块的数量成线性关系。

另一种实现方式是分离存储，即维护多个空闲链表，其中每个链表中的块有大致相等或者相同的大小。一般常见的是根据 2 的幂来划分块大小。分配时，可以直接在某个空闲链表里搜索合适的块。如果没有找到合适的块与之匹配，就搜索下一个链表，以此类推。

简单分离存储

每个大小类的空闲链表包含大小相等的块。分配时，从某个空闲链表取下一块，或者向操作系统请求内存片并分割成大小相等的块，形成新的链表。释放时，只需要简单的将块插入到相应空闲链表的前面。

  • 优点：

    • 分配和释放只需要在链表头进行操作，都是常数时间
    • 因为每个块大小都是固定的，所以只需要一个 next 指针，不需要额外的控制信息，节省空间。

  • 缺点：

    • 容易造成内部碎片和外部碎片。
    • 内部碎片显而易见，因为每个块都是整体分配的，不会被分割。
    • 外部碎片在这样的模式下很容易产生：应用频繁地申请和释放较小大小的内存块，由于这些内存块不会合并，所以系统维护了大量小内存块形成的空闲链表，而没有多余空间来分配大内存块，导致产生外部碎片。

分离适配

这种方法同样维护了多个空闲链表，只不过每个链表中的块是大致相等的大小，比如每个链表中的块大小范围可能是：

  • 1
  • 2
  • 3~4
  • 5~8
  • …
  • 1025~2048
  • 2049~4096
  • 4097~∞

在分配的时候，需要先根据申请内存的大小选择适当的空闲链表，然后遍历该链表，根据匹配算法（如首次适应）寻找合适的块。如果找到一个块，将其分割（可选），并将剩余部分插入到适当的空闲链表中。如果找不到合适的块，则查找下一个更大的大小类的空闲链表，以此类推，直到找到或者向操作系统申请额外的堆内存。在释放一个块时，合并前后相邻的空闲块，并将结果放到相应的空闲链表中。

分离适配方法是一种常见的选择，C 标准库中提供的 GNU malloc 包就是采用的这种方法。这种方法既快速，对内存的使用也很有效率。由于搜索被限制在堆的某个部分而不是整个堆，所以搜索时间减少了。内存利用率也得到了改善，避免大量内部碎片和外部碎片。

伙伴系统

伙伴系统是分离适配的一个特例，具体而言，每个空闲块为 2 的幂次大小，并以此组织为空闲链表。一个内存块和它的伙伴只有 1 位差异。

分配器策略小结

  • placement policy
    • first-fit, next-fit, best-fit, etc
    • 低吞吐量和较小碎片的折衷
    • 分离空闲列表: 不需要搜索整个空闲列表的近似最佳 placement policy
  • splitting policy
    • 什么时候需要分割空闲块?
    • 能够容忍多少外部碎片?
  • coalescing policy
    • Immediate coalescing: 每次 free 调用就会尝试合并
    • Deferred coalescing: 提高 free 的性能，在需要的时候再合并

ptmalloc2

ptmalloc 实现了 malloc()，free()以及一组其它的函数。以提供动态内存管理的支持。分配器处在用户程序和内核之间，它响应用户的分配请求，向操作系统申请内存，然后将其返回给用户程序，为了保持高效的分配，分配器一般都会预先分配一块大于用户请求的内存，并通过某种算法管理这块内存，来满足用户的内存分配要求，用户释放掉的内存也并不是立即就返回给操作系统，相反，分配器会管理这些被释放掉的空闲空间，以应对用户以后的内存分配要求。

也就是说，分配器不但要管理已分配的内存块，还需要管理空闲的内存块，当响应用户分配要求时，分配器会首先在空闲空间中寻找一块合适的内存给用户，在空闲空间中找不到的情况下才分配一块新的内存。为实现一个高效的分配器，需要考虑很多的因素。比如，分配器本身管理内存块所占用的内存空间必须很小，分配算法必须要足够的快。

获取内存

malloc 有两种方式获取内存，分别为sbrk 和 mmap ，以下为示意图：

malloc
malloc

两者一个明显区别在于，通过sbrk获得的新的堆的内存地址和之前的地址是连续的，而 mmap 获得的地址由参数设定。

当申请小内存的时，malloc 使用 sbrk 分配内存；当申请大内存时，使用 mmap 函数申请内存；但是这只是分配了虚拟内存，还没有映射到物理内存，当访问申请的内存时，才会因为缺页异常，内核分配物理内存。

  • 分配内存 < DEFAULT_MMAP_THRESHOLD，走__brk，从内存池获取，失败的话走 brk 系统调用

  • 分配内存 > DEFAULT_MMAP_THRESHOLD，走__mmap，直接调用 mmap 系统调用

    其中，DEFAULT_MMAP_THRESHOLD 默认为 128k，可通过 mallopt 进行设置。 重点看下小块内存(size > DEFAULT_MMAP_THRESHOLD)的分配，glibc 使用的内存池如下图示：

chunk 数据结构

用户请求分配的空间在 ptmalloc 中都使用一个 chunk 来表示，用户调用 free()函数释放掉的内存也并不是立即就归还给操作系统，相反，它们也会被表示为一个 chunk，ptmalloc 使用特定的数据结构来管理这些空闲的 chunk。

ptmalloc 在给用户分配的空间的前后加上了一些控制信息用于描述这些块。 在 ptmalloc 的实现源码中定义结构体 malloc_chunk 来描述这些块。malloc_chunk 定义如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

struct malloc_chunk {
  INTERNAL_SIZE_T      prev_size;    /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;         /* Size in bytes, including overhead. */

  struct malloc_chunk* fd;           /* double links -- used only if free. */
  struct malloc_chunk* bk;

  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize;      /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

chunk 的定义相当简单明了，对各个域做一下简单介绍 :

  • prev_size: 如果前一个 chunk 是空闲的，该域表示前一个 chunk 的大小，如果前一个 chunk 不空闲，该域无意义。
  • size ：当前 chunk 的大小，并且记录了当前 chunk 和前一个 chunk 的一些属性，包括前一个 chunk 是否在使用中，当前 chunk 是否是通过 mmap 获得的内存，当前 chunk 是否属于非主分配区。
  • fd 和 bk ： 指针 fd 和 bk 只有当该 chunk 块空闲时才存在，其作用是用于将对应的空闲 chunk 块加入到空闲 chunk 块链表中统一管理，如果该 chunk 块被分配给应用程序使用，那么这两个指针也就没有用（该 chunk 块已经从空闲链中拆出）了，所以也当作应用程序的使用空间，而不至于浪费。
  • fd_nextsize 和 bk_nextsize: 当当前的 chunk 存在于 large bins 中时， large bins 中的空闲 chunk 是按照大小排序的，但同一个大小的 chunk 可能有多个，增加了这两个字段可以加快遍历空闲 chunk ，并查找满足需要的空闲 chunk ， fd_nextsize 指向下一个比当前 chunk 大小大的第一个空闲 chunk ， bk_nextszie 指向前一个比当前 chunk 大小小的第一个空闲 chunk 。 如果该 chunk 块被分配给应用程序使用，那么这两个指针也就没有用（该 chunk 块已经从 size 链中拆出）了，所以也当作应用程序的使用空间，而不至于浪费。

Allocated chunk

任何堆内存管理器都是以 chunk 为单位进行堆内存管理的，而这就需要一些数据结构来标志各个块的边界，以及区分已经分配块和空闲块。大多数堆内存管理都将这些边界信息作为 chunk 的一部分嵌入到 chunk 内部，下图为 allocated chunk 的结构：

allocated_chunk
allocated_chunk

size：这部分包含了此处已分配的块的容量大小。

堆内存中要求每个 chunk 的大小必须为 8 的整数倍，因此 chunk size 的后 3 位是无效，为了充分利用内存，堆管理奖这 3 个 bit 比特位用作 chunk 的标志位，最后三位包含以下信息：

  • PREV_INUSE(P) ——如果之前的块已经被分配，该位置 1
  • IS_MMAPPED(M) —— 如果块是 mmap 映射的地址，该位置 1
  • NON_MAIN_ARENA(N) —— 如果该块属于一个 thread arena ，该位置 1

Free chunk

free_chunk
free_chunk

以下是空闲块各个部分内容的说明：

  • prev_size：不能同时调整两个空闲的块。当两个块都空闲时，它就会与一个单独的空闲块连接。因此前一个块及当前这个释放的块会被分配，同时 prev_size 包含前一个块的用户数据。
  • size：这个部分包含有空闲块的 size
  • fd：Forward pointer —— 同一bin里指向下一块的指针（不是指向物理内存内的下一块）
  • bk：Backward pointer —— 同一bin里指向前一块的指针（不是指向物理内存内的前一块）

Bins

malloc 采用的是内存池的实现方式，malloc 内存池实现方式更类似于 STL 分配器和 memcached 的内存池，先申请一大块内存，然后将内存分成不同大小的内存块，然后用户申请内存时，直接从内存池中选择一块相近的内存块即可。

img
img

内存池保存在 bins 这个长 128 的数组中，每个元素都是一双向个链表。

  • bins[0]目前没有使用
  • bins[1]的链表称为 unsorted_list，用于维护 free 释放的 chunk。
  • bins[2,63)的区间称为 small_bins，用于维护＜ 512 字节的内存块，其中每个元素对应的链表中的 chunk 大小相同，均为 index*8。
  • bins[64,127)称为 large_bins，用于维护>512 字节的内存块，每个元素对应的链表中的 chunk 大小不同，index 越大，链表中 chunk 的内存大小相差越大，例如: 下标为 64 的 chunk 大小介于[512, 512+64)，下标为 95 的 chunk 大小介于[2k+1,2k+512)。同一条链表上的 chunk，按照从小到大的顺序排列。

Unsorted Bin

当小块或大块被释放时，它会被添加到 unsorted bin 里。 这给了 glibc malloc 再次利用最近释放的块的机会。因此内存分配以及回收的速度都会有所提升（因为 unsorted bin）由于排除了用于查找合适容器的时间。

  • Bins 的数量——1
    • Unsorted bin 包含空闲块的一个循环双向链表（也称为 binlist 容器列表）
  • 块的大小 – 没有大小限制，任何大小的块都可以放入该 bin。

samll_bin
samll_bin

Small bin

小于 512 bytes 的块叫做 small chunk。 支持 small chunks 的容器叫做 small bins。 Small bins 在内存分配和回收时比 large bins 快（比 fast bins 慢）。

  • Bins 的数量——62
    • 每个 small bin 含有空闲块的一个双向循环链表。在这里使用双向链表的原因在于，在 small bins 里，需要从链表的中间取出块。在这里列表头部实现添加并在列表的后部删除 —— FIFO。
  • 块的大小 —— 以 8 bytes 累加
    • Small bin 中的相邻的两个 binlist 中的块大小相差 8 bytes。举个例子，第一个 binlist 中块的大小为 16 bytes，第二 binlist 中块的大小为 24 bytes，依次类推。
    • 在同一个 binlist 中块的大小相同
  • 合并 —— 两个相邻的空闲块，会被合并为一个空闲块。合并消除了外存储碎片，但是影响运行速度。
  • malloc(small chunk)
    • 初始状态下所有 small bins 都是 NULL，因此即使用户请求一个 small chunk，提供的是 unsorted bin code 而不是 small bin code。
    • 在第一次调用 malloc 期间，在 malloc_state 里发现的 small bin 和 large bin 数据结构（bins）被初始化（即，bins 会指向它自己表示他们是空的）。
    • 之后当 small bin 处于非空状态时，其对应 binlist 中的最后一个块会被移除并返回给用户。
  • free(small chunk)
    • 释放块时，查看其前一个或下一个块是否空闲，如果空闲就合并（即，从他们各自的链表里解除块的链接，然后在 unsorted bin 的链表最开端添加新的合并后的块）。

Large bin

大小大于等于 512 bytes 的块称为 large chunk。支持 large chunks 的 bins 叫作 large bins。Large bins 在内存分配和回收中比 small bins 要慢。

  • Bins 的数量——63
    • 每个 large bin 是由空闲块组成的双向循环链表。在 large bins 里，使用双向循环链表的原因是，我们需要在任意位置增加或删除块。
    • 在这 63 个 bins 之外的情况：
    • 32 个 bins 中，相邻的两个 binlist 中的块大小相差 64 bytes 。
    • 16 个 bins 中，相邻的两个 binlist 中的块大小相差 512 bytes 。
    • 8 个 bins 中，相邻的两个 binlist 中的块大小相差 4096 bytes 。
    • 4 个 bins 中，相邻的两个 binlist 中的块大小相差 32768 bytes 。
    • 2 个 bins 中，相邻的两个 binlist 中的块大小相差 262144 bytes。
    • 1 个 bin，剩余的所有容量都在一个块中。
    • 不同于 small bin，在 large bin 里的块大小是不同的。因此他们以降序排列。最大的块在最前端而最小的块被排到 binlist 的末尾。
  • 合并 —— 两个相邻的空闲块，会合并为一个空闲块。
  • malloc(large chunk)
    • 初始化状态下所有 large bins 都是 NULL，因此即使用户请求一个 large chunk，提供的是下一个最大的 bin code ，而不是 large bin code。
    • 同样在第一次调用 malloc 期间，在 malloc_state 里发现的 small bin 和 large bin 被 初始化。即，bins 会指向它自己表示它们是空的。
    • 此后当 large bin 不为空时，如果最大块的大小（在它的容器列表里）比用户请求的容量还大， binlist 会从 尾部到头部，来查找一个大小接近或等于用户请求大小的合适的块。一旦找到，这个块将分裂为两个块。
    • 用户块（容量为用户请求的大小）—— 返回给用户。
    • 剩余块（容量为剩余容量的大小）—— 添加到 unsorted bin。
    • 如果最大块的大小（在它的容器列表里）小于用户请求的大小，那么尽量使用下一个最大（非空）bin 为用户的请求提供服务。下一个最大的 bin code 会扫描容器映射来查找下一个最大的非空 bin ，如果找到任何一个，从 binlist 里检索到了一个合适的块，分裂并返回给用户。如果没找到，尝试使用 Top Chunk 为用户请求提供服务。
  • free(large chunk) —— 过程与 free(small chunk) 类似

Fast Bin

malloc 除了有 unsorted bin，small bin，large bin 三个 bin 之外，还有一个fast bin。一般的情况是，程序在运行时会经常需要申请和释放一些较小的内存空间。当分配器合并了相邻的几个小的 chunk 之后，也许马上就会有另一个小块内存的请求，这样分配器又需要从大的空闲内存中切分出一块，这样无疑是比较低效的，故而，malloc 中在分配过程中引入了 fast bins，不大于 max_fast(默认值为 64B)的 chunk 被释放后，首先会被放到 fast bins 中，fast bins 中的 chunk 并不改变它的使用标志 P。这样也就无法将它们合并，当需要给用户分配的 chunk 小于或等于 max_fast 时，malloc 首先会在 fast bins 中查找相应的空闲块，然后才会去查找 bins 中的空闲 chunk。在某个特定的时候，malloc 会遍历 fast bins 中的 chunk，将相邻的空闲 chunk 进行合并，并将合并后的 chunk 加入 unsorted bin 中，然后再将 unsorted bin 里的 chunk 加入 bins 中。

大小在 16 到 80 bytes 的块叫做 fast chunk 。支持 fast chunk 的 bin 叫做 fast bins。在上述的这些 bin 里，fast bins 在内存分配和重新分配上更快。（译者注：只有 fast bin 是 LIFO 其他的 bin 都是 FIFO）

  • Bins 的数量——10
    • 每个 fast bin 包含由空闲块组成的单向链表。由于在 fast bins 里，在列表中间块不会被移除，所以使用单向链表。添加和删除都在列表末端进行 —— LIFO。
  • 块的大小 —— 以 8 bytes 累加
    • fast bin 中的相邻的两个 binlist 中的块大小相差 8 bytes。举个例子，第一个 binlist 中块的大小为 16 bytes，第二 binlist 中块的大小为 24 bytes，依次类推。
    • 在同一个 binlist 中块的大小相同
  • 在 malloc 初始化 过程中，最大的 fast bin 的大小设置为 64 (!80) bytes。因此通过块的默认大小设置为 16 到 64 就可以将其划分为 fast chunks 了。
  • 不能合并 —— 空闲的两个块可以相邻，但不能合并为一个空闲块。不能合并导致产生外存储碎片，但它可以大大提速！！
  • malloc(fast chunk)
  • free(fast chunk)
    • 计算 Fast bin 目录以检索其对应的 binlist。
    • 该空闲块被添加到以上检索的 binlist 的最前端。

fast_bin
fast_bin

tcmalloc

TCMalloc 是 Google 开发的内存分配器，在不少项目中都有使用，例如在 Golang 中就使用了类似的算法进行内存分配。它具有现代化内存分配器的基本特征：对抗内存碎片、在多核处理器能够 scale。据称，它的内存分配速度是 glibc2.3 中实现的 malloc 的数倍。

参考 https://zhuanlan.zhihu.com/p/29216091

动手实践

Csapp malloc lab 实现

参考资料