定制linux内存管理

对于C/C++开发者，想要开发一款高性能、高稳定性的程序，最重要的问题之一就是内存管理

通常我们会使用malloc（什么，你说new？new是封装malloc的了）来分配内存，并把内存管理交给系统去做。

但是malloc的性能真的够用吗？为什么很多著名开源服务器都会自己写一套内存管理器？如果老板要我优化架构，要不要考虑把malloc给废了？

一 malloc寻根

linux下的malloc实现又叫ptmalloc（ptmalloc是dlmalloc的一种变形，所以有些地方也会直接说成dlmalloc）

当我们调用malloc时，根据申请的大小会分成截然不同的几种处理流程。小内存会进入“定长内存”系统；大内存则进入“变长内存”系统（备注1）。

“定长内存”系统会事先准备好（备注2）一系列空闲内存链表。链表中的空闲内存块都是一样大的。

  

分配内存时只需找到相应的链表，从链表头部取出一个空闲内存块即可。释放时也是直接插入即可。分配和释放的复杂度都是O(1)

虽然定长内存系统的分配和释放极快。但是在分配大块内存时，定长内存分配会导致大量内存碎片（内碎片），关于内存碎片分类和优化我们会在后续章节再讨论。

“变长内存”系统也会组织一系列空闲内存链表。链表中的空闲块通常是不一样大的：

 

在很早以前，变长内存只有1条链表，每次分配时需要遍历这个长长长长的链表以找到大小合适的内存块。

后来ptmalloc做了很多的优化，在分配速度上已经提升了很多。

变长内存会按照大小范围组织成很多个不同的链表，例如：

10K-15K属于链表1；

16K-23K属于链表2；

24K-39K属于链表3；

.........

（数值是随手写的，真实数值请google largebin_index_64）

通过分链表（或者叫分箱），每个链表的大小都会缩小很多。这样就能更快的查找到我们需要的size

总体来说，变长内存的性能比定长内存要差。分配时需要遍历会导致耗时增加，而且变长内存通常需要分裂内存块，会导致外碎片增加。

二 细节决定成败

从整体设计上来看，malloc做的相当好。

但是当我们深入一些关键的细节时，会发现malloc针对一些特殊场景，会出现很严重的问题

1 管理小内存块时浪费了大量的空间

每个内存块需要一个size_t的空间来存放本内存块的大小，供释放时使用。以64位机器为例，size_t是8字节长的。而且内存块必须在2*size_t的长度上对齐。所以当我们malloc(26)时，实际消耗的内存是48字节，浪费了45%的内存。

另外内存块有一个最小大小4*size_t。在64位机器上，最小的分配单位就是32字节。当我们需要分配大量小结构体时，malloc会导致极大的内存浪费。

验证代码请参考附件中的mem_little.cpp

2 定长小内存和变长大内存容易交错混在一起

所有内存块都是从top内存区分出来的，并没有专门给不同尺寸的内存划分专属内存池，所以定长小内存有很大几率会和变长大内存交错混在一起。

这将使得小内存块随时可能和大内存块合并（合并后就走变长内存系统了），使得定长内存的优势大打折扣，malloc时的局部性也很不好

3 释放内存时可能因为brk而被卡住

malloc的主分配区是通过brk向内核申请内存的，非主分配区通过mmap模拟brk。而brk是一个线性的分配器，类似栈。

简单来说，如果我先malloc了5G内存；再malloc 16字节，抓住这16字节不释放；然后释放前面的5G内存，这5G内存是无法还给系统的。

验证代码请参考附件中的mem_brk.cpp

malloc的这个特性对于需要长期持有而不释放的内存是极其不友好的。而且一旦出现内存泄漏，哪怕只漏了几个字节，也可能把几个G的内存释放卡住。

4 锁的性能消耗

ptmalloc的内存分配区不是和线程绑定的，所以必须在进入malloc和free时加一把大锁（针对单个分配区的锁）。虽然可以通过建立多个分配区和try_lock来降低等待锁的几率，但是锁本身也是很消耗性能的

