关于数据结构:LiteOS盘点那些重要的数据结构

48次阅读

共计 21970 个字符,预计需要花费 55 分钟才能阅读完成。

摘要:本文会给读者介绍下 LiteOS 源码中罕用的几个数据结构,包含: 双向循环链表 LOS_DL_LIST,优先级队列 Priority Queue,排序链表 SortLinkList 等。

在学习 Huawei LiteOS 源代码的时候,经常会遇到一些数据结构的应用。如果没有把握这它们的用法,浏览 LiteOS 源代码的时候会很费解、很吃力。本文会给读者介绍下 LiteOS 源码中罕用的几个数据结构,包含: 双向循环链表 LOS_DL_LIST,优先级队列Priority Queue,排序链表SortLinkList 等。在解说时,会联合相干的绘图,造就数据结构的立体设想能力,帮忙更好的学习和了解这些数据结构用法。

本文中所波及的 LiteOS 源码,均能够在 LiteOS 开源站点 https://gitee.com/LiteOS/LiteOS 获取。

咱们首先来看看应用最多的双向循环链表Doubly Linked List

1、LOS_DL_LIST 双向循环链表

双向链表 LOS_DL_LIST 外围的代码都在 kernelincludelos_list.h 头文件中,蕴含 LOS_DL_LIST 构造体定义、一些 inline 内联函数LOS_ListXXX,还有一些双向链表相干的宏定义LOS_DL_LIST_XXXX

双向链表源代码、示例程序代码、开发文档如下:

  • kernelincludelos_list.h 双向链表头文件

    网页获取源码 https://gitee.com/LiteOS/Lite…。

  • demoskernelapilos_api_list.c 双向链表 Demo 程序

    网页获取源码 https://gitee.com/LiteOS/Lite…。

  • 开发指南双向链表文档

    在线文档 https://gitee.com/LiteOS/Lite…

1.1 LOS_DL_LIST 双向链表构造体

双向链表构造体 LOS_DL_LIST 定义如下。看得出来,双向链表的构造非常简单、通用、形象,只蕴含前驱、后继两个节点,负责承前启后的双向链表作用。双向链表不包任何业务数据信息,业务数据信息保护在业务的构造体中。双向链表作为业务构造体的成员应用,应用示例稍后会有讲述。

typedef struct LOS_DL_LIST {
    struct LOS_DL_LIST *pstPrev; /** 以后节点的指向前驱节点的指针 */
    struct LOS_DL_LIST *pstNext; /** 以后节点的指向后继节点的指针  */
} LOS_DL_LIST; 

从双向链表中的任意一个结点开始,都能够很不便地拜访它的前驱结点和后继结点,这种数据结构模式使得双向链表在查找、插入、删除等操作,对于十分不便。因为双向链表的环状构造,任何一个节点的位置都是平等的。从业务上,能够创立一个节点作为 Head 头节点,业务构造体的链表节点从 HEAD 节点开始挂载。从 head 节点的顺次遍历下一个节点,最初一个不等于 Head 节点的节点称之为 Tail 尾节点。这个 Tail 节点也是 Head 节点的前驱。从 Head 向前查找,能够更快的找到 Tail 节点。

咱们看看 LiteOS 内核代码中如何应用双向链表构造体的。上面是互斥锁构造体 LosMuxCB 定义,其中蕴含双向链表 LOS_DL_LIST muxList; 成员变量:

typedef struct {
    LOS_DL_LIST muxList; /** 互斥锁的双向链表 */
    LosTaskCB *owner; /** 以后持有锁的工作 TCB */
    UINT16 muxCount; /** 持有互斥锁的次数 */
    UINT8 muxStat; /** 互斥锁状态 OS_MUX_UNUSED, OS_MUX_USED */
    UINT32 muxId; /** 互斥锁 handler ID*/
} LosMuxCB; 

双向循环链表能够把各个互斥锁链接起来,链表和其余业务成员关系如下图所示:

LiteOS 的双向链表为用户提供上面初始化双向列表,减少、删除链表节点,判断节点是否为空,获取链表节点,获取链表所在的构造体,遍历双向链表,遍历蕴含双向链表的构造体等性能。咱们一一来具体的学习、剖析下代码。

1.2 LOS_DL_LIST 双向链表初始化

1.2.1 LOS_ListInit(LOS_DL_LIST *list)

