鸿蒙轻内核M核源码分析系列九 动态内存Dynamic Memory

内存管理模块管理系统的内存资源，它是操作系统的核心模块之一，主要包括内存的初始化、分配以及释放。

在系统运行过程中，内存管理模块通过对内存的申请/释放来管理用户和OS对内存的使用，使内存的利用率和使用效率达到最优，同时最大限度地解决系统的内存碎片问题。

鸿蒙轻内核的内存管理分为静态内存管理和动态内存管理，提供内存初始化、分配、释放等功能。

• 动态内存：在动态内存池中分配用户指定大小的内存块。

  • 优点：按需分配。
  • 缺点：内存池中可能出现碎片。

• 静态内存：在静态内存池中分配用户初始化时预设（固定）大小的内存块。

  • 优点：分配和释放效率高，静态内存池中无碎片。
  • 缺点：只能申请到初始化预设大小的内存块，不能按需申请。

上一系列分析了静态内存，我们开始分析动态内存。动态内存管理主要用于用户需要使用大小不等的内存块的场景。当用户需要使用内存时，可以通过操作系统的动态内存申请函数索取指定大小的内存块，一旦使用完毕，通过动态内存释放函数归还所占用内存，使之可以重复使用。

OpenHarmony LiteOS-M动态内存在TLSF算法的基础上，对区间的划分进行了优化，获得更优的性能，降低了碎片率。动态内存核心算法框图如下：

根据空闲内存块的大小，使用多个空闲链表来管理。根据内存空闲块大小分为两个部分：[4, 127]和[27, 231]，如上图size class所示：

• 对[4,127]区间的内存进行等分，如上图绿色部分所示，分为31个小区间，每个小区间对应内存块大小为4字节的倍数。每个小区间对应一个空闲内存链表和用于标记对应空闲内存链表是否为空的一个比特位，值为1时，空闲链表非空。[4,127]区间的内存使用1个32位无符号整数位图标记。

• 大于127字节的空闲内存块，按照2的次幂区间大小进行空闲链表管理。总共分为24个小区间，每个小区间又等分为8个二级小区间，见上图蓝色的Size Class和Size SubClass部分。每个二级小区间对应一个空闲链表和用于标记对应空闲内存链表是否为空的一个比特位。总共24*8=192个二级小区间，对应192个空闲链表和192/32=6个32位无符号整数位图标记。

例如，当有40字节的空闲内存需要插入空闲链表时，对应小区间[40,43]，第10个空闲链表，位图标记的第10比特位。把40字节的空闲内存挂载第10个空闲链表上，并判断是否需要更新位图标记。当需要申请40字节的内存时，根据位图标记获取存在满足申请大小的内存块的空闲链表，从空闲链表上获取空闲内存节点。如果分配的节点大于需要申请的内存大小，进行分割节点操作，剩余的节点重新挂载到相应的空闲链表上。当有580字节的空闲内存需要插入空闲链表时，对应二级小区间[2^9,2^9+2^6]，第31+2*8=47个空闲链表，第2个位图标记的第17比特位。把580字节的空闲内存挂载第47个空闲链表上，并判断是否需要更新位图标记。当需要申请580字节的内存时，根据位图标记获取存在满足申请大小的内存块的空闲链表，从空闲链表上获取空闲内存节点。如果分配的节点大于需要申请的内存大小，进行分割节点操作，剩余的节点重新挂载到相应的空闲链表上。如果对应的空闲链表为空，则向更大的内存区间去查询是否有满足条件的空闲链表，实际计算时，会一次性查找到满足申请大小的空闲链表。

动态内存管理结构如下图所示：

• 内存池池头部分

内存池池头部分包含内存池信息和位图标记数组和空闲链表数组。内存池信息包含内存池起始地址及堆区域总大小，内存池属性。位图标记数组有7个32位无符号整数组成，每个比特位标记对应的空闲链表是否挂载空闲内存块节点。空闲内存链表包含223个空闲内存头节点信息，每个空闲内存头节点信息维护内存节点头和空闲链表中的前驱、后继空闲内存节点。

• 内存池节点部分

包含3种类型节点，未使用空闲内存节点，已使用内存节点，尾节点。每个内存节点维护一个前序指针，指向内存池中上一个内存节点，维护大小和使用标记，标记该内存节点的大小和是否使用等。空闲内存节点和已使用内存节点后面的数据域，尾节点没有数据域。

