快手 Android 内存分配器优化探索 (二)

导读

在上篇中，我们介绍了Linux内存管理机制和多种内存分配算法。本篇将深度剖析jemalloc的原理，并介绍Google在Android平台的定制优化，挖掘更多内存极限优化空间。

文 / 李锐

编辑 / 乔

本文共14214字，预计阅读时间40分钟。

03

jemalloc深度剖析

jemalloc是一款被业界广泛使用的内存分配器。2005年，Jason Evans首次将其引入FreeBSD，此后开始在Firefox浏览器、MySQL、Redis等重磅级项目中使用。2014年，Google将旧有的dlmalloc替换为jemalloc，并将其作为Android默认分配器；直至2020年，jemalloc才被替换为自研的scudo。在Android内存领域，jemalloc长期担任着重要角色。

上篇文章，我们介绍了Linux平台内存管理机制和多种类型内存分配算法，本篇将展开对jemalloc的深度剖析，介绍Google在Android平台的定制化配置。本文篇幅较长，细节较多，需要耐心阅读，理解这些原理对于后续的内存优化至关重要。事实上。当理解了jemalloc的原理之后，再去看其他分配器很容易举一反三，如笔者分析Android 11增加的scudo、ART虚拟机的RosAlloc时都会有似曾相识的感觉。

市面上已经有一些分析jemalloc的优秀文章（可参考文末链接）。本文将本着“一图胜千言”的原则，阐述过往文章未提及或未表达清楚的地方，读者可以对比参照阅读。本文未特别标明版本的地方，都将围绕4.x版本代码展开分析。4.x是目前Android最广泛使用的大版本，理解这一内容对了解jemalloc的发展历程很有帮助。

Size Class

不知你是否曾经有过这样的疑问：malloc调用是有大小的，但free的时候并没有传参大小，内存分配器如何管理每次的内存请求？对于jemalloc来说，答案是：不需要存储每次malloc请求的具体大小，每个内存块会对齐相应的档位，将内存块组织在精心设计的存储结构之中；内存释放时只需要对指针地址执行位运算，即可找到存储对应内存块的区域，再将相应区域的metadata信息标记为已释放。

对比其他内存分配器，jemalloc的显著特点就是size class的设计更为精细。在jemalloc 4.x及之前的版本里，内存申请被分为三个档位：small、large和huge，在5.x版本中缩减为只有small和large两个档位。用户程序每次的内存申请都会被对齐到相应的档位，比如申请4个字节，实际上内存分配器会返回的是一个8字节的内存块，申请12字节返回的是一个16字节的内存块，具体如下图：

仔细观察上图，可以看出一些档位分布的规律：从第三个group的160字节档位开始，每四个档位为一个group，同个group内部size class档位之间的差值叫做spacing，翻译为步长，相邻两个group之间的spacing是成倍递增的关系，每个size class都能在下一个group内找到与之2倍大小的档位，这就可以在分割合并内存块时，使用本系列文中第一篇文章中介绍的buddy allocator算法。在源码构建过程中，此size class表会通过脚本生成size_class.h头文件，内部包含一个对照表，给定任意requestSize都可以在常数时间内获取相应的size class index。

存储结构

内存分配器的核心设计是通过高效的数据结构，对所有的内存块进行组织管理，若想透彻了解任一内存分配器，首先需了解的就是它的存储结构。接下来介绍下jemalloc的核心存储结构，部分内容前后会有交叉，需要对照着理解。

Arena

Arena本意是竞技场，在jemalloc里是指最大的内存管理单元。arena之间的内存是相互独立的，即不同arena有独立的地址空间。jemalloc会将分配内存的线程和arena绑定，承担整个线程生命周期之内的申请与释放，如下图：

每个Arena可以看做一个独立的分配个体，其组织内存的结构的从大到小依次是：Chunk、Run、Page和Region，存储结构之间层级结构如下图（注：出于简化考虑，这里忽略了redzone）。

chunk和region是内存相关程序的常用命名，但在不同场景下的含义却有很大差异，如：chunk在dlmalloc中代表单个基本的内存块，而在jemalloc中则是包含多个内存块的大范围地址区间；region在Android拷贝GC中是比较大范围的地址区间，但在jemalloc里是最小的内存块分配单位。因此，请读者先暂时忘记chunk和region在其他领域的含义，在jemalloc中：chunk > run > region。

接下来就按照从大到小的顺序依次介绍这些结构。

Chunk

chunk是jemalloc向操作系统申请和释放page的执行入口，从进程地址空间的角度来看，arena可以理解为是由若干chunks组成的，如下图：

图中：

• 灰色代表不可用的chunk(非jemalloc管理vma)

• 绿色代表已分配的chunk

• 白色代表未分配的chunk

chunk直接或间接地承载了small、large、huge三种级别的档位：

• 对于small和large，通过chunk内部的run来完成分配，具体细节下一节再展开；

• 对于huge allocation，由chunk本身组成，返回malloc请求的就是chunks首地址

