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