---

本文通过分析动态内存模块的源码，帮助读者掌握动态内存的使用。本文中所涉及的源码，以OpenHarmony LiteOS-M内核为例，均可以在开源站点https://gitee.com/openharmony/kernel_liteos_m 获取。接下来，我们看下动态内存的结构体，动态内存初始化，动态内存常用操作的源代码。

1、动态内存结构体定义和常用宏定义

1.1 动态内存结构体定义

动态内存的结构体有动态内存池信息结构体OsMemPoolInfo，动态内存池头结构体OsMemPoolHead、动态内存节点头结构体OsMemNodeHead，已使用内存节点结构体OsMemUsedNodeHead，空闲内存节点结构体OsMemFreeNodeHead。这些结构体定义在文件kernel\src\mm\los_memory.c中，下文会结合上文的动态内存管理结构示意图对各个结构体的成员变量进行说明。

1.1.1 动态内存池池头相关结构体

动态内存池信息结构体OsMemPoolInfo维护内存池的开始地址和大小信息。三个主要的成员是内存池开始地址.pool，内存池大小.poolSize和内存值属性.attr。如果开启宏LOSCFG_MEM_WATERLINE，还会维护内存池的水线数值。

struct OsMemPoolInfo {
    VOID *pool;               /* 内存池的内存开始地址 */
    UINT32 totalSize;         /* 内存池总大小 */
    UINT32 attr;              /* 内存池属性 */
#if (LOSCFG_MEM_WATERLINE == 1)
    UINT32 waterLine;         /* 内存池中内存最大使用值 */
    UINT32 curUsedSize;       /* 内存池中当前已使用的大小 */
#endif
};

动态内存池头结构体OsMemPoolHead源码如下，除了动态内存池信息结构体struct OsMemPoolInfo info，还维护2个数组，一个是空闲内存链表位图数组freeListBitmap[]，一个是空闲内存链表数组freeList[]。宏定义OS_MEM_BITMAP_WORDS和OS_MEM_FREE_LIST_COUNT后文会介绍。

struct OsMemPoolHead {
    struct OsMemPoolInfo info;
    UINT32 freeListBitmap[OS_MEM_BITMAP_WORDS];
    struct OsMemFreeNodeHead *freeList[OS_MEM_FREE_LIST_COUNT];
#if (LOSCFG_MEM_MUL_POOL == 1)
    VOID *nextPool;
#endif
};

1.1.2 动态内存池内存节点相关结构体

先看下动态内存节点头结构体OsMemNodeHead的定义，⑴处如果开启内存节点完整性检查的宏LOSCFG_BASE_MEM_NODE_INTEGRITY_CHECK，会维护魔术字.magic进行校验。⑵处如果开启内存泄漏检查的宏，会维护链接寄存器数组linkReg[]。⑶处的成员变量是个指针组合体，内存池中的每个内存节点头维护指针执行上一个内存节点。⑷处维护内存节点的大小和标记信息。

struct OsMemNodeHead {
  #if (LOSCFG_BASE_MEM_NODE_INTEGRITY_CHECK == 1)
⑴    UINT32 magic;
  #endif
  #if (LOSCFG_MEM_LEAKCHECK == 1)
⑵    UINTPTR linkReg[LOSCFG_MEM_RECORD_LR_CNT];
  #endif
      union {
          struct OsMemNodeHead *prev; /* The prev is used for current node points to the previous node */
          struct OsMemNodeHead *next; /* The next is used for sentinel node points to the expand node */
⑶     } ptr;
 #if (LOSCFG_MEM_FREE_BY_TASKID == 1)
⑷    UINT32 taskID : 6;
      UINT32 sizeAndFlag : 26;
  #else
      UINT32 sizeAndFlag;
  #endif
  };

接着看下已使用内存节点结构体OsMemUsedNodeHead，该结构体比较简单，直接以动态内存节点头结构体OsMemNodeHead作为唯一的成员。

struct OsMemUsedNodeHead {
    struct OsMemNodeHead header;
};

我们再看下空闲内存节点结构体OsMemFreeNodeHead，除了动态内存节点头结构体OsMemNodeHead成员，还包含2个指针分别指向上一个和下一个空闲内存节点。

