1 連結清單簡述
在講Linux核心中的連結清單之前，我們先來看一下平時所見的連結清單：
/*平時所見的單向連結清單*/
struct entry{
int data;
char * desc;
struct entry *next;
}
/*平時所見的雙向連結清單*/
struct entry{
int data;
char * desc;
struct entry *prev;
struct entry *next;
}
用圖檔表示如下：
下面來看一下Linux核心中關于雙向連結清單的實作：
核心中雙向連結清單的結構體：源代碼網址
struct list_head {
struct list_head *next, *prev;
};
先來說一下Linux核心中的連結清單為什麼要這樣設計？
對于每一個連結清單，都需要實作一組操作：初始化連結清單，插入和删除元素，對連結清單進行周遊等等。試想，如果我們采用普通連結清單那樣的方式，每一次我們建立一個連結清單結構體，我們都需要重新實作初始化、插入、删除、周遊元素等，這可能浪費開發人員的精力，也因為對每個不同的連結清單都要重複相同的原語操作（這裡原語操作指的是對連結清單的建立與增、删、周遊等操作）而造成存儲空間的浪費。
2 核心連結清單實作
Linux核心中有關連結清單操作的源代碼如下：源代碼網址
/*對雙向連結清單進行初始化操作*/
#define LIST_HEAD_INIT(name) { &(name), &(name) }
/*建立一個名稱為name的雙向連結清單*/
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
/*初始化雙向連結清單*/
static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}
/*向連結清單中插入一個元素，準确來說是将new元素插在prev和next元素的中間*/
static inline void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next)
{
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
/*向連結清單頭部插入元素，新插入的元素将成為第一個元素。準确來說是将new元素插入到連結清單第一個元素之前，也就是head之後*/
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
/*向連結清單尾部插入元素，新插入的元素将成為連結清單中最後一個元素，也就是head的prev指向的元素*/
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
/*替換連結清單中的某個元素，其中old為要替換的元素，new表示用于替換old的元素
如果old元素為空，它将會被覆寫（If @old was empty, it will be overwritten.）。
也就是說，如果old是連結清單中唯一一個元素，那麼這個連結清單就會被替換*/
static inline void list_replace(struct list_head *old,
struct list_head *new)
{
new->next = old->next;
new->next->prev = new;
new->prev = old->prev;
new->prev->next = new;
}
/*判斷list元素是否為連結清單中的最後一個元素*/
static inline int list_is_last(const struct list_head *list,
const struct list_head *head)
{
return list->next == head;
}
/*判斷連結清單是否為空*/
static inline int list_empty(const struct list_head *head)
{
return head->next == head;
}
/*判斷一個連結清單中是否隻有一個元素*/
static inline int list_is_singular(const struct list_head *head)
{
return !list_empty(head) && (head->next == head->prev);
}
/*周遊連結清單，head表示要周遊的連結清單，pos表示周遊使用的遊标*/
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
/*逆序周遊一個連結清單，head表示要周遊的連結清單，pos表示周遊使用的遊标*/
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; pos != (head); pos = pos->prev)
/*安全的周遊一個連結清單，head表示要周遊的連結清單，pos表示要周遊的連結清單的遊标，n用來臨時存儲連結清單節點
實際上，在周遊連結清單的時候，可能會發生正在周遊的元素被移除，為此，可以臨時儲存下一個要周遊的連結清單節點
*/
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
/*安全的逆序周遊一個連結清單節點，head表示要周遊的連結清單，pos表示周遊使用的遊标，n用來臨時存放連結清單節點*/
#define list_for_each_prev_safe(pos, n, head) \
for (pos = (head)->prev, n = pos->prev; \
pos != (head); \
pos = n, n = pos->prev)
上面是連結清單的一些基本的方法，關于這些方法的一些簡單說明都已經寫在注釋中了，這些方法也很容易明白。簡單畫了一張插入節點的圖，對應__list_add方法：
下面重點說一下list_del這個方法，這個方法的定義如下：源代碼網址
/*從連結清單中删除一個元素*/
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
prev->next = next;
}
#ifndef CONFIG_DEBUG_LIST
static inline void __list_del_entry(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
}
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
#else
extern void __list_del_entry(struct list_head *entry);
extern void list_del(struct list_head *entry);
#endif
從上面的代碼中不難看出list_del(entry)其實就是entry元素從連結清單中删除，但是下面的兩行代碼需要解釋一下：
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
關于LIST_POISON1和LIST_POISON2的宏定義如下：
/*
* These are non-NULL pointers that will result in page faults
* under normal circumstances, used to verify that nobody uses
* non-initialized list entries.
*/
#define LIST_POISON1 ((void *) 0x100 + POISON_POINTER_DELTA)
#define LIST_POISON2 ((void *) 0x200 + POISON_POINTER_DELTA)
這裡為什麼不将entry->next=NULL;entry->prev=NULL;而是将它們置成LIST_POISON1和LIST_POISON2呢？我們先看一下關于LIST_POISON1和LIST_POISON2的注釋，翻譯過來就是：
這些非空指針在正常情況下會導緻頁面錯誤，用于驗證沒有人使用非初始化連結清單項。
頁面錯誤這的就是缺頁中斷，使用entry->next=LIST_POISON1;entry->LIST_POISON2;應該是在删除連結清單元素的時候，如果該連結清單節點已經被删除，那麼就可以進行提示了。也就是說，在普通環境中，用來驗證所有的連結清單節點都已經被初始化。
看到上面關于Linux核心連結清單的介紹，你可能會突然意識到一個問題：
一個連結清單節點中隻有prev和next域，我們的資料放到哪裡呢？其實Linux核心中的連結清單的使用是有技巧的。比如我們定義一個普通的entry元素，元素中包含data和desc連個屬性，如果使用linux核心連結清單，我們該怎麼做呢？答案如下：
struct entry{
int data;
char *desc;
list_head list;
}
關于上面定義的連結清單，就是我們一開始提出來的Linux核心連結清單的使用，也就是下面的圖。
考慮一個問題，我們現在要對上面的這個連結清單進行周遊，并且在周遊的時候讀取data和desc的值，該怎麼做呢？
看一個例子：
/**
* container_of - cast a member of a structure out to the containing structure
* @ptr: the pointer to the member.
* @type: the type of the container struct this is embedded in.
* @member: the name of the member within the struct.
*
*/
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
/**
* list_entry - get the struct for this entry
* @ptr: the &struct list_head pointer.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_struct within the struct.
*/
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
struct entry{
int data;
char *desc;
list_head list;
}
struct entry my_entry;
struct entry *ep;
struct list_head *this, *next;
list_for_each_safe(this, next, &my_entry) {
ep = list_entry(this, struct entry, list);
//在這裡已經擷取到目前周遊的元素，并且是struct entry類型，也就是ep
//是以這裡可以通過ep->data，ep->desc來擷取到data、desc的值
//to do ......
}
其實上面操作的重點是container_of宏定義，下面我們結合上面的代碼重點來看一下這個宏定義：
/**
* container_of - cast a member of a structure out to the containing structure
* @ptr: the pointer to the member.
* @type: the type of the container struct this is embedded in.
* @member: the name of the member within the struct.
*
*/
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
我們将ptr=this,type=struct entry,member=list帶入上面的container_of(ptr,type,member)宏定義，得到結果如下：
container_of(this, struct entry, list) ({ \
const typeof( ((struct entry *)0)->list ) *__mptr = (this); \
(struct entry *)( (char *)__mptr - offsetof(struct entry,list) );})
下面我們來一行一行的分析一下這個展開後的宏，首先看展開後的宏的第一個分号前的那一句：
const typeof( ((struct entry *)0)->list ) * __mptr = (this);
為了便于觀察，我将括号做了一下切分，接下來一點一點的分析，typeof裡面的内容不難了解，就是将0位址強制轉換成struct entry類型，這種做法你擷取不太清楚，舉個常見的例子： ((struct entry *)&my_entry)這樣擷取容易了解一下，&my_entry其實就是個位址，說白了就是一個數字，隻不過上面((struct entry *)0)中是直接将0當做位址了。typeof在核心中很常見，它的作用就是根據變量來擷取變量的類型，是以const typeof( ((struct entry *)0)->list )這一句的結果就是list_head類型，也就是struct entry結構體中list元素的類型。是以const typeof( ((struct entry *)0)->list ) * __mptr = (this);這一句就相當于list_head *__mptr=this;而這個this，我們之前的定義就是list_head *this;這一句不難了解。接下來看下面一句：
(struct entry *)( (char *)__mptr - offsetof(struct entry,list) );
其中offsetof函數是擷取member在type中的偏移量，在這裡就是擷取list在struct entry結構體中的偏移量，這裡為什麼要将__mptr再轉換成char *類型呢？其實為了在做位址加減是時候保證不會出錯，不轉其實是會出問題的，想一想為什麼？是以(char *)__mptr - offsetof(struct entry,list)就擷取到了整個entry元素所在的位址。是以container_of這個宏定義在上面的例子中的功能很簡單：就是根據struct entry元素中list的位址來擷取整個entry的位址，擷取到整個entry的位址之後，我們就可以通路entry元素中的其他屬性了，在上面的例子中就是通路entry元素中的data、desc屬性。
好了，關于Linux核心連結清單的介紹就寫到這裡。
本人能力有限，文中如有錯誤，請您批評指正，郵箱：[email protected]，謝謝！