Mi1k7ea

堆基础

阅读量

网上太多关于这方面的文章了,这里不再重新造轮子了,直接引用ctf wiki以及其他的一些文章的说明,自己再添点东西就好。

0x01 何为堆

在程序运行过程中,堆可以提供动态分配的内存,允许程序申请大小未知的内存。堆其实就是程序虚拟地址空间的一块连续的线性区域,它由低地址向高地址方向增长。我们一般称管理堆的那部分程序为堆管理器。

堆管理器处于用户程序与内核中间,主要做以下工作

  1. 响应用户的申请内存请求,向操作系统申请内存,然后将其返回给用户程序。同时,为了保持内存管理的高效性,内核一般都会预先分配很大的一块连续的内存,然后让堆管理器通过某种算法管理这块内存。只有当出现了堆空间不足的情况,堆管理器才会再次与操作系统进行交互。
  2. 管理用户所释放的内存。一般来说,用户释放的内存并不是直接返还给操作系统的,而是由堆管理器进行管理。这些释放的内存可以来响应用户新申请的内存的请求。

Linux 中早期的堆分配与回收由 Doug Lea 实现,但它在并行处理多个线程时,会共享进程的堆内存空间。因此,为了安全性,一个线程使用堆时,会进行加锁。然而,与此同时,加锁会导致其它线程无法使用堆,降低了内存分配和回收的高效性。同时,如果在多线程使用时,没能正确控制,也可能影响内存分配和回收的正确性。Wolfram Gloger 在 Doug Lea 的基础上进行改进使其可以支持多线程,这个堆分配器就是 ptmalloc 。在 glibc-2.3.x. 之后,glibc 中集成了 ptmalloc2。

目前 Linux 标准发行版中使用的堆分配器是 glibc 中的堆分配器:ptmalloc2。ptmalloc2 主要是通过 malloc/free 函数来分配和释放内存块。

需要注意的是,在内存分配与使用的过程中,Linux 有这样的一个基本内存管理思想,只有当真正访问一个地址的时候,系统才会建立虚拟页面与物理页面的映射关系。 所以虽然操作系统已经给程序分配了很大的一块内存,但是这块内存其实只是虚拟内存。只有当用户使用到相应的内存时,系统才会真正分配物理页面给用户使用。

0x02 堆的基本操作

这里主要说下基本的堆操作(包括堆的分配,回收,堆分配背后的系统调用)以及堆目前的多线程支持等。

malloc

1
malloc(size_t n)

malloc 函数返回对应大小字节的内存块的指针。此外,该函数还对一些异常情况进行了处理

  • 当 n=0 时,返回当前系统允许的堆的最小内存块。
  • 当 n 为负数时,由于在大多数系统上,size_t 是无符号数(这一点非常重要),所以程序就会申请很大的内存空间,但通常来说都会失败,因为系统没有那么多的内存可以分配。

free

1
free(void* p)

free 函数会释放由 p 所指向的内存块。这个内存块有可能是通过 malloc 函数得到的,也有可能是通过相关的函数 realloc 得到的。

此外,该函数也同样对异常情况进行了处理

  • 当 p 为空指针时,函数不执行任何操作。
  • 当 p 已经被释放之后,再次释放会出现乱七八糟的效果,这其实就是 double free
  • 除了被禁用 (mallopt) 的情况下,当释放很大的内存空间时,程序会将这些内存空间还给系统,以便于减小程序所使用的内存空间。

内存分配背后的系统调用

在前面提到的函数中,无论是 malloc 函数还是 free 函数,我们动态申请和释放内存时,都经常会使用,但是它们并不是真正与系统交互的函数。这些函数背后的系统调用主要是 (s)brk 函数以及 mmap, munmap 函数。

如下图所示,我们主要考虑对堆进行申请内存块的操作。

(s)brk

对于堆的操作,操作系统提供了 brk 函数,glibc 库提供了 sbrk 函数,我们可以通过增加 brk 的大小来向操作系统申请内存。初始时,堆的起始地址 start_brk 以及堆的当前末尾 brk 指向同一地址。根据是否开启 ASLR,两者的具体位置会有所不同

  • 不开启 ASLR 保护时,start_brk 以及 brk 会指向 data/bss 段的结尾。
  • 开启 ASLR 保护时,start_brk 以及 brk 也会指向同一位置,只是这个位置是在 data/bss 段结尾后的随机偏移处。

