本篇关键词:TLFS 、内存池 、malloc、free

下载 >> 离线文档.鸿蒙内核源码分析(百篇博客分析.挖透鸿蒙内核).pdf

内存管理相关篇为:

动态分配

本篇开始说一个耳朵听起老茧的概念 动态分配,将分成上下两篇,本篇为上篇,看完能快速理解下篇鸿蒙内核源码对动态内存的具体实现。

  • 鸿蒙内核源码分析(TLFS算法) 结合图表从理论视角说清楚 TLFS 算法
  • 鸿蒙内核源码分析(内存池管理) 结合源码说清楚鸿蒙内核动态内存池实现过程,个人认为这部分代码很精彩,简洁高效,尤其对空闲节点和已使用节点的实现令人称奇。

TLFS 原理

TLSF(Two-Level Segregate Fit) 是一种用于实时操作系统的内存分配算法,用两级结构对空闲块按大小进行划分,采用两级链表/索引的方式来加快查找。详细可查看 >> TLSF 论文

把上图看懂基本能明白 TLFS 的原理,请尝试自己先理解一遍再看本篇。

解读

  • 为方便理解 ,将上图做成(表一),中间过程请查看图表变化

    步骤 操作 一级位图 (FL_bitmap) 二级位图 (SL_bitmaps[]) 空闲链表(大小-虚拟地址)
    第一步 初始阶段 0011 00000000
    00000000
    00100000
    00000010
    109b(0x5625) --> 104b(0x6838)
    38b(0x3457) --> 36b(0xed31)
  • 右边为第一级链表 First List (简称fl)。将空闲内存块的大小根据2的幂进行分类,如(32、64、128、...), 这跟伙伴算法很类似,伙伴算法是物理内存的分配算法,这样做的好处是防止外部碎片化,是否空闲用位图标识 FL_bitmap | 一维数组0011代表 [32-64]、[64-128]这个区间有内存可以申请,例如: malloc(37) 时,查到在区间[32-64]中,为 1代表本次可能可以申请到内存,但具体行不行得进入第二级查看。

  • 中间为第二级链表 Second List (简称sl)。第二层链表在第一层的基础上,按照一定的间隔,线性分段,图中将其分成 8等份,对于[32-64]来说 1/84,对于[64 - 128]来说 1/88,可以确定的是等份也是2的倍数,同样是否空闲用位图标识SL_bitmaps[] | 二维数组 ,每个bit代表是否空闲,图中代表 [36 - 39]有内存可供分配,再查看其空闲链表发现真正可供分配的空间有两块,38 和 36,自然将 38malloc(37) 返回,此时空闲链表中还剩36节点 ,所以 一二级位图数据不会有任何的变化。

  • 左边为空闲链表块,上面挂flsl都为1时的空闲内存块,块大小为区间范围值,图中有两个空闲块 38b --> 36b109b --> 104b,在实际运行过程往往出现同样大小的内存块例如38b --> 36b--> 36b

申请过程

