堆的学习流程

前置知识

内存布局

  • 一个程序典型的内存布局如下图所示：从高地址到低地址分别为内核空间、栈、空闲区域、堆、bss、data、text。主要的就是这几个段，其他的可能有，但是不重要。
    • 栈是自顶向下增长
    • 堆是自底向上增长

虚拟内存空间划分

虚拟内存机制

  • 放CSAPP的博客里面

堆管理器的简单实现

PWN-C语言函数分析 | iyheart的博客

常见的堆管理机制

1
2
3
4
5
6
7
8
9
10
11
dlmalloc    General purpose allocator
优秀的动态内存分配器

ptmalloc2   glibc
glibc里面的内存分配器

jemalloc    Firefox


tcmalloc     chrome
谷歌开发的内存分配器

ptmalloc

前面的这些内容主要是以glibc2.23版本的ptmalloc介绍，在介绍完2.23ptmalloc之后还会补充2.27新增的tcache和其他版本新增的ptmalloc管理机制

brk和mmap函数

  • Linux系统向用户提供申请的内存有brk(sbrk)和mmap函数

brk()和sbrk()

  • 对于每个进程，内核维护着一个变量brk，它指向堆的顶部。
1
2
3
#include<unistd.h>
int brk( const void *addr);
void* sbrk( intptr_t incr);

这两个函数的作用就是扩展heap的上界brk。

  • brk()的参数设置为新的brk上界地址，成功返回1，失败返回0.
  • sbrk()的参数为申请内存的大小，返回heap新的上界brk的地址。

对于brk()运行过程如下图所示

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
54
55
56
/*在程序刚开始运行的时*/
/*程序还没有申请堆内存*/
/*此时brk所指向的位置就会为数据段的末尾*/
高地址
---------
|  栈    |  <- 栈顶
---------
|        |
|  空闲  |
|  区域  |
|        |
---------
|        |  <- 堆
---------
|数据段结尾|	<- brk = 0x08040000
---------
|  bss   |  
---------
| .data  |  
---------
| .text  |  
---------
低地址

//当调用brk()函数申请堆内存时,如：
brk(0x8041000);
//这时brk指针的值就会被设置为0x8041000,指向新的堆顶
//这时也就将堆内存申请过来了

高地址
---------
|  栈    |  <- 栈顶
---------
|        |
|  空闲  |
|  区域  |
|        |
---------
|  新堆顶  |  <- brk=0x8041000 返回新的堆顶指针
---------
| 新分配的堆 |  <- 0x1000 字节的新堆内存
---------
|  原堆顶  |  <- 0x8040000 之前的堆顶指针
---------
|        |  <- 堆
---------
|数据段结尾|
---------
|  bss   |  
---------
| .data  |  
---------
| .text  |  
---------
低地址

对于srbk()运行过程如下图所示

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
54
55
//在程序刚开始运行，没有申请堆时，brk指针依然指向bss段的结尾
高地址
---------
|  栈    |  <- 栈顶
---------
|        |
|  空闲  |
|  区域  |
|        |
---------
|        |  <- 堆
---------
|数据段结尾|	<- brk = 0x08040000
---------
|  bss   |  
---------
| .data  |  
---------
| .text  |  
---------
低地址
    
// 当调用sbrk()函数时
sbrk(0x1000);
//此时sbrk()会开辟0x1000大小的堆
//在sbrk()函数内部还会自动调整brk指针
//还会返回新堆顶的地址

高地址
---------
|  栈    |  <- 栈顶
---------
|        |
|  空闲  |
|  区域  |
|        |
---------
|  新堆顶  |  <- brk   sbrk(0x1000)返回新的堆顶指针
---------
| 新分配的堆 |  <- 1000 字节的新堆内存
---------
|  原堆顶  |  <- 之前的堆顶指针
---------
|        |  <- 堆
---------
|数据段结尾|
---------
|  bss   |  
---------
| .data  |  
---------
| .text  |  
---------
低地址

mmap()

1
2
3
#include <sys/mman.h>
void *mmap(void *addr, size\_z length, int prot,int flags,int fd, off\_t offset);
int munmap(void *addr, size_t length);

  • Mmap的第一种用法是映射磁盘文件到内存中；第二种用法是匿名映射，不映射磁盘文件，而向映射区申请一块内存

  • Malloc使用的是mmap的第二种用法（匿名映射）

  • Munmap函数用于释放内存

映射磁盘文件到内存中的过程

  • 这里要注意mmap()和brk()/sbrk()这两种不同方式申请的堆内存是互相独立的，各自管理不同的内存区域，使用mmap时并不会自动调整brk指针。
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
54
55
56
57
58
//初始状态
高地址
---------
|  栈    |  <- 栈顶
---------
|        |
|  空闲  |
|  区域  |
|        |
---------
|  堆顶  |  <- sbrk(0) 返回当前堆顶指针
---------
|        |  <- 堆
---------
|  bss   |  
---------
| .data  |  
---------
| .text  |  
---------
低地址
    
//打开文件并获取大小
int fd = open("example.txt", O_RDWR);
struct stat sb;
fstat(fd, &sb);

