改进LiteOS中物理内存分配算法（详细实验步骤+相关源码解读）

一、实验要求

优化TLSF算法，将Best-fit策略优化为Good-fit策略，进一步降低时间复杂度至O(1)。

优化思路：

1.初始化时预先为每个索引中的内存块挂上若干空闲块，在实际分配时避免分割（split）操作，加速分配过程；

2.定位到比当前所需空间更大一级的内存块进行空闲块分配，避免因遍历链表寻找合适大小的空闲块所导致的时间浪费。

为了严谨起见，先规范一下术语（注意概念的大小：索引>内存块>空闲块。绿色是小桶，紫色是大桶）：

二、实验准备

第1步：下载带有TLSF算法的源码

在这里下载OpenHarmony 1.1.0 LTS，实测内部含有内存两级分割策略算法（TLSF算法）的代码实现，repo地址如下：

repo init -u https://gitee.com/openharmony/manifest.git -b refs/tags/OpenHarmony_release_v1.1.0 --no-repo-verify

原本的想法是要编写一个程序来验证新内存分配算法的正确性，但由于补丁只能打1.0版本，而这个是1.1版本，抱有侥幸心理试试补丁能不能打1.x版本，于是下载了这个版本，事实证明补丁依旧不能打上..

在openharmony/kernel/liteos_a/kernel/base/mem下有一个tlsf文件夹，这个文件夹里存储的正是tlsf算法的实现：

进入到tlsf文件夹下的los_memory.c文件中。

第2步：查看结构体

图中的结构体如下：

OsMemPoolInfo

OsMemFreeNodeHead

OsMemNodeHead

OsMemUsedNodeHead

第3步：检查常用宏

宏的含义可参考ppt。

第4步：理解TLSF算法

TLSF算法采用的是两级索引。右边的是第一级索引，将空间按2的指数大小（ $2^{_{5}}=32$ ， $2^{6}=64$ ， $2^{7}=128$ ...）进行分块。其内部的内存块是否空闲用位图(一维数组)进行标识，1表示块内有剩余空间，0表示块内已经被挤得满满的。

中间的是第二级索引，二级索引在一级索引分块的基础上，进一步进行分块，如图中将一级索引中的每块进一步分成了8块（例如32-63这段被分为了32-35,36-39,40-43,44-47,48-51,52-55,56-59,60-63，每块长度是4）。用位图(二维数组)标识是否存在空闲内存块。有空闲的块标记为1，没有空闲的块标记为0。

左边的是空闲块，空闲块的大小是一个确定的值，该值要在二级索引的区间范围之内。

上图告诉我们鸿蒙系统将内存块大小分为两个部分： $4$ ~ $127$ 和 $2^{7}$ ~ $2^{31}$ 。

在4~127区间上是小桶申请，可以这么理解：在4~127区间上有31个桶（4，8，12，...，124），每个桶的大小代表了所能挂的空闲块的大小（比如12代表只能挂12B大小的空闲块，120代表只能挂120B大小的空闲块），没有二级索引。

大于127的是大桶申请，可以这么理解一共有24个大桶（ $2^{7}$ ~ $2^{8}-1$ ， $2^{8}$ ~ $2^{9}-1$ ，... ， $2^{30}$ ~ $2^{31}-1$ ），这里的大桶代表了一级索引；然后每个大桶里又有8个小桶，这里的小桶代表2级索引；然后每个小桶里又可以挂若干个空闲块。

三、改进TLSF算法

事先说明：

1. 修改不保证完全正确，如有疏漏，望请指正。

2. 所修改的函数都在openharmony/kernel/liteos_a/kernel/base/mem/tlsf下的los_memory.c文件中。

3.所修改的源码是OpenHarmony 1.1.0 LTS版本，其它版本可能会有所差异。

1.定位到比当前所需空间更大一级的内存块

修改对象：OsMemFreeListIndexGet函数

改进思路：在当前内存块位置的基础上+1，指向下一块内存块的位置，需要考虑的是+1后从小桶变成大桶的情况，所以当size<124时归属于小桶，当size>=124时归属于大桶。

修改如下：

首先复制OsMemFreeListIndexGet这个函数，粘贴到原函数下面，改名为NewOsMemFreeListIndexGet，然后就不再变动NewOsMemFreeListIndexGet这个函数。

fl的值表示的是在一级索引中的位置，OS_MEM_SMALL_BUCKET_MAX_SIZE是一个宏其值为128，如果size<124，就让fl+1，相当于索引指向当前桶的上一级桶。

如果size>=124此时考虑临界状态，当size为124时再上一级桶时（+4后）会进入到大桶的范围（因为小桶的最大上界为127），所以此时会返回newFl。

