第2章 數(shù)據(jù)結(jié)構(gòu)的使用

內(nèi)核中有很多數(shù)據(jù)結(jié)構(gòu)本身并沒有實際意義，它們扮演的是輔助角色，為實現(xiàn)某些特殊目的“穿針引線”，比如下面介紹的幾種，可以輔助實現(xiàn)數(shù)據(jù)結(jié)構(gòu)之間關(guān)系。也有某些數(shù)據(jù)結(jié)構(gòu)，特別適用于某些特定場景，實現(xiàn)某些特定功能，比如位圖。

2.1 關(guān)系型數(shù)據(jù)結(jié)構(gòu)

程序=數(shù)據(jù)結(jié)構(gòu)+算法，數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)與數(shù)據(jù)之間的邏輯關(guān)系，算法指的是解決特定問題的步驟和方法。邏輯關(guān)系本身就是現(xiàn)實的反映與抽象，理解邏輯關(guān)系是理解程序的關(guān)鍵，本節(jié)將講述實現(xiàn)一對一、一對多和多對多關(guān)系的常用數(shù)據(jù)結(jié)構(gòu)和方法。

2.1.1 一對一關(guān)系

一對一的關(guān)系隨處可見，結(jié)構(gòu)體與其成員、很多結(jié)構(gòu)體與結(jié)構(gòu)體之間都是這種關(guān)系。結(jié)構(gòu)體與成員的一對一關(guān)系簡單明了，兩個結(jié)構(gòu)體之間的一對一關(guān)系有指針和內(nèi)嵌（包含）兩種表達方式，代碼如下。

第二種方式的主要優(yōu)點是對一對一關(guān)系體現(xiàn)得比較清晰，同時也方便管理，因為通過container_of宏（內(nèi)核定義好的）可以由b計算出a的位置，而不再需要多一個指向a的指針。

然而第二種方式并不一定是最好的，要視邏輯而定。比如男人和妻子，通常是一對一，如果采用內(nèi)嵌的方式首先造成的是邏輯混亂，男人結(jié)構(gòu)體中多了一些不屬于男人的成員（即妻子）；其次，并不是每個男人都有妻子，有些是單身，用指針表示就是NULL，內(nèi)嵌無疑浪費了空間。所以，要滿足邏輯合理、有a就有b這兩個條件，采用這種方式才是比較恰當(dāng)?shù)摹?/p>

安全性是程序的首要要求，而合理的邏輯是安全性重要的前提，違背邏輯的程序即使當(dāng)前“安全”，在程序不斷維護和更新的過程中，隨著開發(fā)人員的變動，隱患遲早會爆發(fā)。

2.1.2 一對多關(guān)系

一對多關(guān)系在內(nèi)核中一般由鏈表或樹實現(xiàn)，由于數(shù)組的大小是固定的，除非在特殊情況下，才會采用數(shù)組。用鏈表實現(xiàn)有多種常用方式，包括list_head、hlist_head/hlist_node、rb_root/rb_node（紅黑樹）等數(shù)據(jù)結(jié)構(gòu)。下面以branch（樹枝）和leaf（樹葉）為例進行分析。

最簡單的方式是單向鏈表，該方式直接明了，只需要leaf結(jié)構(gòu)體內(nèi)包含一個leaf類型的指針字段即可，代碼如下。中斷部分的irq_desc和irqaction結(jié)構(gòu)體使用的就是這種方式。

branch包含指向鏈接頭的指針，leaf對象通過next串聯(lián)起來，如圖2-1所示。

由圖2-1可見該方式的局限在于不能通過一個leaf訪問前一個leaf對象，當(dāng)然也不能方便地在某個元素前面插入新結(jié)點或刪除當(dāng)前結(jié)點，正因為缺乏靈活性，它一般用在只需要通過branch訪問leaf的情況下。一般情況下，鏈表中所有的點都被稱為結(jié)點，其中鏈表頭被稱為頭結(jié)點。為了更好地區(qū)分頭結(jié)點和其他結(jié)點，在本書中分別稱之為鏈表頭和鏈表的（普通）元素。

