Linux Kernel中l(wèi)ist解讀

作者：Sam （甄峰） sam_code@hotmail.com

?

Sam之前看2.4kernel時，?？吹絃ist.也仔細看了一下，但現(xiàn)在長期沒有看kernel,沒有寫程序，已經忘記了很多。今天又看一看并記錄下來。

?

LinuxKernel中，常常需要使用雙向鏈表。在~/include/linux/list.h中，就定義了雙向鏈表和常用的function.

?

鏈表頭如下：

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

?

1.創(chuàng)建雙向鏈表（doubly linkedlist）：

INIT_LIST_HEAD(struct list_head*list)

代碼如下：

static inline void INIT_LIST_HEAD(struct list_head *list)
{
?list->next = list;
?list->prev = list;
}
將List的頭和尾都指向自身。

?

2. 添加內容到雙向鏈表：

2.1: 平常的添加：

2.1.1:將新項目添加到list的頭部（head之后第一個位置）。注意，此處head是指此雙向鏈表頭。

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

將參數(shù)一（new）添加到head之后。它調用

__list_add(new, head,head->next);也就是說，把new添加到head和head->next之間。

static inline void __list_add(structlist_head *new,
????????struct list_head *prev,
????????struct list_head *next) //它只是將new添加到prev和next之間
{
?next->prev = new;
?new->next = next;
?new->prev = prev;
?prev->next = new;
}

?

2.1.2：將新項目添加雙向鏈表最后一個位置（也就是head的priv）。注意此處head表示list頭。

static inline void list_add_tail(structlist_head *new, struct list_head *head)
{
?__list_add(new, head->prev,head);
}

則將new添加到head->prev和head之間了。

?

2.2:讀拷貝更新（rcu）模式的添加（smp_wmb()）（請看背景知識）

2.2.1: 將新項目加到以知的prev和next之間：

static inline void __list_add_rcu(structlist_head * new,
??struct list_head * prev, structlist_head * next)
{
?new->next = next;
?new->prev = prev;
?smp_wmb();
?next->prev = new;
?prev->next = new;
}//此處注意：smp_wmb();smp_wmb()防止編譯器和CPU優(yōu)化代碼執(zhí)行的順序。在這里，smp_wmb保證在它之前的兩行代碼執(zhí)行完了之后再執(zhí)行后兩行

?

2.2.2:將新項目添加到list的頭部（head之后第一個位置）。注意，此處head是指此雙向鏈表頭。

static inline void list_add_rcu(structlist_head *new, struct list_head *head)
{
?__list_add_rcu(new, head,head->next);
}

?

2.2.3：將新項目添加雙向鏈表最后一個位置（也就是head的priv）。注意此處head表示list頭。staticinline void list_add_tail_rcu(struct list_head *new,
?????structlist_head *head)
{
?__list_add_rcu(new, head->prev,head);
}

?

?

3. 從雙向鏈表刪除項目：

3.1:基本刪除函數(shù)：

static inline void __list_del(structlist_head * prev, struct list_head * next)
{
?next->prev = prev;
?prev->next = next;
}//只是將前一個和后一個互指

?

3.2:刪除指定項：

static inline void list_del(structlist_head *entry)
{
?__list_del(entry->prev,entry->next);
?entry->next = LIST_POISON1;
?entry->prev = LIST_POISON2;
}

?

3.3: 安全的刪除指定項：

static inline void list_del_rcu(structlist_head *entry)
{
?__list_del(entry->prev,entry->next);
?entry->prev = LIST_POISON2;
}

此處Sam并不很清楚怎么回事。

?

3.4：刪除并初始化某一項：

static inline void list_del_init(structlist_head *entry)
{
?__list_del(entry->prev,entry->next);
?INIT_LIST_HEAD(entry);
}

?

4.替換某項：

4.1 使用new 替換 old:

static inline void list_replace(structlist_head *old,
????structlist_head *new)
{
?new->next =old->next;
?new->next->prev =new;
?new->prev =old->prev;
?new->prev->next =new;
}

?

4.2 替換并初始化：

static inline voidlist_replace_init(struct list_head *old,
?????structlist_head *new)
{
?list_replace(old, new);
?INIT_LIST_HEAD(old);
}

?

4.3：安全替換：

static inline void list_replace_rcu(structlist_head *old,
????structlist_head *new)
{
?new->next =old->next;
?new->prev =old->prev;
?smp_wmb();
?new->next->prev =new;
?new->prev->next =new;
?old->prev = LIST_POISON2;
}

?

5. 移動項：

5.1移動到頭部

static inline void list_move(structlist_head *list, struct list_head *head)
{
?__list_del(list->prev,list->next);
?list_add(list, head);
}

?

?

5.2移動到尾部
static inline void list_move_tail(structlist_head *list,
?????struct list_head *head)
{
?__list_del(list->prev,list->next);
?list_add_tail(list, head);
}

6.測試項目是否為最后一項：

static inline int list_is_last(conststruct list_head *list,
????conststruct list_head *head)
{
?return list->next == head;
}

7. 測試list是否為空：

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

8. 兩個鏈表連接起來：

8.1：將list鏈表連接如head鏈表頭部：

static inline void __list_splice(structlist_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;
}

8.2：連接

static inline void list_splice(structlist_head *list, struct list_head *head)
{
?if (!list_empty(list))
??__list_splice(list,head);
}

?

8.3：連接并初始化：

將list連接到head頭部，再將list初始化：

static inline void list_splice_init(structlist_head *list,
???????struct list_head *head)
{
?if (!list_empty(list)) {
??__list_splice(list,head);
??INIT_LIST_HEAD(list);
?}
}

