Linux 核心裡的資料結構——雙向連結清單Linux 核心裡的資料結構——雙向連結清單

<code>struct list_head {</code>

<code>struct list_head *next, *prev;</code>

<code>};</code>

<code>struct glist {</code>

<code>gpointer data;</code>

<code>glist *next;</code>

<code>glist *prev;</code>

通常來說一個連結清單結構會包含一個指向某個項目的指針。但是 linux 核心中的連結清單實作并沒有這樣做。是以問題來了：連結清單在哪裡儲存資料呢？。實際上，核心裡實作的連結清單是侵入式連結清單（intrusive list）。侵入式連結清單并不在節點内儲存資料-它的節點僅僅包含指向前後節點的指針，以及指向連結清單節點資料部分的指針——資料就是這樣附加在連結清單上的。這就使得這個資料結構是通用的，使用起來就不需要考慮節點資料的類型了。

比如：

<code>struct nmi_desc {</code>

<code>spinlock_t lock;</code>

<code>struct list_head head;</code>

<code>#define misc_major 10</code>

但是都有各自不同的次裝置号。比如：

<code>ls -l /dev | grep 10</code>

<code>crw------- 1 root root 10, 235 mar 21 12:01 autofs</code>

<code>drwxr-xr-x 10 root root 200 mar 21 12:01 cpu</code>

<code>crw------- 1 root root 10, 62 mar 21 12:01 cpu_dma_latency</code>

<code>crw------- 1 root root 10, 203 mar 21 12:01 cuse</code>

<code>drwxr-xr-x 2 root root 100 mar 21 12:01 dri</code>

<code>crw-rw-rw- 1 root root 10, 229 mar 21 12:01 fuse</code>

<code>crw------- 1 root root 10, 228 mar 21 12:01 hpet</code>

<code>crw------- 1 root root 10, 183 mar 21 12:01 hwrng</code>

<code>crw-rw----+ 1 root kvm 10, 232 mar 21 12:01 kvm</code>

<code>crw-rw---- 1 root disk 10, 237 mar 21 12:01 loop-control</code>

<code>crw------- 1 root root 10, 227 mar 21 12:01 mcelog</code>

<code>crw------- 1 root root 10, 59 mar 21 12:01 memory_bandwidth</code>

<code>crw------- 1 root root 10, 61 mar 21 12:01 network_latency</code>

<code>crw------- 1 root root 10, 60 mar 21 12:01 network_throughput</code>

<code>crw-r----- 1 root kmem 10, 144 mar 21 12:01 nvram</code>

<code>brw-rw---- 1 root disk 1, 10 mar 21 12:01 ram10</code>

<code>crw--w---- 1 root tty 4, 10 mar 21 12:01 tty10</code>

<code>crw-rw---- 1 root dialout 4, 74 mar 21 12:01 ttys10</code>

<code>crw------- 1 root root 10, 63 mar 21 12:01 vga_arbiter</code>

<code>crw------- 1 root root 10, 137 mar 21 12:01 vhci</code>

現在讓我們看看它是如何使用連結清單的。首先看一下結構體 <code>miscdevice</code>：

<code>struct miscdevice</code>

<code>{</code>

<code>int minor;</code>

<code>const char *name;</code>

<code>const struct file_operations *fops;</code>

<code>struct list_head list;</code>

<code>struct device *parent;</code>

<code>struct device *this_device;</code>

<code>const char *nodename;</code>

<code>mode_t mode;</code>

可以看到結構體<code>miscdevice</code>的第四個變量<code>list</code> 是所有注冊過的裝置的連結清單。在源代碼檔案的開始可以看到這個連結清單的定義：

<code>static list_head(misc_list);</code>

它實際上是對用<code>list_head</code> 類型定義的變量的擴充。

<code>#define list_head(name) \</code>

<code>struct list_head name = list_head_init(name)</code>

然後使用宏 <code>list_head_init</code> 進行初始化，這會使用變量<code>name</code> 的位址來填充<code>prev</code>和<code>next</code> 結構體的兩個變量。

<code>#define list_head_init(name) { &amp;(name), &amp;(name) }</code>

現在來看看注冊雜項裝置的函數<code>misc_register</code>。它在一開始就用函數 <code>init_list_head</code> 初始化了<code>miscdevice-&gt;list</code>。

<code>init_list_head(&amp;misc-&gt;list);</code>

作用和宏<code>list_head_init</code>一樣。

<code>static inline void init_list_head(struct list_head *list)</code>

<code>list-&gt;next = list;</code>

<code>list-&gt;prev = list;</code>

<code>}</code>

接下來，在函數<code>device_create</code> 建立了裝置後，我們就用下面的語句将裝置添加到裝置連結清單：

<code>list_add(&amp;misc-&gt;list, &amp;misc_list);</code>

核心檔案<code>list.h</code> 提供了向連結清單添加新項的 api 接口。我們來看看它的實作：

<code>static inline void list_add(struct list_head *new, struct list_head *head)</code>

<code>__list_add(new, head, head-&gt;next);</code>

實際上就是使用3個指定的參數來調用了内部函數<code>__list_add</code>：

new - 新項。

head - 新項将會插在<code>head</code>的後面

head-&gt;next - 插入前，<code>head</code> 後面的項。

<code>__list_add</code>的實作非常簡單：

<code>static inline void __list_add(struct list_head *new,</code>

<code>struct list_head *prev,</code>

<code>struct list_head *next)</code>

<code>next-&gt;prev = new;</code>

<code>new-&gt;next = next;</code>

<code>new-&gt;prev = prev;</code>

<code>prev-&gt;next = new;</code>

這裡，我們在<code>prev</code>和<code>next</code> 之間添加了一個新項。是以我們開始時用宏<code>list_head_init</code>定義的<code>misc</code> 連結清單會包含指向<code>miscdevice-&gt;list</code> 的向前指針和向後指針。

這兒還有一個問題：如何得到清單的内容呢？這裡有一個特殊的宏：

<code>#define list_entry(ptr, type, member) \</code>

<code>container_of(ptr, type, member)</code>

使用了三個參數：

ptr - 指向結構 <code>list_head</code> 的指針；

type - 結構體類型;

member - 在結構體内類型為<code>list_head</code> 的變量的名字；

比如說：

<code>const struct miscdevice *p = list_entry(v, struct miscdevice, list)</code>

然後我們就可以使用<code>p-&gt;minor</code> 或者 <code>p-&gt;name</code>來通路<code>miscdevice</code>。讓我們來看看<code>list_entry</code> 的實作：

如我們所見，它僅僅使用相同的參數調用了宏<code>container_of</code>。初看這個宏挺奇怪的：

<code>#define container_of(ptr, type, member) ({ \</code>

<code>const typeof( ((type *)0)-&gt;member ) *__mptr = (ptr); \</code>

<code>(type *)( (char *)__mptr - offsetof(type,member) );})</code>

