【分享吧】PTMalloc内存管理浅析

  前言：PTMalloc是glibc自带的内存分配器，其中最出名的两个函数便是大家最常用malloc/free，但是用了这么久的malloc/free，你真的了解它们吗？
奇怪的问题
  1、为什么两次申请的内存地址相同呢？

  2、为什么同样free掉的内存，有的可以继续访问，有的会引发越界呢？

  3、为什么多线程并发申请内存，得到的地址差别这么大？

  4、为什么同一个线程分配不同大小的内存，得到的地址差别这么大？

  5、为什么申请的内存都释放掉了，进程占用的内存还是居高不下？

  上图1对应malloc3进程，上图2对应malloc4进程

术语解释
  1、chunk：ptmalloc内部的块管理数据结构，chunksize=(bytes + 16) & ~15，最小不能小于32字节。
  2、arena：内存分配区域，负责向应用程序提供统一的内存分配/回收功能。由于多线程的缘故，一个进程中可能存在多个arena。
  3、fastbins：arena中的高速缓冲内存块，负责小于128字节内存块的快速分配和回收。
  4、smallbins：64个内存块箱，每个箱子大小间隔为16字节。在内存块大小位于128-1024字节或者fastbins没有合适内存块时使用。
  5、largebins：64个内存块箱，每个箱子大小间隔递增，在内存块大于1024字节时使用。
  6、unsortedbins：fastbins内存块的临时回收站，负责向smallbins/largebins输送内存块。
  7、topchunk：arena中从未参与内存分配的起始可用空间，当内存块无法从free list中获取时，会用topchunk中划分新的内存区域。
  8、sbrk：向操作系统申请堆内存上的空间
  9、mmap：向操作系统申请一块内存映射空间。
Malloc解析
  1、小于等于128字节的chunk优先从fastbins中分配，fastbins中总共7个内存箱，每个内存箱存放的内存块大小间隔为16字节。每个内存箱挂载着一个双向链表，分配内存时先尝试从表头摘取一块内存直接使用。

  2、当fastbins中没有空闲内存块，或者内存块大小大于128字节但小于1024字节时，尝试从smallbins中摘取一块内存直接使用。smallbins中总共64个内存箱，每个内存箱大小间隔为16字节，依然是一个双向链表。

  问题：fastbins和smallbins区别在哪儿呢？
  3、当fastbins和smallbins中均没有满足条件的内存块时，尝试将fastbins中的空闲内存块和其他已经释放的内存块做合并回收操作，并将合并后的内存块放入unsortedbins中。
  4、尝试从unsorted_bins中再做一次内存分配，如果仍然不能成功，则将unsortedbins中的内存块按大小分配到smallbins和largebins中。
  5、经过第3步的回收后，largebins中可能已经存在了一些备选的内存块，开始尝试从largebins中分配内存。
  largebins大概长这个样子
  32个64字节大小间隔的内存箱

  16个512字节大小间隔的内存箱

  8个4096字节大小间隔的内存箱
  4个32768字节大小间隔的内存箱
  2个262144字节大小间隔的内存箱
  1个768K字节大小间隔的内存箱
  注：由于largebins的内存箱中的内存块大小不一，所以每个内存箱中的空闲块链表是按从小到大连接的，每次挑选内存块也从小到大挑选一个最合适的，剩下的部分放入unsortedbins中，等待重新分配。如果当前对应的内存箱中没有空闲内存块，则从下一个l内存箱中继续筛选。
  6、从topchunk中分配内存：topchunk是当前arena中还未被分配的一大块内存，如果topchunk的大小大于申请内存块的大小，则将topchunk切割一部分分配出去。
  当topchunk也无法分配给定大小的内存块时，需要调用sbrk扩充topchunk的大小，然后再从topchunk中分配内存块返回。
  当申请的内存块大小大于128K时，直接调用mmap分配内存并返回。
  多线程下的malloc:
  每个arena在分配内存的过程中都要加一个锁，如果当前系统的arena都被锁住，则malloc时会开辟一个新的arena，将这个arena挂到进程arena列表中，并从这个新的arena中分配内存块。进程初始状态下只有一个main_arena，地址空间通过sbrk获取内存，其他的arena都是调用mmap获取内存。
Free解析
  1、首先判断释放的内存块大小是否属于fastbins，是的话直接挂到对应内存箱的空闲内存块表头。
  2、否则如果是mmap获取的大块内存，直接调用munmap还给操作系统。
  3、否则如果释放的内存块紧邻topchunk，则将它合并到topchunk中。
  4、否则检查该内存块的前后chunk是否也空闲，是的话将它们合并成一个大的空间内存块放入unsortedbins等待复用。
  5、将fastbins中的空闲内存尝试与相邻空闲内存合并后，统统放入unsorted_bins中等待重新分配。
  6、当前 free 的块大小加上前后空闲内存块能合并 chunk 的大小大于 64KB，并且堆顶的大小达128K，才会收缩arena申请的堆内存，把堆最顶端的空闲内存返回给操作系统。
  smallbins和fastbins的区别：fastbins中的内存块不被标记为空闲，不会被free的内存块做相邻合并。而smallbins中的内存块会被free的内存块做相邻合并，所以fastbins可以看做一个高速的小块内存缓冲。
谜底揭晓
  1、为什么同一线程先后两次申请的内存地址相等：对于小块内存，free掉后会被缓存在fastbins一段时间，如果没有触发fastbins回收机制，那么再次申请相同大小的chunk就会得到以前的地址。
  2、为什么多线程一起申请内存，得到的地址差这么大：由于非main_arena中的内存空间都是通过mmap获得，所以和sbrk获取的堆地址相差很大。
  3、为什么同一个线程分配不同大小的内存，得到的地址差别这么大：大于128K的内存直接走的mmap。
  4、为什么同样free掉的内存，有的可以继续访问，有的访问直接coredown：对于小块内存，如果free之后没有触发topchunk收缩机制，那么这个地址对于进程来说依然是可读写的。对于128K以上的大块内存，free时直接调用了munmap将地址映射关系解除，此时这个地址就是不可读写的。
  5、为什么申请的内存都释放掉了，进程占用的内存空间还是居高不下：topchunk只有在符合一定条件时才会进行收缩，如果只是释放中间的一些内存的话，即使内存块再大也不会还给操作系统。
PTMalloc的问题
  1、当分配极小内存时，由于chunksize对齐的缘故，会造成大量的空间浪费。比如即使只想分配8字节的内存，在ptmalloc内部也分配了32字节。
  2、当交替申请的内存块尾部没有释放时，即使释放掉中间的内存块，也无法将地址空间交还给操作系统。
  3、所有内存块都是从top内存区分出来的，并没有专门给不同尺寸的内存划分专属内存池，所以定长小内存有很大几率会和变长大内存交错混在一起。这将使得小内存块随时可能和大内存块合并，后续再次申请时造成二次地址划分，使得定长内存的优势大打折扣，malloc时的数据的局部性也很不好（长时间运行后，连续申请的小块内存很可能地址不再连续）。
  4、多线程在同一个arena中并发申请地址，存在锁的开销。
END