先来看huge allocation，如仔细观察上图，会发现图中绿色区域包含了两种：arena占用的和huge占用的。这是因为在4.0之前，jemalloc的huge allocation都是独立于arena的，上图出自2006年的论文《A scalable concurrent malloc(3) implementation for freebsd》；在2015年之后，huge allocation变更为从属于arena，由arena管理huge allocation。huge allocation的freelist组织形式为一颗按照地址排序的红黑树，分配内存时优先从低地址选择空闲内存块，更多分配的细节将在下文展开。

chunk的基地址按配置的大小对齐，给定任一内存地址，都可以在常数时间通过位运算计算出chunk基址，例如在Android的默认配置2M大小下，在32位平台只需要前11位地址，就可以对chunk进行编址，代码如下：

Run

chunk由若干大小相同亦或不同的run组成，然后通过run来放置small/large allocation，参考上图：

• 对于small allocation，run由大小相同的一组region组成，称之为small run，用户程序申请的small allocation返回的就是region，具体为region的首地址(不考虑readzone)；

• 对于large allocation，run由自身组成，称之为large run，用户程序申请的large allocation返回的就是run本身，具体为run的首地址(不考虑cache-oblivious)；

chunk和small/large run的结构关系：

如上图，在chunk内部维护的metadata分为了chunk header和run header，chunk header记录chunk内部page和run的映射关系、分配状态、size class大小等，run header记录small run内部region的分配状态，这些metadata直接或间接构成了jemalloc的freelist。

在上篇文章里，介绍了显式(explicit)和隐式(implicit)两种freelist，使用显式freelist查找空闲内存块取链表头即可，非常高效，但是会有内存安全的问题，因为分配给用户的内存块和内存分配器自身的metata混在了一起，很容易破坏分配器内部结构，干扰后续的内存分配，带来极大的安全隐患，小则游戏外挂无限金币，大则导致真实的资金损失，这显然是无法接受的。

jemalloc没有使用显式freelist，直接返回region或者run作为malloc请求的内存，用户程序申请的内存和分配器内部结构分离，规避安全风险，并在基础的隐式freelist上做了性能增强，具体为：

• 对于small allocation，在run header存储bitmap，来管理small run内的空闲region。在bitmap内，region的分配状态通过一个bit标记：0代表已分配，1代表空闲，如使用first-fit策略查找空闲内存块，即是查找bitmap中第一个为1的位置，可以使用编译器built-in函数ffs来完成此操作：

ffs很高效，编译器会根据硬件平台差异由不同的专用指令来实现，感兴趣的同学可以查看https://en.wikipedia.org/wiki/Find_first_set做更多了解，不过bitmap的查找性能开销依然要比显示freelist比依然要大，而且实际上，jemalloc使用的是多层bitmap tree(根据管理内存块的数量调整)，细节会更复杂一些，计算量也会更大，这里就不再展开了。

• 对于large allocation，使用红黑树或paring heap存储可用的run，按照地址进行排序，分配内存时优先取出低地址的run；此freelist结构并没有直接存储在chunk header，而是使用chunk header中存储的map_misc作为外挂节点，存储至arena或bin维护的run的红黑树(5.0之后都改为了paring heap)，并根据大小区分为2类，一个叫bin->runs用于存同size class档位的run，另一个叫arena->runs_avail存储不同size class档位的run。

  
  

这里提出了较多新概念，读者可以先继续往下看，等更多细节后文展开后再返回来看。

前文介绍chunk和run关系的图片，取自2011年的官方文章《Scalable memory allocation using jemalloc》，对应jemalloc的版本还处于3.x时代，4.0版本之后small/large allocation的metadata都合并到了chunk header，来看chunk header的细节：

如上图，具体来看，jemalloc的chunk header使用mapbits存储run和page的映射关系、分配状态、大小等；使用mapmisc存储每个run的metadata；通过一个extent_node_t将chunk挂靠到外部的rbtree或者rtree上。

通过mapbits和mapmisc，可以在常量时间求出任一已分配内存块的metadata，难度并不大但是细节比较繁杂，涉及众多位运算和状态，这里不再做更多展开，mapbits结构：

实际上，一个绝佳学习相关组织原理的代码是google实现的malloc_iterate函数（https://cs.android.com/android/platform/superproject/+/android-10.0.0_r1:external/jemalloc/src/android_je_iterate.c;l=36），此函数可以遍历所有jemalloc分配出去的内存块，会在libmemunreachable中使用，并且此函数内部实现会跟随jemalloc不同版本存储结构的变化而变化，5.0版本的实现代码注释请参考下文，更多细节这里不再展开。

这里再贴出small/large allocation的metadata合并至chunk header后的关系图，此图取自jason evans在2015年的演讲《Tick Tock, malloc Needs a Clock》（笔者没有找到幻灯片原搞，此图为视频截图，低画质请见谅），读者可以和前文2011年版本图片对比，体会chunk内部metadata组织方式的变迁：

