Linux 內(nèi)核提供一套雙向鏈表的實(shí)現(xiàn)，你可以在 include/linux/list.h 中找到。我們以雙向鏈表著手開(kāi)始介紹 Linux 內(nèi)核中的數(shù)據(jù)結(jié)構(gòu) ，因?yàn)檫@個(gè)是在 Linux 內(nèi)核中使用最為廣泛的數(shù)據(jù)結(jié)構(gòu)。

首先讓我們看一下主要的結(jié)構(gòu)體：

C

struct list_head { struct list_head *next, *prev;};

1

2

3

struct list_head {

struct list_head *next, *prev;

};

你可以看到其與常見(jiàn)的結(jié)構(gòu)體實(shí)現(xiàn)有顯著不同，比如 glib 中所使用到的雙向鏈表實(shí)現(xiàn)。

C

struct GList { gpointer data; GList *next; GList *prev;};

1

2

3

4

5

struct GList {

gpointer data;

GList *next;

GList *prev;

};

通常來(lái)說(shuō)，鏈表結(jié)構(gòu)體要包括一個(gè)指向數(shù)據(jù)的指針，不過(guò) Linux 內(nèi)核的鏈表卻不包含此實(shí)現(xiàn)。那么首要的疑問(wèn)：鏈表是用什么方式存儲(chǔ)數(shù)據(jù)的?。Linux 內(nèi)核所實(shí)現(xiàn)的是一種被稱為侵入式的鏈表（Intrusive list），這種鏈表并不在鏈表結(jié)構(gòu)中包含數(shù)據(jù)，而僅提供用于維護(hù)前向與后向訪問(wèn)結(jié)構(gòu)的指針。這種實(shí)現(xiàn)方式使得鏈表數(shù)據(jù)結(jié)構(gòu)非常通用，因?yàn)樗⒉恍枰P(guān)注鏈表所維護(hù)的具體數(shù)據(jù)類型。

比如：

C

struct nmi_desc { spinlock_t lock; struct list_head head;};

1

2

3

4

struct nmi_desc {

spinlock_t lock;

struct list_head head;

};

接下來(lái)讓我們看一些內(nèi)核使用 list_head 的具體例子。正如在前文所述的，Linux 內(nèi)核中諸多模塊都使用了 list_head。這里我們以內(nèi)核雜項(xiàng)字符設(shè)備驅(qū)動(dòng)（miscellaneous character drivers）部分實(shí)現(xiàn)為例。驅(qū)動(dòng)的 API 在 drivers/char/misc.c 中，其實(shí)現(xiàn)了簡(jiǎn)單硬件外設(shè)以及虛擬設(shè)備的驅(qū)動(dòng)，這個(gè)驅(qū)動(dòng)共享主設(shè)備號(hào)（Major number）：

C

#define MISC_MAJOR 10

1

#define MISC_MAJOR??????????????10

每個(gè)設(shè)備有自己的次設(shè)備號(hào)，具體可以看這個(gè)列子：

ls -l /dev | grep 10crw------- 1 root root 10, 235 Mar 21 12:01 autofsdrwxr-xr-x 10 root root 200 Mar 21 12:01 cpucrw------- 1 root root 10, 62 Mar 21 12:01 cpu_dma_latencycrw------- 1 root root 10, 203 Mar 21 12:01 cusedrwxr-xr-x 2 root root 100 Mar 21 12:01 dricrw-rw-rw- 1 root root 10, 229 Mar 21 12:01 fusecrw------- 1 root root 10, 228 Mar 21 12:01 hpetcrw------- 1 root root 10, 183 Mar 21 12:01 hwrngcrw-rw----+ 1 root kvm 10, 232 Mar 21 12:01 kvmcrw-rw---- 1 root disk 10, 237 Mar 21 12:01 loop-controlcrw------- 1 root root 10, 227 Mar 21 12:01 mcelogcrw------- 1 root root 10, 59 Mar 21 12:01 memory_bandwidthcrw------- 1 root root 10, 61 Mar 21 12:01 network_latencycrw------- 1 root root 10, 60 Mar 21 12:01 network_throughputcrw-r----- 1 root kmem 10, 144 Mar 21 12:01 nvrambrw-rw---- 1 root disk 1, 10 Mar 21 12:01 ram10crw--w---- 1 root tty 4, 10 Mar 21 12:01 tty10crw-rw---- 1 root dialout 4, 74 Mar 21 12:01 ttyS10crw------- 1 root root 10, 63 Mar 21 12:01 vga_arbitercrw------- 1 root root 10, 137 Mar 21 12:01 vhci

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

ls -l /dev |??grep 10

crw-------?? 1 root root???? 10, 235 Mar 21 12:01 autofs

drwxr-xr-x??10 root root???????? 200 Mar 21 12:01 cpu

crw-------?? 1 root root???? 10,??62 Mar 21 12:01 cpu_dma_latency

crw-------?? 1 root root???? 10, 203 Mar 21 12:01 cuse

