深入理解glibc malloc:内存分配器实现原理
Understanding glibc malloc
文章目录
前言
1. 申请堆的系统调用
2. 多线程支持
2.1. 案例代码
/* Per thread arena example. */
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <sys/types.h>
void* threadFunc(void* arg) {
printf("Before malloc in thread 1\n");
getchar();
char* addr = (char*) malloc(1000);
printf("After malloc and before free in thread 1\n");
getchar();
free(addr);
printf("After free in thread 1\n");
getchar();
}
int main() {
pthread_t t1;
void* s;
int ret;
char* addr;
printf("Welcome to per thread arena example::%d\n",getpid());
printf("Before malloc in main thread\n");
getchar();
addr = (char*) malloc(1000);
printf("After malloc and before free in main thread\n");
getchar();
free(addr);
printf("After free in main thread\n");
getchar();
ret = pthread_create(&t1, NULL, threadFunc, NULL);
if(ret)
{
printf("Thread creation error\n");
return -1;
}
ret = pthread_join(t1, &s);
if(ret)
{
printf("Thread join error\n");
return -1;
}
return 0;
}
2.2. 案例输出
2.2.1. 在主线程 malloc 之前
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread
Welcome to per thread arena example::6501
Before malloc in main thread
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ cat /proc/6501/maps
08048000-08049000 r-xp 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
08049000-0804a000 r--p 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804a000-0804b000 rw-p 00001000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
b7e05000-b7e07000 rw-p 00000000 00:00 0
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$
2.2.2. 在主线程 malloc 之后
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread
Welcome to per thread arena example::6501
Before malloc in main thread
After malloc and before free in main thread
...
sploitfun@sploitfun-VirtualBox:~/lsploits/hof/ptmalloc.ppt/mthread$ cat /proc/6501/maps
08048000-08049000 r-xp 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
08049000-0804a000 r--p 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804a000-0804b000 rw-p 00001000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804b000-0806c000 rw-p 00000000 00:00 0 [heap]
b7e05000-b7e07000 rw-p 00000000 00:00 0
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$
2.2.3. 在主线程 free 之后
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread
Welcome to per thread arena example::6501
Before malloc in main thread
After malloc and before free in main thread
After free in main thread
...
sploitfun@sploitfun-VirtualBox:~/lsploits/hof/ptmalloc.ppt/mthread$ cat /proc/6501/maps
08048000-08049000 r-xp 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
08049000-0804a000 r--p 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804a000-0804b000 rw-p 00001000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804b000-0806c000 rw-p 00000000 00:00 0 [heap]
b7e05000-b7e07000 rw-p 00000000 00:00 0
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread
Welcome to per thread arena example::6501
Before malloc in main thread
After malloc and before free in main thread
After free in main thread
Before malloc in thread 1
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ cat /proc/6501/maps
08048000-08049000 r-xp 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
08049000-0804a000 r--p 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804a000-0804b000 rw-p 00001000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804b000-0806c000 rw-p 00000000 00:00 0 [heap]
b7604000-b7605000 ---p 00000000 00:00 0
b7605000-b7e07000 rw-p 00000000 00:00 0 [stack:6594]
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$
2.2.5. 在 thread1 malloc 之后
ploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread
Welcome to per thread arena example::6501
Before malloc in main thread
After malloc and before free in main thread
After free in main thread
Before malloc in thread 1
After malloc and before free in thread 1
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ cat /proc/6501/maps
08048000-08049000 r-xp 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
08049000-0804a000 r--p 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804a000-0804b000 rw-p 00001000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804b000-0806c000 rw-p 00000000 00:00 0 [heap]
b7500000-b7521000 rw-p 00000000 00:00 0
b7521000-b7600000 ---p 00000000 00:00 0
b7604000-b7605000 ---p 00000000 00:00 0
b7605000-b7e07000 rw-p 00000000 00:00 0 [stack:6594]
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$
2.2.6. 在 thread1 free 之后
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread
Welcome to per thread arena example::6501
Before malloc in main thread
After malloc and before free in main thread
After free in main thread
Before malloc in thread 1
After malloc and before free in thread 1
After free in thread 1
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ cat /proc/6501/maps
08048000-08049000 r-xp 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
08049000-0804a000 r--p 00000000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804a000-0804b000 rw-p 00001000 08:01 539625 /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804b000-0806c000 rw-p 00000000 00:00 0 [heap]
b7500000-b7521000 rw-p 00000000 00:00 0
b7521000-b7600000 ---p 00000000 00:00 0
b7604000-b7605000 ---p 00000000 00:00 0
b7605000-b7e07000 rw-p 00000000 00:00 0 [stack:6594]
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$
3. Arena
3.1. Arena 的数量
For 32 bit systems:
Number of arena = 2 * number of cores.
For 64 bit systems:
Number of arena = 8 * number of cores.
3.2. Multiple Arena
3.3. Multiple Heaps
4. Chunk
4.1. Allocated chunk
4.2. Free chunk
5. Bins
5.1. Fast Bin
5.2. Unsorted Bin
5.3. Small Bin
大小小于 512 字节的 chunk 被称为 「small chunk」,而保存 small chunks 的 bin 被称为 「small bin」。在内存分配回收的速度上,small bin 比 large bin 更快。
数量:62
每个 small bin 都维护着一条 free chunk 的双向循环链表。采用双向链表的原因是,small bins 中的 chunk 可能会从链表中部摘除。这里新增项放在链表的头部位置,而从链表的尾部位置移除项。—— FIFO
chunk 大小:8 字节递增
Small bins 由一系列所维护 chunk 大小以 8 字节递增的 bins 组成。举例而言,
small bin[0]
(Bin 2)维护着大小为 16 字节的 chunks、small bin[1]
(Bin 3)维护着大小为 24 字节的 chunks ,依此类推……指定 small bin 中所有 chunk 大小均相同,因此无需排序;
合并 —— 相邻的 free chunk 将被合并,这减缓了内存碎片化,但是减慢了
free
的速度;malloc(small chunk)
初始情况下,small bins 都是 NULL,因此尽管用户请求 small chunk ,提供服务的将是 unsorted bin 路径而不是 small bin 路径;
第一次调用
malloc
时,维护在 malloc_state 中的 small bins 和 large bins 将被初始化,它们都会指向自身以表示其为空;此后当 small bin 非空,相应的 bin 会摘除其中最后一个 chunk 并返回给用户;
free(small chunk)
free
chunk 的时候,检查其前后的 chunk 是否空闲,若是则合并,也即把它们从所属的链表中摘除并合并成一个新的 chunk,新 chunk 会添加在 unsorted bin 的前端。
5.4. Large Bin
大小大于等于 512 字节的 chunk 被称为「large chunk」,而保存 large chunks 的 bin 被称为 「large bin」。在内存分配回收的速度上,large bin 比 small bin 慢。
数量:63
32 个 bins 所维护的 chunk 大小以 64B 递增,也即
large chunk[0]
(Bin 65) 维护着大小为 512B ~ 568B 的 chunk 、large chunk[1]
(Bin 66) 维护着大小为 576B ~ 632B 的 chunk,依此类推……16 个 bins 所维护的 chunk 大小以 512 字节递增;
8 个 bins 所维护的 chunk 大小以 4096 字节递增;
4 个 bins 所维护的 chunk 大小以 32768 字节递增;
2 个 bins 所维护的 chunk 大小以 262144 字节递增;
1 个 bin 维护所有剩余 chunk 大小;
每个 large bin 都维护着一条 free chunk 的双向循环链表。采用双向链表的原因是,large bins 中的 chunk 可能会从链表中的任意位置插入及删除。
这 63 个 bins
不像 small bin ,large bin 中所有 chunk 大小不一定相同,各 chunk 大小递减保存。最大的 chunk 保存顶端,而最小的 chunk 保存在尾端;
合并 —— 两个相邻的空闲 chunk 会被合并;
malloc(large chunk)
User chunk(用户请求大小)—— 返回给用户;
Remainder chunk (剩余大小)—— 添加到 unsorted bin。
初始情况下,large bin 都会是 NULL,因此尽管用户请求 large chunk ,提供服务的将是 next largetst bin 路径而不是 large bin 路劲 。
第一次调用
malloc
时,维护在 malloc_state 中的 small bin 和 large bin 将被初始化,它们都会指向自身以表示其为空;此后当 large bin 非空,如果相应 bin 中的最大 chunk 大小大于用户请求大小,分配器就从该 bin 顶端遍历到尾端,以找到一个大小最接近用户请求的 chunk。一旦找到,相应 chunk 就会被切分成两块:
如果相应 bin 中的最大 chunk 大小小于用户请求大小,分配器就会扫描 binmaps,从而查找最小非空 bin。如果找到了这样的 bin,就从中选择合适的 chunk 并切割给用户;反之就使用 top chunk 响应用户请求。
free(large chunk)
—— 类似于 small chunk 。
5.5. Top Chunk
一个 arena 中最顶部的 chunk 被称为「top chunk」。它不属于任何 bin 。当所有 bin 中都没有合适空闲内存时,就会使用 top chunk 来响应用户请求。
当 top chunk 的大小比用户请求的大小大的时候,top chunk 会分割为两个部分:
User chunk,返回给用户;
Remainder chunk,剩余部分,将成为新的 top chunk。
当 top chunk 的大小比用户请求的大小小的时候,top chunk 就通过 sbrk
(main arena)或 mmap
( thread arena)系统调用扩容。
5.6. Last Remainder Chunk
「last remainder chunk」即最后一次 small request 中因分割而得到的剩余部分,它有利于改进引用局部性,也即后续对 small chunk 的 malloc
请求可能最终被分配得彼此靠近。
那么 arena 中的若干 chunks,哪个有资格成为 last remainder chunk 呢?
当用户请求 small chunk 而无法从 small bin 和 unsorted bin 得到服务时,分配器就会通过扫描 binmaps 找到最小非空 bin。正如前文所提及的,如果这样的 bin 找到了,其中最合适的 chunk 就会分割为两部分:返回给用户的 User chunk 、添加到 unsorted bin 中的 Remainder chunk。这一 Remainder chunk 就将成为 last remainder chunk。
那么引用局部性是如何达成的呢?
当用户的后续请求 small chunk,并且 last remainder chunk 是 unsorted bin 中唯一的 chunk,该 last remainder chunk 就将分割成两部分:返回给用户的 User chunk、添加到 unsorted bin 中的 Remainder chunk(也是 last remainder chunk)。因此后续的请求的 chunk 最终将被分配得彼此靠近。
刘翔,童薇,刘景宁,冯丹,陈劲龙.动态内存分配器研究综述[J].计算机学报,2018,41(10):2359-2378.