1. 系统结构

系统下经典内存布局如上，程序起始的1GB地址为内核空间，接下来是向下增长的栈空间和向上增长的mmap地址。而堆地址是从底部开始，去除ELF、数据段、代码段、常量段之后的地址并向上增长。纵观各种内存布局，对于大内存各种malloc基本上都是直接mmap的。而对于小数据，则通过向操作系统申请扩大堆顶，这时候操作系统会把需要的内存分页映射过来，然后再由这些malloc管理这些堆内存块，减少系统调用。而在free内存的时候，不同的malloc有不同的策略，不一定会把内存真正地还给系统，所以很多时候，如果访问了free掉的内存，并不会立即Run Time Error，只有访问的地址没有对应的内存分页，才会崩掉。

1.1. ptmalloc (glibc 的malloc实现)

1.1.1. 小内存分配与释放

在ptmalloc中采用chunk进行小内存管理，并且把相似（相同）大小的chunk组织在一个链表中进行维护，这个链表叫做bin。前64个bin中组织的chunk大小按8个字节递增，这一块叫做 small_bin。之后的就是large_bin, large_bin中的chunk是先按size，size相同则按照最近使用时间排列，这样要搜索一个可用的内存时，就在bins里按大小搜索，返回一个最小可用的chunk。

chunk结构如下图所示。可以理解成链表中一个node。存储了上一个相邻的chunk的大小以及flag，还有下一个chunk的“指针”。 flag A 表示是不是在主分配去，M表示是否是mmap得到的， P表示上一个chunk是否在使用中。

在free的时候，ptmalloc会检查附近的chunk，如果标志位为P，即空闲中，会尝试把连续空闲的chunk合并成一个大的chunk，放到unstored bin里。但是当很小的chunk释放的时候，ptmalloc会把它并入fast bin中。同样，某些时候，fast bin里的连续内存块会被合并并加入到一个unsorted bin里，然后再才进入普通bin里。所以malloc小内存的时候，是先查找fast bin，再查找unsorted bin，最后查找普通的bin，如果unsorted bin里的chunk不合适，则会把它扔到bin里。

1.1.2. 大内存分配与释放

ptmalloc的分配的内存顶部还有一个top chunk，如果前面的bin里的空闲chunk都不足以满足需要，就是尝试从top chunk里分配内存。如果top chunk里也不够，就要从操作系统里拿了，这样会造成heap增大。

还有就是特别大的内存，会直接从系统mmap出来，不受chunk管理，这样的内存在回收的时候也会munmap还给操作系统。

1.1.3. ptmalloc 使用总结

1.1.3.1. ptmalloc

小内存：（相当于实现了自身的cache，速度快）

分配：[获取分配区(arena)并加锁] -> fast bin -> unsorted bin -> small bin -> large bin -> top chunk -> 扩展堆（brk分配）
释放：brk分配的内chunk list，只能从top开始线性向下释放。释放掉中间的chunk，无法归还给OS（内存孔洞），而是并链入到了bins/fast bins的容器中。

大内存：（与os直接打交道，速度慢）

分配：mmap从操作系统获得
释放：munmap归还给操作系统

1.1.3.2. 人为控制：

大内存和小内存的界限： mallopt（）函数可以调整threshold，大于此threshold的用mmap分配，小于此值的用brk缓存技术分配。

mallopt(M_MMAP_MAX, 0); // 禁止malloc调用mmap分配内存
mallopt(M_TRIM_THRESHOLD, 0); // 禁止内存缩进，sbrk申请的内存释放后不会归还给操作系统

如上的code相当于实现了一个内存池功能，这个会持续到线程结束才把内存归还给操作系统。

M_MMAP_THRESHOLD 的设置是多大算大内存，多大算小内存的设置 M_TRIM_THRESHOLD heap顶部攒到多大归还给操作系统，0则是不归还给操作系统

手动shrink heap：使用malloc_trim（）根据man手册的解释，它应该是负责告诉glibc在brk维护的堆队列中，堆顶留下多少的空余空间（free space），其他往上的空余空间全部归还给系统。

手动设置每个线程的arena数量：mallopt(M_ARENA_MAX, 1) ，设置为0则为系统自动设置。

1.1.3.3. 经验教训：

ptmalloc默认后分配内存先释放，因为内存回收是从top chunk开始的。

避免多线程频繁分配和释放内存，会造成频繁加解锁。

