linux核心連結清單分析

共享 Linux 核心連結清單分析

有人寫的核心連結清單分析，先放這兒漫漫看

發信人: jeffshia (小豆芽@[email protected]冠玉^_^變成胡蘿蔔), 信區: KernelTech

标題: linux-2.6.14之連結清單分析

發信站: 水木社群 (Sat Apr 1 11:05:39 2006), 轉信

from: http://www.linuxforum.net/

Linux核心源碼分析-連結清單代碼分析

分析人：餘旭

分析時間：2005年11月17日星期四 11:40:10 AM

雨溫度：10-11度

編号：1-4 類别：準備工作

Email： [email protected]

背景：開始在 http://www.linuxforum.net/ Linux核心技術論壇上面發貼，在網友的幫忙

下，解決了一些問題。

text,please claim the writer's name.

**************************************************

-------------雙向循環連結清單---------------------------

來源于：list.h

設計思想：盡可能的代碼重用，化大堆的連結清單設計為單個連結清單。

連結清單的構造：如果需要構造某類對象的特定清單，則在其結構中定義一個類型為list_head

指針的成員，通過這個成員将這類對象連接配接起來，形成所需清單，并通過通用連結清單函

數對其進行操作。其優點是隻需編寫通用連結清單函數，即可構造和操作不同對象的清單

，而無需為每類對象的每種清單編寫專用函數，實作了代碼的重用。

如果想對某種類型建立連結清單，就把一個list_head類型的變量嵌入到該類型中，用list_head

中的成員和相對應的處理函數來對連結清單進行周遊。如果想得到相應的結構的指針，使

用list_entry可以算出來。

-------------防止重複包含同一個頭檔案---------------

#ifndef _LINUX_LIST_H

#define _LINUX_LIST_H

...

#endif

用于防止重複包含同一個list.h頭檔案

-----------struct list_head{}及初始化宏---------

struct list_head

{

struct list_head *next, *prev;

};

list_head從字面上了解，好像是頭結點的意思。但從這裡的代碼來看卻是普通結點

的結構體。在後面的代碼中将list_head當成普通的結點來處理。

--LIST_HEAD_INIT()--LIST_HEAD()--INIT_LIST_HEAD()------

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

#define LIST_HEAD(name) /

struct list_head name = LIST_HEAD_INIT(name)

分析：name當為結構體struct list_head{}的一個結構體變量，&(name)為該結構體

變量的位址。用name結構體變量的始位址将該結構體變量進行初始化。

#define INIT_LIST_HEAD(ptr) do { /

(ptr)->next = (ptr); (ptr)->prev = (ptr); /

} while (0)

1.ptr為一個結構體的指針，而name為一個結構體變量；

2.ptr使用時候，當用括号，(ptr);

------------__list_add()---list_add()-------------

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.普通的在兩個非空結點中插入一個結點，注意new,prev,next都不能是空值。

2.即：适用于中間結點插入。首結點和尾結點則由于指針為空，不能用此函數。

3.在prev指針和next指針所指向的結點之間插入new指針所指向的結點。

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

)

{

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

}

在head和head->next兩指針所指向的結點之間插入new所指向的結點。

即：在head指針後面插入new所指向的結點。此函數用于在頭結點後面插入結點。

注意：對隻有一個單個結點的連結清單，則head->next為空，list_add（）不能用。

-------------list_add_tail()-------------------

static inline void list_add_tail(struct list_head *new, struct list_head

*head)

{

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

}

在頭結點指針head所指向結點的前面插入new所指向的結點。也相當于在尾結點後面

增加一個new所指向的結點。（條件是：head->prev當指向尾結點）

注意：

1.head->prev不能為空，即若head為頭結點，其head->prev當指向一個數值，一般為

指向尾結點，構成循環連結清單。

2.對隻有單個結點的頭結點調用此函數則會出錯。

-----------__list_del()---list_del()--------------

static inline void __list_del(struct list_head * prev, struct list_head *

next)

{

next->prev = prev;

prev->next = next;

}

在prev和next指針所指向的結點之間，兩者互相所指。在後面會看到：prev為待删除

