乐趣区

关于c:鸿蒙内核源码分析双向链表篇-谁是内核最重要结构体-开篇致敬鸿蒙内核开发者-v111

jiezi

子曰：“见贤思齐焉，见不贤而内自省也。”《论语》：里仁篇

百篇博客系列篇. 本篇为:

v01.xx 鸿蒙内核源码剖析(双向链表篇) | 谁是内核最重要构造体

根底工具相干篇为:

  • v01.xx 鸿蒙内核源码剖析(双向链表) | 谁是内核最重要构造体
  • v19.xx 鸿蒙内核源码剖析(位图治理) | 谁能一分钱分两半花
  • v20.xx 鸿蒙内核源码剖析(用栈形式) | 程序运行场地由谁提供
  • v31.xx 鸿蒙内核源码剖析(定时器) | 哪个工作的优先级最高
  • v34.xx 鸿蒙内核源码剖析(原子操作) | 谁在为原子操作保驾护航
  • v35.xx 鸿蒙内核源码剖析(工夫治理) | 谁是内核根本工夫单位

谁是鸿蒙内核最重要的构造体?

答案肯定是: LOS_DL_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;

构造体够简略了吧，只有前后两个指向本人的指针，但恰好是因为太简略，所以才太不简略. 就像氢原子一样，宇宙中无处不在，占比最高，起因是因为它最简略，最稳固!

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

很多人问图怎么来的，source insight 4.0 是浏览大型 C/C++ 工程的必备工具，要用 4.0 否则中文有乱码. [下载 source insight 4.0 破解版]

能够豪不夸大的说了解 LOS_DL_LIST 及相干函数是读懂鸿蒙内核的要害。前后指针 (注者后续将比喻成一对左右触手) 灵便的指挥着零碎精准的运行，越是深入分析内核源码，越能感触到内核开发者对 LOS_DL_LIST 不凡的驾驭能力，笔者好像看到了有数双手前后相连，拉起了一个个双向循环链表，把指针的高效能使用到了极致，这兴许就是编程的艺术吧！这么重要的构造体还是需具体解说一下.

基本概念

双向链表是指含有往前和往后两个方向的链表，即每个结点中除寄存下一个节点指针外，还减少一个指向其前一个节点的指针。其头指针 head 是惟一确定的。从双向链表中的任意一个结点开始，都能够很不便地拜访它的前驱结点和后继结点，这种数据结构模式使得双向链表在查找时更加不便，特地是大量数据的遍历。因为双向链表具备对称性，能不便地实现各种插入、删除等操作，但须要留神前后方向的操作。

有好几个同学问数据在哪? 的确 LOS_DL_LIST 这个构造看起来怪怪的，它竟没有数据域！所以看到这个构造的人第一反馈就是咱们怎么拜访数据？其实 LOS_DL_LIST 不是拿来独自用的，它是寄生在内容构造体上的，谁用它谁就是它的数据. 看图就明确了.

性能接口

鸿蒙零碎中的双向链表模块为用户提供上面几个接口。

性能分类            接口名                        形容
初始化链表          LOS_ListInit                对链表进行初始化
减少节点            LOSListAdd                  将新节点增加到链表中
在链表尾部插入节点   LOS_ListTailInsert          将节点插入到双向链表尾部
在链表头部插入节点   LOS_ListHeadInsert          将节点插入到双向链表头部
删除节点            LOS_ListDelete              将指定的节点从链表中删除
判断双向链表是否为空 LOS_ListEmpty               判断链表是否为空
删除节点并初始化链表 LOS_ListDelInit             将指定的节点从链表中删除应用该节点初始化链表
在链表尾部插入链表   LOS_ListTailInsertList    将链表插入到双向链表尾部
在链表头部插入链表   LOS_ListHeadInsertList    将链表插入到双向链表头部

请联合上面的代码和图去了解双向链表，不论花多少工夫，肯定要了解它的插入 / 删除动作，否则后续内容将无从谈起.

// 将指定节点初始化为双向链表节点
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;
}
// 将指定节点从链表中删除，并应用该节点初始化链表
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);
}

此处仅列出 LOS_ListDelInit图

弱小的宏

除了内联函数，对双向链表的初始化，偏移定位，遍历 等等操作提供了更弱小的宏反对. 使内核以极其简洁高效的代码实现简单逻辑的解决.

// 定义一个节点并初始化为双向链表节点
#define LOS_DL_LIST_HEAD(list) LOS_DL_LIST list = {&(list)，&(list) }

// 获取指定构造体内的成员绝对于构造体起始地址的偏移量
#define LOS_OFF_SET_OF(type，member) ((UINTPTR)&((type *)0)->member)