drwxr-xr-x?? 2 root root???????? 100 Mar 21 12:01 dri

crw-rw-rw-?? 1 root root???? 10, 229 Mar 21 12:01 fuse

crw-------?? 1 root root???? 10, 228 Mar 21 12:01 hpet

crw-------?? 1 root root???? 10, 183 Mar 21 12:01 hwrng

crw-rw----+??1 root kvm??????10, 232 Mar 21 12:01 kvm

crw-rw----?? 1 root disk???? 10, 237 Mar 21 12:01 loop-control

crw-------?? 1 root root???? 10, 227 Mar 21 12:01 mcelog

crw-------?? 1 root root???? 10,??59 Mar 21 12:01 memory_bandwidth

crw-------?? 1 root root???? 10,??61 Mar 21 12:01 network_latency

crw-------?? 1 root root???? 10,??60 Mar 21 12:01 network_throughput

crw-r-----?? 1 root kmem???? 10, 144 Mar 21 12:01 nvram

brw-rw----?? 1 root disk??????1,??10 Mar 21 12:01 ram10

crw--w----?? 1 root tty?????? 4,??10 Mar 21 12:01 tty10

crw-rw----?? 1 root dialout?? 4,??74 Mar 21 12:01 ttyS10

crw-------?? 1 root root???? 10,??63 Mar 21 12:01 vga_arbiter

crw-------?? 1 root root???? 10, 137 Mar 21 12:01 vhci

現(xiàn)在我們看看設(shè)備驅(qū)動(dòng)是如何使用鏈表維護(hù)設(shè)備列表的，首先，我們看一下 miscdevice 的 struct 定義：

C

struct miscdevice{ int minor; const char *name; const struct file_operations *fops; struct list_head list; struct device *parent; struct device *this_device; const char *nodename; mode_t mode;};

1

2

3

4

5

6

7

8

9

10

11

struct miscdevice

{

int minor;

const char *name;

const struct file_operations *fops;

struct list_head list;

struct device *parent;

struct device *this_device;

const char *nodename;

mode_t mode;

};

可以看到 miscdevice 的第四個(gè)成員 list ，這個(gè)就是用于維護(hù)已注冊(cè)設(shè)備鏈表的結(jié)構(gòu)。在源代碼文的首部，我們可以看到以下定義：

C

static LIST_HEAD(misc_list);

1

static LIST_HEAD(misc_list);

這個(gè)定義宏展開(kāi)，可以看到是用于定義 list_head 類型變量：

C

#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)

1

2

#define LIST_HEAD(name)

struct list_head name = LIST_HEAD_INIT(name)

LIST_HEAD_INIT 這個(gè)宏用于對(duì)定義的變量進(jìn)行雙向指針的初始化：

C

#define LIST_HEAD_INIT(name) { &(name), &(name) }

1

#define LIST_HEAD_INIT(name) { &(name), &(name) }

現(xiàn)在我看可以看一下函數(shù) misc_register 是如何進(jìn)行設(shè)備注冊(cè)的。首先是用 INIT_LIST_HEAD 對(duì) miscdevice->list 成員變量進(jìn)行初始化：

C

INIT_LIST_HEAD(&misc->list);

1

INIT_LIST_HEAD(&misc->list);

這個(gè)操作與 LIST_HEAD_INIT 宏一致：

C

static inline void INIT_LIST_HEAD(struct list_head *list){ list->next = list; list->prev = list;}

1

2

3

4

5

static inline void INIT_LIST_HEAD(struct list_head *list)

{

list->next = list;

list->prev = list;

}

接下來(lái)，在通過(guò)函數(shù) device_create 進(jìn)行設(shè)備創(chuàng)建，同時(shí)將設(shè)備添加到 Misc 設(shè)備列表中：

C

list_add(&misc->list, &misc_list);

1

list_add(&misc->list, &misc_list);

內(nèi)核的 list.h文件提供向鏈表添加節(jié)點(diǎn)的 API，這里是添加操作的實(shí)現(xiàn)：

C

static inline void list_add(struct list_head *new, struct list_head *head){ __list_add(new, head, head->next);}

1

2

3

4

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

{

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

}

函數(shù)實(shí)現(xiàn)很簡(jiǎn)單，就是入?yún)⑥D(zhuǎn)換為三個(gè)參數(shù)后調(diào)用內(nèi)部 __list_add ：

new – 新節(jié)點(diǎn);

head – 新節(jié)點(diǎn)插入的雙向鏈表頭;

head->next – 鏈表頭的下一個(gè)節(jié)點(diǎn);

_list_add 函數(shù)的實(shí)現(xiàn)更加簡(jiǎn)單：

C

static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next){ next->prev = new; new->next = next; new->prev = prev; prev->next = new;}

1

2

3

4

5

6

7

8

9

static inline void __list_add(struct list_head *new,

struct list_head *prev,

struct list_head *next)

{

next->prev = new;

new->next = next;

new->prev = prev;

prev->next = new;

}

