开发c++应用可能第一步就是内存管理了，所以我们第一个就说下内存管理。
c++内存，主要的效率瓶颈就是大量小内存的分配问题了，为了解决这个问题，首先想到的就是每次分配一大块内存（比如1M），然后再这块大内存上再去分配给程序使用，这是就不需要频繁的调用系统的内存分配了，同时减少了内存碎片的产生。另外，我们设计内存保持16字节对齐，一方面可以很好的解决多平台的内存对齐问题，另一方面能相应的提高内存的访问速度。
所以，我们会分为两部分进行内存分配，一部分是小内存，以16字节为基础按倍数递增，16、32、48、64、80、96、112、128，128一共8级作为小内存的最小分配单位叫做chunk（比如要分配9个字节，会分配16字节的chunk，要分配78字节就分配80字节的chunk），每一个不同大小的chunk会有一个独立的内存池MemoryPool，所以我们会有8个不同的MemoryPool，每次在分配内存时，比如调用malloc，我们会重载malloc，在函数中判断需要分配内存大小的等级如果是小内存，就调用相应MemoryPool上的malloc函数分配，在分配时每次会分配一个大块内存（如1M）叫block，再在block上分配相应的chunk。如果要分配的内存大于128字节，就直接分配内存，因为分配的内存已经足够大了，分配的内存也是一个chunk。
数据结构如下
MemoryPool
const size_t chunkSize; // chunk的大小，如16、32等
const size_t blockSize; // block大小， 如1M
void* blockNode; // 分配的block链表
void* freeBlockNode; // 空闲的block链表
U32 totalChunkCount; // 一共可以分配的chunk数量
U32 allocatedChunkCount; // 已经分配的chunk数量
volatile long lock; // 原子锁使用的计数器
Block
MemoryPool* const memoryPool; // 属于那个内存池
const size_t chunkSize; // chunk大小，包括chunk头信息的大小
U32 allocatedChunkCount; // 已经分配的大小
U8* startAddr; // chunk的开始地址
U8* endAddr; // chunk的结束地址
U8* freeAddr; // chunk的可分配地址
Chunk* freeChunk; // 空闲的chunk链表，block上一个chunk被释放就会放入这个链表，分配chunk时优先检查这个链表
__declspec(align(16)) Chunk
DebugInfo info; // debug信息，包括地址、callstack等信息，在chunk分配时放入一个检测的全局链表，释放时从全局链表删除，程序结束时检查全局链表是否为空，不为空就是内存泄漏，显示相应信息。数据较多，只在Debug内存是使用
union
{
Block* block; // 如果chunk已经分配时使用，用来标识属于哪个Block，再通过block可以找到相应MemoryPool进行操作，如果为空，就是直接分配的大内存
Chunk* nextChunk; // 如果chunk已经释放并放入了block的freeChunk链表时使用，用来标识下一个空闲的chunk
};
MemoryPool分配chunk时，会先查找freeBlockNode，如果有直接在这个block上分配，如果没有则创建一个新的block并添加到blockNode和freeBlockNode。block分配chunk时，会优先查找freeChunk，如果有直接返回这个chunk，并在freeChunk中删除这个chunk，如果没有则在freeAddr后分配chunk，并将freeAddr向后偏移chunkSize，同时判断block是否已经满了，即
freeAddr + chunkSize > endAddr && freeChunk == null
如果满了，则在MemoryPool的freeBlockNode上删除这个block。
所有返回的chunk地址都是偏移了chunk头大小的，这个地址需要获取chunk信息时直接向前偏移一个chunk头大小即可。
chunk释放时，如果chunk头为空，则是大内存直接释放，如果不是就从中取出block并找到MemoryPool在上面进行释放。
MemoryPool释放chunk时，就是在相应的block上把这个chunk添加到freeChunk中即可，同时如果block不在MemoryPool的freeBlockNode，就把block添加到上面。如果block的allocatedChunkCount为0就说明这个block上的chunk已经完全释放，这时可以判断MemoryPool上面
totalChunkCount- allocatedChunkCount) * chunkSize
是否大于一个阈值比如两倍的blockSize，如果是的话可以删除这个block，同时从blockNode和freeBlockNode移除它。
为了debug内存检测内存泄漏，在debug模式下会在chunk的头上添加debug节点信息，包括地址和callstack等相关信息，在分配chunk时添加到全局的检测链表中，在释放chunk时从全局链表删除，到程序结束时，检查这个全局链表如果不为空，就说明存在内存泄漏，可以打印相关信息。因为相关数量比较大，而且计算时间较长，会比较大的影响内存占用和运行效率，所以只在内存debug时使用。
下面再来看一下主流的一些内存分配的库，介绍来自其他文章。
glibc的ptmalloc
有一个主分配区(main arena)， 有多个非主分配区。 非主分配区只能使用mmap向操作系统批发申请HEAP_MAX_SIZE（64位系统为64MB）大小的虚拟内存。 当某个线程调用malloc的时候，会先查看线程私有变量中是否已经存在一个分配区，如果存在则尝试加锁，如果加锁失败则遍历arena链表试图获取一个没加锁的arena， 如果依然获取不到则创建一个新的非主分配区。
free()的时候也要获取锁。分配小块内存容易产生碎片，ptmalloc在整理合并的时候也要对arena做加锁操作。在线程多的时候，锁的开销就会增大。
用户请求分配的内存在ptmalloc中使用chunk表示， 每个chunk至少需要8个字节额外的开销。用户free掉的内存不会马上归还操作系统，ptmalloc会统一管理空闲chunk，避免了频繁的系统调用。将相似大小的 chunk 用双向链表链接起来, 这样的一个链表被称为一个 bin。Ptmalloc 一共 维护了 128 个 bin,并使用一个数组来存储这些 bin。
数组中的第一个为 unsorted bin, 数组中从2开始编号的前 64个bin称为small bins, 同一个small bin中的chunk具有相同的大小。small bins后面的bin被称作large bins。当free一个chunk并放入bin的时候， ptmalloc还会检查它前后的chunk是否也是空闲的, 如果是的话,ptmalloc会首先把它们合并为一个大的 chunk, 然后将合并后的chunk放到unstored bin中。 另外ptmalloc为了提高分配的速度,会把一些小的(不大于64B)chunk先放到一个叫做fast bins的容器内。在fast bins和bins都不能满足需求后，ptmalloc会设法在一个叫做top chunk的空间分配内存。 对于非主分配区会预先通过mmap分配一大块内存作为top chunk， 当bins和fast bins都不能满足分配需要的时候, ptmalloc会设法在top chunk中分出一块内存给用户, 如果top chunk本身不够大, 分配程序会重新mmap分配一块内存chunk, 并将 top chunk 迁移到新的chunk上，并用单链表链接起来。如果free()的chunk恰好 与 top chunk 相邻,那么这两个 chunk 就会合并成新的 top chunk，如果top chunk大小大于某个阈值才还给操作系统。主分配区类似，不过通过sbrk()分配和调整top chunk的大小，只有heap顶部连续内存空闲超过阈值的时候才能回收内存。需要分配的 chunk 足够大,而且 fast bins 和 bins 都不能满足要求,甚至 top chunk 本身也不能满足分配需求时,ptmalloc 会使用 mmap 来直接使用内存映射来将页映射到进程空间。
存在的问题，
后分配的内存先释放,因为收缩内存是从top chunk开始,如果与top chunk相邻的chunk不能释放,top chunk以下的chunk都无法释放。
多线程锁开销大， 需要避免多线程频繁分配释放。
内存从thread的areana中分配，内存不能从一个arena移动到另一个arena， 就是说如果多线程使用内存不均衡，容易导致内存的浪费。 比如说线程1使用了300M内存，完成任务后glibc没有释放给操作系统，线程2开始创建了一个新的arena，但是线程1的300M却不能用了。
每个chunk至少8字节的开销很大
不定期分配长生命周期的内存容易造成内存碎片，不利于回收。 64位系统最好分配32M以上内存，这是使用mmap的阈值。
tcmalloc
tcmalloc是Google开源的一个内存管理库，作为glibc malloc的替代品。目前已经在chrome、safari等知名软件中运用。
根据官方测试报告，ptmalloc在一台2.8GHz的P4机器上（对于小对象）执行一次malloc及free大约需要300纳秒。而TCMalloc的版本同样的操作大约只需要50纳秒。
tcmalloc为每个线程分配了一个线程本地ThreadCache，小内存从ThreadCache分配，此外还有个中央堆（CentralCache），ThreadCache不够用的时候，会从CentralCache中获取空间放到ThreadCache中。
小对象（<=32K）从ThreadCache分配，大对象从CentralCache分配。大对象分配的空间都是4k页面对齐的,多个pages也能切割成多个小对象划分到ThreadCache中.
小对象有将近170个不同的大小分类(class)，每个class有个该大小内存块的FreeList单链表，分配的时候先找到best fit的class，然后无锁的获取该链表首元素返回。如果链表中无空间了，则到CentralCache中划分几个页面并切割成该class的大小，放入链表中。
大对象(>32K)先4k对齐后，从CentralCache中分配。 CentralCache维护的PageHeap如下图所示， 数组中第256个元素是所有大于255个页面都挂到该链表中。
当best fit的页面链表中没有空闲空间时，则一直往更大的页面空间找，如果所有256个链表遍历后依然没有成功分配。 则使用从系统中分配。
tcmalloc PageHeap管理的连续的页面被称为span.
如果span未分配， 则span是PageHeap中的一个链表元素
如果span已经分配，它可能是返回给应用程序的大对象， 或者已经被切割成多小对象，该小对象的size-class会被记录在span中
在32位系统中，使用一个中央数组(central array)映射了页面和span对应关系， 数组索引号是页面号，数组元素是页面所在的span。 在64位系统中，使用一个3-level radix tree记录了该映射关系。
当一个object free的时候，会根据地址对齐计算所在的页面号，然后通过central array找到对应的span。
如果是小对象，span会告诉我们他的size class，然后把该对象插入当前线程的ThreadCache中。如果此时ThreadCache超过一个预算的值（默认2MB），则会使用垃圾回收机制把未使用的object从ThreadCache移动到CentralCache的central free lists中。
如果是大对象，span会告诉我们对象锁在的页面号范围。 假设这个范围是[p,q]， 先查找页面p-1和q+1所在的span，如果这些临近的span也是free的，则合并到[p,q]所在的span， 然后把这个span回收到PageHeap中。
CentralCache的central free lists类似ThreadCache的FreeList，不过它增加了一级结构，先根据size-class关联到spans的集合， 然后是对应span的object链表。如果span的链表中所有object已经free， 则span回收到PageHeap中。
ThreadCache会阶段性的回收内存到CentralCache里。 解决了ptmalloc2中arena之间不能迁移的问题。
Tcmalloc占用更少的额外空间。例如，分配N个8字节对象可能要使用大约8N * 1.01字节的空间。即，多用百分之一的空间。Ptmalloc2使用最少8字节描述一个chunk。
更快。小对象几乎无锁， >32KB的对象从CentralCache中分配使用自旋锁。 并且>32KB对象都是页面对齐分配，多线程的时候应尽量避免频繁分配，否则也会造成自旋锁的竞争和页面对齐造成的浪费。
Jemalloc
jemalloc是facebook推出的， 最早的时候是freebsd的libc malloc实现。 目前在firefox、facebook服务器各种组件中大量使用。
与tcmalloc类似，每个线程同样在<32KB的时候无锁使用线程本地cache。
Jemalloc在64bits系统上使用下面的size-class分类：
Small: [8], [16, 32, 48, …, 128], [192, 256, 320, …, 512], [768, 1024, 1280, …, 3840]
Large: [4 KiB, 8 KiB, 12 KiB, …, 4072 KiB]
Huge: [4 MiB, 8 MiB, 12 MiB, …]
small/large对象查找metadata需要常量时间， huge对象通过全局红黑树在对数时间内查找。
虚拟内存被逻辑上分割成chunks（默认是4MB，1024个4k页），应用线程通过round-robin算法在第一次malloc的时候分配arena， 每个arena都是相互独立的，维护自己的chunks， chunk切割pages到small/large对象。free()的内存总是返回到所属的arena中，而不管是哪个线程调用free()。
上图可以看到每个arena管理的arena chunk结构， 开始的header主要是维护了一个page map（1024个页面关联的对象状态）， header下方就是它的页面空间。 Small对象被分到一起， metadata信息存放在起始位置。 large chunk相互独立，它的metadata信息存放在chunk header map中。
通过arena分配的时候需要对arena bin（每个small size-class一个，细粒度）加锁，或arena本身加锁。
并且线程cache对象也会通过垃圾回收指数退让算法返回到arena中。
Jmalloc小对象也根据size-class，但是它使用了低地址优先的策略，来降低内存碎片化。
Jemalloc大概需要2%的额外开销。（tcmalloc 1%， ptmalloc最少8B）
Jemalloc和tcmalloc类似的线程本地缓存，避免锁的竞争
相对未使用的页面，优先使用dirty page，提升缓存命中。
相对于tcmalloc和jemalloc我们引擎的内存管理相对比较简单，也没有相应Thread缓存，不过胜在代码简单、更容易修改。
我们是因为在2007年开发，相对来说比较早，那时还没有关注到tcmalloc和jemalloc，再实际使用时，大家可以直接使用这两个库做内存管理。在多线程环境使用tcmalloc和jemalloc效果非常明显。当线程数量固定，不会频繁创建退出的时候， 可以使用jemalloc；反之使用tcmalloc可能是更好的选择。
- 本文固定链接: http://www.wy182000.com/2018/09/22/游戏引擎设计系列1-内存管理/
- 转载请注明: wy182000 于 Studio 发表
