亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

Linux內(nèi)核鏈表

系統(tǒng) 1825 0
以下全部來(lái)自于 http://www.ibm.com/developerworks/cn/linux/kernel/l-chain/index.html 無(wú)任何個(gè)人意見(jiàn)。

本文詳細(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ù)鏈,是線性表的一種重要實(shí)現(xiàn)方式。相對(duì)于數(shù)組,鏈表具有更好的動(dòng)態(tài)性,建立鏈表時(shí)無(wú)需預(yù)先知道數(shù)據(jù)總量,可以隨機(jī)分配空間,可以高效地在鏈表中的任意位置實(shí)時(shí)插入或刪除數(shù)據(jù)。鏈表的開(kāi)銷主要是訪問(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)系形式,鏈表又可以分為單鏈表、雙鏈表、循環(huán)鏈表等多種類型,下面分別給出這幾類常見(jiàn)鏈表類型的示意圖:

1. 單鏈表


圖1 單鏈表
圖1 單鏈表

單鏈表是最簡(jiǎn)單的一類鏈表,它的特點(diǎn)是僅有一個(gè)指針域指向后繼節(jié)點(diǎn)(next),因此,對(duì)單鏈表的遍歷只能從頭至尾(通常是NULL空指針)順序進(jìn)行。

2. 雙鏈表


圖2 雙鏈表
圖2 雙鏈表

通過(guò)設(shè)計(jì)前驅(qū)和后繼兩個(gè)指針域,雙鏈表可以從兩個(gè)方向遍歷,這是它區(qū)別于單鏈表的地方。如果打亂前驅(qū)、后繼的依賴關(guān)系,就可以構(gòu)成"二叉樹(shù)";如果再讓首節(jié)點(diǎn)的前驅(qū)指向鏈表尾節(jié)點(diǎn)、尾節(jié)點(diǎn)的后繼指向首節(jié)點(diǎn)(如圖2中虛線部分),就構(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)的后繼指向首節(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)的組織和使用。



回頁(yè)首



二、 Linux 2.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):鏈表的讀拷貝更新(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ō)明,其余均取自該文件):

              struct list_head {struct list_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)有數(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)典定義方式通常是這樣的(以單鏈表為例):

              struct list_node {struct list_node *next;ElemTypedata;};
            

因?yàn)镋lemType的緣故,對(duì)每一種數(shù)據(jù)項(xiàng)類型都需要定義各自的鏈表結(jié)構(gòu)。有經(jīng)驗(yàn)的C++程序員應(yīng)該知道,標(biāo)準(zhǔn)模板庫(kù)中的<list>采用的是C++ Template,利用模板抽象出和數(shù)據(jù)項(xiàng)類型無(wú)關(guān)的鏈表操作接口。

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


圖3 nf_sockopts鏈表示意圖
圖3 nf_sockopts鏈表示意圖



回頁(yè)首



三、 鏈表操作接口

1. 聲明和初始化

實(shí)際上Linux只定義了鏈表節(jié)點(diǎn),并沒(méi)有專門定義鏈表頭,那么一個(gè)鏈表結(jié)構(gòu)是如何建立起來(lái)的呢?讓我們來(lái)看看LIST_HEAD()這個(gè)宏:

              #define LIST_HEAD_INIT(name) { &(name), &(name) }#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)
            

當(dāng)我們用LIST_HEAD(nf_sockopts)聲明一個(gè)名為nf_sockopts的鏈表頭時(shí),它的next、prev指針都初始化為指向自己,這樣,我們就有了一個(gè)空鏈表,因?yàn)長(zhǎng)inux用頭指針的next是否指向自己來(lái)判斷鏈表是否為空:

              static inline int list_empty(const struct list_head *head){return head->next == head;}
            

除了用LIST_HEAD()宏在聲明的時(shí)候初始化一個(gè)鏈表以外,Linux還提供了一個(gè)INIT_LIST_HEAD宏用于運(yùn)行時(shí)初始化鏈表:

              #define INIT_LIST_HEAD(ptr) do { \(ptr)->next = (ptr); (ptr)->prev = (ptr); \} while (0)
            

