[翻译]GNU C malloc实现原理

原文：https://sourceware.org/glibc/wiki/MallocInternals

Malloc概述⌗

GNU C语言库（glibc）的malloc库包含一些管理应用程序地址空间中分配的内存的函数。glibc的malloc源于ptmalloc（pthreads malloc），而ptmalloc又源于dlmalloc（Doug Lea malloc）。这个malloc是一个 “堆 （heap）“式的malloc，这意味着不同尺寸的chunks（块）存在于一个更大的内存区域（“堆”）中，而不是像其他的实现那样，例如使用位图（bitmaps）和数组（arrays），或者相同尺寸的块（blocks），等等。在以前，每个应用程序只有一个堆，但glibc的malloc允许多个堆，每个堆都在它自己的地址空间内增长。

因此，在本文中，我们参考了一些常用术语：

Arena（竞技场）

在一个或多个线程之间共享的结构，它包含对一个或多个堆的引用（译者注：一般情况下，每个thread arena都只维护一个堆，但是当这个堆的空间耗尽时，新的堆（而非连续内存区域）就会被mmap到这个arena里；），以及这些堆中 “空闲 “的chunk的链表。附属于每个arena的线程将从该arena的空闲列表（free list）中分配内存。

// malloc_state结构体用于记录arena的相关信息
struct malloc_state
{
  /* Serialize access.  */
  __libc_lock_define (, mutex);

  /* Flags (formerly in max_fast).  */
  int flags;

  /* Set if the fastbin chunks contain recently inserted free blocks.  */
  /* Note this is a bool but not all targets support atomics on booleans.  */
  int have_fastchunks;

  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];

  /* Base of the topmost chunk -- not otherwise kept in a bin */
  mchunkptr top;

  /* The remainder from the most recent split of a small request */
  mchunkptr last_remainder;

  /* Normal bins packed as described above */
  mchunkptr bins[NBINS * 2 - 2];

  /* Bitmap of bins */
  unsigned int binmap[BINMAPSIZE];

  /* Linked list */
  struct malloc_state *next;

  /* Linked list for free arenas.  Access to this field is serialized
     by free_list_lock in arena.c.  */
  struct malloc_state *next_free;

  /* Number of threads attached to this arena.  0 if the arena is on
     the free list.  Access to this field is serialized by
     free_list_lock in arena.c.  */
  INTERNAL_SIZE_T attached_threads;

  /* Memory allocated from the system in this arena.  */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

Heap（堆）

一个连续的内存区域，被细分为要分配的chunk。每个堆仅属于一个arena。

// heap_info结构体用于记录heap相关的信息
typedef struct _heap_info
{
  mstate ar_ptr; /* Arena for this heap. */
  struct _heap_info *prev; /* Previous heap. */
  size_t size;   /* Current size in bytes. */
  size_t mprotect_size; /* Size in bytes that has been mprotected
                           PROT_READ|PROT_WRITE.  */
  /* Make sure the following data is properly aligned, particularly
     that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of
     MALLOC_ALIGNMENT. */
  char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];
} heap_info;

Chunk（块）

一个小范围的内存，可以被分配（由应用程序拥有），释放（由glibc拥有），或与相邻的chunk组合成更大的范围。请注意，一个chunk是给应用程序的内存块的包装（ a chunk is a wrapper around the block of memory that is given to the application）。每个chunk存在于一个堆中，属于一个arena。

// malloc_chunk结构体用于记录chunk的相关信息
struct malloc_chunk {
  INTERNAL_SIZE_T      mchunk_prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      mchunk_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;
};

Memory（内存）

应用程序地址空间的一部分，通常由RAM或交换分区（swap）来支持。

注意，在本文中，我们只把 “内存 “作为一个通用术语。虽然在glibc的malloc中有一些代码与Linux内核（或其他操作系统）一起工作，提示哪些内存应该被映射，哪些可以返回给内核，但这种 “真实内存 “和 “虚拟内存 “之间的区别与本文的讨论无关，除非被明确指出。

什么是chunks（块）？⌗

Glibc的malloc是面向chunk（chunk-oriented）的。它将一个大的内存区域（一个 “堆”）分成不同尺寸的chunk。每个chunk包含了元数据，关于它的尺寸（通过chunk头中的size字段），以及相邻的chunk在哪里。当一个chunk被应用程序使用时，唯一被 “记住 “的数据是该chunk的尺寸。当chunk被释放时，之前存放应用程序数据的内存被重新用于记录额外的arena的相关信息，如链表中的指针，这样就可以在需要的时候快速找到合适的chunk并重新使用。另外，被释放的chunk中的最后一个字（word）包含了chunk尺寸的副本（其中最低3位（LSB）置为零，而chunk前部的最低3位（LSB）用做flags标识位）。

