关键词：内存池、哨兵节点、动态扩展、吃水线 内存管理相关篇为: v31.02 鸿蒙内核源码分析(内存规则) | 内存管理到底在管什么 v32.04 鸿蒙内核源码分析(物理内存) | 真实的可不一定精彩 …

                                                                                                                                                                                    本篇关键词：内存池、哨兵节点、动态扩展、吃水线

内存管理相关篇为:

v31.02 鸿蒙内核源码分析(内存规则) | 内存管理到底在管什么
v32.04 鸿蒙内核源码分析(物理内存) | 真实的可不一定精彩
v33.04 鸿蒙内核源码分析(虚拟内存) | 虚拟的也是真实的
v34.03 鸿蒙内核源码分析(虚实映射) | 映射是伟大的发明
v35.02 鸿蒙内核源码分析(页表管理) | 映射关系保存在哪
v36.03 鸿蒙内核源码分析(静态分配) | 很简单的一位小朋友
v37.01 鸿蒙内核源码分析(TLFS算法) | 用图解读TLFS原理
v38.01 鸿蒙内核源码分析(内存池管理) | 如何高效切割合并内存块
v39.04 鸿蒙内核源码分析(原子操作) | 谁在守护指令执行的完整性
v40.01 鸿蒙内核源码分析(圆整对齐) | 正在制作中 …

##### 动态分配
系列篇将动态分配分成上下两篇，本篇为下篇，阅读之前需翻看上篇偏于快速理解。

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

为了便于理解源码，站长画了以下图，图中列出主要结构体，位图，分配和释放信息，逐一说明。

请将内存池想成一条画好了网格虚线的大白纸，会有两种角色往白纸上画东西，一个是内核画管理数据，一个外部程序画业务数据，内核先画，外部程序想画需申请大小，申请成功内核会提供个地址给外部使用，例如申请
1
20

个格子，成功后内核返回一个
1
(5，8)

坐标，表示从第五行第八列开始往后的连续
1
20

个格子你可以使用。用完了释放只需要告诉内核一个坐标
1
(5,8)

而不需要大小，内核就知道回收多少格子。但内核凭什么知道要释放多少个格子呢 ? 一定有个格子给记录下来了对不对，实际中存大小的格子坐标就是
1
(5，7)

。其值是在申请的时候或更早的时候填进去的。而且不一定是
1
20

，但一定不小于
1
20

。如果您能完全理解以上这段话，那可能已经理解了内存池的管理的方式，不用往下看了。

##### 内存池 | OsMemPoolHead

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
  /// 内存池头信息
struct OsMemPoolHead {
    struct OsMemPoolInfo info; ///< 记录内存池的信息
    UINT32 freeListBitmap[OS_MEM_BITMAP_WORDS]; ///< 空闲位图 int[7] = 32 * 7 = 224
    struct OsMemFreeNodeHead *freeList[OS_MEM_FREE_LIST_COUNT];///< 空闲节点链表 32 + 24 * 8 = 224  
    SPIN_LOCK_S spinlock;	///< 操作本池的自旋锁,涉及CPU多核竞争,所以必须得是自旋锁
#ifdef LOSCFG_MEM_MUL_POOL
    VOID *nextPool;	///< 指向下一个内存池 OsMemPoolHead 类型
#endif
};
/// 内存池信息
struct OsMemPoolInfo {
    VOID *pool;			///< 指向内存块基地址,仅做记录而已,真正的分配内存跟它没啥关系
    UINT32 totalSize;	///< 总大小,确定了内存池的边界
    UINT32 attr;		///< 属性 default attr: lock, not expand.
#ifdef LOSCFG_MEM_WATERLINE
    UINT32 waterLine;   /* Maximum usage size in a memory pool | 内存吃水线*/
    UINT32 curUsedSize; /* Current usage size in a memory pool | 当前已使用大小*/
#endif
};



解读


1
OsMemPoolInfo.pool

是整个内存池的第一个格子，里面放的是一个内存池起始虚拟地址。

1
OsMemPoolInfo.totalSize

