dlmalloc 内存分配器

发表于 分类于 阅读次数： 本文字数： 2.7k 阅读时长 ≈ 10 分钟

dlmalloc 是一个 C 语言实现的流行的内存分配器实现，由纽约州立大学 Oswego 分校计算机系教授 Doug Lea 在 1980 年代编写，许多人称之为 Doug Lea 的 malloc，或者简称 dlmalloc。

关于 Doug Lea

Doug Lea 是计算机科学领域的知名学者，尤其在内存管理和并发编程方面有着深厚的造诣。他的研究工作对操作系统、编程语言和计算机体系结构等领域产生了深远的影响。

Doug Lea 曾经是 JCP（Java Community Process）委员会委员，参与了 JSR 166（Java Concurrency Utilities）的设计和实现。他的工作为 Java 的并发编程模型奠定了基础。

由于具备高效且占用空间较小等特点，dlmalloc 被广泛使用，用 Doug Lea 自己的话说，就是“它在一些 linux 版本里面作为默认的 malloc 被使用，被编译到一些公共的软件包里，并且已经被用于各种 PC 环境及嵌入式系统，以及许多甚至我也不知道的地方”。

#dlmalloc 的历史

1987 年，Doug Lea 在编写了一些几乎完全依赖于分配动态内存的 C++ 程序之后，发现它们的运行速度比我预期的要慢得多，并且/或者总内存消耗比预期的要多得多。这是由于所运行的系统（主要是当时的 SunOS 和 BSD 版本）上的内存分配器的特性所致。为了解决这个问题，起初 Doug Lea 用 C++ 编写了一些专用分配器，通过为各种类重载 operator new 来实现的。

然而，随着时间的推移，他意识到为每个类编写一个分配器并不是一个好的解决方案，因为这会导致代码的重复和维护的复杂性。需要一个更通用的内存分配器 —— 编写一个在正常 C++ 和 C 负载下足够好的分配器，这样程序员就不会被诱惑去编写专用的分配器，除非在非常特殊的情况下。于是 Doug Lea 编写了 dlmalloc，并一直在维护和改进它（在许多志愿者贡献者的帮助下）。

该分配器的代码已被放置在公共领域（可从 ftp://g.oswego.edu/pub/misc/malloc.c 获得），并且已经被广泛使用：

  • 它在某些版本的 Linux 中用作 malloc 的默认本机版本；它被编译成几个常用的软件包（覆盖本机 malloc）
  • 在各种 PC 环境以及嵌入式系统中使用
  • Android 的 Dalvik 虚拟机使用了 dlmalloc 作为其内存分配器

#dlmalloc 的设计

一个好的 malloc 库需要平衡这些目标：

  • 最大化兼容性：满足 POSIX 标准
  • 最大化便携性
  • 最小化空间
  • 最小化时间
  • 最大化可定制性：允许用户微调参数
  • 最大化局部性
  • 最大化错误检测
  • 最小化异常

1995 年的一篇综述论文中讨论了这些目标的权衡，认为最大限度地减少浪费（通常是由碎片引起的）必须是任何分配器的主要目标。一个极端的例子是按顺序分配下一块可用内存，不进行 free 的 malloc，它具有最快的性能，但是会导致巨大的内存浪费。内存浪费最终等价于对金钱的浪费。

虽然时间和空间问题占据主导地位，但是权衡和妥协几乎无穷无尽。例如：

  • 为了满足对齐要求，可能会导致浪费一些内存
  • 为了满足可定制性要求（例如 debug 模式），会导致性能下降
  • 为了满足兼容性要求，可能会限制功能的灵活性：例如 POSIX 标准要求 malloc 负数内存应该返回 NULL
  • 为了满足兼容性要求，导致性能下降：例如 dlmalloc 为了兼容一个早期错误的 malloc 实现，允许 realloc 一块 free 过的内存
  • 一些启发式方法，可以改善小程序的性能，但会导致大程序的性能下降

任何一套沿着这些思路的妥协都不可能完美。然而，多年来，分配器已经发展到能够做出大多数用户都能接受的权衡。持续影响 dlmalloc 演进的驱动力包括：

  1. 已有的实证研究表明 dlmalloc 的性能已经跻身于最好的分配器之列
  2. 目标工作负载的变化
  3. 系统和处理器的变化
  4. 来自用户和贡献者的建议、使用报告和代码。

