内存分配器 (Memory Allocator)

Love The Way You Lie 2022-08-24 06:05 253阅读 0赞

对于大多数开发者而言，系统的内存分配就是一个黑盒子，就是几个API的调用。有你就给我，没有我就想别的办法。来UC前，我就是这样认为的。实际深入进去时，才发现这个领域里也是百家争鸣，非常热闹。有操作系统层面的内存分配器(Memory Allocator)，有应用程序层面的，有为实时系统设计的，有为服务程序设计的。但他们的目的却是一样的，平衡内存分配的性能和提高内存使用的效率。

从浏览器开发的角度看，手机内存的增长速度相对于网页内容的增长仍然只是温饱水平，像Android本身就是用内存大户，还有一个[Low Memory Killer][], 一定要优化内存占用。总体上对策就是两点:**一是能不用就不用**，代码里可能隐藏着很多不必要内存分配，特别留意那些中间量。**二是能少用就少用**，特别避免频繁分配，因为那样只会增加内存碎片，到了极端时即使仍有内存可用，也分配不出来了。还有**一个选项: 换个内存分配器**。这样一是如果内存分配器优良就可以缓解内存碎片，也可以在出现OOM时控制程序的行为，崩与不崩、崩在哪里就可以自己控制了。

最近因为工作原因，涉及到了小内存分配器，所以做了一些粗浅的学习，没有完整的阅读代码，也没有进行透彻的测试，只是写个总结以及相关的文档放在这里，备查。

## 内存分配的现实问题 ##

首先通常使用的内存分配器,即malloc/free函数并不是系统提供的，而是C标准库提供的。也被称为动态内存分配器。分配器从操作系统拿内存(虚拟内存)时是以页为单位(通常是4KB，调用sbrk或mmap), 然后再自行管理。

上面也提到了，内存分配器面对的是两个核心问题: 效能和性能(或称为吞吐量Throughoutput)。 前者保证随时有内存可用，后者保证服务时间短、不拖后腿。

对于一个系统进程而言，面对OOM(Out Of Memory)问题，排除程序使用内存的Bug外，会有两个原因:  
  1.系统真的没有内存可用了。

2.内存分配浪费了大量空间，虽然有大量零散的可用空间，却无法合并提供出来使用。 前者才是真正的OOM, 后者就是内存碎片(Fragmentation)问题了。

libc里的malloc遇到分配失败时，默认会abort掉进程，也就是崩掉(CRASH)了。如果系统支持mallopt就有机会改变这个行为，可惜Android还没有支持。

浏览器在加载、解析、渲染页面的时候，会分配大量的小对象，看张图就明白了：

![SouthEast][]

上图中模轴为对象大小，纵轴则为申请分配的次数。如果内存都以页为单位申请，就简单，也就不需要分配器。就是那些小对象，占用不多，使用频繁，很容易造成页内无法再继续使用的碎片(Internal Fragmentation)。

对于性能，内存分配是次于I/O的一个瓶径。虽然绝大多数情况下都相安无事，但内存分配器有一个重要的指标，即上限(bounded limits)。虽然平均值看起很好，但一旦遇到最坏的情况(wrost case)时，能不能保证性能？特别是多线程下，内存分配、释放的性能常常受到加锁的影响。有些分配器(如ptmalloc)过于考虑性能，而无法使线程间的内存共享，各自占去一块，反而降低了内存使用的效率。

这些问题一直存在，不同的人针对不同的场景设计出了不同的分配器算法(DSA, Dynamic Storage Algorithms, 是以应用的角度来看的)，而且几乎每一个都说自己比别人强。比如:  
   1. dlmalloc/ptmalloc/ptmallocX C标准库提供的分配器, 也是应用程序默认使用的malloc/free等函数。  
   2. tcmalloc 出自Google, WebKit/Chrome中应用。  
   3. bmalloc 毕竟Chrome和WebKit越走越远，所以Apple在WebKit最新代码(2014-04)里提供了新的分配器，号称远远超过 TCMalloc, 至少是在性能上。  
   4. jemalloc 原本是为FreeBSD开发的，后来Firefox浏览器和FaceBook的服务端都加以应用，它自身也在这些应用中得到了大幅提升。  
   5. Hoard 一个专为多线程优化的分配器, 作者是大学教授，有一些独特的技术。Mac OS X中的malloc就有参考其实现进行优化。

\*WebKit另外专为Render Object提供了一个所谓的Plain Old Data Areana的类，也算是一个Memory Pool的实现(PODIntervalTree, PODArena)。

## 核心思想和算法 ##

分配器这么多，其核心思想相似，只是差在算法和metadata存储上。附13提供的论文中有比较全面的总结，可以翻看一下。

内存分配器的核心思想概括起来三条:

1. **基本功能**：首先将内存区(Memory Pool)以最小单位(chunk)定义出来，然后区分对象大小分别管理内存，小内存分成若干类(size class)，专门用来分配固定大小的内存块，并用一个表管理起来，降低内部碎片(internal fragmentation)。大内存则以页为单位管理, 配合小对象所在的页，降低碎片。设计一个好的存储方案，即metadata的存储，减少对内存的占用。同时优化内存信息的存储，以使对每个size class或大内存区域的访问的性能最优且有上限(bounded limits)。

比如dlmalloc定义的是一个个bins(同size class)来存储不同大小的内存块:

![SouthEast 1][]  
2. **回收及预测功能**: 当释放内存时，要能够合并小内存为大内存，根据一些条件，该保留的就保留起来，在下次使用时可以快速的响应。不需要保留时，则释放回系统，避免长期占用。

3. **优化多线程下性能问题**：针对多线程环境下，每个线程可以独立占有一段内存区间，被称为TLS(Thread Local Storage)，这样线程内操作时可以不加锁，提高性能。下图是MSDN上贴出的关于TLS的原理图，可以参考:

![SouthEast 2][]

\*另外测试工具也是必不可少，比如tcmalloc的heap profile, jemalloc则结合valgrind。FireFox在移植jemalloc到Android时，特别关掉了TLS，想必是考虑到它对于线程单一应用的副作用。

上面这些思路对于各个分配器而言基本是一致，但具体如何组织size classes, 如果以一个固定步长，必将形成一个巨大且效率低下的表，原因参考第一张图就明白了。很多年前，就有专门的论文对此做了评定(链接)。另外还有如何定位内存块? 如何解决多线程下的false cache line问题? 不同的分配器使用了不同的算法和数据结构来实现。它们所使用的算法统称为DSA, Dynamic Storage Algorithms。

具体的算法实现可以在下面的参考列表中找到对应的文档, 也可以先看附16，文中分别对DSA Algorithms和DSA Operational Model做了描述，概括的很好，会有一个总体的印象。作者将DSA算法分为五类:

**  1. Sequential Fit**

是基于一个单向或双向链表管理各个blocks的基础算法，因为和blocks的个数有关，性能比较差。这一类算法包括Fast-Fit, First-Fit, Next-Fit, and Worst-Fit。

**  2. Segregated Free List** (离散式空闲列表)

使用一个数组，每个元素是存储特定大小内存块的链表，它们所代表的大小并不是连续的，所以称为离散。经典的dlmalloc使用的就是这个算法。数据元素，参照上面的图就可以理解了。TLSF算法则是基于此进行了改进。

**  3. Buddy System**

这是由一代大师Donald Knuth提出，后续产生许多的改进版本。最大的作用是解决外部碎片(external fragmentation), 详细的算法，参考这篇（[浅析Linux内核内存管理之Buddy System][Linux_Buddy System]）。

**  4. Indexed Fit**

以某种数据结构为每个block建立索引，以求可以快速存取。一般以一个二叉树结构实现。比如使用Balanced Tree的Best Fit allocator, 以及基于Cartesian tree 的Stephenson Fast-Fit allocator。这类算法的性能比较高，也比较稳定。

**  5. Bitmap Fit**

这类算法只是索引方法不同，使用以位图式字节表示存储单元的状态。它的好处是使用一小块连续的内存，响应性能更好。Half-Fit就属于这类算法。

随着技术演进，现在主流的allocators, 基本上都是综合运用了两类以上的算法。

另外一些基础算法也是相似的，比如以二叉树组织列表的算法，也就是in-place, 笛卡尔树 和red-block的差异。在线程上，则因为实现的不同，会导致内存占用的差异。比如jemalloc在释放时，并不需要在原来的分配线程执行释放，只是被放回到分配线程的free list中去，ptmalloc则必须回到分配线程里执行释放，性能就相对弱一些。 tcmalloc则设计了算法，让一个线程可以从它的邻居那里偷一些空间来(这个过程称为transfer cache)，这样可以有效地利用线程间的内存。

### 优劣势对比 ###

ptmalloc 劣势:多线程下的性能及内存占用(线程间内存无法共享),并且内存用于存储metadata开销较大，在小内存分配上浪费比较多。优势:算是标准实现。

tcmalloc 劣势：因为算法的设计，占用的内存较大。优势:多线程下的性能。参考附6。

jemalloc 优势: 内存碎片率低，多核下性能较tcmalloc更好。参考附17。

时间有限，没有再深入研究，后面有空再补充一下。在实际应用中，还是有一些参数可以调整的，前提是要熟悉其实现，特别是性能评估的方法。

