鄭文裕 華中偉 徐云龍
摘 要: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.
通訊作者:華中偉