当前位置：首页 > news >正文

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

news 2025/7/16 7:26:20

一、实验要求

优化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的桶上挂空闲块），可以根据自己的需要将空闲块挂到其它桶上，只需修改size的值即可。

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

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

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

preveNode = freeNode是令前一个节点指向当前节点。

最后一行是令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个块中）。

最后解释一下return的这段代码的含义，我首先各处各个变量代表的含义：OS_MEM_SMALL_BUCKET_COUNT=31，代表小桶一共被分为31个区间。OS_MEM_LARGE_START_BUCKET=7，2^7=128即大桶开始的位置。sl返回的是2级索引的值。fl是1级索引的值。

然后我们看表达式：fl - OS_MEM_LARGE_START_BUCKET，表达式的含义是：size所处的一级索引位置减去大桶开始的位置，如下图1：

fl - OS_MEM_LARGE_START_BUCKET) << OS_MEM_SLI，是将上图中那部分一级索引的个数乘以8，为什么要乘以8？因为每个一级索引（大桶）对应有8个二级索引块，所以是计算出二级索引块的个数。

OS_MEM_SMALL_BUCKET_COUNT + ((fl - OS_MEM_LARGE_START_BUCKET) << OS_MEM_SLI)，意思是在前面二级索引块数的基础上，再加上一级索引块的数量（因为<128的一级索引属于小桶范畴不具备二级索引，如上图2，所以直接加上即可）。

OS_MEM_SMALL_BUCKET_COUNT + ((fl - OS_MEM_LARGE_START_BUCKET) << OS_MEM_SLI) + sl就是把所有的小桶+大桶的二级索引块全部加上，然后加上sl自身这个块的偏移量，就能够定位到要在哪个大桶的二级索引块上加入空闲块。

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

首先看osmempoolinit的函数，主要要关注poolHead,newNode,endNode的结构体，这个大家自己看了。

然后要注意newNode = OS_MEM_FIRST_NODE(pool)和endNode=OS_MEM_END_NODE(pool,size)这两个函数对应的是一段计算公式，计算的是起始地址和结束地址，endNode标记的是末尾结点。

再然后要关注OsMemFreeNodeAdd这个函数，只有理清了这个函数才能真正理解是如何为每个桶挂上空闲块的。

1.分析OsMemPoolHead和OsMemNodeHead结构体

poolHead -> OsMemPoolHead

newNode、endNode -> OsMemNodeHead

OsMemPoolHead包含了OsMemPoolInfo结构体，其中freeList表示索引列表：

OS_MEM_FREE_LIST_COUNT=小桶（31个）+ 大桶（24个）x 8 = 223个

从这里可以看出对于小桶<128，是给每个一级索引分配一个链表，对于大桶，是给每个二级索引分配一个链表，链表可以在后续挂载空闲块。

OsMemFreeNodeHead包含了OsMemNodeHead结构体：

2.OS_MEM_FIRST_NODE(pool)和OS_MEM_END_NODE(pool,size)

OS_MEM_FIRST_NODE是一段宏定义，用于指明第1个结点的起始位置。pool是内存池的起始位置，sizeof(struct OsMemPoolHead)是内存池的头的长度，第1个结点从内存池头后开始。

OS_MEM_FIRST_NODE是一段宏定义，用于指明最后1个结点的起始位置。因为size代表的是整个内存池的大小，OS_MEM_NODE_HEAD_SIZE相当于就是endNode本身的结构体（OsMemNodeHead）大小，所以整个式子的含义就是指向刚好容纳最后一个节点的起始位置。

3.OsMemFreeNodeAdd函数

OsMemFreeNodeAdd函数的作用是将空闲块挂载到对应索引的内存块上。

首先进入到OsMemFreeNodeAdd函数后会调用OsMemFreeListIndexGet函数，这就是我们前面的函数，用于返回对应索引的内存块位置。

然后会调用OsMemListAdd函数，freeList就是内存池pool中的索引，然后会根据listIndex的值，将空闲块挂在到该索引上。

【到此为止，源码分析就结束了，如果觉得有帮助记得点赞+收藏吧】

下面补充内存池知识点：

OsMemPoolInit函数用来初始化一个内存池。

内存池（Memory Pool）是一个用于管理内存分配的系统，它预先分配一块大的内存区域，并将其划分为小块以供程序使用。这样做的好处包括减少内存碎片、提高内存分配效率和简化内存管理。

一二级索存在于内存池中，是内存池中的数据结构，它们用于快速定位和管理内存块。

在一个系统中会有多个内存池（比如用户空间和内核空间的内存池）。操作系统的内存不仅由内存池构成还包括页表、段表等，内存池只适用特定场景。空闲块是由内存池中的索引结构组织。