  关键词：TLFS 、内存池 、malloc、free 内存管理相关篇为: v31.02 鸿蒙内核源码分析(内存规则) | 内存管理到底在管什么 v32.04 鸿蒙内核源码分析(物理内存) | 真实的可不一定精彩 v33.04…
本篇关键词：TLFS 、内存池 、malloc、free
内存管理相关篇为:
v31.02 鸿蒙内核源码分析(内存规则) | 内存管理到底在管什么
v32.04 鸿蒙内核源码分析(物理内存) | 真实的可不一定精彩
v33.04 鸿蒙内核源码分析(虚拟内存) | 虚拟的也是真实的
v34.03 鸿蒙内核源码分析(虚实映射) | 映射是伟大的发明
v35.02 鸿蒙内核源码分析(页表管理) | 映射关系保存在哪
v36.03 鸿蒙内核源码分析(静态分配) | 很简单的一位小朋友
v37.01 鸿蒙内核源码分析(TLFS算法) | 用图解读TLFS原理
v38.01 鸿蒙内核源码分析(内存池管理) | 如何高效切割合并内存块
v39.04 鸿蒙内核源码分析(原子操作) | 谁在守护指令执行的完整性
v40.01 鸿蒙内核源码分析(圆整对齐) | 正在制作中 …
动态分配
本篇开始说一个耳朵听起老茧的概念 动态分配，将分成上下两篇，本篇为上篇，看完能快速理解下篇鸿蒙内核源码对动态内存的具体实现。
鸿蒙内核源码分析(TLFS算法) 结合图表从理论视角说清楚 TLFS 算法
鸿蒙内核源码分析(内存池管理) 结合源码说清楚鸿蒙内核动态内存池实现过程，个人认为这部分代码很精彩，简洁高效，尤其对空闲节点和已使用节点的实现令人称奇。
TLFS 原理
TLSF(Two-Level Segregate Fit) 是一种用于实时操作系统的内存分配算法，用两级结构对空闲块按大小进行划分，采用两级链表/索引的方式来加快查找。详细可查看 >> TLSF 论文 。
把上图看懂基本能明白 TLFS 的原理，请尝试自己先理解一遍再看本篇。
解读
为方便理解 ，将上图做成(表一)，中间过程请查看图表变化
步骤
操作
一级位图 (FL_bitmap)
二级位图 (SL_bitmaps[])
空闲链表(大小-虚拟地址)
第一步
初始阶段
0011
00000000<br>00000000<br>00100000<br>00000010
109b(0x5625) --> 104b(0x6838) <br> 38b(0x3457) --> 36b(0xed31)
右边为第一级链表
1 | First List |
(简称
1 | fl |
)。将空闲内存块的大小根据
1 | 2 |
的幂进行分类，如（32、64、128、…）， 这跟伙伴算法很类似，伙伴算法是物理内存的分配算法，这样做的好处是防止外部碎片化，是否空闲用位图标识 FL_bitmap | 一维数组，
1 | 0011 |
代表
1 | [32-64]、[64-128] |
这个区间有内存可以申请，例如： malloc(37) 时，查到在区间
1 | [32-64] |
中，为
1 | 1 |
代表本次可能可以申请到内存，但具体行不行得进入第二级查看。
中间为第二级链表
1 | Second List |
(简称
1 | sl |
)。第二层链表在第一层的基础上，按照一定的间隔，线性分段，图中将其分成
1 | 8 |
等份，对于
1 | [32-64] |
来说
1 | 1/8 |
为
1 | 4 |
，对于
1 | [64 - 128] |
来说
1 | 1/8 |
为
1 | 8 |
，可以确定的是等份也是
1 | 2 |
的倍数，同样是否空闲用位图标识SL_bitmaps[] | 二维数组 ，每个bit代表是否空闲，图中代表
1 | [36 - 39] |
有内存可供分配，再查看其空闲链表发现真正可供分配的空间有两块，
1 | 38 和 36 |
，自然将
1 | 38 |
给 malloc(37) 返回，此时空闲链表中还剩
1 | 36 |
节点 ，所以 一二级位图数据不会有任何的变化。
左边为空闲链表块，上面挂
1 | fl |
，
1 | sl |
都为
1 | 1 |
时的空闲内存块，块大小为区间范围值，图中有两个空闲块
1 | 38b --> 36b |
，
1 | 109b --> 104b |
，在实际运行过程往往出现同样大小的内存块例如
1 | 38b --> 36b--> 36b |
申请过程
用二次申请说明详细过程
malloc(37) ，发现值在区间
1 | [32-64] |
并对应
1 | fl |
的位图为
1 | 1 |
，说明
1 | sl |
中肯定会有一个
1 | 1 |
，但并不能保证能申请到。得细看第二步
1 | sl |
发现区间
1 | [36 - 39] |
的位图为
1 | 1 |
，说明空闲链表中肯定会有一块内存，，但也不能保证大小适合
1 | 37 |
。再看最后一步，发现有两块内存
1 | 38b --> 36b |
，只有
1 | 38b |
符合，于是**malloc(37)**的结果是获得了一块大小
1 | 38b |
的内存块，相差的一个
1 | 1b |
称为内部碎片，这种碎片无法避免。将(表一)更新为(表二)
步骤
操作
一级位图 (FL_bitmap)
二级位图 (SL_bitmaps[])
空闲链表(大小-虚拟地址)
第一步
初始阶段
0011
00000000<br>00000000<br>00100000<br>00000010
109b(0x5625) --> 104b(0x6838) <br> 38b(0x3457) --> 36b(0xed31)
第二步
malloc(37)<br>返回地址0x3457
0011
00000000<br>00000000<br>00100000<br>00000010
109b(0x5625) --> 104b(0x6838) <br> 36b(0xed31)
malloc(50)，同样落在
1 | [32-64] |
查看
1 | fl |
的位图为
1 | 1 |
，查看第二步
1 | sl |
只有
1 | [36 - 39] |
的位图为
1 | 1 |
，而 50 > 39，不能满足所以没必要看第三步，得返回第一步往上走发现
1 | [64-128] |
的
1 | fl |
的位图为
1 | 1 |
，50 < 64 说明 malloc(50) 这次肯定能申请到内存了，查看
1 | [64-128] |
对应的
1 | sl |
发现
1 | [104-111] |
的位图为
1 | 1 |
，到第三步发现有
1 | 109b --> 104b |
两块，选择其中更小
1 | 104b |
的块切割成
1 | 50 |
，
1 | 54 |
两小块，此时要对
1 | 54 |
处理挂入空闲链表，
1 | 54 |
处于
1 | fl = [32-64] |
，
1 | sl = [52-55] |
区间，地址为: 0x6838+50=0x686A 。所以将
1 | [52-55] |
区间位图置为
1 | 1 |
，并挂入空闲链表。将(表二)更新为(表三)
步骤
操作
一级位图 (FL_bitmap)
二级位图 (SL_bitmaps[])
空闲链表(大小-虚拟地址)
第一步
初始阶段
0011
00000000<br>00000000<br>00100000<br>00000010
109b(0x5625) --> 104b(0x6838) <br> 38b(0x3457) --> 36b(0xed31)
第二步
malloc(37)<br>返回地址0x3457
0011
00000000<br>00000000<br>00100000<br>00000010
109b(0x5625) --> 104b(0x6838) <br> 36b(0xed31)
第三步
malloc(50)<br>返回地址0x6838
0011
00000000<br>00000000<br>00100000<br>00100010
109b(0x5625) <br> 54b(0x686A) <br> 36b(0xed31)
注意此时
1 | [32-64] |
的二级位图变成了 00100010 有两个
1 | 1 |
释放过程
同��用二次释放说明详细过程
free(0x3457) 从地址可知正是上面的 malloc(37)的内存，与分配切割相对应的是释放有合并的步骤，但malloc(37)虽然申请是
1 | 37 |
，但其实内核记录的内存块大小是
1 | 38 |
，所以会找寻地址为 0x3457 + 38 = 0x348F 的地址是否也处于空闲，如果是则合并，由表三可知 并没有 0x348F的空闲块将，而
1 | 38 |
位于
1 | fl = [32-64] |
，
1 | sl = [36-39] |
区间，所以挂回该空闲链表等待后续再分配使用，由此(表三)更新为(表四)
步骤
操作
一级位图 (FL_bitmap)
二级位图 (SL_bitmaps[])
空闲链表(大小-虚拟地址)
第一步
初始阶段
0011
00000000<br>00000000<br>00100000<br>00000010
109b(0x5625) --> 104b(0x6838) <br> 38b(0x3457) --> 36b(0xed31)
第二步
malloc(37)<br>返回地址0x3457
0011
00000000<br>00000000<br>00100000<br>00000010
109b(0x5625) --> 104b(0x6838) <br> 36b(0xed31)
第三步
malloc(50)<br>返回地址0x6838
0011
00000000<br>00000000<br>00100000<br>00100010
109b(0x5625) <br> 54b(0x686A) <br> 36b(0xed31)
第四步
free(0x3457)
0011
00000000<br>00000000<br>00100000<br>00100010
109b(0x5625)<br> 54b(0x686A) <br> 38b(0x3457) --> 36b(0xed31)
free(0x5610) 这里假设内核记录该内存块大小为 0x15，归还的同时会找寻0x5610 + 0x15 = 0x5625 是否有空闲块，发现
1 | sl = [104-111] |
有一块
1 | 109b |
空闲块，两块合成一块大小为 109 + 0x15 = 109 + 21 = 130，位于
1 | fl = [128-255] |
，
1 | sl = [128-143] |
区间，由此(表四)再更新为(表五)
步骤
操作
一级位图 (FL_bitmap)
二级位图 (SL_bitmaps[])
空闲链表(大小-虚拟地址)
第一步
初始阶段
0011
00000000<br>00000000<br>00100000<br>00000010
109b(0x5625) --> 104b(0x6838) <br> 38b(0x3457) --> 36b(0xed31)
第二步
malloc(37)<br>返回地址0x3457
0011
00000000<br>00000000<br>00100000<br>00000010
109b(0x5625) --> 104b(0x6838) <br> 36b(0xed31)
第三步
malloc(50)<br>返回地址0x6838
0011
00000000<br>00000000<br>00100000<br>00100010
109b(0x5625) <br> 54b(0x686A) <br> 36b(0xed31)
第四步
free(0x3457)
0011
00000000<br>00000000<br>00100000<br>00100010
109b(0x5625)<br> 54b(0x686A) <br> 38b(0x3457) --> 36b(0xed31)
第五步
free(0x5610)
0101
00000000<br>00000001<br>00000000<br>00100010
130b(0x5610) <br> 54b(0x686A) <br> 38b(0x3457) --> 36b(0xed31)
总结
TLSF(Two-Level Segregate Fit) 有两大优点：
实时性，执行速度快，只需查询位图就能知道结果，最多查询两次一级位图，时间复杂度为O(1)。
碎片少，浪费少，利用率高，因采用2次幂的方式，切割和合并非常的方便，很少出现外部碎片。
真正的鸿蒙内存动态分配实现过程比这些要复杂些，但有了本文算法基础做铺垫看源码实现会容易很多。
百文说内核 | 抓住主脉络
百文相当于摸出内核的肌肉和器官系统，让人开始丰满有立体感，因是直接从注释源码起步，在加注释过程中，每每有心得处就整理,慢慢形成了以下文章。内容立足源码，常以生活场景打比方尽可能多的将内核知识点置入某种场景，具有画面感，容易理解记忆。说别人能听得懂的话很重要! 百篇博客绝不是百度教条式的在说一堆诘屈聱牙的概念，那没什么意思。更希望让内核变得栩栩如生，倍感亲切。
与代码需不断
1 | debug |
一样，文章内容会存在不少错漏之处，请多包涵，但会反复修正，持续更新，
1 | v**.xx |
代表文章序号和修改的次数，精雕细琢，言简意赅，力求打造精品内容。
百文在 < 鸿蒙研究站 | 开源中国 | 博客园 | 51cto | csdn | 知乎 | 掘金 > 站点发布，鸿蒙研究站 | weharmonyos 中回复 百文 可方便阅读。
按功能模块:
基础知识 >> 双向链表 | 内核概念 | 源码结构 | 地址空间 | 计时单位 | 宏的使用 | 钩子框架 | 位图管理 | POSIX | main函数 |
进程管理 >> 调度故事 | 进程控制块 | 进程空间 | 线性区 | 红黑树 | 进程管理 | Fork进程 | 进程回收 | Shell编辑 | Shell解析 |
任务管理 >> 任务控制块 | 并发并行 | 就绪队列 | 调度机制 | 任务管理 | 用栈方式 | 软件定时器 | 控制台 | 远程登录 | 协议栈 |
内存管理 >> 内存规则 | 物理内存 | 虚拟内存 | 虚实映射 | 页表管理 | 静态分配 | TLFS算法 | 内存池管理 | 原子操作 | 圆整对齐 |
通讯机制 >> 通讯总览 | 自旋锁 | 互斥锁 | 快锁使用 | 快锁实现 | 读写锁 | 信号量 | 事件机制 | 信号生产 | 信号消费 | 消息队列 | 消息封装 | 消息映射 | 共享内存 |
文件系统 >> 文件概念 | 文件故事 | 索引节点 | VFS | 文件句柄 | 根文件系统 | 挂载机制 | 管道文件 | 文件映射 | 写时拷贝 |
硬件架构 >> 芯片模式 | ARM架构 | 指令集 | 协处理器 | 工作模式 | 寄存器 | 多核管理 | 中断概念 | 中断管理 |
内核汇编 >> 编码方式 | 汇编基础 | 汇编传参 | 可变参数 | 开机启动 | 进程切换 | 任务切换 | 中断切换 | 异常接管 | 缺页中断 |
编译运行 >> 编译过程 | 编译构建 | GN语法 | 忍者无敌 | ELF格式 | ELF解析 | 静态链接 | 重定位 | 动态链接 | 进程映像 | 应用启动 | 系统调用 | VDSO |
调测工具 >> 模块监控 | 日志跟踪 | 系统安全 | 测试用例 |
前因后果 >> 总目录 | 源码注释 | 静态站点 | 参考手册 |
百万注源码 | 处处扣细节
百万汉字注解内核目的是要看清楚其毛细血管，细胞结构，等于在拿放大镜看内核。内核并不神秘，带着问题去源码中找答案是很容易上瘾的，你会发现很多文章对一些问题的解读是错误的，或者说不深刻难以自圆其说，你会慢慢形成自己新的解读，而新的解读又会碰到新的问题，如此层层递进，滚滚向前，拿着放大镜根本不愿意放手。
< gitee | github | coding | gitcode > 四大码仓推送 | 同步官方源码，鸿蒙研究站 | weharmonyos 中回复 百万 可方便阅读。
据说喜欢点赞分享的,后来都成了大神。:)
本文标题： 推荐系列-v84.01 鸿蒙内核源码分析(TLFS算法篇) - 图表解读TLFS原理 - 百篇博客分析OpenHarmony源码
本文作者： OSChina
发布时间： 2022年05月11日 05:14
最后更新： 2023年06月29日 07:10
原始链接： https://haoxiang.eu.org/4f1c6787/
版权声明： 本文著作权归作者所有，均采用CC BY-NC-SA 4.0许可协议，转载请注明出处！
