Post

mimalloc

Posted Updated
By SimonCho 19 min read

mimalloc的学习

Intro

mimalloc, 19年微软开源的一个malloc内存分配库，代码量不大，目前看起来比较适合学习

有一篇比较完善的paper, Mimalloc: Free List Sharding in Action, 目前看man page也比较完善。

0 关于malloc和为什么

操作系统虽然提供了mmap和brk之类的系统调用来做内存的申请，但是一般这些都不会被直接使用在代码中，而是通过malloc这样的库函数来申请内存。

malloc帮你隐藏了系统层面的细节，然后还有两个比较恶心的点,

  1. brk()和mmap()的最小分配空间取决于操作系统的内存页大小

  2. 频繁的系统调用的开销比较大。

然后对于他们的空间分配

  1. 对于 brk()，它改变的是进程的数据段大小，数据段的大小必须是内存页大小的整数倍。因此，brk()的最小分配空间是一个内存页。在许多现代操作系统上，内存页大小通常是4KB。

  2. 对于mmap()，它创建的是内存映射，内存映射的大小也必须是内存页大小的整数倍。因此，mmap()的最小分配空间也是一个内存页。同样，内存页大小通常是4KB。

如果一直这样用的话内存碎片会很大，所以malloc会有一些策略来解决这个问题。

常见的内存分配器有 glibc 中的 ptmalloc、Google 的 tcmalloc、Facebook 的 jemalloc，微软的mimalloc。 ptmalloc的源码可以下载到。

1 内存分配器的几个概念

1.1 分配区arena

在 ptmalloc 中，使用分配区 arena 管理从操作系统中批量申请来的内存。

之所以要有多个分配区，原因是多线程在操作一个分配区的时候需要加锁。在线程比较多的时候，在锁上浪费的开销会比较多。为了降低锁开销，ptmalloc 支持多个分配区。这样在单个分配区上锁的竞争开销就会小很多。

像ptmalloc的实现中，有一个主分配区，内部有mutex，用链表链接其余的分配区

每个 arena 可以有多个 heap。heap 是 arena 中的一部分，它是真正用于存储 chunk 的地方。

1.2 内存chunk(块)

在每个 arena 中，最基本的内存分配的单位是 malloc_chunk，我们简称 chunk。它包含 header 和 body 两部分。

1
2
3
4
5
6
7
8
9
10
11
12

// file:malloc/malloc.c
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;
};

每次malloc，调用会分给我们一个大小合适的 chunk 出来，把 body 部分的 user data 的地址返回给我们。 chunk里的size看起来会比实际的userdata的size大一点点

1
2
3
4

+----------------+----------------------------------+
| Mgmt Info      | User Data                        |
| (chunk header) | (the memory space for the user)  |
+----------------+----------------------------------+

如果我们在开发中调用 free 释放内存的话，其对应的 chunk 对象其实并不会归还给内核。而是由 glibc 又组织管理了起来。其 body 部分的 fd、bk 字段分别是指向上一个和下一个空闲的 chunk（ chunk 在使用的时候是没有这两个字段的，这块内存在不同场景下的用途不同）

1.3 空闲内存链表bins

glibc 会将相似大小的空闲内存块 chunk 都串起来。这样等下次用户再来分配的时候，先找到链表，然后就可以从链表中取下一个元素快速分配。这样的一个链表被称为一个 bin。

ptmalloc 中根据管理的内存块的大小，总共有 fastbins、smallbins、largebins 和 unsortedbins 四类。

这四类 bins 分别定义在 struct malloc_state 的不同成员里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

//file:malloc/malloc.c
// SIZE_SZ是指针打大小
#define MAX_FAST_SIZE     (80 * SIZE_SZ / 4)
#define NBINS             128

struct malloc_state {

