LiteOS内核源码分析系列一 盘点那些重要的数据结构 -- SortLinkList

在学习Huawei LiteOS源代码的时候，常常会遇到一些数据结构的使用。如果没有掌握这它们的用法，阅读LiteOS源代码的时候会很费解、很吃力。本文会给读者介绍下LiteOS源码中常用的几个数据结构，包括: 双向循环链表LOS_DL_LIST，优先级队列Priority Queue，排序链表SortLinkList等。在讲解时，会结合相关的绘图，培养数据结构的平面想象能力，帮助更好的学习和理解这些数据结构用法。

本文中所涉及的LiteOS源码，均可以在LiteOS开源站点https://gitee.com/LiteOS/LiteOS 获取。

这是第三部分，也是最后一部分，我们来看看SortLinkList 排序链表。

3、SortLinkList 排序链表

SortLinkList是LiteOS另外一个比较重要的数据结构，它在LOS_DL_LIST双向链表结构体的基础上，增加了RollNum滚动数，用于涉及时间到期、超时的业务场景。在阻塞任务是否到期，定时器是否超时场景下，非常依赖SortLinkList排序链表这个数据结构。LiteOS排序链表支持单一链表LOSCFG_BASE_CORE_USE_SINGLE_LIST和多链表LOSCFG_BASE_CORE_USE_MULTI_LIST，可以通过LiteOS的menuconfig工具更改Sortlink Option选项来配置使用单链表还是多链表，我们这里先讲述前者。

排序链表SortLinkList接口主要内部使用，用户业务开发时不涉及，不对外提供接口。SortLinkList排序链表的代码都在kernel\base\include\los_sortlink_pri.h头文件和kernel\base\los_sortlink.c实现文件中。

3.1 SortLinkList 排序链表结构体定义

在kernel\base\include\los_sortlink_pri.h文件中定义了两个结构体，如下述源码所示。

SortLinkAttribute结构体定义排序链表的头结点LOS_DL_LIST *sortLink，游标UINT16 cursor。SortLinkList结构体定义排序链表的业务节点，除了负责双向链接的成员变量LOS_DL_LIST *sortLink，还包括业务信息，UINT32 idxRollNum，即index索引和rollNum滚动数。在单链表的排序链表中，idxRollNum表示多长时间后会到期。

我们举个例子，看下面的示意图。排序链表中，有3个链表节点，分别在25 ticks、35 ticks、50 ticks后到期超时，已经按到期时间进行了先后排序。三个节点的idxRollNum分别等于25 ticks、10
ticks、15 ticks。每个节点的idxRollNum保存的不是这个节点的超时时间，而是从链表head节点到该节点的所
有节点的idxRollNum的加和，才是该节点的超时时间。这样设计的好处就是，随着Tick时间推移，只需要更新第一个节点的超时时间就好，可以好好体会一下。

示意图如下：

源码如下：

typedef struct {
    LOS_DL_LIST sortLinkNode;
    UINT32 idxRollNum;
} SortLinkList;

typedef struct {
    LOS_DL_LIST *sortLink;
    UINT16 cursor;
    UINT16 reserved;
} SortLinkAttribute;

下面我们来学习下排序链表支持的那些操作。

3.2 SortLinkList 排序链表接口

在继续之前我们先看下kernel\base\include\los_sortlink_pri.h文件中的一些单链表配置LOSCFG_BASE_CORE_USE_SINGLE_LIST下的宏定义，包含滚动数最大值等，对滚动数进行加、减、减少1等操作。

源码如下：

#define OS_TSK_SORTLINK_LOGLEN  0U
#define OS_TSK_SORTLINK_LEN     1U
#define OS_TSK_MAX_ROLLNUM      0xFFFFFFFEU
#define OS_TSK_LOW_BITS_MASK    0xFFFFFFFFU
#define SORTLINK_CURSOR_UPDATE(CURSOR)
#define SORTLINK_LISTOBJ_GET(LISTOBJ, SORTLINK)  (LISTOBJ = SORTLINK->sortLink)
#define ROLLNUM_SUB(NUM1, NUM2)         NUM1 = (ROLLNUM(NUM1) - ROLLNUM(NUM2))
#define ROLLNUM_ADD(NUM1, NUM2)         NUM1 = (ROLLNUM(NUM1) + ROLLNUM(NUM2))
#define ROLLNUM_DEC(NUM)                NUM = ((NUM) - 1)
#define ROLLNUM(NUM)                    (NUM)
#define SET_SORTLIST_VALUE(sortList, value) (((SortLinkList *)(sortList))->idxRollNum = (value))

