[文章]鸿蒙内核源码分析(双循环链表篇) ：内核最重要结构体

图解鸿蒙内核, 从 HarmonyOS 架构层视角整理成文, 并首创用生活场景讲故事的方式试图去解构内核，一窥究竟。

为何鸿蒙内核源码分析系列开篇就说 LOS_DL_LIST ？因为它在鸿蒙 LOS 内核中无处不在，在整个内核占了极大的比重，豪不夸张的说理解LOS_DL_LIST及相关函数是读懂鸿蒙内核的关键。前后指针就像人的两只左右手一样灵活的指挥着系统精准的运行，越是深入分析内核源码，越能感受到内核开发者对LOS_DL_LIST非凡的驾驭能力，笔者仿佛看到了无数双手前后相连，拉起了一个个双向循环链表，把指针的高效能运用到了极致，这也许就是编程的艺术吧！

致敬鸿蒙内核开发者贡献了如此优秀的源码，鸿蒙内核源码可作为大学C语言，操作系统，数据结构，汇编语言四门课的教学项目。
/**
* @ingroup los_list
* Structure of a node in a doubly linked list.
*/
typedef struct LOS_DL_LIST {
struct LOS_DL_LIST *pstPrev; /**< Current node's pointer to the previous node */
struct LOS_DL_LIST *pstNext; /**< Current node's pointer to the next node */
} LOS_DL_LIST;

LITE_OS_SEC_ALW_INLINE STAtiC INLINE VOID LOS_ListInit(LOS_DL_LIST *list)
{
list->pstNext = list;
list->pstPrev = list;
}
结构体很简单,就前后两个指向自己的指针,因简单才经典,因太简单才太不简单. 真的是无处不在吗？答：是真的，看看这些使用它的源码吧，无处不在。

基本概念
双向链表是指含有往前和往后两个方向的链表，即每个结点中除存放下一个节点指针外，还增加一个指向其前一个节点的指针。其头指针head是唯一确定的。从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点，这种数据结构形式使得双向链表在查找时更加方便，特别是大量数据的遍历。由于双向链表具有对称性，能方便地完成各种插入、删除等操作，但需要注意前后方向的操作。

功能接口
Huawei LiteOS系统中的双向链表模块为用户提供下面几个接口。

鸿蒙使用了双向循环链表来实现结构体数据结构之间的关联，支持单个节点的头尾插入，更精妙的是链表中支持插入另一个链表，将两个循环链表合成一个大循环链表，实现极为巧妙和简单。详见代码：
//双向链表初始化
LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListInit(LOS_DL_LIST *list)
{
list->pstNext = list; // 前后指针都指向自己
list->pstPrev = list;
}

//链表判空，检查前后指针是否指向自己
LITE_OS_SEC_ALW_INLINE STATIC INLINE BOOL LOS_ListEmpty(LOS_DL_LIST *list)
{
return (BOOL)(list->pstNext == list);
}

//从链表中删除节点
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;
}

//指针互换，具体向双向循环链表中插入节点
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;
}

// 两个循环链表合成一个大循环列表
LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListAddList(LOS_DL_LIST *oldList, LOS_DL_LIST *newList)
{
// 先用临时指针记录头尾位置
LOS_DL_LIST *oldListHead = oldList->pstNext;
LOS_DL_LIST *oldListTail = oldList;
LOS_DL_LIST *newListHead = newList;
LOS_DL_LIST *newListTail = newList->pstPrev;
// 前后指针完成切换
oldListTail->pstNext = newListHead;
newListHead->pstPrev = oldListTail;
oldListHead->pstPrev = newListTail;
newListTail->pstNext = oldListHead;
}
// 这里与其说插入不如说合并，同样支持从头或尾部合并
LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListTailInsertList(LOS_DL_LIST *oldList, LOS_DL_LIST *newList)
{
LOS_ListAddList(oldList->pstPrev, newList);
}
LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListHeadInsertList(LOS_DL_LIST *oldList, LOS_DL_LIST *newList)
{
LOS_ListAddList(oldList, newList);
}
大家在阅读鸿蒙内核源码要时刻带着 LOS_DL_LIST 去理解结构体之间的关联，构想运行时的场景是怎样的，就能体会到内核代码之精妙。

