鸿蒙内核源码分析(双向链表篇).md 8.3 KB
Newer Older
1
[鸿蒙内核源码注释中文版 【 Gitee仓 ](https://gitee.com/weharmony/kernel_liteos_a_note)|[ CSDN仓 ](https://codechina.csdn.net/kuangyufei/kernel_liteos_a_note)|[ Github仓 ](https://github.com/kuangyufei/kernel_liteos_a_note)|[ Coding仓 】](https://weharmony.coding.net/public/harmony/kernel_liteos_a_note/git/files)精读内核源码,中文注解分析.深挖地基工程,构建底层网图.
2

3
[鸿蒙源码分析系列篇 【 CSDN ](https://blog.csdn.net/kuangyufei/article/details/108727970)[| OSCHINA ](https://my.oschina.net/u/3751245/blog/4626852)[| HarmonyOS 】](https://weharmony.github.io/)问答式导读, 生活式比喻, 图形化展示, 层层剥开内核神秘外衣.
4 5 6

---

7
## 谁是鸿蒙内核最重要的结构体? 
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105

答案一定是: LOS\_DL\_LIST(双向链表),它长这样.

```cpp
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;
```

结构体够简单了吧,只有前后两个指向自己的指针,但恰恰是因为太简单,所以才太不简单. 就像氢原子一样,宇宙中无处不在,占比最高,原因是因为它最简单,最稳定!

内核的各自模块都能看到双向链表的身影,下图是各处初始化双向链表的操作,因为太多了,只截取了部分:

![](https://img-blog.csdnimg.cn/20200917171547946.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2t1YW5neXVmZWk=,size_16,color_FFFFFF,t_70)

很多人问图怎么来的, source insight 4.0 是阅读大型C/C++工程的必备工具,要用4.0否则中文有乱码.

可以豪不夸张的说理解LOS\_DL\_LIST及相关函数是读懂鸿蒙内核的关键。前后指针(注者后续将比喻成一对左右触手)灵活的指挥着系统精准的运行,越是深入分析内核源码,越能感受到内核开发者对LOS\_DL\_LIST非凡的驾驭能力,笔者仿佛看到了无数双手前后相连,拉起了一个个双向循环链表,把指针的高效能运用到了极致,这也许就是编程的艺术吧!这么重要的结构体还是需详细讲解一下.

### 基本概念

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

### 功能接口

鸿蒙系统中的双向链表模块为用户提供下面几个接口。

![](https://img-blog.csdnimg.cn/img_convert/2991b499e4191cb7fdd733f10e13ae05.png)

请结合下面的代码和图去理解双向链表,不管花多少时间,一定要理解它的插入/删除动作, 否则后续内容将无从谈起. 

```cpp
//将指定节点初始化为双向链表节点
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 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_ListDelete(LOS_DL_LIST *node)
{
    node->pstNext->pstPrev = node->pstPrev;
    node->pstPrev->pstNext = node->pstNext;
    node->pstNext = NULL;
    node->pstPrev = NULL;
}
```

![](https://img-blog.csdnimg.cn/20210108142534112.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2t1YW5neXVmZWk=,size_16,color_FFFFFF,t_70)

### 具体用法

举例 ProcessCB(进程控制块)是描述一个进程的所有信息,其中用到了 7个双向链表,这简直比章鱼还牛逼,章鱼也才四双触手,但进程有7双(14只)触手.

```cpp
typedef struct ProcessCB {
    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 */ //兄弟进程链表, 56个民族是一家,来自同一个父进程.
    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 */ //哪个线程组是进程的主线程ID
    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
                                                                         priority hash table */	//进程的线程组调度优先级哈希表
    volatile UINT32      threadNumber; /**< Number of threads alive under this process */	//此进程下的活动线程数
    UINT32               threadCount;  /**< Total number of threads created under this process */	//在此进程下创建的线程总数
    LOS_DL_LIST          waitList;     /**< The process holds the waitLits to support wait/waitpid *///进程持有等待链表以支持wait/waitpid
} LosProcessCB;
```

看个简单点的 pendList表示这个进程中所有被阻塞的任务(task)都会挂到这个链表上管理. 任务阻塞的原因很多,可能是申请互斥锁失败,可能等待事件读消息队列,还可能开了一个定时任务等等.

再来看一个复杂点的 threadPriQueueList\[OS\_PRIORITY\_QUEUE_NUM\] ,这又是干嘛的?从名字可以看出来是线程的队列链表,在鸿蒙内核线程就是任务(task),任务分等了32个优先级,同级的任务放在同一个双向链表中, 32级就是32个双向链表,所以是个链表数组,每条链表中存放的是已就绪等待被调度的任务.

双向链表是内核最重要的结构体,精读内核的路上它会反复的映入你的眼帘,理解它是理解内存运作的关键所在!

### **喜欢就关注下吧,您的关注真的很重要**

![在这里插入图片描述](https://gitee.com/weharmony/kernel_liteos_a_note/raw/master/zzz/pic/other/wxcode.png)

作者邮箱:weharmony@126.com

---

106 107
[![WeHarmony/kernel_liteos_a_note](https://gitee.com/weharmony/kernel_liteos_a_note/widgets/widget_card.svg?colors=4183c4,ffffff,ffffff,e3e9ed,666666,9b9b9b)](https://gitee.com/weharmony/kernel_liteos_a_note)

108 109
[鸿蒙内核源码注释中文版 【 Gitee仓 ](https://gitee.com/weharmony/kernel_liteos_a_note)|[ CSDN仓 ](https://codechina.csdn.net/kuangyufei/kernel_liteos_a_note)|[ Github仓 ](https://github.com/kuangyufei/kernel_liteos_a_note)|[ Coding仓 】](https://weharmony.coding.net/public/harmony/kernel_liteos_a_note/git/files)精读内核源码,中文详细注解.深挖地基工程,构建底层网图.

110
[鸿蒙源码分析系列篇 【 CSDN ](https://blog.csdn.net/kuangyufei/article/details/108727970)[| OSCHINA ](https://my.oschina.net/u/3751245/blog/4626852)[| HarmonyOS 】](https://weharmony.github.io/)问答式导读, 生活式比喻, 图形化展示, 层层剥开内核神秘外衣.