用二次申请说明详细过程

  • malloc(37) ,发现值在区间[32-64]并对应fl的位图为1,说明sl中肯定会有一个1,但并不能保证能申请到。得细看第二步sl发现区间[36 - 39]的位图为1,说明空闲链表中肯定会有一块内存,,但也不能保证大小适合37。再看最后一步,发现有两块内存38b --> 36b,只有38b符合,于是 malloc(37) 的结果是获得了一块大小38b的内存块,相差的一个 1b称为内部碎片,这种碎片无法避免。将(表一)更新为(表二)

    步骤 操作 一级位图 (FL_bitmap) 二级位图 (SL_bitmaps[]) 空闲链表(大小-虚拟地址)
    第一步 初始阶段 0011 00000000
    00000000
    00100000
    00000010
    109b(0x5625) --> 104b(0x6838)
    38b(0x3457) --> 36b(0xed31)
    第二步 malloc(37)
    返回地址0x3457
    0011 00000000
    00000000
    00100000
    00000010
    109b(0x5625) --> 104b(0x6838)
    36b(0xed31)
  • malloc(50),同样落在[32-64]查看fl的位图为1,查看第二步sl只有[36 - 39]的位图为1,而 50 > 39,不能满足所以没必要看第三步,得返回第一步往上走发现[64-128]fl的位图为150 < 64 说明 malloc(50) 这次肯定能申请到内存了,查看[64-128]对应的sl发现[104-111]的位图为1,到第三步发现有109b --> 104b两块,选择其中更小104b的块切割成5054两小块,此时要对54处理挂入空闲链表,54处于fl = [32-64]sl = [52-55]区间,地址为: 0x6838+50=0x686A 。所以将[52-55]区间位图置为1,并挂入空闲链表。将(表二)更新为(表三)

    步骤 操作 一级位图 (FL_bitmap) 二级位图 (SL_bitmaps[]) 空闲链表(大小-虚拟地址)
    第一步 初始阶段 0011 00000000
    00000000
    00100000
    00000010
    109b(0x5625) --> 104b(0x6838)
    38b(0x3457) --> 36b(0xed31)
    第二步 malloc(37)
    返回地址0x3457
    0011 00000000
    00000000
    00100000
    00000010
    109b(0x5625) --> 104b(0x6838)
    36b(0xed31)
    第三步 malloc(50)
    返回地址0x6838
    0011 00000000
    00000000
    00100000
    00100010
    109b(0x5625)
    54b(0x686A)
    36b(0xed31)

    注意此时[32-64]的二级位图变成了 00100010 有两个1

释放过程

同样用二次释放说明详细过程

  • free(0x3457) 从地址可知正是上面的 malloc(37)的内存,与分配切割相对应的是释放有合并的步骤,但malloc(37)虽然申请是37,但其实内核记录的内存块大小是38,所以会找寻地址为 0x3457 + 38 = 0x348F 的地址是否也处于空闲,如果是则合并,由表三可知 并没有 0x348F的空闲块将,而38位于fl = [32-64]sl = [36-39]区间,所以挂回该空闲链表等待后续再分配使用,由此(表三)更新为(表四)

    步骤 操作 一级位图 (FL_bitmap) 二级位图 (SL_bitmaps[]) 空闲链表(大小-虚拟地址)
    第一步 初始阶段 0011 00000000
    00000000
    00100000
    00000010
    109b(0x5625) --> 104b(0x6838)
    38b(0x3457) --> 36b(0xed31)
    第二步 malloc(37)
    返回地址0x3457
    0011 00000000
    00000000
    00100000
    00000010
    109b(0x5625) --> 104b(0x6838)
    36b(0xed31)
    第三步 malloc(50)
    返回地址0x6838
    0011 00000000
    00000000
    00100000
    00100010
    109b(0x5625)
    54b(0x686A)
    36b(0xed31)
    第四步 free(0x3457) 0011 00000000
    00000000
    00100000
    00100010
    109b(0x5625)
    54b(0x686A)
    38b(0x3457) --> 36b(0xed31)
  • free(0x5610) 这里假设内核记录该内存块大小为 0x15,归还的同时会找寻0x5610 + 0x15 = 0x5625 是否有空闲块,发现sl = [104-111]有一块109b空闲块,两块合成一块大小为 109 + 0x15 = 109 + 21 = 130,位于fl = [128-255]sl = [128-143]区间,由此(表四)再更新为(表五)

    步骤 操作 一级位图 (FL_bitmap) 二级位图 (SL_bitmaps[]) 空闲链表(大小-虚拟地址)
    第一步 初始阶段 0011 00000000
    00000000
    00100000
    00000010
    109b(0x5625) --> 104b(0x6838)
    38b(0x3457) --> 36b(0xed31)
    第二步 malloc(37)
    返回地址0x3457
    0011 00000000
    00000000
    00100000
    00000010
    109b(0x5625) --> 104b(0x6838)
    36b(0xed31)
    第三步 malloc(50)
    返回地址0x6838
    0011 00000000
    00000000
    00100000
    00100010
    109b(0x5625)
    54b(0x686A)
    36b(0xed31)
    第四步 free(0x3457) 0011 00000000
    00000000
    00100000
    00100010
    109b(0x5625)
    54b(0x686A)
    38b(0x3457) --> 36b(0xed31)
    第五步 free(0x5610) 0101 00000000
    00000001
    00000000
    00100010
    130b(0x5610)
    54b(0x686A)
    38b(0x3457) --> 36b(0xed31)

