Linux內(nèi)核鏈表分析

鄭文裕　華中偉　徐云龍

摘 要：Linux內(nèi)核代碼博大精深，《深入理解linux內(nèi)核》譯者曾在譯者序中把它形容為“覆壓三百余里，隔離天日”、“廊腰縵回，檐牙高啄；各抱地勢，鉤心斗角。” [ 1 ]，可見其內(nèi)容之豐富、結(jié)構(gòu)之龐雜。Linux內(nèi)核經(jīng)過這么多年的發(fā)展，而這個內(nèi)核雙向鏈表卻依舊存在，足以體現(xiàn)出內(nèi)核鏈表運行的穩(wěn)定性，就連Linux社區(qū)的黑客們也都為這個鏈表的設(shè)計感到自豪。

關(guān)鍵詞：內(nèi)核；Linux；數(shù)據(jù)結(jié)構(gòu)；內(nèi)核鏈表；List

中圖分類號：G642 文獻標(biāo)識碼：B/A

Linux內(nèi)核中通常使用的是雙向循環(huán)鏈表，本文鏈表摘自Linux內(nèi)核版本為4.8.9的List[include/linux/list.h]。

內(nèi)核鏈表設(shè)計思想。如圖1，內(nèi)核鏈表結(jié)點只有前驅(qū)和后繼指針沒有數(shù)據(jù)域，這樣設(shè)計是為鏈表提供了一致的訪問接口。和傳統(tǒng)鏈表相比，內(nèi)核鏈表不是在鏈表結(jié)構(gòu)中包含數(shù)據(jù)，而是在數(shù)據(jù)結(jié)構(gòu)中包含鏈表節(jié)點。

從圖1中我們可以看到Linux內(nèi)核鏈表的結(jié)點和部分接口聲明。鏈表數(shù)據(jù)結(jié)構(gòu)的定義很簡單，那Linux內(nèi)核鏈表是怎么存儲數(shù)據(jù)的呢？

我們可以通過圖2看到，內(nèi)核鏈表使用方式是在數(shù)據(jù)結(jié)構(gòu)中包含鏈表結(jié)點，每個數(shù)據(jù)結(jié)構(gòu)又通過雙向循環(huán)鏈表進行關(guān)聯(lián)著。一個頭結(jié)點head牽引著多個記錄結(jié)點entry，每個entry結(jié)點又被數(shù)據(jù)結(jié)構(gòu)node包含著，既能為鏈表提供了一致的訪問接口，又能將數(shù)據(jù)進行雙向循環(huán)關(guān)聯(lián)，可見內(nèi)核鏈表設(shè)計之精妙。

內(nèi)核鏈表使用的時候每個entry在node結(jié)構(gòu)體中的聲明位置是不固定的，在entry聲明位置未知的情況下，我們要如何對每個數(shù)據(jù)結(jié)點node進行遍歷的呢？其實我們可以使用著名的宏（offsetof、container_of）計算出結(jié)構(gòu)體成員變量的地址，然后進行遍歷。

為什么Linux內(nèi)核設(shè)計者要花這么大的力氣，設(shè)計成這樣的鏈表，還要通過這么高深的宏定義來解決一個遍歷問題？其實花這么大力氣是值得的，目的為了節(jié)省內(nèi)存，內(nèi)核設(shè)計者非常珍惜內(nèi)存的使用。在結(jié)構(gòu)體中有個內(nèi)存對齊的概念，也是一個用空間換時間的作用，加快cpu的訪問速度。這樣一來一個結(jié)構(gòu)體占用多少的內(nèi)存不僅僅是結(jié)構(gòu)體成員變量所占內(nèi)存的總和，成員變量的定義位置也會對結(jié)構(gòu)體占用的內(nèi)存產(chǎn)生影響。

那如何拋棄上面的兩個宏，還能實現(xiàn)鏈表的遍歷呢？其實我們可以把entry的定義放在結(jié)構(gòu)體內(nèi)的第一個位置或者最后一個位置，放在最后一個位置需要再計算下node結(jié)構(gòu)體的大小。

國內(nèi)的企業(yè)一般也就是把entry放在第一個位置，可以實現(xiàn)不使用offsetof、container_of宏就能達到鏈表遍歷的目的，這樣list_head的地址也就是node的地址，然后通過將list_head的地址強制轉(zhuǎn)換為node的地址，即可實現(xiàn)遍歷。

參考文獻：

[1] Daniel P. Bovet & Marco Cesati. 深入理解LINUX內(nèi)核[J].中國電力出版社，2015.

[2] W. Richard Stevens & Stephen A. Rago. UNIX環(huán)境高級編程[J].人民郵電出版社，2016.

[3] W.Richard Stevens. UNIX網(wǎng)絡(luò)編程，卷2 [J].人民郵電出版社，2016.

通訊作者：華中偉