不要分配长生命周期的内存块，容易造成内碎片，影响内存回收。

对于动态增长STL容器，要注意它维护的队列却是分配在heap上的。也就是说一个这样的临时对象所操作过的内存，依然可能产生碎片。如果这样的函数被频繁调用，碎片就会非常多。尽量成批reserve一块内存使用。减少在容器已满的情况下仍然push_back单个元素的操作，这样非常容易产生碎片。

即便我们做过shrink_to_fit的工作（std::vector<t*>(v).swap(v)），如果里面是碎片，那也会被驻留在brk维护的free_list中，不会被释放。

长时间的线上服务更应该注重编码习惯，尽量减少内存碎片。

每个线程至少有一个，至多有cores_num*8个自己的arena（看成by线程的内存池），减少锁的使用。不同arena之间不能交替使用。多尝试arena数目的设置，对虚拟内存的消耗有挺大的影响。

#include <malloc.h>
malloc_trim(0);

1.2. tcmalloc（google的实现）

http://goog-perftools.sourceforge.net/doc/tcmalloc.html

Tcmalloc是Google gperftools里的组件之一。全名是 thread cache malloc（线程缓存分配器）。tcmalloc正是通过thread cache这种机制实现了大多数情况下的无锁内存分配。优势如下：

速度快：号称比ptmalloc2.0速度快（tc 50纳秒情况下 pt需要300纳秒）。也号称github因为使用tcmalloc，性能提高了30% 减少锁争用：TCMalloc减少了多线程程序中的锁争用情况。对于小对象，几乎已经达到了零争用。对于大对象，TCMalloc尝试使用粒度较好和有效的自旋锁。省内存：分配N个8字节对象使用大约8N * 1.01字节的空间。而ptmalloc2中每个对象都使用了一个四字节的头。跨线程归还：尽管ptmalloc2也实现了per-thread缓存，第一个线程申请的内存，释放的时候还是必须放到第一个线程池中（不可移动），这样可能导致大量内存浪费。tcmalloc跨线程归还内存，是因为所有线程公用了底层的一个分配器，所以跨线程归还是无需加锁的。 tcmalloc与大多数现代分配器一样，使用的是基于页的内存分配，也就是说，这种内存分配的内部度量单位是页，而不是字节。这种内存分配可以有效地减少内存碎片，同时，也可以增加局部性。此外，也可以使得元数据的跟踪更为简单。tcmalloc定义一页为8K字节，在大多数的linux系统中，一页是4K字节，也就是tcmalloc的一页是linux的两页。 tcmalloc中的内存分配块整体来说分为两类，“小块”和“大块”，“小块”是小于kMaxPages的内存块，“小块”可以进一步分为size classes，而且“小块”的内存分配是通过thread cache或者central per-size class cache而实现。“大块”是大于等于kMaxPages的内存块，“大块”的内存分配是通过central PageHeap实现。

1.2.1. 小内存分配

对于小块内存分配，其内部维护了60个不同大小的分配器（实际源码中看到的是86个），和ptmalloc不同的是，它的每个分配器的大小差是不同的，依此按8字节、16字节、32字节等间隔开。在内存分配的时候，会找到最小复合条件的，比如833字节到1024字节的内存分配请求都会分配一个1024大小的内存块。如果这些分配器的剩余内存不够了，会向中央堆申请一些内存，打碎以后填入对应分配器中。同样，如果中央堆也没内存了，就向中央内存分配器申请内存。

在线程缓存内的分配器中分别维护了一个大小固定的自由空间链表，直接由这些链表分配内存的时候是不加锁的。但是中央堆是所有线程共享的，在由其分配内存的时候会加自旋锁(spin lock)。

小内存分配的步骤如下：

把所需的小内存map到相应的size-class（如833则到1024在的class区操作）；在这个线程的cache内相应的size-class中的free list寻找；如果这个free list不为空（即有相应的可分配内存），删除list的头结点并返回这个头结点（整个过程在by 线程的cache中，不需要加锁，速度非常快，加锁解锁至少消耗100纳秒）如果free list为空（这个size的缓存内存都被分配完了），则去central heap中的central free list中的相应size class中寻找如果central free list 不为空，把这块内存（申请了n个这个大小）放到thread local的free list, 并返回这个list的头结点，剩下n-1个在thread-local的free list中如果central free list为空，向central page allocator申请m个内存页->按照所需要的size分割->放入central free list ->按照5放入 thread local 的free list 在线程内存池每次从中央堆申请内存的时候，分配多少内存也直接影响分配性能。申请地太少会导致频繁访问中央堆，也就会频繁加锁，而申请地太多会导致内存浪费。在tcmalloc里，这个每次申请的内存量是动态调整的，调整方式使用了类似把tcp窗口反过来用的慢启动（slow start）算法调整max_length，每次申请内存是申请min(max_length,每个分配器对应的num_objects_to_move)个数的内存块。

