一、ptmalloc1.1 特点使用空闲链表bins管理用户free掉的内存作为下次使用，而不是直接还给os，可避免频繁的系统调用，降低内存分配的开销； 若分配区锁竞争激烈，会导致非主分区快速增长，当非主分区数量达到阈值之后，会因为无法分配新的非主分区而导致线程阻塞，从而影响ptmalloc的效率； 先申请的内存先释放会导致内存无法收缩。这是因为ptmalloc的内存收缩是从Top chunk开始的，若Top chunk相邻的内存未释放，则Top chunk以下的所有内存都不能释放，从而导致内存泄漏； 申请/释放内存都需要加锁。
1.2 操作系统内存布局linux 32位操作系统：
 heap从低地址向高地址扩展，与mmap相对扩展，直至耗尽虚拟地址空间中的剩余区域； offset：随机偏移量，避免通过缓冲区溢出进行攻击； 应用程序所使用的主要是heap/mmap，前者通过sbrk->brk进行申请，后者通过mmap/unmmap将一个文件映射进内存；
由于brk/mmap属于系统调用，若每次都使用它们申请内存，则每次都会产生系统调用，影响性能；其次，由于堆是从低地址到高地址扩展的数据结构，若高地址内存未释放，则低地址内存即使已被释放也无法回收，故这种申请方式容易产生内存碎片。
基于这种原因，malloc采用内存池的管理方式（ptmalloc），ptmalloc 采用边界标记法将内存划分成很多块，从而对内存的分配与回收进行管理。为了保证内存分配的高效性，ptmalloc会预先向操作系统申请一块内存，当申请/释放内存时，ptmalloc会将这些内存管理起来，并通过一些策略来判断是否将其回收给操作系统。这样做的最大好处就是，使内存的申请/释放更为高效，避免产生过多的内存碎片。 1.4 主分配区/非主分配区旧版本的ptmalloc只有一个主分配区，而线程在分配/释放内存时都需要对主分配区加锁，因此对多线程不友好。改进后的ptmalloc由一个主分配区和若干个非主分配区构成，它们通过一个环形链表进行管理。 1.5 chunkptmalloc中分配/释放的内存都被表示成chunk。chunk按结构可分为使用中和空闲两种类型。
使用中的chunk：
说明： chunk指针：指向chunk的开始地址；mem指针：指向用户内存块的开始地址； A：主分区/非主分区标识符，0：主分配区分配，1：非主分配区分配； M：0：heap区域分配，1：mmap映射区域分配； P：前一个chunk的状态， 0：前一个chunk为空闲（此时prev_size有效）， 1：前一个chunk正在使用（此时prev_size无效）。ptmalloc 分配的第一个块总是将P置为1, 以防止程序引用不存在的chunk区域。 P主要用于内存块的合并操作。
空闲的chunk：
说明： 1.6 空闲链表bins用户free掉的内存，ptmalloc并不会马上还给os，而是用空闲链表bins管理起来了，这样当下次malloc一块内存时，ptmalloc会直接从bins上寻找一块合适大小的内存块分配给用户使用。这样的好处可以避免频繁的系统调用，降低内存分配的开销。
ptmalloc按chunk的大小将bins分成四类：fast/unsorted/small/large bins。 fast bins：
unsorted/small/large bins的高速缓冲区，大约有10个定长队列。每个fast bin都存储着一条空闲chunk的单链表，增删chunk都发生在链表的前端。
当用户释放一块不大于max_fast（默认值64B）的chunk时，会默认会被放到fast bins上。当需要给用户分配的 chunk <= max_fast时，malloc首先会到fast bins上寻找是否有合适的chunk。
 unsorted bins：