//调用mmap映射文件到内存
void *mapped_memory = mmap(NULL, sb.st_size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);

高地址
---------
|  栈    |  <- 栈顶
---------
|        |
|  空闲  |
|  区域  |
|        |
---------
|  堆顶  |  <- sbrk(0) 返回当前堆顶指针
---------
|        |  <- 堆
---------
|        |  
---------
| mmap   |  <- 通过 mmap 映射的文件内容
---------
|        |  
---------
|  bss   |  
---------
| .data  |  
---------
| .text  |  
---------
低地址


匿名映射的过程

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
高地址
---------
|  栈    |  <- 栈顶
---------
|        |
|  空闲  |
|  区域  |
|        |
---------
|  堆顶  |  <- brk(0) 返回当前堆顶指针
---------
|        |  <- 堆
---------
|  bss   |  
---------
| .data  |  
---------
| .text  |  
---------
低地址

// 分配一个内存页的内存大小4096
void *mapped_memory = mmap(NULL, pagesize, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

高地址
---------
|  栈    |  <- 栈顶
---------
|        |
|  空闲  |
|  区域  |
|        |
---------
|  堆顶  |  <- brk(0) 返回当前堆顶指针（未改变）
---------
|        |  <- 堆
---------
|        |  
---------
| mmap   |  <- 通过 mmap 分配的匿名内存区域
---------
|        |  
---------
|  bss   |  
---------
| .data  |  
---------
| .text  |  
---------
低地址

Allocator

Malloc实现原理

  • 因为brk、sbrk、mmap都属于系统调用，若每次申请内存，都调用这三个函数的其中一个，那么每次都会产生系统调用，会影响性能。
  • 这样申请的内存容易产生碎片，因为堆是从低地址到高地址，如果高地址的内存没有被释放，低地址的内存就没办法回收
  • malloc采用的是内存池的管理方式(ptmalloc)，Ptmalloc采用边界标记法将内存划分成很多块(chunk)，从而堆内存的分配与回收进行管理。
  • 为了内存分配函数malloc的高效性，ptmalloc会将这些内存管理起来，并通过一些策略来判断是否将其回收给操作系统。
  • 使用户申请和释放内存的时候更加高效，避免产生过多的内存碎片

chunk内存块的基本组织单元

  • 在ptmalloc的实现源码中定义结构体malloc_chunk来描述这些块。
1
2
3
4
5
6
7
8
9
10
11
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; 
};

简单说明chunk里面的数据

chunk结构体里面的数据可以结合后面的ptmalloc边界标记法具体过程一起看

  • prev_size: 如果前面一个块是空闲的，该区域表示前一个chunk的大小，如果前一个chunk不空闲，该域无意义。

  • size：当前chunk的大小，并且记录了当前chunk和前一个chunk的一些属性（记录在size的最后3个位中），包括前一个chunk是否在使用中，当前chunk是否通过mmap获得的内存，当前chunk是否属于非主分配区

  • fd和bk：
    • 指针fd和bk只有当该chunk块空闲时存在，其作用是用于将对应的空闲chunk块加入到空闲chunk块链表统一管理
    • 如果该chunk块被分配给应用程序使用那么这两个指针也就没有用（该chunk块已经从空闲链中拆除）了，所以也当做应用程序的使用空间，而不至于浪费
    • 在ptmalloc实现中使用双向循环链表来组织空闲块
    • 空闲chunk通常使用头插法插入到适当的空闲链表中，这就意味着后释放的空闲块在链表的前面，再次申请大小相同的chunk（大小相同这个词在这里用的不妥当，可以先这么理解，后面再深入）申请到的是最后被释放的相应大小的内存空间中。这一点是比较重要的，对于后续的pwn堆题uaf等需要明白这一点
  • fd_nextsize和bk_nextsize:
    • 当前的chunk存在于large_bin时,large_bin中空闲chunk是按照大小排序的，但同一个大小的chunk可能有多个。
    • 增加的这两个字段可以加快遍历空间chunk，并满足需要的空间chunk
    • fd_nextsize指向下一个比当前chunk内存大的第一个空间chunk（个人觉得是指向头结点，还不太清楚）
    • bk_nextsize指向前一个比当前chunk内存小的第一个空闲chunk
    • 同一大小的chunk块可能有很多空闲的，如果没有设置fd_nextsize和bk_nextsize这两个指针，那么就需要遍历所有相同大小的chunk之后，才能找到满足需要的大小的chunk。非常影响效率
    • 如果该chunk块被分配给应用程序使用，那么这两个指针也就没有用(该chunk块已经从size链中拆除)了，这样也可以当做应用程序的使用空间，能较好的使用程序空间

chunk的结构视图

  • chunk的结构可以分为使用中的chunk和空闲中的chunk。使用中的chunk和空闲的chunk数据结构基本相同，但是会有一些设计上的小技巧，可以节省内存空间

使用中的chunk

img

​ chunk、men、next_chunk

这三个指针，在一些函数中被定义为局部变量，然后通过计算，返回相应的地址

1
2
3
4
5
6
7
8
// 获取用户数据部分的指针
#define chunk2mem(p) ((void*)((char*)(p) + 2 * sizeof(size_t)))