LOS_DL_LIST的两个成员 *pstPrev*pstNext, 是 LOS_DL_LIST 构造体类型的指针。须要为双向链表节点申请长度为 sizeof(LOS_DL_LIST) 的一段内存空间。为链表节点申请结束内存后,能够调用初始化 LOS_ListInit(LOS_DL_LIST *list) 办法,把这个节点链接为环状的双向链表。初始化链表的时候,只有一个链表节点,这个节点的前序和后继节点都是本身。

链表节点初始化为链表,如图所示:

源码如下:

LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListInit(LOS_DL_LIST *list)
{
    list->pstNext = list;
    list->pstPrev = list;
} 

另外,还提供了一个宏LOS_DL_LIST_HEAD,间接定义一个双向链表节点并以该节点初始化为双向链表。

#define LOS_DL_LIST_HEAD(list) LOS_DL_LIST list = {&(list), &(list) } 

1.2.2 LOS_ListEmpty(LOS_DL_LIST *list)

该接口用于判断链表是否为空。如果双向链表的前驱 / 后继节点均为本身,只有一个链表 HEAD 头节点,没有挂载业务构造体的链表节点,称该链表为空链表。

源码如下:

LITE_OS_SEC_ALW_INLINE STATIC INLINE BOOL LOS_ListEmpty(LOS_DL_LIST *list)
{return (BOOL)(list->pstNext == list);
}

1.3 LOS_DL_LIST 双向链表节点操作

LiteOS双向链表提供三种链表节点插入方法,指定链表节点前面插入LOS_ListAdd、尾部插入LOS_ListTailInsert、头部插入LOS_ListHeadInsert。在头部插入的节点,从头部开始遍历时第一个遍历到,从尾部插入的节点,最初一个遍历到。

1.3.1 LOS_ListAdd(LOS_DL_LIST list, LOS_DL_LIST node)

这个 API 接口往链表节点 *list 所在的双向链表中插入一个链表节点 *node,插入地位在链表节点*list 的前面。如图所示,实现插入后,*node的后继节点是 list->pstNext*node 的前序节点是 *listlist->pstNext 的前序节点是 *node*list 的后续是 *node 节点。

图示:

源码如下:

LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListAdd(LOS_DL_LIST *list, LOS_DL_LIST *node)
{
    node->pstNext = list->pstNext;
    node->pstPrev = list;
    list->pstNext->pstPrev = node;
    list->pstNext = node;
} 

1.3.2 LOS_ListTailInsert(LOS_DL_LIST list, LOS_DL_LIST node)

这个 API 接口往链表节点 *list 所在的双向链表中插入一个链表节点 *node,插入地位在链表节点*list 的后面,在 list->pstPrev 节点的前面。

源码如下:

LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListTailInsert(LOS_DL_LIST *list, LOS_DL_LIST *node)
{LOS_ListAdd(list->pstPrev, node);
} 

1.3.3 LOS_ListHeadInsert(LOS_DL_LIST list, LOS_DL_LIST node)

这个 API 接口和 LOS_ListAdd() 接口实现同样的性能,往链表节点 *list 所在的双向链表中插入一个链表节点 *node,插入地位在链表节点*list 的前面。

源码如下:

LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListHeadInsert(LOS_DL_LIST *list, LOS_DL_LIST *node)
{LOS_ListAdd(list, node);
} 

LiteOS 双向链表提供两种链表节点的删除办法,指定节点删除LOS_ListDelete、删除并初始化为一个新链表LOS_ListDelInit


1.3.4 LOS_ListDelete(LOS_DL_LIST *node)

这个 API 接口将链表节点 *node 从所在的双向链表中删除。节点删除后,可能须要调用 Free() 函数开释节点所占用的内存。如图所示,*node节点后继节点的前序改为 *node 的前序,*node节点前序节点的后续改为 *node 的后续,并把 *node 节点的前序、后续节点设置为null

图示:

源码如下:

LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListDelete(LOS_DL_LIST *node)
{
    node->pstNext->pstPrev = node->pstPrev;
    node->pstPrev->pstNext = node->pstNext;
    node->pstNext = NULL;
    node->pstPrev = NULL;
} 

1.3.5 LOS_ListDelInit(LOS_DL_LIST *list)

这个 API 接口将链表节点 *list 从所在的双向链表中删除, 并把删除后的节点从新初始化为一个新的双向链表。