bins 数组的第一个元素，用于加快分配速度。当用户释放的内存大于max_fast或fast bins合并后的chunk都会首先插入unsorted bin中； small bins：
小于512字节的chunk称为small chunk，而保存small chunks的bin被称为small bin。small bin存储在bins数组第2个至第65个位置，前后两个bin相差8个字节，同一个bin中的chunk大小相同。 large bins：
大于等于512字节的chunk称为large chunk，而保存large chunks的bin被称为large bin。large bin位于small bins后面。每一个large bin包含了给定范围内的chunk，large bin内的chunk按先大小后最近使用时间递减排序。
并不是所有chunk都按以上四种方式进行组织，以下两种情况例外： Top chunk：
分配区的顶部空闲内存，当所有的bins上都不能满足内存分配要求时，就会使用top chunk进行分配。
若Top chunk的大小大于用户请求的内存大小时，则分割top chunk成两部分：User chunk（用户请求大小）和Remainder chunk（剩余大小）。其中Remainder chunk将成为新的Top chunk；
当Top chunk的大小小于用户请求的内存大小时，则通过sbrk（main arena）或mmap（thread arena）系统调用来扩容Top chunk。 mmaped chunk：
当用户请求的内存非常大（大于分配阀值，默认128K）时，需被mmap映射，则会放到mmaped chunk上，当释放mmaped chunk上的内存的时候会直接还给os。
1.7 内存分配锁定一个分配区，防止多线程冲突； 将用户请求分配的内存大小向上取整到class_size； 若class_size < max_fast（64B），则检查fast bins是否存在适合的chunk。存在则分配结束，否则继续； 运行到此步，说明fast bins上未有合适的chunk或class_size > 64B且class_size<512B，则检查small bins是否存在合适的chunk。存在则分配结束，否则继续； 遍历fast bins，将相邻的chunk合并后链接到unsorted bin中。
若unsorted bins中只有一个chunk且大于class_size，则切割并将剩余chunk重新放回unsorted bins；
若unsorted bins中有class_size大小的chunk，则从unsorted bins删除并返回；
若unsorted bins中的chunk属于small bins的范围，则插入small bins的头部；
若unsorted bins中的chunk属于large bins的范围，则插入large bins。 运行到此步，说明fast/unsorted/small bins都不满足分配要求，则从large bins中查找找到合适的chunk进行切割，一部分分配给用户，剩下的放入unsorted bin中； 运行到此步，说明fast/unsorted/small/large bin都不满足分配要求，则检查Top chunk：
若Top chunk的大小大于用户请求的内存大小时，则分割top chunk成两部分：User chunk（用户请求大小）和Remainder chunk（剩余大小）。其中Remainder chunk将成为新的Top chunk；
当Top chunk的大小小于用户请求的内存大小时，则通过sbrk（main arena）或mmap（thread arena）系统调用来扩容Top chunk。
1.8 内存回收获取待释放内存所属的分配区，若该分配区已被其他线程锁定，则等待； 根据chunk的M标识判断该chunk是否由mmap映射的内存。是，则直接使用unmmap()释放，否则继续； 判断chunk释放与Top chunk相邻。是，则与Top chunk合并跳转到6），否则继续； 若chunk > max_fast（64B），则插入unsorted bin，并且检查是否有合并，有合并情况并且和Top chunk相邻，则转到步骤8； 若chunk < max_fast（64B），则插入fast bin。
插入后若当前chunk的下一个chunk也是空闲的，则合并后插入unsorted bin。若合并后的大小 > 64B，则触发fast bins的合并操作：遍历fast bins，将相邻的空闲chunk合并病插入unsorted bin中，fast bin会变为空。（若合并后的chunk与Top chunk相邻，则与Top chunk合并。） 判断Top chunk是否大于mmap收缩阈值（默认为128KB）。是，则将Top chunk中的一部分还给os。
二、 tcmalloc2.1特点2.2 多级缓存池PageHeap：
 CenterCache：
 ThreadCache：
 由若干个链表组成； 同一个链表中节点大小相同，不同链表按8k、16k、32K、48K、……、256K分类； ThreadCache的内存来源于CenterCache； TheadCache为线程的私有线程池，不需要加锁；