在需要方便地進行遍歷、插入和刪除等操作的情況下，上面的方式過于笨拙，可以使用雙向鏈表。內(nèi)核中已經(jīng)提供了list_head、hlist_head等數(shù)據(jù)結(jié)構(gòu)來滿足該需求。branch的head字段是該鏈表的頭，每一個相關(guān)的leaf都通過node字段鏈接起來，list_head的使用如下。

利用這個雙向鏈表和container_of等宏，就可以方便地滿足遍歷、插入和刪除等操作，list_head定義如下。

組成的結(jié)構(gòu)如圖2-2所示。

從上圖可見，真正串聯(lián)起來的是list_head，而不是branch或者leaf。不過有了list_head，通過container_of宏就可以得到branch和leaf了。內(nèi)核提供了很多l(xiāng)ist_head相關(guān)的函數(shù)和宏，其中一部分如表2-1所示。

list_head鏈表的頭與鏈表的元素是相同的結(jié)構(gòu)，所以無論傳遞給各操作的參數(shù)是鏈表頭還是元素編譯器都不會報錯。但它們代表的意義不同，有些操作對參數(shù)是有要求的，比如list_delete不能以鏈表頭為參數(shù)，否則branch的list相關(guān)字段被置為LIST_POISON1/LIST_POISON2，整個鏈表將不復(fù)存在。

另外，需要特別注意的是，也正是由于list_delete刪除元素后會重置它的prev、next字段，所以不帶safe后綴的操作（如list_for_each_entry），獲得元素后不能進行刪除當(dāng)前元素的操作，否則無法完成遍歷操作。有safe后綴的操作會使用n臨時復(fù)制當(dāng)前元素的鏈表關(guān)系，使用n繼續(xù)遍歷，所以不存在該問題。

list_head有一個兄弟，即hlist_head/hlist_node。顧名思義，hlist_head表示鏈表頭，hlist_node表示鏈表元素，它們的定義如下。

hlist_head的first字段的值是鏈表第一個node的地址，hlist_node的next字段是指向下一個node的指針，pprev字段的值等于前一個node的next字段的地址。如果分別以curr、prev和next表示當(dāng)前、前一個和下一個node的地址，那么curr->next==next，curr->pprev==&prev->next都成立。

與list_head相比，hlist的鏈表頭與鏈表元素的數(shù)據(jù)結(jié)構(gòu)是不同的，而且hlist_head占用內(nèi)存與list_head相比小了一半。存在多個同質(zhì)的雙向鏈表的情況下，鏈表頭占的空間就值得考慮節(jié)省了。內(nèi)核中很多地方使用了它，這些鏈表頭存于數(shù)組、哈希表、樹結(jié)構(gòu)中，節(jié)省的空間是比較可觀的。

另外，hlist_head不能直接訪問鏈表的最后一個元素，必須遍歷每一個元素才能達到目的，而list_head鏈表頭的prev字段就指向鏈表最后一個元素。因此，hlist_head并不適用于FIFO（First In First Out）的需求中。

內(nèi)核也提供了hlist_head的相關(guān)操作，大多與list_head的操作相似，如表2-2所示。

與list_head相同，不帶safe后綴的操作（如hlist_for_each_entry）獲得元素后，不能進行刪除當(dāng)前元素的操作，否則無法完成遍歷操作。

紅黑樹、基數(shù)（radix）樹等結(jié)構(gòu)也會用在一對多的關(guān)系中，它們涉及比較有趣的算法，在對查詢與增刪改等性能要求較高的地方使用較多，相關(guān)知識可參考算法方面的書籍，內(nèi)核中提供的函數(shù)可參考rbtree.h和radix-tree.h等文件。

2.1.3 多對多關(guān)系

多對多關(guān)系相對復(fù)雜，它并不能像一對多關(guān)系那樣可以簡單地通過將list_head等的結(jié)點包含到結(jié)構(gòu)體中來實現(xiàn)。在教與學(xué)范疇內(nèi)，教師和學(xué)生關(guān)系屬于多對多關(guān)系，下面就以teacher和student結(jié)構(gòu)體為例分析（鏈表以list_head為例）。

