Computer System

malloc

本文主要分为两部分：探究malloc执行背后涉及的系统调用，以及分配大内存和小内存的执行差别。在此之前先说明一些关于malloc的“传闻”：通过brk系统调用控制heap的增长，自身负责管理一些内存块，对于可以满足的分配需求，可以在用户态下直接分配已有的空闲内存块完成；对于大内存需求，调用mmap系统调用；第二部分是关于现在使用的较多的malloc库的设计和实现思想，包括ptmalloc和tcmalloc。

malloc

我们通过观察一个例子中malloc的行为，探究malloc的行为。

a simple example

使用一个简单的示例程序，程序分别调用malloc分配小块内存(1KB)和大块内存(1GB)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define MEM_SIZE (1<<10)

int main(int argc, char **argv)
{
    printf("I am %d\n", getpid());
    getchar();
    char *big = malloc(MEM_SIZE);
    char *small = malloc(1<<10);
    printf("address: %p %p\n", big, small);
    getchar();
    free(big);
    free(small);
    getchar();

    return 0;
}

同时，我们通过查看进程的内存映射情况，确定heap的范围，以及小内存和大内存分别处于哪块内存区域。在程序中插入了getchar()，方便在分配内存前、分配内存后、释放内存后分别查看内存映射的情况。我们将三个阶段的映射数据分别保存在before、alloc和free的文件中，并通过对比三个文件的差异，可得知malloc和free对内存映射的影响。
第一步，设置MEM_SIZE为1<<10，与小内存大小相同，即均为1KB时，编译并运行main，由于getchar()的存在，程序会有一些停顿（以下程序的输出做了些许调整，与正常输出不同）

1
2
3
4
> gcc main.c -g -o main
> ./main
I am 153825
address: 0x555555559ac0 0x555555559ed0

在程序停顿时，另开一窗口，每次停顿后分别执行

1
2
3
> cat /proc/153825/maps > Templates/before 
> cat /proc/153825/maps > Templates/alloc 
> cat /proc/153825/maps > Templates/free

使用diff命令检查三个文件的不同

1
2
> diff before alloc 
> diff alloc free