3.2.1 UINT32 OsSortLinkInit() 排序链表初始化

在系统启动软件初始化，初始化任务、初始化定时器时，会分别初始化任务的排序链表和定时器的排序链表。

• kernel\base\los_task.c : UINT32 OsTaskInit(VOID)函数

     `ret = OsSortLinkInit(&g_percpu[index].taskSortLink);`
  

• kernel\base\los_swtmr.c : UINT32 OsSwtmrInit(VOID)函数

    `ret = OsSortLinkInit(&g_percpu[cpuid].swtmrSortLink);`
  

我们看下排序链表初始化函数的源代码，⑴处代码计算需要申请多少个双向链表的内存大小，对于单链表的排序链表，OS_TSK_SORTLINK_LOGLEN为0，为一个双向链表申请内存大小即可。然后申请内存，初始化申请的内存区域为0等，⑵处把申请的双向链表节点赋值给sortLinkHeader的链表节点，作为排序链表的头节点，然后调用LOS_ListInit()函数初始化为双向循环链表。

源码如下：

LITE_OS_SEC_TEXT_INIT UINT32 OsSortLinkInit(SortLinkAttribute *sortLinkHeader)
{
    UINT32 size;
    LOS_DL_LIST *listObject = NULL;

⑴  size = sizeof(LOS_DL_LIST) << OS_TSK_SORTLINK_LOGLEN;
    listObject = (LOS_DL_LIST *)LOS_MemAlloc(m_aucSysMem0, size); /* system resident resource */
    if (listObject == NULL) {
        return LOS_NOK;
    }

    (VOID)memset_s(listObject, size, 0, size);
⑵  sortLinkHeader->sortLink = listObject;
    LOS_ListInit(listObject);
    return LOS_OK;
}

3.2.2 VOID OsAdd2SortLink() 排序链表插入

在任务等待互斥锁、信号量等资源阻塞时，定时器启动时，这些需要等待指定时间的任务、定时器等，都会加入对应的排序链表。

我们一起看下代码，包含2个参数，第一个参数sortLinkHeader用于指定排序链表的头结点，第二个参数sortList是待插入的链表节点，此时该节点的滚动数等于对应阻塞任务或定时器的超时时间。

⑴处代码处理滚动数超大的场景，如果滚动数大于OS_TSK_MAX_ROLLNUM，则设置滚动数等于OS_TSK_MAX_ROLLNUM。⑵处代码，如果排序链表为空， 则把链表节点尾部插入。如果排序链表不为空，则执行⑶处代码，获取排序链表上的下一个节点SortLinkList *listSorted。⑷、⑸ 处代码，如果待插入节点的滚动数大于排序链表的下一个节点的滚动数，则把待插入节点的滚动数减去下一个节点的滚动数，并继续执行⑹处代码，继续与下下一个节点进行比较。否则，如果待插入节点的滚动数小于排序链表的下一个节点的滚动数，则把下一个节点的滚动数减去待插入节点的滚动数，然后跳出循环，继续执行⑺处代码，完成待插入节点的插入。插入过程，可以结合上文的示意图进行理解。

源码如下：

LITE_OS_SEC_TEXT VOID OsAdd2SortLink(const SortLinkAttribute *sortLinkHeader, SortLinkList *sortList)
{
    SortLinkList *listSorted = NULL;
    LOS_DL_LIST *listObject = NULL;
⑴  if (sortList->idxRollNum > OS_TSK_MAX_ROLLNUM) {
        SET_SORTLIST_VALUE(sortList, OS_TSK_MAX_ROLLNUM);
    }
    listObject = sortLinkHeader->sortLink;
⑵  if (listObject->pstNext == listObject) {
        LOS_ListTailInsert(listObject, &sortList->sortLinkNode);
    } else {
⑶      listSorted = LOS_DL_LIST_ENTRY(listObject->pstNext, SortLinkList, sortLinkNode);
        do {
⑷          if (ROLLNUM(listSorted->idxRollNum) <= ROLLNUM(sortList->idxRollNum)) {
                ROLLNUM_SUB(sortList->idxRollNum, listSorted->idxRollNum);
            } else {
⑸              ROLLNUM_SUB(listSorted->idxRollNum, sortList->idxRollNum);
                break;
            }

⑹         listSorted = LOS_DL_LIST_ENTRY(listSorted->sortLinkNode.pstNext, SortLinkList, sortLinkNode);
        } while (&listSorted->sortLinkNode != listObject);

⑺      LOS_ListTailInsert(&listSorted->sortLinkNode, &sortList->sortLinkNode);
    }
}