struct OsMemFreeNodeHead {
    struct OsMemNodeHead header;
    struct OsMemFreeNodeHead *prev;
    struct OsMemFreeNodeHead *next;
};

1.2 动态内存核心算法相关的宏和函数

动态内存中还提供了一些和TLSF算法相关的宏定义和内联函数，这些宏非常重要，在分析源代码前需要熟悉下这些宏的定义。可以结合上文的动态内存核心算法框图进行学习。⑴处的宏对处于[2^n,2^(n+1)]，其中（n=7,8，…30）区间的大内存块进行2^3=8等分。⑵处的宏，定义处于[4,127]区间的小内存块划分为31个，即4,8,12，…，124。⑶处定义小内存的上界值，考虑内存对齐和粒度，最大值只能取到124。

⑷处的宏表示处于[2^n,2^(n+1)]，其中（n=7,8，…30）区间的大内存分为24个小区间，其中n=7 就是⑺处定义的宏OS_MEM_LARGE_START_BUCKET。⑻处对应空闲内存链表的长度。⑼处是空闲链表位图数组的长度，31个小内存使用1个位图字，所以需要加1。⑽处定义位图掩码，每个位图字是32位无符号整数。

继续看下内联函数。⑾处函数查找位图字中的第一个1的比特位，这个实现的功能类似内建函数__builtin_ctz。该函数用于获取空闲内存链表对应的位图字中，第一个挂载着空闲内存块的空闲内存链表。⑿处获取位图字中的最后一个1的比特位，(从32位二进制数值从左到右依次第0,1,…,31位)。⒀处函数名称中的Log是对数英文logarithm的缩写，函数用于计算以2为底的对数的整数部分。⒁处获取内存区间的大小级别编号，对于小于128字节的，有31个级别，对处于[2^n,2^(n+1)]，其中（n=7,8，…30）区间的内存，有24个级别。⒂处根据内存大小，内存区间一级编号获取获取二级小区间的编号，对处于[2^n,2^(n+1)]，其中（n=7,8，…30）区间的内存，有8个二级小区间。

    /* The following is the macro definition and interface implementation related to the TLSF. */

    /* Supposing a Second Level Index: SLI = 3. */
⑴  #define OS_MEM_SLI                      3
    /* Giving 1 free list for each small bucket: 4, 8, 12, up to 124. */
⑵  #define OS_MEM_SMALL_BUCKET_COUNT       31
⑶  #define OS_MEM_SMALL_BUCKET_MAX_SIZE    128
    /* Giving 2^OS_MEM_SLI free lists for each large bucket. */
⑷  #define OS_MEM_LARGE_BUCKET_COUNT       24
    /* OS_MEM_SMALL_BUCKET_MAX_SIZE to the power of 2 is 7. */
⑺  #define OS_MEM_LARGE_START_BUCKET       7

    /* The count of free list. */
⑻  #define OS_MEM_FREE_LIST_COUNT  (OS_MEM_SMALL_BUCKET_COUNT + (OS_MEM_LARGE_BUCKET_COUNT << OS_MEM_SLI))
    /* The bitmap is used to indicate whether the free list is empty, 1: not empty, 0: empty. */
⑼  #define OS_MEM_BITMAP_WORDS     ((OS_MEM_FREE_LIST_COUNT >> 5) + 1)

⑽  #define OS_MEM_BITMAP_MASK 0x1FU

    /* Used to find the first bit of 1 in bitmap. */
⑾  STATIC INLINE UINT16 OsMemFFS(UINT32 bitmap)
    {
        bitmap &= ~bitmap + 1;
        return (OS_MEM_BITMAP_MASK - CLZ(bitmap));
    }

    /* Used to find the last bit of 1 in bitmap. */
⑿  STATIC INLINE UINT16 OsMemFLS(UINT32 bitmap)
    {
        return (OS_MEM_BITMAP_MASK - CLZ(bitmap));
    }

⒀  STATIC INLINE UINT32 OsMemLog2(UINT32 size)
    {
        return (size > 0) ? OsMemFLS(size) : 0;
    }

    /* Get the first level: f = log2(size). */
⒁  STATIC INLINE UINT32 OsMemFlGet(UINT32 size)
    {
        if (size < OS_MEM_SMALL_BUCKET_MAX_SIZE) {
            return ((size >> 2) - 1); /* 2: The small bucket setup is 4. */
        }
        return (OsMemLog2(size) - OS_MEM_LARGE_START_BUCKET + OS_MEM_SMALL_BUCKET_COUNT);
    }

    /* Get the second level: s = (size - 2^f) * 2^SLI / 2^f. */
