第1页 / 共137页
第2页 / 共137页
第3页 / 共137页
第4页 / 共137页
第5页 / 共137页
第6页 / 共137页
第7页 / 共137页
第8页 / 共137页
jemalloc深入分析.pdf
Revision History
Table of Contents
1. Introduction
1.1. 主要内容
1.2. 介绍
2. Jemalloc的数据结构
2.1. 配对堆Pairing Heap
2.1.1. phn_merge_ordered
2.1.2. ph_merge_siblings
2.1.3. ph_merge_aux
2.1.4. ph_merge_children
2.1.5. a_prefix##first
2.1.6. a_prefix##insert
2.1.7. a_prefix##remove_first
2.1.8. a_prefix##remove
2.1.9. 配对堆在jemalloc中的使用
2.2. bitmap的两种实现
2.2.1. 什么时候使用bitmap TREE
2.2.2. bitmap TREE设计
2.2.3. bitmap_sfu的处理过程
2.2.4. bitmap初始化过程
2.2.5. bitmap_info初始化过程
2.2.6. bitmap_full检测
2.2.7. bitmap_set
2.2.8. bitmap_sfu
2.3. radix tree 基数树
2.3.1. radix tree的level和对应的subtree结构
2.3.2. radix tree头文件定义
2.3.3. radix tree在jemalloc的实现
2.3.4. radix tree gdb 数据
2.4. red-black tree 红黑树
2.4.1. AVL 失去平衡后的4种姿态
2.4.2. AVL 旋转
2.4.3. RB TREE定义
2.4.4. RB TREE 插入过程
2.4.5. RB TREE删除过程
2.5. Ring definitions双向循环链表
2.5.1. Ring在jemalloc中的使用
2.6. List definitions双向链表
2.6.1. List definitions在jemalloc中的使用
2.7. PRNG线性同余伪随机数生成器和原子操作的使用
2.7.1. 原子操作的使用
2.7.2. 线性同余伪随机数生成器
3. Tcache 实现原理
3.1. TSD:thread specific data 线程局部存储
3.2. Tcache和arena的关系
3.3. Tcache的定义
3.4. Tcache的结构
3.5. Tcache boot与初始化
3.6. Tcache fill过程
3.7. Tcache的分配过程
3.8. Tcache的回收flush过程
3.9. Android 对TCACHE_NSLOTS_SMALL_MAX配置问题
4. Jemalloc的参数和调试相关
4.1. Jemalloc的调试开关
4.1.1. JEMALLOC_DEBUG
4.1.2. JEMALLOC_FILL
4.1.3. JEMALLOC_TCACHE
4.2. Android里Jemalloc的初始化参数
4.2.1. Arena数量
4.2.2. LG_SIZEOF_PTR
4.2.3. NBINS
4.2.4. Chunk size大小
4.2.5. Tcache 相关配置
4.3. Jemalloc参数初始化
4.3.1. 以LG_开始的宏常量定义
4.3.2. map_bias的初始化
4.4. Jemalloc的统计输出
5. Jemalloc多核/多线程分配和互斥锁
5.1. 锁的分类
5.2. Tcache分配的过程
5.3. 从bin的runcur中的分配过程
5.4. 从bin的runs中的分配过程
5.5. arena->runs_avail[i] 中的分配过程
5.6. new chunk的分配过程
6. Region size设计以及和index对应关系
6.1. Region size步长的设计
6.2. Region相关的参数定义（anrdoid 64bits）
6.3. SIZE_CLASSES 定义
6.4. size2index_tab （用于reg_size 小于4096的快速查找）
6.5. size2index_compute的计算过程
6.6. index2size_compute的计算过程
6.7. 步长增加规律分析-浪费率控制
6.8. index2size_tab
7. Jemalloc内存分配释放过程
7.1. 从arena中分配small size内存的过程
7.1.1. tcache中的分配过程
7.1.2. 从bin的runcur中的分配过程
7.1.3. 从bin的runs，arena->runs_avail[i],new chunk的分配过程
7.1.4. 从arena bin的分配debug过程
7.2. small size内存的释放过程
7.2.1. 释放内存到tcache的过程
7.2.2. 如果tcache已满，释放一半tcache回各自的run
7.2.3. 如果run已满，释放回arena->runs_avail[i]
7.2.4. 如果chunk已满，释放chunk 回arena->spare
7.2.5. 如果arena->spare已保存前面释放的chunk，则释放spare的chunk
7.3. 从arena中分配large size内存的过程
7.3.1. tcache分配过程
7.3.2. 非tcache的分配过程
7.4. large size内存的释放过程
7.4.1. 释放large内存到tcache的过程
7.4.2. 如果tcache已满，释放一半tcache回arena->runs_avail[i]
7.4.3. 如果chunk已满，释放chunk 回arena->spare
7.4.4. 如果arena->spare已保存前面释放的chunk，则释放spare的chunk
7.5. 从arena中分配huge size内存的过程
7.6. huge size内存的释放过程
8. Chunk
8.1. Chunk结构 （9832E 64位系统）
8.2. Chunk分配过程
8.3. 根据内存地址对chunk头的进一步分析
8.4. map_bits
8.5. map_misc_t
8.6. 从arena找到chunk地址
8.7. Chunk 的register过程
9. jemalloc存储块(region、run、chunk)
9.1. 存储块(region、run、chunk)
9.2. arena_bin_info
9.3. arena_bin_info中的bitmap_info
10. Jemalloc的初始化过程
11. Jemalloc的异常行为？
11.1. Free(P+n)释放部分空间的问题
12. Jemalloc unit test
12.1. Jemalloc的unit test设计
12.2. RB tree的unit test设计
12.3. 和unit test配套的强壮的assert设计
13. Jemalloc 不相关问题
13.1. 32/64位系统数据类型对应字节数
13.2. Assert的使用
13.3. 0xFFLU和0xFFU
13.4. 堆排序
13.5. typedef struct的使用
13.6. big-endian和little-endian格式
14. 参考资料
Jemalloc 深入分析
Evers Chen
Jemalloc 深入分析
Revision History
Date
2018-10-30
2019-01-09
Author
Evers.chen
Evers.chen
Description
Create
Initial draft
2019-01-25
Evers.chen
Revision
0.1
1.0
1.1
Copyright 2013 Spreadtrum Communications Inc. 2
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 深入分析
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
Copyright 2013 Spreadtrum Communications Inc. 2
Jemalloc 深入分析
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
Copyright 2013 Spreadtrum Communications Inc. 3
Jemalloc 深入分析
7.6. huge size 内存的释放过程 ................................................................................ 101
8. Chunk ....................................................................................................................... 102
8.1. Chunk 结构 （9832E 64 位系统） ................................................................. 102
8.2. Chunk 分配过程 ............................................................................................. 102
8.3. 根据内存地址对 chunk 头的进一步分析 .......................................................... 105
8.4. map_bits........................................................................................................ 107
8.5. map_misc_t ................................................................................................... 110
8.6. 从 arena 找到 chunk 地址 ................................................................................. 112
8.7. Chunk 的 register 过程 .................................................................................. 113
9. jemalloc 存储块(region、run、chunk) ..................................................................... 113
9.1. 存储块(region、run、chunk) .......................................................................... 113
9.2. arena_bin_info ................................................................................................. 114
9.3. arena_bin_info 中的 bitmap_info .................................................................... 115
10. Jemalloc 的初始化过程 .......................................................................................... 116
11. Jemalloc 的异常行为？ .......................................................................................... 119
11.1. Free(P+n)释放部分空间的问题 ...................................................................... 119
12. Jemalloc unit test ................................................................................................... 120
12.1. Jemalloc 的 unit test 设计 ................................................................................ 120
12.2. RB tree 的 unit test 设计 ................................................................................. 122
12.3. 和 unit test 配套的强壮的 assert 设计 ............................................................ 126
13. Jemalloc 不相关问题 ............................................................................................. 126
13.1. 32/64 位系统数据类型对应字节数 ............................................................... 126
13.2. Assert 的使用 ................................................................................................ 127
13.3. 0xFFLU 和 0xFFU ......................................................................................... 128
13.4. 堆排序 .......................................................................................................... 128
13.5. typedef struct 的使用 .................................................................................... 130
13.6. big-endian 和 little-endian 格式 .................................................................... 130
14. 参考资料 ................................................................................................................ 130
Copyright 2013 Spreadtrum Communications Inc. 4
Jemalloc 深入分析
1. Introduction
1.1. 主要内容
1. bitmap 查找算法的优化-32 路查找
2. paring heap，配对堆的使用，提高排序效率
3. RB tree 红黑树
4. Tcache 机制
5. 支持原子操作的线性同余伪随机数生成器
6. 动态头长度的计算过程 map_bias
7. Region size 设计以及和 index 对应关系
8. radix tree 基数树
9. 高可靠性编程讨论
10. small/large/huge 内存的分配和释放过程
1.2. 介绍
jemalloc 最初是 Jason Evans 为 FreeBSD 开发的新一代内存分配器, 用来替代原来
的 phkmalloc, 最早投入使用是在 2005 年. 到目前为止, 除了原版 jemalloc, 还有很多变种
被用在各种项目里. Google 在 android5.0 里将 bionic 中的默认分配器从 dlmalloc 替换为
jemalloc, 也是看中了其强大的多核多线程分配能力.
同经典分配器, 如 dlmalloc 相比, jemalloc 在基本思路和实现上存在明显的差别. 比
如, dlmalloc 在分配策略上倾向于先 dss 后 mmap 的方式, 为的是快速向前分配, 但
jemalloc 则完全相反. 而实现上也放弃了经典的 boundary tag. 这些设计牺牲了局部分配
速度和回收效率, 但在更大的空间和时间范围内却获得更好的分配效果.
更重要的是, 相对经典分配器, jemalloc 最大的优势还是其强大的多核/多线程分配
能力. 以现代计算机硬件架构来说, 最大的瓶颈已经不再是内存容量或 cpu 速度, 而是多核
/多线程下的 lock contention(锁竞争). 因为无论 CPU 核心数量如何多, 通常情况下内存只
有一份. 可以说, 如果内存足够大, CPU 的核心数量越多, 程序线程数越多, jemalloc 的分配
速度越快. 而这一点是经典分配器所无法达到的.
本文档基于 jemalloc4.4.0 版本。
Copyright 2013 Spreadtrum Communications Inc. 1
Jemalloc 深入分析
2. Jemalloc 的数据结构
2.1. 配对堆 Pairing Heap
斐波那契堆主要有两个缺点：编程实现难度较大和实际效率没有理论的那么快（由于它的
存储结构和四个指针）。Pairing Heap 的提出就是弥补斐波那契堆的两个缺点——编程
简单操作的时间复杂度和斐波那契堆一样。
Pairing Heap 其实就是一个具有堆（最大堆或最小堆）性质的树，它的特性不是由它的
结构决定的，而是由于它的操作（插入，合并，减小一个关键字等）决定的。
一个指针指向该节点的第一个孩子 lchild，一个指向它的下个兄弟 next，一个指向它的上
个兄弟 prev（对于最左边的兄弟则指向它的父亲），对于第一个孩子，prev 属性表示该
孩子的父结点；对于其他结点，prev 属性表示该结点的左兄弟。
2.1.1. phn_merge_ordered
把大的作为小的树的最左孩子，插入配对树，小的树如果有孩子作为大的树的根节点的兄
弟节点。
Copyright 2013 Spreadtrum Communications Inc. 2
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
