鸿蒙轻内核M核源码学习 动态内存（1）

首先，要学习一下大佬关于鸿蒙M核动态内存的系列博客：https://bbs.huaweicloud.com/blogs/279703

自己结合代码，理解一下底层的基本原理。

一、关于TLSF算法

TLSF是一个动态内存的分配算法，通过以下两篇文章可以对此有一个大概的了解：

https://blog.csdn.net/sunao2002002/article/details/50611838

https://www.codenong.com/cs106845116/

TLSF算法中，将一整块动态内存池，划分为了许多个小内存块。比如在鸿蒙M核里，所有的内存块，都是被放在了链表里。TLSF使用了两级索引，即每个内存块，都可以由FL（first level）和SL（second level）两个索引来精确表示。128Byte大小以下的内存块，只需要单独一个FL即可以表示它位于哪个链表；而128Byte以上，2^31Byte以下的“大内存块”，需要由FL和SL两个索引来表示。

TLSF算法中，给出了计算两个索引的公式（背后的原理，要仔细学习一下上面两篇介绍TLSF的文章）

公式的变体为：

在鸿蒙M核中，SLI使用固定值3，即对于大块的内存，比如2^7~2^8区间，被分成了8等份，放在八个链表中。

单独看一下这个公式变体，因为这个比较方便通过位操作来实现：

，后面的代码里会有体现。

二、关于OsMemPoolHead->freeList数组

结合《鸿蒙轻内核M核源码分析系列九 动态内存Dynamic Memory 第一部分》和代码可以知道，freeList是一个数组。那么这个数组有多少个元素呢？或者说有多少个桶呢？小块内存，4 ~ 128Byte，一共有31个桶，对应数组下标0~30；大块内存，2^7 ~ 2^30 Byte，一共有24 * 8 = 192个桶，对应数组下标31 ~ 222。

三、关于kernel/src/mm/los_memory.c里重要的宏和方法

代码里的宏和方法，很重要的是为了解决一个关键问题：freeList一共有223个元素，每个元素都指向一个由内存块组成的链表，我们暂且叫它们为223个桶。那么问题是：给定一个size大小的内存，如果确定它属于哪个桶？即给定一个内存块，大小为size，那么他属于freeList[index]链表，index是几？

小块内存比较简单，这里暂不做讨论。考虑大块内存的场景，index = 小块内存数量(固定为31) + (log2(size)取整 - 7)*8 + SL。

比如size=129，129 = 2^7 + 1，二进制表示为1000 0001。小块内存数量是31，log2(size)取整 = 7，SL=0，计算出来属于freeList[31]。它刚刚好就是第一个大块内存的桶，即第32个桶，index=31。

再大一点比如size=560， 560 = 2^9 + 48，二进制表示为0010 0011 0000，小块内存数量是31，log2(size)取整 = 9，SL=0，计算出来属于freeList[47]。

那么接下来再来看代码中“令人头疼”的宏定义：

1、OsMemFFS、OsMemFLS

这个FFS，Find First S、Find Last S，S是啥我没看出来:(。比如十进制240，以UINT32表示是 00000000 00000000 00000000 11110000，

OsMemFFS(240)：

OS_MEM_BITMAP_MASK=31，

~bitmap = 11111111 11111111 11111111 00001111，

~bitmap+1 = 11111111 11111111 11111111 00010000，

bitmap &= ~bitmap + 1后，bitmap=00000000 00000000 00000000 00010000，

CLZ(bitmap) = 27，

OS_MEM_BITMAP_MASK-CLZ(bitmap) = 4；

OsMemFLS(240)：

CLZ(bitmap) = 24，

OS_MEM_BITMAP_MASK-CLZ(bitmap) = 7

理解一下：OsMemFLS，就是求出了一个十进制数，拿二进制表示时，最高的1bit是第几位。关键点来了，它的数学意义就是，log2(size)取整。log2(240) 取整等于7。

所有OsMemFLS单词里面的last bit，就是从低位开始，即从右向左数，第0位开始，最后一个bit位是第几位。

2、OsMemLog2，

有了对FLS的理解，这里就好理解了。给定一个size，求log2(size)的整数部分。

3、STATIC INLINE UINT32 OsMemFlGet(UINT32 size)

第一个if，处理小块内存，size小于128的场景，直接将size/4-1，得到其所属桶的index。

重点看return部分。TLSF算法里，标准的FL，就是等于log2(size)；但是代码里将它减去了一个OS_MEM_LARGE_START_BUCKET（=7），再加上OS_MEM_SMALL_BUCKET_COUNT（=31）。经过一减一加，其实已经失去了数学上的含义。

4、STATIC INLINE UINT32 OsMemSlGet(UINT32 size, UINT32 fl)

我们拿红箭头所指的公式，转换成位操作：SL = （size << SLI >> FL）-（1 << SLI）

再看代码，终于能看懂这左移右移的神操作了。

5、最后，我们最终目的是通过size，计算freeList[index] 中的index。

经过前面对FL，SL的理解，我们先自己尝试推导index的计算公式：index = 小块内存数量(固定为31) + (log2(size)取整 - 7)*8 + SL

这里有两种FL。一种是数学上的，129的FL = 7；另外一种是代码里的，129的fl = 7-7+31 = 31。

再仔细看下代码，(fl - OS_MEM_SMALL_BUCKET_COUNT) 就是(log2(size)取整 - 7，<<OS_MEM_SLI就是<<3，就是乘以8！剩下的就是加减法了。

四、总结

对于本篇文章介绍的宏和函数，首先要理解。

更重要的是要记住，给定内存块大小为size，通过 OsMemFreeListIndexGet(size)，即可得到其所属的桶的index，即freeList[index]。

比如拆分内存，拆出来的内存应该放到哪个链表？申请内存，应该从哪个链表申请？回收内存，应该放到哪个链表里？这些都是用到了OsMemFreeListIndexGet(size)函数。