⒂  STATIC INLINE UINT32 OsMemSlGet(UINT32 size, UINT32 fl)
    {
        if ((fl < OS_MEM_SMALL_BUCKET_COUNT) || (size < OS_MEM_SMALL_BUCKET_MAX_SIZE)) {
            PRINT_ERR("fl or size is too small, fl = %u, size = %u\n", fl, size);
            return 0;
        }

        UINT32 sl = (size << OS_MEM_SLI) >> (fl - OS_MEM_SMALL_BUCKET_COUNT + OS_MEM_LARGE_START_BUCKET);
        return (sl - (1 << OS_MEM_SLI));
    }

2、动态内存常用操作

动态内存管理模块为用户提供初始化和删除内存池、申请、释放动态内存等操作，我们来分析下接口的源代码。在分析下内存操作接口之前，我们先看下一下常用的内部接口。

2.1 动态内存内部接口

2.1.1 设置和清理空闲内存链表标记位

⑴处函数OsMemSetFreeListBit需要2个参数，一个是内存池池头head，一个是空闲内存链表索引index。当空闲内存链表上挂载有空闲内存块时，位图字相应的位需要设置为1。⑴处函数OsMemClearFreeListBit做相反的操作，当空闲内存链表上不再挂载空闲内存块时，需要对应的比特位清零。

  STATIC INLINE VOID OsMemSetFreeListBit(struct OsMemPoolHead *head, UINT32 index)
  {
⑴    head->freeListBitmap[index >> 5] |= 1U << (index & 0x1f);
  }

  STATIC INLINE VOID OsMemClearFreeListBit(struct OsMemPoolHead *head, UINT32 index)
  {
⑵    head->freeListBitmap[index >> 5] &= ~(1U << (index & 0x1f));
  }

2.1.2 合并内存节点

函数VOID OsMemMergeNode(struct OsMemNodeHead *node)用于合并给定节点struct OsMemNodeHead *node和它前一个空闲节点。⑴处把前一个节点的大小加上要合入节点的大小。⑵处获取给定节点的下一个节点，然后执行⑶把它的前一个节点指向给定节点的前一个节点，完成节点的合并。其中宏OS_MEM_NODE_GET_LAST_FLAG用于判断是否最后一个节点，默认为0，可以自行查看下该宏的定义。

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;
    }
}

2.1.3 分割内存节点

函数VOID OsMemSplitNode(VOID *pool, struct OsMemNodeHead *allocNode, UINT32 allocSize)用于分割内存节点，需要三个参数。VOID *pool是内存池起始地址，struct OsMemNodeHead *allocNode表示从该内存节点分配出需要的内存，UINT32 allocSize是需要分配的内存大小。分割之后剩余的部分，如果下一个节点是空闲节点，则合并一起。分割剩余的节点会挂载到空闲内存链表上。

⑴处表示newFreeNode是分配之后剩余的空闲内存节点，设置它的上一个节点为分配的节点，并设置剩余内存大小。⑵处调整分配内存的大小，⑶处获取下一个节点，然后执行⑷下一个节点的前一个节点设置为新的空闲节点newFreeNode。⑸处判断下一个节点是否被使用，如果没有使用，则把下一个节点从链表中删除，然后和空闲节点newFreeNode合并。⑹处分割剩余的空闲内存节点挂载到链表上。

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);
}

2.1.4 重新申请内存

OsMemReAllocSmaller()函数用于从一个大的内存块里重新申请一个较小的内存，他需要的4个参数分别是：VOID *pool是内存池起始地址，UINT32 allocSize是重新申请的内存的大小，struct OsMemNodeHead *node是当前需要重新分配内存的内存节点，UINT32 nodeSize是当前节点的大小。⑴设置内存节点selfNode.sizeAndFlag为去除标记后的实际大小，⑵按需分割节点，⑶分割后的节点设置已使用标记，完成完成申请内存。