*list节点后继节点的前序改为 *list 的前序,*list节点前序节点的后续改为 *list 的后续。和 LOS_ListDelete() 办法不同的是,并不并把 *list 节点的前序、后续节点设置为 null,而是把这个删除的节点从新初始化为一个新的以*list 为头结点的双向链表。

源码如下:

LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListDelInit(LOS_DL_LIST *list)
{
    list->pstNext->pstPrev = list->pstPrev;
    list->pstPrev->pstNext = list->pstNext;
    LOS_ListInit(list);
} 

LiteOS 双向链表还提供获取链表节点、获取蕴含链表的构造体地址的操作。

1.3.6 LOS_DL_LIST_LAST(object)

这个宏定义获取链表的前驱节点。

源码如下:

#define LOS_DL_LIST_LAST(object) ((object)->pstPrev) 

1.3.7 LOS_DL_LIST_FIRST(object)

这个宏定义获取链表的后继节点。

源码如下:

#define LOS_DL_LIST_FIRST(object) ((object)->pstNext) 

1.3.8 LOS_OFF_SET_OF(type, member)

这个宏定义依据构造体类型名称 type 和其中的成员变量名称 member,获取member 成员变量绝对于构造体 type 的内存地址偏移量。在利用场景上,业务构造体蕴含双向链表作为成员,当晓得双向链表成员变量的内存地址时,和这个偏移量,能够进一步获取业务构造体的内存地址。

源码如下:

#define LOS_OFF_SET_OF(type, member) ((UINTPTR)&((type *)0)->member) 

1.3.9 LOS_DL_LIST_ENTRY(item, type, member)

依据业务构造体类型名称 type、其中的双向链表成员变量名称member,和双向链表的内存指针变量item,应用该宏定义LOS_DL_LIST_ENTRY 能够获取业务构造体的内存地址。

咱们以理论例子演示下这个宏 LOS_DL_LIST_ENTRY 是如何应用的。互斥锁的 control block 构造体 LosMuxCB 在上文曾经展现过其代码,有个双向链表的成员变量 LOS_DL_LIST muxList。在创立互斥锁的办法LOS_MuxCreate() 中,⑴ 处代码从闲暇互斥锁链表中获取一个闲暇的双向链表节点指针地址 LOS_DL_LIST *unusedMux,把这个作为第一个参数,构造体名称LosMuxCB 及其成员变量 muxList,别离作为第二、第三个参数,应用宏LOS_DL_LIST_ENTRY 能够计算出构造体的指针变量地址LosMuxCB *muxCreated,见⑵处代码。

LITE_OS_SEC_TEXT UINT32 LOS_MuxCreate(UINT32 *muxHandle)
{
    ......
    LosMuxCB *muxCreated = NULL;
    LOS_DL_LIST *unusedMux = NULL;
    ......
⑴  unusedMux = LOS_DL_LIST_FIRST(&g_unusedMuxList);
    LOS_ListDelete(unusedMux);
⑵  muxCreated = LOS_DL_LIST_ENTRY(unusedMux, LosMuxCB, muxList);
    ......
} 

从这个例子上,就比拟容易了解,这个宏定义能够用于什么样的场景,读者们能够浏览查看更多应用这个宏的例子,增强了解。

源码如下:

源码实现上,基于双向链表节点的内存地址,和双向链表成员变量在构造体中的地址偏移量,能够计算出构造体的内存地址。

#define LOS_DL_LIST_ENTRY(item, type, member) 
    ((type *)(VOID *)((CHAR *)(item) - LOS_OFF_SET_OF(type, member))) 

1.4 LOS_DL_LIST 双向循环链表遍历

LiteOS双向循环链表提供两种遍历双向链表的办法,LOS_DL_LIST_FOR_EACHLOS_DL_LIST_FOR_EACH_SAFE

1.4.1 LOS_DL_LIST_FOR_EACH(item, list)

该宏定义 LOS_DL_LIST_FOR_EACH 遍历双向链表,接口的第一个入参示意的是双向链表节点的指针变量,在遍历过程中顺次指向下一个链表节点。第二个入参是要遍历的双向链表的起始节点。这个宏是个循环条件局部,用户的业务代码写在宏前面的代码块 {} 内。

咱们以理论例子来演示这个宏 LOS_DL_LIST_FOR_EACH 是如何应用的。在 kernelbaseschedsched_sqlos_priqueue.c 文件中,UINT32 OsPriQueueSize(UINT32 priority)函数的片段如下:

&g_priQueueList[priority]是咱们要遍历的双向链表,curNode指向遍历过程中的链表节点,见⑴处代码代码。残缺代码请拜访咱们的开源站点。

UINT32 OsPriQueueSize(UINT32 priority)
{
    UINT32 itemCnt = 0;
    LOS_DL_LIST *curNode = NULL;
    ......
⑴  LOS_DL_LIST_FOR_EACH(curNode, &g_priQueueList[priority]) {
    ......
        task = OS_TCB_FROM_PENDLIST(curNode);
    ......
    }
    return itemCnt;
} 

源码如下:

#define LOS_DL_LIST_FOR_EACH(item, list) 
    for (item = (list)->pstNext;         
         (item) != (list);               
         item = (item)->pstNext) 

1.4.2 LOS_DL_LIST_FOR_EACH_SAFE(item, next, list)

该宏定义 LOS_DL_LIST_FOR_EACH_SAFELOS_DL_LIST_FOR_EACH惟一的区别就是多个入参next, 这个参数示意遍历到的双向链表节点的下一个节点。该宏用于平安删除,如果删除遍历到的item, 不影响持续遍历。

源码如下:

#define LOS_DL_LIST_FOR_EACH_SAFE(item, next, list)      
    for (item = (list)->pstNext, next = (item)->pstNext; 
         (item) != (list);                               
         item = next, next = (item)->pstNext) 

1.5 LOS_DL_LIST 遍历蕴含双向链表的构造体

LiteOS双向链表提供三个宏定义来遍历蕴含双向链表成员的构造体,LOS_DL_LIST_FOR_EACH_ENTRYLOS_DL_LIST_FOR_EACH_ENTRY_SAFELOS_DL_LIST_FOR_EACH_ENTRY_HOOK

1.5.1 LOS_DL_LIST_FOR_EACH_ENTRY(item, list, type, member)

该宏定义 LOS_DL_LIST_FOR_EACH_ENTRY 遍历双向链表,接口的第一个入参示意的是蕴含双向链表成员的构造体的指针变量,第二个入参是要遍历的双向链表的起始节点,第三个入参是要获取的构造体名称,第四个入参是在该构造体中的双向链表的成员变量名称。

咱们以理论例子来演示这个宏 LOS_DL_LIST_FOR_EACH_ENTRY 是如何应用的。在 kernelbaseschedsched_sqlos_priqueue.c 文件中,LosTaskCB *OsGetTopTask(VOID)函数的片段如下。构造体 LosTaskCB 蕴含双向链表成员变量 pendList,&g_priQueueList[priority] 是对应工作优先级prioritypendList的双向链表。会顺次遍历这个双向链表 &g_priQueueList[priority],依据遍历到的链表节点,顺次获取工作构造体LosTaskCB 的指针变量newTask,如⑴处代码所示。

LITE_OS_SEC_TEXT_MINOR LosTaskCB *OsGetTopTask(VOID)
{
    UINT32 priority;
    UINT32 bitmap;
    LosTaskCB *newTask = NULL;
    ......
⑴  LOS_DL_LIST_FOR_EACH_ENTRY(newTask, &g_priQueueList[priority], LosTaskCB, pendList) {
        ......
        OsPriQueueDequeue(&newTask->pendList);
        ......
    }
    ......
} 

源码如下:

源码实现上,for循环的初始化语句 item = LOS_DL_LIST_ENTRY((list)->pstNext, type, member) 示意蕴含双向链表成员的构造体的指针变量 item,条件测试语句&(item)->member != (list) 循环条件示意当双向链表遍历一圈到本身节点的时候,进行循环。循环更新语句 item = LOS_DL_LIST_ENTRY((item)->member.pstNext, type, member)) 中,应用 (item)->member.pstNext 遍历到下一个链表节点,而后依据这个节点获取对应的下一个构造体的指针变量item,直至遍历结束。

#define LOS_DL_LIST_FOR_EACH_ENTRY(item, list, type, member)             
    for (item = LOS_DL_LIST_ENTRY((list)->pstNext, type, member);        
         &(item)->member != (list);                                      
         item = LOS_DL_LIST_ENTRY((item)->member.pstNext, type, member)) 

1.5.2LOS_DL_LIST_FOR_EACH_ENTRY_SAFE(item, next, list, type, member)

