誰(shuí)是鴻蒙內(nèi)核最重要的結(jié)構(gòu)體?

答案一定是:LOS_DL_LIST(雙向鏈表),它長(zhǎng)這樣.

typedef struct LOS_DL_LIST {//雙向鏈表，內(nèi)核最重要結(jié)構(gòu)體
    struct LOS_DL_LIST *pstPrev; /**< Current node's pointer to the previous node *///前驅(qū)節(jié)點(diǎn)(左手)
    struct LOS_DL_LIST *pstNext; /**< Current node's pointer to the next node *///后繼節(jié)點(diǎn)(右手)
} LOS_DL_LIST;

結(jié)構(gòu)體夠簡(jiǎn)單了吧,只有前后兩個(gè)指向自己的指針,但恰恰是因?yàn)樘?jiǎn)單,所以才太不簡(jiǎn)單. 就像氫原子一樣,宇宙中無(wú)處不在,占比最高,原因是因?yàn)樗詈?jiǎn)單,最穩(wěn)定!

內(nèi)核的各自模塊都能看到雙向鏈表的身影,下圖是各處初始化雙向鏈表的操作,因?yàn)樘嗔?只截取了部分:

很多人問(wèn)圖怎么來(lái)的,source insight 4.0是閱讀大型C/C++工程的必備工具,要用4.0否則中文有亂碼.

可以豪不夸張的說(shuō)理解LOS_DL_LIST及相關(guān)函數(shù)是讀懂鴻蒙內(nèi)核的關(guān)鍵。前后指針(注者后續(xù)將比喻成一對(duì)左右觸手)靈活的指揮著系統(tǒng)精準(zhǔn)的運(yùn)行，越是深入分析內(nèi)核源碼，越能感受到內(nèi)核開(kāi)發(fā)者對(duì)LOS_DL_LIST非凡的駕馭能力，筆者仿佛看到了無(wú)數(shù)雙手前后相連，拉起了一個(gè)個(gè)雙向循環(huán)鏈表，把指針的高效能運(yùn)用到了極致，這也許就是編程的藝術(shù)吧！這么重要的結(jié)構(gòu)體還是需詳細(xì)講解一下.

基本概念

雙向鏈表是指含有往前和往后兩個(gè)方向的鏈表，即每個(gè)結(jié)點(diǎn)中除存放下一個(gè)節(jié)點(diǎn)指針外，還增加一個(gè)指向其前一個(gè)節(jié)點(diǎn)的指針。其頭指針head是唯一確定的。從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開(kāi)始，都可以很方便地訪問(wèn)它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)，這種數(shù)據(jù)結(jié)構(gòu)形式使得雙向鏈表在查找時(shí)更加方便，特別是大量數(shù)據(jù)的遍歷。由于雙向鏈表具有對(duì)稱性，能方便地完成各種插入、刪除等操作，但需要注意前后方向的操作。

有好幾個(gè)同學(xué)問(wèn)數(shù)據(jù)在哪? 確實(shí)LOS_DL_LIST這個(gè)結(jié)構(gòu)看起來(lái)怪怪的，它竟沒(méi)有數(shù)據(jù)域！所以看到這個(gè)結(jié)構(gòu)的人第一反應(yīng)就是我們?cè)趺丛L問(wèn)數(shù)據(jù)？其實(shí)LOS_DL_LIST不是拿來(lái)單獨(dú)用的，它是寄生在內(nèi)容結(jié)構(gòu)體上的,誰(shuí)用它誰(shuí)就是它的數(shù)據(jù).看圖就明白了.

功能接口

鴻蒙系統(tǒng)中的雙向鏈表模塊為用戶提供下面幾個(gè)接口。

請(qǐng)結(jié)合下面的代碼和圖去理解雙向鏈表,不管花多少時(shí)間,一定要理解它的插入/刪除動(dòng)作,否則后續(xù)內(nèi)容將無(wú)從談起.

//將指定節(jié)點(diǎn)初始化為雙向鏈表節(jié)點(diǎn)
LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListInit(LOS_DL_LIST *list)
{
    list->pstNext = list;
    list->pstPrev = list;
}

//將指定節(jié)點(diǎn)掛到雙向鏈表頭部
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;
}
//將指定節(jié)點(diǎn)從鏈表中刪除,自己把自己摘掉
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;
}

強(qiáng)大的宏

除了內(nèi)聯(lián)函數(shù),對(duì)雙向遍歷的初始化,定位,遍歷 等等操作提供了更強(qiáng)大的宏支持.使內(nèi)核以極其簡(jiǎn)潔高效的代碼實(shí)現(xiàn)復(fù)雜邏輯的處理.

//定義一個(gè)節(jié)點(diǎn)并初始化為雙向鏈表節(jié)點(diǎn)
#define LOS_DL_LIST_HEAD(list) LOS_DL_LIST list = { &(list), &(list) }

//獲取指定結(jié)構(gòu)體內(nèi)的成員相對(duì)于結(jié)構(gòu)體起始地址的偏移量
#define LOS_OFF_SET_OF(type, member) ((UINTPTR)&((type *)0)->member)

//獲取包含鏈表的結(jié)構(gòu)體地址，接口的第一個(gè)入?yún)⒈硎镜氖擎湵碇械哪硞€(gè)節(jié)點(diǎn)，第二個(gè)入?yún)⑹且@取的結(jié)構(gòu)體名稱，第三個(gè)入?yún)⑹擎湵碓谠摻Y(jié)構(gòu)體中的名稱
#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)