STATIC INLINE VOID OsMemReAllocSmaller(VOID *pool, UINT32 allocSize, struct OsMemNodeHead *node, UINT32 nodeSize)
{
#if (LOSCFG_MEM_WATERLINE == 1)
    struct OsMemPoolHead *poolInfo = (struct OsMemPoolHead *)pool;
#endif
⑴  node->sizeAndFlag = nodeSize;
    if ((allocSize + OS_MEM_MIN_LEFT_SIZE) <= nodeSize) {
⑵       OsMemSplitNode(pool, node, allocSize);
#if (LOSCFG_MEM_WATERLINE == 1)
        poolInfo->info.curUsedSize -= nodeSize - allocSize;
#endif
    }
⑶  OS_MEM_NODE_SET_USED_FLAG(node->sizeAndFlag);
#if (LOSCFG_MEM_LEAKCHECK == 1)
    OsMemLinkRegisterRecord(node);
#endif
}

2.1.5 合并节点重新申请内存

最后，再来看下函数函数OsMemMergeNodeForReAllocBigger()，用于合并内存节点，重新分配更大的内存空间。它需要5个参数，VOID *pool是内存池起始地址，UINT32 allocSize是重新申请的内存的大小，struct OsMemNodeHead *node是当前需要重新分配内存的内存节点，UINT32 nodeSize是当前节点的大小，struct OsMemNodeHead *nextNode是下一个内存节点。⑴处设置内存节点的大小为去除标记后的实际大小，⑵把下一个节点从链表上删除，然后合并节点。⑶处如果合并后的节点大小超过需要重新分配的大小，则分割节点。⑷处把申请的内存节点标记为已使用，完成完成申请内存

STATIC INLINE VOID OsMemMergeNodeForReAllocBigger(VOID *pool, UINT32 allocSize, struct OsMemNodeHead *node,
                                                  UINT32 nodeSize, struct OsMemNodeHead *nextNode)
{
⑴  node->sizeAndFlag = nodeSize;
⑵  OsMemFreeNodeDelete(pool, (struct OsMemFreeNodeHead *)nextNode);
    OsMemMergeNode(nextNode);
    if ((allocSize + OS_MEM_MIN_LEFT_SIZE) <= node->sizeAndFlag) {
⑶       OsMemSplitNode(pool, node, allocSize);
    }
⑷  OS_MEM_NODE_SET_USED_FLAG(node->sizeAndFlag);
    OsMemWaterUsedRecord((struct OsMemPoolHead *)pool, node->sizeAndFlag - nodeSize);
#if (LOSCFG_MEM_LEAKCHECK == 1)
    OsMemLinkRegisterRecord(node);
#endif
}

2.1.6 空闲内存链表相关操作

动态内存提供了针对空闲内存链表的几个操作，我们依次分析下这些操作的代码。首先看下函数OsMemFreeListIndexGet，根据内存节点大小获取空闲内存链表的索引。⑴处先获取一级索引，⑵处获取二级索引，然后计算空闲链表的索引并返回。

STATIC INLINE UINT32 OsMemFreeListIndexGet(UINT32 size)
{
⑴  UINT32 fl = OsMemFlGet(size);
    if (fl < OS_MEM_SMALL_BUCKET_COUNT) {
        return fl;
    }

⑵  UINT32 sl = OsMemSlGet(size, fl);
    return (OS_MEM_SMALL_BUCKET_COUNT + ((fl - OS_MEM_SMALL_BUCKET_COUNT) << OS_MEM_SLI) + sl);
}

接着看下函数OsMemListAdd，如何把空闲内存节点插入空闲内存链表。⑴处获取空闲链表的第一个节点，如果节点不为空，则把这个节点的前驱节点设置为待插入节点node。⑵处设置待插入节点的前驱、后继节点，然后把该节点赋值给空闲链表pool->freeList[listIndex]。最后执行⑶处代码，把设置空闲链表位图字，并设置魔术字。

STATIC INLINE VOID OsMemListAdd(struct OsMemPoolHead *pool, UINT32 listIndex, struct OsMemFreeNodeHead *node)
{
⑴  struct OsMemFreeNodeHead *firstNode = pool->freeList[listIndex];
    if (firstNode != NULL) {
        firstNode->prev = node;
    }
⑵  node->prev = NULL;
    node->next = firstNode;
    pool->freeList[listIndex] = node;
⑶  OsMemSetFreeListBit(pool, listIndex);
    OS_MEM_SET_MAGIC(&node->header);
}