表示这张纸有多少个格子。

1
OsMemPoolInfo.attr

表示池子还能不能再变大。

1
OsMemPoolInfo.waterLine

池子水位警戒线，跟咱三峡大坝发洪水时的警戒线 175米 类似，告知上限，水一旦漫过此线就有重大风险，
1
waterLine

一词很形象，内核很多思想真来源于生活。

1
OsMemPoolInfo.curUsedSize

所有已分配内存大小的叠加。

1
freeListBitmap

空闲位图，这是
1
tlfs

算法的一二级表示，是个长度为
1
7

的整型数组
1
2
3
4
5
6
  #define OS_MEM_BITMAP_WORDS     ((OS_MEM_FREE_LIST_COUNT >> 5) + 1) 
#define OS_MEM_FREE_LIST_COUNT  (OS_MEM_SMALL_BUCKET_COUNT + (OS_MEM_LARGE_BUCKET_COUNT << OS_MEM_SLI)) 
#define OS_MEM_LARGE_START_BUCKET       7 /// 大桶的开始下标
#define OS_MEM_SMALL_BUCKET_COUNT       31 ///< 小桶的偏移单位 从 4 ~ 124 ,共32级
#define OS_MEM_SLI                      3 ///< 二级小区间级数,


这一坨坨的宏看着有点绕，简单说就是鸿蒙对申请大小分成两种情况

第一种：小桶申请** 当小于128个字节大小的需求平均分成了
1
([0-4]，[4-8]，...，[124-128])

共
1
32

个等级，而
1
freeListBitmap[0]

为一个
1
UINT32

，共
1
32

位刚好表示这
1
32

个等级是否有空闲块。例如: 当
1
freeListBitmap[0] = 0b...101

时，如果此时
1
malloc(3)

到来，因
1
101

对应的是
1
12

,
1
8

,
1
4

等级，而且
1
12

，
1
4

位图位为
1
1

，说明在
1
4

的等级上有空闲内存块可以满足
1
malloc(3)

，需要注意的是虽然
1
malloc(3)

但因为
1
4

等级上只有一种单位
1
4

所以
1
malloc(3)

最后实际得到的是
1
4

，而如果
1
malloc(7)

到来时，正常需要
1
8

等级来满足，但
1
8

等级位图位为
1
0

表示没有空闲内存块，就需要向上找位图为
1
1

的
1
12

等级来申请，于是
1
12

将被分成
1
8

，
1
4

两块，
1
8

提供给
1
malloc(7)

，剩下的
1
4

挂入等级为
1
4

的空闲链表上。
第二种：大桶申请** 将占用
1
freeListBitmap

的剩余
1
6

个
1
UINT32

整型变量，共可以表示
1
32 * 6

1
192

位 ，同时
1
192

1
24 * 8

，鸿蒙将大于

1
128

个字节的申请按
1
2

次幂分成
1
24

大等级，每个等级又分成
1
8

个小等级 即 TLFS 算法
1
24

级对应的范围为
1
([2^7-2^8-1]，[2^8-2^9-1]，...，[2^30-2^31-1])

而每大级被平均分成
1
8

小级， 例如最小的
1
[2^7-2^8-1]

将被分成每份递增
1
2^4 = 16

大小的八份
1
([2^7-2^7+2^4]，[2^7+2^4-2^7+2^4*2]，...，[2^7+2^4*7-2^8-1])

而最大的
1
[2^30-2^31-1]

将被分成每份递增
1
2^27 = 134 217 728

大小的八份，请记住
1
2^27

这个数，后面还会说它。
1
([2^30-2^30+2^27]，[2^30+2^4-2^30+2^27*2]，...，[2^30+2^4*7-2^31-1])

1
OsMemFreeNodeHead freeList[..]

是空闲链表数组，大小

1
224

个，即每个
1
freeListBitmap

等级都对应了一个链表
1
2
3
4
5
6
7
  /// 内存池空闲节点
