Linux kernel 之 list_head

Linux Kernel 是世上的 Hacker 們留給世人一份極為珍貴的資產。
然而 Kernel 卻又是如此的龐大，要一下子了解整個 Kernel 實在不容易。

不過，有個有趣的進入點也是一個好的開始。

在大型的系統之中，必定會有大量的資量要處理，儲存...
處理資料的效率和可靠性會強烈的影響一個作業系統的表現。

在這裏 Linux 使用了一個很漂亮，而且相當強大的手法來實作 double link list

它放在 include/linux/list.h

這個東西，其實小弟在三年多前就寫了一篇文章談它
不過那時只是很簡略的談了一這個工具的用法。沒有深入的討論它背後的技術。


list_head 是一個很簡的 struct ，內容如下

struct list_head {
struct list_head *prev,*next;
};

沒錯，它就是這麼的簡單。 list_head 的內容就是兩個 list_head 的指標 (pointer 註一)
我們可以把它想像成一個鉤環，可以把它安裝在任何結構之中。
例如:

struct ANY_STRUCTURE {
int A;
int B;
struct list_head head_1;
char *C;
struct list_head head_2;
}

在這個例子之中 ANY_STRUCTURE 包涵了兩個 list_head 的實體
如下圖所示：


只要稍微想一下，不難發現 head_1 head_2 的 prev 和 next 可以輕易的指到任何 list_head 的位址上。

而當我們有一個結構的定義時，我們就能算出各個 field 在結構中的相對位址。
也就是說 head_1 相對於 struct ANY_STRUCTURE 的位址是 sizeof(int) * 2
而 head_2 的位址是 sizeof(int)*2 + sizeof(struct list_head) + sizeof(char *) 註二

也就是，如果我有一 head_1 的位址，我就可以算出包涵這個 head_1 的ANY_STRUCTURE 的位址了。
設計 head_1 的位址為 ptr，則 ANY_STRUCTURE 的位址是
==> ptr - ((structure ANY_STRUCTURE *)0)->head_1
在這裏，我們把位址 0 當做是 structure ANY_STRUCTURE 的指標，而它指相的 head_1 的 offset 就是 ANY_STRUCTURE 到 head_1 之間的 offset

也就是說，我可以間接從 head_1 或 head_2 的位址得到 ANY_STRUCTURE 的位址。

在 Linux kernel 之中，就利用 list_head 的 prev next 指向 前一個，及後一個 list_head 的物件的位址，和同一串 list 中的物件都為相同結構。就可以不用搬資料，只控制指標的快速對任何 type 的結構做操作。


註一：小弟習慣把 pointer 的中文翻成指標，有些人會翻成指針…有相當多的名字…在這知道指的是 pointer 就好了

註二：在 kernel 之中，因為各種機器的架構不同，我們不可以預設一個基本變數的長度。