一、背景

jemalloc 5.3.0的介绍，我们已经持续了一段时间了，在 jemalloc 5.3.0的tsd模块的源码分析-CSDN博客 博客里，我们介绍了jemalloc的编译和调试，在 跟踪jemalloc 5.3.0的第一次malloc的源头原因及jemalloc相关初始化细节拓展-CSDN博客 博客里，我们介绍了preload jemalloc后发现的第一次pre main的malloc的源头原因并介绍了jemalloc初始化流程的最一开始几级的调用，在 由jemalloc 5.3.0初始化时的内存分配的分析引入jemalloc的三个关键概念及可借鉴的高性能编码技巧-CSDN博客 博客里，我们借初始化时内存分配的场景，通过watch内存的变化，在揣摩jemalloc的内部行为时，引入介绍了jemalloc里的group和delta这两个关键概念及相关细节，然后，在 jemalloc 5.3.0的base模块的源码详细分析及调用链使用场景的详细分析-CSDN博客 博客里，我们详细展开关键的初始化函数malloc_init_hard里的内存分配有关的逻辑，详细分析了base分配器及非base分配器在初始化时的调用细节情况，虽然介绍的还是初始化时的情况，但是已经把jemalloc的关键逻辑都跑了一遍，和进入main之后的逻辑在慢速路径下是差不多的。我们接下来在 jemalloc 5.3.0的arena概念及arena的选择逻辑分析-CSDN博客 博客里，介绍了jemalloc里非常关键的又一个概念arena，并把arena的选择逻辑透彻和细致地分析了一遍。

在这篇博客里，我们来介绍jemalloc里高性能并发实现里的关键的快速路径分配的逻辑步骤，这个快速路径的分配主要针对的就是小内存分配的场景。

二、小内存分配相关的快速路径分配逻辑详解

虽说是详解，但是不可能做到每个函数都面面俱到。我们会挑出几个关键逻辑来介绍，对于关键逻辑的介绍我们会深入到细节里去，并以调试观测的方式进行验证。

与小内存分配相关入口函数即imalloc_fastpath，我们先在 2.1 里介绍imalloc_fastpath函数，在 2.1 里介绍这个函数时，有些论述是已经进行总结和抽象了，具体对应的细节原因还需要看后面的若干小节。

我们把这个第二章里的分析部分用图画了出来，感兴趣的同学可以阅读或下载资源 https://download.csdn.net/download/weixin_42766184/90414684。

2.1 快速路径核心函数imalloc_fastpath函数整体介绍

imalloc_fastpatch函数，如下图进行了步骤上的描述抽象：

上图里的关于thread_event的分配相关的阈值逻辑见 2.2 一节。

这里，我们看一下上图里的cache_bin_alloc_easy和cache_bin_alloc两个函数，这两个函数最终都是会调用到cache_bin_alloc_impl函数里，唯一的差别在于cache_bin_alloc_easy在调用cache_bin_alloc_impl时传入的第三个参数是false，而cache_bin_alloc传入第三个参数是true。差别就在于上图里总结的，cache_bin_alloc会比cache_bin_alloc_easy进行更多的判断，不仅判断low_water水位和当前stack_head的关系，还会判断empty和当前stack_head的关系。

2.1.1 初始化后empty水位不再变化，low_water水位可能会变化

初始化后，empty水位不再变化，指向到了最高地址，low_water水位在运行中可能会进行调整，但是也是在一些特别的场景如batch_alloc等，一般情况下并不调整。大部分情况下，当相关size的bin被fill过了以后，stack_head就指向到了新分配出来的最低地址上（free的情况也一样），这时候，判断stack_head和low_water就判断出有空间，就不用再去判断empty水位了。

但是，特别情况下，low_water水位会进行移动，也就是减值，这时候，在imalloc_fastpath里进行分配时，还需要判断empty水位，在判断出empty水位还是有空间的话，还是可以分配出来，分配出来以后，还得把low_water水位设成和stack_head一样，避免stack_head更新后，和stack_head和low_water的判断又重新变得不一样了，导致了low_water水位的误判。

弄了cache_bin_alloc_easy和cache_bin_alloc两个函数，就是为了在大部分情况下的快速逻辑尽可能的简单高效，让快速逻辑更加快速。因为大部分情况下，cache_bin_alloc_easy函数就成功返回了。

2.1.2 当stack_head既等于low_water水位又等于empty水位，则走慢速路径逻辑

走慢速路径逻辑就是走fallback_alloc，实际走的就是malloc_default函数。malloc_default函数里，会进行cache bin的fill，具体来说，就是先更新stack_head新的要指向的区域里的地址（2.4里介绍），再更新stack_head指针（2.3里介绍）。

