「堆漏洞」堆结构复习之malloc和free的过程

bin的组织结构

ptmalloc【多线程版的malloc】一共有128个bin。用于分配用户动态请求的虚拟空间【系统调用底层：glibc通过brk()&mmap()实现】

bins的情况

1. unsorted bin
2. 2-64为small bins，共62个【最小为16B，最大为504B，相邻small bin之间8 字节差别，bin内相同大小】
   • 所有可能的chunk中最小的chunk也就是16B了，所以再小的chunk，small bins都可以放下
   • 相见chunk结构【有previous_size,size,fd,bk,16B】
3. 其后都会large bins，共63个【大于等于 512B 的空闲 chunk，每个bin下的链表存放的是一个范围的chunk】
   • 每组 bin 是一个固定公差的等差数列，公差依次为 64B、512B、 4096B、32768B、262144B 等
     • 第一个 large bin 的起始 chunk 大小为 512B，共 32 个 bin， 公差为 64B，即Chunk_size=512 + 64 * index
     • 第二个 large bin 的起始 chunk 大小为第一组 bin 的结束 chunk 大小，公差为512B，即Chunk_size=512 + 64 * 32 + 512 * index
   • 每组的 bin 数量依次为 32、16、8、4、2、1

fast bins

对于小chunk的管理。不大于 max_fast （默认值为 64B）的 chunk 被释放后，首先会被放到 fast bins。分配时也先考虑fast bins。

Fast bins 可以看着是 small bins 的一小部分 cache，默认情况下，fast bins 只 cache 了 small bins 的前 7 个大小的空闲 chunk。

也就是说，

1. 32位下，fast bins 有 7 个 chunk 空闲链表（bin），每个 bin 的 chunk 大小依次为 16B，24B，32B，40B，48B，56B，64B；
2. 64位下，fast bins 有 7 个 chunk 空闲链表（bin），每个 bin 的 chunk 大小依 次为 32B，48B，64B，80B，96B，112B，128B

特殊的chunk

• top chunk：bins和fastbins都无法分配，则会考虑top chunk
• last remainder：
• mmaped chunk：大于128KB，则会直接使用mmaped分配成大chunk，回收时也直接还给os，不由bins管理

ptmalloc的分配过程

• 获取分配区的锁：如果所有的分配区都已经加锁，那么 ptmalloc 会开辟一个新的分配区【非主分配区】，把该分配区加入到全局分配区循环链表和线程的私有实例【这个新增的分配区就是这个线程的私有实例】中并加锁
  • 开辟非主分配区时会调用 mmap()创建一个 sub-heap【32位下1MB，64位下64MB】，并设置好 top chunk。
• 转化成实际大小：将用户的请求大小转换为实际需要分配的 chunk 空间大小，即为H
• fast bins中尝试分配：H<= max_fast (max_fast 默认为 64B)，则在fastbin中分配。fast bin中没有则下一步，到small bin中找
  • 在 fast bins 和 small bins 中的查找都需要精确匹配
• small bins中尝试分配：H大小是否处在 small bins 中【即判断H < 512B是否成立】
  • 找到则从该 bin 的尾部摘取一个恰好满足大小的 chunk。【small bin中分配的chunk一定要求大小恰好满足。】
• 整合fast bins到unsorted bin：遍历 fast bins 中的 chunk，将相邻的 chunk 进行合并， 并链接到 unsorted bin。
• unsorted bin中尝试分配：如果 unsorted bin 只有一个 chunk，并且这个 chunk 在上次分配时被使用过。且H大小属于 small bins，并且 chunk 的大小>=H，这种情况下就直接将该 chunk 进行切割，分配结束。
  • 否则将根据 chunk 的空间大小将其放入 small bins 或是 large bins 中，遍历完成后，转入下一步。
  • 也就是说整合unsorted bin中的chunk依据大小分别放到small bins或large bins中。
  • 只有“unsorted bin 只有一个 chunk+上次分配时使用过它+H属于小chunk”才会用unsorted bin分配
  • 到了这一步，说明需要分配的是一块大的内存，或者 small bins 和 unsorted bin 中都找不到合适的 chunk，并且 fast bins 和 unsorted bin 中所有的 chunk 都清除干净了。
• 在large bins中尝试分配：按照最佳匹配算法分配，找一个合适的 chunk，切出H大小，并将剩下的部分链接回到 bins【根据大小放入small，large或是fast】
  • 不需要精确匹配
• 在top chunk中尝试分配：判断 top chunk 大小是否满足所需 chunk 的大小，如果是，则从 top chunk 中分出H，完成，剩下的部分继续作为top chunk。
  • 到了这一步，说明 top chunk 也不能满足分配要求。
  • 所以，于是就有了两个选择:
    • 如果是主分配区，调用 sbrk()，增加 top chunk 大小；
    • 如果是非主分配区，调用 mmap 来分配一个新的 sub-heap，增加 top chunk 大小；或者使用 mmap()来直接分配。