一個教師可以有多個學(xué)生，從數(shù)據(jù)結(jié)構(gòu)的角度看，teacher包含list_head鏈表頭，每個student對象都可以通過list_head結(jié)點訪問到，list_head結(jié)點鏈接到teacher包含的頭上，如圖2-3所示。

本質(zhì)上，一對關(guān)系就需要一個結(jié)點，比如學(xué)生A（S_A）是教師A（T_A）的學(xué)生，需要一個結(jié)點鏈接到T_A包含的鏈表頭；同時，學(xué)生A也是教師B的學(xué)生，也需要一個結(jié)點鏈接到T_B包含的鏈表頭。針對該情況，一個學(xué)生可以屬于多個鏈表，所以簡單地將list_head的結(jié)點包含到student結(jié)構(gòu)體中是無法實現(xiàn)多對多關(guān)系的（因為指針指向的唯一性，list_head屬于且僅屬于一個鏈表）。

可行的做法是將list_head獨立于student結(jié)構(gòu)體，并配合一個指向student對象的指針來定位結(jié)點所關(guān)聯(lián)的student對象，如下。

該方案的結(jié)構(gòu)如圖2-4所示。

這樣從student對象的角度，會有多個指針指向它，也有多個結(jié)點與它關(guān)聯(lián)，如此它就可以與多個鏈表產(chǎn)生關(guān)系了。

同樣，一個學(xué)生可以有多個教師，也會遇到一個teacher對象會出現(xiàn)在多個student的鏈表中的問題，那就需要定義一個t_connection結(jié)構(gòu)體，如下。

由于這種關(guān)系是相互的，如果S_A是T_A的學(xué)生，那么T_A必然是S_A的老師；如果S_A不是T_A的學(xué)生，那么T_A必然也不是S_A的老師。反之亦然。所以可以將s_connection和t_connection合并起來，具體代碼如下。

到此，教師和學(xué)生的多對多關(guān)系就可以完整地用程序?qū)崿F(xiàn)了，具體代碼如下。

connection結(jié)構(gòu)體的s_node字段鏈接到teacher結(jié)構(gòu)體head_for_student_list字段表示的鏈表頭，t_node字段鏈接到student結(jié)構(gòu)體head_for_teacher_list字段表示的鏈表頭，這個錯落有致的關(guān)系網(wǎng)就完畢了。

老師T_A有S_A和S_B兩個學(xué)生的關(guān)系，老師T_B有S_A一個學(xué)生的關(guān)系，如圖2-5所示。

input子系統(tǒng)的三個關(guān)鍵結(jié)構(gòu)體input_dev、input_handler、input_handle就是如此實現(xiàn)的，input_dev和input_handler是多對多的關(guān)系，input_handle就相當(dāng)于這里的connection。

并不是每個多對多的關(guān)系中兩個connection結(jié)構(gòu)體都可以合并的，有些關(guān)系并不是相互的，比如男生和女生的暗戀關(guān)系。A男暗戀B女，B女卻不一定暗戀A男；A男的鏈表關(guān)聯(lián)B女，B女的鏈表不一定關(guān)聯(lián)A男。兩個connection結(jié)構(gòu)體合并在一起明顯浪費空間，如果強行利用多余的空間，豈不邏輯混亂。

2.2 位操作數(shù)據(jù)結(jié)構(gòu)

位圖（bitmap），以每一位（bit）來存放或表示某種狀態(tài)，這樣一個字節(jié)（byte）就可以表示8個元素的狀態(tài)，可以極大地節(jié)省內(nèi)存。一個bit只有0和1兩個值，所以它也只適用于每個元素都是“非黑即白”的場景，比如打開和關(guān)閉、被占用和空閑等。