结合上文描述，会发现当申请small/large allocation时需要分配相应chunk，并对此chunk进行相关metadata初始化，为了规避每次都新分配chunk并初始化的开销，每个arena会维护一个spare chunk，代表最近一次被释放且完整空闲可用的chunk，叫做arena->spare，虽然spare chunk内部的内存块已经被用户程序free了，但不会被真正的释放，更多细节查看下文内存分配与释放一节。

Bin

在上篇文章里，我们描述过分离式freelist(segregated freelist)，即每个size class对应一个freelist：

在jemalloc里相关概念叫做bin，由bin记录不同size的free regions。

bin的数量和small size class的数量相对应，也即只有small allocation会有对应的bin结构，对照前文 Size Class一节的表格，可以算出Android从bin0，bin1，bin2.... ~ bin35共36个，对应[8, 16，32，48...，14K]的大小。

不过bin并不直接组织region，bin中存储了一个叫做runs的结构称之为bin->runs，包含了所有non-full runs，即有空闲region的run的集合，non-full runs以红黑树维护并按地址排序(后面又改成了pairing heap)，方便快速选择低地址的可用run来分配内存，优先低地址的原则贯穿jemalloc全局设计。

bin和前文介绍的arena/chunk/region之间的关系，如下图：

此图摘自文末参考链接《Structures in jemalloc》一文，这里就不再重画了，小勘误：图中bins的数量配置和Android主流版本略有差异(参考前文介绍android应为36个)；此外图中bin存储的应为runs而非run；图中run的来源可以来自多个chunk而非单一chunk。

除了non-full runs之外，bin还会存储一个相应size class的current run叫做runcur，表示此bin中最近一次产生内存分配且有空闲内存块的run。此设计理念和Arena维护的spare chunk类似，目的是方便快速从中分配region，而无需每次从non-full runs中获取可分配内存的run，因为non-full runs的维护数据结构是红黑树或者paring heap(低版本使用红黑树)，从中删除和增加节点都有性能开销。

结合上述分析，理解bin的存储结构代码：

tcache

由于malloc简洁的api和内存分配器良好的细节封装，导致很多人可能都忽略了一个事实，即内存分配是有锁的，多线程同时分配内存时可能面临着严峻的锁竞争。

jemalloc以其优异的伸缩性（scalability）所著称，2006年初版发布论文的标题就是A scalable concurrent malloc(3) implementation，这里的伸缩性指的是在CPU核数上涨的同时性能依然强劲。时代大背景是，21世纪初CPU频率不能保持过去数年来迅猛上涨的势头，由于功耗墙的存在单核的性能发展遇到了瓶颈，软件设计都需要面向多核CPU进行改造，与此同时内存的价格显著的越来越便宜，内存不用每个字节锱铢必较，允许少量内存浪费来空间换时间，于是内存分配器的改造也应运而生，DRAM的价格趋势参考下图：

jemalloc的设计原则是首先保证伸缩性，不违背此原则的同时尽量保持较低内存开销，而影响伸缩性的最主要因素就是CPU Cache和锁，由操作系统锁带来的开销可能比malloc函数本身耗费的cpu cycle数要大的多。

出于伸缩性（scalability）的考虑，jemalloc官方建议arena个数配置为cpu数量的4倍，但为了节省内存，标准Android的Arena个数固定为2，Android Go版本为1。不同线程绑定不同arena，通过arena之间地址的隔离，能减少多线程之间分配内存时的锁竞争，并且可以规避本系列文章第一篇中曾经提到过的伪共享问题；还有，jemalloc设计了多重粒度的锁，以期用缩小临界区的方式来减轻不同Arena、不同size class之间锁竞争的压力，每个Arena、每个bin都有自己的lock。

除此之外，jemalloc给每个线程增加了tcache，取意thread specific allocation cache。在jemalloc中，当分配一些小内存时，会通过查询tsd(thread specific data)优先从当前线程的tcache中获取内存，整个过程用不了几条指令，也没有锁竞争，速度非常快，这种分配路径通常称之为fast path，与之相对的还有slow path，分配细节下文再展开。tcache已经是现代内存分配器的标配，从scudo的LocalCache、PartitionAlloc的ThreadCache、到虚拟机的TLAB，具体名称可能有差异但核心思想都一样。不过事实上，最先引领tcache设计的是Google著名程序员Sanjay Ghemawat发明的的tcmalloc，参考facebook jemaloc官方文章：

jemalloc’s independent arenas were inspired by lkmalloc, but as time went on, tcmalloc made it abundantly clear that it’s even better to avoid synchronization altogether, so jemalloc also implements thread-specific caching.

和bin的命名类似，tcache对应size class档位的存储结构叫做tcache_bin，简称tbin，所有档位一起构成tbins数组，每个tbin缓存了多个相同大小的region的地址。tcache本身存在tsd，空间不会很大，所以tbin存的只是region在run中的地址，并将其维护成LIFO结构(也就是栈)，称之为avail-stack，分配内存就是弹出栈顶，释放内存就是推入栈中，参考示意图：

