title： 内存分配与释放概述

一、内存分配算法

分配算法概述，以 32 位系统为例

  • 小于等于 64字节，用 pool 算法分配
  • 64 到 512 字节之间，在最佳匹配算法分配和 pool 算法分配中取一种合适的
  • 大于等于 512 字节，用最佳匹配算法分配
  • 大于等于 mmap 分配阈值（默认值 128KB）：根据设置的 mmap 的分配策略进行分配，如果没有开启 mmap 分配阈值的动态调整机制，大于等于 128KB 就直接调用 mmap 分配。否则，大于等于 mmap 分配阈值时才直接调用 mmap 分配

ptmalloc 响应用户内存分配要求的具体步骤如下：

  1. 获取分配区的锁，为了防止多个线程同时访问同一个分配区，在进行分配之前需要取得分配区的锁。线程会先查看线程局部缓存 TLS中是否已经存在一个分配区，如果存在尝试对该分配区加锁，如果加锁成功，使用该分配区分配内存，否则，该线程搜索分配区循环链表试图获得一个空闲（没有加锁）的分配区。如果所有的分配区都已经加锁，那么ptmalloc会开辟一个新的分配区，把该分配区加入到全局分配区循环链表和线程的局部缓存 TLS 中并加锁，然后使用该分配区进行分配操作。开辟出来的新分配区一定为非主分配区，因为主分配区是从父进程那里继承来的。开辟非主分配区时会调用 mmap() 创建一个 sub-heap，并设置好 top chunk。
  2. 将用户的请求内存大小转换为实际需要分配的 chunk 空间大小。
  3. 判断所需分配 chunk 的大小是否满足 chunk_size <= max_fast (max_fast 默认为 64B)，如果是的话，则转下一步，否则跳到第5步。
  4. 首先尝试在 fast bins 中取一个所需大小的 chunk 分配给用户。如果可以找到，则分配结束。否则转到下一步
  5. 判断所需大小是否处在 small bins 中，即判断 chunk_size < 512B 是否成立。如果 chunk 大小处在 small bins 中，则转下一步，否则转到第6步。
  6. 根据所需分配的 chunk 的大小，找到具体所在的某个 small bin，从该 bin 的尾部摘取一个恰好满足大小的 chunk。若成功，则分配结束，否则，转到下一步。
  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. 到了这一步，说明需要分配的是一块大的内存，或者 small bins 和 unsorted bin 中都找不到合适的 chunk，并且 fast bins 和 unsorted bin 中所有的 chunk 都清除干净了。从 large bins 中按照 “smallest-first，best-fit” 原则，找一个合适的 chunk，从中划分一块所需大小的 chunk，并将剩下的部分链接回到 bins 中。若操作成功，则分配结束，否则转到下一步。
  9. 如果搜索 fast bins 和 bins 都没有找到合适的 chunk，那么就需要操作 top chunk 来进行分配了。判断 top chunk 大小是否满足所需 chunk 的大小，如果是，则从 top chunk 中分出一块来。否则转到下一步。
  10. 到了这一步，说明 top chunk 也不能满足分配要求，所以，于是就有了两个选择: 如果是主分配区，调用 sbrk()，增加 top chunk 大小；如果是非主分配区，调用 mmap 来分配一个新的 sub-heap，增加 top chunk 大小；或者使用 mmap() 来直接分配。在这里，需要依靠 chunk 的大小来决定到底使用哪种方法。判断所需分配的 chunk 大小是否大于等于 mmap 分配阈值，如果是的话，则转下一步，调用 mmap 分配，否则跳到第12步，增加 top chunk 的大小
  11. 使用 mmap 系统调用为程序的内存空间映射一块 chunk_size align 4kB 大小的空间。 然后将内存指针返回给用户。
  12. 判断是否为第一次调用 malloc，若是主分配区，则需要进行一次初始化工作，分配一块大小为 (chunk_size + 128KB) align 4KB 大小的空间作为初始的 heap。若已经初始化过了，主分配区则调用 sbrk() 增加 heap 空间，分主分配区则在 top chunk 中切割出一个 chunk，使之满足分配需求，并将内存指针返回给用户。

