jemalloc 5.3.0源码总结

例如：size = 65 ，则 size -1 = 64 = 0b100 0000，最高 bit 在第7位
默认 delta 占２位，最小delta单位占4位，则 64 在的 group 数为 x - bits_delta - bits_min_delta = 7-2-4 = 1，即第1组，
delta 值为0b00 = 0，所以64在bin 中的 bin_index 为 (group{0} *(1 << bits_delta{2})) + delta{0} + 1 = 5

为什么用 size - 1 来计算而不用 size 呢？因为分配大小为 63 或 64 时应该使用相同的bin，而65 则应该属于下一个 bin。
具体可以参考（sz_size2index_compute）

每个size class 的具体情况可以跑这个代码看下

scs = [None] * 1024

class SC:
    
    def __init__(self, lg_max_lookup, lg_page, lg_ngroup, index, lg_base, lg_delta, ndelta) -> None:
        self.index = index
        self.lg_base = lg_base
        self.lg_delta = lg_delta
        self.ndelta = ndelta
        self.unit_size =  (1 << self.lg_base) + (ndelta << self.lg_delta)
        # should from os, default 4096
        self.page_size = (1 << lg_page)
        # small or large
        self.is_small =  (self.unit_size < (1 << (lg_page + lg_ngroup)))
        self.pages = self.get_slab_size() if self.is_small else 0
        # small or large
        self.lg_delta_lookup = lg_delta if (self.unit_size <= (1 << lg_max_lookup))  else 0 

    def get_slab_size(self):
        # at most lg_group * 2 - 1 times
        use_size = self.page_size
        while (use_size % self.unit_size) != 0:
            use_size += self.page_size
        return use_size
    
def size_classes(lg_ptr_size, lg_quantum, lg_tiny_min, lg_max_lookup, lg_page, lg_ngroup):
    lg_base = lg_tiny_min
    lg_delta = lg_base
    ngroup = 1 << lg_ngroup
    ptr_bits = (1 << lg_ptr_size) * 8
	
    index = 0
    ndelta = 0
    nlbins = 0 # max lookup table size
    nbins = 0
    ntiny = 0
    lg_tiny_maxclass = 0
    # tiny size is 2^n enlarging
    while lg_base < lg_quantum:
        sc = SC(index, lg_base, lg_delta, ndelta, lg_page, lg_ngroup, lg_max_lookup)
        scs[index] = sc
        if sc.lg_delta_lookup:
            nlbins = index + 1
        if sc.is_small:
            nbins += 1
        ntiny += 1
        lg_tiny_maxclass = lg_base
        index += 1
        lg_delta = lg_base
        lg_base += 1
    
    if ntiny != 0:
        # first non tiny sc
        # use base/delta = quatum-1 rather than base = quatum and delta = 0
        lg_base -= 1
        first_non_tiny_sc = SC(lg_max_lookup, lg_page, lg_ngroup, index, lg_base, lg_delta, 1)
        scs[index] = first_non_tiny_sc
        lg_base += 1
        index += 1
        lg_delta += 1
        if sc.is_small:
            nbins += 1

    while ndelta < ngroup:
        sc = SC(lg_max_lookup, lg_page, lg_ngroup, index, lg_base, lg_delta, ndelta)
        scs[index] = sc
        index += 1
        ndelta += 1
        if sc.is_small:
            nbins += 1
        
    # other groups
    lg_base = lg_base + lg_ngroup
    while lg_base < ptr_bits - 1:
        ndelta = 1
        ndelta_limit = ngroup - 1 if lg_base == (ptr_bits - 2) else ngroup
        while ndelta <= ndelta_limit:
            sc = SC(lg_max_lookup, lg_page, lg_ngroup, index, lg_base, lg_delta, ndelta)
            scs[index] = sc
            if sc.lg_delta_lookup:
                nlbins = index + 1
                lookup_maxclass = (1 << lg_base) + (ndelta << lg_delta)
            if sc.is_small:
                nbins += 1
                small_maxclass = (1 << lg_base) + (ndelta << lg_delta)
                lg_large_minclass = lg_base + 1 if lg_ngroup > 0 else lg_base + 2
            large_maxclass = (1 << lg_base) + (ndelta << lg_delta)
            print("large_maxclass:", lg_base, ndelta, lg_delta, large_maxclass)
            index += 1
            ndelta += 1
        lg_base += 1
        lg_delta += 1

    print(f"""ntiny: {ntiny}
nlbins: {nlbins}
nbins: {nbins}
n: {index}
lg_tiny_maxclass: {lg_tiny_maxclass}
lookup_maxclass: {lookup_maxclass}
small_maxclass: {small_maxclass}
lg_large_minclass: {lg_large_minclass}
large_minclass: {1 << lg_large_minclass}
large_maxclass: {large_maxclass}

""")
    indexs = []
    bases = []
    deltas = []
    unit_sizes = []
    is_small = []
    pages = []
    print("""index\tbase\tdelta\tunit_size\tis_small\tpages""")
    for i in range(1,1024):
        if scs[i] is None:
            break
        sc = scs[i]
        indexs.append(i)
        bases.append(sc.lg_base)
        deltas.append(sc.ndelta << sc.lg_delta)
        unit_sizes.append(sc.unit_size)
        is_small.append("yes" if sc.is_small else "no")
        pages.append(sc.pages)
        
        print(f"""{i}\t{1 << sc.lg_base}\t{sc.ndelta << sc.lg_delta}\t{sc.unit_size}\t{"yes" if sc.is_small else "no"}\t{sc.pages}""")