 /* Fastbins */
 mfastbinptr      fastbins[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 */
 // smallbins、largebins 和 unsortedbins 都使用的是这个数组。
 mchunkptr        bins[NBINS * 2];

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

fastbins 是用来管理尺寸最小空闲内存块的链表。其管理的内存块的最大大小是MAX_FAST_SIZE。

bins 是用来管理空闲内存块的主要链表数组。其链表总数为 2 * NBINS 个，NBINS 的大小是 128，所以这里总共有 256 个空闲链表。smallbins、largebins 和 unsortedbins 都使用的是这个数组。

另外top 成员是用来保存着特殊的 top chunk。当所有的空闲链表中都申请不到合适的大小的时候，会来这里申请。

1.3.1 fastbins

fastbins 是用来管理尺寸最小空闲内存块的链表(尺寸最小的元素的链表)。其管理的内存块的最大大小是MAX_FAST_SIZE。

它存在的原因是，用户的应用程序中绝大多数的内存分配是小内存，这组 bin 是用于提高小内存的分配效率的

fastbin 中有多个链表，每个 bin 链表管理的都是固定大小的 chunk 内存块。在 64 位系统下，每个链表管理的 chunk 元素大小分别是 32 字节、48 字节、……、128 字节 等不同的大小。

glibc 中提供了 fastbin_index 函数可以快速地根据要申请的内存大小找到 fastbins 下对应的数组下标。

1
2
3

//file:malloc/malloc.c
#define fastbin_index(sz) \
  ((((unsigned int)(sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)

例如要申请的内存块大小是 32 字节，fastbin_index(32) 计算后可知应该到下标位 0 的空闲内存链表里去找。再比如要申请的内存块大小是 64 字节，fastbin_index(64) 计算后得知数组下标为 2。

1.3.2 smallbins

smallbins 是在 malloc_state 下的 bins 成员中管理的。smallbins 数组总共有 64 个链表指针，是由 NSMALLBINS 来定义的。

1

#define NSMALLBINS         64

和 fastbin 一样，同一个 small bin 中的 chunk 具有相同的大小。small bin 在 64 位系统上，两个相邻的 small bin 中的 chunk 大小相差 16 字节(MALLOC_ALIGNMENT 是 2 个 SIZE_SZ，一个 SIZE_SZ 大小是 8)。

1
2
3

//file:malloc/malloc.c
#define MALLOC_ALIGNMENT       (2 * SIZE_SZ)
#define SMALLBIN_WIDTH    MALLOC_ALIGNMENT

管理的 chunk 大小范围定义在 in_smallbin_range 中能看到。只要小于 MIN_LARGE_SIZE 的都属于 small bin 的管理范围。

1
2
3

#define MIN_LARGE_SIZE    (NSMALLBINS * SMALLBIN_WIDTH)
#define in_smallbin_range(sz)  \
  ((unsigned long)(sz) < (unsigned long)MIN_LARGE_SIZE)

通过上面的源码可以看出 MIN_LARGE_SIZE 的大小等于 64 * 16 = 1024。所以 small bin 管理的内存块大小是从 32 字节、48 字节、……、1008 字节。（在 glibc 64位系统中没有管理 16 字节的空闲内存，是 32 字节起的）

另外 glibc 也提供了根据申请的字节大小快速算出其在 small bin 中的下标的函数 smallbin_index。

1
2
3

//file:malloc/malloc.c
#define smallbin_index(sz) \
  (SMALLBIN_WIDTH == 16 ? (((unsigned)(sz)) >> 4) : (((unsigned)(sz)) >> 3))

例如要申请的内存块大小是 32 smallbin_index(32) 计算后可知应该到下标位 2 的空闲内存链表里去找。再比如要申请的内存块大小是 64 smallbin_index(64) 计算后得知数组下标为 3。

看起来smallbins的大小和fastbins的区别不是很大，怀疑在fastbins里放的内存不用考虑合并之类的，可能超过阈值才考虑，smallbins里的可能要考虑合并和分割之类的

1.3.3 largebins

largebins 和 smallbins 的区别是它管理的内存块比较大。其管理的内存是 1024 起的。

而且每两个相邻的 largebin 之间管理的内存块大小不再是固定的等差数列。这是为了用较少的链表数来更大块空闲内存的管理。

largebin_index_64 函数用来根据要申请的内存大小计算出其在 large bins 中的下标。

1
2
3
4
5
6
7
8

//file:malloc/malloc.c
#define largebin_index_64(sz)                                                \
(((((unsigned long)(sz)) >>  6) <= 48)?  48 + (((unsigned long)(sz)) >>  6): \
 ((((unsigned long)(sz)) >>  9) <= 20)?  91 + (((unsigned long)(sz)) >>  9): \
 ((((unsigned long)(sz)) >> 12) <= 10)? 110 + (((unsigned long)(sz)) >> 12): \
 ((((unsigned long)(sz)) >> 15) <=  4)? 119 + (((unsigned long)(sz)) >> 15): \
 ((((unsigned long)(sz)) >> 18) <=  2)? 124 + (((unsigned long)(sz)) >> 18): \
     126)

1.3.4 unsortedbins

unsortedbins 比较特殊，它管理的内存块不再是和 smallbins 或 largebins 中那样是相同或者相近大小的。而是不固定，是被当做缓存区来用的。

当用户释放一个堆块之后，会先进入 unsortedbin。再次分配堆块时，ptmalloc 会优先检查这个链表中是否存在合适的堆块，如果找到了，就直接返回给用户(这个过程可能会对 unsortedbin 中的堆块进行切割)。若没有找到合适的，系统也会顺带清空这个链表上的元素，把它放到合适的 smallbin 或者 large bin 中。

1.3.5 top chunk

另外还有有个独立于 fastbins、smallbins、largebins 和 unsortedbins 之外的一个特殊的 chunk 叫 top chunk。

如果没有空闲的 chunk 可用的时候，或者需要分配的 chunk 足够大，当各种 bins 都不满足需求，会从top chunk 中尝试分配。

2 malloc的工作原理

glibc 在分配区 arena 中分别用 fastbins、bins（保存着 smallbins、largebins 和 unsortedbins）以及 top chunk 来管理着当前已经申请到的所有空闲内存块。

有了这些组织手段后，当用户要分配内存的时候，malloc 函数就可以根据其大小，从合适的 bins 中查找合适的 chunk。

当用户用完需要释放的时候，glibc 再根据其内存块大小，放到合适的 bin 下管理起来。下次再给用户申请时备用。

另外还有就是为 ptmalloc 管理的 chunk 可能会发生拆分或者合并。

当需要申请小内存块，但是没有大小合适的时候，会将大的 chunk 拆成多个小 chunk。如果申请大内存块的时候，而系统中又存在大量的小 chunk 的时候，又会发生合并，以降低碎片率。

2.1 代码实现

malloc 在 glibc 中的实现函数名是 public_mALLOc。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

//file:malloc/malloc.c
Void_t*
public_mALLOc(size_t bytes)
{
 // 选一个分配区 arena 出来，并为其加锁
 arena_lookup(ar_ptr);
 arena_lock(ar_ptr, bytes);

 // 从分配区申请内存
 victim = _int_malloc(ar_ptr, bytes);

 // 如果选中的分配区没有申请成功，则换一个分配区申请
 ......

 // 释放锁并返回
 mutex_unlock(&ar_ptr->mutex);
 return victim;
}

在 public_mALLOc 中主要的逻辑就是选择分配区和锁操作，这是为了避免多线程冲突。真正的内存申请核心逻辑都在 _int_malloc 函数中

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

//file:malloc/malloc.c
static Void_t*
_int_malloc(mstate av, size_t bytes)
{
 // 对用户请求的字节数进行规范化
 INTERNAL_SIZE_T nb; /* normalized request size */
 checked_request2size(bytes, nb);

 // 1.从 fastbins 中申请内存
 if ((unsigned long)(nb) <= (unsigned long)(get_max_fast ())) {
  ...
 }

 // 2.从 smallbins 中申请内存
 if (in_smallbin_range(nb)) {
  ...
 }

 for(;;) {
  // 3.遍历搜索 unsorted bins
  while ( (victim = unsorted_chunks(av)->bk) != unsorted_chunks(av)) {
   // 判断是否对 chunk 进行切割
   ...

   // 判断是否精准匹配，若匹配可以直接返回
   ...

   // 若不精准匹配，则将 chunk 放到对应的 bins 中
   // 如果属于 smallbins，则插入到 smallbins 中
   // 如果属于 largebins，则插入到 largebins 中
   ...

   // 避免遍历 unsorted bin 占用过多时间
   if (++iters >= MAX_ITERS)
    break;
  }

  // 4.如果属于 large 范围或者之前的 fastbins/smallbins/unsorted bins 请求都失败
  //   则从 large bin 中寻找 chunk，可能会涉及到切割
  ...


  // 5.尝试从 top chunk 中申请
  //   可能会涉及对 fastbins 中 chunk 的合并
 use_top:
  victim = av->top;
     size = chunksize(victim);
  ...

  // 最后，分配区中没申请到，则向操作系统申请
  void *p = sYSMALLOc(nb, av);
 }
}

在一进入函数的时候，首先是调用 checked_request2size 对用户请求的字节数进行规范化。因为分配区中管理的都是 32、64 等对齐的字节数的内存。如果用户请求 30 字节，那么 ptmalloc 会对齐一下，然后按 32 字节为其申请。

接着是从分配区的各种 bins 中尝试为用户分配内存。总共包括以下几次的尝试。

  1. 如果申请字节数小于 fast bins 管理的内存块最大字节数，则尝试从 fastbins 中申请内存，申请成功就返回
  2. 如果申请字节数小于 small bins 管理的内存，则尝试从 smallbins 中申请内存，申请成功就返回
  3. 尝试从 unsorted bins 中申请内存，申请成功就返回
  4. 尝试从 large bins 中申请内存，申请成功就返回
  5. 如果前面的步骤申请都没成功，尝试从 top chunk 中申请内存并返回
  6. 从操作系统中使用 mmap 等系统调用申请内存

最后在 top chunk 中也没有足够的内存的时候，就会调用 sYSMALLOc 来向操作系统发起内存申请。

1
2
3
4
5
6
7

//file:malloc/malloc.c
static Void_t* sYSMALLOc(INTERNAL_SIZE_T nb, mstate av)
{
 ...
 mm = (char*)(MMAP(0, size, PROT_READ|PROT_WRITE, MAP_PRIVATE));
 ...
}

有个介绍这些的文章

Ref

  1. ptmalloc、tcmalloc与jemalloc对比分析,

  2. 如何评价 mimalloc？

  3. 解析Jemalloc的关键数据结构

  4. Jemalloc中的Radix Tree

  5. 聊聊ptmalloc

  6. 内存管理专栏

  7. ptmalloc

  8. heap mem

  9. glibc malloc 原理简析

  10. 浅谈mmap映射

  11. 术道经纬目录

  12. 内存池实现介绍

  13. 源码分析：malloc如何直接向操作系统申请内存

Blogging, memory
writing
This post is licensed under CC BY 4.0 by the author.

Trending Tags

writing