转 JeMalloc介绍
因为在v2ray一键安装脚本里安装了Jemalloc，所以很好奇，于是网上查了下 20200504
原文链接：https://zhuanlan.zhihu.com/p/48957114
JeMalloc 是一款内存分配器，与其它内存分配器相比，它最大的优势在于多线程情况下的高性能以及内存碎片的减少。
这篇文章介绍JeMalloc-5.1.0版本（release 日期：2018年5月9日）的实现细节。
对于对老版本比较熟悉的人来说，有几点需要说明：
- chunk 这一概念被替换成了 extent
- dirty page 的 decay（或者说 gc） 变成了两阶段，dirty -> muzzy -> retained
- huge class 这一概念不再存在
- 红黑树不再使用，取而代之的是 pairing heap
基础知识
以下内容介绍 JeMalloc 中比较重要的概念以及数据结构。
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，最大是size_index: size 位于size_class中的索引号，区间为 [0，231]，比如8字节则为0，14字节（按16计算）为1，4kb字节为28，当 size 是small_class时，size_index也称作binind
base
用于分配 jemalloc 元数据内存的结构，通常一个base大小为 2mb， 所有base组成一个链表。
base.extents[NSIZES]: 存放每个size_class的extent元数据
bin
管理正在使用中的slab（即用于小内存分配的extent） 的集合，每个bin对应一个size_class
bin.slabcur: 当前使用中的slabbin.slabs_nonfull: 有空闲内存块的slab
extent
管理 jemalloc 内存块（即用于用户分配的内存）的结构，每一个内存块大小可以是N * page_size(4kb)（N >= 1）。每个 extent 有一个序列号（serial number）。
一个extent可以用来分配一次large_class的内存申请，但可以用来分配多次small_class的内存申请。
extent.e_bits: 8字节长，记录多种信息extent.e_addr: 管理的内存块的起始地址extent.e_slab_data: 位图，当此extent用于分配small_class内存时，用来记录这个extent的分配情况，此时每个extent的内的小内存称为region
slab
当 extent 用于分配small_class内存时，称其为slab。一个extent可以被用来处理多个同一size_class的内存申请。
extents
管理extent的集合。
extents.heaps[NPSIZES+1]: 各种page(4kb)倍数大小的extentextents.lru: 存放所有extent的双向链表extents.delay_coalesce: 是否延迟extent的合并
arena
用于分配&回收extent的结构，每个用户线程会被绑定到一个arena上，默认每个逻辑 CPU 会有 4 个arena来减少锁的竞争，各个 arena 所管理的内存相互独立。
arena.extents_dirty: 刚被释放后空闲extent位于的地方arena.extents_muzzy:extents_dirty进行 lazy purge 后位于的地方，dirty -> muzzyarena.extents_retained:extents_muzzy进行 decommit 或 force purge 后extent位于的地方，muzzy -> retainedarena.large: 存放large extent的extentsarena.extent_avail: heap，存放可用的extent元数据arena.bins[NBINS]: 所以用于分配小内存的binarena.base: 用于分配元数据的base
purge 及 decommit 在内存 gc 模块介绍
rtree
全局唯一的存放每个extent信息的 Radix Tree，以extent->e_addr即uintptr_t为 key，以我的机器为例，uintptr_t为64位（8字节），rtree的高度为3，由于extent->e_addr是page(1 << 12)对齐的，也就是说需要 64 - 12 = 52 位即可确定在树中的位置，每一层分别通过第0-16位，17-33位，34-51位来进行访问。...
