
malloc 内部如何工作?一文解析其内存分配机制
来源标题:What is malloc doing, anyway?
malloc 并不每次分配都向内核请求内存:连续调用 1000 次 malloc(16) 只触发两次 brk 系统调用。第一次查询堆结束地址,第二次一次性扩展堆 132 KiB,其余 999 次分配都直接从这块已申请的内存中取用,因为系统调用开销高昂(空调用约 575 纳秒)。
以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
malloc 的接口非常简单优雅:你请求一定量的内存,就会得到一个 void 指针,指向一块凭空出现的连续字节。用完之后,把同一个指针传给 free,这块内存就凭空消失了。
但背后到底发生了什么?显然,由于我们是用户态程序,malloc 必然要通过系统调用向内核申请内存。不过,我们可能会分配很多小块内存,而系统调用开销很高(一次空系统调用实测为 575 ns,见下文),所以后台会做一些簿记工作。下面我们用 GNU libc(glibc)和一段调用 malloc(16) 一千次的程序来演示。
static void *ptrs[1000];
int main(void) {
for (int i = 0; i < 1000; i++)
ptrs[i] = malloc(16);
用 strace 可以看到,整个循环只发起了两次 brk 系统调用:第一次询问程序断点在哪里(即进程堆的结束地址),第二次把堆扩大 132 KiB。这两次都发生在第一次 malloc 调用中——其余 999 次只是从已经分配好的内存里取用。
$ strace -e trace=brk,mmap,munmap,write
./malloc1000 > /dev/null
...
brk(NULL) = 0x59faca231000
brk(0x59faca252000) = 0x59faca252000
+++ exited with 0 +++
你可能会在讨论中看到 brk 和 sbrk 同时出现。brk 是一个系统调用,把程序断点设置为传入的地址;sbrk 则是 libc 提供的便利封装,接受一个增量,把程序断点增加该数值。
运行中的进程拥有自己的地址空间,划分为若干区域,包括存放可执行代码的 text、存放已初始化全局变量的 data、存放未初始化全局变量的 bss 等等。下面的程序打印进程各区域中的一个地址。
#define SHOW(label, p)
printf("%-22s %p\n", label, (void *)(p))
SHOW("main (text)", main);
SHOW("initialised (data)", &initialised);
SHOW("uninitialised (bss)", &uninitialised);
SHOW("malloc(16) (heap)", malloc(16));
SHOW("program break", sbrk(0));
SHOW("printf (libc)", printf);
SHOW("local (stack)", &local);
地址从二进制文件的代码段一路上升到栈。
$ ./layout
main (text) 0x59c0791d7149
initialised (data) 0x59c0791da020
uninitialised (bss) 0x59c0791da028
malloc(16) (heap) 0x59c0903182b0
program break 0x59c090338000
printf (libc) 0x711dcf7c15b0
local (stack) 0x7ffff86c45ec
其中一些区域会随程序运行而变化。例如 malloc(16) 会扩大堆并把断点上移。注意在这次运行中,断点和 libc 中的 printf 相距 23.4 TiB,约为机器 15.6 GiB 内存的 1,530 倍。这段范围几乎全部未映射,因此不占用物理内存。
lowhighat starttextdataBSSgapbreak23 TiBunmappedlibcstackmalloc(16)textdataBSSgapheapbreak23 TiBunmappedlibcstack
用 sbrk 实现一个玩具分配器 #
既然可以直接移动程序断点,我们就可以自己写一个小分配器。这叫做 bump allocator(碰撞分配器),因为每次调用只是把我们允许使用的内存量往上推。
void *my_malloc(size_t size) {
void *p = sbrk(align_up(size));
return p == (void *)-1 ? NULL : p;
void my_free(void *ptr) {
(void)ptr;
这个分配器不太好!它在每一次请求时都移动断点,而每次移动都是一次系统调用。我们可以对比系统调用和 malloc 的耗时,看看为什么 malloc 要向内核申请大块内存再自己切分。下面三个函数各计时一百万次调用。
static void *volatile sink;
static void call_getppid(void) {
syscall(SYS_getppid);
static void call_sbrk(void) {
sink = sbrk(16);
static void call_malloc(void) {
sink = malloc(16);
sbrk(16) 只比空系统调用多花 35 ns,而 malloc(16) 比 sbrk(16) 快 22.7 倍。
$ ./syscall-cost
syscall(SYS_getppid) 575.2 ns per call
sbrk(16) 610.1 ns per call
malloc(16) 26.9 ns per call
sbrk(16) / malloc(16) 22.7x
这个碰撞分配器也无法复用已释放的内存。每次请求都紧接在前一次之后,所以在下面的例子中,尽管 b 已被释放,d 仍然落在 c 之后。
$ ./my-bump-1
a = my_malloc(16) start+0
b = my_malloc(1) start+16
c = my_malloc(100) start+32
my_free(b)
d = my_malloc(1) start+144
break start+160
本文接下来会一步步改进这个分配器。
malloc 实际分配的内存比你请求的更多。这是因为每次分配(或称一个 chunk)在返回指针之前都有一个大小头部;这正是 free 无需显式传入大小也能工作的原因。chunk 大小总是 16 的倍数,所以大小的低位总是零,glibc 就在这些位里存放三个标志。
header24 bytes for the callerheaderp = malloc(24)next chunkchunk:32 bytessize=320A0M1Pone 8-byte wordA:another arenaM:own mappingP:chunk before in use
size_t requests[] = {1, 24, 25, 1000};
size_t count = sizeof requests / sizeof requests[0];
for (size_t i = 0; i < count; i++) {
char *p = malloc(requests[i]);
size_t chunk = ((size_t *)p)[-1] & ~(size_t)7;
printf("%8zu %8zu\n", requests[i], chunk);
每个 chunk 等于请求大小加上 8 字节头部,向上取整到 16 的倍数,最小为 32。这种取整保证了 malloc 返回的每个指针都是 16 字节对齐的,也就是 x86-64 上 max_align_t 的对齐要求,因此这块内存适用于任何 C 类型。32 字节的最小值则为 chunk 释放后存储链表指针留出了空间。
$ ./chunk-header
request chunk
1 32
24 32
25 48
1000 1008
(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。