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

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

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

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

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

图中：

• 灰色代表不可用的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进行编址，代码如下：

//获取chunk指针#define    CHUNK_ADDR2BASE(a)                        \    ((void *)((uintptr_t)(a) & ~chunksize_mask))

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来完成此操作：

— Built-in Function: int __builtin_ffs (unsigned int x)
Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.
— Built-in Function: int __builtin_ffsl (unsigned long)
Similar to __builtin_ffs, except the argument type is unsigned long.

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

• 对于large allocation，使用红黑树或pairing heap存储可用的run，按照地址进行排序，分配内存时优先取出低地址的run；此freelist结构并没有直接存储在chunk header，而是使用chunk header中存储的map_misc作为外挂节点，存储至arena或bin维护的run的红黑树(5.0之后都改为了pairing 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了，但不会被真正的释放，更多细节查看下文内存分配与释放一节。

在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的维护数据结构是红黑树或者pairing heap(低版本使用红黑树)，从中删除和增加节点都有性能开销。

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

struct arena_bin_s {  /*   * All operations on runcur, runs, and stats require that lock be   * locked.  Run allocation/deallocation are protected by the arena lock,   * which may be acquired while holding one or more bin locks, but not   * vise versa.   */  malloc_mutex_t    lock;
  /*   * Current run being used to service allocations of this bin's size   * class.   */  arena_run_t    *runcur;
  /*   * Heap of non-full runs.  This heap is used when looking for an   * existing run when runcur is no longer usable.  We choose the   * non-full run that is lowest in memory; this policy tends to keep   * objects packed well, and it can also help reduce the number of   * almost-empty chunks.   */  arena_run_heap_t  runs;
  /* Bin statistics. */  malloc_bin_stats_t  stats;};

由于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具体代码结构：

struct tcache_s {  ql_elm(tcache_t) link;    /* Used for aggregating stats. */  uint64_t  prof_accumbytes;/* Cleared after arena_prof_accum(). */  ticker_t  gc_ticker;  /* Drives incremental GC. */  szind_t    next_gc_bin;  /* Next bin to GC. */  tcache_bin_t  tbins[1];  /* Dynamically sized. */  /*   * The pointer stacks associated with tbins follow as a contiguous   * array.  During tcache initialization, the avail pointer in each   * element of tbins is initialized to point to the proper offset within   * this array.   */};

tcache_bin具体代码结构：

struct tcache_bin_s {  tcache_bin_stats_t tstats;  int    low_water;  /* Min # cached since last GC. */  unsigned  lg_fill_div;  /* Fill (ncached_max >> lg_fill_div). */  unsigned  ncached;  /* # of cached objects. */  /*   * To make use of adjacent cacheline prefetch, the items in the avail   * stack goes to higher address for newer allocations.  avail points   * just above the available space, which means that   * avail[-ncached, ... -1] are available items and the lowest item will   * be allocated first.   */  void    **avail;  /* Stack of available objects. */};

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

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

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

介绍完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指令少且条件分支少，如下图：

可以看出在一次内存释放的过程中，会不断的由小及大，像多米诺骨牌一样将内存一一归还，释放的流程相较于内存分配其实更简单一些，这里从分别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优化做铺垫。

• 增量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时，对于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掉。ratio模式有一个问题是，由于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：

JEMALLOC_ALWAYS_INLINE voidarena_decay_ticks(tsd_t *tsd, arena_t *arena, unsigned nticks){  ticker_t *decay_ticker;
  if (unlikely(tsd == NULL))    return;  decay_ticker = decay_ticker_get(tsd, arena->ind);  if (unlikely(decay_ticker == NULL))    return;        // 当 tick 为0时，才 purge，默认是1000次  if (unlikely(ticker_ticks(decay_ticker, nticks)))    arena_purge(arena, false);}

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

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

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

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，非本文重点不再展开。

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

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

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

//frameworks/base/libs/hwui/hwui/Bitmap.cppBitmap::~Bitmap() {    switch (mPixelStorageType) {        case PixelStorageType::External:            ...            break;        case PixelStorageType::Ashmem:            ...            break;        case PixelStorageType::Heap:            free(mPixelStorage.heap.address);            mallopt(M_PURGE, 0);            break;        case PixelStorageType::Hardware:            ...            break;    }    android::uirenderer::renderthread::RenderProxy::onBitmapDestroyed(getStableID());}