在malloc库中，“chunk指针（chunk pointer） “或mchunkptr并不指向chunk的开始，而是指向前一个chunk的最后一个字，也就是说，除非你知道前一个chunk是空闲的，否则mchunkptr中的第一个字段（mchunk_prev_size）是无效的。

由于所有的chunk都是8字节的倍数，chunk尺寸的最低3位可以用来做标志。这三个标志被定义如下：

A(0x04) NON_MAIN_ARENA Allocated Arena- 主arena（main arena）使用应用程序的堆。其他arena（other arenas）使用mmap分配的堆。要将一个chunk映射到一个堆，你需要知道哪种情况适用。如果这个位是0，这个chunk来自主arena和主堆（the main arena and the main heap）。如果这个位是1，那么这个chunk就来自mmap分配的内存，堆的位置可以通过chunk的地址计算出来（见下文）。

M(0x02) IS_MAPPED mmap分配的chunk - 这个chunk是通过调用mmap分配的，完全不是堆的一部分，当这个位被设置时其他两个位无效。

P(0x01) PREV_INUSE 前一个chunk正在使用中 - 如果该位被设置，则前一个chunk仍然被应用程序使用，因此prev_size字段无效。注意，有些chunk，比如fastbins中的chunk（见下文），尽管已经被应用程序释放，但这个位仍会被设置。这个位的真正含义是，前一个chunk不应该被认为是合并（coalesce）的候选者，它正被应用程序或其他在malloc代码上层的优化使用。

为了确保一个chunk的有效载荷区域足够大以覆盖malloc所需的开销，一个chunk的最小尺寸是4*sizeof(void*)（除非size_t与void*的尺寸不同，在64位系统上是32字节）。如果平台的ABI要求额外的对齐方式，最小尺寸可能更大。请注意，prev_size不会将最小chunk的尺寸增加到5sizeof(void)，因为当chunk很小的时候，bk_nextsize指针是不使用的，而当chunk大到可以使用它的时候，就有足够的空间了。

注意，由于chunk在内存中是相邻的，如果你知道堆中第一个chunk的地址（最低地址），你可以通过使用尺寸信息来遍历堆中的所有chunk，但只能通过增加地址来实现，尽管可能很难发现你什么时候碰到了堆中的最后一个chunk。

被分配的堆总是按照2次方的地址对齐。因此，当一个chunk在分配的堆中时（即A位被设置），该堆的heap_info的地址可以根据该chunk的地址来计算。（译者注：64位系统上HEAP_MAX_SIZE为 $ 2^{26} $）

arena和堆（Arenas and Heaps）⌗

为了高效地处理多线程应用程序，glibc的malloc允许在同一时间激活多个内存区域。因此，不同的线程可以访问不同的内存区域而互不干扰。这些内存区域被统称为 “arenas”。有一个arena，即 “主arena”，它对应于应用程序的初始堆。在malloc代码中，有一个静态变量指向这个arena，每个arena都有一个下一个指针来连接其他arena。

随着线程碰撞（thread collisions）的压力增加，额外的arena会通过mmap创建，以缓解压力。arena的数量上限为系统中CPU数量的8倍（除非用户另有规定，见mallopt），这意味着一个大量线程的应用程序仍然会看到一些竞争，但权衡之下，碎片化程度会降低。

每个arena结构中都有一个互斥量（mutex），用来控制对该arena的访问。请注意，一些操作，如对fastbin的访问，可以用原子操作完成，不需要锁住arena。所有其他的操作都需要线程在arena上加锁。对这个互斥量的竞争是创建多个arena的原因，分配到不同arena的线程不需要互相等待。如果需要竞争，线程会自动切换到未使用的（未锁定的）arena。

每个arena从一个或多个堆中获取内存。主arena使用程序的初始堆（从.bss等之后开始）。额外的arena通过mmap为它们的堆分配内存，当旧的堆被用完时，就把更多的堆添加到它们的堆的列表中。每个arena都会跟踪一个特殊的 “top” chunk，这通常是最大的可用chunk，也是指最近分配的堆。

为了方便起见，分配给arena的内存是从该arena的初始堆中取出。

在每个arena内，chunk要么被应用程序使用，要么是空闲的（可用的）。arena不对使用中的chunk进行跟踪。空闲chunk根据尺寸和历史存储在不同的列表中，这样库就可以快速找到合适的chunk来满足分配请求。这些列表被称为 “bins”，有以下4种bin

• Fast