具体的使用场景
看下它其中的一个使用场景吧，体验设计者的奇妙用心，上代码。
typedef struct ProcessCB {
CHAR processName[OS_PCB_NAME_LEN]; /**< Process name */
UINT32 processID; /**< process ID = leader thread ID */
UINT16 processStatus; /**< [15:4] process Status; [3:0] The number of threads currently
running in the process */
LOS_DL_LIST pendList; /**< Block list to which the process belongs */
LOS_DL_LIST childrenList; /**< my children process list */
LOS_DL_LIST exitChildList; /**< my exit children process list */
LOS_DL_LIST siblingList; /**< linkage in my parent's children list */
ProcessGroup *group; /**< Process group to which a process belongs */
LOS_DL_LIST subordinateGroupList; /**< linkage in my group list */
UINT32 threadGroupID; /**< Which thread group , is the main thread ID of the process */
UINT32 threadScheduleMap; /**< The scheduling bitmap table for the thread group of the
process */
LOS_DL_LIST threadSiblingList; /**< List of threads under this process */
LOS_DL_LIST threadPriQueueList[OS_PRIORITY_QUEUE_NUM]; /**< The process's thread group schedules the
LOS_DL_LIST waitList; /**< The process holds the waitLits to support
} LosProcessCB;
这是LosProcessCB(进程控制块)，因为结构体很复杂，省去了其他定义，留下LOS_DL_LIST 相关的，LosProcessCB包含了 七个双向循环链表，这些链表承载的是一个进程在期生命周期内的运行的过程逻辑，与其他模块的关系逻辑等等，是的，必须要有如此复杂的又简洁的数据结构才能将进程的实现复杂度降到最低。内核源码就像那个每次考试都要考100分的孩子一样, 不管从宏观架构层面还是微观代码层面都要优秀到极致才能让用户进程安全而稳定的运行。

再看调度队列涉及的代码这是 进程/任务 出队入队的操作，背后都是LOS_DL_LIST的增删过程，这些宏在内核中大规模的使用, 请用心体会这些宏。
#define OS_PROCESS_PRI_QUEUE_SIZE(processCB) OsPriQueueProcessSize(g_priQueueList, (processCB)->priority)

#define OS_TASK_PRI_QUEUE_ENQUEUE(processCB, taskCB)
OsPriQueueEnqueue((processCB)->threadPriQueueList, &((processCB)->threadScheduleMap),
&((taskCB)->pendList), (taskCB)->priority)
#define OS_TASK_PRI_QUEUE_ENQUEUE_HEAD(processCB, taskCB)
OsPriQueueEnqueueHead((processCB)->threadPriQueueList, &((processCB)->threadScheduleMap),
&((taskCB)->pendList), (taskCB)->priority)

#define OS_TASK_PRI_QUEUE_DEQUEUE(processCB, taskCB)
OsPriQueueDequeue((processCB)->threadPriQueueList, &((processCB)->threadScheduleMap), &((taskCB)->pendList))


#define OS_TASK_SCHED_QUEUE_ENQUEUE(taskCB, status) OsTaskSchedQueueEnqueue(taskCB, status)
#define OS_TASK_SCHED_QUEUE_DEQUEUE(taskCB, status) OsTaskSchedQueueDequeue(taskCB, status)

#define OS_PROCESS_PRI_QUEUE_ENQUEUE(processCB)
OsPriQueueEnqueue(g_priQueueList, &g_priQueueBitmap, &((processCB)->pendList), (processCB)->priority)
#define OS_PROCESS_PRI_QUEUE_ENQUEUE_HEAD(processCB)
OsPriQueueEnqueueHead(g_priQueueList, &g_priQueueBitmap, &((processCB)->pendList), (processCB)->priority)
#define OS_PROCESS_PRI_QUEUE_DEQUEUE(processCB) OsPriQueueProcessDequeue(&((processCB)->pendList))

#define OS_TASK_PRI_QUEUE_SIZE(processCB, taskCB) OsPriQueueSize((processCB)->threadPriQueueList, (taskCB)->priority)
#define OS_TASK_GET_NEW(processCB) LOS_DL_LIST_ENTRY(OsPriQueueTop((processCB)->threadPriQueueList,
&((processCB)->threadScheduleMap)),
LosTaskCB, pendList)
内联函数 inline鸿蒙内核大量的使用了内联函数，源码中只有los_list.h，木有.c 文件！这些调用最最频繁的内联函数，免去了像普通函数要出栈入栈的时间和空间，效率极高。
/* Define OS code data sections */
/* The indicator function is inline */
#ifndef LITE_OS_SEC_ALW_INLINE
#define LITE_OS_SEC_ALW_INLINE /* __attribute__((always_inline)) */
#endif

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;
}
LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListTailInsert(LOS_DL_LIST *list, LOS_DL_LIST *node)
{
LOS_ListAdd(list->pstPrev, node);
}
LOS_DL_LIST让内核结构变得简单，高效，是最重要的结构体。