#dlmalloc 的设计

dlmalloc 算法的两个核心元素自最早版本以来一直保持不变：

  • 边界标签
  • 分箱

#边界标签

内存块携带大小信息字段，这些字段位于块的前后。这允许实现两个重要功能：

  • 两个相邻的未使用内存块可以合并成一个更大的块。这最小化了不可用的小块的数量。
  • 所有内存块都可以从任何已知的块开始，向前或向后遍历。

alt text

dlmalloc 的原始版本正是以上图的方式实现了边界标记。较新的版本省略了程序正在使用的块上的尾部字段。这本身是一个小的权衡：当块处于活动状态时，这些字段从未被使用，因此不需要存在。消除它们可以减少开销和浪费。然而，缺少这些字段会稍微削弱错误检测能力，因为无法检查用户是否错误地覆盖了应该具有已知值的字段。

#分箱

可用块被保存在箱中，按大小分组。存在大量（128 个）固定宽度的箱，大小大约呈对数分布。小于 512 字节的块箱只包含恰好一个大小（间隔 8 字节，简化了 8 字节对齐的执行）。可用块的搜索按从小到大的顺序处理，最佳匹配方案（各种类型和近似方法）与其它如首次匹配等通用方法相比，在真实负载下往往产生最少的碎片化。正如 Wilson 等人所展示的。

alt text

直到 1995 年发布的版本，箱内的块是无序的，因此最佳匹配策略只是近似的。较新版本的软件则按大小对箱内的块进行排序，并按最早创建的规则解决冲突。（这是在发现少量时间投入是值得的，以避免观察到的不良情况后进行的。）

因此，该算法的一般分类是最佳匹配合并：释放的块与相邻块合并，并按大小顺序保存在箱中。

这种方法会导致每个数据块产生固定的账务开销。由于每个可用数据块都必须保留大小信息和桶链接，因此在 32 位指针的系统中最小可分配数据块为 16 字节，在 64 位指针的系统中最小可分配数据块为 24 字节。这些最小尺寸比大多数人希望看到的要大——例如，在分配许多小型链表节点的情况下，它们可能导致显著的浪费。然而，至少 16 字节的最低要求是任何需要 8 字节对齐且存在 malloc 账务开销的系统的一个特征。

即使这个基本算法依赖于搜索机制来找到最佳匹配，但通过使用索引技术、利用特殊情况以及精心编码，平均情况下只需要几十条指令，当然这取决于机器和分配模式。

虽然通过边界标签合并和通过桶分配最佳匹配代表了算法的主要思想，但进一步的考虑导致了一系列启发式改进。这包括局部性保持、荒野保持、内存映射和缓存。

#dlmalloc 的实现

整个 dlmalloc 的实现代码只有一个文件 malloc.c。

#Public API

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#ifndef USE_DL_PREFIX
#define dlcalloc               calloc
#define dlfree                 free
#define dlmalloc               malloc
#define dlmemalign             memalign
#define dlposix_memalign       posix_memalign
#define dlrealloc              realloc
#define dlrealloc_in_place     realloc_in_place
#define dlvalloc               valloc
#define dlpvalloc              pvalloc
#define dlmallinfo             mallinfo
#define dlmallopt              mallopt
#define dlmalloc_trim          malloc_trim
#define dlmalloc_stats         malloc_stats
#define dlmalloc_usable_size   malloc_usable_size
#define dlmalloc_footprint     malloc_footprint
#define dlmalloc_max_footprint malloc_max_footprint
#define dlmalloc_footprint_limit malloc_footprint_limit
#define dlmalloc_set_footprint_limit malloc_set_footprint_limit
#define dlmalloc_inspect_all   malloc_inspect_all
#define dlindependent_calloc   independent_calloc
#define dlindependent_comalloc independent_comalloc
#define dlbulk_free            bulk_free
#endif /* USE_DL_PREFIX */

