• 在Linux內(nèi)核中，提供了一個(gè)用來(lái)創(chuàng)建雙向循環(huán)鏈表的結(jié)構(gòu) list_head。雖然linux內(nèi)核是用C語(yǔ)言寫(xiě)的，但是list_head的引入，使得內(nèi)核數(shù)據(jù)結(jié)構(gòu)也可以擁有面向?qū)ο蟮奶匦?，通過(guò)使用操作list_head 的通用接口很容易實(shí)現(xiàn)代碼的重用，有點(diǎn)類(lèi)似于C++的繼承機(jī)制（希望有機(jī)會(huì)寫(xiě)篇文章研究一下C語(yǔ)言的面向?qū)ο髾C(jī)制）。

• 首先找到list_head結(jié)構(gòu)體定義，kernel/inclue/linux/types.h ?如下：

• 需要注意的一點(diǎn)是，頭結(jié)點(diǎn)head是不使用的，這點(diǎn)需要注意。

• 使用list_head組織的鏈表的結(jié)構(gòu)如下圖所示：

• 然后就開(kāi)始圍繞這個(gè)結(jié)構(gòu)開(kāi)始構(gòu)建鏈表，然后插入、刪除節(jié)點(diǎn) ，遍歷整個(gè)鏈表等等，其實(shí)內(nèi)核已經(jīng)提供好了現(xiàn)成的接口，接下來(lái)就讓我們進(jìn)入 kernel/include/linux/list.h中：

一. 創(chuàng)建鏈表

• 內(nèi)核提供了下面的這些接口來(lái)初始化鏈表：

如： 可以通過(guò) LIST_HEAD（mylist） 進(jìn)行初始化一個(gè)鏈表，mylist的prev 和 next 指針都是指向自己

• 但是如果只是利用mylist這樣的結(jié)構(gòu)體實(shí)現(xiàn)鏈表就沒(méi)有什么實(shí)際意義了，因?yàn)檎５逆湵矶际菫榱吮闅v結(jié)構(gòu)體中的其它有意義的字段而創(chuàng)建的，而我們mylist中只有 prev和next指針，卻沒(méi)有實(shí)際有意義的字段數(shù)據(jù)，所以毫無(wú)意義。

• 綜上，我們可以創(chuàng)建一個(gè)宿主結(jié)構(gòu)，然后在此結(jié)構(gòu)中再嵌套mylist字段，宿主結(jié)構(gòu)又有其它的字段（進(jìn)程描述符 task_struct，頁(yè)面管理的page結(jié)構(gòu)，等就是采用這種方法創(chuàng)建鏈表的）。為簡(jiǎn)便理解，定義如下：

創(chuàng)建鏈表，并初始化

• 這樣我們的鏈表就初始化完畢，鏈表頭的myhead就prev 和 next指針?lè)謩e指向myhead自己了，如下圖：

【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【891587639】整理了一些個(gè)人覺(jué)得比較好的學(xué)習(xí)書(shū)籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。?！前100名進(jìn)群領(lǐng)取，額外贈(zèng)送一份價(jià)值699的內(nèi)核資料包（含視頻教程、電子書(shū)、實(shí)戰(zhàn)項(xiàng)目及代碼)?

二. 添加節(jié)點(diǎn)

• 內(nèi)核已經(jīng)提供了添加節(jié)點(diǎn)的接口了

1. list_add

• 如下所示。根據(jù)注釋可知，是在鏈表頭head后方插入一個(gè)新節(jié)點(diǎn)new。

list_add再調(diào)用__list_add接口

• 其實(shí)就是在myhead鏈表頭后和鏈表頭后第一個(gè)節(jié)點(diǎn)之間插入一個(gè)新節(jié)點(diǎn)。然后這個(gè)新的節(jié)點(diǎn)就變成了鏈表頭后的第一個(gè)節(jié)點(diǎn)了。

• 接著上面步驟創(chuàng)建1個(gè)節(jié)點(diǎn)然后插入到myhead之后

• 然后在創(chuàng)建第二個(gè)節(jié)點(diǎn)，同樣把它插入到header_task之后