2.2 有关thread_event的allocate相关的阈值调整

thread_event的分配或者释放逻辑，主要是为了合并一些频繁的分配或者释放操作引起更大的逻辑动作，意思就是，在阈值范围内时，用最少的逻辑完成分配或者释放，与之有关的真正和底层打交道的部分，在超过阈值时才触发，这样可以优化整体性能。

2.2.1 初始化时tsd_slow_update里的te_recompute_fast_threshold函数会设置相关初始阈值

关于thread_event我们在之前的博客 跟踪jemalloc 5.3.0的第一次malloc的源头原因及jemalloc相关初始化细节拓展-CSDN博客 里的 3.2.7 一节也提到过，是在tsd_fetch_slow设过thread_event相关的阈值（下图里的te_recompute_fast_threshold函数）。

上图是在初始化时的设置，在实际程序运行中，在分配结束后，也会触发这个threshold的更新。

实际更新的函数是在te_event_advance里。

2.2.2 te_event_advance函数介绍

在te_event_advance里，te_ctx_current_bytes_set是更新的thread_allocated的tsd的数值（下图是第一次分配72704字节时）：

thread_allocated_next_event_fast的更新是在thread_event.c里的te_event_trigger函数里的下图的te_adjust_thresholds_helper函数里进行的更新（从更新的数值来看，这一次的更新逻辑就是原来的值加上这一次分配的数值，原来的值是65536）：

这时的调用栈是：

malloc->imalloc_fastpath->malloc_default->imalloc->imalloc_body->thread_alloc_event->te_event_advance->te_event_trigger，截图如下：

对于大内存的分配，它也是会走到这个更新逻辑里的：

我们看一下小内存分配的情况，进入main之后的第一次的malloc(256)和第二次的malloc(256)都没有改变上图里的thread_allocated_next_event_fast的数值。其中第一次的malloc 256会在imalloc_fastpath里走到fallback_alloc，也就是malloc_default，继而最终在imalloc_body里调用thread_alloc_event函数，继而走到下图的te_event_advance逻辑里：

如上图看到，虽走到了te_event_advance逻辑里，但是并没有调用te_event_trigger函数，因为这一次的usize加上之前的thread_allocated的计数不够thread_event的触发，也就不改变thread_allocated_next_event_fast的数值。但是thread_allocated的数值是发生了改变的，由81920变成了82176，如下图：

2.3 跟踪tcache.bins的buffer的管理逻辑

这里说的tcache.bins是指tsd里的xxx_tcache.bin这个数组，因为暂且关注的是256字节这个size的分配，所以只需要检测下图这个bins下标12的这个结构体里的内容的变化状态，从而来跟踪tcache.bins里的管理逻辑：

看一下这个bins的结构体声明，如下：

我们通过跑例程进行调试的方式来理解，例程在main里分配很多次256字节的内存，我们跟踪的是第一次256字节的分配。

2.3.1 跟踪stack_head数值的变化

jemalloc里的256字节大小对应的主线程的tcache.bins[12]的地址，在我们多次运行情况时是恒定的都是0x00007ffff7e9fbb8，我们新增一个这个位置的数据断点（这个位置也是放tcachce.bins[12]的stack_head的地址）：

先是在tsd_data_init里的子流程里的cache_bin_init里进行了该tsd的tcache bins的stack_head的初始化。

命中数据断点的调用链如下：

stack_head的值由0变成了0x7ffff6c04348：

我们自己看一下设置stack_head的逻辑，如下：

意思就是把当前的传入的cur_offset指针往后偏移info里的ncached_max个指针的大小，作为stack_head的值。

2.3.2 初始化时tcache_init调用了cache_bin_init进行了stack_head的初始化

看一下是谁调用的cache_bin_init，是如何调用的，如下图看到是tcache_init在一个循环里调用的cache_bin_init：

nhbins是41，SC_NBINS是36。

传入给cache_bin_init的第二个info参数是来自于tcache_bin_info数组里的元素，tcache_bin_info是一个全局数组，每个元素是16bit：

如上图，可以看到对应不同的size对应的ind而言，有不同的tcache_bin_info[ind]数值，从c8也就是200开始，序号越大，对应的数值越小，但是里面有个别的有数值增减的波动。这个数值是指一个具体size对应的cache的bin的buffer缓冲几个。对于256字节，这个值是32：

tcache.c里的tcache_init函数里的这个循环，循环到12时，也就是触发了256字节对应的stack_head的数据断点：