// 获取蕴含链表的构造体地址，接口的第一个入参示意的是链表中的某个节点，第二个入参是要获取的构造体名称，第三个入参是链表在该构造体中的名称
#define LOS_DL_LIST_ENTRY(item，type，member) \
    ((type *)(VOID *)((CHAR *)(item) - LOS_OFF_SET_OF(type，member)))

// 遍历双向链表
#define LOS_DL_LIST_FOR_EACH(item，list) \
    for (item = (list)->pstNext;         \
         (item) != (list);               \
         item = (item)->pstNext)

// 遍历指定双向链表，获取蕴含该链表节点的构造体地址，并存储蕴含以后节点的后继节点的构造体地址
#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))

// 遍历指定双向链表，获取蕴含该链表节点的构造体地址
#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))

LOS_OFF_SET_OF 和 LOS_DL_LIST_ENTRY

这里要重点说下 LOS_OFF_SET_OF和 LOS_DL_LIST_ENTRY 两个宏，集体认为它们是链表操作中最要害，最重要的宏. 在读内核源码的过程会发现 LOS_DL_LIST_ENTRY 高频的呈现，它们解决了通过构造体的任意一个成员变量来找到构造体的入口地址.
这个意义重大，因为在运行过程中，往往只能提供成员变量的地址，那它是如何做到通过集体找到组织的呢?

  • LOS_OFF_SET_OF找到成员变量在构造体中的绝对偏移地位. 在系列篇 用栈形式篇中 已说过 鸿蒙采纳的是递加满栈的形式. 以ProcessCB 构造体举例

    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 个民族是一家，来自同一个父过程.
    LOS_DL_LIST          subordinateGroupList;         /**< linkage in my group list */ // 过程是组长时，有哪些组员过程
    LOS_DL_LIST          threadSiblingList;            /**< List of threads under this process */// 过程的线程 (工作) 列表
    LOS_DL_LIST          threadPriQueueList[OS_PRIORITY_QUEUE_NUM]; /**< The process's thread group schedules thepriority hash table */    // 过程的线程组调度优先级哈希表
    LOS_DL_LIST          waitList;     /**< The process holds the waitLits to support wait/waitpid */// 过程持有期待链表以反对 wait/waitpid
} LosProcessCB;

    waitList因为在构造体的前面，所以它内存地址会比在后面的 pendList 高，有了程序方向就很容易失去 ProcessCB 的第一个变量的地址.LOS_OFF_SET_OF就是干这个的，含意就是绝对第一个变量地址，你 waitList 偏移了多少.

  • 如此，当里面只提供 waitList 的地址再减去偏移地址 就能够失去 ProcessCB 的起始地址.

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

    当然如果提供 pendList 或exitChildList的地址情理一样.LOS_DL_LIST_ENTRY实现了通过任意成员变量来获取 ProcessCB 的起始地址.

    OsGetTopTask

    有了以上对链表操作的宏，能够使得代码变得简洁易懂，例如在调度算法中获取以后最高优先级的工作时，就须要遍历整个过程和其工作的就绪列表.LOS_DL_LIST_FOR_EACH_ENTRY高效的解决了层层循环的问题.

    LITE_OS_SEC_TEXT_MINOR LosTaskCB *OsGetTopTask(VOID)
{
  UINT32 priority，processPriority;
  UINT32 bitmap;
  UINT32 processBitmap;
  LosTaskCB *newTask = NULL;
#if (LOSCFG_KERNEL_SMP == YES)
  UINT32 cpuid = ArchCurrCpuid();
#endif
  LosProcessCB *processCB = NULL;
  processBitmap = g_priQueueBitmap;
  while (processBitmap) {processPriority = CLZ(processBitmap);
      LOS_DL_LIST_FOR_EACH_ENTRY(processCB，&g_priQueueList[processPriority]，LosProcessCB，pendList) {
          bitmap = processCB->threadScheduleMap;
          while (bitmap) {priority = CLZ(bitmap);
              LOS_DL_LIST_FOR_EACH_ENTRY(newTask，&processCB->threadPriQueueList[priority]，LosTaskCB，pendList) {#if (LOSCFG_KERNEL_SMP == YES)
                  if (newTask->cpuAffiMask & (1U << cpuid)) {
#endif
                      newTask->taskStatus &= ~OS_TASK_STATUS_READY;
                      OsPriQueueDequeue(processCB->threadPriQueueList，&processCB->threadScheduleMap，&newTask->pendList);
                      OsDequeEmptySchedMap(processCB);
                      goto OUT;
#if (LOSCFG_KERNEL_SMP == YES)
                  }
#endif
              }
              bitmap &= ~(1U << (OS_PRIORITY_QUEUE_NUM - priority - 1));
          }
      }
      processBitmap &= ~(1U << (OS_PRIORITY_QUEUE_NUM - processPriority - 1));
  }

OUT:
  return newTask;
}

    构造体的最爱

    LOS_DL_LIST是简单构造体的最爱，再以 ProcessCB(过程管制块)举例，它是形容一个过程的所有信息，其中用到了 8 个双向链表，这几乎比章鱼还牛逼，章鱼也才四双触手，但过程有 8 双 (16 只) 触手.

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 个民族是一家，来自同一个父过程.
    LOS_DL_LIST          subordinateGroupList;         /**< linkage in my group list */ // 过程是组长时，有哪些组员过程
    LOS_DL_LIST          threadSiblingList;            /**< List of threads under this process */// 过程的线程 (工作) 列表
    LOS_DL_LIST          threadPriQueueList[OS_PRIORITY_QUEUE_NUM]; /**< The process's thread group schedules thepriority hash table */    // 过程的线程组调度优先级哈希表
    LOS_DL_LIST          waitList;     /**< The process holds the waitLits to support wait/waitpid */// 过程持有期待链表以反对 wait/waitpid
} LosProcessCB;