這里設(shè)置了新添加結(jié)點(diǎn)的 prev 與 next 指針，通過(guò)這些操作，就將先前使用 LIST_HEAD_INIT 所定義的 misc 鏈表的雙向指針與 miscdevice->list 結(jié)構(gòu)關(guān)聯(lián)起來(lái)。

這里還有一個(gè)問(wèn)題，就是如何獲取鏈表中的數(shù)據(jù)，list_head 提供了一個(gè)特殊的宏用于獲取數(shù)據(jù)指針。

C

#define list_entry(ptr, type, member) container_of(ptr, type, member)

1

2

#define list_entry(ptr, type, member)

container_of(ptr, type, member)

這里有三個(gè)參數(shù)

ptr：list_head 結(jié)構(gòu)指針

type：數(shù)據(jù)對(duì)應(yīng)的 struct 類型

member：數(shù)據(jù)中 list_head 成員對(duì)應(yīng)的成員變量名

舉例如下：

C

const struct miscdevice *p = list_entry(v, struct miscdevice, list)

1

const struct miscdevice *p = list_entry(v, struct miscdevice, list)

接下來(lái)我們就夠訪問(wèn) miscdevice 的各個(gè)成員，如 p->minor、p->name 等等，我們看一下 list_entry 的實(shí)現(xiàn)：

C

#define list_entry(ptr, type, member) container_of(ptr, type, member)

1

2

#define list_entry(ptr, type, member)

container_of(ptr, type, member)

其實(shí)現(xiàn)非常簡(jiǎn)單，就是使用入?yún)⒄{(diào)用 container_of 宏，宏的實(shí)現(xiàn)如下：

C

#define container_of(ptr, type, member) ({ const typeof( ((type *)0)->member ) *__mptr = (ptr); (type *)( (char *)__mptr - offsetof(type,member) );})

1

2

3

#define container_of(ptr, type, member) ({??????????????????????

const typeof( ((type *)0)->member ) *__mptr = (ptr);????

(type *)( (char *)__mptr - offsetof(type,member) );})

注意，宏使用了大括號(hào)表達(dá)式，對(duì)于大括號(hào)表達(dá)式，編譯器會(huì)展開(kāi)所有表達(dá)式，同時(shí)使用最后一個(gè)表達(dá)式的結(jié)果進(jìn)行返回。

舉個(gè)例子：

C

#include int main() { int i = 0; printf("i = %dn", ({++i; ++i;})); return 0;}

1

2

3

4

5

6

7

#include

int main() {

int i = 0;

printf("i = %dn", ({++i; ++i;}));

return 0;

}

輸出結(jié)果為 2 。

另一個(gè)關(guān)鍵是 typeof 關(guān)鍵字，這個(gè)非常簡(jiǎn)單，這個(gè)正如它的名字一樣，這個(gè)關(guān)鍵字返回的結(jié)果是變量的類型。當(dāng)我第一次看到這個(gè)宏時(shí)，最讓我覺(jué)得奇怪的是表達(dá)式 ((type*)0) 中的 0 值，實(shí)際上，使用 0 值作為地址這個(gè)是成員變量取得 struct 內(nèi)相對(duì)偏移地址的巧妙實(shí)現(xiàn)，我們?cè)賮?lái)看個(gè)例子：

C

#include struct s { int field1; char field2; char field3;};int main() { printf("%pn", &((struct s*)0)->field3); return 0;}

1

2

3

4

5

6

7

8

9

10

11

12

#include

struct s {

int field1;

char field2;

char field3;

};

int main() {

printf("%pn", &((struct s*)0)->field3);

return 0;

}

輸出結(jié)果為 0x5 。

還有一個(gè)專門用于獲取結(jié)構(gòu)體中某個(gè)成員變量偏移的宏，其實(shí)現(xiàn)與前面提到的宏非常類似：

C

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

1

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

這里對(duì) container_of 宏做個(gè)綜述，container_of 宏通過(guò) struct 中的 list_head 成員返回 struct 對(duì)應(yīng)數(shù)據(jù)的內(nèi)存地址。在宏的第一行定義了指向 list_head 成員的指針 __mptr ，并將 ptr 地址賦給 __mptr 。從技術(shù)實(shí)現(xiàn)的角度來(lái)看，實(shí)際并不需要這一行定義，但這個(gè)對(duì)于類型檢查而言非常有意義。這一行代碼確保結(jié)構(gòu)體（ type ）中存在 member 對(duì)應(yīng)的成員。第二行使用 offsetoff 宏計(jì)算出包含 member 的結(jié)構(gòu)體所對(duì)應(yīng)的內(nèi)存地址，就是這么簡(jiǎn)單。

當(dāng)然 list_add 與 list_entry 并非是 中的全部函數(shù)，對(duì)于雙向鏈表 list_head ，內(nèi)核還提供了以下的接口：

list_add

list_add_tail

list_del

list_replace

list_move

list_is_last

list_empty

list_cut_position

list_splice

未了，需要說(shuō)的是，內(nèi)核代碼中并不僅僅只有上述這些接口。

?