jemalloc 源码解析 - 内存管理

Question

前文对 jemalloc 的核心架构做了详细介绍， 本文重点分析 jemalloc 的内存管理。 jemalloc 采用多级内存分配，引入线程缓存 tcache，分配区 arena 来减少线程间锁的争用， 提高申请释放的效率和线程并发扩展性。前面提到，jemalloc 根据内存对象的大小把其分为 small object，large object 和 huge object, 本文将分别介绍这些内存对象的申请和释放流程。

结构分析

先介绍一下内存管理的层级结构：

如图所示， jemalloc 的内存管理采用层级架构， 分别是线程缓存 tcache, 分配区 arena 和系统内存 memory， 不同大小的内存块对应不同的分配区。每个线程对应一个 tcache, 负责当前线程使用内存块的快速申请和释放， 避免线程间锁的竞争和同步。分配 arena 的具体结构在前文已经提到， 采用内存池的思想对内存区域进行合理的划分和管理， 在有效保证低内存碎片的情况下实现不同大小内存块的高效管理。 system memory 是系统的内存区域。

• small object:当 jemalloc 支持 tcache 时， small object 的分配从 tcache 开始， tcache 不中则从 arena 申请 run 并将剩余区域缓存到 tcache， 若从 arena 中不能分配再从 system memory 中申请 chunk 加入 arena 进行管理，不支持 tcache 时， 则直接从 arena 中申请。
• large object: 当 jemalloc 支持 tcache 时， 如果 large object 的 size 小于 tcache_maxclass，则从 tcache 开始分配， tcache 不中则从 arena 申请，只申请需要的内存块， 不做多余 cache, 若从 arena 中不能分配则从 system memory 中申请。当 large object 的 size 大于 tcache_maxclass 或者 jemmalloc 不支持 tcache 时， 直接从 arena 中申请。
• huge object: huge object 的内存不归 arena 管理， 直接采用 mmap 从 system memory 中申请并由一棵与 arena 独立的红黑树进行管理。

接下来我们基于代码进行详细介绍。

内存分配分析

内存分配函数的入口位于：je_malloc/MALLOC_BODY/imalloc/imalloct

JEMALLOC_ALWAYS_INLINE void *
imalloct(size_t size, bool try_tcache, arena_t *arena)
{
     assert(size != 0);
     if (size <= arena_maxclass)
          /*这里进行 small object 或 large object 的分配*/
          return (arena_malloc(arena, size, false, try_tcache));
     else
         /*这里进行 huge object 的分配*/
          return (huge_malloc(size, false, huge_dss_prec_get(arena)));
}

这里把 huge object 的申请和其他对象进行的分流， 条件是 arena_maxclass， 其中 small object 和 large object 的分配需要通过 tcache 和 arena 进行分配， 如图：

下面我们将分成以下几个部分介绍 jemalloc 内存分配：

• tache 中分配 small object
• arena 中分配 small object
• tache 中分配 large object
• arena 中分配 large object
• 分配 huge object

这里我们先关注 tcache 中 small object 的分配，这里主要要注意的是当 tcache 不中时， 需要调用 arena_tcache_fill_small 从 arena 中申请整块 run 进行分配， run 剩余部分挂靠在 tcache 中使用。

JEMALLOC_ALWAYS_INLINE void *
tcache_alloc_small(tcache_t *tcache, size_t size, bool zero)
{
     ...
     binind = SMALL_SIZE2BIN(size);
     assert(binind < NBINS);
     /*定位到对应的 tbin*/
     tbin = &tcache->tbins[binind];
     size = arena_bin_info[binind].reg_size;
     /如果 tbin 中有 cache 对象， 直接返回/
     ret = tcache_alloc_easy(tbin);
     if (ret == NULL) {
          /*如果 tbin 对应 cache 为空， 则从对应 arena 中提取 run 填充 cache 并返回， 填充操作通过 arena_tcache_fill_small 完成*/
          ret = tcache_alloc_small_hard(tcache, tbin, binind);
          if (ret == NULL)
               return (NULL);
     }
     ...
}

arena 中 small object 的分配：

void * arena_malloc_small(arena_t *arena, size_t size, bool zero)
{
    
   binind = SMALL_SIZE2BIN(size);
   assert(binind < NBINS);
   /*定位到 arena 中对应的 bin*/
   bin = &arena->bins[binind];
   size = arena_bin_info[binind].reg_size;
   malloc_mutex_lock(&bin->lock);
   /*从 bin 取出一个可用的 run 进行内存块的分配中*/
   if ((run = bin->runcur) != NULL && run->nfree > 0)
    /*若 bin 中当前 run 中有空闲内存块可使用， 直接返回*/
    ret = arena_run_reg_alloc(run, &arena_bin_info[binind]);
   else
    /*若 runcur 已满， 则从当前 bin 的 runs（按地址排序的红黑树）中选择地址最低的可用 run*/
    ret = arena_bin_malloc_hard(arena, bin);
   ...   
   return (ret);
}