LG_SIZEOF_PTR = 3
LG_QUANTUM = 4
SC_LG_TINY_MIN = 3
SC_LG_MAX_LOOKUP = 12 
LG_PAGE = 12
SC_LG_NGROUP = 2
size_classes(LG_SIZEOF_PTR, LG_QUANTUM, SC_LG_TINY_MIN, SC_LG_MAX_LOOKUP, LG_PAGE, SC_LG_NGROUP)

SC_NTINY = (LG_QUANTUM - SC_LG_TINY_MIN)
SC_NGROUP = (1 << SC_LG_NGROUP)
SC_NPSEUDO = SC_NGROUP
SC_LG_FIRST_REGULAR_BASE = (LG_QUANTUM + SC_LG_NGROUP)
SC_NBINS = SC_NTINY + SC_NPSEUDO + SC_NGROUP * (LG_PAGE + SC_LG_NGROUP - SC_LG_FIRST_REGULAR_BASE)
print("SC_NBINS is :", SC_NBINS)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

cache 的 gc

tcache 大概是这样的：
bound --------full---------waterline----empty
|------------------|----------------|-------------|
其中当数量超过full时，触发一次flush，将一半的对象还回去，剩余的数量称为waterline。（除此之外好像在flush后，又分配对象，然后又释放对象，重回到waterline 以后，比waterline 多的对象作为detach 的对象也可以被flush 走，但没看太懂，不太确定）

大小对象的分配与释放

无论大小对象都是先从tcache分配，检查bitmap 看对应大小的对象有没有剩余，如果有直接拿，如果没有才去arena 分配。

小对象（<8k）

小对象分配是在arena 的 bin 上，每个大小的bin都对应着一系列的slab。分配时先从cur_slab分配，如果cur_slab没有了，就取一个nonfull list的slab放在cur_slab上 分配，如果nonfull list 也没有了，就去pac或hpa重新分配slab，挂在cur_slab上分配。当cur_slab分配没了，就会挂在full slab上，在释放时发现它在full slab 上，则放回到nonfull slab 上。分配的指针与 arena 还有 size 的映射存在arena_emap_global 上。

大对象（>8k）

直接走 pac 或 hpa 分配和释放。分配后挂在arena->large_list 上。有arena_emap_global来维护指针到large_list上edata 元素的映射。释放时也是直接从 large list 上拿走。

internal 分配器

arena 有两种：普通＋huge。大于 8m（oversize_threshold） 的对象是在 huge arena 上分配的，小于 8m 的在自己绑定的普通 arena 上分配（除非是用户指定了arena，这时才不会自动转到 huge arena 上分配）。
无论哪种分配器，在分配时都会先尝试用 hpa（hpa 最多 hold 一个大页以下的内存，一般linux 配置是２m），如果超出 hpa 的能力才去普通 pac 分配。

hpa 分配器