我們用INIT_LIST_HEAD(&nf_sockopts)來(lái)使用它。

2. 插入/刪除/合并

a) 插入

對(duì)鏈表的插入操作有兩種:在表頭插入和在表尾插入。Linux為此提供了兩個(gè)接口:

              static inline void list_add(struct list_head *new, struct list_head *head);static inline void list_add_tail(struct list_head *new, struct list_head *head);
            

因?yàn)長(zhǎng)inux鏈表是循環(huán)表,且表頭的next、prev分別指向鏈表中的第一個(gè)和最末一個(gè)節(jié)點(diǎn),所以,list_add和list_add_tail的區(qū)別并不大,實(shí)際上,Linux分別用

              __list_add(new, head, head->next);
            

              __list_add(new, head->prev, head);
            

來(lái)實(shí)現(xiàn)兩個(gè)接口,可見(jiàn),在表頭插入是插入在head之后,而在表尾插入是插入在head->prev之后。

假設(shè)有一個(gè)新nf_sockopt_ops結(jié)構(gòu)變量new_sockopt需要添加到nf_sockopts鏈表頭,我們應(yīng)當(dāng)這樣操作:

              list_add(&new_sockopt.list, &nf_sockopts);
            

從這里我們看出,nf_sockopts鏈表中記錄的并不是new_sockopt的地址,而是其中的list元素的地址。如何通過(guò)鏈表訪問(wèn)到new_sockopt呢?下面會(huì)有詳細(xì)介紹。

b) 刪除

              static inline void list_del(struct list_head *entry);
            

當(dāng)我們需要?jiǎng)h除nf_sockopts鏈表中添加的new_sockopt項(xiàng)時(shí),我們這么操作:

              list_del(&new_sockopt.list);
            

被剔除下來(lái)的new_sockopt.list,prev、next指針?lè)謩e被設(shè)為L(zhǎng)IST_POSITION2和LIST_POSITION1兩個(gè)特殊值,這樣設(shè)置是為了保證不在鏈表中的節(jié)點(diǎn)項(xiàng)不可訪問(wèn)--對(duì)LIST_POSITION1和LIST_POSITION2的訪問(wèn)都將引起頁(yè)故障。與之相對(duì)應(yīng),list_del_init()函數(shù)將節(jié)點(diǎn)從鏈表中解下來(lái)之后,調(diào)用LIST_INIT_HEAD()將節(jié)點(diǎn)置為空鏈狀態(tài)。

c) 搬移

Linux提供了將原本屬于一個(gè)鏈表的節(jié)點(diǎn)移動(dòng)到另一個(gè)鏈表的操作,并根據(jù)插入到新鏈表的位置分為兩類:

              static inline void list_move(struct list_head *list, struct list_head *head);static inline void list_move_tail(struct list_head *list, struct list_head *head);
            

例如list_move(&new_sockopt.list,&nf_sockopts)會(huì)把new_sockopt從它所在的鏈表上刪除,并將其再鏈入nf_sockopts的表頭。

d) 合并

除了針對(duì)節(jié)點(diǎn)的插入、刪除操作,Linux鏈表還提供了整個(gè)鏈表的插入功能:

              static inline void list_splice(struct list_head *list, struct list_head *head);
            

假設(shè)當(dāng)前有兩個(gè)鏈表,表頭分別是list1和list2(都是struct list_head變量),當(dāng)調(diào)用list_splice(&list1,&list2)時(shí),只要list1非空,list1鏈表的內(nèi)容將被掛接在list2鏈表上,位于list2和list2.next(原list2表的第一個(gè)節(jié)點(diǎn))之間。新list2鏈表將以原list1表的第一個(gè)節(jié)點(diǎn)為首節(jié)點(diǎn),而尾節(jié)點(diǎn)不變。如圖(虛箭頭為next指針):


圖4 鏈表合并list_splice(&list1,&list2)
圖4 鏈表合并list_splice(&list1,&list2)

當(dāng)list1被掛接到list2之后,作為原表頭指針的list1的next、prev仍然指向原來(lái)的節(jié)點(diǎn),為了避免引起混亂,Linux提供了一個(gè)list_splice_init()函數(shù):

              static inline void list_splice_init(struct list_head *list, struct list_head *head);
            