最后，分析下函数OsMemListDelete如何从空闲内存链表删除指定的空闲内存节点。⑴处如果删除的节点是空闲内存链表的第一个节点，则需要把空闲链表执行待删除节点的下一个节点。如果下一个节点为空，需要执行⑵清除空闲链表的位图字。否则执行⑶把下一个节点的前驱节点设置为空。如果待删除节点不是空闲链表的第一个节点，执行⑷把待删除节点的前驱节点的后续节点设置为待删除节点的后继节点。如果待删除节点不为最后一个节点，需要执行⑸把待删除节点的后继节点的前驱节点设置为待删除节点的前驱节点。最后需要设置下魔术字。

STATIC INLINE VOID OsMemListDelete(struct OsMemPoolHead *pool, UINT32 listIndex, struct OsMemFreeNodeHead *node)
{
⑴  if (node == pool->freeList[listIndex]) {
        pool->freeList[listIndex] = node->next;
        if (node->next == NULL) {
⑵          OsMemClearFreeListBit(pool, listIndex);
        } else {
⑶          node->next->prev = NULL;
        }
    } else {
⑷      node->prev->next = node->next;
        if (node->next != NULL) {
⑸          node->next->prev = node->prev;
        }
    }
    OS_MEM_SET_MAGIC(&node->header);
}

2.1.7 空闲内存节点相关操作

动态内存提供了针对空闲内存的几个操作，如OsMemFreeNodeAdd、OsMemFreeNodeDelete、OsMemFreeNodeGet。

函数OsMemFreeNodeAdd用于把一个空闲内存节点加入相应的空闲内存链表上。⑴处调用函数获取空闲内存链表的索引，然后执行⑵把空闲内存节点加入空闲链表。

STATIC INLINE VOID OsMemFreeNodeAdd(VOID *pool, struct OsMemFreeNodeHead *node)
{
⑴  UINT32 index = OsMemFreeListIndexGet(node->header.sizeAndFlag);
    if (index >= OS_MEM_FREE_LIST_COUNT) {
        LOS_Panic("The index of free lists is error, index = %u\n", index);
    }
⑵  OsMemListAdd(pool, index, node);
}

函数OsMemFreeNodeDelete用于把一个空闲内存节点从相应的空闲内存链表上删除。代码较简单，获取空闲内存链表的索引，然后调用函数OsMemListDelete进行删除。

STATIC INLINE VOID OsMemFreeNodeDelete(VOID *pool, struct OsMemFreeNodeHead *node)
{
    UINT32 index = OsMemFreeListIndexGet(node->header.sizeAndFlag);
    OsMemListDelete(pool, index, node);
}

函数OsMemFreeNodeGet根据内存池地址和需要的内存大小获取满足大小条件的空闲内存块。⑴处调用函数获取满足大小条件的内存块，然后执行⑵把获取到的内存块从空闲内存链表删除，返回内存节点地址。

STATIC INLINE struct OsMemNodeHead *OsMemFreeNodeGet(VOID *pool, UINT32 size)
{
    struct OsMemPoolHead *poolHead = (struct OsMemPoolHead *)pool;
    UINT32 index;
⑴  struct OsMemFreeNodeHead *firstNode = OsMemFindNextSuitableBlock(pool, size, &index);
    if (firstNode == NULL) {
        return NULL;
    }

⑵  OsMemListDelete(poolHead, index, firstNode);

    return &firstNode->header;
}

最后，分析下函数OsMemFindNextSuitableBlock。⑴处根据需要的内存块大小获取一级区间编号，如果申请的内存处于[4,127]区间，执行⑵处记录空闲内存链表索引。如果需要申请的是大内存，执行⑶处代码。先获取二级区间索引，然后计算出空闲内存链表的索引值index。这样计算出来的空闲内存链表下可能并没有挂载空闲内存块，调用⑷处函数OsMemNotEmptyIndexGet获取挂载空闲内存块的空闲内存链表索引值。如果成功获取到满足大小的空闲内存块，返回空闲链表索引值，否则继续执行后续代码。⑹处对空闲链表位图字进行遍历，循环中的自增变量index对应一级区间编号。如果位图字不为空，执行⑺获取这个位图字对应的最大的空闲内存链表的索引。

如果执行到⑻处，说明没有匹配到合适的内存块，返回空指针。⑼处表示存在满足大小的空闲内存链表，调用函数OsMemFindCurSuitableBlock获取合适的内存块并返回。⑽处标签表示获取到合适的空闲内存链表索引，返回空闲内存链表。

