码农code之路年前去过上海掌门集团（做无线wifi万能钥匙的那一家）和百度面试过一次，前者问了linux下gcc的malloc函数如何分配内存的，后者在二面时通过一个链表的数据结构也间接地问到了这个问题。我面试的职位是后台C++开发。
且不说面试会可能会遇到这个问题，我们很多服务器程序在长周期或者大量访问的情况后会变得反应迟钝，排查原因发现占用内存会随着请求数量的增多不规律而且不正常地增长，和内存泄漏一样。如果使用valgrind这样的内存泄露工具排查却发现并无内存泄露，其根本原因是内存碎片造成的。这也是我们在开发高性能服务器需要解决的一个问题，那如何解决这个问题呢？请听我慢慢道来。
一、 内存分配与内存碎片
经典的进程内存布局如图1所示。
图1 内存布局图
图1中底端是内存地址为0的地方，顶端是内存线性地址最大的地方（如32位下线性地址最大值是0xFFFFFFFF），而占据顶端的就是内核空间，这里是操作系统内核预留的空间区域。第二部分是栈空间，也就是堆栈所在的内存空间，众所周知，栈是自高地址处向低地址处增长的，这在图中也有所反映。最后一部分是堆空间，在这个简化的理论模型上所有的剩余空间都预留给了堆，堆是从低地址向高地址增长的。
当然这只是一个简化模型，实际上在堆的下方，还会为静态内存空间预留内存，而堆与栈的中间可能还有供mmap（内存映射）使用的区域。此外，由于栈的空间有限，而且只用来管理所谓的“自动变量”，因此我们在实际程序中需要大量使用到堆。堆空间不仅可用内存多，而且可以动态分配，也就是说按需获取，按需使用，不需要时释放即可。C中的malloc/free与C++中的new/delete就是用来管理内存的。但是较
少有人去深入了解malloc/free或者new/delete到底为我们做了什么。
首先，内存管理函数并不会直接去向操作系统索要内存，因为系统调用的开销比较大，这样做是非常不值的。此外，直接使用过系统调用的人都知道，在Linux下分配堆内存需要使用brk系统调用，而这个系统调用只是简单地改变堆顶指针而已，也就是将堆扩大或者缩小。所以如果我们遇到这种情况，是没有办法直接将内存归还给操作系统的，如图2所示。
图2 内存图
这种情况下，假设我们先分配了memory2，再分配memory1。现在memory2内存不需要了，我们想还给内存，但是遇到问题了——如果我们改变brk指针，那么memory1也会被还给系统，这样是不可行的。
我们有两种解决方案：一是将memory2内存中的数据复制到memory1中，但是这样一来，所有的内存地址都会发生变化，是不可行的；二是将memory2的内存缓存下来，下一次用户申请内存时我们不需要直接使用系统调用，而是直接从缓存的内存中划出一块交给用户。等到用户完全不使用memory1和memory2了再将这两块内存释放。所以在C/C++真正的内存管理中，都会有这么一个内存管理器，它负责向操作系统申请内存，并将内存缓存下来，并通过某种算法从缓存的内存中划出一块交给用户，这样一可以提高程序的运行效率，二可以提高内存的使用效率，一举两得。这个内存管理器就像一个“批发商”，一次性向操作系统索要可观的内存数量，并直接将自己“批发”来的内存销售给调用内存管理函数的用户。
但是，如果我们这个“批发商”对商品管理不当，还是会出很大问题的，如图3所示。
图3 原始内存图
其中，每个字符串我们都分配了一定数量的空间，如字符串“a”需要2字节（C中字符串需要一个额外的0字符用于标识字符串结束）。现在我们发现“a”、“c”、“e”这3个字符串再也不需要了，所以我们将其释放，现在内存如图4所示。
图4 释放字符串之后的内存图
这样这3块内存又可以重复利用了。但是这些内存太小了，为了保证之后可以更好地利用，我们需要将其合并起来（合并成一块内存），这样再次分配内存时，只要用户需要的内存不超过6字节，只需要从中划出一块分给用户即可。合并之后的内存图如图5所示。
图5 合并之后的内存图
但这是一种非常理想的情况，而且是一种极端最优情况。让我们来看另一种极端最坏的情况，假设我们分配内存如图6所示。
图6 内存图
现在看起来是正常的。但是如果我们不需要那几个2字节的内存空间，内存如图7所示。
图7 内存图
现在那几个2字节的空间是被还给内存管理器了，但是内存管理器没办法对其进行合并，因为这几个很小的空间是零碎分布在这片内存中的。一个极端情况是：如果程序再也没有2字节的动态内存可以分配了，而且这几个4字节内存是永远占用的，那么这几个2字节内存又该如何使用呢？
很明显，这几块内存已经再也无法使用了，既不能分配又不能归还——这就是所谓的内存碎片。小规模的内存分配越多，内存碎片也就会越严重。而gcc默认使用的ptmalloc分配器对这种内存碎片的优化不是非常理想，导致了Samuel出现了看似是“内存泄漏”的问题，实际上是内存碎片问题。
此外，我们想象另一个场景，如果每个线程并发分配堆，由于对于每个进程堆是唯一的，因此我们再分配内存时还需要上锁，如果在一个程序中需要在短时间内频繁地分配小内存，那么又会出现因为频繁上锁而导致的性能损耗。这是我们无法接受的。
二、tcmalloc
为了解决这些问题，我们可以使用一些更好的内存管理器替代默认的内存管理器，如Google开发的tcmalloc（Google的gperftools的一部分，网址为https://github.com/gperftools/gperftools）和jemalloc等内存管理库，这些库使用得非常频繁，而且不需要改变原有代码，对于频繁使用内存的程序，是非常值得使用的，例如，Redis为了获得最好的性能就使用了tcmalloc和jemalloc。（Redis是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库，并提供多种语言的API，是目前最流行的缓存解决方案之一。）
tcmalloc和jemalloc的原理非常相似，都是在链接时期替代标准libc中的malloc和free，因此加载程序后就会替代原有的malloc和free进行工作，因此在不改动代码的情况下，就可以解决内存碎片的问题。
下面介绍一下tcmalloc。
tcmalloc就是一个内存分配器，管理堆内存，主要影响malloc和free，用于降低频繁分配、释放内存造成的性能损耗，并且有效地控制内存碎片。glibc中的内存分配器是ptmalloc2，tcmalloc号称要比它快。一次malloc和free操作，ptmalloc需要300 ns，而tcmalloc只要50 ns。同时tcmalloc也优化了小对象的存储，需要更少的空间。tcmalloc特别对多线程做了优化，对于小对象的分配基本上不存在锁竞争，而大对象使用了细粒度、高效的自旋锁（Spinlock）。分配给线程的本地缓存在长时间空闲的情况下会被回收，供其他线程使用，这样提高了在多线程情况下的内存利用率，不会浪费内存，而这一点ptmalloc2是做不到的。tcmalloc区别地对待大、小对象。它为每个线程分配了一个线程局部的cache，线程需要的小对象都是在其cache中分配的，由于是thread local的，所以基本上是无锁操作（在cache不够，需要增加内存时，会加锁）。同时，tcmalloc维护了进程级别的cache，所有的大对象都在这个cache中分配，由于多个线程的大对象的分配都从这个cache进行，所以必须加锁访问。在实际
的程序中，小对象分配的频率要远远高于大对象，通过这种方式（小对象无锁分配，大对象加锁分配）可以提升整体性能。
线程级别cache和进程级别cache实际上就是一个多级的空闲块列表（Free List）。一个空闲块列表以大小为k B倍数的空闲块进行分配，包含n个链表，每个链表存放大小为n×k B的空闲块。在tcmalloc中，小于等于32 KB的对象被称为小对象，大于32 KB的是大对象。在小对象中，小于等于1024 B的对象以8n B分配，大于1025 B，小于等于32 KB的对象以128n B大小分配，例如，要分配20 B则返回的空闲块大小是24 B，小于等于B的，这样在小于等于1024 B的情况下最多浪费7 B，大于1025 B则浪费127 B。而大对象是以页大小4 KB进行对齐的，最多会浪费4KB-1 B。图8所示为一个空闲块列表的示意图。
图8 tcmalloc空闲链表示意图
实际上，一个空闲块列表就是一个数组索引多个链表，每个链表存放相同大小的块。可以根据要分配的内存大小size算出合适的块在free list中的下标，然后找到对应的空闲块链表。
tcmalloc的数据结构组织如图9所示。
图9 tcmalloc数据组织
1）线程局部空闲链表：线程本地的空闲块cache，用于分配小对象。
2）堆空闲链表：中心free list，全局唯一，用于按页对齐分配大对象或者将连续的多个页（被称作span）分割成多个小对象的空闲块分配给thread-local free list。
3）页面数组：用于描述当前tcmalloc持有的内存状态，完成从page number到span的映射。
小对象的分配过程如下。
1）根据分配的size计算出对应的空闲块大小，从而确定对应空闲块链表，然后从thread local的free list进行分配。
2）如果空闲块链表非空，直接将头结点对应的空闲块返回并从空闲块链表中将其删除。
3）如果空闲块链表是空的，需要从heap free list获取一个span。如果heap free list非空，则将span切分成多个相同大小的空闲块插入空闲块链表中，然后返回头节点。
4）如果heap free list是空的，则调用sbrk或者mmap进行内存的分配，一系列连续的内存页作为span，然后切分成多个相同大小的空闲块插入空闲块链表，然后返回头结点。大对象的分配简单得多，直接从heap free list分配4n KB大小的空闲块即可，如果heap free list不存在该大小的空闲块，通过系统调用分配连续的内存页。
tcmalloc还会对thread local cache进行垃圾收集，从而避免内存浪费。或者我们还可以使用一个传统的解决方案——内存池。
三、内存池
内存池的思想很简单，既然对于特定用途通用内存管理器已经无法很好地运作了，那么干脆就模仿内存管理器，直接在系统分配的一块大内存上建立我们自己的内存管理机制，并设计一套数据结构与算法来适应我们特殊的内存分配需求即可。
如果是通用内存池，我们可以模仿通用的内存管理器，通过如图10所示的数据结构来管理内存空间。
图10 内存分配示意图
其中，上面一块是元数据区域，用来记录我们的内存分配信息，元数据区域中最重要的是一个链表，这个链表维护了我们所使用的内存数据。分配内存时我们从内存中分出一块并加入一个表项到链表中；释放内存时，我们将内存从链表中移除。
图10只是一个示意图，如果只是简单地这样管理内存，依然无法解决内存碎片问题，需要对数据结构进行优化，这需要读者自行阅读相关资料。
内存池的另一个好处是我们可以为每个线程单独分配一个内存池，而不需要整个进程共用，这样在多线程的程序中，还可以避免多个线程之间同时分配内存时频繁上锁。除此之外，我们还可以在用户引用错误内存时给出更清晰、更明确的异常信息，并进行Heap Dump，总之就是可以增强我们对内存的控制能力。
此外，如果将内存池技术和句柄技术结合，我们可以更好地解决内存碎片问题，如图11所示。
图11 内存池与句柄
我们将链表中的每个对象都看成一个句柄，并为这些句柄进行编号。用户不再使用直接的指针，而是使用我们包装过的句柄引用对象。这些对象里包含的是句柄的编号。当我们发现由于小块内存过多而引发内存碎片时，只需要将数据内存中的内存进行压缩（也就是将正在使用的内存重新排布到一起，将空闲的内存空间预留出来，可以看成内存的碎片整理），并修改句柄列表中句柄指向的实际地址，这样就可以一定程度上解决内存碎片问题。虽然这样会引起程序的暂时停顿，但是在不直接和用户进行UI交互的服务器程序中，这种小间断往往是可以接受的，尤其是那些追求高吞吐量同时又要避免内存碎片的程序非常适合使用这种模型。