总结

TLSF(Two-Level Segregate Fit) 有两大优点:

  • 实时性,执行速度快,只需查询位图就能知道结果,最多查询两次一级位图,时间复杂度为O(1)。
  • 碎片少,浪费少,利用率高,因采用2次幂的方式,切割和合并非常的方便,很少出现外部碎片。

真正的鸿蒙内存动态分配实现过程比这些要复杂些,但有了本文算法基础做铺垫看源码实现会容易很多。

百文说内核 | 抓住主脉络

  • 百文相当于摸出内核的肌肉和器官系统,让人开始丰满有立体感,因是直接从注释源码起步,在加注释过程中,每每有心得处就整理,慢慢形成了以下文章。内容立足源码,常以生活场景打比方尽可能多的将内核知识点置入某种场景,具有画面感,容易理解记忆。说别人能听得懂的话很重要! 百篇博客绝不是百度教条式的在说一堆诘屈聱牙的概念,那没什么意思。更希望让内核变得栩栩如生,倍感亲切。
  • 与代码需不断debug一样,文章内容会存在不少错漏之处,请多包涵,但会反复修正,持续更新,v**.xx 代表文章序号和修改的次数,精雕细琢,言简意赅,力求打造精品内容。
  • 百文在 < 鸿蒙研究站 | 开源中国 | 博客园 | 51cto | csdn | 知乎 | 掘金 > 站点发布,百篇博客系列目录如下。

按功能模块:

基础知识 进程管理 任务管理 内存管理
双向链表
内核概念
源码结构
地址空间
计时单位
优雅的宏
钩子框架
位图管理
POSIX
main函数
调度故事
进程控制块
进程空间
线性区
红黑树
进程管理
Fork进程
进程回收
Shell编辑
Shell解析
任务控制块
并发并行
就绪队列
调度机制
任务管理
用栈方式
软件定时器
控制台
远程登录
协议栈
内存规则
物理内存
内存概念
虚实映射
页表管理
静态分配
TLFS算法
内存池管理
原子操作
圆整对齐
通讯机制 文件系统 硬件架构 内核汇编
通讯总览
自旋锁
互斥锁
快锁使用
快锁实现
读写锁
信号量
事件机制
信号生产
信号消费
消息队列
消息封装
消息映射
共享内存
文件概念
文件故事
索引节点
VFS
文件句柄
根文件系统
挂载机制
管道文件
文件映射
写时拷贝
芯片模式
ARM架构
指令集
协处理器
工作模式
寄存器
多核管理
中断概念
中断管理
编码方式
汇编基础
汇编传参
链接脚本
内核启动
进程切换
任务切换
中断切换
异常接管
缺页中断
编译运行 调测工具
编译过程
编译构建
GN语法
忍者无敌
ELF格式
ELF解析
静态链接
重定位
动态链接
进程映像
应用启动
系统调用
VDSO
模块监控
日志跟踪
系统安全
测试用例

百万注源码 | 处处扣细节

  • 百万汉字注解内核目的是要看清楚其毛细血管,细胞结构,等于在拿放大镜看内核。内核并不神秘,带着问题去源码中找答案是很容易上瘾的,你会发现很多文章对一些问题的解读是错误的,或者说不深刻难以自圆其说,你会慢慢形成自己新的解读,而新的解读又会碰到新的问题,如此层层递进,滚滚向前,拿着放大镜根本不愿意放手。

  • < gitee | github | coding | gitcode > 四大码仓推送 | 同步官方源码。

关注不迷路 | 代码即人生

期间不断得到小伙伴的支持,有学生,有职场新人,也有老江湖,在此一并感谢,大家的支持是前进的动力。尤其每次收到学生的赞助很感慨,后生可敬。 >> 查看捐助名单

据说喜欢 点赞 + 分享 的,后来都成了大神。😃