該函數(shù)在將list合并到head鏈表的基礎(chǔ)上,調(diào)用INIT_LIST_HEAD(list)將list設(shè)置為空鏈。

3. 遍歷

遍歷是鏈表最經(jīng)常的操作之一,為了方便核心應(yīng)用遍歷鏈表,Linux鏈表將遍歷操作抽象成幾個(gè)宏。在介紹遍歷宏之前,我們先看看如何從鏈表中訪問(wèn)到我們真正需要的數(shù)據(jù)項(xiàng)。

a) 由鏈表節(jié)點(diǎn)到數(shù)據(jù)項(xiàng)變量

我們知道,Linux鏈表中僅保存了數(shù)據(jù)項(xiàng)結(jié)構(gòu)中l(wèi)ist_head成員變量的地址,那么我們?nèi)绾瓮ㄟ^(guò)這個(gè)list_head成員訪問(wèn)到作為它的所有者的節(jié)點(diǎn)數(shù)據(jù)呢?Linux為此提供了一個(gè)list_entry(ptr,type,member)宏,其中ptr是指向該數(shù)據(jù)中l(wèi)ist_head成員的指針,也就是存儲(chǔ)在鏈表中的地址值,type是數(shù)據(jù)項(xiàng)的類型,member則是數(shù)據(jù)項(xiàng)類型定義中l(wèi)ist_head成員的變量名,例如,我們要訪問(wèn)nf_sockopts鏈表中首個(gè)nf_sockopt_ops變量,則如此調(diào)用:

              list_entry(nf_sockopts->next, struct nf_sockopt_ops, list);
            

這里"list"正是nf_sockopt_ops結(jié)構(gòu)中定義的用于鏈表操作的節(jié)點(diǎn)成員變量名。

list_entry的使用相當(dāng)簡(jiǎn)單,相比之下,它的實(shí)現(xiàn)則有一些難懂:

              #define list_entry(ptr, type, member) container_of(ptr, type, member)container_of宏定義在[include/linux/kernel.h]中:#define container_of(ptr, type, member) ({\        const typeof( ((type *)0)->member ) *__mptr = (ptr);\        (type *)( (char *)__mptr - offsetof(type,member) );})offsetof宏定義在[include/linux/stddef.h]中:#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
            

size_t最終定義為unsigned int(i386)。

這里使用的是一個(gè)利用編譯器技術(shù)的小技巧,即先求得結(jié)構(gòu)成員在與結(jié)構(gòu)中的偏移量,然后根據(jù)成員變量的地址反過(guò)來(lái)得出屬主結(jié)構(gòu)變量的地址。

container_of()和offsetof()并不僅用于鏈表操作,這里最有趣的地方是((type *)0)->member,它將0地址強(qiáng)制"轉(zhuǎn)換"為type結(jié)構(gòu)的指針,再訪問(wèn)到type結(jié)構(gòu)中的member成員。在container_of宏中,它用來(lái)給typeof()提供參數(shù)(typeof()是gcc的擴(kuò)展,和sizeof()類似),以獲得member成員的數(shù)據(jù)類型;在offsetof()中,這個(gè)member成員的地址實(shí)際上就是type數(shù)據(jù)結(jié)構(gòu)中member成員相對(duì)于結(jié)構(gòu)變量的偏移量。

如果這么說(shuō)還不好理解的話,不妨看看下面這張圖:


圖5 offsetof()宏的原理
圖5 offsetof()宏的原理

對(duì)于給定一個(gè)結(jié)構(gòu),offsetof(type,member)是一個(gè)常量,list_entry()正是利用這個(gè)不變的偏移量來(lái)求得鏈表數(shù)據(jù)項(xiàng)的變量地址。

b) 遍歷宏

在[net/core/netfilter.c]的nf_register_sockopt()函數(shù)中有這么一段話:

              ……struct list_head *i;……list_for_each(i, &nf_sockopts) {struct nf_sockopt_ops *ops = (struct nf_sockopt_ops *)i;……}……
            

