深入分析 linux 內(nèi)核鏈表

《深入分析 linux 內(nèi)核鏈表》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、深入分析Linux內(nèi)核鏈表本文詳細(xì)分析了2.6.x內(nèi)核中鏈表結(jié)構(gòu)的實(shí)現(xiàn)，并通過(guò)實(shí)例對(duì)每個(gè)鏈表操作接口進(jìn)行了詳盡的講解。一、鏈表數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介鏈表是一種常用的組織有序數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，它通過(guò)指針將一系列數(shù)據(jù)節(jié)點(diǎn)連接成一條數(shù)據(jù)鏈，是線(xiàn)性表的一種重要實(shí)現(xiàn)方式。相對(duì)于數(shù)組，鏈表具有更好的動(dòng)態(tài)性，建立鏈表時(shí)無(wú)需預(yù)先知道數(shù)據(jù)總量，可以隨機(jī)分配空間，可以高效地在鏈表中的任意位置實(shí)時(shí)插入或刪除數(shù)據(jù)。鏈表的開(kāi)銷(xiāo)主要是訪(fǎng)問(wèn)的順序性和組織鏈的空間損失。通常鏈表數(shù)據(jù)結(jié)構(gòu)至少應(yīng)包含兩個(gè)域：數(shù)據(jù)域和指針域，數(shù)據(jù)域用于存儲(chǔ)數(shù)據(jù)，指針域用于建立與下一個(gè)節(jié)點(diǎn)的聯(lián)系。按照指針域的組織以及各個(gè)節(jié)點(diǎn)之間的聯(lián)系形式，鏈表又可以分

2、為單鏈表、雙鏈表、循環(huán)鏈表等多種類(lèi)型，下面分別給出這幾類(lèi)常見(jiàn)鏈表類(lèi)型的示意圖：1．單鏈表圖1單鏈表單鏈表是最簡(jiǎn)單的一類(lèi)鏈表，它的特點(diǎn)是僅有一個(gè)指針域指向后繼節(jié)點(diǎn)（next），因此，對(duì)單鏈表的遍歷只能從頭至尾（通常是NULL空指針）順序進(jìn)行。2．雙鏈表圖2雙鏈表通過(guò)設(shè)計(jì)前驅(qū)和后繼兩個(gè)指針域，雙鏈表可以從兩個(gè)方向遍歷，這是它區(qū)別于單鏈表的地方。如果打亂前驅(qū)、后繼的依賴(lài)關(guān)系，就可以構(gòu)成"二叉樹(shù)"；如果再讓首節(jié)點(diǎn)的前驅(qū)指向鏈表尾節(jié)點(diǎn)、尾節(jié)點(diǎn)的后繼指向首節(jié)點(diǎn)（如圖2中虛線(xiàn)部分），就構(gòu)成了循環(huán)鏈表；如果設(shè)計(jì)更多的指針域，就可以構(gòu)成各種復(fù)雜的樹(shù)狀數(shù)據(jù)結(jié)構(gòu)。3．循環(huán)鏈表循環(huán)鏈表的特點(diǎn)是尾節(jié)點(diǎn)的后繼指

3、向首節(jié)點(diǎn)。前面已經(jīng)給出了雙循環(huán)鏈表的示意圖，它的特點(diǎn)是從任意一個(gè)節(jié)點(diǎn)出發(fā)，沿兩個(gè)方向的任何一個(gè)，都能找到鏈表中的任意一個(gè)數(shù)據(jù)。如果去掉前驅(qū)指針，就是單循環(huán)鏈表。在Linux內(nèi)核中使用了大量的鏈表結(jié)構(gòu)來(lái)組織數(shù)據(jù)，包括設(shè)備列表以及各種功能模塊中的數(shù)據(jù)組織。這些鏈表大多采用在[include/linux/list.h]實(shí)現(xiàn)的一個(gè)相當(dāng)精彩的鏈表數(shù)據(jù)結(jié)構(gòu)。本文的后繼部分就將通過(guò)示例詳細(xì)介紹這一數(shù)據(jù)結(jié)構(gòu)的組織和使用。二、Linux2.6內(nèi)核鏈表數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)盡管這里使用2.6內(nèi)核作為講解的基礎(chǔ)，但實(shí)際上2.4內(nèi)核中的鏈表結(jié)構(gòu)和2.6并沒(méi)有什么區(qū)別。不同之處在于2.6擴(kuò)充了兩種鏈表數(shù)據(jù)結(jié)構(gòu)：鏈表的