// 从用户数据指针获取chunk指针
#define mem2chunk(mem) ((mchunkptr*)((char*)(mem) - 2 * sizeof(size_t)))

// 获取下一个chunk的指针
#define next_chunk(p) ((mchunkptr*)((char*)(p) + ((p)->size & ~0x7)))
  • chunk指针指向chunk开始的地址
  • men指针指向用户内存块开始的地址
  • next_chunk指针指向的是下一个chunk中，size变量的位置，而不是prev_size变量的位置

​ size中的三个标志位A、M、P

  • p=0时，表示前一个chunk为空闲，prev_size才有效
  • p=1时，表示前一个chunk正在使用，prev_size无效p主要用于内存块的合并操作；ptmalloc分配的第一个块总是将p设置为1，以防止程序引用到不存在的区域
  • M=1为mmap映射区域分配，M=0为heap区域分配
  • A=0为主分配区分配，A=1为非主分配区分配

空闲的chunk

img

  • 当chunk空闲时，其M状态是不存在的，只有AP状态(因为M表示是由brk还是mmap分配的内存，而mmap分配的内存free时直接ummap，不会放到空闲链表中。)换言之空闲链表中的都是brk分配的，所以不用额外记录
  • 原本是用户数据的区域开头存储了四个指针
    • 指针fd指向后一个空闲的chunk，bk指向前一个空闲的chunk，malloc通过这两个指针将大小相近的chunk连成一个双向链表
    • 在large_bin中空闲chunk，还有两个指针，fd_nextsize和bk_nextsize，用于加快在large_bin中查找最近匹配的空闲chunk。不同的chunk链表又是通过bins或者fastbins来组织的(这里后面会介绍)

chunk中的空间复用

  • 一个chunk或正在被使用，或者已经被free掉。为了使得chunk所占用的空间最小，ptmalloc使用了空间复用。所以chunk中一些域可以再使用状态和空闲状态表示不同的意义。来达到空间复用的效果
  • 空闲时，一个chunk中至少要4个size_t大小的空间，用来存储prev_size、size、fd、bk，也就是16bytes。(注意：有时候chunk并不需要fd_nextsize和bk_nextsize，这个之后在空闲链表会介绍)
  • chunk的大小要align到8bytes。当一个chunk处于使用状态时，它的下一个chunk的prev_size域肯定是无效的。这个域可以被当前chunk使用
  • 所以，in_use_size=(用户请求大小+8-4)align to 8 bytes（这里的单位为字节）这里加8是因为需要存储prev_size和size，但又因为向下一个chunk“借”了4个bytes，所以要减去4。但是空闲的chunk和使用中的chunk使用的是同一块空间。要取这两者之间的最大值。所以最终分配的空间为chunk_size=max(in_use_size,16)。

注意：在后面的介绍中，如果不是特别指明的地方，指的都是这个经过转换的实际需要分配的内存大小，而不是用户请求的内存分配大小

空闲链表bins

  • 首先bins是一个链表数组，用来管理一系列的chunk。
  • 总体预览，ptmalloc中定义了malloc_state结构体用来统一管理bins。（而不是分别声明fast_bin、unsorted_bin），这就可以使他们在内存上是线性关系的。
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
54
55
56
57
58
59
60
61
62
63
64
65
#include <stddef.h>

// 内存块结构定义
typedef struct malloc_chunk {
    size_t prev_size;    // 前一个块的大小
    size_t size;         // 当前块的大小
    struct malloc_chunk* fd; // 前向指针
    struct malloc_chunk* bk; // 后向指针
} mchunkptr;

// 分配器状态结构定义
typedef struct malloc_state {
    mchunkptr* fastbinsY[10];  // fast bins数组，简化为10个大小
    mchunkptr* unsorted_bin;   // unsorted bin链表头
    mchunkptr* smallbins[64];  // small bins数组，简化为64个大小
    mchunkptr* largebins[64];  // large bins数组，简化为64个大小
    // 其他管理信息
} mstate;

// 初始化malloc_state
void init_malloc_state(mstate* state) {
    for (int i = 0; i < 10; ++i) {
        state->fastbinsY[i] = NULL;
    }
    state->unsorted_bin = NULL;
    for (int i = 0; i < 64; ++i) {
        state->smallbins[i] = NULL;
        state->largebins[i] = NULL;
    }
}


