开源鸿蒙内核源码分析系列 | 内存池管理 | 如何高效切割合并内存块(转载)

开源鸿蒙内核源码分析系列 | 内存池管理 | 如何高效切割合并内存块(转载)

动态分配

本篇开始说一个耳朵听起老茧的概念 动态分配,将分成上下两篇,本篇为下篇,看完能快速理解开源鸿蒙内核源码对动态内存的具体实现。

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

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

请将内存池想成一条画好了网格虚线的大白纸,会有两种角色往白纸上画东西,一个是内核画管理数据,一个外部程序画业务数据,内核先画,外部程序想画需申请大小,申请成功内核会提供个地址给外部使用,例如申请20个格子,成功后内核返回一个(5,8)坐标,表示从第五行第八列开始往后的连续20个格子你可以使用。用完了释放只需要告诉内核一个坐标(5,8)而不需要大小,内核就知道回收多少格子。但内核凭什么知道要释放多少个格子呢 ? 一定有个格子给记录下来了对不对,实际中存大小的格子坐标就是(5,7)。其值是在申请的时候或更早的时候填进去的。而且不一定是20,但一定不小于20。如果您能完全理解以上这段话,那可能已经理解了内存池的管理的方式,不用往下看了。

Composition by Piet Mondrian

内存池 | OsMemPoolHead


/// 内存池头信息
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
};

解读:

  • OsMemPoolInfo.pool 是整个内存池的第一个格子,里面放的是一个内存池起始虚拟地址。
  • OsMemPoolInfo.totalSize 表示这张纸有多少个格子。
  • OsMemPoolInfo.attr 表示池子还能不能再变大。
  • OsMemPoolInfo.waterLine 池子水位警戒线,跟咱三峡大坝发洪水时的警戒线 175米 类似,告知上限,水一旦漫过此线就有重大风险,waterLine一词很形象,内核很多思想真来源于生活。
  • OsMemPoolInfo.curUsedSize 所有已分配内存大小的叠加。
  • freeListBitmap 空闲位图,这是tlfs算法的一二级表示,是个长度为7的整型数组。

#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个字节大小的需求平均分成了([0-4],[4-8],…,[124-128])共32个等级,而freeListBitmap[0]为一个UINT32,共32位刚好表示这32个等级是否有空闲块。例如: 当freeListBitmap[0] = 0b…101时,如果此时malloc(3)到来,因101对应的是12,8,4等级,而且12,4位图位为1,说明在 4的等级上有空闲内存块可以满足malloc(3),需要注意的是虽然malloc(3)但因为4等级上只有一种单位4所以malloc(3)最后实际得到的是4,而如果 malloc(7)到来时,正常需要8等级来满足,但8等级位图位为0表示没有空闲内存块,就需要向上找位图为1的12等级来申请,于是12将被分成8,4两块,8提供给malloc(7),剩下的4挂入等级为4的空闲链表上。
  • 第二种:大桶申请** 将占用freeListBitmap的剩余6个UINT32整型变量,共可以表示32 * 6 = 192位 ,同时 192 = 24 * 8,鸿蒙将大于128个字节的申请按2次幂分成24大等级,每个等级又分成8个小等级 即 TLFS 算法 24级对应的范围为([2^7-2^8-1],[2^8-2^9-1],…,[2^30-2^31-1]) 而每大级被平均分成8小级, 例如最小的[2^7-2^8-1]将被分成每份递增 2^4 = 16 大小的八份 ([2^7-2^7+2^4],[2^7+2^4-2^7+2^4*2],…,[2^7+2^4*7-2^8-1]) 而最大的[2^30-2^31-1]将被分成每份递增 2^27 = 134 217 728大小的八份,请记住2^27这个数,后面还会说它。([2^30-2^30+2^27],[2^30+2^4-2^30+2^27*2],…,[2^30+2^4*7-2^31-1])
  • OsMemFreeNodeHead freeList[..] 是空闲链表数组,大小 224个,即每个freeListBitmap等级都对应了一个链表。

/// 内存池空闲节点
struct OsMemFreeNodeHead {
    struct OsMemNodeHead header;  ///< 内存池节点
    struct OsMemFreeNodeHead *prev;  ///< 前一个空闲前驱节点
    struct OsMemFreeNodeHead *next;  ///< 后一个空闲后继节点
};

prev,next,指向同级前后节点, 节点的内容在OsMemNodeHead中,这是一个关键结构体,需单独讲。

内存池节点 | OsMemNodeHead


/// 内存池节点
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
};

