鴻蒙內(nèi)核源碼分析(雙向鏈表篇) | 最重要結(jié)構(gòu)體

作者：weharmony 2021-01-22 09:47:22

文章由鴻蒙社區(qū)產(chǎn)出，想要了解更多內(nèi)容請(qǐng)前往：51CTO和華為官方戰(zhàn)略合作共建的鴻蒙技術(shù)社區(qū)https://harmonyos.51cto.com/#zz

https://harmonyos.51cto.com/#zz

鴻蒙內(nèi)核源碼注釋中文版 < Gitee倉(cāng) | CSDN倉(cāng) | Github倉(cāng) | Coding倉(cāng) >精讀內(nèi)核源碼,中文注解分析,深挖地基工程,構(gòu)建底層網(wǎng)圖,四大碼倉(cāng)每日同步更新。

鴻蒙源碼分析系列篇 < CSDN | OSCHINA | WeHarmony | 公眾號(hào) >問答式導(dǎo)讀,生活式比喻,表格化說明,圖形化展示,主流站點(diǎn)每日同步更新。

誰(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)樘嗔?只截取了部分:

很多人問圖怎么來的, source insight 4.0 是閱讀大型C/C++工程的必備工具,要用4.0否則中文有亂碼。

可以豪不夸張的說理解LOS_DL_LIST及相關(guān)函數(shù)是讀懂鴻蒙內(nèi)核的關(guān)鍵。前后指針(注者后續(xù)將比喻成一對(duì)左右觸手)靈活的指揮著系統(tǒng)精準(zhǔn)的運(yùn)行，越是深入分析內(nèi)核源碼，越能感受到內(nè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)開始，都可以很方便地訪問它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)，這種數(shù)據(jù)結(jié)構(gòu)形式使得雙向鏈表在查找時(shí)更加方便，特別是大量數(shù)據(jù)的遍歷。由于雙向鏈表具有對(duì)稱性，能方便地完成各種插入、刪除等操作，但需要注意前后方向的操作。

功能接口

鴻蒙系統(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; 
}

具體用法

舉例 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è)民族是一家,來自同一個(gè)父進(jìn)程. 
    ProcessGroup         *group;                       /**< Process group to which a process belongs */ //所屬進(jìn)程組 
    LOS_DL_LIST          subordinateGroupList;         /**< linkage in my group list */ //進(jìn)程是組長(zhǎng)時(shí),有哪些組員進(jìn)程 
    UINT32               threadGroupID;                /**< Which thread group , is the main thread ID of the process */ //哪個(gè)線程組是進(jìn)程的主線程ID 
    UINT32               threadScheduleMap;            /**< The scheduling bitmap table for the thread group of the 
                                                            process */ //進(jìn)程的各線程調(diào)度位圖 
    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 the 
                                                                         priority hash table */ //進(jìn)程的線程組調(diào)度優(yōu)先級(jí)哈希表 
    volatile UINT32      threadNumber; /**< Number of threads alive under this process */ //此進(jìn)程下的活動(dòng)線程數(shù) 
    UINT32               threadCount;  /**< Total number of threads created under this process */ //在此進(jìn)程下創(chuàng)建的線程總數(shù) 
    LOS_DL_LIST          waitList;     /**< The process holds the waitLits to support wait/waitpid *///進(jìn)程持有等待鏈表以支持wait/waitpid 
} LosProcessCB;

看個(gè)簡(jiǎn)單點(diǎn)的 pendList表示這個(gè)進(jìn)程中所有被阻塞的任務(wù)(task)都會(huì)掛到這個(gè)鏈表上管理. 任務(wù)阻塞的原因很多,可能是申請(qǐng)互斥鎖失敗,可能等待事件讀消息隊(duì)列,還可能開了一個(gè)定時(shí)任務(wù)等等。

再來看一個(gè)復(fù)雜點(diǎn)的 threadPriQueueList,這又是干嘛的?從名字可以看出來是線程的隊(duì)列鏈表,在鴻蒙內(nèi)核線程就是任務(wù)(task),任務(wù)分等了32個(gè)優(yōu)先級(jí),同級(jí)的任務(wù)放在同一個(gè)雙向鏈表中, 32級(jí)就是32個(gè)雙向鏈表,所以是個(gè)鏈表數(shù)組,每條鏈表中存放的是已就緒等待被調(diào)度的任務(wù)。

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

作者郵箱:weharmony@126.com

鴻蒙內(nèi)核源碼注釋中文版 < Gitee倉(cāng) | CSDN倉(cāng) | Github倉(cāng) | Coding倉(cāng) >精讀內(nèi)核源碼,中文注解分析,深挖地基工程,構(gòu)建底層網(wǎng)圖,四大碼倉(cāng)每日同步更新

鴻蒙源碼分析系列篇 < CSDN | OSCHINA | WeHarmony | 公眾號(hào) >問答式導(dǎo)讀,生活式比喻,表格化說明,圖形化展示,主流站點(diǎn)每日同步更新