+---------------------------+
|       malloc_state        |
|                           |
| +-----------------------+ |
| |       fastbinsY       | |
| | +-----+  +-----+     | | 
| | | * ->|->| * ->|->...| | 
| | +-----+  +-----+     | |
| +-----------------------+ |
|                           |
| +-----------------------+ |
| |     unsorted_bin      | |
| | +-----+              | | 
| | | * ->|-> NULL       | | 
| | +-----+              | |
| +-----------------------+ |
|                           |
| +-----------------------+ |
| |       smallbins       | |
| | +-----+  +-----+     | | 
| | | * ->|->| * ->|->...| | 
| | +-----+  +-----+     | |
| +-----------------------+ |
|                           |
| +-----------------------+ |
| |       largebins       | |
| | +-----+  +-----+     | | 
| | | * ->|->| * ->|->...| | 
| | +-----+  +-----+     | |
| +-----------------------+ |
|                           |
+---------------------------+

  • 当用户使用free函数释放掉内存，ptmalloc并不会马上将其交给操作系统，而是被ptmalloc本身的空闲链表bins管理起来。

  • 这样当下次进程需要使用malloc申请堆内存的时候，ptmalloc就会从空闲的bins上寻找一块合适大小的内存块分配给用户使用。可以避免频繁系统调用，提高程序运行效率，降低内存分配开销

  • malloc将相似大小的chunk用双向链表链接起来，这样的一个链表被称为一个bin。ptmalloc一共维护了128个bin（也就是说维护了128个双向链表）。每个bins都维护了大小相近的双向链表chunk。根据chunk大小分为以下几种bins：

    • Fast bin
    • Unsorted bin
    • Small bin
    • Large bin

  • 保存这些数据结构为

    • fastbinsY：这个数组以保存fast_bins
    • bins: 这个数组以保存unsorted、small以及large_bins，共计可容纳126个

  • 当用户调用malloc的时候，能很快找到用户需要分配的内存大小是否在维护的bin上，如果在某一个bin上，就可以通过双向链表去查找合适的chunk内存块给用户使用

  • fast_bins中的chunk，size最后一位始终置1，这是为了防止fast_bin中chunk的内存合并

fast_bins

  • 程序在运行时会经常需要申请和释放较小的内存空间。当分配器合并了几个相邻的几个小的chunk之后。也许马上就会有另一个小块内存的请求。这样分配器又需要从大的空闲内存中切分出一块，但是这样低效。
  • 因此malloc引入了fast_bins
  • fast_bins特点：当一个chunk被释放到fast_bins时，它不会立即被合并到相邻的空闲块中，即使有相邻的空闲块，这些块也不会被合成一个更大的块

工作机制

1.释放到Fast_Bins：当一个小的chunk被释放时，如果它的大小适合放入”fast_bins”中，那么它会被直接添加到对应的“fast_bin”链表中

2.分配内存：当需要分配一个小块内存时， 首先检查对应的”fast_bin”链表。如果链表中有可用的chunk，则直接从链表头部取出chunk进行分配

3.延迟合并：“fast_bins”中的块不会立即与相邻空间块合并。只有在执行内存分配操作，且需要更大的块时，或者在合适的时机(如进行垃圾回收或者重新分配时)，才会将”fast_bins”中的块合并

链表介绍

  • fast_bin是bins的高速缓冲区，大约有10个定长队列。
  • 每个fast_bin都记录着一条free_chunk的单链表，由于使用头插法，所以增删chunk都发生在链表的前端
  • fast_bin数组记录着大小以8字节递增的bin链表，但是由于是在虚拟内存中，地址只占了4字节，剩下的高4字节就补0了
  • 当用户释放一块不大于max_fast（默认值64B）的chunk的时候，会默认放到fast_bin上，当需要给用户分配的chunk小于或等于max_fast时，malloc首先会到fast_bins上寻找是否有合适的chunk。（一定大小内的chunk无论是分配还是是否都会先在fast_bin中过一遍，这里过一遍是指先根据请求的大小，求出对应的索引，然后直接查看该索引位置的链表，并不是直接遍历整个数组）
  • 除非特定情况，两个毗连的空闲chunk并不会合成一个空闲的chunk。不合并可能会导致碎片化问题，但是却可以大大加速释放的过程
  • 分配时binlist中被检索的第一个chunk，将被摘除并返回给用户。free掉的chunk将被添加在索引到的binlist的前端

unsorted_bin

  • unsorted_bin的队列使用bins数组的第一个，是bins的一个缓冲区，加快分配的速度。当用户释放的内存大于max_fast或者fast_bins合并后的chunk都会首先进入unsorted_bin上
  • chunk大小没有尺寸的限制。任何大小chunk都可以添加进这里。
  • 这种途径给予glibc_malloc第二次机会以重新使用最近free掉的chunk，这样寻找合适bin的时间开销就没了。因此内存的分配和释放会更快一些
  • 用户malloc时，如果在fast_bin中没有找到合适的chunk，则malloc会先在unsorted_bin中查找合适的空闲chunk,如果没有合适的bin，ptmalloc会将unsorted_bin上的chunk放入bins上然后到bins上查找合适的空闲chunk

small_bins

  • 大小小于512字节的chunk被称为small_chunk，而保存small_chunks的bins被称为small_bin。
  • small_bin每个bin之间相差8个字节，同一个small_bin中chunk具有相同的大小
  • 每个small_bin都包括一个空闲区块的双向循环链表（也称binlist）。free掉的chunk添加在链表的前端，而所需chunk则从链表后端摘除。这与fast_bin所申请重复使用chunk的机制有所不同
  • 两个毗连的空闲chunk会被合并成一个空闲chunk。合并消除了碎片化的影响但是减慢了free的速度
  • 分配时，当small_bin非空后，相应的bin会摘除binlist最后一个chunk并返回给用户。在free一个chunk的时候，检查其前或其后的chunk是否空闲，若空闲则合并。也就是把它们从所属的链表中摘除并合并成一个新的chunk，新的chunk会添加在unsorted bin链表的前端
  • 下面是small_bin的双向链表比较形象的图片