• H>mmap 分配阈值[128KB]：直接用mmap分配，成为mmaped chunk【使用 mmap 系统调用为程序的内存空间映射一块H align 4kB 大小的空间】，完成。
  • 若第一次用户的请求就大于 mmap 分配阈值，则 ptmalloc 直接使用 mmap()分配 一块内存给用户，而 heap 也就没有被初始化，直到用户第一次请求小于 mmap 分配阈值的内存分配。
• 增加top chunk的大小
  • 判断是否为第一次调用 malloc：若是主分配区，则需要进行一次初始化工作，分配一块大小为(chunk_size + 128KB) align 4KB 大小的空间作为**初始的 heap**。
    • 第一次malloc，bins和fastbins以及top chunk都没有空间可以分配，前面的步骤肯定不会分配成功，所以会到这里。
    • 如果是第一次malloc，肯定还没有非主分配区。因为主分配区空闲，不会创建新的非主分配区。因此第一次malloc调用不会出现在非主分配区。
    • 如果是非主分配区，那么在创建的时候就会调用 mmap()创建一个 sub-heap【32位下1MB，64位下64MB】，并设置好 top chunk。因此肯定不会现在才初始化【即会在top chunk中尝试分配那边完成分配】
  • 若已经初始化过了：
    • 主分配区则调用 sbrk()增加 heap 空间，在top chunk中分配
    • 非主分配区则调用 mmap 来分配一个新的 sub-heap，增加 top chunk 大小，在 top chunk 中切 割出一个 chunk=H

free的过程

free() 函数接受一个指向分配区域的指针作为参数，释放该指针所指向的 chunk。

• 获取分配区的锁：获取归还的chunk【即为G】所在分配区的锁
• 判断是否为NULL：判断传入的指针是否为 0，如果为 0，则什么都不做，直接 return
• 判断是否为mmapped chunk：判断所需释放的 chunk 是mmaped chunk，则调用 munmap()释放 mmaped chunk
  • 如果开启了 mmap 分配阈值的动态调整机制，并且当前回收的 chunk 大小大于 mmap 分配阈值，将 mmap 分配阈值设置为该 chunk 的大小，将 mmap 收缩阈值设定为 mmap 分配阈值的 2 倍，释放完成
• 判断 chunk 的大小和所处的位置：
  • 回收到fast bin：chunk_size <= max_fast，并且 chunk 并不位于 heap 的顶部，也就是说并不与 top chunk 相邻（因为与 top chunk 相邻的小 chunk 也和 top chunk 进行合并，所以这里不仅需要判断大小，还需要判断相邻情况）。将 chunk 放到 fast bins 中，不修改该 chunk 使用状态位 P。结束，free返回。
  • 判断和前一个chunk能否合并：如果没有回收到fast bin中，则判断前一个 chunk 是否处在使用中，如果前一个块也是空闲块，则合并，并且转到下一步。
  • 判断下一个chunk是否为top chunk：
    • 如果下一个chunk不是top chunk，且下一个 chunk 也是空闲的，则合并，合并后的 chunk 放到 unsorted bin 中。【注意合并时要更新大小字段】，转下一大步
    • 如果下一个chunk是top chunk，即释放了一个与 top chunk 相邻的 chunk，无论它有多大， 都将它与 top chunk 合并，并更新 top chunk 的大小等信息，转下一大步
• 判断合并后的 chunk 的大小是否大于 FASTBIN_CONSOLIDATION_THRESHOLD（默认 64KB）：
• 如果是的话，则会触发进行 fast bins 的合并操作，fast bins 中的 chunk 将被遍历，并与相邻的空闲 chunk 进行合并，合并后的 chunk 会被放到 unsorted bin 中。 fast bins 将变为空，转下一步
• 释放时：整理fast bins，合并到unsorted bin
• 分配时：整理unsorted bin到small，large bins
• 判断 top chunk 的大小是否大于 mmap 收缩阈值（默认为 128KB）：如果是的话
  • 对于主分配区，则会试图归还 top chunk 中的一部分给操作系统。但是最先分配的 128KB 空间是不会归还的，ptmalloc 会一直管理这部分内存，用于响应用户的分配请求；
  • 如果为非主分配区，会进行 sub-heap 收缩，将 top chunk 的一部分返回给操作系统，如果 top chunk 为整个 sub-heap，会把整个 sub-heap 还回给操作系统。【最初申请的也可能会归还】
• 做完这一步之后，释放结束，从 free() 函数退出。

由上可知：收缩堆的条件是当前 free 的 chunk 大小加上前后能合并 chunk 的大小大于 64k，并且要 top chunk 的大小要达到 mmap 收缩阈值，才有可能收缩堆。

• Previous
  “hitcon pwn writeUp（一）”
• Next
  「MIT 6.828」MIT 6.828 Fall 2018 Tools