5 低效的realloc

当需要扩大已分配的内存块时，ptmalloc将尝试从尾部扩展内存块。但是当系统内存压力较大时，这个尝试的成功率是不高的，这时就需要分配一个全新的内存块并把旧数据拷贝过去，而这将引入极其巨大的性能消耗（备注3）。

三 我们的目标

技术是为需求服务的。我之所以追求性能优化，是因为当时公司的硬件成本占总销售收入的30-40%，而公司的净利润只有10-15%

对于某些土豪行业来说（别躲了，手游，说的就是你），硬件成本只有不到5%的，就不要花太多精力去优化性能了。

我们做的是一款http正向缓存代理服务器，约等于带强大缓存功能的nginx

具体目标是在一台8核16G内存的机器上承载每秒4Gb的http流量，100万并发连接。

我们需要缓存整个互联网，所以需要上亿个10字节的结构体来存储url信息；另外还需要处理每秒4Gb的http socket数据，并尝试进行缓存写入和读出。

在连接建立时我们是不知道每个连接需要多大缓冲区的，这就需要大量的realloc来扩大已有缓冲区。

当用户下载1GB的文件时，原始服务器先将1GB文件发给我们，我们再转发给用户，这将持续相当长的一段时间。在这个过程中，我们可以把已转发给用户的部分内存先释放掉，但是可惜malloc不支持部分free。

总结成一句话就是：我们需要一个内存利用率极高的定长小内存系统和一个支持“高效realloc”和“一次malloc可分为多次free”的变长大内存系统

四 内存系统设计的一般原则 

在设计内存管理系统时，我们主要关心三个方面：

内存利用率

分配和释放效率

局部性

1 内存利用率方面主要是三个问题：

内碎片：分配内存时，分配出的内存大于需要的内存叫内碎片。

例如ptmalloc中，需要8字节对齐，再加上8字节管理信息，这一部分就是内碎片（很多论文中不把管理信息算到内碎片中，而是单独计算，个人喜欢合在一起计算，方便）

如果对大内存块采用定长内存系统，前后两个定长内存块之间的大小会差的较大，从而产生较大的内碎片。这也是为什么绝大多数内存管理系统，仅对小内存块使用定长内存。

外碎片：因为空闲内存块太小导致有内存又无法分配叫外碎片

如下图，经过长时间malloc-free后，空闲内存（绿色）被分隔到成很多小碎片，就无法再malloc出大块内存了

外碎片主要是由于把变长的大内存块分裂成两个内存块而导致的。例如空闲内存块为900K，我们需要分配875K，剩下的25K被分裂出来后，就会形成外碎片

无法还给系统：在上一节中已经举例说明过这个问题，free将内存还给内存管理器后可能无法归还给系统，导致其它进程分配内存失败

2 分配释放效率：

定长分配和释放往往都是O(1)的效率

变长内存分配则通常需要遍历链表来找到大小合适的内存块。通常会通过按大小范围分箱来提高分配速度。

如果定长内存和变长内存交错在一起，定长内存会经常和变长内存合并，使得定长内存的优势体现不出来。

另外我们还可以为每个线程分配一个专属的线程池，可以避免加锁解锁的消耗。

3 局部化：

最近20年来，CPU速度提升了上万倍，内存提升了上百倍，硬盘速度提升仅有几倍，所以优化性能的关键，很多时候都不在于减少CPU的运算压力，而在于减少内存总线读写

通过提升内存的局部化，可以大幅优化CPU的cache效果，提高运行效率

验证代码请参考附件中的mem_cache.cpp

五 slab定长内存池 

linux内核采用的slab算法是一个极好的定长内存管理算法

通过将若干个小定长内存集中在一个桶里，我们就不必为每个内存块维护独立的管理信息了。当我们需要读取管理信息时，对内存块取模取到桶的头部，就可以读到相关管理信息了。

同时，这还将极大的减少定长内存和变长内存交错的情况，提升分配和释放效率。