解读:

  • magic 魔法数字多次提高,内核很多模块都用到了它,比如 栈顶 ,存在的意义是防止越界,栈溢出栈顶元素就一定会被修改。同理使用了大于申请的内存会导致紧挨着的内存块魔法数字被修改,从而判定为内存溢出。
  • 出现一个联合体,其中的prev,是指向前节点的 虚拟地址 或者叫 线性地址 也可以叫 逻辑地址, 这些地址是 连续 的,注意 连续性 很重要,它是内存块合并和分割的前提,回到图中的0x1245,0x12A5,0x1305来看,三个内存块节点的地址是逻辑地址相连的,内存块节点由头体两部分组成,头部放的是该节点的信息,体是 malloc(..) 的返回地址,所以当释放 free(0xXXX) 某块内存时很容易知道本节点的起始地址是多少,但向前合并就得知道前节点prev的地址,而后节点next的地址可通过0xXXX + sizeAndFlag – 头部 = next计算得到。既然不需要next那联合体出现在的next有什么意思呢? 这个next是指该块内存的尾节点的意思,当内存池允许扩展大小时,新旧两块内存之间就会产生一个连接处,它们的线性地址是不可能连续的,所以不存在合并的问题,prev于它而言没有意义,需要记录下一个内存块的地址,这个工作就交给了联合体中的next。
  • 一个内存池可以由多个内存块组成,每个内存块都有独立的尾节点,指向下一块内存的开始地址,最后一个内存块的尾节点也称为哨兵节点,它像个哨兵一样为整个内存池站岗,风餐露宿,固守边疆。当扩大版图之后它又跑到下一站,一个内存池只有一个哨兵,它是最可爱的人,此处应有掌声。
  • linkReg 用于检测内存泄漏,这部分内容在 鸿蒙内核源码分析(模块监控) 已有详细说明,此处不再赘述。
  • UINT32 sizeAndFlag,表示总大小 包括(头部和体部)和 标签 ,上面已经让大家记住2^27这个数,这是动态内存能分配的最大的尺寸。UINT32 中留28位给它足以,剩下的高4位就留给Flag。每位又分别表示以下含义:

#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)
  • 从联合体和sizeAndFlag可以看出鸿蒙的设计思想,充分利用空间,准确区分概念,一张卫生纸擦完嘴还要接着擦地,节俭之家必有余粮啊,这是非常有必要的,因为内存资源太稀缺了。在实际运行过程中,分配节点常数以万计,每个能省一个UINT32,就是一万个UINT32,约等于39KB,非常可观。这也是为什么站长始终觉得鸿蒙是个大宝藏的原因。
  • OsMemUsedNodeHead.taskID已使用节点比空闲节点头部多了一个使用该节点任务的标记,由开关宏OS_MEM_FREE_BY_TASKID控制,默认是关闭的。

代码实现

有了这么长的铺垫,再来看鸿蒙内核动态内存管理的代码简直就是易如反掌,此处拆解 节点切割 ,节点合并 ,内存池扩展 三段代码。

节点切割 | OsMemSplitNode


/// 切割节点
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


/// 合并节点,和前面的节点合并 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;//后一个节点的前节点变成前前节点
    }
}

内存池扩展



/// 内存池扩展实现
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;
}

百文说内核 | 抓住主脉络

子曰:“诗三百,一言以蔽之,曰‘思无邪’。”——《论语》:为政篇。

百文相当于摸出内核的肌肉和器官系统,让人开始丰满有立体感,因是直接从注释源码起步,在开源鸿蒙内核源码加注释过程中,每每有心得处就整理,慢慢形成了以下文章。内容立足源码,常以生活场景打比方尽可能多的将内核知识点置入某种场景,具有画面感,容易理解记忆。说别人能听得懂的话很重要! 百篇博客绝不是百度教条式的在说一堆诘屈聱牙的概念,那没什么意思。更希望让内核变得栩栩如生,倍感亲切.确实有难度,自不量力,但已经出发,回头已是不可能的了。
百万汉字注解内核目的是要看清楚其毛细血管,细胞结构,等于在拿放大镜看内核。内核并不神秘,带着问题去源码中找答案是很容易上瘾的,你会发现很多文章对一些问题的解读是错误的,或者说不深刻难以自圆其说,你会慢慢形成自己新的解读,而新的解读又会碰到新的问题,如此层层递进,滚滚向前,拿着放大镜根本不愿意放手。

与代码有bug需不断debug一样,文章和注解内容会存在不少错漏之处,请多包涵,但会反复修正,持续更新,v**.xx 代表文章序号和修改的次数,精雕细琢,言简意赅,力求打造精品内容。百篇博客系列思维导图结构如下:

根据上图的思维导图,我们未来将要和大家一一分享以上大部分关键技术点的博客文章。

百万汉字注解.精读内核源码

如果大家觉得看文章不过瘾,想直接撸代码的话,可以去下面四大码仓围观同步注释内核源码:

gitee仓

https://gitee.com/weharmony/kernel_liteos_a_note

github仓 :

https://github.com/kuangyufei/kernel_liteos_a_note

codechina仓

https://codechina.csdn.net/kuangyufei/kernel_liteos_a_note

coding仓

https://weharmony.coding.net/public/harmony/kernel_liteos_a_note/git/files

写在最后

我们最近正带着大家玩嗨OpenHarmony。如果你有用OpenHarmony开发的好玩的东东,或者有对OpenHarmony的深度技术剖析,想通过我们平台让更多的小伙伴知道和分享的,欢迎投稿,让我们一起嗨起来!有点子,有想法,有Demo,立刻联系我们:

合作邮箱:zzliang@atomsource.org