以下全部來自于 http://www.ibm.com/developerworks/cn/linux/kernel/l-chain/index.html無任何個人意見。
本文詳細分析了 2.6.x 核心中連結清單結構的實作，并通過執行個體對每個連結清單操作接口進行了詳盡的講解。
一、 連結清單資料結構簡介
連結清單是一種常用的組織有序資料的資料結構，它通過指針将一系列資料節點連接配接成一條資料鍊，是線性表的一種重要實作方式。相對于數組，連結清單具有更好的動态性，建立連結清單時無需預先知道資料總量，可以随機配置設定空間，可以高效地在連結清單中的任意位置實時插入或删除資料。連結清單的開銷主要是通路的順序性群組織鍊的空間損失。
通常連結清單資料結構至少應包含兩個域：資料域和指針域，資料域用于存儲資料，指針域用于建立與下一個節點的聯系。按照指針域的組織以及各個節點之間的聯系形式，連結清單又可以分為單連結清單、雙連結清單、循環連結清單等多種類型，下面分别給出這幾類常見連結清單類型的示意圖：
1． 單連結清單
圖1 單連結清單
單連結清單是最簡單的一類連結清單，它的特點是僅有一個指針域指向後繼節點（next），是以，對單連結清單的周遊隻能從頭至尾（通常是NULL空指針）順序進行。
2． 雙連結清單
圖2 雙連結清單
通過設計前驅和後繼兩個指針域，雙連結清單可以從兩個方向周遊，這是它差別于單連結清單的地方。如果打亂前驅、後繼的依賴關系，就可以構成"二叉樹"；如果再讓首節點的前驅指向連結清單尾節點、尾節點的後繼指向首節點（如圖2中虛線部分），就構成了循環連結清單；如果設計更多的指針域，就可以構成各種複雜的樹狀資料結構。
3． 循環連結清單
循環連結清單的特點是尾節點的後繼指向首節點。前面已經給出了雙循環連結清單的示意圖，它的特點是從任意一個節點出發，沿兩個方向的任何一個，都能找到連結清單中的任意一個資料。如果去掉前驅指針，就是單循環連結清單。
在Linux核心中使用了大量的連結清單結構來組織資料，包括裝置清單以及各種功能子產品中的資料組織。這些連結清單大多采用在[include/linux/list.h]實作的一個相當精彩的連結清單資料結構。本文的後繼部分就将通過示例詳細介紹這一資料結構的組織和使用。
| |
|
二、 Linux 2.6核心連結清單資料結構的實作
盡管這裡使用2.6核心作為講解的基礎，但實際上2.4核心中的連結清單結構和2.6并沒有什麼差別。不同之處在于2.6擴充了兩種連結清單資料結構：連結清單的讀拷貝更新（rcu）和HASH連結清單（hlist）。這兩種擴充都是基于最基本的list結構，是以，本文主要介紹基本連結清單結構，然後再簡要介紹一下rcu和hlist。
連結清單資料結構的定義很簡單（節選自[include/linux/list.h]，以下所有代碼，除非加以說明，其餘均取自該檔案）：
|
list_head結構包含兩個指向list_head結構的指針prev和next，由此可見，核心的連結清單具備雙連結清單功能，實際上，通常它都組織成雙循環連結清單。
和第一節介紹的雙連結清單結構模型不同，這裡的list_head沒有資料域。在Linux核心連結清單中，不是在連結清單結構中包含資料，而是在資料結構中包含連結清單節點。
在資料結構課本中，連結清單的經典定義方式通常是這樣的（以單連結清單為例）：
|
因為ElemType的緣故，對每一種資料項類型都需要定義各自的連結清單結構。有經驗的C++程式員應該知道，标準模闆庫中的<list>采用的是C++ Template，利用模闆抽象出和資料項類型無關的連結清單操作接口。
在Linux核心連結清單中，需要用連結清單組織起來的資料通常會包含一個struct list_head成員，例如在[include/linux/netfilter.h]中定義了一個nf_sockopt_ops結構來描述Netfilter為某一協定族準備的getsockopt/setsockopt接口，其中就有一個（struct list_head list）成員，各個協定族的nf_sockopt_ops結構都通過這個list成員組織在一個連結清單中，表頭是定義在[net/core/netfilter.c]中的nf_sockopts（struct list_head）。從下圖中我們可以看到，這種通用的連結清單結構避免了為每個資料項類型定義自己的連結清單的麻煩。Linux的簡捷實用、不求完美和标準的風格，在這裡展現得相當充分。
圖3 nf_sockopts連結清單示意圖
| |
三、 連結清單操作接口
1. 聲明和初始化
實際上Linux隻定義了連結清單節點，并沒有專門定義連結清單頭，那麼一個連結清單結構是如何建立起來的呢？讓我們來看看LIST_HEAD()這個宏：
|
當我們用LIST_HEAD(nf_sockopts)聲明一個名為nf_sockopts的連結清單頭時，它的next、prev指針都初始化為指向自己，這樣，我們就有了一個空連結清單，因為Linux用頭指針的next是否指向自己來判斷連結清單是否為空：
|
除了用LIST_HEAD()宏在聲明的時候初始化一個連結清單以外，Linux還提供了一個INIT_LIST_HEAD宏用于運作時初始化連結清單：
|
我們用INIT_LIST_HEAD(&nf_sockopts)來使用它。
2. 插入/删除/合并
a) 插入
對連結清單的插入操作有兩種：在表頭插入和在表尾插入。Linux為此提供了兩個接口：
|
因為Linux連結清單是循環表，且表頭的next、prev分别指向連結清單中的第一個和最末一個節點，是以，list_add和list_add_tail的差別并不大，實際上，Linux分别用
|
和
|
來實作兩個接口，可見，在表頭插入是插入在head之後，而在表尾插入是插入在head->prev之後。
假設有一個新nf_sockopt_ops結構變量new_sockopt需要添加到nf_sockopts連結清單頭，我們應當這樣操作：
|
從這裡我們看出，nf_sockopts連結清單中記錄的并不是new_sockopt的位址，而是其中的list元素的位址。如何通過連結清單通路到new_sockopt呢？下面會有詳細介紹。
b) 删除
|
當我們需要删除nf_sockopts連結清單中添加的new_sockopt項時，我們這麼操作：
|
被剔除下來的new_sockopt.list，prev、next指針分别被設為LIST_POSITION2和LIST_POSITION1兩個特殊值，這樣設定是為了保證不在連結清單中的節點項不可通路--對LIST_POSITION1和LIST_POSITION2的通路都将引起頁故障。與之相對應，list_del_init()函數将節點從連結清單中解下來之後，調用LIST_INIT_HEAD()将節點置為空鍊狀态。
c) 搬移
Linux提供了将原本屬于一個連結清單的節點移動到另一個連結清單的操作，并根據插入到新連結清單的位置分為兩類：
|
例如list_move(&new_sockopt.list,&nf_sockopts)會把new_sockopt從它所在的連結清單上删除，并将其再鍊入nf_sockopts的表頭。
d) 合并
除了針對節點的插入、删除操作，Linux連結清單還提供了整個連結清單的插入功能：
|
假設目前有兩個連結清單，表頭分别是list1和list2（都是struct list_head變量），當調用list_splice(&list1,&list2)時，隻要list1非空，list1連結清單的内容将被挂接在list2連結清單上，位于list2和list2.next（原list2表的第一個節點）之間。新list2連結清單将以原list1表的第一個節點為首節點，而尾節點不變。如圖（虛箭頭為next指針）：
圖4 連結清單合并list_splice(&list1,&list2)
當list1被挂接到list2之後，作為原表頭指針的list1的next、prev仍然指向原來的節點，為了避免引起混亂，Linux提供了一個list_splice_init()函數：
|
該函數在将list合并到head連結清單的基礎上，調用INIT_LIST_HEAD(list)将list設定為空鍊。
3. 周遊
周遊是連結清單最經常的操作之一，為了友善核心應用周遊連結清單，Linux連結清單将周遊操作抽象成幾個宏。在介紹周遊宏之前，我們先看看如何從連結清單中通路到我們真正需要的資料項。
a) 由連結清單節點到資料項變量
我們知道，Linux連結清單中僅儲存了資料項結構中list_head成員變量的位址，那麼我們如何通過這個list_head成員通路到作為它的所有者的節點資料呢？Linux為此提供了一個list_entry(ptr,type,member)宏，其中ptr是指向該資料中list_head成員的指針，也就是存儲在連結清單中的位址值，type是資料項的類型，member則是資料項類型定義中list_head成員的變量名，例如，我們要通路nf_sockopts連結清單中首個nf_sockopt_ops變量，則如此調用：
|
這裡"list"正是nf_sockopt_ops結構中定義的用于連結清單操作的節點成員變量名。
list_entry的使用相當簡單，相比之下，它的實作則有一些難懂：
|
size_t最終定義為unsigned int（i386）。
這裡使用的是一個利用編譯器技術的小技巧，即先求得結構成員在與結構中的偏移量，然後根據成員變量的位址反過來得出屬主結構變量的位址。
container_of()和offsetof()并不僅用于連結清單操作，這裡最有趣的地方是((type *)0)->member，它将0位址強制"轉換"為type結構的指針，再通路到type結構中的member成員。在container_of宏中，它用來給typeof()提供參數（typeof()是gcc的擴充，和sizeof()類似），以獲得member成員的資料類型；在offsetof()中，這個member成員的位址實際上就是type資料結構中member成員相對于結構變量的偏移量。
如果這麼說還不好了解的話，不妨看看下面這張圖：
圖5 offsetof()宏的原理
對于給定一個結構，offsetof(type,member)是一個常量，list_entry()正是利用這個不變的偏移量來求得連結清單資料項的變量位址。
b) 周遊宏
在[net/core/netfilter.c]的nf_register_sockopt()函數中有這麼一段話：
|
函數首先定義一個(struct list_head *)指針變量i，然後調用list_for_each(i,&nf_sockopts)進行周遊。在[include/linux/list.h]中，list_for_each()宏是這麼定義的：
|
它實際上是一個for循環，利用傳入的pos作為循環變量，從表頭head開始，逐項向後（next方向）移動pos，直至又回到head（prefetch()可以不考慮，用于預取以提高周遊速度）。
那麼在nf_register_sockopt()中實際上就是周遊nf_sockopts連結清單。為什麼能直接将獲得的list_head成員變量位址當成struct nf_sockopt_ops資料項變量的位址呢？我們注意到在struct nf_sockopt_ops結構中，list是其中的第一項成員，是以，它的位址也就是結構變量的位址。更規範的獲得資料變量位址的用法應該是：
|
大多數情況下，周遊連結清單的時候都需要獲得連結清單節點資料項，也就是說list_for_each()和list_entry()總是同時使用。對此Linux給出了一個list_for_each_entry()宏：
|
與list_for_each()不同，這裡的pos是資料項結構指針類型，而不是(struct list_head *)。nf_register_sockopt()函數可以利用這個宏而設計得更簡單：
|
某些應用需要反向周遊連結清單，Linux提供了list_for_each_prev()和list_for_each_entry_reverse()來完成這一操作，使用方法和上面介紹的list_for_each()、list_for_each_entry()完全相同。
如果周遊不是從連結清單頭開始，而是從已知的某個節點pos開始，則可以使用list_for_each_entry_continue(pos,head,member)。有時還會出現這種需求，即經過一系列計算後，如果pos有值，則從pos開始周遊，如果沒有，則從連結清單頭開始，為此，Linux專門提供了一個list_prepare_entry(pos,head,member)宏，将它的傳回值作為list_for_each_entry_continue()的pos參數，就可以滿足這一要求。
4. 安全性考慮
在并發執行的環境下，連結清單操作通常都應該考慮同步安全性問題，為了友善，Linux将這一操作留給應用自己處理。Linux連結清單自己考慮的安全性主要有兩個方面：
a) list_empty()判斷
基本的list_empty()僅以頭指針的next是否指向自己來判斷連結清單是否為空，Linux連結清單另行提供了一個list_empty_careful()宏，它同時判斷頭指針的next和prev，僅當兩者都指向自己時才傳回真。這主要是為了應付另一個cpu正在處理同一個連結清單而造成next、prev不一緻的情況。但代碼注釋也承認，這一安全保障能力有限：除非其他cpu的連結清單操作隻有list_del_init()，否則仍然不能保證安全，也就是說，還是需要加鎖保護。
b) 周遊時節點删除
前面介紹了用于連結清單周遊的幾個宏，它們都是通過移動pos指針來達到周遊的目的。但如果周遊的操作中包含删除pos指針所指向的節點，pos指針的移動就會被中斷，因為list_del(pos)将把pos的next、prev置成LIST_POSITION2和LIST_POSITION1的特殊值。
當然，調用者完全可以自己緩存next指針使周遊操作能夠連貫起來，但為了程式設計的一緻性，Linux連結清單仍然提供了兩個對應于基本周遊操作的"_safe"接口：list_for_each_safe(pos, n, head)、list_for_each_entry_safe(pos, n, head, member)，它們要求調用者另外提供一個與pos同類型的指針n，在for循環中暫存pos下一個節點的位址，避免因pos節點被釋放而造成的斷鍊。
| |
四、 擴充
1. hlist
圖6 list和hlist
精益求精的Linux連結清單設計者（因為list.h沒有署名，是以很可能就是Linus Torvalds）認為雙頭（next、prev）的雙連結清單對于HASH表來說"過于浪費"，因而另行設計了一套用于HASH表應用的hlist資料結構--單指針表頭雙循環連結清單，從上圖可以看出，hlist的表頭僅有一個指向首節點的指針，而沒有指向尾節點的指針，這樣在可能是海量的HASH表中存儲的表頭就能減少一半的空間消耗。
因為表頭和節點的資料結構不同，插入操作如果發生在表頭和首節點之間，以往的方法就行不通了：表頭的first指針必須修改指向新插入的節點，卻不能使用類似list_add()這樣統一的描述。為此，hlist節點的prev不再是指向前一個節點的指針，而是指向前一個節點（可能是表頭）中的next（對于表頭則是first）指針（struct list_head **pprev），進而在表頭插入的操作可以通過一緻的"*(node->pprev)"通路和修改前驅節點的next（或first）指針。
2. read-copy update
在Linux連結清單功能接口中還有一系列以"_rcu"結尾的宏，與以上介紹的很多函數一一對應。RCU（Read-Copy Update）是2.5/2.6核心中引入的新技術，它通過延遲寫操作來提高同步性能。
我們知道，系統中資料讀取操作遠多于寫操作，而rwlock機制在smp環境下随着處理機增多性能會迅速下降（見參考資料4）。針對這一應用背景，IBM Linux技術中心的Paul E. McKenney提出了"讀拷貝更新"的技術，并将其應用于Linux核心中。RCU技術的核心是寫操作分為寫-更新兩步，允許讀操作在任何時候無阻通路，當系統有寫操作時，更新動作一直延遲到對該資料的所有讀操作完成為止。Linux連結清單中的RCU功能隻是Linux RCU的很小一部分，對于RCU的實作分析已超出了本文所及，有興趣的讀者可以自行參閱本文的參考資料；而對RCU連結清單的使用和基本連結清單的使用方法基本相同。
| |
五、 示例
附件中的程式除了能正向、反向輸出檔案以外，并無實際作用，僅用于示範Linux連結清單的使用。
為了簡便，例子采用的是使用者态程式模闆，如果需要運作，可采用如下指令編譯：
|
因為核心連結清單限制在核心态使用，但實際上對于資料結構本身而言并非隻能在核态運作，是以，在筆者的編譯中使用"-D__KERNEL__"開關"欺騙"編譯器。
參考資料
- 維基百科 http://zh.wikipedia.org ，一個在GNU Documentation License下釋出的網絡辭典，自由軟體理念的延伸，本文的"連結清單"概念即使用它的版本。
- 《Linux核心情景分析》，毛德操先生的這本關于Linux核心的巨著幾乎可以回答絕大部分關于核心的問題，其中也包括核心連結清單的幾個關鍵資料結構。
- Linux核心2.6.7源代碼，所有不明白的問題，隻要潛心看代碼，總能清楚。
- Kernel Korner: Using RCU in the Linux 2.5 Kernel，RCU主要開發者Paul McKenney 2003年10月發表于Linux Journal上的一篇介紹RCU的文章。在 http://www.rdrop.com/users/paulmck/rclock/ 上可以獲得更多關于RCU的幫助。
關于作者
| | |
| | 楊沙洲，目前在國防科技大學計算機學院攻讀軟體方向博士學位。對文中存在的技術問題，歡迎向 [email protected] 質疑。 |
sylar MAIL: [email protected]