struct OsMemFreeNodeHead {
    struct OsMemNodeHead header;	///< 内存池节点
    struct OsMemFreeNodeHead *prev;	///< 前一个空闲前驱节点
    struct OsMemFreeNodeHead *next;	///< 后一个空闲后继节点
};

1
prev

，

1
next

，指向同级前后节点， 节点的内容在
1
OsMemNodeHead

中，这是一个关键结构体，需单独讲。

内存池节点 | OsMemNodeHead
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
  /// 内存池节点
struct OsMemNodeHead {
    UINT32 magic;	///< 魔法数字 0xABCDDCBA
    union {//注意这里的前后指向的是连续的地址节点，用于分割和合并
        struct OsMemNodeHead *prev; /* The prev is used for current node points to the previous node | prev 用于当前节点指向前一个节点*/
        struct OsMemNodeHead *next; /* The next is used for last node points to the expand node | next 用于最后一个节点指向展开节点*/
    } ptr;
#ifdef LOSCFG_MEM_LEAKCHECK //内存泄漏检测
    UINTPTR linkReg[LOS_RECORD_LR_CNT];///< 存放左右节点地址,用于检测
#endif
    UINT32 sizeAndFlag;	///< 数据域大小
};
/// 已使用内存池节点
struct OsMemUsedNodeHead {
    struct OsMemNodeHead header;///< 已被使用节点
#if OS_MEM_FREE_BY_TASKID
    UINT32 taskID; ///< 使用节点的任务ID
#endif
};

解读

1
magic

魔法数字多次提高，内核很多模块都用到了它，比如 栈顶 ，存在的意义是防止越界，栈溢出栈顶元素就一定会被修改。同理使用了大于申请的内存会导致紧挨着的内存块魔法数字被修改，从而判定为内存溢出。
出现一个联合体，其中的

1
prev

，是指向前节点的 虚拟地址 或者叫 线性地址 也可以叫 逻辑地址， 这些地址是 连续 的，注意 连续性 很重要，它是内存块合并和分割的前提，回到图中的
1
0x1245

，
1
0x12A5

，
1
0x1305

来看，三个内存块节点的地址是逻辑地址相连的，内存块节点由头体两部分组成，头部放的是该节点的信息，体是 malloc(..) 的返回地址，所以当释放 free(0xXXX) 某块内存时很容易知道本节点的起始地址是多少，但向前合并就得知道前节点
1
prev

的地址，而后节点
1
next

的地址可通过
1
0xXXX + sizeAndFlag - 头部 = next

计算得到。既然不需要
1
next

那联合体出现在的
1
next

有什么意思呢? 这个
1
next

是指该块内存的尾节点的意思，当内存池允许扩展大小时，新旧两块内存之间就会产生一个连接处，它们的线性地址是不可能连续的，所以不存在合并的问题，
1
prev

于它而言没有意义，需要记录下一个内存块的地址，这个工作就交给了联合体中的
1
next

。
一个内存池可以��多个内存块组成，每个内存块都有独立的尾节点，指向下一块内存的开始地址，最后一个内存块的尾节点也称为哨兵节点，它像个哨兵一样为整个内存池站岗，风餐露宿，固守边疆。当扩大版图之后它又跑到下一站，一个内存池只有一个哨兵，它是最可爱的人，此处应有掌声。

1
linkReg

用于检测内存泄漏，这部分内容在 鸿蒙内核源码分析(模块监控) 已有详细说明，此处不再赘述。

1
UINT32 sizeAndFlag

，表示总大小 包括(头部和体部)和 标签 ，上面已经让大家记住

1
2^27

这个数，这是动态内存能分配的最大的尺寸。
1
UINT32

中留
1
28

位给它足以，剩下的高
1
4

位就留给
1
Flag

。每位又分别表示以下含义
1
2
3
4
5
  #define OS_MEM_NODE_USED_FLAG      0x80000000U ///< 已使用标签