3.2.3 VOID OsDeleteSortLink() 排序链表删除

当任务恢复、删除，定时器停止的时候，会从对应的排序链表中删除。

我们一起阅读下删除函数的源代码，包含2个参数，第一个参数sortLinkHeader用于指定排序链表的头结点，第二个参数sortList是待删除的链表节点。

⑴处是获取排序链表的头结点listObject，⑵处代码检查要删除的节点是否在排序链表里，否则输出错误信息和回溯栈信息。⑶处代码判断是否排序链表里只有一个业务节点，如果只有一个节点，直接执行⑸处代码删除该节点即可。如果排序链表里有多个业务节点，则执行⑷处代码获取待删除节点的下一个节点nextSortList，把删除节点的滚动数加到下一个节点的滚动数里，然后执行⑸处代码执行删除操作。

源码如下：

LITE_OS_SEC_TEXT VOID OsDeleteSortLink(const SortLinkAttribute *sortLinkHeader, SortLinkList *sortList)
{
    LOS_DL_LIST *listObject = NULL;
    SortLinkList *nextSortList = NULL;

⑴  listObject = sortLinkHeader->sortLink;

⑵  OsCheckSortLink(listObject, &sortList->sortLinkNode);

⑶  if (listObject != sortList->sortLinkNode.pstNext) {
⑷      nextSortList = LOS_DL_LIST_ENTRY(sortList->sortLinkNode.pstNext, SortLinkList, sortLinkNode);
        ROLLNUM_ADD(nextSortList->idxRollNum, sortList->idxRollNum);
    }
⑸  LOS_ListDelete(&sortList->sortLinkNode);
}

3.2.4 UINT32 OsSortLinkGetNextExpireTime() 获取下一个超时到期时间

在Tickless特性，会使用此方法获取下一个超时到期时间。

我们一起阅读下源代码，包含1个参数，sortLinkHeader用于指定排序链表的头结点。

⑴处是获取排序链表的头结点listObject，⑵处代码判断排序链表是否为空，如果排序链表为空，则返回OS_INVALID_VALUE。如果链表不为空，⑶处代码获取排序链表的第一个业务节点，然后获取其滚动数，即过期时间，进行返回。

源码如下：

LITE_OS_SEC_TEXT UINT32 OsSortLinkGetNextExpireTime(const SortLinkAttribute *sortLinkHeader)
{
    UINT32 expireTime = OS_INVALID_VALUE;
    LOS_DL_LIST *listObject = NULL;
    SortLinkList *listSorted = NULL;

⑴  listObject = sortLinkHeader->sortLink;
⑵  if (!LOS_ListEmpty(listObject)) {
⑶      listSorted = LOS_DL_LIST_ENTRY(listObject->pstNext, SortLinkList, sortLinkNode);
        expireTime = listSorted->idxRollNum;
    }
    return expireTime;
}

3.2.5 OsSortLinkGetTargetExpireTime() 获取指定节点的超时时间

定时器获取剩余超时时间函数LOS_SwtmrTimeGet()会调用函数OsSortLinkGetTargetExpireTime() 获取指定节点的超时时间。

我们一起看下代码，包含2个参数，第一个参数sortLinkHeader用于指定排序链表的头结点，第二个参数targetSortList是待获取超时时间的目标链表节点。

⑴处代码获取目标节点的滚动数。⑵处代码获取排序链表的头结点listObject，⑶处代码获取排序链表上的下一个节点SortLinkList *listSorted。⑷处循环代码，当下一个节点不为目标链表节点的时候，依次循环，并执行⑸处代码把循环遍历的各个节点的滚动数相加，最终的计算结果即为目标节点的超时时间。

源码如下：

LITE_OS_SEC_TEXT_MINOR UINT32 OsSortLinkGetTargetExpireTime(const SortLinkAttribute *sortLinkHeader,
                                                            const SortLinkList *targetSortList)
{
    SortLinkList *listSorted = NULL;
    LOS_DL_LIST *listObject = NULL;
⑴  UINT32 rollNum = targetSortList->idxRollNum;

⑵  listObject = sortLinkHeader->sortLink;
⑶  listSorted = LOS_DL_LIST_ENTRY(listObject->pstNext, SortLinkList, sortLinkNode);

⑷  while (listSorted != targetSortList) {
⑸      rollNum += listSorted->idxRollNum;
        listSorted = LOS_DL_LIST_ENTRY((listSorted->sortLinkNode).pstNext, SortLinkList, sortLinkNode);
    }

    return rollNum;
}