位圖的本質(zhì)是一段物理連續(xù)的存儲空間，其中每一位表示一個元素的狀態(tài)。比如申請新的文件描述符fd時，某一個bit為1，表示該bit對應(yīng)的fd已被占用；為0，則表示fd可用。該bit相對于起始位置的偏移量就是fd的值。我們不妨假設(shè)表示fd的這段連續(xù)內(nèi)存內(nèi)容從低位到高位是 (11111111，11111111，10…)，第17位可用，那么得到的fd可能就是17。

實際上多數(shù)程序員對位圖并不陌生，人們可能經(jīng)常使用一個整數(shù)來表示某些狀態(tài)，比如很多函數(shù)的flags等類似的參數(shù)，會在自己的函數(shù)中操作這個整數(shù)的位來更改它的狀態(tài)，或者根據(jù)它的狀態(tài)來決定函數(shù)的行為。這其實也可以算作位圖的一種，只不過一個整數(shù)一般最多表示32或者64個元素，位圖可以表示的元素可以更多。除此之外，它們在邏輯上可能也有些許差別，位圖表示的元素一般都是同質(zhì)化的，而操作整數(shù)的情況可能邏輯上要復(fù)雜些。

內(nèi)核提供了幾個宏和函數(shù)，可以用來進行位操作，如表2-3所示。

find_first_zero_bit和find_first_bit的第二個參數(shù)size是以位（bit）為單位的，find_next_zero_bit和find_next_bit從第offset位（包含offset）開始查找為0和為1的位置，找不到則返回size。

有了以上的宏和函數(shù)，可以很方便地找到位圖中的某位，比如要獲取文件描述符的函數(shù)alloc_fd，它最終調(diào)用find_next_zero_bit來查找位圖中下一個值為0的位，該位的偏移量就是可用的文件描述符。

2.3 模塊和內(nèi)核參數(shù)傳遞

內(nèi)核的數(shù)據(jù)結(jié)構(gòu)因為需要供多個模塊使用，所以要考慮通用性，而很多模塊往往要考慮自身的特性，需要滿足自身需求的獨特數(shù)據(jù)結(jié)構(gòu)。模塊傳遞給內(nèi)核通用參數(shù)，從內(nèi)核獲取的也是通用參數(shù)，那么它如何通過通用參數(shù)來獲得屬于它的特殊數(shù)據(jù)呢？在模塊內(nèi)定義全局變量是一個方法，它也不依賴內(nèi)核的通用參數(shù)，除非邏輯需要，全局變量一般并不是首選，下面我們將介紹兩種優(yōu)選方案。

2.3.1 內(nèi)嵌通用數(shù)據(jù)結(jié)構(gòu)

inode是一個典型的例子，內(nèi)核使用inode對象，很多文件系統(tǒng)內(nèi)部除了inode還需要其他特有信息，定義一個內(nèi)嵌inode的特殊結(jié)構(gòu)體就可以解決該問題，代碼如下。

傳遞參數(shù)給內(nèi)核的時候，傳遞my_inode的inode的地址ptr；從內(nèi)核獲得的inode地址，通過container_of(ptr, my_inode, inode)宏就可以獲得my_inode對象。

2.3.2 通用結(jié)構(gòu)的私有變量

內(nèi)核中很多數(shù)據(jù)結(jié)構(gòu)都定義了類型為void*的私有數(shù)據(jù)字段，模塊可以將它特有的數(shù)據(jù)賦值給該字段，通過引用該字段就可以獲取它的數(shù)據(jù)。file結(jié)構(gòu)體的private_data、device結(jié)構(gòu)體的driver_data都是這種用法。

內(nèi)嵌和私有變量方式該如何選擇呢？內(nèi)嵌和對象由模塊負責(zé)創(chuàng)建；私有變量，為私有數(shù)據(jù)的字段賦值的時候，對象已經(jīng)存在了。前者，對象歸模塊所有；后者，對象一般歸內(nèi)核所有。當(dāng)然，有些情況下，模塊也可以將兩種方法一起使用，比如inode除了可以被內(nèi)嵌外，它本身就有一個i_private字段。

2.4 實例分析

