堆分配（自己复现）

发表于： 分类于：
字数： 1916 阅读：≈ 4分钟 浏览：

[TOC] 一篇讲的比较清楚的博客

malloc函数

说明：first chunk是指bin中链表头部的chunk,last chunk是指bin中链表尾部的chunk。fastbin是LIFO，其他bin是FIFO

  1. 判断是否在fastbin大小范围内，如果在则根据malloc的size求出idx；如果fastbin[idx]不为空则取first chunk；如果为空，进入unsorted bins大循环
  2. 如果不在fastbin大小范围内，判断是否在smallbin大小范围内。如果在则根据malloc的size求出idx；如果smallbin[idx]不为空则取last chunk；如果为空,判断smallbin是否初始化。如果已经初始化，那么就进入unsorted bins大循环；如果没有初始化，调用malloc consolidate函数再进入unsorted bins大循环
  3. 如果既不在fastbin大小范围内，也不在smallbin大小范围内，判断有无fastchunks。如果没有，进入unsorted bins大循环；如果有，调用malloc consolidate函数再进入unsorted bins大循环

malloc consolidate函数

  • 穷尽合并fastbin里面的chunk并放入unsorted bin中，与top chunk合并的chunk除外
  1. 遍历整个fastbinY(这是个指针数组,每个元素是一个单向链表的头部),只要整个fastbinY有chunk就遍历。先看prev inuse，如果为0,则unlink prev chunk；如果为1，看next chunk。如果next chunk为top chunk，那就和top chunk合并(和top合并后就直接遍历下一个fastchunk了);如果不是，看next inuse。如果为0，则unlink next chunk；为1就什么都不做。不管next inuse为0还是1，最终都将合并后的chunk插入unsorted bins中
  2. 一直遍历fastbinY直到fastbinY为空，进入unsorted bins大循环

unsorted bins大循环

  • 遍历unsorted bin判断是否有满足条件的unsorted chunk，如果不满足条件就consolidate（将其放入合适的bin中）
  1. 取last unsorted chunk
  2. 1.如果大小刚好合适，返回这个chunk 2.如果在small bin的大小，chunk进入small bin 3.如果large bin为空，放入large bin中（因为在之前已经判断是否是small bin的大小了）4.前面条件都不满足，从large bin的最后开始寻找这个chunk合适的位置。
  3. 一直遍历unsorted bin直到unsorted bin为空 malloc的时候，不论malloc的大小，首先会去检查每个bins链是否有与malloc相等大小的freechunk。如果没有就去检查bins链中是否有大的freechunk可以切割（除去fastbins链），如果切割，那么就切割大的freechunk，那么切割之后的chunk成为last remainder，并且last remainder会被放入到unsortedbin中（这里往往可以泄露libcbase）

free函数

  • 先看能不能放入fastbin，再看能不能进行后向合并与unlink prev chunk，再看能不能和top chunk合并，最后看能不能前向合并与unlink next chunk，不论进不进行前向合并与unlink next chunk，都要放入unsorted bin的头部，之后还有一些检查
  1. 做一系列检查
  2. 判断chunk大小是否小于max fast，做检查后get fastbin index for the chunksize,然后判断fastbin的first chunk是否是这个chunk（这里应该防止fastbin double free，但是很好绕过），放入fast bin中
  3. 判断chunk是否是mmaped，如果是（目前先不了解）。如果不是，做一系列检查，最重要的就是检查当前的chunk是否是inuse（这也是为什么只有fastbin double free）
  4. 检查通过后，检查prev chunk inuse，如果为0，unlink prev chunk;否则看next chunk：如果next chunk为top chunk，与top chunk合并；否则就看next chunk是否inuse,如果inuse为1，什么都不做；否则进行unlink next chunk,除了和top chunk合并的，都要将new chunk放入unsorted bin头部

unlink函数

bin只是用来管理chunk的，即使chunk被free仍然在堆这个结构中

  • 检查chunk size是否符合大小 ；检查FD,BK指向