函數(shù)首先定義一個(gè)(struct list_head *)指針變量i,然后調(diào)用list_for_each(i,&nf_sockopts)進(jìn)行遍歷。在[include/linux/list.h]中,list_for_each()宏是這么定義的:

                      #define list_for_each(pos, head) \for (pos = (head)->next, prefetch(pos->next); pos != (head); \        pos = pos->next, prefetch(pos->next))        
            

它實(shí)際上是一個(gè)for循環(huán),利用傳入的pos作為循環(huán)變量,從表頭head開(kāi)始,逐項(xiàng)向后(next方向)移動(dòng)pos,直至又回到head(prefetch()可以不考慮,用于預(yù)取以提高遍歷速度)。

那么在nf_register_sockopt()中實(shí)際上就是遍歷nf_sockopts鏈表。為什么能直接將獲得的list_head成員變量地址當(dāng)成struct nf_sockopt_ops數(shù)據(jù)項(xiàng)變量的地址呢?我們注意到在struct nf_sockopt_ops結(jié)構(gòu)中,list是其中的第一項(xiàng)成員,因此,它的地址也就是結(jié)構(gòu)變量的地址。更規(guī)范的獲得數(shù)據(jù)變量地址的用法應(yīng)該是:

              struct nf_sockopt_ops *ops = list_entry(i, struct nf_sockopt_ops, list);
            

大多數(shù)情況下,遍歷鏈表的時(shí)候都需要獲得鏈表節(jié)點(diǎn)數(shù)據(jù)項(xiàng),也就是說(shuō)list_for_each()和list_entry()總是同時(shí)使用。對(duì)此Linux給出了一個(gè)list_for_each_entry()宏:

              #define list_for_each_entry(pos, head, member)……
            

與list_for_each()不同,這里的pos是數(shù)據(jù)項(xiàng)結(jié)構(gòu)指針類型,而不是(struct list_head *)。nf_register_sockopt()函數(shù)可以利用這個(gè)宏而設(shè)計(jì)得更簡(jiǎn)單:

              ……struct nf_sockopt_ops *ops;list_for_each_entry(ops,&nf_sockopts,list){……}……
            

某些應(yīng)用需要反向遍歷鏈表,Linux提供了list_for_each_prev()和list_for_each_entry_reverse()來(lái)完成這一操作,使用方法和上面介紹的list_for_each()、list_for_each_entry()完全相同。

如果遍歷不是從鏈表頭開(kāi)始,而是從已知的某個(gè)節(jié)點(diǎn)pos開(kāi)始,則可以使用list_for_each_entry_continue(pos,head,member)。有時(shí)還會(huì)出現(xiàn)這種需求,即經(jīng)過(guò)一系列計(jì)算后,如果pos有值,則從pos開(kāi)始遍歷,如果沒(méi)有,則從鏈表頭開(kāi)始,為此,Linux專門提供了一個(gè)list_prepare_entry(pos,head,member)宏,將它的返回值作為list_for_each_entry_continue()的pos參數(shù),就可以滿足這一要求。

4. 安全性考慮

在并發(fā)執(zhí)行的環(huán)境下,鏈表操作通常都應(yīng)該考慮同步安全性問(wèn)題,為了方便,Linux將這一操作留給應(yīng)用自己處理。Linux鏈表自己考慮的安全性主要有兩個(gè)方面:

a) list_empty()判斷

基本的list_empty()僅以頭指針的next是否指向自己來(lái)判斷鏈表是否為空,Linux鏈表另行提供了一個(gè)list_empty_careful()宏,它同時(shí)判斷頭指針的next和prev,僅當(dāng)兩者都指向自己時(shí)才返回真。這主要是為了應(yīng)付另一個(gè)cpu正在處理同一個(gè)鏈表而造成next、prev不一致的情況。但代碼注釋也承認(rèn),這一安全保障能力有限:除非其他cpu的鏈表操作只有l(wèi)ist_del_init(),否則仍然不能保證安全,也就是說(shuō),還是需要加鎖保護(hù)。

b) 遍歷時(shí)節(jié)點(diǎn)刪除