arena 中 small object 的分配涉及到 run 的管理和分配， 空闲的 run 红黑树顺序的调整已经 run 中 bitmap 状态的改变， 见下图：

tcache 中 large object 的分配与 small object 的分配流程类似， 不同的是定位的 tbin 和处理 cache 不中的方法不同：

• 分配 small object 时, binind = small_size2bin[(s-1) » LG_TINY_MIN]，在 cache 不中时， 会从 arena 得到多个 small objects 进行冗余 cache。
• 分配 large object 时, binind = NBINS + (size » LG_PAGE) - 1， 在 tcache 不中时， 考虑到 large object 内存较大， 做冗余备份过于浪费， 只从 arena 申请一个对象。

JEMALLOC_ALWAYS_INLINE void *
tcache_alloc_large(tcache_t *tcache, size_t size, bool zero)
{
   ...
   size = PAGE_CEILING(size);
   assert(size <= tcache_maxclass);
    
   binind = NBINS + (size >> LG_PAGE) - 1;
   assert(binind < nhbins);
   /*定位到对应的 tbin*/
   tbin = &tcache->tbins[binind];
   /*如果对应的 tbin 中有 cache 对象，直接返回*/
   ret = tcache_alloc_easy(tbin);
   if (ret == NULL) {
      /* 对应的 tbin 中无 cache 时， 直接从 arena 中申请一个 large object, 不像 small object 一次申请多个做 cache  */
      ret = arena_malloc_large(tcache->arena, size, zero);
      if (ret == NULL)
         return (NULL);
   }
   ...
   return (ret);
}​

arena 中 large object 的分配较为简单， 不通过 bin， 直接从对应 chunk 中申请相应大小的对象并通过 run 管理返回。

void * arena_malloc_large(arena_t *arena, size_t size, bool zero)
{
     void *ret;
     UNUSED bool idump;
     /* Large allocation. */
     size = PAGE_CEILING(size);
     malloc_mutex_lock(&arena->lock);
     /*arena 中 large object 不通过 bin 进行管理， 直接从对应 chunk 中申请相应大小的对象并通过 run 管理返回。*/
     ret = (void *)arena_run_alloc_large(arena, size, zero);
     ...
     return (ret);
}

所有的 huge object 通过一棵与 arena 独立的红黑树进行管理:

void *
huge_palloc(size_t size, size_t alignment, bool zero, dss_prec_t dss_prec)
{
     ...
     /*构造一个红黑树节点来管理相应的 large object*/
     node = base_node_alloc();
     if (node == NULL)
          return (NULL);
     /*申请足够的 chunk 并挂靠到前面的红黑树节点下面
 */
     is_zeroed = zero;
     ret = chunk_alloc(csize, alignment, false, &is_zeroed, dss_prec);
     if (ret == NULL) {
          base_node_dealloc(node);
          return (NULL);
     }
     /* Insert node into huge. */
     node->addr = ret;
     node->size = csize;
     malloc_mutex_lock(&huge_mtx);
     /*把对应的红黑树节点插入红黑树*/
     extent_tree_ad_insert(&huge, node);
     ...
     return (ret);
}

内存释放分析

接下来介绍内存释放的过程，刚好与内存申请对应，内存释放函数的入口位于：je_free/ifree/iqalloc/iqalloct/idalloct，

JEMALLOC_ALWAYS_INLINE void
idalloct(void *ptr, bool try_tcache)
{
     arena_chunk_t *chunk;
     assert(ptr != NULL);
     /*基于 small objec 和 large object 的大小小于 chunk,判断对象指针指向对类型 */
     chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
     if (chunk != ptr)
          /*释放 small object 或 large object*/
          arena_dalloc(chunk->arena, chunk, ptr, try_tcache);
     else
          /*释放 huge object*/
          huge_dalloc(ptr, true);
}

JEMALLOC_ALWAYS_INLINE void
arena_dalloc(arena_t *arena, arena_chunk_t *chunk, void *ptr, bool try_tcache)
{
     ...
     if ((mapbits & CHUNK_MAP_LARGE) == 0) {
          /* Small allocation. */
          if (try_tcache && (tcache = tcache_get(false)) != NULL) {
               size_t binind;
               binind = arena_ptr_small_binind_get(ptr, mapbits);
               /*tcache 中释放 small object*/
               tcache_dalloc_small(tcache, ptr, binind);
          } else
                /*arena 中释放 small object*/
               arena_dalloc_small(arena, chunk, ptr, pageind);
     } else {
          size_t size = arena_mapbits_large_size_get(chunk, pageind);
          assert(((uintptr_t)ptr & PAGE_MASK) == 0);
          if (try_tcache && size <= tcache_maxclass && (tcache =
              tcache_get(false)) != NULL) {
                /*tcache 中释放 large object*/
               tcache_dalloc_large(tcache, ptr, size);
          } else
               /*arena 中释放 large object*/
               arena_dalloc_large(arena, chunk, ptr);
     }
}