• list_add

• 以此類(lèi)推，每次插入一個(gè)新節(jié)點(diǎn)，都是緊靠著header節(jié)點(diǎn)，而之前插入的節(jié)點(diǎn)依次排序靠后，那最后一個(gè)節(jié)點(diǎn)則是第一次插入header后的那個(gè)節(jié)點(diǎn)。最終可得出：先來(lái)的節(jié)點(diǎn)靠后，而后來(lái)的節(jié)點(diǎn)靠前，"先進(jìn)后出，后進(jìn)先出"。所以此種結(jié)構(gòu)類(lèi)似于 stack"堆棧"， 而header_task就類(lèi)似于內(nèi)核stack中的棧頂指針esp，它都是緊靠著最后push到棧的元素。

2. list_add_tail 接口

• 上面所講的list_add接口是從鏈表頭頭后添加的節(jié)點(diǎn)。同樣，內(nèi)核也提供了從鏈表尾處向前添加節(jié)點(diǎn)的接口list_add_tail.讓我們來(lái)看一下它的具體實(shí)現(xiàn)。

• 從注釋可得出：

1. 在一個(gè)特定的鏈表頭前面插入一個(gè)節(jié)點(diǎn)

2. 這個(gè)方法很適用于隊(duì)列的實(shí)現(xiàn)（why？）

• 進(jìn)一步把__list_add（）展開(kāi)如下：

• 所以，很清楚明了， list_add_tail就相當(dāng)于在鏈表頭前方依次插入新的節(jié)點(diǎn)（也可理解為在鏈表尾部開(kāi)始插入節(jié)點(diǎn)，此時(shí)，header節(jié)點(diǎn)既是為節(jié)點(diǎn)，保持不變）

• 利用上面分析list_add接口的方法可畫(huà)出數(shù)據(jù)結(jié)構(gòu)圖形如下。

（1）創(chuàng)建一個(gè)鏈表頭（實(shí)際上應(yīng)該是表尾）代碼參考第一節(jié);

（2）插入第一個(gè)節(jié)點(diǎn) node1.list ， 調(diào)用

（3） 插入第二個(gè)節(jié)點(diǎn)node2.list，調(diào)用

• 依此類(lèi)推，每次插入的新節(jié)點(diǎn)都是緊挨著 header_task表尾，而插入的第一個(gè)節(jié)點(diǎn)my_first_task排在了第一位，my_second_task排在了第二位，可得出：先插入的節(jié)點(diǎn)排在前面，后插入的節(jié)點(diǎn)排在后面，"先進(jìn)先出，后進(jìn)后出"，這不正是隊(duì)列的特點(diǎn)嗎（First in First out）！

三. 刪除節(jié)點(diǎn)

• 內(nèi)核同樣在list.h文件中提供了刪除節(jié)點(diǎn)的接口 list_del（）， 讓我們看一下它的實(shí)現(xiàn)流程

• 利用list_del（struct list_head *entry） 接口就可以刪除鏈表中的任意節(jié)點(diǎn)了，但需注意，前提條件是這個(gè)節(jié)點(diǎn)是已知的，既在鏈表中真實(shí)存在，切prev，next指針都不為NULL。

四. 鏈表遍歷

• 內(nèi)核是同過(guò)下面這個(gè)宏定義來(lái)完成對(duì)list_head鏈表進(jìn)行遍歷的，如下 ：

上面這種方式是從前向后遍歷的，同樣也可以使用下面的宏反向遍歷：

• 而且，list.h 中也提供了list_replace（節(jié)點(diǎn)替換） list_move（節(jié)點(diǎn)移位） ，翻轉(zhuǎn)，查找等接口，這里就不在一一分析了。

五. 宿主結(jié)構(gòu)

1.找出宿主結(jié)構(gòu) list_entry（ptr， type， member）

• 上面的所有操作都是基于list_head這個(gè)鏈表進(jìn)行的，涉及的結(jié)構(gòu)體也都是：

