Linux內核鏈表分析

鄭文裕　華中偉　徐云龍

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

關鍵詞：內核；Linux；數據結構；內核鏈表；List

中圖分類號：G642 文獻標識碼：B/A

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

內核鏈表設計思想。如圖1，內核鏈表結點只有前驅和后繼指針沒有數據域，這樣設計是為鏈表提供了一致的訪問接口。和傳統鏈表相比，內核鏈表不是在鏈表結構中包含數據，而是在數據結構中包含鏈表節點。

從圖1中我們可以看到Linux內核鏈表的結點和部分接口聲明。鏈表數據結構的定義很簡單，那Linux內核鏈表是怎么存儲數據的呢？

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

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

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

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

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

參考文獻：

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

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

[3] W.Richard Stevens. UNIX網絡編程，卷2 [J].人民郵電出版社，2016.

通訊作者：華中偉