堆基础
堆基础
相关数据结构(libc-2.23中)
强烈推荐《Glibc内存管理-ptmalloc2源代码分析》
malloc_chunk
1 | /* |
这张图是一个简单的模型
-
prev_size:如果之前的chunk被free掉,那么改为有效,且为上一个chunk的size值
-
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,**prev_inuse:
**- **1.在没有被free时:
** Prev_inuse=1,表示上一个chunk没有被free掉
- 2 .被free时:
Prev_inuse=0,表示上一个chunk被free掉,在有些bin中,free(这个chunk)时,就会通过prev_size的大小实现chunk的合并 -
fd,bk
chunk 处于分配状态时,从 fd 字段开始是用户的数据。chunk 空闲时,会被添加到对应的空闲管理链表中,其字段的含义如下
- fd 指向下一个(非物理相邻)空闲的 chunk
- bk 指向上一个(非物理相邻)空闲的 chunk和fd一起构成双链表结构,这其中就涉及了例如从双链表中拆离出chunk的Unlink函数
- 通过 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 的 prev_size 域无效,所以下一个 chunk 的该部分也可以被当前chunk使用。这就是chunk中的空间复用。
各种各样的bin
这里就引用《Glibc内存管理-ptmalloc2源代码分析》的话和图
用户 free 掉的内存并不是都会马上归还给系统,ptmalloc 会统一管理 heap 和 mmap 映射区域中的空闲的 chunk,当用户进行下一次分配请求时,ptmalloc 会首先试图在空闲的 chunk 中挑选一块给用户,这样就避免了频繁的系统调用,降低了内存分配的开销。ptmalloc将相似大小的 chunk 用双向链表链接起来,这样的一个链表被称为一个 bin。Ptmalloc 一共维护了 128 个 bin,并使用一个数组来存储这些 bin(如下图所示)。
fastbin
保存 0x20~0x80 大小的 chunk,如果被释放的chunk->size满足这个要求就会首先放入到这个bin中,且不修改下一个chunk->prev_size,fastbin使用单链表进行存储,存取顺序为LIFO(先进后出)
1 | chunk_1 <--- chunk_2 <--- chunk_3 |
1 |
|
small bin
同一个 small bin 中的 chunk 具有相同的大小。两个相邻的 small bin 中的 chunk 大小相差 8bytes。small bins 中的 chunk 按照最近使用顺序进行排列,最后释放的 chunk 被链接到链表的头部,而申请 chunk 是从链表尾部开始,这样,每一个 chunk 都有相同的机会被 ptmalloc 选中。
unsorted bin
数组中的第一个为 unsorted bin,无法分进其他bin的chunk就会分配到这里, unsortedbin会不断增大,始终只有一块
fastbin
在libc-2.27中,tcache分配完,直接进unsorted bin,每一代glibc的分配方式都不大相同
当空闲的 chunk 被链接到 bin 中的时候,ptmalloc 会把表示该 chunk 是否处于使用中的标志 P 设为 0(注意,这个标志实际上处在下一个 chunk 中),同时 ptmalloc 还会检查它前后的 chunk 是否也是空闲的,如果是的话,ptmalloc 会首先把它们合并为一个大的 chunk,然后将合并后的 chunk 放到 unstored bin 中。要注意的是,并不是所有的 chunk 被释放后就立即被放到 bin 中。ptmalloc 为了 高分配的速度,会把一些小的的 chunk 先放到一个叫做 fast bins 的容器内。
故而,ptmalloc 中在分配过程中引入了 fast bins,不大于 max_fast (默认值为 64B)的 chunk 被释放后,首先会被放到 fast bins 中,fast bins 中的 chunk 并不改变它的使用标志 P。这样也就无法将它们合并,当需要给用户分配的 chunk 小于或等于 max_fast 时,ptmalloc 首先会在 fast bins 中查找相应的空闲块,然后才会去查找 bins 中的空闲 chunk。在某个特定的时候,ptmalloc 会遍历 fast bins 中的 chunk,
在pwndbg中长这样
1 |
|
相同大小的空闲chunk组成单链表
Topchunk
在gbd中,我们经常看见这样的chunk
1 |
|
在malloc前
malloc过后
发现除了我们的chunk外,多了一个chunk,而且size特别大
这个 chunk 不属于任何一个 bin,它的作用在于当所有的bin 都无法满足用户请求的大小时,如果其大小不小于指定的大小,就进行分配,并将剩下的部分作为新的 top chunk。否则,就对heap进行扩展后再进行分配。在main arena中通过sbrk扩展heap,而在thread arena中通过mmap分配新的heap。
需要注意的是,top chunk 的 prev_inuse 比特位始终为1,否则其前面的chunk就会被合并到top chunk中。
Last_remainder mmaped_chunk
这两个个篇幅较多,直接看书就好了
堆分配和释放的实现
首先假如我们在4G内存大小的空间运行着一个32位的系统,那么内存中的分配空间如下
64位的内存分布大致如下
堆分配-malloc
sbrk与mmap
这两者时实现堆分配的较低层原理
brk、sbrk
对应的有两个 Linux C中的sbrk()和一个API,一般指ptmalloc中的 sbrk和brk
1 | /* Set the end of accessible data space (aka "the break") to ADDR. |
- brk中
- *addr是数据段的结束地址,通过改变该地址来改变数据段的 大小,当结束地址向高地址移动,进程内存空间增大,当结束地址向低地址移动, 进程内存空间减小。
- brk() 调用成功时返回 0,失败时返回 -1。
- sbrk中
- delta 表示增量,即增加或减少的空间大小,调用成功时返回增加后减小前数据段的结束地址,失败时返回 -1。
《CTF All in One》中有这样讲
1 |
|
关闭ASLR
echo 0 > /proc/sys/kernel/randomize_va_space
开两个窗口同时调一下:
cat /proc/<PID>/maps
- 1. 初始化
1 | void *curr_brk, *tmp_brk, *pre_brk; |
- 2. 使用brk分配
1 | brk(curr_brk+4096); |
- **3.**使用sbrk分配
1 | pre_brk = sbrk(4096); |
- **4.**使用brk缩减heap
1 | brk(tmp_brk); |
mmap
原版定义
1 |
|
mmap()
函数要求内核创建一个从地址 addr 开始的 新虚拟内存区域,并将文件描述符 fildes 指定的对象的一个连续的片 (chunk)映射到这个新区域。连续的对象片大小为 len 字节,从距文件开始处 偏移量为 off 字节的地方开始。 prot 描述虚拟内存区域的访问权限 位, flags 描述被映射对象类型的位组成。
- addr:映射区开始地址,为0时表示开始位置有系统决定
- len:映射到调用进程地址空间的字节数
- prot:期望的内存保护标志,不能与文件的打开模式冲突
- PROT_EXEC //页内容可以被执行
- PROT_READ //页内容可以被读取
- PROT_WRITE //页可以被写入
- PROT_NONE //页不可访问
- flags:指定映射对象的类型,映射选项和映射页是否可以共享。它的值可以是一个或者多个以下位的组合体
- MAP_FIXED //使用指定的映射起始地址,如果由start和len参数指定的内存区重叠于现存的映射空间,重叠部分将会被丢弃。如果指定的起始地址不可用,操作将会失败。并且起始地址必须落在页的边界上。
- MAP_SHARED //与其它所有映射这个对象的进程共享映射空间。对共享区的写入,相当于输出到文件。直到msync()或者munmap()被调用,文件实际上不会被更新。
- MAP_PRIVATE //建立一个写入时拷贝的私有映射。内存区域的写入不会影响到原文件。这个标志和以上标志是互斥的,只能使用其中一个。
- MAP_ANON //表明进行的是匿名映射
- fildes:即将映射到进程空间的文件描述字
- off:参数一般设为0,表示从文件头开始映射。被映射对象内容的起点。
这里同样引用《CTF All in One》中的例子
同样的
关闭ASLR
echo 0 > /proc/sys/kernel/randomize_va_space
开两个窗口同时调一下:
cat /proc/<PID>/maps
源代码
1 |
|
- 1.初始化
1 | void *curr_brk; |
- 2.使用mmap创建映射段
1 | char *addr; |
- 3.使用munmap减小函数
1 | munmap(addr, (size_t)4096); |
图里面打掉一个字母…
但是最常用的还是``malloc
calloc
realloc
free`这些函数,我们再以libc-2.23为例,看看这几个函数是如何实现的
malloc
堆初始化
堆初始化是在用户第一次申请内存时执行 malloc_consolidate 再执行 malloc_init_state 实现的。这里不做过多讲解。可以参见 malloc_state 相关函数
1 | struct malloc_state |
创建堆
malloc_init_state
1 | //malloc/malloc.c line 1799 |
接着就是各种hook
1 | /* Forward declarations. */ |
以 malloc_hook_ini 为例
1 | void *weak_variable (*__malloc_hook) |
这个说明了malloc_hook只是一个弱引用,那么由此我们衍生出了将 malloc_hook 修改为 libc_system的攻击方法
1 | // malloc/hooks.c#L28 |
最后调用了libc中的malloc函数
(该部分参照了CTF-Wiki上的解释)
1 | // malloc/malloc.c#L2931 |
上面出现了这个函数 _int_malloc,接着看这个函数干了什么
_int_malloc的代码量很大,因为它时malloc函数功能的主要实现者
malloc/malloc.c#L3318
wiki上也是说的很详细了
https://wiki.x10sec.org/pwn/heap/heap_implementation_details/#_int_malloc
这里简单说下实现过程
- bin里面找合适的
- 所有bin均不满足时,考虑top_chunk
- top_chunk也不满足时,考虑重新进行内存申请
堆释放
free
由上面的我们大概知道过程,free的过程也是相似
也是 __free_hook -> __libc_free -> _int_free
__libc_free
1 | // malloc/malloc.c#L2933 |
_int_free
malloc/malloc.c#L3840
其中也是很了很多情况以及很多的检查
同样Wiki讲的很细了
https://wiki.x10sec.org/pwn/heap/heap_implementation_details/#_int_free
平时作题出错的话可以向里面看看是哪里的检查有问题