前面介紹了用于鏈表遍歷的幾個(gè)宏,它們都是通過(guò)移動(dòng)pos指針來(lái)達(dá)到遍歷的目的。但如果遍歷的操作中包含刪除pos指針?biāo)赶虻墓?jié)點(diǎn),pos指針的移動(dòng)就會(huì)被中斷,因?yàn)閘ist_del(pos)將把pos的next、prev置成LIST_POSITION2和LIST_POSITION1的特殊值。

當(dāng)然,調(diào)用者完全可以自己緩存next指針使遍歷操作能夠連貫起來(lái),但為了編程的一致性,Linux鏈表仍然提供了兩個(gè)對(duì)應(yīng)于基本遍歷操作的"_safe"接口:list_for_each_safe(pos, n, head)、list_for_each_entry_safe(pos, n, head, member),它們要求調(diào)用者另外提供一個(gè)與pos同類型的指針n,在for循環(huán)中暫存pos下一個(gè)節(jié)點(diǎn)的地址,避免因pos節(jié)點(diǎn)被釋放而造成的斷鏈。




四、 擴(kuò)展

1. hlist


圖6 list和hlist
圖6 list和hlist

精益求精的Linux鏈表設(shè)計(jì)者(因?yàn)閘ist.h沒(méi)有署名,所以很可能就是Linus Torvalds)認(rèn)為雙頭(next、prev)的雙鏈表對(duì)于HASH表來(lái)說(shuō)"過(guò)于浪費(fèi)",因而另行設(shè)計(jì)了一套用于HASH表應(yīng)用的hlist數(shù)據(jù)結(jié)構(gòu)--單指針表頭雙循環(huán)鏈表,從上圖可以看出,hlist的表頭僅有一個(gè)指向首節(jié)點(diǎn)的指針,而沒(méi)有指向尾節(jié)點(diǎn)的指針,這樣在可能是海量的HASH表中存儲(chǔ)的表頭就能減少一半的空間消耗。

因?yàn)楸眍^和節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)不同,插入操作如果發(fā)生在表頭和首節(jié)點(diǎn)之間,以往的方法就行不通了:表頭的first指針必須修改指向新插入的節(jié)點(diǎn),卻不能使用類似list_add()這樣統(tǒng)一的描述。為此,hlist節(jié)點(diǎn)的prev不再是指向前一個(gè)節(jié)點(diǎn)的指針,而是指向前一個(gè)節(jié)點(diǎn)(可能是表頭)中的next(對(duì)于表頭則是first)指針(struct list_head **pprev),從而在表頭插入的操作可以通過(guò)一致的"*(node->pprev)"訪問(wèn)和修改前驅(qū)節(jié)點(diǎn)的next(或first)指針。

2. read-copy update

在Linux鏈表功能接口中還有一系列以"_rcu"結(jié)尾的宏,與以上介紹的很多函數(shù)一一對(duì)應(yīng)。RCU(Read-Copy Update)是2.5/2.6內(nèi)核中引入的新技術(shù),它通過(guò)延遲寫(xiě)操作來(lái)提高同步性能。

我們知道,系統(tǒng)中數(shù)據(jù)讀取操作遠(yuǎn)多于寫(xiě)操作,而rwlock機(jī)制在smp環(huán)境下隨著處理機(jī)增多性能會(huì)迅速下降(見(jiàn)參考資料4)。針對(duì)這一應(yīng)用背景,IBM Linux技術(shù)中心的Paul E. McKenney提出了"讀拷貝更新"的技術(shù),并將其應(yīng)用于Linux內(nèi)核中。RCU技術(shù)的核心是寫(xiě)操作分為寫(xiě)-更新兩步,允許讀操作在任何時(shí)候無(wú)阻訪問(wèn),當(dāng)系統(tǒng)有寫(xiě)操作時(shí),更新動(dòng)作一直延遲到對(duì)該數(shù)據(jù)的所有讀操作完成為止。Linux鏈表中的RCU功能只是Linux RCU的很小一部分,對(duì)于RCU的實(shí)現(xiàn)分析已超出了本文所及,有興趣的讀者可以自行參閱本文的參考資料;而對(duì)RCU鏈表的使用和基本鏈表的使用方法基本相同。




五、 示例

附件 中的程序除了能正向、反向輸出文件以外,并無(wú)實(shí)際作用,僅用于演示Linux鏈表的使用。