首先你可以注意到花括号内包含兩個表達式。編譯器會執行花括号内的全部語句，然後傳回最後的表達式的值。

舉個例子來說：

<code>#include &lt;stdio.h&gt;</code>

<code></code>

<code>int main() {</code>

<code>int i = 0;</code>

<code>printf("i = %d\n", ({++i; ++i;}));</code>

<code>return 0;</code>

最終會列印出<code>2</code>。

下一點就是<code>typeof</code>,它也很簡單。就如你從名字所了解的，它僅僅傳回了給定變量的類型。當我第一次看到宏<code>container_of</code>的實作時，讓我覺得最奇怪的就是表達式<code>((type *)0)</code>中的0。實際上這個指針巧妙的計算了從結構體特定變量的偏移，這裡的<code>0</code>剛好就是位寬裡的零偏移。讓我們看一個簡單的例子：

<code>struct s {</code>

<code>int field1;</code>

<code>char field2;</code>

<code>char field3;</code>

<code>printf("%p\n", &amp;((struct s*)0)-&gt;field3);</code>

結果顯示<code>0x5</code>。

下一個宏<code>offsetof</code>會計算從結構體起始位址到某個給定結構字段的偏移。它的實作和上面類似：

<code>#define offsetof(type, member) ((size_t) &amp;((type *)0)-&gt;member)</code>

現在我們來總結一下宏<code>container_of</code>。隻需給定結構體中<code>list_head</code>類型 字段的位址、名字和結構體容器的類型，它就可以傳回結構體的起始位址。在宏定義的第一行，聲明了一個指向結構體成員變量<code>ptr</code>的指針<code>__mptr</code>，并且把<code>ptr</code> 的位址賦給它。現在<code>ptr</code> 和<code>__mptr</code> 指向了同一個位址。從技術上講我們并不需要這一行，但是它可以友善地進行類型檢查。第一行保證了特定的結構體（參數<code>type</code>）包含成員變量<code>member</code>。第二行代碼會用宏<code>offsetof</code>計算成員變量相對于結構體起始位址的偏移，然後從結構體的位址減去這個偏移，最後就得到了結構體。

當然了<code>list_add</code> 和 <code>list_entry</code>不是<code>&lt;linux/list.h&gt;</code>提供的唯一功能。雙向連結清單的實作還提供了如下api：

list_add

list_add_tail

list_del

list_replace

list_move

list_is_last

list_empty

list_cut_position

list_splice

list_for_each

list_for_each_entry

等等很多其它api。

本文來自雲栖社群合作夥伴“linux中國”，原文釋出時間為：2013-04-02.