解读

  • pendList 集体认为它是鸿蒙内核性能最多的一个链表，它远不止字面意思阻塞链表这么简略，只有深刻解读源码后能力领会它真的是太会来事了，个别把它了解为阻塞链表就行. 下面挂的是处于阻塞状态的过程.
  • childrenList孩子链表，所有由它 fork 进去的过程都挂到这个链表上. 下面的孩子过程在死亡前会将本人从下面摘出去，转而挂到 exitChildList 链表上.
  • exitChildList退出孩子链表，进入死亡程序的过程要挂到这个链表上，一个过程的死亡是件挺麻烦的事，过程池的数量无限，须要及时回收过程资源，但家族治理关系简单，要去很多中央打消痕迹. 尤其还有其余过程在看你笑话，等你死亡 (wait/waitpid) 了告诉它们一声.
  • siblingList兄弟链表，和你同一个父亲的过程都挂到了这个链表上.
  • subordinateGroupList 朋友圈链表，外面是因为兴趣爱好 (过程组) 而挂在一起的过程，它们能够不是一个父亲，不是一个祖父，但肯定是同一个老祖宗(用户态和内核态根过程).
  • threadSiblingList线程链表，下面挂的是过程 ID 都是这个过程的线程(工作)，过程和线程的关系是 1:N 的关系，一个线程只能属于一个过程. 这里要留神工作在其生命周期中是不能改所属过程的.
  • threadPriQueueList线程的调度队列数组，一共 32 个，工作和过程一样有 32 个优先级，调度算法的过程是先找到优先级最高的过程，在从该过程的工作队列里去最高的优先级工作运行.

  • waitList 是期待子过程沦亡的工作链表，留神下面挂的是工作. 工作是通过零碎调用

      pid_t wait(int *status);
  pid_t waitpid(pid_t pid，int *status，int options);

    将工作挂到 waitList 上. 鸿蒙 waitpid 零碎调用为SysWait，具体看过程回收篇.

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

百万汉字注解. 精读内核源码

百篇博客剖析. 深挖内核地基

给鸿蒙内核源码加正文过程中，整顿出以下文章。内容立足源码，常以生存场景打比方尽可能多的将内核知识点置入某种场景，具备画面感，容易了解记忆。说他人能听得懂的话很重要! 百篇博客绝不是百度教条式的在说一堆诘屈聱牙的概念，那没什么意思。更心愿让内核变得栩栩如生，倍感亲切. 的确有难度，自不量力，但曾经登程，回头已是不可能的了。:P
与代码有 bug 需一直 debug 一样，文章和注解内容会存在不少错漏之处，请多包涵，但会重复修改，继续更新，.xx 代表批改的次数，精雕细琢，长篇累牍，力求打造精品内容。

编译构建 根底工具 加载运行 过程治理
编译环境
编译过程
环境脚本
构建工具
gn 利用
忍者 ninja		 双向链表
位图治理
用栈形式
定时器
原子操作
工夫治理		 ELF 格局
ELF 解析
动态链接
重定位
过程映像		 过程治理
过程概念
Fork
非凡过程
过程回收
信号生产
信号生产
Shell 编辑
Shell 解析
过程通信 内存治理 前因后果 工作治理
自旋锁
互斥锁
过程通信
信号量
事件管制
音讯队列		 内存调配
内存治理
内存汇编
内存映射
内存规定
物理内存		 总目录
调度故事
内存主奴
源码正文
源码构造
动态站点		 时钟工作
任务调度
工作治理
调度队列
调度机制
线程概念
并发并行
零碎调用
工作切换
文件系统 硬件架构
文件概念
文件系统
索引节点
挂载目录
根文件系统
字符设施
VFS
文件句柄
管道文件		 汇编根底
汇编传参
工作模式
寄存器
异样接管
汇编汇总
中断切换
中断概念
中断治理

鸿蒙钻研站 | 每天死磕一点点，原创不易，欢送转载，但请注明出处。

退出移动版