的結點的前面一個結點，next為待删除的結點的後面一個結點。

static inline void list_del(struct list_head *entry)

{

__list_del(entry->prev, entry->next);

entry->next = LIST_POISON1;

entry->prev = LIST_POISON2;

}

删除entry所指的結點，同時将entry所指向的結點指針域封死。

對LIST_POISON1,LIST_POISON2的解釋說明：

Linux 核心中解釋：These are non-NULL pointers that will result in page faults

under normal circumstances, used to verify that nobody uses non-initialized

list entries.

#define LIST_POISON1 ((void *) 0x00100100)

#define LIST_POISON2 ((void *) 0x00200200)

正常思想是：entry->next = NULL; entry->prev = NULL;

注意：Linux核心中的‘=’都與前後隔了一個空格，這樣比緊靠前後要清晰。

---------------list_del_init()--------------------

static inline void list_del_init(struct list_head *entry)

{

__list_del(entry->prev, entry->next);

INIT_LIST_HEAD(entry);

}

删除entry所指向的結點，同時将entry所指向的結點的next，prev指針域指向自身。

-----------list_move()--list_move_tail()----------

static inline void list_move(struct list_head *list, struct list_head *head

)

{

__list_del(list->prev, list->next);

list_add(list, head);

}

将list結點前後兩個結點互相指向彼此，删除list指針所指向的結點，再将此結點插

入head，和head->next兩個指針所指向的結點之間。

即：将list所指向的結點移動到head所指向的結點的後面。

static inline void list_move_tail(struct list_head *list, struct list_head

*head)

{

__list_del(list->prev, list->next);

list_add_tail(list, head);

}

删除了list所指向的結點，将其插入到head所指向的結點的前面，如果head->prev指

向連結清單的尾結點的話，就是将list所指向的結點插入到連結清單的結尾。