tbin是jemalloc代码部分命名有歧义的典型例子，不过命名也是所有软件开发中难题。前文我们有介绍，bin结构只维护small allocation，但其实tbin并不是如此，tbin内存储的内存块size class上限是可以通过编译期间控制的lg_tcache_max参数来配置，jemalloc默认配置大小为32k，已经超过了smallo allocation的档位范围，android对此参数有所调整，下文再展开。

tcache具体代码结构：

tcache_bin具体代码结构：

tbin缓存的region和用户程序通过malloc申请的region，一样都是从run中分配的内存，所以从某种程度来说，这属于内存分配器级别的“预加载”，于是和所有的“预加载”技术类似，tcache也不可避免的面临潜在内存浪费的风险，因此jemalloc设计了一些列措施来控制tcache所缓存的内存大小，具体细节下文“回收内存”一节详细展开。

至此，jemalloc的存储结构已经介绍完毕，以下图作为总结回顾：

上图同样取自Jason Evans2015年演讲《Tick Tock, malloc Needs a Clock》，渣画质见谅。

small分配释放流程

介绍完jemalloc的存储结构，可以开始研究动态的内存申请与释放细节。

small allocation的分配分配流程是最复杂的，也是最全面的，因为其流程包含了run和chunk的分配流程，进而包含了large/huge allocation的分配流程，本节围绕small allocation展开分析。

分配流程

首先，如果以内存块在这些存储结构中流转角度来看，回顾前文可以得出下图：

small allocation最终分配的是jemalloc内的region，从上图静态的来看small allocation都是从tcache分配的，但动态角度来看并不能每次都直接从tcache中分配成功，甚至tcache功能本身都是可以关闭的。当tcache中缓存已经用完，需要发起一次fill操作从arena批量分配region然后往tcache，最差的情况下要经过多次fallback才能分配成功，需要从小至大的依次尝试从多层freelist中分配，笔者把相关大致流程总结为下图：

具体而言，先尝试从tcache中直接分配，从tbin的avail-stack pop栈顶；若tbin栈已空则调用arena_tcache_fill_small，从run中批量分配region重新填充tbin，单次region的分配过程依次按照region -> run -> chunk的顺序执行分配，即：

• 获取一个可用run：

• 先尝试使用bin current run，即bin->runcur

• 再尝试从bin non-full runs，即bin->runs，获取run

• 最后尝试arena->runs_avail中切割

• 如上一步失败，则获取一个chunk，从中切割可用run：

• 先尝试使用spare chunk，即arena->spare

• 再尝试chunk_recycle，复用释放的chunk

1. 优先使用chunk_cached

2. 次优使用chunk_retained

• 最后尝试chun_alloc_mmap，向操作系统申请分配资源

至于tcache单次fill的内存块个数，会受填充系数即lg_fill_div所影响，具体为：每个size class档位即tbin缓存的内存块个数有上限，这个上限叫做ncached_max，每次fill的region个数为  ；填充系数初始值为1，会跟随内存分配频率动态调整，以期最大限度的节省内存，调整的细节参考下文内存回收一节。

笔者在总结这个流程时还是比较辛苦的，因为包含的细节太多，总体上的思路是优先从fast path分配，当上一层分配失败时fallback到下一层的slow path，对应的时间开销已在前面图中用红字标出。这里参考memory hierachy，对jemalloc的多层freelist，做一个不太严谨但非常利于理解的类比：

当我们用IDA插件查看je_malloc函数逻辑分支控制流程图时，会发现还是比较匹配我们前面总结的特点：逻辑分支复杂，从fast path到slow path层层fallback，fast path耗费CPU指令少且条件分支少，如下图：

释放流程

仔细阅读上文，会发现并没有介绍runs_avail和chunk_cached和chunk_retained的来历，因为这涉及了内存释放的流程，这里依然以small deallocation为例来展示jemalloc内存释放的流程。

和内存分配的流程所类似，释放内存的过程，也按照region -> run -> chunk的顺序依次完成释放，在内存分配过程中执行的是「分割」，在内存释放过程中执行的是「合并」，如下图：

可以看出在一次内存释放的过程中，会不断的由小及大，像多米诺骨牌一样将内存一一归还，释放的流程相较于内存分配其实更简单一些，这里从分别region、run和chunk三个维度来看，大致经历的步骤为：

• region归还

• 标记bitmap对应bit位为1即可

• run归还

• 从bin->runs，即bin non-full runs中解绑

• chunk内同为dirty且相邻的run进行合并

• 加入arena->runs_avail，和bin中只会保存对应size class的run不同，runs_avail包含了所有大小的run，并且按照地址进行排序

• 加入arena->runs_dirty，后续执行物理内存清理(purge)时需要

• chunk归还

• 当chunk内的run合并为一个arena_maxrun时归还至spare chunk，保持始终有一个chunk不被释放

• 开始执行chunk_record，缓存释放的chunk后续复用，分为物理内存和虚拟内存两种级别的复用

• 将chunk加入chunk_cached红黑树中，按照大小或地址两种方式排序，方便后续的chunk分配

