堆入门
堆入门
山林川泽堆
1.堆是由操作系统内核或者堆管理器动态分配的
2.只有在程序中需要时才会分配
3.在CTF的pwn程序中，栈是程序加载进内存后就会出现，而堆需要malloc,alloc,realoc函数分配内存后才会出现。
Windows和Linux下的堆分配，管理方式都不同，
堆在虚拟内存中的位置
128M
1 | *用户空间*（独立） |
堆的生长方向是从低地址向高地址生长的，而栈是从高地址向低地址生长的
生长方向不同的原因
- 内存利用效率：堆和栈的生长方向不同可以让空闲的内存最大程度地被使用。如果栈的生长方向也是向上增长，那么栈空间的起始位置就需要事先固定下来，这样在不同程序中，栈和堆的使用情况不同，可能会导致内存利用不均衡。例如，一个程序可能因为栈溢出而崩溃，但同时堆中还有大量未使用的空间
- 内存管理方式：栈是由编译器自动管理的，而堆则需要程序员手动管理。栈的空间大小在编译时就已确定，通常不会超过编译器为其分配的空间；而堆则是在运行时动态分配的，可以根据需要申请更多的内存空间
堆的基本结构
pre size（prev size） 和size 头统称为chunk头（chunk header）
每次malloc申请得到的内存指针，其实指向user data的起始处。
堆的大致图解如下：
1 | |-----------------| |
堆的结构
malloc_chunk的结构
每个程序分配的内存在内部被一个叫做“堆块”的所替代。一个堆块是由元数据和程序返回的内存组成的 （实际上内存是malloc返回值）。所有的这些堆块都是保存在堆上，这块内存区域在申请新的内存时会不断的扩大。同样，当一定数量的内存释放时，堆可以收缩。在glibc源码中定义的堆块如下：
1 | /* |
假设内存中没有堆块释放，新分配的内存区域紧随之前申请的堆块后。因此如果一个程序依次malloc（256），malloc（512），以及malloc(1024)，内存布局如下：
1 | Meta-data of chunk created by malloc(256) |
1.在堆块之间的“———”是虚拟的边界，实际当中他们是彼此相邻的
2.布局中包含一个“顶块元数据”（top chunk）。顶级块表示堆中可利用的内存，而且是唯一的可以大小可以生长的堆块。当申请新的内存时，顶块分为两个部分：第一个部分变成所申请的堆块，第二个部分变为新的顶块（因此顶块大小可以收缩）。如果顶块不能够满足申请的内存区域大小，程序就会要求操作系统扩大顶块（让堆继续生长）。被释放的chunk被记录在链表中（可能是循环双向链表，也可能是单向链表）。具体结构如下
1 | chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
一般情况下，物理相邻的两个空间chunk会被合并成一个chunk。堆管理器会通过prev_size字段合并两个物理相邻的空闲chunk块。
1.pre size 字段
pre size(prev size) 全程为previous size
· pre_size，如果该chunk的物理相邻的前一地址 chunk （两个指针的地址差值为前一chunk大小）是空闲的话，那该字段记录的是前一个chunk的大小（包括chunk头）。否则，该字段可以用来储存物理相邻的前一个chunk的数据。这里的前一chunk指的是较低地址的chunk。前面一个堆块在使用时并且pre_size为储存前面chunk的数据时，他的值始终为0
堆是由低地址向高地址生长
2.size字段
size，这个是用来指示当前堆块的大小的（头部（pre size+size）加上user data 的大小）。大小必须是 2 * SIZE_SZ的整数倍，如果申请的内存大小不是2乘SIZE_SZ的整数倍，会被转换为满足大小的最小的2乘SIZE_SZ的倍数。
32位系统中，SIZE_SZ是4；
64位系统中，SIZE_SZ是8.
该字段的低三个比特位对chunk的大小没有影响，字段的最后三位相当于三个flag，这三个的作用分别是：
1.A（NON_MAIN_ARENA）：为0表示该chunk属于主分配区（主线程），为1表示该chunk属于非主分配区（非主线程）
2.M（IS_MAPPED）:表示当前chunk是从哪个内存区域获得的虚拟内存，为1表示该chunk是从mmap映射区域分配的，否则是从heap区域分配的
3.P（PREV_INUSE）：记录前一个chunk块是否被分配。一般来说，堆中第一个被分配的内存块的size字段的P位都会设置为1，以便于防止访问前面的非法内存。当一个chunk的size的P位为0时，我们能通过prev_size 字段来获取上一个chunk的大小以及地址。这也方便进行空闲chunk之间的合并
0 1 2 3 4 5 6 7
| 0 | 0 | 1 |
|---|
NON_MAIN_ARENA IS_MAPPED PREV_INUSE
3.user data
用于存放用户数据
使用malloc函数分配到的内存的返回值指针是指向user data（用户数据区）
例如在64位系统中：
1 | malloc（8） |
申请到的堆块总大小为16+8+8+1=0x21（byte）
1.第一个16字节是系统分配的最小内存，也就是说如果想要申请的内存小于系统最小分配的内存的话，就会按照最小的内存分配。
·在64位系统中这个值是16个字节，在32位系统中是八个字节
·例如，如果代码中是malloc（0）的话，堆管理器也会分配最小内存空间给你
2.第二个8字节是pre size字段的大小（32位的为4字节）
3.第三个8字节为size 字段的大小（32位的4字节）
4.最后一个字节是 PREV_INUSE 的值，只有0或1两个值
[^1]: 整理一下：堆的基本结构包括 pre_size、size、user data
[^2]: size字段包括：头部（pre size +size）加上user data的大小
[^3]: malloc出最小大小为：系统最小分配内存 + pre_size字段 + prev_inuse
结构图
使用中（分配后）
1 | chunk start ---->+++++++++++++++++++++++++++++++++++ | previous size |size A|M|P | <=head |
空闲中（使用后）
1.空闲中的chunk不存在M状态，只有A| |P状态
2.user data头部被分配出两个成员，fd和bk
1 | chunk start ---->+++++++++++++++++++++++++++++++++++ | previous size |size A| |P | <=head |
· chunk处于分配状态时，从fd字段开始是用户的数据，chunk空闲时，会被添加到对应的空闲管理链表中，其字段的含义如下
fd 指向前一个（非物理相邻）空闲chunk的起始地址，32位占4字节，64位占八字节
bk 指向后一个（非物理相邻）空闲chunk的起始地址，32位4字节，64位8字节
通过fd和bk可以将空闲的chunk块加入到空闲的chunk块链表进行统一管理
[^注意]: 事实上，释放后的large block 中还存在另外两个成员：fd_nextsize和bk_nextsize,上图并未画出，其简介如下
fd_nextsize , bk_nextsize , 是只有chunk空闲的时候才使用 ，不过其用于较大的chunk（large chunk）
fd_nextsize 指向前一个与当前chunk大小不同的第一个空闲块，不包含bin的头指针。
bk_nextsize 指向后一个与当前chunk大小不同的第一个空闲块，不包含bin的头指针。
[^注意]: 一般空闲的large chunk按照由大到小的顺序排列，在fd的遍历时，可以避免在寻找合适chunk时对所有chunk进行遍历
堆块大小
32位操作系统：
用户分配到的最小堆块大小为17B：prev_size(4B) + size(4B) + fd(4B) + bk(4B) + next_chunk –>p(1B)
若用户申请到的大小超过最小堆块大小，会与16B进行对齐
空间复用
当一个chunk处于使用状态时，它的下一个chunk的prev_size无效。所以下一个chunk的prev_size也可以被当前chunk使用，
这就是chunk的空间复用
IDA中常见的指针表示形式
在IDA的伪代码中的指针形式如下
1 | *(qword_6020A8+8) |
表示取到qword_6020A8这个地址加8偏移的那个地址储存的值
汇编代码等同于
1 | mov rax,cs:qword_6020A8 |
简单转化一下就是
1 | *(addr) = [addr] |
链表
在pwn的题目中经常会有一些笔记管理系统的题目
代码提供了最基本的增删查改的功能。这个“笔记”的数据结构通常就是使用链表连接起来的，记录当前note的大小、属性、内容等等。
例如
1 | *(qword_6020A8 + 24LL *i +16) = 1LL;// ==1 |
(qword_6020A8+16)就代表从qword_6020A8这个地址处再往后偏移16个字节，取到这个地址存储的值，接着吧1赋值给这个地方（也就是把1存入这个地址）同样的*(qword_6020A8 + 24)就代表偏移24个字节处的值为len依次类推就可以在不连续的内存空间中，把整个note的数据结构存储下来了
申请堆块的本质
堆管理器ptmalloc2主要是通过malloc/free函数来分配和释放内存块。
ptmalloc2的作用通俗的讲就是相当于一个“中间商”，在程序想要向系统申请堆空间时，这里的ptmalloc2就会申请一块很大的空间，并根据算法从这些内存中把空间真正的分配给程序。
例如
1 | 操作系统（内核）=========>运行库（堆管理器）=========>程序 |
例
1 |
|
在gdb处进行调试，在call malloc处下断点， 在这里使用vmmap命令，查看内存分布。可以看到此时并没有发现堆段
单步n，vmmap命令再次查看内存，发现出现了堆段
1 | gdb |
但是这里我们明明只是申请了10字节的大小，但是为什么这里给了那么大
的堆段呢？
计算一下刚好是132kb
一个地址可以容纳1byte的内容
这132kb的堆空间叫做arena，此时因为是主线程分配的，所以这个区域叫做main arena
也就是说这132kb是“厂家”（内核）批发给”中间商“（ptmalloc2)的货物，以便下次程序在向系统申请小内存的时候，直接去“中间商”去取就行了，他就会在这ptmalloc2就继续去找“厂家”（系统内核）去取货
查看已分配的堆内存分布
在上面我们动态调试的时候执行了malloc函数，申请到的堆指针是保存在eax中的
1 | RAX 0x5555555592a0 ◂— 0x0 //申请到的堆指针是保存在eax中的 |
我们这里使用下面这个命令来查看内存堆块情况：
x/32gx 0x5555555592a0-0x10 //32位的程序使用 x/32xw比较直观一点
这里减去0x10表示从堆块的头部开始观察（包含pre size 和 size字段）
main_arena与 top chunk
main_arena
这个main_arena其实就是ptmalloc2堆管理器通过与操作系统内核进行交互申请到的，也就是上面所说的“批发”到的一堆货物
因为是主线程分配的，所以叫main arena , 通过增加program break location的方法来增加 main arena 的大小。
top chunk
顾名思义，是堆中第一个堆块 相当于“带头大哥”，程序以后分配到的内存要放到他的后面
在系统当前的所以free chunk（无论那种bin) 都无法满足用户请求的内存的大小的时候，将此chunk当作一个应急消防员，分配给用户使用。
简单来说，也就是在程序在向堆管理器申请内存时，没有合适的内存空间可以分配给他，此时就会从 top chunk 上 “ 剪切 ” 一部分作为chunk分配给他
free函数和bins
free函数
free函数的使用是和bins的分配息息相关的。
例
1 | #include<stdio.h> |
gdb调试，执行到memcpy函数后单步运行
x /32gx 0x5555555592a0 - 0x10
1 | 0x555555559290: 0x0000000000000000 0x0000000000000021 |
继续运行 执行free
可以看到原本堆块中的内容已经被清空
原本堆空间中的内容已经被清空
1 | 0x555555559290: 0x0000000000000000 0x0000000000000021 |
执行x /2gx 0x5555555592a0
1 | 0x7ffff7e1ace0 <main_arena>: 0x0000000000000000 0x00005555555592a0 |
所以调用free函数之后做了两件事：
1.清空此堆块的user_data
2.将此堆块的指针存储到 main_arena 中了 （或是fast bin)
bin
bins 这个概念是与”内存回收“相关的，也就是堆管理器会根据用户已经申请到的内存空间大小进行释放，来决定放入哪类bins。 bins直接翻译过来就是”垃圾桶“的意思，
所以系统在决定使用哪个bins时可以看作“垃圾的分类”
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
暂未完成，后面的还没完全理解贯彻
