堆数据结构的理解

堆的数据结构

Posted by 枸杞蒲蒻 on August 20, 2019

_int_malloc

_int_malloc是内存分配的核心函数它主要进行一下思想的核心操作:

  • 根据用户申请的内存块大小来进行分配(fastbin,small bin,large bin,unsorted bin)
  • 有小到大依次检查不同的bin又不是有相应的块可以用来分配
  • 当所有的chunk无法满足则会考虑top chunk
  • top chunk无法满足则会内存申请

    fast bin

    申请内存的大小位于fast bin范围内,则从fastbin开始取chunk,一般情况下系统将fastbin的chunk inuse始终置为1,除非fastbin和相邻空闲chunk的大小和大于FASTBIN_CONSOLIDATION_THRESHOLD系统就会将它和别的chunk合并。 fast bin存储采用头插法,LIFO

    small bin

    small bin 大小一般是chunk_size = 2 * SIZE_SZ*index。small bin总共有62个循环双向链表。 每个small bin 采用双链表FIFO small bin 经常会有unlink攻击 small bin 一部分大小和fast bin 重合

    large bin

    large bin 一共包含63个bin,每个大小不一致,但是大小公差一致 系统在处理large bin之前会会先使用malloc_consolidate,将可能合并的fastbin合并后放入unsorted bin 中,将不能合并的直接放入unsorted bin中.

    unsorted bin

    unsorted bin 其实像是一个bin的缓冲区。 unsorted bin 产生有如下方式:

  • 当一个较大的chunk被分割成两半后,剩下的部分大于MINSIZE就会被放到unsorted bin中
  • 释放一个不属于fast bin 的chunk,且该chunk不和top chunk紧邻将会被放入unsorted bin
  • 在申请large bin时将可以合并的fastbin合并后放入unsorted bin,将不能合并的放入unosrted bin

    large bin的分配过程

    首先会先遍历unsorted bin如果满足于用户申请条件则会将chunk取出后直接返回。 如果不是则会放入相应的bin中 unsorted bin中扫描完后会扫描large bin 之后是top chunk 最后申请内存