num_objects_to_move取值:以64K为基准，并且最小不低于2，最大不高于32的值。也就是说，对于大于等于32K的分配器这个值为2（好像没有这样的分配器 class），对于小于2K的分配器，统一为32。其他的会把数据调整到64K / size 的个数。

对于max_length取值：其更多是用于释放内存。max_length由1开始，在其小于num_objects_to_move的时候每次累加1，大于等于的num_objects_to_move 累加1。释放内存的时候，首先max_length会对齐到num_objects_to_move，然后在大于num_objects_to_move的释放次数超过一定阀值，则会按num_objects_to_move缩减大小。

1.2.2. 大内存分配

对于大内存分配(大于8个分页, 即32K)，tcmalloc直接在中央堆里central page free lists分配。中央堆的内存管理是以分页为单位的，同样按大小维护了256个空闲空间链表central list，前255个分别是1个分页、2个分页到255个分页的空闲空间，最后一个是更多分页的小的空间。这里的空间如果不够用，就会直接从系统申请了。

1.2.3. 资源释放

TCMalloc管理的堆中有很多分页。连续的分页由一种叫span得对象来表示。span的状态有allocated和free两种。如果是free，这个span对象会被page heap linked-list 记录。如果是allocated，他要么是作为大对象分配，或作为小对象分配（这时候span内记录了小对象的class size）。 page的编号可以用来判断每个page属于哪个span。如下图span a占有两个分页，b占有1个，c占有5个，d占有三个。

在32位系统中，span分为两级由中央分配器管理。第一级有2^5个节点，第二级是2^15个。32位总共只能有2^20个分页（每个分页4KB = 2^12）。64为中有三级管理。

释放某个object
找到该object所在的span
如果是小对象，归入小对象分配器的空闲链表，如果空闲空间大于指定预置则归还给central free list; 如果是大对象，则会把物理地址连续的前后的span也找出来，如果空闲则合并，并归入central free list。

4 central list也会试图通过释放可用span列表的最后几个span来将不用的空间归还给OS

1.2.4. tcmalloc使用总结

1.2.4.1. tcmalloc的分配与释放

1.2.4.1.1. 小内存：

分配：先向thread cache请求，资源不足则向central heap请求，再资源不足则由central heap向os请求释放：找资源所在的页，找到span，归入thread local的free list，如果空闲够大，归还给central list；如果central free list 能合并成一个空的span，则归还给central page free list

1.2.4.1.2. 大内存：

分配：先向central heap(central page free list)请求，资源不足则由central page alloctor向os请求释放: 找到资源所在页，找到span，尝试前后合并成更大的free span，归还给central page free list

1.2.4.1.3. 一点感想：

由于tcmalloc可以跨线程的把释放小内存的资源归还到central free list中，glibc中频繁分配释放带来的内存碎片问题应该可以一定程度的得以改善 tcmalloc每个线程默认最大缓存16M空间，所以当线程多的时候其占用的空间还是非常可观的（可能会缓存比glibc更多的内存），在common.h中有几个参数是控制缓存空间的，可以做合理的修改：

降低每个线程的缓存空间，可以修改common.h中的kMaxThreadCacheSize，比如2M

尽快将free的空间还给central list，可以将kMaxOverages改小一点，比如1

降低所有线程的缓存空间的总大小，可以修改common.h中的kDefaultOverallThreadCacheSize，比如20M

还可以定期让tcmalloc归还空间给OS

#include "google/malloc_extension.h" 
MallocExtension::instance()->ReleaseFreeMemory();

1.3. Jemalloc(facebook的实现）

https://www.facebook.com/notes/facebook-engineering/scalable-memory-allocation-using-jemalloc/480222803919/

首先介绍一下jemalloc中的几个核心概念

arena。jemalloc的核心分配管理区域，对于多核系统，会默认分配4*cores的Arena，线程采取轮询的方式来选择相应的arena来进行内存分配。

chunk。具体进行内存分配的区域，目前的默认大小是4M。chunk以page（默认为4K)为单位进行管理，每个chunk的前几个page（默认是6个）用于存储后面所有page的状态，比如是否待分配还是已经分配；而后面的所有page则用于进行实际的分配。

