本篇关键词:TLFS 、内存池 、malloc、free
内存管理相关篇为:
本篇开始说一个耳朵听起老茧的概念 动态分配,将分成上下两篇,本篇为上篇,看完能快速理解下篇鸿蒙内核源码对动态内存的具体实现。
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) |
右边为第一级链表 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/8
为4
,对于[64 - 128]
来说 1/8
为8
,可以确定的是等份也是2
的倍数,同样是否空闲用位图标识SL_bitmaps[] | 二维数组 ,每个bit代表是否空闲,图中代表 [36 - 39]
有内存可供分配,再查看其空闲链表发现真正可供分配的空间有两块,38 和 36
,自然将 38
给 malloc(37) 返回,此时空闲链表中还剩36
节点 ,所以 一二级位图数据不会有任何的变化。
左边为空闲链表块,上面挂fl
,sl
都为1
时的空闲内存块,块大小为区间范围值,图中有两个空闲块 38b --> 36b
,109b --> 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<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),同样落在[32-64]
查看fl
的位图为1
,查看第二步sl
只有[36 - 39]
的位图为1
,而 50 > 39,不能满足所以没必要看第三步,得返回第一步往上走发现[64-128]
的fl
的位图为1
,50 < 64 说明 malloc(50) 这次肯定能申请到内存了,查看[64-128]
对应的sl
发现[104-111]
的位图为1
,到第三步发现有109b --> 104b
两块,选择其中更小104b
的块切割成50
,54
两小块,此时要对54
处理挂入空闲链表,54
处于fl = [32-64]
, sl = [52-55]
区间,地址为: 0x6838+50=0x686A 。所以将[52-55]
区间位图置为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) |
注意此时[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<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 是否有空闲块,发现sl = [104-111]
有一块109b
空闲块,两块合成一块大小为 109 + 0x15 = 109 + 21 = 130,位于fl = [128-255]
,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) 有两大优点:
真正的鸿蒙内存动态分配实现过程比这些要复杂些,但有了本文算法基础做铺垫看源码实现会容易很多。
debug
一样,文章内容会存在不少错漏之处,请多包涵,但会反复修正,持续更新,v**.xx
代表文章序号和修改的次数,精雕细琢,言简意赅,力求打造精品内容。按功能模块:
百万汉字注解内核目的是要看清楚其毛细血管,细胞结构,等于在拿放大镜看内核。内核并不神秘,带着问题去源码中找答案是很容易上瘾的,你会发现很多文章对一些问题的解读是错误的,或者说不深刻难以自圆其说,你会慢慢形成自己新的解读,而新的解读又会碰到新的问题,如此层层递进,滚滚向前,拿着放大镜根本不愿意放手。
< gitee | github | coding | gitcode > 四大码仓推送 | 同步官方源码,鸿蒙研究站 | weharmonyos 中回复 百万 可方便阅读。
据说喜欢点赞分享的,后来都成了大神。:)
|