2.3 内存分配tcmalloc将内存分为3类： 小对象：(0, 256K]； 中对象：(256k, 128Page]； 大对象：(128Page, -)
对于小对象，按8k、16k、32K、48K、……、256K等class_size分类，为了避免内存碎片，它们之间并不是成简单的2的幂次方关系。分配内存时，采用向上取整方式，即申请1-7字节都会被分配一块8字节内存。这是因为若采用2的幂次方，则当申请33字节时，会被分配一块64字节内存，从而导致50%的内存碎片。 小对象内存分配： 假设申请的内存大小为size，将size向上取整到class_size； 检查ThreadCache class_size对应的链表是否为空。否，则取出一个节点作为分配结果，否则继续； 检查CenterCache class_size对应的链表是否为空。否，则为了平摊锁的开销，会一次性取出若干个节点，一个作为分配结果，剩余的存储到ThreadCache中；否则继续； 将class_size向上取整到NPage。N的取值为：(NPage-Mclass_size)/(NPage)<=1/8，通过这种方法可以将内存碎片控制在12.5%。 遍历PageHeap从NPage至128Page的链表，检查是否有大于NPage的节点。是，假设节点大小为MPage，则将MPage切割成N*Page和(M-N)*Page两部分，前一部分按class_size分割后存储到CenterCache，后一部分插入到HeapPage中(M-N)*Page的链表中，否则继续； 若PageHeap不为空，则取出一个节点，假设为MPage，切割成NPage和(M-N)*Page两部分前一部分按class_size分割后存储到CenterCache，后一部分若大于128Page，则重新插入集合，否则插入到HeapPage中(M-N)*Page的链表中，否则继续； 使用mmap/sbrk向os申请内存； 中对象内存分配与小对象类似，区别在于不会查找ThreadCache/CenterCache，而是直接检索PageHeap链表，链表分配失败，则继续查找PageHeap集合，之后再直接向os申请。 大对象内存分配则直接检索PageHeap集合，分配失败后，直接向os申请。
2.4 内存回收若释放的内存大于1*Page，则插入到PageHeap中，否则继续； 将内存插入到ThreadCache链表中，若插入后链表长度超过阈值，则将若干个节点插入到CenterCache的链表中； 若CenterCache链表长度超过阈值，则合并后插入到PageHeap；
三、 jemalloc3.1 特点减少多线程竞争。采用多个arena管理内存并与线程绑定（small/large都由arena分配），当线程数不超过arena数时，可保证各线程独占一个arena。由于arena之间不存在地址关联，因此此时线程之间不存在锁竞争。当线程数超过arena数时，存在多个线程共享一个arena，此时可通过arena内部的锁机制进行同步； 各线程都有自己的tcache，可避免多线程同步； 地址空间重用，减少碎片。释放的内存会首先存入tcache，同时在一定的条件下可与相邻的空闲空间合并，并归还给arena或os； 使用了红黑树等策略实现低地址优先（总是从低地址开始分配），以降低内存碎片化； jemalloc大概需要2%的额外开销（tcmalloc 1%，ptmalloc最少8B）。
3.2 内存结构
3.3 class size为了减少内存碎片及快速定位到合适大小的内存，jemalloc将run按以下class_size分成44类（同一个run下的region大小相同）： small（<4K）: [8], [16, 32, 48, …, 128], [192, 256, 320, …, 512], [768, 1024, 1280, …, 3840] large（4K-4M）: [4K, 8K, 12K, …, 4072K] huge（>4M）: [4M, 8M, 12M, …]
对于小于4K内存的申请，jemalloc直接向上取整到最小的class_size，例如申请1-7字节，都会分配一个8字节内存。
3.4 arena
jemalloc将内存划分成若干个arena，并采用一个动态指针数组“arena_t **arenas”来存储所有的arena，其中arena结构如下：
struct arena_s
{
unsigned ind; //当前arena在arenas数组中的索引
unsigned nthreads; //已绑定的线程数
malloc_mutex_t lock; //锁同步，绑定线程（修改nthreads）、新增chunk/run是需要加锁
ql_head(tcache_t) tcache_ql; //ring queue, 存储于了所有与当前arena绑定的线程的tcache
arena_chunk_tree_t chunks_dirty; //红黑树, 节点为含有dirty page的chunk（dirty：已被分配）
arena_chunk_t *spare; //存储最近一次被释放的chunk，当需要创建一个新chunk时, 首先会检索spare, 由此提高频繁分配释放而可能导致chunk利用率下降的问题
size_t nactive; //当前arena中正在使用的page数
size_t ndirty;
size_t npurgatory;
arena_avail_tree_t runs_avail; //红黑树, 记录所有空闲的runs（run被释放后，会存储在这里）
chunk_alloc_t *chunk_alloc;
chunk_dalloc_t *chunk_dalloc;
arena_bin_t bins[NBINS]; //记录各small class_size中non-full runs的使用情况
}; arena_bin_s 结构： struct arena_bin_s
{
malloc_mutex_t lock;
arena_run_t *runcur; //当前可用于分配的run, 一般情况下指向地址最低的non-full run, 同一时间一个bin只有一个current run用于分配
arena_run_tree_t runs; //记录当前arena中该bin对应small class_size的所有non-full runs。因为分配是通过current run完成的, 所以也相当于current run的仓库
malloc_bin_stats_t stats;
}; 3.5 chunk与run
chunk header结构：
struct arena_chunk_s
{
arena_t *arena; //属于哪个arena
rb_node(arena_chunk_t) dirty_link; //若该chunk含有dirty page，则该node挂载到红黑树arena.chunks_dirty中
size_t ndirty; //含有的dirty page数量
size_t nruns_avail; //内部available runs数量
size_t nruns_adjac;
arena_chunk_map_t map[1]; //动态数组, 指向并记录内部各page状态：unallocated（还未建立run的page）和small/large(该page所属run的类型为small/large)三类
} run header结构： struct arena_run_s
{
arena_bin_t *bin; //所属的bin
uint32_t nextind; //下一个clean region的索引
unsigned nfree; //当前空闲region数量
map; //指向并记录内部各region的状态
} 3.6 Thread caches (tcache_t)
线程的私有存储空间，其内部保存的仅仅是指向外部region的指针, region对象仍存储于各run当中。 换句话说, 如果一个region被tcache记录了, 那么从run的角度看, 它就已经被分配了。
tcache头结构：
struct tcache_s
{
ql_elm(tcache_t) link; //链接节点，用于将同一个arena下的所有tcache链接起来
uint64_t prof_accumbytes;
arena_t *arena; //指向所属的arena
unsigned ev_cnt; //周期计数器。tcache每执行一次分配/释放, ev_cnt记录一次，当周期到来时, jemalloc会清理tcache中多余的region, 将它们归还给run，以便交给其他更饥饿的线程以分配使用
unsigned next_gc_bin; //指向下一次gc的binidx. tcache gc按照一周期清理一个bin执行
tcache_bin_t tbins[1]; //动态数组
}; tcache bin结构： struct tcache_bin_s
{
tcache_bin_stats_t tstats;
int low_water;
unsigned lg_fill_div; //跟cache refill有关，当tcache耗尽时, 会请求arena run进行refill。
unsigned ncached; //当前空闲的region数量
void **avail; //保存region指针的stack, 称为avail-stack
} 3.7 内存分配
假设请求分配的内存大小为size：
将size向上取整到class_size； 若class_size > 4M，则跳转到6； 检查当前线程是否已绑定arena，若未绑定，则选择并绑定一个arena。
如何选择arena？ 遍历指针数组arenas，检查是否存在未被任何线程绑定的arena。有，则与当前线程绑定，否则继续； 检查已创建的arena总数是否超过最大阈值（阈值跟cpu核数有关，初始状态只有一个arena）。否，则新增一个arena，在与当前线程绑定后存入数组arenas；否则继续； 将当前线程与绑定的线程数最少的arena绑定；
注：
当线程数 <= area数时，可以保证每个线程都能独占一个area，而由于两个arena在地址空间上几乎不存在任何联系, 故此时可以避免多线程竞争；
当线程数 > area数时，则会出现多个线程绑定同一个arena，此时线程之间的内存分配需要加锁。 若class_size < 4K： 检查线程私有存储空间tcache.tbins[class_size]是有空闲region，有则取出栈顶节点作为分配结果，否则继续； 尝试从arena.bins[class_size].runs获取new run。若获取失败，则继续，否则跳转到5）； 尝试从arena.runs_avail上获取一个new run。若获取失败，则继续，否则跳转到5）； 构造一个新的chunk并分割成若干个new run，其中一个作为本次使用，剩余的存储到arena.runs_avail中； 在使用new run之前, 再次检查当前bin的runcur是否可用（这里有两种可能，一是其他线程可能通过free释放了多余的region/run, 另一种是其他线程抢在当前线程之前分配了新run）。若runcur可用且new run是空，则释放new run；若runcur可用且new run不为空且其地址低于runcur, 则交换二者, 并将runcur插入arena.runs_avail；否则继续； 在new run中分配若干region，其中一个作为分配结果，其余的挂载在tcache.tbins[class_size].avail下作为下次使用； 若class_size > 4K且class_size < 4M： 检查线程私有存储空间tcache.tbins[class_size]是否空闲region。有则直接分配，否则继续； 从从arena.runs_avail上获取一个new run。若获取成功，则切割一块class_size作为分配结果（不会分配多块填充tcache.tbins），剩余部分放回arena.runs_avail，否则继续； 分配一个新的chunk，分割，剩余部分放回arena.runs_avail； 通过mmap分配；
3.8 内存回收对于所有small/large的region，会直接插入到线程私有存储空间tcache_t.tbins[class_size]的栈顶（为了保持region的热度，保证下次最先被分配出去）； 当tcache_t.tbins[class_size]满载时，需要将栈底的N个region放回到run内，即将arena_chunk_s.map对应位置标记为空闲，然后将剩余部分整体移到栈低（为了保持cache热度）； 将tcache_t.tbins[class_size]中的region塞回run后，若塞入之前该run已没有剩余region，则塞入之后需要将该run插入所属的bin中，即arena_bin_s.runs；若塞入之后，整个run都为空闲，则需将其从所属的arena_bin_s.runs移除，并插入到arena.runs_avail； 在3）中将run释放后，会与相邻的空闲run合并，若整个chunk都空闲，则需要将chunk插入到arena.spare中。若arena.spare已有chunk，则插入前需要将旧chunk移除并释放其物理内存；
4、测试4.1 官方测试
服务器吞吐量分别用6个malloc实现的对比数据，可以看到tcmalloc和jemalloc最好。
4.2 本地测试通过不同线程，测试并发能力；通过随机分配，测试不同大小的分配速度。只测试malloc，因为申请后马上释放，再申请，可能会复用前一次的内存（释放给系统后，不会马上归还到虚拟/物理内存）。 4.2.1 单线程单线程随机分配100-150字节：
单线程随机分配1K-2K：
4.2.2 2线程2个线程随机分配100-150字节：
2个线程随机分配1K-2K：
4.2.3 4线程4个线程随机分配100-150字节：
4个线程随机分配1K-2K：
4.2.4 8线程8个线程随机分配100-150字节：
8个线程随机分配1K-2K：
4.2.5 ptmalloc内存泄漏测试伪代码： for(int I = 0; I < num; ++i)
{
p[i] = alloc(***);
}
//for(int I = 0; I < num - 1; ++i) //全部释放
for(int I = 0; I < num - 1; ++i) //最后一块不释放
{
free(p[i]);
}
4.2.6 tcmalloc内存泄漏malloc后free全部内存：
free之后，使用api：ReleaseFreeMemory（）回收：
最后一块不free后使用api回收：
4.2.6 jemalloc内存释放分配测试free前一半，再free后一半：
allocated：应用程序分配的字节总数； active：应用程序分配的活动页面中的字节总数（默认为每页4 KB）。 这是页面大小的倍数，并且大于或等于allocated； mapped：映射的活动块中的字节总数（默认为每块4MB）。 这是块大小的倍数，并且大于JeMalloc活动字节。
|