1
2
3
4
5
6
7
8
9
10
11
12
13
+-------------------------------------------+
|              malloc_state                 |
|                                           |
| +-----------+  +-----------+  +---------+ |
| | smallbins |  | smallbins |  |  ...    | |
| |  [0]      |  |  [1]      |  |         | |
| | +---+     |  | +---+     |  |         | |
| | | * |---->|  | | * |---->|  |         | |
| | +---+     |  | +---+     |  |         | |
| +-----------+  +-----------+  +---------+ |
|                                           |
+-------------------------------------------+

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
smallbins[0] -->  +-----------+     +-----------+     +-----------+
                  | chunk A   |     | chunk B   |     | chunk C   |
                  +-----------+     +-----------+     +-----------+
                  | size      |     | size      |     | size      |
                  |  ...      |     |  ...      |     |  ...      |
                  | fd  ----->|---->| fd  ----->|---->| fd  ----->|
                  | bk  <-----|<----| bk  <-----|<----| bk  <-----|
                  +-----------+     +-----------+     +-----------+
                  | user data |     | user data |     | user data |
                  +-----------+     +-----------+     +-----------+

smallbins[1] -->  +-----------+     +-----------+     +-----------+
                  | chunk D   |     | chunk E   |     | chunk F   |
                  +-----------+     +-----------+     +-----------+
                  | size      |     | size      |     | size      |
                  |  ...      |     |  ...      |     |  ...      |
                  | fd  ----->|---->| fd  ----->|---->| fd  ----->|
                  | bk  <-----|<----| bk  <-----|<----| bk  <-----|
                  +-----------+     +-----------+     +-----------+
                  | user data |     | user data |     | user data |
                  +-----------+     +-----------+     +-----------+

large_bins

  • 大小大于等于512字节的chunk被称为large_chunk，而保存large_chunks的bin被称为large_bin，位于small_bins后面。
  • large_bins中的每一个bin分别包含了一个给定范围内的chunk，其中的chunk按大小递减排序，大小相同则按照最近使用时间排序
  • 两个毗连的空闲chunk会被合并成一个新空闲chunk
  • 分配时，遵循原则“smallest-fist,best-fit”，从顶部遍历到底部以找到一个大小最接近用户需求的chunk。一旦找到，相应chunk就会分成两个块User chunk（用户请求大小）返回给用户
  • Remainder chunk剩余部分添加到unsorted_bin。free和small_bin类似

三种特殊chunk

top chunk

  • top_chunk相当于分配区的顶部空闲内存(可能就是由brk调用控制的brk指针)，当bins上都不能满足内存分配要求的时候，就会来top_chunk上分配
  • 当top_chunk大小比用户所请求大小还大的时候，top_chunk会分为两个部分：User_chunk（用户请求大小）和Remainder_chunk(剩余大小)。其中Remainder chunk成为新的top_chunk
  • 当top_chunk大小小于用户所请求的大小时，top_chunk就通过sbrk（main arena）或mmap（thread arena）系统调用来扩容

mmaped chunk

  • 当分配的内存非常大（大于分配阈值，默认128KB）的时候，需要被mmap映射，则会放到mmaped_chunk上。当释放mmaped_chunk上的内存的时候会直接交还给操作系统。chunk中M标志位置1

last remainder chunk

  • Last remainder chunk是另外一种特殊的chunk，就像top_chunk和mmaped_chunk一样，不会在任何bins中找到这种chunk。当需要分配一个small_chunk大小，last remainder chunk被分裂成两个chunk，其中一个chunk返回给用户，另一个chunk变成新的last remainder chunk
  • 在ptmalloc中unlink函数用于从空闲链表中移除一个内存块。这个过程涉及调整链表指针以确保内存块被正确移除，并且其他空闲块的链接不会受到影响。
  • unlink函数在glibc中存在两个版本，一个是过去使用的unlink还有一个是当前在使用的unlink
  • 旧版的unlink函数负责将一个空闲块从双向链表中移除。这个过程需要更新表中的前向和后向指针，确保移除块之后，链表仍然保持正确的结构。
  • 假设用一个空闲链表，由三个块A、B、C组成，每个块包含前向指针fd和后向指针bk
1
2
3
4
5
6
7
+---------+     +---------+     +---------+
|   A     |     |   B     |     |   C     |
+---------+     +---------+     +---------+
| fd: B   |<--->| fd: C   |<--->| fd: NULL|
| bk: NULL|     | bk: A   |     | bk: B   |
+---------+     +---------+     +---------+

  • 当要移除中间的块B
    • 先确定前后块，B块的前一个块是A块，B块的后一个块是C块
    • 更新前一个块的fd指针，将A块的fd指向C块
    • 更新后一个块的bk指针，将C块中的bk指向A块
  • 移除块B之后的空闲块结构头如下