该宏定义和 LOS_DL_LIST_FOR_EACH_ENTRY 惟一的区别就是多个个入参next, 这个参数示意遍历到的构造体的下一个构造体地址的指针变量。该宏用于平安删除,如果删除遍历到的item,不影响持续遍历。

源码如下:

#define LOS_DL_LIST_FOR_EACH_ENTRY_SAFE(item, next, list, type, member)               
    for (item = LOS_DL_LIST_ENTRY((list)->pstNext, type, member),                     
         next = LOS_DL_LIST_ENTRY((item)->member->pstNext, type, member);             
         &(item)->member != (list);                                                   
         item = next, next = LOS_DL_LIST_ENTRY((item)->member.pstNext, type, member)) 

1.5.3LOS_DL_LIST_FOR_EACH_ENTRY_HOOK(item, list, type, member, hook)

该宏定义和 LOS_DL_LIST_FOR_EACH_ENTRY 的区别就是多了个入参 hook 个钩子函数。在每次遍历循环中,调用该钩子函数做些用户定制的工作。

源码如下:

#define LOS_DL_LIST_FOR_EACH_ENTRY_HOOK(item, list, type, member, hook)  
    for (item = LOS_DL_LIST_ENTRY((list)->pstNext, type, member), hook;  
         &(item)->member != (list);                                      
         item = LOS_DL_LIST_ENTRY((item)->member.pstNext, type, member), hook)

2、Priority Queue 优先级队列

在任务调度模块,就绪队列是个重要的数据结构,就绪队列须要反对初始化,出入队列,从队列获取最高优先级工作等操作。LiteOS调度模块反对繁多就绪队列(Single Ready Queue)和多就绪队列(Multiple Ready Queue),咱们这里次要讲述一下繁多就绪队列。

优先级队列 Priority Queue 接口次要外部应用,用户业务开发时不波及,不对外提供接口。优先级队列其实就是个双向循环链表数组,提供更加不便的接口反对工作基于优先级进行调度。
优先级队列外围的代码都在 kernelbaseincludelos_priqueue_pri.h 头文件和 kernelbaseschedsched_sqlos_priqueue.c 实现文件中。

咱们来看看优先级队列反对的操作。

2.1 Priority Queue 优先级队列变量定义

LiteOS反对 32 个优先级,取值范畴 0 -31,优先级数值越小优先级越大。优先级队列在 kernelbaseschedsched_sqlos_priqueue.c 文件中定义的几个变量如下,
其中⑴示意优先级为 0 的位,⑵处示意优先级队列的双向链表数组,后文会初始化为数组的长度为 32,⑶示意优先级位图,标记哪些优先级就绪队列里有挂载的工作。

示意图如下:
优先级位图 g_priQueueBitmap 的 bit 位和优先级的关系是 bits=31-priority,g_priQueueList[priority]优先级数组内容为双向链表,挂载各个优先级的处于就绪状态的工作。

源码如下:

 #define OS_PRIORITY_QUEUE_NUM 32
⑴ #define PRIQUEUE_PRIOR0_BIT   0x80000000U
⑵ LITE_OS_SEC_BSS LOS_DL_LIST *g_priQueueList = NULL;
⑶ STATIC LITE_OS_SEC_BSS UINT32 g_priQueueBitmap; 

上面咱们来学习下优先级队列反对的那些操作。

2.2 Priority Queue 优先级队列接口

2.2.1 OsPriQueueInit(VOID)初始化

优先级队列初始化在零碎初始化的时候调用:main.c:main(void)k-->kernelinitlos_init.c:OsMain(VOID)-->kernelbaselos_task.c:OsTaskInit(VOID)-->OsPriQueueInit()

从上面的代码能够看出,⑴处申请长度为 32 的双向链表数值申请常驻内存,运行期间不会调用 Free() 接口开释。⑴处代码为数组的每一个双向链表元素都初始化为双向循环链表。

源码如下:

UINT32 OsPriQueueInit(VOID)
{
    UINT32 priority;
    /* 零碎常驻内存,运行期间不会 Free 开释 */
⑴  g_priQueueList = (LOS_DL_LIST *)LOS_MemAlloc(m_aucSysMem0, (OS_PRIORITY_QUEUE_NUM * sizeof(LOS_DL_LIST)));
    if (g_priQueueList == NULL) {return LOS_NOK;}
    for (priority = 0; priority < OS_PRIORITY_QUEUE_NUM; ++priority) {⑵      LOS_ListInit(&g_priQueueList[priority]);
    }
    return LOS_OK;
} 