被存储在特定尺寸的bin中的小chunk。添加到"fastbin"中的chunk不会与相邻的chunk结合在一起——这种逻辑是最基本的，为了保持快速访问（因此得名）。fastbin中的chunk可以根据需要被移到其他bin中。fastbin的chunk被存储在一个单一的链表中，因为它们的尺寸都是一样的，列表中间的chunk永远不需要被访问。

• Unsorted

当chunk被释放时，它们最初被存储在一个单一的bin中。之后在malloc中对它们进行排序，以便给它们一个快速重新使用的机会。这也意味着排序逻辑只需要存在于一个地方——其他的地方只需将释放的chunk放入这个bin中，它们之后会被排序。“unsorted” bin只是常规bin中的第一个。

• Small

普通bin分为"small” bins和"large” bins，“small” bins中的每个chunk都是一样大的，“large” bins中的chunk有各种尺寸。当一个chunk被添加到这些仓bins时，它们首先与相邻的chunk结合，将它们"聚合"成更大的chunk。因此，这些chunk永远不会与其他此类chunk相邻（尽管它们可能与fast或unsorted bins相邻，当然还有正在使用的chunk）。小chunk和大chunk是用双向链表链接的，因此，chunk可以从中间移除（例如，当它们与新释放的chunk结合时）。

• Large

如果一个chunk的bin可能包含一个以上的尺寸，那么它就是"large”。对于small bins，你可以选择第一个chunk并直接使用它。对于large bins，你必须找到 “最佳的"chunk，并可能将其分成两个chunk（一个是你需要的尺寸，另一个是剩余的）。

注意：在上图（和下图）中，所有的指针都指向一个 “chunk”（mchunkptr）。由于bin不是chunk（它们是fwd/bck指针的数组），一个hack技巧被用来提供一个mchunkptr到一个"恰好"与bin重叠的类似于chunk的对象，这样mchunkptr的fwd和bck字段就可以用来访问适当的bin。

由于需要找到 “最佳"的large chunks，large chunks有一个额外的双向链表，链表中每个尺寸的第一个，并且chunk按尺寸排序，从大到小。这使得malloc能够快速扫描出第一个足够大的chunk。注意：如果存在多个给定尺寸的chunk，通常选择第二个，这样就不需要调整下一个尺寸的链表。出于同样的原因，插入到列表中的chunk被添加到相同尺寸的chunk之后。

线程本地缓存Thread Local Cache（tcache）⌗

虽然malloc知道有多个线程，但这几乎是它的认知范围——它只知道有多个线程。malloc中没有任何代码可以针对NUMA架构进行优化，协调线程的局部性（locality），按处理器核心（core）对线程进行排序，等等。我们假设内核（kernel）会很好地处理这些问题。

每个线程都有一个线程本地变量（thread-local variable），它会记住最后使用过的arena。如果当一个线程需要使用该arena时，arena正在使用中，那么该线程将阻塞以等待该场馆被释放。如果线程以前从未使用过arena，那么它可能会尝试重新使用一个未使用的arena，创建一个新的arena，或者在全局列表中选择下一个。

每个线程都有一个线程（per-thread）缓存（称为tcache），其中包含一个由chunks组成的小集合，可以在不需要锁arena的情况下被访问。这些chunks被存储为一个单向链表组成的数组中，就像fastbins一样，但链接指向有效载荷（用户区）而不是chunk头部（header）。每个bin包含一个尺寸的chunk，所以数组是（间接地）按chunk的尺寸来索引的。与fastbins不同，tcache限制每个bin中允许有多少个chunk（tcache_count）。如果tcache bin在给定的请求尺寸的情况下是空的，下一个更大尺寸的chunk就不会被使用（因为可能会导致内部碎片），而是退一步，使用正常的malloc例程，也就是说，锁定线程的arena并从那里分配内存。

Malloc算法⌗

简而言之，malloc是这样工作的：

• 如果在tcache中有一个合适的（精确匹配的）块，它将被返回给调用者。不会试图使用一个更大尺寸的bin中的可用chunk。

• 如果请求足够大，mmap()会被用来直接向操作系统请求内存。注意mmap的阈值是动态的，除非被M_MMAP_THRESHOLD覆盖（见mallopt()文档），而且一次可以有多少个这样的映射可能是有限制的。

• 如果合适的fastbin中有一个块，就使用它。如果有额外的chunks，也要预先填入tcache。

• 如果合适的smallbin中有一个块，就使用它，可能也会在这里预填充tcache。

• 如果请求是"large"的，花点时间把fastbins中的所有chunk移到unsorted bin中，一边移一边聚合它们。