hpa 在第一次分配时会申请 128 个 hugepage放在empty list 中。分配时先从 psset 缓存找对应大小的 bitmap，看有没有空闲，如果有就从这个大小的pairing heap上拿最小空闲的一个huge page 下来（这个最小空闲指在这个huge page 上最大的一段连续内存的大小，在所有同组huge page 中是最小的
），如果没有空闲就找下一个更大大小的组，直到找到一个 huge page。根据 huge page的bitmap找到对应的位置，并更新这个 huge page 上最大的没分配范围。
分配出来的内存由edata来记录，并放在shard->emap 上，这是一个前缀树，可以在释放时根据前缀树找到是否有相邻的释放内存，并对它们做合并。
分配后的 huge page 会根据剩余的最大内存重新挂回到psset 上。
释放时内存先从emap 上摘下来，然后在如果它的回归能够让huge page 的最大空闲更新，则把huge page 插入到更合适的 bin 中。释放时如果发现一页完全空了，则可以添加回到psset->empty list中。这些做完后还要标记这个范围到psset->to_purge，会在合适的时间触发purge(实际是提示操作系统不再使用madvice(NONEED))

pac 分配器

pac 也有类似的缓存，但过程不全相同。pac 的页合并不像huge page 那样用bitmap，而是借助 shard_map （见上图） 。pac 在分配时会先找完全满足的bin去分配，如果配置的bin没有空闲，它会找更大一点的bin来split，但只会向上找最多opt_lg_extent_max_active_fit个bin。如果新分配出来的内存对extent 做了切割，那么切割剩的extent 会加入到retained 缓存中。
pac 有三个缓存，dirty / muzzy / retained。分配时先去 dirty cache 找匹配的或能切割的，再去 muzzy 找，如果都找不到，会去 retained 中找，retained 中找不到时才真正去 base 分配，并在切割后将剩余的放到retained 中。
之所以新分配的内存还是有切割可能，是因为pac 每次去 base 进货的单位内存是不断增加的，进货的单位内存有一个 pac->exp_grow 来维护（它有一个增长到的最大 limit值，但应该不起作用，因为limit 值设置为了最大object class size，而这个值对于64位的指针来说就是2^63。）
muzzy 与 dirty 内存的区别： muzzy 的 lazy purge 的时间会更久，dirty 内存在 purge 时，会检查一下可否转为 muzzy，如果能转，则它 purge 的时间会更 delay。这样可以避免频繁向操作系统申请和释放。

base 分配器

base 真正分配 block 时也像 pac 一样有一个申请内存的单位不断增长的机制（由 base->pind_last记录上一次分配的大小级别，下次分配只能比这个级别相等或更大）
真实的分配是由sbrk(dss方式) 或 mmap 系统调用来分配的，默认是先用 mmap 分配(DSS_DEFAULT =“secondary”)，用户可以调整。
dss 比 mmap 快，但没有 mmap 灵活。

bitmap

为了加速查找，bitmap 采用的是多层的形式，对当于一个bit-skip-list。

emap

emap 是用 radix tree 实现的。用于根据指针找到与它分配相关的信息（64位的bit信息）。
通常的 radix tree 为两层（如果减少页大小或扩大虚拟地址长，可导致其为三层），它是以页为单位的索引，64位指针分成三个部分，其中中间的36位作为两层的索引key（即１中间节点层＋１叶节点层）。

中间层每个节点由256k个指针组成，叶子层每个节点由256个指针大小的bit（64bit）组成，这些bit划分了５个部分：

1. 0~8：未使用
2. 9~16：size 的 index，
3. 17~57：extent 元数据 (edata) 指针，由于edata 的地址在分配时是128位对齐过的，低７位一定是0，不会与其它位冲突，又由于它不会大于虚拟地址长度（低48位），因而不会与size index所在位冲突。
4. 58~59：未使用
5. 60~62：页状态，如active dirty 等
6. 63：是否指向一个完整分配来的extent，而不是extent 中切割下来的中位位置（看代码注释好像是有些系统不支持将两个mmap 出来的地址连续但 region 不同的两块内存合并，也就是不允许extent 与前一块邻接的 extent 合并，但没找到这个检查的代码在哪）
7. 64：是否属于slab的extent

emap 在查找时实现了两层 cache，l1 cache 有16个位置，将最后一个非叶子层的key模16得到 l1 cache，如果不命中，则去l2 cache 找， l2 cache 是一个８个位置的数组，需要一个个遍历，如果l2 也不命中，才按照两层 key 去找。
注：　指针与emap 的叶子节点不是一一对应的，当分配一个slab extent 或 large extent ，它可能跨越多页，这时这些页的起始位置都需要作为key插入到radix tree 中，它们对应了相同的value（实现在emap_register_boundary＋emap_register_interior，之所以分成两个是因为boundary 查找需要一层层找，直到叶子节点，而interior 可以在叶子结点一个个遍历插入）。通过将指针align 到页大小来找到它对应的 value。