内存释放的流程刚好与内存分配对应起来， 根据对象的类型和来源的不同考虑不同的释放方法，这里将分为以下几个部分介绍：

• tcache 中释放对象
• arena 中释放 small object
• arena 中释放 large object
• 释放 huge object

tcache 中释放 small object 和 large object 的流程大致相同， 首先定位到对应的 tbin, 如果当前 tbin 的缓存已满， 则调用 tcache_bin_flush_xxx 清除部分缓存， 然后把当前释放的 object 挂靠到缓存列表下面。

JEMALLOC_ALWAYS_INLINE void
tcache_dalloc_xxx(tcache_t *tcache, void *ptr, size_t size)
{
     ...
     /*定位到 tbin*/
     tbin = &tcache->tbins[binind];
     tbin_info = &tcache_bin_info[binind];
     /*若 cache 满了则 flush 掉一半 cache 对象*/
     if (tbin->ncached == tbin_info->ncached_max) {
          tcache_bin_flush_xxx(tbin, binind, (tbin_info->ncached_max >>
              1), tcache);
     }
     assert(tbin->ncached < tbin_info->ncached_max);
     /*把要释放的对象插入 bin 对应 cache 数组，并更新数据*/
     tbin->avail[tbin->ncached] = ptr;
     tbin->ncached++;
}

arena 中 small object 的释放：arena_dalloc_small/arena_dalloc_bin/arena_dalloc_bin_locked:

void
arena_dalloc_bin_locked(arena_t *arena, arena_chunk_t *chunk, void *ptr,
    arena_chunk_map_t *mapelm)
{
     ...
     pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE;
     /*定位到对应的 run*/
     run = (arena_run_t *)((uintptr_t)chunk + (uintptr_t)((pageind -
         arena_mapbits_small_runind_get(chunk, pageind)) << LG_PAGE));
     bin = run->bin;
     binind = arena_ptr_small_binind_get(ptr, mapelm->bits);
     bin_info = &arena_bin_info[binind];
     ...
    /*改变 run 内部对应分配区域的状态*/
     arena_run_reg_dalloc(run, ptr);
    /*针对 run 状态的变化对 bin 进行调整*/
     if (run->nfree == bin_info->nregs) {
          /*run 有只是用一个到变空的状态变化*/
          arena_dissociate_bin_run(chunk, run, bin);
          arena_dalloc_bin_run(arena, chunk, run, bin);
     } else if (run->nfree == 1 && run != bin->runcur)
          /*run 由 full 变成空闲一个的状态变化*/
          arena_bin_lower_run(arena, chunk, run, bin);
     ...
}

arena 中 small object 的释放和申请一样会造成所在 run 空闲状态的变化， 进而导致对应 bin 和 arena 结构的调整，稍微复杂一些， 如图：

arena 的 largel object 的释放跟 bin 没有关系， 只需要把占用的内存页还给 arena 并更新 arena 的状态就可以:arena_dalloc_large/arena_dalloc_large_locked:

void arena_dalloc_large_locked(arena_t *arena, arena_chunk_t *chunk, void *ptr)
{
     /*更新 arena 的 run 的状态*/
     arena_run_dalloc(arena, (arena_run_t *)ptr, true, false);
}

huge object 的释放就是红黑树的删除节点的操作并释放相关内存。

void huge_dalloc(void *ptr, bool unmap)
{
     ...
     /* Extract from tree of huge allocations. */
     key.addr = ptr;
     /*找到对应红黑树节点*/
     node = extent_tree_ad_search(&huge, &key);
     assert(node != NULL);
     assert(node->addr == ptr);
     /*从红黑树中删除节点*/
     extent_tree_ad_remove(&huge, node);
     ...
     /*释放相关内存*/
     chunk_dealloc(node->addr, node->size, unmap);
     base_node_dealloc(node);
}

小结

jemalloc 的内存分配就介绍完毕， 这里做一个简单的总结：

• jemalloc 引入线程缓存 tcache, 分配区 arena 来减少线程间锁的争用，保证线程并发扩展性的同时实现了内存的快速申请释放
• 采用 arena 管理不同大小的内存对象在保证内存高效管理的同时减少了内存碎片
• 引入红黑树管理空闲 run 和 chunk, 相比链表具有了更高的效率
• 在 run 中采用 bitmap 管理可分配区域来实现管理和数据分离， 且能够更快地定位到空闲区域
• 引入了多层 cache， 基于内存池的思想， 虽然增加了内存占用， 但实现了内存的快速申请释放， 除了 tcache，还有 bin 中的 runcur， arena 中的 spare 等。

参考文献

• A Scalable Concurrent malloc(3) Implementation for FreeBSD
• Scalable memory allocation using jemalloc
• jemalloc 原理分析
• 内存分配奥义·jemalloc(一)
• ptmalloc,tcmalloc 和 jemalloc 内存分配策略研究
• 更好的内存管理-jemalloc
• jemalloc 3.6.0 源码