newFl会进入到OsMemSlGet函数，这个函数的作用是返回某个值在二级索引中的位置（详见第四部分），所以sl的值代表了size在二级索引中的位置。

此时我们让sl+1，就相当于指向了下一个位置的二级索引，最后这里return的这一长串数很巧妙（同样详见第2部分）。

为什么要这么修改呢？原因：因为OsMemFreeListIndexGet这个函数的作用是返回要插入空闲块的内存块位置，我们为了在一般情况下默认定位到比当前所需空间更大一级的内存块进行空闲块插入，所以对OsMemFreeListIndexGet这个函数进行修改。

在特殊情况下，比如初始化时预先为每个索引挂上若干空闲块，要求12B就是为大小为12的内存块预先挂上空闲块，因此设定仍按准确的大小定位。

2.初始化时预先为每个内存块挂上若干空闲块

修改对象：OsMemPoolInit函数、OsMemFreeNodeAdd函数

修改思路：在初始化内存池的时候，同时为内存块挂上空闲块。人为给出要预先为哪些索引上的内存块挂上空闲块，空闲块的大小用sizeArray给出，然后为OsMemNodeHead结构体的变量freeNode赋值进行初始化，存储逻辑上用双向链表进行连接，索引逻辑上通过NewOsMemFreeNodeAdd函数将特定大小的空闲块挂载到索引的内存块上。

修改如下：

OsMemPoolInit这个函数是用于初始化内存池的，可以在该函数中预先挂上空闲块。

首先我定义了一个名为currentNode的OsMemNodeHead结构体指针，指向的是初始节点（newNode）的末尾，即后续空闲的线性空间的开头，用于顺序存储新的结构体和空闲块。

preveNode的作用是要记录前驱节点，方便后续双向链表的构建。

然后我定义了n和sizeArray这里是用于指定想要在哪个内存块上挂空闲块（比如12代表想要在大小为的内存块上挂大小为12B的空闲块），可以根据自己的需要将空闲块挂到其它内存块上，只需修改sizeArray数组内的值即可。

在for循环里主要就是给freeNode结构体内的参数赋值，freeNode指向的是前一个节点的末尾地址，即未被占用的线性空间开头的位置。

如果i==0，前驱节点要指向newNode，如果i>0此时preveNode的作用就凸显出来，freeNode（当前节点）的前驱就指向preveNode（前一个节点）。

然后调用NewOsMemFreeNodeAdd函数，这个函数主要是将结构体插入到索引的内存块当中。

preveNode = freeNode 用于前移preveNode指针指向的节点，使preveNode永远指向当前节点的前一个节点，

最后一行是令currentNode指向后续空闲空间的起始位置，方便添加新的结构体。

在OsMemPoolInit函数中调用到NewOsMemFreeNodeAdd这个函数，这个函数原名是OsMemFreeNodeAdd，只需在前面加上New即可，然后这里就和本节1中修改的NewOsMemFreeListIndexGet函数联系在一起。

四、源码解析+修改逻辑分析

1.定位到比当前所需空间更大一级的索引

首先我们分析一下OsMemFlGet这个函数，调用逻辑是：OsMemFlGet->OsMemLog2->OsMemFLS->

我们直接看OsMemFLS函数，OS_MEM_BITMAP_MASK是一个宏定义，代表数31（0到31共计32位，因为操作系统是32位的）。

CLZ是“Count Leading Zeros”的缩写，用于统计二进制数前导0的个数（比如一个32位的数0000010100...，前导0有5个）。

OS_MEM_BITMAP_MASK-CLZ(bitmap)是计算第1个“1”所在的位置（比如上面举例的32位数0000010100...，前导0有5个，用31-5得到的就是该数最高位的“1”所在的位置是26），这个的用处就是去定位这个数是在哪一个一级索引里（比如上面那个数最后会被放在2^26~2^27-1这个一级索引里），参考下面的图来理解：

接下来我们看OsMemSlGet函数，OS_MEM_SLI是一个宏定义值为3，OS_MEM_FREE_LIST_NUM是1<<3，即值为8。

size << OS_MEM_SLI是将size扩大8倍，(size << OS_MEM_SLI)>>fl是将乘8后的size再除以2^fl倍，这个的目的是得到二级索引的值，不至于移除低位导致精度缺失（比如对于数111000000，fl即一级索引是8，如果不乘8，此时将该数右移8位结果为1，明显不对，而乘8后右移8位结果为1110，十进制为14，此时减8，结果为6，表明该数在一级索引中是2^9~2^10-1，在二级索引中排在第6个块中）。