经过累加后，如下图，*curr_offset变成了17224，加上alloc这个基址赋值给了stack_head：

low_bits_low_water是stack_head的低16bit，low_bits_full是full_position，即curr_offset在进入时的原始值来加上base，另外，low_bits_empty在初始化时也被赋值成了empty_position也就是stack_head的低16bit。所以，在初始化时，low_bits_full是要比low_bits_low_water和low_bits_empty小的。

2.3.3 在执行malloc(256)时，stack_head是如何被改写的

我们接下来看第一次malloc(256)时，是什么时候改写了stack_head的值。

在第一次malloc(256)时，走到jemalloc_internal_inlines_c.h里，执行了cache_bin_alloc_eay和cache_bin_alloc，这两个函数唯一的区别就是在调用cache_bin_alloc_impl时的入参，前者是传入的adjust_low_water是false，后者传入的是true，这个差别在于cache_bin_alloc_impl里的下图红色框逻辑是否会执行，前者不会走到下红框部分，后者会走到红框部分：

看上面的逻辑可以看到，检查的low_bits != bin->low_bits_low_water和low_bits != bin->low_bits_empty这两个判断，在第一次的malloc(256)进入时，都是不满足条件的。

而由于走不到条件判断触发的逻辑里，success一值都是false，所以，在imalloc_fastpath函数里走到了fallback_alloc里：

在执行fallback_alloc后，在arena_malloc的子逻辑最终调用到cache_bin_finish_fill函数：

在cache_bin_finish_fill函数里，触发了上面说的数据断点，改写了bin12的stack_head值：

如下图看到这时候的empty_position值是0x7ffff6c04348：

上图里的empty_position是通过下图的逻辑进行的计算：

其实就是高位那stack_head的部分，低16位用low_bits_empty的部分。在我们跟的这个时候，low_bits_empty和stack_head的低16位是一样的，所以empty_position就是stack_head在进入cache_bin_finish_fill函数时的值。

再看一下在计算新设的stack_head的值是怎么算出来的：

上图里的nfilled是从下图的tcache_alloc_small_hard函数里计算得到的nfill一路传下来最终传给cache_bin_finish_fill里的：

刚才我们看过binind12对应的tcache_bin_info是32，要右移的数是tcache_slow->lg_fill_div[12]，是1，如下图：

有关的这个lg_fill_div的注释说明如下：

这个16乘以指针的大小，也就是128字节（0x80），也就是tcache的bin一次fill的大小。

回到cache_bin_finish_fill里，bin->stack_head比原来的值减去了0x80，变成了0x7ffff6c042c8：

在完成了cache_bin_finish_fill后，回到arena_malloc调用的tcache_alloc_small继而调用的tcache_alloc_small_hard函数里，如下图，会调用cache_bin_alloc：

cache_bin_alloc继而调用cache_bin_alloc_impl（传入的adjust_low_water是true，如下图），而cache_bin_alloc_impl就是之前分析的判断stack_head指针：

我们看一下在arena_cache_bin_fill_small之后，也就是stack_head指针调整过后，进入cache_bin_alloc_impl后（adjust_low_water是true），是如何走的逻辑：

它会走到下图的逻辑里，因为low_bits是刚更新的stack_head的值也就是0x7ffff6c042c8的低16bit（0x42c8=17096）：

如上图，stack_head进行了更新，更新成了stack_head往后+8字节的位置0x7ffff6c042d0：

于是cache_bin_alloc_impl就成功返回了：

在分析第二个malloc函数的逻辑之前，我们先解决一个问题，就是stack_head指针更新前，得确保新地址上的内容已经正确更新了（stack_head是指针的指针）。

接下里，我们来看一下新地址上的内容是在哪里进行的更新。

2.4 更新stack_head指针前，需要确保新地址上的内容已经正确更新

在arena_malloc的子逻辑里的cache_bin_finish_fill里去更新stack_head指针前，需要确保stack_head要更新的地址上的数值已经进行了正确地设置，我们用数据断点来跟踪是在哪里进行的数值的设置，我们观测stack_head要更新的0x7ffff6c042c8地址上的数值是什么时候设置成如下图里的数值的：

跟踪到相关的逻辑如下图，是也是arena_malloc里的子逻辑调用到了arena_cache_bin_fill_small，继而调用了arena_slab_reg_alloc_batch进行了下图里逻辑的更新：

arena_cache_bin_fill_small函数里，先是调用了arena_slab_reg_alloc_batch进行了更新后的指针指向的内容的更新，继而再调用了cache_bin_finish_fill进行指针更新。

2.5 第二次到第N次malloc(256)的调用逻辑