要让slab达到最高效率，我们需要事先对slab系统进行初始化，声明我们需要用到定长内存块大小（通常是某个频繁使用的struct/class），最好还能手动设定一下桶的大小。这也是为什么malloc不采用slab算法的原因。

六 大内存支持非连续化 

非连续化，即我们不再要求指针指向一段连续内存。例如在传统情况下，一个10MB的缓冲区必须是连续10MB的虚拟地址。而非连续化之后，一个10MB的缓冲区可以由若干个4K的虚拟页拼接而成。

通过支持非连续内存，我们将变长内存池的问题转化成了定长内存的问题，大内存使用过程中碰到的几个最主要问题，都已经解决了。

因为所有内存块都是定长的，我们不再会有任何外碎片的问题，跑上100年也不会有外碎片。

内碎片有可能会较多，这取决于我们对内存块大小的控制。

通过实际测试，对http代理来说，采用4K和512两级内存块就可以达到90%以上的内存利用率。

在realloc重分配问题上有着极高的性能。我们随时可以从已分配内存的头部释放内存（代理服务器已转发数据的释放），也随时可以在已分配内存的尾部追加内存。

非连续内存有一个极大的缺陷：无法用常规的strcmp、memcpy系列函数处理；也无法转换成string；使用时一不小心就会踩内存。必须提供一系列函数对非连续内存池进行处理，例如jump_get_next来获取下一个字符并自动判断是否需要跳到下一个内存块。

在08年阅读nginx代码时，发现nginx就已经实现了一套非连续内存池的代码，但是并没有发现任何代码在使用这个非连续内存池。对于开源这样人员多变的开发环境，确实不太适合使用非连续内存池；但是对于人员稳定性和素质有保障的商业公司，完全可以尝试用非连续内存来提升性能。   

备注1：

实际上ptmalloc会按大小维护5个级别的分配算法：

fastbin、smallbin、largebin、top、mmap

fastbin：最小的内存空闲块，属于定长内存。

smallbin：大于等于fastbin，也属于定长内存。

有一些最小的内存块，即可以属于fastbin也可以属于smallbin（优先从fastbin分配，当fastbin为空时走smallbin逻辑）

fastbin和smallbin最大的区别在于fastbin的合并更lazy一些，系统中更容易留下未被合并的fastbin；而smallbin更容易被合并掉（合并指当两个相邻内存块都是空闲时，合并成一个大的空闲内存块）

largebin大于smallbin，属于变长内存，包含大量的内存块链表，每个链表覆盖一个长度范围

top内存：top内存只有一个块，所有从内核brk上来的内存（非主分配区会通过mmap模拟brk）都会先放在这里，再分配给前面的3种内存块。当从上述3种内存块释放内存时，也必须先合并到top之后才能还给内核

mmap内存：大于一定大小的内存会直接通过mmap从内核获取，释放时直接unmmap还给内存。

备注2：

实际上这里有一个lazy的机制。

第一次malloc时并没有事先准备好的定长内存，此时需要从更高层的内存块中（例如largebin或top），速度较慢。

free时，如果大小属于fastbin会直接放入定长内存池中。如果属于smallbin，在尝试和相邻内存块合并失败时，也会放入定长内存池。

在经过一段时间的malloc和free之后，如果没有触发大量的合并，我们就可以幸运的拥有一个快速的定长内存池了

备注3：

在不同的系统中，性能的瓶颈是不一样的。在我们的http代理服务器中，CPU消耗比例大概是：

应用层消耗        5%

    Tcp协议栈 20%

    copy_to_user等 20%

    网卡驱动 15%

    其它内核函数 40%

可以看到copy_to_user和copy_from_user加起来占了20%的CPU。这两个内核函数属于recv和send的内核实现，负责在内核和应用层间拷贝socket数据。

换句话说，如果我们通过realloc将所有socket缓冲区拷贝了一遍，就会增加约20%性能消耗

验证代码压缩包：

 mem_test.zip