#分配算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
void* dlmalloc(size_t bytes) {
  /*
     Basic algorithm:
     If a small request (< 256 bytes minus per-chunk overhead):
       1. If one exists, use a remainderless chunk in associated smallbin.
          (Remainderless means that there are too few excess bytes to
          represent as a chunk.)
       2. If it is big enough, use the dv chunk, which is normally the
          chunk adjacent to the one used for the most recent small request.
       3. If one exists, split the smallest available chunk in a bin,
          saving remainder in dv.
       4. If it is big enough, use the top chunk.
       5. If available, get memory from system and use it
     Otherwise, for a large request:
       6. Find the smallest available binned chunk that fits, and use it
          if it is better fitting than dv chunk, splitting if necessary.
       7. If better fitting than any binned chunk, use the dv chunk.
       8. If it is big enough, use the top chunk.
       9. If request size >= mmap threshold, try to directly mmap this chunk.
       10. If available, get memory from system and use it

     The ugly goto's here ensure that postaction occurs along all paths.
  */

#if USE_LOCKS
  ensure_initialization(); /* initialize in sys_alloc if not using locks */
#endif

  if (!PREACTION(gm)) {
    void* mem;
    size_t nb;
    if (bytes <= MAX_SMALL_REQUEST) {
      bindex_t idx;
      binmap_t smallbits;
      nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes);
      idx = small_index(nb);
      smallbits = gm->smallmap >> idx;

      if ((smallbits & 0x3U) != 0) { /* Remainderless fit to a smallbin. */
        mchunkptr b, p;
        idx += ~smallbits & 1;       /* Uses next bin if idx empty */
        b = smallbin_at(gm, idx);
        p = b->fd;
        assert(chunksize(p) == small_index2size(idx));
        unlink_first_small_chunk(gm, b, p, idx);
        set_inuse_and_pinuse(gm, p, small_index2size(idx));
        mem = chunk2mem(p);
        check_malloced_chunk(gm, mem, nb);
        goto postaction;
      }

      else if (nb > gm->dvsize) {
        if (smallbits != 0) { /* Use chunk in next nonempty smallbin */
          mchunkptr b, p, r;
          size_t rsize;
          bindex_t i;
          binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx));
          binmap_t leastbit = least_bit(leftbits);
          compute_bit2idx(leastbit, i);
          b = smallbin_at(gm, i);
          p = b->fd;
          assert(chunksize(p) == small_index2size(i));
          unlink_first_small_chunk(gm, b, p, i);
          rsize = small_index2size(i) - nb;
          /* Fit here cannot be remainderless if 4byte sizes */
          if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE)
            set_inuse_and_pinuse(gm, p, small_index2size(i));
          else {
            set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
            r = chunk_plus_offset(p, nb);
            set_size_and_pinuse_of_free_chunk(r, rsize);
            replace_dv(gm, r, rsize);
          }
          mem = chunk2mem(p);
          check_malloced_chunk(gm, mem, nb);
          goto postaction;
        }

        else if (gm->treemap != 0 && (mem = tmalloc_small(gm, nb)) != 0) {
          check_malloced_chunk(gm, mem, nb);
          goto postaction;
        }
      }
    }
    else if (bytes >= MAX_REQUEST)
      nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */
    else {
      nb = pad_request(bytes);
      if (gm->treemap != 0 && (mem = tmalloc_large(gm, nb)) != 0) {
        check_malloced_chunk(gm, mem, nb);
        goto postaction;
      }
    }

    if (nb <= gm->dvsize) {
      size_t rsize = gm->dvsize - nb;
      mchunkptr p = gm->dv;
      if (rsize >= MIN_CHUNK_SIZE) { /* split dv */
        mchunkptr r = gm->dv = chunk_plus_offset(p, nb);
        gm->dvsize = rsize;
        set_size_and_pinuse_of_free_chunk(r, rsize);
        set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
      }
      else { /* exhaust dv */
        size_t dvs = gm->dvsize;
        gm->dvsize = 0;
        gm->dv = 0;
        set_inuse_and_pinuse(gm, p, dvs);
      }
      mem = chunk2mem(p);
      check_malloced_chunk(gm, mem, nb);
      goto postaction;
    }

    else if (nb < gm->topsize) { /* Split top */
      size_t rsize = gm->topsize -= nb;
      mchunkptr p = gm->top;
      mchunkptr r = gm->top = chunk_plus_offset(p, nb);
      r->head = rsize | PINUSE_BIT;
      set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
      mem = chunk2mem(p);
      check_top_chunk(gm, gm->top);
      check_malloced_chunk(gm, mem, nb);
      goto postaction;
    }

    mem = sys_alloc(gm, nb);

  postaction:
    POSTACTION(gm);
    return mem;
  }

  return 0;
}