?

9.一些有用的宏：

9.1得到 list_entry(ptr, type, member)

簡單的講，這個宏的作用是：通過結構（type）中的某個變量(member)的指針（ptr）獲取結構本身的指針.

也就是說，type中包含一個成員變量member.且某個結構體實體中member的指針為ptr.則list_entry（）則返回的是：這個結構體實體的指針。至于如何做到的，請看背景知識3---container_of。

?

9.2:list_first_entry(ptr, type,member)?
得到ptr鏈表中下一個的struct的實體。

?

9.3:??list_for_each(pos,head)

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

它其實就是一個for循環(huán)，循環(huán)雙向鏈表一圈。

prefetch()是檔案快取技術，不用深究。

?

下面幾個宏與之類似：

__list_for_each(pos, head)? //不用檔案快取技術的循環(huán)

list_for_each_prev(pos, head) //向前循環(huán)

?

9.4: list_for_each_entry(pos,head, member)

這個宏是雙向鏈表中最常用的，也是最有用的。表示從以head為頭的雙向循環(huán)列表中，一個一個拿出包含此list項目的結構體（pos的類型），并放到pos中。

#define list_for_each_entry(pos, head,member)????
?for (pos =list_entry((head)->next, typeof(*pos),member);?
?????prefetch(pos->member.next),&pos->member != (head);?
?????pos = list_entry(pos->member.next, typeof(*pos),member))

因為有上面list_entry()的鋪墊，所以非常簡單。

參數(shù)一：pos就是一個結構體指針。這個結構體中會包含成員變量member.

參數(shù)二：head就是一個雙向鏈表頭。

參數(shù)三：pos結構體中的成員變量名。

pos = list_entry((head)->next, typeof(*pos),member)：pos得到雙向鏈表中第一個鏈表被包含的結構體實體。

&pos->member !=(head)：此結構體中的鏈表不是頭。

pos = list_entry(pos->member.next, typeof(*pos),member): pos得到雙向鏈表中下一個結構體實體。

?

?

Linux kernel 中雙向循環(huán)鏈表的使用：

在Linux內核鏈表中，需要用鏈表組織起來的數(shù)據(jù)通常會包含一個structlist_head成員，結構都通過這個list成員組織在一個鏈表中。

例如：在hid-core.c中，要組織一個report鏈表。

?

于是，首先使用

1）

INIT_LIST_HEAD（&device->report_enum[i].report_list）

struct hid_report {
?struct list_head list;
?unsignedid;?????
?unsignedtype;?????
?struct hid_field*field[HID_MAX_FIELDS];?
?unsignedmaxfield;????
?unsignedsize;?????
?struct hid_device*device;???
};

這就是需要用鏈表組織起來的數(shù)據(jù)通常會包含一個struct list_head成員。

?

2）。

list_add_tail(&report->list,&report_enum->report_list);

?將report類型的項目添加到剛才初始化的list中。

?

3).

list_for_each_entry(report,&hid->report_enum[HID_INPUT_REPORT].report_list,list)

遍歷?hid->report_enum[HID_INPUT_REPORT].report_list，從其中一個一個得到report.放到report中。

?

?

?

背景知識：

背景知識一：typeof:

typeof不是標準C的運算符，這是gcc的一個擴展.

它與sizeof() 語義類似，sizeof(exp)代表返回exp長度。則typeof(exp)返回的事exp類型。

?

例1：

int a;

typeof(&a) b;

因為a 為int型。所以&a為int*.

也就是說b 為int* 類型。

?

例2：

typedef struct

{

int size;

char t;

} ngate, *pngate;

?

typeof(((ngate *)0)->t) w;

這其實就是表示，w 的類型為：ngate的t的類型。

在這里0并不是真正的變量，可以把它理解為一個替代使用的符號。其意思更可以理解為一個被賦值了的變量，這個數(shù)可以不是0，，隨便什么數(shù)字都可以。

?

背景知識二：offsetof

kernel中定義如下：

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

與上面所以類似，（TYPE *）0 表示：0是指向TYPE的指針。

則 &（TYPE *）0->MEMBER表示：TYPE類型的實體0的變量MEMBER的地址，因為從0開始，所以它的地址就成為offset.再用size_t強制轉換，就是從struct頭到成員變量MEMBER的offset.

?

背景知識三：container_of(ptr, type,member)

Kernel中如下定義：

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

（type *）0: 表明某個實體為type類型的。

(（type *）0)->member表明這個實體的某個成員變量。

typeof((（type *）0)->member) *__mptr表明定了一個指向此成員變量類型的指針。

?

offsetof(type,member)表明成員變量member到結構體類型type頭的offset.

(type *)( (char*)__mptr - offsetof(type,member) 則表明：返回的是一個指向type的指針，此指針指向一個type類型的實體。而參數(shù)ptr則是這個實體中的某一個成員變量位置。

?

?

背景知識四：RCU（Read-CopyUpdate）

RCU是2.5/2.6內核中引入的新技術，它通過延遲寫操作來提高同步性能。

系統(tǒng)中數(shù)據(jù)讀取操作遠多于寫操作，而rwlock機制在smp環(huán)境下隨著處理機增多性能會迅速下降。針對這一應用背景，IBMLinux技術中心的Paul E.McKenney提出了"讀拷貝更新"的技術，并將其應用于Linux內核中。RCU技術的核心是寫操作分為寫-更新兩步，允許讀操作在任何時候無阻訪問，當系統(tǒng)有寫操作時，更新動作一直延遲到對該數(shù)據(jù)的所有讀操作完成為止。