導讀：本文節選自人民郵電出版社出版的《Linux核心程式設計》一書。本書的三位作者有多年的行業經驗：Claudia Salzberg Rodriguez就職于IBM Linux技術中心，從事核心及相關程式設計工具的開發工作；Gordon Fischer為很多裝置開發了Linux和UNIX裝置驅動程式；Steve Smolski在半導體行業已經浸染了26年，開發過各種驅動程式和嵌入式系統。該書譯者為陳莉君、賀炎和劉霞林。
作者獨特的由表及裡的講解方法使得核心程式設計更易于了解：從使用者空間到核心，把核心内在的實作原理與使用者級程式設計的基本原則相聯系，系統地追蹤了實作功能。這種途徑有助于擴大你所了解的Linux知識，加深對核心組成及工作機理的了解。
圖書封面：
核心探索工具集
Linux核心中包含許多對象和資料結構，例如記憶體頁面、程序和中斷。如果作業系統要高效運作，那麼如何及時地從多個對象中引用其中某個對象将是至關重要的。Linux使用連結清單和二叉搜尋樹（以及一組輔助例程）先将這些對象分組放入一個容器中，然後再以某種有效的方式查找單個元素。
連結清單
在計算機科學中，連結清單是一種常見的資料類型，廣泛用于Linux核心中。它在Linux核心中常以循環雙向連結清單的形式出現（參見圖2-1）。是以，給定連結清單中的任一節點，都可以找到其下一節點和上一節點。連結清單的完整代碼存放在頭檔案include/linux/list.h中。本節讨論連結清單的主要特征。
圖2-1 調用宏INIT_LIST_HEAD後的連結清單
以下是使用宏LIST_HEAD和INIT_LIST_HEAD初始化連結清單的代碼：
include/linux/list.h
27
28 struct list_head {
29 struct list_head *next, *prev;
30 };
31
32 #define LIST_HEAD_INIT(name) { &(name), &(name) }
33
34 #define LIST_HEAD(name) \
35 struct list_head name = LIST_HEAD_INIT(name)
36
37 #define INIT_LIST_HEAD(ptr) do { \
38 (ptr)->next = (ptr); (ptr)->prev = (ptr); \
39 } while (0)
第34行：宏LIST_HEAD根據給定的名字name建立連結清單的表頭。
第37行：宏INIT_LIST_HEAD将表頭節點中的prev指針和next指針都初始化為指向表頭節點本身，完成這兩個宏調用後，name就指向一個空的雙向連結清單 。
相應地，簡單的棧和隊列也可以由函數list_add()或list_add_tail()分别來實作，工作隊列的代碼中給出了一個典型的例子：
kernel/workqueue.c
330 list_add(&wq->list, &workqueues);
核心将wq->list加入到系統的工作隊列連結清單workqueues中，是以workqueues就是一個棧形式的隊列。
與此類似，下列代碼将work->entry添加到連結清單cwq->worklist的末尾，cwq->worklist因而也被當作隊列：
84 list_add_tail(&work->entry, &cwq->worklist);
從連結清單中删除某個元素可以調用函數list_del()。該函數将要删除的連結清單元素作為參數，删除元素時，僅需修改該元素的下一個節點和前一個節點，使之互相指向對方即可。例如，當銷毀一個工作隊列時，下列代碼可以從系統的工作隊列連結清單中删除該工作隊列：
382 list_del(&wq->list);
include/linux/list.h中定義了一個特别有用的宏list_for_each_entry：
349 /**
350 * list_for_each_entry - iterate over list of given type
351 * @pos: the type * to use as a loop counter.
352 * @head: the head for your list.
353 * @member: the name of the list_struct within the struct.
354 */
355 #define list_for_each_entry(pos, head, member)
356 for (pos = list_entry((head)->next, typeof(*pos), member),
357 prefetch(pos->member.next);
358 &pos->member != (head);
359 pos = list_entry(pos->member.next, typeof(*pos), member),
360 prefetch(pos->member.next))
該函數循環周遊整個連結清單，操作連結清單中的每個元素。例如，當CPU工作時，将為每個工作隊列喚醒一個程序：
59 struct workqueue_struct {
60 struct cpu_workqueue_struct cpu_wq[NR_CPUS];
61 const char *name;
62 struct list_head list; /* Empty if single thread */
63 };
...
466 case CPU_ONLINE:
467 /* Kick off worker threads. */
468 list_for_each_entry(wq, &workqueues, list)
469 wake_up_process(wq->cpu_wq[hotcpu].thread);
470 break;
該宏展開并使用workqueue_struct wq中的list_head list連結清單來周遊那些頭節點位于工作隊列中的連結清單。如果這看起來讓人有點困惑的話，請記住，為了周遊連結清單并不需要知道我們是哪個連結清單的成員。目前節點的next指針指向連結清單的頭節點 時，就已經通路到該連結清單的表尾了。有關工作隊列的說明參見圖2-2。
圖2-2 工作隊列連結清單
與在前一節中讨論過的帶有雙指針的頭節點相反，這裡我們還可以修改連結清單，使其頭節點中僅有一個指向第一個元素的指針，這樣的頭節點應用于散清單（參見第4章），它沒有指向連結清單表尾元素的指針。由于在散列查找中不常用到尾指針，因而這樣做可以節省記憶體空間。
484 struct hlist_head {
485 struct hlist_node *first;
486 };
488 struct hlist_node {
489 struct hlist_node *next, **pprev;
490 };
492 #define HLIST_HEAD_INIT { .first = NULL }
493 #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
第492行：宏HLIST_HEAD_INIT将指針first置為空指針。
第493行：宏HLIST_HEAD根據名稱建立連結清單，并将指針first置為空指針。
正如我們将會在排程程式、定時器和子產品處理例程（module-handling routine）中看到的那樣，整個Linux核心的工作隊列代碼中都用到了這些連結清單結構。
查找
上一節我們分析了連結清單中的分組元素。有序表根據連結清單中每個元素的關鍵值進行排序（例如，每個元素的關鍵值均大于其前一進制素中對應的值）。如果想要找到某個特定元素（基于其關鍵值），可以從表頭開始，順序查找整個連結清單，比較目前節點的關鍵值與給定的關鍵值。如果不相等，就繼續比較下一個元素，直到找到比對的值為止。采用這種查找方法時，從連結清單中查找給定元素所花的時間與其關鍵值成正比。換句話說，如果增加連結清單中元素個數，這種線性查找将花費更多時間。
大O表示法
對于查找算法而言，大O表示法常用于從理論上來衡量一個算法找到某給定關鍵值的執行時間，它代表對于一個給定值n在最壞情況下所花費的查找時間。線性查找的效率是O（n/2），這就意味着，平均來算，找到一個給定關鍵值必須與連結清單中的一半元素進行比較。
出處：美國标準和技術協會（www.nist.gov）
對于元素較多的連結清單而言，為了不使作業系統空等，需要更快地存儲和定位給定資料的方法。雖然目前已經實作了很多方法（包括其派生方法），但Linux存儲資料時用的另一主要資料結構還是樹。
樹
樹用于Linux記憶體管理中，能夠高效地通路并操作資料。此時，其效率就是用存儲和檢索資料的快慢程度來衡量的。本節将讨論基本樹，重點介紹紅黑樹，而關于樹在Linux下的具體實作及其輔助例程，請參考第6章。在計算機科學中，有根樹由節點和邊組成（參見圖2-3），節點代表資料元素，邊代表節點之間的路徑。第一個節點，或者說頂層節點，就是有根樹的根節點。節點之間的互相關系有父、子、兄弟這三種。每個子節點有且僅有一個父節點（根節點除外），每個父節點可以有一個或多個子節點，互為兄弟的節點有共同的父節點，沒有子的節點稱為葉節點。樹的高度是指從樹根到最遠的葉節點之間的邊數。樹的每一行子孫被稱為一層。在圖2-3中，b和c位于a的下一層，而d、e、f位于a下面兩層。查找給定兄弟節點集合中的某一資料元素時，有序樹最左邊的兄弟節點其值最小，而最右邊的兄弟節點其值最大。樹通常以連結清單和數組的形式來實作，而在樹中移動的過程就叫樹的周遊。
圖2-3 有根樹
1.二叉樹
前面我們用線性查找的方式來查找關鍵值，在每次循環中比較關鍵值的大小。如果每次比較都可以将有序表中待處理的節點數目減半呢？
二叉樹和連結清單不同，它是一種非線性的分層資料結構。在二叉樹中，每個元素或節點指向一個左子或右子節點，每個子節點又指向它的一個左子或右子節點，以此類推。其節點之間排序的主要規則就是左子節點的關鍵值小于父節點的關鍵值，而右子節點的關鍵值大于或等于父節點的關鍵值。是以，對于一個給定節點的關鍵值，其左子樹上所有節點的關鍵值都小于該節點，而其右子樹上所有節點的關鍵值都大于或等于該節點。
往二叉樹中存放資料時，首先必須找到适當的插入位置，而每次循環都可以将要查找的資料個數減半。用大O表示法來表示時，其性能（關于查找的次數）就是O log(n)，相比之下，線性查找的性能是O(n/2)。
周遊二叉樹的算法比較簡單。對于每個節點而言，比較完該節點的關鍵值後，就可以周遊其左子樹或者右子樹，因而，二叉樹的周遊本身就很友善用遞歸來實作。下面将讨論其具體實作、輔助函數以及二叉樹的類型。
剛才我們提到，二叉樹中的節點可以有一個左子節點，或者一個右子節點，或者有左、右兩個子節點，也可以沒有子節點。有序二叉樹的規則是，給定一個節點的值x，其左子節點（包括所有子孫節點）的值小于x，而其右子節點（包括所有子孫節點）的值大于x。由此可知，如果将資料的有序集合插入到二叉樹中，将形成一個線性清單，對于一個給定值，其查找速度就會變得和線性查找一樣慢。例如，根據資料集[0,1,2,3,4,5,6]建立一顆二叉樹時，0是樹根；1比0大，是0的右子節點；2比1大，是1的右子節點；而3是2的右子節點，以此類推。
在均高二叉樹中，根節點到任意葉節點的距離都是一樣遠的。節點添加到二叉樹中後，為了保證查找的效率，必須進行平衡化處理，這可以通過旋轉來實作。插入一個節點後，給定節點e，如果它有一個比任何其他葉節點高兩層的左子樹，就必須右旋轉e。如圖2-4所示，e變成h的父節點，e的右子節點則變成h的左子節點。如果每次插入節點後都進行了平衡化處理，那麼，每次最多隻需要作一次旋轉。滿足平衡規則（若某節點的子節點是一個葉節點的話，它們之間的間距不會超過1）的二叉樹被稱為AVL樹（這一術語最初是由G.M.Adelson-Velskii和E.M.Landis提出來的）。
圖2-4 二叉樹的右旋轉
2.紅黑樹
紅黑樹類似于AVL樹，用于Linux記憶體管理。紅黑樹就是平衡二叉樹，其每個節點都有紅或黑的顔色屬性。
紅黑樹的規則如下：
每個節點要麼是紅色的，要麼是黑色的；
如果一個節點是紅色的，那麼它的所有子節點都是黑色的；
所有葉節點都是黑色的；
從根節點到葉節點的每條路徑包含同樣多的黑色節點。
AVL樹和紅黑樹的查找效率都是O log(n)，而根據插入（已排序的/未排序的）和查找資料的不同，每次都能得出不同的具體數值。（網上有一些讨論二叉搜尋樹[BST]性能的文章，有興趣的話，可以找來看看。）
前面已經提到，許多其他資料結構和相關的查找算法也被應用于計算機科學中。本節的主要目的是，希望通過介紹Linux核心中常用資料結構的基本概念，幫助探索Linux核心。對連結清單和樹結構有一定了解後，就可以更好地了解複雜的操作，例如将在後續章節讨論的記憶體管理和隊列。