3.2.6 VOID OsSortLinkUpdateExpireTime() 更新超时时间

在Tickless特性，会使用此方法更新超时时间。Tickless休眠sleep时，需要把休眠的ticks数目从排序链表里减去。调用此方法的函数会保障减去的ticks数小于节点的滚动数。

我们一起阅读下源代码，包含2个参数，第一个参数sleepTicks是休眠的ticks数，第二个参数sortLinkHeader用于指定排序链表的头结点。

⑴处获取排序链表的头结点listObject，⑵处代码获取下一个链表节点sortList，这个也是排序链表的第一个业务节点，然后把该节点的滚动数减去sleepTicks - 1完成超时时间更新。

源码如下：

LITE_OS_SEC_TEXT VOID OsSortLinkUpdateExpireTime(UINT32 sleepTicks, SortLinkAttribute *sortLinkHeader)
{
    SortLinkList *sortList = NULL;
    LOS_DL_LIST *listObject = NULL;

    if (sleepTicks == 0) {
        return;
    }

⑴  listObject = sortLinkHeader->sortLink;
⑵  sortList = LOS_DL_LIST_ENTRY(listObject->pstNext, SortLinkList, sortLinkNode);
    ROLLNUM_SUB(sortList->idxRollNum, sleepTicks - 1);
}

3.3 SortLinkList 排序链表和Tick时间关系

任务、定时器加入排序链表后，随时时间推移，一个tick一个tick的逝去，排序链表中的滚动数是如何更新的呢？

我们看看Tick中断的处理函数VOID OsTickHandler(VOID)，该函数在kernel\base\los_tick.c文件里。

当时间每走过一个tick，会调用该中断处理函数，代码片段中的⑴、⑵处的代码分别扫描任务和定时器，检查和更新时间。

LITE_OS_SEC_TEXT VOID OsTickHandler(VOID)
{
    UINT32 intSave;

    TICK_LOCK(intSave);
    g_tickCount[ArchCurrCpuid()]++;
    TICK_UNLOCK(intSave);
    ......
⑴  OsTaskScan(); /* task timeout scan */

#if (LOSCFG_BASE_CORE_SWTMR == YES)
⑵  OsSwtmrScan();
#endif
}

我们以OsTaskScan()为例，快速了解下排序链表和tick时间的关系。函数在kernel\base\los_task.c文件中，函数代码片段如下：
⑴处代码获取任务排序链表的第一个节点，然后执行下一行代码把该节点的滚动数减去1。⑵处代码循环遍历排序链表，如果滚动数为0，即时间到期了，会调用LOS_ListDelete()函数从从排序链表中删除，然后执行⑶处代码，获取对应的taskCB，然后进一步进行业务处理。读者可以自行查看更多代码，后续的文章中也会对任务、定时器进行专题进行讲解。

LITE_OS_SEC_TEXT VOID OsTaskScan(VOID)
{
    SortLinkList *sortList = NULL;
    ......
    LOS_DL_LIST *listObject = NULL;
    SortLinkAttribute *taskSortLink = NULL;

    taskSortLink = &OsPercpuGet()->taskSortLink;
    SORTLINK_CURSOR_UPDATE(taskSortLink->cursor);
    SORTLINK_LISTOBJ_GET(listObject, taskSortLink);
    ......
⑴  sortList = LOS_DL_LIST_ENTRY(listObject->pstNext, SortLinkList, sortLinkNode);
    ROLLNUM_DEC(sortList->idxRollNum);

⑵  while (ROLLNUM(sortList->idxRollNum) == 0) {
        LOS_ListDelete(&sortList->sortLinkNode);
⑶      taskCB = LOS_DL_LIST_ENTRY(sortList, LosTaskCB, sortList);
         ......
        sortList = LOS_DL_LIST_ENTRY(listObject->pstNext, SortLinkList, sortLinkNode);
    }
    ......
}

小结

掌握LiteOS内核的双向循环链表LOS_DL_LIST，优先级队列Priority Queue，排序链表SortLinkList等重要的数据结构，给进一步学习、分析LiteOS源代码打下了基础，让后续的学习更加容易。后续也会陆续推出更多的分享文章，敬请期待，也欢迎大家分享学习使用LiteOS的心得，有任何问题、建议，都可以留言给我们： https://gitee.com/LiteOS/LiteOS/issues 。为了更容易找到LiteOS代码仓，建议访问 https://gitee.com/LiteOS/LiteOS ，关注Watch、点赞Star、并Fork到自己账户下，如下图，谢谢。