• 将chunk_cached中的chunk执行「物理内存」清理，这个过程叫做purge，此流程的更多细节后文内存回收一节展开

• 将purge后的chunk与chunk_retained中相邻地址的chunk合并，按照大小或地址两种排序加入chunk_retained

内存释放三个维度由小及大，相应的耗时也逐级增加，这个过程和内存申请时一样是有锁的，这里就不再展开了。

同前面的je_malloc逻辑分支分析一样，若我们用IDA查看je_free函数的逻辑分支控制流程图：

内存回收

进程内存的RSS(物理内存占用)是一个我们非常关注的指标，它与应用的流畅度和稳定性都息息相关，但从上文所述的内存释放基本流程来看，我们会发现和开发者的直觉不同，用户程序调用free后物理内存是并不会立即释放的，jemalloc内有层层缓存的freelist结构。本节将围绕tcache和purge，在上一节已经介绍的释放流程的基础之上，对jemalloc的内存回收机制，做更进一步的介绍，为后续执行RSS优化做铺垫。

tcache内存回收

首先介绍的是tcache flush，此操作与上文所述的tcache fill相对，在free操作时可能会触发。

具体为，当tcache对应size class释放的内存块过多，超过ncached_max上限时导致tbin栈满，就会触发一次flush，把当前缓存的空闲内存块重新释放回run中。ncached_max支持编译时配置，small allocation和large allocation上限分别为TCACHE_NSLOTS_SMALL_MAX和TCACHE_NSLOTS_LARGE控制，jemalloc的默认配置是200和20，但此配置在Android上被改为了为8和16，small请求的tcache被重重砍了一刀。

然后是GC，需要先声明的是，这里的GC指的是调整tcache的缓存数量，减少内存分配器带来的额外内存占用，和Java中的GC不是一个概念。

jemalloc给tcache设计了增量GC和full GC，官方称之为exponential decay approach。大致思路为，在内存申请或释放时触发GC，对线程的申请和分配事件加以记录，目的是反应tcache的使用率，然后在内存申请或释放时触发GC，对长时间未使用的内存块加以回收，具体细节是：

• 增量GC与Full GC

• 内存申请和释放事件计数为ev_cnt

• 当超过TCACHE_GC_INCR时（Android上的配置是228次），触发一次增量gc

• 当超过TCACHE_GC_SWEEP（Android上的配置是8192次），触发一次Full GC

• 增量GC意思是按照size class index的顺序，依次对每个tbin执行gc

• Full GC意思是对所有的size class index的tbin，都执行gc

• 每个tbin单次GC流程

• 引入low_water概念，记录两次tcache gc之间内部使用的最低水线即ncached的最小值，在一次gc过程会清理3/4的low_water数量的region，ncached越小代表tcache使用率越高，tbin->avail为空时low_water置-1

• 引入lg_fill_div概念，用做tcache fill填充系数，控制单次fill分配的region数量，具体数值为ncached_max除以2^lg_fill_div个region

• GC过程中，根据low_water数值，调整lg_fill_div即填充系数

1. 若tbin->low_water > 0，说明此轮GC周期，tbin中有些region并未分配，lg_fill_div++，代表下次填充时要少分配一些

2. 若tbin->low_water < 0，说明说明此轮GC周期，tbin全部分配完了，lg_fill_div--，代表下次填充时要多分配一些

tcache的另外一个清理时机是线程退出，tache会对应全部清除，但仍存在一个badcase：假设一个线程分配了一些内存，然后释放到了tcache，但从此不再分配内存，陷入一种所谓的idle状态，用户预期是已经调用了free，内存是可以释放掉的，但实际上此场景下若线程没有退出，tcache并不会清理。这样就会造成内存的浪费，这种情况需要手动调用mallctl通过"thread.tcache.flush"才能清除。

purge

purge在jemalloc里指的是释放「物理内存」，具体而言，是通过madvise清理在内存释放过程中产生的chunk_cache和runs_dirty中的dirty page，并在purge完成后加入chunk_retained和arena->runs_avail后续继续复用，所以在jemalloc里一个page的生命周期要经历clean -> active -> dirty ->retained这几个环节循环往复。

那么虚拟内存呢？执行purge时，对于run，直接调用mavise即可；对于chunk，可以用munmap或madvise，但munmap作为一个编译时配置从3.0起就被默认关闭了，原因参看这个MR: Disable munmap() if it causes VM map holes.（https://github.com/jemalloc/jemalloc/commit/7ca0fdfb85b2a9fc7a112e158892c098e004385b）

Jason Evans在官方文档里是这么描述的：

munmap() is disabled by default (i.e.--disable-munmap is implied) on Linux, which has a quirk in its virtual memory allocation algorithm that causes semi-permanent VM map holes under normal jemalloc operation.

这意味着jemalloc分配的虚拟内存是永远不会释放的，这一点对Android 32位平台影响较大。