总结一下：根据用户请求分配的内存的大小，ptmalloc 有可能会在两个地方为用户分配内存空间。在第一次分配内存时，一般情况下只存在一个主分配区，但也有可能从父进程那里继承来了多个非主分配区，在这里主要讨论主分配区的情况，brk 值等于 start_brk，所以实际上 heap 大小为 0，top chunk 大小也是0。这时，如果不增加 heap 大小，就不能满足任何分配要求。所以，若用户的请求的内存大小小于 mmap 分配阈值，则 ptmalloc 会初始 heap。然后在 heap 中分配空间给用户，以后的分配就基于这个 heap 进行。若第一次用户的请求就大于 mmap 分配阈值，则 ptmalloc 直接使用 mmap() 分配一块内存给用户，而 heap 也就没有被初始化，直到用户第一次请求小于 mmap 分配阈值的内存分配。第一次以后的分配就比较复杂了，简单说来，ptmalloc 首先会查找 fast bins，如果不能找到匹配的chunk，则查找 small bins。若还是不行，合并 fast bins，把 chunk 加入 unsorted bin，在 unsorted bin 中查找，若还是不行，把 unsorted bin 中的 chunk 全加入 large bins 中，并查找 large bins。在 fast bins 和 small bins 中的查找都需要精确匹配，而在 large bins 中查找时，则遵循 “smallest-first，best-fit” 的原则，不需要精确匹配。若以上方法都失败了，则ptmalloc 会考虑使用 top chunk。若 top chunk 也不能满足分配要求。而且所需 chunk 大小大于 mmap 分配阈值，则使用 mmap 进行分配。否则增加 heap，增大 top chunk。以满足分配要求。

二、内存回收概述

free() 函数接受一个指向分配区域的指针作为参数，释放该指针所指向的chunk。而具体的释放方法则看该chunk所处的位置和该chunk的大小。free()函数的工作步骤如下：

  1. free() 函数同样首先需要获取分配区的锁，来保证线程安全
  2. 判断传入的指针是否为 NULL，如果为 NULL，则什么都不做，直接 return。否则下一步
  3. 判断所需释放的 chunk 是否为 mmaped chunk，如果是，则调用 munmap() 释放 mmaped chunk，解除内存空间映射，该空间不再有效。如果开启了 mmap 分配阈值的动态调整机制，并且当前回收的 chunk 大小大于 mmap 分配阈值，将 mmap 分配阈值设置为该 chunk 的大小，将 mmap 收缩阈值设定为 mmap 分配阈值的 2 倍，释放完成，否则跳到下一步。
  4. 判断 chunk 的大小和所处的位置，若 chunk_size <= max_fast，并且 chunk 并不位于 heap 的顶部，也就是说并不与 top chunk 相邻，则转到下一步，否则跳到第 6 步。（因为与 top chunk 相邻的小 chunk 也和 top chunk进行合并，所以这里不仅需要判断大小，还需要判断相邻情况）
  5. 将 chunk 放到 fast bins 中，chunk 放入到 fast bins 中时，并不修改该 chunk 使用状态位 P。也不与相邻的 chunk 进行合并。只是放进去，如此而已。这一步做完之后释放便结束了，程序从 free() 函数中返回。
  6. 判断前一个 chunk 是否处在使用中，如果前一个块也是空闲块，则合并。并转下一步
  7. 判断当前释放 chunk 的下一个块是否为 top chunk，如果是，则转第 9 步，否则转下一步。
  8. 判断下一个 chunk 是否处在使用中，如果下一个 chunk 也是空闲的，则合并，并将合并后的 chunk 放到 unsorted bin 中。注意，这里在合并的过程中，要更新 chunk 的大小，以反映合并后的 chunk 的大小。并转到第 10 步。
  9. 如果执行到这一步，说明释放了一个与 top chunk 相邻的 chunk。则无论它有多大，都将它与 top chunk 合并，并更新 top chunk 的大小等信息。转下一步。
  10. 判断合并后的 chunk 的大小是否大于 FASTBIN_CONSOLIDATION_THRESHOLD（默认64KB），如果是的话，则会触发进行 fast bins 的合并操作，fast bins 中的 chunk 将被遍历，并与相邻的空闲 chunk 进行合并，合并后的 chunk 会被放到 unsorted bin 中。fast bins 将变为空，操作完成之后转下一步。
  11. 判断 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 收缩阈值，才有可能收缩堆。