其實(shí)，正如文章一開(kāi)始所說(shuō)，我們真正更關(guān)心的是包含list_head這個(gè)結(jié)構(gòu)體字段的宿主結(jié)構(gòu)體，因?yàn)橹挥卸ㄎ坏搅怂拗鹘Y(jié)構(gòu)體的起始地址，我們才能對(duì)對(duì)宿主結(jié)構(gòu)體中的其它有意義的字段進(jìn)行操作。

那我們?nèi)绾胃鶕?jù)list這個(gè)字段的地址而找到宿主結(jié)構(gòu)node1的位置呢？list.h中定義如下：

• list.h中提供了list_entry宏來(lái)實(shí)現(xiàn)對(duì)應(yīng)地址的轉(zhuǎn)換，但最終還是調(diào)用了container_of宏，所以container_of宏的偉大之處不言而喻。

2 container_of

• 做linux驅(qū)動(dòng)開(kāi)發(fā)的同學(xué)是不是想到了LDD3這本書(shū)中經(jīng)常使用的一個(gè)非常經(jīng)典的宏定義！

• 在LDD3這本書(shū)中的第三章字符設(shè)備驅(qū)動(dòng)，以及第十四章驅(qū)動(dòng)設(shè)備模型中多次提到，我覺(jué)得這個(gè)宏應(yīng)該是內(nèi)核最經(jīng)典的宏之一。那接下來(lái)讓我們揭開(kāi)她的面紗：

• 此宏在內(nèi)核代碼 kernel/include/linux/kernel.h中定義（此處kernel版本為3.10;新版本4.13之后此宏定義改變，但實(shí)現(xiàn)思想保持一致）

• 而offsetof定義在 kernel/include/linux/stddef.h ，如下：

• 舉個(gè)例子，來(lái)簡(jiǎn)單分析一下container_of內(nèi)部實(shí)現(xiàn)機(jī)制。

• 例如:

展開(kāi)container_of宏，探究?jī)?nèi)部的實(shí)現(xiàn)：

1. 獲取成員變量b的類(lèi)型 ，這里獲取的就是short 類(lèi)型。這是GNU_C的擴(kuò)展語(yǔ)法。

2. 用獲取的變量類(lèi)型，定義了一個(gè)指針變量 __mptr ，并且將成員變量 b的首地址賦值給它

3. 這里的offsetof（struct test，b）是用來(lái)計(jì)算成員b在這個(gè)struct test 結(jié)構(gòu)體的偏移。__mptr

• 是成員b的首地址, 現(xiàn)在 減去成員b在結(jié)構(gòu)體里面的偏移值，算出來(lái)的是不是這個(gè)結(jié)構(gòu)體的首地址呀 。

3. 宿主結(jié)構(gòu)的遍歷

• 我們可以根據(jù)結(jié)構(gòu)體中成員變量的地址找到宿主結(jié)構(gòu)的地址，并且我們可以對(duì)成員變量所建立的鏈表進(jìn)行遍歷，那我們是不是也可以通過(guò)某種方法對(duì)宿主結(jié)構(gòu)進(jìn)行遍歷呢？

• 答案肯定是可以的，內(nèi)核在list.h中提供了下面的宏：

• 其中，list_first_entry 和 list_next_entry宏都定義在list.h中，分別代表：獲取第一個(gè)真正的宿主結(jié)構(gòu)的地址;獲取下一個(gè)宿主結(jié)構(gòu)的地址。它們的實(shí)現(xiàn)都是利用list_entry宏。

最終實(shí)現(xiàn)了宿主結(jié)構(gòu)的遍歷

• 首先pos定位到第一個(gè)宿主結(jié)構(gòu)地址，然后循環(huán)獲取下一個(gè)宿主結(jié)構(gòu)地址，如果查到宿主結(jié)構(gòu)中的member成員變量（宿主結(jié)構(gòu)中struct list_head定義的字段）地址為head，則退出，從而實(shí)現(xiàn)了宿主結(jié)構(gòu)的遍歷。如果要循環(huán)對(duì)宿主結(jié)構(gòu)中的其它成員變量進(jìn)行操作，這個(gè)遍歷操作就顯得特別有意義了。

• 我們用上面的 nod結(jié)構(gòu)舉個(gè)例子：