使用strace跟踪mmap的调用情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7ffff7fbb000
mmap(NULL, 71183, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7ffff7fa9000
mmap(NULL, 2260560, PROT_READ, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x7ffff7d81000
mmap(0x7ffff7da9000, 1658880, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x28000) = 0x7ffff7da9000
mmap(0x7ffff7f3e000, 360448, PROT_READ, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x1bd000) = 0x7ffff7f3e000
mmap(0x7ffff7f96000, 24576, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x214000) = 0x7ffff7f96000
mmap(0x7ffff7f9c000, 52816, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x7ffff7f9c000
mmap(NULL, 12288, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7ffff7d7e000
I am 154037

address: 0x555555559ac0 0x555555559ed0


+++ exited with 0 +++

在输出”I am …”信息后，并未调用mmap系统调用。
三个文件内容相同，且未调用mmap。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
> cat before 
555555554000-555555555000 r--p 00000000 08:03 271805                     /home/rda/Templates/main
555555555000-555555556000 r-xp 00001000 08:03 271805                     /home/rda/Templates/main
555555556000-555555557000 r--p 00002000 08:03 271805                     /home/rda/Templates/main
555555557000-555555558000 r--p 00002000 08:03 271805                     /home/rda/Templates/main
555555558000-555555559000 rw-p 00003000 08:03 271805                     /home/rda/Templates/main
555555559000-55555557a000 rw-p 00000000 00:00 0                          [heap]
7ffff7d7e000-7ffff7d81000 rw-p 00000000 00:00 0 
7ffff7d81000-7ffff7da9000 r--p 00000000 08:03 526570                     /usr/lib/x86_64-linux-gnu/libc.so.6
7ffff7da9000-7ffff7f3e000 r-xp 00028000 08:03 526570                     /usr/lib/x86_64-linux-gnu/libc.so.6
7ffff7f3e000-7ffff7f96000 r--p 001bd000 08:03 526570                     /usr/lib/x86_64-linux-gnu/libc.so.6
7ffff7f96000-7ffff7f9a000 r--p 00214000 08:03 526570                     /usr/lib/x86_64-linux-gnu/libc.so.6
7ffff7f9a000-7ffff7f9c000 rw-p 00218000 08:03 526570                     /usr/lib/x86_64-linux-gnu/libc.so.6
7ffff7f9c000-7ffff7fa9000 rw-p 00000000 00:00 0 
7ffff7fbb000-7ffff7fbd000 rw-p 00000000 00:00 0 
7ffff7fbd000-7ffff7fc1000 r--p 00000000 00:00 0                          [vvar]
7ffff7fc1000-7ffff7fc3000 r-xp 00000000 00:00 0                          [vdso]
7ffff7fc3000-7ffff7fc5000 r--p 00000000 08:03 526564                     /usr/lib/x86_64-linux-gnu/ld-linux-x86-64.so.2
7ffff7fc5000-7ffff7fef000 r-xp 00002000 08:03 526564                     /usr/lib/x86_64-linux-gnu/ld-linux-x86-64.so.2
7ffff7fef000-7ffff7ffa000 r--p 0002c000 08:03 526564                     /usr/lib/x86_64-linux-gnu/ld-linux-x86-64.so.2
7ffff7ffb000-7ffff7ffd000 r--p 00037000 08:03 526564                     /usr/lib/x86_64-linux-gnu/ld-linux-x86-64.so.2
7ffff7ffd000-7ffff7fff000 rw-p 00039000 08:03 526564                     /usr/lib/x86_64-linux-gnu/ld-linux-x86-64.so.2
7ffffffde000-7ffffffff000 rw-p 00000000 00:00 0                          [stack]
ffffffffff600000-ffffffffff601000 --xp 00000000 00:00 0                  [vsyscall]

heap的范围为555555559000-55555557a000，而p和q的地址分别为0x555555559ac0和0x555555559ed0，均位于其中。因此，malloc会管理一个预先分配好的heap，如果请求分配的内存可以满足，则直接分配即可。
设置MEM_SIZE为1<<30，即1GB，显然，上述heap的大小为0x7a000 - 0x59000 = 0x21000，远小于MEM_SIZE。
重新编译并执行

1
2
3
4
> gcc main.c -g -o main
rda@pa ~/Templates> ./main
I am 154154
address: 0x7fffb7d7d010 0x555555559ac0

使用diff查看三个文件的差异

1
2
3
4
5
6
7
8
9
10
11
> diff before alloc
7c7
< 7ffff7d7e000-7ffff7d81000 rw-p 00000000 00:00 0 
---
> 7fffb7d7d000-7ffff7d81000 rw-p 00000000 00:00 0 
> diff alloc free
7c7
< 7fffb7d7d000-7ffff7d81000 rw-p 00000000 00:00 0 
---
> 7ffff7d7e000-7ffff7d81000 rw-p 00000000 00:00 0 
> diff before free

可见，在执行malloc之前和执行free后的文件内容是相同的。而执行malloc后，内存空间的差异仅有一处：有一块内存区域的从7ffff7d7e000-7ffff7d81000变为了7fffb7d7d000-7ffff7d81000。即起始处从0x7ffff7d7e000变味了0x7fffb7d7d000，p（大内存）的地址为0x7fffb7d7d010，恰好在该内存区域的起始处偏移0x10的位置，而q（小内存）的地址为0x555555559ac0，仍位于heap中。
执行strace跟踪mmap和munmap的调用情况

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
> strace -e mmap ./main
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7ffff7fbb000
mmap(NULL, 71183, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7ffff7fa9000
mmap(NULL, 2260560, PROT_READ, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x7ffff7d81000
mmap(0x7ffff7da9000, 1658880, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x28000) = 0x7ffff7da9000
mmap(0x7ffff7f3e000, 360448, PROT_READ, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x1bd000) = 0x7ffff7f3e000
mmap(0x7ffff7f96000, 24576, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x214000) = 0x7ffff7f96000
mmap(0x7ffff7f9c000, 52816, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x7ffff7f9c000
mmap(NULL, 12288, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7ffff7d7e000
I am 154333

mmap(NULL, 1073745920, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fffb7d7d000
address: 0x7fffb7d7d010 0x555555559ac0


+++ exited with 0 +++
> strace -e munmap ./main
munmap(0x7ffff7fa9000, 71183)           = 0
I am 154371

address: 0x7fffb7d7d010 0x555555559ac0

munmap(0x7fffb7d7d000, 1073745920)      = 0

+++ exited with 0 +++

可见，在malloc申请大内存后执行了mmap，返回的地址为 0x7fffb7d7d000，而free后，调用了munmap(0x7fffb7d7d000, 1073745920)

summary

malloc自身维护了一块地址较低的内存，对于小块的内存请求，malloc从自身管理的空闲内存块中分配；对于大块内存，通过调用mmap和munmap分配和释放。

malloc实例

总结几个常用的malloc库的实现思想和机制：

  • glibc中的ptmalloc
  • Google的tcmalloc
  • Facebook的jemalloc

ptmalloc

tcmalloc