//遍歷指定雙向鏈表，獲取包含該鏈表節(jié)點(diǎn)的結(jié)構(gòu)體地址，并存儲(chǔ)包含當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)的結(jié)構(gòu)體地址
#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))

//遍歷指定雙向鏈表，獲取包含該鏈表節(jié)點(diǎn)的結(jié)構(gòu)體地址
#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))

例如在調(diào)度算法中獲取當(dāng)前最高優(yōu)先級(jí)的任務(wù)時(shí),就需要遍歷整個(gè)進(jìn)程和進(jìn)程任務(wù)的所有就緒列表.LOS_DL_LIST_FOR_EACH_ENTRY高效的解決了層層循環(huán)的問(wèn)題,讓代碼簡(jiǎn)潔易懂.

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;
}

結(jié)構(gòu)體的最愛(ài)

LOS_DL_LIST是復(fù)雜結(jié)構(gòu)體的最愛(ài),以下舉例ProcessCB(進(jìn)程控制塊)是描述一個(gè)進(jìn)程的所有信息,其中用到了 8個(gè)雙向鏈表,這簡(jiǎn)直比章魚還牛逼,章魚也才四雙觸手,但進(jìn)程有8雙(16只)觸手.

typedef struct ProcessCB {
    //...此處省略其他變量
    LOS_DL_LIST          pendList;                     /**< Block list to which the process belongs */ //進(jìn)程所屬的阻塞列表,如果因拿鎖失敗,就由此節(jié)點(diǎn)掛到等鎖鏈表上
    LOS_DL_LIST          childrenList;                 /**< my children process list */	//孩子進(jìn)程都掛到這里,形成雙循環(huán)鏈表
    LOS_DL_LIST          exitChildList;                /**< my exit children process list */	//那些要退出孩子進(jìn)程掛到這里，白發(fā)人送黑發(fā)人。
    LOS_DL_LIST          siblingList;                  /**< linkage in my parent's children list */ //兄弟進(jìn)程鏈表, 56個(gè)民族是一家,來(lái)自同一個(gè)父進(jìn)程.
    LOS_DL_LIST          subordinateGroupList;         /**< linkage in my group list */ //進(jìn)程是組長(zhǎng)時(shí),有哪些組員進(jìn)程
    LOS_DL_LIST          threadSiblingList;            /**< List of threads under this process *///進(jìn)程的線程(任務(wù))列表
    LOS_DL_LIST          threadPriQueueList[OS_PRIORITY_QUEUE_NUM]; /**< The process's thread group schedules thepriority hash table */	//進(jìn)程的線程組調(diào)度優(yōu)先級(jí)哈希表
    LOS_DL_LIST          waitList;     /**< The process holds the waitLits to support wait/waitpid *///進(jìn)程持有等待鏈表以支持wait/waitpid
} LosProcessCB;

解讀

pendList個(gè)人認(rèn)為它是鴻蒙內(nèi)核功能最多的一個(gè)鏈表,它遠(yuǎn)不止字面意思阻塞鏈表這么簡(jiǎn)單,只有深入解讀源碼后才能體會(huì)它真的是太會(huì)來(lái)事了,一般把它理解為阻塞鏈表就行.上面掛的是處于阻塞狀態(tài)的進(jìn)程.

childrenList孩子鏈表,所有由它fork出來(lái)的進(jìn)程都掛到這個(gè)鏈表上.上面的孩子進(jìn)程在死亡前會(huì)將自己從上面摘出去,轉(zhuǎn)而掛到exitChildList鏈表上.

exitChildList退出孩子鏈表,進(jìn)入死亡程序的進(jìn)程要掛到這個(gè)鏈表上,一個(gè)進(jìn)程的死亡是件挺麻煩的事,進(jìn)程池的數(shù)量有限,需要及時(shí)回收進(jìn)程資源,但家族管理關(guān)系復(fù)雜,要去很多地方消除痕跡.尤其還有其他進(jìn)程在看你笑話,等你死亡(wait/waitpid)了通知它們一聲.

siblingList兄弟鏈表,和你同一個(gè)父親的進(jìn)程都掛到了這個(gè)鏈表上.

subordinateGroupList朋友圈鏈表,里面是因?yàn)榕d趣愛(ài)好(進(jìn)程組)而掛在一起的進(jìn)程,它們可以不是一個(gè)父親,不是一個(gè)祖父,但一定是同一個(gè)老祖宗(用戶態(tài)和內(nèi)核態(tài)根進(jìn)程).

threadSiblingList線程鏈表,上面掛的是進(jìn)程ID都是這個(gè)進(jìn)程的線程(任務(wù)),進(jìn)程和線程的關(guān)系是1:N的關(guān)系,一個(gè)線程只能屬于一個(gè)進(jìn)程.這里要注意任務(wù)在其生命周期中是不能改所屬進(jìn)程的.

threadPriQueueList線程的調(diào)度隊(duì)列數(shù)組,一共32個(gè),任務(wù)和進(jìn)程一樣有32個(gè)優(yōu)先級(jí),調(diào)度算法的過(guò)程是先找到優(yōu)先級(jí)最高的進(jìn)程,在從該進(jìn)程的任務(wù)隊(duì)列里去最高的優(yōu)先級(jí)任務(wù)運(yùn)行.

waitList是等待子進(jìn)程消亡的任務(wù)鏈表,注意上面掛的是任務(wù).任務(wù)是通過(guò)系統(tǒng)調(diào)用

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

雙向鏈表是內(nèi)核最重要的結(jié)構(gòu)體,精讀內(nèi)核的路上它會(huì)反復(fù)的映入你的眼簾,理解它是理解內(nèi)核運(yùn)作的關(guān)鍵所在!

編輯：hfy