第二次malloc(256)相比第一次的逻辑简单多了，因为在imalloc_fastpath里的cache_bin_alloc_easy里就走到了cache_bin_alloc_impl里的下图的逻辑里：

就执行了一个简单的stack_head的数值上+8的操作，然后就把原stack_head指向的数值作为返回值返回回去。

我们看一下返回回去的地址，也就是stack_head这个指针数组上依次存的地址是怎样的，可以看到下图左上方框出的stack_head指针数组里存的地址是单调递增的（递增方便cache hardware prefetch）：

我们发现tcache.bins[12]里的low_bits_xxx这几个变量都没有变化：

nrequests是会跟随分配累加的：

接下来，我们看第三次分配，如下图，和第二次分配的更改逻辑一模一样，增大了nrequests，stack_head增大了8：

这是因为stack_head的第16bit数值虽增加8，但是没达到低水位即low_bits_low_water：

我们改写一下调试程序，增加一个循环来malloc(256)，如下图，运行到i=16时，如下图：

为什么观察这一次malloc，因为这时候stack_head的值的第16bit值已经和low_bits_low_water一样了：

这时候，由于stack_head的第16bit既和low_bits_low_water一样，也和low_bits_empty一样，所以如上面几节里分析的那样，它会走到fallback_alloc里。

我们先是猜测后面的fill会填充到0x00007ffff6c042f8地址之后的地址块上，所以在0x00007ffff6c042f8地址上设置数据断点（当然也保留stack_head数值所在地址的这个数据断点）：

为了同时也跟踪影响快速路径逻辑的low_bits_low_water和low_bits_empty两个变量啥时候被修改了，我们再增加了两个数据断点，先通过如下方式算出地址，再增加数据断点：

数据断点有数量上限的，要注意，如下设置了4个就不能运行：

删除一个就可以继续运行：

2.5.1 同一个size的bin在第二次fill时，仍然还是fill的原来的那块区域

调试后发现，我们预期可能会变化的0x7ffff6c04348往后的地址段并没有因为arena_cache_bin_fill_small函数而被fill，而是仍然fill的原来那块区域，也就是如下图的0x00007FFFF6C042C8开始到0x7ffff6c04348前的这块放指针的区域。

我们看一下分配时的计算stack_head指针数组的大小的逻辑（看是不是本身分配的大小就除以2了），如下：

如下图在计算大小时并没有右移1：

改一下了一下main里的逻辑，在malloc(256)后又malloc(320)，因为256的下一个size是320：

想用临近的size的stack_head指针数组的内容所在的地址段，看一下是否真的有一半空间没用，发现确实如此，如下图：

那么这剩下的一半空间不用不是浪费了吗，其实并没有浪费，它是为了free出来的对应size可以放剩下的一半空间里。

下面我们来看一下jemalloc里的free时对cache bin做了什么。

2.6 free(256)的调用逻辑

我们先改写程序如下：

为什么这么改写？有两个思路：

1）第一个for循环，写了16次，是为了让fill的动作执行两次，然后再进行free，可以更容易从调试角度看出还原时的细节

2）第二个for循环，进行free，为了看是否发生刚才说的free时填充另一半空间的情况

如上图，在执行到free的第7次前，发现下图里右边红框部分，从0x00007ffff6c042c8开始往低地址方向，已经变更了6条内容：

我们回头来看在下图时开始做第一次free时的情况：

这时候，因为之前进行了16次malloc(256)，在执行第17次malloc(256)时进行fill，把0x00007ffff6c042c8开始到0x00007FFFF6C04340为止，总共16条地址进行了更新。

发现在free->free_fastpath->cache_bin_dalloc_easy时进行了0x00007ffff6c042c8地址上数值的变更，如下图：

如下图所示，归还的地址正是刚free出来的地址：

我们理解一下这个cache_bin_dalloc_easy里的逻辑：

因为之前的stack_head在进行到第17次分配，触发了refill之后又分配了一次之后，stack_head是0x7ffff6c042d0，stack_head--了以后变成了0x7ffff6c042c8，更新的是0x7ffff6c042c8上的数值，因为0x7ffff6c042c8的这个地址已经被分配出去了，这个位置可以被拿来放新的地址块的地址了，所以free出来的地址就从0x7ffff6c042c8这里开始存放。

我们接下来来看第二次free，第二次free更新到了0x7ffff6c042c8-8的地址上了：

所以，fill了一半就是为了free时可以有地方归还，另外，之前以为fill的是前一半空间，调试下来发现不是，fill的其实是地址较大的一半空间，地址较少的一半空间用于留出来放free出来的地址。

