以下全部來(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)鏈表類型的示意圖:
單鏈表是最簡(jiǎn)單的一類鏈表,它的特點(diǎn)是僅有一個(gè)指針域指向后繼節(jié)點(diǎn)(next),因此,對(duì)單鏈表的遍歷只能從頭至尾(通常是NULL空指針)順序進(jìn)行。
通過(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)。
循環(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)充分。
![]()
![]()
![]()
![]()
回頁(yè)首
實(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)使用它。
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)
![]()
當(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è)置為空鏈。
遍歷是鏈表最經(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ō)還不好理解的話,不妨看看下面這張圖:
對(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ù),就可以滿足這一要求。
在并發(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)被釋放而造成的斷鏈。
![]()
![]()
精益求精的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)指針。
在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)"欺騙"編譯器。
- 維基百科 http://zh.wikipedia.org ,一個(gè)在GNU Documentation License下發(fā)布的網(wǎng)絡(luò)辭典,自由軟件理念的延伸,本文的"鏈表"概念即使用它的版本。
- 《Linux內(nèi)核情景分析》,毛德操先生的這本關(guān)于Linux內(nèi)核的巨著幾乎可以回答絕大部分關(guān)于內(nèi)核的問(wèn)題,其中也包括內(nèi)核鏈表的幾個(gè)關(guān)鍵數(shù)據(jù)結(jié)構(gòu)。
- Linux內(nèi)核2.6.7源代碼,所有不明白的問(wèn)題,只要潛心看代碼,總能清楚。
- 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ó)防科技大學(xué)計(jì)算機(jī)學(xué)院攻讀軟件方向博士學(xué)位。對(duì)文中存在的技術(shù)問(wèn)題,歡迎向 pubb@163.net 質(zhì)疑。
sylar MAIL: cug@live.cn
更多文章、技術(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ì)您有幫助就好】元