#define OS_MEM_NODE_ALIGNED_FLAG   0x40000000U ///< 对齐标签
#define OS_MEM_NODE_LAST_FLAG      0x20000000U  /* Sentinel Node | 哨兵节点标签，最后一个节点*/
#define OS_MEM_NODE_ALIGNED_AND_USED_FLAG (OS_MEM_NODE_USED_FLAG | OS_MEM_NODE_ALIGNED_FLAG | OS_MEM_NODE_LAST_FLAG)

从联合体和

1
sizeAndFlag

可以看出鸿蒙的设计思想，充分利用空间，准确区分概念，一张卫生纸擦完嘴还要接着擦地，节俭之家必有余粮啊，这是非常有必要的，因为内存资源太稀缺了。在实际运行过程中，分配节点常数以万计，每个能省一个
1
UINT32

，就是一万个
1
UINT32

，约等于
1
39KB

，非常可观。 这也是为什么站长始终觉得鸿蒙是个大宝藏的原因。

1
OsMemUsedNodeHead.taskID

已使用节点比空闲节点头部多了一个使用该节点任务的标记，由开关宏

1
OS_MEM_FREE_BY_TASKID

控制，默认是关闭的。

代码实现

有了这么长的铺垫，再来看鸿蒙内核动态内存管理的代码简直就是易如反掌，此处拆解 节点切割 ，节点合并 ，内存池扩展 三段代码。都已添加详细的注解 ，所有注解代码请前往 百万汉字注解鸿蒙内核 | kernel_liteos_a_note 仓库查看

节点切割 | OsMemSplitNode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
  /// 切割节点
STATIC INLINE VOID OsMemSplitNode(VOID *pool, struct OsMemNodeHead *allocNode, UINT32 allocSize)
{
    struct OsMemFreeNodeHead *newFreeNode = NULL;
    struct OsMemNodeHead *nextNode = NULL;
    newFreeNode = (struct OsMemFreeNodeHead *)(VOID *)((UINT8 *)allocNode + allocSize);//切割后出现的新空闲节点,在分配节点的右侧
    newFreeNode->header.ptr.prev = allocNode;//新节点指向前节点,说明是从左到右切割
    newFreeNode->header.sizeAndFlag = allocNode->sizeAndFlag - allocSize;//新空闲节点大小
    allocNode->sizeAndFlag = allocSize;//分配节点大小
    nextNode = OS_MEM_NEXT_NODE(&newFreeNode->header);//获取新节点的下一个节点
    if (!OS_MEM_NODE_GET_LAST_FLAG(nextNode->sizeAndFlag)) {//如果下一个节点不是哨兵节点(末尾节点)
        nextNode->ptr.prev = &newFreeNode->header;//下一个节点的前节点为新空闲节点
        if (!OS_MEM_NODE_GET_USED_FLAG(nextNode->sizeAndFlag)) {//如果下一个节点也是空闲的
            OsMemFreeNodeDelete(pool, (struct OsMemFreeNodeHead *)nextNode);//删除下一个节点信息
            OsMemMergeNode(nextNode);//下一个节点和新空闲节点 合并成一个新节点
        }
    }
    OsMemFreeNodeAdd(pool, newFreeNode);//挂入空闲链表
}

节点合并 | OsMemMergeNode
1
2
3
4
5
6
7
8
9
10
11
  /// 合并节点,和前面的节点合并 node 消失
STATIC INLINE VOID OsMemMergeNode(struct OsMemNodeHead *node)
{
    struct OsMemNodeHead *nextNode = NULL;
    node->ptr.prev->sizeAndFlag += node->sizeAndFlag; //前节点长度变长
    nextNode = (struct OsMemNodeHead *)((UINTPTR)node + node->sizeAndFlag); // 下一个节点位置
    if (!OS_MEM_NODE_GET_LAST_FLAG(nextNode->sizeAndFlag)) {//不是哨兵节点
        nextNode->ptr.prev = node->ptr.prev;//后一个节点的前节点变成前前节点
    }
}

内存池扩展
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
  /// 内存池扩展实现