bin。用来管理各个不同大小单元的分配，比如最小的Bin管理的是8字节的分配，每个Bin管理的大小都不一样，依次递增。jemalloc的bin和ptmalloc的bin的作用类似。

run。每个bin在实际上是通过对它对应的正在运行的Run进行操作来进行分配的，一个run实际上就是chunk里的一块区域，大小是page的整数倍，具体由实际的bin来决定，比如8字节的bin对应的run就只有1个page，可以从里面选取一个8字节的块进行分配。在run的最开头会存储着这个run的信息，比如还有多少个块可供分配。

tcache。线程对应的私有缓存空间，默认是使用的。因此在分配内存时首先从tcache中找，miss的情况下才会进入一般的分配流程。

Jemalloc 把内存分配分为了三个部分，第一部分类似tcmalloc，是分别以8字节、16字节、64字节等分隔开的small class；第二部分以分页为单位，等差间隔开的large class；然后就是huge class。内存块的管理也通过一种chunk进行，一个chunk的大小是2^k (默认4M)。通过这种分配实现常数时间地分配small和large对象，对数时间地查询huge对象的meta（使用红黑树）。默认64位系统的划分方式如下：

Small: [8], [16, 32, 48, …, 128], [192, 256, 320, …, 512], [768,1024, 1280, …, 3840]  （1-57344分为44档）
Large: [4 KiB, 8 KiB, 12 KiB, …, 4072 KiB]  （58345-4MB）
Huge: [4 MiB, 8 MiB, 12 MiB, …]  （4MB的整数倍）

内存分配 jemalloc 的内存分配，可分成四类：

small( size < min(arena中得bin) ):如果请求size不大于arena的最小的bin，那么就通过线程对应的tcache来进行分配。首先确定size的大小属于哪一个tbin，比如2字节的size就属于最小的8字节的tbin，然后查找tbin中有没有缓存的空间，如果有就进行分配，没有则为这个tbin对应的arena的bin分配一个run，然后把这个run里面的部分块的地址依次赋给tcache的对应的bin的avail数组，相当于缓存了一部分的8字节的块，最后从这个availl数组中选取一个地址进行分配；

large( max(tcache中的块) > size > min(arean中的bin) ): 如果请求size大于arena的最小的bin，同时不大于tcache能缓存的最大块，也会通过线程对应的tcache来进行分配，但方式不同。首先看tcache对应的tbin里有没有缓存块，如果有就分配，没有就从chunk里直接找一块相应的page整数倍大小的空间进行分配（当这块空间后续释放时，这会进入相应的tcache对应的tbin里）；

large( chunk > size > tcache ): 如果请求size大于tcache能缓存的最大块，同时不大于chunk大小（默认是4M），具体分配和第2类请求相同，区别只是没有使用tcache；

huge(size> chunk ):如果请求大于chunk大小，直接通过mmap进行分配。

简而言之，就是：小内存（small class）：线程缓存bin -> 分配区bin(bin加锁) -> 问系统要中型内存（large class）：分配区bin(bin加锁) -> 问系统要大内存（huge class）：直接mmap组织成N个chunk+全局huge红黑树维护(带缓存)

内存释放回收流程大体和分配流程类似，有tcache机制的会将回收的块进行缓存，没有tcache机制的直接回收（不大于chunk的将对应的page状态进行修改，回收对应的run；大于chunk的直接munmap）。需要关注的是jemalloc何时会将内存还给操作系统，因为ptmalloc中存在因为使用top_chunk机制（详见华庭的文章）而使得内存无法还给操作系统的问题。目前看来，除了大内存直接munmap，jemalloc还有两种机制可以释放内存：

   1.   当释放时发现某个chunk的所有内存都已经为脏（即分配后又回收）就把整个chunk释放；
   2.   当arena中的page分配情况满足一个阈值时对dirty page进行purge（通过调用madvise来进行）。这个阈值的具体含义是该arena中的dirty page大小已经达到一个chunk的大小且占到了active page的1/opt_lg_dirty_mult（默认为1/32）。active page的意思是已经正在使用中的run的page，而dirty page就是其中已经分配后又回收的page。