2.2.2 OsPriQueueEnqueueHead()插入就绪队列头部

OsPriQueueEnqueueHead()从就绪队列的头部进行插入,插入得晚,但在等同优先级的工作中,会第一个调度。一起看下代码,⑴处先判断指定优先级 priority 的就绪队列是否为空,如果为空,则在⑵处更新优先级位图。⑶处把就绪状态的工作插入就绪队列的头部,以便优先调度。

源码如下:

VOID OsPriQueueEnqueueHead(LOS_DL_LIST *priqueueItem, UINT32 priority)
{LOS_ASSERT(priqueueItem->pstNext == NULL);
⑴  if (LOS_ListEmpty(&g_priQueueList[priority])) {⑵      g_priQueueBitmap |= PRIQUEUE_PRIOR0_BIT >> priority;}
⑶  LOS_ListHeadInsert(&g_priQueueList[priority], priqueueItem);
} 

2.2.3 OsPriQueueEnqueue()插入就绪队列尾部

OsPriQueueEnqueueHead() 的区别是,把就绪状态的工作插入就绪队列的尾部,等同优先级的工作中,后插入的后调度。

2.2.4 OsPriQueueDequeue()就绪队列中删除

在工作被删除、进入 suspend 状态,优先级调整等场景时,都须要调用接口 OsPriQueueEnqueue() 把工作从优先级队列中删除。

咱们来看下代码,⑴把工作从优先级就绪队列中删除。⑵获取删除的工作 TCB 信息,用来获取工作的优先级。刚从优先级队列中删除了一个工作,⑶处代码判断优先级队列是否为空,
如果为空,则须要执行⑷处代码,把优先级位图中对应的优先级 bit 地位为 0。

源码如下:

VOID OsPriQueueDequeue(LOS_DL_LIST *priqueueItem)
{
    LosTaskCB *runTask = NULL;
⑴  LOS_ListDelete(priqueueItem);
⑵  runTask = LOS_DL_LIST_ENTRY(priqueueItem, LosTaskCB, pendList);
⑶  if (LOS_ListEmpty(&g_priQueueList[runTask->priority])) {⑷      g_priQueueBitmap &= ~(PRIQUEUE_PRIOR0_BIT >> runTask->priority);
    }
} 

2.2.5 LOS_DL_LIST *OsPriQueueTop(VOID)获取就绪的优先级最高的链表节点

这个接口能够获取优先级就绪队列中优先级最高的链表节点。⑴处判断优先级位图 g_priQueueBitmap 是否为 0,如果为 0,阐明没有任何就绪状态的工作,返回 NULL。⑵处计算 g_priQueueBitmap 二进制时结尾的 0 的数目,这个数目对应于
工作的优先级 priority,而后⑶处从&g_priQueueList[priority] 优先级队列链表中获取第一个链表节点。

源码如下:

LOS_DL_LIST *OsPriQueueTop(VOID)
{
    UINT32 priority;
⑴  if (g_priQueueBitmap != 0) {⑵      priority = CLZ(g_priQueueBitmap);
⑶      return LOS_DL_LIST_FIRST(&g_priQueueList[priority]);
    }
    return NULL;
} 

2.2.6 UINT32 OsPriQueueSize(UINT32 priority)获取指定优先级的就绪工作的数量

这个接口能够获取指定优先级的就绪队列中工作的数量。⑴、⑶处代码示意,在 SMP 多核模式下,依据获取的以后 CPU 编号的 cpuId,判断工作是否属于以后 CPU 核,如果不属于,则不计数。⑵处代码应用for 循环遍历指定优先级就绪队列中的链表节点,对遍历到新节点则执行⑷处代码,对计数进行进行加 1 操作。

源码如下:

 UINT32 OsPriQueueSize(UINT32 priority)
    {
        UINT32 itemCnt = 0;
        LOS_DL_LIST *curNode = NULL;
    #ifdef LOSCFG_KERNEL_SMP
        LosTaskCB *task = NULL;
⑴      UINT32 cpuId = ArchCurrCpuid();
    #endif
        LOS_ASSERT(ArchIntLocked());
        LOS_ASSERT(LOS_SpinHeld(&g_taskSpin));
⑵      LOS_DL_LIST_FOR_EACH(curNode, &g_priQueueList[priority]) {
    #ifdef LOSCFG_KERNEL_SMP
            task = OS_TCB_FROM_PENDLIST(curNode);
⑶          if (!(task->cpuAffiMask & (1U << cpuId))) {continue;}
    #endif
⑷          ++itemCnt;
        }
        return itemCnt;
    } 