1
2
3
4
5
6
7
+---------+     +---------+
|   A     |     |   C     |
+---------+     +---------+
| fd: C   |<--->| fd: NULL|
| bk: NULL|     | bk: A   |
+---------+     +---------+

  • 当前的unlink函数对移除块的操作和旧版的unlink函数一样，但是在移除的过程中多了检查
  • 先要验证块的大小，确认当前块P的大小与下个块next_chunk(P)的前一个块大小是否匹配，这里next_chunk(P)指的是与当前块P内存连续的块，而不是在逻辑上连续的块
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
+-----------+     +-----------+
|  P 块     |     | next_chunk|
+-----------+     +-----------+
| size: 32  |     | size: ... |
| 其他数据  |     | 其他数据  |
+-----------+     +-----------+
      ↑                 ↑
      |                 |
    P 块起始地址     P 块起始地址 + 块大小（32）


if (__builtin_expect (chunksize(P) != prev_size(next_chunk(P)), 0)) {
    malloc_printerr ("corrupted size vs. prev_size");
}
chunksize(P)获取当前块'P'的大小
next_chunk(P)获取当前块'P'的下一个块
prev_size(next_chunk(P))获取下一个块的前一个块大小
比较'chunksize(P)'和'prev_size(next_chunk(P))'的值，如果不相等，说明内存块的大小信息被破坏，程序报告错误
malloc_printerr ("corrupted size vs. prev_size")
  • 在验证完内存上的块大小是否匹配，接下来需要验证逻辑上块，指针指向的地址是否出现错误，如果错误就报错
1
2
3
if (__builtin_expect (FD->bk != P || BK->fd != P, 0)) {
    malloc_printerr ("corrupted double-linked list");
}
  • 接下来就是和旧版unlink一样的操作

区别

  • 旧版本的unlink和当前版本的unlink主要区别在于安全性和对指针操作的验证

  • 对于旧版的unlink直接操作双向链表中的前向指针fd和后向指针bk，没有做太多的安全检查。这种实现方式比较高效，但是存在安全隐患，例如double free的堆漏洞会出现

1
2
3
4
5
6
7
#define unlink(P, BK, FD) { 
  BK = P->bk; 
  FD = P->fd; 
  FD->bk = BK; 
  BK->fd = FD; 
}
P是需要移除的块，BK是前一个块，FD是后一个块。
  • 当前版本的ptmalloc通过添加多种安全检查来防止潜在的安全漏洞。例如在glibc 2.25中的unlink函数实现大致如下
1
2
3
4
5
6
7
8
9
#define unlink(AV, P, BK, FD) { 
  if (__builtin_expect (chunksize(P) != prev_size(next_chunk(P)), 0)) 
    malloc_printerr ("corrupted size vs. prev_size"); 
  if (__builtin_expect (FD->bk != P || BK->fd != P, 0)) 
    malloc_printerr ("corrupted double-linked list"); 
  FD->bk = BK; 
  BK->fd = FD; 
}
块前大小检查，前向、后向指针的有效性检查

补充

  • 在large_bin中的检查
1
2
3
4
// largebin 中 next_size 双向链表完整性检查 
if (__builtin_expect (P->fd_nextsize->bk_nextsize != P, 0)|| __builtin_expect (P->bk_nextsize->fd_nextsize != P, 0))    \
	malloc_printerr (check_action,"corrupted double-linked list (not small)",P, AV);
//检查largebin中要移除的块在逻辑上的前一个块指向的后一个块是否为P，再检查后一个块的前一个块指向的是否为P

首次申请堆

  • 在堆区中，start_brk指向heap的开始，而brk指向heap的顶部。
    • 可以使用系统调用brk()和sbrk()来增加标识heap顶部的brk值
    • 使得线性地增加分配给用户的heap空间
    • 在使用malloc之前，brk的值等于start_brk，也就是说heap大小为0
  • ptmalloc在开始时，若请求的空间小于mmap分配的阈值(mmap threshold，默认值为128KB)时，主分配区会调用sbrk()增加一块大小为（128KB +chunk_size）align 4KB(页面大小对齐)的空间作为heap。非主分配区会调用mmap映射一块大小为HEAP_MAX_SIZE(32位系统上默认为1MB，64位系统上默认为64MB)的空间作为sub-heap。这就是前面说的ptmalloc所维护的分配空间
  • 当用户请求内存分配时，首先会在这个区域内（heap）找一块合适的chunk给用户。当用户释放了heap中的chunk时，ptmalloc又会使用fastbins和bins来组织空闲的chunk。以备用户的下一次分配
  • 若需要分配的chunk大小小于mmap分配阈值，而heap空间又不够，则此时主分配区会通过sbrk()调用来增加heap大小，非主分配区会调用mmap映射一块新的sub-heap，也就是增加了top chunk的大小，每次heap增加的值都会对齐到4KB。
  • 当用户请求超过mmap分配阈值，并且主分配区使用sbrk()分配失败的时候，或是非主分配区在top chunk中不能分配到需要的内存时，ptmalloc会尝试使用mmap()直接映射一块内存到进程内存空间。
  • 使用mmap（）直接映射的chunk在释放时直接解除映射，而不再属于进程的内存空间。任何对该内存的访问都会产生段错误。而在heap中或是sub-heap中分配的空间则可能会留在进程内存空间内，还可以再次引用（但是很危险）

