作者：Sam （甄峰） sam_code@hotmail.com
?
Sam之前看2.4kernel時，?？吹絃ist.也仔細看了一下，但現在長期沒有看kernel,沒有寫程序，已經忘記了很多。今天又看一看并記錄下來。
?
LinuxKernel中，常常需要使用雙向鏈表。在~/include/linux/list.h中，就定義了雙向鏈表和常用的function.
?
鏈表頭如下：
struct list_head {
?struct list_head *next, *prev;
};
?
1.創(chuàng)建雙向鏈表（doubly linkedlist）：
INIT_LIST_HEAD(struct list_head*list)
代碼如下：
static inline void INIT_LIST_HEAD(struct list_head *list)
{
?list->next = list;
?list->prev = list;
}
將List的頭和尾都指向自身。
?
2. 添加內容到雙向鏈表：
2.1: 平常的添加：
2.1.1:將新項目添加到list的頭部（head之后第一個位置）。注意，此處head是指此雙向鏈表頭。
void list_add(struct list_head *new, struct list_head *head)
將參數一（new）添加到head之后。它調用
__list_add(new, head,head->next);也就是說，把new添加到head和head->next之間。
static inline void __list_add(structlist_head *new,
????????struct list_head *prev,
????????struct list_head *next) //它只是將new添加到prev和next之間
{
?next->prev = new;
?new->next = next;
?new->prev = prev;
?prev->next = new;
}
?
2.1.2：將新項目添加雙向鏈表最后一個位置（也就是head的priv）。注意此處head表示list頭。
static inline void list_add_tail(structlist_head *new, struct list_head *head)
{
?__list_add(new, head->prev,head);
}
則將new添加到head->prev和head之間了。
?
2.2:讀拷貝更新（rcu）模式的添加（smp_wmb()）（請看背景知識）
2.2.1: 將新項目加到以知的prev和next之間：
static inline void __list_add_rcu(structlist_head * new,
??struct list_head * prev, structlist_head * next)
{
?new->next = next;
?new->prev = prev;
?smp_wmb();
?next->prev = new;
?prev->next = new;
}//此處注意：smp_wmb();smp_wmb()防止編譯器和CPU優(yōu)化代碼執(zhí)行的順序。在這里，smp_wmb保證在它之前的兩行代碼執(zhí)行完了之后再執(zhí)行后兩行
?
2.2.2:將新項目添加到list的頭部（head之后第一個位置）。注意，此處head是指此雙向鏈表頭。
static inline void list_add_rcu(structlist_head *new, struct list_head *head)
{
?__list_add_rcu(new, head,head->next);
}
?
2.2.3：將新項目添加雙向鏈表最后一個位置（也就是head的priv）。注意此處head表示list頭。staticinline void list_add_tail_rcu(struct list_head *new,
?????structlist_head *head)
{
?__list_add_rcu(new, head->prev,head);
}
?
?
3. 從雙向鏈表刪除項目：
3.1:基本刪除函數：
static inline void __list_del(structlist_head * prev, struct list_head * next)
{
?next->prev = prev;
?prev->next = next;
}//只是將前一個和后一個互指
?
3.2:刪除指定項：
static inline void list_del(structlist_head *entry)
{
?__list_del(entry->prev,entry->next);
?entry->next = LIST_POISON1;
?entry->prev = LIST_POISON2;
}
?
3.3: 安全的刪除指定項：
static inline void list_del_rcu(structlist_head *entry)
{
?__list_del(entry->prev,entry->next);
?entry->prev = LIST_POISON2;
}
此處Sam并不很清楚怎么回事。
?
3.4：刪除并初始化某一項：
static inline void list_del_init(structlist_head *entry)
{
?__list_del(entry->prev,entry->next);
?INIT_LIST_HEAD(entry);
}
?
4.替換某項：
4.1 使用new 替換 old:
static inline void list_replace(structlist_head *old,
????structlist_head *new)
{
?new->next =old->next;
?new->next->prev =new;
?new->prev =old->prev;
?new->prev->next =new;
}
?
4.2 替換并初始化：
static inline voidlist_replace_init(struct list_head *old,
?????structlist_head *new)
{
?list_replace(old, new);
?INIT_LIST_HEAD(old);
}
?
4.3：安全替換：
static inline void list_replace_rcu(structlist_head *old,
????structlist_head *new)
{
?new->next =old->next;
?new->prev =old->prev;
?smp_wmb();
?new->next->prev =new;
?new->prev->next =new;
?old->prev = LIST_POISON2;
}
?
5. 移動項：
5.1移動到頭部
static inline void list_move(structlist_head *list, struct list_head *head)
{
?__list_del(list->prev,list->next);
?list_add(list, head);
}
?
?
5.2移動到尾部
static inline void list_move_tail(structlist_head *list,
?????struct list_head *head)
{
?__list_del(list->prev,list->next);
?list_add_tail(list, head);
}
6.測試項目是否為最后一項：
static inline int list_is_last(conststruct list_head *list,
????conststruct list_head *head)
{
?return list->next == head;
}
7. 測試list是否為空：
static inline int list_empty(const structlist_head *head)
{
?return head->next == head;
}
8. 兩個鏈表連接起來：
8.1：將list鏈表連接如head鏈表頭部：
static inline void __list_splice(structlist_head *list,
????struct list_head *head)
{
?struct list_head *first =list->next;
?struct list_head *last =list->prev;
?struct list_head *at =head->next;
?first->prev =head;
?head->next = first;
?last->next = at;
?at->prev = last;
}
8.2：連接
static inline void list_splice(structlist_head *list, struct list_head *head)
{
?if (!list_empty(list))
??__list_splice(list,head);
}
?
8.3：連接并初始化：
將list連接到head頭部，再將list初始化：
static inline void list_splice_init(structlist_head *list,
???????struct list_head *head)
{
?if (!list_empty(list)) {
??__list_splice(list,head);
??INIT_LIST_HEAD(list);
?}
}
?
9.一些有用的宏：
9.1得到 list_entry(ptr, type, member)
簡單的講，這個宏的作用是：通過結構（type）中的某個變量(member)的指針（ptr）獲取結構本身的指針.
也就是說，type中包含一個成員變量member.且某個結構體實體中member的指針為ptr.則list_entry（）則返回的是：這個結構體實體的指針。至于如何做到的，請看背景知識3---container_of。
?
9.2:list_first_entry(ptr, type,member)?
得到ptr鏈表中下一個的struct的實體。
?
9.3:??list_for_each(pos,head)
#define list_for_each(pos, head)
?for (pos = (head)->next;prefetch(pos->next), pos != (head);
????????pos = pos->next)
它其實就是一個for循環(huán)，循環(huán)雙向鏈表一圈。
prefetch()是檔案快取技術，不用深究。
?
下面幾個宏與之類似：
__list_for_each(pos, head)? //不用檔案快取技術的循環(huán)
list_for_each_prev(pos, head) //向前循環(huán)
?
9.4: list_for_each_entry(pos,head, member)
這個宏是雙向鏈表中最常用的，也是最有用的。表示從以head為頭的雙向循環(huán)列表中，一個一個拿出包含此list項目的結構體（pos的類型），并放到pos中。
#define list_for_each_entry(pos, head,member)????
?for (pos =list_entry((head)->next, typeof(*pos),member);?
?????prefetch(pos->member.next),&pos->member != (head);?
?????pos = list_entry(pos->member.next, typeof(*pos),member))
因為有上面list_entry()的鋪墊，所以非常簡單。
參數一：pos就是一個結構體指針。這個結構體中會包含成員變量member.
參數二：head就是一個雙向鏈表頭。
參數三：pos結構體中的成員變量名。
pos = list_entry((head)->next, typeof(*pos),member)：pos得到雙向鏈表中第一個鏈表被包含的結構體實體。
&pos->member !=(head)：此結構體中的鏈表不是頭。
pos = list_entry(pos->member.next, typeof(*pos),member): pos得到雙向鏈表中下一個結構體實體。
?
?
Linux kernel 中雙向循環(huán)鏈表的使用：
在Linux內核鏈表中，需要用鏈表組織起來的數據通常會包含一個structlist_head成員，結構都通過這個list成員組織在一個鏈表中。
例如：在hid-core.c中，要組織一個report鏈表。
?
于是，首先使用
1）
INIT_LIST_HEAD（&device->report_enum[i].report_list）
struct hid_report {
?struct list_head list;
?unsignedid;?????
?unsignedtype;?????
?struct hid_field*field[HID_MAX_FIELDS];?
?unsignedmaxfield;????
?unsignedsize;?????
?struct hid_device*device;???
};
這就是需要用鏈表組織起來的數據通常會包含一個struct list_head成員。
?
2）。
list_add_tail(&report->list,&report_enum->report_list);
?將report類型的項目添加到剛才初始化的list中。
?
3).
list_for_each_entry(report,&hid->report_enum[HID_INPUT_REPORT].report_list,list)
遍歷?hid->report_enum[HID_INPUT_REPORT].report_list，從其中一個一個得到report.放到report中。
?
?
?
背景知識：
背景知識一：typeof:
typeof不是標準C的運算符，這是gcc的一個擴展.
它與sizeof() 語義類似，sizeof(exp)代表返回exp長度。則typeof(exp)返回的事exp類型。
?
例1：
int a;
typeof(&a) b;
因為a 為int型。所以&a為int*.
也就是說b 為int* 類型。
?
例2：
typedef struct
{
int size;
char t;
} ngate, *pngate;
?
typeof(((ngate *)0)->t) w;
這其實就是表示，w 的類型為：ngate的t的類型。
在這里0并不是真正的變量，可以把它理解為一個替代使用的符號。其意思更可以理解為一個被賦值了的變量，這個數可以不是0，，隨便什么數字都可以。
?
背景知識二：offsetof
kernel中定義如下：
#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
與上面所以類似，（TYPE *）0 表示：0是指向TYPE的指針。
則 &（TYPE *）0->MEMBER表示：TYPE類型的實體0的變量MEMBER的地址，因為從0開始，所以它的地址就成為offset.再用size_t強制轉換，就是從struct頭到成員變量MEMBER的offset.
?
背景知識三：container_of(ptr, type,member)
Kernel中如下定義：
#define container_of(ptr, type, member)({???
?const typeof( ((type *)0)->member) *__mptr = (ptr);?
?(type *)( (char *)__mptr - offsetof(type,member));})
（type *）0: 表明某個實體為type類型的。
(（type *）0)->member表明這個實體的某個成員變量。
typeof((（type *）0)->member) *__mptr表明定了一個指向此成員變量類型的指針。
?
offsetof(type,member)表明成員變量member到結構體類型type頭的offset.
(type *)( (char*)__mptr - offsetof(type,member) 則表明：返回的是一個指向type的指針，此指針指向一個type類型的實體。而參數ptr則是這個實體中的某一個成員變量位置。
?
?
背景知識四：RCU（Read-CopyUpdate）
RCU是2.5/2.6內核中引入的新技術，它通過延遲寫操作來提高同步性能。
系統(tǒng)中數據讀取操作遠多于寫操作，而rwlock機制在smp環(huán)境下隨著處理機增多性能會迅速下降。針對這一應用背景，IBMLinux技術中心的Paul E.McKenney提出了"讀拷貝更新"的技術，并將其應用于Linux內核中。RCU技術的核心是寫操作分為寫-更新兩步，允許讀操作在任何時候無阻訪問，當系統(tǒng)有寫操作時，更新動作一直延遲到對該數據的所有讀操作完成為止。
下載文檔
