Jemalloc 深入分析
Evers Chen
Jemalloc 深入分析
Copyright 2013 Spreadtrum Communications Inc. 2
Revision History
Revision
Date
Author
Description
0.1
2018-10-30
Evers.chen
Create
1.0
2019-01-09
Evers.chen
Initial draft
1.1
2019-01-25
Evers.chen
Table of Contents
Revision History ................................................................................................................ 2
Table of Contents .............................................................................................................. 1
1. Introduction ................................................................................................................. 1
1.1. 主要内容 ............................................................................................................ 1
1.2. 介绍 .................................................................................................................... 1
2. Jemalloc 的数据结构 ................................................................................................... 2
2.1. 配对堆 Pairing Heap .......................................................................................... 2
2.1.1. phn_merge_ordered................................................................................ 2
2.1.2. ph_merge_siblings .................................................................................. 3
2.1.3. ph_merge_aux ........................................................................................ 5
2.1.4. ph_merge_children ................................................................................. 5
2.1.5. a_prefix##first ......................................................................................... 5
2.1.6. a_prefix##insert ...................................................................................... 5
2.1.7. a_prefix##remove_first ............................................................................ 5
2.1.8. a_prefix##remove ................................................................................... 5
2.1.9. 配对堆在 jemalloc 中的使用..................................................................... 5
2.2. bitmap 的两种实现 .............................................................................................. 9
2.2.1. 什么时候使用 bitmap TREE .................................................................... 9
2.2.2. bitmap TREE 设计 ................................................................................. 11
2.2.3. bitmap_sfu 的处理过程 .......................................................................... 11
2.2.4. bitmap 初始化过程................................................................................. 12
2.2.5. bitmap_info 初始化过程 ......................................................................... 14
2.2.6. bitmap_full 检测 ..................................................................................... 14
2.2.7. bitmap_set ............................................................................................ 15
2.2.8. bitmap_sfu ............................................................................................ 15
2.3. radix tree 基数树 ............................................................................................. 15
2.3.1. radix tree 的 level 和对应的 subtree 结构 ............................................... 16
2.3.2. radix tree 头文件定义 ............................................................................ 16
2.3.3. radix tree 在 jemalloc 的实现 ................................................................. 18
2.3.4. radix tree gdb 数据 ................................................................................ 22
2.4. red-black tree 红黑树 ...................................................................................... 24
2.4.1. AVL 失去平衡后的 4 种姿态 .................................................................. 25
2.4.2. AVL 旋转 ............................................................................................... 26
Jemalloc 深入分析
Copyright 2013 Spreadtrum Communications Inc. 2
2.4.3. RB TREE 定义 ...................................................................................... 28
2.4.4. RB TREE 插入过程 ............................................................................... 28
2.4.5. RB TREE 删除过程 ............................................................................... 34
2.5. Ring definitions 双向循环链表 ......................................................................... 47
2.5.1. Ring 在 jemalloc 中的使用 ..................................................................... 47
2.6. List definitions 双向链表 .................................................................................. 47
2.6.1. List definitions 在 jemalloc 中的使用 ...................................................... 48
2.7. PRNG 线性同余伪随机数生成器和原子操作的使用 ......................................... 49
2.7.1. 原子操作的使用 ..................................................................................... 49
2.7.2. 线性同余伪随机数生成器 ....................................................................... 49
3. Tcache 实现原理 ....................................................................................................... 53
3.1. TSD:thread specific data 线程局部存储 .......................................................... 53
3.2. Tcache 和 arena 的关系 .................................................................................. 55
3.3. Tcache 的定义 ................................................................................................. 56
3.4. Tcache 的结构 ................................................................................................. 58
3.5. Tcache boot 与初始化 ..................................................................................... 60
3.6. Tcache fill 过程 ................................................................................................ 61
3.7. Tcache 的分配过程 .......................................................................................... 61
3.8. Tcache 的回收 flush 过程 ................................................................................ 62
3.9. Android 对 TCACHE_NSLOTS_SMALL_MAX 配置问题 ................................. 65
4. Jemalloc 的参数和调试相关 ....................................................................................... 66
4.1. Jemalloc 的调试开关 ......................................................................................... 67
4.1.1. JEMALLOC_DEBUG ............................................................................ 67
4.1.2. JEMALLOC_FILL .................................................................................. 67
4.1.3. JEMALLOC_TCACHE .......................................................................... 67
4.2. Android 里 Jemalloc 的初始化参数 ..................................................................... 68
4.2.1. Arena 数量 ............................................................................................ 68
4.2.2. LG_SIZEOF_PTR ................................................................................. 68
4.2.3. NBINS ................................................................................................... 69
4.2.4. Chunk size 大小 .................................................................................... 69
4.2.5. Tcache 相关配置 ................................................................................... 70
4.3. Jemalloc 参数初始化 ......................................................................................... 71
4.3.1. 以 LG_开始的宏常量定义 ...................................................................... 71
4.3.2. map_bias 的初始化 ............................................................................... 72
4.4. Jemalloc 的统计输出 ......................................................................................... 73
5. Jemalloc 多核/多线程分配和互斥锁 ........................................................................... 77
Jemalloc 深入分析
Copyright 2013 Spreadtrum Communications Inc. 3
5.1. 锁的分类 .......................................................................................................... 77
5.2. Tcache 分配的过程 .......................................................................................... 77
5.3. 从 bin 的 runcur 中的分配过程 ......................................................................... 78
5.4. 从 bin 的 runs 中的分配过程 ............................................................................ 78
5.5. arena->runs_avail[i] 中的分配过程 .................................................................. 78
5.6. new chunk 的分配过程 .................................................................................... 78
6. Region size 设计以及和 index 对应关系 ....................................................................... 78
6.1. Region size 步长的设计 ................................................................................... 78
6.2. Region 相关的参数定义（anrdoid 64bits） ......................................................... 79
6.3. SIZE_CLASSES 定义 ..................................................................................... 80
6.4. size2index_tab （用于 reg_size 小于 4096 的快速查找） ..................................... 84
6.5. size2index_compute 的计算过程 ......................................................................... 86
6.6. index2size_compute 的计算过程 ......................................................................... 89
6.7. 步长增加规律分析-浪费率控制 ........................................................................ 91
6.8. index2size_tab ................................................................................................ 91
7. Jemalloc 内存分配释放过程 ....................................................................................... 93
7.1. 从 arena 中分配 small size 内存的过程 ............................................................... 93
7.1.1. tcache 中的分配过程 ............................................................................. 93
7.1.2. 从 bin 的 runcur 中的分配过程 ............................................................... 94
7.1.3. 从 bin 的 runs，arena->runs_avail[i],new chunk 的分配过程 ................. 95
7.1.4. 从 arena bin 的分配 debug 过程 ............................................................ 96
7.2. small size 内存的释放过程 ................................................................................. 97
7.2.1. 释放内存到 tcache 的过程 ..................................................................... 97
7.2.2. 如果 tcache 已满，释放一半 tcache 回各自的 run ................................. 97
7.2.3. 如果 run 已满，释放回 arena->runs_avail[i] .......................................... 97
7.2.4. 如果 chunk 已满，释放 chunk 回 arena->spare .................................... 97
7.2.5. 如果 arena->spare 已保存前面释放的 chunk，则释放 spare 的 chunk .. 98
7.3. 从 arena 中分配 large size 内存的过程 ................................................................ 98
7.3.1. tcache 分配过程 .................................................................................... 98
7.3.2. 非 tcache 的分配过程 ............................................................................ 98
7.4. large size 内存的释放过程 ............................................................................... 100
7.4.1. 释放 large 内存到 tcache 的过程 ......................................................... 100
7.4.2. 如果 tcache 已满，释放一半 tcache 回 arena->runs_avail[i] ............... 100
7.4.3. 如果 chunk 已满，释放 chunk 回 arena->spare .................................. 100
7.4.4. 如果 arena->spare 已保存前面释放的 chunk，则释放 spare 的 chunk 100
7.5. 从 arena 中分配 huge size 内存的过程 .............................................................. 101
