Linux内存管理(四):Jemalloc

1. Jemalloc简介

    jemalloc 是由 Jason Evans 在 FreeBSD 项目中引入的新一代内存分配器。它是一个通用的 malloc 实现,侧重于减少内存碎片和提升高并发场景下内存的分配效率,其目标是能够替代 malloc。jemalloc 应用十分广泛,在 Firefox、Redis、Rust、Netty 等出名的产品或者编程语言中都有大量使用。具体细节可以参考 Jason Evans 发表的论文 《A Scalable Concurrent malloc Implementation for FreeBSD》。

    jemalloc 借鉴了 tcmalloc 优秀的设计思路,所以在架构设计方面两者有很多相似之处,同样都包含 thread cache 的特性。但是 jemalloc 在设计上比 ptmalloc 和 tcmalloc 都要复杂,jemalloc 将内存分配粒度划分为 Small、Large、Huge 三个分类,并记录了很多 meta 数据,所以在空间占用上要略多于 tcmalloc,不过在大内存分配的场景,jemalloc 的内存碎片要少于 tcmalloc。tcmalloc 内部采用红黑树管理内存块和分页,Huge 对象通过红黑树查找索引数据可以控制在指数级时间。

2. 基础知识

2.1 size_class

    每个 size_class 代表 jemalloc 分配的内存大小,共有 NSIZES(232)个小类(如果用户申请的大小位于两个小类之间,会取较大的,比如申请14字节,位于8和16字节之间,按16字节分配),分为2大类:

  • small_class小内存 :

    对于64位机器来说,通常区间是 [8, 14kb],常见的有 8, 16, 32, 48, 64, …, 2kb, 4kb, 8kb,注意为了减少内存碎片并不都是2的次幂,比如如果没有48字节,那当申请33字节时,分配64字节显然会造成约50%的内存碎片

  • large_class大内存:

    对于64位机器来说,通常区间是 [16kb, 7EiB],从 4 * page_size 开始,常见的比如 16kb, 32kb, …, 1mb, 2mb, 4mb,最大是 $2^{62}+3^{60}$

  • size_index (size 索引:

    size 位于 size_class 中的索引号,区间为 [0,231],比如8字节则为0,14字节(按16计算)为1,4kb字节为28,当 size 是 small_class 时,size_index 也称作 binind

2.2 arena

    arena 是 jemalloc 最重要的部分,内存由一定数量的 arenas 负责管理。每个用户线程都会被绑定到一个 arena 上,线程采用 round-robin 轮询的方式选择可用的 arena 进行内存分配,为了减少线程之间的锁竞争,默认每个 CPU 会分配 4 个 arena。

    每个arena内都会包含对应的管理信息,记录该arena的分配情况。arena都有专属的chunks, 每个chunk的头部都记录了chunk的分配信息。在使用某一个chunk的时候,会把它分割成很多个run,并记录到bin中。不同size的class对应着不同的bin,在bin里,都会有一个红黑树来维护空闲的run,并且在run里,使用了bitmap来记录了分配状态。此外,每个arena里面维护一组按地址排列的可获得的run的红黑树。

struct arena_s {
    ...
    arena_chunk_tree_t  chunks_dirty;  // 当前arena管理的dirty chunks

    arena_chunk_t *spare;     // arena缓存的最近释放的chunk, 每个arena一个spare chunk

    size_t nactive;           // 当前arena中正在使用的page数.

    size_t ndirty;            // 当前arana中未使用的dirty page数

    size_t npurgatory;        // 需要清理的page的大概数目
 
    /* 当前arena可获得的runs构成的红黑树,红黑树按大小/地址顺序进行排列。 分配run时采用first-best-fit策略 */
    arena_avail_tree_t runs_avail;

    arena_bin_t bins[NBINS];  // bins储存不同大小size的内存区域
};

2.3 bin

    在arena中, 不同bin管理不同size大小的run,在任意时刻, bin中会针对当前size保存一个run用于内存分配。

struct arena_bin_s {
    malloc_mutex_t  lock;    // 作用域当前数据结构的锁

    arena_run_t *runcur;     // 当前正在使用的run

    /* 
     * 可用的run构成的红黑树, 主要用于runcur用完的时候。在查找可用run时, 
     * 为保证对象紧凑分布,尽量从低地址开始查找,减少快要空闲的chunk的数量。
     */
    arena_run_tree_t runs;

    malloc_bin_stats_t stats;  // 用于bin统计
};

2.4 run 

    每个bin在实际上是通过对它对应的正在运行的Run进行操作来进行分配的,一个run实际上就是chunk里的一块区域,大小是page的整数倍,在run的最开头会存储着这个run的信息,比如还有多少个块可供分配。下一块可分配区域的索引。

struct arena_run_s {

    arena_bin_t *bin;      // 所属的bin 

    uint32_t    nextind;  // 下一块可分配区域的索引

    unsigned    nfree;    // 当前run中空闲块数目
};

  // todo

3. 内存分配

  // todo

4. 内存释放

// todo

5. 内存再分配

// todo

6. 内存GC

// todo

上一篇:ptmalloc、tcmalloc与jemalloc内存分配器对比分析


下一篇:“LevelDB源码解析(1) Arena内存分配器