purge的迭代历史比较悠久，参考Jason Evans 在2015年的演讲《Tick Tock, malloc Needs a Clock》，可以看到从2006年起到2015年已经迭代了7、8个版本，但实际上这还没停止。参看下文介绍的jemalloc 5.0，可以看到2015年之后purge依然在变化：

虽然版本一直在变化，但基本都围绕着触发purge时机以及dirty page清理顺序这两个问题展开。jemalloc的purge的方式大体可以分为两类：ratio和decay。

ratio这种模式是早期的jemalloc purge模式，任意一次arena_run_dalloc或者arena_chunk_dalloc时，都有可能会触发purge，在这个过程里jemalloc会把dirty page和active page之间的比例控制在一定范围之内，默认是1:8（通过opt.lg_dirty_mult控制），当dirty page的占比超过比例时就会将多出来的page purge掉。ration模式有一个问题是，由于dirty比例大于1/9时需要清理dirty内存，如果在刚好等于1/9时，不停的执行malloc/free，就会触发不停的purge，没有起到通过预留一定比例dirty page来减少madvise次数的效果。为了规避ratio模式带来的始终在1:8范围波动频繁触发物理内存清理的问题，jemalloc 4.1之后正式上线了decay based purge模式，详情参考这个MR:Implement decay-based unused dirty page purging. #325（https://github.com/jemalloc/jemalloc/issues/325）

这种purge方式会模拟Smoothstep的流程（https://en.wikipedia.org/wiki/Smoothstep），在一个额外的独立线程中使用timer wheel将decay_time分成了200组时间段，每次只释放分组内的部分page，使得dirty page在配置的decay time时间段内平滑的被释放掉，而不是向之前一样一下子全部purge完所有dirty page，这样便可以缓解瞬时CPU使用率猛增的情况。释放曲线如下图：

看起来非常赞，那什么时候触发decay purge呢？和旧版本相比，purge时机做了和很大变动：原有的arena_run_dalloc和arena_chunk_dalloc时并不会每次都触发清理内存了，而是将allocate和deallocate作为tick-tok的事件，超过1000次时，才会主动触发purge：

也就是说，purge参考了类似tcache的做法，通过内存的申请与释放事件来触发purge的时机，于是purge就拥有了和tcache一样的潜在内存浪费的badcase，当内存分配释放事件陷于停滞期时，物理内存的释放是非常不及时的，这会给RSS或PSS统计带来困扰。物理内存释放不及时，是每个内存分配器多少都会有的问题，但jemalloc引入的decay purge在部分特定场景下，会加剧此问题的发生，给开发人员带来不必要的误解。以内存泄露或free/delete内存不释放为关键字，随便搜索一下，就可以看到类似很多案例。这些案例都是内存占用测量不准确的受害者，某种程度上来讲，内存释放后没有立即回收是“反直觉”的。

Google Android默认decay time为0，当decaytime设置为<=0时，会关闭decay继续使用ratio模式，如下图：

但是在Zygote进程PreApplicationInit阶段，又通过mallopt方法设置为1s：

所以可以理解为，普通App进程默认为1s使用decay模式，纯native进程默认为0s使用ratio模式。

jemalloc 5.x版本

从存储结构角度来看，5.0是jemalloc变化最大的版本。自2017年发布以来，至今没有变动更大的新版本发布，感兴趣的同学移步github查看jemalloc 5.0.0的release note，这里大致介绍我们需要关注的jemalloc 5.0几个最大的变化。

chunkless

jemalloc 5.0废弃了chunk的概念，全部使用extent，与之而来的结构变更还有：huge变为只有small和large两种size class；原本从属于chunk的run概念被废弃，small run更名为slab，过去是有slab之实，无slab之名，均为通过bin结构维护small allocation的分离式freelist。

extent不再像chunk一样固定大小，不同的extent之间大小可以不同，extent大小的约束只有需要对齐page size，可以根据需求灵活的进行合并与分割。和原本的chunk一样，extent同时承载了small/large allocation的内存分配器，但不同的是，不像chunk头部有chunk header做metadata，extent内部只存储分配内存，不存储分配器metadata，具体而言：

• small allocation，extent等同于4.0版本的small run称之为slab，内部由一系列相同大小的region组成

• large allocation，非常类似于原本的large run，每个extent放置一个large allocation，返回malloc请求的即是extent首地址

  
  

从chunk迭代至extent，虽然看起来变化巨大，但仔细品味会发现其实有暗线藏在其中，源起于4.0之后radix tree改版变成了lock free的，感兴趣的同学可以查看这个MR:Improve scalability of huge allocation. #189 https://github.com/jemalloc/jemalloc/issues/189，jemalloc从4.0版本开始，为了提高huge allocation的伸缩性，减小了默认的chunk大小(3.0版本chunk的默认大小还是4m)，改为由每个arena管理自己的huge allocation，但其实所有arena的chunks仍统一管理注册和删除由chunks_rtree维护，此次改版jason evans引入了lock free radix tree，开始挖掘rtree的潜力。在4.0版本里huge allocation以chunk为单位在rtree中注册，那么large allocation是不是也能以run为单位注册至rtree？5.0版本extent的变更从此演变而来。