2.2.7 LosTaskCB *OsGetTopTask(VOID)获取就绪的优先级最高的工作

这个接口或者就绪工作队列中优先级最高的工作。一起看下代码,⑴、⑷处对 SMP 多核做非凡解决,如果是多核,只获取指定在以后 CPU 核运行的优先级最高的工作。⑵处获取 g_priQueueBitmap 优先级位图的值,赋值给 UINT32 bitmap;。不间接操作优先级位图的起因是什么呢?在SMP 多核时,在高优先级工作就绪队列里没有找到指定在以后 CPU 核运行的工作,须要执行⑹处的代码,清零长期优先级位图的 bit 位,去低一级的优先级就绪队列里去查找。只能改变长期优先级位图,不能扭转g_priQueueBitmap。⑶处代码对优先级最高的就绪队列进行遍历,如果遍历到则执行⑸处代码从优先级就绪队列里出队,函数返回对应的LosTaskCB *newTask

源码如下:

 {
        UINT32 priority;
        UINT32 bitmap;
        LosTaskCB *newTask = NULL;
    #ifdef LOSCFG_KERNEL_SMP
⑴      UINT32 cpuid = ArchCurrCpuid();
    #endif
⑵      bitmap = g_priQueueBitmap;
        while (bitmap) {priority = CLZ(bitmap);
⑶          LOS_DL_LIST_FOR_EACH_ENTRY(newTask, &g_priQueueList[priority], LosTaskCB, pendList) {
    #ifdef LOSCFG_KERNEL_SMP
⑷              if (newTask->cpuAffiMask & (1U << cpuid)) {
    #endif
⑸                  OsPriQueueDequeue(&newTask->pendList);
                    goto OUT;
    #ifdef LOSCFG_KERNEL_SMP
                }
    #endif
            }
⑹          bitmap &= ~(1U << (OS_PRIORITY_QUEUE_NUM - priority - 1));
        }
    OUT:
        return newTask;
    }

3、SortLinkList 排序链表

SortLinkListLiteOS 另外一个比拟重要的数据结构,它在 LOS_DL_LIST 双向链表构造体的根底上,减少了 RollNum 滚动数,用于波及工夫到期、超时的业务场景。在阻塞工作是否到期,定时器是否超时场景下,十分依赖 SortLinkList 排序链表这个数据结构。LiteOS排序链表反对繁多链表 LOSCFG_BASE_CORE_USE_SINGLE_LIST 和多链表 LOSCFG_BASE_CORE_USE_MULTI_LIST,能够通过LiteOSmenuconfig工具更改 Sortlink Option 选项来配置应用单链表还是多链表,咱们这里先讲述前者。

排序链表 SortLinkList 接口次要外部应用,用户业务开发时不波及,不对外提供接口。SortLinkList排序链表的代码都在 kernelbaseincludelos_sortlink_pri.h 头文件和 kernelbaselos_sortlink.c 实现文件中。

3.1 SortLinkList 排序链表构造体定义

kernelbaseincludelos_sortlink_pri.h 文件中定义了两个构造体,如下述源码所示。

SortLinkAttribute构造体定义排序链表的头结点 LOS_DL_LIST *sortLink,游标UINT16 cursorSortLinkList 构造体定义排序链表的业务节点,除了负责双向链接的成员变量 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 排序链表接口

在持续之前咱们先看下 kernelbaseincludelos_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() 排序链表初始化

在系统启动软件初始化,初始化工作、初始化定时器时,会别离初始化工作的排序链表和定时器的排序链表。

  • kernelbaselos_task.c : UINT32 OsTaskInit(VOID)函数

     `ret = OsSortLinkInit(&g_percpu[index].taskSortLink);` 
  • kernelbaselos_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),该函数在kernelbaselos_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 工夫的关系。函数在 kernelbaselos_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/Lite…。为了更容易找到 LiteOS 代码仓,倡议拜访 https://gitee.com/LiteOS/LiteOS,关注 Watch、点赞Star、并Fork 到本人账户下,如下图,谢谢。

本文分享自华为云社区《LiteOS 内核源码剖析系列一 盘点那些重要的数据结构》,原文作者:zhushy。

点击关注,第一工夫理解华为云陈腐技术~

正文完
 0