说明：CTF的pwn题很多与malloc（）与free（）有关
这关系到系统堆管理策略的实现
这一节主要讨论主流的堆管理策略glibc在系统中的结构和一些基本概念
本文主要是一篇国外写的挺好的介绍堆的博客的翻译+读书笔记，建议可以读一读
原文地址：https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/
以后会深入学习堆管理策略的实现和堆机制漏洞攻击的方法
最后推荐一个在线画结构图、流程图、思维导图的网站：https://www.processon.com
历史沿革
常常用到的堆管理策略主要有以下几种
- dlmalloc – General purpose allocator
- ptmalloc2 – glibc
- jemalloc – FreeBSD and Firefox
- tcmalloc – Google
- libumem – Solaris
ptmalloc2最初由dlmalloc修改而来，后来ptmalloc2加入了多线程机制的支持，从此与dlmalloc渐渐区分开来，现在是linux的默认内存管理策略。
dlmalloc为多个线程维护一个堆，多个线程调用malloc时只能依次执行。ptmalloc为每个线程分配一个arena，在各个线程专属的arena中进行堆管理，因此可以同时处理多个线程的malloc调用，该机制称为Per Thread Arena
实现细节
调用的系统函数
- brk：改变程序退出的节点地址所在，一般情况下，程序退出节点位于数据段末尾后内存，但是堆管理过程需要在数据段后附加新数据（堆），因此调用系统函数brk（）增加内存空间
- mmap：与brk直接粗暴的改变程序退出节点不同，mmap用来添加新的映射到其余的内存地址中，堆管理在映射到的内存地址中进行
malloc（）
- 调用malloc后，会根据情况调用brk和mmap两个系统函数创建堆
- brk：当主线程调用malloc（），且请求的内存大小较小时（<128KB），使用brk分配堆
直接在数据段之后请求一段内存负责堆管理，返回的内存比请求的内存更大，以用于后续的需求 - mmap：当普通线程调用malloc（）时，调用mmap()系统函数将线程的arena分配到映射的内存空间中
- 堆会维护一个freelist（glibc里面称为bin）来对堆中未被使用的内存地址进行记录，如果在同一个arena中请求堆，先检查bin中是否有free的堆地址，如果堆不够用时，才会向内核请求增加arena的内存大小
free（）
调用free（）函数并不会将malloc（）分配的内存释放掉，仅仅是将free的内存地址加入bin，在下一次malloc的时候可以使用
堆结构
堆结构分为三层：arena、heap、chunk
这里绘制了一副图表明堆，类似的这样的图网上还有很多
arena
- arena的个数有上限，通常为CPU核心的个数2（32位系统）8（64位系统），如果超过了这一上限，则内核可能将多个线程的堆映射到一个arena
- 一个arena可以维护多个堆，但是只维护一个malloc_state（即Arena Header）
只有一个堆的内存地址
当当前堆内存地址空间不足时，调用mmap（）在内存空间中映射一个新的堆出来，映射出来后的结果如下
heap
- 如果一个arena维护了多个堆，每个堆需要维护一个heap_info（即Heap Header）。但main arena是例外，因为他不需要调用mmap，只需要往后增加内存大小就可以，他只用维护一个堆就好
- main heap
chunk
chunk是堆中分出的数据块，每个chunk是一个连续的内存地址，用来存放比如数组等程序运行时的数据
chunk分为四种类型
- Allocated chunk
- Free chunk
- Top chunk
- Last Remainder chunk
1. allocated chunk
被分配了的在使用中的chunk
image.png
- prev chunk：记录上一个chunk的大小，将chunk想象成一个单链表，prev chunk就是chunk上的上一个数据单元，不同的chunk间是不连续的
- chunk size：记录当前chunk的大小，其中，包含三比特的符号位
- N：置0表示该chunk属于main arena
- P：置1表示prev chunk在使用中（没有被free掉）
- M：置1表示该chunk是调用mmap而产生的（即被映射到了其他的内存空间中）
2. free chunk
记录在bin中未被使用的chunk。两个chunk不能是地址连续的，否则会被合并掉
除了allocated chunk中记录的数据外，free chunk还记录了一些指针指向bin中记录的上一个/下一个free chunk的地址
bin
bin即freelist，维护一个记录freechunk地址的列表，根据free chunk的大小不同分为4种chunk
- Fast bin
- Small bin
- Large bin
- Unsorted bin（还没有排序过大小的chunk，排序后分为上述三类）
- bins数组用于记录Small bin、Large bin、Unsorted bin。fastbinsY记录fast bin，共包含10个bin。bins数组包含共126个bin，第1个bin记录unsorted chunks，Bin 2-63是Small bin，Bin 64-126是Large bin
- fast bins：
- 单链表FILO（first in last out），每个freechunk维护一个fd指针指向bin中记录的下一个fast chunk的地址
- 每个bins记录的chunk大小一致，第0个bin记录8字节的chunk，第一个记录16字节，第二个记录24字节，此后递增
-
fast chunks可以是内存地址上连续的，这是chunk中的一个例外
- unsorted bins：
- 当small 和large chunk被free后，chunk会被加入到unsorted bins
- 双链表，在调用malloc（）时会首先检查是否有unsorted chunk，然后根据size决定将他分类或者合并
- small bins：
- 双链表FIFO（first in first out）
- 与fast bins类似，以8个字节为单位分类bin。smallchunk的尺寸大小为120~512字节
- free时，先检查前/后一个chunk是否是free的，如果是，则合并，之后加入到unsorted中
- large bins：
- 类似于一个网状的链表，有多个指针，除了指向list中的下/上一个指针，还会指向按照size排序比他大/小一点的其他chunk
- 不同的bin维护不同size范围的large chunk，但是同一个bin中记录的chunk size不一定相等
- 调用malloc时，找到size相等或者最相近的那个large chunk，再将其分为两部分，一部分叫做：used chunk，另外一部分叫做remaining chunk，归入unsorted bin重新分配
- 调用free过程与small chunk类似
3. Top Chunk
堆中最高地址处的chunk，不属于任何bin，当最大的chunk都不能满足用户的需求时，调用此处chunk，如果还不够，则调用系统函数增加top chunk
4. Last Remainder Chunk
unsorted bin中存放的最后一个没有被使用的chunk
网友评论