于是，我们研究extent的变更也更通透了一些，将两个版本的freelist结构做一下类比：

• 旧版本arena->chunks_cached和arena->runs_dirty，对应5.0版本的arena->extents_dirty

• 旧版本arena->chunks_retained，对应5.0版本的arena->chunks_retained

• 旧版本arena->runs_avail，对应5.0版本的arena->extents_avail

• 旧版本bin->runcur，对应5.0版本的bin->slabcur

• 旧版本bin->runs，对应5.0版本的bin->slabs_nonfull

与extent变更相关的技术细节和优缺点，都被完整记录到了这个MR: Experiment with chunkless algorithms #360 https://github.com/jemalloc/jemalloc/issues/360，简单总结：

• 优点

• 从原本的每个chunk都要存储metadata，变更为extent只存储分配内存，节省由内存分配器本身带来的overhead

• 和chunk相比，extent要对齐的地址范围变小了，可以更好的与ASLR(Addrees Space Layout Randomization)结合

• 对huge allocation也支持cache-oblivious实现起来也更方便

• 缺点

• 给定任一内存块地址计算metadata，从只需对指针运算几次，变为了每次都需要查询rtree，性能开销更大

• 原有的chunk_hooks系列API都需要被废弃

这里展开介绍一下第一个缺点：

• 5.0之前，由于small和large allocation的metadata信息都是维护在chunk header，给定任一内存指针地址，可以通过指针运算，在常数时间找到相应的metadata信息执行free操作，非常高效，如：

• 判断是否为huge allocation，只需要判断内存块地址是否与chunk大小对齐；

• 计算small/large allocation的size class，只需要计算内存块地址相对chunk基址的偏移量，然后读map bits。

• 5.0之后，不能再通过简单的指针地址运算找到metadata，一切信息获取都需要从extent注册的rtree中查找

参考前面的MR链接：Experiment with chunkless algorithms #360 （https://github.com/jemalloc/jemalloc/issues/360），Jason Evans后续提交了一些列优化代码来弥补从chunk切换至extent带来的性能损失，但由于extent天然的需要使用更复杂的数据结构的限制，其实给jemalloc代码可读性带来了一些影响，新增的代码逻辑没有以前干净了，比如rtree名字听起来只是一个单纯的数据结构，但内部实现已经掺杂了tsd/slab/extent等概念，已经和jemalloc内部结构深度融合了，笔者初次研究时琢磨了很久，有机会可以单独再开一篇文章介绍，感兴趣的读者可以对比两个版本Google Android malloc_iterate的实现，5.0版本的实现

（https://cs.android.com/android/platform/superproject/+/android-10.0.0_r1:external/jemalloc_new/src/android_je_iterate.c;l=20），简单注释：

和extent一同变更的还有红黑树全面废弃，取而代之的是 pairing heap，非本文重点不再展开。

two-phase decay

前文有述，jemalloc会优先使用madvise执行物理内存释放，Linux平台使用madvise有MADV_DONTNEED和MADV_FREE两种方式，5.0之前只会选择其中一种来执行物理内存释放。

jemalloc 5.0将旧有purge的流程程优化为了two phase purge，page释放的状态变化从dirty -> clean两种状态之间的切换，变成了dirty -> muzzy -> clean三种状态的切换，具体为：

• dirty -> muzzy，lazy-purging，madvise的advice:MADV_FREE，由操作系统控制

• muzzy -> clean，forced-purging，madvise的advice:MADV_DONTNEED，强制释放

Google Android的定制优化

在2014年，Christopher Ferris首次将jemalloc 3.6引入AOSP bionic代码树，此后一直迭代多年，直至2020年最后一个版本jemalloc 5.1，这之间的多个版本Google都有相应的定制化配置策略，本节将汇总这些定制配置，并阐述相应修改背后的考量和潜在优化空间。

Android内存分配器版本对照

这里对不同Android版本的内存分配器做了一个汇总，需要注意的是这只代表AOSP，国内ROM会根据硬件实际情况做调整，如下表：

Android 6.0首次集成

首次集成时，在arena_maybe_purge时，执行了ANDROID_ALWAYS_PURGE的策略，即忽略ratio模式active:dirty比例的限制，立即执行物理内存释放：

本来为了伸缩性，jemalloc默认Aren数量是逻辑CPU的4倍，在android被修改为了固定2个arena；tcache small allocation数量从200削到了8，large allocation从20削减到了16，削减幅度较大；但tcache缓存的size class上限有提升，从默认的32k提升到了64k，通过编译选项配置：

可以看出，首次集成时Android以节省内存为主，对大部分默认配置进行了削减，除了ALWAYS_PURGE其他配置一直沿用至今。

Android 7.0 ~ Android 9.0

前文有提到，jemalloc 4.0的时候，huge allocation不再独立于arena，实际上是由每个arena维护自己的chunk_cached/chunk_retained，这会增大虚拟内存占用的开销，对此在32位平台，Android jemalloc有一个定制修改是，会强制从第一个arena分配，进而保证huge allocation的chunk_cached/chunk_retained只保存从属于第一个arena的：