為了簡(jiǎn)便,例子采用的是用戶態(tài)程序模板,如果需要運(yùn)行,可采用如下命令編譯:

              gcc -D__KERNEL__ -I/usr/src/linux-2.6.7/include pfile.c -o pfile
            

因?yàn)閮?nèi)核鏈表限制在內(nèi)核態(tài)使用,但實(shí)際上對(duì)于數(shù)據(jù)結(jié)構(gòu)本身而言并非只能在核態(tài)運(yùn)行,因此,在筆者的編譯中使用"-D__KERNEL__"開(kāi)關(guān)"欺騙"編譯器。



參考資料

  1. 維基百科 http://zh.wikipedia.org ,一個(gè)在GNU Documentation License下發(fā)布的網(wǎng)絡(luò)辭典,自由軟件理念的延伸,本文的"鏈表"概念即使用它的版本。
  2. 《Linux內(nèi)核情景分析》,毛德操先生的這本關(guān)于Linux內(nèi)核的巨著幾乎可以回答絕大部分關(guān)于內(nèi)核的問(wèn)題,其中也包括內(nèi)核鏈表的幾個(gè)關(guān)鍵數(shù)據(jù)結(jié)構(gòu)。
  3. Linux內(nèi)核2.6.7源代碼,所有不明白的問(wèn)題,只要潛心看代碼,總能清楚。
  4. Kernel Korner: Using RCU in the Linux 2.5 Kernel,RCU主要開(kāi)發(fā)者Paul McKenney 2003年10月發(fā)表于Linux Journal上的一篇介紹RCU的文章。在 http://www.rdrop.com/users/paulmck/rclock/ 上可以獲得更多關(guān)于RCU的幫助。



關(guān)于作者

楊沙洲,目前在國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院攻讀軟件方向博士學(xué)位。對(duì)文中存在的技術(shù)問(wèn)題,歡迎向 pubb@163.net 質(zhì)疑。

sylar MAIL: cug@live.cn

Linux內(nèi)核鏈表


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號(hào)聯(lián)系: 360901061

您的支持是博主寫(xiě)作最大的動(dòng)力,如果您喜歡我的文章,感覺(jué)我的文章對(duì)您有幫助,請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長(zhǎng)非常感激您!手機(jī)微信長(zhǎng)按不能支付解決辦法:請(qǐng)將微信支付二維碼保存到相冊(cè),切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對(duì)您有幫助就好】

您的支持是博主寫(xiě)作最大的動(dòng)力,如果您喜歡我的文章,感覺(jué)我的文章對(duì)您有幫助,請(qǐng)用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長(zhǎng)會(huì)非常 感謝您的哦!!!

發(fā)表我的評(píng)論
最新評(píng)論 總共0條評(píng)論
主站蜘蛛池模板: 久草在线免费看视频 | 日日射天天射 | 欧美成人性色生活18黑人 | 99视频国产在线 | 91成人免费观看网站 | 久久精品国产大片免费观看 | 伊人影院视频 | 看欧美的一级毛片 | 亚洲艹逼 | 国产精品夜夜春夜夜爽久久 | 狠狠色伊人亚洲综合成人 | 久久夜色tv网站免费影院 | 五月天婷婷久久 | 色综合久久中文 | 91一区二区三区四区五区 | 综合婷婷 | 免费久久精品 | 久操综合 | 四虎影院在线观看网站 | 四房婷婷在线视频播放 | 5566中文字幕亚洲精品 | a级片免费在线播放 | 久久伊人一区二区三区四区 | 国偷盗摄自产福利一区在线 | 色婷婷中文字幕 | 国产精品二区三区 | 中文字幕一区二区三 | 免费www xxx| 亚洲高清一区二区三区四区 | 日日摸日日碰夜夜97 | 亚洲欧美国产18 | 98色花堂国产精品首页 | 国产一区二区在线视频 | 久久久精品2021免费观看 | 99热久久这里只有精品在 | 操穴网| 久久免费小视频 | 欧美日韩成人 | 亚洲天堂一区 | 精品国产一区二区三区在线观看 | 成年看片永远免费 |