三、注意事项

为了避免 Glibc 暴增，使用时要注意：

  1. 后分配的内存先释放，因为 ptmalloc 收缩内存是从 top chunk 开始，如果与 top chunk 相邻的 chunk 不能释放，top chunk 以下的 chunk 都无法释放。
  2. ptmalloc 不适合用于管理长生命周期的内存，特别是持续性的、不定期分配和释放的长生命周期的内存。如果要用 ptmalloc 分配长生命周期内存，那么分配的内存块大小最好大于 32MB，因为 32 MB 是 mmap 分配阈值的最大值，大于 32M 可以保证 ptmalloc 分配的内存一定是从 mmap 映射区域分配的，当 free 时，ptmalloc 会直接把该内存返回给操作系统。这样可以避免被 ptmalloc 缓存。同时，不定期分配长生命周期的内存容易造成内存碎片，不利于回收。
  3. 不要关闭 ptmalloc 的 mmap 分配阈值动态调整机制，因为这种机制保证了短生命周期的内存分配尽量从 ptmalloc 的缓存中分配，更高效。如果关闭了该机制，对大于 128KB 的内存分配就会使用 mmap 分配内存，而使用 mmap 分配内存特别慢，特别是在多线程同时分配大内存块时，操作系统会串行的调用 mmap，并为发生缺页异常的页加载新物理页，还要默认强制清 0。因此频繁使用 mmap 分配内存是相当低效的。使用 mmap 分配内存只适合长生命周期的大内存块。
  4. 多线程分阶段执行（比如：线程 A 先执行，线程 B 拿到结果后再执行）的程序不适合用 ptmalloc。因为 ptmalloc 假设了线程 A 释放的内存块能在线程 B 中得到重用，但线程 B 不一定会分配和线程 A 同样大小的内存块，于是就需要不断的做切割和合并，可能导致内存碎片。
  5. 尽量减少程序的线程数量、尽量避免频繁的分配和释放内存。ptmalloc 在多线程竞争激烈的情况下，首先查看线程局部缓存 TLS 中是否存在分配区，如果存在则尝试加锁，如果加锁不成功会尝试其他分配区，如果所有分配区的锁都被占用着，就会增加一个非主分配区供当前线程使用。由于在多个线程的局部缓存中可能会保存同一个分配区，所以当线程较多时，加锁的代价就会上升，ptmalloc 分配和回收都要对分配区加锁，从而导致了多线程竞争环境下 ptmalloc 的性能非常低。
  6. 不要出现内存泄漏，ptmalloc 对内存泄漏是相当敏感的，根据他的内存收缩机制，如果与 top chunk 相邻的那个 chunk 没有回收，将导致 top chunk 以下的空闲内存都无法返回给操作系统。

问题：

  1. 如果后分配的内存先释放，无法及时归还系统。因为 ptmalloc 收缩内存是从 top chunk 开始,如果与 top chunk 相邻的 chunk 不能释放, top chunk 以下的 chunk 都无法释放。
  2. 每个chunk至少8字节的开销很大
  3. 内存不能在线程间移动，多线程使用内存不均衡将导致内存浪费
  4. 不定期分配长生命周期的内存容易造成内存碎片，不利于回收。
  5. 锁耗时，无论当前分区有无耗时，在内存分配和释放时，会首先加锁。