基本数据结构
- Main_arena
在最开始实现的版本中只有一个main arena，每次分配内存都必须对主分配区加锁，分配完成后释放锁。 在多线程环境下由于锁的竞争效率低。
新版本增加了非主分配区。根据系统对分配区的争用情况非主分配区会增加，但不减少。
- 主分配区访问heap和mmap区域（主分配区可以使用sbrk和mmap想操作系统申请虚拟内存），非主分配区只能访问mmap区域。
- 主分配区每次mmap向操作系统刚申请HEAP_MAX_SIZE（32位1MB,64位64MB）大小的虚拟内存。
- 当某一线程需要调用malloc()分配内存空间时，该线程先查看线程私有变量中是否已经存在一个分配区，如果存在，尝试对该分配区加锁，如果加锁成功，使用该分配区分配内存，如果失败，该线程搜索循环链表试图获得一个没有加锁的分配区。如果所有的分配区都已经加锁，那么malloc()会开辟一个新的分配区，把该分配区加入到全局分配区循环链表并加锁，然后使用该分配区进行分配内存操作。
- chunk
ptmalloc 在给用户分配的空间的前后加上了一些控制信息，用这样的方法来记录分配的信息，以便完成分配和释放工作。一个使用中的chunk（使用中，就是指还没有被free掉）在内存中的样子如图所示：
- mem：返回给用户的内存指针
- chunk控制位：P，它表示前一个块是否在使用中，M，他表示当前chunk是从哪个内存区域获得的虚拟内存（mmao/brk）A，表示该chunk属于主分配区或者非主分配区。
下面展示了一个空闲chunk在内存中的状态
- bins
ptmalloc将相似大小的chunk用双向链表链接起来，这样的一个链表被称为一个bin.ptmalloc一共维护了128个bin,并使用一个数组来存储这些bin.
unsorted bins:bins数组的第一个
small bins:2
64的bin（chunk大小范围为16512）large bins:large bins中的每一个bin分别包含了一个给定范围内的chunk，其中的chunk按大小序排列。相同大小的chunk同样按照最近使用顺序排列。
fast bins:主要用来处理申请释放一些小的内存空间。后入先出。
ptmalloc中在分配过程中引入了fast bins，不大于max_fast （默认值为64B）的chunk被释放后，首先会被放到fast bins 中，fast bins中的chunk并不改变它的使用标志P。这样也就无法将它们合并。当需要给用户分配的chunk小于或等于max_fast时，ptmalloc首先会在fast bins中查找相应的空闲块，然后才会去查找bins中的空闲chunk.
- Unsorted bin:bins的缓冲区
如果被用户释放的chunk大于max_fast，或者fast bins中的空闲chunk合并后，这些chunk首先会被放到unsorted bin队列中,，在进行malloc操作的时候，如果在fast bins中没有找到合适的chunk，则ptmalloc会先在unsorted bin中查找合适的空闲chunk，然后才查找bins。
- 三种特殊的chunk
- top chunk:fast bin和bin失效后的补救措施
非主分配区预先从mmap区域分配交大的空间内存模拟sub-heap。
Q1：什么时候分配？
A：第一次使用malloc时，主分配区在堆顶分配，子分配区mmap后在分配。
- mmaped chunk:top chunk不能分配的补救措施
如果top chunk都不能分配，直接mmap一段内存到共享映射区。
- last reminder
当需要分配一个small chunk,但在small bins中找不到合适的chunk，如果last remainder chunk的大小大于所需要的small chunk大小，last remainder chunk被分裂成两个chunk，其中一个chunk返回给用户，另一个chunk变成新的last remainder chunk。
last remainder chunk主要通过提高内存分配的局部性来提高连续malloc（产生大量 small chunk）的效率。
brk和mmap注意事项
- 在使malloc之前，brk的值等于start_brk，也就是说heap大小为0.
- ptmalloc在开始时，若请求的空间小于 mmap分配阈值（mmap threshold，默认值为128KB）时，主分配区会调用sbrk()增加一块大小为 (128 KB + chunk_size) align 4KB的空间作为heap。非主分配区会调用mmap映射一块大小为HEAP_MAX_SIZE（32位系统上默认为1MB，64位系统上默认为64MB）的空间作为sub-heap.
- 当用户请求内存分配时，首先会在这个区域内找一块合适的chunk给用户。当用户释放了heap 中的chunk时，ptmalloc又会使用fast bins和bins来组织空闲chunk。以备用户的下一次分配。
- 若需要分配的chunk大小小于mmap分配阈值，而heap空间又不够，则此时主分配区会通过sbrk()调用来增加heap大小，非主分配区会调用mmap映射一块新的sub-heap，也就是增加top chunk的大小，每次heap增加的值都会对齐到4KB。
- 当用户的请求超过mmap分配阈值，并且主分配区使用sbrk()分配失败的时候，或是非主分配区在top chunk中不能分配到需要的内存时，ptmalloc会尝试使用mmap()直接映射一块内存到进程内存空间。使用mmap()直接映射的chunk在释放时直接解除映射，而不再属于进程的内存空间.
分配算法
- 小于等于64字节：用pool算法分配。
- 64到512字节之间：在最佳匹配算法分配和pool算法分配中取一种合适的。
- 大于等于512字节：用最佳匹配算法分配。
- 大于等于mmap分配阈值（默认值128KB）：根据设置的mmap的分配策略进行分配，如果没有开启mmap分配阈值的动态调整机制，大于等于128KB就直接调用mmap()分配。否则，大于等于mmap分配阈值时才直接调用mmap()分配。
分配具体流程
- 获取分配区的锁，为了防止多个线程同时访问同一个分配区，在进行分配之前需要取得分配区域的锁。线程先查看线程私有实例中是否已经存在一个分配区，如果存在尝试对该分配区加锁，如果加锁成功，使用该分配区分配内存，否则，该线程搜索分配区循环链表试图获得一个空闲（没有加锁）的分配区。如果所有的分配区都已经加锁，那么ptmalloc会开辟一个新的分配区，把该分配区加入到全局分配区循环链表和线程的私有实例中并加锁，然后使用该分配区进行分配操作。开辟出来的新分配区一定为非主分配区，因为主分配区是从父进程那里继承来的。开辟非主分配区时会调用mmap()创建一个sub-heap，并设置好top chunk。
- 将用户的请求大小转换为实际需要分配的chunk空间大小。
- 判断所需分配chunk的大小是否满足chunk_size <= max_fast (max_fast 默认为 64B)，如果是的话，则转下一步，否则跳到第5步。
- 首先尝试在fast bins中取一个所需大小的chunk分配给用户。如果可以找到，则分配结束。否则转到下一步。
- 判断所需大小是否处在small bins中，即判断chunk_size < 512B是否成立。如果chunk大小处在small bins中，则转下一步，否则转到第6步。
- 根据所需分配的chunk的大小，找到具体所在的某个small bin，从该bin的尾部摘取一个恰好满足大小的chunk。若成功，则分配结束，否则，转到下一步。
- 到了这一步，说明需要分配的是一块大的内存，或者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中，遍历完成后，转入下一步。
- 到了这一步，说明需要分配的是一块大的内存，或者small bins和unsorted bin中都找不到合适的 chunk，并且fast bins和unsorted bin中所有的chunk都清除干净了。从large bins中按照“smallest-first，best-fit”原则，找一个合适的 chunk，从中划分一块所需大小的chunk，并将剩下的部分链接回到bins中。若操作成功，则分配结束，否则转到下一步。
- 如果搜索fast bins和bins都没有找到合适的chunk，那么就需要操作top chunk来进行分配了。判断top chunk大小是否满足所需chunk的大小，如果是，则从top chunk中分出一块来。否则转到下一步。
- 到了这一步，说明top chunk也不能满足分配要求，所以，于是就有了两个选择: 如果是主分配区，调用sbrk()，增加top chunk大小；如果是非主分配区，调用mmap来分配一个新的sub-heap，增加top chunk大小；或者使用mmap()来直接分配。在这里，需要依靠chunk的大小来决定到底使用哪种方法。判断所需分配的chunk大小是否大于等于 mmap分配阈值，如果是的话，则转下一步，调用mmap分配，否则跳到第12步，增加top chunk 的大小。
- 使用mmap系统调用为程序的内存空间映射一块chunk_size align 4kB大小的空间。 然后将内存指针返回给用户。
- 判断是否为第一次调用malloc，若是主分配区，则需要进行一次初始化工作，分配一块大小为(chunk_size + 128KB) align 4KB大小的空间作为初始的heap。若已经初始化过了，主分配区则调用sbrk()增加heap空间，分主分配区则在top chunk中切割出一个chunk，使之满足分配需求，并将内存指针返回给用户。
参考文献：
csdn ptmalloc
《glic内存管理ptmalloc源码分析》