骑麦兜看落日

[Binary]Heap

字数统计: 1.3k阅读时长: 4 min
2018/08/05 Share

堆概述

\2. ptmalloc 的响应用户内存分配要求的具体步骤为:

  1. 1) 获取分配区的锁,为了防止多个线程同时访问同一个分配区,在进行分配之前需要

    取得分配区域的锁。线程先查看线程私有实例中是否已经存在一个分配区,如果存 在尝试对该分配区加锁,如果加锁成功,使用该分配区分配内存,否则,该线程搜 索分配区循环链表试图获得一个空闲(没有加锁)的分配区。如果所有的分配区都 已经加锁,那么 ptmalloc 会开辟一个新的分配区,把该分配区加入到全局分配区循 环链表和线程的私有实例中并加锁,然后使用该分配区进行分配操作。开辟出来的 新分配区一定为非主分配区,因为主分配区是从父进程那里继承来的。开辟非主分 配区时会调用 mmap()创建一个 sub-heap,并设置好 top chunk。

  2. 2) 将用户的请求大小转换为实际需要分配的 chunk 空间大小。

  3. 3) 判断所需分配 chunk 的大小是否满足 chunk_size <= max_fast (max_fast 默认为 64B),

    如果是的话,则转下一步,否则跳到第 5 步。

  4. 4) 首先尝试在 fast bins 中取一个所需大小的 chunk 分配给用户。如果可以找到,则分

    1
    配结束。否则转到下一步。
  5. 5) 判断所需大小是否处在 small bins 中,即判断 chunk_size < 512B 是否成立。如果

    chunk 大小处在 small bins 中,则转下一步,否则转到第 6 步。

  6. 6) 根据所需分配的 chunk 的大小,找到具体所在的某个 small bin,从该 bin 的尾部摘

    取一个恰好满足大小的 chunk。若成功,则分配结束,否则,转到下一步。

  7. 7) 到了这一步,说明需要分配的是一块大的内存,或者 small bins 中找不到合适的 chunk。于是,ptmalloc 首先会遍历 fast bins 中的 chunk,将相邻的 chunk 进行合并, 并链接到 unsorted bin 中,然后遍历 unsorted bin 中的 chunk,如果 unsorted bin 只 有一个 chunk,并且这个 chunk 在上次分配时被使用过,并且所需分配的 chunk 大 小属于 small bins,并且 chunk 的大小大于等于需要分配的大小,这种情况下就直 接将该 chunk 进行切割,分配结束,否则将根据 chunk 的空间大小将其放入 small

    bins 或是 large bins 中,遍历完成后,转入下一步。

  8. 8) 到了这一步,说明需要分配的是一块大的内存,或者 small bins 和 unsorted bin 中

    都找不到合适的 chunk,并且 fast bins 和 unsorted bin 中所有的 chunk 都清除干净 了。从 large bins 中按照“smallest-first,best-fit”原则,找一个合适的 chunk,从 中划分一块所需大小的 chunk,并将剩下的部分链接回到 bins 中。若操作成功,则 分配结束,否则转到下一步。

  9. 9) 如果搜索 fast bins 和 bins 都没有找到合适的 chunk,那么就需要操作 top chunk 来 进行分配了。判断 top chunk 大小是否满足所需 chunk 的大小,如果是,则从 top chunk 中分出一块来。否则转到下一步。

  10. 10) 到了这一步,说明 top chunk 也不能满足分配要求,所以,于是就有了两个选择: 如 果是主分配区,调用 sbrk(),增加 top chunk 大小;如果是非主分配区,调用 mmap 来分配一个新的 sub-heap,增加 top chunk 大小;或者使用 mmap()来直接分配。在 这里,需要依靠 chunk 的大小来决定到底使用哪种方法。判断所需分配的 chunk 大小是否大于等于 mmap 分配阈值,如果是的话,则转下一步,调用 mmap 分配, 否则跳到第 12 步,增加 top chunk 的大小。

  11. 11) 使用 mmap 系统调用为程序的内存空间映射一块 chunk_size align 4kB 大小的空间。 然后将内存指针返回给用户。

  12. 12) 判断是否为第一次调用 malloc,若是主分配区,则需要进行一次初始化工作,分配 20

一块大小为(chunk_size + 128KB) align 4KB 大小的空间作为初始的 heap。若已经初 始化过了,主分配区则调用 sbrk()增加 heap 空间,分主分配区则在 top chunk 中切 割出一个 chunk,使之满足分配需求,并将内存指针返回给用户。

Fast bins 可以看着是 small bins 的一小部分 cache,默认情况下,fast bins 只 cache 了 small bins 的前 7 个大小的空闲 chunk,也就是说,对于 SIZE_SZ 为 4B 的平台,fast bins 有 7 个 chunk 空闲链表(bin),每个 bin 的 chunk 大小依次为 16B,24B,32B,40B,48B,56B,64B;对 于SIZE_SZ为8B的平台,fast bins有7个chunk空闲链表(bin),每个bin的chunk大小依 次为 32B,48B,64B,80B,96B,112B,128B。


参考资料

CATALOG
  1. 1. 堆概述
  2. 2. 参考资料