玩轉(zhuǎn)內(nèi)核鏈表list_head，教你管理不同類型節(jié)點(diǎn)的實(shí)現(xiàn)，建議收藏
在Linux內(nèi)核中，提供了一個(gè)用來(lái)創(chuàng)建雙向循環(huán)鏈表的結(jié)構(gòu) list_head。雖然linux內(nèi)核是用C語(yǔ)言寫的，但是list_head的引入，使得內(nèi)核數(shù)據(jù)結(jié)構(gòu)也可以擁有面向?qū)ο蟮奶匦?，通過(guò)使用操作list_head 的通用接口很容易實(shí)現(xiàn)代碼的重用，有點(diǎn)類似于C++的繼承機(jī)制（希望有機(jī)會(huì)寫篇文章研究一下C語(yǔ)言的面向?qū)ο髾C(jī)制）。
首先找到list_head結(jié)構(gòu)體定義，kernel/inclue/linux/types.h 如下：
struct list_head { struct list_head *next, *prev;};
需要注意的一點(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)初始化鏈表：
-
-
-
-
-
-
-
-
-
-
struct list_head name = LIST_HEAD_INIT(name) static inline void INIT_LIST_HEAD(struct list_head *list){ WRITE_ONCE(list->next, list); list->prev = list;}
如： 可以通過(guò) LIST_HEAD(mylist) 進(jìn)行初始化一個(gè)鏈表，mylist的prev 和 next 指針都是指向自己。
-
structlist_head mylist = {&mylist, &mylist} ;
但是如果只是利用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)便理解，定義如下：
-
-
-
-
-
struct mylist{ int type; char name[MAX_NAME_LEN]; struct list_head list;}
創(chuàng)建鏈表，并初始化
-
-
structlist_head myhead; INIT_LIST_HEAD(&myhead);
這樣我們的鏈表就初始化完畢，鏈表頭的myhead就prev 和 next指針?lè)謩e指向myhead自己了，如下圖：
二. 添加節(jié)點(diǎn)
內(nèi)核已經(jīng)提供了添加節(jié)點(diǎn)的接口了
1. list_add
如下所示。根據(jù)注釋可知，是在鏈表頭head后方插入一個(gè)新節(jié)點(diǎn)new。
-
-
-
-
-
-
-
-
-
-
-
-
/** * list_add - add a new entry * @new: new entry to be added * @head: list head to add it after * * Insert a new entry after the specified head. * This is good for implementing stacks. */static inline void list_add(struct list_head *new, struct list_head *head){ __list_add(new, head, head->next);}
list_add再調(diào)用__list_add接口
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
/* * Insert a new entry between two known consecutive entries. * * This is only for internal list manipulation where we know * the prev/next entries already! */static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next){ if (!__list_add_valid(new, prev, next)) return; next->prev = new;
下載文檔