分配区(arena)

  • 分配区初学只需要稍微了解，等大致了解了ptmalloc后，可以再深入了解，多线程竞争题可能会考到

  • 在ptmalloc中，内存分配管理区域主要分为主分配区(main arena)和非主分配区(non-main arenas)。这种设计是为了在多线程环境中提高内存分配和释放的效率，这样避免锁锁竞争

主分配区

非主分配区

内存分配malloc流程

内存回收流程

注意事项

ptmalloc后续版本新增

tcache

参考博客：关于如何理解Glibc堆管理器(Ⅶ——Tcache Bins!!)_tcachebins-CSDN博客

  • 在glibc 2.26版本开始引入了tcache（Thread-Local Caching），以提高多线程程序的内存分配性能。ptmalloc2.27版本继承了这一机制，并在一定程度上优化了内存管理。

tcache结构

  • 每个线程都有一个tcache_perthread_struct结构体，该结构体即为Tcache Bins的结构体
  • 可以注意到，每个线程最多只能有64个Tcache Bin，且用单项链表储存free chunk，这与Fast Bin是相同的，且它们储存chunk的大小也是严格分类，因此这一点上也相同
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/* We overlay this structure on the user-data portion of a chunk when the chunk is stored in the per-thread cache.  */
# define TCACHE_MAX_BINS		64
 typedef struct tcache_entry
 {
   struct tcache_entry *next;
  /* This field exists to detect double frees.  */
  struct tcache_perthread_struct *key;
 } tcache_entry;
/* There is one of these for each thread, which contains the per-thread cache (hence "tcache_perthread_struct").  Keeping overall size low is mildly important.  Note that COUNTS and ENTRIES are redundant (we could have just counted the linked list each time), this is for performance reasons.  */
typedef struct tcache_perthread_struct
{
  char counts[TCACHE_MAX_BINS];
  tcache_entry *entries[TCACHE_MAX_BINS];
} tcache_perthread_struct;
 
static __thread tcache_perthread_struct *tcache = NULL;

/注：tcache_entry结构体中的*key直到glibc-2.29才出现，此前的版本均没有这一项。
    

+------------------+
|   Thread 1       |
|   +------------+ |
|   |  tcache    | |
|   | +--------+ | |
|   | | bin[0] | | |
|   | +--------+ | |
|   | | bin[1] | | |
|   | +--------+ | |
|   | | bin[2] | | |
|   | +--------+ | |
|   | |  ...   | | |
|   | +--------+ | |
|   | | bin[N] | | |
|   +------------+ |
+------------------+

+------------------+
|   Thread 2       |
|   +------------+ |
|   |  tcache    | |
|   | +--------+ | |
|   | | bin[0] | | |
|   | +--------+ | |
|   | | bin[1] | | |
|   | +--------+ | |
|   | | bin[2] | | |
|   | +--------+ | |
|   | |  ...   | | |
|   | +--------+ | |
|   | | bin[N] | | |
|   +------------+ |
+------------------+
    
tcache_bins[0] -> +--------+     +--------+     +--------+
                  | Block  | --> | Block  | --> | Block  |
                  +--------+     +--------+     +--------+
                  
tcache_bins[1] -> +--------+     +--------+     +--------+
                  | Block  | --> | Block  | --> | Block  |
                  +--------+     +--------+     +--------+

tcache_bins[2] -> +--------+     +--------+     +--------+
                  | Block  | --> | Block  | --> | Block  |
                  +--------+     +--------+     +--------+


tcache分配内存

  • 假如请求分配大小为32字节的内存块
    • 先检查tcache_bins[0]是否有可用的块，如果找不到合适的块，则接下去找tcache_bins[1]链表里面的块
    • 如果tcache_bins[0]中有可使用的块，那么就从中取出一个块，并移除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
请求分配大小为 32 字节的内存块：
    |
    v
检查 tcache_bins[0] 是否有可用块：
    |
    v
+--------+     +--------+     +--------+
| Block  | --> | Block  | --> | Block  |
+--------+     +--------+     +--------+
    |
    v
找到可用块，分配并移除：
    |
    v
+--------+     +--------+
| Block  | --> | Block  |
+--------+     +--------+

释放块到tcache

  • 假如释放一个32字节的内存块
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
释放大小为 32 字节的内存块：
    |
    v
将块放入 tcache_bins[0]：
    |
    v
+--------+     +--------+     +--------+
| Block  | --> | Block  | --> | Block  |
+--------+     +--------+     +--------+
    |
    v
检查 tcache_bins[0] 是否已满：
    |
    v
如果未满，则操作结束。
如果已满，将块放入全局链表。

源码分析

  • 操作tcache结构体的函数主要是一下两个
  • 前者向Bins中放入chunk，后者则从中取出chunk。且每个Tcache Bin最多存放7个chunk
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
/* This is another arbitrary limit, which tunables can change.  Each
   tcache bin will hold at most this number of chunks.  */