STATIC INLINE INT32 OsMemPoolExpandSub(VOID *pool, UINT32 size, UINT32 intSave)
{
    UINT32 tryCount = MAX_SHRINK_PAGECACHE_TRY;
    struct OsMemPoolHead *poolInfo = (struct OsMemPoolHead *)pool;
    struct OsMemNodeHead *newNode = NULL;
    struct OsMemNodeHead *endNode = NULL;
    size = ROUNDUP(size + OS_MEM_NODE_HEAD_SIZE, PAGE_SIZE);//圆整
    endNode = OS_MEM_END_NODE(pool, poolInfo->info.totalSize);//获取哨兵节点
RETRY:
    newNode = (struct OsMemNodeHead *)LOS_PhysPagesAllocContiguous(size >> PAGE_SHIFT);//申请新的内存池 | 物理内存
    if (newNode == NULL) 
        return -1;
    newNode->sizeAndFlag = (size - OS_MEM_NODE_HEAD_SIZE);//设置新节点大小
    newNode->ptr.prev = OS_MEM_END_NODE(newNode, size);//新节点的前节点指向新节点的哨兵节点
    OsMemSentinelNodeSet(endNode, newNode, size);//设置老内存池的哨兵节点信息,其实就是指向新内存块
    OsMemFreeNodeAdd(pool, (struct OsMemFreeNodeHead *)newNode);//将新节点加入空闲链表
    endNode = OS_MEM_END_NODE(newNode, size);//获取新节点的哨兵节点
    (VOID)memset(endNode, 0, sizeof(*endNode));//清空内存
    endNode->ptr.next = NULL;//新哨兵节点没有后续指向,因为它已成为最后
    endNode->magic = OS_MEM_NODE_MAGIC;//设置新哨兵节的魔法数字
    OsMemSentinelNodeSet(endNode, NULL, 0); //设置新哨兵节点内容
    OsMemWaterUsedRecord(poolInfo, OS_MEM_NODE_HEAD_SIZE);//更新内存池警戒线
    return 0;
}

百文说内核 | 抓住主脉络

百文相当于摸出内核的肌肉和器官系统，让人开始丰满有立体感，因是直接从注释源码起步，在加注释过程中，每每有心得处就整理,慢慢形成了以下文章。内容立足源码，常以生活场景打比方尽可能多的将内核知识点置入某种场景，具有画面感，容易理解记忆。说别人能听得懂的话很重要! 百篇博客绝不是百度教条式的在说一堆诘屈聱牙的概念，那没什么意思。更希望让内核变得栩栩如生，倍感亲切。
与代码需不断

1
debug

一样，文章内容会存在不少错漏之处，请多包涵，但会反复修正，持续更新，
1
v**.xx

代表文章序号和修改的次数，精雕细琢，言简意赅，力求打造精品内容。
百文在 < 鸿蒙研究站 | 开源中国 | 博客园 | 51cto | csdn | 知乎 | 掘金 > 站点发布，鸿蒙研究站 | weharmonyos 中回复 百文 可方便阅读。

按功能模块:

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

百万注源码 | 处处扣细节

百万汉字注解内核目的是要看清楚其毛细血管，细胞结构，等于在拿放大镜看内核。内核并不神秘，带着问题去源码中找答案是很容易上瘾的，你会发现很多文章对一些问题的解读是错误的，或者说不深刻难以自圆其说，你会慢慢形成自己新的解读，而新的解读又会碰到新的问题，如此层层递进，滚滚向前，拿着放大镜根本不愿意放手。
< gitee | github | coding | gitcode > 四大码仓推送 | 同步官方源码，鸿蒙研究站 | weharmonyos 中回复 百万 可方便阅读。

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

本文标题： 推荐系列-v85.01 鸿蒙内核源码分析(内存池管理) - 如何高效切割合并内存块 - 百篇博客分析OpenHarmony源码

本文作者： OSChina

发布时间： 2022年05月11日 05:14

最后更新： 2023年06月29日 07:10

原始链接： https://haoxiang.eu.org/c0f9fba3/

版权声明： 本文著作权归作者所有，均采用CC BY-NC-SA 4.0许可协议，转载请注明出处！

赏
× 喜欢就赞赏一下呗！
打赏二维码