STATIC INLINE struct OsMemFreeNodeHead *OsMemFindNextSuitableBlock(VOID *pool, UINT32 size, UINT32 *outIndex)
{
    struct OsMemPoolHead *poolHead = (struct OsMemPoolHead *)pool;
⑴  UINT32 fl = OsMemFlGet(size);
    UINT32 sl;
    UINT32 index, tmp;
    UINT32 curIndex = OS_MEM_FREE_LIST_COUNT;
    UINT32 mask;

    do {
        if (fl < OS_MEM_SMALL_BUCKET_COUNT) {
⑵          index = fl;
        } else {
⑶          sl = OsMemSlGet(size, fl);
            curIndex = ((fl - OS_MEM_SMALL_BUCKET_COUNT) << OS_MEM_SLI) + sl + OS_MEM_SMALL_BUCKET_COUNT;
            index = curIndex + 1;
        }

⑷      tmp = OsMemNotEmptyIndexGet(poolHead, index);
        if (tmp != OS_MEM_FREE_LIST_COUNT) {
⑸          index = tmp;
            goto DONE;
        }

⑹      for (index = LOS_Align(index + 1, 32); index < OS_MEM_FREE_LIST_COUNT; index += 32) {
            mask = poolHead->freeListBitmap[index >> 5]; /* 5: Divide by 32 to calculate the index of the bitmap array. */
            if (mask != 0) {
⑺              index = OsMemFFS(mask) + index;
                goto DONE;
            }
        }
    } while (0);

⑻  if (curIndex == OS_MEM_FREE_LIST_COUNT) {
        return NULL;
    }

⑼  *outIndex = curIndex;
    return OsMemFindCurSuitableBlock(poolHead, curIndex, size);
DONE:
    *outIndex = index;
⑽  return poolHead->freeList[index];
}

我们再详细分析下函数OsMemNotEmptyIndexGet的源码。⑴处根据空闲内存链表索引获取位图字，⑵处判断空闲内存链表索引对应的一级内存区间对应的二级小内存区间是否存在满足条件的空闲内存块。其中index & OS_MEM_BITMAP_MASK对索引只取低5位后，可以把索引值和位图字中的比特位关联起来，比如index为39时，index & OS_MEM_BITMAP_MASK等于7，对应位图字的第7位。表达式~((1 << (index & OS_MEM_BITMAP_MASK)) - 1)则用于表示大于空闲内存链表索引index的索引值对应的位图字。⑵处的语句执行后，mask就表示空闲链表索引值大于index的链表索引对应的位图字的值。当mask不为0时，表示存在满足内存大小的空闲内存块，则执行⑶处代码，其中OsMemFFS(mask)获取位图字中第一个为1的比特位位数，该位对应着挂载空闲内存块的链表。(index & ~OS_MEM_BITMAP_MASK)对应链表索引的高位，加上位图字位数就计算出挂载着满足申请条件的空闲内存链表的索引值。

STATIC INLINE UINT32 OsMemNotEmptyIndexGet(struct OsMemPoolHead *poolHead, UINT32 index)
{
⑴  UINT32 mask = poolHead->freeListBitmap[index >> 5]; /* 5: Divide by 32 to calculate the index of the bitmap array. */
⑵  mask &= ~((1 << (index & OS_MEM_BITMAP_MASK)) - 1);
    if (mask != 0) {
⑶      index = OsMemFFS(mask) + (index & ~OS_MEM_BITMAP_MASK);
        return index;
    }

    return OS_MEM_FREE_LIST_COUNT;
}

最后，再看下函数OsMemFindCurSuitableBlock。⑴处循环遍历空闲内存链表上挂载的内存块，如果遍历到的内存块大小大于需要的大小，则执行⑵返回该空闲内存块。否则返回空指针。

STATIC INLINE struct OsMemFreeNodeHead *OsMemFindCurSuitableBlock(struct OsMemPoolHead *poolHead,
                                        UINT32 index, UINT32 size)
{
    struct OsMemFreeNodeHead *node = NULL;

⑴  for (node = poolHead->freeList[index]; node != NULL; node = node->next) {
        if (node->header.sizeAndFlag >= size) {
⑵           return node;
        }
    }

    return NULL;
}