數(shù)據(jù)結(jié)構(gòu)是基礎(chǔ)中的基礎(chǔ)，內(nèi)核中的結(jié)構(gòu)體數(shù)不勝數(shù)，讀者可以從它們的使用范圍（模塊內(nèi)部還是內(nèi)核通用）和數(shù)據(jù)結(jié)構(gòu)間的關(guān)系掌握它們。

2.4.1 模塊的封裝

內(nèi)核中經(jīng)常提起模塊，在實現(xiàn)某一特定功能的時候，最好的做法是將它與其他部分獨立開，形成一個單獨的模塊，有利于在未來以最小的改動擴展功能。這并不是說模塊是封閉的，它一方面需要調(diào)用其他模塊的函數(shù)，另一方面也需要提供函數(shù)供其他模塊訪問。

在面向?qū)ο蟮木幊讨校@叫作封裝，C語言并沒有該概念，但封裝的思想是一樣的，我們在模塊中要盡可能少地透漏實現(xiàn)細節(jié)，僅提供必要的函數(shù)供外部使用。這樣在內(nèi)部實現(xiàn)變化的時候，對其他模塊影響更小，或者說在改變內(nèi)部實現(xiàn)的時候，需要考慮的因素更少。

同樣，在使用其他模塊的時候，不要違背其他模塊的訪問控制意圖，雖然在我們試圖這么做的時候編譯器不會報錯。

以inode結(jié)構(gòu)體為例，它主要適用VFS和具體文件系統(tǒng)的實現(xiàn)兩種場景。其他模塊，比如一個設(shè)備驅(qū)動一般是不會直接訪問它的，而是訪問file結(jié)構(gòu)體。從代碼角度，通過file->f_inode就可以得到inode，是可行的，甚至在知道具體的文件系統(tǒng)時，可以通過inode獲得內(nèi)嵌它的那個文件系統(tǒng)內(nèi)定義的xxx_inode。雖然這么做是錯誤的，但是方法起碼是值得斟酌的。

xxx_inode從文件系統(tǒng)的角度不需要為我們的模塊負責(zé)，但強行“綁定”可能會導(dǎo)致更改xxx_inode變得困難。

所以開發(fā)一個新模塊，不僅要理清它自身的邏輯，還要理解已有模塊數(shù)據(jù)結(jié)構(gòu)的意圖，不要逾越對它們的訪問控制。

2.4.2 火眼金睛：看破數(shù)據(jù)結(jié)構(gòu)

要掌握一個模塊，首先要理清模塊內(nèi)的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)是靈魂，函數(shù)是表現(xiàn)。而復(fù)雜的模塊往往數(shù)據(jù)結(jié)構(gòu)也是復(fù)雜的，主要表現(xiàn)在定義的結(jié)構(gòu)體數(shù)量多，而且它們之間的關(guān)系錯綜復(fù)雜。

結(jié)構(gòu)體間的關(guān)系中，類似指針這類單向引用關(guān)系容易理解，較難迅速理清的是間接關(guān)系，比如本章討論的關(guān)系型數(shù)據(jù)結(jié)構(gòu)。這些關(guān)系雖然表面上不明顯，但還是有些技巧可以快速理清脈絡(luò)的。

對一個結(jié)構(gòu)體的某個字段，我們要關(guān)心字段類型和名字兩方面，這句話看似多余卻隱藏玄機。

首先，鏈表或樹類型結(jié)構(gòu)，如果區(qū)分鏈表頭和元素（樹的根和葉），從類型即可區(qū)分結(jié)構(gòu)體在鏈表或樹中的地位。

其次，字段類型在很大程度上體現(xiàn)了它的意圖，這由類型本身的特性決定。鏈表一般用來遍歷或者查找，紅黑樹一般用來查找。

最后，如果從類型上看不出門道，可以嘗試從字段名入手，鏈表頭的名字多為復(fù)數(shù)或者帶有l(wèi)(list)等字樣。如果依然沒有思路，可以借助于代碼注釋，雖然多數(shù)情況下會無功而返。