• 开始从unsorted bin列表中取出块，并将它们移到small或large bin中，边移边聚合（注意，这是代码中唯一将块放入small或large bin的地方）。如果看到一个大小合适的chunk，就使用这个chunk。

• 如果请求是"large”，就搜索相应的large bin，以及连续的更大的bin，直到找到足够大的chunk。

• 如果我们在fastbins中仍有chunk（这可能发生在"small"请求中），合并那些chunks并重复前两个步骤。

• 分离"top” chunk的一部分，可能事先扩大"top”。

对于过度对齐的malloc，如valloc、pvalloc或memalign，一个过大的chunk被定位（使用上面的malloc算法）并分成两个或更多的块，这样的方式使得大部分的chunk被适当地对齐（并返回给调用者），而这部分前后的多余部分被返回到unsorted列表中，以便以后重新使用。

Free算法⌗

注意，一般来说，“free（释放）“内存实际上并没有把它还给操作系统供其他应用程序使用。free()调用将一块内存标记为可以被应用程序重新使用，但从操作系统的角度来看，该内存仍然属于该应用程序。然而，如果堆中的top chunk——与未映射的内存相邻的部分变得足够大，其中一些内存可能会被取消映射并返回到操作系统中。

简而言之，free的工作原理是这样的：

• 如果tcache中还有空间，就把这块内存存放在那里并返回。

• 如果这块内存足够小，就把它放到适当的fastbin中。

• 如果该块之前是被mmap分配的，就调用munmap。

• 看这个chunk是否与另一个空闲的空闲的chunk相邻，如果是的话，就进行聚合。

• 将该chunk放在unsorted列表中，除非它现在是"top” chunk。

• 如果这个chunk足够大，聚合所有的fastbins，看top chunk是否足够大，以便把一些内存还给系统。注意，出于性能的考虑，这一步可能会被推迟到malloc或其他调用中发生。

Realloc算法⌗

请注意，对NULL的重新分配和对零大小的重新分配是分开处理的，并按照相关规范进行。

简而言之，realloc的工作原理是这样的：

对于mmap分配的chunks：

通过单独的mmap调用分配的内存（即大块内存），用mremap()来重新分配（如果有的话），这可能会导致新的内存与旧的内存在不同的地址，取决于内核的做法。

如果系统不支持munmap()，并且新的内存尺寸小于旧的尺寸，那么什么都不会发生，旧的地址会被返回，否则会发生一次malloc-copy-free。

对于arena chunks：

• 如果分配的尺寸被减少到"值得"拆分的程度，那么这个chunk会被分成两个chunks。前半部分（旧地址）被返回，后半部分作为空闲chunk归还到arena。稍微减少尺寸被视为"相同大小”（注：不会拆分chunk）。

• 如果分配的尺寸增长，则检查下一个（相邻）chunk。如果它是空闲的，或者是 “顶部 “块（代表堆的可扩展部分），并且足够大，那么该chunk和当前chunk合并，产生一个足够大的chunk，可以被分割（如上问所述）。在这种情况下，旧的指针被返回。

• 如果分配的尺寸增长，且没有办法使用现有的或后续的chunk，那么就会使用一次malloc-copy-free序列。

交换arenas⌗

一个线程所依附的arena通常被看作是一个不变量，在进程的生命周期内不会发生变化。这种不变性虽然对解释一般的概念有用，但并不是真的。在以下几种情况下会改变arena：

• 线程从依附的arena分配内存失败。

  • 假设我们尝试了聚合，搜索了空闲列表，处理了unsorted列表等等。
  • 假设我们试图扩展堆，但sbrk失败，或者创建新的内存映射失败。

• 如果之前使用的是带有mmap堆的非主arena，那么线程将通过arena_get_retry切换到带有基于sbrk堆的主arena。或者如果之前使用的是主arena，则切换到非主arena（从空闲列表获取或创建新的arena）。作为一种优化，如果进程是单线程的我们就不会像上面这样做。如果在这里失败了，就返回ENOMEM（这里假定如果sbrk不起作用，并且我们尝试了mmap来扩展主arena，非主arena也不会起作用）。

请注意，在低内存条件下，一个线程可能会在不同的arena之间频繁切换，从基于sbrk的主arena切换到基于mmap的非主arena，都是为了找到一个有足够空间的堆来满足分配内存。

平台相关的阈值和常量⌗

总结⌗

分配内存涉及到的系统调用：

• sbrk()
• mmap()
• munmap()
• mremap()

参考⌗

• malloc源码：https://code.woboq.org/userspace/glibc/malloc/malloc.c.html

• 知乎专栏：https://zhuanlan.zhihu.com/p/163401620

• 知乎专栏：https://zhuanlan.zhihu.com/p/449427297