玩轉(zhuǎn)內(nèi)核鏈表list_head，教你管理不同類型節(jié)點的實現(xiàn)，建議收藏
在Linux內(nèi)核中，提供了一個用來創(chuàng)建雙向循環(huán)鏈表的結(jié)構(gòu) list_head。雖然linux內(nèi)核是用C語言寫的，但是list_head的引入，使得內(nèi)核數(shù)據(jù)結(jié)構(gòu)也可以擁有面向?qū)ο蟮奶匦?，通過使用操作list_head 的通用接口很容易實現(xiàn)代碼的重用，有點類似于C++的繼承機制（希望有機會寫篇文章研究一下C語言的面向?qū)ο髾C制）。
首先找到list_head結(jié)構(gòu)體定義，kernel/inclue/linux/types.h 如下：
struct list_head { struct list_head *next, *prev;};
需要注意的一點是，頭結(jié)點head是不使用的，這點需要注意。
使用list_head組織的鏈表的結(jié)構(gòu)如下圖所示：
然后就開始圍繞這個結(jié)構(gòu)開始構(gòu)建鏈表，然后插入、刪除節(jié)點 ，遍歷整個鏈表等等，其實內(nèi)核已經(jīng)提供好了現(xiàn)成的接口，接下來就讓我們進入 kernel/include/linux/list.h中：
一. 創(chuàng)建鏈表
內(nè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;}
如： 可以通過 LIST_HEAD(mylist) 進行初始化一個鏈表，mylist的prev 和 next 指針都是指向自己。
-
structlist_head mylist = {&mylist, &mylist} ;
但是如果只是利用mylist這樣的結(jié)構(gòu)體實現(xiàn)鏈表就沒有什么實際意義了，因為正常的鏈表都是為了遍歷結(jié)構(gòu)體中的其它有意義的字段而創(chuàng)建的，而我們mylist中只有 prev和next指針，卻沒有實際有意義的字段數(shù)據(jù)，所以毫無意義。
綜上，我們可以創(chuàng)建一個宿主結(jié)構(gòu)，然后在此結(jié)構(gòu)中再嵌套mylist字段，宿主結(jié)構(gòu)又有其它的字段（進程描述符 task_struct，頁面管理的page結(jié)構(gòu)，等就是采用這種方法創(chuàng)建鏈表的）。為簡便理解，定義如下：
-
-
-
-
-
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指針分別指向myhead自己了，如下圖：
二. 添加節(jié)點
內(nèi)核已經(jīng)提供了添加節(jié)點的接口了
1. list_add
如下所示。根據(jù)注釋可知，是在鏈表頭head后方插入一個新節(jié)點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;
下載文檔