---------------------list_empty(）-------------

static inline int list_empty(const struct list_head *head)

{

return head->next == head;

}

注意：

1.如果是隻有一個結點，head，head->next，head->prev都指向同一個結點，則這裡

會傳回1，但連結清單卻不為空，仍有一個頭結點

2.return 後面不帶括号，且為一個表達式。

3.測試連結清單是否為空,但這個空不是沒有任何結點，而是隻有一個頭結點。

--------------------list_empty_careful(）---------

static inline int list_empty_careful(const struct list_head *head)

{

struct list_head *next = head->next;

return (next == head) && (next == head->prev);

}

分析：

1.隻有一個頭結點head，這時head指向這個頭結點，head->next,head->prev指向head

，即：head==head->next==head->prev，這時候list_empty_careful（）函數傳回1

。

2.有兩個結點，head指向頭結點，head->next,head->prev均指向後面那個結點，即

：head->next==head->prev,而head!=head->next,head!=head->prev.是以函數将返

回0

3.有三個及三個以上的結點，這是一般的情況，自己容易分析了。

注意：這裡empty list是指隻有一個空的頭結點，而不是毫無任何結點。并且該頭結

點必須其head->next==head->prev==head

---------------__list_splice()------------------

static inline void __list_splice(struct list_head *list, struct list_head

*head)

{

struct list_head *first = list->next;

struct list_head *last = list->prev;

struct list_head *at = head->next;

first->prev = head;

head->next = first;

last->next = at;

at->prev = last;

}

--------------------list_splice()----------------

static inline void list_splice(struct list_head *list, struct list_head *

head)

{

if (!list_empty(list))

__list_splice(list, head);

}

分析：

情況1：

普遍的情況，每個連結清單都至少有3個以上的結點：

====>此處作者畫了圖，可顯示不出來，郁悶！！！

========》待作者上傳一個word文檔，圖在裡面。

-------------------------------------------------------------------------

------------------

這種情況會丢棄list所指向的結點，這是特意設計的，因為兩個連結清單有兩個頭結點，

要去掉一個頭結點。隻要一個頭結點。

-------------------------------------------------------------------------

--------------------------------------

特殊情況1：

初始情況：

------------------------------------------------------------------------

特殊情況2：

初始情況：

--------------------list_splice_init()-----------------------------------

static inline void list_splice_init(struct list_head *list,

struct list_head *head)

{

if (!list_empty(list))

{

__list_splice(list, head);

INIT_LIST_HEAD(list);

}

--------------------/asm-i386/posix_types.h-------

typedef unsigned int __kernel_size_t;

------/linux/types.h---------size_t---------------

#ifndef _SIZE_T

#define _SIZE_T

typedef __kernel_size_t size_t;

#endif

-------------/linux/compiler-gcc4.h--------------

#define __compiler_offsetof(a,b) __builtin_offsetof(a,b)

分析準備：__compiler_offsetof(),為gcc編譯器中的編譯方面的參數，查閱gcc方面

的文檔:

--->gcc.pdf.Download from http://www.gnu.org/。其中解釋如下：

#define offsetof(type, member) __builtin_offsetof (type, member)

自己分析：即：__builtin_offsetof(a,b)就是#define offsetof(TYPE, MEMBER) (

(size_t) &((TYPE *)0)->MEMBER)。__builtin_offsetof(a,b)和offsetof(TYPE,MEMBER

)本質一樣的，隻是offsetof()宏是由程式員自己來設計(詳見後面講解)。而__builtin_offsetof

()宏就是在編譯器中已經設計好了的函數，直接調用即可。明白了這個差別後，下面

的代碼很好了解。

-------/linux/stddef.h-----offsetof()-----------

#define __compiler_offsetof(a,b) __builtin_offsetof(a,b)

-------------------------------

#undef offsetof

#ifdef __compiler_offsetof

#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)

#else

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

#endif

1.對__compiler_offsetof()宏的分析：

__compiler_offsetof來确認編譯器中是否内建了功能同offsetof()宏一樣的宏。若

已經内建了這樣的宏，則offsetof()就是使用這個内建宏__compiler_offsetof()即

：__builtin_offsetof()宏。如果沒有定義__compiler_offsetof()宏，則offsetof

()宏就由程式員來設計之。

2.對offsetof()宏的分析：（以下引用論壇）---曾經的騰訊QQ的筆試題。

宿舍舍友參加qq筆試，回來讨論一道選擇題，求結構中成員偏移。

想起Linux核心連結清單，資料節點攜帶連結清單節點，通過連結清單通路資料的方法，用到offsetof

宏，今天把它翻了出來:

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

一共4步

1. ( (TYPE *)0 ) 将零轉型為TYPE類型指針;

2. ((TYPE *)0)->MEMBER 通路結構中的資料成員;

3. &( ( (TYPE *)0 )->MEMBER )取出資料成員的位址;

4.(size_t)(&(((TYPE*)0)->MEMBER))結果轉換類型.巧妙之處在于将0轉換成(TYPE*

)，結構以記憶體空間首位址0作為起始位址，則成員位址自然為偏移位址；

舉例說明：

#include<stdio.h>

typedef struct _test

{

char i;

int j;

char k;

}Test;

int main()

{

Test *p = 0;

printf("%p/n", &(p->k));

}

自己分析：這裡使用的是一個利用編譯器技術的小技巧，即先求得結構成員變量在結

構體中的相對于結構體的首位址的偏移位址，然後根據結構體的首位址為0，進而得

出該偏移位址就是該結構體變量在該結構體中的偏移，即：該結構體成員變量距離結

構體首的距離。在offsetof()中，這個member成員的位址實際上就是type資料結構中

member成員相對于結構變量的偏移量。對于給定一個結構，offsetof(type,member)

是一個常量，list_entry()正是利用這個不變的偏移量來求得連結清單資料項的變量位址

。

---------------------typeof()--------------------

--->我開始不懂，源代碼中也查不到，網上發貼請教。由liubo1977在 http://www.linuxforum/

.net上的Linux核心技術論壇上解答，QQ:84915771

答複：

unsigned int i;

typeof(i) x;

x=100;

printf("x:%d/n",x);

typeof() 是 gcc 的擴充，和 sizeof() 類似。

------------------------

container_of()和offsetof()并不僅用于連結清單操作，這裡最有趣的地方是 ((type *

)0)->member，它将0位址強制 "轉換" 為 type 結構的指針，再通路到 type 結構中

的 member 成員。在 container_of 宏中，它用來給 typeof() 提供參數，以獲得

member 成員的資料類型；

---------------container_of()--------------------

container_of() 來自/linux/kernel.h

核心中的注釋：container_of - cast a member of a tructure out to the containing

structure。

ptr: the pointer to the member.

type: the type of the container struct this is embedded in.

member:the name of the member within the truct.

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

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

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

自己分析：

1.(type *)0->member為設計一個type類型的結構體，起始位址為0，編譯器将結構體

的起始的位址加上此結構體成員變量的偏移得到此結構體成員變量的偏移位址，由于

結構體起始位址為0，是以此結構體成員變量的偏移位址就等于其成員變量在結構體

内的距離結構體開始部分的偏移量。即：&(type *)0->member就是取出其成員變量的

偏移位址。而其等于其在結構體内的偏移量:即為：(size_t)(& ((type *)0)->member

)經過size_t的強制類型轉換後，其數值為結構體内的偏移量。該偏移量這裡由offsetof

()求出。

2.typeof( ( (type *)0)->member )為取出member成員的變量類型。用其定義__mptr

指針.ptr為指向該成員變量的指針。__mptr為member資料類型的常量指針，其指向ptr

所指向的變量處。

3.(char *)__mptr轉換為位元組型指針。(char *)__mptr - offsetof(type,member)

)用來求出結構體起始位址（為char *型指針），然後(type *)( (char *)__mptr -

offsetof(type,member) )在(type *)作用下進行将位元組型的結構體起始指針轉換為

type *型的結構體起始指針。

這就是從結構體某成員變量指針來求出該結構體的首指針。指針類型從結構體某成員

變量類型轉換為該結構體類型。

-----------茶餘飯後一點小資料----------------------

學辛苦了，看點收集的小東東：

以下文字摘自微軟中國研究院前任院長，現微軟進階副總裁李開複先生《一封寫給中

國學生的信》：

“我的老闆 Rick室Rashid博士是目前微軟公司主管研究的進階副總裁，他已經功成

名就，卻始終保持一顆學習和進取的心。現在，他每年仍然編寫大約50,000行程式。

他認為：用最新的技術程式設計可以使他保持對計算機最前沿技術的敏感，使自己能夠不

斷進步。今天，有些博士生帶低年級的大學生和碩士生做項目，就自滿地認為自己已

經沒有必要再程式設計了。其實，這樣的做法是很不明智的。”

--------------arch-v32/cache.h------------------

#ifndef _ASM_CRIS_ARCH_CACHE_H

#define _ASM_CRIS_ARCH_CACHE_H

#define L1_CACHE_BYTES 32

#define L1_CACHE_SHIFT 5

#define L1_CACHE_SHIFT_MAX 5

#endif

分析：

也可用#define L1_CACHE_BYTES (1UL<<L1_CACHE_SHIFT)來實作

-------------asm-i386/cache.h--------------------

#ifndef __ARCH_I386_CACHE_H

#define __ARCH_I386_CACHE_H

#define L1_CACHE_SHIFT (CONFIG_X86_L1_CACHE_SHIFT)

#define L1_CACHE_BYTES (1 << L1_CACHE_SHIFT)

//largest L1 which this arch supports

#define L1_CACHE_SHIFT_MAX 7

#endif

分析：cache行在32位平台上多為32位元組，但在I386平台上也有128位元組的。

----------/linux/prefetch.h--------------------

這裡是核心中的解釋：(含有自己的分析)

#define _LINUX_PREFETCH_H

#ifndef ARCH_HAS_PREFETCH

static inline void prefetch(const void *x) {;}

#endif

#ifndef ARCH_HAS_PREFETCHW

static inline void prefetchw(const void *x) {;}

#endif

#ifndef ARCH_HAS_SPINLOCK_PREFETCH

#define spin_lock_prefetch(x) prefetchw(x)

#endif

#ifndef PREFETCH_STRIDE

#define PREFETCH_STRIDE (4*L1_CACHE_BYTES)

#endif //PREFETCH_STRIDE

static inline void prefetch_range(void *addr, size_t len)

{

#ifdef ARCH_HAS_PREFETCH

char *cp;

char *end = addr + len;

for (cp = addr; cp < end; cp += PREFETCH_STRIDE)

prefetch(cp);

#endif //ARCH_HAS_PREFETCH

}

#endif //_LINUX_PREFETCH_H

-----asm-x86_64/processor.h---prefetch()---------

static inline void prefetch(void *x)

{

asm volatile("prefetcht0 %0" :: "m" (*(unsigned long *)x));

}

分析：

将x指針作強制類型轉換為unsigned long *型，然後取出該記憶體操作數，送入高速緩

存。

----------------list_for_each()------------------

#define list_for_each(pos, head) /

for (pos = (head)->next; prefetch(pos->next), pos != (head); /

pos = pos->next)

----------------__list_for_each()-----------------

Linux Kernel 2.6.14中的解釋中的精華部分：

#define __list_for_each(pos, head) /

for (pos = (head)->next; pos != (head); pos = pos->next)

list_for_each()有prefetch()用于複雜的表的周遊，而__list_for_each()無prefetch

()用于簡單的表的周遊.

注意：head在宏定義中用了括号将其括起來.

----------------list_for_each_prev()-------------

#define list_for_each_prev(pos, head) /

for (pos = (head)->prev; prefetch(pos->prev), pos != (head); /

pos = pos->prev)

解釋類似上面的list_for_each()。

----------------list_for_each_safe()--------------

核心中解釋的精華部分：

#define list_for_each_safe(pos, n, head) /

for (pos = (head)->next, n = pos->next; pos != (head); /

pos = n, n = pos->next)

這是說你可以邊周遊邊删除，這就叫safe。十分精彩。剛開始時，我也一直不了解safe

的意思，後來在 http://www.linuxforum.net/論壇上搜尋list_for_each_safe找到了解答。

----------------list_entry()--------------------

#define list_entry(ptr, type, member) /

container_of(ptr, type, member)

分析：

list_entry()函數用于将指向某連結清單結點成員的指針調整到該連結清單的開始處，并指針

轉換為該連結清單結點的類型。

-------------list_for_each_entry()---------------

#define list_for_each_entry(pos, head, member) /

for (pos = list_entry((head)->next, t ypeof(*pos), member); /

prefetch(pos->member.next), &pos->member != (head); /

pos = list_entry(pos->member.next, typeof(*pos), member))

分析：

1.楊沙洲--國防科技大學計算機學院--2004年8月指出：

大多數情況下，周遊連結清單的時候都需要獲得連結清單節點資料項，也就是說list_for_each

()和list_entry()總是同時使用。對此Linux給出了一個list_for_each_entry()宏。

2.這是用于嵌套的結構體中的宏：（這個程式例子來自：《Linux核心分析及程式設計》

作者：倪繼利電子工業出版社）

struct example_struct

{

struct list_head list;

int priority;

... //其他結構體成員

};

struct example_struct *node = list_entry(ptr,struct example_struct,list);

自己分析：對比list_entry(ptr,type,member)可知有以下結果：

其中list相當于member成員，struct example_struct相當于type成員，ptr相當于ptr

成員。而list{}成員嵌套于example_struct{}裡面。ptr指向example_struct{}中的

list成員變量的。在list_entry（）作用下，将ptr指針回轉指向struct example_struct

{}結構體的開始處。

3.pos當指向外層結構體，比如指向struct example_struct{}的結點，最開始時候，

pos當指向第一個結點。而head開始時候也是指向第一個外層結點的裡面的這個内嵌

的連結清單結構體struct list_head{}，(head)->next則指向後繼的一個外層結點的内嵌

的連結清單結點struct list_head{} list。member即是指出該list為其内嵌的結點。

思路：用pos指向外層結構體的結點，用head指向内層嵌入的結構體的結點。用(head

)->next,pos->member.next(即：ptr->list.next)來在内嵌的結構體結點連結清單中周遊

。每周遊一個結點，就用list_entry()将内嵌的pos->member.next指針回轉為指向該

結點外層結構體起始處的指針，并将指針進行指針類型轉換為外層結構體型pos。&pos

->member! = (head)用pos外層指針引用member即：list成員，與内層嵌入的連結清單之

頭結點比較來為循環結束條件。

-------------list_for_each_entry_reverse()-------

#define list_for_each_entry_reverse(pos, head, member) /

for (pos = list_entry((head)->prev, typeof(*pos), m+ember); /

prefetch(pos->member.prev), &pos->member != (head); /

pos = list_entry(pos->member.prev, typeof(*pos), member))

分析類似上面。

---------------list_prepare_entry()---------------

1.函數背景：來自楊沙洲.國防科技大學計算機學院.2004年8月. http://www.linuxforum.net/

Linux 核心技術論壇：

楊在貼子中指出：如果周遊不是從連結清單頭開始，而是從已知的某個pos結點開始，則

可以使用list_for_each_entry_continue(pos,head,member)。有時還會出現這種需

求，即經過一系列計算後，如果pos有值，則從pos開始周遊，如果沒有，則從連結清單頭

開始，為此，Linux專門提供了一個list_prepare_entry(pos,head,member)宏，将它

的傳回值作為list_for_each_entry_continue()的pos參數，就可以滿足這一要求。

2.核心中的list_prepare_entry()的注釋及代碼：

核心源代碼:

#define list_prepare_entry(pos, head, member) /

((pos) ? : list_entry(head, typeof(*pos), member))

分析：

:前面是個空值，即：若pos不為空，則pos為其自身。等效于：

(pos)? （pos）: list_entry(head,typeof(*pos),member)

注意核心格式：:前後都加了空格。

------------list_for_each_entry_continue()--------

3.核心中的list_for_each_entry_continue()的注釋及代碼：

核心源代碼：

#define list_for_each_entry_continue(pos, head, member) /

for (pos = list_entry(pos->member.next, typeof(*pos), member); /

prefetch(pos->member.next), &pos->member != (head); /

pos = list_entry(pos->member.next, typeof(*pos), member))

分析見list_prepare_entry()中的函數背景。

-------------list_for_each_entry_safe()-----------

1.函數背景：來自楊沙洲.國防科技大學計算機學院.2004年8月. http://www.linuxforum.net/

Linux 核心技術論壇：

楊在貼子中指出：list_for_each_entry_safe(pos, n, head,member)，它們要求調

用者另外提供一個與pos同類型的指針n，在for循環中暫存pos下一個節點的位址，避

免因pos節點被釋放而造成的斷鍊。

2.核心中的注釋與源代碼：

#define list_for_each_entry_safe(pos, n, head, member) /

for (pos = list_entry((head)->next, typeof(*pos), member), /

n = list_entry(pos->member.next, typeof(*pos), member); /

&pos->member != (head); /

pos = n, n = list_entry(n->member.next, typeof(*n), member))

分析類似上面。容易明白。

--------list_for_each_entry_safe_continue()-------

#define list_for_each_entry_safe_continue(pos, n, head, member) /

for (pos = list_entry(pos->member.next, typeof(*pos), member), /

n = list_entry(pos->member.next, typeof(*pos), member); /

&pos->member != (head); /

pos = n, n = list_entry(n->member.next, typeof(*n), member))

linux核心連結清單分析

繼續閱讀

華為筆試軟體

LoadRunner參數化功能詳解

probe()函數是什麼時候被調用，裝置和驅動是怎麼聯系起來的

二叉樹先序、中序、後序三種周遊的非遞歸算法

淺談---測試Native Windows Command與Native PowerShell Command哪個效率高

C/C++頭檔案、函數使用說明

SOFTICE 使用說明 (斷點)

List control NM

設定某一行背景顔色的CListCtrl

VS2008 不在支援 Attributed ATL

BMP檔案結構及圖像每行位元組計算方法

linux網絡程式設計----發送與接收檔案

c寫檔案

處理PCX檔案

Linux網卡總結線速光子產品檢視網卡資訊檢視PCI資訊RSS（Receive Side Scaling）RPS（Receive Packet Steering）XPS（Transmit Packet Steering）FD（Flow Director）Rx/Tx Ring Buffer網卡多隊列

Linux裝置模型（中）之上層容器