要注意的是，小size的内存分配是直接占满一个delta的，关于delta和group的概念见之前的博客 由jemalloc 5.3.0初始化时的内存分配的分析引入jemalloc的三个关键概念及可借鉴的高性能编码技巧-CSDN博客 里的 2.2.4 一节。

另外，小size没有usize用剩下的内存塞回的动作，不像base里分配的内存有用剩的塞回的逻辑，关于这块base里用剩塞回的逻辑见之前的博客 jemalloc 5.3.0的base模块的源码详细分析及调用链使用场景的详细分析-CSDN博客 里的 2.7.4 一节。

三、可借鉴的高性能编程思路

3.1 减少数据量从而减少数据对cache的占用提高性能

如下代码的注释可以看到，为了减少查表所造成的数据cache的使用，减少了数组的元素的大小，8字节放数组的index信息足够了就用8字节。

另外，关于这个size2index的查表逻辑，jemalloc里其实是又进行了进一步压缩来减少数据cache的使用，我们看下图里的sz_size2index_tab数组的定义部分：

它通过一定的运算，减少了数组元素的个数，从而进一步减少了数组的大小：

因为对于jemalloc里的size2index的逻辑而言，最后的3个bit是无用的。关于这个逻辑相关的group和delta的细节见之前的博客 由jemalloc 5.3.0初始化时的内存分配的分析引入jemalloc的三个关键概念及可借鉴的高性能编码技巧-CSDN博客 里 2.2.4 一节。

3.2 指针有时候可以裁剪高位部分来省数据空间

指针在64位系统上占用了8字节，但是一般来说变动的范围也就16bit就够了，jemalloc里cache_bin_s结构体里几个标记stack使用状况的指针用的就是低16bit，如下图：

3.3 利用cache的硬件prefetch特性

下图是jemalloc以前版本的代码里声明tcache_s结构体的一段注释，利用catch的硬件prefetch特性：

意思就是，如果是手动维护和管理一段内存，按照低地址再到高地址的内存使用顺序，这样可以利用cache的硬件prefetch特性。

在 5.3.0 代码里，cache_bin_s里用stack_head这个指针的数组来管理buffer的使用。从分配的顺序上也是由低地址再到高地址的顺序来使用的。

3.4 把常写入的数据放在临近的地方，从而减少write-back操作

如下图里的注释，cache_bin_s结构体里，将常改的变量stack_head和tstats放一起，来减少write-back操作：

3.5 指针的赋值可以借助rcu的“更新后变更”的思想，通过指针所在地址的变更来减少一些冗余的标志位检查和同步操作

cache_bin_s里维护了一些用于跟踪预分配出来内存的使用情况的指针，当判断出stack_head和low_bits_low_water及low_bits_empty都相等后，进行arena_malloc的tcache alloc的动作时，先是进行了数据的更新， 然后再更新指针。相关的逻辑细节上面也讲到了：

在arena_cache_bin_fill_small函数里，先是调用了arena_slab_reg_alloc_batch进行更新后的指针指向到的内容的更新，继而再调用了cache_bin_finish_fill进行指针更新。

这样的实现方式可借鉴用于一些高并发的场景，借用rcu的思想，预分配数据的buffer实现高性能并发。相关的内核rcu的介绍见之前的博客 rcu的实例、注意事项及原理讲解_rcu 使用实例-CSDN博客。另外，利用这个思想的还有内核顺序锁里可用于nmi handler里的seqcount_latch的实现，见之前的博客 顺序锁的原理和使用注意事项-CSDN博客。

3.6 对于一些频繁访问的内存可以进行pagesize的首地址对齐和size对齐，确保这块数据在访问时不会干扰到别的cacheline，也不让别的cacheline干扰它

jemalloc里在计算各个size class的tcache_bin用的stack_head指针数组的内存对应的内存块所需要分配的总大小时，加了page的alignment，如下图里的注释也解释得比较清楚了：

3.7 使用likely和拆分逻辑步骤，让快速路径的逻辑更加“快速”

jemalloc里的快速路径的函数imalloc_fastpath里的实现，用inline加上likely进行优化的同时，还进行了逻辑上的拆分，如下图注释：

意思就是大部分情况下用到low_water的水位就成功返回了，所以，不需要运行下图里的红框逻辑：

所以，通过两个函数，配合上图里的adjust_low_water的入参的判断，强行把上图里的红色逻辑隔开，否则不加adjust_low_water这段，上图里的红色框因为之前的都是likely，所以红色框里的逻辑的读取会提前进行，另外，红色框里还多了low_bits_low_water的提交修改的动作，在快速路径代码里要尽量避免它。