# define TCACHE_FILL_COUNT 7
 
static __always_inline void
tcache_put (mchunkptr chunk, size_t tc_idx)
{
   tcache_entry *e = (tcache_entry *) chunk2mem (chunk);
   assert (tc_idx < TCACHE_MAX_BINS);
 
   /* Mark this chunk as "in the tcache" so the test in _int_free will
      detect a double free.  */
   e->key = tcache;
 
   e->next = tcache->entries[tc_idx];
   tcache->entries[tc_idx] = e;
   ++(tcache->counts[tc_idx]);
 }
------------------------------------------------------------------------ 
/* Caller must ensure that we know tc_idx is valid and there's
   available chunks to remove.  */
static __always_inline void *
tcache_get (size_t tc_idx)
{
  tcache_entry *e = tcache->entries[tc_idx];
  assert (tc_idx < TCACHE_MAX_BINS);
  assert (tcache->entries[tc_idx] > 0);
  tcache->entries[tc_idx] = e->next;
  --(tcache->counts[tc_idx]);
  return (void *) e;
}
  • 当有tcache时的内存分配
1
2
3
4
5
6
7
8
9
10
11
内存申请：
在内存分配的 malloc 函数中有多处，会将内存块移入 tcache 中

1. 首先，申请的内存块符合 fastbin 大小时并且在 fastbin 内找到可用的空闲块时，会把该 fastbin 链上的其他内存块放入 tcache 中
2. 其次，申请的内存块符合 smallbin 大小时并且在 smallbin 内找到可用的空闲块时，会把该 smallbin 链上的其他内存块放入 tcache 中
3. 当在 unsorted bin 链上循环处理时，当找到大小合适的链时，并不直接返回，而是先放到 tcache 中，继续处理
    
    
tcache 取出：在内存申请的开始部分，首先会判断申请大小块，并验证 tcache 是否存在，如果存在就直接从 tcache 中摘取，否则再使用_int_malloc 分配

在循环处理 unsorted bin 内存块时，如果达到放入 unsorted bin 块最大数量，会立即返回。不过默认是 0，即不存在上限

边界标记法

gdb关于堆的动调

相关指令

1
2
3
4
5
6
7
8
9
10
11
12
13
14
查看堆块信息
vmmap   	 显示进程的虚拟内存布局，包括堆、栈、代码段等
heap	 	 打印堆的相关信息，包括arena、chunk等
heap chunks  显示堆中所有chunk的信息，包括大小、状态（分配/未分配等）
heap bins	 显示不同类型的bins(fast bins 、samll bins、large bins等)的内容
heap fastbins 显示fast bins的内容
tcachebins 显示tcache bins的内容
heap unsorted   显示unsorted bin的内容
heap smallbins  显示small bins的内容
heap largebins  显示large bins的内容
heap -v			查看详细的堆块信息
查看特定的堆块
heap chunk <address>

堆glibc环境

  • 在了解堆进行实验或者示例程序的时候，本地ubuntu环境由于glibc版本和gcc版本的不同，导致有些示例程序运行不了。
  • 这就需要搭建编译环境，试过很多办法，但是还是使用Docker容器比较方便。

glibc2.23环境

  • 在Docker Hub上可以找到Ubuntu16.04版本的镜像，该版本的Ubuntu镜像通常会自带glibc2.23版本。
  • 所以直接在Docker容器中做实验，如何下载Docker这边不做介绍具体看Docker概述与安装 | iyheart的博客
1
docker pull ubuntu:16.04

image-20240718134555687

  • 然后再启动容器
1
docker run -it --name glibc2.23 ubuntu:16.04

image-20240718135313841

  • 启动容器后就会自动进入所启动的容器内部，退出指令exit
  • 如果要重新进入容器，需要先启动容器，然后再进入容器
1
2
docker start <container_id_or_name>
docker exec -it <container_id_or_name> bash

image-20240718135804128

  • 然后更新包管理器
1
2
apt-get update
apt-get upgrade
  • 然后再安装gcc编译器
1
apt-get install gcc
  • 下载好后使用gcc -v，查看gcc编译器的命令，glibc2.23兼容gcc版本一般是gcc 5的版本，ubuntu16.04在安装gcc的时候，会默认安装gcc 5的版本

image-20240718140348033

  • 剩下的vim编辑器和gdb还有一些比较好用的终端，看着安装即可

glibc2.27环境

  • glibc2.27，是ubuntu18.04版本自带的，可以用Docker拉取Ubuntu18.04镜像

glib2.31环境

  • glibc2.31，是ubuntu20.04版本自带的，可以用Docker拉取Ubuntu20.04镜像

glibc2.33环境

  • glibc2.33，是ubuntu21.04版本自带的，可以用Docker拉取Ubuntu21.04镜像

glibc2.34环境

  • glibc2.34，是ubuntu21.10版本自带的，可以用Docker拉取Ubuntu21.10镜像

glibc2.35环境

  • glibc2.35，是ubuntu22.04版本自带的，可以用Docker拉取Ubuntu22.04镜像

glibc2.39环境

  • 目前没有镜像自带glibc2.39，目前还不知道怎么搞这个环境