具体效果如下图(这个图片与网上流传的基本一致,这里是因为要画一张大图,所以自己单独画了下)所示

示例:

在每一次执行完操作后,都执行了 getchar() 函数,这是为了方便查看程序真正的映射。

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
/* sbrk and brk example */
#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>

int main()
{
void *curr_brk, *tmp_brk = NULL;

printf("Welcome to sbrk example:%d\n", getpid());

/* sbrk(0) gives current program break location */
tmp_brk = curr_brk = sbrk(0);
printf("Program Break Location1:%p\n", curr_brk);
getchar();

/* brk(addr) increments/decrements program break location */
brk(curr_brk+4096);

curr_brk = sbrk(0);
printf("Program break Location2:%p\n", curr_brk);
getchar();

brk(tmp_brk);

curr_brk = sbrk(0);
printf("Program Break Location3:%p\n", curr_brk);
getchar();

return 0;
}

在第一次调用brk()之前

可以看出,并没有出现堆。此时:

start_brk = end_data = brk = 0x0x230d000

第一次调用brk()——增加内存

已经出现了堆段。

1
brk(curr_brk+4096);

通过增加brk的大小来向OS申请内存,较之前申请了0x1000即4096字节的内存空间。此时:

start_brk = end_data = 0x0230d000

brk = 0x0230e000

其中,关于堆的那一行

  • 0x0230d000是相应堆的起始地址
  • rw-p表明堆具有可读可写权限,并且属于隐私数据
  • 00000000 表明文件偏移,由于这部分内容并不是从文件中映射得到的,所以为0
  • 00:00是主从 (Major/mirror) 的设备号,这部分内容也不是从文件中映射得到的,所以也都为0
  • 0表示着Inode 号。由于这部分内容并不是从文件中映射得到的,所以为0

第二次调用brk()——减少内存

1
brk(tmp_brk);

通过减少brk的大小,使堆的内存空间减至初始的大小。此时:

start_brk = end_data = brk = 0x0x230d000

恢复为了之前的状态,没有heap段。

mmap

malloc 会使用 mmap 来创建独立的匿名映射段。匿名映射的目的主要是可以申请以 0 填充的内存,并且这块内存仅被调用进程所使用。

示例:

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
/* Private anonymous mapping example using mmap syscall */
#include <stdio.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdlib.h>

void static inline errExit(const char* msg)
{
printf("%s failed. Exiting the process\n", msg);
exit(-1);
}