4、讀拷貝更新（rcu）和HASH鏈表（hlist）。這兩種擴(kuò)展都是基于最基本的list結(jié)構(gòu)，因此，本文主要介紹基本鏈表結(jié)構(gòu)，然后再簡(jiǎn)要介紹一下rcu和hlist。鏈表數(shù)據(jù)結(jié)構(gòu)的定義很簡(jiǎn)單（節(jié)選自[include/linux/list.h]，以下所有代碼，除非加以說(shuō)明，其余均取自該文件）：structlist_head{structlist_head*next,*prev;};list_head結(jié)構(gòu)包含兩個(gè)指向list_head結(jié)構(gòu)的指針prev和next，由此可見(jiàn)，內(nèi)核的鏈表具備雙鏈表功能，實(shí)際上，通常它都組織成雙循環(huán)鏈表。和第一節(jié)介紹的雙鏈表結(jié)構(gòu)模型不同，這里的list_head沒(méi)有

5、數(shù)據(jù)域。在Linux內(nèi)核鏈表中，不是在鏈表結(jié)構(gòu)中包含數(shù)據(jù)，而是在數(shù)據(jù)結(jié)構(gòu)中包含鏈表節(jié)點(diǎn)。在數(shù)據(jù)結(jié)構(gòu)課本中，鏈表的經(jīng)典定義方式通常是這樣的（以單鏈表為例）：structlist_node{structlist_node*next;ElemTypedata;};因?yàn)镋lemType的緣故，對(duì)每一種數(shù)據(jù)項(xiàng)類(lèi)型都需要定義各自的鏈表結(jié)構(gòu)。有經(jīng)驗(yàn)的C++程序員應(yīng)該知道，標(biāo)準(zhǔn)模板庫(kù)中的采用的是C++Template，利用模板抽象出和數(shù)據(jù)項(xiàng)類(lèi)型無(wú)關(guān)的鏈表操作接口。在Linux內(nèi)核鏈表中，需要用鏈表組織起來(lái)的數(shù)據(jù)通常會(huì)包含一個(gè)structlist_head成員，例如在[include/li

6、nux/netfilter.h]中定義了一個(gè)nf_sockopt_ops結(jié)構(gòu)來(lái)描述Netfilter為某一協(xié)議族準(zhǔn)備的getsockopt/setsockopt接口，其中就有一個(gè)（structlist_headlist）成員，各個(gè)協(xié)議族的nf_sockopt_ops結(jié)構(gòu)都通過(guò)這個(gè)list成員組織在一個(gè)鏈表中，表頭是定義在[net/core/netfilter.c]中的nf_sockopts（structlist_head）。從下圖中我們可以看到，這種通用的鏈表結(jié)構(gòu)避免了為每個(gè)數(shù)據(jù)項(xiàng)類(lèi)型定義自己的鏈表的麻煩。Linux的簡(jiǎn)捷實(shí)用、不求完美和標(biāo)準(zhǔn)的風(fēng)格，在這里體現(xiàn)得相當(dāng)充分。圖3nf_s

7、ockopts鏈表示意圖?三、鏈表操作接口1.聲明和初始化實(shí)際上Linux只定義了鏈表節(jié)點(diǎn)，并沒(méi)有專(zhuān)門(mén)定義鏈表頭，那么一個(gè)鏈表結(jié)構(gòu)是如何建立起來(lái)的呢？讓我們來(lái)看看LIST_HEAD()這個(gè)宏：#defineLIST_HEAD_INIT(name){&(name),&(name)}#defineLIST_HEAD(name)structlist_headname=LIST_HEAD_INIT(name)當(dāng)我們用LIST_HEAD(nf_sockopts)聲明