转载请注明出处: [http://blog.csdn.net/horkychen][http_blog.csdn.net_horkychen]

## 参考 ##

这是我列的最长的参考清单了，前人的确已经做了很多的研究，我对其中内容只是泛读，并不是所有内容都相关，只是觉得有些内容可以相互应证就也列进来了。  
1. jemalloc关于使用red-block tree的反思 [\[链接\]][Link 1]  
  文章发布于2008年，作者在2009年将其应用于FaceBook时，则是进行了算法上优化。  
2. 2011年jemalloc作者在FaceBook应用jemalloc后撰文介绍了jemalloc的核心算法及在Facebook上应用效果。[\[链接\]][Link 2] [\[早期的论文，有更多的细节\]][Link 3]  
3. Android碎片化的度量 通过改造ROM做的实验。  
4. Hoard Offical [\[链接\]][Link 4]  
5. Mac OS上malloc是怎么工作的[\[链接\]][Link 5]  
6. 关于WebKit应用tcmalloc的对比[\[链接\]][Link 6]  
7. How tcmalloc works[\[链接\]][Link 7] [\[中文翻译\]][Link 8]  
8. TCMalloc源代码分析,很不错资料。作者的网站还有其它干货值得一读。[\[链接\]][Link 9]  
9. dlmalloc早期的技术文档，讲述了其核心算法。[\[链接\]][Link 10]  
10. ptmalloc源码分析,讲的很系统，非常值得一读。[\[CSDN下载链接\]][CSDN]  
11. 介绍jemalloc的资料《更好的内存管理-jemalloc》[\[链接\]][Link 11]  
12. 替换系统malloc的四种方法 [\[链接\]][Link 12]  
13. 介绍针对实时系统进行优化的内存分配算法TLSF，其中对动态分配算法(DSA)做了总结。[\[链接\]][Link 13]  
14. 维基百科上关于Thread Local Storage的说明, 也许你能感受到技术的相通性。[\[链接\]][Link 14]  
15. 针对实时系统进行各种分配算法的对比,可以结合13一起看。[\[链接\]][Link 15]  
16. ptmalloc,tcmalloc和jemalloc内存分配策略研究。[\[链接\]][Link 16]  
17. Firefox3使用jemalloc后的总结，可以看到Firefox优化的思路。[\[链接\]][Link 17] [\[Firefox使用的源代码\]][Firefox]  
18. Chromimum Project: Out of memory handling, 里面有不错的观点。 [\[链接\]][Link 18]

[Low Memory Killer]: http://tech.it168.com/a2011/0805/1228/000001228471_2.shtml
[SouthEast]: /images/20220823/aa2fe2c23e99409bab9fe4ca69605491.png
[SouthEast 1]: /images/20220823/bb15fa78bd0149e783bb8189b9490f0d.png
[SouthEast 2]: /images/20220823/44ad5a6ddabd4edfb09babcb34a002eb.png
[Linux_Buddy System]: http://blog.csdn.net/hsly_support/article/details/7483113
[http_blog.csdn.net_horkychen]: http://blog.csdn.net/horkychen
[Link 1]: http://www.canonware.com/~ttt/2008/07/overzealous-use-of-my-red-black-tree.html
[Link 2]: https://www.facebook.com/notes/facebook-engineering/scalable-memory-allocation-using-jemalloc/480222803919
[Link 3]: http://people.freebsd.org/~jasone/jemalloc/bsdcan2006/jemalloc.pdf
[Link 4]: http://www.hoard.org/
[Link 5]: http://www.cocoawithlove.com/2010/05/look-at-how-malloc-works-on-mac.html
[Link 6]: http://webkit.sed.hu/blog/20120525/memory-consumption-qtwebkit-comparewebkit1-webkit2-systemmalloc-tcmalloc
[Link 7]: http://jamesgolick.com/2013/5/19/how-tcmalloc-works.html
[Link 8]: http://blog.chinaunix.net/uid-24990614-id-3911071.html?/7990.html
[Link 9]: http://dirlt.com/tcmalloc.html
[Link 10]: http://gee.cs.oswego.edu/dl/html/malloc.html
[CSDN]: http://download.csdn.net/download/csuideal/4829502
[Link 11]: http://wangkaisino.blog.163.com/blog/static/1870444202011431112323846/
[Link 12]: http://blog.csdn.net/littlefang/article/details/6052563
[Link 13]: http://wks.gii.upv.es/tlsf/files/ecrts04_tlsf_0.pdf
[Link 14]: http://en.wikipedia.org/wiki/Thread-local_storage
[Link 15]: http://www.ijera.com/papers/Vol2_issue3/GR2311511156.pdf
[Link 16]: http://www.owent.net/QoH5w
[Link 17]: http://blog.pavlov.net/2008/03/11/firefox-3-memory-usage/
[Firefox]: http://mxr.mozilla.org/mozilla-central/source/memory/mozjemalloc/
[Link 18]: http://www.chromium.org/chromium-os/chromiumos-design-docs/out-of-memory-handling