Linux堆内存管理 #7
Description
Linux使用glibc动态库中的ptmalloc2来管理堆内存，它可以支持多线程下的堆内存管理。在早期的不支持多线程的堆内存管理时，因为线程共享虚拟地址空间，当有两个线程同时调用malloc函数的时候，只能有一个线程能够进入临界区，另一个线程阻塞。使用ptmalloc2后，通过维护多个arena的数据结构，为同时调用malloc函数的多个线程同时分配和回收内存。接下来我们来看它的实现原理。
一个示例
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <pthread.h>
void *ThreadFunc(void *arg)
{
printf("Before malloc in son thread1\n");
getchar();
char *addr = (char *)malloc(1000);
printf("After malloc and before free in son thread1\n");
getchar();
free(addr);
printf("After free in son thread1\n");
getchar();
}
int main(void)
{
pthread_t tid;
void *s = NULL;
int ret = 0;
char *addr = NULL;
printf("pid: %d\n", getpid());
printf("Before malloc in main thread\n");
getchar();
addr = (char *)malloc(100);
printf("After malloc and before free in main thread\n");
getchar();
free(addr);
printf("After free in main thread\n");
getchar();
ret = pthread_create(&tid, NULL, ThreadFunc, NULL);
if (ret == -1)
{
perror("pthread_create");
exit(-1);
}
ret = pthread_join(tid, &s);
if (ret == -1)
{
perror("pthread_join");
exit(-1);
}
return 0;
}主线程调用malloc之前：
[luckilzy@:~/work/my_test]$./arena
pid: 32438
Before malloc in main thread
After malloc and before free in main thread
...
[luckilzy@:~/test]$cat /proc/32438/maps
55f71287e000-55f71287f000 r-xp 00000000 08:10 157949419 /luckilzy/work/my_test/arena
55f712a7f000-55f712a80000 r--p 00001000 08:10 157949419 /luckilzy/work/my_test/arena
55f712a80000-55f712a81000 rw-p 00002000 08:10 157949419 /luckilzy/work/my_test/arena
55f713b18000-55f713b39000 rw-p 00000000 00:00 0 [heap]
...主线程调用malloc之后：
[luckilzy@:~/work/my_test]$./arena
pid: 32438
Before malloc in main thread
After malloc and before free in main thread
The Start address of 1000Bytes: 0x55f713b18a80
...
[luckilzy@:~/test]$cat /proc/32438/maps
55f71287e000-55f71287f000 r-xp 00000000 08:10 157949419 /luckilzy/work/my_test/arena
55f712a7f000-55f712a80000 r--p 00001000 08:10 157949419 /luckilzy/work/my_test/arena
55f712a80000-55f712a81000 rw-p 00002000 08:10 157949419 /luckilzy/work/my_test/arena
55f713b18000-55f713b39000 rw-p 00000000 00:00 0 [heap]
...在调用malloc之前就已经分配了132KB（55f713b18000-55f713b39000）的堆内存，这一块内存就叫做arena，因为这是主线程创建的所以就叫做main arena。调用malloc分配的1KB的内存就是从arena中划分的，当arena的空间不够用了的时候将会移动brk指针来扩充，相反，也可以移动brk指针来缩减。
主线程调用free之后：
[luckilzy@:~/work/my_test]$./arena
pid: 32438
Before malloc in main thread
After malloc and before free in main thread
The Start address of 1000Bytes: 0x55f713b18a80
After free in main thread
...
[luckilzy@:~/test]$cat /proc/32438/maps
55f71287e000-55f71287f000 r-xp 00000000 08:10 157949419 /luckilzy/work/my_test/arena
55f712a7f000-55f712a80000 r--p 00001000 08:10 157949419 /luckilzy/work/my_test/arena
55f712a80000-55f712a81000 rw-p 00002000 08:10 157949419 /luckilzy/work/my_test/arena
55f713b18000-55f713b39000 rw-p 00000000 00:00 0 [heap]
...调用free之后，没有并没有看到实际的变化。实际上glibc库将这空闲的1KB内存添加到了main arena的bin中了，bin是一个维护空闲内存块的列表。后续如果有申请内存的需要，内核将先从这个bin中查找是否有合适的内存块可以直接使用，当bin中没有合适的内存块时才会重新申请内存。
创建子线程后：
[luckilzy@:~/work/my_test]$./arena
pid: 32438
Before malloc in main thread
After malloc and before free in main thread
The Start address of 1000Bytes: 0x55f713b18a80
After free in main thread
Before malloc in son thread1
...
[luckilzy@:~/test]$cat /proc/32438/maps
55f71287e000-55f71287f000 r-xp 00000000 08:10 157949419 /luckilzy/work/my_test/arena
55f712a7f000-55f712a80000 r--p 00001000 08:10 157949419 /luckilzy/work/my_test/arena
55f712a80000-55f712a81000 rw-p 00002000 08:10 157949419 /luckilzy/work/my_test/arena
55f713b18000-55f713b39000 rw-p 00000000 00:00 0 [heap]
7f7e0a5eb000-7f7e0a5ec000 ---p 00000000 00:00 0
7f7e0a5ec000-7f7e0adec000 rw-p 00000000 00:00 0
...新出现的[7f7e0a5eb000-7f7e0a5ec000]和[7f7e0a5ec000-7f7e0adec000]这两个地址范围实际上是新创建线程的栈区。
子线程调用malloc后：
[luckilzy@:~/work/my_test]$./arena
pid: 32438
Before malloc in main thread
After malloc and before free in main thread
The Start address of 1000Bytes: 0x55f713b18a80
After free in main thread
Before malloc in son thread1
After malloc and before free in son thread1
The Start address of 1000Bytes: 0x7f7e04000b20
...
[luckilzy@:~/test]$cat /proc/32438/maps
55f71287e000-55f71287f000 r-xp 00000000 08:10 157949419 /luckilzy/work/my_test/arena
55f712a7f000-55f712a80000 r--p 00001000 08:10 157949419 /luckilzy/work/my_test/arena
55f712a80000-55f712a81000 rw-p 00002000 08:10 157949419 /luckilzy/work/my_test/arena
55f713b18000-55f713b39000 rw-p 00000000 00:00 0 [heap]
7f7e04000000-7f7e04021000 rw-p 00000000 00:00 0
7f7e04021000-7f7e08000000 ---p 00000000 00:00 0
7f7e0a5eb000-7f7e0a5ec000 ---p 00000000 00:00 0
7f7e0a5ec000-7f7e0adec000 rw-p 00000000 00:00 0
...分配出来了[7f7e04000000-7f7e04021000]和[7f7e04021000-7f7e08000000]这两块内存，工1MB。其中[7f7e04000000-7f7e04021000]这132KB的内存就和前面讲到的main arena类似，但这是属于子线程的，所以叫做thread arena。
子线程调用free之后：
[luckilzy@:~/work/my_test]$./arena
pid: 32438
Before malloc in main thread
After malloc and before free in main thread
The Start address of 1000Bytes: 0x55f713b18a80
After free in main thread
Before malloc in son thread1
After malloc and before free in son thread1
The Start address of 1000Bytes: 0x7f7e04000b20
After free in son thread1
...
[luckilzy@:~/test]$cat /proc/32438/maps
55f71287e000-55f71287f000 r-xp 00000000 08:10 157949419 /luckilzy/work/my_test/arena
55f712a7f000-55f712a80000 r--p 00001000 08:10 157949419 /luckilzy/work/my_test/arena
55f712a80000-55f712a81000 rw-p 00002000 08:10 157949419 /luckilzy/work/my_test/arena
55f713b18000-55f713b39000 rw-p 00000000 00:00 0 [heap]
7f7e04000000-7f7e04021000 rw-p 00000000 00:00 0
7f7e04021000-7f7e08000000 ---p 00000000 00:00 0
7f7e0a5eb000-7f7e0a5ec000 ---p 00000000 00:00 0
7f7e0a5ec000-7f7e0adec000 rw-p 00000000 00:00 0
...与在主线程中一样，glibc将这1KB的释放的内存放到thread arena的bin中了。
arena
在上面的例子中，主线程对应一个main arena， 子线程对应一个thread arena，但是当线程较多的时候，给每一个线程分配一个arena显示是不合适的。arena的数量和内核有如下关系：
- 32位编译下，arena最多是2*cpu核心数量+main arena
- 64位编译下，arena最多是8*cpu核心数量+main arena
现在假设有一个32位的程序运行在一个单核设备上，除了主线程之外还有3个子线程，所以最多可以创建三个arena。首先主线程会分配一个main arena，子线程1调用第一次malloc时会生成一个thread arena1，子线程2第一次调用malloc时会生成一个thread arena2，当子线程3调用malloc时便不能创建可用的arena了。此时子线程3按照以下步骤申请arena：
- 循环所有的arena，则尝试对其加锁。
- 如果加锁成功则返回并使用该arena。
- 如果该arena正在使用，则尝试申请下一个arena，直到得到一个可用的arena。
在glibc中主要有三个管理堆的数据结构：
- heap_info：堆的头部。一个arena可以有多个不同的堆，因为当一个堆的地址用完了之后需要映射一个新的堆。
- malloc_stat：arena的头部。一个arena可以有多个堆，但一个堆只属于一个arena。该部分记录了bins, top chunk, last remainder chunk的相关信息。
- malloc_chunck：块的头部。根据用户请求内存的需要，一个堆被分成了若干个块，块的头部记录了该块的信息，以及用于数据对齐。
main arena只有一个堆，因此没有heap_info，在main arena中当它的堆没有足够的空间时将移动brk指针来进行扩充。main arena的arena头部并不在它的堆段中，而是保存在glibc库中的全局变量。
chunk
一个块（chunk）包含了块的头部（malloc_chunk）和用户数据。一个堆中有四种chunk（块）：
- allocated chunk（已分配的块）
- free chunk（空闲块）
- top chunk（顶部块）
- last remainder chunk（最后剩余块）
allocated chunk
已分配的块的头部包含两部分：
- prev_size：如果前一个块是空闲的，则包含了前一个块的大小。如果前一个块是已经被分配的，则包含了前一个块的用户数据。
- size：包含本块的大小。最后的三个字节包含了标志位信息：
- PREV_INUSE：如果前一个块已经被分配，则标记该位。
- IS_MMAPPED：如果该块被映射（mmap得到），则标记该位。
- NON_MAIN_ARENA：如果该块属于某个thread arena，则标记该位。
free chunk
空闲块的头部包含四部分：
- prev_size：两个空闲块不能够相邻，因为它们将合并成为一个更大的空闲块。因此prev_size总是包含了上一个已经分配的块的用户数据。
- size：包含了该空闲块的大小。
- fd：指向同一个bin中前一个空闲块的指针。
- bk：指向同一个bin中后一个空闲块的指针。
top chunk
top chunk是一个arena最顶部的块，它不属于任何bin，当在任何bin中找不到合适的内存块的时候就会使用top chunk。当top chunk的大小大于用户需要的大小时将会被分为两部分：
- suer chunk（分配给用户的大小）
- remainder chunk（剩余的大小）
remainder chunk将会成为新的top chunk。当top chunk不够时，将会使用sbrk或者mmap系统调用来扩充。
last remainder chunk
当最近的一次内存分配请求从一个bin中拿出一个块，但是该块的大小比请求的大小要大，所以将该块分为两部分，其中一部分满足用户请求的大小返回给用户，剩下的那部分就是last remainder chunk。将这部分的last remainder chunk添加到unsorted bin中（下一小节会讲到），因为当用户再次请求一块内存的时候会先去unsorted bin中查找有没有足够大小的块，如果unsorted bin中有，则将unsorted bin中的这个块分出来一部分来满足用户请求。这样当用户连续两次请求一个较小的内存的时候，请求的这两部分内存将会是地址连续的，由此可以提高内存的局部性原理。
bins
bins是维护空闲块的链表。根据所维护的空闲块的大小分为不同的类型：
- fast bins
- unsorted bin
- small bins
- large bins
fast bins是用一个单独的链表数组来维护。其他的bins共有126个，第1个bin用于unsorted bin，第2个到第63个bins用于small bins，第64个到第126个bins用于large bins。
fast bins
大小为16到80字节的块称为fast chunk，fast bins中维护的是fast chunk，fast bins拥有更快的内存分配和回收速度。
fast bins中有10个fast bin，每一个fast bin都维护了一个单链表，因此其中的fast chunk只能在链表的头和尾部分配和回收。第一个fast bin中fast chunk的大小都是16字节，第二个fast bin中fast chunk的大小都是24字节，...，这样以8字节大小递增。fast bin中相邻的空闲块并不会合并成为更大的空闲块。
调用malloc函数从fast bins中分配内存的过程如下：
- 一开始的时候fast bins是空的，没有任何块，因此将会从small bin中分配。
- 当fast bins中有了fast chunk之后，就可以找到对应大小的fast bin链表。
- 从对应大小的fast bin链表的链表头取出一个fast chunk。
调用free函数回收一个fast chunk的过程如下：
- 根据该fast chunk的大小找到对应的fast bin链表。
- 将fast chunk插入到fast bin链表的头部
unsorted bin
当small bins或者large bins中的块被释放后，并不会立即再重新加入到small bins或者large bins中，而是将该块添加到unsorted bin中。基于局部性原理，该大小的块可能在不久的将来还会被使用，所以将其加入到unsorted bin中，再次分配的时候就不需要去相应的bins中遍历链表。
unsorted bin只有一个双向循环链表，其中的块的大小没有限制。
small bins
大小不超过512字节的块称为small chunk，small bins中维护的是small chunk，samll bins拥有比large bins更快的内存分配和回收速度。
small bins中有62个small bin，每一个small bin都维护了一个双向循环链表，方便将一个块从链表上取下来。第一个small bin中small chunk的大小都是16字节，第二个small bin中small chunk的大小都是24字节，...，这样以8字节大小递增。small bin中相邻的空闲可以合并成为更大的空闲块。
调用malloc函数从small bins中分配内存的过程如下：
- 一开始small bins是空的，因此需要先从别处来分配内存，比如unsorted bin。
- small bins还将初始化自身的双向循环链表的数据结构，将其指向自身（空的）。
- 当mall bins非空的时候，找到对应大小的samll bin链表，取出链表头部的一个small chunk给用户。
调用free函数回收一个small chunk的过程如下：
- 检查该块前后指针指向的块是否是空闲的，如果有空闲的，将他们合并后从链表上取出放到unsorted bin中。
large bins
大于等于512字节的块称为large chunk，large bins中维护的是large chunk，large bins的内存分配和回收速度要小于small bins。
large bins中有63个large bin，每一个large bin都维护了一个双向循环链表，方便将一个块从链表上取下来。这63个large bin维护的large chunk的大小如下：
- 前32个large bin维护的large chunk以64字节大小递增，第一个large bin中large chunk的大小都是512字节到575字节之间，第二个large bin中large chunk的大小都是576字节到639字节之间，...。
- 12个large bin维护的large chunk以512字节大小递增。
- 8个large bin维护的large chunk以4096字节大小递增。
- 4个large bin维护的large chunk以32768字节大小递增。
- 2个large bin维护的large chunk以262144字节大小递增。
- 1个large bin维护的large chunk为remaining的大小。
因为同一个large bin链表中块的大小是不一定相同的，所以large bin链表中的块是按照从大到小排序的，大块在链表头，小块在链表尾。两个相邻的空闲块同样会被合并为更大的空闲块。
调用malloc函数从large bins中分配内存的过程如下：
- 一开始large bins是空的，因此需要先从别处来分配内存，比如top chunk。
- large bins还将初始化自身的双向循环链表的数据结构，将其指向自身（空的）。
- 当large bins非空的时候，如果当前的large bin中的最大的块比需要的内存大，那么沿着该链表向下找到一个能够满足用户需求的最小的块，并请该块分为两部分：
-
- user chunk：用户实际需要的大小，返回给用户。
-
- remainder chunk：分配给用户之后剩余的内存，添加到unsorted bin中。
- 如果当前的large bin中的最大的块比需要的内存小，则再去下一个更大的large bin中请求。如果所有的large bin都无法满足需求将使用top chunk。
调用free函数回收一个large chunk的过程和small bins类似。