此外，从4.1版本开始，jemalloc逐渐使用decay模式替代旧有的ratio模式来执行purge，decay模式会有前文我们提过的物理内存释放不及时的问题，且bitmap从Android 8.0起使用native内存执行分配，占据了大量native内存，因此Google在Android 9.0时增加了一个逻辑是，当bitmap执行析构函数时，在free调用之外，还主动调用purge清理物理内存：

Android 10升级5.1.0

Android 10版本进行了jemalloc大版本升级：集成jemalloc 5.1，此版本Google在前面的定制配置的基础上，额外加了一个宏定义把tcache stat的nrequests统计功能阉割了，按照官方数据这样每个线程能省2k内存，如图：

Android 11禁止32位retain

在android 11谷歌自己也发现了32位有虚拟内存占用过高的问题，默认把虚拟内存不释放的开关给关了，然而在android 11及以上默认已经使用scudo内存分配器了，只有在Android Go这种使用低端硬件的版本上才会继续使用jemalloc。

小结

至此，jemalloc原理的介绍已接近尾声了，可以发现jemalloc是一款设计非常精巧的分配器：首先它强调的是伸缩性，通过层层递进的freelist缓存组织，最大限度地快速响应内存分配释放请求；其次是通过一以贯之的优先低地址、分割合并内存块的原则，保证低碎片。

不过，jemalloc从诞生之日起，除了早年的Firefox，更多是基于服务器端的场景设计的，服务器和消费者终端的的硬件配置相差悬殊，无论从单进程堆内存使用量还是计算任务类型来看都有较大差异，虽然jemalloc考虑了通用性可以在客户端使用，但通用与定制在性能优化领域往往是互斥的因素，必须在通用性和定制性之间做出权衡。

Google的定制主要出于节省整机内存的考虑，单纯的大幅削减了arena的数量和tcache的缓存容量，并不会根据客户端的堆内存规模、线程活跃度、高低端设备分级等单独调优，仍有些点可以进一步挖掘优化。在下一篇文章中，我们将具体介绍，基于Android客户端领域场景内分配器定制优化实践。

本文章较长细节较多，阅读下来还是比较辛苦的，但是只有啃下这块硬骨头后，才能在内存优化中走的更远，这里和所有坚持读完的同学共勉，欢迎指出错误，共同进步。

薛秋实、芦航、王连宝、韩亚慧等人对本文提出了不少富有建设性的修改意见，在此致谢。

参考资料

[1]A scalable concurrent malloc(3) implementation for freebsd: https://papers.freebsd.org/2006/bsdcan/evans-jemalloc/

[2]Scalable memory allocation using jemalloc: https://engineering.fb.com/2011/01/03/core-data/scalable-memory-allocation-using-jemalloc/

[3]Tick Tock, malloc Needs a Clock: https://dl.acm.org/doi/10.1145/2742580.2742807

[4]Structures in jemalloc: https://medium.com/iskakaushik/eli5-jemalloc-e9bd412abd70

[5]Inside of jemalloc: https://www.cnblogs.com/vector03/p/5182730.html

[6]A Tale of Two Mallocs: On Android libc Allocators – Part 2 – jemalloc: https://blog.nsogroup.com/a-tale-of-two-mallocs-on-android-libc-allocators-part-2-jemalloc/

[7]CENSUS Shadow: https://census-labs.com/media/shadow-infiltrate-2017.pdf

[8]Freebsd jemalloc manual: https://www.freebsd.org/cgi/man.cgi?query=jemalloc&apropos=0&sektion=0&manpath=FreeBSD+11.4-RELEASE&arch=default&format=html

[9]JeMalloc: https://zhuanlan.zhihu.com/p/48957114

[10]使用 jemalloc profile memory：https://www.jianshu.com/p/5fd2b42cbf3d

[11]jemalloc purge改进：https://youjiali1995.github.io/allocator/jemalloc-purge/

[12]jemalloc源码分析：https://youjiali1995.github.io/allocator/jemalloc/

文章勘误

在上篇文章中，有一处需矫正：“显式的 freelist 查找速度慢，但面对内存破坏更脆弱”——其中“速度慢”更正为“速度快”。

”

欢迎加入

快手主站技术部客户端团队由业界资深的移动端技术专家组成，通过领先的移动技术深耕工程架构、研发工具、动态化、数据治理等多个垂直领域，积极探索创新技术，为亿万用户打造极致体验。团队自2011年成立以来全面赋能快手生态，已经建立起业内领先的大前端技术体系，支撑快手在国内外的亿万用户。

在这里你可以获得：

• 提升架构设计能力和代码质量

• 通过大数据解决用户痛点的能力 

• 持续优化业务架构、挑战高效研发效能

• 和行业大牛并肩作战

我们期待你的加入！请发简历到：

app-eng-hr@kuaishou.com

”