int main()
{
int ret = -1;
printf("Welcome to private anonymous mapping example::PID:%d\n", getpid());
printf("Before mmap\n");
getchar();
char* addr = NULL;
addr = mmap(NULL, (size_t)132*1024, PROT_READ|PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
if (addr == MAP_FAILED)
errExit("mmap");
printf("After mmap\n");
getchar();

/* Unmap mapped region. */
ret = munmap(addr, (size_t)132*1024);
if(ret == -1)
errExit("munmap");
printf("After munmap\n");
getchar();
return 0;
}

在执行 mmap 之前

可以从下面的输出看到,目前只有. so文件的mmap段:

mmap 后

从下面的输出可以看出,我们申请的内存与已经存在的内存段结合在了一起构成了7f2a92624000到7f2a92645000的mmap段:

munmap

从下面的输出,我们可以看到我们原来申请的内存段已经没有了,内存段又恢复了原来的样子了:

多线程支持

在原来的 dlmalloc 实现中,当两个线程同时要申请内存时,只有一个线程可以进入临界区申请内存,而另外一个线程则必须等待直到临界区中不再有线程。这是因为所有的线程共享一个堆。在 glibc 的 ptmalloc 实现中,比较好的一点就是支持了多线程的快速访问。在新的实现中,所有的线程共享多个堆。

示例:

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
/* 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;
}

注意在gcc编译时加上-lpthread参数,否则会编译出错,因为pthread不是Linux下的默认的库,也就是在链接的时候,无法找到phread库中函数的入口地址,于是链接会失败。

第一次申请之前

没有heap段。

第一次申请后

heap段被建立了,并且它就紧邻着数据段,这说明malloc的背后是用brk()函数来实现的。同时需要注意的是,我们虽然只是申请了 1000 个字节,但是我们却得到了|0x01291000-0x012b2000|=0x21000 个字节的堆。这说明虽然程序可能只是向操作系统申请很小的内存,但是为了方便,操作系统会把很大的内存分配给程序。这样的话,就避免了多次内核态与用户态的切换,提高了程序的效率。我们称这一块连续的内存区域为arena。此外,我们称由主线程申请的内存为main_arena。后续的申请的内存会一直从这个arena 中获取,直到空间不足。当arena空间不足时,它可以通过增加brk的方式来增加堆的空间。类似地,arena也可以通过减小brk来缩小自己的空间。

在主线程释放内存后

对应的arena并没有进行回收,而是交由glibc来进行管理。当后面程序再次申请内存时,在glibc中管理的内存充足的情况下,glibc就会根据堆分配的算法来给程序分配相应的内存。

在第一个线程 malloc 之前

可以看到并没有出现与线程1相关的堆,但是出现了与线程1相关的栈。

第一个线程 malloc 后

可以看出线程1的堆段被建立了,而且它所在的位置为内存映射段区域,同样大小也是132KB(7fd1a0000000-7fd1a0021000)。因此这表明该线程申请的堆时,背后对应的函数为mmap函数。同时可以看出实际真的分配给程序的内存为64M(7fd1a0000000-7fd1a4000000),而且只有132KB的部分具有可读可写权限,这一块连续的区域成为thread arena。

注意:

当用户请求的内存大于 128KB 时,并且没有任何 arena 有足够的空间时,那么系统就会执行 mmap 函数来分配相应的内存空间。这与这个请求来自于主线程还是从线程无关。

在第一个线程释放内存后

可以看到,这样释放内存同样不会把内存重新给系统。

0x03 堆相关数据结构

与堆相关的数据结构主要分为

  • 宏观结构,包含堆的宏观信息,可以通过这些数据结构索引堆的基本信息。
  • 微观结构,用于具体处理堆的分配与回收中的内存块。

微观结构

malloc_chunk

概述

在程序的执行过程中,称由malloc()申请的内存为chunk。这块内存在ptmalloc内部用malloc_chunk结构体来表示。当程序申请的 chunk 被 free 后,会被加入到相应的空闲管理列表中。

无论一个chunk的大小如何,处于分配状态还是释放状态,它们都使用一个统一的结构。虽然它们使用了同一个数据结构,但根据是否被释放,它们的表现形式会有所不同。

malloc_chunk的结构如下:

1
2
3
4
5
6
7
8
9
10
11
12
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;
};

首先,这里给出一些必要的解释 INTERNAL_SIZE_T,SIZE_SZ,MALLOC_ALIGN_MASK:

1
2
3
4
5
/* The corresponding word size.  */
#define SIZE_SZ (sizeof (INTERNAL_SIZE_T))

/* The corresponding bit mask value. */
#define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1)

一般来说,size_t 在 64 位中是 64 位无符号整数,32 位中是 32 位无符号整数。

每个字段的具体的解释如下:

  • prev_size, 如果该 chunk 的物理相邻的前一地址 chunk(两个指针的地址差值为前一 chunk 大小)是空闲的话,那该字段记录的是前一个 chunk 的大小 (包括 chunk 头)。否则,该字段可以用来存储物理相邻的前一个 chunk 的数据。这里的前一 chunk 指的是较低地址的 chunk
  • size,该 chunk 的大小,大小必须是 2 SIZE_SZ 的整数倍。如果申请的内存大小不是 2 SIZE_SZ 的整数倍,会被转换满足大小的最小的 2 * SIZE_SZ 的倍数。32 位系统中,SIZE_SZ 是 4;64 位系统中,SIZE_SZ 是 8。 该字段的低三个比特位对 chunk 的大小没有影响,它们从高到低分别表示
    • NON_MAIN_ARENA,记录当前 chunk 是否不属于主线程,1 表示不属于,0 表示属于。
    • IS_MAPPED,记录当前 chunk 是否是由 mmap 分配的。
    • PREV_INUSE,记录前一个 chunk 块是否被分配。一般来说,堆中第一个被分配的内存块的 size 字段的 P 位都会被设置为 1,以便于防止访问前面的非法内存。当一个 chunk 的 size 的 P 位为 0 时,我们能通过 prev_size 字段来获取上一个 chunk 的大小以及地址。这也方便进行空闲 chunk 之间的合并。
  • fd,bk。 chunk 处于分配状态时,从 fd 字段开始是用户的数据。chunk 空闲时,会被添加到对应的空闲管理链表中,其字段的含义如下
    • fd 指向下一个(非物理相邻)空闲的 chunk
    • bk 指向上一个(非物理相邻)空闲的 chunk
    • 通过 fd 和 bk 可以将空闲的 chunk 块加入到空闲的 chunk 块链表进行统一管理
  • fd_nextsize, bk_nextsize,也是只有 chunk 空闲的时候才使用,不过其用于较大的 chunk(large chunk)。
    • fd_nextsize 指向前一个与当前 chunk 大小不同的第一个空闲块,不包含 bin 的头指针。
    • bk_nextsize 指向后一个与当前 chunk 大小不同的第一个空闲块,不包含 bin 的头指针。
    • 一般空闲的 large chunk 在 fd 的遍历顺序中,按照由大到小的顺序排列。这样做可以避免在寻找合适 chunk 时挨个遍历。

一个已经分配的 chunk 的样子如下。我们称前两个字段称为 chunk header,后面的部分称为 user data。每次 malloc 申请得到的内存指针,其实指向 user data 的起始处。

当一个 chunk 处于使用状态时,它的下一个 chunk 的 prev_size 域无效,所以下一个 chunk 的该部分也可以被当前 chunk 使用。这就是 chunk 中的空间复用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of previous chunk, if unallocated (P clear) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of chunk, in bytes |A|M|P|
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| User data starts here... .
. .
. (malloc_usable_size() bytes) .
next . |
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| (size of chunk, but used for application data) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of next chunk, in bytes |A|0|1|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

被释放的 chunk 被记录在链表中(可能是循环双向链表,也可能是单向链表)。具体结构如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of previous chunk, if unallocated (P clear) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
`head:' | Size of chunk, in bytes |A|0|P|
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Forward pointer to next chunk in list |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Back pointer to previous chunk in list |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Unused space (may be 0 bytes long) .
. .
next . |
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
`foot:' | Size of chunk, in bytes |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of next chunk, in bytes |A|0|0|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

可以发现,如果一个 chunk 处于 free 状态,那么会有两个位置记录其相应的大小

  1. 本身的 size 字段会记录,
  2. 它后面的 chunk 会记录。

一般情况下,物理相邻的两个空闲 chunk 会被合并为一个 chunk 。堆管理器会通过 prev_size 字段以及 size 字段合并两个物理相邻的空闲 chunk 块。

!!!一些关于堆的约束,后面详细考虑!!!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
The three exceptions to all this are:
1. The special chunk `top' doesn't bother using the
trailing size field since there is no next contiguous chunk
that would have to index off it. After initialization, `top'
is forced to always exist. If it would become less than
MINSIZE bytes long, it is replenished.
2. Chunks allocated via mmap, which have the second-lowest-order
bit M (IS_MMAPPED) set in their size fields. Because they are
allocated one-by-one, each must contain its own trailing size
field. If the M bit is set, the other bits are ignored
(because mmapped chunks are neither in an arena, nor adjacent
to a freed chunk). The M bit is also used for chunks which
originally came from a dumped heap via malloc_set_state in
hooks.c.
3. Chunks in fastbins are treated as allocated chunks from the
point of view of the chunk allocator. They are consolidated
with their neighbors only in bulk, in malloc_consolidate.
*/

0x04 参考

堆概述

堆相关数据结构


Copyright © Mi1k7ea | 本站总访问量