理解glibc的堆管理策略

说明：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

实现细节

调用的系统函数

1. brk：改变程序退出的节点地址所在，一般情况下，程序退出节点位于数据段末尾后内存，但是堆管理过程需要在数据段后附加新数据（堆），因此调用系统函数brk（）增加内存空间
2. mmap：与brk直接粗暴的改变程序退出节点不同，mmap用来添加新的映射到其余的内存地址中，堆管理在映射到的内存地址中进行

malloc（）

1. 调用malloc后，会根据情况调用brk和mmap两个系统函数创建堆

• brk：当主线程调用malloc（），且请求的内存大小较小时（<128KB），使用brk分配堆
  直接在数据段之后请求一段内存负责堆管理，返回的内存比请求的内存更大，以用于后续的需求
• mmap：当普通线程调用malloc（）时，调用mmap()系统函数将线程的arena分配到映射的内存空间中

2. 堆会维护一个freelist（glibc里面称为bin）来对堆中未被使用的内存地址进行记录，如果在同一个arena中请求堆，先检查bin中是否有free的堆地址，如果堆不够用时，才会向内核请求增加arena的内存大小

free（）

调用free（）函数并不会将malloc（）分配的内存释放掉，仅仅是将free的内存地址加入bin，在下一次malloc的时候可以使用

堆结构

堆结构分为三层：arena、heap、chunk
这里绘制了一副图表明堆，类似的这样的图网上还有很多

arena

1. arena的个数有上限，通常为CPU核心的个数2（32位系统）8（64位系统），如果超过了这一上限，则内核可能将多个线程的堆映射到一个arena
2. 一个arena可以维护多个堆，但是只维护一个malloc_state（即Arena Header）

只有一个堆的内存地址

当当前堆内存地址空间不足时，调用mmap（）在内存空间中映射一个新的堆出来，映射出来后的结果如下

heap

1. 如果一个arena维护了多个堆，每个堆需要维护一个heap_info（即Heap Header）。但main arena是例外，因为他不需要调用mmap，只需要往后增加内存大小就可以，他只用维护一个堆就好
2. 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，排序后分为上述三类）

1. 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
2. fast bins：

• 单链表FILO（first in last out），每个freechunk维护一个fd指针指向bin中记录的下一个fast chunk的地址
• 每个bins记录的chunk大小一致，第0个bin记录8字节的chunk，第一个记录16字节，第二个记录24字节，此后递增

• fast chunks可以是内存地址上连续的，这是chunk中的一个例外

  
  

3. unsorted bins：

• 当small 和large chunk被free后，chunk会被加入到unsorted bins
• 双链表，在调用malloc（）时会首先检查是否有unsorted chunk，然后根据size决定将他分类或者合并

4. small bins：

• 双链表FIFO（first in first out）
• 与fast bins类似，以8个字节为单位分类bin。smallchunk的尺寸大小为120~512字节
• free时，先检查前/后一个chunk是否是free的，如果是，则合并，之后加入到unsorted中

5. 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